Quake2: Deficiency in Cm_TransformedBoxTrace

Discuss programming topics for the various GPL'd game engine sources.
Post Reply
Jay Dolan
Posts: 59
Joined: Tue Jan 22, 2008 7:16 pm
Location: Naples, FL
Contact:

Quake2: Deficiency in Cm_TransformedBoxTrace

Post by Jay Dolan »

I noticed the other day that while Cm_TransformedBoxTrace rotates plane normals for inline BSP models, it does not adjust plane distance for them:

Code: Select all

/*
 * @brief Collision detection for inline BSP models. Rotates the specified end
 * points into the model's space, and traces down the relevant subset of the
 * BSP tree.
 */
c_trace_t Cm_TransformedBoxTrace(const vec3_t start, const vec3_t end, const vec3_t mins,
		const vec3_t maxs, const int32_t head_node, const int32_t contents, const vec3_t origin,
		const vec3_t angles) {

	c_trace_t trace;
	vec3_t start_l, end_l;
	vec3_t forward, right, up;
	vec3_t temp;
	_Bool rotated;

	// subtract origin offset
	VectorSubtract(start, origin, start_l);
	VectorSubtract(end, origin, end_l);

	// rotate start and end into the models frame of reference
	if (head_node != cm_box.head_node && (angles[0] || angles[1] || angles[2]))
		rotated = true;
	else
		rotated = false;

	if (rotated) {
		AngleVectors(angles, forward, right, up);

		VectorCopy(start_l, temp);
		start_l[0] = DotProduct(temp, forward);
		start_l[1] = -DotProduct(temp, right);
		start_l[2] = DotProduct(temp, up);

		VectorCopy(end_l, temp);
		end_l[0] = DotProduct(temp, forward);
		end_l[1] = -DotProduct(temp, right);
		end_l[2] = DotProduct(temp, up);
	}

	// sweep the box through the model
	trace = Cm_BoxTrace(start_l, end_l, mins, maxs, head_node, contents);

	if (rotated && trace.fraction != 1.0) {
		vec3_t a;

		VectorNegate(angles, a);
		AngleVectors(a, forward, right, up);

		VectorCopy(trace.plane.normal, temp);
		trace.plane.normal[0] = DotProduct(temp, forward);
		trace.plane.normal[1] = -DotProduct(temp, right);
		trace.plane.normal[2] = DotProduct(temp, up);
	}

	trace.end[0] = start[0] + trace.fraction * (end[0] - start[0]);
	trace.end[1] = start[1] + trace.fraction * (end[1] - start[1]);
	trace.end[2] = start[2] + trace.fraction * (end[2] - start[2]);

	return trace;
}
As you can see, rotation is handled, but the plane distance is not. I'm going to try to fix this, but I'm wondering if anyone else already has, and / or what I might break in doing so :)
Jay Dolan
Posts: 59
Joined: Tue Jan 22, 2008 7:16 pm
Location: Naples, FL
Contact:

Re: Quake2: Deficiency in Cm_TransformedBoxTrace

Post by Jay Dolan »

As I've mentioned in other threads, I'm using LordHavoc's matrix library, which is heavily optimized and handles these kinds of transformations for points and planes really well. Here's the updated code which fully transforms the intersected plane for translated and rotated inline models:

Code: Select all

/*
 * @brief Collision detection for non-world models. Rotates the specified end
 * points into the model's space, and traces down the relevant subset of the
 * BSP tree. For inline BSP models, the head node is the root of the model's
 * subtree. For mesh models, a special reserved box hull and head node are
 * used.
 *
 * @param start The trace start point, in world space.
 * @param end The trace end point, in world space.
 * @param mins The trace bounding box mins.
 * @param maxs The trace bounding box maxs.
 * @param head_node The BSP head node to recurse down.
 * @param contents The contents mask to clip to.
 * @param origin The origin of the entity to be clipped against.
 * @param angles The angles of the entity to be clipped against.
 */
c_trace_t Cm_TransformedBoxTrace(const vec3_t start, const vec3_t end, const vec3_t mins,
		const vec3_t maxs, const int32_t head_node, const int32_t contents, const vec3_t origin,
		const vec3_t angles) {

	vec3_t start0, end0;
	matrix4x4_t mat, inv;

	const vec_t *o = origin, *a = angles;
	Matrix4x4_CreateFromQuakeEntity(&mat, o[0], o[1], o[2], a[0], a[1], a[2], 1.0);

	Matrix4x4_Invert_Simple(&inv, &mat);

	Matrix4x4_Transform(&inv, start, start0);
	Matrix4x4_Transform(&inv, end, end0);

	// sweep the box through the model
	c_trace_t trace = Cm_BoxTrace(start0, end0, mins, maxs, head_node, contents);

	if (trace.fraction < 1.0) {
		vec4_t plane;

		const c_bsp_plane_t *p = &trace.plane;
		const vec_t *n = p->normal;

		Matrix4x4_TransformPositivePlane(&mat, n[0], n[1], n[2], p->dist, plane);

		VectorCopy(plane, trace.plane.normal);
		trace.plane.dist = plane[3];
	}

	trace.end[0] = start[0] + trace.fraction * (end[0] - start[0]);
	trace.end[1] = start[1] + trace.fraction * (end[1] - start[1]);
	trace.end[2] = start[2] + trace.fraction * (end[2] - start[2]);

	return trace;
}
I'm going to look into caching a clipping matrix for cl_entity_t and sv_entity_t, and passing that into this function so that the matrix doesn't have to be derived and inverted for each trace.
Jay Dolan
Posts: 59
Joined: Tue Jan 22, 2008 7:16 pm
Location: Naples, FL
Contact:

Re: Quake2: Deficiency in Cm_TransformedBoxTrace

Post by Jay Dolan »

I've wrapped up my refactoring of Quake2's collision code. I've broken it into logical units, like Quake3, and I've ported over Quake3's "offsets" array that leverages planes' sign_bits to speed up testing against non-axial planes. I've also cleaned the code up and applied c99 standards. The full code lives here:

https://github.com/jdolan/quake2world/b ... /collision

The last bit I mentioned in my previous post was to cache clipping matrices for each entity, so that these matrices don't have to be resolved within Cm_TransformedBoxTrace / Cm_TransformedPointContents. This should provide a performance improvement, because these rotations that Quake2 has done for years (Q3 still does them, btw) are per trace and per entity. So if you have 10 rotated BSP entities in your scene, every single trace has to resolve 10 unique rotations before recursing down the tree. That's pretty wasteful.

So what my code does now is store clipping matrices on cl_entity_t and sv_entity_t (new to Q2W). The matrices themselves are only refreshed when the entity moves (client) or is re-linked (server). Because of this, they are guaranteed to always reflect the entity's current orientation. These are then passed into Cm_TransformedBoxTrace and Cm_TransformedPointContents, which uses them to rotate the points into place.

A perk of this change is that I was able to apply frame interpolation to the matrices on the client, so as to yield pixel-perfect collision detection for prediction. Quake2 (and Quake3?) doesn't have this. The prediction code in Q2 uses the "current" entity state which, for almost all frames, is ahead of where you're rendering.

Code: Select all

/*
 * @brief Collision detection for non-world models. Rotates the specified end
 * points into the model's space, and traces down the relevant subset of the
 * BSP tree. For inline BSP models, the head node is the root of the model's
 * subtree. For mesh models, a special reserved box hull and head node are
 * used.
 *
 * @param start The trace start point, in world space.
 * @param end The trace end point, in world space.
 * @param mins The trace bounding box mins.
 * @param maxs The trace bounding box maxs.
 * @param head_node The BSP head node to recurse down.
 * @param contents The contents mask to clip to.
 * @param matrix The matrix of the entity to be clipped to.
 * @param inverse_matrix The inverse matrix of the entity to be clipped to.
 *
 * @return The trace.
 */
cm_trace_t Cm_TransformedBoxTrace(const vec3_t start, const vec3_t end, const vec3_t mins,
                const vec3_t maxs, const int32_t head_node, const int32_t contents, const matrix4x4_t *matrix,
                const matrix4x4_t *inverse_matrix) {

        vec3_t start0, end0;

        Matrix4x4_Transform(inverse_matrix, start, start0);
        Matrix4x4_Transform(inverse_matrix, end, end0);

        // sweep the box through the model
        cm_trace_t trace = Cm_BoxTrace(start0, end0, mins, maxs, head_node, contents);

        if (trace.fraction < 1.0) {
                vec4_t plane;

                const cm_bsp_plane_t *p = &trace.plane;
                const vec_t *n = p->normal;

                Matrix4x4_TransformPositivePlane(matrix, n[0], n[1], n[2], p->dist, plane);

                VectorCopy(plane, trace.plane.normal);
                trace.plane.dist = plane[3];
        }

        trace.end[0] = start[0] + trace.fraction * (end[0] - start[0]);
        trace.end[1] = start[1] + trace.fraction * (end[1] - start[1]);
        trace.end[2] = start[2] + trace.fraction * (end[2] - start[2]);

        return trace;
}

Code: Select all

/*
 * @brief Interpolates translation and rotation for all entities within the
 * current frame. If the entity is at its most recently parsed orientation,
 * this is a no-op.
 */
void Cl_LerpEntities(void) {

        for (uint16_t i = 0; i < cl.frame.num_entities; i++) {

                const uint32_t snum = (cl.frame.entity_state + i) & ENTITY_STATE_MASK;
                cl_entity_t *ent = &cl.entities[cl.entity_states[snum].number];

                if (!VectorCompare(ent->origin, ent->current.origin)
                                || !VectorCompare(ent->angles, ent->current.angles)) {

                        // interpolate the origin and angles
                        VectorLerp(ent->prev.origin, ent->current.origin, cl.lerp, ent->origin);
                        AngleLerp(ent->prev.angles, ent->current.angles, cl.lerp, ent->angles);

                        if (ent->current.solid != SOLID_NOT) {
                                // and for solids, update the clipping matrices
                                const vec_t *angles = ent->current.solid == SOLID_BSP ? ent->angles : vec3_origin;

                                Matrix4x4_CreateFromEntity(&ent->matrix, ent->origin, angles, 1.0);
                                Matrix4x4_Invert_Simple(&ent->inverse_matrix, &ent->matrix);
                        }
                }
        }
}
Post Reply