collision detection in quake 1

redC said:
I want to understand the role of clipnodes in this process. … Any explanation or example of the recursive hull trace algorithm would be very helpful.

I mean, you can read exactly what it does here?

They're somewhat similar to a bounding box, but closer to bounding slabs, a collection of planes that can quickly satisfy a plane test, above or below the plane. Pass all the tests and motion is legal, fail any any and it isn't allowed.

If someone happened to make exactly six of them at orthogonal angles make a bounding box, but that's not the only shape possible, you can have an arbitrary number and they are arbitrary planes, so boxes aren't the only option, and the details of the shape are entirely up to the complexity of data desired.

redC said:
what is the typical algorithm followed to compute collision fraction and surface normals for movement?

I can describe a typical algorithm, but idk if it was used that way in Quake.

We have a BSP tree for the world and a axis aligned bounding box for the player.
But casting the box shape against the world would be complicated, so we use a Minkowski Sum to simplify the problem to casting a point against a extruded version of the world:

There is world walls (black triangle) and player box (thick green outline)
We put the box on each vertex of the triangle and calculate the convex hull (red polygon).
For the collision test, we now only need to trace a ray from the box center against the null. (hit polygon gives surface normal)

Placing the box (light blue) at the hit point (cross), gives us the state of the player at the time of collision at this point, and we can model some collision response from there. For example reflecting the ray and repeating recursively until we have traveled the desired distance given by timestep times velocity magnitude.

Accepting the player box can never rotate or change it's shape,
ans also accepting enemies have the same size,
we can precompute the hulls.

But now we have two options for this hull data:
We can add them as subtrees to the leafs of the visible bsp geometry we already have.
Or we can make a new, unique bsp tree containing just the collision geometry.

In the first option the geometry was already split from the visible BSP, so we have more data than needed.
In the second option we avoid those redundant splits, but we loose the mapping from visible leaf to collision geometry guaranteed to be inside that same leaf.

I do not really see a need for the mapping, so the second option seems better to me.

Idk what Quake does in detail, but i guess it's mostly like that.

thanks for the detailed explanation,
i have a follow up question if you could,how are the planes chosen and combined to form the collision hull, and is this hull derived from visible BSP leaves ?

redC said:
how are the planes chosen and combined to form the collision hull

I would use a standard algorithm calculating the convex hull from a given point set. (That's some work, but an open source implementation is in the Newton physics engine, for example.)

redC said:
is this hull derived from visible BSP leaves ?

It should work better to use the initial ‘brushes’ made in the editor, which should be already convex polyhedrons.
But you can also use solid leaves of the visible BSP. But doing so causes more pieces, because they were already split.

In either case you have a set of convex polyhedrons, and you can generate one hull from each.
To get one hull, make the point set from 8 points from each vertex of the polyhedron as explained above.
Then generate a new bsp from all hulls.