Logo    
Деловая газета CitCity.ru CITKIT.ru - все об Open Source Форумы Все публикации Учебный центр Курилка
CitForum    CITForum на CD    Подписка на новости портала Море(!) аналитической информации! :: CITFORUM.RU
IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware

22.05.2017

Google
WWW CITForum.ru
С Новым годом!

2004 г.

Алгоритмы триангуляции

Романюк Александр, Сторчак Александр, "Комиздат"

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

Генерация объемных изображений представляет сложную вычислительную задачу, в связи этим на практике выполняют ее декомпозицию. Сложные изображения формируют из фрагментов объектов, для чего их разбивают на составные части. Процесс разбиения поверхности объектов на полигоны получил название тесселяции. Эта стадия на данном этапе развития машинной графики проводится полностью программно вне зависимости от технического уровня 3D-аппаратуры.

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

На практике наиболее часто производится разбиение изображений на треугольники.

Это объясняется следующими причинами:

треугольник является простейшим полигоном, вершины которого однозначно задают грань;

любую область можно гарантировано разбить на треугольники;

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

реализация процедур рендеринга наиболее проста для области, ограниченной треугольником;

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

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

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

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

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

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

Последним этапом является применение алгоритмов сглаживания, которые устраняется ребристость поверхности, эффект Маха.

Сколько треугольников нужно?

При моделировании объекта возникает задача, какое количество треугольников нужно использовать? С одной стороны нужно достичь максимального качества при окончательной визуализации, а с другой снизить нагрузку на процессор и 3D-акселератор. Для снижения нагрузки можно использовать менее детализированную триангуляционную сеть, но при этом качество будет далеко не самым лучшим.

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

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

Триангуляция полигонов

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

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

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

Приведем универсальный алгоритм. Триангуляцию любого полигона можно осуществить по следующему универсальному алгоритму.

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

диагональ является хордой;

диагональ — не хорда, так как внутрь треугольника попадает вершина полигона (в общем случае их может быть несколько).

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

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

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

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

GL_TRIANGLES. Треугольники. Команда рисует серию треугольников, используя тройки вершин v0, v1 и v2, затем v3, v4 и v5 и т.д. Если количество вершин не кратно 3, оставшиеся точки игнорируются. Команду удобно использовать при описании поверхности, которая в результате тесселяции представляется кроме треугольников и другими геометрическими фигурами, например, прямоугольниками. В этом случае треугольники могут быть не соприкасаться между собой. Команда может использоваться для описания всех треугольников полигона, независимо от того, связаны они или нет между собой, однако из-за дублирования информации о координатах общих вершин память используется нерационально.

GL_TRIANGLE_STRIP. Полоса треугольников. Команда рисует серию треугольников, используя вершины в следующем порядке: v0, v1, v2, затем v2, v0, v3, затем v2, v3, v4, и т. д. При таком подходе каждая следующая вершина вместе с двумя предыдущими задает треугольник. Порядок вершин должен гарантировать, что треугольники имеют правильную ориентацию. Полоса может использоваться для формирования части поверхности.

GL_TRIANGLE_FAN. Команда похожа на GL_TRIANGLE_STRIP, но при формировании треугольников используют вершины в таком порядке: v0, v1, v2, затем v0, v2, v3, затем v0, v3, v4, и т. д. Все треугольники имеют общую вершину v0. Команда позволяет разбить n-угольник на n-2 треугольника. Для этого нужно выбрать одну из n вершин полигона и соединить ее с каждой из n-3 несоседних вершин

Поверхности, заданные набором точек

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

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

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

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

Заключение

Алгоритмы триангуляции реализованы во многих профессиональных графических пакетах 3D-моделирования, таких как 3D Studio MAX, OpenGL Optimizer, LightWave и др. Эти пакеты позволяют не только использовать различные алгоритмы для триангуляции, но и добавлять пользователям свои.

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

Размещение рекламы — тел. +7 495 4119920, ICQ 232284597

Подписка на новости IT-портала CITForum.ru
(библиотека, CITKIT.ru, CitCity)

Новые публикации:

24 декабря

CITKIT.ru:

  • Новогодние поздравления
  • Сергей Кузнецов. Цикл Операционные системы: Ностальгия по будущему:

  • Алексей Федорчук. OpenSolaris 2008.11 Release

  • Сергей Голубев:

  • Евгений Чайкин aka StraNNik (Блогометки):

    17 декабря

  • С.Д.Кузнецов. Базы данных. Вводный курс

    10 декабря

    CITKIT.ru:

  • OpenSolaris 2008.11 Release

  • Альтернативные ОС: две грустные истории (С.Кузнецов)
  • Nokia N810 — доведение до ума
  • CitCity:

  • Платформа 2009: заоблачные перспективы Microsoft

    4 декабря

  • Лекция С.Д.Кузнецова Понятие модели данных. Обзор разновидностей моделей данных

    CITKIT.ru:

  • OpenSolaris 2008.11 Release. Первые впечатления

  • Linux vs FreeBSD: продолжим "Священные войны"?

  • Nokia N810 as is

  • Индульгенция для FOSS

  • Друзья СПО'2008

    26 ноября

  • Нечеткое сравнение коллекций: семантический и алгоритмический аспекты

    CitCity:

    CITKIT.ru:

  • Глава из книги А.Федорчука
    Сага о FreeBSD:
  • 19 ноября

  • Проблемы экономики производства крупных программных продуктов

  • Язык модификации данных формата XML функциональными методами

    CITKIT.ru:

  • Главы из книги А.Федорчука
    Сага о FreeBSD:

    Заметки к книге:

  • FreeBSD: монтирование сменных устройств и механизм HAL
  • Текстовый редактор ee

    12 ноября

  • Правило пяти минут двадцать лет спустя, и как флэш-память изменяет правила (Гоц Грейф, перевод: Сергей Кузнецов)

    CITKIT.ru:

  • Главы из книги А.Федорчука
    Сага о FreeBSD:
  • OSS в России: взгляд правоведа (В.Житомирский)

  • Новая статья из цикла С.Голубева "Железный марш":

    29 октября

  • О некоторых задачах обратной инженерии

  • Веб-сервисы и Ruby

  • Тестирование web-приложений с помощью Ruby

    CITKIT.ru:

  • Главы из книги А.Федорчука
    Сага о FreeBSD:

  • PuppyRus Linux - беседа с разработчиком (С.Голубев)

  • Сергей Кузнецов. Заметка не про Linux

    22 октября

  • Обзор методов описания встраиваемой аппаратуры и построения инструментария кросс-разработки

    CITKIT.ru:

  • Сергей Кузнецов. Почему я равнодушен к Linux

  • Глава из книги А.Федорчука
    Сага о FreeBSD:
  • Что надо иметь
    3. Базовые познания

    CitCity:

  • Управление IT-инфраструктурой на основе продуктов Microsoft

    15 октября

  • Методы бикластеризации для анализа интернет-данных

    CitCity:

  • Разъемы на ноутбуках: что они дают и зачем их так много?
  • AMD Puma и Intel Centrino 2: кто лучше?

    CITKIT.ru:

  • Новый цикл статей С.Голубева
    Железный марш:

  • Главы из книги А.Федорчука
    Сага о FreeBSD:

    8 октября

  • Автоматизация тестирования web-приложений, основанных на скриптовых языках
  • Опыт применения технологии Azov для тестирования библиотеки Qt3

    Обзоры журнала Computer:

  • SOA с гарантией качества
  • Пикоджоуль ватт бережет
  • ICT и всемирное развитие

    CitCity:

  • Пиррова победа корпорации Microsoft

    CITKIT.ru:

  • Главы из книги А.Федорчука
    Сага о FreeBSD:

    Статья из архива:

  • Я живу в FreeBSD (Вадим Колонцов)

    Новые Блогометки:

  • Перекройка шаблона Blogger или N шагов к настоящему
  • Blogger. Comment style
  • Screenie или глянцевый снимок экрана

    2 октября

    CITKIT.ru:

  • Сага о FreeBSD (А. Федорчук)

    Zenwalk: пакет недели

  • Банинг — интеллектуальное развлечение (С.Голубев)

    CitCity:

    25 сентября

  • Клермонтский отчет об исследованиях в области баз данных

    CITKIT.ru:

  • Пользователям просьба не беспокоиться... (В.Попов)

  • Снова про ZFS: диск хорошо, а два лучше
  • Командная оболочка tcsh (А.Федорчук)

    Zenwalk: пакет недели

    17 сентября

  • T2C: технология автоматизированной разработки тестов базовой функциональности программных интерфейсов
  • Технология Azov автоматизации массового создания тестов работоспособности

    CITKIT.ru:

  • FreeBSD: ZFS vs UFS, и обе-две — против всех (А.Федорчук)

    Zenwalk: пакет недели

  • Дачнет — практика без теории (С.Голубев)

    10 сентября

  • За чем следить и чем управлять при работе приложений с Oracle
  • Планировщик заданий в Oracle
    (В.Пржиялковский)

    CITKIT.ru:

  • Microsoft: ответный "боян" (С.Голубев)

  • Причуды симбиоза, или снова "сделай сам" (В.Попов)

  • Файловые системы современного Linux'а: последнее тестирование
  • Zsh. Введение и обзор возможностей
    (А.Федорчук)

    Описания пакетов Zenwalk: Zsh, Thunar, Thunar-bulk-rename, Xfce4-places-plugin, Xfce4-fsguard-plugin

    Блогометки:

  • Google Chrome
  • Лончер для ASUS Eee PC 701

    3 сентября

    CITKIT.ru:

  • Заметки о ядре (А.Федорчук):

    Добавлены описания пакетов Zenwalk: Galculator, Screenshot, Gnumeric, Pidgin

    В дискуссинном клубе:

  • И еще о Википедии и Google Knol

  • Лекция для начинающего линуксоида (С.Голубев)

    26 августа

  • Транзакционная память (Пересказ: С. Кузнецов)

    CITKIT.ru:

  • Открыт новый проект Zenwalk: пакет недели

  • Статья Текстовые процессоры и их быстродействие: конец еще одной легенды?

    21 августа

    CITKIT.ru:

  • Почему школам следует использовать только свободные программы (Ричард Столлман)
  • Беседа Сергея Голубева с учителем В.В.Михайловым

  • Википедия или Гуглезнание? Приглашение к обсуждению (Алексей Федорчук)
  • Народная энциклопедия от Google (StraNNik)

  • Обзор Mandriva 2009.0 Beta 1 Thornicrofti
  • Новичок в Линукс: Оптимизируем Mandriva 2008.1

  • Книга Zenwalk. Приобщение к Linux:

    13 августа

    CitCity:

  • Мирный Atom на службе человеку. Обзор платы Intel D945GCLF с интегрированным процессором
  • Обзор процессоров Intel Atom 230 на ядре Diamondville

  • iPhone - год спустя. Скоро и в России?

    CITKIT.ru:

  • Интермедия 3.4. GRUB: установка и настройка (из книги Zenwalk. Приобщение к Linux)

    6 августа

  • СУБД с хранением данных по столбцами и по строкам: насколько они отличаются в действительности? (Пересказ: С. Кузнецов)

    CITKIT.ru:

  • Интермедия 2.2. Что неплохо знать для начала (из книги Zenwalk. Приобщение к Linux)

  • И снова про шрифты в Иксах (А.Федорчук)

  • 20 самых быстрых и простых оконных менеджеров для Linux

  • Дело о трех миллиардах (С.Голубев)

    30 июля

  • OLTP в Зазеркалье (Пересказ: С. Кузнецов)

    CitCity:

  • Будущее BI в облаках?
  • Тиражные приложения и заказная разработка. Преимущества для заказчика
  • Дискуссия со сторонниками заказной разработки

    CITKIT.ru:

  • Новые главы книги Zenwalk. Приобщение к Linux:
  • Глава 8. Пакеты: средства установки, системы управления, системы построения
  • Глава 9. Zenwalk: репозитории, пакеты, методы установки

    23 июля

    CITKIT.ru:

  • Все против всех. 64 vs 32, Intel vs AMD, tmpfs vs ext3
  • Две головы от Intel

  • Zenwalk: обзор штатных приложений (глава из книги "Zenwalk. Приобщение к Linux")

  • Нормально, Григорий...

    16 июля

    Обзоры журнала Computer:

  • Перспективы и проблемы программной инженерии в XXI веке
  • Большие хлопоты с большими объемами данных
  • Перспективы наноэлектроники

    CITKIT.ru:

  • Интермедия о лицензиях (А.Федорчук. "Zenwalk. Приобщение к Linux")

  • Есть ли будущее у KDE?

  • Linux в школе: альтернативный вариант в задачах

  • Шифр (приключения агента Никодима)

    10 июля

    CITKIT.ru:

  • Новые разделы книги А. Федорчука Zenwalk. Приобщение к Linux:
  • Интермедия вступительная. Linux или GNU/Linux? Как вас теперь называть?
  • Глава 5. Среда Xfce
  • Глава 6. Xfce: приложения и плагины

  • ZUR (Zenwalk User Repository) FAQ

    2 июля

  • Персистентность данных в объектно-ориентированных приложениях (С. Кузнецов)

    CITKIT.ru:

  • Новые разделы книги А. Федорчука Zenwalk. Приобщение к Linux:
  • Интермедия 1.2. Дорога к Zenwalk'у. Период бури и натиска
  • Интермедия 3.3. Немного о Linux'е и "железе"
  • Глава 4. Настройка: инструментами и руками
  • Интермедия 4.1. Zenpanel и конфиги: поиски корреляции

  • Интервью с Жан-Филиппом Гийоменом, создателем дистрибутива Zenwalk

  • Linux в школе: первые итоги (С. Голубев)

    25 июня

    CITKIT.ru:

  • Zenwalk. Приобщение к Linux (А. Федорчук)

  • Логика и риторика (С.Голубев)

  • Технология Tru64 AdvFS

  • Ханс Райзер предлагает отвести полицейских к телу Нины

    18 июня

  • Проекты по управлению данными в Google (Пересказ: С. Кузнецов)

    CITKIT.ru:

  • ОС и поддержка "железа": мифы и реальность (А. Федорчук)

  • Linux в школе: другие дистрибутивы

  • Пинок (С. Голубев)

    4 июня

  • Ландшафт области управления данными: аналитический обзор (С. Кузнецов)

    CITKIT.ru:

  • Linux в школе: слово заинтересованным лицам

  • SlackBuild: пакеты своими руками

  • Linux от компании Novell. Установка и обзор openSUSE Linux

    Все публикации >>>




  • IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware

    Информация для рекламодателей PR-акции, размещение рекламы — тел. +7 495 4119920, ICQ 232284597 Пресс-релизы — pr@citcity.ru
    Послать комментарий
    Информация для авторов
    Rambler's Top100 TopList liveinternet.ru: показано число просмотров за 24 часа, посетителей за 24 часа и за сегодня This Web server launched on February 24, 1997
    Copyright © 1997-2000 CIT, © 2001-2007 CIT Forum
    Внимание! Любой из материалов, опубликованных на этом сервере, не может быть воспроизведен в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. Подробнее...