1 | #ifndef _MeshKdTree_H__
|
---|
2 | #define _MeshKdTree_H__
|
---|
3 |
|
---|
4 | #include <functional>
|
---|
5 | //
|
---|
6 |
|
---|
7 | #include "Containers.h"
|
---|
8 | #include "AxisAlignedBox3.h"
|
---|
9 | #include "Ray.h"
|
---|
10 |
|
---|
11 | namespace GtpVisibilityPreprocessor {
|
---|
12 |
|
---|
13 | class MeshKdNode;
|
---|
14 | class MeshKdLeaf;
|
---|
15 | class MeshKdInterior;
|
---|
16 |
|
---|
17 | /** Abstract class for kd-tree node */
|
---|
18 | class MeshKdNode {
|
---|
19 | public:
|
---|
20 | MeshKdNode() {}
|
---|
21 |
|
---|
22 | /** Determines whether this node is a leaf or interior node
|
---|
23 | @return true if leaf
|
---|
24 | */
|
---|
25 | virtual bool IsLeaf() const = 0;
|
---|
26 | virtual ~MeshKdNode() {}
|
---|
27 | };
|
---|
28 |
|
---|
29 | /** Implementation of the kd-tree interior node */
|
---|
30 | class MeshKdInterior : public MeshKdNode {
|
---|
31 |
|
---|
32 | public:
|
---|
33 | MeshKdInterior():MeshKdNode(),
|
---|
34 | mBack(NULL), mFront(NULL) {}
|
---|
35 |
|
---|
36 | /** \sa KdNode::IsLeaf() */
|
---|
37 | virtual bool IsLeaf() const { return false; }
|
---|
38 |
|
---|
39 | /** splitting axis */
|
---|
40 | int mAxis;
|
---|
41 | /** splitting position, absolute position within the bounding box of this node */
|
---|
42 | float mPosition;
|
---|
43 |
|
---|
44 | /** back node */
|
---|
45 | MeshKdNode *mBack;
|
---|
46 | /** front node */
|
---|
47 | MeshKdNode *mFront;
|
---|
48 |
|
---|
49 | void SetupChildLinks(MeshKdNode *b, MeshKdNode *f) {
|
---|
50 | mBack = b;
|
---|
51 | mFront = f;
|
---|
52 | }
|
---|
53 |
|
---|
54 | void ReplaceChildLink(MeshKdNode *oldChild, MeshKdNode *newChild) {
|
---|
55 | if (mBack == oldChild)
|
---|
56 | mBack = newChild;
|
---|
57 | else
|
---|
58 | mFront = newChild;
|
---|
59 | }
|
---|
60 |
|
---|
61 | ~MeshKdInterior() {
|
---|
62 | delete mBack;
|
---|
63 | delete mFront;
|
---|
64 | }
|
---|
65 | };
|
---|
66 |
|
---|
67 |
|
---|
68 | /** Implementation of the kd-tree leaf node */
|
---|
69 | class MeshKdLeaf : public MeshKdNode {
|
---|
70 | public:
|
---|
71 | MeshKdLeaf():MeshKdNode() {
|
---|
72 | }
|
---|
73 |
|
---|
74 | MeshKdLeaf(const vector<int> &faces):MeshKdNode() {
|
---|
75 | mFaces = faces;
|
---|
76 | }
|
---|
77 |
|
---|
78 | /** \sa KdNode::IsLeaf() */
|
---|
79 | virtual bool IsLeaf() const { return true; }
|
---|
80 |
|
---|
81 | /** indices of contained faces */
|
---|
82 | vector<int> mFaces;
|
---|
83 |
|
---|
84 | };
|
---|
85 |
|
---|
86 |
|
---|
87 |
|
---|
88 | /** KdTree for indexing scene entities - occluders/occludees/viewcells */
|
---|
89 | class MeshKdTree {
|
---|
90 |
|
---|
91 | protected:
|
---|
92 | struct TraversalData
|
---|
93 | {
|
---|
94 | MeshKdNode *mNode;
|
---|
95 | MeshKdInterior *mParent;
|
---|
96 | AxisAlignedBox3 mBox;
|
---|
97 | int mDepth;
|
---|
98 | float mPriority;
|
---|
99 |
|
---|
100 | TraversalData() {}
|
---|
101 |
|
---|
102 | TraversalData(MeshKdNode *n, const float p):
|
---|
103 | mNode(n), mPriority(p)
|
---|
104 | {}
|
---|
105 |
|
---|
106 | TraversalData(MeshKdNode *n,
|
---|
107 | MeshKdInterior *p,
|
---|
108 | const AxisAlignedBox3 &b,
|
---|
109 | const int d):
|
---|
110 | mNode(n), mParent(p), mBox(b), mDepth(d) {}
|
---|
111 |
|
---|
112 |
|
---|
113 | bool operator<(
|
---|
114 | const TraversalData &b) const {
|
---|
115 | MeshKdLeaf *leafa = (MeshKdLeaf *) mNode;
|
---|
116 | MeshKdLeaf *leafb = (MeshKdLeaf *) b.mNode;
|
---|
117 | return
|
---|
118 | leafa->mFaces.size()*mBox.SurfaceArea()
|
---|
119 | <
|
---|
120 | leafb->mFaces.size()*b.mBox.SurfaceArea();
|
---|
121 | }
|
---|
122 |
|
---|
123 | };
|
---|
124 |
|
---|
125 |
|
---|
126 |
|
---|
127 | public:
|
---|
128 |
|
---|
129 | enum {
|
---|
130 | SPLIT_OBJECT_MEDIAN,
|
---|
131 | SPLIT_SPATIAL_MEDIAN,
|
---|
132 | SPLIT_SAH};
|
---|
133 |
|
---|
134 |
|
---|
135 | MeshKdTree(Mesh *mesh);
|
---|
136 | ~MeshKdTree();
|
---|
137 |
|
---|
138 | virtual bool Construct();
|
---|
139 |
|
---|
140 | /** Check whether subdivision criteria are met for the given subtree.
|
---|
141 | If not subdivide the leafs of the subtree. The criteria are specified in
|
---|
142 | the environment as well as the subdivision method. By default surface area
|
---|
143 | heuristics is used.
|
---|
144 |
|
---|
145 | @param subtree root of the subtree
|
---|
146 |
|
---|
147 | @return true if subdivision was performed, false if subdivision criteria
|
---|
148 | were already met
|
---|
149 | */
|
---|
150 | virtual MeshKdNode *Subdivide(const TraversalData &tdata);
|
---|
151 |
|
---|
152 | /** Get the root of the tree
|
---|
153 | */
|
---|
154 | MeshKdNode *GetRoot() const;
|
---|
155 |
|
---|
156 | AxisAlignedBox3 GetBox() const;
|
---|
157 |
|
---|
158 | int
|
---|
159 | CastRay(
|
---|
160 | Ray &ray,
|
---|
161 | MeshInstance *instance
|
---|
162 | );
|
---|
163 |
|
---|
164 |
|
---|
165 | protected:
|
---|
166 |
|
---|
167 | struct RayTraversalData {
|
---|
168 | MeshKdNode *mNode;
|
---|
169 | Vector3 mExitPoint;
|
---|
170 | float mMaxT;
|
---|
171 |
|
---|
172 | RayTraversalData() {}
|
---|
173 | RayTraversalData(MeshKdNode *n,
|
---|
174 | const Vector3 &p,
|
---|
175 | const float maxt):
|
---|
176 | mNode(n), mExitPoint(p), mMaxT(maxt) {}
|
---|
177 | };
|
---|
178 |
|
---|
179 | // --------------------------------------------------------------
|
---|
180 | // For sorting objects
|
---|
181 | // --------------------------------------------------------------
|
---|
182 | struct SortableEntry
|
---|
183 | {
|
---|
184 | enum {
|
---|
185 | FACE_MIN,
|
---|
186 | FACE_MAX
|
---|
187 | };
|
---|
188 |
|
---|
189 | int type;
|
---|
190 | float value;
|
---|
191 | int face;
|
---|
192 |
|
---|
193 | SortableEntry() {}
|
---|
194 | SortableEntry(const int t, const float v, const int f):type(t),
|
---|
195 | value(v),
|
---|
196 | face(f) {}
|
---|
197 |
|
---|
198 | bool operator<(const SortableEntry &b) const {
|
---|
199 | return value < b.value;
|
---|
200 | }
|
---|
201 |
|
---|
202 | };
|
---|
203 |
|
---|
204 |
|
---|
205 | float
|
---|
206 | BestCostRatio(
|
---|
207 | MeshKdLeaf *node,
|
---|
208 | const AxisAlignedBox3 &box,
|
---|
209 | const int axis,
|
---|
210 | float &position,
|
---|
211 | int &objectsBack,
|
---|
212 | int &objectsFront
|
---|
213 | );
|
---|
214 |
|
---|
215 | void
|
---|
216 | SortSubdivisionCandidates(
|
---|
217 | MeshKdLeaf *node,
|
---|
218 | const int axis
|
---|
219 | );
|
---|
220 |
|
---|
221 | MeshKdNode *
|
---|
222 | SubdivideNode(
|
---|
223 | MeshKdLeaf *leaf,
|
---|
224 | MeshKdInterior *parent,
|
---|
225 | const AxisAlignedBox3 &box,
|
---|
226 | const int depth,
|
---|
227 | AxisAlignedBox3 &backBBox,
|
---|
228 | AxisAlignedBox3 &frontBBox
|
---|
229 | );
|
---|
230 |
|
---|
231 | bool
|
---|
232 | TerminationCriteriaMet(const MeshKdLeaf *leaf, const int depth);
|
---|
233 |
|
---|
234 | int
|
---|
235 | SelectPlane(MeshKdLeaf *leaf,
|
---|
236 | const AxisAlignedBox3 &box,
|
---|
237 | float &position
|
---|
238 | );
|
---|
239 |
|
---|
240 | /// pointer to the mesh owning the tree
|
---|
241 | Mesh *mMesh;
|
---|
242 |
|
---|
243 | /// root of the tree
|
---|
244 | MeshKdNode *mRoot;
|
---|
245 |
|
---|
246 | /// reusable array of split candidates
|
---|
247 | vector<SortableEntry> *mSubdivisionCandidates;
|
---|
248 |
|
---|
249 | public:
|
---|
250 | static void ParseEnvironment();
|
---|
251 | static float mSplitBorder;
|
---|
252 | static int mTermMaxDepth;
|
---|
253 | static int mTermMinCost;
|
---|
254 | static float mMaxCostRatio;
|
---|
255 | static float mCt_div_ci;
|
---|
256 | static int mSplitMethod;
|
---|
257 |
|
---|
258 | };
|
---|
259 |
|
---|
260 |
|
---|
261 |
|
---|
262 | }
|
---|
263 |
|
---|
264 |
|
---|
265 | #endif
|
---|