MeshCompiler.cc 115 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
54

#include "MeshCompiler.hh"

#include <map>
#include <list>
55
#include <cassert>
56
#include <iostream>
57
#include <sstream>
58
#include <algorithm>
59
60
61
62
63
64
65
66

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

#ifdef ACG_MC_USE_STL_HASH
#include <unordered_map> // requires c++0x
#else
67
#include <QHash>  // alternative to unordered_map
68
#endif // ACG_MC_USE_STL_HASH
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
112
113
114
115

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


116
MeshCompilerVertexCompare MeshCompiler::defaultVertexCompare;
117
118
119
120
121

void MeshCompiler::AdjacencyList::init( int n )
{
  delete [] start;
  delete [] buf;
122
  delete [] count;
123
124

  num = n;
125
126
  start = new int[n];
  count = new unsigned char[n];
127
128
129
130
131
132
133

  buf   = 0; // unknown buffer length

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

  // reset count
134
  memset(count, 0, n * sizeof(unsigned char));  
135
136
}

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

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

  return buf[st + k];
}

148
int MeshCompiler::AdjacencyList::getCount( const int i ) const
149
150
151
152
{
  return count[i];
}

153
void MeshCompiler::AdjacencyList::clear()
154
{
155
156
157
158
159
160
  num = 0;
  delete [] start; start = 0;
  delete [] buf; buf = 0;
  delete [] count; count = 0;
  bufSize = 0;
}
161
162
163



164
165
166
void MeshCompiler::computeAdjacency()
{
  const int numVerts = input_[inputIDPos_].count;
167
168

  // ==============================================================
169
  // compute vertex -> face adjacency
170

171
172
  // count total number of adjacency entries
  // store adj entries in a single tightly packed buffer
173

174
175
  // check if user provided adjacency information
  if (faceInput_->getVertexAdjCount(0) < 0 && adjacencyVert_.bufSize <= 0)
176
  {
177
    adjacencyVert_.init(numVerts);
178

179
180
    // count # adjacent faces per vertex
    for (int i = 0; i < numFaces_; ++i)
181
    {
182
      int nCorners = getFaceSize(i);
183

184
      for (int k = 0; k < nCorners; ++k)
185
      {
186
187
        //        int vertex = faceInput_->getSingleFaceAttr(i, k, inputIDPos_);
        int vertex = getInputIndex(i, k, inputIDPos_);
188

189
        adjacencyVert_.count[vertex]++;
190
191
192
193
      }
    }


194
195
    // count num of needed entries
    int nCounter = 0;
196

197
    for (int i = 0; i < numVerts; ++i)
198
    {
199
      adjacencyVert_.start[i] = nCounter; // save start indices
200

201
      nCounter += adjacencyVert_.count[i];
202

203
204
      adjacencyVert_.count[i] = 0; // count gets recomputed in next step
    }
205

206
207
208
    // alloc memory
    adjacencyVert_.buf = new int[nCounter];
    adjacencyVert_.bufSize = nCounter;
209

210
211
    // build adjacency list
    for (int i = 0; i < numFaces_; ++i)
212
    {
213
      int nCorners = getFaceSize(i);
214

215
      for (int k = 0; k < nCorners; ++k)
216
      {
217
218
219
        //        int vertex = faceInput_->getSingleFaceAttr(i, k, inputIDPos_);
        int vertex = getInputIndex(i, k, inputIDPos_);
        int adjIdx = adjacencyVert_.start[vertex] + adjacencyVert_.count[vertex]++;
220

221
        adjacencyVert_.buf[ adjIdx ] = i;
222
223
224
      }
    }

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


263
void MeshCompiler::setVertices( int _num, const void* _data, int _stride, bool _internalCopy /*= false*/, GLuint _fmt, int _elementSize )
264
{
265
  setAttribVec(inputIDPos_, _num, _data, _stride, _internalCopy, _fmt, _elementSize);
266
267
}

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

273
void MeshCompiler::setTexCoords( int _num, const void* _data, int _stride, bool _internalCopy /*= false*/, GLuint _fmt, int _elementSize )
274
{
275
  setAttribVec(inputIDTexC_, _num, _data, _stride, _internalCopy, _fmt, _elementSize);
276
277
278
}


279
void MeshCompiler::setAttribVec(int _attrIdx, int _num, const void* _data, int _stride, bool _internalCopy /*= false*/, GLuint _fmt, int _elementSize)
280
{
281
282
283
284
285
286
287
288
  // 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!

289
290
291
292
293
294
295
296
297
  if (_attrIdx < 0)
    return;

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

  VertexElementInput* inbuf = input_ + _attrIdx;

  inbuf->count = _num;

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

301
302

  // make an internal copy of the input if the user can not guarantee, that the data address is permanently valid
303
304
  if (_internalCopy)
  {
305
    delete [] inbuf->internalBuf;
306
307
308
309
310
311
312
313
314
315
    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)
      {
316
317
        memcpy(inbuf->internalBuf + (size_t)(size * i),
          (const char*)_data + (size_t)(_stride * i),
318
319
320
321
322
323
          size);
      }
    }
  }
  else
  {
324
    // store data address only without making a copy
325
326
327
328
329
330
    inbuf->data = (const char*)_data;
    inbuf->stride = _stride ? _stride : size;

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


  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);
392
  vertexWeldMapCorner_.resize(numIndices_, -1);
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
523
524
525
526
527
528
529
530
531
532
533
534

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

Christopher Tenter's avatar
Christopher Tenter committed
535
536
      // 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
537
538
539
540
541
542
543
      if (vertexWeldMapFace_[weldMapOffset] < 0)
      {
        vertexWeldMapFace_[weldMapOffset] = i;
        vertexWeldMapCorner_[weldMapOffset] = k;
      }
    }
  }
544
545
}

546
547
548
549
550
551
552
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.
553

554
555
556
557
558
  for (int i = 0; i < nVerts; ++i)
  {
    if (splitter_->isIsolated(i))
      ++numIsolatedVerts_;
  }
559

560
561
562
563
564
565
566
567
  isolatedVertices_.clear();
  isolatedVertices_.reserve(numIsolatedVerts_);
  for (int i = 0; i < nVerts; ++i)
  {
    if (splitter_->isIsolated(i))
      isolatedVertices_.push_back(i);
  }
}
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600

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

  */

601
602
  const int numPositions = input_[inputIDPos_].count;

603
  // estimate number of splits to avoid resizing too often
604
  int estimatedSplitCount = 0;
605
  int numDifferentInputCounts = 0;
606

607
608
609
  // 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.
610
611
612
613
614
615
616
  for (int i = 0; i < numAttributes_; ++i)
  {
    if (i != inputIDPos_)
    {
      if (input_[i].count > numPositions)
      {
        const int diff = input_[i].count - numPositions;
617

618
619
620
621
622
        if (diff > 0)
        {
          estimatedSplitCount = std::max(diff, estimatedSplitCount);
          ++numDifferentInputCounts;
        }
623
624
      }
    }
625
626
  }

627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
  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;
665

666
  // 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
667
668
  delete splitter_;
  splitter_ = new VertexSplitter(decl_.getNumElements(),
669
670
671
                                 numPositions,
                                 numPositions + estimatedSplitCount,
                                 0.0f);
672
673
674
675
676
677
678
679
680
681
682

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

686

687
      // get indices of a face corner after welding
688
      getInputFaceVertex_Welded(i, k, vertex);
689
690
691

      // split vertices by index data only
      // value of position, normal etc. are not considered
692
      const int idx = splitter_->split(vertex);
693
694
695
696
697

      // handle index storage
      setInputIndexSplit(i, k, idx);
    }
  }
698
699


700
701
702
703
//  std::cout << "actual split count: " << (numDrawVerts_ - numPositions) << std::endl;



704
705
706
707
708
709
710
711
  // 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
712
713
    //  this is done in the index domain after splitting
    std::vector<int> IsoFix(splitter_->numVerts, 0);
714
715

    int fixIndex = 0;
716
    for (int i = 0; i < splitter_->numVerts; ++i)
717
718
719
720
721
722
723
    {
      if (splitter_->isIsolated(i))
        fixIndex--;

      IsoFix[i] = fixIndex;
    }

724
725
    // 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
726
    // Isolates may be appended later to the vbo if the user wants that.
727

728
729
    numDrawVerts_ = 0;

Christopher Tenter's avatar
Christopher Tenter committed
730
    // apply index fixing table to current vertex ids
731
732
733
734
735
    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
736
        // get interleaved vertex id for (i, k) after splitting
737
        int idx = getInputIndexSplit(i, k);
Christopher Tenter's avatar
Christopher Tenter committed
738

739
740
741
        // 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
742
743

        // store fixed vertex id
744
745
746
747
        setInputIndexSplit(i, k, idx);
      }
    }
  }
748
749
750
}


751
752
753
754
755
bool MeshCompiler_forceUnsharedFaceVertex_InnerValenceSorter( const std::pair<int, int>& a, const std::pair<int, int>& b )
{
  return a.second > b.second;
}

756
757
758
759
760
761
762
763
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
764
765
  // 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
766
  std::vector<int> sharedVertices;
767
  sharedVertices.resize(maxFaceSize_);
768

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

773
  int numInitialVerts = numDrawVerts_;
774
775
776
777
778
779
780
  std::vector<int> VertexUsed(numDrawVerts_, -1); // marks vertices which are not shared with any neighboring face


  // process all n-polygons first

  /*
  new and better algorithm:   O(n^2)
781

782
783
784
785
786
  for each face:

  trisCovered = 0;

  while (trisCovered < faceSize)
787
  {
788
    compute inner valence of all corners in the remaining polygon
789

790
791
792
793
794
795
796
797
798
    add 'best' corner: - highest inner valence and unused by other tris

    for each triangle affected by this corner
      rotate triIndexBuffer entries of the tri
      remove tri from the remaining triangle list
      ++ trisCovered
  }
  */
  int triCounter = 0;
799
800


801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
  int fids[] = { 276, 284 };
  std::vector<int> faces[2];
  std::vector<int> tris[2];
  for (int i = 0; i < 2; ++i)
  {
    int faceID = fids[i];
    int fsize = getFaceSize(fids[i]);
    for (int k = 0; k < fsize; ++k)
      faces[i].push_back(getInputIndexSplit(faceID, k));
  }

  for (int sortFaceID = 0; sortFaceID < numFaces_; ++sortFaceID)
  {
    // get original face id
    const int faceID = faceSortMap_.empty() ? sortFaceID : faceSortMap_[sortFaceID];
    int fsize = getFaceSize(faceID);

    int faceNo = -1;
    if (faceID == fids[0])
      faceNo = 0;
    else if (faceID == fids[1])
      faceNo = 1;

    if (0 <= faceNo && faceNo <= 1)
    {
      for (int i = 0; i < fsize - 2; ++i)
827
      {
828
829
830
        tris[faceNo].push_back(triIndexBuffer_[(triCounter + i) * 3]);
        tris[faceNo].push_back(triIndexBuffer_[(triCounter + i) * 3 + 1]);
        tris[faceNo].push_back(triIndexBuffer_[(triCounter + i) * 3 + 2]);
831
832
833
834
      }
    }


835
836
837
838
839
840
841
842
843
    triCounter += fsize - 2;
  }

  triCounter = 0;


  if (1)
  {
    for (int sortFaceID = 0; sortFaceID < numFaces_; ++sortFaceID)
844
    {
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
      // get original face id
      const int faceID = faceSortMap_.empty() ? sortFaceID : faceSortMap_[sortFaceID];

      const int faceSize = getFaceSize(faceID);

      if (faceSize > 3)
      {
        // which corners of the polygon have been duplicated
//        std::vector<int> duplicatedVerts;


        // vertexPriorities[priority] = pair(cornerID, valence)
        std::vector< std::pair<int, int> > vertexPriorities(faceSize);

        // linked ring list for all the triangles in the uncovered triangulation
        // ie. nextTri = remainingTris[currentTri];
        const int faceTris = faceSize - 2;

        struct RingTriangle 
        {
          RingTriangle() {}
          RingTriangle(int i, RingTriangle* p, RingTriangle* n) : id(i), prev(p), next(n) {}

          int id; // local index of the triangle within a polygon [0, ... faceSize-3]
          RingTriangle* prev; // prev triangle in the ring
          RingTriangle* next; // next triangle in the ring
        };

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


        RingTriangle* currentTri = &remainingTris[0];
        int numTrisCovered = 0;

        while (numTrisCovered < faceTris)
        {
          // compute valence of vertices within the remaining triangulation
          for (int k = 0; k < faceSize; ++k)
            vertexPriorities[k] = std::pair<int, int>(k, 0);

          RingTriangle* startTri = currentTri;
          int numRemainingTris = faceTris - numTrisCovered;
          for (int t = 0; t < numRemainingTris; ++t)
          {
            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);

          // sort by valence
          std::sort(vertexPriorities.begin(), vertexPriorities.end(), MeshCompiler_forceUnsharedFaceVertex_InnerValenceSorter);

          // find a good corner
          int goodCorner = -1;
          int goodVertexID = -1;
          int bestValence = -1;
          for (int k = 0; k < faceSize && vertexPriorities[k].second; ++k)
          {
            int cornerID = vertexPriorities[k].first;
            int vertexID = getInputIndexSplit(faceID, cornerID);

            int valence = vertexPriorities[k].second;

            if (vertexID >= numInitialVerts || (VertexUsed[vertexID] == faceID))
            {
              // best case, this vertex is already owned by the polygon
              // stop the search
              goodCorner = cornerID;
              goodVertexID = vertexID;
              bestValence = valence;
              break;
            }
            else if (VertexUsed[vertexID] < 0 && bestValence < valence)
            {
              goodCorner = cornerID; // best for now, but continue the search
              goodVertexID = vertexID;
              bestValence = valence;
            }
          }


          // maybe add a new vertex
          if (goodCorner < 0)
          {
            // have to add a new vertex
            // use the one with highest inner valence

            goodCorner = vertexPriorities[0].first; // polygon corner
//            duplicatedVerts.push_back(goodCorner);

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

          // 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
            bool triSkipped = true;
            for (int k = 0; k < 3; ++k)
            {
              int cornerID = -1 - triIndexBuffer_[(triCounter + currentTri->id) * 3 + k];

              if (cornerID == goodCorner)
              {
                // rotate the triangle such that the first corner of the triangle references the good corner
                int rotCount = 3 - k;

                // make a temp copy of current triangle
                int tmpTriVerts[3] =
                {
                  triIndexBuffer_[(triCounter + currentTri->id) * 3],
                  triIndexBuffer_[(triCounter + currentTri->id) * 3 + 1],
                  triIndexBuffer_[(triCounter + currentTri->id) * 3 + 2],
                };

                // apply rotation
                for (int i = 0; i < 3; ++i)
                  triIndexBuffer_[(triCounter + currentTri->id) * 3 + (i + rotCount) % 3] = tmpTriVerts[i];


                ++numTrisCovered;
                triSkipped = false;

                // remove triangle from the ring list
                currentTri->prev->next = currentTri->next;
                currentTri->next->prev = currentTri->prev;
                break;
              }
            }

            currentTri = currentTri->next;
          }
        }

        
993
994


995
996
997
      }

      triCounter += faceSize - 2;
998
    }
999
  }
1000

1001
1002
1003
  // process all triangles now
  numInitialVerts = VertexUsed.size();
  triCounter = 0;
1004

1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
  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;
1015

1016
1017
      // find shared list (corners of this face, that are shared with the neighbors)
      for (int v0 = 0; v0 < numCorners && numShared < numCorners; ++v0)
1018
      {
1019
1020
1021
1022
1023
1024
1025
1026
        if (sharedVertices[v0])
          continue;

        const int vertexID0 = getInputIndexSplit(faceID, v0);

        // EDIT:
        // vertexID0 >= numInitialVerts || (...) seemed wrong
        if (vertexID0 < numInitialVerts && (VertexUsed[vertexID0] >= 0 && VertexUsed[vertexID0] != faceID))
1027
        {
1028
1029
          sharedVertices[v0] = true;
          ++numShared;
1030
        }
1031
1032
      }

1033
      int rotCount = 0;
1034

1035
1036
1037
      if (numShared == numCorners)
      {
        // worst-case: all vertices shared with neighbors
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
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
        // 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;
      }
1091
    }
1092

1093
    triCounter += numCorners - 2;
1094
1095
  }

1096
  std::cout << "force unshared num added: " << (numDrawVerts_ - numInitialVerts) << std::endl;
1097
1098
}

1099
void MeshCompiler::getInputFaceVertex( const int _face, const int _corner, int* _out ) const
1100
1101
{
  for (unsigned int k = 0; k < decl_.getNumElements(); ++k)
1102
    _out[k] = getInputIndex(_face, _corner, k);
1103
1104
}

1105
void MeshCompiler::getInputFaceVertex_Welded( const int i, const int j, int* _out ) const
1106
1107
1108
{
  int face = i;
  int corner = j;
1109

1110
1111
1112
1113
  // apply welding map if available
  if (!vertexWeldMapFace_.empty())
  {
    const int offset = getInputFaceOffset(i);
1114

1115
1116
1117
    face = vertexWeldMapFace_[offset + j];
    corner = vertexWeldMapCorner_[offset + j];
  }
1118

1119
1120
1121
  for (unsigned int k = 0; k < decl_.getNumElements(); ++k)
    _out[k] = getInputIndex(face, corner, k);
}
1122

1123
void MeshCompiler::getInputFaceVertexData( const int _faceId, const int _corner, void* _out ) const
1124
{
1125
1126
1127
1128
  for (int i = 0; i < numAttributes_; ++i)
  {
    const VertexElement* el = decl_.getElement(i);

1129
    const int idx = getInputIndex(_faceId, _corner, i);
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141

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




MeshCompiler::MeshCompiler(const VertexDeclaration& _decl)
: decl_(_decl)
{
  faceInput_ = 0;
1142
1143
1144
1145
1146
1147
1148
  deleteFaceInputeData_ = false;

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

Christopher Tenter's avatar
Christopher Tenter committed
1149
1150
1151
  numFaces_ = 0;
  curFaceInputPos_ = 0;

1152
1153
1154
  indices_ = 0;

  numDrawVerts_ = 0;
1155
  numIsolatedVerts_ = 0;
1156

1157
1158
1159
1160
1161
  maxFaceSize_ = 0;
  constantFaceSize_ = false;

  provokingVertex_ = -1;
  provokingVertexSetByUser_ = false;
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178

  // 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;
    }
  }
1179
1180
1181
1182


  vertexCompare_ = &defaultVertexCompare;

1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
}

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