Tessellating Tiles

Arranging in Distance Dependent Detail

One of the immediate problems to be solved when building a tiled landscape is the need to tessellate tiles of different scales. Assuming the tiles are repeats of the same regular mesh but with varying heights on the Y axis, and with each tile size being double the previous the following method can be used.

  • Arrange the tiles with respect to the distance from the viewer. In this example the number denotes the size of the tile, and the viewer is assumed to be on one of the most detailed “4” tiles.

image

  • Record the adjacencies of each tile to the next
  • Parse the adjacencies using the following rule

If the tiles are more than one size differential split the larger tile into its constituent four smaller tiles.

image

Results of pass 1 – reduces a “2” tile to its constituent “3” tiles.

image

Results of pass 2 – reduces the bottom right “1” tile to four constituent “2” tiles

image

Results of pass 3 – reduces the top right “2” tile to it four constituent “3” tiles

image

Results of pass 4 – reduces the top left corner.

After this iterative process the tile map now has no junctions where a tile meets another tile that is more than one size differential. This is important in the next step.

Preventing Ripping

  • Using the adjacency map record for each tile which edge abuts another tile which has a larger number.
  • When producing the mesh, store two numbers for the Y coordinate – its more accurate height, and the height as interpolated between its two neighbours, for each odd numbered vertex across the edge.

image

In the example above the numbered vertexes will have two values recorded for its Y (height) value – the actual value obtained from a heightmap or other source, and the value as a linear interpolation between its two neighbours, if it is an odd numbered vertex. So V1 interpolated height would be average of V0 and V2, V3 would be average of V2 and V4. This step is called “vertex welding”.

image

From the above diagram you can see that when rendering the black, more detailed mesh, you can choose to render the numbered vertexes either as their “natural” more accurate value, or the interpolated value – and that interpolated value will precisely match the “natural” value of the adjacent larger tile, as the interpolated point V1 will fall exactly on the line A-B and V3 on the line B-C. This will render a seamless join between the two tiles.

Tidying Up

Although no ripping will be evident the normals calculated for each vertex in a mesh are dependent on the values of their neighbours. At the edges of meshes you would not take into account the values of their neighbours in the adjacent mesh. In addition to prevent “jumping” or visible normal transition artefacts, the normals should be calculated with reference to an adjacent mesh at the same level of detail as the subject mesh.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s