Re: [rp-ml] algorithm&implementation for STL slicing

From: <sachs_at_pipeline.com>
Date: Mon Aug 21 2006 - 20:22:37 EEST

>From: Adrian Bowyer <A.Bowyer@bath.ac.uk>

Adrian, you make several very good points, BUT ....

>CSG is inherently robust - you _never_ get a topological inconsistency,
>because there is no topology.

Well, of coarse, any solid has topology, especially if you are doing lots of boolean operations to get one, so CSG solids do have lots of topology and can still develop problems (at tangencies for instance), but these may be far less common than with other approaches. I think you meant to say that the PRIMITIVES (the things you start with) in CSG have trivial topology and that CSG objects are easier to work with analytically. I'd agree with that.

CSG is certainly pretty good and robust, but it's just a MINISCULE subset of all polynomial representations of surfaces and solids (it usually just involves working with simple primitives such as spheres, cones, boxes, etc.). And I don't know of any really high level commercial systems that are currently using "unrestricted" implicit polynomial representations of surfaces, though there may be some that use CSG (maybe I just haven't kept up). Can you give me some examples of any sophisticated CSG systems so I can learn a little more about them (not ones like DesignCad that I am somewhat familiar with)?

While numerical errors can be gradually cumulative and not cause immediate problems, BUGS are usually all or nothing things that are the real problems in most CAD systems and other software (ask Bill Gates). While you can try to control for the initial assumptions and numerical accuracy, it's hard to control for the human element, especially when working on a very complex CAD system. But by starting with "canned" and robust libraries of fundamental elements (as in ACIS, UNIGRAPHICS, etc.) it can certainly become much easier to write a new application which is much less prone to problems because, hopefully, most of the hard stuff has already been done. Even in CSG, I think it's still possible to get cases of topology problems - you just might have to try harder to get them; say by uncovering a bug.

>I think that the ideal representation for RP is a CSG/boolean one. You
>can represent surfaces just as complicated as NURBS with implicit
>polynomials (you can even put these in the Bernstein basis if you
>like)

While I believe that from the purely mathematical point of view this is absolutely correct, the problem is that most computers don't work on a purely symbolic mathematical level (certainly not CAD systems ... and maybe that's the problem!). They do numerical approximations of the math and while they do these to fairly high accuracy (except when talking about STL data which is single precision - but that's a whole other can of worms), they are all prone to a host of problems that can arise from evaluating and solving equations using numerical methods. I have found in my experience, that the quality of programming itself can greatly affect such results. Someone having a deep understanding of these issues can do a better job of writing algorithms than someone who does not. As good as pure mathematical and/or implicit representations of surfaces may be (and you must include rational polynomials which is (pretty much) = NURBS), solving for the zeros of the implicit equations is not exactly a trivial exercise (in terms of accuracy and speed) especially when you get into high degree equations. In fact you can't solve most of these in closed form anyway, so you have to go with a numerical approximation - again, only as good as your programmer. Things were simpler when some CAD systems only worked with parabolas. You could do a lot analytically with these, but designers wanted to get to their end results faster and they wanted their surfaces REALLY smooth (class A) - you can't get all this with CSG - unless you like cars that look like spheres.

And, yes, CSG systems are much easier to work with and, in theory at least, you are right about what can be done using implicit polynomials. But, if it were all that simple, we'd all have CAD systems that are 100% robust, be able to easily create anything our imaginations might concoct and always be able to unambiguously talk to each other. So where are these magical systems?

>Ray-tracing is really fast, too, if you need the whole structure of a
>scan line before you start it.

Not sure what you mean about the structure of a scan line but, yes, things like octree's and other structures like them work great for getting speed, but they also take lots of memory (though this really isn't much of a problem anymore).

>And finally, creating a slice is trivial - you just substitute a number
>for the Z variable...

You still have to solve for X&Y, but - yes - not a problem, if you're only dealing with a bunch of primatives like spheres and cubes.

I find that, overall, Rhino does a "pretty good" job (with its NURBS representation of things) on most things that RP'ers might want to do. Right now though, surface/surface intersection... not so much (but that was Beta).

Regards,

G. Sachs

-----Original Message-----
>From: Adrian Bowyer <A.Bowyer@bath.ac.uk>
>Sent: Aug 18, 2006 7:52 AM
>To: rp-ml@rapid.lpt.fi
>Subject: Re: [rp-ml] algorithm&implementation for STL slicing
>
>Quoting sachs@pipeline.com:
>
>> I believe there are at least a couple of quite inexpensive software
>> packages out there that can output slices from an STL file (including
>> many slices at a time). But the practical problem with trying to go
>> from some public domain type software (even if available) to a
>> commercial or even semi-commercial algorithm is that there is usually
>> a little more involved than just the basic math and concepts
>> underlying such things. Unfortunately you have to contend with speed
>> issues and questions about tolerances, topology ambiguities and what
>> you actually need to do with the sections you get. Remember you will
>> basically just get outer boundary region lines (and that's if your
>> lucky and do it right). If only things in the "real" world were that
>> easy I wouldn't have had to spend several years working on
>> surface/surface intersectors (NURBS not STL). Besides who wants to
>> keep using STL files anyway? They're SOoooo 80's. If you're really
>> going to go to the trouble, in my opinion, the way to go is Nurbs and
>> skip the STL all together.
>
>I think that the ideal representation for RP is a CSG/boolean one. You
>can represent surfaces just as complicated as NURBS with implicit
>polynomials (you can even put these in the Bernstein basis if you
>like), and (especially if you superimpse a Woodwark-style recursive
>subdivision structure on your CSG model), point-membership tests are
>faster than a speeding bullet. If you are (say) scanning a laser over
>a layer, all you need is a point-membership test to tell you when to
>turn the beam on and off.
>
>Ray-tracing is really fast, too, if you need the whole structure of a
>scan line before you start it.
>
>CSG is inherently robust - you _never_ get a topological inconsistency,
>because there is no topology.
>
>And finally, creating a slice is trivial - you just substitute a number
>for the Z variable...
>
>Yours
>
>Adrian
>
>http://staff.bath.ac.uk/ensab
>http://reprap.org
>
Received on Mon Aug 21 19:56:24 2006

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