在Bresenham画线算法及实践一文中讲到了如何将理想的直线绘制到由一个个离线的像素组成的屏幕上的过程，这个过程就是光栅化。本文介绍如何实现三角形的光栅化，绘制三角形和绘制线段不同，因为三角形不仅包含线段，还涉及三角形内部的着色问题。
理解三角形的绘制原理
1. 包围三角形的矩形框
首先，可以考虑把三角形限制在一个矩形框内，只要逐一遍历矩形内的像素坐标，位于三角形内的点才进行绘制。那么接下来就需要知道如何判定矩形内的点坐标是不是在三角形内，以及这个点颜色该如何确定。
2. 重心坐标
我们先来看如何判定一个点是不是在由a、b、c三个点组成的三角形内。如下图所示，如果我们把a看作坐标原点、向量ab为横坐标且作为单位向量、向量ac为纵坐标且作为单位向量，那么实际上就它们就构成了一个非正交坐标系，β为横坐标、γ为纵坐标。
根据向量的运算法则可以得出任意点p的坐标为
变换之后可以表示为
把1-β-γ简化为α（也就是a+β+γ=1），则p点的坐标公式又可简化为
当p位于三角形内时，(α、β、γ)被称为p点的重心坐标，且0<α、β、γ<1；如果其中一个为0则落在某一边上，两个为0则落在顶点上。
我们还知道通过(x0,y0)、(x1,y1)两点的直线方程可以表示为如下方程的形式，如fca表通过点a、c的直线方程，那么所有平行于ac所在直线的坐标fca(x,y)的值与β存在线性比例关系；同样的fab(x,y)与γ存在比例关系、fbc(x,y)与α存在比例关系。
据此线性关系，α、β、γ的值可以通过p点的(x,y)坐标计算如下：
注：本文重点偏向图形学的应用，相关数学公式建议能直观地理解其含义就行，如需详细推导过程建议参阅参考文献中的章节。
3. 颜色插值
确定了点是否在三角形内部之后，我们通过如下公式来内插出该点的颜色(c0，c1、c2为三角形三个点的颜色值)
使用canvas实现三角形绘制
我们使用html canvas来编写代码实现三角形的光栅化绘制，之所以选择canvas来实践图形学，是因为它不需要任何的环境准备、工具安装，只要打开浏览器和编辑器就可以开撸代码并观察效果了，而且canvas本身提供的方法我们也只用到设置单个像素的颜色就行了，用不到其他任何额外的方法。如果你对图形学感兴趣的话，你完全可以从绘制一个简单的点开始一步步地实践3D、动画等复杂的场景是如何一步步构建起来的。
废话不多说了，下面直接列出代码及显示的效果，关键代码已做了注释，示例中绘制了三个三角形，渲染效果如下：
index.html
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>三角形光栅化</title>
</head>
<body>
<canvas id="canvas" width="780" height="780"></canvas>
<script src="./triangle.js"></script>
</body>
</html>
triangle.ts，这里使用的是typescript语言编写，只需要执行tsc命令编译成js文件即可
interface Point {
x: number;
y: number;
}
interface Color {
r: number;
g: number;
b: number;
a: number;
}
function add(c1: Color, c2: Color): Color {
return {
r: c1.r + c2.r,
g: c1.g + c2.g,
b: c1.b + c2.b,
a: c1.a + c2.a
}
}
function scale(c1: Color, s: number): Color {
return {
r: c1.r * s,
g: c1.g * s,
b: c1.b * s,
a: c1.a * s
}
}
class Painter {
canvas: HTMLCanvasElement;
ctx: any;
constructor(canvas: HTMLCanvasElement) {
this.canvas = canvas;
this.ctx = this.canvas.getContext("2d");
}
// 设置像素坐标(x,y)颜色为c
setPixel(x: number, y: number, c: Color = {r:255,g:255,b:255,a:1.0}) {
let c_str = "rgba(" + c.r + "," + c.g + "," + c.b + "," + c.a + ")";
this.ctx.fillStyle = c_str;
this.ctx.fillRect(x, y, 1, 1);
}
// 清空画布背景为黑色
clear() {
this.ctx.fillStyle = "0x000000";
this.ctx.fillRect(0, 0, this.canvas.clientWidth, this.canvas.clientHeight);
}
// 绘制三角形
drawTriangle(p0:Point, p1:Point, p2:Point,
c0: Color={r: 255, g: 0, b: 0, a: 1},
c1: Color={r: 0, g: 255, b: 0, a: 1},
c2: Color={r: 0, g: 0, b: 255, a: 1}) {
// p2
// / \
// / \
// p0------p1
let [x0, y0, x1, y1, x2, y2] = [p0.x, p0.y, p1.x, p1.y, p2.x, p2.y];
// 获取包围三角形的矩形框
let xmin = Math.min(x0, x1, x2);
let xmax = Math.max(x0, x1, x2);
let ymin = Math.min(y0, y1, y2);
let ymax = Math.max(y0, y1, y2);
// 经过两点的直线方程函数形式
// f01(x, y) = (y0 ? y1)x + (x1 ? x0)y + x0y1 ? x1y0
let f01 = (x, y) => (y0 - y1) * x + (x1 - x0) * y + x0 * y1 - x1 * y0;
// f12(x, y) = (y1 ? y2)x + (x2 ? x1)y + x1y2 ? x2y1
let f12 = (x, y) => (y1 - y2) * x + (x2 - x1) * y + x1 * y2 - x2 * y1;
// f20(x, y) = (y2 ? y0)x + (x0 ? x2)y + x2y0 ? x0y2
let f20 = (x, y) => (y2 - y0) * x + (x0 - x2) * y + x2 * y0 - x0 * y2;
let fa = f12(x0, y0);
let fb = f20(x1, y1);
let fr = f01(x2, y2);
// 遍历矩形框内的像素坐标
for (let y = ymin; y < ymax; y++) {
for (let x = xmin; x < xmax; x++) {
// 计算α、β、γ的值
let a = f12(x, y) / fa;
let b = f20(x, y) / fb;
let r = f01(x, y) / fr;
// 计算α、β、γ的范围>=0表示在三角形内、边或顶点
if (a >= 0 && b >= 0 && r >= 0) {
// 如果多个三角形有存在公共边的情况下，如果不加判断就会三角形公共边多次绘制的情况
// 这种公共边的情况我们只选择一个三角形的边进行绘制即可
// 为了避免多次绘制的问题（其实从效果上看不出区别），增加的下面的判断只是为了
// 只绘制与坐标(-1,-1)（选择的是一个不在屏幕中的点）在同一侧的那个三角形的边
if ((a > 0 || fa * f12(-1, -1) > 0) &&
(b > 0 || fb * f20(-1, -1) > 0) &&
(r > 0 || fr * f01(-1, -1) > 0)) {
// 计算颜色插值
let c = add(add(scale(c0, a), scale(c1, b)), scale(c2, r));
// 绘制像素颜色
this.setPixel(x, y, c);
}
}
}
}
}
}
var app = function() {
var canvas = <HTMLCanvasElement> document.getElementById("canvas");
var painter = new Painter(canvas);
painter.clear();
// 绘制中间三角形
painter.drawTriangle({x: 290, y: 490}, {x: 490, y: 490}, {x: 390, y: 290});
// 绘制右侧三角形
painter.drawTriangle({x: 390, y: 290}, {x: 490, y: 490}, {x: 590, y: 190});
// 绘制左侧三角形
painter.drawTriangle({x: 190, y: 190}, {x: 290, y: 490}, {x: 390, y: 290});
}
app();
参考文献
[1]. 《fundamentals of computer graphics》9.1.2 Triangle Rasterization, P182;