00001 /* 00002 ----------------------------------------------------------------------------- 00003 This source file is part of OGRE 00004 (Object-oriented Graphics Rendering Engine) 00005 For the latest info, see http://www.ogre3d.org/ 00006 00007 Copyright © 2000-2004 The OGRE Team 00008 Also see acknowledgements in Readme.html 00009 00010 This program is free software; you can redistribute it and/or modify it under 00011 the terms of the GNU Lesser General Public License as published by the Free Software 00012 Foundation; either version 2 of the License, or (at your option) any later 00013 version. 00014 00015 This program is distributed in the hope that it will be useful, but WITHOUT 00016 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS 00017 FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details. 00018 00019 You should have received a copy of the GNU Lesser General Public License along with 00020 this program; if not, write to the Free Software Foundation, Inc., 59 Temple 00021 Place - Suite 330, Boston, MA 02111-1307, USA, or go to 00022 http://www.gnu.org/copyleft/lesser.txt. 00023 ----------------------------------------------------------------------------- 00024 */ 00025 #include "OgreStableHeaders.h" 00026 #include "OgreEdgeListBuilder.h" 00027 #include "OgreLogManager.h" 00028 #include "OgreStringConverter.h" 00029 #include "OgreVertexIndexData.h" 00030 00031 namespace Ogre { 00032 00033 void EdgeData::log(Log* l) 00034 { 00035 EdgeGroupList::iterator i, iend; 00036 EdgeList::iterator ei, eiend; 00037 TriangleList::iterator ti, tiend; 00038 tiend = triangles.end(); 00039 l->logMessage("Edge Data"); 00040 l->logMessage("---------"); 00041 size_t num = 0; 00042 for (ti = triangles.begin(); ti != tiend; ++ti, ++num) 00043 { 00044 Triangle& t = *ti; 00045 l->logMessage("Triangle " + StringConverter::toString(num) + " = {" + 00046 "indexSet=" + StringConverter::toString(t.indexSet) + ", " + 00047 "vertexSet=" + StringConverter::toString(t.vertexSet) + ", " + 00048 "v0=" + StringConverter::toString(t.vertIndex[0]) + ", " + 00049 "v1=" + StringConverter::toString(t.vertIndex[1]) + ", " + 00050 "v2=" + StringConverter::toString(t.vertIndex[2]) + "}"); 00051 } 00052 iend = edgeGroups.end(); 00053 for (i = edgeGroups.begin(); i != iend; ++i) 00054 { 00055 num = 0; 00056 eiend = i->edges.end(); 00057 l->logMessage("Edge Group vertexSet=" + StringConverter::toString(i->vertexSet)); 00058 for (ei = i->edges.begin(); ei != eiend; ++ei, ++num) 00059 { 00060 Edge& e = *ei; 00061 l->logMessage( 00062 "Edge " + StringConverter::toString(num) + " = {\n" + 00063 " tri0=" + StringConverter::toString(e.triIndex[0]) + ", \n" + 00064 " tri1=" + StringConverter::toString(e.triIndex[1]) + ", \n" + 00065 " v0=" + StringConverter::toString(e.vertIndex[0]) + ", \n" + 00066 " v1=" + StringConverter::toString(e.vertIndex[1]) + ", \n" 00067 " degenerate=" + StringConverter::toString(e.degenerate) + " \n" 00068 "}"); 00069 } 00070 } 00071 } 00072 //--------------------------------------------------------------------- 00073 EdgeListBuilder::EdgeListBuilder() 00074 { 00075 } 00076 //--------------------------------------------------------------------- 00077 EdgeListBuilder::~EdgeListBuilder() 00078 { 00079 } 00080 //--------------------------------------------------------------------- 00081 void EdgeListBuilder::addVertexData(const VertexData* vertexData) 00082 { 00083 mVertexDataList.push_back(vertexData); 00084 } 00085 //--------------------------------------------------------------------- 00086 void EdgeListBuilder::addIndexData(const IndexData* indexData, 00087 size_t vertexSet, RenderOperation::OperationType opType) 00088 { 00089 mIndexDataList.push_back(indexData); 00090 mIndexDataVertexDataSetList.push_back(vertexSet); 00091 mOperationTypeList.push_back(opType); 00092 } 00093 //--------------------------------------------------------------------- 00094 EdgeData* EdgeListBuilder::build(void) 00095 { 00096 /* Ok, here's the algorithm: 00097 For each set of indices in turn 00098 // First pass, create triangles and create edges 00099 For each set of 3 indexes 00100 Create a new Triangle entry in the list 00101 For each vertex referenced by the tri indexes 00102 Get the position of the vertex as a Vector3 from the correct vertex buffer 00103 Attempt to locate this position in the existing common vertex set 00104 If not found 00105 Create a new common vertex entry in the list 00106 End If 00107 Populate the original vertex index and common vertex index 00108 Next vertex 00109 If commonIndex[0] < commonIndex[1] 00110 Create a new edge 00111 End If 00112 If commonIndex[1] < commonIndex[2] 00113 Create a new edge 00114 End If 00115 If commonIndex[2] < commonIndex[0] 00116 Create a new edge 00117 End If 00118 Next set of 3 indexes 00119 Next index set 00120 // Identify shared edges (works across index sets) 00121 For each triangle in the common triangle list 00122 If commonIndex[0] > commonIndex[1] 00123 Find existing edge and update with second side 00124 End If 00125 If commonIndex[1] > commonIndex[2] 00126 Find existing edge and update with second side 00127 End If 00128 If commonIndex[2] > commonIndex[0] 00129 Find existing edge and update with second side 00130 End If 00131 Next triangle 00132 00133 Note that all edges 'belong' to the index set which originally caused them 00134 to be created, which also means that the 2 vertices on the edge are both referencing the 00135 vertex buffer which this index set uses. 00136 */ 00137 00138 mEdgeData = new EdgeData(); 00139 // resize the edge group list to equal the number of vertex sets 00140 mEdgeData->edgeGroups.resize(mVertexDataList.size()); 00141 // Initialise edge group data 00142 for (unsigned short vSet = 0; vSet < mVertexDataList.size(); ++vSet) 00143 { 00144 mEdgeData->edgeGroups[vSet].vertexSet = vSet; 00145 mEdgeData->edgeGroups[vSet].vertexData = mVertexDataList[vSet]; 00146 } 00147 00148 IndexDataList::iterator i, iend; 00149 std::vector<size_t>::iterator mapi, mapiend; 00150 mapiend = mIndexDataVertexDataSetList.end(); 00151 mapi = mIndexDataVertexDataSetList.begin(); 00152 iend = mIndexDataList.end(); 00153 // Stage 1, build triangles and initial edge list 00154 size_t indexSet = 0; 00155 for (i = mIndexDataList.begin(); i != iend; ++i, ++mapi, ++indexSet) 00156 { 00157 buildTrianglesEdges(indexSet, *mapi); 00158 } 00159 // Stage 2, link edges 00160 connectEdges(); 00161 00162 // Log 00163 //log(LogManager::getSingleton().createLog("EdgeListBuilder.log")); 00164 00165 return mEdgeData; 00166 00167 00168 } 00169 //--------------------------------------------------------------------- 00170 void EdgeListBuilder::buildTrianglesEdges(size_t indexSet, size_t vertexSet) 00171 { 00172 const IndexData* indexData = mIndexDataList[indexSet]; 00173 RenderOperation::OperationType opType = mOperationTypeList[indexSet]; 00174 00175 size_t iterations; 00176 00177 switch (opType) 00178 { 00179 case RenderOperation::OT_TRIANGLE_LIST: 00180 iterations = indexData->indexCount / 3; 00181 break; 00182 case RenderOperation::OT_TRIANGLE_FAN: 00183 case RenderOperation::OT_TRIANGLE_STRIP: 00184 iterations = indexData->indexCount - 2; 00185 break; 00186 default: 00187 break; 00188 }; 00189 00190 00191 00192 // locate position element & the buffer to go with it 00193 const VertexData* vertexData = mVertexDataList[vertexSet]; 00194 const VertexElement* posElem = vertexData->vertexDeclaration->findElementBySemantic(VES_POSITION); 00195 HardwareVertexBufferSharedPtr vbuf = 00196 vertexData->vertexBufferBinding->getBuffer(posElem->getSource()); 00197 // lock the buffer for reading 00198 unsigned char* pBaseVertex = static_cast<unsigned char*>( 00199 vbuf->lock(HardwareBuffer::HBL_READ_ONLY)); 00200 00201 // Get the indexes ready for reading 00202 unsigned short* p16Idx; 00203 unsigned int* p32Idx; 00204 00205 if (indexData->indexBuffer->getType() == HardwareIndexBuffer::IT_32BIT) 00206 { 00207 p32Idx = static_cast<unsigned int*>( 00208 indexData->indexBuffer->lock(HardwareBuffer::HBL_READ_ONLY)); 00209 } 00210 else 00211 { 00212 p16Idx = static_cast<unsigned short*>( 00213 indexData->indexBuffer->lock(HardwareBuffer::HBL_READ_ONLY)); 00214 } 00215 00216 // Iterate over all the groups of 3 indexes 00217 Real* pReal; 00218 // Get the triangle start, if we have more than one index set then this 00219 // will not be zero 00220 size_t triStart = mEdgeData->triangles.size(); 00221 // Pre-reserve memory for less thrashing 00222 mEdgeData->triangles.reserve(triStart + iterations); 00223 for (size_t t = 0; t < iterations; ++t) 00224 { 00225 EdgeData::Triangle tri; 00226 tri.indexSet = indexSet; 00227 tri.vertexSet = vertexSet; 00228 00229 unsigned int index[3]; 00230 Vector3 v[3]; 00231 for (size_t i = 0; i < 3; ++i) 00232 { 00233 // Standard 3-index read for tri list or first tri in strip / fan 00234 if (opType == RenderOperation::OT_TRIANGLE_LIST || 00235 t == 0) 00236 { 00237 if (indexData->indexBuffer->getType() == HardwareIndexBuffer::IT_32BIT) 00238 { 00239 index[i] = *p32Idx++; 00240 } 00241 else 00242 { 00243 index[i] = *p16Idx++; 00244 } 00245 } 00246 else 00247 { 00248 // Strips and fans are formed from last 2 indexes plus the 00249 // current one for triangles after the first 00250 if (indexData->indexBuffer->getType() == HardwareIndexBuffer::IT_32BIT) 00251 { 00252 index[i] = p32Idx[i-2]; 00253 } 00254 else 00255 { 00256 index[i] = p16Idx[i-2]; 00257 } 00258 // Perform single-index increment at the last tri index 00259 if (i == 2) 00260 { 00261 if (indexData->indexBuffer->getType() == HardwareIndexBuffer::IT_32BIT) 00262 { 00263 p32Idx++; 00264 } 00265 else 00266 { 00267 p16Idx++; 00268 } 00269 00270 } 00271 00272 } 00273 00274 // Populate tri original vertex index 00275 tri.vertIndex[i] = index[i]; 00276 00277 // Retrieve the vertex position 00278 unsigned char* pVertex = pBaseVertex + (index[i] * vbuf->getVertexSize()); 00279 posElem->baseVertexPointerToElement(pVertex, &pReal); 00280 v[i].x = *pReal++; 00281 v[i].y = *pReal++; 00282 v[i].z = *pReal++; 00283 // find this vertex in the existing vertex map, or create it 00284 tri.sharedVertIndex[i] = findOrCreateCommonVertex(v[i], vertexSet); 00285 } 00286 // Calculate triangle normal (NB will require recalculation for 00287 // skeletally animated meshes) 00288 tri.normal = Math::calculateFaceNormal(v[0], v[1], v[2]); 00289 // Add triangle to list 00290 mEdgeData->triangles.push_back(tri); 00291 // Create edges from common list 00292 EdgeData::Edge e; 00293 e.degenerate = true; // initialise as degenerate 00294 if (tri.sharedVertIndex[0] < tri.sharedVertIndex[1]) 00295 { 00296 // Set only first tri, the other will be completed in connectEdges 00297 e.triIndex[0] = triStart + t; 00298 e.sharedVertIndex[0] = tri.sharedVertIndex[0]; 00299 e.sharedVertIndex[1] = tri.sharedVertIndex[1]; 00300 e.vertIndex[0] = tri.vertIndex[0]; 00301 e.vertIndex[1] = tri.vertIndex[1]; 00302 mEdgeData->edgeGroups[vertexSet].edges.push_back(e); 00303 } 00304 if (tri.sharedVertIndex[1] < tri.sharedVertIndex[2]) 00305 { 00306 // Set only first tri, the other will be completed in connectEdges 00307 e.triIndex[0] = triStart + t; 00308 e.sharedVertIndex[0] = tri.sharedVertIndex[1]; 00309 e.sharedVertIndex[1] = tri.sharedVertIndex[2]; 00310 e.vertIndex[0] = tri.vertIndex[1]; 00311 e.vertIndex[1] = tri.vertIndex[2]; 00312 mEdgeData->edgeGroups[vertexSet].edges.push_back(e); 00313 } 00314 if (tri.sharedVertIndex[2] < tri.sharedVertIndex[0]) 00315 { 00316 // Set only first tri, the other will be completed in connectEdges 00317 e.triIndex[0] = triStart + t; 00318 e.sharedVertIndex[0] = tri.sharedVertIndex[2]; 00319 e.sharedVertIndex[1] = tri.sharedVertIndex[0]; 00320 e.vertIndex[0] = tri.vertIndex[2]; 00321 e.vertIndex[1] = tri.vertIndex[0]; 00322 mEdgeData->edgeGroups[vertexSet].edges.push_back(e); 00323 } 00324 00325 } 00326 indexData->indexBuffer->unlock(); 00327 vbuf->unlock(); 00328 00329 00330 00331 00332 } 00333 //--------------------------------------------------------------------- 00334 size_t EdgeListBuilder::findOrCreateCommonVertex(const Vector3& vec, size_t vertexSet) 00335 { 00336 // Iterate over existing list 00337 CommonVertexList::iterator i, iend; 00338 iend = mVertices.end(); 00339 size_t index = 0; 00340 for (i = mVertices.begin(); i != iend; ++i, ++index) 00341 { 00342 const CommonVertex& commonVec = *i; 00343 00344 if (Math::RealEqual(vec.x, commonVec.position.x, 1e-04) && 00345 Math::RealEqual(vec.y, commonVec.position.y, 1e-04) && 00346 Math::RealEqual(vec.z, commonVec.position.z, 1e-04)) 00347 { 00348 return index; 00349 } 00350 00351 } 00352 // Not found, insert 00353 CommonVertex newCommon; 00354 newCommon.index = mVertices.size(); 00355 newCommon.position = vec; 00356 newCommon.vertexSet = vertexSet; 00357 mVertices.push_back(newCommon); 00358 return newCommon.index; 00359 } 00360 //--------------------------------------------------------------------- 00361 void EdgeListBuilder::connectEdges(void) 00362 { 00363 // Iterate over existing triangles 00364 EdgeData::TriangleList::iterator ti, tiend; 00365 tiend = mEdgeData->triangles.end(); 00366 size_t triIndex = 0; 00367 for (ti = mEdgeData->triangles.begin(); ti != tiend; ++ti, ++triIndex) 00368 { 00369 EdgeData::Triangle& tri = *ti; 00370 EdgeData::Edge* e; 00371 if (tri.sharedVertIndex[0] > tri.sharedVertIndex[1]) 00372 { 00373 e = findEdge(tri.sharedVertIndex[1], tri.sharedVertIndex[0]); 00374 if (e) 00375 { 00376 e->triIndex[1] = triIndex; 00377 e->degenerate = false; 00378 } 00379 } 00380 if (tri.sharedVertIndex[1] > tri.sharedVertIndex[2]) 00381 { 00382 // Find the existing edge (should be reversed order) 00383 e = findEdge(tri.sharedVertIndex[2], tri.sharedVertIndex[1]); 00384 if (e) 00385 { 00386 e->triIndex[1] = triIndex; 00387 e->degenerate = false; 00388 } 00389 } 00390 if (tri.sharedVertIndex[2] > tri.sharedVertIndex[0]) 00391 { 00392 e = findEdge(tri.sharedVertIndex[0], tri.sharedVertIndex[2]); 00393 if (e) 00394 { 00395 e->triIndex[1] = triIndex; 00396 e->degenerate = false; 00397 } 00398 } 00399 00400 } 00401 00402 00403 } 00404 //--------------------------------------------------------------------- 00405 EdgeData::Edge* EdgeListBuilder::findEdge(size_t sharedIndex1, size_t sharedIndex2) 00406 { 00407 // Iterate over the existing edges 00408 EdgeData::EdgeGroupList::iterator i, iend; 00409 EdgeData::EdgeList::iterator ei, eiend; 00410 00411 iend = mEdgeData->edgeGroups.end(); 00412 for (i = mEdgeData->edgeGroups.begin(); i != iend; ++i) 00413 { 00414 eiend = i->edges.end(); 00415 for (ei = i->edges.begin(); ei != eiend; ++ei) 00416 { 00417 EdgeData::Edge& e = *ei; 00418 if (e.sharedVertIndex[0] == sharedIndex1 && e.sharedVertIndex[1] == sharedIndex2) 00419 { 00420 return &(*ei); 00421 } 00422 } 00423 } 00424 00425 // no edge 00426 return 0; 00427 00428 } 00429 //--------------------------------------------------------------------- 00430 //--------------------------------------------------------------------- 00431 void EdgeData::updateTriangleLightFacing(const Vector4& lightPos) 00432 { 00433 // Iterate over the triangles, and determine if they are light facing 00434 EdgeData::TriangleList::iterator ti, tiend; 00435 tiend = triangles.end(); 00436 Vector3 vertToLight; 00437 for (ti = triangles.begin(); ti != tiend; ++ti) 00438 { 00439 EdgeData::Triangle& t = *ti; 00440 // Get pointer to positions, and reference the first position 00441 00442 Real dp = t.normal.dotProduct(lightPos); 00443 t.lightFacing = (dp > 0); 00444 00445 } 00446 00447 } 00448 //--------------------------------------------------------------------- 00449 void EdgeData::updateFaceNormals(size_t vertexSet, 00450 HardwareVertexBufferSharedPtr positionBuffer) 00451 { 00452 assert (positionBuffer->getVertexSize() == sizeof(Real) * 3 00453 && "Position buffer should contain only positions!"); 00454 00455 // Lock buffer for reading 00456 Real* pVert = static_cast<Real*>( 00457 positionBuffer->lock(HardwareBuffer::HBL_READ_ONLY)); 00458 00459 // Iterate over the triangles 00460 EdgeData::TriangleList::iterator i, iend; 00461 iend = triangles.end(); 00462 for (i = triangles.begin(); i != iend; ++i) 00463 { 00464 Triangle& t = *i; 00465 // Only update tris which are using this vertex set 00466 if (t.vertexSet == vertexSet) 00467 { 00468 size_t offset = t.vertIndex[0]*3; 00469 Vector3 v1(pVert + offset); 00470 00471 offset = t.vertIndex[1]*3; 00472 Vector3 v2(pVert + offset); 00473 00474 offset = t.vertIndex[2]*3; 00475 Vector3 v3(pVert + offset); 00476 00477 t.normal = Math::calculateFaceNormal(v1, v2, v3); 00478 } 00479 } 00480 00481 00482 // unlock the buffer 00483 positionBuffer->unlock(); 00484 } 00485 //--------------------------------------------------------------------- 00486 void EdgeListBuilder::log(Log* l) 00487 { 00488 l->logMessage("EdgeListBuilder Log"); 00489 l->logMessage("-------------------"); 00490 l->logMessage("Number of vertex sets: " + StringConverter::toString(mVertexDataList.size())); 00491 l->logMessage("Number of index sets: " + StringConverter::toString(mIndexDataList.size())); 00492 00493 size_t i, j; 00494 // Log original vertex data 00495 for(i = 0; i < mVertexDataList.size(); ++i) 00496 { 00497 const VertexData* vData = mVertexDataList[i]; 00498 l->logMessage("."); 00499 l->logMessage("Original vertex set " + 00500 StringConverter::toString(i) + " - vertex count " + 00501 StringConverter::toString(vData->vertexCount)); 00502 const VertexElement* posElem = vData->vertexDeclaration->findElementBySemantic(VES_POSITION); 00503 HardwareVertexBufferSharedPtr vbuf = 00504 vData->vertexBufferBinding->getBuffer(posElem->getSource()); 00505 // lock the buffer for reading 00506 unsigned char* pBaseVertex = static_cast<unsigned char*>( 00507 vbuf->lock(HardwareBuffer::HBL_READ_ONLY)); 00508 Real* pReal; 00509 for (j = 0; j < vData->vertexCount; ++j) 00510 { 00511 posElem->baseVertexPointerToElement(pBaseVertex, &pReal); 00512 l->logMessage("Vertex " + StringConverter::toString(j) + 00513 ": (" + StringConverter::toString(pReal[0]) + 00514 ", " + StringConverter::toString(pReal[1]) + 00515 ", " + StringConverter::toString(pReal[2]) + ")"); 00516 pBaseVertex += vbuf->getVertexSize(); 00517 } 00518 vbuf->unlock(); 00519 } 00520 00521 // Log original index data 00522 for(i = 0; i < mIndexDataList.size(); i++) 00523 { 00524 const IndexData* iData = mIndexDataList[i]; 00525 l->logMessage("."); 00526 l->logMessage("Original triangle set " + 00527 StringConverter::toString(i) + " - index count " + 00528 StringConverter::toString(iData->indexCount) + " - " + 00529 "vertex set " + StringConverter::toString(mIndexDataVertexDataSetList[i]) + " - " + 00530 "operationType " + StringConverter::toString(mOperationTypeList[i])); 00531 // Get the indexes ready for reading 00532 unsigned short* p16Idx; 00533 unsigned int* p32Idx; 00534 00535 if (iData->indexBuffer->getType() == HardwareIndexBuffer::IT_32BIT) 00536 { 00537 p32Idx = static_cast<unsigned int*>( 00538 iData->indexBuffer->lock(HardwareBuffer::HBL_READ_ONLY)); 00539 } 00540 else 00541 { 00542 p16Idx = static_cast<unsigned short*>( 00543 iData->indexBuffer->lock(HardwareBuffer::HBL_READ_ONLY)); 00544 } 00545 00546 for (j = 0; j < iData->indexCount; ) 00547 { 00548 if (iData->indexBuffer->getType() == HardwareIndexBuffer::IT_32BIT) 00549 { 00550 if (mOperationTypeList[i] == RenderOperation::OT_TRIANGLE_LIST 00551 || j == 0) 00552 { 00553 l->logMessage("Triangle " + StringConverter::toString(j) + 00554 ": (" + StringConverter::toString(*p32Idx++) + 00555 ", " + StringConverter::toString(*p32Idx++) + 00556 ", " + StringConverter::toString(*p32Idx++) + ")"); 00557 j += 3; 00558 } 00559 else 00560 { 00561 l->logMessage("Triangle " + StringConverter::toString(j) + 00562 ": (" + StringConverter::toString(*p32Idx++) + ")"); 00563 j++; 00564 } 00565 } 00566 else 00567 { 00568 if (mOperationTypeList[i] == RenderOperation::OT_TRIANGLE_LIST 00569 || j == 0) 00570 { 00571 l->logMessage("Index " + StringConverter::toString(j) + 00572 ": (" + StringConverter::toString(*p16Idx++) + 00573 ", " + StringConverter::toString(*p16Idx++) + 00574 ", " + StringConverter::toString(*p16Idx++) + ")"); 00575 j += 3; 00576 } 00577 else 00578 { 00579 l->logMessage("Triangle " + StringConverter::toString(j) + 00580 ": (" + StringConverter::toString(*p16Idx++) + ")"); 00581 j++; 00582 } 00583 } 00584 00585 00586 } 00587 00588 iData->indexBuffer->unlock(); 00589 00590 00591 // Log common vertex list 00592 l->logMessage("."); 00593 l->logMessage("Common vertex list - vertex count " + 00594 StringConverter::toString(mVertices.size())); 00595 for (i = 0; i < mVertices.size(); ++i) 00596 { 00597 CommonVertex& c = mVertices[i]; 00598 l->logMessage("Common vertex " + StringConverter::toString(i) + 00599 ": (vertexSet=" + StringConverter::toString(c.vertexSet) + 00600 ", originalIndex=" + StringConverter::toString(c.index) + 00601 ", position=" + StringConverter::toString(c.position)); 00602 } 00603 } 00604 00605 } 00606 00607 00608 00609 } 00610
Copyright © 2002-2003 by The OGRE Team
Last modified Fri May 14 23:22:07 2004