Naturalistic World Partiniong using Pseudo Voroni

When considering vegetation coverage, woodland coverage, lakes, river courses and all other visual features you need to partition your landscape into regions. The regions need to look naturalisic (i.e. not hexagons, grids or other repeating patterns) but need to be even sized.

A nice trick is to use a random scatter of points and then triangulate them

Graph_GenerateFactory

Now carry out a “pseudo vornoi” algorithm to generate a pleasing set of regular partitions;

PseudoVoroni

Each of these units can be used as a landscape parition.

What is a psuedo-voroni algoirthm ? In this case I dont want a mathematically accurate voroni graph so I just take the centroid of each triangle and join them together. In the above diagram you should see the Voroni cell walls in white but the underlying original triangulation in dark blue.

You can then attach a set of properties to each cell based on their height and the affect of the adjacent voroni cell attributes.

For river courses the Voroni cell borders form a network of routes which an A* routing algorithm can use to describe all the possible routes of a river. Each Voroni cell vertex has only three possible adjacent points, and this makes route finding much faster and helps provide a nice river pattern when used as a set of control points to a spline.

Credit to http://www-cs-students.stanford.edu/~amitp/game-programming/polygon-map-generation/ who inspired this approach

 

Advertisements

Concave Hull

Working on some arcane aspect of my landscape pipeline I find I need to identify whether points in my mesh are part of the “outside edge” of the mesh. I am familiar with the calculation of a Convex Hull – but this creates the shorest line that connects encompasses the mesh, and is not limited to triangles that already exist in the mesh. This means that the Convex Hull probably does not resemble the shape of the original mesh.

The solution to the problem jumped into my head rather than searching for it on the web – it was a really simple solution when I considered what made an “exterior” point different from an “interior” point. We can visually see an interior point because it is completely surrounded by triangles – but what does that “surrounded” mean mathematically ?

It means that the sum of all the angles between the subject point and all the other points of the triangles it forms part of are exactly 360 degrees. Anything less than that; then the point is an “exterior” point.

In order to determine a convex hull for a point cloud I follow the following logic

  1. Triangulate the mesh.
  2. For each point, select all the triangles it it part of
  3. For each of those triangles, calculate the angle formed between the subject point and the other two points.
  4. Iterate all the triangles that use this point, and sum the angles found.
  5. If they are less than 360 then this point is not wholly surrounded by triangles and is therefore exterior.

This method works for meshes that do not have interior holes in them, as the points on the hole boundary would be treated as part of the Concave Hull.