I have seen a few episodes now working on the sprite sorting problem, and now the more I think about it, the more I realize I have some questions about it. I believe there were a couple episodes about this problem that I missed, so maybe these ideas were explored there. If that is the case my apologies for traversing old ground again.
So the thing I am always a little confused with in 2D is why it should be semantically difficult when we know exactly how the way things eclipse one another in 3D. The only difference I can think of that seems important is that in 3D you can have one model with multiple Z values at different vertices, whereas in a 2D sort the problem is to find a rule that decides whether "this object is completely in front of this object". My first question: Are there any other reasons why we don't think 3D logic applies?
Nevertheless it still seems to me like the rules of 3D apply. For instance, take the idea from episode 303 that there are Z sprites and Y sprites and no other types of sprites. With that point of view, it seems to me that there are only two depth values of on an image which define the range of depths that image exists at in 3D. The depth of the image at the top of the sprite and the depth of the image at the bottom of the sprite. So for Y sprites the depth is lower on top and higher on bottom, and for Z sprites the depth is higher on top and lower on bottom. My second question: Are there really only these types of sprites? Also are we doing any math to turn the Y,Z coordinates into projected depths?
Further we know the area on the screen that a sprite is going to fill even if we don't know which sprites eclipse which other ones. So we can see when two sprites cover an overlapping area. If they are overlapping, it seems pretty easy to determine which must eclipse the other: If they are both Z, the one with the lower Z must go on top. If they are both Y, the one with the lower Y must go on top. If one is a Z and the other is a Y it get's a little involved but not too much:
If Z.top and Z.bottom are the top and bottom depth values of the Z sprite, and Y.top and Y.bottom are the top and bottom depth values of the Y sprite, we know that Z.bottom < Z.top and Y.top < Y.bottom. So if Z.top < Y.top then Z is first, if Y.bottom < Z.bottom, then Y is first. If neither of those cases occur we can project the Z value of the Z sprite into the plane of the Y sprite and figure out the depth of the position. That projected value cannot be between Z.bottom and Z.top if we assume there are no intersections, so it will tell us whether the Z sprite goes on top.
Finally, if all of my thinking so far has been correct so far, the last part I do not get is why this would lead to a directed graph with cycles. I understand the example with the three sprites from the Q&A on day 303 featured a situation where it looked like two Z sprites should sort one way, but then a third Y sprite was introduced to create a cycle. But my final question here is, if the two Z sprites did not overlap in pixels, why not just say "no relationship" instead of guessing? That way the graph that comes out is a partial ordering instead which is a lot easier to turn into a total ordering. Also note that if the two Z sprites DID overlap in their pixels, then there would be no space between the Z sprites for a Y sprite to create this problem, and in general I am convinced that no such issue can arise if sprites aren't allowed to intersect.
So there's the idea. To summarize my questions again: Do normal rules about 3D and depth not work for some reason other than the fact that we're trying to do a sort rather than use a depth buffer? Is there any reason why we cannot always figure out the sorting of two overlapping images? Do we have to make guesses in certain cases instead of leaving the pair of sprites unrelated?
(Also note I haven't implemented any of this, I've just been doing math and sketches.)
So the thing I am always a little confused with in 2D is why it should be semantically difficult when we know exactly how the way things eclipse one another in 3D. The only difference I can think of that seems important is that in 3D you can have one model with multiple Z values at different vertices, whereas in a 2D sort the problem is to find a rule that decides whether "this object is completely in front of this object". My first question: Are there any other reasons why we don't think 3D logic applies?
Nevertheless it still seems to me like the rules of 3D apply. For instance, take the idea from episode 303 that there are Z sprites and Y sprites and no other types of sprites. With that point of view, it seems to me that there are only two depth values of on an image which define the range of depths that image exists at in 3D. The depth of the image at the top of the sprite and the depth of the image at the bottom of the sprite. So for Y sprites the depth is lower on top and higher on bottom, and for Z sprites the depth is higher on top and lower on bottom. My second question: Are there really only these types of sprites? Also are we doing any math to turn the Y,Z coordinates into projected depths?
Further we know the area on the screen that a sprite is going to fill even if we don't know which sprites eclipse which other ones. So we can see when two sprites cover an overlapping area. If they are overlapping, it seems pretty easy to determine which must eclipse the other: If they are both Z, the one with the lower Z must go on top. If they are both Y, the one with the lower Y must go on top. If one is a Z and the other is a Y it get's a little involved but not too much:
If Z.top and Z.bottom are the top and bottom depth values of the Z sprite, and Y.top and Y.bottom are the top and bottom depth values of the Y sprite, we know that Z.bottom < Z.top and Y.top < Y.bottom. So if Z.top < Y.top then Z is first, if Y.bottom < Z.bottom, then Y is first. If neither of those cases occur we can project the Z value of the Z sprite into the plane of the Y sprite and figure out the depth of the position. That projected value cannot be between Z.bottom and Z.top if we assume there are no intersections, so it will tell us whether the Z sprite goes on top.
Finally, if all of my thinking so far has been correct so far, the last part I do not get is why this would lead to a directed graph with cycles. I understand the example with the three sprites from the Q&A on day 303 featured a situation where it looked like two Z sprites should sort one way, but then a third Y sprite was introduced to create a cycle. But my final question here is, if the two Z sprites did not overlap in pixels, why not just say "no relationship" instead of guessing? That way the graph that comes out is a partial ordering instead which is a lot easier to turn into a total ordering. Also note that if the two Z sprites DID overlap in their pixels, then there would be no space between the Z sprites for a Y sprite to create this problem, and in general I am convinced that no such issue can arise if sprites aren't allowed to intersect.
So there's the idea. To summarize my questions again: Do normal rules about 3D and depth not work for some reason other than the fact that we're trying to do a sort rather than use a depth buffer? Is there any reason why we cannot always figure out the sorting of two overlapping images? Do we have to make guesses in certain cases instead of leaving the pair of sprites unrelated?
(Also note I haven't implemented any of this, I've just been doing math and sketches.)
Edited by Allen Webster
on
Reason: Disclaimer
I haven't watched 303 yet, but here's an example of how you can get a cycle with non-intersecting sprites (from my previous thread about comparison sort). The only solutions are to have an imperfect sort (i.e. sprites sometimes clip in front of sprites of the opposite type when they logically shouldn't), or to do more work (like splitting up the sprites, or using a depth buffer).
Sizik
As an aside, I've done more thinking, and found that even though we only have flat or standing sprites, we can still can run into painter's algorithm issues. Here's an example, which is basically the above two examples combined. This creates a situation where there is no order in which you could draw the sprites, without having to split the sprites up into parts.
Well one of my questions is "why do we have to guess?". I mean what do you gain from making the guess on the A?C comparison? If the plan is that your sort will just be producing a directed graph anyway, why not just *not* assign a value?
As for the second point, that is totally true. I failed to visualize that case, good point!
At this point I can't help but ask, why are we not using a depth buffer? I'm sure Casey has addressed this, but it seems to me like that would be a good idea now.
As for the second point, that is totally true. I failed to visualize that case, good point!
At this point I can't help but ask, why are we not using a depth buffer? I'm sure Casey has addressed this, but it seems to me like that would be a good idea now.
Edited by Allen Webster
on
Reason: english
Allen, first of all I think a depth buffer will be an exaggerated overkill solution.
But to the point, you got the answer in your questions.
So far we've been trying to sort the sprites in world space (correct me if I'm wrong), and my suggestion is to sort them in view space, meaning their screen projection.
Because after projection they all become essentially z sprites that can be sorted by their min/max Y.
To answer Matt's point, there is no solution with just sorting.
You create a zbuffer to sort by occlusion (and that takes care of everything else), or you split intersecting sprites and continue sorting.
But to the point, you got the answer in your questions.
So far we've been trying to sort the sprites in world space (correct me if I'm wrong), and my suggestion is to sort them in view space, meaning their screen projection.
Because after projection they all become essentially z sprites that can be sorted by their min/max Y.
To answer Matt's point, there is no solution with just sorting.
You create a zbuffer to sort by occlusion (and that takes care of everything else), or you split intersecting sprites and continue sorting.
Allen, you might want to look at
http://andrewrussell.net/2016/06/...in-river-city-ransom-underground/
for a more complete explanation!
But the short answer is, it's because we don't actually know what's supposed to happen in 3D, and a Z-buffer doesn't really help us. We are essentially flattening real 3D objects into flat 2D planes, but those are just approximations and to the viewer it is clearly not perceived as a flat plane, etc. So when it comes to figuring out what should be in front of or behind something, we cannot appeal to any "real" 3D structure of the scene, since we don't actually have one!
- Casey
http://andrewrussell.net/2016/06/...in-river-city-ransom-underground/
for a more complete explanation!
But the short answer is, it's because we don't actually know what's supposed to happen in 3D, and a Z-buffer doesn't really help us. We are essentially flattening real 3D objects into flat 2D planes, but those are just approximations and to the viewer it is clearly not perceived as a flat plane, etc. So when it comes to figuring out what should be in front of or behind something, we cannot appeal to any "real" 3D structure of the scene, since we don't actually have one!
- Casey
cmuratori
Allen, you might want to look at
http://andrewrussell.net/2016/06/...in-river-city-ransom-underground/
for a more complete explanation!
But the short answer is, it's because we don't actually know what's supposed to happen in 3D, and a Z-buffer doesn't really help us. We are essentially flattening real 3D objects into flat 2D planes, but those are just approximations and to the viewer it is clearly not perceived as a flat plane, etc. So when it comes to figuring out what should be in front of or behind something, we cannot appeal to any "real" 3D structure of the scene, since we don't actually have one!
- Casey
I'm having a ton of trouble understanding his blog post. He's talking about voxels and heightmaps and what? Could anyone please perhaps translate?
Edited by Randy Gaul
on
Thanks Casey!
The example with the hand and the truck made it click in my head. I always internally resist the fact that the "grammar" of 2D game visuals is totally not physically correct.
The example with the hand and the truck made it click in my head. I always internally resist the fact that the "grammar" of 2D game visuals is totally not physically correct.
Yeah, it's a confusing subject area for me as well, since I am always used to thinking in 3D and I haven't ever considered this kind of thing before. It's not the sort of thing you want to do on-stream while talking :)
- Casey
- Casey