summaryrefslogtreecommitdiff
path: root/thirdparty
diff options
context:
space:
mode:
Diffstat (limited to 'thirdparty')
-rw-r--r--thirdparty/README.md2
-rw-r--r--thirdparty/assimp/code/FBXConverter.cpp35
-rw-r--r--thirdparty/assimp/code/FBXConverter.h20
-rw-r--r--thirdparty/assimp/code/FBXMaterial.cpp32
-rw-r--r--thirdparty/assimp/code/FBXUtil.cpp44
-rw-r--r--thirdparty/assimp/code/FBXUtil.h15
-rw-r--r--thirdparty/assimp/code/Version.cpp2
-rw-r--r--thirdparty/assimp/include/assimp/material.h1
-rw-r--r--thirdparty/bullet/BulletCollision/CollisionDispatch/btCollisionWorld.cpp19
-rw-r--r--thirdparty/bullet/BulletCollision/CollisionShapes/btHeightfieldTerrainShape.cpp420
-rw-r--r--thirdparty/bullet/BulletCollision/CollisionShapes/btHeightfieldTerrainShape.h21
11 files changed, 589 insertions, 22 deletions
diff --git a/thirdparty/README.md b/thirdparty/README.md
index 815c533645..c98f593920 100644
--- a/thirdparty/README.md
+++ b/thirdparty/README.md
@@ -4,7 +4,7 @@
## assimp
- Upstream: http://github.com/assimp/assimp
-- Version: git (d2b45377e4b09a1f43be95e45553afcc06b03f4b)
+- Version: git (d3d98a7ec0c8d38e1952b46dfe53f7e9233dc92d)
- License: BSD-3-Clause
diff --git a/thirdparty/assimp/code/FBXConverter.cpp b/thirdparty/assimp/code/FBXConverter.cpp
index 000c4ed53b..09ae06a64f 100644
--- a/thirdparty/assimp/code/FBXConverter.cpp
+++ b/thirdparty/assimp/code/FBXConverter.cpp
@@ -78,6 +78,16 @@ namespace Assimp {
FBXConverter::FBXConverter(aiScene* out, const Document& doc)
: defaultMaterialIndex()
+ , lights()
+ , cameras()
+ , textures()
+ , materials_converted()
+ , textures_converted()
+ , meshes_converted()
+ , node_anim_chain_bits()
+ , mNodeNameInstances()
+ , mNodeNames()
+ , anim_fps()
, out(out)
, doc(doc) {
// animations need to be converted first since this will
@@ -410,19 +420,24 @@ namespace Assimp {
void FBXConverter::GetUniqueName(const std::string &name, std::string &uniqueName)
{
- int i = 0;
uniqueName = name;
- while (mNodeNames.find(uniqueName) != mNodeNames.end())
+ int i = 0;
+ auto it = mNodeNameInstances.find(name); // duplicate node name instance count
+ if (it != mNodeNameInstances.end())
{
- ++i;
- std::stringstream ext;
- ext << name << std::setfill('0') << std::setw(3) << i;
- uniqueName = ext.str();
+ i = it->second;
+ while (mNodeNames.find(uniqueName) != mNodeNames.end())
+ {
+ i++;
+ std::stringstream ext;
+ ext << name << std::setfill('0') << std::setw(3) << i;
+ uniqueName = ext.str();
+ }
}
+ mNodeNameInstances[name] = i;
mNodeNames.insert(uniqueName);
}
-
const char* FBXConverter::NameTransformationComp(TransformationComp comp) {
switch (comp) {
case TransformationComp_Translation:
@@ -2041,6 +2056,12 @@ namespace Assimp {
CalculatedOpacity = 1.0f - ((Transparent.r + Transparent.g + Transparent.b) / 3.0f);
}
+ // try to get the transparency factor
+ const float TransparencyFactor = PropertyGet<float>(props, "TransparencyFactor", ok);
+ if (ok) {
+ out_mat->AddProperty(&TransparencyFactor, 1, AI_MATKEY_TRANSPARENCYFACTOR);
+ }
+
// use of TransparencyFactor is inconsistent.
// Maya always stores it as 1.0,
// so we can't use it to set AI_MATKEY_OPACITY.
diff --git a/thirdparty/assimp/code/FBXConverter.h b/thirdparty/assimp/code/FBXConverter.h
index 398baa445f..50637468b9 100644
--- a/thirdparty/assimp/code/FBXConverter.h
+++ b/thirdparty/assimp/code/FBXConverter.h
@@ -58,6 +58,8 @@ OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
#include <assimp/texture.h>
#include <assimp/camera.h>
#include <assimp/StringComparison.h>
+#include <unordered_map>
+#include <unordered_set>
struct aiScene;
struct aiNode;
@@ -74,8 +76,6 @@ namespace FBX {
class Document;
-using NodeNameCache = std::set<std::string>;
-
/**
* Convert a FBX #Document to #aiScene
* @param out Empty scene to be populated
@@ -419,7 +419,6 @@ private:
void TransferDataToScene();
private:
-
// 0: not assigned yet, others: index is value - 1
unsigned int defaultMaterialIndex;
@@ -429,22 +428,27 @@ private:
std::vector<aiLight*> lights;
std::vector<aiCamera*> cameras;
std::vector<aiTexture*> textures;
-
- typedef std::map<const Material*, unsigned int> MaterialMap;
+ using MaterialMap = std::map<const Material*, unsigned int>;
MaterialMap materials_converted;
- typedef std::map<const Video*, unsigned int> VideoMap;
+ using VideoMap = std::map<const Video*, unsigned int>;
VideoMap textures_converted;
- typedef std::map<const Geometry*, std::vector<unsigned int> > MeshMap;
+ using MeshMap = std::map<const Geometry*, std::vector<unsigned int> >;
MeshMap meshes_converted;
// fixed node name -> which trafo chain components have animations?
- typedef std::map<std::string, unsigned int> NodeAnimBitMap;
+ using NodeAnimBitMap = std::map<std::string, unsigned int> ;
NodeAnimBitMap node_anim_chain_bits;
+ // number of nodes with the same name
+ using NodeAnimNameMap = std::unordered_map<std::string, unsigned int>;
+ NodeAnimNameMap mNodeNameInstances;
+
+ using NodeNameCache = std::unordered_set<std::string>;
NodeNameCache mNodeNames;
+
double anim_fps;
aiScene* const out;
diff --git a/thirdparty/assimp/code/FBXMaterial.cpp b/thirdparty/assimp/code/FBXMaterial.cpp
index 08347740fa..f16f134404 100644
--- a/thirdparty/assimp/code/FBXMaterial.cpp
+++ b/thirdparty/assimp/code/FBXMaterial.cpp
@@ -55,6 +55,7 @@ OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
#include <assimp/ByteSwapper.h>
#include <algorithm> // std::transform
+#include "FBXUtil.h"
namespace Assimp {
namespace FBX {
@@ -206,6 +207,20 @@ Texture::Texture(uint64_t id, const Element& element, const Document& doc, const
props = GetPropertyTable(doc,"Texture.FbxFileTexture",element,sc);
+ // 3DS Max and FBX SDK use "Scaling" and "Translation" instead of "ModelUVScaling" and "ModelUVTranslation". Use these properties if available.
+ bool ok;
+ const aiVector3D& scaling = PropertyGet<aiVector3D>(*props, "Scaling", ok);
+ if (ok) {
+ uvScaling.x = scaling.x;
+ uvScaling.y = scaling.y;
+ }
+
+ const aiVector3D& trans = PropertyGet<aiVector3D>(*props, "Translation", ok);
+ if (ok) {
+ uvTrans.x = trans.x;
+ uvTrans.y = trans.y;
+ }
+
// resolve video links
if(doc.Settings().readTextures) {
const std::vector<const Connection*>& conns = doc.GetConnectionsByDestinationSequenced(ID());
@@ -307,7 +322,22 @@ Video::Video(uint64_t id, const Element& element, const Document& doc, const std
const Token& token = GetRequiredToken(*Content, 0);
const char* data = token.begin();
if (!token.IsBinary()) {
- DOMWarning("video content is not binary data, ignoring", &element);
+ if (*data != '"') {
+ DOMError("embedded content is not surrounded by quotation marks", &element);
+ }
+ else {
+ const char* encodedData = data + 1;
+ size_t encodedDataLen = static_cast<size_t>(token.end() - token.begin());
+ // search for last quotation mark
+ while (encodedDataLen > 1 && encodedData[encodedDataLen] != '"')
+ encodedDataLen--;
+ if (encodedDataLen % 4 != 0) {
+ DOMError("embedded content is invalid, needs to be in base64", &element);
+ }
+ else {
+ contentLength = Util::DecodeBase64(encodedData, encodedDataLen, content);
+ }
+ }
}
else if (static_cast<size_t>(token.end() - data) < 5) {
DOMError("binary data array is too short, need five (5) bytes for type signature and element count", &element);
diff --git a/thirdparty/assimp/code/FBXUtil.cpp b/thirdparty/assimp/code/FBXUtil.cpp
index c184c4a00b..fb483161b2 100644
--- a/thirdparty/assimp/code/FBXUtil.cpp
+++ b/thirdparty/assimp/code/FBXUtil.cpp
@@ -49,6 +49,7 @@ OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
#include <assimp/TinyFormatter.h>
#include <string>
+#include <cstring>
#ifndef ASSIMP_BUILD_NO_FBX_IMPORTER
@@ -113,6 +114,49 @@ std::string AddTokenText(const std::string& prefix, const std::string& text, con
text) );
}
+static const uint8_t base64DecodeTable[128] = {
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 62, 0, 0, 0, 63,
+ 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 0, 0, 0, 64, 0, 0,
+ 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
+ 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 0, 0, 0, 0, 0,
+ 0, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40,
+ 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 0, 0, 0, 0, 0
+};
+
+uint8_t DecodeBase64(char ch)
+{
+ return base64DecodeTable[size_t(ch)];
+}
+
+size_t DecodeBase64(const char* in, size_t inLength, uint8_t*& out)
+{
+ if (inLength < 4) {
+ out = 0;
+ return 0;
+ }
+
+ const size_t outLength = (inLength * 3) / 4;
+ out = new uint8_t[outLength];
+ memset(out, 0, outLength);
+
+ size_t i = 0;
+ size_t j = 0;
+ for (i = 0; i < inLength - 4; i += 4)
+ {
+ uint8_t b0 = Util::DecodeBase64(in[i]);
+ uint8_t b1 = Util::DecodeBase64(in[i + 1]);
+ uint8_t b2 = Util::DecodeBase64(in[i + 2]);
+ uint8_t b3 = Util::DecodeBase64(in[i + 3]);
+
+ out[j++] = (uint8_t)((b0 << 2) | (b1 >> 4));
+ out[j++] = (uint8_t)((b1 << 4) | (b2 >> 2));
+ out[j++] = (uint8_t)((b2 << 6) | b3);
+ }
+ return outLength;
+}
+
} // !Util
} // !FBX
} // !Assimp
diff --git a/thirdparty/assimp/code/FBXUtil.h b/thirdparty/assimp/code/FBXUtil.h
index 1a37d346b4..6890e015ba 100644
--- a/thirdparty/assimp/code/FBXUtil.h
+++ b/thirdparty/assimp/code/FBXUtil.h
@@ -48,6 +48,7 @@ OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
#include "FBXCompileConfig.h"
#include "FBXTokenizer.h"
+#include <stdint.h>
namespace Assimp {
namespace FBX {
@@ -98,6 +99,20 @@ std::string AddLineAndColumn(const std::string& prefix, const std::string& text,
* @return A string of the following format: {prefix} ({token-type}, line {line}, col {column}) {text}*/
std::string AddTokenText(const std::string& prefix, const std::string& text, const Token* tok);
+/** Decode a single Base64-encoded character.
+*
+* @param ch Character to decode (from base64 to binary).
+* @return decoded byte value*/
+uint8_t DecodeBase64(char ch);
+
+/** Decode a Base64-encoded string
+*
+* @param in Characters to decode.
+* @param inLength Number of characters to decode.
+* @param out Reference to pointer where we will store the decoded data.
+* @return size of the decoded data (number of bytes)*/
+size_t DecodeBase64(const char* in, size_t inLength, uint8_t*& out);
+
}
}
}
diff --git a/thirdparty/assimp/code/Version.cpp b/thirdparty/assimp/code/Version.cpp
index cc94340ac8..0381037ff1 100644
--- a/thirdparty/assimp/code/Version.cpp
+++ b/thirdparty/assimp/code/Version.cpp
@@ -134,7 +134,7 @@ ASSIMP_API aiScene::aiScene()
, mCameras(nullptr)
, mMetaData(nullptr)
, mPrivate(new Assimp::ScenePrivateData()) {
- // empty
+ // empty
}
// ------------------------------------------------------------------------------------------------
diff --git a/thirdparty/assimp/include/assimp/material.h b/thirdparty/assimp/include/assimp/material.h
index b882bbc72c..4b5a1293dd 100644
--- a/thirdparty/assimp/include/assimp/material.h
+++ b/thirdparty/assimp/include/assimp/material.h
@@ -900,6 +900,7 @@ extern "C" {
#define AI_MATKEY_ENABLE_WIREFRAME "$mat.wireframe",0,0
#define AI_MATKEY_BLEND_FUNC "$mat.blend",0,0
#define AI_MATKEY_OPACITY "$mat.opacity",0,0
+#define AI_MATKEY_TRANSPARENCYFACTOR "$mat.transparencyfactor",0,0
#define AI_MATKEY_BUMPSCALING "$mat.bumpscaling",0,0
#define AI_MATKEY_SHININESS "$mat.shininess",0,0
#define AI_MATKEY_REFLECTIVITY "$mat.reflectivity",0,0
diff --git a/thirdparty/bullet/BulletCollision/CollisionDispatch/btCollisionWorld.cpp b/thirdparty/bullet/BulletCollision/CollisionDispatch/btCollisionWorld.cpp
index 782e9efaf1..b30ce03164 100644
--- a/thirdparty/bullet/BulletCollision/CollisionDispatch/btCollisionWorld.cpp
+++ b/thirdparty/bullet/BulletCollision/CollisionDispatch/btCollisionWorld.cpp
@@ -19,9 +19,10 @@ subject to the following restrictions:
#include "BulletCollision/CollisionShapes/btCollisionShape.h"
#include "BulletCollision/CollisionShapes/btConvexShape.h"
#include "BulletCollision/NarrowPhaseCollision/btGjkEpaPenetrationDepthSolver.h"
-#include "BulletCollision/CollisionShapes/btSphereShape.h" //for raycasting
-#include "BulletCollision/CollisionShapes/btBvhTriangleMeshShape.h" //for raycasting
-#include "BulletCollision/CollisionShapes/btScaledBvhTriangleMeshShape.h" //for raycasting
+#include "BulletCollision/CollisionShapes/btSphereShape.h" //for raycasting
+#include "BulletCollision/CollisionShapes/btBvhTriangleMeshShape.h" //for raycasting
+#include "BulletCollision/CollisionShapes/btScaledBvhTriangleMeshShape.h" //for raycasting
+#include "BulletCollision/CollisionShapes/btHeightfieldTerrainShape.h" //for raycasting
#include "BulletCollision/NarrowPhaseCollision/btRaycastCallback.h"
#include "BulletCollision/CollisionShapes/btCompoundShape.h"
#include "BulletCollision/NarrowPhaseCollision/btSubSimplexConvexCast.h"
@@ -413,6 +414,18 @@ void btCollisionWorld::rayTestSingleInternal(const btTransform& rayFromTrans, co
rcb.m_hitFraction = resultCallback.m_closestHitFraction;
triangleMesh->performRaycast(&rcb, rayFromLocalScaled, rayToLocalScaled);
}
+ else if (collisionShape->getShapeType()==TERRAIN_SHAPE_PROXYTYPE)
+ {
+ ///optimized version for btHeightfieldTerrainShape
+ btHeightfieldTerrainShape* heightField = (btHeightfieldTerrainShape*)collisionShape;
+ btTransform worldTocollisionObject = colObjWorldTransform.inverse();
+ btVector3 rayFromLocal = worldTocollisionObject * rayFromTrans.getOrigin();
+ btVector3 rayToLocal = worldTocollisionObject * rayToTrans.getOrigin();
+
+ BridgeTriangleRaycastCallback rcb(rayFromLocal,rayToLocal,&resultCallback,collisionObjectWrap->getCollisionObject(),heightField,colObjWorldTransform);
+ rcb.m_hitFraction = resultCallback.m_closestHitFraction;
+ heightField->performRaycast(&rcb, rayFromLocal, rayToLocal);
+ }
else
{
//generic (slower) case
diff --git a/thirdparty/bullet/BulletCollision/CollisionShapes/btHeightfieldTerrainShape.cpp b/thirdparty/bullet/BulletCollision/CollisionShapes/btHeightfieldTerrainShape.cpp
index c85ce2498e..4adf27e6bb 100644
--- a/thirdparty/bullet/BulletCollision/CollisionShapes/btHeightfieldTerrainShape.cpp
+++ b/thirdparty/bullet/BulletCollision/CollisionShapes/btHeightfieldTerrainShape.cpp
@@ -73,6 +73,10 @@ void btHeightfieldTerrainShape::initialize(
m_useZigzagSubdivision = false;
m_upAxis = upAxis;
m_localScaling.setValue(btScalar(1.), btScalar(1.), btScalar(1.));
+ m_vboundsGrid = NULL;
+ m_vboundsChunkSize = 0;
+ m_vboundsGridWidth = 0;
+ m_vboundsGridLength = 0;
// determine min/max axis-aligned bounding box (aabb) values
switch (m_upAxis)
@@ -108,6 +112,7 @@ void btHeightfieldTerrainShape::initialize(
btHeightfieldTerrainShape::~btHeightfieldTerrainShape()
{
+ clearAccelerator();
}
void btHeightfieldTerrainShape::getAabb(const btTransform& t, btVector3& aabbMin, btVector3& aabbMax) const
@@ -323,6 +328,8 @@ void btHeightfieldTerrainShape::processAllTriangles(btTriangleCallback* callback
}
}
+ // TODO If m_vboundsGrid is available, use it to determine if we really need to process this area
+
for (int j = startJ; j < endJ; j++)
{
for (int x = startX; x < endX; x++)
@@ -373,3 +380,416 @@ const btVector3& btHeightfieldTerrainShape::getLocalScaling() const
{
return m_localScaling;
}
+
+
+
+struct GridRaycastState
+{
+ int x; // Next quad coords
+ int z;
+ int prev_x; // Previous quad coords
+ int prev_z;
+ btScalar param; // Exit param for previous quad
+ btScalar prevParam; // Enter param for previous quad
+ btScalar maxDistanceFlat;
+ btScalar maxDistance3d;
+};
+
+
+// TODO Does it really need to take 3D vectors?
+/// Iterates through a virtual 2D grid of unit-sized square cells,
+/// and executes an action on each cell intersecting the given segment, ordered from begin to end.
+/// Initially inspired by http://www.cse.yorku.ca/~amana/research/grid.pdf
+template <typename Action_T>
+void gridRaycast(Action_T &quadAction, const btVector3 &beginPos, const btVector3 &endPos)
+{
+ GridRaycastState rs;
+ rs.maxDistance3d = beginPos.distance(endPos);
+ if (rs.maxDistance3d < 0.0001)
+ // Consider the ray is too small to hit anything
+ return;
+
+ btScalar rayDirectionFlatX = endPos[0] - beginPos[0];
+ btScalar rayDirectionFlatZ = endPos[2] - beginPos[2];
+ rs.maxDistanceFlat = btSqrt(rayDirectionFlatX * rayDirectionFlatX + rayDirectionFlatZ * rayDirectionFlatZ);
+
+ if(rs.maxDistanceFlat < 0.0001)
+ {
+ // Consider the ray vertical
+ rayDirectionFlatX = 0;
+ rayDirectionFlatZ = 0;
+ }
+ else
+ {
+ rayDirectionFlatX /= rs.maxDistanceFlat;
+ rayDirectionFlatZ /= rs.maxDistanceFlat;
+ }
+
+ const int xiStep = rayDirectionFlatX > 0 ? 1 : rayDirectionFlatX < 0 ? -1 : 0;
+ const int ziStep = rayDirectionFlatZ > 0 ? 1 : rayDirectionFlatZ < 0 ? -1 : 0;
+
+ const float infinite = 9999999;
+ const btScalar paramDeltaX = xiStep != 0 ? 1.f / btFabs(rayDirectionFlatX) : infinite;
+ const btScalar paramDeltaZ = ziStep != 0 ? 1.f / btFabs(rayDirectionFlatZ) : infinite;
+
+ // pos = param * dir
+ btScalar paramCrossX; // At which value of `param` we will cross a x-axis lane?
+ btScalar paramCrossZ; // At which value of `param` we will cross a z-axis lane?
+
+ // paramCrossX and paramCrossZ are initialized as being the first cross
+ // X initialization
+ if (xiStep != 0)
+ {
+ if (xiStep == 1)
+ paramCrossX = (ceil(beginPos[0]) - beginPos[0]) * paramDeltaX;
+ else
+ paramCrossX = (beginPos[0] - floor(beginPos[0])) * paramDeltaX;
+ }
+ else
+ paramCrossX = infinite; // Will never cross on X
+
+ // Z initialization
+ if (ziStep != 0)
+ {
+ if (ziStep == 1)
+ paramCrossZ = (ceil(beginPos[2]) - beginPos[2]) * paramDeltaZ;
+ else
+ paramCrossZ = (beginPos[2] - floor(beginPos[2])) * paramDeltaZ;
+ }
+ else
+ paramCrossZ = infinite; // Will never cross on Z
+
+ rs.x = static_cast<int>(floor(beginPos[0]));
+ rs.z = static_cast<int>(floor(beginPos[2]));
+
+ // Workaround cases where the ray starts at an integer position
+ if (paramCrossX == 0.0)
+ {
+ paramCrossX += paramDeltaX;
+ // If going backwards, we should ignore the position we would get by the above flooring,
+ // because the ray is not heading in that direction
+ if (xiStep == -1)
+ rs.x -= 1;
+ }
+
+ if (paramCrossZ == 0.0)
+ {
+ paramCrossZ += paramDeltaZ;
+ if (ziStep == -1)
+ rs.z -= 1;
+ }
+
+ rs.prev_x = rs.x;
+ rs.prev_z = rs.z;
+ rs.param = 0;
+
+ while (true)
+ {
+ rs.prev_x = rs.x;
+ rs.prev_z = rs.z;
+ rs.prevParam = rs.param;
+
+ if (paramCrossX < paramCrossZ)
+ {
+ // X lane
+ rs.x += xiStep;
+ // Assign before advancing the param,
+ // to be in sync with the initialization step
+ rs.param = paramCrossX;
+ paramCrossX += paramDeltaX;
+ }
+ else
+ {
+ // Z lane
+ rs.z += ziStep;
+ rs.param = paramCrossZ;
+ paramCrossZ += paramDeltaZ;
+ }
+
+ if (rs.param > rs.maxDistanceFlat)
+ {
+ rs.param = rs.maxDistanceFlat;
+ quadAction(rs);
+ break;
+ }
+ else
+ quadAction(rs);
+ }
+}
+
+
+struct ProcessTrianglesAction
+{
+ const btHeightfieldTerrainShape *shape;
+ bool flipQuadEdges;
+ bool useDiamondSubdivision;
+ int width;
+ int length;
+ btTriangleCallback* callback;
+
+ void exec(int x, int z) const
+ {
+ if(x < 0 || z < 0 || x >= width || z >= length)
+ return;
+
+ btVector3 vertices[3];
+
+ // Check quad
+ if (flipQuadEdges || (useDiamondSubdivision && (((z + x) & 1) > 0)))
+ {
+ // First triangle
+ shape->getVertex(x, z, vertices[0]);
+ shape->getVertex(x + 1, z, vertices[1]);
+ shape->getVertex(x + 1, z + 1, vertices[2]);
+ callback->processTriangle(vertices, x, z);
+
+ // Second triangle
+ shape->getVertex(x, z, vertices[0]);
+ shape->getVertex(x + 1, z + 1, vertices[1]);
+ shape->getVertex(x, z + 1, vertices[2]);
+ callback->processTriangle(vertices, x, z);
+ }
+ else
+ {
+ // First triangle
+ shape->getVertex(x, z, vertices[0]);
+ shape->getVertex(x, z + 1, vertices[1]);
+ shape->getVertex(x + 1, z, vertices[2]);
+ callback->processTriangle(vertices, x, z);
+
+ // Second triangle
+ shape->getVertex(x + 1, z, vertices[0]);
+ shape->getVertex(x, z + 1, vertices[1]);
+ shape->getVertex(x + 1, z + 1, vertices[2]);
+ callback->processTriangle(vertices, x, z);
+ }
+ }
+
+ void operator ()(const GridRaycastState &bs) const
+ {
+ exec(bs.prev_x, bs.prev_z);
+ }
+};
+
+
+struct ProcessVBoundsAction
+{
+ const btHeightfieldTerrainShape::Range *vbounds;
+ int width;
+ int length;
+ int chunkSize;
+
+ btVector3 rayBegin;
+ btVector3 rayEnd;
+ btVector3 rayDir;
+
+ ProcessTrianglesAction processTriangles;
+
+ void operator ()(const GridRaycastState &rs) const
+ {
+ int x = rs.prev_x;
+ int z = rs.prev_z;
+
+ if(x < 0 || z < 0 || x >= width || z >= length)
+ return;
+
+ const btHeightfieldTerrainShape::Range chunk = vbounds[x + z * width];
+
+ btVector3 enterPos;
+ btVector3 exitPos;
+
+ if (rs.maxDistanceFlat > 0.0001)
+ {
+ btScalar flatTo3d = chunkSize * rs.maxDistance3d / rs.maxDistanceFlat;
+ btScalar enterParam3d = rs.prevParam * flatTo3d;
+ btScalar exitParam3d = rs.param * flatTo3d;
+ enterPos = rayBegin + rayDir * enterParam3d;
+ exitPos = rayBegin + rayDir * exitParam3d;
+
+ // We did enter the flat projection of the AABB,
+ // but we have to check if we intersect it on the vertical axis
+ if (enterPos[1] > chunk.max && exitPos[1] > chunk.max)
+ return;
+ if (enterPos[1] < chunk.min && exitPos[1] < chunk.min)
+ return;
+ }
+ else
+ {
+ // Consider the ray vertical
+ // (though we shouldn't reach this often because there is an early check up-front)
+ enterPos = rayBegin;
+ exitPos = rayEnd;
+ }
+
+ gridRaycast(processTriangles, enterPos, exitPos);
+ // Note: it could be possible to have more than one grid at different levels,
+ // to do this there would be a branch using a pointer to another ProcessVBoundsAction
+ }
+};
+
+
+// TODO How do I interrupt the ray when there is a hit? `callback` does not return any result
+/// Performs a raycast using a hierarchical Bresenham algorithm.
+/// Does not allocate any memory by itself.
+void btHeightfieldTerrainShape::performRaycast(btTriangleCallback* callback, const btVector3& raySource, const btVector3& rayTarget) const
+{
+ // Transform to cell-local
+ btVector3 beginPos = raySource / m_localScaling;
+ btVector3 endPos = rayTarget / m_localScaling;
+ beginPos += m_localOrigin;
+ endPos += m_localOrigin;
+
+ ProcessTrianglesAction processTriangles;
+ processTriangles.shape = this;
+ processTriangles.flipQuadEdges = m_flipQuadEdges;
+ processTriangles.useDiamondSubdivision = m_useDiamondSubdivision;
+ processTriangles.callback = callback;
+ processTriangles.width = m_heightStickWidth - 1;
+ processTriangles.length = m_heightStickLength - 1;
+
+ // TODO Transform vectors to account for m_upAxis
+ int iBeginX = static_cast<int>(floor(beginPos[0]));
+ int iBeginZ = static_cast<int>(floor(beginPos[2]));
+ int iEndX = static_cast<int>(floor(endPos[0]));
+ int iEndZ = static_cast<int>(floor(endPos[2]));
+
+ if (iBeginX == iEndX && iBeginZ == iEndZ)
+ {
+ // The ray will never cross quads within the plane,
+ // so directly process triangles within one quad
+ // (typically, vertical rays should end up here)
+ processTriangles.exec(iBeginX, iEndZ);
+ return;
+ }
+
+ if (m_vboundsGrid == NULL)
+ {
+ // Process all quads intersecting the flat projection of the ray
+ gridRaycast(processTriangles, beginPos, endPos);
+ }
+ else
+ {
+ btVector3 rayDiff = endPos - beginPos;
+ btScalar flatDistance2 = rayDiff[0] * rayDiff[0] + rayDiff[2] * rayDiff[2];
+ if (flatDistance2 < m_vboundsChunkSize * m_vboundsChunkSize)
+ {
+ // Don't use chunks, the ray is too short in the plane
+ gridRaycast(processTriangles, beginPos, endPos);
+ }
+
+ ProcessVBoundsAction processVBounds;
+ processVBounds.width = m_vboundsGridWidth;
+ processVBounds.length = m_vboundsGridLength;
+ processVBounds.vbounds = m_vboundsGrid;
+ processVBounds.rayBegin = beginPos;
+ processVBounds.rayEnd = endPos;
+ processVBounds.rayDir = rayDiff.normalized();
+ processVBounds.processTriangles = processTriangles;
+ processVBounds.chunkSize = m_vboundsChunkSize;
+ // The ray is long, run raycast on a higher-level grid
+ gridRaycast(processVBounds, beginPos / m_vboundsChunkSize, endPos / m_vboundsChunkSize);
+ }
+}
+
+
+/// Builds a grid data structure storing the min and max heights of the terrain in chunks.
+/// if chunkSize is zero, that accelerator is removed.
+/// If you modify the heights, you need to rebuild this accelerator.
+void btHeightfieldTerrainShape::buildAccelerator(int chunkSize)
+{
+ if (chunkSize <= 0)
+ {
+ clearAccelerator();
+ return;
+ }
+
+ m_vboundsChunkSize = chunkSize;
+ int nChunksX = m_heightStickWidth / chunkSize;
+ int nChunksZ = m_heightStickLength / chunkSize;
+
+ if (m_heightStickWidth % chunkSize > 0)
+ ++nChunksX; // In case terrain size isn't dividable by chunk size
+ if (m_heightStickLength % chunkSize > 0)
+ ++nChunksZ;
+
+ if(m_vboundsGridWidth != nChunksX || m_vboundsGridLength != nChunksZ)
+ {
+ clearAccelerator();
+ m_vboundsGridWidth = nChunksX;
+ m_vboundsGridLength = nChunksZ;
+ }
+
+ if (nChunksX == 0 || nChunksZ == 0)
+ return;
+
+ // TODO What is the recommended way to allocate this?
+ // This data structure is only reallocated if the required size changed
+ if (m_vboundsGrid == NULL)
+ m_vboundsGrid = new Range[nChunksX * nChunksZ];
+
+ // Compute min and max height for all chunks
+ for (int cz = 0; cz < nChunksZ; ++cz)
+ {
+ int z0 = cz * chunkSize;
+
+ for (int cx = 0; cx < nChunksX; ++cx)
+ {
+ int x0 = cx * chunkSize;
+
+ Range r;
+
+ r.min = getRawHeightFieldValue(x0, z0);
+ r.max = r.min;
+
+ // Compute min and max height for this chunk.
+ // We have to include one extra cell to account for neighbors.
+ // Here is why:
+ // Say we have a flat terrain, and a plateau that fits a chunk perfectly.
+ //
+ // Left Right
+ // 0---0---0---1---1---1
+ // | | | | | |
+ // 0---0---0---1---1---1
+ // | | | | | |
+ // 0---0---0---1---1---1
+ // x
+ //
+ // If the AABB for the Left chunk did not share vertices with the Right,
+ // then we would fail collision tests at x due to a gap.
+ //
+ for (int z = z0; z < z0 + chunkSize + 1; ++z)
+ {
+ if (z >= m_heightStickLength)
+ continue;
+
+ for (int x = x0; x < x0 + chunkSize + 1; ++x)
+ {
+ if (x >= m_heightStickWidth)
+ continue;
+
+ btScalar height = getRawHeightFieldValue(x, z);
+
+ if (height < r.min)
+ r.min = height;
+ else if (height > r.max)
+ r.max = height;
+ }
+ }
+
+ m_vboundsGrid[cx + cz * nChunksX] = r;
+ }
+ }
+}
+
+
+void btHeightfieldTerrainShape::clearAccelerator()
+{
+ if (m_vboundsGrid)
+ {
+ // TODO What is the recommended way to deallocate this?
+ delete[] m_vboundsGrid;
+ m_vboundsGrid = 0;
+ }
+}
+
+
diff --git a/thirdparty/bullet/BulletCollision/CollisionShapes/btHeightfieldTerrainShape.h b/thirdparty/bullet/BulletCollision/CollisionShapes/btHeightfieldTerrainShape.h
index 8a50a57e31..e23b548cb2 100644
--- a/thirdparty/bullet/BulletCollision/CollisionShapes/btHeightfieldTerrainShape.h
+++ b/thirdparty/bullet/BulletCollision/CollisionShapes/btHeightfieldTerrainShape.h
@@ -18,6 +18,7 @@ subject to the following restrictions:
#include "btConcaveShape.h"
+
///btHeightfieldTerrainShape simulates a 2D heightfield terrain
/**
The caller is responsible for maintaining the heightfield array; this
@@ -71,6 +72,12 @@ subject to the following restrictions:
ATTRIBUTE_ALIGNED16(class)
btHeightfieldTerrainShape : public btConcaveShape
{
+public:
+ struct Range {
+ btScalar min;
+ btScalar max;
+ };
+
protected:
btVector3 m_localAabbMin;
btVector3 m_localAabbMax;
@@ -100,9 +107,14 @@ protected:
btVector3 m_localScaling;
+ // Accelerator
+ Range *m_vboundsGrid;
+ int m_vboundsGridWidth;
+ int m_vboundsGridLength;
+ int m_vboundsChunkSize;
+
virtual btScalar getRawHeightFieldValue(int x, int y) const;
void quantizeWithClamp(int* out, const btVector3& point, int isMax) const;
- void getVertex(int x, int y, btVector3& vertex) const;
/// protected initialization
/**
@@ -154,6 +166,13 @@ public:
virtual void setLocalScaling(const btVector3& scaling);
virtual const btVector3& getLocalScaling() const;
+
+ void getVertex(int x,int y,btVector3& vertex) const;
+
+ void performRaycast (btTriangleCallback* callback, const btVector3& raySource, const btVector3& rayTarget) const;
+
+ void buildAccelerator(int chunkSize=16);
+ void clearAccelerator();
//debugging
virtual const char* getName() const { return "HEIGHTFIELD"; }
generated by cgit v1.2.3 (git 2.25.1) at 2026-01-05 05:07:32 +0000