Extending CSG with projections: Towards formally certified geometric modeling. (September 2015)

• Record Type: Journal Article
• Authors: Tzoumas, George; Michelucci, Dominique; Foufou, Sebti
• Is Part Of: Computer aided design. Volume 66(2015)
• Page Start: 45
• Page End: 54
• Publication Date: 2015-09
• Subjects: Constructive solid geometry -- Projection -- Homotopy equivalence -- Formal methods -- Constraint solving -- Disjunctive normal form; Computer-aided design -- Periodicals; Engineering design -- Data processing -- Periodicals; Computer graphics -- Periodicals; Conception technique -- Informatique -- Périodiques; Infographie -- Périodiques; Computer graphics; Engineering design -- Data processing; Periodicals; Electronic journals; 620.00420285
• DOI: 10.1016/j.cad.2015.04.003
• Languages: English
• ISSNs: 0010-4485

Abstract

Abstract: We extend traditional Constructive Solid Geometry (CSG) trees to support the projection operator. Existing algorithms in the literature prove various topological properties of CSG sets. Our extension readily allows these algorithms to work on a greater variety of sets, in particular parametric sets, which are extensively used in CAD/CAM systems. Constructive Solid Geometry allows for algebraic representation which makes it easy for certification tools to apply. A geometric primitive may be defined in terms of a characteristic function, which can be seen as the zero-set of a corresponding system along with inequality constraints. To handle projections, we exploit the Disjunctive Normal Form, since projection distributes over union. To handle intersections, we transform them into disjoint unions. Each point in the projected space is mapped to a contributing primitive in the original space. This way we are able to perform gradient computations on the boundary of the projected set through equivalent gradient computations in the original space. By traversing the final expression tree, we are able to automatically generate a set of equations and inequalities that express either the geometric solid or the conditions to be tested for computing various topological properties, such as homotopy equivalence. We conclude by presenting our prototype implementation and several examples. Highlights: Extension of classical CSG with the projection operator. Support for gradient computations. Topological property computation. Application of formal methods like interval analysis and proof assistants to CSG models.