2 Bullet Continuous Collision Detection and Physics Library
3 Copyright (c) 2003-2009 Erwin Coumans http://bulletphysics.org
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:
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.
16 #include "btHeightfieldTerrainShape.h"
18 #include "LinearMath/btTransformUtil.h"
20 btHeightfieldTerrainShape::btHeightfieldTerrainShape(
21 int heightStickWidth, int heightStickLength,
22 const float* heightfieldData, btScalar minHeight, btScalar maxHeight,
23 int upAxis, bool flipQuadEdges)
24 : m_userValue3(0), m_triangleInfoMap(0)
26 initialize(heightStickWidth, heightStickLength, heightfieldData,
27 /*heightScale=*/1, minHeight, maxHeight, upAxis, PHY_FLOAT,
31 btHeightfieldTerrainShape::btHeightfieldTerrainShape(
32 int heightStickWidth, int heightStickLength, const double* heightfieldData,
33 btScalar minHeight, btScalar maxHeight, int upAxis, bool flipQuadEdges)
34 : m_userValue3(0), m_triangleInfoMap(0)
36 initialize(heightStickWidth, heightStickLength, heightfieldData,
37 /*heightScale=*/1, minHeight, maxHeight, upAxis, PHY_DOUBLE,
41 btHeightfieldTerrainShape::btHeightfieldTerrainShape(
42 int heightStickWidth, int heightStickLength, const short* heightfieldData, btScalar heightScale,
43 btScalar minHeight, btScalar maxHeight, int upAxis, bool flipQuadEdges)
44 : m_userValue3(0), m_triangleInfoMap(0)
46 initialize(heightStickWidth, heightStickLength, heightfieldData,
47 heightScale, minHeight, maxHeight, upAxis, PHY_SHORT,
51 btHeightfieldTerrainShape::btHeightfieldTerrainShape(
52 int heightStickWidth, int heightStickLength, const unsigned char* heightfieldData, btScalar heightScale,
53 btScalar minHeight, btScalar maxHeight, int upAxis, bool flipQuadEdges)
54 : m_userValue3(0), m_triangleInfoMap(0)
56 initialize(heightStickWidth, heightStickLength, heightfieldData,
57 heightScale, minHeight, maxHeight, upAxis, PHY_UCHAR,
61 btHeightfieldTerrainShape::btHeightfieldTerrainShape(
62 int heightStickWidth, int heightStickLength, const void* heightfieldData,
63 btScalar heightScale, btScalar minHeight, btScalar maxHeight, int upAxis,
64 PHY_ScalarType hdt, bool flipQuadEdges)
68 // legacy constructor: Assumes PHY_FLOAT means btScalar.
69 #ifdef BT_USE_DOUBLE_PRECISION
70 if (hdt == PHY_FLOAT) hdt = PHY_DOUBLE;
72 initialize(heightStickWidth, heightStickLength, heightfieldData,
73 heightScale, minHeight, maxHeight, upAxis, hdt,
77 btHeightfieldTerrainShape::btHeightfieldTerrainShape(int heightStickWidth, int heightStickLength, const void* heightfieldData, btScalar maxHeight, int upAxis, bool useFloatData, bool flipQuadEdges)
81 // legacy constructor: support only btScalar or unsigned char data,
82 // and min height is zero.
83 PHY_ScalarType hdt = (useFloatData) ? PHY_FLOAT : PHY_UCHAR;
84 #ifdef BT_USE_DOUBLE_PRECISION
85 if (hdt == PHY_FLOAT) hdt = PHY_DOUBLE;
87 btScalar minHeight = 0.0f;
89 // previously, height = uchar * maxHeight / 65535.
90 // So to preserve legacy behavior, heightScale = maxHeight / 65535
91 btScalar heightScale = maxHeight / 65535;
93 initialize(heightStickWidth, heightStickLength, heightfieldData,
94 heightScale, minHeight, maxHeight, upAxis, hdt,
98 void btHeightfieldTerrainShape::initialize(
99 int heightStickWidth, int heightStickLength, const void* heightfieldData,
100 btScalar heightScale, btScalar minHeight, btScalar maxHeight, int upAxis,
101 PHY_ScalarType hdt, bool flipQuadEdges)
104 btAssert(heightStickWidth > 1); // && "bad width");
105 btAssert(heightStickLength > 1); // && "bad length");
106 btAssert(heightfieldData); // && "null heightfield data");
107 // btAssert(heightScale) -- do we care? Trust caller here
108 btAssert(minHeight <= maxHeight); // && "bad min/max height");
109 btAssert(upAxis >= 0 && upAxis < 3); // && "bad upAxis--should be in range [0,2]");
110 btAssert(hdt != PHY_UCHAR || hdt != PHY_FLOAT || hdt != PHY_DOUBLE || hdt != PHY_SHORT); // && "Bad height data type enum");
112 // initialize member variables
113 m_shapeType = TERRAIN_SHAPE_PROXYTYPE;
114 m_heightStickWidth = heightStickWidth;
115 m_heightStickLength = heightStickLength;
116 m_minHeight = minHeight;
117 m_maxHeight = maxHeight;
118 m_width = (btScalar)(heightStickWidth - 1);
119 m_length = (btScalar)(heightStickLength - 1);
120 m_heightScale = heightScale;
121 m_heightfieldDataUnknown = heightfieldData;
122 m_heightDataType = hdt;
123 m_flipQuadEdges = flipQuadEdges;
124 m_useDiamondSubdivision = false;
125 m_useZigzagSubdivision = false;
126 m_flipTriangleWinding = false;
128 m_localScaling.setValue(btScalar(1.), btScalar(1.), btScalar(1.));
130 m_vboundsChunkSize = 0;
131 m_vboundsGridWidth = 0;
132 m_vboundsGridLength = 0;
134 // determine min/max axis-aligned bounding box (aabb) values
139 m_localAabbMin.setValue(m_minHeight, 0, 0);
140 m_localAabbMax.setValue(m_maxHeight, m_width, m_length);
145 m_localAabbMin.setValue(0, m_minHeight, 0);
146 m_localAabbMax.setValue(m_width, m_maxHeight, m_length);
151 m_localAabbMin.setValue(0, 0, m_minHeight);
152 m_localAabbMax.setValue(m_width, m_length, m_maxHeight);
157 //need to get valid m_upAxis
158 btAssert(0); // && "Bad m_upAxis");
162 // remember origin (defined as exact middle of aabb)
163 m_localOrigin = btScalar(0.5) * (m_localAabbMin + m_localAabbMax);
166 btHeightfieldTerrainShape::~btHeightfieldTerrainShape()
171 void btHeightfieldTerrainShape::getAabb(const btTransform& t, btVector3& aabbMin, btVector3& aabbMax) const
173 btVector3 halfExtents = (m_localAabbMax - m_localAabbMin) * m_localScaling * btScalar(0.5);
175 btVector3 localOrigin(0, 0, 0);
176 localOrigin[m_upAxis] = (m_minHeight + m_maxHeight) * btScalar(0.5);
177 localOrigin *= m_localScaling;
179 btMatrix3x3 abs_b = t.getBasis().absolute();
180 btVector3 center = t.getOrigin();
181 btVector3 extent = halfExtents.dot3(abs_b[0], abs_b[1], abs_b[2]);
182 extent += btVector3(getMargin(), getMargin(), getMargin());
184 aabbMin = center - extent;
185 aabbMax = center + extent;
188 /// This returns the "raw" (user's initial) height, not the actual height.
189 /// The actual height needs to be adjusted to be relative to the center
190 /// of the heightfield's AABB.
192 btHeightfieldTerrainShape::getRawHeightFieldValue(int x, int y) const
195 switch (m_heightDataType)
199 val = m_heightfieldDataFloat[(y * m_heightStickWidth) + x];
205 val = m_heightfieldDataDouble[(y * m_heightStickWidth) + x];
211 unsigned char heightFieldValue = m_heightfieldDataUnsignedChar[(y * m_heightStickWidth) + x];
212 val = heightFieldValue * m_heightScale;
218 short hfValue = m_heightfieldDataShort[(y * m_heightStickWidth) + x];
219 val = hfValue * m_heightScale;
225 btAssert(!"Bad m_heightDataType");
232 /// this returns the vertex in bullet-local coordinates
233 void btHeightfieldTerrainShape::getVertex(int x, int y, btVector3& vertex) const
237 btAssert(x < m_heightStickWidth);
238 btAssert(y < m_heightStickLength);
240 btScalar height = getRawHeightFieldValue(x, y);
247 height - m_localOrigin.getX(),
248 (-m_width / btScalar(2.0)) + x,
249 (-m_length / btScalar(2.0)) + y);
255 (-m_width / btScalar(2.0)) + x,
256 height - m_localOrigin.getY(),
257 (-m_length / btScalar(2.0)) + y);
263 (-m_width / btScalar(2.0)) + x,
264 (-m_length / btScalar(2.0)) + y,
265 height - m_localOrigin.getZ());
270 //need to get valid m_upAxis
275 vertex *= m_localScaling;
284 return (int)(x - 0.5);
286 return (int)(x + 0.5);
289 // Equivalent to std::minmax({a, b, c}).
290 // Performs at most 3 comparisons.
291 static btHeightfieldTerrainShape::Range minmaxRange(btScalar a, btScalar b, btScalar c)
296 return btHeightfieldTerrainShape::Range(c, a);
298 return btHeightfieldTerrainShape::Range(b, a);
300 return btHeightfieldTerrainShape::Range(b, c);
305 return btHeightfieldTerrainShape::Range(c, b);
307 return btHeightfieldTerrainShape::Range(a, b);
309 return btHeightfieldTerrainShape::Range(a, c);
313 /// given input vector, return quantized version
315 This routine is basically determining the gridpoint indices for a given
316 input vector, answering the question: "which gridpoint is closest to the
319 "with clamp" means that we restrict the point to be in the heightfield's
320 axis-aligned bounding box.
322 void btHeightfieldTerrainShape::quantizeWithClamp(int* out, const btVector3& point, int /*isMax*/) const
324 btVector3 clampedPoint(point);
325 clampedPoint.setMax(m_localAabbMin);
326 clampedPoint.setMin(m_localAabbMax);
328 out[0] = getQuantized(clampedPoint.getX());
329 out[1] = getQuantized(clampedPoint.getY());
330 out[2] = getQuantized(clampedPoint.getZ());
333 /// process all triangles within the provided axis-aligned bounding box
336 - convert input aabb to local coordinates (scale down and shift for local origin)
337 - convert input aabb to a range of heightfield grid points (quantize)
338 - iterate over all triangles in that subset of the grid
340 void btHeightfieldTerrainShape::processAllTriangles(btTriangleCallback* callback, const btVector3& aabbMin, const btVector3& aabbMax) const
342 // scale down the input aabb's so they are in local (non-scaled) coordinates
343 btVector3 localAabbMin = aabbMin * btVector3(1.f / m_localScaling[0], 1.f / m_localScaling[1], 1.f / m_localScaling[2]);
344 btVector3 localAabbMax = aabbMax * btVector3(1.f / m_localScaling[0], 1.f / m_localScaling[1], 1.f / m_localScaling[2]);
346 // account for local origin
347 localAabbMin += m_localOrigin;
348 localAabbMax += m_localOrigin;
350 //quantize the aabbMin and aabbMax, and adjust the start/end ranges
351 int quantizedAabbMin[3];
352 int quantizedAabbMax[3];
353 quantizeWithClamp(quantizedAabbMin, localAabbMin, 0);
354 quantizeWithClamp(quantizedAabbMax, localAabbMax, 1);
356 // expand the min/max quantized values
357 // this is to catch the case where the input aabb falls between grid points!
358 for (int i = 0; i < 3; ++i)
360 quantizedAabbMin[i]--;
361 quantizedAabbMax[i]++;
365 int endX = m_heightStickWidth - 1;
367 int endJ = m_heightStickLength - 1;
373 if (quantizedAabbMin[1] > startX)
374 startX = quantizedAabbMin[1];
375 if (quantizedAabbMax[1] < endX)
376 endX = quantizedAabbMax[1];
377 if (quantizedAabbMin[2] > startJ)
378 startJ = quantizedAabbMin[2];
379 if (quantizedAabbMax[2] < endJ)
380 endJ = quantizedAabbMax[2];
385 if (quantizedAabbMin[0] > startX)
386 startX = quantizedAabbMin[0];
387 if (quantizedAabbMax[0] < endX)
388 endX = quantizedAabbMax[0];
389 if (quantizedAabbMin[2] > startJ)
390 startJ = quantizedAabbMin[2];
391 if (quantizedAabbMax[2] < endJ)
392 endJ = quantizedAabbMax[2];
397 if (quantizedAabbMin[0] > startX)
398 startX = quantizedAabbMin[0];
399 if (quantizedAabbMax[0] < endX)
400 endX = quantizedAabbMax[0];
401 if (quantizedAabbMin[1] > startJ)
402 startJ = quantizedAabbMin[1];
403 if (quantizedAabbMax[1] < endJ)
404 endJ = quantizedAabbMax[1];
409 //need to get valid m_upAxis
414 // TODO If m_vboundsGrid is available, use it to determine if we really need to process this area
416 const Range aabbUpRange(aabbMin[m_upAxis], aabbMax[m_upAxis]);
417 for (int j = startJ; j < endJ; j++)
419 for (int x = startX; x < endX; x++)
421 btVector3 vertices[3];
422 int indices[3] = { 0, 1, 2 };
423 if (m_flipTriangleWinding)
429 if (m_flipQuadEdges || (m_useDiamondSubdivision && !((j + x) & 1)) || (m_useZigzagSubdivision && !(j & 1)))
431 getVertex(x, j, vertices[indices[0]]);
432 getVertex(x, j + 1, vertices[indices[1]]);
433 getVertex(x + 1, j + 1, vertices[indices[2]]);
435 // Skip triangle processing if the triangle is out-of-AABB.
436 Range upRange = minmaxRange(vertices[0][m_upAxis], vertices[1][m_upAxis], vertices[2][m_upAxis]);
438 if (upRange.overlaps(aabbUpRange))
439 callback->processTriangle(vertices, 2 * x, j);
441 // already set: getVertex(x, j, vertices[indices[0]])
443 // equivalent to: getVertex(x + 1, j + 1, vertices[indices[1]]);
444 vertices[indices[1]] = vertices[indices[2]];
446 getVertex(x + 1, j, vertices[indices[2]]);
447 upRange.min = btMin(upRange.min, vertices[indices[2]][m_upAxis]);
448 upRange.max = btMax(upRange.max, vertices[indices[2]][m_upAxis]);
450 if (upRange.overlaps(aabbUpRange))
451 callback->processTriangle(vertices, 2 * x + 1, j);
455 getVertex(x, j, vertices[indices[0]]);
456 getVertex(x, j + 1, vertices[indices[1]]);
457 getVertex(x + 1, j, vertices[indices[2]]);
459 // Skip triangle processing if the triangle is out-of-AABB.
460 Range upRange = minmaxRange(vertices[0][m_upAxis], vertices[1][m_upAxis], vertices[2][m_upAxis]);
462 if (upRange.overlaps(aabbUpRange))
463 callback->processTriangle(vertices, 2 * x, j);
465 // already set: getVertex(x, j + 1, vertices[indices[1]]);
467 // equivalent to: getVertex(x + 1, j, vertices[indices[0]]);
468 vertices[indices[0]] = vertices[indices[2]];
470 getVertex(x + 1, j + 1, vertices[indices[2]]);
471 upRange.min = btMin(upRange.min, vertices[indices[2]][m_upAxis]);
472 upRange.max = btMax(upRange.max, vertices[indices[2]][m_upAxis]);
474 if (upRange.overlaps(aabbUpRange))
475 callback->processTriangle(vertices, 2 * x + 1, j);
481 void btHeightfieldTerrainShape::calculateLocalInertia(btScalar, btVector3& inertia) const
483 //moving concave objects not supported
485 inertia.setValue(btScalar(0.), btScalar(0.), btScalar(0.));
488 void btHeightfieldTerrainShape::setLocalScaling(const btVector3& scaling)
490 m_localScaling = scaling;
492 const btVector3& btHeightfieldTerrainShape::getLocalScaling() const
494 return m_localScaling;
499 struct GridRaycastState
501 int x; // Next quad coords
503 int prev_x; // Previous quad coords
505 btScalar param; // Exit param for previous quad
506 btScalar prevParam; // Enter param for previous quad
507 btScalar maxDistanceFlat;
508 btScalar maxDistance3d;
512 // TODO Does it really need to take 3D vectors?
513 /// Iterates through a virtual 2D grid of unit-sized square cells,
514 /// and executes an action on each cell intersecting the given segment, ordered from begin to end.
515 /// Initially inspired by http://www.cse.yorku.ca/~amana/research/grid.pdf
516 template <typename Action_T>
517 void gridRaycast(Action_T& quadAction, const btVector3& beginPos, const btVector3& endPos, int indices[3])
520 rs.maxDistance3d = beginPos.distance(endPos);
521 if (rs.maxDistance3d < 0.0001)
523 // Consider the ray is too small to hit anything
528 btScalar rayDirectionFlatX = endPos[indices[0]] - beginPos[indices[0]];
529 btScalar rayDirectionFlatZ = endPos[indices[2]] - beginPos[indices[2]];
530 rs.maxDistanceFlat = btSqrt(rayDirectionFlatX * rayDirectionFlatX + rayDirectionFlatZ * rayDirectionFlatZ);
532 if (rs.maxDistanceFlat < 0.0001)
534 // Consider the ray vertical
535 rayDirectionFlatX = 0;
536 rayDirectionFlatZ = 0;
540 rayDirectionFlatX /= rs.maxDistanceFlat;
541 rayDirectionFlatZ /= rs.maxDistanceFlat;
544 const int xiStep = rayDirectionFlatX > 0 ? 1 : rayDirectionFlatX < 0 ? -1 : 0;
545 const int ziStep = rayDirectionFlatZ > 0 ? 1 : rayDirectionFlatZ < 0 ? -1 : 0;
547 const float infinite = 9999999;
548 const btScalar paramDeltaX = xiStep != 0 ? 1.f / btFabs(rayDirectionFlatX) : infinite;
549 const btScalar paramDeltaZ = ziStep != 0 ? 1.f / btFabs(rayDirectionFlatZ) : infinite;
552 btScalar paramCrossX; // At which value of `param` we will cross a x-axis lane?
553 btScalar paramCrossZ; // At which value of `param` we will cross a z-axis lane?
555 // paramCrossX and paramCrossZ are initialized as being the first cross
561 paramCrossX = (ceil(beginPos[indices[0]]) - beginPos[indices[0]]) * paramDeltaX;
565 paramCrossX = (beginPos[indices[0]] - floor(beginPos[indices[0]])) * paramDeltaX;
570 paramCrossX = infinite; // Will never cross on X
578 paramCrossZ = (ceil(beginPos[indices[2]]) - beginPos[indices[2]]) * paramDeltaZ;
582 paramCrossZ = (beginPos[indices[2]] - floor(beginPos[indices[2]])) * paramDeltaZ;
587 paramCrossZ = infinite; // Will never cross on Z
590 rs.x = static_cast<int>(floor(beginPos[indices[0]]));
591 rs.z = static_cast<int>(floor(beginPos[indices[2]]));
593 // Workaround cases where the ray starts at an integer position
594 if (paramCrossX == 0.0)
596 paramCrossX += paramDeltaX;
597 // If going backwards, we should ignore the position we would get by the above flooring,
598 // because the ray is not heading in that direction
605 if (paramCrossZ == 0.0)
607 paramCrossZ += paramDeltaZ;
620 rs.prevParam = rs.param;
622 if (paramCrossX < paramCrossZ)
626 // Assign before advancing the param,
627 // to be in sync with the initialization step
628 rs.param = paramCrossX;
629 paramCrossX += paramDeltaX;
635 rs.param = paramCrossZ;
636 paramCrossZ += paramDeltaZ;
639 if (rs.param > rs.maxDistanceFlat)
641 rs.param = rs.maxDistanceFlat;
652 struct ProcessTrianglesAction
654 const btHeightfieldTerrainShape* shape;
656 bool useDiamondSubdivision;
659 btTriangleCallback* callback;
661 void exec(int x, int z) const
663 if (x < 0 || z < 0 || x >= width || z >= length)
668 btVector3 vertices[3];
670 // TODO Since this is for raycasts, we could greatly benefit from an early exit on the first hit
673 if (flipQuadEdges || (useDiamondSubdivision && (((z + x) & 1) > 0)))
676 shape->getVertex(x, z, vertices[0]);
677 shape->getVertex(x + 1, z, vertices[1]);
678 shape->getVertex(x + 1, z + 1, vertices[2]);
679 callback->processTriangle(vertices, x, z);
682 shape->getVertex(x, z, vertices[0]);
683 shape->getVertex(x + 1, z + 1, vertices[1]);
684 shape->getVertex(x, z + 1, vertices[2]);
685 callback->processTriangle(vertices, x, z);
690 shape->getVertex(x, z, vertices[0]);
691 shape->getVertex(x, z + 1, vertices[1]);
692 shape->getVertex(x + 1, z, vertices[2]);
693 callback->processTriangle(vertices, x, z);
696 shape->getVertex(x + 1, z, vertices[0]);
697 shape->getVertex(x, z + 1, vertices[1]);
698 shape->getVertex(x + 1, z + 1, vertices[2]);
699 callback->processTriangle(vertices, x, z);
703 void operator()(const GridRaycastState& bs) const
705 exec(bs.prev_x, bs.prev_z);
709 struct ProcessVBoundsAction
711 const btAlignedObjectArray<btHeightfieldTerrainShape::Range>& vbounds;
721 ProcessTrianglesAction processTriangles;
723 ProcessVBoundsAction(const btAlignedObjectArray<btHeightfieldTerrainShape::Range>& bnd, int* indices)
728 void operator()(const GridRaycastState& rs) const
733 if (x < 0 || z < 0 || x >= width || z >= length)
738 const btHeightfieldTerrainShape::Range chunk = vbounds[x + z * width];
743 if (rs.maxDistanceFlat > 0.0001)
745 btScalar flatTo3d = chunkSize * rs.maxDistance3d / rs.maxDistanceFlat;
746 btScalar enterParam3d = rs.prevParam * flatTo3d;
747 btScalar exitParam3d = rs.param * flatTo3d;
748 enterPos = rayBegin + rayDir * enterParam3d;
749 exitPos = rayBegin + rayDir * exitParam3d;
751 // We did enter the flat projection of the AABB,
752 // but we have to check if we intersect it on the vertical axis
753 if (enterPos[1] > chunk.max && exitPos[m_indices[1]] > chunk.max)
757 if (enterPos[1] < chunk.min && exitPos[m_indices[1]] < chunk.min)
764 // Consider the ray vertical
765 // (though we shouldn't reach this often because there is an early check up-front)
770 gridRaycast(processTriangles, enterPos, exitPos, m_indices);
771 // Note: it could be possible to have more than one grid at different levels,
772 // to do this there would be a branch using a pointer to another ProcessVBoundsAction
776 // TODO How do I interrupt the ray when there is a hit? `callback` does not return any result
777 /// Performs a raycast using a hierarchical Bresenham algorithm.
778 /// Does not allocate any memory by itself.
779 void btHeightfieldTerrainShape::performRaycast(btTriangleCallback* callback, const btVector3& raySource, const btVector3& rayTarget) const
781 // Transform to cell-local
782 btVector3 beginPos = raySource / m_localScaling;
783 btVector3 endPos = rayTarget / m_localScaling;
784 beginPos += m_localOrigin;
785 endPos += m_localOrigin;
787 ProcessTrianglesAction processTriangles;
788 processTriangles.shape = this;
789 processTriangles.flipQuadEdges = m_flipQuadEdges;
790 processTriangles.useDiamondSubdivision = m_useDiamondSubdivision;
791 processTriangles.callback = callback;
792 processTriangles.width = m_heightStickWidth - 1;
793 processTriangles.length = m_heightStickLength - 1;
795 // TODO Transform vectors to account for m_upAxis
796 int indices[3] = { 0, 1, 2 };
802 int iBeginX = static_cast<int>(floor(beginPos[indices[0]]));
803 int iBeginZ = static_cast<int>(floor(beginPos[indices[2]]));
804 int iEndX = static_cast<int>(floor(endPos[indices[0]]));
805 int iEndZ = static_cast<int>(floor(endPos[indices[2]]));
807 if (iBeginX == iEndX && iBeginZ == iEndZ)
809 // The ray will never cross quads within the plane,
810 // so directly process triangles within one quad
811 // (typically, vertical rays should end up here)
812 processTriangles.exec(iBeginX, iEndZ);
818 if (m_vboundsGrid.size()==0)
820 // Process all quads intersecting the flat projection of the ray
821 gridRaycast(processTriangles, beginPos, endPos, &indices[0]);
825 btVector3 rayDiff = endPos - beginPos;
826 btScalar flatDistance2 = rayDiff[indices[0]] * rayDiff[indices[0]] + rayDiff[indices[2]] * rayDiff[indices[2]];
827 if (flatDistance2 < m_vboundsChunkSize * m_vboundsChunkSize)
829 // Don't use chunks, the ray is too short in the plane
830 gridRaycast(processTriangles, beginPos, endPos, &indices[0]);
834 ProcessVBoundsAction processVBounds(m_vboundsGrid, &indices[0]);
835 processVBounds.width = m_vboundsGridWidth;
836 processVBounds.length = m_vboundsGridLength;
837 processVBounds.rayBegin = beginPos;
838 processVBounds.rayEnd = endPos;
839 processVBounds.rayDir = rayDiff.normalized();
840 processVBounds.processTriangles = processTriangles;
841 processVBounds.chunkSize = m_vboundsChunkSize;
842 // The ray is long, run raycast on a higher-level grid
843 gridRaycast(processVBounds, beginPos / m_vboundsChunkSize, endPos / m_vboundsChunkSize, indices);
847 /// Builds a grid data structure storing the min and max heights of the terrain in chunks.
848 /// if chunkSize is zero, that accelerator is removed.
849 /// If you modify the heights, you need to rebuild this accelerator.
850 void btHeightfieldTerrainShape::buildAccelerator(int chunkSize)
858 m_vboundsChunkSize = chunkSize;
859 int nChunksX = m_heightStickWidth / chunkSize;
860 int nChunksZ = m_heightStickLength / chunkSize;
862 if (m_heightStickWidth % chunkSize > 0)
864 ++nChunksX; // In case terrain size isn't dividable by chunk size
866 if (m_heightStickLength % chunkSize > 0)
871 if (m_vboundsGridWidth != nChunksX || m_vboundsGridLength != nChunksZ)
874 m_vboundsGridWidth = nChunksX;
875 m_vboundsGridLength = nChunksZ;
878 if (nChunksX == 0 || nChunksZ == 0)
883 // This data structure is only reallocated if the required size changed
884 m_vboundsGrid.resize(nChunksX * nChunksZ);
886 // Compute min and max height for all chunks
887 for (int cz = 0; cz < nChunksZ; ++cz)
889 int z0 = cz * chunkSize;
891 for (int cx = 0; cx < nChunksX; ++cx)
893 int x0 = cx * chunkSize;
897 r.min = getRawHeightFieldValue(x0, z0);
900 // Compute min and max height for this chunk.
901 // We have to include one extra cell to account for neighbors.
903 // Say we have a flat terrain, and a plateau that fits a chunk perfectly.
906 // 0---0---0---1---1---1
908 // 0---0---0---1---1---1
910 // 0---0---0---1---1---1
913 // If the AABB for the Left chunk did not share vertices with the Right,
914 // then we would fail collision tests at x due to a gap.
916 for (int z = z0; z < z0 + chunkSize + 1; ++z)
918 if (z >= m_heightStickLength)
923 for (int x = x0; x < x0 + chunkSize + 1; ++x)
925 if (x >= m_heightStickWidth)
930 btScalar height = getRawHeightFieldValue(x, z);
936 else if (height > r.max)
943 m_vboundsGrid[cx + cz * nChunksX] = r;
948 void btHeightfieldTerrainShape::clearAccelerator()
950 m_vboundsGrid.clear();