# Geometry Algorithms

Discussion in 'Assets and Asset Store' started by Jobberwocky, Jun 8, 2016.

1. ### Jobberwocky

Joined:
May 6, 2016
Posts:
54

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!

Last edited: Sep 26, 2018
2. ### Jobberwocky

Joined:
May 6, 2016
Posts:
54
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!

3. ### Jobberwocky

Joined:
May 6, 2016
Posts:
54
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!

4. ### phoberman

Joined:
Jan 16, 2008
Posts:
74
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

5. ### Jobberwocky

Joined:
May 6, 2016
Posts:
54
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?

6. ### Charles-Van-Norman

Joined:
Aug 10, 2010
Posts:
86
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.

7. ### Jobberwocky

Joined:
May 6, 2016
Posts:
54
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.

8. ### Charles-Van-Norman

Joined:
Aug 10, 2010
Posts:
86
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.)

9. ### Jobberwocky

Joined:
May 6, 2016
Posts:
54
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.

10. ### pixelsteam

Joined:
May 1, 2009
Posts:
924
Could this be used for creating a cave system?

11. ### Jobberwocky

Joined:
May 6, 2016
Posts:
54
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/

12. ### jGate99

Joined:
Oct 22, 2013
Posts:
953
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

13. ### Jobberwocky

Joined:
May 6, 2016
Posts:
54
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.

jGate99 likes this.
14. ### pssaravanan

Joined:
Nov 25, 2017
Posts:
13
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

15. ### Jobberwocky

Joined:
May 6, 2016
Posts:
54
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.

Joined:
Nov 25, 2017
Posts:
13

17. ### Jobberwocky

Joined:
May 6, 2016
Posts:
54
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.

18. ### Jobberwocky

Joined:
May 6, 2016
Posts:
54
Updated the opening post with new information and with several links to demo scenes.

19. ### Jobberwocky

Joined:
May 6, 2016
Posts:
54
Geometry Algorithms 2.0 update is now live at the Unity asset store

20. ### Hitjones

Joined:
Jul 17, 2014
Posts:
8
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)

21. ### Jobberwocky

Joined:
May 6, 2016
Posts:
54

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.

22. ### ifnoLee

Joined:
Feb 27, 2017
Posts:
5
Hi, How is 3D triangulation from a set of arbitrary points now？

23. ### Jobberwocky

Joined:
May 6, 2016
Posts:
54
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.

Joined:
Jul 10, 2017
Posts:
8
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

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.

25. ### Jobberwocky

Joined:
May 6, 2016
Posts:
54
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://stackoverflow.com/questions/49784416/unable-to-execute-command-killed-9-in-xcode-9-3

26. ### AlexiJohansen123

Joined:
Apr 5, 2016
Posts:
17
@Nevade Have you managed to solve your compiling issues on IOS? I have run into the same problem and am Looking for a solution.

27. ### nsfnotthrowingaway

Joined:
Feb 18, 2016
Posts:
45
@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?

Last edited: Dec 12, 2018
28. ### jGate99

Joined:
Oct 22, 2013
Posts:
953

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

29. ### Jobberwocky

Joined:
May 6, 2016
Posts:
54
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.

nsfnotthrowingaway likes this.
30. ### Jobberwocky

Joined:
May 6, 2016
Posts:
54
I'm not sure what you exactly mean, but it seems that this feature is not in the scope of this asset.

31. ### jGate99

Joined:
Oct 22, 2013
Posts:
953
Something like that?

32. ### Jobberwocky

Joined:
May 6, 2016
Posts:
54
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)

33. ### CrackerHackerMasterChecker

Joined:
Nov 1, 2018
Posts:
4
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

34. ### Jobberwocky

Joined:
May 6, 2016
Posts:
54
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

35. ### SpeedySpike

Joined:
Jun 27, 2016
Posts:
5
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.

36. ### Jobberwocky

Joined:
May 6, 2016
Posts:
54
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.

37. ### forouzan

Joined:
Sep 2, 2017
Posts:
4
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?

38. ### Jobberwocky

Joined:
May 6, 2016
Posts:
54
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.

39. ### forouzan

Joined:
Sep 2, 2017
Posts:
4
Thank you. So if I can translate the bitmap image to a set of points, after that can I use this asset?

40. ### Jobberwocky

Joined:
May 6, 2016
Posts:
54
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.

41. ### forouzan

Joined:
Sep 2, 2017
Posts:
4
Thanks and do you know how can I translate the bitmap image to a set of points?

42. ### Jobberwocky

Joined:
May 6, 2016
Posts:
54
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.

Joined:
Sep 2, 2017
Posts:
4
Thank you.

44. ### God-at-play

Joined:
Nov 3, 2006
Posts:
319
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.

45. ### Jobberwocky

Joined:
May 6, 2016
Posts:
54
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

46. ### AymericV521

Joined:
Oct 21, 2016
Posts:
1
Jobberwocky likes this.

Joined:
May 6, 2016
Posts:
54
unityunity