I have a bunch of Vector3 points that I need to triangulate. This is for a physics simulation that I am working on.
I have not found any modules that are capable of triangulating 3D points. These points are ment to be the vertices for the resulting triangles.
So far, I have searched through Roblox and GitHub, but every module that I found does not support 3D triangulation.
What exactly are you trying to do? Are you trying to triangulate a point set so that it represents the shape as depicted above, or are you looking for a convex hull?
The points are vertices, so I am trying to triangulate a point set.
This is quite a complex problem to solve, and I would imagine that the solution would vary dependent on your use case. I don’t think Delaunay tetrahedralisation would suit your point set above.
From your picture, I’m guessing that you want them to be treated as surface points, so you could do surface reconstruction. Pretty sure the authors of that paper have the source on github.
There’s also this collection of methods - I’m unsure on licensing though.
Another one that may of some use is the Ball Pivoting algorithm, which should be readily available on github.
If you give me a little more of an idea of your exact use case, and what data you start with beforehand (e.g. in the case above, it looks like you have access to the mesh?) then I may be able to help further
You need face/edge information here, you can’t just give an algorithm a set of points and say “turn this into a mesh”. There are too many ways to connect all the vertices. (edit: I should say, there’s no “easy” way that will always result in the mesh you expect).
…Unless you just want the convex hull, in which case there are several algorithms available online.
Edit: for example: this is like asking “make a polygon from this set of vertices”:
There’s no way to know which of these is the “right” answer:
That is a good point. I will edit the update of this topic.
That is fine, because I only need some valid triangle mesh output that can connect the points (even if there are multiple solutions to this problem).
So basically, I want to run a method that can simulate friction on a surface. This method requires the following properties the surface:
That means that if you were to simulate this friction for a MeshPart, you need to estimate the surfaces of a MeshPart.
To make this possible, I wrote a module that can generate vertex points using raycasts (as seen in the picture of the row boat with its raycast vertices). Now I need to divide these into surfaces.
I see. For your use case, I’m unsure you really require any form of reconstruction method.
Assuming you have the asset outside of roblox:
Then, when you need to query with a raycast:
You will now have the face you hit and can calculate the surface area, centroid and the normal by reading the data from the face.
Another method, also utilising the .obj data, would be to perform Volumetric Hierarchical Approximate Convex Decomposition to partition the mesh into convex sub-surfaces, for which you could perform the simulation on.
There are several .obj readers available on the DevForum that will speed up the start of your project, but you’ll need to write the AABB tree + ray tracer yourself. There’ll be a lot of code on Github you can utilise for that though - same goes for the VHACD.
If you don’t own the asset, you could write an external parser that works with Roblox’s mesh format. Host it on a server or something for on the fly parsing.
This would be a pretty awesome project if you did this part too.
Is this still possible though? The asset?id=n api to get the raw asset doesn’t seem to work anymore when I last checked.
Edit: the api has been updated to https://assetdelivery.roblox.com/v1/asset/?id= so this should still work. Nice idea!
Or, again, make a convex hull 
Sometimes, it’s a lot harder to find “some valid” solution than it is when there’s just the one.
I think I will just go for a convex hull. The only limitation for my use case with the mesh format is that I do not want too many triangles for performance reasons. It is a very cool suggestion nonetheless
Also, just so we’re not putting the cart before the horse: do you know that MeshParts can have accurate collisions now?
Yup, I am aware of that. I just need to do some custom physics simulation, so that is why I need the triangles.
Recommend QuickHull3D (ported to several languages on Git) if you go this route
That is this one GitHub - EgoMoose/Quickhull-lua: Port of maurizzzio's quickhull3D I assume for Lua then?
Didn’t know that Ego had ported it to Lua, that’s useful. That will work, yes!
A convex hull seems to work fine for my problem. This is the outcome (surface normals of the resulting triangles):
I guess that the QuickHull3D answer should be the solution, since that is the end of story. It feels quite uncomfortable to award a solution to 1 answer when 2 are correct (both of you recommended using a convex hull).
