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