TY - JOUR

T1 - Boolean operations with implicit and parametric representation of primitives using R-functions

AU - Fougerolle, Yohan D.

AU - Gribok, Andrei

AU - Foufou, Sebti

AU - Truchetet, Frédéric

AU - Abidi, Mongi A.

N1 - Funding Information:
The authors would like to thank David Page and Brad Grinstead for their valuable comments, and Michaël Roy for his implementation advice. Dr. Gribok is thankful to Anton Bougaev for introducing him to the theory of R-functions. This work is supported by the University Research Program in Robotics under grant DOE-DE-FG02-86NE37968, by the DOD/RDECOM/NAC/ARC Program, R01-1344-18, by the US Army under grant Army-W56HC2V-04-C-0044, and by FAA/NSSA Program, R01-1344-129/130 and R01-1344-088.

PY - 2005/9

Y1 - 2005/9

N2 - We present a new and efficient algorithm to accurately polygonize an implicit surface generated by multiple Boolean operations with globally deformed primitives. Our algorithm is special in the sense that it can be applied to objects with both an implicit and a parametric representation, such as superquadrics, supershapes, and Dupin cyclides. The input is a Constructive Solid Geometry tree (CSG tree) that contains the Boolean operations, the parameters of the primitives, and the global deformations. At each node of the CSG tree, the implicit formulations of the subtrees are used to quickly determine the parts to be transmitted to the parent node, while the primitives' parametric definition are used to refine an intermediary mesh around the intersection curves. The output is both an implicit equation and a mesh representing its solution. For the resulting object, an implicit equation with guaranteed differential properties is obtained by simple combinations of the primitives' implicit equations using R-functions. Depending on the chosen R-function, this equation is continuous and can be differentiable everywhere. The primitives' parametric representations are used to directly polygonize the resulting surface by generating vertices that belong exactly to the zero-set of the resulting implicit equation. The proposed approach has many potential applications, ranging from mechanical engineering to shape recognition and data compression. Examples of complex objects are presented and commented on to show the potential of our approach for shape modeling.

AB - We present a new and efficient algorithm to accurately polygonize an implicit surface generated by multiple Boolean operations with globally deformed primitives. Our algorithm is special in the sense that it can be applied to objects with both an implicit and a parametric representation, such as superquadrics, supershapes, and Dupin cyclides. The input is a Constructive Solid Geometry tree (CSG tree) that contains the Boolean operations, the parameters of the primitives, and the global deformations. At each node of the CSG tree, the implicit formulations of the subtrees are used to quickly determine the parts to be transmitted to the parent node, while the primitives' parametric definition are used to refine an intermediary mesh around the intersection curves. The output is both an implicit equation and a mesh representing its solution. For the resulting object, an implicit equation with guaranteed differential properties is obtained by simple combinations of the primitives' implicit equations using R-functions. Depending on the chosen R-function, this equation is continuous and can be differentiable everywhere. The primitives' parametric representations are used to directly polygonize the resulting surface by generating vertices that belong exactly to the zero-set of the resulting implicit equation. The proposed approach has many potential applications, ranging from mechanical engineering to shape recognition and data compression. Examples of complex objects are presented and commented on to show the potential of our approach for shape modeling.

KW - Computational geometry and object modeling

KW - Constructive solid geometry

KW - Dupin cyclides

KW - Object representation

KW - R-functions

KW - Superquadrics

KW - Supershapes

KW - Volume visualization

UR - http://www.scopus.com/inward/record.url?scp=25644437121&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=25644437121&partnerID=8YFLogxK

U2 - 10.1109/TVCG.2005.72

DO - 10.1109/TVCG.2005.72

M3 - Article

C2 - 16144250

AN - SCOPUS:25644437121

SN - 1077-2626

VL - 11

SP - 529

EP - 538

JO - IEEE Transactions on Visualization and Computer Graphics

JF - IEEE Transactions on Visualization and Computer Graphics

IS - 5

ER -