Geometry Algorithms

Thanks for the input. I will check the points this evening.

A lower concavity value (the value itself represents the maximum distance allowed) means that it tries to create a hull from points that are closer together. However that can go wrong in this case when there are not that many points available that also very different distances between each other.

Would it be possible to increase the number of points that you are using, so that the boundaries of the floor plan are more densely populated? That would definitely improve the results.

 

I can try that, but I'll need an algo that will only keep corner points.

 

with 15 concavity:


by what factor do you mean "more densely populated"?

 

It depends on the concavity value you are using and of course the actual shape that you want to have (as in how much details). The lower the concavity, the more points you would need to add.

I also would suggest to distribute the extra points uniformly over the boundaries. For example if you would have to add one point between two corner points then add it in the middle. Not sure if that is possible to do in your case because I don't know how you obtained the points that you give as input.

Non-corner could be removed by using a line simplification algorithm (https://en.wikipedia.org/wiki/Ramer–Douglas–Peucker_algorithm) or by keeping track what the corner points are and remove the other points in the hull afterwards.

 

Yesterday, I released an update that fixes the iOS building error when creating a build in Xcode. It's no longer necessary to remove the "Example" folder from the asset before building the asset.

 

I have a question about whether Bowyer Watson method can be used for triangulation of any polygon？
What's the difference between Bowyer Watson and the constrained deluanay method you introduced?
Thank you so much！

 

The Delaunay triangulation is based on the Dwyer algorithm. I don't think there is much difference compared to the Bowyer Watson triangulation algorithm. Both generate valid Delaunay triangulations and I believe performance is more or less the same for most use cases. The only difference is the way the algorithms create the Delaunay triangulation. So, overall it does not really matter which algorithm you pick to create a triangulation.

 

ok,Thank U!
And For example how do you add delaunay constraints on the picture below?Because I don't want to get a triangle
for 457 and 647!

 

To create a constrained Delaunay triangulation, you have to provide the boundary of your shape. So, in your example you would define the boundary as 0,1,2,7,5,4,6,3. Then, the algorithm will create the shape that you drew.

 

Another small update is made available today. It improves the results of the 3D triangulation; normals are now correctly calculated.

 

Hello I bought your asset and I have some question about the Voronoi3D feature. You said in the manual of the asset that examples of the Voronoi2D and Voronoi3D can be found in ExampleGeometry2D and ExampleGeometry3D but there is no reference to the Voronoi part in these scripts.

For the Voronoi2D there is another script ExampleInteractiveVoronoi2D but there isn't one for the Voronoi3D. When I try to create a Voronoi3D using the vertices of a cube, this is the mesh it return

How can I create a 3D Voronoi Diagram using this asset ?

PS: I only need the Voronoi Nodes of the diagram for my algorithm

 

Thanks for reaching out! Apparently, I accidentally removed the Voronoi diagram examples a while back. My apologies! The Voronoi diagram examples will be re-added with the next update.

Regarding your example, could you share with me what you have exactly done and what your input points are (a PM or email is also fine if you prefer that)? Then I can have a closer look at it!

 

This is the code I used to test the Voronoi3D part. testMesh is the mesh from which I want the voronoi diagram and voronoizedMesh is the mesh that will use the mesh VoronoiAPI.Voronoi3D will return.

For testMesh I used a cube primitive and a more complex mesh but they both return the same results, except the complex mesh have more of these black lines (because it has more vertices than the cube). For voronoizedMesh I just used another cube primitive to show the result of Voronoi3D (I assumed the primitive chosen will not affect the result displayed)

Code (CSharp):

1. using System.Collections;
2. using System.Collections.Generic;
3. using UnityEngine;
4. using Jobberwocky.GeometryAlgorithms.Source.API;
5. using Jobberwocky.GeometryAlgorithms.Source.Parameters;
6.  
7. public class VoronoiDiagram : MonoBehaviour
8. {
9.  
10.     public MeshFilter testMesh;
11.     public GameObject voronoizedMesh;
12.     private VoronoiAPI api;
13.  
14.     public VoronoiDiagram()
15.     {
16.         api = new VoronoiAPI();
17.     }
18.  
19.     [ContextMenu("TestVoronoi")]
20.     public void TestVoronoi()
21.     {
22.         Voronoi3DParameters tmp = new Voronoi3DParameters();
23.         tmp.Points = testMesh.mesh.vertices;
24.         voronoizedMesh.GetComponent<MeshFilter>().mesh = api.Voronoi3D(tmp);
25.     }
26. }

 

Thanks for the info! I will have a look at it this evening.

FYI, those large outwards black lines are Voronoi lines that I automatically calculate (see simple 2d example below, the blue encircles lines are the lines I'm talking about). Also, I already got an update in the queue that will limit the length of these lines based on the hull of the input mesh.

 

To follow up on this, I just pushed a new version to the Unity assetstore for review containing several improvements to the 3D voronoi diagram algorithm. This new version will be available within several days through the assetstore.

 

The new version is now available through the Unity assetstore.

 

Is there a limit to the number of vertices that the algorithm can handle? For example...would I be able to triangulate a mesh with somewhere around 3,000,000 vertices?

 

There is not really a limit for the triangulation algorithm. I guess at some point memory will play a role, but that won't be a problem when you process millions of points.

 

Hello,

I have been using your asset to generate mesh from points. Is there any possibility to achieve 3D U Shaped meshes by some Geometry Algorithm implementation as Concave Hull for 3D? Any Update on that will be Good.

 

Hi Rai,

3D concave hull or 3D concave triangulation is not supported by this asset. Therefore, it won't be possible to create a 3D U-shaped concave hull or triangulation. Also, there no plans to add these algorithms in the nearby future.

 

Hi a doc or API reference would help explain all the things this asset can fully do, but how does it compare to Triangle.NET and Poly2Tri open source projects? Can it do the same basic (non delaunay) triangulation as Triangle.NET and how does speed compare?

 

Hi andyz,

Thanks for the feedback, a public doc or api reference is on the roadmap.

The 2D/2.5D triangulation algorithm use Triangle.NET in its core, so performance is comparable and you can perform the same basic triangulation (or more complex ones if you like). Also, there are several other geometric algorithms available in this asset.

 

Oh I see - well maybe you should state your code is built on 2 open source libraries as it reduces what you have created with the asset somewhat?
I guess your part is threading the code and adding conversion to/from Unity objects/classes within an easier API on top?

 

Yes, for some of the algorithms, I only handle the conversions, threading, and provide an easier to use API. For others, like the concave hull algorithm, they are built from scratch and do not use an external library.

 

I don't understand how to use the api to make a 2D polygon based on my points that define the perimeter. I have an ordered list of points that are ordered clockwise... and I do:

Code (CSharp):

1.             var parameters = new Triangulation2DParameters();
2.             parameters.Points = null;
3.             parameters.Boundary = _points.ToArray();
4.             parameters.Holes = null;
5.             parameters.Delaunay = true;
6.  
7.             var triangulationAPI = new TriangulationAPI();
8.             var m = triangulationAPI.Triangulate2D(parameters);
9.             Gizmos.DrawMesh(m);

Yet i get no output from the gizmos.

Also do you plan to update the asset to use the job system and general DOTs for more performance in future?

 

Hi,

The code to generate a triangulation seems to be correct. How does your input look like? If your points use the XZY coordinate system then you have to set that in the Triangulation2DParameters object (the CoordinateSystem property). Could you also check the actual mesh result if that is fine then the problem lies elsewhere.

At the moment there are no short-term plans to use the job system and DOTs

 

The `_points` collection has Vector3 as (x,0,z). I put the same points into unity's 2D polygon collider which correctly produced a mesh (although on the XY plane). So the list of points is correct (they are in a clockwise order representing the shape of the polygon).

 

If your input points always have the y value as zero and you triangulate in the xz plane then you should change the coordinate system (parameters.CoordinateSystem = CoordinateSystem.XZY). If this doesn't help then please provide a small example of what you are exactly doing, so I can have a closer look.

 

I've noticed that even with Delaunay set to false my point count is changing. Triangulate2D seems to remove a small number of points. And also seems to add a point occasionally.

I think I can work with this fact but I was thinking it would be nice if the algorithm told you the indexes of the points that were removed and added if possible.

I have custom procedural UV data that I need to match to vertices. And this is making that process very cumbersome.

I imagine having Triangulate2D provide this data would be faster than me looping through the vertices to find the indexes myself which is what I am doing now.

 

Hi, sorry for my late reply! I understand your issue, unfortunately the asset does not come with a solution that you can use right now. However, I will try to have a look at it if I can provide you the requested data.

Further, could you perhaps, if you don't mind send me an email (or dm) at benny@jobberwockysoftware.com with a small example of your input set where you experience these changes? Maybe I can improve the triangulation process as well.

 

is this support page still active? I have been trying to figure out how to generate a mesh using points that are generated at runtime. I have been able to do it based on the text file and also presetting up the array of points in the constructor of the Shape type class but not from anywhere else.

Is there a simple example. I am generating the verts and then pasing them to the Points array and attempting to triangulate2D.

Here is the error I am getting.

Code (CSharp):

1. NullReferenceException: Object reference not set to an instance of an object
2. Jobberwocky.TriangleNet.Mesh.InsertSubseg (Jobberwocky.TriangleNet.Topology.Otri& tri, System.Int32 subsegmark) (at <c5df936b5bcc45989f273b694e72af7c>:0)
3.  
4. Jobberwocky.TriangleNet.Meshing.ConstraintMesher.MarkHull () (at <c5df936b5bcc45989f273b694e72af7c>:0)
5. Jobberwocky.TriangleNet.Meshing.ConstraintMesher.FormSkeleton (Jobberwocky.TriangleNet.Geometry.IPolygon input) (at <c5df936b5bcc45989f273b694e72af7c>:0)
6.  
7. Jobberwocky.TriangleNet.Meshing.ConstraintMesher.Apply (Jobberwocky.TriangleNet.Geometry.IPolygon input, Jobberwocky.TriangleNet.Meshing.ConstraintOptions options) (at <c5df936b5bcc45989f273b694e72af7c>:0)
8. Jobberwocky.TriangleNet.Meshing.GenericMesher.Triangulate (Jobberwocky.TriangleNet.Geometry.IPolygon polygon, Jobberwocky.TriangleNet.Meshing.ConstraintOptions options, Jobberwocky.TriangleNet.Meshing.QualityOptions quality) (at <c5df936b5bcc45989f273b694e72af7c>:0)
9.  
10. Jobberwocky.TriangleNet.Meshing.GenericMesher.Triangulate (Jobberwocky.TriangleNet.Geometry.IPolygon polygon, Jobberwocky.TriangleNet.Meshing.ConstraintOptions options) (at <c5df936b5bcc45989f273b694e72af7c>:0)
11. Jobberwocky.GeometryAlgorithms.Source.Algorithms.Triangulation2D.Triangulation2DWrapper.Triangulate2DBase (Jobberwocky.GeometryAlgorithms.Source.Parameters.Triangulation2DParameters parameters) (at Assets/GeometryAlgorithms/Source/Algorithms/Triangulation2D/Triangulation2DWrapper.cs:152)
12. Jobberwocky.GeometryAlgorithms.Source.Algorithms.Triangulation2D.Triangulation2DWrapper.Triangulate2D (Jobberwocky.GeometryAlgorithms.Source.Parameters.Triangulation2DParameters parameters) (at Assets/GeometryAlgorithms/Source/Algorithms/Triangulation2D/Triangulation2DWrapper.cs:34)
13. Jobberwocky.GeometryAlgorithms.Source.API.TriangulationAPI.Triangulate2DRaw (Jobberwocky.GeometryAlgorithms.Source.Parameters.Triangulation2DParameters parameters) (at Assets/GeometryAlgorithms/Source/API/TriangulationAPI.cs:21)
14. Jobberwocky.GeometryAlgorithms.Source.API.TriangulationAPI.Triangulate2D (Jobberwocky.GeometryAlgorithms.Source.Parameters.Triangulation2DParameters parameters) (at Assets/GeometryAlgorithms/Source/API/TriangulationAPI.cs:33)
15. ShapePointList.OnEnable () (at Assets/ShapePointList.cs:91)

 

Hi there,

Yes there is still support and I just replied to your email!

 

Hey, I sent over an email with another question.

 

Hi,

Is it possible with this library to generate individual meshes for each voronoi cell? I would like to create a mesh that represents the shape created by the voronoi diagram centered around a given input point, but it does not appear as though Voronoi3D returns any linkage to the original points. Thus, I cannot tell what vertices returned in the geometry object should be used to generate this mesh via a convex hull for a given input point.

Is there something I am missing or a different method you recommend to accomplish this? Thanks!

 

Again sorry for my late, I just replied to your email.

 

Is there a constrained delaunay triangulation example?

 

The image on the right shows the result of a constrained delaunay triangulation. In the asset itself there are also various examples that you can try out and have a look at to learn how to use that algorithm.

 

Useful asset. Can you also add planar UVs to geometry3d and extrude?

 

Hmm, procedural mesh should be very mobile do-able... Why is it not working on iOS?

 

The asset store link at the start of this thread does not work for me. But this one does:
https://assetstore.unity.com/packages/tools/modeling/geometry-algorithms-61875