Геометричне моделювання деформації об’єкта політочковими перетвореннями на основі паралельних обчислень

Скорочена інформація про документ
dc.contributor.advisorСидоренко, Юлія Всеволодівна
dc.contributor.authorГородецький, Микола Вадимович
dc.date.accessioned2026-06-29T09:04:52Z
dc.date.available2026-06-29T09:04:52Z
dc.date.issued2026
dc.description.abstractГородецький М.В. Геометричне моделювання деформації об’єкта політочковими перетвореннями на основі паралельних обчислень. — Кваліфікаційна наукова праця на правах рукопису. Дисертація на здобуття наукового ступеня доктора філософії за спеціальністю 122 «Комп’ютерні науки». — Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського», Київ, 2026. Дисертаційне дослідження присвячене розв'язанню науково-прикладної проблеми геометричного моделювання нелінійних деформацій двовимірних та тривимірних об’єктів шляхом розвитку методу політочкових перетворень та реалізації високоефективних паралельних алгоритмів на гетерогенних обчислювальних системах. У цифрову епоху, коли фізична реальність дедалі тісніше переплітається з віртуальними моделями, адитивним виробництвом та концепціями Індустрії 4.0, геометричне моделювання стало фундаментальною основою авіакосмічної промисловості, біомедичної інженерії та систем віртуальної реальності. Проте фундаментальна проблема ефективної та точної деформації складних тривимірних об’єктів залишається відкритою. Існуючі методи часто досягають межі обчислювальних можливостей обладнання і виділеного бюджету на нього, коли зіштовхуються з викликами топологічної складності сучасних біонічних форм та вимогами до реального часу обробки масивів даних. Дослідження пропонує удосконалений підхід, що долає розрив між жорсткістю класичних параметричних підходів та непередбачуваністю нейромережевих методів, використовуючи потенціал сучасних архітектур паралельних обчислень. Актуальність дисертаційного дослідження, присвяченого розвитку методу політочкових перетворень, зумовлена необхідністю подолання розриву між жорсткістю класичних параметричних підходів та непередбачуваністю сучасних нейромережевих методів. Дослідження пропонує удосконалений погляд на проблему деформації простору, базуючись на критичному аналізі недоліків існуючих рішень та використовуючи потенціал сучасних архітектур паралельних обчислень. Доцільність роботи підтверджується нагальною потребою у створенні вітчизняних алгоритмічних ядер геометричного моделювання, здатних забезпечити незалежність та конкурентоспроможність у стратегічно важливих галузях науки та виробництва. Метою дослідження є розробка способів та алгоритмів політочкових перетворень для моделювання нелінійних деформацій двовимірних і тривимірних об'єктів з використанням гетерогенних обчислювальних систем. Об’єктом дослідження є процеси геометричного моделювання деформацій дво- і тривимірних об’єктів. У роботі проаналізовано сучасні методи деформації геометричних об’єктів, такі як: нейронні імпліцитні підходи: NeRF, Гаусовий сплаттінг, фізично обґрунтовані методи: метод скінчених елементів, модель мас‑пружинної системи, системи частинок, а також геометрично деформативні та інтерполяційні методи: політканинні перетворення, політочкові перетворення, побудова інтерполяційних векторних полів та симплексна інтерполяція. Встановлено, що нейронні імпліцитні методи відкривають нові можливості для процесінгу в режимі реального часу, але мають значні обчислювальні витрати та обмеження у збереженні топології, фізично обґрунтовані підходи забезпечують високу точність, але обмежені продуктивністю в реальному часі, тоді як геометрично деформативні методи дають керованість і адаптивність. Метод політочкових перетворень забезпечує низку вагомих переваг серед інших підходів: його базисом є скінченна множина контрольних точок, що дозволяє ефективно керувати деформацією цілого об’єкта, а математичний апарат зводиться до систем лінійних рівнянь, роблячи розрахунки простими й прозорими на відміну від «чорного ящика» нейронних методів. Цей апарат є природно паралельним і добре підходить для реалізації на багатоядерних та гетерогенних архітектурах, однак у вигляді послідовної реалізації на трикутникових сітках із мільйонами трикутників метод стає надто повільним, що й мотивувало розробку нових способів задання геометрії об’єкта та спеціалізованих схем паралелізації обчислень. На основі цього обґрунтовано використання методу політочкових перетворень як базового інструментарію, що має високий потенціал до паралелізації та точності. Для моделювання двовимірних об'єктів розроблено формалізований полігональний спосіб задання вихідної геометрії. Замість ресурсоємного відслідковування перетинів прямих для кожної точки, об’єкт подається у вигляді ланцюжка відрізків, що утворюють полігон. Це удосконалило спосіб задання геометричного об’єкта при двовимірних політочкових перетвореннях за рахунок введення стека для відслідковування входження прямих при відображенні заданої ламаної, що зберігає топологічну цілісність об’єкта. Експериментально показано, що залежність між кутом твірних прямих у вершині та зміщенням точки має майже лінійний характер без осциляцій, що підтверджує стабільність методу. Щоб з’єднати точки в цілісний об’єкт після деформації, запропоновано застосувати модифікований метод параметричної інтерполяції Гауса. Його вдосконалено завдяки адаптації варіативного параметра до форми кривої на кожному кроці, що дозволило суттєво (у понад 13 разів для тестових функцій) зменшити похибку інтерполяції. У тривимірному просторі вирішено ключову проблему втрати однозначності під час трансформації вершин трикутникової сітки. Вперше запропоновано спосіб представлення 3D-об’єкта, заданого трикутниковою сіткою на основі площин, що перетинаються, який дозволяє зберігати цілісність об’єкта після полiточкових перетворень. Проведено порівняльний аналіз трьох способів задання геометрії об'єкта. Встановлено, що метод представлення вершини як точки перетину площин дотичних трикутників забезпечує найкраще співвідношення між точністю реконструкції геометрії та обчислювальною ефективністю. Для розв'язання перевизначених систем лінійних алгебричних рівнянь, що виникають при перетині більше ніж трьох площин, застосовано метод найменших квадратів та псевдоінверсну матрицю Мура-Пенроуза. Виявлено проблему чисельної нестійкості у вироджених конфігураціях трикутникової сітки, для розв'язання якої успішно застосовано метод регуляризації Тихонова з експериментально обґрунтованим оптимальним параметром 10− = . Для забезпечення роботи алгоритмів у реальному часі з масивами даних до 80 млн полігонів обґрунтовано та реалізовано методи інженерного масштабування у гетерогенному середовищі. Встановлено, що продуктивність багатопотокових реалізацій на центральних процесорах обмежується архітектурою неоднорідного доступу до пам'яті. Розроблена NUMA-орієнтована стратегія з використанням OpenMP, яка дозволила прискорити виконання на 15–30% порівняно з базовою реалізацією. Подальше радикальне прискорення досягнуто шляхом розробки масовопаралельного алгоритму для графічних процесорів на базі архітектури CUDA. Застосовано концепцію «одна площина — один потік» та проведено глибоку оптимізацію на мікроархітектурному рівні: заміну високолатентних операцій подвійної точності на апаратні інструкції, зниження тиску на регістрову пам'ять та впровадження кешування масиву базисних точок у спільній пам'яті стрімінгового мультипроцесора. Це дозволило переорієнтувати задачу з тієї, що обмежена пропускною здатністю пам'яті, на таку, що обмежена швидкістю обчислень, і досягти прискорення у ~14.8 раза відносно послідовного виконання на ЦП та у 2.11 раза відносно оптимізованого 192-ядерного кластера. Практичного впровадження результати дисертаційного дослідження набули в ТОВ «БІ-ХАБ», де розроблене розширення для системи моделювання Blender застосовувалося для високоточної 3D-візуалізації банківських платіжних карток із відтворенням оптичних спецефектів. Отримані візуалізаційні результати використовувалися як еталонні 3D-моделі для виробництва. Загалом, результати апробації свідчать про практичну придатність запропонованих методів до впровадження в системи реального часу. Практична доцільність запропонованих методів визначається тим, що розроблене розширення: а) удосконалює спосіб задання геометричного об’єкта; б) забезпечує збереження цілісності 3D-об’єкта після політочкових перетворень; в) підвищує точність обчислень завдяки адаптації параметра в модифікованій Гаус-інтерполяції до локальної форми кривої; г) оптимізує обчислення політочкових перетворень, скорочуючи час підрахунків при збереженні цілісності геометрії. Сукупність зазначених властивостей має прикладну цінність для задач, де критичними є точність деформації, стабільність топології, цілісності та продуктивність, зокрема для застосувань, наближених до реального часу. Висновки, отримані на основі проведених досліджень, підтверджують доцільність їх використання.
dc.description.abstractotherHorodetskyi M.V. Geometric modeling of object deformation by polypoint transformations based on parallel computing. — Qualifying scientific work as a manuscript. Dissertation for the degree of Doctor of Philosophy in specialty 122 «Computer Science». — National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute", Kyiv, 2026. The dissertation research is devoted to solving the scientific and applied problem of geometric modeling of non-linear deformations of two-dimensional and threedimensional objects by developing the polypoint transformation method and implementing high-performance parallel algorithms on heterogeneous computing systems. In the digital era, where physical reality is increasingly intertwined with virtual models, additive manufacturing, and Industry 4.0 concepts, geometric modeling has become a fundamental cornerstone of the aerospace industry, biomedical engineering, and virtual reality systems. However, the fundamental problem of efficient and accurate deformation of complex three-dimensional objects remains open. Existing methods, facing the challenges of the topological complexity of modern bionic forms and real-time processing requirements for massive datasets, often reach the limits of hardware computational capabilities and the budgets allocated for them. The research proposes an enhanced approach that bridges the gap between the rigidity of classical parametric approaches and the unpredictability of neural network methods, leveraging the potential of modern parallel computing architectures. The relevance of the dissertation research, dedicated to the development of the polypoint transformation method, is driven by the need to bridge the gap between the rigidity of classical parametric approaches and the unpredictability of modern neural network methods. The research offers an enhanced perspective on the problem of space deformation, based on a critical analysis of the shortcomings of existing solutions and leveraging the potential of modern parallel computing architectures. The expediency of the work is confirmed by the urgent need to create national algorithmic kernels for geometric modeling capable of ensuring independence and competitiveness in strategically important fields of science and industry. The aim of the research is to develop methods and algorithms for polypoint transformations for modeling non-linear deformations of two-dimensional and threedimensional objects using heterogeneous computing systems. The object of the study is the processes of geometric modeling of deformations of two- and three-dimensional objects. The paper analyzes modern methods of geometric object deformation, such as: neural implicit approaches (NeRF, Gaussian Splatting); physically-based methods (the finite element method, the mass-spring system model, and particle systems); and geometric deformation and interpolation methods (poly-cloth transformations, polypoint transformations, the construction of interpolating vector fields, and simplex interpolation). It has been established that neural implicit methods open new possibilities for real-time processing but entail significant computational costs and limitations in topology preservation; physically-based approaches provide high accuracy but are limited by real-time performance, whereas geometric deformation methods offer controllability and adaptability. The polypoint transformation method provides a number of significant advantages over other approaches: its basis is a finite set of control points, which allows for effective control over the deformation of the entire object, and its mathematical apparatus is reduced to systems of linear equations, making the calculations simple and transparent, unlike the "black box" of neural methods. This apparatus is naturally parallel and well-suited for implementation on multicore and heterogeneous architectures; however, in the form of a sequential implementation on triangular meshes with millions of triangles, the method becomes excessively slow, which motivated the development of new methods for defining object geometry and specialized computational parallelization schemes. On this basis, the use of the polypoint transformation method is justified as a fundamental toolkit with high potential for parallelization and accuracy. A formalized polygonal method for specifying initial geometry has been developed for 2D object modeling. Instead of resource-intensive tracking of line intersections for each point, the object is represented as a chain of segments forming a polygon. This improved the method of specifying a geometric object in 2D polypoint transformations by introducing a stack to track line inclusion when mapping a given polyline, which preserves the topological integrity of the object. It is experimentally shown that the relationship between the angle of the generating lines at the vertex and the point displacement is nearly linear without oscillations, confirming the stability of the method. To connect points into a coherent object after deformation, a modified Gaussian parametric interpolation method is proposed. It has been enhanced by adapting a variable parameter α to the curve shape at each step, which significantly reduced the interpolation error (by more than 13 times for test functions). In three-dimensional space, the key problem of the loss of uniqueness during the transformation of triangular mesh vertices has been resolved. For the first time, a method for representing a 3D object defined by a triangular mesh based on intersecting planes has been proposed, which allows for the preservation of object integrity after polypoint transformations. A comparative analysis of three methods for specifying object geometry has been conducted. It was established that the method of representing a vertex as the intersection point of the planes of tangent triangles provides the best balance between geometry reconstruction accuracy and computational efficiency. To solve the overdetermined systems of linear algebraic equations that arise when more than three planes intersect, the least squares method and the Moore-Penrose pseudoinverse matrix were applied. A problem of numerical instability in degenerate triangular mesh configurations was identified, for the resolution of which Tikhonov regularization with an experimentally justified optimal parameter was successfully applied. To ensure real-time algorithm operation with datasets of up to 80 million polygons, engineering scaling methods in a heterogeneous environment have been substantiated and implemented. It was established that the performance of multi-threaded implementations on central processing units is limited by the Non-Uniform Memory Access (NUMA) architecture. A NUMA-aware strategy using OpenMP has been developed, which allowed for a 15–30% acceleration in execution compared to the baseline implementation. Further radical acceleration was achieved through the development of a massively parallel algorithm for graphics processing units based on the CUDA architecture. The «one plane — one thread» concept was applied, and deep optimization at the microarchitectural level was performed: replacing high-latency double-precision operations with hardware instructions, reducing register pressure, and implementing caching of the basis point array in the shared memory of the streaming multiprocessor. This allowed for the reorientation of the task from being memory-bound to being compute-bound, achieving a speedup of ~14.8 times relative to sequential CPU execution and 2.11 times relative to an optimized 192-core cluster. The results of the dissertation research have been practically implemented at "BIHUB" LLC, where the developed extension for the Blender modeling system was applied for high-precision 3D visualization of bank payment cards with the reproduction of optical special effects. The obtained visualization results were used as reference 3D models for production. Overall, the validation results indicate the practical suitability of the proposed methods for implementation in real-time systems. The practical expediency of the proposed methods is determined by the fact that the developed extension: a) improves the method of specifying a geometric object; b) ensures the preservation of 3D object integrity after polypoint transformations; c) increases calculation accuracy by adapting a parameter in the modified Gaussian interpolation to the local curve shape; d) optimizes the computation of polypoint transformations, reducing calculation time while maintaining geometric integrity. The combination of these properties provides applied value for tasks where deformation accuracy, topological stability, integrity, and performance are critical, particularly for near-real-time applications. The conclusions drawn from the research confirm the expediency of their application.
dc.format.extent216 с.
dc.identifier.citationГородецький, М. В. Геометричне моделювання деформації об’єкта політочковими перетвореннями на основі паралельних обчислень : дис. … д-ра філософії : 122 Комп’ютерні науки / Городецький Микола Вадимович. – Київ, 2026. – 216 с.
dc.identifier.urihttps://ela.kpi.ua/handle/123456789/81973
dc.language.isouk
dc.publisherКПІ ім. Ігоря Сікорського
dc.publisher.placeКиїв
dc.subjectгеометричне моделювання
dc.subjectмоделювання деформацій
dc.subjectмоделювання
dc.subjectполіточкові перетворення
dc.subjectінтерполяція
dc.subjectдискретна модель поверхні
dc.subjectкомп’ютерні інформаційні технології
dc.subjectперетворення простору
dc.subjectоптимізація
dc.subjectтрикутникові сітки
dc.subjectпаралельні обчислення
dc.subjectрозподілені системи
dc.subjectінформаційні системи
dc.subjectЗD-графіка
dc.subjectGPU
dc.subjectgeometric modeling
dc.subjectdeformation modeling
dc.subjectmodeling
dc.subjectpolypoint transformations
dc.subjectinterpolation
dc.subjectdiscrete surface model
dc.subjectcomputer information technologies
dc.subjectspace transformation
dc.subjectoptimization
dc.subjecttriangular meshes
dc.subjectparallel computing
dc.subjectdistributed systems
dc.subjectinformation systems
dc.subject3D graphics
dc.subject.udc004.94
dc.titleГеометричне моделювання деформації об’єкта політочковими перетвореннями на основі паралельних обчислень
dc.title.alternativeGeometric modeling of object deformation by polypoint transformations based on parallel computing
dc.typeThesis Doctoral

Файли

Контейнер файлів
Зараз показуємо 1 - 1 з 1
Ескіз
Назва:
Horodetskyi_dys.pdf
Розмір:
5.31 MB
Формат:
Adobe Portable Document Format
Завантажити
Ліцензійна угода
Зараз показуємо 1 - 1 з 1
Ескіз недоступний
Назва:
license.txt
Розмір:
8.98 KB
Формат:
Item-specific license agreed upon to submission
Опис:
Завантажити

Зібрання

Дисертації (ЦТЕ)
Дисертації (вільний доступ)