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-2002 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 00027 // The algorithm in this file is based heavily on: 00028 /* 00029 * Progressive Mesh type Polygon Reduction Algorithm 00030 * by Stan Melax (c) 1998 00031 */ 00032 00033 #include "OgreProgressiveMesh.h" 00034 #include "OgreString.h" 00035 #include "OgreHardwareBufferManager.h" 00036 #include <algorithm> 00037 00038 #include <iostream> 00039 00040 #if OGRE_DEBUG_MODE 00041 std::ofstream ofdebug; 00042 #endif 00043 00044 namespace Ogre { 00045 #define NEVER_COLLAPSE_COST 99999.9f 00046 00047 00050 struct vectorLess 00051 { 00052 _OgreExport bool operator()(const Vector3& v1, const Vector3& v2) const 00053 { 00054 if (v1.x < v2.x) return true; 00055 if (v1.x == v2.x && v1.y < v2.y) return true; 00056 if (v1.x == v2.x && v1.y == v2.y && v1.z < v2.z) return true; 00057 00058 return false; 00059 } 00060 }; 00061 //--------------------------------------------------------------------- 00062 ProgressiveMesh::ProgressiveMesh(const VertexData* vertexData, 00063 const IndexData* indexData) 00064 { 00065 addWorkingData(vertexData, indexData); 00066 mpVertexData = vertexData; 00067 mpIndexData = indexData; 00068 mWorstCosts.resize(vertexData->vertexCount); 00069 00070 00071 00072 } 00073 //--------------------------------------------------------------------- 00074 ProgressiveMesh::~ProgressiveMesh() 00075 { 00076 } 00077 //--------------------------------------------------------------------- 00078 void ProgressiveMesh::addExtraVertexPositionBuffer(const VertexData* vertexData) 00079 { 00080 addWorkingData(vertexData, mpIndexData); 00081 } 00082 //--------------------------------------------------------------------- 00083 void ProgressiveMesh::build(ushort numLevels, LODFaceList* outList, 00084 VertexReductionQuota quota, Real reductionValue) 00085 { 00086 IndexData* newLod; 00087 00088 computeAllCosts(); 00089 00090 #if OGRE_DEBUG_MODE 00091 dumpContents("pm_before.log"); 00092 #endif 00093 00094 // Init 00095 mCurrNumIndexes = mpIndexData->indexCount; 00096 size_t numVerts, numCollapses; 00097 // Use COMMON vert count, not original vert count 00098 // Since collapsing 1 common vert position is equivalent to collapsing them all 00099 numVerts = mNumCommonVertices; 00100 00101 #if OGRE_DEBUG_MODE 00102 ofdebug.open("progressivemesh.log"); 00103 #endif 00104 numCollapses = 0; 00105 bool abandon = false; 00106 while (numLevels--) 00107 { 00108 // NB idf 'abandon' is set, we stop reducing 00109 // However, we still bake the number of LODs requested, even if it 00110 // means they are the same 00111 if (!abandon) 00112 { 00113 if (quota == VRQ_PROPORTIONAL) 00114 { 00115 numCollapses = numVerts * reductionValue; 00116 } 00117 else 00118 { 00119 numCollapses = reductionValue; 00120 } 00121 // Minimum 3 verts! 00122 if ( (numVerts - numCollapses) < 3) 00123 numCollapses = numVerts - 3; 00124 // Store new number of verts 00125 numVerts = numVerts - numCollapses; 00126 00127 while(numCollapses-- && !abandon) 00128 { 00129 size_t nextIndex = getNextCollapser(); 00130 // Collapse on every buffer 00131 WorkingDataList::iterator idata, idataend; 00132 idataend = mWorkingData.end(); 00133 for (idata = mWorkingData.begin(); idata != idataend; ++idata) 00134 { 00135 PMVertex* collapser = &( idata->mVertList.at( nextIndex ) ); 00136 // This will reduce mCurrNumIndexes and recalc costs as required 00137 if (collapser->collapseTo == NULL) 00138 { 00139 // Must have run out of valid collapsables 00140 abandon = true; 00141 break; 00142 } 00143 #if OGRE_DEBUG_MODE 00144 ofdebug << "Collapsing index " << (unsigned int)collapser->index << "(border: "<< collapser->isBorder() << 00145 ") to " << (unsigned int)collapser->collapseTo->index << "(border: "<< collapser->collapseTo->isBorder() << 00146 ")" << std::endl; 00147 #endif 00148 assert(collapser->collapseTo->removed == false); 00149 00150 collapse(collapser); 00151 } 00152 00153 } 00154 } 00155 #if OGRE_DEBUG_MODE 00156 char logname[20]; 00157 sprintf(logname, "pm_level%d.log", numLevels); 00158 dumpContents(logname); 00159 #endif 00160 00161 // Bake a new LOD and add it to the list 00162 newLod = new IndexData(); 00163 bakeNewLOD(newLod); 00164 outList->push_back(newLod); 00165 00166 } 00167 00168 00169 00170 } 00171 //--------------------------------------------------------------------- 00172 void ProgressiveMesh::addWorkingData(const VertexData * vertexData, 00173 const IndexData * indexData) 00174 { 00175 // Insert blank working data, then fill 00176 mWorkingData.push_back(PMWorkingData()); 00177 00178 PMWorkingData& work = mWorkingData.back(); 00179 00180 // Build vertex list 00181 // Resize face list (this will always be this big) 00182 work.mFaceVertList.resize(vertexData->vertexCount); 00183 // Also resize common vert list to max, to avoid reallocations 00184 work.mVertList.resize(vertexData->vertexCount); 00185 00186 // locate position element & hte buffer to go with it 00187 const VertexElement* posElem = vertexData->vertexDeclaration->findElementBySemantic(VES_POSITION); 00188 HardwareVertexBufferSharedPtr vbuf = 00189 vertexData->vertexBufferBinding->getBuffer(posElem->getSource()); 00190 // lock the buffer for reading 00191 unsigned char* pVertex = static_cast<unsigned char*>( 00192 vbuf->lock(HardwareBuffer::HBL_READ_ONLY)); 00193 Real* pReal; 00194 Vector3 pos; 00195 // Map for identifying duplicate position vertices 00196 typedef std::map<Vector3, size_t, vectorLess> CommonVertexMap; 00197 CommonVertexMap commonVertexMap; 00198 CommonVertexMap::iterator iCommonVertex; 00199 size_t numCommon = 0; 00200 size_t i = 0; 00201 for (i = 0; i < vertexData->vertexCount; ++i, pVertex += vbuf->getVertexSize()) 00202 { 00203 posElem->baseVertexPointerToElement(pVertex, &pReal); 00204 00205 pos.x = *pReal++; 00206 pos.y = *pReal++; 00207 pos.z = *pReal++; 00208 00209 // Try to find this position in the existing map 00210 iCommonVertex = commonVertexMap.find(pos); 00211 if (iCommonVertex == commonVertexMap.end()) 00212 { 00213 // Doesn't exist, so create it 00214 PMVertex* commonVert = &(work.mVertList[numCommon]); 00215 commonVert->setDetails(pos, numCommon); 00216 commonVert->removed = false; 00217 commonVert->toBeRemoved = false; 00218 commonVert->seam = false; 00219 00220 // Enter it in the map 00221 commonVertexMap.insert(CommonVertexMap::value_type(pos, numCommon) ); 00222 // Increment common index 00223 ++numCommon; 00224 00225 work.mFaceVertList[i].commonVertex = commonVert; 00226 work.mFaceVertList[i].realIndex = i; 00227 } 00228 else 00229 { 00230 // Exists already, reference it 00231 PMVertex* existingVert = &(work.mVertList[iCommonVertex->second]); 00232 work.mFaceVertList[i].commonVertex = existingVert; 00233 work.mFaceVertList[i].realIndex = i; 00234 00235 // Also tag original as a seam since duplicates at this location 00236 work.mFaceVertList[i].commonVertex->seam = true; 00237 00238 } 00239 00240 } 00241 vbuf->unlock(); 00242 00243 mNumCommonVertices = numCommon; 00244 00245 // Build tri list 00246 size_t numTris = indexData->indexCount / 3; 00247 unsigned short* pShort; 00248 unsigned int* pInt; 00249 HardwareIndexBufferSharedPtr ibuf = indexData->indexBuffer; 00250 bool use32bitindexes = (ibuf->getType() == HardwareIndexBuffer::IT_32BIT); 00251 if (use32bitindexes) 00252 { 00253 pInt = static_cast<unsigned int*>( 00254 ibuf->lock(HardwareBuffer::HBL_READ_ONLY)); 00255 } 00256 else 00257 { 00258 pShort = static_cast<unsigned short*>( 00259 ibuf->lock(HardwareBuffer::HBL_READ_ONLY)); 00260 } 00261 work.mTriList.resize(numTris); // assumed tri list 00262 for (i = 0; i < numTris; ++i) 00263 { 00264 PMFaceVertex *v0, *v1, *v2; 00265 // use 32-bit index always since we're not storing 00266 unsigned int vindex = use32bitindexes? *pInt++ : *pShort++; 00267 v0 = &(work.mFaceVertList[vindex]); 00268 vindex = use32bitindexes? *pInt++ : *pShort++; 00269 v1 = &(work.mFaceVertList[vindex]); 00270 vindex = use32bitindexes? *pInt++ : *pShort++; 00271 v2 = &(work.mFaceVertList[vindex]); 00272 00273 work.mTriList[i].setDetails(i, v0, v1, v2); 00274 00275 work.mTriList[i].removed = false; 00276 00277 } 00278 ibuf->unlock(); 00279 00280 } 00281 //--------------------------------------------------------------------- 00282 Real ProgressiveMesh::computeEdgeCollapseCost(PMVertex *src, PMVertex *dest) 00283 { 00284 // if we collapse edge uv by moving src to dest then how 00285 // much different will the model change, i.e. how much "error". 00286 // The method of determining cost was designed in order 00287 // to exploit small and coplanar regions for 00288 // effective polygon reduction. 00289 Vector3 edgeVector = src->position - dest->position; 00290 00291 Real cost; 00292 Real curvature = 0.001f; 00293 00294 // find the "sides" triangles that are on the edge uv 00295 PMVertex::FaceList sides; 00296 PMVertex::FaceList::iterator srcface, srcfaceEnd; 00297 srcfaceEnd = src->face.end(); 00298 // Iterate over src's faces and find 'sides' of the shared edge which is being collapsed 00299 for(srcface = src->face.begin(); srcface != srcfaceEnd; ++srcface) 00300 { 00301 // Check if this tri also has dest in it (shared edge) 00302 if( (*srcface)->hasCommonVertex(dest) ) 00303 { 00304 sides.insert(*srcface); 00305 } 00306 } 00307 00308 // Special cases 00309 // If we're looking at a border vertex 00310 if(src->isBorder()) 00311 { 00312 if (sides.size() > 1) 00313 { 00314 // src is on a border, but the src-dest edge has more than one tri on it 00315 // So it must be collapsing inwards 00316 // Mark as very high-value cost 00317 // curvature = 1.0f; 00318 cost = 1.0f; 00319 } 00320 else 00321 { 00322 // Collapsing ALONG a border 00323 // We can't use curvature to measure the effect on the model 00324 // Instead, see what effect it has on 'pulling' the other border edges 00325 // The more colinear, the less effect it will have 00326 // So measure the 'kinkiness' (for want of a better term) 00327 // Normally there can be at most 1 other border edge attached to this 00328 // However in weird cases there may be more, so find the worst 00329 Vector3 collapseEdge, otherBorderEdge; 00330 Real kinkiness, maxKinkiness; 00331 PMVertex::NeighborList::iterator n, nend; 00332 nend = src->neighbor.end(); 00333 maxKinkiness = 0.0f; 00334 edgeVector.normalise(); 00335 collapseEdge = edgeVector; 00336 for (n = src->neighbor.begin(); n != nend; ++n) 00337 { 00338 if (*n != dest && (*n)->isManifoldEdgeWith(src)) 00339 { 00340 otherBorderEdge = src->position - (*n)->position; 00341 otherBorderEdge.normalise(); 00342 // This time, the nearer the dot is to -1, the better, because that means 00343 // the edges are opposite each other, therefore less kinkiness 00344 // Scale into [0..1] 00345 kinkiness = (otherBorderEdge.dotProduct(collapseEdge) + 1.002f) * 0.5f; 00346 maxKinkiness = std::max(kinkiness, maxKinkiness); 00347 00348 } 00349 } 00350 00351 cost = maxKinkiness; 00352 00353 } 00354 } 00355 else // not a border 00356 { 00357 00358 // Standard inner vertex 00359 // Calculate curvature 00360 // use the triangle facing most away from the sides 00361 // to determine our curvature term 00362 // Iterate over src's faces again 00363 for(srcface = src->face.begin(); srcface != srcfaceEnd; ++srcface) 00364 { 00365 Real mincurv = 1.0f; // curve for face i and closer side to it 00366 // Iterate over the sides 00367 PMVertex::FaceList::iterator sidesFace, sidesFaceEnd; 00368 sidesFaceEnd = sides.end(); 00369 for(sidesFace = sides.begin(); sidesFace != sidesFaceEnd; ++sidesFace) 00370 { 00371 // Dot product of face normal gives a good delta angle 00372 Real dotprod = (*srcface)->normal.dotProduct( (*sidesFace)->normal ); 00373 // NB we do (1-..) to invert curvature where 1 is high curvature [0..1] 00374 // Whilst dot product is high when angle difference is low 00375 mincurv = std::min(mincurv,(1.002f - dotprod) * 0.5f); 00376 } 00377 curvature = std::max(curvature, mincurv); 00378 } 00379 cost = curvature; 00380 } 00381 00382 // check for texture seam ripping 00383 if (src->seam && !dest->seam) 00384 { 00385 cost = 1.0f; 00386 } 00387 00388 // Check for singular triangle destruction 00389 // If src and dest both only have 1 triangle (and it must be a shared one) 00390 // then this would destroy the shape, so don't do this 00391 if (src->face.size() == 1 && dest->face.size() == 1) 00392 { 00393 cost = NEVER_COLLAPSE_COST; 00394 } 00395 00396 00397 /* 00398 // Degenerate case check 00399 // Are we going to invert a face normal of one of the neighbouring faces? 00400 // Can occur when we have a very small remaining edge and collapse crosses it 00401 // Look for a face normal changing by > 90 degrees 00402 for(srcface = src->face.begin(); srcface != srcfaceEnd; ++srcface) 00403 { 00404 // Ignore the deleted faces (those including src & dest) 00405 if( !(*srcface)->hasCommonVertex(dest) ) 00406 { 00407 // Test the new face normal 00408 PMVertex *v0, *v1, *v2; 00409 // Replace src with dest wherever it is 00410 v0 = ( (*srcface)->vertex[0]->commonVertex == src) ? dest : (*srcface)->vertex[0]->commonVertex; 00411 v1 = ( (*srcface)->vertex[1]->commonVertex == src) ? dest : (*srcface)->vertex[1]->commonVertex; 00412 v2 = ( (*srcface)->vertex[2]->commonVertex == src) ? dest : (*srcface)->vertex[2]->commonVertex; 00413 00414 // Cross-product 2 edges 00415 Vector3 e1 = v1->position - v0->position; 00416 Vector3 e2 = v2->position - v1->position; 00417 00418 Vector3 newNormal = e1.crossProduct(e2); 00419 newNormal.normalise(); 00420 00421 // Dot old and new face normal 00422 // If < 0 then more than 90 degree difference 00423 if (newNormal.dotProduct( (*srcface)->normal ) < 0.0f ) 00424 { 00425 // Don't do it! 00426 cost = NEVER_COLLAPSE_COST; 00427 break; // No point continuing 00428 } 00429 00430 00431 } 00432 } 00433 */ 00434 00435 00436 assert (cost >= 0); 00437 return cost; 00438 } 00439 //--------------------------------------------------------------------- 00440 void ProgressiveMesh::initialiseEdgeCollapseCosts(void) 00441 { 00442 WorkingDataList::iterator i, iend; 00443 iend = mWorkingData.end(); 00444 for (i = mWorkingData.begin(); i != iend; ++i) 00445 { 00446 CommonVertexList::iterator v, vend; 00447 vend = i->mVertList.end(); 00448 for (v = i->mVertList.begin(); v != vend; ++v) 00449 { 00450 v->collapseTo = NULL; 00451 v->collapseCost = NEVER_COLLAPSE_COST; 00452 } 00453 } 00454 00455 00456 } 00457 //--------------------------------------------------------------------- 00458 Real ProgressiveMesh::computeEdgeCostAtVertexForBuffer(WorkingDataList::iterator idata, size_t vertIndex) 00459 { 00460 // compute the edge collapse cost for all edges that start 00461 // from vertex v. Since we are only interested in reducing 00462 // the object by selecting the min cost edge at each step, we 00463 // only cache the cost of the least cost edge at this vertex 00464 // (in member variable collapse) as well as the value of the 00465 // cost (in member variable objdist). 00466 00467 CommonVertexList::iterator v = idata->mVertList.begin(); 00468 v += vertIndex; 00469 00470 if(v->neighbor.empty()) { 00471 // v doesn't have neighbors so nothing to collapse 00472 v->notifyRemoved(); 00473 return v->collapseCost; 00474 } 00475 00476 // Init metrics 00477 v->collapseCost = NEVER_COLLAPSE_COST; 00478 v->collapseTo = NULL; 00479 00480 // search all neighboring edges for "least cost" edge 00481 PMVertex::NeighborList::iterator n, nend; 00482 nend = v->neighbor.end(); 00483 Real cost; 00484 for(n = v->neighbor.begin(); n != nend; ++n) 00485 { 00486 cost = computeEdgeCollapseCost(&(*v), *n); 00487 if( (!v->collapseTo) || cost < v->collapseCost) 00488 { 00489 v->collapseTo = *n; // candidate for edge collapse 00490 v->collapseCost = cost; // cost of the collapse 00491 } 00492 } 00493 00494 return v->collapseCost; 00495 } 00496 //--------------------------------------------------------------------- 00497 void ProgressiveMesh::computeAllCosts(void) 00498 { 00499 initialiseEdgeCollapseCosts(); 00500 size_t i; 00501 for (i = 0; i < mpVertexData->vertexCount; ++i) 00502 { 00503 computeEdgeCostAtVertex(i); 00504 } 00505 } 00506 //--------------------------------------------------------------------- 00507 void ProgressiveMesh::collapse(ProgressiveMesh::PMVertex *src) 00508 { 00509 PMVertex *dest = src->collapseTo; 00510 std::set<PMVertex*> recomputeSet; 00511 00512 // Abort if we're never supposed to collapse 00513 if (src->collapseCost == NEVER_COLLAPSE_COST) 00514 return; 00515 00516 // Remove this vertex from the running for the next check 00517 src->collapseTo = NULL; 00518 src->collapseCost = NEVER_COLLAPSE_COST; 00519 mWorstCosts[src->index] = NEVER_COLLAPSE_COST; 00520 00521 // Collapse the edge uv by moving vertex u onto v 00522 // Actually remove tris on uv, then update tris that 00523 // have u to have v, and then remove u. 00524 if(!dest) { 00525 // src is a vertex all by itself 00526 #if OGRE_DEBUG_MODE 00527 ofdebug << "Aborting collapse, orphan vertex. " << std::endl; 00528 #endif 00529 return; 00530 } 00531 00532 // Add dest and all the neighbours of source and dest to recompute list 00533 recomputeSet.insert(dest); 00534 PMVertex::NeighborList::iterator n, nend; 00535 nend = src->neighbor.end(); 00536 00537 PMVertex* temp; 00538 00539 for(n = src->neighbor.begin(); n != nend; ++n) 00540 { 00541 temp = *n; 00542 recomputeSet.insert( *n ); 00543 } 00544 nend = dest->neighbor.end(); 00545 for(n = dest->neighbor.begin(); n != nend; ++n) 00546 { 00547 temp = *n; 00548 recomputeSet.insert( *n ); 00549 } 00550 00551 // delete triangles on edge src-dest 00552 // Notify others to replace src with dest 00553 PMVertex::FaceList::iterator f, fend; 00554 fend = src->face.end(); 00555 // Queue of faces for removal / replacement 00556 // prevents us screwing up the iterators while we parse 00557 PMVertex::FaceList faceRemovalList, faceReplacementList; 00558 for(f = src->face.begin(); f != fend; ++f) 00559 { 00560 if((*f)->hasCommonVertex(dest)) 00561 { 00562 // Tri is on src-dest therefore is gone 00563 faceRemovalList.insert(*f); 00564 // Reduce index count by 3 (useful for quick allocation later) 00565 mCurrNumIndexes -= 3; 00566 } 00567 else 00568 { 00569 // Only src involved, replace with dest 00570 faceReplacementList.insert(*f); 00571 } 00572 } 00573 00574 src->toBeRemoved = true; 00575 // Replace all the faces queued for replacement 00576 for(f = faceReplacementList.begin(); f != faceReplacementList.end(); ++f) 00577 { 00578 /* Locate the face vertex which corresponds with the common 'dest' vertex 00579 To to this, find a removed face which has the FACE vertex corresponding with 00580 src, and use it's FACE vertex version of dest. 00581 */ 00582 PMFaceVertex* srcFaceVert = (*f)->getFaceVertexFromCommon(src); 00583 PMFaceVertex* destFaceVert = NULL; 00584 PMVertex::FaceList::iterator iremoved; 00585 for(iremoved = faceRemovalList.begin(); iremoved != faceRemovalList.end(); ++iremoved) 00586 { 00587 //if ( (*iremoved)->hasFaceVertex(srcFaceVert) ) 00588 //{ 00589 destFaceVert = (*iremoved)->getFaceVertexFromCommon(dest); 00590 //} 00591 } 00592 00593 assert(destFaceVert); 00594 00595 #if OGRE_DEBUG_MODE 00596 ofdebug << "Replacing vertex on face " << (unsigned int)(*f)->index << std::endl; 00597 #endif 00598 (*f)->replaceVertex(srcFaceVert, destFaceVert); 00599 } 00600 // Remove all the faces queued for removal 00601 for(f = faceRemovalList.begin(); f != faceRemovalList.end(); ++f) 00602 { 00603 #if OGRE_DEBUG_MODE 00604 ofdebug << "Removing face " << (unsigned int)(*f)->index << std::endl; 00605 #endif 00606 (*f)->notifyRemoved(); 00607 } 00608 00609 // Notify the vertex that it is gone 00610 src->notifyRemoved(); 00611 00612 // recompute costs 00613 std::set<PMVertex*>::iterator irecomp, irecompend; 00614 irecompend = recomputeSet.end(); 00615 for (irecomp = recomputeSet.begin(); irecomp != irecompend; ++irecomp) 00616 { 00617 temp = (*irecomp); 00618 computeEdgeCostAtVertex( (*irecomp)->index ); 00619 } 00620 00621 } 00622 //--------------------------------------------------------------------- 00623 void ProgressiveMesh::computeEdgeCostAtVertex(size_t vertIndex) 00624 { 00625 // Call computer for each buffer on this vertex 00626 Real worstCost = -0.01f; 00627 WorkingDataList::iterator i, iend; 00628 iend = mWorkingData.end(); 00629 for (i = mWorkingData.begin(); i != iend; ++i) 00630 { 00631 worstCost = std::max(worstCost, 00632 computeEdgeCostAtVertexForBuffer(i, vertIndex)); 00633 } 00634 // Save the worst cost 00635 mWorstCosts[vertIndex] = worstCost; 00636 } 00637 //--------------------------------------------------------------------- 00638 size_t ProgressiveMesh::getNextCollapser(void) 00639 { 00640 // Scan 00641 // Not done as a sort because want to keep the lookup simple for now 00642 Real bestVal = NEVER_COLLAPSE_COST; 00643 size_t i, bestIndex; 00644 bestIndex = 0; // NB this is ok since if nothing is better than this, nothing will collapse 00645 for (i = 0; i < mNumCommonVertices; ++i) 00646 { 00647 if (mWorstCosts[i] < bestVal) 00648 { 00649 bestVal = mWorstCosts[i]; 00650 bestIndex = i; 00651 } 00652 } 00653 return bestIndex; 00654 } 00655 //--------------------------------------------------------------------- 00656 void ProgressiveMesh::bakeNewLOD(IndexData* pData) 00657 { 00658 assert(mCurrNumIndexes > 0 && "No triangles to bake!"); 00659 // Zip through the tri list of any working data copy and bake 00660 pData->indexCount = mCurrNumIndexes; 00661 pData->indexStart = 0; 00662 // Base size of indexes on original 00663 bool use32bitindexes = 00664 (mpIndexData->indexBuffer->getType() == HardwareIndexBuffer::IT_32BIT); 00665 00666 // Create index buffer, we don't need to read it back or modify it a lot 00667 pData->indexBuffer = HardwareBufferManager::getSingleton().createIndexBuffer( 00668 use32bitindexes? HardwareIndexBuffer::IT_32BIT : HardwareIndexBuffer::IT_16BIT, 00669 pData->indexCount, HardwareBuffer::HBU_STATIC_WRITE_ONLY, false); 00670 00671 unsigned short* pShort; 00672 unsigned int* pInt; 00673 if (use32bitindexes) 00674 { 00675 pInt = static_cast<unsigned int*>( 00676 pData->indexBuffer->lock( 0, 00677 pData->indexBuffer->getSizeInBytes(), 00678 HardwareBuffer::HBL_DISCARD)); 00679 } 00680 else 00681 { 00682 pShort = static_cast<unsigned short*>( 00683 pData->indexBuffer->lock( 0, 00684 pData->indexBuffer->getSizeInBytes(), 00685 HardwareBuffer::HBL_DISCARD)); 00686 } 00687 TriangleList::iterator tri, triend; 00688 // Use the first working data buffer, they are all the same index-wise 00689 WorkingDataList::iterator pWork = mWorkingData.begin(); 00690 triend = pWork->mTriList.end(); 00691 for (tri = pWork->mTriList.begin(); tri != triend; ++tri) 00692 { 00693 if (!tri->removed) 00694 { 00695 if (use32bitindexes) 00696 { 00697 *pInt++ = static_cast<unsigned int>(tri->vertex[0]->realIndex); 00698 *pInt++ = static_cast<unsigned int>(tri->vertex[1]->realIndex); 00699 *pInt++ = static_cast<unsigned int>(tri->vertex[2]->realIndex); 00700 } 00701 else 00702 { 00703 *pShort++ = static_cast<unsigned short>(tri->vertex[0]->realIndex); 00704 *pShort++ = static_cast<unsigned short>(tri->vertex[1]->realIndex); 00705 *pShort++ = static_cast<unsigned short>(tri->vertex[2]->realIndex); 00706 } 00707 } 00708 } 00709 pData->indexBuffer->unlock(); 00710 00711 } 00712 //--------------------------------------------------------------------- 00713 ProgressiveMesh::PMTriangle::PMTriangle() : removed(false) 00714 { 00715 } 00716 //--------------------------------------------------------------------- 00717 void ProgressiveMesh::PMTriangle::setDetails(size_t newindex, 00718 ProgressiveMesh::PMFaceVertex *v0, ProgressiveMesh::PMFaceVertex *v1, 00719 ProgressiveMesh::PMFaceVertex *v2) 00720 { 00721 assert(v0!=v1 && v1!=v2 && v2!=v0); 00722 00723 index = newindex; 00724 vertex[0]=v0; 00725 vertex[1]=v1; 00726 vertex[2]=v2; 00727 00728 computeNormal(); 00729 00730 // Add tri to vertices 00731 // Also tell vertices they are neighbours 00732 for(int i=0;i<3;i++) { 00733 vertex[i]->commonVertex->face.insert(this); 00734 for(int j=0;j<3;j++) if(i!=j) { 00735 vertex[i]->commonVertex->neighbor.insert(vertex[j]->commonVertex); 00736 } 00737 } 00738 } 00739 //--------------------------------------------------------------------- 00740 void ProgressiveMesh::PMTriangle::notifyRemoved(void) 00741 { 00742 int i; 00743 for(i=0; i<3; i++) { 00744 // remove this tri from the vertices 00745 if(vertex[i]) vertex[i]->commonVertex->face.erase(this); 00746 } 00747 for(i=0; i<3; i++) { 00748 int i2 = (i+1)%3; 00749 if(!vertex[i] || !vertex[i2]) continue; 00750 // Check remaining vertices and remove if not neighbours anymore 00751 // NB May remain neighbours if other tris link them 00752 vertex[i ]->commonVertex->removeIfNonNeighbor(vertex[i2]->commonVertex); 00753 vertex[i2]->commonVertex->removeIfNonNeighbor(vertex[i ]->commonVertex); 00754 } 00755 00756 removed = true; 00757 } 00758 //--------------------------------------------------------------------- 00759 bool ProgressiveMesh::PMTriangle::hasCommonVertex(ProgressiveMesh::PMVertex *v) const 00760 { 00761 return (v == vertex[0]->commonVertex || 00762 v == vertex[1]->commonVertex || 00763 v == vertex[2]->commonVertex); 00764 } 00765 //--------------------------------------------------------------------- 00766 bool ProgressiveMesh::PMTriangle::hasFaceVertex(ProgressiveMesh::PMFaceVertex *v) const 00767 { 00768 return (v == vertex[0] || 00769 v == vertex[1] || 00770 v == vertex[2]); 00771 } 00772 //--------------------------------------------------------------------- 00773 ProgressiveMesh::PMFaceVertex* 00774 ProgressiveMesh::PMTriangle::getFaceVertexFromCommon(ProgressiveMesh::PMVertex* commonVert) 00775 { 00776 if (vertex[0]->commonVertex == commonVert) return vertex[0]; 00777 if (vertex[1]->commonVertex == commonVert) return vertex[1]; 00778 if (vertex[2]->commonVertex == commonVert) return vertex[2]; 00779 00780 return NULL; 00781 00782 } 00783 //--------------------------------------------------------------------- 00784 void ProgressiveMesh::PMTriangle::computeNormal() 00785 { 00786 Vector3 v0=vertex[0]->commonVertex->position; 00787 Vector3 v1=vertex[1]->commonVertex->position; 00788 Vector3 v2=vertex[2]->commonVertex->position; 00789 // Cross-product 2 edges 00790 Vector3 e1 = v1 - v0; 00791 Vector3 e2 = v2 - v1; 00792 00793 normal = e1.crossProduct(e2); 00794 normal.normalise(); 00795 } 00796 //--------------------------------------------------------------------- 00797 void ProgressiveMesh::PMTriangle::replaceVertex( 00798 ProgressiveMesh::PMFaceVertex *vold, ProgressiveMesh::PMFaceVertex *vnew) 00799 { 00800 assert(vold && vnew); 00801 assert(vold==vertex[0] || vold==vertex[1] || vold==vertex[2]); 00802 assert(vnew!=vertex[0] && vnew!=vertex[1] && vnew!=vertex[2]); 00803 if(vold==vertex[0]){ 00804 vertex[0]=vnew; 00805 } 00806 else if(vold==vertex[1]){ 00807 vertex[1]=vnew; 00808 } 00809 else { 00810 assert(vold==vertex[2]); 00811 vertex[2]=vnew; 00812 } 00813 int i; 00814 vold->commonVertex->face.erase(this); 00815 vnew->commonVertex->face.insert(this); 00816 for(i=0;i<3;i++) { 00817 vold->commonVertex->removeIfNonNeighbor(vertex[i]->commonVertex); 00818 vertex[i]->commonVertex->removeIfNonNeighbor(vold->commonVertex); 00819 } 00820 for(i=0;i<3;i++) { 00821 assert(vertex[i]->commonVertex->face.find(this) != vertex[i]->commonVertex->face.end()); 00822 for(int j=0;j<3;j++) if(i!=j) { 00823 #if OGRE_DEBUG_MODE 00824 ofdebug << "Adding vertex " << (unsigned int)vertex[j]->commonVertex->index << " to the neighbor list " 00825 "of vertex " << (unsigned int)vertex[i]->commonVertex->index << std::endl; 00826 #endif 00827 vertex[i]->commonVertex->neighbor.insert(vertex[j]->commonVertex); 00828 } 00829 } 00830 computeNormal(); 00831 } 00832 //--------------------------------------------------------------------- 00833 ProgressiveMesh::PMVertex::PMVertex() : removed(false) 00834 { 00835 } 00836 //--------------------------------------------------------------------- 00837 void ProgressiveMesh::PMVertex::setDetails(const Vector3& v, size_t newindex) 00838 { 00839 position = v; 00840 index = newindex; 00841 } 00842 //--------------------------------------------------------------------- 00843 void ProgressiveMesh::PMVertex::notifyRemoved(void) 00844 { 00845 NeighborList::iterator i, iend; 00846 iend = neighbor.end(); 00847 for (i = neighbor.begin(); i != iend; ++i) 00848 { 00849 // Remove me from neighbor 00850 (*i)->neighbor.erase(this); 00851 } 00852 removed = true; 00853 this->collapseTo = NULL; 00854 this->collapseCost = NEVER_COLLAPSE_COST; 00855 } 00856 //--------------------------------------------------------------------- 00857 bool ProgressiveMesh::PMVertex::isBorder() 00858 { 00859 // Look for edges which only have one tri attached, this is a border 00860 00861 NeighborList::iterator i, iend; 00862 iend = neighbor.end(); 00863 // Loop for each neighbor 00864 for(i = neighbor.begin(); i != iend; ++i) 00865 { 00866 // Count of tris shared between the edge between this and neighbor 00867 ushort count = 0; 00868 // Loop over each face, looking for shared ones 00869 FaceList::iterator j, jend; 00870 jend = face.end(); 00871 for(j = face.begin(); j != jend; ++j) 00872 { 00873 if((*j)->hasCommonVertex(*i)) 00874 { 00875 // Shared tri 00876 count ++; 00877 } 00878 } 00879 //assert(count>0); // Must be at least one! 00880 // This edge has only 1 tri on it, it's a border 00881 if(count == 1) 00882 return true; 00883 } 00884 return false; 00885 } 00886 //--------------------------------------------------------------------- 00887 bool ProgressiveMesh::PMVertex::isManifoldEdgeWith(ProgressiveMesh::PMVertex* v) 00888 { 00889 // Check the sides involving both these verts 00890 // If there is only 1 this is a manifold edge 00891 ushort sidesCount = 0; 00892 FaceList::iterator i, iend; 00893 iend = face.end(); 00894 for (i = face.begin(); i != iend; ++i) 00895 { 00896 if ((*i)->hasCommonVertex(v)) 00897 { 00898 sidesCount++; 00899 } 00900 } 00901 00902 return (sidesCount == 1); 00903 } 00904 //--------------------------------------------------------------------- 00905 void ProgressiveMesh::PMVertex::removeIfNonNeighbor(ProgressiveMesh::PMVertex *n) 00906 { 00907 // removes n from neighbor list if n isn't a neighbor. 00908 NeighborList::iterator i = neighbor.find(n); 00909 if (i == neighbor.end()) 00910 return; // Not in neighbor list anyway 00911 00912 FaceList::iterator f, fend; 00913 fend = face.end(); 00914 for(f = face.begin(); f != fend; ++f) 00915 { 00916 if((*f)->hasCommonVertex(n)) return; // Still a neighbor 00917 } 00918 00919 #if OGRE_DEBUG_MODE 00920 ofdebug << "Vertex " << (unsigned int)n->index << " is no longer a neighbour of vertex " << (unsigned int)this->index << 00921 " so has been removed from the latter's neighbor list." << std::endl; 00922 #endif 00923 neighbor.erase(n); 00924 00925 if (neighbor.empty() && !toBeRemoved) 00926 { 00927 // This vertex has been removed through isolation (collapsing around it) 00928 this->notifyRemoved(); 00929 } 00930 } 00931 //--------------------------------------------------------------------- 00932 void ProgressiveMesh::dumpContents(const String& log) 00933 { 00934 std::ofstream ofdump(log); 00935 00936 // Just dump 1st working data for now 00937 WorkingDataList::iterator worki = mWorkingData.begin(); 00938 00939 CommonVertexList::iterator vi, vend; 00940 vend = worki->mVertList.end(); 00941 ofdump << "-------== VERTEX LIST ==-----------------" << std::endl; 00942 size_t i; 00943 for (vi = worki->mVertList.begin(), i = 0; i < mNumCommonVertices; ++vi, ++i) 00944 { 00945 ofdump << "Vertex " << (unsigned int)vi->index << " pos: " << vi->position << " removed: " 00946 << vi->removed << " isborder: " << vi->isBorder() << std::endl; 00947 ofdump << " Faces:" << std::endl; 00948 PMVertex::FaceList::iterator f, fend; 00949 fend = vi->face.end(); 00950 for(f = vi->face.begin(); f != fend; ++f) 00951 { 00952 ofdump << " Triangle index " << (unsigned int)(*f)->index << std::endl; 00953 } 00954 ofdump << " Neighbours:" << std::endl; 00955 PMVertex::NeighborList::iterator n, nend; 00956 nend = vi->neighbor.end(); 00957 for (n = vi->neighbor.begin(); n != nend; ++n) 00958 { 00959 ofdump << " Vertex index " << (unsigned int)(*n)->index << std::endl; 00960 } 00961 00962 } 00963 00964 TriangleList::iterator ti, tend; 00965 tend = worki->mTriList.end(); 00966 ofdump << "-------== TRIANGLE LIST ==-----------------" << std::endl; 00967 for(ti = worki->mTriList.begin(); ti != tend; ++ti) 00968 { 00969 ofdump << "Triangle " << (unsigned int)ti->index << " norm: " << ti->normal << " removed: " << ti->removed << std::endl; 00970 ofdump << " Vertex 0: " << (unsigned int)ti->vertex[0]->realIndex << std::endl; 00971 ofdump << " Vertex 1: " << (unsigned int)ti->vertex[1]->realIndex << std::endl; 00972 ofdump << " Vertex 2: " << (unsigned int)ti->vertex[2]->realIndex << std::endl; 00973 } 00974 00975 ofdump << "-------== COLLAPSE COST LIST ==-----------------" << std::endl; 00976 for (size_t ci = 0; ci < mNumCommonVertices; ++ci) 00977 { 00978 ofdump << "Vertex " << (unsigned int)ci << ": " << mWorstCosts[ci] << std::endl; 00979 } 00980 00981 ofdump.close(); 00982 } 00983 00984 00985 }
Copyright © 2002-2003 by The OGRE Team
Last modified Wed Jan 21 00:10:23 2004