Version: SMASH-2.2
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 >:
[legend]
Collaboration diagram for smash::Grid< Options >:
[legend]

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/c
[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  number_of_cells_[i] =
155  (strategy == CellSizeStrategy::Largest)
156  ? 2
157  : static_cast<int>(std::floor(length_[i] * index_factor[i]));
158 
159  if (number_of_cells_[i] == 0) {
160  // In case of zero cells, make at least one cell that is then smaller than
161  // the minimal cell length. This is ok for all setups, since all particles
162  // are inside the same cell, except for the box with peroidic boundary
163  // conditions, where we need a 2x2x2 grid.
164  number_of_cells_[i] = 1;
165  } else if (number_of_cells_[i] < 2 &&
167  // Double the minimal cell length exceeds the length of the box, but we
168  // need at least 2x2x2 cells for periodic boundaries.
169  std::string error_box_too_small =
170  "Input error: Your box is too small for the grid.\n"
171  "The minimal length of the box is given by: " +
172  std::to_string(2 * max_interaction_length) +
173  " fm with the given timestep size.\n"
174  "If you have large timesteps please reduce them.\n"
175  "A larger box or the use of testparticles also helps.\n"
176  "Please take a look at your config.";
177  throw std::runtime_error(error_box_too_small);
178  } else if (limit == CellNumberLimitation::ParticleNumber &&
179  number_of_cells_[i] > max_cells) {
180  number_of_cells_[i] = max_cells;
181  }
182  // Only bother rescaling the index_factor if the grid length is large enough
183  // for 1 full min. cell length, since all particles are anyway placed in the
184  // first cell along the i-th axis
185  if (length_[i] >= max_interaction_length) {
186  index_factor[i] = number_of_cells_[i] / length_[i];
187  // std::nextafter implements a safety margin so that no valid position
188  // inside the grid can reference an out-of-bounds cell
189  while (index_factor[i] * length_[i] >= number_of_cells_[i]) {
190  index_factor[i] = std::nextafter(index_factor[i], 0.);
191  }
192  assert(index_factor[i] * length_[i] < number_of_cells_[i]);
193  }
194  }
195 
196  if (O == GridOptions::Normal &&
197  all_of(number_of_cells_, [](SizeType n) { return n <= 2; })) {
198  // dilute limit:
199  // the grid would have <= 2x2x2 cells, meaning every particle has to be
200  // compared with every other particle anyway. Then we can just as well
201  // fall back to not using the grid at all
202  // For a grid with periodic boundaries the situation is different and we
203  // never want to have a grid smaller than 2x2x2.
204  logg[LGrid].debug(
205  "There would only be ", number_of_cells_,
206  " cells. Therefore the Grid falls back to a single cell / "
207  "particle list.");
208  number_of_cells_ = {1, 1, 1};
209  cell_volume_ = length_[0] * length_[1] * length_[2];
210  if (include_unformed_particles) {
211  cells_.clear();
212  cells_.reserve(1);
213  cells_.emplace_back(particles.copy_to_vector());
214  } else {
215  // filter out the particles that can not interact
216  cells_.resize(1);
217  cells_.front().reserve(particles.size());
218  std::copy_if(particles.begin(), particles.end(),
219  std::back_inserter(cells_.front()),
220  [&](const ParticleData &p) {
221  return p.xsec_scaling_factor(timestep_duration) > 0.0;
222  });
223  }
224  } else {
225  // construct a normal grid
226 
228  (length_[1] / number_of_cells_[1]) *
229  (length_[2] / number_of_cells_[2]);
230 
231  logg[LGrid].debug("min: ", min_position, "\nlength: ", length_,
232  "\ncell_volume: ", cell_volume_,
233  "\ncells: ", number_of_cells_,
234  "\nindex_factor: ", index_factor);
235 
236  // After the grid parameters are determined, we can start placing the
237  // particles in cells.
238  cells_.resize(number_of_cells_[0] * number_of_cells_[1] *
239  number_of_cells_[2]);
240 
241  // Returns the one-dimensional cell-index from the position vector inside
242  // the grid.
243  // This simply calculates the distance to min_position and multiplies it
244  // with index_factor to determine the 3 x,y,z indexes to pass to make_index.
245  auto &&cell_index_for = [&](const ParticleData &p) {
246  return make_index(
247  std::floor((p.position()[1] - min_position[0]) * index_factor[0]),
248  std::floor((p.position()[2] - min_position[1]) * index_factor[1]),
249  std::floor((p.position()[3] - min_position[2]) * index_factor[2]));
250  };
251  for (const auto &p : particles) {
252  if (!include_unformed_particles &&
253  (p.xsec_scaling_factor(timestep_duration) <= 0.0)) {
254  continue;
255  }
256  const auto idx = cell_index_for(p);
257 #ifndef NDEBUG
258  if (idx >= SizeType(cells_.size())) {
259  logg[LGrid].fatal(
261  "\nan out-of-bounds access would be necessary for the "
262  "particle ",
263  p,
264  "\nfor a grid with the following parameters:\nmin: ", min_position,
265  "\nlength: ", length_, "\ncells: ", number_of_cells_,
266  "\nindex_factor: ", index_factor, "\ncells_.size: ", cells_.size(),
267  "\nrequested index: ", idx);
268  throw std::runtime_error("out-of-bounds grid access on construction");
269  }
270 #endif
271  cells_[idx].push_back(p);
272  }
273  }
274 
275  logg[LGrid].debug(cells_);
276 }
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:279
#define SMASH_SOURCE_LOCATION
Hackery that is required to output the location in the source code where the log statement occurs.
Definition: logging.h:243
std::array< einhard::Logger<>, std::tuple_size< LogArea::AreaTuple >::value > logg
An array that stores all pre-configured Logger objects.
Definition: logging.cc:39
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.
Here is the call graph for this function:

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 279 of file grid.cc.

280  {
281  return (z * number_of_cells_[1] + y) * number_of_cells_[0] + x;
282 }
Here is the caller graph for this function:

◆ 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  }
Here is the call graph for this function:

◆ 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 292 of file grid.cc.

295  {
296  std::array<SizeType, 3> search_index;
297  SizeType &x = search_index[0];
298  SizeType &y = search_index[1];
299  SizeType &z = search_index[2];
300  SizeType search_cell_index = 0;
301  for (z = 0; z < number_of_cells_[2]; ++z) {
302  for (y = 0; y < number_of_cells_[1]; ++y) {
303  for (x = 0; x < number_of_cells_[0]; ++x, ++search_cell_index) {
304  assert(search_cell_index == make_index(search_index));
305  assert(search_cell_index >= 0);
306  assert(search_cell_index < SizeType(cells_.size()));
307  const ParticleList &search = cells_[search_cell_index];
308  search_cell_callback(search);
309 
310  const auto &dz_list = z == number_of_cells_[2] - 1 ? ZERO : ZERO_ONE;
311  const auto &dy_list = number_of_cells_[1] == 1
312  ? ZERO
313  : y == 0 ? ZERO_ONE
314  : y == number_of_cells_[1] - 1
317  const auto &dx_list = number_of_cells_[0] == 1
318  ? ZERO
319  : x == 0 ? ZERO_ONE
320  : x == number_of_cells_[0] - 1
323  for (SizeType dz : dz_list) {
324  for (SizeType dy : dy_list) {
325  for (SizeType dx : dx_list) {
326  const auto di = make_index(dx, dy, dz);
327  if (di > 0) {
328  neighbor_cell_callback(search, cells_[search_cell_index + di]);
329  }
330  }
331  }
332  }
333  }
334  }
335  }
336 }
static const std::initializer_list< GridBase::SizeType > ZERO_ONE
Definition: grid.cc:285
static const std::initializer_list< GridBase::SizeType > MINUS_ONE_ZERO
Definition: grid.cc:286
static const std::initializer_list< GridBase::SizeType > ZERO
Definition: grid.cc:284
static const std::initializer_list< GridBase::SizeType > MINUS_ONE_ZERO_ONE
Definition: grid.cc:287

◆ 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 358 of file grid.cc.

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

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: