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