diff options
Diffstat (limited to 'externals/g3dlite/G3D.lib/source/MeshAlgWeld2.cpp')
| -rw-r--r-- | externals/g3dlite/G3D.lib/source/MeshAlgWeld2.cpp | 377 |
1 files changed, 377 insertions, 0 deletions
diff --git a/externals/g3dlite/G3D.lib/source/MeshAlgWeld2.cpp b/externals/g3dlite/G3D.lib/source/MeshAlgWeld2.cpp new file mode 100644 index 00000000000..13f731353a6 --- /dev/null +++ b/externals/g3dlite/G3D.lib/source/MeshAlgWeld2.cpp @@ -0,0 +1,377 @@ +/** + @file MeshAlgWeld2.cpp + + @author Morgan McGuire, Kyle Whitson, Corey Taylor + + @created 2008-07-30 + @edited 2008-11-10 + */ + +#include "G3D/platform.h" +#include "G3D/Vector2.h" +#include "G3D/Vector3.h" +#include "G3D/Sphere.h" +#include "G3D/PointHashGrid.h" +#include "G3D/MeshAlg.h" + +namespace G3D { namespace _internal{ + +/** Used by WeldHelper2::smoothNormals. */ +class VN { +public: + Vector3 vertex; + Vector3 normal; + + VN() {} + VN(const Vector3& v, const Vector3& n) : vertex(v), normal(n) {} +}; + +/** Used by WeldHelper::getIndex to maintain a list of vertices by location. */ +class VNTi { +public: + Vector3 vertex; + Vector3 normal; + Vector2 texCoord; + int index; + + VNTi() : index(0) {} + + VNTi(const Vector3& v, const Vector3& n, const Vector2& t, int i) : + vertex(v), normal(n), texCoord(t), index(i) {} +}; + + +}} // G3D + +template <> struct HashTrait <G3D::_internal::VN> { + static size_t hashCode(const G3D::_internal::VN& k) { return static_cast<size_t>(k.vertex.hashCode()); } +}; +template <> struct HashTrait <G3D::_internal::VNTi> { + static size_t hashCode(const G3D::_internal::VNTi& k) { return static_cast<size_t>(k.vertex.hashCode()); } +}; + + +template<> struct EqualsTrait <G3D::_internal::VN> { + static bool equals(const G3D::_internal::VN& a, const G3D::_internal::VN& b) { return a.vertex == b.vertex; } +}; +template<> struct EqualsTrait <G3D::_internal::VNTi> { + static bool equals(const G3D::_internal::VNTi& a, const G3D::_internal::VNTi& b) { return a.vertex == b.vertex; } +}; + +template<> struct PositionTrait<G3D::_internal::VN> { + static void getPosition(const G3D::_internal::VN& v, G3D::Vector3& p) { p = v.vertex; } +}; +template<> struct PositionTrait<G3D::_internal::VNTi> { + static void getPosition(const G3D::_internal::VNTi& v, G3D::Vector3& p) { p = v.vertex; } +}; + +namespace G3D { namespace _internal { + +class WeldHelper { +private: + /** Used by getIndex and updateTriLists */ + PointHashGrid<VNTi> weldGrid; + + Array<Vector3>* outputVertexArray; + Array<Vector3>* outputNormalArray; + Array<Vector2>* outputTexCoordArray; + + float vertexWeldRadius; + /** Squared radius allowed for welding similar normals. */ + float normalWeldRadius2; + float texCoordWeldRadius2; + + float normalSmoothingAngle; + + /** + Returns the index of the vertex in + outputVertexArray/outputNormalArray/outputTexCoordArray + that is within the global tolerances of v,n,t. If there + is no such vertex, adds it to the arrays and returns that index. + + Called from updateTriLists(). + */ + int getIndex(const Vector3& v, const Vector3& n, const Vector2& t) { + PointHashGrid<VNTi>::SphereIterator it = + weldGrid.beginSphereIntersection(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()) { + if ((t - it->texCoord).squaredLength() <= texCoordWeldRadius2) { + // This is the vertex + return it->index; + } + ++it; + } + } else { + while (it.hasMore()) { + if (((n - it->normal).squaredLength() <= normalWeldRadius2) && + ((t - it->texCoord).squaredLength() <= texCoordWeldRadius2)) { + // This is the vertex + return it->index; + } + ++it; + } + } + + // Note that a sliver triangle processed before its neighbors may reach here + // with a zero length normal. + + // The vertex does not exist. Create it. + const int i = outputVertexArray->size(); + outputVertexArray->append(v); + outputNormalArray->append(n); + outputTexCoordArray->append(t); + + // Store in the grid so that it will be remembered. + weldGrid.insert(VNTi(v, n, t, i)); + + return i; + } + + + /** + Updates each indexArray to refer to vertices in the + outputVertexArray. + + Called from process() + */ + void updateTriLists( + Array<Array<int>*>& indexArrayArray, + const Array<Vector3>& vertexArray, + const Array<Vector3>& normalArray, + const Array<Vector2>& texCoordArray) { + + // Compute a hash grid so that we can find neighbors quickly. + // It begins empty and is extended as the tri lists are iterated + // through. + weldGrid.clear(); + + // Process all triLists + int numTriLists = indexArrayArray.size(); + int u = 0; + for (int t = 0; t < numTriLists; ++t) { + Array<int>& triList = *(indexArrayArray[t]); + + // For all vertices in this list + for (int v = 0; v < triList.size(); ++v) { + // This vertex mapped to u in the flatVertexArray + triList[v] = getIndex(vertexArray[u], normalArray[u], texCoordArray[u]); + + /* +# ifdef G3D_DEBUG + { + int i = triList[v]; + Vector3 N = normalArray[i]; + debugAssertM(N.length() > 0.9f, "Produced non-unit normal"); + } +# endif + */ + ++u; + } + } + } + + /** 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) { + + int numTriLists = indexArrayArray.size(); + for (int t = 0; t < numTriLists; ++t) { + const Array<int>& triList = *(indexArrayArray[t]); + for (int v = 0; v < triList.size(); ++v) { + int i = triList[v]; + unrolledVertexArray.append(vertexArray[i]); + unrolledTexCoordArray.append(texCoordArray[i]); + } + } + } + + /** 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) { + + debugAssertM(vertexArray.size() % 3 == 0, "Input is not a triangle soup"); + debugAssertM(faceNormalArray.size() == 0, "Output must start empty."); + + for (int v = 0; v < vertexArray.size(); v += 3) { + const Vector3& e0 = vertexArray[v + 1] - vertexArray[v]; + const Vector3& e1 = vertexArray[v + 2] - vertexArray[v]; + + // Note that the length may be zero in the case of sliver polygons, e.g., + // those correcting a T-junction. + const Vector3& n = e0.cross(e1).directionOrZero(); + + // Append the normal once per vertex. + faceNormalArray.append(n, n, n); + } + } + + + /** + 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) { + + const float cosThresholdAngle = (float)cos(normalSmoothingAngle); + + debugAssert(vertexArray.size() == normalArray.size()); + smoothNormalArray.resize(normalArray.size()); + + // Compute a hash grid so that we can find neighbors quickly. + PointHashGrid<VN> grid(vertexWeldRadius); + for (int v = 0; v < normalArray.size(); ++v) { + grid.insert(VN(vertexArray[v], normalArray[v])); + } + + 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)); + + Vector3 sum; + + const Vector3& original = normalArray[v]; + while (it.hasMore()) { + const Vector3& N = it->normal; + const float cosAngle = N.dot(original); + + if (cosAngle > cosThresholdAngle) { + // This normal is close enough to consider + sum += N; + } + ++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: + + 1. Unroll the indexed triangle list into a triangle list, where + there are duplicated vertices. + + 2. Compute face normals for all triangles, and expand those into + the triangle vertices. + + 3. At each vertex, average all normals that are within normalSmoothingAngle. + + 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) { + + normalSmoothingAngle = normAngle; + normalWeldRadius2 = square(normRadius); + texCoordWeldRadius2 = square(texRadius); + + const bool hasTexCoords = (texCoordArray.size() > 0); + + if (hasTexCoords) { + debugAssertM(vertexArray.size() == texCoordArray.size(), + "Input arrays are not parallel."); + } + + Array<Vector3> unrolledVertexArray; + Array<Vector3> unrolledFaceNormalArray; + Array<Vector3> unrolledSmoothNormalArray; + Array<Vector2> unrolledTexCoordArray; + + if (! hasTexCoords) { + // Generate all zero texture coordinates + texCoordArray.resize(vertexArray.size()); + } + + // Generate a flat (unrolled) triangle list with texture coordinates. + unroll(indexArrayArray, vertexArray, texCoordArray, + unrolledVertexArray, unrolledTexCoordArray); + + // Put the output back into the input slots. Clear immediately to reduce peak + // memory. + outputVertexArray = &vertexArray; + outputNormalArray = &normalArray; + outputTexCoordArray = &texCoordArray; + outputVertexArray->fastClear(); + outputNormalArray->fastClear(); + outputTexCoordArray->fastClear(); + + // For every three vertices, generate their face normal and store it at + // each vertex. The output array has the same length as the input. + computeFaceNormals(unrolledVertexArray, unrolledFaceNormalArray); + + // Compute smooth normals at vertices. + smoothNormals(unrolledVertexArray, unrolledFaceNormalArray, unrolledSmoothNormalArray); + unrolledFaceNormalArray.clear(); + + // Regenerate the triangle lists + updateTriLists(indexArrayArray, unrolledVertexArray, unrolledSmoothNormalArray, unrolledTexCoordArray); + + if (! hasTexCoords) { + // Throw away the generated texCoords + texCoordArray.resize(0); + } + } + + WeldHelper(float vertRadius) : + weldGrid(vertRadius), + vertexWeldRadius(vertRadius) {} + +}; +} // Internal + +void MeshAlg::weld( + Array<Vector3>& vertexArray, + Array<Vector2>& texCoordArray, + Array<Vector3>& normalArray, + Array<Array<int>*>& indexArrayArray, + float normalSmoothingAngle, + float vertexWeldRadius, + float textureWeldRadius, + float normalWeldRadius) { + + _internal::WeldHelper(vertexWeldRadius).process( + vertexArray, texCoordArray, normalArray, indexArrayArray, + normalSmoothingAngle, textureWeldRadius, normalWeldRadius); +} + +} // G3D |