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

Steve has eloquently articulated what I have thought for years.

I would only add one further thing: instead of voxels, use an oct-tree divided
to the RP machine's resolution. That would be much more efficient in time and
storage.

The oct-tree division of CSG models was pioneered by my old chum John Woodwark
back in the eighties, and is perfect for this application.

A closely-related, and maybe even better, alternative is simply to substitute z
= 3.85 (o.w.e.) into the entire CSG expression when you're making the layer at
3.85 mm high. Then the model becomes an even simpler 2D CSG one, whereupon you
do a quad-tree division in that plane, and have your RP machine zap the
resulting bunch of rectangles.

Maybe I'll get my old SvLis CSG modeller
(http://people.bath.ac.uk/ensab/G_mod/Svlis/), which implements all these
operations, to drive RepRap version 2.0...

Yours

Adrian

http://staff.bath.ac.uk/ensab
http://reprap.org

steve wrote:
> 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 11:27:18 2006