Подсчет количественной невидимости. Алгоритм Аппеля

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

Как изменяется количественная невидимость вдоль A B

ребра? Естественно, рассматриваются только потенциально

видимые ребра, т.е. перед работой алгоритма выполняется D C

тест видимости. Количественная невидимость точек ребра

изменяется на единицу при прохождении ребра позади кон- F E

турной линии. Контурная линия состоит из ребер, для кото- G H

рых одна из составляющих ребро граней видима (лицевая),

другая - нет. На рисунке контурной является ломаная J I

ABCIJDEKLGA. L K

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

Работа алгоритма начинается с выбора какой-либо вершины многогранника и определения ее количественной невидимости. Для этого через эту точку и точку наблюдения проводится отрезок прямой и находятся пересечения этого отрезка со всеми гранями (как в тесте глубины DT1). Число найденных граней - количественная невидимость начальной точки. Далее прослеживается изменение количественной невидимости вдоль каждого из ребер, выходящих из этой вершины. Эти ребра проверяются на прохождение позади контурной линии, что изменяет количественную невидимость. Части отрезка с нулевой количественной невидимостью сразу рисуются. Далее выбирается вершина, образуемая одним из рассмотренных ребер. Для нее количественная невидимость подсчитана, процесс повторяется. Как опреде-

лить пересечение рассматриваемого ребра с контур-

ным? Аппель предлагает

контурное ребро

следующее. Образуется тре-

угольник, вершинами которого являются точка наб-

людения и концы исследуемого ребра. Контурное ре- q + 1

бро изменяет коли

наблюдатель

чественную невидимость ребра q,

если оно “протыкает” треугольник, т.е. точка пере-

сечения контурного ребра с плоскостью треугольни- q

исследу- емое ребро

ка лежит внутри треугольника. Если пересечение

существует, количественная невидимость q увели-

чивается на 1 при положительном знаке векторного

произведения контурного и рассматриваемого ребер и уменьшается на 1 в противном случае.

По сравнению с алгоритмом Робертса алгоритм Аппеля более быстр, т.к. число ребер, входящих в контурную линию, намного меньше общего числа ребер.

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

Дата добавления: 2014-01-11