Quake Player Movement And Entity Collision

[Buzz]

Hey again,

How does Quake handle collision for player movement against the BSP and entities?. I have looked at the code in world.c and sv_move.c but i don't exacly understand it, does it just trace the player bounds against the BSP bounds and then sets fraction to 1.0?, could someone explain please?.

- Thanks

[R00k]

Look in world.c at SV_ClipMoveToEntity, Spike might be able to explain it in better detail, but thats the core of entity collisions against the bsp.

[talisa]

every entity in the world of quake has a big invisible square bounding-box around it

if you use darkplaces, just type 'r_showbboxes 1' in console and those bouncing boxes will become visible as colored semi-trans blocks around the entities

[Spike]

dotproducts. lots and lots of them. they're like a 1d matrix!

startdistfromplane = dotproduct(startpos, plane.normal) - plane.dist
enddistfromplane = dotproduct(startpos, plane.normal) - plane.dist
assert(startdistfromplane >= 0)
assert(enddistfromplane < 0)
frac = startdistfromplane / (startdistfromplane - enddistfromplane)

basically transforms the start+end points into the 1d-space of the plane, then figures out the fraction based on how much of the distance is on each side of the plane.
this is done for each node of the bsp etc to figure out the start position and which planes the traces crosses. BSPs are well documented elsewhere as a classic divide-and-conquer algorithm, and most examples don't need much maths beyond dotproducts to understand the basics.

axially aligned bboxes provide an easy early-out method to completely skip entities, as an optimisation, but any actual collision that returns a value < 1 will use the dist/frac calculations I gave.

the trace_plane_normal is the normal of the surface that was hit. by using that in combination with the velocity and stuff, you can calculate the velocity relative to the surface, and then remove it from the original velocity by subtracting that multiplied by the normal. Multiply that subtraction by 2 and it'll bounce off the surface with as much 'energy' as it had when it hit it.

I've probably gone and made it sound super easy now... but its the floating point imprecisions that will lead to early hair loss. special extra adds and subtracts to bias things a little towards one side, etc. very nasty stuff. really not very precise at all. this is why many engines have weird clipping and impassable convex corner issues... q2bsp is much more sane where the bsp tree is used instead only to find convex brushes which can be collided against much more cleanly without random precision issues weirding things up.
Anyway, practise makes perfect.

ah, maths... pissing off maths students for years.

[MadGypsy]

I've probably gone and made it sound super easy now.

Yeah, it's all 2+2 now.

[talisa]

I've probably gone and made it sound super easy now...

eyup... absolutely! its all like chinese to me now: sounds fancy and awesome but i dont get a fuck of it

[R00k]

i store this in my subconscious when i dream of banging my head against a bsp wall.