MeshCompiler.cc 98.9 KB
Newer Older
Christopher Tenter's avatar
Christopher Tenter committed
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/*===========================================================================*\
 *                                                                           *
 *                              OpenFlipper                                  *
 *      Copyright (C) 2001-2014 by Computer Graphics Group, RWTH Aachen      *
 *                           www.openflipper.org                             *
 *                                                                           *
 *---------------------------------------------------------------------------*
 *  This file is part of OpenFlipper.                                        *
 *                                                                           *
 *  OpenFlipper is free software: you can redistribute it and/or modify      *
 *  it under the terms of the GNU Lesser General Public License as           *
 *  published by the Free Software Foundation, either version 3 of           *
 *  the License, or (at your option) any later version with the              *
 *  following exceptions:                                                    *
 *                                                                           *
 *  If other files instantiate templates or use macros                       *
 *  or inline functions from this file, or you compile this file and         *
 *  link it with other files to produce an executable, this file does        *
 *  not by itself cause the resulting executable to be covered by the        *
 *  GNU Lesser General Public License. This exception does not however       *
 *  invalidate any other reasons why the executable file might be            *
 *  covered by the GNU Lesser General Public License.                        *
 *                                                                           *
 *  OpenFlipper is distributed in the hope that it will be useful,           *
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of           *
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the            *
 *  GNU Lesser General Public License for more details.                      *
 *                                                                           *
 *  You should have received a copy of the GNU LesserGeneral Public          *
 *  License along with OpenFlipper. If not,                                  *
 *  see <http://www.gnu.org/licenses/>.                                      *
 *                                                                           *
\*===========================================================================*/

/*===========================================================================*\
*                                                                            *
*   $Revision$                                                       *
*   $LastChangedBy$                                                *
*   $Date$                     *
*                                                                            *
\*===========================================================================*/

43
44
45
46
47

#include "MeshCompiler.hh"

#include <map>
#include <list>
48
#include <cassert>
49
#include <iostream>
50
#include <sstream>
51
#include <algorithm>
52
53
54
55
56
57
58
59

#ifdef USE_OPENMP
#include <omp.h>
#endif

#ifdef ACG_MC_USE_STL_HASH
#include <unordered_map> // requires c++0x
#else
60
#include <QHash>  // alternative to unordered_map
61
#endif // ACG_MC_USE_STL_HASH
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108

#include <ACG/Geometry/GPUCacheOptimizer.hh>

namespace ACG{

/*
use case


mesh with float3 pos, float2 uv, float3 n:

VertexElement elements[] = {{..}, ..};
VertexDeclaration decl;

decl.addElement(..float3 position..)
decl.addElement(..float2 uv..)
decl.addElement(..float3 normal..)

MeshCompiler mesh(decl);

mesh.setVertices(..)
mesh.setNormals(..)
mesh.setTexCoords(..)


mesh.setNumFaces(333);
mesh.setTriangles(indexBuffer);
for each face i
  mesh.setFaceMaterial(i, matID)

mesh.compile(FLAG_OPTIMIZE | FLAG_COMPUTE_TANGENTS | FLAG_STATIC)
*/


/* TODO
- default declaration (declaration can not be changed afterwards)
   float3 pos, float2 uv, float3 normal

- option to set triangle input buffer

- compile function with options
   FLAG_OPTIMIZE         : optimize for better gpu cache usage
   FLAG_COMPUTE_TANGENTS : compute tangent vectors if tangent slots are available in buffer layout
   FLAG_STATIC           : no update needed in future
*/


109
MeshCompilerVertexCompare MeshCompiler::defaultVertexCompare;
110
111
112
113
114

void MeshCompiler::AdjacencyList::init( int n )
{
  delete [] start;
  delete [] buf;
115
  delete [] count;
116
117

  num = n;
118
119
  start = new int[n];
  count = new unsigned char[n];
120
121
122
123
124
125
126

  buf   = 0; // unknown buffer length

  // invalidate start indices
  memset(start, -1, n * sizeof(int));

  // reset count
127
  memset(count, 0, n * sizeof(unsigned char));  
128
129
}

130
int MeshCompiler::AdjacencyList::getAdj( const int i, const int k ) const
131
{
Jan Möbius's avatar
Jan Möbius committed
132
  assert(k < count[i]);
133
134
135
136
137
138
139
140
  assert(k > -1);

  int st = start[i];
  assert(st > -1);

  return buf[st + k];
}

141
int MeshCompiler::AdjacencyList::getCount( const int i ) const
142
143
144
145
{
  return count[i];
}

146
void MeshCompiler::AdjacencyList::clear()
147
{
148
149
150
151
152
153
  num = 0;
  delete [] start; start = 0;
  delete [] buf; buf = 0;
  delete [] count; count = 0;
  bufSize = 0;
}
154
155
156



157
158
159
void MeshCompiler::computeAdjacency()
{
  const int numVerts = input_[inputIDPos_].count;
160
161

  // ==============================================================
162
  // compute vertex -> face adjacency
163

164
165
  // count total number of adjacency entries
  // store adj entries in a single tightly packed buffer
166

167
168
  // check if user provided adjacency information
  if (faceInput_->getVertexAdjCount(0) < 0 && adjacencyVert_.bufSize <= 0)
169
  {
170
    adjacencyVert_.init(numVerts);
171

172
173
    // count # adjacent faces per vertex
    for (int i = 0; i < numFaces_; ++i)
174
    {
175
      int nCorners = getFaceSize(i);
176

177
      for (int k = 0; k < nCorners; ++k)
178
      {
179
180
        //        int vertex = faceInput_->getSingleFaceAttr(i, k, inputIDPos_);
        int vertex = getInputIndex(i, k, inputIDPos_);
181

182
        adjacencyVert_.count[vertex]++;
183
184
185
186
      }
    }


187
188
    // count num of needed entries
    int nCounter = 0;
189

190
    for (int i = 0; i < numVerts; ++i)
191
    {
192
      adjacencyVert_.start[i] = nCounter; // save start indices
193

194
      nCounter += adjacencyVert_.count[i];
195

196
197
      adjacencyVert_.count[i] = 0; // count gets recomputed in next step
    }
198

199
200
201
    // alloc memory
    adjacencyVert_.buf = new int[nCounter];
    adjacencyVert_.bufSize = nCounter;
202

203
204
    // build adjacency list
    for (int i = 0; i < numFaces_; ++i)
205
    {
206
      int nCorners = getFaceSize(i);
207

208
      for (int k = 0; k < nCorners; ++k)
209
      {
210
211
212
        //        int vertex = faceInput_->getSingleFaceAttr(i, k, inputIDPos_);
        int vertex = getInputIndex(i, k, inputIDPos_);
        int adjIdx = adjacencyVert_.start[vertex] + adjacencyVert_.count[vertex]++;
213

214
        adjacencyVert_.buf[ adjIdx ] = i;
215
216
217
      }
    }

218
219
220
221
    //////////////////////////////////////////////////////////////////////////
    // debug version:
    // dump computed and external adjacency for comparison
//     dbgdumpAdjList("dbg_adjacency_mc.txt");
222
// 
223
//     if (faceInput_->getVertexAdjCount(0) >= 0)
224
//     {
225
226
227
228
229
230
231
232
233
234
235
236
237
238
//       FILE* file = 0;
//       file = fopen("dbg_adjacency_ext.txt", "wt");
// 
//       if (file)
//       {
//         fprintf(file, "vertex-adjacency: \n");
//         for (int i = 0; i < input_[inputIDPos_].count; ++i)
//         {
//           // sorting the adjacency list for easy comparison of adjacency input
//           int count = faceInput_->getVertexAdjCount(i);
// 
//           std::vector<int> sortedList(count);
//           for (int k = 0; k < count; ++k)
//             sortedList[k] = faceInput_->getVertexAdjFace(i, k);
239
// 
240
//           std::sort(sortedList.begin(), sortedList.end());
241
// 
242
243
244
245
246
247
248
//           for (int k = 0; k < count; ++k)
//             fprintf(file, "adj[%d][%d] = %d\n", i, k, sortedList[k]);
//         }
// 
// 
//         fclose(file);
//       }
249
//     }
250
    
251
  }
252
    
253
254
255
}


256
void MeshCompiler::setVertices( int _num, const void* _data, int _stride, bool _internalCopy /*= false*/, GLuint _fmt, int _elementSize )
257
{
258
  setAttribVec(inputIDPos_, _num, _data, _stride, _internalCopy, _fmt, _elementSize);
259
260
}

261
void MeshCompiler::setNormals( int _num, const void* _data, int _stride, bool _internalCopy /*= false*/, GLuint _fmt, int _elementSize )
262
{
263
  setAttribVec(inputIDNorm_, _num, _data, _stride, _internalCopy, _fmt, _elementSize);
264
265
}

266
void MeshCompiler::setTexCoords( int _num, const void* _data, int _stride, bool _internalCopy /*= false*/, GLuint _fmt, int _elementSize )
267
{
268
  setAttribVec(inputIDTexC_, _num, _data, _stride, _internalCopy, _fmt, _elementSize);
269
270
271
}


272
void MeshCompiler::setAttribVec(int _attrIdx, int _num, const void* _data, int _stride, bool _internalCopy /*= false*/, GLuint _fmt, int _elementSize)
273
274
275
276
277
278
279
280
281
282
283
284
285
286
{
  if (_attrIdx < 0)
    return;

  assert(_attrIdx < (int)decl_.getNumElements());

  VertexElementInput* inbuf = input_ + _attrIdx;

  inbuf->count = _num;

  int size = inbuf->attrSize = (int)VertexDeclaration::getElementSize(decl_.getElement(_attrIdx));

  if (_internalCopy)
  {
287
    delete [] inbuf->internalBuf;
288
289
290
291
292
293
294
295
296
297
    inbuf->internalBuf = new char[size * _num];
    inbuf->data = inbuf->internalBuf;

    inbuf->stride = size;

    if (_data)
    {
      // copy elementwise because of striding
      for (int i = 0; i < _num; ++i)
      {
298
299
        memcpy(inbuf->internalBuf + (size_t)(size * i),
          (const char*)_data + (size_t)(_stride * i),
300
301
302
303
304
305
306
307
308
309
310
311
          size);
      }
    }
  }
  else
  {
    inbuf->data = (const char*)_data;
    inbuf->stride = _stride ? _stride : size;

    delete [] inbuf->internalBuf;
    inbuf->internalBuf = 0;
  }
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522


  inbuf->fmt = _fmt;
  inbuf->elementSize = _elementSize;
}

void MeshCompiler::WeldList::add(const int _face, const int _corner)
{
  const int stride = meshComp->getVertexDeclaration()->getVertexStride();

  // pointer address to vertex data
  char* vtx0 = workBuf + stride * list.size();
  char* vtx1 = workBuf;

  // query vertex data
  meshComp->getInputFaceVertexData(_face, _corner, vtx0);

  bool matched = false;

  // search for same vertex that is referenced already
  for (size_t i = 0; i < list.size() && !matched; ++i)
  {
    WeldListEntry* it = &list[i];
    // query referenced vertex data

    // compare vertices
    if (cmpFunc->equalVertex(vtx0, vtx1, meshComp->getVertexDeclaration()))
    {
      // found duplicate vertex
      // -> remap index data s.t. only one these two vertices is referenced

      WeldListEntry e;
      e.faceId = _face; e.cornerId = _corner;
      e.refFaceId = it->refFaceId; e.refCornerId = it->refCornerId;

      list.push_back(e);

      matched = true;
    }

    vtx1 += stride;
  }

  // unreferenced vertex
  if (!matched)
  {
    WeldListEntry e;
    e.faceId = _face; e.cornerId = _corner;
    e.refFaceId = _face; e.refCornerId = _corner;

    list.push_back(e);
  }

}

void MeshCompiler::weldVertices()
{
  const int numVerts = input_[inputIDPos_].count;

  // clear weld map
  vertexWeldMapFace_.resize(numIndices_, -1);
  vertexWeldMapCorner_.resize(numIndices_, 0xff);

  // alloc buffer to query vertex data
  int maxAdjCount = 0;
  for (int i = 0; i < numVerts; ++i)
  {
    const int n = getAdjVertexFaceCount(i);
    maxAdjCount = std::max(n, maxAdjCount);
  }

  // OPTIMIZATION: Now the vertex compare buffer works as a vertex cache, storing interpreted vertex data.
  //  Thus, each vertex has to be interpreted only once ( when it gets inserted into the welding list )
  char* vtxCompBuf = new char[decl_.getVertexStride() * (maxAdjCount + 1)];

  WeldList weldList;
  weldList.meshComp = this;
  weldList.cmpFunc = vertexCompare_;
  weldList.workBuf = vtxCompBuf;

  weldList.list.reserve(maxAdjCount);

  for (int i = 0; i < numVerts; ++i)
  {
    // OPTIMIZATION: Moved constructor/destructor of WeldList out of for-loop
    // Create welding list for each vertex.
    weldList.list.clear();

    // Search for candidates in adjacent faces
    for (int k = 0; k < getAdjVertexFaceCount(i); ++k)
    {
      const int adjFace = getAdjVertexFace(i, k);

      // find corner id of adj face
      int adjCornerId = -1;
      for (int m = 0; m < getFaceSize(adjFace); ++m)
      {
        const int adjVertex = getInputIndex(adjFace, m, inputIDPos_);
        
        if (adjVertex == i)
        {
          adjCornerId = m;
          break;
        }
      }

      assert(adjCornerId != -1);


      // check for existing entry
      const int weldMapOffset = getInputFaceOffset(adjFace) + adjCornerId;
      
      if (vertexWeldMapFace_[weldMapOffset] >= 0)
        continue; // skip

      weldList.add(adjFace, adjCornerId);
    }


    // apply local WeldList of a vertex to global weld map

    for (size_t e = 0; e < weldList.list.size(); ++e)
    {
      const WeldListEntry* it = &weldList.list[e];
      const int weldMapOffset = getInputFaceOffset(it->faceId) + it->cornerId;

      if (vertexWeldMapFace_[weldMapOffset] >= 0)
        continue; // skip

      // store in map
      vertexWeldMapFace_[weldMapOffset] = it->refFaceId;
      vertexWeldMapCorner_[weldMapOffset] = it->refCornerId;
    }
  }


  // -------------------------------------------------------------
  // Alternative method that avoids iterating over adjacency list at cost of higher memory load
  // Could not measure any noticeable difference in run-time performance.
// 
//   std::vector< std::vector< std::pair<int,int> > > VertexColMap;
//   VertexColMap.resize(numVerts);
// 
//   for (int i = 0; i < numVerts; ++i)
//     VertexColMap[i].reserve( getAdjVertexFaceCount(i) );
// 
//   for (int i = 0; i < numFaces_; ++i)
//   {
//     for (int k = 0; k < getFaceSize(i); ++k)
//     {
//       int v = faceInput_->getSingleFaceAttr(i, k, inputIDPos_);
// 
//       VertexColMap[v].push_back( std::pair<int,int>(i,k) );
//     }
//   }
// 
//   for (int i = 0; i < numVerts; ++i)
//   {
//     // Create welding list for each vertex.
//     WeldList weldList;
//     weldList.meshComp = this;
//     weldList.cmpFunc = vertexCompare_;
//     weldList.workBuf = vtxCompBuf;
// 
//     for (int k = 0; k < VertexColMap[i].size(); ++k)
//       weldList.add(VertexColMap[i][k].first, VertexColMap[i][k].second);
// 
//     // apply local WeldList of a vertex to global weld map
// 
// //     for (std::list< WeldListEntry >::iterator it = weldList.list.begin();
// //       it != weldList.list.end();  ++ it)
//     for (size_t e = 0; e < weldList.list.size(); ++e)
//     {
//       const WeldListEntry* it = &weldList.list[e];
//       const int weldMapOffset = getInputFaceOffset(it->faceId) + it->cornerId;
// 
// //      if (vertexWeldMap_[weldMapOffset].first >= 0)
//       if (vertexWeldMapFace_[weldMapOffset] >= 0)
//         continue; // skip
// 
//       // store in map
// //      vertexWeldMap_[weldMapOffset] = std::pair<int, int> ( it->refFaceId, it->refCornerId );
//       vertexWeldMapFace_[weldMapOffset] = it->refFaceId;
//       vertexWeldMapCorner_[weldMapOffset] = it->refCornerId;
//     }
//   }
//   // -------------------------------------------------------------


  // fix incomplete welding map (isolated vertices)
  fixWeldMap();

  delete [] vtxCompBuf;
}

void MeshCompiler::fixWeldMap()
{
  for (int i = 0; i < numFaces_; ++i)
  {
    const int fsize = getFaceSize(i);
    for (int k = 0; k < fsize; ++k)
    {
      const int weldMapOffset = getInputFaceOffset(i) + k;

      if (vertexWeldMapFace_[weldMapOffset] < 0)
      {
        vertexWeldMapFace_[weldMapOffset] = i;
        vertexWeldMapCorner_[weldMapOffset] = k;
      }
    }
  }
523
524
}

525
526
527
528
529
530
531
void MeshCompiler::findIsolatedVertices()
{
  const int nVerts = input_[inputIDPos_].count;

  numIsolatedVerts_ = 0;
  // For each vertex check if there exists a reference in the splitting list. We have found an isolated vertex if there is no reference.
  //  Checking the vertex-face adjacency count is also possible to detect isolated vertices.
532

533
534
535
536
537
  for (int i = 0; i < nVerts; ++i)
  {
    if (splitter_->isIsolated(i))
      ++numIsolatedVerts_;
  }
538

539
540
541
542
543
544
545
546
  isolatedVertices_.clear();
  isolatedVertices_.reserve(numIsolatedVerts_);
  for (int i = 0; i < nVerts; ++i)
  {
    if (splitter_->isIsolated(i))
      isolatedVertices_.push_back(i);
  }
}
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579

void MeshCompiler::splitVertices()
{
  /* algorithm overview

  we split by indices only,
  actual vertex data will not be taken into account.

  thus if the input contains two vertices with the same value,
  they still are treated as different vertices since they have different indices


  a shared vertex gets split whenever at least one attribute
  changes with respect to the face.
  i.e. one face wants to combine vertex i with attribute j
  while another face needs it with attribute k

  example:

  face 0 and 5 share vertex v3

  face 0 uses v3 combined with normal n0,
  but face 5 wants to have v3 with normal n1


  we look up if v3 has been split up already and search
  for a v3-n0 combination
  eventually this combination is added to the splitting list

  repeat for the v3-n1 combination

  */

580
581
582
583
  const int numPositions = input_[inputIDPos_].count;

  // estimate number of splits
  int estimatedSplitCount = 0;
584
  int numDifferentInputCounts = 0;
585

586
587
588
589
590
591
592
  for (int i = 0; i < numAttributes_; ++i)
  {
    if (i != inputIDPos_)
    {
      if (input_[i].count > numPositions)
      {
        const int diff = input_[i].count - numPositions;
593

594
595
596
597
598
        if (diff > 0)
        {
          estimatedSplitCount = std::max(diff, estimatedSplitCount);
          ++numDifferentInputCounts;
        }
599
600
      }
    }
601
602
  }

603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
  if (numDifferentInputCounts > 1)
  {
    // estimation probably too small, increase by 20 %
    estimatedSplitCount = int(float(estimatedSplitCount) * 1.2f);
  }

  assert(estimatedSplitCount >= 0);

  // worst case: each vertex can be used by only one face
  //  clamp estimation-count accordingly

  int maxSplitCount = 0;

  if (numIndices_ > 0)
  {
    if (numIndices_ > numPositions)
      maxSplitCount = numIndices_ - numPositions;
  }
  else
  {
    // numIndices_ is unknown
    int sumFaceSize = 0;

    if (constantFaceSize_)
      sumFaceSize = numFaces_ * maxFaceSize_;
    else
    {
      for (int i = 0; i < numFaces_; ++i)
        sumFaceSize += getFaceSize(i);
    }

    if (sumFaceSize > numPositions)
      maxSplitCount = sumFaceSize - numPositions;
  }

  estimatedSplitCount = std::min(estimatedSplitCount, maxSplitCount);

//  std::cout << "estimated split count: " << estimatedSplitCount << std::endl;
641

642
643
  delete splitter_;
  splitter_ = new VertexSplitter(decl_.getNumElements(),
644
645
646
                                 numPositions,
                                 numPositions + estimatedSplitCount,
                                 0.0f);
647
648
649
650
651
652
653
654
655
656
657
658
659

  faceBufSplit_.resize(numIndices_, -1);

  // count # vertices after splitting
  numDrawVerts_ = 0;

  for (int i = 0; i < numFaces_; ++i)
  {
    const int fsize = getFaceSize(i);
    for (int k = 0; k < fsize; ++k)
    {
      int vertex[16];

660
661

      getInputFaceVertex_Welded(i, k, vertex);
662
663
664

      // split vertices by index data only
      // value of position, normal etc. are not considered
665
      const int idx = splitter_->split(vertex);
666
667
668
669
670

      // handle index storage
      setInputIndexSplit(i, k, idx);
    }
  }
671
672


673
674
675
676
//  std::cout << "actual split count: " << (numDrawVerts_ - numPositions) << std::endl;



677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
  // Fix splitting list if there are isolated vertices in between.
  // Isolated vertices currently occupy spots in in the interleaved vertex buffer.
  // -> Remove them from the vbo.
  findIsolatedVertices();

  if (numIsolatedVerts_ > 0)
  {
    // create table that stores how many isolated vertices have been encountered up to each vertex
    std::vector<int> IsoFix(numPositions, 0);

    int fixIndex = 0;
    for (int i = 0; i < numPositions; ++i)
    {
      if (splitter_->isIsolated(i))
        fixIndex--;

      IsoFix[i] = fixIndex;
    }

    numDrawVerts_ = 0;

    // apply index fixing table
    for (int i = 0; i < numFaces_; ++i)
    {
      const int fsize = getFaceSize(i);
      for (int k = 0; k < fsize; ++k)
      {
        // get vertex position id
        int vertex[16];
        getInputFaceVertex_Welded(i, k, vertex);

        // fix interleaved index
        int idx = getInputIndexSplit(i, k);
        idx += IsoFix[vertex[0]];
        setInputIndexSplit(i, k, idx);
      }
    }
  }
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
}


void MeshCompiler::forceUnsharedFaceVertex()
{
  // ==============================================
  //  face normal fix
  //  make sure that each triangle has at least one unique unshared vertex
  //  this vertex can store per face attributes when needed

  // the used algorithm is optimal (min split count) for any n-poly mesh
  //  however, this step should be done before triangulation
  //  and faces have to be triangulated in fans to ensure
  //  that each triangle makes use of the face-specific vertex


  std::vector<int> sharedVertices;
732
  sharedVertices.resize(maxFaceSize_);
733
734

  std::vector<int> tmpFaceVerts; // used for face rotation-swap
735
  tmpFaceVerts.resize(maxFaceSize_);
736
737
738

  faceRotCount_.resize(numFaces_, 0);

739
740
741
742
  int numInitialVerts = numDrawVerts_;
  char* VertexUsed = new char[numDrawVerts_];
  memset(VertexUsed, 0, sizeof(char) * numDrawVerts_);

743
744
745
  for (int faceID = 0; faceID < numFaces_; ++faceID)
  {
    const int numCorners = getFaceSize(faceID);
746
    
747
    // reset shared list
748
    memset(&sharedVertices[0], 0, sizeof(int) * maxFaceSize_);
749
750
    int numShared = 0;

751
752
753
754
    for (int v0 = 0; v0 < numCorners && numShared < numCorners; ++v0)
    {
      if (sharedVertices[v0])
        continue;
755

756
      const int vertexID0 = getInputIndexSplit(faceID, v0);
757

758
759
760
761
      if (vertexID0 >= numInitialVerts || VertexUsed[vertexID0])
      {
        sharedVertices[v0] = true;
        ++numShared;
762
763
764
765
766
767
768
769
770
      }
    }


    if (numShared == numCorners)
    {
      // worst-case: all vertices shared with neighbors

      // add split vertex to end of vertex buffer, which is used exclusively by the current face
771
      // current vertex count is stored in numDrawVerts_
772

773
      setInputIndexSplit(faceID, 0, numDrawVerts_);
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
    }
    else if (sharedVertices[0])
    {
      // validation code
      int x = 0;
      for (int i = 0; i < numCorners; ++i)
        x += sharedVertices[i];
      assert(x < numCorners);

      // we have to make sure that an unshared vertex is the first referenced face vertex
      // this is currently not the case, so rotate the face indices until this is true

      // make copy of current face splitVertexID
      for (int i = 0; i < numCorners; ++i)
        tmpFaceVerts[i] = getInputIndexSplit(faceID, i);

      // rotation order: i -> i+1
      // find # rotations needed
      int rotCount = 1;
      for (; rotCount < numCorners; ++rotCount)
      {
        if (!sharedVertices[rotCount % numCorners])
796
797
798
        {
          if (tmpFaceVerts[rotCount] < numInitialVerts)
            VertexUsed[tmpFaceVerts[rotCount]] = 1;
799
          break;
800
        }
801
802
803
804
805
806
807
808
809
810
811
812
      }

      assert(rotCount < numCorners);

      // rotate:  i -> i+rotCount
      rotCount = numCorners - rotCount;

      faceRotCount_[faceID] = rotCount;
   
      for (int i = 0; i < numCorners; ++i)
        setInputIndexSplit(faceID, (i + rotCount)%numCorners, tmpFaceVerts[i]);
    }
813
814
815
816
817
818
819
    else
    {
      // best-case: unshared vertex at corner 0
      const int idx = getInputIndexSplit(faceID, 0);
      if (idx < numInitialVerts)
        VertexUsed[idx] = 1;
    }
820
821
822

  }

823
824
  delete [] VertexUsed;

825
826
}

827
void MeshCompiler::getInputFaceVertex( const int _face, const int _corner, int* _out ) const
828
829
{
  for (unsigned int k = 0; k < decl_.getNumElements(); ++k)
830
    _out[k] = getInputIndex(_face, _corner, k);
831
832
}

833
void MeshCompiler::getInputFaceVertex_Welded( const int i, const int j, int* _out ) const
834
835
836
{
  int face = i;
  int corner = j;
837

838
839
840
841
  // apply welding map if available
  if (!vertexWeldMapFace_.empty())
  {
    const int offset = getInputFaceOffset(i);
842

843
844
845
    face = vertexWeldMapFace_[offset + j];
    corner = vertexWeldMapCorner_[offset + j];
  }
846

847
848
849
  for (unsigned int k = 0; k < decl_.getNumElements(); ++k)
    _out[k] = getInputIndex(face, corner, k);
}
850

851
void MeshCompiler::getInputFaceVertexData( const int _faceId, const int _corner, void* _out ) const
852
{
853
854
855
856
  for (int i = 0; i < numAttributes_; ++i)
  {
    const VertexElement* el = decl_.getElement(i);

857
    const int idx = getInputIndex(_faceId, _corner, i);
858
859
860
861
862
863
864
865
866
867
868
869

    input_[i].getElementData(idx, (char*)_out + (size_t)el->pointer_, el);
  }
}




MeshCompiler::MeshCompiler(const VertexDeclaration& _decl)
: decl_(_decl)
{
  faceInput_ = 0;
870
871
872
873
874
875
876
  deleteFaceInputeData_ = false;

  splitter_ = 0;
  numSubsets_ = 0;
  numIndices_ = 0;
  numTris_ = 0;

Christopher Tenter's avatar
Christopher Tenter committed
877
878
879
  numFaces_ = 0;
  curFaceInputPos_ = 0;

880
881
882
  indices_ = 0;

  numDrawVerts_ = 0;
883
  numIsolatedVerts_ = 0;
884

885
886
887
888
889
  maxFaceSize_ = 0;
  constantFaceSize_ = false;

  provokingVertex_ = -1;
  provokingVertexSetByUser_ = false;
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906

  // search for convenient attribute indices
  numAttributes_ = decl_.getNumElements();
  inputIDNorm_ = inputIDPos_ = inputIDTexC_ = -1;

  for (int i = 0; i < (int)decl_.getNumElements(); ++i)
  {
    const VertexElement* e = decl_.getElement(i);

    switch (e->usage_)
    {
    case VERTEX_USAGE_POSITION: inputIDPos_ = i; break;
    case VERTEX_USAGE_NORMAL: inputIDNorm_ = i; break;
    case VERTEX_USAGE_TEXCOORD: inputIDTexC_ = i; break;
    default: break;
    }
  }
907
908
909
910


  vertexCompare_ = &defaultVertexCompare;

911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
}

MeshCompiler::~MeshCompiler()
{
  if (!triIndexBuffer_.empty() && indices_ != &triIndexBuffer_[0])
    delete [] indices_;


  if (deleteFaceInputeData_)
    delete faceInput_;

  delete splitter_;
}


int MeshCompiler::getInputIndexOffset( const int _face, const int _corner, const bool _rotation ) const
{
  assert(_face >= 0);
  assert(_face < numFaces_);

Jan Möbius's avatar
Jan Möbius committed
931
  const int baseIdx = int(