Geometry Algorithms

AssetStore: https://www.assetstore.unity3d.com/en/#!/content/61875
Mail: jobberwockysoftware@gmail.com
Facebook: https://facebook.com/JobberwockySoftware
Twitter: @JobberwockySoft

Demo scenes:

• Demo 1 - Contains several 2D triangulation and hull examples;
• Demo 2 - Contains several 3D triangulation and hull examples;
• Demo 3 - Is an interactive Voronoi example.

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.

I hope this information can help you further!

 

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.)

Thanks for your speedy response.

 

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.

 

Could this be used for creating a cave system?
Web demo would help you sell more

 

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!

https://bonrust.bitbucket.io/GeometryAlgorithms/Geometry2D/

https://bonrust.bitbucket.io/GeometryAlgorithms/Voronoi/

 

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.

Does this information help you?

 

Hi,

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.

Thank you

 

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.

Does this information help you?

 

Yes, Thanks for your reply.

 

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.

 

Updated the opening post with new information and with several links to demo scenes.

 

Geometry Algorithms 2.0 update is now live at the Unity asset store

 

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)

 

Well we already had some private chat going on about the performance of Geometry Algorithm.

So you can ignore this one ;-) Anyway, I will just write something for the other people that are looking at this thread and are interested about the performance. First of all, the performance depends on the number of points and the complexity of the shape. All examples provided by this asset can be generated in real-time. For example, I profiled two examples:

1) Tank example (299 points): Hull generation took 41.77ms and the triangulation took 1.53ms.

2) Dude example (228 points): Hull generation took 53.7ms, and the triangulation took 2.15ms.

Further, all the algorithms available in Geometry Algorithms can be run async from the main thread. Therefore, if you have very large calculations you can always offload it to another thread without freezing the main thread.

 

Hi, How is 3D triangulation from a set of arbitrary points now？

 

The 3D triangulation algorithm in this asset can only triangulate convex shapes properly. So, it cannot handle holes or boundaries. The result of the algorithm is either a set of tetrahydrons or if you change the input settings, it can return a set of triangles that represent the hull of the set of generated tetrahydrons.

 

Hello.
I'm try to build Geometry plugin for IOS but it give a me a strange error in XCode (Both 9 and 10Beta).
Tried to put it in a new project and build only a demo scene: it stuck and the end of building (circa 160/166 taks) then give me this error:

clang: error: unable to execute command: Killed: 9

clang: error: clang frontend command failed due to signal (use -v to see invocation)

Apple LLVM version 10.0.0 (clang-1000.10.25.5)

Target: aarch64-apple-darwin17.6.0

Thread model: posix

InstalledDir: /Applications/Xcode-beta.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin

clang: note: diagnostic msg: PLEASE submit a bug report to http://developer.apple.com/bugreporter/ and include the crash backtrace, preprocessed source, and associated run script.

Is something know? I must follow some rules to build IOS? As i say i just tried to create a New Project with GeometryAlgorithms and nothing else in Unity2018f1.2.f1 and just build it. No problem with Unity generating XCode code but got this strange error while building inside XCode.

 

Hi,

Sorry to hear that Geometry Algorithms is not fully working for you. This is the first time I have heard about this issue, so it is not known to me. Also, I have never tested it with building for ios or building within xCode.

So, at the moment, I don't have a solution to this problem. :/

I am not sure if you already found these links, but maybe they can help:

https://answers.unity.com/questions/1275810/xcode-error-unable-to-execute-command-segmentation.html
https://stackoverflow.com/questions/49784416/unable-to-execute-command-killed-9-in-xcode-9-3

 

@Nevade Have you managed to solve your compiling issues on IOS? I have run into the same problem and am Looking for a solution.

 

@Jobberwocky - I have a few questions.

1. Can you do constrained Delaunay where I can specify edges that must be included? For instance, if we pretend that the blue lines in this image weren't part of the Delaunay triangulation, but forced to be included? Constraint edges and/or Steiner points.
   
   
   
   
2. So, just to make sure about the basic operation of this. I can specify the outline, and automatically get the triangulated polygons for the inside?
3. Can I specify a minimum angle for the triangulations?
4. What platforms does this work on? Does it work on Windows, Mac, and Linux? How about consoles?

Thanks for your time

 

I took another look at your asset after last message notification.

Can you add a feature where it takes the image, cut into those pieces which you draw and provide us cooridates to put those pieces in Sprites

 

1. No, at the moment this is not possible. You can only specify the boundaries when you want to perform a constrained Delaunay

2.Yes

3 No

4 From feedback that I received, I only know it is not working for iOS. I never tested it on any consoles.

 

I'm not sure what you exactly mean, but it seems that this feature is not in the scope of this asset.

 

Something like that?

 

No that is not possible. However, the triangulation could be configured in such a way that it would return the triangle data instead of a Unity mesh. Then, you can use that that for further processing (e.g. coloring)

 

Hello, I am really interested in your tool. It looks really great.
I have 2 questions:
Question 1:
I have Points of a 2D-Contour I can pass to a Unity-Line Renderer Component.
The Problem is: I want to fill the contour with color. Unity Line Renderer can't fill a contour. Can I use your tool to fill the contour? I only have contour points, no points inside of the contour (like you have in your demos).
Question 2:
I have 2D contour (see question below). At the moment, I am renderering them with a Unity line renderer.
It is just 2D. But can I extrude the my 2D form in height, so I get a 3D Objekt? For example: I have a circle, but I want to extrude it in Y-Axis, so I get a coin.
Question 3: Is there a trial version I can test for few days?

best regards

 

Thanks!

1) Yes that is possible! You can generate (triangulate) a mesh from the contour points and color the mesh after.

2) This is not yet possible, but the plan is to add it with the next update as this feature is being requested more often.

3) There is no trial version

 

Can this asset also calculate a 3d Delaunay triangulation for an arbitrary point set? I assume so given that you are able to create the 3d Voronoi, but I wanted to confirm.

 

Yes, it is possible to create 3D Delaunay triangulations. Do note that the 3D algorithm is less advanced than the 2D algorithm, because it cannot create concave shapes or take into account holes.

 

Hello

I want to use your Geometry Algorithms asset to triangulate 2D mesh for bitmap images.
In other words, I want to implement a prototype in unity that input is a bitmap image, and after that triangulate image, like attached image.
Could you help me what should I do?

 

This asset cannot directly triangulate bitmap images. The triangulation algorithms requires a set of points as input. So, to be able to use this algorithm, you have to somehow translate the bitmap image to a set of points and then afterwards draw the lines on the image.

I guess the tricky part in this process is to retrieve the points from the bitmap image.

 

Thank you. So if I can translate the bitmap image to a set of points, after that can I use this asset?

 

Yes, the whole triangulation part can be done by this asset. Afterwards based on the result of the triangulation, you have to draw the lines on the bitmap yourself.

 

Thanks and do you know how can I translate the bitmap image to a set of points?

 

I'm not really familiar with bitmaps images and using them in Unity, but I was thinking that perhaps if the boundary of an image has a unique color (e.g. black), you could generate points for each (in this case) black pixel. The location of these points would corresponds with the location of the black pixel counterpart.

 

Thank you.

 

Is there a way to get a result similar to concave 3D Delaunay using Voronoi3D? For example, I have a point cloud that is fit to a surface, and the surface is concave. I was hoping I could constrain it somehow and use voronoi to give me a mesh. But Voronoi3D as-is is definitely not working like I hoped it would.

 

Hi,

All the 3D methods in this asset do only work for convex shapes and not concave ones. So, both the 3d delaunay and 3d voronoi methods wont give the desired results.

If you are working with 2.5d shapes (like surfaces) then you can use the 2d methods which can handle concave shapes

 

FYI - I've managed to compile on iOS by removing the Example folder (I think the problem was the huge shapes datas, as in the link given by Jobberwocky => https://stackoverflow.com/questions/49784416/unable-to-execute-command-killed-9-in-xcode-9-3 )

 

Oh that is great to hear that you found the problem! Thank you! I will try to fix the size issue in the next update.

 

Hi,

I'm trying to generate walls from floor points using a concave hull and I'm unable to obtain good results with your plugin. I've tried all the methods you provided in the examples but always end up with messed up geo.

Also my Editor always ends up not responding when I put a certain value of concavity, let's say 10 for example.

With a concavity value of 15 I obtain this:


instead of this, with another algorithm:


Let's say you have an array of unsorted Vector3s that all have the same Y value, what code would you write to get a nice concave hull and draw lines with it?

This is all for an editor tool, so async isn't supported.

Thanks in advance.

 

Hi,

Thanks for reaching out! Could you try to swap the Y and Z value of your input points (if you didn't try that already). In the algorithm itself the Z value is used as the height value and the X and Y values to calculate the hull.

If this doesn't solve your problem, is it possible to provide me with the list of points that you are using? Then I will have a closer look at it later today when I'm back home.

Finally, if you don't mind, which algorithm did you use for the other (good) result?

Anyway let me know how it goes!

 

Hi,

Thanks for the quick answer.

I did what you suggested + I've sorted the points in radial order (which is not changing anything).

Here's what I have with a concavity of 17:


and with a concavity of 30:


Here's a Json of all the points as they are in 3D (y == 0):

Spoiler: json

[{"x":64.5,"z":-63.75,"normalized":{"x":0.711229742,"z":-0.702959657,"magnitude":1.0,"sqrMagnitude":1.0},"magnitude":90.6879959,"sqrMagnitude":8224.3125},{"x":64.5,"z":-47.7499962,"normalized":{"x":0.803722739,"z":-0.595003963,"magnitude":1.0,"sqrMagnitude":0.99999994},"magnitude":80.25156,"sqrMagnitude":6440.312},{"x":76.5,"z":-63.75,"normalized":{"x":0.7682213,"z":-0.6401844,"magnitude":1.0,"sqrMagnitude":1.00000012},"magnitude":99.58068,"sqrMagnitude":9916.3125},{"x":76.5,"z":-47.75,"normalized":{"x":0.848309636,"z":-0.5295005,"magnitude":1.0,"sqrMagnitude":1.0},"magnitude":90.17934,"sqrMagnitude":8132.3125},{"x":80.5,"z":-47.75,"normalized":{"x":0.8600745,"z":-0.510168433,"magnitude":1.0,"sqrMagnitude":1.0},"magnitude":93.59654,"sqrMagnitude":8760.3125},{"x":80.5,"z":-38.75,"normalized":{"x":0.9010422,"z":-0.4337315,"magnitude":1.0,"sqrMagnitude":1.00000012},"magnitude":89.34099,"sqrMagnitude":7981.8125},{"x":92.5,"z":-38.75,"normalized":{"x":0.9223377,"z":-0.386384726,"magnitude":1.0,"sqrMagnitude":1.0},"magnitude":100.288643,"sqrMagnitude":10057.8125},{"x":92.5,"z":-21.25,"normalized":{"x":0.974612653,"z":-0.2238975,"normalized":{"x":0.9746127,"z":-0.223897517,"magnitude":1.0,"sqrMagnitude":1.0},"magnitude":0.99999994,"sqrMagnitude":0.99999994},"magnitude":94.9095,"sqrMagnitude":9007.8125},{"x":80.5,"z":-21.25,"normalized":{"x":0.9668798,"z":-0.255232245,"magnitude":1.0,"sqrMagnitude":1.0},"magnitude":83.25751,"sqrMagnitude":6931.8125},{"x":80.5,"z":-12.25,"normalized":{"x":0.9886189,"z":-0.150442,"normalized":{"x":0.9886188,"z":-0.150441989,"normalized":{"x":0.988618851,"z":-0.150442,"magnitude":1.0,"sqrMagnitude":1.0},"magnitude":0.99999994,"sqrMagnitude":0.9999999},"magnitude":1.00000012,"sqrMagnitude":1.00000012},"magnitude":81.42673,"sqrMagnitude":6630.3125},{"x":64.5,"z":-18.7499962,"normalized":{"x":0.9602497,"z":-0.2791423,"magnitude":1.0,"sqrMagnitude":0.99999994},"magnitude":67.17003,"sqrMagnitude":4511.8125},{"x":64.5,"z":-12.25,"normalized":{"x":0.982438445,"z":-0.18658714,"magnitude":1.0,"sqrMagnitude":1.0},"magnitude":65.65297,"sqrMagnitude":4310.3125},{"x":58.25,"z":5.75,"normalized":{"x":0.9951632,"z":0.0982349962,"normalized":{"x":0.995163262,"z":0.098235,"magnitude":1.0,"sqrMagnitude":1.0},"magnitude":0.99999994,"sqrMagnitude":0.99999994},"magnitude":58.53311,"sqrMagnitude":3426.125},{"x":58.25,"z":-18.75,"normalized":{"x":0.951900959,"z":-0.3064059,"magnitude":1.0,"sqrMagnitude":1.0},"magnitude":61.19334,"sqrMagnitude":3744.625},{"x":29.75,"z":5.75,"normalized":{"x":0.981829464,"z":0.189765364,"magnitude":1.0,"sqrMagnitude":1.0},"magnitude":30.3005772,"sqrMagnitude":918.125},{"x":48.5,"z":-18.75,"normalized":{"x":0.932724655,"z":-0.360589445,"magnitude":1.0,"sqrMagnitude":1.0},"magnitude":51.9981956,"sqrMagnitude":2703.8125},{"x":29.75,"z":-18.75,"normalized":{"x":0.8459953,"z":-0.5331903,"magnitude":1.0,"sqrMagnitude":0.99999994},"magnitude":35.16568,"sqrMagnitude":1236.625},{"x":26.5,"z":-18.75,"normalized":{"x":0.8163271,"z":-0.5775899,"magnitude":1.0,"sqrMagnitude":1.0},"magnitude":32.46248,"sqrMagnitude":1053.8125},{"x":48.5,"z":-26.75,"normalized":{"x":0.8756435,"z":-0.482958019,"magnitude":1.0,"sqrMagnitude":1.0},"magnitude":55.3878365,"sqrMagnitude":3067.8125},{"x":35.5,"z":-26.7499962,"normalized":{"x":0.7986482,"z":-0.6017982,"magnitude":1.0,"sqrMagnitude":0.99999994},"magnitude":44.45011,"sqrMagnitude":1975.81226},{"x":26.5,"z":-26.75,"normalized":{"x":0.7037793,"z":-0.7104187,"magnitude":1.0,"sqrMagnitude":1.0},"magnitude":37.65385,"sqrMagnitude":1417.8125},{"x":35.5,"z":-37.7499962,"normalized":{"x":0.68506366,"z":-0.72848314,"normalized":{"x":0.6850637,"z":-0.7284832,"magnitude":1.0,"sqrMagnitude":1.00000012},"magnitude":0.99999994,"sqrMagnitude":0.9999999},"magnitude":51.82,"sqrMagnitude":2685.31226},{"x":48.5,"z":-37.7499962,"normalized":{"x":0.7891332,"z":-0.614222169,"magnitude":1.0,"sqrMagnitude":1.00000012},"magnitude":61.4598427,"sqrMagnitude":3777.31226},{"x":48.5,"z":-47.7499962,"normalized":{"x":0.7125951,"z":-0.7015756,"magnitude":1.0,"sqrMagnitude":1.00000012},"magnitude":68.06109,"sqrMagnitude":4632.312}]

Use

List<Vector3> _list = Newtonsoft.Json.JsonConvert.DeserializeObject(text);

to deserialize.

I've found the "working" algo here https://github.com/Liagson/ConcaveHullGenerator/tree/master/Assets.