目录
优化2:若三角形是否在屏幕范围内or屏幕是否在一个巨大的三角形内
如何判断一个点在三角形中?
判断点p与pi是否在ei的同一侧

比如,看p点和p2这两个点。
判断此时p的x值,再计算此x值在e2边上的y值。
我们就知道了:p点的y值,和e2上的y值。
如果这p点y值和p2点y值都小于e2上的y值,则说明p和p2点在e2的同一侧。
其他两个点同理。都需要两两在对边的同一侧,即p点在三角形的同一侧,即在三角形内部。
根据这个原理,来实现函数:

最直观的想法:遍历所有像素,判断点是否在三角形中,如果在则绘制。
但是太浪费了,做一个包围盒优化:

这样只需遍历包围盒即可,不用遍历整个屏幕
- void Canvas::drawTriange(Point p1, Point p2, Point p3){
- RGBA _color(255, 0, 0);
-
- //构建包围盒
- int left = MIN(p3.m_x, MIN(p1.m_x, p2.m_x));
- int top = MIN(p3.m_y, MIN(p1.m_y, p2.m_y));
- int right = MAX(p3.m_x, MAX(p1.m_x, p2.m_x));
- int bottom = MAX(p3.m_y, MAX(p1.m_y, p2.m_y));
-
- //裁剪屏幕
- left = left < 0 ? 0 : left;
- top = top < 0 ? 0 : top;
- right = right > (m_width - 1) ? m_width - 1 : right;
- bottom = bottom > (m_height - 1) ? m_height - 1 : bottom;
-
- //计算直线参数值
- float k1 = (float)(p2.m_y - p3.m_y) / (float)(p2.m_x - p3.m_x);
- float k2 = (float)(p1.m_y - p3.m_y) / (float)(p1.m_x - p3.m_x);
- float k3 = (float)(p2.m_y - p1.m_y) / (float)(p2.m_x - p1.m_x);
-
- //计算直线的b值
- float b1 = (float)p2.m_y - k1 * (float)p2.m_x;
- float b2 = (float)p3.m_y - k2 * (float)p3.m_x;
- float b3 = (float)p1.m_y - k3 * (float)p1.m_x;
-
- //循环判断
- for (int x = left; x <= right; x++) {
- for (int y = top; y <= bottom; y++) {
- //判断是否在当前点是否在三角形内
- float judge1 = (y - (k1 * x + b1)) * (p1.m_y - (k1 * p1.m_x + b1));
- float judge2 = (y - (k2 * x + b2)) * (p2.m_y - (k2 * p2.m_x + b2));
- float judge3 = (y - (k3 * x + b3)) * (p3.m_y - (k3 * p3.m_x + b3));
-
- if (judge1 >= 0 && judge2 >= 0 && judge3 >= 0) {
- drawPoint(x, y, _color);
- }
- }
- }
-
-
- }
- void Render() {
- _canvas->clear();
-
- GT::Point p1(0, 0, GT::RGBA(255, 0, 0));
- GT::Point p2(100, 50, GT::RGBA(255, 0, 0));
- GT::Point p3(150, 200, GT::RGBA(255, 0, 0));
-
- _canvas->drawTriange(p1, p2, p3);
-
- //在这里画到设备上,hMem相当于缓冲区
- BitBlt(hDC, 0, 0, wWidth, wHeight, hMem, 0, 0, SRCCOPY);
- }


直白来讲,就是将三角形分为若干个平顶/平底三角形。
而平顶/平底三角形的绘制则可以通过之前的Brensenhem直线绘制来实现:
最后,需要考虑直角三角形,需要特殊判断点的x坐标。
- void Canvas::drawTriangeFlat(Point pFlat1, Point pFlat2, Point pt){
- //两边直线斜率
- float k1 = 0.0;
- float k2 = 0.0;
-
- if (pFlat1.m_x != pt.m_x) {
- k1 = (float)(pFlat1.m_y - pt.m_y) / (float)(pFlat1.m_x - pt.m_x);
- }
- if (pFlat2.m_x != pt.m_x) {
- k2 = (float)(pFlat2.m_y - pt.m_y) / (float)(pFlat2.m_x - pt.m_x);
- }
-
- //两直线b值
- float b1 = (float)pt.m_y - (float)pt.m_x * k1;
- float b2 = (float)pt.m_y - (float)pt.m_x * k2;
-
- //做垂线
- int yStart = MIN(pt.m_y, pFlat1.m_y);
- int yEnd = MAX(pt.m_y, pFlat1.m_y);
- for (int y = yStart; y <= yEnd; ++y) {
- int x1 = 0;
- //判断是否为直角三角形
- if (k1 == 0) {
- x1 = pFlat1.m_x;
- }
- else {
- x1 = ((float)y - b1) / k1;
- }
-
- int x2 = 0;
- //判断是否为直角三角形
- if (k2 == 0) {
- x2 = pFlat2.m_x;
- }
- else {
- x2 = ((float)y - b2) / k2;
- }
-
- //构建这两个点
- Point pt1(x1, y, RGBA(255, 0, 0));
- Point pt2(x2, y, RGBA(255, 0, 0));
-
- //绘制直线
- drawLine(pt1, pt2);
- }
- }
- void Render() {
- _canvas->clear();
-
- GT::Point p1(100, 100, GT::RGBA(255, 0, 0));
- GT::Point p2(200, 100, GT::RGBA(255, 0, 0));
- GT::Point p3(150, 150, GT::RGBA(255, 0, 0));
-
- _canvas->drawTriangeFlat(p1, p2, p3);
-
- //在这里画到设备上,hMem相当于缓冲区
- BitBlt(hDC, 0, 0, wWidth, wHeight, hMem, 0, 0, SRCCOPY);
- }

是白色的,原因是上节的color插值没有变化,不过原理是对的。

先给三个点按y值排序,然后分上下两个平顶/平底三角形
- void Canvas::drawTriange(Point p1, Point p2, Point p3) {
- std::vector
pVec; - pVec.push_back(p1);
- pVec.push_back(p2);
- pVec.push_back(p3);
-
- std::sort(pVec.begin(), pVec.end(), [](const Point& p1, const Point& p2) {
- return p1.m_y > p2.m_y;
- });
-
- //获取三个排序好的点
- Point ptMax = pVec[0];
- Point ptMid = pVec[1];
- Point ptMin = pVec[2];
-
- //判断是否为平顶平底三角形
- if (ptMax.m_y == ptMid.m_y) {
- drawTriangeFlat(ptMax, ptMid, ptMin);
- return;
- }
- if (ptMin.m_y == ptMid.m_y) {
- drawTriangeFlat(ptMin, ptMid, ptMax);
- return;
- }
-
- //计算直线参数k b
- float k = 0.0;
- if (ptMax.m_x != ptMin.m_x) {
- k = (float)(ptMax.m_y - ptMin.m_y) / (float)(ptMax.m_x - ptMin.m_x);
- }
- float b = (float)ptMax.m_y - (float)ptMax.m_x * k;
- Point newPoint(0, 0, RGBA(255, 0, 0));
- newPoint.m_y = ptMid.m_y;
- if (k == 0) {
- newPoint.m_x = ptMax.m_x;
- }
- else {
- newPoint.m_x = ((float)newPoint.m_y - b) / k;
- }
-
- //分别绘制这两个平顶/平底三角形
- drawTriangeFlat(ptMid, newPoint, ptMax);
- drawTriangeFlat(ptMid, newPoint, ptMin);
-
- return;
- }
- void Render() {
- _canvas->clear();
-
- GT::Point p1(700, 500, GT::RGBA(255, 0, 0));
- GT::Point p2(200, 100, GT::RGBA(255, 0, 0));
- GT::Point p3(150, 150, GT::RGBA(255, 0, 0));
-
- _canvas->drawTriange(p1, p2, p3);
-
- //在这里画到设备上,hMem相当于缓冲区
- BitBlt(hDC, 0, 0, wWidth, wHeight, hMem, 0, 0, SRCCOPY);
- }

此时需要判断,避免无意义的遍历

判断:
实现如下:
- bool Canvas::judgeInTriangle(Point pt, std::vector
_ptArray) { - Point pt1 = _ptArray[0];
- Point pt2 = _ptArray[1];
- Point pt3 = _ptArray[2];
-
- int x = pt.m_x;
- int y = pt.m_y;
-
- //三个k
- float k1 = (float)(pt1.m_y - pt2.m_y) / (float)(pt1.m_x - pt2.m_x);
- float k2 = (float)(pt1.m_y - pt3.m_y) / (float)(pt1.m_x - pt3.m_x);
- float k3 = (float)(pt3.m_y - pt2.m_y) / (float)(pt3.m_x - pt2.m_x);
-
- //三个b
- float b1 = (float)pt1.m_y - k1 * pt1.m_x;
- float b2 = (float)pt3.m_y - k2 * pt3.m_x;
- float b3 = (float)pt2.m_y - k3 * pt2.m_x;
-
- //是否在三角形内
- float judge1 = (y - (k1 * x + b1)) * (pt3.m_y - (k1 * pt3.m_x + b1));
- float judge2 = (y - (k2 * x + b2)) * (pt2.m_y - (k2 * pt2.m_x + b2));
- float judge3 = (y - (k3 * x + b3)) * (pt1.m_y - (k3 * pt1.m_x + b3));
-
- if (judge1 > 0 && judge2 > 0 && judge3 > 0)
- {
- return true;
- }
-
- return false;
- }
-
- void Canvas::drawTriange(Point p1, Point p2, Point p3) {
- std::vector
pVec; - pVec.push_back(p1);
- pVec.push_back(p2);
- pVec.push_back(p3);
-
- std::sort(pVec.begin(), pVec.end(), [](const Point& p1, const Point& p2) {
- return p1.m_y > p2.m_y;
- });
-
- //获取三个排序好的点
- Point ptMax = pVec[0];
- Point ptMid = pVec[1];
- Point ptMin = pVec[2];
-
- //判断是否为平顶平底三角形
- if (ptMax.m_y == ptMid.m_y) {
- drawTriangeFlat(ptMax, ptMid, ptMin);
- return;
- }
- if (ptMin.m_y == ptMid.m_y) {
- drawTriangeFlat(ptMin, ptMid, ptMax);
- return;
- }
-
- //计算直线参数k b
- float k = 0.0;
- if (ptMax.m_x != ptMin.m_x) {
- k = (float)(ptMax.m_y - ptMin.m_y) / (float)(ptMax.m_x - ptMin.m_x);
- }
- float b = (float)ptMax.m_y - (float)ptMax.m_x * k;
- Point newPoint(0, 0, RGBA(255, 0, 0));
- newPoint.m_y = ptMid.m_y;
- if (k == 0) {
- newPoint.m_x = ptMax.m_x;
- }
- else {
- newPoint.m_x = ((float)newPoint.m_y - b) / k;
- }
-
- //分别绘制这两个平顶/平底三角形
- drawTriangeFlat(ptMid, newPoint, ptMax);
- drawTriangeFlat(ptMid, newPoint, ptMin);
-
- return;
- }
在Canvas::drawTriangeFlat中进行剪裁:
- void Canvas::drawTriangeFlat(Point pFlat1, Point pFlat2, Point pt){
- //两边直线斜率
- float k1 = 0.0;
- float k2 = 0.0;
-
- if (pFlat1.m_x != pt.m_x) {
- k1 = (float)(pFlat1.m_y - pt.m_y) / (float)(pFlat1.m_x - pt.m_x);
- }
- if (pFlat2.m_x != pt.m_x) {
- k2 = (float)(pFlat2.m_y - pt.m_y) / (float)(pFlat2.m_x - pt.m_x);
- }
-
- //两直线b值
- float b1 = (float)pt.m_y - (float)pt.m_x * k1;
- float b2 = (float)pt.m_y - (float)pt.m_x * k2;
-
- //做垂线
- int yStart = MIN(pt.m_y, pFlat1.m_y);
- int yEnd = MAX(pt.m_y, pFlat1.m_y);
- if (yStart < 0)yStart = 0;
- if (yEnd > m_height)yEnd = m_height - 1;
-
-
- for (int y = yStart; y <= yEnd; ++y) {
- int x1 = 0;
- //判断是否为直角三角形
- if (k1 == 0) {
- x1 = pFlat1.m_x;
- }
- else {
- x1 = ((float)y - b1) / k1;
- }
- //剪裁
- if (x1 < 0)x1 = 0;
- if (x1 > m_width)x1 = m_width - 1;
-
- int x2 = 0;
- //判断是否为直角三角形
- if (k2 == 0) {
- x2 = pFlat2.m_x;
- }
- else {
- x2 = ((float)y - b2) / k2;
- }
- //剪裁
- if (x2 < 0)x2 = 0;
- if (x2 > m_width)x2 = m_width - 1;
-
- //构建这两个点
- Point pt1(x1, y, RGBA(255, 0, 0));
- Point pt2(x2, y, RGBA(255, 0, 0));
-
- //绘制直线
- drawLine(pt1, pt2);
- }
- }
测试效果:

也可以设置为一个巨大的三角形,大于屏幕空间,其速度要由于不做剪裁的方法很多倍。
根据之前三角形画线的方法,确定两个点,这次是对两个点的RGBA值进行插值过渡。
- void Canvas::drawTriange(Point p1, Point p2, Point p3) {
- std::vector
pVec; - pVec.push_back(p1);
- pVec.push_back(p2);
- pVec.push_back(p3);
-
- //是否双方相交
- GT_RECT _rect(0, m_width, 0, m_height);
- while (1) {
- if (judgeInRect(p1, _rect) ||
- judgeInRect(p2, _rect) ||
- (judgeInRect(p3, _rect) ) ) {
- break;
- }
- Point rpt1(0, 0, RGBA());
- Point rpt2(0, m_width, RGBA());
- Point rpt3(0, m_height, RGBA());
- Point rpt4(m_width, m_height, RGBA());
- if (judgeInTriangle(rpt1,pVec) ||
- judgeInTriangle(rpt2,pVec) ||
- judgeInTriangle(rpt3,pVec) ||
- judgeInTriangle(rpt4,pVec)) {
- break;
- }
- return;
- }
-
-
- std::sort(pVec.begin(), pVec.end(), [](const Point& p1, const Point& p2) {
- return p1.m_y > p2.m_y;
- });
-
- //获取三个排序好的点
- Point ptMax = pVec[0];
- Point ptMid = pVec[1];
- Point ptMin = pVec[2];
-
- //判断是否为平顶平底三角形
- if (ptMax.m_y == ptMid.m_y) {
- drawTriangeFlat(ptMax, ptMid, ptMin);
- return;
- }
- if (ptMin.m_y == ptMid.m_y) {
- drawTriangeFlat(ptMin, ptMid, ptMax);
- return;
- }
-
- //计算直线参数k b
- float k = 0.0;
- if (ptMax.m_x != ptMin.m_x) {
- k = (float)(ptMax.m_y - ptMin.m_y) / (float)(ptMax.m_x - ptMin.m_x);
- }
- float b = (float)ptMax.m_y - (float)ptMax.m_x * k;
- Point newPoint(0, 0, RGBA(255, 0, 0));
- newPoint.m_y = ptMid.m_y;
- if (k == 0) {
- newPoint.m_x = ptMax.m_x;
- }
- else {
- newPoint.m_x = ((float)newPoint.m_y - b) / k;
- }
- float s = (float)(newPoint.m_y - ptMin.m_y) / (float)(ptMax.m_y - ptMin.m_y);
- newPoint.m_color = colorLerp(ptMin.m_color, ptMax.m_color, s);
-
-
- //分别绘制这两个平顶/平底三角形
- drawTriangeFlat(ptMid, newPoint, ptMax);
- drawTriangeFlat(ptMid, newPoint, ptMin);
-
- return;
- }
- void Canvas::drawTriangeFlat(Point pFlat1, Point pFlat2, Point pt){
- //两边直线斜率
- float k1 = 0.0;
- float k2 = 0.0;
-
- if (pFlat1.m_x != pt.m_x) {
- k1 = (float)(pFlat1.m_y - pt.m_y) / (float)(pFlat1.m_x - pt.m_x);
- }
- if (pFlat2.m_x != pt.m_x) {
- k2 = (float)(pFlat2.m_y - pt.m_y) / (float)(pFlat2.m_x - pt.m_x);
- }
-
- //两直线b值
- float b1 = (float)pt.m_y - (float)pt.m_x * k1;
- float b2 = (float)pt.m_y - (float)pt.m_x * k2;
-
- //做垂线
- int yStart = MIN(pt.m_y, pFlat1.m_y);
- int yEnd = MAX(pt.m_y, pFlat1.m_y);
- if (yStart < 0)yStart = 0;
- if (yEnd > m_height)yEnd = m_height - 1;
-
-
- //颜色插值相关
- RGBA colorStart1, colorEnd1;
- RGBA colorStart2, colorEnd2;
- if (pt.m_y < pFlat1.m_y) {
- yStart = pt.m_y;
- yEnd = pFlat1.m_y;
-
- colorStart1 = pt.m_color;
- colorEnd1 = pFlat1.m_color;
- colorStart2 = pt.m_color;
- colorEnd2 = pFlat2.m_color;
- }
- else {
- yStart = pFlat1.m_y;
- yEnd = pt.m_y;
-
- colorStart1 = pFlat1.m_color;
- colorEnd1 = pt.m_color;
- colorStart2 = pFlat2.m_color;
- colorEnd2 = pt.m_color;
- }
- float yColorStep = 1.0 / ((float)(yEnd - yStart));
- int yColorStart = yStart;
-
-
- for (int y = yStart; y <= yEnd; ++y) {
- int x1 = 0;
- //判断是否为直角三角形
- if (k1 == 0) {
- x1 = pFlat1.m_x;
- }
- else {
- x1 = ((float)y - b1) / k1;
- }
- //剪裁
- if (x1 < 0)x1 = 0;
- if (x1 > m_width)x1 = m_width - 1;
-
- int x2 = 0;
- //判断是否为直角三角形
- if (k2 == 0) {
- x2 = pFlat2.m_x;
- }
- else {
- x2 = ((float)y - b2) / k2;
- }
- //剪裁
- if (x2 < 0)x2 = 0;
- if (x2 > m_width)x2 = m_width - 1;
-
- //构建这两个点
- float s1 = (float)(y - yColorStart) * yColorStep;
- RGBA _color1 = colorLerp(colorStart1, colorEnd1, s1);
- RGBA _color2 = colorLerp(colorStart2, colorEnd2, s1);
- Point pt1(x1, y, _color1);
- Point pt2(x2, y, _color2);
-
- //绘制直线
- drawLine(pt1, pt2);
- }
- }
- void Render() {
- _canvas->clear();
-
- GT::Point p1(0, 0, GT::RGBA(255, 0, 0));
- GT::Point p2(500, 0, GT::RGBA(0, 255, 0));
- GT::Point p3(250, 200, GT::RGBA(0, 0, 255));
-
- _canvas->drawTriange(p1, p2, p3);
-
- //在这里画到设备上,hMem相当于缓冲区
- BitBlt(hDC, 0, 0, wWidth, wHeight, hMem, 0, 0, SRCCOPY);
- }