A parallel algorithm for binary-tree-based string rewriting in L-systems

Abstract

The L-system is a commonly used methodology to generate fractals and realistic model plants, yet it is very complex and computationally expensive. This paper presents a new parallel L-system string re-writing algorithm based on two types of binary tree: the growth-state tree (GST) and the growth-manner tree (GMT). This data structure makes one of the basic operations in the L-system - left and right context searching - extremely easy during the process of growth-state evolvement. Another benefit from this data structure is that we can make use of pseudo nodes to store information about neighboring sub-strings after each string partition. This helps working processes, in both the stage of growth and rendering, communicate well with each other so as to accomplish the final image compositions. Results of experimental tests have demonstrated that our parallel strategy works effectively on clusters with a multi-processors architecture.