Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Zero-width triangles are produced (They have no area as one point is between the two others) #6

Closed
KellanHiggins opened this issue Aug 20, 2015 · 26 comments
Assignees
Labels

Comments

@KellanHiggins
Copy link

First off, great port. This saved me probably years of time when generating meshes from complex shapes. But I am having an issue with zero width triangles.

When tessellating a 6 sided box, zero width triangles are being generated. These zero-width triangles then mess up my tangent calculation in Unity.

Here is a picture of the box.

triangleissue

The Triangle is created by using the contour of (2.0, 0.0, 4.0), (2.0, 0.0, 2.0), (4.0, 0.0, 2.0), (4.0, 0.0, 0.0), (0.0, 0.0, 0.0), (0.0, 0.0, 4.0), (2.0, 0.0, 4.0). This will regularly reproduce the issue with the zero width triangle. The triangle of zero with has the points of (0,0,4), (2,0,2), (4,0,0).

This also happens with cutouts, creating zero width triangles for cutouts that are on the same level (I am using this for window cutout generation in a wall).

I tried to dive into the Tessellation code, but that is over my head. I can sort of fix the problem by adding randomization to the contours so I don't get zero width triangles, but it is a pain.

Any help or even directing me to where this problem might original would be super appreciated!

@speps
Copy link
Owner

speps commented Aug 22, 2015

Thanks Kellan, I'll see if I can take a look soon but no promises. The code itself isn't too complicated, but it's a bit hard to get into it for the first time. If I remember correctly there is some code that merged vertices, try looking for calls to Mesh.Splice as it's the operation that merges vertices (among other operations).

@KellanHiggins
Copy link
Author

Hmmm, okay. May look into later. I hacked / fixed the issue by adding uncertainty to all points. So you get extremely small triangles but at leas they have some uncertainty.

Maybe add a function that figures out if a triangle has zero area and then delete it if true?

@ratkingsminion
Copy link

Will this ever get fixed? I also have a simple case where such triangles are generated already, see this animation:

PlusSign

In all other cases, this is the best triangulation library I ever tried - congrats to that!

EDIT: I tried release version 1.0.29, and there the problem with the zero-area triangles is not present, at least not with this shape. (With some donut-like shape I could see very thin triangles, tho.)

@KellanHiggins
Copy link
Author

REALLY?? It is fixed? I will do some testing and see if it is fixed on my end. Super pumped.

@ratkingsminion
Copy link

No, it's not really fixed. But with this particular test case, version 1.0.29 (which is older than the current one) produces a much better result. I still have problems with cases like this:

Ring

With poly2tri, this ring get triangulated in a much nicer way. Unfortunately poly2tri has problem in a lot of other cases, where it even throws exceptions.

@KellanHiggins
Copy link
Author

I wrote a fixer script that after generating the triangles it finds any zero size triangles and deletes them. This is a hack fix, but does fix it.

@ratkingsminion
Copy link

Unfortunately the triangles in this ring are never zero sized, but just very very thin. It would be visible if I'd delete them.

@KellanHiggins
Copy link
Author

May be a general problem with the algorithm. I am using this mostly for weird shaped squares. May have to update the library if it becomes a problem for me.

@speps
Copy link
Owner

speps commented Dec 9, 2015

A bug was fixed where the reference vector for triangulation was diagonal (or horizontal) but in the original libtess it wasn't so that's why you get different results.

About thin or zero triangles, I don't know if it's a problem with the algorithm or the port. However, it's known that this kind of algorithm can have precision issues. In the case of very very thin triangles, if you say that you would see it if you deleted them, then they should be here :)

@speps speps added the bug label Dec 9, 2015
@speps speps self-assigned this Dec 9, 2015
@speps
Copy link
Owner

speps commented Dec 9, 2015

It should be possible to add an option to delete the zero area faces from the half edge mesh directly instead of having to do it post triangulation.

@ratkingsminion
Copy link

Just saying - this is how poly2tri triangulates the same ring:

Ring2

Or the "plus" shape from above:

Plus

So yeah, LibTess' algorithm isn't quite optimal.

@speps
Copy link
Owner

speps commented Dec 10, 2015

It's a different algorithm, it's faster on most cases (not sure about yours) and mostly designed for real-time use cases.

In the end, it depends on your usage, if they look the same when filled in, I don't see why it's a problem :)

@ratkingsminion
Copy link

I got poly2tri from here. It could become a problem for example with cloth simulation.

@speps
Copy link
Owner

speps commented Dec 10, 2015

I know Poly2Tri, it's bundled in the TessBed program to provide comparison between the 2 libraries :)

For cloth simulation, you would have issues with using that mesh directly anyway, it would need more links than just the edges so you'd need another authoring process entirely.

@ratkingsminion
Copy link

Yeah, maybe.

@KellanHiggins
Copy link
Author

I wrote a pretty inefficient (I think) removal script. You need to run this at the end of running the method Tessellate.

Problems are that it uses a list to remove the offending triangles. Not great for memory management.

Also uses UnityEngine's Vector3 instead of the LibTess's Vector3s to calculate the size of a sphere. To fix this, need to add calculation of magnitude to LibTess's Vector3 and change the code.

Hope this helps someone in the future! Its work for all the cases I've run into so far.

/// <summary>
/// Removes triangles from this tesselated object that are thin enough to be a straight line
/// </summary>
private void RemoveZeroAreaTriangles ()
{
    List<int> zeroAreaTriangleStartIndexes = new List<int>();

    for (int n = 0; n < this.Elements.Length; n = n+3)
    {
        UnityEngine.Vector3 p1 = this.Vertices[this.Elements[n]].Position.ToVector3(); 
        UnityEngine.Vector3 p2 = this.Vertices[this.Elements[n + 1]].Position.ToVector3(); 
        UnityEngine.Vector3 p3 = this.Vertices[this.Elements[n + 2]].Position.ToVector3(); 

        if(p1 == p2 || p2 == p3 || p3 == p1)
        {
            zeroAreaTriangleStartIndexes.Add(n);
            continue;
        }

        float area = CalculateAreaOfTriangle(p1, p2, p3);

        if(area == 0 || float.IsNaN(area) || area < 0.1f) // 0.04 will cover walls with a lot of skinny windows up to about 40 meters long. After that, you either get blackness or lightness
        {
            if(area > 0)
            {
                if(p1.y == p2.y && p2.y == p3.y)
                {
                    // Also should make sure the triangle is very thin
                    // This is a specific fix for the window generation where very small triangles are created
                    if(p1.x == p2.x && p2.x == p3.x
                       || p1.z == p2.z && p2.z == p3.z)
                        zeroAreaTriangleStartIndexes.Add(n);
                }
            }
            else
            {
                zeroAreaTriangleStartIndexes.Add(n);
            }
        }
    }

    if(zeroAreaTriangleStartIndexes.Count > 0)
    {
        List<int> ElementsList = this._elements.ToList<int>();

        // Removes all zero sized area triangles
        // Does this by loading the list and removing at them
        for(int i = 0; i < zeroAreaTriangleStartIndexes.Count; i++)
        {
            ElementsList.RemoveRange(zeroAreaTriangleStartIndexes[i] - i * 3, 3);
        }

        this._elements = ElementsList.ToArray<int>();
    }
}

private float CalculateAreaOfTriangle (UnityEngine.Vector3 p1, UnityEngine.Vector3 p2, UnityEngine.Vector3 p3)
{
    double a = (p1 - p2).magnitude; // pt1.DistanceTo(pt2);
    double b = (p2 - p3).magnitude; // pt2.DistanceTo(pt3);
    double c = (p1 - p3).magnitude; // pt3.DistanceTo(pt1);
    double s = (a + b + c) / 2;
    return (float)System.Math.Sqrt(s * (s-a) * (s-b) * (s-c));
}

@speps
Copy link
Owner

speps commented Jan 30, 2016

I'm sorry I've not had the time to take a closer look at this. It is expected to have zero area triangles with the algorithm, however, they could be removed automatically at the source (i.e. in the Mesh class). There is a ZapFace method that could be used for this right after the decomposition into convex faces has been done.

@speps speps changed the title Zero-width triangles are producedm (They have no area as one point is between the two others) Zero-width triangles are produced (They have no area as one point is between the two others) Jan 30, 2016
speps added a commit that referenced this issue Feb 3, 2016
@speps
Copy link
Owner

speps commented Feb 3, 2016

I've had a look with the first test data you gave and added it to the test data in c61e5ba.

It seems correct to me in TessBed, I had to improve it in b2e9f0c to support non XY plane test data. It returns 3 triangles only (see issue6.testdat).

Do you have more data I could work with please? Screenshots help but data is better for me :) Thanks.

@KellanHiggins
Copy link
Author

Oh that is awesome. I will get you some data soon, maybe tomorrow. Bump this in a week if I don't get it to you.

@speps
Copy link
Owner

speps commented Feb 4, 2016

@KellanHiggins My bad, it does return an empty triangle with the L shape or the cross shape. I will look into solutions, probably a new tessellation mode so it doesn't change the behaviour. The original libtess and libtess2 (the refactored version) do return those zero area triangles as well it seems (I tested the L shape). Your solution is okay but it would be better to do the right thing on the internal quad edge mesh directly.

@ratkingsminion About the differences between Poly2Tri and LibTessDotNet, I can't do anything to the algorithm, it's just how it works and why it's so robust as well. However, you can try changing the Normal property on the Tess instance to specify the sweep plane (which would help for the cross if you have a diagonal as the normal). Changing the Normal should work with your version, but I improved it a little bit with the latest one.

@KellanHiggins
Copy link
Author

It may be a limitation of libtess and how it is generated. That is totally fine and I don't think there should be an entirely new algorithm to determine these triangles.

Maybe someone smarter than me can make a garbageless super quick version of my empty triangle remover and add it as an option when generating the triangles.

@speps
Copy link
Owner

speps commented Feb 4, 2016

Yeah that's what I meant, I'll try to do that, it should be straightforward.

@KellanHiggins
Copy link
Author

Awesome! I look forward to it :).

@speps
Copy link
Owner

speps commented Feb 6, 2016

Fixed by 665c8f6. Let me know if it works for you.

See https://github.com/speps/LibTessDotNet/releases/tag/v1.0.46 for more information.

@KellanHiggins
Copy link
Author

I don't really understand the solution, but I will test it to see if it works. Thanks so much!

@KellanHiggins KellanHiggins reopened this Feb 6, 2016
@KellanHiggins
Copy link
Author

WHOOPS, didn't mean to open this up again. Tested it.

Before:

screen shot 2016-02-06 at 12 05 32 pm

After:

screen shot 2016-02-06 at 12 05 42 pm

You did it! All the black areas (which meant there was an incorrectly created small triangle) have been removed.

Thanks a lot! Closed for good.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

No branches or pull requests

3 participants