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

From: Adrian Bowyer <>
Date: Fri Dec 08 2006 - 12:34:37 EET

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

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
(, which implements all these
operations, to drive RepRap version 2.0...



steve wrote:
> I've been thinking about Adrian's document:
> ...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

This archive was generated by hypermail 2.1.8 : Tue Jul 21 2009 - 10:27:52 EEST