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