实现画家算法时，排列多边形的正确方法是什么？

我正在写一个HTML5画布，所以使用z缓冲区看起来非常昂贵。例如，如果它是一个500x500的画布，并且不得不循环10个多边形，那么在CPU中完成每帧2,500,000次迭代。我不知道这是一个很大的数字，但它似乎是错误的方式来做这个应用程序。

画家算法似乎更合适。基本步骤是：

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

但我很困惑如何找到他们的z。假设我们从下列多边形中俯瞰：

如果我只是找到最大z（离屏幕最远），红色将被视为更远。所以它会先涂成红色，然后用橙色涂上红色，即使红色在橙色前面。

排序这些多边形的正确方法是什么？或者更一般地说，当实现画家算法时，您如何确定多边形的顺序？

编辑：this就是为什么我怕我自己的滚动Z缓存的（经过的每个像素，并随机分配它在这五年的老酷睿i7颜色〜10FPS）。

的复杂性是相同的。您可以对10个（修剪过的）三角形进行排序，并使用2.5M 2D像素操作盲目地绘制它们，或者使用z缓冲区为每个像素只添加一个z操作。只有在CG算法确定某些三角形完全被其他三角形遮挡的情况下才会带来好处。 –

三个三角形可以循环地相互覆盖，这意味着不存在通用的排序算法。相反，通常通过沿重叠边缘切割重叠的三角形形成新的三角形/多边形来解决问题，该三角形/多边形完全位于彼此的任一侧。

所讨论的两个多边形可以通过顶点与另一个多边形的平面方程的有符号距离进行OTOH排序。

2017-07-21 18:37:31

所有的多边形都放在一个大的列表中，然后运行排序算法，或者您应该尝试根据它们是否在x和y中重叠来对多边形进行分组？ – user1873073

通过边界框（对齐xyz或非对齐）或球体进行分组通常用于加快排序。 –

Z排序通常比较慢然后Z缓冲。你有更好的多边形是使用Z缓冲区。你对迭代的假设是错误的。 Z缓冲不是基于每个多边形进行迭代，而是基于每个像素进行迭代。

所以无论你得到多少多边形。重要的是以像素呈现的区域（重叠区域每个多边形占据多次一次）。所以你不能指望500x500屏幕和10多边形将得到10*500*500迭代。

我不HTML5画布代码，但除非你有直接像素访问和影后缓冲器和栅格化的多边形你自己（或有接取它像GLSL片段着色器），你会得到时间难以实现z缓冲即使它只是单个简单的条件。我认为它可以用模板或alpha蒙版来完成，但从来没有这样做过。

Z分级通常用在这些情况下：

但随着对方的回答涵盖了它，如果你的多边形的距离相交的相机，你需要将它们切割成多。这种操作通常非常昂贵，以至于消耗的时间会抵消z-sorting的任何益处。这就是为什么即使是＃3是使用Z缓冲和排序是由面部剔除像这样伪造：

或者光线追踪的使用形式：

在某些情况下，组合使用Z排序（排序网格渲染顺序）和Z缓冲（每个多边形顺序）。这里的一个示例：

2017-07-22 06:11:33 Spektre

回答