source: trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h @ 225

Revision 225, 5.2 KB checked in by mattausch, 19 years ago (diff)

updated bsp trees

Line 
1#ifndef _ViewCellBsp_H__
2#define _ViewCellBsp_H__
3
4#include "Mesh.h"
5#include "Containers.h"
6#include <queue>
7
8class ViewCell;
9class Plane3;
10//class Mesh;
11
12//namespace GtpVisibilityPreprocessor {
13class BspTree; 
14class BspInterior;
15class Polygon;
16
17  /**
18     BspNode abstract class serving for interior and leaf node implementation
19  */
20  class BspNode
21  {
22          friend BspTree;
23
24  public:
25          /** Determines whether this node is a leaf or not
26          @return true if leaf
27          */
28          virtual bool IsLeaf() const = 0;
29   
30          /** Determines whether this node is a root
31          @return true if root
32          */
33          virtual bool IsRoot() const;
34
35          /** Returns parent node.
36          */
37          BspInterior *GetParent();
38         
39  protected:
40
41          /// parent of this node
42          BspInterior *mParent;
43  };
44
45  /** BSP interior node implementation
46  */
47  class BspInterior : public BspNode
48  {
49  public:
50          /** Standard contructor taking split plane as argument.
51          */
52          BspInterior(Plane3 plane);
53          /** @return false since it is an interior node
54          */
55          bool IsLeaf() const;
56
57          BspNode *GetBack();
58          BspNode *GetFront();
59
60          Plane3 *GetPlane();
61
62          void ReplaceChildLink(BspNode *oldChild, BspNode *newChild);
63          void SetupChildLinks(BspNode *b, BspNode *f);
64
65  protected:
66               
67          /// Splitting plane corresponding to this node
68          Plane3 mPlane;
69          /// back node
70          BspNode *mBack;
71          /// front node
72          BspNode *mFront;
73  };
74 
75 
76  /** BSP leaf node implementation */
77  class BspLeaf : public BspNode
78  {
79  public:
80          BspLeaf(ViewCell *viewCell = NULL);
81   
82          /** @return true since it is an interior node */
83          bool IsLeaf() const;
84          ViewCell *GetViewCell();
85
86  protected:
87   
88          /// polygonal representation of this viewcell
89          /// if NULL this note does not correspond to feasible viewcell
90          ViewCell *mViewCell;
91  };
92 
93  typedef std::queue<Polygon *> PolygonQueue;
94
95  /** Class representing a polygon.
96  */
97  class Polygon
98  {
99  public:
100          Polygon();
101          Polygon(const VertexContainer &vertices);
102
103          /** Copies all the vertices of the face.
104          */
105          Polygon(Face *face, Mesh *parent);
106         
107           /** Returns supporting plane of this polygon.
108          */
109          Plane3 GetSupportingPlane();
110
111          /** Splits polygon.
112                  @param partition the split plane
113                  @param front the front polygon
114                  @param back the back polygon
115          */
116          void Split(Plane3 *partition, Polygon *front, Polygon *back);
117
118          enum {BACK_SIDE, FRONT_SIDE, SPLIT, COINCIDENT};
119
120          /** Side of the plane where the polygon is located.
121              @returns one of BACK_SIDE, FRONT_SIDE, SPLIT, COINCIDENT
122          */
123          int Side(Plane3 *plane);
124
125          static void DeletePolygons(PolygonQueue *polys);
126
127          /// vertices are connected in counterclockwise order.
128          VertexContainer mVertices;
129  };
130
131  /** Implementation of the ViewCell BSP tree. */
132  class BspTree
133  {
134  public:
135                 
136          /** Additional data which is passed down the BSP tree during traversal.
137          */
138          struct BspTraversalData
139          { 
140                  /// the current node
141                  BspNode *mNode;
142                  /// parent of current node
143                  BspInterior *mParent;
144                  /// polygonal data for splitting
145                  PolygonQueue *mPolys;
146                  /// current depth
147                  int mDepth;
148                     
149                  BspTraversalData() {}
150                 
151                  BspTraversalData(BspNode *node, BspInterior *parent, PolygonQueue *polys, const int depth):
152                  mNode(node), mParent(parent), mPolys(polys), mDepth(depth) {}
153      };
154
155
156          /** Constructs BSP tree from list of view cells.
157          */
158          BspTree(const ViewCellContainer &viewCells);
159          /** Constructs BSP tree from list of objects.
160                  @param object list of intersectables
161                  @param maxPolys maximal allowed number of polygons
162                  @param maxDepth maximal allowed BSP tree depth
163          */
164          BspTree(const ObjectContainer &objects, int maxPolys, int maxDepth);
165 
166          ~BspTree();
167
168  protected:
169          /** Selects a splitting plane from the given polygons.
170          */
171          Plane3 SelectPlane(PolygonQueue *polyQueue);
172
173          /** Filters next viewcell down the tree and inserts it into the appropriate leaves
174                  (i.e., possibly more than one leaf).
175          */
176          void InsertViewCell(ViewCell *viewCell);
177
178          /** Subdivides tree according to the given list of viewcells.
179          */
180          void Subdivide(const ViewCellContainer &viewCells);
181          /** Subdivides tree according to the given list of objects.
182          */
183          void Subdivide(const ObjectContainer &objects);
184           
185          /** Subdivides leaf.
186                  @param leaf the leaf to be subdivided
187                  @param parent the parent node of this leaf
188                  @param polys the input polygons
189                  @param depth the current tree depth
190                  @param frontPolys the polygons of the front child node as a result from splitting
191                  @param backPolys the polygons of the back child node as a result from splitting
192          */
193          BspNode *SubdivideNode(BspLeaf *leaf, BspInterior *parent,
194                                                         PolygonQueue *polys, const int depth,
195                                                         PolygonQueue *frontPolys, PolygonQueue *backPolys);
196
197          /** Extracts the mesh instances of the objects and copies them into the mesh.
198          */
199          static void Copy2PolygonSoup(const ObjectContainer &objects, PolygonQueue &polys);
200
201          static void CopyMesh2Polygon(Mesh *mesh, PolygonQueue &polys);
202
203          /// Pointer to the root of the tree
204          BspNode *mRoot;
205          /// Pointer to the root cell of the viewspace
206          // ViewCell *mRootCell;
207          /// maximal number of polygons allowed in leaf
208          int mMaxPolys;
209          /// maximal depth
210          int mMaxDepth;
211  };
212 
213//}; // GtpVisibilityPreprocessor
214
215#endif
Note: See TracBrowser for help on using the repository browser.