Алгоритм преобразования вершин треугольной полосы в многоугольник - PullRequest
Новая
       60

Алгоритм преобразования вершин треугольной полосы в многоугольник

9 голосов
/ 20 августа 2010

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

OpenGL = совместимо, см. http://en.wikipedia.org/wiki/Triangle_strip

Пример: для этой полосы http://en.wikipedia.org/wiki/File:Triangle_Strip_Small.png Мне нужен выход A B D F E C или A C E F D B

Ответы [ 3 ]

6 голосов
/ 20 августа 2010

Я считаю, что должно работать следующее:

Прогулка по списку вершин. Добавьте первую точку к вашему многоугольнику. Нажмите на вторую точку в стеке. Добавьте третью точку к многоугольнику. Продолжайте чередовать перемещение точек в стеке и добавление их в многоугольник, пока не дойдете до конца списка. Когда вы дойдете до конца списка, вытолкните точки стека и добавьте их в многоугольник.

1 голос
/ 20 августа 2010

alt text

Я предполагаю, что ваша треугольная полоса всегда подключена одинаково (что, я считаю, верно для OpenGL).

  • "Нижние" вершинывсегда два разнесенных: A, C, E, ...
  • "Верхние" вершины всегда две раздельные: B, D, F, ...

Взять "нижний список и добавьте обратную сторону «верхнего» списка.(ACEFDB для примера)

Или, точнее, используя индекс на основе нуля вместо букв: 

// do "bottom"
for ( i = 0; i < N; i += 2 )
  addVertex( i )

// do "top"
largestOddNumberLessThanN = N % 2 == 0 ? N - 1 : N - 2;
for ( i = largestOddNumberLessThanN; i >= 0; i -= 2 )
  addVertex( i )
0 голосов
/ 20 августа 2010

Может быть ярлык, если ваша фигура имеет особенно простую структуру, но в целом я думаю, что вы хотите сделать следующее

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