MeshCompiler.hh 36.8 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
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
 * 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:                                                                  *
 *                                                                           *
 * 1. Redistributions of source code must retain the above copyright notice, *
 *    this list of conditions and the following disclaimer.                  *
 *                                                                           *
 * 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.   *
 *                                                                           *
 * 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.               *
 *                                                                           *
 * 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
50
 *                                                                           *
\*===========================================================================*/

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


51
52
53
54
55
56
#pragma once

#include "VertexDeclaration.hh"

#include <map>
#include <vector>
57
#include <cstdio>
58
#include <string>
Jan Möbius's avatar
Jan Möbius committed
59
#include <fstream>
60

61
62
#include <ACG/GL/gl.hh>

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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
/*

Mesh buffer assembler:

Builds a pair of vertex and index buffer based on a poly mesh.


- flexible processing pipeline
- uses index mapping only -> lower memory consumption
- independent of OpenMesh, OpenGL
- 



usage

1. Create a vertex declaration to specify your wanted
   vertex format, such as float3 pos, float3 normal..

2. Set your vertex data.
   Example in (float3 pos, float3 normal, float2 texc) format:
   
   float VertexPositions[100*3] = {..};
   float VertexNormals[120*3] = {..};
   float VertexUV[80*2] = {..};

   drawMesh->setVertices(100, VertexPositions, 12);
   drawMesh->setNormals(120, VertexNormals, 12);
   drawMesh->setTexCoords(80, VertexUV, 8);

   Note that different indices for vertices, normals and texcoords are allowed,
   hence the various element numbers 100, 120 and 80.


   Example 2 (interleaved input)

   float Vertices[100] = {
                            x0, y0, z0,   u0, v0,   nx0, ny0, nz0,
                            x1, y1, z1,   u1, v1,   nx1, ny1, nz1,
                            ...
                          };

   The stride is 8*4 = 32 bytes.
   We use parameters as follows.

   drawMesh->setVertices(100, Vertices, 32);
   drawMesh->setNormals(100, (char*)Vertices + 20, 32);
   drawMesh->setTexCoords(100, (char*)Vertices + 12, 32);
   
3. Set index data.

   Two methods are supported for this.

   You can either specify one index set for all vertex attributes
   or use another index buffer for each vertex attribute.
   The latter means having different indices for vertex and texcoords for example.


   drawMesh->setNumFaces(32, 96);


   for each face i
     int* faceVertexIndices = {v0, v1, v2, ...};
     setFaceVerts(i, 3, faceVertexIndices);

4. finish the initialization by calling the build() function

*/

namespace ACG{

134
class ACGDLLEXPORT MeshCompilerFaceInput
135
136
137
138
139
140
141
142
{
  // face data input interface
  // allows flexible and memory efficient face data input

public:
  MeshCompilerFaceInput(){}
  virtual ~MeshCompilerFaceInput(){}

143
  virtual int getNumFaces() const = 0;
144
145
146
147
148

  /** Get total number of indices in one attribute channel.
   *
   * i.e. total number of position indices of the whole mesh
  */
149
  virtual int getNumIndices() const = 0;
150
151
152
153

  /** Get number of vertices per face.
   * @param _faceID face index
  */
154
  virtual int getFaceSize(const int _faceID) const = 0;
155
156
157
158
159
160
161
162

  /** Get a single vertex-index entry of a face.
   *
   * @param _faceID face index
   * @param _faceCorner vertex corner of the face
   * @param _attrID attribute channel 
   * @return index-data if successful, -1 otherwise
  */
163
  virtual int getSingleFaceAttr(const int _faceID, const int _faceCorner, const int _attrID) const;
164
165
166
167
168
169
170

  /** Get an index buffer of a face for a specific attribute channel.
   * @param _faceID face index
   * @param _attrID attribute channel
   * @param _out pointer to output buffer, use getFaceSize(_faceID) to get the size needed to store face data
   * @return true if successful, false otherwise
  */
171
  virtual bool getFaceAttr(const int _faceID, const int _attrID, int* _out) const {return false;}
172
173
174
175
176
177

  /** Get an index buffer of a face for a specific attribute channel.
   * @param _faceID face index
   * @param _attrID attribute channel
   * @return array data of size "getFaceSize(_faceID)", allowed to return 0 when array data not permanently available in memory
  */
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
  virtual int* getFaceAttr(const int _faceID, const int _attrID) const {return 0;}


  // Adjacency information can be provided if it has been generated already.
  // Otherwise it will be generated on the fly when needed, which might be time consuming.

  /** Get the number of adjacent faces for a vertex.
   * @param _vertexID vertex index
   * @return number of adjacent faces, return -1 if adjacency information unavailable
  */
  virtual int getVertexAdjCount(const int _vertexID) const {return -1;}

  /** Get the index of an adjacent face for a vertex.
   * @param _vertexID vertex index
   * @param _k adjacency list entry in range [0, .., adjCount - 1]
   * @return face id of adjacent face, return -1 if adjacency information is available
  */
  virtual int getVertexAdjFace(const int _vertexID, const int _k) const {return -1;}

197
198
};

199
class ACGDLLEXPORT MeshCompilerDefaultFaceInput : public MeshCompilerFaceInput
200
201
202
203
204
{
public:
  MeshCompilerDefaultFaceInput(int _numFaces, int _numIndices);
  virtual ~MeshCompilerDefaultFaceInput(){}

205
206
  int getNumFaces() const  {return numFaces_;}
  int getNumIndices() const {return numIndices_;}
207

208
  int getFaceSize(const int _faceID) const {return faceSize_[_faceID];}
209

210
  int getSingleFaceAttr(const int _faceID, const int _faceCorner, const int _attrID) const;
211

212
  bool getFaceAttr(const int _faceID, const int _attrID, int* _out) const;
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233

  void dbgWriteToObjFile(FILE* _file, int _posAttrID = 0, int _normalAttrID = -1, int _texcAttrID = -1);


  void setFaceData(int _faceID, int _size, int* _data, int _attrID = 0);

protected:

  int numFaces_,
    numIndices_;

  // input data is stored in a sequence stream
  //  face offsets may not be in sequence
  std::vector<int> faceOffset_;
  std::vector<int> faceSize_;

  // face index buffer for each vertex attribute
  std::vector<int> faceData_[16];

};

234
235
236
237

class ACGDLLEXPORT MeshCompilerVertexCompare
{
public:
238
  MeshCompilerVertexCompare(double _d_eps = 1e-4, float _f_eps = 1e-4f) : d_eps_(_d_eps), f_eps_(_f_eps) {}
239
240

  virtual bool equalVertex(const void* v0, const void* v1, const VertexDeclaration* _decl);
241
242
243

  const double d_eps_;
  const float f_eps_;
244
245
246
};

class ACGDLLEXPORT MeshCompiler
247
248
249
250
251
252
253
{
public:

  MeshCompiler(const VertexDeclaration& _decl);

  virtual ~MeshCompiler();

254
255
256
257
258
//===========================================================================
/** @name Vertex Data Input
* @{ */
//===========================================================================  

259
260
261
262
263
264
  /** set input vertex positions
   *
   * @param _num Number of vertex positions
   * @param _data Pointer to vertex data
   * @param _stride Difference in bytes between two vertex positions in _data. Default value 0 indicates a tight float3 position array without any other data or memory alignment.
   * @param _internalCopy Memory optimization flag: select true if the provided data address is only temporarily valid. Otherwise an internal copy must be made.
265
266
   * @param _fmt data format of one element (must be set if input data does not match vertex declaration)
   * @param _elementSize number of elements per attribute (i.e. 3 for vec3 ..,  -1 if unknown)
267
  */
Jan Möbius's avatar
Jan Möbius committed
268
  void setVertices(size_t _num, const void* _data, size_t _stride = 0, bool _internalCopy = false, GLuint _fmt = 0, int _elementSize = -1);
269
270

  /** set input normals
271
272
273
274
275
   *
   * @param _num Number of normals
   * @param _data Pointer to normals data
   * @param _stride Difference in bytes between two normals positions in _data. Default value 0 indicates a tight float3 position array without any other data or memory alignment.
   * @param _internalCopy Memory optimization flag: select true if the provided data address is only temporarily valid. Otherwise an internal copy must be made.
276
277
   * @param _fmt data format of one element (must be set if input data does not match vertex declaration)
   * @param _elementSize number of elements per attribute (i.e. 3 for vec3 ..,  -1 if unknown)
278
  */
Jan Möbius's avatar
Jan Möbius committed
279
  void setNormals(size_t _num, const void* _data, size_t _stride = 0, bool _internalCopy = false, GLuint _fmt = 0, int _elementSize = -1);
280
281

  /** set input texture coords
282
283
284
285
286
   *
   * @param _num Number of texture coords
   * @param _data Pointer to texture coord data
   * @param _stride Difference in bytes between two texture coordinate positions in _data. Default value 0 indicates a tight float3 position array without any other data or memory alignment.
   * @param _internalCopy Memory optimization flag: select true if the provided data address is only temporarily valid. Otherwise an internal copy must be made.
287
288
   * @param _fmt data format of one element (must be set if input data does not match vertex declaration)
   * @param _elementSize number of elements per attribute (i.e. 3 for vec3 ..,  -1 if unknown)
289
  */
Jan Möbius's avatar
Jan Möbius committed
290
  void setTexCoords(size_t _num, const void* _data, size_t _stride = 0, bool _internalCopy = false, GLuint _fmt = 0, int _elementSize = -1);
291
292
293
294

  /** Set custom input attribute.
  *
  * Alternatively allocates an internal buffer only, such that data can be provided via setAttrib().
295
296
  * @param _attrIdx      Attribute id from VertexDeclaration
  * @param _num          Number of attributes
297
  * @param _data         Input data buffer, may be null to only allocate an internal buffer
298
  * @param _stride       Offset difference in bytes to the next attribute in _data. Default value 0 indicates no data alignment/memory packing.
299
  * @param _internalCopy Create an internal buffer and make a copy _data
300
301
  * @param _fmt data format of one element (must be set if input data does not match vertex declaration)
  * @param _elementSize number of elements per attribute (i.e. 3 for vec3 ..,  -1 if unknown)
302
  */
Jan Möbius's avatar
Jan Möbius committed
303
  void setAttribVec(int _attrIdx, size_t _num, const void* _data, size_t _stride = 0, bool _internalCopy = false, GLuint _fmt = 0, int _elementSize = -1);
304

305
306
307
308
309
310
  /** Set single custom input attributes.
  *
  * An internal buffer for the requested attribute must be allocated before using this function. See setAttribVec()
  * @param _attrIdx      Attribute id from VertexDeclaration
  * @param _v            Buffer id of the single attribute
  * @param _data         attribute data
311
312
313
  */
  void setAttrib(int _attrIdx, int _v, const void* _data);

314
315
316
317
318
319
320

  /** Get number of attributes in an input buffer
  * 
  * @param _attrIdx Attribute id from VertexDeclaration
  */
  int getNumInputAttributes(int _attrIdx) const;

321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
/** @} */  


//===========================================================================
/** @name Flexible Face Data Input
* @{ */
//===========================================================================  

  /** Set Face data input
   *
   * Making use of the MeshCompilerFaceInput interface completly overrides the default input behavior.
   * Any subsequent call to default input data functions such as setNumFaces(), setFaceVerts() etc. will be ignored
   *
   * @param _faceInput user defined face input (no internal copy made, do not delete while using MeshCompiler)
   */
  void setFaceInput(MeshCompilerFaceInput* _faceInput);

/** @} */  

//===========================================================================
/** @name Default Face Data Input
* @{ */
//===========================================================================  
344

345
  /** \brief Set number of faces and indices if known by user
346
   *
347
348
349
350
   * User may give a rough estimate of face/index count. 
   * A more accurate estimation improves efficiency: too low numbers result in performance hit, too high numbers in memory consumption
   * @param _numFaces Number of faces. Value 0 accepted at cost of performance
   * @param _numIndices Number of indices, i.e. 3 * numFaces for triangle meshes. Value 0 accepted at cost of performance
351
352
353
354
   */
  void setNumFaces(const int _numFaces, const int _numIndices);


355
  /** \brief Set index buffer for a triangle mesh.
356
357
358
359
360
361
362
363
   *
   * This should only be used if the input vertex buffer is interleaved already.
   * @param _numTris Number of triangles.
   * @param _indexSize Size in bytes of one index.
   * @param _indices Pointer to a buffer containing the index data.
   */
  void setIndexBufferInterleaved(int _numTris, int _indexSize, const void* _indices);

364
  /** \brief Set vertex ids per triangle.
365
366
367
368
369
370
   *
   * @param _i Face ID
   * @param _v0 1st vertex id
   * @param _v1 2nd vertex id
   * @param _v2 3rd vertex id
   */
371
372
  void setFaceVerts(int _i, int _v0, int _v1, int _v2);

373
  /** \brief Set vertex ids per face.
374
375
376
377
378
379
380
   *
   * @param _i Face id
   * @param _faceSize Size of face, ie. number of vertices of face
   * @param _v Vertex ids
   */
  void setFaceVerts(int _i, int _faceSize, int* _v);

381
  /** \brief Set normal ids per triangle.
382
383
384
385
386
387
   *
   * @param _i Face ID
   * @param _v0 1st normal id
   * @param _v1 2nd normal id
   * @param _v2 3rd normal id
   */
388
  void setFaceNormals(int _i, int _v0, int _v1, int _v2);
389
  
390
  /** \brief Set normal ids per face.
391
392
393
394
395
396
   *
   * @param _i Face id
   * @param _faceSize Size of face, ie. number of vertices of face
   * @param _v Normal ids
   */
  void setFaceNormals(int _i, int _faceSize, int* _v);
397

398
  /** \brief Set texcoord ids per triangle.
399
400
401
402
403
404
   *
   * @param _i Face ID
   * @param _v0 1st texcoord id
   * @param _v1 2nd texcoord id
   * @param _v2 3rd texcoord id
   */
405
406
  void setFaceTexCoords(int _i, int _v0, int _v1, int _v2);

407
  /** \brief Set texcoord ids per face.
408
409
410
411
412
413
414
415
   *
   * @param _i Face id
   * @param _faceSize Size of face, ie. number of vertices of face
   * @param _v Texcoord ids
   */
  void setFaceTexCoords(int _i, int _faceSize, int* _v);


416
  /** \brief Set attribute ids per triangle.
417
418
419
420
421
422
423
   *
   * @param _i Face id
   * @param _v0 1st element id
   * @param _v1 2nd element id
   * @param _v2 3rd element id
   * @param _attrID Which attribute: index of VertexDeclaration element array
   */
424
425
  void setFaceAttrib(int _i, int _v0, int _v1, int _v2, int _attrID);

426
  /** \brief Set attribute ids per face.
427
   *
428
   * @param _i        Face id
429
   * @param _faceSize Size of face, ie. number of vertices of face
430
431
   * @param _v        Element ids
   * @param _attrID   Which attribute: index of VertexDeclaration element array
432
433
434
435
436
437
438
439
440
441
442
   */
  void setFaceAttrib(int _i, int _faceSize, int* _v, int _attrID);


/** @} */  

//===========================================================================
/** @name Face Grouping and Subsets
* @{ */
//===========================================================================  

443

444
  /** \brief Specify face groups.
445
446
447
   *
   * Faces with the same group ID will be chunked together in the sorting process.
   * This feature may be used for material/texture subsets.
448
   * @param _i       Face ID
449
450
   * @param _groupID Custom group ID
   */
451
  void setFaceGroup(int _i, short _groupID);
452

453
454
  // subset/group management
  struct Subset
455
  {
456
457
458
459
460
461
462
463
    int id; // subset id
    unsigned int startIndex; // 1st occurrence of group in index buffer
    unsigned int numTris; // number of tris belonging to subset in index buffer

    unsigned int numFaces; // number of faces belonging to subset
    unsigned int startFace; // index into sorted list of faces
  };

464
465
466
467
468
  /** \brief get subset ID of a group
   *
   * @param _groupID Id of the group
   * @return Subset Id
   */
469
  int findGroupSubset(int _groupID);
470

471
472
473
474
475
  /** \brief Get Face Group of the given face
   *
   * @param _faceID Id of the face
   * @return Group Id
   */
476
  int getFaceGroup(int _faceID) const;
477
478
479
480
481
482

  /** \brief Get Group Id of the triangle
   *
   * @param _triID Id of the triangle
   * @return Group of the triangle
   */
483
484
  int getTriGroup(int _triID) const;

485
486
487
488
  /** \brief Get the number of subsets
   *
   * @return Number of subsets
   */
489
  int getNumSubsets() const {return (int)subsets_.size();}
490
491
492
493
494
495

  /** \brief get a specific subset
   *
   * @param _i  Id of the subset
   * @return    The subset
   */
496
497
498
499
  const Subset* getSubset(int _i) const;


/** @} */  
500

501
502
503
504
505
506
//===========================================================================
/** @name Mesh Compilation
* @{ */
//===========================================================================  


507
  /** \brief Build vertex + index buffer.
508
   * 
509
510
   * @param _weldVertices Compare vertices and attempt to eliminate duplicates. High computation cost
   * @param _optimizeVCache Reorder faces for optimized vcache usage. High computation cost
Christopher Tenter's avatar
Christopher Tenter committed
511
   * @param _needPerFaceAttribute User wants to set per-face attributes in draw vertex buffer. Per-face data can be stored in the provoking vertex of each face. Low computation cost
512
   * @param _keepIsolatedVertices Isolated vertices should not be discarded in the output vertex buffer
513
  */
514
515
516
517
518
519
520
521
522
523
524
525
  void build(bool _weldVertices = false, bool _optimizeVCache = true, bool _needPerFaceAttribute = false, bool _keepIsolatedVertices = false);

  /** Get number of vertices in final buffer.
  */
  int getNumVertices() const {return numDrawVerts_;}

  /** See glProvokingVertex()
   *
   * Specifiy the vertex to be used as the source of data for flat shading.
   * The default value is 2, meaning that the last vertex of each triangle will be used.
   * setProvokingVertex() must be called prior to build(), if a different provoking vertex is desired.
   * Additionally build() has to set its _needPerFaceAttribute parameter to true to enable provoking vertices.
Christopher Tenter's avatar
Christopher Tenter committed
526
   * The provoking vertex of a face is a vertex, which is not shared with any other face in the mesh.
527
528
529
530
   *
   * @param _v triangle vertex where the provoking vertex should be stored [0, 1, 2]
   */
  void setProvokingVertex(int _v);
531

532
533
534
535
536
537
  /** See glProvokingVertex()
   *
   * @return provoking vertex id
   */
  int getProvokingVertex() const {return provokingVertex_;}

538

539
  /** \brief Get vertex buffer ready for rendering.
540
541
542
543
544
545
546
547
548
   * 
   * Query final vertex buffer data.
   * Support vertex buffer batch uploads.
   * @param _dst [out] Pointer to memory address where the vertex buffer should be copied to
   * @param _offset Begin of vertex buffer batch
   * @param _range Size of vertex buffer batch. Copies rest of buffer if _range < 0.
  */
  void getVertexBuffer(void* _dst, const int _offset = 0, const int _range = -1);

549
  /** Get index buffer ready for rendering.
550
  */
551
  const int* getIndexBuffer() const {return indices_.data();}
552

553
554
555
  /** \brief Get index buffer with adjacency information ready for rendering.
   *
   * This index buffer can be used to render in GL_TRIANGLES_ADJACENCY mode.
556
557
   * For each triangle, it contains the 3 neighboring triangles with a shared edge in addition to the triangle vertices.
   * Each triangle stores 6 indices:
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
   *  0 - first vertex of triangle
   *  1 - opposite vertex to first edge of adjacent triangle
   *  2 - second vertex of triangle
   *  3 - opposite vertex to second edge of adjacent triangle
   *  4 - third vertex of triangle
   *  5 - opposite vertex to third edge of adjacent triangle
   *
   *  5___4___3
   *  \  /\  /
   *   \/__\/
   *   0\  /2
   *     \/
   *      1
   *
   *
   *
   * @param _dst [out] Pointer to memory address where the 32bit index buffer should be copied to. Must have size of at least 6 * numTris * 4 bytes
   * @param _borderIndex index to use for border edges (missing adjacent triangles)
  */
  void getIndexAdjBuffer(void* _dst, const int _borderIndex = -1);

579
580
581
582
583
584
585
586
587
588
589
590
  /** \brief Slow brute-force version of getIndexAdjBuffer
   * 
   * Computes index buffer with adjacency information, but uses a much simpler algorithm.
   * Runtime = O(n^2), but this can be used to verify the result of getIndexAdjBuffer.
   * Results from brute-force and optimized algorithm must be equal for meshes where no edge is shared by more than two triangles.
   *
   * @param _dst [out] Pointer to memory address where the 32bit index buffer should be copied to. Must have size of at least 6 * numTris * 4 bytes
   * @param _borderIndex index to use for border edges (missing adjacent triangles)
  */
  void getIndexAdjBuffer_BruteForce(void* _dst, const int _borderIndex = -1);


591
592
  /** Get number of triangles in final buffer.
  */
593
  int getNumTriangles() const {return numTris_;}
594

595
596
597
598
  /** Get number of input faces.
  */
  int getNumFaces() const;

599
600
601
602
603
  /** \brief Get size of input face
   *
   * @param _i Index
   * @return Size
   */
604
605
  inline int getFaceSize(const int _i) const
  {
Jan Möbius's avatar
Jan Möbius committed
606
    return int(faceSize_.empty() ? maxFaceSize_ : faceSize_[_i]);
607
608
  }

609
610
611
612
  /** Get Vertex declaration.
  */
  const VertexDeclaration* getVertexDeclaration() const {return &decl_;}

613
614
615
616
617
618
619
620
  /** Get vertex in final draw vertex buffer.
  */
  void getVertex(int _id, void* _out) const;

  /** Get index in final draw index buffer.
  */
  int getIndex(int _i) const;

621
622
623
624
625
626
627
628
629
630
631

/** @} */  



//===========================================================================
/** @name Input/Output ID mapping
* @{ */
//===========================================================================  


632
633
634
635
636
  /** Mapping from draw vertex id -> input vertex id
   *
   * @param _i Vertex ID in draw buffer
   * @param _faceID [out] Face ID in face input buffer
   * @param _cornerID [out] Corner of face corresponding to vertex.
637
   * @return Position ID in input buffer
638
  */
Jan Möbius's avatar
Jan Möbius committed
639
  int mapToOriginalVertexID(const size_t _i, int& _faceID, int& _cornerID) const;
640
641
642
643
644
645
646
647

  /** Mapping from draw tri id -> input face id
   *
   * @param _triID Triangle ID in draw index buffer
   * @return Input Face ID
  */
  int mapToOriginalFaceID(const int _triID) const;

648
649
650
651
652
  /** Get pointer to the lookup table mapping from tri id -> input face id
   *
   * @return ptr to address of lookup table with size getNumTriangles()
  */
  const int* mapToOriginalFaceIDPtr() const;
653
654
655
656
657
658
659
660
661

  /** Mapping from input vertex id -> draw vertex id
   *
   * @param _faceID Face ID in input data
   * @param _cornerID Corner of face
   * @return Draw Vertex ID in output vertex buffer
  */
  int mapToDrawVertexID(const int _faceID, const int _cornerID) const;

662
  /** Mapping from input Face id -> draw triangle id
663
664
665
666
667
668
669
670
671
   *
   * @param _faceID Face ID in input data
   * @param _k triangle no. associated to face, offset 0
   * @param _numTrisOut [out] Number of triangles associated to face (if input face was n-poly)
   * @return Draw Triangle ID in output vertex buffer
  */
  int mapToDrawTriID(const int _faceID, const int _k = 0, int* _numTrisOut = 0) const;


672
/** @} */  
673
674


675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
//===========================================================================
/** @name Triangulation properties
* @{ */
//===========================================================================  

  /** Test if the input mesh consists of triangles only.
  */
  bool isTriangleMesh() const;

  /** Test if a triangle edge is a face edge from the input buffer.
   *
   * When a convex n-poly is subdivided into (n-2) triangles, new edges are created which do not exist in the input mesh.
   * This function identifies if an edge was already existant in the input mesh or added during triangulation.
   * @param _triID triangle ID in draw buffer
   * @param _edge edge of triangle, edge ordering: v0-v1, v1-v2, v2-v0
   * @return true if the edge is an edge from an input face, false otherwise
  */
  bool isFaceEdge(const int _triID, const int _edge) const;


/** @} */  
696
697
698
699
700



private:

701
  // compute adjacency information: vertex -> neighboring faces (, face -> neighboring faces [removed] )
702
  void computeAdjacency(bool _forceRecompute = false);
703

704
  // convert per-face vertices to unique ids
705
706
707
708
709
710
711
712
713
714
  void splitVertices();

private:

  // small helper functions

  /** i: face index
      j: corner index
      _out: output vertex (index for each attribute)
  */
715
716
717
718
719
720
  void getInputFaceVertex(const int _face, const int _corner, int* _out) const;

  /** i: face index
      j: corner index
      _out: output vertex (index for each attribute) post welding operation
  */
721
  void getInputFaceVertex_Welded(const int _face, const int _corner, int* _out) const;
722
723
724
725
726

  /** i: face index
      j: corner index
      _out: output vertex address (vertex data)
  */
727
  void getInputFaceVertexData(const int _face, const int _corner, void* _out) const;
728
729
730
731
732
733
734
735
736
737


  inline int getInputIndex( const int& _face, const int& _corner, const int& _attrId ) const
  {
    return faceInput_->getSingleFaceAttr(_face, _corner, _attrId);

    // alternatively avoid virtual function call at cost of higher memory overhead ( could not confirm any run-time difference )
    // to use this, uncomment code in prepareData() that initializes faceData_ array as well
//    return faceData_[(getInputFaceOffset(_face) + _corner) * numAttributes_ + _attrId];
  }
738
739
740
741
742
743
744


private:

  // ====================================================
  // input data

745

746
747
  // vertex buffer input

748
  struct ACGDLLEXPORT VertexElementInput 
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
  {
    VertexElementInput();
    ~VertexElementInput();

     /// mem alloc if attribute buffer managed by this class
    char* internalBuf;

    /** address to data input, will not be released by MeshCompiler
        - may be an external address provided by user of class
    */
    const char* data;

    /// # elements in buffer
    int count;

    /// offset in bytes from one element to the next
    int stride;

    /// size in bytes of one attribute
    int attrSize;


    // vertex data access

773
774
775
776
777
778
    /// element data format
    GLuint fmt;

    /// number of ints/floats/bytes per element 
    int elementSize;

779
    /// read a vertex element
780
    void getElementData(int _idx, void* _dst, const VertexElement* _desc) const;
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
  };
  
  // input vertex data
  VertexElementInput  input_[16];

  // convenient attribute indices
  int inputIDPos_;  // index of positions into input_ array
  int inputIDNorm_; // index of normals into input_ array
  int inputIDTexC_; // index of texcoords into input_ array

  int                 numAttributes_;
  VertexDeclaration   decl_;


  // input face data

  int   numFaces_, 
        numIndices_;
Jan Möbius's avatar
Jan Möbius committed
799
800

  std::vector<int>           faceStart_;         // start position in buf for each face
801
  std::vector<int>           faceSize_;          // face size, copy of faceInput_->getFaceSize() for better performance
Jan Möbius's avatar
Jan Möbius committed
802
803
804
805
806
  std::vector<int>           faceData_;
  size_t                     maxFaceSize_;       // max(faceSize_)
  bool                       constantFaceSize_;
  std::vector<short>         faceGroupIDs_;      // group id for each face (optional input)
  int                        curFaceInputPos_;   // current # indices set by user
807
808
809
810

  MeshCompilerFaceInput* faceInput_;   // face data input interface
  bool deleteFaceInputeData_;       // delete if face input data internally created

811
  std::vector<int>  faceBufSplit_; // mapping from (faceID, cornerID) to interleaved vertex id after splitting
812
  std::vector<int>  faceSortMap_;  // face IDs sorted by group; maps sortFaceID -> FaceID
813
814
  int               provokingVertex_; // provoking vertex of each triangle
  bool              provokingVertexSetByUser_; // was the provoking vertex selected by user or set to default?
815
816
817
818

  int   numTris_;
  std::vector<int>  triIndexBuffer_; // triangulated index buffer with interleaved vertices

819
820
  // IDs of isolated vertices: index into input position buffer
  std::vector<int>  isolatedVertices_;
821
822
823
824
825
826
827
828

  // face grouping with subsets for per-face materials
  int     numSubsets_;
  std::vector<Subset> subsets_;
  std::map<int, int> subsetIDMap_; // maps groupId -> subsetID

  // =====================================================

829
  struct ACGDLLEXPORT AdjacencyList 
830
  {
831
832
833
834
835
836
837
838
    AdjacencyList()
      : start(0), count(0), buf(0), bufSize(0), num(0) {}
    ~AdjacencyList()
    {
      delete [] start;
      delete [] buf;
      delete [] count;
    }
839
840
841
842
843

    void init(int n);
    int  getAdj(int i, int k) const;
    int  getCount(int i) const;

844
845
    void clear();

846
    int* start;   // index to adjacency buffer
847
    unsigned char* count;   // # of adjacent faces
848
849
850
851
    int* buf;     // adjacency data
    int  bufSize; // size of buf
    int  num;     // # adjacency entries

Jan Möbius's avatar
Jan Möbius committed
852
853
//    void dbgdump(FILE* file) const;
    void dbgdump(std::ofstream& file) const;
854
855
856
857
858
  };

  // adjacency list: vertex -> faces
  AdjacencyList adjacencyVert_;

859
860
861
862
863
864
865
866
  // adjacency access interface (choosing between user input / self generated data)
  int getAdjVertexFaceCount(int _vertexID) const;
  int getAdjVertexFace(int _vertexID, int _k) const;


  struct WeldListEntry
  {
    int faceId;
867
    int cornerId;
868
869
    
    int refFaceId;
870
    int refCornerId;
871
872
873
874
875
876
877
878
879
880
  };

  struct ACGDLLEXPORT WeldList
  {
    void add(const int _face, const int _corner);

    std::vector< WeldListEntry > list;

    MeshCompiler* meshComp;
    MeshCompilerVertexCompare* cmpFunc;
881

882
883
884
885
886
887
888
889
890
    char* workBuf;
  };


  static MeshCompilerVertexCompare defaultVertexCompare;
  MeshCompilerVertexCompare* vertexCompare_;

  // mapping from <faceId, faceCornerId> -> <weldFaceId, weldFaceCorner>
//  std::vector< std::pair<int, unsigned char> > vertexWeldMap_;   // std::pair<int, unsigned char> gets padded to 8 bytes
891
892
  std::vector<int> vertexWeldMapFace_;
  std::vector<int> vertexWeldMapCorner_;
893
894


895
  struct ACGDLLEXPORT VertexSplitter 
896
897
898
899
900
901
902
903
904
905
906
907
908
  {
    // worst case split: num entries in vertex adj list
    // estBufferIncrease: if numWorstCase == 0, then we estimate an increase in vertex buffer by this percentage
    VertexSplitter(int numAttribs,
                   int numVerts,
                   int numWorstCase = 0,
                   float estBufferIncrease = 0.5f);

    ~VertexSplitter();

    /// returns a unique index for a vertex-attribute combination
    int split(int* vertex);

909
910
911
    /// check if vertex is isolated with a complete splitting list
    bool isIsolated(const int vertexPosID);

912
913
914
915
916
    int  numAttribs;

    /// number of vertex combinations currently in use
    int  numVerts;

917
918
919
    /// number of input vertex positions
    const int  numBaseVerts;

920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
    /** split list format:
         for each vertex: [next split,  attribute ids]
          next split: -1 -> not split yet
                       i -> index into split list for next combination
                             with the same vertex position id (single linked list)

          attribute ids:
            array of attribute indices into input buffers,
            that makes up the complete vertex
            -1 -> vertex not used yet (relevant for split() only)
    */
//    int* splits;
    std::vector<int> splits;

    // split list access
935
936
937
938
939
940
941
942
    int  getNext(const int id);
    int* getAttribs(const int id);
    void setNext(const int id, const int next);
    void setAttribs(const int id, int* attr);

    // debugging metrics
    int dbg_numResizes;
    int dbg_numSplits;
943
944
945
946
947
948
949
950
951
952
953
954
955
956
  };

  VertexSplitter*  splitter_;

  // =====================================================

  // mappings

  /// maps from triangle ID to sorted face ID
  std::vector<int> triToSortFaceMap_;

  /// maps from optimized tri ID to unoptimized tri ID
  std::vector<int> triOptMap_;

957
958
  /// vertex index in vbo -> input (face id, corner id) pair , also inverse of faceBufSplit_
//  std::vector<std::pair<int, unsigned char> > vertexMap_; // sizeof( std::pair<int, unsigned char> ) = 8!!
959
960
  std::vector<int> vertexMapFace_;
  std::vector<int> vertexMapCorner_;
961
962
963

  /// input face index -> output tri index
  std::vector<int> faceToTriMap_;
964
965
966
967
  std::vector<int> faceToTriMapOffset_; 

  /// output tri index -> input face index
  std::vector<int> triToFaceMap_;
968
969
970
971
972
973

  // =====================================================

  // final buffers used for drawing

  /// # vertices in vbo
Jan Möbius's avatar
Jan Möbius committed
974
  size_t numDrawVerts_;
975

976
  /// # isolated vertices
Jan Möbius's avatar
Jan Möbius committed
977
  size_t numIsolatedVerts_;
978

979
  /// index buffer
980
  std::vector<int>  indices_;
981
982
983
984
985
986
987
988

private:

  // return interleaved vertex id for input buffers
  int getInputIndexSplit(const int _face, const int _corner) const;

  void setInputIndexSplit(const int _face, const int _corner, const int _val);

989
  int mapTriToInputFace(const int _tri) const;
990

991
  int getInputIndexOffset(const int _face, const int _corner) const;
992

993
994
  inline int getInputFaceOffset(const int _face) const
  {
Jan Möbius's avatar
Jan Möbius committed
995
    return int(faceStart_.empty() ? maxFaceSize_ * _face : faceStart_[_face]);
996
  }
997
998
999
1000

  /// build() preparation
  void prepareData();

1001
1002
1003
  // find isolated vertices
  void findIsolatedVertices();

1004
1005
  // make sure each face has one vertex id without any references by neighboring faces
  // split vertices when necessary
1006
1007
  void forceUnsharedFaceVertex();

1008
1009
1010
1011
1012
1013
  // eliminate duplicate attribute entries
  void weldVertices();

  // fix incomplete welding map if mesh contains isolated vertices
  void fixWeldMap();

1014
  // convert n-poly -> tris (triangle fans)
1015
1016
  void triangulate();

1017
1018
1019
  // resolve triangulation
  void resolveTriangulation();

1020
  // sort input faces by group ids
1021
1022
  void sortFacesByGroup();

1023
  // v-cache optimization + vertex reorder
1024
1025
  void optimize();

1026
  // create vertex mapping: input id <-> final buffer id
1027
  void createVertexMap(bool _keepIsolatedVerts);
1028
1029

  // create face mapping: input id <-> final tri id
1030
1031
  void createFaceMap();

1032
1033
public:

1034
1035
1036
1037
1038
1039
1040
1041
1042
  /** \brief Multi-threaded version of getIndexAdjBuffer
   * 
   * Uses a multi-threaded method based on the vertex-triangle adjacency list to compute the index buffer with adjacency.
   *
   * @param _dst [out] Pointer to memory address where the 32bit index buffer should be copied to. Must have size of at least 6 * numTris * 4 bytes
   * @param _borderIndex index to use for border edges (missing adjacent triangles)
  */
  void getIndexAdjBuffer_MT(void* _dst, const int _borderIndex = -1);

1043
1044
1045
  // debugging tools

  /// dump mesh info to text file
1046
  void dbgdump(const char* _filename) const;
1047
1048

  /// dump mesh in wavefront obj format
1049
  void dbgdumpObj(const char* _filename) const;
1050

1051
1052
1053
1054
1055
1056
  /// dump input mesh to binary file format
  void dbgdumpInputBin(const char* _filename, bool _seperateFiles = false) const;

  /// dump input mesh to wavefront obj format
  void dbgdumpInputObj(const char* _filename) const;

1057
  /// dump adjacency list to text file
1058
1059
  void dbgdumpAdjList(const char* _filename) const;

1060
1061
1062
1063
1064
1065
  /// test correctness of input <-> output id mappings, unshared per face vertex.. logs errors in file
  bool dbgVerify(const char* _filename) const;

  /// interpret vertex data according declaration and write to string
  std::string vertexToString(const void* v) const;

1066
  /// return memory consumption in bytes
1067
1068
  /// @param _printConsole print detailed memory costs to command console
  size_t getMemoryUsage(bool _printConsole = true) const;
1069

1070
1071
  /// check for errors in input data
  std::string checkInputData() const;
1072
1073
};

1074
1075
1076
1077
1078
1079
1080
1081
1082
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
};
1083
1084
1085


}