Other Lemmings Projects > Loap

Rendering issues - some help?

(1/4) > >>

namida:
I'm wondering if anyone more experienced with 3D graphics (or perhaps just geometry / maths in general is enough) can help with ideas on how to improve the rendering.

The main problem here is around determining the order to draw block faces and other 3D-space elements in. Due to how L3D levels can have multiple block faces in the same position, a Z buffer is not an option - this leads to an awful level of Z-fighting, and can also lead to lemmings' graphics disappearing inside blocks when they're close to a block face (especially deflectors). Instead, we need to determine what order to draw the block faces in. (Optionally, we can also work out which ones don't need to be drawn at all, due to being outside the viewing area. However, not doing this only results in a performance penalty, not glitches, so this is not critical.)

The current build, orders these elements purely by the distance from the camera to a "key point". The key point is usually, but not always, the middle of the element's position in 3D space. In the case of a tie, it's broken by a defined priority order based on the element type (so for example, if a block face and a lemming have exactly the same key point - or different points that are the same distance from the camera - the block face will be drawn first, then the lemming).

Source code in a side branch (wip/rendering-fix-20220828) implements a different algorithm, which looks at every vertex of each element, and finds the one that when transformed into screen coordinates is furthest from the camera (including the depth) then uses this as the "key point". The other difference is that instead of determining position based on the entire key point at once, it determines it based only on the depth at first, using the other two axes as a tiebreaker only (if it's still a tie after this, it uses the same priority order as the existing algorithm to break the tie). This algorithm seems to have slightly fewer glitches, but those it does have tend to be more noticable.

I'm wondering if anyone has any better ideas here? I've taken several shots at it throughout Loap's development, and these two algorithms (the former of which has been the one used in virtually all released builds; the latter is a recent development and hasn't been included in any build yet) are the only ones that even come close to getting it right - most other things I've tried have felt like they should work, but  produce awful results when I actually implement and try them out. To be clear - what I really need is thoughts on the algorithm itself; once I have the right idea, I shouldn't have any difficulty coding it.

Also, just to avoid miscommunications - note that in Loap, the X axis is left to right, the Y axis is front to back, and the Z axis is bottom to top. (ie: the coordinates (1, 2, 3) would be 1 space to the right, 2 spaces "into" the screen, and 3 spaces upwards from the origin).

EDIT: Also, with regards to freedom of movement of the camera - the camera in Loap can move in any 3D direction, has a full 360 degree freedom of movement for the yaw, a -45 degrees to +45 degrees range of movement for the pitch, and no ability at all to roll.

Simon:
This problem sounds like it must have a standard solution; the problem seems ubiquitous in 3D rendering. But I have no experience with 3D rendering. Therefore, I'll treat it as a puzzle. Let's see if I solve it sometime under the shower.

I make the following assumptions:

* Elements are always triangles or rectangles. In particular, every element is a subset of some 2D plane.

* Lemmings are not special either, they're rectangles with lots of transparency in the texture.

* Inner points of different elements never intersect. Boundaries of elements can intersect anything, even inner points, of different elements. E.g., a lemming can stand on anywhere on a floor rectangle. Wrong, see namida's attachment in next post.

* Given 2 elements, the desired output is always to paint one of them first entirely, then the other entirely. We never have to paint part of an element, then part of the other, then some more of the first. (Maybe it's even possible to prove this assumption, using that everything is a triangle/rectangle. For now, I'll just use it as an axiom.)

* The camera is a point in 3D space (that tells us where the camera is), plus a unit direction in 3D space that describes where it looks.
Indeed, the problem then reduces to defining a linear order (a.k.a. total order) on the set of elements so that the drawing "looks" good, and I can't yet point the finger on how to express that.

I conjecture that you don't need the midpoint or far point of the element. The midpoint gives me an idea though: Maybe something good comes from considering the angle relative to the camera, or, equivalently, do something with normal vectors (perpendicular to the element, and resting on the element; these always exist because the elements are 2D).

-- Simon

namida:

--- Quote ---Given 2 elements, the desired output is always to paint one of them first entirely, then the other entirely. We never have to paint part of an element, then part of the other, then some more of the first. (Maybe it's even possible to prove this assumption, using that everything is a triangle/rectangle. For now, I'll just use it as an axiom.)
--- End quote ---

Not always possible. Consider in particular a deflector block and a lemming, as attached. I have a gut feeling that the solution for elements such as lemmings (ie: those that are displayed as "billboards") is to only consider their center point on the X/Y axes (but still account for the entirity of their height) rather than the boundaries of their graphics, or at least something related to this idea.

Simon:
Very good corner case, thanks.

It's a counterexample to how rectangles can intersect in arbitrary ways. But is it a counterexample to how one of the two gets painted first entirely, then the second? If we paint all elements in the deflector block first, and then the lemming on top, is that desired? Or do you want to hide the hand (that the lemming sticks inside the deflector)?

-- Simon

namida:

--- Quote ---But is it a counterexample to how one of the two gets painted first entirely, then the second? If we paint all elements in the deflector block first, and then the lemming on top, is that desired? Or do you want to hide the hand (that the lemming sticks inside the deflector)?
--- End quote ---

No - we would always want one or the other drawn in its entirity first. In general, I'm quite happy to accept corner case glithches occuring in situations that otherwise can only be resolved by partial drawing of one / both elements; this should be fairly rare anyway.

Note that in Loap:
- Seperate faces of a block can be drawn at different times; each face is its own element when it comes to rendering.
- A block is 1 unit wide x 1 unit deep x 0.25 units high (where a unit is the size of what would visually appear as a single block, or in other words, the size of a "block" by L3D's definition). Sprites on the other hand can be arbitrarily-sized, but in practice none are larger than 1 unit wide x 1 unit high (some are smaller).

Also worth noting - a lemming will almost always be at a half-block position on either the X or Y axis. The only time where a lemming can be at a position that is not the middle of the block in at least one (non-vertical) axis, is during the movement caused by a spring or rope slide. Or to put this a different way - at all times except when springing / rope sliding, it is guaranteed that at least one (and possibly both) of the lemming's X or Y coordinate, will be (n + 0.5), where n is any integer.

Navigation

[0] Message Index

[#] Next page