基于二叉树的上下文相关L-系统实现  

Implementation of context-sensitive L-system based on binary tree

作　　者：黄争舸[1] 陈建军[1] 杨廷俊[1] 林形省[1] 郑耀[1] 

机构地区：[1]浙江大学工程与科学计算研究中心,计算机学院,浙江杭州310027

出　　处：《浙江大学学报（工学版）》2008年第3期403-406,449,共5页Journal of Zhejiang University：Engineering Science

基　　金：国家自然科学基金资助项目(90405003);国家杰出青年基金资助项目(60225009)

摘　　要：从底层数据结构的角度讨论了上下文相关L-系统实现中的几个关键问题.结合L-系统的语法,解释了以二叉树为底层数据结构的新系统设计机理,提出了生长方式树和生长状态树的概念,给出了新的数据结构形式下生长状态演化算法的实现.与采用线性数组实现的L系统相比,新系统很好地模拟了L-系统本身的树形逻辑结构,简化了L-系统中上下文搜索的过程,在生长模拟环节有更高的时空效率,且具备更好的可扩展性.以虚拟植物生长为背景,介绍了如何基于新数据结构进行虚拟植物绘制和绘制优化,并通过实例验证了新算法的有效性.Some key problems were addressed about the context-sensitive L-system in terms of the fundamental data structure. Associated with the syntax of L-system, new solutions based on binary tree were explored, including two new concepts, growth-state tree and growth-manner tree, based on which a context-sensitive L-system was re-implemented. Compared with the L-system based on the linear array, the new system captures the essence of logical structure in L-systems, and simplifies the context search process, so as to obtain better timing and spacing performance in the simulation, as well as better extendibility. Finally, the optimization of rendering process was investigated with applications in virtual plants, and some plant samples demonstrated the effectiveness of the new implementation.

关 键 词：L-系统 虚拟植物 二叉树 场景图 

分 类 号：TP181[自动化与计算机技术—控制理论与控制工程]