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