Developer Documentation
MeshCompiler.hh
1 /*===========================================================================*\
2  * *
3  * OpenFlipper *
4  * Copyright (c) 2001-2015, RWTH-Aachen University *
5  * Department of Computer Graphics and Multimedia *
6  * All rights reserved. *
7  * www.openflipper.org *
8  * *
9  *---------------------------------------------------------------------------*
10  * This file is part of OpenFlipper. *
11  *---------------------------------------------------------------------------*
12  * *
13  * Redistribution and use in source and binary forms, with or without *
14  * modification, are permitted provided that the following conditions *
15  * are met: *
16  * *
17  * 1. Redistributions of source code must retain the above copyright notice, *
18  * this list of conditions and the following disclaimer. *
19  * *
20  * 2. Redistributions in binary form must reproduce the above copyright *
21  * notice, this list of conditions and the following disclaimer in the *
22  * documentation and/or other materials provided with the distribution. *
23  * *
24  * 3. Neither the name of the copyright holder nor the names of its *
25  * contributors may be used to endorse or promote products derived from *
26  * this software without specific prior written permission. *
27  * *
28  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS *
29  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED *
30  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A *
31  * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER *
32  * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, *
33  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, *
34  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR *
35  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF *
36  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING *
37  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS *
38  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. *
39  * *
40 \*===========================================================================*/
41 
42 /*===========================================================================*\
43 * *
44 * $Revision$ *
45 * $LastChangedBy$ *
46 * $Date$ *
47 * *
48 \*===========================================================================*/
49 
50 
51 #pragma once
52 
53 #include "VertexDeclaration.hh"
54 
55 #include <map>
56 #include <vector>
57 #include <cstdio>
58 #include <string>
59 #include <fstream>
60 
61 #include <ACG/GL/gl.hh>
62 
63 /*
64 
65 Mesh buffer assembler:
66 
67 Builds a pair of vertex and index buffer based on a poly mesh.
68 
69 
70 - flexible processing pipeline
71 - uses index mapping only -> lower memory consumption
72 - independent of OpenMesh, OpenGL
73 -
74 
75 
76 
77 usage
78 
79 1. Create a vertex declaration to specify your wanted
80  vertex format, such as float3 pos, float3 normal..
81 
82 2. Set your vertex data.
83  Example in (float3 pos, float3 normal, float2 texc) format:
84 
85  float VertexPositions[100*3] = {..};
86  float VertexNormals[120*3] = {..};
87  float VertexUV[80*2] = {..};
88 
89  drawMesh->setVertices(100, VertexPositions, 12);
90  drawMesh->setNormals(120, VertexNormals, 12);
91  drawMesh->setTexCoords(80, VertexUV, 8);
92 
93  Note that different indices for vertices, normals and texcoords are allowed,
94  hence the various element numbers 100, 120 and 80.
95 
96 
97  Example 2 (interleaved input)
98 
99  float Vertices[100] = {
100  x0, y0, z0, u0, v0, nx0, ny0, nz0,
101  x1, y1, z1, u1, v1, nx1, ny1, nz1,
102  ...
103  };
104 
105  The stride is 8*4 = 32 bytes.
106  We use parameters as follows.
107 
108  drawMesh->setVertices(100, Vertices, 32);
109  drawMesh->setNormals(100, (char*)Vertices + 20, 32);
110  drawMesh->setTexCoords(100, (char*)Vertices + 12, 32);
111 
112 3. Set index data.
113 
114  Two methods are supported for this.
115 
116  You can either specify one index set for all vertex attributes
117  or use another index buffer for each vertex attribute.
118  The latter means having different indices for vertex and texcoords for example.
119 
120 
121  drawMesh->setNumFaces(32, 96);
122 
123 
124  for each face i
125  int* faceVertexIndices = {v0, v1, v2, ...};
126  setFaceVerts(i, 3, faceVertexIndices);
127 
128 4. finish the initialization by calling the build() function
129 
130 */
131 
132 namespace ACG{
133 
134 class ACGDLLEXPORT MeshCompilerFaceInput
135 {
136  // face data input interface
137  // allows flexible and memory efficient face data input
138 
139 public:
141  virtual ~MeshCompilerFaceInput(){}
142 
143  virtual int getNumFaces() const = 0;
144 
149  virtual int getNumIndices() const = 0;
150 
154  virtual int getFaceSize(const int _faceID) const = 0;
155 
163  virtual int getSingleFaceAttr(const int _faceID, const int _faceCorner, const int _attrID) const;
164 
171  virtual bool getFaceAttr(const int _faceID, const int _attrID, int* _out) const {return false;}
172 
178  virtual int* getFaceAttr(const int _faceID, const int _attrID) const {return 0;}
179 
180 
181  // Adjacency information can be provided if it has been generated already.
182  // Otherwise it will be generated on the fly when needed, which might be time consuming.
183 
188  virtual int getVertexAdjCount(const int _vertexID) const {return -1;}
189 
195  virtual int getVertexAdjFace(const int _vertexID, const int _k) const {return -1;}
196 
197 };
198 
200 {
201 public:
202  MeshCompilerDefaultFaceInput(int _numFaces, int _numIndices);
203  virtual ~MeshCompilerDefaultFaceInput(){}
204 
205  int getNumFaces() const {return numFaces_;}
206  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  void dbgWriteToObjFile(FILE* _file, int _posAttrID = 0, int _normalAttrID = -1, int _texcAttrID = -1);
215 
216 
217  void setFaceData(int _faceID, int _size, int* _data, int _attrID = 0);
218 
219 protected:
220 
221  int numFaces_,
222  numIndices_;
223 
224  // input data is stored in a sequence stream
225  // face offsets may not be in sequence
226  std::vector<int> faceOffset_;
227  std::vector<int> faceSize_;
228 
229  // face index buffer for each vertex attribute
230  std::vector<int> faceData_[16];
231 
232 };
233 
234 
235 class ACGDLLEXPORT MeshCompilerVertexCompare
236 {
237 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  const double d_eps_;
243  const float f_eps_;
244 };
245 
246 class ACGDLLEXPORT MeshCompiler
247 {
248 public:
249 
250  MeshCompiler(const VertexDeclaration& _decl);
251 
252  virtual ~MeshCompiler();
253 
254 //===========================================================================
257 //===========================================================================
258 
268  void setVertices(int _num, const void* _data, int _stride = 0, bool _internalCopy = false, GLuint _fmt = 0, int _elementSize = -1);
269 
279  void setNormals(int _num, const void* _data, int _stride = 0, bool _internalCopy = false, GLuint _fmt = 0, int _elementSize = -1);
280 
290  void setTexCoords(int _num, const void* _data, int _stride = 0, bool _internalCopy = false, GLuint _fmt = 0, int _elementSize = -1);
291 
303  void setAttribVec(int _attrIdx, int _num, const void* _data, int _stride = 0, bool _internalCopy = false, GLuint _fmt = 0, int _elementSize = -1);
304 
312  void setAttrib(int _attrIdx, int _v, const void* _data);
313 
314 
319  int getNumInputAttributes(int _attrIdx) const;
320 
324 //===========================================================================
327 //===========================================================================
328 
336  void setFaceInput(MeshCompilerFaceInput* _faceInput);
337 
340 //===========================================================================
343 //===========================================================================
344 
352  void setNumFaces(const int _numFaces, const int _numIndices);
353 
354 
362  void setIndexBufferInterleaved(int _numTris, int _indexSize, const void* _indices);
363 
371  void setFaceVerts(int _i, int _v0, int _v1, int _v2);
372 
379  void setFaceVerts(int _i, int _faceSize, int* _v);
380 
388  void setFaceNormals(int _i, int _v0, int _v1, int _v2);
389 
396  void setFaceNormals(int _i, int _faceSize, int* _v);
397 
405  void setFaceTexCoords(int _i, int _v0, int _v1, int _v2);
406 
413  void setFaceTexCoords(int _i, int _faceSize, int* _v);
414 
415 
424  void setFaceAttrib(int _i, int _v0, int _v1, int _v2, int _attrID);
425 
433  void setFaceAttrib(int _i, int _faceSize, int* _v, int _attrID);
434 
435 
438 //===========================================================================
441 //===========================================================================
442 
443 
451  void setFaceGroup(int _i, short _groupID);
452 
453  // subset/group management
454  struct Subset
455  {
456  int id; // subset id
457  unsigned int startIndex; // 1st occurrence of group in index buffer
458  unsigned int numTris; // number of tris belonging to subset in index buffer
459 
460  unsigned int numFaces; // number of faces belonging to subset
461  unsigned int startFace; // index into sorted list of faces
462  };
463 
469  int findGroupSubset(int _groupID);
470 
476  int getFaceGroup(int _faceID) const;
477 
483  int getTriGroup(int _triID) const;
484 
489  int getNumSubsets() const {return (int)subsets_.size();}
490 
496  const Subset* getSubset(int _i) const;
497 
498 
501 //===========================================================================
504 //===========================================================================
505 
506 
514  void build(bool _weldVertices = false, bool _optimizeVCache = true, bool _needPerFaceAttribute = false, bool _keepIsolatedVertices = false);
515 
518  int getNumVertices() const {return numDrawVerts_;}
519 
530  void setProvokingVertex(int _v);
531 
536  int getProvokingVertex() const {return provokingVertex_;}
537 
538 
547  void getVertexBuffer(void* _dst, const int _offset = 0, const int _range = -1);
548 
551  const int* getIndexBuffer() const {return indices_.data();}
552 
577  void getIndexAdjBuffer(void* _dst, const int _borderIndex = -1);
578 
588  void getIndexAdjBuffer_BruteForce(void* _dst, const int _borderIndex = -1);
589 
590 
593  int getNumTriangles() const {return numTris_;}
594 
597  int getNumFaces() const;
598 
604  inline int getFaceSize(const int _i) const
605  {
606  return int(faceSize_.empty() ? maxFaceSize_ : faceSize_[_i]);
607  }
608 
611  const VertexDeclaration* getVertexDeclaration() const {return &decl_;}
612 
615  void getVertex(int _id, void* _out) const;
616 
619  int getIndex(int _i) const;
620 
621 
626 //===========================================================================
629 //===========================================================================
630 
631 
639  int mapToOriginalVertexID(const int _i, int& _faceID, int& _cornerID) const;
640 
646  int mapToOriginalFaceID(const int _triID) const;
647 
652  const int* mapToOriginalFaceIDPtr() const;
653 
660  int mapToDrawVertexID(const int _faceID, const int _cornerID) const;
661 
669  int mapToDrawTriID(const int _faceID, const int _k = 0, int* _numTrisOut = 0) const;
670 
671 
675 //===========================================================================
678 //===========================================================================
679 
682  bool isTriangleMesh() const;
683 
692  bool isFaceEdge(const int _triID, const int _edge) const;
693 
694 
699 private:
700 
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  void splitVertices();
706 
707 private:
708 
709  // small helper functions
710 
715  void getInputFaceVertex(const int _face, const int _corner, int* _out) const;
716 
721  void getInputFaceVertex_Welded(const int _face, const int _corner, int* _out) const;
722 
727  void getInputFaceVertexData(const int _face, const int _corner, void* _out) const;
728 
729 
730  inline int getInputIndex( const int& _face, const int& _corner, const int& _attrId ) const
731  {
732  return faceInput_->getSingleFaceAttr(_face, _corner, _attrId);
733 
734  // alternatively avoid virtual function call at cost of higher memory overhead ( could not confirm any run-time difference )
735  // to use this, uncomment code in prepareData() that initializes faceData_ array as well
736 // return faceData_[(getInputFaceOffset(_face) + _corner) * numAttributes_ + _attrId];
737  }
738 
739 
740 private:
741 
742  // ====================================================
743  // input data
744 
745 
746  // vertex buffer input
747 
748  struct ACGDLLEXPORT VertexElementInput
749  {
751  ~VertexElementInput();
752 
754  char* internalBuf;
755 
759  const char* data;
760 
762  int count;
763 
765  int stride;
766 
768  int attrSize;
769 
770 
771  // vertex data access
772 
774  GLuint fmt;
775 
778 
780  void getElementData(int _idx, void* _dst, const VertexElement* _desc) const;
781  };
782 
783  // input vertex data
784  VertexElementInput input_[16];
785 
786  // convenient attribute indices
787  int inputIDPos_; // index of positions into input_ array
788  int inputIDNorm_; // index of normals into input_ array
789  int inputIDTexC_; // index of texcoords into input_ array
790 
791  int numAttributes_;
792  VertexDeclaration decl_;
793 
794 
795  // input face data
796 
797  int numFaces_,
798  numIndices_;
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
802  std::vector<int> faceData_;
803  size_t maxFaceSize_; // max(faceSize_)
804  bool constantFaceSize_;
805  std::vector<short> faceGroupIDs_; // group id for each face (optional input)
806  int curFaceInputPos_; // current # indices set by user
807 
808  MeshCompilerFaceInput* faceInput_; // face data input interface
809  bool deleteFaceInputeData_; // delete if face input data internally created
810 
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  int provokingVertex_; // provoking vertex of each triangle
814  bool provokingVertexSetByUser_; // was the provoking vertex selected by user or set to default?
815 
816  int numTris_;
817  std::vector<int> triIndexBuffer_; // triangulated index buffer with interleaved vertices
818 
819  // IDs of isolated vertices: index into input position buffer
820  std::vector<int> isolatedVertices_;
821 
822  // face grouping with subsets for per-face materials
823  int numSubsets_;
824  std::vector<Subset> subsets_;
825  std::map<int, int> subsetIDMap_; // maps groupId -> subsetID
826 
827  // =====================================================
828 
829  struct ACGDLLEXPORT AdjacencyList
830  {
831  AdjacencyList()
832  : start(0), count(0), buf(0), bufSize(0), num(0) {}
833  ~AdjacencyList()
834  {
835  delete [] start;
836  delete [] buf;
837  delete [] count;
838  }
839 
840  void init(int n);
841  int getAdj(int i, int k) const;
842  int getCount(int i) const;
843 
844  void clear();
845 
846  int* start; // index to adjacency buffer
847  unsigned char* count; // # of adjacent faces
848  int* buf; // adjacency data
849  int bufSize; // size of buf
850  int num; // # adjacency entries
851 
852 // void dbgdump(FILE* file) const;
853  void dbgdump(std::ofstream& file) const;
854  };
855 
856  // adjacency list: vertex -> faces
857  AdjacencyList adjacencyVert_;
858 
859  // adjacency access interface (choosing between user input / self generated data)
860  int getAdjVertexFaceCount(int _vertexID) const;
861  int getAdjVertexFace(int _vertexID, int _k) const;
862 
863 
865  {
866  int faceId;
867  int cornerId;
868 
869  int refFaceId;
870  int refCornerId;
871  };
872 
873  struct ACGDLLEXPORT WeldList
874  {
875  void add(const int _face, const int _corner);
876 
877  std::vector< WeldListEntry > list;
878 
879  MeshCompiler* meshComp;
880  MeshCompilerVertexCompare* cmpFunc;
881 
882  char* workBuf;
883  };
884 
885 
886  static MeshCompilerVertexCompare defaultVertexCompare;
887  MeshCompilerVertexCompare* vertexCompare_;
888 
889  // mapping from <faceId, faceCornerId> -> <weldFaceId, weldFaceCorner>
890 // std::vector< std::pair<int, unsigned char> > vertexWeldMap_; // std::pair<int, unsigned char> gets padded to 8 bytes
891  std::vector<int> vertexWeldMapFace_;
892  std::vector<int> vertexWeldMapCorner_;
893 
894 
895  struct ACGDLLEXPORT VertexSplitter
896  {
897  // worst case split: num entries in vertex adj list
898  // estBufferIncrease: if numWorstCase == 0, then we estimate an increase in vertex buffer by this percentage
899  VertexSplitter(int numAttribs,
900  int numVerts,
901  int numWorstCase = 0,
902  float estBufferIncrease = 0.5f);
903 
904  ~VertexSplitter();
905 
907  int split(int* vertex);
908 
910  bool isIsolated(const int vertexPosID);
911 
912  int numAttribs;
913 
915  int numVerts;
916 
918  const int numBaseVerts;
919 
931 // int* splits;
932  std::vector<int> splits;
933 
934  // split list access
935  int getNext(const int id);
936  int* getAttribs(const int id);
937  void setNext(const int id, const int next);
938  void setAttribs(const int id, int* attr);
939 
940  // debugging metrics
941  int dbg_numResizes;
942  int dbg_numSplits;
943  };
944 
945  VertexSplitter* splitter_;
946 
947  // =====================================================
948 
949  // mappings
950 
952  std::vector<int> triToSortFaceMap_;
953 
955  std::vector<int> triOptMap_;
956 
958 // std::vector<std::pair<int, unsigned char> > vertexMap_; // sizeof( std::pair<int, unsigned char> ) = 8!!
959  std::vector<int> vertexMapFace_;
960  std::vector<int> vertexMapCorner_;
961 
963  std::vector<int> faceToTriMap_;
964  std::vector<int> faceToTriMapOffset_;
965 
967  std::vector<int> triToFaceMap_;
968 
969  // =====================================================
970 
971  // final buffers used for drawing
972 
975 
978 
980  std::vector<int> indices_;
981 
982 private:
983 
984  // return interleaved vertex id for input buffers
985  int getInputIndexSplit(const int _face, const int _corner) const;
986 
987  void setInputIndexSplit(const int _face, const int _corner, const int _val);
988 
989  int mapTriToInputFace(const int _tri) const;
990 
991  int getInputIndexOffset(const int _face, const int _corner) const;
992 
993  inline int getInputFaceOffset(const int _face) const
994  {
995  return int(faceStart_.empty() ? maxFaceSize_ * _face : faceStart_[_face]);
996  }
997 
999  void prepareData();
1000 
1001  // find isolated vertices
1002  void findIsolatedVertices();
1003 
1004  // make sure each face has one vertex id without any references by neighboring faces
1005  // split vertices when necessary
1006  void forceUnsharedFaceVertex();
1007 
1008  // eliminate duplicate attribute entries
1009  void weldVertices();
1010 
1011  // fix incomplete welding map if mesh contains isolated vertices
1012  void fixWeldMap();
1013 
1014  // convert n-poly -> tris (triangle fans)
1015  void triangulate();
1016 
1017  // resolve triangulation
1018  void resolveTriangulation();
1019 
1020  // sort input faces by group ids
1021  void sortFacesByGroup();
1022 
1023  // v-cache optimization + vertex reorder
1024  void optimize();
1025 
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  void createFaceMap();
1031 
1032 public:
1033 
1041  void getIndexAdjBuffer_MT(void* _dst, const int _borderIndex = -1);
1042 
1043  // debugging tools
1044 
1046  void dbgdump(const char* _filename) const;
1047 
1049  void dbgdumpObj(const char* _filename) const;
1050 
1052  void dbgdumpInputBin(const char* _filename, bool _seperateFiles = false) const;
1053 
1055  void dbgdumpInputObj(const char* _filename) const;
1056 
1058  void dbgdumpAdjList(const char* _filename) const;
1059 
1061  bool dbgVerify(const char* _filename) const;
1062 
1064  std::string vertexToString(const void* v) const;
1065 
1068  size_t getMemoryUsage(bool _printConsole = true) const;
1069 
1071  std::string checkInputData() const;
1072 };
1073 
1075 {
1076  RingTriangle() {}
1077  RingTriangle(int i, RingTriangle* p, RingTriangle* n) : id(i), prev(p), next(n) {}
1078 
1079  int id; // local index of the triangle within a polygon [0, ... faceSize-3]
1080  RingTriangle* prev; // prev triangle in the ring
1081  RingTriangle* next; // next triangle in the ring
1082 };
1083 
1084 
1085 }
int getNumVertices() const
int getProvokingVertex() const
virtual int * getFaceAttr(const int _faceID, const int _attrID) const
std::vector< int > vertexMapFace_
vertex index in vbo -> input (face id, corner id) pair , also inverse of faceBufSplit_ ...
int getNumSubsets() const
Get the number of subsets.
int elementSize
number of ints/floats/bytes per element
Description of one vertex element.
int getNumTriangles() const
Class to define the vertex input layout.
virtual bool getFaceAttr(const int _faceID, const int _attrID, int *_out) const
std::vector< int > triToSortFaceMap_
maps from triangle ID to sorted face ID
std::vector< int > triToFaceMap_
output tri index -> input face index
std::vector< int > indices_
index buffer
virtual int getVertexAdjFace(const int _vertexID, const int _k) const
std::vector< int > triOptMap_
maps from optimized tri ID to unoptimized tri ID
const int * getIndexBuffer() const
char * internalBuf
mem alloc if attribute buffer managed by this class
virtual int getVertexAdjCount(const int _vertexID) const
int stride
offset in bytes from one element to the next
const int numBaseVerts
number of input vertex positions
Namespace providing different geometric functions concerning angles.
Definition: DBSCANT.cc:51
GLuint fmt
element data format
const VertexDeclaration * getVertexDeclaration() const
int numDrawVerts_
vertices in vbo
int numIsolatedVerts_
isolated vertices
int getFaceSize(const int _faceID) const
int numVerts
number of vertex combinations currently in use
int attrSize
size in bytes of one attribute
int getFaceSize(const int _i) const
Get size of input face.
std::vector< int > faceToTriMap_
input face index -> output tri index