Comments (16)
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:
quickhull3d/test/index.test.js
Lines 271 to 275 in 2012ad0
And verified that the output is a convex hull using:
quickhull3d/test/index.test.js
Lines 22 to 47 in 2012ad0
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:
- Crash the program because the input is not valid. This was the initial implementation but caused runtime errors so I went for option 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.
- 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.
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 :-(
- 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.
- 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.
- This module is now an ESmodule, in node please read https://nodejs.org/api/esm.html#enabling about how to enable it.
- 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 - 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.
Related Issues (15)
- images HOT 2
- hangs with simple 7 point hull HOT 2
- AssertionError: attempting to join destroyed faces HOT 2
- Gives different set of faces to Matlab convhulln HOT 4
- Crashes on these points HOT 1
- Likely a typo HOT 1
- bug in doAdjacentMerge HOT 1
- No @type definition for TypeScript HOT 1
- sir,How to tell if a point is inside the convex hull HOT 1
- Use input STL or OBJ mesh file as input HOT 2
- maintain UV textureCoordinates HOT 3
- Update README.md HOT 2
- Incorrect results for objects with duplicate vertices HOT 3
- sometimes not working. HOT 3
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from quickhull3d.