Wednesday, February 24, 2010
Getting the perimeters right
When using a image processing approach to slicing and dicing when one extracts the perimeter of a curved boundary one is faced with an avalanche of very short (~0.1 - 0.1414 mm) print segments that do not easily transcribe into nice long, straight print roads like infills tend to. Trying to print 0.1 mm line segments presses the limits speed at which the Rapman MCU can take data off of the SD card and process it into stepper instructions.
I spent several days reasoning that if the conversion of vectors into bitmaps is rasterisation, then I ought to be doing the reverse process which is vectorisation. Vectorisation is a well-understood, if unpleasant algorithmic process. After struggling with the likes of the LZ78 algorithm for several days, I finally realised that what I needed to be doing was far simpler than that.
The approach I've finally taken was quite simple. My routines identify a series of pixels that form the boundary of an object slice. I simply begin by taking the first and third pixels in the path and forming a line thereby. Once I have this line I then determine the normal distance of the second pixel to that line. If it is less than a boundary that I can set I go on to test pixels one and four as a line and check the normal distances ob two and three against the the boundary value. I continue that process until one of the internal pixel's distance exceeds the boundary. I then step back one pixel and save that as the end points of a line segment in the compressed boundary. I then repeat the process using the end point of the last line segment in the boundary as the start point for the next until I've finished with the whole boundary description.
What I've described is a classic smoothing algorithm. The larger one sets the boundary the larger the degree of smoothing the boundary will be subjected to. I typically set it to 0.05 mm at the moment.
The code seems to handle my circular boundary problem adequately for the moment.
Subscribe to:
Post Comments (Atom)
12 comments:
Hey Forest,
I've been eagerly watching this project for the few weeks that you've been at it. What are you writing your code in? While it's probably pretty rough right now, are you going to release any intermediate code for those of us who'd also like to tinker?
I've often thought of writing my own version of skeinforge, and nearly come down to it twice when I see the strange paths that it makes, or other such things. I had figured that it would either end up 1) ultimately working better than skeinforge, or 2) work much worse and give me an appreciation for the difficulty of the problems of slice and dicing.
good luck!
Peter: I'm always happy to share my code. I'm writing in Visual Basic .NET, the free 2008 Express edition.
I must warn you, though, that Slice and Dice is a research programme in the purest sense of the word. It's not even alpha code at this point, never mind beta. It's really not ready for anybody save the terminally foolhardy to try to work with. I've written it to do things that Skeinforge doesn't do very well, viz, print light, open-frame structures. I think you'd be better advised to just bear with Enrique or buy a copy of the new Netfabb slice and dice code.
Forest: I'm actually most curious to see a working example of code that imports an STL file, and slices it into a bunch of (say) bitmaps or 2D arrays given some layer height. From there I figure I could write a bunch of different pathing/filling routines, but that's the part I'm the most unsure about. (Ideally the example would be in C, as thats what I'm most familiar with, but another language would be okay too). Any thoughts?
thanks
(p.s. -- I also ask, because I figure at some point or another if the test rig for the mini stereolithography powder printer that I posted to the builders blog a week or so ago works out, I'll likely have to experiment with toolpaths for melting the powder in an workable pattern, too).
Forrest, perhaps instead of just trying the next pixel in the line you could double the number of pixels in the line segment. Doubling is commonly used in optimization line searches. It usually greatly increases the speed when there are lots of pixels or data points that will fit the approximate line.
geo01005: I ran into the "takes forever" problem and sorted out a faster way of doing the analysis.
Perhaps these edge-detection tools inside imagemagic might help?
http://www.imagemagick.org/Usage/transform/#vision
http://www.imagemagick.org/Usage/transform/#edge_bitmap
Buzz.
(infact, after about half an hour of searching for an STL slicing algorithm, i haven't had much luck -- lots of old posts and dead links, but no real solid information or code. any thoughts on where to find one?)
Did you not get the code I sent you?
hmm, unless your email began 'DEAR SIR, I REPRESENT A WEALTHY NIGERIAN BUSINESS PERSON...' then i'm not sure it sent through :).
that being said, maybe hang off a little -- it's inspired me to get a little brain exercise and write my own slicer/dicer from scratch. :) i did the STL importer last night, and it was good exercise.
I sent it. You probably ought to take a look in your spam filter. I'll bet that's where it went, unless you have some limit on how big a zipped file you'll accept.
Mind, writing this stuff is good mental exercise. If nothing else, it will certainly give you an appreciation for what Adrian and Enrique have managed to accomplish. :-)
Post a Comment