Bullet Collision Detection & Physics Library
btOptimizedBvh.cpp
Go to the documentation of this file.
1/*
2Bullet Continuous Collision Detection and Physics Library
3Copyright (c) 2003-2009 Erwin Coumans http://bulletphysics.org
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"
20
22{
23}
24
26{
27}
28
30{
32
33 // NodeArray triangleNodes;
34
36 {
38
40 {
41 m_triangleNodes.copyFromArray(other.m_triangleNodes);
42 return *this;
43 }
44
47 {
48 }
49
50 virtual void internalProcessTriangleIndex(btVector3* triangle, int partId, int triangleIndex)
51 {
56 aabbMin.setMin(triangle[0]);
57 aabbMax.setMax(triangle[0]);
58 aabbMin.setMin(triangle[1]);
59 aabbMax.setMax(triangle[1]);
60 aabbMin.setMin(triangle[2]);
61 aabbMax.setMax(triangle[2]);
62
63 //with quantization?
64 node.m_aabbMinOrg = aabbMin;
65 node.m_aabbMaxOrg = aabbMax;
66
67 node.m_escapeIndex = -1;
68
69 //for child nodes
70 node.m_subPart = partId;
72 m_triangleNodes.push_back(node);
73 }
74 };
76 {
78 const btQuantizedBvh* m_optimizedTree; // for quantization
79
81 {
82 m_triangleNodes.copyFromArray(other.m_triangleNodes);
83 m_optimizedTree = other.m_optimizedTree;
84 return *this;
85 }
86
89 {
90 }
91
92 virtual void internalProcessTriangleIndex(btVector3* triangle, int partId, int triangleIndex)
93 {
94 // The partId and triangle index must fit in the same (positive) integer
97 //negative indices are reserved for escapeIndex
99
104 aabbMin.setMin(triangle[0]);
105 aabbMax.setMax(triangle[0]);
106 aabbMin.setMin(triangle[1]);
107 aabbMax.setMax(triangle[1]);
108 aabbMin.setMin(triangle[2]);
109 aabbMax.setMax(triangle[2]);
110
111 //PCK: add these checks for zero dimensions of aabb
112 const btScalar MIN_AABB_DIMENSION = btScalar(0.002);
114 if (aabbMax.x() - aabbMin.x() < MIN_AABB_DIMENSION)
115 {
118 }
119 if (aabbMax.y() - aabbMin.y() < MIN_AABB_DIMENSION)
120 {
123 }
124 if (aabbMax.z() - aabbMin.z() < MIN_AABB_DIMENSION)
125 {
128 }
129
130 m_optimizedTree->quantize(&node.m_quantizedAabbMin[0], aabbMin, 0);
131 m_optimizedTree->quantize(&node.m_quantizedAabbMax[0], aabbMax, 1);
132
134
135 m_triangleNodes.push_back(node);
136 }
137 };
138
139 int numLeafNodes = 0;
140
142 {
143 //initialize quantization values
145
147
148 triangles->InternalProcessAllTriangles(&callback, m_bvhAabbMin, m_bvhAabbMax);
149
150 //now we have an array of leafnodes in m_leafNodes
152
154 }
155 else
156 {
158
161
162 triangles->InternalProcessAllTriangles(&callback, aabbMin, aabbMax);
163
164 //now we have an array of leafnodes in m_leafNodes
166
168 }
169
170 m_curNodeIndex = 0;
171
173
176 {
179 subtree.m_rootNodeIndex = 0;
180 subtree.m_subtreeSize = m_quantizedContiguousNodes[0].isLeafNode() ? 1 : m_quantizedContiguousNodes[0].getEscapeIndex();
181 }
182
183 //PCK: update the copy of the size
185
186 //PCK: clear m_quantizedLeafNodes and m_leafNodes, they are temporary
189}
190
192{
194 {
196
198
200
201 int i;
202 for (i = 0; i < m_SubtreeHeaders.size(); i++)
203 {
205 subtree.setAabbFromQuantizeNode(m_quantizedContiguousNodes[subtree.m_rootNodeIndex]);
206 }
207 }
208 else
209 {
210 }
211}
212
214{
215 //incrementally initialize quantization values
217
218 btAssert(aabbMin.getX() > m_bvhAabbMin.getX());
219 btAssert(aabbMin.getY() > m_bvhAabbMin.getY());
220 btAssert(aabbMin.getZ() > m_bvhAabbMin.getZ());
221
222 btAssert(aabbMax.getX() < m_bvhAabbMax.getX());
223 btAssert(aabbMax.getY() < m_bvhAabbMax.getY());
224 btAssert(aabbMax.getZ() < m_bvhAabbMax.getZ());
225
228
229 unsigned short quantizedQueryAabbMin[3];
230 unsigned short quantizedQueryAabbMax[3];
231
234
235 int i;
236 for (i = 0; i < this->m_SubtreeHeaders.size(); i++)
237 {
239
240 //PCK: unsigned instead of bool
242 if (overlap != 0)
243 {
244 updateBvhNodes(meshInterface, subtree.m_rootNodeIndex, subtree.m_rootNodeIndex + subtree.m_subtreeSize, i);
245
246 subtree.setAabbFromQuantizeNode(m_quantizedContiguousNodes[subtree.m_rootNodeIndex]);
247 }
248 }
249}
250
252{
253 (void)index;
254
256
257 int curNodeSubPart = -1;
258
259 //get access info to trianglemesh data
260 const unsigned char* vertexbase = 0;
261 int numverts = 0;
263 int stride = 0;
264 const unsigned char* indexbase = 0;
265 int indexstride = 0;
266 int numfaces = 0;
267 PHY_ScalarType indicestype = PHY_INTEGER;
268
271 const btVector3& meshScaling = meshInterface->getScaling();
272
273 int i;
274 for (i = endNode - 1; i >= firstNode; i--)
275 {
277 if (curNode.isLeafNode())
278 {
279 //recalc aabb from triangle data
280 int nodeSubPart = curNode.getPartId();
281 int nodeTriangleIndex = curNode.getTriangleIndex();
283 {
284 if (curNodeSubPart >= 0)
285 meshInterface->unLockReadOnlyVertexBase(curNodeSubPart);
286 meshInterface->getLockedReadOnlyVertexIndexBase(&vertexbase, numverts, type, stride, &indexbase, indexstride, numfaces, indicestype, nodeSubPart);
287
289 }
290 //triangles->getLockedReadOnlyVertexIndexBase(vertexBase,numVerts,
291
292 unsigned int* gfxbase = (unsigned int*)(indexbase + nodeTriangleIndex * indexstride);
293
294 for (int j = 2; j >= 0; j--)
295 {
296 int graphicsindex;
297 switch (indicestype) {
298 case PHY_INTEGER: graphicsindex = gfxbase[j]; break;
299 case PHY_SHORT: graphicsindex = ((unsigned short*)gfxbase)[j]; break;
300 case PHY_UCHAR: graphicsindex = ((unsigned char*)gfxbase)[j]; break;
301 default: btAssert(0);
302 }
303 if (type == PHY_FLOAT)
304 {
305 float* graphicsbase = (float*)(vertexbase + graphicsindex * stride);
307 graphicsbase[0] * meshScaling.getX(),
308 graphicsbase[1] * meshScaling.getY(),
309 graphicsbase[2] * meshScaling.getZ());
310 }
311 else
312 {
313 double* graphicsbase = (double*)(vertexbase + graphicsindex * stride);
315 }
316 }
317
320 aabbMin.setMin(triangleVerts[0]);
321 aabbMax.setMax(triangleVerts[0]);
322 aabbMin.setMin(triangleVerts[1]);
323 aabbMax.setMax(triangleVerts[1]);
324 aabbMin.setMin(triangleVerts[2]);
325 aabbMax.setMax(triangleVerts[2]);
326
327 quantize(&curNode.m_quantizedAabbMin[0], aabbMin, 0);
328 quantize(&curNode.m_quantizedAabbMax[0], aabbMax, 1);
329 }
330 else
331 {
332 //combine aabb from both children
333
335
337
338 {
339 for (int i = 0; i < 3; i++)
340 {
341 curNode.m_quantizedAabbMin[i] = leftChildNode->m_quantizedAabbMin[i];
342 if (curNode.m_quantizedAabbMin[i] > rightChildNode->m_quantizedAabbMin[i])
343 curNode.m_quantizedAabbMin[i] = rightChildNode->m_quantizedAabbMin[i];
344
345 curNode.m_quantizedAabbMax[i] = leftChildNode->m_quantizedAabbMax[i];
346 if (curNode.m_quantizedAabbMax[i] < rightChildNode->m_quantizedAabbMax[i])
347 curNode.m_quantizedAabbMax[i] = rightChildNode->m_quantizedAabbMax[i];
348 }
349 }
350 }
351 }
352
353 if (curNodeSubPart >= 0)
354 meshInterface->unLockReadOnlyVertexBase(curNodeSubPart);
355}
356
359{
361
362 //we don't add additional data so just do a static upcast
363 return static_cast<btOptimizedBvh*>(bvh);
364}
unsigned testQuantizedAabbAgainstQuantizedAabb(const unsigned short int *aabbMin1, const unsigned short int *aabbMax1, const unsigned short int *aabbMin2, const unsigned short int *aabbMax2)
PHY_ScalarType
PHY_ScalarType enumerates possible scalar types.
@ PHY_FLOAT
@ PHY_UCHAR
@ PHY_SHORT
@ PHY_INTEGER
const T & btMax(const T &a, const T &b)
Definition btMinMax.h:27
#define MAX_NUM_PARTS_IN_BITS
float btScalar
The btScalar type abstracts floating point numbers, to easily switch between double and single floati...
Definition btScalar.h:314
#define BT_LARGE_FLOAT
Definition btScalar.h:316
#define btAssert(x)
Definition btScalar.h:153
int size() const
return the number of elements in the array
void copyFromArray(const btAlignedObjectArray &otherArray)
void resize(int newsize, const T &fillData=T())
void clear()
clear the array, deallocated memory. Generally it is better to use array.resize(0),...
T & expand(const T &fillValue=T())
btBvhSubtreeInfo provides info to gather a subtree of limited size
void setAabbFromQuantizeNode(const btQuantizedBvhNode &quantizedNode)
The btOptimizedBvh extends the btQuantizedBvh to create AABB tree for triangle meshes,...
static btOptimizedBvh * deSerializeInPlace(void *i_alignedDataBuffer, unsigned int i_dataBufferSize, bool i_swapEndian)
deSerializeInPlace loads and initializes a BVH from a buffer in memory 'in place'
void updateBvhNodes(btStridingMeshInterface *meshInterface, int firstNode, int endNode, int index)
virtual ~btOptimizedBvh()
void refitPartial(btStridingMeshInterface *triangles, const btVector3 &aabbMin, const btVector3 &aabbMax)
void refit(btStridingMeshInterface *triangles, const btVector3 &aabbMin, const btVector3 &aabbMax)
void build(btStridingMeshInterface *triangles, bool useQuantizedAabbCompression, const btVector3 &bvhAabbMin, const btVector3 &bvhAabbMax)
The btQuantizedBvh class stores an AABB tree that can be quickly traversed on CPU and Cell SPU.
NodeArray m_leafNodes
void setQuantizationValues(const btVector3 &bvhAabbMin, const btVector3 &bvhAabbMax, btScalar quantizationMargin=btScalar(1.0))
‍***************************************** expert/internal use only *************************
btVector3 m_bvhAabbMax
void buildTree(int startIndex, int endIndex)
QuantizedNodeArray m_quantizedLeafNodes
void quantize(unsigned short *out, const btVector3 &point, int isMax) const
btVector3 m_bvhAabbMin
static btQuantizedBvh * deSerializeInPlace(void *i_alignedDataBuffer, unsigned int i_dataBufferSize, bool i_swapEndian)
deSerializeInPlace loads and initializes a BVH from a buffer in memory 'in place'
BvhSubtreeInfoArray m_SubtreeHeaders
NodeArray m_contiguousNodes
QuantizedNodeArray m_quantizedContiguousNodes
The btStridingMeshInterface is the interface class for high performance generic access to triangle me...
btVector3 can be used to represent 3D points and vectors.
Definition btVector3.h:82
const btScalar & getZ() const
Return the z value.
Definition btVector3.h:565
void setValue(const btScalar &_x, const btScalar &_y, const btScalar &_z)
Definition btVector3.h:640
const btScalar & getY() const
Return the y value.
Definition btVector3.h:563
const btScalar & getX() const
Return the x value.
Definition btVector3.h:561
btOptimizedBvhNode contains both internal and leaf node information.
btQuantizedBvhNode is a compressed aabb node, 16 bytes.
unsigned short int m_quantizedAabbMin[3]
unsigned short int m_quantizedAabbMax[3]
bool isLeafNode() const