Just another WordPress.com site

Archive for October 30, 2010

Understanding Fractal and L-System

Introduction

Fractal and L-system have been around for many years. Some of them are very simple and easy to create, and the others can be very complex. This article will explain the basic about both of them.

Fractal

Fractal is a geometric shape that is considered as infinitely complex object that can be scaled infinitely without reducing its complexity on all level. The common feature of fractal is self-similarity which means every part of the fractal is similar to the whole fractal. The famous example of the fractal object are Mandelbrot set and Koch snowflake.

Mandelbrot set is a fractal that is generated by using a recurrence relation of each point in the space. Because of that, the self-similarity of this fractal is only an approximation of the whole fractal or we can call it quasi-self-similarity. If a part of Mandelbrot set is zoomed, the result will not exactly the same as the whole Mandelbrot set but still similar to the whole Mandelbrot set.

As you can see at the pictures above, when the Mandelbrot set is zoomed 2000 times, it still has the same complexity as the original Mandelbrot set. Although the shape of the zoomed version is different that the normal sized, it still has similar characteristics.

Koch Snowflake, on the other hand, is generated using geometric replacement rule that applied iteratively to the initial geometric shape. In case of Koch Snowflake, the initial shape is a triangle which consist of 3 individual straight lines. Each of those lines will be replaced by another form of shape (we can call it generator). The process will be iterated some times to generate more detailed object. This kind of fractal can be also scaled up infinitely.

Usually, the fractal generated using iterated function will be exactly-self-similar. Another famous examples of this fractal type are Cantor set, Peano curve, dragon curve, and Menger sponge.

L-System

L-system was proposed by Astrid Lindenmayer. It is a system string rewriting system. In general, rewriting is a technique to define a complex object by changing the object’s parts, which are originally the more simple parts, into the more complex parts consecutively by using a set of rewriting rules and productions. It is very similar to the iterated function fractal explained above. Actually L-system itself is a kind of iterated function fractal that operates on a sequence of string.

As it is easier to study the rewriting system by using string than a graphical representation, there were several concepts of rewriting system appearing, including Chomsky grammar and L-system. The main difference is how the productions are applied to the existing string. While Chomsky grammar replace the string with the production sequentially, L-system replace all the string simultaneously in parallel.

The simplest class of L-System which are deterministic and context free, called DOL-System. For example, assume that a string is formed by two letter, a and b, which can appear multiple times in a string. Every letter has its own rewriting rule. The rule a → ab means that every letter a will be replaced by string ab, and the rule b → a means that every letter b will be replaced by string a. The rewriting process starts from a distinguished string called axiom. Assume that the axiom contains the letter b. In the first rewriting phase, axiom b is replaced by a using production b → a. In the second derivation, a is replaced with ab from the production a → ab. String ab has two letters, both of them will be replaced simultaneously and it will produce aba. Using the same method, aba will produce abaab, then it will become abaababa, then abaababaabaab, and so on.

You can think it like the picture below.

Assume that V is an alphabet, V* is a set of every words of V, and V+ is a set of non-empty words of V. A string in OL-system is an ordered triplet G = {V,ω,P} where V is the alphabet, ω ∈ V+ is a non-empty word which is called axiom, and P ⊂ V × V* is a finite set of productions. A production (a, χ) ∈ P written as a → χ. The letter a is a predecessor and the letter χ is the successor of the production. It is assumed that for any letter a ∈ V, there should be at least one word χ ∈ V* such as a → χ. If there is no production specified for a given predecessor a ∈ V, the identity production of a → a is assumed as the part of production P. An OL-system is deterministic (noted DOL-system) if and only if for each a ∈ V there is exactly one χ ∈ V* such that a → χ.

Let μ = a1 … am be an arbitrary word over V. The word ν = χ1 … χm ∈  V* is directly derived (or generated by) μ, noted μ ⇒ ν, if and only if ai → χi for i = 1,…, m. A word ν is generated by G in a derivation of length n if there exists a developmental sequence of words μ0,  μ1,…, μn such that μ0 = ω, μn = ν and μ0 ⇒ μ1 ⇒ … ⇒ μn.

L-system can be used to visualize the structures by embedding graphical symbols in the string that can be used later to render it. Turtle commands can be used to describe and visualize a wide range of L-systems including Koch’s snowflake, plants and branching structures. The concept behind Turtle Graphics is that the ‘turtle’ is given instructions relative to its current position and as it moves it leaves a pen line mark behind it. By using turtle graphics, shapes, drawing and structures can be defined in the terms of a L-system. Using a bracket extension to Turtle Graphics, L-systems can support the branching structures such as trees that are predominant in nature.

The picture above is an example of L-system that is rendered by using turtle graphics. It can be used to produce natural forms quite nicely. Lindenmayer himself use this system to produce realistic looking 3 dimensional representation of various plants.

The pictures above are the examples of generated plants using L-system.

Maybe that’s all I can explain about fractal and l-system for now. The area of research that involve fractal and l-system is very large so it’s impossible for me to explain it here. You can find many books that explain about fractal in detail. For the next article, I will explain how to implement l-system by using java.

Advertisements

Creating Your Own 3D World Editor with JMonkeyEngine 2.0 (Part 5) – Fill Your World

Introduction

Until the 4th part of the articles, we have finished our terrain editing feature of our world editor. We can alter the shape of our terrain as we want. We can also paint the texture to our terrain to make it looked more realistic. But we haven’t been able to put another objects on our terrain. For example we want to put some characters, buildings, or maybe some trees. This article will cover that. I think this part is not to hard to follow since you got the basic already. I will tell you the basics you need to put your models onto the terrain, but you should think of how to manage every models you have on your terrain properly by yourself.

3D Models

Before I begin to explain how to put the models onto the terrain, I will start with the basic explanation with 3D model. First of all, jME is one of many engines that support many kind of model format. The other engines usually can load several different 3D file formats, and jME is equipped with many loaders that we can choose. From those many formats, I think the most reliable one is ogrexml. It is because some features that I can’t find in the other format loader. For example, to control the animation, ogrexml can use the animation name instead of the starting and ending frame. It can also support animation blending. Ogrexml can also be exported from some 3D modeling application such as 3dsmax and blender (with additional plug-in). I think the jME developer will also agree with this because they use ogrexml as their only supported model format in jME 3. If I’m not wrong, jME 3 also support wavefront obj, but it’s only for static object. For that reason, I will only use ogrexml file format in my world editor.

When the 3D scene is exported into ogrexml format, it usually divided into some parts. There’s a file to contain the scene information (.scene). There’re files to contain the mesh data (.mesh.xml) and the skeleton data if the model has skeleton (.skeleton.xml). The three of them are in xml format, so we can read and edit it without any editor (of course we won’t do that). Then the last one is a file containing material information which is not in xml format but still readable (.material). To load them into our jME application we have two options. First is we can load the .scene file only and the second one is we can load the .mesh.xml and .material files separately. We will never need to load .skeleton file as it will be loaded when we load the .mesh file. I choose the first method for my world editor. It means I won’t need to store 2 file paths (mesh and material) to load the model. I only need to know the path for scene file.

If you use ogremax (3dsmax plug-in to export the scene into ogrexml format), you will need to add something into the scene file. It seems when exporting using ogremax, the ogrexml version is different than the one jME use or maybe there are some options in ogremax that I have to change(it’s only my thought though). This is the original .scene file exported by ogremax

Then this is the modified version. I only add <externals> which contains the information of which material file to be used in the scene.

Then I also modify the material file. The picture below is the original one. I delete the settings for ambient, diffuse, and specular. Those settings will affect the lightning state in our jME application. Deleting them would make no change to our lightning state.

Loading 3D Models

Since we will only use ogrexml, it is easier to load the objects. I made a static method to load the ogrexml scene and return it as a Node. This is the code.

Placing the Objects

If you have ever done flagrush tutorial on the jME website, there is a part which explain about how to place the object exactly on the terrain. It means no matter how high the terrain is on some point, the object will always be placed on the terrain. That tutorial also explains how we place the object to follow the tilt of the ground. In my world editor, I only allow my object to move in 2D plane, thus are xz-plane. It means, for the movement in y-axis I move it automatically to the terrain height. Of course this kind of movement is lack of flexibility. If the user wants to make the object floating or planted on the ground, they have to change the model’s pivot position manually. But everything will depend on the game you want to create with this world editor. My game won’t allow any object to be placed not on the ground, so there’s no point to make it able to move on y-axis.

You can also choose your own way to move the objects. You can use the help of 3D xyz-axes to move the object (similar to many 3D authoring tools) or just drag the object around to move it. In my case, I will choose to drag the object to move it. I don’t need 3D xyz-axes since my object can only move on xy-plane. It is also harder to implement since we have to know which axis the user click and then where the user drag the axis. But if we drag the object directly, we can reduce some unneeded operations. You can choose one that suits your need.

If you choose to drag the object directly, you only have to know which object do you click. Then do a little mouse picking to the terrain, and move the clicked object to that position. It should be very easy to do.

If you use 3D xyz axes, first you have to create the axis when you click the object. Then you have to check which axis the user click. Let’s says the user click on the x-axis. Then we have to check how far the user drags the mouse around. Here we have to decide which mouse coordinate will affect the object movement. For example for the x-axis, is the only one that affects the movement is the x coordinate movement of the mouse? Of course we also have to decide how it will affect he object. For example if the mouse is dragged to the right, usually the object will also move to the right or translated by a positive number along the x-axis. But how about if we look the object from different angle, let’s says from behind, is dragging the mouse to the right still move the object to the right? Of course it shouldn’t, or else it will look weird. You have to take all of them for more consideration.

Rotating the Objects

For this type of transformation, you have to decide which axis you will use to rotate the object. For almost every 3D authoring tools, they can use all three axes to rotate the object. But of course it is more complicated to make than using only one axis to rotate. For my world editor, I only use y-axis as the rotation pivot for my object. It means my object can only be rotated to the left or right. My game doesn’t need the objects to be rotated in the other ways. To rotate it around y-axis, I pick the clicked object, then calculating how far the mouse dragged to the left or right. Then I convert that distance into the rotating angle. Finally, I rotate the object.

If you use all three axes to rotate the object, you will find the same problem as in translating the object. You need to take the viewer position and angle into the consideration when rotating the object.

Scaling the Objects

To scale the object, you also have to decide whether you want uniform scaling or non uniform scaling. I prefer uniform scaling as it is easier to implement (the reasons are similar to translating and rotating the object) and also, doing non uniform scaling will create undesired effect. The texture maybe distorted because we can’t dynamically change the texture uv coordinate. For scaling, I will pick the clicked object and then calculating how far the mouse is dragged as the scaling ratio. It is not too different from rotating.

Adding Trees

Trees are important elements in the scene. But it is very hard to make it looked real but only needs very little processing power to render into the scene. Some games use billboard node for their trees. But sometime it won’t work for some cases. Some other games use a low poly model for the trees. Of course it won’t be looked very real. But for my game, I think a low poly model should be enough. So I will use that one. To place it on our terrain, you can use the same way as the other object or you can use scattering brush to place it randomly.

Conclusion

Those are the basic to place the objects on our terrain. There are still many things that you can add to your scene. You can add water surface to your scene. You can also give skybox or something else to cover the sky. You may also let the user to change the direction, color, and intensity of the lightning. There are still many rooms for improvement to make you world editor more powerful and flexible. You may want to make your world editor as generic as possible.