计算机图形学 第3版 第5章 图形运算.pptx

2024/10/11;第五章图形运算;第一节线段的交点计算;若两线段相交,则交点的参数值,应满足:

即

因此,若行列式;需要注意,只有0≤λ≤1,0≤μ≤1时两线段才真正相交。否则,交点在两线段或其中某一条线段的延长线上,这时仍然认为是两线段不相交。;两线段AB和CD交点的算法;二.多条线段求交;其中，S2uS4,S1νS2,S2νS4,S1νS4;假设：为简便起见，要求交点的n条线段中没有垂直的线段(规定的次序关系对垂直的线段不适合)，也没有三条以上的线段交于一点的情况。

两线段相交的必要条件：

若两线段相交,则必然存在某个x,使它们在规定的次序关系x下是相邻的。

算法从左向右扫描,在扫描过程维持正确的线段间上述次序关系。这种次序关系只能有三种可能的变化方式:

1．遇见某条线段S的左端点,此时S应加入次序关系。

2．遇见某线段S的右端点,此时S应从次序关系中删除。

3．遇到某两条线段S1和S2的交点,这时在次序关系中S1和S2交换位置。;算法的数据结构和实现过程:

算法实施需要两个基本的数据结构:

扫描线状态表和事件点进度表

扫描线状态表L：存放按次序关系x排序的线段的序列。初始为空,扫描过程中当关系x改变时变化。

事件点：扫描过程中可能使次序关系x发生变化的点,

事件点进度表E：存放事件点的表，初始为n条线段的2n个端点，在平面扫描过程中求出的交点，应及时地插入到事件点进度表中。;扫描线状态表应能支持以下四个操作:

(1)INSERT(S,L),把线段S插入到扫描线状态表L中,注意应插入到适当位置以保持正确的次序关系。

(2)DELETE(S,L),从L中删除线段S。

(3)ABOVE(S,L),返回次序关系中S上面紧接着的线段的编号。

(4)BELOW(S,L),返回次序关系中S下面紧接着的线段的编号。

事件点进度表E应能支持以下三个操作:

(1)MIN(E),取出表E中的最小元素。

(2)INSERT(x,E),把横坐标为x的一个点插入到表E中,插入要使E中事件点存放保持递增次序。

(3)MEMBER(x,E),判定横坐标为x的点是否在事件点进度表E中。

;算法:;算法:;2024/10/11;2024/10/11;2024/10/11; 设有三条线段S1，S2，S3,它们的坐标如下

(1,1),(5,3,),(2,3),(4,1),(6,4),(8,2).要计算所有交点。

算法初??形成的事件点进度表E，可有形式

(((1,1),S1左端点)，((2,3),S2左端点)，

((4,1),S2右端点)，((5,3),S1右端点)，

((6,4),S3左端点)，((8,2),S3右端点));算法步骤

;;1.求平面方程

采用多个顶点位置坐标来计算平面方程可以减少由于不共面而引起的偏差。

设要求出通过若干顶点的平面方程Ax+By+Cz+D=0,即要确定系数A,B,C,D,可采用如下做法

平面方程Ax+By+Cz+D=0的系数A,B,C与该平面上多边形分别在x=0,y=0,z=0三个坐标平面上投影的面积成比例;多边形在z=0平面上投影的面积S可如下求出:

式中若i=n则j=1,否则j=i+1。

类似地可计算多边形表面在x=0和y=0平面上投影的面积,从而确定A,B,然后D可通过代入平面上一点坐标数值来求出。

; 若给出空间若干点的坐标(x1,y1,z1),(x2,y2,z2),….,(xn,yn,zn),注意这里没有要求这些点共面或围成了凸多边形,都可以求出通过或接近这些点的一个平面方程Ax+By+Cz+D=0:

式中若i=n,则j=1,否则j=i+1; 两平面重合或平行,没有交点;3.确定交线同时在两个多边形内部的部分

分别对每个多边形表面各边相应的线段,计算它与另一个多边形表面所在平面的交点。

注意：求线段（有限）与平面（无限）的交点,即交点在线段延长线上时算不相交。

假定两个多边形表面都是凸的,故共可以交出四个交点。

交得的四个交点可按x,y,z坐标字典式排序，中间两个交点的连线是两个多边形表面相交所得的线段。 ; 求线段（有限）与平面（无限）的交点

空间线段两个端点的坐标(x1,y1,z1)和(x2,y2,z2)给出,平面方程Ax+By+Cz+D=0。

;代入平面方程,得:

A(x1+(x2-x1)t)+B(y1+(y2-y1)t)+C(z1+(z2-zl)t)+D=0

整理得到:

[A(x2-x1)+B(y2-y1)+C(z2-zl)]t=-(Ax1+By1+Cz1+D)

若 A(x2-x1)+B(y2-y1)+C(z2-z1)=0

即(A,B,C)和(x2-x1,y2-y1