Высокопроизводительные методы геометрического моделирования Михаил Бессмельцев к. ф.- м. н. Ольга Нечаева Лекция 1. Сетки : определения и структуры данных. - презентация

1 Высокопроизводительные методы геометрического моделирования Михаил Бессмельцев к. ф.- м. н. Ольга Нечаева Лекция 1. Сетки : определения и структуры данных

2 Определения Графы, Планарность, Триангуляция, Делоне, Сетки

3 Graphs Графы Сетка – это частный случай неориентированного графа G = V – вершины (A,B,…) E – ребра (AB, BC, …) Цикл – например, AJLCB Степень вершины – кол - во ребер, инцидентных вершине deg(B) = 3, deg(K) = 4 Грань – цикл без ребер / вершин внутри

4 Planar Graphs Планарные графы Граф планарный, если его можно нарисовать на плоскости без пересечений Любой планарный граф можно нарисовать так, чтобы все ребра были прямыми

5 Planar Graphs Планарные графы Граф планарный, если его можно нарисовать на плоскости без пересечений Любой планарный граф можно нарисовать так, чтобы все ребра были прямыми

6 Planar Graphs Планарные графы Граф планарный, если его можно нарисовать на плоскости без пересечений Любой планарный граф можно нарисовать так, чтобы все ребра были прямыми

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

8 Триангуляция Делоне Триангуляция Делоне – хорошая триангуляция. Триангуляция является ~ Делоне, если внутри описанной окружности любого треугольника нет вершин триангуляции ( точек ). В 2 D для данного множества точек триангуляция Делоне существует ( возможно, не одна ).

9 Meshes Сетки Сетка – граф с прямыми ребрами в R 3. Граничные ребра – ребра, содержащиеся ровно в одном треугольнике. Обычные ребра – ребра, содержащиеся ровно в 2 х треугольниках. Сингулярные ребра – > 2 треугольников. Замкнутая сетка – сетка без граничных ребер. Manifold mesh ( многообразия ) – сетка без сингулярных ребер.

10 Planar graphs & meshes Планарные графы и сетки Любая сетка многообразия является планарной ! ( почти )

11 Сеточные структуры данных

12 Где и как используются структуры данных для сеток ?

13 Для рендеринга ( отрисовки ) Для обработки / вычислений : Вопросы типа Какие вершины у треугольника номер ##? Смежны ли вершины i и j? Какие соседи у треугольника ##? Операции Вставить / удалить треугольник Вставить / удалить вершину Сделать общую универсальную структуру данных - маловероятно

14 Чем отличаются структуры данных ? Временная сложность создания Временная сложность изменения Временная сложность ответа на вопросы про соседей / смежность Простота самой структуры ( важно для портирования / распараллеливания ) Ёмкостная сложность ( точнее, сколько занимает памяти эта структура )

15 Список граней ( треугольников ) GeomPrimitives::TriangulationData Структура состоит из : Списка координат вершин TriangulationData::getAllPoints(); // возвращает все вершины TriangulationData::getPoint (i); Списка треугольников TriangulationData::getAllTriangles(); TriangulationData::getTriangle(i); Ответ на вопрос « Какие вершины у треугольника номер ##» занимает O(1) Ответ на вопрос, смежны ли вершины i и j, занимает O(|E|) – неэффективно

16 Список граней - пример f1f1 f2f2 f3f3 f4f4 v1v1 v2v2 v3v3 v4v4 v5v5 v6v6 координатывершина (x 1,y 1,z 1 )v1v1 (x 2,y 2,z 2 )v2v2 (x 3,y 3,z 3 )v3v3 (x 4,y 4,z 4 )v4v4 (x 5,y 5,z 5 )v5v5 (x 6,y 6,z 6 )v6v6 вершиныгрань (v 1, v 2, v 3 )f1f1 (v 2, v 4, v 3 )f2f2 (v 3, v 4, v 6 )f3f3 (v 4, v 5, v 6 )f4f4

17 Список граней : плюсы и минусы Удобная и простая Эффективная ( занимает мало памяти ) Универсальная ( нет ограничений на дырки или сингулярные ребра ) Слишком простая : нет дополнительной информации вроде соседей треугольника

18 Adjacency Matrix Матрица смежности Матрица смежности может задавать, вообще говоря, произвольный граф Пусть у нас есть n вершин. Матрица смежности – матрица n*n {e i,j }: e i,j = true, если вершины i и j смежны. e i,j = false, else. Кроме самой матрицы, нужно хранить список координат вершин Дополнительно храним треугольники – тройки номеров

19 Adjacency Matrix : example Матрица смежности : пример coordinatevertex (x 1,y 1,z 1 )v1v1 (x 2,y 2,z 2 )v2v2 (x 3,y 3,z 3 )v3v3 (x 4,y 4,z 4 )v4v4 (x 5,y 5,z 5 )v5v5 (x 6,y 6,z 6 )v6v6 vertices (ccw)face (v 1, v 2, v 3 )f1f1 (v 2, v 4, v 3 )f2f2 (v 3, v 4, v 6 )f3f3 (v 4, v 5, v 6 )f4f4 v6v6 v5v5 v4v4 v3v3 v2v2 v1v1 11v1v1 111v2v2 1111v3v3 1111v4v4 11v5v5 111v6v6 f1f1 f2f2 f3f3 f4f4 v1v1 v2v2 v3v3 v4v4 v5v5 v6v6

20 Матрица смежности : эффективность Какие вершины в треугольнике ##? O(1) – посмотреть соотв. элемент списка треугольников Смежны ли вершины i и j? O(1) – проверить соответствующий элемент в матрице. В каких треугольниках содержится вершина i? O(|Faces|) – придется пробежать все грани/треугольники

21 Adjacency Matrix : pros and cons Матрица смежности : плюсы и минусы Любые вопросы о смежности отвечаются мгновенно – O(1) Универсальная Расходуется слишком много памяти ( |V| 2 ). Редко применяется для сеток, скорее с её помощью описывают графы, близкие к полным ( |E||V| 2 ). По вершине сложно найти треугольник

22 Half-Edge structure Полуреберная структура Для каждой вершины храним Координаты Указатель на какое - нибудь « полуребро », началом которого является эта вершина Для каждого треугольника храним Указатель на какое-нибудь «полуребро» этого треугольника e twin(e) origin(e) IncFace(e) prev(e) next(e)

23 Half-Edge structure Полуреберная структура Полуребро – это e twin(e) origin(e) IncFace(e) prev(e) next(e) 1. Указатель на начало: origin(e) 2. Указатель на двойственное полуребро - twin(e) 3. Указатель на треугольник, которому оно принадлежит – IncidentFace(e) (положительный обход контура) 4. Указатели на следующее и предыдущее полуребра в треугольнике – next(e) и prev(e)

24 Half-Edge structure: Efficiency Полуреберная структура : Эффективность Большинство операций выполняются за O(1) Основные операции : Пробежать по границе ( ребра + вершины ) какого - то треугольника Пробежать все ребра, инцидентные v

25 Half-Edge structure: Example Полуреберная структура : Пример Incident EdgecoordinateVertex e 2,1 (x 1,y 1,z 1 )v1v1 e 5,1 (x 2,y 2,z 2 )v2v2 e 1,1 (x 3,y 3,z 3 )v3v3 e 7,1 (x 4,y 4,z 4 )v4v4 e 9,1 (x 5,y 5,z 5 )v5v5 e 7,2 (x 6,y 6,z 6 )v6v6 edgeface e 1,1 f1f1 e 5,1 f2f2 e 4,2 f3f3 e 8,1 f4f4 f1f1 f2f2 f3f3 f4f4 v1v1 v2v2 v3v3 v4v4 v5v5 v6v6 e 1,1 e 6,1 e 4,1 e 7,2 e 9,1 e 8,1 e 3,2 e 5,1 e 7,1 e 3,1 e 2,1 e 4,2

26 Half-Edge structure: Example Полуреберная структура : Пример f1f1 f2f2 f3f3 f4f4 v1v1 v2v2 v3v3 v4v4 v5v5 v6v6 e 1,1 e 6,1 e 4,1 e 7,2 e 9,1 e 8,1 e 3,2 e 5,1 e 7,1 e 3,1 e 2,1 e 4,2 prevnextIncidentFacetwinoriginHalf-edge e 2,1 e 1,1 f1f1 e 3,2 v2v2 e 3,1 e 4,1 e 5,1 f2f2 e 3,1 v3v3 e 3,2 e 5,1 e 3,2 f2f2 e 4,2 v4v4 e 4,1 e 6,1 e 7,1 f3f3 e 4,1 v3v3 e 4,2

27 Half-Edge structure Полуреберная структура Вопрос : Как пробежать все ребра, примыкающие к данной вершине ?

28 Half-Edge structure Полуреберная структура Вопрос : Как пробежать все ребра, примыкающие к данной вершине ? begin = vertex.half; half = begin; do { half = half->pair->next; } while (half != begin)

29 Half-Edge structure Полуреберная структура Вопрос 2: Какие ограничения на сетку накладывает такая структура ?

30 Half-Edge structure Полуреберная структура Вопрос 2: Какие ограничения на сетку накладывает такая структура ?

31 Half-Edge structure Полуреберная структура Вопрос 2: Какие ограничения на сетку накладывает такая структура ? Ответ : сетка должна быть Сеткой многообразия Ориентируемой

32 Half-Edge structure: Pros & cons Полуреберная структура : Плюсы и минусы Эффективная – большинство операций и запросов за O(1) ( как правило ) Не универсальная : годится только для сеток многообразий

33 Corner Table Таблица Углов Угол состоит из Треугольника – c.t. Вершины - c.v Следующего угла – c.n Предыдущего угла – c.p Противоположного угла – c.o Левого угла – угла, противоположного c.p ( == c.n.n.o) Правого угла – угла, противоположного c.n ( == c.n.o)

34 Corner Table: Example Таблица Углов : Пример f1f1 f2f2 f3f3 f4f4 v1v1 v2v2 v3v3 v4v4 v5v5 v6v6 c1c1 c2c2 c5c5 c3c3 c4c4 c6c6 c 10 c 12 c 11 c9c9 c7c7 c7c7 c.lc.rc.oc.pc.nc.tc.v corner NULL c6c6 c3c3 c2c2 f1f1 v1v1 c1c1 c6c6 c1c1 c3c3 f1f1 v2v2 c2c2 c6c6 c2c2 c1c1 f1f1 v3v3 c3c3 c1c1 c7c7 c6c6 c5c5 f2f2 v3v3 c4c4 c1c1 c7c7 c4c4 c6c6 f2f2 v2v2 c5c5 c7c7 c1c1 c5c5 c4c4 f2f2 v4v4 c6c6

35 Corner Table: Pros & Cons Таблица Углов : плюсы и минусы Все запросы за O(1) Все операции, как правило, за O(1) Только сетки многообразий Избыточность ( хотя и не много )

36 Corner Table: Queries Examples Таблица Углов : Примеры запросов Какие вершины у 3 его треугольника ? Проверить c.v. у углов 9, 10, 11 (c.v, c.n.v, c.p.v) Смежны ли вершнины i и j? Пробежать все углы вершины i, проверить, c.n.v == j или c.p.v == j Какие треугольники примыкают к вершине i? Проверить все c.t всех углов i

37 ПО для семинаров AITricks GeomPrimitives & AITricks GeomBox

38 AITricks GeomPrimitives Вам не требуется реализовывать тривиальные структуры данных, вроде точек, треугольников, сегментов, фигур и операций над ними. Зато у Вас будут задания посложнее Документация скоро будет на сайте

39 AITricks GeomBox Те задачи, которые потребуют визуализации, можно рисовать, используя GeomBox. Вам не нужно самим писать отрисовку ваших сеток / примитивов

40 AITricks GeomBox

41 В следующий раз … Упрощение сеток 12,0002,

42 Вопросы ? Вся информация по спецкурсу + презентации + текущие баллы выкладываются на