 | Эта статья требует дополнительных ссылок для проверки . ( июнь 2009 г. ) ( Узнайте, как и когда удалить это сообщение-шаблон ) |
В 3D компьютерной графики и твердотельного моделирования , A полигон сетки представляет собой набор вершин , край с и лица с , который определяет форму многогранного объекта. Грани обычно состоят из треугольников ( сетка треугольников ), четырехугольников ( четырехугольников ) или других простых выпуклых многоугольников ( n-угольников ), так как это упрощает рендеринг , но в более общем случае они также могут состоять из вогнутых многоугольников или даже многоугольников с отверстиями.
Изучение полигональных сеток - это большая область компьютерной графики (в частности, 3D компьютерной графики) и геометрического моделирования . Различные представления полигональных сеток используются для разных приложений и целей. Разнообразие операций, выполняемых с сетками, может включать: логическую логику , сглаживание , упрощение и многие другие. Также существуют алгоритмы для трассировки лучей , обнаружения столкновений и динамики твердого тела с полигональными сетками. Если вместо граней визуализируются края сетки, то модель становится каркасной .
Объемные сетки отличаются от полигональных сеток тем, что они явно представляют как поверхность, так и объем конструкции, в то время как полигональные сетки только явно представляют поверхность (объем неявный).
Существует несколько методов создания сетки , включая алгоритм марширующих кубов . [1]
Элементы [ править ]
Объекты, созданные с помощью полигональных сеток, должны содержать различные типы элементов. К ним относятся вершины, ребра, грани, многоугольники и поверхности. Во многих приложениях сохраняются только вершины, ребра и грани или полигоны. Средство визуализации может поддерживать только 3-сторонние грани, поэтому многоугольники должны быть построены из многих из них, как показано выше. Однако многие средства визуализации либо поддерживают четырехугольники и многоугольники с более высокими сторонами, либо могут на лету преобразовывать многоугольники в треугольники, что делает ненужным сохранение сетки в триангулированной форме.
Представления [ править ]
Полигональные сетки могут быть представлены различными способами с использованием различных методов для хранения данных о вершинах, ребрах и гранях. К ним относятся:
Каждое из представленных выше представлений имеет определенные преимущества и недостатки, которые дополнительно обсуждаются в Smith (2006). [2] Выбор структуры данных определяется приложением, требуемой производительностью, размером данных и выполняемыми операциями. Например, с треугольниками легче работать, чем с обычными многоугольниками, особенно в вычислительной геометрии . Для определенных операций необходим быстрый доступ к топологической информации, такой как ребра или соседние грани; для этого требуются более сложные структуры, такие как представление с крылатым краем. Для аппаратного рендеринга необходимы компактные простые структуры; таким образом, угловая таблица (треугольный веер) обычно включается в низкоуровневые API рендеринга, такие как DirectX и OpenGL..
Вершинно-вершинные сетки [ править ]
Сетки вершины-вершины представляют объект как набор вершин, соединенных с другими вершинами. Это простейшее представление, но оно не используется широко, поскольку информация о гранях и краях неявна. Таким образом, необходимо просмотреть данные, чтобы сгенерировать список лиц для рендеринга. Кроме того, операции с краями и гранями выполнить нелегко.
Однако сетки VV выигрывают от небольшого пространства для хранения и эффективного изменения формы. На приведенном выше рисунке показан четырехсторонний блок, представленный сеткой VV. Каждая вершина индексирует свои соседние вершины. Обратите внимание, что последние две вершины, 8 и 9 в верхней и нижней части «прямоугольного цилиндра», имеют четыре соединенных вершины, а не пять. Общая система должна иметь возможность обрабатывать произвольное количество вершин, связанных с любой данной вершиной.
Полное описание сеток VV см. В Smith (2006). [2]
Сетки грань-вершина [ править ]
Сетки граней и вершин представляют объект как набор граней и набор вершин. Это наиболее широко используемое представление сетки, которое обычно принимается современным графическим оборудованием.
Сетки грань-вершина улучшают VV-сетку для моделирования, поскольку они позволяют явно искать вершины грани и грани, окружающие вершину. На приведенном выше рисунке показан пример «коробчатого цилиндра» в виде сетки FV. Вершина v5 выделена, чтобы показать грани, которые ее окружают. Обратите внимание, что в этом примере у каждой грани должно быть ровно 3 вершины. Однако это не означает, что каждая вершина имеет одинаковое количество окружающих граней.
Для рендеринга список граней обычно передается в графический процессор как набор индексов вершин, а вершины отправляются как структуры положение / цвет / нормаль (на рисунке дано только положение). Это имеет то преимущество, что изменение формы, но не геометрии, может быть динамически обновлено путем простой повторной отправки данных вершины без обновления связности граней.
Моделирование требует легкого обхода всех структур. С помощью сеток грань-вершина легко найти вершины грани. Кроме того, список вершин содержит список граней, соединенных с каждой вершиной. В отличие от сеток VV, и грани, и вершины являются явными, поэтому определение местоположения соседних граней и вершин является постоянным временем. Однако края неявны, поэтому поиск по-прежнему необходим, чтобы найти все грани, окружающие данную грань. Другие динамические операции, такие как разделение или объединение грани, также затруднены с сетками грань-вершина.
Сетки с крыльями [ править ]
Представленные Баумгартом в 1975 году сетки с крылатыми краями явно представляют вершины, грани и ребра сетки. Это представление широко используется в программах моделирования для обеспечения максимальной гибкости при динамическом изменении геометрии сетки, поскольку операции разделения и объединения могут выполняться быстро. Их основной недостаток - большие требования к хранилищу и повышенная сложность из-за поддержки множества индексов. Хорошее обсуждение вопросов реализации сеток с крылатыми краями можно найти в книге Graphics Gems II .
Сетки с крылатыми краями решают проблему перехода от края к краю и предоставляют упорядоченный набор граней вокруг края. Для любого данного ребра количество исходящих ребер может быть произвольным. Чтобы упростить это, сетки с крылатыми краями предоставляют только четыре, ближайшие по часовой стрелке и против часовой стрелки края на каждом конце. Остальные кромки можно перемещать постепенно. Таким образом, информация для каждого края напоминает бабочку, отсюда и сетки с «крылатым краем». На приведенном выше рисунке показан "цилиндр-коробка" в виде сетки с крылатыми краями. Общие данные для ребра состоят из 2 вершин (конечных точек), 2 граней (с каждой стороны) и 4 ребер (крылатое ребро).
Рендеринг сеток с крылатыми краями для графического оборудования требует создания списка индексов лиц. Обычно это делается только при изменении геометрии. Сетки с крылатыми краями идеально подходят для динамической геометрии, такой как поверхности разделения и интерактивное моделирование, поскольку изменения в сетке могут происходить локально. Обход по сетке, который может потребоваться для обнаружения столкновений, может быть выполнен эффективно.
Подробнее см. Баумгарт (1975). [3]
Визуализация динамических сеток [ править ]
Сетки с крыльями - не единственное представление, которое позволяет динамически изменять геометрию. Новое представление, которое объединяет сетки с крылатыми ребрами и сетки граней с вершинами, - это динамическая сетка рендеринга , которая явно хранит как вершины грани и грани вершины (например, сетки FV), так и грани и вершины ребра ( как крылатый край).
Для визуализации динамических сеток требуется немного меньше места для хранения, чем для стандартных сеток с крылатыми краями, и их можно напрямую визуализировать с помощью графического оборудования, поскольку список граней содержит индекс вершин. Кроме того, переход от вершины к грани явный (постоянное время), как и от грани к вершине. Сетки RD не требуют четырех исходящих ребер, так как их можно найти, пройдя от ребра к грани, а затем повернувшись лицом к соседнему ребру.
Сетки RD извлекают выгоду из свойств сеток с крылатыми краями, позволяя динамически обновлять геометрию.
См. Более подробную информацию в Tobler & Maierhofer ( WSCG 2006). [4]
Резюме представления сетки [ править ]
| Операция | Вершина-вершина | Лицо-вершина | Крылатый край | Рендеринг динамический | |
|---|---|---|---|---|---|
| ВВ | Все вершины вокруг вершины | Явный | V → f1, f2, f3, ... → v1, v2, v3, ... | V → e1, e2, e3, ... → v1, v2, v3, ... | V → e1, e2, e3, ... → v1, v2, v3, ... |
| EF | Все края лица | F (a, b, c) → {a, b}, {b, c}, {a, c} | F → {a, b}, {b, c}, {a, c} | Явный | Явный |
| VF | Все вершины грани | F (a, b, c) → {a, b, c} | Явный | F → e1, e2, e3 → a, b, c | Явный |
| FV | Все грани вокруг вершины | Поиск пары | Явный | V → e1, e2, e3 → f1, f2, f3, ... | Явный |
| Электромобиль | Все ребра вокруг вершины | V → {v, v1}, {v, v2}, {v, v3}, ... | V → f1, f2, f3, ... → v1, v2, v3, ... | Явный | Явный |
| FE | Обе грани края | Список сравнить | Список сравнить | Явный | Явный |
| VE | Обе вершины ребра | 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: сводка операций представления сетки | |||||
В приведенной выше таблице явно указано, что операция может выполняться в постоянное время, поскольку данные хранятся непосредственно; сравнение списков указывает, что для выполнения операции необходимо выполнить сравнение двух списков; а парный поиск указывает, что поиск должен выполняться по двум индексам. Обозначение avg (V, V) означает среднее количество вершин, соединенных с данной вершиной; avg (E, V) означает среднее количество ребер, соединенных с данной вершиной, а avg (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 , Khronos Group | N / A | Стенды для " COLLA borative D ESIGN A 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 | N / A | Аналогичен формату 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) форматы. Включает данные для вершинной анимации и целевой анимации Morph (blendshape). Данные скелетной анимации в отдельном файле (.skeleton). |
| .veg | Тетраэдрическая сетка Vega FEM | Ерней Барбич | Вега ФЭМ | Открытый исходный код. Сохраняет тетраэдрическую сетку и ее свойства материала для моделирования методом конечных элементов. Доступны форматы ASCII (.veg) и двоичные (.vegb). |
| . z3d | Z3d | Олег Мелашенко | Zanoza Modeler | - |
| .vtk | Сетка ВТК | VTK , Kitware | ВТК , Paraview | Открытый, ASCII или двоичный формат, содержащий множество различных полей данных, включая точечные данные, данные ячеек и данные полей. |
| .l4d | Рисунок LAI4D | Лаборатория искусственного интеллекта для дизайна | LAI4D | Формат данных ASCII, описывающий иерархическое дерево сущностей. |
См. Также [ править ]
- B-реп.
- Оператор Эйлера
- Гиперграф
- Многообразие (сетка может быть многообразной или неоднородной)
- Подразделение сетки (метод добавления деталей к многоугольной сетке)
- Полигональное моделирование
- Полигонизатор
- Симплекс
- Т-образный шлиц
- Триангуляция (геометрия)
- Каркасная модель
Ссылки [ править ]
- ^ Лоренсен, Уильям Э .; Клайн, Харви Э. (1 августа 1987 г.). «Марширующие кубики: алгоритм построения трехмерной поверхности высокого разрешения». ACM SIGGRAPH Компьютерная графика . 21 (4): 163–169. CiteSeerX 10.1.1.545.613 . DOI : 10.1145 / 37402.37422 .
- ^ a b Колин Смит, О сетках вершин и вершин и их использовании в геометрическом и биологическом моделировании , ( PDF )
- ^ Брюс Баумгарт, Представление многогранника с крылатым краем для компьютерного зрения. Национальная компьютерная конференция, май 1975 г. «Использование многогранников в компьютерном зрении» . baumgart.org . Май 1975. Архивировано из оригинала на 2005-08-29 . Проверено 29 августа 2005 .
- ^ Tobler & Maierhofer, Структура данных сетки для рендеринга и подразделения. 2006 . ( PDF )
Внешние ссылки [ править ]
- Вайсштейн, Эрик В. "Симплициальный комплекс" . MathWorld .
- Вайсштейн, Эрик В. «Триангуляция» . MathWorld .
- OpenMesh с открытым исходным кодом, представляющий половинную сетку.
- Библиотека обработки полигональной сетки
