没有合适的资源?快使用搜索试试~ 我知道了~
+图形和视觉计算6(2022)200047技术部分预先计算的快速拒绝射线-三角形相交Thomas Alois Pichlera,Andrej Ferkob,Michal Ferkob,Peter Kána, Kaufmann a,Hannes Kaufmannaa视觉计算和以人为中心的技术研究所,TU Wien,奥地利维也纳b斯洛伐克布拉迪斯拉发夸美纽斯大学数学、物理和信息学院代数和几何系ar t i cl e i nf o文章历史记录:2021年6月30日收到收到修订版,2022年4月28日接受,2022年2022年5月10日网上发售保留字:射线-三角形相交射线射击碰撞点位置交点a b st ra ct提出了一种具有快速拒绝策略的光线-三角形求交算法。我们将射线与三角形平面相交,然后通过将变换矩阵应用于射线-平面交点,将相交问题转化为二维问题。对于2D变换,我们研究了两种不同的方法。第一种方法使用变换矩阵,将三角形变换为单位三角形。然后进行简单的2D测试。第二种方法将三角形转换为2D三角形,同时保持相似性。这允许我们修剪(即,剪切掉)三角形周围的区域,确定变换后的交点是否位于三角形内。我们讨论了这种修剪方法的几个优化。我们将这两种方法实现到基于CPU的光线跟踪框架PBRT版本3中,并且我们针对PBRT的默认相交算法以及Baldwin和Weber的算法执行基于时间的比较实验结果表明,我们的算法比默认算法有更快的速度.它们与Baldwin和Weber的算法相当或稍慢,然而,修剪方法产生水密的结果,并且可以进一步优化。此外,在PBRT之外的其他CPU/GPU实验证明,在光线投射或碰撞检测等领域,标准Möller-Trumbore算法的加速效果很有希望版权所有©2022作者。爱思唯尔有限公司出版这是CC BY许可下的开放获取文章(http://creativecommons.org/licenses/by/4.0/)中找到。1. 介绍射线-三角形相交计算属于图像合成和计算几何应用中最常见的基本任务,例如Goodman等人[1]报告了射线拍摄、碰撞、点定位、相交和手指探测中的问题。射线三角形相交的进一步应用是射线跟踪,包含测试,布尔运算,对象建模和物理模拟[2,3]。三角形被认为是计算机图形学和其他表示(NURBS,F-rep)中的标准图元.)通常在渲染之前进行三角测量。它们通常被视为建模器和渲染器的共同基础[4]的文件。三角形的简单性使得即使对于高性能应用也可以实现快速操作[2]。随后,在这些应用中多次计算射线三角形因此,使用快速有效的光线-三角形相交算法具有重要意义[4在本文中,我们研究了每个三角形的预处理,以加快计算时间的射线三角形相交在任何内存成本和确定RESIDENT情况下(无交集)在运行时,尽快。我们讨论了两种不同的早期拒绝测试方法,并与默认的这篇文章是由M推荐出版道根*通讯作者。电子邮件地址:ferko@fmph.uniba.sk(A. Ferko),peterkan@peterkan.com(P.Kán)。https://doi.org/10.1016/j.gvc.2022.200047射线跟踪框架PBRT 3 [8,9]的交叉算法以及Baldwin和Weber算法[7]。我们的两种方法都将相交问题转化为二维空间。我们的第一个方法将三角形转换成一个单位三角形,并提供重心坐标。第二种方法通过修剪三角形周围的区域预先计算这些区域被射线击中的概率,我们可以重新排序拒绝测试,以进一步加快相交过程。第二种方法产生了Woop等人的意义上的水密结果。的论文[9]。我们将水密性定义为相邻三角形之间没有间隙的三角形网格。相反,Baldwin和Weber进行了简化的第三边缘测试,即,计算重心坐标u和v,他们测试第三个三角形边是否与uv.根据Woop例如,这不会导致水密结果[9]。我们创建了一个混合算法,结合了单位三角形的方法和修剪方法。我们研究了八种不同的修剪变体,包括3倍和4倍修剪和修剪命中区域概率估计。我们的算法如图所示。1 .一、我们发现,我们的单位三角形方法比PBRT 3的默认算法[ 8,9 ]更快,修剪方法,一般来说,不快于单位三角形的方法,但产生水密的结果,可以进一步优化,并可能是有用的其他点在三角形的应用。2666-6294/©2022作者。 由Elsevier Ltd.发布。这是CC BY许可下的开放获取文章(http://creativecommons.org/licenses/by/4.0/)。可在ScienceDirect上获得目录列表图形与视觉计算期刊首页:www.elsevier.com/locate/gvcT.A. Pichler,A.Ferko,M.Ferko等人图形和视觉计算6(2022)2000472+ −−∈Fig. 1. 我们算法的概要。我们在3D中使用射线和三角形。我们计算光线平面交点P(如果存在)。 然后,我们使用一个变换来投影P,该变换将原始三角形映射到三角形(0,0),(1, 0),(0, 1),或映射到与原始三角形相似的三角形。最后,简单的拒绝2D测试确定P是否在三角形内我们对该领域的主要贡献是:使用早期拒绝测试研究了光线与平面相交到二维空间尝试不同的变体和优化的修剪方法将我们的算法与现实光线跟踪应用中的两种最先进的光线-三角形相交算法进行比较,其中一种方法(修剪方法)实现了水密结果,而第二种方法更快。2. 以前的工作由三个非共线点#A、B、C和具有原点O和归一化方向d的射线R(t)给出三角形AABC,欧几里得空间定义为:#»R(t)=O+t·d,(1)等人[9]报道了在该方法中顶点处有限的水密性。Woop等人进一步讨论了交叉口出租中的水密性。使用重心坐标u、v和w的算法如果针对u测试第三个三角形边,则无法提供严密的结果v,即如果w由1表示uv.当对网格中的相邻三角形再次测试同一条边时,这可能会导致不同的结果。Woop 等人指出,Dammertz和KellerWoop等人“的算法在边缘和顶点处是水密的,并且对于所有三角形配置都是鲁棒的[9]。Pharr 和汉弗莱 使用 Möller–Trumbore[10]在他们基于物理的光线跟踪框架PBRT,版本2 [16]中。它被Baldwin和Weber [7]认为是光线追踪的标准光线-三角形相交例程,并被Jiménez等人[2]认为是通用情况下的最快相交算法。然而,鲍德温和韦伯声称,‘‘under 他们储存了一种反式-其中t是实数,#»D =#»0。 我们过滤退化每个三角形内的形成矩阵,通过y坐标的零值来计算三角形,参见图2中的点P,而不计算这些三角形的共线性或零面积因此,输入的大小是15个实数(通常是32位浮点数)。在光线-三角形相交问题中,我们要确定光线是否错过了三角形或它们相交的位置(命中点、射线参数、重心)。先前已知的算法,例如,Möller和Trumbore [10],首先计算射线和三角形所在平面之间的交点,然后测试包含,返回射线参数t R和两个重心坐标u,v。他们的算法使用最少的存储,没有预处理,通常用作比较的参考。我们不打算最小化存储,而是通过严格分离预处理和运行时计算来最大化加速另一种方法是使用签名卷[4]在3D中解决问题。然而,在给定的配置 文 件 上 测 量 数 百 万 个 交 点 的 测 试 表 明 , Möller 和TrumboreAkenine-Möller的实时渲染门户网站上的交叉口调查第三种选择使用Plücker坐标, 即, Grass-mann代数术语[13]。Shevtsov等人报告了Plücker检验[14 ]第10段。但是,Woop三角形到顶点在(0, 0),(1, 0),(0, 1)上的2D单位三角形。Baldwin和Weber的方法通过构造变换矩阵,使其列之一是“自由向量”,仅由零和一个1组成,从而最大限度地减少了所需的存储以及射线变换的操作次数。他们将他们的算法集成到PBRT版本2中,将其与Möller-Trumbore算法进行比较在Baldwin和Weber利用变换矩阵对光线进行变换的同时,我们对光线与平面的交点进行变换。在PBRT第3版中,Pharr等人[8]使用与Woop等人[9]相同的算法,仅在术语和观察三角形边的方向上有所不同。我们将我们的算法实现到PBRT3中,以测试PBRT3算法Havel和Herout [5]描述了一种快速实现光线-三角形求交的方法,但它仅限于一个特殊的(SSE)指令集。对射线束内的某一给定射线,采用牛顿- 拉夫逊迭代法进行计算,提高了计算精度。Shevtsov等人[14]提出了另一种射线束相干GPU算法。一个用于x86CPU的开源光线跟踪框架是Embree [17],·····T.A. Pichler,A.Ferko,M.Ferko等人图形和视觉计算6(2022)2000473图三. 斯坦福兔子模型由35947个点和69451个三角形(左)组成。网格三角形分布使用三角形紧凑度等值线[21,22](右)显示图二. 三种三角形共用最长边l2-钝角(实线)、直角(虚线)和等边(虚线).灰色区域的点表示所有三角形。根据泰勒斯定理,CR半圆代表所有的直角三角形。灰色区域的两个非水平边界表示所有非退化等腰三角形。Guéziec3. 算法我们假设在一个给定的三维多边形场景网格三角形。为了有一个完整的定义,回想一下第2节中的以下陈述:设A、B、C是三个非共线点在3D欧几里德空间中,并且#>R是给定的射线(从原点O,方向d)。用P(xP,yP,zP)表示分配。可以针对多个平行三角形测试光线。在我们的研究中,我们没有研究射线束。早期退出的想法也可以在Bloo- menthal等人的工作中找到。[18]在三角形的适当投影后评估三个叉积的符号的成本。通过54个浮点运算,它们计算光线矢量和三角形边矢量之间的乘积‘‘If thesigns are not the same, then Áfra [19]使用AABB(包含整个三角形的轴对齐边界框)来快速拒绝和存储三角形。另一种提前终止策略关注射线参数t和重心坐标u,v。如果他们在外面在区间[t0,t1],[0,1],[0,1 -u]中,则候选被拒绝[20],p. 79。输出t,v, u是三角形着色所必需的,但并非所有应用领域都需要。我们计算交点坐标。根据泰勒斯定理,人们可以用上三角形的点来表示所有的直角三角形。 2)。通过将所有三角形的最长边映射到单位线段(0,0)(1,0),并将第三个点相应地映射到第一象限,可以对所有三角形进行相似性保持变换对于每个三角形,我们在预处理中存储这个变换矩阵MGrabner [22]将这种变换应用于三角形网格的另一个目的是可视化给定网格的三角形形状分布,如图3所示的Stanford Bunny数据集。“漂亮"网格最好由锐角或直角、非钝角三角形组成,如图所示。3.第三章。Shewchuk在一份未发表但经常被引用的手稿中深入讨论了三角形质量度量及其可视化的替代方案[24]。为了我们的目的,三角形相邻区域是相关的。假设点在平面上均匀分布,可以通过面积来近似射线命中概率。我们将在5.1节中讨论如何使用这样的概率来加速拒绝。 对于给定的网格,我们将三角形的表示组合为类似的2D三角形(如图1所示)。 2)用命中概率来调整测试顺序。R与给定平面的交点。我们形成了一个预处理的数据结构,并使用早期终止策略,如包围体测试和包围圈测试,并探索不同的,速度优化的配置,以实现真实的光线跟踪用例。我们在最高层次上对该方法的主要介绍可能包括以下4个步骤:1. 测试给定光线与三角形边界球的相交如果三角形没有交集,则丢弃该三角形。2. 计算光线平面交点。3. 根据三角形的AABB测试交点。如果交点不在AABB内,则丢弃三角形。4. 对交点应用2D变换并执行2D测试以确定该点是否位于三角形内。对于步骤4.,我们提出了两种不同的2D变换方法。第一种方法使用单位三角形变换器(UTM),其将三角形变换为单位三角形。然后,简单的2D测试确定交点是否位于单位三角形内。我们的第二 种 方 法 是 修 剪 的 方 法 , 它 使 用 了 相 似 性 保 持 变 换 矩 阵(SPTM)。在预处理过程中,我们构造了一个与原始3D三角形相似的2D三角形。在运行时,我们可以修剪2D三角形周围的区域,我们检查变换后的交点是否位于这些区域之一中,从而不位于三角形内。我们考虑了几种进行和优化修剪的方法。我们的测试表明,UTM方法通常更快,同时原生提供重心坐标,这可能是未来计算所需的然而,修剪方法在Woop等人的意义上提供了水密的结果。的论文[9],并可以通过估计面积命中概率,随后重新排序的算法步骤进一步优化。T.A. Pichler,A.Ferko,M.Ferko等人图形和视觉计算6(2022)2000474T=v2y−v 1yv 3y−v 1ybv 1y,(2)01=- -Xnx2#n»⎟1号线-·1nnnn⎟E2ZE2⎜⎝#»xy#»zy#»1yx和y值。⎛E2Z⎜#»⎞⎜3. 围绕y轴旋转三角形,4. 单位三角形法我们使用Baldwin和Weber他们注意到一个单位三角形可以用变换矩阵变换成任意三角形v1v2v3。v2x−v1xv3x−v1xav1xv2z−0v1zv3z−0v1zcv1z其中(a, b, c)是不影响变换的所谓自由向量。因此,可以以简化点的坐标与逆矩阵的稍后相乘的方式来选择a、b和c。Baldwin和Weber将其中一个自由向量元素设置为1,其他的设置为0。他们发现,三角形的法线的最高幅度分量作为自由向量le和s的非零分量n#>t,在数值上为m#>ore稳定的结果。 设E1为(v2设E2为(v3v1)。 n是三角形平面的法向量逆变换取决于选择自由向量的哪个分量作为非零分量。对于1,逆(这是我们的UTM)如下[7]:5. 修剪方法对 于 修 剪 方 法 , 我 们 使 用 了 一 个 相 似 性 保 持 变 换 矩 阵(SPTM),将3D三角形转换为2D空间,同时保持相似性。我们定义变换三角形的以下要求:1. 三角形的最低边将被映射到x轴上。设这条边是AB,A和B是它的顶点,A′和B′是变换后的点A和B。2. A′必须在(0,0)上,而B′必须在(1,0)上。3. 设C′为用SPTM变换后的第三个顶点C。C′必须被映射到2D坐标系的第一象限中,使得得到的三角形A′B′C′与ABC类似。4. C′必须位于三角形外切的右半边圈这个附加条件提高了修剪的效率,因为它扩大了左侧修剪区域,并且左侧修剪在计算上比右侧修剪便宜(参见不等式(10)和(11))。需要几个变换矩阵来构造SPTM。要像上面描述的那样变换三角形,需要采取以下步骤:#»0#n»#»#n»#»#»Ey(v3×v1)x#»x⎟#»#»z#n»v#»1. 平移三角形,使A在原点结束2. 围绕z轴旋转三角形,⎜0 −E1zE1y−(v2×v1)xB变为0。UTM=0#n»x#n»x#n»x.(三)n xn xnx⎠B变为0。0 0 0 1对于b=1,逆是4. 围绕x轴旋转三角形,C变为0。5. 按比例缩放三角形,使B−#»0#»x(v3×v1)y⎞−n⎟⎠T.A. Pichler,A.Ferko,M.Ferko等人图形和视觉计算6(2022)2000475变为1。#n»y#»E1z#n»y#»0−E1x#n»y-(v2×v1)yT.A. Pichler,A.Ferko,M.Ferko等人图形和视觉计算6(2022)20004766. 如果在这些步骤之后,C的y值 是负的,镜像T.A. Pichler,A.Ferko,M.Ferko等人图形和视觉计算6(2022)2000477X yyX绕x轴旋转 ,使其为正值. 所得UTM=0T.A. Pichler,A.Ferko,M.Ferko等人图形和视觉计算6(2022)20004782#»#»#»⎝#n»x位于三角形内的条件:⎛#»#»y#n»#n»y1#n»#n»y-#n»·v- 是的(四)顶点为A′=(0,0),B′T.A. Pichler,A.Ferko,M.Ferko等人图形和视觉计算6(2022)2000479=(1,0),且C′为正T.A. Pichler,A.Ferko,M.Ferko等人图形和视觉计算6(2022)20004710#»n1−·1⎟0 0 0 1对于c=1,逆是T.A. Pichler,A.Ferko,M.Ferko等人图形和视觉计算6(2022)20004711这些步骤对于功能相似性保持是足够的T.A. Pichler,A.Ferko,M.Ferko等人图形和视觉计算6(2022)20004712转型然而,如前所述,另一个步骤可以是T.A. Pichler,A.Ferko,M.Ferko等人图形和视觉计算6(2022)20004713以提高后期修剪的效果如果C'说谎#»#»Ey−E2x0(v3×v1)z⎞在三角形外接圆的左半部分如果X-′n#»zn zn zT.A. Pichler,A.Ferko,M.Ferko等人图形和视觉计算6(2022)20004714C值小于0.5时,C′可绕直线镜像−E1yT.A. Pichler,A.Ferko,M.Ferko等人图形和视觉计算6(2022)20004715#»E1x0−(v2×v1)zx= 0。5. 这将C′移到右半边,同时仍保持T.A. Pichler,A.Ferko,M.Ferko等人图形和视觉计算6(2022)20004716UTM=0nz#n»z#n»z#»y#n»znz#n»v#n»z.(五)T.A. Pichler,A.Ferko,M.Ferko等人图形和视觉计算6(2022)20004717⎟⎠相似性,这增加了左撇子的概率,测试将检测到非命中。注意,C的转换T.A. Pichler,A.Ferko,M.Ferko等人图形和视觉计算6(2022)200047180 0 0 1仅存储UTM的前两行就足够了T.A. Pichler,A.Ferko,M.Ferko等人图形和视觉计算6(2022)20004719因为只有x和y坐标是测试所需要的,转型而不是存储自由向量,我们只存储T.A. Pichler,A.Ferko,M.Ferko等人图形和视觉计算6(2022)20004720具有自由向量的列的索引,如Baldwin和Weber [7].
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- zigbee-cluster-library-specification
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功