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

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

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


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

   |
   |
   |
  / \
 /   \



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

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

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

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


PS. Вот кривая пеано, кстати —
]

Спасибо!
Правильно работающая программа — просто частный случай Undefined Behavior
Re: Обход графа про peano-like кривой.
От: Trean Беларусь http://axamit.com/
Дата: 17.01.06 12:42
Оценка:
Здравствуйте, _Winnie, Вы писали:

_W>Есть полигональная модель из треугольников.

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

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


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

_W>Путь может рваться, на произвольном графе из треугольников этого не избежать, но минимальное число раз.

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


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


_W>Треугольник — это три целых числа (индекс вершины в другом массиве, в которой лежат позиция, цвет, нормаль и тд).

_W>Например, квадрат из двух треугольников — это
_W>{ { 0, 1, 2 } { 1, 0, 3 } }

_W>Спасибо!


В инете полно исходников, поищи по Hilbert curve.
Re[2]: Обход графа про peano-like кривой.
От: _Winnie Россия C++.freerun
Дата: 17.01.06 13:07
Оценка:
Здравствуйте, Trean, Вы писали:

T>В инете полно исходников, поищи по Hilbert curve.

Кроме названия темы и картинки надо было прочитать и текст между ними.
Между прочим, картинку я сам нарисовал, я это умею —
void draw(int deep, float ax, float ay, float bx, float by, float sign)
{
    float hx = bx/2, hy = by/2;
    float px = sign*hy, py = -sign*hx;
    if (deep == 0)
        return glVertex2f(ax + hx + px, ay + hy + py);
    draw(deep-1, ax, ay, px, py, -sign);
    draw(deep-1, ax+px, ay+py, hx, hy, sign);
    draw(deep-1, ax+px+hx, ay+py+hy, hx, hy, sign);
    draw(deep-1, ax+bx+px, ay+by+py, -px, -py, -sign);
}


Мне надо построить такую запутанную кривую на графе из треугольков, который вовсе не квадратно-гнезовая сетка.
Правильно работающая программа — просто частный случай Undefined Behavior
Re[3]: Обход графа про peano-like кривой.
От: Trean Беларусь http://axamit.com/
Дата: 17.01.06 13:25
Оценка:
Здравствуйте, _Winnie, Вы писали:

_W>Здравствуйте, Trean, Вы писали:


T>>В инете полно исходников, поищи по Hilbert curve.

_W>Кроме названия темы и картинки надо было прочитать и текст между ними.

Читал, но видно либо объяснили не понятно, либо одно из двух

_W>Мне надо построить такую запутанную кривую на графе из треугольков, который вовсе не квадратно-гнезовая сетка.


Если не квадратно-гнездовая, то не плохо было бы узнать по какому принципу организован кэш. И почему запутанная кривая должна дать выигрыш в бытсродействии. Кривая гильберта ведь не случайно была выбрана, если просто абстрактную запутанную кривую нарисовать, то ничего получится. Определись какая запутанная кривая должна быть для начала, свойства какие у нее.
Re[4]: Обход графа про peano-like кривой.
От: WolfHound  
Дата: 17.01.06 16:30
Оценка:
Здравствуйте, Trean, Вы писали:

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

Что тут не понятного? Есть произвольная сетка из треугольников. Ее надо разбить на минимальное колличество triangle strip'ов.
... << RSDN@Home 1.1.4 beta 6a rev. 436>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[5]: Обход графа про peano-like кривой.
От: Рома Мик Россия http://romamik.com
Дата: 17.01.06 20:00
Оценка:
Здравствуйте, WolfHound, Вы писали:

WH>Здравствуйте, Trean, Вы писали:


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

WH>Что тут не понятного? Есть произвольная сетка из треугольников. Ее надо разбить на минимальное колличество triangle strip'ов.
А "запутанность" зачем? Почему бы не обойтись требованием минимального числа разрывов?
... << RSDN@Home 1.2.0 alpha rev. 622>>
Re[6]: Обход графа про peano-like кривой.
От: WolfHound  
Дата: 17.01.06 20:21
Оценка:
Здравствуйте, Рома Мик, Вы писали:

РМ>А "запутанность" зачем? Почему бы не обойтись требованием минимального числа разрывов?

Это ты у меня спрашиваешь? Я думаю просто _Winnie плохо сформулировал вопрос.
Впрочем чего гадать подождем автора вопроса.
... << RSDN@Home 1.1.4 beta 6a rev. 436>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[5]: Обход графа про peano-like кривой.
От: Trean Беларусь http://axamit.com/
Дата: 18.01.06 07:46
Оценка:
Здравствуйте, WolfHound, Вы писали:

WH>Здравствуйте, Trean, Вы писали:


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

WH>Что тут не понятного? Есть произвольная сетка из треугольников. Ее надо разбить на минимальное колличество triangle strip'ов.

Полагаю, но не уверен, что на произвольной сетке точного полиномиального алгоритма не будет, кроме того такой алгоритм на большом меше быстро работать не будет, даже динамическое программирование не спасет, которое тут можно попробовать применить.
На мой взгляд можно вполне обойтись обычным рандомным depth-first search, отсеивая пройденные вершины и листья (если меш не замкнут).
Re[6]: Обход графа про peano-like кривой.
От: WolfHound  
Дата: 18.01.06 10:18
Оценка:
Здравствуйте, Trean, Вы писали:

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

T>На мой взгляд можно вполне обойтись обычным рандомным depth-first search, отсеивая пройденные вершины и листья (если меш не замкнут).
1)Для подовляющего числа игр время (в приделах часа на современной машине) не имеет значения ибо модель можно обсчитать один раз на компьютере разработчика.
2)Подойдет хорошой приближонный алгоритм ибо пара лишних стрипов на большой модели погоды не сделают.
3)_Winnie недооценил сложность задачи ибо разбить сетку на стрипы задача болие сложная чем просто пройтись по графу.
... << RSDN@Home 1.1.4 beta 6a rev. 436>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[5]: Обход графа про peano-like кривой.
От: _Winnie Россия C++.freerun
Дата: 19.01.06 04:17
Оценка:
WH>Здравствуйте, Trean, Вы писали:

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


Не, мне нужны не стрипы, мне нужны triangle-листы

И мне интересна теоретика кайфа — не оптимизация под кеш конретного размера(они разные у разных видеокарт), а под кеш заранее неизвестного размера.
Дело в том, что когда я обхожу меш треугольниками, последние N вершин (точнее, результат применения к ним освещения и трансформации — Transform and Lighting — TNL) запоминаются в FIFO буфер. (новая вершина вытесняет старую, они могут дублироваться — если старая такая же есть, то новая всё равно добавится и самая старая вытолкнется). И если в очередном треугольнике какие-то вершины есть уже в кеше, то результат вычисления TNL берётся из кеша, а не считается заново.

Например, стрипы — это как бы такой очень специальный кеш, но только размером ровно в две вершины.

Если кеш фиксированного размера — то оптимальное решение для такого квадрата это обходить его "змейкой" шириной в половину кеша.

Для кеша размеров в 8 лучше обходить так —

 _  _  _  
|1/|3/|5/|
|/2|/4|/6|
|7/|9/|B/|
|/8|/A|/C|
   ...
   ...
   ...
   ...

У треугольников 7,9,B результы вычисления всех трёх вершин будут братся из кеша.
чем так —
 _  _  _  _  _  _  _  
|1/|3/|5/|7/|9/|B/|D/| ...............
|/2|/4|/6|/8|/A|/C|/E| ...............


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

На квадратной сетке, где каждый квадрат составлен из двух треугольников её легко построить, а вот на произвольном меше...

ХМ. я вроде ставил галочку "Получать ответы по e-mail", но мне пришло только одно письмо. Я и не знал, что тут от меня просят уточнить
Правильно работающая программа — просто частный случай Undefined Behavior
Re[6]: Обход графа про peano-like кривой.
От: Trean Беларусь http://axamit.com/
Дата: 19.01.06 08:35
Оценка:
Здравствуйте, _Winnie, Вы писали:

_W>И мне интересна теоретика кайфа — не оптимизация под кеш конретного размера(они разные у разных видеокарт), а под кеш заранее неизвестного размера.

_W>Дело в том, что когда я обхожу меш треугольниками, последние N вершин (точнее, результат применения к ним освещения и трансформации — Transform and Lighting — TNL) запоминаются в FIFO буфер. (новая вершина вытесняет старую, они могут дублироваться — если старая такая же есть, то новая всё равно добавится и самая старая вытолкнется). И если в очередном треугольнике какие-то вершины есть уже в кеше, то результат вычисления TNL берётся из кеша, а не считается заново.

Если я правильно понял, надо так организовать обход графа, чтобы по максимуму использовать вершины лежащие в кэше и добавлять новые в него по-минимуму? (Код Грея что-то напоминает :)

С кэшем я не совсем понял. FIFO буфер и кэш это разные вещи (если одно и тоже тогда не понятно, почему вершины могут дублироваться)? Все вершины треугольника добавляются в очередь? По какому принципу обновляется кэш.
По подробнее этот момент освятите.
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.