Error-bounded antialiased rendering of complex scenes
First Claim
1. A computer implemented method for rendering a 3-D scene onto a display having pixels, the 3-D scene being a view of a model space which includes a plurality of surface primitives, comprising the steps of:
- a) organizing the model space into a quadtree data structure having a plurality of nodes including a root node and child nodes;
b) traversing the quadtree data structure to cull nodes which are completely hidden and to insert primitives associated with any of said nodes which may be visible into an image-space quadtree data structure;
c) recursively subdividing the quadtree data structure to resolve the visibility of primitives in a given pixel and determining an output pixel value for the given pixel by applying an antialiasing filter to color components of the primitives visible in the given pixel wherein the output pixel value is determined by interval multiplication of the color components with intervals contained in a table of intervals for the filter; and
d) displaying the 3-D scene on the display with hidden primitives removed therefrom and with antialiased color components of the visible primitives.
3 Assignments
0 Petitions
Accused Products
Abstract
An antialiased rendering algorithm that guarantees that each pixel of the output image is within a user-specified error tolerance of the filtered underlying continuous image wherein an object-space octree is used to cull hidden geometry rapidly, and a quadtree data structure is used to test visibility through image-space regions. When regions are too complex, quadtree subdivision is employed to simplify the geometry. Subdivision stops when the algorithm can either analytically filter the required region or bound the convolution integral appropriately with interval methods.
110 Citations
14 Claims
-
1. A computer implemented method for rendering a 3-D scene onto a display having pixels, the 3-D scene being a view of a model space which includes a plurality of surface primitives, comprising the steps of:
-
a) organizing the model space into a quadtree data structure having a plurality of nodes including a root node and child nodes; b) traversing the quadtree data structure to cull nodes which are completely hidden and to insert primitives associated with any of said nodes which may be visible into an image-space quadtree data structure; c) recursively subdividing the quadtree data structure to resolve the visibility of primitives in a given pixel and determining an output pixel value for the given pixel by applying an antialiasing filter to color components of the primitives visible in the given pixel wherein the output pixel value is determined by interval multiplication of the color components with intervals contained in a table of intervals for the filter; and d) displaying the 3-D scene on the display with hidden primitives removed therefrom and with antialiased color components of the visible primitives. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. A computer apparatus for rendering a 3-D scene onto a display having pixels, the 3-D scene being a view of a model space which includes a plurality of surface primitives, comprising:
-
means for organizing the model space into a quadtree data structure having a plurality of nodes including a root node and child nodes; means for traversing the quadtree data structure to cull nodes which are completely hidden and to insert primitives associated with any of said nodes which may be visible into an image-space quadtree data structure; means for recursively subdividing the quadtree data structure to resolve the visibility of primitives in a given pixel and determining an output pixel value for the given pixel by applying an antialiasing filter to color components of the primitives visible in the given pixel wherein the output pixel value is determined by interval multiplication of the color components with intervals contained in a table of intervals for the filter; and means for displaying the 3-D scene on the display with hidden primitives removed therefrom and with antialiased color components of the visible primitives. - View Dependent Claims (9, 10, 11, 12, 13, 14)
-
Specification