source: downloads/OgreMain/src/OgreEdgeListBuilder.cpp @ 3

/*
-----------------------------------------------------------------------------
This source file is part of OGRE
    (Object-oriented Graphics Rendering Engine)
For the latest info, see http://www.ogre3d.org/

Copyright (c) 2000-2006 Torus Knot Software Ltd
Also see acknowledgements in Readme.html

This program is free software; you can redistribute it and/or modify it under
the terms of the GNU Lesser General Public License as published by the Free Software
Foundation; either version 2 of the License, or (at your option) any later
version.

This program is distributed in the hope that it will be useful, but WITHOUT
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along with
this program; if not, write to the Free Software Foundation, Inc., 59 Temple
Place - Suite 330, Boston, MA 02111-1307, USA, or go to
http://www.gnu.org/copyleft/lesser.txt.

You may alternatively use this source under the terms of a specific version of
the OGRE Unrestricted License provided you have obtained such a license from
Torus Knot Software Ltd.
-----------------------------------------------------------------------------
*/
#include "OgreStableHeaders.h"
#include "OgreEdgeListBuilder.h"
#include "OgreLogManager.h"
#include "OgreStringConverter.h"
#include "OgreVertexIndexData.h"
#include "OgreException.h"
#include "OgreOptimisedUtil.h"

namespace Ogre {

    void EdgeData::log(Log* l)
    {
        EdgeGroupList::iterator i, iend;
        EdgeList::iterator ei, eiend;
        TriangleList::iterator ti, tiend;
        tiend = triangles.end();
        l->logMessage("Edge Data");
        l->logMessage("---------");
        size_t num = 0;
        for (ti = triangles.begin(); ti != tiend; ++ti, ++num)
        {
            Triangle& t = *ti;
            l->logMessage("Triangle " + StringConverter::toString(num) + " = {" +
                "indexSet=" + StringConverter::toString(t.indexSet) + ", " + 
                "vertexSet=" + StringConverter::toString(t.vertexSet) + ", " + 
                "v0=" + StringConverter::toString(t.vertIndex[0]) + ", " + 
                "v1=" + StringConverter::toString(t.vertIndex[1]) + ", " + 
                "v2=" + StringConverter::toString(t.vertIndex[2]) + "}"); 
        }
        iend = edgeGroups.end();
        for (i = edgeGroups.begin(); i != iend; ++i)
        {
            num = 0;
            eiend = i->edges.end();
            l->logMessage("Edge Group vertexSet=" + StringConverter::toString(i->vertexSet));
            for (ei = i->edges.begin(); ei != eiend; ++ei, ++num)
            {
                Edge& e = *ei;
                l->logMessage(
                    "Edge " + StringConverter::toString(num) + " = {\n" + 
                    "  tri0=" + StringConverter::toString(e.triIndex[0]) + ", \n" + 
                    "  tri1=" + StringConverter::toString(e.triIndex[1]) + ", \n" + 
                    "  v0=" + StringConverter::toString(e.vertIndex[0]) + ", \n" + 
                    "  v1=" + StringConverter::toString(e.vertIndex[1]) + ", \n"
                    "  degenerate=" + StringConverter::toString(e.degenerate) + " \n"
                    "}"); 
            }
        }
    }
    //---------------------------------------------------------------------
    EdgeListBuilder::EdgeListBuilder()
        : mEdgeData(0)
    {
    }
    //---------------------------------------------------------------------
    EdgeListBuilder::~EdgeListBuilder()
    {
    }
    //---------------------------------------------------------------------
    void EdgeListBuilder::addVertexData(const VertexData* vertexData)
    {
        if (vertexData->vertexStart != 0)
        {
            OGRE_EXCEPT(Exception::ERR_INVALIDPARAMS,
                "The base vertex index of the vertex data must be zero for build edge list.",
                "EdgeListBuilder::addVertexData");
        }

        mVertexDataList.push_back(vertexData);
    }
    //---------------------------------------------------------------------
    void EdgeListBuilder::addIndexData(const IndexData* indexData, 
        size_t vertexSet, RenderOperation::OperationType opType)
    {
        if (opType != RenderOperation::OT_TRIANGLE_LIST &&
            opType != RenderOperation::OT_TRIANGLE_FAN &&
            opType != RenderOperation::OT_TRIANGLE_STRIP)
        {
            OGRE_EXCEPT(Exception::ERR_INVALIDPARAMS,
                "Only triangle list, fan and strip are supported to build edge list.",
                "EdgeListBuilder::addIndexData");
        }

        Geometry geometry;
        geometry.indexData = indexData;
        geometry.vertexSet = vertexSet;
        geometry.opType = opType;
        geometry.indexSet = mGeometryList.size();
        mGeometryList.push_back(geometry);
    }
    //---------------------------------------------------------------------
    EdgeData* EdgeListBuilder::build(void)
    {
        /* Ok, here's the algorithm:
        For each set of indices in turn
          For each set of 3 indexes
            Create a new Triangle entry in the list
            For each vertex referenced by the tri indexes
              Get the position of the vertex as a Vector3 from the correct vertex buffer
              Attempt to locate this position in the existing common vertex set
              If not found
                Create a new common vertex entry in the list
              End If
              Populate the original vertex index and common vertex index 
            Next vertex
            Connect to existing edge(v1, v0) or create a new edge(v0, v1)
            Connect to existing edge(v2, v1) or create a new edge(v1, v2)
            Connect to existing edge(v0, v2) or create a new edge(v2, v0)
          Next set of 3 indexes
        Next index set

        Note that all edges 'belong' to the index set which originally caused them
        to be created, which also means that the 2 vertices on the edge are both referencing the 
        vertex buffer which this index set uses.
        */


        /* 
        There is a major consideration: 'What is a common vertex'? This is a
        crucial decision, since to form a completely close hull, you need to treat
        vertices which are not physically the same as equivalent. This is because
        there will be 'seams' in the model, where discrepancies in vertex components
        other than position (such as normals or texture coordinates) will mean
        that there are 2 vertices in the same place, and we MUST 'weld' them
        into a single common vertex in order to have a closed hull. Just looking
        at the unique vertex indices is not enough, since these seams would render
        the hull invalid.

        So, we look for positions which are the same across vertices, and treat 
        those as as single vertex for our edge calculation. However, this has
        it's own problems. There are OTHER vertices which may have a common 
        position that should not be welded. Imagine 2 cubes touching along one
        single edge. The common vertices on that edge, if welded, will cause 
        an ambiguous hull, since the edge will have 4 triangles attached to it,
        whilst a manifold mesh should only have 2 triangles attached to each edge.
        This is a problem.

        We deal with this with allow welded multiple pairs of edges. Using this
        techniques, we can build a individual hull even if the model which has a
        potentially ambiguous hull. This is feasible, because in the case of
        multiple hulls existing, each hull can cast same shadow in any situation.
        Notice: For stencil shadow, we intent to build a valid shadow volume for
        the mesh, not the valid hull for the mesh.
        */

        // Sort the geometries in the order of vertex set, so we can grouping
        // triangles by vertex set easy.
        std::sort(mGeometryList.begin(), mGeometryList.end(), geometryLess());
        // Initialize edge data
        mEdgeData = new EdgeData();
        // resize the edge group list to equal the number of vertex sets
        mEdgeData->edgeGroups.resize(mVertexDataList.size());
        // Initialise edge group data
        for (unsigned short vSet = 0; vSet < mVertexDataList.size(); ++vSet)
        {
            mEdgeData->edgeGroups[vSet].vertexSet = vSet;
            mEdgeData->edgeGroups[vSet].vertexData = mVertexDataList[vSet];
            mEdgeData->edgeGroups[vSet].triStart = 0;
            mEdgeData->edgeGroups[vSet].triCount = 0;
        }

        // Build triangles and edge list
        GeometryList::const_iterator i, iend;
        iend = mGeometryList.end();
        for (i = mGeometryList.begin(); i != iend; ++i)
        {
            buildTrianglesEdges(*i);
        }

        // Allocate memory for light facing calculate
        mEdgeData->triangleLightFacings.resize(mEdgeData->triangles.size());

        // Record closed, ie the mesh is manifold
        mEdgeData->isClosed = mEdgeMap.empty();

        return mEdgeData;
    }
    //---------------------------------------------------------------------
    void EdgeListBuilder::buildTrianglesEdges(const Geometry &geometry)
    {
        size_t indexSet = geometry.indexSet;
        size_t vertexSet = geometry.vertexSet;
        const IndexData* indexData = geometry.indexData;
        RenderOperation::OperationType opType = geometry.opType;

        size_t iterations;
        
        switch (opType)
        {
        case RenderOperation::OT_TRIANGLE_LIST:
            iterations = indexData->indexCount / 3;
            break;
        case RenderOperation::OT_TRIANGLE_FAN:
        case RenderOperation::OT_TRIANGLE_STRIP:
            iterations = indexData->indexCount - 2;
            break;
        default:
            return; // Just in case
        };

        // The edge group now we are dealing with.
        EdgeData::EdgeGroup& eg = mEdgeData->edgeGroups[vertexSet];

                // locate position element & the buffer to go with it
        const VertexData* vertexData = mVertexDataList[vertexSet];
                const VertexElement* posElem = vertexData->vertexDeclaration->findElementBySemantic(VES_POSITION);
                HardwareVertexBufferSharedPtr vbuf = 
                        vertexData->vertexBufferBinding->getBuffer(posElem->getSource());
                // lock the buffer for reading
                unsigned char* pBaseVertex = static_cast<unsigned char*>(
                        vbuf->lock(HardwareBuffer::HBL_READ_ONLY));

        // Get the indexes ready for reading
                bool idx32bit = (indexData->indexBuffer->getType() == HardwareIndexBuffer::IT_32BIT);
                size_t indexSize = idx32bit ? sizeof(uint32) : sizeof(uint16);
#if defined(_MSC_VER) && _MSC_VER <= 1300
        // NB: Can't use un-named union with VS.NET 2002 when /RTC1 compile flag enabled.
        void* pIndex = indexData->indexBuffer->lock(HardwareBuffer::HBL_READ_ONLY);
                pIndex = static_cast<void*>(
                        static_cast<char*>(pIndex) + indexData->indexStart * indexSize);
        unsigned short* p16Idx = static_cast<unsigned short*>(pIndex);
        unsigned int* p32Idx = static_cast<unsigned int*>(pIndex);
#else
        union {
            void* pIndex;
            unsigned short* p16Idx;
            unsigned int* p32Idx;
        };
        pIndex = indexData->indexBuffer->lock(HardwareBuffer::HBL_READ_ONLY);
                pIndex = static_cast<void*>(
                        static_cast<char*>(pIndex) + indexData->indexStart * indexSize);
#endif

        // Iterate over all the groups of 3 indexes
        unsigned int index[3];
        // Get the triangle start, if we have more than one index set then this
        // will not be zero
        size_t triangleIndex = mEdgeData->triangles.size();
        // If it's first time dealing with the edge group, setup triStart for it.
        // Note that we are assume geometries sorted by vertex set.
        if (!eg.triCount)
        {
            eg.triStart = triangleIndex;
        }
        // Pre-reserve memory for less thrashing
        mEdgeData->triangles.reserve(triangleIndex + iterations);
        mEdgeData->triangleFaceNormals.reserve(triangleIndex + iterations);
        for (size_t t = 0; t < iterations; ++t)
        {
            EdgeData::Triangle tri;
            tri.indexSet = indexSet;
            tri.vertexSet = vertexSet;

            if (opType == RenderOperation::OT_TRIANGLE_LIST || t == 0)
            {
                // Standard 3-index read for tri list or first tri in strip / fan
                if (idx32bit)
                {
                    index[0] = p32Idx[0];
                    index[1] = p32Idx[1];
                    index[2] = p32Idx[2];
                    p32Idx += 3;
                }
                else
                {
                    index[0] = p16Idx[0];
                    index[1] = p16Idx[1];
                    index[2] = p16Idx[2];
                    p16Idx += 3;
                }
            }
            else
            {
                // Strips are formed from last 2 indexes plus the current one for
                // triangles after the first.
                // For fans, all the triangles share the first vertex, plus last
                // one index and the current one for triangles after the first.
                // We also make sure that all the triangles are process in the
                // _anti_ clockwise orientation
                index[(opType == RenderOperation::OT_TRIANGLE_STRIP) && (t & 1) ? 0 : 1] = index[2];
                // Read for the last tri index
                if (idx32bit)
                    index[2] = *p32Idx++;
                else
                    index[2] = *p16Idx++;
            }

            Vector3 v[3];
            for (size_t i = 0; i < 3; ++i)
            {
                // Populate tri original vertex index
                tri.vertIndex[i] = index[i];

                // Retrieve the vertex position
                unsigned char* pVertex = pBaseVertex + (index[i] * vbuf->getVertexSize());
                float* pFloat;
                posElem->baseVertexPointerToElement(pVertex, &pFloat);
                v[i].x = *pFloat++;
                v[i].y = *pFloat++;
                v[i].z = *pFloat++;
                // find this vertex in the existing vertex map, or create it
                tri.sharedVertIndex[i] = 
                    findOrCreateCommonVertex(v[i], vertexSet, indexSet, index[i]);
            }

            // Ignore degenerate triangle
            if (tri.sharedVertIndex[0] != tri.sharedVertIndex[1] &&
                tri.sharedVertIndex[1] != tri.sharedVertIndex[2] &&
                tri.sharedVertIndex[2] != tri.sharedVertIndex[0])
            {
                // Calculate triangle normal (NB will require recalculation for 
                // skeletally animated meshes)
                mEdgeData->triangleFaceNormals.push_back(
                    Math::calculateFaceNormalWithoutNormalize(v[0], v[1], v[2]));
                // Add triangle to list
                mEdgeData->triangles.push_back(tri);
                // Connect or create edges from common list
                connectOrCreateEdge(vertexSet, triangleIndex, 
                    tri.vertIndex[0], tri.vertIndex[1], 
                    tri.sharedVertIndex[0], tri.sharedVertIndex[1]);
                connectOrCreateEdge(vertexSet, triangleIndex, 
                    tri.vertIndex[1], tri.vertIndex[2], 
                    tri.sharedVertIndex[1], tri.sharedVertIndex[2]);
                connectOrCreateEdge(vertexSet, triangleIndex, 
                    tri.vertIndex[2], tri.vertIndex[0], 
                    tri.sharedVertIndex[2], tri.sharedVertIndex[0]);
                ++triangleIndex;
            }
        }

        // Update triCount for the edge group. Note that we are assume
        // geometries sorted by vertex set.
        eg.triCount = triangleIndex - eg.triStart;

        indexData->indexBuffer->unlock();
        vbuf->unlock();
    }
    //---------------------------------------------------------------------
    void EdgeListBuilder::connectOrCreateEdge(size_t vertexSet, size_t triangleIndex, 
        size_t vertIndex0, size_t vertIndex1, size_t sharedVertIndex0, 
        size_t sharedVertIndex1)
    {
        // Find the existing edge (should be reversed order) on shared vertices
        EdgeMap::iterator emi = mEdgeMap.find(std::pair<size_t, size_t>(sharedVertIndex1, sharedVertIndex0));
        if (emi != mEdgeMap.end())
        {
            // The edge already exist, connect it
            EdgeData::Edge& e = mEdgeData->edgeGroups[emi->second.first].edges[emi->second.second];
            // update with second side
            e.triIndex[1] = triangleIndex;
            e.degenerate = false;

            // Remove from the edge map, so we never supplied to connect edge again
            mEdgeMap.erase(emi);
        }
        else
        {
            // Not found, create new edge
            mEdgeMap.insert(EdgeMap::value_type(
                std::pair<size_t, size_t>(sharedVertIndex0, sharedVertIndex1),
                std::pair<size_t, size_t>(vertexSet, mEdgeData->edgeGroups[vertexSet].edges.size())));
            EdgeData::Edge e;
            e.degenerate = true; // initialise as degenerate

            // Set only first tri, the other will be completed in connect existing edge
            e.triIndex[0] = triangleIndex;
            e.triIndex[1] = static_cast<size_t>(~0);
            e.sharedVertIndex[0] = sharedVertIndex0;
            e.sharedVertIndex[1] = sharedVertIndex1;
            e.vertIndex[0] = vertIndex0;
            e.vertIndex[1] = vertIndex1;
            mEdgeData->edgeGroups[vertexSet].edges.push_back(e);
        }
    }
    //---------------------------------------------------------------------
    size_t EdgeListBuilder::findOrCreateCommonVertex(const Vector3& vec, 
        size_t vertexSet, size_t indexSet, size_t originalIndex)
    {
        // Because the algorithm doesn't care about manifold or not, we just identifying
        // the common vertex by EXACT same position.
        // Hint: We can use quantize method for welding almost same position vertex fastest.
        std::pair<CommonVertexMap::iterator, bool> inserted =
            mCommonVertexMap.insert(CommonVertexMap::value_type(vec, mVertices.size()));
        if (!inserted.second)
        {
            // Already existing, return old one
            return inserted.first->second;
        }
        // Not found, insert
        CommonVertex newCommon;
        newCommon.index = mVertices.size();
        newCommon.position = vec;
        newCommon.vertexSet = vertexSet;
        newCommon.indexSet = indexSet;
        newCommon.originalIndex = originalIndex;
        mVertices.push_back(newCommon);
        return newCommon.index;
    }
    //---------------------------------------------------------------------
    //---------------------------------------------------------------------
    void EdgeData::updateTriangleLightFacing(const Vector4& lightPos)
    {
        // Triangle face normals should be 1:1 with light facing flags
        assert(triangleFaceNormals.size() == triangleLightFacings.size());

        // Use optimised util to determine if triangle's face normal are light facing
        OptimisedUtil::getImplementation()->calculateLightFacing(
            lightPos,
            &triangleFaceNormals.front(),
            &triangleLightFacings.front(),
            triangleLightFacings.size());
    }
    //---------------------------------------------------------------------
    void EdgeData::updateFaceNormals(size_t vertexSet, 
        const HardwareVertexBufferSharedPtr& positionBuffer)
    {
        assert (positionBuffer->getVertexSize() == sizeof(float) * 3
            && "Position buffer should contain only positions!");

        // Triangle face normals should be 1:1 with triangles
        assert(triangleFaceNormals.size() == triangles.size());

        // Lock buffer for reading
        float* pVert = static_cast<float*>(
            positionBuffer->lock(HardwareBuffer::HBL_READ_ONLY));

        // Calculate triangles which are using this vertex set
        const EdgeData::EdgeGroup& eg = edgeGroups[vertexSet];
        OptimisedUtil::getImplementation()->calculateFaceNormals(
            pVert,
            &triangles[eg.triStart],
            &triangleFaceNormals[eg.triStart],
            eg.triCount);

        // unlock the buffer
        positionBuffer->unlock();
    }
    //---------------------------------------------------------------------
    void EdgeListBuilder::log(Log* l)
    {
        l->logMessage("EdgeListBuilder Log");
        l->logMessage("-------------------");
        l->logMessage("Number of vertex sets: " + StringConverter::toString(mVertexDataList.size()));
        l->logMessage("Number of index sets: " + StringConverter::toString(mGeometryList.size()));
        
        size_t i, j;
        // Log original vertex data
        for(i = 0; i < mVertexDataList.size(); ++i)
        {
            const VertexData* vData = mVertexDataList[i];
            l->logMessage(".");
            l->logMessage("Original vertex set " + 
                StringConverter::toString(i) + " - vertex count " + 
                StringConverter::toString(vData->vertexCount));
            const VertexElement* posElem = vData->vertexDeclaration->findElementBySemantic(VES_POSITION);
            HardwareVertexBufferSharedPtr vbuf = 
                vData->vertexBufferBinding->getBuffer(posElem->getSource());
            // lock the buffer for reading
            unsigned char* pBaseVertex = static_cast<unsigned char*>(
                vbuf->lock(HardwareBuffer::HBL_READ_ONLY));
            float* pFloat;
            for (j = 0; j < vData->vertexCount; ++j)
            {
                posElem->baseVertexPointerToElement(pBaseVertex, &pFloat);
                l->logMessage("Vertex " + StringConverter::toString(j) + 
                    ": (" + StringConverter::toString(pFloat[0]) + 
                    ", " + StringConverter::toString(pFloat[1]) + 
                    ", " + StringConverter::toString(pFloat[2]) + ")");
                pBaseVertex += vbuf->getVertexSize();
            }
            vbuf->unlock();
        }

        // Log original index data
        for(i = 0; i < mGeometryList.size(); i++)
        {
            const IndexData* iData = mGeometryList[i].indexData;
            l->logMessage(".");
            l->logMessage("Original triangle set " + 
                StringConverter::toString(mGeometryList[i].indexSet) + " - index count " + 
                StringConverter::toString(iData->indexCount) + " - " + 
            "vertex set " + StringConverter::toString(mGeometryList[i].vertexSet) + " - " + 
            "operationType " + StringConverter::toString(mGeometryList[i].opType));
            // Get the indexes ready for reading
            unsigned short* p16Idx;
            unsigned int* p32Idx;

            if (iData->indexBuffer->getType() == HardwareIndexBuffer::IT_32BIT)
            {
                p32Idx = static_cast<unsigned int*>(
                    iData->indexBuffer->lock(HardwareBuffer::HBL_READ_ONLY));
            }
            else
            {
                p16Idx = static_cast<unsigned short*>(
                    iData->indexBuffer->lock(HardwareBuffer::HBL_READ_ONLY));
            }

            for (j = 0; j < iData->indexCount;  )
            {
                if (iData->indexBuffer->getType() == HardwareIndexBuffer::IT_32BIT)
                {
                    if (mGeometryList[i].opType == RenderOperation::OT_TRIANGLE_LIST
                        || j == 0)
                    {
                        unsigned int n1 = *p32Idx++;
                        unsigned int n2 = *p32Idx++;
                        unsigned int n3 = *p32Idx++;
                        l->logMessage("Triangle " + StringConverter::toString(j) + 
                            ": (" + StringConverter::toString(n1) + 
                            ", " + StringConverter::toString(n2) + 
                            ", " + StringConverter::toString(n3) + ")");
                        j += 3;
                    }
                    else
                    {
                        l->logMessage("Triangle " + StringConverter::toString(j) + 
                            ": (" + StringConverter::toString(*p32Idx++) + ")");
                        j++;
                    }
                }
                else
                {
                    if (mGeometryList[i].opType == RenderOperation::OT_TRIANGLE_LIST
                        || j == 0)
                    {
                        unsigned short n1 = *p16Idx++;
                        unsigned short n2 = *p16Idx++;
                        unsigned short n3 = *p16Idx++;
                        l->logMessage("Index " + StringConverter::toString(j) + 
                            ": (" + StringConverter::toString(n1) + 
                            ", " + StringConverter::toString(n2) + 
                            ", " + StringConverter::toString(n3) + ")");
                        j += 3;
                    }
                    else
                    {
                        l->logMessage("Triangle " + StringConverter::toString(j) + 
                            ": (" + StringConverter::toString(*p16Idx++) + ")");
                        j++;
                    }
                }


            }

            iData->indexBuffer->unlock();


            // Log common vertex list
            l->logMessage(".");
            l->logMessage("Common vertex list - vertex count " + 
                StringConverter::toString(mVertices.size()));
            for (i = 0; i < mVertices.size(); ++i)
            {
                CommonVertex& c = mVertices[i];
                l->logMessage("Common vertex " + StringConverter::toString(i) + 
                    ": (vertexSet=" + StringConverter::toString(c.vertexSet) + 
                    ", originalIndex=" + StringConverter::toString(c.originalIndex) + 
                    ", position=" + StringConverter::toString(c.position));
            }
        }

    }



}