Rendering issues - some help?

[geoo]

I've been thinking this over for a while and the only obvious downside I can see is that it will mark a lot of pairs of faces as having one that must come first, even when it actually doesn't matter. However, this would only result in a performance penalty, rather than a failure - it might be acceptable, would have to test (and possibly optimize) before I could say for sure.

Actually, if you mark dependencies where there are none, you add additional edges to your graph, and making it more likely to get cycles.

I think the many cyclic dependencies you see are exactly a result of this. There may be instances where you legitimately get cyclic dependencies, but these should be rare in practice (e.g. the lemming intersecting with the diagonal block).

I don't really have time to think through your outlined algorithm in detail, but you should have as few extraneous dependencies as possible.
Newell's algorithm (linked in my previous post, and the linked stack overflow post also has a link to the Wikipedia article) claims to take care of this, maybe worth having a look at.

[namida]

So I managed to think of a case where my idea (which I had partially, but nowhere near fully, implemented) would fail. See attached sketch. The black lines are intended to represent billboard sprites (perhaps lemmings), although pretty much the same thing would arise even from them merely being the front face of a block.

There is an objectively correct answer to the rendering order here. First, note that the two non-diagonal faces of the deflector block would not be rendered anyway due to facing away from the camera. With this in mind, the correct ordering for the remaining pieces is that the deflector block's diagonal face must be drawn before the billboard on the right; while it doesn't matter which order those two are drawn in relative to the billboard on the left. However, my idea would create a cyclic result here.

Newell's algorithm specifically relies on splitting polygons. This in turn would produce the appearance of lemmings disappearing into corner blocks that they're very close to (much like Z-buffering also does). Discarding the polygon splitting aspect and simply doing the overlap detection, my hunch is that this would not eliminate cases where cyclic results emerge in cases that do have a correct draw order. If this result were going to be accepted, it would be less effort (and better performance-wise) to at least have another go at resolving the Z-buffering issues - perhaps by trying the "render only a subset of Z depths at a time" approach.

Maybe it's worth giving that a go anyway. It shouldn't be particularly time-consuming to implement.

[namida]

Okay, so I tried a hybrid approach here - keeping the existing code for rendering the blocks (and cracks on them etc), but using Z buffer for sprites. Although it does have the "sprite partially disappears into deflector / slope" issue, this is not too severe and I think it's better than the downright odd stuff that was happening with the existing code.

The code for blocks seems to mostly get things right - it's when sprites (which can be taller than blocks) get thrown into the mix that things get weird, generally. However if there are still issues, I can look at going into a full BSP tree approach for the blocks.

There's also one special case, to avoid Z-fighting - when hatch flaps are completely closed, they get treated as block faces rather than sprites. Similar special cases need to be added for a few other things too; namely teleporters, spring landing pads, and trampolines; but this is trickier to do as they'd need to be seperated out from other objects during the rendering.

[namida]

I've gotten the new rendering code to a state where I'm comfortable merging it into master. It's not perfect yet - there's some cases (in particular, with the smaller segment of 22.5 degree slopes) where there's still issues, but those are issues that already existed prior to these changes. A whole lot of issues on the other hand were improved. Compare the attached screenshots (default camera on Fun 1 of L3D).

Regarding performance, on LP3D Mayhem 19 "Power Distribution", with FPS limiter turned off, I get around 210 FPS on the preview screen and 190 FPS in-game with the new code. On the old code, I get 205 FPS on the preview screen (so the new code actually performs better, somehow) and 195 FPS in-game (so the new code is about 2% slower).