Core/Dependencies: Update G3D to v9.0 r4036

1 files changed, 189 insertions, 87 deletions

diff --git a/dep/g3dlite/source/Welder.cpp b/dep/g3dlite/source/Welder.cpp
index 2db47722e64..55a888590c3 100644
--- a/dep/g3dlite/source/Welder.cpp
+++ b/dep/g3dlite/source/Welder.cpp
@@ -1,10 +1,10 @@
 /**
- @file Welder.cpp
+ \file Welder.cpp
 
- @author Morgan McGuire, Kyle Whitson, Corey Taylor
+ \author Morgan McGuire, Kyle Whitson, Corey Taylor
 
- @created 2008-07-30
- @edited  2009-11-29
+ \created 2008-07-30
+ \edited  2011-07-04
  */
 
 #include "G3D/platform.h"
@@ -17,9 +17,14 @@
 #include "G3D/AreaMemoryManager.h"
 #include "G3D/Any.h"
 #include "G3D/stringutils.h"
+#include "G3D/BinaryInput.h"
+#include "G3D/BinaryOutput.h"
 
 namespace G3D { namespace _internal{
 
+// Uncomment to print information that can help with performance
+// profiling.
+//#define VERBOSE
 
 /** Used by WeldHelper2::smoothNormals. */
 class VN {
@@ -98,11 +103,11 @@ private:
      */
     int getIndex(const Vector3& v, const Vector3& n, const Vector2& t) {
         PointHashGrid<VNTi>::SphereIterator it = 
-                weldGrid.beginSphereIntersection(Sphere(v, vertexWeldRadius));
+                weldGrid.begin(Sphere(v, vertexWeldRadius));
 
         if (n.isZero()) {
             // Don't bother trying to match the surface normal, since this vertex has no surface normal.
-            while (it.hasMore()) {
+            while (it.isValid()) {
                 if ((t - it->texCoord).squaredLength() <= texCoordWeldRadius2) {
                     // This is the vertex
                     return it->index;
@@ -110,7 +115,7 @@ private:
                 ++it;
             }
         } else {
-            while (it.hasMore()) {
+            while (it.isValid()) {
                 if (((n - it->normal).squaredLength() <= normalWeldRadius2) &&
                     ((t - it->texCoord).squaredLength() <= texCoordWeldRadius2)) {
                     // This is the vertex
@@ -142,12 +147,16 @@ private:
 
      Called from process()
      */
-    void updateTriLists(
-        Array<Array<int>*>&         indexArrayArray, 
-        const Array<Vector3>&       vertexArray,
-        const Array<Vector3>&       normalArray,
-        const Array<Vector2>&       texCoordArray) {
-        
+    void updateTriLists
+    (Array<Array<int>*>&         indexArrayArray, 
+     const Array<Vector3>&       vertexArray,
+     const Array<Vector3>&       normalArray,
+     const Array<Vector2>&       texCoordArray) {
+     
+#       ifdef VERBOSE
+            debugPrintf("WeldHelper::updateTriLists\n");
+#       endif
+          
         // Compute a hash grid so that we can find neighbors quickly.
         // It begins empty and is extended as the tri lists are iterated
         // through.
@@ -183,13 +192,17 @@ private:
     /** Expands the indexed triangle lists into a triangle list.
 
         Called from process() */
-    void unroll(
-        const Array<Array<int>*>&   indexArrayArray, 
-        const Array<Vector3>&       vertexArray, 
-        const Array<Vector2>&       texCoordArray, 
-        Array<Vector3>&             unrolledVertexArray, 
-        Array<Vector2>&             unrolledTexCoordArray) {
-
+    void unroll
+    (const Array<Array<int>*>&   indexArrayArray, 
+     const Array<Vector3>&       vertexArray, 
+     const Array<Vector2>&       texCoordArray, 
+     Array<Vector3>&             unrolledVertexArray, 
+     Array<Vector2>&             unrolledTexCoordArray) {
+
+#       ifdef VERBOSE
+            debugPrintf("WeldHelper::unroll\n");
+#       endif
+       
         int numTriLists = indexArrayArray.size();
         for (int t = 0; t < numTriLists; ++t) {
             if (indexArrayArray[t] != NULL) {
@@ -206,9 +219,12 @@ private:
     /** For every three vertices, compute the face normal and store it three times.
         Sliver triangles have a zero surface normal, which we will later take to
         match *any* surface normal. */
-    void computeFaceNormals(
-        const Array<Vector3>&  vertexArray, 
-        Array<Vector3>&        faceNormalArray) {
+    void computeFaceNormals
+    (const Array<Vector3>&  vertexArray, 
+     Array<Vector3>&        faceNormalArray) {
+#       ifdef VERBOSE
+            debugPrintf("WeldHelper::computeFaceNormals\n");
+#       endif
 
         debugAssertM(vertexArray.size() % 3 == 0, "Input is not a triangle soup");
         debugAssertM(faceNormalArray.size() == 0, "Output must start empty.");
@@ -231,17 +247,19 @@ private:
      Computes @a smoothNormalArray, whose elements are those of normalArray averaged
      with neighbors within the angular cutoff.
      */
-    void smoothNormals(
-        const Array<Vector3>& vertexArray, 
-        const Array<Vector3>& normalArray, 
-        Array<Vector3>&       smoothNormalArray) {
-        
+    void smoothNormals
+    (const Array<Point3>& vertexArray, 
+     const Array<Vector3>& normalArray, 
+     Array<Vector3>&       smoothNormalArray) {
         if (normalSmoothingAngle <= 0) {
             smoothNormalArray = normalArray;
             return;
         }
 
-        
+#       ifdef VERBOSE
+            debugPrintf("WeldHelper::smoothNormals\n");
+#       endif
+
         // Create an area memory manager for fast deallocation
         MemoryManager::Ref mm = AreaMemoryManager::create(iRound(sizeof(VN) * normalArray.size() * 1.5));
 
@@ -250,53 +268,110 @@ private:
         debugAssert(vertexArray.size() == normalArray.size());
         smoothNormalArray.resize(normalArray.size());
 
-        // Compute a hash grid so that we can find neighbors quickly.
-        PointHashGrid<VN> grid(vertexWeldRadius, mm);
-        for (int v = 0; v < normalArray.size(); ++v) {
-            grid.insert(VN(vertexArray[v], normalArray[v]));
-        }
+        if (vertexWeldRadius == 0) {
+            // Look for vertices with the exactly identical normal only
+#           ifdef VERBOSE
+                debugPrintf("Taking fast path\n");
+#           endif
+
+            // Maximum expected faces that meet at a vertex
+            static const int k = 8;
+
+            // Maps vertices to the indices of normals at that vertex
+            Table<Point3, SmallArray<Vector3, k> > normalTable;
+            for (int v = 0; v < vertexArray.size(); ++v) {
+                bool ignore = false;
+                SmallArray<Vector3, k>& list = normalTable.getCreate(vertexArray[v], ignore);
+                list.append(normalArray[v]);
+            }
 
-        // TODO: this step could be done on multiple threads
-        for (int v = 0; v < normalArray.size(); ++v) {            
-            // Compute the sum of all nearby normals within the cutoff angle.
-            // Search within the vertexWeldRadius, since those are the vertices
-            // that will collapse to the same point.
-            PointHashGrid<VN>::SphereIterator it = 
-                grid.beginSphereIntersection(Sphere(vertexArray[v], vertexWeldRadius));
+            for (int v = 0; v < vertexArray.size(); ++v) {
+                Vector3 sum;
 
-            Vector3 sum;
+                const Vector3& original = normalArray[v];
 
-            const Vector3& original = normalArray[v];
-            while (it.hasMore()) {
-                const Vector3& N = it->normal;
-                const float cosAngle = N.dot(original);
+                const SmallArray<Vector3, k>& list = normalTable[vertexArray[v]];
 
-                if (cosAngle > cosThresholdAngle) {
-                    // This normal is close enough to consider.  Avoid underflow by scaling up
-                    sum += (N * 256.0f);
-                }
-                ++it;
-            }
+                for (int i = 0; i < list.size(); ++i) {
+                    const Vector3& N = list[i];
+                    const float cosAngle = N.dot(original);
 
-            const Vector3& average = sum.directionOrZero();
+                    if (cosAngle > cosThresholdAngle) {
+                        // This normal is close enough to consider.  Avoid underflow by scaling up
+                        sum += (N * 256.0f);
+                    }
+                }
 
-            const bool indeterminate = average.isZero();
-            // Never "smooth" a normal so far that it points backwards
-            const bool backFacing    = original.dot(average) < 0;
+                const Vector3& average = sum.directionOrZero();
+
+                const bool indeterminate = average.isZero();
+                // Never "smooth" a normal so far that it points backwards
+                const bool backFacing    = original.dot(average) < 0;
+                
+                if (indeterminate || backFacing) {
+                    // Revert to the face normal
+                    smoothNormalArray[v] = original;
+                } else {
+                    // Average available normals
+                    smoothNormalArray[v] = average;
+                }
+            }
 
-            if (indeterminate || backFacing) {
-                // Revert to the face normal
-                smoothNormalArray[v] = original;
-            } else {
-                // Average available normals
-                smoothNormalArray[v] = average;
+        } else {
+            // Non-zero vertex normal welding
+#           ifdef VERBOSE
+                debugPrintf("Taking slower weld path because vertexWeldRadius = %f\n",
+                            vertexWeldRadius);
+#           endif
+
+            // Compute a hash grid so that we can find neighbors quickly.
+            alwaysAssertM(vertexWeldRadius > 0, "Cannot smooth with zero vertex weld radius");
+            PointHashGrid<VN> grid(vertexWeldRadius, mm);
+            for (int v = 0; v < normalArray.size(); ++v) {
+                grid.insert(VN(vertexArray[v], normalArray[v]));
+            }
+            
+            // OPT: this step could be done on multiple threads
+            for (int v = 0; v < normalArray.size(); ++v) {            
+                // Compute the sum of all nearby normals within the cutoff angle.
+                // Search within the vertexWeldRadius, since those are the vertices
+                // that will collapse to the same point.
+                PointHashGrid<VN>::SphereIterator it = 
+                    grid.begin(Sphere(vertexArray[v], vertexWeldRadius));
+                
+                Vector3 sum;
+                
+                const Vector3& original = normalArray[v];
+                while (it.isValid()) {
+                    const Vector3& N = it->normal;
+                    const float cosAngle = N.dot(original);
+                    
+                    if (cosAngle > cosThresholdAngle) {
+                        // This normal is close enough to consider.  Avoid underflow by scaling up
+                        sum += (N * 256.0f);
+                    }
+                    ++it;
+                }
+                
+                const Vector3& average = sum.directionOrZero();
+                
+                const bool indeterminate = average.isZero();
+                // Never "smooth" a normal so far that it points backwards
+                const bool backFacing    = original.dot(average) < 0;
+                
+                if (indeterminate || backFacing) {
+                    // Revert to the face normal
+                    smoothNormalArray[v] = original;
+                } else {
+                    // Average available normals
+                    smoothNormalArray[v] = average;
+                }
             }
         }
     }
 
 public:
 
-
     /**
     Algorithm:
 
@@ -311,14 +386,17 @@ public:
     4. Generate output indexArrayArray.  While doing so, merge all vertices where 
        the distance between position, texCoord, and normal is within the thresholds.
      */
-    void process(
-        Array<Vector3>&     vertexArray,
-        Array<Vector2>&     texCoordArray, 
-        Array<Vector3>&     normalArray,
-        Array<Array<int>*>& indexArrayArray,
-        float               normAngle,
-        float               texRadius,
-        float               normRadius) {
+    void process
+    ( Array<Vector3>&     vertexArray,
+      Array<Vector2>&     texCoordArray, 
+      Array<Vector3>&     normalArray,
+      Array<Array<int>*>& indexArrayArray,
+      float               normAngle,
+      float               texRadius,
+      float               normRadius) {
+#       ifdef VERBOSE
+            debugPrintf("WeldHelper::process\n");
+#       endif
 
         normalSmoothingAngle = normAngle;
         normalWeldRadius2    = square(normRadius);
@@ -331,11 +409,17 @@ public:
                 "Input arrays are not parallel.");
         }
 
+        // Create an area memory manager for fast deallocation
         Array<Vector3> unrolledVertexArray;
         Array<Vector3> unrolledFaceNormalArray;
         Array<Vector3> unrolledSmoothNormalArray;
         Array<Vector2> unrolledTexCoordArray;
 
+        unrolledVertexArray.reserve(vertexArray.size());
+        unrolledFaceNormalArray.reserve(vertexArray.size());
+        unrolledSmoothNormalArray.reserve(vertexArray.size());
+        unrolledTexCoordArray.reserve(vertexArray.size());
+
         if (! hasTexCoords) {
             // Generate all zero texture coordinates
             texCoordArray.resize(vertexArray.size());
@@ -373,23 +457,40 @@ public:
     }
 
     WeldHelper(float vertRadius) :
-        weldGrid(vertRadius, AreaMemoryManager::create()),
+        weldGrid(max(vertRadius, 0.1f), AreaMemoryManager::create()),
         vertexWeldRadius(vertRadius) {
     }
 
 };
 } // Internal
 
-void Welder::weld(
-    Array<Vector3>&     vertexArray,
-    Array<Vector2>&     texCoordArray, 
-    Array<Vector3>&     normalArray,
-    Array<Array<int>*>& indexArrayArray,
-    const Welder::Settings& settings) {
 
-    _internal::WeldHelper(settings.vertexWeldRadius).process(
-        vertexArray, texCoordArray, normalArray, indexArrayArray, 
-        settings.normalSmoothingAngle, settings.textureWeldRadius, settings.normalWeldRadius);
+void Welder::Settings::serialize(class BinaryOutput& b) const {
+    b.writeFloat32(normalSmoothingAngle);
+    b.writeFloat32(vertexWeldRadius);
+    b.writeFloat32(textureWeldRadius);
+    b.writeFloat32(normalWeldRadius);
+}
+
+
+void Welder::Settings::deserialize(class BinaryInput& b) {
+    normalSmoothingAngle    = b.readFloat32();
+    vertexWeldRadius        = b.readFloat32();
+    textureWeldRadius       = b.readFloat32();
+    normalWeldRadius        = b.readFloat32();
+}
+
+
+void Welder::weld
+(Array<Vector3>&     vertexArray,
+ Array<Vector2>&     texCoordArray, 
+ Array<Vector3>&     normalArray,
+ Array<Array<int>*>& indexArrayArray,
+ const Welder::Settings& settings) {
+
+    _internal::WeldHelper(settings.vertexWeldRadius).process
+        (vertexArray, texCoordArray, normalArray, indexArrayArray, 
+         settings.normalSmoothingAngle, settings.textureWeldRadius, settings.normalWeldRadius);
         
 }
 
@@ -397,7 +498,7 @@ void Welder::weld(
 Welder::Settings::Settings(const Any& any) {
     *this = Settings();
     any.verifyName("Welder::Settings");
-    for (Any::AnyTable::Iterator it = any.table().begin(); it.hasMore(); ++it) {
+    for (Any::AnyTable::Iterator it = any.table().begin(); it.isValid(); ++it) {
         const std::string& key = toLower(it->key);
         if (key == "normalsmoothingangle") {
             normalSmoothingAngle = it->value;
@@ -413,12 +514,13 @@ Welder::Settings::Settings(const Any& any) {
     }
 }
 
-Welder::Settings::operator Any() const {
+
+Any Welder::Settings::toAny() const {
     Any a(Any::TABLE, "Welder::Settings");
-    a.set("normalSmoothingAngle", normalSmoothingAngle);
-    a.set("vertexWeldRadius", vertexWeldRadius);
-    a.set("textureWeldRadius", textureWeldRadius);
-    a.set("normalWeldRadius", normalWeldRadius);
+    a["normalSmoothingAngle"]   = normalSmoothingAngle;
+    a["vertexWeldRadius"]       = vertexWeldRadius;
+    a["textureWeldRadius"]      = textureWeldRadius;
+    a["normalWeldRadius"]       = normalWeldRadius;
     return a;
 }