CSG-BRep Duality and Compression

Jarek Rossignac

Georgia Institute of Technology


Solid Modeling technology has been traditionally divided into two camps: CSG and BRep.Constructive Solid Geometry (CSG) represents a shape as a Boolean combination of half-spaces. A Boundary Representation (BRep) specifies the location of the vertices, their connectivity, and a description of how they should be interpolated or approximated by a piecewise simple surface (such as a polyhedron, a subdivision surface, a B-spline, or a trimmed implicit or parametric patch).We will investigate the equivalence between CSG and BRep (using a simple duality) and will show that for a large class of polyhedral models, both can be encoded using (3k+4)N bits, where N represents the number of primitives in a CSG model or equivalently the number of vertices in the dual BRep, and where k represents the number of bits used to represent a quantization of each coordinate of vectors that define each either a vertex of the BRep or a plane of the CSG primitive. We will review recent advances in lossless and lossy compression and in selective and progressive transmission over error-prone connections. In particular, we will describe in detail the Corner Table, a simple and compact data structure for processing triangle meshes, and the Edgebreaker 3D connectivity compression algorithm, whose simplicity (2 pages of code) and effectiveness (between 1 and 1.8 bits per triangle) surpasses other compression techniques and standards. Details and source code may be found at http://www.gvu.gatech.edu/~jarek/edgebreaker/eb/.


Jarek Rossignac is Professor in the College of Computing at Georgia Tech. His current research is focused on the design, compression, progressive transmission, and interactive inspection of complex 3D models. The MPEG-4 standard for 3D compression is based on the award-winning Topological Surgery technique that he co-invented and patented at IBM, where, until 1996, he was Senior Manager and Visualization Strategist and managed research activities in 3D graphics, Computer Aided Design, 3D Interactive Visualization, and VR. He was also responsible for the development, maintenance, and commercialization of IBM's Data Explorer and 3D Interaction Accelerator products. At Georgia Tech, from 1996 till 2000, he served as the Director of the GVU Center, which he grew to 50 faculty and 14 scientists, focused on computing and communication technologies that make humans more effective. His recent work on 3D compression is supported by the NSF and has resulted in the Edgebreaker system, which has been adopted by several companies and has received the Sigma Xi Award for the Best Paper published by Georgia Tech faculty in 1999. He has authored 80 technical papers and 17 patents, for which he has received 7 Best Paper and 5 Invention Awards. He chaired 18 conferences, workshops, and technical program committees. He has served on the Editorial Boards of 7 journals and on 50 technical Program Committees of international conferences and workshops. He Guest-Edited 8 special issues of professional journals and gave 14 keynote or invited lectures. He was elected Fellow of the Eurographics Association in 2000. In 1985, he received a PhD in E.E. from the University of Rochester, New York. He also holds a Diplome d'Ingenieur from the French Engineering School E.N.S.E.M. and a Maitrise in Mechanical Engineering from the University of Nancy in France.

back to SM'02