Merge branch 'master' into blender2.8
[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 #ifdef WITH_CXX_GUARDEDALLOC
26 #  include "MEM_guardedalloc.h"
27 #endif
28
29 //! bsp tree stack classes, defined in ntl_bsptree.cpp,
30 //  detailed definition unnecesseary here
31 class BSPNode;
32 class BSPStackElement;
33 class BSPStack;
34 class TriangleBBox;
35 class ntlScene;
36 class ntlTriangle;
37
38
39 //! Class for a bsp tree for triangles
40 class ntlTree
41 {
42         public:
43
44                 //! Default constructor
45                 ntlTree();
46                 //! Constructor with init
47                 ntlTree(int depth, int objnum, ntlScene *scene, int triFlagMask);
48                 //! Destructor
49                 ~ntlTree();
50
51                 //! subdivide tree
52                 void subdivide(BSPNode *node, int depth, int axis);
53
54                 //! intersect ray with BSPtree
55                 void intersect(const ntlRay &ray, gfxReal &distance, ntlVec3Gfx &normal, ntlTriangle *&tri, int flags, bool forceNonsmooth) const;
56                 //! intersect along +X ray
57                 void intersectX(const ntlRay &ray, gfxReal &distance, ntlVec3Gfx &normal, ntlTriangle *&tri, int flags, bool forceNonsmooth) const;
58
59                 //! Returns number of nodes
60                 int getCurrentNodes( void ) { return mCurrentNodes; }
61
62         protected:
63
64                 // check if a triangle is in a node
65                 bool checkAABBTriangle(ntlVec3Gfx &min, ntlVec3Gfx &max, ntlTriangle *tri);
66
67
68                 // VARs
69
70                 //! distance to plane function for nodes
71                 gfxReal distanceToPlane(BSPNode *curr, ntlVec3Gfx plane, ntlRay ray) const;
72
73                 //! return ordering of children nodes relatice to origin point
74                 void getChildren(BSPNode *curr, ntlVec3Gfx origin, BSPNode *&node_near, BSPNode *&node_far) const;
75
76                 //! delete a node of the tree with all sub nodes, dont delete root members
77                 void deleteNode(BSPNode *curr);
78
79                 //inline bool isLeaf(BSPNode *node) const { return (node->child[0] == NULL); }
80
81
82                 //! AABB for tree
83                 ntlVec3Gfx mStart,mEnd;
84
85                 //! maximum depth of tree
86                 int mMaxDepth;
87
88                 //! maximum number of objects in one node
89                 int mMaxListLength;
90
91                 //! root node pointer
92                 BSPNode *mpRoot;
93                 //! count no. of node
94                 int mNumNodes;
95                 int mAbortSubdiv;
96
97                 //! stack for the node pointers
98                 BSPStack *mpNodeStack;
99                 //stack<BSPNode *> nodestack;
100
101                 //! pointer to vertex array
102                 vector<ntlVec3Gfx> *mpVertices;
103
104                 //! pointer to vertex array
105                 vector<ntlVec3Gfx> *mpVertNormals;
106
107                 //! vector for all the triangles
108                 vector<ntlTriangle> *mpTriangles;
109                 vector<ntlTriangle *> *mppTriangles;
110
111                 //! temporary array for triangle distribution to nodes
112                 char *mpTriDist;
113
114                 //! temporary array for triangle bounding boxes
115                 TriangleBBox *mpTBB;
116
117                 //! triangle mask - include only triangles that match mask
118                 int mTriangleMask;
119
120                 //! Status vars (max depth, # of current nodes)
121                 int mCurrentDepth, mCurrentNodes;
122
123                 //! duplicated triangles, inited during subdivide 
124                 int mTriDoubles; 
125
126 private:
127 #ifdef WITH_CXX_GUARDEDALLOC
128        MEM_CXX_CLASS_ALLOC_FUNCS("ELBEEM:ntlTree")
129 #endif
130 };
131
132
133 #endif
134
135