MD3-based collision support via ZScript

[Nash]

Quake never did any collisions with MD2/MD3 models, only with meshes. and mesh is a thing that has pre-built BSP tree, which is used to do box tracing (with some trickery inside). that is, pre-built BSP tree not only makes things alot faster, it also makes things alot more reliable too. but models doesn't have it.

p.s.: i meant "exact collision" -- AABB checks are there, of course.

I never knew this was how Quake did it. Thanks for the info. It does sound like a better way actually.

[ketmar]

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

[ZZYZX]

Quake never did any collisions with MD2/MD3 models, only with meshes.

And that's how it should be done if implemented. Stuff like this may be cool but when used in actual production will quickly fall apart. It's a nice proof of concept but done in the completely wrong place with completely wrong data sets.

In Doom terms, what's the difference between models and meshes? Or you want to embed static models into the BSP? Note that I had plans (in case I occasionally get an enlightenment on how to resolve multiple plane bump conflict) to make rideable models, that is — dynamic. And ZScript has everything necessary to do this.

Especially lol'd at the wrong place — obviously everything should be done in the engine so that modder has zero control over it, I do remember your stance on dynamic slopes and almost everything else I did as-is — render overlays, per-camera preprocessing (would have helped implementing actor render layers by offsetting from the viewpoint, not from the consoleplayer...), now this as well.
While I do understand the concerns, it's not like this approach doesn't have any right to live, if it works

But either way I can't really tell if this particular approach that I implemented can work for common use, due to said multiple plane bump conflict — player just gets thrusted wildly. Not rly sure what's wrong with the logic there.

[ketmar]

having it in the engine doesn't mean that a modder is locked out of it. still, the right and reliable way to do it is a 3d mesh with pre-built beveled BSP tree -- it will solve your coldet problems too, btw. but you have to have a properly "closed" mesh for it to work, not a random polygon soup, as in md2/md3 (while most models are "ok", they doesn't have to be so). strictly speaking, models are decorations, they are not supposed to be a part of a level geometry.

at least we have to have a separate tool that will check if a given model is a valid one, and build beveled BSP tree for it. we also should implement a loader for this new mesh format, and a renderer for it too. and somehow integrate new coldet code into existing grid-based coldet. with this solution you will have a properly working geometry, with properly working pull/push mechanics, and it won't slow the game down to a crawl when people will start to throw in 9e+3 meshes per level (and believe me, they will start doing that! ;-).

i am pretty sure that this is what Graf meant when he wrote about "wrong place with wrong data sets" -- what you have now is probably ok as PoC, but not something one want to have as a long-time solution.

[ZZYZX]

Exactly why this is a script/mod: it also somewhat guarantees that people will know what they are doing if they use it, not the usual "it's in GZDoom so it should scale to nuts.wad level".
The assumed target audience for this is people like Nash/Zanieon, not people like Tormentor667 who utterly abuses every feature given
And the point wasn't to allow replacing map geometry with models universally, but rather to finally use large models without projectiles randomly passing through, which is really obvious in a low-res game.

btw: How will using a BSP help in this case? Since the issue I'm talking about is when player collides with two planes and they push the box into each other. Trivially this should be solved by calculating mean normal and pushing the player away with that, but it didn't work IIRC. Or the point here is that instead of colliding box-vs-plane it collides point-vs-offset-plane which makes it easier? I could probably do something similar as models are preprocessed, but how does it support actors with different radius/height?

Overall, using a separate tool to generate something doesn't sound really good. Already enough weird engine-specific formats almost without Blender support (looks at UE — no export plugins, broken import; and MD2/3 — almost all export plugins are outdated, and also broken import). But if someone else implements it like that, well, whatevs. At least it'd actually work.

[ketmar]

>Or the point here is that instead of colliding box-vs-plane it collides
>point-vs-offset-plane which makes it easier?
exactly. just look at how Q3 did it (if you're brave enough ;-).

>how does it support actors with different radius/height?
that is where beveled BSP comes to the rescue: due to bevels, you can scale your model by huge factors by any axis (and rotate, of course). early Q engines did a special processing of BSP trees to make 'em usable with common AABB sizes, but with proper beveling it shouldn't be a problem (and it should work with spheres too, with small, almost unnoticable quirks).

of course, you can create BSP trees on the fly, it is not hard. what is hard are proper checks for valid "closed" models -- that's why separate utility is better.

[dpJudas]

You can do mesh collision on a triangle soup by sorting the triangles into an axis-aligned bounding-box (AABB) or oriented-bounding-box (OBB) binary tree. This can be done fairly quickly at startup. No need to bring a Quake BSP into it. The shadow map code already creates such a AABB tree for lines in 2d. Change the lines to triangles and add the third dimension to the node AABBs. The bullet collision library (used by Unity, among others) uses this method for static meshes if you feed it a triangle soup.

Personally, I wouldn't attempt to write a completely new collision library in ZScript. For two reasons: performance and amount of work required. Once you support basic collision detection you'll immediately be faced with people requesting rigid body physics - rag dolls and all that. This is also time critical code - are you sure ZScript scales to deliver? If not, it is kind of useless to do it from there.

About the face normal and pushing player away - this is the classical problem with collision stuff: floating point precision. What works in perfect math breaks down horribly with floating point unless you start to do all kinds of things to avoid it. For example, Bullet requires all triangles to stay between 0.1m and 0.5m in size. Probably similar constraints on movement per tic. Bullet also applies margins to objects to avoid them actually touching, and its broken kinematic character controller has a fallback "recover from penetration" function that tries to push the character out of an object if it somehow managed to collide anyway.

[ketmar]

the whole thing about (beveled) BSP is that it allows to use much faster (and easier too) ray-vs-plane checks instead of ray-vs-poly, or aabb-vs-poly. it is possible to go with polygon soup, of course, but using pre-built BSP is just *way* easier (and faster too, as with balanced tree you will get amorthised O(log n) regardless of polycount).

p.s.: also, bullet does "penetrate and pop out" instead of CCD (at least it did way back when i looked at it) -- 'cause doing CCD on polysoup is hard (and it is easy for BSP, that's why D3 did all its physics based on CCD, for example).

[dpJudas]

Given how much trouble Doom has had with splitting lines for the BSP, saying this method is way easier to implement is.. questionable. Is it faster? The triangle test at the end certainly is slower, but on the other hand if the BSP generator creates too many split lines ("segs") it is no longer certain it wins. Which brings us back to the BSP way certainly isn't the easier one to implement.

[ketmar]

much of the troubles Doom has with BSP is due to its (Doom's) fixed point math, and due to its grid-based coldet. if only Carmack thought about using BSP to do coldet, and discovered beveled BSP trick back then... but that ship was sailed, and we cannot do anything with it now without breaking some wads.

yes, making fast BSP builder is still something that is hard, but it doesn't matter much for standalone utility. and once you have it, actually *using* BSP is way easier.

but anyway, i think that we're going too far off-topic here. ;-)

[ZZYZX]

As for having it in ZScript and speed/optimization concerns: there are 3D games entirely (except the renderer) written in non-jitted scripting languages (Python) that actually work. It really depends on proper coding and proper usage.
So yea, I believe it'd work for my purposes, if finished.

[Graf Zahl]

Your code will face one big problem eventually: You completely circumvent the engine.

And you have to read the definition files again. So you are not working with the in-game data. It is entirely dependent on the implementation not changing - and it's format limited. It also doesn't really integrate into the engine's own collision detection. Change anything in there and you'll be in for a rough ride. There's a reason why the collision detection stuff is not exposed to modders outside a very limited peek at what something collides with.

there are 3D games entirely (except the renderer) written in non-jitted scripting languages (Python) that actually work.

How much processing do they allow?

[jjjjoa]

Sorry for the bump, but the download link isn't working (stuck on a loop of "Generating new download key"), if you can please try to fix it, and question, how stable/optimized is the code?, is it properly use-able in normal projects?

[TDRR]

Will the "carry things" feature ever happen? This would be a perfect way to circumvent polyobjects not having a definite top or bottom (even if you made a midtex polyobj it wouldn't carry you) and we would finally get the subway sectors which have been requested a very long time now.

[Nash]

I wonder how much faster this is now with JIT enabled? If at all?

(can't check; download doesn't work anymore)