3D quickhull() does not always work correctly when all vertices are in same plane

[Hermann-SW]

Expected Behavior

With five convex 3D points, geom3.fromPointsConvex() calling quickhull() should return pentagon.

Actual Behavior

Only 4 of the 5 points are part of response (right, with eps=0).
With eps=1e-10 moving one point out of plane a bit (left) all 5 vertices are in response.
With eps=1e-15 moving one point out of plane a bit (middle) only 4 of 5 points are part of response.

Steps to Reproduce the Problem

1. open below code in jscad.app

const jscad = require('@jscad/modeling')
const { geom3 } = jscad.geometries
const { hull } = jscad.hulls
const { sphere } = jscad.primitives
const { translate } = jscad.transforms

function fromPointsConvex(listofpoints) {
return hull([geom3.create(),
  geom3.fromPoints(listofpoints.map((p) => [p,p,p]))])
}

const eps = [1e-10, 1e-15, 0]

function e(ep,i) {
pts = [[-8,1,0],[-7+ep,4,0],[-6,5,-2],[-7,0,-4],[-8,0,-1]]
g = /*geom3.*/fromPointsConvex(pts)
console.log(JSON.stringify(g))
return translate([0,-6*i,0],
                 [g,
                  pts.map((p)=>translate(p,sphere({radius: 0.1})))])
}

function main() {
return eps.map((ep,i)=>e(ep,i))
}

module.exports={main}

This is not a problem specific to geom3.fromPointsConvex().
Above implementation based on hull() shows same behavior.
So it is quickhull() problem for all 3D points in same plane.

Specifications

• Version: latest modelling with new geom.fromPointsConvex()
• Platform: ubuntu 22.04
• Environment: firefox

[Hermann-SW]

I implemented a workaround for my app in this diff:
Hermann-SW/lattice_sphere_cmp@083d582#diff-93e00aa7bb721b3cc9d54a52895f396ada5a8dc0093c4c223ef9d7c39a1c145c
Just add centroid to convex points of a face with subtracted normal scaled with 1e-3, that makes not all points on same plane and quickhull() does its job correctly. Because of scaling factor 1e-3 this workaround is not visible in jscad.app.
Easiest example is to select p=5, q=13, "= pq" and "centroid!=normal +face", reducing scaling factor to 1e-1 makes workaround visible. Reducing scaling factor to 0 undos workaround and shows problem, in that case two triangles of a hexagon are missing.

[Hermann-SW]

Fix is discussed and implemented in this thread:
https://discord.com/channels/775984095250612234/1248251413629370389
In case of all points in a plane the resulting geom3 needs the convex face two times, in both orientations.
Demos for that are in the thread, the code is in these commits:
Hermann-SW/lattice_sphere_cmp@7834f9a#diff-93e00aa7bb721b3cc9d54a52895f396ada5a8dc0093c4c223ef9d7c39a1c145c
Hermann-SW/lattice_sphere_cmp@78225b5#diff-93e00aa7bb721b3cc9d54a52895f396ada5a8dc0093c4c223ef9d7c39a1c145c

[z3dev]

JSCAD could make a patch but it would be better to have the original author make a patch to quickhull3d

https://github.com/mauriciopoppe/quickhull3d

[Hermann-SW]

Hi,
i would really like to create an issue in that repo and provide pull request there.
But I cannot get a single demo working.
I did

pi@raspberrypi5:~ $ npm install --save quickhull3d

added 6 packages in 4s
pi@raspberrypi5:~ $

But no example works, here from README.md:

pi@raspberrypi5:~/quickhull3d $ node
Welcome to Node.js v18.19.0.
Type ".help" for more information.
> import qh, { isPointInsideHull } from 'quickhull3d'
import qh, { isPointInsideHull } from 'quickhull3d'
^^^^^^

Uncaught:
SyntaxError: Cannot use import statement inside the Node.js REPL, alternatively use dynamic import: const { default: qh, isPointInsideHull } = await import("quickhull3d");
> 

Unfortunately the repo sandox link does not work either.

Are you able to use that repo somehow?
If so, how?

[z3dev]

It's not trivial. I think the documentation was incorrect.

First, you need to create a new package with type module. Put this into package.json

{
  "name": "new",
  "version": "1.0.0",
  "description": "a new project",
  "main": "index.js",
  "type": "module",
  "scripts": {
    "test": "echo \"Error: no test specified\" && exit 1"
  },
  "author": "",
  "license": "ISC",
  "dependencies": {
    "quickhull3d": "^2.1.0"
  }
}

npm install

Second, you then need to import the QH function correctly. Put this into index.js

import qh from 'quickhull3d'

const runner = qh.default

const points = [
  [0, 0, 0], [1, 0, 0], [0, 1, 0], [0, 0, 1],
  [1, 1, 0], [1, 0, 1], [0, 1, 1], [1, 1, 1]
]
const faces = runner(points)

console.log(faces)

[Hermann-SW]

@z3dev THANK you for the great instructions!
Worked immediately.

After your example worked, I used the 5 points from initial posting in this issue.
And the bug shows up.
Some faces should contain point 1, but none does:

pi@raspberrypi5:~/quickhull3d $ node bug.js
[ [ 3, 0, 2 ], [ 4, 3, 2 ], [ 4, 2, 0 ], [ 4, 0, 3 ] ]
pi@raspberrypi5:~/quickhull3d $ cat bug.js 
import qh from 'quickhull3d'

const runner = qh.default

const pts = [[-8,1,0],[-7,4,0],[-6,5,-2],[-7,0,-4],[-8,0,-1]]

const faces = runner(pts)

console.log(faces)
pi@raspberrypi5:~/quickhull3d $ 

[Hermann-SW]

@z3dev
Mauricio did fix the bug:
mauriciopoppe/quickhull3d#30 (comment)

It is not a single commit but quite some.
Will you take the fix for modelling quickhull3d?

I tested that new version works for the bug input I reported:
mauriciopoppe/quickhull3d#30 (comment)

   1---0
  /   / \
2 ---/    \
| \        \
|   \ ------4
|          /
+---------3

[Hermann-SW]

I just did diff of the files in this repo's
https://github.com/jscad/OpenJSCAD.org/tree/master/packages/modeling/src/operations/hulls/quickhull

with same files with fix in
https://github.com/mauriciopoppe/quickhull3d/tree/master/src

Lots of differences ...

[z3dev]

@Hermann-SW its not the same... the quickhull library was converted to use JSCAD internals. Sadly, it will diverge a little more due to this fix.

I'm working on the changes.