Get all points within a triangle is causing an overflow

Question

Well I'm lacking GraphicsPath in Unity (to fills polygon, draw them with and outline and utilities with shapes in general), so I'm doing my own implementation of it. Well, we could debate also which is the best option, but actually, I prefer this because I'm learning a lot.

The idea is the following, given a polygon, we do an offset polygon (inwards and outwards) with ClipperLib, and later with LibTessDotNet we triangulate it, outputing this:

Green, blue and yellow pixels are the sides of every triangle. LibTessDotNet output like 501 triangles for this shape.

So, thanks to @SimpleVar I done this:

public static IEnumerable<T> PointsInTriangle<T>(T pt1, T pt2, T pt3)
   where T : IPoint
{
    /*
         // https://www.geeksforgeeks.org/check-whether-triangle-valid-not-sides-given/
         a + b > c
         a + c > b
         b + c > a
     */

    float a = Vector2.Distance(new Vector2(pt1.x, pt1.y), new Vector2(pt2.x, pt2.y)),
          b = Vector2.Distance(new Vector2(pt2.x, pt2.y), new Vector2(pt3.x, pt3.y)),
          c = Vector2.Distance(new Vector2(pt3.x, pt3.y), new Vector2(pt1.x, pt1.y));

    // (new[] { pt1, pt2, pt3 }).Distinct(new PointComparer()).Count() == 0
    if (a + b <= c || a + c <= b || b + c <= a)
    {
        Debug.LogWarning($"The given points must form a triangle. {{{pt1}, {pt2}, {pt3}}}");
        yield break;
    }

    T tmp;

    if (pt2.x < pt1.x)
    {
        tmp = pt1;
        pt1 = pt2;
        pt2 = tmp;
    }

    if (pt3.x < pt2.x)
    {
        tmp = pt2;
        pt2 = pt3;
        pt3 = tmp;

        if (pt2.x < pt1.x)
        {
            tmp = pt1;
            pt1 = pt2;
            pt2 = tmp;
        }
    }

    var baseFunc = CreateFunc(pt1, pt3);
    var line1Func = pt1.x == pt2.x ? (x => pt2.y) : CreateFunc(pt1, pt2);

    for (var x = pt1.x; x < pt2.x; ++x)
    {
        int maxY;
        int minY = GetRange(line1Func(x), baseFunc(x), out maxY);

        for (int y = minY; y <= maxY; ++y)
            yield return (T)Activator.CreateInstance(typeof(T), x, y);
    }

    var line2Func = pt2.x == pt3.x ? (x => pt2.y) : CreateFunc(pt2, pt3);

    for (var x = pt2.x; x <= pt3.x; ++x)
    {
        int maxY;
        int minY = GetRange(line2Func(x), baseFunc(x), out maxY);

        for (int y = minY; y <= maxY; ++y)
            yield return (T)Activator.CreateInstance(typeof(T), x, y);
    }
}

private static int GetRange(float y1, float y2, out int maxY)
{
    if (y1 < y2)
    {
        maxY = Mathf.FloorToInt(y2);
        return Mathf.CeilToInt(y1);
    }

    maxY = Mathf.FloorToInt(y1);
    return Mathf.CeilToInt(y2);
}

private static Func<int, float> CreateFunc<T>(T pt1, T pt2)
    where T : IPoint
{
    var y0 = pt1.y;

    if (y0 == pt2.y)
        return x => y0;

    float m = (float)(pt2.y - y0) / (pt2.x - pt1.x);

    return x => m * (x - pt1.x) + y0;
}

Actually it works, but not too fine. Because it causes overflows (I have to kill Unity process with Process Explorer due to the big amount of RAM used by this code).

I have debugged this thing with breakpoints, but I can't figure where is the problem actually.

I think the problem are in for (var x = pt1.x; x < pt2.x; ++x) or for (int y = minY; y <= maxY; ++y) or in the next block... But as I said I can't debug like I'm get used to in WinForms. When the overflow is reached Visual Studio stops debugging and Unity crashes, so I'm a little bit stucked.

I tried to do a DotNetFiddle doing an overflow but I can't figure out nothing here... So... I don't know what can I do to improve the code.

Explain me everything you find is unoptimized, as well as, approaches I could do to improve my main goal.

Bobette

You've been dealing with this task for like 5 questions now. Maybe you gotta separate it into classes and write tests for it. – Salchunas

What do you mean by classes? – Bobette

If you cannot figure out a problem, maybe you should divide it into smaller pieces. You could write tests for each small step of your problem and make sure you understand every edge case. Then you could fix issues that occur unexpectedly. Write smaller methods and move similar methods into classes. – Salchunas

And this is what I actually doing. First I know Clipper, then I starting researching how to fill offset polygons given by this. Then I discovered triangulation, I tried several solutions like Poly2Tri and some done by Unity developers, finally I found LibTessDotNet and now I'm trying to fill triangles that tesselation gives me (to fill the offset polygon). My main problem now is how could I get all points within a triangle. But thanks! ^^ – Bobette

Can you show where you're calling this coroutine? Are you calling it every frame in Update or something? Make sure you are only calling it once. – Beatitude

No, I only call once at Start point. I'm researching for rasterization algorithms: sunshine2k.de/coding/java/TriangleRasterization/… and cs.unm.edu/~joel/cs491_VR/src/DrawUtilities.cs – Bobette

Answer 1

Ok, I solved it the problem was that triangles with an area equal or less to 1 was doing the overflow. Checking this with the Heron's formula I solved it:

    public static float TriangleArea(Point p1, Point p2, Point p3)
    {
        float a, b, c;

        if (!CheckIfValidTriangle(p1, p2, p3, out a, out b, out c))
            return 0;

        return TriangleArea(a, b, c);
    }

    public static float TriangleArea(float a, float b, float c)
    {
        // Thanks to: http://james-ramsden.com/area-of-a-triangle-in-3d-c-code/

        float s = (a + b + c) / 2.0f;
        return Mathf.Sqrt(s * (s - a) * (s - b) * (s - c));
    }

And then:

        if (TriangleArea(pt1, pt2, pt3) <= 1)
            return;

Maybe (I didn't tested) but it could be caused by generics.

In any case, I posted on Gist Github this nice TriangleUtils. Given a list of triangles tesselated with LibTessDotNet we can rasterize it: https://gist.github.com/z3nth10n/7d60f22c7e906f645d53c9622507c23b

I uploaded the following video showing what I achieved: https://youtu.be/7yY3MIyRtPw

Bobette