Получить границы ребер сетки - в порядке намотки

У меня есть триангулированная сетка. Предположим, это похоже на неровную поверхность. Я хочу быть в состоянии найти все края, которые падают на окружающую границу сетки. (забудь о внутренних вершинах)

Я знаю, что должен найти ребра, которые связаны только с одним треугольником, и собрать все это вместе, и это ответ. Но я хочу быть уверен, что вершины этих ребер расположены по часовой стрелке вокруг фигуры.

Я хочу сделать это, потому что я хотел бы получить линию многоугольника вокруг сетки.

Я надеюсь, что это достаточно ясно, чтобы понять. В некотором смысле я пытаюсь "де-триангулировать" сетку. ха! если есть такой термин.

Источник

4 ответа

Решение

На граничные ребра ссылается только один треугольник в сетке, поэтому, чтобы найти их, вам нужно отсканировать все треугольники в сетке и взять ребра с одним счетчиком ссылок. Вы можете сделать это эффективно (в O(N)) используя хеш-таблицу.

Чтобы преобразовать набор ребер в упорядоченный многоугольный цикл, вы можете использовать метод обхода:

  1. Выберите любой не посещенный край [v_start,v_next] и добавить эти вершины в цикл многоугольника.
  2. Найти непосещенный крайний сегмент [v_i,v_j] это имеет либо v_i = v_next или же v_j = v_next и добавить другую вершину (ту, которая не равна v_next) к многоугольной петле. Сброс v_next как эта вновь добавленная вершина, отметьте край как посещенный и продолжайте с 2.
  3. Обход завершен, когда мы вернемся к v_start,

Обход даст многоугольную петлю, которая может иметь порядок по часовой стрелке или против часовой стрелки. Последовательное упорядочение может быть установлено с учетом подписанной области многоугольника. Если обход приводит к неправильной ориентации, вам просто нужно изменить порядок вершин многоугольной петли.

Источник

Ну, как говорится, - заставить его работать - тогда лучше работать. Я заметил в моем примере выше, что предполагается, что все ребра в массиве ребер на самом деле соединяются в красивую границу. Это не может иметь место в реальном мире (как я обнаружил из моих входных файлов, которые я использую!) На самом деле некоторые из моих входных файлов на самом деле имеют много полигонов, и все они должны быть обнаружены. Я также хотел убедиться, что порядок намотки правильный. Так что я исправил это. увидеть ниже. (Чувствую, что я наконец добился успеха!)

    private static List<int> OrganizeEdges(List<int> edges, List<Point> positions)
    {
        var visited = new Dictionary<int, bool>();
        var edgeList = new List<int>();
        var resultList = new List<int>();
        var nextIndex = -1;
        while (resultList.Count < edges.Count)
        {
            if (nextIndex < 0)
            {
                for (int i = 0; i < edges.Count; i += 2)
                {
                    if (!visited.ContainsKey(i))
                    {
                        nextIndex = edges[i];
                        break;
                    }
                }
            }

            for (int i = 0; i < edges.Count; i += 2)
            {
                if (visited.ContainsKey(i))
                    continue;

                int j = i + 1;
                int k = -1;
                if (edges[i] == nextIndex)
                    k = j;
                else if (edges[j] == nextIndex)
                    k = i;

                if (k >= 0)
                {
                    var edge = edges[k];
                    visited[i] = true;
                    edgeList.Add(nextIndex);
                    edgeList.Add(edge);
                    nextIndex = edge;
                    i = 0;
                }
            }

            // calculate winding order - then add to final result.
            var borderPoints = new List<Point>();
            edgeList.ForEach(ei => borderPoints.Add(positions[ei]));
            var winding = CalculateWindingOrder(borderPoints);
            if (winding > 0)
                edgeList.Reverse();

            resultList.AddRange(edgeList);
            edgeList = new List<int>();
            nextIndex = -1;
        }

        return resultList;
    }




    /// <summary>
    /// returns 1 for CW, -1 for CCW, 0 for unknown.
    /// </summary>
    public static int CalculateWindingOrder(IList<Point> points)
    {
        // the sign of the 'area' of the polygon is all we are interested in.
        var area = CalculateSignedArea(points);
        if (area < 0.0)
            return 1;
        else if (area > 0.0)
            return - 1;        
        return 0; // error condition - not even verts to calculate, non-simple poly, etc.
    }

    public static double CalculateSignedArea(IList<Point> points)
    {
        double area = 0.0;
        for (int i = 0; i < points.Count; i++)
        {
            int j = (i + 1) % points.Count;
            area += points[i].X * points[j].Y;
            area -= points[i].Y * points[j].X;
        }
        area /= 2.0f;

        return area;
    }
Источник

Код обхода (неэффективный - нужно привести в порядок, в какой-то момент дойдет до него). Обратите внимание: я храню каждый сегмент в цепочке как 2 индекса, а не как 1, как предложил Даррен. Это чисто для моих собственных нужд реализации / рендеринга.

        // okay now lets sort the segments so that they make a chain.

        var sorted = new List<int>();
        var visited = new Dictionary<int, bool>();

        var startIndex = edges[0];
        var nextIndex = edges[1];

        sorted.Add(startIndex);
        sorted.Add(nextIndex);

        visited[0] = true;
        visited[1] = true;

        while (nextIndex != startIndex)
        {
            for (int i = 0; i < edges.Count - 1; i += 2)
            {
                var j = i + 1;
                if (visited.ContainsKey(i) || visited.ContainsKey(j))
                    continue;

                var iIndex = edges[i];
                var jIndex = edges[j];

                if (iIndex == nextIndex)
                {
                    sorted.Add(nextIndex);
                    sorted.Add(jIndex);
                    nextIndex = jIndex;
                    visited[j] = true;
                    break;
                }
                else if (jIndex == nextIndex)
                {
                    sorted.Add(nextIndex);
                    sorted.Add(iIndex);
                    nextIndex = iIndex;
                    visited[i] = true;
                    break;
                }
            }
        }

        return sorted;
Источник

Ответ на ваш вопрос на самом деле зависит от того, как треугольная сетка представлена ​​в памяти. Если вы используете структуру данных Half-edge , то алгоритм предельно прост, так как все уже было сделано при построении структуры данных Half-edge.

  1. Начать с любого граничного полуребраHE_edge* edge0(его можно найти линейным поиском по всем полуребрам как первое ребро без допустимогоface). Установить текущее полуреброHE_edge* edge = edge0.
  2. Выведите пункт назначенияedge->vertтекущего края.
  3. Следующее ребро по часовой стрелке вокруг формы (и против часовой стрелки вокруг окружающего «отверстия») будетedge->next.
  4. Остановитесь, когда достигнетеedge0.

Для эффективного перечисления граничных ребер в обратном порядке (против часовой стрелки) структура данных должна иметьprevполе данных, которое предоставляют многие существующие реализации структуры данных Half-edge в дополнение кnext, например MeshLib

Источник
Другие вопросы по тегам