Cheap well-behaved affine transformation of bounding spheres
US6664975B1 · kind B1 · utility
Assignee
Inventor
Key dates
| Filing date | May 23, 2000 |
| Grant date | Dec 16, 2003 |
| Priority date | — |
| Expiry date | May 23, 2020 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F17/10
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
The present invention relates to a method and apparatus for obtaining a bounding sphere for the ellipsoid that results when an affine transformation matrix transforms a bounding volume. The present invention accomplishes this by using Gershgorin intervals to obtain a new radius for the bounding volume. The invention operates on a scene graph, which is comprised of a number of nodes arranged in a hierarchical organization. At least one of these nodes is an affine transformation matrix, which is used for operations such as rotations, scaling, and translations. Associated with the transformation matrix is a bounding sphere. The present invention calculates the radius of a new bounding sphere that encircles the ellipsoid formed when the affine matrix transforms the old bounding volume. The use of Gershgorin intervals is fast and yields accurate results. Thus, the present invention provides for a method and apparatus that is computationally fast and produces a well-behaved affine transformation of bounding spheres.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.