Refinement Problems

Aug 9, 2015 at 2:28 AM
Hello,

I've been working on a project using unity and triangle, and I'm having weird issues with the refinement procedure. I'm using the Beta 3 download. The issues are best illustrated with images:
The code I'm using is as follows:
var geometry = new InputGeometry();

/*for loop on the points on my curves to create the points (AddPoint) and segments (AddSegment)  to the InputGeometry */

TriangleNet.Mesh m = new TriangleNet.Mesh();
m.Triangulate(geometry);

var statistic = new TriangleNet.Tools.Statistic();
 statistic.Update(m, 1);
m.Behavior.MinAngle = (double)minAngle;
m.Behavior.MaxAngle = (double)maxAngle;
m.Behavior.MaxArea = statistic.LargestArea * (double)maxAreaRatio;

m.Refine();

/* loop through m.Vertices to retrieve verts, and m.Triangles to retrieve triangles.
Construct unity mesh from these */
I've tried a bunch of different things to no avail (playing with parameter values, adding m.Behaviour.Quality = true, copying code from the demo app). The demo app does seem to work perfectly fine though, and I copied the triangle source code directly from that. Any ideas?

Thanks!
Coordinator
Aug 9, 2015 at 9:46 AM
Edited Aug 9, 2015 at 9:53 AM
This looks a lot like you're messing up the triangle indices, so please review this part:
/* loop through m.Vertices to retrieve verts, and m.Triangles to retrieve triangles.
Construct unity mesh from these */
Additionally, you can check for any error's in the mesh by doing:
bool isConsistent, isDelauany;
m.Check(out isConsistent, out isDelauany);

foreach (var msg in TriangleNet.Log.SimpleLog.Instance.Data)
{
    Console.WriteLine(msg.Message);
}
EDIT: before passing data to another application, you should always call m.Renumber(); to ensure vertices are numbered linearly. But I'm not sure it will make difference in this case.
Aug 9, 2015 at 12:55 PM
m.Renumber actually solved this issue completely! Thanks!

There is another issue that happens while refining (and has happened in the past occasionally as well). This relates specifically to the interpolation of attributes on vertecies. In this case, I'm using an attribute for the z-value, And I will sometimes get these kinds of errors:

https://drive.google.com/file/d/0B9Sm8zke1RqAWVgyMUNEUno0QnM/view?usp=sharing
https://drive.google.com/file/d/0B9Sm8zke1RqAUTByMWl0WE82R2c/view?usp=sharing
https://drive.google.com/file/d/0B9Sm8zke1RqANWwtYzFtcFRIZzQ/view?usp=sharing

It seems to create seemingly random bumps, spikes, and other artifacts in the non-boundary regions, and they change drastically with the slightest movement of a vertex. In the images, the set vertecies are where the transform handles are, and the only difference between the images is that I moved one vertex.

Do you have a clue as to why this is, or what one can do to improve it?

Thanks!
Coordinator
Aug 9, 2015 at 4:10 PM
No, I never had this kind of issue. Do you have a static example (pure C#, no Unity stuff), where this issue occurs?
Aug 9, 2015 at 5:13 PM
Edited Aug 9, 2015 at 10:48 PM
Of course - I managed to reproduce it by re-making the shape I used in unity as a poly file and using the sample mesh explorer project. I added a text box to the statistics panel that writes out a list of the vertecies and their attributes, and found that I still got these issues when refining (There were attributes that had values that were larger in absolute value than any of the values I provided).
The full solution with that minor change is here: https://drive.google.com/file/d/0B9Sm8zke1RqAQmpxa1dseGd5S1U/view?usp=sharing
just load the test.poly file in the data folder when running the mesh explorer, triangulate using a min angle of 25, a max angle of 95 and a max area of 0.2, and look at the text in the vertex list text box in the statistics panel.
(The only change to code I made was adding that box, and populating it in the HandleMeshChange method of the StatisticView).

Here is the poly data I used:
9 2 1 1
1 -564.963 -961.3954 0 1
2 766.894 -643.5915 0 1
3 650.1689 379.2653 0 1
4 -251.2134 365.9495 0 1
5 -1552.631 -71.71667 0 1
6 -256.2429 -499.8359 291.8905 1
7 611.605 -445.8072 270.9263 1
8 433.6885 237.7357 0 1
9 -224.3082 296.6656 -147.7938 1
9 1
1 1 2 1
2 2 3 1
3 3 4 1
4 4 5 1
5 5 1 1
6 6 7 1
7 7 8 1
8 8 9 1
9 9 1 1
0
And here is my vertex list without refinement:
0: x - -564.963 y - -961.3954 attributes: 0 
1: x - 766.894 y - -643.5915 attributes: 0 
2: x - 650.1689 y - 379.2653 attributes: 0 
3: x - -251.2134 y - 365.9495 attributes: 0 
4: x - -1552.631 y - -71.71667 attributes: 0 
5: x - -256.2429 y - -499.8359 attributes: 291.8905 
6: x - 611.605 y - -445.8072 attributes: 270.9263 
7: x - 433.6885 y - 237.7357 attributes: 0 
8: x - -224.3082 y - 296.6656 attributes: -147.7938 
And with refinement:
0: x - -564.963 y - -961.3954 attributes: 0 
1: x - 766.894 y - -643.5915 attributes: 0 
2: x - 650.1689 y - 379.2653 attributes: 0 
3: x - -251.2134 y - 365.9495 attributes: 0 
4: x - -1552.631 y - -71.71667 attributes: 0 
5: x - -256.2429 y - -499.8359 attributes: 291.8905 
6: x - 611.605 y - -445.8072 attributes: 270.9263 
7: x - 433.6885 y - 237.7357 attributes: 0 
8: x - -224.3082 y - 296.6656 attributes: -147.7938 
9: x - 708.53145 y - -132.1631 attributes: 0 
10: x - 199.47775 y - 372.6074 attributes: 0 
11: x - -431.143915299624 y - -467.192554429526 attributes: -58.0576907778506 
12: x - 104.69015 y - 267.20065 attributes: -73.8969 
13: x - -901.9222 y - 147.116415 attributes: 0 
14: x - -25.867825 y - 369.27845 attributes: 0 
15: x - -576.5678 y - 256.5329575 attributes: 0 
16: x - -138.5406125 y - 367.613975 attributes: 0 
17: x - -413.8906 y - 311.24122875 attributes: 0 
18: x - -327.726057649812 y - -85.2634772147631 attributes: -102.925745388925 
19: x - -59.809025 y - 281.933125 attributes: -110.84535 
20: x - -347.379855881782 y - 250.377981232561 attributes: -175.814476027355 
21: x - -291.217742350189 y - 49.5641772147634 attributes: -118.764954611075 
22: x - -418.084278055385 y - 190.071277952843 attributes: -346.003650801662 
23: x - 306.198771047277 y - 249.153625011191 attributes: -28.6356930101518 
24: x - 424.823325 y - 375.93635 attributes: 0 
25: x - 522.64675 y - -104.03575 attributes: 135.46315 
26: x - -515.466784531917 y - -51.6489960405488 attributes: -315.887448969853 
27: x - 177.68105 y - -472.82155 attributes: 281.4084 
28: x - 100.9655 y - -802.49345 attributes: 0 
29: x - -41.5848691806783 y - -158.266710236183 attributes: -40.9905231773482 
30: x - -133.098533259951 y - 122.50277004416 attributes: -103.198189729375 
31: x - -231.99875 y - -881.944425 attributes: 0 
32: x - 90.2317996209904 y - 105.988124338587 attributes: -58.1495187953537 
33: x - -498.053457649812 y - -714.293977214763 attributes: -29.0288453889253 
34: x - 737.712725 y - -387.8773 attributes: 0 
35: x - 310.17797471778 y - 8.67373936416598 attributes: 55.3305754749748 
36: x - 567.125875 y - -274.921475 attributes: 203.194725 
37: x - -379.434986474718 y - -276.228015822145 attributes: -80.4917180833879 
38: x - 394.643025 y - -459.314375 attributes: 276.16735 
39: x - 679.350175 y - 123.5511 attributes: 0 
40: x - 433.92975 y - -723.042475 attributes: 0 
41: x - -945.380654542575 y - -618.720031593798 attributes: 0 
42: x - -781.62194738104 y - -238.8341525917 attributes: -515.414188776497 
43: x - 318.978131932777 y - -231.354374135286 attributes: 185.80570589094 
44: x - -755.171827271288 y - -790.057715796899 attributes: 0 
45: x - -685.200492947001 y - -553.347054809233 attributes: -292.929303370824 
Do you have any clue what could be causing this, or where I should look if I want to fix this?

Thanks again!

EDIT: added triangulation details

EDIT 2: It seems that the problem lies in the Quality.cs file, specifically in the SplitTriangle method. It has the following code:
for (int i = 0; i < mesh.nextras; i++)
                    {
                        // Interpolate the vertex attributes at the circumcenter.
                        newvertex.attributes[i] = borg.attributes[i]
                           + xi * (bdest.attributes[i] - borg.attributes[i])
                            + eta * (bapex.attributes[i] - borg.attributes[i]);
                    }
xi & eta are part of the Barycentric coordinates for the triangles, but there is one problem: they can sometimes be outside the triangle. Occasionally, they are more than 1 or less than 0. And on those occasions, the values inside the triangle will be scaled in a manner that doesn't match the actual values. Not yet sure how to solve this though. I still don't know where to find the actual coordinates of the point relative to it's containing triangle. But now I know it occurs when you have triangles that do not contain their circumcenters.
Coordinator
Aug 9, 2015 at 10:30 PM
Edited Aug 9, 2015 at 10:34 PM
Yes , I can confirm this. A possible fix/workaround might be to only use offcenters (the original Triangle code) for Steiner point locations. So, in Quality.cs find
if (behavior.fixedArea || behavior.VarArea)
{
    newloc = Primitives.FindCircumcenter(borg, bdest, bapex, ref xi, ref eta, behavior.offconstant);
}
else
{
    newloc = newLocation.FindLocation(borg, bdest, bapex, ref xi, ref eta, true, badotri);
}
and always use Primitives.FindCircumcenter.
Aug 10, 2015 at 1:20 AM
Edited Aug 10, 2015 at 1:24 AM
The fix that ended up working for me is this:
1) In the Mesh class, add an optional boolean calcAttr parameter to the InsertVertex method:
internal InsertVertexResult InsertVertex(Vertex newvertex, ref Otri searchtri,
            ref Osub splitseg, bool segmentflaws, bool triflaws, bool calcAttr = false)
This tells me that the InsertVertex method should calculate the attributes, rather than them being supplied by the newvertex.
2) Then change this:
 else
            {
                // Insert the vertex in a triangle, splitting it into three.
                horiz.Lnext(ref botleft);
                horiz.Lprev(ref botright);
                botleft.Sym(ref botlcasing);
                botright.Sym(ref botrcasing);
                MakeTriangle(ref newbotleft);
                MakeTriangle(ref newbotright);

                // Set the vertices of changed and new triangles.
                rightvertex = horiz.Org();
                leftvertex = horiz.Dest();
                botvertex = horiz.Apex();
                newbotleft.SetOrg(leftvertex);
                newbotleft.SetDest(botvertex);
                newbotleft.SetApex(newvertex);
                newbotright.SetOrg(botvertex);
                newbotright.SetDest(rightvertex);
                newbotright.SetApex(newvertex);
                horiz.SetApex(newvertex);
to this:
 else
            {
                // Insert the vertex in a triangle, splitting it into three.
                horiz.Lnext(ref botleft);
                horiz.Lprev(ref botright);
                botleft.Sym(ref botlcasing);
                botright.Sym(ref botrcasing);
                MakeTriangle(ref newbotleft);
                MakeTriangle(ref newbotright);

                // Set the vertices of changed and new triangles.
                rightvertex = horiz.Org();
                leftvertex = horiz.Dest();
                botvertex = horiz.Apex();

                if(calcAttr)
                {
                    double xdo, ydo, xao, yao;
                    double denominator;
                    double dodist, aodist;
                    double dx, dy;
                    xdo = leftvertex.x - rightvertex.x;
                    ydo = leftvertex.y - rightvertex.y;
                    xao = botvertex.x - rightvertex.x;
                    yao = botvertex.y - rightvertex.y;
                    denominator = 0.5 / (xdo * yao - xao * ydo);
                    dodist = xdo * xdo + ydo * ydo;
                    aodist = xao * xao + yao * yao;
                    dx = newvertex.x - rightvertex.x; //Note that this is different than the regular calculations used for dx/dy.
                    dy = newvertex.y - rightvertex.y;
                    double xi = (yao * dx - xao * dy) * (2.0 * denominator);
                    double eta = (xdo * dy - ydo * dx) * (2.0 * denominator);
                    for (int i = 0; i < nextras; i++)
                    {
                        // Interpolate the vertex attributes at the circumcenter.
                        newvertex.attributes[i] = rightvertex.attributes[i]
                           + xi * (leftvertex.attributes[i] - rightvertex.attributes[i])
                            + eta * (botvertex.attributes[i] - rightvertex.attributes[i]);
                    }
                }

                newbotleft.SetOrg(leftvertex);
                newbotleft.SetDest(botvertex);
                newbotleft.SetApex(newvertex);
                newbotright.SetOrg(botvertex);
                newbotright.SetDest(rightvertex);
                newbotright.SetApex(newvertex);
                horiz.SetApex(newvertex);
Here I'm checking if the calcAttr bool is set, and if so I'm doing the attribute calculation using the corners of the triangle actually being split by the new vertex.

Finally, in Quality.cs, in the SplitTriangle method, I commented out the calculation of the newvertex attributes, and added a true at the end of the function call to InsertVertex that comes immediately after.

Thanks again, and I hope this helps.
Coordinator
Aug 10, 2015 at 6:50 PM
This discussion has been copied to a work item. Click here to go to the work item and continue the discussion.
Coordinator
Sep 27, 2015 at 8:23 PM
Can you confirm that the latest changeset fixes the issue?