| 61 |
jab |
1 |
#ifndef __CELL_H
|
|
|
2 |
#define __CELL_H
|
|
|
3 |
|
|
|
4 |
#include <vector>
|
|
|
5 |
#include "CGLA/Vec3i.h"
|
|
|
6 |
#include "CGLA/BitMask.h"
|
|
|
7 |
#include "RGrid.h"
|
|
|
8 |
|
|
|
9 |
namespace Geometry
|
|
|
10 |
{
|
|
|
11 |
/** Class template for a cell in a hierarchical grid.
|
|
|
12 |
The template arguments are the type and the cell dimension.
|
|
|
13 |
A Cell is much like an RGrid - except that a Cell may
|
|
|
14 |
be coalesced into a single value and then split again
|
|
|
15 |
when a new value is inserted. Also cells are constrained to
|
|
|
16 |
be of size NxNxN where N=2^m for some m. This makes some things
|
|
|
17 |
faster.
|
|
|
18 |
|
|
|
19 |
The reason for making CELL_DIM a template argument rather
|
|
|
20 |
than a constructor argument is that we generally have many
|
|
|
21 |
cells and do not wish that each cell contains its dimension.
|
|
|
22 |
*/
|
|
|
23 |
template<class T, int CELL_DIM, class ChildT>
|
|
|
24 |
class Cell
|
|
|
25 |
{
|
|
|
26 |
public:
|
|
|
27 |
typedef T DataType;
|
|
|
28 |
|
|
|
29 |
private:
|
|
|
30 |
bool touched;
|
|
|
31 |
|
|
|
32 |
/// Linear array containing data of this Cell.
|
|
|
33 |
std::vector<T> data;
|
|
|
34 |
|
|
|
35 |
/** Return a bit mask used to mask indices.
|
|
|
36 |
Some functions in this class are passed a Vec3i
|
|
|
37 |
whose lower bits index into the cell. The mask is
|
|
|
38 |
used to select these lower bits before the 3D
|
|
|
39 |
index is converted to a linear index.
|
|
|
40 |
|
|
|
41 |
If you are wondering about why the static variable
|
|
|
42 |
inside the function is not simply a static member of
|
|
|
43 |
the class, check out item 47 og "Effective C++" by
|
|
|
44 |
Scott Meyers.
|
|
|
45 |
*/
|
|
|
46 |
static const CGLA::BitMask& get_bit_mask()
|
|
|
47 |
{
|
|
|
48 |
static const CGLA::BitMask bit_mask(CELL_DIM);
|
|
|
49 |
return bit_mask;
|
|
|
50 |
}
|
|
|
51 |
|
|
|
52 |
public:
|
|
|
53 |
|
|
|
54 |
/** Get dimensions of Cell. Returns only one value since
|
|
|
55 |
x, y, and z dimensions are the same. */
|
|
|
56 |
static int get_dim()
|
|
|
57 |
{
|
|
|
58 |
return CELL_DIM;
|
|
|
59 |
}
|
|
|
60 |
|
|
|
61 |
private:
|
|
|
62 |
|
|
|
63 |
/** Get index. Computes an index into the linear array representation
|
|
|
64 |
of the voxels in the cell from a 3D grid index. The top bits (which
|
|
|
65 |
have been used to find this Cell) are masked out. */
|
|
|
66 |
int get_idx(const CGLA::Vec3i& idx) const
|
|
|
67 |
{
|
|
|
68 |
CGLA::Vec3i bot_idx = get_bit_mask().mask(idx);
|
|
|
69 |
return (bot_idx[2]*get_dim()+bot_idx[1])*get_dim()+bot_idx[0];
|
|
|
70 |
}
|
|
|
71 |
|
|
|
72 |
protected:
|
|
|
73 |
|
|
|
74 |
/** Store a value in the Cell. If the Cell is
|
|
|
75 |
coalesced, it is first resized to contain CELL_DIMS
|
|
|
76 |
cubed voxels, and then the voxel is inserted. */
|
|
|
77 |
void store_priv(const CGLA::Vec3i& p, const T& new_val)
|
|
|
78 |
{
|
|
|
79 |
if(is_coalesced()) split();
|
|
|
80 |
touched = true;
|
|
|
81 |
data[get_idx(p)] = new_val;
|
|
|
82 |
}
|
|
|
83 |
|
|
|
84 |
|
|
|
85 |
public:
|
|
|
86 |
|
|
|
87 |
/** Create empty grid cell. A Cell contains initially a single value.
|
|
|
88 |
Reading (using operator[]) any voxel will yield this value. */
|
|
|
89 |
Cell(const T& val): data(1,val), touched(false)
|
|
|
90 |
{
|
|
|
91 |
assert(CELL_DIM==get_dim());
|
|
|
92 |
}
|
|
|
93 |
|
|
|
94 |
/** Clear cell. Removes Cell contents replacing it with a single
|
|
|
95 |
specified value. */
|
|
|
96 |
void coalesce(const T& val)
|
|
|
97 |
{
|
|
|
98 |
data=std::vector<T>(1,val);
|
|
|
99 |
touched = true;
|
|
|
100 |
}
|
|
|
101 |
|
|
|
102 |
/// Split cell - causes memory to be reserved for CELL_DIM^3 voxels.
|
|
|
103 |
void split()
|
|
|
104 |
{
|
|
|
105 |
T val = data[0];
|
|
|
106 |
data.resize(CGLA::qbe(CELL_DIM), val);
|
|
|
107 |
touched = true;
|
|
|
108 |
}
|
|
|
109 |
|
|
|
110 |
/// Check if the cell is coalesced
|
|
|
111 |
bool is_coalesced() const
|
|
|
112 |
{
|
|
|
113 |
// We rely on size() being constant time below.
|
|
|
114 |
// Probably this function should be changed.... it would be bad
|
|
|
115 |
// if it was slow ... very bad....
|
|
|
116 |
return data.size()==1;
|
|
|
117 |
}
|
|
|
118 |
|
|
|
119 |
|
|
|
120 |
/** Read access to voxel grid. This function is passed
|
|
|
121 |
a Vec3i and returns the corresponding voxel. If the
|
|
|
122 |
cell is coalesced, the single value stored is returned. */
|
|
|
123 |
const T& operator[](const CGLA::Vec3i& p) const
|
|
|
124 |
{
|
|
|
125 |
if(is_coalesced()) return data[0];
|
|
|
126 |
return *(&data[get_idx(p)]);
|
|
|
127 |
}
|
|
|
128 |
|
|
|
129 |
void store(const CGLA::Vec3i& p, const T& new_val)
|
|
|
130 |
{
|
|
|
131 |
return static_cast<ChildT&>(*this).store(p,new_val);
|
|
|
132 |
}
|
|
|
133 |
|
|
|
134 |
|
|
|
135 |
/** Const get a pointer to the first element in the linear
|
|
|
136 |
array representation of the grid. */
|
|
|
137 |
const T* get() const {return &data[0];}
|
|
|
138 |
|
|
|
139 |
/** Non-const get a pointer to the first element in the linear
|
|
|
140 |
array representation of the grid. */
|
|
|
141 |
T* get()
|
|
|
142 |
{
|
|
|
143 |
touched = true;
|
|
|
144 |
return &data[0];
|
|
|
145 |
}
|
|
|
146 |
|
|
|
147 |
void untouch() {touched=false;}
|
|
|
148 |
void touch() {touched=true;}
|
|
|
149 |
bool is_touched() const {return touched;}
|
|
|
150 |
|
|
|
151 |
};
|
|
|
152 |
|
|
|
153 |
|
|
|
154 |
template<class T, int CELL_DIM>
|
|
|
155 |
class DefaultCell: public Cell<T,CELL_DIM,DefaultCell<T, CELL_DIM> >
|
|
|
156 |
{
|
|
|
157 |
public:
|
|
|
158 |
DefaultCell(const T& val): Cell<T,CELL_DIM,DefaultCell>(val){}
|
|
|
159 |
void store(const CGLA::Vec3i& p, const T& new_val)
|
|
|
160 |
{
|
|
|
161 |
store_priv(p, new_val);
|
|
|
162 |
}
|
|
|
163 |
|
|
|
164 |
};
|
|
|
165 |
|
|
|
166 |
|
|
|
167 |
}
|
|
|
168 |
#endif
|