L-systems in geometric modeling

DOI10.1142/S0129054112400096MaRDI QIDQ2909188zbMATH OpenOpenAlexFDO

Authors Przemyslaw Prusinkiewicz, Mitra Shirmohammadi, Faramarz Samavati

Publication date 30 August 2012

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1008.1664

zbMATH Keywords

affine geometryB-splineBézier curveL-systemsubdivision

Mathematics Subject Classification ID

Numerical computation using splines (65D07) Computer-aided design (modeling of curves and surfaces) (65D17) Grammars and rewriting systems (68Q42) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: We show that parametric context-sensitive L-systems with affine geometry interpretation provide a succinct description of some of the most fundamental algorithms of geometric modeling of curves. Examples include the Lane-Riesenfeld algorithm for generating B-splines, the de Casteljau algorithm for generating Bezier curves, and their extensions to rational curves. Our results generalize the previously reported geometric-modeling applications of L-systems, which were limited to subdivision curves.

Review text

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.

Recommendations

• L-systems in geometric modeling
• L-SYSTEM DESCRIPTION OF SUBDIVISION CURVES
• scientific article; zbMATH DE number 176935
• Practical curves and surfaces for a geometric modeler
• MESH-BASED PARAMETRIZED L-SYSTEMS AND GENERALIZED SUBDIVISION FOR GENERATING COMPLEX GEOMETRY

Cites work

• Doubly deterministic tabled OL systems
• scientific article; zbMATH DE number 3480114 (Why is no real title available?)
• scientific article; zbMATH DE number 1547387 (Why is no real title available?)
• scientific article; zbMATH DE number 3802813 (Why is no real title available?)
• L-SYSTEM DESCRIPTION OF SUBDIVISION CURVES
• On subdivision schemes generalizing uniform B-spline surfaces of arbitrary degree
• TOL schemes and control sets
• TOL systems and languages

Cited in

(10)

• Algorithms for inferring context-sensitive L-systems
• A multi-criteria based selection method using non-dominated sorting for genetic algorithm based design
• A dynamic root simulation model in response to soil moisture heterogeneity
• Animating plant growth in L-system by parametric functional symbols
• Developing fractal curves
• scientific article; zbMATH DE number 176935 (Why is no real title available?)
• L-system specification of knot-insertion rules for non-uniform B-spline subdivision
• scientific article; zbMATH DE number 2099653 (Why is no real title available?)
• L-systems in geometric modeling
• L-SYSTEM DESCRIPTION OF SUBDIVISION CURVES

This page was built for publication: L-systems in geometric modeling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2909188)