Graphics, Imaging, and Games Lab

We present a method to generate models for trees in which we first create a weighted graph, organized based on the Yao graph, then place endpoints and root point and plan least-cost paths from endpoints to the root point. The collection of resulting paths forms a branching structure. We create a hierarchical tree structure by placing subgraphs around each endpoint and beginning again through some number of iterations. Powerful control over the global shape of the resulting tree is exerted by the shape of the initial graph, composed of simple geometric primitives arranged in part manually and in part procedurally. Users can create desired variations by adjusting the initial graph shape; more subtle variations can be accomplished by modifying parameters of the graph and subgraph creation processes and by changing the endpoint distribution mechanisms. The method is capable of matching a desired target structure with a little manual effort, and can easily generate a large group of slightly different models under the same parameter settings. Environmental effects can also be incorporated into the models by automatic parameter adjustment. The final trees are both intricate and convincingly realistic in appearance.