Main Page   Namespace List   Class Hierarchy   Alphabetical List   Compound List   File List   Namespace Members   Compound Members   File Members   Related Pages  

OgreProgressiveMesh.cpp

Go to the documentation of this file.
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