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