1

I'm writing a graphing app and have been advised to use either a z-buffer or the painters algorithm to handle the visibility problem.

I am writing this in an HTML5 canvas so using a z-buffer seems outrageously expensive. For example, if it were a 500x500 canvas and had to loop over just 10 polygons that would be 2,500,000 iterations per frame done in the CPU. I don't know if that's a big number but it seems like the wrong way to do it for this app.

The painters algorithm seems more appropriate. The basic steps are:

1. Sort polygons based on their "z".
2. Paint all polygons, but paint the ones farthest away first.

But I'm confused about how to find their z. Say we were looking top down at the following polygons: enter image description here

If I were to just find the maximum z (farthest away from screen) red would be considered farther away. So it would paint red first and then overpaint red with orange even though red is in front of orange.

What is the correct way to sort these polygons? Or more generally, when implementing the painters algorithm how do you determine the order of your polygons?

edit: this is why im afraid of rolling my own z-buffer (goes through each pixel and randomly assigns it a color ~10FPS on this five year old i7).

user1873073
  • 3,580
  • 5
  • 46
  • 81
  • 2
    The complexity is the same. Either you sort 10 (clipped) triangles and draw them blindly using 2.5M 2D pixel operations, or use z-buffer adding only one z-operation per pixel. The benefits come only if your CG algorithm has determined that some triangles are completely occluded by others. – Aki Suihkonen Jul 21 '17 at 18:56

2 Answers2

1

Three triangles can cyclically cover each other, meaning that no generic sorting algorithm exists. Instead the problem is typically solved by cutting overlapping triangles along the overlapped edge forming new triangles/polygons, that locate completely in either side of each other.

The two polygons in question can be OTOH sorted by signed distance of vertex from the plane equation of the other polygon.

Aki Suihkonen
  • 19,144
  • 1
  • 36
  • 57
  • Are all polygons put into a big list and then ran through the sorting algorithm or should you try to group polygons based on whether they overlap in x & y first? – user1873073 Jul 21 '17 at 18:42
  • 1
    Grouping by bounding boxes (aligned to xyz or nonaligned) or spheres are typically used to speed up the sorting. – Aki Suihkonen Jul 21 '17 at 18:49
1

Z-sorting is usually slower then Z-buffering. The more polygons you have the better is to use Z-buffer. Your assumption about iterations is wrong. Z-buffering does not iterate on per polygon basis but on per pixel basis instead.

So does not matter how many polygons you got. The important thing is the area rendered in pixels (overlapped areas accounted multiple times once per each polygon it belongs to). so you can not expect that for 500x500 screen and 10 polygons will got 10*500*500 iterations.

I do not code with HTML5 canvas but unless you got direct pixel access and shadow back buffers and rasterize your polygons on your own (or have acess to it like fragment shader in GLSL) you will get hard time to implement z-buffering even if it is just single simple if condition. I think it could be done with stencil or alpha masking too but never done that.

z-sorting is usually used in these cases:

  1. You do not have enough memory to store Z-buffer

    that also infers your polygon complexity and count is low...

  2. You have polygons already sorted (due to process that created them)

  3. You need correct transparency

But as the other answer covers it if your polygons are intersecting their distance to camera you need to cut them to more. Such operation is usually so expensive that any benefit of z-sorting is negated by the time consumed. That is why even for #3 is z-buffering used and the sorting is faked by face culling like this:

Or form of ray-tracing is used:

In some cases both Z-sorting (to sort mesh rendering order) and Z-buffering (per polygon order) are used in combination. Here an example:

Community
  • 1
  • 1
Spektre
  • 49,595
  • 11
  • 110
  • 380