Now, why was it so hard?
1. Odd/even vs winding number.
Getting the original design right was tricky. What should it actually do? Even when you know you want a polygon library you do not necessarily know what the spec is. The main issue is how you handle holes. Basically, there are two approaches - something one can see in the postscript language even. If you walk from infinity over the shape, you can consider each line you meet as an edge, i.e. inside, outside, inside, outside, etc... This is odd/even logic. In this case the direction of each line is unimportant. Alternatively you can have a counter, starting at zero, and count each line you passed which is going to your left is plus one and each line going to your right is minus one. When the counter is non zero you are inside. This second approach is winding number logic. To me it seems much more logical so that is what I went for.
However, even with winding number logic you have to think. I just said any non-zero is inside, which is what postscript does. But what happens if you do something to a shale that makes it self intersect or even turn inside out.
Above is an example of a simple shape. A is what you started with. B is inset a bit. C is inset more - see how part of the shape has turned inside out. D is what you wanted - the inside out bit removed. To fix this you do winding number logic but only consider positive number as inside. Negative winding number are thrown away.
In fact the whole logic for basic intersect and union type operation works well with winding number. Union is just keeping all winding number 1 or above. Intersect is keeping winding number 2 or above. You can use it on one polygon to clean up things like this going inside out issue. You could use on more than two polygons at once even.
So, this makes winding number definitely the right way to do it. Else you have lots of other problems to sort out. This is, I believe, the key difference to the general clipper library that I looked at originally. Interestingly Cliff's idea at the beer festival was to have a separate function to simplify each polygon and then have Boolean operation functions which work on two polygons that you know are cleaned up like this. That would work, of course, but is a totally different approach.
2. Floating point numbers.
I coded this all with a typedef for the co-ordinate system, so I could change later. I just knew floats would bite me, but given machines have floating point hardware I thought I would try. Yes, as expected it bit me. Whilst comparison of floats was not the issue as such, there were problems where line intersection logic would happily decide to slice 10^-18mm off a line repeatedly. I am sure it would have finished eventually, but was due to the unit steps of floats and in particular the fact the two floats can have different intervals as different magnitudes. In the end, I simply changed to 64 bit integer which for my 3D stuff I am doing as micrometres. That also made it a lot faster as it happens.
3. Intersection logic.
One issue I then seem to have is that when you break a line because you have decided it intersects another line, you change it. This is made worse in some ways by use of integer maths. Basically, the break point is not going to be exactly on the line - it will be the nearest whole co-ordinate. This should not be an issue as obviously both ends move to the same point. The problem is that intersections you have already checked (off to the left) may change because the angle of the line you have just split has changed. An obscure edge case, but it happened. It meant that the segments needed re-checking as you could end up with self intersecting results. I initially solved most of these simply by making sure the X/Y intersect point was rounded to nearest whole number, not just truncated, but even then it still breaks with some shapes (not surprised). Now I just run the intersect checking code again until no more line segments are chopped up. That got pretty much everything working. I am trying to see if I can improve that.
4. Final bug
Well, I still have one test case breaking it - I need to figure that out. It is clearly even more of an edge case as quite complex shapes (like TARDIS and DALEK) are just working now. Should be easy to track down I am sure.
However, now I can actually get the output, I can continue on the original challenge - new 3D libraries. I can see my inset algorithm is breaking with some shapes so that needs fixing. Then I have new challenges with working out the extrude path and filling over open space, and all sort... But that should be fun, and a lot easier with a working polygon library...
It's a lot simpler if you define your shapes in terms of the sum of a set of convex primitives. The 'usual' way is to model solids is to perform solid geometry operations on a collection of convex hulls, with subtract operations making splits to produce a (hopefully) minimal set of convex hulls.
ReplyDeleteThere is a real industry application for machining machine tools (yes, software for designing and cutting machine tool cutting bits) that uses an approach like this. If you need slices you slice afterwards.
Obviously, there are also drawbacks to such an approach, but in terms of difficult edge cases (no pun intended) there are fewer issues. The 2D poly library approach is very old school (and might end up being more efficient for simple shapes) but may not scale well to highly complex systems.
As I implied in an earlier comment, if you're going to use float you need to understand intervals and floating point numerical stability issues. I'm not sure how you ended up doing repeated iterative subtractions though... There's obviously a point with floats where largeX +or- smallY == largeX but it's somewhat equivalent to the case in integers - see below.
The advantage of integers is that when a number gets too small, it's zero, which is trivial to spot, and suddenly it's all very simple. With floats the value depends on the other being operated on, but on the up side your small values don't become meaningless, they can still be useful when compounded with other small values. I guess it's a no brainer that 64-bit integers contain more data than 32-bit floats. Or were you using wider floats than that? Doubles are definitely doing to be slower than integers unless you leverage the hardware well, but for what you're doing I'd have thought a 32-bit float would be more than adequate - used wisely.
If you are careful about tracking what points should be co-located you can ensure that you never create holes or cracks, regardless of whether you use floats or integers. Cracks are something you really need to watch for and ensure that your algorithms cannot produce them because repeated processing can magnify them.
I'd still say that if you're serious about performance then letting a graphics chip do floating point calculations is always going to be quickest, but it doesn't sound like you aren't really worried about performance at this stage - just want stuff to work.
Solutions to automating the optimal positioning of a solid for 3D printing, and automated construction of support spurs or other rigging is interesting and ambitious. It's similar to design for injection moulding in some respects - the sort of thing that takes years of experience for a human to learn to do well. It will certainly be very cool if you can get some of that working reliably.
Take a look at how something like Bullet physics works to optimize 3D collision tests and store 3D collision meshes. There might be some useful ideas in there. I'd say look at Havok, but you might find the source harder to come by.