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