I decided to dive into an area where I have absolutely no experience. Meshes.
For start of my journey I have chosen to create myself a 3D Convex Hull.
Having a set of random points, I am able to create the initial tetrahedron from the first four points in the list. Now, I can evaluate the points and exclude the ones that are already inside the initial mesh. Question is when iterating over the ones that outside. How do I choose to which two/three points from the mesh it has to connect? I assume I have to look for the closest point. But how to look for the second and third closest?
What is the best approach?
creating expaning sphere?
creating lines and measuring distances?
iterating over all points and trying to create mesh checking the result if it is closed?
I don’t yet know what properties I can extract from the mesh, or face, or vertex.
Are the mesh faces (1,2,3), (3,2,1), (1,3,2), (2,1,3), (2,3,1) and (3,1,2) the same mesh?
You could transform your points into a point cloud and recursively check for closest points. At each level/iteration a found closest point gets stored somewhere and removed from the point cloud. This runs until your desired number of closest points has been found.
Using the rTree algorithm could be more efficient, especially if your dealing with a huge amount of points, but you’d need a search radius, which you don’t have.
The vertices are organised in flat list. The order is up to you. The face vertices are tuples of vertex indices. Each index refers to a vertex inside the vertices list. The list of vertices and the list of face vertices represent the mesh.
The face vertices of a mesh face are commonly organised in a counterclockwise way. The faces (1,2,3) and (3,2,1) refer to the same vertices, but have an opposed direction.
Furthermore, you should use quad meshes, since they are easier to understand from a human perspective. They have 4 vertex indices per face!
As far as I’m concerned convex-hull algorithms are not easy to implement. So you either have to read up on some algorithms that are out there or you can try something very grasshoppery:
Maybe try to solve the problem using kangaroo for grasshopper, it’s a physics-engine:
Create a Sphere around your point-cloud and let it shirk until it fit’s your geometry well, the connections between your spheres vertices act like springs, it would result in a convex shape. Do it like Christev in the video but don’t specify any anchors.
Flexhopper is another engine that might works well.
They’re extremely fast and deal well with these neighborhood type problems. You’ll need to test some of the functions out but I think there’s some will output a list of points by proximity. RTree.Point3dKNeighbors seems about right. If you want to just dip your toe, LunchBox tools has a few simple RTree tools in Grasshopper that I’ve started using quite regularly.
As for the clockwise/counter clockwise vertex naming, it’s used to tell if the normal is pointing inward or outward.
I don’t know if you’re working in C# but @LongNguyen 's Grasshopper development class is really awesome and I can’t recommend it enough. https://icd.uni-stuttgart.de/?p=22773 The final exercise is a mesh problem and he does a good job of explaining the basics and also integrates RTree.
As far as algorithms go, I’d start from the outside of the point cloud, that approach would be faster I think, not sure though.
Get the outermost point by measuring the distance of all points to the average of the cloud.
place a plane with it’s origin at that outermost point and look for points closest to that plane, if you found the closest point, save that in a variable, closest_pt
iterate by creating another plane at closest_pt find closest point other than the ones you already checked
You could also create a cone at the outermost point and make it smaller at certain increments, until you intersect another point and repeat that.
You cannot do this. There’s no point cloud, first of all. Second, you can get a point from a randomized list.
No plane should be involved as well. You only work with points and their coordinates, until you get the starting tetrahedron. From there you begin looking for closest points that are not inside this starting mesh. And here come the algorithms.
Your approach is wrong, you assume you have everything available at start.
My approach isn’t wrong, it’s just different and more simple, because I don’t calculate for inclusion. If you have a library that does it for you, good!
I assume to only have points in R3, that is simply a point-cloud
“You only work with points and their coordinates”, that’s exactly what I did.
I can easily generate planes from normal-vectors very fast. In fact, planes are at the core of vector-math. The cartesian-coordinate-system is based on three of them!
If you don’t want alternative ideas fine, I assume you want to stick to the nearest-neighbor-inclusion-method. It will work fine.
On another note, You can extract the vertices, triangles, UVs, tangents and nomals of a mesh, but you don’t need those for a convex-hull, you only need the vertices, which is, again, a point-cloud.
Two of the best known algorithms for tackling this are Jarvis march aka gift wrapping, and Quickhull.
The first is similar to what @lesan describes, starting from a plane on an outside point (found by sorting the points in 1d), then wrapping around with successive planes.
Quickhull first builds a tetrahedron (after also sorting in 1d to get the extremes) and works outwards, which sounds more like what @ivelin.peychev is thinking of.
Both are valid approaches, and maybe it’s not such a good idea to be so dismissive of people who take the time to answer your questions.
Yes, I read about the algorithms a little. I realized that gift wrapping has really bad performance, iterating through all points in each step.
I assumed the logical approach will be to create a closed mesh at start to remove the points that are inside, thus reducing the number of iterations. Later I saw that Quickhull is also proposing this.
The issue I have is what happens next.
say I found the nearest point to one of the vertices of the tetrahedron. How do I define which this nearest point should be added to the mesh, how do I pick the indices? Should that happen again trial/error until I get a closed volume again?
Perhaps it is faster to pick a random point instead of the nearest one, then I can enclose points that I’ll later exclude. You know pseudo-genetic approach.
What does that mean?
I don’t dismiss people I dismiss proposals. @lesan’s R-tree proposal was very good suggestion. I didn’t even know what that is before he suggested it, but talking about point cloud and cone, when you don’t know anything about how points are spread, makes no sense.
it’s not a physics engine.