Box (instead of ray) tracing?

[IneQuation]

I guess this topic belongs here.

Well, I'm trying to incorporate Bullet into the Quake III Arena engine to replace the old Q3 collision map and ultra-simplified physics. I've got most of the work already done thanks to the BSP demo (I use a heavily modified version of it - I extended it to load patch meshes and terrain (the game I'm working on will have heightfield terrain) as concave shapes and additional info like content/surface flags), but there's still one component that needs to be replaced - the tracing. The thing is, Q3 uses box-, not raytracing. Well, it can also do raytracing, but then it's just a cube with [0, 0, 0] extents that's used. This box can also be transformed (i.e. euler angles can be passed; still, they are only used to produce an AABB that is used instead of the non-transformed box; Bullet has an advantage here because it can do true shape transformation and use it in collision detection). The trace result (endpos) is the origin of the cast box. I thought that Bullet's convex casting could replace this.

I modified the rayTest and rayTestSingle to meet these requirements, but the code below does not work as intended. I don't quite understand most of the inner workings of Bullet, so please excuse my lameness. Basically what I've done is to replace all pointShapes with traceBox and shove the rayFrom transform wherever I thought it was appropriate (I may have chosen the wrong places, though ). Also, for collision against concave shapes I snatched a snippet of code from convexConcave collision detection algorithm's calculateTimeOfImpact.

One primary problem I can see is the btRayAabb checking. How would I go about a similar thing for a box?

I'd be really grateful if anyone could take a look at this and tell me whether I've done the job right.

Don't mind the content/surface flags retrieving code, of that part I'm perfectly sure it's right.

Code: Select all

/*
Bullet Continuous Collision Detection and Physics Library
Copyright (c) 2003-2006 Erwin Coumans  http://continuousphysics.com/Bullet/

This software is provided 'as-is', without any express or implied warranty.
In no event will the authors be held liable for any damages arising from the use of this software.
Permission is granted to anyone to use this software for any purpose,
including commercial applications, and to alter it and redistribute it freely,
subject to the following restrictions:

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.
2. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software.
3. This notice may not be removed or altered from any source distribution.
*/

// bt_trace.cpp - Q3 clip map tracing replacement module
// utilizes Bullet collision while providing an interface similar to CM

#include "bt_local.h"

SIMD_FORCE_INLINE void BT_TraceSingleTest(const btTransform& rayFrom, const btTransform& rayTo,
	btCollisionObject* collisionObject,
	const btCollisionShape* collisionShape,
	btConvexShape* traceBox,
	const btTransform& colObjWorldTransform,
	btCollisionWorld::RayResultCallback& resultCallback) {

	if (collisionShape->isConvex()) {
		btConvexCast::CastResult castResult;
		castResult.m_fraction = btScalar(1);

		btConvexShape* convexShape = (btConvexShape*) collisionShape;
		btVoronoiSimplexSolver	simplexSolver;
		btSubsimplexConvexCast convexCaster(traceBox, convexShape, &simplexSolver);

		if (convexCaster.calcTimeOfImpact(rayFrom, rayTo, colObjWorldTransform, colObjWorldTransform, castResult)) {
			//add hit
			if (castResult.m_normal.length2() > btScalar(0.0001)) {
				castResult.m_normal.normalize();
				if (castResult.m_fraction < resultCallback.m_closestHitFraction) {
					btCollisionWorld::LocalRayResult localRayResult
						(
							collisionObject,
							0,
							castResult.m_normal,
							castResult.m_fraction
						);
					resultCallback.AddSingleResult(localRayResult);
				}
			}
		}
	} else {
		if (collisionShape->isConcave()) {
			btTriangleMeshShape* triangleMesh = (btTriangleMeshShape*)collisionShape;

			btTransform worldTocollisionObject = colObjWorldTransform.inverse();

			btTransform rayFromLocal = worldTocollisionObject * rayFrom;
			btTransform rayToLocal = worldTocollisionObject * rayTo;

			struct LocalTriangleSphereCastCallback	: public btTriangleCallback {
				btTransform m_ccdSphereFromTrans;
				btTransform m_ccdSphereToTrans;
				btTransform	m_meshTransform;

				btScalar	m_ccdSphereRadius;
				btScalar	m_hitFraction;

				btVector3	m_normal;

				LocalTriangleSphereCastCallback(const btTransform& from,
					const btTransform& to, btScalar ccdSphereRadius,
					btScalar hitFraction)
					:m_ccdSphereFromTrans(from),
					m_ccdSphereToTrans(to),
					m_ccdSphereRadius(ccdSphereRadius),
					m_hitFraction(hitFraction)
				{
				}

				virtual void processTriangle(btVector3* triangle, int partId, int triangleIndex) {
					//do a swept sphere for now
					btTransform ident;
					ident.setIdentity();
					btConvexCast::CastResult castResult;
					castResult.m_fraction = m_hitFraction;
					btSphereShape	pointShape(m_ccdSphereRadius);
					btTriangleShape	triShape(triangle[0],triangle[1],triangle[2]);
					btVoronoiSimplexSolver	simplexSolver;
					btSubsimplexConvexCast convexCaster(&pointShape,&triShape,&simplexSolver);
					if (convexCaster.calcTimeOfImpact(m_ccdSphereFromTrans, m_ccdSphereToTrans,
						ident, ident, castResult)) {
						if (m_hitFraction > castResult.m_fraction) {
							m_hitFraction = castResult.m_fraction;
							m_normal = castResult.m_normal;
						}
					}
				}
			};

			btVector3 rayAabbMin = rayFromLocal.getOrigin();
			rayAabbMin.setMin(rayToLocal.getOrigin());
			btVector3 rayAabbMax = rayFromLocal.getOrigin();
			rayAabbMax.setMax(rayToLocal.getOrigin());
			/*btScalar ccdRadius0 = traceBox->getCcdSweptSphereRadius();
			rayAabbMin -= btVector3(ccdRadius0,ccdRadius0,ccdRadius0);
			rayAabbMax += btVector3(ccdRadius0,ccdRadius0,ccdRadius0);*/

			//btScalar curHitFraction = btScalar(1.); //is this available?
			LocalTriangleSphereCastCallback raycastCallback(rayFromLocal, rayToLocal,
				/*traceBox->getCcdSweptSphereRadius()*/0.f, (resultCallback.m_closestHitFraction));

			//raycastCallback.m_hitFraction = convexbody->getHitFraction();

			triangleMesh->processAllTriangles(&raycastCallback, rayAabbMin, rayAabbMax);

			if (raycastCallback.m_normal.length2() > btScalar(0.0001)) {
				raycastCallback.m_normal.normalize();
				if (raycastCallback.m_hitFraction < resultCallback.m_closestHitFraction) {
					btCollisionWorld::LocalRayResult localRayResult
						(
							collisionObject,
							0,
							raycastCallback.m_normal,
							raycastCallback.m_hitFraction
						);
					resultCallback.AddSingleResult(localRayResult);
				}
			}
		} else {
			//todo: use AABB tree or other BVH acceleration structure!
			if (collisionShape->isCompound()) {
				const btCompoundShape* compoundShape = static_cast<const btCompoundShape*>(collisionShape);
				for (int j = 0; j < compoundShape->getNumChildShapes(); j++) {
					btTransform childTrans = compoundShape->getChildTransform(j);
					const btCollisionShape* childCollisionShape = compoundShape->getChildShape(j);
					btTransform childWorldTrans = colObjWorldTransform * childTrans;
					BT_TraceSingleTest(rayFrom, rayTo,
						collisionObject,
						childCollisionShape,
						traceBox,
						childWorldTrans,
						resultCallback);
				}
			}
		}
	}
}

// this function replaces the functionality of CM_BoxTrace and CM_TransformedBoxTrace
// can pass NULL for the optional parametres (i.e. mins, maxs, origin or angles)
void BT_BoxTrace(trace_t *results, const vec3_t start, const vec3_t mins, const vec3_t maxs, const vec3_t end, int passEntityNum, int contentmask, const vec3_t origin, const vec3_t angles, int capsule) {
	btVector3	extents(0, 0, 0);
	btVector3	offset(0, 0, 0);
	btTransform	rayFrom;
	btTransform	rayTo;

	// handle dimensions
	if (mins && maxs) {
		// ensure symmetric mins and maxs and derive extents for a box shape for them
		offset[0] = (mins[0] + maxs[0]) * 0.5;
		offset[1] = (mins[1] + maxs[1]) * 0.5;
		offset[2] = (mins[2] + maxs[2]) * 0.5;
		extents = btVector3(maxs[0], maxs[1], maxs[2]) - offset;
		extents[0] = btFabs(extents[0]);
		extents[1] = btFabs(extents[0]);
		extents[2] = btFabs(extents[0]);
		rayFrom.setOrigin(btVector3(start[0], start[1], start[2]) + offset);
		rayTo.setOrigin(btVector3(end[0], end[1], end[2]) + offset);
	} else {
		rayFrom.setOrigin(btVector3(start[0], start[1], start[2]));
		rayTo.setOrigin(btVector3(end[0], end[1], end[2]));
	}

	// mimicking CM_TransformedBoxTrace behaviour - apply origin offset (wtf is this for?)
	if (origin != NULL) {
		rayFrom.setOrigin(rayFrom.getOrigin() - btVector3(origin[0], origin[1], origin[2]));
		rayTo.setOrigin(rayTo.getOrigin() - btVector3(origin[0], origin[1], origin[2]));
	}

	// handle rotation -> produce the trace box transform
	if (angles != NULL) {
		rayFrom.setIdentity();
		rayTo.setIdentity();
	} else {
		btMatrix3x3	tm;
		tm.setEulerYPR(angles[1], angles[0], angles[2]);
		rayFrom.setBasis(tm);
		rayTo.setBasis(tm);
	}

	// initialize the trace struct
	Com_Memset(&results, 0, sizeof(*results));
	results->fraction = 1.f;
	VectorCopy(end, results->endpos);
	results->entityNum = ENTITYNUM_WORLD;

	// these are filled each time a trace ends with a shorter fraction
	// they are used after the loop to fill the trace_t
	float		frac;
	vec3_t		endpos, normal;
	btRigidBody	*hitbody;

	gameInfo_t *gi;

	// do the actual tracing
	btBoxShape traceBox(extents);
	// based on btCollisionWorld::rayTest and btCollisionWorld::rayTestSingle
	// go over all objects, and if the ray intersects their aabb, do a ray-shape query using convexCaster (CCD)
	for (int i = 0; i < dynamicsWorld->getNumCollisionObjects(); i++) {
		btCollisionObject *collisionObject = dynamicsWorld->getCollisionObjectArray()[i];

		btVector3 collisionObjectAabbMin, collisionObjectAabbMax;
		collisionObject->getCollisionShape()->getAabb(collisionObject->getWorldTransform(), collisionObjectAabbMin, collisionObjectAabbMax);

		btScalar hitLambda = btScalar(1); //could use resultCallback.m_closestHitFraction, but needs testing
		btVector3 hitNormal;

		btCollisionWorld::ClosestRayResultCallback resultCallback(rayFrom.getOrigin(), rayTo.getOrigin());

		gi = (gameInfo_t *)collisionObject->getUserPointer();
		// compare object AABBs and content flags
		if (btRayAabb(rayFrom.getOrigin(), rayTo.getOrigin(), collisionObjectAabbMin, collisionObjectAabbMax, hitLambda, hitNormal)
			&& contentmask & gi->contentflags) {
			BT_TraceSingleTest(rayFrom, rayTo, collisionObject, collisionObject->getCollisionShape(), &traceBox,
				collisionObject->getWorldTransform(), resultCallback);
			if (resultCallback.m_closestHitFraction < results->fraction) {
				// copy new stuff over
				frac = resultCallback.m_closestHitFraction;
				VectorCopy(resultCallback.m_hitPointWorld, endpos);
				VectorCopy(resultCallback.m_hitNormalWorld, normal);
				hitbody = (btRigidBody *)collisionObject;
			}
		}
	}
	gi = (gameInfo_t *)hitbody->getUserPointer();;
	results->fraction = frac;
	VectorCopy(endpos, results->endpos);
	results->entityNum = gi->entnum;
	VectorCopy(normal, results->plane.normal);
	results->plane.type = PlaneTypeForNormal(results->plane.normal);
	results->contents = gi->contentflags;
	if (gi->entnum == ENTITYNUM_WORLD) {
		if (gi->type == WB_BRUSH) {
			btVector3 compare;
			int j;
			for (j = 0; j < gi->numSides; j++) {
				VectorSubtract(gi->sides[j].normal, results->plane.normal, compare);
				if (compare.length() <= SIMD_EPSILON) {
					results->surfaceFlags = gi->sides[j].surfaceflags;
					break;
				}
			}
			if (j == gi->numSides)
				bi.Printf("BT_Trace: WARNING: Could not determine surface flags at ( %f %f %f )\n",
					results->endpos[0], results->endpos[1], results->endpos[2]);
		} else if (gi->type == WB_TERRAIN) {
			// terrain
			// find the 4 closest pixels to the impact point
			// a fancy method (c) me :)
			vec2_t point = {results->endpos[0] / terrainScale[0], results->endpos[1] / terrainScale[1]};
			int pixels[4];
			pixels[0] = TERSURFFLAGS((int)floorf(point[0]),	(int)floorf(point[1]));
			pixels[1] = TERSURFFLAGS((int)ceilf(point[0]),	(int)floorf(point[1]));
			pixels[2] = TERSURFFLAGS((int)floorf(point[0]),	(int)ceilf(point[1]));
			pixels[3] = TERSURFFLAGS((int)ceilf(point[0]),	(int)ceilf(point[1]));
			if (pixels[0] == pixels[1] && pixels[0] == pixels[2] && pixels[0] == pixels[3])
				// ok, that's easy, just shove the surface flags and let's proceed
				results->surfaceFlags = pixels[0];
			else { // weigh the pixels and pick the one with most weight
				float weights[4], least = 2.f; // can't be more than sqrt(2) anyway
				int index = 0;
				// actually, these would be weights (in 0..1) range if we did
				// (sqrtf(2) - sqrtf(floorf) etc.) / sqrtf(2),
				// but we don't want the overhead; therefore the one we want
				// will be the one with least, not most, weight
				weights[0] = sqrtf(floorf(point[0])	* floorf(point[0])	+ floorf(point[1])	* floorf(point[1]));
				weights[1] = sqrtf(ceilf(point[0])	* ceilf(point[0])	+ floorf(point[1])	* floorf(point[1]));
				weights[2] = sqrtf(floorf(point[0])	* floorf(point[0])	+ ceilf(point[1])	* ceilf(point[1]));
				weights[3] = sqrtf(ceilf(point[0])	* ceilf(point[0])	+ ceilf(point[1])	* ceilf(point[1]));
				for (int j = 0; j < 4; j++) {
					if (weights[j] < least) {
						least = weights[j];
						index = j;
					}
				}
				results->surfaceFlags = pixels[index];
			}
		} else if (gi->type == WB_PATCH)
			results->surfaceFlags = *((int *)gi->sides);
	}
	// remove the offset
	VectorSubtract(results->endpos, offset, results->endpos);
} 

Huge thanks in advance!

IneQuation

[Erwin Coumans]

The Bullet convex cast should provide what you need. The functionality might not be the same in case the objects are touching. This can be worked out.

but the code below does not work as intended

Can you be more specific and give some details what is not working as intended?

Thanks,
Erwin

[IneQuation]

I'm not sure, the endpos can be quite a way off from where it should be. Plus there's the problem of selecting bodies based on their AABB - I switched it off for the time being, but I'm not sure how would I go about writing a function like btBoxAabb instead of btRayAabb.

[IneQuation]

Hello there,

I've just come back to working on this project and due to memory errors that pested my previous code I decided to rewrite it from scratch. Well, not exactly this part, but the BSP loading code is mostly new. Now that the pointer crashes are gone I have another problem - the subsimplex convex caster doesn't seem to work properly. It just doesn't detect any collision. I'll elaborate on that in a moment. The problematic part of code follows.

This is how the box that's swept through the world is initialized:

Code: Select all

	btBoxShape traceBox(extents);
	//btSphereShape traceBox(0.f);
	traceBox.setMargin(0.f); 

Why the commented sphere shape line? I was trying various ways to find out why this isn't working, and tried forcing ray- instead of box traces, just for testing, since it worked in the demos. And the 'point shape' turned out a half-success, that is, when e.g. the player falls down from the air onto a platform, the trace succeeds and hits the platform and they can stand on it for the first 4-5 frames, but then it somehow gets through and they start falling through it anyway. As soon as I put the box shape back in it stops working altogether. I've tried subtracting the margin from the box extents, but still no avail. I've been debugging the code for some time already and I'm 100% sure that all the other things, specifically the rayFrom, rayTo and colObjWorldTransform transforms and the shape pointers are OK and the calcTimeOfImpact call always returning false is the source of the problem. I'm using Bullet 2.53.

The map is comprised of brushes only, and I'm not populating the world with entities yet, so the only collision case case is box shape vs convex hull.

Code: Select all

	if (collisionShape->isConvex()) {
		btConvexCast::CastResult castResult;
		castResult.m_fraction = btScalar(1);

		btConvexShape* convexShape = (btConvexShape*) collisionShape;
		btVoronoiSimplexSolver	simplexSolver;
		btSubsimplexConvexCast convexCaster(traceBox, convexShape, &simplexSolver);

		btVector3 mins, maxs;
		traceBox->getAabb(rayFrom, mins, maxs);

		if (convexCaster.calcTimeOfImpact(rayFrom, rayTo, colObjWorldTransform, colObjWorldTransform, castResult)) {
			//add hit
			if (castResult.m_normal.length2() > btScalar(0.0001)) {
				castResult.m_normal.normalize();
				if (castResult.m_fraction < resultCallback.m_closestHitFraction) {
					btCollisionWorld::LocalRayResult localRayResult
						(
							collisionObject,
							0,
							castResult.m_normal,
							castResult.m_fraction
						);
					resultCallback.AddSingleResult(localRayResult);
				}
			}
		}
	}

Perhaps using the algebraic CCD would be a workaround for this problem?

[IneQuation]

Bump!

[slithEToves]

I have been using this code extensively, and it works as it is supposed to with the exception of the normal direction.

Other than this issue, I have tested this code against many different convex shape types and have had no issues once I fed my data to Bullet correctly. Note that this last point is somewhat trickier than it may seem at first.

Also, if you need the actual contact point rather than the time of impact, you can get this by using btGjkPairDetector with the cast object transformed to the location determined by the TOI.

For a fix to the normal issue, see below:

If you upgrade to 2.55, there is a new parameter to AddSingleResult that specifies whether the normal is in world space, and then doesn't transform the normal if it is. This is fine for ray casts, but for object casts where the object is transformed, it doesn't work correctly because the calculation is done in the cast object's space, not the hit object's space as is the case for concave collisions.

Try adding these lines

castResult.m_normal = rayFromTrans.getBasis()*castResult.m_normal;
castResult.m_normal.normalize();

above

btCollisionWorld::LocalRayResult localRayResult
(
collisionObject,
0,
castResult.m_normal,
castResult.m_fraction
);

bool normalInWorldSpace = true; resultCallback.AddSingleResult(localRayResult, normalInWorldSpace);

Then remove the other normalize call that is no longer needed. This should fix the normal. If this fix works for you, please respond as such so we have an independent verification of the fix. Thanks!

[IneQuation]

OK, so it seems there's an error on my end. Thanks for verifying the code, it clears some things up. I'll apply your normal fix and get back with the result.