PolyVox  0.2.1
Open source voxel management library
MeshDecimator.cpp
Go to the documentation of this file.
1 /*******************************************************************************
2 Copyright (c) 2005-2009 David Williams
3 
4 This software is provided 'as-is', without any express or implied
5 warranty. In no event will the authors be held liable for any damages
6 arising from the use of this software.
7 
8 Permission is granted to anyone to use this software for any purpose,
9 including commercial applications, and to alter it and redistribute it
10 freely, subject to the following restrictions:
11 
12  1. The origin of this software must not be misrepresented; you must not
13  claim that you wrote the original software. If you use this software
14  in a product, an acknowledgment in the product documentation would be
15  appreciated but is not required.
16 
17  2. Altered source versions must be plainly marked as such, and must not be
18  misrepresented as being the original software.
19 
20  3. This notice may not be removed or altered from any source
21  distribution.
22 *******************************************************************************/
23 
24 #include "PolyVoxCore/MeshDecimator.h"
25 #include "PolyVoxCore/SurfaceMesh.h"
26 
27 using namespace std;
28 
29 namespace PolyVox
30 {
31  template<>
32  POLYVOX_API void MeshDecimator<PositionMaterial>::fillInitialVertexMetadata(std::vector<InitialVertexMetadata>& vecVertexMetadata)
33  {
34  vecVertexMetadata.clear();
35  vecVertexMetadata.resize(m_pOutputMesh->m_vecVertices.size());
36  //Initialise the metadata
37  for(uint32_t ct = 0; ct < vecVertexMetadata.size(); ct++)
38  {
39  vecVertexMetadata[ct].normal.setElements(0,0,0);
40  vecVertexMetadata[ct].isOnMaterialEdge = false;
41  vecVertexMetadata[ct].isOnRegionFace.reset();
42  }
43 
44  //Identify duplicate vertices, as they lie on the material edge. To do this we convert into integers and sort
45  //(first on z, then y, then x). They should be mostly in order as this is the order they come out of the
46  //CubicSurfaceExtractor in. Duplicates are now neighbours in the resulting list so just scan through for pairs.
47  std::vector<IntVertex> intVertices;
48  intVertices.reserve(m_pOutputMesh->m_vecVertices.size());
49  for(uint32_t ct = 0; ct < m_pOutputMesh->m_vecVertices.size(); ct++)
50  {
51  const Vector3DFloat& floatPos = m_pOutputMesh->m_vecVertices[ct].position;
52  IntVertex intVertex(static_cast<uint32_t>(floatPos.getX()), static_cast<uint32_t>(floatPos.getY()), static_cast<uint32_t>(floatPos.getZ()), ct);
53  intVertices.push_back(intVertex);
54  }
55 
56  //Do the sorting so that duplicate become neighbours
57  sort(intVertices.begin(), intVertices.end());
58 
59  //Find neighbours which are duplicates.
60  for(uint32_t ct = 0; ct < intVertices.size() - 1; ct++)
61  {
62  const IntVertex& v0 = intVertices[ct+0];
63  const IntVertex& v1 = intVertices[ct+1];
64 
65  if((v0.x == v1.x) && (v0.y == v1.y) && (v0.z == v1.z))
66  {
67  vecVertexMetadata[v0.index].isOnMaterialEdge = true;
68  vecVertexMetadata[v1.index].isOnMaterialEdge = true;
69  }
70  }
71 
72  //Compute an approcimation to the normal, used when deciding if an edge can collapse.
73  for(uint32_t ct = 0; ct < m_pOutputMesh->m_vecVertices.size(); ct++)
74  {
75  Vector3DFloat sumOfNormals(0.0f,0.0f,0.0f);
76  for(vector<uint32_t>::iterator iter = trianglesUsingVertex[ct].begin(); iter != trianglesUsingVertex[ct].end(); iter++)
77  {
78  sumOfNormals += m_vecTriangles[*iter].normal;
79  }
80 
81  vecVertexMetadata[ct].normal = sumOfNormals;
82  vecVertexMetadata[ct].normal.normalise();
83  }
84 
85  //Identify those vertices on the edge of a region. Care will need to be taken when moving them.
86  for(uint32_t ct = 0; ct < vecVertexMetadata.size(); ct++)
87  {
88  Region regTransformed = m_pOutputMesh->m_Region;
89  regTransformed.shift(regTransformed.getLowerCorner() * static_cast<int32_t>(-1));
90 
91  //Plus and minus X
92  vecVertexMetadata[ct].isOnRegionFace.set(RFF_ON_REGION_FACE_NEG_X, m_pOutputMesh->m_vecVertices[ct].getPosition().getX() < regTransformed.getLowerCorner().getX() + 0.001f);
93  vecVertexMetadata[ct].isOnRegionFace.set(RFF_ON_REGION_FACE_POS_X, m_pOutputMesh->m_vecVertices[ct].getPosition().getX() > regTransformed.getUpperCorner().getX() - 0.001f);
94  //Plus and minus Y
95  vecVertexMetadata[ct].isOnRegionFace.set(RFF_ON_REGION_FACE_NEG_Y, m_pOutputMesh->m_vecVertices[ct].getPosition().getY() < regTransformed.getLowerCorner().getY() + 0.001f);
96  vecVertexMetadata[ct].isOnRegionFace.set(RFF_ON_REGION_FACE_POS_Y, m_pOutputMesh->m_vecVertices[ct].getPosition().getY() > regTransformed.getUpperCorner().getY() - 0.001f);
97  //Plus and minus Z
98  vecVertexMetadata[ct].isOnRegionFace.set(RFF_ON_REGION_FACE_NEG_Z, m_pOutputMesh->m_vecVertices[ct].getPosition().getZ() < regTransformed.getLowerCorner().getZ() + 0.001f);
99  vecVertexMetadata[ct].isOnRegionFace.set(RFF_ON_REGION_FACE_POS_Z, m_pOutputMesh->m_vecVertices[ct].getPosition().getZ() > regTransformed.getUpperCorner().getZ() - 0.001f);
100  }
101  }
102 
103  template<>
104  POLYVOX_API void MeshDecimator<PositionMaterialNormal>::fillInitialVertexMetadata(std::vector<InitialVertexMetadata>& vecVertexMetadata)
105  {
106  vecVertexMetadata.clear();
107  vecVertexMetadata.resize(m_pOutputMesh->m_vecVertices.size());
108 
109  //Initialise the metadata
110  for(uint32_t ct = 0; ct < vecVertexMetadata.size(); ct++)
111  {
112  vecVertexMetadata[ct].isOnRegionFace.reset();
113  vecVertexMetadata[ct].isOnMaterialEdge = false;
114  vecVertexMetadata[ct].normal = m_pOutputMesh->m_vecVertices[ct].normal;
115  }
116 
117  //Identify those vertices on the edge of a region. Care will need to be taken when moving them.
118  for(uint32_t ct = 0; ct < vecVertexMetadata.size(); ct++)
119  {
120  Region regTransformed = m_pOutputMesh->m_Region;
121  regTransformed.shift(regTransformed.getLowerCorner() * static_cast<int32_t>(-1));
122 
123  //Plus and minus X
124  vecVertexMetadata[ct].isOnRegionFace.set(RFF_ON_REGION_FACE_NEG_X, m_pOutputMesh->m_vecVertices[ct].getPosition().getX() < regTransformed.getLowerCorner().getX() + 0.001f);
125  vecVertexMetadata[ct].isOnRegionFace.set(RFF_ON_REGION_FACE_POS_X, m_pOutputMesh->m_vecVertices[ct].getPosition().getX() > regTransformed.getUpperCorner().getX() - 0.001f);
126  //Plus and minus Y
127  vecVertexMetadata[ct].isOnRegionFace.set(RFF_ON_REGION_FACE_NEG_Y, m_pOutputMesh->m_vecVertices[ct].getPosition().getY() < regTransformed.getLowerCorner().getY() + 0.001f);
128  vecVertexMetadata[ct].isOnRegionFace.set(RFF_ON_REGION_FACE_POS_Y, m_pOutputMesh->m_vecVertices[ct].getPosition().getY() > regTransformed.getUpperCorner().getY() - 0.001f);
129  //Plus and minus Z
130  vecVertexMetadata[ct].isOnRegionFace.set(RFF_ON_REGION_FACE_NEG_Z, m_pOutputMesh->m_vecVertices[ct].getPosition().getZ() < regTransformed.getLowerCorner().getZ() + 0.001f);
131  vecVertexMetadata[ct].isOnRegionFace.set(RFF_ON_REGION_FACE_POS_Z, m_pOutputMesh->m_vecVertices[ct].getPosition().getZ() > regTransformed.getUpperCorner().getZ() - 0.001f);
132  }
133 
134  //If all three vertices have the same material then we are not on a material edge. If any vertex has a different
135  //material then all three vertices are on a material edge. E.g. If one vertex has material 'a' and the other two
136  //have material 'b', then the two 'b's are still on an edge (with 'a') even though they are the same as eachother.
137  for(uint32_t ct = 0; ct < m_vecTriangles.size(); ct++)
138  {
139  uint32_t v0 = m_vecTriangles[ct].v0;
140  uint32_t v1 = m_vecTriangles[ct].v1;
141  uint32_t v2 = m_vecTriangles[ct].v2;
142 
143  bool allMatch =
144  (m_pOutputMesh->m_vecVertices[v0].material - m_pOutputMesh->m_vecVertices[v1].material < 0.001f) &&
145  (m_pOutputMesh->m_vecVertices[v1].material - m_pOutputMesh->m_vecVertices[v2].material < 0.001f);
146 
147  if(!allMatch)
148  {
149  vecVertexMetadata[v0].isOnMaterialEdge = true;
150  vecVertexMetadata[v1].isOnMaterialEdge = true;
151  vecVertexMetadata[v2].isOnMaterialEdge = true;
152  }
153  }
154  }
155 
156  template<>
157  POLYVOX_API bool MeshDecimator<PositionMaterialNormal>::canCollapseNormalEdge(uint32_t uSrc, uint32_t uDst)
158  {
159  if(m_vecInitialVertexMetadata[uSrc].normal.dot(m_vecInitialVertexMetadata[uDst].normal) < m_fMinDotProductForCollapse)
160  {
161  return false;
162  }
163 
164  //With the marching cubes surface we honour the user specified threshold
165  return !collapseChangesFaceNormals(uSrc, uDst, m_fMinDotProductForCollapse);
166  }
167 
168  template<>
169  POLYVOX_API bool MeshDecimator<PositionMaterial>::canCollapseNormalEdge(uint32_t uSrc, uint32_t uDst)
170  {
171  //We don't actually use the normal here, because we want to allow face
172  //vertices to collapse onto edge vertices. Simply checking whether anything
173  //has flipped has proved to be the most robust approach, though rather slow.
174  //It's not sufficient to just check the normals, there can be holes in the middle
175  //of the mesh for example.
176 
177  //User specified threshold is not used for cubic surface, any
178  //movement is too much (but allow for floating point error).
179  return !collapseChangesFaceNormals(uSrc, uDst, 0.999f);
180  }
181 }
Generated by   doxygen 1.8.1