摘要
本論文提出兩種對靜態模型迅速且有效的點簡化演算法；並且也針對動態模型提出一種使用主成分分析來壓縮資料量的資料簡化演算法。 針對靜態模型的簡化，本論文提出以八元樹為基礎之點的簡化及以離散外形運算子(DSO)為基礎之點的簡化方法。以八元樹為基礎之點的簡化演算法利用區域性的共平面分析來萃取代表點集合。區域性的共平面分析使用八元樹資料結構為基礎，利用八元樹節點中取樣點的散佈情形來判斷是否符合共平面的特性。此方法除了可以成功萃取出特徵區域，且可以依物體外觀變化情形與使用者的定義調整代表點集合的密度。代表點集合，又稱為基礎模型(base model)，將使用重建演算法重建出網狀模型。本論文除了可以成功重建外，對於簡化後模型也可保有不錯的誤差值，且相對於利用原始取樣點集合重建再進行簡化三角片的傳統方式，其所需花費之時間成本與計算代價均有良好的改善。本論文最終輸出為一階層式三角網格並保有多層次解析與自動多層次顯像的效果，並且可以產生點集合平均散佈或呈現出往特徵區域集中的兩種階層式成像法。 本論文並且提出以外形運算子為基礎之有效且低誤差的點簡化演算法用來保留物體的特徵。離散外形運算子(DSO)將用來針對點集合萃取特徵，並且所萃取出來的特徵點集合將會被延遲簡化。此簡化方法改善以二次誤差矩陣為基礎的網格點對簡化演算法，除了可以有效的在簡化物體時保留物體外型特徵，並且可以有效降低萃取特徵時的前處理時間。本論文並且提出一個得到單一簡化模型的方法。此單一簡化模型可以有效減少先對原始點集合進行重建的時間約百分之七十點六。換言之，此方法使用離散外形運算子可以獲得更多的幾何資訊，特別是在有高度變化的表面區域以及特徵點集合。並且離散外形運算子的特徵萃取不但有助於重建簡化後的點集合，而且在點簡化時可以適度地保留模型特徵，並且可以減少點簡化時所造成的誤差 針對動態模型的簡化，本論文使用仿射矩陣與主成份分析來壓縮3D動畫。使用主成份分析對一般的3D動畫模型均可以獲得不錯的簡化結果，因為主成份分析能將多個有相關性的變數簡化成少數幾個沒有相關的主成份，而且經由線性組合可還原出近似原始動畫。要選擇多少個主成分因子一直是一個值得研究的問題。選擇較多的主成分因子將可以獲得較精細的動畫模型並且降低誤差。因此，如何獲得主成分因子的公式是必需要的。本論文提出一個自動化選取主成分基底的方法，包含選擇最適當基底外並且分別應用主成分分析於x, y, z三軸上。 主成分分析適合用於原地運動的動態模型。若將原始動畫加入剛體運動，諸如:平移、旋轉、縮放，則對使用相同基底的主成份分析將會造成龐大的失真情形。本論文首先使用仿射矩陣來萃取模型運動特徵，並且將位移變化利用4e4矩陣來記錄。轉換過後的模型可去除幾何轉換的影響，並將動畫模型正規化至侷限空間內；之後使用主成份分析將可以更正確的計算出最適當的基底(變異數)。
並列摘要
This investigation presents two novel rapid and effective point simplification algorithms for static model simplification utilizing point cloud without normals. And this thesis also presents a simplification algorithm for dynamic model, also called animation model, using principal component analysis. For static model simplification, octree based point cloud simplification and DSO feature based point cloud simplification are proposed. The octree based point cloud simplification adopted local coplanar analysis to obtain the relevant points from a point set sampled from 3D objects. The local coplanar analysis, on the basis of an oc-tree data structure with an inner point distribution of a cube, can determine whether these points are coplanar. The proposed approach successfully extracts the feature area from point set. According to the object’s surface variation and user definition, the scheme also modulates the density of these relevant points. The relevant points, called the base model, were reconstructed to triangular mesh. In addition to the successful reconstruction, the error rate of the base model within a specific tolerance level. Compared with the traditional methods in which surface reconstruction is completed prior to mesh simplification, this approach applies point cloud simplification prior to surface reconstruction to improved time expense and calculation cost. By using the octree data structure, this thesis proposes some hierarchical rendering for the recon-structed model to suit user demand and produce a uniform or feature-sensitive simpli-fied model that facilitates rapid further mesh based applications. Finally, output of the proposed method is a hierarchical triangular mesh that inherently supports generation of multi-resolution representations for the applications of level of detail. This thesis also proposes a Discrete Shape operator (DSO) feature based method for effective low-error point cloud simplification method to retain the physi-cal features of models. The DSO value is adopted to extract the features of the point cloud models, and the feature vertices are postponed to simplify. The proposed method improves the quadric error metric of the vertex pair contraction; it not only effectively simplifies the model while retaining the features of the object model but also decreases the pre-processing time cost for feature analysis. This algorithm pro-poses a method to obtain unique simplified model for each model. The unique sim-plified model obtained can significantly reduce the computation cost about 70.6% than mesh simplification which reconstruct original points first. In other words, the proposed method using DSO can adaptively collect more geometric information, par-ticularly on the high variation surfaces and the feature points. The DSO extraction can help to successfully reconstruct the simplified point cloud, preserve the features of simplified models, and reduce the errors caused by point cloud simplification. For dynamic model (animation model) simplification, this thesis investigates the use of the affine transformation matrix when employing Principal Component Analy-sis (PCA) to simplify the data of 3D animation models. Satisfactory results were achieved for the common 3D models by using PCA because it can simplify several related variables to a few independent main factors, in addition to making the anima-tion identical to the original by using linear combinations. The selection of the prin-cipal component factor (also known as the base) is still a subject for further research. Selecting a large number of bases could improve the precision of the animation and reduce distortion for a large data volume. Hence, a formula is required for base selec-tion. This thesis develops an automatic PCA selection method, which includes the se-lection of suitable bases and a PCA separately on the three axes to select the number of suitable bases for each axis. PCA is more suitable for animation models for apparent stationary movement. If the original animation model is integrated with transformation movements such as translation, rotation, and scaling, the resulting animation model will have a greater distortion in the case of the same base vector with regard to apparent stationary movement. This thesis is the first to extract the model movement characteristics using the affine transformation matrix and then to compress 3D animation using PCA. The affine transformation matrix can record the changes in the geometric transformation by using 4 × 4 matrices. The transformed model can eliminate the influences of geo-metric transformations with the animation model normalized to a limited space. Sub-sequently, by using PCA, the most suitable base vector (variance) can be selected more precisely.