Jump to content
  • Advertisement
Sign in to follow this  
JDX_John

Dynamic tree generation

This topic is 2640 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm interested to read some good articles about how to generate polygons for a tree (principally the branches/trunk not leaves), based on the idea that I have the basic structure defined i.e. not procedurally generating from scratch but 'clothing' the skeleton of the tree with polygons so branches attach nicely, etc.

Share this post


Link to post
Share on other sites
Advertisement
Thanks. I like the Implicit Surface idea - but how do you actually find points on the surface? They describe it as a way to tell if a point is on a surface but you don't want to scan the whole 3D space, you want to know where the surface is to generate vertices on it and tie them into polygons.

Share this post


Link to post
Share on other sites
With implicit surfaces, if you know that the object is a single volume (ie, no disconnected bits), then you can cast a ray into the volume and progress along cells (cubes, in the marching cubes algorithm) until you find a cell that contains a piece of surface. From that initial intersection, you can devise a scheme to test connected neighbors in an iterative or recursive fashion, in effect attempting to follow the surface. Each neighbor is iterated and tested; if it contains a piece of surface, the cube is evaluated and polygons are constructed for it and inserted into the mesh, then the cube is marked as Visited in some fashion and its neighbors are iterated and tested. If the neighbor does not contain a piece of surface, it is discarded. Of course, this works best, as I mentioned, with implicit surfaces that delineate a solid, one-piece object.

Note that trees are a particularly difficult class of object to represent well with implicit surfaces. The crown of a tree can cover a larger area, but the individual branches can be quite small. Branches occupy less than 20% of the volume of the crown; the rest is empty space. What this means is that unless you subdivide the space the tree occupies very, very finely, then you will miss details of the tree. Smaller twigs, etc... will be removed. But if you do subdivide the space deeply, then you start hitting some serious memory or processing walls, and generating some huge meshes.

The Might Maple article that the previous poster linked discusses an explicit meshing algorithm that I believe is probably better, at least from a video game art perspective, than an implicit surface. The segments of the tree can more easily be meshed while taking into account the relative size of the segments in relation to the other pieces. So you won't drop any twigs, for example, and can in fact degrade the mesh resolution to account for the fact that the twig will be small enough that nobody will notice it is represented by a 3-sided tube. Also, generating the 2D texture coords to map the tree with textures is significantly easier when using explicit meshing than it is with trying to parameterize an implicit surface. The most difficult parts of explicit meshing, of course, are the forks, or "ramiforms", as that article calls them. However, once you have figured them out, the rest is relatively simple.

Of course, explicit meshing also has drawbacks. With blob objects, it can be easier to model all the bulges and bumps and knots that living trees exhibit, while explicit meshes tend toward the rigidly perfect. Even with random noise and variation applied to the explicit mesh, I feel that the implicit mesh tends to be more organic-feeling. This, however, is probably due to weaknesses of my own, rather than fundamental weakness of the technique.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!