nicklockwood / Euclid

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

CSG bug when operating on a particular extruded mesh #97

Open kunitsyn opened 2 years ago

kunitsyn commented 2 years ago

First of all, thank you for the library, it's awesome. I understand it's in development, and I believe it would benefit from another test case. The following code yields non-optimal results, on the current master branch:

let av = [(1.6363814, -0.42992532),
          (1.7721995, -0.34534788),
          (0.28442883, 2.0437772),
          (0.19985116, 2.1795955),
          (-2.5245433, 0.4830433),
          (-2.6603615, 0.3984658),
          (-1.1725912, -1.9906592),
          (-1.0880136, -2.1264777)]
let ap = Path(av.map { PathPoint.point(Vector(Double($0.0), -0.25924492, Double($0.1))) })
let a = Mesh.extrude(ap.closed(), depth: 2.9344041)
let b = Mesh.cube(size: Vector(size: 3))
let r = b.subtract(a)

Mesh R will look like this (with A shown in wireframe):

image

There is a hole on top, and a lone polygon (behind) not having any volume.

Here, it's not really important what B is, it looks like most CSG operations with A will have problems like these. As fair as I understand, A is watertight and otherwise "legal" to use with CSG operations.

I took some time to look into this, and it seems to me that the problem occurs during building BSP of mesh A, where the polygon with vertex positions

(-1.0880136, 1.20795713, -2.1264777000000001),
(-1.1725912000000001, 1.20795713, -1.9906591999999999),
(-2.6603615, 1.20795713, 0.39846579999999998),
(-2.5245432999999999, 1.20795713, 0.48304330000000001),
(0.19985116, 1.20795713, 2.1795955),
(0.28442883000000002, 1.20795713, 2.0437772000000001),
(1.7721994999999999, 1.20795713, -0.34534788),
(1.6363813999999999, 1.20795713, -0.42992532)

is marked as spanning with regard to another polygon's plane that's equal to normal = (x = 0.52861031077292353, y = 0, z = -0.84886461779517774) w = 1.2299564728393015, where it's probably should have been marked as a back polygon. However, I don't know exactly how to solve this problem.

nicklockwood commented 2 years ago

Thanks for reporting this, I'll see what I can do. In general I have a lot of problems with floating point precision for which there seems to be no simple solution. Usually I solve specific cases by tweaking the various epsilon values, but often this just breaks something else.