没有合适的资源?快使用搜索试试~ 我知道了~
一种基于边指针搜索及区域划分的三角剖分算法.docx
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 18 浏览量
2023-02-23
20:15:28
上传
评论
收藏 223KB DOCX 举报
温馨提示
试读
13页
一种基于边指针搜索及区域划分的三角剖分算法.docx
资源推荐
资源详情
资源评论
三维重建技术是根据物体的二维图像信息恢复其三维模型, 多年来一直是计算机图形
学领域的研究热点
[1-2]
.三角剖分是三维重建过程中最重要的基础之一, 通过将散点连接形成
许多互不相交的三角形或四面体, 从而使模型面化或者体化
[3]
.经过多年探索, 研究者们对于
二维三角剖分的研究已经取得了很多成果, 提出了多种三角网格的优化准则和构造方法.其
中, Delaunay 三角剖分由于具有良好的几何特性-可以最大化最小角
[4]
, 即能使得到的三角网
格最平均, 使用最广泛
[5]
.然而, 随着计算机图形学技术的发展, 扫描设备的精度越来越高,
用于三维重建的点集对象的规模也越来越大.因此, 在保证三角网格的整体质量的提前下,
有必要寻找一种更高效的 Delaunay 三角剖分, 从而满足三维重建的实时性.
Delaunay 三角剖分算法有很多种类, 主要分为三大类:逐点插入算法
[6]
、分治算法
[7]
、
三角网生长算法.其中, 逐点插入法由于实现相对简单且占用空间相对较小
[8]
, 被大量研究者
所采用; 分治算法在执行时间方面可以达到最优, 但占用内存较大, 不适用于一般的计算机
平台; 三角网生长算法相对于前两种算法效率较低, 不适用于大规模点集, 在实际应用中很
少被采用.逐点插入法的主要流程如下: 1)构造一个包含所有插入点的超级三角形; 2)将存储
在链表中的点按序插入, 遍历三角形链表找出包含插入点的三角形(即目标三角形), 利用插
入点将目标三角形拆分生成新的三角形, 在三角形链表中删除目标三角形, 完成一个点的插
入; 3)利用空圆特性对新生成的三角形进行 Delaunay 规则判断; 4)循环执行 2)和 3), 直至完
成对所有插入点的处理.经典的逐点插入法有 Bowyer 算法
[9]
、Watson 算法
[10]
以及 Lawson 算
法
[11]
等.
虽然逐点插入法易于实现, 但在处理大规模的散点集数据时, 实时性不是很好, 为了提
高逐点插入法的效率, 研究者们进行了大量的研究.一部分研究者认为可以对插入点进行预
处理, 通过改进插入点的序列来提高三角剖分的效率. Liu 等
[12]
提出了一种基于广度优先搜
索的确定性插入序列, 使用 k-d 树来构造 Delaunay 三角关系, 但是构造 k-d 较为复杂, 需耗
费大量时间.在多重网格插入法
[13]
的基础上, Su 等
[14]
提出了使用 Hilbert 曲线遍历插入点, 减
少了三角剖分过程中狭长三角形出现的数量, 从而降低局部优化时间. Zalik 等
[15]
提出一种
两级均匀细分加速技术, 将目标三角形问题转化为最近点问题, 在他们的方案中, 从最近的
Delaunay 点开始, 然后从第二个最近的 Delaunay 点开始, 以这种递归的方式直到找到目标
三角形.在此基础上, Zadravec 等
[16]
提出结合哈希表与跳跃表来寻找插入点的最近点, 从而快
速定位目标三角形.一些研究人员提出基于重心方向来定位目标三角形, 但是, 当出现分界
点时, 这种方法的搜索路径可能不唯一.针对此问题, Xi 等
[17]
提出可以通过移动重心来避免
截点, 从而使目标三角形可以连续搜索.随着计算机技术的快速发展, 许多研究者们提出了
并行 Delaunay 三角剖分, 将点集划分成许多独立的分区, 这些分区可以同时进行 Delaunay
三角剖分, Kohout 等
[18]
、Rong 等
[19]
、Cuong 等
[20]
、Lo
[21]
均对此进行了研究及改进.此外, 杨
昊禹等
[22]
提出了并行动态 Delaunay 三角剖分算法, 可以解决新增点位于原来三角网之外的
情况.另外李国庆等
[23]
提出了基于凸多边形的 Delaunay 三角剖分算法, 使用生成的凸多边形
代替传统算法中的超级三角形.常见的生成凸包算法有 Graham 扫描法
[24]
、分区算法
[25]
等.刘
斌等
[26]
提出将主成分分析法(PCA)与二分法结合, 通过快速确定凸包边缘点来计算平面点集
的凸包.
通过对 Delaunay 三角剖分逐点插入法的研究, 可知在构建三角网过程中最耗时的部分
为寻找插入点的目标三角形.本文在传统算法的基础上, 将边指针与区域划分相结合, 很大
程度上提高了构建 Delaunay 三角网的效率.
1. 基于边指针的搜索
在传统的逐点插入法中, 对每个插入点的目标三角形的搜索总是从三角形链表的表头
开始.这意味着, 目标三角形若位于链表的表头, 则可以很快被找到; 若位于链表的尾部, 则
需要遍历整个链表才能被找到.随着点的数量大幅度增加, 三角形链表的长度也必然会大幅
度增加, 从而导致寻找目标三角形会越来越耗时, 降低三角剖分的效率.针对此问题, 本文对
三角形的数据结构进行优化, 提出了基于边指针的数据结构.如图 1 所示, 在△ABC△ABC
中, AA 为起始顶点且 AA、BB、CC 逆时针分布, ACAC 为边 1, ABAB 为边 2, BCBC 为边 3.
在三条边上分别存在边指针 P1P1、P2P2、P3P3, 分别指向边指针所在的公共边的相邻三
角形, 如 P1P1 指向与边 ACAC 相邻的三角形, 对于 P2P2、P3P3 情况类似.
图 1 三角形数据结构
Fig. 1 Data structure of triangle
下载: 全尺寸图片 幻灯片
1.1 点与三角形的位置判断
点与三角形之间的位置关系可以根据其坐标的相对关系来判断.对于任意三个点
A(xA,yA)A(xA,yA), B(xB,yB)B(xB,yB), C(xC,yC)C(xC,yC), 其中
Flag(A,B,C)=(xB−xA)(yc−yB)−(xc−xB)(yB−yA)[27]Flag(A,B,C)=(xB−xA)(yc−yB)−(xc−xB)(yB−yA)[27]
(1)
若 Flag(A,B,C)>0Flag(A,B,C)>0, 则 AA、BB、CC 按逆时针方向分布; 若
Flag(A,B,C)<0Flag(A,B,C)<0, 则 AA、BB、CC 按顺时针方向分布; 若
Flag(A,B,C)=0Flag(A,B,C)=0, 则 AA、BB、CC 三点共线.如图 2 (a)所示, 若
Flag(C,A,M)Flag(C,A,M)、Flag(A,B,M)Flag(A,B,M)、Flag(B,C,M)Flag(B,C,M)三者的值都大
于零, 则点 MM 位于△ABC△ABC 的内部.若三者中一个值为零且其余二者皆为正值, 则位
于某条边上, 如图 2 (b)中 Flag(A,B,M)Flag(A,B,M)为零, Flag(C,A,M)Flag(C,A,M)、
Flag(B,C,M)Flag(B,C,M)为正值, 故点 MM 位于边 ABAB 上.若三者中至少有一个为负值, 则
点位于三角形的外部.如图 2 (c)所示, Flag(A,B,M)Flag(A,B,M)为负值, 故点 MM 位于边
ACAC 的外侧.当然, 点位于三角形外侧还会出现图 2 (d)与图 2 (e)的情况.在图 2 (d)
中, Flag(A,B,M)Flag(A,B,M)、Flag(B,C,M)Flag(B,C,M)皆为负值, 在此情况下, 由于 ABAB
为边 2, 而 BCBC 为边 3, 本文中优先取编号在前的边, 故认为 MM 位于边 ABAB 的外侧.在
图 2 (e)中, 点 MM 虽位于三角形外部且与边 ACAC 共线, 但是 Flag(B,C,M)Flag(B,C,M)为
负值, 故本文认为点 MM 位于边 BCBC 的外侧.
图 2 点与三角形位置关系判断
Fig. 2 Judgment of positional relationship between point and triangle
下载: 全尺寸图片 幻灯片
1.2 基于边指针搜索的路径确定
在搜索目标三角形的过程中, 搜索路径通过判断插入点与当前被搜索三角形的位置关
系来确定的.如图 3 所示, 点 VV 为插入点, 假设△AIJ△AIJ 存储在三角形链表的表头, 搜索
过程如下所述. 1)检测点 VV 与△AIJ△AIJ 的位置关系, 首先确定了点 VV 位于△AIJ△AIJ
的外部, 然后确定点 VV 位于△AIJ△AIJ 的哪条边的外侧, 根据式(1)可知点 VV 位于边 IJIJ
剩余12页未读,继续阅读
资源评论
罗伯特之技术屋
- 粉丝: 3663
- 资源: 1万+
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功