Voxel
 All Classes Namespaces Files Functions Typedefs Enumerations Enumerator Macros Pages
renderer_detail_trace.h
1 #pragma once
2 
3 #ifndef RENDERER_DETAIL_TRACE_H
4 #define RENDERER_DETAIL_TRACE_H
5 
6 
7 
8 
9 #include "synchronized.h"
10 #include "octree.h"
11 #include "vector.h"
12 #include "helpers.h"
13 #include "settings.h"
14 
15 #include <boost/math/special_functions.hpp> // MSVC does not yet support std::isfinite
16 
17 #include <algorithm>
18 #include <limits>
19 #include <cmath>
20 
21 #include <assert.h>
22 #include <stdint.h>
23 
24 
25 
26 
27 namespace Renderer {
28 
29 
30 namespace detail {
31 
32 
33 
34 
35 /*==============================================================================
36  Function declarations
37 ==============================================================================*/
38 
39 
40 double Project( Vector< double, 3 >& position, Vector< double, 3 > const& ray );
41 
42 
43 
44 
45 /*==============================================================================
46  TraceTexture function
47 ==============================================================================*/
48 
49 
50 template< int t_ColorFormat, int t_Platform >
51 int TraceTexture(
52  uint8_t* const colorDestination,
53  float* const depthDestination,
54  typename Synchronized::TextureHeap< t_ColorFormat, t_Platform >::Pointer const& texture,
55  double lambda,
56  Vector< double, 3 > remaining,
57  Vector< double, 3 > remainingMaximum,
58  unsigned int const origin
59 )
60 {
61  static unsigned int const maskTable[] = { 0, 3, 12, 15, 48, 51, 60, 63 }; // abc -> aabbcc (binary)
62 
63  unsigned int const mask = maskTable[ origin ];
64  unsigned int index = 0;
65 
66  remainingMaximum /= 2;
67  if ( remaining[ 0 ] >= remainingMaximum[ 0 ] ) {
68 
69  index += 2;
70  remaining[ 0 ] -= remainingMaximum[ 0 ];
71  }
72  if ( remaining[ 1 ] >= remainingMaximum[ 1 ] ) {
73 
74  index += 8;
75  remaining[ 1 ] -= remainingMaximum[ 1 ];
76  }
77  if ( remaining[ 2 ] >= remainingMaximum[ 2 ] ) {
78 
79  index += 32;
80  remaining[ 2 ] -= remainingMaximum[ 2 ];
81  }
82 
83  remainingMaximum /= 2;
84  if ( remaining[ 0 ] >= remainingMaximum[ 0 ] ) {
85 
86  index += 1;
87  remaining[ 0 ] -= remainingMaximum[ 0 ];
88  }
89  if ( remaining[ 1 ] >= remainingMaximum[ 1 ] ) {
90 
91  index += 4;
92  remaining[ 1 ] -= remainingMaximum[ 1 ];
93  }
94  if ( remaining[ 2 ] >= remainingMaximum[ 2 ] ) {
95 
96  index += 16;
97  remaining[ 2 ] -= remainingMaximum[ 2 ];
98  }
99 
100  int comparisons = -1;
101  while ( comparisons < 0 ) {
102 
103  assert( ( index ^ mask ) < 64 );
104  Color< t_ColorFormat > const& color = texture[ index ^ mask ];
105  if ( color.Packed() != 0 ) { // **NOTE: black is transparent
106 
107  // **NOTE: BGRA
108  colorDestination[ 0 ] = color.Blue();
109  colorDestination[ 1 ] = color.Green();
110  colorDestination[ 2 ] = color.Red();
111  colorDestination[ 3 ] = 0xff;
112 
113  *depthDestination = lambda;
114 
115  comparisons = -1;
116  break; // **NOTE: break
117  }
118 
119  comparisons = (
120  ( ( remaining[ 0 ] < remaining[ 1 ] ) ? 1 : 0 ) |
121  ( ( remaining[ 1 ] < remaining[ 2 ] ) ? 2 : 0 ) |
122  ( ( remaining[ 2 ] < remaining[ 0 ] ) ? 4 : 0 )
123  );
124  switch( comparisons ) {
125 
126  case 0: case 7: // any are fine--fall through
127  case 1: case 3: {
128 
129  if ( ( index & 3 ) != 0 ) {
130 
131  --index;
132 
133  lambda += remaining[ 0 ];
134  remaining[ 1 ] -= remaining[ 0 ];
135  remaining[ 2 ] -= remaining[ 0 ];
136  remaining[ 0 ] = remainingMaximum[ 0 ];
137 
138  comparisons = -1;
139  }
140 
141  break;
142  }
143 
144  case 2: case 6: {
145 
146  if ( ( index & 12 ) != 0 ) {
147 
148  index -= 4;
149 
150  lambda += remaining[ 1 ];
151  remaining[ 0 ] -= remaining[ 1 ];
152  remaining[ 2 ] -= remaining[ 1 ];
153  remaining[ 1 ] = remainingMaximum[ 1 ];
154 
155  comparisons = -1;
156  }
157 
158  break;
159  }
160 
161  case 4: case 5: {
162 
163  if ( ( index & 48 ) != 0 ) {
164 
165  index -= 16;
166 
167  lambda += remaining[ 2 ];
168  remaining[ 0 ] -= remaining[ 2 ];
169  remaining[ 1 ] -= remaining[ 2 ];
170  remaining[ 2 ] = remainingMaximum[ 2 ];
171 
172  comparisons = -1;
173  }
174 
175  break;
176  }
177  }
178  }
179 
180  return comparisons;
181 }
182 
183 
184 
185 
186 /*==============================================================================
187  Trace function
188 ==============================================================================*/
189 
190 
191 template< int t_ColorFormat, int t_Platform >
192 void Trace(
193  uint8_t* const colorDestination,
194  float* const depthDestination,
195  typename Synchronized::Heap< t_Platform >::template Pointer< Octree::Node< t_ColorFormat, t_Platform > > const& pRoot,
196  double const spread,
197  Vector< double, 3 > const& position,
198  Vector< double, 3 > const& ray
199 )
200 {
201  double const epsilon = std::numeric_limits< double >::epsilon();
202 
203  Vector< double, 3 > projected = position;
204  double lambda = Project( projected, ray );
205  if ( ! boost::math::isfinite( lambda ) )
206  return; // **NOTE: return
207 
208  unsigned int origin = 7;
209  Vector< double, 3 > remaining = 1 - projected;
210  Vector< double, 3 > delta = ray;
211  if ( delta[ 0 ] < 0 ) {
212 
213  origin ^= 1;
214  remaining[ 0 ] = projected[ 0 ];
215  delta[ 0 ] = -delta[ 0 ];
216  }
217  if ( delta[ 1 ] < 0 ) {
218 
219  origin ^= 2;
220  remaining[ 1 ] = projected[ 1 ];
221  delta[ 1 ] = -delta[ 1 ];
222  }
223  if ( delta[ 2 ] < 0 ) {
224 
225  origin ^= 4;
226  remaining[ 2 ] = projected[ 2 ];
227  delta[ 2 ] = -delta[ 2 ];
228  }
229 
230  // deltas must be strictly positive
231  delta = std::max( delta, epsilon );
232 
233 #if ( SETTING_MIPMAP != 0 )
234  Vector< double, 3 > distance = std::abs( position - projected ) - ( 1 - remaining );
235 
236  double sideLength = 1;
237  double distanceThresholds[ SETTING_TRACE_STACK_SIZE ];
238  distanceThresholds[ 0 ] = 0.125 / spread; // 0.5 because we want to compare to the size at the *next* depth, and 0.25 because we draw 4x4x4 textures
239  for ( unsigned int ii = 1; ii < ARRAYLENGTH( distanceThresholds ); ++ii )
240  distanceThresholds[ ii ] = distanceThresholds[ ii - 1 ] / 2;
241 #endif // SETTING_MIPMAP
242 
243  Vector< double, 3 > remainingMaximum = 1 / delta;
244  remaining *= remainingMaximum;
245 
246  Octree::Node< t_ColorFormat, t_Platform > const* childrenStack[ SETTING_TRACE_STACK_SIZE ];
247  unsigned int indexStack[ SETTING_TRACE_STACK_SIZE ];
248  unsigned int depth = 0;
249 
250  Octree::Node< t_ColorFormat, t_Platform > const* children = pRoot.get();
251  unsigned int index = 0;
252  do {
253 
254  // ==== descend until we reach a leaf node or the maximum mipmap level ====
255 
256  while ( children[ index ].children ) {
257 
258 #if ( SETTING_MIPMAP != 0 )
259  if ( ( distance[ 0 ] > distanceThresholds[ depth ] ) || ( distance[ 1 ] > distanceThresholds[ depth ] ) || ( distance[ 2 ] > distanceThresholds[ depth ] ) )
260  break;
261 #endif // SETTING_MIPMAP
262 
263  assert( depth < ARRAYLENGTH( childrenStack ) );
264  assert( depth < ARRAYLENGTH( indexStack ) );
265  childrenStack[ depth ] = children;
266  indexStack[ depth ] = index;
267  ++depth;
268 
269  children = children[ index ].children.get();
270  index = origin;
271 
272 #if ( SETTING_MIPMAP != 0 )
273  sideLength /= 2;
274 #endif // SETTING_MIPMAP
275  remainingMaximum /= 2;
276 
277  if ( remaining[ 0 ] >= remainingMaximum[ 0 ] ) {
278 
279  remaining[ 0 ] -= remainingMaximum[ 0 ];
280  index ^= 1;
281  }
282 #if ( SETTING_MIPMAP != 0 )
283  else
284  distance[ 0 ] += sideLength;
285 #endif // SETTING_MIPMAP
286 
287  if ( remaining[ 1 ] >= remainingMaximum[ 1 ] ) {
288 
289  remaining[ 1 ] -= remainingMaximum[ 1 ];
290  index ^= 2;
291  }
292 #if ( SETTING_MIPMAP != 0 )
293  else
294  distance[ 1 ] += sideLength;
295 #endif // SETTING_MIPMAP
296 
297  if ( remaining[ 2 ] >= remainingMaximum[ 2 ] ) {
298 
299  remaining[ 2 ] -= remainingMaximum[ 2 ];
300  index ^= 4;
301  }
302 #if ( SETTING_MIPMAP != 0 )
303  else
304  distance[ 2 ] += sideLength;
305 #endif // SETTING_MIPMAP
306 
307  assert( index < 8 );
308  }
309 
310  // ==== try to draw the 4x4x4 texture stored at this node, if any ====
311 
312  int comparisons = -1;
313  if ( children[ index ].texture ) {
314 
315  comparisons = TraceTexture< t_ColorFormat, t_Platform >(
316  colorDestination,
317  depthDestination,
318  children[ index ].texture,
319  lambda,
320  remaining,
321  remainingMaximum,
322  origin
323  );
324 
325  if ( comparisons < 0 )
326  break; // **NOTE: break
327  }
328  else {
329 
330  comparisons = (
331  ( ( remaining[ 0 ] < remaining[ 1 ] ) ? 1 : 0 ) |
332  ( ( remaining[ 1 ] < remaining[ 2 ] ) ? 2 : 0 ) |
333  ( ( remaining[ 2 ] < remaining[ 0 ] ) ? 4 : 0 )
334  );
335  }
336 
337  // ==== step to the next adjacent voxel, ascending as necessary ====
338 
339  switch( comparisons ) {
340 
341  case 0: case 7: // any are fine--fall through
342  case 1: case 3: {
343 
344 #if ( SETTING_MIPMAP != 0 )
345  distance[ 0 ] += sideLength;
346 #endif // SETTING_MIPMAP
347 
348  lambda += remaining[ 0 ];
349  remaining[ 1 ] -= remaining[ 0 ];
350  remaining[ 2 ] -= remaining[ 0 ];
351 
352  do {
353 
354  unsigned int const indexOrigin = ( index ^ origin );
355  if ( indexOrigin & 1 ) {
356 
357  index ^= 1;
358  break;
359  }
360  else {
361 
362  if ( indexOrigin & 2 )
363  remaining[ 1 ] += remainingMaximum[ 1 ];
364 #if ( SETTING_MIPMAP != 0 )
365  else
366  distance[ 1 ] -= sideLength;
367 #endif // SETTING_MIPMAP
368 
369  if ( indexOrigin & 4 )
370  remaining[ 2 ] += remainingMaximum[ 2 ];
371 #if ( SETTING_MIPMAP != 0 )
372  else
373  distance[ 2 ] -= sideLength;
374 #endif // SETTING_MIPMAP
375 
376 #if ( SETTING_MIPMAP != 0 )
377  sideLength *= 2;
378 #endif // SETTING_MIPMAP
379  remainingMaximum *= 2;
380 
381  assert( depth > 0 );
382  --depth;
383  children = childrenStack[ depth ];
384  index = indexStack[ depth ];
385  }
386 
387  } while ( depth > 0 );
388 
389  remaining[ 0 ] = remainingMaximum[ 0 ];
390 
391  break;
392  }
393 
394  case 2: case 6: {
395 
396 #if ( SETTING_MIPMAP != 0 )
397  distance[ 1 ] += sideLength;
398 #endif // SETTING_MIPMAP
399 
400  lambda += remaining[ 1 ];
401  remaining[ 0 ] -= remaining[ 1 ];
402  remaining[ 2 ] -= remaining[ 1 ];
403 
404  do {
405 
406  unsigned int const indexOrigin = ( index ^ origin );
407  if ( indexOrigin & 2 ) {
408 
409  index ^= 2;
410  break;
411  }
412  else {
413 
414  if ( indexOrigin & 1 )
415  remaining[ 0 ] += remainingMaximum[ 0 ];
416 #if ( SETTING_MIPMAP != 0 )
417  else
418  distance[ 0 ] -= sideLength;
419 #endif // SETTING_MIPMAP
420 
421  if ( indexOrigin & 4 )
422  remaining[ 2 ] += remainingMaximum[ 2 ];
423 #if ( SETTING_MIPMAP != 0 )
424  else
425  distance[ 2 ] -= sideLength;
426 #endif // SETTING_MIPMAP
427 
428 #if ( SETTING_MIPMAP != 0 )
429  sideLength *= 2;
430 #endif // SETTING_MIPMAP
431  remainingMaximum *= 2;
432 
433  assert( depth > 0 );
434  --depth;
435  children = childrenStack[ depth ];
436  index = indexStack[ depth ];
437  }
438 
439  } while ( depth > 0 );
440 
441  remaining[ 1 ] = remainingMaximum[ 1 ];
442 
443  break;
444  }
445 
446  case 4: case 5: {
447 
448 #if ( SETTING_MIPMAP != 0 )
449  distance[ 2 ] += sideLength;
450 #endif // SETTING_MIPMAP
451 
452  lambda += remaining[ 2 ];
453  remaining[ 0 ] -= remaining[ 2 ];
454  remaining[ 1 ] -= remaining[ 2 ];
455 
456  do {
457 
458  unsigned int const indexOrigin = ( index ^ origin );
459  if ( indexOrigin & 4 ) {
460 
461  index ^= 4 ;
462  break;
463  }
464  else {
465 
466  if ( indexOrigin & 1 )
467  remaining[ 0 ] += remainingMaximum[ 0 ];
468 #if ( SETTING_MIPMAP != 0 )
469  else
470  distance[ 0 ] -= sideLength;
471 #endif // SETTING_MIPMAP
472 
473  if ( indexOrigin & 2 )
474  remaining[ 1 ] += remainingMaximum[ 1 ];
475 #if ( SETTING_MIPMAP != 0 )
476  else
477  distance[ 1 ] -= sideLength;
478 #endif // SETTING_MIPMAP
479 
480 #if ( SETTING_MIPMAP != 0 )
481  sideLength *= 2;
482 #endif // SETTING_MIPMAP
483  remainingMaximum *= 2;
484 
485  assert( depth > 0 );
486  --depth;
487  children = childrenStack[ depth ];
488  index = indexStack[ depth ];
489  }
490 
491  } while ( depth > 0 );
492 
493  remaining[ 2 ] = remainingMaximum[ 2 ];
494 
495  break;
496  }
497  }
498 
499  } while ( depth > 0 );
500 }
501 
502 
503 
504 
505 } // namespace detail
506 
507 
508 } // namespace Renderer
509 
510 
511 
512 
513 #endif // RENDERER_DETAIL_TRACE_H
Generated on Thu Jun 20 2013 11:05:27 for Voxel by   doxygen 1.8.1.2