Многоугольная сетка - Polygon mesh
 | Эта статья нужны дополнительные цитаты для проверка. (Июнь 2009 г.) (Узнайте, как и когда удалить этот шаблон сообщения) |
В 3D компьютерная графика и твердотельное моделирование, а полигональная сетка это собрание вершины, крайs и лицоs который определяет форму многогранник объект. Лица обычно состоят из треугольники (треугольная сетка ), четырехугольники (квадроциклы) или другие простые выпуклые многоугольники (n-угольники ), поскольку это упрощает рендеринг, но также может состоять из вогнутые многоугольники или даже многоугольники с отверстиями.
Изучение многоугольник сетки - это большое подполе компьютерная графика (в частности, 3D компьютерная графика) и геометрическое моделирование. Различные представления полигональных сеток используются для разных приложений и целей. Разнообразие операций, выполняемых с сетками, может включать: Логическая логика, сглаживание, упрощение, и много других. Также существуют алгоритмы для трассировка лучей, обнаружение столкновения, и динамика твердого тела с многоугольными сетками. Если вместо граней визуализируются края сетки, то модель становится каркасная модель.
Объемные сетки отличаются от полигональных сеток тем, что они явно представляют как поверхность, так и объем конструкции, а полигональные сетки только явно представляют поверхность (объем неявный).
Существует несколько методов для создание сетки, в том числе маршевые кубики алгоритм.[1]
Элементы
Объекты, созданные с помощью полигональных сеток, должны содержать различные типы элементов. К ним относятся вершины, ребра, грани, многоугольники и поверхности. Во многих приложениях сохраняются только вершины, ребра и грани или полигоны. Средство визуализации может поддерживать только 3-сторонние грани, поэтому многоугольники должны быть построены из многих из них, как показано выше. Однако многие рендереры либо поддерживают четырехугольники и многоугольники с более высокой стороной, либо могут на лету конвертировать многоугольники в треугольники, что делает ненужным сохранение сетки в триангулированный форма.
Представления
Полигональные сетки могут быть представлены различными способами с использованием различных методов для хранения данных о вершинах, ребрах и гранях. К ним относятся:
Каждое из представленных выше представлений имеет свои преимущества и недостатки, которые дополнительно обсуждаются в Smith (2006).[2]Выбор структуры данных определяется приложением, требуемой производительностью, размером данных и выполняемыми операциями. Например, с треугольниками легче работать, чем с обычными многоугольниками, особенно в вычислительная геометрия. Для определенных операций необходим быстрый доступ к топологической информации, такой как ребра или соседние грани; это требует более сложных структур, таких как представление крылатого края. Для аппаратного рендеринга необходимы компактные простые структуры; таким образом, угловая таблица (веер треугольника) обычно включается в низкоуровневые API рендеринга, такие как DirectX и OpenGL.
Вершинно-вершинные сетки
Вершинно-вершинные сетки представляют объект как набор вершин, соединенных с другими вершинами. Это простейшее представление, но оно не используется широко, поскольку информация о гранях и краях неявна. Таким образом, необходимо просмотреть данные, чтобы создать список лиц для рендеринга. Кроме того, операции с краями и гранями выполнить нелегко.
Однако сетки VV выигрывают от небольшого пространства для хранения и эффективного изменения формы. На приведенном выше рисунке показан четырехсторонний блок, представленный сеткой VV. Каждая вершина индексирует свои соседние вершины. Обратите внимание, что последние две вершины, 8 и 9 в верхней и нижней части «прямоугольного цилиндра», имеют четыре соединенных вершины, а не пять. Общая система должна быть способна обрабатывать произвольное количество вершин, связанных с любой данной вершиной.
Полное описание сеток VV см. В Smith (2006).[2]
Сетки грань-вершина
Сетки грань-вершина представляют объект как набор граней и набор вершин. Это наиболее широко используемое представление сетки, которое обычно принимается современным графическим оборудованием.
Сетки грань-вершина улучшают VV-сетку для моделирования в том, что они позволяют явно искать вершины лица и грани, окружающие вершину. На приведенном выше рисунке показан пример «коробчатого цилиндра» в виде сетки FV. Вершина v5 выделена, чтобы показать грани, которые ее окружают. Обратите внимание, что в этом примере у каждой грани должно быть ровно 3 вершины. Однако это не означает, что у каждой вершины одинаковое количество окружающих граней.
Для рендеринга список граней обычно передается в графический процессор как набор индексов вершин, а вершины отправляются как структуры положение / цвет / нормаль (на рисунке дано только положение). Это имеет то преимущество, что изменения формы, но не геометрии, могут быть динамически обновлены путем простой повторной отправки данных вершины без обновления связности граней.
Моделирование требует легкого обхода всех структур. С помощью сеток грань-вершина легко найти вершины грани. Также список вершин содержит список граней, соединенных с каждой вершиной. В отличие от сеток VV, и грани, и вершины являются явными, поэтому определение местоположения соседних граней и вершин является постоянным временем. Однако края неявны, поэтому поиск по-прежнему необходим, чтобы найти все грани, окружающие данную грань. Другие динамические операции, такие как разделение или объединение грани, также затруднены с сетками грань-вершина.
Сетки с крыльями
Представленный Баумгартом в 1975 году, сетки с крыльями явным образом представляют вершины, грани и ребра сетки. Это представление широко используется в программах моделирования для обеспечения максимальной гибкости при динамическом изменении геометрии сетки, поскольку операции разделения и объединения могут выполняться быстро. Их основной недостаток - большие требования к хранилищу и повышенная сложность из-за поддержки множества индексов. Хорошее обсуждение вопросов реализации сеток Winged-edge можно найти в книге. Графика Gems II.
Сетки с крыльями решают проблему перехода от края к краю и предоставляют упорядоченный набор граней вокруг края. Для любого данного ребра количество исходящих ребер может быть произвольным. Чтобы упростить это, сетки с крылатыми краями предоставляют только четыре, ближайшие по часовой стрелке и против часовой стрелки края на каждом конце. Остальные кромки можно перемещать постепенно. Таким образом, информация для каждого ребра напоминает бабочку, отсюда и сетки с «крылатым краем». На приведенном выше рисунке показан "цилиндр коробки" в виде сетки с крылатыми краями. Общие данные для ребра состоят из 2 вершин (конечных точек), 2 граней (с каждой стороны) и 4 ребер (крылатое ребро).
Визуализация сеток с крылатыми краями для графического оборудования требует создания списка индексов лиц. Обычно это делается только при изменении геометрии. Сетки с крылатыми краями идеально подходят для динамической геометрии, такой как поверхности разделения и интерактивное моделирование, поскольку изменения в сетке могут происходить локально. Обход по сетке, который может потребоваться для обнаружения столкновений, может быть выполнен эффективно.
Подробнее см. Баумгарт (1975).[3]
Отрисовка динамических сеток
Сетки с крыльями - не единственное представление, которое позволяет динамически изменять геометрию. Новое представление, которое объединяет сетки с крылатыми ребрами и сетки граней с вершинами, - это визуализировать динамическую сетку, который явно хранит как вершины грани, так и грани вершины (например, сетки FV), а также грани и вершины ребра (например, winged-edge).
Для визуализации динамических сеток требуется немного меньше места для хранения, чем для стандартных сеток с крылатыми краями, и их можно напрямую визуализировать с помощью графического оборудования, поскольку список граней содержит индекс вершин. Кроме того, переход от вершины к грани явный (постоянное время), как и от грани к вершине. Сетки RD не требуют четырех исходящих ребер, поскольку их можно найти, пройдя от ребра к грани, а затем повернувшись лицом к соседнему ребру.
Сетки RD выигрывают от свойств сеток с крылатыми краями, позволяя динамически обновлять геометрию.
См. Tobler & Maierhofer (WSCG 2006) для более подробной информации.[4]
Резюме представления сетки
| Операция | Вершина-вершина | Лицо-вершина | Крылатый край | Рендеринг динамический | |
|---|---|---|---|---|---|
| V-V | Все вершины вокруг вершины | Явный | V → f1, f2, f3, ... → v1, v2, v3, ... | V → e1, e2, e3, ... → v1, v2, v3, ... | V → e1, e2, e3, ... → v1, v2, v3, ... |
| E-F | Все края лица | F (a, b, c) → {a, b}, {b, c}, {a, c} | F → {a, b}, {b, c}, {a, c} | Явный | Явный |
| V-F | Все вершины грани | F (a, b, c) → {a, b, c} | Явный | F → e1, e2, e3 → a, b, c | Явный |
| F-V | Все грани вокруг вершины | Поиск пары | Явный | V → e1, e2, e3 → f1, f2, f3, ... | Явный |
| E-V | Все ребра вокруг вершины | V → {v, v1}, {v, v2}, {v, v3}, ... | V → f1, f2, f3, ... → v1, v2, v3, ... | Явный | Явный |
| F-E | Обе грани края | Список сравнить | Список сравнить | Явный | Явный |
| V-E | Обе вершины ребра | E (a, b) → {a, b} | E (a, b) → {a, b} | Явный | Явный |
| Flook | Найти грань с заданными вершинами | F (a, b, c) → {a, b, c} | Установить пересечение v1, v2, v3 | Установить пересечение v1, v2, v3 | Установить пересечение v1, v2, v3 |
| Размер хранилища | V * ср (В, В) | 3F + V * ср. (F, V) | 3F + 8E + V * ср (E, V) | 6F + 4E + V * ср (E, V) | |
| Пример с 10 вершинами, 16 гранями, 24 ребрами: | |||||
| 10 * 5 = 50 | 3*16 + 10*5 = 98 | 3*16 + 8*24 + 10*5 = 290 | 6*16 + 4*24 + 10*5 = 242 | ||
| Рисунок 6: сводка операций представления сетки | |||||
В приведенной выше таблице явный указывает, что операция может выполняться в постоянное время, поскольку данные хранятся непосредственно; список сравнить указывает, что для выполнения операции необходимо выполнить сравнение двух списков; и поиск пары указывает, что поиск должен выполняться по двум индексам. Обозначение ср (В, В) означает среднее количество вершин, соединенных с данной вершиной; ср (E, V) означает среднее количество ребер, соединенных с данной вершиной, и ср (F, V) - среднее количество граней, соединенных с данной вершиной.
Обозначение «V → f1, f2, f3, ... → v1, v2, v3, ...» описывает, что для выполнения операции требуется обход нескольких элементов. Например, чтобы получить «все вершины вокруг данной вершины V» с использованием сетки грань-вершина, необходимо сначала найти грани вокруг данной вершины V, используя список вершин. Затем из этих граней используйте список граней, чтобы найти вершины вокруг них. Обратите внимание, что в сетках с крылатыми краями явно хранится почти вся информация, а другие операции всегда сначала переходят к краю, чтобы получить дополнительную информацию. Сетки вершины-вершины - единственное представление, в котором явно хранятся соседние вершины данной вершины.
По мере того, как представления сетки становятся более сложными (слева направо в сводке), объем явно сохраненной информации увеличивается. Это дает более прямой, постоянный по времени доступ к обходу и топологии различных элементов, но за счет увеличения накладных расходов и места для правильного обслуживания индексов.
На рисунке 7 показан информация о подключении для каждого из четырех методов, описанных в этой статье. Существуют и другие представления, например, полуреберные и угловые таблицы. Это все варианты того, как вершины, грани и ребра индексируют друг друга.
Как правило, сетки грань-вершина используются всякий раз, когда объект должен быть визуализирован на графическом оборудовании, которое не изменяет геометрию (связность), но может деформировать или изменять форму (положение вершин), например рендеринг в реальном времени статических или изменяющихся объектов. При изменении геометрии используются динамические сетки с крыльями или рендеринг, например, в пакетах интерактивного моделирования или для вычисления поверхностей подразделения. Вершинно-вершинные сетки идеальны для эффективных сложных изменений геометрии или топологии, если аппаратный рендеринг не имеет значения.
Другие представления
Форматы файлов
Есть много разных форматы файлов для хранения данных полигональной сетки. Каждый формат наиболее эффективен при использовании по назначению его создателя. Некоторые из этих форматов представлены ниже:
| Суффикс файла | Название формата | Организация (ы) | Программа (ы) | Описание |
|---|---|---|---|---|
| .сырой | Сырая сетка | Неизвестный | Разные | Открытый формат только ASCII. Каждая строка содержит 3 вершины, разделенные пробелами, чтобы сформировать треугольник, например: X1 Y1 Z1 X2 Y2 Z2 X3 Y3 Z3 |
| .смешивать | Формат файла Blender | Blender Foundation | Блендер 3D | Открытый исходный код, только двоичный формат |
| .fbx | Формат Autodesk FBX | Autodesk | Разные | Собственный. Существуют двоичные и ASCII-спецификации. |
| .3ds | Файл 3ds Max | Autodesk | 3ds Max | Распространенный, но устаревший формат с жесткими 16-битными ограничениями на количество вершин и граней. Ни стандартизирован, ни хорошо документирован, но раньше был «стандартом де-факто» для обмена данными. |
| .dae | Биржа цифровых активов (COLLADA) | Sony Computer Entertainment, Хронос Групп | Нет данных | Означает "КОЛЛАборативный Dдизайн Аctivity ». Универсальный формат, предназначенный для предотвращения несовместимости. |
| .dgn | Файл MicroStation | Bentley Systems | MicroStation | Существует два формата файлов dgn: до версии 8 и версии 8 (V8). |
| .3dm | Файл Rhino | Роберт Макнил и партнеры | Носорог 3D | |
| .dxf, .dwg | Формат обмена чертежами | Autodesk | AutoCAD | |
| .obj | OBJ волнового фронта | Технологии волнового фронта | Разные | Формат ASCII, описывающий трехмерную геометрию. Вершины всех граней упорядочены против часовой стрелки, поэтому нормали граней неявны. Гладкие нормали указываются для каждой вершины. |
| .ply | Формат файла многоугольника | Стэндфордский Университет | Разные | Двоичный и ASCII |
| .pmd | Данные Polygon Movie Maker | Ю Хигучи | МикуМикуТанец | Собственный двоичный формат файла для хранения геометрии модели гуманоида с информацией о оснастке, материалах и физике. |
| .stl | Стереолитография Формат | 3D системы | Много | Двоичный формат и формат ASCII, изначально разработанный для помощи в ЧПУ. |
| .amf | Формат файлов аддитивного производства | ASTM International | Нет данных | Подобен формату STL, но с добавленной поддержкой цвета, материала и созвездий. |
| .wrl | Язык моделирования виртуальной реальности | Консорциум Web3D | Веб-браузеры | Стандарт ISO 14772-1: 1997 |
| .wrz | VRML сжатый | Консорциум Web3D | Веб-браузеры | |
| .x3d, .x3db, .x3dv | Расширяемый 3D | Консорциум Web3D | Веб-браузеры | Основанный на XML, открытый исходный код, бесплатный, расширяемый и совместимый; также поддерживает информацию о цвете, текстуре и сцене. Стандарт ISO 19775/19776/19777 |
| .x3dz, .x3dbz, .x3dvz | X3D сжатый двоичный файл | Консорциум Web3D | Веб-браузеры | |
| .c4d | Cinema 4D файл | МАКСОН | CINEMA 4D | |
| .lwo | Файл 3D-объекта LightWave | NewTek | LightWave 3D | |
| .smb | SCOREC apf | RPI SCOREC | ПУМИ | Параллельные адаптивные неструктурированные трехмерные сетки с открытым исходным кодом для рабочих процессов моделирования на основе PDE. |
| .msh | Gmsh Mesh | Разработчики GMsh | Проект GMsh | Открытый исходный код, предоставляющий описание сетки ASCII для линейных и полиномиально интерполированных элементов в 1-3 измерениях. |
| .mesh | OGRE XML | Команда разработчиков OGRE | OGRE, чистый базовый | Открытый исходный код. Доступны двоичный (.mesh) и ASCII (.mesh.xml) форматы. Включает данные для вершинной анимации и Морфинг целевой анимации (blendshape). Скелетная анимация данные в отдельном файле (.skeleton). |
| .veg | Тетраэдрическая сетка Vega FEM | Ерней Барбич | Вега ФЭМ | Открытый исходный код. Сохраняет тетраэдрическую сетку и ее свойства материала для моделирования методом конечных элементов. Доступны форматы ASCII (.veg) и двоичные (.vegb). |
| .z3d | Z3d | Олег Мелашенко | Zanoza Modeler | - |
| .vtk | Сетка ВТК | VTK, Kitware | VTK, Paraview | Открытый, ASCII или двоичный формат, содержащий множество различных полей данных, включая данные точек, данные ячеек и данные полей. |
| .l4d | Рисунок LAI4D | Лаборатория искусственного интеллекта для дизайна | LAI4D | Формат данных ASCII, описывающий иерархическое дерево сущностей. |
Смотрите также
- B-rep
- Оператор Эйлера
- Гиперграф
- Многообразие (сетка может быть многообразной или неоднородной)
- Подразделение сетки (техника добавления деталей к полигональной сетке)
- Полигональное моделирование
- Полигонизатор
- Симплекс
- Т-образный шлиц
- Триангуляция (геометрия)
- Каркасная модель
Рекомендации
- ^ Lorensen, William E .; Клайн, Харви Э. (1 августа 1987 г.). «Марширующие кубики: алгоритм построения трехмерной поверхности высокого разрешения». ACM SIGGRAPH Компьютерная графика. 21 (4): 163–169. CiteSeerX 10.1.1.545.613. Дои:10.1145/37402.37422.
- ^ а б Колин Смит, О сетках вершин и вершин и их использовании в геометрическом и биологическом моделировании, (PDF )
- ^ Брюс Баумгарт, Представление многогранников с крылатыми краями для компьютерного зрения. Национальная компьютерная конференция, май 1975 г. «Использование многогранников в компьютерном зрении». baumgart.org. Май 1975 г. Архивировано с оригинал на 2005-08-29. Получено 2005-08-29.
- ^ Тоблер и Майерхофер, Структура данных сетки для рендеринга и разделения. 2006 г.. (PDF )
внешняя ссылка
- Вайсштейн, Эрик В. «Симплициальный комплекс». MathWorld.
- Вайсштейн, Эрик В. «Триангуляция». MathWorld.
- OpenMesh представление полуреберной сетки с открытым исходным кодом.
- Библиотека обработки полигональной сетки