"subtract" gives bad output.

[briansturgill]

Expected Behavior

Actual Behavior

Meshlab reports 12 non manifold vertices 64 faces over non manifold edges. (I've seen this several times, here's a simple example.)

Steps to Reproduce the Problem

Run this: program output to .stl const { cylinder } = require('@jscad/modeling').primitives const { translate } = require('@jscad/modeling').transforms const { subtract, union, intersect } = require('@jscad/modeling').booleans

const main = () => { h = 8 size = 3 const inner_d = size*0.8 const outer_d = 4+size; c1 = cylinder({radius: outer_d/2, height: h}) c2 = cylinder({radius: inner_d/2, height: h}) let shape = union( subtract(c1, c2), //translate([20, 0, 0],union(c1, translate([3, 0, 0],c2))), //translate([0, 20, 0],intersect(c1, translate([3, 0, 0],c2))) ) return shape; }

module.exports = { main }

Run meshlab on the stl file.

Specifications

OpenJSCAD 2.2.21 [Linux:5.15.0-39-generic,linux:x64]

• Version:
• Platform:
• Environment: (browser, local server, node.js etc) CLI

[briansturgill]

OK, put updated code in original issue message. The union also has a similar problem. The intersect works perfectly. Is this by any chance, the "T-junction" problem? Update: geom3.validate(shape) reports it is non-manifold. Prusa slicer doesn't see any errors. I was able to print the faulty subtract object with no issues.

[platypii]

Yea, the issues with boolean operations creating non-manifold geometries is well known. #807 #696 #598 (this comment) and others. Here's the simplest example I've found:

union(
  cube({ size: 8 }),
  cube({ center: [0, 0, 4] }),
)

The main issue appears to be creation of T-junctions as you mention. To fix it will require either:

1. Fix it inside the BSP operations, likely using a data structure which tracks adjacent faces, and anytime one face is split along an edge, the adjacent face must also have a vertex introduced.
2. Fix it after the fact with some kind of "repair" function. We kind of already have this, but it does not seem to work reliably. I suspect this fails due to small rounding errors.

[hrgdavor]

1) sounds faster, and I am not sure if it will be more complicated to make a better fixing tool, or change BSP to track these splits. I can only hope someone with better knowledge of computational geometry than me will find this problem interesting to fix :)

[briansturgill]

@platypii Thanks for that example, I'm sure that will be handy while I work on this!

1. Fix it inside the BSP operations, likely using a data structure which tracks adjacent faces, and anytime one face is split along an edge, the adjacent face must also have a vertex introduced.

I'm starting to question if the right criterion is being use see the union algorithm here.

2. Fix it after the fact with some kind of "repair" function. We kind of already have this, but it does not seem to work reliably. I suspect this fails due to small rounding errors.

I find this very unlikely to work. The boolean algorithms only work on manifold sets of polygons. Anytime you do one of the booleans, there's a good chance you're not manifold. Subsequent boolean ops will have undefined results. Not sure you can ever fix that sort of problem in generalize.

[briansturgill]

I'm busy until next week sometime. I intend to go after the problem full blast when I get free. So if you want to beat me to it, now's the time. :-) I've been hunting down reference materials.

https://www.gamers.org/dhs/helpdocs/bsp_faq.html These folks actually have a Java implementation of 2D and 3D versions in Java... it's not straightforward though. https://commons.apache.org/proper/commons-geometry/tutorials/bsp-tree.html

Here's a paper from 1990 about this... http://www.cs.yorku.ca/~amana/research/bsptSetOp.pdf Alas the scan of the paper is faulty at the edge! EDIT: a better PDF or the article: http://www.vjlove.com/publications/papers/siggraph90.pdf

[briansturgill]

@platypii The union example you gave above actually works, i.e. doesn't fail under either CSCAD or the latest JSCAD.

[platypii]

I should have been more clear. The example I gave DOES produce a non-manifold geometry. But on export, generalize is called and is able to fix this example. There are other examples (like yours) that fail to repair even with generalize. The nice thing about my example was just that it demonstrates the same kind of underlying issue, with nice easy round numbers. This can be shown using geom3.validate:

const jscad = require('@jscad/modeling')
const { geom3 } = jscad.geometries
const { cube } = jscad.primitives
const { union } = jscad.booleans

const main = () => {
  const obs = union(
    cube({ size: 8 }),
    cube({ center: [0, 0, 4] }),
  )
  geom3.validate(obs)
  return obs
}

module.exports = { main }

[platypii]

Looking at @briansturgill's example.

Before generalize, it produces 326 non-manifold edges. After generalize there are zero-area polygons, and 71 non-manifold edges. Even after repair.

nonmanifold.js

```js const jscad = require('@jscad/modeling') const { subtract } = jscad.booleans const { geom3 } = jscad.geometries const { generalize } = jscad.modifiers const { cylinder } = jscad.primitives const main = () => { const c1 = cylinder({ radius: 3.5 }) const c2 = cylinder({ radius: 1.2 }) let shape = subtract(c1, c2) try { geom3.validate(shape) } catch (e) { console.log(e.message) } shape = generalize({ triangulate: true }, shape) try { geom3.validate(shape) } catch (e) { console.log(e.message) } return shape } module.exports = { main } ```

Pre-generalize non-manifold edges:

Post-generalize non-manifold edges:

[briansturgill]

@platypii Thanks!

In a manifold object, every edge has exactly two faces. That edge will get split twice. So I modified SplitPolygonByPlane to use a Dictionary (Map) of edges to returned values and then check for the reverse edge to see if the adjacent was already done, returning the cached intersect point if it was there, so that the points would definitely be the same. It made no difference. So, I just kept number track of the number seen and alternates seen. Over half the alternates were not seen, so clearly something is wrong with the algorithm. I don't think this is strictly a precision problem.

I think I'll try steping through one of your simple examples in the debugger next.

[z3dev]

It's a problem of precision.

@platypii lets investigate those zero area polygons. The generalize functions should be removing those.

[briansturgill]

Ummm... I believe that was what the recently removed repair did. It was generally not turned on anyway.

On Tue, Jun 21, 2022 at 4:36 PM Z3 Development @.***> wrote:

It's a problem of precision.

@platypii https://github.com/platypii lets investigate those zero area polygons. The generalize functions should be removing those.

— Reply to this email directly, view it on GitHub https://github.com/jscad/OpenJSCAD.org/issues/1113#issuecomment-1162430985, or unsubscribe https://github.com/notifications/unsubscribe-auth/ABYCO7ZRTTYHQAQHLH742H3VQI7XXANCNFSM5ZG4SNQA . You are receiving this because you were mentioned.Message ID: @.***>

--

Brian

[z3dev]

The serializers call generalize if necessary to create triangular meshes, etc.

[z3dev]

From the paper on BSP trees...

Note that this code is not robust, since numerical stability may cause errors in the classification of a point. The standard solution is to make the plane "thick" by use of an epsilon value.

Which is the current approach being taken to classify polygons for clipping.

[briansturgill]

I've found a better PDF of the naylor journal article: http://www.vjlove.com/publications/papers/siggraph90.pdf

[briansturgill]

Which is the current approach being taken to classify polygons for clipping.

Yes, but the problem (at least with the Cube, Cube example) is that it is not clipping properly. Or more accurately, edges that should have been split were not. As I said, I think the algorithm implementation is faulty. (It's kind of a myth that there is a BSP union algorithm... generally the academics wave their hand and say it's possible. Note, I only have found only one other package that use BSP's for 3D at all, and that is the Apache Commons project I gave the link to earlier.) None of the big packages (that are open source) use BSP trees.

Certainly the choice of plane for the split is very questionable. It doesn't match at all what was said in: https://www.gamers.org/dhs/helpdocs/bsp_faq.html

[briansturgill]

Anybody at an institution that has access to this: https://www.sciencedirect.com/science/article/abs/pii/S0010448512002412?via%3Dihub It sounds like exactly what we are looking for. Title: "Fast and robust Booleans on polyhedra" Abstract This paper presents efficient methods for supporting robust Boolean operations on pairs of polyhedral manifolds. A new spatial hashing technique is proposed for detecting intersections of pairs of polygon faces quickly and robustly. Robust predicates are used to compute the exact topology of the resulting polyhedron. Degenerate intersections are identified explicitly but handled in the topological routines. Geometric positions of new vertices are then approximated using finite-precision computations. Although vertex locations are rounded off, the exact connectivity graph is kept. The faces of the rounded-off triangulated final model thus could intersect each other and have the potential for an invalid embedding.

[hrgdavor]

Anybody at an institution that has access to this:

I am willing to bu iy for $32 if you are eager to try it out.

[briansturgill]

Anybody at an institution that has access to this:

I am willing to bu iy for $32 if you are eager to try it out.

I too am willing to buy it, but only if it looks like it really does what it is billed to do. Abstracts are unreliable. I was hoping someone could take a look at it first to see if was implementable. Academics are prone to hand waving when it comes to the hard parts.

[briansturgill]

So I think I may have figured out what is wrong with the Booleans algorithm. I think it may be for convex polyhedron. We have convex polygons, but definitely not convex polyhedron [that would be wrong]. Anyway, it would explain why some things are missed. If I am right, we'll have to find a different algorithm. I tried find evanw's email but didn't find it. Perhaps we could ask him about the origins of the algorithm, that might quickly decide the matter.

[hrgdavor]

@briansturgill there are some more in the references this one is may 2022 https://arxiv.org/abs/2205.14151 https://arxiv.org/pdf/2205.14151.pdf

[briansturgill]

OK, I have a "fix", feels more like duct-tape, but here goes. In line 245 of insertTjunctions.js: constants.EPS * constants.EPS, should only be constants.EPS I see this a lot in the code... it makes no sense. First of all, squaring EPS makes it SMALLER. This allows for LESS error. Clearly not what is desired. Didn't check it in JavaScript, but in the CSharp version, everything that was producing bad output, now produces good output. Note, I'm not saying that EPS is the correct value here, just that EPS**2 is too small.

[platypii]

Hm, I'm not seeing any effect from changing that line. On your example with the 2 cylinders, I get exactly the same numbers of non-manifold edges with EPS or with EPS EPS. I looked at the values we were getting for distancesquared and they were all either like 0 or 0.001 or 1e-32. None were affected by choice of EPS = 0.00001 or `EPS EPS = 1e-10`. Maybe I'm missing something?

[briansturgill]

Hm, I'm not seeing any effect from changing that line. On your example with the 2 cylinders, I get exactly the same numbers of non-manifold edges with EPS or with EPS EPS. I looked at the values we were getting for distancesquared and they were all either like 0 or 0.001 or 1e-32. None were affected by choice of EPS = 0.00001 or `EPS EPS = 1e-10`. Maybe I'm missing something? @platypii

Perhaps I wasn't clear enough. You do indeed still get manifold issues, etc. The changes only occur when you output an STL file. It is passing meshlab perfectly. In other words, you need to go through snap/insertTjunctions/triangulate.

I just went back and checked and that one change in insertTjunction fixes this sample: (To be clear, I checked that (EPS*EPS) failed and just EPS works (in meshlab). Git is showing no other changes in code. (Eariler I had many but backed them out.)

I even did a clean and rebuilt from scratch, just to be certain.

var g2 = new Geom2();
Geom3 TapPost(double h, double size, double post_wall = 2, bool add_taper = false, double z_rot = 0)
{
    var inner_d = size * 0.8; //Possibly snug, but with PLA I prefer that
    var outer_d = post_wall * 2 + size;
    var a = ExtrudeLinear(height: h, gobj: Circle(outer_d / 2.0));
    var b = (Geom3)Translate((0, 0, -1), ExtrudeLinear(height: h + 2, gobj: Circle(inner_d / 2.0)));
    a = Cylinder(radius: outer_d / 2.0, height: h);
    b = (Geom3)Translate((0, 0, -1), Cylinder(radius: inner_d / 2.0, height: h + 2));
    //a = Triangulate(a);
    //b = Triangulate(b);
    var gobj = (Geom3)Subtract(a, b);
    //gobj = (Geom3)ExtrudeSimpleOutlines(Circle(outer_d / 2.0), Circle(inner_d / 2.0), height: h);
    //gobj = Triangulate(gobj);
    //gobj.Validate();
    if (add_taper)
    {
        var cout = Circle(outer_d / 2.0);
        var cylout = ExtrudeLinear(height: h * 2, gobj: cout);
        cylout.Validate();
        var cin = Circle(inner_d / 2.0);
        var cylin = ExtrudeLinear(height: h * 2 + 2, gobj: cin);
        cylin.Validate();
        var cb = Cuboid((outer_d, outer_d, h * 3 + 2), center: (0, 0, 0));
        cb.Validate();
        var g3 = (Geom3)Subtract(cylout, Translate((0, 0, -1), cylin));
        //g3.Validate();
        g3 = (Geom3)Subtract(g3, Rotate((45, 0, z_rot), Translate((0, 0, h), cb)));
        //g3.Validate();
        gobj = (Geom3)Union(gobj, (Geom3)Translate((0, 0, -h * 2), g3));
    }
    return gobj;
}

/*
var a = Cylinder(radius: 4.5, height: 8, segments: 10);
a.Validate();
var b = (Geom3)Translate((0, 0, -1), Cylinder(radius: 2, height: 10, segments: 10));
b.Validate();
var g = (Geom3)Subtract(a, b);// TapPost(8, 5, add_taper: false);
*/
var g = TapPost(8, 5, add_taper: true);
Save("/tmp/test.stl", g);
//g.Validate();

[briansturgill]

So, EPS (1e-5) might be too large: (I'm refering to its use in insertTjunctions.js, not elsewhere). For:

g = Union(Sphere(radius: 20), Translate((5, 5, 5), Sphere(radius: 20)));
Save("/tmp/test.stl", g);

I set the value to 1e-6 and get no errors from meshlab. At 1e-5. it causes 1 failure that was different (I thought maybe it "fixed" a T-junction that wasn't a T-junction. At 1e-7 Boundary Faces and Boundary edges exist, though I have no idea what that is or if they are bad. At, 1e-8 and below still sees errors from unfixed T-junctions.

I'm going with 1e-6 at the moment.

The real solutions is to of course not to create T-junctions to begin with. One serious problem with the current algorithm is it doesn't require triangulation. Booleans are much simpler when everything is a triangle.

UPDATE: I did more research on boundary faces and edges, they are bad. None of them should be showing either. https://pages.mtu.edu/~shene/COURSES/cs3621/SLIDES/Mesh.pdf

[briansturgill]

OK, I've tried various values, it looks like 1e-6 works the best. This is all very much a hack though.

[briansturgill]

Ok, after mind numbing searching, I think I've found the general approach that should be used to replace 3D boolean processing. This approach is used in Blender and CGAL and apparently in OpenGL as well. It requires that meshes be triangulated. There are a number of papers: https://cims.nyu.edu/gcl/papers/zhou2016mas.pdf https://arxiv.org/pdf/1601.07953.pdf https://igl.ethz.ch/projects/winding-number/robust-inside-outside-segmentation-using-generalized-winding-numbers-siggraph-2013-jacobson-et-al.pdf https://www.dgp.toronto.edu/projects/fast-winding-numbers/fast-winding-numbers-for-soups-and-clouds-siggraph-2018-barill-et-al.pdf These 4 papers all contain Alec Jacobson (ETH & Univ. Toronto) as a primary/co-author.

[elalish]

Sorry to jump in late; I just found your library. I too am a big fan of OpenSCAD, web development, and computational geometry. I've been building a library that might be helpful on the Mesh Boolean front: https://github.com/elalish/manifold

It's C++, but we now have a WASM build that's <200kb; you can see a really basic test here. I built it from the ground up for topological robustness; I can't promise there are no bugs, but I think it avoids a lot of the problems being talked about here. If anyone wants to kick the tires, I could definitely use more bug reports.

As a bonus, it's also several orders of magnitude faster than OpenSCAD: https://elalish.blogspot.com/2022/03/manifold-performance.html (and it's had some performance improvements since this was written).

[hrgdavor]

@elalish wow, that looks promising indeed. We are definitely interested in making the boolean engine plugabble at some point and also explore what there is. I am also very curious seeing that you also have a gpu variant.

[briansturgill]

Sorry to jump in late; I just found your library. I too am a big fan of OpenSCAD, web development, and computational geometry. I've been building a library that might be helpful on the Mesh Boolean front: https://github.com/elalish/manifold ...

@elalish Interesting, does the algorithm you are using require the meshes to be triangulated. (Our current one doesn't, but I'm having trouble find one to replace that directly.) I'm doing a C# translation of JSCAD, with a Python API Wrapper. C++ is somewhat problematic for me, though I guess I could translate that too. :-)

I don't think you're late to the game at all... currently focused on fixing the 2D problem. But 3D needs done too!

[elalish]

So, yes and no. Manifold's API is based on triangle meshes (I wouldn't trust an input polygonal face to be planar). However, a Boolean operation obviously creates polygonal faces from triangle inputs, so I have internal triangulation and decimation routines to return it to a clean triangle mesh. I invented by own robust triangulator as part of writing this library, since none of the existing ones could guarantee manifoldness and handle rounding errors the way I wanted.

The Boolean itself can operate on polygon meshes and I tried that approach (leave the internal data structure polygonal and only triangulate at the end as needed), but it turns out there are nasty edge cases when input polygons are nearly coplanar and when the polygons have holes. It's much more reliable to triangulate at each step.

[briansturgill]

@elalish

The Boolean itself can operate on polygon meshes and I tried that approach (leave the internal data structure polygonal and only triangulate at the end as needed), but it turns out there are nasty edge cases when input polygons are nearly coplanar and when the polygons have holes. It's much more reliable to triangulate at each step.

Yeah, that's the conclusion I've been coming to as well... First I need to get 2D Primitives and Extrudes robust and properly triangulated (almost there), then I'll tackle 3D. Any suggested papers for 3D mesh booleans? Oh, I love the GPU stuff.... but not likely practical for my own project at this stage. EDITED: Never mind my question, I found your cache of papers here (Thanks!): https://github.com/elalish/manifold/tree/master/docs

[elalish]

Manifold already has a Python API wrapper, in addition to WASM. Is there a reason you can't use it directly? It has extrusion with triangulation and lots of other handy functions. If you're interested in collaboration, it would be great to flesh out our 2D subsystem (I'm thinking of taking a dependency on clipperLib).

[briansturgill]

Working on 3D now. Does anyone know why the retessellation of coplanar polygons were added to the 3D booleans? The algorithm seems to be designed to remove the triangulation that I have been working so hard to add. Why did someone think this is needed? I tried to look in the git logs, but it only goes back to the last source tree reorganization. Anyway, I have commented it out at the moment, and it doesn't seem to hurt anything. (Actually, it made 3D booleans run significantly faster.)

[z3dev]

Working on 3D now. Does anyone know why the retessellation of coplanar polygons were added to the 3D booleans? The algorithm seems to be designed to remove the triangulation that I have been working so hard to add.

simply to reduce the number of small polygons, which is a by product of the booleans.

[briansturgill]

Ok, now I know way more about BSP trees than I ever wanted to know. I also no why the retessellation was absolutely necessary... in fact Naylor knew about this problem in 1990. I add some paper links in the next comment. The short version: The BSP boolean algorithm is severly broken. As Naylor admits the problem, one thinks it might be an intractable problem. But the problem with boundary conditions (i.e. T-junctions) and the tiny triangles are all expected. JSCAD is amazing in that it was made to more or less work. Here's his comments (THE UPPER CASING IS MY EMPHASIS.) He fails to mention the real problem is that the algorithm breaks things up so oddly that it is impossible to act on structural knowledge.

VII.  Numerical Robustness

The occurrence of numerical errors due to finite arithmetic has
been a nemesis of geometric computing since its inception. Its
negative impact is greatest when the result of a numerical com-
putation is used to discriminate logical alternatives in an algo-
rithm. This can lead to arbitrarily "discontinuous" behavior;
that is, the output of the algorithm can be highly sensitive to~
small random perturbations of the discriminators (the program
may fail as well). While a number of schemes have been devised
to ameliorate the problem, the simplest and most common is
the use of e-intervals. For example, a discrimination based on
whether a real value X is less than, greater than, or equal to 0
can be replaced with one that determines whether a X < -e, X >
+E, or in [ - e +el respectively. More sophisticated methods
enforce the intended semantics through a variety of schemes (
see e.g. [Karasiek 89]).

The only numerical computation in this work is the parti-
tioning of a polygon by a plane. Its primitive operation is the
dot product of a point and a plane to determine the location of
that point with respect to the plane. The specific algorithm we
use assumes the semantics of planar, convex polygons, and we
rely on the epsilon method just described to attain robustness
(to dampen the noise). Thus, the hyperplanes are in effect slabs
2E thick. ANY FAILURE OF THIS TECHNIQUE IS DETECTED, BUT NO
CORRECTION STRATEGY IS EVIDENT OTHER THAN USING LARGER EPSILONS
(THIS HAS BEEN IN USE SINCE [Naylor 81]).

Unfortunately, THIS APPROACH IS INSUFFICIENT TO ACHIEVE A RO-
BUST BI-PARTITIONING OPERATION. In fact, larger epsilon exacer-
bate the problem. Recall that there is a correlation between the
location of the two bps: P l ' s location = IrgBoth ¢=> P2's loca-
tion = InBoth, and similarly On ¢=> On, and NotInBoth ¢0
NotInBoth . Numerically this does not always hold. OUR AP-
PROACH IS TO DETECT INCONSISTENCIES AND INDUCE A MAPPING TO ONE
OF THE CONSISTENT RESULT. When one location is InBoth and the
other is InNegHs or InPosHs, we can force the the former to be
either InNegHs or InPosHs by selecting the "half" which
contain vertices farthest from the partitioning plane, or we can
force the second to the InBoth condition by extracting "on"
vertices. If only one bp is On, we force it to a value consistent
with the other bp. WHILE WE BELIEVE THAT FORCING SEMANTIC CON-
SISTENCY IS ESSENTIAL, OUR CURRENT CHOICES FOR ENFORCING THIS ARE
AT THIS POINT ONLY TENTATIVE.

NUMERICAL PROBLEMS ALSO AFFECT ATTAINING THE SEMANTICS OF
THE NEIGHBORHOOD OPERATION. The method used for constructing
bsp trees, defined in the continuum, implies that any sets lying
in T.root region.bp.shp will not be On any sub-hp in either of
T's subtrees; however, NUMERICALLY THIS DOES NOT ALWAYS HOLD.
We employ the following defense. When a face fragment from
node V is classified as On during the neighborhood operation at
a descendant node U, we essentially treat that node as if it were
contained in the face's sub-hp, i.e. as if it did not exist. We
then choose the subtree of U that is "not adjacent" to V, and
continue the search.

The combination of these techniques has led to a robust set
operation algorithm is the sense that the program will not fail
and its output is in the neighborhood of the ideal output over a
large numerical range. For example, the standard test in which a
set operation is performed between a cube and a second cube
that has been rotated successively about each of its three prin-
cipal axes by an angle 0t has been executed successfully with
viewing resolution. AN UPPER BOUND TO THE THICKNESS IS THE
POINT AT WHICH THE AFFECT OF TREATING FACES AS BEING CO-PLANAR,
WHEN IN FACT THEY ARE NOT, BECOMES VISIBLE TO A VIEWER.

[briansturgill]

The paper quoted above is "Merging BSP Trees Yields Polyhedral Set Operations" http://www.vjlove.com/publications/papers/siggraph90.pdf This paper was not what evanw was using (at least not directly) It refers to "in" and "out" faces.

I believe than evanw may have been using either an early version of this next paper, or else both he and this group of students learned from the same source: https://static1.squarespace.com/static/51bb9790e4b0510af19ea9c4/t/51bf7c34e4b0a897bf550945/1371503668974/CSG_report.pdf Both evanw and the group of students refer to "front" and "back". That group of students seem to have hit similar problems to what we have experienced. It is amazing that JSCAD has gotten things to work as well as they did.

Anyway, I'm moving on to rolling my own algorithm. Most things these days are hardware oriented. Old school approaches even worked on arbitrary polygons. Though do to colinear/coplanar issues, one is definitely better of with triangles. So using what I've gleened from O'Rourke and others, I'm going to take the obvious old school approach, but on triangles. The first cut will be O(n)+O(m^2) where in "n" is the number of polygons and m is the number of polygons not culled by a bounding-box exclusion. In the end I expect I'll end up with O(n)+O(m log m) as there are various techniques to cut down on the intersection checks.

[elalish]

@briansturgill Indeed, I started my Manifold library because A) some folks I worked with in the CAD industry said a robust mesh boolean operation has been an open problem for a long time and they didn't think it was feasible to solve and B) I found someone's dissertation that outlined a new approach avoiding floating-point error entirely. It's taken me years, but I haven't found a manifoldness error in ages. Might you be interested in collaboration? It's a long road to reimplement.

[briansturgill]

... It's a long road to reimplement.

I'm not entirely ruling the possibilty of collaboration out, but I think I'm a lot closer than you think I am. O'Rourke Computation Geometry in C is a good place to look at the old school approach to booleans.

Note, we might be talking at cross-purposes here. If you are dealing with meshes for more than say 3D printing... especially if you are dealing with models that will go through constant hardware manipulation... robutness has a much different meaning. For my purposes (an OpenSCAD replacement), being what is sometimes called "numerically stable" is sufficient.

You aren't going to put such a model through 1,000,000 random boolean ops. You just need to not be sloppy. I've already gotten the rest in line... I just need the 3D booleans. They really are not that hard, especially as I am not doing realtime stuff. I just need to get the performance to be sufficient. I'll be very shocked if I can't beat the existing algorithm in a couple of week's time. Mostly because the existing algorithm needs FOUR different fix-it passes. Really, that's just sad.

[hrgdavor]

Looking at this topic I am more and more convinced that jscad take more effort in separating modeling part of the library from the actual boolean operations, or even further than just booleans.

One big reason is that I have different priorities for the output precision correctness and speed depending if I am rendering preview or exporting for 3d printing .

@elalish I have bookmarked manifold, and hopefuly will have time in the future to play with it too :)

[hrgdavor]

Also I would like to point you to checkout https://github.com/bluelightning32/walnut A design doc for how the internals of Walnut work is available at: https://docs.google.com/document/d/1G9616Bs4OURC1fKEUgY0b25A_Wra7Mn9mVxW1SmjVRY/edit?usp=sharing

[elalish]

Thanks for the pointer, that library looks cool. I was thinking about how to fix up non-manifold / self-intersecting input and that looks like it could help.

[elalish]

@briansturgill I just got a notification from you on this thread, but your comment seems to have vanished. Anyway, I thought you might be interested in a JS example of manifold: https://elalish.github.io/manifold/bindings/wasm/examples/model-viewer.html - the whole library is <150kb gzipped.

[briansturgill]

@elalish Yeah, I posted, then deleted it as I haven't made up my mind. I agree that "It's a long road to reimplement". Every academic source left out the hardest parts, yet still claimed to be robust. Much of the open-source is not really open (tied up in GPL). I've been through several algorithms in detail in the last few weeks and several things are true: 1) Implementations, even when using exact arithmetic, fall short of robust, often failing to even to do manifold. 2) All algorithms I've seen need much post processing to fix things. 3) Many algorithms/implementations admit up front that their 3D booleans are not robust. Looking at Smith's dissertation, it is clear that he doesn't really do everything he says (and your own writeup about implementation confirms that).

Note the above seems to be true of Manifold as well (except you've focused on being manifold).

So, I'm in a quandry. Manifold is roughly 2x bigger than the equivalent code in JSCAD. I suspect that the algorithm is faster, but that isn't certain. Both algorithms are complex and only running head to head with the same examples on the same hardware would determine relative speed.

I had written (in the post I deleted) that I was about to attempt that comparison, but when I started in on trying to compile the code, I discovered you had only compiled it on Linux. Having done a lot cross-platform C++ in my life, this was the last straw... I'm not interested in trying to get it to work on the 4 (soon 5 or 6) platforms I want this to run on. C++ always claims to be portable, but life is very unpleasant there. My C# code (developed on Linux) ran first shot on Windows and MacOS. NO RECOMPILATION WAS NEEDED! Though recompilation to native also worked first shot.

So, I'm beating on the insertTjunction code again, trying find a way to get objects to be manifold after each operation. If necessary, I'll just make the validation not check manifold if it's been through a boolean op.

In the end, I've gotten things to be reliably manifold after post-processing, but only if the geometry has been snapped, which you can only do that once without causing problems. Adding the geometry flag for it being through a boolean op would also be helpful in knowing that the insertTjunction was actually needed. (Currently, all output goes through that.)

I don't see a way forward with Manifold... translating that modern C++ (good code BTW) to C# would be very difficult. I would not attempt it without some evidence that the algorithm was significantly faster than the current one.

[elalish]

Thanks for the writeup; I agree with most of what you're saying. However, a few things:

We do in fact have Manifold now compiling on a variety of targets, including Windows (build steps in yml, CI results). Github doesn't have a MacOS CI, but a user did report that it worked there with LLVM (obviously not the CUDA-accelerated version, but the single-threaded is fine). And of course we have the WASM build, which I figured was the only part that would matter for OpenJSCAD, given the name, but perhaps I'm missing something?

I would say your 1-3 points do not in fact apply to Manifold; really its whole purpose of existence is solve those for the first time. It does do post-processing, but that is for performance and ease of use of the output. It is guaranteed manifold at every step (this used to only be true for geometrically-valid input, but even that requirement has now been removed).

I appreciate the code review in any case! I really need to update our README; a lot has changed. I don't know that Manifold is significantly faster than what you have now, at least in single-threaded mode. I would expect it to be about the same or better - it's the guaranteed manifoldness that sets it apart.

[udif]

Github doesn't have a MacOS CI

I think it does, you can take a look at this as an example . You can also take a look at MacOS jobs here .

[briansturgill]

@elalish

... And of course we have the WASM build, which I figured was the only part that would matter for OpenJSCAD, given the name, but perhaps I'm missing something?

I'm with CSharpCAD (and Pycscad)... a port of JSCAD that has some extras (and is missing a few things too)... I share code/bug reports/ideas with the JSCAD people but am not a part of their team.

Have you ever run your WASM version against JSCAD?

[hrgdavor]

which I figured was the only part that would matter for OpenJSCAD, given the name, but perhaps I'm missing something

you are right here regarding jscad, I have bookmarked manifold to look into at some point later

[elalish]

@briansturgill Gotcha; indeed it's less appropriate for CSharpCAD 😄 We do have Python bindings now if that's useful.

Thanks @udif, I didn't realize that. We'll have to add it.

We're working on getting a v2.0 out the door fairly soon; a lot of work has happened in the last 6 months! So stay tuned for that release.

[briansturgill]

@elalish I discovered that the Bytecode Alliance released wasmtime-dotnet 1.0 5 days ago, so I was going to try Manifold for speed. But I cannot get it to build. I am confused, you seem only to build it with Github CI? I just wanted to get Python and WASM versions under Linux.

[elalish]

Cool! Would you mind filing an issue with your build difficulties? I have been using manifold.yml as our canonical build instructions since the CI validates they are complete and correct. As I say, I need to update the README with some distillations of that. But seeing the troubles people have will help me know what to write there.