在实现画家算法时，对多边形进行排序的正确方法是什么? [英] What's the right way to order polygons when implementing the painter's algorithm?
问题描述
我正在编写一个图形
如果我只是找到最大的 z(离屏幕最远)，红色会被认为更远.所以它会先涂红色，然后用橙色覆盖红色，即使红色在橙色之前.
对这些多边形进行排序的正确方法是什么?或者更一般地说，在实现画家算法时，您如何确定多边形的顺序?
这就是为什么我害怕自己动手z-buffer(在这个 5 岁的 i7 上遍历每个像素并随机为其分配一个约 10FPS 的颜色).
Z-sorting 通常比 Z-buffering 慢.您拥有的多边形越多越好，最好使用 Z 缓冲区.你对迭代的假设是错误的.Z 缓冲不是在每个多边形的基础上迭代，而是在每个像素的基础上迭代.
所以你得到多少多边形并不重要.重要的是以像素呈现的区域(重叠区域对它所属的每个多边形进行多次计算).所以你不能指望 500x500 屏幕和 10 多边形会得到 10*500*500 迭代.
我不使用 HTML5 画布 进行编码，但除非您可以直接访问像素和阴影后台缓冲区并自行光栅化多边形(或者像 GLSL 中的片段着色器一样可以访问它)，否则您将获得很难实现 z-buffering 即使它只是一个简单的 if 条件.我认为也可以使用模板或 alpha 遮罩来完成，但从未这样做过.
z 排序通常用于以下情况:
您没有足够的内存来存储 Z 缓冲区
这也可以推断出您的多边形复杂度和数量很少...
您已经对多边形进行了排序(由于创建它们的过程)
你需要正确的透明度
但是正如另一个答案所涵盖的那样，如果您的多边形与相机的距离相交，您需要将它们切割成更多.这种操作通常非常昂贵，以致于 z-sorting 的任何好处都被消耗的时间抵消了.这就是为什么即使对于 #3 也使用 z-buffering 并且排序是通过像这样的面部剔除来伪造的:
或者使用光线追踪的形式:
在某些情况下，Z-排序(对网格渲染顺序进行排序)和 Z-缓冲(按多边形顺序)结合使用.举个例子:
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:
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).
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:
You do not have enough memory to store Z-buffer
that also infers your polygon complexity and count is low...
You have polygons already sorted (due to process that created them)
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:
这篇关于在实现画家算法时，对多边形进行排序的正确方法是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
