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.

Do you want to read more?

Hi Forrest,

... some ten years ago i programmed a simple vectorizer for isolation milling from bitmap-PCB-layouts.

Here i simly scanned in horizontal rows for the first pixel, set a start-coordinate for a vector-line ... then searched the neighbour-pixel-coordinates in the same direction - or all possible orthogonal and diagonal directions (max. 8), when found, elongated the vector and deleted the pixels, until it didn't find a pixel in the specific direction ... then searched again in 8 directions, and so on.

When the continuous line ended (no pixels around), then i set the last vector coordinate and proceed at the next coordinates in the previous scanning row - until the complete image-area was scanned ...

So i received vector lines which fits perfect to all orthogonal or diagonal lines, but contained many short segments for curves and not diagonally aligned lines. But this wasn't visible in the output with the CNC-mill ...

This scanning method was fast enough for basic without long waiting times :-)

Victor: I used methods very much like what you describe before. As you rightly point out, however, once you stop encountering orthogonal or diagonal lines the segments get very short. Those short ones are exactly the ones I am trying to cope with.

The work I am having to do right now is a result of trying to work with a controller board that I didn't design that has a very fast CPU which is crippled by slow access times in getting data off of the SD card. I didn't have this kind of problem with the Tommelise 2 controller board. Unfortunately, I don't have the time or ambition to redesign the Rapman controller. :-(
... hmmm ... maybe a two-stage-solution - one controller reading the SD-card feeding the other with preoptimized data?
Yes an SDcard can easily provide the data fast enough, it is just a poor firmware implementation.
I sure hope that it is that simple.
Filtering a polygon in a pixel image to remove short segments is quite easy and quite fast.

The fundamental operation is to take a pair of points on the polygon and to run a Bressenham DDA between them checking if the polygon points correspond with the DDA points. If they do, the line segment is straight, if not, not.

Obviously trying every point pair in the polygon is an N^2 disaster, so you do a binary chop to find the pairs: first point to a point half way round; then to either 1/4 or 3/4 the way round depending on whether the DDA said not straight, or straight. Recurse.

Then do the next line the same way as the first from the end of the first.

You end up with a polygon that has a minimal number of straight line segments in, possibly plus one if the first and last segments happen to be co-linear. You can either ignore that, or check for it using the DDA and merge them.
PS - the DDA can obviously drop out on a non-straight bit reporting FALSE as soon as it finds a pixel that's off its line.
Adrian: Thanks for the tip. I'll be updating my code to do that. :-)
Post a Comment

<< Home

This page is powered by Blogger. Isn't yours?

Subscribe to
Posts [Atom]