13.4. Алгоритм Аппеля (Количественная невидимость)

Рассмотрим произвольное гладкое выпуклое тело в пространстве. Взяв произвольную точку Р на границе этого тела, назовем ее лицевой, если (n,l)>0, где n - вектор внешней нормали к границе в этой точке. Если же (n,l)<0, то данная точка является нелицевой (и, соответственно, невидимой). В силу гладкости поверхности у лицевой (нелицевой) точки существует достаточно малая окрестность, целиком состоящая из лицевых (нелицевых) точек и проектирующаяся на картинную плоскость взаимнооднозначно (не закрывая саму себя) (рис. 13.4.1).

    У точек, для которых (n,l) = 0, подобной окрестности (состоящей только из лицевых или только нелицевых точек) может не существовать. Такие точки, в отличие от (регулярных) точек называются нерегулярными (особыми) точками проектирования (рис. 13.4.2).

Рис. 13.4.1. Пример регулярных точек.                Рис 13.4.2. Пример НЕрегулярных точек.

В общем случае множество всех нерегулярных точек (n,1) = 0 образует на поверхности рассматриваемого объекта гладкую кривую, называемую контурной линией. Эта линия разбивает поверхность выпуклого тела на две части, каждая из которых однозначно проектируется на картинную плоскость и целиком состоит из регулярных точек. Одна из этих частей является полностью видимой, а другая – полностью невидимой.

Попытаемся обобщить этот подход на случай одного или нескольких невыпуклых тел.

Множество всех контурных линий (их уже может быть несколько) разбивает границы тел на набор связных частей (компонент), каждая из которых по-прежнему взаимнооднозначно проектируется на картинную плоскость и состоит либо из лицевых, либо из нелицевых точек.

Никакая из этих частей не может закрывать себя при проектировании, однако возможны случаи, когда одна такая часть закрывает другую. Чтобы это учесть, введем числовую характеристику невидимости – так называемую количественную невидимость точки, определив ее как количество точек, закрывающих при проектировании данную точку. Точка оказывается видимой только в том случае, когда ее количественная невидимость равна нулю.

Количественная невидимость является кусочно-постоянной функцией и может изменять свое значение лишь в тех точках, проекции которых на картинную плоскость лежат в проекции одной из контурных линий.

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

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

Рассмотрим теперь изменение количественной невидимости вдоль самой контурной линии.

Можно показать, что она может измениться только в двух случаях – при прохождении позади контурной линии и в точках сборки. В первом случае происходит загораживание складкой другого участка поверхности и количественная невидимость изменяется на два. Во втором случае происходит загораживание поверхностью самой себя и количественная невидимость изменяется на единицу.

Таким образом, для определения видимости достаточно найти контурные линии и их проекциями разбить всю картинную плоскость на области, являющиеся видимыми частями проекций объектов сцены.

В результате мы приходим к следующему алгоритму: на границах тел выделяется множество контурных линий С. Каждая из этих линий разбивается на части в тех точках, где она закрывается при проектировании на картинную плоскость какой-либо линией этого множества, проходящей в точке закрывания ближе к картинной плоскости. Контурные линии разбиваются и в точками сборки. В результате получается множество линий, на каждой из которых количественная невидимость одна и та же (постоянна).

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

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

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

Его с успехом можно применить и для работы с полигональными объектами. Одним из вариантов такого применения является алгоритм Аппеля.

Аппель вводит понятие количественной невидимости QI (quontative invisibility) точки как число лицевых граней, ее закрывающих. Это несколько отличается от определения, введенного ранее, однако существо подхода остается неизменным.

Контурная линия полигонального объекта состоит из тех ребер, для которых одна из проходящих граней является лицевой, а другая – нелицевой.

Так, для многогранника на рис. 13.4.3 контурной линией является ломаная ABCIJDEKLGA.

Рассмотрим, как меняется количественная невидимость вдоль ребра.     Для определения видимости ребер произвольного многогранника сначала берется какая-либо его вершина и ее количественная невидимость определяется непосредственно.

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

Следующим шагом является определение количественной невидимости для ребер, выходящих из новой вершины, и т. д.

Рис. 13.4.3. Пример лицевых и нелицевых граней.

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

В случае, когда рассматривается изменение количественной невидимости вдоль ребра, выходящего из вершины, принадлежащей контурной линии, необходимо проверить, не закрывается ли это ребро одной из граней, выходящей из этой вершины (как, например, грань DEKJ закрывает ребро DJ, и это является аналогом точки сборки).

Так как для реальных объектов количество ребер, входящих в контурную линию, намного меньше общего числа ребер (если общее количество ребер равно n, то количество ребер, входящих в контурную линию, – О(√n )), алгоритм Аппеля является более эффективным, чем алгоритм Робертса.

На поверхности многогранников можно выделить набор линий такой, что каждая контурная линия независимо от направления проектирования обязательно пересечет хотя бы одну из линий этого набора. Таким образом, для отыскания контурных линий необязательно перебирать все ребра – достаточно проверить заданный набор и восстановить контурные линии от точек пересечения с этим набором.

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