近似包覆橢圓球之應用與研究

林捷翔(Jie-Siang Lin)

指導教授 ： 莊漢東

國立中央大學/工學院/機械工程學系/碩士(2006年)

摘要

摘 要
物件近似為一種普遍使用於電腦繪圖、計算幾何學計算物件間相交(Object Intersection)與機器人自動避碰(Collision Avoidance)軌跡規劃分析的方法。藉由適當之物件近似可將複雜之物體以簡單體積來近似，如此便可利用簡單的方法初步分析兩物體相交或發生碰撞之可能性。若兩近似體不存在任何交集，則代表實際物體也不可能發生相交或碰撞之情形。反之，若兩近似體存在著交集，則兩物體有可能存在相交或碰撞之情形，此時才需要再進一步執行複雜之計算。
所以為能更快速且方便的提供碰撞偵測比對，本計畫將結合保守近似之包覆矩形具有長寬高之彈性變化與積極近似包覆圓球的概念，探討不等軸之包覆橢圓球(Bounding Elliposid)近似方法，相較於目前用於偵測橢圓球的方法，本研究加上了密度評估的策略，能讓嵌合計算出的橢圓球更接近物體外形，進而在碰撞偵測上能更準確。

關鍵字

Bounding Box ； Bounding Ellipsoid ； Convex hull ； 最小平方橢圓球嵌合(Least Squares Ellipsoid Specific Fitting)

並列摘要

Abstract
Bounding volume are widely employed in many areas of computer graphics.Usually,we use crude approximations of the scene geometry to speed up some time-consuming computations, such as object intersection or collision avoidance, etc.Test was performed to check if overlapping of the bounding boxes occurs.If it occurs,we need further computations.
In order to fast and effectively computes the object intersection or collision avoidance,this investigaton combined bounding box with bounding spherea as the method of bounding ellipsoid.In this investigation,we combine least squares ellipsoid specific fitting with weights estimation such that the collision detection will be more accurate.

並列關鍵字

none

參考文獻

[1] Thomas Brinkhoff, Hans-Peter Kriegel, Ralf Schneider, “Comparison of Approximation of Complex Objects Used for Approximation-based Query Processing in Spatial Database System”, Proceedings of the Ninth International Conference on Data Engineering, pp.40-49, 1993.

[2] S. Ding, M.A. Mannan, A.N. Poo, “Oriented bounding box and octree based gloabal interference detection in 5-axis machining of free-form surfaces”, Proceedings of the ACM SIGGRAPH Conference on Computer-Aided Design, Vol.36, pp.1281-1294, 2004.

[3] C.K. Chan, S.T. Tan, “Determination of the minimum bounding box of an arbitrary solid : an iterative approach”, Computers and Structures, Vol.79, pp.1433-1449, 2001.

[5] Qingde Li, John G. Griffiths, “Least Squares Ellipsoid Specific Fitting”, Geometric Modeling and Processing 2004,pp.335-340.

[6] A. Fitzgibbon, M. Pilu, R. B. Fisher, “Direct least square fitting of ellipses”, IEEE Transaction on Pattern Analysis and Machine intelligence, 21(5),pp.476–480, May 1999.