Jump to content

View more

Image of the Day

Trying out some of Pickle Jar compositions in @SketchUp and Unity, for a late #screenshotsaturday #gamedev https://t.co/HU0kZAnQtD
IOTD | Top Screenshots

The latest, straight to your Inbox.

Subscribe to GameDev.net's newsletters to receive the latest updates and exclusive content.


Sign up now

sweep sphere vs triangle edge 3D intersect - response

2: Adsense

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.


  • You cannot reply to this topic
10 replies to this topic

#1 xdev1000   Members   

215
Like
0Likes
Like

Posted 22 April 2010 - 08:06 AM

I'm writting code to test sweep sphere to triangle collision. I'm stuck on the sphere to edge response. I have (T) time along the sweep sphere path for the shortest distance to triangle edge, and distance to the edge at that point. I cant figure out how to find the path point where the sphere first intersected the edge line segment. Uploaded with ImageShack.us Trigonometry works ok but it fails when the lines are nearly parallel, see picture. Whats happening is the closest distance is found between two lines, but the collision point is before this point. if( edge_collision_found ) { float rr = radiussquare - closestdistance; //trigonomentry to figure out how far back the sphere needs to move float dd = sphere_velocity.length(); rr/= dd; rr = sqrtf(rr); T -= rr; T *= sphere_velocity.lengthsqrt(); if(firstcollision <-1.f || T<firstcollision) { first_collision_time = T; } } any suggestions? thanks [Edited by - chris2001net on April 22, 2010 2:32:14 PM]

#2 CPPNick   Members   

100
Like
0Likes
Like

Posted 01 May 2010 - 05:24 PM

Funny you ask this question, because I am stuck at the same part. One thing I was thinking of differently though was this line:

float rr = radiussquare - closestdistance;

since A^2 + B^2 = C^2, and
closest distance should be a perpendicular line segment between the two lines, and the distance between t on the direction vector and the closest point on the edge should be radius^2, then we only have to solve for the third edge of the triangle. Then we subtract that third edge from the vector between the origin of the direction vector and the point where the two segments are closest, and that is the spheres collision position..does that sound right?

X^2 + closest_distance_vector^2 = radius^2

solve for X

then construct a vector from the origin of the direction vector to the point on the direction vector where the segs are closest.

finally subtract (X*normalized_direction) from that vector to get the spheres collided position.

I don't see any reason why this wouldn't work..but I don't think it would be nearly as fast as it could be...anywho, let me know what you think

#3 0BZEN   Members   

2194
Like
0Likes
Like

Posted 02 May 2010 - 12:29 AM

say you have a sphere (p, v, r) and you want to collision against edge (a, b).

The usual process is to find the times of intersect of ray (p, v) against the infinite cylinder (a, b, r).

a point q is on the cylinder surface if

((q - a) x (b - a))^2 = r^2 * ((b - a).(b - a))

So that's quite similar to a test of a sphere against a ray, which boils down to solving a quadratic equation.


Vector vxd = v.cross_product(b - a);
Vector pxd = (p - c).cross_product(b - a);

float a = vxd.dot_product(vxd);
float b = 2.0f * vxd.dot_product(pxd);
float c = pxd.dot_product(pxd) - (r*r) * (b - a).dot_product(b - a);

float d2 = b*b - (4.0f * a * c);
if(d2 < 0.0f) return false;

float d = sqrt(d2);
float t0 = (-b - d) / (2.0f * a);
float t1 = (-b + d) / (2.0f * a);

if(t0 > t1) swap(t0, t1);


t0 and t1 are the times the ray enters and exits the cylinder.

The position of the sphere at the first time of collision is then


p_enter = p + v * t0;


Now you check where that point is with respect to the edge start and end positions.

If that point is in front of 'a', then it means that the sphere will be tested against the vertex 'a'.

If that point is behind of 'b', then it means that the sphere will be tested against the vertex 'b'.

Else, the point is in between 'a' and 'b', and the cylinder collision will be the edge collision.

You can do that check like this.


float t = (p_enter - a).dot_product(b - a) / (b - a).dot_product(b - a);

if(t < 0.0f)
{
// you've hit the cylinder in front of 'a'.
// test against vertex 'a'.
}
else if(t > 1.of)
{
// you've hit the cylinder behind of 'b'.
// test against vertex 'b'.
}
else
{
// you've hit the cylinder between 'a' and 'b'.
t_collision = t0;
}

Everything is better with Metal.


#4 0BZEN   Members   

2194
Like
0Likes
Like

Posted 02 May 2010 - 12:40 AM

if you use a 'closest point' approach, you'll need an iterative solution. It's quite complicated in itself, and since you can solve the equation relatively easily, it's probably overkill.

Everything is better with Metal.


#5 CPPNick   Members   

100
Like
0Likes
Like

Posted 04 May 2010 - 08:04 PM

I'm still a little confused. What I understand of the theory so far is this:

1. Form a cylinder from the path of the sphere
2. Find the intersections of the ray(triangle's edge) with the cylinder
3. Check if the intersections are beyond the end points of the triangle's edge to decide which vertex, if any, to colide with.
4. If both intersections are between the triangle edge ray's endpoints, then the sphere has to be tested against the edge itself.

This is where I am having trouble now. How do I find where the sphere hit the edge? I know you probably have it in your explanation, but I am just not seeing it for some reason. I can't use the Collision with the Cylinder can I? then what happens if the sphere hits the line dead on?

#6 0BZEN   Members   

2194
Like
0Likes
Like

Posted 04 May 2010 - 11:18 PM

Nope, it's the reverse process.

1) Form a cylinder from the edge points, and the radius of the sphere.
2) form a ray from the sphere path.
3) find intersections of ray and cylinder.
4) check if first intersection is beyond the end points of the triangle's edge to decide which vertex, if any, to colide with.
5) If first intersections is between the triangle edge ray's endpoints, then the sphere has to be tested against the edge itself.

In a way, the sphere radius is 'transferred' from the sphere to the edge, turning the edge into a cylinder, while the sphere is turned into a point.

If you know how to check when a sphere hits a vertex, then you'll know how to check if a sphere hits an infinite line, because the equations are virtually the same.

sphere(c, r) equation. 'p' is on sphere surface if : (p - c)^2 = r^2


cylinder(c, d, r) equation (d is the direction of the cylinder, normalised, c is a point on the centre of the cylinder). 'p' is on cylinder surface if : ((p - c) x d)^2 = r^2.

Everything is better with Metal.


#7 CPPNick   Members   

100
Like
0Likes
Like

Posted 05 May 2010 - 03:38 AM

Eureka! it makes sense, but for step 5, do I actually have to test again? Shouldn't the first intersection with the cylinder be the sphere's center at time of collision with the edge?

edit- wait!. I think I get it. I need to find the spot on the surface of the sphere to compute the normal of the sliding plane right?

#8 0BZEN   Members   

2194
Like
0Likes
Like

Posted 05 May 2010 - 04:32 AM

yes on both counts.

Once you found the time the sphere hits the edge, you use the point of contact at the time of intersection, and check if it is near a vertex, or on the edge itself.

If on the edge, the normal will be the the line shooting from the sphere centre to the point on the edge closest to the sphere centre.

Vector p_edge = a + (b - a) * t;
ncoll = (p_enter - p_edge);
ncoll.normalise();


Everything is better with Metal.


#9 CPPNick   Members   

100
Like
0Likes
Like

Posted 05 May 2010 - 05:38 AM

ok. I'm still a little foggy about the quadratic formula stuff, but I'm gonna start coding anyways. I think I can figure it out. Thanks for the help!

#10 0BZEN   Members   

2194
Like
0Likes
Like

Posted 05 May 2010 - 05:39 AM

here's the code if you're interested.



class Vector
{
public:
float x, y, z;

Vector(){}
Vector(float a, float b, float c) : x(a), y(b), z©{}
Vector(const Vector& other) : x(other.x), y(other.y), z(other.z){}

Vector& operator += (const Vector& other) { x += other.x; y += other.y; z += other.z; return *this; }
Vector& operator -= (const Vector& other) { x -= other.x; y -= other.y; z -= other.z; return *this; }
Vector& operator *= (const float scalar) { x *= scalar; y *= scalar; z *= scalar; return *this; }
Vector& operator /= (const float scalar) { float inv = (1.0f / scalar); return (*this) *= inv; }

Vector operator + (const Vector& other) const { Vector temp(*this); return temp += other; }
Vector operator - (const Vector& other) const { Vector temp(*this); return temp -= other; }
Vector operator * (const float scalar) const { Vector temp(*this); return temp *= scalar; }
Vector operator / (const float scalar) const { Vector temp(*this); return temp /= scalar; }

Vector cross_product(const Vector& other) const { Vector temp(y*other.z-z*other.y, z*other.x-x*other.z, x*other.y-y*other.x); return temp; }
float dot_product(const Vector& other) const { return x*other.x + y*other.y + z*other.z; }

float length_squared() const { return (*this).dot_product(*this); }
float length() const { return sqrt(length_squared()); }
float normalise() { float l = length(); if(l > 1.0E-8f) (*this) /= l; return l; }

friend Vector operator * (float scalar, const Vector& v) { return v * scalar; }
};


// quadratic : a* t^2 + b*t + c = 0.
// d = b^2 - 4*a*c
// t0 = (-b - sqrt(d)) / (2 * a)
// t1 = (-b + sqrt(d)) / (2 * a)
bool solveQuadratic(float a, float b, float c, float& t0, float& t1)
{
float d2 = b*b - 4 * a * c;
if(d2 < 0.0f) return false;
float d = sqrt(d2);
t0 = (-b - d) / (2 * a);
t1 = (-b + d) / (2 * a);
if(t0 > t1) { float temp(t0); t0 = t1; t1 = temp; }
if(t1 < 0.0f || t0 > 1.0f) return false;
return true;
}

// ray (p, v)
// sphere (c, r)
// quadratic : ((p - c) + v * t)^2 = r^2
bool intersectRaySphere(const Vector& ray_origin,
const Vector& ray_direction,
const Vector& sphere_origin,
const float sphere_radius,
float& t_enter,
float& t_exit)
{
Vector p(ray_origin - sphere_origin);
float r2 = (sphere_radius * sphere_radius);
float v2 = ray_direction.dot_product(ray_direction);
float p2 = p.dot_product(p);
float pv = p.dot_product(ray_direction);

float a = v2;
float b = pv * 2.0f;
float c = p2 - r2;

// ray direction very small.
if(a < 1.0E-8f)
{
// no intersection
if (c > 0.0f) return false;

// intersection
t_enter = t_exit = 0.0f;
return true;
}

return solveQuadratic(a, b, c, t_enter, t_exit);
}

// ray (p, v)
// cylinder (c, d, r)
// quadratic : ((p - c) x d + (v x d) * t)^2 = r^2 * (d.d)
bool intersectRayCylinder( const Vector& ray_origin,
const Vector& ray_direction,
const Vector& cylinder_origin,
const Vector& cylinder_direction,
const float cylinder_radius,
float& t_enter,
float& t_exit)
{
Vector pxd = (ray_origin - cylinder_origin).cross_product(cylinder_direction);
Vector vxd = ray_direction.cross_product(cylinder_direction);
float r2 = (cylinder_radius * cylinder_radius);
float d2 = cylinder_direction.dot_product(cylinder_direction);
float v2 = vxd.dot_product(vxd);
float p2 = pxd.dot_product(pxd);
float pv = pxd.dot_product(vxd);

float a = v2;
float b = pv * 2.0f;
float c = p2 - (r2 * d2);

// ray direction parallel to cylinder.
if(a < 1.0E-8f)
{
// no intersection
if (c > 0.0f) return false;

// intersection
t_enter = t_exit = 0.0f;
return true;
}

return solveQuadratic(a, b, c, t_enter, t_exit);
}

bool CollideSphereEdge( const Vector& sphere_centre,
const Vector& sphere_velocity,
const float sphere_radius,
const Vector& edge_start,
const Vector& edge_end,
Vector& collision_point, // point of collision on edge
Vector& collision_normal, // normal of collision
float& collision_depth, // depth of intersection in case the sphere is embedded in edge
float& collision_time) // time of collisoin. 0.0f if sphere intersects edge already.
{
// edge dir (not normalised)
Vector edge_dir(edge_end - edge_start);

// chech against infinite cylinder.
float t_enter, t_exit;
if(!intersectRayCylinder( sphere_centre,
sphere_velocity,
edge_start,
edge_dir,
sphere_radius,
t_enter,
t_exit))
{
// missed cylinder -> missed edge
return false;
}

// time of collision (the time we first hit the edge).
float t_collision = t_enter;

// intersecting. reset to 0.0f.
if(t_collision < 0.0f) t_collision = 0.0f;

// sphere centre position at time of collision.
Vector sphere_collision = sphere_centre + sphere_velocity * t_collision;

// which side of the edge the sphere is.
float u = (sphere_collision - edge_start).dot_product(edge_dir) / edge_dir.dot_product(edge_dir);

// point on the edge collided by the sphere
Vector edge_collision;

// sphere position before edge start. test against edge start vertex.
if(u < 0.0f)
{
// test against start vertex.
if(!intersectRaySphere( sphere_centre,
sphere_velocity,
edge_start,
sphere_radius,
t_enter,
t_exit))
{
// missed vertex -> missed edge.
return false;
}

// new time of collision
t_collision = t_enter;
if(t_collision < 0.0f) t_collision = 0.0f;

// re-compute the sphere position at new time of collision.
sphere_collision = sphere_centre + sphere_velocity * t_collision;

// point on edge is start point.
edge_collision = edge_start;
}
// sphere position after edge end. test against edge end vertex.
else if (u > 1.0f)
{
if(!intersectRaySphere( sphere_centre,
sphere_velocity,
edge_end,
sphere_radius,
t_enter,
t_exit))
{
// missed vertex -> missed edge.
return false;
}

// new time of collision
t_collision = t_enter;
if(t_collision < 0.0f) t_collision = 0.0f;

// re-compute the sphere position at new time of collision.
sphere_collision = sphere_centre + sphere_velocity * t_collision;

// point on edge is end point.
edge_collision = edge_end;
}
else
{
// point of collision on the edge.
edge_collision = edge_start + edge_dir * u;
}

collision_point = edge_collision; // collision point on edge.
collision_time = t_collision; // time of collision.
collision_normal = (sphere_collision - edge_collision); // normal of collision.
float d = collision_normal.normalise(); // disatnce of the sphere position and point of collision
collision_depth = (d < sphere_radius)? (sphere_radius- d) : 0.0f; // intersection depth, if intersecting.
return true;
}



Everything is better with Metal.


#11 CPPNick   Members   

100
Like
0Likes
Like

Posted 05 May 2010 - 12:52 PM

Hey..Thanks bro. I can't bare to look at this code right now though lol
tomorrow is another day XD




Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.