三角形和多边形的光栅化

三角形光栅化

• 定义：将一个三角形的内部区域填充为特定的颜色、纹理或图案的过程
• 输入：三角形顶点坐标$(x_1, y_1; x_2, y_2; x_3, y_3)$
• 输出：三角形内部所有像素点坐标
• 方法：逐点填充、扫描填充

逐点填充

伪代码实现：

TriangleRaster(triangle T) {
    for(int x=0;i<xmax;x++) {
        for(int y=0;j<ymax;y++) {
            if(Inside(T,x,y))
                putpixel(x,y);
        }
    }
}

点在三角形内外判定

面积法

1. 连接点$O$和三角形顶点得到三条线段$OA$, $OB$和$OC$
2. 依次求出$S(ABO)$, $S(ACO)$, $S(BCO)$
3. 如果$S(ABO)+S(ACO)+S(BCO)=S(ABC)$, 那么点$O$在三角形内
4. 如果$S(ABO)+S(ACO)+S(BCO)>S(ABC)$, 那么点$O$不在三角形内
   

内角和法

1. 连接点$P$和三角形顶点得到三条线段$PA$, $PB$和$PC$
2. 求出这三条线段与三角形各边的夹角
3. 如果所有夹角之和为180度，那么点$P$在三角形内，否则不在

面积法和内角和法简单直观，但效率低下

同侧判断法

分析

如果P在三角形$ABC$内部，则满足以下三个条件：

• P,A在BC同侧
• P,B在AC同侧
• P,C在AB同侧

某一个不满足则说明该点不在三角形内部

判断方法

将 $\vec{AP}$ 和 $\vec{AB}$ 做叉积，得到一个向量
将 $\vec{AC}$ 和 $\vec{AB}$ 做叉积，也得到一个向量
如果P与C在$AB$同侧，则两个向量的方向一致

判断向量同方向可以使用 点积

如果点积大于0, 则两向量夹角是锐角，否则钝角

伪代码实现：

bool PointInTriangle(Vector3 A, Vector3 B, Vector3 C, Vector3 P){
    return SameSide(A, B, C, P) && 
    SameSide(B, C, A, P) && SameSide(C, A, B, P);
}

bool SameSide(Vector3 A, Vector3 B, Vector3 C, Vector3 P){
    Vector3 AB = B - A; 
    Vector3 AC = C - A; 
    Vector3 AP = P - A; 
    Vector3 vl = AB.Cross(AC);  // AB X AC
    Vector3 v2 = AB.Cross(AP);  // AB X AP
    if (vl.Dot(v2) >= 0) // 点积 >= 0 
        return true;
    else 
        return false;
}

重心坐标法

三角形平面中任意点却可以表示为顶点的加权平均值，这些加权称为 重心坐标 (Barycentric Coordinates)

给定三角形A,B,C, 该平面内一点P可以写成这三点的线性组合形式，即 $P = \alpha A + \beta B + \gamma C$
其中 $\alpha + \beta + \gamma = 1$
P点的重心坐标即 $(\alpha, \beta, \gamma)$

将一点P与A,B,C三点直接连接, 构成三个三角形面积分别为 $A_{A}$，$A_{B}$，$A_{C}$
重心坐标 $\alpha$ $\beta$ $\gamma$ 分别为：

$\alpha = \frac{A_{A} } {A_{A}+A_{B}+A_{C} }$
$\beta = \frac{A_{B} } {A_{A} + A_{B} + A_{C} }$
$\gamma = \frac{A_{C} } {A_{A} + A_{B} + A_{C} }$

在三角形ABC所在平面中，以A为原点，AB, AC为向量构建坐标系，则P点可写为：

• $P = A+\beta(B-A)+\gamma(C-A)$
• $(1-\beta-\gamma)A+\beta B+\gamma C$
  其中，独立坐标的数量为 2

定位：

若点P要在三角形内部或边上，需要满足 $\alpha>=0$ 且$\beta>=0$且$\gamma>=0$, 否则点P在三角形所在平面外

插值：

可以根据三个顶点A,B,C的属性插值出任意点的属性，包括位置，颜色，深度，法线向量等
$P = \alpha A + \beta B + \gamma C$

重心坐标计算

1. 代数法

$$\begin{bmatrix} x_{B}-x_{A}&x_C-x_A\\ y_B-y_A&y_C-y_A\\ \end{bmatrix} \begin{bmatrix}\beta \\ \gamma \end{bmatrix} = \begin{bmatrix} x_p-x_A \\ y_P-y_A\end{bmatrix}$$

2. 几何法

$$P=A+u(B-A)+v(C-A)$$

$$A-P+u(B-A)+v(C-A)=0$$

$$u\vec{AB}+v\vec{AC}+\vec{PA}=0$$

考虑到坐标有

$$u\vec{AB_x}+v\vec{AC_x}+\vec{PA_x}=0$$

$$u\vec{AB_y}+v\vec{AC_y}+\vec{PA_y}=0$$

写成矩阵形式：

$$\begin{bmatrix} u&v&1 \end{bmatrix} \begin{bmatrix} \vec{AB_x} \\ \vec{AC_x} \\ \vec{PA_x} \end{bmatrix} = 0$$

$$\begin{bmatrix} u&v&1 \end{bmatrix} \begin{bmatrix} \vec{AB_y} \\ \vec{AC_y} \\ \vec{PA_y} \end{bmatrix} = 0$$

寻找向量$(u,v,1)$ 同时垂直于向量$V_x(\vec{AB_x},\vec{AC_x},\vec{PA_x})$和向量$V_y(\vec{AB_y},\vec{AC_y},\vec{PA_y})$
叉乘

$$V_x = (B_x-A_x , C_x-A_x , A_x-P_x)$$

$$V_y = (B_y-A_y , C_y-A_y , A_y-P_y)$$

$$U_z=V_x \times V_y$$

如果$U_z$不等于1则说明点P不在三角形内

扫描填充

思想

对于三角形的每一条扫描线，找到对应的左右端点所在区间并进行填充
步骤：

• 拆分，把三角形拆成上下两部分
• 对于上下两部分按下列步骤处理
  • 从$y_{min}$到$y_{max}$， 对每条扫描线求出扫描线对应的端点A和B
  • 在AB之间填充
    

利用增量不变可以加速计算，但也使得计算需要按照一定顺序访问像素点，也很难实现并行

扫描填充法如何提高效率?

选择合理的数据结构；
并行计算；
隔行扫描；
边缘表优化；
硬件加速；
优化内存访问;

---

多边形光栅化

填充多边形、圆、椭圆或其它简单曲线围成的区域
多边形光栅化，也称多边形扫描转换

区域的表示方法

顶点表示
优点：表示直观、几何意义强、占内存少，易于进行几何变换
缺点：无法直接用于着色
点阵表示
优点：利用多边形边界和内部像素刻画多边形
缺点：丢失了许多几何信息

多边形光栅化的基本问题：把多边形的顶点表示转换为点阵表示

逐点填充法

和三角形光栅化相似，主要问题是如何判断点是否在多边形内部

缺点

算法割断了各像素之间的联系，孤立地考察各像素与多边形的内外关系，使得大量像素都要一一判别
每次判别要多次求交，需要做大量乘除运算，费时

射线法：确定待判断点与多边形边界交点

方法

从待判别点P发出射线
求交点个数k

• 若k为奇数，点P位于多边形内
• 若k为偶数，点P位于多边形外
  • 奇点：射线与多边形边界点的交点为多边形的顶点
  • 极值点：顶点相邻的两边在射线的同侧（2个交点）
  • 非极值点：顶点相邻的两边在射线的异侧（1个交点）

累计角度法：利用多边形的顶点和待判断点之间的角度之和来确定点的位置

从v点向多边形P顶点发出射线，形成有向角$\theta_i$
计算有向角的和，得出结论

$$\sum _ {i=0} ^n \theta _i = \begin{cases} 0, & \text{$v$位于$P$之外} \\ \pm 2\pi, & \text{$v$位于$P$之内} \end{cases}$$

弧长法：计算以待判断点为圆心的单位圆上多边形各边投影的代数和来确定点的位置

方法

以待测点为圆心作单位圆
将全部有向边向单位圆作径向投影计算单位圆上各边投影代数之和$\Sigma$
若$\Sigma=0$, 则待测点在多边形外部
若$\Sigma=2\pi$，则待测点在多边形内部

伪代码实现

void FillPolygonPbyP(Polygon *P, int polygonColor) {
    int x, y;
    for(y = screen->ymin; y <= screen->ymax; y++) {
        for(x = screen->xmin; x <= screen->xmax; x++) {
            if(IsInside(P, x, y))
                PutPixel(x, y, polygonColor);
            else
                PutPixel(x, y, backgroundColor);
        }
    }
}

扫描线填充法

基本思想：按扫描线顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的像素

1. 确定多边形所占有的最大扫描线数: $y_{\text{min}}, y_{\text{max}}$
2. 从$y_{\text{min}}$到 $y_{\text{max}}$，对每条扫描线:
   a. 求交点
   b. 排序
   c. 交点配对 [关键步骤]
   d. 区间填色

计算扫描线与多边形顶点相交时，按上闭下开原则

当射线与多边形交于某顶点时且该点的两个邻边在射线的上方时，计数0次。
当射线与多边形交于某顶点时且该点的两个邻边在射线的下方时，计数2次。
当射线与多边形交于某顶点时且该点的两个邻边分别在射线的两侧时，计数1次。

void FillPolygonbySL(Polygon *P, int polygonColor) {
    int y;
    Edge e;
    for(y = ymin; y <= ymax; y++) {
        for(e = first->edge; e <= last->edge; e++) {
            if(IsIntersect(e, y))
                RecordPoint(x, y);
            SortPoint;
            配对; 
            Fill;
        }
    }
}

活动边表填充法

算法步骤：假定扫描线是从 $y=y_{\min}$ 开始向 $y=y_{\max}$ 的方向移动

1. 初始化ET
2. 初始化AET为空表
3. AET=ET表中的第一行
4. 从AET中取出交点对进行填充
5. $y_{i+1}=y_{i}+1$, 根据$x_{i+1}=x_{i}+1/k$修改 AET
   • 丢弃旧边：删除$y=y_{\max}$ 的边
   • 加入新边：合并ET表中$y=y_{i+1}$桶中的边，按次序插入到AET
6. AET不为空则转(4)，否则结束

• 优点:
  • 对每个像素只访问一次
  • 采用增量计算的方法进行交点计算
  • 仅仅在新边加入时排序，且边数远小于扫描线数（<<表示远小于）
• 缺点:
  • 对各种表的维持和排序开销较大
  • 适合软件实现而不适合硬件实现

边缘填充算法

基本思想

• 计算每一条边与扫描线的交点
• 逐边向右取补（异或写）

优点：简单
缺点：重复访问像素点

栅栏填充算法

栅栏：一条过多边形顶点且与扫描线垂直的直线

• 利用栅栏把多边形分为两半
• 基本思想：按任意顺序处理多边形的每条边，在处理每条边与扫描线的交点间的像素取补

边标志算法

先画边界后填色

基本思想

1. 用一种特殊的颜色在帧缓冲器中将多边形的边界勾画出来；
2. 将着色的像素点依x坐标递增的顺序两两配对；
3. 将每一对像素所构成的扫描线区间内的所有像素值为填充色；

具体步骤:

• 打标记: 对多边形的每条边进行直线扫描转换（将多边形边界所经过的像素打上标记）
• 填充:
  • 设置布尔量inside: 内部，真；外部，假
  • 初值：假
  • 遇到标记点：取反
  • 真：填充
  • 假：不填充

算法分析:

• 边标志算法对每个像素仅访问一次:
  与边缘填充算法和栅栏填充算法相比，避免了对帧缓存中大量元素的多次赋值，但仍然需逐条扫描线地对帧缓存中的元素进行搜索和比较。
• 利用硬件实现:
  当用软件实现算法时，速度与改进的活动边表算法相当，但本算法用硬件实现后速度会有很大提高