This might help you:
http://code.google.com/p/libarea/
Also, check out HeeksCAD/HeeksCNC:
http://code.google.com/p/heekscnc/
Dan
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
Similar Threads:
This might help you:
http://code.google.com/p/libarea/
Also, check out HeeksCAD/HeeksCNC:
http://code.google.com/p/heekscnc/
Dan
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
Were you able to port over to c# successfully?
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
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
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
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
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
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
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
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.
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.at the end all chains that are not closed (looped) are thrown away (if closed chain intersects all "good" parts must be looped)
Last edited by Larken; 05-21-2010 at 11:21 AM.
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"
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.
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
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/
Nice pictures, how to fill area with bitmap? Do it works for pockets with islands?
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
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.