# Sorting Polygons by Distance to Camera

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

## Recommended Posts

Ok, basically (like the subject title says) I'm trying to sort all of the polygons in the scene from closest to farthest from the camera eye and I'm having some trouble. I've tried several things, but I'm still getting the wrong overlapping when I turn the depth buffer off and render the sorted list. At the most I've gotten them 80% in order. So, I'm out of ideas and need help from people smarter than me:)

##### Share on other sites
Well hard to know without more concreate details...but...I assume you're talking about sorting individual tris?...In which case what are you taking as the position to use for the depth calc? As you get incorrect sorting in some cases if you're using the average of the 3 vertex positions (i.e. a really big triangle which is behind a smaller triangle could actually have a average position which is in front of the smaller triangle, and so would sort incorrectly)

It's all a matter of quality :)
If it looks good enough then it is good enough :)

Paul

##### Share on other sites
It is impossible to sort polygons by their distance to the camera in general because such an order doesn't necessarily exist. Polygons A, B, and C can overlap such that A is in front of B, B is in front of C, and C is in front of A. In this case the painter's algorithm (drawing further objects before closer objects to make the closer objects cover the further ones) doesn't work. It can be necessary to split polygons to sucessfully sort them as needed.

That being said, how are you currently sorting the polygons? What point are you finding the distance to? Are you finding the distance from the camera, or the distance from the viewing plane?

##### Share on other sites
Well, I've been trying a bunch of things with each triangle's plane... but even if I get that working, it'll be incredibly slow I'm sure.. especially when more objects are in the scene. I tried the average point thing... but it wasn't very accurate. I guess I was hoping there was some easy trick to this... but the more i look into it, the more I see that it's a very complex problem when you take speed into account:|

##### Share on other sites
I guess in my algorithm, I'm assuming that the object is convex and there won't be any weird triangle combinations (like 3 triangles overlapping in a way that's impossible to draw correctly in an order) and no intersections. I basically want my models to look exactly like they would with a depth buffer... but without using one (so the triangles would be drawn whole, in a sense, like layers in photoshop).

all of my approaches so far don't work... so I'm kind of at the drawing board. A bunch of polygons in 3D space that need to overlap right from the perspective of the camera.

##### Share on other sites
As you say, with non-convex objects, or with three overlapping triangles, it's impossible to get perfect sorting by just sorting the triangles. You need to build what's basically a beam tree from the camera point of view, using plane cutting when you hit triangles (and splitting geometry).

##### Share on other sites
3d APIs use per pixel Z tests for some reason... And it's that, you can't have perfect results with just sorting triangles.
What you describe is actually called the "painter's algorithm", and from what I understand, it's not just "far from perfect", it is most unsuitable to implement for 3d graphics.

E.g. imagine 2 rectangles made of 2 faces each, (4 including the backfacing ones), placed in 3d, in a way that they form an "extruded X", with their centers coinciding. There is no way to get the correct visual result based on triangle sorting.

The idea is to *minimize* pixel overdraw -the average number of times that a pixel is drawn, while rendering a scene- in order to save time and not deal with things that won't even be visible... Not maximize it!

In fact, a "rough" optimization, is to sort and render objects the other way -thus render first those ones *closer* to camera- because they generally occlude more volume in the viewport, and you end up saving significant portion of it from having to be drawn over and over... (with per pixel Z tests, that is)

##### Share on other sites
Is there any reason you need 'perfect' sorting? (apart from general satisfaction)

Out of the games I've worked none of them had a 100% precise sorting method, it generally ended up as a depth sort per model (based on bounding box), and art fixes to the geometry as needed ( i.e. chopping up into smaller models or just making saner geometry etc). We had to option to render objects with per poly sorting, but IIRC only one small object in the whole game had that option turned on, because it's so damn slow that we avoided it like the plague (in fact we considered the use of that particular draw call quite satanic).

Sorting for alpha is just a pain all the time, if you have good artists they will understand that it's a pain and make art which avoids a lot of the problems that can occur,

Paul

##### Share on other sites
If you want to work at the world-space level (per-polygon/per-triangle) instead of in image-space(per-pixel, z-buffering) then you should start out with a BSP tree or such. It might take some massaging to get exactly what you want, but it'll get a good approximation to your target quickly.

##### Share on other sites
what I'm trying to do is a cel-shaded look using quads. If I don't sort the triangles right, there's artifacts on the lines. Maybe I should look into a better technique?

1. 1
2. 2
Rutin
20
3. 3
khawk
17
4. 4
A4L
14
5. 5

• 12
• 16
• 26
• 10
• 44
• ### Forum Statistics

• Total Topics
633759
• Total Posts
3013716
×