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