Monday, June 21, 2010

Vectorization of pixel defined print roads

In which your narrator describes the end, hopefully, of a search for a reasonable way of converting pixel-defined print roads calculated by Slice and Dice.

For the past two months I've struggled with what has been, for me, a very nasty problem, viz, converting pixel boundaries defining print roads for my Rapman printer into equivalent vector descriptions.  As I mentioned previously, in order to get a major axis velocity of 16 mm/sec on the SD card Rapman 3.x you have to have GCode vectors of no less than 0.3 mm.  If you are printing detail finer than that the lag caused by reading off the card and processing the GCode slows down the print head dramatically.

From my literature search, vectorization is a fraught process, especially if you are not willing to accept considerable degradation of your pixel-defined road.  With 3D printing, perforce, we really can't accept degradation.

Over the last few weeks, I've finally confected a method which seems to do the job.  As with most things I do, it is relatively simple and straightforward.

Suppose we have a perimeter path for an involute profile gear...

The method grabs a 2.1 mm patch {note the red circle} at the extreme left of the path which you can see here...

Here you can see the individual pixels making up the print road.  The first thing we do is define the starting point and direction of the road from the centre of the patch.

At that point I pivot a scan from the center of the patch and identify the closest fits at ranges varying from 1 pixel to 11 pixels.

In this case, the longest perfect fit to the involute profile was 4 pixels.

Red pixels represent the fitted vector while blue indicate the remaining pixels.  Notice that this vector is four pixels long, just enough for the Rapman to operate at 16 mm/sec.

The patch is then re-centred over the most distant red pixel and the process repeated until the full loop is vectorized.

Looking at a simpler problem, consider a hexagonal print road...

Isolating the beginning of the print road yields...

Scanning this straight line gets a perfect match at 11 pixels.  Thus the way I have the code set up now creates vectors of up to 11 pixels in length, a maximum length of about 1.4 mm.  It's reasonable to ask why the vectors are kept so short.  In fact, it takes much longer to process the print roads with longer vectors and there is no reason, SD cards having huge storage capacity, not to have large print files.

As I get time in the coming weeks I will be fully embedding this method into Slice and Dice.


Giles said...

Forgive me for not understanding your algorithm but it seems to be inspired from marching squares

Forrest Higgs said...

Reading over the method, I can see where you could draw that conclusion. I fear, however, that 1) I was trying to vectorize, not describe a perimeter. The perimeters that I am dealing with are rather easy to delineate and 2) the method is much more elegant that what I came up with. :-)

Adrian Bowyer said...

Hi Forrest

I take it that your rule for whether a trail of pixels is straight is: "Is this what a Bressenham DDA would give me between these end-points?" If so, that is what the standard RepRap host software does to solve this problem too. It breaks a pixel perimeter into the longest straight-Bressenham-runs that it can.

Forrest Higgs said...

Adrian: That's pretty much it. I limit the search for the longest straight run to 1.1 mm, though, because searching for longer ones takes more computing time and I don't get any additional advantage in print speed after that. It would make for shorter gcode files, but since I have 2 gigabytes on the SD card, that really isn't an issue.

tim said...


I don't know if you know this, but for this kind of problem "blob detection" is constantly being used in computer vision problems.

If you are working with C++ there is the very good openCV library. I use it all the time and its lightning fast!

hope this helps.

btw. I love your blog and the detailed descriptions of your work process. keep it up!