17.5. ОДНОРОДНОСТЬ ЭЛЕМЕНТОВ ИЗОБРАЖЕНИЯ ПО НАБЛЮДАЕМОСТИ

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

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

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

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

Однородность объекта по наблюдаемости. Наблюдаемость некоторого объекта часто можно определить, рассматривая некоторое описывающее его тело, форма которого может быть весьма простой, — это может быть сфера или многогранник с гранями, параллельными координатным плоскостям. Это некоторое обобщение идеи, использованной для определения пересечения многоугольников в разд. 15.6, и применяться оно может целым рядом способов. Так, например, можно упростить шаг 4 алгоритма

17.2, заведя отдельный список для диапазонов изменения значений у (максимальное и минимальное значения) для каждого объекта. Можно, например, использовать однородность объекта по наблюдаемости в алгоритме 17.1 для уменьшения начального размера списка L. И, наконец, использование этого вида однородности по наблюдаемости может облегчить определение отношений затенения поверхностей, о чем шла речь в подразд. 17.2.2.

Однородность строк развертки по наблюдаемости. Сегменты, которые видны в одной строке, вероятно, видны и в следующей строке развертки. Если имеется оценка минимального размера объекта, то можно задать значение К и изменить алгоритм 17.2 следующим образом. После обработки и воспроизведения строки развертки пропускаются строк и очередной обрабатываемой строкой служит Если одни и те же отрезки видны на обеих строках, обозначим через множество граней, которым эти отрезки принадлежат. После этого для пропущенных строк формируется массив С, причем используются лишь грани, принадлежащие множеству Затем К строк развертки воспроизводятся одновременно. (Можно полностью обойти решение задачи разделения видимых и невидимых элементов для промежуточных строк при помощи интерполирования разбиений, заданных на строках

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

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

Геометрическая однородность по наблюдаемости. Число допустимых видимых и невидимых конфигураций для каждой вершины ограничено.

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

Рис. 17.8. Пример использования геометрической однородности по наблюдаемости: а — если изображенные ребра принадлежат некоторому выпуклому объекту, то два крайние ребра должны быть видны; б — если изображенные ребра принадлежат некоторому выпуклому объекту, то все ребра, окружающие некоторую вершину, характеризуются одной и той же наблюдаемостью

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

Рис. 17.9. Определение межкадровой однородности объекта по наблюдаемости; на всех трех кадрах грани и характеризуются одной и той же наблюдаемостью

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

Рис. 17.10. Примеры нетривиальных случаев разделения видимых и невидимых элементов сцены: а — для установления наблюдаемости недостаточно определения экстремальных значений по координате необходимо сопоставление точек и — две плоские поверхности взаимно загораживают друг друга

Следует отметить, что в нетривиальных случаях многие простые методы решения задачи разделения видимых и невидимых элементов сцены не срабатывают Так, на рис 17.10, а приведен пример случая, когда учет экстремального значения координаты оказывается недостаточным. Если Р — точка, принадлежащая пересечению проекций двух отрезков прямых, то для определения наблюдаемости достаточно сравнить лишь точки и проектирующиеся в точку Р. Этот метод можно использовать и в тех случаях, когда обе грани являются выпуклыми плоскими областями. Если же поверхности плоские, но невыпуклые области, то анализ случаев типа, приведенного на рис. 17.10, б, должен носить более детальный характер. Объем вычислений, необходимый для обработки неплоских поверхностей, еще больше, чем в случае плоскостей. Упростить задачу можно с помощью разбиения конечных участков поверхности, ограниченных замкнутыми кривыми, на меньшие конечные участки.