第1关：扫描线填充法

一. 任务描述

1. 本关任务

了解和掌握扫描线填充法，实现对三角形区域进行填充，具体要求如下： (1) 补全triangle函数; (2) 将main函数中的三角形顶点坐标和triangle函数参数补充完整。

2. 输入

(1) 三角形的三个顶点的坐标:
t0 = {125,50}， t1 = {300,200}， t2 ={200,350};
(2) 三角形区域为蓝色。

3. 输出

程序运行结果为一个蓝色三角形区域，如下图所示：

二. 相关知识

1. 绘制点函数

image.set(x, y, color)函数用来绘制点，其中参数x,y为点的坐标，color为点的颜色。

2. 扫描线填充方法

如果想绘制一个三角形，最简单的方法是，对于三角形边界上每个点的y坐标，我们找到对应的左右两边界的X坐标y_left(A)和y_right(B) 从三角形的最低顶点开始，沿着你的方法一直到顶部，用扫描线法填充它。
为了简单起见，让我们将三角形分成上部和下部分：

对于一个特定的y，如果我们想找到它的左右点A和B，思路是这样的:
首先排序，保证 t0 ≤ t1 ≤ t2; 整个三角形的y坐标高度为 t2.y - t0.y; 对于下半部分，y每增加1点(有可能t0 == t1)我们就用插值来求出对应的点A和点B。 扫描线算法的部分示意代码如下，其中Vec2i是定义一个点的x和y坐标的结构体，参数t0, t1, t2对应三角形的三个顶点坐标：

1. void triangle(Vec2i t0, Vec2i t1, Vec2i t2) {
2. // sort the vertices, t0, t1, t2 lower−to−upper
3. if (t0.y>t1.y) std::swap(t0, t1);
4. if (t0.y>t2.y) std::swap(t0, t2);
5. if (t1.y>t2.y) std::swap(t1, t2);
6. int total_height = t2.y-t0.y;
7. //lower parts
8. for (int y=t0.y; y<=t1.y; y++) {
9. int segment_height = t1.y-t0.y+1; //be careful with divisions by zero
10. float alpha = (float)(y-t0.y)/total_height; //edge t0t2
11. float beta = (float)(y-t0.y)/segment_height; //edge t0t1
12. Vec2i A,B;
13. A.y=B.y=y;
14. A.x = t0.x + (t2.x-t0.x)*alpha;
15. B.x = t0.x + (t1.x-t0.x)*beta;
16. if (A.x>B.x) std::swap(A.x, B.x);
17. for (int x=A.x; x<=B.x; x++) {
18. image.set(x, y, color);
19. }
20. }
21. //upper parts
22. for (int y = t1.y; y <= t2.y; y++){
23. ... //Please refer to the above code to program
24. ...
25. }
26. }

三. 操作说明

(1) 按要求补全代码； (2) 点击窗口右下角"测评"按钮，等待测评结果，如果通过后可进行下一关任务。

---

开始你的任务吧，祝你成功！

四、实验代码

#include "pngimage.h"
#include<stdio.h>
#include <iostream>struct Vec2i
{int x, y;
};void triangle(Vec2i t0, Vec2i t1, Vec2i t2, PNGImage&  image, PNGColor color) {// Please add your code here/********** Begin ********///根据三个顶点y坐标大小，保证t0.y <= t1.y <= t2.y，这样确定好分为上下部分//根据图可以知道为右三角形 if (t0.y>t1.y) std::swap(t0, t1);if (t0.y>t2.y) std::swap(t0, t2); if (t1.y>t2.y) std::swap(t1, t2); int tH = t2.y-t0.y;//总共的高度为最高点y坐标减最低点y坐标 for (int y=t0.y; y<=t1.y; y++)//下部分扫描 { int xsH = t1.y-t0.y+1;//下部分高度    float a = (float)(y-t0.y)/tH;//a为从t0.y到当前行之间的比例,y不断变化下移//b为从t0.y到当前行之间的比例       float b  = (float)(y-t0.y)/xsH;    Vec2i A,B;A.y=B.y=y;A.x = t0.x + (t2.x-t0.x)*a,B.x = t0.x + (t1.x-t0.x)*b;// 计算A点的横坐标//计算B点的横坐标if (A.x>B.x) std::swap(A.x, B.x);//确保B点在A点右边，即B点横坐标大于A点横坐标 for (int x=A.x; x<=B.x; x++) { image.set(x, y, color);//指定位置的指定颜色函数  } } 
for (int y=t1.y; y<=t2.y; y++)//上部分扫描 
{ int ssH = t2.y-t1.y+1;//上部分高度    float a = (float)(y-t0.y)/tH;//a为从t0.y到当前行之间的比例,y不断变化下移      float b  = (float)(y-t1.y)/ssH;//b为从t1.y到当前行之间的比例    Vec2i A,B;A.y=B.y=y;A.x = t0.x + (t2.x-t0.x)*a,B.x = t1.x + (t2.x-t1.x)*b;// 计算A点的横坐标//计算B点的横坐标 if (A.x>B.x) std::swap(A.x, B.x);//确保B点在A点右边，即B点横坐标大于A点横坐标 for (int x=A.x; x<=B.x; x++) { image.set(x, y, color);//指定位置的指定颜色函数  } } /********** End **********/
}int main(int argc, char** argv) {PNGColor white = PNGColor(255, 255, 255, 255);PNGColor black = PNGColor(0, 0, 0, 255);PNGColor red = PNGColor(255, 0, 0, 255);PNGColor blue = PNGColor(0, 255, 255, 255);int width = 400;int height = 400;PNGImage image(width, height, PNGImage::RGBA); //Error when RGB because lodepng_get_raw_size_lct(w, h, colortype, bitdepth) > in.size() in encodeimage.init(black);// Please add your code here/********** Begin ********/Vec2i t0 = {125 , 50}, t1 = { 300,200 }, t2 = {200 ,350 };triangle(t0,t1,t2,image,PNGColor(0,255,255,255));/********** End **********/image.flip_vertically(); // i want to have the origin at the left bottom corner of the imageimage.write_png_file("../img_step3/test.png");return 0;
}