Обход графа про peano-like кривой.
От: _Winnie Россия C++.freerun
Дата: 17.01.06 11:27
Оценка:
Есть полигональная модель из треугольников.
Построим граф, где вершины — это треуголькники, а ребра между ними — это связи между треугольниками из полинональной модели.

то есть вот такая модель из четрырех треугольников

|\
| \
|  \ 
|   \
|____\
|\    \    
| \   |\   
|  \  | \  
|   \ |  \ 
|____\|___\


Прератится в такой граф из чытырех:

   |
   |
   |
  / \
 /   \



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

Это нужно для оптимизации порядка вывода треугольников под post-TNL кеш видеокарты, но неизвестного заранее размера.

модель изначально в виде :

Треугольник — это три целых числа (индекс вершины в другом массиве, в которой лежат позиция, цвет, нормаль и тд).
Например, квадрат из двух треугольников — это
{ { 0, 1, 2 } { 1, 0, 3 } }


PS. Вот кривая пеано, кстати —
http://rsdn.org/File/23256/peano_curve.png]

Спасибо!
Правильно работающая программа — просто частный случай Undefined Behavior http://rsdn.org/File/23256/catsmiley.gif
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.