Constructive solid geometry

From apm
Revision as of 14:22, 13 July 2021 by Apm (Talk | contribs) (→‎Why signed distance functions are desirable)

Jump to: navigation, search

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:

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 R3 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 R3)

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, ...)

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

Math:

Retrieved from "http://apm.bplaced.net/w/index.php?title=Constructive_solid_geometry&oldid=11582"