Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: code/branches/physics/src/bullet/BulletCollision/GIMPACT/btGImpactBvh.h @ 2379

Last change on this file since 2379 was 2192, checked in by rgrieder, 16 years ago

Reverted all changes of attempt to update physics branch.

  • Property svn:eol-style set to native
File size: 9.0 KB
RevLine 
[1963]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/*! \defgroup BOX_TREES
36
37
38
39*/
40//! @{
41
42
43//! Overlapping pair
44struct BT_PAIR
45{
46    int m_index1;
47    int m_index2;
48    BT_PAIR()
49    {}
50
51    BT_PAIR(const BT_PAIR & p)
52    {
53        m_index1 = p.m_index1;
54        m_index2 = p.m_index2;
55        }
56
57        BT_PAIR(int index1, int index2)
58    {
59        m_index1 = index1;
60        m_index2 = index2;
61        }
62};
63
64//! A pairset array
65class btPairSet: public btAlignedObjectArray<BT_PAIR>
66{
67public:
68        btPairSet()
69        {
70                reserve(32);
71        }
72        inline void push_pair(int index1,int index2)
73        {
74                push_back(BT_PAIR(index1,index2));
75        }
76
77        inline void push_pair_inv(int index1,int index2)
78        {
79                push_back(BT_PAIR(index2,index1));
80        }
81};
82
83
84
85struct BT_BVH_DATA
86{
87        btAABB m_bound;
88        int m_data;
89};
90
91//! Node Structure for trees
92class BT_BVH_TREE_NODE
93{
94public:
95        btAABB m_bound;
96protected:
97        int     m_escapeIndexOrDataIndex;
98public:
99        BT_BVH_TREE_NODE()
100        {
101                m_escapeIndexOrDataIndex = 0;
102        }
103
104        SIMD_FORCE_INLINE bool isLeafNode() const
105        {
106                //skipindex is negative (internal node), triangleindex >=0 (leafnode)
107                return (m_escapeIndexOrDataIndex>=0);
108        }
109
110        SIMD_FORCE_INLINE int getEscapeIndex() const
111        {
112                //btAssert(m_escapeIndexOrDataIndex < 0);
113                return -m_escapeIndexOrDataIndex;
114        }
115
116        SIMD_FORCE_INLINE void setEscapeIndex(int index)
117        {
118                m_escapeIndexOrDataIndex = -index;
119        }
120
121        SIMD_FORCE_INLINE int getDataIndex() const
122        {
123                //btAssert(m_escapeIndexOrDataIndex >= 0);
124
125                return m_escapeIndexOrDataIndex;
126        }
127
128        SIMD_FORCE_INLINE void setDataIndex(int index)
129        {
130                m_escapeIndexOrDataIndex = index;
131        }
132
133};
134
135
136class BT_BVH_DATA_ARRAY:public btAlignedObjectArray<BT_BVH_DATA>
137{
138};
139
140
141class BT_BVH_TREE_NODE_ARRAY:public btAlignedObjectArray<BT_BVH_TREE_NODE>
142{
143};
144
145
146
147
148//! Basic Box tree structure
149class btBvhTree
150{
151protected:
152        int m_num_nodes;
153        BT_BVH_TREE_NODE_ARRAY m_node_array;
154protected:
155        int _sort_and_calc_splitting_index(
156                BT_BVH_DATA_ARRAY & primitive_boxes,
157                 int startIndex,  int endIndex, int splitAxis);
158
159        int _calc_splitting_axis(BT_BVH_DATA_ARRAY & primitive_boxes, int startIndex,  int endIndex);
160
161        void _build_sub_tree(BT_BVH_DATA_ARRAY & primitive_boxes, int startIndex,  int endIndex);
162public:
163        btBvhTree()
164        {
165                m_num_nodes = 0;
166        }
167
168        //! prototype functions for box tree management
169        //!@{
170        void build_tree(BT_BVH_DATA_ARRAY & primitive_boxes);
171
172        SIMD_FORCE_INLINE void clearNodes()
173        {
174                m_node_array.clear();
175                m_num_nodes = 0;
176        }
177
178        //! node count
179        SIMD_FORCE_INLINE int getNodeCount() const
180        {
181                return m_num_nodes;
182        }
183
184        //! tells if the node is a leaf
185        SIMD_FORCE_INLINE bool isLeafNode(int nodeindex) const
186        {
187                return m_node_array[nodeindex].isLeafNode();
188        }
189
190        SIMD_FORCE_INLINE int getNodeData(int nodeindex) const
191        {
192                return m_node_array[nodeindex].getDataIndex();
193        }
194
195        SIMD_FORCE_INLINE void getNodeBound(int nodeindex, btAABB & bound) const
196        {
197                bound = m_node_array[nodeindex].m_bound;
198        }
199
200        SIMD_FORCE_INLINE void setNodeBound(int nodeindex, const btAABB & bound)
201        {
202                m_node_array[nodeindex].m_bound = bound;
203        }
204
205        SIMD_FORCE_INLINE int getLeftNode(int nodeindex) const
206        {
207                return nodeindex+1;
208        }
209
210        SIMD_FORCE_INLINE int getRightNode(int nodeindex) const
211        {
212                if(m_node_array[nodeindex+1].isLeafNode()) return nodeindex+2;
213                return nodeindex+1 + m_node_array[nodeindex+1].getEscapeIndex();
214        }
215
216        SIMD_FORCE_INLINE int getEscapeNodeIndex(int nodeindex) const
217        {
218                return m_node_array[nodeindex].getEscapeIndex();
219        }
220
221        SIMD_FORCE_INLINE const BT_BVH_TREE_NODE * get_node_pointer(int index = 0) const
222        {
223                return &m_node_array[index];
224        }
225
226        //!@}
227};
228
229
230//! Prototype Base class for primitive classification
231/*!
232This class is a wrapper for primitive collections.
233This tells relevant info for the Bounding Box set classes, which take care of space classification.
234This 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.
235*/
236class btPrimitiveManagerBase
237{
238public:
239
240        //! determines if this manager consist on only triangles, which special case will be optimized
241        virtual bool is_trimesh() const = 0;
242        virtual int get_primitive_count() const = 0;
243        virtual void get_primitive_box(int prim_index ,btAABB & primbox) const = 0;
244        //! retrieves only the points of the triangle, and the collision margin
245        virtual void get_primitive_triangle(int prim_index,btPrimitiveTriangle & triangle) const= 0;
246};
247
248
249//! Structure for containing Boxes
250/*!
251This class offers an structure for managing a box tree of primitives.
252Requires a Primitive prototype (like btPrimitiveManagerBase )
253*/
254class btGImpactBvh
255{
256protected:
257        btBvhTree m_box_tree;
258        btPrimitiveManagerBase * m_primitive_manager;
259
260protected:
261        //stackless refit
262        void refit();
263public:
264
265        //! this constructor doesn't build the tree. you must call      buildSet
266        btGImpactBvh()
267        {
268                m_primitive_manager = NULL;
269        }
270
271        //! this constructor doesn't build the tree. you must call      buildSet
272        btGImpactBvh(btPrimitiveManagerBase * primitive_manager)
273        {
274                m_primitive_manager = primitive_manager;
275        }
276
277        SIMD_FORCE_INLINE btAABB getGlobalBox()  const
278        {
279                btAABB totalbox;
280                getNodeBound(0, totalbox);
281                return totalbox;
282        }
283
284        SIMD_FORCE_INLINE void setPrimitiveManager(btPrimitiveManagerBase * primitive_manager)
285        {
286                m_primitive_manager = primitive_manager;
287        }
288
289        SIMD_FORCE_INLINE btPrimitiveManagerBase * getPrimitiveManager() const
290        {
291                return m_primitive_manager;
292        }
293
294
295//! node manager prototype functions
296///@{
297
298        //! this attemps to refit the box set.
299        SIMD_FORCE_INLINE void update()
300        {
301                refit();
302        }
303
304        //! this rebuild the entire set
305        void buildSet();
306
307        //! returns the indices of the primitives in the m_primitive_manager
308        bool boxQuery(const btAABB & box, btAlignedObjectArray<int> & collided_results) const;
309
310        //! returns the indices of the primitives in the m_primitive_manager
311        SIMD_FORCE_INLINE bool boxQueryTrans(const btAABB & box,
312                 const btTransform & transform, btAlignedObjectArray<int> & collided_results) const
313        {
314                btAABB transbox=box;
315                transbox.appy_transform(transform);
316                return boxQuery(transbox,collided_results);
317        }
318
319        //! returns the indices of the primitives in the m_primitive_manager
320        bool rayQuery(
321                const btVector3 & ray_dir,const btVector3 & ray_origin ,
322                btAlignedObjectArray<int> & collided_results) const;
323
324        //! tells if this set has hierarcht
325        SIMD_FORCE_INLINE bool hasHierarchy() const
326        {
327                return true;
328        }
329
330        //! tells if this set is a trimesh
331        SIMD_FORCE_INLINE bool isTrimesh()  const
332        {
333                return m_primitive_manager->is_trimesh();
334        }
335
336        //! node count
337        SIMD_FORCE_INLINE int getNodeCount() const
338        {
339                return m_box_tree.getNodeCount();
340        }
341
342        //! tells if the node is a leaf
343        SIMD_FORCE_INLINE bool isLeafNode(int nodeindex) const
344        {
345                return m_box_tree.isLeafNode(nodeindex);
346        }
347
348        SIMD_FORCE_INLINE int getNodeData(int nodeindex) const
349        {
350                return m_box_tree.getNodeData(nodeindex);
351        }
352
353        SIMD_FORCE_INLINE void getNodeBound(int nodeindex, btAABB & bound)  const
354        {
355                m_box_tree.getNodeBound(nodeindex, bound);
356        }
357
358        SIMD_FORCE_INLINE void setNodeBound(int nodeindex, const btAABB & bound)
359        {
360                m_box_tree.setNodeBound(nodeindex, bound);
361        }
362
363
364        SIMD_FORCE_INLINE int getLeftNode(int nodeindex) const
365        {
366                return m_box_tree.getLeftNode(nodeindex);
367        }
368
369        SIMD_FORCE_INLINE int getRightNode(int nodeindex) const
370        {
371                return m_box_tree.getRightNode(nodeindex);
372        }
373
374        SIMD_FORCE_INLINE int getEscapeNodeIndex(int nodeindex) const
375        {
376                return m_box_tree.getEscapeNodeIndex(nodeindex);
377        }
378
379        SIMD_FORCE_INLINE void getNodeTriangle(int nodeindex,btPrimitiveTriangle & triangle) const
380        {
381                m_primitive_manager->get_primitive_triangle(getNodeData(nodeindex),triangle);
382        }
383
384
385        SIMD_FORCE_INLINE const BT_BVH_TREE_NODE * get_node_pointer(int index = 0) const
386        {
387                return m_box_tree.get_node_pointer(index);
388        }
389
390//! @}
391
392        static float getAverageTreeCollisionTime();
393
394
395        static void find_collision(btGImpactBvh * boxset1, const btTransform & trans1,
396                btGImpactBvh * boxset2, const btTransform & trans2,
397                btPairSet & collision_pairs);
398};
399
400
401#endif // GIM_BOXPRUNING_H_INCLUDED
Note: See TracBrowser for help on using the repository browser.