3D数学基础第12章几何图元课件

第12章几何图元表示图元的一般方法直线和射线表示方法不同的表示方法之间的转换球和圆的表示方法矩阵边界框（重点介绍AABB）AABB的表示方法计算AABBAABB与边界球的比较变换AABB第12章几何图元平面平面的表示方法点到平面的距离三角形基本性质面积重心坐标空间三角形的重心、内心、外心多边形多边形的定义凸多边形的判定方法多边形的分解12.1图元的表示方法隐式表示定义一个布尔函数f(x,y,z)，如果所指定的点在图元上，布尔函数为真；不在图元上，则布尔函数为假。例：x2+y2+z2=1隐式表示法可用于测试图元是否包含某点12.1图元的表示方法参数形式表示()()xxtyyt图元上任意一点的坐标x,y都是某个变量t（参变量）的函数，且对于t每一个允许值，由方程组所确定的点都在这个图元上参变量t从0变化到1时，点(x(t),y(t))的轨迹就是所要描述的图元的形状。,[0,1][0,],tttll实际上参变量可在任意范围内变化，但为了方便，多数情况下。也可使为图元的长度12.1图元的表示方法参数形式表示单参变量形式cos2sin2xtyt单参变量方程组表示的轨迹是一条曲线12.1图元的表示方法参数形式表示双参变量形式(,)(,)xxstyyst双参变量方程组表示的轨迹是一个曲面“直接”形式表示“直接”形式表示方法随图元的类型而变化，能直接体现图元最本质和最明显的信息例：用两个端点表示一个线段用球心和半径表示一个球12.1图元的表示方法几何图元的固有属性——自由度自由度是无歧义地描述该实体所需信息量的最小数目同一几何图元，不同表示方法所用到的自由度是不同的多余的自由度数量是由于图元参数化中的冗余造成的，这些冗余可以通过一些适当的假设条件来消除例：定位一个点需要两个参数：点的x坐标和y坐标，因此点的自由度为212.2直线和射线直线、线段、射线的定义直线向两个方向无限延伸射线定义了一个位置、一个有限长度、一个方向（当射线长度非零时）线段是直线的有限部分，有两个端点射线是有向线段12.2直线和射线射线的表示方法两点表示法给出射线的两个端点：起点porg和终点pend射线的参数形式2D射线的参数形式3D射线的参数形式000()()()xtxtxytytyztztz:01t00()()xtxtxytyty12.2直线和射线射线的表示方法两点表示法给出射线的两个端点：起点porg和终点pend射线的参数形式射线参数形式的向量记法0()ptptd射线的起点，指定了射线的位置信息。p0=p(0)增量向量，指定了射线的长度和方向0(1)ppd12.2直线和射线射线的表示方法两点表示法给出射线的两个端点：起点porg和终点pend射线的参数形式射线参数形式的向量记法的变形0()ptptdd:单位向量t:0→ll:射线的长度12.2直线和射线2D直线的表示方法2D直线的隐式定义隐式定义axbyd2D直线隐式定义的向量记法pnd两边同时乘以k()()pknkd•记法knd当等式两边同乘以常数时,和会发生变化但并不会改变直线的定义为方便起见,常用单位向量12.2直线和射线2D直线的表示方法2D直线的隐式定义2D直线隐式定义的向量记法•几何解释n:垂直于直线的单位向量，描述了直线的方向d:原点到直线的有符号距离，描述了直线的位置有符号距离：如果直线和标准向量n代表的点在原点的同一侧，则d为正。当d增大时，直线沿方向n移动12.2直线和射线2D直线的表示方法2D直线的隐式定义向量记法的变形用直线上的点来描述直线的位置，直线的方向仍然用垂直于直线的标准向量n表示12.2直线和射线2D直线的表示方法2D直线的斜截式定义ymxb水平直线斜率为0竖直直线斜率为无穷大，不能用斜截式表示。竖直直线的隐式表示：x=k12.2直线和射线2D直线的表示方法将直线作为两个点q和r的垂直平分线12.2直线和射线在不同表示方法间转换直线的不同表示方法间转换隐式→斜截式隐式→标准向量+距离标准向量+直线上的点→标准向量+距离/,/mabbdb2222[]/+,/nababdistancedab,nndistancenq12.2直线和射线在不同表示方法间转换直线的不同表示方法间转换垂直平分线→隐式12.2直线和射线射线的不同表示方法之间转换两点定义式→参数形式0,orgendorgppdpp参数形式→包含该射线的直线的隐式,yxyxorgxorgyadbddpdpd参数形式→两点定义式00,+orgendppppd12.3球和圆球直接表示法给出球心和半径隐式表示的向量记法pcr隐式表示2222()()()xyzxcyczcr球的表面积和体积234=4,3SrVr12.3球和圆圆圆的直径和周长圆面积=22DrCrD2=Ar12.4矩形边界框矩形边界框的分类矩形边界框是一个简单的六面体,常用来界定物体AABB(axiallyalignedboundingbox)轴对齐矩形边界框OBB(orientedboundingbox)方向矩形边界框重点介绍12.4矩形边界框界定物体的目的——碰撞检测碰撞检测的基本任务是确定虚拟空间中两个或多个物体彼此之间是否发生接触，避免物体之间在运动过程中发生穿透等现象。AABB(axiallyalignedboundingbox)轴对齐矩形边界框OBB(orientedboundingbox)方向矩形边界框典型的包围盒算法：常用的碰撞检测技术——层次包围盒12.4矩形边界框Sphere(包围球）K-DOPs(k-DiscreteOrientationPolytopes)K-DOPs包围盒是一种凸多面体，它的面由一些半空间所确定，这些半空间的外法向是从k个固定的方向中选取的。K-DOPs可以看作是AABB的扩展，它不但继承了凸包紧密性好的优点，同时也继承了AABB简单性好的优点，通过调整固定方向集合的大小和取值，可以在紧密性和简单性之间达到一定的折衷。常用的碰撞检测技术——层次包围盒典型的包围盒算法：（继续）12.4矩形边界框常用的碰撞检测技术——层次包围盒典型的包围盒算法：（继续）包围盒比较12.4矩形边界框包围盒树OBB包围盒树生成图传统OBB碰撞检测算法根节点—叶节点—基本几何元素12.4矩形边界框AABB的表达方法AABB的重要性质及记法AABB内的点满足下列不等式两个重要的顶点12.4矩形边界框AABB的表达方法AABB的重要性质及记法AABB的中心点半径向量尺寸向量(包含AABB的长、宽、高)maxminsppminmax()/2cppmax/2rpcs12.4矩形边界框AABB的表达方法AABB的表达方法minmaxminmax,,,,5AABBppcsrpAABBs和r不能明确地定义只需要这个向量中的两个()。在一些情况下，某些配对形式比其他的更有用。建议用p和来表示配对c++中的AABB类classAABB3{public:Vector3min;Vector3max;};12.4矩形边界框AABB的表达方法计算给定顶点集合的AABB引入两个辅助函数//“清空”AABBvoidAABB3::empty(){constfloatkBigNumber=1e37f;min.x=min.y=min.z=kBigNumber;max.x=max.y=max.z=-kBigNumber;}12.4矩形边界框AABB的表达方法计算AABB引入两个辅助函数//addapointtotheboxvoidAABB3::add(constVector3&p){if(p.xmin.x)min.x=p.x;if(p.xmax.x)max.x=p.x;if(p.ymin.y)min.y=p.y;if(p.ymax.y)max.y=p.y;if(p.zmin.z)min.z=p.z;if(p.zmax.z)max.z=p.z;}classVector3{Public:floatx,y,z;}12.4矩形边界框AABB的表达方法计算AABB从点集计算其AABBconstintn;Vector3list[n];//First,emptytheboxAABB3box;box.empty();//Addeachpointintotheboxfor(inti=0;in;++i){box.add(list[i]);}12.4矩形边界框AABB与边界球计算一个点集的AABB，在编程上更容易实现，并能在较短的时间内完成，计算边界球则困难得多对实际世界里的许多物体，AABB提供了一种更紧凑的边界（对于某些物体，边界球更好)。在极端的情况下，AABB的体积可能仅相当于边界球体积1/2AABB对物体方向敏感，边界球对物体方向不敏感原因：边界球的形状只有一个自由度——半径，而AABB有三个自由度——长、宽、高，因此，它可以调节这些自由度以适应不同物体12.4矩形边界框变换AABB用变换后的物体重新计算AABB对AABB做和物体同样的变换，然后对变换后的AABB重新计算AABB当物体在虚拟世界中移动时，对AABB的更新有两种选择通过“变换后的AABB”计算要比“通过变换后的物体”计算AABB快得多，因为AABB只有8个顶点通过“变换后的AABB”计算不能只简单地变换8个顶点，也不能通过转换原pmin和pmax来得到新的pmin和pmax。为了计算新的AABB，必须先变换8个顶点，再从这8个顶点中计算一个新的AABB12.4矩形边界框变换AABB通过“变换后的AABB”计算存在的问题这种方法可能使新边界框比原边界框大许多12.4矩形边界框变换AABBAABB的快速计算'max'max'max'min'min'minmaxmaxmaxminminmin,,,,,,,,,,,zyxzyxzyxzyx新边界框为设原边界框为12.4矩形边界框变换AABBAABB的快速计算voidAABB3::setToTransformedBox(constAABB3&box,constMatrix43&m){//Ifwe'reempty,thenbailif(box.isEmpty()){empty();return;}//Startwiththetranslationportion//ReturntrueiftheboxisenmptyboolAABB3::isEmpty()const{//Checkifwe'reinvertedonanyaxisreturn(min.xmax.x)||(min.ymax.y)||(min.zmax.z);}12.4矩形边界框变换AABBAABB的快速计算min=max=getTranslation(m);//Examineeachoftheninematrixelements//andcomputethenewAABBif(m.m110.0f){min.x+=m.m11*box.min.x;max.x+=m.m11*box.max.x;}else{min.x+=m.m11*box.max.x;max.x+=m.m11*box.min.x;}//ReturnthetranslationrowofthematrixinvectorformVector3getTranslation(constMatrix4x3&m){returnVector3(m.tx,m.ty,m.tz);}12.4矩形边界框变换AABBAABB的快速计算if(m.m120.0f){min.y+=m.m12*box.min.x;max.y+=