目标
光栅化2D三角形（scan conversion）。避免重复光栅化相邻三角形边界的像素（edge equation）。
- 光栅化空心三角形
- 光栅化实心三角形
- 避免重复光栅化相邻三角形边界的像素
实现
继续为ImageRaster增加光栅化三角形的功能。
空心三角形
这一步几乎不需要做任何多余的事情，直接调用3次 drawLine 就行。
/**
* 画空心三角形
*
*/
public void drawTriangle(int x0, int y0, int x1, int y1, int x2, int y2, ColorRGBA color) {
drawLine(x0, y0, x1, y1, color);
drawLine(x0, y0, x2, y2, color);
drawLine(x2, y2, x1, y1, color);
}
实心三角形
这个功能参考：从零实现3D图像引擎：(15)三角形的光栅化
基本思路是，先把任意三角形转变成“平底三角形”或“平顶三角形”，然后逐行扫描划线。
平顶实心三角形的画法实现如下。
/**
* 画平顶实心三角形
*/
private void fillTopLineTriangle(int x0, int y0, int x1, int y1, int x2, int y2, ColorRGBA color) {
for (int y = y0; y <= y2; y++) {
int xs, xe;
xs = (int) ((y - y0) * (x2 - x0) / (y2 - y0) + x0 + 0.5);
xe = (int) ((y - y1) * (x2 - x1) / (y2 - y1) + x1 + 0.5);
drawLine(xs, y, xe, y, color);
}
}
平底实心三角形的画法几乎一模一样，只是把y坐标改了改。
/**
* 画平底实心三角形
*/
private void fillBottomLineTriangle(int x0, int y0, int x1, int y1, int x2, int y2, ColorRGBA color) {
for (int y = y0; y <= y1; y++) {
int xs, xe;
xs = (int) ((y - y0) * (x1 - x0) / (y1 - y0) + x0 + 0.5);
xe = (int) ((y - y0) * (x2 - x0) / (y2 - y0) + x0 + 0.5);
drawLine(xs, y, xe, y, color);
}
}
完整的实心三角形画法如下。
/**
* 画实心三角形
*/
public void fillTriangle(int x0, int y0, int x1, int y1, int x2, int y2, ColorRGBA color) {
if (y0 == y1) {
if (y2 <= y0) // 平底
{
fillBottomLineTriangle(x2, y2, x0, y0, x1, y1, color);
} else // 平顶
{
fillTopLineTriangle(x0, y0, x1, y1, x2, y2, color);
}
} else if (y0 == y2) {
if (y1 <= y0) // 平底
{
fillBottomLineTriangle(x1, y1, x0, y0, x2, y2, color);
} else // 平顶
{
fillTopLineTriangle(x0, y0, x2, y2, x1, y1, color);
}
} else if (y1 == y2) {
if (y0 <= y1) // 平底
{
fillBottomLineTriangle(x0, y0, x1, y1, x2, y2, color);
} else // 平顶
{
fillTopLineTriangle(x1, y1, x2, y2, x0, y0, color);
}
} else {
int xtop = 0, ytop = 0, xmiddle = 0, ymiddle = 0, xbottom = 0, ybottom = 0;
if (y0 < y1 && y1 < y2) // y1 y2 y3
{
xtop = x0;
ytop = y0;
xmiddle = x1;
ymiddle = y1;
xbottom = x2;
ybottom = y2;
} else if (y0 < y2 && y2 < y1) // y1 y3 y2
{
xtop = x0;
ytop = y0;
xmiddle = x2;
ymiddle = y2;
xbottom = x1;
ybottom = y1;
} else if (y1 < y0 && y0 < y2) // y2 y1 y3
{
xtop = x1;
ytop = y1;
xmiddle = x0;
ymiddle = y0;
xbottom = x2;
ybottom = y2;
} else if (y1 < y2 && y2 < y0) // y2 y3 y1
{
xtop = x1;
ytop = y1;
xmiddle = x2;
ymiddle = y2;
xbottom = x0;
ybottom = y0;
} else if (y2 < y0 && y0 < y1) // y3 y1 y2
{
xtop = x2;
ytop = y2;
xmiddle = x0;
ymiddle = y0;
xbottom = x1;
ybottom = y1;
} else if (y2 < y1 && y1 < y0) // y3 y2 y1
{
xtop = x2;
ytop = y2;
xmiddle = x1;
ymiddle = y1;
xbottom = x0;
ybottom = y0;
}
int xl; // 长边在ymiddle时的x，来决定长边是在左边还是右边
xl = (int) ((ymiddle - ytop) * (xbottom - xtop) / (ybottom - ytop) + xtop + 0.5);
if (xl <= xmiddle) // 左三角形
{
// 画平底
fillBottomLineTriangle(xtop, ytop, xl, ymiddle, xmiddle, ymiddle, color);
// 画平顶
fillTopLineTriangle(xl, ymiddle, xmiddle, ymiddle, xbottom, ybottom, color);
} else // 右三角形
{
// 画平底
fillBottomLineTriangle(xtop, ytop, xmiddle, ymiddle, xl, ymiddle, color);
// 画平顶
fillTopLineTriangle(xmiddle, ymiddle, xl, ymiddle, xbottom, ybottom, color);
}
}
}
测试用例
让我写个例子测试一下效果如何。
先定义一个2D三角形，实现Drawable接口。在draw方法中调用ImageRaster绘制三角形。
package net.jmecn.geom;
import net.jmecn.math.ColorRGBA;
import net.jmecn.renderer.ImageRaster;
/**
* 代表一个三角形。
*
* @author yanmaoyuan
*
*/
public class Triangle2D implements Drawable {
public int x0, y0;
public int x1, y1;
public int x2, y2;
public ColorRGBA color = ColorRGBA.RED;
public boolean isSolid = true;// 是否实心
@Override
public void draw(ImageRaster imageRaster) {
if (isSolid) {
imageRaster.fillTriangle(x0, y0, x1, y1, x2, y2, color);
} else {
imageRaster.drawTriangle(x0, y0, x1, y1, x2, y2, color);
}
}
}
再写个 Test2DTriangle 类来显示结果。
package net.jmecn.examples;
import java.util.Random;
import net.jmecn.Application;
import net.jmecn.geom.Triangle2D;
import net.jmecn.math.ColorRGBA;
/**
* 绘制2D三角形
*
* @author yanmaoyuan
*
*/
public class Test2DTriangles extends Application {
public static void main(String[] args) {
Test2DTriangles app = new Test2DTriangles();
app.setResolution(720, 405);
app.setTitle("2D Triangles");
app.setFrameRate(120);
app.start();
}
/**
* 初始化
*/
@Override
protected void initialize() {
Random rand = new Random();
/**
* 随机生成三角形
*/
for(int i=0; i<10; i++) {
Triangle2D tri = new Triangle2D();
tri.x0 = rand.nextInt(width);
tri.y0 = rand.nextInt(height);
tri.x1 = rand.nextInt(width);
tri.y1 = rand.nextInt(height);
tri.x2 = rand.nextInt(width);
tri.y2 = rand.nextInt(height);
tri.color = new ColorRGBA(rand.nextInt(0x4FFFFFFF));
tri.isSolid = rand.nextFloat() > 0.5f;
// 添加到场景中
scene.add(tri);
}
}
@Override
protected void update(float delta) {
}
}
效果如下：
总结
实现了基本的三角形光栅化，没有达成第三个目标，即解决“避免重复光栅化相邻三角形边界的像素”这个问题。
fillTriangle方法还有一些可以优化的余地，优化思路有：
- 为了判断三角形是否有一条边是“平”的，可以先按y坐标对三个顶点进行排序；
- 在画扫描线的时候，线段的两个端点坐标，还可以通过Bresenham算法来同步计算；
- 避免重复光栅化相邻三角形边界的像素。
但是我现在对2D光栅化的实现已经有些腻了。关于这些算法，网上有大量的资料和可参考的代码，对我学习和理解这些算法的原理来说已经足够，没有必要再实现一遍。
其次，我想早点开始实现3D渲染管线。目前的2D光栅器在3D渲染阶段早晚要重做，所以干脆直接进入下一阶段吧！等完成了3D渲染之后，再回头来做这些优化也不迟。
原计划，2D阶段还有这些功能要做，现在放弃。
- 光栅化2D多边形；
- 顶点着色/颜色插值；
- 绘制bmp图片；
- 二维几何变换；
- 按键控制窗口运动，改变观察范围。