Sound and robust solid modeling via exact real arithmetic and continuity

• DOI: 10.1145/3341703
• Publication Date: 2019-07-29T20:55:51Z
• Authors: Benjamin Sherman; Jesse Michel; Michael Carbin
• Keywords: Monad (category theory); Representation

Algorithms for solid modeling, i.e., Computer-Aided Design (CAD) and computer graphics, are often specified on real numbers then implemented with finite-precision arithmetic, such as floating-point. The result is that these implementations do not soundly compute the results expected from their specifications. We present a new library, StoneWorks, provides sound robust modeling primitives. implement StoneWorks in MarshallB, pure functional programming language exact arithmetic which types denote topological spaces functions continuous maps, ensuring all programs robust. developed MarshallB an extension of Marshall language. also define shape representation, compact representation ( K-rep ), enables constructions Minkowski sum analyses Hausdorff distance possible traditional representations. nondeterminism monad describing points shape. With our language, together, we show short can specify execute algorithms tasks.