7.3 线段与三角形相交
(Segment-Triangle Intersection)
现在我们来计算三维空间中线段与三角形交点的问题。这个问题虽然更困难一些，但仍然很简洁。 我们将在 7.5 节中使用这部分代码来检测一个点是否位于多面体内部。此外，它还有许多其他用途。 事实上，这是当今最普遍的几何计算之一，因为它是计算机图形学中"光线追踪(ray tracing)"技术的关键步骤，即寻找光线与空间中多边形集合之间的交点。
我们将再次使用参数化的表示方法来推导方程。在全文中，我们用 \(T = \triangle abc\) 表示三角形，\(qr\) 表示线段，其中 \(q\) 被视为起始(“查询 query”)端点， \(r\) 为另一个端点。有可能要用 \(qr\) 表示射线，所以 "r" 是指“射线 ray”。我们将始终假设 \(r \neq q\)，因此输入的线段具有非零长度。
7.3.1 线段与平面的交点 (Segment-Plane Intersection)
第一步是确定 \(qr\) 是否与包含 \(T\) 的平面 \(\pi\) 相交。在本小节中，我们将先致力于实现这一中间目标，然后再确定交点是否位于三角形内。 就像直线上的所有点都必须满足关于 \(x\) 和 \(y\) 的直线方程一样，平面上的所有点也必须满足一个方程:
我们将用这四个系数来表示平面。将前三个系数看作一个向量 \((A, B, C)\)，这样平面方程就可以被看作是一个点积:
$$ \begin{equation}\label{f7.5} \pi : (x, y, z) \cdot (A, B, C) = D \tag{7.5} \end{equation} $$这个方程的几何意义是，平面上的每一点 \((x, y, z)\) 在 \((A, B, C)\) 上的投影长度都是相同的。结合图 7.2 可以清楚地看出，\(N = (A, B, C)\) 是平面的法向量，垂直于平面。 如果该向量是单位长度，那么 \(D\) 就是从原点到 \(\pi\) 的距离。
就像在二维空间中一样，线段上的任意点 \(p(t)\) 都可以如下表示。先移动到端点 \(q\)，然后加上一个沿该线段方向的缩放向量 \(p(t) = q + t(r - q)\)。 假设 \(q = (0, 0, 0)\)，那么 \(p(t) = tr\)，这将使计算更简单。现在我们要寻找一个参数 \(t\) 的值，将 \(r\) 延伸到该平面上。 因为平面上的每一点都必须满足公式(\(\ref{f7.5}\))，所以有
例如，考虑三点 \((1, 0, 0), (0, 1, 0), (0, 0, 1)\) 的平面。其平面方程为 \(x + y + z = 1\)，因此 \(N = (1, 1, 1)\)。令 \(r = (1, 2, 3)\)。由方程(7.6) 可得
$$ t = \frac{1}{(1, 2, 3) \cdot (1, 1, 1)} = \frac{1}{6} $$ 有，\(tr = \frac{1}{6}(1, 2, 3) = (\frac{1}{6}, \frac{1}{3}, \frac{1}{2})\) 位于该平面上，因为 \(\frac{1}{6} + \frac{1}{3} + \frac{1}{2} = 1\)。 将方程(7.6) 推广到任意 \(q\) 并不困难： $$ \begin{aligned}{} [q + t(r - q)] \cdot N & = D \\ q \cdot N + t(r - q) \cdot N & = D \\ t & = \frac{D - q \cdot N}{(r - q) \cdot N} \end{aligned} \tag{7.7} $$读者可能会好奇，为什么这种更复杂的情况，最后得到的方程只有一个而且只有一个未知数。 而较简单的线段-线段相交却导出了两个含两个未知参数的方程(7.1)和 (7.2)。 原因在于，我们尚未相对于三角形来精确定位交点，那将涉及其他未知数。我们在二维空间中本也可以遵循同样的策略，先求线段与直线的交点。但当时的情况很简单，我们可以直接同时确定参数。
在编写代码之前，还有一件事情，需要获取平面参数。通常，我们是从空间中确定三角形的三个点开始的，而不是从平面参数开始。者三个参数定义了垂直于三角形的法向量，可以利用上面的结果来求得。 我们可以使用第 1 章中的叉积方程(1.1)来确定 \(N\)， 就像在第 5 章中寻找下凸包(5.7.4 节)那样。有了 \(N\)， 我们可以通过将平面上的任意一点，比如三角形的一个顶点，代入方程(\(\ref{f7.5}\)) 来求得第四个系数 \(D\)。
线段-平面实现 (Segment-Plane Implementation)
现在我们开始编写代码。为了便于理解代码的用法，我们使用以下简单的数据结构，输入点类型为 tPointi，
存储在数组 tPointi Vertices[PMAX] 中。三角形用该数组中的三个整数索引表示。我们仍然使用 tPointi 类型表示这三个索引。
最终，我们将得到一个三角形集合，存储在数组 tPointi Faces[PMAX] 中。这里，Face[i] 代表一个特定的三角形，
如果 \(T\) 是一个三角形，则 Vertices[T[j]]，代表它的三个顶点，其中 \(j = 0, 1, 2\)。数据将通过简单的函数读取，此处不再赘述。参见Code7.4。
#define X 0
#define Y 1
#define Z 2
#define DIM 3 /* Dimension of points */
typedef int tPointi[DIM]; /* Type integer point */
typedef double tPointd[DIM]; /* Type double point */
#define PMAX 10000 /* Max # of pts */
tPointi Vertices[PMAX]; /* All the points */
tPointi Faces[PMAX]; /* Each triangle face is 3 indices */
main()
{
int V, F;
V = ReadVertices();
F = ReadFaces();
/* Processing */
}
线段-平面相交的实现分为两个过程。第一个过程 PlaneCoeff 计算 \(N\) 和 \(D\)，具体细节已在前面详细说明。
我们选择分两部分返回平面相关参数，因为它们在公式 (7.7) 中分别使用。稍后我们会解释，我们还将记录并返回 \(N\) 的最大分量的索引 \(m\)。参见Code7.5。
NormalVec` 的实现如 Code7.6 所示，与 Code4.12 相同，返回 \(N = (b - a) \times (c - a)\)。
为了防止溢出，即使 \(N\) 的坐标是整数，我们也使用 double 类型来表示它。
int PlaneCoeff( tPointi T, tPointd N, double *D )
{
int i;
double t; /* Temp storage */
double biggest = 0.0; /* Largest component of normal vector. */
int m = 0; /* Index of largest component. */
NormalVec( Vertices[T[0]], Vertices[T[1]], Vertices[T[2]], N );
*D = Dot( Vertices[T[0]], N );
/* Find the largest component of N. */
for ( i = 0; i < DIM; i++ ) {
t = fabs( N[i] );
if ( t > biggest ) {
biggest = t;
m = i;
}
}
return m;
}
void NormalVec( tPointi a, tPointi b, tPointi c, tPointd N )
{
N[X] = ( c[Z] - a[Z] ) * ( b[Y] - a[Y] ) -
( b[Z] - a[Z] ) * ( c[Y] - a[Y] );
N[Y] = ( b[Z] - a[Z] ) * ( c[X] - a[X] ) -
( b[X] - a[X] ) * ( c[Z] - a[Z] );
N[Z] = ( b[X] - a[X] ) * ( c[Y] - a[Y] ) -
( b[Y] - a[Y] ) * ( c[X] - a[X] );
}
double Dot( tPointi a, tPointd b )
{
int i;
double sum = 0.0;
for( i = 0; i < DIM; i++ )
sum += a[i] * b[i];
return sum;
}
void SubVec( tPointi a, tPointi b, tPointi c )
{
int i;
/* a - b => c. */
for( i = 0; i < DIM; i++ )
c[i] = a[i] - b[i];
}
我们将遵循 7.2 节的约定，让求交的函数返回一个编码来对结果进行分类：
- 'p': 线段完全位于平面内。
- 'q': (第一个)端点 \(q\) 位于平面上，但不是情况 'p'。
- 'r': (第二个)端点 \(r\) 位于平面上，但不是情况 'p'。
- '0': 线段严格位于平面的某一侧。
- '1': 线段与平面相交，且不满足 {'p', 'q', 'r'} 中的任何一种情况。
现在我们讨论，如何确定何时适用 'p'。当方程 (7.7) 的分母为零时，则 \(qr\) 平行于平面 \(\pi\)。这一点在较简单的方程 (7.6) 中或许最能看出来，当且仅当 \(r\) 正交于 \(N\) 时， 即，\(r\) 平行于 \(N\) 所正交的平面 \(\pi\)，分母为零。从该方程还可以看出，如果分子 \(D\) 也为零，则 \(r\) 位于平面内。推广到 \(qr\)， 根据方程 (7.7) 有，只要 \(q \cdot N = D\)，分子就为零，这正是代入 \(q\) 后的平面方程(\ref{f7.5})。因此，当且仅当 \(q\) 位于 \(\pi\) 上时，分子为零。 所以，当且仅当分子和分母都为零时，应返回编码 'p'。编码 'q' 和 'r' 分别由 \(t = 0\) 和 \(t = 1\) 确定，这可以通过测试分子和分母来验证，以避免依赖浮点除法。参见Code7.7。
char SegPlaneInt( tPointi T, tPointi q, tPointi r, tPointd p, int *m )
{
tPointd N; double D;
tPointi rq;
double num, denom, t;
int i;
*m = PlaneCoeff( T, N, &D );
num = D - Dot( q, N );
SubVec( r, q, rq );
denom = Dot( rq, N );
if ( denom == 0.0 ) { /* Segment is parallel to plane. */
if ( num == 0.0 ) /* q is on plane. */
return 'p';
else
return '0';
}
else
t = num / denom;
for( i = 0; i < DIM; i++ )
p[i] = q[i] + t * ( r[i] - q[i] );
if ( (0.0 < t) && (t < 1.0) )
return '1';
else if ( num == 0.0 ) /* t == 0 */
return 'q';
else if ( num == denom ) /* t == 1 */
return 'r';
else return '0';
}
线段-三角形分类 (Segment-Triangle Classification)
现在我们已经得到了线段 \(qr\) 与包含三角形 \(T\) 的平面 \(\pi\) 的交点 \(p\)，剩下的任务就是对 \(p\) 和 \(T\) 的关系进行分类: 它是在内部还是外部，在边界上，还是在顶点处? 虽然这看起来是一项简单的任务，但其中有一些细微之处。我们首先描述一种优雅的数学方法，但我们最终将不选择实现它。
重心坐标 (Barycentric Coordinates)。物体的重心 (barycenter)是其重量的中心。在二维、三维或任意维度中， 三角形 \(T = \Delta abc\) 的重心坐标可以由一组和为 1 的实数 \((\alpha, \beta, \gamma)\) 唯一表示，满足如下的关系:
$$ \begin{equation}\label{f7.8} \alpha a + \beta b + \gamma c = p \tag{7.8} \end{equation} $$根据 3.1 节和练习 3.2.3[4] 中关于凸组合和仿射组合的讨论，应该清楚的是，方程(\ref{f7.8}) 描述了平面 \(\pi\) 上的一个点。当且仅当三个系数都在 \([0, 1]\) 区间内，那么该点在 \(T\) 内。 这些系数可以看作是顶点的重量，其重心为 \(p\)。假设 \(a = (0, 0), b = (1, 0), c = (3, 2)\)。重心系数 \((\alpha, \beta, \gamma) = (\frac{1}{2}, 0, \frac{1}{2})\)， 指定了点 \(p = (0, 0)/2 + 0(1, 0) + (3, 2)/2 = (\frac{3}{2}, 1)\)，即边 \(ac\) 的中点。
这个例子说明，我们想要区分的所有类别都蕴含在重心坐标之中了。当且仅当恰好有一个系数为 0，则 \(p\) 位于边的内部，当且仅当有一个坐标为 1，则 \(p\) 与顶点重合。 当然，内/外的区别取决于坐标是否在 \([0, 1]\) 区间内。
重心坐标可以通过联立求解方程(\ref{f7.8}) 和 \(\alpha + \beta + \gamma = 1\) 来计算。对于三维三角形，这给出了包含三个未知数的四个方程。因为三角形位于一个平面内， 我们拥有冗余信息，问题可以简化为求解包含三个未知数的三个方程。
虽然这种计算是完全可能的，但我们选择另一种策略，部分是为了与第 4 章中使用的技术相联系，部分是因为该计算需要相当高的精度。 假设我们不做任何优化，对这种精度做一个粗略的估计。如果我们的输入坐标使用 \(L\) 位精度，那么法向量 \(N\) 使用 \(2L\)，而 \(q \cdot N\) 则需要 \(3L\)。 因此，方程(7.7) 的分子以及分母各需要 \(3L\)，所以 \(t\) 可能需要 \(6L\) 位。接下来 \(t\) 乘以 \(r - q\)，使得 \(p\) 的精度计数上升到 \(7L\)。 而这甚至还没有开始求解重心坐标方程。我们得出的结论是，基于 \(p\) 的浮点表示来对 \(p\) 进行分类需要十分精致的数据。尽管如此，当 \(p\) 是查询线段的端点时， 我们在任何情况下都需要对 \(p\) 进行分类，下面我们先来处理这个问题。
投影到二维 (Projection to Two Dimensions)。我们有一个点 \(p\) 已知它位于包含三角形 \(T\) 的平面 \(\pi\) 上，我们想要对 \(p\) 与 \(T\) 的关系进行分类。 因为 \(p\) 位于 \(\pi\) 上，所以这个问题本质上是二维的，而不是三维的。然而，要平移和旋转 \(\pi\) 使其与 \(xy\) 平面重合，需要做一些工作。 但有两个现象使得我们在不对平面进行这种重新对齐的情况下，可以在二维空间中解决问题。首先，假设将 \(T\) 投影到 \(xy\) 平面上，当且仅当 \(p\) 在 \(T\) 的投影内， 则 \(p\) 在 \(T\) 内。这一点从图 7.3 中可以明显看出。设 \(p'\) 和 \(T'\) 分别是 \(p\) 和 \(T\) 的投影。\(p\) 关于 \(T\) 的分类完全可以通过这些投影完成。 当且仅当 \(p'\) 在 \(T'\) 的某条边的内部，则\(p\) 在 \(T\) 的某条边的内部，依此类推。
如果 \(\pi\) 是垂直的，刚才的命题就失效了，这该如何是好?这可以通过第二个现象来避免。将对应于平面 \(\pi\) 的法向量 \(N\) 的最大分量的坐标投影掉(projecting out)，可以保证非退化性。 比如，一个接近水平的平面具有较大的 \(z\) 分量，这就需要进行到 \(xy\) 平面的投影。一个垂直 \(xy\) 平面的 \(N\) 将具有零 \(z\) 分量，因此我们就投影到 \(xz\) 平面或 \(yz\) 平面上， 具体取决于哪一个更接近与 \(\pi\) 平行。这就是为什么 Code7.5 计算了最大分量的索引 \(m\)。
我们现在准备编写一个函数 InTri3D，它使用以下分类方案对三角形 \(T\) 上的点 \(p\) 进行分类:
- 'V': \(p\) 与 \(T\) 的一个顶点(Vertex)重合。
- 'E': \(p\) 在 \(T\) 的一条边(Edge)的内部。
- 'F': \(p\) 在 \(T\) 的一个面(Face)的内部。
- '0': \(p\) 不与 \(T\) 相交。
如 Code7.8 所示，从顶层来看，它做的事情很少。它投影掉坐标 \(m\)，并将 \(p'\) 和 \(T'\) 传递给一个在二维投影上函数 InTri2D。
请注意，无论投影到哪个平面，我们都用 \(x,y\) 来记录 \(pp\) 和 \(Tp\) 的投影坐标。
char InTri3D( tPointi T, int m, tPointi p )
{
int i; /* Index for X,Y,Z */
int j; /* Index for X,Y */
int k; /* Index for triangle vertex */
tPointi pp; /* projected p */
tPointi Tp[3]; /* projected T: three new vertices */
/* Project out coordinate m in both p and the triangular face */
j = 0;
for ( i = 0; i < DIM; i++ ) {
if ( i != m ) { /* skip largest coordinate */
pp[j] = p[i];
for ( k = 0; k < 3; k++ )
Tp[k][j] = Vertices[T[k]][i];
j++;
}
}
return( InTri2D( Tp, pp ) );
}
既然问题已经转化到了 \(xy\) 平面上，这就很容易解决了。我们可以像第 1 章那样，通过计算有向面积(signed areas)来对 \(p'\) 进行分类。
唯一的麻烦是，我们不知道这三个顶点的方向(orientation)。但由于只有三个顶点，给定的顺序必然不是逆时针就是顺时针的。代码必须能够处理这两种方向。
InTri2D 首先计算由 \(p'\) 与 \(T'\) 的三条边分别确定的三个面积。分类正是基于这些面积进行的。
参见图 7.4，并与图1.19 比较:
- 如果这三个面积全为正，或全为负，则 \(p'\) 严格位于 \(T'\) 内部。
- 如果有两个面积为零，则 \(p'\) 位于包含两条边的直线上，即，在顶点处。
- 如果三个面积全为零，则 \(p'\) 必然与所有三条边共线，这只有在 \(T'\) 退化成一条线时才会发生。这是不可能的，因此我们输出一条错误信息并退出。
- 只有一个面积为零而另外两个非零时，只有当另外两个非零面积同号时，\(p'\) 才位于 \(T'\) 某条边上。
Code7.9 分类讨论了上述几种情况，并给出了实现。
char InTri2D( tPointi Tp[3], tPointi pp )
{
int area0, area1, area2;
area0 = AreaSign( pp, Tp[0], Tp[1] );
area1 = AreaSign( pp, Tp[1], Tp[2] );
area2 = AreaSign( pp, Tp[2], Tp[0] );
if ( ( area0 == 0 ) && ( area1 > 0 ) && ( area2 > 0 ) ||
( area1 == 0 ) && ( area0 > 0 ) && ( area2 > 0 ) ||
( area2 == 0 ) && ( area0 > 0 ) && ( area1 > 0 ) )
return 'E';
if ( ( area0 == 0 ) && ( area1 < 0 ) && ( area2 > 0 ) ||
( area1 == 0 ) && ( area0 < 0 ) && ( area2 > 0 ) ||
( area2 == 0 ) && ( area0 < 0 ) && ( area1 > 0 ) )
return 'E';
if ( ( area0 > 0 ) && ( area1 > 0 ) && ( area2 > 0 ) ||
( area0 < 0 ) && ( area1 < 0 ) && ( area2 < 0 ) )
return 'F';
if ( ( area0 == 0 ) && ( area1 == 0 ) && ( area2 == 0 ) )
fprintf( stderr, "Error in InTriD\n" ),
exit (EXIT_FAILURE);
if ( ( area0 == 0 ) && ( area1 == 0 ) ||
( area0 == 0 ) && ( area2 == 0 ) ||
( area1 == 0 ) && ( area2 == 0 ) )
return 'V';
else
return '0';
}
平面内的线段 (Segment in Plane)。对于线段 \(qr\) 位于平面 \(\pi\) 内的情况，也可以通过相同的投影方法来处理。投影到二维空间中，
检查 \(q'\) 或 \(r'\) 是否位于 \(T'\) 内。在这种情况下，相应的端点可以作为 \(p\) 返回。否则，使用 SegSegInt，
检查 \(q'r'\) 是否与 \(T'\) 的某条边相交。既然我们已经给出了所有这些代码片段，这里就不再深入探讨了，将实现细节留给练习 7.3.2[4]。
通过体积进行分类 (Classification by Volumes)。我们终于可以来解决"通常 usual"的情况了，\(qr\) 穿过平面 \(\pi\)，\(q\) 在一侧 \(r\) 在另一侧。
我们可以以一种类似于 InTri2D 对 \(p'\) 进行分类的方式，来讨论 \(qr\) 如何与 \(T\)相交，只是现在我们计算的是体积而不是面积。
具体的，我们计算由 \(qr\) 和 \(T\) 的每条边确定的三个四面体的有向体积。设 \(T = (v_0, v_1, v_2)\)。如此，我们得到体积 \(V_i = \text{Volume}(q, v_i, v_{i+1}, r)\)。
与二维空间一样，我们只能假设顶点是按逆时针或顺时针顺序排列的，但这已经足够了。我们将采用如下分类方案:
- 'v': 开线段包含 \(T\) 的一个顶点。
- 'e': 开线段包含 \(T\) 的一条边的相对内点。
- 'f': 开线段包含 \(T\) 的一个面的相对内点。
- '0': 开线段不与三角形 \(T\) 相交。
如果所有三个 \(V_i\) 都是正的，或者都是负的，那么 \(qr\) 穿过 \(T\) 的一个严格内点，如图 7.5(f) 所示。
如果 \(V_i\) 中有两个符号相反，那么 \(qr\) 不与 \(T\) 相交。如果有一个为零，那么 \(qr\) 穿过某条边的内点。如图 7.5(e) 中 \(V_1 = 0\)。
如果有两个为零，\(qr\) 穿过一个顶点。如图 7.5(v) 中 \(V_1 = V_2 = 0\)。如果所有三个 \(V_i\) 都为零，这意味着 \(qr\) 位于 \(T\) 的平面内，这种情况前面已经处理过了。
很容易看出，所有这些条件都是相应表征的充要条件。这些规则的简单实现体现在函数 SegTriCross 中，参加Code7.10。
VolumeSign 与第 4 章中使用的 Code4.16 逻辑相同，
只是对输入数据结构做了一点适配。
char SegTriCross( tPointi T, tPointi q, tPointi r )
{
int vol0, vol1, vol2;
vol0 = VolumeSign( q, Vertices[ T[0] ], Vertices[ T[1] ], r );
vol1 = VolumeSign( q, Vertices[ T[1] ], Vertices[ T[2] ], r );
vol2 = VolumeSign( q, Vertices[ T[2] ], Vertices[ T[0] ], r );
/* Same sign: segment intersects interior of triangle. */
if ( ( ( vol0 > 0 ) && ( vol1 > 0 ) && ( vol2 > 0 ) ) ||
( ( vol0 < 0 ) && ( vol1 < 0 ) && ( vol2 < 0 ) ) )
return 'f';
/* Opposite sign: no intersection between segment and triangle. */
if ( ( ( vol0 > 0 ) || ( vol1 > 0 ) || ( vol2 > 0 ) ) &&
( ( vol0 < 0 ) || ( vol1 < 0 ) || ( vol2 < 0 ) ) )
return '0';
else if ( ( vol0 == 0 ) && ( vol1 == 0 ) && ( vol2 == 0 ) )
fprintf( stderr, "Error 1 in SegTriCross\n" ),
exit (EXIT_FAILURE);
/* Two zeros: segment intersects vertex. */
else if ( ( ( vol0 == 0 ) && ( vol1 == 0 ) ) ||
( ( vol0 == 0 ) && ( vol2 == 0 ) ) ||
( ( vol1 == 0 ) && ( vol2 == 0 ) ) )
return 'v';
/* One zero: segment intersects edge. */
else if ( ( vol0 == 0 ) || ( vol1 == 0 ) || ( vol2 == 0 ) )
return 'e';
else
fprintf( stderr, "Error 2 in SegTriCross\n" ),
exit (EXIT_FAILURE);
}
char SegTriInt( tPointi T, tPointi q, tPointi r, tPointd p )
{
int code;
int m;
code = SegPlaneInt( T, q, r, p, &m );
if ( code == 'q' )
return InTri3D( T, m, q );
else if ( code == 'r' )
return InTri3D( T, m, r );
else if ( code == 'p' )
return InPlane( T, m, q, r, p );
else
return SegTriCross( T, q, r );
}
如此，我们完成了计算线段与三角形交点的代码开发。简单的顶层逻辑如 Code7.11 所示。由于未实现 InPlane 函数且仅返回 'p'，
该代码返回集合 \(\{0, p, V, E, F, v, e, f\}\) 中的一个字符，具有以下互斥的含义:
- '0': 闭线段不与 \(T\) 相交。
- 'p': 线段完全位于 \(T\) 的平面内。剩余的所有类别均假设 'p' 不成立。
- 'V': 线段的一个端点与 \(T\) 的一个顶点(Vertex)重合。
- 'E': 线段的一个端点位于 \(T\) 的一条边(Edge)的相对内部。
- 'F': 线段的一个端点位于 \(T\) 的一个面(Face)的相对内部。
- 'v': 开线段包含 (T) 的一个顶点。
- 'e': 开线段包含 (T) 的一条边的相对内部的一点。
- 'f': 开线段包含 (T) 的一个面的相对内部的一点。
返回的编码可以看作是对布尔值 0/1 的细化，将 1 扩展为七种退化相交类型。如前所述，通过允许参数 \(t\) 在区间 \([0, 1]\) 之外变化，很容易对其修改，使其能够表示射线或直线与三角形的交集。 我们将在 7.5 节再演示该代码的用法。
7.3.2 练习
- 分母为零 Denominator zero。证明，当且仅当这两条线段平行时，线段与线段相交方程(公式 (7.1)–(7.3))中的分母为零。
- [Programming] 射线与线段相交 Ray-segment intersection。修改函数
SegSegInt为RaySegInt， 将 \(a\) 视为射线原点，将 \(b\) 视为射线上的一点，使其返回一个字符代码，以指示射线与线段 \(cd\) 之间各种可能的相交情况。 - 重心坐标 Barycentric coordinates。令 \(p\) 为三角形 \(T = (v_1, v_2, v_3)\) 内的一点，其重心参数为 \((t_1, t_2, t_3)\)。 连接 \(p\) 与三个顶点，将 \(T\) 分割成三个三角形。将它们分别命名为 \(T_1, T_2, T_3\)，其中 \(T_i\) 不与 \(v_i\) 相邻，即 \(v_i\) 不是 \(T_i\) 的顶点。 证明这些三角形 \(T_i\) 的面积与 \(p\) 的重心参数 \(t_i\) 成正比(Coxeter 1961, p. 217)。
- [Programming] 线段在平面内 Segment in plane。通过实现一个适当的函数
InPlane， 来扩展函数SegTriInt以处理 \(qr\) 完全位于 \(T\) 所在平面内的情况。