L-Grammars
Author
I have heard that one could use something called "L-Grammars" to create tree effects in games. I have done a few searches, and could not find any good explanations. Does anyone here know how L-Grammars work, or have a URL to a page that explains them?
L-systems.
Define a set of tokens, each having a meaning.
e.g. (simplisitic)
Then define substitution rules :
Set a recursion threshold (ex: 3)
Set the global parameters (here length, angle)
(they could be part of the expression itself)
Do the substitutions, generate the figure. Here:
Documents [ GDNet | MSDN | STL | OpenGL | Formats | RTFM | Asking Smart Questions ]
C++ Stuff [ MinGW | Loki | SDL | Boost. | STLport | FLTK | ACCU Recommended Books ]
Define a set of tokens, each having a meaning.
e.g. (simplisitic)
F = go forwardS = scale length downA = scale angles downR = rotate clockwiseL = rotate counterclockwise() = subexpression is a ''branch'', state is restored when leaving the subexpression. Then define substitution rules :
Start -> FF -> SF(LAF)(RAF) Set a recursion threshold (ex: 3)
Set the global parameters (here length, angle)
(they could be part of the expression itself)
Do the substitutions, generate the figure. Here:
0 Start1 F2 SF(LAF)(RAF)3 SSF(LASF(LAF)(RAF))(RASF(LAF)(RAF)) Documents [ GDNet | MSDN | STL | OpenGL | Formats | RTFM | Asking Smart Questions ]
C++ Stuff [ MinGW | Loki | SDL | Boost. | STLport | FLTK | ACCU Recommended Books ]
Author
Thanks for the speedy response =)
But, is that just an example, or the equasion? That''s kind of like what I found on the web.. but I don''t really get what you mean.
But, is that just an example, or the equasion? That''s kind of like what I found on the web.. but I don''t really get what you mean.
I hate the Internet. I typed in a nice reply, hit go, then ERROR: no post for you! Argggg.
But here is the gist.
Fruny is right. L-grammer is the language structured used to define Lindenmayer Systems, aka L-systems, which can be used to model flora, trees, and such. Some work has been done by Dr. P. Prusinkiewicz and students from the University of Calgary. They have some publications available in PDF format, here:
www.cpsc.ucalgary.ca/Redirect/bmv/papers/
See especially the most recent SIGGRAPH 2001 publication at the top of the list, titled "The use of positional information in the modeling of plants."
The papers are quite technical, but I''m not sure you''re going to find a satisfactory article that doesn''t get technical.
Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.
But here is the gist.
Fruny is right. L-grammer is the language structured used to define Lindenmayer Systems, aka L-systems, which can be used to model flora, trees, and such. Some work has been done by Dr. P. Prusinkiewicz and students from the University of Calgary. They have some publications available in PDF format, here:
www.cpsc.ucalgary.ca/Redirect/bmv/papers/
See especially the most recent SIGGRAPH 2001 publication at the top of the list, titled "The use of positional information in the modeling of plants."
The papers are quite technical, but I''m not sure you''re going to find a satisfactory article that doesn''t get technical.
Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.
Grammar based modeling of plants, using L-systems.
Its roots start with the logo programming language
for kids (the one with the turtle). There
are a lot of good references on it. One of the projects
I was thinking of doing was building a parser
to read in the language and produce an opengl rendered
image. Pretty cool stuff, and you can make very
detailed models with little grammer code.
Here is a link to my professors powerpoint presentation.
He went over it the last week, and it definetely peeked
my interest.
http://www.cs.uml.edu/~hmasterm/Charts/week13.ppt
(I keep getting an error posting this thing...)
Its roots start with the logo programming language
for kids (the one with the turtle). There
are a lot of good references on it. One of the projects
I was thinking of doing was building a parser
to read in the language and produce an opengl rendered
image. Pretty cool stuff, and you can make very
detailed models with little grammer code.
Here is a link to my professors powerpoint presentation.
He went over it the last week, and it definetely peeked
my interest.
http://www.cs.uml.edu/~hmasterm/Charts/week13.ppt
(I keep getting an error posting this thing...)
It''s an example, there is no ''equation''.
The whole idea is that you do substitutions in a string according to a set of rules you define (usually as a context-free grammar... a whole topic unto itself). Then you ''interpret'' the resulting string to generate a figure.
In my simplistic example, each step you replaced ''F'' (go forward) with ''SF(LAF)(RAF)''
Therefore, in the figure, every straight line ''|'' was replaced with a ''Y'' branch. If you do that recursively, you get a ''tree''.
Documents [ GDNet | MSDN | STL | OpenGL | Formats | RTFM | Asking Smart Questions ]
C++ Stuff [ MinGW | Loki | SDL | Boost. | STLport | FLTK | ACCU Recommended Books ]
The whole idea is that you do substitutions in a string according to a set of rules you define (usually as a context-free grammar... a whole topic unto itself). Then you ''interpret'' the resulting string to generate a figure.
In my simplistic example, each step you replaced ''F'' (go forward) with ''SF(LAF)(RAF)''
S reduce the size of the forward stepF go forward( save the stateL rotate leftA reduce the rotation angleF go forward) restore the state( save the stateR rotate rightA reduce the rotation angleF go forward) restore the state Therefore, in the figure, every straight line ''|'' was replaced with a ''Y'' branch. If you do that recursively, you get a ''tree''.
Documents [ GDNet | MSDN | STL | OpenGL | Formats | RTFM | Asking Smart Questions ]
C++ Stuff [ MinGW | Loki | SDL | Boost. | STLport | FLTK | ACCU Recommended Books ]
The production rules you use determine what sort of tree you get. The tokens listed by Fruny (forward, new branch, rotate, etc.) will stay roughly the same throughout implementations (you definitely need ''forward'' ''new branch'', and variants on the rotation bit.)
I''ve got some sample code for you to play around with over here (C++ and OpenGL/GLUT).
I defined the tokens as follows:
F = go forward
[ = start new branch (push it onto the stack)
] = end of branch (pop last result - move back)
-,+, < > = rotate in one of four directions
In my example code I scaled each branch automatically - that is, the [ token implies "start a new branch, glScalef". This meant I didn''t use an explicit token for scaling down.
Now, get the code and play around with the variable "lstring". Try the following and understand the results:
char lstring[20] = "F";
// or...
char lstring[20] = "F[-F]";
// or...
char lstring[20] = "F[-F+F]";
// or...
char lstring[20] = "F[-F][F]";
etc. The lstring here represents the production rule to generate the tree. You can see that by changing the string you get different trees. (Also, note that the above trees will be two dimensional because I haven''t used the < and > tokens.)
I''ve got some sample code for you to play around with over here (C++ and OpenGL/GLUT).
I defined the tokens as follows:
F = go forward
[ = start new branch (push it onto the stack)
] = end of branch (pop last result - move back)
-,+, < > = rotate in one of four directions
In my example code I scaled each branch automatically - that is, the [ token implies "start a new branch, glScalef". This meant I didn''t use an explicit token for scaling down.
Now, get the code and play around with the variable "lstring". Try the following and understand the results:
char lstring[20] = "F";
// or...
char lstring[20] = "F[-F]";
// or...
char lstring[20] = "F[-F+F]";
// or...
char lstring[20] = "F[-F][F]";
etc. The lstring here represents the production rule to generate the tree. You can see that by changing the string you get different trees. (Also, note that the above trees will be two dimensional because I haven''t used the < and > tokens.)
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement