Введение
Набор многоугольников для определения 3D-модели.
В 3D-компьютерной графике и твердотельном моделировании, многоугольная сетка представляет собой совокупность вершин, ребер и граней, определяющих форму многогранного объекта. Грани обычно состоят из треугольников (треугольная сетка), четырехугольников (квады) или других простых выпуклых многоугольников (n-гонов), поскольку это упрощает рендеринг, но они также могут состоять из вогнутых многоугольников или даже многоугольников с отверстиями. Изучение многоугольных сеток является обширной областью компьютерной графики (в частности, 3D-компьютерной графики) и геометрического моделирования. Для различных приложений и целей используются различные представления многоугольных сеток. Разнообразие операций, выполняемых над сетками, может включать в себя: булеву логику (конструктивную геометрию твердых тел), сглаживание, упрощение и многое другое. Существуют также алгоритмы для трассировки лучей, обнаружения столкновений и динамики твердых тел с использованием многоугольных сеток. Если ребра сетки отображаются вместо граней, модель становится каркасной моделью. Объемные сетки отличаются от многоугольных тем, что они явно представляют как поверхность, так и объем структуры, в то время как многоугольные сетки явно представляют только поверхность (объем подразумевается). Существует несколько методов генерации сеток, включая алгоритм марширующих кубов.
Представительства
Полигональные сетки могут быть представлены различными способами, используя различные методы для хранения данных о вершинах, ребрах и гранях. К ним относятся:
Сетки вершин-граней – простой список вершин и набор многоугольников, ссылающихся на используемые ими вершины. Крылатые реберные сетки, в которых каждое ребро указывает на две вершины, две грани и четыре (по часовой и против часовой стрелки) ребра, которые к ним примыкают. Крылатые реберные сетки обеспечивают обход поверхности за постоянное время, но требуют больше памяти. Полуреберные сетки – аналогичны крылатым реберным сеткам, за исключением того, что используется только половина информации об обходе ребер (см. OpenMesh). Четырехугольные реберные сетки, которые хранят ребра, полуребра и вершины без ссылок на многоугольники. Многоугольники неявно заданы в представлении и могут быть найдены путем обхода структуры. Требования к памяти аналогичны полуреберным сеткам. Угловые таблицы, которые хранят вершины в предопределенной таблице, так что обход таблицы неявно определяет многоугольники. По сути, это веер треугольников, используемый в аппаратном графическом рендеринге. Представление более компактно и эффективно для извлечения многоугольников, но операции изменения многоугольников выполняются медленно. Кроме того, угловые таблицы не полностью представляют сетки. Для представления большинства сеток требуется несколько угловых таблиц (вееров треугольников). Сетки вершина-вершина – сетка, представляющая только вершины, указывающие на другие вершины. Информация о ребрах и гранях неявно задана в представлении. Каждое из вышеперечисленных представлений имеет свои преимущества и недостатки, которые более подробно обсуждаются в Smith (2006). Выбор структуры данных определяется областью применения, требуемой производительностью, размером данных и выполняемыми операциями. Например, с треугольниками легче работать, чем с общими многоугольниками, особенно в вычислительной геометрии. Для определенных операций необходим быстрый доступ к топологической информации, такой как ребра или соседние грани; это требует более сложных структур, таких как крылатое реберное представление. Для аппаратного рендеринга требуются компактные и простые структуры; поэтому угловая таблица (веер треугольников) обычно встраивается в низкоуровневые графические API, такие как DirectX и OpenGL.
quad edge meshes which store edges, half edges, and vertices without any reference to polygons. The polygons are implicit in the representation, and may be found by traversing the structure. Memory requirements are similar to half edge meshes. Corner tables which store vertices in a predefined table, such that traversing the table implicitly defines polygons. This is in essence the triangle fan used in hardware graphics rendering. The representation is more compact, and more efficient to retrieve polygons, but operations to change polygons are slow. Furthermore, corner tables do not represent meshes completely. Multiple corner tables (triangle fans) are needed to represent most meshes. Vertex vertex meshesA "VV" mesh represents only vertices, which point to other vertices. Both the edge and face information is implicit in the representation. However, the simplicity of the representation does not allow for many efficient operations to be performed on meshes. Each of the representations above have particular advantages and drawbacks, further discussed in Smith (2006). The choice of the data structure is governed by the application, the performance required, size of the data, and the operations to be performed. For example, it is easier to deal with triangles than general polygons, especially in computational geometry. For certain operations it is necessary to have a fast access to topological information such as edges or neighboring faces; this requires more complex structures such as the winged edge representation. For hardware rendering, compact, simple structures are needed; thus the corner table (triangle fan) is commonly incorporated into low level rendering APIs such as DirectX and OpenGL.
Оши вертикально-вертикальные
Вершинные сетки представляют объект как набор вершин, соединенных с другими вершинами. Это самое простое представление, но оно не получило широкого распространения, поскольку информация о гранях и ребрах является неявной. Следовательно, для генерации списка граней для рендеринга необходимо последовательно просматривать данные. Кроме того, операции с ребрами и гранями выполнять затруднительно. Однако вершинные сетки отличаются небольшим объемом памяти и эффективным изменением формы. На рисунке выше показан четырехсторонний параллелепипед, представленный вершинной сеткой. Каждая вершина содержит индексы своих соседних вершин. Последние две вершины, 8 и 9, расположенные в верхней и нижней центральных точках "цилиндрического параллелепипеда", имеют четыре соединенных вершины вместо пяти. Общая система должна быть способна обрабатывать любое количество вершин, соединенных с любой заданной вершиной. Подробное описание вершинных сеток можно найти в работе Smith (2006).
Регенерировать динамические сетки
Крылатые ребра – не единственный способ представления, позволяющий динамически изменять геометрию. Новое представление, объединяющее крылатые ребра и сети вершин граней, – это динамическая сеть рендеринга, которая явно хранит как вершины граней и грани вершин (как в FV-сетях), так и грани и вершины ребер (как в крылатых ребрах). Динамические сети рендеринга требуют немного меньше памяти, чем стандартные крылатые ребра, и могут быть непосредственно отрисованы графическим оборудованием, поскольку список граней содержит индексы вершин. Кроме того, переход от вершины к грани является явным (за постоянное время), как и от грани к вершине. Динамические сети рендеринга не требуют хранения четырех исходящих ребер, поскольку их можно найти, переходя от ребра к грани, а затем от грани к соседнему ребру. Динамические сети рендеринга используют преимущества крылатых ребер, позволяя динамически обновлять геометрию. Подробности см. в работе Tobler & Maierhofer (WSCG 2006).
Резюме представления сетчатки
Операция Vertex вершинаFace вершинаWinged edge рендерингDynamicV VAll вершины вокруг вершиныExplicitV → f1, f2, f3, → v1, v2, v3, V → e1, e2, e3, → v1, v2, v3, V → e1, e2, e3, → v1, v2, v3, E FAll ребра граниF(a,b,c) → {a,b}, {b,c}, {a,c}F → {a,b}, {b,c}, {a,c}ExplicitExplicitV FAll вершины граниF(a,b,c) → {a,b,c}ExplicitF → e1, e2, e3 → a, b, cExplicitF VAll грани вокруг вершиныПоиск парыExplicitV → e1, e2, e3 → f1, f2, f3, ExplicitE VAll ребра вокруг вершиныV → {v,v1}, {v,v2}, {v,v3}, V → f1, f2, f3, → v1, v2, v3, ExplicitExplicitF EОбе грани ребраСравнение списковСравнениеExplicitExplicitV EОбе вершины ребраE(a,b) → {a,b}E(a,b) → {a,b}ExplicitExplicitFПоискНайти грань с заданными вершинамиF(a,b,c) → {a,b,c}Пересечение множеств v1,v2,v3Пересечение множеств v1,v2,v3Пересечение множеств v1,v2,v3Размер хранилищаV*avg(V,V)3F + V*avg(F,V)3F + 8E + V*avg(E,V)6F + 4E + V*avg(E,V)Пример с 10 вершинами, 16 гранями, 24 ребрами:10 * 5 = 503*16 + 10*5 = 983*16 + 8*24 + 10*5 = 2906*16 + 4*24 + 10*5 = 242Рисунок 6: сводка операций представления сетки
В приведенной выше таблице "explicit" указывает, что операция может быть выполнена за постоянное время, поскольку данные хранятся непосредственно; "list compare" указывает, что для выполнения операции необходимо выполнить сравнение списков между двумя списками; а "pair search" указывает, что необходимо выполнить поиск по двум индексам. Обозначение avg(V,V) означает среднее число вершин, соединенных с данной вершиной; avg(E,V) означает среднее число ребер, соединенных с данной вершиной, а avg(F,V) – среднее число граней, соединенных с данной вершиной. Обозначение "V → f1, f2, f3, → v1, v2, v3, " описывает, что для выполнения операции требуется переход через несколько элементов. Например, чтобы получить "все вершины вокруг данной вершины V" с помощью сетки вершин-граней, сначала необходимо найти грани вокруг данной вершины V с помощью списка вершин. Затем, используя список граней, найдите вершины вокруг них. Крылатые краевые сетки явно хранят почти всю информацию, а другие операции всегда первыми переходят к ребру, чтобы получить дополнительную информацию. Сети вершин-вершин являются единственным представлением, которое явно хранит соседние вершины данной вершины. По мере того, как представления сетки становятся более сложными (слева направо в сводке), количество явно хранимой информации увеличивается. Это обеспечивает более прямой, постоянный доступ к пересечению и топологии различных элементов, но за счет увеличения накладных расходов и пространства при правильном поддержании индексов. На рисунке 7 показана информация о связности для каждого из четырех методов, описанных в этой статье. Существуют и другие представления, такие как полуребра и угловые таблицы. Это все варианты того, как вершины, грани и ребра индексируют друг друга. Как правило, сетки вершин-граней используются всякий раз, когда объект должен быть отображен на графическом оборудовании, которое не меняет геометрию (связность), но может деформироваться или изменять форму (позиции вершин), например, при рендеринге в реальном времени статических или изменяющих форму объектов. Крылатые краевые или динамические рендеринговые сетки используются при изменениях геометрии, например, в интерактивных пакетах моделирования или для вычисления поверхностей подразделения. Сети вершин-вершин идеально подходят для эффективных, сложных изменений геометрии или топологии, если только не требуется аппаратного рендеринга.
Другие представления
Потоковые сетки хранят грани в упорядоченном, но независимом виде, что позволяет передавать сетку по частям. Порядок граней может быть пространственным, спектральным или основан на других свойствах сетки. Потоковые сетки позволяют визуализировать очень большую сетку даже в процессе её загрузки. Прогрессивные сетки передают данные о вершинах и гранях с возрастающим уровнем детализации. В отличие от потоковых сеток, прогрессивные сетки передают общую форму всего объекта, но с низкой детализацией. Дополнительные данные, новые ребра и грани, постепенно увеличивают детализацию сетки. Нормальные сетки передают прогрессивные изменения сетки в виде набора нормальных смещений от базовой сетки. При использовании этой техники ряд текстур представляет желаемые инкрементные модификации. Нормальные сетки компактны, поскольку для выражения смещения требуется только одно скалярное значение. Однако для создания текстур смещения требуется сложная серия преобразований.
Форматы файлов
Существует множество различных форматов файлов для хранения данных полигональной сетки. Каждый формат наиболее эффективен, когда используется в целях, предусмотренных его создателем. Популярные форматы включают fbx, dae, obj и stl. Ниже приведена таблица некоторых из этих форматов:
File suffix Format name Organization(s) Program(s) Description raw Raw mesh Unknown Various Open, ASCII only format. Each line contains 3 vertices, separated by spaces, to form a triangle, like so: X1 Y1 Z1 X2 Y2 Z2 X3 Y3 Z3 blend Blender File Format Blender Foundation Blender 3D Open source, binary only format fbx Autodesk FBX Format Autodesk Various Proprietary. Binary and ASCII specifications exist. .3ds 3ds Max File Autodesk 3ds Max A common but outdated format with hard 16 bit limits on the number of vertices and faces. Neither standardised nor well documented, but used to be a "de facto standard" for data exchange. dae Digital Asset Exchange (COLLADA) Sony Computer Entertainment, Khronos Group N/A Stands for "COLLAborative Design Activity". A universal format designed to prevent incompatibility. dgn MicroStation File Bentley Systems MicroStation There are two dgn file formats: pre version 8 and version 8 (V8) .3dm Rhino File Robert McNeel & Associates Rhinoceros 3D dxf, dwg Drawing Exchange Format Autodesk AutoCAD obj Wavefront OBJ Wavefront Technologies Various ASCII format describing 3D geometry. All faces' vertices are ordered counter clockwise, making facet normals implicit. Smooth normals are specified per vertex. ply Polygon File Format Stanford University Various Binary and ASCII pmd Polygon Movie Maker data Yu Higuchi MikuMikuDance Proprietary binary file format for storing humanoid model geometry with rigging, material, and physics information. stl Stereolithography Format 3D Systems Many Binary and ASCII format originally designed to aid in CNC. amf Additive Manufacturing File Format ASTM International N/A Like the STL format, but with added native color, material, and constellation support. wrl Virtual Reality Modeling Language Web3D Consortium Web Browsers ISO Standard 14772 1:1997 wrz VRML Compressed Web3D Consortium Web Browsers x3d, x3db, x3dv Extensible 3D Web3D Consortium Web Browsers XML based, open source, royalty free, extensible, and interoperable; also supports color, texture, and scene information. ISO Standard 19775/19776/19777 x3dz, x3dbz, x3dvz X3D Compressed Binary Web3D Consortium Web Browsers c4d Cinema 4D File Maxon CINEMA 4D lwo LightWave 3D object File NewTek LightWave 3D smbSCOREC apfRPI SCORECPUMIOpen source parallel adaptive unstructured 3D meshes for PDE based simulation workflows. msh Gmsh Mesh GMsh Developers GMsh Project Open source, providing an ASCII mesh description for linear and polynomially interpolated elements in 1 to 3 dimensions. mesh OGRE XML OGRE Development Team OGRE, purebasic Open Source. Binary (. mesh) and ASCII (. mesh. xml) format available. Includes data for vertex animation and Morph target animation (blendshape). Skeletal animation data in separate file (. skeleton). veg Vega FEM tetrahedral mesh Jernej Barbič Vega FEM Open Source. Stores a tetrahedral mesh and its material properties for FEM simulation. ASCII (. veg) and binary (. vegb) formats available. z3d Z3d Oleg Melashenko Zanoza Modeler vtk VTK mesh VTK, Kitware VTK, Paraview Open, ASCII or binary format that contains many different data fields, including point data, cell data, and field data. l4d LAI4D drawing Laboratory of Artificial Intelligence for Design LAI4D ASCII data format that describes a hierarchical tree of entities.
Суффикс файла | Название формата | Организация(ы) | Программа(ы) | Описание
------- | -------- | -------- | -------- | --------
raw | Raw mesh | Неизвестный | Различные | Открытый, только формат ASCII. Каждая строка содержит 3 вершины, разделенные пробелами, для формирования треугольника, например: X1 Y1 Z1 X2 Y2 Z2 X3 Y3 Z3
blend | Blender File Format | Blender Foundation | Blender 3D | Открытый исходный код, только двоичный формат.
fbx | Autodesk FBX Format | Autodesk | Различные | Запатентованный. Существуют бинарные и ASCII спецификации.
.3ds | 3ds Max File | Autodesk | 3ds Max | Распространенный, но устаревший формат с жесткими 16-битными ограничениями на количество вершин и граней. Не стандартизован и плохо документирован, но ранее был "де-факто стандартом" для обмена данными.
dae | Digital Asset Exchange (COLLADA) | Sony Computer Entertainment, Khronos Group | N/A | Расшифровывается как "COLLAborative Design Activity" (совместная деятельность по проектированию). Универсальный формат, предназначенный для предотвращения несовместимости.
dgn | MicroStation File | Bentley Systems | MicroStation | Существует два формата файлов dgn: до версии 8 и версии 8 (V8).
.3dm | Rhino File | Robert McNeel & Associates | Rhinoceros 3D |
dxf, dwg | Drawing Exchange Format | Autodesk | AutoCAD |
obj | Wavefront OBJ | Wavefront Technologies | Различные | Формат ASCII, описывающий 3D-геометрию. Вершины всех граней упорядочены против часовой стрелки, что делает нормали граней неявными. Гладкие нормали задаются для каждой вершины.
ply | Polygon File Format | Stanford University | Различные | Бинарный и ASCII форматы.
pmd | Polygon Movie Maker data | Yu Higuchi | MikuMikuDance | Запатентованный двоичный формат файла для хранения геометрии гуманоидных моделей с данными о риггинге, материалах и физике.
stl | Stereolithography Format | 3D Systems | Многие | Бинарный и ASCII форматы, первоначально разработанные для поддержки ЧПУ.
amf | Additive Manufacturing File Format | ASTM International | N/A | Подобен формату STL, но с добавленной поддержкой цвета, материала и созвездий.
wrl | Virtual Reality Modeling Language | Web3D Consortium | Веб-браузеры | Стандарт ISO 14772 1:1997.
wrz | VRML Compressed | Web3D Consortium | Веб-браузеры |
x3d, x3db, x3dv | Extensible 3D | Web3D Consortium | Веб-браузеры | Основан на XML, открытый исходный код, без роялти, расширяемый и совместимый; также поддерживает цвет, текстуру и информацию о сцене. Стандарт ISO 19775/19776/19777.
x3dz, x3dbz, x3dvz | X3D Compressed Binary | Web3D Consortium | Веб-браузеры |
c4d | Cinema 4D File | Maxon | CINEMA 4D |
lwo | LightWave 3D object File | NewTek | LightWave 3D |
smbSCOREC apfRPI SCORECPUMIO | | | | Открытый исходный код параллельных адаптивных неструктурированных 3D сеток для рабочих процессов моделирования на основе PDE.
msh | Gmsh Mesh | GMsh Developers | GMsh Project | Открытый исходный код, предоставляющий описание сетки в формате ASCII для линейных и полиномиально интерполированных элементов в 1–3 измерениях.
mesh | OGRE XML | OGRE Development Team | OGRE, purebasic | Открытый исходный код. Доступны бинарный (.mesh) и ASCII (.mesh.xml) форматы. Включает данные для анимации вершин и анимации Morph-целей (blendshape). Данные скелетной анимации хранятся в отдельном файле (.skeleton).
veg | Vega FEM tetrahedral mesh | Jernej Barbič | Vega FEM | Открытый исходный код. Хранит тетраэдрическую сетку и ее свойства материала для моделирования методом конечных элементов. Доступны форматы ASCII (.veg) и бинарный (.vegb).
z3d | Z3d | Oleg Melashenko | Zanoza Modeler |
vtk | VTK mesh | VTK, Kitware | VTK, Paraview | Открытый, формат ASCII или двоичный, содержащий различные поля данных, включая точечные данные, данные ячеек и данные полей.
l4d | LAI4D drawing | Laboratory of Artificial Intelligence for Design | LAI4D | Формат данных ASCII, описывающий иерархическое дерево сущностей.
File suffix Format name Organization(s) Program(s) Description raw Raw mesh Unknown Various Open, ASCII only format. Each line contains 3 vertices, separated by spaces, to form a triangle, like so: X1 Y1 Z1 X2 Y2 Z2 X3 Y3 Z3 blend Blender File Format Blender Foundation Blender 3D Open source, binary only format fbx Autodesk FBX Format Autodesk Various Proprietary. Binary and ASCII specifications exist. .3ds 3ds Max File Autodesk 3ds Max A common but outdated format with hard 16 bit limits on the number of vertices and faces. Neither standardised nor well documented, but used to be a "de facto standard" for data exchange. dae Digital Asset Exchange (COLLADA) Sony Computer Entertainment, Khronos Group N/A Stands for "COLLAborative Design Activity". A universal format designed to prevent incompatibility. dgn MicroStation File Bentley Systems MicroStation There are two dgn file formats: pre version 8 and version 8 (V8) .3dm Rhino File Robert McNeel & Associates Rhinoceros 3D dxf, dwg Drawing Exchange Format Autodesk AutoCAD obj Wavefront OBJ Wavefront Technologies Various ASCII format describing 3D geometry. All faces' vertices are ordered counter clockwise, making facet normals implicit. Smooth normals are specified per vertex. ply Polygon File Format Stanford University Various Binary and ASCII pmd Polygon Movie Maker data Yu Higuchi MikuMikuDance Proprietary binary file format for storing humanoid model geometry with rigging, material, and physics information. stl Stereolithography Format 3D Systems Many Binary and ASCII format originally designed to aid in CNC. amf Additive Manufacturing File Format ASTM International N/A Like the STL format, but with added native color, material, and constellation support. wrl Virtual Reality Modeling Language Web3D Consortium Web Browsers ISO Standard 14772 1:1997 wrz VRML Compressed Web3D Consortium Web Browsers x3d, x3db, x3dv Extensible 3D Web3D Consortium Web Browsers XML based, open source, royalty free, extensible, and interoperable; also supports color, texture, and scene information. ISO Standard 19775/19776/19777 x3dz, x3dbz, x3dvz X3D Compressed Binary Web3D Consortium Web Browsers c4d Cinema 4D File Maxon CINEMA 4D lwo LightWave 3D object File NewTek LightWave 3D smbSCOREC apfRPI SCORECPUMIOpen source parallel adaptive unstructured 3D meshes for PDE based simulation workflows. msh Gmsh Mesh GMsh Developers GMsh Project Open source, providing an ASCII mesh description for linear and polynomially interpolated elements in 1 to 3 dimensions. mesh OGRE XML OGRE Development Team OGRE, purebasic Open Source. Binary (. mesh) and ASCII (. mesh. xml) format available. Includes data for vertex animation and Morph target animation (blendshape). Skeletal animation data in separate file (. skeleton). veg Vega FEM tetrahedral mesh Jernej Barbič Vega FEM Open Source. Stores a tetrahedral mesh and its material properties for FEM simulation. ASCII (. veg) and binary (. vegb) formats available. z3d Z3d Oleg Melashenko Zanoza Modeler vtk VTK mesh VTK, Kitware VTK, Paraview Open, ASCII or binary format that contains many different data fields, including point data, cell data, and field data. l4d LAI4D drawing Laboratory of Artificial Intelligence for Design LAI4D ASCII data format that describes a hierarchical tree of entities.