Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: code/branches/physics/src/bullet/BulletCollision/GIMPACT/btGImpactQuantizedBvh.h @ 2056

Last change on this file since 2056 was 1963, checked in by rgrieder, 16 years ago

Added Bullet physics engine.

  • Property svn:eol-style set to native
File size: 9.2 KB
Line 
1#ifndef GIM_QUANTIZED_SET_H_INCLUDED
2#define GIM_QUANTIZED_SET_H_INCLUDED
3
4/*! \file btGImpactQuantizedBvh.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#include "btGImpactBvh.h"
28#include "btQuantization.h"
29
30
31
32/*! \defgroup BOX_TREES
33
34
35
36*/
37//! @{
38
39
40///btQuantizedBvhNode is a compressed aabb node, 16 bytes.
41///Node can be used for leafnode or internal node. Leafnodes can point to 32-bit triangle index (non-negative range).
42ATTRIBUTE_ALIGNED16     (struct) BT_QUANTIZED_BVH_NODE
43{
44        //12 bytes
45        unsigned short int      m_quantizedAabbMin[3];
46        unsigned short int      m_quantizedAabbMax[3];
47        //4 bytes
48        int     m_escapeIndexOrDataIndex;
49
50        BT_QUANTIZED_BVH_NODE()
51        {
52                m_escapeIndexOrDataIndex = 0;
53        }
54
55        SIMD_FORCE_INLINE bool isLeafNode() const
56        {
57                //skipindex is negative (internal node), triangleindex >=0 (leafnode)
58                return (m_escapeIndexOrDataIndex>=0);
59        }
60
61        SIMD_FORCE_INLINE int getEscapeIndex() const
62        {
63                //btAssert(m_escapeIndexOrDataIndex < 0);
64                return -m_escapeIndexOrDataIndex;
65        }
66
67        SIMD_FORCE_INLINE void setEscapeIndex(int index)
68        {
69                m_escapeIndexOrDataIndex = -index;
70        }
71
72        SIMD_FORCE_INLINE int getDataIndex() const
73        {
74                //btAssert(m_escapeIndexOrDataIndex >= 0);
75
76                return m_escapeIndexOrDataIndex;
77        }
78
79        SIMD_FORCE_INLINE void setDataIndex(int index)
80        {
81                m_escapeIndexOrDataIndex = index;
82        }
83
84        SIMD_FORCE_INLINE bool testQuantizedBoxOverlapp(
85                unsigned short * quantizedMin,unsigned short * quantizedMax) const
86        {
87                if(m_quantizedAabbMin[0] > quantizedMax[0] ||
88                   m_quantizedAabbMax[0] < quantizedMin[0] ||
89                   m_quantizedAabbMin[1] > quantizedMax[1] ||
90                   m_quantizedAabbMax[1] < quantizedMin[1] ||
91                   m_quantizedAabbMin[2] > quantizedMax[2] ||
92                   m_quantizedAabbMax[2] < quantizedMin[2])
93                {
94                        return false;
95                }
96                return true;
97        }
98
99};
100
101
102
103class BT_QUANTIZED_BVH_NODE_ARRAY:public btAlignedObjectArray<BT_QUANTIZED_BVH_NODE>
104{
105};
106
107
108
109
110//! Basic Box tree structure
111class btQuantizedBvhTree
112{
113protected:
114        int m_num_nodes;
115        BT_QUANTIZED_BVH_NODE_ARRAY m_node_array;
116        btAABB m_global_bound;
117        btVector3 m_bvhQuantization;
118protected:
119        void calc_quantization(BT_BVH_DATA_ARRAY & primitive_boxes, btScalar boundMargin = btScalar(1.0) );
120
121        int _sort_and_calc_splitting_index(
122                BT_BVH_DATA_ARRAY & primitive_boxes,
123                 int startIndex,  int endIndex, int splitAxis);
124
125        int _calc_splitting_axis(BT_BVH_DATA_ARRAY & primitive_boxes, int startIndex,  int endIndex);
126
127        void _build_sub_tree(BT_BVH_DATA_ARRAY & primitive_boxes, int startIndex,  int endIndex);
128public:
129        btQuantizedBvhTree()
130        {
131                m_num_nodes = 0;
132        }
133
134        //! prototype functions for box tree management
135        //!@{
136        void build_tree(BT_BVH_DATA_ARRAY & primitive_boxes);
137
138        SIMD_FORCE_INLINE void quantizePoint(
139                unsigned short * quantizedpoint, const btVector3 & point) const
140        {
141                bt_quantize_clamp(quantizedpoint,point,m_global_bound.m_min,m_global_bound.m_max,m_bvhQuantization);
142        }
143
144
145        SIMD_FORCE_INLINE bool testQuantizedBoxOverlapp(
146                int node_index,
147                unsigned short * quantizedMin,unsigned short * quantizedMax) const
148        {
149                return m_node_array[node_index].testQuantizedBoxOverlapp(quantizedMin,quantizedMax);
150        }
151
152        SIMD_FORCE_INLINE void clearNodes()
153        {
154                m_node_array.clear();
155                m_num_nodes = 0;
156        }
157
158        //! node count
159        SIMD_FORCE_INLINE int getNodeCount() const
160        {
161                return m_num_nodes;
162        }
163
164        //! tells if the node is a leaf
165        SIMD_FORCE_INLINE bool isLeafNode(int nodeindex) const
166        {
167                return m_node_array[nodeindex].isLeafNode();
168        }
169
170        SIMD_FORCE_INLINE int getNodeData(int nodeindex) const
171        {
172                return m_node_array[nodeindex].getDataIndex();
173        }
174
175        SIMD_FORCE_INLINE void getNodeBound(int nodeindex, btAABB & bound) const
176        {
177                bound.m_min = bt_unquantize(
178                        m_node_array[nodeindex].m_quantizedAabbMin,
179                        m_global_bound.m_min,m_bvhQuantization);
180
181                bound.m_max = bt_unquantize(
182                        m_node_array[nodeindex].m_quantizedAabbMax,
183                        m_global_bound.m_min,m_bvhQuantization);
184        }
185
186        SIMD_FORCE_INLINE void setNodeBound(int nodeindex, const btAABB & bound)
187        {
188                bt_quantize_clamp(      m_node_array[nodeindex].m_quantizedAabbMin,
189                                                        bound.m_min,
190                                                        m_global_bound.m_min,
191                                                        m_global_bound.m_max,
192                                                        m_bvhQuantization);
193
194                bt_quantize_clamp(      m_node_array[nodeindex].m_quantizedAabbMax,
195                                                        bound.m_max,
196                                                        m_global_bound.m_min,
197                                                        m_global_bound.m_max,
198                                                        m_bvhQuantization);
199        }
200
201        SIMD_FORCE_INLINE int getLeftNode(int nodeindex) const
202        {
203                return nodeindex+1;
204        }
205
206        SIMD_FORCE_INLINE int getRightNode(int nodeindex) const
207        {
208                if(m_node_array[nodeindex+1].isLeafNode()) return nodeindex+2;
209                return nodeindex+1 + m_node_array[nodeindex+1].getEscapeIndex();
210        }
211
212        SIMD_FORCE_INLINE int getEscapeNodeIndex(int nodeindex) const
213        {
214                return m_node_array[nodeindex].getEscapeIndex();
215        }
216
217        SIMD_FORCE_INLINE const BT_QUANTIZED_BVH_NODE * get_node_pointer(int index = 0) const
218        {
219                return &m_node_array[index];
220        }
221
222        //!@}
223};
224
225
226
227//! Structure for containing Boxes
228/*!
229This class offers an structure for managing a box tree of primitives.
230Requires a Primitive prototype (like btPrimitiveManagerBase )
231*/
232class btGImpactQuantizedBvh
233{
234protected:
235        btQuantizedBvhTree m_box_tree;
236        btPrimitiveManagerBase * m_primitive_manager;
237
238protected:
239        //stackless refit
240        void refit();
241public:
242
243        //! this constructor doesn't build the tree. you must call      buildSet
244        btGImpactQuantizedBvh()
245        {
246                m_primitive_manager = NULL;
247        }
248
249        //! this constructor doesn't build the tree. you must call      buildSet
250        btGImpactQuantizedBvh(btPrimitiveManagerBase * primitive_manager)
251        {
252                m_primitive_manager = primitive_manager;
253        }
254
255        SIMD_FORCE_INLINE btAABB getGlobalBox()  const
256        {
257                btAABB totalbox;
258                getNodeBound(0, totalbox);
259                return totalbox;
260        }
261
262        SIMD_FORCE_INLINE void setPrimitiveManager(btPrimitiveManagerBase * primitive_manager)
263        {
264                m_primitive_manager = primitive_manager;
265        }
266
267        SIMD_FORCE_INLINE btPrimitiveManagerBase * getPrimitiveManager() const
268        {
269                return m_primitive_manager;
270        }
271
272
273//! node manager prototype functions
274///@{
275
276        //! this attemps to refit the box set.
277        SIMD_FORCE_INLINE void update()
278        {
279                refit();
280        }
281
282        //! this rebuild the entire set
283        void buildSet();
284
285        //! returns the indices of the primitives in the m_primitive_manager
286        bool boxQuery(const btAABB & box, btAlignedObjectArray<int> & collided_results) const;
287
288        //! returns the indices of the primitives in the m_primitive_manager
289        SIMD_FORCE_INLINE bool boxQueryTrans(const btAABB & box,
290                 const btTransform & transform, btAlignedObjectArray<int> & collided_results) const
291        {
292                btAABB transbox=box;
293                transbox.appy_transform(transform);
294                return boxQuery(transbox,collided_results);
295        }
296
297        //! returns the indices of the primitives in the m_primitive_manager
298        bool rayQuery(
299                const btVector3 & ray_dir,const btVector3 & ray_origin ,
300                btAlignedObjectArray<int> & collided_results) const;
301
302        //! tells if this set has hierarcht
303        SIMD_FORCE_INLINE bool hasHierarchy() const
304        {
305                return true;
306        }
307
308        //! tells if this set is a trimesh
309        SIMD_FORCE_INLINE bool isTrimesh()  const
310        {
311                return m_primitive_manager->is_trimesh();
312        }
313
314        //! node count
315        SIMD_FORCE_INLINE int getNodeCount() const
316        {
317                return m_box_tree.getNodeCount();
318        }
319
320        //! tells if the node is a leaf
321        SIMD_FORCE_INLINE bool isLeafNode(int nodeindex) const
322        {
323                return m_box_tree.isLeafNode(nodeindex);
324        }
325
326        SIMD_FORCE_INLINE int getNodeData(int nodeindex) const
327        {
328                return m_box_tree.getNodeData(nodeindex);
329        }
330
331        SIMD_FORCE_INLINE void getNodeBound(int nodeindex, btAABB & bound)  const
332        {
333                m_box_tree.getNodeBound(nodeindex, bound);
334        }
335
336        SIMD_FORCE_INLINE void setNodeBound(int nodeindex, const btAABB & bound)
337        {
338                m_box_tree.setNodeBound(nodeindex, bound);
339        }
340
341
342        SIMD_FORCE_INLINE int getLeftNode(int nodeindex) const
343        {
344                return m_box_tree.getLeftNode(nodeindex);
345        }
346
347        SIMD_FORCE_INLINE int getRightNode(int nodeindex) const
348        {
349                return m_box_tree.getRightNode(nodeindex);
350        }
351
352        SIMD_FORCE_INLINE int getEscapeNodeIndex(int nodeindex) const
353        {
354                return m_box_tree.getEscapeNodeIndex(nodeindex);
355        }
356
357        SIMD_FORCE_INLINE void getNodeTriangle(int nodeindex,btPrimitiveTriangle & triangle) const
358        {
359                m_primitive_manager->get_primitive_triangle(getNodeData(nodeindex),triangle);
360        }
361
362
363        SIMD_FORCE_INLINE const BT_QUANTIZED_BVH_NODE * get_node_pointer(int index = 0) const
364        {
365                return m_box_tree.get_node_pointer(index);
366        }
367
368//! @}
369
370        static float getAverageTreeCollisionTime();
371
372
373        static void find_collision(btGImpactQuantizedBvh * boxset1, const btTransform & trans1,
374                btGImpactQuantizedBvh * boxset2, const btTransform & trans2,
375                btPairSet & collision_pairs);
376};
377
378
379#endif // GIM_BOXPRUNING_H_INCLUDED
Note: See TracBrowser for help on using the repository browser.