Subversion Repositories gelsvn

Rev

Rev 61 | Rev 443 | Go to most recent revision | Only display areas with differences | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

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