RE: [Algorithms] Moving sphere, moving triangle collision

[Gribb, G. <gg...@ra...>]

> Can anyone explain, or point me to somewhere, that does a 
> moving sphere
> versus a static triangle?

Here is a moving triangle vs unit sphere at the origin test, that I designed
and implemented. It handles your case (and ellipsoids). You have to subtract
the initial sphere origin from the triangle verts. Then scale all components
of the triangle verts and the movement vector (called the velocity in the
code) by the inverse of the sphere radius. Finally, negate the movement
vector, since we are considering the triangle moving not the sphere.

Without further ado, the code. ( ^ is a dot product).
-Gil

bool SegmentUnitSphereAtOriginTest(const CVect3 &start,const CVect3
&end,CVect3 *returnedPoint,float *returnedT)
{
	// a quick box test
	if (start.x()<-1.0f&&end.x()<-1.0f)
	{
		return false;
	}
	if (start.x()>1.0f&&end.x()>1.0f)
	{
		return false;
	}
	if (start.y()<-1.0f&&end.y()<-1.0f)
	{
		return false;
	}
	if (start.y()>1.0f&&end.y()>1.0f)
	{
		return false;
	}
	if (start.z()<-1.0f&&end.z()<-1.0f)
	{
		return false;
	}
	if (start.z()>1.0f&&end.z()>1.0f)
	{
		return false;
	}
	
	// compute dir, a unit vector in the direction if the segment
	CVect3 dir=end;
	dir-=start;
	float invLen=1.0f/dir.Len();
	dir*=invLen;

	// compute minimum distance to collision, d

	float dot=start^dir;	
	
	float det=1.0f+dot*dot-(start^start);
	if (det<0.0f)
	{
		return false; // segment misses sphere
	}
	float d=-((dir^start)+sqrt(det));
	if (d<0.0f)
	{
		return false; // segment is either start solid or misses
	}
	float t=d*invLen; // convert back to 0-1 t param
	if (t>1.0f)
	{
		return false; // collides after the end of the segment
	}
	if (returnedT)
	{
		*returnedT=t;
	}
	if (returnedPoint)
	{
		*returnedPoint=dir;
		(*returnedPoint)*=d;
		(*returnedPoint)+=start;
		assert(fabs(returnedPoint->Len2()-1.0f)<0.1f);
	}	
	return true;
}

bool UnitSphereAtOriginTriangleTest(
	const CVect3 &velocity, //for the triangle
	const CVect3 &A,const CVect3 &B,const CVect3 &C, //triangle
	bool backFaces,bool frontFaces, // which faces to accept
	CVect3 &returnedPoint,CVect3 &returnedNormal,float &returnedT)
{
	static const float tiny=1E-10f;

	returnedT=1.01f; // start off the end
	
	CVect3 edgeAC=C;
	edgeAC-=A;

	CVect3 edgeAB=B;
	edgeAB-=A;
	
	returnedNormal=edgeAB;	
	returnedNormal.Cross(edgeAC);
	
	float denom=velocity^returnedNormal;
	
	
	if (
		(!backFaces&&denom>0)||		// not accepting back faces
		(!frontFaces&&denom<0))		//not accepting front faces
	{
		return false;
	}
	
	bool doFace=fabs(denom)>tiny;

	CVect3 Av=A;
	Av+=velocity;
	CVect3 Bv=B;
	Bv+=velocity;
	CVect3 Cv=C;
	Cv+=velocity;

	// test the 3 verts
	CVect3 retp;
	float rett;
		
	if (SegmentUnitSphereAtOriginTest(A,Av,&retp,&rett))
	{
		if (rett<returnedT)
		{
			returnedT=rett;
			returnedPoint=retp;
		}
	}
	if (SegmentUnitSphereAtOriginTest(B,Bv,&retp,&rett))
	{
		if (rett<returnedT)
		{
			returnedT=rett;
			returnedPoint=retp;
		}
	}
	if (SegmentUnitSphereAtOriginTest(C,Cv,&retp,&rett))
	{
		if (rett<returnedT)
		{
			returnedT=rett;
			returnedPoint=retp;
		}
	}
		
	// now test the three edges	
	CVect3 start,end;
	float ts,te;

	float invLenAC=1.0f/edgeAC.Len();
	edgeAC*=invLenAC;

	ts=-(A^edgeAC);
	te=-(Av^edgeAC);
	if (
		(ts>0.0f||te>0.0f)&& // the line of impact is off this edge
		(ts*invLenAC<1.0f||te*invLenAC<1.0f)) // the line of impact
is off this edge
	{
		start=edgeAC;
		start*=ts;
		start+=A;	
		
		end=edgeAC;
		end*=te;
		end+=Av;	
		if (SegmentUnitSphereAtOriginTest(start,end,&retp,&rett))
		{
			if (rett<returnedT)
			{
				float test=((te-ts)*rett+ts)*invLenAC;
				if (test>0.0f&&test<1.0f)
				{
					returnedT=rett;
					returnedPoint=retp;
				}
			}
		}
	}
	float invLenAB=1.0f/edgeAB.Len();
	edgeAB*=invLenAB;

	ts=-(A^edgeAB);
	te=-(Av^edgeAB);
	if (
		(ts>0.0f||te>0.0f)&& // the line of impact is off this edge
		(ts*invLenAB<1.0f||te*invLenAB<1.0f)) // the line of impact
is off this edge
	{
		start=edgeAB;
		start*=ts;
		start+=A;	
		
		end=edgeAB;
		end*=te;
		end+=Av;	
		if (SegmentUnitSphereAtOriginTest(start,end,&retp,&rett))
		{
			if (rett<returnedT)
			{
				float test=((te-ts)*rett+ts)*invLenAB;
				if (test>0.0f&&test<1.0f)
				{
					returnedT=rett;
					returnedPoint=retp;
				}
			}
		}
	}
	

	CVect3 edgeCB=B;
	edgeCB-=C;
	
	float invLenCB=1.0f/edgeCB.Len();
	edgeCB*=invLenCB;

	ts=-(C^edgeCB);
	te=-(Cv^edgeCB);
	if (
		(ts>0.0f||te>0.0f)&& // the line of impact is off this edge
		(ts*invLenCB<1.0f||te*invLenCB<1.0f)) // the line of impact
is off this edge
	{
		start=edgeCB;
		start*=ts;
		start+=C;	
		
		end=edgeCB;
		end*=te;
		end+=Cv;	
		if (SegmentUnitSphereAtOriginTest(start,end,&retp,&rett))
		{
			if (rett<returnedT)
			{
				float test=((te-ts)*rett+ts)*invLenCB;
				if (test>0.0f&&test<1.0f)
				{
					returnedT=rett;
					returnedPoint=retp;
				}
			}
		}
	}
	
	// and finally the surface of the triangle
	if (doFace)
	{
	
		CVect3 perpCB=edgeCB;
		perpCB.Cross(returnedNormal);
		
		float invLenPerpCB=1.0f/perpCB.Len();
		perpCB*=invLenPerpCB;
		
		start=edgeCB;
		start*=-(C^edgeCB);
		CVect3 temp=perpCB;
		temp*=-(C^perpCB);
		start+=temp;
		start+=C;
		
		end=edgeCB;
		end*=-(Cv^edgeCB);
		temp=perpCB;
		temp*=-(Cv^perpCB);
		end+=temp;
		end+=Cv;
		if (SegmentUnitSphereAtOriginTest(start,end,&retp,&rett))
		{
			if (rett<returnedT)
			{
				// set At Bt Ct to the triangle at the time
of contact
				CVect3 At=velocity;
				At*=rett;
				CVect3 Bt=At;
				CVect3 Ct=At;
				At+=A;
				Bt+=B;
				Ct+=C;
				
				CVect3 edgePA=At;
				edgePA-=retp;
				CVect3 edgePB=Bt;
				edgePB-=retp;
				CVect3 edgePC=Ct;
				edgePC-=retp;
				
				// now see if the hit spot is in the
triangle
				temp=edgePA;
				temp.Cross(edgePB);
				if ((temp^returnedNormal)>=0.0f)
				{
					temp=edgePC;
					temp.Cross(edgePA);
					if ((temp^returnedNormal)>=0.0f)
					{
						temp=edgePB;
						temp.Cross(edgePC);
						if
((temp^returnedNormal)>=0.0f)
						{
							returnedT=rett;
							returnedPoint=retp;
						}
					}
				}
			}
		}
		
	}
	if (returnedT<=1.0f)
	{
		returnedNormal*=-1.0f;
		CVect3 tvel=velocity;
		tvel*=-returnedT;
		returnedPoint+=tvel;
		return true;
	}
	return false;
}