Lindenmayer Systems

(L-Systems)

Adriano Machado (adrianoc@dcc.ufmg.br)

Jan/2004

Disciplina: Teoria de LinguagensProfessor: Newton Vieira

Sumário

• Introdução• Definição (L-Systems)• Exemplo• Interpretação Gráfica• Aplicação• Conclusão• Referências Bibliográficas

• Proposto por Aristid Lindenmayer em 1968;

• É um tipo particular de gramática;• Um fundamento para a teoria do

desenvolvimento ou crescimento biológico.

Introduçã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

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 , {ab, bab}). Onde:

• Σ=(a,b,c)• w = a• P: ab

bab

Exemplo

• L = ({a,b,c}, a , {ab, bab}). Estado 0 : a 1 Estado 1 : b 1 Estado 2 : ab 2 Estado 3 : bab 3 Estado 4 : abbab 5 Estado 5 : bababbab 8 Estado 6 : abbabbababbab 13 Estado 7 : 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.