Оптимизация честной Z-сортировки
12.07.2007 Антон ВолковТрижды переписывали алгоритм сравнения полигонов.
Всё успешно разрулили, причём ещё остались возможности для будущей оптимизации.
Появились нюансы — сортировка точек и рёбер с самим телом объекта.
10.09.2007 в 13:42
Привет Антон!
Интересно как вы сравниваете треугольники ? по каким критериям? и как вообще устроена «честная сортировка»? хотя бы принцип.
Я занимался созданием 3d движков еще с 6го флеша, скажу сразу, что лучшая оптимизация — логическая. Во всяком случае мне кажется не стоит сравнивать все треугольники друг с другом т.к. при 1000 треугольниках (а это совсем немного треугольников) , будет 1000*1000 сравнений! Думаю будет тормоз полнейший, и никакая оптимизация на флеш-асемблере не поможет. Конечно это мое личное мнение, но имея большой опыт я так считаю.
15.09.2007 в 06:39
Привет! Насчёт 1000000 сравнений абсолютно верно. Оптимизаций целый ряд, порядка 6 этапов. Главное в оптимизации — не считать то, что считать не надо или уже не надо, потому что и так ясен результат. Вот и начинаем, сначала смотрим разбивку по секторам (http://blog.alternativaplatform.com/ru/files/2007/08/realsortingboundmap.swf), поэтому остаётся уже уже не 1000, а пара десятков сравнений. Потом проверяем границы (так называемые boundbox), далее путём нахождения точки в полуплоскости начинаем проверять пересечения. Дальше идут оптимизации в духе «если слой полигона не изменился, ничего не делать» и так далее.
17.09.2007 в 13:49
Привет! Да! Это конечно новый подход! Я тоже думал что без боундинг боксов не обойтись! Я вот думаю может вам сделать BSP дерево? может это поможет ? ведь у вас же очень огромный мир… да еще надо бы сюда LOD т.к. при удалении камеры от объекта можно ухудшить качество текстуры да и самой геометрии и должно не дать косметического эффекта…
И еще хотел спросить у вас для каждого полигона отдельный спрайт? Или вы рисуете все в один спрайт?
17.09.2007 в 14:25
С BSP возились, но нам этот вариант не подходит. Во-первых, из-за часто изменяемой геометрии (в мире постоянно будут происходить анимация объектов), а во-вторых из-за необходимости делить полигоны.
О LOD уже думали, но это пока не требуется, да и за 3D-движок слабо зацеплено. Достаточно будет подменять 3D-модели при подгрузке с сервера при переключении зума.
Да, для каждого полигона отдельный Shape, ведь в любой момент может произойти Z-сортировка и перерисовывать всё заново неэффективно.