[rp-ml] CSG correctness. (LONG!)

I've been thinking about Adrian's document:

http://reprapdoc.voodoo.co.nz/bin/view/Main/SeparatePageOnTheQuestion

...I have a suggestion that ought to fix the problems.

It's true that CSG operations are almost impossible to evaluate
with only finite precision - and a consequence of the 'fudge
factors' necessary to implement this stuff on a real computer,
we have objects that blow up in our faces.

However, the problem only occurs because we insist on actually
calculating the shape of the resulting object.

Consider a hypothetical CAD package that only stored the original
shapes and the binary operations between them. It would never
calculate intervals or try to represent the shape of the resulting
object internally.

It would have no problems at all with these issues - except when
we wished to present the resulting object on-screen to the user -
or when trying to actually make the resulting object with a
fab machine.

The display solution is soluable. There are ways to use clever
Z-buffer tricks in OpenGL to render boolean operations more or
less directly. The result isn't a 100% perfect representation
of the object - but it's accurate to within one screen pixel
which is 'good enough'.

The fabrication problem is only a problem because we toss out
the CSG representation and feed our fab machines with triangle-
based surface representations (such as STL) - and then rasterize
them. Calculating a triangulated representation of a complex
CSG object is a computational nightmare.

But why the heck are we taking a perfectly well-described
CSG volume - expending vast effort to try to skin it into
an approximate triangulated surface mesh - then trying to
deduce where the solid volume is by analysing the triangular
skin!

Why on earth do we do that? It's really dumb!

A CSG model is a set of primitive objects (cuboids, cylinders,
etc) - along with a boolean equation that relates those
primitives:

     eg (cube1 & cube2) | (cylinder1 ^ !cylinder2)

Why don't we simply rasterize the CSG model directly? It's
not that hard - we can convert the CSG model into a 3D voxel
grid at higher resolution than the RP machine can render.

For each voxel in the grid, test whether that voxel is
inside each of the primitives that made up the object -
then evaluate the boolean 'equation' that is the object
by substituting those boolean results into the equation.

That's EASY to do!

This isn't a perfectly accurate solution - but it IS accurate
to within the finite precision of the RP machine - which is
"good enough".

If you are concerned about very thin surfaces coming about
due to roundoff error, then test all eight corners of each
voxel and say "only fabricate this voxel if all eight corners
lie within the final object"...or maybe "only fabricate it
if more than 50% of the voxel lies inside the object.

At the end of this process, you have a long list of all of
the 3D voxels that make up the interior of the object - which
you have to connect up into 'paths' that the extrusion head
can follow. That's almost certainly even easier than what
we are doing to rasterize our triangle meshes.

What's nice about this is that the CSG file is resolution
independent. You don't have to regenerate triangle meshes
at different precisions. It also ought to be an amazingly
small file compared to a triangulated version.

I can't immediately see a flaw in this plan - it eliminates
100% of the problems we have with ill-conditioned situations
in triangle mesh files and it also eliminates the problems
of writing CSG tools that have to generate triangle meshes.
Received on Fri Dec 08 01:05:14 2006