有效边表填充算法

2024-01-03 06:42:53

有效边表填充算法

如何填充示例三角形

在这里插入图片描述
在这里插入图片描述

按照扫描线从上往下的顺序，依次处理和多边形相交的扫描线，对于当前处理的扫描线找到和它相交的所有边的交点，按照交点横坐标从小到大的顺序，两个两个配对，配对之后填充每对交点之间的像素，所有的扫描线处理完成之后，图形的扫描就结束了。在算法中主要学习三种数据结构

  1. 边表
  2. 有效边表
  3. 桶表
边表

在这里插入图片描述

在这里插入图片描述

有效边表

三角形与当前扫描线相交的边称为有效边。在处理一条扫描线时仅对有效边进行求教运算，可以避免与多边形的所有边求交。扫描线由有效的低端 ( y = y m i n ) (y = y_{min}) (y=ymin?) 向高端 y = y m a x y=y_{max} y=ymax? 运动，交点的 y y y 坐标每次相加 1.

这个图事实上就是 DDA 算法中的 y y y 为主轴位移的方向，执行 y = y + 1 y = y +1 y=y+1， x = x + 1 k x = x + \frac{1}{k} x=x+k1?

在这里插入图片描述

桶表

桶表是一个纵向扫描线链表，链表的长度为多边形所覆盖的最大扫描线数，链表的每个节点称为桶，链接边表。

在这里插入图片描述

算法

  1. 建立桶表
  2. 在桶节点上建立边表
  3. 按照扫描线由从小到大的顺序循环访问每个桶节点，计算扫描线与边的交点建立有效边表
  4. 从有效边表中取出扫描线上相邻两条边的交点，进行配对并填充
  5. 循环下一桶结点，并修改有效边表
  6. 如果桶结点的扫描线的值大于等于有效边表中某个结点的 y m a x y_max ym?ax 值，则该边成为无效边
  7. 当桶结点不为空则转 4，否则算法结束

结论

  • 有效边表算法通过维护边表与有效边表，避开了扫描线与多边形所有边求交的复杂运算。已经称为最常用的多边形扫描转换算法之一。
  • 有效边表算法的特点是可以直接填充四边形，而无需将四边形细分为两个三角形
  • 通过顶点颜色沿着边和扫描线两个方向的线性插值，可以绘制颜色渐变的多边形
  • 有效边表算法可以填充凸多边形，凹多边形和环。
    代码实现下一篇

文章来源:https://blog.csdn.net/weixin_43862398/article/details/135351695
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。