US4888583A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for rendering an image from data arranged in a constructive solid geometry format
Assignee: Tektronix Inc
•
Filing: 1988-03-14
•
Granted: 1989-12-19
•
Expires: 2008-03-14
Abstract
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.
Inventors
- 👤 Terry J. Ligocki
- 👤 Peter A. Borgwardt
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 19:00
CPC Classifications
G; G06; G06T; G06T17/00; G06T17/10
Claims Analysis
Total Claims: 18
Claim 1
Independent Claim
172 words
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.
Claim 2
Dependent Claim
172 words
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.
Claim 3
Dependent Claim
62 words
The method of claim 1 in which each volume element comprises a boundary and a volume element interior and in which the identification of the upper and lower bounds of the functions representing boundaries of the halfspaces comprises identifying extrema of the mathematical functions for each volume element, the extrema lying on the boundary and the volume element interior being separately identified.
Claim 4
Dependent Claim
58 words
The method of claim 2 in which each volume element comprises a boundary and a volume element interior, the boundary being of rectangular parallelepiped shape and including plural faces, edges, and vertices, and the extrema lying on the volume element interior and on the faces, edges, and vertices of the boundary of the volume element being separately identified.
Claim 5
Dependent Claim
28 words
The method of claim 2 in which the extrema of the mathematical functions are identified by calculating first partial derivatives of the mathematical functions for each volume element.
Claim 6
Dependent Claim
18 words
The method of claim 1 in which the image data are arranged in a constructive solid geometry format.
Claim 7
Dependent Claim
56 words
The method of claim 1 in which the upper bound is an approximation that is greater than or equal to the maximum value of the mathematical function in the volume element and the lower bound is an approximation that is less than or equal to the minimum value of the mathematical function in the volume element.
Claim 8
Dependent Claim
33 words
The method of claim 1 in which the identification of the upper and lower bounds of the mathematical functions representing boundaries of the halfspaces comprises calculating Taylor series expansions of the mathematical functions.
Claim 9
Dependent Claim
57 words
The method of claim 7 in which the Taylor series expansion can include positive and negative terms, the method further comprising approximating the Taylor series expansions of the mathematical functions so that only positive terms are included in the identification of the upper bound and only negative terms are included in the identification of the lower bound.
Claim 10
Dependent Claim
38 words
The method of claim 7 in which each volume element comprises an extreme minimum corner and an extreme maximum corner, the Taylor series for each mathematical function being expanded about the extreme minimum corner of the volume element.
Claim 11
Dependent Claim
196 words
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.
Claim 12
Dependent Claim
196 words
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.
Claim 13
Dependent Claim
62 words
The system of claim 10 in which each volume element comprises a boundary and a volume element interior and in which the identification of the upper and lower bounds of the functions representing boundaries of the halfspaces comprises identifying extrema of the mathematical functions for each volume element, the extrema lying on the boundary and the volume element interior being separately identified.
Claim 14
Dependent Claim
60 words
The system of claim 11 in which each volume element comprises a boundary and a volume element interior, the boundary being of a rectangular parallelepiped shape and including plural faces, edges, and vertices, the extrema lying on the interior of the volume element and on the faces, edges, and vertices of the boundary of the volume element being separately identified.
Claim 15
Dependent Claim
28 words
The system of claim 11 in which the extrema of the mathematical functions are identified by calculating first partial derivatives of the mathematical functions for each volume element.
Claim 16
Dependent Claim
33 words
The system of claim 10 in which the identification of the upper and lower bounds of the mathematical functions representing boundaries of the halfspaces includes calculating Taylor series expansions of the mathematical functions.
Claim 17
Dependent Claim
57 words
The system of claim 14 in which the Taylor series expansion can include positive and negative terms, the image processing means approximating the Taylor series expansions of the mathematical functions so that only positive terms are included in the identification of the upper bound and only negative terms are included in the identification of the lower bound.
Claim 18
Dependent Claim
38 words
The system of claim 14 in which each volume element comprises an extreme minimum corner and an extreme maximum corner, the Taylor series for each mathematical function being expanded about the extreme minimum corner of the volume element.
References Cited (Backward Citations)
US4649498A
Cited
US4785399A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1992-12-18 | 1993-06-19 | 1993-12-19 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1996-12-18 | 1997-06-19 | 1997-12-19 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2000-12-18 | 2001-06-19 | 2001-12-19 | $7700.00 | Window Closed / Lapsed |