oskarsigvardsson / unity-quickhull Goto Github PK
View Code? Open in Web Editor NEWAn implementation in Unity of the Quickhull algorithm for generating 3D convex hulls
License: MIT License
An implementation in Unity of the Quickhull algorithm for generating 3D convex hulls
License: MIT License
I have the following point set:
a = (-0.125, 0.125, -0.125)
b = (-0.149, 0.125, -0.125)
c = (-0.125, 0.125, -0.192)
d = (-0.125, 0.0, -0.125)
When finding the initial points for the hull generation, these points are identified as coplanar, so the generation fails.
The problem probably comes from the input point coordinates being smaller than 1, so the cross product becomes smaller and smaller (eventually they become smaller than epsilon).
Maybe this could be fixed by taking the normalized vector after the cross product (or choose a different method to calculate if points are coplanar)?
(I haven't checked if this solution is actually correct, but it seems to be working)
bool AreCoplanar(Vector3 a, Vector3 b, Vector3 c, Vector3 d)
{
var n1 = Cross(c - a, c - b).normalized;
var n2 = Cross(d - a, d - b).normalized;
return AreCollinear(Vector3.zero, n1, n2);
}
Hello! First of all I want to thank you for this code snippet which I have found very useful. I just wanted to report an error I have been running into when attempting to generate a hull for a specific mesh -
GK.ConvexHullCalculator.FindHorizon (System.Collections.Generic.List`1[T] points, UnityEngine.Vector3 point, System.Int32 fi, GK.ConvexHullCalculator+Face face) (at ConvexHullCalculator.cs:666)
I think this may be related to points being too close to one another, so I was messing around with the epsilon setting. But decreasing the epsilon value actually led to many more errors of the same kind, which I was not expecting.
Is it possible to increase the resolution, so that the hull has more faces?
generate convex hull fail. I run the code on a plane mesh.
I understand that generating a convex collider for a box mesh is pointless, but its running runtime on pre-made and dynamic objects unanimously.
The box in question is ProBuilder generated box with a size of [6.05, 0.16, 6.59].
I would export the mesh and put it here, but I have no idea where ProBuilder meshes are stored at :(
Besides this minor issue, no issues found. This lib is amazing! Thanks for sharing it with the community!
EDIT: The missing vertex is not actually missing, it is rather put inside the resulting vertices array as a duplicate of a different vertex. This effectively renders it useless though, so its as good as missing.
input data(X,Y,Z):
-0.06270732 , 0.03174151 , 0.025
-0.06097341 , 0.03174151 , 0.025
-0.06270732 , 0.03174151 , 0
-0.06097341 , 0.03174151 , 0
-0.05804581 , 0.03174151 , 0.025
0.0850401 , 0.03174151 , 0.025
-0.05804581 , 0.03174151 , 0
0.0850401 , 0.03174151 , 0
-0.06874499 , -0.05041299 , 0.025
-0.06874499 , 0.03174151 , 0.025
-0.06874499 , -0.05041299 , 0
-0.06874499 , 0.03174151 , 0
0.0850401 , -0.05041299 , 0.025
0.0850401 , -0.05041299 , 0
-0.06563492 , 0.03174151 , 0
-0.06563492 , 0.03174151 , 0.025
-0.06558505 , 0.03136266 , 0.025
-0.06520618 , 0.03070645 , 0.025
-0.06543881 , 0.03100961 , 0.025
-0.06092353 , 0.03136266 , 0.025
-0.06313606 , 0.03070645 , 0.025
-0.0607773 , 0.03100961 , 0.025
-0.06290343 , 0.03100961 , 0.025
-0.06275719 , 0.03136266 , 0.025
-0.05809569 , 0.03136266 , 0.025
-0.05824192 , 0.03100961 , 0.025
-0.06417112 , 0.03027771 , 0.025
-0.06454998 , 0.03032759 , 0.025
-0.06490302 , 0.03047382 , 0.025
-0.05847454 , 0.03070645 , 0.025
-0.05877771 , 0.03047382 , 0.025
-0.05913075 , 0.03032759 , 0.025
-0.05950961 , 0.03027771 , 0.025
-0.05988847 , 0.03032759 , 0.025
-0.06343922 , 0.03047382 , 0.025
-0.06379226 , 0.03032759 , 0.025
-0.06054467 , 0.03070645 , 0.025
-0.06024151 , 0.03047382 , 0.025
-0.05824192 , 0.03100961 , 0
-0.05809569 , 0.03136266 , 0
-0.06290343 , 0.03100961 , 0
-0.06313606 , 0.03070645 , 0
-0.06343922 , 0.03047382 , 0
-0.06275719 , 0.03136266 , 0
-0.06092353 , 0.03136266 , 0
-0.0607773 , 0.03100961 , 0
-0.06054467 , 0.03070645 , 0
-0.05913075 , 0.03032759 , 0
-0.05877771 , 0.03047382 , 0
-0.05847454 , 0.03070645 , 0
-0.06558505 , 0.03136266 , 0
-0.06543881 , 0.03100961 , 0
-0.06520618 , 0.03070645 , 0
-0.06490302 , 0.03047382 , 0
-0.06454998 , 0.03032759 , 0
-0.06417112 , 0.03027771 , 0
-0.06379226 , 0.03032759 , 0
-0.06024151 , 0.03047382 , 0
-0.05988847 , 0.03032759 , 0
-0.05950961 , 0.03027771 , 0
This is quite the edge case, but there is a quadruple-for loop in FindInitialHullIndices
each vertex that can cause programs to stall. It's a O(n^4) algorithm.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.