SimpLSystem - L-System collaborative project

jfriedmanjfriedman Fabric for Houdini Posts: 81 ✭✭
edited February 2016 in Canvas Graphs and Presets

Hello All,

I've made an L-system extension, called SimpLSystem. I was thinking about what I wanted to do with it, and I've decided I'd like to use it as the starting point to try to start a community project. So I changed the name to SimpLSystem (it was originally JFLSystem), cleaned up a bit, and starting writing this post.

This project doesn't have any well defined goals at this point. As such, I'd like to invite anyone to discuss directions they'd like to go with it here. If you'd rather just do whatever you'd like with it on your own, please feel free to do that as well.

This is a personal project not affiliated with Psyop, but I'd like to thank them anyway for being so supportive of this kind of thing.

Repo

https://github.com/jonahf/SimpLSystem
Background on L-systems: https://en.wikipedia.org/wiki/L-system#Examples_of_L-systems

The repo contains the extension, and two sample canvas files. The canvas files contain the examples on Wikipedia. Theres one that implements them more or less straight ("wikipedia_examples_standard.canvas"), and one that has more creative interpretations of the same L-systems ("wikipedia_examples_interpreted.canvas"). All the pictures here are from the latter one.


An interpretation of a Koch curve L-system

About the project

As far as I'm concerned the project doesn't really have any defined goals yet, just that I would like it to collaborative and in the community.

A few possibilities for directions this could be taken: The most obvious one would probably be to develop applications of L-systems, such as dynamically creating plant geometry. Another direction would be just to generate arbitrary geometry - it currently just makes a Vec3[] for points, and Xfo[] for leaves. Another direction might be trying to take advantage of the new feature of evaluating DFG graphs in KL, to make the behavior of the evolving system programmable in interesting ways.


An interpretation of a Pythagoras tree L-system

Tech overview

The system consists of two parts right now, the L-system, and the interpreter. The L-system defines and generates the strings, and the interpreter interprets the symbols in the resulting string and performs the walk ("walk the turtle").

The only thing the interpreter can currently do is "walkTheTurtle()", which refers to turtle graphics (see the Wikipedia article). The system continually updates a Mat44 internally while interpreting string to keep the transform updated, and drops points along the way.

That's it for the moment. Drawing Lines while it goes is (at least one) obvious next step.

Technical details

SimpLSystem - The Iterative grammar part of the L-system.

  • struct SimpLRule Defines an L-system rule, such as "A"->"AB".
  • object SimpLSystem The L-system object, initialized from an array of SimpLRules and a start string (axiom).
  • SimpLSystem.evolve(Size iterations) evolves the system iteratively, expanding the string formed.

SimpLInterpreter - For interpreting the L-system into 3D space:

  • object SimpLInterpreter
  • SimpLInterpreter.addSymbol!(String symbol, Xfo transform, Integer leaf) Adds a symbol to the interpreter, and a transform to apply when encountering that symbol. Using this all the non-branching symbols such as translate forward, turn, roll, pitch and yaw in the usual ways, plus more.
  • SimpLInterpreter.addBranchSymbol(...) Adds two symbols, one to branch the tree (push a transform onto the stack), and one to unbranch the tree (pop a transform from the stack). Arbitrary transforms can be added on branching and unbranching as well.
  • SimpLInterpreter.walkTheTurtle(...) Walks down the string, applying the interpretations as it goes, generating an array of positions it visited along the way.

There's also a compound for "add standard symbols", which adds F as move forward, +- for turn left and right, &^ for pitch up an down, \^ for roll left and right, | for turn around, and [] for push/branch and pop/unbranch.

Non-standard things this particular L-system does:

  • SimpLSystem.partialEvolve!(Scalar iterations) evolves the system with partial iterations. 8.4 iterations would mean that the 9th iteration is only done on the first 40% of the string, and the remaining 60% of the original string left alone. This can make interesting half-formed L-systems, is helpful in debugging, and can be used to animate the system's construction.
  • Every symbol can have a full Xfo applied to it, not just an angle or walk distance. For example, you could apply a scaling every time the tree branches, or rotate slightly in one direction every time you walk forward.

Comments

  • PoobyPooby Posts: 122

    A great idea.
    It's probably a bit beyond my current skill set to contribute right now, as I've only started learning, but having a vegetation making tool seems a very useful thing and developing a solid L system to build on a great idea for a community project.

    I'm primarily trying to help the visual programming development, in my own small way, through providing feedback on Canvas.

  • malbrechtmalbrecht Fabric for Houdini Posts: 748 ✭✭✭

    Moin,

    very cool start! I would love to contribute, although I am by no means a Fabric/KL expert. But ideas I sometimes have ... I created a (proof-of-concept-ish) experiment somewhat loosely based on a Fabric vegetation script a couple of weeks ago testing out Fabric's modo integration here:

    ... Around that project I noted down some ideas about how a flexible "vegetation system" could, hopefully, be more performant than the ususal "do some temporary meshing around the point cloud and check for collisions" approach. I'd love to discuss those ideas.

    One wish I do have for such a system is that it should be performance-optimized, PEX where possible and, if necessary, taking shortcuts to get speed over mathematical accuracy. Because if such a tool is to be accepted by users, it needs to give "life" feedback (abusing the hype word here).

    Anyway, I'll give your repo a good look once someone faxes me a six pack of time!

    Marc


    Marc Albrecht - marc-albrecht.de - does things.

  • Paul DoylePaul Doyle Administrator, Fabric Employee Posts: 226 admin

    this is very cool - thanks for putting this out there Jonah!

    CEO at Fabric Software
    Twitter

  • jfriedmanjfriedman Fabric for Houdini Posts: 81 ✭✭

    @Paul Doyle:
    Thanks!

    @Pooby said:
    It's probably a bit beyond my current skill set to contribute right now, as I've only started learning, but having a vegetation making tool seems a very useful thing and developing a solid L system to build on a great idea for a community project.

    If you'd like to try anyway, even just making samples or examples that implement neat L systems could work fine. I really do want this to be a community project and that means taking contributions at all skill levels.

    @malbrecht:

    Very cool vines tool, I dig it!

    So about vegetation: L systems are really fractalish-thing generators that happen to be able to generate plant-like branching structures. I'm not 100% convinced they're the right tool for artist tools to create vegetation, so if a project were started to generated good plant geometry, I would want to decouple it from the L-system proper a little bit. For instance, have the L system generate a Lines object with the right structure and certain attributes, separate data for leaves, and then have a vegetation meshing system that can generate nice plant geometry from that. This way, other sources of data could be used to generate the geometry, not only L systems. I think this would have a lot of other advantages too.

    The geometry generation, while part of the same project, might be a related but separate system. We'd want some changes to the L system proper too though, probably. Symbols interpretations can currently perform three actions: Apply a transform to the turtle, create leaves, and branch/unbranch. I think we'd want to add one or two more:

    Randomization: (You don't want to generate the same plant every time). Perhaps you could optionally give the interpretation of symbols a second Xfo for randomization, which would be used as the variance range to modify those transforms. I think this can probably fit into the system we have for interpreting rules.

    Symbols that modify the interpretation of other symbols: This is something I saw existing in other L-systems, which is made a little more complicated by our use of whole transforms as interpretations: There were symbols that modify the interpretation of other symbols. You could use them to, for instance, negate the direction of turning. I don't think these fit in very well right now as just another type of interpretation, and I'm not sure exactly how to best handle modification of other symbols while walking.

  • malbrechtmalbrecht Fabric for Houdini Posts: 748 ✭✭✭

    @jfriedman - thanks for the quick response. Totally got you, I was short circuiting from the first screenshot you posted.
    Yet, I agree that geometry creation might still be a "cross over" area of interest. But, for example, collision control is probably out of the L-System's playground.

    I'll still give the extension a go asap, maybe at least I can provide ideas/input, if not some "foot work for stupids that write before thinking" :-D

    Marc


    Marc Albrecht - marc-albrecht.de - does things.

  • jfriedmanjfriedman Fabric for Houdini Posts: 81 ✭✭
    edited February 2016

    @malbrecht said:
    Yet, I agree that geometry creation might still be a "cross over" area of interest.

    I think so too and it's definitely an area worth exploring.

    But, for example, collision control is probably out of the L-System's playground.

    Probably, at least an ordinary L system. But who is to say you couldn't have an interpreter for the L system that travels through a signed distance field?

  • Roy NieterauRoy Nieterau Posts: 258 ✭✭✭

    @jfriedman I'm a bit into a continuous stream of crunch time, but once I have some more time on my hands I'm very interested to playing around with this and having a look at how I could contribute to this.

    It seems the Issues are closed on the repository, but I think that could be (when opened up) a good place to discuss features, improvements and alike. E.g. adding the randomization could be an Issue on the repository that could also be referred to upon commits.

    Thanks for sharing!

    Also...

    But who is to say you couldn't have an interpreter for the L system that travels through a signed distance field?

    Not sure why, but that does sound so badass.

  • jfriedmanjfriedman Fabric for Houdini Posts: 81 ✭✭

    @Roy Nieterau said:
    It seems the Issues are closed on the repository,

    Should be open now, great point!

    Not sure why, but that does sound so badass.

    I think it really might be..

  • EricTEricT Administrator, Moderator, Fabric Employee Posts: 300 admin

    I've only known L Systems to be mentioned in Vegetation type systems. What else can they be used for? Maybe compiling a list we can compare the similarities and see if trying to steer this extension in a way to be able to be utilized as much as possible. Can this be used to generate procedural textures / images? Is that useful for anything outside of just textures and images such as maps across a mesh?

    Eric Thivierge
    Kraken Developer
    Kraken Rigging Framework

  • malbrechtmalbrecht Fabric for Houdini Posts: 748 ✭✭✭

    L-Systems are recursive (fractal-ish) "growth" algorithms, that's why they are often used as a base for vegetation (which is growing in some kind of "recursive-ish" pattern ...). But you need to introduce some randomness and additional "forces" (gravity, light, nutrition, maybe colliders etc) to make a realistic vegetation system. If you ever wrote a Turtle program (in Logo, for example), you most likely created some basic L-System :)

    The interesting thing about them is that they are, generally, quite easy to control but can quickly give you complex patterns. I'd go as far as saying that - with the right amount of "additional dirt" having such a fundamental fractal-geometry creation tool can provide a lot of naturalistic material - vegetation (technical fundaments), rocks, minerals, shells, even fur-patterns and the like.
    It's "basic science", but useful on many higher levels :)

    Marc


    Marc Albrecht - marc-albrecht.de - does things.

  • jfriedmanjfriedman Fabric for Houdini Posts: 81 ✭✭

    @EricT said:
    Can this be used to generate procedural textures / images?

    I have noticed that 2d L-systems have a tendency to criss-cross themselves like crazy. Perhaps you could do one where every time it crosses a pixel or volume it leaves a little bit of weight that accumulates, you might have something interesting, that could perhaps be used as a height map.

    To brain storm a bit more, they can also create space filling curves. Space filling curves look neat and can be used to index grids in a way where adjacent cells will be close together in memory.

    I bet a vein/capillary structure in 3d would also be modelable at least partially as an L-system.

  • mootzoidmootzoid Fabric Employee Posts: 182 Fabric Employee

    Very interesting discussion, thanks for starting this discussion, Jonah!

    Five years back I wrote some "emTree" plugin for XSI that used some custom L-System. Never finished it, but it worked really well, was interactive and aside from plants it could also grow stuff like hair. Finally it created a single, closed mesh as a result.
    As for collisions - even though they never made it into the pugin - I had planned something similar to what Jonah already mentioned in a previous post: use an octree to keep track of parts in space that are already occupied by something.

    Here some pics from emTree (super old):



    Cheers,
    Eric

  • borjaborja Administrator, Fabric Employee Posts: 470 admin

    Thank you for sharing @jfriedman it looks great!

    Borja Morales
    Technical Product Manager
    Fabric Software Inc.

  • jfriedmanjfriedman Fabric for Houdini Posts: 81 ✭✭

    @mootzoid: Hi Eric, that looks great. Can you share any details about how the meshing worked?

  • mootzoidmootzoid Fabric Employee Posts: 182 Fabric Employee

    Hi Jonah,

    when I started with the project I tried to think of an easy solution to solve the meshing and came up with the idea of using pre-built mesh items as inputs. Those items had to be built in a specific way and also have some custom parameters to define their 'behavior' (e.g. probability of being used at certain depths, growth direction, randomness).
    So the rules / grammar was encoded partly in the topology of the mesh items and partly in the attached custom parameters.

    In the bottom left corner of the first image (in my above post) you can see the three source mesh items that were used to grow the final mesh. What you can't see are the attached parameters, but they were roughly something like this:

    • use this item only for a depth between 0 and X.
    • random twist around your local y axis.
    • have the preferred growing direction X/Y/Z.
      etc.

    Below is another test I made: the setup contains two input mesh items, the head and a simple cylinder with the following rules:
    "use the head item only once at depth 0" + "use the cylinder items at any depth except zero" + "make the cylinder items have a preferred grow/bend direction".
    Finally, as a post-meshing step, any open holes in the mesh are closed.

    Cheers,
    Eric

  • jfriedmanjfriedman Fabric for Houdini Posts: 81 ✭✭

    That's a really interesting technique for doing that. Just thinking out loud about it in the context of system where the L system defines what geometry is generated and not the other way, perhaps you could supply geometry for the various topological branching possibilities and it could stitch them together in the same way. The possibilities might be I, Y, and X.

  • mootzoidmootzoid Fabric Employee Posts: 182 Fabric Employee
    edited February 2016

    The approach has one huge benefit: creating the final mesh is trivial (and very fast) since you only need to merge together pieces that are easily mergeable by design.
    The backside was, at least in the way I made it at the time (over nine years ago), that my approach makes it kind of difficult to control certain growing behaviors, which is why I never released the tool.

  • malbrechtmalbrecht Fabric for Houdini Posts: 748 ✭✭✭

    Using a set of defined "building blocks" is exactly what I want to do for my "flexible veg system" :) For collision detection I have been playing with the idea of a "zBrush"-like voxelspace (which, in a way, is like the octree idea) where each "node" (a building block or connection node) occupies one small-byte (2-4 bit) in the collision cluster. By not only using "occupied" versus "air" in the cluster, a collision with specific "occupied" nodes could be used to trigger specific growth/death scenarios.

    But in my case that's all still head-work (aka "daydreaming"). I still need a source for TIME ...

    Marc


    Marc Albrecht - marc-albrecht.de - does things.

  • AhmidouAhmidou Posts: 161 ✭✭

    I'm coming late in the discution, but thanks a lot Jonas for sharing this project!

    I remember one of my first scripting project was a tree generator in Softimage 1.5, I knew nothing about L systems and was trying
    to understand basic concepts like recursive loops....that was almost 16 years ago.
    Having a seemless mesh for the trunk and branches, is still some kind of Holly Grail, and Eric's method is very interesting.

    My personal idea would be to use a mesher simular Zbrush's Zsphere, or Blender's mesh skinning. I really wish I had more time....

    That's cool stuff, thanks again!
    Ahmidou

  • jfriedmanjfriedman Fabric for Houdini Posts: 81 ✭✭

    An update - relatively minor, but with some cool pictures:

    The main new thing is a new SimpLTurtle interface, which is an interface meant for things that want to generate geometry while the interpreter walks the L system. We have two turtles, PositionsTurtle, which draws dots as before, and LinesTurtle, which creates Lines objects. It can also create scalar attributes on the lines to record branch depth, (how many branchings we're downstream of), stack depth (how deep the branch stack is at any given point, this is what's pictured in the first two) and string ratio, which is just a 0-1 parameter of how far down the string we were when each piece of geometry was generated. The examples are updated too.

    So I have an idea- it's been done before, but I'm not sure it's every been done well. I want to try to make a genetic algorithm to create L Systems. I'm planning on using the canvas graphs in KL feature for that. The idea will be that you give it a canvas graph with the features exposed on which you want the genetic algorithm to work on. Then you'll pick what you care about in your fitness function (max spread of leaves, minimum segment length, etc), and let it run.

  • AlexanderMAlexanderM Posts: 132 ✭✭

    About trees. This is a test of colonization algorithm. http://algorithmicbotany.org/papers/colonization.egwnp2007.large.pdf

    Let's say NO to Autodesk®Fabric®

  • scaronscaron Fabric for Houdini Posts: 171

    @AlexanderM did your post actually use @jfriedman SimpLSystem when implementing the paper you linked? Just wondering because it wasn't clear to me.

  • AlexanderMAlexanderM Posts: 132 ✭✭
    edited March 2016

    No, it's a completely different method. I didn't want to start a separate topic because of such unimportant work. I just supported the theme of generation of trees :) .Unfortunately my implementation of paper is very slow

    Let's say NO to Autodesk®Fabric®

  • scaronscaron Fabric for Houdini Posts: 171

    ok, the paper listed using l-system as a last pass to refining the skeleton. wanted to know if you employed it there...

  • AlexanderMAlexanderM Posts: 132 ✭✭

    no, I used only this part

    Let's say NO to Autodesk®Fabric®

  • jfriedmanjfriedman Fabric for Houdini Posts: 81 ✭✭

    Ah, I had the same question.

    A minor update on my part, I have a working genetic algorithm. I Just don't have a lot of useful fitness criteria yet. I'll post something about it soon.

  • LalancelotLalancelot Posts: 41

    Sorry to sound like the noob that I am, but could you tell us the right way to install this. I have tried, and of course, nothing worked. :/

  • LalancelotLalancelot Posts: 41

    Forget it, I got it. That thing is incredible. Now, all I have to do is understand it.

  • jfriedmanjfriedman Fabric for Houdini Posts: 81 ✭✭

    Ah, fantastic! I should have the genetic component of it ready to play with soon as well.

    I recommend reading up on L systems in general first. If you understand what they do, I think the way this one does it is fairly straightforward.

Sign In or Register to comment.