algorithm - 以 x,y 位置的形式获取三角形内的位置列表

Question

假设我有一个由三个整数顶点 (x1,y1)、(x2,y2) 和 (x3,y3) 给出的三角形。我可以使用哪种算法来返回位于三角形内的所有 (x,y) 整数对的完整列表。

Answer 1

这个问题的正确名称是三角形 rasterization .

这是一个经过深入研究的问题，有多种方法可以解决。两种流行的方法是:

1. 逐行扫描。

   对于每条扫描线，您需要一些基本的几何形状来重新计算 行的开始和结束。参见 Bresenham's Line drawing algorithm .

2. 测试边界框中的每个像素，看它是否在 三角形。

   这通常是通过使用 barycentric 来完成的坐标。

大多数人认为方法 1) 更有效，因为您不会浪费时间测试可能位于三角形外部的像素，大约是边界框中所有像素的一半。然而，2) 有一个主要优势——它可以更容易地并行运行，因此对于硬件来说通常是更快的选择。 2) 编码也更简单。

原文paper用于准确描述如何使用方法 2) 的文章由 Juan Pineda 于 1988 年编写，称为“A Parallel Algorithm for Polygon Rasterization”。

对于三角形，它在概念上非常简单(如果您学习了重心坐标)。如果将每个像素转换为三角形重心坐标、alpha、beta 和 gamma - 那么简单的测试是 alpha、beta 和 gamma 必须在 0 和 1 之间。