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

Public Member Functions

 Grid (const Particles &particles, double min_cell_length, double timestep_duration, CellNumberLimitation limit, 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, 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,
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]strategyThe strategy for determining the cell size

Definition at line 111 of file grid.h.

114  : Grid{find_min_and_length(particles),
115  std::move(particles),
116  min_cell_length,
117  timestep_duration,
118  limit,
119  strategy} {}
static std::pair< std::array< double, 3 >, std::array< double, 3 > > find_min_and_length(const Particles &particles)
Definition: grid.cc:72
Grid(const Particles &particles, double min_cell_length, double timestep_duration, CellNumberLimitation limit, CellSizeStrategy strategy=CellSizeStrategy::Optimal)
Constructs a grid from the given particle list particles.
Definition: grid.h:111

◆ 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,
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]strategyThe strategy for determining the cell size
Exceptions
runtime_errorif your box length is smaller than the grid length.

Definition at line 101 of file grid.cc.

106  : length_(min_and_length.second) {
107  const auto min_position = min_and_length.first;
108  const SizeType particle_count = particles.size();
109 
110  // very simple setup for non-periodic boundaries and largest cellsize strategy
111  if (O == GridOptions::Normal && strategy == CellSizeStrategy::Largest) {
112  number_of_cells_ = {1, 1, 1};
113  cell_volume_ = length_[0] * length_[1] * length_[2];
114  cells_.clear();
115  cells_.reserve(1);
116  cells_.emplace_back(particles.copy_to_vector());
117  return;
118  }
119 
120  // The number of cells is determined by the min and max coordinates where
121  // particles are positioned and the maximal interaction length (which equals
122  // the length of a cell).
123  // But don't let the number of cells exceed the actual number of particles.
124  // That would be overkill. Let max_cells³ ≤ particle_count (conversion to
125  // int truncates). Limit only applied for geometric criteiron, where grid
126  // is an optimisation and cells can be made larger.
127  const int max_cells =
128  (O == GridOptions::Normal)
129  ? std::cbrt(particle_count)
130  : std::max(2, static_cast<int>(std::cbrt(particle_count)));
131 
132  // This normally equals 1/max_interaction_length. If the number of cells
133  // is reduced (because of low density) then this value is smaller. If only
134  // one cell is used than this value might also be larger.
135  std::array<double, 3> index_factor = {1. / max_interaction_length,
136  1. / max_interaction_length,
137  1. / max_interaction_length};
138  for (std::size_t i = 0; i < number_of_cells_.size(); ++i) {
139  number_of_cells_[i] =
140  (strategy == CellSizeStrategy::Largest)
141  ? 2
142  : static_cast<int>(std::floor(length_[i] * index_factor[i]));
143 
144  if (number_of_cells_[i] == 0) {
145  // In case of zero cells, make at least one cell that is then smaller than
146  // the minimal cell length. This is ok for all setups, since all particles
147  // are inside the same cell, except for the box with peroidic boundary
148  // conditions, where we need a 2x2x2 grid.
149  number_of_cells_[i] = 1;
150  } else if (number_of_cells_[i] < 2 &&
152  // Double the minimal cell length exceeds the length of the box, but we
153  // need at least 2x2x2 cells for periodic boundaries.
154  std::string error_box_too_small =
155  "Input error: Your box is too small for the grid.\n"
156  "The minimal length of the box is given by: " +
157  std::to_string(2 * max_interaction_length) +
158  " fm with the given timestep size.\n"
159  "If you have large timesteps please reduce them.\n"
160  "A larger box or the use of testparticles also helps.\n"
161  "Please take a look at your config.";
162  throw std::runtime_error(error_box_too_small);
163  } else if (limit == CellNumberLimitation::ParticleNumber &&
164  number_of_cells_[i] > max_cells) {
165  number_of_cells_[i] = max_cells;
166  }
167  // Only bother rescaling the index_factor if the grid length is large enough
168  // for 1 full min. cell length, since all particles are anyway placed in the
169  // first cell along the i-th axis
170  if (length_[i] >= max_interaction_length) {
171  index_factor[i] = number_of_cells_[i] / length_[i];
172  // std::nextafter implements a safety margin so that no valid position
173  // inside the grid can reference an out-of-bounds cell
174  while (index_factor[i] * length_[i] >= number_of_cells_[i]) {
175  index_factor[i] = std::nextafter(index_factor[i], 0.);
176  }
177  assert(index_factor[i] * length_[i] < number_of_cells_[i]);
178  }
179  }
180 
181  if (O == GridOptions::Normal &&
182  all_of(number_of_cells_, [](SizeType n) { return n <= 2; })) {
183  // dilute limit:
184  // the grid would have <= 2x2x2 cells, meaning every particle has to be
185  // compared with every other particle anyway. Then we can just as well
186  // fall back to not using the grid at all
187  // For a grid with periodic boundaries the situation is different and we
188  // never want to have a grid smaller than 2x2x2.
189  logg[LGrid].debug(
190  "There would only be ", number_of_cells_,
191  " cells. Therefore the Grid falls back to a single cell / "
192  "particle list.");
193  number_of_cells_ = {1, 1, 1};
194  cell_volume_ = length_[0] * length_[1] * length_[2];
195  cells_.resize(1);
196  cells_.front().reserve(particles.size());
197  std::copy_if(particles.begin(), particles.end(),
198  std::back_inserter(cells_.front()),
199  [&](const ParticleData &p) {
200  return p.xsec_scaling_factor(timestep_duration) > 0.0;
201  }); // filter out the particles that can not interact
202  } else {
203  // construct a normal grid
204 
206  (length_[1] / number_of_cells_[1]) *
207  (length_[2] / number_of_cells_[2]);
208 
209  logg[LGrid].debug("min: ", min_position, "\nlength: ", length_,
210  "\ncell_volume: ", cell_volume_,
211  "\ncells: ", number_of_cells_,
212  "\nindex_factor: ", index_factor);
213 
214  // After the grid parameters are determined, we can start placing the
215  // particles in cells.
216  cells_.resize(number_of_cells_[0] * number_of_cells_[1] *
217  number_of_cells_[2]);
218 
219  // Returns the one-dimensional cell-index from the position vector inside
220  // the grid.
221  // This simply calculates the distance to min_position and multiplies it
222  // with index_factor to determine the 3 x,y,z indexes to pass to make_index.
223  auto &&cell_index_for = [&](const ParticleData &p) {
224  return make_index(
225  std::floor((p.position()[1] - min_position[0]) * index_factor[0]),
226  std::floor((p.position()[2] - min_position[1]) * index_factor[1]),
227  std::floor((p.position()[3] - min_position[2]) * index_factor[2]));
228  };
229 
230  for (const auto &p : particles) {
231  if (p.xsec_scaling_factor(timestep_duration) > 0.0) {
232  const auto idx = cell_index_for(p);
233 #ifndef NDEBUG
234  if (idx >= SizeType(cells_.size())) {
235  logg[LGrid].fatal(
237  "\nan out-of-bounds access would be necessary for the "
238  "particle ",
239  p, "\nfor a grid with the following parameters:\nmin: ",
240  min_position, "\nlength: ", length_,
241  "\ncells: ", number_of_cells_, "\nindex_factor: ", index_factor,
242  "\ncells_.size: ", cells_.size(), "\nrequested index: ", idx);
243  throw std::runtime_error("out-of-bounds grid access on construction");
244  }
245 #endif
246  cells_[idx].push_back(p);
247  }
248  }
249  }
250 
251  logg[LGrid].debug(cells_);
252 }
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:183
std::array< int, 3 > number_of_cells_
The number of cells in x, y, and z direction.
Definition: grid.h:189
double cell_volume_
The volume of a single cell.
Definition: grid.h:186
std::vector< ParticleList > cells_
The cell storage.
Definition: grid.h:192
SizeType make_index(SizeType x, SizeType y, SizeType z) const
Definition: grid.cc:255
#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:66
@ 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 165 of file grid.h.

165 { 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 255 of file grid.cc.

256  {
257  return (z * number_of_cells_[1] + y) * number_of_cells_[0] + x;
258 }
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 178 of file grid.h.

178  {
179  return make_index(idx[0], idx[1], idx[2]);
180  }
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 268 of file grid.cc.

271  {
272  std::array<SizeType, 3> search_index;
273  SizeType &x = search_index[0];
274  SizeType &y = search_index[1];
275  SizeType &z = search_index[2];
276  SizeType search_cell_index = 0;
277  for (z = 0; z < number_of_cells_[2]; ++z) {
278  for (y = 0; y < number_of_cells_[1]; ++y) {
279  for (x = 0; x < number_of_cells_[0]; ++x, ++search_cell_index) {
280  assert(search_cell_index == make_index(search_index));
281  assert(search_cell_index >= 0);
282  assert(search_cell_index < SizeType(cells_.size()));
283  const ParticleList &search = cells_[search_cell_index];
284  search_cell_callback(search);
285 
286  const auto &dz_list = z == number_of_cells_[2] - 1 ? ZERO : ZERO_ONE;
287  const auto &dy_list = number_of_cells_[1] == 1
288  ? ZERO
289  : y == 0 ? ZERO_ONE
290  : y == number_of_cells_[1] - 1
293  const auto &dx_list = number_of_cells_[0] == 1
294  ? ZERO
295  : x == 0 ? ZERO_ONE
296  : x == number_of_cells_[0] - 1
299  for (SizeType dz : dz_list) {
300  for (SizeType dy : dy_list) {
301  for (SizeType dx : dx_list) {
302  const auto di = make_index(dx, dy, dz);
303  if (di > 0) {
304  neighbor_cell_callback(search, cells_[search_cell_index + di]);
305  }
306  }
307  }
308  }
309  }
310  }
311  }
312 }
static const std::initializer_list< GridBase::SizeType > ZERO_ONE
Definition: grid.cc:261
static const std::initializer_list< GridBase::SizeType > MINUS_ONE_ZERO
Definition: grid.cc:262
static const std::initializer_list< GridBase::SizeType > ZERO
Definition: grid.cc:260
static const std::initializer_list< GridBase::SizeType > MINUS_ONE_ZERO_ONE
Definition: grid.cc:263

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

337  {
338  std::array<SizeType, 3> search_index;
339  SizeType &x = search_index[0];
340  SizeType &y = search_index[1];
341  SizeType &z = search_index[2];
342  SizeType search_cell_index = 0;
343 
344  // defaults:
345  std::array<NeighborLookup, 2> dz_list;
346  std::array<NeighborLookup, 3> dy_list;
347  std::array<NeighborLookup, 3> dx_list;
348 
349  assert(number_of_cells_[2] >= 2);
350  assert(number_of_cells_[1] >= 2);
351  assert(number_of_cells_[0] >= 2);
352 
353  for (z = 0; z < number_of_cells_[2]; ++z) {
354  dz_list[0].index = z;
355  dz_list[1].index = z + 1;
356  if (dz_list[1].index == number_of_cells_[2]) {
357  dz_list[1].index = 0;
358  // last z in the loop, so no need to reset wrap again
359  dz_list[1].wrap = NeedsToWrap::MinusLength;
360  }
361  for (y = 0; y < number_of_cells_[1]; ++y) {
362  dy_list[0].index = y;
363  dy_list[1].index = y - 1;
364  dy_list[2].index = y + 1;
365  dy_list[2].wrap = NeedsToWrap::No;
366  if (y == 0) {
367  dy_list[1] = dy_list[2];
368  dy_list[2].index = number_of_cells_[1] - 1;
369  dy_list[2].wrap = NeedsToWrap::PlusLength;
370  } else if (dy_list[2].index == number_of_cells_[1]) {
371  dy_list[2].index = 0;
372  dy_list[2].wrap = NeedsToWrap::MinusLength;
373  }
374  for (x = 0; x < number_of_cells_[0]; ++x, ++search_cell_index) {
375  dx_list[0].index = x;
376  dx_list[1].index = x - 1;
377  dx_list[2].index = x + 1;
378  dx_list[2].wrap = NeedsToWrap::No;
379  if (x == 0) {
380  dx_list[1] = dx_list[2];
381  dx_list[2].index = number_of_cells_[0] - 1;
382  dx_list[2].wrap = NeedsToWrap::PlusLength;
383  } else if (dx_list[2].index == number_of_cells_[0]) {
384  dx_list[2].index = 0;
385  dx_list[2].wrap = NeedsToWrap::MinusLength;
386  }
387 
388  assert(search_cell_index == make_index(search_index));
389  assert(search_cell_index >= 0);
390  assert(search_cell_index < SizeType(cells_.size()));
391  ParticleList search = cells_[search_cell_index];
392  search_cell_callback(search);
393 
394  auto virtual_search_index = search_index;
395  ThreeVector wrap_vector = {}; // no change
396  auto current_wrap_vector = wrap_vector;
397 
398  for (const auto &dz : dz_list) {
399  if (dz.wrap == NeedsToWrap::MinusLength) {
400  // last dz in the loop, so no need to undo the wrap
401  wrap_vector[2] = -length_[2];
402  virtual_search_index[2] = -1;
403  }
404  for (const auto &dy : dy_list) {
405  // only the last dy in dy_list can wrap
406  if (dy.wrap == NeedsToWrap::MinusLength) {
407  wrap_vector[1] = -length_[1];
408  virtual_search_index[1] = -1;
409  } else if (dy.wrap == NeedsToWrap::PlusLength) {
410  wrap_vector[1] = length_[1];
411  virtual_search_index[1] = number_of_cells_[1];
412  }
413  for (const auto &dx : dx_list) {
414  // only the last dx in dx_list can wrap
415  if (dx.wrap == NeedsToWrap::MinusLength) {
416  wrap_vector[0] = -length_[0];
417  virtual_search_index[0] = -1;
418  } else if (dx.wrap == NeedsToWrap::PlusLength) {
419  wrap_vector[0] = length_[0];
420  virtual_search_index[0] = number_of_cells_[0];
421  }
422  assert(dx.index >= 0);
423  assert(dx.index < number_of_cells_[0]);
424  assert(dy.index >= 0);
425  assert(dy.index < number_of_cells_[1]);
426  assert(dz.index >= 0);
427  assert(dz.index < number_of_cells_[2]);
428  const auto neighbor_cell_index =
429  make_index(dx.index, dy.index, dz.index);
430  assert(neighbor_cell_index >= 0);
431  assert(neighbor_cell_index < SizeType(cells_.size()));
432  if (neighbor_cell_index <= make_index(virtual_search_index)) {
433  continue;
434  }
435 
436  if (wrap_vector != current_wrap_vector) {
437  logg[LGrid].debug("translating search cell by ",
438  wrap_vector - current_wrap_vector);
439  for_each(search, [&](ParticleData &p) {
440  p = p.translated(wrap_vector - current_wrap_vector);
441  });
442  current_wrap_vector = wrap_vector;
443  }
444  neighbor_cell_callback(search, cells_[neighbor_cell_index]);
445  }
446  virtual_search_index[0] = search_index[0];
447  wrap_vector[0] = 0;
448  }
449  virtual_search_index[1] = search_index[1];
450  wrap_vector[1] = 0;
451  }
452  }
453  }
454  }
455 }
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 183 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 186 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 189 of file grid.h.

◆ cells_

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

The cell storage.

Definition at line 192 of file grid.h.


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