YafaRay Core  v3.2.0-ALPHA-10-g60452c5
ray_kdtree.cc
Go to the documentation of this file.
1 // search for "todo" and "IMPLEMENT" and "<<" or ">>"...
2 
4 #include <core_api/material.h>
5 #include <core_api/scene.h>
6 #include <stdexcept>
7 //#include <math.h>
8 #include <limits>
9 #include <set>
10 #if (defined (__GNUC__) && !defined (__clang__))
11 #include <ext/mt_allocator.h>
12 #endif
13 #include <time.h>
14 
16 
17 #define LOWER_B 0
18 #define UPPER_B 2
19 #define BOTH_B 1
20 
21 #define _TRI_CLIP 1 //tempoarily disabled
22 #define TRI_CLIP_THRESH 32
23 #define CLIP_DATA_SIZE (3*12*sizeof(double))
24 #define KD_BINS 1024
25 
26 #define KD_MAX_STACK 64
27 
28 // #define Y_MIN3(a,b,c) ( ((a)>(b)) ? ( ((b)>(c))?(c):(b)):( ((a)>(c))?(c):(a)) )
29 // #define Y_MAX3(a,b,c) ( ((a)<(b)) ? ( ((b)>(c))?(b):(c)):( ((a)>(c))?(a):(c)) )
30 
31 #if (defined(_M_IX86) || defined(i386) || defined(_X86_))
32  #define Y_FAST_INT 1
33 #else
34  #define Y_FAST_INT 0
35 #endif
36 
37 #define _doublemagicroundeps (0.5 - 1.4e-11)
38 
39 inline int Y_Round2Int(double val) {
40 #if Y_FAST_INT > 0
41  union { double f; int i[2]; } u;
42  u.f = val + 6755399441055744.0; //2^52 * 1.5, uses limited precision to floor
43  return u.i[0];
44 #else
45  return int(val);
46 #endif
47 }
48 
49 inline int Y_Float2Int(double val) {
50 #if Y_FAST_INT > 0
51  return (val<0) ? Y_Round2Int( val+_doublemagicroundeps ) :
53 #else
54  return (int)val;
55 #endif
56 }
57 
58 //still in old file...
59 //int Kd_inodes=0, Kd_leaves=0, _emptyKd_leaves=0, Kd_prims=0, _clip=0, _bad_clip=0, _null_clip=0, _early_out=0;
60 
61 //bound_t getTriBound(const triangle_t tri);
62 //int triBoxOverlap(double boxcenter[3],double boxhalfsize[3],double triverts[3][3]);
63 //int triBoxClip(const double b_min[3], const double b_max[3], const double triverts[3][3], bound_t &box);
64 
65 template<class T>
66 kdTree_t<T>::kdTree_t(const T **v, int np, int depth, int leafSize,
67  float cost_ratio, float emptyBonus)
68  : costRatio(cost_ratio), eBonus(emptyBonus), maxDepth(depth)
69 {
70  std::cout << "starting build of kd-tree ("<<np<<" prims, cr:"<<costRatio<<" eb:"<<eBonus<<")\n";
71  clock_t c_start, c_end;
72  c_start = clock();
73  Kd_inodes=0, Kd_leaves=0, _emptyKd_leaves=0, Kd_prims=0, depthLimitReached=0, NumBadSplits=0,
75  totalPrims = np;
76  nextFreeNode = 0;
77  allocatedNodesCount = 256;
78  nodes = (rkdTreeNode<T>*)y_memalign(64, 256 * sizeof(rkdTreeNode<T>));
79  if(maxDepth <= 0) maxDepth = int( 7.0f + 1.66f * log(float(totalPrims)) );
80  double logLeaves = 1.442695f * log(double(totalPrims)); // = base2 log
81  if(leafSize <= 0)
82  {
83  //maxLeafSize = int( 1.442695f * log(float(totalPrims)/62500.0) );
84  int mls = int( logLeaves - 16.0 );
85  if(mls <= 0) mls = 1;
86  maxLeafSize = (unsigned int) mls;
87  }
88  else maxLeafSize = (unsigned int) leafSize;
89  if(maxDepth>KD_MAX_STACK) maxDepth = KD_MAX_STACK; //to prevent our stack to overflow
90  //experiment: add penalty to cost ratio to reduce memory usage on huge scenes
91  if( logLeaves > 16.0 ) costRatio += 0.25*( logLeaves - 16.0 );
92  allBounds = new bound_t[totalPrims + TRI_CLIP_THRESH+1];
93  std::cout << "getting triangle bounds...";
94  for(u_int32 i=0; i<totalPrims; i++)
95  {
96  allBounds[i] = v[i]->getBound();
97  /* calc tree bound. Remember to upgrade bound_t class... */
98  if(i) treeBound = bound_t(treeBound, allBounds[i]);
99  else treeBound = allBounds[i];
100  }
101  //slightly(!) increase tree bound to prevent errors with prims
102  //lying in a bound plane (still slight bug with trees where one dim. is 0)
103  for(int i=0;i<3;i++)
104  {
105  double foo = (treeBound.g[i] - treeBound.a[i])*0.001;
106  treeBound.a[i] -= foo, treeBound.g[i] += foo;
107  }
108  std::cout << "done!\n";
109  // get working memory for tree construction
110  boundEdge *edges[3];
111  u_int32 rMemSize = 3*totalPrims; // (maxDepth+1)*totalPrims;
112  u_int32 *leftPrims = new u_int32[std::max( (u_int32)2*TRI_CLIP_THRESH, totalPrims )];
113  u_int32 *rightPrims = new u_int32[rMemSize]; //just a rough guess, allocating worst case is insane!
114 // u_int32 *primNums = new u_int32[totalPrims]; //isn't this like...totaly unnecessary? use leftPrims?
115  for (int i = 0; i < 3; ++i) edges[i] = new boundEdge[514/*2*totalPrims*/];
116  clip = new int[maxDepth+2];
117  cdata = (char*)y_memalign(64, (maxDepth+2)*TRI_CLIP_THRESH*CLIP_DATA_SIZE);
118 
119  // prepare data
120  for (u_int32 i = 0; i < totalPrims; i++) leftPrims[i] = i;//primNums[i] = i;
121  for (int i = 0; i < maxDepth+2; i++) clip[i] = -1;
122 
123  /* build tree */
124  prims = v;
125  std::cout << "starting recursive build...\n";
126  buildTree(totalPrims, treeBound, leftPrims,
127  leftPrims, rightPrims, edges, // <= working memory
128  rMemSize, 0, 0 );
129 
130  // free working memory
131  delete[] leftPrims;
132  delete[] rightPrims;
133  delete[] allBounds;
134  for (int i = 0; i < 3; ++i) delete[] edges[i];
135  delete[] clip;
136  y_free(cdata);
137  //print some stats:
138  c_end = clock() - c_start;
139  std::cout << "\n=== kd-tree stats ("<< float(c_end) / (float)CLOCKS_PER_SEC <<"s) ===\n";
140  std::cout << "used/allocated kd-tree nodes: " << nextFreeNode << "/" << allocatedNodesCount
141  << " (" << 100.f * float(nextFreeNode)/allocatedNodesCount << "%)\n";
142  std::cout << "primitives in tree: " << totalPrims << std::endl;
143  std::cout << "interior nodes: " << Kd_inodes << " / " << "leaf nodes: " << Kd_leaves
144  << " (empty: " << _emptyKd_leaves << " = " << 100.f * float(_emptyKd_leaves)/Kd_leaves << "%)\n";
145  std::cout << "leaf prims: " << Kd_prims << " (" << float(Kd_prims)/totalPrims << "x prims in tree, leaf size:"<< maxLeafSize<<")\n";
146  std::cout << " => " << float(Kd_prims)/ (Kd_leaves-_emptyKd_leaves) << " prims per non-empty leaf\n";
147  std::cout << "leaves due to depth limit/bad splits: " << depthLimitReached << "/" << NumBadSplits << "\n";
148  std::cout << "clipped triangles: " << _clip << " (" <<_bad_clip << " bad clips, "<<_null_clip
149  <<" null clips)\n";
150  //std::cout << "early outs: " << _early_out << "\n\n";
151 }
152 
153 template<class T>
155 {
156 // std::cout << "kd-tree destructor: freeing nodes...";
157  y_free(nodes);
158 // std::cout << "done!\n";
159  //y_free(prims); //├╝berfl├╝ssig?
160 }
161 
162 // ============================================================
168 template<class T>
169 void kdTree_t<T>::pigeonMinCost(u_int32 nPrims, bound_t &nodeBound, u_int32 *primIdx, splitCost_t &split)
170 {
171  bin_t bin[ KD_BINS+1 ];
172  float d[3];
173  d[0] = nodeBound.longX();
174  d[1] = nodeBound.longY();
175  d[2] = nodeBound.longZ();
176  split.oldCost = float(nPrims);
177  split.bestCost = std::numeric_limits<float>::infinity();
178  float invTotalSA = 1.0f / (d[0]*d[1] + d[0]*d[2] + d[1]*d[2]);
179  float t_low, t_up;
180  int b_left, b_right;
181 
182  for(int axis=0;axis<3;axis++)
183  {
184  float s = KD_BINS/d[axis];
185  float min = nodeBound.a[axis];
186  // pigeonhole sort:
187  for(unsigned int i=0; i<nPrims; ++i)
188  {
189  const bound_t &bbox = allBounds[ primIdx[i] ];
190  t_low = bbox.a[axis];
191  t_up = bbox.g[axis];
192  b_left = (int)((t_low - min)*s);
193  b_right = (int)((t_up - min)*s);
194 // b_left = Y_Round2Int( ((t_low - min)*s) );
195 // b_right = Y_Round2Int( ((t_up - min)*s) );
196  if(b_left<0) b_left=0; else if(b_left > KD_BINS) b_left = KD_BINS;
197  if(b_right<0) b_right=0; else if(b_right > KD_BINS) b_right = KD_BINS;
198 
199  if(t_low == t_up)
200  {
201  if(bin[b_left].empty() || (t_low >= bin[b_left].t && !bin[b_left].empty() ) )
202  {
203  bin[b_left].t = t_low;
204  bin[b_left].c_both++;
205  }
206  else
207  {
208  bin[b_left].c_left++;
209  bin[b_left].c_right++;
210  }
211  bin[b_left].n += 2;
212  }
213  else
214  {
215  if(bin[b_left].empty() || (t_low > bin[b_left].t && !bin[b_left].empty() ) )
216  {
217  bin[b_left].t = t_low;
218  bin[b_left].c_left += bin[b_left].c_both + bin[b_left].c_bleft;
219  bin[b_left].c_right += bin[b_left].c_both;
220  bin[b_left].c_both = bin[b_left].c_bleft = 0;
221  bin[b_left].c_bleft++;
222  }
223  else if(t_low == bin[b_left].t)
224  {
225  bin[b_left].c_bleft++;
226  }
227  else bin[b_left].c_left++;
228  bin[b_left].n++;
229 
230  bin[b_right].c_right++;
231  if(bin[b_right].empty() || t_up > bin[b_right].t)
232  {
233  bin[b_right].t = t_up;
234  bin[b_right].c_left += bin[b_right].c_both + bin[b_right].c_bleft;
235  bin[b_right].c_right += bin[b_right].c_both;
236  bin[b_right].c_both = bin[b_right].c_bleft = 0;
237  }
238  bin[b_right].n++;
239  }
240 
241  }
242 
243  const int axisLUT[3][3] = { {0,1,2}, {1,2,0}, {2,0,1} };
244  float capArea = d[ axisLUT[1][axis] ] * d[ axisLUT[2][axis] ];
245  float capPerim = d[ axisLUT[1][axis] ] + d[ axisLUT[2][axis] ];
246 
247  unsigned int nBelow=0, nAbove=nPrims;
248  // cumulate prims and evaluate cost
249  for(int i=0; i<KD_BINS+1; ++i)
250  {
251  if(!bin[i].empty())
252  {
253  nBelow += bin[i].c_left;
254  nAbove -= bin[i].c_right;
255  // cost:
256  float edget = bin[i].t;
257  if (edget > nodeBound.a[axis] &&
258  edget < nodeBound.g[axis]) {
259  // Compute cost for split at _i_th edge
260  float l1 = edget - nodeBound.a[axis];
261  float l2 = nodeBound.g[axis] - edget;
262  float belowSA = capArea + l1*capPerim;
263  float aboveSA = capArea + l2*capPerim;
264  float rawCosts = (belowSA * nBelow + aboveSA * nAbove);
265  //float eb = (nAbove == 0 || nBelow == 0) ? eBonus*rawCosts : 0.f;
266  float eb;
267  if(nAbove == 0) eb = (0.1f + l2/d[axis])*eBonus*rawCosts;
268  else if(nBelow == 0) eb = (0.1f + l1/d[axis])*eBonus*rawCosts;
269  else eb = 0.0f;
270  float cost = costRatio + invTotalSA * (rawCosts - eb);
271  // Update best split if this is lowest cost so far
272  if (cost < split.bestCost) {
273  split.t = edget;
274  split.bestCost = cost;
275  split.bestAxis = axis;
276  split.bestOffset = i; // kinda useless...
277  split.nBelow = nBelow;
278  split.nAbove = nAbove;
279  }
280  }
281  nBelow += bin[i].c_both + bin[i].c_bleft;
282  nAbove -= bin[i].c_both;
283  }
284  } // for all bins
285  if(nBelow != nPrims || nAbove != 0)
286  {
287  int c1=0, c2=0, c3=0, c4=0, c5=0;
288  std::cout << "SCREWED!!\n";
289  for(int i=0;i<KD_BINS+1;i++){ c1+= bin[i].n; std::cout << bin[i].n << " ";}
290  std::cout << "\nn total: "<< c1 << "\n";
291  for(int i=0;i<KD_BINS+1;i++){ c2+= bin[i].c_left; std::cout << bin[i].c_left << " ";}
292  std::cout << "\nc_left total: "<< c2 << "\n";
293  for(int i=0;i<KD_BINS+1;i++){ c3+= bin[i].c_bleft; std::cout << bin[i].c_bleft << " ";}
294  std::cout << "\nc_bleft total: "<< c3 << "\n";
295  for(int i=0;i<KD_BINS+1;i++){ c4+= bin[i].c_both; std::cout << bin[i].c_both << " ";}
296  std::cout << "\nc_both total: "<< c4 << "\n";
297  for(int i=0;i<KD_BINS+1;i++){ c5+= bin[i].c_right; std::cout << bin[i].c_right << " ";}
298  std::cout << "\nc_right total: "<< c5 << "\n";
299  std::cout << "\nnPrims: "<<nPrims<<" nBelow: "<<nBelow<<" nAbove: "<<nAbove<<"\n";
300  std::cout << "total left: " << c2 + c3 + c4 << "\ntotal right: " << c4 + c5 << "\n";
301  std::cout << "n/2: " << c1/2 << "\n";
302  throw std::logic_error("cost function mismatch");
303  }
304  for(int i=0;i<KD_BINS+1;i++) bin[i].reset();
305  } // for all axis
306 }
307 
308 // ============================================================
313 template<class T>
314 void kdTree_t<T>::minimalCost(u_int32 nPrims, bound_t &nodeBound, u_int32 *primIdx,
315  const bound_t *pBounds, boundEdge *edges[3], splitCost_t &split)
316 {
317  float d[3];
318  d[0] = nodeBound.longX();
319  d[1] = nodeBound.longY();
320  d[2] = nodeBound.longZ();
321  split.oldCost = float(nPrims);
322  split.bestCost = std::numeric_limits<float>::infinity();
323  float invTotalSA = 1.0f / (d[0]*d[1] + d[0]*d[2] + d[1]*d[2]);
324  int nEdge;
325 
326  for(int axis=0;axis<3;axis++)
327  {
328  // << get edges for axis >>
329  int pn;
330  nEdge=0;
331  //test!
332  if(pBounds!=allBounds) for (unsigned int i=0; i < nPrims; i++)
333  {
334  pn = primIdx[i];
335  const bound_t &bbox = pBounds[i];
336  if(bbox.a[axis] == bbox.g[axis])
337  {
338  edges[axis][nEdge] = boundEdge(bbox.a[axis], i /* pn */, BOTH_B);
339  ++nEdge;
340  }
341  else
342  {
343  edges[axis][nEdge] = boundEdge(bbox.a[axis], i /* pn */, LOWER_B);
344  edges[axis][nEdge+1] = boundEdge(bbox.g[axis], i /* pn */, UPPER_B);
345  nEdge += 2;
346  }
347  }
348  else for (unsigned int i=0; i < nPrims; i++)
349  {
350  pn = primIdx[i];
351  const bound_t &bbox = pBounds[pn];
352  if(bbox.a[axis] == bbox.g[axis])
353  {
354  edges[axis][nEdge] = boundEdge(bbox.a[axis], pn, BOTH_B);
355  ++nEdge;
356  }
357  else
358  {
359  edges[axis][nEdge] = boundEdge(bbox.a[axis], pn, LOWER_B);
360  edges[axis][nEdge+1] = boundEdge(bbox.g[axis], pn, UPPER_B);
361  nEdge += 2;
362  }
363  }
364  std::sort(&edges[axis][0], &edges[axis][nEdge]);
365  // Compute cost of all splits for _axis_ to find best
366  const int axisLUT[3][3] = { {0,1,2}, {1,2,0}, {2,0,1} };
367  float capArea = d[ axisLUT[1][axis] ] * d[ axisLUT[2][axis] ];
368  float capPerim = d[ axisLUT[1][axis] ] + d[ axisLUT[2][axis] ];
369  unsigned int nBelow = 0, nAbove = nPrims;
370  //todo: early-out criteria: if l1 > l2*nPrims (l2 > l1*nPrims) => minimum is lowest (highest) edge!
371  if(nPrims>5)
372  {
373  float edget = edges[axis][0].pos;
374  float l1 = edget - nodeBound.a[axis];
375  float l2 = nodeBound.g[axis] - edget;
376  if(l1 > l2*float(nPrims) && l2 > 0.f)
377  {
378  float rawCosts = (capArea + l2*capPerim) * nPrims;
379  float cost = costRatio + invTotalSA * (rawCosts - eBonus); //todo: use proper ebonus...
380  //optimal cost is definitely here, and nowhere else!
381  if (cost < split.bestCost) {
382  split.bestCost = cost;
383  split.bestAxis = axis;
384  split.bestOffset = 0;
385  split.nEdge = nEdge;
386  ++_early_out;
387  }
388  continue;
389  }
390  edget = edges[axis][nEdge-1].pos;
391  l1 = edget - nodeBound.a[axis];
392  l2 = nodeBound.g[axis] - edget;
393  if(l2 > l1*float(nPrims) && l1 > 0.f)
394  {
395  float rawCosts = (capArea + l1*capPerim) * nPrims;
396  float cost = costRatio + invTotalSA * (rawCosts - eBonus); //todo: use proper ebonus...
397  if (cost < split.bestCost) {
398  split.bestCost = cost;
399  split.bestAxis = axis;
400  split.bestOffset = nEdge-1;
401  split.nEdge = nEdge;
402  ++_early_out;
403  }
404  continue;
405  }
406  }
407 
408  for (int i = 0; i < nEdge; ++i) {
409  if (edges[axis][i].end == UPPER_B) --nAbove;
410  float edget = edges[axis][i].pos;
411  if (edget > nodeBound.a[axis] &&
412  edget < nodeBound.g[axis]) {
413  // Compute cost for split at _i_th edge
414  float l1 = edget - nodeBound.a[axis];
415  float l2 = nodeBound.g[axis] - edget;
416  float belowSA = capArea + (l1)*capPerim;
417  float aboveSA = capArea + (l2)*capPerim;
418  float rawCosts = (belowSA * nBelow + aboveSA * nAbove);
419  //float eb = (nAbove == 0 || nBelow == 0) ? eBonus*rawCosts : 0.f;
420  float eb;
421  if(nAbove == 0) eb = (0.1f + l2/d[axis])*eBonus*rawCosts;
422  else if(nBelow == 0) eb = (0.1f + l1/d[axis])*eBonus*rawCosts;
423  else eb = 0.0f;
424  float cost = costRatio + invTotalSA * (rawCosts - eb);
425  // Update best split if this is lowest cost so far
426  if (cost < split.bestCost) {
427  split.bestCost = cost;
428  split.bestAxis = axis;
429  split.bestOffset = i;
430  split.nEdge = nEdge;
431  //delete again:
432  split.nBelow = nBelow;
433  split.nAbove = nAbove;
434  }
435  }
436  if (edges[axis][i].end != UPPER_B)
437  {
438  ++nBelow;
439  if (edges[axis][i].end == BOTH_B) --nAbove;
440  }
441  }
442  if(nBelow != nPrims || nAbove != 0) std::cout << "you screwed your new idea!\n";
443 // Assert(nBelow == nPrims && nAbove == 0);
444  }
445 }
446 
447 // ============================================================
454 template<class T>
455 int kdTree_t<T>::buildTree(u_int32 nPrims, bound_t &nodeBound, u_int32 *primNums,
456  u_int32 *leftPrims, u_int32 *rightPrims, boundEdge *edges[3], //working memory
457  u_int32 rightMemSize, int depth, int badRefines ) // status
458 {
459 // std::cout << "tree level: " << depth << std::endl;
460  if (nextFreeNode == allocatedNodesCount) {
461  int newCount = 2*allocatedNodesCount;
462  newCount = (newCount > 0x100000) ? allocatedNodesCount+0x80000 : newCount;
463  rkdTreeNode<T> *n = (rkdTreeNode<T> *) y_memalign(64, newCount * sizeof(rkdTreeNode<T>));
464  memcpy(n, nodes, allocatedNodesCount * sizeof(rkdTreeNode<T>));
465  y_free(nodes);
466  nodes = n;
467  allocatedNodesCount = newCount;
468  }
469 
470 #if _TRI_CLIP > 0
471  if(nPrims <= TRI_CLIP_THRESH)
472  {
473 // exBound_t ebound(nodeBound);
474  int oPrims[TRI_CLIP_THRESH], nOverl=0;
475  double bHalfSize[3];
476  double b_ext[2][3];
477  for(int i=0; i<3; ++i)
478  {
479 // bCenter[i] = ((double)nodeBound.a[i] + (double)nodeBound.g[i])*0.5;
480  bHalfSize[i] = ((double)nodeBound.g[i] - (double)nodeBound.a[i]);
481  double temp = ((double)treeBound.g[i] - (double)treeBound.a[i]);
482  b_ext[0][i] = nodeBound.a[i] - 0.021*bHalfSize[i] - 0.00001*temp;
483  b_ext[1][i] = nodeBound.g[i] + 0.021*bHalfSize[i] + 0.00001*temp;
484 // ebound.halfSize[i] *= 1.01;
485  }
486  char *c_old = cdata + (TRI_CLIP_THRESH * CLIP_DATA_SIZE * depth);
487  char *c_new = cdata + (TRI_CLIP_THRESH * CLIP_DATA_SIZE * (depth+1));
488  for(unsigned int i=0; i<nPrims; ++i)
489  {
490  const T *ct = prims[ primNums[i] ];
491  u_int32 old_idx=0;
492  if(clip[depth] >= 0) old_idx = primNums[i+nPrims];
493 // if(old_idx > TRI_CLIP_THRESH){ std::cout << "ouch!\n"; }
494 // std::cout << "parent idx: " << old_idx << std::endl;
495  if(ct->clippingSupport())
496  {
497  if( ct->clipToBound(b_ext, clip[depth], allBounds[totalPrims+nOverl],
498  c_old + old_idx*CLIP_DATA_SIZE, c_new + nOverl*CLIP_DATA_SIZE) )
499  {
500  ++_clip;
501  oPrims[nOverl] = primNums[i]; nOverl++;
502  }
503  else ++_null_clip;
504  }
505  else
506  {
507  // no clipping supported by prim, copy old bound:
508  allBounds[totalPrims+nOverl] = allBounds[ primNums[i] ]; //really??
509  oPrims[nOverl] = primNums[i]; nOverl++;
510  }
511  }
512  //copy back
513  memcpy(primNums, oPrims, nOverl*sizeof(u_int32));
514  nPrims = nOverl;
515  }
516 #endif
517  // << check if leaf criteria met >>
518  if(nPrims <= maxLeafSize || depth >= maxDepth)
519  {
520 // std::cout << "leaf\n";
521  nodes[nextFreeNode].createLeaf(primNums, nPrims, prims, primsArena);
522  nextFreeNode++;
523  if( depth >= maxDepth ) depthLimitReached++; //stat
524  return 0;
525  }
526 
527  //<< calculate cost for all axes and chose minimum >>
528  splitCost_t split;
529  float baseBonus=eBonus;
530  eBonus *= 1.1 - (float)depth/(float)maxDepth;
531  if(nPrims > 128) pigeonMinCost(nPrims, nodeBound, primNums, split);
532 #if _TRI_CLIP > 0
533  else if (nPrims > TRI_CLIP_THRESH) minimalCost(nPrims, nodeBound, primNums, allBounds, edges, split);
534  else minimalCost(nPrims, nodeBound, primNums, allBounds+totalPrims, edges, split);
535 #else
536  else minimalCost(nPrims, nodeBound, primNums, allBounds, edges, split);
537 #endif
538  eBonus=baseBonus; //restore eBonus
539  //<< if (minimum > leafcost) increase bad refines >>
540  if (split.bestCost > split.oldCost) ++badRefines;
541  if ((split.bestCost > 1.6f * split.oldCost && nPrims < 16) ||
542  split.bestAxis == -1 || badRefines == 2) {
543  nodes[nextFreeNode].createLeaf(primNums, nPrims, prims, primsArena);
544  nextFreeNode++;
545  if( badRefines == 2) ++NumBadSplits; //stat
546  return 0;
547  }
548 
549  //todo: check working memory for child recursive calls
550  u_int32 remainingMem, *morePrims = nullptr, *nRightPrims;
551  u_int32 *oldRightPrims = rightPrims;
552  if(nPrims > rightMemSize || 2*TRI_CLIP_THRESH > rightMemSize ) // *possibly* not enough, get some more
553  {
554 // std::cout << "buildTree: more memory allocated!\n";
555  remainingMem = nPrims * 3;
556  morePrims = new u_int32[remainingMem];
557  nRightPrims = morePrims;
558  }
559  else
560  {
561  nRightPrims = oldRightPrims;
562  remainingMem = rightMemSize;
563  }
564 
565  // Classify primitives with respect to split
566  float splitPos;
567  int n0 = 0, n1 = 0;
568  if(nPrims > 128) // we did pigeonhole
569  {
570  int pn;
571  for (unsigned int i=0; i<nPrims; i++)
572  {
573  pn = primNums[i];
574  if(allBounds[ pn ].a[split.bestAxis] >= split.t) nRightPrims[n1++] = pn;
575  else
576  {
577  leftPrims[n0++] = pn;
578  if(allBounds[ pn ].g[split.bestAxis] > split.t) nRightPrims[n1++] = pn;
579  }
580  }
581  splitPos = split.t;
582  if (n0!= split.nBelow || n1 != split.nAbove) std::cout << "oops!\n";
583 /* static int foo=0;
584  if(foo<10)
585  {
586  std::cout << "best axis:"<<split.bestAxis<<", rel. split:" <<(split.t - nodeBound.a[split.bestAxis])/(nodeBound.g[split.bestAxis]-nodeBound.a[split.bestAxis]);
587  std::cout << "\nleft Prims:"<<n0<<", right Prims:"<<n1<<", total Prims:"<<nPrims<<" (level:"<<depth<<")\n";
588  foo++;
589  }*/
590  }
591  else if(nPrims <= TRI_CLIP_THRESH)
592  {
593  int cindizes[TRI_CLIP_THRESH];
594  u_int32 oldPrims[TRI_CLIP_THRESH];
595 // std::cout << "memcpy\n";
596  memcpy(oldPrims, primNums, nPrims*sizeof(int));
597 
598  for (int i=0; i<split.bestOffset; ++i)
599  if (edges[split.bestAxis][i].end != UPPER_B)
600  {
601  cindizes[n0] = edges[split.bestAxis][i].primNum;
602 // if(cindizes[n0] >nPrims) std::cout << "error!!\n";
603  leftPrims[n0] = oldPrims[cindizes[n0]];
604  ++n0;
605  }
606 // std::cout << "append n0\n";
607  for(int i=0; i<n0; ++i){ leftPrims[n0+i] = cindizes[i]; /* std::cout << cindizes[i] << " "; */ }
608  if (edges[split.bestAxis][split.bestOffset].end == BOTH_B)
609  {
610  cindizes[n1] = edges[split.bestAxis][split.bestOffset].primNum;
611 // if(cindizes[n1] >nPrims) std::cout << "error!!\n";
612  nRightPrims[n1] = oldPrims[cindizes[n1]];
613  ++n1;
614  }
615  for (int i=split.bestOffset+1; i<split.nEdge; ++i)
616  if (edges[split.bestAxis][i].end != LOWER_B)
617  {
618  cindizes[n1] = edges[split.bestAxis][i].primNum;
619 // if(cindizes[n1] >nPrims) std::cout << "error!!\n";
620  nRightPrims[n1] = oldPrims[cindizes[n1]];
621  ++n1;
622  }
623 // std::cout << "\nappend n1\n";
624  for(int i=0; i<n1; ++i){ nRightPrims[n1+i] = cindizes[i]; /* std::cout << cindizes[i] << " "; */ }
625  splitPos = edges[split.bestAxis][split.bestOffset].pos;
626 // std::cout << "\ndone\n";
627  }
628  else //we did "normal" cost function
629  {
630  for (int i=0; i<split.bestOffset; ++i)
631  if (edges[split.bestAxis][i].end != UPPER_B)
632  leftPrims[n0++] = edges[split.bestAxis][i].primNum;
633  if (edges[split.bestAxis][split.bestOffset].end == BOTH_B)
634  nRightPrims[n1++] = edges[split.bestAxis][split.bestOffset].primNum;
635  for (int i=split.bestOffset+1; i<split.nEdge; ++i)
636  if (edges[split.bestAxis][i].end != LOWER_B)
637  nRightPrims[n1++] = edges[split.bestAxis][i].primNum;
638  splitPos = edges[split.bestAxis][split.bestOffset].pos;
639  }
640 // std::cout << "split axis: " << split.bestAxis << ", pos: " << splitPos << "\n";
641  //advance right prims pointer
642  remainingMem -= n1;
643 
644 
645  u_int32 curNode = nextFreeNode;
646  nodes[curNode].createInterior(split.bestAxis, splitPos);
647  ++nextFreeNode;
648  bound_t boundL = nodeBound, boundR = nodeBound;
649  switch(split.bestAxis){
650  case 0: boundL.setMaxX(splitPos); boundR.setMinX(splitPos); break;
651  case 1: boundL.setMaxY(splitPos); boundR.setMinY(splitPos); break;
652  case 2: boundL.setMaxZ(splitPos); boundR.setMinZ(splitPos); break;
653  }
654 
655 #if _TRI_CLIP > 0
656  if(nPrims <= TRI_CLIP_THRESH)
657  {
658  remainingMem -= n1;
659  //<< recurse below child >>
660  clip[depth+1] = split.bestAxis;
661  buildTree(n0, boundL, leftPrims, leftPrims, nRightPrims+2*n1, edges, remainingMem, depth+1, badRefines);
662  clip[depth+1] |= 1<<2;
663  //<< recurse above child >>
664  nodes[curNode].setRightChild (nextFreeNode);
665  buildTree(n1, boundR, nRightPrims, leftPrims, nRightPrims+2*n1, edges, remainingMem, depth+1, badRefines);
666  clip[depth+1] = -1;
667  }
668  else
669  {
670 #endif
671  //<< recurse below child >>
672  buildTree(n0, boundL, leftPrims, leftPrims, nRightPrims+n1, edges, remainingMem, depth+1, badRefines);
673  //<< recurse above child >>
674  nodes[curNode].setRightChild (nextFreeNode);
675  buildTree(n1, boundR, nRightPrims, leftPrims, nRightPrims+n1, edges, remainingMem, depth+1, badRefines);
676 #if _TRI_CLIP > 0
677  }
678 #endif
679  // free additional working memory, if present
680  if(morePrims) delete[] morePrims;
681  return 1;
682 }
683 
684 
685 
686 //============================
690 template<class T>
691 bool kdTree_t<T>::Intersect(const ray_t &ray, float dist, T **tr, float &Z, intersectData_t &data) const
692 {
693  Z=dist;
694 
695  float a, b, t; // entry/exit/splitting plane signed distance
696  float t_hit;
697 
698  if (!treeBound.cross(ray, a, b, dist))
699  { return false; }
700 
701  intersectData_t currentData, tempData;
702  vector3d_t invDir(1.0/ray.dir.x, 1.0/ray.dir.y, 1.0/ray.dir.z); //was 1.f!
703 // int rayId = curMailboxId++;
704  bool hit = false;
705 
706  rKdStack<T> stack[KD_MAX_STACK];
707  const rkdTreeNode<T> *farChild, *currNode;
708  currNode = nodes;
709 
710  int enPt = 0;
711  stack[enPt].t = a;
712 
713  //distinguish between internal and external origin
714  if(a >= 0.0) // ray with external origin
715  stack[enPt].pb = ray.from + ray.dir * a;
716  else // ray with internal origin
717  stack[enPt].pb = ray.from;
718 
719  // setup initial entry and exit poimt in stack
720  int exPt = 1; // pointer to stack
721  stack[exPt].t = b;
722  stack[exPt].pb = ray.from + ray.dir * b;
723  stack[exPt].node = nullptr; // "nowhere", termination flag
724 
725  //loop, traverse kd-Tree until object intersection or ray leaves tree bound
726  while (currNode != nullptr)
727  {
728  if (dist < stack[enPt].t) break;
729  // loop until leaf is found
730  while( !currNode->IsLeaf() )
731  {
732  int axis = currNode->SplitAxis();
733  float splitVal = currNode->SplitPos();
734 
735  if(stack[enPt].pb[axis] <= splitVal){
736  if(stack[exPt].pb[axis] <= splitVal)
737  {
738  currNode++;
739  continue;
740  }
741  if(stack[exPt].pb[axis] == splitVal)
742  {
743  currNode = &nodes[currNode->getRightChild()];
744  continue;
745  }
746  // case N4
747  farChild = &nodes[currNode->getRightChild()];
748  currNode ++;
749  }
750  else
751  {
752  if(splitVal < stack[exPt].pb[axis])
753  {
754  currNode = &nodes[currNode->getRightChild()];
755  continue;
756  }
757  farChild = currNode+1;
758  currNode = &nodes[currNode->getRightChild()];
759  }
760  // traverse both children
761 
762  t = (splitVal - ray.from[axis]) * invDir[axis];
763 
764  // setup the new exit point
765  int tmp = exPt;
766  exPt++;
767 
768  // possibly skip current entry point so not to overwrite the data
769  if (exPt == enPt) exPt++;
770  // push values onto the stack //todo: lookup table
771  static const int npAxis[2][3] = { {1, 2, 0}, {2, 0, 1} };
772  int nextAxis = npAxis[0][axis];//(axis+1)%3;
773  int prevAxis = npAxis[1][axis];//(axis+2)%3;
774  stack[exPt].prev = tmp;
775  stack[exPt].t = t;
776  stack[exPt].node = farChild;
777  stack[exPt].pb[axis] = splitVal;
778  stack[exPt].pb[nextAxis] = ray.from[nextAxis] + t * ray.dir[nextAxis];
779  stack[exPt].pb[prevAxis] = ray.from[prevAxis] + t * ray.dir[prevAxis];
780  }
781 
782  u_int32 nPrimitives = currNode->nPrimitives();
783  if (nPrimitives == 1)
784  {
785  T *mp = currNode->onePrimitive;
786  if (mp->intersect(ray, &t_hit, tempData))
787  {
788  if(t_hit < Z && t_hit >= ray.tmin)
789  {
790  Z = t_hit;
791  *tr = mp;
792  currentData = tempData;
793  hit = true;
794  }
795  }
796  }
797  else
798  {
799  T **prims = currNode->primitives;
800  for (u_int32 i = 0; i < nPrimitives; ++i) {
801  T *mp = prims[i];
802  if (mp->intersect(ray, &t_hit, tempData))
803  {
804  if(t_hit < Z && t_hit >= ray.tmin)
805  {
806  Z = t_hit;
807  *tr = mp;
808  currentData = tempData;
809  hit = true;
810  }
811  }
812  }
813  }
814 
815  if(hit && Z <= stack[exPt].t)
816  {
817  data = currentData;
818  return true;
819  }
820 
821  enPt = exPt;
822  currNode = stack[exPt].node;
823  exPt = stack[enPt].prev;
824 
825  } // while
826 
827  data = currentData;
828 
829  return hit;
830 }
831 
832 template<class T>
833 bool kdTree_t<T>::IntersectS(const ray_t &ray, float dist, T **tr, float shadow_bias) const
834 {
835  float a, b, t; // entry/exit/splitting plane signed distance
836  float t_hit;
837 
838  if (!treeBound.cross(ray, a, b, dist))
839  return false;
840 
841  intersectData_t bary;
842  vector3d_t invDir(1.f/ray.dir.x, 1.f/ray.dir.y, 1.f/ray.dir.z);
843 
844  rKdStack<T> stack[KD_MAX_STACK];
845  const rkdTreeNode<T> *farChild, *currNode;
846  currNode = nodes;
847 
848  int enPt = 0;
849  stack[enPt].t = a;
850 
851  //distinguish between internal and external origin
852  if(a >= 0.0) // ray with external origin
853  stack[enPt].pb = ray.from + ray.dir * a;
854  else // ray with internal origin
855  stack[enPt].pb = ray.from;
856 
857  // setup initial entry and exit poimt in stack
858  int exPt = 1; // pointer to stack
859  stack[exPt].t = b;
860  stack[exPt].pb = ray.from + ray.dir * b;
861  stack[exPt].node = nullptr; // "nowhere", termination flag
862 
863  //loop, traverse kd-Tree until object intersection or ray leaves tree bound
864  while (currNode != nullptr)
865  {
866  if (dist < stack[enPt].t /*a*/) break;
867  // loop until leaf is found
868  while( !currNode->IsLeaf() )
869  {
870  int axis = currNode->SplitAxis();
871  float splitVal = currNode->SplitPos();
872 
873  if(stack[enPt].pb[axis] <= splitVal){
874  if(stack[exPt].pb[axis] <= splitVal)
875  {
876  currNode++;
877  continue;
878  }
879  if(stack[exPt].pb[axis] == splitVal)
880  {
881  currNode = &nodes[currNode->getRightChild()];
882  continue;
883  }
884  // case N4
885  farChild = &nodes[currNode->getRightChild()];
886  currNode ++;
887  }
888  else
889  {
890  if(splitVal < stack[exPt].pb[axis])
891  {
892  currNode = &nodes[currNode->getRightChild()];
893  continue;
894  }
895  farChild = currNode+1;
896  currNode = &nodes[currNode->getRightChild()];
897  }
898  // traverse both children
899 
900  t = (splitVal - ray.from[axis]) * invDir[axis];
901 
902  // setup the new exit point
903  int tmp = exPt;
904  exPt++;
905 
906  // possibly skip current entry point so not to overwrite the data
907  if (exPt == enPt) exPt++;
908  // push values onto the stack //todo: lookup table
909  static const int npAxis[2][3] = { {1, 2, 0}, {2, 0, 1} };
910  int nextAxis = npAxis[0][axis];//(axis+1)%3;
911  int prevAxis = npAxis[1][axis];//(axis+2)%3;
912  stack[exPt].prev = tmp;
913  stack[exPt].t = t;
914  stack[exPt].node = farChild;
915  stack[exPt].pb[axis] = splitVal;
916  stack[exPt].pb[nextAxis] = ray.from[nextAxis] + t * ray.dir[nextAxis];
917  stack[exPt].pb[prevAxis] = ray.from[prevAxis] + t * ray.dir[prevAxis];
918  }
919 
920  // Check for intersections inside leaf node
921  u_int32 nPrimitives = currNode->nPrimitives();
922  if (nPrimitives == 1)
923  {
924  T *mp = currNode->onePrimitive;
925  if (mp->intersect(ray, &t_hit, bary))
926  {
927  if(t_hit < dist && t_hit > ray.tmin )
928  {
929  *tr = mp;
930  return true;
931  }
932  }
933  }
934  else
935  {
936  T **prims = currNode->primitives;
937  for (u_int32 i = 0; i < nPrimitives; ++i)
938  {
939  T *mp = prims[i];
940  if (mp->intersect(ray, &t_hit, bary))
941  {
942  if(t_hit < dist && t_hit > ray.tmin )
943  {
944  *tr = mp;
945  return true;
946  }
947  }
948  }
949  }
950 
951  enPt = exPt;
952  currNode = stack[exPt].node;
953  exPt = stack[enPt].prev;
954 
955  } // while
956 
957  return false;
958 }
959 
960 /*=============================================================
961  allow for transparent shadows.
962 =============================================================*/
963 
964 template<class T>
965 bool kdTree_t<T>::IntersectTS(renderState_t &state, const ray_t &ray, int maxDepth, float dist, T **tr, color_t &filt, float shadow_bias) const
966 {
967  float a, b, t; // entry/exit/splitting plane signed distance
968  float t_hit;
969 
970  if (!treeBound.cross(ray, a, b, dist))
971  return false;
972 
973  intersectData_t bary;
974  vector3d_t invDir(1.f/ray.dir.x, 1.f/ray.dir.y, 1.f/ray.dir.z);
975 
976  int depth=0;
977 #if (defined (__GNUC__) && !defined (__clang__))
978  std::set<const T *, std::less<const T *>, __gnu_cxx::__mt_alloc<const T *> > filtered;
979 #else
980  std::set<const T *> filtered;
981 #endif
982  rKdStack<T> stack[KD_MAX_STACK];
983  const rkdTreeNode<T> *farChild, *currNode;
984  currNode = nodes;
985 
986  int enPt = 0;
987  stack[enPt].t = a;
988 
989  //distinguish between internal and external origin
990  if(a >= 0.0) // ray with external origin
991  stack[enPt].pb = ray.from + ray.dir * a;
992  else // ray with internal origin
993  stack[enPt].pb = ray.from;
994 
995  // setup initial entry and exit poimt in stack
996  int exPt = 1; // pointer to stack
997  stack[exPt].t = b;
998  stack[exPt].pb = ray.from + ray.dir * b;
999  stack[exPt].node = nullptr; // "nowhere", termination flag
1000 
1001  //loop, traverse kd-Tree until object intersection or ray leaves tree bound
1002  while (currNode != nullptr)
1003  {
1004  if (dist < stack[enPt].t /*a*/) break;
1005  // loop until leaf is found
1006  while( !currNode->IsLeaf() )
1007  {
1008  int axis = currNode->SplitAxis();
1009  float splitVal = currNode->SplitPos();
1010 
1011  if(stack[enPt].pb[axis] <= splitVal){
1012  if(stack[exPt].pb[axis] <= splitVal)
1013  {
1014  currNode++;
1015  continue;
1016  }
1017  if(stack[exPt].pb[axis] == splitVal)
1018  {
1019  currNode = &nodes[currNode->getRightChild()];
1020  continue;
1021  }
1022  // case N4
1023  farChild = &nodes[currNode->getRightChild()];
1024  currNode ++;
1025  }
1026  else
1027  {
1028  if(splitVal < stack[exPt].pb[axis])
1029  {
1030  currNode = &nodes[currNode->getRightChild()];
1031  continue;
1032  }
1033  farChild = currNode+1;
1034  currNode = &nodes[currNode->getRightChild()];
1035  }
1036  // traverse both children
1037 
1038  t = (splitVal - ray.from[axis]) * invDir[axis];
1039 
1040  // setup the new exit point
1041  int tmp = exPt;
1042  exPt++;
1043 
1044  // possibly skip current entry point so not to overwrite the data
1045  if (exPt == enPt) exPt++;
1046  // push values onto the stack //todo: lookup table
1047  static const int npAxis[2][3] = { {1, 2, 0}, {2, 0, 1} };
1048  int nextAxis = npAxis[0][axis];//(axis+1)%3;
1049  int prevAxis = npAxis[1][axis];//(axis+2)%3;
1050  stack[exPt].prev = tmp;
1051  stack[exPt].t = t;
1052  stack[exPt].node = farChild;
1053  stack[exPt].pb[axis] = splitVal;
1054  stack[exPt].pb[nextAxis] = ray.from[nextAxis] + t * ray.dir[nextAxis];
1055  stack[exPt].pb[prevAxis] = ray.from[prevAxis] + t * ray.dir[prevAxis];
1056  }
1057 
1058  // Check for intersections inside leaf node
1059  u_int32 nPrimitives = currNode->nPrimitives();
1060  if (nPrimitives == 1)
1061  {
1062  T *mp = currNode->onePrimitive;
1063  if (mp->intersect(ray, &t_hit, bary))
1064  {
1065  if(t_hit < dist && t_hit >= ray.tmin )
1066  {
1067  const material_t *mat = mp->getMaterial();
1068  if(!mat->isTransparent() ) return true;
1069  if(filtered.insert(mp).second)
1070  {
1071  if(depth>=maxDepth) return true;
1072  point3d_t h=ray.from + t_hit*ray.dir;
1073  surfacePoint_t sp;
1074  mp->getSurface(sp, h, bary);
1075  filt *= mat->getTransparency(state, sp, ray.dir);
1076  ++depth;
1077  }
1078  }
1079  }
1080  }
1081  else
1082  {
1083  T **prims = currNode->primitives;
1084  for (u_int32 i = 0; i < nPrimitives; ++i) {
1085  T *mp = prims[i];
1086  if (mp->intersect(ray, &t_hit, bary))
1087  {
1088  if(t_hit < dist && t_hit >= ray.tmin )
1089  {
1090  const material_t *mat = mp->getMaterial();
1091  if(!mat->isTransparent() ) return true;
1092  if(filtered.insert(mp).second)
1093  {
1094  if(depth>=maxDepth) return true;
1095  point3d_t h=ray.from + t_hit*ray.dir;
1096  surfacePoint_t sp;
1097  mp->getSurface(sp, h, bary);
1098  filt *= mat->getTransparency(state, sp, ray.dir);
1099  ++depth;
1100  }
1101  }
1102  }
1103  }
1104  }
1105 
1106  enPt = exPt;
1107  currNode = stack[exPt].node;
1108  exPt = stack[enPt].prev;
1109 
1110  } // while
1111 
1112  return false;
1113 }
1114 
1115 // explicit instantiation of template:
1116 template class kdTree_t<triangle_t>;
1117 template class kdTree_t<primitive_t>;
1118 
void y_free(void *ptr)
Definition: y_alloc.h:45
point3d_t g
Definition: bound.h:134
vector3d_t dir
Definition: ray.h:19
bool Intersect(const ray_t &ray, float dist, T **tr, float &Z, intersectData_t &data) const
Definition: ray_kdtree.cc:691
void setMaxY(float Y)
Cuts the bound to have the given max Y.
Definition: bound.h:100
int bestAxis
Definition: kdtree.h:102
point3d_t pb
the point coordinates of entry/exit point
Definition: ray_kdtree.h:72
bool IntersectTS(renderState_t &state, const ray_t &ray, int maxDepth, float dist, T **tr, color_t &filt, float shadow_bias) const
Definition: ray_kdtree.cc:965
float longX() const
Returns the lenght along X axis.
Definition: bound.h:89
bool cross(const ray_t &ray, float &enter, float &leave, const float dist) const
Returns true if the given ray crosses the bound.
Definition: bound.h:158
int prev
the pointer to the previous stack item
Definition: ray_kdtree.h:73
float SplitPos() const
Definition: ray_kdtree.h:51
kdTree_t(const T **v, int np, int depth=-1, int leafSize=2, float cost_ratio=0.35, float emptyBonus=0.33)
Definition: ray_kdtree.cc:66
#define UPPER_B
Definition: ray_kdtree.cc:18
int c_left
Definition: kdtree.h:118
float t
Definition: kdtree.h:120
int nBelow
Definition: kdtree.h:108
__BEGIN_YAFRAY int _early_out
Definition: kdtree.cc:53
int bestOffset
Definition: kdtree.h:104
#define BOTH_B
Definition: ray_kdtree.cc:19
const rkdTreeNode< T > * node
pointer to far child
Definition: ray_kdtree.h:70
#define __BEGIN_YAFRAY
float t
Definition: kdtree.h:107
float tmin
Definition: ray.h:20
int c_right
Definition: kdtree.h:118
float oldCost
Definition: kdtree.h:106
int SplitAxis() const
Definition: ray_kdtree.h:52
__BEGIN_YAFRAY typedef unsigned int u_int32
Definition: y_alloc.h:17
Definition: ray.h:11
__BEGIN_YAFRAY int _bad_clip
Definition: kdtree.cc:53
__BEGIN_YAFRAY int Kd_inodes
Definition: kdtree.cc:53
Definition: scene.h:39
Definition: kdtree.h:111
void setMaxZ(float Z)
Cuts the bound to have the given max Z.
Definition: bound.h:105
virtual bool isTransparent() const
Definition: material.h:138
__BEGIN_YAFRAY int _null_clip
Definition: kdtree.cc:53
float pos
Definition: kdtree.h:79
int nAbove
Definition: kdtree.h:108
bool empty()
Definition: kdtree.h:115
int end
Definition: kdtree.h:81
void setMaxX(float X)
Cuts the bound to have the given max X.
Definition: bound.h:95
Definition: color.h:49
virtual color_t getTransparency(const renderState_t &state, const surfacePoint_t &sp, const vector3d_t &wo) const
Definition: material.h:142
#define KD_MAX_STACK
Definition: ray_kdtree.cc:26
float bestCost
Definition: kdtree.h:105
Definition: bound.h:50
__BEGIN_YAFRAY int Kd_prims
Definition: kdtree.cc:53
#define KD_BINS
Definition: ray_kdtree.cc:24
int c_both
Definition: kdtree.h:119
#define _doublemagicroundeps
Definition: ray_kdtree.cc:37
float max(float a, float b)
Definition: GridVolume.cc:117
float z
Definition: vector3d.h:92
#define CLIP_DATA_SIZE
Definition: ray_kdtree.cc:23
int nEdge
Definition: kdtree.h:108
float x
Definition: vector3d.h:92
int nPrimitives() const
Definition: ray_kdtree.h:53
__BEGIN_YAFRAY int _emptyKd_leaves
Definition: kdtree.cc:53
point3d_t a
Two points define the box.
Definition: bound.h:134
int c_bleft
Definition: kdtree.h:119
#define Z
Definition: tribox3_d.cc:25
void * y_memalign(size_t bound, size_t size)
Definition: y_alloc.h:23
#define LOWER_B
Definition: ray_kdtree.cc:17
int n
Definition: kdtree.h:116
__BEGIN_YAFRAY int Kd_leaves
Definition: kdtree.cc:53
float y
Definition: vector3d.h:92
int Y_Float2Int(double val)
Definition: ray_kdtree.cc:49
int primNum
Definition: kdtree.h:80
#define TRI_CLIP_THRESH
Definition: ray_kdtree.cc:22
float longZ() const
Returns the lenght along Y axis.
Definition: bound.h:93
float longY() const
Returns the lenght along Y axis.
Definition: bound.h:91
__BEGIN_YAFRAY int _clip
Definition: kdtree.cc:53
T * onePrimitive
leaf: direct inxex of one primitive
Definition: ray_kdtree.h:62
bool IsLeaf() const
Definition: ray_kdtree.h:54
T ** primitives
leaf: list of primitives
Definition: ray_kdtree.h:61
point3d_t from
Definition: ray.h:18
u_int32 getRightChild() const
Definition: ray_kdtree.h:55
bool IntersectS(const ray_t &ray, float dist, T **tr, float shadow_bias) const
Definition: ray_kdtree.cc:833
int Y_Round2Int(double val)
Definition: ray_kdtree.cc:39
float t
the entry/exit signed distance
Definition: ray_kdtree.h:71
#define __END_YAFRAY
float min(float a, float b)
Definition: GridVolume.cc:116