US6226003B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for rendering silhouette and true edges of 3-D line drawings with occlusion
Assignee: Microsoft Technology Licensing LLC
•
Filing: 1998-08-11
•
Granted: 2001-05-01
•
Expires: 2018-08-11
Abstract
Abstract A computer-implemented method for generating three dimensional line drawings in which only silhouette edges and true edges that are visible are displayed. The color, depth, and stencil buffers are respectively initialized to background color, farthest value, and zero. In a first pass, all polygons are rendered by filling all pixels within their boundaries. At each pixel, only its depth value is modified by selecting the nearer of either the current depth value or the new depth value. This creates a depth image in the depth buffer used for occlusion detection. In a second pass, all the polygons of a particular orientation are rendered by drawing lines from vertex to vertex for each of the polygons. The pixel values are modified only when the depth comparison passes (i.e., the pixel is visible and not occluded). Each time a particular pixel is modified, its corresponding stencil value is toggled from 0 to 1 or from 1 back to 0. Afterwards, the value of each pixel in the frame buffer is set to the line color if and only if its corresponding stencil value is 1. Lastly, all true edges are rendered. For the true edges, only those pixels which pass the depth comparison are modified by setting them to the line color. In the end, only the visible true edges and silhouette edges are drawn for display.
Inventors
- 👤 Kurt Akeley
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 18:01
CPC Classifications
G; G06; G06T; G06T15/00; G06T15/10; G06T15/40
Claims Analysis
Total Claims: 22
Claim 1
Independent Claim
129 words
A method for generating a three-dimensional line drawing of an object, comprising the computer implemented steps of: initializing a color buffer and a depth buffer; creating a depth image stored in the depth buffer; rendering a plurality of polygons by drawing lines between vertices of the polygons, wherein pixels corresponding to the lines are modified if the pixels pass a depth comparison according to the depth image; setting a mode of operation for toggling a bit each time the pixel value in the frame buffer is changed to determine the number of times the pixel has been rendered; changing a pixel value in a frame buffer to a line color according to the number of times the pixel has been rendered according to the toggling of the stencil buffer.
Claim 2
Independent Claim
129 words
A method for generating a three-dimensional line drawing of an object, comprising the computer implemented steps of: initializing a color buffer and a depth buffer; creating a depth image stored in the depth buffer; rendering a plurality of polygons by drawing lines between vertices of the polygons, wherein pixels corresponding to the lines are modified if the pixels pass a depth comparison according to the depth image; setting a mode of operation for toggling a bit each time the pixel value in the frame buffer is changed to determine the number of times the pixel has been rendered; changing a pixel value in a frame buffer to a line color according to the number of times the pixel has been rendered according to the toggling of the stencil buffer.
Claim 3
Dependent Claim
45 words
The method of claim 1 , wherein the step of creating the depth image is comprised of the steps of: rendering the polygons by filling pixels corresponding to the polygons; biasing depth values for the pixels as a function of depth slopes of corresponding polygons.
Claim 4
Dependent Claim
39 words
The method of claim 2 , wherein the depth buffer is initialized to a farthest depth value and the depth image is created by selecting between the nearer of either an existing depth value or a new depth value.
Claim 5
Dependent Claim
42 words
The method of claim 1 further comprising the step of: setting a mode of operation for toggling a stencil buffer each time the pixel value in the frame buffer is changed to determine the number of times the pixel has been rendered.
Claim 6
Dependent Claim
37 words
The method of claim 1 further comprising the step of: changing pixel values corresponding to a true edge of the object to the line color if the pixel values of the true edge pass the depth comparison.
Claim 7
Dependent Claim
146 words
In a display system, a method for generating a line drawing corresponding to an object, wherein only true edges and silhouette edges of the object which are visible are displayed, comprising the steps of: setting a color buffer to a background color; setting a depth buffer to a depth value corresponding to a distance that is farthest away from a view point; performing occlusion culling; rendering pixels of a plurality of polygons corresponding to the object; determining a number of times each of the pixels has been rendered by toggling a bit each time the pixel is rendered, wherein the bit is toggled from one to zero or from zero back to one; setting pixels which have been rendered a particular number of times to a predetermined color; modifying pixels of the true edges which have not been culled; drawing the pixels in the frame buffer.
Claim 8
Dependent Claim
146 words
In a display system, a method for generating a line drawing corresponding to an object, wherein only true edges and silhouette edges of the object which are visible are displayed, comprising the steps of: setting a color buffer to a background color; setting a depth buffer to a depth value corresponding to a distance that is farthest away from a view point; performing occlusion culling; rendering pixels of a plurality of polygons corresponding to the object; determining a number of times each of the pixels has been rendered by toggling a bit each time the pixel is rendered, wherein the bit is toggled from one to zero or from zero back to one; setting pixels which have been rendered a particular number of times to a predetermined color; modifying pixels of the true edges which have not been culled; drawing the pixels in the frame buffer.
Claim 9
Dependent Claim
13 words
The method of claim 6 further comprising the step of performing depth aliasing.
Claim 10
Dependent Claim
25 words
The method of claim 6 further comprising the step of toggling a stencil buffer to determine the number of times the pixel has been rendered.
Claim 11
Dependent Claim
19 words
The method of claim 6 , wherein frame buffer values corresponding to the line drawing are updated in real-time.
Claim 12
Dependent Claim
29 words
The method of claim 6 further comprising the step of performing a signed area calculation of projected vertexes of a facet to determine whether the facet faces the viewpoint.
Claim 13
Independent Claim
109 words
A method for rendering a computer-generated hidden-line drawing, comprising the steps of: processing an unfilled proper solid into a plurality of polygons; determining whether pixels of the polygons is visible or hidden; determining a number of times pixels corresponding to a non-hidden edge is rendered; setting a mode of operation for toggling a stencil buffer each time the pixel value in the frame buffer is changed to determine the number of times the pixel has been rendered; modifying the pixels corresponding to the non-hidden edge according to the number of times the pixels of the non-hidden edge was rendered; drawing the pixels of the non-hidden edge which were modified.
Claim 14
Independent Claim
109 words
A method for rendering a computer-generated hidden-line drawing, comprising the steps of: processing an unfilled proper solid into a plurality of polygons; determining whether pixels of the polygons is visible or hidden; determining a number of times pixels corresponding to a non-hidden edge is rendered; setting a mode of operation for toggling a stencil buffer each time the pixel value in the frame buffer is changed to determine the number of times the pixel has been rendered; modifying the pixels corresponding to the non-hidden edge according to the number of times the pixels of the non-hidden edge was rendered; drawing the pixels of the non-hidden edge which were modified.
Claim 15
Dependent Claim
24 words
The method of claim 11 further comprising the steps of: identifying real edges separating two different surfaces of the solid; displaying the real edges.
Claim 16
Dependent Claim
56 words
The method of claim 11 , wherein the step of determining whether each of the facets is visible or hidden is performed according to a backfacing facet elimination scheme in which polygons facing a viewer are designated with a first vertex orientation and polygons facing away from the viewer are designated with a different vertex orientation.
Claim 17
Dependent Claim
41 words
The method of claim 11 , wherein the step of determining the number of times an edge is rendered is performed by initially clearing a buffer and toggling a bit stored in a buffer each time a corresponding pixel is rendered.
Claim 18
Dependent Claim
13 words
The method of claim 11 further comprising the step of executing depth biasing.
Claim 19
Dependent Claim
15 words
The method of claim 11 , wherein hidden-line drawings of the object are generated interactively.
Claim 20
Dependent Claim
222 words
A computer readable memory having instructions stored thereon for generating a three-dimensional line drawing, the instructions comprising computer implemented steps of: initializing a plurality of buffers; creating a depth image for occlusion detection; rendering silhouette edges with occlusion detection; rendering true edges with occlusion detection; clearing a color buffer to a background color; clearing a depth buffer to a farthest value; clearing a stencil buffer to zero; rendering all polygons of an object by filling all pixels within the polygons; biasing depth values of the pixels away from a viewpoint based on a maximum depth slope of the polygons; modifying depth values of the pixels by selecting the nearer of either a depth value currently stored in the depth buffer or a new depth value; rendering all polygons of a particular orientation by drawing lines from one vertex to another vertex; modifying pixel values only if the pixels pass depth comparison; setting the stencil buffer to a mode which causes a stencil value to toggle each time a corresponding pixel value is modified; setting pixel values in the frame buffer to a specified color value according to stencil values stored in the stencil buffer; modifying pixel values of true edges of the object if the pixels passes the depth comparison; displaying an image according to color values stored in the frame buffer.
Claim 21
Dependent Claim
222 words
A computer readable memory having instructions stored thereon for generating a three-dimensional line drawing, the instructions comprising computer implemented steps of: initializing a plurality of buffers; creating a depth image for occlusion detection; rendering silhouette edges with occlusion detection; rendering true edges with occlusion detection; clearing a color buffer to a background color; clearing a depth buffer to a farthest value; clearing a stencil buffer to zero; rendering all polygons of an object by filling all pixels within the polygons; biasing depth values of the pixels away from a viewpoint based on a maximum depth slope of the polygons; modifying depth values of the pixels by selecting the nearer of either a depth value currently stored in the depth buffer or a new depth value; rendering all polygons of a particular orientation by drawing lines from one vertex to another vertex; modifying pixel values only if the pixels pass depth comparison; setting the stencil buffer to a mode which causes a stencil value to toggle each time a corresponding pixel value is modified; setting pixel values in the frame buffer to a specified color value according to stencil values stored in the stencil buffer; modifying pixel values of true edges of the object if the pixels passes the depth comparison; displaying an image according to color values stored in the frame buffer.
Claim 22
Dependent Claim
193 words
The computer readable memory of claim 17 , wherein the instructions further comprise the steps of: clearing a color buffer to a background color; clearing a depth buffer to a farthest value; clearing a stencil buffer to zero; rendering all polygons of an object by filling all pixels within the polygons; biasing depth values of the pixels away from a viewpoint based on a maximum depth slope of the polygons; modifying depth values of the pixels by selecting the nearer of either a depth value currently stored in the depth buffer or a new depth value; rendering all polygons of a particular orientation by drawing lines from one vertex to another vertex; modifying pixel values only if the pixels pass depth comparison; setting the stencil buffer to a mode which causes a stencil value to toggle each time a corresponding pixel value is modified; setting pixel values in the frame buffer to a specified color value according to stencil values stored in the stencil buffer; modifying pixel values of true edges of the object if the pixels passes the depth comparison; displaying an image according to color values stored in the frame buffer.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2004-04-30 | 2004-10-30 | 2005-05-01 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2008-04-30 | 2008-10-30 | 2009-05-01 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2012-04-30 | 2012-10-30 | 2013-05-01 | $7700.00 | Window Closed / Lapsed |