source: OGRE/trunk/ogrenew/OgreMain/src/OgreEdgeListBuilder.cpp @ 692

Revision 692, 24.7 KB checked in by mattausch, 19 years ago (diff)

adding ogre 1.2 and dependencies

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#include "OgreEdgeListBuilder.h"
27#include "OgreLogManager.h"
28#include "OgreStringConverter.h"
29#include "OgreVertexIndexData.h"
30#include "OgreException.h"
31
32namespace Ogre {
33
34    void EdgeData::log(Log* l)
35    {
36        EdgeGroupList::iterator i, iend;
37        EdgeList::iterator ei, eiend;
38        TriangleList::iterator ti, tiend;
39        tiend = triangles.end();
40        l->logMessage("Edge Data");
41        l->logMessage("---------");
42        size_t num = 0;
43        for (ti = triangles.begin(); ti != tiend; ++ti, ++num)
44        {
45            Triangle& t = *ti;
46            l->logMessage("Triangle " + StringConverter::toString(num) + " = {" +
47                "indexSet=" + StringConverter::toString(t.indexSet) + ", " +
48                "vertexSet=" + StringConverter::toString(t.vertexSet) + ", " +
49                "v0=" + StringConverter::toString(t.vertIndex[0]) + ", " +
50                "v1=" + StringConverter::toString(t.vertIndex[1]) + ", " +
51                "v2=" + StringConverter::toString(t.vertIndex[2]) + "}");
52        }
53        iend = edgeGroups.end();
54        for (i = edgeGroups.begin(); i != iend; ++i)
55        {
56            num = 0;
57            eiend = i->edges.end();
58            l->logMessage("Edge Group vertexSet=" + StringConverter::toString(i->vertexSet));
59            for (ei = i->edges.begin(); ei != eiend; ++ei, ++num)
60            {
61                Edge& e = *ei;
62                l->logMessage(
63                    "Edge " + StringConverter::toString(num) + " = {\n" +
64                    "  tri0=" + StringConverter::toString(e.triIndex[0]) + ", \n" +
65                    "  tri1=" + StringConverter::toString(e.triIndex[1]) + ", \n" +
66                    "  v0=" + StringConverter::toString(e.vertIndex[0]) + ", \n" +
67                    "  v1=" + StringConverter::toString(e.vertIndex[1]) + ", \n"
68                    "  degenerate=" + StringConverter::toString(e.degenerate) + " \n"
69                    "}");
70            }
71        }
72    }
73    //---------------------------------------------------------------------
74    EdgeListBuilder::EdgeListBuilder()
75        : mEdgeData(0)
76    {
77    }
78    //---------------------------------------------------------------------
79    EdgeListBuilder::~EdgeListBuilder()
80    {
81    }
82    //---------------------------------------------------------------------
83    void EdgeListBuilder::addVertexData(const VertexData* vertexData)
84    {
85        mVertexDataList.push_back(vertexData);
86    }
87    //---------------------------------------------------------------------
88    void EdgeListBuilder::addIndexData(const IndexData* indexData,
89        size_t vertexSet, RenderOperation::OperationType opType)
90    {
91        Geometry geometry;
92        geometry.indexData = indexData;
93        geometry.vertexSet = vertexSet;
94        geometry.opType = opType;
95        geometry.indexSet = mGeometryList.size();
96        mGeometryList.push_back(geometry);
97    }
98    //---------------------------------------------------------------------
99    EdgeData* EdgeListBuilder::build(void)
100    {
101        /* Ok, here's the algorithm:
102        For each set of indices in turn
103          For each set of 3 indexes
104            Create a new Triangle entry in the list
105            For each vertex referenced by the tri indexes
106              Get the position of the vertex as a Vector3 from the correct vertex buffer
107              Attempt to locate this position in the existing common vertex set
108              If not found
109                Create a new common vertex entry in the list
110              End If
111              Populate the original vertex index and common vertex index
112            Next vertex
113            Connect to existing edge(v1, v0) or create a new edge(v0, v1)
114            Connect to existing edge(v2, v1) or create a new edge(v1, v2)
115            Connect to existing edge(v0, v2) or create a new edge(v2, v0)
116          Next set of 3 indexes
117        Next index set
118
119        Note that all edges 'belong' to the index set which originally caused them
120        to be created, which also means that the 2 vertices on the edge are both referencing the
121        vertex buffer which this index set uses.
122        */
123
124
125        /*
126        There is a major consideration: 'What is a common vertex'? This is a
127        crucial decision, since to form a completely close hull, you need to treat
128        vertices which are not physically the same as equivalent. This is because
129        there will be 'seams' in the model, where discrepancies in vertex components
130        other than position (such as normals or texture coordinates) will mean
131        that there are 2 vertices in the same place, and we MUST 'weld' them
132        into a single common vertex in order to have a closed hull. Just looking
133        at the unique vertex indices is not enough, since these seams would render
134        the hull invalid.
135
136        So, we look for positions which are the same across vertices, and treat
137        those as as single vertex for our edge calculation. However, this has
138        it's own problems. There are OTHER vertices which may have a common
139        position that should not be welded. Imagine 2 cubes touching along one
140        single edge. The common vertices on that edge, if welded, will cause
141        an ambiguous hull, since the edge will have 4 triangles attached to it,
142        whilst a manifold mesh should only have 2 triangles attached to each edge.
143        This is a problem.
144
145        We deal with this with allow welded multiple pairs of edges. Using this
146        techniques, we can build a individual hull even if the model which has a
147        potentially ambiguous hull. This is feasible, because in the case of
148        multiple hulls existing, each hull can cast same shadow in any situation.
149        Notice: For stencil shadow, we intent to build a valid shadow volume for
150        the mesh, not the valid hull for the mesh.
151        */
152
153        // Sort the geometries in the order of vertex set, so we can grouping
154        // triangles by vertex set easy, and improve memory access as well.
155        std::sort(mGeometryList.begin(), mGeometryList.end(), geometryLess());
156        // Initialize edge data
157        mEdgeData = new EdgeData();
158        // resize the edge group list to equal the number of vertex sets
159        mEdgeData->edgeGroups.resize(mVertexDataList.size());
160        // Initialise edge group data
161        for (unsigned short vSet = 0; vSet < mVertexDataList.size(); ++vSet)
162        {
163            mEdgeData->edgeGroups[vSet].vertexSet = vSet;
164            mEdgeData->edgeGroups[vSet].vertexData = mVertexDataList[vSet];
165        }
166
167        // Build triangles and edge list
168        GeometryList::const_iterator i, iend;
169        iend = mGeometryList.end();
170        for (i = mGeometryList.begin(); i != iend; ++i)
171        {
172            buildTrianglesEdges(*i);
173        }
174
175        // Log
176        //log(LogManager::getSingleton().createLog("EdgeListBuilder.log"));
177
178                // Record closed - uncomment this when .mesh format includes isClosed
179                //mEdgeData->isClosed = mEdgeMap.empty();
180        return mEdgeData;
181    }
182    //---------------------------------------------------------------------
183    void EdgeListBuilder::buildTrianglesEdges(const Geometry &geometry)
184    {
185        size_t indexSet = geometry.indexSet;
186        size_t vertexSet = geometry.vertexSet;
187        const IndexData* indexData = geometry.indexData;
188        RenderOperation::OperationType opType = geometry.opType;
189
190        size_t iterations;
191       
192        switch (opType)
193        {
194        case RenderOperation::OT_TRIANGLE_LIST:
195            iterations = indexData->indexCount / 3;
196            break;
197        case RenderOperation::OT_TRIANGLE_FAN:
198        case RenderOperation::OT_TRIANGLE_STRIP:
199            iterations = indexData->indexCount - 2;
200            break;
201        default:
202            break;
203        };
204
205
206
207                // locate position element & the buffer to go with it
208        const VertexData* vertexData = mVertexDataList[vertexSet];
209                const VertexElement* posElem = vertexData->vertexDeclaration->findElementBySemantic(VES_POSITION);
210                HardwareVertexBufferSharedPtr vbuf =
211                        vertexData->vertexBufferBinding->getBuffer(posElem->getSource());
212                // lock the buffer for reading
213                unsigned char* pBaseVertex = static_cast<unsigned char*>(
214                        vbuf->lock(HardwareBuffer::HBL_READ_ONLY));
215
216        // Get the indexes ready for reading
217                bool idx32bit = (indexData->indexBuffer->getType() == HardwareIndexBuffer::IT_32BIT);
218                size_t indexSize = idx32bit ? sizeof(uint32) : sizeof(uint16);
219#if defined(_MSC_VER) && _MSC_VER <= 1300
220        // NB: Can't use un-named union with VS.NET 2002 when /RTC1 compile flag enabled.
221        void* pIndex = indexData->indexBuffer->lock(HardwareBuffer::HBL_READ_ONLY);
222                pIndex = static_cast<void*>(
223                        static_cast<char*>(pIndex) + indexData->indexStart * indexSize);
224        unsigned short* p16Idx = static_cast<unsigned short*>(pIndex);
225        unsigned int* p32Idx = static_cast<unsigned int*>(pIndex);
226#else
227        union {
228            void* pIndex;
229            unsigned short* p16Idx;
230            unsigned int* p32Idx;
231        };
232        pIndex = indexData->indexBuffer->lock(HardwareBuffer::HBL_READ_ONLY);
233                pIndex = static_cast<void*>(
234                        static_cast<char*>(pIndex) + indexData->indexStart * indexSize);
235#endif
236
237        // Iterate over all the groups of 3 indexes
238        unsigned int index[3];
239        // Get the triangle start, if we have more than one index set then this
240        // will not be zero
241        size_t triStart = mEdgeData->triangles.size();
242        // Pre-reserve memory for less thrashing
243        mEdgeData->triangles.reserve(triStart + iterations);
244        for (size_t t = 0; t < iterations; ++t)
245        {
246            EdgeData::Triangle tri;
247            tri.indexSet = indexSet;
248            tri.vertexSet = vertexSet;
249
250            if (opType == RenderOperation::OT_TRIANGLE_LIST || t == 0)
251            {
252                // Standard 3-index read for tri list or first tri in strip / fan
253                if (idx32bit)
254                {
255                    index[0] = p32Idx[0];
256                    index[1] = p32Idx[1];
257                    index[2] = p32Idx[2];
258                    p32Idx += 3;
259                }
260                else
261                {
262                    index[0] = p16Idx[0];
263                    index[1] = p16Idx[1];
264                    index[2] = p16Idx[2];
265                    p16Idx += 3;
266                }
267            }
268            else
269            {
270                // Strips are formed from last 2 indexes plus the current one for
271                // triangles after the first.
272                // For fans, all the triangles share the first vertex, plus last
273                // one index and the current one for triangles after the first.
274                // We also make sure that all the triangles are process in the
275                // _anti_ clockwise orientation
276                index[(opType == RenderOperation::OT_TRIANGLE_STRIP) && (t & 1) ? 0 : 1] = index[2];
277                // Read for the last tri index
278                if (idx32bit)
279                    index[2] = *p32Idx++;
280                else
281                    index[2] = *p16Idx++;
282            }
283
284            Vector3 v[3];
285            for (size_t i = 0; i < 3; ++i)
286            {
287                // Populate tri original vertex index
288                tri.vertIndex[i] = index[i];
289
290                // Retrieve the vertex position
291                unsigned char* pVertex = pBaseVertex + (index[i] * vbuf->getVertexSize());
292                float* pFloat;
293                posElem->baseVertexPointerToElement(pVertex, &pFloat);
294                v[i].x = *pFloat++;
295                v[i].y = *pFloat++;
296                v[i].z = *pFloat++;
297                // find this vertex in the existing vertex map, or create it
298                tri.sharedVertIndex[i] =
299                    findOrCreateCommonVertex(v[i], vertexSet, indexSet, index[i]);
300            }
301
302            // Ignore degenerate triangle
303            if (tri.sharedVertIndex[0] != tri.sharedVertIndex[1] &&
304                tri.sharedVertIndex[1] != tri.sharedVertIndex[2] &&
305                tri.sharedVertIndex[2] != tri.sharedVertIndex[0])
306            {
307                // Calculate triangle normal (NB will require recalculation for
308                // skeletally animated meshes)
309                tri.normal = Math::calculateFaceNormalWithoutNormalize(v[0], v[1], v[2]);
310                // Add triangle to list
311                mEdgeData->triangles.push_back(tri);
312                // Connect or create edges from common list
313                connectOrCreateEdge(vertexSet, triStart + t,
314                    tri.vertIndex[0], tri.vertIndex[1],
315                    tri.sharedVertIndex[0], tri.sharedVertIndex[1]);
316                connectOrCreateEdge(vertexSet, triStart + t,
317                    tri.vertIndex[1], tri.vertIndex[2],
318                    tri.sharedVertIndex[1], tri.sharedVertIndex[2]);
319                connectOrCreateEdge(vertexSet, triStart + t,
320                    tri.vertIndex[2], tri.vertIndex[0],
321                    tri.sharedVertIndex[2], tri.sharedVertIndex[0]);
322            }
323        }
324
325        indexData->indexBuffer->unlock();
326        vbuf->unlock();
327    }
328    //---------------------------------------------------------------------
329    void EdgeListBuilder::connectOrCreateEdge(size_t vertexSet, size_t triangleIndex,
330        size_t vertIndex0, size_t vertIndex1, size_t sharedVertIndex0,
331        size_t sharedVertIndex1)
332    {
333        // Find the existing edge (should be reversed order) on shared vertices
334        EdgeMap::iterator emi = mEdgeMap.find(std::pair<size_t, size_t>(sharedVertIndex1, sharedVertIndex0));
335        if (emi != mEdgeMap.end())
336        {
337            // The edge already exist, connect it
338            EdgeData::Edge& e = mEdgeData->edgeGroups[emi->second.first].edges[emi->second.second];
339            // update with second side
340            e.triIndex[1] = triangleIndex;
341            e.degenerate = false;
342
343            // Remove from the edge map, so we never supplied to connect edge again
344            mEdgeMap.erase(emi);
345        }
346        else
347        {
348            // Not found, create new edge
349            mEdgeMap.insert(EdgeMap::value_type(
350                std::pair<size_t, size_t>(sharedVertIndex0, sharedVertIndex1),
351                std::pair<size_t, size_t>(vertexSet, mEdgeData->edgeGroups[vertexSet].edges.size())));
352            EdgeData::Edge e;
353            e.degenerate = true; // initialise as degenerate
354
355            // Set only first tri, the other will be completed in connect existing edge
356            e.triIndex[0] = triangleIndex;
357            e.triIndex[1] = ~0;
358            e.sharedVertIndex[0] = sharedVertIndex0;
359            e.sharedVertIndex[1] = sharedVertIndex1;
360            e.vertIndex[0] = vertIndex0;
361            e.vertIndex[1] = vertIndex1;
362            mEdgeData->edgeGroups[vertexSet].edges.push_back(e);
363        }
364    }
365    //---------------------------------------------------------------------
366    size_t EdgeListBuilder::findOrCreateCommonVertex(const Vector3& vec,
367        size_t vertexSet, size_t indexSet, size_t originalIndex)
368    {
369        // Because the algorithm doesn't care about manifold or not, we just identifying
370        // the common vertex by EXACT same position.
371        // Hint: We can use quantize method for welding almost same position vertex fastest.
372        std::pair<CommonVertexMap::iterator, bool> inserted =
373            mCommonVertexMap.insert(CommonVertexMap::value_type(vec, mVertices.size()));
374        if (!inserted.second)
375        {
376            // Already existing, return old one
377            return inserted.first->second;
378        }
379        // Not found, insert
380        CommonVertex newCommon;
381        newCommon.index = mVertices.size();
382        newCommon.position = vec;
383        newCommon.vertexSet = vertexSet;
384        newCommon.indexSet = indexSet;
385        newCommon.originalIndex = originalIndex;
386        mVertices.push_back(newCommon);
387        return newCommon.index;
388    }
389    //---------------------------------------------------------------------
390    //---------------------------------------------------------------------
391    void EdgeData::updateTriangleLightFacing(const Vector4& lightPos)
392    {
393        // Iterate over the triangles, and determine if they are light facing
394        EdgeData::TriangleList::iterator ti, tiend;
395        tiend = triangles.end();
396        Vector3 vertToLight;
397        for (ti = triangles.begin(); ti != tiend; ++ti)
398        {
399            EdgeData::Triangle& t = *ti;
400            // Get pointer to positions, and reference the first position
401
402            Real dp = t.normal.dotProduct(lightPos);
403            t.lightFacing = (dp > 0);
404
405        }
406
407    }
408    //---------------------------------------------------------------------
409    void EdgeData::updateFaceNormals(size_t vertexSet,
410        HardwareVertexBufferSharedPtr positionBuffer)
411    {
412        assert (positionBuffer->getVertexSize() == sizeof(float) * 3
413            && "Position buffer should contain only positions!");
414
415        // Lock buffer for reading
416        float* pVert = static_cast<float*>(
417            positionBuffer->lock(HardwareBuffer::HBL_READ_ONLY));
418
419        // Iterate over the triangles
420        EdgeData::TriangleList::iterator i, iend;
421        iend = triangles.end();
422        for (i = triangles.begin(); i != iend; ++i)
423        {
424            Triangle& t = *i;
425            // Only update tris which are using this vertex set
426            if (t.vertexSet == vertexSet)
427            {
428                size_t offset = t.vertIndex[0]*3;
429                Vector3 v1(pVert[offset], pVert[offset+1], pVert[offset+2]);
430
431                offset = t.vertIndex[1]*3;
432                Vector3 v2(pVert[offset], pVert[offset+1], pVert[offset+2]);
433
434                offset = t.vertIndex[2]*3;
435                Vector3 v3(pVert[offset], pVert[offset+1], pVert[offset+2]);
436
437                t.normal = Math::calculateFaceNormalWithoutNormalize(v1, v2, v3);
438            }
439        }
440
441
442        // unlock the buffer
443        positionBuffer->unlock();
444    }
445    //---------------------------------------------------------------------
446    void EdgeListBuilder::log(Log* l)
447    {
448        l->logMessage("EdgeListBuilder Log");
449        l->logMessage("-------------------");
450        l->logMessage("Number of vertex sets: " + StringConverter::toString(mVertexDataList.size()));
451        l->logMessage("Number of index sets: " + StringConverter::toString(mGeometryList.size()));
452       
453        size_t i, j;
454        // Log original vertex data
455        for(i = 0; i < mVertexDataList.size(); ++i)
456        {
457            const VertexData* vData = mVertexDataList[i];
458            l->logMessage(".");
459            l->logMessage("Original vertex set " +
460                StringConverter::toString(i) + " - vertex count " +
461                StringConverter::toString(vData->vertexCount));
462            const VertexElement* posElem = vData->vertexDeclaration->findElementBySemantic(VES_POSITION);
463            HardwareVertexBufferSharedPtr vbuf =
464                vData->vertexBufferBinding->getBuffer(posElem->getSource());
465            // lock the buffer for reading
466            unsigned char* pBaseVertex = static_cast<unsigned char*>(
467                vbuf->lock(HardwareBuffer::HBL_READ_ONLY));
468            float* pFloat;
469            for (j = 0; j < vData->vertexCount; ++j)
470            {
471                posElem->baseVertexPointerToElement(pBaseVertex, &pFloat);
472                l->logMessage("Vertex " + StringConverter::toString(j) +
473                    ": (" + StringConverter::toString(pFloat[0]) +
474                    ", " + StringConverter::toString(pFloat[1]) +
475                    ", " + StringConverter::toString(pFloat[2]) + ")");
476                pBaseVertex += vbuf->getVertexSize();
477            }
478            vbuf->unlock();
479        }
480
481        // Log original index data
482        for(i = 0; i < mGeometryList.size(); i++)
483        {
484            const IndexData* iData = mGeometryList[i].indexData;
485            l->logMessage(".");
486            l->logMessage("Original triangle set " +
487                StringConverter::toString(mGeometryList[i].indexSet) + " - index count " +
488                StringConverter::toString(iData->indexCount) + " - " +
489            "vertex set " + StringConverter::toString(mGeometryList[i].vertexSet) + " - " +
490            "operationType " + StringConverter::toString(mGeometryList[i].opType));
491            // Get the indexes ready for reading
492            unsigned short* p16Idx;
493            unsigned int* p32Idx;
494
495            if (iData->indexBuffer->getType() == HardwareIndexBuffer::IT_32BIT)
496            {
497                p32Idx = static_cast<unsigned int*>(
498                    iData->indexBuffer->lock(HardwareBuffer::HBL_READ_ONLY));
499            }
500            else
501            {
502                p16Idx = static_cast<unsigned short*>(
503                    iData->indexBuffer->lock(HardwareBuffer::HBL_READ_ONLY));
504            }
505
506            for (j = 0; j < iData->indexCount;  )
507            {
508                if (iData->indexBuffer->getType() == HardwareIndexBuffer::IT_32BIT)
509                {
510                    if (mGeometryList[i].opType == RenderOperation::OT_TRIANGLE_LIST
511                        || j == 0)
512                    {
513                        l->logMessage("Triangle " + StringConverter::toString(j) +
514                            ": (" + StringConverter::toString(*p32Idx++) +
515                            ", " + StringConverter::toString(*p32Idx++) +
516                            ", " + StringConverter::toString(*p32Idx++) + ")");
517                        j += 3;
518                    }
519                    else
520                    {
521                        l->logMessage("Triangle " + StringConverter::toString(j) +
522                            ": (" + StringConverter::toString(*p32Idx++) + ")");
523                        j++;
524                    }
525                }
526                else
527                {
528                    if (mGeometryList[i].opType == RenderOperation::OT_TRIANGLE_LIST
529                        || j == 0)
530                    {
531                        l->logMessage("Index " + StringConverter::toString(j) +
532                            ": (" + StringConverter::toString(*p16Idx++) +
533                            ", " + StringConverter::toString(*p16Idx++) +
534                            ", " + StringConverter::toString(*p16Idx++) + ")");
535                        j += 3;
536                    }
537                    else
538                    {
539                        l->logMessage("Triangle " + StringConverter::toString(j) +
540                            ": (" + StringConverter::toString(*p16Idx++) + ")");
541                        j++;
542                    }
543                }
544
545
546            }
547
548            iData->indexBuffer->unlock();
549
550
551            // Log common vertex list
552            l->logMessage(".");
553            l->logMessage("Common vertex list - vertex count " +
554                StringConverter::toString(mVertices.size()));
555            for (i = 0; i < mVertices.size(); ++i)
556            {
557                CommonVertex& c = mVertices[i];
558                l->logMessage("Common vertex " + StringConverter::toString(i) +
559                    ": (vertexSet=" + StringConverter::toString(c.vertexSet) +
560                    ", originalIndex=" + StringConverter::toString(c.originalIndex) +
561                    ", position=" + StringConverter::toString(c.position));
562            }
563        }
564
565    }
566
567
568
569}
570
Note: See TracBrowser for help on using the repository browser.