桂林動畫數(shù)字課件制作之分割面
只要在每次分割的時候選取的分割面與其余的三角面的相交盡可能的少，就能保證整個算法的高 效性和穩(wěn)定性。
現(xiàn)在有兩種方法可以減小生成的BSP樹規(guī)模： (1)針對每次分割，預(yù)先計(jì)算所有分割面分割后的規(guī)模，選擇分割最少的平面作為分割面。 (2)使用隨機(jī)方法，在三角面片序列中，隨機(jī)選擇一個作為分割面。 對于第一種方法，需要進(jìn)行許多預(yù)計(jì)算，因?yàn)閷τ诿恳粋€可能的分割面，都要計(jì)算分割后的面片 總數(shù)，使得整個算法的效率大大下降。另外由于每次選取只考慮樹的當(dāng)前層，所以整個算法只能保證 局部最優(yōu)而不是整體最優(yōu)。
但是，使用隨機(jī)方法，雖然不能保證每次分割都是最優(yōu)的，卻可以保證構(gòu) 造出來的BSP樹的期望規(guī)模非常小。 這里引入免費(fèi)分割的概念：進(jìn)行分割面選取時，若該平面可以直接跨越某個子區(qū)域，則該子區(qū)域 中的其他面將不會被分割，所以在以后的計(jì)算中不用計(jì)算這些面。圖3.6 免費(fèi)分割 圖3.6中，三角面片P直接將三角面片／、分割成兩部分，若三角面片／所在的平面中的其他三角 面片也按照e進(jìn)行分割，則以后計(jì)算中可以不用冉考慮這些三角面片。 因?yàn)樗惴╝lgorithmBSPConstruct中初始分割面總是選取三角面片集合的第一個面，所以使得算法 的效率直接取決于三角面片集合的輸入順序。
為了避免引入預(yù)計(jì)算而使BSP樹建立速度過慢，可以考慮 生成三角面片序列的隨機(jī)排列，然后再進(jìn)行分割。與隨機(jī)算法相結(jié)合，可以使生成的BSP樹的期望規(guī)模 較小。算法的描述如下：BSP樹TalgonthmBSPRandom（場景圖中的三角面片集合S）I生成三角面片集合 的隨機(jī)排列S，for(i=l to n){if(S:包含1個三角面或碎片，{直接生成樹T，S：存儲在T中return T} else(將S：所在平面Pi作為分割面){ 第3章 角色*35T+＝algorithmBSPRandom(位于H+空間的三角面片集合)T= algorithmBSPaRandom(位于 環(huán)空間的三角面片集合)H=S'return lif(S：構(gòu)成免費(fèi)分割)進(jìn)行所有的免費(fèi)分割從結(jié)果來看，若三維 場景中包含n個三角面片，對任意一個三角面片Sj，它被分割的碎塊數(shù)目的期望是O(i)，因此算法 algorithrmBSPRandom生成的碎片期望數(shù)目為O(3.4 習(xí)題(1)什么是骨骼動畫？(2)實(shí)時角色動畫可以 分為哪三類？(3)骨(4)骨(5)請骼動畫有哪些數(shù)據(jù)信息？骼動畫是如何驅(qū)動的？表示出M形對應(yīng)的BSP樹 。參考文獻(xiàn) ∑ ，=0 i)＝O(Tl2)Damian M, Tim D. Skeletal animation for the exploration of graphs [C]. In Proceedings of the 2004Australasian symposium on Information Visualisation, Vol. 35, 61- 70, 2004.Thalman N M, Daniel T. Computer Animation: Theory and Practice [M]. 2nd ed. New York:SpringerVerlag New York, Inc. , 1990. 鮑虎軍,金小WiJ ,彭群生， i+算機(jī)4tj畫的算法礎(chǔ)[M].杭州：浙江大學(xué)出版社,2000.Shoemake K. Animating rotation with quaternion curves [J]. Computer Graphics, 19 (3): 245-254, 1985.Naylor B. Constructing Good Partitioning Trees [C]. Graphics Interface (annual Canadian CGconference) May, 1993.Gottschalk S, I_in M C, Manocha D. OBBTree: a hierarchical structure for rapid interference detection[Cl. Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, 171-180, 1996.Meagher D. ()ctree Encoding: A New Technique for the Representation, Manipulation and DisplHy ofArbitrary 3-D Objects by Computer[R]. Rensselaer Polytechnic Institute (Technical Report IPI.-TR-80-111) , 1980.i-l i-i ri r f ] r-i_ 2 3 4 Ln 6 r-[-l [ I-I t-l L_l L_l L_l
轉(zhuǎn)載請注明：
桂林flash動畫制作公司：http://www.haldonestatewines.com/city107/
