584,830 active members*
5,897 visitors online*
Register for free
Login
Results 1 to 19 of 19
  1. #1
    Join Date
    May 2003
    Posts
    42

    Offset Algorithm

    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

  2. #2
    Join Date
    Sep 2004
    Posts
    149

    offseting

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

    Also, check out HeeksCAD/HeeksCNC:

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

    Dan

  3. #3
    Join Date
    May 2003
    Posts
    42

    Offset Algorithm

    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

  4. #4
    Join Date
    Oct 2004
    Posts
    147

    C# port

    Were you able to port over to c# successfully?

  5. #5
    Join Date
    May 2003
    Posts
    42
    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

  6. #6
    Join Date
    Oct 2004
    Posts
    147
    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

  7. #7
    Join Date
    Feb 2007
    Posts
    962
    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
    Manufacturer of CNC routers and Viper Servo Drives
    www.LarkenCNC.com and www.Viperservo.com

  8. #8
    Join Date
    Oct 2008
    Posts
    242
    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?
    ___________________________
    http://jack.works

  9. #9
    Join Date
    Feb 2007
    Posts
    962
    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;onl ine: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
    Manufacturer of CNC routers and Viper Servo Drives
    www.LarkenCNC.com and www.Viperservo.com

  10. #10
    Join Date
    Nov 2008
    Posts
    110
    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

  11. #11
    Join Date
    Oct 2008
    Posts
    242
    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.
    ___________________________
    http://jack.works

  12. #12
    Join Date
    Feb 2007
    Posts
    962
    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.
    Manufacturer of CNC routers and Viper Servo Drives
    www.LarkenCNC.com and www.Viperservo.com

  13. #13
    Join Date
    Nov 2008
    Posts
    110
    Jack000: thank you for that paper - my previosu algorithm was much simplier (and faster) but could not generate multiple loops - at the end there was only one. New algorithm works better - but calculations take much much longer.

    Larken: i'm using linked lists (std::list) to store primitives - most operations on chains involve inserting and deleting objects from container and resizing vector takes time.
    "Chain inside chain" shuold be easy - create a infinite line starting from any node of "suspected chain" (direction of line is unimportant) and count how many times this line croses other chain - assuming that "other" chain is closed and does not intersect with "suspected" chain - when number of intersections is odd - "suspected" is inside "other"


    Quote Originally Posted by Larken View Post
    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.
    Looks like i'm trying to reinvent the wheel Frankly speaking i started this project to give my brain some workout (you need something intersting to think of while coding (ctrl-c ctrl-v mostly) thousandth version of "that creative teaser animation") so i tried without looking at other's.

  14. #14
    Join Date
    Oct 2008
    Posts
    242
    to tell whether one chain is inside another, you could first detect whether the two intersect - if they do intersect, just return null or w/e, but if they don't intersect, choose one point on either chain and do a point in polygon. (if they don't intersect, either every point is inside or every point is outside)

    here's an illustration of my offset method:



    the butterfly was about 200ms for the offset, which is pretty good for flash/actionscript.

    There are still some issues - because of the finite resolution of the bitmap, sometimes it leaves "stubbles", but it should be fairly easy to detect.

    I'm squashing some bugs, but should be ready for a release soon :rainfro:
    ___________________________
    http://jack.works

  15. #15
    Join Date
    Apr 2006
    Posts
    3498
    awesome... Now i understand how the offset is made with the software..thanks for explanation
    http://free3dscans.blogspot.com/ http://my-woodcarving.blogspot.com/
    http://my-diysolarwind.blogspot.com/

  16. #16
    Join Date
    Nov 2005
    Posts
    5
    Nice pictures, how to fill area with bitmap? Do it works for pockets with islands?

  17. #17
    Join Date
    Oct 2008
    Posts
    242
    check out the open source forum, the app's been released :]

    I'm using a feature of flash to generate the bitmap. Admittedly this is a bit of a hack, but I'm not smart enough to do it with voronoi diagrams..
    ___________________________
    http://jack.works

  18. #18

    Re: Offset Algorithm

    Quote Originally Posted by babinda01 View Post
    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
    Hi Andrew,
    I am writing a c# program that reads DXF lines and I need to work out how to offset these lines and how to do pocketing of the geometry. Do you have any C# methods or library that you could pass on so that I can just pass through a set of lines/arcs and get a a set of lines/arcs that have been offset?
    Also, do you have any other methods that are robust enough to find intersection points of arcs and lines? I keep running into issues when arcs and lines are tangent and other similar issues. Most of the methods I have found out there are for Polygons but they don't work for arcs or circles which is what we have with DXFs.
    I know that you worked on this a long time ago so I was hoping you have resolved these issues and might be able to same me a lot of time.

  19. #19
    Join Date
    Oct 2017
    Posts
    12
    Quote Originally Posted by alexDownUnder View Post
    Hi Andrew,
    I am writing a c# program that reads DXF lines and I need to work out how to offset these lines and how to do pocketing of the geometry. Do you have any C# methods or library that you could pass on so that I can just pass through a set of lines/arcs and get a a set of lines/arcs that have been offset?
    Also, do you have any other methods that are robust enough to find intersection points of arcs and lines? I keep running into issues when arcs and lines are tangent and other similar issues. Most of the methods I have found out there are for Polygons but they don't work for arcs or circles which is what we have with DXFs.
    I know that you worked on this a long time ago so I was hoping you have resolved these issues and might be able to same me a lot of time.
    If wrote a c++ libtary that does cutter radius compensation, which might be usable for your purposes. Mine runs inside a cnc control but I wrote it to work mostly independently.

Similar Threads

  1. need Process control algorithm
    By Sathis Kumar in forum Fanuc
    Replies: 0
    Last Post: 02-08-2012, 04:56 AM
  2. Algorithm?
    By CNCgr in forum OpenSource Software
    Replies: 16
    Last Post: 12-08-2009, 12:23 AM
  3. Algorithm for G02 / G03 coding
    By jemmyell in forum Coding
    Replies: 19
    Last Post: 08-06-2009, 11:58 PM
  4. Archimedean Spiral Algorithm
    By fooo in forum Coding
    Replies: 6
    Last Post: 10-09-2007, 04:28 AM
  5. XY positioning algorithm needed
    By Tracid in forum PIC Programing / Design
    Replies: 4
    Last Post: 11-28-2006, 05:26 PM

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •