by ketmar » Thu Jul 19, 2018 9:44 pm
yeah. actually, Quake does very smart thing: so-called "beveled BSP tree". that is, to trace a box, Quake makes the world bigger, so the box can be approximated as a point, and then it can just does a raycast. but when you have sharp corner in your geometry, and makes your geometry bigger, you'll get an "invisible spike", which will block the move. this is due to the fact that collision hull is actually made of planes, not polygons, and is implicitly defined by plane intersections. so if you'll make, for example, 2d triangle bigger by moving planes away from its center, the intersections will be further from the original shape. to alleviate this, Quake's BSP builder adds some additional planes at the sharp corners, to "cut" them off. it is slightly hard to visualise without a picture, but sorry, i am not good at painting at all. ;-)
that is what i called a "trick".
having such tree allows to do collision checking (actually, raycasting) in amortised O(log n) time, and also gives you hit point and hit normal for free (this is how wall sliding is done). it can also be used to check if some AABB is inside a solid (maybe partially). this is used to check if player is in water/lava (technically they are solids, just with another matherial settings).
it looks that when Karmack did Doom engine, he didn't thought about such use of BSP trees, so Doom does collision detection by a more conventional grid-based checking (that is why we have blockmaps). this solution is much worser, and it has some flaws (you may stuck in some wall configurations and collision angles, even on seemingly prefectly nice walls).
p.s.: IRL, it is even more complex than that (afair, beveled trees appeared only in Q3, and before it, BSP trees was specially modified to fit to some common box sizes; but this is really long topic, and my post is already boring enough without such details ;-).