Graphics Reference
In-Depth Information
// Sphere and triangle intersect if the (squared) distance from sphere
// center to point p is less than the (squared) sphere radius
Vectorv=p-s.c;
return Dot(v, v) <= s.r * s.r;
}
To avoid an expensive square root operation, the squared distances are compared
in the code.
5.2.8
Testing Sphere Against Polygon
Testing whether a sphere intersects a polygon could be done analogously to the
last few tests: computing the closest point on the polygon to the sphere center and
comparing the distance between these two points to the sphere radius. The closest
point on a polygon to a given point
P
can be computed by triangulating the polygon
and computing the closest point to
P
for each triangle, and returning the point closest
to
P
as the result. This is not very efficient for large polygons, however, as
n
−
2 triangle
tests would have to be performed for a polygon with
n
vertices.
An alternative method is to perform the following tests in turn:
1. Test if the sphere intersects the plane of the polygon. Exit with false if not.
2. Test each edge of the polygon to see if it pierces the sphere. Exit with true if so.
3. Project the sphere center onto the plane of the polygon. Perform a point-in-
polygon test (see Section 5.4.1) to see if this point is inside the polygon. If so, exit
with true. Otherwise, exit with false, as the sphere does not intersect the polygon.
The following code fragment illustrates how the test can be implemented.
// Test whether sphere s intersects polygon p
int TestSpherePolygon(Sphere s, Polygon p)
{
// Compute normal for the plane of the polygon
Vector n = Normalize(Cross(p.v[1] - p.v[0], p.v[2] - p.v[0]));
// Compute the plane equation for p
Plane m; m.n = n; m.d = -Dot(n, p.v[0]);
// No intersection if sphere not intersecting plane of polygon
if (!TestSpherePlane(s, m)) return 0;
// Test to see if any one of the polygon edges pierces the sphere
