Revision as of 15:46, 13 July 2021

Constructive solid geometry (CSG) is a form of volumetric modelling where complex geometries can be built up by combining simple geometries via boolean functions.

Why functional representation is desirable

Functional representation (representing volumes with an implicit function in three variables) is especially suitable for CSG.
Functional representation (F-Rep)

• is typically more robust than boundary representation (B-Rep)
• is resolution preserving, and
• the boolean operations can be combined with blending operations with a simple change in math.

Pro: Higher robustness

Functional representation is typically more robust than a triangulation based boundary representation.
There is no need to worry about

• holes in meshes (meshes being not "watertight")
• flipped normals, degenerate triangles, coaxial edges, and
• a gazillion of other possible bad configurations.

Con: No convex hulls (general case)

Functional representation has one major weakness though:
The extremely useful of creating convex hulls seems not implementable (aside from a few special cases maybe)

F-Rep is higher level than (polygonal modelling) B-Rep

Functional representation (F-Rep) is on a higher abstraction level than triangulation based boundary representation (B-Rep). That is

• F-Rep can be triamgulized to B-Rep to arbitrary precision
• Going from B-Rep to F-rep requires a bit of artistic creativity filling in the blanks

The relation between F-rep and polygonal modelling B-rep is respectively a bit like:

• the relation between vectrographics and rastergraphics
• the relation between Denotative continuous-time programming and treaton dtme in a discrete way

In all three cases dragging out the discretionary step to the last possible moment is the way to go.
Manipulation of the continuous not jet discreticed representations allows for more expressiveness and
even more importantly more scalability in the complexity of systems modelled.

Why signed distance functions are desirable

Functional representations with their scalar field (f(x,y,z) in R³ aka "algebraic variety")
being constrained to a norm of one can be useful.
(a special case with magnitude of gradient always being one - and C0 continuity?)
Finding points on the surfaces (by some root finding algorithm like Newton method or Regula falsi) can be much faster (one step).
That is useful for:

• Faster triangulation
• Ray marching

As an example:

• y^2 + y^2 + z^2 < R^2 – evaluated without taking toots suffices to define a sphere
• sqrt(y^2 + y^2 + z^2) < R – evaluated this way unlocks the power of SDFs at the cost of needing to compute a root

F-Rep basics

Only a few types of elements are essential for F-Rep CSG

• The base volumes
• The boolean operations for combining them
• The coordinate transformations
• (projections)

For a convex hull over any geometry it seems
it is unavoidable to leave F-Rep and triangulate down to B-Rep

Base volumes

Volumes are defined just by implicit functions in 3 variables (f(x,y,z) in R³)

Boolean operations

Combining geometries via volumetric boolean operations amounts to simple mathematical operations

• minimum or maximum function corresponds to intersection and union (respectively or reverse respectively deepening if inside is positive
• multiplicative negation (commonly known as multiplication with minus one) turns a volumes inside out and vice versa – with that and the above one can construct differences

Coordinate transformations

• linear transfomations (translation, rotation, shear, mirror, boost) ...
• nonlinear transformations (waves, swirls, twists, ...)

How it all goes together

(wiki-TODO: Explain this in more detail.)

The order of composition in the programmatic 3D modelling process differs from the order the math is finally evaluated.
E.g. a translation of a complex geometry at the end gets "threaded through" and is the first thing applied to the coordinates.

There are some neat tricks to do part of this on the type level.
Using type constructors X Y Z as placeholders for the coordinate axis values x y z.
This trick has been done in an F-Rep CSG library Implicitcad
(A domain specific 3D modelling library implemented in the programming language haskell)
In this particular example:

• A lot of hard to trace indirection (somewhat typical for haskell) can make this quite hard to understand
• In the case of haskell type level computing is kind of added as an after-though => consequence: incomprehensible error messages
• Haskell is not a dependently typed language. So it has a value-level type-level barrier. This somehow feels like a big problem ...

(wiki-TODO: This seems important – discuss this ...)

• First there is the domain specific modelling library code describing the geometry.
• Then there is the single value of the entire 3D geometry with all the type constructors inside.

This eventually needs to go to:

• (1) a displayable 3D representation (ideally with data back-propagation allowing for direct manipulation that does not spoil the code)
• (2) a representation that is suitable for the targeted production process
  For now just 3D printers & co but eventually some-when gemstone metamaterial on-chip factories.
  Think about about "direct manipulation interactivity" of physical gem-gum products that threads back interaction data through that compilation chain. Sounds complicated.)

Compiling exactly the same code to very different targets is the topic of: Compiling to categories (Conal Elliott).
So this might be highly relevant here. Deeper analysis needed.

F-Rep challenges

Term simplification with a CAS

When big numbers of base geometries are combined this can lead to a really big symbolic expression.
The whole 3D models geometry is represented as one single formula (no matter how big).
One might need to simplify these in one way or another to get to acceptable performance.
Unfortunately this requires a full on computer algebra system (CAS) something that is typically not present as library in todays programming languages

• The experiment in implementing "F-Rep CSG" in the sage computer algebra system ran into this problem:
  See: miniSageCAD
• Interestingly Christian Scahfmeisters work on spiroligomers turned up similar algebraic simplification challenges

Term pruning

With max and min some parts of of the formula can completely cancel out for the most part of the total volume that the model occupies.
Thus there should also be other ways to prune out parts of the expression to avoid their unnecessary evaluation (and remember these pruneouts).

• Binary space partitioning trees
• Octrees
• ...

Quadrics

Nice projections

Quadrics are a limited subset of algebraic varieties with some useful properties.
One of them is that projecting them to a lower dimension like 2D always yields nice formulas (2D quadrics).

Quadriculation

Quatrics may be usable for some non-trianle-based B-Rep. That is:
Maybe some king of "quarticulation" is possible, analogous to "triangulation" but adding continuity of the first derivative as additional boundary condition.

External links

• Solid modeling – 3D modeling
• Constructive solid modelling: Constructive solid geometry
• Function representation F-Rep
• Boundary representation B-Rep
• Polygonal modeling

Math:

• Signed distance function
• Implicit surface – Isosurface
• Algebraic variety

• Ray marching and Volume ray casting