Alternative solutions for rendering moving geometry

Hi, this post is pretty technical, I hope this is the correct subforum for this topic. Please feel free to move it somewhere else if this is not the case.

Imagine, you would have to create a new sector based software rendered engine (like the Doom, Build, Jedi engines) for a completely new game where backwards compatibility to existing levels and tools would not be an issue. Imagine, one of the requirements would be that some doors/platforms/etc. could move, like polyobjects in Hexen or everything in Build. What algorithms would you choose for hidden-surface determination?

The two existing solutions in similar engines are as I previously mentioned polyobjects (BSP with moving lines inside convex subsector like in Hexen) and portals with sorting done at runtime (Build). The disadvantage of polyobjects is that the system is relatively limited in how the moving lines are all confined to a single convex subsector. Build‘s portals with runtime sorting don‘t have that limitation but instead you have the extreme overhead of having to do VSD at runtime which slows down everything else and limits the complexity of levels you can do overall, just for a few moving lines.

I don‘t think Quake‘s system of rendering the world using a BSP and writing to a z-buffer first then rendering moving objects using the z-buffer wouldn‘t work with the way the world is drawn in Doom/Build as the floors and ceilings are drawn using a floodfill-like algorithm that requires everything to be drawn in the right order, so filling in the moving walls/sectors later wouldn‘t work. Maybe this could be done if one would project the floors and ceilings on screen and draw them as polygons instead?

Do you have any other ideas or thoughts on this?

5 minutes ago, Sylvester said:

The disadvantage of polyobjects is that the system is relatively limited in how the moving lines are all confined to a single convex subsector.

This limit was removed by using the "miniBSP" approach pioneered by ZDoom where each subsector (the leaves of the main BSP tree) can have their own internal BSP tree that is recomputed on the fly when polyobjects move through this subsector. Since this is a small area instead of the entire level, and there usually aren't that many polyobjects active at once, this computation can be done quite fast so the impact on performance is insignificant.

For a brand-new engine, I'd suggest pushing this static+dynamic mix to the next level, and have it apply to pretty much everything. Parts of the level that are static should be explicitly marked as static; parts of the level that are dynamic (that can move or deform) are explicitly marked as dynamic.

Personally I would use a Z buffer, and support 3D models for doors (etc) which need to move in the XY plane.

Nothing about the way DOOM renders floors and ceilings precludes the use of a Z buffer.  The walls and floors can simply write the Z buffer (i.e. without a read and check) which is fairly fast, and something the Quake renderer does too.

Main thing lost with a Z buffer is the way that some sprites in DOOM (etc) are several pixels "sunk" into the floor, which helps the impression of 3D-ness, but cannot be emulated when using a Z buffer for everything, so these sprites get raised up a bit and can look like they are floating.

1 hour ago, Gez said:

This limit was removed by using the "miniBSP" approach pioneered by ZDoom where each subsector (the leaves of the main BSP tree) can have their own internal BSP tree that is recomputed on the fly when polyobjects move through this subsector.

With „confined to a subsector“ I meant that each polyobject is limited in that it is only able to move within a single subsector and if I understand the miniBSP approach correctly this is still the case here. Compare this to Build where a group of sectors could freely move inside a concave sector, e.g. vehicles in Shadow Warrior like the tank.

43 minutes ago, andrewj said:

Main thing lost with a Z buffer is the way that some sprites in DOOM (etc) are several pixels "sunk" into the floor, which helps the impression of 3D-ness, but cannot be emulated when using a Z buffer for everything, so these sprites get raised up a bit and can look like they are floating.

This would be a pretty big loss for me personally as I really prefer the way sprites are sunk into the floor in those engines. Otherwise I think the 3D model approach would probably be a good solution for rendering moving geometry but you would have to write completely separate collision detection code. 
 

Apart from that I would be really interested if there was a clean way to render the moving geometry the same way as all the other sectors without the disadvantages of the other methods.

3 minutes ago, Sylvester said:

With „confined to a subsector“ I meant that each polyobject is limited in that it is only able to move within a single subsector and if I understand the miniBSP approach correctly this is still the case here.

No! They can move out of the subsector, and into another subsector that will therefore have its own MiniBSP to accommodate the traveling polyobject. It can go across the entire map this way, visit every single subsector.

1 hour ago, Gez said:

No! They can move out of the subsector, and into another subsector that will therefore have its own MiniBSP to accommodate the traveling polyobject. It can go across the entire map this way, visit every single subsector.

I see, my bad. So the engine clips each polyobject to every subsector it crosses and builds a separate BSP for every subsector for sorting all the polyobject lines it contains?

4 hours ago, Gez said:

This limit was removed by using the "miniBSP" approach pioneered by ZDoom where each subsector (the leaves of the main BSP tree) can have their own internal BSP tree that is recomputed on the fly when polyobjects move through this subsector. Since this is a small area instead of the entire level, and there usually aren't that many polyobjects active at once, this computation can be done quite fast so the impact on performance is insignificant.

Minor tangent, but polyobjects not being limited to their original subsector was originaly pioneered by Eternity's dynasegs system in 2008 prior to ZDoom's miniBSP implementation in 2010. miniBSP is more advanced and EE's implementation was later updated to mostly match it, but it wasn't the pioneer. :P

10 hours ago, andrewj said:

Main thing lost with a Z buffer is the way that some sprites in DOOM (etc) are several pixels "sunk" into the floor, which helps the impression of 3D-ness, but cannot be emulated when using a Z buffer for everything, so these sprites get raised up a bit and can look like they are floating.

There's nothing stopping somebody, whether they are working with a hardware renderer or a software, from creating an additional buffer that marks whether or not a pixel belongs to the floor, and excluding those from Z buffer checks when drawing sprites.

On 5/19/2023 at 9:35 AM, Wagi said:

There's nothing stopping somebody, whether they are working with a hardware renderer or a software, from creating an additional buffer that marks whether or not a pixel belongs to the floor, and excluding those from Z buffer checks when drawing sprites.

How does that handle sprites that should be behind a certain floor?  You would need something like DOOM's sillouette system (clipping sprites to drawsegs), which kinda sucks, and probably doesn't work well with true (not skewed) mlook.

7 hours ago, andrewj said:

How does that handle sprites that should be behind a certain floor?  You would need something like DOOM's sillouette system (clipping sprites to drawsegs), which kinda sucks, and probably doesn't work well with true (not skewed) mlook.

if you already have a buffer where you mark whether a pixel belongs to a floor you could also store an ID of that floor in it and based on that decide whether or not that floor should clip a sprite.

For a modern sector engine - if you remove the need to support fully 3D overlapping sectors, then you can use portals for culling and depth buffer for floor/ceiling/wall rendering. TFE actually supports both depth buffering[1] (sector geometry writes to the depth buffer only, sprites and 3D objects read and write) and proper sprite/flat sorting. This is done by generating flats by extruding walls vertically + adding a cap to fill holes and projecting the positions onto the planes in order to generate texture coordinates, determine z value for shading, etc.. Because TFE uses GPU clip planes[2], then by projecting the view to infinity, clamping to the cap planes, quads converge to "infinity" allowing for accurate caps with no triangulation. Once the player leaves the sector, quads that would extend outside are clipped by the GPU clipping planes.

Anyway, the largest complexity comes from the need to support overlapping sectors in 3D - which means that full portal clipping is required[3]. For TFE this is done in two phases, 2D on the CPU (top-down[4]) and 3D on the GPU (replaces the column heights). But without that, a simple depth buffer would suffice on its own, though you lose some occlusion culling power and will get some overdraw.

So for pure software rendering, you will have to weigh the benefits of increased overdraw over the simplicity of the algorithm. For GPU rendering, it would be a clear and obvious win - especially since you can easily draw front to back and make use of hardware hierarchical z-culling.

[1] Jedi actually uses a 1D, column-based, z-buffer for object clipping. So TFE just extends that concept to 2D to support proper perspective when looking vertically.

[2] A large buffer of planes get filled in during render setup, where each draw-item has an offset and count to reference the plane table to avoid splitting up batches.

[3] Jedi doesn't clip against the portal plane correctly - and the game makes use of its quirks. But other planes are clipped correctly.

[4] CPU "wall segment" clipping is required for proper sprite and portal clipping later on to match vanilla behavior. This does allow for fully occluded sprites, 3D objects, and portals to be discarded (occlusion culling).