Overlapping geometry and inconsistent results when subtracting meshes
zilmarinen opened this issue · 5 comments
I am frequently seeing inconsistent results when performing mesh operations. Specifically subtract in this instance but I have also encountered several "holes" popping up when merging meshes with union.
Below is a screenshot showing the missing polygons (giant hole on the left) and also two instances of overlapping geometry (circled) after a subtraction operation.
The holes appear semi-randomly between iterations. I can run this several times and get different results each time, occasionally giving the correct result. I have tried different shape configurations and adjusted the depth of the two penetrating meshes but still get the same intermittent results.
As for the overlapping polygons; these are difficult to see in the screenshot but obvious when viewing/rotating around the model. These appear at various points along the outer facing edges of the mesh and can be seen clipping through each other. This happens every time regardless of the "correct" output but only seems to be a symptom of the subtract operation.
@CaptainRedmuff that's interesting. There is an element of randomness to the BSP generation, but it's seeded and should be consistent every time it runs for the same set of geometry. I may have inadvertently used an unordered Set or something in the process that causes non-deterministic behavior.
Again, it would be very helpful if you could supply a sample project, or at least some saved geometry I can use to recreate the specific issue you're seeing.
@nicklockwood Many thanks for your response and looking into this.
Hopefully you should be able to recreate this using these meshes by subtracting the inner mesh from the outer mesh.
I have not been able to find a means to consistently reproduce the holes appearing when performing a union but perhaps this might be due to the behaviour you described.
@CaptainRedmuff I believe I've worked out what's causing the disappearing polygons in your mesh. The inner and outer meshes that you provided are not watertight - the polygons do not meet at their edges, but are overlapping.
I extracted the polygon data for a single face of the shape and rendered it with different colors applied to each polygon to demonstrate the issue. Do you see the cross-hatching effect at the edges? That's z-fighting, caused by two polygons overlapping on the same plane.
Did you construct these Meshes using from smaller components by combining them with Euclid? If so, please share the base components, and I'll see if I can drill down to the root cause.
(FYI, here is the code I used to generate the mesh in the screenshot:)
let normal = Vector(0, 1, 0)
mesh = Mesh([
Polygon([
Vector(-0.54, 0.125, -0.51),
Vector(-0.49, 0.125, -0.45999999999999996),
Vector(0.49, 0.125, -0.45999999999999996),
Vector(0.49, 0.125, -1.441),
Vector(0.441, 0.125, -1.49),
Vector(-0.54, 0.125, -1.49),
].map { Vertex($0, normal) })?.with(material: UIColor.red),
Polygon([
Vector(-0.49, 0.125, 1.441),
Vector(-0.441, 0.125, 1.49),
Vector(0.54, 0.125, 1.49),
Vector(0.54, 0.125, 0.51),
Vector(0.49, 0.125, 0.45999999999999996),
Vector(-0.49, 0.125, 0.45999999999999996),
].map { Vertex($0, normal) })?.with(material: UIColor.green),
Polygon([
Vector(0.45999999999999996, 0.125, 1.49),
Vector(1.441, 0.125, 1.49),
Vector(1.49, 0.125, 1.441),
Vector(1.49, 0.125, 0.5589999999999999),
Vector(1.441, 0.125, 0.51),
Vector(0.45999999999999996, 0.125, 0.51),
].map { Vertex($0, normal) })?.with(material: UIColor.blue),
Polygon([
Vector(-0.49, 0.125, 0.54),
Vector(0.49, 0.125, 0.54),
Vector(0.49, 0.125, -0.54),
Vector(-0.49, 0.125, -0.54),
].map { Vertex($0, normal) })?.with(material: UIColor.purple),
Polygon([
Vector(-1.49, 0.125, -0.5589999999999999),
Vector(-1.441, 0.125, -0.51),
Vector(-0.45999999999999996, 0.125, -0.51),
Vector(-0.45999999999999996, 0.125, -1.49),
Vector(-1.441, 0.125, -1.49),
Vector(-1.49, 0.125, -1.441),
].map { Vertex($0, normal) })?.with(material: UIColor.orange),
].compactMap { $0 })@nicklockwood Oh dear. I feel like a complete idiot 😰
These meshes were not generated using Euclid components. I am stitching together the polygons programatically based on Pentomino meshes and had incorrectly projected the outer vertices of each tile into its neighbour.
Apologies for wasting your time on essentially debugging a problem in my own mesh generation!
@CaptainRedmuff no problem - I'd like to try and make the error detection and correction more robust anyway, so this was a good test case 👍