Выбор объектов.

После таких сложных тем как машина состояний ОГЛ и VBO решил выбрать для рассмотрения что-то попроще, но не менее важное для графического движка., такое как банальный выбор объекта мышкой. Не смотря на повседневность этой задачи тут также есть свои нюансы, которые мы с вами и рассмотрим.

Всего существует две принципиально разные технологии выбора объектов, одна предполагает что объект будет "выбираться" аппаратно (на стороне GPU), вторая - программно (на CPU). Рассмотрим обе из них, их достоинства и недостатки.
Суть технологии выбора на GPU заключается в том, чтоб отрендерить все объекты, используя вместо цвета специальный идентификатор объекта, в результате, прочитав цвет пикселя под курсором, мы можем узнать идентификатор объекта, по которому можем вернуть объект. Достоинства такого подхода - простота реализации, точность выбора, работает со всеми типами объектов. Недостатки тут тоже имеются:

• Мы обязаны попасть в "пиксель" объекта, если попасть в "дырку от бублика", то мы не определим попадание или выберем объект находящихся за "бубликом";
• Необходимость отрендерить всю сцену дважды (один раз в основной буфер кадра, второй раз в специальный буфер выбора или FBO), чтоб на экране присутствовали все объекты и в нужном порядке. Не смотря на то, что вывод в буфер выбора осуществляется без расчета освещенности, без настроек смешивания и без текстурирования (текстуры и блендинг могут быть использованы чтоб избежать следующей проблемы) всеравно происходит некоторое падение производительности, и тем выше, чем сложнее сцена;
• Проблема с альфатестом - если используется текстура с "дыркой" (альфа равна нулю) при включенном альфатесте вы не будете видеть этот кусок, но при заполнении буфера выбора - он будет заполнен идентификатором объекта. Для решения этой проблемы может потребоваться передавать еще и текстуру в шейдер и вручную обрабатывать такой момент;
• Проблема с прозрачностью - вы не можете выбрать объект, находящийся за полупрозрачным объектом (к примеру оконным стеклом). Решается путем исключения таких объектов из цикла рисования в буфер выбора;
• Проблема с выбором нескольких объектов под курсором;
• Проблема с выбором нескольких объектов рамкой (если хоть один пиксель попадет в область выбора - объект будет выбран.

Со времен первых версий OpenGL и до OpenGL 3.0 эта задача решалась при помощи специальных команд и так и называемого буфера выбора (Selection Buffer). 
Подробности можно узнать к примеру тут:
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 и может выполняться в отдельном потоке пока рендерится сцена.

Как видите - список преимуществ весьма внушающий, но есть и недостатки, названные чуть выше - можно применять только к геометрии находящейся в системной памяти (можно конечно осуществлять проверку в геометрическом шейдере или через рендеринг геометрии в текстуру, но это выходит за рамки данной статьи). Как следствие - нам нужно в оперативной памяти держать копию всей геометрии, мало того - для ускорения поиска нам нужно еще и построить октри по этой геометрии, которое так же занимает место в оперативной памяти и требует время на генерацию/загрузку. Еще один недостаток - через рейкаст мы не можем отбросить полупрозрачные объекты или объекты с альфатестом (можно получить ID  материала для полигона под курсором, можно получить текстурные координаты для этой точки, можно вытащить из материала/текстуры информацию о прозрачности пикселя, но это потребует существенно больше оперативной памяти и усложнит алгоритм поиска, привязав октри к системе материалов, что совсем нежелательно). 

Но есть и альтернатива, помните в чем был основной недостаток подхода с буфером вывода? Правильно, в необходимости дважды выводить всю геометрию сцены. Комбинируя эти два подхода можно на первом этапе, за счет грубой проверки по AABB, отбросить всю геометрию, которая заведомо не попадет в область выбора, изменить размер вьюпорта (или указать обрезку) чтоб он соответствовал выбираемой области (снизить филлрейт) и применить первый вариант, с проверкой альфатеста или попиксельной проверкой. При таком подходе мы получим максимальное соотношение производительности и точности, к тому же этот подход прекрасно работает для геометрии хранимой в видеопамяти или рассчитываемой на GPU (нужно только ее AABB для грубого отсечения). Недостатки - несколько усложняется код, так как нужно реализовать и работу с FBO/шейдерами и работу с октри. Так как обе этих возможности присутствуют в большинстве движков, то нужно лишь написать алгоритм проверки, состоящий из описанных этапов.


Если посмотреть на GLScene, то мы так же обнаружим там два варианта, первый вариант, аппаратный, реализован посредством буфера выбора средствами ОГЛ 1.х и отдельно есть возможность произвести рейкаст по объектам сцены по направлению курсора (координаты и вектор получаем сами). Октри используется лишь для фриформы, в остальных случаях используется либо точное значение, полученное через математические функции (куб, сфера, конус, плоскость) либо приближенные, через окаймляющую сферу (додекаэдр, икосаэдр и т.д.). 
Имеется возможность реализовать рендеринг в текстуру (FBO) и имеется возможность построить октри для мешей и имеются шейдера, так что есть все необходимое для реализации способа смешанного выбора. 


Из минусов - октри позволяет определить только объект с которым было пересечение и точку пересечения, невозможно определить какому MeshObject принадлежит точка пересечения (попали в актера а не в руку актера). Октри генерируется очень долго и нет возможности сохранить сгенерированное дерево в файл. Проблемы поиска пересечений с базовыми объектами (отсутствует или через окаймляющий бокс/сферу).


В VBOMesh изначально предполагалось наличие геометрии для всех объектов, таким образом проблемы с рейкастом не было. Изначально использовался модуль Octree из GLScene, но в процессе работы некоторые ограничения (скорость генерации, расход памяти, невозможность сохранить/загрузить результат, отсутствие возможности поиска по мешам, отсутствие детальных данных о точке пересечения) привели меня к необходимости написания своей модификации модуля октри, где я решил названные проблемы. В частности было сделано:

• Ускорение генерации октри, уменьшение занимаемой памяти и ускорения поиска за счет пропуска пустых ветвей дерева;
• Ускорение поиска за счет подгонки размера ветви к реальному размеру данных в ветви;
• Исключение двойного поиска для полигонов, принадлежащих разным ветвям октри одного уровня за счет копирования этих объектов в отдельный список проверки;
• Три типа поиска пересечений - поиск по массиву треугольников (аналог сценовского октри), поиск по списку мешей - для каждого меша строится свое октри, это позволяет уменьшить количество проверяемых полигонов в рамках одного меша и ускорить проверку за счет возможного откидывания отдельных мешей по их AABB без по-полигонной проверки и поиск до первого нахождения пересечения (если нужно определить сам факт пересечения); 
• Есть возможность сохранить и загрузить сгенерированное дерево октри, что существенно ускоряет процесс подготовки сцены. 

Говоря о возможностях самого рейкаста, то есть возможность осуществить рейкаст только по AABB объектов и есть возможность узнать с каким конкретно мешем объекта произошло пересечение. Так же можно получить полный список объектов, с которыми произошло пересечения и получить информацию по ближайшей точке пересечения. Преобразование экранных координат курсора в пару положение-вектор при выборе объекта производится автоматически ( так же позицию и вектор можно указать явно). Имеется возможность делать выборку объектов из прямоугольной области, это реализовано двумя способами: через проекцию узлов AABB на плоскость экрана и определение попадания в прямоугольник выделения и через проверку попадания узлов или геометрического центра в усеченную пирамиду, образованную проекцией прямоугольной области выделения в глубину сцены. По производительности оба метода примерно одинаковые и позволяют мгновенно выбирать тысячи объектов.

Выбор через буфер цвета не реализован, так как по моему мнению он неоправданно дорогой и может быть легко реализован пользователем, с учетом его потребностей и используемых им шейдеров или эффектов. Для этого в модуле имеется поддержка и FBO и шейдеров.

В будущем возможно реализую описанный ранее смешанный способ выбора объектов.

Так же интерес представляет выбор объектов посредством геометрического шейдера, в этом случае можно обойтись достаточно простым геометрическим шейдером, получающим на вход отрисовываемые треугольники и "на лету" делая для них рейкаст. Такой подход решает проблему динамической геометрии (морфинг, скелетная анимация, частицы). К сожалению это ограничивает круг пользователей обладателями новых видеокарт, потому пока это так же не входит в возможности движка, но так же может быть легко реализовано с использованием существующих средств.

В настоящее время я стараюсь избегать использования шейдеров внутри движка, связанно это с невозможностью к одному объекту прикрепить два шейдера и нет штатных средств для объединения нескольких эффектов в один шейдер. Это очень серьезная проблема, но о ней мы поговорим в следующий раз.