Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: code/trunk/src/external/bullet/BulletCollision/Gimpact/btGImpactBvh.h @ 7031

Last change on this file since 7031 was 5781, checked in by rgrieder, 15 years ago

Reverted trunk again. We might want to find a way to delete these revisions again (x3n's changes are still available as diff in the commit mails).

  • Property svn:eol-style set to native
File size: 9.1 KB
Line 
1#ifndef GIM_BOX_SET_H_INCLUDED
2#define GIM_BOX_SET_H_INCLUDED
3
4/*! \file gim_box_set.h
5\author Francisco Len Nßjera
6*/
7/*
8This source file is part of GIMPACT Library.
9
10For the latest info, see http://gimpact.sourceforge.net/
11
12Copyright (c) 2007 Francisco Leon Najera. C.C. 80087371.
13email: projectileman@yahoo.com
14
15
16This software is provided 'as-is', without any express or implied warranty.
17In no event will the authors be held liable for any damages arising from the use of this software.
18Permission is granted to anyone to use this software for any purpose,
19including commercial applications, and to alter it and redistribute it freely,
20subject to the following restrictions:
21
221. The origin of this software must not be misrepresented; you must not claim that you wrote the original software. If you use this software in a product, an acknowledgment in the product documentation would be appreciated but is not required.
232. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software.
243. This notice may not be removed or altered from any source distribution.
25*/
26
27
28#include "LinearMath/btAlignedObjectArray.h"
29
30#include "btBoxCollision.h"
31#include "btTriangleShapeEx.h"
32
33
34
35
36
37//! Overlapping pair
38struct GIM_PAIR
39{
40    int m_index1;
41    int m_index2;
42    GIM_PAIR()
43    {}
44
45    GIM_PAIR(const GIM_PAIR & p)
46    {
47        m_index1 = p.m_index1;
48        m_index2 = p.m_index2;
49        }
50
51        GIM_PAIR(int index1, int index2)
52    {
53        m_index1 = index1;
54        m_index2 = index2;
55        }
56};
57
58//! A pairset array
59class btPairSet: public btAlignedObjectArray<GIM_PAIR>
60{
61public:
62        btPairSet()
63        {
64                reserve(32);
65        }
66        inline void push_pair(int index1,int index2)
67        {
68                push_back(GIM_PAIR(index1,index2));
69        }
70
71        inline void push_pair_inv(int index1,int index2)
72        {
73                push_back(GIM_PAIR(index2,index1));
74        }
75};
76
77
78///GIM_BVH_DATA is an internal GIMPACT collision structure to contain axis aligned bounding box
79struct GIM_BVH_DATA
80{
81        btAABB m_bound;
82        int m_data;
83};
84
85//! Node Structure for trees
86class GIM_BVH_TREE_NODE
87{
88public:
89        btAABB m_bound;
90protected:
91        int     m_escapeIndexOrDataIndex;
92public:
93        GIM_BVH_TREE_NODE()
94        {
95                m_escapeIndexOrDataIndex = 0;
96        }
97
98        SIMD_FORCE_INLINE bool isLeafNode() const
99        {
100                //skipindex is negative (internal node), triangleindex >=0 (leafnode)
101                return (m_escapeIndexOrDataIndex>=0);
102        }
103
104        SIMD_FORCE_INLINE int getEscapeIndex() const
105        {
106                //btAssert(m_escapeIndexOrDataIndex < 0);
107                return -m_escapeIndexOrDataIndex;
108        }
109
110        SIMD_FORCE_INLINE void setEscapeIndex(int index)
111        {
112                m_escapeIndexOrDataIndex = -index;
113        }
114
115        SIMD_FORCE_INLINE int getDataIndex() const
116        {
117                //btAssert(m_escapeIndexOrDataIndex >= 0);
118
119                return m_escapeIndexOrDataIndex;
120        }
121
122        SIMD_FORCE_INLINE void setDataIndex(int index)
123        {
124                m_escapeIndexOrDataIndex = index;
125        }
126
127};
128
129
130class GIM_BVH_DATA_ARRAY:public btAlignedObjectArray<GIM_BVH_DATA>
131{
132};
133
134
135class GIM_BVH_TREE_NODE_ARRAY:public btAlignedObjectArray<GIM_BVH_TREE_NODE>
136{
137};
138
139
140
141
142//! Basic Box tree structure
143class btBvhTree
144{
145protected:
146        int m_num_nodes;
147        GIM_BVH_TREE_NODE_ARRAY m_node_array;
148protected:
149        int _sort_and_calc_splitting_index(
150                GIM_BVH_DATA_ARRAY & primitive_boxes,
151                 int startIndex,  int endIndex, int splitAxis);
152
153        int _calc_splitting_axis(GIM_BVH_DATA_ARRAY & primitive_boxes, int startIndex,  int endIndex);
154
155        void _build_sub_tree(GIM_BVH_DATA_ARRAY & primitive_boxes, int startIndex,  int endIndex);
156public:
157        btBvhTree()
158        {
159                m_num_nodes = 0;
160        }
161
162        //! prototype functions for box tree management
163        //!@{
164        void build_tree(GIM_BVH_DATA_ARRAY & primitive_boxes);
165
166        SIMD_FORCE_INLINE void clearNodes()
167        {
168                m_node_array.clear();
169                m_num_nodes = 0;
170        }
171
172        //! node count
173        SIMD_FORCE_INLINE int getNodeCount() const
174        {
175                return m_num_nodes;
176        }
177
178        //! tells if the node is a leaf
179        SIMD_FORCE_INLINE bool isLeafNode(int nodeindex) const
180        {
181                return m_node_array[nodeindex].isLeafNode();
182        }
183
184        SIMD_FORCE_INLINE int getNodeData(int nodeindex) const
185        {
186                return m_node_array[nodeindex].getDataIndex();
187        }
188
189        SIMD_FORCE_INLINE void getNodeBound(int nodeindex, btAABB & bound) const
190        {
191                bound = m_node_array[nodeindex].m_bound;
192        }
193
194        SIMD_FORCE_INLINE void setNodeBound(int nodeindex, const btAABB & bound)
195        {
196                m_node_array[nodeindex].m_bound = bound;
197        }
198
199        SIMD_FORCE_INLINE int getLeftNode(int nodeindex) const
200        {
201                return nodeindex+1;
202        }
203
204        SIMD_FORCE_INLINE int getRightNode(int nodeindex) const
205        {
206                if(m_node_array[nodeindex+1].isLeafNode()) return nodeindex+2;
207                return nodeindex+1 + m_node_array[nodeindex+1].getEscapeIndex();
208        }
209
210        SIMD_FORCE_INLINE int getEscapeNodeIndex(int nodeindex) const
211        {
212                return m_node_array[nodeindex].getEscapeIndex();
213        }
214
215        SIMD_FORCE_INLINE const GIM_BVH_TREE_NODE * get_node_pointer(int index = 0) const
216        {
217                return &m_node_array[index];
218        }
219
220        //!@}
221};
222
223
224//! Prototype Base class for primitive classification
225/*!
226This class is a wrapper for primitive collections.
227This tells relevant info for the Bounding Box set classes, which take care of space classification.
228This class can manage Compound shapes and trimeshes, and if it is managing trimesh then the  Hierarchy Bounding Box classes will take advantage of primitive Vs Box overlapping tests for getting optimal results and less Per Box compairisons.
229*/
230class btPrimitiveManagerBase
231{
232public:
233
234        //! determines if this manager consist on only triangles, which special case will be optimized
235        virtual bool is_trimesh() const = 0;
236        virtual int get_primitive_count() const = 0;
237        virtual void get_primitive_box(int prim_index ,btAABB & primbox) const = 0;
238        //! retrieves only the points of the triangle, and the collision margin
239        virtual void get_primitive_triangle(int prim_index,btPrimitiveTriangle & triangle) const= 0;
240};
241
242
243//! Structure for containing Boxes
244/*!
245This class offers an structure for managing a box tree of primitives.
246Requires a Primitive prototype (like btPrimitiveManagerBase )
247*/
248class btGImpactBvh
249{
250protected:
251        btBvhTree m_box_tree;
252        btPrimitiveManagerBase * m_primitive_manager;
253
254protected:
255        //stackless refit
256        void refit();
257public:
258
259        //! this constructor doesn't build the tree. you must call      buildSet
260        btGImpactBvh()
261        {
262                m_primitive_manager = NULL;
263        }
264
265        //! this constructor doesn't build the tree. you must call      buildSet
266        btGImpactBvh(btPrimitiveManagerBase * primitive_manager)
267        {
268                m_primitive_manager = primitive_manager;
269        }
270
271        SIMD_FORCE_INLINE btAABB getGlobalBox()  const
272        {
273                btAABB totalbox;
274                getNodeBound(0, totalbox);
275                return totalbox;
276        }
277
278        SIMD_FORCE_INLINE void setPrimitiveManager(btPrimitiveManagerBase * primitive_manager)
279        {
280                m_primitive_manager = primitive_manager;
281        }
282
283        SIMD_FORCE_INLINE btPrimitiveManagerBase * getPrimitiveManager() const
284        {
285                return m_primitive_manager;
286        }
287
288
289//! node manager prototype functions
290///@{
291
292        //! this attemps to refit the box set.
293        SIMD_FORCE_INLINE void update()
294        {
295                refit();
296        }
297
298        //! this rebuild the entire set
299        void buildSet();
300
301        //! returns the indices of the primitives in the m_primitive_manager
302        bool boxQuery(const btAABB & box, btAlignedObjectArray<int> & collided_results) const;
303
304        //! returns the indices of the primitives in the m_primitive_manager
305        SIMD_FORCE_INLINE bool boxQueryTrans(const btAABB & box,
306                 const btTransform & transform, btAlignedObjectArray<int> & collided_results) const
307        {
308                btAABB transbox=box;
309                transbox.appy_transform(transform);
310                return boxQuery(transbox,collided_results);
311        }
312
313        //! returns the indices of the primitives in the m_primitive_manager
314        bool rayQuery(
315                const btVector3 & ray_dir,const btVector3 & ray_origin ,
316                btAlignedObjectArray<int> & collided_results) const;
317
318        //! tells if this set has hierarcht
319        SIMD_FORCE_INLINE bool hasHierarchy() const
320        {
321                return true;
322        }
323
324        //! tells if this set is a trimesh
325        SIMD_FORCE_INLINE bool isTrimesh()  const
326        {
327                return m_primitive_manager->is_trimesh();
328        }
329
330        //! node count
331        SIMD_FORCE_INLINE int getNodeCount() const
332        {
333                return m_box_tree.getNodeCount();
334        }
335
336        //! tells if the node is a leaf
337        SIMD_FORCE_INLINE bool isLeafNode(int nodeindex) const
338        {
339                return m_box_tree.isLeafNode(nodeindex);
340        }
341
342        SIMD_FORCE_INLINE int getNodeData(int nodeindex) const
343        {
344                return m_box_tree.getNodeData(nodeindex);
345        }
346
347        SIMD_FORCE_INLINE void getNodeBound(int nodeindex, btAABB & bound)  const
348        {
349                m_box_tree.getNodeBound(nodeindex, bound);
350        }
351
352        SIMD_FORCE_INLINE void setNodeBound(int nodeindex, const btAABB & bound)
353        {
354                m_box_tree.setNodeBound(nodeindex, bound);
355        }
356
357
358        SIMD_FORCE_INLINE int getLeftNode(int nodeindex) const
359        {
360                return m_box_tree.getLeftNode(nodeindex);
361        }
362
363        SIMD_FORCE_INLINE int getRightNode(int nodeindex) const
364        {
365                return m_box_tree.getRightNode(nodeindex);
366        }
367
368        SIMD_FORCE_INLINE int getEscapeNodeIndex(int nodeindex) const
369        {
370                return m_box_tree.getEscapeNodeIndex(nodeindex);
371        }
372
373        SIMD_FORCE_INLINE void getNodeTriangle(int nodeindex,btPrimitiveTriangle & triangle) const
374        {
375                m_primitive_manager->get_primitive_triangle(getNodeData(nodeindex),triangle);
376        }
377
378
379        SIMD_FORCE_INLINE const GIM_BVH_TREE_NODE * get_node_pointer(int index = 0) const
380        {
381                return m_box_tree.get_node_pointer(index);
382        }
383
384
385        static float getAverageTreeCollisionTime();
386
387
388        static void find_collision(btGImpactBvh * boxset1, const btTransform & trans1,
389                btGImpactBvh * boxset2, const btTransform & trans2,
390                btPairSet & collision_pairs);
391};
392
393
394#endif // GIM_BOXPRUNING_H_INCLUDED
Note: See TracBrowser for help on using the repository browser.