Computer graphics processing and selective visual display system – Computer graphics processing – Graph generating
Reexamination Certificate
1999-08-30
2001-03-27
Powell, Mark R. (Department: 2672)
Computer graphics processing and selective visual display system
Computer graphics processing
Graph generating
C345S441000
Reexamination Certificate
active
06208352
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to computer graphics, and more particularly, to systems and methods for the computerized solution of the intersection of polygons.
Current systems focus on the interior of a polygon and employ rasterized approximations to the target and intersecting polygons. The intersection is then produced by scanning the sets of polygons to produce a raster of the result. The perimeter of the resulting raster is then finally converted to a description of its perimeter.
One problem with known prior art systems, however, is that a raster is an approximate solution since the raster entails discrete sampling of the problem space. Increased accuracy can only be obtained by using a finer raster. In some cases the full mathematical precision of the solution cannot be obtained without encountering round-off difficulties with the computer representation of numbers. Using a raster approximation is also very slow and increases with the absolute size of the intersecting polygons.
SUMMARY OF THE INVENTION
Accordingly, the present invention is directed to methods and systems for the computerized solution of the intersection of polygons that substantially obviates the problems of the prior art.
In accordance with the purposes of the invention, as embodied and broadly described herein, the invention comprises a method for subtracting a first subtracting polygon from a product polygon, including determining an intersection of the first subtracting polygon and the product polygon, wherein the first subtracting polygon is represented by a plurality of vertices in a first subtracting polygon linked list and the product polygon is represented by a plurality of vertices in a product polygon linked list, inserting a first intersection node at the intersection in the product polygon linked list, inserting a second intersection node at the intersection in the first subtracting polygon linked list, and creating a new linked list. The new linked list is created by determining a first vertex in the product polygon linked list, adding vertices from the product polygon linked list to the new linked list until the first intersection node is encountered by following the product polygon linked list from the determined first vertex, if an intersection node is encountered, adding vertices from the first subtracting product polygon linked list to the new linked list until a third intersection node is encountered by following the first subtracting polygon linked list from the second intersection node, and repeating the above subsets until returned to the determined first vertex.
In another aspect the invention comprises an apparatus for subtracting a first subtracting polygon from a product polygon, including a memory for storing a program and a processor for running the program. The program is for determining an intersection of the first subtracting polygon and the product polygon, wherein the first subtracting polygon is represented by a plurality of vertices in a first subtracting polygon linked list and the product polygon is represented by a plurality of vertices in a product polygon linked list, inserting a first intersection node at the intersection in the product polygon linked list, inserting a second intersection node at the intersection in the first subtracting polygon linked list, and creating a new linked list. The new linked list is created by determining a first vertex in the product polygon linked list, adding vertices from the product polygon linked list to the new linked list until the first intersection node is encountered by following the product polygon linked list from the determined first vertex, if an intersection node is encountered, adding vertices from the first subtracting product polygon linked list to the new linked list until a third intersection node is encountered by following the first subtracting polygon linked list from the second intersection node, repeating the above substeps until returned to the determined first vertex.
In another aspect the invention comprises a computer-readable medium whose contents cause a computer system to subtract a first subtracting polygon from a product polygon, by performing the steps of determining an intersection of the first subtracting polygon and the product polygon, wherein the first subtracting polygon is represented by a plurality of vertices in a first subtracting polygon linked list and the product polygon is represented by a plurality of vertices in a product polygon linked list, inserting a first intersection node at the intersection in the product polygon linked list, inserting a second intersection node at the intersection in the first subtracting polygon linked list, and creating a new linked list. The new linked list is created by determining a first vertex in the product polygon linked list, adding vertices from the product polygon linked list to the new linked list until the first intersection node is encountered by following the product polygon linked list from the determined first vertex, if an intersection node is encountered, adding vertices from the first subtracting product polygon linked list to the new linked list until a third intersection node is encountered by following the first subtracting polygon linked list from the second intersection node, and repeating the above subsets until returned to the determined first vertex.
This summary of the invention and the following detailed description should not restrict the scope of the claimed invention. Both provide examples and explanations to enable others to practice the invention. The accompanying drawings, which form part of the description for carrying out a best mode of the invention, show several embodiments of the invention, and together with the description, explain the principles of the invention.
REFERENCES:
patent: 4805127 (1989-02-01), Hata et al.
patent: 5048099 (1991-09-01), Lee
patent: 5129051 (1992-07-01), Cain
patent: 5371840 (1994-12-01), Fisher et al.
Cummingham G. F.
General Dynamics Government Systems Corp.
Jenner & Block LLC
Powell Mark R.
LandOfFree
Method for the computerized solution of the intersection of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for the computerized solution of the intersection of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for the computerized solution of the intersection of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2449393