Lindenmayer Systems
(L-Systems)
Disciplina: Teoria de Linguagens
Professor: Newton Vieira
Adriano Machado ([email protected])
Jan/2004
Sumário
•
•
•
•
•
•
•
Introdução
Definição (L-Systems)
Exemplo
Interpretação Gráfica
Aplicação
Conclusão
Referências Bibliográficas
Introdução
• Proposto por Aristid Lindenmayer em
1968;
• É um tipo particular de gramática;
• Um fundamento para a teoria do
desenvolvimento
ou
crescimento
biológico.
Definição
• L-Systems
 Define objetos complexos por sucessivas
substituições de partes simples do objeto
usando um conjunto de regras;
 Regras
são
aplicadas
em
paralelo,
substituindo-se simultaneamente todas as
letras de uma dada palavra.
Definição (0L-system)
• Uma 0L-system é uma tripla G=(Σ,w,P),
onde Σ é o alfabeto do sistema, P é o
conjunto finito de produções ou regras em
Σ, sendo uma produção (a,x)  P escrita
como a x, onde a  Σ e x  Σ *, e w é
uma palavra não vazia, chamada de
axioma, tal que ω  +.
Definição (0L-system)
• Σ é um conjunto finito de símbolos
formais, como a,b,c, etc.
 Variáveis;
 Constantes.
• w é uma palavra que define como o
sistema começa, chamada axioma;
• P é um mapeamento de um símbolo para
uma palavra x onde x Σ *.
Exemplo
• L = ({a,b,c}, a , {ab, bab}).
Onde:
• Σ=(a,b,c)
• w=a
• P: ab
bab
Exemplo
• L = ({a,b,c}, a , {ab, bab}).








Estado 0 :
Estado 1 :
Estado 2 :
Estado 3 :
Estado 4 :
Estado 5 :
Estado 6 :
Estado 7 :
a
1
b
1
ab
2
bab
3
abbab
5
bababbab
8
abbabbababbab
13
bababbababbabbababbab 21
Interpretação Gráfica
• Palavras contém informações sobre a
geometria de uma figura;
• Interpretação gráfica das palavras
 Estado é uma Tripla (x,y,a), onde (x,y) são
coordenadas cartesianas e a, o ângulo de
direcionamento;
 F: move um passo de tamanho d;
 +: vira à esquerda de um ângulo a;
 - : vira à direita de um ângulo a.
Curva do Dragão
• L = ({a,b}, a, { a  ab , b  ab}).
Curva do Dragão
Curva do Dragão
Geração 10
Curva do Dragão
Curva de Koch
• L = ({F,+,-}, F, { F  F + F - - F + F}).
Curva de Koch
Aplicação - Modelagem de
Plantas
• Descrever formalmente a ramificação das
estruturas encontradas em plantas;
• Estrutura modular das plantas facilita o
uso;
• Símbolos ‘[‘ e ‘]’, para determinar os
desvios no gráfico tartaruga;
• Predecessor gera sucessor.
Aplicação - Produções
Aplicação - Arbusto
W = ++++F
F=FF-[-F+F+F]+[+F-F-F]
Aplicação - Palmeira
(Phoenix dactyfera)
Aplicação - Modelagem de
Penas e Aves
• Uma estrutura ramificada composta por
módulos repetitivos;
• Partes fundamentais: o eixo, as farpas e
contorno da pena;
• Renderização foto-realística.
Aplicação - Modelagem de
Penas
Aplicação - Modelagem de Aves
Aplicação - Modelagem de
Cidades
• Utiliza informações de mapas rodoviários,
populacionais, etc.;
• Utiliza padrões de construção com base
no histórico e legislação da região;
• Renderização foto-realística.
Aplicação - Modelagem de
Cidades
Aplicação - Modelagem de
Cidades
Aplicação - Modelagem de
Cidades
Conclusão
• O uso de L-system na Computação
Gráfica tem se mostrado uma poderosa
ferramenta para a modelagem;
• L-systems paramétricas contribuem de
modo a permitir que o usuário crie
facilmente tipos e formas diferentes;
• Com o aprofundamento das pesquisas,
têm sido possível modelar estruturas cada
vez mais complexas.
Referências
•
•
•
•
•
•
•
•
•
[1] Lindenmayer, A., Mathematical models for cellular interactions in
development, I: filaments with one-sided inputs", Journal of Theoretical Biology
18, (1968), pv 280-299.
[2] Chen, Y., Xu, Y., Guo, B., and Shum, H., Modeling and rendering of realistic
feathers. ACM Transactions on Graphics 21(3): 630-636, 2002.
[3] Parish, Y., Müller, P., Procedural Modeling of Cities. ACM Transactions on
Graphics 21(3): pp. 301-308, 2001.
[4] Rozenberg, G., Salomaa, A., Handbook of Formal Languages. Springer-Verlag,
Berlin Heidelberg, 1997.
[5] Prusinkiewicz, P., Hanan, J., Lindenmayer Systems, Fractals and Plants.
Springer-Verlag, New York Inc., 1989.
[6] Neto, J. , L-Systems aplicados a computacao grafica. Monografia apresentada
na disciplina Teoria de Linguagens, DCC/UFMG, 2003.
[7] Prusinkiewicz, P., Hammel, M., Mech, M. and Hanan, J., The artificial life of
plants. In Artificial life for graphics, animation, and virtual reality, volume 7 of
SIGGRAPH '95 Course Notes, pages 1-1 - 1-38. ACM SIGGRAPH, 1995
[8] Hearn, D.; Baker, M. P. Computer Graphics C version, 2nd edition, Prentice Hall,
1997.
[9] Rogers, D. F.; Procedural Elements for Computer Graphics, McGraw-Hill, 1985.