Clever 2D mode?

[ramcdona]

In addition to 3D boolean operations, my program needs to do some 2D work (actually in UV coordinates of 3D surfaces). Here we intersect and mark a 2D 'SubSurface' in a surface.

Here are two examples, a UV ellipse on the upper surface of a wing and a control surface that is on the upper and lower surfaces of the trailing edge of the wing.

Instead of a traditional Boolean operation, I calculate the intersection to 'impress' the second onto the first. In this case, the first is a mesh and the second is 'just' a polyline.

In the current world (where my CSG engine doesn't care about manifolds except for inside/outside detection) we do this by expressing the first mesh in UVZ (where Z=0) like a sheet of dough. We then make a cookie cutter mesh out of the UV polyline by extruding it in the Z direction from [-1,1] and connecting the points to a simple mesh. We then intersect these two UVZ meshes, we interpolate the XYZ points. We color the triangles as inside/outside the cutting polyline.

I don't do all this in XYZ because when the UV subsurface intersects only the upper or lower surface, it wouldn't be possible to construct the cutting surface in a way that it is guaranteed to not intersect the opposite surface. By un-rolling to a sheet of dough and using a cookie cutter approach, we can avoid those problems.

Is there a clever way to work in 2D in Manifold?

My current thoughts are:

1. Proceed substantially as I currently do, but extend my sheet of dough to form a volume manifold. Likewise extend the cookie cutter to form an enclosed volume manifold. Perform the intersection algorithms required to get both the 'inside' and 'outside' surfaces. (hopefully use Manifold's interpolation, but revert to the existing interpolation if required).

2. Attempt to use Clipper2. From what I can tell, it works exclusively with polylines (not meshes). So I would either need to treat the mesh as a large number of independent triangles, or as a large number of independent edges. In either case, this seems like I would need to implement my own spatial search (quadtree) to accelerate the process as Clipper isn't really set up to handle bulk requests in this way.

3. Write a new from-scratch 2D mesh-polyline intersection algorithm. I hate to go this way, but it seems like a substantially simpler problem than general 3D booleans and it might not be 'too bad'. A complete algorithm should be able to be based on 'only' a robust 2D line-line intersection algorithm.

4. Something else.

[elalish]

I think of this as two different features used together:

1. Having a slice (better name?) operation the intersections between the manifolds is merely carved into the first manifold's triangles, probably with a new given originalID to mark them and keep them from being immediately decimated back together. We've talked about this before, and I don't think it would be a huge hassle to implement.
2. Having some way to do a boolean with an oriented CrossSection that implicitly extrudes it, but stops at the first intersected surface. I've thought about this occasionally, but it seems like it'll get sticky when the extrusion only partially intersects the manifold. Curious what you think expected behavior should be in that situation?

[elalish]

The key to robustness is that there is no assumption that the winding numbers are all 0 or 1 - of course that's the case we mostly care about, but we'll get a manifold result for self-intersecting meshes as well when that's no longer true. So you can work out most of it assuming the winding numbers are just 0 and 1 and ensure it all makes sense, then check a self-intersecting case just to make sure it's sane, but we're less concerned about the result in that case.

[ramcdona]

I've modified the enum in public.h

enum class OpType { Add, Subtract, Intersect, KeepP, KeepQ };

And then I've modified boolean_result.cpp

` // Add, Subtract, Intersect, KeepP, KeepQ
const int c1tab[] = { 1, 1, 0, 1, 0 };
const int c2tab[] = { 1, 0, 0, 0, 1 };
const int c3tab[] = { -1, -1, 1, 0, 0 };

const int c1 = c1tab[ (int) op ];
const int c2 = c2tab[ (int) op ];
const int c3 = c3tab[ (int) op ];`

I think this should work (but haven't been brave enough to try it yet.)

The next dozen lines of Boolean3::Result() contain some logic based on the operation type. I haven't thought through what to do in the new cases for those.

I also have no idea what other changes might need to be made throughout the library.

[elalish]

Fear not, just start a PR and let's discuss there. I think the places where c1, c2, c3 are used will probably have to change a little. Conceptually for inclusion numbers, you need all the i12 and i21 to be kept (verts at the intersections of edges, 1d, and faces, 2d), so those can't be multiplied by zero. For i03 and i30 (retained verts from P and Q, respectively) you'll need to keep all of one and none of the other, regardless of their winding number. Hopefully the rest will just fall into place, but we'll see.

[ramcdona]

PR created here #578.

From the way the inclusion summation worked, I was hoping that cA and cB contained the full intersected set of A and B respectively -- and cI contained just the parts in the intersection.

From your comment, this seems to not be true. So yes, it looks like more than a simple net set of constants is going to be required.

I think my next step would be to split the idea of cI. Such that one value cIA is applied to X12 and X03 and cIB is applied to X21 and X30. In the current cases (Union, Intersection, Difference), cIA==cIB always. However, allowing them to be different might allow what we need here.

I agree that we need to somehow tag the tris differently from which set they came from. Adding an offset to OriginalID, or perhaps even negating it might be options.

I know this will go over like a lead balloon, but if you could tolerate non-manifold output, you could put the two parts into separate manifolds -- they'd be manifold as a combination.

As far as API goes, I also like the idea of an equivalent to the Split() command for this. I.e. execute one Boolean operation and get back both KeepP and KeepQ in two results.

[elalish]

Indeed, Manifold is the name of the library after all - we'll be sticking with manifold output. Once you allow a bit of non-manifoldness, then anything becomes valid, even STL-style triangle soup. This gives us a hard backstop to our testing, and something our users can rely on.