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);
}
}
}
}