Method and apparatus for rendering an image from data arranged in a constructive solid geometry format
First Claim
1. In a graphics display system that forms on a display screen a two-dimensional image representing a three-dimensional object, the two-dimensional image being defined by image data comprising mathematical functions that represent plural halfspaces having boundaries that divide an object space into interior object space regions lying inside the halfspaces and exterior object space regions lying outside the halfspaces, at least one of the halfspaces having a nonplanar boundary, a method of rendering the image, comprising:
- subdividing the object space into volume elements;
identifying for each volume element an upper bound and a lower bound for values of the mathematical functions representing the boundaries of the halfspaces;
determining which ones of the upper and lower bounds of the mathematical functions lie inside their corresponding halfspaces;
simplifying the image data in accordance with simplification identities to reduce the number of halfspaces, the simplification taking place whenever both the upper and lower bounds correspond to locations lying inside the halfspace; and
rendering the image on the display screen in accordance with the simplified image data.
1 Assignment
0 Petitions
Accused Products
Abstract
A method and an apparatus render on a display screen (14) an image of a three-dimensional object. The object is represented by image data arranged in a constructive solid geometry format including at least one halfspace that divides an object space (28) into an interior region that lies inside the halfspace and an exterior region that lies outside the halfspace. The boundary of the halfspace is defined by an implicit mathematical function. The method includes subdividing the object space into volume elements of either a cubical or rectangular parallelepiped shape. For each volume element, an upper bound and a lower bound are calculated to the values of each function defining the boundary of a halfspace. In a first preferred embodiment, the calculation of the upper and lower bounds of the function defining a halfspace within a volume element identifies all of the extrema of the function that lie in or on the boundary of the volume element. In a second preferred embodiment, the upper and lower bounds are calculated as approximations to the absolute maximum and minimum values, respectively, of the function. An image is rendered in accordance with whether the upper and lower bounds of the function defining the boundary of a halfspace show that all locations in a volume element are inside or outside the halfspace.
-
Citations
16 Claims
-
1. In a graphics display system that forms on a display screen a two-dimensional image representing a three-dimensional object, the two-dimensional image being defined by image data comprising mathematical functions that represent plural halfspaces having boundaries that divide an object space into interior object space regions lying inside the halfspaces and exterior object space regions lying outside the halfspaces, at least one of the halfspaces having a nonplanar boundary, a method of rendering the image, comprising:
-
subdividing the object space into volume elements; identifying for each volume element an upper bound and a lower bound for values of the mathematical functions representing the boundaries of the halfspaces; determining which ones of the upper and lower bounds of the mathematical functions lie inside their corresponding halfspaces; simplifying the image data in accordance with simplification identities to reduce the number of halfspaces, the simplification taking place whenever both the upper and lower bounds correspond to locations lying inside the halfspace; and rendering the image on the display screen in accordance with the simplified image data. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
10. A graphics display system, comprising:
-
a display screen on which a two-dimensional image representing a three-dimensional object is formed, the two-dimensional image being formed in accordance with image data that include plural halfspaces having boundaries which are represented by mathematical functions and which divide an object space into interior regions that are inside the halfspaces and exterior regions that are outside the halfspaces, at least one of the halfspaces having a nonplanar boundary; and image data processing means communicating with the display screen for generating from the image data a control signal that controls the formation of the two-dimensional image on the display screen;
the control signal being generated by subdividing the object space into volume elements, identifying with respect to each volume element an upper bound and a lower bound for the values of the mathematical functions representing the boundaries of the halfspaces, determining which ones of the upper and lower bounds of the mathematical functions lie inside their corresponding halfspaces, and simplifying the image data in accordance with simplification identities to reduce the number of halfspaces, the simplification taking place whenever both the upper and lower bounds correspond to locations lying inside the halfspace. - View Dependent Claims (11, 12, 13, 14, 15, 16)
-
Specification