Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: code/trunk/src/external/bullet/BulletCollision/CollisionShapes/btOptimizedBvh.cpp @ 8124

Last change on this file since 8124 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: 11.9 KB
Line 
1/*
2Bullet Continuous Collision Detection and Physics Library
3Copyright (c) 2003-2006 Erwin Coumans  http://continuousphysics.com/Bullet/
4
5This software is provided 'as-is', without any express or implied warranty.
6In no event will the authors be held liable for any damages arising from the use of this software.
7Permission is granted to anyone to use this software for any purpose,
8including commercial applications, and to alter it and redistribute it freely,
9subject to the following restrictions:
10
111. 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.
122. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software.
133. This notice may not be removed or altered from any source distribution.
14*/
15
16#include "btOptimizedBvh.h"
17#include "btStridingMeshInterface.h"
18#include "LinearMath/btAabbUtil2.h"
19#include "LinearMath/btIDebugDraw.h"
20
21
22btOptimizedBvh::btOptimizedBvh()
23{ 
24}
25
26btOptimizedBvh::~btOptimizedBvh()
27{
28}
29
30
31void btOptimizedBvh::build(btStridingMeshInterface* triangles, bool useQuantizedAabbCompression, const btVector3& bvhAabbMin, const btVector3& bvhAabbMax)
32{
33        m_useQuantization = useQuantizedAabbCompression;
34
35
36        // NodeArray    triangleNodes;
37
38        struct  NodeTriangleCallback : public btInternalTriangleIndexCallback
39        {
40
41                NodeArray&      m_triangleNodes;
42
43                NodeTriangleCallback& operator=(NodeTriangleCallback& other)
44                {
45                        m_triangleNodes = other.m_triangleNodes;
46                        return *this;
47                }
48               
49                NodeTriangleCallback(NodeArray& triangleNodes)
50                        :m_triangleNodes(triangleNodes)
51                {
52                }
53
54                virtual void internalProcessTriangleIndex(btVector3* triangle,int partId,int  triangleIndex)
55                {
56                        btOptimizedBvhNode node;
57                        btVector3       aabbMin,aabbMax;
58                        aabbMin.setValue(btScalar(1e30),btScalar(1e30),btScalar(1e30));
59                        aabbMax.setValue(btScalar(-1e30),btScalar(-1e30),btScalar(-1e30)); 
60                        aabbMin.setMin(triangle[0]);
61                        aabbMax.setMax(triangle[0]);
62                        aabbMin.setMin(triangle[1]);
63                        aabbMax.setMax(triangle[1]);
64                        aabbMin.setMin(triangle[2]);
65                        aabbMax.setMax(triangle[2]);
66
67                        //with quantization?
68                        node.m_aabbMinOrg = aabbMin;
69                        node.m_aabbMaxOrg = aabbMax;
70
71                        node.m_escapeIndex = -1;
72       
73                        //for child nodes
74                        node.m_subPart = partId;
75                        node.m_triangleIndex = triangleIndex;
76                        m_triangleNodes.push_back(node);
77                }
78        };
79        struct  QuantizedNodeTriangleCallback : public btInternalTriangleIndexCallback
80        {
81                QuantizedNodeArray&     m_triangleNodes;
82                const btQuantizedBvh* m_optimizedTree; // for quantization
83
84                QuantizedNodeTriangleCallback& operator=(QuantizedNodeTriangleCallback& other)
85                {
86                        m_triangleNodes = other.m_triangleNodes;
87                        m_optimizedTree = other.m_optimizedTree;
88                        return *this;
89                }
90
91                QuantizedNodeTriangleCallback(QuantizedNodeArray&       triangleNodes,const btQuantizedBvh* tree)
92                        :m_triangleNodes(triangleNodes),m_optimizedTree(tree)
93                {
94                }
95
96                virtual void internalProcessTriangleIndex(btVector3* triangle,int partId,int  triangleIndex)
97                {
98                        // The partId and triangle index must fit in the same (positive) integer
99                        btAssert(partId < (1<<MAX_NUM_PARTS_IN_BITS));
100                        btAssert(triangleIndex < (1<<(31-MAX_NUM_PARTS_IN_BITS)));
101                        //negative indices are reserved for escapeIndex
102                        btAssert(triangleIndex>=0);
103
104                        btQuantizedBvhNode node;
105                        btVector3       aabbMin,aabbMax;
106                        aabbMin.setValue(btScalar(1e30),btScalar(1e30),btScalar(1e30));
107                        aabbMax.setValue(btScalar(-1e30),btScalar(-1e30),btScalar(-1e30)); 
108                        aabbMin.setMin(triangle[0]);
109                        aabbMax.setMax(triangle[0]);
110                        aabbMin.setMin(triangle[1]);
111                        aabbMax.setMax(triangle[1]);
112                        aabbMin.setMin(triangle[2]);
113                        aabbMax.setMax(triangle[2]);
114
115                        //PCK: add these checks for zero dimensions of aabb
116                        const btScalar MIN_AABB_DIMENSION = btScalar(0.002);
117                        const btScalar MIN_AABB_HALF_DIMENSION = btScalar(0.001);
118                        if (aabbMax.x() - aabbMin.x() < MIN_AABB_DIMENSION)
119                        {
120                                aabbMax.setX(aabbMax.x() + MIN_AABB_HALF_DIMENSION);
121                                aabbMin.setX(aabbMin.x() - MIN_AABB_HALF_DIMENSION);
122                        }
123                        if (aabbMax.y() - aabbMin.y() < MIN_AABB_DIMENSION)
124                        {
125                                aabbMax.setY(aabbMax.y() + MIN_AABB_HALF_DIMENSION);
126                                aabbMin.setY(aabbMin.y() - MIN_AABB_HALF_DIMENSION);
127                        }
128                        if (aabbMax.z() - aabbMin.z() < MIN_AABB_DIMENSION)
129                        {
130                                aabbMax.setZ(aabbMax.z() + MIN_AABB_HALF_DIMENSION);
131                                aabbMin.setZ(aabbMin.z() - MIN_AABB_HALF_DIMENSION);
132                        }
133
134                        m_optimizedTree->quantize(&node.m_quantizedAabbMin[0],aabbMin,0);
135                        m_optimizedTree->quantize(&node.m_quantizedAabbMax[0],aabbMax,1);
136
137                        node.m_escapeIndexOrTriangleIndex = (partId<<(31-MAX_NUM_PARTS_IN_BITS)) | triangleIndex;
138
139                        m_triangleNodes.push_back(node);
140                }
141        };
142       
143
144
145        int numLeafNodes = 0;
146
147       
148        if (m_useQuantization)
149        {
150
151                //initialize quantization values
152                setQuantizationValues(bvhAabbMin,bvhAabbMax);
153
154                QuantizedNodeTriangleCallback   callback(m_quantizedLeafNodes,this);
155
156       
157                triangles->InternalProcessAllTriangles(&callback,m_bvhAabbMin,m_bvhAabbMax);
158
159                //now we have an array of leafnodes in m_leafNodes
160                numLeafNodes = m_quantizedLeafNodes.size();
161
162
163                m_quantizedContiguousNodes.resize(2*numLeafNodes);
164
165
166        } else
167        {
168                NodeTriangleCallback    callback(m_leafNodes);
169
170                btVector3 aabbMin(btScalar(-1e30),btScalar(-1e30),btScalar(-1e30));
171                btVector3 aabbMax(btScalar(1e30),btScalar(1e30),btScalar(1e30));
172
173                triangles->InternalProcessAllTriangles(&callback,aabbMin,aabbMax);
174
175                //now we have an array of leafnodes in m_leafNodes
176                numLeafNodes = m_leafNodes.size();
177
178                m_contiguousNodes.resize(2*numLeafNodes);
179        }
180
181        m_curNodeIndex = 0;
182
183        buildTree(0,numLeafNodes);
184
185        ///if the entire tree is small then subtree size, we need to create a header info for the tree
186        if(m_useQuantization && !m_SubtreeHeaders.size())
187        {
188                btBvhSubtreeInfo& subtree = m_SubtreeHeaders.expand();
189                subtree.setAabbFromQuantizeNode(m_quantizedContiguousNodes[0]);
190                subtree.m_rootNodeIndex = 0;
191                subtree.m_subtreeSize = m_quantizedContiguousNodes[0].isLeafNode() ? 1 : m_quantizedContiguousNodes[0].getEscapeIndex();
192        }
193
194        //PCK: update the copy of the size
195        m_subtreeHeaderCount = m_SubtreeHeaders.size();
196
197        //PCK: clear m_quantizedLeafNodes and m_leafNodes, they are temporary
198        m_quantizedLeafNodes.clear();
199        m_leafNodes.clear();
200}
201
202
203
204
205void    btOptimizedBvh::refit(btStridingMeshInterface* meshInterface,const btVector3& aabbMin,const btVector3& aabbMax)
206{
207        if (m_useQuantization)
208        {
209
210                setQuantizationValues(aabbMin,aabbMax);
211
212                updateBvhNodes(meshInterface,0,m_curNodeIndex,0);
213
214                ///now update all subtree headers
215
216                int i;
217                for (i=0;i<m_SubtreeHeaders.size();i++)
218                {
219                        btBvhSubtreeInfo& subtree = m_SubtreeHeaders[i];
220                        subtree.setAabbFromQuantizeNode(m_quantizedContiguousNodes[subtree.m_rootNodeIndex]);
221                }
222
223        } else
224        {
225
226        }
227}
228
229
230
231
232void    btOptimizedBvh::refitPartial(btStridingMeshInterface* meshInterface,const btVector3& aabbMin,const btVector3& aabbMax)
233{
234        //incrementally initialize quantization values
235        btAssert(m_useQuantization);
236
237        btAssert(aabbMin.getX() > m_bvhAabbMin.getX());
238        btAssert(aabbMin.getY() > m_bvhAabbMin.getY());
239        btAssert(aabbMin.getZ() > m_bvhAabbMin.getZ());
240
241        btAssert(aabbMax.getX() < m_bvhAabbMax.getX());
242        btAssert(aabbMax.getY() < m_bvhAabbMax.getY());
243        btAssert(aabbMax.getZ() < m_bvhAabbMax.getZ());
244
245        ///we should update all quantization values, using updateBvhNodes(meshInterface);
246        ///but we only update chunks that overlap the given aabb
247       
248        unsigned short  quantizedQueryAabbMin[3];
249        unsigned short  quantizedQueryAabbMax[3];
250
251        quantize(&quantizedQueryAabbMin[0],aabbMin,0);
252        quantize(&quantizedQueryAabbMax[0],aabbMax,1);
253
254        int i;
255        for (i=0;i<this->m_SubtreeHeaders.size();i++)
256        {
257                btBvhSubtreeInfo& subtree = m_SubtreeHeaders[i];
258
259                //PCK: unsigned instead of bool
260                unsigned overlap = testQuantizedAabbAgainstQuantizedAabb(quantizedQueryAabbMin,quantizedQueryAabbMax,subtree.m_quantizedAabbMin,subtree.m_quantizedAabbMax);
261                if (overlap != 0)
262                {
263                        updateBvhNodes(meshInterface,subtree.m_rootNodeIndex,subtree.m_rootNodeIndex+subtree.m_subtreeSize,i);
264
265                        subtree.setAabbFromQuantizeNode(m_quantizedContiguousNodes[subtree.m_rootNodeIndex]);
266                }
267        }
268       
269}
270
271void    btOptimizedBvh::updateBvhNodes(btStridingMeshInterface* meshInterface,int firstNode,int endNode,int index)
272{
273        (void)index;
274
275        btAssert(m_useQuantization);
276
277        int curNodeSubPart=-1;
278
279        //get access info to trianglemesh data
280                const unsigned char *vertexbase = 0;
281                int numverts = 0;
282                PHY_ScalarType type = PHY_INTEGER;
283                int stride = 0;
284                const unsigned char *indexbase = 0;
285                int indexstride = 0;
286                int numfaces = 0;
287                PHY_ScalarType indicestype = PHY_INTEGER;
288
289                btVector3       triangleVerts[3];
290                btVector3       aabbMin,aabbMax;
291                const btVector3& meshScaling = meshInterface->getScaling();
292               
293                int i;
294                for (i=endNode-1;i>=firstNode;i--)
295                {
296
297
298                        btQuantizedBvhNode& curNode = m_quantizedContiguousNodes[i];
299                        if (curNode.isLeafNode())
300                        {
301                                //recalc aabb from triangle data
302                                int nodeSubPart = curNode.getPartId();
303                                int nodeTriangleIndex = curNode.getTriangleIndex();
304                                if (nodeSubPart != curNodeSubPart)
305                                {
306                                        if (curNodeSubPart >= 0)
307                                                meshInterface->unLockReadOnlyVertexBase(curNodeSubPart);
308                                        meshInterface->getLockedReadOnlyVertexIndexBase(&vertexbase,numverts,   type,stride,&indexbase,indexstride,numfaces,indicestype,nodeSubPart);
309
310                                        curNodeSubPart = nodeSubPart;
311                                        btAssert(indicestype==PHY_INTEGER||indicestype==PHY_SHORT);
312                                }
313                                //triangles->getLockedReadOnlyVertexIndexBase(vertexBase,numVerts,
314
315                                unsigned int* gfxbase = (unsigned int*)(indexbase+nodeTriangleIndex*indexstride);
316                               
317                               
318                                for (int j=2;j>=0;j--)
319                                {
320                                       
321                                        int graphicsindex = indicestype==PHY_SHORT?((unsigned short*)gfxbase)[j]:gfxbase[j];
322                                        if (type == PHY_FLOAT)
323                                        {
324                                                float* graphicsbase = (float*)(vertexbase+graphicsindex*stride);
325                                                triangleVerts[j] = btVector3(
326                                                        graphicsbase[0]*meshScaling.getX(),
327                                                        graphicsbase[1]*meshScaling.getY(),
328                                                        graphicsbase[2]*meshScaling.getZ());
329                                        }
330                                        else
331                                        {
332                                                double* graphicsbase = (double*)(vertexbase+graphicsindex*stride);
333                                                triangleVerts[j] = btVector3( btScalar(graphicsbase[0]*meshScaling.getX()), btScalar(graphicsbase[1]*meshScaling.getY()), btScalar(graphicsbase[2]*meshScaling.getZ()));
334                                        }
335                                }
336
337
338                               
339                                aabbMin.setValue(btScalar(1e30),btScalar(1e30),btScalar(1e30));
340                                aabbMax.setValue(btScalar(-1e30),btScalar(-1e30),btScalar(-1e30)); 
341                                aabbMin.setMin(triangleVerts[0]);
342                                aabbMax.setMax(triangleVerts[0]);
343                                aabbMin.setMin(triangleVerts[1]);
344                                aabbMax.setMax(triangleVerts[1]);
345                                aabbMin.setMin(triangleVerts[2]);
346                                aabbMax.setMax(triangleVerts[2]);
347
348                                quantize(&curNode.m_quantizedAabbMin[0],aabbMin,0);
349                                quantize(&curNode.m_quantizedAabbMax[0],aabbMax,1);
350                               
351                        } else
352                        {
353                                //combine aabb from both children
354
355                                btQuantizedBvhNode* leftChildNode = &m_quantizedContiguousNodes[i+1];
356                               
357                                btQuantizedBvhNode* rightChildNode = leftChildNode->isLeafNode() ? &m_quantizedContiguousNodes[i+2] :
358                                        &m_quantizedContiguousNodes[i+1+leftChildNode->getEscapeIndex()];
359                               
360
361                                {
362                                        for (int i=0;i<3;i++)
363                                        {
364                                                curNode.m_quantizedAabbMin[i] = leftChildNode->m_quantizedAabbMin[i];
365                                                if (curNode.m_quantizedAabbMin[i]>rightChildNode->m_quantizedAabbMin[i])
366                                                        curNode.m_quantizedAabbMin[i]=rightChildNode->m_quantizedAabbMin[i];
367
368                                                curNode.m_quantizedAabbMax[i] = leftChildNode->m_quantizedAabbMax[i];
369                                                if (curNode.m_quantizedAabbMax[i] < rightChildNode->m_quantizedAabbMax[i])
370                                                        curNode.m_quantizedAabbMax[i] = rightChildNode->m_quantizedAabbMax[i];
371                                        }
372                                }
373                        }
374
375                }
376
377                if (curNodeSubPart >= 0)
378                        meshInterface->unLockReadOnlyVertexBase(curNodeSubPart);
379
380               
381}
382
383///deSerializeInPlace loads and initializes a BVH from a buffer in memory 'in place'
384btOptimizedBvh* btOptimizedBvh::deSerializeInPlace(void *i_alignedDataBuffer, unsigned int i_dataBufferSize, bool i_swapEndian)
385{
386        btQuantizedBvh* bvh = btQuantizedBvh::deSerializeInPlace(i_alignedDataBuffer,i_dataBufferSize,i_swapEndian);
387       
388        //we don't add additional data so just do a static upcast
389        return static_cast<btOptimizedBvh*>(bvh);
390}
Note: See TracBrowser for help on using the repository browser.