nicklockwood / Euclid

A Swift library for creating and manipulating 3D geometry
MIT License
639 stars 53 forks source link

Unexpected results from multiple subtract operations on native SCNBox #87

Closed tonyskansf closed 2 years ago

tonyskansf commented 2 years ago

Hi, I'm getting weird results from multiple subtract operations between two nodes created from the SCNBox geometry—there are always some polygons from the RHS mesh remaining in the resulting mesh after the subtraction. This, however, does not happen when Euclid's Mesh.cube is used.

I believe the below example should explain what's happening. The example is simplified. I'm facing the same issue with custom nodes created from custom SCNGeometry.

Example: The loop simulates a real-time node movement (position changes) and subtraction.

Unexpected results:

// LHS node
let box1 = SCNBox(width: 0.2, height: 0.2, length: 0.2, chamferRadius: 0)
box1.firstMaterial?.diffuse.contents = UIColor.orange
let node1 = SCNNode(geometry: box1)
node1.position = SCNVector3(0, 0, -0.4)
sceneView.scene.rootNode.addChildNode(node1)

// RHS node
let box2 = SCNBox(width: 0.1, height: 0.1, length: 0.1, chamferRadius: 0)
let node2 = SCNNode(geometry: box2)

for i in 0...6 {
    let lhs = Mesh(node1).translated(by: Vector(node1.position))
    let rhs = Mesh(node2).translated(by: Vector(0, 0.12 - 0.01 * Double(i), -0.3)) // simulate movement in y-axis
    let subtracted = lhs.subtract(rhs)
    node1.geometry = SCNGeometry(subtracted.translated(by: -1 * Vector(node1.position)))
}

Works fine with Euclid's Mesh.cube:

// LHS node
let box1 = SCNBox(width: 0.2, height: 0.2, length: 0.2, chamferRadius: 0)
box1.firstMaterial?.diffuse.contents = UIColor.orange
let node1 = SCNNode(geometry: box1)
node1.position = SCNVector3(0, 0, -0.4)
sceneView.scene.rootNode.addChildNode(node1)

for i in 0...6 {
    let lhs = Mesh.cube(size: Vector(0.2, 0.2, 0.2), material: UIColor.orange).translated(by: Vector(node1.position))
    let rhs = Mesh.cube(size: 0.1).translated(by: Vector(0, 0.12 - 0.01 * Double(i), -0.3))
    let subtracted = lhs.subtract(rhs)
    node1.geometry = SCNGeometry(subtracted.translated(by: -1 * Vector(node1.position)))
}
nicklockwood commented 2 years ago

Thanks for the detailed report - I'll look into it.

tonyskansf commented 2 years ago

I did some digging and noticed this with the mesh created from the SCNBox geometry:

The polygons share vertices; however, in some cases, these (visually same) vertices have different values in their x, y, or z position coordinate. Although those values vary, they visually represent the same vertex.

(It seems like this is the reason why polygons.areWatertight would return false for this geometry even though the mesh is watertight as every edge is attached to at least two polygons.)

Not sure if it helps anything, but I thought it might have something to do with how polygons/vertices are compared during the subtraction algorithm (?).

I'd like to look into this more too, so if you have any idea where the problem might root from, I'm more than happy to help debug this.

nicklockwood commented 2 years ago

@tonyskansf AFAICT the issue is with the actual vertices produced by SceneKit. If I reduce the precision value in Utilities.quantize() down to 1e-7 it solves the problem, but that's not really a good solution as it breaks other models with fine details.

I'm not really sure what to do about it. I could add a special case to produce clean data for SCNBox, but that wouldn't solve the general problem. Maybe I need to add some code to clean up vertex data generally.

nicklockwood commented 2 years ago

Hmm, it seems like reducing epsilon to 1e-7 also solves the problem, and is a slightly less terrible solution. I'm still not very happy with simply tweaking magic numbers as a solution though, since there are presumably other cases which this would either break or fail to solve.

tonyskansf commented 2 years ago

Just as you said, reducing the numbers might help in this specific case, but is breaking other cases. I still have two input meshes that are watertight but the resulting mesh after subtract is not even though there is no reason not to be. Not sure however how to proceed further with the issue.

nicklockwood commented 2 years ago

@tonyskansf this should be fixed in 0.5.19. I've added some additional logic to makeWatertight() that merges vertices that are close but not exactly equal, such as those in the SCN primitives.