quickhull3d does not always work if all points are on a same plane about quickhull3d HOT 16 CLOSED

Fix released in https://github.com/mauriciopoppe/quickhull3d/releases/tag/v3.1.0

from quickhull3d.

Thanks for the graph, for the case and the expected output, I think this library can do a better job for this scenario so I have an algorithm that I haven't implemented yet.

• Before computing the initial tetrahedron check if the input is degenerate i.e. check if all the points are in the same plane
  • Pick 3 points and get a plane, project all the points towards the plane i.e. find the distance to the plane, if the projection distance is 0 for all the points then it means that all the points are in the same plane
• Translate the origin so that one of the 3 points becomes the origin, rotate the frame so that the plane is parallel to a plane formed by any 2 of the 3 axis e.g. any of the xy, xz, yz planes
• Discard the dimension where all the values are 0.
• Do a 2d convex hull
• Create a face where the indexes are the indexes of the convex hull points

from quickhull3d.

Thanks for the bug report, a similar bug was opened a few years ago in #5 where the input only contains points in a plane, I remember I added this test:

And verified that the output is a convex hull using:

As you can see I'm using EPS of 1e-6.

I understand the motivation of outputing 2 faces if the input only contains coplanar points, as you mention this is not a normal input case. A similar problem happens in a lower dimension, e.g. find a triangle with 3 co-linear points, effectively there's no triangle and we only have a line segment.

If the input only contains coplanar points, we have a few options:

1. Crash the program because the input is not valid. This was the initial implementation but caused runtime errors so I went for option 2.
2. Provide an ordering of points and faces that doesn't break the guarantee that for each face all the other points are behind it (or in the same plane). This is the option that is currently implemented.
3. Create at least 2 opposite faces, keeping the guarantee that guarantee that for each face all the other points are behind it (or in the same plane). I'd argue that this is not a good output either with the triangle example above.

from quickhull3d.

Provide an ordering of points and faces that doesn't break the guarantee that for each face all the other points are behind it (or in the same plane). This is the option that is currently implemented.

Given the example, is this a problem of determining the orientation of the point to the face? It looks like the first point has been assigned to another face.

from quickhull3d.

OK, no need for face to appear twice, that can be done by application using quickhull3d in postprocessing.

The 5 points of the example from description are in order, so complete face would be [0,1,2,3,4].
This script shows what quickhull3d does when adding a point outside the plane (origin here), and removing all faces containging new point (5). The result [ [ 4, 0, 1 ], [ 4, 1, 2 ], [ 4, 2, 3 ] ] is correct, all original five points 0..4 contained:

pi@raspberrypi5:~/quickhull3d $ node bug2.js
[[-8,1,0],[-7,4,0],[-6,5,-2],[-7,0,-4],[-8,0,-1]]
[[3,0,2],[4,3,2],[4,2,0],[4,0,3]]

[[-8,1,0],[-7,4,0],[-6,5,-2],[-7,0,-4],[-8,0,-1],[0,0,0]]
[[3,2,5],[1,0,5],[1,5,2],[4,0,1],[4,1,2],[4,2,3],[4,3,5],[4,5,0]]
[ [ 4, 0, 1 ], [ 4, 1, 2 ], [ 4, 2, 3 ] ]
pi@raspberrypi5:~/quickhull3d $ 
pi@raspberrypi5:~/quickhull3d $ cat bug2.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(JSON.stringify(pts))
console.log(JSON.stringify(faces))
console.log()

const pts2 = [...pts,[0,0,0]]
const faces2 = runner(pts2)
console.log(JSON.stringify(pts2))
console.log(JSON.stringify(faces2))
const faces2b = faces2.reduce((a,p) =>
    (p.some((v)=>(v==pts2.length-1)))?a:a=[...a,p],[])
console.log(faces2b)
pi@raspberrypi5:~/quickhull3d $ 

So either Mauricio option (1) would be ok, reject input and let calling application deal with it (reposnse [] could indicate no faces, or coplanar points).
Or something else.

But not the current response [ [ 3, 0, 2 ], [ 4, 3, 2 ], [ 4, 2, 0 ], [ 4, 0, 3 ] ] because left top point 1 is in no triangle of response, so outside of convex hull contrary to definition of convex hull.

jscad app

Correct response:
[ [ 4, 0, 1 ], [ 4, 1, 2 ], [ 4, 2, 3 ] ]

from quickhull3d.

Sorry, that response is not correct.
isPointInsideHull() is false for point [-6,5,2] for those faces.

Perhaps correct response is [ [ 0, 1, 2, 3, 4] ]?
All 5 points are "inside":

pi@raspberrypi5:~/quickhull3d $ node bug3.js
[[-8,1,0],[-7,4,0],[-6,5,-2],[-7,0,-4],[-8,0,-1]]
[ [ 0, 1, 2, 3, 4 ] ]
[ true, true, true, true, true ]
pi@raspberrypi5:~/quickhull3d $ cat bug3.js 
import qh from 'quickhull3d'

const isPointInsideHull = qh.isPointInsideHull

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

console.log(JSON.stringify(pts))
console.log(faces)
console.log(pts.map((p) => isPointInsideHull(p, pts, faces)))
pi@raspberrypi5:~/quickhull3d $ 

from quickhull3d.

Thanks Mauricio.
I tried to implement similar in JSCAD and tried to proces the generated geom2 with hull(), but that was not easy to get right.

There is only one issue with your approach:
... , if the projection distance is 0 for all the points ...
You need to Math.abs() compare to some tolerance instead.
And that depends on the max/min in the 3 dimensions.
A default tolerance of 1e-10 worked for me, but it is important to be able to raise that for inputs where max/min dimension values are very big numbers.
Below code is part of my lattice_sphere_cmp JSCAD app, it was used but currently is not (because I now use fromPointsConvexPlaneℤ3(pts) which allows to compare distance to 0 because all my application points are guaranteed to be in ℤ³ — I use cross procuct for "distance" computation instead of normalized normal, because cross product is guaranteed to have integer only entries in my scenario, and therefore all dot() results are integers). Below code is used by my fromPointsConvex(pts), which is workaround for geom3.fromPointsConvex() (issue #1347) that is based on quickhull3d:

const isPointOnPlane = (pla, pt, tol=1e-10) =>
  Math.abs(vec3.dot(pt, pla) - pla[3]) < tol

const arePointsOnPlane = (pla, pts, tol=1e-10) =>
  pts.every((p) => isPointOnPlane(pla, p, tol))

from quickhull3d.

This should be fixed in the alpha release 3.1.0-1 https://www.npmjs.com/package/quickhull3d/v/3.1.0-1, let me know how it goes and I'll create a stable release 3.1.0.

from quickhull3d.

Hi,
I really want to test this.
I tried 3 methods and none worked :-(

1. From npm instructions, Cannot use import statement outside a module:

hermann@j4105:~$ npm install --save quickhull3d

up to date, audited 18 packages in 1s

found 0 vulnerabilities
hermann@j4105:~$ node bug.js 
(node:4689) Warning: To load an ES module, set "type": "module" in the package.json or use the .mjs extension.
(Use `node --trace-warnings ...` to show where the warning was created)
/home/hermann/bug.js:1
import qh from 'https://cdn.jsdelivr.net/npm/[email protected]/+esm'
^^^^^^

SyntaxError: Cannot use import statement outside a module
    at wrapSafe (node:internal/modules/cjs/loader:1281:20)
    at Module._compile (node:internal/modules/cjs/loader:1321:27)
    at Module._extensions..js (node:internal/modules/cjs/loader:1416:10)
    at Module.load (node:internal/modules/cjs/loader:1208:32)
    at Module._load (node:internal/modules/cjs/loader:1024:12)
    at Function.executeUserEntryPoint [as runMain] (node:internal/modules/run_main:174:12)
    at node:internal/main/run_main_module:28:49

Node.js v20.13.1
hermann@j4105:~$ cat bug.js 
import qh from 'https://cdn.jsdelivr.net/npm/[email protected]/+esm'

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)
hermann@j4105:~$ 

from quickhull3d.

2. in web developer tools:

import qh from 'https://cdn.jsdelivr.net/npm/[email protected]/+esm'
Uncaught SyntaxError: import declarations may only appear at top level of a module debugger eval code:1:1

from quickhull3d.

I did git pull, created package.json for module as learned from @z3dev
jscad/OpenJSCAD.org#1347 (comment)

Does not take your changes:

hermann@j4105:~/quickhull3d$ cat > 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"
  }
}
hermann@j4105:~/quickhull3d$ npm install

removed 11 packages, changed 1 package, and audited 7 packages in 2s

found 0 vulnerabilities
hermann@j4105:~/quickhull3d$ node bug.js 
[ [ 3, 0, 2 ], [ 4, 3, 2 ], [ 4, 2, 0 ], [ 4, 0, 3 ] ]
hermann@j4105:~/quickhull3d$ 

from quickhull3d.

Please let me know how I can undo whatever I did and test your current repo.
Can you please run bug.js locally on your computer? And show output?

from quickhull3d.

1. This module is now an ESmodule, in node please read https://nodejs.org/api/esm.html#enabling about how to enable it.
2. You can load it in a browser but not through devtools because it needs to be a file imported with <script type="module" src="main.js"></script>, in fact, this is what I'm using in gh-pages https://github.com/mauriciopoppe/quickhull3d/blob/gh-pages/index.html
3. The package is published as alpha so you need to explicitly use the version I sent above e.g. "quickhull3d": "3.1.0-1" and reinstall.

from quickhull3d.

Hi,
thanks for the infos.
But I was not able to get anything to work but in browser.
Be aware that the "Minimal browser demo" output for your example changed
(now: [[2,1,0],[3,1,2],[3,0,1],[3,2,0]]):
https://www.npmjs.com/package/quickhull3d/v/3.1.0-1

This is above bug.js for the browser as bug.html:

<!DOCTYPE html>
<html>
<head><meta charset="UTF-8" /></head>

<body>
 <script type="module">
  import qh from 'https://cdn.jsdelivr.net/npm/[email protected]/+esm'

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

  const faces = qh(pts)

  alert(JSON.stringify(faces))
 </script>
</body>

</html>

And it correctly alerts now this:

[[2,1,0],[2,0,4],[2,4,3]]

Corresponding to this ASCII art diagram, similar to JSCAD screenshot above with bug output, but this time correct:

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

from quickhull3d.

Thanks, I updated the output of the example in the README.

from quickhull3d.

@mauriciopoppe thanks a lot for the fix. And of course, this very nice library.

from quickhull3d.