- L
- Участник
Вопрос к тем, кто работал с такими структурами данных как KD-tree, BVH-tree и т.п.
В дипломной работе я реализовал(не полностью) придуманный мною алгоритм по реструктуризации пространственных деревьев. Планировал об этом статейку написать, но перед этим хотелось бы убедиться - придумал ли я что-то новое или же очередной велосипед)
Просмотрел несколько англоязычных документов по данной тематике - похожего не нашел. Буду очень признателен тем, кто уже видел или работал с подобным методом и скинет ссылку на его описание.
Краткое описание алгоритма есть в прилагаемом по ссылке документе. Там же парочка прог.
[file=55802]
сплошные крякозябры в тексте, что в приложении, что в readme
У меня все нормально открылось, кроме *.doc - на тачке нет офиса (да да - уныло )
Насчет метода ничего не могу сказать.
Но вот что сцена динамическая можно сказать лишь с трудом - дикие тормоза.
Тут была демка, от кого уже не помню, там можно было выжать 60фпс. А тут.... Ну правда кол-во лучей 2280256, при этом один кадр считает 00:00:526 - а в динамике вообще жуть. (3Gb Ram, 512DDR3 9600GT, 2*3Ghz Athlon, Win7)
16bit
> сплошные крякозябры в тексте, что в приложении, что в readme
у меня всё в норме о_О
Divait_Fir
> В дипломной работе я реализовал(не полностью) придуманный мною алгоритм по
> реструктуризации пространственных деревьев. Планировал об этом статейку
> написать, но перед этим хотелось бы убедиться - придумал ли я что-то новое или
> же очередной велосипед)
А в чём собсно профит? Демка жутко тормозит. Видел реализации с 50+ФПС на моей машине на такойже по сложности сцене. А тут на глаз 2-3 ФПС
это у меня английская win7 видимо не понимает русский немножко :) вот и крякозябры.
Не очень понял описание, читал немного поверхностно, но как правило всех инетресует работа с мешами и кол-во треугольников хотя бы несколько сот тысяч а лучше миллион-два.
А при том количестве шариков которое наблюдается в сцене можно просто заново перестроить. Двигаются опять же только шарики.
Если метод поддерживает движение целых мешей и позволяет не перестраивать kd-tree для них то гуд. То тогда соответственно и демку надо с более весомой геометрией.
fzr125
В демке скорее всего рейтресинг на GPU был.
А я в readme.txt писал, что на процах intel намного быстрее будет)
.L
Я и не говорю что у меня сама трассировка крутая. По скорости она почти такая же, как и изначальный исходник. Суть работы не в том, чтобы ускорить трассировку, а в том, чтобы при изменении сцены не перестраивать все дерево, в котором сцена содержится. Это позволит выполнять трассировку, что в динамических сценах, что в статических примерно с одной и той же скоростью.
FROL
> А при том количестве шариков которое наблюдается в сцене можно просто заново перестроить.
Справа в проге отображается - скока времени затрачивается на создание дерева, а скока не перестроение. В данном примере время создания примерно в 3 раза больше, чем время перестроения. Хоть и небольшая, но уже выгода.
Как я уже говорил – метод еще не полностью реализован, да и скорость построение kd-дерева не оптимизирована. К тому же, скорее всего использование BVH-дерева дало бы большую скорость. Так что в приведенном примере лишь малая часть возможной скорости. Пока-что прога лишь показывает, что данный подход работает.
> Если метод поддерживает движение целых мешей и позволяет не перестраивать kd-tree для них то гуд.
Метод позволяет перестраивать в Kd-дереве только тот небольшой участок, где меши будут передвигаться.
Если использовать еще и метод двухуровневой трассировки лучей, то тогда шарики можно заменить мешами с n-ым количеством треугольников. В таком случае, если меши не будут менять свою структуры, а только перемещаться, то скорость перестроения дерева не уменьшится. Если же структуру мешей надо как-то изменять, то для ускорения перестроения именно деревьев мешей можно использовать еще какой-нибудь метод. Например, на форуме есть такой вариант: http://www.gamedev.ru/code/forum/?id=121411.
Подводя итог – оба метода (двухуровневая трассировка лучей и предварительный расчет кластеров треугольников) предназначены для ускорения перестроения деревьев самих мешей, в то время как предложенный мною метод предназначен для перестроения именно дерева сцены (в листьях которого храняться уже не треугольники, а меши). Таким образом он может дополнять их, позволяя добиться еще большей скорости.
Ну это здорово тогда, но нужно какую-то сцену более представительную - хотя бы Sponza, а в ней двигающиеся объекты.
Или фея. Фот у нее же есть анимация даже просчитанная.
По хорошему надо бы, конечно. Но на доработку уйдет еще не один месяц. Пока для диплома было нужно - делал, а щас мотивации то уже и нету.
Тема в архиве.