source/blender/blenkernel/intern/CCGSubSurf.c

   1 /* $Id$ */
   2
   3 #include <stdlib.h>
   4 #include <string.h>
   5 #include <math.h>
   6 #include <float.h>
   7
   8 #include "CCGSubSurf.h"
   9
  10 #include "BLO_sys_types.h" // for intptr_t support
  11
  12 /***/
  13
  14 typedef unsigned char   byte;
  15
  16 /***/
  17
  18 static int kHashSizes[] = {
  19         1, 3, 5, 11, 17, 37, 67, 131, 257, 521, 1031, 2053, 4099, 8209,
  20         16411, 32771, 65537, 131101, 262147, 524309, 1048583, 2097169,
  21         4194319, 8388617, 16777259, 33554467, 67108879, 134217757, 268435459
  22 };
  23
  24 typedef struct _EHEntry EHEntry;
  25 struct _EHEntry {
  26         EHEntry *next;
  27         void *key;
  28 };
  29 typedef struct _EHash {
  30         EHEntry **buckets;
  31         int numEntries, curSize, curSizeIdx;
  32
  33         CCGAllocatorIFC allocatorIFC;
  34         CCGAllocatorHDL allocator;
  35 } EHash;
  36
  37 #define EHASH_alloc(eh, nb)                     ((eh)->allocatorIFC.alloc((eh)->allocator, nb))
  38 #define EHASH_free(eh, ptr)                     ((eh)->allocatorIFC.free((eh)->allocator, ptr))
  39
  40 #define EHASH_hash(eh, item)    (((uintptr_t) (item))%((unsigned int) (eh)->curSize))
  41
  42 static EHash *_ehash_new(int estimatedNumEntries, CCGAllocatorIFC *allocatorIFC, CCGAllocatorHDL allocator) {
  43         EHash *eh = allocatorIFC->alloc(allocator, sizeof(*eh));
  44         eh->allocatorIFC = *allocatorIFC;
  45         eh->allocator = allocator;
  46         eh->numEntries = 0;
  47         eh->curSizeIdx = 0;
  48         while (kHashSizes[eh->curSizeIdx]<estimatedNumEntries)
  49                 eh->curSizeIdx++;
  50         eh->curSize = kHashSizes[eh->curSizeIdx];
  51         eh->buckets = EHASH_alloc(eh, eh->curSize*sizeof(*eh->buckets));
  52         memset(eh->buckets, 0, eh->curSize*sizeof(*eh->buckets));
  53
  54         return eh;
  55 }
  56 typedef void (*EHEntryFreeFP)(EHEntry *, void *);
  57 static void _ehash_free(EHash *eh, EHEntryFreeFP freeEntry, void *userData) {
  58         int numBuckets = eh->curSize;
  59
  60         while (numBuckets--) {
  61                 EHEntry *entry = eh->buckets[numBuckets];
  62
  63                 while (entry) {
  64                         EHEntry *next = entry->next;
  65
  66                         freeEntry(entry, userData);
  67
  68                         entry = next;
  69                 }
  70         }
  71
  72         EHASH_free(eh, eh->buckets);
  73         EHASH_free(eh, eh);
  74 }
  75
  76 static void _ehash_insert(EHash *eh, EHEntry *entry) {
  77         int numBuckets = eh->curSize;
  78         int hash = EHASH_hash(eh, entry->key);
  79         entry->next = eh->buckets[hash];
  80         eh->buckets[hash] = entry;
  81         eh->numEntries++;
  82
  83         if (eh->numEntries > (numBuckets*3)) {
  84                 EHEntry **oldBuckets = eh->buckets;
  85                 eh->curSize = kHashSizes[++eh->curSizeIdx];
  86
  87                 eh->buckets = EHASH_alloc(eh, eh->curSize*sizeof(*eh->buckets));
  88                 memset(eh->buckets, 0, eh->curSize*sizeof(*eh->buckets));
  89
  90                 while (numBuckets--) {
  91                         for (entry = oldBuckets[numBuckets]; entry;) {
  92                                 EHEntry *next = entry->next;
  93
  94                                 hash = EHASH_hash(eh, entry->key);
  95                                 entry->next = eh->buckets[hash];
  96                                 eh->buckets[hash] = entry;
  97
  98                                 entry = next;
  99                         }
 100                 }
 101
 102                 EHASH_free(eh, oldBuckets);
 103         }
 104 }
 105
 106 static void *_ehash_lookupWithPrev(EHash *eh, void *key, void ***prevp_r) {
 107         int hash = EHASH_hash(eh, key);
 108         void **prevp = (void**) &eh->buckets[hash];
 109         EHEntry *entry;
 110
 111         for (; (entry = *prevp); prevp = (void**) &entry->next) {
 112                 if (entry->key==key) {
 113                         *prevp_r = (void**) prevp;
 114                         return entry;
 115                 }
 116         }
 117
 118         return NULL;
 119 }
 120
 121 static void *_ehash_lookup(EHash *eh, void *key) {
 122         int hash = EHASH_hash(eh, key);
 123         EHEntry *entry;
 124
 125         for (entry = eh->buckets[hash]; entry; entry = entry->next)
 126                 if (entry->key==key)
 127                         break;
 128
 129         return entry;
 130 }
 131
 132 /**/
 133
 134 typedef struct _EHashIterator {
 135         EHash *eh;
 136         int curBucket;
 137         EHEntry *curEntry;
 138 } EHashIterator;
 139
 140 static EHashIterator *_ehashIterator_new(EHash *eh) {
 141         EHashIterator *ehi = EHASH_alloc(eh, sizeof(*ehi));
 142         ehi->eh = eh;
 143         ehi->curEntry = NULL;
 144         ehi->curBucket = -1;
 145         while (!ehi->curEntry) {
 146                 ehi->curBucket++;
 147                 if (ehi->curBucket==ehi->eh->curSize)
 148                         break;
 149                 ehi->curEntry = ehi->eh->buckets[ehi->curBucket];
 150         }
 151         return ehi;
 152 }
 153 static void _ehashIterator_free(EHashIterator *ehi) {
 154         EHASH_free(ehi->eh, ehi);
 155 }
 156
 157 static void *_ehashIterator_getCurrent(EHashIterator *ehi) {
 158         return ehi->curEntry;
 159 }
 160
 161 static void _ehashIterator_next(EHashIterator *ehi) {
 162         if (ehi->curEntry) {
 163         ehi->curEntry = ehi->curEntry->next;
 164                 while (!ehi->curEntry) {
 165                         ehi->curBucket++;
 166                         if (ehi->curBucket==ehi->eh->curSize)
 167                                 break;
 168                         ehi->curEntry = ehi->eh->buckets[ehi->curBucket];
 169                 }
 170         }
 171 }
 172 static int _ehashIterator_isStopped(EHashIterator *ehi) {
 173         return !ehi->curEntry;
 174 }
 175
 176 /***/
 177
 178 static void *_stdAllocator_alloc(CCGAllocatorHDL a, int numBytes) {
 179         return malloc(numBytes);
 180 }
 181 static void *_stdAllocator_realloc(CCGAllocatorHDL a, void *ptr, int newSize, int oldSize) {
 182         return realloc(ptr, newSize);
 183 }
 184 static void _stdAllocator_free(CCGAllocatorHDL a, void *ptr) {
 185         free(ptr);
 186 }
 187
 188 static CCGAllocatorIFC *_getStandardAllocatorIFC(void) {
 189         static CCGAllocatorIFC ifc;
 190
 191         ifc.alloc = _stdAllocator_alloc;
 192         ifc.realloc = _stdAllocator_realloc;
 193         ifc.free = _stdAllocator_free;
 194         ifc.release = NULL;
 195
 196         return &ifc;
 197 }
 198
 199 /***/
 200
 201 static int VertDataEqual(float *a, float *b) {
 202         return a[0]==b[0] && a[1]==b[1] && a[2]==b[2];
 203 }
 204 #define VertDataZero(av)                                { float *_a = (float*) av; _a[0] = _a[1] = _a[2] = 0.0f; }
 205 #define VertDataCopy(av, bv)                    { float *_a = (float*) av, *_b = (float*) bv; _a[0] =_b[0]; _a[1] =_b[1]; _a[2] =_b[2]; }
 206 #define VertDataAdd(av, bv)                             { float *_a = (float*) av, *_b = (float*) bv; _a[0]+=_b[0]; _a[1]+=_b[1]; _a[2]+=_b[2]; }
 207 #define VertDataSub(av, bv)                             { float *_a = (float*) av, *_b = (float*) bv; _a[0]-=_b[0]; _a[1]-=_b[1]; _a[2]-=_b[2]; }
 208 #define VertDataMulN(av, n)                             { float *_a = (float*) av; _a[0]*=n; _a[1]*=n; _a[2]*=n; }
 209 #define VertDataAvg4(tv, av, bv, cv, dv) \
 210         { \
 211                 float *_t = (float*) tv, *_a = (float*) av, *_b = (float*) bv, *_c = (float*) cv, *_d = (float*) dv; \
 212                 _t[0] = (_a[0]+_b[0]+_c[0]+_d[0])*.25; \
 213                 _t[1] = (_a[1]+_b[1]+_c[1]+_d[1])*.25; \
 214                 _t[2] = (_a[2]+_b[2]+_c[2]+_d[2])*.25; \
 215         }
 216 #define NormZero(av)                                    { float *_a = (float*) av; _a[0] = _a[1] = _a[2] = 0.0f; }
 217 #define NormCopy(av, bv)                                { float *_a = (float*) av, *_b = (float*) bv; _a[0] =_b[0]; _a[1] =_b[1]; _a[2] =_b[2]; }
 218 #define NormAdd(av, bv)                                 { float *_a = (float*) av, *_b = (float*) bv; _a[0]+=_b[0]; _a[1]+=_b[1]; _a[2]+=_b[2]; }
 219
 220
 221 static int _edge_isBoundary(CCGEdge *e);
 222
 223 /***/
 224
 225 enum {
 226         Vert_eEffected=         (1<<0),
 227         Vert_eChanged=          (1<<1),
 228         Vert_eSeam=                     (1<<2),
 229 } VertFlags;
 230 enum {
 231         Edge_eEffected=         (1<<0),
 232 } CCGEdgeFlags;
 233 enum {
 234         Face_eEffected=         (1<<0),
 235 } FaceFlags;
 236
 237 struct _CCGVert {
 238         CCGVert         *next;  /* EHData.next */
 239         CCGVertHDL      vHDL;   /* EHData.key */
 240
 241         short numEdges, numFaces, flags, pad;
 242
 243         CCGEdge **edges;
 244         CCGFace **faces;
 245 //      byte *levelData;
 246 //      byte *userData;
 247 };
 248 #define VERT_getLevelData(v)            ((byte*) &(v)[1])
 249
 250 struct _CCGEdge {
 251         CCGEdge         *next;  /* EHData.next */
 252         CCGEdgeHDL      eHDL;   /* EHData.key */
 253
 254         short numFaces, flags;
 255         float crease;
 256
 257         CCGVert *v0,*v1;
 258         CCGFace **faces;
 259
 260 //      byte *levelData;
 261 //      byte *userData;
 262 };
 263 #define EDGE_getLevelData(e)            ((byte*) &(e)[1])
 264
 265 struct _CCGFace {
 266         CCGFace         *next;  /* EHData.next */
 267         CCGFaceHDL      fHDL;   /* EHData.key */
 268
 269         short numVerts, flags, pad1, pad2;
 270
 271 //      CCGVert **verts;
 272 //      CCGEdge **edges;
 273 //      byte *centerData;
 274 //      byte **gridData;
 275 //      byte *userData;
 276 };
 277 #define FACE_getVerts(f)                ((CCGVert**) &(f)[1])
 278 #define FACE_getEdges(f)                ((CCGEdge**) &(FACE_getVerts(f)[(f)->numVerts]))
 279 #define FACE_getCenterData(f)   ((byte*) &(FACE_getEdges(f)[(f)->numVerts]))
 280
 281 typedef enum {
 282         eSyncState_None = 0,
 283         eSyncState_Vert,
 284         eSyncState_Edge,
 285         eSyncState_Face,
 286         eSyncState_Partial,
 287 } SyncState;
 288
 289 struct _CCGSubSurf {
 290         EHash *vMap;    /* map of CCGVertHDL -> Vert */
 291         EHash *eMap;    /* map of CCGEdgeHDL -> Edge */
 292         EHash *fMap;    /* map of CCGFaceHDL -> Face */
 293
 294         CCGMeshIFC meshIFC;
 295
 296         CCGAllocatorIFC allocatorIFC;
 297         CCGAllocatorHDL allocator;
 298
 299         int subdivLevels;
 300         int numGrids;
 301         int allowEdgeCreation;
 302         float defaultCreaseValue;
 303         void *defaultEdgeUserData;
 304
 305         void *q, *r;
 306
 307                 // data for calc vert normals
 308         int calcVertNormals;
 309         int normalDataOffset;
 310
 311                 // data for age'ing (to debug sync)
 312         int currentAge;
 313         int useAgeCounts;
 314         int vertUserAgeOffset;
 315         int edgeUserAgeOffset;
 316         int faceUserAgeOffset;
 317
 318                 // data used during syncing
 319         SyncState syncState;
 320
 321         EHash *oldVMap, *oldEMap, *oldFMap;
 322         int lenTempArrays;
 323         CCGVert **tempVerts;
 324         CCGEdge **tempEdges;
 325 };
 326
 327 #define CCGSUBSURF_alloc(ss, nb)                        ((ss)->allocatorIFC.alloc((ss)->allocator, nb))
 328 #define CCGSUBSURF_realloc(ss, ptr, nb, ob)     ((ss)->allocatorIFC.realloc((ss)->allocator, ptr, nb, ob))
 329 #define CCGSUBSURF_free(ss, ptr)                        ((ss)->allocatorIFC.free((ss)->allocator, ptr))
 330
 331 /***/
 332
 333 static CCGVert *_vert_new(CCGVertHDL vHDL, CCGSubSurf *ss) {
 334         CCGVert *v = CCGSUBSURF_alloc(ss, sizeof(CCGVert) + ss->meshIFC.vertDataSize * (ss->subdivLevels+1) + ss->meshIFC.vertUserSize);
 335         byte *userData;
 336
 337         v->vHDL = vHDL;
 338         v->edges = NULL;
 339         v->faces = NULL;
 340         v->numEdges = v->numFaces = 0;
 341         v->flags = 0;
 342
 343         userData = ccgSubSurf_getVertUserData(ss, v);
 344         memset(userData, 0, ss->meshIFC.vertUserSize);
 345         if (ss->useAgeCounts) *((int*) &userData[ss->vertUserAgeOffset]) = ss->currentAge;
 346
 347         return v;
 348 }
 349 static void _vert_remEdge(CCGVert *v, CCGEdge *e) {
 350         int i;
 351         for (i=0; i<v->numEdges; i++) {
 352                 if (v->edges[i]==e) {
 353                         v->edges[i] = v->edges[--v->numEdges];
 354                         break;
 355                 }
 356         }
 357 }
 358 static void _vert_remFace(CCGVert *v, CCGFace *f) {
 359         int i;
 360         for (i=0; i<v->numFaces; i++) {
 361                 if (v->faces[i]==f) {
 362                         v->faces[i] = v->faces[--v->numFaces];
 363                         break;
 364                 }
 365         }
 366 }
 367 static void _vert_addEdge(CCGVert *v, CCGEdge *e, CCGSubSurf *ss) {
 368         v->edges = CCGSUBSURF_realloc(ss, v->edges, (v->numEdges+1)*sizeof(*v->edges), v->numEdges*sizeof(*v->edges));
 369         v->edges[v->numEdges++] = e;
 370 }
 371 static void _vert_addFace(CCGVert *v, CCGFace *f, CCGSubSurf *ss) {
 372         v->faces = CCGSUBSURF_realloc(ss, v->faces, (v->numFaces+1)*sizeof(*v->faces), v->numFaces*sizeof(*v->faces));
 373         v->faces[v->numFaces++] = f;
 374 }
 375 static CCGEdge *_vert_findEdgeTo(CCGVert *v, CCGVert *vQ) {
 376         int i;
 377         for (i=0; i<v->numEdges; i++) {
 378                 CCGEdge *e = v->edges[v->numEdges-1-i]; // XXX, note reverse
 379                 if (    (e->v0==v && e->v1==vQ) ||
 380                                 (e->v1==v && e->v0==vQ))
 381                         return e;
 382         }
 383         return 0;
 384 }
 385 static int _vert_isBoundary(CCGVert *v) {
 386         int i;
 387         for (i=0; i<v->numEdges; i++)
 388                 if (_edge_isBoundary(v->edges[i]))
 389                         return 1;
 390         return 0;
 391 }
 392
 393 static void *_vert_getCo(CCGVert *v, int lvl, int dataSize) {
 394         return &VERT_getLevelData(v)[lvl*dataSize];
 395 }
 396 static float *_vert_getNo(CCGVert *v, int lvl, int dataSize, int normalDataOffset) {
 397         return (float*) &VERT_getLevelData(v)[lvl*dataSize + normalDataOffset];
 398 }
 399
 400 static void _vert_free(CCGVert *v, CCGSubSurf *ss) {
 401         CCGSUBSURF_free(ss, v->edges);
 402         CCGSUBSURF_free(ss, v->faces);
 403         CCGSUBSURF_free(ss, v);
 404 }
 405
 406 static int VERT_seam(CCGVert *v) {
 407         return ((v->flags & Vert_eSeam) != 0);
 408 }
 409
 410 /***/
 411
 412 static CCGEdge *_edge_new(CCGEdgeHDL eHDL, CCGVert *v0, CCGVert *v1, float crease, CCGSubSurf *ss) {
 413         CCGEdge *e = CCGSUBSURF_alloc(ss, sizeof(CCGEdge) + ss->meshIFC.vertDataSize *((ss->subdivLevels+1) + (1<<(ss->subdivLevels+1))-1) + ss->meshIFC.edgeUserSize);
 414         byte *userData;
 415
 416         e->eHDL = eHDL;
 417         e->v0 = v0;
 418         e->v1 = v1;
 419         e->crease = crease;
 420         e->faces = NULL;
 421         e->numFaces = 0;
 422         e->flags = 0;
 423         _vert_addEdge(v0, e, ss);
 424         _vert_addEdge(v1, e, ss);
 425
 426         userData = ccgSubSurf_getEdgeUserData(ss, e);
 427         memset(userData, 0, ss->meshIFC.edgeUserSize);
 428         if (ss->useAgeCounts) *((int*) &userData[ss->edgeUserAgeOffset]) = ss->currentAge;
 429
 430         return e;
 431 }
 432 static void _edge_remFace(CCGEdge *e, CCGFace *f) {
 433         int i;
 434         for (i=0; i<e->numFaces; i++) {
 435                 if (e->faces[i]==f) {
 436                         e->faces[i] = e->faces[--e->numFaces];
 437                         break;
 438                 }
 439         }
 440 }
 441 static void _edge_addFace(CCGEdge *e, CCGFace *f, CCGSubSurf *ss) {
 442         e->faces = CCGSUBSURF_realloc(ss, e->faces, (e->numFaces+1)*sizeof(*e->faces), e->numFaces*sizeof(*e->faces));
 443         e->faces[e->numFaces++] = f;
 444 }
 445 static int _edge_isBoundary(CCGEdge *e) {
 446         return e->numFaces<2;
 447 }
 448
 449 static CCGVert *_edge_getOtherVert(CCGEdge *e, CCGVert *vQ) {
 450         if (vQ==e->v0) {
 451                 return e->v1;
 452         } else {
 453                 return e->v0;
 454         }
 455 }
 456
 457 static void *_edge_getCo(CCGEdge *e, int lvl, int x, int dataSize) {
 458         int levelBase = lvl + (1<<lvl) - 1;
 459         return &EDGE_getLevelData(e)[dataSize*(levelBase + x)];
 460 }
 461 #if 0
 462 static float *_edge_getNo(CCGEdge *e, int lvl, int x, int dataSize, int normalDataOffset) {
 463         int levelBase = lvl + (1<<lvl) - 1;
 464         return (float*) &EDGE_getLevelData(e)[dataSize*(levelBase + x) + normalDataOffset];
 465 }
 466 #endif
 467 static void *_edge_getCoVert(CCGEdge *e, CCGVert *v, int lvl, int x, int dataSize) {
 468         int levelBase = lvl + (1<<lvl) - 1;
 469         if (v==e->v0) {
 470                 return &EDGE_getLevelData(e)[dataSize*(levelBase + x)];
 471         } else {
 472                 return &EDGE_getLevelData(e)[dataSize*(levelBase + (1<<lvl) - x)];
 473         }
 474 }
 475
 476 static void _edge_free(CCGEdge *e, CCGSubSurf *ss) {
 477         CCGSUBSURF_free(ss, e->faces);
 478         CCGSUBSURF_free(ss, e);
 479 }
 480 static void _edge_unlinkMarkAndFree(CCGEdge *e, CCGSubSurf *ss) {
 481         _vert_remEdge(e->v0, e);
 482         _vert_remEdge(e->v1, e);
 483         e->v0->flags |= Vert_eEffected;
 484         e->v1->flags |= Vert_eEffected;
 485         _edge_free(e, ss);
 486 }
 487
 488 static float EDGE_getSharpness(CCGEdge *e, int lvl) {
 489         if (!lvl)
 490                 return e->crease;
 491         else if (!e->crease)
 492                 return 0.0;
 493         else if (e->crease - lvl < 0.0)
 494                 return 0.0;
 495         else
 496                 return e->crease - lvl;
 497 }
 498
 499 static CCGFace *_face_new(CCGFaceHDL fHDL, CCGVert **verts, CCGEdge **edges, int numVerts, CCGSubSurf *ss) {
 500         int maxGridSize = 1 + (1<<(ss->subdivLevels-1));
 501         CCGFace *f = CCGSUBSURF_alloc(ss, sizeof(CCGFace) + sizeof(CCGVert*)*numVerts + sizeof(CCGEdge*)*numVerts + ss->meshIFC.vertDataSize *(1 + numVerts*maxGridSize + numVerts*maxGridSize*maxGridSize) + ss->meshIFC.faceUserSize);
 502         byte *userData;
 503         int i;
 504
 505         f->numVerts = numVerts;
 506         f->fHDL = fHDL;
 507         f->flags = 0;
 508
 509         for (i=0; i<numVerts; i++) {
 510                 FACE_getVerts(f)[i] = verts[i];
 511                 FACE_getEdges(f)[i] = edges[i];
 512                 _vert_addFace(verts[i], f, ss);
 513                 _edge_addFace(edges[i], f, ss);
 514         }
 515
 516         userData = ccgSubSurf_getFaceUserData(ss, f);
 517         memset(userData, 0, ss->meshIFC.faceUserSize);
 518         if (ss->useAgeCounts) *((int*) &userData[ss->faceUserAgeOffset]) = ss->currentAge;
 519
 520         return f;
 521 }
 522
 523 static void *_face_getIECo(CCGFace *f, int lvl, int S, int x, int levels, int dataSize) {
 524         int maxGridSize = 1 + (1<<(levels-1));
 525         int spacing = 1<<(levels-lvl);
 526         byte *gridBase = FACE_getCenterData(f) + dataSize*(1 + S*(maxGridSize + maxGridSize*maxGridSize));
 527         return &gridBase[dataSize*x*spacing];
 528 }
 529 static void *_face_getIFCo(CCGFace *f, int lvl, int S, int x, int y, int levels, int dataSize) {
 530         int maxGridSize = 1 + (1<<(levels-1));
 531         int spacing = 1<<(levels-lvl);
 532         byte *gridBase = FACE_getCenterData(f) + dataSize*(1 + S*(maxGridSize + maxGridSize*maxGridSize));
 533         return &gridBase[dataSize*(maxGridSize + (y*maxGridSize + x)*spacing)];
 534 }
 535 static float *_face_getIFNo(CCGFace *f, int lvl, int S, int x, int y, int levels, int dataSize, int normalDataOffset) {
 536         int maxGridSize = 1 + (1<<(levels-1));
 537         int spacing = 1<<(levels-lvl);
 538         byte *gridBase = FACE_getCenterData(f) + dataSize*(1 + S*(maxGridSize + maxGridSize*maxGridSize));
 539         return (float*) &gridBase[dataSize*(maxGridSize + (y*maxGridSize + x)*spacing) + normalDataOffset];
 540 }
 541 static int _face_getVertIndex(CCGFace *f, CCGVert *v) {
 542         int i;
 543         for (i=0; i<f->numVerts; i++)
 544                 if (FACE_getVerts(f)[i]==v)
 545                         return i;
 546         return -1;
 547 }
 548 static void *_face_getIFCoEdge(CCGFace *f, CCGEdge *e, int lvl, int eX, int eY, int levels, int dataSize) {
 549         int maxGridSize = 1 + (1<<(levels-1));
 550         int spacing = 1<<(levels-lvl);
 551         int S, x, y, cx, cy;
 552
 553         for (S=0; S<f->numVerts; S++)
 554                 if (FACE_getEdges(f)[S]==e)
 555                         break;
 556
 557         eX = eX*spacing;
 558         eY = eY*spacing;
 559         if (e->v0!=FACE_getVerts(f)[S]) {
 560                 eX = (maxGridSize*2 - 1)-1 - eX;
 561         }
 562         y = maxGridSize - 1 - eX;
 563         x = maxGridSize - 1 - eY;
 564         if (x<0) {
 565                 S = (S+f->numVerts-1)%f->numVerts;
 566                 cx = y;
 567                 cy = -x;
 568         } else if (y<0) {
 569                 S = (S+1)%f->numVerts;
 570                 cx = -y;
 571                 cy = x;
 572         } else {
 573                 cx = x;
 574                 cy = y;
 575         }
 576         return _face_getIFCo(f, levels, S, cx, cy, levels, dataSize);
 577 }
 578 static float *_face_getIFNoEdge(CCGFace *f, CCGEdge *e, int lvl, int eX, int eY, int levels, int dataSize, int normalDataOffset) {
 579         return (float*) ((byte*) _face_getIFCoEdge(f, e, lvl, eX, eY, levels, dataSize) + normalDataOffset);
 580 }
 581 void _face_calcIFNo(CCGFace *f, int lvl, int S, int x, int y, float *no, int levels, int dataSize) {
 582         float *a = _face_getIFCo(f, lvl, S, x+0, y+0, levels, dataSize);
 583         float *b = _face_getIFCo(f, lvl, S, x+1, y+0, levels, dataSize);
 584         float *c = _face_getIFCo(f, lvl, S, x+1, y+1, levels, dataSize);
 585         float *d = _face_getIFCo(f, lvl, S, x+0, y+1, levels, dataSize);
 586         float a_cX = c[0]-a[0], a_cY = c[1]-a[1], a_cZ = c[2]-a[2];
 587         float b_dX = d[0]-b[0], b_dY = d[1]-b[1], b_dZ = d[2]-b[2];
 588         float length;
 589
 590         no[0] = b_dY*a_cZ - b_dZ*a_cY;
 591         no[1] = b_dZ*a_cX - b_dX*a_cZ;
 592         no[2] = b_dX*a_cY - b_dY*a_cX;
 593
 594         length = sqrt(no[0]*no[0] + no[1]*no[1] + no[2]*no[2]);
 595
 596         if (length>FLT_EPSILON) {
 597                 float invLength = 1.f/length;
 598
 599                 no[0] *= invLength;
 600                 no[1] *= invLength;
 601                 no[2] *= invLength;
 602         } else {
 603                 NormZero(no);
 604         }
 605 }
 606
 607 static void _face_free(CCGFace *f, CCGSubSurf *ss) {
 608         CCGSUBSURF_free(ss, f);
 609 }
 610 static void _face_unlinkMarkAndFree(CCGFace *f, CCGSubSurf *ss) {
 611         int j;
 612         for (j=0; j<f->numVerts; j++) {
 613                 _vert_remFace(FACE_getVerts(f)[j], f);
 614                 _edge_remFace(FACE_getEdges(f)[j], f);
 615                 FACE_getVerts(f)[j]->flags |= Vert_eEffected;
 616         }
 617         _face_free(f, ss);
 618 }
 619
 620 /***/
 621
 622 CCGSubSurf *ccgSubSurf_new(CCGMeshIFC *ifc, int subdivLevels, CCGAllocatorIFC *allocatorIFC, CCGAllocatorHDL allocator) {
 623         if (!allocatorIFC) {
 624                 allocatorIFC = _getStandardAllocatorIFC();
 625                 allocator = NULL;
 626         }
 627
 628         if (subdivLevels<1) {
 629                 return NULL;
 630         } else {
 631                 CCGSubSurf *ss = allocatorIFC->alloc(allocator, sizeof(*ss));
 632
 633                 ss->allocatorIFC = *allocatorIFC;
 634                 ss->allocator = allocator;
 635
 636                 ss->vMap = _ehash_new(0, &ss->allocatorIFC, ss->allocator);
 637                 ss->eMap = _ehash_new(0, &ss->allocatorIFC, ss->allocator);
 638                 ss->fMap = _ehash_new(0, &ss->allocatorIFC, ss->allocator);
 639
 640                 ss->meshIFC = *ifc;
 641
 642                 ss->subdivLevels = subdivLevels;
 643                 ss->numGrids = 0;
 644                 ss->allowEdgeCreation = 0;
 645                 ss->defaultCreaseValue = 0;
 646                 ss->defaultEdgeUserData = NULL;
 647
 648                 ss->useAgeCounts = 0;
 649                 ss->vertUserAgeOffset = ss->edgeUserAgeOffset = ss->faceUserAgeOffset = 0;
 650
 651                 ss->calcVertNormals = 0;
 652                 ss->normalDataOffset = 0;
 653
 654                 ss->q = CCGSUBSURF_alloc(ss, ss->meshIFC.vertDataSize);
 655                 ss->r = CCGSUBSURF_alloc(ss, ss->meshIFC.vertDataSize);
 656
 657                 ss->currentAge = 0;
 658
 659                 ss->syncState = eSyncState_None;
 660
 661                 ss->oldVMap = ss->oldEMap = ss->oldFMap = NULL;
 662                 ss->lenTempArrays = 0;
 663                 ss->tempVerts = NULL;
 664                 ss->tempEdges = NULL;
 665
 666                 return ss;
 667         }
 668 }
 669
 670 void ccgSubSurf_free(CCGSubSurf *ss) {
 671         CCGAllocatorIFC allocatorIFC = ss->allocatorIFC;
 672         CCGAllocatorHDL allocator = ss->allocator;
 673
 674         if (ss->syncState) {
 675                 _ehash_free(ss->oldFMap, (EHEntryFreeFP) _face_free, ss);
 676                 _ehash_free(ss->oldEMap, (EHEntryFreeFP) _edge_free, ss);
 677                 _ehash_free(ss->oldVMap, (EHEntryFreeFP) _vert_free, ss);
 678
 679                 CCGSUBSURF_free(ss, ss->tempVerts);
 680                 CCGSUBSURF_free(ss, ss->tempEdges);
 681         }
 682
 683         CCGSUBSURF_free(ss, ss->r);
 684         CCGSUBSURF_free(ss, ss->q);
 685         if (ss->defaultEdgeUserData) CCGSUBSURF_free(ss, ss->defaultEdgeUserData);
 686
 687         _ehash_free(ss->fMap, (EHEntryFreeFP) _face_free, ss);
 688         _ehash_free(ss->eMap, (EHEntryFreeFP) _edge_free, ss);
 689         _ehash_free(ss->vMap, (EHEntryFreeFP) _vert_free, ss);
 690
 691         CCGSUBSURF_free(ss, ss);
 692
 693         if (allocatorIFC.release) {
 694                 allocatorIFC.release(allocator);
 695         }
 696 }
 697
 698 CCGError ccgSubSurf_setAllowEdgeCreation(CCGSubSurf *ss, int allowEdgeCreation, float defaultCreaseValue, void *defaultUserData) {
 699         if (ss->defaultEdgeUserData) {
 700                 CCGSUBSURF_free(ss, ss->defaultEdgeUserData);
 701         }
 702
 703         ss->allowEdgeCreation = !!allowEdgeCreation;
 704         ss->defaultCreaseValue = defaultCreaseValue;
 705         ss->defaultEdgeUserData = CCGSUBSURF_alloc(ss, ss->meshIFC.edgeUserSize);
 706
 707         if (defaultUserData) {
 708                 memcpy(ss->defaultEdgeUserData, defaultUserData, ss->meshIFC.edgeUserSize);
 709         } else {
 710                 memset(ss->defaultEdgeUserData, 0, ss->meshIFC.edgeUserSize);
 711         }
 712
 713         return eCCGError_None;
 714 }
 715 void ccgSubSurf_getAllowEdgeCreation(CCGSubSurf *ss, int *allowEdgeCreation_r, float *defaultCreaseValue_r, void *defaultUserData_r) {
 716         if (allowEdgeCreation_r) *allowEdgeCreation_r = ss->allowEdgeCreation;
 717         if (ss->allowEdgeCreation) {
 718                 if (defaultCreaseValue_r) *defaultCreaseValue_r = ss->defaultCreaseValue;
 719                 if (defaultUserData_r) memcpy(defaultUserData_r, ss->defaultEdgeUserData, ss->meshIFC.edgeUserSize);
 720         }
 721 }
 722
 723 CCGError ccgSubSurf_setSubdivisionLevels(CCGSubSurf *ss, int subdivisionLevels) {
 724         if (subdivisionLevels<=0) {
 725                 return eCCGError_InvalidValue;
 726         } else if (subdivisionLevels!=ss->subdivLevels) {
 727                 ss->numGrids = 0;
 728                 ss->subdivLevels = subdivisionLevels;
 729                 _ehash_free(ss->vMap, (EHEntryFreeFP) _vert_free, ss);
 730                 _ehash_free(ss->eMap, (EHEntryFreeFP) _edge_free, ss);
 731                 _ehash_free(ss->fMap, (EHEntryFreeFP) _face_free, ss);
 732                 ss->vMap = _ehash_new(0, &ss->allocatorIFC, ss->allocator);
 733                 ss->eMap = _ehash_new(0, &ss->allocatorIFC, ss->allocator);
 734                 ss->fMap = _ehash_new(0, &ss->allocatorIFC, ss->allocator);
 735         }
 736
 737         return eCCGError_None;
 738 }
 739
 740 void ccgSubSurf_getUseAgeCounts(CCGSubSurf *ss, int *useAgeCounts_r, int *vertUserOffset_r, int *edgeUserOffset_r, int *faceUserOffset_r)
 741 {
 742         *useAgeCounts_r = ss->useAgeCounts;
 743
 744         if (vertUserOffset_r) *vertUserOffset_r = ss->vertUserAgeOffset;
 745         if (edgeUserOffset_r) *edgeUserOffset_r = ss->edgeUserAgeOffset;
 746         if (faceUserOffset_r) *faceUserOffset_r = ss->faceUserAgeOffset;
 747 }
 748
 749 CCGError ccgSubSurf_setUseAgeCounts(CCGSubSurf *ss, int useAgeCounts, int vertUserOffset, int edgeUserOffset, int faceUserOffset) {
 750         if (useAgeCounts) {
 751                 if (    (vertUserOffset+4>ss->meshIFC.vertUserSize) ||
 752                                 (edgeUserOffset+4>ss->meshIFC.edgeUserSize) ||
 753                                 (faceUserOffset+4>ss->meshIFC.faceUserSize)) {
 754                         return eCCGError_InvalidValue;
 755                 }  else {
 756                         ss->useAgeCounts = 1;
 757                         ss->vertUserAgeOffset = vertUserOffset;
 758                         ss->edgeUserAgeOffset = edgeUserOffset;
 759                         ss->faceUserAgeOffset = faceUserOffset;
 760                 }
 761         } else {
 762                 ss->useAgeCounts = 0;
 763                 ss->vertUserAgeOffset = ss->edgeUserAgeOffset = ss->faceUserAgeOffset = 0;
 764         }
 765
 766         return eCCGError_None;
 767 }
 768
 769 CCGError ccgSubSurf_setCalcVertexNormals(CCGSubSurf *ss, int useVertNormals, int normalDataOffset) {
 770         if (useVertNormals) {
 771                 if (normalDataOffset<0 || normalDataOffset+12>ss->meshIFC.vertDataSize) {
 772                         return eCCGError_InvalidValue;
 773                 } else {
 774                         ss->calcVertNormals = 1;
 775                         ss->normalDataOffset = normalDataOffset;
 776                 }
 777         } else {
 778                 ss->calcVertNormals = 0;
 779                 ss->normalDataOffset = 0;
 780         }
 781
 782         return eCCGError_None;
 783 }
 784
 785 /***/
 786
 787 CCGError ccgSubSurf_initFullSync(CCGSubSurf *ss) {
 788         if (ss->syncState!=eSyncState_None) {
 789                 return eCCGError_InvalidSyncState;
 790         }
 791
 792         ss->currentAge++;
 793
 794         ss->oldVMap = ss->vMap;
 795         ss->oldEMap = ss->eMap;
 796         ss->oldFMap = ss->fMap;
 797
 798         ss->vMap = _ehash_new(0, &ss->allocatorIFC, ss->allocator);
 799         ss->eMap = _ehash_new(0, &ss->allocatorIFC, ss->allocator);
 800         ss->fMap = _ehash_new(0, &ss->allocatorIFC, ss->allocator);
 801
 802         ss->numGrids = 0;
 803
 804         ss->lenTempArrays = 12;
 805         ss->tempVerts = CCGSUBSURF_alloc(ss, sizeof(*ss->tempVerts)*ss->lenTempArrays);
 806         ss->tempEdges = CCGSUBSURF_alloc(ss, sizeof(*ss->tempEdges)*ss->lenTempArrays);
 807
 808         ss->syncState = eSyncState_Vert;
 809
 810         return eCCGError_None;
 811 }
 812
 813 CCGError ccgSubSurf_initPartialSync(CCGSubSurf *ss) {
 814         if (ss->syncState!=eSyncState_None) {
 815                 return eCCGError_InvalidSyncState;
 816         }
 817
 818         ss->currentAge++;
 819
 820         ss->syncState = eSyncState_Partial;
 821
 822         return eCCGError_None;
 823 }
 824
 825 CCGError ccgSubSurf_syncVertDel(CCGSubSurf *ss, CCGVertHDL vHDL) {
 826         if (ss->syncState!=eSyncState_Partial) {
 827                 return eCCGError_InvalidSyncState;
 828         } else {
 829                 void **prevp;
 830                 CCGVert *v = _ehash_lookupWithPrev(ss->vMap, vHDL, &prevp);
 831
 832                 if (!v || v->numFaces || v->numEdges) {
 833                         return eCCGError_InvalidValue;
 834                 } else {
 835                         *prevp = v->next;
 836                         _vert_free(v, ss);
 837                 }
 838         }
 839
 840         return eCCGError_None;
 841 }
 842
 843 CCGError ccgSubSurf_syncEdgeDel(CCGSubSurf *ss, CCGEdgeHDL eHDL) {
 844         if (ss->syncState!=eSyncState_Partial) {
 845                 return eCCGError_InvalidSyncState;
 846         } else {
 847                 void **prevp;
 848                 CCGEdge *e = _ehash_lookupWithPrev(ss->eMap, eHDL, &prevp);
 849
 850                 if (!e || e->numFaces) {
 851                         return eCCGError_InvalidValue;
 852                 } else {
 853                         *prevp = e->next;
 854                         _edge_unlinkMarkAndFree(e, ss);
 855                 }
 856         }
 857
 858         return eCCGError_None;
 859 }
 860
 861 CCGError ccgSubSurf_syncFaceDel(CCGSubSurf *ss, CCGFaceHDL fHDL) {
 862         if (ss->syncState!=eSyncState_Partial) {
 863                 return eCCGError_InvalidSyncState;
 864         } else {
 865                 void **prevp;
 866                 CCGFace *f = _ehash_lookupWithPrev(ss->fMap, fHDL, &prevp);
 867
 868                 if (!f) {
 869                         return eCCGError_InvalidValue;
 870                 } else {
 871                         *prevp = f->next;
 872                         _face_unlinkMarkAndFree(f, ss);
 873                 }
 874         }
 875
 876         return eCCGError_None;
 877 }
 878
 879 CCGError ccgSubSurf_syncVert(CCGSubSurf *ss, CCGVertHDL vHDL, void *vertData, int seam, CCGVert **v_r) {
 880         void **prevp;
 881         CCGVert *v = NULL;
 882         short seamflag = (seam)? Vert_eSeam: 0;
 883
 884         if (ss->syncState==eSyncState_Partial) {
 885                 v = _ehash_lookupWithPrev(ss->vMap, vHDL, &prevp);
 886                 if (!v) {
 887                         v = _vert_new(vHDL, ss);
 888                         VertDataCopy(_vert_getCo(v,0,ss->meshIFC.vertDataSize), vertData);
 889                         _ehash_insert(ss->vMap, (EHEntry*) v);
 890                         v->flags = Vert_eEffected|seamflag;
 891                 } else if (!VertDataEqual(vertData, _vert_getCo(v, 0, ss->meshIFC.vertDataSize)) || ((v->flags & Vert_eSeam) != seamflag)) {
 892                         int i, j;
 893
 894                         VertDataCopy(_vert_getCo(v,0,ss->meshIFC.vertDataSize), vertData);
 895                         v->flags = Vert_eEffected|seamflag;
 896
 897                         for (i=0; i<v->numEdges; i++) {
 898                                 CCGEdge *e = v->edges[i];
 899                                 e->v0->flags |= Vert_eEffected;
 900                                 e->v1->flags |= Vert_eEffected;
 901                         }
 902                         for (i=0; i<v->numFaces; i++) {
 903                                 CCGFace *f = v->faces[i];
 904                                 for (j=0; j<f->numVerts; j++) {
 905                                         FACE_getVerts(f)[j]->flags |= Vert_eEffected;
 906                                 }
 907                         }
 908                 }
 909         } else {
 910                 if (ss->syncState!=eSyncState_Vert) {
 911                         return eCCGError_InvalidSyncState;
 912                 }
 913
 914                 v = _ehash_lookupWithPrev(ss->oldVMap, vHDL, &prevp);
 915                 if (!v) {
 916                         v = _vert_new(vHDL, ss);
 917                         VertDataCopy(_vert_getCo(v,0,ss->meshIFC.vertDataSize), vertData);
 918                         _ehash_insert(ss->vMap, (EHEntry*) v);
 919                         v->flags = Vert_eEffected|seamflag;
 920                 } else if (!VertDataEqual(vertData, _vert_getCo(v, 0, ss->meshIFC.vertDataSize)) || ((v->flags & Vert_eSeam) != seamflag)) {
 921                         *prevp = v->next;
 922                         _ehash_insert(ss->vMap, (EHEntry*) v);
 923                         VertDataCopy(_vert_getCo(v,0,ss->meshIFC.vertDataSize), vertData);
 924                         v->flags = Vert_eEffected|Vert_eChanged|seamflag;
 925                 } else {
 926                         *prevp = v->next;
 927                         _ehash_insert(ss->vMap, (EHEntry*) v);
 928                         v->flags = 0;
 929                 }
 930         }
 931
 932         if (v_r) *v_r = v;
 933         return eCCGError_None;
 934 }
 935
 936 CCGError ccgSubSurf_syncEdge(CCGSubSurf *ss, CCGEdgeHDL eHDL, CCGVertHDL e_vHDL0, CCGVertHDL e_vHDL1, float crease, CCGEdge **e_r) {
 937         void **prevp;
 938         CCGEdge *e = NULL, *eNew;
 939
 940         if (ss->syncState==eSyncState_Partial) {
 941                 e = _ehash_lookupWithPrev(ss->eMap, eHDL, &prevp);
 942                 if (!e || e->v0->vHDL!=e_vHDL0 || e->v1->vHDL!=e_vHDL1 || crease!=e->crease) {
 943                         CCGVert *v0 = _ehash_lookup(ss->vMap, e_vHDL0);
 944                         CCGVert *v1 = _ehash_lookup(ss->vMap, e_vHDL1);
 945
 946                         eNew = _edge_new(eHDL, v0, v1, crease, ss);
 947
 948                         if (e) {
 949                                 *prevp = eNew;
 950                                 eNew->next = e->next;
 951
 952                                 _edge_unlinkMarkAndFree(e, ss);
 953                         } else {
 954                                 _ehash_insert(ss->eMap, (EHEntry*) eNew);
 955                         }
 956
 957                         eNew->v0->flags |= Vert_eEffected;
 958                         eNew->v1->flags |= Vert_eEffected;
 959                 }
 960         } else {
 961                 if (ss->syncState==eSyncState_Vert) {
 962                         ss->syncState = eSyncState_Edge;
 963                 } else if (ss->syncState!=eSyncState_Edge) {
 964                         return eCCGError_InvalidSyncState;
 965                 }
 966
 967                 e = _ehash_lookupWithPrev(ss->oldEMap, eHDL, &prevp);
 968                 if (!e || e->v0->vHDL!=e_vHDL0 || e->v1->vHDL!=e_vHDL1|| e->crease!=crease) {
 969                         CCGVert *v0 = _ehash_lookup(ss->vMap, e_vHDL0);
 970                         CCGVert *v1 = _ehash_lookup(ss->vMap, e_vHDL1);
 971                         e = _edge_new(eHDL, v0, v1, crease, ss);
 972                         _ehash_insert(ss->eMap, (EHEntry*) e);
 973                         e->v0->flags |= Vert_eEffected;
 974                         e->v1->flags |= Vert_eEffected;
 975                 } else {
 976                         *prevp = e->next;
 977                         _ehash_insert(ss->eMap, (EHEntry*) e);
 978                         e->flags = 0;
 979                         if ((e->v0->flags|e->v1->flags)&Vert_eChanged) {
 980                                 e->v0->flags |= Vert_eEffected;
 981                                 e->v1->flags |= Vert_eEffected;
 982                         }
 983                 }
 984         }
 985
 986         if (e_r) *e_r = e;
 987         return eCCGError_None;
 988 }
 989
 990 CCGError ccgSubSurf_syncFace(CCGSubSurf *ss, CCGFaceHDL fHDL, int numVerts, CCGVertHDL *vHDLs, CCGFace **f_r) {
 991         void **prevp;
 992         CCGFace *f = NULL, *fNew;
 993         int j, k, topologyChanged = 0;
 994
 995         if (numVerts>ss->lenTempArrays) {
 996                 int oldLen = ss->lenTempArrays;
 997                 ss->lenTempArrays = (numVerts<ss->lenTempArrays*2)?ss->lenTempArrays*2:numVerts;
 998                 ss->tempVerts = CCGSUBSURF_realloc(ss, ss->tempVerts, sizeof(*ss->tempVerts)*ss->lenTempArrays, sizeof(*ss->tempVerts)*oldLen);
 999                 ss->tempEdges = CCGSUBSURF_realloc(ss, ss->tempEdges, sizeof(*ss->tempEdges)*ss->lenTempArrays, sizeof(*ss->tempEdges)*oldLen);
1000         }
1001
1002         if (ss->syncState==eSyncState_Partial) {
1003                 f = _ehash_lookupWithPrev(ss->fMap, fHDL, &prevp);
1004
1005                 for (k=0; k<numVerts; k++) {
1006                         ss->tempVerts[k] = _ehash_lookup(ss->vMap, vHDLs[k]);
1007                 }
1008                 for (k=0; k<numVerts; k++) {
1009                         ss->tempEdges[k] = _vert_findEdgeTo(ss->tempVerts[k], ss->tempVerts[(k+1)%numVerts]);
1010                 }
1011
1012                 if (f) {
1013                         if (    f->numVerts!=numVerts ||
1014                                         memcmp(FACE_getVerts(f), ss->tempVerts, sizeof(*ss->tempVerts)*numVerts) ||
1015                                         memcmp(FACE_getEdges(f), ss->tempEdges, sizeof(*ss->tempEdges)*numVerts))
1016                                 topologyChanged = 1;
1017                 }
1018
1019                 if (!f || topologyChanged) {
1020                         fNew = _face_new(fHDL, ss->tempVerts, ss->tempEdges, numVerts, ss);
1021
1022                         if (f) {
1023                                 ss->numGrids += numVerts - f->numVerts;
1024
1025                                 *prevp = fNew;
1026                                 fNew->next = f->next;
1027
1028                                 _face_unlinkMarkAndFree(f, ss);
1029                         } else {
1030                                 ss->numGrids += numVerts;
1031                                 _ehash_insert(ss->fMap, (EHEntry*) fNew);
1032                         }
1033
1034                         for (k=0; k<numVerts; k++)
1035                                 FACE_getVerts(fNew)[k]->flags |= Vert_eEffected;
1036                 }
1037         } else {
1038                 if (ss->syncState==eSyncState_Vert || ss->syncState==eSyncState_Edge) {
1039                         ss->syncState = eSyncState_Face;
1040                 } else if (ss->syncState!=eSyncState_Face) {
1041                         return eCCGError_InvalidSyncState;
1042                 }
1043
1044                 f = _ehash_lookupWithPrev(ss->oldFMap, fHDL, &prevp);
1045
1046                 for (k=0; k<numVerts; k++) {
1047                         ss->tempVerts[k] = _ehash_lookup(ss->vMap, vHDLs[k]);
1048
1049                         if (!ss->tempVerts[k])
1050                                 return eCCGError_InvalidValue;
1051                 }
1052                 for (k=0; k<numVerts; k++) {
1053                         ss->tempEdges[k] = _vert_findEdgeTo(ss->tempVerts[k], ss->tempVerts[(k+1)%numVerts]);
1054
1055                         if (!ss->tempEdges[k]) {
1056                                 if (ss->allowEdgeCreation) {
1057                                         CCGEdge *e = ss->tempEdges[k] = _edge_new((CCGEdgeHDL) -1, ss->tempVerts[k], ss->tempVerts[(k+1)%numVerts], ss->defaultCreaseValue, ss);
1058                                         _ehash_insert(ss->eMap, (EHEntry*) e);
1059                                         e->v0->flags |= Vert_eEffected;
1060                                         e->v1->flags |= Vert_eEffected;
1061                                         if (ss->meshIFC.edgeUserSize) {
1062                                                 memcpy(ccgSubSurf_getEdgeUserData(ss, e), ss->defaultEdgeUserData, ss->meshIFC.edgeUserSize);
1063                                         }
1064                                 } else {
1065                                         return eCCGError_InvalidValue;
1066                                 }
1067                         }
1068                 }
1069
1070                 if (f) {
1071                         if (    f->numVerts!=numVerts ||
1072                                         memcmp(FACE_getVerts(f), ss->tempVerts, sizeof(*ss->tempVerts)*numVerts) ||
1073                                         memcmp(FACE_getEdges(f), ss->tempEdges, sizeof(*ss->tempEdges)*numVerts))
1074                                 topologyChanged = 1;
1075                 }
1076
1077                 if (!f || topologyChanged) {
1078                         f = _face_new(fHDL, ss->tempVerts, ss->tempEdges, numVerts, ss);
1079                         _ehash_insert(ss->fMap, (EHEntry*) f);
1080                         ss->numGrids += numVerts;
1081
1082                         for (k=0; k<numVerts; k++)
1083                                 FACE_getVerts(f)[k]->flags |= Vert_eEffected;
1084                 } else {
1085                         *prevp = f->next;
1086                         _ehash_insert(ss->fMap, (EHEntry*) f);
1087                         f->flags = 0;
1088                         ss->numGrids += f->numVerts;
1089
1090                         for (j=0; j<f->numVerts; j++) {
1091                                 if (FACE_getVerts(f)[j]->flags&Vert_eChanged) {
1092                                         for (k=0; k<f->numVerts; k++)
1093                                                 FACE_getVerts(f)[k]->flags |= Vert_eEffected;
1094                                         break;
1095                                 }
1096                         }
1097                 }
1098         }
1099
1100         if (f_r) *f_r = f;
1101         return eCCGError_None;
1102 }
1103
1104 static void ccgSubSurf__sync(CCGSubSurf *ss);
1105 CCGError ccgSubSurf_processSync(CCGSubSurf *ss) {
1106         if (ss->syncState==eSyncState_Partial) {
1107                 ss->syncState = eSyncState_None;
1108
1109                 ccgSubSurf__sync(ss);
1110         } else if (ss->syncState) {
1111                 _ehash_free(ss->oldFMap, (EHEntryFreeFP) _face_unlinkMarkAndFree, ss);
1112                 _ehash_free(ss->oldEMap, (EHEntryFreeFP) _edge_unlinkMarkAndFree, ss);
1113                 _ehash_free(ss->oldVMap, (EHEntryFreeFP) _vert_free, ss);
1114                 CCGSUBSURF_free(ss, ss->tempEdges);
1115                 CCGSUBSURF_free(ss, ss->tempVerts);
1116
1117                 ss->lenTempArrays = 0;
1118
1119                 ss->oldFMap = ss->oldEMap = ss->oldVMap = NULL;
1120                 ss->tempVerts = NULL;
1121                 ss->tempEdges = NULL;
1122
1123                 ss->syncState = eSyncState_None;
1124
1125                 ccgSubSurf__sync(ss);
1126         } else {
1127                 return eCCGError_InvalidSyncState;
1128         }
1129
1130         return eCCGError_None;
1131 }
1132
1133 static void ccgSubSurf__sync(CCGSubSurf *ss) {
1134         CCGVert **effectedV;
1135         CCGEdge **effectedE;
1136         CCGFace **effectedF;
1137         int numEffectedV, numEffectedE, numEffectedF;
1138         int subdivLevels = ss->subdivLevels;
1139         int vertDataSize = ss->meshIFC.vertDataSize;
1140         int i,ptrIdx,cornerIdx;
1141         int S,x,y;
1142         void *q = ss->q, *r = ss->r;
1143         int curLvl, nextLvl;
1144         int j;
1145
1146         effectedV = CCGSUBSURF_alloc(ss, sizeof(*effectedV)*ss->vMap->numEntries);
1147         effectedE = CCGSUBSURF_alloc(ss, sizeof(*effectedE)*ss->eMap->numEntries);
1148         effectedF = CCGSUBSURF_alloc(ss, sizeof(*effectedF)*ss->fMap->numEntries);
1149         numEffectedV = numEffectedE = numEffectedF = 0;
1150         for (i=0; i<ss->vMap->curSize; i++) {
1151                 CCGVert *v = (CCGVert*) ss->vMap->buckets[i];
1152                 for (; v; v = v->next) {
1153                         if (v->flags&Vert_eEffected) {
1154                                 effectedV[numEffectedV++] = v;
1155
1156                                 for (j=0; j<v->numEdges; j++) {
1157                                         CCGEdge *e = v->edges[j];
1158                                         if (!(e->flags&Edge_eEffected)) {
1159                                                 effectedE[numEffectedE++] = e;
1160                                                 e->flags |= Edge_eEffected;
1161                                         }
1162                                 }
1163
1164                                 for (j=0; j<v->numFaces; j++) {
1165                                         CCGFace *f = v->faces[j];
1166                                         if (!(f->flags&Face_eEffected)) {
1167                                                 effectedF[numEffectedF++] = f;
1168                                                 f->flags |= Face_eEffected;
1169                                         }
1170                                 }
1171                         }
1172                 }
1173         }
1174
1175 #define VERT_getCo(v, lvl)                              _vert_getCo(v, lvl, vertDataSize)
1176 #define EDGE_getCo(e, lvl, x)                   _edge_getCo(e, lvl, x, vertDataSize)
1177 #define FACE_getIECo(f, lvl, S, x)              _face_getIECo(f, lvl, S, x, subdivLevels, vertDataSize)
1178 #define FACE_getIFCo(f, lvl, S, x, y)   _face_getIFCo(f, lvl, S, x, y, subdivLevels, vertDataSize)
1179         curLvl = 0;
1180         nextLvl = curLvl+1;
1181
1182         for (ptrIdx=0; ptrIdx<numEffectedF; ptrIdx++) {
1183                 CCGFace *f = effectedF[ptrIdx];
1184                 void *co = FACE_getCenterData(f);
1185                 VertDataZero(co);
1186                 for (i=0; i<f->numVerts; i++) {
1187                         VertDataAdd(co, VERT_getCo(FACE_getVerts(f)[i], curLvl));
1188                 }
1189                 VertDataMulN(co, 1.0f/f->numVerts);
1190
1191                 f->flags = 0;
1192         }
1193         for (ptrIdx=0; ptrIdx<numEffectedE; ptrIdx++) {
1194                 CCGEdge *e = effectedE[ptrIdx];
1195                 void *co = EDGE_getCo(e, nextLvl, 1);
1196                 float sharpness = EDGE_getSharpness(e, curLvl);
1197
1198                 if (_edge_isBoundary(e) || sharpness>=1.0) {
1199                         VertDataCopy(co, VERT_getCo(e->v0, curLvl));
1200                         VertDataAdd(co, VERT_getCo(e->v1, curLvl));
1201                         VertDataMulN(co, 0.5f);
1202                 } else {
1203                         int numFaces = 0;
1204                         VertDataCopy(q, VERT_getCo(e->v0, curLvl));
1205                         VertDataAdd(q, VERT_getCo(e->v1, curLvl));
1206                         for (i=0; i<e->numFaces; i++) {
1207                                 CCGFace *f = e->faces[i];
1208                                 VertDataAdd(q, FACE_getCenterData(f));
1209                                 numFaces++;
1210                         }
1211                         VertDataMulN(q, 1.0f/(2.0f+numFaces));
1212
1213                         VertDataCopy(r, VERT_getCo(e->v0, curLvl));
1214                         VertDataAdd(r, VERT_getCo(e->v1, curLvl));
1215                         VertDataMulN(r, 0.5f);
1216
1217                         VertDataCopy(co, q);
1218                         VertDataSub(r, q);
1219                         VertDataMulN(r, sharpness);
1220                         VertDataAdd(co, r);
1221                 }
1222
1223                 // edge flags cleared later
1224         }
1225         for (ptrIdx=0; ptrIdx<numEffectedV; ptrIdx++) {
1226                 CCGVert *v = effectedV[ptrIdx];
1227                 void *co = VERT_getCo(v, curLvl);
1228                 void *nCo = VERT_getCo(v, nextLvl);
1229                 int sharpCount = 0, allSharp = 1;
1230                 float avgSharpness = 0.0;
1231                 int seam = VERT_seam(v), seamEdges = 0;
1232
1233                 for (i=0; i<v->numEdges; i++) {
1234                         CCGEdge *e = v->edges[i];
1235                         float sharpness = EDGE_getSharpness(e, curLvl);
1236
1237                         if (seam && _edge_isBoundary(e))
1238                                 seamEdges++;
1239
1240                         if (sharpness!=0.0f) {
1241                                 sharpCount++;
1242                                 avgSharpness += sharpness;
1243                         } else {
1244                                 allSharp = 0;
1245                         }
1246                 }
1247
1248                 if(sharpCount) {
1249                         avgSharpness /= sharpCount;
1250                         if (avgSharpness>1.0) {
1251                                 avgSharpness = 1.0;
1252                         }
1253                 }
1254
1255                 if (seam && seamEdges < 2)
1256                         seam = 0;
1257
1258                 if (!v->numEdges) {
1259                         VertDataCopy(nCo, co);
1260                 } else if (_vert_isBoundary(v)) {
1261                         int numBoundary = 0;
1262
1263                         VertDataZero(r);
1264                         for (i=0; i<v->numEdges; i++) {
1265                                 CCGEdge *e = v->edges[i];
1266                                 if (_edge_isBoundary(e)) {
1267                                         VertDataAdd(r, VERT_getCo(_edge_getOtherVert(e, v), curLvl));
1268                                         numBoundary++;
1269                                 }
1270                         }
1271                         VertDataCopy(nCo, co);
1272                         VertDataMulN(nCo, 0.75);
1273                         VertDataMulN(r, 0.25f/numBoundary);
1274                         VertDataAdd(nCo, r);
1275                 } else {
1276                         int numEdges = 0, numFaces = 0;
1277
1278                         VertDataZero(q);
1279                         for (i=0; i<v->numFaces; i++) {
1280                                 CCGFace *f = v->faces[i];
1281                                 VertDataAdd(q, FACE_getCenterData(f));
1282                                 numFaces++;
1283                         }
1284                         VertDataMulN(q, 1.0f/numFaces);
1285                         VertDataZero(r);
1286                         for (i=0; i<v->numEdges; i++) {
1287                                 CCGEdge *e = v->edges[i];
1288                                 VertDataAdd(r, VERT_getCo(_edge_getOtherVert(e, v), curLvl));
1289                                 numEdges++;
1290                         }
1291                         VertDataMulN(r, 1.0f/numEdges);
1292
1293                         VertDataCopy(nCo, co);
1294                         VertDataMulN(nCo, numEdges-2.0f);
1295                         VertDataAdd(nCo, q);
1296                         VertDataAdd(nCo, r);
1297                         VertDataMulN(nCo, 1.0f/numEdges);
1298                 }
1299
1300                 if (sharpCount>1 || seam) {
1301                         VertDataZero(q);
1302
1303                         if (seam) {
1304                                 avgSharpness = 1.0f;
1305                                 sharpCount = seamEdges;
1306                                 allSharp = 1;
1307                         }
1308
1309                         for (i=0; i<v->numEdges; i++) {
1310                                 CCGEdge *e = v->edges[i];
1311                                 float sharpness = EDGE_getSharpness(e, curLvl);
1312
1313                                 if (seam) {
1314                                         if (_edge_isBoundary(e)) {
1315                                                 CCGVert *oV = _edge_getOtherVert(e, v);
1316                                                 VertDataAdd(q, VERT_getCo(oV, curLvl));
1317                                         }
1318                                 } else if (sharpness != 0.0) {
1319                                         CCGVert *oV = _edge_getOtherVert(e, v);
1320                                         VertDataAdd(q, VERT_getCo(oV, curLvl));
1321                                 }
1322                         }
1323
1324                         VertDataMulN(q, (float) 1/sharpCount);
1325
1326                         if (sharpCount!=2 || allSharp) {
1327                                         // q = q + (co-q)*avgSharpness
1328                                 VertDataCopy(r, co);
1329                                 VertDataSub(r, q);
1330                                 VertDataMulN(r, avgSharpness);
1331                                 VertDataAdd(q, r);
1332                         }
1333
1334                                 // r = co*.75 + q*.25
1335                         VertDataCopy(r, co);
1336                         VertDataMulN(r, .75);
1337                         VertDataMulN(q, .25);
1338                         VertDataAdd(r, q);
1339
1340                                 // nCo = nCo  + (r-nCo)*avgSharpness
1341                         VertDataSub(r, nCo);
1342                         VertDataMulN(r, avgSharpness);
1343                         VertDataAdd(nCo, r);
1344                 }
1345
1346                 // vert flags cleared later
1347         }
1348
1349         if (ss->useAgeCounts) {
1350                 for (i=0; i<numEffectedV; i++) {
1351                         CCGVert *v = effectedV[i];
1352                         byte *userData = ccgSubSurf_getVertUserData(ss, v);
1353                         *((int*) &userData[ss->vertUserAgeOffset]) = ss->currentAge;
1354                 }
1355
1356                 for (i=0; i<numEffectedE; i++) {
1357                         CCGEdge *e = effectedE[i];
1358                         byte *userData = ccgSubSurf_getEdgeUserData(ss, e);
1359                         *((int*) &userData[ss->edgeUserAgeOffset]) = ss->currentAge;
1360                 }
1361
1362                 for (i=0; i<numEffectedF; i++) {
1363                         CCGFace *f = effectedF[i];
1364                         byte *userData = ccgSubSurf_getFaceUserData(ss, f);
1365                         *((int*) &userData[ss->faceUserAgeOffset]) = ss->currentAge;
1366                 }
1367         }
1368
1369         for (i=0; i<numEffectedE; i++) {
1370                 CCGEdge *e = effectedE[i];
1371                 VertDataCopy(EDGE_getCo(e, nextLvl, 0), VERT_getCo(e->v0, nextLvl));
1372                 VertDataCopy(EDGE_getCo(e, nextLvl, 2), VERT_getCo(e->v1, nextLvl));
1373         }
1374         for (i=0; i<numEffectedF; i++) {
1375                 CCGFace *f = effectedF[i];
1376                 for (S=0; S<f->numVerts; S++) {
1377                         CCGEdge *e = FACE_getEdges(f)[S];
1378                         CCGEdge *prevE = FACE_getEdges(f)[(S+f->numVerts-1)%f->numVerts];
1379
1380                         VertDataCopy(FACE_getIFCo(f, nextLvl, S, 0, 0), FACE_getCenterData(f));
1381                         VertDataCopy(FACE_getIECo(f, nextLvl, S, 0), FACE_getCenterData(f));
1382                         VertDataCopy(FACE_getIFCo(f, nextLvl, S, 1, 1), VERT_getCo(FACE_getVerts(f)[S], nextLvl));
1383                         VertDataCopy(FACE_getIECo(f, nextLvl, S, 1), EDGE_getCo(FACE_getEdges(f)[S], nextLvl, 1));
1384
1385                         VertDataCopy(FACE_getIFCo(f, nextLvl, S, 1, 0), _edge_getCoVert(e, FACE_getVerts(f)[S], nextLvl, 1, vertDataSize));
1386                         VertDataCopy(FACE_getIFCo(f, nextLvl, S, 0, 1), _edge_getCoVert(prevE, FACE_getVerts(f)[S], nextLvl, 1, vertDataSize));
1387                 }
1388         }
1389
1390         for (curLvl=1; curLvl<subdivLevels; curLvl++) {
1391                 int edgeSize = 1 + (1<<curLvl);
1392                 int gridSize = 1 + (1<<(curLvl-1));
1393                 nextLvl = curLvl+1;
1394
1395                 for (ptrIdx=0; ptrIdx<numEffectedF; ptrIdx++) {
1396                         CCGFace *f = (CCGFace*) effectedF[ptrIdx];
1397
1398                                 /* interior face midpoints
1399                                  *  o old interior face points
1400                                  */
1401                         for (S=0; S<f->numVerts; S++) {
1402                                 for (y=0; y<gridSize-1; y++) {
1403                                         for (x=0; x<gridSize-1; x++) {
1404                                                 int fx = 1 + 2*x;
1405                                                 int fy = 1 + 2*y;
1406                                                 void *co0 = FACE_getIFCo(f, curLvl, S, x+0, y+0);
1407                                                 void *co1 = FACE_getIFCo(f, curLvl, S, x+1, y+0);
1408                                                 void *co2 = FACE_getIFCo(f, curLvl, S, x+1, y+1);
1409                                                 void *co3 = FACE_getIFCo(f, curLvl, S, x+0, y+1);
1410                                                 void *co = FACE_getIFCo(f, nextLvl, S, fx, fy);
1411
1412                                                 VertDataAvg4(co, co0, co1, co2, co3);
1413                                         }
1414                                 }
1415                         }
1416
1417                                 /* interior edge midpoints
1418                                  *  o old interior edge points
1419                                  *  o new interior face midpoints
1420                                  */
1421                         for (S=0; S<f->numVerts; S++) {
1422                                 for (x=0; x<gridSize-1; x++) {
1423                                         int fx = x*2 + 1;
1424                                         void *co0 = FACE_getIECo(f, curLvl, S, x+0);
1425                                         void *co1 = FACE_getIECo(f, curLvl, S, x+1);
1426                                         void *co2 = FACE_getIFCo(f, nextLvl, (S+1)%f->numVerts, 1, fx);
1427                                         void *co3 = FACE_getIFCo(f, nextLvl, S, fx, 1);
1428                                         void *co = FACE_getIECo(f, nextLvl, S, fx);
1429
1430                                         VertDataAvg4(co, co0, co1, co2, co3);
1431                                 }
1432
1433                                                 /* interior face interior edge midpoints
1434                                                  *  o old interior face points
1435                                                  *  o new interior face midpoints
1436                                                  */
1437
1438                                         /* vertical */
1439                                 for (x=1; x<gridSize-1; x++) {
1440                                         for (y=0; y<gridSize-1; y++) {
1441                                                 int fx = x*2;
1442                                                 int fy = y*2+1;
1443                                                 void *co0 = FACE_getIFCo(f, curLvl, S, x, y+0);
1444                                                 void *co1 = FACE_getIFCo(f, curLvl, S, x, y+1);
1445                                                 void *co2 = FACE_getIFCo(f, nextLvl, S, fx-1, fy);
1446                                                 void *co3 = FACE_getIFCo(f, nextLvl, S, fx+1, fy);
1447                                                 void *co = FACE_getIFCo(f, nextLvl, S, fx, fy);
1448
1449                                                 VertDataAvg4(co, co0, co1, co2, co3);
1450                                         }
1451                                 }
1452
1453                                         /* horizontal */
1454                                 for (y=1; y<gridSize-1; y++) {
1455                                         for (x=0; x<gridSize-1; x++) {
1456                                                 int fx = x*2+1;
1457                                                 int fy = y*2;
1458                                                 void *co0 = FACE_getIFCo(f, curLvl, S, x+0, y);
1459                                                 void *co1 = FACE_getIFCo(f, curLvl, S, x+1, y);
1460                                                 void *co2 = FACE_getIFCo(f, nextLvl, S, fx, fy-1);
1461                                                 void *co3 = FACE_getIFCo(f, nextLvl, S, fx, fy+1);
1462                                                 void *co = FACE_getIFCo(f, nextLvl, S, fx, fy);
1463
1464                                                 VertDataAvg4(co, co0, co1, co2, co3);
1465                                         }
1466                                 }
1467                         }
1468                 }
1469
1470                         /* exterior edge midpoints
1471                          *  o old exterior edge points
1472                          *  o new interior face midpoints
1473                          */
1474                 for (ptrIdx=0; ptrIdx<numEffectedE; ptrIdx++) {
1475                         CCGEdge *e = (CCGEdge*) effectedE[ptrIdx];
1476                         float sharpness = EDGE_getSharpness(e, curLvl);
1477
1478                         if (_edge_isBoundary(e) || sharpness>1.0) {
1479                                 for (x=0; x<edgeSize-1; x++) {
1480                                         int fx = x*2 + 1;
1481                                         void *co0 = EDGE_getCo(e, curLvl, x+0);
1482                                         void *co1 = EDGE_getCo(e, curLvl, x+1);
1483                                         void *co = EDGE_getCo(e, nextLvl, fx);
1484
1485                                         VertDataCopy(co, co0);
1486                                         VertDataAdd(co, co1);
1487                                         VertDataMulN(co, 0.5);
1488                                 }
1489                         } else {
1490                                 for (x=0; x<edgeSize-1; x++) {
1491                                         int fx = x*2 + 1;
1492                                         void *co0 = EDGE_getCo(e, curLvl, x+0);
1493                                         void *co1 = EDGE_getCo(e, curLvl, x+1);
1494                                         void *co = EDGE_getCo(e, nextLvl, fx);
1495                                         int numFaces = 0;
1496
1497                                         VertDataCopy(q, co0);
1498                                         VertDataAdd(q, co1);
1499
1500                                         for (i=0; i<e->numFaces; i++) {
1501                                                 CCGFace *f = e->faces[i];
1502                                                 VertDataAdd(q, _face_getIFCoEdge(f, e, nextLvl, fx, 1, subdivLevels, vertDataSize));
1503                                                 numFaces++;
1504                                         }
1505
1506                                         VertDataMulN(q, 1.0f/(2.0f+numFaces));
1507
1508                                         VertDataCopy(r, co0);
1509                                         VertDataAdd(r, co1);
1510                                         VertDataMulN(r, 0.5);
1511
1512                                         VertDataCopy(co, q);
1513                                         VertDataSub(r, q);
1514                                         VertDataMulN(r, sharpness);
1515                                         VertDataAdd(co, r);
1516                                 }
1517                         }
1518                 }
1519
1520                         /* exterior vertex shift
1521                          *  o old vertex points (shifting)
1522                          *  o old exterior edge points
1523                          *  o new interior face midpoints
1524                          */
1525                 for (ptrIdx=0; ptrIdx<numEffectedV; ptrIdx++) {
1526                         CCGVert *v = (CCGVert*) effectedV[ptrIdx];
1527                         void *co = VERT_getCo(v, curLvl);
1528                         void *nCo = VERT_getCo(v, nextLvl);
1529                         int sharpCount = 0, allSharp = 1;
1530                         float avgSharpness = 0.0;
1531                         int seam = VERT_seam(v), seamEdges = 0;
1532
1533                         for (i=0; i<v->numEdges; i++) {
1534                                 CCGEdge *e = v->edges[i];
1535                                 float sharpness = EDGE_getSharpness(e, curLvl);
1536
1537                                 if (seam && _edge_isBoundary(e))
1538                                         seamEdges++;
1539
1540                                 if (sharpness!=0.0f) {
1541                                         sharpCount++;
1542                                         avgSharpness += sharpness;
1543                                 } else {
1544                                         allSharp = 0;
1545                                 }
1546                         }
1547
1548                         if(sharpCount) {
1549                                 avgSharpness /= sharpCount;
1550                                 if (avgSharpness>1.0) {
1551                                         avgSharpness = 1.0;
1552                                 }
1553                         }
1554
1555                         if (seam && seamEdges < 2)
1556                                 seam = 0;
1557
1558                         if (!v->numEdges) {
1559                                 VertDataCopy(nCo, co);
1560                         } else if (_vert_isBoundary(v)) {
1561                                 int numBoundary = 0;
1562
1563                                 VertDataZero(r);
1564                                 for (i=0; i<v->numEdges; i++) {
1565                                         CCGEdge *e = v->edges[i];
1566                                         if (_edge_isBoundary(e)) {
1567                                                 VertDataAdd(r, _edge_getCoVert(e, v, curLvl, 1, vertDataSize));
1568                                                 numBoundary++;
1569                                         }
1570                                 }
1571
1572                                 VertDataCopy(nCo, co);
1573                                 VertDataMulN(nCo, 0.75);
1574                                 VertDataMulN(r, 0.25f/numBoundary);
1575                                 VertDataAdd(nCo, r);
1576                         } else {
1577                                 int cornerIdx = (1 + (1<<(curLvl))) - 2;
1578                                 int numEdges = 0, numFaces = 0;
1579
1580                                 VertDataZero(q);
1581                                 for (i=0; i<v->numFaces; i++) {
1582                                         CCGFace *f = v->faces[i];
1583                                         VertDataAdd(q, FACE_getIFCo(f, nextLvl, _face_getVertIndex(f,v), cornerIdx, cornerIdx));
1584                                         numFaces++;
1585                                 }
1586                                 VertDataMulN(q, 1.0f/numFaces);
1587                                 VertDataZero(r);
1588                                 for (i=0; i<v->numEdges; i++) {
1589                                         CCGEdge *e = v->edges[i];
1590                                         VertDataAdd(r, _edge_getCoVert(e, v, curLvl, 1,vertDataSize));
1591                                         numEdges++;
1592                                 }
1593                                 VertDataMulN(r, 1.0f/numEdges);
1594
1595                                 VertDataCopy(nCo, co);
1596                                 VertDataMulN(nCo, numEdges-2.0f);
1597                                 VertDataAdd(nCo, q);
1598                                 VertDataAdd(nCo, r);
1599                                 VertDataMulN(nCo, 1.0f/numEdges);
1600                         }
1601
1602                         if ((sharpCount>1 && v->numFaces) || seam) {
1603                                 VertDataZero(q);
1604
1605                                 if (seam) {
1606                                         avgSharpness = 1.0f;
1607                                         sharpCount = seamEdges;
1608                                         allSharp = 1;
1609                                 }
1610
1611                                 for (i=0; i<v->numEdges; i++) {
1612                                         CCGEdge *e = v->edges[i];
1613                                         float sharpness = EDGE_getSharpness(e, curLvl);
1614
1615                                         if (seam) {
1616                                                 if (_edge_isBoundary(e))
1617                                                         VertDataAdd(q, _edge_getCoVert(e, v, curLvl, 1, vertDataSize));
1618                                         } else if (sharpness != 0.0) {
1619                                                 VertDataAdd(q, _edge_getCoVert(e, v, curLvl, 1, vertDataSize));
1620                                         }
1621                                 }
1622
1623                                 VertDataMulN(q, (float) 1/sharpCount);
1624
1625                                 if (sharpCount!=2 || allSharp) {
1626                                                 // q = q + (co-q)*avgSharpness
1627                                         VertDataCopy(r, co);
1628                                         VertDataSub(r, q);
1629                                         VertDataMulN(r, avgSharpness);
1630                                         VertDataAdd(q, r);
1631                                 }
1632
1633                                         // r = co*.75 + q*.25
1634                                 VertDataCopy(r, co);
1635                                 VertDataMulN(r, .75);
1636                                 VertDataMulN(q, .25);
1637                                 VertDataAdd(r, q);
1638
1639                                         // nCo = nCo  + (r-nCo)*avgSharpness
1640                                 VertDataSub(r, nCo);
1641                                 VertDataMulN(r, avgSharpness);
1642                                 VertDataAdd(nCo, r);
1643                         }
1644                 }
1645
1646                         /* exterior edge interior shift
1647                          *  o old exterior edge midpoints (shifting)
1648                          *  o old exterior edge midpoints
1649                          *  o new interior face midpoints
1650                          */
1651                 for (ptrIdx=0; ptrIdx<numEffectedE; ptrIdx++) {
1652                         CCGEdge *e = (CCGEdge*) effectedE[ptrIdx];
1653                         float sharpness = EDGE_getSharpness(e, curLvl);
1654                         int sharpCount = 0;
1655                         float avgSharpness = 0.0;
1656
1657                         if (sharpness!=0.0f) {
1658                                 sharpCount = 2;
1659                                 avgSharpness += sharpness;
1660
1661                                 if (avgSharpness>1.0) {
1662                                         avgSharpness = 1.0;
1663                                 }
1664                         } else {
1665                                 sharpCount = 0;
1666                                 avgSharpness = 0;
1667                         }
1668
1669                         if (_edge_isBoundary(e) && (!e->numFaces || sharpCount<2)) {
1670                                 for (x=1; x<edgeSize-1; x++) {
1671                                         int fx = x*2;
1672                                         void *co = EDGE_getCo(e, curLvl, x);
1673                                         void *nCo = EDGE_getCo(e, nextLvl, fx);
1674                                         VertDataCopy(r, EDGE_getCo(e, curLvl, x-1));
1675                                         VertDataAdd(r, EDGE_getCo(e, curLvl, x+1));
1676                                         VertDataMulN(r, 0.5);
1677                                         VertDataCopy(nCo, co);
1678                                         VertDataMulN(nCo, 0.75);
1679                                         VertDataMulN(r, 0.25);
1680                                         VertDataAdd(nCo, r);
1681                                 }
1682                         } else {
1683                                 for (x=1; x<edgeSize-1; x++) {
1684                                         int fx = x*2;
1685                                         void *co = EDGE_getCo(e, curLvl, x);
1686                                         void *nCo = EDGE_getCo(e, nextLvl, fx);
1687                                         int numFaces = 0;
1688
1689                                         VertDataZero(q);
1690                                         VertDataZero(r);
1691                                         VertDataAdd(r, EDGE_getCo(e, curLvl, x-1));
1692                                         VertDataAdd(r, EDGE_getCo(e, curLvl, x+1));
1693                                         for (i=0; i<e->numFaces; i++) {
1694                                                 CCGFace *f = e->faces[i];
1695                                                 VertDataAdd(q, _face_getIFCoEdge(f, e, nextLvl, fx-1, 1, subdivLevels, vertDataSize));
1696                                                 VertDataAdd(q, _face_getIFCoEdge(f, e, nextLvl, fx+1, 1, subdivLevels, vertDataSize));
1697
1698                                                 VertDataAdd(r, _face_getIFCoEdge(f, e, curLvl, x, 1, subdivLevels, vertDataSize));
1699                                                 numFaces++;
1700                                         }
1701                                         VertDataMulN(q, 1.0/(numFaces*2.0f));
1702                                         VertDataMulN(r, 1.0/(2.0f + numFaces));
1703
1704                                         VertDataCopy(nCo, co);
1705                                         VertDataMulN(nCo, (float) numFaces);
1706                                         VertDataAdd(nCo, q);
1707                                         VertDataAdd(nCo, r);
1708                                         VertDataMulN(nCo, 1.0f/(2+numFaces));
1709
1710                                         if (sharpCount==2) {
1711                                                 VertDataCopy(q, co);
1712                                                 VertDataMulN(q, 6.0f);
1713                                                 VertDataAdd(q, EDGE_getCo(e, curLvl, x-1));
1714                                                 VertDataAdd(q, EDGE_getCo(e, curLvl, x+1));
1715                                                 VertDataMulN(q, 1/8.0f);
1716
1717                                                 VertDataSub(q, nCo);
1718                                                 VertDataMulN(q, avgSharpness);
1719                                                 VertDataAdd(nCo, q);
1720                                         }
1721                                 }
1722                         }
1723                 }
1724
1725                 for (ptrIdx=0; ptrIdx<numEffectedF; ptrIdx++) {
1726                         CCGFace *f = (CCGFace*) effectedF[ptrIdx];
1727
1728                                 /* interior center point shift
1729                                  *  o old face center point (shifting)
1730                                  *  o old interior edge points
1731                                  *  o new interior face midpoints
1732                                  */
1733                         VertDataZero(q);
1734                         for (S=0; S<f->numVerts; S++) {
1735                                 VertDataAdd(q, FACE_getIFCo(f, nextLvl, S, 1, 1));
1736                         }
1737                         VertDataMulN(q, 1.0f/f->numVerts);
1738                         VertDataZero(r);
1739                         for (S=0; S<f->numVerts; S++) {
1740                                 VertDataAdd(r, FACE_getIECo(f, curLvl, S, 1));
1741                         }
1742                         VertDataMulN(r, 1.0f/f->numVerts);
1743
1744                         VertDataMulN(FACE_getCenterData(f), f->numVerts-2.0f);
1745                         VertDataAdd(FACE_getCenterData(f), q);
1746                         VertDataAdd(FACE_getCenterData(f), r);
1747                         VertDataMulN(FACE_getCenterData(f), 1.0f/f->numVerts);
1748
1749                         for (S=0; S<f->numVerts; S++) {
1750                                         /* interior face shift
1751                                          *  o old interior face point (shifting)
1752                                          *  o new interior edge midpoints
1753                                          *  o new interior face midpoints
1754                                          */
1755                                 for (x=1; x<gridSize-1; x++) {
1756                                         for (y=1; y<gridSize-1; y++) {
1757                                                 int fx = x*2;
1758                                                 int fy = y*2;
1759                                                 void *co = FACE_getIFCo(f, curLvl, S, x, y);
1760                                                 void *nCo = FACE_getIFCo(f, nextLvl, S, fx, fy);
1761
1762                                                 VertDataAvg4(q, FACE_getIFCo(f, nextLvl, S, fx-1, fy-1),
1763                                                         FACE_getIFCo(f, nextLvl, S, fx+1, fy-1),
1764                                                         FACE_getIFCo(f, nextLvl, S, fx+1, fy+1),
1765                                                         FACE_getIFCo(f, nextLvl, S, fx-1, fy+1));
1766
1767                                                 VertDataAvg4(r, FACE_getIFCo(f, nextLvl, S, fx-1, fy+0),
1768                                                         FACE_getIFCo(f, nextLvl, S, fx+1, fy+0),
1769                                                         FACE_getIFCo(f, nextLvl, S, fx+0, fy-1),
1770                                                         FACE_getIFCo(f, nextLvl, S, fx+0, fy+1));
1771
1772                                                 VertDataCopy(nCo, co);
1773                                                 VertDataSub(nCo, q);
1774                                                 VertDataMulN(nCo, 0.25f);
1775                                                 VertDataAdd(nCo, r);
1776                                         }
1777                                 }
1778
1779                                         /* interior edge interior shift
1780                                          *  o old interior edge point (shifting)
1781                                          *  o new interior edge midpoints
1782                                          *  o new interior face midpoints
1783                                          */
1784                                 for (x=1; x<gridSize-1; x++) {
1785                                         int fx = x*2;
1786                                         void *co = FACE_getIECo(f, curLvl, S, x);
1787                                         void *nCo = FACE_getIECo(f, nextLvl, S, fx);
1788
1789                                         VertDataAvg4(q, FACE_getIFCo(f, nextLvl, (S+1)%f->numVerts, 1, fx-1),
1790                                                 FACE_getIFCo(f, nextLvl, (S+1)%f->numVerts, 1, fx+1),
1791                                                 FACE_getIFCo(f, nextLvl, S, fx+1, +1),
1792                                                 FACE_getIFCo(f, nextLvl, S, fx-1, +1));
1793
1794                                         VertDataAvg4(r, FACE_getIECo(f, nextLvl, S, fx-1),
1795                                                 FACE_getIECo(f, nextLvl, S, fx+1),
1796                                                 FACE_getIFCo(f, nextLvl, (S+1)%f->numVerts, 1, fx),
1797                                                 FACE_getIFCo(f, nextLvl, S, fx, 1));
1798
1799                                         VertDataCopy(nCo, co);
1800                                         VertDataSub(nCo, q);
1801                                         VertDataMulN(nCo, 0.25f);
1802                                         VertDataAdd(nCo, r);
1803                                 }
1804                         }
1805                 }
1806
1807                         /* copy down */
1808                 edgeSize = 1 + (1<<(nextLvl));
1809                 gridSize = 1 + (1<<((nextLvl)-1));
1810                 cornerIdx = gridSize-1;
1811                 for (i=0; i<numEffectedE; i++) {
1812                         CCGEdge *e = effectedE[i];
1813                         VertDataCopy(EDGE_getCo(e, nextLvl, 0), VERT_getCo(e->v0, nextLvl));
1814                         VertDataCopy(EDGE_getCo(e, nextLvl, edgeSize-1), VERT_getCo(e->v1, nextLvl));
1815                 }
1816                 for (i=0; i<numEffectedF; i++) {
1817                         CCGFace *f = effectedF[i];
1818                         for (S=0; S<f->numVerts; S++) {
1819                                 CCGEdge *e = FACE_getEdges(f)[S];
1820                                 CCGEdge *prevE = FACE_getEdges(f)[(S+f->numVerts-1)%f->numVerts];
1821
1822                                 VertDataCopy(FACE_getIFCo(f, nextLvl, S, 0, 0), FACE_getCenterData(f));
1823                                 VertDataCopy(FACE_getIECo(f, nextLvl, S, 0), FACE_getCenterData(f));
1824                                 VertDataCopy(FACE_getIFCo(f, nextLvl, S, cornerIdx, cornerIdx), VERT_getCo(FACE_getVerts(f)[S], nextLvl));
1825                                 VertDataCopy(FACE_getIECo(f, nextLvl, S, cornerIdx), EDGE_getCo(FACE_getEdges(f)[S], nextLvl, cornerIdx));
1826                                 for (x=1; x<gridSize-1; x++) {
1827                                         void *co = FACE_getIECo(f, nextLvl, S, x);
1828                                         VertDataCopy(FACE_getIFCo(f, nextLvl, S, x, 0), co);
1829                                         VertDataCopy(FACE_getIFCo(f, nextLvl, (S+1)%f->numVerts, 0, x), co);
1830                                 }
1831                                 for (x=0; x<gridSize-1; x++) {
1832                                         int eI = gridSize-1-x;
1833                                         VertDataCopy(FACE_getIFCo(f, nextLvl, S, cornerIdx, x), _edge_getCoVert(e, FACE_getVerts(f)[S], nextLvl, eI,vertDataSize));
1834                                         VertDataCopy(FACE_getIFCo(f, nextLvl, S, x, cornerIdx), _edge_getCoVert(prevE, FACE_getVerts(f)[S], nextLvl, eI,vertDataSize));
1835                                 }
1836                         }
1837                 }
1838         }
1839
1840 #define FACE_getIFNo(f, lvl, S, x, y)           _face_getIFNo(f, lvl, S, x, y, subdivLevels, vertDataSize, normalDataOffset)
1841 #define FACE_calcIFNo(f, lvl, S, x, y, no)      _face_calcIFNo(f, lvl, S, x, y, no, subdivLevels, vertDataSize)
1842         if (ss->calcVertNormals) {
1843                 int lvl = ss->subdivLevels;
1844                 int edgeSize = 1 + (1<<lvl);
1845                 int gridSize = 1 + (1<<(lvl-1));
1846                 int normalDataOffset = ss->normalDataOffset;
1847
1848                 for (ptrIdx=0; ptrIdx<numEffectedF; ptrIdx++) {
1849                         CCGFace *f = (CCGFace*) effectedF[ptrIdx];
1850                         int S, x, y;
1851
1852                         for (S=0; S<f->numVerts; S++) {
1853                                 for (y=0; y<gridSize-1; y++)
1854                                         for (x=0; x<gridSize-1; x++)
1855                                                 NormZero(FACE_getIFNo(f, lvl, S, x, y));
1856
1857                                 if (FACE_getEdges(f)[(S-1+f->numVerts)%f->numVerts]->flags&Edge_eEffected)
1858                                         for (x=0; x<gridSize-1; x++)
1859                                                 NormZero(FACE_getIFNo(f, lvl, S, x, gridSize-1));
1860                                 if (FACE_getEdges(f)[S]->flags&Edge_eEffected)
1861                                         for (y=0; y<gridSize-1; y++)
1862                                                 NormZero(FACE_getIFNo(f, lvl, S, gridSize-1, y));
1863                                 if (FACE_getVerts(f)[S]->flags&Vert_eEffected)
1864                                         NormZero(FACE_getIFNo(f, lvl, S, gridSize-1, gridSize-1));
1865                         }
1866                 }
1867
1868                 for (ptrIdx=0; ptrIdx<numEffectedF; ptrIdx++) {
1869                         CCGFace *f = (CCGFace*) effectedF[ptrIdx];
1870                         int S, x, y;
1871                         float no[3];
1872
1873                         for (S=0; S<f->numVerts; S++) {
1874                                 int yLimit = !(FACE_getEdges(f)[(S-1+f->numVerts)%f->numVerts]->flags&Edge_eEffected);
1875                                 int xLimit = !(FACE_getEdges(f)[S]->flags&Edge_eEffected);
1876                                 int yLimitNext = xLimit;
1877                                 int xLimitPrev = yLimit;
1878
1879                                 for (y=0; y<gridSize - 1; y++) {
1880                                         for (x=0; x<gridSize - 1; x++) {
1881                                                 int xPlusOk = (!xLimit || x<gridSize-2);
1882                                                 int yPlusOk = (!yLimit || y<gridSize-2);
1883
1884                                                 FACE_calcIFNo(f, lvl, S, x, y, no);
1885
1886                                                 NormAdd(FACE_getIFNo(f, lvl, S, x+0, y+0), no);
1887                                                 if (xPlusOk)
1888                                                         NormAdd(FACE_getIFNo(f, lvl, S, x+1, y+0), no);
1889                                                 if (yPlusOk)
1890                                                         NormAdd(FACE_getIFNo(f, lvl, S, x+0, y+1), no);
1891                                                 if (xPlusOk && yPlusOk) {
1892                                                         if (x<gridSize-2 || y<gridSize-2 || FACE_getVerts(f)[S]->flags&Vert_eEffected) {
1893                                                                 NormAdd(FACE_getIFNo(f, lvl, S, x+1, y+1), no);
1894                                                         }
1895                                                 }
1896
1897                                                 if (x==0 && y==0) {
1898                                                         int K;
1899
1900                                                         if (!yLimitNext || 1<gridSize-1)
1901                                                                 NormAdd(FACE_getIFNo(f, lvl, (S+1)%f->numVerts, 0, 1), no);
1902                                                         if (!xLimitPrev || 1<gridSize-1)
1903                                                                 NormAdd(FACE_getIFNo(f, lvl, (S-1+f->numVerts)%f->numVerts, 1, 0), no);
1904
1905                                                         for (K=0; K<f->numVerts; K++) {
1906                                                                 if (K!=S) {
1907                                                                         NormAdd(FACE_getIFNo(f, lvl, K, 0, 0), no);
1908                                                                 }
1909                                                         }
1910                                                 } else if (y==0) {
1911                                                         NormAdd(FACE_getIFNo(f, lvl, (S+1)%f->numVerts, 0, x), no);
1912                                                         if (!yLimitNext || x<gridSize-2)
1913                                                                 NormAdd(FACE_getIFNo(f, lvl, (S+1)%f->numVerts, 0, x+1), no);
1914                                                 } else if (x==0) {
1915                                                         NormAdd(FACE_getIFNo(f, lvl, (S-1+f->numVerts)%f->numVerts, y, 0), no);
1916                                                         if (!xLimitPrev || y<gridSize-2)
1917                                                                 NormAdd(FACE_getIFNo(f, lvl, (S-1+f->numVerts)%f->numVerts, y+1, 0), no);
1918                                                 }
1919                                         }
1920                                 }
1921                         }
1922                 }
1923                         // XXX can I reduce the number of normalisations here?
1924                 for (ptrIdx=0; ptrIdx<numEffectedV; ptrIdx++) {
1925                         CCGVert *v = (CCGVert*) effectedV[ptrIdx];
1926                         float length, *no = _vert_getNo(v, lvl, vertDataSize, normalDataOffset);
1927
1928                         NormZero(no);
1929
1930                         for (i=0; i<v->numFaces; i++) {
1931                                 CCGFace *f = v->faces[i];
1932                                 NormAdd(no, FACE_getIFNo(f, lvl, _face_getVertIndex(f,v), gridSize-1, gridSize-1));
1933                         }
1934
1935                         length = sqrt(no[0]*no[0] + no[1]*no[1] + no[2]*no[2]);
1936
1937                         if (length>FLT_EPSILON) {
1938                                 float invLength = 1.0f/length;
1939                                 no[0] *= invLength;
1940                                 no[1] *= invLength;
1941                                 no[2] *= invLength;
1942                         } else {
1943                                 NormZero(no);
1944                         }
1945
1946                         for (i=0; i<v->numFaces; i++) {
1947                                 CCGFace *f = v->faces[i];
1948                                 NormCopy(FACE_getIFNo(f, lvl, _face_getVertIndex(f,v), gridSize-1, gridSize-1), no);
1949                         }
1950                 }
1951                 for (ptrIdx=0; ptrIdx<numEffectedE; ptrIdx++) {
1952                         CCGEdge *e = (CCGEdge*) effectedE[ptrIdx];
1953
1954                         if (e->numFaces) {
1955                                 CCGFace *fLast = e->faces[e->numFaces-1];
1956                                 int x;
1957
1958                                 for (i=0; i<e->numFaces-1; i++) {
1959                                         CCGFace *f = e->faces[i];
1960
1961                                         for (x=1; x<edgeSize-1; x++) {
1962                                                 NormAdd(_face_getIFNoEdge(fLast, e, lvl, x, 0, subdivLevels, vertDataSize, normalDataOffset),
1963                                                                 _face_getIFNoEdge(f, e, lvl, x, 0, subdivLevels, vertDataSize, normalDataOffset));
1964                                         }
1965                                 }
1966
1967                                 for (i=0; i<e->numFaces-1; i++) {
1968                                         CCGFace *f = e->faces[i];
1969
1970                                         for (x=1; x<edgeSize-1; x++) {
1971                                                 NormCopy(_face_getIFNoEdge(f, e, lvl, x, 0, subdivLevels, vertDataSize, normalDataOffset),
1972                                                                 _face_getIFNoEdge(fLast, e, lvl, x, 0, subdivLevels, vertDataSize, normalDataOffset));
1973                                         }
1974                                 }
1975                         }
1976                 }
1977                 for (ptrIdx=0; ptrIdx<numEffectedF; ptrIdx++) {
1978                         CCGFace *f = (CCGFace*) effectedF[ptrIdx];
1979                         int S;
1980
1981                         for (S=0; S<f->numVerts; S++) {
1982                                 NormCopy(FACE_getIFNo(f, lvl, (S+1)%f->numVerts, 0, gridSize-1),
1983                                                  FACE_getIFNo(f, lvl, S, gridSize-1, 0));
1984                         }
1985                 }
1986                 for (ptrIdx=0; ptrIdx<numEffectedF; ptrIdx++) {
1987                         CCGFace *f = (CCGFace*) effectedF[ptrIdx];
1988                         int S, x, y;
1989
1990                         for (S=0; S<f->numVerts; S++) {
1991                                 for (y=0; y<gridSize; y++) {
1992                                         for (x=0; x<gridSize; x++) {
1993                                                 float *no = FACE_getIFNo(f, lvl, S, x, y);
1994                                                 float length = sqrt(no[0]*no[0] + no[1]*no[1] + no[2]*no[2]);
1995
1996                                                 if (length>FLT_EPSILON) {
1997                                                         float invLength = 1.0f/length;
1998                                                         no[0] *= invLength;
1999                                                         no[1] *= invLength;
2000                                                         no[2] *= invLength;
2001                                                 } else {
2002                                                         NormZero(no);
2003                                                 }
2004                                         }
2005                                 }
2006                         }
2007                 }
2008         }
2009 #undef FACE_getIFNo
2010
2011         for (ptrIdx=0; ptrIdx<numEffectedV; ptrIdx++) {
2012                 CCGVert *v = effectedV[ptrIdx];
2013                 v->flags = 0;
2014         }
2015         for (ptrIdx=0; ptrIdx<numEffectedE; ptrIdx++) {
2016                 CCGEdge *e = effectedE[ptrIdx];
2017                 e->flags = 0;
2018         }
2019
2020 #undef VERT_getCo
2021 #undef EDGE_getCo
2022 #undef FACE_getIECo
2023 #undef FACE_getIFCo
2024
2025         CCGSUBSURF_free(ss, effectedF);
2026         CCGSUBSURF_free(ss, effectedE);
2027         CCGSUBSURF_free(ss, effectedV);
2028 }
2029
2030 /*** External API accessor functions ***/
2031
2032 int ccgSubSurf_getNumVerts(CCGSubSurf *ss) {
2033         return ss->vMap->numEntries;
2034 }
2035 int ccgSubSurf_getNumEdges(CCGSubSurf *ss) {
2036         return ss->eMap->numEntries;
2037 }
2038 int ccgSubSurf_getNumFaces(CCGSubSurf *ss) {
2039         return ss->fMap->numEntries;
2040 }
2041
2042 CCGVert *ccgSubSurf_getVert(CCGSubSurf *ss, CCGVertHDL v) {
2043         return (CCGVert*) _ehash_lookup(ss->vMap, v);
2044 }
2045 CCGEdge *ccgSubSurf_getEdge(CCGSubSurf *ss, CCGEdgeHDL e) {
2046         return (CCGEdge*) _ehash_lookup(ss->eMap, e);
2047 }
2048 CCGFace *ccgSubSurf_getFace(CCGSubSurf *ss, CCGFaceHDL f) {
2049         return (CCGFace*) _ehash_lookup(ss->fMap, f);
2050 }
2051
2052 int ccgSubSurf_getSubdivisionLevels(CCGSubSurf *ss) {
2053         return ss->subdivLevels;
2054 }
2055 int ccgSubSurf_getEdgeSize(CCGSubSurf *ss) {
2056         return ccgSubSurf_getEdgeLevelSize(ss, ss->subdivLevels);
2057 }
2058 int ccgSubSurf_getEdgeLevelSize(CCGSubSurf *ss, int level) {
2059         if (level<1 || level>ss->subdivLevels) {
2060                 return -1;
2061         } else {
2062                 return 1 + (1<<level);
2063         }
2064 }
2065 int ccgSubSurf_getGridSize(CCGSubSurf *ss) {
2066         return ccgSubSurf_getGridLevelSize(ss, ss->subdivLevels);
2067 }
2068 int ccgSubSurf_getGridLevelSize(CCGSubSurf *ss, int level) {
2069         if (level<1 || level>ss->subdivLevels) {
2070                 return -1;
2071         } else {
2072                 return 1 + (1<<(level-1));
2073         }
2074 }
2075
2076 /* Vert accessors */
2077
2078 CCGVertHDL ccgSubSurf_getVertVertHandle(CCGVert *v) {
2079         return v->vHDL;
2080 }
2081 int ccgSubSurf_getVertAge(CCGSubSurf *ss, CCGVert *v) {
2082         if (ss->useAgeCounts) {
2083                 byte *userData = ccgSubSurf_getVertUserData(ss, v);
2084                 return ss->currentAge - *((int*) &userData[ss->vertUserAgeOffset]);
2085         } else {
2086                 return 0;
2087         }
2088 }
2089 void *ccgSubSurf_getVertUserData(CCGSubSurf *ss, CCGVert *v) {
2090         return VERT_getLevelData(v) + ss->meshIFC.vertDataSize*(ss->subdivLevels+1);
2091 }
2092 int ccgSubSurf_getVertNumFaces(CCGVert *v) {
2093         return v->numFaces;
2094 }
2095 CCGFace *ccgSubSurf_getVertFace(CCGVert *v, int index) {
2096         if (index<0 || index>=v->numFaces) {
2097                 return NULL;
2098         } else {
2099                 return v->faces[index];
2100         }
2101 }
2102 int ccgSubSurf_getVertNumEdges(CCGVert *v) {
2103         return v->numEdges;
2104 }
2105 CCGEdge *ccgSubSurf_getVertEdge(CCGVert *v, int index) {
2106         if (index<0 || index>=v->numEdges) {
2107                 return NULL;
2108         } else {
2109                 return v->edges[index];
2110         }
2111 }
2112 void *ccgSubSurf_getVertData(CCGSubSurf *ss, CCGVert *v) {
2113         return ccgSubSurf_getVertLevelData(ss, v, ss->subdivLevels);
2114 }
2115 void *ccgSubSurf_getVertLevelData(CCGSubSurf *ss, CCGVert *v, int level) {
2116         if (level<0 || level>ss->subdivLevels) {
2117                 return NULL;
2118         } else {
2119                 return _vert_getCo(v, level, ss->meshIFC.vertDataSize);
2120         }
2121 }
2122
2123 /* Edge accessors */
2124
2125 CCGEdgeHDL ccgSubSurf_getEdgeEdgeHandle(CCGEdge *e) {
2126         return e->eHDL;
2127 }
2128 int ccgSubSurf_getEdgeAge(CCGSubSurf *ss, CCGEdge *e) {
2129         if (ss->useAgeCounts) {
2130                 byte *userData = ccgSubSurf_getEdgeUserData(ss, e);
2131                 return ss->currentAge - *((int*) &userData[ss->edgeUserAgeOffset]);
2132         } else {
2133                 return 0;
2134         }
2135 }
2136 void *ccgSubSurf_getEdgeUserData(CCGSubSurf *ss, CCGEdge *e) {
2137         return EDGE_getLevelData(e) + ss->meshIFC.vertDataSize *((ss->subdivLevels+1) + (1<<(ss->subdivLevels+1))-1);
2138 }
2139 int ccgSubSurf_getEdgeNumFaces(CCGEdge *e) {
2140         return e->numFaces;
2141 }
2142 CCGFace *ccgSubSurf_getEdgeFace(CCGEdge *e, int index) {
2143         if (index<0 || index>=e->numFaces) {
2144                 return NULL;
2145         } else {
2146                 return e->faces[index];
2147         }
2148 }
2149 CCGVert *ccgSubSurf_getEdgeVert0(CCGEdge *e) {
2150         return e->v0;
2151 }
2152 CCGVert *ccgSubSurf_getEdgeVert1(CCGEdge *e) {
2153         return e->v1;
2154 }
2155 void *ccgSubSurf_getEdgeDataArray(CCGSubSurf *ss, CCGEdge *e) {
2156         return ccgSubSurf_getEdgeData(ss, e, 0);
2157 }
2158 void *ccgSubSurf_getEdgeData(CCGSubSurf *ss, CCGEdge *e, int x) {
2159         return ccgSubSurf_getEdgeLevelData(ss, e, x, ss->subdivLevels);
2160 }
2161 void *ccgSubSurf_getEdgeLevelData(CCGSubSurf *ss, CCGEdge *e, int x, int level) {
2162         if (level<0 || level>ss->subdivLevels) {
2163                 return NULL;
2164         } else {
2165                 return _edge_getCo(e, level, x, ss->meshIFC.vertDataSize);
2166         }
2167 }
2168 float ccgSubSurf_getEdgeCrease(CCGEdge *e) {
2169         return e->crease;
2170 }
2171
2172 /* Face accessors */
2173
2174 CCGFaceHDL ccgSubSurf_getFaceFaceHandle(CCGSubSurf *ss, CCGFace *f) {
2175         return f->fHDL;
2176 }
2177 int ccgSubSurf_getFaceAge(CCGSubSurf *ss, CCGFace *f) {
2178         if (ss->useAgeCounts) {
2179                 byte *userData = ccgSubSurf_getFaceUserData(ss, f);
2180                 return ss->currentAge - *((int*) &userData[ss->faceUserAgeOffset]);
2181         } else {
2182                 return 0;
2183         }
2184 }
2185 void *ccgSubSurf_getFaceUserData(CCGSubSurf *ss, CCGFace *f) {
2186         int maxGridSize = 1 + (1<<(ss->subdivLevels-1));
2187         return FACE_getCenterData(f) + ss->meshIFC.vertDataSize *(1 + f->numVerts*maxGridSize + f->numVerts*maxGridSize*maxGridSize);
2188 }
2189 int ccgSubSurf_getFaceNumVerts(CCGFace *f) {
2190         return f->numVerts;
2191 }
2192 CCGVert *ccgSubSurf_getFaceVert(CCGSubSurf *ss, CCGFace *f, int index) {
2193         if (index<0 || index>=f->numVerts) {
2194                 return NULL;
2195         } else {
2196                 return FACE_getVerts(f)[index];
2197         }
2198 }
2199 CCGEdge *ccgSubSurf_getFaceEdge(CCGSubSurf *ss, CCGFace *f, int index) {
2200         if (index<0 || index>=f->numVerts) {
2201                 return NULL;
2202         } else {
2203                 return FACE_getEdges(f)[index];
2204         }
2205 }
2206 int ccgSubSurf_getFaceEdgeIndex(CCGFace *f, CCGEdge *e) {
2207         int i;
2208
2209         for (i=0; i<f->numVerts; i++)
2210                 if (FACE_getEdges(f)[i]==e)
2211                         return i;
2212
2213         return -1;
2214 }
2215 void *ccgSubSurf_getFaceCenterData(CCGFace *f) {
2216         return FACE_getCenterData(f);
2217 }
2218 void *ccgSubSurf_getFaceGridEdgeDataArray(CCGSubSurf *ss, CCGFace *f, int gridIndex) {
2219         return ccgSubSurf_getFaceGridEdgeData(ss, f, gridIndex, 0);
2220 }
2221 void *ccgSubSurf_getFaceGridEdgeData(CCGSubSurf *ss, CCGFace *f, int gridIndex, int x) {
2222         return _face_getIECo(f, ss->subdivLevels, gridIndex, x, ss->subdivLevels, ss->meshIFC.vertDataSize);
2223 }
2224 void *ccgSubSurf_getFaceGridDataArray(CCGSubSurf *ss, CCGFace *f, int gridIndex) {
2225         return ccgSubSurf_getFaceGridData(ss, f, gridIndex, 0, 0);
2226 }
2227 void *ccgSubSurf_getFaceGridData(CCGSubSurf *ss, CCGFace *f, int gridIndex, int x, int y) {
2228         return _face_getIFCo(f, ss->subdivLevels, gridIndex, x, y, ss->subdivLevels, ss->meshIFC.vertDataSize);
2229 }
2230
2231 /*** External API iterator functions ***/
2232
2233 CCGVertIterator *ccgSubSurf_getVertIterator(CCGSubSurf *ss) {
2234         return (CCGVertIterator*) _ehashIterator_new(ss->vMap);
2235 }
2236 CCGEdgeIterator *ccgSubSurf_getEdgeIterator(CCGSubSurf *ss) {
2237         return (CCGEdgeIterator*) _ehashIterator_new(ss->eMap);
2238 }
2239 CCGFaceIterator *ccgSubSurf_getFaceIterator(CCGSubSurf *ss) {
2240         return (CCGFaceIterator*) _ehashIterator_new(ss->fMap);
2241 }
2242
2243 CCGVert *ccgVertIterator_getCurrent(CCGVertIterator *vi) {
2244         return (CCGVert*) _ehashIterator_getCurrent((EHashIterator*) vi);
2245 }
2246 int ccgVertIterator_isStopped(CCGVertIterator *vi) {
2247         return _ehashIterator_isStopped((EHashIterator*) vi);
2248 }
2249 void ccgVertIterator_next(CCGVertIterator *vi) {
2250         _ehashIterator_next((EHashIterator*) vi);
2251 }
2252 void ccgVertIterator_free(CCGVertIterator *vi) {
2253         _ehashIterator_free((EHashIterator*) vi);
2254 }
2255
2256 CCGEdge *ccgEdgeIterator_getCurrent(CCGEdgeIterator *vi) {
2257         return (CCGEdge*) _ehashIterator_getCurrent((EHashIterator*) vi);
2258 }
2259 int ccgEdgeIterator_isStopped(CCGEdgeIterator *vi) {
2260         return _ehashIterator_isStopped((EHashIterator*) vi);
2261 }
2262 void ccgEdgeIterator_next(CCGEdgeIterator *vi) {
2263         _ehashIterator_next((EHashIterator*) vi);
2264 }
2265 void ccgEdgeIterator_free(CCGEdgeIterator *vi) {
2266         _ehashIterator_free((EHashIterator*) vi);
2267 }
2268
2269 CCGFace *ccgFaceIterator_getCurrent(CCGFaceIterator *vi) {
2270         return (CCGFace*) _ehashIterator_getCurrent((EHashIterator*) vi);
2271 }
2272 int ccgFaceIterator_isStopped(CCGFaceIterator *vi) {
2273         return _ehashIterator_isStopped((EHashIterator*) vi);
2274 }
2275 void ccgFaceIterator_next(CCGFaceIterator *vi) {
2276         _ehashIterator_next((EHashIterator*) vi);
2277 }
2278 void ccgFaceIterator_free(CCGFaceIterator *vi) {
2279         _ehashIterator_free((EHashIterator*) vi);
2280 }
2281
2282 /*** Extern API final vert/edge/face interface ***/
2283
2284 int ccgSubSurf_getNumFinalVerts(CCGSubSurf *ss) {
2285         int edgeSize = 1 + (1<<ss->subdivLevels);
2286         int gridSize = 1 + (1<<(ss->subdivLevels-1));
2287         int numFinalVerts = ss->vMap->numEntries + ss->eMap->numEntries*(edgeSize-2) + ss->fMap->numEntries + ss->numGrids*((gridSize-2) + ((gridSize-2)*(gridSize-2)));
2288         return numFinalVerts;
2289 }
2290 int ccgSubSurf_getNumFinalEdges(CCGSubSurf *ss) {
2291         int edgeSize = 1 + (1<<ss->subdivLevels);
2292         int gridSize = 1 + (1<<(ss->subdivLevels-1));
2293         int numFinalEdges = ss->eMap->numEntries*(edgeSize-1) + ss->numGrids*((gridSize-1) + 2*((gridSize-2)*(gridSize-1)));
2294         return numFinalEdges;
2295 }
2296 int ccgSubSurf_getNumFinalFaces(CCGSubSurf *ss) {
2297         int gridSize = 1 + (1<<(ss->subdivLevels-1));
2298         int numFinalFaces = ss->numGrids*((gridSize-1)*(gridSize-1));
2299         return numFinalFaces;
2300 }