Primitive Collision Detecting (5)
Line Segment & Plane
Line Seg: P = P0 + t * V t ∈ [0, 1]
Plane : N • P - N • Q = 0 (N is the normal of the plane，Q is some point on plane)
N • (P0 + t * V) - N • Q = 0;
N • (P0 – Q) + t * (N • V) = 0;
t * (N • V) = N • (Q – P0);
dp = N • V;
if ( dp == 0 ) return Line Parallel to Plane;
t = N • (Q – P0) / dp;
if ( t >= 0 && t <= 1 ) return Intersectant;
return No Intersection;
Point On Plane
Point: P
Plane: N • P - N • Q = 0
d = N • (P – Q);
if ( d == 0 ) return On Plane;
return Not On Plane;
Sphere & Plane
Sphere: | P – C0 | <= R
Plane : N • P - N • Q = 0
d = N • (C0 – Q);
if ( d^2 <= R^2 ) return Intersectant;
return No Intersection;
Dynamic Sphere & Plane
Sphere: | P – C0 | <= R
Delta : C = C0 + t * V t ∈ [0, 1]
Plane : N • P - N • Q = 0
d0 = N • (C0 – Q); //t = 0
d1 = N • (C0 + V – Q); //t = 1
if ( d0 * d1 > 0 && |d0| > R && |d1| > R ) return No Intersection;
return Intersectant;
//now we can evaluate t
//if ( d0 == d1 ) Line Parallel to Plane, then t ∈ [0, 1]
//else t = (d0 – R) / (d0 - d1); here t must ∈ [0, 1]
Ellipsoid & Plane
Ellipsoid: (x - x0)^2 / a^2 + (y - y0)^2 / b^2 + (z - z0)^2 / c^2 <= 1 (a>0, b>0, c>0)
Plane : N • P - N • Q = 0
Assume: F = (x - x0)^2 / a^2 + (y - y0)^2 / b^2 + (z - z0)^2 / c^2 – 1;
For a given point T on a common ellipsoid, the normal M of the tangent plane is:
M.x = ЭF/Эx = 2 * (T.x – x0) / a^2;
M.y = ЭF/Эy = 2 * (T.y – y0) / b^2;
M.z = ЭF/Эz = 2 * (T.z – z0) / c^2;
Here M is not normalized. Now we normalize it:
L = sqrt(M.x^2 + M.y^2 + M.z^2);
N.x = 2 * (T.x – x0) / a^2 / L;
N.y = 2 * (T.y – y0) / b^2 / L;
N.z = 2 * (T.z – z0) / c^2 / L;
N.x * L * a / 2 = (T.x – x0) / a;
N.y * L * b / 2 = (T.y – y0) / b;
N.z * L * c / 2 = (T.z – z0) / c;
(N.x * L * a)^2 / 4 + (N.y * L * b)^2 / 4 +(N.z * L * c)^2 / 4 = 1;
L^2 * ((N.x * a)^2 + (N.y * b)^2 +(N.z * c)^2) = 4;
L = 2 / sqrt((N.x * a)^2 + (N.y * b)^2 +(N.z * c)^2);
Assume: K = sqrt((N.x * a)^2 + (N.y * b)^2 +(N.z * c)^2);
T.x = x0 + L * N.x * a^2 / 2 = x0 + N.x * a^2 / K;
T.y = y0 + L * N.y * b^2 / 2 = y0 + N.y * b^2 / K;
T.z = z0 + L * N.z * c^2 / 2 = z0 + N.z * c^2 / K;
P0 = {x0, y0, z0};
dp = (P0 - T) • N = -((N.x * a)^2 + (N.y * b)^2 +(N.z * c)^2) / K = -K;
dp^2 = (-K)^2 = (N.x * a)^2 + (N.y * b)^2 +(N.z * c)^2;
D = (P0 - Q) • N;
if ( D^2 <= dp^2 ) return Intersectant;
return No Intersection;
Triangle & Plane
Triangle : P0, P1, P2
Plane : N • P - N • Q = 0
dp0 = N • (P0 - Q);
dp1 = N • (P1 - Q);
dp2 = N • (P2 - Q);
if ( dp0 > 0 && dp1 > 0 && dp2 > 0 ) return No Intersection;
if ( dp0 < 0 && dp1 < 0 && dp2 < 0 ) return No Intersection;
return Intersectant;
//the intersected line of triangle & plane can be evaluated by using proportion
//for example: P0 is at the positive side of the plane, P1 & P2 are at the negative side
//then dp0 >= 0, dp1 <= 0, dp2 <=0
//if (dp0 == 0 && dp1 == 0 && dp2 == 0 ), then the triangle is on the plane, the intersected part is the triangle itself
//else if (dp1 – dp0 == 0), then P0 & P1 are both on the Plane, the intersected line is P0 – P1
//else if (dp2 – dp0 == 0), then P0 & P2 are both on the Plane, the intersected line is P0 – P2
//else
//assume E is the intersected point between (P0 – P1) & plane, F is the intersected point between (P0 – P2) & plane
//so E = P1 + dp1 / (dp1 – dp0) * (P0 – P1)
//so F = P2 + dp2 / (dp2 – dp0) * (P0 – P2)
//and EF is the intersected line of triangle & plane
AABB & Plane
AABB : A { V3d inf, sup;}
Plane : N • P - N • Q = 0
//摘自Real Time Rendering
基本思想是计算AABB的8个顶点到平面的距离，如果都在同一侧，则表示没有相交，否则就有相交
优化的方法就是找出沿平面法线方向离平面距离最近的两个顶点，这两个顶点是AABB的对角顶点，构成AABB四条对角线中的一条
//这里Vmin和Vmax是按平面的方向N来说的，两个点到平面的带符号距离较大的就是Vmax
for each i ∈ [x, y, z]
{
if ( N.i >= 0 )
{
Vmin.i = A.inf.i;
Vmax.i = A.sup.i;
}
else
{
Vmax.i = A.inf.i;
Vmin.i = A.sup.i;
}
}
if ( N • (Vmin - Q) ) > 0 ） return No Intersection;
if ( N • (Vmax - Q) ) < 0 ） return No Intersection;
return Intersectant;
OBB & Plane
OBB : { V3d C, U, V, W;
V3d L; } //C是中心点坐标，U、V、W是三个轴方向，L的三个分量是U、V、W是三个方向的半长，表示Box长宽高各一半大小
Plane: N • P - N • Q = 0
//摘自Real Time Rendering
D = (C - Q) • N;
f = L.x * |N • U| + L.y * |N • V| + L.z * |N • W|;
if ( D^2 > f^2 ) return No Intersection;
return Intersectant;
