Введение
В статье рассматривается несколько точных методов деления уровня на секторы, а также предлагается приблизительный “корпускулярный” метод.
Благодарности: огромное спасибо Zemedelec’у (Сергею Милойкову) за разрешение представить в приложении описание двух его методов, а также за полезные/ценные советы.
1. Понятия портала и сектора
Прежде чем говорить о каких-то методах и математических алгоритмах, попытаемся определить сами понятия портала и сектора.
Чтобы было полегче, представим себе следующую картинку: посреди поляны стоит хижина без крыши. Подойдите к любому человеку, покажите ему эту картинку и попросите выделить на ней два сектора. В ответ человек гарантированно разграничит то, что внутри хижины и то, что снаружи.
Почему так происходит? Что делает эти две области секторами?
Как мне кажется, самый легкий способ “формально” ответить на этот вопрос – это выразить понятие сектора через понятие портала.
Итак, сектор – это связная пустая замкнутая область, ограниченная статической геометрией и порталами. На нашей картинке секторами являются, как и следовало ожидать, внутренность хижины и пространство вокруг нее. Проиллюстрируем приведенное выше определение на внутренности хижины:
1) Внутренность хижины связная (т.е. не имеет изолированных друг от друга участков).
2) Внутренность хижины пустая.
3) Внутренность хижины замкнута, т.е. ограничена статической геометрией (стены, пол) и порталами (дверь и отсутствующая плоская крыша).
Но при таком раскладе остается главный вопрос – что же такое портал? А вот определение портала мне вывести не удалось. Максимум, что получается, звучит примерно так: портал – это объект, связывающий два сектора. Но такое определение бессмысленно, так как мы уже определили сектор через портал.
Поэтому я думаю так: портал – это объект, интуитивно воспринимаемый человеком как связывающий две области. Т.е. портал становится понятием нижнего уровня, вроде понятия множества в математике. Как следствие, здесь я не буду приводить каких-то мыслей по поводу поиска порталов и предположу, что они задаются дизайнерами на этапе моделирования.
2. Поиск границы сектора
Если дизайнер уже выделил порталы на этапе моделирования, то на плечи программиста возлагается единственная задача: определить, на какие сектора оказался разделен уровень. Посмотрим на выведенное нами определение. Сектор – это область. Что значит задать область? В математике это значит задать (можно неявно, в виде уравнения) функцию, описывающую границу области.
Посмотрим на обычный BSP-алгоритм: мы строим для созданного уровня BSP-дерево, потом описываем вокруг уровня ограничивающий куб и «спускаем» его по дереву вниз. Когда процесс «спускания» окончен, собираем висящие на листьях объедки и склеиваем их в сектора.
Фактически, BSP-алгоритм находит плоскости, ограничивающие сектор. Иными словами, он неявно, в виде набора уравнений задает функцию, описывающую границу сектора. То есть BSP-алгоритм формально, в классическом смысле задает область, которой является сектор. Есть еще два интересных алгоритма, позволяющих определить границу сектора (автор обоих – Zemedelec), их описания представлены в приложении.
3. Поиск множества точек: “корпускулярный” метод winter’а
Но что делать, если нам не нужно задавать границы секторов точно? Что если мы все равно собираемся описать вокруг каждого сектора ограничивающий куб и в дальнейшем использовать для всех проверок только его?
Тогда поиск точной границы сектора оказывается избыточной операцией. Остается единственный вариант. Еще раз вспоминаем определение: сектор – это область. А что есть область, если отвлечься от ее границы? Множество точек.
Сущность “корпускулярного” метода заключается в том, чтобы приблизительно задать множество точек, принадлежащее сектору, и описать ограничивающий куб вокруг этого множества.
Хорошее приближение для точки в трехмерном пространстве – это, как известно, аксиальный (с гранями, параллельными главным осям) кубик. Тогда общий контур алгоритма будет выглядеть так:
1) Берем некоторый портал. Предположим, что это абстрактный четырехугольник.
2) Строим по обеим сторонам от портала два маленьких кубика заданного размера.
3) Для каждого кубика:
а) Определяем, попадает ли в него какая-либо геометрия или порталы (поскольку кубик аксиальный, проверка проходит очень быстро).
б) Если кубик пуст, для него строятся “соседи”.
4) Повторяем шаг 3) до тех пор, пока поток новых кубиков не иссякнет.
5) Описываем вокруг каждого множества кубиков большой ограничивающий куб (если сектор велик, можно и восьмеричное дерево).
Таким образом, кубики заполняют все внутреннее пространство двух секторов, соединяемых порталом. Этот процесс можно представить себе примерно так: мы запускаем в нашу хижину цемент, который медленно заполняет все ее внутреннее пространство. Потом ждем, пока цемент застынет, “извлекаем” его из хижины и снимаем с него форму.
4. Приложение
А теперь, обещанные точные алгоритмы поиска границы сектора. Автор обоих — Zemedelec (Сергей Милойков).
Метод лучевой маркировки
1) Производим операцию маркировки первый раз: берем некоторый портал и испускаем из него лучи. Находим несколько полигонов, видимых из данного портала; найденные полигоны маркируются как принадлежащие новому сектору.
2) Перебираем таким образом все порталы.
3) Операция маркировки повторяется для только что отмаркированных полигонов – теперь уже они испускают лучи. Если некоторый маркированный полигон, принадлежащий сектору B, “видит” немаркированный полигон A, то полигон A тоже маркируется – приписывается сектору B.
4) Количество маркированных полигонов постепенно растет; когда их станет достаточно много, операция маркировки повторяется для оставшихся немаркированными полигонов.
Т.е. вначале порталы находят несколько полигонов и маркируют их; потом маркированные полигоны находят “собратьев по сектору”; наконец, когда “собратьев” станет достаточно много, их обделенные вниманием товарищи начнут искать, к какому сектору им нужно прибиться. Алгоритм действует по принципу: меньшинству всегда легче увидеть большинство.
Сущность метода лучевой маркировки можно выразить двумя словами: если полигон A “видит” один из полигонов сектора B, то он тоже принадлежит сектору B.
Метод “хождения по ребрам”
Этот метод — самый простой из всех, но и наиболее требовательный к геометрии.
1) Создаем пустой список для полигонов сектора.
2) Выбираем один из полигонов, смежных с порталом, и добавляем его в список.
3) Для каждого полигона из списка добавляем в список полигоны, имеющие с ним общие ребра.
Т.е. мы начинаем от портала и далее “идем” по ребрам, добавляя полигоны в список сектора. Легко видеть, что этот метод при всей своей простоте требует некоторой “связности” геометрии, и поэтому применять его следует осторожно.
Послесловие
Если мой “корпускулярный” алгоритм найдет хоть какой-то отклик в народе, я попытаюсь написать еще одну статью, уже на тему Самой Быстрой Проверки пересечения аксиального кубика и полигона. А пока — спасибо всем тем, кто терпеливо прочитал этот документ. До новых встреч (я надеюсь).