Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1999-11-12
2002-12-03
Zimmerman, Mark (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S420000
Reexamination Certificate
active
06489959
ABSTRACT:
TECHNICAL FIELD OF THE INVENTION
The present invention relates to a method for converting OFF (object file format) from three-dimensional polygon data into quad edge data structure.
BACKGROUND OF THE INVENTION
Generally, typical shapes of data in computer graphics are three-dimensional polygons or triangles.
Three-dimensional polygons and triangles are displayed on a computer screen through a rendering process, which requires an efficient algorithm.
Three-dimensional polygon data are generated, modified, or added in application areas such as rendering, virtual reality, and animation.
To perform such operations efficiently, various data structures have been proposed, and quad edge data structure is one of them.
Quad edge data structure is an edge-based data structure and is able to describe graph and dual graph at the same time. In addition, quad edge data structure employs a splice operator, which is a topological operator.
Even though quad edge is a sufficient data structure for its purposes, an efficient method converting conventional data structure into quad edge data structure has not been discovered.
SUMMARY OF THE INVENTION
A method for converting OFF (object file format) of three-dimensional polygon data into a quad edge data structure is provided.
The method in accordance with an embodiment of the present invention includes the following steps. A first step is to determine if an input triangle in object file format is a whole new triangle. An additional step is to find two edges and perform a splice operation if the input triangle is a whole new triangle in the determination step. The two edges are connected with a vertex. A step is to find a quad edge from a vertex link of the quad edge data structure if the input triangle is not a whole new triangle in the determination step. The vertex link has a counterclockwise sequence. A further step is to find a candidate edge for a splice operation by comparing the link generated in the preprocessing stage and the vertex link of the quad edge data structure and performing the splice operation on the candidate edge and a new quad edge.
The method implemented in a computer system in accordance with an embodiment of the present invention includes the following steps. A first step is to determine if an input triangle of object file format is a whole new triangle. An additional step is to find two edges and perform a splice operation if the input triangle is a whole new triangle in the determination step. The two edges are connected with a vertex. A further step is to find a quad edge from a vertex link of the quad edge data structure if the input triangle is not a whole new triangle in the determination step. The vertex link has a counterclockwise sequence. Another additional step is to find a candidate edge for a splice operation by comparing the link generated in the preprocessing stage and the vertex link of the quad edge data structure and performing the splice operation on the candidate edge and a new quad edge.
REFERENCES:
patent: 4736306 (1988-04-01), Christensen et al.
patent: 4987554 (1991-01-01), Kaufman
patent: 6227850 (2001-05-01), Chishti et al.
Oh, Kwang M., “An Efficient Quad Edge Conversion of Polygonal Manifold Objects,”MIT Team, Multimedia section of Computer and Software Technology Lab., Electronics and Telecommunications Research Institute(ETRI), South Korea.
Guibas, Leonidas et al., “Primitives for the Manipulation of General Subdivisions and the Computation of Voronoi Diagrams,”ACM Transactions on Graphics, vol. 4, No. 2, Apr. 1985, pp. 74-122.
Lischinski, Dani, “Incremental Delaunay Triangulation,” 1994.
Choi Byoung Tae
Kim Jong Sung
Min Byung Eui
Oh Kwang-Man
Shim Kwang-Hyun
Electronics and Telecommunications Research Institute
Sealey Lance W.
Zimmerman Mark
LandOfFree
Method for converting three-dimensional polygon data into... 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 converting three-dimensional polygon data into..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for converting three-dimensional polygon data into... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2979674