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.