MeshCompiler.cc 114 KB
Newer Older
Christopher Tenter's avatar
Christopher Tenter committed
1
2
3
/*===========================================================================*\
 *                                                                           *
 *                              OpenFlipper                                  *
Jan Möbius's avatar
Jan Möbius committed
4
5
6
7
 *           Copyright (c) 2001-2015, RWTH-Aachen University                 *
 *           Department of Computer Graphics and Multimedia                  *
 *                          All rights reserved.                             *
 *                            www.openflipper.org                            *
Christopher Tenter's avatar
Christopher Tenter committed
8
9
 *                                                                           *
 *---------------------------------------------------------------------------*
Jan Möbius's avatar
Jan Möbius committed
10
11
12
13
14
15
 * This file is part of OpenFlipper.                                         *
 *---------------------------------------------------------------------------*
 *                                                                           *
 * Redistribution and use in source and binary forms, with or without        *
 * modification, are permitted provided that the following conditions        *
 * are met:                                                                  *
Christopher Tenter's avatar
Christopher Tenter committed
16
 *                                                                           *
Jan Möbius's avatar
Jan Möbius committed
17
18
 * 1. Redistributions of source code must retain the above copyright notice, *
 *    this list of conditions and the following disclaimer.                  *
Christopher Tenter's avatar
Christopher Tenter committed
19
 *                                                                           *
Jan Möbius's avatar
Jan Möbius committed
20
21
22
 * 2. Redistributions in binary form must reproduce the above copyright      *
 *    notice, this list of conditions and the following disclaimer in the    *
 *    documentation and/or other materials provided with the distribution.   *
Christopher Tenter's avatar
Christopher Tenter committed
23
 *                                                                           *
Jan Möbius's avatar
Jan Möbius committed
24
25
26
 * 3. Neither the name of the copyright holder nor the names of its          *
 *    contributors may be used to endorse or promote products derived from   *
 *    this software without specific prior written permission.               *
Christopher Tenter's avatar
Christopher Tenter committed
27
 *                                                                           *
Jan Möbius's avatar
Jan Möbius committed
28
29
30
31
32
33
34
35
36
37
38
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS       *
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED *
 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A           *
 * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER *
 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,  *
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,       *
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR        *
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF    *
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING      *
 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS        *
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.              *
Christopher Tenter's avatar
Christopher Tenter committed
39
40
41
42
43
44
45
46
47
48
49
 *                                                                           *
\*===========================================================================*/

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

50
51
52
53

#include "MeshCompiler.hh"

#include <iostream>
54
#include <sstream>
55
56
57
58
59
60
61

#ifdef USE_OPENMP
#endif

#ifdef ACG_MC_USE_STL_HASH
#include <unordered_map> // requires c++0x
#else
62
#include <QHash>  // alternative to unordered_map
63
#endif // ACG_MC_USE_STL_HASH
64
65

#include <ACG/Geometry/GPUCacheOptimizer.hh>
Christopher Tenter's avatar
Christopher Tenter committed
66
#include <ACG/Geometry/Triangulator.hh>
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
109
110
111

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
*/


112
MeshCompilerVertexCompare MeshCompiler::defaultVertexCompare;
113
114
115
116
117

void MeshCompiler::AdjacencyList::init( int n )
{
  delete [] start;
  delete [] buf;
118
  delete [] count;
119
120

  num = n;
121
122
  start = new int[n];
  count = new unsigned char[n];
123
124
125
126
127
128
129

  buf   = 0; // unknown buffer length

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

  // reset count
130
  memset(count, 0, n * sizeof(unsigned char));  
131
132
}

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

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

  return buf[st + k];
}

144
int MeshCompiler::AdjacencyList::getCount( const int i ) const
145
146
147
148
{
  return count[i];
}

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



160
void MeshCompiler::computeAdjacency(bool _forceRecompute)
161
162
{
  const int numVerts = input_[inputIDPos_].count;
163
164

  // ==============================================================
165
  // compute vertex -> face adjacency
166

167
168
  // count total number of adjacency entries
  // store adj entries in a single tightly packed buffer
169

170
  // check if user provided adjacency information
171
  if (_forceRecompute || (faceInput_->getVertexAdjCount(0) < 0 && adjacencyVert_.bufSize <= 0))
172
  {
173
    adjacencyVert_.init(numVerts);
174

175
176
    // count # adjacent faces per vertex
    for (int i = 0; i < numFaces_; ++i)
177
    {
178
      int nCorners = getFaceSize(i);
179

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

185
        adjacencyVert_.count[vertex]++;
186
187
188
189
      }
    }


190
191
    // count num of needed entries
    int nCounter = 0;
192

193
    for (int i = 0; i < numVerts; ++i)
194
    {
195
      adjacencyVert_.start[i] = nCounter; // save start indices
196

197
      nCounter += adjacencyVert_.count[i];
198

199
200
      adjacencyVert_.count[i] = 0; // count gets recomputed in next step
    }
201

202
203
204
    // alloc memory
    adjacencyVert_.buf = new int[nCounter];
    adjacencyVert_.bufSize = nCounter;
205

206
207
    // build adjacency list
    for (int i = 0; i < numFaces_; ++i)
208
    {
209
      int nCorners = getFaceSize(i);
210

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

217
        adjacencyVert_.buf[ adjIdx ] = i;
218
219
220
      }
    }

221
222
223
224
    //////////////////////////////////////////////////////////////////////////
    // debug version:
    // dump computed and external adjacency for comparison
//     dbgdumpAdjList("dbg_adjacency_mc.txt");
225
// 
226
//     if (faceInput_->getVertexAdjCount(0) >= 0)
227
//     {
228
229
230
231
232
233
234
235
236
237
238
239
240
241
//       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);
242
// 
243
//           std::sort(sortedList.begin(), sortedList.end());
244
// 
245
246
247
248
249
250
251
//           for (int k = 0; k < count; ++k)
//             fprintf(file, "adj[%d][%d] = %d\n", i, k, sortedList[k]);
//         }
// 
// 
//         fclose(file);
//       }
252
//     }
253
    
254
  }
255
    
256
257
258
}


Jan Möbius's avatar
Jan Möbius committed
259
void MeshCompiler::setVertices( size_t _num, const void* _data, size_t _stride, bool _internalCopy /*= false*/, GLuint _fmt, int _elementSize )
260
{
261
  setAttribVec(inputIDPos_, _num, _data, _stride, _internalCopy, _fmt, _elementSize);
262
263
}

Jan Möbius's avatar
Jan Möbius committed
264
void MeshCompiler::setNormals( size_t _num, const void* _data, size_t _stride, bool _internalCopy /*= false*/, GLuint _fmt, int _elementSize )
265
{
266
  setAttribVec(inputIDNorm_, _num, _data, _stride, _internalCopy, _fmt, _elementSize);
267
268
}

Jan Möbius's avatar
Jan Möbius committed
269
void MeshCompiler::setTexCoords( size_t _num, const void* _data, size_t _stride, bool _internalCopy /*= false*/, GLuint _fmt, int _elementSize )
270
{
271
  setAttribVec(inputIDTexC_, _num, _data, _stride, _internalCopy, _fmt, _elementSize);
272
273
274
}


Jan Möbius's avatar
Jan Möbius committed
275
void MeshCompiler::setAttribVec(int _attrIdx, size_t _num, const void* _data, size_t _stride, bool _internalCopy /*= false*/, GLuint _fmt, int _elementSize)
276
{
277
278
279
280
281
282
283
284
  // sets vertex data for each attribute individually
  // Example:
  // Format: float3 pos, float2 uv, float3 normal has 3 attribute vectors, that store all positions, texcoords etc. of the mesh
  // - positions: float3[n1]  n1: number of positions
  // - texcoords: float2[n2]  n2: number of texcoords
  // - normals: float3[n3]    n3: number of normals
  //  the vector sizes n1, n2, n3 do not have to be equal!

285
286
287
288
289
290
291
292
293
  if (_attrIdx < 0)
    return;

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

  VertexElementInput* inbuf = input_ + _attrIdx;

  inbuf->count = _num;

294
  // size in bytes of one vertex element (eg. 12 for float3 element)
295
296
  int size = inbuf->attrSize = (int)VertexDeclaration::getElementSize(decl_.getElement(_attrIdx));

297
298

  // make an internal copy of the input if the user can not guarantee, that the data address is permanently valid
299
300
  if (_internalCopy)
  {
301
    delete [] inbuf->internalBuf;
302
303
304
305
306
307
308
309
    inbuf->internalBuf = new char[size * _num];
    inbuf->data = inbuf->internalBuf;

    inbuf->stride = size;

    if (_data)
    {
      // copy elementwise because of striding
Jan Möbius's avatar
Jan Möbius committed
310
      for (size_t i = 0; i < _num; ++i)
311
      {
312
313
        memcpy(inbuf->internalBuf + (size_t)(size * i),
          (const char*)_data + (size_t)(_stride * i),
314
315
316
317
318
319
          size);
      }
    }
  }
  else
  {
320
    // store data address only without making a copy
321
322
323
324
325
326
    inbuf->data = (const char*)_data;
    inbuf->stride = _stride ? _stride : size;

    delete [] inbuf->internalBuf;
    inbuf->internalBuf = 0;
  }
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


  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);
388
  vertexWeldMapCorner_.resize(numIndices_, -1);
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408

  // 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);

409
410
  bool retry = false;
  
411
412
413
414
415
416
417
  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
418
419
    int numAdjFaces = getAdjVertexFaceCount(i);
    for (int k = 0; k < numAdjFaces; ++k)
420
421
422
423
    {
      const int adjFace = getAdjVertexFace(i, k);

      // find corner id of adj face
424
      int adjFaceSize = getFaceSize(adjFace);
425
      int adjCornerId = -1;
426
      for (int m = 0; m < adjFaceSize; ++m)
427
428
429
430
431
432
433
434
435
436
      {
        const int adjVertex = getInputIndex(adjFace, m, inputIDPos_);
        
        if (adjVertex == i)
        {
          adjCornerId = m;
          break;
        }
      }

437
438
439
440
441
442
443
444
445
446
447
      if (adjCornerId < 0)
      {
        // user provided adjacency is faulty
        // retry with internally compute adjacency
        retry = true;
        break;
      }
      else
      {
        // check for existing entry
        const int weldMapOffset = getInputFaceOffset(adjFace) + adjCornerId;
448

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

452
453
        weldList.add(adjFace, adjCornerId);
      }
454
455
456
457
    }


    // apply local WeldList of a vertex to global weld map
458
    if (!retry)
459
    {
460
461
462
463
      for (size_t e = 0; e < weldList.list.size(); ++e)
      {
        const WeldListEntry* it = &weldList.list[e];
        const int weldMapOffset = getInputFaceOffset(it->faceId) + it->cornerId;
464

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

468
469
470
471
        // store in map
        vertexWeldMapFace_[weldMapOffset] = it->refFaceId;
        vertexWeldMapCorner_[weldMapOffset] = it->refCornerId;
      }
472
    }
473
474
    else
      break;
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
523
524
525
526
527
528
529
530
531
  // -------------------------------------------------------------
  // 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;
//     }
//   }
//   // -------------------------------------------------------------

532
533
534
535
536
537
538
539
540
541
  if (retry)
  {
    if (adjacencyVert_.bufSize <= 0)
    {
      // there is an issue with the external vertex-face adjacency list provided with the input interface

      // 1. compute internal adjacency list and use that instead
      computeAdjacency(true);

      // 2. rollback welding progress
542

543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
      vertexWeldMapFace_.clear();
      vertexWeldMapCorner_.clear();

      // 3. try again with updated adjacency
      weldVertices();
    }
    else
    {
      // something went badly wrong..
      std::cerr << "MeshCompiler - faulty internal adjacency list" << std::endl;
    }
  }
  else
  {
    // fix incomplete welding map (isolated vertices)
    fixWeldMap();
  }
560
561
562
563
564
565
566
567
568
569
570
571
572

  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;

Christopher Tenter's avatar
Christopher Tenter committed
573
574
      // if a (face,corner) pair is mapped to an invalid value, make it valid by mapping to itself
      // invalid value is caused by isolated vertices
575
576
577
578
579
580
581
      if (vertexWeldMapFace_[weldMapOffset] < 0)
      {
        vertexWeldMapFace_[weldMapOffset] = i;
        vertexWeldMapCorner_[weldMapOffset] = k;
      }
    }
  }
582
583
}

584
585
586
587
588
589
590
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.
591

592
593
594
595
596
  for (int i = 0; i < nVerts; ++i)
  {
    if (splitter_->isIsolated(i))
      ++numIsolatedVerts_;
  }
597

598
599
600
601
602
603
604
605
  isolatedVertices_.clear();
  isolatedVertices_.reserve(numIsolatedVerts_);
  for (int i = 0; i < nVerts; ++i)
  {
    if (splitter_->isIsolated(i))
      isolatedVertices_.push_back(i);
  }
}
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

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

  */

639
640
  const int numPositions = input_[inputIDPos_].count;

641
  // estimate number of splits to avoid resizing too often
642
  int estimatedSplitCount = 0;
643
  int numDifferentInputCounts = 0;
644

645
646
647
  // simple heuristic:
  // if the number of elements of an arbitrary attribute is larger than the number of positions, add the difference to the number of splits
  //  the actual number of splits may be larger, in which case the array has to be resized.
648
649
650
651
652
653
654
  for (int i = 0; i < numAttributes_; ++i)
  {
    if (i != inputIDPos_)
    {
      if (input_[i].count > numPositions)
      {
        const int diff = input_[i].count - numPositions;
655

656
657
658
659
660
        if (diff > 0)
        {
          estimatedSplitCount = std::max(diff, estimatedSplitCount);
          ++numDifferentInputCounts;
        }
661
662
      }
    }
663
664
  }

665
666
667
668
669
670
671
672
673
674
675
676
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
  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;
703

704
  // split vertices such that each index combination of a face corner (i_pos, i_uv, i_attr..) has a unique vertex id and the number of vertices is minimal
705
706
  delete splitter_;
  splitter_ = new VertexSplitter(decl_.getNumElements(),
707
708
709
                                 numPositions,
                                 numPositions + estimatedSplitCount,
                                 0.0f);
710
711
712
713
714
715
716
717
718
719
720

  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)
    {
721
722
      // indices of the face vertex into the attribute vectors
      int vertex[16];  // {i_pos, i_attr1, i_attr2 ..}
723

724

725
      // get indices of a face corner after welding
726
      getInputFaceVertex_Welded(i, k, vertex);
727
728
729

      // split vertices by index data only
      // value of position, normal etc. are not considered
730
      const int idx = splitter_->split(vertex);
731
732
733
734
735

      // handle index storage
      setInputIndexSplit(i, k, idx);
    }
  }
736
737


738
739
740
741
//  std::cout << "actual split count: " << (numDrawVerts_ - numPositions) << std::endl;



742
743
744
745
746
747
748
749
  // 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
750
751
    //  this is done in the index domain after splitting
    std::vector<int> IsoFix(splitter_->numVerts, 0);
752
753

    int fixIndex = 0;
754
    for (int i = 0; i < splitter_->numVerts; ++i)
755
756
757
758
759
760
761
    {
      if (splitter_->isIsolated(i))
        fixIndex--;

      IsoFix[i] = fixIndex;
    }

762
763
    // IsoFix[] array contains offsets <= 0 for each split vertex id.
    // It maps from such an id to the vbo index, which does not contain any isolates.
Christopher Tenter's avatar
Christopher Tenter committed
764
    // Isolates may be appended later to the vbo if the user wants that.
765

766
767
    numDrawVerts_ = 0;

Christopher Tenter's avatar
Christopher Tenter committed
768
    // apply index fixing table to current vertex ids
769
770
771
772
773
    for (int i = 0; i < numFaces_; ++i)
    {
      const int fsize = getFaceSize(i);
      for (int k = 0; k < fsize; ++k)
      {
Christopher Tenter's avatar
Christopher Tenter committed
774
        // get interleaved vertex id for (i, k) after splitting
775
        int idx = getInputIndexSplit(i, k);
Christopher Tenter's avatar
Christopher Tenter committed
776

777
778
779
        // idx is the split vertex id of (i, k)
        // IsoFix[idx] is the offset that has to be applied to that
        idx += IsoFix[idx];
Christopher Tenter's avatar
Christopher Tenter committed
780
781

        // store fixed vertex id
782
783
784
785
        setInputIndexSplit(i, k, idx);
      }
    }
  }
786
787
788
}


789
790
791
792
793
bool MeshCompiler_forceUnsharedFaceVertex_InnerValenceSorter( const std::pair<int, int>& a, const std::pair<int, int>& b )
{
  return a.second > b.second;
}

794
795
796
797
798
799
800
801
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


Christopher Tenter's avatar
Christopher Tenter committed
802
803
  // sharedVertex[i] = 1 iff the vertex id of corner i is shared with any neighboring face
  // sharedVertex is computed on-the-fly for each face
804
  std::vector<int> sharedVertices;
805
  sharedVertices.resize(maxFaceSize_);
806

Christopher Tenter's avatar
Christopher Tenter committed
807
  // temporary copy of the vertex ids of a face
808
  std::vector<int> tmpFaceVerts; // used for face rotation-swap
809
  tmpFaceVerts.resize(maxFaceSize_);
810

811
  int numInitialVerts = numDrawVerts_;
812
813
814
815
816
817
  std::vector<int> VertexUsed(numDrawVerts_, -1); // marks vertices which are not shared with any neighboring face


  // process all n-polygons first

  /*
Christopher Tenter's avatar
Christopher Tenter committed
818
  new and better algorithm:   O(n * m^2) where n = numFaces, m = faceSize
819

820
821
  for each face:

Christopher Tenter's avatar
Christopher Tenter committed
822
    trisCovered = 0;
823

Christopher Tenter's avatar
Christopher Tenter committed
824
825
826
    while (trisCovered < faceSize)
    {
      compute inner valence of all corners in the remaining polygon
827

Christopher Tenter's avatar
Christopher Tenter committed
828
      add 'best' corner: - highest inner valence and unused by other tris
829

Christopher Tenter's avatar
Christopher Tenter committed
830
831
832
833
834
      for each triangle affected by this corner
        rotate triIndexBuffer entries of the tri
        remove tri from the remaining triangle list
        ++ trisCovered
    }
835
836
  */
  int triCounter = 0;
837
838


839
840
841
842
843
  for (int sortFaceID = 0; sortFaceID < numFaces_; ++sortFaceID)
  {
    // get original face id
    const int faceID = faceSortMap_.empty() ? sortFaceID : faceSortMap_[sortFaceID];

Christopher Tenter's avatar
Christopher Tenter committed
844
    const int faceSize = getFaceSize(faceID);
845

Christopher Tenter's avatar
Christopher Tenter committed
846
    if (faceSize > 3)
847
    {
Christopher Tenter's avatar
Christopher Tenter committed
848
849
      // vertexPriorities[priority] = pair(cornerID, valence)
      std::vector< std::pair<int, int> > vertexPriorities(faceSize);
850

Christopher Tenter's avatar
Christopher Tenter committed
851
852
853
      // linked ring list for all the triangles in the uncovered triangulation
      // ie. nextTri = remainingTris[currentTri];
      const int faceTris = faceSize - 2;
854

Christopher Tenter's avatar
Christopher Tenter committed
855
856
857
      std::vector<RingTriangle> remainingTris(faceTris);
      for (int i = 0; i < faceTris; ++i)
        remainingTris[i] = RingTriangle(i, &remainingTris[(i + faceTris - 1) % faceTris], &remainingTris[(i + 1) % faceTris]);
858
859


Christopher Tenter's avatar
Christopher Tenter committed
860
861
      RingTriangle* currentTri = &remainingTris[0];
      int numTrisCovered = 0;
862

Christopher Tenter's avatar
Christopher Tenter committed
863
      while (numTrisCovered < faceTris)
864
      {
Christopher Tenter's avatar
Christopher Tenter committed
865
866
867
        // compute valence of vertices within the remaining triangulation
        for (int k = 0; k < faceSize; ++k)
          vertexPriorities[k] = std::pair<int, int>(k, 0);
868

Christopher Tenter's avatar
Christopher Tenter committed
869
870
871
        RingTriangle* startTri = currentTri;
        int numRemainingTris = faceTris - numTrisCovered;
        for (int t = 0; t < numRemainingTris; ++t)
872
        {
Christopher Tenter's avatar
Christopher Tenter committed
873
874
875
876
877
878
879
880
          for (int k = 0; k < 3; ++k)
          {
            int cornerID = -1 - triIndexBuffer_[(triCounter + currentTri->id) * 3 + k];
            ++vertexPriorities[cornerID].second;
          }
          currentTri = currentTri->next;
        }
        assert(currentTri == startTri);
881

Christopher Tenter's avatar
Christopher Tenter committed
882
883
        // sort by valence
        std::sort(vertexPriorities.begin(), vertexPriorities.end(), MeshCompiler_forceUnsharedFaceVertex_InnerValenceSorter);
884

Christopher Tenter's avatar
Christopher Tenter committed
885
886
887
888
889
        // find a good corner
        int goodCorner = -1;
        int goodVertexID = -1;
        int bestValence = -1;
        for (int k = 0; k < faceSize && vertexPriorities[k].second; ++k)
890
        {
Christopher Tenter's avatar
Christopher Tenter committed
891
892
893
894
          int cornerID = vertexPriorities[k].first;
          int vertexID = getInputIndexSplit(faceID, cornerID);

          int valence = vertexPriorities[k].second;
895

Christopher Tenter's avatar
Christopher Tenter committed
896
          if (vertexID >= numInitialVerts || (VertexUsed[vertexID] == faceID))
897
          {
Christopher Tenter's avatar
Christopher Tenter committed
898
899
900
901
902
903
            // best case, this vertex is already owned by the polygon
            // stop the search
            goodCorner = cornerID;
            goodVertexID = vertexID;
            bestValence = valence;
            break;
904
          }
Christopher Tenter's avatar
Christopher Tenter committed
905
          else if (VertexUsed[vertexID] < 0 && bestValence < valence)
906
          {
Christopher Tenter's avatar
Christopher Tenter committed
907
908
909
            goodCorner = cornerID; // best for now, but continue the search
            goodVertexID = vertexID;
            bestValence = valence;
910
          }
Christopher Tenter's avatar
Christopher Tenter committed
911
        }
912
913


Christopher Tenter's avatar
Christopher Tenter committed
914
915
916
917
918
        // maybe add a new vertex
        if (goodCorner < 0)
        {
          // have to add a new vertex
          // use the one with highest inner valence
919

Christopher Tenter's avatar
Christopher Tenter committed
920
          goodCorner = vertexPriorities[0].first; // polygon corner
921

Christopher Tenter's avatar
Christopher Tenter committed
922
923
924
925
926
927
928
929
930
          // add new vertex at the end of the buffer
          goodVertexID = numDrawVerts_;
          setInputIndexSplit(faceID, goodCorner, goodVertexID);
        }
        else
        {
          // mark the polygon as owner of the vertex
          VertexUsed[goodVertexID] = faceID;
        }
931

Christopher Tenter's avatar
Christopher Tenter committed
932
933
934
935
936
        // process tris
        for (int t = 0; t < numRemainingTris; ++t)
        {
          // check if the triangle references the good corner by testing the 3 vertices of the triangulation
          for (int k = 0; k < 3; ++k)
937
          {
Christopher Tenter's avatar
Christopher Tenter committed
938
939
940
            int cornerID = -1 - triIndexBuffer_[(triCounter + currentTri->id) * 3 + k];

            if (cornerID == goodCorner)
941
            {
Christopher Tenter's avatar
Christopher Tenter committed
942
943
              // rotate the triangle such that the first corner of the triangle references the good corner
              int rotCount = 3 - k;
944

Christopher Tenter's avatar
Christopher Tenter committed
945
946
              // make a temp copy of current triangle
              int tmpTriVerts[3] =
947
              {
Christopher Tenter's avatar
Christopher Tenter committed
948
949
950
951
                triIndexBuffer_[(triCounter + currentTri->id) * 3],
                triIndexBuffer_[(triCounter + currentTri->id) * 3 + 1],
                triIndexBuffer_[(triCounter + currentTri->id) * 3 + 2],
              };
952

Christopher Tenter's avatar
Christopher Tenter committed
953
954
955
              // apply rotation
              for (int i = 0; i < 3; ++i)
                triIndexBuffer_[(triCounter + currentTri->id) * 3 + (i + rotCount) % 3] = tmpTriVerts[i];
956

957

Christopher Tenter's avatar
Christopher Tenter committed
958
              ++numTrisCovered;
959

Christopher Tenter's avatar
Christopher Tenter committed
960
961
962
963
964
965
966
967
968
              // remove triangle from the ring list
              currentTri->prev->next = currentTri->next;
              currentTri->next->prev = currentTri->prev;
              break;
            }
          }

          currentTri = currentTri->next;
        }
969
970
      }

971
    }
Christopher Tenter's avatar
Christopher Tenter committed
972
973

    triCounter += faceSize - 2;
974
  }
975

976
977
978
  // process all triangles now
  numInitialVerts = VertexUsed.size();
  triCounter = 0;
979

980
981
982
983
984
985
986
987
988
989
  for (int sortFaceID = 0; sortFaceID < numFaces_; ++sortFaceID)
  {
    int faceID = faceSortMap_.empty() ? sortFaceID : faceSortMap_[sortFaceID];
    const int numCorners = getFaceSize(faceID);
    
    if (numCorners == 3)
    {
      // reset shared list
      memset(&sharedVertices[0], 0, sizeof(int) * maxFaceSize_);
      int numShared = 0;
990

991
992
      // find shared list (corners of this face, that are shared with the neighbors)
      for (int v0 = 0; v0 < numCorners && numShared < numCorners; ++v0)
993
      {
994
995
996
997
998
999
1000
1001
        if (sharedVertices[v0])
          continue;

        const int vertexID0 = getInputIndexSplit(faceID, v0);

        // EDIT:
        // vertexID0 >= numInitialVerts || (...) seemed wrong
        if (vertexID0 < numInitialVerts && (VertexUsed[vertexID0] >= 0 && VertexUsed[vertexID0] != faceID))
1002
        {
1003
1004
          sharedVertices[v0] = true;
          ++numShared;
1005
        }
1006
1007
      }

1008
      int rotCount = 0;
1009

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

1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
        // add split vertex to end of vertex buffer, which is used exclusively by the current face
        // current vertex count is stored in numDrawVerts_

        setInputIndexSplit(faceID, 0, numDrawVerts_);
      }
      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
        rotCount = 1;
        for (; rotCount < numCorners; ++rotCount)
        {
          if (!sharedVertices[rotCount % numCorners])
          {
            if (tmpFaceVerts[rotCount] < numInitialVerts)
              VertexUsed[tmpFaceVerts[rotCount]] = faceID;
            break;
          }
        }

        assert(rotCount < numCorners);

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

        for (int i = 0; i < numCorners; ++i)
        {
//        setInputIndexSplit(faceID, i, tmpFaceVerts[(i + numCorners - rotCount) % numCorners]);

          triIndexBuffer_[triCounter * 3 + i] = tmpFaceVerts[(i + numCorners - rotCount) % numCorners];
        }
      }
      else
      {
        // best-case: unshared vertex at corner 0
        const int idx = getInputIndexSplit(faceID, 0);
        if (idx < numInitialVerts)
          VertexUsed[idx] = faceID;
      }
1066
    }
1067

1068
    triCounter += numCorners - 2;
1069
1070
  }

Christopher Tenter's avatar
Christopher Tenter committed
1071
//  std::cout << "force unshared num added: " << (numDrawVerts_ - numInitialVerts) << std::endl;
1072
1073
}

1074
void MeshCompiler::getInputFaceVertex( const int _face, const int _corner, int* _out ) const
1075
1076
{
  for (unsigned int k = 0; k < decl_.getNumElements(); ++k)
1077
    _out[k] = getInputIndex(_face, _corner, k);
1078
1079
}

1080
void MeshCompiler::getInputFaceVertex_Welded( const int i, const int j, int* _out ) const
1081
1082
1083
{
  int face = i;
  int corner = j;
1084

1085
1086
1087
1088
  // apply welding map if available
  if (!vertexWeldMapFace_.empty())
  {
    const int offset = getInputFaceOffset(i);
1089

1090
1091
1092
    face = vertexWeldMapFace_[offset + j];
    corner = vertexWeldMapCorner_[offset + j];
  }
1093

1094
1095
1096
  for (unsigned int k = 0; k < decl_.getNumElements(); ++k)
    _out[k] = getInputIndex(face, corner, k);
}
1097

1098
void MeshCompiler::getInputFaceVertexData( const int _faceId, const int _corner, void* _out ) const
1099
{
1100
1101
1102
1103
  for (int i = 0; i < numAttributes_; ++i)
  {
    const VertexElement* el = decl_.getElement(i);

1104
    const int idx = getInputIndex(_faceId, _corner, i);
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116

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




MeshCompiler::MeshCompiler(const VertexDeclaration& _decl)
: decl_(_decl)
{
  faceInput_ = 0;
1117
1118
1119
1120
1121
1122
1123
  deleteFaceInputeData_ = false;

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

Christopher Tenter's avatar
Christopher Tenter committed
1124
1125
1126
  numFaces_ = 0;
  curFaceInputPos_ = 0;

1127
  numDrawVerts_ = 0;
1128
  numIsolatedVerts_ = 0;
1129

1130
1131
1132
1133
1134
  maxFaceSize_ = 0;
  constantFaceSize_ = false;

  provokingVertex_ = -1;
  provokingVertexSetByUser_ = false;
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151

  // 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;
    }
  }
1152
1153
1154
1155


  vertexCompare_ = &defaultVertexCompare;

1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
}

MeshCompiler::~MeshCompiler()
{
  if (deleteFaceInputeData_)
    delete faceInput_;

  delete splitter_;
}


1167
int MeshCompiler::getInputIndexOffset( const int _face, const int _corner ) const
1168
1169
1170
1171
{
  assert(_face >= 0);
  assert(_face < numFaces_);

Christopher Tenter's avatar
Christopher Tenter committed
1172
  // baseIdx: offset to first index of the (face, corner) pair
Jan Möbius's avatar
Jan Möbius committed
1173
  const int baseIdx = int(faceStart_.empty() ? maxFaceSize_ * _face : faceStart_[_face]);
1174
  return baseIdx + _corner;
1175
1176
1177
1178
1179
}


void MeshCompiler::setInputIndexSplit( const int _face, const int _corner, const int _val )
{
1180
  const int offset = getInputIndexOffset(_face, _corner);
1181
1182

  // keep track of number of vertices after splitting process
Jan Möbius's avatar
Jan Möbius committed
1183
  if ( static_cast<size_t>(_val) >= numDrawVerts_)
1184
1185
1186
1187
1188
1189
1190
    numDrawVerts_ = _val + 1;

  faceBufSplit_[offset] = _val;
}

int MeshCompiler::getInputIndexSplit( const int _face, const int _corner ) const
{
1191
  const int offset = getInputIndexOffset(_face, _corner);
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248

  return faceBufSplit_[offset];
}




MeshCompilerDefaultFaceInput::MeshCompilerDefaultFaceInput(int _numFaces, int _numIndices)
: numFaces_(_numFaces), numIndices_(_numIndices)
{
  faceOffset_.resize(numFaces_, -1);
  faceSize_.resize(numFaces_, 0);
  faceData_[0].reserve(_numIndices);
}


void MeshCompiler::setNumFaces( const int _numFaces, const int _numIndices )
{
  if (faceInput_)
    return;

  MeshCompilerDefaultFaceInput* internalInput = new MeshCompilerDefaultFaceInput(_numFaces, _numIndices);

  numFaces_ = _numFaces;

  faceInput_ = internalInput;
  deleteFaceInputeData_ = true;

}


void MeshCompiler::setFaceAttrib( int _i, int _numEdges, int* _v, int _attrID )
{
  if (!_v || _attrID < 0) return;

  if (!faceInput_)
    faceInput_ = new MeshCompilerDefaultFaceInput(0, 0);

  MeshCompilerDefaultFaceInput* input = dynamic_cast<MeshCompilerDefaultFaceInput*>(faceInput_);
  if (input)
  {
    input->setFaceData(_i, _numEdges, _v, _attrID);
  }
}

void MeshCompiler::setFaceAttrib( int _i, int _v0, int _v1, int _v2, int _attrID )
{
  int tmp[3] = {_v0, _v1, _v2};
  setFaceAttrib(_i, 3, tmp, _attrID);
}



MeshCompiler::VertexSplitter::VertexSplitter(int _numAttribs,
                                         int _numVerts,
                                         int _numWorstCase,
                                         float _estBufferIncrease)
1249
: numAttribs(_numAttribs), numVerts(_numVerts), numBaseVerts(_numVerts)
1250
1251
1252
1253
{
  if (_numWorstCase <= 0)
    _numWorstCase = int(float(_numVerts) * (_estBufferIncrease + 1.0f));

1254
  const int maxCount = (_numAttribs + 1) * (_numWorstCase + 1);
1255
1256
1257

  // alloc split list and invalidate
  splits.resize(maxCount, -1);
1258
1259
1260

  dbg_numResizes = 0;
  dbg_numSplits = 0;
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
}



MeshCompiler::VertexSplitter::~VertexSplitter()
{
}


int MeshCompiler::VertexSplitter::split(int* vertex)
{
  int pos = vertex[0];
  int next = getNext(pos);

  if (next < 0)
  {
    // 1st time reference

    // store attributes
    setAttribs(pos, vertex);

    // mark as referenced (next = this)
    setNext(pos, pos);
  }
  else
  {
    // already referenced

    int bSearchSplit = 1;

    // search vertex in split list
1292
    while (pos >= 0 && bSearchSplit)
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
    {
      // is vertex already in split list?
      if (!memcmp(vertex, getAttribs(pos), numAttribs * sizeof(int)))
      {
        // found! reuse index
        return pos;
      }
      else
      {
        next = getNext(pos);
        
1304
        if (next < 0) break;    // end of list
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
        if (next == pos) break; // avoid loop

        pos = next;             // go to next entry
      }
    }

    // combination not found -> add new vertex

    int newID = numVerts++;

    setNext(pos, newID);
    setAttribs(newID, vertex);

    pos = newID;
1319
1320

    ++dbg_numSplits;
1321
1322
1323
1324
1325
1326
1327
  }

  return pos;
}



1328
int MeshCompiler::VertexSplitter::getNext(const int id)
1329
1330
1331
{
  assert(id >= 0);

1332
  const int entryIdx = id * (1 + numAttribs);
1333
1334
1335

  // need more space?
  if (entryIdx >= (int)splits.size())
1336
  {
1337
    splits.resize(entryIdx + numAttribs * 100, -1);
1338
1339
    ++dbg_numResizes;
  }
1340
1341
1342
1343

  return splits[entryIdx];
}

1344
void MeshCompiler::VertexSplitter::setNext(const int id, const int next)
1345
1346
1347
{
  assert(id >= 0);