Voxel
 All Classes Namespaces Files Functions Typedefs Enumerations Enumerator Macros Pages
octree_create.h
1 #pragma once
2 
3 #ifndef OCTREE_CREATE_H
4 #define OCTREE_CREATE_H
5 
6 
7 
8 
9 #include "synchronized.h"
10 #include "octree_node.h"
11 #include "shape.h"
12 
13 #include <array>
14 #include <algorithm>
15 
16 #include <assert.h>
17 
18 
19 
20 
21 namespace Octree {
22 
23 
24 
25 
26 namespace {
27 
28 
29 
30 
31 /*==============================================================================
32  CreateNode function
33 ==============================================================================*/
34 
35 
36 template< int t_ColorFormat, int t_Platform >
37 Node< t_ColorFormat, t_Platform > CreateNode(
38  Synchronized::Heap< t_Platform >& heap,
39  Synchronized::TextureHeap< t_ColorFormat, t_Platform >& textureHeap,
40  unsigned int const depthRemaining,
41  Vector< double, 3 > const& position,
42  double side,
43  Shape< unsigned int > const shape
44 )
45 {
46  Node< t_ColorFormat, t_Platform > result;
47 
48  Vector< double, 3 > const center = position + ( side / 2 );
49  bool const split = shape.Split( position, side );
50  bool const inside = ( shape.Inside( 0, center ) != 0 );
51 
52  if ( ( depthRemaining > 0 ) && split ) {
53 
54  result.children = heap.template Allocate< Node< t_ColorFormat, t_Platform > >( 8 );
55 
56  double const sideChild = side / 2;
57  Vector< double, 3 > positionChild;
58 
59  unsigned int index = 0;
60  positionChild[ 2 ] = position[ 2 ];
61  for ( unsigned int ii = 0; ii < 2; ++ii ) {
62 
63  positionChild[ 1 ] = position[ 1 ];
64  for ( unsigned int jj = 0; jj < 2; ++jj ) {
65 
66  positionChild[ 0 ] = position[ 0 ];
67  for ( unsigned int kk = 0; kk < 2; ++kk ) {
68 
69  result.children.Assign( index, CreateNode( heap, textureHeap, depthRemaining - 1, positionChild, sideChild, shape ) );
70 
71  positionChild[ 0 ] += sideChild;
72  ++index;
73  }
74  positionChild[ 1 ] += sideChild;
75  }
76  positionChild[ 2 ] += sideChild;
77  }
78  }
79 
80  if ( split || inside ) {
81 
82  result.texture = textureHeap.Allocate( 2 );
83 
84  double const textureSide = ( side / 4 );
85  Vector< double, 3 > texturePosition;
86 
87  unsigned int index = 0;
88  texturePosition[ 2 ] = position[ 2 ] + ( textureSide / 2 );
89  for ( unsigned int ii = 0; ii < 4; ++ii ) {
90 
91  texturePosition[ 1 ] = position[ 1 ] + ( textureSide / 2 );
92  for ( unsigned int jj = 0; jj < 4; ++jj ) {
93 
94  texturePosition[ 0 ] = position[ 0 ] + ( textureSide / 2 );
95  for ( unsigned int kk = 0; kk < 4; ++kk ) {
96 
97  std::array< uint8_t, 3 > color;
98  switch( shape.Inside( 0, texturePosition ) ) {
99 
100  case 1: {
101 
102  color[ 0 ] = ( ( texturePosition[ 0 ] > 0 ) ? 0x00 : 0x80 );
103  color[ 1 ] = ( ( texturePosition[ 1 ] > 0 ) ? 0x00 : 0x80 );
104  color[ 2 ] = ( ( texturePosition[ 2 ] > 0 ) ? 0x00 : 0x80 );
105 
106  uint8_t const xxIndex = static_cast< uint8_t >( ( texturePosition[ 0 ] + 1 ) * 512 + 0.5 );
107  uint8_t const yyIndex = static_cast< uint8_t >( ( texturePosition[ 1 ] + 1 ) * 512 + 0.5 );
108  uint8_t const zzIndex = static_cast< uint8_t >( ( texturePosition[ 2 ] + 1 ) * 512 + 0.5 );
109 
110  color[ 0 ] += ( ( yyIndex ^ zzIndex ) & 0x7f );
111  color[ 1 ] += ( ( xxIndex ^ zzIndex ) & 0x7f );
112  color[ 2 ] += ( ( xxIndex ^ yyIndex ) & 0x7f );
113 
114  break;
115  }
116 
117  case 2: {
118 
119  color[ 0 ] = static_cast< uint8_t >( std::max( 0.0, std::min( 1.0, ( texturePosition[ 0 ] + 0.1 ) / 0.2 ) ) * 0xef + 0x10 );
120  color[ 1 ] = static_cast< uint8_t >( std::max( 0.0, std::min( 1.0, ( texturePosition[ 1 ] + 0.1 ) / 0.2 ) ) * 0xff + 0x00 );
121  color[ 2 ] = static_cast< uint8_t >( std::max( 0.0, std::min( 1.0, ( texturePosition[ 2 ] + 0.1 ) / 0.2 ) ) * 0xef + 0x10 );
122 
123  break;
124  }
125 
126  case 3: {
127 
128  color[ 0 ] = 0xc0;
129  color[ 1 ] = 0xc0;
130  color[ 2 ] = 0xc0;
131 
132  // shuffle the colors a bit so that we can distinguish between adjacent voxels
133  color[ 0 ] ^= ( ( ii & 1 ) << 4 );
134  color[ 1 ] ^= ( ( jj & 1 ) << 3 );
135  color[ 2 ] ^= ( ( kk & 1 ) << 4 );
136 
137  break;
138  }
139 
140  case 4: {
141 
142  color[ 0 ] = ( ( texturePosition[ 0 ] > 0 ) ? 0xc0 : 0x20 );
143  color[ 1 ] = ( ( texturePosition[ 1 ] > 0 ) ? 0xc0 : 0x20 );
144  color[ 2 ] = ( ( texturePosition[ 2 ] > 0 ) ? 0xc0 : 0x20 );
145 
146  // shuffle the colors a bit so that we can distinguish between adjacent voxels
147  color[ 0 ] ^= ( ( ii & 1 ) << 5 );
148  color[ 1 ] ^= ( ( jj & 1 ) << 4 );
149  color[ 2 ] ^= ( ( kk & 1 ) << 5 );
150 
151  break;
152  }
153 
154  default: {
155 
156  color[ 0 ] = 0x00;
157  color[ 1 ] = 0x00;
158  color[ 2 ] = 0x00;
159 
160  break;
161  }
162  }
163 
164  assert( index < 64 );
165  result.texture.Assign( index, Color< t_ColorFormat >( color[ 0 ], color[ 1 ], color[ 2 ] ) );
166 
167  ++index;
168  texturePosition[ 0 ] += textureSide;
169  }
170 
171  texturePosition[ 1 ] += textureSide;
172  }
173 
174  texturePosition[ 2 ] += textureSide;
175  }
176  }
177 
178  return result;
179 }
180 
181 
182 
183 
184 /*==============================================================================
185  SubtractNode function
186 ==============================================================================*/
187 
188 
189 template< int t_ColorFormat, int t_Platform >
190 Node< t_ColorFormat, t_Platform > SubtractNode(
191  Synchronized::Heap< t_Platform >& heap,
192  Synchronized::TextureHeap< t_ColorFormat, t_Platform >& textureHeap,
193  Node< t_ColorFormat, t_Platform > const& originalNode,
194  unsigned int const depthRemaining,
195  Vector< double, 3 > const& position,
196  double side,
197  Shape< unsigned int > const shape
198 )
199 {
200  Node< t_ColorFormat, t_Platform > result;
201 
202  Vector< double, 3 > const center = position + ( side / 2 );
203  bool const split = shape.Split( position, side );
204  bool const inside = ( shape.Inside( 0, center ) != 0 );
205 
206  if ( ( depthRemaining > 0 ) && split ) {
207 
208  if ( originalNode.children ) {
209 
210  result.children = heap.template Allocate< Node< t_ColorFormat, t_Platform > >( 8 );
211 
212  double const sideChild = side / 2;
213  Vector< double, 3 > positionChild;
214 
215  unsigned int index = 0;
216  positionChild[ 2 ] = position[ 2 ];
217  for ( unsigned int ii = 0; ii < 2; ++ii ) {
218 
219  positionChild[ 1 ] = position[ 1 ];
220  for ( unsigned int jj = 0; jj < 2; ++jj ) {
221 
222  positionChild[ 0 ] = position[ 0 ];
223  for ( unsigned int kk = 0; kk < 2; ++kk ) {
224 
225  result.children.Assign( index, SubtractNode( heap, textureHeap, originalNode.children[ index ], depthRemaining - 1, positionChild, sideChild, shape ) );
226 
227  positionChild[ 0 ] += sideChild;
228  ++index;
229  }
230  positionChild[ 1 ] += sideChild;
231  }
232  positionChild[ 2 ] += sideChild;
233  }
234  }
235  // **TODO: if texture and no children, we should continue splitting, generating new data
236  }
237  else if ( ! inside )
238  result.children = originalNode.children;
239 
240  if ( originalNode.texture ) {
241 
242  if ( split ) {
243 
244  result.texture = textureHeap.Allocate( 2 );
245 
246  double const textureSide = ( side / 4 );
247  Vector< double, 3 > texturePosition;
248 
249  unsigned int index = 0;
250  texturePosition[ 2 ] = position[ 2 ] + ( textureSide / 2 );
251  for ( unsigned int ii = 0; ii < 4; ++ii ) {
252 
253  texturePosition[ 1 ] = position[ 1 ] + ( textureSide / 2 );
254  for ( unsigned int jj = 0; jj < 4; ++jj ) {
255 
256  texturePosition[ 0 ] = position[ 0 ] + ( textureSide / 2 );
257  for ( unsigned int kk = 0; kk < 4; ++kk ) {
258 
259  if ( ! shape.Inside( 0, texturePosition ) ) {
260 
261  assert( index < 64 );
262  result.texture.Assign( index, originalNode.texture[ index ] );
263  }
264 
265  ++index;
266  texturePosition[ 0 ] += textureSide;
267  }
268 
269  texturePosition[ 1 ] += textureSide;
270  }
271 
272  texturePosition[ 2 ] += textureSide;
273  }
274  }
275  else if ( ! inside )
276  result.texture = originalNode.texture;
277  }
278 
279  return result;
280 }
281 
282 
283 
284 
285 } // anonymous namespace
286 
287 
288 
289 
290 /*==============================================================================
291  Create function
292 ==============================================================================*/
293 
294 
295 template< int t_ColorFormat, int t_Platform >
296 typename Synchronized::Heap< t_Platform >::template Pointer< Node< t_ColorFormat, t_Platform > > const Create(
297  Synchronized::Heap< t_Platform >& heap,
298  Synchronized::TextureHeap< t_ColorFormat, t_Platform >& textureHeap,
299  unsigned int const logResolution = 7
300 )
301 {
302  Shape< unsigned int > shape;
303  // central shape
304  { Vector< double, 3 > center = { { 0.0, 0.0, 0.0 } }; shape.PushBall( 1, center, 1.0, 0.6 ); }
305  { Vector< double, 3 > center = { { 0.0, 0.0, 0.0 } }; shape.PushBall( 0, center, 0.9, 0.6 ); }
306  { Vector< double, 3 > center = { { 0.0, 0.0, 0.0 } }; shape.PushBall( 2, center, 0.1, 2.0 ); }
307  // small balls on the corners
308  { Vector< double, 3 > center = { { 0.00, 0.00, 0.97 } }; shape.PushBall( 3, center, 0.03, 2.0 ); }
309  { Vector< double, 3 > center = { { 0.00, 0.00, -0.97 } }; shape.PushBall( 3, center, 0.03, 2.0 ); }
310  { Vector< double, 3 > center = { { 0.00, 0.97, 0.00 } }; shape.PushBall( 3, center, 0.03, 2.0 ); }
311  { Vector< double, 3 > center = { { 0.00, -0.97, 0.00 } }; shape.PushBall( 3, center, 0.03, 2.0 ); }
312  { Vector< double, 3 > center = { { 0.97, 0.00, 0.00 } }; shape.PushBall( 3, center, 0.03, 2.0 ); }
313  { Vector< double, 3 > center = { { -0.97, 0.00, 0.00 } }; shape.PushBall( 3, center, 0.03, 2.0 ); }
314  // squarish balls on the sides
315  { Vector< double, 3 > center = { { 0.3, 0.3, 0.3 } }; shape.PushBall( 4, center, 0.1, 4.0 ); }
316  { Vector< double, 3 > center = { { 0.3, 0.3, -0.3 } }; shape.PushBall( 4, center, 0.1, 4.0 ); }
317  { Vector< double, 3 > center = { { 0.3, -0.3, 0.3 } }; shape.PushBall( 4, center, 0.1, 4.0 ); }
318  { Vector< double, 3 > center = { { 0.3, -0.3, -0.3 } }; shape.PushBall( 4, center, 0.1, 4.0 ); }
319  { Vector< double, 3 > center = { { -0.3, 0.3, 0.3 } }; shape.PushBall( 4, center, 0.1, 4.0 ); }
320  { Vector< double, 3 > center = { { -0.3, 0.3, -0.3 } }; shape.PushBall( 4, center, 0.1, 4.0 ); }
321  { Vector< double, 3 > center = { { -0.3, -0.3, 0.3 } }; shape.PushBall( 4, center, 0.1, 4.0 ); }
322  { Vector< double, 3 > center = { { -0.3, -0.3, -0.3 } }; shape.PushBall( 4, center, 0.1, 4.0 ); }
323 
324  assert( logResolution > 0 );
325 
326  // populate the tree
327  Vector< double, 3 > const position = { { -1, -1, -1 } };
328  typename Synchronized::Heap< t_Platform >::template Pointer< Node< t_ColorFormat, t_Platform > > pRoot = heap.template Allocate< Node< t_ColorFormat, t_Platform > >();
329  pRoot.Assign( CreateNode( heap, textureHeap, logResolution, position, 2, shape ) );
330 
331  return pRoot;
332 }
333 
334 
335 
336 
337 /*==============================================================================
338  Subtract function
339 ==============================================================================*/
340 
341 
342 template< int t_ColorFormat, int t_Platform >
343 typename Synchronized::Heap< t_Platform >::template Pointer< Node< t_ColorFormat, t_Platform > > const Subtract(
344  Synchronized::Heap< t_Platform >& heap,
345  Synchronized::TextureHeap< t_ColorFormat, t_Platform >& textureHeap,
346  typename Synchronized::Heap< t_Platform >::template Pointer< Node< t_ColorFormat, t_Platform > > const& pOriginalRoot,
347  Vector< double, 3 > const& center,
348  double const radius,
349  double const power,
350  unsigned int const logResolution = 7
351 )
352 {
353  Vector< double, 3 > const scaledCenter = center * 2 - 1;
354  Shape< unsigned int > shape;
355  shape.PushBall( 1, scaledCenter, radius, power );
356 
357  // populate the tree
358  Vector< double, 3 > const position = { { -1, -1, -1 } };
359  typename Synchronized::Heap< t_Platform >::template Pointer< Node< t_ColorFormat, t_Platform > > pRoot = heap.template Allocate< Node< t_ColorFormat, t_Platform > >();
360  pRoot.Assign( SubtractNode( heap, textureHeap, *pOriginalRoot, logResolution, position, 2, shape ) );
361 
362  return pRoot;
363 }
364 
365 
366 
367 
368 } // namespace Octree
369 
370 
371 
372 
373 #endif // OCTREE_CREATE_H
Generated on Thu Jun 20 2013 11:05:27 for Voxel by   doxygen 1.8.1.2