# Sphere Collision & 270 degree corners.

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

## Recommended Posts

I currently have a Sphere surrounding the camera which acts as a boundary for collision detection. After your help with the Ray Intersection methods, moving the idea forward to a method involving a Sphere wasn't too difficult. However, although I now no longer have stuttering when colliding with walls that are 90 degrees or less, I am getting horrible stuttering when colliding with two walls that are exposed at 270 degrees. E.G
              (Wall 1)
|
|
|
|___________(Wall 2)

^
|
(Camera Direction)

If the camera hits the intersection between Wall 1 and Wall 2 it will stutter between each wall until pushed out. It wont do this for any other scenario, why? Here is my code, I am using a Sphere/Triangle Collision method:

struct CollisionResult
{
public bool hasHit;                     // The following parameters are only valid when hasHit is true

//public float distanceSqr;               // distance to intersection point
public float distance;                  // Distance to the intersection point
public Vector3 location;                // Actual location of the hit (always a point on the triangle)
public Vector3 normal;                  // Normal of the hit

public static CollisionResult CreateNoHit()
{
CollisionResult result;
result.hasHit = false;
result.location = new Vector3(0, 0, 0);
result.normal = new Vector3(0, 0, 0);
//result.distanceSqr = 0;
result.distance = 0;

return result;
}

public void KeepClosest(CollisionResult result)
{
if (result.hasHit && (!hasHit || (result.distance < distance)))
{
this = result;
}
}
}

// In separate class:

public void BoundingSphereTriangleCollisionDetection(Camera camera)
{
Vector3 projectedPosition = camera.Position;                    // Position we will move to
BoundingSphere boundingSphere = camera.BoundingSphere;          // Object's BoundingSphere

foreach (Triangle tri in Game1.levelTriangleList)
{

// Don't continue until all collisions have been resolved
while (result.hasHit)
{
// Distance to current Triangle from Object's BoundingSphere Centre (I.E. Object's Centre/Position)
//Console.WriteLine("Distance to Triangle: " + result.distance);
projectedPosition -= result.normal * (result.distance - boundingSphere.Radius - EPSILON);

}
}

camera.Position = projectedPosition;
// Bounding Sphere Position should be updated in Object Method (not here)
}

/// <summary>
/// Perform a Sphere/Triangle check. (Will work with XNA BoundingSpheres also)
///
/// :
/// - Spheres can only collide with the front side of triangles! (Much like Bounding Sphere/Plane behaviour)
/// - Always the closest possible intersection position is returned, which is always inside the triangle.
/// </summary>
/// <param name="position"></param>
/// <param name="result"></param>
private void SphereTriangleCollision(Vector3 position, float sphereRadius, Triangle triangle, out CollisionResult result)
{
result = new CollisionResult();
Vector3 faceNormal = triangle.FaceNormal;
Vector3[] trianglePoints = triangle.Points;
Vector3[] triangleEdgeNormals = triangle.EdgeNormals;

Vector3 v = position - trianglePoints[0];

// Check which side of the plane we are on
float dist;
Vector3.Dot(ref v, ref faceNormal, out dist);

if (dist < 0)
{
return;     // We need some more testing, since we're at the wrong side of the polygon!
}
{
return;     // We're too far away from the triangle
}

// If the above two rules are false there is a collision point
Vector3 collisionPoint = position - (dist * faceNormal);
//Console.WriteLine("Triangle Collision At " + collisionPoint);

// Is the collision point in the current Triangle?
if (PointInTriangle(ref collisionPoint, trianglePoints, triangleEdgeNormals))
{
CollisionResult t;
t.hasHit = true;
//t.distanceSqr = (collisionPoint - position).LengthSquared();
t.distance = (collisionPoint - position).Length();
t.normal = faceNormal;
t.location = collisionPoint;

result.KeepClosest(t);
return;
}

// If the point is not inside the triangle it could still intersect the triangle! (It would intersect the Triangle edge)
for (int i = 0; i < 3; i++)
{
Vector3 E = trianglePoints[(i + 1) % 3] - trianglePoints;

// Relative position to edge start.
Vector3 H = collisionPoint - trianglePoints;

// Distance of P to edge plane
float hn = Vector3.Dot(H, triangleEdgeNormals);

// Point is on the same side of the triangle, from the edge plane, try another
if (hn < 0.0f)
{
continue;
}

// Too far away from this edge's plane
{
return;
}

// test intersection with polygon's edge
Vector3 intersectionPoint = new Vector3();

if (SpherePartialEdgeCollide(ref position, ref trianglePoints, ref E, ref intersectionPoint))
{
CollisionResult t;
t.hasHit = true;
//t.distanceSqr = (intersectionPoint - position).LengthSquared();
t.distance = (intersectionPoint - position).Length();
t.normal = faceNormal; //triangleEdgeNormals;
t.location = intersectionPoint;

result.KeepClosest(t);
}
}
}

private bool SpherePartialEdgeCollide(ref Vector3 start, ref Vector3 edgeV0, ref Vector3 edgeDir, ref Vector3 intersection)
{
// Find the point on line [edgeV0, edgeV0+edgeDir] that is closest to start
// See: http://softsurfer.com/Archive/algorithm_0102/algorithm_0102.htm

// Distance of a Point to a Ray or Segment
Vector3 w = start - edgeV0;

float c1 = Vector3.Dot(w, edgeDir);
if (c1 <= 0)
{
if ((start - edgeV0).LengthSquared() <= 1)
{
intersection = edgeV0;
return true;
}
else
{
return false;
}
}

float c2 = Vector3.Dot(edgeDir, edgeDir);
if (c2 <= c1)
{
Vector3 p1 = edgeV0 + edgeDir;
if ((start - p1).LengthSquared() <= 1)
{
intersection = p1;
return true;
}
else
{
return false;
}
}

float b = c1 / c2;

intersection = edgeV0 + b * edgeDir;

float distance = 0;
Vector3.DistanceSquared(ref start, ref intersection, out distance);

return (distance <= 1.0f);
}

/// <summary>
/// Determine for a given point (that lies on our triangle's plane) if
/// it lies within the triangle's borders or not.
///
/// Implemented by using the triangle's edge's planes.
/// </summary>
/// <param name="pt">a point on the triangle's plane</param>
/// <returns>true when point pt lies within the triangle</returns>
private bool PointInTriangle(ref Vector3 point, Vector3[] trianglePoints, Vector3[] triangleEdgeNormals)
{
Vector3 a = point - trianglePoints[0];
Vector3 b = point - trianglePoints[1];
Vector3 c = point - trianglePoints[2];

float v;

Vector3.Dot(ref a, ref triangleEdgeNormals[0], out v);
if (v >= 0)
{
return false;
}

Vector3.Dot(ref b, ref triangleEdgeNormals[1], out v);
if (v >= 0)
{
return false;
}

Vector3.Dot(ref c, ref triangleEdgeNormals[2], out v);
if (v >= 0)
{
return false;
}

return true;
}


I'm not sure why it is happening, can anyone enlighten me please? Thank you. [Fixed formatting - Zahlman] [Edited by - Zahlman on May 6, 2009 3:05:46 PM]

##### Share on other sites
OK I have solved the problem now.

Does anyone know of a Triangle Trianlge intersection method in C# per chance?

##### Share on other sites
You should pick up this book, it is seriously the greatest book i have ever seen on collision detection:

http://www.amazon.com/Real-Time-Collision-Detection-Interactive-Technology/dp/1558607323/ref=sr_1_1?ie=UTF8&s=books&qid=1241469247&sr=8-1

it is really full featured in the collision it talks about, and it talks about the theory and math behind the collision detection, as well as gives you source code in case you dont feel like digging into the theory and math (or can't understand it completely as is generally my case haha).

Really awesome book, every game programmer should own a copy (:

##### Share on other sites
I do own a copy! :)

It is a truly awesome book but I have problems porting some of the code over to C#.

An simple example would the following:

if (Max(v0.Y, v1.Y, v2.Y) < -e1 || Min(v0.Y, v1.Y, v2.Y) > e1)

Now in C# Math.Max can only take 2 arguments.

Assuming of course that the Maximum value is to be found with Max() how would I create a Max function that can take EITHER 2 or 3 arguments in and return the maximum value?

// Naff example for 2:        public static float Max(float a, float b)        {            float max = float.MinValue;            if (a > max)            {                max = a;            }            if (b > a)            {                max = b;            }        }

Thanks

##### Share on other sites
Quote:
 Original post by Spa8nkyNow in C# Math.Max can only take 2 arguments.Assuming of course that the Maximum value is to be found with Max() how would I create a Max function that can take EITHER 2 or 3 arguments in and return the maximum value?

You don't write a function that takes either 2 or 3 arguments; you write a function that takes 2 arguments, and one that takes 3 arguments, and give them the same name (i.e. overload the function).

The maximum of 3 elements can be found, for example, as the maximum of (the maximum of the first 2 elements) and the 3rd element.

Better yet, you can write a function that calculates the maximum of an array of elements; then you can pass in however many you need. Beware, I did a quick Google search to find examples of such a function and they were all buggy. :)

P.S. Checking if the maximum of however many values is less than a threshold is equivalent to checking if all the values are less than the threshold. Similarly for the minimum and greater-than check.

##### Share on other sites
Quote:
 Original post by ZahlmanYou don't write a function that takes either 2 or 3 arguments; you write a function that takes 2 arguments, and one that takes 3 arguments, and give them the same name (i.e. overload the function).

Awesome. I didn't know about this until now but that's probably only giving away that I am very new to this whole programming thang.

Thanks Zahlman.

##### Share on other sites
I have come up with the following for Max(). It doesn't have any bugs in it as far as I can tell.

        private float Max(float v1, float v2, float v3)        {            float[] array = new float[3];            float max = float.MinValue;            array[0] = v1;            array[1] = v2;            array[2] = v3;            foreach (float value in array)            {                if (value > max)                {                    max = value;                }            }            return max;        }

Feel free to rip it apart...

##### Share on other sites
Try something like

float m = Math.Max( v1, v2 );m = Math.Max( m, v3 );

You want to avoid allocating memory and looping in a function that could be potentially called hundreds or even thousands of times per frame depending on your scene size.

##### Share on other sites
Quote:
 Original post by Spa8nkyI have come up with the following for Max(). It doesn't have any bugs in it as far as I can tell.Comments please :D

There's no point in accepting 3 separate elements, putting them into an array and then iterating over the array. Iterating over an array allows you to avoid repeating per-item code, but then you have per-item code to *create* the array anyway.

Also, while initializing the maximum to float.MinValue will work, it's a little cleaner to initialize it to the first element and then check every *other* element.

Oh, and your variable names are bit strange, too. Why "v1" for a float?

I came up with this version for maximum-of-array, when I was looking for examples for you, found a horrible blog post and felt compelled to comment:

// Actually this is adapted slightly...public float max(float[] thearray) {  // Throws NullReferenceException if thearray is null  // Throws IndexOutOfRangeException if thearray is zero length  float max = thearray[0];  for (int i = 1; i != thearray.Length; ++i) {    if (thearray > max) { max = thearray; }  }  return max;}

But for a function accepting 3 separate floats, it makes more sense to just do what mightypigeon suggests - although we can simplify it even further:

public float max(float a, float b, float c) {  return Math.Max(Math.Max(a, b), c);}

##### Share on other sites
Huge thanks for the information guys.

1. 1
2. 2
3. 3
Rutin
15
4. 4
khawk
14
5. 5
frob
12

• 9
• 11
• 11
• 23
• 12
• ### Forum Statistics

• Total Topics
633660
• Total Posts
3013223
×