游戏数学基础教程 教学课件 ppt 作者 房晓溪 第五章 空间几何体

《游戏数学基础教程 教学课件 ppt 作者 房晓溪 第五章 空间几何体》由会员分享，可在线阅读，更多相关《游戏数学基础教程 教学课件 ppt 作者 房晓溪 第五章 空间几何体（69页珍藏版）》请在金锄头文库上搜索。

1、第5章空间几何体,主要内容,表达图元的一般方法 直线和射线 球和圆 包围盒 平面 三角形 多边形,表达方法,讨论一般的表达方法，如方程、参数形式等 任意图元都可以使用这些方法中的一种或多种 不同情况下不同方法更加合适,隐式表示,定义一个布尔函数f（x，y，z），能够隐含的表达一个图元 对于在这个图元上的点，布尔函数为真；对于所有其它点，布尔函数为假 例如，等式 对中心在原点的单位球表面上的所有点为真,参数形式,图元也能以参数形式表达，看一个简单的2D例子 ，定义如下两个t的函数： t被称作参数，和所用的坐标系不相关 当t从0到1变化时，点（x（t），y（t）的轨迹就是所要描述的形状,参数形式,

2、一个参数的轨迹是一个曲线 两个参数的轨迹是一个曲面,“直接”形式,因为没有更好的术语，所以将这组表达方法命名为“直接” 方法 它们随图元的类型而变化，经常是直接抓住图元最本质和最明显的信息 例如，为了表达一个线段，给出两个端点。对于一个球，给出什么？,球心和半径,自由度,每个图元都有一个与生俱来的数字：自由度 无歧义地描述该实体所需信息量的最小数目 同一几何图元，不同表达方式的自由度不同,直线和射线,在经典几何中，使用下列定义： 直线向两个方向无限延伸 线段是直线有限的一部分，有两个端点 射线是直线的“一半”，有一个起点并向一个方向无限延伸,我们稍微修改“射线”的定义 射线就是有向线段 这样，

3、一条射线定义了一个位置，一个有限长度和一个方向 任何射线也定义了包含这个射线的一条直线和线段 射线在计算几何和图形学中占有非常重要的位置,两点表示法,描述射线最明显的方法是给出两个端点：起点p起点和终点p终点,射线的参数形式,2D和3D射线都能用参数形式表达 2D射线的参数形式使用两个函数： 3D射线是一种直接扩展，只需再加第三个函数z（t）。参数t的范围为0到1。,射线的参数形式,向量记法能使射线的参数形式更加紧凑 在任意维中表达射线都可以用这种形式： 射线的起点 增量向量d包含了它的 长度和方向 射线的终点,直线的特殊2D表示,2D中，可以使用下式隐含的表达直线： 另一种方式：设向量na，

4、b，向量记法为： 再换一种方法，变换等式将直线表示为斜距式：,m是直线的“斜率”：等于rise和run的比值 b是y截距：直线和y轴交于yb,当斜率等于0时，不能使用斜截式表示,另一种描述直线的方法是给出垂直于直线的标准向量n和原点到直线的垂直距离d 标准向量描述了直线的方向，距离则描述了位置,另一种变形是用直线上的点来描述直线的位置而不是用原点到直线的距离。 当然，直线上的任意点都可以。 直线的方向仍然用垂直于直线的标准向量n表示,最后一种定义是将直线作为两个点q和r的垂直平分线 这也是直线最早的一种定义：到两个给定点距离相等的点的集合。,在不同表示方法间转换,从射线的两点定义式转换到参数形

5、式： 相反的转换，从参数形式转换到两点定义式,在不同表示方法间转换,给定一条参数射线，能够从中计算出包含该射线的直线的隐格式： 其它转换,球和圆,球是一种3D物体，定义为到给定点有给定距离的点的集合 球的直接表达方式是给出球心c和半径r 球的隐格式由它的定义直接导出，球心为c，半径为r的球的隐格式为,球和圆,“包围球”经常用于相交性测试中 因为检验与一个球是否相交是非常简单的。 因为旋转一个球并不会改变它的形状，所以使用包围球时不必考虑物体的方向 圆和球的直径 圆的面积：,球和圆,球的表面积： 球的体积：,圆面积的微分是圆周长；球体积的微分是球表面积。,包围盒,用来包围物体的几何图元是包围盒

6、轴对齐 任意方向 轴对齐的包围盒（axially aligned bounding box ） 它的边必须垂直于坐标轴 常用缩写AABB来表示 轴对齐包围盒容易创建，易于使用,一个3DAABB就是一个简单的六面体，每一边都平行于一个坐标平面 包围盒不一定是立方体，它的长、宽、高可以彼此不同,表达AABB,特别重要的两个顶点为： AABB内的点满足下列不等式,中心点c为： “尺寸向量”s为： 还可以求出盒子的“半径向量”r,无歧义的描述一个AABB只需要上面五个向量中的两个，除s 和r不能配对外 建议用 和 表示一个包围盒，因为实际应用中，使用它们的频率远高于c，s ，r 从它们计算这三个中的任

7、意一个都是很快的 public: Vector3 min; Vector3 max;,计算AABB,计算一个点的集合的AABB是非常简单的：先将最小值和最大值设为“无限”或任何比实际中用到的都大得多的数。接着，遍历整个点的列表，扩张包围盒直到包含每个点。 引入了两个辅助函数，第一个函数“清空”AABB： void AABB3:empty() const float kBigNumber = 1e37f; min.x = min.y = min.z = kBigNumber; max.x = max.y = max.z = -kBigNumber; ,第二个函数将单个点“加”到AABB中，必要的

8、时候扩张AABB以包含这些点： void AABB3:add(const Vector3 ,从一个点集中创建包围盒，可以使用下面这样的代码： / 点的列表 const int n; Vector3 listn; / 首先，清空包围盒 AABB3 box; box.empty(); / 将点添加到包围盒中 for (int i = 0 ; i n ; +i) box.add(listi); ,AABB VS 包围球,很多情况下，AABB的表现要比包围球的好 计算点集的AABB，在编程上更容易，并能在线性时间内完成。计算包围球则是一件困难得多的任务 对实际中的许多物体，AABB提供了一种“更紧”的

9、包围。 对于某些物体，包围球更好（设想一个本身就是球的物体！）。 在最坏的情况下，AABB的体积也小于包围球体积的两倍。 比较电线杆的包围球和AABB,包围球的根本问题是它的形状只有一个自由度半径 AABB有三个自由度长、宽、高，它可以调节以适应不同形状的物体,AABB对物体的方向很敏感,变换AABB,物体在虚拟世界中移动时，它的AABB需要跟着移动 变换后物体的AABB？ 有两个选择 从变换后的物体，物体重新计算AABB 对AABB做和物体同样的变换 计算“变换后AABB”的AABB比从变换后的物体重新计算AABB快得多，因为AABB只有八个点,从“变换后的AABB” 计算不能只是简单地变换

10、八个顶点 也不能通过转换原来的最大点和最小点来得到新的最大点和最小点 先变换八个顶点，再从这八个顶点中计算一个新的AABB,新AABB几乎是原来的两倍,平面,3D中，平面是到两个点距离相等的点的集合 平面完全是平的，没有厚度，且无限延伸,平面方程隐格式,可以用类似定义直线的方法定义平面 平面的隐格式由所有满足平面方程的点p（x，y，z）给出，平面方程的两种记法如下：,向量n称作平面的法向量，它垂直于平面 平面有“正面”和“反面”，一般来说，n指向的方向是平面的正面 经常将n限制为单位长度,用三个点定义,另一种定义平面的方法是给出平面上不共线的三个点 从平面上的三个点 ， 和 中计算n和d 先计

11、算n，n指向什么方向呢？ 左手坐标系中的标准是：从平面的正面看时假设 ， 和 以顺时针方向列出 右手坐标系中假设这些点以逆时针方向列出，这样，不管使用什么坐标系公式相同,以顺时针方向构造两个向量 两个向量的叉乘结果就是n，但可能不是单位向量，标准化即可 得到n，任意点点乘n即为d,多于三个点的“最佳”平面,怎么从多于三个点的点集中求出平面方程 任意选择三个点计算平面方程的缺点 三个点共线或接近共线 凹多边形导致法向量方向错误 顶点可能不共面 从点集中求出最佳平面，该平面综合考虑了所有的点,点到平面的距离,设想一个平面和一个不在平面上的点q 平面上存在一个点p，到q的距离最短。很明显，从p到q的

12、向量垂直于平面，且形式为an,设n为单位向量，那么p到q的距离（也就是q到平面的距离）就是a 不用知道p的位置就能计算出a,三角形,三角形在建模和图形学中有着极其重要的位置 复杂3D物体的表面，如车或人体，都是用三角形模拟的 像这样一组相连的三角形称作三角网格,基本性质,三角形通过列出它的三个顶点定义 这些点列出的顺序是非常重要的，在左手坐标系中，当从三角形“正面”看时，经常以顺时针方向列出这些点,基本性质,一个三角形在一个平面中，这个平面的方程（法向量n和到原点的距离d）在很多应用中非常重要 ，怎样从给定的三个点中计算平面方程 ，参考前面的内容,面积,最经典的方法是从底和高计算面积 由底和高

13、给出的三角形面积公式为：,面积,如果高不知道，可以使用海伦公式计算面积，它只需要三边的长度 海伦公式非常有用，因为它在3D中使用非常方便。,有时候，高和周长都没有直接提供，所知道的只有顶点的笛卡儿坐标 当然，总是可以从坐标中算出边长，但某些情况下，我们想要避免这种相对昂贵的计算 能否从顶点坐标直接计算面积 ？,先在2D中解决这个问题。基本思想是，对三角形三边中的每一边，计算上由该边下由x轴围成的梯形的有符号面积 “有符号面积”是指如果边的端点从左向右则面积为正，如果边的端点从右向左则面积为负,注意不管三角形的方向如何变化，都存在至少一个正边，一个负边，竖直边的面积为0，每一边下的面积公式为：

14、这三个梯形的有符号面积相加，就得到了三角形本身的面积,3D中，可以使用叉乘计算三角形的面积 两向量a，b叉乘的大小等于以a，b为两边的平行四边形的面积。因为三角形面积等于包围它的平行四边形的一半，所以我们有了一种简便方法 给出三角形的两边向量，三角形面积为：,重心坐标系,虽然我们经常在3D中使用三角形，但三角形表面是一个平面，它天生是一个2D物体 3D中在任意朝向的三角形表面上移动是一件令人烦恼的事。最好是有一个坐标系与三角形表面相连且独立于三角形所在的3D坐标系 重心坐标系正是这样的坐标系,三角形所在平面的任意点都能表示为顶点的加权平均值，这个权称作重心坐标 从重心坐标（ ， ， ）到标准3

15、D坐标的转换为： 重心坐标的和总是1：,， 和 的值是顶点对该点的“贡献”或“比重”,三角形的3个顶点的重心坐标都是单位形式的 某顶点的相对边上的所有点，这些点所对应的重心坐标为0 三角形所在平面的所有的点都可以用重心坐标描述,重心坐标系是2D的，本质上不同于笛卡尔坐标系，它使用了3个坐标，并且坐标的和等于1 重心坐标系仅有两个自由度，有一个冗余 重心坐标系中仅用两个数就能描述一点，另一个可以由这两个计算得到。,转换,为了将重心坐标转换到平常的3D坐标，只需要应用公式计算顶点重力均值就可以了 计算2D或3D中任意一点的重心坐标稍微复杂一些 先看2D中的方法,它展示了三个顶点和点p 还标出了三个

16、“子三角形”,现在，我们知道三个顶点和点p的笛卡儿坐标，任务是计算重心坐标 ， 和 这给了我们三个等式和三个未知数,解这个方程组得：,仔细观察上式，发现每个表达式中的分母相同，并且都等于三角形面积的两倍。还有，对每个重心坐标i，分子等于i“子三角形”面积的两倍 ，即,3D中,1）可以抛弃某个坐标投影到一个平面上，转换到2D中（p265） 2）叉乘 求Ti,T 缺点：对方向不敏感，始终为正 改善：使用点乘 设c为三角形两边向量的叉乘，2S n为法向量 则：c/n-c.n=|c|n|cosa =|c|(+/-1) =+/-|c| T=1/2c.n,特殊点,重心 中线交点 重心坐标为（1/3，1/3，1/3） 重心是三角形的最佳平衡点 重心是三个顶点的几何