Painters Algorithm 2D sorting

Why's insertion not an option?

When I've implemented Z-sorting I've usually ended up doing it as a linked list of objects (build through an insertion sort). Then I exploit temporal coherence - the list doesn't usually change much from one frame to the next, so I can just move individual objects backwards and forwards as necessary.

You could build your list using a binary tree. Insert items into the tree on a depth comparison basis (shallower goes left, deeper goes right). When you're done you can just read the tree out recursively.

I'm sorry, wasn't too clear, I guess...

I have already tried inserting objects into a sorted list, but that simply doesn't work. For example: There's a 'wall' that starts in the left front of the screen and moves far away (in depth) to the middle of the screen. Now there's another line, just in front of it, and a line just behind it. It's, as far as I see, impossible to tell which line should be drawn first. The minimum and maximum z-values of both smaller lines can be equal, but one is in front and the other one is behind the large 'wall'.

So I believe that the only possible way to tell which one is in front is to check if one line lies in the view of the other, if that's the case then sort the deeper line to back.

This, I tried... And it worked... At least, almost... Lets say that there's only 1 line in the list. Then insert another one, which doesn't overlap the other one, so where should it go? In front, or behind? It's now possible that there's a 3rd line inserted, which lies between both. This line is the connection between the two: 1 is behind 3, 3 is behind 2. But if 1 and 2 are inserted in the wrong way, since it didn't matter at the time, insertion isn't possible (or goes wrong in my case).

So mainly you only know (or compute or whatsoever):
1 < 3
3 < 2
and then sort this...

Is there a simple solution to this? Or should I mark everything, put things in batches, locally sort en check and recheck all the time? And then merge and find out it's still not sorted right?

But thanks anyway, that's indeed the most obvious way to do it

[Edited by - JanR on October 6, 2004 8:15:01 AM]

Investigate the Newell-Newell-Sancha depth sort algorithm. It is a refinement of the simple painters algo that uses 5 steps to sort primitives based on depth. Good stuff.

joe
image space

Just a reminder, the painter's algorithm is not complete, so you can hit situations where there doesn't exist a correct sorting order (depending on your data set, that may never occur though). I'm guessing you already knew this, but since you mentioned problems finding the correct order I thought I'd mention it just in case.

Quote:

Original post by Scoob Droolins Investigate the Newell-Newell-Sancha depth sort algorithm. It is a refinement of the simple painters algo that uses 5 steps to sort primitives based on depth. Good stuff. joe image space

Thanks, that's just what I needed!

Quote:

Just a reminder, the painter's algorithm is not complete, so you can hit situations where there doesn't exist a correct sorting order (depending on your data set, that may never occur though).

Since I actually perform the test in a top-down 2D map (visualized in 3D) there can't be a situation when there's a cyclic overlap. So yes, that never occurs and it's always possible to sort.

Should've asked you guys much earlier, thanks again!