jm
'Раньше' - ето когда Quake ходил по земле? Тогда ведь опять z-buffer прикрутили, софтуернъй.
tav
Ещё можно прикрутить постобработку полигонов - если на полигоне какие-то точки расположены очень уж близко друг к другу - можно их просто объединить
Я, если позволите, тоже хочу пять копеек своих вставить, т.к. запарился уже искать инфу.
Все дело в том, что мне нужен BSP для рейтрейсинга. Я долго искал в сети исходники, но в итоге плюнул, собрал все свои силёнки и написал сам. Работает он только с треугольными мешами. Как минимум его отличие от геймовых BSP в том, что полигоны он не рассекает - это для рейтрейсинга неэффективно, а добавляет треугольнички в подузлы, с которыми пересекается. А ещё все секущие плоскости в нем параллельны координатным - это упрощает и ускоряет определение принадлежности одного треугольника тому или иному подпространству.
Сейчас встала такая проблема: у меня в алгоритме реализована проверка, определяющая порядок пересечения полупространств трассирующим лучом. Этот кусок целиком опирается на процедуру нахождения точек "входа" и "выхода" трассирующего луча в/из узла (BoundingBoxа узла дерева). Она у меня, видимо, не совсем корректно работает в сложных ситуациях (на простых я всё отлаживал - всё ок). Так вот у меня просьба: есть ли у кого-нибудь исходник на C такой процедуры. Желательно грамотно написанной с точки зрения производительности, т.к. она всё-таки при рендеринге вызывается очень часто :)
Короче, формализация задачи такая:
1. Есть точка A и вектор B, определяющие трассирующий луч. Параметрически: R(t) = A + B * t;
2. Есть параллелипипед, ребра которого параллельны осям координат. Задается точками двух углов (верхнего дальнего левого и т.п......) - P1, P2
Нужно получить значения параметра t (t1,t2), при которых указанный луч "входит" в бокс (t1) и выходит из него (t2).
Разумеется, t1 и t2 могут быть и отрицательными - но это уже мои проблемы.
Помогите, плиз. Я доделаю и исходники выкину. Они на C++
Я так и не понял, то есть при БСП З-Буффер все равно используется?
И еще, тогда веть придется отказатся от glDrawElements и рисовать потреугольно, так?
Zemedelec
>jm
>'Раньше' - ето когда Quake ходил по земле? Тогда ведь опять z-buffer
>прикрутили, софтуернъй.
ну да вобщем то... История как никак. А про квак я и сказал что там софтверный z-buffer пару сообщений назад...
FLashM
>Я так и не понял, то есть при БСП З-Буффер все равно используется?
>И еще, тогда веть придется отказатся от glDrawElements и рисовать потреугольно,
>так?
Все равно используется. Не используется только на голом node bsp.
Ээээ почему потреугольно ?
Нужно не рисовать потреугольно, а пополигонно тогда уж, собирая индексы с попавших в видимость узлов.
Zloy
Я же говорил, что что я только не пробовал. Алгоритм должен был быть по идее бузупречным. Да и пост обработка была (если расстояние между соседними вершинами < epsilon они объединялись, пытался не epsilon, а 0.1f брать -- ничего не помогало), и еще куча-куча всяких тестов -- ошибку все-равно не нашел, а с хранением нормалей все заработало, почему-то.
Zlobnyi Serg
Ну неужели так трудно было сделать классический BSP. Надо обязательно в какие-то дебри лезть.
Про обычный BSP повсюду статей немало (да и вот, тут вроде еще одну статью про не только классический BSP обсуждаем вроде). Он же для трассировки лучей идеально подходит -- не помню какой там traversal, короче от точки начала луча (считаем её как бы глазом) рекурсивно ищем пересечение со всеми полигонами. Учитывая специфику BSP-дерева ПЕРВЫЙ полигон, с которым нашли пересечение -- искомый, т.е. ближний к началу луча. (Я, кстати, таким образов лайтмепы делал, до реалтайма, конечно, далеко, но скорость терпимая)
А насчет пересечения BBOX'а чего проще. Например для верхней плоскости:
bool BBOXHitRay(vector3f &start,vector3f &end,vector3f &intersection) { k=( start.z-maxZ)/( start.z-end.z); ix=start.x-( start.x-end.x)*k; iy=start.y-( start.y-end.y)*k; if ( ix>minX && ix<maxX && iy>minY && iy<maxY && start.z>maxZ) {intersection.set( ix,iy,maxZ); return true;} ...
Ну я примерно написал, так что может не работать.
tav
А что "неклассического" ты заметил в моей реализации BSP? Рассекать полигоны - весьма неэффективное занятие, как мне кажется, для рей-трейсинга. Ну может мой способ выбора секущей плоскости (которая всегда перпендикулярна одной из осей координат) немного и выпадает из определения "классического BSP", но зато в моем случае гораздо быстрее можно произвести трассировку луча.
Весьма некорректно твое высказываение насчёт "специфику BSP-дерева ПЕРВЫЙ полигон, с которым нашли пересечение -- искомый, т.е. ближний к началу луча". - Этого быть не может потому что этого не может быть, как говорил наш препод по матану :) Один узел (leaf) BSP-дерева может содержать N полигонов(треугольников), и, естественно, они не могут быть упорядочены по отношению к любому лучу в пространстве, который нам, возможно, придется трассировать.
В этом смысле у БСП есть только такой уровень оптимизации (зависящий, кстати, от точек пересечения с BBOX :)):
1. Трассировать только левый узел
2. Трассировать только правый узел
3. Трассировать сначала левый, потом правый (или наоброт: правый, левый) - здесь подразумевается, что обладая информацией об упорядоченности узлов если мы находим пересечение луча с каким-л. полигоном левого узла, то правый из рассмотрения исключаем.
4. Трассировать оба, выбирая ближайший к точке испускания луча полигон.
И вот он у меня криво работает.... :) Если я заменяю рассмотрение этих 4 условий просто вызовом рекурсивного трассировщика у обоих детей, то всё корректно начинает считатся (только раза в 1.5 медленнее). Как только использую if... - полигоны начинают выпадать :(
Zlobnyi Serg
Тъ прав, разсекать в твоем случае ненадо - также как и для колижена. Иногда разсекать не надо даже и для рендеринга.
А ето твое назъвается kd-tree, что есть частнъй случай BSPT.
А разве не надо трасировать сначала ближайший под-узел, а ЕСЛИ в нем или в его детях пересечения нет, ТОЛЬКО тогда запускать рекурсию в дальний под-узел...?
tav
Стандартное BSPT страдает неточностями, расечениями и т.д. Иногда ето ненужно, именно в случаях трасировки луча и колизии.
Zemedelec
Я именно это и написал, рассматривая 4 случая... :)
Ещё мой BSP долго строится, гад :( Секунды 2-3 для 32000-полигональной модели статуэтки Будды... Зато трейсит потом 1.06 сек.
Zlobnyi Serg
>Этого быть не может потому что этого не может быть, как говорил наш препод по матану
Не понял шутки. Ну не повезло с преподом, и что теперь (или повезло, смотря как смотреть).
Еще здесь непонятливые есть. Я же сказал классическое BSP-дерево.
>Один узел (leaf) BSP-дерева
КАКОЕ ЕЩЕ leaf BSP. Или я неправильно понимаю, что такое классическое BSP.
Ты мне еще давай рассказывать, что без Z-буфера нельзя отображать leaf BSP. А то я не знаю:-) .
НО Я ГОВОРИЛ НЕ О LEAF bsp. Самое обычное БИНАРИ СПЕЙС ПАРТИШН. И у нём ПЕРВОЕ пересечение с любым полигоном узла, ЕСЛИ ПРАВИЛЬНО РЕКУРСИВНО ПРОХОДИТЬ, есть пересечение с искомым полигоном. Я этой фишкой 1000 раз пользовался: и при генерации лайтмэпов, и при нахождении пересечения луча курсора мыши с полигонами BSP-дерева.
Zemedelec
>Стандартное BSPT страдает неточностями, расечениями и т.д. Иногда ето ненужно, именно в случаях трасировки луча и колизии.
Мне, почему-то кажется, наоборот. Если видны НА ЭКРАНЕ щели между полигонами, то это нехорошо. А при трасировке луча, особенно со сверхопросом и при выборе маленького критического угла для определения принадлежности точки пересечения луча и плоскости полигона самому полигону (например градусов 358) -- все нормально будет. С коллизиями тоже, в принципе. Надо, просто делать расчет на бОльшую погрешность, чем без делений.
tav
(leaf) - это относится к слову "узел" и является его синонимом в английской терминологии описания BSP. Ни о каких leaf-bsp речи не шло :)
ПЕРВОЕ пересечение с любым полигоном узла - всегда правильное, судя по твоим словам. Оно может быть правильным ТОЛЬКО в том случае, если в любом узле дерева содержится не более 1 полигона :) В противном случае - как бы ты правильно ни пытался его проходить: рекурсивно, при помощи стека - не важно как, я для любого узла, содержащего более 1 различных полигонов подберу такой луч, что твоя версия нахождения пересечения даст неправильный результат.
А вообще, мне кажется мы спорим совсем о разных вещах, чего делать не стОит. Вобщем говоря, для того дерева, что построил Я, такое твое утверждение будет неверным. А загвоздка здесь в том, что мои секущие плоскости выбираются не из полигонов в сцене, а являются параллельными координатным плоскостям - так мне гораздо удобнее производить трассировку. Возможно, в играх этим не пользуюся, но я пишу это для НЕ-реалтайм-рендеринга и судя по исследованиям в диссертации некоторых людей, сбалансированное k-d tree (типа BSP, только плоскость секущая обладает теми свойствами, что я уже описывал + ось сечения и позиция выбирается минимизацией некоторой оценочной функции) является наиболее быстрым и эффективным для трассировки луча. (По кр. мере на том тестовом наборе в 32 сцены с различными уровнями детализации).
tav
Ну, не знаю, что у тебя там и как, но я никогда и не мыслил полигонов без хранения уравнения их плоскости в виде:
struct plane_eqt { float nvect[3]; float D; };
А попадания точек на секущую плоскость лучше проверяй во время разбиения
Плюс есть еще один нюанс - "ложное пересечение" полигона сплитовой плоскостью. Это когда из-за всяческих неточностей мы получаем более двух пересечений плоскости с рёбрами выпуклого полигона, хотя грамотные люди понимают, что такого быть не может. Но это если пытаться уменьшить количество сплитов путём отлова точек, попадающих на плоскость сечения.
Zlobnyi Serg
>Вобщем говоря, для того дерева, что построил Я, такое твое утверждение будет неверным.
Так я про то и говорил, что лучше делать классическое Node BSP. (Я там везде слово Node пропустил)
>Оно может быть правильным ТОЛЬКО в том случае, если в любом узле дерева содержится не более 1 полигона :)
Что за бред? Как раз наоборот, если полигоны, лежащие на секущей плоскости запихивать там в левую/правую ветвь, то непонятно что получится, а так мы имеем классическое Node BSP, в каждом узле хранятся: уравнение делящей плоскости, ВСЕ полигоны, лежащие на этой плоскости (их может и не быть -- плоскость произвольная), их кол-во и ссылки на 2 поддерева.
Как искать пересечение луча и ПОЛИГОНА (НЕ плоскости) я объяснять не буду. Ну какая разница сколько полигонов в узле 1 или несколько. Перекрываться-то они не могут, а если и могут -- какая разница? Ты статью читал? Там же даже написано, что при front-to-back traversal (мне удобнее это называть -- Near-To-Far) -- перекрытия пикселей НЕ будет (при использовании Z-буффера), что означает, ЧТО ПЕРВЫЙ ПИКСЕЛЬ, КОТОРЫЙ МОЖНО НАРИСОВАТЬ (В СООТВЕТСТВИИ С Z-БУФЕРОМ) НЕ БУДЕТ ПЕРЕРИСОВЫВАТЬСЯ. То есть если нарисовали мы полигон, то он БЛИЖАЙШИЙ. Объяснять я, конечно плохо умею. Ты автора статьи спроси. Можт он лучше объяснит.
Пересечение луча рекурсивно ищется таким же образом, как и рендер Node BSP (описан в статье). Только вместо рисования ВСЕХ ПОЛИГОНОВ В ДЕЛЯЩЕЙ ПЛОСКОСТИ, мы ищем пересечение луча с ДЕЛЯЩЕЙ ПЛОСКОСТЬЮ (используя ее уравнение).
Затем ЭТУ точку пересечения проверяем на ПРИНАДЛЕЖНОСТЬ КАЖДОМУ ПОЛИГОНУ УЗЛА.
А вот какая реализация эффективнее (KD-BSP vs Node BSP) -- это уже другой вопрос.
jm
Вопрос по статье.
>не следует использовать BSP алгоритмы для открытых пространств
А почему? Ну leaf BSP согласен. А если с NodeBSP. Кстати, а как в UT-2003 сделано. Динамич. ландшафтом там и не пахнет, зато открытых пространств....
>jm
>Вопрос по статье.
>>не следует использовать BSP алгоритмы для открытых пространств
>А почему? Ну leaf BSP согласен. А если с NodeBSP. Кстати, а как в UT-2003
>сделано. Динамич. ландшафтом там и не пахнет, зато открытых пространств....
А ты попробуй прикинуть почему не стоит - представь себе ландшафт к примеру...
Кроме того, мне вот кажется что leaf+pvs для открытых пространств как раз быстрее будет...
В ут честно говоря не знаю. Вряд ли bsp... Хотя в статье я написал "вероятно bsp" :)
Скорее всего портальный движок и возможно octree...
Тема в архиве.