Цепной алгоритм сжатия 3D-моделей
Автор: Клячин В.А.
Журнал: Математическая физика и компьютерное моделирование @mpcm-jvolsu
Рубрика: Моделирование, информатика и управление
Статья в выпуске: 2 т.28, 2025 года.
Бесплатный доступ
В статье подробно излагается алгоритм сжатия информации о геометрическом строении трехмерных пространственных моделей и многомерных триангуляций, основанный на использовании смежности граней. Этот алгоритм преобразует набор граней 3D-модели в список цепочек (list of chains), последовательно расположенных в пространстве и смежных между собой. Сжатие информации происходит за счет отсутствия дублирования номеров вершин, образующих грани модели. Описанный в статье алгоритм состоит из трех основных частей. В первой части по множеству граней модели строится специальный граф граней – ребра графа соответствуют смежным граням. Используя алгоритм обхода вершин графа в глубину, этот граф разбивается на простые цепи. Вторая часть алгоритма преобразует каждую цепь графа в последовательность номеров вершин, участвующих в формировании граней этой цепочки. Третья часть алгоритма призвана выполнять обратное действие – переводить построенную последовательность номеров вершин обратно в наборы кортежей, состоящих из номеров вершин, соответствующих граням 3D-модели. Указанный алгоритм распространен и на случай пространственных триангуляций полигональных областей. Программная реализация алгоритма для частного случая 3D-моделей выполнена в виде встраиваемых модулей в программу Blender. Архивы модулей свободно доступны в репозитории автора статьи по адресу: https://github.com/KlyachinVA/LocFile.
Триангуляция, граф модели, цепь граней, обход графа в глубину, смежность граней
Короткий адрес: https://sciup.org/149148931
IDR: 149148931 | УДК: 514.76.3, 517.95 | DOI: 10.15688/mpcm.jvolsu.2025.2.2
Chain Algorithm for Compressing 3D-Models
The article describes in detail the algorithm for compressing information about the geometric structure of three-dimensional spatial models and multidimensional triangulations based on the use of adjacency of faces. This algorithm transforms a set of 3D-model faces into a list of chains sequentially located in space and adjacent to each other. Information compression occurs due to the absence of duplication of the numbers of vertices that form the model faces. The algorithm described in the article consists of three main parts. In the first part, a special graph of faces is constructed based on the set of model faces, the edges of the graph correspond to adjacent faces. Using the algorithm of traversal of graph vertices in depth, this graph is divided into simple chains. The second part of the algorithm transforms each chain of the graph into a sequence of numbers of vertices participating in the formation of the faces of this chain. The third part of the algorithm is designed to perform the reverse action – to translate the constructed sequence of vertex numbers back into sets of tuples consisting of the numbers of vertices that form the faces of the 3D-model. This algorithm is also extended to the case of spatial triangulations of polygonal areas. The software implementation of the algorithm for the special case of 3D-models is made in the form of built-in modules in the Blender program. The archives of the modules are freely available in the repository of the author of the article at https://github.com/KlyachinVA/LocFile.
