Abstract
八元樹表示法已非常廣泛的應用在三維的實體模型塑造上。而一個立體實物則可視為由一樣版平面沿特定軌跡掃描所構成之體積。本論文係在探討如何以旋轉掃描法建構實物之相關研究，本文中提出兩種不同之建構法分別為〞區域旋轉掃描法（Region Rotational Sweep ）〞和〞外殼旋轉掃描法（Border Rotational Sweep ）〞，而用來掃描之樣版（Pattern ）區域或外殼以及所欲模塑之實體則分別以線性四元樹（L-inear Quadtree）和線性八元樹（Linear Octree ）來表示。區域旋轉掃描之建構方法係採用垂直平移掃描法（Orthogonal Translation Sweep）配合集合元素篩分（S-et Membership Classification）來建構實體。由於受垂直水平掃描法之限制，用來掃描的樣版平面則須為一〞X 向凸櫞〞之區域（X-Convex Region ）。本文將提出兩種區域旋轉掃描之建構法，即直接旋轉掃描和改良之旋轉掃描法。前者執行效率為０（BlogB ），而後者效率則為０（B ），其中B 表八元樹實體之黑節點數。本文亦對上述二法予以實作來驗証兩者在程式執行效率上之優劣。本文第二部份將介紹另一種旋轉掃描法稱之為”外殼旋轉掃描法〞，此法係採用計算機圖學理論中之數位微量分析法（Digit Differential Analyzer ）直接利用二維之樣版外殼旋轉造圖，結合所有造出之圖即構成三維實體之外殼。產生之實體外殼本身即代表一種實物或可進一步利用回填（Filling ）操作以塑造實體。此法因不受〞X向凸櫞〞之限制故在實體製作上頗具彈性，而唯一的限制是二維的樣版外殼均須以細至解析度之線性四元樹碼來表示。本文亦提兩種外殼掃描的方法，分別為直接外殼掃描法：執行效率為０（BlogB ）和改良之外殼掃描法：執行效率為０（BlonP ）。其中B 和P 分別表線性八元樹和線性四元樹之黑節點數。本文亦分別對上述二法予以實作並將二者之執行效率作一驗証。由於以旋轉掃描法所模塑之實體具有圖對稱性，故本文所討論之旋轉掃描模塑法均透過鏡像映射（Murror Operation）作業來完成。為求線性之執行效率，本文亦提出一線性之鏡像映射作業法可在線性時間內完成鏡像映射作業。重要之參考文獻：１．Meagher D., 'Geometric Modeling Using Octree Encoding ',CGIP, VOL.19,NO.2,JUN.1982, pp.129-174.２．M. D. McILROY AT&T Bell Laboratories 'Best Approximate Circles on Int-eget Grids',ACM Transactions on Graphics,VOL.2,NO.4, OCT.1983,pp.237-263.３．Chen H. and Huang T.S.,'A Survey of Construction and Manipulation ofOctrees',CVFIP,VOL.43,1988,pp.409-431.４．Yang S. N. and Jong B. S.,'Optimal Linear Octree Consturction Algorit-m by Sweep Operations', Technical Report, Institute of Computer Science,Tsing Hua University, 1988.