Крылатая грань: структура данных для представления полигональных сеток.
Winged edge
Крылатая грань: структура данных для представления полигональных сеток в компьютерной графике. Быстрый доступ к геометрии и топологии модели. Эффективные алгоритмы.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Введение
Структура данных для представления полигональных сеток в компьютерной памяти.
Data structure for representing polygon meshes in computer memory
В компьютерной графике крылатая реберная структура данных — это способ представления полигональных сеток в компьютерной памяти. Это тип представления на основе границ, который описывает как геометрию, так и топологию модели. Используются три типа записей: записи вершин, записи рёбер и записи граней. Имея ссылку на запись ребра, можно получить ответы на несколько типов запросов о смежности (запросов о соседних рёбрах, вершинах и гранях) за постоянное время. Такая информация о смежности полезна для алгоритмов, таких как подразделение поверхностей.
In computer graphics, the winged edge data structure is a way to represent polygon meshes in computer memory. It is a type of boundary representation and describes both the geometry and topology of a model. Three types of records are used: vertex records, edge records, and face records. Given a reference to an edge record, one can answer several types of adjacency queries (queries about neighboring edges, vertices and faces) in constant time. This kind of adjacency information is useful for algorithms such as subdivision surface.
Особенности
Структура данных «крылатый край» явно описывает геометрию и топологию граней, ребер и вершин в тех случаях, когда три или более поверхностей сходятся и пересекаются по общему ребру. Порядок организован таким образом, что поверхности упорядочены против часовой стрелки относительно внутренней ориентации ребра пересечения. Более того, данное представление позволяет обрабатывать численно неустойчивые ситуации, как показано ниже. Структура данных «крылатый край» обеспечивает быстрый переход между гранями, ребрами и вершинами благодаря явно связанной структуре сети. Она позволяет выполнять запросы на смежность за постоянное время с небольшими затратами памяти. Эта детализированная форма задания неструктурированной сетки отличается от более простых спецификаций многоугольных сеток, таких как список узлов и элементов, или подразумеваемая связность регулярной сетки. Альтернативой структуре данных «крылатый край» является структура данных «полукрай».
The winged edge data structure explicitly describes the geometry and topology of faces, edges, and vertices when three or more surfaces come together and meet at a common edge. The ordering is such that the surfaces are ordered counter clockwise with respect to the innate orientation of the intersection edge. Moreover the representation allows numerically unstable situations like that depicted below. The winged edge data structure allows for quick traversal between faces, edges, and vertices due to the explicitly linked structure of the network. It serves adjacency queries in constant time with little storage overhead. This rich form of specifying an unstructured grid is in contrast to simpler specifications of polygon meshes such as a node and element list, or the implied connectivity of a regular grid. An alternative to the winged edge data structure is the Half edge data structure.