WebSVN – gelsvn – Diff – /trunk/src/Geometry/ThreeDDDA.h


#ifndef __THREEDDDA_H
#define __THREEDDDA_H
 
#ifdef _MSC_VER 
typedef __int64 Integer64Bits;
#else
typedef int64_t Integer64Bits;
#endif
 
 
#include "CGLA/Vec3f.h"
#include "CGLA/Vec3i.h"
 
namespace Geometry
{
 
 
	/** \brief A ThreeDDDA is a class for traversing a grid of cells. 
 
      We wish to 
			enumerate all cells pierced by the ray going from a point p0 to a 
			point p1. It is dangerous to use floating point arithmetic since rounding
			errors may accumulate entailing that the 3ddda misses the cell containing
			the end point of the ray.
		
			Daniel Cohen-Or devised a technique for exact ray traversal using only 
			integer arithmetic. Using integer arithmetic, the computations are
			exact, but the ray must start and terminate exactly at grid points.
			I.e. the ray must start and terminate in cell corners.
 
			To overcome this issue, I have implemented a scheme where the ray
			starts and terminates on a grid that is finer than the cell grid.
			This means that we have fast and exact computations, and the ray can
			travel between two almost arbitrary points.
 
			A central problem with this scheme was that - in order to simplify
			things during the iterative traversal - the ray direction vector
			is always mirrored into the first octant (+x +y +z).  If the fine
			grid used for the ray start and end points is a superset of the
			grid points of the cell grid, this mirroring is almost impossible
			to implement correctly. This is due to the fact that the first
			cell on the right side of the y axis is called 0,y whereas the
			first cell on the left is called -1,y. This lack of symmetry makes
			things very difficult, but by ensuring that the endpoints of a ray
			can never lie on an a corner, edge, or face of the cell grid, we
			can make the problems go away.
 
			Hence, in this implementation, the fine grid is obtained by dividing 
			the cell into NxNxN subcells, but the grid points	of the fine grid lie 
			at the CENTRES of these subcells.  
		
	*/
 
	class ThreeDDDA
	{
		/** Resolution of the grid. This number indicates how many subcells
				(along each axis) a cell is divided into. */
		const int PRECISION;
 
		/// Sign indicates which octant contains the direction vector.
		const CGLA::Vec3i sgn;
 
		/// Fine grid position where the ray begins
		const CGLA::Vec3i p0_int;
 
		// Fine grid position where the ray ends.
		const CGLA::Vec3i p1_int;
 
		/// The direction of the ray 
		const CGLA::Vec3i dir;
 
		/// The cell containing the initial point on the ray.
		const CGLA::Vec3i first_cell;
 
		/// The cell containing the last point on the ray.
		const CGLA::Vec3i last_cell;
 
		/** Number of steps. We can compute the number of steps that the
				ray will take in advance. */
		const int no_steps; 
 
		/** The direction vector, premultiplied by the step length.
				This constant is used to update the equations governing the
				traversal. */
		const CGLA::Vec3i dir_pre_mul;
 
		/** Discriminators. These values are delta[i]*dir[j] where delta[i]
				is the distance from the origin of the ray to the current position
				along the i axis multiplied by two). dir[j] is the direction vector
				coordinate j. */
	
		Integer64Bits disc[3][3];
 
		/** The current cell containing the ray. This value along with the 
				discriminators mentioned above represent the state of a ThreeDDDA. */
		CGLA::Vec3i cell;
 
 
		/** Return the position on the fine grid of a vector v. 
				We simply multiply by the precision and round down. Note that 
				it is necessary to use floor since simply clamping the value
				will always round toward zero.
		*/
		const CGLA::Vec3i grid_pos(const CGLA::Vec3f& v) const;
	
		/// Compute the cell containing a given fine grid position.
		CGLA::Vec3i get_cell(const CGLA::Vec3i& v) const;
	
		/// Mirror a fine grid position
		CGLA::Vec3i mirror(const CGLA::Vec3i& v) const;
 
 
	public:
 
		/** Create a 3DDDA based on the two end-points of the ray. An optional
				last argument indicates the resolution of the grid. */
		ThreeDDDA(const CGLA::Vec3f& p0, const CGLA::Vec3f& p1, 
							int _PRECISION = 0x100);
	
		/// Return the total number of steps the ray will traverse.
		int get_no_steps() const
		{
			return no_steps;
		}
 
		/// Yields the current cell containing the ray.
		const CGLA::Vec3i& get_current_cell() const
		{
			return cell;
		}
 
		/// Get the initial cell containing the ray.
		const CGLA::Vec3i& get_first_cell() const
		{
			return first_cell;
		}
 
		/// Get the last cell containing the ray.
		const CGLA::Vec3i& get_last_cell() const
		{
			return last_cell;
		}
 
		/// Get the initial point containing the ray.
		const CGLA::Vec3f get_first_point() const
		{
			return (CGLA::Vec3f(p0_int)+CGLA::Vec3f(0.5))/PRECISION;
		}
 
 
		/// Get the last cell containing the ray.
		const CGLA::Vec3f get_last_point() const
		{
			return (CGLA::Vec3f(p1_int)+CGLA::Vec3f(0.5))/PRECISION;
		}
	
		/// Returns true if we have reached the last cell.
		bool at_end() const
		{
			return cell == last_cell;
		}
 
		/// Take a step along the ray.
		void operator++()
		{
			int step_dir;
			if(disc[1][0] > disc[0][1])
				if(disc[2][0] > disc[0][2])
					step_dir = 0;
				else
					step_dir = 2;
			else
				if(disc[2][1] > disc[1][2])
					step_dir = 1;
				else
					step_dir = 2;
				
			const int k1 = (step_dir + 1) % 3;
			const int k2 = (step_dir + 2) % 3;
			cell[step_dir] += sgn[step_dir];
			disc[step_dir][k1] += dir_pre_mul[k1];
			disc[step_dir][k2] += dir_pre_mul[k2];
		}
 
		/// Get the initial point containing the ray.
			const CGLA::Vec3f step();
 
 
	};
}
 
#endif
 

Subversion Repositories gelsvn

(root)/trunk/src/Geometry/ThreeDDDA.h – Rev 299 → 304

Rev 299		Rev 304
1	`#ifndef __THREEDDDA_H`	1	`#ifndef __THREEDDDA_H`
2	`#define __THREEDDDA_H`	2	`#define __THREEDDDA_H`
3		3
-		4	`#ifdef _MSC_VER`
-		5	`typedef __int64 Integer64Bits;`
-		6	`#else`
-		7	`typedef int64_t Integer64Bits;`
-		8	`#endif`
-		9
-		10
4	`#include "CGLA/Vec3f.h"`	11	`#include "CGLA/Vec3f.h"`
5	`#include "CGLA/Vec3i.h"`	12	`#include "CGLA/Vec3i.h"`
6		13
7	`namespace Geometry`	14	`namespace Geometry`
8	`{`	15	`{`
9		16
10		17
11	`/** \brief A ThreeDDDA is a class for traversing a grid of cells.`	18	`/** \brief A ThreeDDDA is a class for traversing a grid of cells.`
12		19
13	`We wish to`	20	`We wish to`
14	`enumerate all cells pierced by the ray going from a point p0 to a`	21	`enumerate all cells pierced by the ray going from a point p0 to a`
15	`point p1. It is dangerous to use floating point arithmetic since rounding`	22	`point p1. It is dangerous to use floating point arithmetic since rounding`
16	`errors may accumulate entailing that the 3ddda misses the cell containing`	23	`errors may accumulate entailing that the 3ddda misses the cell containing`
17	`the end point of the ray.`	24	`the end point of the ray.`
18		25
19	`Daniel Cohen-Or devised a technique for exact ray traversal using only`	26	`Daniel Cohen-Or devised a technique for exact ray traversal using only`
20	`integer arithmetic. Using integer arithmetic, the computations are`	27	`integer arithmetic. Using integer arithmetic, the computations are`
21	`exact, but the ray must start and terminate exactly at grid points.`	28	`exact, but the ray must start and terminate exactly at grid points.`
22	`I.e. the ray must start and terminate in cell corners.`	29	`I.e. the ray must start and terminate in cell corners.`
23		30
24	`To overcome this issue, I have implemented a scheme where the ray`	31	`To overcome this issue, I have implemented a scheme where the ray`
25	`starts and terminates on a grid that is finer than the cell grid.`	32	`starts and terminates on a grid that is finer than the cell grid.`
26	`This means that we have fast and exact computations, and the ray can`	33	`This means that we have fast and exact computations, and the ray can`
27	`travel between two almost arbitrary points.`	34	`travel between two almost arbitrary points.`
28		35
29	`A central problem with this scheme was that - in order to simplify`	36	`A central problem with this scheme was that - in order to simplify`
30	`things during the iterative traversal - the ray direction vector`	37	`things during the iterative traversal - the ray direction vector`
31	`is always mirrored into the first octant (+x +y +z). If the fine`	38	`is always mirrored into the first octant (+x +y +z). If the fine`
32	`grid used for the ray start and end points is a superset of the`	39	`grid used for the ray start and end points is a superset of the`
33	`grid points of the cell grid, this mirroring is almost impossible`	40	`grid points of the cell grid, this mirroring is almost impossible`
34	`to implement correctly. This is due to the fact that the first`	41	`to implement correctly. This is due to the fact that the first`
35	`cell on the right side of the y axis is called 0,y whereas the`	42	`cell on the right side of the y axis is called 0,y whereas the`
36	`first cell on the left is called -1,y. This lack of symmetry makes`	43	`first cell on the left is called -1,y. This lack of symmetry makes`
37	`things very difficult, but by ensuring that the endpoints of a ray`	44	`things very difficult, but by ensuring that the endpoints of a ray`
38	`can never lie on an a corner, edge, or face of the cell grid, we`	45	`can never lie on an a corner, edge, or face of the cell grid, we`
39	`can make the problems go away.`	46	`can make the problems go away.`
40		47
41	`Hence, in this implementation, the fine grid is obtained by dividing`	48	`Hence, in this implementation, the fine grid is obtained by dividing`
42	`the cell into NxNxN subcells, but the grid points of the fine grid lie`	49	`the cell into NxNxN subcells, but the grid points of the fine grid lie`
43	`at the CENTRES of these subcells.`	50	`at the CENTRES of these subcells.`
44		51
45	`*/`	52	`*/`
46		53
47	`class ThreeDDDA`	54	`class ThreeDDDA`
48	`{`	55	`{`
49	`/** Resolution of the grid. This number indicates how many subcells`	56	`/** Resolution of the grid. This number indicates how many subcells`
50	`(along each axis) a cell is divided into. */`	57	`(along each axis) a cell is divided into. */`
51	`const int PRECISION;`	58	`const int PRECISION;`
52		59
53	`/// Sign indicates which octant contains the direction vector.`	60	`/// Sign indicates which octant contains the direction vector.`
54	`const CGLA::Vec3i sgn;`	61	`const CGLA::Vec3i sgn;`
55		62
56	`/// Fine grid position where the ray begins`	63	`/// Fine grid position where the ray begins`
57	`const CGLA::Vec3i p0_int;`	64	`const CGLA::Vec3i p0_int;`
58		65
59	`// Fine grid position where the ray ends.`	66	`// Fine grid position where the ray ends.`
60	`const CGLA::Vec3i p1_int;`	67	`const CGLA::Vec3i p1_int;`
61		68
62	`/// The direction of the ray`	69	`/// The direction of the ray`
63	`const CGLA::Vec3i dir;`	70	`const CGLA::Vec3i dir;`
64		71
65	`/// The cell containing the initial point on the ray.`	72	`/// The cell containing the initial point on the ray.`
66	`const CGLA::Vec3i first_cell;`	73	`const CGLA::Vec3i first_cell;`
67		74
68	`/// The cell containing the last point on the ray.`	75	`/// The cell containing the last point on the ray.`
69	`const CGLA::Vec3i last_cell;`	76	`const CGLA::Vec3i last_cell;`
70		77
71	`/** Number of steps. We can compute the number of steps that the`	78	`/** Number of steps. We can compute the number of steps that the`
72	`ray will take in advance. */`	79	`ray will take in advance. */`
73	`const int no_steps;`	80	`const int no_steps;`
74		81
75	`/** The direction vector, premultiplied by the step length.`	82	`/** The direction vector, premultiplied by the step length.`
76	`This constant is used to update the equations governing the`	83	`This constant is used to update the equations governing the`
77	`traversal. */`	84	`traversal. */`
78	`const CGLA::Vec3i dir_pre_mul;`	85	`const CGLA::Vec3i dir_pre_mul;`
79		86
80	`/** Discriminators. These values are delta[i]*dir[j] where delta[i]`	87	`/** Discriminators. These values are delta[i]*dir[j] where delta[i]`
81	`is the distance from the origin of the ray to the current position`	88	`is the distance from the origin of the ray to the current position`
82	`along the i axis multiplied by two). dir[j] is the direction vector`	89	`along the i axis multiplied by two). dir[j] is the direction vector`
83	`coordinate j. */`	90	`coordinate j. */`
84		91
85	`__int64 disc[3][3];`	92	`Integer64Bits disc[3][3];`
86		93
87	`/** The current cell containing the ray. This value along with the`	94	`/** The current cell containing the ray. This value along with the`
88	`discriminators mentioned above represent the state of a ThreeDDDA. */`	95	`discriminators mentioned above represent the state of a ThreeDDDA. */`
89	`CGLA::Vec3i cell;`	96	`CGLA::Vec3i cell;`
90		97
91		98
92	`/** Return the position on the fine grid of a vector v.`	99	`/** Return the position on the fine grid of a vector v.`
93	`We simply multiply by the precision and round down. Note that`	100	`We simply multiply by the precision and round down. Note that`
94	`it is necessary to use floor since simply clamping the value`	101	`it is necessary to use floor since simply clamping the value`
95	`will always round toward zero.`	102	`will always round toward zero.`
96	`*/`	103	`*/`
97	`const CGLA::Vec3i grid_pos(const CGLA::Vec3f& v) const;`	104	`const CGLA::Vec3i grid_pos(const CGLA::Vec3f& v) const;`
98		105
99	`/// Compute the cell containing a given fine grid position.`	106	`/// Compute the cell containing a given fine grid position.`
100	`CGLA::Vec3i get_cell(const CGLA::Vec3i& v) const;`	107	`CGLA::Vec3i get_cell(const CGLA::Vec3i& v) const;`
101		108
102	`/// Mirror a fine grid position`	109	`/// Mirror a fine grid position`
103	`CGLA::Vec3i mirror(const CGLA::Vec3i& v) const;`	110	`CGLA::Vec3i mirror(const CGLA::Vec3i& v) const;`
104		111
105		112
106	`public:`	113	`public:`
107		114
108	`/** Create a 3DDDA based on the two end-points of the ray. An optional`	115	`/** Create a 3DDDA based on the two end-points of the ray. An optional`
109	`last argument indicates the resolution of the grid. */`	116	`last argument indicates the resolution of the grid. */`
110	`ThreeDDDA(const CGLA::Vec3f& p0, const CGLA::Vec3f& p1,`	117	`ThreeDDDA(const CGLA::Vec3f& p0, const CGLA::Vec3f& p1,`
111	`int _PRECISION = 0x100);`	118	`int _PRECISION = 0x100);`
112		119
113	`/// Return the total number of steps the ray will traverse.`	120	`/// Return the total number of steps the ray will traverse.`
114	`int get_no_steps() const`	121	`int get_no_steps() const`
115	`{`	122	`{`
116	`return no_steps;`	123	`return no_steps;`
117	`}`	124	`}`
118		125
119	`/// Yields the current cell containing the ray.`	126	`/// Yields the current cell containing the ray.`
120	`const CGLA::Vec3i& get_current_cell() const`	127	`const CGLA::Vec3i& get_current_cell() const`
121	`{`	128	`{`
122	`return cell;`	129	`return cell;`
123	`}`	130	`}`
124		131
125	`/// Get the initial cell containing the ray.`	132	`/// Get the initial cell containing the ray.`
126	`const CGLA::Vec3i& get_first_cell() const`	133	`const CGLA::Vec3i& get_first_cell() const`
127	`{`	134	`{`
128	`return first_cell;`	135	`return first_cell;`
129	`}`	136	`}`
130		137
131	`/// Get the last cell containing the ray.`	138	`/// Get the last cell containing the ray.`
132	`const CGLA::Vec3i& get_last_cell() const`	139	`const CGLA::Vec3i& get_last_cell() const`
133	`{`	140	`{`
134	`return last_cell;`	141	`return last_cell;`
135	`}`	142	`}`
136		143
137	`/// Get the initial point containing the ray.`	144	`/// Get the initial point containing the ray.`
138	`const CGLA::Vec3f get_first_point() const`	145	`const CGLA::Vec3f get_first_point() const`
139	`{`	146	`{`
140	`return (CGLA::Vec3f(p0_int)+CGLA::Vec3f(0.5))/PRECISION;`	147	`return (CGLA::Vec3f(p0_int)+CGLA::Vec3f(0.5))/PRECISION;`
141	`}`	148	`}`
142		149
143		150
144	`/// Get the last cell containing the ray.`	151	`/// Get the last cell containing the ray.`
145	`const CGLA::Vec3f get_last_point() const`	152	`const CGLA::Vec3f get_last_point() const`
146	`{`	153	`{`
147	`return (CGLA::Vec3f(p1_int)+CGLA::Vec3f(0.5))/PRECISION;`	154	`return (CGLA::Vec3f(p1_int)+CGLA::Vec3f(0.5))/PRECISION;`
148	`}`	155	`}`
149		156
150	`/// Returns true if we have reached the last cell.`	157	`/// Returns true if we have reached the last cell.`
151	`bool at_end() const`	158	`bool at_end() const`
152	`{`	159	`{`
153	`return cell == last_cell;`	160	`return cell == last_cell;`
154	`}`	161	`}`
155		162
156	`/// Take a step along the ray.`	163	`/// Take a step along the ray.`
157	`void operator++()`	164	`void operator++()`
158	`{`	165	`{`
159	`int step_dir;`	166	`int step_dir;`
160	`if(disc[1][0] > disc[0][1])`	167	`if(disc[1][0] > disc[0][1])`
161	`if(disc[2][0] > disc[0][2])`	168	`if(disc[2][0] > disc[0][2])`
162	`step_dir = 0;`	169	`step_dir = 0;`
163	`else`	170	`else`
164	`step_dir = 2;`	171	`step_dir = 2;`
165	`else`	172	`else`
166	`if(disc[2][1] > disc[1][2])`	173	`if(disc[2][1] > disc[1][2])`
167	`step_dir = 1;`	174	`step_dir = 1;`
168	`else`	175	`else`
169	`step_dir = 2;`	176	`step_dir = 2;`
170		177
171	`const int k1 = (step_dir + 1) % 3;`	178	`const int k1 = (step_dir + 1) % 3;`
172	`const int k2 = (step_dir + 2) % 3;`	179	`const int k2 = (step_dir + 2) % 3;`
173	`cell[step_dir] += sgn[step_dir];`	180	`cell[step_dir] += sgn[step_dir];`
174	`disc[step_dir][k1] += dir_pre_mul[k1];`	181	`disc[step_dir][k1] += dir_pre_mul[k1];`
175	`disc[step_dir][k2] += dir_pre_mul[k2];`	182	`disc[step_dir][k2] += dir_pre_mul[k2];`
176	`}`	183	`}`
177		184
178	`/// Get the initial point containing the ray.`	185	`/// Get the initial point containing the ray.`
179	`const CGLA::Vec3f step();`	186	`const CGLA::Vec3f step();`
180		187
181		188
182	`};`	189	`};`
183	`}`	190	`}`
184		191
185	`#endif`	192	`#endif`
186		193