source: OGRE/trunk/ogrenew/OgreMain/src/OgreProgressiveMesh.cpp @ 657

Revision 657, 34.0 KB checked in by mattausch, 19 years ago (diff)

added ogre dependencies and patched ogre sources

Line 
1/*
2-----------------------------------------------------------------------------
3This source file is part of OGRE
4(Object-oriented Graphics Rendering Engine)
5For the latest info, see http://www.ogre3d.org/
6
7Copyright (c) 2000-2005 The OGRE Team
8Also see acknowledgements in Readme.html
9
10This program is free software; you can redistribute it and/or modify it under
11the terms of the GNU Lesser General Public License as published by the Free Software
12Foundation; either version 2 of the License, or (at your option) any later
13version.
14
15This program is distributed in the hope that it will be useful, but WITHOUT
16ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
17FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.
18
19You should have received a copy of the GNU Lesser General Public License along with
20this program; if not, write to the Free Software Foundation, Inc., 59 Temple
21Place - Suite 330, Boston, MA 02111-1307, USA, or go to
22http://www.gnu.org/copyleft/lesser.txt.
23-----------------------------------------------------------------------------
24*/
25#include "OgreStableHeaders.h"
26
27// The algorithm in this file is based heavily on:
28/*
29*  Progressive Mesh type Polygon Reduction Algorithm
30*  by Stan Melax (c) 1998
31*/
32
33#include "OgreProgressiveMesh.h"
34#include "OgreString.h"
35#include "OgreHardwareBufferManager.h"
36#include <algorithm>
37
38#include <iostream>
39
40#if OGRE_DEBUG_MODE
41std::ofstream ofdebug;
42#endif
43
44namespace Ogre {
45        #define NEVER_COLLAPSE_COST 99999.9f
46
47
48    /** Comparator for unique vertex list
49    */
50    struct vectorLess
51    {
52                _OgreExport bool operator()(const Vector3& v1, const Vector3& v2) const
53        {
54                        if (v1.x < v2.x) return true;
55                        if (v1.x == v2.x && v1.y < v2.y) return true;
56                        if (v1.x == v2.x && v1.y == v2.y && v1.z < v2.z) return true;
57
58                        return false;
59                }
60        };
61    //---------------------------------------------------------------------
62    ProgressiveMesh::ProgressiveMesh(const VertexData* vertexData,
63        const IndexData* indexData)
64    {
65        addWorkingData(vertexData, indexData);
66        mpVertexData = vertexData;
67        mpIndexData = indexData;
68        mWorstCosts.resize(vertexData->vertexCount);
69
70
71
72    }
73    //---------------------------------------------------------------------
74    ProgressiveMesh::~ProgressiveMesh()
75    {
76    }
77    //---------------------------------------------------------------------
78    void ProgressiveMesh::addExtraVertexPositionBuffer(const VertexData* vertexData)
79    {
80        addWorkingData(vertexData, mpIndexData);
81    }
82    //---------------------------------------------------------------------
83    void ProgressiveMesh::build(ushort numLevels, LODFaceList* outList,
84                        VertexReductionQuota quota, Real reductionValue)
85    {
86        IndexData* newLod;
87
88        computeAllCosts();
89
90#if OGRE_DEBUG_MODE
91                dumpContents("pm_before.log");
92#endif
93
94        // Init
95        mCurrNumIndexes = mpIndexData->indexCount;
96        size_t numVerts, numCollapses;
97        // Use COMMON vert count, not original vert count
98        // Since collapsing 1 common vert position is equivalent to collapsing them all
99        numVerts = mNumCommonVertices;
100               
101#if OGRE_DEBUG_MODE
102                ofdebug.open("progressivemesh.log");
103#endif
104                numCollapses = 0;
105                bool abandon = false;
106                while (numLevels--)
107        {
108            // NB idf 'abandon' is set, we stop reducing
109            // However, we still bake the number of LODs requested, even if it
110            // means they are the same
111            if (!abandon)
112            {
113                            if (quota == VRQ_PROPORTIONAL)
114                            {
115                                    numCollapses = numVerts * reductionValue;
116                            }
117                            else
118                            {
119                                    numCollapses = reductionValue;
120                            }
121                // Minimum 3 verts!
122                if ( (numVerts - numCollapses) < 3)
123                    numCollapses = numVerts - 3;
124                            // Store new number of verts
125                            numVerts = numVerts - numCollapses;
126
127                            while(numCollapses-- && !abandon)
128                {
129                    size_t nextIndex = getNextCollapser();
130                    // Collapse on every buffer
131                    WorkingDataList::iterator idata, idataend;
132                    idataend = mWorkingData.end();
133                    for (idata = mWorkingData.begin(); idata != idataend; ++idata)
134                    {
135                        PMVertex* collapser = &( idata->mVertList.at( nextIndex ) );
136                        // This will reduce mCurrNumIndexes and recalc costs as required
137                                            if (collapser->collapseTo == NULL)
138                                            {
139                                                    // Must have run out of valid collapsables
140                                                    abandon = true;
141                                                    break;
142                                            }
143#if OGRE_DEBUG_MODE
144                                            ofdebug << "Collapsing index " << (unsigned int)collapser->index << "(border: "<< collapser->isBorder() <<
145                                                    ") to " << (unsigned int)collapser->collapseTo->index << "(border: "<< collapser->collapseTo->isBorder() <<
146                                                    ")" << std::endl;
147#endif
148                                            assert(collapser->collapseTo->removed == false);
149
150                        collapse(collapser);
151                    }
152
153                }
154            }
155#if OGRE_DEBUG_MODE
156                        StringUtil::StrStreamType logname;
157                        logname << "pm_level" << numLevels << ".log";
158                        dumpContents(logname.str());
159#endif
160
161            // Bake a new LOD and add it to the list
162            newLod = new IndexData();
163            bakeNewLOD(newLod);
164            outList->push_back(newLod);
165                       
166        }
167
168
169
170    }
171    //---------------------------------------------------------------------
172    void ProgressiveMesh::addWorkingData(const VertexData * vertexData,
173        const IndexData * indexData)
174    {
175        // Insert blank working data, then fill
176        mWorkingData.push_back(PMWorkingData());
177
178        PMWorkingData& work = mWorkingData.back();
179
180        // Build vertex list
181                // Resize face list (this will always be this big)
182                work.mFaceVertList.resize(vertexData->vertexCount);
183                // Also resize common vert list to max, to avoid reallocations
184                work.mVertList.resize(vertexData->vertexCount);
185
186                // locate position element & hte buffer to go with it
187                const VertexElement* posElem = vertexData->vertexDeclaration->findElementBySemantic(VES_POSITION);
188                HardwareVertexBufferSharedPtr vbuf =
189                        vertexData->vertexBufferBinding->getBuffer(posElem->getSource());
190                // lock the buffer for reading
191                unsigned char* pVertex = static_cast<unsigned char*>(
192                        vbuf->lock(HardwareBuffer::HBL_READ_ONLY));
193                float* pFloat;
194                Vector3 pos;
195                // Map for identifying duplicate position vertices
196                typedef std::map<Vector3, size_t, vectorLess> CommonVertexMap;
197                CommonVertexMap commonVertexMap;
198                CommonVertexMap::iterator iCommonVertex;
199                size_t numCommon = 0;
200        size_t i = 0;
201        for (i = 0; i < vertexData->vertexCount; ++i, pVertex += vbuf->getVertexSize())
202        {
203                        posElem->baseVertexPointerToElement(pVertex, &pFloat);
204
205            pos.x = *pFloat++;
206            pos.y = *pFloat++;
207            pos.z = *pFloat++;
208
209                        // Try to find this position in the existing map
210                        iCommonVertex = commonVertexMap.find(pos);
211                        if (iCommonVertex == commonVertexMap.end())
212                        {
213                                // Doesn't exist, so create it
214                                PMVertex* commonVert = &(work.mVertList[numCommon]);
215                                commonVert->setDetails(pos, numCommon);
216                                commonVert->removed = false;
217                                commonVert->toBeRemoved = false;
218                                commonVert->seam = false;
219
220                                // Enter it in the map
221                                commonVertexMap.insert(CommonVertexMap::value_type(pos, numCommon) );
222                                // Increment common index
223                                ++numCommon;
224
225                                work.mFaceVertList[i].commonVertex = commonVert;
226                                work.mFaceVertList[i].realIndex = i;
227                        }
228                        else
229                        {
230                                // Exists already, reference it
231                                PMVertex* existingVert = &(work.mVertList[iCommonVertex->second]);
232                                work.mFaceVertList[i].commonVertex = existingVert;
233                                work.mFaceVertList[i].realIndex = i;
234
235                                // Also tag original as a seam since duplicates at this location
236                                work.mFaceVertList[i].commonVertex->seam = true;
237
238                        }
239                       
240        }
241                vbuf->unlock();
242
243                mNumCommonVertices = numCommon;
244
245        // Build tri list
246        size_t numTris = indexData->indexCount / 3;
247                unsigned short* pShort;
248                unsigned int* pInt;
249                HardwareIndexBufferSharedPtr ibuf = indexData->indexBuffer;
250                bool use32bitindexes = (ibuf->getType() == HardwareIndexBuffer::IT_32BIT);
251                if (use32bitindexes)
252                {
253                        pInt = static_cast<unsigned int*>(
254                                ibuf->lock(HardwareBuffer::HBL_READ_ONLY));
255                }
256                else
257                {
258                        pShort = static_cast<unsigned short*>(
259                                ibuf->lock(HardwareBuffer::HBL_READ_ONLY));
260                }
261        work.mTriList.resize(numTris); // assumed tri list
262        for (i = 0; i < numTris; ++i)
263        {
264                        PMFaceVertex *v0, *v1, *v2;
265                        // use 32-bit index always since we're not storing
266                        unsigned int vindex = use32bitindexes? *pInt++ : *pShort++;
267                        v0 = &(work.mFaceVertList[vindex]);
268                        vindex = use32bitindexes? *pInt++ : *pShort++;
269                        v1 = &(work.mFaceVertList[vindex]);
270                        vindex = use32bitindexes? *pInt++ : *pShort++;
271                        v2 = &(work.mFaceVertList[vindex]);
272
273                        work.mTriList[i].setDetails(i, v0, v1, v2);
274
275            work.mTriList[i].removed = false;
276
277        }
278                ibuf->unlock();
279
280    }
281    //---------------------------------------------------------------------
282    Real ProgressiveMesh::computeEdgeCollapseCost(PMVertex *src, PMVertex *dest)
283    {
284        // if we collapse edge uv by moving src to dest then how
285        // much different will the model change, i.e. how much "error".
286        // The method of determining cost was designed in order
287        // to exploit small and coplanar regions for
288        // effective polygon reduction.
289        Vector3 edgeVector = src->position - dest->position;
290
291        Real cost;
292                Real curvature = 0.001f;
293
294        // find the "sides" triangles that are on the edge uv
295        PMVertex::FaceList sides;
296        PMVertex::FaceList::iterator srcface, srcfaceEnd;
297        srcfaceEnd = src->face.end();
298        // Iterate over src's faces and find 'sides' of the shared edge which is being collapsed
299        for(srcface = src->face.begin(); srcface != srcfaceEnd; ++srcface)
300        {
301            // Check if this tri also has dest in it (shared edge)
302            if( (*srcface)->hasCommonVertex(dest) )
303            {
304                sides.insert(*srcface);
305            }
306        }
307
308                // Special cases
309                // If we're looking at a border vertex
310        if(src->isBorder())
311        {
312                        if (sides.size() > 1)
313                        {
314                                // src is on a border, but the src-dest edge has more than one tri on it
315                                // So it must be collapsing inwards
316                                // Mark as very high-value cost
317                                // curvature = 1.0f;
318                                cost = 1.0f;
319                        }
320                        else
321                        {
322                                // Collapsing ALONG a border
323                                // We can't use curvature to measure the effect on the model
324                                // Instead, see what effect it has on 'pulling' the other border edges
325                                // The more colinear, the less effect it will have
326                                // So measure the 'kinkiness' (for want of a better term)
327                                // Normally there can be at most 1 other border edge attached to this
328                                // However in weird cases there may be more, so find the worst
329                                Vector3 collapseEdge, otherBorderEdge;
330                                Real kinkiness, maxKinkiness;
331                                PMVertex::NeighborList::iterator n, nend;
332                                nend = src->neighbor.end();
333                                maxKinkiness = 0.0f;
334                                edgeVector.normalise();
335                                collapseEdge = edgeVector;
336                                for (n = src->neighbor.begin(); n != nend; ++n)
337                                {
338                                        if (*n != dest && (*n)->isManifoldEdgeWith(src))
339                                        {
340                                                otherBorderEdge = src->position - (*n)->position;
341                                                otherBorderEdge.normalise();
342                                                // This time, the nearer the dot is to -1, the better, because that means
343                                                // the edges are opposite each other, therefore less kinkiness
344                                                // Scale into [0..1]
345                                                kinkiness = (otherBorderEdge.dotProduct(collapseEdge) + 1.002f) * 0.5f;
346                                                maxKinkiness = std::max(kinkiness, maxKinkiness);
347
348                                        }
349                                }
350
351                                cost = maxKinkiness;
352
353                        }
354        }
355                else // not a border
356                {
357
358                        // Standard inner vertex
359                        // Calculate curvature
360                        // use the triangle facing most away from the sides
361                        // to determine our curvature term
362                        // Iterate over src's faces again
363                        for(srcface = src->face.begin(); srcface != srcfaceEnd; ++srcface)
364                        {
365                                Real mincurv = 1.0f; // curve for face i and closer side to it
366                                // Iterate over the sides
367                                PMVertex::FaceList::iterator sidesFace, sidesFaceEnd;
368                                sidesFaceEnd = sides.end();
369                                for(sidesFace = sides.begin(); sidesFace != sidesFaceEnd; ++sidesFace)
370                                {
371                                        // Dot product of face normal gives a good delta angle
372                                        Real dotprod = (*srcface)->normal.dotProduct( (*sidesFace)->normal );
373                                        // NB we do (1-..) to invert curvature where 1 is high curvature [0..1]
374                                        // Whilst dot product is high when angle difference is low
375                                        mincurv =  std::min(mincurv,(1.002f - dotprod) * 0.5f);
376                                }
377                                curvature = std::max(curvature, mincurv);
378                        }
379                        cost = curvature;
380                }
381
382        // check for texture seam ripping
383                if (src->seam && !dest->seam)
384                {
385                        cost = 1.0f;
386                }
387
388        // Check for singular triangle destruction
389        // If src and dest both only have 1 triangle (and it must be a shared one)
390        // then this would destroy the shape, so don't do this
391        if (src->face.size() == 1 && dest->face.size() == 1)
392        {
393            cost = NEVER_COLLAPSE_COST;
394        }
395
396
397                // Degenerate case check
398                // Are we going to invert a face normal of one of the neighbouring faces?
399                // Can occur when we have a very small remaining edge and collapse crosses it
400                // Look for a face normal changing by > 90 degrees
401                for(srcface = src->face.begin(); srcface != srcfaceEnd; ++srcface)
402                {
403                        // Ignore the deleted faces (those including src & dest)
404                        if( !(*srcface)->hasCommonVertex(dest) )
405                        {
406                                // Test the new face normal
407                                PMVertex *v0, *v1, *v2;
408                                // Replace src with dest wherever it is
409                                v0 = ( (*srcface)->vertex[0]->commonVertex == src) ? dest : (*srcface)->vertex[0]->commonVertex;
410                                v1 = ( (*srcface)->vertex[1]->commonVertex == src) ? dest : (*srcface)->vertex[1]->commonVertex;
411                                v2 = ( (*srcface)->vertex[2]->commonVertex == src) ? dest : (*srcface)->vertex[2]->commonVertex;
412
413                                // Cross-product 2 edges
414                                Vector3 e1 = v1->position - v0->position;
415                                Vector3 e2 = v2->position - v1->position;
416
417                                Vector3 newNormal = e1.crossProduct(e2);
418                                newNormal.normalise();
419
420                                // Dot old and new face normal
421                                // If < 0 then more than 90 degree difference
422                                if (newNormal.dotProduct( (*srcface)->normal ) < 0.0f )
423                                {
424                                        // Don't do it!
425                                        cost = NEVER_COLLAPSE_COST;
426                                        break; // No point continuing
427                                }
428
429
430                        }
431                }
432               
433
434                assert (cost >= 0);
435                return cost;
436    }
437    //---------------------------------------------------------------------
438    void ProgressiveMesh::initialiseEdgeCollapseCosts(void)
439    {
440        WorkingDataList::iterator i, iend;
441        iend = mWorkingData.end();
442        for (i = mWorkingData.begin(); i != iend; ++i)
443        {
444            CommonVertexList::iterator v, vend;
445            vend = i->mVertList.end();
446            for (v = i->mVertList.begin(); v != vend; ++v)
447            {
448                v->collapseTo = NULL;
449                v->collapseCost = NEVER_COLLAPSE_COST;
450            }
451        }
452
453       
454    }
455    //---------------------------------------------------------------------
456    Real ProgressiveMesh::computeEdgeCostAtVertexForBuffer(WorkingDataList::iterator idata, size_t vertIndex)
457    {
458        // compute the edge collapse cost for all edges that start
459        // from vertex v.  Since we are only interested in reducing
460        // the object by selecting the min cost edge at each step, we
461        // only cache the cost of the least cost edge at this vertex
462        // (in member variable collapse) as well as the value of the
463        // cost (in member variable objdist).
464
465        CommonVertexList::iterator v = idata->mVertList.begin();
466        v += vertIndex;
467
468        if(v->neighbor.empty()) {
469            // v doesn't have neighbors so nothing to collapse
470            v->notifyRemoved();
471            return v->collapseCost;
472        }
473
474        // Init metrics
475        v->collapseCost = NEVER_COLLAPSE_COST;
476        v->collapseTo = NULL;
477
478        // search all neighboring edges for "least cost" edge
479        PMVertex::NeighborList::iterator n, nend;
480        nend = v->neighbor.end();
481        Real cost;
482        for(n = v->neighbor.begin(); n != nend; ++n)
483        {
484            cost = computeEdgeCollapseCost(&(*v), *n);
485            if( (!v->collapseTo) || cost < v->collapseCost)
486            {
487                v->collapseTo = *n;  // candidate for edge collapse
488                v->collapseCost = cost;             // cost of the collapse
489            }
490        }
491
492        return v->collapseCost;
493    }
494    //---------------------------------------------------------------------
495    void ProgressiveMesh::computeAllCosts(void)
496    {
497        initialiseEdgeCollapseCosts();
498        size_t i;
499        for (i = 0; i < mpVertexData->vertexCount; ++i)
500        {
501            computeEdgeCostAtVertex(i);
502        }
503    }
504    //---------------------------------------------------------------------
505    void ProgressiveMesh::collapse(ProgressiveMesh::PMVertex *src)
506    {
507        PMVertex *dest = src->collapseTo;
508                std::set<PMVertex*> recomputeSet;
509
510                // Abort if we're never supposed to collapse
511                if (src->collapseCost == NEVER_COLLAPSE_COST)
512                        return;
513
514                // Remove this vertex from the running for the next check
515                src->collapseTo = NULL;
516                src->collapseCost = NEVER_COLLAPSE_COST;
517                mWorstCosts[src->index] = NEVER_COLLAPSE_COST;
518
519                // Collapse the edge uv by moving vertex u onto v
520            // Actually remove tris on uv, then update tris that
521            // have u to have v, and then remove u.
522            if(!dest) {
523                    // src is a vertex all by itself
524#if OGRE_DEBUG_MODE
525                        ofdebug << "Aborting collapse, orphan vertex. " << std::endl;
526#endif
527                        return;
528            }
529
530                // Add dest and all the neighbours of source and dest to recompute list
531                recomputeSet.insert(dest);
532                PMVertex::NeighborList::iterator n, nend;
533        nend = src->neighbor.end();
534
535                PMVertex* temp;
536
537            for(n = src->neighbor.begin(); n != nend; ++n)
538        {
539                        temp = *n;
540                        recomputeSet.insert( *n );
541                }
542        nend = dest->neighbor.end();
543            for(n = dest->neighbor.begin(); n != nend; ++n)
544        {
545                        temp = *n;
546                        recomputeSet.insert( *n );
547                }
548
549            // delete triangles on edge src-dest
550        // Notify others to replace src with dest
551        PMVertex::FaceList::iterator f, fend;
552        fend = src->face.end();
553                // Queue of faces for removal / replacement
554                // prevents us screwing up the iterators while we parse
555                PMVertex::FaceList faceRemovalList, faceReplacementList;
556            for(f = src->face.begin(); f != fend; ++f)
557        {
558                    if((*f)->hasCommonVertex(dest))
559            {
560                // Tri is on src-dest therefore is gone
561                                faceRemovalList.insert(*f);
562                // Reduce index count by 3 (useful for quick allocation later)
563                mCurrNumIndexes -= 3;
564                    }
565            else
566            {
567                // Only src involved, replace with dest
568                                faceReplacementList.insert(*f);
569            }
570            }
571
572                src->toBeRemoved = true;
573                // Replace all the faces queued for replacement
574            for(f = faceReplacementList.begin(); f != faceReplacementList.end(); ++f)
575                {
576                        /* Locate the face vertex which corresponds with the common 'dest' vertex
577                        To to this, find a removed face which has the FACE vertex corresponding with
578                        src, and use it's FACE vertex version of dest.
579                        */
580                        PMFaceVertex* srcFaceVert = (*f)->getFaceVertexFromCommon(src);
581                        PMFaceVertex* destFaceVert = NULL;
582                        PMVertex::FaceList::iterator iremoved;
583                        for(iremoved = faceRemovalList.begin(); iremoved != faceRemovalList.end(); ++iremoved)
584                        {
585                                //if ( (*iremoved)->hasFaceVertex(srcFaceVert) )
586                                //{
587                                        destFaceVert = (*iremoved)->getFaceVertexFromCommon(dest);
588                                //}
589                        }
590                       
591                        assert(destFaceVert);
592
593#if OGRE_DEBUG_MODE
594                        ofdebug << "Replacing vertex on face " << (unsigned int)(*f)->index << std::endl;
595#endif
596            (*f)->replaceVertex(srcFaceVert, destFaceVert);
597                }
598                // Remove all the faces queued for removal
599            for(f = faceRemovalList.begin(); f != faceRemovalList.end(); ++f)
600                {
601#if OGRE_DEBUG_MODE
602                        ofdebug << "Removing face " << (unsigned int)(*f)->index << std::endl;
603#endif
604                        (*f)->notifyRemoved();
605                }
606
607        // Notify the vertex that it is gone
608        src->notifyRemoved();
609
610        // recompute costs
611                std::set<PMVertex*>::iterator irecomp, irecompend;
612                irecompend = recomputeSet.end();
613                for (irecomp = recomputeSet.begin(); irecomp != irecompend; ++irecomp)
614                {
615                        temp = (*irecomp);
616                        computeEdgeCostAtVertex( (*irecomp)->index );
617                }
618               
619    }
620    //---------------------------------------------------------------------
621    void ProgressiveMesh::computeEdgeCostAtVertex(size_t vertIndex)
622    {
623                // Call computer for each buffer on this vertex
624        Real worstCost = -0.01f;
625        WorkingDataList::iterator i, iend;
626        iend = mWorkingData.end();
627        for (i = mWorkingData.begin(); i != iend; ++i)
628        {
629            worstCost = std::max(worstCost,
630                computeEdgeCostAtVertexForBuffer(i, vertIndex));
631        }
632        // Save the worst cost
633        mWorstCosts[vertIndex] = worstCost;
634    }
635    //---------------------------------------------------------------------
636    size_t ProgressiveMesh::getNextCollapser(void)
637    {
638        // Scan
639        // Not done as a sort because want to keep the lookup simple for now
640        Real bestVal = NEVER_COLLAPSE_COST;
641        size_t i, bestIndex;
642                bestIndex = 0; // NB this is ok since if nothing is better than this, nothing will collapse
643        for (i = 0; i < mNumCommonVertices; ++i)
644        {
645            if (mWorstCosts[i] < bestVal)
646            {
647                bestVal = mWorstCosts[i];
648                bestIndex = i;
649            }
650        }
651        return bestIndex;
652    }
653    //---------------------------------------------------------------------
654    void ProgressiveMesh::bakeNewLOD(IndexData* pData)
655    {
656        assert(mCurrNumIndexes > 0 && "No triangles to bake!");
657        // Zip through the tri list of any working data copy and bake
658        pData->indexCount = mCurrNumIndexes;
659                pData->indexStart = 0;
660                // Base size of indexes on original
661                bool use32bitindexes =
662                        (mpIndexData->indexBuffer->getType() == HardwareIndexBuffer::IT_32BIT);
663
664                // Create index buffer, we don't need to read it back or modify it a lot
665                pData->indexBuffer = HardwareBufferManager::getSingleton().createIndexBuffer(
666                        use32bitindexes? HardwareIndexBuffer::IT_32BIT : HardwareIndexBuffer::IT_16BIT,
667                        pData->indexCount, HardwareBuffer::HBU_STATIC_WRITE_ONLY, false);
668
669        unsigned short* pShort;
670                unsigned int* pInt;
671                if (use32bitindexes)
672                {
673                        pInt = static_cast<unsigned int*>(
674                                pData->indexBuffer->lock( 0,
675                                        pData->indexBuffer->getSizeInBytes(),
676                                        HardwareBuffer::HBL_DISCARD));
677                }
678                else
679                {
680                        pShort = static_cast<unsigned short*>(
681                                pData->indexBuffer->lock( 0,
682                                        pData->indexBuffer->getSizeInBytes(),
683                                        HardwareBuffer::HBL_DISCARD));
684                }
685        TriangleList::iterator tri, triend;
686        // Use the first working data buffer, they are all the same index-wise
687        WorkingDataList::iterator pWork = mWorkingData.begin();
688        triend = pWork->mTriList.end();
689        for (tri = pWork->mTriList.begin(); tri != triend; ++tri)
690        {
691            if (!tri->removed)
692            {
693                                if (use32bitindexes)
694                                {
695                                        *pInt++ = static_cast<unsigned int>(tri->vertex[0]->realIndex);
696                                        *pInt++ = static_cast<unsigned int>(tri->vertex[1]->realIndex);
697                                        *pInt++ = static_cast<unsigned int>(tri->vertex[2]->realIndex);
698                                }
699                                else
700                                {
701                                        *pShort++ = static_cast<unsigned short>(tri->vertex[0]->realIndex);
702                                        *pShort++ = static_cast<unsigned short>(tri->vertex[1]->realIndex);
703                                        *pShort++ = static_cast<unsigned short>(tri->vertex[2]->realIndex);
704                                }
705            }
706        }
707                pData->indexBuffer->unlock();
708
709    }
710    //---------------------------------------------------------------------
711    ProgressiveMesh::PMTriangle::PMTriangle() : removed(false)
712    {
713    }
714    //---------------------------------------------------------------------
715    void ProgressiveMesh::PMTriangle::setDetails(size_t newindex,
716                ProgressiveMesh::PMFaceVertex *v0, ProgressiveMesh::PMFaceVertex *v1,
717        ProgressiveMesh::PMFaceVertex *v2)
718    {
719        assert(v0!=v1 && v1!=v2 && v2!=v0);
720
721        index = newindex;
722                vertex[0]=v0;
723        vertex[1]=v1;
724        vertex[2]=v2;
725
726        computeNormal();
727
728        // Add tri to vertices
729        // Also tell vertices they are neighbours
730        for(int i=0;i<3;i++) {
731            vertex[i]->commonVertex->face.insert(this);
732            for(int j=0;j<3;j++) if(i!=j) {
733                vertex[i]->commonVertex->neighbor.insert(vertex[j]->commonVertex);
734            }
735        }
736    }
737    //---------------------------------------------------------------------
738    void ProgressiveMesh::PMTriangle::notifyRemoved(void)
739    {
740        int i;
741        for(i=0; i<3; i++) {
742            // remove this tri from the vertices
743            if(vertex[i]) vertex[i]->commonVertex->face.erase(this);
744        }
745        for(i=0; i<3; i++) {
746            int i2 = (i+1)%3;
747            if(!vertex[i] || !vertex[i2]) continue;
748            // Check remaining vertices and remove if not neighbours anymore
749            // NB May remain neighbours if other tris link them
750            vertex[i ]->commonVertex->removeIfNonNeighbor(vertex[i2]->commonVertex);
751            vertex[i2]->commonVertex->removeIfNonNeighbor(vertex[i ]->commonVertex);
752        }
753
754        removed = true;
755    }
756    //---------------------------------------------------------------------
757    bool ProgressiveMesh::PMTriangle::hasCommonVertex(ProgressiveMesh::PMVertex *v) const
758    {
759        return (v == vertex[0]->commonVertex ||
760                        v == vertex[1]->commonVertex ||
761                        v == vertex[2]->commonVertex);
762    }
763    //---------------------------------------------------------------------
764        bool ProgressiveMesh::PMTriangle::hasFaceVertex(ProgressiveMesh::PMFaceVertex *v) const
765        {
766                return (v == vertex[0] ||
767                                v == vertex[1] ||
768                                v == vertex[2]);
769        }
770    //---------------------------------------------------------------------
771        ProgressiveMesh::PMFaceVertex*
772        ProgressiveMesh::PMTriangle::getFaceVertexFromCommon(ProgressiveMesh::PMVertex* commonVert)
773        {
774                if (vertex[0]->commonVertex == commonVert) return vertex[0];
775                if (vertex[1]->commonVertex == commonVert) return vertex[1];
776                if (vertex[2]->commonVertex == commonVert) return vertex[2];
777
778                return NULL;
779
780        }
781    //---------------------------------------------------------------------
782    void ProgressiveMesh::PMTriangle::computeNormal()
783    {
784        Vector3 v0=vertex[0]->commonVertex->position;
785        Vector3 v1=vertex[1]->commonVertex->position;
786        Vector3 v2=vertex[2]->commonVertex->position;
787        // Cross-product 2 edges
788        Vector3 e1 = v1 - v0;
789        Vector3 e2 = v2 - v1;
790
791        normal = e1.crossProduct(e2);
792        normal.normalise();
793    }
794    //---------------------------------------------------------------------
795    void ProgressiveMesh::PMTriangle::replaceVertex(
796                ProgressiveMesh::PMFaceVertex *vold, ProgressiveMesh::PMFaceVertex *vnew)
797    {
798        assert(vold && vnew);
799        assert(vold==vertex[0] || vold==vertex[1] || vold==vertex[2]);
800        assert(vnew!=vertex[0] && vnew!=vertex[1] && vnew!=vertex[2]);
801        if(vold==vertex[0]){
802            vertex[0]=vnew;
803        }
804        else if(vold==vertex[1]){
805            vertex[1]=vnew;
806        }
807        else {
808            assert(vold==vertex[2]);
809            vertex[2]=vnew;
810        }
811        int i;
812        vold->commonVertex->face.erase(this);
813        vnew->commonVertex->face.insert(this);
814        for(i=0;i<3;i++) {
815            vold->commonVertex->removeIfNonNeighbor(vertex[i]->commonVertex);
816            vertex[i]->commonVertex->removeIfNonNeighbor(vold->commonVertex);
817        }
818        for(i=0;i<3;i++) {
819            assert(vertex[i]->commonVertex->face.find(this) != vertex[i]->commonVertex->face.end());
820            for(int j=0;j<3;j++) if(i!=j) {
821#if OGRE_DEBUG_MODE
822                                ofdebug << "Adding vertex " << (unsigned int)vertex[j]->commonVertex->index << " to the neighbor list "
823                                        "of vertex " << (unsigned int)vertex[i]->commonVertex->index << std::endl;
824#endif
825                vertex[i]->commonVertex->neighbor.insert(vertex[j]->commonVertex);
826            }
827        }
828        computeNormal();
829    }
830    //---------------------------------------------------------------------
831    ProgressiveMesh::PMVertex::PMVertex() : removed(false)
832    {
833    }
834    //---------------------------------------------------------------------
835    void ProgressiveMesh::PMVertex::setDetails(const Vector3& v, size_t newindex)
836    {
837        position = v;
838        index = newindex;
839    }
840    //---------------------------------------------------------------------
841    void ProgressiveMesh::PMVertex::notifyRemoved(void)
842    {
843        NeighborList::iterator i, iend;
844        iend = neighbor.end();
845        for (i = neighbor.begin(); i != iend; ++i)
846        {
847            // Remove me from neighbor
848            (*i)->neighbor.erase(this);
849        }
850        removed = true;
851                this->collapseTo = NULL;
852        this->collapseCost = NEVER_COLLAPSE_COST;
853    }
854    //---------------------------------------------------------------------
855    bool ProgressiveMesh::PMVertex::isBorder()
856    {
857        // Look for edges which only have one tri attached, this is a border
858
859        NeighborList::iterator i, iend;
860        iend = neighbor.end();
861        // Loop for each neighbor
862        for(i = neighbor.begin(); i != iend; ++i)
863        {
864            // Count of tris shared between the edge between this and neighbor
865            ushort count = 0;
866            // Loop over each face, looking for shared ones
867            FaceList::iterator j, jend;
868            jend = face.end();
869            for(j = face.begin(); j != jend; ++j)
870            {
871                if((*j)->hasCommonVertex(*i))
872                {
873                    // Shared tri
874                    count ++;
875                }
876            }
877            //assert(count>0); // Must be at least one!
878            // This edge has only 1 tri on it, it's a border
879            if(count == 1)
880                                return true;
881        }
882        return false;
883    }
884        //---------------------------------------------------------------------
885        bool ProgressiveMesh::PMVertex::isManifoldEdgeWith(ProgressiveMesh::PMVertex* v)
886        {
887                // Check the sides involving both these verts
888                // If there is only 1 this is a manifold edge
889                ushort sidesCount = 0;
890                FaceList::iterator i, iend;
891                iend = face.end();
892                for (i = face.begin(); i != iend; ++i)
893                {
894                        if ((*i)->hasCommonVertex(v))
895                        {
896                                sidesCount++;
897                        }
898                }
899
900                return (sidesCount == 1);
901        }
902        //---------------------------------------------------------------------
903    void ProgressiveMesh::PMVertex::removeIfNonNeighbor(ProgressiveMesh::PMVertex *n)
904    {
905        // removes n from neighbor list if n isn't a neighbor.
906        NeighborList::iterator i = neighbor.find(n);
907        if (i == neighbor.end())
908            return; // Not in neighbor list anyway
909
910        FaceList::iterator f, fend;
911        fend = face.end();
912        for(f = face.begin(); f != fend; ++f)
913        {
914            if((*f)->hasCommonVertex(n)) return; // Still a neighbor
915        }
916
917#if OGRE_DEBUG_MODE
918                ofdebug << "Vertex " << (unsigned int)n->index << " is no longer a neighbour of vertex " << (unsigned int)this->index <<
919                        " so has been removed from the latter's neighbor list." << std::endl;
920#endif
921        neighbor.erase(n);
922
923                if (neighbor.empty() && !toBeRemoved)
924                {
925                        // This vertex has been removed through isolation (collapsing around it)
926                        this->notifyRemoved();
927                }
928    }
929    //---------------------------------------------------------------------
930    void ProgressiveMesh::dumpContents(const String& log)
931        {
932                std::ofstream ofdump(log.c_str());
933
934                // Just dump 1st working data for now
935                WorkingDataList::iterator worki = mWorkingData.begin();
936
937                CommonVertexList::iterator vi, vend;
938                vend = worki->mVertList.end();
939                ofdump << "-------== VERTEX LIST ==-----------------" << std::endl;
940                size_t i;
941                for (vi = worki->mVertList.begin(), i = 0; i < mNumCommonVertices; ++vi, ++i)
942                {
943                        ofdump << "Vertex " << (unsigned int)vi->index << " pos: " << vi->position << " removed: "
944                                << vi->removed << " isborder: " << vi->isBorder() << std::endl;
945                        ofdump << "    Faces:" << std::endl;
946                        PMVertex::FaceList::iterator f, fend;
947                        fend = vi->face.end();
948                        for(f = vi->face.begin(); f != fend; ++f)
949                        {
950                                ofdump << "    Triangle index " << (unsigned int)(*f)->index << std::endl;
951                        }
952                        ofdump << "    Neighbours:" << std::endl;
953                        PMVertex::NeighborList::iterator n, nend;
954                        nend = vi->neighbor.end();
955                        for (n = vi->neighbor.begin(); n != nend; ++n)
956                        {
957                                ofdump << "    Vertex index " << (unsigned int)(*n)->index << std::endl;
958                        }
959
960                }
961
962                TriangleList::iterator ti, tend;
963                tend = worki->mTriList.end();
964                ofdump << "-------== TRIANGLE LIST ==-----------------" << std::endl;
965                for(ti = worki->mTriList.begin(); ti != tend; ++ti)
966                {
967                        ofdump << "Triangle " << (unsigned int)ti->index << " norm: " << ti->normal << " removed: " << ti->removed << std::endl;
968                        ofdump << "    Vertex 0: " << (unsigned int)ti->vertex[0]->realIndex << std::endl;
969                        ofdump << "    Vertex 1: " << (unsigned int)ti->vertex[1]->realIndex << std::endl;
970                        ofdump << "    Vertex 2: " << (unsigned int)ti->vertex[2]->realIndex << std::endl;
971                }
972
973                ofdump << "-------== COLLAPSE COST LIST ==-----------------" << std::endl;
974                for (size_t ci = 0; ci < mNumCommonVertices; ++ci)
975                {
976                        ofdump << "Vertex " << (unsigned int)ci << ": " << mWorstCosts[ci] << std::endl;
977                }
978
979                ofdump.close();
980        }
981
982
983}
Note: See TracBrowser for help on using the repository browser.