[221] | 1 | #ifndef _ViewCellBsp_H__ |
---|
| 2 | #define _ViewCellBsp_H__ |
---|
| 3 | |
---|
| 4 | #include "Mesh.h" |
---|
[224] | 5 | #include "Containers.h" |
---|
[225] | 6 | #include <queue> |
---|
[233] | 7 | #include <stack> |
---|
[224] | 8 | |
---|
[221] | 9 | class ViewCell; |
---|
| 10 | class Plane3; |
---|
| 11 | //class Mesh; |
---|
| 12 | |
---|
| 13 | //namespace GtpVisibilityPreprocessor { |
---|
[224] | 14 | class BspTree; |
---|
[221] | 15 | class BspInterior; |
---|
[235] | 16 | class Polygon3; |
---|
[221] | 17 | |
---|
[235] | 18 | /** Queue storing a soup of polygons used during BSP tree construction |
---|
| 19 | */ |
---|
| 20 | typedef std::queue<Polygon3 *> PolygonQueue; |
---|
[224] | 21 | |
---|
[234] | 22 | class BspTreeStatistics // TODO: should have common superclass with KdTreeStatistics |
---|
| 23 | { |
---|
| 24 | public: |
---|
| 25 | // total number of nodes |
---|
| 26 | int nodes; |
---|
[235] | 27 | // number of splits |
---|
| 28 | int splits; |
---|
[234] | 29 | // totals number of rays |
---|
| 30 | int rays; |
---|
[235] | 31 | // maximal reached depth |
---|
| 32 | int maxDepth; |
---|
[234] | 33 | // total number of query domains |
---|
| 34 | int queryDomains; |
---|
| 35 | // total number of ray references |
---|
| 36 | int rayRefs; |
---|
| 37 | // refs in non empty leafs |
---|
| 38 | int rayRefsNonZeroQuery; |
---|
| 39 | // total number of query references |
---|
| 40 | int objectRefs; |
---|
| 41 | // nodes with zero queries |
---|
| 42 | int zeroQueryNodes; |
---|
| 43 | // max depth nodes |
---|
| 44 | int maxDepthNodes; |
---|
| 45 | // max number of rays per node |
---|
| 46 | int maxObjectRefs; |
---|
| 47 | // number of dynamically added ray refs |
---|
| 48 | int addedRayRefs; |
---|
| 49 | // number of dynamically removed ray refs |
---|
| 50 | int removedRayRefs; |
---|
| 51 | |
---|
| 52 | // Constructor |
---|
| 53 | BspTreeStatistics() |
---|
| 54 | { |
---|
[235] | 55 | Reset(); |
---|
[234] | 56 | } |
---|
| 57 | |
---|
| 58 | int Nodes() const {return nodes;} |
---|
| 59 | int Interior() const { return nodes/2; } |
---|
| 60 | int Leaves() const { return (nodes/2) + 1; } |
---|
| 61 | |
---|
| 62 | void Reset() |
---|
| 63 | { |
---|
| 64 | nodes = 0; |
---|
[235] | 65 | splits = 0; |
---|
[234] | 66 | rays = queryDomains = 0; |
---|
| 67 | rayRefs = rayRefsNonZeroQuery = objectRefs = 0; |
---|
| 68 | zeroQueryNodes = 0; |
---|
| 69 | maxDepthNodes = 0; |
---|
| 70 | //minCostNodes = 0; |
---|
| 71 | maxObjectRefs = 0; |
---|
| 72 | addedRayRefs = removedRayRefs = 0; |
---|
| 73 | } |
---|
| 74 | |
---|
| 75 | void |
---|
| 76 | Print(ostream &app) const; |
---|
| 77 | |
---|
| 78 | friend ostream &operator<<(ostream &s, const BspTreeStatistics &stat) { |
---|
| 79 | stat.Print(s); |
---|
| 80 | return s; |
---|
| 81 | } |
---|
| 82 | |
---|
| 83 | }; |
---|
| 84 | |
---|
[233] | 85 | /** |
---|
| 86 | BspNode abstract class serving for interior and leaf node implementation |
---|
| 87 | */ |
---|
| 88 | class BspNode |
---|
| 89 | { |
---|
| 90 | friend BspTree; |
---|
[221] | 91 | |
---|
[233] | 92 | public: |
---|
[235] | 93 | BspNode(); |
---|
| 94 | BspNode(BspInterior *parent); |
---|
| 95 | |
---|
[233] | 96 | /** Determines whether this node is a leaf or not |
---|
| 97 | @return true if leaf |
---|
| 98 | */ |
---|
| 99 | virtual bool IsLeaf() const = 0; |
---|
[221] | 100 | |
---|
[233] | 101 | /** Determines whether this node is a root |
---|
| 102 | @return true if root |
---|
| 103 | */ |
---|
| 104 | virtual bool IsRoot() const; |
---|
[221] | 105 | |
---|
[233] | 106 | /** Returns parent node. |
---|
| 107 | */ |
---|
| 108 | BspInterior *GetParent(); |
---|
[235] | 109 | /** Sets parent node. |
---|
| 110 | */ |
---|
| 111 | void SetParent(BspInterior *parent); |
---|
| 112 | |
---|
[233] | 113 | protected: |
---|
[221] | 114 | |
---|
[233] | 115 | /// parent of this node |
---|
| 116 | BspInterior *mParent; |
---|
| 117 | }; |
---|
[221] | 118 | |
---|
[233] | 119 | /** BSP interior node implementation |
---|
| 120 | */ |
---|
| 121 | class BspInterior : public BspNode |
---|
| 122 | { |
---|
| 123 | public: |
---|
| 124 | /** Standard contructor taking split plane as argument. |
---|
| 125 | */ |
---|
| 126 | BspInterior(Plane3 plane); |
---|
| 127 | /** @return false since it is an interior node |
---|
| 128 | */ |
---|
| 129 | bool IsLeaf() const; |
---|
[222] | 130 | |
---|
[233] | 131 | BspNode *GetBack(); |
---|
| 132 | BspNode *GetFront(); |
---|
[221] | 133 | |
---|
[233] | 134 | Plane3 *GetPlane(); |
---|
[221] | 135 | |
---|
[233] | 136 | void ReplaceChildLink(BspNode *oldChild, BspNode *newChild); |
---|
| 137 | void SetupChildLinks(BspNode *b, BspNode *f); |
---|
[225] | 138 | |
---|
[233] | 139 | /** Splits polygons. |
---|
| 140 | @param polys the polygons to be split |
---|
| 141 | @param frontPolys returns the polygons in the front of the split plane |
---|
| 142 | @param backPolys returns the polygons in the back of the split plane |
---|
[235] | 143 | @param splits number of splits |
---|
[233] | 144 | */ |
---|
[235] | 145 | void SplitPolygons(PolygonQueue *polys, PolygonQueue *frontPolys, PolygonQueue *backPolys, int &splits); |
---|
[225] | 146 | |
---|
[233] | 147 | protected: |
---|
| 148 | |
---|
| 149 | /// Splitting plane corresponding to this node |
---|
| 150 | Plane3 mPlane; |
---|
| 151 | /// back node |
---|
| 152 | BspNode *mBack; |
---|
| 153 | /// front node |
---|
| 154 | BspNode *mFront; |
---|
| 155 | }; |
---|
[225] | 156 | |
---|
| 157 | |
---|
[233] | 158 | /** BSP leaf node implementation */ |
---|
| 159 | class BspLeaf : public BspNode |
---|
| 160 | { |
---|
| 161 | public: |
---|
| 162 | BspLeaf(ViewCell *viewCell = NULL); |
---|
[225] | 163 | |
---|
[233] | 164 | /** @return true since it is an interior node */ |
---|
| 165 | bool IsLeaf() const; |
---|
| 166 | ViewCell *GetViewCell(); |
---|
[225] | 167 | |
---|
[233] | 168 | protected: |
---|
[225] | 169 | |
---|
[233] | 170 | /// polygonal representation of this viewcell |
---|
| 171 | /// if NULL this note does not correspond to feasible viewcell |
---|
| 172 | ViewCell *mViewCell; |
---|
| 173 | }; |
---|
[225] | 174 | |
---|
| 175 | |
---|
[233] | 176 | /** Implementation of the ViewCell BSP tree. */ |
---|
| 177 | class BspTree |
---|
| 178 | { |
---|
| 179 | public: |
---|
| 180 | |
---|
| 181 | /** Additional data which is passed down the BSP tree during traversal. |
---|
| 182 | */ |
---|
| 183 | struct BspTraversalData |
---|
| 184 | { |
---|
| 185 | /// the current node |
---|
| 186 | BspNode *mNode; |
---|
| 187 | /// parent of current node |
---|
| 188 | BspInterior *mParent; |
---|
| 189 | /// polygonal data for splitting |
---|
[235] | 190 | PolygonQueue *mPolygons; |
---|
[233] | 191 | /// current depth |
---|
| 192 | int mDepth; |
---|
| 193 | |
---|
| 194 | BspTraversalData() {} |
---|
| 195 | |
---|
| 196 | BspTraversalData(BspNode *node, BspInterior *parent, PolygonQueue *polys, const int depth): |
---|
[235] | 197 | mNode(node), mParent(parent), mPolygons(polys), mDepth(depth) {} |
---|
[233] | 198 | }; |
---|
| 199 | |
---|
| 200 | typedef std::stack<BspTraversalData> BspTraversalStack; |
---|
| 201 | |
---|
[235] | 202 | /// BSP tree construction type |
---|
| 203 | enum {VIEWCELLS, SCENE_GEOMETRY}; |
---|
| 204 | |
---|
| 205 | /** Default constructor creating an empty tree. |
---|
[233] | 206 | */ |
---|
[235] | 207 | BspTree(); |
---|
[233] | 208 | |
---|
| 209 | ~BspTree(); |
---|
| 210 | |
---|
[235] | 211 | const BspTreeStatistics &GetStatistics() const; |
---|
| 212 | |
---|
| 213 | /** Constructs tree using the given list of viewcells.
|
---|
| 214 | A pointer to the appropriate viewcell is stored within each leaf.
|
---|
| 215 | Many leafs can point to the same viewcell.
|
---|
| 216 | */
|
---|
| 217 | void Construct(const ViewCellContainer &viewCells);
|
---|
| 218 | /** Constructs tree using the given list of objects. Each leaf is taken as viewcell.
|
---|
| 219 | No objects are treated as viewcells explicitly.
|
---|
| 220 |
|
---|
| 221 | @param objects list of objects
|
---|
| 222 | */
|
---|
| 223 | void Construct(const ObjectContainer &objects); |
---|
| 224 | |
---|
| 225 | |
---|
[233] | 226 | protected: |
---|
[235] | 227 | void EvaluateLeafStats(const BspTraversalData &data); |
---|
| 228 | |
---|
| 229 | /** Subdivides node with respect to the traversal data. |
---|
| 230 | @param tStack current traversal stack |
---|
| 231 | @param tData traversal data also holding node to be subdivided |
---|
| 232 | @param viewCell the view cell that will be represented with this part of the Bsp tree. |
---|
[233] | 233 | */ |
---|
[235] | 234 | void Subdivide(BspTraversalStack &tStack, BspTraversalData &tData, ViewCell *viewCell = NULL); |
---|
[233] | 235 | |
---|
[235] | 236 | /** Selects a splitting plane. |
---|
| 237 | @param polyQueue the polygon data on which the split decition is based |
---|
[233] | 238 | */ |
---|
| 239 | Plane3 SelectPlane(PolygonQueue *polyQueue); |
---|
[224] | 240 |
|
---|
[233] | 241 | /** Filters next viewcell down the tree and inserts it into the appropriate leaves
|
---|
| 242 | (i.e., possibly more than one leaf).
|
---|
| 243 | */
|
---|
[235] | 244 | void InsertViewCell(ViewCell *viewCell); |
---|
[233] | 245 |
|
---|
[235] | 246 | /** Subdivide leaf.
|
---|
[233] | 247 | @param leaf the leaf to be subdivided
|
---|
| 248 | @param parent the parent node of this leaf
|
---|
| 249 | @param polys the input polygons
|
---|
| 250 | @param depth the current tree depth
|
---|
| 251 | @param frontPolys the polygons of the front child node as a result from splitting
|
---|
| 252 | @param backPolys the polygons of the back child node as a result from splitting
|
---|
| 253 | */
|
---|
| 254 | BspNode *SubdivideNode(BspLeaf *leaf, BspInterior *parent,
|
---|
| 255 | PolygonQueue *polys, const int depth,
|
---|
| 256 | ViewCell *viewCell,
|
---|
| 257 | PolygonQueue *frontPolys, PolygonQueue *backPolys); |
---|
[221] | 258 | |
---|
[233] | 259 | /** Filters polygons down the tree. |
---|
| 260 | @param node the current BSP node |
---|
| 261 | @param polys the polygons to be filtered |
---|
| 262 | @param frontPolys returns the polygons in front of the split plane |
---|
| 263 | @param backPolys returns the polygons in the back of the split plane |
---|
| 264 | */ |
---|
[235] | 265 | void FilterPolygons(BspInterior *node, PolygonQueue *polys, |
---|
| 266 | PolygonQueue *frontPolys, PolygonQueue *backPolys); |
---|
[224] | 267 | |
---|
[235] | 268 | /** Extracts the meshes of the objects and copies them into the mesh. |
---|
[233] | 269 | */ |
---|
| 270 | static void Copy2PolygonSoup(const ObjectContainer &objects, PolygonQueue &polys); |
---|
[224] | 271 | |
---|
[235] | 272 | /** copy this mesh into polygons. |
---|
| 273 | */ |
---|
| 274 | static void CopyMesh2Polygons(Mesh *mesh, PolygonQueue &polys); |
---|
[233] | 275 | |
---|
| 276 | /// Pointer to the root of the tree |
---|
| 277 | BspNode *mRoot; |
---|
| 278 | /// Pointer to the root cell of the viewspace |
---|
| 279 | // ViewCell *mRootCell; |
---|
[235] | 280 | |
---|
| 281 | |
---|
| 282 | BspTreeStatistics mStat; |
---|
[234] | 283 | |
---|
[235] | 284 | /// local maximal polygons (changes depending on method) |
---|
| 285 | int mTermMaxPolygons; |
---|
| 286 | int mTermMaxDepth; |
---|
| 287 | |
---|
| 288 | public: |
---|
| 289 | /// Parses the environment and stores the global BSP tree parameters |
---|
| 290 | static void ParseEnvironment(); |
---|
| 291 | |
---|
| 292 | /// maximal number of polygons where tree construction is terminated |
---|
| 293 | static int sTermMaxPolygons; |
---|
| 294 | /// maximal possible depth |
---|
| 295 | static int sTermMaxDepth; |
---|
[233] | 296 | }; |
---|
| 297 | |
---|
[221] | 298 | //}; // GtpVisibilityPreprocessor |
---|
| 299 | |
---|
| 300 | #endif |
---|