Author Topic: Rendering issues - some help?  (Read 3679 times)

0 Members and 1 Guest are viewing this topic.

Online geoo

  • Administrator
  • Posts: 1450
    • View Profile
Re: Rendering issues - some help?
« Reply #15 on: October 02, 2022, 09:13:56 AM »
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.

Offline namida

  • Administrator
  • Posts: 12239
    • View Profile
    • NeoLemmix Website
Re: Rendering issues - some help?
« Reply #16 on: October 30, 2022, 09:23:00 PM »
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.
« Last Edit: October 30, 2022, 09:29:27 PM by namida »
My Lemmings projects
2D Lemmings: NeoLemmix (engine) | Lemmings Plus Series (level packs) | Doomsday Lemmings (level pack)
3D Lemmings: Loap (engine) | L3DEdit (level / graphics editor) | L3DUtils (replay / etc utility) | Lemmings Plus 3D (level pack)