After spending some days in Blender and Unity3D trying to do a level for a puzzle game I am working on, I realized (as I knew in theory) how painful it is to make vegetation by placing, rotating and scaling items in the scene one by one. Specifically I wanted to place dense vegetation along the borders of my level to create the illusion of a vast and dark forest surrounding the level, explaining in a way why the player is stuck in that place. So I created a tree and some grass in blender, nothing fancy, and started placing them on my scene. After a couple of hours I was done and the result looked pretty nice, but then I realized that there were things I did not like and had to tweak them. I wanted trees to be closer and more grass. but I couldn’t go through that process again. Creating the vegetation manually in the first place was way too much effort. So I looked back to a DirectX project I did during my master degree where I implemented a random scattering algorithm inspired from an article of Mick West in Gamasutra (originally in Game Developer magazine), “Random Scattering: Creating Realistic Landscapes”  and I decided to do a tool for Unity3D that will help me simplify the whole process of placing vegetation in the scene. What I want to achieve with this tool is the following:
- Define an area of vegetation on the selected ground (mesh),
- Select the models that will be used for the vegetation, I’ll call them ‘Vegetation Entities’ (trees, grass, bush, whatever)
- Configure the properties of the vegetation on this area (how dense, relationship between vegetation entities; how close to each other, etc) and…
- Build the vegetation on the selected area.
So what is random scattering? Simply put, random scattering is a way of procedurally placing items in the scene, in a way that looks natural. There are many techniques for doing so and Mick West’s article is a great resource for anyone interested. The simplest way to procedurally scatter vegetation in a scene is to define an exclusion area around each vegetation entity inside which no other entity can be placed. For my tool I will use the ‘Different sized trees’ (Fig. 1, lower right) approach from Mick West’s article and take it a step forward, similar to my DirectX 10 project, by using relationships between vegetation entities and vegetation statistics. The vegetation statistics is a way to classify vegetation entities in types and build vegetation based on user defined percentages for each type. This way we can define tree models as type ‘HIGH’, various bushes as ‘MID’ and grass as ‘LOW’ and build vegetation in an area with the following percentages: 20% HIGH, 50% MID and 30% LOW. The resulting vegetation will be composed mostly of bushes and grass and only a few trees will be here and there. A relationship between vegetation entities is a way to place two entities closer to each other if they are related and further away if not. For each entity two radiuses are used, a min and max. When the entities are placed in the scene a check is performed to define which of the two radiuses will be used. For example let’s assume we have a tree entity (min=0.2, max=2) and a grass entity (min=0.1, max=0.5), a tree entity is placed in the scene and we want to place grass. If the two entities are related (tree-grass or grass-tree relationship) then when placing the grass we will use the min radius to place the grass close to the tree (the max of the two min radius of the entities will be used). If the two entities were not related, the max radius (max=2) will be used instead.
Desired features of the first version
- Select the ground GameObject from the scene hierarchy. The game object should contain geometry.
- Define multiple areas on the ground mesh. Using the mouse in the scene editor add points to define a vegetation area.
- Edit an area by adding, removing or moving the points that define it, through the scene window.
- For each area, define its properties, such as; vegetation entities and their characteristics, density, percentage of each entity type (High, Mid, Low vegetation), etc.
Some implementation details
The EditorWindow script
Through this script we should be able to select the ground mesh, add/edit/remove vegetation areas, clear vegetation of selected areas, define vegetation entities, their properties and their relationships with each other.
Defining an area using the mouse through Unity3D’s scene window
The idea is to define a vegetation area on a selected mesh (ground gameObject) by clicking with the mouse on the scene window. This is done simply by casting a ray from the mouse position to the game world on a left mouse button click. If that point is on the desired ground mesh, the point is added on the mesh. Currently I use Unity3D’s Handles.Button for each point of the area to easily select the point I want to edit by clicking it with the mouse.
Algorithm to check if a point is inside a polygon (2D)
A vegetation area is defined by points in 3D space. I’m doing that for the sake of editing since this way I can use the y position to make a point stick on the ground (with raycasting) and well, make it look nicer. However, the algorithm to check if a point is inside that polygon only needs points in 2D. Thus, I’m only using the x and z position of every point to do the check, reducing the problem to 2 dimensions. The algorithm I’m using to do the check is quite simple and described in more detail here. The process is the following: First generate a random point (let’s call it point R). Then get a point outside the vegetation area (call it O) and for each line segment defined by two consecutive points in the vegetation area array (A1-A2, A2-A3, A3-A4 and so on), check if it intersects with the line segment defined by points O and R. If those two segments intersect and the intersection point is on both of the segments, then increase the intersection count. After doing this check for every line segment of the polygon defining the area, check if the intersection count is odd or even. If it is odd, then the point is inside the area, if not, then it’s outside. The input of the algorithm is a vegetation area defined by an array of 3D points and a point in 3D space. The output is a boolean, being true when the point is inside the area and false if not.
The scattering algorithm
This part is still a work in progress and some stuff might change when I actually start coding, but in general lines it follows the process described below, which is pretty much the same process I followed in my DirectX project:
- Pick a vegetation entity in random from the list of entities that will compose the vegetation of the current area.
- Check if the picked vegetation entity satisfies the vegetation statistics of the area. If the area already has too many entities of the picked entity type then discard it and pick another type of vegetation.
- Generate a random position inside the area.
- Check if the picked position for this entity satisfies the conditions defined by the properties of this and the already placed nearby entities. Specifically, iterating through all the placed vegetation entities, we first check if the picked entity (A) is in relationship with the currently checked entity (B). If the two entities are related (min radius) then we check if entity A is inside the area defined by the biggest of the min radius of the entities (radius = max(A.radius.min, B.radius.min)). If A and B are not related the same check is done while using the maximum radius instead (radius = max(A.radius.max, B.radius.max)).
- If the picked position is not inside the area (min or max defined by relationship) of any nearby entity, then we can place the entity in the scene. Before we place the entity, we randomly pick a scale and a rotation satisfying the scale and rotation range defined in the vegetation entity properties.
- This process goes on until the desired vegetation statistics are met or if the algorithm decides that it cannot place any new entities in the area (too many failed tries).
Progress (Update #1)
I started the development of this tool around 1.5 months ago, but unfortunately for the past 2-3 weeks I wasn’t able to do much and thus I’m far from releasing something solid. Considering that I’ve figured out most of the implementation details, apart from some minor details such as storing the state of the editor window in Unity3D, I should be able to have a first version in the next month or two. Anyway, so far I’ve got the algorithm that checks if a point is in a polygon, the biggest part of the scattering algorithm and the necessary classes to implement the rest of the functionality. What I still need to do is the editor window, add vegetation statistics and relationships to the scattering algorithm and find a way to reload the state of my unity editor window after a reload (pretty much the whole tool!). Below you can see some screenshots of the prototype I’ve got working which shows the intended use of the tool.