Fast Normals .. Or Not

Well, I spoke too soon about the fast normals. They almost work. The normals do not line up exactly at the corners of the cube so there are visible seams. I spent some time trying to come up with some extra rotation to compensate for this distortion but was not successful and have decided to revert to calculating the normals the old way, which is by calculating triangle normals and then smoothing.

I believe to fix the cube to sphere mapping you need to rotate the normals about their vertical axis as they approach the corners, but I have not come up with a good method yet, if anyone has any ideas I'd love to hear them.



(click the above image to see the normal map corner distortion)

Fast Normal Calculations for Planets

Up till now I've been using a brute force method of normal calculation for the patch normals. I would use the cross product to find the normal for each triangle and then smooth the triangle normals when calculation the per-vertex normals.

I was aware of the simplified normal calculations for flat heightfields but wasn't sure how to translate those to the sphere - until now. Aurelio Reis and I had been corresponding and I emailed him about how I didn't think his method for mapping normals to the sphere was correct (turns out I completely misunderstood his method) and I recommended translating the normal on the cube face to a normal on the sphere by getting the rotation matrix from the normal of the cube face to the vertex position on the unit sphere.

The fast method for deriving a rotation matrix given a start and an end vector can be found here: http://www.cs.brown.edu/~jfh/papers/Moller-EBA-1999/main.htm - Tomas Moller & John F. Hughes "Efficiently Building a Matrix to Rotate One Vector to Another and their sample code here: http://jgt.akpeters.com/papers/MollerHughes99/code.html

The funny thing is my implementation failed and I had given up, when Aurelio wrote me back with news of his success, and some helpful advice about calculating the heightfield normals. With that encouragement I attacked it again, fixed my bugs and got it working.

Thanks to Aurelio's suggestion, I'm using the Game Programming Gems 3 method for calculating heightfield normals. The tricky thing with this method of calculating normals is that it assumes the distance between the vertices is 1 unit. When the camera approaches the terrain and it splits the quadtree, the new patches are twice the resolution of the old patch, so the vertices are now 0.5 units apart. Thankfully the distance of the normal vector doesn't matter in the calculations so it simplifies things and you can see below that for level N of the quadtree to calculate a normal for a vertex at that level the equation is:

Normal = ( h3 - h1, 2.0 / (1 << level), h4 - h2 )

Where h1-h4 are the heights of the neighboring vertices, and level is the depth in the quadtree (starting at depth 0).

Here's what that equations looks like for levels 0, 1, and 2:

Level 0:
Nv = ( h3 - h1, 2, h4 - h2 )

Level 1:
Nv = ( h3 - h1, 1, h4 - h2 )

Level 2:
Nv = ( h3 - h1, 0.5 , h4 - h2 )

I normalise the normals before applying the rotation matrix that rotates them from cube space to sphere space.

Here's the basic code for calculating the normals (hMap is a RGBA image where the RGB values are the XYZ for the vertex position on the unit sphere and the A value is the height in the heightmap)

    // Get the Y factor for the normal calculations
    Real f = 2.0  / ((Real)(1 << getDepth()));
    Matrix3 m;
    
    float* hMap = (float*)mHeightMap->getData();

    // skip the outer edge and first vertex
    hMap += (patchSize+2 + 1) << 2;

    // loop through the vertices and save the normals to the normal map
    float* nMap = (float*)mNormalMap->getData(); 
    for(int y = 0; y < patchSize; ++y) {
        for(int x = 0; x < patchSize; ++x) {
            h1 = *(hMap + 7);
            h2 = *(hMap + ((patchSize + 2) * 4) + 3);
            h3 = *(hMap - 4 + 3);
            h4 = *(hMap - ((patchSize + 2) * 4) + 3);
                    
            spherePos.x = hMap[0];
            spherePos.y = hMap[1];
            spherePos.z = hMap[2];
        
            normal = Vector3( (h3 - h1), f, (h4 - h2)).normalisedCopy();
            
            buildRotationMatrix(Vector3::UNIT_Y, spherePos, m);
            normal = m * normal;
            
            *nMap++ = normal.x;
            *nMap++ = normal.y;
            *nMap++ = normal.z;
            
            hMap += 4;           
        }

        // skip edge vertices
        hMap += 8;
    }

Of course I plan to clean up the code when/if I make the loops OpenMP compatible.

Resource Managers

I've been looking for a fast, safe, memory efficient implementation of a basic resource manager that does a few things:

1. Uses handles instead of pointers


2. Supports reference counting so resources can be shared and freed properly


3. Doesn't fragment the heap, but instead, allocates memory in contiguous chunks so all the data in a resource "pool" is local


4. Is templated and simple


5. Releases resource handles by pushing them onto the back of the list and getting available handles off the front of the list so that the most recently used handles stay in the handles list longest for best cache results.

Here are the ones I considered in my research.

A Simple Fast Resource Manager using C++ and STL (Ashic Mahtab, Zinat Wali)

Pros:
Uses STL and templates, very simple easy to understand, uses reference counting and handles.

Cons:
Uses strings for unique identifiers, pointers to resources are stored in std::vector, not the resources themselves, uses a stack for handles (push and pops off the front).

Gem: A Generic Handle-Based Resource Manager (Scott Bilas)

Pros:
Uses STL and templates, simple to understand, uses handles, stores resources not resource pointers.

Cons:
Uses strings for unique identifiers, does not have reference counting for handles (handle sharing), does not use a queue for handles.

Ogre 3D Resource Manager

Pros:
Is built to work with Ogre resources, supports shared resources and handles (reference counting), supports loading states and threaded loading of resources.

Cons:
Uses strings for unique identifiers, does not use a queue for handles, stores pointers to resources.

All these resource managers are great for managing resources loaded from files, which is why they all use a string as an identifier. None of them were designed with storing on-the-fly generated terrain data in mind.

I ended up starting with Ashic Mahtab and Zinat Wali's manager code and modified it to use a std::deque for the handles, to use an unsigned long long as the unique identifier and to store the resources themselves and not resource pointers.

So after I coded that up I ran into some major problems:

1. The Ogre::VertexData class has its constructor set private so I couldn't subclass it to easily make it a resource. The solution was to store a shared pointer to it instead, which means that I lose my resource memory locality.


2. My vertices and blending vertices can be of variable size and my implementation was designed to store objects of known sizes (known at compile time). I could specialize the vertices manager class to handle this shortcoming, but I opted to just use a shared pointer instead.

Looks like I ended up basically storing pointers to resources instead of the resources so far!

The profile results show that I have brought the deletion time down from 251 microseconds average to about 5 microseconds average. Over-all the application update time and the _updateRenderQueue() function time seems to have decreased by at least half.

So I'm fairly happy with the results, the problem is that I'm still seeing spikes in the Ogre::Root::renderOneFrame(). The average time for that function is 4,000 microseconds, but the maximum time is around 40,000 microseconds.

In the future I will look into what is going on inside Ogre that is taking this time, but for now I'm going to continue on with my refactoring so this may be the last resource performance related post for a bit.