2.4 字符的生成 2.5 图形求交

2.5 图形求交

^{在计算机图形学中常常会遇到求交计算。例如，在进行扫描线区域填充时要求线段的交点，许多消隐算法需要进行直线和平面多边形的求交，等等。求交运算往往是比较复杂的，为了减小计算量，在进行真正的求交计算之前，往往先用凸包等辅助结构进行粗略的比较，排除那些显然不相交的情形。求交计算是CAD系统的重要部分。它的准确性与效率直接影响CAD系统的可靠性与实用性。}

^{在数学上两个浮点数可以严格相等，但计算机表示的浮点数有误差，所以当两个浮点数的差的绝对值充分小时（例如，小于某个正数? ），就认为它们相等。相应地，求交运算中也要引进容差。当两个点的坐标值充分接近时，即其距离充分近时，就被认为是重合的点，直观地说，点可看作半径为? 的球，线可看作半径为? 的圆管，面可看作厚度为2? 的薄板。一般取? =10-6或更小的数。}电脑爱好者网2Ev5r{y-G$q7I

^{求交问题可以分为求交点和求交线两类。本节的讨论不涉及自由曲线曲面，有关自由曲线曲面的求交问题将在2.7和2.8节讨论。}

2.5.1求交点算法

^{求交点可以分两种情况：求线与线的交点以及求线与面的交点。下面首先讨论线与线的交点的求法。。}

^{1、直线段与直线段的交点}

^{假设二条直线的端点分别为P1，P2，Q1，Q2，则它们可以用向量形式表示为：}

^{P(t)=A+Bt (0? t? 1)}电脑爱好者网"q8A&Z)g0w6q

^{Q(s)=C+Ds (0? s? 1)}

^{其中，A=P1，B=P2-P1，C=Q1，D=Q2-Q1。}电脑爱好者网K&j` N'}9{

^构造方程

^{A+Bt=C+Ds (2-5-1)}电脑爱好者网c Si$T0dz#G

^{对三维空间中的直线段来说，上述方程实际上是一个二元一次方程组，由三个方程式组成。可以从其中两个解出s, t，再用第三个验证解的有效性：若第三个方程成立则说明找到了解，否则说明两条直线不相交。当所得的解（ti, si）是有效解时，可用二个线段方程之一计算交点坐标，例如P(ti)=A+Bti。}

^{我们还可以根据向量的基本性质，直接计算s与t：对（2-5-2）两边构造点积得}

^{(C? D)·（A+Bt）=（C? D）·（C+Ds）}电脑爱好者网E
~)c] K

^{由于C? D同时垂直于C和D，等式右边为零。故有}

              电脑爱好者网v"|6N.^e8O!lW#EW SfL

^类似地有

电脑爱好者网I:P~5kz

^{完整的算法还应判断无解与无穷多解（共线）的情形，以及考虑数值计算误差造成的影响。}电脑爱好者网T2Bm{0T

^{2、直线段与二次曲线的交点}电脑爱好者网+\:W\8L D2wR/B0E@8v

^{不失一般性，考虑平面上一条直线与同平面的一条二次曲线的交。}电脑爱好者网d.kPz"Kd3T ?:U[ ]7X"B

^{假设 曲线方程为 　　f(x, y)=0,}电脑爱好者网1r9^A4d7N

^{直线段方程为 　　(x, y)=(x1+tdx, y1+tdy),}电脑爱好者网5z'uF/]j+p,a:P]

^{则在交点处有 　f(x1+tdx, y1+tdy)=0}电脑爱好者网 m-MJnc y]wE2K

^{当曲线为二次曲线时，上述方程可写为}

^at2+bt+c=0

^{用二次方程求根公式即可解出t值。}电脑爱好者网r,e e|#[{$BHQG

^{3、圆锥曲线与圆锥曲线的交点}电脑爱好者网1\$}D\
nJv

^{圆锥曲线有代数法表示、几何法表示与参数法表示。在进行一对圆锥曲线的求交时，把其中一条圆锥曲线用代数/几何法表示为隐函数形式，另一条表示为参数形式（如二次NURBS曲线）。将参数形式代入隐函数形式可得关于参数的四次方程，可以使用四次方程的求根公式解出交点参数。得到交点后可再验证交点是否在有效的圆锥曲线段上。}电脑爱好者网s1E)WE?`

^{下面讨论线与面的交点的求法。}电脑爱好者网K*J%kf&t

^{1、直线段与平面的交点}电脑爱好者网]Kcq+|;Lk%E}e:V

图2.5.1 线段与平面求交电脑爱好者网6M(M ? \N1H,l\

^{考虑直线段与无界平面的求交问题，如图8.3.6所示。把平面上的点表示为P(u, w)=A+uB+wC，直线段上的点表示为Q(t)=D+tE，二者的交点记为R。假设线段不平行于平面，则它们交于R=P(u, w)=Q(t)，即}电脑爱好者网?UIm6[u2~

^A+uB+wC=D+tE电脑爱好者网 F?f5V y%c}

^{等式两边点乘（B? C），得}

^{（B? C）·（A+uB+wC）=（B? C）·（D+tE）}电脑爱好者网 Z.GG*e|9P*U&b6N.j$E

^{由于B? C既垂直于B，又垂直于C，故有}电脑爱好者网*k6ALdF[_2F

^{（B? C）·A=（B? C）·（D+tE）}

^可解出

类似求得

l#ic6Ha\^ Kl~8w$Y0

^{如果是直线与平面区域求交点，则要进一步判断点是否在平面上的有效区域中，其算法可参见2.5.3节。}

^{2、圆锥曲线与平面的交点}

^{圆锥曲线与平面求交时，可以把圆锥曲线表示为参数形式，并把圆锥曲线的参数形式代入平面方程，即可得到参数的二次方程进行求解。}

3. ^{圆锥曲线与二次曲面的交点}

^{圆锥曲线与二次曲面求交时，可把圆锥曲线的参数形式代入二次曲面的隐式方程，得到参数的四次方程，用求根公式求解。}