02-2 第二章 基本图形的生成与计算-图形求交.pptx

第1页：图形求交

计算机图形学讲义 第2章 基本图形的生成与计算—图形求交

第2页：本章主要内容

主要内容

• 求空间直线段与直线段的交点
• 求平面上两线段的交点
• 求直线段与平面的交点
• 判断点是否在多边形内

第3页：空间直线段求交

假设两条直线的端点分别为 P1、P2 和 Q1、Q2，则直线可以用向量形式表示为：

P(t) = A + Bt，0≤t≤1　　Q(s) = C + Ds，0≤s≤1

其中，A = P1，B = P2 − P1，C = Q1，D = Q2 − Q1。构造方程 A + Bt = C + Ds（2.9）

对三维空间中的直线段来说，上述方程组实际上是一个二元一次方程组，由 3 个方程式组成。可以从其中两个解出 s、t，再用第三个验证解的有效性。当所得的解 (ti, si) 是有效解时，可用两个方程之一计算交点坐标。

第4页：用点积求解参数s与t

根据向量的基本性质，可直接计算 s 与 t。对方程（2.9）两边构造点积得：

(C×D)·(A + Bt) = (C×D)·(C + Ds)

由于 C×D 同时垂直于 C 和 D，等式右边为 0。故有类似地可求出另一参数。

第5页：空间线段求交计算实例

• P(t) = A + Bt；A = (1,1,1)，B = (3,4,5)；
• Q(s) = C + Ds；C = (1,1,2)，D = (5,3,2)；
• 交点：O1 = Q(−1) = (−4,−2,0)；

第6页：交点的有效性与无解判别

• 交点：O2 = P(1/5) = (1,1,1) + (1/5)*(3,4,5)；
• 交点：O1 = (−4,−2,0)；
• 无交点时，不能用这种方法！
• 先判断有无解：计算方阵 (B, −D, C−A) 的行列式。

第7页：平面上两线段求交

2. 求平面上两线段的交点

• 线段 AB 顶点坐标为 A(0,0)、B(4,4)，线段 CD 的顶点坐标为 C(0,4)、D(1,2)。判断线段 AB 和 CD 有无交点。
• 线段 AB 方程：A + (B−A)*t1 = (0,0) + (4,4)*t1，其中 0≤t1≤1，即 x = 4*t1，y = 4*t1；
• 线段 CD 方程：C + (D−C)*t2 = (0,4) + (1,−2)*t2，其中 0≤t2≤1，即 x = t2，y = 4−2*t2；
• 联立有 4*t1 = t2；4*t1 = 4−2*t2，可解得 t1 = 1/3，t2 = 4/3。
• 因为 t2 > 1，故无交点。

第8页：线段与平面求交

3. 求直线段与平面的交点

把平面上的点表示为 P(u,w) = A + uB + wC，即：x = a1 + u*b1 + w*c1；y = a2 + u*b1 + w*c1；z = a1 + u*b1 + w*c1。直线段上的点表示为 Q(t) = D + tE。

假设线段不平行于平面，则它们交于 R = P(u,w) = Q(t)，即 A + uB + wC = D + tE。

第9页：平面求交的点乘解法

等式两边点乘 (B×C)，得：(B×C)·(A + uB + wC) = (B×C)·(D + tE)

由于 B×C 既垂直于 B，又垂直于 C，故有：(B×C)·A = (B×C)·(D + tE)，可解出参数。如果无交点，则该式不成立。

第10页：判断点是否在多边形内

4. 判断点是否在多边形内

当多边形是凹多边形，甚至还带孔时，可采用交点计数法判断点是否在多边形内。具体做法是，从判断点作一射线至无穷远：若交点个数为奇数，则点在多边形内；否则，点在多边形外。

第11页：五边形判定计算实例

5 计算实例

• 有一平面五边形区域，顶点坐标为 A(0,0)、B(0,2)、C(1,1)、D(2,2)、E(2,0)，用交点计数法判断点 P(0.5,1.2) 是否在该多边形区域内，设所引射线为：x = 0.5+u，y = 1.2，其中 u > 0。
• 线段 AB 方程：x = 0，y = 2*t1；线段 BC 方程：x = t2，y = 2−t2；同理可求线段 CD、DE、EA 的参数方程。
• 将线段 AB 的方程与射线方程联立，有 0.5+u = 0；1.2 = 2*t1，可解得 u = −0.5，t1 = 0.6。因为 u < 0，故无交点。
• 同理可将其它线段的方程与射线方程联立判断是否有交点。

第12页：本章作业

作业

1. 空间两条直线段的端点为 P1(1,2,−3)、P2(2,−1,−1) 和 Q1(1,1,−2)、Q2(2,2,−4)，判断直线段 P1P2 和 Q1Q2 有没有交点，如果有的话，求出交点。写出算法详细的计算过程。
2. 有一平面五边形区域，顶点坐标为 A(0,0)、B(0,2)、C(1,1)、D(2,2)、E(2,0)，用交点计数法判断点 P(0.5,1.8) 是否在该多边形区域内。写出算法详细的计算过程。