Offset Algorithm

[babinda01]

Hi
I am trying to write a simple 2.5d cam program, for a specific special purpose machine.
Does anyone have an example code of creating offsets and/or for pocketing of a dxf file. I can easily read a dxf and convert it to gcode, but I want to be able to apply an offset either inside or outside the line. And also to pocket within the shape. I don't want to use offset left/right gcodes, I need to be able to actually offset the toolpath.

Regards
Andrew

[Dan Falck]

This might help you:
http://code.google.com/p/libarea/

Also, check out HeeksCAD/HeeksCNC:

http://code.google.com/p/heekscnc/

Dan

[babinda01]

Hi Dan

Thanks for your reply. The first link you sent looks very promising. I am madly porting it over to C#.

Thanks again

Andrew

[bradodarb]

Were you able to port over to c# successfully?

[babinda01]

Hi
No - I just havn't managed to find the time. I have too many projects and not enough time.....
It is still on my to-do list.

Regards
Andrew

[bradodarb]

I am thinking at the moment it might be as fast or faster to write it from scratch.... been resarching the math all week. Right now I can offset lines, arcs and fillet two lines easily enough. Where I am stumped is filleting two arcs or a line and arc combo. I have some pretty robust geometry entit classes with WPF graphics support (for verification). Once the remaining filleting operations are implemented I will be happy to share. Any help is greatly apreciated. .... Back to the math lab

[Larken]

I worked a lot in the 90's trying to write an offset for my Lcam program. I had a basic one but would make loops when the cutter went into some tight places with a lot of small vectors.
I write in Delphi, are you using C+ ?

I figured out now, how to make a perfect offset and how they do it in Corel draw using a thick line to clear the path of any loops and knots. I just don't have the time or mental ambition right now to code it.

There are a lot of tricks to analyze vector chains. I know how to determine path direction, whether one chain is inside an other etc.

Check out my StarCam. Its layout program for CNC that goes in front of my CNC controller. I would like to add a Cutter offset some day and a Fill routine.

http://www.larkencnc.com/dloads/index.shtml

I'm possibly looking for some one to write an offset for it in Delphi

Larry K

[Jack000]

any progress on your code? I'm also writing a 2.5d cam program, and offsets have caused a lot of headaches. From a cursory look at libarea, they seem to be breaking the paths into points, and matching lines and circular arcs to the points?

The approach I've gone with is to approximate the path with biarcs and lines, and offsetting the resulting approximation. This makes things a lot simpler because unlike beziers, biarcs and lines have exact offsets.

The problem lies in eliminating self-intersections of the offset path. Right now I'm doing a brute force thing - find all intersections and eliminate segments based on the normal of the offset path, but clearly this is an O(n^2) operation and not optimal.

I wonder how commercial cam packages do it. I've read things about voronoi diagrams and distance maps, but the math is a bit over my head..

I'm also curious about efficient algorithms for computing path winding direction. I know about the point in polygon method, but what if you don't have a point? The method that comes to mind involves calculating the polygonal area and checking whether it's positive or negative. Is there a more efficient approach?

[Larken]

I guess you know some of the tricks.
- First make contours closed.
- Make your contour CW
- Offset the chain of arcs and lines.
- You can Find all intersections using line intersect routines
- create closed contours of all intersection loops
- Bad loops will be CCW (erase them)

Breaking objects to points is not the way to go. Its very slow cam programs don't do it this way.


Here is my intersection procedure (pascal) for lines. I wrote this years ago.

Procedure intersect(xa1,ya1,xa2,ya2,xb1,yb1,xb2,yb2:real;online:boolean);
var xla,xlb,ma,mb,a1,a2,b1,b2,cc1,cc2,det:real;
begin
parallel:=false; linescross:=false;
xla:=xa2-xa1; xlb:=xb2-xb1;
if (xa1-xa2=0) and (ya1-ya2=0) then parallel:=true;
if (xb1-xb2=0) and (yb1-yb2=0) then parallel:=true;
if (xla=0) or (xlb=0) then
begin
if (xla=0) and (xlb=0) then parallel:=true;
if parallel=false then begin
if xla<>0 then
begin
ma:=(ya2-ya1)/(xa2-xa1);
cc1:=ma*xa1-ya1;
yint:=ma*xb1-cc1; xint:=xb1;
end else
begin
mb:=(yb2-yb1)/(xb2-xb1);
cc2:=mb*xb1-yb1;
yint:=mb*xa1-cc2; xint:=xa1;
end;
end;
end
else begin
ma:=(ya2-ya1)/(xa2-xa1); mb:=(yb2-yb1)/(xb2-xb1); b1:=-1; b2:=-1;
if abs(ma-mb)<0.00001 then parallel:=true;
cc1:=-(ma*xa1-ya1); cc2:=-(mb*xb1-yb1);
det:=((ma*b2)-(b1*mb));
if det<>0 then begin
xint:=((cc2*b1)-(cc1*b2))/det;
yint:=((cc1*mb)-(ma*cc2))/det;
end
else parallel:=true;
end;

if (not parallel) and online then {check if intersect is in range of LINE }
begin
if ((xint>=xa1) and (xint<=xa2)) or ((xint>=xa2) and (xint<=xa1))
then if ((yint>=ya1) and (yint<=ya2)) or ((yint>=ya2) and (yint<=ya1))
then if ((xint>=xb1) and (xint<=xb2)) or ((xint>=xb2) and (xint<=xb1))
then if ((yint>=yb1) and (yint<=yb2)) or ((yint>=yb2) and (yint<=yb1))
then begin linescross:=true; end;
end;
end;


Larry K

[grg12]

Hallo

I'm working on simple dxf->g-code conversion tool - current version is available at http://members.chello.at/grzegorz12/.../DXFKornik.rar . This rar contains all sources and executable - to start it you need QT4.1 library (available at http://qt.nokia.com/products/library...-class-library ), program is writen in C++, configured for VisualStudio 2003). I have started this project over 4 months ago, hoping that it will take 3, max 4 weeks - and it's still waaaay from being ready.
Unfortunetly offseting algorithm is far more complex than i thought - offseting line/circle/arc primitives is easy - real problems begin at this point.
Short descrition of current version of algorithm:
Basic "unit" is class PathPrimitive that could be line, circle, arc or list of primitives. Special type of primive is "chain" -> list of connected primitives.
Offseting algorithm (childPathGenerator) goes over "chain" components and creates offseted primitives (to offset a line you need to move it's endpotins over a vector perpendicular to line, to offset arc/circle you must change it's radius - thats all), every time new offseted object is created algorithm checks if a "connector arc" is needed to connect it to previous component. Algorithm uses tangent angles at endpoints of components to calculate if connector arc is needed and how the arc should look like. At this point we have collection of small "chains" - broken at points where offseted primiteves cross each other. To connect that mess into pretty chain algorithm must cut and throw away "swarf". To do this algothim tries to find crosspoints between all primiteves in list (all to all) - every cross point is added in special list with info "good->bad", "bad->good" (decision is based on tangent angles at cross point - basically when you go "away" from orginal path it's bad2good). After all primitves are checked algorithm scans this list - everything between "bad->good" and "good->bad" is saved, other parts are cut away. At this point our "chain" is almost clean - but in sometimes it's not a chain anymore - in some cases offseted chain breaks into collection of loops (example - big circles connected with thin "pipe" when offset is bigger than "pipe" width...) and some stubborn swarf. So algorithm searches this list and collects connected primitives into chains - at the end all chains that are not closed (looped) are thrown away (if closed chain intersects all "good" parts must be looped)
And that's all, at last for today

Gregor

[Jack000]

grg12: that sounds exactly like what I'm doing :]

I also tried to implement the offset algorithm, almost exactly as you describe - using the normal vector as a criterion for good/bad. The problem I came across was that it doesn't seem to like multiple intersections between several internal invalid loops, which usually happens when you have a complex curve with a large offset radius.

I've instead gone with a bitmap approach, although that has its own problems.

One point to note is that finding all intersections between all segments is O(n^2) time complexity. This is really really bad. I have implemented a sweep-line algorithm for finding intersections with O(log m) complexity, which brought my processing time from over 5 seconds to under 200ms.

here's the paper, it's for polygonal chains, but it was pretty easy to adapt to circular arcs.

[Larken]

I though of the bitmap also, but it uses a lot of memory if resolution is very high and is slow.
There is a trick to creating the perfect offset with no overlaps. If you study corel draw8-10 (the best versions) they had a excellent fast clean, 'Contour' command it will give you some hints.

Gregor, how are you storing the vectors , using an array or linked list ?

Do you have a routine to tell if one chain is inside another ? Thats a hard one . I have one to tell if a contour is ccw or cw no matter how complex it is, but i havn't one to tell if its inside other chains yet.

at the end all chains that are not closed (looped) are thrown away (if closed chain intersects all "good" parts must be looped)

If your origional chain is CW and you do an intesection check and then join all closed chains. The Ones to keep will all be CW and the gouging (bad) ones (to erase) will all be CCW.