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