Subversion Repositories gelsvn

Rev

Rev 89 | Only display areas with differences | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

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