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?
Comments:
<< Home
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 :-)
Viktor
... 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 :-)
Viktor
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. :-(
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?
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.
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.
Post a Comment
<< Home
