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