计算机科学与技术专业研究型课程 几 何 图 元 宋传鸣 chmsong@lnnu.edu.cn 辽宁师范大学计算机与信息技术学院

几何图元的表示 隐式表示 通过定义一个布尔函数f(x,y,z),如果所指定的点在找个图元上,找个布尔函数就为真;否则,该布尔函数为假 示例: x2+y2+z2=1 参数表示 示例: 如果函数只使用一个参数,则为单变量函数,否则称为多变量函数 单变量函数的轨迹是一条曲线,双变量函数的轨迹是一个曲面 表示方法 直线和射线 球和圆 矩形边界框 平面 三角形 多边形

直线、线段与射线 直线:向两个方向无限延伸 线段:直线的有限部分,有两个端点 射线:在计算机科学和计算几何中,射线是指有向线段 一条射线定义了一个位置、一个有限长度和一个方向(除非射线长度为0) 表示方法 直线和射线 球和圆 矩形边界框 平面 三角形 多边形

射线的表示 两点表示法 参数表示法 给出两个端点,即起点porg和终点pend 2D情形: 向量形式: 表示方法 直线和射线 球和圆 矩形边界框 平面 三角形 多边形

特殊的2D直线表示 直线的隐式定义(仅适用于2D情形) 斜截式 ax+by=d 延伸:令n=[a b],则p·n=d y=mx+b 表示方法 直线和射线 球和圆 矩形边界框 平面 三角形 多边形

不同表示方法间的转换 两点表示法向参数形式转换 参数形式向两点表示转换 射线的参数形式向包含该直线的隐式形式转换 直线隐式到斜截式的转换 p0 = porg d = pend－porg 参数形式向两点表示转换 porg = p0 pend = p0+d 射线的参数形式向包含该直线的隐式形式转换 a=dy b=－dx d=porgxdy － porgydx 直线隐式到斜截式的转换 m= － a/b b=d/b 表示方法 直线和射线 球和圆 矩形边界框 平面 三角形 多边形

不同表示方法间的转换 直线隐式到标准向量+距离形式的转换 表示方法 直线和射线 球和圆 矩形边界框 平面 三角形 多边形

不同表示方法间的转换 球的隐式表示法 球的参数表示法 球的表面积 球的体积 ||p－c||=r, c表示圆心,r表示圆半径 (x－cx)2+(y－cy)2+(z－cz)2=r2 球的参数表示法 x(a,b)=rsin(a)cos(b) y(a,b)=rsin(a)sin(b) z(a,b)=rcos(a) 球的表面积 S=4πr2 球的体积 V=4πr3/3 表示方法 直线和射线 球和圆 矩形边界框 平面 三角形 多边形

轴对齐矩形边界框(Axially Aligned Bounding Box) 矩形边界框:用来界定物体的几何图元 与轴对齐:边必须垂直于坐标轴,缩写为AABB 任意方向:方向矩形边界框,缩写为OBB (Oriented Bounding Box) 一个3D的AABB就是一个简单的六面体,每一边都平行于一个坐标平面 表示方法 直线和射线 球和圆 矩形边界框 平面 三角形 多边形

AABB的表达方法 AABB内的点满足下列不等式 重要顶点 中心点c 尺寸向量s:从pmin指向pmax的向量 xmin≤x≤xmax , ymin≤y≤ymax , zmin≤z≤zmax 重要顶点 pmin= [xmin ymin zmin], pmax= [xmax ymax zmax] 中心点c c = (pmin + pmax)/2 尺寸向量s:从pmin指向pmax的向量 s = pmax－ pmin 半径向量r:从中心指向pmax的向量 r = pmax－ c = s/2 明确定义一个AABB只需要pmin, pmax, c, s, r这5个向量中的两个 建议用pmin和pmax表示一个边界框 表示方法 直线和射线 球和圆 矩形边界框 平面 三角形 多边形

AABB与边界球 例子: AABB与边界球的比较 计算一个点集的AABB在编程上更容易实现 表示方法 直线和射线 球和圆 矩形边界框 平面 三角形 多边形

AABB的计算和变换 计算一个顶点集的AABB: 变换AABB:当物体在虚拟世界中移动,其AABB也需要随之移动 先将最小值和最大值设为正负无穷大或任何比实际中用到的数都大或小得多的数 然后遍历全部顶点集,并扩展边界框直到它包含所有顶点为止 变换AABB:当物体在虚拟世界中移动,其AABB也需要随之移动 用变换后的物体来重新计算AABB 对AABB做和物体同样的变换 该方法比前一方法更快,AABB只有8个顶点 所得结果不一定是轴对齐的 表示方法 直线和射线 球和圆 矩形边界框 平面 三角形 多边形

AABB的计算和变换 变换AABB的计算方法 目标:最小化乘积 3D顶点的变换过程 有 如果m11>0,用xmin能得到最小化乘积 如果m11<0,用xmax能得到最小化乘积 其余各个坐标同理 表示方法 直线和射线 球和圆 矩形边界框 平面 三角形 多边形

平面的表示 隐式定义 ax+by+cz=d 令p=(x,y,z), n=(a,b,c), 则有p·n=d. 其中n称为平面的法向量 表示方法 直线和射线 球和圆 矩形边界框 平面 三角形 多边形

平面的表示 用三个点定义 选择平面上不共线的三个点p1,p2和p3来计算n和d 在左手坐标系下:以顺时针顺序列出三个点 在右手坐标系下:以逆时针顺序列出三个点 以顺时针方向构造向量为例 e3 = p2 － p1 e1 = p3 － p2 表示方法 直线和射线 球和圆 矩形边界框 平面 三角形 多边形

平面的表示 多于三个点的“最佳”平面:从一组三个以上的点集求出平面方程(顶点绕多边形顺时针列出) 任选三个连续的顶点 所选的三个顶点有可能共线,或者接近共线 由于数值的不精确,多边形上的顶点可能不共面 设给定n个点: p1=(x1,y1,z1), p2=(x2,y2,z2), … , pn-1=(xn-1,yn-1,zn-1), pn=(xn,yn,zn),则最佳的法向量为 表示方法 直线和射线 球和圆 矩形边界框 平面 三角形 多边形

平面的表示 多于三个点的“最佳”平面:从一组三个以上的点集求出平面方程(顶点绕多边形顺时针列出) 任选三个连续的顶点 所选的三个顶点有可能共线,或者接近共线 由于数值的不精确,多边形上的顶点可能不共面 设给定n个点: p1=(x1,y1,z1), p2=(x2,y2,z2), … , pn-1=(xn-1,yn-1,zn-1), pn=(xn,yn,zn),则最佳的d值 表示方法 直线和射线 球和圆 矩形边界框 平面 三角形 多边形

点到平面的距离 一个平面和一个不在平面上的点q,计算q到平面的距离 p+an = q (p+an) ·n = q·n p·n + (an) ·n = q·n d+a = q·n a= q·n－d 表示方法 直线和射线 球和圆 矩形边界框 平面 三角形 多边形

三角形的基本性质 在左手坐标系下,当从三角形正面看时,经常以顺时针方向列出三个顶点 正弦公式 余弦公式 表示方法 直线和射线 球和圆 矩形边界框 平面 三角形 多边形

三角形的基本性质 面积 3D情况下,可通过向量积计算面积 底*高/2 如果不知道高,可使用海伦公式 表示方法 直线和射线 球和圆 矩形边界框 平面 三角形 多边形

三角形的面积 2D情况下,可用更为简单的办法计算面积 基本思想:对三角形三边中的每一边,计算上由该边、下由x轴所围成的梯形的有符号面积 有符号面积:如果边的端点是从左向右的,则面积为正;否则,面积为负.竖直边的面积为0 表示方法 直线和射线 球和圆 矩形边界框 平面 三角形 多边形

三角形的面积 2情况下,可用更为简单的办法计算面积 平移三角形不会改变三角形的面积 表示方法 直线和射线 球和圆 矩形边界框 平面 三角形 多边形

三角形的重心坐标空间 三角形所在平面的任意点都能表示为顶点的加权平均值,这个权称为重心坐标 从重心坐标(b1,b2,b3)到标准3D坐标的转换: (b1,b2,b3) →b1v1+b2v2+b3v3 b1+b2+b3=1 示例 表示方法 直线和射线 球和圆 矩形边界框 平面 三角形 多边形

三角形的重心坐标空间 注意事项 三角形各顶点的重心坐标(b1,b2,b3)都是单位向量 在某顶点的相对边上的所有点对应重心坐标分量都为0 不只是三角形内的点,该平面上的所有点都能用重心坐标描述 重心坐标是有冗余的,仅用两个坐标即可计算出第三个坐标 表示方法 直线和射线 球和圆 矩形边界框 平面 三角形 多边形

三角形的重心坐标空间 由2D坐标向重心坐标转换 已知三个顶点的坐标和点P的笛卡尔坐标,则有 解该方程组,得 表示方法 直线和射线 球和圆 矩形边界框 平面 三角形 多边形

三角形的重心坐标空间 由2D坐标向重心坐标转换 对照上述公式可以发现 重心坐标等于各个子三角形与原三角形的面积比 表示方法 直线和射线 球和圆 矩形边界框 平面 三角形 多边形

三角形的重心坐标空间 由3D坐标向重心坐标转换 方程组过定:三个未知数,四个方程 p可能不在三角形所在的平面中,重心坐标无意义 方法一: 向某一个投影平面做投影,抛弃x,y,z中的一个分量.根据法向量,抛弃绝对值最大的坐标 方法二:用向量积计算原三角形和各个子三角形的面积,再计算面积比 由于向量积的大小总是正的,该方法不适用于三角形外的点 方法三:向量内积.设c为三角形两边的向量积,c的大小等于三角形面积的两倍,n为三角形的单位法向量,有 表示方法 直线和射线 球和圆 矩形边界框 平面 三角形 多边形

三角形的重心坐标空间 由3D坐标向重心坐标转换 表示方法 直线和射线 球和圆 矩形边界框 平面 三角形 多边形

三角形的重心 重心是三角形三条中线的交点,是三角形的最佳平衡点 重心的坐标是三个顶点的几何均值,对应的重心空间下的坐标为(1/3,1/3,1/3) 表示方法 直线和射线 球和圆 矩形边界框 平面 三角形 多边形

三角形的内心 内心是到三角形各边距离相等的点,也是三角形内切圆的圆心,也是角平分线的交点 内心的坐标是 内心对应的重心空间坐标为 内切圆的半径等于三角形的面积除以三角形的周长 内切圆解决了寻找与三条直线相切的圆的问题 表示方法 直线和射线 球和圆 矩形边界框 平面 三角形 多边形

三角形的外心 外心是到三角形各顶点距离相等的点,是三角形外接圆的圆心,也是各边垂直平分线的交点 外心坐标的计算 外心坐标为: 外接圆半径为: 外心和外接圆半径解决寻找过三个点的圆的问题 表示方法 直线和射线 球和圆 矩形边界框 平面 三角形 多边形

简单多边形与复杂多边形 简单多边形不包含洞,复杂多边形可能含洞 简单多边形可以通过沿着多边形列出所有顶点来描述 表示方法 直线和射线 球和圆 矩形边界框 平面 三角形 多边形

简单多边形与复杂多边形 通过添加一对接缝边,能将任意复杂多边形转化成简单多边形 相邻的接缝边方向相反 表示方法 直线和射线 球和圆 矩形边界框 平面 三角形 多边形

自交多边形 多边形的边存在自相交 大多数时间处理的都是非自相交多边形 表示方法 直线和射线 球和圆 矩形边界框 平面 三角形 多边形

凸多边形与凹多边形 几何上的定义 实践中的定义 凸多边形中,任意两顶点的连线都包含在多边形中 沿着凸多边形周边移动时,在每个顶点的转向都是相同的 实践中的定义 如果只能对凸多边形起作用的代码对某个多边形也能起作用,那么它就是凸多边形 如果凸性测试算法判定他是凸的,那么它就是凸的 表示方法 直线和射线 球和圆 矩形边界框 平面 三角形 多边形

凸多边形的判断 角度和的方法:将每个顶点处较小的角相加,凸多边形得到(n－2)180度,而凹多边形则小于该数值 凸性检测:用相邻的两个边向量计算该顶点的法向量,接着用多边形的法向量和顶点的法向量求内积.如果内积为负数,那么该顶点就是一个凹点 表示方法 直线和射线 球和圆 矩形边界框 平面 三角形 多边形

多边形的三角剖分 扇形分解:选取一个点,沿着顶点按扇形分解多边形 可能出现比较细的三角形,进而引起数值计算的问题 连接两顶点的对角线将一个多边形分解为两部分,对角线端点处的两个内角分解为4个内角.选择能使四个内角中最小的角最大化的对角线 表示方法 直线和射线 球和圆 矩形边界框 平面 三角形 多边形