Jump to content
  • Advertisement
Sign in to follow this  
JanR

Painters Algorithm 2D sorting

This topic is 5462 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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]

Share this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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!

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!