PolyVox  0.2.1
Open source voxel management library
CubicSurfaceExtractor.inl
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 namespace PolyVox
25 {
26  // We try to avoid duplicate vertices by checking whether a vertex has already been added at a given position.
27  // However, it is possible that vertices have the same position but different materials. In this case, the
28  // vertices are not true duplicates and both must be added to the mesh. As far as I can tell, it is possible to have
29  // at most six vertices with the same position but different materials. This worst-case scenario happens when we
30  // have a 2x2x2 group of voxels (all with different materials) and then we delete two voxels from opposing corners.
31  // The vertex position at the center of this group is then going to be used by six quads all with different materials.
32  // One futher note - we can actually have eight quads sharing a vertex position (imagine two 1x1x10 rows of voxels
33  // sharing a common edge) but in this case all eight quads will not have different materials.
34  template<typename VolumeType, typename IsQuadNeeded>
35  const uint32_t CubicSurfaceExtractor<VolumeType, IsQuadNeeded>::MaxVerticesPerPosition = 6;
36 
37  template<typename VolumeType, typename IsQuadNeeded>
38  CubicSurfaceExtractor<VolumeType, IsQuadNeeded>::CubicSurfaceExtractor(VolumeType* volData, Region region, SurfaceMesh<PositionMaterial>* result, bool bMergeQuads, IsQuadNeeded isQuadNeeded)
39  :m_volData(volData)
40  ,m_regSizeInVoxels(region)
41  ,m_meshCurrent(result)
42  ,m_bMergeQuads(bMergeQuads)
43  {
44  m_funcIsQuadNeededCallback = isQuadNeeded;
45  }
46 
47  template<typename VolumeType, typename IsQuadNeeded>
48  void CubicSurfaceExtractor<VolumeType, IsQuadNeeded>::execute()
49  {
50  m_meshCurrent->clear();
51 
52  uint32_t uArrayWidth = m_regSizeInVoxels.getUpperCorner().getX() - m_regSizeInVoxels.getLowerCorner().getX() + 2;
53  uint32_t uArrayHeight = m_regSizeInVoxels.getUpperCorner().getY() - m_regSizeInVoxels.getLowerCorner().getY() + 2;
54 
55  uint32_t arraySize[3]= {uArrayWidth, uArrayHeight, MaxVerticesPerPosition};
56  m_previousSliceVertices.resize(arraySize);
57  m_currentSliceVertices.resize(arraySize);
58  memset(m_previousSliceVertices.getRawData(), 0xff, m_previousSliceVertices.getNoOfElements() * sizeof(IndexAndMaterial));
59  memset(m_currentSliceVertices.getRawData(), 0xff, m_currentSliceVertices.getNoOfElements() * sizeof(IndexAndMaterial));
60 
61  m_vecQuads[NegativeX].resize(m_regSizeInVoxels.getUpperCorner().getX() - m_regSizeInVoxels.getLowerCorner().getX() + 2);
62  m_vecQuads[PositiveX].resize(m_regSizeInVoxels.getUpperCorner().getX() - m_regSizeInVoxels.getLowerCorner().getX() + 2);
63 
64  m_vecQuads[NegativeY].resize(m_regSizeInVoxels.getUpperCorner().getY() - m_regSizeInVoxels.getLowerCorner().getY() + 2);
65  m_vecQuads[PositiveY].resize(m_regSizeInVoxels.getUpperCorner().getY() - m_regSizeInVoxels.getLowerCorner().getY() + 2);
66 
67  m_vecQuads[NegativeZ].resize(m_regSizeInVoxels.getUpperCorner().getZ() - m_regSizeInVoxels.getLowerCorner().getZ() + 2);
68  m_vecQuads[PositiveZ].resize(m_regSizeInVoxels.getUpperCorner().getZ() - m_regSizeInVoxels.getLowerCorner().getZ() + 2);
69 
70  typename VolumeType::Sampler volumeSampler(m_volData);
71 
72  for(int32_t z = m_regSizeInVoxels.getLowerCorner().getZ(); z <= m_regSizeInVoxels.getUpperCorner().getZ(); z++)
73  {
74  uint32_t regZ = z - m_regSizeInVoxels.getLowerCorner().getZ();
75 
76  for(int32_t y = m_regSizeInVoxels.getLowerCorner().getY(); y <= m_regSizeInVoxels.getUpperCorner().getY(); y++)
77  {
78  uint32_t regY = y - m_regSizeInVoxels.getLowerCorner().getY();
79 
80  for(int32_t x = m_regSizeInVoxels.getLowerCorner().getX(); x <= m_regSizeInVoxels.getUpperCorner().getX(); x++)
81  {
82  uint32_t regX = x - m_regSizeInVoxels.getLowerCorner().getX();
83 
84  volumeSampler.setPosition(x,y,z);
85 
86  uint32_t material; //Filled in by callback
87  typename VolumeType::VoxelType currentVoxel = volumeSampler.getVoxel();
88  typename VolumeType::VoxelType negXVoxel = volumeSampler.peekVoxel1nx0py0pz();
89  typename VolumeType::VoxelType negYVoxel = volumeSampler.peekVoxel0px1ny0pz();
90  typename VolumeType::VoxelType negZVoxel = volumeSampler.peekVoxel0px0py1nz();
91 
92  // X
93  if(m_funcIsQuadNeededCallback(currentVoxel, negXVoxel, material))
94  {
95  uint32_t v0 = addVertex(static_cast<float>(regX) - 0.5f, static_cast<float>(regY) - 0.5f, static_cast<float>(regZ) - 0.5f, material, m_previousSliceVertices);
96  uint32_t v1 = addVertex(static_cast<float>(regX) - 0.5f, static_cast<float>(regY) - 0.5f, static_cast<float>(regZ) + 0.5f, material, m_currentSliceVertices);
97  uint32_t v2 = addVertex(static_cast<float>(regX) - 0.5f, static_cast<float>(regY) + 0.5f, static_cast<float>(regZ) + 0.5f, material, m_currentSliceVertices);
98  uint32_t v3 = addVertex(static_cast<float>(regX) - 0.5f, static_cast<float>(regY) + 0.5f, static_cast<float>(regZ) - 0.5f, material, m_previousSliceVertices);
99 
100  m_vecQuads[NegativeX][regX].push_back(Quad(v0, v1, v2, v3));
101  }
102 
103  if(m_funcIsQuadNeededCallback(negXVoxel, currentVoxel, material))
104  {
105  uint32_t v0 = addVertex(static_cast<float>(regX) - 0.5f, static_cast<float>(regY) - 0.5f, static_cast<float>(regZ) - 0.5f, material, m_previousSliceVertices);
106  uint32_t v1 = addVertex(static_cast<float>(regX) - 0.5f, static_cast<float>(regY) - 0.5f, static_cast<float>(regZ) + 0.5f, material, m_currentSliceVertices);
107  uint32_t v2 = addVertex(static_cast<float>(regX) - 0.5f, static_cast<float>(regY) + 0.5f, static_cast<float>(regZ) + 0.5f, material, m_currentSliceVertices);
108  uint32_t v3 = addVertex(static_cast<float>(regX) - 0.5f, static_cast<float>(regY) + 0.5f, static_cast<float>(regZ) - 0.5f, material, m_previousSliceVertices);
109 
110  m_vecQuads[PositiveX][regX].push_back(Quad(v0, v3, v2, v1));
111  }
112 
113  // Y
114  if(m_funcIsQuadNeededCallback(currentVoxel, negYVoxel, material))
115  {
116  uint32_t v0 = addVertex(static_cast<float>(regX) - 0.5f, static_cast<float>(regY) - 0.5f, static_cast<float>(regZ) - 0.5f, material, m_previousSliceVertices);
117  uint32_t v1 = addVertex(static_cast<float>(regX) + 0.5f, static_cast<float>(regY) - 0.5f, static_cast<float>(regZ) - 0.5f, material, m_previousSliceVertices);
118  uint32_t v2 = addVertex(static_cast<float>(regX) + 0.5f, static_cast<float>(regY) - 0.5f, static_cast<float>(regZ) + 0.5f, material, m_currentSliceVertices);
119  uint32_t v3 = addVertex(static_cast<float>(regX) - 0.5f, static_cast<float>(regY) - 0.5f, static_cast<float>(regZ) + 0.5f, material, m_currentSliceVertices);
120 
121  m_vecQuads[NegativeY][regY].push_back(Quad(v0, v1, v2, v3));
122  }
123 
124  if(m_funcIsQuadNeededCallback(negYVoxel, currentVoxel, material))
125  {
126  uint32_t v0 = addVertex(static_cast<float>(regX) - 0.5f, static_cast<float>(regY) - 0.5f, static_cast<float>(regZ) - 0.5f, material, m_previousSliceVertices);
127  uint32_t v1 = addVertex(static_cast<float>(regX) + 0.5f, static_cast<float>(regY) - 0.5f, static_cast<float>(regZ) - 0.5f, material, m_previousSliceVertices);
128  uint32_t v2 = addVertex(static_cast<float>(regX) + 0.5f, static_cast<float>(regY) - 0.5f, static_cast<float>(regZ) + 0.5f, material, m_currentSliceVertices);
129  uint32_t v3 = addVertex(static_cast<float>(regX) - 0.5f, static_cast<float>(regY) - 0.5f, static_cast<float>(regZ) + 0.5f, material, m_currentSliceVertices);
130 
131  m_vecQuads[PositiveY][regY].push_back(Quad(v0, v3, v2, v1));
132  }
133 
134  // Z
135  if(m_funcIsQuadNeededCallback(currentVoxel, negZVoxel, material))
136  {
137  uint32_t v0 = addVertex(static_cast<float>(regX) - 0.5f, static_cast<float>(regY) - 0.5f, static_cast<float>(regZ) - 0.5f, material, m_previousSliceVertices);
138  uint32_t v1 = addVertex(static_cast<float>(regX) - 0.5f, static_cast<float>(regY) + 0.5f, static_cast<float>(regZ) - 0.5f, material, m_previousSliceVertices);
139  uint32_t v2 = addVertex(static_cast<float>(regX) + 0.5f, static_cast<float>(regY) + 0.5f, static_cast<float>(regZ) - 0.5f, material, m_previousSliceVertices);
140  uint32_t v3 = addVertex(static_cast<float>(regX) + 0.5f, static_cast<float>(regY) - 0.5f, static_cast<float>(regZ) - 0.5f, material, m_previousSliceVertices);
141 
142  m_vecQuads[NegativeZ][regZ].push_back(Quad(v0, v1, v2, v3));
143  }
144 
145  if(m_funcIsQuadNeededCallback(negZVoxel, currentVoxel, material))
146  {
147  uint32_t v0 = addVertex(static_cast<float>(regX) - 0.5f, static_cast<float>(regY) - 0.5f, static_cast<float>(regZ) - 0.5f, material, m_previousSliceVertices);
148  uint32_t v1 = addVertex(static_cast<float>(regX) - 0.5f, static_cast<float>(regY) + 0.5f, static_cast<float>(regZ) - 0.5f, material, m_previousSliceVertices);
149  uint32_t v2 = addVertex(static_cast<float>(regX) + 0.5f, static_cast<float>(regY) + 0.5f, static_cast<float>(regZ) - 0.5f, material, m_previousSliceVertices);
150  uint32_t v3 = addVertex(static_cast<float>(regX) + 0.5f, static_cast<float>(regY) - 0.5f, static_cast<float>(regZ) - 0.5f, material, m_previousSliceVertices);
151 
152  m_vecQuads[PositiveZ][regZ].push_back(Quad(v0, v3, v2, v1));
153  }
154  }
155  }
156 
157  m_previousSliceVertices.swap(m_currentSliceVertices);
158  memset(m_currentSliceVertices.getRawData(), 0xff, m_currentSliceVertices.getNoOfElements() * sizeof(IndexAndMaterial));
159  }
160 
161  for(uint32_t uFace = 0; uFace < NoOfFaces; uFace++)
162  {
163  std::vector< std::list<Quad> >& vecListQuads = m_vecQuads[uFace];
164 
165  for(uint32_t slice = 0; slice < vecListQuads.size(); slice++)
166  {
167  std::list<Quad>& listQuads = vecListQuads[slice];
168 
169  if(m_bMergeQuads)
170  {
171  //Repeatedly call this function until it returns
172  //false to indicate nothing more can be done.
173  while(performQuadMerging(listQuads)){}
174  }
175 
176  typename std::list<Quad>::iterator iterEnd = listQuads.end();
177  for(typename std::list<Quad>::iterator quadIter = listQuads.begin(); quadIter != iterEnd; quadIter++)
178  {
179  Quad& quad = *quadIter;
180  m_meshCurrent->addTriangleCubic(quad.vertices[0], quad.vertices[1],quad.vertices[2]);
181  m_meshCurrent->addTriangleCubic(quad.vertices[0], quad.vertices[2],quad.vertices[3]);
182  }
183  }
184  }
185 
186  m_meshCurrent->m_Region = m_regSizeInVoxels;
187  m_meshCurrent->removeUnusedVertices();
188 
189  m_meshCurrent->m_vecLodRecords.clear();
190  LodRecord lodRecord;
191  lodRecord.beginIndex = 0;
192  lodRecord.endIndex = m_meshCurrent->getNoOfIndices();
193  m_meshCurrent->m_vecLodRecords.push_back(lodRecord);
194  }
195 
196  template<typename VolumeType, typename IsQuadNeeded>
197  int32_t CubicSurfaceExtractor<VolumeType, IsQuadNeeded>::addVertex(float fX, float fY, float fZ, uint32_t uMaterialIn, Array<3, IndexAndMaterial>& existingVertices)
198  {
199  uint32_t uX = static_cast<uint32_t>(fX + 0.75f);
200  uint32_t uY = static_cast<uint32_t>(fY + 0.75f);
201 
202  for(uint32_t ct = 0; ct < MaxVerticesPerPosition; ct++)
203  {
204  IndexAndMaterial& rEntry = existingVertices[uX][uY][ct];
205 
206  if(rEntry.iIndex == -1)
207  {
208  //No vertices matched and we've now hit an empty space. Fill it by creating a vertex.
209  rEntry.iIndex = m_meshCurrent->addVertex(PositionMaterial(Vector3DFloat(fX, fY, fZ), uMaterialIn));
210  rEntry.uMaterial = uMaterialIn;
211 
212  return rEntry.iIndex;
213  }
214 
215  //If we have an existing vertex and the material matches then we can return it.
216  if(rEntry.uMaterial == static_cast<int32_t>(uMaterialIn))
217  {
218  return rEntry.iIndex;
219  }
220  }
221 
222  // If we exit the loop here then apparently all the slots were full but none of them matched. I don't think
223  // this can happen so let's put an assert to make sure. If you hit this assert then please report it to us!
224  assert(false);
225  return -1; //Should never happen.
226  }
227 
228  template<typename VolumeType, typename IsQuadNeeded>
229  bool CubicSurfaceExtractor<VolumeType, IsQuadNeeded>::performQuadMerging(std::list<Quad>& quads)
230  {
231  bool bDidMerge = false;
232  for(typename std::list<Quad>::iterator outerIter = quads.begin(); outerIter != quads.end(); outerIter++)
233  {
234  typename std::list<Quad>::iterator innerIter = outerIter;
235  innerIter++;
236  while(innerIter != quads.end())
237  {
238  Quad& q1 = *outerIter;
239  Quad& q2 = *innerIter;
240 
241  bool result = mergeQuads(q1,q2);
242 
243  if(result)
244  {
245  bDidMerge = true;
246  innerIter = quads.erase(innerIter);
247  }
248  else
249  {
250  innerIter++;
251  }
252  }
253  }
254 
255  return bDidMerge;
256  }
257 
258  template<typename VolumeType, typename IsQuadNeeded>
259  bool CubicSurfaceExtractor<VolumeType, IsQuadNeeded>::mergeQuads(Quad& q1, Quad& q2)
260  {
261  //All four vertices of a given quad have the same material,
262  //so just check that the first pair of vertices match.
263  if(std::abs(m_meshCurrent->getVertices()[q1.vertices[0]].getMaterial() - m_meshCurrent->getVertices()[q2.vertices[0]].getMaterial()) < 0.001)
264  {
265  //Now check whether quad 2 is adjacent to quad one by comparing vertices.
266  //Adjacent quads must share two vertices, and the second quad could be to the
267  //top, bottom, left, of right of the first one. This gives four combinations to test.
268  if((q1.vertices[0] == q2.vertices[1]) && ((q1.vertices[3] == q2.vertices[2])))
269  {
270  q1.vertices[0] = q2.vertices[0];
271  q1.vertices[3] = q2.vertices[3];
272  return true;
273  }
274  else if((q1.vertices[3] == q2.vertices[0]) && ((q1.vertices[2] == q2.vertices[1])))
275  {
276  q1.vertices[3] = q2.vertices[3];
277  q1.vertices[2] = q2.vertices[2];
278  return true;
279  }
280  else if((q1.vertices[1] == q2.vertices[0]) && ((q1.vertices[2] == q2.vertices[3])))
281  {
282  q1.vertices[1] = q2.vertices[1];
283  q1.vertices[2] = q2.vertices[2];
284  return true;
285  }
286  else if((q1.vertices[0] == q2.vertices[3]) && ((q1.vertices[1] == q2.vertices[2])))
287  {
288  q1.vertices[0] = q2.vertices[0];
289  q1.vertices[1] = q2.vertices[1];
290  return true;
291  }
292  }
293 
294  //Quads cannot be merged.
295  return false;
296  }
297 }
Generated by   doxygen 1.8.1