发布时间 : 星期三 文章计算机图形学各种算法的作业（偏于理论）更新完毕开始阅读d669a0c2d5bbfd0a795673b5
LH计算机图形学作业：共九道题
u?(C?E)?D?(C?E)?A
(C?E)?B(B?E)?D?(B?E)?A
(B?E)?C??如果是直线与平面区域求交点，则要进一步判断点是否在平面上的有效区域中，其算法可参见4.2节。
2、圆锥曲线与平面的交点
圆锥曲线与平面求交时，可以把圆锥曲线表示为参数形式，并把圆锥曲线的参数形式代入平面方程，即可得到参数的二次方程进行求解。
3、圆锥曲线与二次曲面的交点
圆锥曲线与二次曲面求交时，可把圆锥曲线的参数形式代入二次曲
面的隐式方程，得到参数的四次方程，用求根公式求解。 4.2 求交线算法
求交线显然是指求面与面的交线，下面讨论几种常见的情况。 1、平面与平面的交线
在CAD中一般使用平面上有界区域。先考虑最简单的情形。两个平面区域分别由P?u,w定如果它们不共面而且不分 Q?s,t, u?, ?w, ?s, 义t 。0, 1?,?离，则必交于一直线段。这条直线必落在P?u,w?-Q?s,t?=0所定义的无限直线上。注意这是个含有四个未知数，三个方程式的方程组，只要分别与八条边界线方程：u=0, u=1, w=0, w=1, s=0, s=1, t=0, t=1联立，即可求出线段的两个端点的参数。在上述方程组中，只要找到两组解，就可以不再对剩余其它方程组求解。找到的两组解就是所求的交线段端点参数。
当两个一般的多边形（即既可能是凸的，也可能是凹的，甚至可能带有内孔）相交时，可能有多段交线。我们可以把两个多边形分别记为A和B，用如下的算法求出它们的交线：
（1）把A的所有边与B求交，求出所有有效交点； （2）把B的所有边与A求交，求出所有有效交点； （3）把所有交点先按y，再按x的大小进行排序；
（4）把每对交点的中点与A和B进行包含性检测，若该中点即在A中又在B中，则该对交点定义了一条交线段。
2、平面与二次曲面的交线
求平面与二次曲面的交线有两种方法：代数法和几何法。
19
LH计算机图形学作业：共九道题
用代数法考虑平面与二次曲面求交问题时，可以把二次曲面表示为代数形式：
Ax2+By2+Cz2+2Dxy+2Eyz+2Fxz+2Gx+2Hy+2Iz+J=0
可以通过平移与旋转坐标变换把平面变为XOY平面，对二次曲面进行同样的坐标变换。由于在新坐标系下平面的方程为z?0，所以新坐标系下二次曲面方程中，把含z项都去掉即为平面与二次曲面的交线方程（在新坐标系下）。对该交线方程进行一次逆坐标变换即可获得在原坐标系下的交线方程。在具体实现时，交线可以用二元二次方程系数表示（代数表示），辅之以局部坐标系到用户坐标系的变换矩阵。这种方法的缺点是，每当需要使用这些交线时，都要进行坐标变换。例如，判断一个空间点是否在交线上，必须先对它进行坐标变换，变到z?0平面上，再进行检测。需要绘制该交线时，也要先在局部坐标系下求出点坐标，再变换到用户坐标系下的坐标。所以交线采用另一种方法（几何表示）更合理。几何方法存储曲线的类型（椭圆、抛物线或双曲线），以及定义参数（中心点、对称轴、半径等大小尺寸）的数值信息，使用局部坐标系到用户坐标系的变换，把局部坐标系下的定义参数变换到用户坐标系直接使用。这第二种方法使用较少的变换，但需要用计算来判断曲线的种类，及计算曲线的定义参数。由于浮点运算的不精确性，容易发生判错类型以及定义参数误差过大的问题。
当平面与二次曲面的交线需要精确表示时，往往采用几何法求交。二次曲面采用几何表示，平面与二次曲面求交时，根据它们的相对位置与角度（根据定义参数），直接判断交线类型，其准确性大大优于用代数法计算分类的方法。几何法不需要对面进行变换，所以只要通过很少的计算就可以得到交线的精确描述。由于存储的信息是具有几何意义的，所以判断相等性、相对性等问题时，可以确定有几何意义的容差。下面以平面一球求交为例，说明几何法求交算法。
平面用一个记录p表示，p的两子域p.b, p.w分别代表平面上一点与平面法向量。球面用记录s表示。它的两个子域s.c, s.r分别代表球面中心和半径。则可写出平面与球面相交的算法如下： plane_sphere_intersect(p, s) plane p; sphere s; {
20
LH计算机图形学作业：共九道题
d=球面中心到平面的有向距离； if(abs(d)=s.r)
{ 二个面相交于一（切）点s.c-d * p.w;} else if (abs(d)>s.r) { 两个面无交；} else
{ 所求交线是圆。其圆半，半径，圆所在平面法向量为 c=s.c-d * p. w; r=sqr t(s.r2-d2); w=p.w; } }
一个平面与一个圆柱面可以无交、交于一条直线（切线）、二条直线、一个椭圆或一个圆，可以用两个面的定义参数求出它们的相对位置关系和相对角度关系，进而判断其交属于何种情况，并求出交线的定义参数。平面与圆锥的交线也可类似求出。
3、平面与参数曲面的交线
最简单的方法是把参数曲面的表示（x?s,?t,? y?s,?t,代s入 z,t平面方?）程
ax+by+cz+d=0
得到用参数曲面的参数s、t表示的交线方程
ax?s,t?+by?s,t?+cz?s,t?+d=0
另一种方法是用平移和旋转变换对平面进行坐标变换，使平面成为新坐标系下的xoy平面。再用相同的变换应用于参数曲面方程得到参数曲面在新坐标系下的方程
（x*, y*, z*）=（x*?s,t?, y*?s,t?, z*?s,t?）由此得交线在新坐标系下的方程为z*?s,t??0。 4.3 包含判定算法
在进行图形求交时，常常需要判定两个图形间是否有包含关系。如点是否包含在线段、平面区域、三维形体中，线段是否包含在平面区域、三维形体中，等等。许多包含判定问题可转化为点的包含判定问题，如判断线段是否在平面上可以转化为判断其两端点是否在平面上。因此下
21
LH计算机图形学作业：共九道题
面主要讨论关于点的包含判定算法。
判断点与线段的包含关系，也就是判断点与线的最短距离是否位于容差范围内。造型中常用的线段有三种：
1、直线段；
2、圆锥曲线段（主要是圆弧）；
3、参数曲线（主要是Bezier，B样条与NURBS曲线）。 点与面的包含判定也类似地分为三种情况。下面分别讨论。 1、点与直线段的包含判定
假设点坐标为P?x,y?，P2?x2,y2,z2?，则,，z直线段端点为P1?x1,yz1,?1点P到线段PP12的距离的平方为
d2??x?x1???y?y1???z?z1?222??x2?x1??x?x1???y2?y1??y?y1???z2?z1??z?z1???? ???x2?x1?2??y2?y1?2??z2?z1?2???2当d2?0时，认为点在线段（或其延长线）上，这时还需进一步判断点是否落在直线段的有效区间内。只要对坐标分量进行比较，假设线段两端点的x分量不等（否则所有分量均相等，那么线段两端点重合，线段退化为一点），那么当x?x1与x?x2反号时，点P在线段的有效区间内。
2、点与圆锥曲线段的包含判定
以圆弧为例，假设点的坐标为?x, y, z?，圆弧的中心为（x0, y0, z0），半径为r，起始角?1，终止角?2。这些角度都是相对于局部坐标系x轴而言。圆弧所在平面为
ax+by+cz+d=0
先判断点是否在该平面上，若不在，则点不可能被包含。若在，则通过坐标变换，把问题转换到二维的问题。
给定中心为（x0, y0），半径为r，起始角?1，终止角?2的圆弧，对平
（x, ）y面上一点P，判断P是否在圆弧上，可分二步进行。
第一步判断P是否在圆心为（x0, y0），半径为r的圆的圆周上，即下式是否成立：
(x?x0)2?(y?y0)2?r??
第二步判断P是否在有效的圆弧段内。 3、点与参数曲线的包含判定
设点坐标为P?x, y?,，参 z数曲线为Q?t?=?x?t?, y?t?, z?t??。点也参数曲
22