Введение в методы переменного уровня детализации полигональных сеток Алексей Игнатенко

Основные темы Что такое уровень детализации Что такое уровень детализации Статические и динамические методы Статические и динамические методы Видозависимость Видозависимость Реализация Реализация По материалам учебного курса при конфереренции ACM SIGGRAPH 2001 Что такое уровень детализации Что такое уровень детализации Статические и динамические методы Статические и динамические методы Видозависимость Видозависимость Реализация Реализация По материалам учебного курса при конфереренции ACM SIGGRAPH 2001

Мотивация Очень важен интерактивный рендеринг геометрических данных большого объема Научная и медицинская визуализацияНаучная и медицинская визуализация CADCAD СимуляторыСимуляторы ИгрыИгры Очень важен интерактивный рендеринг геометрических данных большого объема Научная и медицинская визуализацияНаучная и медицинская визуализация CADCAD СимуляторыСимуляторы ИгрыИгры

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

Пример модели 10 миллионов треугольников

Пример модели 80 миллионов треугольников

Уровень детализации: Основная идея Возможное решение: Возможное решение: Упрощение геометрии малых или удаленных объектовУпрощение геометрии малых или удаленных объектов Известно как Level of Detail (LOD)Известно как Level of Detail (LOD) –Так же известно как polygonal simplification, geometric simplification, mesh reduction, multiresolution modeling,… Возможное решение: Возможное решение: Упрощение геометрии малых или удаленных объектовУпрощение геометрии малых или удаленных объектов Известно как Level of Detail (LOD)Известно как Level of Detail (LOD) –Так же известно как polygonal simplification, geometric simplification, mesh reduction, multiresolution modeling,…

Уровень детализации: традиционный подход Создание уровней детализации объектов (LODs)

Уровень детализации: традиционный подход Более удаленные объекты используют более грубые уровни детализации

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

Преимущества статического LOD Легко программируется Создание и визуализация разделены Создание LODов не учитывает ограничений интерактивной визуализацииСоздание LODов не учитывает ограничений интерактивной визуализации От визуализации требуется только выбрать нужный LODОт визуализации требуется только выбрать нужный LOD Легко программируется Создание и визуализация разделены Создание LODов не учитывает ограничений интерактивной визуализацииСоздание LODов не учитывает ограничений интерактивной визуализации От визуализации требуется только выбрать нужный LODОт визуализации требуется только выбрать нужный LOD

Преимущества статического LOD Позволяет на полную использовать аппаратное ускорение Статические LODы можно легко упаковать в дисплейные списки, вершинные массивы, страйпы и т.д.Статические LODы можно легко упаковать в дисплейные списки, вершинные массивы, страйпы и т.д. Это позволяет намного ускорить визуализацию, т.к. такие структуры рисуются на современной аппаратуре в 3-5 раз быстрее чем неорганизованные полигоныЭто позволяет намного ускорить визуализацию, т.к. такие структуры рисуются на современной аппаратуре в 3-5 раз быстрее чем неорганизованные полигоны Позволяет на полную использовать аппаратное ускорение Статические LODы можно легко упаковать в дисплейные списки, вершинные массивы, страйпы и т.д.Статические LODы можно легко упаковать в дисплейные списки, вершинные массивы, страйпы и т.д. Это позволяет намного ускорить визуализацию, т.к. такие структуры рисуются на современной аппаратуре в 3-5 раз быстрее чем неорганизованные полигоныЭто позволяет намного ускорить визуализацию, т.к. такие структуры рисуются на современной аппаратуре в 3-5 раз быстрее чем неорганизованные полигоны

Недостатки статического LOD Вопрос: Почему же возникает необходимость использовать что-то кроме статического LOD? Ответ: Потому что иногда статический LOD не подходит для радикального упрощения геометрии Например: ЛандшафтыЛандшафты Трехмерные изоповерхностиТрехмерные изоповерхности Данные с трехмерных дистанционных сканеровДанные с трехмерных дистанционных сканеров Сложные CAD-моделиСложные CAD-модели Вопрос: Почему же возникает необходимость использовать что-то кроме статического LOD? Ответ: Потому что иногда статический LOD не подходит для радикального упрощения геометрии Например: ЛандшафтыЛандшафты Трехмерные изоповерхностиТрехмерные изоповерхности Данные с трехмерных дистанционных сканеровДанные с трехмерных дистанционных сканеров Сложные CAD-моделиСложные CAD-модели

Радикальное упрощение Для радикального упрощения геометрии: сложные объекты должны быть разбиты на простыесложные объекты должны быть разбиты на простые простые – скомбинированыпростые – скомбинированы Это очень сложно или невозможно при статическом подходе Так что же можно сделать? Для радикального упрощения геометрии: сложные объекты должны быть разбиты на простыесложные объекты должны быть разбиты на простые простые – скомбинированыпростые – скомбинированы Это очень сложно или невозможно при статическом подходе Так что же можно сделать?

Динамический уровень детализации Отличие от традиционного подхода: Статический LOD: создание уровней заранее перед визуализациейСтатический LOD: создание уровней заранее перед визуализацией Динамический LOD: создание структуры данных, из которой геометрия с нужной детализацией может быть извлечена в реальном времени во время визуализации.Динамический LOD: создание структуры данных, из которой геометрия с нужной детализацией может быть извлечена в реальном времени во время визуализации. Отличие от традиционного подхода: Статический LOD: создание уровней заранее перед визуализациейСтатический LOD: создание уровней заранее перед визуализацией Динамический LOD: создание структуры данных, из которой геометрия с нужной детализацией может быть извлечена в реальном времени во время визуализации.Динамический LOD: создание структуры данных, из которой геометрия с нужной детализацией может быть извлечена в реальном времени во время визуализации.

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

Динамический уровень детализации: преимущества Более плавная визуализация Переключение между статическими LODами может привести к эффекту «перепрыгивания»Переключение между статическими LODами может привести к эффекту «перепрыгивания» Динамические LOD позволяют плавно изменять уровень разбиения, устраняя этот эффектДинамические LOD позволяют плавно изменять уровень разбиения, устраняя этот эффект Более плавная визуализация Переключение между статическими LODами может привести к эффекту «перепрыгивания»Переключение между статическими LODами может привести к эффекту «перепрыгивания» Динамические LOD позволяют плавно изменять уровень разбиения, устраняя этот эффектДинамические LOD позволяют плавно изменять уровень разбиения, устраняя этот эффект

Динамический уровень детализации: преимущества Поддерживает прогрессивную передачуПоддерживает прогрессивную передачу Поддерживает видозависимые (view-dependent) LODПоддерживает видозависимые (view-dependent) LOD –Можно использовать текущие параметры виртуальной камеры для определения лучшего представления для данного вида. Поддерживает прогрессивную передачуПоддерживает прогрессивную передачу Поддерживает видозависимые (view-dependent) LODПоддерживает видозависимые (view-dependent) LOD –Можно использовать текущие параметры виртуальной камеры для определения лучшего представления для данного вида.

Видозависимый LOD: варианты применения Видозависимость используется для того, чтобы Показывать близкие часть объекта с большей точностью, чем удаленныеПоказывать близкие часть объекта с большей точностью, чем удаленные Показывать границы объекта или наиболее интересные части с большей точностьюПоказывать границы объекта или наиболее интересные части с большей точностью Показывать больше деталей там, куда смотрит пользователь и меньше в области периферического зренияПоказывать больше деталей там, куда смотрит пользователь и меньше в области периферического зрения Видозависимость используется для того, чтобы Показывать близкие часть объекта с большей точностью, чем удаленныеПоказывать близкие часть объекта с большей точностью, чем удаленные Показывать границы объекта или наиболее интересные части с большей точностьюПоказывать границы объекта или наиболее интересные части с большей точностью Показывать больше деталей там, куда смотрит пользователь и меньше в области периферического зренияПоказывать больше деталей там, куда смотрит пользователь и меньше в области периферического зрения

Динамический уровень детализации: пример

Иерархический LOD Видозависимые LOD могут решить проблему с большими объектами Иерархические LOD решают проблему маленьких объектов Разделение объектов на составляющиеРазделение объектов на составляющие На достаточном расстоянии упрощение составляющих, а не объектовНа достаточном расстоянии упрощение составляющих, а не объектов Иерархический LOD подразумевает алгоритмы, модифицирующие топологию объекта Видозависимые LOD могут решить проблему с большими объектами Иерархические LOD решают проблему маленьких объектов Разделение объектов на составляющиеРазделение объектов на составляющие На достаточном расстоянии упрощение составляющих, а не объектовНа достаточном расстоянии упрощение составляющих, а не объектов Иерархический LOD подразумевает алгоритмы, модифицирующие топологию объекта

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

Алгоритмы видозависимых LOD Разработано достаточно много хороших алгоритмов видозависимых LOD Далее для примера будет рассмотрен алгоритм VDS (View-Dependent simplification) Разработано достаточно много хороших алгоритмов видозависимых LOD Далее для примера будет рассмотрен алгоритм VDS (View-Dependent simplification)

Обзор метода VDS Обзор метода VDS: На эпапе препроцессинга строится дерево вершин - иерархическая кластеризация вершин данной полигональной сеткиНа эпапе препроцессинга строится дерево вершин - иерархическая кластеризация вершин данной полигональной сетки Во время рисования кластеры разворачиваются и сворачиваются в зависимости от положения виртуальной камерыВо время рисования кластеры разворачиваются и сворачиваются в зависимости от положения виртуальной камеры –Кластеры, которые становятся слишком маленькими, сворачиваются, уменьшая общее число треугольников Обзор метода VDS: На эпапе препроцессинга строится дерево вершин - иерархическая кластеризация вершин данной полигональной сеткиНа эпапе препроцессинга строится дерево вершин - иерархическая кластеризация вершин данной полигональной сетки Во время рисования кластеры разворачиваются и сворачиваются в зависимости от положения виртуальной камерыВо время рисования кластеры разворачиваются и сворачиваются в зависимости от положения виртуальной камеры –Кластеры, которые становятся слишком маленькими, сворачиваются, уменьшая общее число треугольников

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

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

Дерево вершин: сворачивание и разворачивание Сворачивание узла дерева заменяет ассоциированные с ним вершины на вершину-заместительСворачивание узла дерева заменяет ассоциированные с ним вершины на вершину-заместитель Разворачивание узла заменяет заместитель на ассоциированные вершиныРазворачивание узла заменяет заместитель на ассоциированные вершины Сворачивание узла дерева заменяет ассоциированные с ним вершины на вершину-заместительСворачивание узла дерева заменяет ассоциированные с ним вершины на вершину-заместитель Разворачивание узла заменяет заместитель на ассоциированные вершиныРазворачивание узла заменяет заместитель на ассоциированные вершины

Дерево вершин: пример

Дерево вершин: livetris и subtris 2 категории треугольников

Дерево вершин: livetris и subtris Ключевое наблюдение: Для каждого узла дерева subtris может быть вычислено заранееДля каждого узла дерева subtris может быть вычислено заранее Для каждого узла дерева livetris можно поддерживать в реальном времени.Для каждого узла дерева livetris можно поддерживать в реальном времени. Ключевое наблюдение: Для каждого узла дерева subtris может быть вычислено заранееДля каждого узла дерева subtris может быть вычислено заранее Для каждого узла дерева livetris можно поддерживать в реальном времени.Для каждого узла дерева livetris можно поддерживать в реальном времени.

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

Оптимизация Методы оптимизации Асинхронное упрощение сеткиАсинхронное упрощение сетки –Распараллеливание алгоритма Использование пространственной связностиИспользование пространственной связности –За малый промежуток времени сцена меняется мало Поддержание связанной геометрии в памятиПоддержание связанной геометрии в памяти –Оптимизация для аппаратных ускорителей Методы оптимизации Асинхронное упрощение сеткиАсинхронное упрощение сетки –Распараллеливание алгоритма Использование пространственной связностиИспользование пространственной связности –За малый промежуток времени сцена меняется мало Поддержание связанной геометрии в памятиПоддержание связанной геометрии в памяти –Оптимизация для аппаратных ускорителей

Проблема: перехлестывание сетки

Проблема: искажение сетки (mesh foldovers)

Видозависимый LOD vs. Статического LOD Видозависимый LOD предпочтительнее, когда Модели содержат большое число небольших объектов (напр. ландшафт)Модели содержат большое число небольших объектов (напр. ландшафт) Упрощение должно выполняться автоматически (напр. CAD)Упрощение должно выполняться автоматически (напр. CAD) Необходима гибкая система видозависимых критериев упрощения сеткиНеобходима гибкая система видозависимых критериев упрощения сетки Видозависимый LOD предпочтительнее, когда Модели содержат большое число небольших объектов (напр. ландшафт)Модели содержат большое число небольших объектов (напр. ландшафт) Упрощение должно выполняться автоматически (напр. CAD)Упрощение должно выполняться автоматически (напр. CAD) Необходима гибкая система видозависимых критериев упрощения сеткиНеобходима гибкая система видозависимых критериев упрощения сетки

Видозависимый LOD vs. Статического LOD Статический LOD является лучшим выбором, так как обладает свойствами Простая для реализации модельПростая для реализации модель Малая загрузка CPUМалая загрузка CPU Проще использовать аппаратуруПроще использовать аппаратуру Статический LOD является лучшим выбором, так как обладает свойствами Простая для реализации модельПростая для реализации модель Малая загрузка CPUМалая загрузка CPU Проще использовать аппаратуруПроще использовать аппаратуру

Видозависимый LOD vs. Статического LOD Приложения, которые используют Статический LODСтатический LOD –Видеоигры –Симуляторы Видозависимый LODВидозависимый LOD –Инструменты CAD –Научные и медицинские приложения –Виртуальные музеи Приложения, которые используют Статический LODСтатический LOD –Видеоигры –Симуляторы Видозависимый LODВидозависимый LOD –Инструменты CAD –Научные и медицинские приложения –Виртуальные музеи

Вопросы?