ConvexHull example is broken

[WestLangley]

ConvexGeometry appears to be generating extra internal faces.

There are calls to Math.random() in the algorithm, so the output is not deterministic. Several refreshes may be required to see the issue.

Only tested on macOS.

Three.js version

• [ ] Dev
• [ ] r82 and later
• [ ] ...

/ping @Mugen87 Maybe this problem would interest you? ;-)

[Mugen87]

I'll put this on my todo list 😉

Maybe we can directly port this to BufferGeometry when fixing the bug...

[Mugen87]

The bug actually disappears if i delete the following lines. I'm not 100% why this offsetting is performed. @WestLangley Do you have any ideas?

Anyway, i think a typical implementation of the incremental convex hull algorithm looks a little bit different than in ConvexHull. Randomly shifting vertices should not be necessary. Besides, the actual time complexity should be O(nlogn) and not O(n^2).

Implementing a faster version will take some time. Maybe it's better to provide a quick fix first....

[WestLangley]

The bug actually disappears if i delete the following lines.

What I don't understand, is the bug does not appear to occur before rev 82. At least, I don't think it does...

Implementing this will take some time. Maybe it's better to provide a quick fix first....

Maybe a replacement would be better. See this thread: https://github.com/mrdoob/three.js/pull/1841.

/ping @marklundin

[donmccurdy]

@Mugen87 the random offsetting is common in convex hull calculation, to deal with edge cases around co-planar points, or perhaps duplicate points. I haven't implemented this incremental algorithm before (just a 2D MergeHull once) but you can reproduce the problem easily enough with a box. This snippet works only with that randomization:

geometry = new THREE.ConvexGeometry(new THREE.BoxGeometry(5, 5, 5).vertices);

EDIT: I've been using this quickhull implementation most recently. It doesn't include, but often requires, a random shuffle as well.

[Mugen87]

@donmccurdy Thanks for the explanation. I've actually never seen the usage of Math.random() in a convex hull algorithm before.

Can you say something about the numerical stability and robustness of the linked Quickhull implementation? Some time ago, i've tried to develop a Quickhull 3D port for three.js based on this presentation of Valve. Unfortunately i'v never finished this piece of code because it was too sophisticated to regard all possible invariants (see page 74).

BTW: The presentation is excellent in order to understand the details of Quickhull! 😊

[WestLangley]

Another JS implementation: https://github.com/maurizzzio/quickhull3d

with three.js r.73 demo: http://requirebin.com/?gist=9b19fccfa670c9e2597b

[WestLangley]

Fixed in #10987