Help end child hunger

Geometric Approach – Testing Points and Spheres

Prev: Implementation Next: Testing Boxes
 

Once the planes have been extracted, it is possible to find out if a point is inside or outside the frustum. Computing the signed distance tells us which side of the plane the point is on. Assuming that the planes’ normals are pointing inwards, then if the signed distance is negative the point is outside the frustum. Otherwise the point is on the right side of the plane.

The following function of the class FrustumG shows a possible implementation. The parameter is the point to be tested.

int FrustumG::pointInFrustum(Vec3 &p) {

	int result = INSIDE;

	for(int i=0; i < 6; i++) {
		if (pl[i].distance(p) < 0)
			return OUTSIDE;
	}
	return(result);
}

Notice the early way out of the function. If a point is inside the frustum it must be on the right side of every plane, therefore in order to accept a point, all six planes must be tested. However, to reject a point all that is needed is for the point to be on the wrong side of a single plane.

To test an object, all vertices could be tested. If all the vertices are on the wrong side of a plane then the object would be outside the frustum. However this test may be too time consuming for large objects. Consider a car with 10000 polygons, in the worst case scenario 10000 tests would have to be done to reach a conclusion of the whereabouts of the car relative to the frustum.

In this case it is very likely that asking the graphics hardware to render the car would have been faster than performing all the tests and then, on top of it, maybe having to render the car anyway.

Hence for complex objects testing all vertices is not an option, instead bounding volumes are used. Several types of bounding volumes exist, and two of the most popular, for their simplicity, are spheres and boxes.

Finding a sphere that contains all the vertices of the car is an easy task (the average of the vertices is the center of the sphere, and the radius is the distance to the farthest vertex), and testing a sphere is extremely fast as it will be shown next.

There is a trade-of in here: simplicity of the test implies faster but less accurate testing: the car may be outside the frustum, but the sphere may be partially inside. Less tests imply that potentially stuff that is outside of the frustum will be sent to the graphics hardware. But as long as there is a good match between the bounding volume and the object, this strategy does compensate.

Spheres

Testing spheres is similar to testing points, except for the radius of the sphere. A sphere is out of the frustum if its center is on the wrong side of at least one plane and the distance to the plane is greater than the radius of the sphere. If the absolute value of the distance is smaller than the radius then the sphere intersects the plane, meaning that the sphere is partially on the right side of the plane. Otherwise the sphere is completely on the right side of the plane.

int FrustumG::sphereInFrustum(Vec3 &p, float radius) {

	float distance;
	int result = INSIDE;

	for(int i=0; i < 6; i++) {
		distance = pl[i].distance(p);
		if (distance < -radius)
			return OUTSIDE;
		else if (distance < radius)
			result =  INTERSECT;
	}
	return(result);
}

The function receives as parameters the center and radius of the sphere and tests the distance against all planes.

 

Prev: Implementation Next: Testing Boxes
 

7 Responses to “Geometric Approach – Testing Points and Spheres”

  1. The sphere test contains false positives when the sphere intersects 2 planes in a corner and don’t intersect the frustum.

  2. What is a negative distance?
    Are not all distances between 2 vectors or points greater or equal than null?
    If pl[i] ist a vector and p is a vector, the distance is
    sqrt( (pl[i].x-p.x)*pl[i].x-p.x)+(pl[i].y-p.y)*pl[i].y-p.y)+(pl[i].z-p.z)*pl[i].z-p.z) )
    is always greater or equal than null.

    • Hi Marvin,

      You’re right when you say that a distance is always positive. When considering the distance from a point to a plane, computed as shown in here, see section “Distance from a point to a plane”, the distance is the absolute value of a computation. The initial result of that computation, without the absolute value step, can be positive or negative, hence the term “signed distance”. This “signed distance” tells us in which side of the plane the point is located and that’s exactly what we want when we are doing View Frustum Culling.

      Hope this helps :-)

      • Hi
        Thanks for your fast reply.
        Where i take my planes.
        From modelViewMatrix, perspectiveMatrix or modelViewProjectionMatrix?

        • Hi Marvin,

          Considering the clip space approach its the projection-view-model matrix.

          • Thanks,yes it is so. So my points for culling test
            must also lay in this space?

          • Hi Marvin,

            The points must be in the same space where the planes we’re extracted. If following the clip space approach then the points must be in clip space. If you’re considering the geometric approach then the points should be in world space.

Leave a Reply

(required)

(required)

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

© 2014 Lighthouse3d.com Suffusion theme by Sayontan Sinha