第三章 (计算机图形学基本图形算法之三)

计算机图形学基础

ComputerGraphics

赵东保

华北水利水电学院2011.9第三章基本图形算法（三）在计算机图形学中，经常需要处理一些共性的问题，如判断两条线段是否相交，它们的交点是多少；线段与面之间的位置关系；点是否落在面内，点与线段的位置关系等等，这些问题也是计算机图形学的基本问题。1概述既有大小又有方向的量，也称向量。其几何意义一般是指从起点指向终点的有向线段。矢量的加减法矢量的点乘：a·b=|a|·|b|·cos(a,b)矢量的叉乘：∣a×b∣=|a|·|b|·sin(a,b)

矢量的混合积：

(a×b)·c

2矢量3点与线的关系点在线上点在有向线的左侧点在有向线的右侧3点与线的关系利用向量的叉乘可以判断点与线的各种关系4点与面的关系点在面内的包含性检测空间一点是否在平面上5线与线的关系判断两条线段是否相交线段求交5线与线的关系若A，B分别在CD的两侧；C，D分别在AB的两侧则二者必相交退化情况5线与线的关系两线段的参数方程为：两线段的交点应满足：求得代入u,v可得交点坐标5线与线的关系三维空间中，怎样判断空间两线段是否相交，并求出交点参数方程求交三点构成面，判断另一点是否在面上，再转为二维平面上的判断线段是否相交向三个平面投影：5线与线的关系三维空间中，假定Z轴是深度方向，如何判断空间两线段是否相互遮挡？将两线段向XOY平面投影利用参数方程求两投影线段的交点，并获得参数λ，u。将参数λ，u代入Z方向的参数方程，获得深度，比较深度可判知遮挡关系6线与面的关系二维平面内，主要有如下关系：线段与面相交线段在面内线段与面相离6线与面的关系二维平面内，如何判断线段在面内？两个条件：（1）线段两端点都在面内（2）线段和多边形边不相交线段与多边形的交点如何求取？6线与面的关系三维空间内，如何判断线段与面的遮挡关系设线段的两端点为P1(x1,y1,z1)，P2(x2,y2,z2)平面方程：Ax+By+Cz+D=0令D1=Ax1+By1+Cz1+DD2=Ax2+By2+Cz2+D当D1(D2)<0

设N1(N2)=-2当D1(D2)=0

设N1(N2)=0当D1(D2)>0

设N1(N2)=1再令N=N1+N26线与面的关系则当N≤-2，线段在面的后面N=0，线段在面上；N=-1，线段贯穿面；N>0，线段在面之前。（N=1和N=2）6线与面的关系一条线段被一平面遮挡的判别原则如下：当N>0时，面不遮挡线段，不用进行比较；当N≤-2时，线段被面遮挡，两者在投影平面上的公共部份即为线段被面遮挡的部份；6线与面的关系当N=-1时，令λ=│D1│/(│D1│+│D2│)

若N2<0，则线段的[0,λ]间的部份在面的前面；6线与面的关系当N=0时，线段在面之上。此时线段在面的正面或在面的背面。若另两个端点中有一端点在面的前面，则此线段在

面的正面，可见；若另两端点均在面之后，此时线段在面的背面，需和此面比较，他们的投影公共部份即为棱的不可见部份。7面与面的关系

二维平面内，多边形的关系主要为多边形之间相交一个多边形在另一个多边形内多边形之间相离7面与面的关系三维空间内，如何判断多边形之间的遮挡关系？8射线求交射线与直线求交设直线方程为ax+by+c=0，射线方程为x=d1t+x0，y=d2t+y0。(t>0)

把射线方程代入直线方程有：

(ad1+bd2)t+ax0+by0+c=0若ad1+bd2=0，直线与射线平行若ad1+bd2不为零，可求得t=-(ax0+by0+c)/(ad1+bd2)若t<0，则无交点；t=0，直线与射线重合，t>0,则有交点。8射线求交射线与面求交假设面方程为ax+by+cz+d=0，再设射线方程为x=d1t+x0，y=d2t+y0，z=d3t+z0。(t>0)

把射线方程代入直线方程有：

(ad1+bd2+cd3)t+ax0+by0+cz0+d=0若ad1+bd2+cd3=0，射线与面平行若ad1+bd2+cd3不为零，可求得

t=-(ax0+by0+cz0+d)/(ad1+bd2+cd3)。若t<0，则无交点；t=0，射线与面重合，t>0,则有交点。9凸包的生成步1【找内点】：找到点集合的一个内点G，从内点作水平向右的一向量L；步2【排序】：连接内点和全部点列，根据这些连线与L的夹角按递增次序对点集排序，形成一个双向链接表；步3【求凸包上的起点】：求取点列中的任一个极点P0（X或Y的最小/大者）；9凸包的生成步4【求凸包上的一个顶点】：从P0出发依次考察连续的三个顶点，如果是向逆向转（图中实心圆点），则前进到下一点，否则删去三个顶点中的中间点（图中空心圆点），且后退到上一点；步5【求取凸包】：按步4遍历点表，其结果即为点集的有向凸包。这样求得的凸包是一个循环点列，选取任一个起点均可作为凸包的起点。逆向点顺向点10三角网剖分简单多边形的三角剖分离散点集的三角网剖分11点到线段的距离11点到线段的距离如何判断角度是锐角还是钝角如何计算点到直线的距离（1）构建直线方程，利用点到直线的距离公式求取距离。（2）计算向量叉乘，其结果的一半为三角形的面积，除以边长的2倍，即得高，就是要求的距离。思考：如何求线段与线段的距离？矩的定义对于二元有界函数f(x,y)，它的(j+k)阶矩为

集合{Mjk}对于函数f(x，y)是惟一的，也只有f(x，y)才具有这种特定的矩集。12几何矩1面积参数j＋k称为矩的阶。特别地，零阶矩是多边形的面积，即对二维离散函数f(x，y)，零阶矩可表示为

所有的一阶矩和高阶矩除以M00后，与多边形区域大小无关。

12几何矩2质心当j=1,k=0时，M10对多边形区域来讲就是多边形区域内所有点的x坐标的总和，类似地，M01就是多边形区域内所有点的y坐标的总和，所以

就是物体的质心的坐标。为了获得矩的不变特征，往往采用中心矩以及归一化的中心矩。中心矩的定义为3主轴使二阶中心矩从μ11变得最小的旋转角θ可以由下式得出：将x、y轴分别旋转θ角得坐标轴x′、y′