Образования Российской Федерации томский государственный университет факультет информатики Кафедра теоретических основ информатики




НазваниеОбразования Российской Федерации томский государственный университет факультет информатики Кафедра теоретических основ информатики
страница2/4
Дата24.09.2012
Размер0.62 Mb.
ТипДипломная работа
1   2   3   4

1.2.6. Полигон

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




Рисунок 5. Примеры полигонов


Для этого класса реализованы 2 алгоритма:

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

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

1.2.6.1. Алгоритм определения положения точки относительно произвольного полигона

Идея данного алгоритма аналогична идее алгоритма определения положения точки относительно трехмерного объекта (см. далее)

Реализуется алгоритм в три этапа:

  1. Этап предподготовки: для всех ребер полигона нужно создать список векторов, указывающих правую сторону каждого ребра (т.е. указывающих вовнутрь полигона). Вектора должны находиться в плоскости полигона и каждый вектор должен быть перпендикулярен соответствующему ребру (аналог нормалей для граней трехмерного объекта). Их можно найти с помощью векторного произведения нормали к полигону и вектора направления соответствующего ребра.

  2. Ищем ближайший отрезок к данной точке путем анализа расстояний от точки до середины каждого отрезка.


  3. И
    з данной точки пускаем луч в направлении середины найденного ближайшего отрезка в плоскости полигона. Далее сопоставляем направления двух векторов: вектора, построенного для ближайшего отрезка и вектора направления луча. Если они сонаправлены (т.е. угол отклонения не более 90 градусов), то точка находится вне полигона, иначе – внутри (см. Рисунок 7).


А) точка снаружи

Б) точка внутри

Рисунок 7. Определение положения точки относительно полигона




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





Рисунок 8. Порядок обхода вершин полигона



1.2.6.2. Алгоритм триангуляции полигона

Существует множество алгоритмов триангуляции полигонов [7] и все они дают специфичный для каждого алгоритма результат. Некоторые отличаются быстротой выполнения, другие эффективностью представления результата. В данной задаче алгоритм триангуляции используется лишь для того, чтобы разбить полигон, полученный при пересечении двух объектов, представленных в виде списка треугольников, на треугольники. Таким образом, вершин в этом полигоне будет немного. Кроме того, данный полигон может быть совершенно произвольной формы (не только выпуклый). Наиболее «красиво» выглядит триангуляция Делоне, но ввиду произвольности полигона использовать алгоритмы построения такой триангуляции нельзя, за исключением алгоритма, который предполагает разбиение невыпуклого полигона на несколько выпуклых.

В данной работе используется алгоритм, своей идеей похожий на жадный алгоритм [8], который оправдывает себя тем, что на небольшом количестве вершин его трудоемкость не сильно повлияет на трудоемкость всего алгоритма в целом (в общем случае трудоемкость жадного алгоритма имеет порядок N^2 * log N [8]).


Реализуется он следующим образом:

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


На данном этапе понадобится алгоритм определения положения точки относительно полигона (внутри или снаружи) для проверки положения линии относительно полигона: если середина отрезка принадлежит полигону, то отрезок находится внутри полигона, и

А) все возможные отрезки


Б) конечный список линий

Рисунок 9. Триангуляция полигона

наче - снаружи. Этот алгоритм будет рассмотрен ниже.


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


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


      1. Трехмерный объект


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


        1. Алгоритм определения положения точки относительно объекта

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

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



Рисунок 10. Точка находится снаружи объекта, вектора противоположно направлены


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




Рисунок 11. Выбор ближайшего треугольника

Т.о. необходимо точно находить расстояние до треугольников.

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

  1. Опустим на плоскость треугольника перпендикуляр из данной точки, получим проекцию точки на плоскость

  2. Если точка проекции принадлежит области, ограниченной данным треугольником, то длину перпендикуляра и будем считать расстоянием.

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


На Рисунке 12 изображена ситуация, когда ищется ближайший треугольник к точке P. Точка P находится «ниже» плоскостей обоих треугольников. Визуально видно, что правильным решением является треугольник АВС. Но расстояние, если следовать рисунку, до треугольника АBD от точки P будет таким же как от P до ABC.



Рисунок 12. Подсчет расстояния до треугольника


Найти правильное решение можно следующим путем:

Пусть угол L1 – угол между плоскостью АPB и плоскостью ABC, а угол L2 – угол между плоскостью APB и плоскостью ABD. Сравним два этих угла: точка будет ближе к тому треугольнику, для которого угол будет больше, т.е. если L2 > L1, то точка ближе к треугольнику ABD.

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

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



        1. Алгоритм построения совокупной модели пересечения двух пространственных объектов

Суть данного алгоритма состоит в отсечении всех «невидимых» частей обоих объектов, т.е. тех их плоскостей, которые окажутся внутри совокупной модели.

Из-за того, что объекты могут пересекаться совершенно произвольным образом, треугольники, описывающие исходные объекты, могут перекрываться не полностью, а вследствие отсечения у них невидимых частей, может получиться произвольный полигон. Так, на Рисунке 13, показан контур полигона, получившийся при пересечении одного из треугольников, принадлежащих объекту A, с объектом B.





Рисунок 13. Полигон, получившийся при пересечении двух объектов



Алгоритм представляет собой несколько этапов:

  1. поиск отрезков, принадлежащих границе пересечения двух объектов.

  2. построение заготовок для полигонов и построение внешних отрезков

  3. построение полигонов из заготовок и множества отрезков

  4. построение полигонов из множества отрезков

  5. разбиение полигонов на треугольники (см. выше)

Далее эти этапы рассматриваются подробнее.



А) отрезки, не

принадлежащие объекту B

Б) отрезки, не

принадлежащие объекту А

В) отрезки пересечения объекта А и объекта Б


Рисунок 14. Множество отрезков

Поиск граничных отрезков

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

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

Что касается поиска отрезков пересечения двух треугольников в трехмерном пространстве, то здесь используется та же идея, что и при получении списка пересечений двух объектов: сначала запускается процедура поиска всех отрезков пересечений, которые принадлежат ребрам первого треугольника и поверхности, ограниченной ребрами другого треугольника, а затем наоборот (см. Рисунок 15).



А) отрезки, найденные для ребер первого треугольника

Б) отрезки, найденные для ребер второго треугольника


Рисунок 15. Поиск граничных отрезков

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

Рассмотрим i-й треугольник, принадлежащий объекту А и j-й треугольник, принадлежащий объекту В. Для каждого ребра i-го треугольника ищем возможные точки пересечения с j-м треугольником. Далее, определяем находится ли найденный сегмент, ограниченный точками пересечения внутри j-го треугольника и, в зависимости от этого включаем его в список отрезков пересечения. То же надо проделать и для j-го треугольника. Т.о. алгоритм поиска пересечений трехмерных треугольников идентичен алгоритму поиска пересечений объектов в пространстве.


Построение заготовок для полигонов и построение внешних отрезков

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

Таким образом, заготовки полигонов, внешние отрезки и отрезки, принадлежащие границе пересечения двух объектов, позволяют получить полигоны. На Рисунке 16 изображены (слева – направо): два отрезка, вошедшие в заготовку для будущего полигона; пять отрезков (один из них скрыт геометрией OBJECT2), вошедших в список отрезков (среди них и внешние отрезки и граничные отрезки); и ребра конечного полигона.




Рисунок 16. Заготовка для полигона и множество отрезков

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

На Рисунке 17 показаны несколько отрезков, для которых родителем является изображенный треугольник. Ломаная линия – граница пересечения этого треугольника с другим объектом. Часть треугольника, находящаяся справа от ломаной (залита темным цветом), находится внутри этого объекта.





Рисунок 17. Треугольник-родитель по отношению к выделенным отрезкам


Для отслеживания треугольников-родителей используются дополнительные флаги.

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

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

Для каждого отрезка из множества отрезков флаги хранятся следующим образом:


int flags[4];

0й и 1й элементы – индексы двух треугольников для данного отрезка.

2й и 3й элементы – номера объектов (1 или 2) для соответствующих индексов треугольников (2й соответствет 0му, 3й – 1му)


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

Флаги же для набора заготовок представляют собой одномерный массив длинны n+m, где n – количество треугольников в первом объекте, m – количество треугольников во втором объекте. Заготовок для каждого объекта может быть не более, чем количество треугольников в данном объекте (будет равенство, только если объекты не пересекаются). Т.о. начиная с элемента [0] хранятся индексы треугольников-родителей из первого объекта для соответствующей [i]-той заготовки, а с индекса [n] – из второго объекта.

Ниже рассмотрен механизм устранения «дырок» в полигоне за счет использования дополнительных флагов.


Решение проблемы «дырок» в полигонах путем использования дополнительных флагов

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




Рисунок 18. Проблема «дырок» в полигонах


Треугольник АВС не разбивается на треугольники, т.е. часть треугольника не отсекается другим объектом. В результате полигон представляет собой все тот же треугольник АВС.


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


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

typedef struct FOR_JOIN_LINES_TYP

{

LINE3D line;

int flags[4];

}FOR_JOIN_LINES;


typedef struct JOIN_LINES_TYP

{

vector hole1;

vector hole2;

vector lines;

}JOIN_LINES;


hole1 и hole2 имеют тот же формат, что и lines и определяют множество дырок для первого и второго объекта соответственно.

Т.о. при построении полигона нужно проверить его на наличие дырок. Об этом скажут флаги в соответствующем множестве. Также при построении полигона в случае отсутствия ребра во множестве обычных отрезков lines нужно проверить не находится ли отрезок во множестве дырок hole.

Построение дырок в полигоне аналогично построению границы полигона, важно только правильно учитывать все флаги.

Не смотря на то, что алгоритм, описанный в данном разделе, разработан, в коде он на момент написания отчета не реализован.


Построение полигонов из заготовок и множества отрезков

П

Рисунок 19. Обход смежных треугольников

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

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


Построение полигонов из множества отрезков

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

1   2   3   4

Похожие:

Образования Российской Федерации томский государственный университет факультет информатики Кафедра теоретических основ информатики iconМинобрнауки томский государственный университет факультет информатики утверждаю
Цель курса – закрепление теоретических знаний по теоретическим и математическим основам информатики, навыков создания и анализа программных...
Образования Российской Федерации томский государственный университет факультет информатики Кафедра теоретических основ информатики iconМинобрнауки томский государственный университет факультет информатики утверждаю
Цель курса – изучение математических основ и алгоритмов представления и обработки изображений
Образования Российской Федерации томский государственный университет факультет информатики Кафедра теоретических основ информатики iconМинобрнауки томский государственный университет факультет информатики утверждаю
Цель курса – формирование основ знаний по теории информации, принципам кодирования, изучение важнейших алгоритмов в этой области
Образования Российской Федерации томский государственный университет факультет информатики Кафедра теоретических основ информатики icon«Российский экономический университет им. Г. В. Плеханова» Факультет информатики Кафедра информатики
БД. Рассматриваются экономические и технологические характеристики процессов в информационных системах
Образования Российской Федерации томский государственный университет факультет информатики Кафедра теоретических основ информатики icon«Томский государственный университет систем управления и радиоэлектроники» Кафедра экономики
А. Г. Буймов – Министерство образования и науки Российской Федерации, Федеральное государственное бюджетное образовательное учреждение...
Образования Российской Федерации томский государственный университет факультет информатики Кафедра теоретических основ информатики iconРоссийской Федерации Томский государственный университет Философский факультет Кафедра политологии
Молодежные политические объединения как политтехнологии –22
Образования Российской Федерации томский государственный университет факультет информатики Кафедра теоретических основ информатики iconГеофизический факультет кафедра информатики и гис
Министерство образования и науки РФ российский государственный геологоразведочный университет имени серго орджоникидзе
Образования Российской Федерации томский государственный университет факультет информатики Кафедра теоретических основ информатики iconРоссийской Федерации Томский государственный университет Исторический факультет Кафедра истории и документоведения
Специальность 032001 – Документоведение и документационное обеспечение управления
Образования Российской Федерации томский государственный университет факультет информатики Кафедра теоретических основ информатики iconМинобрнауки томский государственный университет факультет информатики утверждаю
Требования к уровню освоения дисциплины – владение методами математического анализа
Образования Российской Федерации томский государственный университет факультет информатики Кафедра теоретических основ информатики iconМинобрнауки томский государственный университет факультет информатики утверждаю
Цель курса – изучение методов объектно-ориентированного анализа и проектирования
Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница