桂林动画数字课件制作之分割面
只要在每次分割的时候选取的分割面与其余的三角面的相交尽可能的少，就能保证整个算法的高 效性和稳定性。
现在有两种方法可以减小生成的BSP树规模： (1)针对每次分割，预先计算所有分割面分割后的规模，选择分割最少的平面作为分割面。 (2)使用随机方法，在三角面片序列中，随机选择一个作为分割面。 对于第一种方法，需要进行许多预计算，因为对于每一个可能的分割面，都要计算分割后的面片 总数，使得整个算法的效率大大下降。另外由于每次选取只考虑树的当前层，所以整个算法只能保证 局部最优而不是整体最优。
但是，使用随机方法，虽然不能保证每次分割都是最优的，却可以保证构 造出来的BSP树的期望规模非常小。 这里引入免费分割的概念：进行分割面选取时，若该平面可以直接跨越某个子区域，则该子区域 中的其他面将不会被分割，所以在以后的计算中不用计算这些面。图3.6 免费分割 图3.6中，三角面片P直接将三角面片／、分割成两部分，若三角面片／所在的平面中的其他三角 面片也按照e进行分割，则以后计算中可以不用冉考虑这些三角面片。 因为算法algorithmBSPConstruct中初始分割面总是选取三角面片集合的第一个面，所以使得算法 的效率直接取决于三角面片集合的输入顺序。
为了避免引入预计算而使BSP树建立速度过慢，可以考虑 生成三角面片序列的随机排列，然后再进行分割。与随机算法相结合，可以使生成的BSP树的期望规模 较小。算法的描述如下：BSP树TalgonthmBSPRandom（场景图中的三角面片集合S）I生成三角面片集合 的随机排列S，for(i=l to n){if(S:包含1个三角面或碎片，{直接生成树T，S：存储在T中return T} else(将S：所在平面Pi作为分割面){ 第3章 角色*35T+＝algorithmBSPRandom(位于H+空间的三角面片集合)T= algorithmBSPaRandom(位于 环空间的三角面片集合)H=S'return lif(S：构成免费分割)进行所有的免费分割从结果来看，若三维 场景中包含n个三角面片，对任意一个三角面片Sj，它被分割的碎块数目的期望是O(i)，因此算法 algorithrmBSPRandom生成的碎片期望数目为O(3.4 习题(1)什么是骨骼动画？(2)实时角色动画可以 分为哪三类？(3)骨(4)骨(5)请骼动画有哪些数据信息？骼动画是如何驱动的？表示出M形对应的BSP树 。参考文献 ∑ ，=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+算机4tj画的算法础[M].杭州：浙江大学出版社,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
转载请注明：
桂林flash动画制作公司：http://www.flash520.com/city107/
