Version: SMASH-3.1
smash::Grid< Options > Class Template Reference

#include <grid.h>

template<GridOptions Options = GridOptions::Normal>
class smash::Grid< Options >

Abstracts a list of cells that partition the particles in the experiment into regions of space that can interact / cannot interact.

This class is used to construct a helper data structure to reduce the combinatorics of finding particle pairs that could interact (scatter). It takes a list of ParticleData objects and sorts them in such a way that it is easy to look only at lists of particles that have a chance of interacting.

Template Parameters
OptionsThis policy parameter determines whether ghost cells are created to support periodic boundaries, or not.

Definition at line 96 of file grid.h.

Inheritance diagram for smash::Grid< Options >:
smash::GridBase

Public Member Functions

 Grid (const Particles &particles, double min_cell_length, double timestep_duration, CellNumberLimitation limit, const bool include_unformed_particles=false, CellSizeStrategy strategy=CellSizeStrategy::Optimal)
 Constructs a grid from the given particle list particles. More...
 
 Grid (const std::pair< std::array< double, 3 >, std::array< double, 3 >> &min_and_length, const Particles &particles, double min_cell_length, double timestep_duration, CellNumberLimitation limit, const bool include_unformed_particles=false, CellSizeStrategy strategy=CellSizeStrategy::Optimal)
 Constructs a grid with the given minimum grid coordinates and grid length. More...
 
void iterate_cells (const std::function< void(const ParticleList &)> &search_cell_callback, const std::function< void(const ParticleList &, const ParticleList &)> &neighbor_cell_callback) const
 Iterates over all cells in the grid and calls the callback arguments with a search cell and 0 to 13 neighbor cells. More...
 
double cell_volume () const
 
void iterate_cells (const std::function< void(const ParticleList &)> &search_cell_callback, const std::function< void(const ParticleList &, const ParticleList &)> &neighbor_cell_callback) const
 Specialization of iterate_cells. More...
 
void iterate_cells (const std::function< void(const ParticleList &)> &search_cell_callback, const std::function< void(const ParticleList &, const ParticleList &)> &neighbor_cell_callback) const
 Specialization of iterate_cells. More...
 

Private Member Functions

SizeType make_index (SizeType x, SizeType y, SizeType z) const
 
SizeType make_index (std::array< SizeType, 3 > idx) const
 

Private Attributes

const std::array< double, 3 > length_
 The 3 lengths of the complete grid. Used for periodic boundary wrapping. More...
 
double cell_volume_
 The volume of a single cell. More...
 
std::array< int, 3 > number_of_cells_
 The number of cells in x, y, and z direction. More...
 
std::vector< ParticleList > cells_
 The cell storage. More...
 

Additional Inherited Members

- Public Types inherited from smash::GridBase
typedef int SizeType
 A type to store the sizes. More...
 
- Static Protected Member Functions inherited from smash::GridBase
static std::pair< std::array< double, 3 >, std::array< double, 3 > > find_min_and_length (const Particles &particles)
 

Constructor & Destructor Documentation

◆ Grid() [1/2]

template<GridOptions Options = GridOptions::Normal>
smash::Grid< Options >::Grid ( const Particles particles,
double  min_cell_length,
double  timestep_duration,
CellNumberLimitation  limit,
const bool  include_unformed_particles = false,
CellSizeStrategy  strategy = CellSizeStrategy::Optimal 
)
inline

Constructs a grid from the given particle list particles.

It automatically determines the necessary size for the grid from the positions of the particles.

Parameters
[in]particlesThe particles to place onto the grid.
[in]min_cell_lengthThe minimal length a cell must have.
[in]timestep_durationDuration of the timestep. It is necessary for formation times treatment: if particle is fully or partially formed before the end of the timestep, it has to be on the grid.
[in]limitLimitation of cell number
[in]include_unformed_particlesinclude unformed particles from the grid (worsens runtime)
[in]strategyThe strategy for determining the cell size

Definition at line 113 of file grid.h.

117  : Grid{find_min_and_length(particles),
118  std::move(particles),
119  min_cell_length,
120  timestep_duration,
121  limit,
122  include_unformed_particles,
123  strategy} {}
static std::pair< std::array< double, 3 >, std::array< double, 3 > > find_min_and_length(const Particles &particles)
Definition: grid.cc:87
Grid(const Particles &particles, double min_cell_length, double timestep_duration, CellNumberLimitation limit, const bool include_unformed_particles=false, CellSizeStrategy strategy=CellSizeStrategy::Optimal)
Constructs a grid from the given particle list particles.
Definition: grid.h:113

◆ Grid() [2/2]

template<GridOptions O>
template smash::Grid< Options >::Grid ( const std::pair< std::array< double, 3 >, std::array< double, 3 >> &  min_and_length,
const Particles particles,
double  min_cell_length,
double  timestep_duration,
CellNumberLimitation  limit,
const bool  include_unformed_particles = false,
CellSizeStrategy  strategy = CellSizeStrategy::Optimal 
)

Constructs a grid with the given minimum grid coordinates and grid length.

If you need periodic boundaries you have to use this constructor to set the correct length to use for wrapping particles around the borders.

Parameters
[in]min_and_lengthA pair consisting of the three min coordinates and the three lengths.
[in]particlesThe particles to place onto the grid.
[in]min_cell_lengthThe minimal length a cell must have.
[in]timestep_durationDuration of the timestep in fm.
[in]limitLimitation of cell number.
[in]include_unformed_particlesinclude unformed particles from the grid (worsens runtime).
[in]strategyThe strategy for determining the cell size.
Exceptions
runtime_errorif your box length is smaller than the grid length.

Definition at line 116 of file grid.cc.

121  : length_(min_and_length.second) {
122  const auto min_position = min_and_length.first;
123  const SizeType particle_count = particles.size();
124 
125  // very simple setup for non-periodic boundaries and largest cellsize strategy
126  if (O == GridOptions::Normal && strategy == CellSizeStrategy::Largest) {
127  number_of_cells_ = {1, 1, 1};
128  cell_volume_ = length_[0] * length_[1] * length_[2];
129  cells_.clear();
130  cells_.reserve(1);
131  cells_.emplace_back(particles.copy_to_vector());
132  return;
133  }
134 
135  // The number of cells is determined by the min and max coordinates where
136  // particles are positioned and the maximal interaction length (which equals
137  // the length of a cell).
138  // But don't let the number of cells exceed the actual number of particles.
139  // That would be overkill. Let max_cells³ ≤ particle_count (conversion to
140  // int truncates). Limit only applied for geometric criteiron, where grid
141  // is an optimisation and cells can be made larger.
142  const int max_cells =
143  (O == GridOptions::Normal)
144  ? std::cbrt(particle_count)
145  : std::max(2, static_cast<int>(std::cbrt(particle_count)));
146 
147  // This normally equals 1/max_interaction_length. If the number of cells
148  // is reduced (because of low density) then this value is smaller. If only
149  // one cell is used than this value might also be larger.
150  std::array<double, 3> index_factor = {1. / max_interaction_length,
151  1. / max_interaction_length,
152  1. / max_interaction_length};
153  for (std::size_t i = 0; i < number_of_cells_.size(); ++i) {
154  if (strategy == CellSizeStrategy::Largest) {
155  number_of_cells_[i] = 2;
156  } else if (unlikely(length_[i] >
157  std::numeric_limits<int>::max() / index_factor[i])) {
158  throw std::overflow_error(
159  "An integer overflow would occur constructing the system grid.\n"
160  "Impossible to (further) simulate the provided system using "
161  "SMASH.\n"
162  "Refer to the user guide for more information (see the Modi "
163  "page).");
164  } else {
165  number_of_cells_[i] =
166  static_cast<int>(std::floor(length_[i] * index_factor[i]));
167  }
169  // In case of zero cells, make at least one cell that is then smaller than
170  // the minimal cell length. This is ok for all setups, since all particles
171  // are inside the same cell, except for the box with periodic boundary
172  // conditions, where we need a 2x2x2 grid.
173  number_of_cells_[i] = 1;
174  } else if (number_of_cells_[i] < 2 &&
176  // Double the minimal cell length exceeds the length of the box, but we
177  // need at least 2x2x2 cells for periodic boundaries.
178  std::string error_box_too_small =
179  "Input error: With the chosen time step (Delta_Time), your box is\n"
180  "too small for the grid. Using the provided time step, the minimal\n"
181  "length of the box should be " +
182  std::to_string(2 * max_interaction_length) +
183  "fm. Using a smaller time step\n"
184  "will reduce the minimal needed box size. The use of test particles\n"
185  "also helps reducing the minimum needed size. Have a look to the\n"
186  "user guide (e.g. box modus page) for further information.\n"
187  "Please, adjust your config file and run SMASH again.";
188  throw std::runtime_error(error_box_too_small);
189  } else if (limit == CellNumberLimitation::ParticleNumber &&
190  number_of_cells_[i] > max_cells) {
191  number_of_cells_[i] = max_cells;
192  }
193  // Only bother rescaling the index_factor if the grid length is large enough
194  // for 1 full min. cell length, since all particles are anyway placed in the
195  // first cell along the i-th axis
196  if (length_[i] >= max_interaction_length) {
197  index_factor[i] = number_of_cells_[i] / length_[i];
198  // std::nextafter implements a safety margin so that no valid position
199  // inside the grid can reference an out-of-bounds cell
200  while (index_factor[i] * length_[i] >= number_of_cells_[i]) {
201  index_factor[i] = std::nextafter(index_factor[i], 0.);
202  }
203  assert(index_factor[i] * length_[i] < number_of_cells_[i]);
204  }
205  }
206 
207  if (O == GridOptions::Normal &&
208  all_of(number_of_cells_, [](SizeType n) { return n <= 2; })) {
209  // dilute limit:
210  // the grid would have <= 2x2x2 cells, meaning every particle has to be
211  // compared with every other particle anyway. Then we can just as well
212  // fall back to not using the grid at all
213  // For a grid with periodic boundaries the situation is different and we
214  // never want to have a grid smaller than 2x2x2.
215  logg[LGrid].debug(
216  "There would only be ", number_of_cells_,
217  " cells. Therefore the Grid falls back to a single cell / "
218  "particle list.");
219  number_of_cells_ = {1, 1, 1};
220  cell_volume_ = length_[0] * length_[1] * length_[2];
221  if (include_unformed_particles) {
222  cells_.clear();
223  cells_.reserve(1);
224  cells_.emplace_back(particles.copy_to_vector());
225  } else {
226  // filter out the particles that can not interact
227  cells_.resize(1);
228  cells_.front().reserve(particles.size());
229  std::copy_if(particles.begin(), particles.end(),
230  std::back_inserter(cells_.front()),
231  [&](const ParticleData &p) {
232  return p.xsec_scaling_factor(timestep_duration) > 0.0;
233  });
234  }
235  } else {
236  // construct a normal grid
237 
239  (length_[1] / number_of_cells_[1]) *
240  (length_[2] / number_of_cells_[2]);
241 
242  logg[LGrid].debug("min: ", min_position, "\nlength: ", length_,
243  "\ncell_volume: ", cell_volume_,
244  "\ncells: ", number_of_cells_,
245  "\nindex_factor: ", index_factor);
246 
247  // After the grid parameters are determined, we can start placing the
248  // particles in cells.
249  cells_.resize(number_of_cells_[0] * number_of_cells_[1] *
250  number_of_cells_[2]);
251 
252  // Returns the one-dimensional cell-index from the position vector inside
253  // the grid.
254  // This simply calculates the distance to min_position and multiplies it
255  // with index_factor to determine the 3 x,y,z indexes to pass to make_index.
256  auto &&cell_index_for = [&](const ParticleData &p) {
257  return make_index(
258  std::floor((p.position()[1] - min_position[0]) * index_factor[0]),
259  std::floor((p.position()[2] - min_position[1]) * index_factor[1]),
260  std::floor((p.position()[3] - min_position[2]) * index_factor[2]));
261  };
262  for (const auto &p : particles) {
263  if (!include_unformed_particles &&
264  (p.xsec_scaling_factor(timestep_duration) <= 0.0)) {
265  continue;
266  }
267  const auto idx = cell_index_for(p);
268 #ifndef NDEBUG
269  if (idx >= SizeType(cells_.size())) {
270  logg[LGrid].fatal(
272  "\nan out-of-bounds access would be necessary for the "
273  "particle ",
274  p,
275  "\nfor a grid with the following parameters:\nmin: ", min_position,
276  "\nlength: ", length_, "\ncells: ", number_of_cells_,
277  "\nindex_factor: ", index_factor, "\ncells_.size: ", cells_.size(),
278  "\nrequested index: ", idx);
279  throw std::runtime_error("out-of-bounds grid access on construction");
280  }
281 #endif
282  cells_[idx].push_back(p);
283  }
284  }
285 
286  logg[LGrid].debug(cells_);
287 }
int SizeType
A type to store the sizes.
Definition: grid.h:70
const std::array< double, 3 > length_
The 3 lengths of the complete grid. Used for periodic boundary wrapping.
Definition: grid.h:190
std::array< int, 3 > number_of_cells_
The number of cells in x, y, and z direction.
Definition: grid.h:196
double cell_volume_
The volume of a single cell.
Definition: grid.h:193
std::vector< ParticleList > cells_
The cell storage.
Definition: grid.h:199
SizeType make_index(SizeType x, SizeType y, SizeType z) const
Definition: grid.cc:290
#define SMASH_SOURCE_LOCATION
Hackery that is required to output the location in the source code where the log statement occurs.
Definition: logging.h:153
std::array< einhard::Logger<>, std::tuple_size< LogArea::AreaTuple >::value > logg
An array that stores all pre-configured Logger objects.
Definition: logging.cc:39
#define unlikely(x)
Tell the branch predictor that this expression is likely false.
Definition: macros.h:16
constexpr int p
Proton.
constexpr int n
Neutron.
@ ParticleNumber
Limit the number of cells to the number of particles.
bool all_of(Container &&c, UnaryPredicate &&p)
Convenience wrapper for std::all_of that operates on a complete container.
Definition: algorithms.h:80
@ Normal
Without ghost cells.
@ PeriodicBoundaries
With ghost cells for periodic boundaries.
static constexpr int LGrid
Definition: grid.cc:81
@ Largest
Make cells as large as possible.

Member Function Documentation

◆ iterate_cells() [1/3]

template<GridOptions Options = GridOptions::Normal>
void smash::Grid< Options >::iterate_cells ( const std::function< void(const ParticleList &)> &  search_cell_callback,
const std::function< void(const ParticleList &, const ParticleList &)> &  neighbor_cell_callback 
) const

Iterates over all cells in the grid and calls the callback arguments with a search cell and 0 to 13 neighbor cells.

The neighbor cells are constructed like this:

  • one cell at x+1
  • three cells (x-1,x,x+1) at y+1
  • nine cells (x-1, y-1)...(x+1, y+1) at z+1
Parameters
[in]search_cell_callbackA callable called for/with every non-empty cell in the grid.
[in]neighbor_cell_callbackA callable called for/with every non-empty cell and adjacent cell combination. For a periodic grid, the first argument will be adjusted to wrap around the grid.

◆ cell_volume()

template<GridOptions Options = GridOptions::Normal>
double smash::Grid< Options >::cell_volume ( ) const
inline
Returns
the volume of a single grid cell

Definition at line 172 of file grid.h.

172 { return cell_volume_; }

◆ make_index() [1/2]

template<GridOptions Options>
Grid< Options >::SizeType smash::Grid< Options >::make_index ( SizeType  x,
SizeType  y,
SizeType  z 
) const
inlineprivate
Returns
the one-dimensional cell-index from the 3-dim index x, y, z.

Definition at line 290 of file grid.cc.

291  {
292  return (z * number_of_cells_[1] + y) * number_of_cells_[0] + x;
293 }

◆ make_index() [2/2]

template<GridOptions Options = GridOptions::Normal>
SizeType smash::Grid< Options >::make_index ( std::array< SizeType, 3 >  idx) const
inlineprivate
Returns
the one-dimensional cell-index from the 3-dim index idx. This is a convenience overload for the above function.

Definition at line 185 of file grid.h.

185  {
186  return make_index(idx[0], idx[1], idx[2]);
187  }

◆ iterate_cells() [2/3]

void smash::Grid< GridOptions::Normal >::iterate_cells ( const std::function< void(const ParticleList &)> &  search_cell_callback,
const std::function< void(const ParticleList &, const ParticleList &)> &  neighbor_cell_callback 
) const

Specialization of iterate_cells.

Definition at line 303 of file grid.cc.

306  {
307  std::array<SizeType, 3> search_index;
308  SizeType &x = search_index[0];
309  SizeType &y = search_index[1];
310  SizeType &z = search_index[2];
311  SizeType search_cell_index = 0;
312  for (z = 0; z < number_of_cells_[2]; ++z) {
313  for (y = 0; y < number_of_cells_[1]; ++y) {
314  for (x = 0; x < number_of_cells_[0]; ++x, ++search_cell_index) {
315  assert(search_cell_index == make_index(search_index));
316  assert(search_cell_index >= 0);
317  assert(search_cell_index < SizeType(cells_.size()));
318  const ParticleList &search = cells_[search_cell_index];
319  search_cell_callback(search);
320 
321  const auto &dz_list = z == number_of_cells_[2] - 1 ? ZERO : ZERO_ONE;
322  const auto &dy_list = number_of_cells_[1] == 1 ? ZERO
323  : y == 0 ? ZERO_ONE
324  : y == number_of_cells_[1] - 1
327  const auto &dx_list = number_of_cells_[0] == 1 ? ZERO
328  : x == 0 ? ZERO_ONE
329  : x == number_of_cells_[0] - 1
332  for (SizeType dz : dz_list) {
333  for (SizeType dy : dy_list) {
334  for (SizeType dx : dx_list) {
335  const auto di = make_index(dx, dy, dz);
336  if (di > 0) {
337  neighbor_cell_callback(search, cells_[search_cell_index + di]);
338  }
339  }
340  }
341  }
342  }
343  }
344  }
345 }
static const std::initializer_list< GridBase::SizeType > ZERO_ONE
Definition: grid.cc:296
static const std::initializer_list< GridBase::SizeType > MINUS_ONE_ZERO
Definition: grid.cc:297
static const std::initializer_list< GridBase::SizeType > ZERO
Definition: grid.cc:295
static const std::initializer_list< GridBase::SizeType > MINUS_ONE_ZERO_ONE
Definition: grid.cc:298

◆ iterate_cells() [3/3]

void smash::Grid< GridOptions::PeriodicBoundaries >::iterate_cells ( const std::function< void(const ParticleList &)> &  search_cell_callback,
const std::function< void(const ParticleList &, const ParticleList &)> &  neighbor_cell_callback 
) const

Specialization of iterate_cells.

Definition at line 367 of file grid.cc.

370  {
371  std::array<SizeType, 3> search_index;
372  SizeType &x = search_index[0];
373  SizeType &y = search_index[1];
374  SizeType &z = search_index[2];
375  SizeType search_cell_index = 0;
376 
377  // defaults:
378  std::array<NeighborLookup, 2> dz_list;
379  std::array<NeighborLookup, 3> dy_list;
380  std::array<NeighborLookup, 3> dx_list;
381 
382  assert(number_of_cells_[2] >= 2);
383  assert(number_of_cells_[1] >= 2);
384  assert(number_of_cells_[0] >= 2);
385 
386  for (z = 0; z < number_of_cells_[2]; ++z) {
387  dz_list[0].index = z;
388  dz_list[1].index = z + 1;
389  if (dz_list[1].index == number_of_cells_[2]) {
390  dz_list[1].index = 0;
391  // last z in the loop, so no need to reset wrap again
392  dz_list[1].wrap = NeedsToWrap::MinusLength;
393  }
394  for (y = 0; y < number_of_cells_[1]; ++y) {
395  dy_list[0].index = y;
396  dy_list[1].index = y - 1;
397  dy_list[2].index = y + 1;
398  dy_list[2].wrap = NeedsToWrap::No;
399  if (y == 0) {
400  dy_list[1] = dy_list[2];
401  dy_list[2].index = number_of_cells_[1] - 1;
402  dy_list[2].wrap = NeedsToWrap::PlusLength;
403  } else if (dy_list[2].index == number_of_cells_[1]) {
404  dy_list[2].index = 0;
405  dy_list[2].wrap = NeedsToWrap::MinusLength;
406  }
407  for (x = 0; x < number_of_cells_[0]; ++x, ++search_cell_index) {
408  dx_list[0].index = x;
409  dx_list[1].index = x - 1;
410  dx_list[2].index = x + 1;
411  dx_list[2].wrap = NeedsToWrap::No;
412  if (x == 0) {
413  dx_list[1] = dx_list[2];
414  dx_list[2].index = number_of_cells_[0] - 1;
415  dx_list[2].wrap = NeedsToWrap::PlusLength;
416  } else if (dx_list[2].index == number_of_cells_[0]) {
417  dx_list[2].index = 0;
418  dx_list[2].wrap = NeedsToWrap::MinusLength;
419  }
420 
421  assert(search_cell_index == make_index(search_index));
422  assert(search_cell_index >= 0);
423  assert(search_cell_index < SizeType(cells_.size()));
424  ParticleList search = cells_[search_cell_index];
425  search_cell_callback(search);
426 
427  auto virtual_search_index = search_index;
428  ThreeVector wrap_vector = {}; // no change
429  auto current_wrap_vector = wrap_vector;
430 
431  for (const auto &dz : dz_list) {
432  if (dz.wrap == NeedsToWrap::MinusLength) {
433  // last dz in the loop, so no need to undo the wrap
434  wrap_vector[2] = -length_[2];
435  virtual_search_index[2] = -1;
436  }
437  for (const auto &dy : dy_list) {
438  // only the last dy in dy_list can wrap
439  if (dy.wrap == NeedsToWrap::MinusLength) {
440  wrap_vector[1] = -length_[1];
441  virtual_search_index[1] = -1;
442  } else if (dy.wrap == NeedsToWrap::PlusLength) {
443  wrap_vector[1] = length_[1];
444  virtual_search_index[1] = number_of_cells_[1];
445  }
446  for (const auto &dx : dx_list) {
447  // only the last dx in dx_list can wrap
448  if (dx.wrap == NeedsToWrap::MinusLength) {
449  wrap_vector[0] = -length_[0];
450  virtual_search_index[0] = -1;
451  } else if (dx.wrap == NeedsToWrap::PlusLength) {
452  wrap_vector[0] = length_[0];
453  virtual_search_index[0] = number_of_cells_[0];
454  }
455  assert(dx.index >= 0);
456  assert(dx.index < number_of_cells_[0]);
457  assert(dy.index >= 0);
458  assert(dy.index < number_of_cells_[1]);
459  assert(dz.index >= 0);
460  assert(dz.index < number_of_cells_[2]);
461  const auto neighbor_cell_index =
462  make_index(dx.index, dy.index, dz.index);
463  assert(neighbor_cell_index >= 0);
464  assert(neighbor_cell_index < SizeType(cells_.size()));
465  if (neighbor_cell_index <= make_index(virtual_search_index)) {
466  continue;
467  }
468 
469  if (wrap_vector != current_wrap_vector) {
470  logg[LGrid].debug("translating search cell by ",
471  wrap_vector - current_wrap_vector);
472  for_each(search, [&](ParticleData &p) {
473  p = p.translated(wrap_vector - current_wrap_vector);
474  });
475  current_wrap_vector = wrap_vector;
476  }
477  neighbor_cell_callback(search, cells_[neighbor_cell_index]);
478  }
479  virtual_search_index[0] = search_index[0];
480  wrap_vector[0] = 0;
481  }
482  virtual_search_index[1] = search_index[1];
483  wrap_vector[1] = 0;
484  }
485  }
486  }
487  }
488 }
UnaryFunction for_each(Container &&c, UnaryFunction &&f)
Convenience wrapper for std::for_each that operates on a complete container.
Definition: algorithms.h:96

Member Data Documentation

◆ length_

template<GridOptions Options = GridOptions::Normal>
const std::array<double, 3> smash::Grid< Options >::length_
private

The 3 lengths of the complete grid. Used for periodic boundary wrapping.

Definition at line 190 of file grid.h.

◆ cell_volume_

template<GridOptions Options = GridOptions::Normal>
double smash::Grid< Options >::cell_volume_
private

The volume of a single cell.

Definition at line 193 of file grid.h.

◆ number_of_cells_

template<GridOptions Options = GridOptions::Normal>
std::array<int, 3> smash::Grid< Options >::number_of_cells_
private

The number of cells in x, y, and z direction.

Definition at line 196 of file grid.h.

◆ cells_

template<GridOptions Options = GridOptions::Normal>
std::vector<ParticleList> smash::Grid< Options >::cells_
private

The cell storage.

Definition at line 199 of file grid.h.


The documentation for this class was generated from the following files: