Конструктивна блокова геометрія

Складний об'єкт може бути представлений двійковим деревом, де «листя» — це об'єкти, а вузли — операції. ($\cap$ перетин, $\cup$ об'єднання, $-$ різниця)

Конструктивна блокова геометрія (Шаблон:Lang-en, скорочено CSG) — це технологія, яка використовується для моделювання твердих тіл. Конструктивна блокова геометрія дозволяє створити більш складну поверхню чи об'єкт як комбінацію простих об'єктів за допомогою бітових операцій. Це дозволяє спростити математичний опис складних об'єктів, хоча для цього не завжди використовуються лише примітивні об'єкти.

Конструктивна блокова геометрія часто, але не завжди, є способом моделювання в тривимірній графіці та САПР. КБУ також часто використовують у процедурному моделюванні. Так за допомогою конструктивної блокової геометрії представляють моделі або поверхні, які лише виглядають складними, а насправді вони являють собою більш хитро скомбіновані або декомбіновані прості об'єкти. В деяких випадках конструктивна блокова геометрія використовує полігональні сітки (Шаблон:Lang-en), і може бути процедурною та/або параметричною.

Опис

Найпростіші тіла, які використовуються в конструктивній блокової геометрії називаються примітивами (Шаблон:Lang-en). Як правило, це об'єкти, які мають просту форму: куб, циліндр, призма, піраміда, сфера, конус. Набір доступних примітивів залежить від програмного забезпечення. Так, деякі програми дозволяють створення нових об'єктів конструктивно блокової геометрії на основі вигнутих об'єктів, а інші ні.

Побудова складнішого об'єкта відбувається шляхом застосування до об'єктів булевих (бітових) операцій на множинах — об'єднання, перетин і різниця, а також геометричні перетворення цих множин.

Зазвичай примітив можна описати алгоритмом, який приймає декілька параметрів, наприклад: сфера може бути описана координатами центра разом зі значенням радіуса. Примітиви можуть бути об'єднані в складені об'єкти за допомогою таких операцій:

• 
  Об'єднання
  Злиття двох об'єктів в один
• 
  Різниця
  Віднімання одного об'єкта від іншого
• 
  Перетин
  Спільна частина обох об'єктів

Поєднуючи ці елементарні операції, можна будувати складні об'єкти на основі простих.

Використання

Конструктивна блокова геометрія (КБУ) має ряд практичних застосувань. Вона застосовується там, де необхідне використання простих геометричних об'єктів, або математична точність. Майже у всіх інженерних пакетах САПР використовується КБУ (де це може бути корисно для представлення інструментів відсікань та функцій, де деталі повинні підганятися одна до одної).

Ігрові рушії, наприклад Quake engine, Unreal engine, Hammer (нативний редактор рівнів рушія Source), Шаблон:Нп / Шаблон:Нп використовують цю систему. Конструктивна блокова геометрія широко використовується, оскільки розробник може використовувати множину відносно простих об'єктів, щоб створити дуже складне геометричне зображення. При використанні процедурної, або параметричної конструктивної блокової геометрії, користувач може переглянути свою складну геометричну фігуру, змінюючи положення об'єктів, або змінюючи логічні операції для комбінацій цих об'єктів.

Однією з переваг конструктивної блокової геометрії є те, що вона може гарантувати, що створені об'єкти є «твердими», або «водонепроникними», якщо всі примітивні форми є «водонепроникними». Це може бути важливо для деяких виробничих або інженерних обчислювальних застосувань. Для порівняння, при створенні геометричних фігур на основі представлення границь, потрібен додатковий топологічний ряд даних або потрібно робити перевірку на узгодженість задля гарантії, що цей опис границі фігури вказує на чинний твердий об'єкт.

Зручною властивістю об'єктів конструктивної блокової геометрії є те, що довільні точки легко класифікувати як всередині, так і поза формою, створеною КБУ. Точка просто класифікується за всіма базовими примітивами та обчислюється отриманий булевий вираз. Це бажана опція для деяких програм, таких як трасування променів.

Перетворення з полігональних сіток в КБГ

Оскільки моделі конструктивної блокової геометрії параметризовані за конструкцією, вони часто вигідніші за полігональні сітки, коли справа стосується додатків, метою яких є виготовлення незалежних моделей. Для таких програм може бути корисним перетворити вже наявні сітки в дерева КБГ. Проблема автоматичного перетворення полігональних сіток у дерева конструктивної блокової геометрії називається оберненою КБГ.

Отримане дерево КБГ повинно займати той самий обсяг у тривимірному просторі, що і вхідна полігональна сітка, маючи мінімальну кількість вузлів. Перевагу віддають простим рішенням, щоб гарантувати, що отриману модель можна легко редагувати. Розв'язання цієї проблеми є складним завданням через великий простір пошуку, який потрібно дослідити. Він поєднує в собі безперервні параметри, такі як розмірність, розмір примітивних фігур і дискретні параметри, такі як булеві оператори, що використовуються для побудови остаточного дерева КБГ.

Дедуктивні методи розв'язують цю проблему шляхом побудови набору напівпросторів, що описують внутрішню будову геометричної фігури. Ці напівпростори використовуються для опису примітивів, які можна об'єднати, щоб отримати фінальну складну модель.

Інший підхід поєднує в собі виявлення примітивних фігур та обчислення дерева КБГ, що визначає фінальну модель. Цей підхід використовує здатність сучасних засобів Шаблон:Нп знаходити дерево КБГ з мінімальною складністю.

Існують також підходи, які використовують генетичні алгоритми для ітеративної оптимізації початкової форми у напрямку до форми бажаної полігональної сітки.

Програми із підтримкою КБГ

Загальні мови моделювання та програмне забезпечення

• Шаблон:Не перекладено
• Шаблон:Не перекладено

Трасування променів та перенесення частинок

• PhotoRealistic RenderMan
• POV-Ray

Комп'ютерне проектування

• AutoCAD
• Autodesk Inventor
• Autodesk Fusion 360
• BRL-CAD
• CATIA
• FreeCAD
• NX CAD
• SolveSpaceAutoCAD
• Autodesk Inventor
• Autodesk Fusion 360
• BRL-CAD
• NIX CAD
• SolveSpace
• Шаблон:Нп
• Шаблон:Нп
• Шаблон:Нп (раніше відомий як Pro/Engineer)
• Realsoft 3D
• Rhino
• SelfCAD
• Шаблон:Нп
• SolidWorks
• Tinkercad
• Шаблон:Нп

Створення ігор

• Шаблон:Нп
• Godot
• GtkRadiant
• Unity
• UnrealEd
• Valve Hammer Editor
• Roblox

Інші

• Шаблон:Не перекладено
• Шаблон:Нп (версії 0.6.0)
• Blender
• Шаблон:Не перекладено
• Geant4
• Шаблон:Нп
• SketchUp

Література

• Martti Mantyla, «An Introduction to Solid modeling», 1988
• Christoph M. Hoffman, «Geometric and Solid modeling», 1989
• Philip M. Hubbard, «Constructive Solid Geometry for Triangulated Polyhedra», 1990
• Michael Muuss & Lee Butler, Глава «Combinatorial Solid Geometry, B-Reps, and n-Manifold Geometry» з книги «State of the Art in Computer Graphics», 1991

Додаткові посилання

• Leadwerks Software 'What is Constructive Solid Geometry?' — пояснення термінів, рівнянь та застосувань.
• GNU Triangulated Surface library Шаблон:Webarchive — бібліотека з відкритим кодом (LGPL), яка містить можливості CSG на сітках з трикутників.
• Computational Geometry Algorithms Library Шаблон:Webarchive — бібліотека з відкритим кодом (LGPL), яка містить, крім іншого, можливості CSG.
• The CSG rendering library Шаблон:Webarchive — бібліотека з відкритим кодом, яка виробляє орієнтований на зображення CSG-рендеринг з використанням OpenGL.
• HyperFun Project Шаблон:Webarchive — проста функціональна мова для геометричного моделювання, здатний виконувати CSG-операції на різних типах об'єктів.
• Overview of CSG in avoCADo — програма 3D CAD з відкритим сирцевим кодом.
• SimpleGeo — інтерактивне твердотіле моделювання для симуляції переміщення часток за методом Монте-Карло.
• FMEpedia CSGBuilder example Шаблон:Webarchive — wikipedia CSG binary tree as replicated using FME (Feature Manipulation Engine).
• SolidKit Library — програмна бібліотека для програм з 3D/2D-графікою, розроблена на C++ з використанням OpenGL, містить можливості CSG на сітках з трикутників.