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

2D隐式直线上的最近点 直线隐式方程: p·n=d 目标:找出直线L上距q距离最短的点q’ 只需要将q沿着n的方向位移一定距离即可得到q’ 做一条经过q并平行于L的辅助线M 设nM和dM为直线M的法向量和d值 只需要将q沿着n的方向位移一定距离即可得到q’ 线上的最近点 面上的最近点 相交性检测

参数射线上的最近点 在2D或3D中的射线参数方程: d为单位向量 目标:找出射线R上距定点q距离最短的点q’ 注意事项 如果t<0或t>l,则p(t)不在R的 范围内.R上距q最近的点事原 点或是终点 线上的最近点 面上的最近点 相交性检测

平面上的最近点 平面p的隐式方程: p·n=d, n为单位向量 目标:给定一点q,找到q在平面p上的投影点q’ p+an = q (p+an) ·n = q·n p·n + (an) ·n = q·n d+a = q·n a= q·n－d 将q沿着n的相反方向移动一段距离得到q’ q’=q+(d－q·n)·n 线上的最近点 面上的最近点 相交性检测

圆上的最近点 目标:给定2D中的点q和圆心为c、半径为r的圆,要找到圆上距离q最近的点q’ ||b|| = ||d|| － r 线上的最近点 面上的最近点 相交性检测

AABB上的最近点 目标:给定B是由极值点pmin和pmax定义的AABB和任意点q,寻找B上距离q最近的点q’ 核心代码 如果q本来在AABB内部,则返回原来的点 线上的最近点 面上的最近点 相交性检测

相交性检测概述 目的:检测两个几何图元是否相交,在某些情况下还要求出其相交的部分 相交性检测是碰撞检测系统的基础,用来防止物体互相穿越,或者使物体看起来好像互相被弹开 静态测试:检测两个静止图元是否相交,返回一个布尔值 动态测试:检测两个运动图元是否相交以及相交的时间点.返回的结果包含一个布尔值和一个指明相交时间点的值 所有动态测试总是涉及一个静态图元和一个动态图元 线上的最近点 面上的最近点 相交性检测 线线相交 线面相交 AABB和面相交 面面相交 线球相交 球球相交 AABB和球相交 面和球相交 线和三角形相交 线与AABB相交 两个AABB相交

在2D中两条隐式直线的相交性检测 设两条直线的隐式方程为a1x+b1y=d1, a2x+b2y=d2 将方程组得 若分母为0,则只有一个解 无解,直线是彼此平行的,分母为0 无穷多解,两条直线重合,分母为0 线上的最近点 面上的最近点 相交性检测 线线相交 线面相交 AABB和面相交 面面相交 线球相交 球球相交 AABB和球相交 面和球相交 线和三角形相交 线与AABB相交 两个AABB相交

在3D中两条射线的相交性检测(1) 设两条射线的隐式方程为: r1(t1)=p1+t1d1 r2(t2)=p2+t2d2 两条射线的关系 交于一点 平行,没有交点 重合,有无限个交点 不在一个平面中 线上的最近点 面上的最近点 相交性检测 线线相交 线面相交 AABB和面相交 面面相交 线球相交 球球相交 AABB和球相交 面和球相交 线和三角形相交 线与AABB相交 两个AABB相交

在3D中两条射线的相交性检测(2) 交点的计算方法 解得 线上的最近点 面上的最近点 相交性检测 线线相交 线面相交 AABB和面相交 面面相交 线球相交 球球相交 AABB和球相交 面和球相交 线和三角形相交 线与AABB相交 两个AABB相交

在3D中两条射线的相交性检测(3) 交点的分情况讨论 如果两条射线平行,d1和d2的向量积为0,分母为0 如果分母不为0,通过检查p1(t1)和p2(t2)即可确定两条射线的相交情况(需给出一定的偏差值阈值) 上面的解法没有限定t1, t2的取值范围.如果射线的长度有限,在计算出t1, t2后还应作适当的边界检测 线上的最近点 面上的最近点 相交性检测 线线相交 线面相交 AABB和面相交 面面相交 线球相交 球球相交 AABB和球相交 面和球相交 线和三角形相交 线与AABB相交 两个AABB相交

射线和平面的相交性检测(1) 在3D中的射线方程为p(t)=p0+td 平面方程为p·n=d 假设射线的长度是无限的,则有 解得 线上的最近点 面上的最近点 相交性检测 线线相交 线面相交 AABB和面相交 面面相交 线球相交 球球相交 AABB和球相交 面和球相交 线和三角形相交 线与AABB相交 两个AABB相交

射线和平面的相交性检测(2) 讨论 如果射线和平面互相平行,分母d·n=0,则它们之间没有交点 如果t超出了取值范围,说明射线和平面不相交 线上的最近点 面上的最近点 相交性检测 线线相交 线面相交 AABB和面相交 面面相交 线球相交 球球相交 AABB和球相交 面和球相交 线和三角形相交 线与AABB相交 两个AABB相交

AABB和平面的相交性检测 AABB由pmin和pmax定义 平面方程为p·n=d 静态测试 动态测试(假设平面是静止的) 计算AABB顶点与n的点积,然后比较点积与d 如果所有点积都大于d,那么AABB都在平面正侧 如果所有点积都小于d,那么AABB都在平面反侧 动态测试(假设平面是静止的) AABB的位移由单位向量d和长度l定义 先求点积最大和最小的点,并在t=0时做相交检测 如果边界框和平面最初没有相交,一定是离平面最近的顶点先接触平面 如果只对与平面正面的碰撞感兴趣,那么总是使用点积值最小的顶点 线上的最近点 面上的最近点 相交性检测 线线相交 线面相交 AABB和面相交 面面相交 线球相交 球球相交 AABB和球相交 面和球相交 线和三角形相交 线与AABB相交 两个AABB相交

三个平面间的相交性检测 假设三个平面相交于一点.三个平面的隐式方程为p·n1=d1, p·n2=d2, p·n3=d3 求解方程组,得 讨论 如果三个平面交于一点,则分母不为0,方程组有唯一解 如果任意一对平面平行,那么交点不存在,要么不唯一 线上的最近点 面上的最近点 相交性检测 线线相交 线面相交 AABB和面相交 面面相交 线球相交 球球相交 AABB和球相交 面和球相交 线和三角形相交 线与AABB相交 两个AABB相交

射线和圆球的相交性检测 射线方程为p(t)=p0+td,d为单位向量,t从0变化到l,l为射线长度 圆用圆心c和半径r来定义 计算步骤 讨论 t = a－ f a是e在射线方向上的投影长度: e=c－p0, a=e·d f2 = r2－b2 = r2－(e2－a2) = a2+r2 －e·e t=e·d－sqrt(a2+r2 －e·e) 讨论 如果a2+r2 －e·e为负数,那么射线和圆不相交 如果e·e<r2,则射线起点可能在圆内 线上的最近点 面上的最近点 相交性检测 线线相交 线面相交 AABB和面相交 面面相交 线球相交 球球相交 AABB和球相交 面和球相交 线和三角形相交 线与AABB相交 两个AABB相交

两个圆或球的相交性检测(1) 静态检测: d2 < (r1+r2)2 圆用圆心c和半径r来定义 线上的最近点 面上的最近点 相交性检测 线线相交 线面相交 AABB和面相交 面面相交 线球相交 球球相交 AABB和球相交 面和球相交 线和三角形相交 线与AABB相交 两个AABB相交

两个圆或球的相交性检测(2) 动态检测 将第一个球变换成静止的,第二球的位移:d2－ d1 设静止球的球心为cs,半径为rs,运动球的球心为cm,半径为rm.在t时刻,运动球的球心为cm+td,d为单位向量,t为0到l, l表示移动的距离 线上的最近点 面上的最近点 相交性检测 线线相交 线面相交 AABB和面相交 面面相交 线球相交 球球相交 AABB和球相交 面和球相交 线和三角形相交 线与AABB相交 两个AABB相交

两个圆或球的相交性检测(3) 目标:计算运动球碰撞到静止球时的t 推导过程 线上的最近点 面上的最近点 相交性检测 线线相交 线面相交 AABB和面相交 面面相交 线球相交 球球相交 AABB和球相交 面和球相交 线和三角形相交 线与AABB相交 两个AABB相交

两个圆或球的相交性检测(4) 讨论 较小的根对应于两个球开始接触时的t,较大的根是两个球脱离接触时的t值 一般情况下,人们对较小的根比较感兴趣 如果||e||<r,说明两个球在初始情况下就相交 如果t<0或t>l,说明两个球在讨论的时间内不会相交 如果根号内的值为负数,那么两个球永远不会相交 线上的最近点 面上的最近点 相交性检测 线线相交 线面相交 AABB和面相交 面面相交 线球相交 球球相交 AABB和球相交 面和球相交 线和三角形相交 线与AABB相交 两个AABB相交

球和AABB的相交性检测 静态检测 找到AABB中距球心最近的点 计算该点到球心的距离的平方,并与球的半径平方比较 线上的最近点 面上的最近点 相交性检测 线线相交 线面相交 AABB和面相交 面面相交 线球相交 球球相交 AABB和球相交 面和球相交 线和三角形相交 线与AABB相交 两个AABB相交

球和平面的相交性检测(1) 静态检测 计算球心到平面的距离 如果距离小于半径平方,那么球和平面相交 简化算法: 线上的最近点 面上的最近点 线线相交 线面相交 AABB和面相交 面面相交 线球相交 球球相交 AABB和球相交 面和球相交 线和三角形相交 线与AABB相交 两个AABB相交

球和平面的相交性检测(2) 动态检测:设平面是静止的,球作相对位移 球的定义:半径r和初始球心c 球的运动:单位向量d指明方向,l代表位移的距离 不管在平面的哪一点上发生碰撞,在球上的相交点总是固定的 交点的初始位置: c－rn 利用射线与平面相交性检测,有 线上的最近点 面上的最近点 相交性检测 线线相交 线面相交 AABB和面相交 面面相交 线球相交 球球相交 AABB和球相交 面和球相交 线和三角形相交 线与AABB相交 两个AABB相交

射线和三角形的相交性检测 当求解射线与复杂物体相交性检测时,通常用三角网格代表物体表面,再作射线和三角网格的相交性检测 主要思路 计算射线和包含该三角形的平面的交点 计算交点的重心坐标.如果重心坐标的各个分量全为正数,则相交 线上的最近点 面上的最近点 相交性检测 线线相交 线面相交 AABB和面相交 面面相交 线球相交 球球相交 AABB和球相交 面和球相交 线和三角形相交 线与AABB相交 两个AABB相交

射线和AABB的相交性检测 可将该检测过程放在射线与三角形的相交性检测之前,来避免对更复杂物体的测试 主要思路 判断矩形边界框的哪个面会相交 检测射线与包含这个面的平面的相交性 如果交点在盒子中,那么射线与AABB有相交,否则不存在相交 线上的最近点 面上的最近点 相交性检测 线线相交 线面相交 AABB和面相交 面面相交 线球相交 球球相交 AABB和球相交 面和球相交 线和三角形相交 线与AABB相交 两个AABB相交

两个AABB的相交性检测(1) 第一个AABB的定义为:smin和smax,第二个AABB的定义为:mmin和mmax 静态检测 在每一维上单独检查其重合程度 如果在所有维上都没有重合,那么这两个AABB就不会相交 线上的最近点 面上的最近点 相交性检测 线线相交 线面相交 AABB和面相交 面面相交 线球相交 球球相交 AABB和球相交 面和球相交 线和三角形相交 线与AABB相交 两个AABB相交

两个AABB的相交性检测(2) 动态检测 分别分析每一维的重合问题,然后再组合到一起 设mmin(t)和mmax(t)代表运动AABB在时刻t的最小值和最大值,则 线上的最近点 面上的最近点 相交性检测 线线相交 线面相交 AABB和面相交 面面相交 线球相交 球球相交 AABB和球相交 面和球相交 线和三角形相交 线与AABB相交 两个AABB相交

两个AABB的相交性检测(3) 动态检测 讨论 组合各维情况:所有维上的时间区间的交集就是两个边界框相交的时间段 如果运动AABB开始位于静止AABB的右边并向左运动,那么tenter>tleave 如果tleave>1或tenter<0,表明在所讨论的时间内它们是不相交的 组合各维情况:所有维上的时间区间的交集就是两个边界框相交的时间段 如果区间为空,那么两个AABB永远不相交 如果区间在[0,1]之外,那么在所讨论的时间段内两个AABB不相交 线上的最近点 面上的最近点 相交性检测 线线相交 线面相交 AABB和面相交 面面相交 线球相交 球球相交 AABB和球相交 面和球相交 线和三角形相交 线与AABB相交 两个AABB相交