📄 2.5 图形求交.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0058)http://www.ekany.com/wdg98/cg/contents/chapter2/les251.htm -->
<HTML><HEAD><TITLE>2</TITLE>
<META http-equiv=Content-Type content="text/html; charset=gb2312">
<META content="MSHTML 6.00.2800.1106" name=GENERATOR></HEAD>
<BODY>
<H2 align=justify><FONT face=楷体_GB2312><B><FONT size=5>2.5
图形求交</FONT></B></FONT></H2>
<P align=justify><FONT face=楷体_GB2312><SUP><SPAN
style="LETTER-SPACING: 1px"><FONT
size=4>在计算机图形学中常常会遇到求交计算。例如，在进行扫描线区域填充时要求线段的交点，许多消隐算法需要进行直线和平面多边形的求交，等等。求交运算往往是比较复杂的，为了减小计算量，在进行真正的求交计算之前，往往先用凸包等辅助结构进行粗略的比较，排除那些显然不相交的情形。求交计算是</FONT></SPAN></SUP><SPAN
style="LETTER-SPACING: 1px"><SUP><FONT
size=4>CAD系统的重要部分。它的准确性与效率直接影响CAD</FONT></SUP></SPAN><SUP><FONT size=4><SPAN
style="LETTER-SPACING: 1px">系统的可靠性与实用性。</SPAN></FONT></SUP></FONT></P>
<P align=justify><FONT face=楷体_GB2312><SUP><SPAN
style="LETTER-SPACING: 1px"><FONT
size=4>在数学上两个浮点数可以严格相等，但计算机表示的浮点数有误差，所以当两个浮点数的差的绝对值充分小时（例如，小于某个正数</FONT></SPAN></SUP><SPAN
style="LETTER-SPACING: 1px"><SUP><FONT size=4>?
），就认为它们相等。相应地，求交运算中也要引进容差。当两个点的坐标值充分接近时，即其距离充分近时，就被认为是重合的点，直观地说，点可看作半径为?
的球，线可看作半径为? 的圆管，面可看作厚度为2? 的薄板。一般取? =10-6</FONT></SUP></SPAN><SUP><FONT
size=4><SPAN style="LETTER-SPACING: 1px">或更小的数。</SPAN></FONT></SUP></FONT></P>
<P align=justify><FONT face=楷体_GB2312><SUP><SPAN
style="LETTER-SPACING: 1px"><FONT
size=4>求交问题可以分为求交点和求交线两类。本节的讨论不涉及自由曲线曲面，有关自由曲线曲面的求交问题将在</FONT></SPAN></SUP><FONT
size=4><SUP><SPAN
style="LETTER-SPACING: 1px">2.7和2.8节讨论。</SPAN></SUP></FONT></FONT><B></P>
<H3 align=justify><FONT face=楷体_GB2312 size=4>2.5.1求交点算法</FONT></B></H3>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>求交点可以分两种情况：求线与线的交点以及求线与面的交点。下面首先讨论线与线的交点的求法。。</FONT></SPAN></SUP></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>1、直线段与直线段的交点</FONT></SPAN></SUP></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>假设二条直线的端点分别为P1，P2，Q1，Q2，则它们可以用向量形式表示为：</FONT></SPAN></SUP></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4> P(t)=A+Bt (0? t? 1)</FONT></SPAN></SUP></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4> Q(s)=C+Ds (0? s? 1)</FONT></SPAN></SUP></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>其中，A=P1，B=P2-P1，C=Q1，D=Q2-Q1。</FONT></SPAN></SUP></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>构造方程</FONT></SPAN></SUP></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4> A+Bt=C+Ds (2-5-1)</FONT></SPAN></SUP></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>对三维空间中的直线段来说，上述方程实际上是一个二元一次方程组，由三个方程式组成。可以从其中两个解出s,
t，再用第三个验证解的有效性：若第三个方程成立则说明找到了解，否则说明两条直线不相交。当所得的解（ti,
si）是有效解时，可用二个线段方程之一计算交点坐标，例如P(ti)=A+Bti。</FONT></SPAN></SUP></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>我们还可以根据向量的基本性质，直接计算s与t：对（2-5-2）两边构造点积得</FONT></SPAN></SUP></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4> (C? D)·（A+Bt）=（C? D）·（C+Ds）</FONT></SPAN></SUP></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>由于C? D同时垂直于C和D，等式右边为零。故有</FONT></SPAN></SUP></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>
<IMG height=44 src="2.5 图形求交.files/Image94.gif"
width=112></FONT></SPAN></SUP></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>类似地有</FONT></SPAN></SUP></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4> <IMG height=44 src="2.5 图形求交.files/Image95.gif"
width=113></FONT></SPAN></SUP></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>完整的算法还应判断无解与无穷多解（共线）的情形，以及考虑数值计算误差造成的影响。</FONT></SPAN></SUP></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>2、直线段与二次曲线的交点</FONT></SPAN></SUP></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>不失一般性，考虑平面上一条直线与同平面的一条二次曲线的交。</FONT></SPAN></SUP></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>假设 曲线方程为 f(x, y)=0,</FONT></SPAN></SUP></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4> 直线段方程为 (x, y)=(x1+tdx, y1+tdy),</FONT></SPAN></SUP></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4> 则在交点处有 f(x1+tdx, y1+tdy)=0</FONT></SPAN></SUP></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>当曲线为二次曲线时，上述方程可写为</FONT></SPAN></SUP></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4> at2+bt+c=0</FONT></SPAN></SUP></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>用二次方程求根公式即可解出t值。</FONT></SPAN></SUP></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>3、圆锥曲线与圆锥曲线的交点</FONT></SPAN></SUP></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>圆锥曲线有代数法表示、几何法表示与参数法表示。在进行一对圆锥曲线的求交时，把其中一条圆锥曲线用代数/几何法表示为隐函数形式，另一条表示为参数形式（如二次NURBS曲线）。将参数形式代入隐函数形式可得关于参数的四次方程，可以使用四次方程的求根公式解出交点参数。得到交点后可再验证交点是否在有效的圆锥曲线段上。</FONT></SPAN></SUP></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>下面讨论线与面的交点的求法。</FONT></SPAN></SUP></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>1、直线段与平面的交点</FONT></SPAN></SUP></P>
<P align=center><FONT face=楷体_GB2312><IMG height=333
alt="2_5_1.gif (4026 bytes)" src="2.5 图形求交.files/2_5_1.gif"
width=336></FONT></P>
<P align=center><FONT face=楷体_GB2312>图2.5.1 线段与平面求交</FONT></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>考虑直线段与无界平面的求交问题，如图8.3.6所示。把平面上的点表示为P(u,
w)=A+uB+wC，直线段上的点表示为Q(t)=D+tE，二者的交点记为R。假设线段不平行于平面，则它们交于R=P(u,
w)=Q(t)，即</FONT></SPAN></SUP></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4> A+uB+wC=D+tE</FONT></SPAN></SUP></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>等式两边点乘（B? C），得</FONT></SPAN></SUP></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4> （B? C）·（A+uB+wC）=（B? C）·（D+tE）</FONT></SPAN></SUP></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>由于B? C既垂直于B，又垂直于C，故有</FONT></SPAN></SUP></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>（B? C）·A=（B? C）·（D+tE）</FONT></SPAN></SUP></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>可解出</FONT></SPAN></SUP><FONT face=System></P></FONT>
<P><FONT face=楷体_GB2312 size=3><IMG height=44 src="2.5 图形求交.files/Image96.gif"
width=184></FONT></P>
<P align=justify><FONT face=楷体_GB2312>类似求得</FONT></P>
<P><FONT face=楷体_GB2312 size=3><IMG height=44 src="2.5 图形求交.files/Image97.gif"
width=189></FONT></P>
<P><FONT face=楷体_GB2312 size=3><IMG height=44 src="2.5 图形求交.files/Image98.gif"
width=192></FONT></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>如果是直线与平面区域求交点，则要进一步判断点是否在平面上的有效区域中，其算法可参见2.5.3节。</FONT></SPAN></SUP></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>2、圆锥曲线与平面的交点</FONT></SPAN></SUP></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>圆锥曲线与平面求交时，可以把圆锥曲线表示为参数形式，并把圆锥曲线的参数形式代入平面方程，即可得到参数的二次方程进行求解。</FONT></SPAN></SUP></P>
<OL start=3>
<LI><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>圆锥曲线与二次曲面的交点</FONT></SPAN></SUP> </LI></OL>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>圆锥曲线与二次曲面求交时，可把圆锥曲线的参数形式代入二次曲面的隐式方程，得到参数的四次方程，用求根公式求解。</FONT></SPAN></SUP></P>
<P><A href="http://www.ekany.com/wdg98/cg/contents/chapter2/les244.htm"><FONT
face=楷体_GB2312><上一节〉</FONT></A><FONT face=楷体_GB2312> <A
href="http://www.ekany.com/wdg98/cg/contents/chapter2/les252.htm">〈下一节〉</A>
<A
href="http://www.ekany.com/wdg98/cg/tutorial/chapter2/lesson2-5.htm">〈返回〉</A></FONT></P></BODY></HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -