CUHK electronic theses & dissertations collection

實體造型在各種設計和生產項目中起著關鍵的作用。他們作為虛擬雕刻，微結構設計和快速成型等等這些常常需要處理複雜形狀和拓撲模型的應用的基礎。隨著愈來愈複雜性的工業模型和需要執行重複性的操作，我們必須要有一個有效率的處理系統。然而，因為許多基本的幾何運算是計算密集型的，一般商用的幾何內核（例如Parasolid和ACIS），尤其是對自由曲面和高度詳細複雜的模型，計算成本的要求是非常高，甚至有時不能使用。本研究的目的是開發一個以自由曲面模型為對象能夠完全在GPU 上運行的實體建模，這將大大提高建模的效率。引致操作中高計算強度的一個關鍵原因是因為他們使用了邊界表示法（B-REP）。我們引入了一個新的表述 - 名為多層深度法向圖像（LDNI）來直接在GPU 上描述對象。LDNI 能夠滿足一定的幾何和拓撲的要求，同時保持簡單和易於並行實現，提供了一個比邊界表示法更可行的形式。在基於B-REP 的建模核心內執行基本操作（如布爾運算，閔可夫斯基和等）往往是耗時和容易出現偶爾失敗。我們已經開發出一些GPU 加速算法，包括布爾和一般閔可夫斯基和，它們的執行速度遠遠超過傳統的方法並且沒有顯著的穩定性問題出現。這些算法是基於圖像表示法來進行的，可以讓特定的任務在每個像素上獨立運行。我們還開發了在GPU 上由B-REP 轉換成LDNI 和由LDNI 轉換成B-REP 的算法。我們為了高效率而使用光栅化來獲得圖像並利用GPGPU 庫來將圖像轉換成B-REP。有了這些算法，我們的建模框架可以與其他常見的CAD 內核進行交換操作。這框架還支持模型的局部細化網格，這有助減少內存消耗，並同時保持曲面G¹ 連續性。最後，本研究的目的是提供一個全面處理複雜形狀的建模問題的框架。我們展示幾個使用了以GPU 為基礎的實體建模應用例子，相比現有的以B-REP 為基礎的系統，我們的框架在效率上得到極大的改善。Solid modeling plays a key role in a variety of design and manufacturing activities. They serve as the foundation for applications like virtual sculpting, microstructure design and rapid prototyping, which usually deal with complex shape and topology model. The fast growing complexity of industrial models and the need to perform some operations repeatedly thereby necessitate an efficient processing system. However, since many fundamental geometric operations are compute-intensive, most commercial geometric kernels (e.g. Parasolid and ACIS), especially for freeform and highly-detailed complex models, require very high computational cost and do not work on such complex models. The purpose of this research is to exploit a solid modeler for freeform objects completely running on GPUs, which will greatly improve the efficiency of shape modeling.A critical reason for such high computing intensity in operations is because they are performed on Boundary Representation (B-Rep). A new representation named Layered Depth Normal Images (LDNI) is introduced in this thesis to describe an object directly on GPU. LDNI is an extension of ray-representation which inherits the good properties of Boolean simplicity, localization, domain decoupling and the ease of parallel implementation, therefore provides a more feasible form than usual boundary representations.Performing fundamental operations (such as Boolean operations, Minkowski sum, etc) are often time-consuming and prone to numerical problems when being applied on B-Rep model. This work develops several GPU-accelerated algorithms, including Boolean and general Minkowski sum. Our algorithms are carried out on image-based representation and thus are able to perform much faster than conventional approaches without arise any significant instability or robustness issues.Algorithms have also been developed for converting B-Rep to LDNI and vice versa on GPU. Our sampling method makes use of rasterization to get the images for high efficiency and GPGPU libraries to convert them back to B-Rep. With these algorithms, the representations of models can be converted between this framework and other common CAD kernels. The framework also supports local refinement of coarse mesh, which is useful for reducing memory consumption while maintaining G¹ continuity.Finally, the objective of this research is to provide a comprehensive framework for complex shape modeling problem. Several applications are demonstrated in using the GPU-based solid modeler, which shows great improvement in the efficiency compared with existing B-rep based systems.Detailed summary in vernacular field only.Detailed summary in vernacular field only.Detailed summary in vernacular field only.Detailed summary in vernacular field only.Detailed summary in vernacular field only.Leung, Yuen Shan.Thesis (Ph.D.)--Chinese University of Hong Kong, 2012.Includes bibliographical references (leaves 148-159).Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web.Abstract also in Chinese.Abstract --- p.iChinese Abstract --- p.iiiAcknowledgements --- p.ivList of Figures --- p.ixList of Tables --- p.xiList of Publications --- p.xiiChapter 1 --- Introduction --- p.1Chapter 1.1 --- Motivation --- p.1Chapter 1.2 --- Contribution --- p.3Chapter 1.3 --- Organization --- p.4Chapter 2 --- Literature Review --- p.6Chapter 2.1 --- Exact Solid Modeling --- p.6Chapter 2.1.1 --- Solid Modeling Based on B-rep --- p.6Chapter 2.1.1.1 --- Data Structure --- p.7Chapter 2.1.1.2 --- Boolean Operation --- p.10Chapter 2.1.1.3 --- Problems --- p.11Chapter 2.1.2 --- Solid Modeling based on CSG --- p.11Chapter 2.1.2.1 --- Operations --- p.12Chapter 2.1.2.2 --- Comparison --- p.13Chapter 2.1.3 --- Boundary Space Partition Trees --- p.14Chapter 2.2 --- Approximate Solid Modeling --- p.16Chapter 2.2.1 --- Voxel representation --- p.16Chapter 2.2.2 --- Oct-tree representation --- p.18Chapter 2.2.3 --- Distance-Field --- p.20Chapter 2.2.4 --- Unorganized Point-Cloud --- p.22Chapter 2.3 --- Computational Intensive Operations --- p.23Chapter 2.3.1 --- Minkowski Sum --- p.23Chapter 2.3.2 --- Offset --- p.26Chapter 2.3.3 --- Sweeping --- p.29Chapter 2.4 --- Volumetric Representation to B-Rep Conversion --- p.32Chapter 2.5 --- Curved B-rep Generation on GPU --- p.33Chapter 3 --- Data Structure of Solid Modeling on GPU --- p.36Chapter 3.1 --- Layered Depth Normal Images --- p.36Chapter 3.2 --- Data Structure on GPU --- p.39Chapter 3.2.1 --- Encode Normal Vector --- p.41Chapter 3.2.2 --- Compactly Stored Data Structure --- p.42Chapter 4 --- Model Sampling in Image Space --- p.46Chapter 4.1 --- Introduction --- p.46Chapter 4.2 --- Prior Sampling Approaches --- p.48Chapter 4.2.1 --- Stencil Buffer --- p.50Chapter 4.2.2 --- Freepipe --- p.52Chapter 4.3 --- GPU-Accelerated Conservative Sampling --- p.53Chapter 4.3.1 --- Algorithm Overview --- p.54Chapter 4.3.2 --- Voxel Classification --- p.57Chapter 4.3.3 --- Fast Bit Checking --- p.60Chapter 4.3.4 --- MAX Blending for Depth Value Retrieval --- p.61Chapter 4.3.5 --- Implementation Detail --- p.62Chapter 4.4 --- Results and Discussion --- p.64Chapter 4.5 --- Applications --- p.67Chapter 5 --- Boolean Operations in Images Space --- p.69Chapter 5.1 --- Introduction --- p.69Chapter 5.2 --- GPU-Accelerated Boolean Operations --- p.70Chapter 5.2.1 --- Boolean Operations on shader --- p.70Chapter 5.2.2 --- Boolean Operations on CUDA --- p.71Chapter 5.3 --- Results and Discussion --- p.75Chapter 6 --- Minkowski Sum in Image Space --- p.77Chapter 6.1 --- Introduction --- p.77Chapter 6.2 --- Algorithm Based on Exterior Boundary Extraction --- p.78Chapter 6.3 --- GPU-Accelerated Minkowski Sum --- p.79Chapter 6.3.1 --- Minkowski Sums in Image Space Without Voids --- p.79Chapter 6.3.1.1 --- Algorithm Overview --- p.79Chapter 6.3.1.2 --- Implementation Issue --- p.80Chapter 6.3.1.3 --- Results and Performance --- p.81Chapter 6.3.2 --- Minkowski Sums with Inner Voids --- p.82Chapter 6.3.2.1 --- Algorithm Overview --- p.83Chapter 6.3.2.2 --- Convex Decomposition --- p.83Chapter 6.3.2.3 --- Pairwise Minkowski Sum --- p.85Chapter 6.3.2.4 --- Super-union in Image Space --- p.86Chapter 6.3.2.5 --- Results and Discussion --- p.90Chapter 6.3.2.6 --- Application --- p.93Chapter 7 --- Localized Construction of Curved Surfaces --- p.96Chapter 7.1 --- Local Construction of Curved Polygon --- p.98Chapter 7.1.1 --- Basic Construction Scheme --- p.98Chapter 7.1.1.1 --- Gregory Patch Interpolation --- p.98Chapter 7.1.1.2 --- Silhouette Curve Interpolation --- p.100Chapter 7.1.1.3 --- Cross-Tangent Function --- p.101Chapter 7.1.2 --- Property Analysis --- p.103Chapter 7.1.3 --- Discussions --- p.106Chapter 7.1.4 --- Algorithm for Generating N-Sided Polygons --- p.109Chapter 7.2 --- Flexible Shape Control --- p.111Chapter 7.2.1 --- Possibility of Extending the Basic Scheme --- p.111Chapter 7.2.2 --- Reorienting Silhouette Curve (Extended Scheme 1) --- p.111Chapter 7.2.3 --- Straight Silhouette (Extended Scheme 2) --- p.112Chapter 7.2.4 --- Crease (Extended Scheme 3) --- p.113Chapter 7.2.5 --- Silhouette Adjacent to Crease (Extended Scheme 4) --- p.113Chapter 7.2.6 --- Smooth Patch Bulging (Extended Scheme 5) --- p.114Chapter 7.2.7 --- Flat Surface (Extended Scheme 6) --- p.115Chapter 7.3 --- Implementation Details on GPU --- p.115Chapter 7.3.1 --- Refinement --- p.116Chapter 7.3.2 --- Position Mapping --- p.118Chapter 7.3.3 --- Normal Computation for Shading --- p.118Chapter 7.4 --- Results and Comparison --- p.119Chapter 8 --- B-rep Reconstruction on GPU --- p.124Chapter 8.1 --- Introduction --- p.124Chapter 8.2 --- B-rep Representation by Dual-Contouring --- p.125Chapter 8.3 --- GPU-Accelerated Dual-Contouring --- p.126Chapter 8.3.1 --- Algorithm Overview --- p.126Chapter 8.3.2 --- Implementation Issue --- p.129Chapter 8.4 --- Results and Discussion --- p.130Chapter 9 --- Applications --- p.133Chapter 9.1 --- Bone Graft --- p.133Chapter 9.2 --- Personalized Medical Treatment --- p.137Chapter 10 --- Conclusion --- p.139Chapter 10.1 --- Summary --- p.139Chapter 10.2 --- Future Work --- p.141Chapter A --- Appendix A: Examples and Results --- p.143Bibliography --- p.14