jscad
2D booleans are an absolute mess.
Expected Behavior
Reasonable retention of precision.
Actual Behavior
Some of these numbers are off by 4 times EPS!!!
[
[ 2.999997997037038, 1.499998998518519 ],
[ 3.999997329382717, 1.499998998518519 ],
[ 3.999997329382717, 2.499998330864198 ],
[ 2.999997997037038, 2.499998330864198 ]
]
[
[ 0, 0 ],
[ 8.000044658732051, 0 ],
[ 8.000044658732051, 0.9999993323456793 ],
[ 8.999993991111113, 0.9999993323456793 ],
[ 8.999993991111113, 2.999997997037038 ],
[ 8.000044658732051, 2.999997997037038 ],
[ 8.000044658732051, 3.999997329382717 ],
[ 0, 3.999997329382717 ]
]
[
[ 1.9999986646913586, 2.999997997037038 ],
[ 5.999995994074076, 2.999997997037038 ],
[ 5.999995994074076, 0.9999993323456793 ],
[ 1.9999986646913586, 0.9999993323456793 ]
]
[
[ 3.1499978968888898, 1.8499987648395066 ],
[ 3.349997763358026, 1.8499987648395066 ],
[ 3.349997763358026, 1.6499988983703708 ],
[ 3.1499978968888898, 1.6499988983703708 ]
]
[
[ 3.3999977299753095, 2.39999839762963 ],
[ 3.6999975296790133, 2.39999839762963 ],
[ 3.6999975296790133, 1.9999986646913586 ],
[ 3.3999977299753095, 1.9999986646913586 ]
]
Steps to Reproduce the Problem
const { geom2 } = jscad.geometries
const { rectangle } = jscad.primitives
const { union, subtract } = jscad.booleans
const { translate } = jscad.transforms
const { extrudeLinear } = jscad.extrusions
const main = () => {
let g2 = subtract(rectangle({size:[8, 4], center:[4,2]}), translate([2, 1], rectangle({size:[4, 2], center:[2, 1]})));
g2 = union(g2, translate([7, 1], rectangle({size:[2, 2], center:[1,1]})), translate([3, 1.5], rectangle({size:[1, 1], center:[0.5,0.5]})));
g2 = subtract(g2, translate([3.15, 1.65], rectangle({size:[0.20, 0.20], center:[0.1,0.1]})));
g2 = subtract(g2, translate([3.4, 2.0], rectangle({size:[0.30, 0.40], center:[0.15, 0.2]})));
const outlines = geom2.toOutlines(g2);
for (let i =0; i<outlines.length; i++) {
console.log(outlines[i])
}
let g3 = extrudeLinear({height:5}, g2);
return g2
}
Anyway, as step one to correcting the Boolean issues (#1113 ), I'm working on booleans for 2D. It's kind of crazy to be using 3D for 2D anyway.
BTW, is there some hidden documentation about how Geom2 outlines and sides work? I was making a sample, trying to understand how they work when I realized the severe precision issues.
Yea using the 3D BSP algorithms (which already have issues) for 2D is kind of crazy. Using the "fake polygons" to do so leads to a whole bunch of numeric errors, and the performance is awful.
There has been discussion, and I even started some work, on changing the 2D boolean operations to use better algorithms which are both 1) much faster and 2) more accurate and stable.
There was general agreement with z3dev that martinez might be the best implementation to use as inspiration. It is a line-sweep algorithm which is generally considered state of the art in computational geometry. It is very well tested on edge cases, see here.
There has also been some discussion of just depending on another lib such as here
Great. I'll look at those also. In almost every case, a JS version exists of the algorithms I've been looking at and they had either MIT or Boost licenses. It turns out I was already looking at Martinez-Rueda.
Comments moved that were posted in the wrong place... The link that @z3dev posted in the other thread (that I refer to below) is: https://github.com/w8r/martinez
OK, just been looking around. Polybooljs is also based on Martinez. More important from my standpoint is that two C# ports already exist! Martinez-Rueda is very full blown... it will be quite of bit of work paring it down...
Oh, NOTE: polybooljs seems to have a different maintainer, it now appears to be at: https://github.com/velipso/polybooljs ... no idea what the story is, but the links to the old place are all broken, including the doc ones on npmjs.com.
OK, revising my opinion about the martinez-reuda link @z3dev gave above. It seems it's is very similar to polybooljs, and the reason is simple, it all started with the author's C code, see: https://github.com/akavel/martinez-src The link @z3dev gave above is probably the best to go with because it uses the newest form of the algorithm. The new form gives information on what are holes, for example. And I think I'd really like to see "sides" go away in Geom2 and a form of the data provided by toOulines be the format used. In almost every instance, the first use of sides is to convert them back to points. If you know of a reason why sides need to stay, I'd love to hear it.
Comments moved that were posted in the wrong place... The link that @z3dev posted in the other thread (that I refer to below) is: https://github.com/w8r/martinez
This library has also been ported to Rust, if that helps. Bot are actively maintained.
FYI, the results of 2D booleans are snapped (rounded) in order to prevent gaps, which comes from the 3D booleans, so precision is 'adjusted'.
@z3dev It is possible you're actually making things worse with the "snap"... that is a common problem with snap rounding (there's a Wikipedia article). Anyway, I did notice that one of the worst values (8.00004) which is off by a full 4 EPS, got worse with each boolean. Being off 4 EPS makes the object unusable... you can't trust normal manipulations to work.
@z3dev , this is what numbers should look like!!!
ccw cw Vec2(3.35000,1.85000), Vec2(3.35000,1.65000), Vec2(3.15000,1.65000), Vec2(3.15000,1.85000),
cw Vec2(3.70000,2.40000), Vec2(3.70000,2.00000), Vec2(3.40000,2.00000), Vec2(3.40000,2.40000),
ccw Vec2(3.00000,2.50000), Vec2(3.00000,1.50000), Vec2(4.00000,1.50000), Vec2(4.00000,2.50000),
cw Vec2(6.00000,3.00000), Vec2(6.00000,1.00000), Vec2(2.00000,1.00000), Vec2(2.00000,3.00000),
ccw Vec2(8.00000,3.00000), Vec2(8.00000,4.00000), Vec2(0.00000,4.00000), Vec2(0.00000,0.00000), Vec2(8.00000,0.00000), Vec2(8.00000,1.00000), Vec2(9.00000,1.00000), Vec2(9.00000,3.00000),
I hacked in a C# translation of https://github.com/velipso/polybooljs called Polybool.Net. I wanted to see if it was worth translating w8r/martinez. The verdict is YES. The version of the algorithm I running is older and does not separate out holes, so I had quite a bit of frustration getting this in proper order for Geom2.
w8r/martinez does separate "contours" from holes -- see index.js there. So I will be translating that next.
There are some challenges, but even so, it runs about 10% faster than the current method. Challenges... one Geom2 sides really need to go, the take extra storage and are not useful anywhere that I can see. I've been playing around with stuff and I believe we should store things as Outlines. This would be a List<List<Vec2>> with ordering as you would expect. Each list in the list of lists would be a complete path. We spend a lot of time building sides, then tearing them down. My favorite example of this craziness is in the Extrudes. We get the sides, pass them to the Slice constructor. Which essentially rebuilds sides, calling them edges. Having them as outlines, preferable with some easy way to identify holes. (For example, w8r/martinez appears to do something like List<List<List<Vec2>>> where the call the first level rings, which seem to consist of a "contour" and it's associated rings. The "contour" seems to be the first entry in the array. Note, I could be wrong here... I've not started the port yet.
Anyway, I'd like to see a discussion about replacing sides with a different form of storage.
It is very important that you guys look into what I have done. @platypii @z3dev @hrgdavor Much, if not all of this needs done in JSCAD. OK, I've done the following to CSharpCAD:
- Changed 2D booleans to use a C# translation of polybooljs called NPolyBool.
- It is based on the eariler martinez algorithm. I had difficulties with the w8r/martinez. Problems in the code, etc. Also I did not like the fact that the paper isn't generally available. The only problem with the older algorithm is that it had the side effect of me needing to detect which were shapes and which were holes. This turned out to be a blessing, not a curse. See next comment about why.
- NPolyBool runs about 30% faster than the existing 2D booleans. It has much better data integrity. If I were you guys, I'd try the w8r/martinez to see if it is faster than polybooljs.
- I entirely replaced the non-twisty portion of ExtrudeLinear. it is 10x (that's TIMES, not %) faster than the existing extrude Linear. There are many reason why this is true, I'll deal with that in the next comment.
- I tried a different earcut, but ended up back with the current one. I FOUND AN IMPORTANT PROBLEM, see issue: #1132
- Because of the need to fix 3D booleans, I have made this and most of the primitives triangulated. I expect to have this completed soon. It will be far easier to fix the 3D problems if everything is triangulated.
The code is all available at: https://github.com/briansturgill/CSharpCAD
Edit Note... originally this note said the new ExtrudeLinear is 30x faster than the old version. I had accidently turned on some debug code in the old ExtudeLinear (from experimenting with it earlier). I realized my mistake only last night. It is still 10x faster, and that is great, just not as good as I believed. Sorry for the confusion. Oh, you can have faith in the 10x... I compared the timings of the "old" ExtrudeLinear with ones I took a few months ago, and it is running as expected.
Why I've started deprecating sides in Geom2.
They simply are not useful. I cannot find a single place in the code where having sides was useful. In most cases ToSides is called only to get data and convert it to some other format. They take twice the storage and it is fairly expensive creating them. It makes the very important ToOutlines() slow.
What I am using:
I created an NRTree (a nested Ring Tree). It is incredibly simple:
internal class NRTreeNode
{
internal Vec2[] Points;
internal Vec2 Min; // BoundingBox of points
internal Vec2 Max;
internal List<NRTreeNode> Contained;
}
// Nodes at (depth%2 == 0) are shapes, Nodes at (depth%2 == 1) are holes.
// ToOutlines() is now a very simple data copy.
// ToEarcutNesting() quickly creates Earcut data (sorted properly!)
// Obviously, during switch over, ToSides() is easily faked.
- It takes less storage and time to create than sides.
- It AUTOMATICALLY figures out spaces and holes on creation (solving the NPolyBool/polyboojs problem of winding.
- It bypasses the need for Earcut AssignHoles.
- It improve performance anywhere ToOutlines() is used.
- I haven't done it yet, but it is likely to make offset/expand/extrudeRectangular work faster.
- It is one of the reason that my extrudeLinear is so much faster.
- You can find the code here: https://github.com/briansturgill/CSharpCAD/blob/main/CSharpCAD/src/geometries/Geom2.cs
You can see extrudeLinear (no twisting) here: https://github.com/briansturgill/CSharpCAD/blob/main/CSharpCAD/src/operations/extrusions/extrudeLinear.cs
OK, I have created a full replacement for extrudeRotate. It runs about 50% faster than the old version.
The primary problem with the current JSCAD extrudes in general is that they all cater to extrudeRotate.
This makes most extrudes way too slow.
I have code that autoselects midpoint triangulation over earcut if the Geom2 is Convex.
Earcut handles Convex shapes somewhat painfully... especially on circles where it makes very tiny triangles and a few huge ones. It is also much slower, here it is in action:
You can find extrudeRotate code at:
https://github.com/briansturgill/CSharpCAD/blob/main/CSharpCAD/src/operations/extrusions/extrudeRotate.cs
Some may be mystified about my making new extrude functions... but take a look at what happens when you extrudeLinear without twisting under JSCAD.
- You (having created Sides in a Geom2), now copy the Sides into Edges (which are 3D).
- Remember each point gets a memory allocation. (Really 2 in the sides and 3 in Edges) It is now a 3D Slice.
- It then sets up a 3D routine that will do a matrix transform on your 3D slice, which uses trig.
- It then calls the main workhorse: extrudeFromSlices
- It will then repair the slice. Note if you've sent it a valid Geom2... why does it need to repair it? The repair is like O(N log N)
- It will then call the transformation on your baseSlice. Trig will be used... but essentially (after much CPU) it will do nothing.
- You then will go through a loop that does nothing on this pass, but asks for the next Slice.
- For the simple linear extrude this will be the last pass.
- Once again it will transform your Slice, this time the height will get added... but by trig transformation. Fuzzy numbers?
- As you have two slices "walls" will be built with Extrude Walls. Now keep in mind you only need to have two paths (which should be identical except for the z value) to have triangles placed between them.
- However, for reasons that truly mystify me, extrudeWalls attempts to handle a case where the two slices don't have the same length. It also checks area for EVERY triangle generated... why? You have to be doing something very weird to get those triangles to be too small. For a linear extrude you would either have a bad geometry (points too close together) or you chose a height that is less than EPS.
- Next we generate endcaps. Now for concave shapes, it is essential that the endcap be triangulated. (And I of course make them all triangulated as I think it will be necessary for 3D). But earcut needs to operate at 2D... so the 3D points are passed through an OthroNormalBasis (no, not that one, Earcut has it's OWN version). The 2D shape is then sorted by shapes and holes. The algorithm seems to be suboptimal (possibly N^2). The 2D data is then passed through Earcut (which requires its own transformation of data). Then, we get to use the OthroNormalBasis to get the 3D points again. Fuzzy numbers?
- Finally we create Poly3s and then Geom3.
When I look at the JSCAD extrude system... it's really rather elegant. I mean it manages to put all the extrudes through one framework. But in Computer Science, many, many elegant systems, simply don't work in practice. I think part of the problem is the desire to do it by the Math. Jumping to 3D immediately seems a great idea. But the truth is that even extrudeRotate should stay 2D until the Poly3s are created. Anyway, between the inappropriate Sides data structure in Geom2 and all the levels of abstraction draining CPU, it's not surprising to me that my linearExtrude is 10x faster than the JSCAD-based one was.
@briansturgill all of your insights are appreciated, and I enjoy reading your posts here and suggestions. @z3dev is much longer on this project than me and he may know (but may also not) who made some choices in the current code-base.
I agree with your sentiment about the extrude, and although elegant I prefer splitting the concept so simple linear extrude can benefit in performance.
Thank you for sharing your experiences from CSharpCAD. You could have easily just done the improvements there, and not take time to share these insights with us.
