1

Given a set of triangles which form a closed, non-overlapping 3D-object, when the object is convex, the order at which the triangles are drawn doesn't matter, provided that only triangles which face the 'camera' are drawn.

When the object is partially concave however, at certain angles two or more triangles that face the camera will overlap. In this case, the order in which the triangles are drawn does matter.

For all of the few simple concave objects that I looked at, there is at least one order in which the object is correctly drawn at (almost) all angles.

Take a doughnut for example: The triangles that face the whole of the doughnut will have lower indices in a array of triangles and be drawn first. The triangles that face away from the center of the doughnut will have higher indices and be drawn last. Within the inner triangles there is also an order.

This image shows the order at which the triangles should be drawn. White is drawn first, black is drawn last. enter image description here

Lower order triangles can still be covered by higher order ones at extreme angles (the darker segments will be drawn over the lighter ones), but only by a small margin as shown here: enter image description here

This heart shape is another example. The white rectangles are too large and could be drawn in the wrong order. Dissecting them would solve this problem. enter image description here

Are there any known studies done on this subject?

Is there an algorithm that sorts triangles of a 3D-object so that most cases of overlapping triangles are drawn in the right order at any angle (without resorting the triangles)?

uzumaki
  • 1,743
  • 17
  • 32
  • 2
    This problem is usually solved by **Zed(Depth) buffer** in `O(1)` time and `O(xs*ys)` space complexity where `xs,ys` is view resolution. See [Mathematically compute a simple graphics pipeline](https://stackoverflow.com/a/21100338/2521214) – Spektre Aug 28 '17 at 07:17
  • I second Spektre's comment. Some additions: In general, it is very hard to find a view-independent triangle order. There will almost always be configurations that will break. And even if you have the camera location, sorting triangles is not always possible because the overlap graph can form cycles. That's why the decision is performed per pixel, where cycles are not possible. – Nico Schertler Aug 28 '17 at 18:26
  • I have never come across such research. I cut my 3D teeth in the late 1980s. Your torus would be way over the poly budget. For complex scenes (non real time) you would procedurally generate such objects from back to front In those days memory was low and slow, the usage and access time of a (best order) stored mesh would give no benefit. Z-fighting was ignored on the most part. When memory became cheap, the need for sort almost vanished from 3D (and CG). Though you may find something in other CS disciplines (not CG) where sorts are still the only solution – Blindman67 Aug 28 '17 at 18:57
  • @Blindman67 yes the topic is correct transparency rendering .... but only up to a point as more complex scenes are done by ray-tracing. – Spektre Aug 29 '17 at 07:26
  • @Spektre modern GPUs make it possible to implement a variety of Order independent transparency removing that last need for sorts in rendering. I agree that ray-tracing is the direction we are heading. That massively parallel general purpose CPU devices will see the end of the dedicated GPU (and associated extra cost) over the next 10-15 years – Blindman67 Aug 29 '17 at 08:26
  • @Blindman67 order independent transparency without ray tracing or volume based methods is very limited. For example this is how I usually do it: [OpenGL - How to create Order Independent transparency?](https://stackoverflow.com/a/37783085/2521214) – Spektre Aug 29 '17 at 08:37

1 Answers1

0

What you describe is known as the painter's algorithm. https://en.wikipedia.org/wiki/Painter%27s_algorithm

The painting order is view-dependent, but cases such that you have to split faces are exceptional.