1 /*
2 Bullet Continuous Collision Detection and Physics Library
3 Copyright (c) 2003-2009 Erwin Coumans http://bulletphysics.org
4
5 This software is provided 'as-is', without any express or implied warranty.
6 In no event will the authors be held liable for any damages arising from the use of this software.
7 Permission is granted to anyone to use this software for any purpose,
8 including commercial applications, and to alter it and redistribute it freely,
9 subject to the following restrictions:
10
11 1. 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.
12 2. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software.
13 3. This notice may not be removed or altered from any source distribution.
14 */
15
16 //#define DISABLE_BVH
17
18 #include "BulletCollision/CollisionShapes/btBvhTriangleMeshShape.h"
19 #include "BulletCollision/CollisionShapes/btOptimizedBvh.h"
20 #include "LinearMath/btSerializer.h"
21
22 ///Bvh Concave triangle mesh is a static-triangle mesh shape with Bounding Volume Hierarchy optimization.
23 ///Uses an interface to access the triangles to allow for sharing graphics/physics triangles.
btBvhTriangleMeshShape(btStridingMeshInterface * meshInterface,bool useQuantizedAabbCompression,bool buildBvh)24 btBvhTriangleMeshShape::btBvhTriangleMeshShape(btStridingMeshInterface* meshInterface, bool useQuantizedAabbCompression, bool buildBvh)
25 :btTriangleMeshShape(meshInterface),
26 m_bvh(0),
27 m_triangleInfoMap(0),
28 m_useQuantizedAabbCompression(useQuantizedAabbCompression),
29 m_ownsBvh(false)
30 {
31 m_shapeType = TRIANGLE_MESH_SHAPE_PROXYTYPE;
32 //construct bvh from meshInterface
33 #ifndef DISABLE_BVH
34
35 if (buildBvh)
36 {
37 buildOptimizedBvh();
38 }
39
40 #endif //DISABLE_BVH
41
42 }
43
btBvhTriangleMeshShape(btStridingMeshInterface * meshInterface,bool useQuantizedAabbCompression,const btVector3 & bvhAabbMin,const btVector3 & bvhAabbMax,bool buildBvh)44 btBvhTriangleMeshShape::btBvhTriangleMeshShape(btStridingMeshInterface* meshInterface, bool useQuantizedAabbCompression,const btVector3& bvhAabbMin,const btVector3& bvhAabbMax,bool buildBvh)
45 :btTriangleMeshShape(meshInterface),
46 m_bvh(0),
47 m_triangleInfoMap(0),
48 m_useQuantizedAabbCompression(useQuantizedAabbCompression),
49 m_ownsBvh(false)
50 {
51 m_shapeType = TRIANGLE_MESH_SHAPE_PROXYTYPE;
52 //construct bvh from meshInterface
53 #ifndef DISABLE_BVH
54
55 if (buildBvh)
56 {
57 void* mem = btAlignedAlloc(sizeof(btOptimizedBvh),16);
58 m_bvh = new (mem) btOptimizedBvh();
59
60 m_bvh->build(meshInterface,m_useQuantizedAabbCompression,bvhAabbMin,bvhAabbMax);
61 m_ownsBvh = true;
62 }
63
64 #endif //DISABLE_BVH
65
66 }
67
partialRefitTree(const btVector3 & aabbMin,const btVector3 & aabbMax)68 void btBvhTriangleMeshShape::partialRefitTree(const btVector3& aabbMin,const btVector3& aabbMax)
69 {
70 m_bvh->refitPartial( m_meshInterface,aabbMin,aabbMax );
71
72 m_localAabbMin.setMin(aabbMin);
73 m_localAabbMax.setMax(aabbMax);
74 }
75
76
refitTree(const btVector3 & aabbMin,const btVector3 & aabbMax)77 void btBvhTriangleMeshShape::refitTree(const btVector3& aabbMin,const btVector3& aabbMax)
78 {
79 m_bvh->refit( m_meshInterface, aabbMin,aabbMax );
80
81 recalcLocalAabb();
82 }
83
~btBvhTriangleMeshShape()84 btBvhTriangleMeshShape::~btBvhTriangleMeshShape()
85 {
86 if (m_ownsBvh)
87 {
88 m_bvh->~btOptimizedBvh();
89 btAlignedFree(m_bvh);
90 }
91 }
92
performRaycast(btTriangleCallback * callback,const btVector3 & raySource,const btVector3 & rayTarget)93 void btBvhTriangleMeshShape::performRaycast (btTriangleCallback* callback, const btVector3& raySource, const btVector3& rayTarget)
94 {
95 struct MyNodeOverlapCallback : public btNodeOverlapCallback
96 {
97 btStridingMeshInterface* m_meshInterface;
98 btTriangleCallback* m_callback;
99
100 MyNodeOverlapCallback(btTriangleCallback* callback,btStridingMeshInterface* meshInterface)
101 :m_meshInterface(meshInterface),
102 m_callback(callback)
103 {
104 }
105
106 virtual void processNode(int nodeSubPart, int nodeTriangleIndex)
107 {
108 btVector3 m_triangle[3];
109 const unsigned char *vertexbase;
110 int numverts;
111 PHY_ScalarType type;
112 int stride;
113 const unsigned char *indexbase;
114 int indexstride;
115 int numfaces;
116 PHY_ScalarType indicestype;
117
118 m_meshInterface->getLockedReadOnlyVertexIndexBase(
119 &vertexbase,
120 numverts,
121 type,
122 stride,
123 &indexbase,
124 indexstride,
125 numfaces,
126 indicestype,
127 nodeSubPart);
128
129 unsigned int* gfxbase = (unsigned int*)(indexbase+nodeTriangleIndex*indexstride);
130 btAssert(indicestype==PHY_INTEGER||indicestype==PHY_SHORT);
131
132 const btVector3& meshScaling = m_meshInterface->getScaling();
133 for (int j=2;j>=0;j--)
134 {
135 int graphicsindex = indicestype==PHY_SHORT?((unsigned short*)gfxbase)[j]:gfxbase[j];
136
137 if (type == PHY_FLOAT)
138 {
139 float* graphicsbase = (float*)(vertexbase+graphicsindex*stride);
140
141 m_triangle[j] = btVector3(graphicsbase[0]*meshScaling.getX(),graphicsbase[1]*meshScaling.getY(),graphicsbase[2]*meshScaling.getZ());
142 }
143 else
144 {
145 double* graphicsbase = (double*)(vertexbase+graphicsindex*stride);
146
147 m_triangle[j] = btVector3(btScalar(graphicsbase[0])*meshScaling.getX(),btScalar(graphicsbase[1])*meshScaling.getY(),btScalar(graphicsbase[2])*meshScaling.getZ());
148 }
149 }
150
151 /* Perform ray vs. triangle collision here */
152 m_callback->processTriangle(m_triangle,nodeSubPart,nodeTriangleIndex);
153 m_meshInterface->unLockReadOnlyVertexBase(nodeSubPart);
154 }
155 };
156
157 MyNodeOverlapCallback myNodeCallback(callback,m_meshInterface);
158
159 m_bvh->reportRayOverlappingNodex(&myNodeCallback,raySource,rayTarget);
160 }
161
performConvexcast(btTriangleCallback * callback,const btVector3 & raySource,const btVector3 & rayTarget,const btVector3 & aabbMin,const btVector3 & aabbMax)162 void btBvhTriangleMeshShape::performConvexcast (btTriangleCallback* callback, const btVector3& raySource, const btVector3& rayTarget, const btVector3& aabbMin, const btVector3& aabbMax)
163 {
164 struct MyNodeOverlapCallback : public btNodeOverlapCallback
165 {
166 btStridingMeshInterface* m_meshInterface;
167 btTriangleCallback* m_callback;
168
169 MyNodeOverlapCallback(btTriangleCallback* callback,btStridingMeshInterface* meshInterface)
170 :m_meshInterface(meshInterface),
171 m_callback(callback)
172 {
173 }
174
175 virtual void processNode(int nodeSubPart, int nodeTriangleIndex)
176 {
177 btVector3 m_triangle[3];
178 const unsigned char *vertexbase;
179 int numverts;
180 PHY_ScalarType type;
181 int stride;
182 const unsigned char *indexbase;
183 int indexstride;
184 int numfaces;
185 PHY_ScalarType indicestype;
186
187 m_meshInterface->getLockedReadOnlyVertexIndexBase(
188 &vertexbase,
189 numverts,
190 type,
191 stride,
192 &indexbase,
193 indexstride,
194 numfaces,
195 indicestype,
196 nodeSubPart);
197
198 unsigned int* gfxbase = (unsigned int*)(indexbase+nodeTriangleIndex*indexstride);
199 btAssert(indicestype==PHY_INTEGER||indicestype==PHY_SHORT);
200
201 const btVector3& meshScaling = m_meshInterface->getScaling();
202 for (int j=2;j>=0;j--)
203 {
204 int graphicsindex = indicestype==PHY_SHORT?((unsigned short*)gfxbase)[j]:gfxbase[j];
205
206 if (type == PHY_FLOAT)
207 {
208 float* graphicsbase = (float*)(vertexbase+graphicsindex*stride);
209
210 m_triangle[j] = btVector3(graphicsbase[0]*meshScaling.getX(),graphicsbase[1]*meshScaling.getY(),graphicsbase[2]*meshScaling.getZ());
211 }
212 else
213 {
214 double* graphicsbase = (double*)(vertexbase+graphicsindex*stride);
215
216 m_triangle[j] = btVector3(btScalar(graphicsbase[0])*meshScaling.getX(),btScalar(graphicsbase[1])*meshScaling.getY(),btScalar(graphicsbase[2])*meshScaling.getZ());
217 }
218 }
219
220 /* Perform ray vs. triangle collision here */
221 m_callback->processTriangle(m_triangle,nodeSubPart,nodeTriangleIndex);
222 m_meshInterface->unLockReadOnlyVertexBase(nodeSubPart);
223 }
224 };
225
226 MyNodeOverlapCallback myNodeCallback(callback,m_meshInterface);
227
228 m_bvh->reportBoxCastOverlappingNodex (&myNodeCallback, raySource, rayTarget, aabbMin, aabbMax);
229 }
230
231 //perform bvh tree traversal and report overlapping triangles to 'callback'
processAllTriangles(btTriangleCallback * callback,const btVector3 & aabbMin,const btVector3 & aabbMax) const232 void btBvhTriangleMeshShape::processAllTriangles(btTriangleCallback* callback,const btVector3& aabbMin,const btVector3& aabbMax) const
233 {
234
235 #ifdef DISABLE_BVH
236 //brute force traverse all triangles
237 btTriangleMeshShape::processAllTriangles(callback,aabbMin,aabbMax);
238 #else
239
240 //first get all the nodes
241
242
243 struct MyNodeOverlapCallback : public btNodeOverlapCallback
244 {
245 btStridingMeshInterface* m_meshInterface;
246 btTriangleCallback* m_callback;
247 btVector3 m_triangle[3];
248 int m_numOverlap;
249
250 MyNodeOverlapCallback(btTriangleCallback* callback,btStridingMeshInterface* meshInterface)
251 :m_meshInterface(meshInterface),
252 m_callback(callback),
253 m_numOverlap(0)
254 {
255 }
256
257 virtual void processNode(int nodeSubPart, int nodeTriangleIndex)
258 {
259 m_numOverlap++;
260 const unsigned char *vertexbase;
261 int numverts;
262 PHY_ScalarType type;
263 int stride;
264 const unsigned char *indexbase;
265 int indexstride;
266 int numfaces;
267 PHY_ScalarType indicestype;
268
269
270 m_meshInterface->getLockedReadOnlyVertexIndexBase(
271 &vertexbase,
272 numverts,
273 type,
274 stride,
275 &indexbase,
276 indexstride,
277 numfaces,
278 indicestype,
279 nodeSubPart);
280
281 unsigned int* gfxbase = (unsigned int*)(indexbase+nodeTriangleIndex*indexstride);
282 btAssert(indicestype==PHY_INTEGER||indicestype==PHY_SHORT||indicestype==PHY_UCHAR);
283
284 const btVector3& meshScaling = m_meshInterface->getScaling();
285 for (int j=2;j>=0;j--)
286 {
287
288 int graphicsindex = indicestype==PHY_SHORT?((unsigned short*)gfxbase)[j]:indicestype==PHY_INTEGER?gfxbase[j]:((unsigned char*)gfxbase)[j];
289
290
291 #ifdef DEBUG_TRIANGLE_MESH
292 printf("%d ,",graphicsindex);
293 #endif //DEBUG_TRIANGLE_MESH
294 if (type == PHY_FLOAT)
295 {
296 float* graphicsbase = (float*)(vertexbase+graphicsindex*stride);
297
298 m_triangle[j] = btVector3(
299 graphicsbase[0]*meshScaling.getX(),
300 graphicsbase[1]*meshScaling.getY(),
301 graphicsbase[2]*meshScaling.getZ());
302 }
303 else
304 {
305 double* graphicsbase = (double*)(vertexbase+graphicsindex*stride);
306
307 m_triangle[j] = btVector3(
308 btScalar(graphicsbase[0])*meshScaling.getX(),
309 btScalar(graphicsbase[1])*meshScaling.getY(),
310 btScalar(graphicsbase[2])*meshScaling.getZ());
311 }
312 #ifdef DEBUG_TRIANGLE_MESH
313 printf("triangle vertices:%f,%f,%f\n",triangle[j].x(),triangle[j].y(),triangle[j].z());
314 #endif //DEBUG_TRIANGLE_MESH
315 }
316
317 m_callback->processTriangle(m_triangle,nodeSubPart,nodeTriangleIndex);
318 m_meshInterface->unLockReadOnlyVertexBase(nodeSubPart);
319 }
320
321 };
322
323 MyNodeOverlapCallback myNodeCallback(callback,m_meshInterface);
324
325 m_bvh->reportAabbOverlappingNodex(&myNodeCallback,aabbMin,aabbMax);
326
327 #endif//DISABLE_BVH
328
329
330 }
331
setLocalScaling(const btVector3 & scaling)332 void btBvhTriangleMeshShape::setLocalScaling(const btVector3& scaling)
333 {
334 if ((getLocalScaling() -scaling).length2() > SIMD_EPSILON)
335 {
336 btTriangleMeshShape::setLocalScaling(scaling);
337 buildOptimizedBvh();
338 }
339 }
340
buildOptimizedBvh()341 void btBvhTriangleMeshShape::buildOptimizedBvh()
342 {
343 if (m_ownsBvh)
344 {
345 m_bvh->~btOptimizedBvh();
346 btAlignedFree(m_bvh);
347 }
348 ///m_localAabbMin/m_localAabbMax is already re-calculated in btTriangleMeshShape. We could just scale aabb, but this needs some more work
349 void* mem = btAlignedAlloc(sizeof(btOptimizedBvh),16);
350 m_bvh = new(mem) btOptimizedBvh();
351 //rebuild the bvh...
352 m_bvh->build(m_meshInterface,m_useQuantizedAabbCompression,m_localAabbMin,m_localAabbMax);
353 m_ownsBvh = true;
354 }
355
setOptimizedBvh(btOptimizedBvh * bvh,const btVector3 & scaling)356 void btBvhTriangleMeshShape::setOptimizedBvh(btOptimizedBvh* bvh, const btVector3& scaling)
357 {
358 btAssert(!m_bvh);
359 btAssert(!m_ownsBvh);
360
361 m_bvh = bvh;
362 m_ownsBvh = false;
363 // update the scaling without rebuilding the bvh
364 if ((getLocalScaling() -scaling).length2() > SIMD_EPSILON)
365 {
366 btTriangleMeshShape::setLocalScaling(scaling);
367 }
368 }
369
370
371
372 ///fills the dataBuffer and returns the struct name (and 0 on failure)
serialize(void * dataBuffer,btSerializer * serializer) const373 const char* btBvhTriangleMeshShape::serialize(void* dataBuffer, btSerializer* serializer) const
374 {
375 btTriangleMeshShapeData* trimeshData = (btTriangleMeshShapeData*) dataBuffer;
376
377 btCollisionShape::serialize(&trimeshData->m_collisionShapeData,serializer);
378
379 m_meshInterface->serialize(&trimeshData->m_meshInterface, serializer);
380
381 trimeshData->m_collisionMargin = float(m_collisionMargin);
382
383
384
385 if (m_bvh && !(serializer->getSerializationFlags()&BT_SERIALIZE_NO_BVH))
386 {
387 void* chunk = serializer->findPointer(m_bvh);
388 if (chunk)
389 {
390 #ifdef BT_USE_DOUBLE_PRECISION
391 trimeshData->m_quantizedDoubleBvh = (btQuantizedBvhData*)chunk;
392 trimeshData->m_quantizedFloatBvh = 0;
393 #else
394 trimeshData->m_quantizedFloatBvh = (btQuantizedBvhData*)chunk;
395 trimeshData->m_quantizedDoubleBvh= 0;
396 #endif //BT_USE_DOUBLE_PRECISION
397 } else
398 {
399
400 #ifdef BT_USE_DOUBLE_PRECISION
401 trimeshData->m_quantizedDoubleBvh = (btQuantizedBvhData*)serializer->getUniquePointer(m_bvh);
402 trimeshData->m_quantizedFloatBvh = 0;
403 #else
404 trimeshData->m_quantizedFloatBvh = (btQuantizedBvhData*)serializer->getUniquePointer(m_bvh);
405 trimeshData->m_quantizedDoubleBvh= 0;
406 #endif //BT_USE_DOUBLE_PRECISION
407
408 int sz = m_bvh->calculateSerializeBufferSizeNew();
409 btChunk* chunk = serializer->allocate(sz,1);
410 const char* structType = m_bvh->serialize(chunk->m_oldPtr, serializer);
411 serializer->finalizeChunk(chunk,structType,BT_QUANTIZED_BVH_CODE,m_bvh);
412 }
413 } else
414 {
415 trimeshData->m_quantizedFloatBvh = 0;
416 trimeshData->m_quantizedDoubleBvh = 0;
417 }
418
419
420
421 if (m_triangleInfoMap && !(serializer->getSerializationFlags()&BT_SERIALIZE_NO_TRIANGLEINFOMAP))
422 {
423 void* chunk = serializer->findPointer(m_triangleInfoMap);
424 if (chunk)
425 {
426 trimeshData->m_triangleInfoMap = (btTriangleInfoMapData*)chunk;
427 } else
428 {
429 trimeshData->m_triangleInfoMap = (btTriangleInfoMapData*)serializer->getUniquePointer(m_triangleInfoMap);
430 int sz = m_triangleInfoMap->calculateSerializeBufferSize();
431 btChunk* chunk = serializer->allocate(sz,1);
432 const char* structType = m_triangleInfoMap->serialize(chunk->m_oldPtr, serializer);
433 serializer->finalizeChunk(chunk,structType,BT_TRIANLGE_INFO_MAP,m_triangleInfoMap);
434 }
435 } else
436 {
437 trimeshData->m_triangleInfoMap = 0;
438 }
439
440 return "btTriangleMeshShapeData";
441 }
442
serializeSingleBvh(btSerializer * serializer) const443 void btBvhTriangleMeshShape::serializeSingleBvh(btSerializer* serializer) const
444 {
445 if (m_bvh)
446 {
447 int len = m_bvh->calculateSerializeBufferSizeNew(); //make sure not to use calculateSerializeBufferSize because it is used for in-place
448 btChunk* chunk = serializer->allocate(len,1);
449 const char* structType = m_bvh->serialize(chunk->m_oldPtr, serializer);
450 serializer->finalizeChunk(chunk,structType,BT_QUANTIZED_BVH_CODE,(void*)m_bvh);
451 }
452 }
453
serializeSingleTriangleInfoMap(btSerializer * serializer) const454 void btBvhTriangleMeshShape::serializeSingleTriangleInfoMap(btSerializer* serializer) const
455 {
456 if (m_triangleInfoMap)
457 {
458 int len = m_triangleInfoMap->calculateSerializeBufferSize();
459 btChunk* chunk = serializer->allocate(len,1);
460 const char* structType = m_triangleInfoMap->serialize(chunk->m_oldPtr, serializer);
461 serializer->finalizeChunk(chunk,structType,BT_TRIANLGE_INFO_MAP,(void*)m_triangleInfoMap);
462 }
463 }
464
465
466
467
468