Geometry Algorithms is a collection of algorithms that can help you to generate complex geometry from a set of unknown points.

What are the main features?

Hull generation - Allows you to find the boundary of an unknown point set. Concave hulls are supported when you are in working in the 2D and 2.5D space. In 3D, only convex hulls can be generated.

Triangulation - Creates a mesh from a set of points that can be directly used for visualization. Both Delaunay and constrained triangulations are available for the 2D and 2.5D point sets. Complex meshes can be calculated by providing boundaries and holes. Together with the hull generation algorithm a boundary can be generated and be used as input for you triangulation. The 3D triangulation is not constrained, so it is not possible to define holes or boundaries.

Voronoi generation - Calculates the Voronoi diagram of any point set in 2D or 3D.

Threading - All algorithms can be called asynchronous, because threading is supported and handled by this asset. No extra effort is required by the user.

Real-time - All methods are implemented in a way that they can be used in real-time even when large point sets are provided as input. By utilizing the threading support even larger point sets could be used for real-time calculations.

Is it easy to use?

By just writing two lines of code you should be able to use any algorithm in this asset. However if you encounter any problems, Geometry Algorithms is shipped with several examples scenes and a detailed documentation. In addition, you can always get in touch with me by using the contact information at the top of this page or by just leaving a comment here. Do not hesitate to contact me if you have any questions, or suggestions!

A new version is released for this asset! It is now possible to use threading for the 2D hull generation algorithm. Soon, the threading option will be made available for the other algorithms as well!

This week a new update for the Triangulation for Unity has been released! Now you can use threading for creating triangulations.If you have any questions about this new feature, feel free to contact me!

Is there a web demo of this package? It looks good, but its capabilities are not entirely clear from the description & images, and it’s a bit too expensive to try out without more information

At the moment, there is no web demo available for this package. This is scheduled for when I release version 2.0. However, I do not have a date for that release yet. Currently, the main focus of this package is on the triangulation and hull generation of 2d and 2.5d shapes. The triangulation algorithm supports holes and you can define the boundary of the shape. If you do not know the boundary, you can use the hull algorithm to calculate the (concave) boundary. Anyway, for what purposes do you want to use it?

Will this turn unordered point cloud into a triangulated mesh or a collection of individual triangles? I want to reconstruct a 3D environment from a point cloud.

Currently, the triangulation methods return a triangulated unity mesh, so from that mesh you could retrieve the individual triangles if necessary.

Depending on the point cloud, you could use either the 2D or 3D triangulation. The 3D triangulations only properly triangulates convex shapes, so no concave shapes. The 2D triangulation could be used if you only want to triangulate in the x and y direction and maintain the z (height), like a terrain.

Looks like this won’t work for my purposes (I get a point cloud from AR kit and I want to reconstruct the interior space as a mesh or set of meshes.) But rooms are inherently concave! So it won’t work out of the box (I’d need to parse only convex shapes from the point cloud data, not an easy task.)

You are correct, so sadly this won’t work for you when you are going to triangulate concave shapes in 3D. Concave shapes are only supported when triangulating in 2D or 2.5D.

Ehm well I guess that depends on what you exactly want to do… If you want to triangulate a 3D space from a point set then this won’t work for you since the 3D triangulation algorithm can only handle convex shapes and a cave is not convex as far as I know

Currently, I’m preparing some demos for the next release and two are already ready for public!

Hi there,
Im not really good at math, but i know this plugin is doing some serious stuff, can you please explain what kind of games we can do or problems can we solve (game related) with it for a lay man?
Thanks

Hi! This asset allows you to generate geometry (unity mesh) that can be used in your game. This can be usefull when you have for example an (un)known point set (like the height points of a terrain) which you want to visualize as a polygon. Algorithms in this asset can create the geometry for such polygon and also you can apply various constraints (e.g. a boundary or holes) if necessary. See also the two demo’s in my previous post.

Can we use this asset for mesh cutting in real-time (incision). Is it possible to generate hole in a geometry (plane, cube, or mesh from fbx file) in real-time.

Hi! This asset does not contain a method for method cutting itself, but if you have change the vertices of a mesh yourself then you can provide vertices to the triangulation algorithm which will calculate the new mesh. The algorithms for both 2D and 3D meshes are efficient, so for normal use cases this can be done in real-time. Please note that concave shapes are only supported with the 2D/2.5D triangulation, while 3D triangulation only creates convex shapes.

Holes are supported with the 2D/2.5D triangulation algorithm. In that case, you will provide the vertices of the fbx file with separatly the holes that you have defined somehow.

Submitted the 2.0 update of Geometry algorithms for review at the Unity asset store. Hopefully, it will be available soon! Later this week I will update this page with new information, screenshots, and links to some demos.

Hi. What about performance? Is it possible to use almost in Update?

I need to generate concave hull for Jelly-physic character (soft body). I want to generate a field of points for character and generate concave hull for this in update (in a few word, it will be more complex)