Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024 namespace PolyVox
00025 {
00036 template <typename VertexType>
00037 MeshDecimator<VertexType>::MeshDecimator(const SurfaceMesh<VertexType>* pInputMesh, SurfaceMesh<VertexType>* pOutputMesh, float fEdgeCollapseThreshold)
00038 :m_pInputMesh(pInputMesh)
00039 ,m_pOutputMesh(pOutputMesh)
00040 ,m_fMinDotProductForCollapse(fEdgeCollapseThreshold)
00041 {
00042 *m_pOutputMesh = *m_pInputMesh;
00043 }
00044
00045 template <typename VertexType>
00046 void MeshDecimator<VertexType>::execute()
00047 {
00048
00049 if((m_pOutputMesh->m_vecVertices.empty()) || (m_pOutputMesh->m_vecTriangleIndices.empty()))
00050 {
00051 return;
00052 }
00053
00054 buildConnectivityData();
00055 fillInitialVertexMetadata(m_vecInitialVertexMetadata);
00056
00057 uint32_t noOfEdgesCollapsed;
00058 do
00059 {
00060 noOfEdgesCollapsed = performDecimationPass(m_fMinDotProductForCollapse);
00061 m_pOutputMesh->removeDegenerateTris();
00062 if(noOfEdgesCollapsed > 0)
00063 {
00064
00065
00066 buildConnectivityData();
00067 }
00068 }while(noOfEdgesCollapsed > 0);
00069
00070 m_pOutputMesh->removeUnusedVertices();
00071
00072
00073 m_pOutputMesh->m_vecLodRecords.clear();
00074 LodRecord lodRecord;
00075 lodRecord.beginIndex = 0;
00076 lodRecord.endIndex = m_pOutputMesh->getNoOfIndices();
00077 m_pOutputMesh->m_vecLodRecords.push_back(lodRecord);
00078 }
00079
00080 template <typename VertexType>
00081 void MeshDecimator<VertexType>::buildConnectivityData(void)
00082 {
00083
00084 m_vecTriangles.clear();
00085 m_vecTriangles.resize(m_pOutputMesh->m_vecTriangleIndices.size() / 3);
00086 for(uint32_t triCt = 0; triCt < m_vecTriangles.size(); triCt++)
00087 {
00088 m_vecTriangles[triCt].v0 = m_pOutputMesh->m_vecTriangleIndices[triCt * 3 + 0];
00089 m_vecTriangles[triCt].v1 = m_pOutputMesh->m_vecTriangleIndices[triCt * 3 + 1];
00090 m_vecTriangles[triCt].v2 = m_pOutputMesh->m_vecTriangleIndices[triCt * 3 + 2];
00091
00092 Vector3DFloat v0Pos = m_pOutputMesh->m_vecVertices[m_vecTriangles[triCt].v0].position;
00093 Vector3DFloat v1Pos = m_pOutputMesh->m_vecVertices[m_vecTriangles[triCt].v1].position;
00094 Vector3DFloat v2Pos = m_pOutputMesh->m_vecVertices[m_vecTriangles[triCt].v2].position;
00095
00096 Vector3DFloat v0v1 = v1Pos - v0Pos;
00097 Vector3DFloat v0v2 = v2Pos - v0Pos;
00098 Vector3DFloat normal = v0v1.cross(v0v2);
00099 normal.normalise();
00100
00101 m_vecTriangles[triCt].normal = normal;
00102 }
00103
00104
00105 trianglesUsingVertex.clear();
00106 trianglesUsingVertex.resize(m_pOutputMesh->m_vecVertices.size());
00107 for(uint32_t ct = 0; ct < trianglesUsingVertex.size(); ct++)
00108 {
00109 trianglesUsingVertex[ct].reserve(6);
00110 }
00111 for(uint32_t ct = 0; ct < m_vecTriangles.size(); ct++)
00112 {
00113 trianglesUsingVertex[m_vecTriangles[ct].v0].push_back(ct);
00114 trianglesUsingVertex[m_vecTriangles[ct].v1].push_back(ct);
00115 trianglesUsingVertex[m_vecTriangles[ct].v2].push_back(ct);
00116 }
00117 }
00118
00119 template <typename VertexType>
00120 uint32_t MeshDecimator<VertexType>::performDecimationPass(float )
00121 {
00122
00123 uint32_t noOfEdgesCollapsed = 0;
00124
00125
00126 vertexMapper.clear();
00127 vertexMapper.resize(m_pOutputMesh->m_vecVertices.size());
00128
00129
00130
00131
00132
00133 vertexLocked.clear();
00134 vertexLocked.resize(m_pOutputMesh->m_vecVertices.size());
00135
00136
00137 for(uint32_t ct = 0; ct < m_pOutputMesh->m_vecVertices.size(); ct++)
00138 {
00139
00140 vertexMapper[ct] = ct;
00141
00142 vertexLocked[ct] = false;
00143 }
00144
00145
00146 for(uint32_t ctIter = 0; ctIter < m_vecTriangles.size(); ctIter++)
00147 {
00148 if(attemptEdgeCollapse(m_vecTriangles[ctIter].v0, m_vecTriangles[ctIter].v1))
00149 {
00150 ++noOfEdgesCollapsed;
00151 }
00152
00153 if(attemptEdgeCollapse(m_vecTriangles[ctIter].v1, m_vecTriangles[ctIter].v2))
00154 {
00155 ++noOfEdgesCollapsed;
00156 }
00157
00158 if(attemptEdgeCollapse(m_vecTriangles[ctIter].v2, m_vecTriangles[ctIter].v0))
00159 {
00160 ++noOfEdgesCollapsed;
00161 }
00162 }
00163
00164 if(noOfEdgesCollapsed > 0)
00165 {
00166
00167 for(uint32_t triCt = 0; triCt < m_pOutputMesh->m_vecTriangleIndices.size(); triCt++)
00168 {
00169 uint32_t before = m_pOutputMesh->m_vecTriangleIndices[triCt];
00170 uint32_t after = vertexMapper[m_pOutputMesh->m_vecTriangleIndices[triCt]];
00171 if(before != after)
00172 {
00173 m_pOutputMesh->m_vecTriangleIndices[triCt] = vertexMapper[m_pOutputMesh->m_vecTriangleIndices[triCt]];
00174 }
00175 }
00176 }
00177
00178 return noOfEdgesCollapsed;
00179 }
00180
00181 template <typename VertexType>
00182 bool MeshDecimator<VertexType>::attemptEdgeCollapse(uint32_t uSrc, uint32_t uDst)
00183 {
00184
00185 if(vertexLocked[uSrc] || vertexLocked[uDst])
00186 {
00187 return false;
00188 }
00189
00190 if(canCollapseEdge(uSrc, uDst))
00191 {
00192
00193 vertexMapper[uSrc] = uDst;
00194 vertexLocked[uSrc] = true;
00195 vertexLocked[uDst] = true;
00196
00197
00198 return true;
00199 }
00200
00201 return false;
00202 }
00203
00204 template <typename VertexType>
00205 bool MeshDecimator<VertexType>::canCollapseEdge(uint32_t uSrc, uint32_t uDst)
00206 {
00207 bool bCanCollapse = true;
00208
00209 if(m_vecInitialVertexMetadata[uSrc].isOnMaterialEdge)
00210 {
00211 bCanCollapse &= canCollapseMaterialEdge(uSrc, uDst);
00212 }
00213
00214 if(m_vecInitialVertexMetadata[uSrc].isOnRegionFace.any())
00215 {
00216 bCanCollapse &= canCollapseRegionEdge(uSrc, uDst);
00217 }
00218
00219 if(bCanCollapse)
00220 {
00221 bCanCollapse &= canCollapseNormalEdge(uSrc, uDst);
00222 }
00223
00224 return bCanCollapse;
00225 }
00226
00227 template <typename VertexType>
00228 bool MeshDecimator<VertexType>::canCollapseRegionEdge(uint32_t uSrc, uint32_t uDst)
00229 {
00230
00231
00232
00233 if(isSubset(m_vecInitialVertexMetadata[uSrc].isOnRegionFace, m_vecInitialVertexMetadata[uDst].isOnRegionFace) == false)
00234 {
00235 return false;
00236 }
00237
00238
00239
00240
00241
00242 if(m_vecInitialVertexMetadata[uSrc].normal.dot(m_vecInitialVertexMetadata[uDst].normal) < 0.999f)
00243 {
00244 return false;
00245 }
00246
00247 return true;
00248 }
00249
00250 template <typename VertexType>
00251 bool MeshDecimator<VertexType>::canCollapseMaterialEdge(uint32_t , uint32_t )
00252 {
00253 return false;
00254 }
00255
00256
00257
00258 template <typename VertexType>
00259 bool MeshDecimator<VertexType>::collapseChangesFaceNormals(uint32_t uSrc, uint32_t uDst, float fThreshold)
00260 {
00261 bool faceFlipped = false;
00262 std::vector<uint32_t>& triangles = trianglesUsingVertex[uSrc];
00263
00264 for(std::vector<uint32_t>::iterator triIter = triangles.begin(); triIter != triangles.end(); triIter++)
00265 {
00266 uint32_t tri = *triIter;
00267
00268 const uint32_t& v0Old = m_pOutputMesh->m_vecTriangleIndices[tri * 3];
00269 const uint32_t& v1Old = m_pOutputMesh->m_vecTriangleIndices[tri * 3 + 1];
00270 const uint32_t& v2Old = m_pOutputMesh->m_vecTriangleIndices[tri * 3 + 2];
00271
00272
00273 if((v0Old == v1Old) || (v1Old == v2Old) || (v2Old == v0Old))
00274 {
00275 continue;
00276 }
00277
00278 uint32_t v0New = v0Old;
00279 uint32_t v1New = v1Old;
00280 uint32_t v2New = v2Old;
00281
00282 if(v0New == uSrc)
00283 v0New = uDst;
00284 if(v1New == uSrc)
00285 v1New = uDst;
00286 if(v2New == uSrc)
00287 v2New = uDst;
00288
00289
00290 if((v0New == v1New) || (v1New == v2New) || (v2New == v0New))
00291 {
00292 continue;
00293 }
00294
00295 const Vector3DFloat& v0OldPos = m_pOutputMesh->m_vecVertices[vertexMapper[v0Old]].getPosition();
00296 const Vector3DFloat& v1OldPos = m_pOutputMesh->m_vecVertices[vertexMapper[v1Old]].getPosition();
00297 const Vector3DFloat& v2OldPos = m_pOutputMesh->m_vecVertices[vertexMapper[v2Old]].getPosition();
00298
00299 const Vector3DFloat& v0NewPos = m_pOutputMesh->m_vecVertices[vertexMapper[v0New]].getPosition();
00300 const Vector3DFloat& v1NewPos = m_pOutputMesh->m_vecVertices[vertexMapper[v1New]].getPosition();
00301 const Vector3DFloat& v2NewPos = m_pOutputMesh->m_vecVertices[vertexMapper[v2New]].getPosition();
00302
00303 Vector3DFloat OldNormal = (v1OldPos - v0OldPos).cross(v2OldPos - v1OldPos);
00304 Vector3DFloat NewNormal = (v1NewPos - v0NewPos).cross(v2NewPos - v1NewPos);
00305
00306 OldNormal.normalise();
00307 NewNormal.normalise();
00308
00309 float dotProduct = OldNormal.dot(NewNormal);
00310
00311 if(dotProduct < fThreshold)
00312 {
00313
00314
00315 faceFlipped = true;
00316
00317
00318
00319
00320 break;
00321 }
00322 }
00323
00324 return faceFlipped;
00325 }
00326
00327
00328 template <typename VertexType>
00329 bool MeshDecimator<VertexType>::isSubset(std::bitset<RFF_NO_OF_REGION_FACE_FLAGS> a, std::bitset<RFF_NO_OF_REGION_FACE_FLAGS> b)
00330 {
00331 bool result = true;
00332
00333 for(int ct = 0; ct < RFF_NO_OF_REGION_FACE_FLAGS; ct++)
00334 {
00335 if(a.test(ct))
00336 {
00337 if(b.test(ct) == false)
00338 {
00339 result = false;
00340 break;
00341 }
00342 }
00343 }
00344
00345 return result;
00346 }
00347 }