4. 三角形

浏览量:31

参考

    Tomas Möller, and Ben Trumbore. "Fast, minimum storage ray-triangle intersection." Journal of graphics tools, vol.2, no.1, pp.21-28, 1997.     Philip J. Schneider, and David H. Eberly. Geometric Tools for Computer Graphics. Morgan Kaufmann, 2002.     Tomas Möller. "A fast

spacer
浏览量:549

4.4. 三角形与三角形的重叠检测

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。 PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry 4.4. 三角形与三角形的重叠检测 问题描述:在三维空间上,有两个三角形\({T_1}:\Delta V_0^1V_1^1V_2^1\)和\({T_2}:\Delta V_0^2V_1^2V_2^2\),分别位于平面\({\pi _1}\)和\({\pi _2}\)上,判断这两个三角形是否重叠。 图4.12 三角形和它所在的平面 至少有六种算法可以用于判定三角形与三角形是否相交。第一种算法,也是最朴素的算法,速度最慢。第二种算法,由Möller et al(1997)提出了一种更加高效的算法,算法是基本思路是:若两个三角形相交,那么它们所在的平面必相交于一条直线,两个三角形分别在该直线上产生间隔,如图4.12所示,若间隔重叠,则两个三角形相交,否则,不相交,因此该方法也称为间隔重叠法。第三种算法,Guigue& Devillers (2003)对间隔重叠法进行改进,通过采用行列式的计算,来判断两个三角形是否相交,有效的避免的除法操作,由于不用求解实际的间隔值,浮点数的误差相对较小,因此也比第二种算法更稳定。第四种算法,Held(1997)实现了一个名为ERIT的软件包,用于三维空间的相交测试,ERIT包括了一种三角形与三角形相交测试的算法,该方法的算法比第一种算法高效,由于需要求交点操作,必需包括一些必要的除法运算,再根据求出的交点进行后续的判断,浮点数的精度误差更大,因此稳定性上也不如第二种和第三种算法。此外,Shen et al(2003)提出了一种通过计算线与线之间有向距离的方法,来判定两个三角形是否相交,还可以采用分离轴的方法实现相交测试。下面将分别介绍前四种算法的思想和实现方法。 4.4.1. 朴素算法 首先,判断三角形\({T_1}\)的每一条边,是否与三角形\({T_2}\)相交,若至少存在一条这样的边,说明两个三角形相交;接着,判断三角形\({T_2}\)的每一条边,是否与三角形\({T_1}\)相交。最坏情况下,需要做6次线段与三角形的相交测试,这是最容易想到的一种算法,也是最暴力的算法。 4.4.2. 间隔重叠法 Möller(1997)提出了通过判断两个三角形在相交直线上是否重叠的方法来实现两个三角形的重叠检测。设平面\({\pi _2}\)的参数方程表示为\({{\vec{d}}_{2}}\cdot X+{{D}_{2}}=0\),\(X\)是平面上的点,由三角形初始化一个平面,即\({{\vec{d}}_{2}}=(V_{1}^{2}-V_{0}^{2})\times (V_{2}^{2}-V_{0}^{2}),{{D}_{2}}=-{{\vec{d}}_{2}}\cdot V_{0}^{2}\)。 三角形\({{T}_{1}}\)上的顶点到到平面\({{\pi }_{2}}\)的有符号距离用如下等式表示,由于这里只需要判断有符号距离的符号,所以可以不需要除法\(\left\| {{{\vec{d}}}_{2}} \right\|\): \({{d}_{V_{i}^{1}}}={{\vec{d}}_{2}}\cdot V_{i}^{1}+{{D}_{2}},i=0,1,2 \tag{4.23}\) 现在,如果对于所有的\(i=0,1,2\),\({{d}_{V_{i}^{1}}}\ne 0\)(说明没有顶点在平面上),同时所有的值均具有相同的符号,那么\({{T}_{1}}\)的三个顶点都位于平面的同一侧。这样,就可以排除重叠的可能性。对于三角形\({{T}_{2}}\)和平面\({{\pi }_{1}}\),也需要这样的测试,测试过程也是相同的。这两步测试,可以避免很多不必要的计算,如果通过了这两个测试,说明两个平面必相交,两个平面相交于一条直线,即\({{\vec{d}}_{1}}\times {{\vec{d}}_{2}}\)一定存在。 如果对于所有的\(i=0,1,2,{{d}_{V_{i}^{1}}}=0\),说明两个三角形在同一个平面上,这种情况在后面会单独讨论。如果不是都为零的情况,设两个平面相交的直线的参数方程是\(L=O+t\vec{d}\),其中\(\vec{d}={{\vec{d}}_{1}}\times

spacer
浏览量:59

4.3. 线性对象与三角形的交

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。 PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry 4.3. 线性对象与三角形的交 问题描述:在三维空间上,判断线性对象\(P + t\vec d\)与三角形\(\Delta {V_0}{V_1}{V_2}\)是否相交,若相交,求出交点,三角形所在的平面是\(\pi \)。 图4.11 直线与三角形的四种关系 三维空间的模型通常是由一个个三角形面片构成的,线性对象与三角形的相交检测也显得特别的重要。如图4.11所示,一条直线与三角形可能有四种关系:1)直线\({L_0}\)与三角形相交;2)直线\({L_1}\)与三角形所在的平面相交,但与三角形不相交;3)直线\({L_2}\)与在三角形所在的平面上;4)直线\({L_3}\)与三角形所在的平面平行。 一种朴素的检测算法是计算线性对象与三角形所在的平面的交点,再判断交点是否在三角形内。如果交点在三角形内,则线性对象与三角形相交;否则,不相交。这种算法效率不仅效率较低,而且更容易造成浮点数误差。因为计算机中的浮点数占用字节有限,能表示的精度有限,有效数较少,求直线与平面的交点,由于对同一个变量多次的乘法或者除法操作,造成误差的叠加,最后计算出来的结果由于精度问题,可能造成较大的误差。例如,三角形顶点的坐标数值较大,计算的直线与平面的交点,会由于精度误差导致求出的交点偏离平面,即可以检测到交点不在平面上。 Möller&Trumbore(1997)提出了一种更加高效的射线与三角形相交测试的算法,而且乘法或者除法操作造成的误差叠加较少,精度损失更小,因此性能上更加健壮。 三角形内的任意一点都可以用它相对于三角形的顶点的位置来定义: \(T(u,v) = (1 - u - v){V_0} + u{V_1} + v{V_2} \tag{4.18}\) 其中,\((u,v) \in D = \{ (u,v):u \ge 0,v \ge 0,u + v

spacer
浏览量:180

4.2. 点与三角形

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。 PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry 4.2. 点与三角形 4.2.1. 点与三角形的关系 1. 二维空间 问题描述:在二维空间上,判断点\(P\)与三角形\({V_0}{V_1}{V_2}\)的关系,其中,\({V_i} = \left( {{x_i},{y_i}} \right),i \in \{ 0,1,2\} \)。 图4.3 点与三角形的三种关系 二维空间上点与三角形共有三种关系:三角形内,三角形边上和三角形外。如图4.3所示,\({P_0}\)在三角形内部,\({P_1}\)在三角形边上,\({P_2}\)在三角形外。 在二维空间上的叉积遵守右手定则,设有三个点\({B_0}\),\({B_1}\)和\({B_2}\),令\(d = \left( {{B_1} - {B_0}} \right) \times \left( {{B_2} - {B_0}} \right)\),如果\(d \succ 0\),则\({B_0}\),\({B_1}\)和\({B_2}\)三个点是逆时针方向分布;如果\(d \prec 0\),则是顺时针方向分布;无否则,有\(d = 0\),则三点是共线的。 如果点\(P\)在\(\Delta

spacer
浏览量:22

4.1. 三角形简介

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。 PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry 4.1. 三角形简介 三角形面片,在图形学上有非常重要的应用,很多三维模型都是以三角形面片为基础图元。 在二维空间上,给定一个三角形\(T:\Delta {V_0}{V_1}{V_2}\),三角形的有符号面积可以表示为: \ 图4.1 逆时针朝向的三角形\(\Delta {V_0}{V_1}{V_2}\)和边\(\overline {{V_0}{V_1}} \)的法向量 三角形顶点顺序影响\({\mathop{\rm Area}\nolimits} (T) = \frac{1}{2}({V_1} - {V_0}) \times ({V_2} - {V_0})\)的正负,\(\left| {{\mathop{\rm Area}\nolimits} (T)} \right|\)表示三角形面积的大小。如果\({\mathop{\rm Area}\nolimits}

spacer