Другие журналы

научное издание МГТУ им. Н.Э. Баумана

НАУКА и ОБРАЗОВАНИЕ

Издатель ФГБОУ ВПО "МГТУ им. Н.Э. Баумана". Эл № ФС 77 - 48211.  ISSN 1994-0408

Использование свойств связности изображения в алгоритмах удаления невидимых поверхностей

#1 январь 2005

манипулятора возникает обратная проблема — ввиду бопьшой продолжительности выполняемых операций исследователь нуждается в уско

Ю.А. Кондрашин, К.П. Саблин, В.Ю. Судзиловский, канд. физ-мат. наук, МГГУ “Станкин”

 

Использование свойств связности изображения в алгоритмах удаления невидимых поверхностей

 

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

 

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

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

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

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

Несмотря на столь широкое разнообразие методов, И.Е. Сазерленду [1] представилось возможным выделить два свойства, присущие всем алгоритмам: использование связности и сортировки, причём сортировка является основной проблемой. Действительно, в результате работы алгоритма удаления невидимых поверхностей графические объекты рассортировываются на два основных класса: видимые и невидимые объекты.

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

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

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

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

Рис. 1. Определение граничных ребер

Если обозначить (для случая параллельного проецирования) вектор проецирования v(xv, yv, zv) вектор плоскости n(xn, yn, zn), то для потенциально видимой плоскости должно выполняться условие:

xvxn + yvyn + zvzn < 0,                                           (1)

а для потенциально невидимой -

xvxn + yvyn + zvzn > 0.                                           (2)

Случай f(v, n) = 0 можно отнести к любому из представленных выше случаев. Следовательно, для граничного ребра должно выполняться условие:

f(v, n1) f(v, n2) < 0                                                       (З)

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

Рис. 2. Построение очерковой линии

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

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

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

Если ссылки ещё не расставлены, то существует простой способ их проставления (простановка ссылок должна выполняться ещё на предварительном этапе - при подготовке модели к обработке). Для этого нет необходимости проводить поиск для каждого ребра на предмет соответствия его отдельной грани. Гораздо проще и быстрее просмотреть все грани, и для каждого ребра грани выставить обратную ссылку. В результате каждое правильное ребро будет иметь по две ссылки на различные грани. Таким образом можно ещё проверить и правильность модели - если существуют рёбра только с одной ссылкой или будет попытка добавить третью ссылку к ребру, модель неверна.

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

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

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

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

Рис. 3. Сравнение граничных плоскостей

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

Рис. 4. Построение картинной плоскости при параллельном проецировании

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

Для вычисления расстояния от требуемой точки p с координатами (x, y, z) до картинной плоскости следует подставить координаты точки в выражение

         (4)

где A, B, C, D - коэффициенты картинной плоскости. Для случая представления уравнения плоскости в

нормализованном виде выражение (4) упрощается до вида

d = (Ax + By + Cz + D).                                               (5)

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

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

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

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

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

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

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

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

 

Литература

1. Sutherland I.E., R.F. Sproull and R.A. Schumaher A Characterization of Ten Hidden-Surface Algorithms. // ACM Computing Surveys, 6(1), March 1974, P. 1-55.

ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ, 3. 1997

КОМПЬЮТЕРНАЯ ГРАФИКА И МОДЕЛИРОВАНИЕ

Поделиться:
 
ПОИСК
 
elibrary crossref ulrichsweb neicon rusycon
 
ЮБИЛЕИ
ФОТОРЕПОРТАЖИ
 
СОБЫТИЯ
 
НОВОСТНАЯ ЛЕНТА



Авторы
Пресс-релизы
Библиотека
Конференции
Выставки
О проекте
Rambler's Top100
Телефон: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)
  RSS
© 2003-2020 «Наука и образование»
Перепечатка материалов журнала без согласования с редакцией запрещена
 Тел.: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)