Is the first Edgeloop still the outer loop?

[pmeigneux]

Hello,

I try to determine for all types of surfaces what is the outer Edgeloop.

Is it always the first one on the face.EdgeLoops?

If not how to find it?

Philippe.

[RPTHOMAS108]

Below is another issue I now recall that you might want to consider:

When face is disjunct (single solid made of two or more parts) you need to be able to identify both outer loops of the face not just the outer loop to the furthest left or right.

Solved previously for this purpose.

[stefanome]

I created a version of SortCurveLoops that converts the XYZ points to UV points, then works on planar loops. I only tested it with a few cases where ExporterIFCUtils.SortCurveLoops fails, and it works well. I will start using it and see if it breaks in the next weeks.

My function takes in input a Face instead of a list of CurveLoops, because all the curves are tessellated and converted to UV. The Face is used for both finding the CurveLoops and converting to UV.

If there are outer loops contained in other outer loops (like in the third snapshot), the innermost loops are first in the resulting list.

This is the function:

public static List<List<CurveLoop>> SortCurveLoops(Face face)
{
    var allLoops = face.GetEdgesAsCurveLoops().Select(loop => new CurveLoopUV(loop, face)).ToList();

    var outerLoops = allLoops.Where(loop => loop.IsCounterclockwise).ToList();
    var innerLoops = allLoops.Where(loop => !outerLoops.Contains(loop)).ToList();

    // sort outerLoops putting last the ones that are outside all the preceding loops
    bool somethingHasChanged;
    do
    {
        somethingHasChanged = false;
        for (var i = 1; i < outerLoops.Count(); i++)
        {
            var point = outerLoops[i].StartPointUV;
            var loop = outerLoops[i - 1];
            if (loop.IsPointInside(point) is CurveLoopUV.PointLocation.Inside)
            {
                var tmp = outerLoops[i];
                outerLoops[i] = outerLoops[i - 1];
                outerLoops[i - 1] = tmp;

                somethingHasChanged = true;
            }
        }
    } while (somethingHasChanged);

    var result = new List<List<CurveLoop>>();
    foreach (var outerLoop in outerLoops)
    {
        var list = new List<CurveLoop> {outerLoop.Loop3d};

        for (var i = innerLoops.Count - 1; i >= 0; i--)
        {
            var innerLoop = innerLoops[i];
            if (outerLoops.Count() == 1 // skip testing whether the inner loop is inside the outer loop
                || outerLoop.IsPointInside(innerLoop.StartPointUV) == CurveLoopUV.PointLocation.Inside)
            {
                list.Add(innerLoop.Loop3d);
                innerLoops.RemoveAt(i);
            }
        }

        result.Add(list);
    }

    return result;
}

This is the class CurveLoopUV that converts the curves from 3D XYZ to UV, then to planar XYZ. 

class CurveLoopUV : IEnumerable<Curve>
{
    public enum PointLocation
    {
        Outside,
        OnTheEdge,
        Inside,
    }

    public CurveLoop Loop3d { get; }
    private readonly CurveLoop _loop2d;

    public readonly double MinX, MaxX, MinY, MaxY;

    public CurveLoopUV(CurveLoop curveLoop, Face face)
    {
        Loop3d = curveLoop;
        _loop2d = new CurveLoop();
        
        var points3d = Loop3d.SelectMany(curve => curve.Tessellate().Skip(1));
        var pointsUv = points3d.Select(point3d => face.Project(point3d).UVPoint);
        var points2d = pointsUv.Select(pointUv => new XYZ(pointUv.U, pointUv.V, 0)).ToList();

        MinX = MinY = 1.0e100;
        MaxX = MaxY = -1.0e100;
        var nPoints = points2d.Count();
        for (var i = 0; i < nPoints; i++)
        {
            var p1 = points2d[i];
            var p2 = points2d[(i + 1) % nPoints];
            _loop2d.Append(Line.CreateBound(p1, p2));
            if (p1.X < MinX) MinX = p1.X;
            if (p1.Y < MinY) MinY = p1.Y;
            if (p1.X > MaxX) MaxX = p1.X;
            if (p1.Y > MaxY) MaxY = p1.Y;
        }
    }

    public PointLocation IsPointInside(XYZ point)
    {
        if (point.Y + Eps < MinY || point.Y + Eps > MaxY)
            return PointLocation.Outside;

        if (_loop2d.Any(curve => curve.Distance(point) < Eps))
            return PointLocation.OnTheEdge;

        var line = Line.CreateBound(point, new XYZ(1.0e100, point.Y, 0));
        var nIntersections = _loop2d.Count(edge => edge.Intersect(line) == SetComparisonResult.Overlap);
        return nIntersections % 2 == 1 ? PointLocation.Inside : PointLocation.Outside;
    }

    public bool IsCounterclockwise => _loop2d.IsCounterclockwise(XYZ.BasisZ);

    public XYZ StartPointUV => _loop2d.First().GetEndPoint(0);

    public IEnumerator<Curve> GetEnumerator() => _loop2d.GetEnumerator();

    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}

[jeremy_tammik]

Wow! Fantastic job! This is real research, with real test cases. I love it. Thank you very much for your work and important results. I'll take a closer look and would probably like to share this on the blog soon.

Cheers, 

Jeremy

[stefanome]

Here is a little improvement on CurveLoopUV.IsPointInside:

public PointLocation IsPointInside(XYZ point)
{
    // Check if the point is outside of the loop bounding box
    if (point.X - Eps < MinX
        || point.X + Eps > MaxX
        || point.Y - Eps < MinY
        || point.Y + Eps > MaxY)
        return PointLocation.Outside;

    // Check if the point is on the loop
    if (_loop2d.Any(curve => curve.Distance(point) < Eps))
        return PointLocation.OnTheEdge;

    // Count the number of intersections between a line starting from point and going outside
    // of the loop. If the number of intersection is odd, then point is inside the loop.
    // Discard the solutions where the intersection is the edge start point, because these
    // intersections have already been counted when intersecting the end point of the
    // previous segments
    var line = Line.CreateBound(point, new XYZ(MaxX + 1, MaxY + 1, 0));
    var nIntersections = _loop2d
        .Where(edge => edge.Intersect(line) == SetComparisonResult.Overlap)
        .Count(edge => line.Distance(edge.GetEndPoint(0)) > Eps);

    return nIntersections % 2 == 1 ? PointLocation.Inside : PointLocation.Outside;
}

[jeremy_tammik]

Brilliant! Thank you very much for your careful research and nice implementation!

Thank you also for your pull request to The Building Coder Samples:

https://github.com/jeremytammik/the_building_coder_samples/pull/16

I integrated it into release 2021.0.150.25:

https://github.com/jeremytammik/the_building_coder_samples/compare/2021.0.150.24...2021.0.150.25

Now to edit the discussion above into a succinct blog post...

[stefanome]

Here is the model I used for testing.

As you can tell, I'm learning how Revit works, I'm sure there are better ways to create faces with multiple nested loops.

[jeremy_tammik]

Finally got around to editing this:

https://thebuildingcoder.typepad.com/blog/2021/05/roadmap-today-and-sorting-non-planar-curve-loops.h...

Thank you very much for your very nice work!

[BKSpurgeon]

yeah this just tripped me up too. I stumbled upon a special case where the zero index was not the outer loop.

It would be super nice if the API had an "outerloop" property which simply returned that for us.

Update:

I just now submitted a ticket to the Revit Idea Station. I copy pasted @stefanome code as well thanks for that to illustrate the amount of work required to obtain that outerloop.

I would gladly submit a PR to the API to implement this for the rest of the community.

EdgeArray edgeArray = edgeArrayArrays.OuterLoop;

[jeremy_tammik]

Yup, sorry about that. Please submit a wish list item for this functionality in the Revit Idea Station and ensure that it gets lots of votes.

[BKSpurgeon]

Done! I have followed your advice: so anyone who is interested in a solution to this can vote for it here: 

https://forums.autodesk.com/t5/revit-ideas/revit-api-request-edgearrayarray-should-have-an-outerloop...

[lvirone]

Hello,

I think the projection of the curved Face on XY plane makes the IsCounterclockwise not robust. I tested this method on the following faces and the faces at the opposite direction, and I got opposite result to determine OuterLoops and InnerLoops so the algorithm return a wrong value half the time (wrong result for opposites faces in this example). My tests are in Revit 2022.

To have a more robust solution, I used the projection CurveLoopUV perform with ExportedIFCUtils :
ExporterIFCUtils.SortCurveLoops(allLoops.Select(x => x.Loop2d).ToList()).Select(x => x).ToList();

After this, I perform a CustomEquals between the curveLoops (I compare their Curves order, and for each Curve their Type and their EndPoints XYZ with a Tolerance).

public static List<List<CurveLoop>> SortCurveLoops(Face face)
{
    var allLoops = face.GetEdgesAsCurveLoops().Select(loop => new CurveLoopUV(loop, face)).ToList();

    var sorted2ds =
    ExporterIFCUtils.SortCurveLoops(allLoops.Select(x => x.Loop2d).ToList()).Select(x => x.ToList()).ToList();

    var result = new List<List<CurveLoop>>();
    foreach (var sorted2d in sorted2ds)
    {
        var resultIn = new List<CurveLoop>();

        foreach (var loop in sorted2d)
        {
            var loopUv = allLoops.First(x => x.Loop2d.CustomEquals(loop));
            resultIn.Add(loopUv.Loop3d);
        }

        result.Add(resultIn);
    }

    return result;
}

[jeremy_tammik]

Thank you very much for raising the topic and sharing your solution. One note or the sorting direction: You cannot reply on clockwise or counterclockwise sorting from SortCurveLoops, because it does not take a normal argument. Therefore, it is impossible to determine from which side you are looking at the curve loop. Looking from one side, a sorted curve loop is sorted clockwise; from the other, counterclockwise.