-
Notifications
You must be signed in to change notification settings - Fork 514
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
"subtract" gives bad output. #1113
Comments
OK, put updated code in original issue message. |
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:
|
|
@platypii Thanks for that example, I'm sure that will be handy while I work on this!
I'm starting to question if the right criterion is being use see the union algorithm here.
I find this very unlikely to work. The boolean algorithms only work on manifold sets of polygons. |
I'm busy until next week sometime. https://www.gamers.org/dhs/helpdocs/bsp_faq.html Here's a paper from 1990 about this... |
@platypii The union example you gave above actually works, i.e. doesn't fail under either CSCAD or the latest JSCAD. |
I should have been more clear. The example I gave DOES produce a non-manifold geometry. But on export, 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 } |
Looking at @briansturgill's example. Before nonmanifold.jsconst 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 } |
@platypii Thanks! In a manifold object, every edge has exactly two faces. That edge will get split twice. I think I'll try steping through one of your simple examples in the debugger next. |
It's a problem of precision. @platypii lets investigate those zero area polygons. The generalize functions should be removing those. |
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
<#1113 (comment)>,
or unsubscribe
<https://github.com/notifications/unsubscribe-auth/ABYCO7ZRTTYHQAQHLH742H3VQI7XXANCNFSM5ZG4SNQA>
.
You are receiving this because you were mentioned.Message ID:
***@***.***>
--
Brian
|
The serializers call generalize if necessary to create triangular meshes, etc. |
From the paper on BSP trees...
Which is the current approach being taken to classify polygons for clipping. |
I've found a better PDF of the naylor journal article: |
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.) Certainly the choice of plane for the split is very questionable. It doesn't match at all what was said in: |
Anybody at an institution that has access to this: https://www.sciencedirect.com/science/article/abs/pii/S0010448512002412?via%3Dihub |
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. |
So I think I may have figured out what is wrong with the Booleans algorithm. I think it may be for convex polyhedron. |
@briansturgill there are some more in the references |
OK, I have a "fix", feels more like duct-tape, but here goes. |
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 |
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: 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(); |
So, EPS (1e-5) might be too large: (I'm refering to its use in insertTjunctions.js, not elsewhere). 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. I'm going with 1e-6 at the moment. The real solutions is to of course not to create T-junctions to begin with. UPDATE: I did more research on boundary faces and edges, they are bad. None of them should be showing either. |
OK, I've tried various values, it looks like 1e-6 works the best. |
Ok, after mind numbing searching, I think I've found the general approach that should be used to replace 3D boolean processing. |
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). |
@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. |
@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 don't think you're late to the game at all... currently focused on fixing the 2D problem. But 3D needs done too! |
Working on 3D now. Does anyone know why the retessellation of coplanar polygons were added to the 3D booleans? |
simply to reduce the number of small polygons, which is a by product of the booleans. |
Ok, now I know way more about BSP trees than I ever wanted to know.
|
The paper quoted above is "Merging BSP Trees Yields Polyhedral Set Operations" I believe than evanw may have been using either an early version of this next paper, or else both he Anyway, I'm moving on to rolling my own algorithm. |
@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. |
I'm not entirely ruling the possibilty of collaboration out, but I think I'm a lot closer than you think I am. 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. You aren't going to put such a model through 1,000,000 random boolean ops. You just need to not be sloppy. |
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 :) |
Also I would like to point you to checkout https://github.com/bluelightning32/walnut |
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. |
@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 |
@elalish Yeah, I posted, then deleted it as I haven't made up my mind.
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, 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 So, I'm beating on the insertTjunction code again, trying find a way to get objects to be manifold after each operation. In the end, I've gotten things to be reliably manifold after post-processing, but only if the geometry has been snapped, I don't see a way forward with Manifold... translating that modern C++ (good code BTW) to C# would be very difficult. |
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. |
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? |
you are right here regarding jscad, I have bookmarked manifold to look into at some point later |
@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. |
@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? |
Cool! Would you mind filing an issue with your build difficulties? I have been using |
I'll probably do more of this discussion to Manifold's board, but felt this thread needs an update. Using union script by @platypii (translated to python and adding subtract and intersect) I managed to get a first round of timing tests comparing the C# version of the BSP algorithm with Manifold's algorithm, both using their Python bindings. I then spent the rest of the day trying to figure out if it was actually true. I've been through it thoroughly and it appears that Manifold's booleans are 3 ORDERS OF MAGNITUDE (1000x) faster than the BSP-based booleans in JSCAD/CSharpCAD. There are some caveats. First, the sphere code between the two was different, but I changed the segment values (100 for JSCAD/CSharpCAD and 150 for Manifold) so that the resulting sphere had approximately the same number of vertices and faces. The Python interface to C# is probably less efficient than the one to Manifold, however the overhead is probably not substantial realtive to the operations being tested. The test by @platypii is edge case oriented... I don't know if that is having an effect or not. Finally, JSCAD/CSharpCAD is faster handling the "disjoint" case as we have special handling for that. I'm assuming Manifold doesn't bother checking (it's still very fast for that case). Here is my code for Manifold: from pymanifold import Manifold
from time import time_ns
segments = 150
def test(x, radius, name):
s1 = Manifold.sphere(radius=1, circular_segments=segments)
s2 = Manifold.sphere(radius=radius, circular_segments=segments).translate(x, 0, 0)
start = time_ns()
ret = s1+s2
finish = time_ns()
if name == "ignore":
return
print("union", name, (finish-start)/1000000.0)
start = time_ns()
ret = s1^s2
finish = time_ns()
print("intersect", name, (finish-start)/1000000.0)
start = time_ns()
ret = s1-s2
finish = time_ns()
print("subtract", name, (finish-start)/1000000.0)
test(4, 1, "ignore");
test(4, 1, "disjoint");
test(2, 1, "touching");
test(1, 1, "overlap");
test(0, 1, "same");
test(0, 0.5, "inside"); Using separate programs, I checked the output from Manifold and it appears correct. Indeed, in the case "union overlap", CSharpCAD was producing output that was not manifold. Manifold handled it correctly. I'm hoping someone on the JSCAD team will attempt timing tests with the WASM version. |
@briansturgill, @elalish that is great news, looking forward to trying out manifold wasm |
Thank you @briansturgill! You really made my day with your analysis. Manifold does in fact have a fast path for disjoint inputs, but it could probably use further optimization; I'd guess we're not skipping as much as we could. |
Oh, forgot to answer the question: Yes, please start a Discussion thread in Manifold. |
manifold library has come a long way from when this thread was started. I am following it closely, and finally have some basinc examples working in jscad.app. My guess with manifold you would not have those errors @nmattia. I firmly believe future of jscad is in adopting manifold (if not completely, at least as an optional CSG backend) |
@hrgdavor thanks! I'm actually giving it a try. The API reference seems to have moved so it's a slow but promising start (the part that failed in JSCAD is exporting without issues in Manifold). I did have a look at the JSCAD sources and I'm actually not sure it's a boolean issue afterall (in my case); looks like it might be an issue with the way JSCAD triangulates. The STL export does have some triangulation code but AFAICT it shouldn't actually run because the model goes through Will report on how that goes! |
@udif JSCAD internally does care if polygons are triangulated or not. That's the biggest difference with modern CSG engines. let us know if you find anything suspicious, and can reproduce with a fairly simple test. |
@nmattia can you supply the name of the slicer? There are many and many are subpar when dealing with mesh issues. Blender also has 'repair' functions as Blender itself can produce invalid meshes. My personal favorite is Meshlab. You might want to look at this application. |
The slicer is PrusaSlicer, which does autorepair. Regardless of the slicer, the blender screenshot does show the issue. IIUC the technical term for the STL rule being broken here is "vertex-to-vertex rule":
Or do you mean that, upon import, Blender messed with the Mesh which makes the screenshot moot? I'll admit I didn't read the actual STL output... 😂 Thanks for pointing out Meshlab, I'll keep it in mind! EDIT: just to clarify, PrusaSlicer & Blender both showed the same issue, or rather both showed an issue at the same spot. PrusaSlicer just highlighted the edges in red, and Blender showed the vertex was on the edge and not connected to another face |
Coming in from the Manifold side of things... Please keep in mind that STL is a lossy format regarding manifoldness. Effectively all STLs (even ones produced from a proper manifold) require fixing and that fixing process is heuristic and can easily result in a previously manifold mesh becoming non-manifold, but worse, the results will be different when imported through different software. I would strongly recommend 3MF (or even OBJ) as alternatives that actually encode manifoldness (topological) data. I also authored an |
This the typical issue reported as booleans operations do not produce 'watertight' meshes. That's why all the generalize functions were created. The output is typically good enough for the slicers to print or to fix.
Absolutely not. I was just wondering which slicer was being used. Not all slicers are the same, and Prusa is one of the better ones. |
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]
The text was updated successfully, but these errors were encountered: