Bug in blueprint fusing algorigthm

[paulftw]

Code below throws a "Bug in blueprint fusing algorigthm" exception.

First two triangles share one vertex, so fuse2D returns Blueprints. Fusing Blueprints with a triangle that overlaps only one of the blueprints raises an error.

const triangles = [
  [
    [8, 27],
    [7, 35],
    [11, 15],
  ],
  [
    [11, 15],
    [0, 15],
    [3, 17],
  ],
  [
    [11, 15],
    [3, 17],
    [4, 18],
  ],
]

const colors = ['red', 'green', 'blue']

 function main({BlueprintSketcher, fuse2D}) {
  const blueprints = triangles.map(([a, b, c]) =>
    new BlueprintSketcher().movePointerTo(a).lineTo(b).lineTo(c).close(),
  )

  // return blueprints.map((b,i) => ({shape:b.sketchOnPlane('XY').extrude(1), color: colors[i]}))

  const fused = blueprints.reduce(
    (acc, bp) => fuse2D(acc, bp),
    new BlueprintSketcher().hLine(1e-5).vLine(1e-5).close(),
  )

  return fused.sketchOnPlane('XY').extrude(1)
}

(a note for a separate question: all triangles here are in CW order and that works as expected, but if I change them into CCW - fuse gets confused about inside and outside of a blueprint. At the same time sketchRectangle works in CCW.

Either I am missing something obvious, or there's a difference in how sketches and blueprints work?
one way to test CCW triangles is to change the lambda inside map: triangles.map(([a, **c**, b])
)

[paulftw]

Code in question is here:

replicad/packages/replicad/src/blueprints/boolean2D.ts

Line 89 in c937113

const newFused = genericFuse(blueprint, otherBlueprint);

I think genericIntersects returns true, because triangles touch at one point. But then genericFuse returns Blueprints because it cannot combine two triangles. This edge case is considered a "bug".

It was actually really hard to tell what is the difference between Blueprints and CompoundBlueprint.
The former produces Sketches the latter - CompoundSketch.
CompoundSketch is an array of N sketches with first one representing outer "shell", and remaining N-1 representing holes.

If that is correct, then wrapping every triangle into Blueprints should have worked:

function main({BlueprintSketcher, fuse2D, Blueprints}) {
   const blueprints = triangles.map(([a, b, c]) =>
     new BlueprintSketcher().movePointerTo(a).lineTo(b).lineTo(c).close(),
   )

   const fused = blueprints.reduce(
     (acc, bp) => fuse2D(acc, new Blueprints([bp])),
     new Blueprints([new BlueprintSketcher().hLine(1e-5).vLine(1e-5).close()]),
   )

   return fused.sketchOnPlane('XY').extrude(1)
}

But it doesn't, which may mean an unrelated bug?

[sgenoud]

Note that you might alos have made some weird behaving with stuff with new BlueprintSketcher().hLine(1e-5).vLine(1e-5).close() - which is close to the precision of the fusing algorithm. Changing to the following does not explode (while the fuse is not working):

 function main({BlueprintSketcher, fuse2D}) {
  const blueprints = triangles.map(([a, b, c]) =>
    new BlueprintSketcher().movePointerTo(a).lineTo(b).lineTo(c).close(),
  )

  // return blueprints.map((b,i) => b.sketchOnPlane('XY').extrude(1+i*0.2))

  const fused = blueprints.reduce(
    (acc, bp) => fuse2D(acc, bp),
    new BlueprintSketcher().hLine(1e-5).vLine(1e-5).close(),
  )

  return fused.sketchOnPlane('XY').extrude(1)
}

As an aside I would advice you to use the draw API which hides some complexity (typically with the blueprints vs blueprint):

function main({ draw }) {
  const drawings = triangles.map(([a, b, c]) =>
    draw().movePointerTo(a).lineTo(b).lineTo(c).close()
  );

  const fused = drawings
    .slice(1)
    .reduce((acc, bp) => acc.fuse(bp), drawings[0]);

  return fused.sketchOnPlane("XY").extrude(1);
}

All of this said, it looks like you have found a bug with the single common point - I will have a look! Note that the spirit of the error message is to say there is a bug in my algo because it reached a state I thought it would not. But you found an edge case where it does.

[paulftw]

Yes, that "invisible" triangle was a workaround to get an empty Blueprint. I haven't yet found a correct way to do it, and assumed it doesn't exist.

Changing to the following does not explode (while the fuse is not working)

I went over your "changed" code sample several times to find what's changed and suspect you may have copy-pasted a wrong file 😉

But looking at your second example with slice(1) and and drawings[0] as the starting accumulator I think I know what you've meant. It does fix the "Bug in blueprint fusing" exception but result is incorrect.

[sgenoud]

Oups, yeah, copy paste error!

All in all, I have found (and fixed) the bug - can you confirm that once the latest version of the visulalizer is loaded it works?

[paulftw]

(seems like my comment disappeared, maybe I hit a network glitch)

I can confirm that v0.12.3 works great for the original test case.
However, I'm now hitting an infinite call loop in cleanEdgeCases / handleNestedBlueprints.
My test code is here, will try to clean it up to be under 200 lines of code.

Do you prefer to open a new issue (so we'd have a sense of progress by marking this one as fixed) or add a new test case here?

P.S. is visualizer closed source? I could not find its source code in the main repo.

[sgenoud]

Your triangle mesh code is perfect to find bugs in my fusing algorithm. I solved the bugs you originally reported here, but it uncovered more.

The general gist is that the mesh creates shapes that do not intersects themselves but touch themselves in one point. It messes with the assumptions I had made for my algo a lot by opening a bunch of edge cases I had not thought about. You can see my progress here

[paulftw]

Glad you are having fun! I was worried I sent too many bug reports at once :)
These triangles are from an experiment in unwrapping faces on a flat surface (think papercraft). So none of them should overlap (save for some bugs in earlier stages of my code).

Does OCJS expose any APIs to use OCCT's 2d boolean operations? I'm very new to these libraries, but this forum thread suggests there may be a function for that.

[sgenoud]

This is for merging stuff and creating faces (i.e. a 2D surface in 3D space). What I am trying to achieve with drawings (and blueprints) is to have stuff in 2D in a 2D plane - not notion of the third dimension.

For the papercraft stuff, I am not sure that merging the triangles is the good way of doing it - you still want the borders to of the triangles to exists (to make folding patterns).

Is this what you expect from the merge? Is my algorithm dropping some triangles it should not, or are there some triangles missing in your example)?

This is all in 0.12.4 (and on the visualizer) - do you confirm?

[paulftw]

Yes, your image matches the one I get if I simply extrude each triangle separately.
Closing this issue now.
Thanks a lot for fixing it!