YafaRay Core  v3.2.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
kdtree.h
Go to the documentation of this file.
1 #ifndef __Y_KDTREE_H
2 #define __Y_KDTREE_H
3 
4 #include <yafray_config.h>
5 
6 #include <algorithm>
7 
8 #include <utilities/y_alloc.h>
9 #include <core_api/bound.h>
10 #include <core_api/object3d.h>
11 #include <yafraycore/meshtypes.h>
12 
14 
16 
17 struct renderState_t;
18 
19 #define PRIM_DAT_SIZE 32
20 
21 // ============================================================
27 {
28 public:
29  void createLeaf(u_int32 *primIdx, int np, const triangle_t **prims, MemoryArena &arena)
30  {
31  primitives = 0;
32  flags = np << 2;
33  flags |= 3;
34  if(np>1)
35  {
36  primitives = (triangle_t **)arena.Alloc(np * sizeof(triangle_t *));
37  for(int i=0;i<np;i++) primitives[i] = (triangle_t *)prims[primIdx[i]];
38  Kd_prims+=np; //stat
39  }
40  else if(np==1)
41  {
42  onePrimitive = (triangle_t *)prims[primIdx[0]];
43  Kd_prims++; //stat
44  }
45  else _emptyKd_leaves++; //stat
46  Kd_leaves++; //stat
47  }
48  void createInterior(int axis, float d)
49  { division = d; flags = (flags & ~3) | axis; Kd_inodes++; }
50  float SplitPos() const { return division; }
51  int SplitAxis() const { return flags & 3; }
52  int nPrimitives() const { return flags >> 2; }
53  bool IsLeaf() const { return (flags & 3) == 3; }
54  u_int32 getRightChild() const { return (flags >> 2); }
55  void setRightChild(u_int32 i) { flags = (flags&3) | (i << 2); }
56 
57  union
58  {
59  float division;
62  };
64 };
65 
69 class boundEdge {
70 public:
71  boundEdge(){};
72  boundEdge(float position, int primitive, int bound_end):
73  pos(position), primNum(primitive), end(bound_end) {};
74  bool operator<(const boundEdge &e) const {
75  if (pos == e.pos)
76  return (int)end > (int)e.end;
77  else return pos < e.pos;
78  }
79  float pos;
80  int primNum;
81  int end;
82 };
83 
85 struct KdStack
86 {
87  const kdTreeNode *node;
88  float t;
90  int prev;
91 };
92 
93 struct KdToDo
94 {
95  const kdTreeNode *node;
96  float tmin, tmax;
97 };
98 
100 {
101 public:
103  int bestAxis;
105  float bestCost;
106  float oldCost;
107  float t;
109 };
110 
111 class bin_t
112 {
113  public:
114  bin_t(): n(0), c_left(0), c_right(0), c_bleft(0), c_both(0) {};
115  bool empty(){ return n==0; };
116  void reset(){n=0, c_left=0, c_right=0, c_both=0, c_bleft=0;};
117  int n;
120  float t;
121 };
122 
123 // ============================================================
128 {
129 public:
130  triKdTree_t(const triangle_t **v, int np, int depth=-1, int leafSize=2,
131  float cost_ratio=0.35, float emptyBonus=0.33);
132  bool Intersect(const ray_t &ray, float dist, triangle_t **tr, float &Z, intersectData_t &data) const;
133 // bool IntersectDBG(const ray_t &ray, float dist, triangle_t **tr, float &Z) const;
134  bool IntersectS(const ray_t &ray, float dist, triangle_t **tr, float shadow_bias) const;
135  bool IntersectTS(renderState_t &state, const ray_t &ray, int maxDepth, float dist, triangle_t **tr, color_t &filt, float shadow_bias) const;
136 // bool IntersectO(const point3d_t &from, const vector3d_t &ray, float dist, triangle_t **tr, float &Z) const;
137  bound_t getBound(){ return treeBound; }
138  ~triKdTree_t();
139 private:
140  void pigeonMinCost(u_int32 nPrims, bound_t &nodeBound, u_int32 *primIdx, splitCost_t &split);
141  void minimalCost(u_int32 nPrims, bound_t &nodeBound, u_int32 *primIdx,
142  const bound_t *allBounds, boundEdge *edges[3], splitCost_t &split);
143  int buildTree(u_int32 nPrims, bound_t &nodeBound, u_int32 *primNums,
144  u_int32 *leftPrims, u_int32 *rightPrims, boundEdge *edges[3],
145  u_int32 rightMemSize, int depth, int badRefines );
146 
147  float costRatio;
148  float eBonus;
149  u_int32 nextFreeNode, allocatedNodesCount, totalPrims;
150  int maxDepth;
151  unsigned int maxLeafSize;
152  bound_t treeBound;
153  MemoryArena primsArena;
154  kdTreeNode *nodes;
155 
156  // those are temporary actually, to keep argument counts bearable
157  const triangle_t **prims;
158  bound_t *allBounds;
159  int *clip; // indicate clip plane(s) for current level
160  char *cdata; // clipping data...
161 
162  // some statistics:
163  int depthLimitReached, NumBadSplits;
164 };
165 
166 
168 #endif //__Y_KDTREE_H
int bestAxis
Definition: kdtree.h:102
float division
interior: division plane position
Definition: kdtree.h:59
int c_left
Definition: kdtree.h:118
float t
Definition: kdtree.h:120
float tmax
Definition: kdtree.h:96
float SplitPos() const
Definition: kdtree.h:50
int nBelow
Definition: kdtree.h:108
int bestOffset
Definition: kdtree.h:104
triangle_t ** primitives
leaf: list of primitives
Definition: kdtree.h:60
#define __BEGIN_YAFRAY
float t
Definition: kdtree.h:107
int c_right
Definition: kdtree.h:118
float oldCost
Definition: kdtree.h:106
__BEGIN_YAFRAY typedef unsigned int u_int32
Definition: y_alloc.h:17
Definition: ray.h:11
__BEGIN_YAFRAY int Kd_inodes
Definition: kdtree.cc:53
Definition: kdtree.h:111
float pos
Definition: kdtree.h:79
bin_t()
Definition: kdtree.h:114
int nAbove
Definition: kdtree.h:108
bool empty()
Definition: kdtree.h:115
int end
Definition: kdtree.h:81
Definition: kdtree.h:93
Definition: color.h:49
bool IsLeaf() const
Definition: kdtree.h:53
splitCost_t()
Definition: kdtree.h:102
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
u_int32 getRightChild() const
Definition: kdtree.h:54
const kdTreeNode * node
pointer to far child
Definition: kdtree.h:87
int SplitAxis() const
Definition: kdtree.h:51
int nEdge
Definition: kdtree.h:108
bound_t getBound()
Definition: kdtree.h:137
const kdTreeNode * node
Definition: kdtree.h:95
point3d_t pb
the point coordinates of entry/exit point
Definition: kdtree.h:89
triangle_t * onePrimitive
leaf: direct inxex of one primitive
Definition: kdtree.h:61
__BEGIN_YAFRAY int _emptyKd_leaves
Definition: kdtree.cc:53
float tmin
Definition: kdtree.h:96
int c_bleft
Definition: kdtree.h:119
void reset()
Definition: kdtree.h:116
#define Z
Definition: tribox3_d.cc:25
#define YAFRAYCORE_EXPORT
__BEGIN_YAFRAY const int prims[50]
Definition: scr_halton.h:11
int n
Definition: kdtree.h:116
boundEdge()
Definition: kdtree.h:71
__BEGIN_YAFRAY int Kd_leaves
Definition: kdtree.cc:53
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
boundEdge(float position, int primitive, int bound_end)
Definition: kdtree.h:72
u_int32 flags
2bits: isLeaf, axis; 30bits: nprims (leaf) or index of right child
Definition: kdtree.h:63
int prev
the pointer to the previous stack item
Definition: kdtree.h:90
bool operator<(const boundEdge &e) const
Definition: kdtree.h:74
void * Alloc(u_int32 sz)
Definition: y_alloc.h:103
Definition: kdtree.h:85
#define __END_YAFRAY