Connectivity encoding and decoding of polygon meshes

Details Connectivity encoding and decoding of polygon meshes Connectivity encoding and decoding of polygon meshes

2006-08-29

2006-08-29

Chauhan, Ulka (Department: 2628)

Computer graphics processing and selective visual display system

Computer graphics processing

Adjusting level of detail

C345S419000, C345S418000, C382S232000, C382S241000

Reexamination Certificate

active

07098916

ABSTRACT:
Methods of connectivity encoding polygonal mesh representations of objects are described, along with methods of decoding encoded connectivity information for polygonal mesh representations of objects. In the encoding process, an active vertex queue is initialized with one or more vertices incident to a seed face. A vertex is selected from the queue, and the ring of the vertex traversed. If an unprocessed face is encountered during the traversal, the degree of the face, and the valences of any unprocessed vertices incident to the face are output. Any such unprocessed vertices are also entered into the queue. The method iterates until no more vertices remain on the active queue. In one implementation, an encoded data stream is output, which comprises two logical streams, one for face-degree information and the other for vertex-valence information. In the decoding process, the encoded data stream is received, and the connectivity of the mesh regenerated.

REFERENCES:
Isenburg, M. and J. Snoeyink. “Face fixer: compressing polygon meshes with properties.” Int. Conf. on Comp. Graphics and Inter. Techniques. Siggraph 2000, pp. 263-270. □□ISBN:1-58113-208-5.
Alliez, P. and M. Desbrun. “Progressive compression for lossless transmission of triangle meshes”. Proc. 28th Annual Conf. on Comp. Graph. and Int. Tech. (SIGCHI). 2001, pp. 195-202, ISBN: 1-58113-374-X.
Alliez, P. and Desbrun, M.,Valence-Driven Connectivity Encoding of 3D Meshes, Eurographics 2001 Conference Proceedings, Sep. 2001, pp. 480-489.
Bar-Yehuda, R. and Gotsman, C.,Time/Space Tradeoffs for Polygon Mesh Rendering, ACM Transactions on Graphics 15 (2), Apr. 1996, pp. 141-152.
Chow, M.,Optimized Geometry Compression for Real-Time Rendering, IEEE Visualization 97 Conference Proceedings, 1997, pp. 347-354.
Chuang, R. C.-N., et al.,Compact Encodings of Planar Graphs via Canonical Orderings and Multiple Parentheses, Automata, Languages and Programming, 1998, pp. 118-129.
Deering, M.,Geometry Compression, ACM SIGGRAPH 98 Conference Proceedings, 1995, pp. 13-20.
Gumhold, S.New Bounds on the Encoding of Planar Triangulations, Tech. Rep. WSI-2000-1, Wilhelm Schickard Institute for Computer Science, Tübingen, Mar. 2000.
Gumhold, S. and Strasser, W.,Real Time Compression of Triangle Mesh Connectivity, SIGGRAPH 98 Conference Proceedings, 1998, pp. 133-140.
Isenburg, M.,Compression Polygon Mesh Connectivity with Degree Duality Prediction, Graphics Interface, May 2002.
Isenburg, M. and Snoeyink, J.,Spirale Reversi: Reverse Decoding of the Edgebreaker Encoding, 12thCanadian Conference on Computational Geometry, 2000, 247-256.
Isenburg, M. and Snoeyink, J.,Face Fixer: Compressing Polygon Meshes With Properties, ACM SIGGRAPH 2000 Conference Proceedings, 2000, pp. 263-270.
Keeler, K. and Westbrook, J.,Short Encodings of Planar Graphs and Maps, Aug. 3, 1993,reprinted inDAMATH: Discrete Applied Mathematics and Combinatorial Operations Research and Computer Science 58, 1995.
King, D. and Rossignac, J.,Guaranteed 3.67V bit Encoding of Planar Triangle Graphs, 11thCanadian Conference on Computational Geometry, 1999, 146-149.
King, D. et al.,Connectivity Compression for Irregular Quadrilateral Meshes, GVU Tech. Rep. GVU-GIT-99-36, Georgia Tech, Nov. 19, 1999, revised Mar. 31, 2000.
Kronrod, B. and Gotsman, C.,Efficient Coding of Non-Triangular Mesh Connectivity, Graphical Models 63, 2001, pp. 263-275.
Li, J., Kuo, C.-C.J. and Chen, H.,Mesh Connectivity Coding by Dual Graph Approach, ISO/IEC JTC1/SC29/WG11 Coding of Moving Pictures and Audio, MPEG98/m3530, Mar. 1998.
Rossignac, J.,Edgebreaker: Connectivity Compression for Triangle Meshes, IEEE Transactions on Visualization and Computer Graphics, 1999, pp. 47-61.
Rossignac, J. et al.,3D Compression Made Simple: Edgebreaker on a Corner-Table, Invited Lecture at the Sharpe Modeling Intl Conference, Gemoa, Italy, Jan. 30, 2001, pp. 1-6.
Rossignac, J. and Szymczak, A.,Wrap&Zip Decompression of the Connectivity of Triangle Meshes Compressed with Edgebreaker, Journal of Computational Geometry, Theory and Applications 14, Nov. 1999, pp. 119-135.
Szymczak, A. et al.,An Edgebreaker-based Efficient Compression Scheme for Regular Meshes, 12thCanadian Conference on Computational Geometry, 2000, pp. 257-265.
Taubin, G. et al.,Geometry Coding and VRML, Proceedings of the IEEE 96(6), 1998, pp. 1228-1243.
Taubin, G. and Rossignac, J.,Geometric Compression Through Topilogical Surgery, ACM Transactions on Graphics 17(2), Apr. 1998, pp. 84-115.
Touma, C. and Gotsman, C.,Triangular Mesh Compression, Graphics Interface 98 Conference Proceedings, Jun. 1998, pp. 26-34.
Turan, G.,Succinct Representations of Graphs, Discrete Applied Mathematics 8, 1984, pp. 289-294.
Tutte, W.,A Census of Planar Triangulations, Canadian Journal of Mathematics 14, 1962, pp. 21-38.
Tutte, W.,A Census of Planar Maps, Canadian Journal of Mathematics 15, 1963, 249-271.

Affiliated with

Also associated with

Rating

Connectivity encoding and decoding of polygon meshes does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Connectivity encoding and decoding of polygon meshes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Connectivity encoding and decoding of polygon meshes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3715043