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: https://github.com/Hermann-SW/lattice_sphere_cmp/commit/083d58286c08b896e5a61205bb3f145c9af327e6#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: https://github.com/Hermann-SW/lattice_sphere_cmp/commit/7834f9a03ba058a7122af323d1e978cf289411c9#diff-93e00aa7bb721b3cc9d54a52895f396ada5a8dc0093c4c223ef9d7c39a1c145c https://github.com/Hermann-SW/lattice_sphere_cmp/commit/78225b5f94c8103bfdfdaf699b288428eb7497ca#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: https://github.com/mauriciopoppe/quickhull3d/issues/30#issuecomment-2170973708

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: https://github.com/mauriciopoppe/quickhull3d/issues/30#issuecomment-2176949401

   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.