I found an interesting general polygon clipper library. So I figured it would do as an interim step until I made my own. I re-coded everything to use it, and then banged my head against the wall a lot. I then used svn to rewind everything about 5 hours...
Basically it is quite a nice library. It seems to work. It has a good simple interface.
However, looking at it, it seems complicated. It seems to classify each vertex in one of 16 different ways and have code for handling each. That seems wrong to me - the algorithm should be simpler and neater than that. It just feels wrong.
So I slept on it and worked out how the logic should - I think.
Step 1: Find mid-line intersections and create new point
Step 2: Find points that intersect
This comes out of the finding crossing lines basically. Each endpoint that intersects will be part of two joined segments, one or more times.
Step 3: Work out if the intersecting endpoints cross
This can be done with angles. Imagine AXB and CXD are the possibly crossed lines, X is the point they cross. So it appears in line segments AX then XB, and CX then DX. You can look at the angles of each of the four points (A, B, C, D) around X and work out if the paths cross.
Thankfully you don't need real angles for this (slow atan logic) you just need something you can compare, and that can be done by calculating the relative position of B, C and D relative to AB using multiplication and division only so nice and quick.
Step 4: Uncross them
The end result means turning crossed over polygons in to a set of simple polygons that do not cross. You need data structures such that you can easily splice lists of points, and can mop up loops you create and would be left over. That is not too hard to do.
Step 5: Winding number
Then work out if each path is clockwise or anti -clockwise and the winding number. I think the logic here is the winding number on your right as you traverse the path, (so the winding number of the inside of a clockwise path, or outside of an anti-clockwise path) which means a clockwise path and an anti-clockwise hole within it have the same winding number and so stay together when we do Boolean operations (see below). Winding number is not too hard to work out especially knowing the paths no longer intersect.
Step 6: Boolean maths
So, the plan is to make a new polygon library of my own. I am making it as a general purpose library and will probably open source it.
I'm probably teaching my grandmother here, but don't forget to do all your float/vector comparisons to some small amount, rather than zero :D
ReplyDeleteThis does of course throw up pathological cases where points A and B are the 'same', B and C are, and A and C aren't. But the alternatives are worse.
He he, yes, well in this case you can probably not bother as step 1 means you create cross over points if there is not an exact match and those are then exact matches.
ReplyDeleteAlso I have been toying with using long long rather than long double. It is faster in tests so far, I think because there is a lot of comparison which is going to be quicker in integer rather than floats. It is tricky as CPUs have lots of hardware float support now, and separate registers, which could make the maths quicker.
However, floating point rounding does mean that your crossover point might not actually be exactly on the equation of the line(s). :D
ReplyDeleteIndeed, but as a new point added to the lines, the point added will make new line segments and have the exact endpoint the same in both places...
ReplyDeleteI hate floating point at the best of times.
Will be fun when I have coded it all.
This is a very old problem for game programmers and I suggest you look at nVidia's site for some articles on this. Other places to go are the Graphics Gems book series and Game Programming gems books.
ReplyDeleteThe obvious way to make this go fast is to use your GPU using either the nVidia or AMD general purpose GPU computing support libraries (type GPGPU into wikipedia).
Another way to make this go fast is to use your PS3 SPUs :)
Most game programmers abandoned using fixed point years ago due to Intel's relentless optimization of floating point performance at the expense of integer throughput. With GPUs also offering highly parallel floating point computation it's a no-brainer.
If you don't want to go GPGPU and stick to your main CPU you can access SSE2 instructions easily from the Microsoft macros in Visual C/C++, or use an SSE2 library for gcc.
You'll see moderately improved performance on any remotely modern PC - though a lot of this will come just from aligning and organizing your data for SSE. It's likely any PC bought in the last few years has SSE3 as well.
I have written plenty of code to do this sort of thing, and really it's nothing special to get it working using SSE2/3, but if you want optimal performance you need to do a lot more work to organize your data so that memory access and decision logic don't become bottlenecks.
One approach is to test which side of the plane the three points of a given triangle lie (you can cache and re-use test results if you have a strip or indexed mesh). This is nice to optimize as you simply test plane side for each point in the first phase which is a sweet tight loop.
Once you have your side flags you have to calulate an interpolated point for any line between points on different sides, again a simple tight loop. Once you have the points you can make another pass to build the new polygon/strip/mesh data.
You will see floating point errors are larger when you have a line with a low angle of incidence to the plane, smaller when you are perpendicular. If you just want to render the mesh, then the errors are unlikely to matter, but if you are performing subtractive geometry operations for CAD then you will definitely want to go to 64-bit floats (or higher).
Also, regarding what Mike Whitaker says about floating point comparison - simple 'epsilon' tests are hopeless: you need to count 'floating point intervals' if you want your code to be as robust and accurate as possible. Again, wikipedia has what you need to know. Fortunately, this sort of test is efficient to do and can be done in the integer units while you're using the FPU for something else - the only pain is that you may want to compare values that are in FP registers - and shuffling them through memory to get them into ordinary registers is wasteful - but if you are using SSE you likely won't hit that problem.
ReplyDeleteIt's a great pity that FPU's don't allow you to do an interval test, as this would be easy for them to do in h/w.
The float comparisons are being a non issue though. Where we need tolerances they are done in units like 0.4mm and the like as they are for the 3D extrude stuff. The actual poly library has some cases that take a user specified tolerance but most are OK as it is the same value compared in different places so equality tests are consistent.
ReplyDeleteFYI, all working well except for one edge case I am working on - co-incident polygons!
ReplyDeleteThe winding number logic cannot cope as it counts lines crossed moving left from a point on the polygon, but that means counting or not counting all the co-incident ones...
Just working on a slight tweak to make an otherwise equal left point count or not count if before or after in the contour list.
That should sort the issue.
I never could get the hang of maths. I just don't get it.
ReplyDeleteSo this is how I'd solve the problem...
Firstly, create a three dimensional array the correct size for the object to be printed - if the object was 10cm^3 and the resolution is 0.4mm, then the array would be 250x250x250. Ensure each element of the array contains the value zero.
It's then a reasonably simple job to plot lines/polygons/whatver shapes within the array, setting a value of 1 (or 2, or 3 etc. for multiple colours where there is more than one print head) where we want to print plastic and 0 where we don't. I guess the only problem is making sure that the shapes are plotted in the correct order...
Anyway, you then end up with an array holding a 3D version of the shape to be printed.
Then, surely, it's a simple matter to take each layer and print it.
So there you are - far from optimal in pretty much every respect, but I think it would work! What's better (for me) is the complete lack of any complex maths.
Give me your worst (FX dons flack jacket).
So basically 3D rasterise it and print from that - yeh. Sorry, crap idea :-)
ReplyDeleteFor a start it does not really solve the problem - doing it at 0.4mm level would be crap resolution output - this is not a dot matrix printer, so you would have to do at a much higher resolution, and then you are back to working out how you navigate that raster image to find the best path for the extrusion head within it.
It is likely to be a bigger problem then the polygons to be honest.
Nice try though :-)
BTW, Polygon library passing a load of shape tests I have devised and working well.
ReplyDeleteJust that I have one real life shape (the coffee machine hopper extender) that is breaking it. Seemingly much more complex shapes work fine in every way, but not that.
It will be something simple I am sure.
So it would work. For some values of 'work'. :-)
ReplyDeleteI did say I was crap at maths!
Hi RevK.
ReplyDeleteFirstly congratulations - or perhaps commiserations ;) - on 'having a go' with polygon clipping.
Here's a recent comparison of 5 existing open source libraries.
You'll notice that the code for each of these libraries is complex - and that's because it really isn't easy to get polygon clipping to work reliably for every kind of polygon (concave, self-intersecting, multiple overlapping etc).
Interesting. In true http://xkcd.com/927/ I hope I am number 6.
ReplyDeletePretty close to working this time :-)
"In true http://xkcd.com/927/ I hope I am number 6."
ReplyDeleteLOL.