- General
-
Questions
0
BoundingSphere ,RayIntersection implementation ...
This discussion was imported from CodePlex
RuiTheAlmeida wrote at 2012-11-29 11:48:
Hi Objo and everybody,
First of all I want to congratulate you for this great Helix 3D tookit
I had to use one of the methods of class BoundingSphere and as it was not implemented so I did it. Feel free to test and include the code I'm sending here.
Best Regards,
Rui
public bool RayIntersection(Ray3D ray, out Point3D[] result)
{
result = null;
bool inter = false;
double h = this.center.X ;
double j = this.center.Y;
double k = this.center.Z;
double ra = this.radius;
double x1 = ray.Origin.X ;
double y1 = ray.Origin.Y;
double z1 = ray.Origin.Z;
double a = x1 - ray.Origin.X * ray.Direction.X;
double b = y1 - ray.Origin.Y * ray.Direction.Y;
double c = z1 - ray.Origin.Z * ray.Direction.Z;
//Quadratic solving
double aQ = a * a + b * b + c * c;
double bQ = 2 * a * (x1 - h) + 2 * b * (y1 - j) + 2 * c * (z1 - k);
double cQ = x1 * x1 + y1 * y1 + z1 * z1 + h * h + k * k + j * j - 2 * (j * y1 + k * z1 + h * x1) - ra * ra;
//Dscriminant
double Q = bQ * bQ - 4 * aQ * cQ;
if (Q >= 0)
{
double rx1 = (-bQ + Math.Sqrt(bQ * bQ - 4 * aQ * cQ)) / (2 * aQ); //First Root
double rx2 = (-bQ - Math.Sqrt(bQ * bQ - 4 * aQ * cQ)) / (2 * aQ); //Second Root
//first Intersection
Point3D I1 = new Point3D(x1 + a * rx1,y1 + b * rx1 , z1 + c * rx1);
//Second Intersection
Point3D I2 = new Point3D(x1 + a * rx2, y1 + b * rx2, z1 + c * rx2);
//ray inside sphere
if ((ray.Origin - this.center).Length <= this.radius)
{
result = new Point3D[1];
//Check if the vectors have the same direction
if (Vector3D.DotProduct(ray.Direction, I1 - ray.Origin) >= 0)
{
result[0] = I1;
}
else
{
result[0] = I2;
}
}
else
{
result = new Point3D[2];
result[0] = I1;
result[1] = I2;
}
inter = true;
}
else
{
inter = false;
}
return inter;
}
objo wrote at 2012-12-04 19:45:
thanks for the code! Did you make this yourself, or do you have a reference?
I created some unit tests for this code, but could not get my last case (no intersection) to work:
[Test, Ignore]
public void RayInterSection_NoIntersections()
{
var ray = new Ray3D(new Point3D(0.2, 0.3, 1), new Vector3D(1, 0.1, 0.1));
var sphere = new BoundingSphere(new Point3D(0.2, 0.3, 0), 1.0);
Point3D[] result;
Assert.IsFalse(sphere.RayIntersection(ray, out result));
Assert.AreEqual(sphere.Radius, sphere.Center.DistanceTo(result[0]), 1e-6, "Point is not on sphere.");
Assert.AreEqual(0, ray.GetNearest(result[0]).DistanceTo(result[0]), 1e-6, "Point is not on ray.");
}
RuiTheAlmeida wrote at 2012-12-07 05:12:
Hi objo,
I did the all code myself, and yes I have some references from Wikipedia and other common links that I will give.
I'm also finishing a detailed presentation with the all theoretical stuff, and I will post it all here.
Regards,
Rui
objo wrote at 2012-12-07 08:01:
Good! Can you also look at the "no intersections" case? Is there an error in my test?
I found some efficient implementations at
- http://wiki.cgsociety.org/index.php/Ray_Sphere_Intersection
- http://www.siggraph.org/education/materials/HyperGraph/raytrace/rtinter1.htm
- http://paulbourke.net/geometry/circlesphere/
- http://www.lighthouse3d.com/tutorials/maths/ray-sphere-intersection/
- http://www.scratchapixel.com/lessons/3d-basic-lessons/lesson-7-intersecting-simple-shapes/ray-sphere-intersection/
- http://www.ccs.neu.edu/home/fell/CSU540/programs/RayTracingFormulas.htm
RuiTheAlmeida wrote at 2012-12-09 19:11:
Hi Objo,
I've made some improvements, and you can find the new code below. I'm also posting some test cases. (I've changed your "no intersections" case )
You can also find my detailed explanation and references here
thanks,
Rui
public bool RayIntersection(Ray3D ray, out Point3D[] result) { result = new Point3D[2]; result[0] = new Point3D(double.PositiveInfinity, double.PositiveInfinity, double.PositiveInfinity); result[1] = new Point3D(double.PositiveInfinity, double.PositiveInfinity, double.PositiveInfinity); bool inter = false; double h = this.center.X; double j = this.center.Y; double k = this.center.Z; double ra = this.radius; double x1 = ray.Origin.X; double y1 = ray.Origin.Y; double z1 = ray.Origin.Z; //[a,b,c] = Ray.direction double a = ray.Direction.X; double b = ray.Direction.Y; double c = ray.Direction.Z; //Quadratic solving double aQ = a * a + b * b + c * c; double bQ = 2 * a * (x1 - h) + 2 * b * (y1 - j) + 2 * c * (z1 - k); double cQ = x1 * x1 + y1 * y1 + z1 * z1 + h * h + k * k + j * j - 2 * (j * y1 + k * z1 + h * x1) - ra * ra; //Dscriminant double Q = bQ * bQ - 4 * aQ * cQ; if (Q >= 0) //We have at least one possible Intersection { double rx1 = (-bQ + Math.Sqrt(bQ * bQ - 4 * aQ * cQ)) / (2 * aQ); //First Root double rx2 = (-bQ - Math.Sqrt(bQ * bQ - 4 * aQ * cQ)) / (2 * aQ); //Second Root //first Possible Intersection Point3D I1 = new Point3D(x1 + a * rx1, y1 + b * rx1, z1 + c * rx1); //Second Possible Intersection Point3D I2 = new Point3D(x1 + a * rx2, y1 + b * rx2, z1 + c * rx2); //Check if I1 is intersection by laying in the ray if (Vector3D.DotProduct(ray.Direction, I1 - ray.Origin) >= 0) { result[0] = I1; inter = true; } //Check if I2 is intersection by laying in the ray if (Vector3D.DotProduct(ray.Direction, I2 - ray.Origin) >= 0) { result[1] = I2; inter = true; } } return inter; }
TESTS:
[Test]
public void RayInterSection_HasIntersections()
{
var ray = new Ray3D(new Point3D(0.2, 0.3, 0), new Vector3D(1, 0, 0));
var sphere = new BoundingSphere(new Point3D(0.2, 0.3, 0), 1.0);
Point3D[] result;
Assert.IsTrue(sphere.RayIntersection(ray, out result));
Assert.AreEqual(sphere.Radius, sphere.Center.DistanceTo(result[0]), 1e-6, "Point is not on sphere.");
Assert.AreEqual(0, ray.GetNearest(result[0]).DistanceTo(result[0]), 1e-6, "Point "+ result[0] +" is not on ray.");
}
[Test]
public void RayInterSection_NoIntersections()
{
var ray = new Ray3D(new Point3D(0.2, 0.3, 1), new Vector3D(1, 0.1, 0.1));
var sphere = new BoundingSphere(new Point3D(0.2, 0.3, 0), 1.0);
Point3D[] result;
Assert.IsFalse(sphere.RayIntersection(ray, out result));
Assert.IsTrue( double.IsInfinity(sphere.Center.DistanceTo(result[0])), "There is a finite solution 1.");
Assert.AreNotEqual(0, ray.GetNearest(result[0]).DistanceTo(result[0]), "Point 1 is on ray.");
Assert.IsTrue(double.IsInfinity(sphere.Center.DistanceTo(result[1])), "There is a finite solution 2.");
Assert.AreNotEqual(0, ray.GetNearest(result[0]).DistanceTo(result[1]), "Point 2 is on ray.");
}
[Test]
public void RayInterSection_TwoIntersections()
{
var sphere = new BoundingSphere(new Point3D(0.2, 0.3, 0), 1.0);
var ray = new Ray3D(new Point3D(12, 23, 32), sphere.Center - new Point3D(12, 23, 32)); // vector away and pointing to the center of sphere
Point3D[] result;
Assert.IsTrue(sphere.RayIntersection(ray, out result));
Assert.AreEqual(sphere.Radius, sphere.Center.DistanceTo(result[0]), 1e-6, "Point 1 is not on sphere.");
Assert.AreEqual(0, ray.GetNearest(result[0]).DistanceTo(result[0]), 1e-6, "Point 1" + result[0] + " is not on ray.");
Assert.AreEqual(sphere.Radius, sphere.Center.DistanceTo(result[1]), 1e-6, "Point 2 is not on sphere.");
Assert.AreEqual(0, ray.GetNearest(result[1]).DistanceTo(result[1]), 1e-6, "Point 2 " + result[0] + " is not on ray.");
}
[Test]
public void RayInterSection_OnlyOneIntersection()
{
var sphere = new BoundingSphere(new Point3D(0.2, 0.3, 0), 1.0);
var ray = new Ray3D(sphere.Center, new Vector3D(1, 0.1, 0.1)); // vector origin in the center of sphere pointing away
Point3D[] result;
Assert.IsTrue(sphere.RayIntersection(ray, out result), "No intersection");
Assert.IsTrue(sphere.Center.DistanceTo(ray.Origin ) <= sphere.Radius,"Ray origin outside sphere");
Assert.IsFalse( double.IsInfinity(sphere.Center.DistanceTo(result[0])) && double.IsInfinity(sphere.Center.DistanceTo(result[1])), "No Intersections");
Assert.IsFalse(!double.IsInfinity(sphere.Center.DistanceTo(result[0])) && !double.IsInfinity(sphere.Center.DistanceTo(result[1])), "Two Intersections");
}
[Test]
public void RayInterSection_TwoTangentIntersections()
{
var sphere = new BoundingSphere(new Point3D(0.2, 0.3, 0), 1.0);
var ray = new Ray3D(new Point3D(sphere.Center.X + sphere.Radius, sphere.Center.Y + sphere.Radius, sphere.Center.Z + 50), new Point3D(sphere.Center.X + sphere.Radius, sphere.Center.Y, sphere.Center.Z) - new Point3D(sphere.Center.X + sphere.Radius, sphere.Center.Y + sphere.Radius, sphere.Center.Z + 50)); // ray tangent to sphere
Point3D[] result;
Assert.IsTrue(sphere.RayIntersection(ray, out result), "No intersection");
Assert.IsTrue(!double.IsInfinity(sphere.Center.DistanceTo(result[0])) && !double.IsInfinity(sphere.Center.DistanceTo(result[1])), "Less then two Intersections");
Assert.IsTrue(result[0]==result[1], "Solutions are not equal");
}
objo wrote at 2012-12-13 23:08:
thanks for the unit tests. I have done some modifications and submitted the changes!
Customer support service by UserEcho
