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