Jump to content
  • Advertisement
Sign in to follow this  

Vertex Normals In A QuadTree Terrain

This topic is 1736 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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++) {

            return result;

Share this post

Link to post
Share on other sites

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. 



Share this post

Link to post
Share on other sites

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

Share this post

Link to post
Share on other sites

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. 



Share this post

Link to post
Share on other sites

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?

Share this post

Link to post
Share on other sites
Sign in to follow this  

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!