Feature request: holes in terms of index in the Position array #22
Comments
|
As an example, it would be pretty difficult for me to describe the big black shape containing two holes with HoleSeeds. Maybe there is an easy way, but I don't know it.
|
|
Even crazier example here: https://twitter.com/madjoystudio/status/1367959932104962050/photo/1 |
|
Hi, @tony-topper, thanks for the feedback! Currently public class InputData
{
public NativeArray<float2> Positions { get; set; }
public NativeArray<int> ConstraintEdges { get; set; }
public NativeArray<float2> HoleSeeds { get; set; }
}Hole seed is defined as arbitrary position "inside" the hole. See the first fig in summary. Example: So one can describe above configuration as following: using var positions = new NativeArray<float2>(new[]
{
math.float2(0, 0),
math.float2(3, 0),
math.float2(3, 3),
math.float2(0, 3),
math.float2(1, 1),
math.float2(2, 1),
math.float2(2, 2),
math.float2(1, 2),
}, Allocator.Persistent);
using var edges = new NativeArray<int>(new[]
{
0, 1,
1, 2,
2, 3,
3, 0,
4, 5,
5, 6,
6, 7,
7, 4
}, Allocator.Persistent);
using var holeSeeds = new NativeArray<float2>(new[] { (float2)1.5f }, Allocator.Persistent);As I understand it correctly, you want to define hole explicitly, using hole's edges. Please let me know if I answered your question. |
|
Thanks for the reply; super helpful. So you only need one hole seed per hole? If I am understanding you correctly there, then yes, that is easier. (FWIW, the current triangulator I am using is here) I tried a few others before picking that one. It does have some threading support but it is C# standard threading, not the Unity Jobs system and Burst. Am I right in assuming you don't need to provide the edges? Is that part of the settings somewhere? I'll be working on a job today that takes my point array and indexes array and finds a hole seed for each whole. I can get that to create the edges as well if I need to. Maybe it will be clean enough to provide back to as a possible alternative constructor or something. As that seems to be a common way to have 2D plane data. |
|
FWIW, I was getting this error: "ArgumentException: The provided input Positions is not supported!
Then I noticed in your source you are validating the data at the time of calling Schedule, which unfortunately doesn't work well for my case, and I imagine quite a number of use cases that use dependencies. I think this will be a problem for anyone that builds the data in a dependent job. I noticed you must have anticipated this since the ValidateInput setting does exist. Really looking forward to getting this running and seeing if it will offer me any speed up in my map generation prototype. I don't think I'll be able to provide my job back though. I ended up using a strange way to get the hole seed, but it was very efficient for me to do so the way I did. To do the beveling effect you see in my screenshot I do some LERPing towards a target. Which I just used to LERP away from and get a point inside the hole. Hoping that works for me. Cheers, Tony |
|
Another FWIW, not clear if Output.Positions are congruent to vertices but that is what I am guessing. |
Yes.
You have to constrain edges which belong to the hole (using Creating holes is a post-process operation. After triangulation is complete, For each hole seed, a triangle which contains its position is found. Then the triangle is enqueued and all its neighbor triangles, which do not share constrain edges, are added to the queue. All triangles from the queue are deleted.
I think using a single constructor and additional input/output class is a more user-friendly experience.
It is rather great news, because we have some lead 😀 I'm guessing that you are generating input data using If this is the problem then the simplest solution is to try to call
Do not worry about validation. using var triangulator = new Triangulator(Allocator.Persistent);
triangulator.Settings.ValidateInput = falseRegarding job dependency. Currently, validation is done in jobs and dependency is passed, see below: [Conditional("ENABLE_UNITY_COLLECTIONS_CHECKS")]
private static void RunValidateInputPositions(Triangulator @this, JobHandle dependencies)
{
using var isValid = new NativeReference<bool>(Allocator.TempJob);
new ValidateInputPositionsJob(@this, isValid).Schedule(dependencies).Complete();
if (isValid.Value == false)
{
throw new ArgumentException(
$"The provided input {nameof(Triangulator.Input.Positions)} is not supported!\n" +
$"1. Points count must be greater/equal 3.\n" +
$"2. Input positions cannot contain duplicated entries.\n" +
$"3. Input positions cannot contain NaN or infinities."
);
}
}Validation is a costly operation since Burst does not have full Exception support and I have to call complete on validation.
I hope it helps, if not can you provide me with your input data (points, edges, holes) for triangulation? I could try it investigate further. Best, |
|
Thanks for another thorough reply. Much appreciated.
Being straightforward, the validation seems suspicious to me. Something doesn't look quite right in there, but maybe I am not following the code accurately. Also, from an API consumer's perspective, I would not be expecting to have my dependencies be completed by the validation.
Still not clear on if Positions are congruent to vertices. Meaning can I convert them to Vector3 and call SetVertices on a Unity Mesh instance. That is a more old school way, but that's still how I am doing it. I know they have a MeshData struct which is meant for using with the Unity Jobs system. To circumvent the need for more clarity, a helpful method might be to add a ToMesh() method on OutputData class or maybe that would be better in an extension method. Although now that I am looking at MeshData and MeshDataArray in the Unity API docs it looks like MeshDataArray is the way for me to go since I am creating hundreds of Mesh objects at once. But for now I just want to get the I/O of this API going and see what I get out and how fast it is compared to making all my meshes on the main thread, which is a big bottleneck for me right now. |
Do you suspect some errors in validation? I have tests for it, did I miss some cases? I hope validation is ok. Regarding the "consumer's perspective". Input validation is editor-only and optional, so I do not care much about job completion here. In build, when the highest performance is required, validation is not available.
Yes, positions can be used for creating the mesh. I do it in my PBD2D project. See here and here.
I have been thinking about it but rather as extension methods. I want to preserve sparse, single-file, form of the project. How about my lead related to
I am convinced in 99% if you are using Feel free to ask me more for help, share the data, or whatever you like. |
|
I am currently writing a job to create the edges array in the format needed for the triangulator. I am able to see the length of the data in that job and it looks good. It isn't a deferred array at that point but farther up the chain it was, not sure if what kind of difference that makes. Will report back after I iron that out and can see what kind of data the triangulator comes back with. |
|
I've just opened #23. I fixed here the issue related to deferred arrays. I'm going to release it as |
|
The links for mesh creation are helpful to see, thanks. Well, I am not passing it in as a deferred array directly into the Input.Positions. But it was originally a deferred array, further up the dependency chain, so the bug might still apply. Here's the debug log I call in the job prior to the triangulator where I build the edges. Calling AsReadOnly() does not seem to affect the length.
Everything seems good in my data AFAIK. Getting 0 output positions and 0 triangles when I turn off validation. With validation I get the errors and a warning saying Position.Length is less then 3! Does using AsReadOnly make things faster? I ask that because otherwise it doesn't seem necessary. And if Validation is only for development environments it doesn't seem needed, right? Maybe I do not know something; I would love to learn something. |
|
Ok, thanks for the data, I will investigate it today.
Burst compiler optimization is incredible! As far as I know, |
|
Ok, there are several issues here.
I did not observe a problem with a position count of less than three, so probably you have some issues with the jobs. Another issue, which I did not observe earlier, is the problem with floating point precision. Below I attach code for your data with respect to the translation of the COM and debug image. [Test]
public void DrawTest()
{
float2[] managedPositions =
{
new(47.2836f, 97.28359f), // 0
new(47.21725f, 97.38288f), // 1
new(47.19396f, 97.5f), // 2
new(47.21725f, 97.61712f), // 3
new(47.2836f, 97.71641f), // 4
new(47.32997f, 97.75447f), // 5
new(47.38288f, 97.78275f), // 6
new(47.44029f, 97.80016f), // 7
new(47.5f, 97.80605f), // 8
new(47.55971f, 97.80016f), // 9
new(47.61712f, 97.78275f), // 10
new(47.67003f, 97.75447f), // 11
new(47.7164f, 97.71641f), // 12
new(47.78275f, 97.61712f), // 13
new(47.80604f, 97.5f), // 14
new(47.79561f, 97.42079f), // 15
new(47.76504f, 97.34698f), // 16
new(47.7164f, 97.28359f), // 17
new(47.65302f, 97.23495f), // 18
new(47.57921f, 97.20438f) // 19
};
var com = float2.zero;
foreach(var p in managedPositions)
{
com += p;
}
com /= managedPositions.Length;
managedPositions = managedPositions.Select(i => i - com).ToArray();
int[] constraints =
{
0, 1,
1, 2,
2, 3,
3, 4,
4, 5,
5, 6,
6, 7,
7, 8,
8, 9,
9, 10,
10, 11,
11, 12,
12, 13,
13, 14,
14, 15,
15, 16,
16, 17,
17, 18,
18, 19,
19, 0, // andywiecko: inserted by me
//19, 20, // andywiecko: out of range!
//20, 21,
//21, 22,
//22, 23,
//23, 0
};
using var positions = new NativeArray<float2>(managedPositions, Allocator.Persistent);
using var edges = new NativeArray<int>(constraints, Allocator.Persistent);
using var triangulator = new Triangulator(64, Allocator.Persistent)
{
Settings =
{
ValidateInput = true,
ConstrainEdges = true,
RefineMesh = false,
RestoreBoundary = true,
},
Input =
{
Positions = positions,
ConstraintEdges = edges
}
};
triangulator.Run();
var triangles = triangulator.Output.Triangles.AsArray().AsReadOnly();
for (int i = 0; i < triangles.Length / 3; i++)
{
var a = triangles[3 * i + 0];
var b = triangles[3 * i + 1];
var c = triangles[3 * i + 2];
var pA = managedPositions[a];
var pB = managedPositions[b];
var pC = managedPositions[c];
Draw(pA, pB, Color.blue);
Draw(pB, pC, Color.blue);
Draw(pC, pA, Color.blue);
}
for (int i = 0; i < edges.Length / 2; i++)
{
var a = edges[2 * i + 0];
var b = edges[2 * i + 1];
var pA = managedPositions[a];
var pB = managedPositions[b];
Draw(pA, pB, Color.red);
}
void Draw(float2 pA, float2 pB, Color color, float time = 10f) =>
Debug.DrawLine(new(pA.x, pA.y, 0), new(pB.x, pB.y, 0), color, time);
}
|
|
Sorry, look in the Debug.Log call; I truncate the debug output because some of these shapes will have 100s of points. |
|
Translating the input positions from world space to local space is something I did forget I am doing in cases with holes. I currently have two triangulators I am using. One for meshes with holes and one for meshes without. And for the meshes with holes, I do have to translate the input to local space, but not within a [-1, 1] box. I do need the positions to be in my prototype's Unity space though. Wondering how much of a penalty there would be with translating to a -1, 1 space, and back, Is there an advantage to having it in that kind of space for the triangulation? |
Upps I missed that, I focused on the data too much 😁
Normalized position can influence numerical stability, see e.g. S.W. Sloan. "A fast algorithm for generating constrained Delaunay triangulations." Comput. Struct. 47.3:441-450 (1993):
The normalization is cheap operation and "parallel friendly". |
|
Ah, good to know. Thanks for the reply. Seems like you're package is the only one to do Burst triangulation with holes that I can find. I guess I'll be waiting til you can update these things; plenty of other things to work on in the meantime. |
Great! I hope I will add normalization till the end of the month, but it may take a little longer. |
|
@tony-topper Halloween update 🎃 I've just released |
|
Thanks! Hopefully, I can check it out this week. |
|
One more note @tony-topper regarding meshes. |
I was so stoked to try your triangulator but unfortunately, I ran into a somewhat significant hurdle.
I am used to having holes stored as an index in the array of overall points. So if there are 100 points and 0 through 79 is the outer boundary and 80 through 89 is one hole and 90 through 99 is another hole you'd have an array of 2 or 3 int indexes describing the boundaries/holes
Either { 0, 80, 90 } or just { 80, 90 } depending on preferences.
The text was updated successfully, but these errors were encountered: