L-systems in geometric modeling (Q2909188)

An L-system is a string rewriting system which primarily is used to plant modeling and generation. Its definition is based on the notions and notations from the formal language theory. The geometric interpretation of the obtained string is mostly based on turtle geometry or chain coding. The authors of the paper introduce the use of L-systems in geometric modeling. They represent some of the basics curves using L-systems and affine geometry as the geometric interpretation.NEWLINENEWLINEIn the preliminary section the authors introduce extended context-sensitive L-systems and some notations which are used in all considered algorithms. Next, in Section 3, they introduce an L-system for the well known Chaikin algorithm. The axiom of this system consists of the curve control points and the set of rules has only one context-sensitive rule. Later, they give an L-system which uses not only the control points but also the edges connecting them. In this case, the number of rules rises to three and the axiom consists of control points and edges of the control polygon. The last L-system introduced for Chaikin's curve is a variant of the second system. In this case, the set of rules can be divided into two types of rules. In the first set we have one rule which inserts new vertices and in the second we have rules which replace the predecessor polygon by a new one.NEWLINENEWLINEIn Section 4 L-systems for the generation of Bézier curves are introduced. For the derivation of the L-systems two algorithm are used: the de Casteljau algorithm and subdivision. Using the simple rule from the de Casteljau algorithm (dividing successive line segments in proportion \(t : 1-t\)), the L-system for generating a point for a given value \(t\) is given. The system consists of two simple rules. The first replaces each point with an affine combination of this point and its neighbor to the right, and the second one erases the last point in the sequence. Then, similar to the case of Chaikin's curve, the L-system with information about the edges is given. The system consists of three rules: production which replaces an edge with a vertex, production which replaces a vertex between two edges with an edge and production which erases the first and the last vertex. Next, a subdivision scheme is used to create another L-system for generating Bézier curves of any degree. This time the system is extended by a state of a point and two types of edges. The system after extension consists of five rules which are used \(n\) times and two more which are used later. At the end of this section the authors give an L-system for a quadratic and a pseudo L-system for a cubic Bézier curve which are derived from the subdivision scheme.NEWLINENEWLINEAn extension of the presented L-systems to rational curves is presented in Section 5. The extension is made by introducing a rule responsible for projection and a small change in the interpretation of the rule for edges.