uzluga.ru
добавить свой файл
1





Уменьшать количество информации

  • Уменьшать количество информации

    • для передачи и хранения сеток
  • Ускорять рендеринг (отрисовку)

  • Контролировать разрешение модели



Подробная сетка для близких объектов

  • Подробная сетка для близких объектов

  • Грубая для далёких



Упрощать за один шаг

  • Упрощать за один шаг

    • Приоритет: качество
  • Упрощать постепенно (Прогрессивные сетки)

    • Приоритет: скорость


Hoppe, 1996

  • Hoppe, 1996

  • Подробная сетка - это самая грубая сетка + история, как с ней такое сделали (вся последовательность операций упрощения)







Упрощение – последовательность локальных операций

  • Упрощение – последовательность локальных операций

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


Удаление вершины

  • Удаление вершины

    • v = v-1;
    • f = f -2;
  • Новое множество вершин – подмножество старого



Коллапс ребра (Edge collapse)

  • Коллапс ребра (Edge collapse)

    • v = v -1;
    • f = f - 2;
  • Вершины двигаются!



  • Вершины двигаются!



Локальная ошибка

  • Локальная ошибка

    • Быстро считать
    • Нужно мало памяти
    • Можно накапливать
  • Глобальная ошибка: сравнить что получилось с тем, что было

    • Медленно
    • Зато точнее контролируем ошибку
    • Можно использовать в качестве условия останова
    • Необходимо помнить начальную сетку


Меры

  • Меры

    • Расстояние до плоскости
    • Кривизна
  • Обычно аппроксимируется

    • Средняя плоскость
    • Дискретная кривизна


Repeat

  • Repeat

    • Найти элемент с минимальной ошибкой
    • Выполнить операцию (удаление или слияние)
    • Пересчитать ошибку
  • Пока не достигнут нужный размер / качество сетки



Структура данных сетки

  • Структура данных сетки

    • Такая, чтобы было просто обходить соседей
  • Очередь с приоритетами (например, куча)

    • Быстрый доступ к элементу с минимальной ошибкой
      • В случае кучи: Θ(1) для нахождения максимума
      • O(log n) для извлечения максимума
    • Быстрое добавление
      • Для кучи: O(log n)




Операция упрощения: удаление вершины

  • Операция упрощения: удаление вершины

  • Мера ошибки: расстояние до плоскости

  • Можно предохранять особенности сетки



Оригинал (1972 вершины):

  • Оригинал (1972 вершины):



Результат упрощения (200 вершин)

  • Результат упрощения (200 вершин)



Результат умного упрощение (те же 200 вершин)

  • Результат умного упрощение (те же 200 вершин)



Schroeder et al. 1992

  • Schroeder et al. 1992



Исследовать локальную топологию/геометрию

  • Исследовать локальную топологию/геометрию

  • Посмотреть, какие вершины можно удалять

  • Повторять

    • Удалить вершину
    • Триангулировать образовавшуюся дырку
    • Обновить ошибку нужных вершин
  • Пока не выполнено условие упрощения (например, на размер сетки)





Простые вершины можно еще классифицировать:

  • Простые вершины можно еще классифицировать:

    • if (двугранный угол между соседними треугольниками > FeatureAngle),
    • then их общее ребро – характерное ребро


Пользователь задаёт Emax

  • Пользователь задаёт Emax

  • Простая вершина

    • Расстояние от неё до средней плоскости < Emax
  • Граничная вершина

    • Расстояние от вершины до нового граничного ребра < Emax


После удаления вершины образуется неплоская дырка (непланарный цикл)

  • После удаления вершины образуется неплоская дырка (непланарный цикл)

    • 2D алгоритмы в общем случае не сработают
    • Рекурсивно разбивать дырку
    • Следить за качеством получаемой триангуляции
  • Триангуляция может не сработать

    • Тогда не удаляем вершину


Эффективный

  • Эффективный

  • Легко запрограммировать и использовать

    • Немного параметров для настройки
  • Неплохая аппроксимация

  • Работает на очень больших сетках

  • Выбирает из начального мн-ва вершин (не двигает)

  • Ошибка не ограничена

    • Т.к. ошибка меряется только локально




Операция упрощения: коллапс ребра

    • Операция упрощения: коллапс ребра
    • Мера ошибки: расстояние, псевдо-глобальное
    • Также упрощает топологию


Найти точку, ближайшую к множеству плоскостей

  • Найти точку, ближайшую к множеству плоскостей

  • Сумма расстояний до множества плоскостей – это квадратичная форма – а значит, у нее есть минимум



Плоскость

  • Плоскость

    • Ax + By + Cz + D = 0, где A2 + B2 + C2 = 1
    • p = [A, B, C, D], v = [x, y, z, 1], v pT = 0
  • Выражается в виде квадратичной формы

  • p(v) = (v pT)2 = (v pT) (p vT) = v (pTp) vT = v KP vT





Цель: Пусть дано ребро e = (v1,v2), найти вершину v = (x,y,z,1) «слияния», которая минимизирует функцию

  • Цель: Пусть дано ребро e = (v1,v2), найти вершину v = (x,y,z,1) «слияния», которая минимизирует функцию

  • (v):

  • /x = /y = /z = 0

  • Для этого нужно решить следующую СЛУ:

  • Если решения нет, то выбираем середину



Выбирать ребра из сетки

  • Выбирать ребра из сетки

  • Или вершины, которые находятся близко – с заданным порогом



Посчитать QV для всех вершин сетки

  • Посчитать QV для всех вершин сетки

  • Найти все нужные пары вершин

  • Для каждой нужной пары (v1,v2) вычислить оптимальную вершину для слияния и её ошибку (v)

  • Разместить все пары в очереди с приоритетами (в соответствии с (v))

  • Пока не выполняется условие останова

    • Склеить ребро (v1,v2) с наименьшей ошибкой в v
    • Обновить очередь




Упрощение сеток

  • Упрощение сеток



Ошибка ограничена

  • Ошибка ограничена

  • Можно упрощать топологию

  • Получаются сетки высокого качества

  • Довольно эффективный

  • Проблемы с границами

  • Добавляет вершины, которых не было в оригинальной сетке



Вся информация по спецкурсу + презентации + текущие баллы выкладываются на http://aitricks.com/ru/research/course

  • Вся информация по спецкурсу + презентации + текущие баллы выкладываются на http://aitricks.com/ru/research/course