Розробка моделі єдиного алгоритмічного середовища для розв’язання комплексу задач адитивного виробництва
Тип публікації :
Дисертація
Дата випуску :
13 травня 2026 р.
Автор(и) :
Осіпьонок, Максим Миколайович
Науковий(і) керівник(и)/редактор(и) :
Мова основного тексту :
Ukrainian
eKNUTSHIR URL :
Цитування :
[APA 7] Осіпьонок, М. М. (2026). Розробка моделі єдиного алгоритмічного середовища для розв’язання комплексу задач адитивного виробництва [Дис. доктора філософії, Київський національний університет імені Тараса Шевченка]. eKNUTSHIR. https://ir.library.knu.ua/handle/15071834/35540
[ДСТУ] Осіпьонок М. М. Розробка моделі єдиного алгоритмічного середовища для розв’язання комплексу задач адитивного виробництва : дис. … доктора філософії : 122 Комп’ютерні науки. Київ, 2026. 182 с. URL: https://ir.library.knu.ua/handle/15071834/35540
Осіпьонок М.М. Розробка моделі єдиного алгоритмічного середовища для розв’язання комплексу задач адитивного виробництва. – Кваліфікаційна наукова праця на правах рукопису.
Дисертація на здобуття наукового ступеня доктора філософії за спеціальністю 122 - Комп’ютерні науки. – Київський національний університет імені Тараса Шевченка, Київ, 2026.
Дисертаційна робота присвячена розробці концепції моделі єдиного алгоритмічного середовища (МЄАС) для розв’язування комплексу алгоритмічних задач, що постають в процесу планування адитивного виробництва (АВ), тобто під час підготовки однієї або кількох цифрових тривимірних моделей до 3D-друку. Увага акцентується на наступному наборі задач, які постають при використанні більшості існуючих технологій АВ: генеруванні мешів, виборі оптимальної орієнтації для моделей та їх розміщення всередині робочої області принтера, генерування опорних конструкцій, слайсинг та побудова траєкторії друку.
Сфера застосування адитивного виробництва в сучасному світі поступово розширюється з інструменту швидкого прототипування до повноцінної компоненти складних виробничих ланцюжків. Перевагою АВ є здатність долати обмеження традиційних методів виробництва, таких як лиття або фрезування, шляхом створення деталі з внутрішніми каналами ти сітчастими структурами, в результаті чого надруковані деталі міцнішими при меншій вазі. В таких індустріях промисловості як автомобілебудування та аерокосмічна галузь, застосування деталей виготовлених шляхом адитивного виробництва дозволяє збільшити вантажопідйомність та знизити витрати пального. Сучасні геополітичні виклики та логістичні кризи підкреслюють ще одну перевагу АВ – можливість використання моделі «виробництво на вимогу», за якої створення необхідної деталі відбувається за лічені години локально в місці її використання, що є критично важливим у військовій справі, енергетиці та медицині.
На сьогодні існує велика кількість різноманітних технологій АВ, що орієнтовані на друк різними матеріалами – пластиком, керамікою, металами тощо. В основу цих технологій покладені різні фізичні явища, однак об’єднує їх процес планування АВ, що неодмінно передує безпосередньому друку моделі. Різні технології АВ накладають різні вимоги та обмеження щодо вхідних даних, тому розв’язання задачі планування АВ не може бути зведене до єдиного універсального алгоритму.
Програмні рішення, що існують на сьогодні, можна розділити на три категорії: відкриті системи масового сегмента (наприклад Cura та PrusaSlicer), промислові платформи (наприклад Autodesk Netfabb та Siemens NX) та пропрієтарні рішення від виробників обладнання (наприклад Formlabs PreForm та EOS Build).
Представники першої категорії є відкритими програмними продуктами та мають відносно низький поріг входу, що зробило їх стандартом для настільних 3D-принтерів аматорського сегмента. В межах своєї спеціалізації ці системи пропонують повноцінний робочий цикл, від завантаження моделі до генерування зрозумілих принтеру інструкцій, однак, незважаючи на відкритість вихідного коду, будь-яка суттєва модифікація вимагає високих навичок у програмуванні та глибокого розуміння ядра системи, в наслідок чого при розробці нових алгоритмів розв’язання задач АВ часто простішим є створення власних скриптів, а не адаптація архітектури існуючих програмних рішень.
Перевагою класу промислових платформ є широкий набір інструментів виправлення дефектів та покращення якості, гнучкі алгоритми пакування, а також нативна інтеграція з модулями термомеханічного аналізу. Але, з точки зору архітектури програмного забезпечення, такі системи є яскравим прикладом пакетно-алгоритмічного підходу, за якого функціональні модулі будуються з використанням різних, часто несумісних між собою бібліотек. Промислові платформи зазвичай дозволяють користувачеві забезпечити певний рівень автоматизації рутинних задач (наприклад, шляхом написання скриптів мовою Python), ці можливості обмежуються автоматизацією стандартних дій в інтерфейсі.
Пропрієтарні рішення від виробників принтерів орієнтуються на автоматизацію базового процесу використання обладнання. В такому програмному забезпеченні більшість параметрів друку прихована від користувача заради стабільності результату та простоти експлуатації. Це дозволяє досягти високої повторюваності виробництва без глибоких знань технологічного процесу, проте повністю позбавляє систему універсальності та забороняє її використання з принтерами від інших виробників, а будь-яке розширення функціоналу з боку користувача є неможливим.
З наведеного огляду існуючих рішень видно, що жодне з них не є таким, яке б забезпечувало процес планування АВ від початку до кінця для будь-якої технології 3D-друку, зберігаючи при цьому властивості розширюваності та масштабованості. Тому актуальною на сьогодні проблемою є розробка архітектури мультиалгоритмічної платформи, яка б дозволяла ефективно розв’язувати послідовність задач планування АВ та була б відкритою до розширення.
Враховуючи велику кількість геометричних задач, що постають в процесі планування АВ, фундаментом розв’язання яких є алгоритми та задачі обчислювальної геометрії та комп’ютерної графіки, найбільш доцільним та перспективним шляхом побудови мультиалгоритмічного середовища з зазначеними властивостями є застосування моделі єдиного алгоритмічного середовища (МЄАС), оскільки використання МЄАС вже дозволило отримати значний приріст ефективності під час розв’язання взаємопов’язаних задач обчислювальної геометрії: побудова діаграми Вороного та тріангуляції Делоне, пошук найближчого сусіда тощо.
Однак, безпосереднє застосування МЄАС на основі теорії звідності в якості архітектурного ядра системи підтримки процесу планування АВ не дає бажаного ефекту, оскільки зазначений комплекс задач, алгоритми їх розв’язання та структури даних, на яких вони базуються не є взаємопов’язаними на формальному рівні. Тому в цій дисертаційній роботі вперше пропонується розширити концепцію МЄАС шляхом введення інструментів керування обчисленнями на рівні архітектури середовища: менеджера структур даних (МСД) та неявним зведенням репрезентацій даних.
МСД є основним елементом запропонованої архітектури МЄАС, що відповідає за зберігання та синхронізацію спільних структур даних для різних алгоритмів. В процесі виконання алгоритми розв’язання задач процесу планування АВ не будують необхідні структури даних, а отримують їх від МСД. Якщо необхідна структура даних вже була побудована та знаходиться в актуальному стані, алгоритм може її використати одразу, якщо ні – то, МСД спершу будує або актуалізує необхідну структуру даних, зберігає її, і лише після цього повертає її алгоритму.
Робота МСД базується на введеній класифікації алгоритмів за характером змін, що вносяться в геометрію, над якою вони працюють. Немодифікаційні алгоритми не змінюють геометрію чи структури даних (наприклад, пошук найближчого сусіда), атрибутивні алгоритми додають, модифікують або видаляють властивості геометричних об’єктів або їх складових частин (наприклад, призначення кольору вершини трикутника), топологічно-тріангуляційні алгоритми виконують топологічні зміни (наприклад, перебудова тріангуляції), геометричні алгоритми вносять зміни в геометричне місце точок, що описує об’єкт, над яким вони оперують (наприклад, побудова більш органічного мешу за рахунок заокруглення кутів), просторово-трансформаційні алгоритми впливають лише на матрицю трансформації об’єкта (наприклад, поворот або перенесення об’єкта в просторі) та комплексні (або радикальні) алгоритми, що здійснюють суттєві перетворення структури моделі. Кожен алгоритм в МЄАС в явному вигляді декларує, до яких класів змін він належить, завдяки чому МСД може слідкувати за актуальністю наявних структур даних.
Також, в межах запропонованої архітектури, ядро МЄАС відповідає за автоматичне визначення оптимального шляху отримання необхідної репрезентації даних. При цьому МЄАС виконує необхідні проміжні обчислення або трансформації даних «за кадром», тому розробнику алгоритму непотрібно власноруч слідкувати за способом отримання потрібних даних.
В роботі проведено огляд основних актуальних підходів до розв’язання зазначеного вище комплексу задач процесу планування АВ. При цьому, однією з ключових вимог до архітектури МЄАС є масштабованість системи, зокрема, шляхом додавання нових задач та алгоритмів, тому функціональні можливості запропонованої моделі єдиного алгоритмічного середовища не обмежується наведеним вище переліком задач. Також, з метою забезпечення додаткової гнучкості системи, окремо розглянуто загальні алгоритми генерування мешів на основі функції відстані зі знаком та алгоритми виконання булевих операцій над мешами, які дозволяють реалізовувати прикладні задачі процесу планування АВ, які є актуальними лише для деяких технологій друку або спеціалізованих робочих процесів (наприклад, додавання відступу до моделі).
Окремо акцентується увага на структурах даних, що використовуються розглянутими алгоритмами в процесі роботи, а також проаналізовано, за який рахунок інтеграція цих алгоритмів в єдиній системі на базі запропонованої архітектури МЄАС дозволяє прискорити загальний час їх виконання.
Також в дисертації досліджено підхід до побудови ефективних алгоритмів розв’язання деяких задач обчислювальної геометрії з використанням графу Ріба (ГР) для плоского многокутника. Зокрема, в роботі запропоновано новий алгоритм побудови декомпозиції довільного плоского многокутника на набір монотонних многокутників з одночасною їх тріангуляцією. Встановлено, що за умови наявності ГР в МСД, обчислювальна складність розробленого алгоритму складає O(n), де n – кількість вершин многокутника, що є ефективнішим за існуючі алгоритми тріангуляції. Показано, що використання застосування ГР дозволяє оптимізувати задачі процесу планування АВ при роботі на рівні слайсів моделі.
Розроблено алгоритм перевірки подібності многокутників, який працює за лінійний час та використовує константний обсяг додаткової пам’яті, на основі якого запропоновано новий підхід до врахування подібності сусідніх слайсів моделі в алгоритмах, що виконують процедуру декомпозиції многокутника. Також, в роботі запропоновано алгоритм відновлення декомпозиції многокутника на основі існуючої декомпозиції для подібного многокутника. В сукупності, ці два алгоритми дозволяють уникати повторну побудову декомпозиції або тріангуляції для однакових або дуже схожих контурів моделі, що забезпечує економію часу при обробці великої кількості послідовних слайсів.
Ефективність запропонованих алгоритмів як складових компонентів МЄАС підтверджено практичними експериментами. Швидкість роботи процедури декомпозиції довільного многокутника на монотонні з одночасною їх тріангуляцією було порівняно з найбільш вживаними бібліотеками мови програмування C++, які містять алгоритми побудови тріангуляції: CGAL, PolyPartition та Geometric Tools. Тестування, проведене на многокутниках з кількістю вершин від 〖10〗^2 до 〖10〗^7, показало, що запропонований алгоритм в поєднанні з МЄАС в середньому є в 2-3 рази швидшим за PolyPartition, в залежності від розміру вхідного многокутника, та щонайменше в 5 разів швидшим за інші розглянуті бібліотеки. Експериментальні дослідження оптимізації процедури декомпозиції многокутника шляхом врахування подібності сусідніх слайсів були проведені для задачі декомпозиції довільного многокутника на опуклі, що часто використовується в алгоритмах планування траєкторії друку в адитивному виробництві. Показано, що застосування такої оптимізації дозволяє скоротити час виконання декомпозиції, причому, зі збільшенням кількості слайсів ефект від використання оптимізації стає більш помітним. Наприклад, час обробки 2000 слайсів моделі Stanford Bunny зменшився 32.2%, а час обробки 4000 слайсів аналогічної моделі зменшився на 47.8%, тобто операція була виконана майже вдвічі швидше.
Дисертація на здобуття наукового ступеня доктора філософії за спеціальністю 122 - Комп’ютерні науки. – Київський національний університет імені Тараса Шевченка, Київ, 2026.
Дисертаційна робота присвячена розробці концепції моделі єдиного алгоритмічного середовища (МЄАС) для розв’язування комплексу алгоритмічних задач, що постають в процесу планування адитивного виробництва (АВ), тобто під час підготовки однієї або кількох цифрових тривимірних моделей до 3D-друку. Увага акцентується на наступному наборі задач, які постають при використанні більшості існуючих технологій АВ: генеруванні мешів, виборі оптимальної орієнтації для моделей та їх розміщення всередині робочої області принтера, генерування опорних конструкцій, слайсинг та побудова траєкторії друку.
Сфера застосування адитивного виробництва в сучасному світі поступово розширюється з інструменту швидкого прототипування до повноцінної компоненти складних виробничих ланцюжків. Перевагою АВ є здатність долати обмеження традиційних методів виробництва, таких як лиття або фрезування, шляхом створення деталі з внутрішніми каналами ти сітчастими структурами, в результаті чого надруковані деталі міцнішими при меншій вазі. В таких індустріях промисловості як автомобілебудування та аерокосмічна галузь, застосування деталей виготовлених шляхом адитивного виробництва дозволяє збільшити вантажопідйомність та знизити витрати пального. Сучасні геополітичні виклики та логістичні кризи підкреслюють ще одну перевагу АВ – можливість використання моделі «виробництво на вимогу», за якої створення необхідної деталі відбувається за лічені години локально в місці її використання, що є критично важливим у військовій справі, енергетиці та медицині.
На сьогодні існує велика кількість різноманітних технологій АВ, що орієнтовані на друк різними матеріалами – пластиком, керамікою, металами тощо. В основу цих технологій покладені різні фізичні явища, однак об’єднує їх процес планування АВ, що неодмінно передує безпосередньому друку моделі. Різні технології АВ накладають різні вимоги та обмеження щодо вхідних даних, тому розв’язання задачі планування АВ не може бути зведене до єдиного універсального алгоритму.
Програмні рішення, що існують на сьогодні, можна розділити на три категорії: відкриті системи масового сегмента (наприклад Cura та PrusaSlicer), промислові платформи (наприклад Autodesk Netfabb та Siemens NX) та пропрієтарні рішення від виробників обладнання (наприклад Formlabs PreForm та EOS Build).
Представники першої категорії є відкритими програмними продуктами та мають відносно низький поріг входу, що зробило їх стандартом для настільних 3D-принтерів аматорського сегмента. В межах своєї спеціалізації ці системи пропонують повноцінний робочий цикл, від завантаження моделі до генерування зрозумілих принтеру інструкцій, однак, незважаючи на відкритість вихідного коду, будь-яка суттєва модифікація вимагає високих навичок у програмуванні та глибокого розуміння ядра системи, в наслідок чого при розробці нових алгоритмів розв’язання задач АВ часто простішим є створення власних скриптів, а не адаптація архітектури існуючих програмних рішень.
Перевагою класу промислових платформ є широкий набір інструментів виправлення дефектів та покращення якості, гнучкі алгоритми пакування, а також нативна інтеграція з модулями термомеханічного аналізу. Але, з точки зору архітектури програмного забезпечення, такі системи є яскравим прикладом пакетно-алгоритмічного підходу, за якого функціональні модулі будуються з використанням різних, часто несумісних між собою бібліотек. Промислові платформи зазвичай дозволяють користувачеві забезпечити певний рівень автоматизації рутинних задач (наприклад, шляхом написання скриптів мовою Python), ці можливості обмежуються автоматизацією стандартних дій в інтерфейсі.
Пропрієтарні рішення від виробників принтерів орієнтуються на автоматизацію базового процесу використання обладнання. В такому програмному забезпеченні більшість параметрів друку прихована від користувача заради стабільності результату та простоти експлуатації. Це дозволяє досягти високої повторюваності виробництва без глибоких знань технологічного процесу, проте повністю позбавляє систему універсальності та забороняє її використання з принтерами від інших виробників, а будь-яке розширення функціоналу з боку користувача є неможливим.
З наведеного огляду існуючих рішень видно, що жодне з них не є таким, яке б забезпечувало процес планування АВ від початку до кінця для будь-якої технології 3D-друку, зберігаючи при цьому властивості розширюваності та масштабованості. Тому актуальною на сьогодні проблемою є розробка архітектури мультиалгоритмічної платформи, яка б дозволяла ефективно розв’язувати послідовність задач планування АВ та була б відкритою до розширення.
Враховуючи велику кількість геометричних задач, що постають в процесі планування АВ, фундаментом розв’язання яких є алгоритми та задачі обчислювальної геометрії та комп’ютерної графіки, найбільш доцільним та перспективним шляхом побудови мультиалгоритмічного середовища з зазначеними властивостями є застосування моделі єдиного алгоритмічного середовища (МЄАС), оскільки використання МЄАС вже дозволило отримати значний приріст ефективності під час розв’язання взаємопов’язаних задач обчислювальної геометрії: побудова діаграми Вороного та тріангуляції Делоне, пошук найближчого сусіда тощо.
Однак, безпосереднє застосування МЄАС на основі теорії звідності в якості архітектурного ядра системи підтримки процесу планування АВ не дає бажаного ефекту, оскільки зазначений комплекс задач, алгоритми їх розв’язання та структури даних, на яких вони базуються не є взаємопов’язаними на формальному рівні. Тому в цій дисертаційній роботі вперше пропонується розширити концепцію МЄАС шляхом введення інструментів керування обчисленнями на рівні архітектури середовища: менеджера структур даних (МСД) та неявним зведенням репрезентацій даних.
МСД є основним елементом запропонованої архітектури МЄАС, що відповідає за зберігання та синхронізацію спільних структур даних для різних алгоритмів. В процесі виконання алгоритми розв’язання задач процесу планування АВ не будують необхідні структури даних, а отримують їх від МСД. Якщо необхідна структура даних вже була побудована та знаходиться в актуальному стані, алгоритм може її використати одразу, якщо ні – то, МСД спершу будує або актуалізує необхідну структуру даних, зберігає її, і лише після цього повертає її алгоритму.
Робота МСД базується на введеній класифікації алгоритмів за характером змін, що вносяться в геометрію, над якою вони працюють. Немодифікаційні алгоритми не змінюють геометрію чи структури даних (наприклад, пошук найближчого сусіда), атрибутивні алгоритми додають, модифікують або видаляють властивості геометричних об’єктів або їх складових частин (наприклад, призначення кольору вершини трикутника), топологічно-тріангуляційні алгоритми виконують топологічні зміни (наприклад, перебудова тріангуляції), геометричні алгоритми вносять зміни в геометричне місце точок, що описує об’єкт, над яким вони оперують (наприклад, побудова більш органічного мешу за рахунок заокруглення кутів), просторово-трансформаційні алгоритми впливають лише на матрицю трансформації об’єкта (наприклад, поворот або перенесення об’єкта в просторі) та комплексні (або радикальні) алгоритми, що здійснюють суттєві перетворення структури моделі. Кожен алгоритм в МЄАС в явному вигляді декларує, до яких класів змін він належить, завдяки чому МСД може слідкувати за актуальністю наявних структур даних.
Також, в межах запропонованої архітектури, ядро МЄАС відповідає за автоматичне визначення оптимального шляху отримання необхідної репрезентації даних. При цьому МЄАС виконує необхідні проміжні обчислення або трансформації даних «за кадром», тому розробнику алгоритму непотрібно власноруч слідкувати за способом отримання потрібних даних.
В роботі проведено огляд основних актуальних підходів до розв’язання зазначеного вище комплексу задач процесу планування АВ. При цьому, однією з ключових вимог до архітектури МЄАС є масштабованість системи, зокрема, шляхом додавання нових задач та алгоритмів, тому функціональні можливості запропонованої моделі єдиного алгоритмічного середовища не обмежується наведеним вище переліком задач. Також, з метою забезпечення додаткової гнучкості системи, окремо розглянуто загальні алгоритми генерування мешів на основі функції відстані зі знаком та алгоритми виконання булевих операцій над мешами, які дозволяють реалізовувати прикладні задачі процесу планування АВ, які є актуальними лише для деяких технологій друку або спеціалізованих робочих процесів (наприклад, додавання відступу до моделі).
Окремо акцентується увага на структурах даних, що використовуються розглянутими алгоритмами в процесі роботи, а також проаналізовано, за який рахунок інтеграція цих алгоритмів в єдиній системі на базі запропонованої архітектури МЄАС дозволяє прискорити загальний час їх виконання.
Також в дисертації досліджено підхід до побудови ефективних алгоритмів розв’язання деяких задач обчислювальної геометрії з використанням графу Ріба (ГР) для плоского многокутника. Зокрема, в роботі запропоновано новий алгоритм побудови декомпозиції довільного плоского многокутника на набір монотонних многокутників з одночасною їх тріангуляцією. Встановлено, що за умови наявності ГР в МСД, обчислювальна складність розробленого алгоритму складає O(n), де n – кількість вершин многокутника, що є ефективнішим за існуючі алгоритми тріангуляції. Показано, що використання застосування ГР дозволяє оптимізувати задачі процесу планування АВ при роботі на рівні слайсів моделі.
Розроблено алгоритм перевірки подібності многокутників, який працює за лінійний час та використовує константний обсяг додаткової пам’яті, на основі якого запропоновано новий підхід до врахування подібності сусідніх слайсів моделі в алгоритмах, що виконують процедуру декомпозиції многокутника. Також, в роботі запропоновано алгоритм відновлення декомпозиції многокутника на основі існуючої декомпозиції для подібного многокутника. В сукупності, ці два алгоритми дозволяють уникати повторну побудову декомпозиції або тріангуляції для однакових або дуже схожих контурів моделі, що забезпечує економію часу при обробці великої кількості послідовних слайсів.
Ефективність запропонованих алгоритмів як складових компонентів МЄАС підтверджено практичними експериментами. Швидкість роботи процедури декомпозиції довільного многокутника на монотонні з одночасною їх тріангуляцією було порівняно з найбільш вживаними бібліотеками мови програмування C++, які містять алгоритми побудови тріангуляції: CGAL, PolyPartition та Geometric Tools. Тестування, проведене на многокутниках з кількістю вершин від 〖10〗^2 до 〖10〗^7, показало, що запропонований алгоритм в поєднанні з МЄАС в середньому є в 2-3 рази швидшим за PolyPartition, в залежності від розміру вхідного многокутника, та щонайменше в 5 разів швидшим за інші розглянуті бібліотеки. Експериментальні дослідження оптимізації процедури декомпозиції многокутника шляхом врахування подібності сусідніх слайсів були проведені для задачі декомпозиції довільного многокутника на опуклі, що часто використовується в алгоритмах планування траєкторії друку в адитивному виробництві. Показано, що застосування такої оптимізації дозволяє скоротити час виконання декомпозиції, причому, зі збільшенням кількості слайсів ефект від використання оптимізації стає більш помітним. Наприклад, час обробки 2000 слайсів моделі Stanford Bunny зменшився 32.2%, а час обробки 4000 слайсів аналогічної моделі зменшився на 47.8%, тобто операція була виконана майже вдвічі швидше.
Ключові слова :
3D-моделювання адитивне виробництво код композиція математична модель математична оптимізація множина даних модель єдиного алгоритмічного середовища обчислювальна геометрія оптимізація параметрична оптимізація представлення поверхні просторові задачі регуляризація швидкість обробки. 3D-modelling additive manufacturing code composition computational geometry data set mathematical model mathematical optimization model of a unified algorithmic environment optimization parametric optimization processing speed regularization spatial problems surface representation.
Галузі знань та спеціальності :
F3 Комп’ютерні науки
Файл(и) :![Ескіз]()
Вантажиться...
Формат :
Adobe PDF
Розмір :
2.6 MB
Контрольна сума :
(MD5):6bab5da53b39cfa573d784306912b6b3
Якщо не вказано інше, ця робота розповсюджується на умовах ліцензії Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International