Статьи Королевства Дельфи
в пределах которого лежат вершины,
Обычно примитив относят к тому узлу, в пределах которого лежат вершины, образующие примитив. К какому из узлов отнести треугольник в данном случае? Казалось бы, взять да и отнести его к узлу I. Но так делать нельзя, и вот почему. Предположим, что мы связали треугольник с узлом I - тогда, если в процессе рендеринга мы определили, что узел I не виден, то и треугольник выведен не будет. Однако при этом возможна ситуация, когда узлы II и III будут в пространстве вида - полигон "выпадет" из сцены. Для избежания этого примитив относят к узлу, если хотя бы одна вершина примитива находится в пределах узла. В данном случае при таком подходе один и тот же треугольник будет ассоциирован с узлами I, II и III. В принципе, это не так уж страшно, так как данные можно индексировать, и этим избежать значительных расходов памяти. Однако в процессе рендеринга, если видны все три узла, полигон придётся вывести три раза. А это уже неприятно. Тем более, что такой полигон обычно не один, их множество.
Кое-где пишут, что это не так страшно, но я не согласен. Если такой примитив, например, покрыт большой текстурой, скорость вывода упадёт в несколько раз. Да и вообще, такие КрамольныЕ мысли в интерактивной графике недопустимы! Поэтому я поступил так: если примитив не полностью лежит в узле, его индекс заносится в отдельный массив. В процессе рендеринга ведётся учёт всех отрисованных "дробных" примитивов в специальном буфере, и если при выводе данного треугольника его индекс совпадёт с одним из индексов в буфере, мы не рисуем этот треугольник. Как показал опыт, помечать примитивы не так уж медленно, гораздо более медленно выводить геометрию три-четыре раза подряд.
Всё бы хорошо, да с делением примитива есть ещё одна проблема. Допустим, узлы I, II и III не видны. Однако узел IV может всё же попадать в поле зрения камеры, и видно, что частичка полигона всё же может выпасть, вот так:
Рисунок 3. Полигон выпал
Что делать? Очевидно, что нельзя относить примитив к узлу, ориентируясь только на факт принадлежности вершины примитива к этому узлу. Наверное, все же вместо этого надо проверять, проходит ли РЕБРО примитива через пространство узла. Это может потребовать гораздо больше времени при построении дерева, но зато мы избежим выпадения полигонов. Кстати, структуру один раз построенного дерева можно записать в файл, и уже больше не строить его каждый раз при старте программы, а загружать из файла. В приведённом случае полигон придётся отнести ко всем четырём узлам.
Второй недостаток octree-дерева - это вывод всех объектов, находящихся в поле viewing frustum, но на самом деле в конечном счёте невидимых. Например, стена кухни может закрывать бутылки с кетчупом, но они всё равно будут отсылаться на конвейер (так как находятся в области viewing frustum), и fps будет низким. По-видимому, чистым octree-based алгоритмом здесь не обойтись, необходимо дополнительно реализовать так называемый Z-buffer, например, на тайловой основе. Коротко его работу можно описать так:
- Разбиваем проектную плоскость на некоторое число прямоугольников (тайлов), размером, например 32х32 пикселя.
- Если некий примитив полностью закрывает собой этот тайл, записываем в этот тайл среднее z-значение данного примитива
- При выводе очередного узла определяем, находятся ли его лицевые грани полностью в пределах тайла. Если это так и z-значение ближайшей вершины узла-куба больше z-значения тайла, то узел является скрытым, а значит, вся его геометрия тоже скрыта.
