vrshoot

annotate libs/assimp/Subdivision.cpp @ 0:b2f14e535253

find changesets by author, revision, files, or words in the commit message
initial commit
author John Tsiombikas <nuclear@member.fsf.org>
date Sat, 01 Feb 2014 19:58:19 +0200
parents
children
rev   line source
nuclear@0 1 /*
nuclear@0 2 Open Asset Import Library (assimp)
nuclear@0 3 ----------------------------------------------------------------------
nuclear@0 4
nuclear@0 5 Copyright (c) 2006-2012, assimp team
nuclear@0 6 All rights reserved.
nuclear@0 7
nuclear@0 8 Redistribution and use of this software in source and binary forms,
nuclear@0 9 with or without modification, are permitted provided that the
nuclear@0 10 following conditions are met:
nuclear@0 11
nuclear@0 12 * Redistributions of source code must retain the above
nuclear@0 13 copyright notice, this list of conditions and the
nuclear@0 14 following disclaimer.
nuclear@0 15
nuclear@0 16 * Redistributions in binary form must reproduce the above
nuclear@0 17 copyright notice, this list of conditions and the
nuclear@0 18 following disclaimer in the documentation and/or other
nuclear@0 19 materials provided with the distribution.
nuclear@0 20
nuclear@0 21 * Neither the name of the assimp team, nor the names of its
nuclear@0 22 contributors may be used to endorse or promote products
nuclear@0 23 derived from this software without specific prior
nuclear@0 24 written permission of the assimp team.
nuclear@0 25
nuclear@0 26 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
nuclear@0 27 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
nuclear@0 28 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
nuclear@0 29 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
nuclear@0 30 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
nuclear@0 31 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
nuclear@0 32 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
nuclear@0 33 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
nuclear@0 34 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
nuclear@0 35 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
nuclear@0 36 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
nuclear@0 37
nuclear@0 38 ----------------------------------------------------------------------
nuclear@0 39 */
nuclear@0 40
nuclear@0 41 #include "AssimpPCH.h"
nuclear@0 42
nuclear@0 43 #include "Subdivision.h"
nuclear@0 44 #include "SceneCombiner.h"
nuclear@0 45 #include "SpatialSort.h"
nuclear@0 46 #include "ProcessHelper.h"
nuclear@0 47 #include "Vertex.h"
nuclear@0 48
nuclear@0 49 using namespace Assimp;
nuclear@0 50 void mydummy() {}
nuclear@0 51
nuclear@0 52 // ------------------------------------------------------------------------------------------------
nuclear@0 53 /** Subdivider stub class to implement the Catmull-Clarke subdivision algorithm. The
nuclear@0 54 * implementation is basing on recursive refinement. Directly evaluating the result is also
nuclear@0 55 * possible and much quicker, but it depends on lengthy matrix lookup tables. */
nuclear@0 56 // ------------------------------------------------------------------------------------------------
nuclear@0 57 class CatmullClarkSubdivider : public Subdivider
nuclear@0 58 {
nuclear@0 59
nuclear@0 60 public:
nuclear@0 61
nuclear@0 62 void Subdivide (aiMesh* mesh, aiMesh*& out, unsigned int num, bool discard_input);
nuclear@0 63 void Subdivide (aiMesh** smesh, size_t nmesh,
nuclear@0 64 aiMesh** out, unsigned int num, bool discard_input);
nuclear@0 65
nuclear@0 66 // ---------------------------------------------------------------------------
nuclear@0 67 /** Intermediate description of an edge between two corners of a polygon*/
nuclear@0 68 // ---------------------------------------------------------------------------
nuclear@0 69 struct Edge
nuclear@0 70 {
nuclear@0 71 Edge()
nuclear@0 72 : ref(0)
nuclear@0 73 {}
nuclear@0 74 Vertex edge_point, midpoint;
nuclear@0 75 unsigned int ref;
nuclear@0 76 };
nuclear@0 77
nuclear@0 78
nuclear@0 79
nuclear@0 80 typedef std::vector<unsigned int> UIntVector;
nuclear@0 81 typedef std::map<uint64_t,Edge> EdgeMap;
nuclear@0 82
nuclear@0 83 // ---------------------------------------------------------------------------
nuclear@0 84 // Hashing function to derive an index into an #EdgeMap from two given
nuclear@0 85 // 'unsigned int' vertex coordinates (!!distinct coordinates - same
nuclear@0 86 // vertex position == same index!!).
nuclear@0 87 // NOTE - this leads to rare hash collisions if a) sizeof(unsigned int)>4
nuclear@0 88 // and (id[0]>2^32-1 or id[0]>2^32-1).
nuclear@0 89 // MAKE_EDGE_HASH() uses temporaries, so INIT_EDGE_HASH() needs to be put
nuclear@0 90 // at the head of every function which is about to use MAKE_EDGE_HASH().
nuclear@0 91 // Reason is that the hash is that hash construction needs to hold the
nuclear@0 92 // invariant id0<id1 to identify an edge - else two hashes would refer
nuclear@0 93 // to the same edge.
nuclear@0 94 // ---------------------------------------------------------------------------
nuclear@0 95 #define MAKE_EDGE_HASH(id0,id1) (eh_tmp0__=id0,eh_tmp1__=id1,\
nuclear@0 96 (eh_tmp0__<eh_tmp1__?std::swap(eh_tmp0__,eh_tmp1__):mydummy()),(uint64_t)eh_tmp0__^((uint64_t)eh_tmp1__<<32u))
nuclear@0 97
nuclear@0 98
nuclear@0 99 #define INIT_EDGE_HASH_TEMPORARIES()\
nuclear@0 100 unsigned int eh_tmp0__, eh_tmp1__;
nuclear@0 101
nuclear@0 102 private:
nuclear@0 103
nuclear@0 104 void InternSubdivide (const aiMesh* const * smesh,
nuclear@0 105 size_t nmesh,aiMesh** out, unsigned int num);
nuclear@0 106 };
nuclear@0 107
nuclear@0 108
nuclear@0 109 // ------------------------------------------------------------------------------------------------
nuclear@0 110 // Construct a subdivider of a specific type
nuclear@0 111 Subdivider* Subdivider::Create (Algorithm algo)
nuclear@0 112 {
nuclear@0 113 switch (algo)
nuclear@0 114 {
nuclear@0 115 case CATMULL_CLARKE:
nuclear@0 116 return new CatmullClarkSubdivider();
nuclear@0 117 };
nuclear@0 118
nuclear@0 119 ai_assert(false);
nuclear@0 120 return NULL; // shouldn't happen
nuclear@0 121 }
nuclear@0 122
nuclear@0 123 // ------------------------------------------------------------------------------------------------
nuclear@0 124 // Call the Catmull Clark subdivision algorithm for one mesh
nuclear@0 125 void CatmullClarkSubdivider::Subdivide (
nuclear@0 126 aiMesh* mesh,
nuclear@0 127 aiMesh*& out,
nuclear@0 128 unsigned int num,
nuclear@0 129 bool discard_input
nuclear@0 130 )
nuclear@0 131 {
nuclear@0 132 assert(mesh != out);
nuclear@0 133 Subdivide(&mesh,1,&out,num,discard_input);
nuclear@0 134 }
nuclear@0 135
nuclear@0 136 // ------------------------------------------------------------------------------------------------
nuclear@0 137 // Call the Catmull Clark subdivision algorithm for multiple meshes
nuclear@0 138 void CatmullClarkSubdivider::Subdivide (
nuclear@0 139 aiMesh** smesh,
nuclear@0 140 size_t nmesh,
nuclear@0 141 aiMesh** out,
nuclear@0 142 unsigned int num,
nuclear@0 143 bool discard_input
nuclear@0 144 )
nuclear@0 145 {
nuclear@0 146 ai_assert(NULL != smesh && NULL != out);
nuclear@0 147
nuclear@0 148 // course, both regions may not overlap
nuclear@0 149 assert(smesh<out || smesh+nmesh>out+nmesh);
nuclear@0 150 if (!num) {
nuclear@0 151
nuclear@0 152 // No subdivision at all. Need to copy all the meshes .. argh.
nuclear@0 153 if (discard_input) {
nuclear@0 154 for (size_t s = 0; s < nmesh; ++s) {
nuclear@0 155 out[s] = smesh[s];
nuclear@0 156 smesh[s] = NULL;
nuclear@0 157 }
nuclear@0 158 }
nuclear@0 159 else {
nuclear@0 160 for (size_t s = 0; s < nmesh; ++s) {
nuclear@0 161 SceneCombiner::Copy(out+s,smesh[s]);
nuclear@0 162 }
nuclear@0 163 }
nuclear@0 164 return;
nuclear@0 165 }
nuclear@0 166
nuclear@0 167 std::vector<aiMesh*> inmeshes;
nuclear@0 168 std::vector<aiMesh*> outmeshes;
nuclear@0 169 std::vector<unsigned int> maptbl;
nuclear@0 170
nuclear@0 171 inmeshes.reserve(nmesh);
nuclear@0 172 outmeshes.reserve(nmesh);
nuclear@0 173 maptbl.reserve(nmesh);
nuclear@0 174
nuclear@0 175 // Remove pure line and point meshes from the working set to reduce the
nuclear@0 176 // number of edge cases the subdivider is forced to deal with. Line and
nuclear@0 177 // point meshes are simply passed through.
nuclear@0 178 for (size_t s = 0; s < nmesh; ++s) {
nuclear@0 179 aiMesh* i = smesh[s];
nuclear@0 180 // FIX - mPrimitiveTypes might not yet be initialized
nuclear@0 181 if (i->mPrimitiveTypes && (i->mPrimitiveTypes & (aiPrimitiveType_LINE|aiPrimitiveType_POINT))==i->mPrimitiveTypes) {
nuclear@0 182 DefaultLogger::get()->debug("Catmull-Clark Subdivider: Skipping pure line/point mesh");
nuclear@0 183
nuclear@0 184 if (discard_input) {
nuclear@0 185 out[s] = i;
nuclear@0 186 smesh[s] = NULL;
nuclear@0 187 }
nuclear@0 188 else {
nuclear@0 189 SceneCombiner::Copy(out+s,i);
nuclear@0 190 }
nuclear@0 191 continue;
nuclear@0 192 }
nuclear@0 193
nuclear@0 194 outmeshes.push_back(NULL);inmeshes.push_back(i);
nuclear@0 195 maptbl.push_back(s);
nuclear@0 196 }
nuclear@0 197
nuclear@0 198 // Do the actual subdivision on the preallocated storage. InternSubdivide
nuclear@0 199 // *always* assumes that enough storage is available, it does not bother
nuclear@0 200 // checking any ranges.
nuclear@0 201 ai_assert(inmeshes.size()==outmeshes.size()&&inmeshes.size()==maptbl.size());
nuclear@0 202 if (inmeshes.empty()) {
nuclear@0 203 DefaultLogger::get()->warn("Catmull-Clark Subdivider: Pure point/line scene, I can't do anything");
nuclear@0 204 return;
nuclear@0 205 }
nuclear@0 206 InternSubdivide(&inmeshes.front(),inmeshes.size(),&outmeshes.front(),num);
nuclear@0 207 for (unsigned int i = 0; i < maptbl.size(); ++i) {
nuclear@0 208 ai_assert(outmeshes[i]);
nuclear@0 209 out[maptbl[i]] = outmeshes[i];
nuclear@0 210 }
nuclear@0 211
nuclear@0 212 if (discard_input) {
nuclear@0 213 for (size_t s = 0; s < nmesh; ++s) {
nuclear@0 214 delete smesh[s];
nuclear@0 215 }
nuclear@0 216 }
nuclear@0 217 }
nuclear@0 218
nuclear@0 219 // ------------------------------------------------------------------------------------------------
nuclear@0 220 // Note - this is an implementation of the standard (recursive) Cm-Cl algorithm without further
nuclear@0 221 // optimizations (except we're using some nice LUTs). A description of the algorithm can be found
nuclear@0 222 // here: http://en.wikipedia.org/wiki/Catmull-Clark_subdivision_surface
nuclear@0 223 //
nuclear@0 224 // The code is mostly O(n), however parts are O(nlogn) which is therefore the algorithm's
nuclear@0 225 // expected total runtime complexity. The implementation is able to work in-place on the same
nuclear@0 226 // mesh arrays. Calling #InternSubdivide() directly is not encouraged. The code can operate
nuclear@0 227 // in-place unless 'smesh' and 'out' are equal (no strange overlaps or reorderings).
nuclear@0 228 // Previous data is replaced/deleted then.
nuclear@0 229 // ------------------------------------------------------------------------------------------------
nuclear@0 230 void CatmullClarkSubdivider::InternSubdivide (
nuclear@0 231 const aiMesh* const * smesh,
nuclear@0 232 size_t nmesh,
nuclear@0 233 aiMesh** out,
nuclear@0 234 unsigned int num
nuclear@0 235 )
nuclear@0 236 {
nuclear@0 237 ai_assert(NULL != smesh && NULL != out);
nuclear@0 238 INIT_EDGE_HASH_TEMPORARIES();
nuclear@0 239
nuclear@0 240 // no subdivision requested or end of recursive refinement
nuclear@0 241 if (!num) {
nuclear@0 242 return;
nuclear@0 243 }
nuclear@0 244
nuclear@0 245 UIntVector maptbl;
nuclear@0 246 SpatialSort spatial;
nuclear@0 247
nuclear@0 248 // ---------------------------------------------------------------------
nuclear@0 249 // 0. Offset table to index all meshes continuously, generate a spatially
nuclear@0 250 // sorted representation of all vertices in all meshes.
nuclear@0 251 // ---------------------------------------------------------------------
nuclear@0 252 typedef std::pair<unsigned int,unsigned int> IntPair;
nuclear@0 253 std::vector<IntPair> moffsets(nmesh);
nuclear@0 254 unsigned int totfaces = 0, totvert = 0;
nuclear@0 255 for (size_t t = 0; t < nmesh; ++t) {
nuclear@0 256 const aiMesh* mesh = smesh[t];
nuclear@0 257
nuclear@0 258 spatial.Append(mesh->mVertices,mesh->mNumVertices,sizeof(aiVector3D),false);
nuclear@0 259 moffsets[t] = IntPair(totfaces,totvert);
nuclear@0 260
nuclear@0 261 totfaces += mesh->mNumFaces;
nuclear@0 262 totvert += mesh->mNumVertices;
nuclear@0 263 }
nuclear@0 264
nuclear@0 265 spatial.Finalize();
nuclear@0 266 const unsigned int num_unique = spatial.GenerateMappingTable(maptbl,ComputePositionEpsilon(smesh,nmesh));
nuclear@0 267
nuclear@0 268
nuclear@0 269 #define FLATTEN_VERTEX_IDX(mesh_idx, vert_idx) (moffsets[mesh_idx].second+vert_idx)
nuclear@0 270 #define FLATTEN_FACE_IDX(mesh_idx, face_idx) (moffsets[mesh_idx].first+face_idx)
nuclear@0 271
nuclear@0 272 // ---------------------------------------------------------------------
nuclear@0 273 // 1. Compute the centroid point for all faces
nuclear@0 274 // ---------------------------------------------------------------------
nuclear@0 275 std::vector<Vertex> centroids(totfaces);
nuclear@0 276 unsigned int nfacesout = 0;
nuclear@0 277 for (size_t t = 0, n = 0; t < nmesh; ++t) {
nuclear@0 278 const aiMesh* mesh = smesh[t];
nuclear@0 279 for (unsigned int i = 0; i < mesh->mNumFaces;++i,++n)
nuclear@0 280 {
nuclear@0 281 const aiFace& face = mesh->mFaces[i];
nuclear@0 282 Vertex& c = centroids[n];
nuclear@0 283
nuclear@0 284 for (unsigned int a = 0; a < face.mNumIndices;++a) {
nuclear@0 285 c += Vertex(mesh,face.mIndices[a]);
nuclear@0 286 }
nuclear@0 287
nuclear@0 288 c /= static_cast<float>(face.mNumIndices);
nuclear@0 289 nfacesout += face.mNumIndices;
nuclear@0 290 }
nuclear@0 291 }
nuclear@0 292
nuclear@0 293 EdgeMap edges;
nuclear@0 294
nuclear@0 295 // ---------------------------------------------------------------------
nuclear@0 296 // 2. Set each edge point to be the average of all neighbouring
nuclear@0 297 // face points and original points. Every edge exists twice
nuclear@0 298 // if there is a neighboring face.
nuclear@0 299 // ---------------------------------------------------------------------
nuclear@0 300 for (size_t t = 0; t < nmesh; ++t) {
nuclear@0 301 const aiMesh* mesh = smesh[t];
nuclear@0 302
nuclear@0 303 for (unsigned int i = 0; i < mesh->mNumFaces;++i) {
nuclear@0 304 const aiFace& face = mesh->mFaces[i];
nuclear@0 305
nuclear@0 306 for (unsigned int p =0; p< face.mNumIndices; ++p) {
nuclear@0 307 const unsigned int id[] = {
nuclear@0 308 face.mIndices[p],
nuclear@0 309 face.mIndices[p==face.mNumIndices-1?0:p+1]
nuclear@0 310 };
nuclear@0 311 const unsigned int mp[] = {
nuclear@0 312 maptbl[FLATTEN_VERTEX_IDX(t,id[0])],
nuclear@0 313 maptbl[FLATTEN_VERTEX_IDX(t,id[1])]
nuclear@0 314 };
nuclear@0 315
nuclear@0 316 Edge& e = edges[MAKE_EDGE_HASH(mp[0],mp[1])];
nuclear@0 317 e.ref++;
nuclear@0 318 if (e.ref<=2) {
nuclear@0 319 if (e.ref==1) { // original points (end points) - add only once
nuclear@0 320 e.edge_point = e.midpoint = Vertex(mesh,id[0])+Vertex(mesh,id[1]);
nuclear@0 321 e.midpoint *= 0.5f;
nuclear@0 322 }
nuclear@0 323 e.edge_point += centroids[FLATTEN_FACE_IDX(t,i)];
nuclear@0 324 }
nuclear@0 325 }
nuclear@0 326 }
nuclear@0 327 }
nuclear@0 328
nuclear@0 329 // ---------------------------------------------------------------------
nuclear@0 330 // 3. Normalize edge points
nuclear@0 331 // ---------------------------------------------------------------------
nuclear@0 332 {unsigned int bad_cnt = 0;
nuclear@0 333 for (EdgeMap::iterator it = edges.begin(); it != edges.end(); ++it) {
nuclear@0 334 if ((*it).second.ref < 2) {
nuclear@0 335 ai_assert((*it).second.ref);
nuclear@0 336 ++bad_cnt;
nuclear@0 337 }
nuclear@0 338 (*it).second.edge_point *= 1.f/((*it).second.ref+2.f);
nuclear@0 339 }
nuclear@0 340
nuclear@0 341 if (bad_cnt) {
nuclear@0 342 // Report the number of bad edges. bad edges are referenced by less than two
nuclear@0 343 // faces in the mesh. They occur at outer model boundaries in non-closed
nuclear@0 344 // shapes.
nuclear@0 345 char tmp[512];
nuclear@0 346 sprintf(tmp,"Catmull-Clark Subdivider: got %u bad edges touching only one face (totally %u edges). ",
nuclear@0 347 bad_cnt,static_cast<unsigned int>(edges.size()));
nuclear@0 348
nuclear@0 349 DefaultLogger::get()->debug(tmp);
nuclear@0 350 }}
nuclear@0 351
nuclear@0 352 // ---------------------------------------------------------------------
nuclear@0 353 // 4. Compute a vertex-face adjacency table. We can't reuse the code
nuclear@0 354 // from VertexTriangleAdjacency because we need the table for multiple
nuclear@0 355 // meshes and out vertex indices need to be mapped to distinct values
nuclear@0 356 // first.
nuclear@0 357 // ---------------------------------------------------------------------
nuclear@0 358 UIntVector faceadjac(nfacesout), cntadjfac(maptbl.size(),0), ofsadjvec(maptbl.size()+1,0); {
nuclear@0 359 for (size_t t = 0; t < nmesh; ++t) {
nuclear@0 360 const aiMesh* const minp = smesh[t];
nuclear@0 361 for (unsigned int i = 0; i < minp->mNumFaces; ++i) {
nuclear@0 362
nuclear@0 363 const aiFace& f = minp->mFaces[i];
nuclear@0 364 for (unsigned int n = 0; n < f.mNumIndices; ++n) {
nuclear@0 365 ++cntadjfac[maptbl[FLATTEN_VERTEX_IDX(t,f.mIndices[n])]];
nuclear@0 366 }
nuclear@0 367 }
nuclear@0 368 }
nuclear@0 369 unsigned int cur = 0;
nuclear@0 370 for (size_t i = 0; i < cntadjfac.size(); ++i) {
nuclear@0 371 ofsadjvec[i+1] = cur;
nuclear@0 372 cur += cntadjfac[i];
nuclear@0 373 }
nuclear@0 374 for (size_t t = 0; t < nmesh; ++t) {
nuclear@0 375 const aiMesh* const minp = smesh[t];
nuclear@0 376 for (unsigned int i = 0; i < minp->mNumFaces; ++i) {
nuclear@0 377
nuclear@0 378 const aiFace& f = minp->mFaces[i];
nuclear@0 379 for (unsigned int n = 0; n < f.mNumIndices; ++n) {
nuclear@0 380 faceadjac[ofsadjvec[1+maptbl[FLATTEN_VERTEX_IDX(t,f.mIndices[n])]]++] = FLATTEN_FACE_IDX(t,i);
nuclear@0 381 }
nuclear@0 382 }
nuclear@0 383 }
nuclear@0 384
nuclear@0 385 // check the other way round for consistency
nuclear@0 386 #ifdef _DEBUG
nuclear@0 387
nuclear@0 388 for (size_t t = 0; t < ofsadjvec.size()-1; ++t) {
nuclear@0 389 for (unsigned int m = 0; m < cntadjfac[t]; ++m) {
nuclear@0 390 const unsigned int fidx = faceadjac[ofsadjvec[t]+m];
nuclear@0 391 ai_assert(fidx < totfaces);
nuclear@0 392 for (size_t n = 1; n < nmesh; ++n) {
nuclear@0 393
nuclear@0 394 if (moffsets[n].first > fidx) {
nuclear@0 395 const aiMesh* msh = smesh[--n];
nuclear@0 396 const aiFace& f = msh->mFaces[fidx-moffsets[n].first];
nuclear@0 397
nuclear@0 398 bool haveit = false;
nuclear@0 399 for (unsigned int i = 0; i < f.mNumIndices; ++i) {
nuclear@0 400 if (maptbl[FLATTEN_VERTEX_IDX(n,f.mIndices[i])]==(unsigned int)t) {
nuclear@0 401 haveit = true; break;
nuclear@0 402 }
nuclear@0 403 }
nuclear@0 404 ai_assert(haveit);
nuclear@0 405 break;
nuclear@0 406 }
nuclear@0 407 }
nuclear@0 408 }
nuclear@0 409 }
nuclear@0 410
nuclear@0 411 #endif
nuclear@0 412 }
nuclear@0 413
nuclear@0 414 #define GET_ADJACENT_FACES_AND_CNT(vidx,fstartout,numout) \
nuclear@0 415 fstartout = &faceadjac[ofsadjvec[vidx]], numout = cntadjfac[vidx]
nuclear@0 416
nuclear@0 417 typedef std::pair<bool,Vertex> TouchedOVertex;
nuclear@0 418 std::vector<TouchedOVertex > new_points(num_unique,TouchedOVertex(false,Vertex()));
nuclear@0 419 // ---------------------------------------------------------------------
nuclear@0 420 // 5. Spawn a quad from each face point to the corresponding edge points
nuclear@0 421 // the original points being the fourth quad points.
nuclear@0 422 // ---------------------------------------------------------------------
nuclear@0 423 for (size_t t = 0; t < nmesh; ++t) {
nuclear@0 424 const aiMesh* const minp = smesh[t];
nuclear@0 425 aiMesh* const mout = out[t] = new aiMesh();
nuclear@0 426
nuclear@0 427 for (unsigned int a = 0; a < minp->mNumFaces; ++a) {
nuclear@0 428 mout->mNumFaces += minp->mFaces[a].mNumIndices;
nuclear@0 429 }
nuclear@0 430
nuclear@0 431 // We need random access to the old face buffer, so reuse is not possible.
nuclear@0 432 mout->mFaces = new aiFace[mout->mNumFaces];
nuclear@0 433
nuclear@0 434 mout->mNumVertices = mout->mNumFaces*4;
nuclear@0 435 mout->mVertices = new aiVector3D[mout->mNumVertices];
nuclear@0 436
nuclear@0 437 // quads only, keep material index
nuclear@0 438 mout->mPrimitiveTypes = aiPrimitiveType_POLYGON;
nuclear@0 439 mout->mMaterialIndex = minp->mMaterialIndex;
nuclear@0 440
nuclear@0 441 if (minp->HasNormals()) {
nuclear@0 442 mout->mNormals = new aiVector3D[mout->mNumVertices];
nuclear@0 443 }
nuclear@0 444
nuclear@0 445 if (minp->HasTangentsAndBitangents()) {
nuclear@0 446 mout->mTangents = new aiVector3D[mout->mNumVertices];
nuclear@0 447 mout->mBitangents = new aiVector3D[mout->mNumVertices];
nuclear@0 448 }
nuclear@0 449
nuclear@0 450 for(unsigned int i = 0; minp->HasTextureCoords(i); ++i) {
nuclear@0 451 mout->mTextureCoords[i] = new aiVector3D[mout->mNumVertices];
nuclear@0 452 mout->mNumUVComponents[i] = minp->mNumUVComponents[i];
nuclear@0 453 }
nuclear@0 454
nuclear@0 455 for(unsigned int i = 0; minp->HasVertexColors(i); ++i) {
nuclear@0 456 mout->mColors[i] = new aiColor4D[mout->mNumVertices];
nuclear@0 457 }
nuclear@0 458
nuclear@0 459 mout->mNumVertices = mout->mNumFaces<<2u;
nuclear@0 460 for (unsigned int i = 0, v = 0, n = 0; i < minp->mNumFaces;++i) {
nuclear@0 461
nuclear@0 462 const aiFace& face = minp->mFaces[i];
nuclear@0 463 for (unsigned int a = 0; a < face.mNumIndices;++a) {
nuclear@0 464
nuclear@0 465 // Get a clean new face.
nuclear@0 466 aiFace& faceOut = mout->mFaces[n++];
nuclear@0 467 faceOut.mIndices = new unsigned int [faceOut.mNumIndices = 4];
nuclear@0 468
nuclear@0 469 // Spawn a new quadrilateral (ccw winding) for this original point between:
nuclear@0 470 // a) face centroid
nuclear@0 471 centroids[FLATTEN_FACE_IDX(t,i)].SortBack(mout,faceOut.mIndices[0]=v++);
nuclear@0 472
nuclear@0 473 // b) adjacent edge on the left, seen from the centroid
nuclear@0 474 const Edge& e0 = edges[MAKE_EDGE_HASH(maptbl[FLATTEN_VERTEX_IDX(t,face.mIndices[a])],
nuclear@0 475 maptbl[FLATTEN_VERTEX_IDX(t,face.mIndices[a==face.mNumIndices-1?0:a+1])
nuclear@0 476 ])]; // fixme: replace with mod face.mNumIndices?
nuclear@0 477
nuclear@0 478 // c) adjacent edge on the right, seen from the centroid
nuclear@0 479 const Edge& e1 = edges[MAKE_EDGE_HASH(maptbl[FLATTEN_VERTEX_IDX(t,face.mIndices[a])],
nuclear@0 480 maptbl[FLATTEN_VERTEX_IDX(t,face.mIndices[!a?face.mNumIndices-1:a-1])
nuclear@0 481 ])]; // fixme: replace with mod face.mNumIndices?
nuclear@0 482
nuclear@0 483 e0.edge_point.SortBack(mout,faceOut.mIndices[3]=v++);
nuclear@0 484 e1.edge_point.SortBack(mout,faceOut.mIndices[1]=v++);
nuclear@0 485
nuclear@0 486 // d= original point P with distinct index i
nuclear@0 487 // F := 0
nuclear@0 488 // R := 0
nuclear@0 489 // n := 0
nuclear@0 490 // for each face f containing i
nuclear@0 491 // F := F+ centroid of f
nuclear@0 492 // R := R+ midpoint of edge of f from i to i+1
nuclear@0 493 // n := n+1
nuclear@0 494 //
nuclear@0 495 // (F+2R+(n-3)P)/n
nuclear@0 496 const unsigned int org = maptbl[FLATTEN_VERTEX_IDX(t,face.mIndices[a])];
nuclear@0 497 TouchedOVertex& ov = new_points[org];
nuclear@0 498
nuclear@0 499 if (!ov.first) {
nuclear@0 500 ov.first = true;
nuclear@0 501
nuclear@0 502 const unsigned int* adj; unsigned int cnt;
nuclear@0 503 GET_ADJACENT_FACES_AND_CNT(org,adj,cnt);
nuclear@0 504
nuclear@0 505 if (cnt < 3) {
nuclear@0 506 ov.second = Vertex(minp,face.mIndices[a]);
nuclear@0 507 }
nuclear@0 508 else {
nuclear@0 509
nuclear@0 510 Vertex F,R;
nuclear@0 511 for (unsigned int o = 0; o < cnt; ++o) {
nuclear@0 512 ai_assert(adj[o] < totfaces);
nuclear@0 513 F += centroids[adj[o]];
nuclear@0 514
nuclear@0 515 // adj[0] is a global face index - search the face in the mesh list
nuclear@0 516 const aiMesh* mp = NULL;
nuclear@0 517 size_t nidx;
nuclear@0 518
nuclear@0 519 if (adj[o] < moffsets[0].first) {
nuclear@0 520 mp = smesh[nidx=0];
nuclear@0 521 }
nuclear@0 522 else {
nuclear@0 523 for (nidx = 1; nidx<= nmesh; ++nidx) {
nuclear@0 524 if (nidx == nmesh ||moffsets[nidx].first > adj[o]) {
nuclear@0 525 mp = smesh[--nidx];
nuclear@0 526 break;
nuclear@0 527 }
nuclear@0 528 }
nuclear@0 529 }
nuclear@0 530
nuclear@0 531 ai_assert(adj[o]-moffsets[nidx].first < mp->mNumFaces);
nuclear@0 532 const aiFace& f = mp->mFaces[adj[o]-moffsets[nidx].first];
nuclear@0 533 # ifdef _DEBUG
nuclear@0 534 bool haveit = false;
nuclear@0 535 # endif
nuclear@0 536
nuclear@0 537 // find our original point in the face
nuclear@0 538 for (unsigned int m = 0; m < f.mNumIndices; ++m) {
nuclear@0 539 if (maptbl[FLATTEN_VERTEX_IDX(nidx,f.mIndices[m])] == org) {
nuclear@0 540
nuclear@0 541 // add *both* edges. this way, we can be sure that we add
nuclear@0 542 // *all* adjacent edges to R. In a closed shape, every
nuclear@0 543 // edge is added twice - so we simply leave out the
nuclear@0 544 // factor 2.f in the amove formula and get the right
nuclear@0 545 // result.
nuclear@0 546
nuclear@0 547 const Edge& c0 = edges[MAKE_EDGE_HASH(org,maptbl[FLATTEN_VERTEX_IDX(
nuclear@0 548 nidx,f.mIndices[!m?f.mNumIndices-1:m-1])])];
nuclear@0 549 // fixme: replace with mod face.mNumIndices?
nuclear@0 550
nuclear@0 551 const Edge& c1 = edges[MAKE_EDGE_HASH(org,maptbl[FLATTEN_VERTEX_IDX(
nuclear@0 552 nidx,f.mIndices[m==f.mNumIndices-1?0:m+1])])];
nuclear@0 553 // fixme: replace with mod face.mNumIndices?
nuclear@0 554 R += c0.midpoint+c1.midpoint;
nuclear@0 555
nuclear@0 556 # ifdef _DEBUG
nuclear@0 557 haveit = true;
nuclear@0 558 # endif
nuclear@0 559 break;
nuclear@0 560 }
nuclear@0 561 }
nuclear@0 562
nuclear@0 563 // this invariant *must* hold if the vertex-to-face adjacency table is valid
nuclear@0 564 ai_assert(haveit);
nuclear@0 565 }
nuclear@0 566
nuclear@0 567 const float div = static_cast<float>(cnt), divsq = 1.f/(div*div);
nuclear@0 568 ov.second = Vertex(minp,face.mIndices[a])*((div-3.f) / div) + R*divsq + F*divsq;
nuclear@0 569 }
nuclear@0 570 }
nuclear@0 571 ov.second.SortBack(mout,faceOut.mIndices[2]=v++);
nuclear@0 572 }
nuclear@0 573 }
nuclear@0 574 }
nuclear@0 575
nuclear@0 576 // ---------------------------------------------------------------------
nuclear@0 577 // 7. Apply the next subdivision step.
nuclear@0 578 // ---------------------------------------------------------------------
nuclear@0 579 if (num != 1) {
nuclear@0 580 std::vector<aiMesh*> tmp(nmesh);
nuclear@0 581 InternSubdivide (out,nmesh,&tmp.front(),num-1);
nuclear@0 582 for (size_t i = 0; i < nmesh; ++i) {
nuclear@0 583 delete out[i];
nuclear@0 584 out[i] = tmp[i];
nuclear@0 585 }
nuclear@0 586 }
nuclear@0 587 }