I'm developing a software 3D-engine that's only able to render lines and rectangle with volume. By that I mean lines become 'walls' and rectangles form solid boxes. Drawing everything on te screen isn't that difficult, my biggest problem is sorting the objects. Rendering can only be done back-to-front since I don't have any z-buffer or something like that. Code for computing one object is in the 'view' of another is already there, I just don't know how to sort it correctly. Quicksort isn't possible, since every object has to be tested to every other (there isn't a simple distance number or something like that). Also tried insertion, that's not an option too. Maybe a combination of diffirent sorts? I really don't know it anymore, stuck on this for a long, long time... [crying]

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!