Комментарии 9
навязнувший, встроенка - вы тогда и словарь к статье бы прикрепили.
С некоторым опозданием до меня дошло, что DDA всё-таки не то же самое, что модифицированный Брезенхем… тем более спасибо.
UPD: DDA, Брез Модифицированный или вообще «наивный» алгоритм (который каждый раз вычисляет самый короткий остаток до линии и шагает на него) — в любом случае всё вышеописанное должно работать одинаково, потому что важен только порядок проверки столбцов, а он у них всех в направлении от камеры к точке лимита длины луча.
я не особо в теме, просто давно это видео находил, вдруг что полезное.
Так и вышло :) Статья, по сути, не про рэйкаст в 2D, а про то, как к имеющемуся прикрутить синей изолентой третью ось. И уточнение про DDA действительно более чем полезное — вероятно, для шейдеров DDA больше подходит, чем БМ, потому что БМ требует ветвлений в момент шага по меньшей дельте, а DDA так и прёт вперёд, как целеустремлённый слон :) А я что-то зациклился в своём Брезе, потому что он для CPU практически идеален, и особо нос не высовывал за его пределы, а для отладки вообще обычно наивный алгоритм использую (дебажить удобно, координаты всегда точные и лежат одновременно на луче и на границе блоков).
А, блин! Когда задумался и пересмотрел видео — вспомнил, что уже маялся этими муками выбора и быстро понял чисто аналитически, что любые алгоритмы с константным шагом в принципе не могут работать, потому что всегда найдётся достаточно маленький уголок, который они пропустят!
Поэтому DDA в этом видео такой же модифицированный, как и Брезенхем (там DDA с ярко выраженными элементами наивного алгоритма). Проще говоря, у него нет преимущества перед БМ на шейдерах — у него тоже ветвлений полно.
Ох, чует моё сердце, надо закодить и во всём разобраться уже всерьёз, потому что сразу приходит на ум алгоритм с чередующимися константными шагами…
Можно добавить к карте дополнительное значение - расстояние до ближайшего не пустого блока (по типу signed distance field), тогда можно будет пропускать сразу несколько пустых блоков и быстрее приходить к занятому. Либо организовать все в виде octree, там не только можно пропускать большие пустые блоки, но и упрощать детализацию на больших расстояниях, но деревья в шейдеры запихать будет сложнее (все же Хуанг их как-то хранит).
SDF пробовал в прямом рэйкасте, скорость даже почти терпимая стала (кроме каста параллельно плоским структурам), но после каждого изменения блока будет пересчитываться пол-мира :(
Октальники — это да, я не просто так их упоминаю пол-статьи :) Не обязательно именно octree, можно ведь и перепрыгнуть уровень, сделав грубую карту с укрупнением 8² (не на 2, а на 4 по каждой координате), ну или ещё как-то под свою конкретику сделать какой-то свой октальник, идейно близкий к octree, но не в точности им являющийся :)
Как я не добился 60 fps на дистанции 256 чанков на Lenovo X201i