在3D中的射线方程为p(t)=p0+td 平面方程为p·n=d
内容提要 交点的计算方法
线上的最近点 面上的最近点 相交性检测
线线相交 线面相交 AABB和面相交 面面相交 线球相交 球球相交 AABB和球相交 面和球相交 线和三角形相
交 线与AABB相交 两个AABB相交

解得
辽宁师范大学计算机与信息技术学院 宋传鸣
核心代码


如果q本来在AABB内部,则返回原来的点
辽宁师范大学计算机与信息技术学院 宋传鸣
《图形与游戏开发的3D数学》
相交性检测概述
内容提要 目的:检测两个几何图元是否相交,在某些情况下
线上的最近点 还要求出其相交的部分
面上的最近点 相交性检测
相交性检测是碰撞检测系统的基础,用来防止物 体互相穿越,或者使物体看起来好像互相被弹开
无穷多解,两条直线重合,分母为0
辽宁师范大学计算机与信息技术学院 宋传鸣
《图形与游戏开发的3D数学》
在3D中两条射线的相交性检测(1)
内容提要
线上的最近点 面上的最近点 相交性检测
线线相交 线面相交 AABB和面相交 面面相交 线球相交 球球相交 AABB和球相交 面和球相交 线和三角形相
所有动态测试总是涉及一个静态图元和一个动态 图元
线与AABB相交
两个AABB相交
辽宁师范大学计算机与信息技术学院 宋传鸣
《图形与游戏开发的3D数学》
在2D中两条隐式直线的相交性检测
内容提要
线上的最近点 面上的最近点 相交性检测
线线相交 线面相交 AABB和面相交 面面相交 线球相交 球球相交 AABB和球相交 面和球相交 线和三角形相
《图形与游戏开发的3D数学》
射线和平面的相交性检测(1)
内容提要
线上的最近点 面上的最近点 相交性检测
线线相交 线面相交 AABB和面相交 面面相交 线球相交 球球相交 AABB和球相交 面和球相交 线和三角形相
交 线与AABB相交 两个AABB相交
《图形与游戏开发的3D数学》
参数射线上的最近点
内容提要 在2D或3D中的射线参数方程: p(t)= p0 + td(0 ＃t l)
线上的最近点 d为单位向量
面上的最近点 目标:找出射线R上距定点q距离最短的点q’
相交性检测
注意事项
如果t<0或t>l,则p(t)不在R的 范围内.R上距q最近的点事原 点或是终点
要找到圆上距离q最近的点q’
||b|| = ||d|| － r
d- r
b=
d
d
q¢= q + b = q +
d-
r d
d
辽宁师范大学计算机与信息技术学院 宋传鸣
《图形与游戏开发的3D数学》
AABB上的最近点 相交性检测
目标:给定B是由极值点pmin和pmax定义的AABB 和任意点q,寻找B上距离q最近的点q’
辽宁师范大学计算机与信息技术学院 宋传鸣
《图形与游戏开发的3D数学》
平面上的最近点
内容提要 平面p的隐式方程: p·n=d, n为单位向量
线上的最近点 面上的最近点 相交性检测
目标:给定一点q,找到q在平面p上的投影点q’
p+an = q (p+an) ·n = q·n
p·n + (an) ·n = q·n
2D隐式直线上的最近点
内容提要 直线隐式方程: p·n=d
线上的最近点 面上的最近点 相交性检测
目标:找出直线L上距q距离最短的点q’
做一条经过q并平行于L的辅助线M 设nM和dM为直线M的法向量和d值

只需要将q沿着n的方向位移一定距离即可得到q’

辽宁师范大学计算机与信息技术学院 宋传鸣
线线相交 线面相交 AABB和面相交 面面相交 线球相交 球球相交 AABB和球相交 面和球相交 线和三角形相
交
静态测试:检测两个静止图元是否相交,返回一个 布尔值
动态测试:检测两个运动图元是否相交以及相交 的时间点.返回的结果包含一个布尔值和一个指 明相交时间点的值
《图形与游戏开发的3D数学》
在3D中两条射线的相交性检测(3)
内容提要 交点的分情况讨论
线上的最近点 面上的最近点 相交性检测
线线相交 线面相交 AABB和面相交 面面相交 线球相交 球球相交 AABB和球相交 面和球相交 线和三角形相
交 线与AABB相交 两个AABB相交
交 线与AABB相交 两个AABB相交
设两条直线的隐式方程为a1x+b1y=d1, a2x+b2y=d2 将方程组得

d1 b1
a1 d1
x d2 b2 , a1 b1
y a2 d2 a1 b1
a2 b2
a2 b2
若分母为0,则只有一个解
无解,直线是彼此平行的,分母为0
交 线与AABB相交 两个AABB相交
设两条射线的隐式方程为: r1(t1)=p1+t1d1 r2(t2)=p2+t2d2
两条射线的关系
交于一点
平行,没有交点 重合,有无限个交点 不在一个平面中
辽宁师范大学计算机与信息技术学院 宋传鸣
《图形与游戏开发的3D数学》
在3D中两条射线的相交性检测(2)
如果两条射线平行,d1和d2的向量积为0,分母为0
如果分母不为0,通过检查p1(t1)和p2(t2)即可确定两 条射线的相交情况(需给出一定的偏差值阈值)
上面的解法没有限定t1, t2的取值范围.如果射线的 长度有限,在计算出t1, t2后还应作适当的边界检测
辽宁师范大学计算机与信息技术学院 宋传鸣
d+a = q·n
a= q·n－d
将q沿着n的相反方向移动一段距离得到q’
q’=q+(d－q·n)·n
辽宁师范大学计算机与信息技术学院 宋传鸣
《图形与游戏开发的3D数学》
圆上的最近点
内容提要 目标:给定2D中的点q和圆心为c、半径为r的圆,
线上的最近点 面上的最近点 相交性检测