Finite Algebras for Solid Modeling using Julia's Sparse Arrays. (February 2023)

• Record Type: Journal Article
• Authors: Paoluzzi, Alberto; Shapiro, Vadim; DiCarlo, Antonio; Scorzelli, Giorgio; Onofri, Elia
• Is Part Of: Computer aided design. Volume 155(2023)
• Publication Date: 2023-02
• Subjects: Computational topology -- Chain Complex -- Cellular Complex -- Solid Modeling -- Constructive Solid Geometry (CSG) -- Linear Algebraic Representation (LAR) -- Arrangement -- Boolean Algebra; 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.2022.103436
• Languages: English
• ISSNs: 0010-4485

Abstract

Abstract: An early research in solid modeling led by Herbert Voelcker at the University of Rochester and later at Cornell suggested that every solid representation scheme corresponds to an algebra, where the elements of the algebra are solid representations constructed and edited using operations in the algebra. For example, every CSG representation describes an element in a finite Boolean algebra of closed regular sets, whereas every boundary representation describes an element of a vector space of 2-chains in an algebraic topological chain complex. In this paper, we elucidate the precise relationships (functors) between all algebras used for CSG and boundary representations of solids. Based on these properties, we show that many solid modeling operations, including boundary evaluation, reduce to straightforward algebraic operations or application of identified functors that are efficiently implemented using point membership tests and sparse matrix operations. To fully exploit the efficacy of the new algebraic approach to solid modeling, all algorithms are fully implemented in Julia, the modern language of choice for numerical and scientific computing. Graphical abstract: Highlights: New research direction in solid modeling. Algebraic relationships between CSG and boundary representations of PL solids. Arrangements are isomorphic to the finite Boolean algebra of regularized sets. This algebra is isomorphic to a linear vector space of 3-chains. Operations on CSG and b-reps reduce to composition of algebraic operations. operations.