實體模型之平行布林運算

Parallel Boolean Operations in Solid Modeling

孫俊斌(Chun-Pin Sun)

指導教授 ： 尤春風

國立臺灣大學/工學院/機械工程學研究所/碩士(2008年)

https://doi.org/10.6342/NTU.2008.01921

摘要

在實體模型的建構過程中，通常都是從最基本的幾何資料(點、線、面)開始繪製，然後再利用大量外型簡單的實體進行一連串布林運算，藉此以獲得最終複雜的模型。然而，隨著模型在資料數量的累積和複雜度的增加，布林運算時間亦會相對隨之變長。對於目前布林運算的循序演算法則(sequential algorithms)，因為要考量模型建構後的編輯和修改問題，若要不斷優化演算法來減少運算量以提升之效能實屬有限。
　　採取平行處理(parallel operation)中分工合作的概念，讓重複運算的地方能同步進行，則可縮短因實體複雜化後的運算時間，進而達到大幅提升效能之目標。本研究提出平行布林運算法則，以Java語言所撰寫的Spring Solid System作為核心，透過Parallel Java所提供的平行程式套件，將系統中原有的布林運算模組之循序演算法則平行化，並於多核心處理器(multicore)的電腦平台上實作具有平行布林運算能力之CAD系統。

關鍵字

實體模型 ； 布林運算 ； 平行處理 ； Spring Solid ； Parallel Java

並列摘要

During the construction process of solid modeling, complex models are usually built up from basic geometric entities (points, curves, surfaces) and then use several primitive solids to execute a series of Boolean operations. However, the more plenty and complex of the cumulation of data, the more amount of time is required in Boolean operation. In consideration of editing and modifying after the model construction, it is difficult to improve the calculation efficiency by optimizing the existing sequential algorithms.
The concept of parallel operation seems to be a probable technique for improving the computation speed in operation of complex solids. This paper presents a method for performing parallel Boolean operations on multicore computer systems. The system was implemented using Java language. The main kernel used to construct model and perform Boolean operation is based on the library of Spring Solid System, and the middleware used to code parallel program is supplied by Parallel Java.

並列關鍵字

Solid modeling ； Boolean operation ； parallel operation ； Spring Solid ； Parallel Java

參考文獻

[22]葉子豪，特徵編輯在協同環境之研究與應用，國立台灣大學機械工程學研究所碩士論文，2004。

[2]Crocker, G.A. and Reinke, W.F., “An editable non-manifold boundary representation”, IEEE Computer Graphics and Applications, Vol.11, No.2, pp.39-51, 1991.

[3]Gardan, Y. and Perrin, E., “An algorithm reducing 3D Boolean operations to a 2D problem: concepts and results”, Computer-Aided Design, Vol.28, No.4, pp.277-287, 1996.

[4]Hui, K.C. and Kan, Y.M., “Data partitioning for parallel solid modeling”, The Visual Computer, Vol.11, No.10, 1995.

[5]Hui, K.C. and Kan, Y.M., “Distributed boundary representation and Boolean operations on a massively parallel computer”, Computer-Aided Design, Vol.28, No.8, pp.631-649, 1996.