• Advertisement
Sign in to follow this  

Sphere-Triangle Snowboarding Physics [Solved]

This topic is 3990 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm working on a 3D snowboarding game and need some physics. To give you an idea, the player needs to be able to go down the mountain and go off jumps smoothly, as well as ride up half-pipes. Rails can be programmed separately. I just need a general solution for movement now. My geometry is based off bezier patches, but currently it gets tesselated into triangles for the collision code. So far I've tried swept sphere vs triangle collision detection+response but the results were a little different than I expected (my implementation may be wrong, but I've checked it so many times I don't know where else to look), and I'm not sure if that's the right way to go anyway. How would you do it? [Edited by - skittleo on March 25, 2007 1:32:27 AM]

Share this post


Link to post
Share on other sites
Advertisement
Hmm I was thinking thyat this morning too...

My ideas of how to do it were:

  • Swept-sphere

  • Use ray tracing on the patches. (I cannot think of a reliable way to do this)

  • Use a physics engine to simulate an actual board. (Unsure of how to do this either)



And as you said, swept sphere does seem to make the most sense in this situation. I expected the sphere to slide around on the terrain more smoothly than it does though. It gets caught up on rapidly changing slopes (hard to explain because I haven't figured out why and when it always happens, but the sphere just gets caught sometimes and doesn't slide on certain slopes). After classes today I'm going to go through each part of the collision code to see if this is an implementation problem...

... more details to come, but if anyone has any ideas feel free to share them..

Share this post


Link to post
Share on other sites
I've done slide sphere collision on terrain, it's pretty slippery :) I'll post a demo later. The demo I've got at the moment is a bit crummy.

Share this post


Link to post
Share on other sites
Slippery is definitely not the word I would use to describe my implementation haha. Fortunately, since you said it should be slippery I've been debugging again. Not fixed yet, but I did find that if I don't update the position and only the velocity when the sphere collides with triangles its rather slippery like you said. But that's only a temporary fix. The problem must be somehow related to the updating of the position. Let me do some more code review and get back to you... Thanks oliii for if nothing else just the verification that I had the right idea... I should be able to fix this soon.

PS: That source would be very helpful if you have it around, but if not, I've got a few others here your old one included.

Share this post


Link to post
Share on other sites
I figure since I had trouble finding source code to compare mine with, I thought I'd post the relavent parts of my code for others to look at or use.


bool Math::SolveQuadratic(float a, float b, float c, float& root1, float& root2)
{
float determinant = b * b - 4.0f * a * c;

if (determinant < 0.0f)
return false;

float sqrtD = sqrt(determinant);
float a2 = 2.0f * a;
root1 = (-b - sqrtD) / a2;
root2 = (-b + sqrtD) / a2;

return true;
}

bool Math::IsPointInTriangle(D3DXVECTOR3& triangleVertex1, D3DXVECTOR3& triangleVertex2,
D3DXVECTOR3& triangleVertex3, D3DXVECTOR3& triangleNormal, D3DXVECTOR3& point)
{
D3DXVECTOR3 cross;

D3DXVec3Cross(&cross, &(triangleVertex2 - triangleVertex1), &(point - triangleVertex1));
if (D3DXVec3Dot(&cross, &triangleNormal) < Math::Epsilon)
return false;

D3DXVec3Cross(&cross, &(triangleVertex3 - triangleVertex2), &(point - triangleVertex2));
if (D3DXVec3Dot(&cross, &triangleNormal) < Math::Epsilon)
return false;

D3DXVec3Cross(&cross, &(triangleVertex1 - triangleVertex3), &(point - triangleVertex3));
if (D3DXVec3Dot(&cross, &triangleNormal) < Math::Epsilon)
return false;

return true;
}

void Intersection::SweptUnitSphereTriangle(D3DXVECTOR3& trianglePoint1, D3DXVECTOR3& trianglePoint2,
D3DXVECTOR3& trianglePoint3, D3DXVECTOR3& triangleNormal, D3DXVECTOR3& spherePosition,
D3DXVECTOR3& sphereVelocity, D3DXVECTOR3& intersectionPoint, float& intersectionTime, bool& doesIntersect)
{
// Check intersection against the triangle plane

D3DXPLANE trianglePlane;
bool embeddedInPlane;
D3DXPlaneFromPointNormal(&trianglePlane, &trianglePoint1, &triangleNormal);
SweptUnitSpherePlane(trianglePlane, spherePosition, sphereVelocity, intersectionPoint, intersectionTime,
doesIntersect, embeddedInPlane);

if (doesIntersect)
{
if (!embeddedInPlane)
{
if (Math::IsPointInTriangle(trianglePoint1, trianglePoint2, trianglePoint3, triangleNormal,
intersectionPoint))
return;
}
}
else return;

// Check for intersection against each vertex

bool intersect;
float time;
doesIntersect = false;
intersectionTime = 1.0f;

SweptUnitSpherePoint(trianglePoint1, spherePosition, sphereVelocity, time, intersect);
if (intersect && time < intersectionTime)
{
intersectionPoint = trianglePoint1;
intersectionTime = time;
doesIntersect = true;
}

SweptUnitSpherePoint(trianglePoint2, spherePosition, sphereVelocity, time, intersect);
if (intersect && time < intersectionTime)
{
intersectionPoint = trianglePoint2;
intersectionTime = time;
doesIntersect = true;
}

SweptUnitSpherePoint(trianglePoint3, spherePosition, sphereVelocity, time, intersect);
if (intersect && time < intersectionTime)
{
intersectionPoint = trianglePoint3;
intersectionTime = time;
doesIntersect = true;
}

// Check for intersection against each edge

D3DXVECTOR3 point;

SweptUnitSphereEdge(trianglePoint1, trianglePoint2, spherePosition, sphereVelocity, time, point, intersect);
if (intersect && time < intersectionTime)
{
intersectionPoint = point;
intersectionTime = time;
doesIntersect = true;
}

SweptUnitSphereEdge(trianglePoint2, trianglePoint3, spherePosition, sphereVelocity, time, point, intersect);
if (intersect && time < intersectionTime)
{
intersectionPoint = point;
intersectionTime = time;
doesIntersect = true;
}

SweptUnitSphereEdge(trianglePoint3, trianglePoint1, spherePosition, sphereVelocity, time, point, intersect);
if (intersect && time < intersectionTime)
{
intersectionPoint = point;
intersectionTime = time;
doesIntersect = true;
}
}

void Intersection::SweptUnitSpherePlane(D3DXPLANE& plane, D3DXVECTOR3& spherePosition,
D3DXVECTOR3& sphereVelocity, D3DXVECTOR3& intersectionPoint, float& intersectionTime, bool& doesIntersect,
bool& embeddedInPlane)
{
doesIntersect = false;
intersectionTime = 1.0f;
embeddedInPlane = false;

// Heading towards plane?
float normalDotVelocity = D3DXPlaneDotNormal(&plane, &sphereVelocity);
if (normalDotVelocity > 0.0f)
return;

// Behind plane?
float signedDistanceToPlane = D3DXPlaneDotCoord(&plane, &spherePosition);
if (signedDistanceToPlane < -1.0f)
return;

if (normalDotVelocity == 0.0f)
{
// Inside plane?
if (signedDistanceToPlane < 1.0f)
{
doesIntersect = true;
embeddedInPlane = true;
}
}
else
{
float time1 = (signedDistanceToPlane - 1.0f) / -normalDotVelocity;
float time2 = (signedDistanceToPlane + 1.0f) / -normalDotVelocity;

if (time1 > time2)
{
float temp = time1;
time1 = time2;
time2 = temp;
}

if (time1 > 1.0f || time2 < 0.0f)
return;

intersectionTime = time1;
intersectionTime = MAX(0.0f, MIN(1.0f, intersectionTime));

intersectionPoint = spherePosition + sphereVelocity * intersectionTime
- D3DXVECTOR3(plane.a, plane.b, plane.c);
doesIntersect = true;
}
}


void Intersection::SweptUnitSpherePoint(D3DXVECTOR3& point, D3DXVECTOR3& spherePosition,
D3DXVECTOR3& sphereVelocity, float& intersectionTime, bool& doesIntersect)
{
intersectionTime = 1.0f;

D3DXVECTOR3 pointToSpherePosition = spherePosition - point;
float distanceFromPointToSpherePosition = D3DXVec3Length(&pointToSpherePosition);

float a = D3DXVec3Dot(&sphereVelocity, &sphereVelocity);
float b = 2.0f * D3DXVec3Dot(&sphereVelocity, &pointToSpherePosition);
float c = D3DXVec3Dot(&pointToSpherePosition, &pointToSpherePosition) - 1.0f;

float time1, time2;
doesIntersect = Math::SolveQuadratic(a, b, c, time1, time2);

if (doesIntersect)
{
if (time1 >= 0.0f && time1 <= 1.0f)
{
if (time1 < time2)
{
intersectionTime = time1;
return;
}
}

if (time2 >= 0.0f && time2 <= 1.0f)
{
if (time2 <= time1)
{
intersectionTime = time2;
return;
}
}

doesIntersect = false;
}
}

void Intersection::SweptUnitSphereEdge(D3DXVECTOR3& point1, D3DXVECTOR3& point2, D3DXVECTOR3& spherePosition,
D3DXVECTOR3& sphereVelocity, float& intersectionTime, D3DXVECTOR3&intersectionPoint, bool& doesIntersect)
{
intersectionTime = 1.0f;

D3DXVECTOR3 edge = point2 - point1;
D3DXVECTOR3 spherePositionToVertex = point1 - spherePosition;
float edgeLengthSquared = D3DXVec3Dot(&edge, &edge);
float edgeDotVelocity = D3DXVec3Dot(&edge, &sphereVelocity);
float edgeDotSpherePositionToVertex = D3DXVec3Dot(&edge, &spherePositionToVertex);

float a = edgeLengthSquared * (-D3DXVec3Dot(&sphereVelocity, &sphereVelocity)) + SQUARE(edgeDotVelocity);
float b = edgeLengthSquared * (2.0f * D3DXVec3Dot(&sphereVelocity, &spherePositionToVertex)) -
2 * edgeDotVelocity * edgeDotSpherePositionToVertex;
float c = edgeLengthSquared * (1.0f - D3DXVec3Dot(&spherePositionToVertex, &spherePositionToVertex)) +
SQUARE(edgeDotSpherePositionToVertex);

float time1, time2;
doesIntersect = Math::SolveQuadratic(a, b, c, time1, time2);

if (doesIntersect)
{
if (time1 >= 0.0f && time1 <= 1.0f)
{
if (time1 <= time2)
{
float f = (edgeDotVelocity * time1 - edgeDotSpherePositionToVertex) / edgeLengthSquared;
if (f >= 0.0f && f <= 1.0f)
{
intersectionTime = time1;
intersectionPoint = point1 + edge * f;
return;
}
}
}

if (time2 >= 0.0f && time2 <= 1.0f)
{
if (time2 <= time1)
{
float f = (edgeDotVelocity * time2 - edgeDotSpherePositionToVertex) / edgeLengthSquared;
if (f >= 0.0f && f <= 1.0f)
{
intersectionTime = time2;
intersectionPoint = point1 + edge * f;
return;
}
}
}

doesIntersect = false;
}
}

void ColliderSphere::Move(CollisionMesh& collisionMesh, float timeStep)
{
Velocity += Acceleration * timeStep;
Acceleration = D3DXVECTOR3(0.0f, 0.0f, 0.0f);

D3DXVECTOR3 frameVelocity = Velocity * timeStep;

RecursiveCollide(Position, frameVelocity, collisionMesh);

if (OnSurface)
{
D3DXVECTOR3 normalVelocity = SurfaceNormal * D3DXVec3Dot(&SurfaceNormal, &Velocity);
D3DXVECTOR3 tangentVelocity = Velocity - normalVelocity;
Velocity = tangentVelocity * TANGENT_VELOCITY_MULTIPLIER - normalVelocity * NORMAL_VELOCITY_MULTIPLIER;
}
}

void ColliderSphere::RecursiveCollide(D3DXVECTOR3& position, D3DXVECTOR3& velocity, CollisionMesh& collisionMesh,
unsigned int recursionCount)
{
if (D3DXVec3Dot(&velocity, &velocity) < MINIMUM_VELOCITY_SQUARED || recursionCount == 0)
return;

D3DXVECTOR3 intersectionPoint;
float intersectionTime = 1.0f;
bool doesIntersect = false;
collisionMesh.CollideSweptSphere(position, Radius, velocity, intersectionPoint, intersectionTime,
doesIntersect);

if (doesIntersect)
{
float velocityLength = D3DXVec3Length(&velocity);
D3DXVECTOR3 normalizedVelocity = velocity / velocityLength;

D3DXVECTOR3 newPosition = position + velocity * (intersectionTime) - normalizedVelocity * Math::Epsilon;

SurfaceNormal = newPosition - intersectionPoint;
D3DXVec3Normalize(&SurfaceNormal, &SurfaceNormal);

D3DXVECTOR3 normalVelocity = SurfaceNormal * D3DXVec3Dot(&SurfaceNormal, &velocity);
D3DXVECTOR3 tangentVelocity = velocity - normalVelocity;
D3DXVECTOR3 newVelocity = tangentVelocity * TANGENT_VELOCITY_MULTIPLIER
- normalVelocity * NORMAL_VELOCITY_MULTIPLIER;

RecursiveCollide(newPosition, newVelocity, collisionMesh, recursionCount - 1);

OnSurface = true;
position = newPosition;
}
else
{
position += velocity;
OnSurface = false;
}
}





The only part that's not there is the code that searches the octree for nearby triangles and scales them down by the sphere's radius. I figure there's enough examples online if you're having octree problems.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement