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
249
250 MyNodeOverlapCallback(btTriangleCallback* callback,btStridingMeshInterface* meshInterface)
251 :m_meshInterface(meshInterface),
252 m_callback(callback)
253 {
254 }
255
256 virtual void processNode(int nodeSubPart, int nodeTriangleIndex)
257 {
258 const unsigned char *vertexbase;
259 int numverts;
260 PHY_ScalarType type;
261 int stride;
262 const unsigned char *indexbase;
263 int indexstride;
264 int numfaces;
265 PHY_ScalarType indicestype;
266
267
268 m_meshInterface->getLockedReadOnlyVertexIndexBase(
269 &vertexbase,
270 numverts,
271 type,
272 stride,
273 &indexbase,
274 indexstride,
275 numfaces,
276 indicestype,
277 nodeSubPart);
278
279 unsigned int* gfxbase = (unsigned int*)(indexbase+nodeTriangleIndex*indexstride);
280 btAssert(indicestype==PHY_INTEGER||indicestype==PHY_SHORT||indicestype==PHY_UCHAR);
281
282 const btVector3& meshScaling = m_meshInterface->getScaling();
283 for (int j=2;j>=0;j--)
284 {
285
286 int graphicsindex = indicestype==PHY_SHORT?((unsigned short*)gfxbase)[j]:indicestype==PHY_INTEGER?gfxbase[j]:((unsigned char*)gfxbase)[j];
287
288
289 #ifdef DEBUG_TRIANGLE_MESH
290 printf("%d ,",graphicsindex);
291 #endif //DEBUG_TRIANGLE_MESH
292 if (type == PHY_FLOAT)
293 {
294 float* graphicsbase = (float*)(vertexbase+graphicsindex*stride);
295
296 m_triangle[j] = btVector3(
297 graphicsbase[0]*meshScaling.getX(),
298 graphicsbase[1]*meshScaling.getY(),
299 graphicsbase[2]*meshScaling.getZ());
300 }
301 else
302 {
303 double* graphicsbase = (double*)(vertexbase+graphicsindex*stride);
304
305 m_triangle[j] = btVector3(
306 btScalar(graphicsbase[0])*meshScaling.getX(),
307 btScalar(graphicsbase[1])*meshScaling.getY(),
308 btScalar(graphicsbase[2])*meshScaling.getZ());
309 }
310 #ifdef DEBUG_TRIANGLE_MESH
311 printf("triangle vertices:%f,%f,%f\n",triangle[j].x(),triangle[j].y(),triangle[j].z());
312 #endif //DEBUG_TRIANGLE_MESH
313 }
314
315 m_callback->processTriangle(m_triangle,nodeSubPart,nodeTriangleIndex);
316 m_meshInterface->unLockReadOnlyVertexBase(nodeSubPart);
317 }
318
319 };
320
321 MyNodeOverlapCallback myNodeCallback(callback,m_meshInterface);
322
323 m_bvh->reportAabbOverlappingNodex(&myNodeCallback,aabbMin,aabbMax);
324
325
326 #endif//DISABLE_BVH
327
328
329 }
330
setLocalScaling(const btVector3 & scaling)331 void btBvhTriangleMeshShape::setLocalScaling(const btVector3& scaling)
332 {
333 if ((getLocalScaling() -scaling).length2() > SIMD_EPSILON)
334 {
335 btTriangleMeshShape::setLocalScaling(scaling);
336 buildOptimizedBvh();
337 }
338 }
339
buildOptimizedBvh()340 void btBvhTriangleMeshShape::buildOptimizedBvh()
341 {
342 if (m_ownsBvh)
343 {
344 m_bvh->~btOptimizedBvh();
345 btAlignedFree(m_bvh);
346 }
347 ///m_localAabbMin/m_localAabbMax is already re-calculated in btTriangleMeshShape. We could just scale aabb, but this needs some more work
348 void* mem = btAlignedAlloc(sizeof(btOptimizedBvh),16);
349 m_bvh = new(mem) btOptimizedBvh();
350 //rebuild the bvh...
351 m_bvh->build(m_meshInterface,m_useQuantizedAabbCompression,m_localAabbMin,m_localAabbMax);
352 m_ownsBvh = true;
353 }
354
setOptimizedBvh(btOptimizedBvh * bvh,const btVector3 & scaling)355 void btBvhTriangleMeshShape::setOptimizedBvh(btOptimizedBvh* bvh, const btVector3& scaling)
356 {
357 btAssert(!m_bvh);
358 btAssert(!m_ownsBvh);
359
360 m_bvh = bvh;
361 m_ownsBvh = false;
362 // update the scaling without rebuilding the bvh
363 if ((getLocalScaling() -scaling).length2() > SIMD_EPSILON)
364 {
365 btTriangleMeshShape::setLocalScaling(scaling);
366 }
367 }
368
369
370
371 ///fills the dataBuffer and returns the struct name (and 0 on failure)
serialize(void * dataBuffer,btSerializer * serializer) const372 const char* btBvhTriangleMeshShape::serialize(void* dataBuffer, btSerializer* serializer) const
373 {
374 btTriangleMeshShapeData* trimeshData = (btTriangleMeshShapeData*) dataBuffer;
375
376 btCollisionShape::serialize(&trimeshData->m_collisionShapeData,serializer);
377
378 m_meshInterface->serialize(&trimeshData->m_meshInterface, serializer);
379
380 trimeshData->m_collisionMargin = float(m_collisionMargin);
381
382
383
384 if (m_bvh && !(serializer->getSerializationFlags()&BT_SERIALIZE_NO_BVH))
385 {
386 void* chunk = serializer->findPointer(m_bvh);
387 if (chunk)
388 {
389 #ifdef BT_USE_DOUBLE_PRECISION
390 trimeshData->m_quantizedDoubleBvh = (btQuantizedBvhData*)chunk;
391 trimeshData->m_quantizedFloatBvh = 0;
392 #else
393 trimeshData->m_quantizedFloatBvh = (btQuantizedBvhData*)chunk;
394 trimeshData->m_quantizedDoubleBvh= 0;
395 #endif //BT_USE_DOUBLE_PRECISION
396 } else
397 {
398
399 #ifdef BT_USE_DOUBLE_PRECISION
400 trimeshData->m_quantizedDoubleBvh = (btQuantizedBvhData*)serializer->getUniquePointer(m_bvh);
401 trimeshData->m_quantizedFloatBvh = 0;
402 #else
403 trimeshData->m_quantizedFloatBvh = (btQuantizedBvhData*)serializer->getUniquePointer(m_bvh);
404 trimeshData->m_quantizedDoubleBvh= 0;
405 #endif //BT_USE_DOUBLE_PRECISION
406
407 int sz = m_bvh->calculateSerializeBufferSizeNew();
408 btChunk* chunk = serializer->allocate(sz,1);
409 const char* structType = m_bvh->serialize(chunk->m_oldPtr, serializer);
410 serializer->finalizeChunk(chunk,structType,BT_QUANTIZED_BVH_CODE,m_bvh);
411 }
412 } else
413 {
414 trimeshData->m_quantizedFloatBvh = 0;
415 trimeshData->m_quantizedDoubleBvh = 0;
416 }
417
418
419
420 if (m_triangleInfoMap && !(serializer->getSerializationFlags()&BT_SERIALIZE_NO_TRIANGLEINFOMAP))
421 {
422 void* chunk = serializer->findPointer(m_triangleInfoMap);
423 if (chunk)
424 {
425 trimeshData->m_triangleInfoMap = (btTriangleInfoMapData*)chunk;
426 } else
427 {
428 trimeshData->m_triangleInfoMap = (btTriangleInfoMapData*)serializer->getUniquePointer(m_triangleInfoMap);
429 int sz = m_triangleInfoMap->calculateSerializeBufferSize();
430 btChunk* chunk = serializer->allocate(sz,1);
431 const char* structType = m_triangleInfoMap->serialize(chunk->m_oldPtr, serializer);
432 serializer->finalizeChunk(chunk,structType,BT_TRIANLGE_INFO_MAP,m_triangleInfoMap);
433 }
434 } else
435 {
436 trimeshData->m_triangleInfoMap = 0;
437 }
438
439 return "btTriangleMeshShapeData";
440 }
441
serializeSingleBvh(btSerializer * serializer) const442 void btBvhTriangleMeshShape::serializeSingleBvh(btSerializer* serializer) const
443 {
444 if (m_bvh)
445 {
446 int len = m_bvh->calculateSerializeBufferSizeNew(); //make sure not to use calculateSerializeBufferSize because it is used for in-place
447 btChunk* chunk = serializer->allocate(len,1);
448 const char* structType = m_bvh->serialize(chunk->m_oldPtr, serializer);
449 serializer->finalizeChunk(chunk,structType,BT_QUANTIZED_BVH_CODE,(void*)m_bvh);
450 }
451 }
452
serializeSingleTriangleInfoMap(btSerializer * serializer) const453 void btBvhTriangleMeshShape::serializeSingleTriangleInfoMap(btSerializer* serializer) const
454 {
455 if (m_triangleInfoMap)
456 {
457 int len = m_triangleInfoMap->calculateSerializeBufferSize();
458 btChunk* chunk = serializer->allocate(len,1);
459 const char* structType = m_triangleInfoMap->serialize(chunk->m_oldPtr, serializer);
460 serializer->finalizeChunk(chunk,structType,BT_TRIANLGE_INFO_MAP,(void*)m_triangleInfoMap);
461 }
462 }
463
464
465
466
467