STL Slice & Dice - Help Wanted!

You run Export Slices, at:
[members.axion.net]

by downloading and saving it in your Tools folder in Scripts in your Art of Illusions folder;
../ArtOfIllusion/Scripts/Tools/

Then save the test file Reprap Hollow Square, at:
[members.axion.net]

Then open Art of Illusion, then in Art of Illusion open the file Reprap Hollow Square.aoi. On my Linux computer I have to do it in this order, because for some reason double clicking on the Reprap Hollow Square file open Art of Illusion to a new page.

Once you have loaded the test file, choose Export Slices from the Scripts submenu in the Tools menu. On opening Export Slices you have the choice of printing or saving the Triangle Mesh and GCode output.

Export Slices is not finished; but, it can barely output GCode for an object, which would be very blobby since inseting the extruder path has not been implemented yet.

I am not proprietorial at all about the STL slice-and-plot code. If someone can find some OS code out there that does what we want, that's absolutely fine by me.

A few observations followed by a spec.

Obs:

1. Commercial systems on zillion-dollar RP machines make mistakes; they usually detect them, tell you, and give up. You then have to go away and regenerate the STL files...

2. Once you have the data in a robust form (RepRap uses CSG), everything is pretty easy from then on.

3. 98% of the problems stem from the rubbish STL format, and getting data out of it. That will be common to whatever system is used.

4. Fancy graphics tell you nothing. You can make a nice picture that fools the eye from garbage data - Hollywood has been doing that for decades.

5. Bitmaps are very inefficient (but a quad-tree would be OK). Except that you can't trace round the edges of either efficiently.

6. The geometry code hasn't really taken me months. It's taken me a week or two spread out over months because of other work. But I have now finished my major teaching for the year, and am moving towards going part-time in August. As of now I should be able to devote a lot more time to it.

7. I really would appreciate a hand, but I know I'm the only one who understands it, and so that is not a reasonable expectation until I get my arse in gear and wiki-document how it works. Dilemma: document first, or fix first?...

8. Don't mix the geometry questions (which are mathematical and algorithmic) with questions of how to control the machine (which are communications). The two need to be kept completely independent.


Spec:

1. We need outline slice polygons that you can trace round, and that you can offset (+ or -) by a given distance.

2. We need to be able to do robust booleans on polygons (which may have lots of coincident edges - see my piece at [reprap.org]) to do the support-material calculations.

3. We need a zig-zag infill in which as many ends join up as possible. Note that "join up" means trace round a bit of an offset polygon between a zig and a zag.


I have a personal preference for the CSG format that RepRap (uniquely) uses - it is compact, tough, and future-proof. In particular, in many years time when we're down among the nanometers, that will still be going strong when all systems using boundary representations will have to be rewritten. And it can be offset with no algorithmic calculations.

But if there's an OS solution out there, I'm all for it if it really does what we want.

---

best wishes

Adrian

[reprap.org]
[reprapltd.com]

P.S. The current code produces lots of pretty red messages on the screen. But that doesn't mean it's going wrong a lot; they are more for my information; I should (I know) switch them off with the debug flag...

---

best wishes

Adrian

[reprap.org]
[reprapltd.com]

Hi

Can someone supply a REPRAP.JAR file with Blerik's patches to version 0.8.1 for the Java challenged who also work only in Windows?

---

Regards

Ian

Adrian Bowyer Wrote:
-------------------------------------------------------
> Spec:
>
> 1. We need outline slice polygons that you can
> trace round, and that you can offset (+ or -) by a
> given distance.

I agree completely. But it isn't a hard problem, especially with well-formed stl files. And for this project we have control of the files, so that should be easily doable. AoI is very very bad at this, but there are other options.

> 2. We need to be able to do robust booleans on
> polygons (which may have lots of coincident edges
> - see my piece at
> [reprap.org]
> uestion) to do the support-material calculations.

In the future, yes. Now we need to be able to print a RepRap 1.0 Darwin. It doesn't need support material. So this is not a priority as far as I can see.

> 3. We need a zig-zag infill in which as many ends
> join up as possible. Note that "join up" means
> trace round a bit of an offset polygon between a
> zig and a zag.

Can you tell me why? Is it essential to the object being printed to have those tiny tiny bits of plastic between the infill lines? I'd guess you just move the head without printing to the nearest bit that still needs to be printed. Not an optimal path, but not really relevant, since extruding is a whole lot slower than moving.

As far as I can see the project needs nicely formatted stl files for all of the objects. The host code is capable enough of printing those, even though it eats memory like no ones business. That is the bottleneck right now. And yes, stl is a bad format, like xml. But it is the standard in the industry. That alone gives it so much tooling support that it is superior to any other format.

--Blerik

*edit* @Ian:

I've attached GCodeWriter.java. Get Eclipse if you don't have it yet, and build the project. Just follow the documentation on the site.

Edited 2 time(s). Last edit at 02/25/2008 08:36AM by blerik.

> Can you tell me why? Is it essential to the object being printed to have those tiny tiny bits of > plastic between the infill lines? I'd guess you just move the head without printing to the
> nearest bit that still needs to be printed. Not an optimal path, but not really relevant, since
> extruding is a whole lot slower than moving.

Repeatedly turning the head on and off does not work, especially for short line segments, because of the mechanical delays in the extrusion. So it has to stay on for (and between) multiple lines.

And if you don't follow the outline but instead just move directly to the next line, half the time you draw across something that should have been a void, and quite a bit of the remaining time you draw across somewhere you've already drawn and so make a splodge...

---

best wishes

Adrian

[reprap.org]
[reprapltd.com]

Adrian Bowyer Wrote:
-------------------------------------------------------
> > Can you tell me why? Is it essential to the
> object being printed to have those tiny tiny bits
> of > plastic between the infill lines? I'd guess
> you just move the head without printing to the
> > nearest bit that still needs to be printed. Not
> an optimal path, but not really relevant, since
> > extruding is a whole lot slower than moving.
>
> Repeatedly turning the head on and off does not
> work, especially for short line segments, because
> of the mechanical delays in the extrusion. So it
> has to stay on for (and between) multiple lines.

Fair enough.

> And if you don't follow the outline but instead
> just move directly to the next line, half the time
> you draw across something that should have been a
> void, and quite a bit of the remaining time you
> draw across somewhere you've already drawn and so
> make a splodge...

So for short moves (next line within 1.5 mm or so), you keep the extruder running, and it doesn't really matter if you follow the outline. And for big moves you stop the extruder right? And I see some head lifting bits in the code as well. Vik sees some spiderwebbing, but it doesn't really break anything. So that should be fine as well.

Or are you suggesting the code should be changed so it can print a whole layer without stopping the extruder? That would be a nice challenge to figure out. Would simplify matters a lot though. After you start the extruder, you just keep on going till the layer is done. No more starting/stopping a couple of seconds before the beginning/end of a line.

*edit*

About the open and closed intervals. You know the resolution of the RepRap beforehand. So it changes from a continuous problem to a discrete problem. The whole open/closed distinction disappears. Slivers are always big enough to be printed. Am I missing something here?

--Blerik

Edited 2 time(s). Last edit at 02/25/2008 08:59AM by blerik.

This is just to get it on paper (might code it someday):

An algorithm to slice an stl file through the Z plane:
(only works for sane stl files)

You need a list of lines and a list of triangles and a way to get from one to the other.

* find a line that intersects the plane
* find the intersection point
* reverse the two endpoints of the line
* find the triangle that has that reversed line (should be only one*)
* save the normal of this triangle (for deciding what side is the inside later)
* find which of the other two lines of the triangle intersects the plane
* find the intersection point, join with the previous one.
* repeat (except for saving the normal)
* If the intersection point is already on your slice polygon, this polygon is done. find an unvisited line that intersects the plane
* If there are no more lines intersecting the plane you are done

edge cases:

* All points of a triangle are on the plane -> depending on the size of the triangle, discard it (small triangle) , or try and incorporate it if it's big. Better solution: have two slicing planes a very small amount apart. Switch to the other plane.
* Two points are on the plane. If this is the first triangle of a polygon, record both points as part of the triangle (save the normal as well). If it is isn't the first triangle of the polygon, one of the points was already handled with the previous triangle, so just treat it like it has only 1 point on the plane. Or use the two plane trick.
* One point is on the plane. Find all triangles that share this point. eliminate the one you already did (if this isn't the first). Only one of the lines of these triangles should intersect the plane. find it and record it. Or use the two plane trick. *edit* there is another edge case here, the next triangle has two points on the plane. As has it's brother. Then you get three intersecting lines (one of them in the plane). Get the one in the plane.

There are edge cases that defeat the two plane trick. In that case, use three or four. Or just stop, since this triangle is either almost infinitely thin or angled really really weird.

*edit* after all this you have a couple of polygon outlines. Now you can filter crap like lines turning (almost) 180 degrees back, and try and stitch up the rest.

* If this isn't true, the stl file doesn't conform to the stl spec. Abort.
--Blerik

Edited 3 time(s). Last edit at 02/25/2008 10:04AM by blerik.

That assumes that the STL file is perfect, which it never is (even after being run through various "healing" programs). In particular as-recorded-in-the-file triangle normals are almost always unreliable.

The current code takes the Z plane and, for each triangle that intersects it (i.e. one point one side, some points - maybe, if you're lucky, two - the other) works out the line of intersection.

The big problem is putting the ends of the lines together. There is _no_ geometrically robust way to do this. In particular nearest-neighbour methods are provably incorrect. RepRap divides the data in a quad tree such that leaf quads contain 0 or 2-different line endpoints. It then pairs up all the ends in all the occupied quads.

Adrian Bowyer Wrote:
-------------------------------------------------------
> That assumes that the STL file is perfect, which
> it never is (even after being run through various
> "healing" programs). In particular
> as-recorded-in-the-file triangle normals are
> almost always unreliable.

So recalculate the normal. I'll try and do some research on the RepRap stl files to check for brokenness in the files. Of course I'm being hopelessly naive here, but I assume that the only problems are floating point drift and reversed triangle problems? Or are you saying there could be more than two triangles sharing the same line? The MiniMug.stl file is fine, but that is a very small file.

> The current code takes the Z plane and, for each
> triangle that intersects it (i.e. one point one
> side, some points - maybe, if you're lucky, two -
> the other) works out the line of intersection.
>
> The big problem is putting the ends of the lines
> together. There is _no_ geometrically robust way
> to do this. In particular nearest-neighbour
> methods are provably incorrect. RepRap divides
> the data in a quad tree such that leaf quads
> contain 0 or 2-different line endpoints. It then
> pairs up all the ends in all the occupied quads.

Isn't there a problem (here come the open and closed sets again) with one of the ends lying on a quadtree division line? You have to choose in what quad to put it (50% change you choose wrong), or recurse into infinity.

*edit* Duh! It is in both parts of the quadtree, so it'll sort itself.

--Blerik

Edited 1 time(s). Last edit at 02/25/2008 10:23AM by blerik.

> So recalculate the normal.

That calculation is a trivial vector product, of course. The problem is getting its sign right when the triangles have the wrong cyclic sense...

> Isn't there a problem (here come the open and closed sets again) with one of the ends lying
> on a quadtree division line? You have to choose in what quad to put it (50% change you
> choose wrong), or recurse into infinity.

Yes - you're absolutely right. The code classifies points into quads that are slightly larger than they really are, so nothing falls down the cracks. This means that the division may progress further than strictly needed, but that it should never miss anything.

I spotted the tendency of AoI STL files to have bad normals quite some time ago and wrote a bit of code in my Slice and Dice routine to simply recalculate the normals from the perimeter definitions of the triangles. I mentioned this to the AoI people and they fixed the problem, too, on their end.

PS. Things get interesting when the algorithm has to decide the optimal coordinates to split X and Y to make 4 quads. At the moment it searches for a gap in the line-end coordinates near the centre of a quad and cuts in the middle of that gap.

Adrian Bowyer Wrote:
-------------------------------------------------------
> That calculation is a trivial vector product, of
> course. The problem is getting its sign right
> when the triangles have the wrong cyclic sense...

If the triangles have the wrong cyclic sense, and the normals are broken, just stop all processing. The stl file is broken beyond repair. Your quadtree algorithm can still grok it, but why continue, something is really really messed up.

--Blerik

> If the triangles have the wrong cyclic sense, and the normals are broken, just stop all
> processing. The stl file is broken beyond repair. Your quadtree algorithm can still grok
> it, but why continue, something is really really messed up.

True. True. But (at a guess) almost every STL file for anything more complicated than a cube has at least one such error, so then we'd never make anything...

The quad-tree algorithm was my attempt to extract data from STL files robustly even when they are wrong (which most are).

---

best wishes

Adrian

[reprap.org]
[reprapltd.com]

Right now, I do a visual inspection of each layer's toolpath display before I do a print. I store them all in a file and then cycle through them looking for problems. I've also got a rudimentary editing function that let's be repair bad layer toolpaths. I've worked with solids modeling since the late 1960's on and off and I've never seen a perfect solids modeling app. There are so many special cases that often conflict with other special cases that writing a package that always gets everything right is, imo, a bit like hunting for the Holy Grail.

Thus, I advocate not so much trying to make a perfect app, but rather creating an app that allows you to scan for problems and fix them when you find them. You can get usuable toolpath files if you put the user into the loop.

Edited 1 time(s). Last edit at 02/25/2008 10:41AM by Forrest Higgs.

I see the point, but that is a slight counsel of despair, I think. Especially so as we know that there is a robust representation (a boolean one) if one can get to it...

LOL! More a pragmatic one, I think.

"Especially so as we know that there is a robust representation (a boolean one) if one can get to it..."

Ideally, or is there actually operational code out there, open source or closed, that expresses the ideal?

@Adrian and Forrest:

Are you seriously saying that modeling apps don't even know the difference between the inside and the outside of a solid? I find that very hard to believe (I'm naive, I know). You'd see it instantly in the app when a triangle is inside out. Backface culling discards the triangle, and you see a hole. I can accept a triangle that is inside out, but connected properly to its neighbors (happens when the neighbors overlap). But not a triangle mesh with one reversed triangle. Hardware shaders rely on the right hand rule to be correct. Most 3d apps I've checked (ok, lots of games) seem to do alright. Am I really naive now?

Does AoI also export stl meshes that violate the vertex-to-vertex rule? Are you allowed to call your files .stl when the contents don't even look like stl?

--Blerik

*edit* @Forrest:
I think AoI uses CSG internally, not sure if you can export it. And PovRay of course uses CSG in its scripts. Some people already use PovRay to slice stl files, might as well make the objects in PovRay then. There are very nice gui editors for PovRay.

Edited 1 time(s). Last edit at 02/25/2008 11:17AM by blerik.

> Are you seriously saying that modeling apps don't even know the difference between the
> inside and the outside of a solid?

Yes. It doesn't matter for graphics because the ones that are wrong are almost always very small, or at least very thin. But those do matter for manufacture because everything has to really join up.

> Are you allowed to call your files .stl when the contents don't even look like stl?

Many do...

> I think AoI uses CSG internally, not sure if you can export it. And PovRay of course uses
> CSG in its scripts.

All these system have CSG _operations_. But those mainly act on boundary-representation objects, not CSG objects. Once it gets there, RepRap uses a CSG _representation_, which is very tough, and is guaranteed (for example) to have no leaks. It consists of unions and intersections of planar inequalities. That is:

P1: a1*x + b1*y + c1 <= 0
P2: a2*x + b2*y + c2 <= 0
P3: a3*x + b3*y + c3 <= 0
.
.
.


Polygon = (P1 U P2) ^ P3 U (P4 ^ P5)

and so on, where U is union and ^ is intersection.

---

best wishes

Adrian

[reprap.org]
[reprapltd.com]

Adrian's the man on this sort of thing. He's much more up-to-date on the state-of-the-art. I can give you a bit of a thought experiment, though.

Suppose you have some object that you've confected and you put a triangular mesh around it prior to generating an STL. Okay, if the mesh is sound, knowing what is inside the object and what is outside is a bit of a trivial exercise.

Suppose, however, that your object, usually as a result of flaws stemming from having done boolean ops on ideal solids to generate more complex forms, has flaws where, for example, all or part of a single surface projects into the object. When you apply a triangular mesh to this flawed object you are going to perforce generate a mesh that isn't sound. Following the logic to it's bitter end, without a sound triangular mesh you can't be for certain that your tests for sidedness and inside outside, especially if you have a triangular projecting through or cutting another, becomes problematic.

The question then is whether you can find the errant triangles and fix them via your code. That's quite a nasty problem. That's why put myself in the loop. I can see the consequences of stuff that code has a difficult time spotting in flawed slices and especially flawed toolpaths.

I've worked with AoI quite a lot and have regularly encountered situations where this sort thing happens.

I'll just keep working on the GCodeWriter, and leave the slice and dice be for now. It works good enough for simple stuff. And for really complex stuff, you can always resort to raster scanning* like the CandyFab guys do. Your printed objects will look like crap, but they will be functional.

--Blerik

* Alternating between X and Y scanning for each layer of course

*edit*

Did some more work. Temperature works now, and writing to a file as well. It even prints to the serial if you leave it as default (had to get the filename from somewhere, so I used the Port(name) property ).

*edit again*
Forgot to mention the magic 'stdout' filename. If the code sees this filename, it prints to stdout instead of to a file. I tried using the canonical unix - (dash) filename, but savePreferences doesn't like it.

Edited 2 time(s). Last edit at 02/26/2008 04:04AM by blerik.

ummm.... the inside or outside of a given polygon is represented by the order the polygons points are listed. This is what is used to calculate the surface normal which is then use to calculate the dot product between that and the camera to work out the backface cull. If it is positive, the angle is less than 90 and the face is drawn, if it is negative, the angle is more than 90 and the face is culled.

I did some research on the printed object stl files (the ones with modifications) here: [reprap.org]

I checked out Bed-corner-1.1.stl, X-motor-bracket-flattened.stl and corner-bracket-degroof-vik.stl. All three are perfect. vertex connectivity is sane (each point is a part of 3 or more triangles), and the vertex-to-vertex rule is never broken, which means the meshes are watertight. And these are not trivial meshes. So it is possible to get proper stl files for objects. And it seems the host software likes these objects better (some were created to get rid of overhangs, and some to get around printing bugs). Slicing these meshes should be possible using my algorithm. I'll try and cobble up something over the weekend...

--Blerik

Yes - I didn't mean to imply that all STL files were incorrect; far from it. It's just that in general enough are wrong to mean that any algorithm has to be robust against geometrically small but topologically inconsistent errors.

---

best wishes

Adrian

[reprap.org]
[reprapltd.com]

Adrian, the current heavyweight champion of slice/dice has fixed the host software! The current subversion build successfully handles the minimug file.

I'm putting the povray stuff on hold and admitting defeat. Yay!

blerik: lets take the gcodewriter stuff and get it into the current subversion. i'd like to start using that and making it my primary print output format.

Zach,

You can try and merge the diff file that is on the first page. It should merge without too much problems. It prints to stdout only though. Or you can wait for me to get the subversion head version working. I found that my problems are related to java3d. I use a too old version. I tried installing the newest version yesterday, but found out really late I also need jogl libraries. So I'll be testing that later tonight.

It really is too bad the RepRap host code needs Java3d 1.5.1 and not 1.5.0, because that version comes standard with the newest osx 10.4.

You can also try printing with the minimug.nc file I generated previously. It probably needs some work in a text editor, but the toolpaths themselves are straight from the host, so they should be good.

--Blerik

Edited 1 time(s). Last edit at 02/28/2008 01:59PM by blerik.

awesome. i'm looking forward to playing with this. yay!

Ok, got it,

Attached you'll find the java source for GCodeWriter ported to the latest revision (1369). Also attached are minimug.nc and RepRap.jar for those that don't want to compile it.

To use it, change the following preferences:

Geometry=gcodewriter
Port(name)=/dev/ttyS0 or the equivalent on your computer to print directly to the Arduino
Port(name)=stdout to print to standard out (for testing)
Port(name)=filename.nc to print to filename.nc

When the print is done, check the output for errors before printing!

Zach, can you add these files to Subversion? The only lines added to the project are these:

else if (geometry.compareToIgnoreCase("gcodewriter") == 0)
return new GCodeWriter(prefs);

And the GCodeWriter.java code, so it'll break exactly nothing unless you want it to.

Hi

Running GcodeWriter I see the following message frequently repeated:-

RrHalfPlane.find(): plane not found!


Also what controls the speed as it seems to run at actual extrusion speed? Presumably it could run a lot faster when it is only producing a file.

If a real running file is to be produced a method of setting will be needed. This could be G28 homing followed by an absolute move to a suitable start position. It occurred to me that an INI file could be useful where this absolute information is stored as I guess this will be different on every machine. This could be read by the GcodeWriter and appended into the appropriate position in the file.

Also for real G code consistency M30 needs to be implemented as end of file.

Also a few real CNC machines need the decimal point in the F word to ensure the correct feed is used.

The other thing I would strongly suggest is that if possible the G code is converted to absolute mode. This based on years of experience of people running incremental programmes with out first jogging the machine to the correct start position or interrupting a job, jogging away and forgetting to jog back. The result at the very least is a scrapped job but frequently machine damage as well.
A G28 implementation at the beginning of the file should at least trap an incorrect start position.

I am thinking here of users running the code on an existing CNC machine with an extruder attached.

None of this is a criticism of what has been achieved which is very impressive, just suggestions to help the development.

---

Regards

Ian