/* ----------------------------------------------------------------------------- This source file is part of OGRE (Object-oriented Graphics Rendering Engine) For the latest info, see http://www.ogre3d.org/ Copyright (c) 2000-2009 Torus Knot Software Ltd Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions: The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. ----------------------------------------------------------------------------- */ #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 = OGRE_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( 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( static_cast(pIndex) + indexData->indexStart * indexSize); unsigned short* p16Idx = static_cast(pIndex); unsigned int* p32Idx = static_cast(pIndex); #else union { void* pIndex; unsigned short* p16Idx; unsigned int* p32Idx; }; pIndex = indexData->indexBuffer->lock(HardwareBuffer::HBL_READ_ONLY); pIndex = static_cast( static_cast(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(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(sharedVertIndex0, sharedVertIndex1), std::pair(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(~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 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 if(!triangleFaceNormals.empty()) { 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( positionBuffer->lock(HardwareBuffer::HBL_READ_ONLY)); // Calculate triangles which are using this vertex set const EdgeData::EdgeGroup& eg = edgeGroups[vertexSet]; if (eg.triCount != 0) { 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( 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 = 0; unsigned int* p32Idx = 0; if (iData->indexBuffer->getType() == HardwareIndexBuffer::IT_32BIT) { p32Idx = static_cast( iData->indexBuffer->lock(HardwareBuffer::HBL_READ_ONLY)); } else { p16Idx = static_cast( 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)); } } } }