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

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

Конструктивна блокова геометрія (англ. Constructive Solid Geometry, скорочено CSG) — це технологія, яка використовується для моделювання твердих тіл. Конструктивна блокова геометрія дозволяє створити більш складну поверхню чи об'єкт як комбінацію простих об'єктів за допомогою бітових операцій.[1] Це дозволяє спростити математичний опис складних об'єктів, хоча для цього не завжди використовуються лише примітивні об'єкти.[2][3]

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

Опис

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Інші

Примітки

  1. ↑ а б в г Foley, James D.; Van, Foley Dan; Dam, Andries Van; Feiner, Steven K.; Hughes, John F.; Angel, Edward; Hughes, J. (1996). Computer Graphics: Principles and Practice (англ.). Addison-Wesley Professional. ISBN 978-0-201-84840-3. Архів оригіналу за 15 квітня 2021. Процитовано 24 травня 2021.
  2. ↑ Ray casting for modeling solids. Computer Graphics and Image Processing (англ.). Т. 18, № 2. 1 лютого 1982. с. 109—144. doi:10.1016/0146-664X(82)90169-1. ISSN 0146-664X. Архів оригіналу за 24 травня 2021. Процитовано 24 травня 2021.
  3. ↑ а б Bloomenthal, Jules; Bajaj, Chandrajit; Blinn, Jim; Wyvill, Brian; Cani, Marie-Paule; Rockwood, Alyn; Wyvill, Geoff (15 серпня 1997). Introduction to Implicit Surfaces (англ.). Morgan Kaufmann. ISBN 978-1-55860-233-5. Архів оригіналу за 23 квітня 2017. Процитовано 24 травня 2021.
  4. ↑ Constructive solid geometry. Wikipedia (англ.). 10 травня 2021. Процитовано 24 травня 2021.
  5. ↑ Ansari, Marwan (19 квітня 2016). Game Development Tools (англ.). CRC Press. ISBN 978-1-4398-6772-3. Архів оригіналу за 1 січня 2017. Процитовано 24 травня 2021.
  6. ↑ а б Glassner, Andrew S. (11 лютого 1989). An Introduction to Ray Tracing (англ.). Morgan Kaufmann. ISBN 978-0-12-286160-4. Архів оригіналу за 1 січня 2017. Процитовано 23 травня 2021.
  7. ↑ Three-dimensional halfspace constructive solid geometry tree construction from implicit boundary representations. Computer-Aided Design (англ.). Т. 36, № 11. 15 вересня 2004. с. 1063—1073. doi:10.1016/j.cad.2004.01.006. ISSN 0010-4485. Архів оригіналу за 24 травня 2021. Процитовано 24 травня 2021.
  8. ↑ Du, Tao; Inala, Jeevana Priya; Pu, Yewen; Spielberg, Andrew; Schulz, Adriana; Rus, Daniela; Solar-Lezama, Armando; Matusik, Wojciech (4 грудня 2018). InverseCSG: automatic conversion of 3D models to CSG trees. ACM Transactions on Graphics. Т. 37, № 6. с. 213:1–213:16. doi:10.1145/3272127.3275006. ISSN 0730-0301. Процитовано 24 травня 2021.
  9. ↑ ayolle, Pierre-Alain; Pasko, Alexander A. (2016) (PDF). Архів оригіналу (PDF) за 14 квітня 2021. Процитовано 24 травня 2021.
  10. ↑ Engine, Godot. Godot Engine - Godot gets CSG support. Godot Engine (англ.). Архів оригіналу за 24 травня 2021. Процитовано 24 травня 2021.
  11. ↑ Aqsis Renderer / News: Major release. sourceforge.net. Архів оригіналу за 24 травня 2021. Процитовано 24 травня 2021.

Література

  • 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

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

Read other articles:

Raimondo Lullo

Beato Raimondo Lullo Laico  NascitaPalma di Maiorca, 1232 MortePalma di Maiorca, 29 giugno 1316 Venerato daChiesa cattolica Beatificazione1850 da papa Pio IX Ricorrenza29 giugno Manuale Raimondo Lullo (in catalano Ramon Llull; in latino Raimundus Lullus; Palma di Maiorca, 1232 – Palma di Maiorca, 29 giugno 1316) è stato un filosofo, scrittore, teologo, logico, astrologo, alchimista, mistico e missionario spagnolo, tra i più celebri dell'Europa del tempo. Indice 1 Biografia 2 Ope...

 

Slavko Kvaternik

Croatian soldier and politician (1878–1947) Slavko KvaternikKvaternik in 19421st Minister of Armed Forces of the Independent State of CroatiaIn office10 April 1941 – 4 January 1943Prime MinisterAnte PavelićPreceded byOffice establishedSucceeded byAnte PavelićChief of General Staff of theState of Slovenes, Croats and SerbsIn office29 October 1918 – 1 December 1918PresidentAnton KorošecPreceded byOffice establishedSucceeded byOffice abolished Personal detailsBorn(...

 

Rankoshi, Hokkaido

Rankoshi 蘭越町KotaprajaBalai Kota Rankoshi BenderaEmblemLokasi Rankoshi di Hokkaido (Subprefektur Shiribeshi)RankoshiLokasi di JepangKoordinat: 42°49′N 140°32′E / 42.817°N 140.533°E / 42.817; 140.533Koordinat: 42°49′N 140°32′E / 42.817°N 140.533°E / 42.817; 140.533NegaraJepangWilayahHokkaidoPrefektur Hokkaido (Subprefektur Shiribeshi)DistrikIsoyaPemerintahan • WalikotaHideyuki KonLuas • Total449,7...

Conciergerie

Medieval building in Paris, France See also: Palais de la Cité The ConciergieThe ConciergerieGeneral informationTypepalace, courthouse, prisonArchitectural styleGothic and Gothic revivalLocationÎle de la CitéTown or cityParisCountryFranceCoordinates48°51′23″N 2°20′44″E / 48.8564°N 2.3456°E / 48.8564; 2.3456 The Conciergerie (French pronunciation: [kɔ̃sjɛʁʒəʁi]) (English: Lodge) is a former courthouse and prison in Paris, France, located on...

 

Texas Almanac

The Texas Almanac Cover of the 2006-2007 Texas Almanac (sesquicentennial)AuthorMultipleCover artistJohn Collier (2006-2007 ed.)CountryUnited StatesLanguageEnglishSubjectTexasGenreReferencePublisherTexas State Historical AssociationPublication date1857Media typeBook (electronic edition available)Pages~700ISBN978-0-914511-38-0 (2006-2007 ed.)OCLC80720995 The Texas Almanac is a biennially published reference work providing information for the general public on the history of the US sta...

 

Raja Hindustani

Raja HindustaniPoster filmSutradaraDharmesh DarshanProduserAlive MoraniKarim MoraniBunty SoormaDitulis olehDharmesh DarshanJaved Siddiqui (dialog)SkenarioRobin BhattCeritaDharmesh DarshanPemeranAamir KhanKarisma KapoorSuresh OberoiJohnny LeverNavneet NishanVeeru KrishnanKunal KhemuPramod MouthoMohnish BehlTiku TalsaniaFarida JalalArchana Puran SinghPenata musikLagu:Nadeem-ShravanMusik Latar:Surinder SodhiSinematograferW.B. RaoPenyuntingBharatPerusahaanproduksiCineyugDistributorTips Film...

WDR 2

You can help expand this article with text translated from the corresponding article in German. (August 2023) Click [show] for important translation instructions. Machine translation, like DeepL or Google Translate, is a useful starting point for translations, but translators must revise errors as necessary and confirm that the translation is accurate, rather than simply copy-pasting machine-translated text into the English Wikipedia. Consider adding a topic to this template: there are a...

 

Creatures the World Forgot

1971 British filmCreatures the World ForgotTheatrical release posterDirected byDon ChaffeyWritten byMichael CarrerasProduced byMichael CarrerasStarringJulie EgeBrian O'ShaughnessyCinematographyVincent CoxEdited byChris BarnesMusic byMario NascimbeneProductioncompanyHammer Film ProductionsDistributed byColumbia PicturesRelease dates 18 April 1971 (1971-04-18) (UK) September 1, 1971 (1971-09-01) (USA) Running time95 mins.CountryUnited KingdomLanguageEnglis...

 

Edy Supriyanta

artikel ini perlu dirapikan agar memenuhi standar Wikipedia. Tidak ada alasan yang diberikan. Silakan kembangkan artikel ini semampu Anda. Merapikan artikel dapat dilakukan dengan wikifikasi atau membagi artikel ke paragraf-paragraf. Jika sudah dirapikan, silakan hapus templat ini. (Pelajari cara dan kapan saatnya untuk menghapus pesan templat ini) Edy Supriyanta (lahir 4 Mei 1965) adalah seorang birokrat Indonesia. Edy juga menghabiskan masa mudanya hingga lulus SMA. Setelah lulus dari SMAN ...

Cassivellaunus

King of the Catuvellauni CassivellaunusKing of the CatuvellauniA representation of Cassivellaunus, New York Public LibraryPredecessorUnknownSuccessorTasciovanusBornEnglandDiedEnglandBurialUnknown (In legend: York)OccupationChief commander of the British resistance during Caesar's second invasion of Britain Cassivellaunus was a historical British military leader who led the defence against Julius Caesar's second expedition to Britain in 54 BC. He led an alliance of tribes against Roman forces...

 

Robert Roosevelt

American politician (1829–1906) Robert RooseveltTreasurer of the Democratic National CommitteeIn officeJuly 21, 1892 – June 26, 1896Preceded byCharles J. CandaSucceeded byWilliam P. St. JohnMember of the U.S. House of Representativesfrom New York's 4th districtIn officeMarch 4, 1871 – March 3, 1873Preceded byJohn FoxSucceeded byArchibald M. BlissUnited States Ambassador to the NetherlandsIn officeAugust 10, 1888 – May 17, 1889President Grover Cle...

 

Primula

Disambiguazione – Se stai cercando l'album di Piero Fabrizi, vedi Primula (album). Come leggere il tassoboxPrimula Primula vulgaris Classificazione APG IV Dominio Eukaryota Regno Plantae (clade) Angiosperme (clade) Mesangiosperme (clade) Eudicotiledoni (clade) Eudicotiledoni centrali (clade) Superasteridi Ordine Ericales Famiglia Primulaceae Genere Primula Specie L. Classificazione Cronquist Dominio Eukaryota Regno Plantae Divisione Magnoliophyta Classe Magnoliopsida Ordine Primulales Fami...

بروتوكول التحكم بالنقل متعدد المسارات (Multipath TCP)

هذه المقالة بحاجة لصندوق معلومات. فضلًا ساعد في تحسين هذه المقالة بإضافة صندوق معلومات مخصص إليها. هذه المقالة تحتاج للمزيد من الوصلات للمقالات الأخرى للمساعدة في ترابط مقالات الموسوعة. فضلًا ساعد في تحسين هذه المقالة بإضافة وصلات إلى المقالات المتعلقة بها الموجودة في ال...

 

Yuriy Bilonoh

Ukrainian shot putter This biography of a living person needs additional citations for verification. Please help by adding reliable sources. Contentious material about living persons that is unsourced or poorly sourced must be removed immediately from the article and its talk page, especially if potentially libelous.Find sources: Yuriy Bilonoh – news · newspapers · books · scholar · JSTOR (January 2013) (Learn how and when to remove this message) Yuriy...

 

约翰斯顿环礁

此條目可参照英語維基百科相應條目来扩充。 (2021年5月6日)若您熟悉来源语言和主题，请协助参考外语维基百科扩充条目。请勿直接提交机械翻译，也不要翻译不可靠、低品质内容。依版权协议，译文需在编辑摘要注明来源，或于讨论页顶部标记{{Translated page}}标签。 约翰斯顿环礁Kalama Atoll 美國本土外小島嶼 Johnston Atoll 旗幟颂歌：《星條旗》The Star-Spangled Banner約翰斯頓環礁...

Flavor of Love

Television series Flavor of LoveCreated byCris AbregoMark CroninStarringFlavor FlavCountry of originUnited StatesNo. of seasons3No. of episodes39ProductionExecutive producersCris AbregoMark Cronin[1]Ben SamekRunning time60 minutesProduction company51 Minds EntertainmentOriginal releaseNetworkVH1ReleaseJanuary 1, 2006 (2006-01-01) –May 26, 2008 (2008-05-26) Flavor of Love is an American reality television dating game show starring Flavor Flav of the rap group Public En...

 

فورتنايت باتل رويال

فورتنايت باتل رويال (بالإنجليزية: Fortnite Battle Royale)‏  المطور إيبك غيمز الناشر إيبك غيمز الموزع بلاي ستيشن ستور[1]،  وآب ستور[2]،  وإكس بوكس ستور[3]،  ونينتندو إي شوب،  وجوجل بلاي،  وأمازون لونا  الرخصة رخصة احتكارية  سلسلة اللعبة فورتنايت محرك الل...

 

قائمة معاهدات الدولة العثمانية

يسرد الجدول التالي معاهدات الدولة العثمانية.[1][2] السنة اسم المعاهدة الموقعون الرئيسيون (غير الدولة العثمانية) 1403 معاهدة جاليبولي الإمبراطورية البيزنطية وجمهورية البندقية 1411 معاهدة سليمبريا جمهورية البندقية 1419 معاهدة السلام العثمانية البندقية (1419) جمهورية البند...

أوتو فون بسمارك

سعادة السمو الجليل أوتو فون بيسمارك أمير آل بيسمارك Otto von Bismarck بيسمارك في عام 1890 مستشار ألمانيا في المنصب21 مارس 1871 - 20 مارس 1890 العاهل فيلهلم الأول فريديك الثالث فيلهلم الثاني تم إنشاء المنصب ليو فون كابريفي معلومات شخصية اسم الولادة أوتو إدوارد ليوبولد فون بيسمارك-شونهاوسن...

 

63rd Tony Awards

2009 awards ceremony 63rd Tony Awards63rd Tony Awards posterDateJune 7, 2009LocationRadio City Music HallHosted byNeil Patrick HarrisMost awardsBilly Elliot the Musical (10)Most nominationsBilly Elliot the Musical (15)Websitetonyawards.comTelevision/radio coverageNetworkCBSViewership7.4 million[1]Produced byRicky KirshnerGlenn WeissDirected byGlenn Weiss ← 62nd · Tony Awards · 64th → The 63rd Annual Tony Awards, which recognized Broadway productions o...