• C++模拟OpenGL库——图形光栅化理论及实现(三):三角形绘制


    目录

    判断点是否在三角形内

    实现:区域扫描-遍历包围盒

    优化1:平顶平底三角形扫描

    实现:平底/平顶三角形绘制

    实现:任意(非平顶/平底)三角形绘制

    优化2:若三角形是否在屏幕范围内or屏幕是否在一个巨大的三角形内

    优化3:对优化2中的情况进行剪裁

    实现:绘制彩色三角形


    判断点是否在三角形内

    如何判断一个点在三角形中?

    判断点p与pi是否在ei的同一侧

    比如,看p点和p2这两个点。

    判断此时p的x值,再计算此x值在e2边上的y值。

    我们就知道了:p点的y值,和e2上的y值。

    如果这p点y值和p2点y值都小于e2上的y值,则说明p和p2点在e2的同一侧。

    其他两个点同理。都需要两两在对边的同一侧,即p点在三角形的同一侧,即在三角形内部。

    实现:区域扫描-遍历包围盒

    根据这个原理,来实现函数:

     

    最直观的想法:遍历所有像素,判断点是否在三角形中,如果在则绘制。

    但是太浪费了,做一个包围盒优化:

    这样只需遍历包围盒即可,不用遍历整个屏幕

    1. void Canvas::drawTriange(Point p1, Point p2, Point p3){
    2. RGBA _color(255, 0, 0);
    3. //构建包围盒
    4. int left = MIN(p3.m_x, MIN(p1.m_x, p2.m_x));
    5. int top = MIN(p3.m_y, MIN(p1.m_y, p2.m_y));
    6. int right = MAX(p3.m_x, MAX(p1.m_x, p2.m_x));
    7. int bottom = MAX(p3.m_y, MAX(p1.m_y, p2.m_y));
    8. //裁剪屏幕
    9. left = left < 0 ? 0 : left;
    10. top = top < 0 ? 0 : top;
    11. right = right > (m_width - 1) ? m_width - 1 : right;
    12. bottom = bottom > (m_height - 1) ? m_height - 1 : bottom;
    13. //计算直线参数值
    14. float k1 = (float)(p2.m_y - p3.m_y) / (float)(p2.m_x - p3.m_x);
    15. float k2 = (float)(p1.m_y - p3.m_y) / (float)(p1.m_x - p3.m_x);
    16. float k3 = (float)(p2.m_y - p1.m_y) / (float)(p2.m_x - p1.m_x);
    17. //计算直线的b值
    18. float b1 = (float)p2.m_y - k1 * (float)p2.m_x;
    19. float b2 = (float)p3.m_y - k2 * (float)p3.m_x;
    20. float b3 = (float)p1.m_y - k3 * (float)p1.m_x;
    21. //循环判断
    22. for (int x = left; x <= right; x++) {
    23. for (int y = top; y <= bottom; y++) {
    24. //判断是否在当前点是否在三角形内
    25. float judge1 = (y - (k1 * x + b1)) * (p1.m_y - (k1 * p1.m_x + b1));
    26. float judge2 = (y - (k2 * x + b2)) * (p2.m_y - (k2 * p2.m_x + b2));
    27. float judge3 = (y - (k3 * x + b3)) * (p3.m_y - (k3 * p3.m_x + b3));
    28. if (judge1 >= 0 && judge2 >= 0 && judge3 >= 0) {
    29. drawPoint(x, y, _color);
    30. }
    31. }
    32. }
    33. }
    1. void Render() {
    2. _canvas->clear();
    3. GT::Point p1(0, 0, GT::RGBA(255, 0, 0));
    4. GT::Point p2(100, 50, GT::RGBA(255, 0, 0));
    5. GT::Point p3(150, 200, GT::RGBA(255, 0, 0));
    6. _canvas->drawTriange(p1, p2, p3);
    7. //在这里画到设备上,hMem相当于缓冲区
    8. BitBlt(hDC, 0, 0, wWidth, wHeight, hMem, 0, 0, SRCCOPY);
    9. }

    优化1:平顶平底三角形扫描

    直白来讲,就是将三角形分为若干个平顶/平底三角形

    平顶/平底三角形绘制则可以通过之前的Brensenhem直线绘制来实现:

    • 找到平顶/平底三角形的”中间点“(比如上图pt),做一条垂直x轴的垂线
    • 这样就知道了两条边的y值,根据直线方程即可知道两条边对应的x值
    • 知道两个x值(x1,x2)就可以画出一条直线,从顶点一直画到底,即可扫描填充三角形

    最后,需要考虑直角三角形,需要特殊判断点的x坐标。

    实现:平底/平顶三角形绘制

    1. void Canvas::drawTriangeFlat(Point pFlat1, Point pFlat2, Point pt){
    2. //两边直线斜率
    3. float k1 = 0.0;
    4. float k2 = 0.0;
    5. if (pFlat1.m_x != pt.m_x) {
    6. k1 = (float)(pFlat1.m_y - pt.m_y) / (float)(pFlat1.m_x - pt.m_x);
    7. }
    8. if (pFlat2.m_x != pt.m_x) {
    9. k2 = (float)(pFlat2.m_y - pt.m_y) / (float)(pFlat2.m_x - pt.m_x);
    10. }
    11. //两直线b值
    12. float b1 = (float)pt.m_y - (float)pt.m_x * k1;
    13. float b2 = (float)pt.m_y - (float)pt.m_x * k2;
    14. //做垂线
    15. int yStart = MIN(pt.m_y, pFlat1.m_y);
    16. int yEnd = MAX(pt.m_y, pFlat1.m_y);
    17. for (int y = yStart; y <= yEnd; ++y) {
    18. int x1 = 0;
    19. //判断是否为直角三角形
    20. if (k1 == 0) {
    21. x1 = pFlat1.m_x;
    22. }
    23. else {
    24. x1 = ((float)y - b1) / k1;
    25. }
    26. int x2 = 0;
    27. //判断是否为直角三角形
    28. if (k2 == 0) {
    29. x2 = pFlat2.m_x;
    30. }
    31. else {
    32. x2 = ((float)y - b2) / k2;
    33. }
    34. //构建这两个点
    35. Point pt1(x1, y, RGBA(255, 0, 0));
    36. Point pt2(x2, y, RGBA(255, 0, 0));
    37. //绘制直线
    38. drawLine(pt1, pt2);
    39. }
    40. }
    1. void Render() {
    2. _canvas->clear();
    3. GT::Point p1(100, 100, GT::RGBA(255, 0, 0));
    4. GT::Point p2(200, 100, GT::RGBA(255, 0, 0));
    5. GT::Point p3(150, 150, GT::RGBA(255, 0, 0));
    6. _canvas->drawTriangeFlat(p1, p2, p3);
    7. //在这里画到设备上,hMem相当于缓冲区
    8. BitBlt(hDC, 0, 0, wWidth, wHeight, hMem, 0, 0, SRCCOPY);
    9. }

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

    实现:任意(非平顶/平底)三角形绘制

    先给三个点按y值排序,然后分上下两个平顶/平底三角形

    1. void Canvas::drawTriange(Point p1, Point p2, Point p3) {
    2. std::vectorpVec;
    3. pVec.push_back(p1);
    4. pVec.push_back(p2);
    5. pVec.push_back(p3);
    6. std::sort(pVec.begin(), pVec.end(), [](const Point& p1, const Point& p2) {
    7. return p1.m_y > p2.m_y;
    8. });
    9. //获取三个排序好的点
    10. Point ptMax = pVec[0];
    11. Point ptMid = pVec[1];
    12. Point ptMin = pVec[2];
    13. //判断是否为平顶平底三角形
    14. if (ptMax.m_y == ptMid.m_y) {
    15. drawTriangeFlat(ptMax, ptMid, ptMin);
    16. return;
    17. }
    18. if (ptMin.m_y == ptMid.m_y) {
    19. drawTriangeFlat(ptMin, ptMid, ptMax);
    20. return;
    21. }
    22. //计算直线参数k b
    23. float k = 0.0;
    24. if (ptMax.m_x != ptMin.m_x) {
    25. k = (float)(ptMax.m_y - ptMin.m_y) / (float)(ptMax.m_x - ptMin.m_x);
    26. }
    27. float b = (float)ptMax.m_y - (float)ptMax.m_x * k;
    28. Point newPoint(0, 0, RGBA(255, 0, 0));
    29. newPoint.m_y = ptMid.m_y;
    30. if (k == 0) {
    31. newPoint.m_x = ptMax.m_x;
    32. }
    33. else {
    34. newPoint.m_x = ((float)newPoint.m_y - b) / k;
    35. }
    36. //分别绘制这两个平顶/平底三角形
    37. drawTriangeFlat(ptMid, newPoint, ptMax);
    38. drawTriangeFlat(ptMid, newPoint, ptMin);
    39. return;
    40. }
    1. void Render() {
    2. _canvas->clear();
    3. GT::Point p1(700, 500, GT::RGBA(255, 0, 0));
    4. GT::Point p2(200, 100, GT::RGBA(255, 0, 0));
    5. GT::Point p3(150, 150, GT::RGBA(255, 0, 0));
    6. _canvas->drawTriange(p1, p2, p3);
    7. //在这里画到设备上,hMem相当于缓冲区
    8. BitBlt(hDC, 0, 0, wWidth, wHeight, hMem, 0, 0, SRCCOPY);
    9. }

    优化2:若三角形是否在屏幕范围内or屏幕是否在一个巨大的三角形内

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

    判断:

    • 三角形的点是否在矩形内
    • 矩形的点是否在三角形内

    实现如下:

    1. bool Canvas::judgeInTriangle(Point pt, std::vector _ptArray){
    2. Point pt1 = _ptArray[0];
    3. Point pt2 = _ptArray[1];
    4. Point pt3 = _ptArray[2];
    5. int x = pt.m_x;
    6. int y = pt.m_y;
    7. //三个k
    8. float k1 = (float)(pt1.m_y - pt2.m_y) / (float)(pt1.m_x - pt2.m_x);
    9. float k2 = (float)(pt1.m_y - pt3.m_y) / (float)(pt1.m_x - pt3.m_x);
    10. float k3 = (float)(pt3.m_y - pt2.m_y) / (float)(pt3.m_x - pt2.m_x);
    11. //三个b
    12. float b1 = (float)pt1.m_y - k1 * pt1.m_x;
    13. float b2 = (float)pt3.m_y - k2 * pt3.m_x;
    14. float b3 = (float)pt2.m_y - k3 * pt2.m_x;
    15. //是否在三角形内
    16. float judge1 = (y - (k1 * x + b1)) * (pt3.m_y - (k1 * pt3.m_x + b1));
    17. float judge2 = (y - (k2 * x + b2)) * (pt2.m_y - (k2 * pt2.m_x + b2));
    18. float judge3 = (y - (k3 * x + b3)) * (pt1.m_y - (k3 * pt1.m_x + b3));
    19. if (judge1 > 0 && judge2 > 0 && judge3 > 0)
    20. {
    21. return true;
    22. }
    23. return false;
    24. }
    25. void Canvas::drawTriange(Point p1, Point p2, Point p3) {
    26. std::vectorpVec;
    27. pVec.push_back(p1);
    28. pVec.push_back(p2);
    29. pVec.push_back(p3);
    30. std::sort(pVec.begin(), pVec.end(), [](const Point& p1, const Point& p2) {
    31. return p1.m_y > p2.m_y;
    32. });
    33. //获取三个排序好的点
    34. Point ptMax = pVec[0];
    35. Point ptMid = pVec[1];
    36. Point ptMin = pVec[2];
    37. //判断是否为平顶平底三角形
    38. if (ptMax.m_y == ptMid.m_y) {
    39. drawTriangeFlat(ptMax, ptMid, ptMin);
    40. return;
    41. }
    42. if (ptMin.m_y == ptMid.m_y) {
    43. drawTriangeFlat(ptMin, ptMid, ptMax);
    44. return;
    45. }
    46. //计算直线参数k b
    47. float k = 0.0;
    48. if (ptMax.m_x != ptMin.m_x) {
    49. k = (float)(ptMax.m_y - ptMin.m_y) / (float)(ptMax.m_x - ptMin.m_x);
    50. }
    51. float b = (float)ptMax.m_y - (float)ptMax.m_x * k;
    52. Point newPoint(0, 0, RGBA(255, 0, 0));
    53. newPoint.m_y = ptMid.m_y;
    54. if (k == 0) {
    55. newPoint.m_x = ptMax.m_x;
    56. }
    57. else {
    58. newPoint.m_x = ((float)newPoint.m_y - b) / k;
    59. }
    60. //分别绘制这两个平顶/平底三角形
    61. drawTriangeFlat(ptMid, newPoint, ptMax);
    62. drawTriangeFlat(ptMid, newPoint, ptMin);
    63. return;
    64. }

    优化3:对优化2中的情况进行剪裁

    在Canvas::drawTriangeFlat中进行剪裁:

    1. void Canvas::drawTriangeFlat(Point pFlat1, Point pFlat2, Point pt){
    2. //两边直线斜率
    3. float k1 = 0.0;
    4. float k2 = 0.0;
    5. if (pFlat1.m_x != pt.m_x) {
    6. k1 = (float)(pFlat1.m_y - pt.m_y) / (float)(pFlat1.m_x - pt.m_x);
    7. }
    8. if (pFlat2.m_x != pt.m_x) {
    9. k2 = (float)(pFlat2.m_y - pt.m_y) / (float)(pFlat2.m_x - pt.m_x);
    10. }
    11. //两直线b值
    12. float b1 = (float)pt.m_y - (float)pt.m_x * k1;
    13. float b2 = (float)pt.m_y - (float)pt.m_x * k2;
    14. //做垂线
    15. int yStart = MIN(pt.m_y, pFlat1.m_y);
    16. int yEnd = MAX(pt.m_y, pFlat1.m_y);
    17. if (yStart < 0)yStart = 0;
    18. if (yEnd > m_height)yEnd = m_height - 1;
    19. for (int y = yStart; y <= yEnd; ++y) {
    20. int x1 = 0;
    21. //判断是否为直角三角形
    22. if (k1 == 0) {
    23. x1 = pFlat1.m_x;
    24. }
    25. else {
    26. x1 = ((float)y - b1) / k1;
    27. }
    28. //剪裁
    29. if (x1 < 0)x1 = 0;
    30. if (x1 > m_width)x1 = m_width - 1;
    31. int x2 = 0;
    32. //判断是否为直角三角形
    33. if (k2 == 0) {
    34. x2 = pFlat2.m_x;
    35. }
    36. else {
    37. x2 = ((float)y - b2) / k2;
    38. }
    39. //剪裁
    40. if (x2 < 0)x2 = 0;
    41. if (x2 > m_width)x2 = m_width - 1;
    42. //构建这两个点
    43. Point pt1(x1, y, RGBA(255, 0, 0));
    44. Point pt2(x2, y, RGBA(255, 0, 0));
    45. //绘制直线
    46. drawLine(pt1, pt2);
    47. }
    48. }

    测试效果:

     也可以设置为一个巨大的三角形,大于屏幕空间,其速度要由于不做剪裁的方法很多倍。

    实现:绘制彩色三角形

    根据之前三角形画线的方法,确定两个点,这次是对两个点的RGBA值进行插值过渡。

    1. void Canvas::drawTriange(Point p1, Point p2, Point p3) {
    2. std::vectorpVec;
    3. pVec.push_back(p1);
    4. pVec.push_back(p2);
    5. pVec.push_back(p3);
    6. //是否双方相交
    7. GT_RECT _rect(0, m_width, 0, m_height);
    8. while (1) {
    9. if (judgeInRect(p1, _rect) ||
    10. judgeInRect(p2, _rect) ||
    11. (judgeInRect(p3, _rect) ) ) {
    12. break;
    13. }
    14. Point rpt1(0, 0, RGBA());
    15. Point rpt2(0, m_width, RGBA());
    16. Point rpt3(0, m_height, RGBA());
    17. Point rpt4(m_width, m_height, RGBA());
    18. if (judgeInTriangle(rpt1,pVec) ||
    19. judgeInTriangle(rpt2,pVec) ||
    20. judgeInTriangle(rpt3,pVec) ||
    21. judgeInTriangle(rpt4,pVec)) {
    22. break;
    23. }
    24. return;
    25. }
    26. std::sort(pVec.begin(), pVec.end(), [](const Point& p1, const Point& p2) {
    27. return p1.m_y > p2.m_y;
    28. });
    29. //获取三个排序好的点
    30. Point ptMax = pVec[0];
    31. Point ptMid = pVec[1];
    32. Point ptMin = pVec[2];
    33. //判断是否为平顶平底三角形
    34. if (ptMax.m_y == ptMid.m_y) {
    35. drawTriangeFlat(ptMax, ptMid, ptMin);
    36. return;
    37. }
    38. if (ptMin.m_y == ptMid.m_y) {
    39. drawTriangeFlat(ptMin, ptMid, ptMax);
    40. return;
    41. }
    42. //计算直线参数k b
    43. float k = 0.0;
    44. if (ptMax.m_x != ptMin.m_x) {
    45. k = (float)(ptMax.m_y - ptMin.m_y) / (float)(ptMax.m_x - ptMin.m_x);
    46. }
    47. float b = (float)ptMax.m_y - (float)ptMax.m_x * k;
    48. Point newPoint(0, 0, RGBA(255, 0, 0));
    49. newPoint.m_y = ptMid.m_y;
    50. if (k == 0) {
    51. newPoint.m_x = ptMax.m_x;
    52. }
    53. else {
    54. newPoint.m_x = ((float)newPoint.m_y - b) / k;
    55. }
    56. float s = (float)(newPoint.m_y - ptMin.m_y) / (float)(ptMax.m_y - ptMin.m_y);
    57. newPoint.m_color = colorLerp(ptMin.m_color, ptMax.m_color, s);
    58. //分别绘制这两个平顶/平底三角形
    59. drawTriangeFlat(ptMid, newPoint, ptMax);
    60. drawTriangeFlat(ptMid, newPoint, ptMin);
    61. return;
    62. }
    1. void Canvas::drawTriangeFlat(Point pFlat1, Point pFlat2, Point pt){
    2. //两边直线斜率
    3. float k1 = 0.0;
    4. float k2 = 0.0;
    5. if (pFlat1.m_x != pt.m_x) {
    6. k1 = (float)(pFlat1.m_y - pt.m_y) / (float)(pFlat1.m_x - pt.m_x);
    7. }
    8. if (pFlat2.m_x != pt.m_x) {
    9. k2 = (float)(pFlat2.m_y - pt.m_y) / (float)(pFlat2.m_x - pt.m_x);
    10. }
    11. //两直线b值
    12. float b1 = (float)pt.m_y - (float)pt.m_x * k1;
    13. float b2 = (float)pt.m_y - (float)pt.m_x * k2;
    14. //做垂线
    15. int yStart = MIN(pt.m_y, pFlat1.m_y);
    16. int yEnd = MAX(pt.m_y, pFlat1.m_y);
    17. if (yStart < 0)yStart = 0;
    18. if (yEnd > m_height)yEnd = m_height - 1;
    19. //颜色插值相关
    20. RGBA colorStart1, colorEnd1;
    21. RGBA colorStart2, colorEnd2;
    22. if (pt.m_y < pFlat1.m_y) {
    23. yStart = pt.m_y;
    24. yEnd = pFlat1.m_y;
    25. colorStart1 = pt.m_color;
    26. colorEnd1 = pFlat1.m_color;
    27. colorStart2 = pt.m_color;
    28. colorEnd2 = pFlat2.m_color;
    29. }
    30. else {
    31. yStart = pFlat1.m_y;
    32. yEnd = pt.m_y;
    33. colorStart1 = pFlat1.m_color;
    34. colorEnd1 = pt.m_color;
    35. colorStart2 = pFlat2.m_color;
    36. colorEnd2 = pt.m_color;
    37. }
    38. float yColorStep = 1.0 / ((float)(yEnd - yStart));
    39. int yColorStart = yStart;
    40. for (int y = yStart; y <= yEnd; ++y) {
    41. int x1 = 0;
    42. //判断是否为直角三角形
    43. if (k1 == 0) {
    44. x1 = pFlat1.m_x;
    45. }
    46. else {
    47. x1 = ((float)y - b1) / k1;
    48. }
    49. //剪裁
    50. if (x1 < 0)x1 = 0;
    51. if (x1 > m_width)x1 = m_width - 1;
    52. int x2 = 0;
    53. //判断是否为直角三角形
    54. if (k2 == 0) {
    55. x2 = pFlat2.m_x;
    56. }
    57. else {
    58. x2 = ((float)y - b2) / k2;
    59. }
    60. //剪裁
    61. if (x2 < 0)x2 = 0;
    62. if (x2 > m_width)x2 = m_width - 1;
    63. //构建这两个点
    64. float s1 = (float)(y - yColorStart) * yColorStep;
    65. RGBA _color1 = colorLerp(colorStart1, colorEnd1, s1);
    66. RGBA _color2 = colorLerp(colorStart2, colorEnd2, s1);
    67. Point pt1(x1, y, _color1);
    68. Point pt2(x2, y, _color2);
    69. //绘制直线
    70. drawLine(pt1, pt2);
    71. }
    72. }
    1. void Render() {
    2. _canvas->clear();
    3. GT::Point p1(0, 0, GT::RGBA(255, 0, 0));
    4. GT::Point p2(500, 0, GT::RGBA(0, 255, 0));
    5. GT::Point p3(250, 200, GT::RGBA(0, 0, 255));
    6. _canvas->drawTriange(p1, p2, p3);
    7. //在这里画到设备上,hMem相当于缓冲区
    8. BitBlt(hDC, 0, 0, wWidth, wHeight, hMem, 0, 0, SRCCOPY);
    9. }

  • 相关阅读:
    嵌入式系统开发中的DevOps自动化: 工具、益处和挑战
    LoadRunner负载机和IP欺骗
    Netty 学习(十):ChannelPipeline源码说明
    黑客技术(网络安全)——自学思路
    FreeRTOS教程5 信号量
    Jetson AGX Orin R34.1.1 源码环境搭建 & SDKmanager刷机
    Python游戏开发实战:飞机大战(含代码)
    关于网络协议的若干问题(二)
    电流互感器绝缘电阻测试
    数字化转型将为企业带来什么样的变革?
  • 原文地址:https://blog.csdn.net/Jason6620/article/details/127837547