После таких сложных тем как машина состояний ОГЛ и VBO решил
выбрать для рассмотрения что-то попроще, но не менее важное для
графического движка., такое как банальный выбор объекта мышкой. Не
смотря на повседневность этой задачи тут также есть свои нюансы, которые
мы с вами и рассмотрим.
Всего существует две принципиально разные технологии выбора объектов, одна предполагает что объект будет "выбираться" аппаратно (на стороне GPU), вторая - программно (на CPU). Рассмотрим обе из них, их достоинства и недостатки.
Суть технологии выбора на GPU заключается в том, чтоб отрендерить все объекты, используя вместо цвета специальный идентификатор объекта, в результате, прочитав цвет пикселя под курсором, мы можем узнать идентификатор объекта, по которому можем вернуть объект. Достоинства такого подхода - простота реализации, точность выбора, работает со всеми типами объектов. Недостатки тут тоже имеются:
Подробности можно узнать к примеру тут:
http://www.gamedev.ru/code/articles/?id=4174
После выхода OpenGL 3.0 буфер выбора был удален из ядра, потому остался только описанный вариант с использованием внеэкранного буфера цвета (FBO+Shader). Дальше уже идут модификации и оптимизации этого алгоритма, так можно использовать предварительно полученный буфер глубины для решения проблемы выбора нескольких объектов под курсором и повышения производительности (рисуем только то, что видно и что можно выбрать), можно реализовать многопроходный рендеринг, если важно получить все объекты под курсором, особенно в случае полупрозрачных объектов, или добавить проверку на альфатест, чтоб исключить попадание в нежелательные области (к примеру GUI сделано как текстура и выводится как скринквад), можно объединить вывод объекта и заполнения буфера выбора в одном проходе шейдера или совместить эту операцию с другими проходами рендера (Early-Z Pass, Oclussion Culling и т.д.), можно уменьшать разрешение буфера выбора, это позволит снизить филлрейт и сделает выбор объектов более "мягким" и т.д. и т.п., так как все возможности шейдеров в ваших руках. Тем не менее, не смотря на оптимизации, использование буфера выбора может быть неприемлемо, к примеру при выводе ландшафта, который сам по себе является очень "тяжелым" из-за большого количества полигонов, а при использовании буфера цвета его придется выводить дважды. А иногда он просто не заменим, к примеру если нужно вывести скелетную анимацию или сделать морфинг или вывести систему частиц на GPU, тоесть в тех случаях, когда у нас на стороне CPU попросту нет геометрии для реализации проверки по второму способу. Собственно давайте рассмотрим второй способ проверки выбора объекта и его достоинства/недостатки.
Как вы уже наверное догадались - второй способ это использование рейкаста для определения пересечения луча, пущенного из позиции курсора в глубь экрана. В чем преимущества такого подхода:
Но есть и альтернатива, помните в чем был основной недостаток подхода с буфером вывода? Правильно, в необходимости дважды выводить всю геометрию сцены. Комбинируя эти два подхода можно на первом этапе, за счет грубой проверки по AABB, отбросить всю геометрию, которая заведомо не попадет в область выбора, изменить размер вьюпорта (или указать обрезку) чтоб он соответствовал выбираемой области (снизить филлрейт) и применить первый вариант, с проверкой альфатеста или попиксельной проверкой. При таком подходе мы получим максимальное соотношение производительности и точности, к тому же этот подход прекрасно работает для геометрии хранимой в видеопамяти или рассчитываемой на GPU (нужно только ее AABB для грубого отсечения). Недостатки - несколько усложняется код, так как нужно реализовать и работу с FBO/шейдерами и работу с октри. Так как обе этих возможности присутствуют в большинстве движков, то нужно лишь написать алгоритм проверки, состоящий из описанных этапов.
Если посмотреть на GLScene, то мы так же обнаружим там два варианта, первый вариант, аппаратный, реализован посредством буфера выбора средствами ОГЛ 1.х и отдельно есть возможность произвести рейкаст по объектам сцены по направлению курсора (координаты и вектор получаем сами). Октри используется лишь для фриформы, в остальных случаях используется либо точное значение, полученное через математические функции (куб, сфера, конус, плоскость) либо приближенные, через окаймляющую сферу (додекаэдр, икосаэдр и т.д.).
Имеется возможность реализовать рендеринг в текстуру (FBO) и имеется возможность построить октри для мешей и имеются шейдера, так что есть все необходимое для реализации способа смешанного выбора.
Из минусов - октри позволяет определить только объект с которым было пересечение и точку пересечения, невозможно определить какому MeshObject принадлежит точка пересечения (попали в актера а не в руку актера). Октри генерируется очень долго и нет возможности сохранить сгенерированное дерево в файл. Проблемы поиска пересечений с базовыми объектами (отсутствует или через окаймляющий бокс/сферу).
В VBOMesh изначально предполагалось наличие геометрии для всех объектов, таким образом проблемы с рейкастом не было. Изначально использовался модуль Octree из GLScene, но в процессе работы некоторые ограничения (скорость генерации, расход памяти, невозможность сохранить/загрузить результат, отсутствие возможности поиска по мешам, отсутствие детальных данных о точке пересечения) привели меня к необходимости написания своей модификации модуля октри, где я решил названные проблемы. В частности было сделано:
Всего существует две принципиально разные технологии выбора объектов, одна предполагает что объект будет "выбираться" аппаратно (на стороне GPU), вторая - программно (на CPU). Рассмотрим обе из них, их достоинства и недостатки.
Суть технологии выбора на GPU заключается в том, чтоб отрендерить все объекты, используя вместо цвета специальный идентификатор объекта, в результате, прочитав цвет пикселя под курсором, мы можем узнать идентификатор объекта, по которому можем вернуть объект. Достоинства такого подхода - простота реализации, точность выбора, работает со всеми типами объектов. Недостатки тут тоже имеются:
- Мы обязаны попасть в "пиксель" объекта, если попасть в "дырку от бублика", то мы не определим попадание или выберем объект находящихся за "бубликом";
- Необходимость отрендерить всю сцену дважды (один раз в основной буфер кадра, второй раз в специальный буфер выбора или FBO), чтоб на экране присутствовали все объекты и в нужном порядке. Не смотря на то, что вывод в буфер выбора осуществляется без расчета освещенности, без настроек смешивания и без текстурирования (текстуры и блендинг могут быть использованы чтоб избежать следующей проблемы) всеравно происходит некоторое падение производительности, и тем выше, чем сложнее сцена;
- Проблема с альфатестом - если используется текстура с "дыркой" (альфа равна нулю) при включенном альфатесте вы не будете видеть этот кусок, но при заполнении буфера выбора - он будет заполнен идентификатором объекта. Для решения этой проблемы может потребоваться передавать еще и текстуру в шейдер и вручную обрабатывать такой момент;
- Проблема с прозрачностью - вы не можете выбрать объект, находящийся за полупрозрачным объектом (к примеру оконным стеклом). Решается путем исключения таких объектов из цикла рисования в буфер выбора;
- Проблема с выбором нескольких объектов под курсором;
- Проблема с выбором нескольких объектов рамкой (если хоть один пиксель попадет в область выбора - объект будет выбран.
Подробности можно узнать к примеру тут:
http://www.gamedev.ru/code/articles/?id=4174
После выхода OpenGL 3.0 буфер выбора был удален из ядра, потому остался только описанный вариант с использованием внеэкранного буфера цвета (FBO+Shader). Дальше уже идут модификации и оптимизации этого алгоритма, так можно использовать предварительно полученный буфер глубины для решения проблемы выбора нескольких объектов под курсором и повышения производительности (рисуем только то, что видно и что можно выбрать), можно реализовать многопроходный рендеринг, если важно получить все объекты под курсором, особенно в случае полупрозрачных объектов, или добавить проверку на альфатест, чтоб исключить попадание в нежелательные области (к примеру GUI сделано как текстура и выводится как скринквад), можно объединить вывод объекта и заполнения буфера выбора в одном проходе шейдера или совместить эту операцию с другими проходами рендера (Early-Z Pass, Oclussion Culling и т.д.), можно уменьшать разрешение буфера выбора, это позволит снизить филлрейт и сделает выбор объектов более "мягким" и т.д. и т.п., так как все возможности шейдеров в ваших руках. Тем не менее, не смотря на оптимизации, использование буфера выбора может быть неприемлемо, к примеру при выводе ландшафта, который сам по себе является очень "тяжелым" из-за большого количества полигонов, а при использовании буфера цвета его придется выводить дважды. А иногда он просто не заменим, к примеру если нужно вывести скелетную анимацию или сделать морфинг или вывести систему частиц на GPU, тоесть в тех случаях, когда у нас на стороне CPU попросту нет геометрии для реализации проверки по второму способу. Собственно давайте рассмотрим второй способ проверки выбора объекта и его достоинства/недостатки.
Как вы уже наверное догадались - второй способ это использование рейкаста для определения пересечения луча, пущенного из позиции курсора в глубь экрана. В чем преимущества такого подхода:
- Это очень быстрый алгоритм проверки по AABB, который сходу может дать список объектов под курсором;
- За счет грубой проверки через AABB решается проблема с попаданием в "дырку от бублика"
- Можно легко реализовать проверку попадания объектов в область прямоугольной рамки, причем можно контролировать попадание в эту область центра (или центра масс) объекта, что позволяет исключить ложное выделение соседних объектов;
- За счет очень простой проверки по AABB можем отбросить 99% объектов сцены перед точным поиском (рейкастом по полигонам или через буфер вывода);
- Можно исключить еще на этапе проверки AABB все объекты, которые не могут быть выбраны, к примеру тот же ландшафт или другую высокополигональную геометрию;
- Можем легко получить список объектов под курсором;
- Можно легко узнать точные координаты попадания;
- Не нагружает GPU и может выполняться в отдельном потоке пока рендерится сцена.
Но есть и альтернатива, помните в чем был основной недостаток подхода с буфером вывода? Правильно, в необходимости дважды выводить всю геометрию сцены. Комбинируя эти два подхода можно на первом этапе, за счет грубой проверки по AABB, отбросить всю геометрию, которая заведомо не попадет в область выбора, изменить размер вьюпорта (или указать обрезку) чтоб он соответствовал выбираемой области (снизить филлрейт) и применить первый вариант, с проверкой альфатеста или попиксельной проверкой. При таком подходе мы получим максимальное соотношение производительности и точности, к тому же этот подход прекрасно работает для геометрии хранимой в видеопамяти или рассчитываемой на GPU (нужно только ее AABB для грубого отсечения). Недостатки - несколько усложняется код, так как нужно реализовать и работу с FBO/шейдерами и работу с октри. Так как обе этих возможности присутствуют в большинстве движков, то нужно лишь написать алгоритм проверки, состоящий из описанных этапов.
Если посмотреть на GLScene, то мы так же обнаружим там два варианта, первый вариант, аппаратный, реализован посредством буфера выбора средствами ОГЛ 1.х и отдельно есть возможность произвести рейкаст по объектам сцены по направлению курсора (координаты и вектор получаем сами). Октри используется лишь для фриформы, в остальных случаях используется либо точное значение, полученное через математические функции (куб, сфера, конус, плоскость) либо приближенные, через окаймляющую сферу (додекаэдр, икосаэдр и т.д.).
Имеется возможность реализовать рендеринг в текстуру (FBO) и имеется возможность построить октри для мешей и имеются шейдера, так что есть все необходимое для реализации способа смешанного выбора.
Из минусов - октри позволяет определить только объект с которым было пересечение и точку пересечения, невозможно определить какому MeshObject принадлежит точка пересечения (попали в актера а не в руку актера). Октри генерируется очень долго и нет возможности сохранить сгенерированное дерево в файл. Проблемы поиска пересечений с базовыми объектами (отсутствует или через окаймляющий бокс/сферу).
В VBOMesh изначально предполагалось наличие геометрии для всех объектов, таким образом проблемы с рейкастом не было. Изначально использовался модуль Octree из GLScene, но в процессе работы некоторые ограничения (скорость генерации, расход памяти, невозможность сохранить/загрузить результат, отсутствие возможности поиска по мешам, отсутствие детальных данных о точке пересечения) привели меня к необходимости написания своей модификации модуля октри, где я решил названные проблемы. В частности было сделано:
- Ускорение генерации октри, уменьшение занимаемой памяти и ускорения поиска за счет пропуска пустых ветвей дерева;
- Ускорение поиска за счет подгонки размера ветви к реальному размеру данных в ветви;
- Исключение двойного поиска для полигонов, принадлежащих разным ветвям октри одного уровня за счет копирования этих объектов в отдельный список проверки;
- Три типа поиска пересечений - поиск по массиву треугольников (аналог сценовского октри), поиск по списку мешей - для каждого меша строится свое октри, это позволяет уменьшить количество проверяемых полигонов в рамках одного меша и ускорить проверку за счет возможного откидывания отдельных мешей по их AABB без по-полигонной проверки и поиск до первого нахождения пересечения (если нужно определить сам факт пересечения);
- Есть возможность сохранить и загрузить сгенерированное дерево октри, что существенно ускоряет процесс подготовки сцены.
Выбор через буфер цвета не реализован, так как по моему
мнению он неоправданно дорогой и может быть легко реализован
пользователем, с учетом его потребностей и используемых им шейдеров или
эффектов. Для этого в модуле имеется поддержка и FBO и шейдеров.
В будущем возможно реализую описанный ранее смешанный способ выбора объектов.
Так же интерес представляет выбор объектов посредством геометрического шейдера, в
этом случае можно обойтись достаточно простым геометрическим шейдером,
получающим на вход отрисовываемые треугольники и "на лету" делая для них
рейкаст. Такой подход решает проблему динамической геометрии (морфинг, скелетная анимация, частицы). К сожалению это ограничивает круг пользователей обладателями
новых видеокарт, потому пока это так же не входит в возможности движка,
но так же может быть легко реализовано с использованием существующих
средств.
В настоящее время я стараюсь избегать использования шейдеров
внутри движка, связанно это с невозможностью к одному объекту прикрепить
два шейдера и нет штатных средств для объединения нескольких эффектов в
один шейдер. Это очень серьезная проблема, но о ней мы поговорим в следующий раз.
Кхм, ты заставил меня передумать насчет отказа от хранения геометрии на стороне ОЗУ. Думал, что сооружу систему выбора по схеме "рендер в FBO объектов разными цветами, а затем нахождение объекта согласно цвету", но теперь крепко задумался над этим.
ОтветитьУдалитьFantom, пиши еще, очень познавательно выходит. Если никто не комментит - это еще не значит, что никто не читает :)
Хранить геометрию в системной памяти может потребоваться по нескольким причинам, во-первых для рейкаста, во-вторых для физики, в третьих для манипуляции с геометрией (модификация, тесселяция и т.д.), в четвертых - для подгрузки (уровней и прочего).
ОтветитьУдалитьНо и тут можно обойтись без хранения копии, вместо рейкаста - использовать буфер выбора, с предварительным отсечением ненужной геометрии по AABB, для физики - использовать коллайдеры подходящей формы или использовать для этого (как и для рейкаста) низкополигональную копию объекта. Для модификации - можно временно считать геометрию из видеопамяти, модифицировать, перезалить в видеопамять и удалить копию из системной памяти.
Для движка эти техники несколько неудобны (предполагая что пользователь еще что-то может придумать), но под конкретную задачу можно обойтись и без хранения копии в ОЗУ.
"с предварительным отсечением ненужной геометрии по AABB"
ОтветитьУдалитьЗначит, при загрузке нужно считать AABB, а если меш анимированный? Искать максимально возможный AABB из всех кадров всех анимаций? А если заранее неизвестны анимации?
Кстати, с другой стороны, даже если и хранить такую геометрию на ОЗУ, то ситуация с неизвестными скелетными анимациями ставит задачу динамического расчета AABB. Как минимум, когда делается attach анимации к мешу (актеру), и затем хранить полученные AABB применительно к каждому фрейму. Хотя, наверное проще к конкретной анимации...
А если совсем не париться, то рассчитывать AABB для анимированного актера "методом витрувианского человека" :)
Черт, надо это попытаться где-то изобразить или закодить.
"а если меш анимированный?" Для общего случая решения нет, только путем обновления ААВВ по текущей геометрии, но это очень ресурсоемко.
ОтветитьУдалитьНо в некоторых частных случаях, к примеру для актера, можно проверять видимость отдельных суставов - у тебя на каждом кадре есть положение каждого сустава, строишь вокруг них окаймляющую сферу, чтоб захватила натянутую на кость геометрию и делаешь проверку по этой сфере).
Если это анимация по ключевым кадрам, то можно брать матрицы трансформации из ключевых кадров. Если это морфинг (есть два набора геометрии со своими ААВВ), то можно высчитать объединение двух ААВВ (интерполяция не может выйти за пределы этого бокса) и в таком духе.