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 {
00026 template< template<typename> class VolumeType, typename VoxelType>
00027 const uint32_t CubicSurfaceExtractor<VolumeType, VoxelType>::MaxQuadsSharingVertex = 4;
00028
00029 template< template<typename> class VolumeType, typename VoxelType>
00030 CubicSurfaceExtractor<VolumeType, VoxelType>::CubicSurfaceExtractor(VolumeType<VoxelType>* volData, Region region, SurfaceMesh<PositionMaterial>* result, bool bMergeQuads)
00031 :m_volData(volData)
00032 ,m_regSizeInVoxels(region)
00033 ,m_meshCurrent(result)
00034 ,m_bMergeQuads(bMergeQuads)
00035 {
00036 }
00037
00038 template< template<typename> class VolumeType, typename VoxelType>
00039 void CubicSurfaceExtractor<VolumeType, VoxelType>::execute()
00040 {
00041 m_meshCurrent->clear();
00042
00043 uint32_t uArrayWidth = m_regSizeInVoxels.getUpperCorner().getX() - m_regSizeInVoxels.getLowerCorner().getX() + 2;
00044 uint32_t uArrayHeight = m_regSizeInVoxels.getUpperCorner().getY() - m_regSizeInVoxels.getLowerCorner().getY() + 2;
00045
00046 uint32_t arraySize[3]= {uArrayWidth, uArrayHeight, MaxQuadsSharingVertex};
00047 m_previousSliceVertices.resize(arraySize);
00048 m_currentSliceVertices.resize(arraySize);
00049 memset(m_previousSliceVertices.getRawData(), 0xff, m_previousSliceVertices.getNoOfElements() * sizeof(IndexAndMaterial));
00050 memset(m_currentSliceVertices.getRawData(), 0xff, m_currentSliceVertices.getNoOfElements() * sizeof(IndexAndMaterial));
00051
00052 uint32_t uRegionWidth = m_regSizeInVoxels.getUpperCorner().getX() - m_regSizeInVoxels.getLowerCorner().getX() + 1;
00053 uint32_t uRegionHeight = m_regSizeInVoxels.getUpperCorner().getY() - m_regSizeInVoxels.getLowerCorner().getY() + 1;
00054 uint32_t uRegionDepth = m_regSizeInVoxels.getUpperCorner().getZ() - m_regSizeInVoxels.getLowerCorner().getZ() + 1;
00055
00056 m_vecQuads[NegativeX].resize(m_regSizeInVoxels.getUpperCorner().getX() - m_regSizeInVoxels.getLowerCorner().getX() + 2);
00057 m_vecQuads[PositiveX].resize(m_regSizeInVoxels.getUpperCorner().getX() - m_regSizeInVoxels.getLowerCorner().getX() + 2);
00058
00059 m_vecQuads[NegativeY].resize(m_regSizeInVoxels.getUpperCorner().getY() - m_regSizeInVoxels.getLowerCorner().getY() + 2);
00060 m_vecQuads[PositiveY].resize(m_regSizeInVoxels.getUpperCorner().getY() - m_regSizeInVoxels.getLowerCorner().getY() + 2);
00061
00062 m_vecQuads[NegativeZ].resize(m_regSizeInVoxels.getUpperCorner().getZ() - m_regSizeInVoxels.getLowerCorner().getZ() + 2);
00063 m_vecQuads[PositiveZ].resize(m_regSizeInVoxels.getUpperCorner().getZ() - m_regSizeInVoxels.getLowerCorner().getZ() + 2);
00064
00065 typename VolumeType<VoxelType>::Sampler volumeSampler(m_volData);
00066 Quad quad;
00067
00068 for(int32_t z = m_regSizeInVoxels.getLowerCorner().getZ(); z <= m_regSizeInVoxels.getUpperCorner().getZ() + 1; z++)
00069 {
00070 uint32_t regZ = z - m_regSizeInVoxels.getLowerCorner().getZ();
00071 bool finalZ = (z == m_regSizeInVoxels.getUpperCorner().getZ() + 1);
00072
00073 for(int32_t y = m_regSizeInVoxels.getLowerCorner().getY(); y <= m_regSizeInVoxels.getUpperCorner().getY() + 1; y++)
00074 {
00075 uint32_t regY = y - m_regSizeInVoxels.getLowerCorner().getY();
00076 bool finalY = (y == m_regSizeInVoxels.getUpperCorner().getY() + 1);
00077
00078 for(int32_t x = m_regSizeInVoxels.getLowerCorner().getX(); x <= m_regSizeInVoxels.getUpperCorner().getX() + 1; x++)
00079 {
00080 uint32_t regX = x - m_regSizeInVoxels.getLowerCorner().getX();
00081 bool finalX = (x == m_regSizeInVoxels.getUpperCorner().getX() + 1);
00082
00083 volumeSampler.setPosition(x,y,z);
00084
00085 VoxelType currentVoxel = volumeSampler.getVoxel();
00086 bool currentVoxelIsSolid = currentVoxel.getDensity() >= VoxelType::getThreshold();
00087
00088 VoxelType negXVoxel = volumeSampler.peekVoxel1nx0py0pz();
00089 bool negXVoxelIsSolid = negXVoxel.getDensity() >= VoxelType::getThreshold();
00090
00091 if((currentVoxelIsSolid != negXVoxelIsSolid) && (finalY == false) && (finalZ == false))
00092 {
00093 uint32_t material = (std::max)(currentVoxel.getMaterial(), negXVoxel.getMaterial());
00094
00095
00096 if(((currentVoxelIsSolid > negXVoxelIsSolid) && finalX == false) || ((currentVoxelIsSolid < negXVoxelIsSolid) && regX != 0))
00097 {
00098 uint32_t v0 = addVertex(regX - 0.5f, regY - 0.5f, regZ - 0.5f, material, m_previousSliceVertices);
00099 uint32_t v1 = addVertex(regX - 0.5f, regY - 0.5f, regZ + 0.5f, material, m_currentSliceVertices);
00100 uint32_t v2 = addVertex(regX - 0.5f, regY + 0.5f, regZ + 0.5f, material, m_currentSliceVertices);
00101 uint32_t v3 = addVertex(regX - 0.5f, regY + 0.5f, regZ - 0.5f, material, m_previousSliceVertices);
00102
00103 if(currentVoxelIsSolid > negXVoxelIsSolid)
00104 {
00105 quad.vertices[0] = v0;
00106 quad.vertices[1] = v1;
00107 quad.vertices[2] = v2;
00108 quad.vertices[3] = v3;
00109
00110 m_vecQuads[NegativeX][regX].push_back(quad);
00111 }
00112 else
00113 {
00114 quad.vertices[0] = v0;
00115 quad.vertices[1] = v3;
00116 quad.vertices[2] = v2;
00117 quad.vertices[3] = v1;
00118
00119 m_vecQuads[PositiveX][regX].push_back(quad);
00120 }
00121
00122 }
00123 }
00124
00125 VoxelType negYVoxel = volumeSampler.peekVoxel0px1ny0pz();
00126 bool negYVoxelIsSolid = negYVoxel.getDensity() >= VoxelType::getThreshold();
00127
00128 if((currentVoxelIsSolid != negYVoxelIsSolid) && (finalX == false) && (finalZ == false))
00129 {
00130 int material = (std::max)(currentVoxel.getMaterial(),negYVoxel.getMaterial());
00131
00132 if(((currentVoxelIsSolid > negYVoxelIsSolid) && finalY == false) || ((currentVoxelIsSolid < negYVoxelIsSolid) && regY != 0))
00133 {
00134 uint32_t v0 = addVertex(regX - 0.5f, regY - 0.5f, regZ - 0.5f, material, m_previousSliceVertices);
00135 uint32_t v1 = addVertex(regX - 0.5f, regY - 0.5f, regZ + 0.5f, material, m_currentSliceVertices);
00136 uint32_t v2 = addVertex(regX + 0.5f, regY - 0.5f, regZ + 0.5f, material, m_currentSliceVertices);
00137 uint32_t v3 = addVertex(regX + 0.5f, regY - 0.5f, regZ - 0.5f, material, m_previousSliceVertices);
00138
00139 if(currentVoxelIsSolid > negYVoxelIsSolid)
00140 {
00141
00142 quad.vertices[0] = v0;
00143 quad.vertices[1] = v3;
00144 quad.vertices[2] = v2;
00145 quad.vertices[3] = v1;
00146
00147 m_vecQuads[NegativeY][regY].push_back(quad);
00148 }
00149 else
00150 {
00151
00152 quad.vertices[0] = v0;
00153 quad.vertices[1] = v1;
00154 quad.vertices[2] = v2;
00155 quad.vertices[3] = v3;
00156
00157 m_vecQuads[PositiveY][regY].push_back(quad);
00158 }
00159 }
00160 }
00161
00162 VoxelType negZVoxel = volumeSampler.peekVoxel0px0py1nz();
00163 bool negZVoxelIsSolid = negZVoxel.getDensity() >= VoxelType::getThreshold();
00164
00165 if((currentVoxelIsSolid != negZVoxelIsSolid) && (finalX == false) && (finalY == false))
00166 {
00167 int material = (std::max)(currentVoxel.getMaterial(), negZVoxel.getMaterial());
00168
00169 if(((currentVoxelIsSolid > negZVoxelIsSolid) && finalZ == false) || ((currentVoxelIsSolid < negZVoxelIsSolid) && regZ != 0))
00170 {
00171 uint32_t v0 = addVertex(regX - 0.5f, regY - 0.5f, regZ - 0.5f, material, m_previousSliceVertices);
00172 uint32_t v1 = addVertex(regX - 0.5f, regY + 0.5f, regZ - 0.5f, material, m_previousSliceVertices);
00173 uint32_t v2 = addVertex(regX + 0.5f, regY + 0.5f, regZ - 0.5f, material, m_previousSliceVertices);
00174 uint32_t v3 = addVertex(regX + 0.5f, regY - 0.5f, regZ - 0.5f, material, m_previousSliceVertices);
00175
00176 if(currentVoxelIsSolid > negZVoxelIsSolid)
00177 {
00178 quad.vertices[0] = v0;
00179 quad.vertices[1] = v1;
00180 quad.vertices[2] = v2;
00181 quad.vertices[3] = v3;
00182
00183 m_vecQuads[NegativeZ][regZ].push_back(quad);
00184 }
00185 else
00186 {
00187 quad.vertices[0] = v0;
00188 quad.vertices[1] = v3;
00189 quad.vertices[2] = v2;
00190 quad.vertices[3] = v1;
00191
00192 m_vecQuads[PositiveZ][regZ].push_back(quad);
00193 }
00194 }
00195 }
00196 }
00197 }
00198
00199 m_previousSliceVertices.swap(m_currentSliceVertices);
00200 memset(m_currentSliceVertices.getRawData(), 0xff, m_currentSliceVertices.getNoOfElements() * sizeof(IndexAndMaterial));
00201 }
00202
00203 for(uint32_t uFace = 0; uFace < NoOfFaces; uFace++)
00204 {
00205 std::vector< std::list<Quad> >& vecListQuads = m_vecQuads[uFace];
00206
00207 for(uint32_t slice = 0; slice < vecListQuads.size(); slice++)
00208 {
00209 std::list<Quad>& listQuads = vecListQuads[slice];
00210
00211 if(m_bMergeQuads)
00212 {
00213
00214
00215 while(performQuadMerging(listQuads)){}
00216 }
00217
00218 typename std::list<Quad>::iterator iterEnd = listQuads.end();
00219 for(typename std::list<Quad>::iterator quadIter = listQuads.begin(); quadIter != iterEnd; quadIter++)
00220 {
00221 Quad& quad = *quadIter;
00222 m_meshCurrent->addTriangleCubic(quad.vertices[0], quad.vertices[1],quad.vertices[2]);
00223 m_meshCurrent->addTriangleCubic(quad.vertices[0], quad.vertices[2],quad.vertices[3]);
00224 }
00225 }
00226 }
00227
00228 m_meshCurrent->m_Region = m_regSizeInVoxels;
00229 m_meshCurrent->removeUnusedVertices();
00230
00231 m_meshCurrent->m_vecLodRecords.clear();
00232 LodRecord lodRecord;
00233 lodRecord.beginIndex = 0;
00234 lodRecord.endIndex = m_meshCurrent->getNoOfIndices();
00235 m_meshCurrent->m_vecLodRecords.push_back(lodRecord);
00236 }
00237
00238 template< template<typename> class VolumeType, typename VoxelType>
00239 int32_t CubicSurfaceExtractor<VolumeType, VoxelType>::addVertex(float fX, float fY, float fZ, uint32_t uMaterialIn, Array<3, IndexAndMaterial>& existingVertices)
00240 {
00241 uint32_t uX = static_cast<uint32_t>(fX + 0.75f);
00242 uint32_t uY = static_cast<uint32_t>(fY + 0.75f);
00243
00244 for(uint32_t ct = 0; ct < MaxQuadsSharingVertex; ct++)
00245 {
00246 IndexAndMaterial& rEntry = existingVertices[uX][uY][ct];
00247
00248 if(rEntry.iIndex == -1)
00249 {
00250
00251 rEntry.iIndex = m_meshCurrent->addVertex(PositionMaterial(Vector3DFloat(fX, fY, fZ), uMaterialIn));
00252 rEntry.uMaterial = uMaterialIn;
00253
00254 return rEntry.iIndex;
00255 }
00256
00257
00258 if(rEntry.uMaterial == uMaterialIn)
00259 {
00260 return rEntry.iIndex;
00261 }
00262 }
00263
00264
00265
00266 assert(false);
00267 return 0;
00268 }
00269
00270 template< template<typename> class VolumeType, typename VoxelType>
00271 bool CubicSurfaceExtractor<VolumeType, VoxelType>::performQuadMerging(std::list<Quad>& quads)
00272 {
00273 bool bDidMerge = false;
00274 for(typename std::list<Quad>::iterator outerIter = quads.begin(); outerIter != quads.end(); outerIter++)
00275 {
00276 typename std::list<Quad>::iterator innerIter = outerIter;
00277 innerIter++;
00278 while(innerIter != quads.end())
00279 {
00280 Quad& q1 = *outerIter;
00281 Quad& q2 = *innerIter;
00282
00283 bool result = mergeQuads(q1,q2);
00284
00285 if(result)
00286 {
00287 bDidMerge = true;
00288 innerIter = quads.erase(innerIter);
00289 }
00290 else
00291 {
00292 innerIter++;
00293 }
00294 }
00295 }
00296
00297 return bDidMerge;
00298 }
00299
00300 template< template<typename> class VolumeType, typename VoxelType>
00301 bool CubicSurfaceExtractor<VolumeType, VoxelType>::mergeQuads(Quad& q1, Quad& q2)
00302 {
00303
00304
00305 if(fabs(m_meshCurrent->getVertices()[q1.vertices[0]].getMaterial() - m_meshCurrent->getVertices()[q2.vertices[0]].getMaterial()) < 0.001)
00306 {
00307
00308
00309
00310 if((q1.vertices[0] == q2.vertices[1]) && ((q1.vertices[3] == q2.vertices[2])))
00311 {
00312 q1.vertices[0] = q2.vertices[0];
00313 q1.vertices[3] = q2.vertices[3];
00314 return true;
00315 }
00316 else if((q1.vertices[3] == q2.vertices[0]) && ((q1.vertices[2] == q2.vertices[1])))
00317 {
00318 q1.vertices[3] = q2.vertices[3];
00319 q1.vertices[2] = q2.vertices[2];
00320 return true;
00321 }
00322 else if((q1.vertices[1] == q2.vertices[0]) && ((q1.vertices[2] == q2.vertices[3])))
00323 {
00324 q1.vertices[1] = q2.vertices[1];
00325 q1.vertices[2] = q2.vertices[2];
00326 return true;
00327 }
00328 else if((q1.vertices[0] == q2.vertices[3]) && ((q1.vertices[1] == q2.vertices[2])))
00329 {
00330 q1.vertices[0] = q2.vertices[0];
00331 q1.vertices[1] = q2.vertices[1];
00332 return true;
00333 }
00334 }
00335
00336
00337 return false;
00338 }
00339 }