mesh welding

namespace
{
//computes a hash
REALINLINE u32 getBucketFromVector(const core::vector3df& vec, f32 tolerance, u32 bucketCount)
{
    f32 sum = (vec.X + vec.Y + vec.Z) / tolerance;
    return ((u32)sum) % bucketCount;
}

//helpers for comparing vertices
template<typename T>
bool vertsAreEqual(const T& v1, const T& v2, f32 tolerance, bool ignoreNormals)
{
    //empty, see specializations
}

template<>
inline bool vertsAreEqual<video::S3DVertex>(const video::S3DVertex& v1, const video::S3DVertex& v2, f32 tolerance, bool ignoreNormals)
{
    return
        v1.Pos.equals(v2.Pos, tolerance) &&
        (ignoreNormals || v1.Normal.equals(v2.Normal, tolerance)) &&
        v1.TCoords.equals(v2.TCoords, tolerance) &&
        (v1.Color == v2.Color);
}

template<>
inline bool vertsAreEqual<video::S3DVertex2TCoords>(const video::S3DVertex2TCoords& v1, const video::S3DVertex2TCoords& v2, f32 tolerance, bool ignoreNormals)
{
    return
        v1.Pos.equals(v2.Pos, tolerance) &&
        (ignoreNormals || v1.Normal.equals(v2.Normal, tolerance)) &&
        v1.TCoords.equals(v2.TCoords, tolerance) &&
        v1.TCoords2.equals(v2.TCoords2, tolerance) &&
        (v1.Color == v2.Color);
}

template<>
inline bool vertsAreEqual<video::S3DVertexTangents>(const video::S3DVertexTangents& v1, const video::S3DVertexTangents& v2, f32 tolerance, bool ignoreNormals)
{
    return
        v1.Pos.equals(v2.Pos, tolerance) &&
        (ignoreNormals || v1.Normal.equals(v2.Normal, tolerance)) &&
        v1.TCoords.equals(v2.TCoords) &&
        v1.Tangent.equals(v2.Tangent, tolerance) &&
        v1.Binormal.equals(v2.Binormal, tolerance) &&
        (v1.Color == v2.Color);
}

//TV: vertex type, TI: index type
//TVList: the used type of dynamic array for the vertex output
//TIList: the used type of dynamic array for the index output
//the lists must provide size() and push_back()
template <typename TV, typename TI, typename TVList, typename TIList>
void createMeshBufWelded2T(const IMeshBuffer* const mbIn, TVList& vertsOut, TIList& indicesOut, f32 tolerance, bool ignoreNormals)
{
    //more buckets: faster but needs more memory
    u32 avgVertsPerBucket = 4;  //smaller buckets = more buckets
    const u32 absoluteMaxBuckets = 100000;
    u32 bucketCount = core::min_(mbIn->getVertexCount() / avgVertsPerBucket, absoluteMaxBuckets);
    core::array<u32>* buckets = new core::array<u32>[bucketCount];

    //prepare buckets, may increase speed?

    //for (u32 i=0; i<bucketCount; ++i)
        //buckets[i] = core::array<u32>(avgVertsPerBucket);

    const TV* verticesIn = reinterpret_cast<const TV*>(mbIn->getVertices());
    core::array<TI> redirects;
    redirects.set_used(mbIn->getVertexCount());


    //we fill the buckets using hashes
    for (u32 i=0; i<mbIn->getVertexCount(); ++i)
    {
        u32 bucketNum = getBucketFromVector(verticesIn[i].Pos, tolerance, bucketCount);

        core::array<u32>* bucket = &buckets[bucketNum];

        bool found = false;

        for (u32 j=0; j<bucket->size(); ++j)
        {
            u32 vertexIndex = (*bucket)[j];
            if (vertsAreEqual(verticesIn[i], verticesIn[vertexIndex], tolerance, ignoreNormals))
            {
                found = true;
                redirects[i] = redirects[vertexIndex];
            }
        }

        //also check the previous and the next bucket

        bucket = (bucketNum == 0) ? &buckets[bucketCount-1] : &buckets[bucketNum-1];    //previous bucket
        if (!found)
            for (u32 j=0; j<bucket->size(); ++j)
            {
                u32 vertexIndex = (*bucket)[j];
                if (vertsAreEqual(verticesIn[i], verticesIn[vertexIndex], tolerance, ignoreNormals))
                {
                    found = true;
                    redirects[i] = redirects[vertexIndex];
                    break;
                }
            }

        bucket = (bucketNum+1 >= bucketCount ) ? &buckets[0] : &buckets[bucketNum+1];   //next bucket
        if (!found)
            for (u32 j=0; j<bucket->size(); ++j)
            {
                u32 vertexIndex = (*bucket)[j];
                if (vertsAreEqual(verticesIn[i], verticesIn[vertexIndex], tolerance, ignoreNormals))
                {
                    found = true;
                    redirects[i] = redirects[vertexIndex];
                    break;
                }
            }

        if (!found)
        {
            //add to bucket if not found
            buckets[bucketNum].push_back(i);

            //also add to mesh and add to redirect list
            vertsOut.push_back(verticesIn[i]);
            redirects[i] = vertsOut.size() -1;
        }
    }

    //vertsOut is now final.

    //now, indices have to be updated
    const TI* indicesIn = reinterpret_cast<const TI*>(mbIn->getIndices());
    for (u32 i=0; i<mbIn->getIndexCount(); i+=3)
    {
        TI ia = indicesIn[i+0];
        TI ib = indicesIn[i+1];
        TI ic = indicesIn[i+2];
        ia = redirects[ia];
        ib = redirects[ib];
        ic = redirects[ic];
        //check for degenerate triangles:
        if ((ia == ib) || (ib == ic) || (ic == ia) )
            continue;

        indicesOut.push_back(ia);
        indicesOut.push_back(ib);
        indicesOut.push_back(ic);
    }

    //now indicesOut are final
    delete[] buckets;
}

}

//! Creates a copy of a mesh, which will have identical vertices welded together
// supports 32 bit and uses buckets for speedup
IMesh* CMeshManipulator::createMeshWelded2(IMesh *mesh, f32 tolerance, bool ignoreNormals) const
{
#ifdef _MESH_WELDING_DEBUG
    u32 time = os::Timer::getRealTime();
    u32 vertCountInSum = 0;
    u32 vertCountOutSum = 0;
#endif
    SMesh* clone = new SMesh();
    clone->BoundingBox = mesh->getBoundingBox();

    for (u32 b=0; b<mesh->getMeshBufferCount(); ++b)
    {
        IMeshBuffer* mbIn = mesh->getMeshBuffer(b);
        IMeshBuffer* mbOut = 0;

        if (mbIn->getIndexType() == video::EIT_16BIT)
            switch (mbIn->getVertexType())
            {
            case video::EVT_STANDARD:
            {
                SMeshBuffer* mbOutSpec;
                mbOut = mbOutSpec = new SMeshBuffer();
                createMeshBufWelded2T<video::S3DVertex, u16, core::array<video::S3DVertex>, core::array<u16>>(mbIn, mbOutSpec->Vertices, mbOutSpec->Indices, tolerance, ignoreNormals);
                break;
            }
            case video::EVT_2TCOORDS:
            {
                SMeshBufferLightMap* mbOutSpec;
                mbOut = mbOutSpec = new SMeshBufferLightMap();
                createMeshBufWelded2T<video::S3DVertex2TCoords, u16, core::array<video::S3DVertex2TCoords>, core::array<u16>>(mbIn, mbOutSpec->Vertices, mbOutSpec->Indices, tolerance, ignoreNormals);
                break;
            }
            case video::EVT_TANGENTS:
            {
                SMeshBufferTangents* mbOutSpec;
                mbOut = mbOutSpec = new SMeshBufferTangents();
                createMeshBufWelded2T<video::S3DVertexTangents, u16, core::array<video::S3DVertexTangents>, core::array<u16>>(mbIn, mbOutSpec->Vertices, mbOutSpec->Indices, tolerance, ignoreNormals);
                break;
            }
            default:
                os::Printer::log("Cannot create welded mesh, vertex type unsupported", ELL_ERROR);
                break;
            }
        else
        {
            CDynamicMeshBuffer* mbOutSpec;
            mbOut = mbOutSpec = new CDynamicMeshBuffer(mbIn->getVertexType(), mbIn->getIndexType());
            video::E_VERTEX_TYPE vType = mbIn->getVertexType();
            video::E_INDEX_TYPE iType = mbIn->getIndexType();
            switch(mbIn->getVertexType())
            {
            case video::EVT_STANDARD:
                createMeshBufWelded2T<video::S3DVertex, u32, IVertexBuffer, IIndexBuffer>(mbIn, mbOutSpec->getVertexBuffer(), mbOutSpec->getIndexBuffer(), tolerance, ignoreNormals);
                break;
            case video::EVT_2TCOORDS:
                createMeshBufWelded2T<video::S3DVertex2TCoords, u32, IVertexBuffer, IIndexBuffer>(mbIn, mbOutSpec->getVertexBuffer(), mbOutSpec->getIndexBuffer(), tolerance, ignoreNormals);
                break;
            case video::EVT_TANGENTS:
                createMeshBufWelded2T<video::S3DVertexTangents, u32, IVertexBuffer, IIndexBuffer>(mbIn, mbOutSpec->getVertexBuffer(), mbOutSpec->getIndexBuffer(), tolerance, ignoreNormals);
                break;
            default:
                os::Printer::log("Cannot create welded mesh, vertex type unsupported", ELL_ERROR);
                break;
            }
        }

        if (mbOut == 0)
            clone->addMeshBuffer(mbIn); //if it could not be welded, just return the old mb
        else
        {
            mbOut->setBoundingBox(mbIn->getBoundingBox());
            mbOut->getMaterial() = mbIn->getMaterial();
            clone->addMeshBuffer(mbOut);
        }

#ifdef _MESH_WELDING_DEBUG
        vertCountInSum += mbIn->getVertexCount();
        vertCountOutSum += mbOut->getVertexCount();
#endif
    }

#ifdef _MESH_WELDING_DEBUG
    time = os::Timer::getRealTime() - time;

    core::stringw info = "Mesh welded. Vertex Count before: ";
    info += vertCountInSum;
    info += " after: ";
    info += vertCountOutSum;
    info += " took ";
    info += time;
    info += "ms";
    os::Printer::log(info.c_str(), ELL_DEBUG);
#endif
    return clone;
}