Monday, January 26, 2015

Trees...but not quad or binary.

A week ago, after watching 64k demos (if you haven't seen one yet, check it out), I realized that programming can be boring if you only see numbers on the screen. I opened Unity and started a new project.

I hardly finish my projects, maybe 1 or 2 programs of mine are completed. So I don't know how long can I concentrate on one thing, but I hope this one will be the 3rd to finish.

This game will be using procedural algorithms, just like Minecraft or Terraria does. My plan is to make a 2D fantasy world (side-scroller ofc) using proc.gen. where I can. My main goal is to create a dynamic environment, with lots of movement - grass, trees, stars, sun, particles, butterflies, birds and other effects.

Fortunately, I did not have to start it from the very beginning. From another unfinished project I managed to reuse the scripts for a fully functional modular skill system, movement system, cameras and controls. I chose to create a line renderer and a tree first, because they are easier than other procedural things I think, and later on I can use (parts of) them to create better 2D effects.

What is a fractal tree?

It would be good to make something similar on the computer. As you might know, the algorithm is:
  • create a branch (line).
  • at the end of the line, split at some angle, and draw the two branches
  • for these two branches, start it again from step 1, until you have the specified number of lines, layers or the width is small enough.
How can it be implemented? - With recursion.
How can it be better? - With randomness, more variations, and more movement..
Random factors: 
  • the angle at which the branch will split
  • the number of branches per parent branch
  • the width and height decrease factor of the branches
You can use controls to clamp these factors to allowed ranges. 
It also looks good, when the branches are not staright. This can be done using a spline. I use Catmull-Rom interpolation with 3 control points (the 2 ends, and a displaced midpoint).
To make it even better, you can animate how it grows:
  • grow a branch over time
  • when it is finished, start the grow function in another routine
It can be implemented easily with corutines in Unity:

(with coroutines it is not really recursion, and you should not fear of overflows, neither should you with simple recursive alg cuz I don't think a tree should have millions of branch layers)

private IEnumerator GrowBranch(Vector3 branchPivot, Vector3 growDirection, float width, int currentLayer, AnimLine root)
        {
            if (currentLayer < maxLevels)
            {
                Transform rootTransform = null;
                if (root != null) rootTransform = root.Line.transform;

                AnimLine mainBranch = new AnimLine(rootTransform, branchPivot, tessellation, treeMaterial);

                Vector3 norm = new Vector3(growDirection.y, -growDirection.x, growDirection.z).normalized;
                Vector3 middle = growDirection / 2.0f;
                middle += norm * Random.Range(-growDirection.magnitude / 10.0f, growDirection.magnitude / 10.0f);

                List<Vector3> controlPoints = new List<Vector3>()
                {
                    Vector3.zero,
                    middle,
                    growDirection
                };

                mainBranch.CreateSpline(controlPoints, width, width * widthDecrease);

                if (root != null)
                {
                    mainBranch.Line.transform.parent = rootTransform;
                    mainBranch.Line.RootType = LineMesh.RootPoint.RootLine;
                    mainBranch.Line.RootLine = root.Line;
                }

                var growEnum = StartCoroutine(mainBranch.UpdateLine(LayerGrowTime));

                lines.Add(mainBranch);

                int noBranches =
                    (int) Mathf.Lerp(Random.Range(minBrachPerLayer, maxBrachPerLayer), minBrachPerLayer,
                        (float) (currentLayer) / maxLevels);

                Vector3[] newBranches = new Vector3[noBranches];

                if (lines.Count+newBranches.Length > maxBranches)
                    yield break;

                for (int i = 0; i < newBranches.Length; i++)
                {
                    Vector3 angles = new Vector3
                    {
                        z = (((i & 1) * 2) - 1) * Random.Range(minAngle, maxAngle)
                    };
                    newBranches[i] = RotatePointAroundPivot(growDirection, Vector3.zero, angles) *
                                  Random.Range(minHeightMult, maxHeightMult);
                }

                yield return growEnum;

                foreach (var branch in newBranches)
                {
                    StartCoroutine(GrowBranch(growDirection, branch,
                        width * widthDecrease, currentLayer + 1,
                        mainBranch));
                }
            }
        }



I implemented an AnimLine class, which can create an animated line, weld lines and transform them. It uses meshes and only updates the necessary parts, so it's pretty fast. It also looks good to have the wind blowing the branches. Since in the AnimLine class I can parent lines and set their pivots, the wind function uses local angles to move the branches, and some randomness.

private IEnumerator UpdateBranches()
        {
            while (true)
            {
                if (maxWindStrength==0.0f)
                {
                    yield return null;
                    continue;
                }
                var time = Time.time;
                for (int i = 1; i < lines.Count; i++)
                {
                    if (lines[i].Line.PointCount < 2) continue;
                    float localStrength = 1.0f;
                    if (maxWindHeight != 0.0f)
                        localStrength = Mathf.Clamp01(lines[i].Line.GetPoint(0).y / maxWindHeight);
                    lines[i].Line.transform.localEulerAngles = new Vector3(0, 0,
                        maxWindStrength * localStrength * Mathf.Sin(time * windSpeed - i));
                    lines[i].Line.UpdateLine(0, 1);
                }
                yield return new WaitForSeconds(0.03f);
            }
        }

Now this is what I currently have. However, there are still problems with it. The infamous Z-fighting. Since I use meshes on the same plane, and because I use perspective camera and cannot offset the meshes too much, also deciding about the offsets is comlex. The weld points of different lines have wrong uv coordinates, so the texture clamps there. I will add a better work-sharing model too, so it will be more effective to update branches. Now when it updates a specified number in a frame, the update returns and continues it in the next frame, so it keeps the desired fps even with tens of thousands of branches, altough it looks terrible to have a low update batch size.

As soon as I manage to finish a simple demo and add more functions, I will upload it with my line renderer class in an unity package. I will also add a skinned mesh line renderer class. Until that here's what it currently looks like, animation demo soon.

No comments:

Post a Comment