cell_list_3d.hpp File Reference

Cache-coherent 3D cell list for O(1) amortized neighbour queries. More...

#include <vector>
#include <cmath>
#include <algorithm>
#include <cassert>
#include <tuple>

Go to the source code of this file.

Classes
class	num::CellList3D< Scalar >

Namespaces
namespace	num

Detailed Description

Cache-coherent 3D cell list for O(1) amortized neighbour queries.

Direct extension of CellList2D to three dimensions.

Algorithm

build() – O(n + C) counting sort over C = nx*ny*nz cells query() – O(k) sequential reads over 3x3x3 = 27 cells

iterate_pairs() – forward half-shell with 13 offsets In 3D there are 26 neighbour directions (3^3-1). The 13 "forward" offsets are chosen so that (A,B) is visited exactly once:

forward = (dz > 0) OR (dz == 0 AND dy > 0) OR (dz == 0 AND dy == 0 AND dx > 0)

This partitions all 26 directed edges into 13 unique unordered pairs. The 13 offsets: dz=1 layer (all 9): (-1,-1,1)(0,-1,1)(1,-1,1) (-1, 0,1)(0, 0,1)(1, 0,1) (-1, 1,1)(0, 1,1)(1, 1,1) dz=0, dy=1 (3): (-1,1,0) (0,1,0) (1,1,0) dz=0, dy=0, dx=1 (1): (1,0,0)

Template Parameters

Scalar

float or double

Definition in file cell_list_3d.hpp.