775a216fba8ef51401d52c3b92cd71defae457df
[blender.git] / intern / elbeem / intern / ntl_bsptree.h
1 /** \file elbeem/intern/ntl_bsptree.h
2  *  \ingroup elbeem
3  */
4 /******************************************************************************
5  *
6  * El'Beem - Free Surface Fluid Simulation with the Lattice Boltzmann Method
7  * Copyright 2003-2006 Nils Thuerey
8  *
9  * Tree container for fast triangle intersects
10  *
11  *****************************************************************************/
12 #ifndef NTL_TREE_H
13 #define NTL_TREE_H
14
15 #include "ntl_vector3dim.h"
16 #include "ntl_ray.h"
17
18
19 #define AXIS_X 0
20 #define AXIS_Y 1
21 #define AXIS_Z 2
22
23 #define BSP_STACK_SIZE 50
24
25
26 //! bsp tree stack classes, defined in ntl_bsptree.cpp,
27 //  detailed definition unnecesseary here
28 class BSPNode;
29 class BSPStackElement;
30 class BSPStack;
31 class TriangleBBox;
32 class ntlScene;
33 class ntlTriangle;
34
35
36 //! Class for a bsp tree for triangles
37 class ntlTree
38 {
39         public:
40
41                 //! Default constructor
42                 ntlTree();
43                 //! Constructor with init
44                 ntlTree(int depth, int objnum, ntlScene *scene, int triFlagMask);
45                 //! Destructor
46                 ~ntlTree();
47
48                 //! subdivide tree
49                 void subdivide(BSPNode *node, int depth, int axis);
50
51                 //! intersect ray with BSPtree
52                 void intersect(const ntlRay &ray, gfxReal &distance, ntlVec3Gfx &normal, ntlTriangle *&tri, int flags, bool forceNonsmooth) const;
53                 //! intersect along +X ray
54                 void intersectX(const ntlRay &ray, gfxReal &distance, ntlVec3Gfx &normal, ntlTriangle *&tri, int flags, bool forceNonsmooth) const;
55
56                 //! Returns number of nodes
57                 int getCurrentNodes( void ) { return mCurrentNodes; }
58
59         protected:
60
61                 // check if a triangle is in a node
62                 bool checkAABBTriangle(ntlVec3Gfx &min, ntlVec3Gfx &max, ntlTriangle *tri);
63
64
65                 // VARs
66
67                 //! distance to plane function for nodes
68                 gfxReal distanceToPlane(BSPNode *curr, ntlVec3Gfx plane, ntlRay ray) const;
69
70                 //! return ordering of children nodes relatice to origin point
71                 void getChildren(BSPNode *curr, ntlVec3Gfx origin, BSPNode *&node_near, BSPNode *&node_far) const;
72
73                 //! delete a node of the tree with all sub nodes, dont delete root members
74                 void deleteNode(BSPNode *curr);
75
76                 //inline bool isLeaf(BSPNode *node) const { return (node->child[0] == NULL); }
77
78
79                 //! AABB for tree
80                 ntlVec3Gfx mStart,mEnd;
81
82                 //! maximum depth of tree
83                 int mMaxDepth;
84
85                 //! maximum number of objects in one node
86                 int mMaxListLength;
87
88                 //! root node pointer
89                 BSPNode *mpRoot;
90                 //! count no. of node
91                 int mNumNodes;
92                 int mAbortSubdiv;
93
94                 //! stack for the node pointers
95                 BSPStack *mpNodeStack;
96                 //stack<BSPNode *> nodestack;
97
98                 //! pointer to vertex array
99                 vector<ntlVec3Gfx> *mpVertices;
100
101                 //! pointer to vertex array
102                 vector<ntlVec3Gfx> *mpVertNormals;
103
104                 //! vector for all the triangles
105                 vector<ntlTriangle> *mpTriangles;
106                 vector<ntlTriangle *> *mppTriangles;
107
108                 //! temporary array for triangle distribution to nodes
109                 char *mpTriDist;
110
111                 //! temporary array for triangle bounding boxes
112                 TriangleBBox *mpTBB;
113
114                 //! triangle mask - include only triangles that match mask
115                 int mTriangleMask;
116
117                 //! Status vars (max depth, # of current nodes)
118                 int mCurrentDepth, mCurrentNodes;
119
120                 //! duplicated triangles, inited during subdivide 
121                 int mTriDoubles; 
122
123 };
124
125
126 #endif
127
128