Blending Vertex Normals In A Quad Tree

Ogre 3D Vertex Normal Blending from petrocket on Vimeo.

I've finally had some time to work on blending the mesh normals and can post a video - my FIRST video of the app so go easy - and talk about what works about it and where the idea came from.

As it turns out there is/was another excellent planetary LOD program based on geo clipmaps and I read that Lutz Justen (the author, now an engineer at Red 5 Studios!) had blended his normal maps and done some other fancy things like cloud map shadows. I contacted Lutz and he responded with this:

"Vertex normals: I don't think there is *any* way to make vertex normals not pop - UNLESS you change the way geo morphing works. You probably interpolate a vertex to the position between the two higher-level verts, i.e.
x
/ | \
/ \/ \
x---o----x

The upper vertex is interpolated to the average of the lower 2 vertices. In that case, you'll always have lighting pops. If you instead interpolate the upper vertex to either the left or the right vertex, you'd get rid of the pops because the limit of the finer triangles as you interpolate to the coarser triangles actually match the coarser triangles. I hope that makes sense. If you interpolate to the average of the lower vertices, the limit doesn't match the coarser representation. It's the same geometry, but a different triangulation.

If you store per-patch normals as Ysaneya does, there's another way. You can store your normal maps in object space (instead of tangent space) because they are unique anyway. Then you can lerp between a fine-level normal map and the corresponding coarse-level normal map. That'd make your lighting completely smooth. That's what I did in my demo, although the resolution of the normal map was very low - it was the same resolution as the vertices! But nevertheless, the lighting was completely continuous."

And that's what I tried to do, only right now my normal map calculations for the "coarse" map are not entirely correct because there is still a pop when the mesh level changes - although a MUCH smaller pop than before, it is still there as you can see in the video. Maybe sometime I will post a video of the transitions without normal blending so you can see the improvement.

Here's how I implemented the normal map blending in Ogre (cooking directions style!)
Ingredients:
6 quad trees
4 quad tree meshes per node
2 sets of normals per mesh (for blending)
1 blend start distance for each level/depth in the quad tree
1 blend end distance for each level/depth in the quad tree
1 GLSL vertex shader to take these values and do something with them

1. prepare your meshes by creating the 3d vertex positions from your 3d noise function
2. calculate your end normals based on those positions and save them - these are the normals we will blend to.
3. get the outer edge vertices for the "coarser" mesh
4. calculate the normals for each vertex that exists in the "coarser" mesh
5. calculate all the interpolated normals for each vertex that exists in the "finer" mesh but not in the "coarser" mesh.
6. in the vertex shader blend between the "finer" and "coarser" normals based on the camera's distance to the vertex. Each level of the quad tree will have a different distance based on the split distance for that level - the split distance is the distance from the camera to a node at which it must split into 4 sub nodes, one for each quadrant.

Right now my calculations are not completely correct for step 5 because there is still a visible transition or "pop" when the finer mesh is displayed. I don't know where my calculations are wrong, but if I figure it out I will post the solution.

Multithreaded Graphics Programming Caveats

You can't make graphics calls in any thread but the main thread without sacrificing platform portability and graphics library portability. In my case I want to be able to run this application on Windows in DirectX 9+ and in OSX and Linux in OpenGL. OpenGL allows you to make graphics calls in a secondary thread if you copy and initialize the graphics context in that other thread, but even if I did that I would have to write separate procedures to initialize the secondary threads for OpenGL and DirectX and none of it would be pretty and from what I've read the gains wouldn't be that significant.

So my compromise is to use POSIX threads and OpenMP for the non-graphic call related stuff - like the heavy lifting math in the terrain generation and normal maps etc. All the graphics related calls will live in the main thread (creating vertex/index buffers and populating them with data, and releasing vertex/index buffers).

I've noticed that creating an Ogre VBO and populating it with data can take up to 700 microseconds (but averages around 165 microseconds), while deleting an Ogre VBO takes 10 times as long (max 8 milliseconds, avg 1 millisecond). By only creating or deleting one VBO per frame, and after moving all the vertex calculations to separate threads, I'm able to keep things pretty smooth. Did I mention I'm using my MacBook Pro? It has an Intel Core II Duo 2.4ghz with 4GB of RAM and the NVidia GeForce 8600M GT with 256MB VRAM.

At some point I will need to identify why freeing the buffer is taking so much more time, and try to optimize that.

Here's the biggest caveat with threads that I've run into: I cannot reliably allocate memory inside a child thread. Ogre uses nedmalloc now and it is a fantastic allocator/deallocator. Unfortunately when I try to allocate memory from within a thread other than the main thread I get an EXC_BAD_ACCESS signal from within nedalloc::GetThreadCache() The annoying thing is that it doesn't happen right away - it's only after the program generates enough meshes. So for now I'm steering clear of any allocation/deallocation inside threads and keeping that in the main thread. It doesn't look like keeping it in the main thread is causing any performance hit anyways.

POSIX Threads And OpenMP Can Co-Exist

Not exactly a major revelation, but as an experiment I changed the mesh build process to a threaded model using POSIX threads (pthreads). The short version is that when the quad tree changes, first a manager thread is spawned, which spawns several worker threads. The worker threads build the actual mesh and then quit when there are no more meshes to build. The manager thread just waits for all the worker threads to finish then updates the render queue with the new list of meshes and quits.

One important thing to mention, besides all the mutexes to protect the lists, is that the quad tree is not allowed to be updated while the new meshes are being built. Changing the quad tree while still building would invalidate our list of meshes to build and could get us into a situation where the render queue is never updated because the list of meshes to build is never completed!

After the meshes are all built and the new visible list of meshes is given to the render queue then the quad tree is allowed to update, and when the tree changes the whole process begins again.

Also note that while the worker threads are building the new mesh, the render queue continues to display the meshes from the previous version of the quad tree.

The second part of the experiment was to use OpenMP to utilize the extra core of my processor in building the meshes using work sharing. Fortunately, XCode supports GCC 4.2 which supports OpenMP 2.5, and that will suffice for now. I only added parallel processing to the for loop that generates the vertices so I don't expect to see much improvement, however when I start generating normal maps I think the improvement will be noticable. Anyways, it compiles and runs.

Next I have to fix some logic bugs, re-implement the code that deletes old meshes in the cache list, and either re-implement the heightfield and normal generating, or take a crack at a second quad tree that is updated based on where the camera will be so those meshes can be pre-built and put in the cache.

A small aside - making the build process threaded made my simple profiler not completely reliable anymore because the thread may start sampling during one frame and then before it is done sampling, the profiler might attempt to process the samples because that part of the profiler runs in the main thread! Fortunately that is unlikely to occur and if it does it shouldn't skew the results much, though I suppose I could add a semaphore to resolve the issue.