• Create Account

# Vertex Normals In A QuadTree Terrain

4 replies to this topic

### #1Imprecision  Members   -  Reputation: 189

Like
2Likes
Like

Posted 18 October 2013 - 07:32 AM

I finally managed it to get my terrain stitching working on a globe with six quadtrees.

I used a index system similiar to this one http://img406.imageshack.us/img406/2153/screen4ya3.png.

Everything looks fine so far (no cracks, no shifted heightdata), except for the lighting. The vertex normals on the edges are sh*t.

See the image below:

Is there any way how to calculate/interpolate the edges, so they have the same normal?

One of the problems that I cant "fix in my head" are the differences between LODs

I cant just copy the vertices of my neighbor because maybe its larger or smaller than me:

Node (1) needs the vertex data (red and green slice) from node (2), (3) and (4)  to calculate correct normals. This means data from these nodes must be extracted (slice) and some of it must be skipped (because node (1) has a lower resolution) by the difference of the specific neighbor depth. This is complicated, but not that much.

The other way around is giving me headache. Node (2) needs the border vertex slice from (1) (the blue one). The problem is, that it just needs a specific "range" of the slice, so it needs to determine what exact position it (2) has compared to the border of the node (1) and calculate the index of the first vertex to extract. WTF?!

Next problem with this is, the 3D aspect. I have different behavior when my neighbors are on other sides of the node:

For Node (4) I need three slices to get correct normals for the north and west edge. One from (5) one from (6) and the last vertex for the corner from Node (1). When I have the same situation with the neighbors beeing on anthoder side, i just have 2 slices, because I don't have a corner at all.

-

Even if i would have a super algorithm that calculates how much shifted a smaller node to a bigger node is handling different sides of the cube... there must be another way. I found 1000 topics of neighbor finding and crack fixing problems for quadtrees. But not a single one who has problems with vertex normals.

This makes me suspicious that I make something fundamentally wrong.

Btw. here is the code how I calc the normals:

 private static Vector3d[] create(Vector3d[] vertices, int[] indices) {
// Prefilling result
int vertLength = vertices.Length;
Vector3d[] result = new Vector3d[vertLength];
for (int i = 0; i < vertLength; i++) {
result[i] = Vector3d.Zero;
}

// Calculating normals
int length = (int)(indices.Length / 3);
for (int i = 0; i < length; i++) {
Vector3d v1 = vertices[indices[i * 3]];
Vector3d v2 = vertices[indices[i * 3 + 1]];
Vector3d v3 = vertices[indices[i * 3 + 2]];

Vector3d ab = v1 - v2;
Vector3d ac = v1 - v3;

Vector3d vCross;
Vector3d.Cross(ref ab, ref ac, out vCross);

result[indices[i * 3]] += vCross;
result[indices[i * 3 + 1]] += vCross;
result[indices[i * 3 + 2]] += vCross;
}

// Normalize
for (int i = 0; i < vertLength; i++) {
result[i].Normalize();
}

return result;
}

### #2kauna  Crossbones+   -  Reputation: 1542

Like
0Likes
Like

Posted 18 October 2013 - 08:43 AM

I don't know how you store your data, but if you have a separate height map as a source for your vertex elevation, you may use it for calculating the terrain normal.

That is, you should have a function which is capable of calculating the terrain normal at a terrain position x,y regardless of the triangulation of the terrain. This way you'll have the same vertex normals at the patch edges.

Cheers!

### #3Imprecision  Members   -  Reputation: 189

Like
0Likes
Like

Posted 18 October 2013 - 09:31 AM

I think you assume, that I have a global heightmap.

I forgot to say that I this is procedural terrain. The heightdata is generated per Node on the GPU, so no global heightmap data.

Someone might say "Then make the heightmap one pixel larger in every direction" - That dosen"t work either. When the node is on the edge of the cube, I would have to make a 3D heightmap, what would require to know the different side while creating the heightmap and increases the memory consumption by at least 3 times.

Edited by Imprecision, 18 October 2013 - 09:37 AM.

### #4kauna  Crossbones+   -  Reputation: 1542

Like
1Likes
Like

Posted 18 October 2013 - 11:10 AM

You say that you generate height data on GPU? The source code you present is working on CPU?

For a procedural terrain you do have a function which determines the vertex height at certain position I assume?

So you should be able to generate the vertex normals procedurally also.

Cheers!

### #5wintertime  Members   -  Reputation: 1333

Like
0Likes
Like

Posted 19 October 2013 - 05:54 AM

Just an idea, but maybe you could simplify the problem by not having 6 heightmaps to approximate the sphere with a cube. With only a single heightmap you don't have to connect it to other heightmaps, if you wrap it around the sphere directly by transforming the coordinates in a different way.

You could say 1 corner is the northpole, the opposite corner the south pole, the remaining 2 corners wrap to the point where the 0 meridian crosses the equator, which gets something resembling 2 cones connected at their bases, then extrude the coordinates a bit so you get a sphere?

PARTNERS