Image analysis – Image transformation or preprocessing – Measuring image properties
Reexamination Certificate
1999-12-29
2004-08-03
Do, Anh Hong (Department: 2624)
Image analysis
Image transformation or preprocessing
Measuring image properties
C345S420000, C345S421000, C345S422000
Reexamination Certificate
active
06771841
ABSTRACT:
BACKGROUND
This invention relates to determining a bounding shape for a collection of points.
One way to accelerate the drawing of graphics is to avoid processing objects that are not visible in a frame, e.g., objects that are “off camera.” One way to avoid processing off camera objects is to calculate a bounding shape that encompasses all of the points on a given object and then to use the bounding shape to test whether to exclude the entire object from processing. In a multi-dimensional graphics system, e.g., three-dimensional (“3-D”), the collection of points, e.g., (x,y,z) coordinates, on an object in a frame is the vertex pool for each object's bounding shape.
Bounding shapes can be useful in a variety of processing scenarios. For scene management, off camera objects may not need updating in every new frame. For example, a wheel of a car may be off camera in a particular frame. Processing the car but not the hidden (off camera) wheel decreases the amount of time and computation that would be necessary if the wheel were processed and then later discarded before the frame is finally rendered. An object such as the wheel will be off camera if its bounding shape is off camera. The test to determine if the bounding shape is off camera is much simpler than the test to determine if all points of the object are off camera.
For run-time animation, intersections of objects may need to be determined. For example, part of a wheel of a car may be obscured by a rock in the road. Refraining from processing the off camera portions of the wheel decreases the amount of time and computation that would be necessary if the entire wheel were processed and later partially obscured by the rock. If the bounding shapes of two objects such as the wheel and the rock do not intersect, then the objects do not intersect. Testing for the intersection of two bounding shapes is much simpler than testing for the intersection of two complicated objects.
In ray tracing rendering methods, the intersection of a ray with an object needs to be determined. A quick test to determine if the ray intersects a bounding shape of the object can be used to avoid work if there is no intersection. Any intersection points may give an initial range for some ray tracing methods.
One known method of calculating bounding spheres is described in Jack Ritter, “An Efficient Bounding Sphere,” in GRAPHICS GEMS, Andrew S. Glassner (ed.), Academic Press, Inc., Boston, 1990, pp. 301-03, 723-25. As shown in
FIG. 1
, the Ritter method finds the location and size of a bounding circle
10
, e.g., a 3-D sphere, for a collection of points
12
by the following steps. First, the method finds the points that have the minimum and maximum positions along each dimension, points
14
a
and
14
b
(x dimension) and
16
a
and
16
b
(y dimension). The method then finds the dimension that has the largest distance between its minimum and maximum points
14
or
16
. Here it is the y dimension between points
16
a
and
16
b
. The method next calculates an initial radius
18
of an initial bounding sphere
20
as one half the distance between the minimum and maximum points
16
a
and
16
b
. The method also calculates an initial center
22
of the initial bounding sphere
20
as the average of the minimum and maximum points
16
a
and
16
b.
Now, to see if the initial bounding sphere
20
encloses all points in the collection
12
, the method checks each point in the collection
12
to see if the distance between it and the initial center
22
is greater than the initial radius
18
. For the first point in the collection
12
that is outside the initial sphere
20
, the initial radius
18
and initial center
22
change to an intermediate radius
24
and an intermediate center
26
to define an intermediate bounding sphere
28
. All subsequent points are evaluated using the intermediate values
24
and
26
, which can change in the same way as the initial values
18
and
22
. Checking all of the points in the collection in this manner requires a number of calculations. The more points in the collection
12
, the higher the number of required calculations. Once all points in the collection
12
have been checked against the appropriate sphere
20
or
28
, the final bounding sphere
10
is defined by the appropriate radius
18
or
24
and center
22
or
26
.
SUMMARY
In general, in one aspect, the invention features determining a multi-dimensional bounding sphere for a collection of points by determining a multi-dimensional bounding box that encompasses all of the points, determining the center of the bounding sphere from the center of the bounding box, and determining the radius of the bounding sphere as the distance from the center of the bounding sphere to a location not closer to the center of the bounding sphere than any of the points in the collection of points.
In another aspect, the invention features an apparatus for determining a three-dimensional bounding sphere for a collection of points including a storage unit to store the collection of points and a processor. The processor is configured to determine a three-dimensional bounding box that encompasses all of the points, to determine the center of the bounding sphere from the center of the bounding box, and to determine the radius of the bounding sphere as the distance from the center of the bounding sphere to a location not closer to the center of the bounding sphere than any of the points in the collection of points.
In another aspect, the invention features determining a bounding sphere for a collection of points by determining a bounding box that encompasses all of the points, determining a center of the bounding box, determining the one of the points that is farthest away from the center, and determining a radius of the bounding sphere as the distance from the center to the one of the points that is farthest away from the center.
In another aspect, the invention features determining a bounding sphere for a collection of points by determining a bounding box that encompasses all of the points, determining a center of the bounding box, and determining a radius of the bounding sphere as the distance from the center to a corner of the bounding box.
Other advantages and features will become apparent from the following description and from the claims.
REFERENCES:
patent: 4885688 (1989-12-01), Crawford
patent: 5357600 (1994-10-01), Shirman et al.
patent: 5363475 (1994-11-01), Baker et al.
patent: 5757321 (1998-05-01), Billyard
patent: 5856924 (1999-01-01), Brost et al.
patent: 6016152 (2000-01-01), Dickie
patent: 6016487 (2000-01-01), Rioux et al.
patent: 6054991 (2000-04-01), Crane et al.
patent: 6263334 (2001-07-01), Fayyad et al.
patent: 6373489 (2002-04-01), Lu et al.
patent: 6556206 (2003-04-01), Benson et al.
patent: 6571012 (2003-05-01), Pettigrew
patent: 6573895 (2003-06-01), Carter et al.
patent: 6618047 (2003-09-01), Lim
Iones et al., “On Optimality of OBBs for Visibility Tests for Frustum Culling, Ray Shooting and Collision Detection”, IEEE Proceedings on Computer Graphics International, Jun. 1998, pps. 256-263.*
Ritter Jack, “An Efficient Bounding Sphere”, Graphics Gems, Andrew S. Glassner (ed.), Academic Press, Inc., Boston, 1990, pp. 301-303, 723-725.
O'Rourke Thomas P.
Plumb Jason R.
Do Anh Hong
Fish & Richardson P.C.
LandOfFree
Determining a bounding shape for a collection of points does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Determining a bounding shape for a collection of points, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Determining a bounding shape for a collection of points will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3300728