Original title:
CSG modelování pro polygonální objekty
Translated title:
CSG modeling for polygonal objects
Authors:
Václavík, Jiří ; Křivánek, Jaroslav (advisor) ; Beneš, Jan (referee) Document type: Master’s theses
Year:
2012
Language:
cze Abstract:
[cze][eng] Tato práce se zabývá efektivní a robustní technikou provádění booleovských operací nad polygonálními modely. Plné robustnosti je dosaženo ve vnitřní reprezentaci založené na rovinách a BSP stromech (binary space partitioning trees), v které lze operace provádět přesně v pouhé aritmetice s pevnou přesností. Potřebné konverze z obvyklé reprezentace do vnitřní a zpět včetně jejich důsledků jsou podrobně analyzovány. Výkon metody je optimalizován lokalizačním schématem v podobě adaptivního oktantového stromu. Vzniklá implementace RazeCSG je experimentálně srovnána s implementacemi používanými v praxi Carve a Maya, které nejsou plně robustní. U velkých modelů vykazuje RazeCSG v nejhorším případě jen dvakrát nižší výkon než Carve a je nejméně 130krát rychlejší než Maya.This work deals with an efficient and robust technique of performing Boolean operations on polygonal models. Full robustness is achieved within an internal representation based on planes and BSP (binary space partitioning) trees, in which operations can be carried out exactly in mere fixed precision arithmetic. Necessary conversions from the usual representation to the inner one and back, including their consequences are analyzed in detail. The performance of the method is optimized by a localization scheme in the form of an adaptive octree. The resulting implementation RazeCSG is experimentally compared with implementations used in practice Carve and Maya, which are not fully robust. For large models, RazeCSG shows only twice lower performance in the worst case than Carve, and is at least 130 times faster than Maya.
Keywords:
3D; computer graphics; constructive solid geometry; CSG; efficient and robust Boolean operations; 3D; CSG; efektivní a robustní booleovské operace; konstruktivní geometrie těles; počítačová grafika
Institution: Charles University Faculties (theses)
(web)
Document availability information: Available in the Charles University Digital Repository. Original record: http://hdl.handle.net/20.500.11956/49559