Skip to content.

Navigation

Toolbox

Billboard Cloud Algorithm

From OpenTree

This is an experimental approach to create billboad clouds, it has yet to proof how fast it will be, or how good it might work.

Contents

Functional description

Step 1: Grouping

At a first step, all leaves will be put in groups

Sub-Step 1.1: Group by Rotation

Each leaf will be put in a group defined by it's rotation. How big the delta between the rotations may be is up to the user. The smaller the delta, the more billboards.

Sub-Step 1.2: Group by Position

Each group will be subdivided into more groups according to the distance between the meshes along the normal vector of that rotation group.

Step 2: Merging

Once all leaves are grouped, each group will be evaluated and the best fitting plane will be generated. Also the leaf count of the group decides if there will be a plane or not. It might not be worth it to create a plane for just a few leaves.

Step 3: Texturing

Each of the planes need a fitting texture now. One way would be to render the leaves that were used to define the plane on a texture. However, it might be faster to simply copy the texture of the leaf to the plane texture. Copy is actually too simple, it must be projected, however, without invoking opengl in that.

Improvement Ideas

This will be a rather simple yet (hopefully) fast implementation.

  • This alogihm will use fix angles and distances for grouping. So they don't shift to catch most possible leaves. To change this might give better billboard clouds, however it will make the algorithm slower.
  • Instead of copying the texture it might be better to write a reference to the uv coordinates of the leaf texture on the plane texture. This way, the leaf texture could be exchanged or altered easily at runtime.
  • At the moment, the rotation about all axis is taken into account. However, since a leaf is flat, the rotation around its own normal is irrelevant! Due to this, it is possible to reduce the number of groups.

Implementation

It is not necessairy to do all Steps after each other. It could be faster to do all steps at once. Then there is only one for loop and no arrays for the grouping are needed.

for (int i=0; i<tree->getLeafCount(); i++)
{
  // == Grouping ==

  otLeaf* leaf = tree->getLeaf(i);

  // -- Get Rotations --
  otVector3 rot = leaf->transform.getRotationDegrees();
  // maybe it would be better to use the leaf's normal vector...
  // otVector3 rot = leaf->transform.apply(otVector3(0,1,0));

  // Since a leaf is visible on both sides: modulo 180
  if (rot.X > 180) rot.X -= 180;
  if (rot.Y > 180) rot.Y -= 180;
  if (rot.Z > 180) rot.Z -= 180;

  // Group = x * rot_groups^1 + x * rot_groups^2 + x * rot_groups^3
  otVector3 rot_group(int(rot.X/180*rot_groups),
                      int(rot.Y/180*rot_groups),
                      int(rot.Z/180*rot_groups);

  int rot_group_no = rot_group.X + rot_group.Y * rot_groups 
                   + rot_group.Z * rot_groups * rot_groups;

  // -- Get Translation --

  // Rotation normal
  otVector3 rotnorm(0,1,0);
  rotnorm.rotXRad((rot_group.X+0.5f)/rot_groups*360*D2RAD);
  rotnorm.rotYRad((rot_group.Y+0.5f)/rot_groups*360*D2RAD);
  rotnorm.rotZRad((rot_group.Z+0.5f)/rot_groups*360*D2RAD);

  // Get Translation (dot product between roatation normal and translation
  float translation = rotnorm | leaf->transform.getTranslation() ;

  // Now it's needed to find out in which group this belongs. 
  // I have no idea of how to do that yet. Maybe I would have
  // to get the boundingbox around the tree in advance.
  // Another method would be to store the leaves in an array
  // for each group. So we could get the min and max translation
  // for each of those arrays.

  // @@@ TODO: insert code @@@

  // == Merging ==

  // Get plane for this group

  // @@@ TODO: insert code @@@

  // Check if the leaf fits on the plane. if not, extend it.

  // @@@ TODO: insert code @@@

  // == Texturing ==

  // Get Texture for this plane

  // @@@ TODO: insert code @@@

  // Project the leaf texture on this plane's texture.

  // @@@ TODO: insert code @@@
}

Get plane for this group

Since we know the leaves all have the same rotation, we can normalise their coordinats to 1 dimension. We then apply a simple sort algo on this data to find the most common values and create a plane with that information.

Optionally we can reject leaves with extreme values(too far from the plane to render useable pixels) to another group and repeat the process.