Полигональное задание пространственных форм

ТНС – триангулированная нерегулярная сетка: Здесь все точки могут быть не привязаны ни к каким дескрипторам. В основе метода лежит круговой критерий: Если провести окружность вокруг 3ч точек то другие точки не должны попа дать в него. Алгоритм: 1 Все точки которые надо стриангулировать лежат внутри прямоугольника: 2 После этого проводят начальную триангуляцию: делим прямоугольник по полам; 3 Берётся точка например А и проводится триангуляция: а Определяем в какой треугольник попала эта...

2014-07-07

39.04 KB

1 чел.


Поделитесь работой в социальных сетях

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


Полигональное задание пространственных  форм.

 

14.1. Рельефы:

-         регулярные;

-         нерегулярные.

 

1)     

Представление на регулярных сетках:

Вид сверху:

ТСР-трианулярная регулярная сетка:

 

а)

 

 

 

 

 

 

 

 

 

 

 

б) но предпочтительнее правильные треугольники:

 

 

 

 

 

 

 

 

 

Плюс ТСР:

                   Простота построения.

Недостаток:

                    Большой объём данных.

 

 

2)     

ТНС – триангулированная нерегулярная сетка:

 

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

 

Пример:

 

 

 

 

 

 

 

 

 

 

 

Метод триангуляции Делоне.

 

Суть :

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

В основе метода лежит круговой критерий:

 Если провести окружность вокруг 3-ч точек, то другие точки не должны попа-

 дать в него.

 

Алгоритм:

1)      Все точки, которые надо стриангулировать, лежат внутри прямоугольника:

 

 

2)      После этого проводят начальную триангуляцию: делим прямоугольник по-

полам;

3)      Берётся точка (например  А) и проводится триангуляция:

а) Определяем , в какой треугольник попала эта точка;

б) Делим этот треугольник на 3 треугольника;

в) Помещаем в стек флипов 3 ребра (на рис. 1, 2, 3);

г) Просматриваем стек флипов и , используя круговой критерий, решаем на до флиповать ребро или нет (если точка не попала в окружность, то флип не нужен, а если попала – нужен)

         Флип – переброска ребра.

         На этом основании в  рассматриваемом примере произошла замена ребра

         1 на ребро 4.

 

Примечание:

Если у нас есть N вершин, то сколько у нас будет рёбер (R) и сколько треугольников (Т), а так же найдём количество соседних треугольников (К), приходящихся на одну вершину.

Пусть у нас есть треугольник. На каждую точку, взятую в этом треугольнике, добавляется 2 треугольника. Следовательно,   Т=2N.

Число рёбер:   R=3N, так как при добавлении каждой точки добавляется ещё и 3 новых ребра.

У каждой точки есть определённое количество соседних вершин, а общее количество прикреплений рёбер к треугольникам будет равно: 2R.

Следовательно: (т.е. у каждой точки есть по “шесть соседей”)

 

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

 

Флип производится с учётом критерия флипа (связан с окружностью)

Решение кругового критерия можно свести к следующему решению:

 

 

Введём следующие обозначения :

= отрезок  01;     = отрезок 02  и т. д.

Необходимо решить вопрос о том : Какое ребро выбрать?  (12 или 34)

В этом нам поможет следующее выражение:

 

 

14.1.2. Области Вороного.

 

Область Вороного строится соединением серединных перпендикуляров в исход-

ных треугольниках.

 

 

 

                                                                                                                                                                                                                                                                                         Свойство области Вороного:

Область Вороного гарантирует, что любая точка этой области лежит ближе к точки, вокруг которой строилась эта область, чем любая точка, не лежащая в этой области.

Дуализм проявляется в том , что:

    По триангуляции Делоне можно построить области Вороного и наоборот

14.1.3. Представление рельефа с мультиразрешением.

 

Мультиразрешение – представление с различной степенью детализации.

 

Основная задача:

Сортировка тачек по степени важности.

 

Данное представление можно использовать при изображении рельефа:

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

 

Наблюдатель в точке.

 

Показана триангуляция 0-го ранга

 

 

                                                                                             

 

 

Существует и такое понятие, как переменное мультиразрешение – один объект(рельеф), но представляется с различным разрешением в разных частях этого объекта.

 

Теперь рассмотрим такую задачу, как удаление точки из триангуляции. Это сделать достаточно сложно, но можно.

 

 

Допустим, хотим удалить следующую точку(на рис. помечена красным):

Для этого нужно:

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


Безусловно, сеществует несколько способов удаления точек, но самый эффективный это

Ранжирование точек.

 

Принцип по которому строится этот способ состоит в следующем:

В первую очередь удаляются точки, которые лежат в одной плоскости.

 

Наша задача – оценить важность точки, а значит наити ценность для каждой точки.

 

-нормированная нормаль для j-ой вершины;

- соседние вершины (число соседних вершин m);

- сама точка.

Функция нормировки:

 

Алгоритм ранжирования точек:

 

1) Построить триангуляцию полного разрешения, т.е. всех вершин. Присвоить    

    всем вершинам максимальный ранг;

2) Для каждой вершины посчитать среднюю нормаль(она считается один раз

   и является постоянной характеристикой вершины);

3) Для всех вершин рассчитать стоимость;

4) Установить текущий ранг = 0;

5) Удалить из триангуляции часть вершин, имеющих наименьшую стоимость.

    Пересчитать стоимость соседних вершин по отношению к удалённой.

    Присваиваем им текущий ранг;

6) Посчитать ошибку с данным рангом триангуляции, т.е. для каждой вершины

   (удалённой) посчитать расстояние по её триангуляции;

7) Увеличиваем текущий ранг на единицу;

8) Проверка текущего ранга(если текущий ранг не равен максимальному рангу,

   то возвращаемся к 5-му пункту.

 

Этот алгоритм можно усложнить. Например:

Оценивать ошибки удалённых вершин, а если, вершина была удалена неудачно,

то её возвращаем обратно.

 

14.2. Объекты.

 

В отличие от рельефа объект изображается с использованием одного разреше-

ния. Как правило создаётся много моделей одного объекта.

 

В этом случае точка удаляется следующим образом:

 

 

 

 

 

Допустим, удаляем ребро {1 2}. В этом случае всё что

имело связь с вершиной 1 перейдёт в вершину 2.

 

 

 

Т.е. происходит процесс калабса ребра:

Нужно выбрать ребро, которое подвергнем калабсу. Для этого определяем стоимость рёбер.

 

Оценку ребра можно сделать, используя среднюю нормаль, но мы рассмотрим

математическую основу (т.е. основанную на квадриках).

 

Пусть плоскость задана нормалью  и числом D.

Тогда уравнение плоскости будет выглядеть следующим образом:

                           

D – свободный член в уравнении плоскости.

Рассмотрим расстояние от точки V до плоскости.

Пусть точка V имеет следующие координаты V(x, y, z). Тогда расстояние будет

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

                            

Но нас больше интересует квадрат этого расстояния:

     

 

                                                            

 

Обозначим:

                                

 

Тогда выражение для квадрата расстояния будет выглядеть следующим образом:

                        

Это формула вычисления квадрата расстояния с помощью квадрика плоскости и точки плоскости.

 

Квадрик – совокупность величин А, В, С:

                                           

Таким образом квадрик определяется только параметрами плоскости.

При работе с объектами вводится следующее понятие:

Если к одной вершине присоединены несколько треугольников, то квадрик этой

вершины будет равен сумме всех квадриков прилегающих к этой вершине треугольников:

                                           

 

 

 

Например:

 

 

 

 

 

 

 

 

 

 

 

В данном случае:

                               

А так же важно записать следующее выражение:

                              

 

Рассмотрим ещё один пример:

                                                               

Допустим, мы хотим переместить точку 6 в точку 7.

Тогда:

    

А для точки 7 мы можем посчитать следующее:

 

 

 

 

Эта величина показывает на сколько вершина 7 отклоняется от окружающих плоскостей вершины 6.

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

14.2.1. Механизм колабса ребра.

 

Цель: выбор ребра, от которого можно избавмться, но это избавление должно принести наименьшую ошибку. Рассмотрим пример:

 

 

 

Во-первых, нам нужно найти квадрики всех вершин, а затем и рёбер.

Для примера возьмём ребро {1-2}:

 

     Квадрик этого ребра:

                                              

Во-вторых, для каждого ребра считаем критерий, выбирая лучший переброс:

     

     Критерий для ребра {1-2}:

          ,

                      так как

                                    

Затем выбираем ребро с наименьшим значением , которое и будет удалено.

Замыкание будет зависеть от следующего критерия:

        - удаляется

        - удаляется  

Результат:

       Мы выбрали такое перемещение, которое приносит наименьшую ошибку.

 

Примечание:

При перебросе квадрики вершин изменяются, следовательно, их нужно пересчи-

тать, а значит стоимость рёбер так же поменяется.

 

С помощью квадрика мы можем порождать новую вершину:

 

  Допустим, мы хотим перекинуть все связи в

  точку О. Координаты этой точки нам не изве-

  стны, но мы можем их найти следующим об-

  разом:

               

  Получается, что

  Минимальный критерий для точки :

                                       

Т.е. квадрик несёт в себе информацию об оптимальной точке, в которую можно свести все связи.

 

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

 

 

14.2.2. Гипертриангуляция

 

Заключает в себе триангуляции всех уровней разрешения. Но выигрыш в её

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

 

Резюме:

1)      Существуют:

             а) Рельеф:

                   представляется с разным уровнем разрешения (мультиразрешение)

                   и наиболее удачна для этого триангуляция Делоне.

             б) Объект:

                   представляется с постоянным уровнем разрешения, триангуляция

                   Делоне не применяется, но используется математическое упроще-

                   ние с помощью квадриков.

2)      Механизм квадриков можно перекинуть на работу с рельефом, а работу с

нормалью перекинуть на объекты



 

Другие похожие работы, которые могут вас заинтересовать.
3417. Обучение студентов проведению активных форм санпросветработы в группах дошкольников. Задание на дом по составлению сказок – бесед для детей 3-5 лет 27.34 KB
  Задание на дом по составлению сказок – бесед для детей 35 лет. Тщательно разбираются особенности психологии поведения детей дошкольного возраста. У детей 2 – 4 лет беседы и обучение гигиене полости рта должны быть тесно переплетены между собой в форме игрового обучающего продолжительного в несколько занятий спектакля в котором беседа подана в виде доступной детям игры на примере Зайки который хорошо чистит зубы ест морковку и не любит конфеты а обучение навыкам носит регулярный последовательный характер с требованием...
3669. Работа с модификаторами. Полигональное моделирование. Ознакомление с редактором материалов 1.19 MB
  Научиться использовать модификаторы геометрии в 3ds Max и применять методы полигонального моделирования. Ознакомиться с редактором материалов.
1973. АНАЛИЗ ПРОСТРАНСТВЕННЫХ ДАННЫХ 5.82 KB
  Анализ пространственного распределения объектов 5. Например операции наложения графических объектов средства анализа сетевых структур или выделения объектов по заданным признакам. Это прежде всего организация выбора и объединения объектов в соответствии с заданными условиями реализация операций вычислительной геометрии анализ наложений построение буферных зон сетевой анализ. Основные функции пространственного анализа данных Выбор объектов по запросу: самой простой формой запроса является получение характеристик объекта указанного...
16866. Сравнение пространственных эффектов для восточных и западных российских регионов 17.32 KB
  Идея лежащая в основе пространственно-эконометрических моделей довольно проста: при моделировании макроэкономических показателей стран или регионов надо учитывать не только влияние других факторов в этих странах или регионах но и значения этих же макроэкономических показателей в других странах или регионах. Тогда количество параметров отражающих влияние других стран или регионов сокращается до одного - коэффициента пространственной автокорреляции по аналогии с коэффициентом автокорреляциии во временных рядах. Однако для...
3549. Родительское собрание на тему: «Как готовить домашнее задание» 14.02 KB
  Учеба в школе, выполнение домашних заданий – серьезный труд. Бывает, что третьеклассник занят не меньше взрослого. Прочитайте эпиграф к нашему собранию. Наша задача – приучить ребенка трудиться правильно, не нанося вред здоровью, т. к. учеба – это главный труд школьника.
9804. Задание на курсовую работу Анализ линейных электрических цепей в установившихся режимах 299.45 KB
  Среди возможностей MthCd можно выделить: Решение дифференциальных уравнений в том числе и численными методами Построение двумерных и трёхмерных графиков функций в разных системах координат контурные векторные и т. Метод узловых потенциалов. Заземлим узел 4 и составим уравнение по методу узловых потенциалов. Метод контурных токов.
1336. Виды источников (форм) права 39.97 KB
  Тема источников российского права традиционно является одной из ключевых для отечественной правовой науки и неизменно привлекает повышенное внимание исследователей. При этом, несмотря на весьма внушительную историю разработки проблем, связанных с сущностью, содержанием, эволюцией источников права...
10741. Эволюция форм и видов денег 26.16 KB
  Государственные бумажные деньги: понятие особенности. Кредитные деньги: понятие виды их сходство и отличия от государственных бумажных денег. Квазиденьги вексель чек банковская карта...
4412. КЛАСИФІКАЦІЯ ОСНОВНИХ ФОРМ ДІЯЛЬНОСТІ ЛЮДИНИ 6.91 KB
  Діяльність це активна взаємодія людини з навколишнім середовищем завдяки чому вона досягає свідомо поставленої мети яка виникла внаслідок прояву у неї певної потреби Життя людини – це постійна динаміка різних видів її діяльності. Гра – це найпростіший вид діяльності яким оволодіває дитина в процесі свого розвитку. В ній розпочинається формування людини як особистості як субâ€єкта діяльності.
5019. Составление форм бухгалтерской (финансовой) отчетности 174.49 KB
  Изучить теоретические аспекты составления бухгалтерской (финансовой) отчетности; рассмотреть содержание и порядок составления форм бухгалтерской (финансовой) отчетности, особенности международных стандартов финансовой отчетности; сформировать показатели форм бухгалтерской отчетности на примере деятельности условного предприятия;
© "REFLEADER" http://refleader.ru/
Все права на сайт и размещенные работы
защищены законом об авторском праве.