constraints unique name length was set too long (could overrun the buffer), use sizeo...
[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 "MEM_guardedalloc.h"
10 #include "BLO_sys_types.h" // for intptr_t support
11
12 #ifdef _MSC_VER
13 #define CCG_INLINE __inline
14 #else
15 #define CCG_INLINE inline
16 #endif
17
18 /* used for normalize_v3 in BLI_math_vector
19  * float.h's FLT_EPSILON causes trouble with subsurf normals - campbell */
20 #define EPSILON (1.0e-35f)
21
22 /***/
23
24 typedef unsigned char   byte;
25
26 /***/
27
28 static int kHashSizes[] = {
29         1, 3, 5, 11, 17, 37, 67, 131, 257, 521, 1031, 2053, 4099, 8209, 
30         16411, 32771, 65537, 131101, 262147, 524309, 1048583, 2097169, 
31         4194319, 8388617, 16777259, 33554467, 67108879, 134217757, 268435459
32 };
33
34 typedef struct _EHEntry EHEntry;
35 struct _EHEntry {
36         EHEntry *next;
37         void *key;
38 };
39 typedef struct _EHash {
40         EHEntry **buckets;
41         int numEntries, curSize, curSizeIdx;
42
43         CCGAllocatorIFC allocatorIFC;
44         CCGAllocatorHDL allocator;
45 } EHash;
46
47 #define EHASH_alloc(eh, nb)                     ((eh)->allocatorIFC.alloc((eh)->allocator, nb))
48 #define EHASH_free(eh, ptr)                     ((eh)->allocatorIFC.free((eh)->allocator, ptr))
49
50 #define EHASH_hash(eh, item)    (((uintptr_t) (item))%((unsigned int) (eh)->curSize))
51
52 static EHash *_ehash_new(int estimatedNumEntries, CCGAllocatorIFC *allocatorIFC, CCGAllocatorHDL allocator) {
53         EHash *eh = allocatorIFC->alloc(allocator, sizeof(*eh));
54         eh->allocatorIFC = *allocatorIFC;
55         eh->allocator = allocator;
56         eh->numEntries = 0;
57         eh->curSizeIdx = 0;
58         while (kHashSizes[eh->curSizeIdx]<estimatedNumEntries)
59                 eh->curSizeIdx++;
60         eh->curSize = kHashSizes[eh->curSizeIdx];
61         eh->buckets = EHASH_alloc(eh, eh->curSize*sizeof(*eh->buckets));
62         memset(eh->buckets, 0, eh->curSize*sizeof(*eh->buckets));
63
64         return eh;
65 }
66 typedef void (*EHEntryFreeFP)(EHEntry *, void *);
67 static void _ehash_free(EHash *eh, EHEntryFreeFP freeEntry, void *userData) {
68         int numBuckets = eh->curSize;
69
70         while (numBuckets--) {
71                 EHEntry *entry = eh->buckets[numBuckets];
72
73                 while (entry) {
74                         EHEntry *next = entry->next;
75
76                         freeEntry(entry, userData);
77
78                         entry = next;
79                 }
80         }
81
82         EHASH_free(eh, eh->buckets);
83         EHASH_free(eh, eh);
84 }
85
86 static void _ehash_insert(EHash *eh, EHEntry *entry) {
87         int numBuckets = eh->curSize;
88         int hash = EHASH_hash(eh, entry->key);
89         entry->next = eh->buckets[hash];
90         eh->buckets[hash] = entry;
91         eh->numEntries++;
92
93         if (eh->numEntries > (numBuckets*3)) {
94                 EHEntry **oldBuckets = eh->buckets;
95                 eh->curSize = kHashSizes[++eh->curSizeIdx];
96                 
97                 eh->buckets = EHASH_alloc(eh, eh->curSize*sizeof(*eh->buckets));
98                 memset(eh->buckets, 0, eh->curSize*sizeof(*eh->buckets));
99
100                 while (numBuckets--) {
101                         for (entry = oldBuckets[numBuckets]; entry;) {
102                                 EHEntry *next = entry->next;
103                                 
104                                 hash = EHASH_hash(eh, entry->key);
105                                 entry->next = eh->buckets[hash];
106                                 eh->buckets[hash] = entry;
107                                 
108                                 entry = next;
109                         }
110                 }
111
112                 EHASH_free(eh, oldBuckets);
113         }
114 }
115
116 static void *_ehash_lookupWithPrev(EHash *eh, void *key, void ***prevp_r) {
117         int hash = EHASH_hash(eh, key);
118         void **prevp = (void**) &eh->buckets[hash];
119         EHEntry *entry;
120         
121         for (; (entry = *prevp); prevp = (void**) &entry->next) {
122                 if (entry->key==key) {
123                         *prevp_r = (void**) prevp;
124                         return entry;
125                 }
126         }
127         
128         return NULL;
129 }
130
131 static void *_ehash_lookup(EHash *eh, void *key) {
132         int hash = EHASH_hash(eh, key);
133         EHEntry *entry;
134         
135         for (entry = eh->buckets[hash]; entry; entry = entry->next)
136                 if (entry->key==key)
137                         break;
138         
139         return entry;
140 }
141
142 /**/
143
144 typedef struct _EHashIterator {
145         EHash *eh;
146         int curBucket;
147         EHEntry *curEntry;
148 } EHashIterator;
149
150 static EHashIterator *_ehashIterator_new(EHash *eh) {
151         EHashIterator *ehi = EHASH_alloc(eh, sizeof(*ehi));
152         ehi->eh = eh;
153         ehi->curEntry = NULL;
154         ehi->curBucket = -1;
155         while (!ehi->curEntry) {
156                 ehi->curBucket++;
157                 if (ehi->curBucket==ehi->eh->curSize)
158                         break;
159                 ehi->curEntry = ehi->eh->buckets[ehi->curBucket];
160         }
161         return ehi;
162 }
163 static void _ehashIterator_free(EHashIterator *ehi) {
164         EHASH_free(ehi->eh, ehi);
165 }
166
167 static void *_ehashIterator_getCurrent(EHashIterator *ehi) {
168         return ehi->curEntry;
169 }
170
171 static void _ehashIterator_next(EHashIterator *ehi) {
172         if (ehi->curEntry) {
173         ehi->curEntry = ehi->curEntry->next;
174                 while (!ehi->curEntry) {
175                         ehi->curBucket++;
176                         if (ehi->curBucket==ehi->eh->curSize)
177                                 break;
178                         ehi->curEntry = ehi->eh->buckets[ehi->curBucket];
179                 }
180         }
181 }
182 static int _ehashIterator_isStopped(EHashIterator *ehi) {
183         return !ehi->curEntry;
184 }
185
186 /***/
187
188 static void *_stdAllocator_alloc(CCGAllocatorHDL a, int numBytes) {
189         return malloc(numBytes);
190 }
191 static void *_stdAllocator_realloc(CCGAllocatorHDL a, void *ptr, int newSize, int oldSize) {
192         return realloc(ptr, newSize);
193 }
194 static void _stdAllocator_free(CCGAllocatorHDL a, void *ptr) {
195         free(ptr);
196 }
197
198 static CCGAllocatorIFC *_getStandardAllocatorIFC(void) {
199         static CCGAllocatorIFC ifc;
200
201         ifc.alloc = _stdAllocator_alloc;
202         ifc.realloc = _stdAllocator_realloc;
203         ifc.free = _stdAllocator_free;
204         ifc.release = NULL;
205
206         return &ifc;
207 }
208
209 /***/
210
211 static int VertDataEqual(float *a, float *b) {
212         return a[0]==b[0] && a[1]==b[1] && a[2]==b[2];
213 }
214 #define VertDataZero(av)                                { float *_a = (float*) av; _a[0] = _a[1] = _a[2] = 0.0f; }
215 #define VertDataCopy(av, bv)                    { float *_a = (float*) av, *_b = (float*) bv; _a[0] =_b[0]; _a[1] =_b[1]; _a[2] =_b[2]; }
216 #define VertDataAdd(av, bv)                             { float *_a = (float*) av, *_b = (float*) bv; _a[0]+=_b[0]; _a[1]+=_b[1]; _a[2]+=_b[2]; }
217 #define VertDataSub(av, bv)                             { float *_a = (float*) av, *_b = (float*) bv; _a[0]-=_b[0]; _a[1]-=_b[1]; _a[2]-=_b[2]; }
218 #define VertDataMulN(av, n)                             { float *_a = (float*) av; _a[0]*=n; _a[1]*=n; _a[2]*=n; }
219 #define VertDataAvg4(tv, av, bv, cv, dv) \
220         { \
221                 float *_t = (float*) tv, *_a = (float*) av, *_b = (float*) bv, *_c = (float*) cv, *_d = (float*) dv; \
222                 _t[0] = (_a[0]+_b[0]+_c[0]+_d[0])*.25; \
223                 _t[1] = (_a[1]+_b[1]+_c[1]+_d[1])*.25; \
224                 _t[2] = (_a[2]+_b[2]+_c[2]+_d[2])*.25; \
225         }
226 #define NormZero(av)                                    { float *_a = (float*) av; _a[0] = _a[1] = _a[2] = 0.0f; }
227 #define NormCopy(av, bv)                                { float *_a = (float*) av, *_b = (float*) bv; _a[0] =_b[0]; _a[1] =_b[1]; _a[2] =_b[2]; }
228 #define NormAdd(av, bv)                                 { float *_a = (float*) av, *_b = (float*) bv; _a[0]+=_b[0]; _a[1]+=_b[1]; _a[2]+=_b[2]; }
229
230
231 static int _edge_isBoundary(CCGEdge *e);
232
233 /***/
234
235 enum {
236         Vert_eEffected=         (1<<0),
237         Vert_eChanged=          (1<<1),
238         Vert_eSeam=                     (1<<2),
239 } VertFlags;
240 enum {
241         Edge_eEffected=         (1<<0),
242 } CCGEdgeFlags;
243 enum {
244         Face_eEffected=         (1<<0),
245 } FaceFlags;
246
247 struct _CCGVert {
248         CCGVert         *next;  /* EHData.next */
249         CCGVertHDL      vHDL;   /* EHData.key */
250
251         short numEdges, numFaces, flags, pad;
252
253         CCGEdge **edges;
254         CCGFace **faces;
255 //      byte *levelData;
256 //      byte *userData;
257 };
258 #define VERT_getLevelData(v)            ((byte*) &(v)[1])
259
260 struct _CCGEdge {
261         CCGEdge         *next;  /* EHData.next */
262         CCGEdgeHDL      eHDL;   /* EHData.key */
263
264         short numFaces, flags;
265         float crease;
266
267         CCGVert *v0,*v1;
268         CCGFace **faces;
269
270 //      byte *levelData;
271 //      byte *userData;
272 };
273 #define EDGE_getLevelData(e)            ((byte*) &(e)[1])
274
275 struct _CCGFace {
276         CCGFace         *next;  /* EHData.next */
277         CCGFaceHDL      fHDL;   /* EHData.key */
278
279         short numVerts, flags, pad1, pad2;
280
281 //      CCGVert **verts;
282 //      CCGEdge **edges;
283 //      byte *centerData;
284 //      byte **gridData;
285 //      byte *userData;
286 };
287 #define FACE_getVerts(f)                ((CCGVert**) &(f)[1])
288 #define FACE_getEdges(f)                ((CCGEdge**) &(FACE_getVerts(f)[(f)->numVerts]))
289 #define FACE_getCenterData(f)   ((byte*) &(FACE_getEdges(f)[(f)->numVerts]))
290
291 typedef enum {
292         eSyncState_None = 0,
293         eSyncState_Vert,
294         eSyncState_Edge,
295         eSyncState_Face,
296         eSyncState_Partial,
297 } SyncState;
298
299 struct _CCGSubSurf {
300         EHash *vMap;    /* map of CCGVertHDL -> Vert */
301         EHash *eMap;    /* map of CCGEdgeHDL -> Edge */
302         EHash *fMap;    /* map of CCGFaceHDL -> Face */
303
304         CCGMeshIFC meshIFC;
305         
306         CCGAllocatorIFC allocatorIFC;
307         CCGAllocatorHDL allocator;
308
309         int subdivLevels;
310         int numGrids;
311         int allowEdgeCreation;
312         float defaultCreaseValue;
313         void *defaultEdgeUserData;
314
315         void *q, *r;
316                 
317                 // data for calc vert normals
318         int calcVertNormals;
319         int normalDataOffset;
320
321                 // data for age'ing (to debug sync)
322         int currentAge;
323         int useAgeCounts;
324         int vertUserAgeOffset;
325         int edgeUserAgeOffset;
326         int faceUserAgeOffset;
327
328                 // data used during syncing
329         SyncState syncState;
330
331         EHash *oldVMap, *oldEMap, *oldFMap;
332         int lenTempArrays;
333         CCGVert **tempVerts;
334         CCGEdge **tempEdges;
335 };
336
337 #define CCGSUBSURF_alloc(ss, nb)                        ((ss)->allocatorIFC.alloc((ss)->allocator, nb))
338 #define CCGSUBSURF_realloc(ss, ptr, nb, ob)     ((ss)->allocatorIFC.realloc((ss)->allocator, ptr, nb, ob))
339 #define CCGSUBSURF_free(ss, ptr)                        ((ss)->allocatorIFC.free((ss)->allocator, ptr))
340
341 /***/
342
343 static CCGVert *_vert_new(CCGVertHDL vHDL, CCGSubSurf *ss) {
344         CCGVert *v = CCGSUBSURF_alloc(ss, sizeof(CCGVert) + ss->meshIFC.vertDataSize * (ss->subdivLevels+1) + ss->meshIFC.vertUserSize);
345         byte *userData;
346
347         v->vHDL = vHDL;
348         v->edges = NULL;
349         v->faces = NULL;
350         v->numEdges = v->numFaces = 0;
351         v->flags = 0;
352
353         userData = ccgSubSurf_getVertUserData(ss, v);
354         memset(userData, 0, ss->meshIFC.vertUserSize);
355         if (ss->useAgeCounts) *((int*) &userData[ss->vertUserAgeOffset]) = ss->currentAge;
356
357         return v;
358 }
359 static void _vert_remEdge(CCGVert *v, CCGEdge *e) {
360         int i;
361         for (i=0; i<v->numEdges; i++) {
362                 if (v->edges[i]==e) {
363                         v->edges[i] = v->edges[--v->numEdges];
364                         break;
365                 }
366         }
367 }
368 static void _vert_remFace(CCGVert *v, CCGFace *f) {
369         int i;
370         for (i=0; i<v->numFaces; i++) {
371                 if (v->faces[i]==f) {
372                         v->faces[i] = v->faces[--v->numFaces];
373                         break;
374                 }
375         }
376 }
377 static void _vert_addEdge(CCGVert *v, CCGEdge *e, CCGSubSurf *ss) {
378         v->edges = CCGSUBSURF_realloc(ss, v->edges, (v->numEdges+1)*sizeof(*v->edges), v->numEdges*sizeof(*v->edges));
379         v->edges[v->numEdges++] = e;
380 }
381 static void _vert_addFace(CCGVert *v, CCGFace *f, CCGSubSurf *ss) {
382         v->faces = CCGSUBSURF_realloc(ss, v->faces, (v->numFaces+1)*sizeof(*v->faces), v->numFaces*sizeof(*v->faces));
383         v->faces[v->numFaces++] = f;
384 }
385 static CCGEdge *_vert_findEdgeTo(CCGVert *v, CCGVert *vQ) {
386         int i;
387         for (i=0; i<v->numEdges; i++) {
388                 CCGEdge *e = v->edges[v->numEdges-1-i]; // XXX, note reverse
389                 if (    (e->v0==v && e->v1==vQ) ||
390                                 (e->v1==v && e->v0==vQ))
391                         return e;
392         }
393         return 0;
394 }
395 static int _vert_isBoundary(CCGVert *v) {
396         int i;
397         for (i=0; i<v->numEdges; i++)
398                 if (_edge_isBoundary(v->edges[i]))
399                         return 1;
400         return 0;
401 }
402
403 static void *_vert_getCo(CCGVert *v, int lvl, int dataSize) {
404         return &VERT_getLevelData(v)[lvl*dataSize];
405 }
406 static float *_vert_getNo(CCGVert *v, int lvl, int dataSize, int normalDataOffset) {
407         return (float*) &VERT_getLevelData(v)[lvl*dataSize + normalDataOffset];
408 }
409
410 static void _vert_free(CCGVert *v, CCGSubSurf *ss) {
411         CCGSUBSURF_free(ss, v->edges);
412         CCGSUBSURF_free(ss, v->faces);
413         CCGSUBSURF_free(ss, v);
414 }
415
416 static int VERT_seam(CCGVert *v) {
417         return ((v->flags & Vert_eSeam) != 0);
418 }
419
420 /***/
421
422 static CCGEdge *_edge_new(CCGEdgeHDL eHDL, CCGVert *v0, CCGVert *v1, float crease, CCGSubSurf *ss) {
423         CCGEdge *e = CCGSUBSURF_alloc(ss, sizeof(CCGEdge) + ss->meshIFC.vertDataSize *((ss->subdivLevels+1) + (1<<(ss->subdivLevels+1))-1) + ss->meshIFC.edgeUserSize);
424         byte *userData;
425
426         e->eHDL = eHDL;
427         e->v0 = v0;
428         e->v1 = v1;
429         e->crease = crease;
430         e->faces = NULL;
431         e->numFaces = 0;
432         e->flags = 0;
433         _vert_addEdge(v0, e, ss);
434         _vert_addEdge(v1, e, ss);
435
436         userData = ccgSubSurf_getEdgeUserData(ss, e);
437         memset(userData, 0, ss->meshIFC.edgeUserSize);
438         if (ss->useAgeCounts) *((int*) &userData[ss->edgeUserAgeOffset]) = ss->currentAge;
439
440         return e;
441 }
442 static void _edge_remFace(CCGEdge *e, CCGFace *f) {
443         int i;
444         for (i=0; i<e->numFaces; i++) {
445                 if (e->faces[i]==f) {
446                         e->faces[i] = e->faces[--e->numFaces];
447                         break;
448                 }
449         }
450 }
451 static void _edge_addFace(CCGEdge *e, CCGFace *f, CCGSubSurf *ss) {
452         e->faces = CCGSUBSURF_realloc(ss, e->faces, (e->numFaces+1)*sizeof(*e->faces), e->numFaces*sizeof(*e->faces));
453         e->faces[e->numFaces++] = f;
454 }
455 static int _edge_isBoundary(CCGEdge *e) {
456         return e->numFaces<2;
457 }
458
459 static CCGVert *_edge_getOtherVert(CCGEdge *e, CCGVert *vQ) {
460         if (vQ==e->v0) {
461                 return e->v1;
462         } else {
463                 return e->v0;
464         }
465 }
466
467 static void *_edge_getCo(CCGEdge *e, int lvl, int x, int dataSize) {
468         int levelBase = lvl + (1<<lvl) - 1;
469         return &EDGE_getLevelData(e)[dataSize*(levelBase + x)];
470 }
471 static float *_edge_getNo(CCGEdge *e, int lvl, int x, int dataSize, int normalDataOffset) {
472         int levelBase = lvl + (1<<lvl) - 1;
473         return (float*) &EDGE_getLevelData(e)[dataSize*(levelBase + x) + normalDataOffset];
474 }
475 static void *_edge_getCoVert(CCGEdge *e, CCGVert *v, int lvl, int x, int dataSize) {
476         int levelBase = lvl + (1<<lvl) - 1;
477         if (v==e->v0) {
478                 return &EDGE_getLevelData(e)[dataSize*(levelBase + x)];
479         } else {
480                 return &EDGE_getLevelData(e)[dataSize*(levelBase + (1<<lvl) - x)];              
481         }
482 }
483
484 static void _edge_free(CCGEdge *e, CCGSubSurf *ss) {
485         CCGSUBSURF_free(ss, e->faces);
486         CCGSUBSURF_free(ss, e);
487 }
488 static void _edge_unlinkMarkAndFree(CCGEdge *e, CCGSubSurf *ss) {
489         _vert_remEdge(e->v0, e);
490         _vert_remEdge(e->v1, e);
491         e->v0->flags |= Vert_eEffected;
492         e->v1->flags |= Vert_eEffected;
493         _edge_free(e, ss);
494 }
495
496 static float EDGE_getSharpness(CCGEdge *e, int lvl) {
497         if (!lvl)
498                 return e->crease;
499         else if (!e->crease)
500                 return 0.0;
501         else if (e->crease - lvl < 0.0)
502                 return 0.0;
503         else
504                 return e->crease - lvl;
505 }
506
507 static CCGFace *_face_new(CCGFaceHDL fHDL, CCGVert **verts, CCGEdge **edges, int numVerts, CCGSubSurf *ss) {
508         int maxGridSize = 1 + (1<<(ss->subdivLevels-1));
509         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);
510         byte *userData;
511         int i;
512
513         f->numVerts = numVerts;
514         f->fHDL = fHDL;
515         f->flags = 0;
516
517         for (i=0; i<numVerts; i++) {
518                 FACE_getVerts(f)[i] = verts[i];
519                 FACE_getEdges(f)[i] = edges[i];
520                 _vert_addFace(verts[i], f, ss);
521                 _edge_addFace(edges[i], f, ss);
522         }
523
524         userData = ccgSubSurf_getFaceUserData(ss, f);
525         memset(userData, 0, ss->meshIFC.faceUserSize);
526         if (ss->useAgeCounts) *((int*) &userData[ss->faceUserAgeOffset]) = ss->currentAge;
527
528         return f;
529 }
530
531 static CCG_INLINE void *_face_getIECo(CCGFace *f, int lvl, int S, int x, int levels, int dataSize) {
532         int maxGridSize = 1 + (1<<(levels-1));
533         int spacing = 1<<(levels-lvl);
534         byte *gridBase = FACE_getCenterData(f) + dataSize*(1 + S*(maxGridSize + maxGridSize*maxGridSize));
535         return &gridBase[dataSize*x*spacing];
536 }
537 static CCG_INLINE void *_face_getIENo(CCGFace *f, int lvl, int S, int x, int levels, int dataSize, int normalDataOffset) {
538         int maxGridSize = 1 + (1<<(levels-1));
539         int spacing = 1<<(levels-lvl);
540         byte *gridBase = FACE_getCenterData(f) + dataSize*(1 + S*(maxGridSize + maxGridSize*maxGridSize));
541         return &gridBase[dataSize*x*spacing + normalDataOffset];
542 }
543 static CCG_INLINE void *_face_getIFCo(CCGFace *f, int lvl, int S, int x, int y, int levels, int dataSize) {
544         int maxGridSize = 1 + (1<<(levels-1));
545         int spacing = 1<<(levels-lvl);
546         byte *gridBase = FACE_getCenterData(f) + dataSize*(1 + S*(maxGridSize + maxGridSize*maxGridSize));
547         return &gridBase[dataSize*(maxGridSize + (y*maxGridSize + x)*spacing)];
548 }
549 static CCG_INLINE float *_face_getIFNo(CCGFace *f, int lvl, int S, int x, int y, int levels, int dataSize, int normalDataOffset) {
550         int maxGridSize = 1 + (1<<(levels-1));
551         int spacing = 1<<(levels-lvl);
552         byte *gridBase = FACE_getCenterData(f) + dataSize*(1 + S*(maxGridSize + maxGridSize*maxGridSize));
553         return (float*) &gridBase[dataSize*(maxGridSize + (y*maxGridSize + x)*spacing) + normalDataOffset];
554 }
555 static int _face_getVertIndex(CCGFace *f, CCGVert *v) {
556         int i;
557         for (i=0; i<f->numVerts; i++)
558                 if (FACE_getVerts(f)[i]==v)
559                         return i;
560         return -1;
561 }
562 static CCG_INLINE void *_face_getIFCoEdge(CCGFace *f, CCGEdge *e, int lvl, int eX, int eY, int levels, int dataSize) {
563         int maxGridSize = 1 + (1<<(levels-1));
564         int spacing = 1<<(levels-lvl);
565         int S, x, y, cx, cy;
566
567         for (S=0; S<f->numVerts; S++)
568                 if (FACE_getEdges(f)[S]==e)
569                         break;
570
571         eX = eX*spacing;
572         eY = eY*spacing;
573         if (e->v0!=FACE_getVerts(f)[S]) {
574                 eX = (maxGridSize*2 - 1)-1 - eX;
575         }
576         y = maxGridSize - 1 - eX;
577         x = maxGridSize - 1 - eY;
578         if (x<0) {
579                 S = (S+f->numVerts-1)%f->numVerts;
580                 cx = y;
581                 cy = -x;
582         } else if (y<0) {
583                 S = (S+1)%f->numVerts;
584                 cx = -y;
585                 cy = x;
586         } else {
587                 cx = x;
588                 cy = y;
589         }
590         return _face_getIFCo(f, levels, S, cx, cy, levels, dataSize);
591 }
592 static float *_face_getIFNoEdge(CCGFace *f, CCGEdge *e, int lvl, int eX, int eY, int levels, int dataSize, int normalDataOffset) {
593         return (float*) ((byte*) _face_getIFCoEdge(f, e, lvl, eX, eY, levels, dataSize) + normalDataOffset);
594 }
595 void _face_calcIFNo(CCGFace *f, int lvl, int S, int x, int y, float *no, int levels, int dataSize) {
596         float *a = _face_getIFCo(f, lvl, S, x+0, y+0, levels, dataSize);
597         float *b = _face_getIFCo(f, lvl, S, x+1, y+0, levels, dataSize);
598         float *c = _face_getIFCo(f, lvl, S, x+1, y+1, levels, dataSize);
599         float *d = _face_getIFCo(f, lvl, S, x+0, y+1, levels, dataSize);
600         float a_cX = c[0]-a[0], a_cY = c[1]-a[1], a_cZ = c[2]-a[2];
601         float b_dX = d[0]-b[0], b_dY = d[1]-b[1], b_dZ = d[2]-b[2];
602         float length;
603
604         no[0] = b_dY*a_cZ - b_dZ*a_cY;
605         no[1] = b_dZ*a_cX - b_dX*a_cZ;
606         no[2] = b_dX*a_cY - b_dY*a_cX;
607
608         length = sqrt(no[0]*no[0] + no[1]*no[1] + no[2]*no[2]);
609
610         if (length>EPSILON) {
611                 float invLength = 1.f/length;
612
613                 no[0] *= invLength;
614                 no[1] *= invLength;
615                 no[2] *= invLength;
616         } else {
617                 NormZero(no);
618         }
619 }
620
621 static void _face_free(CCGFace *f, CCGSubSurf *ss) {
622         CCGSUBSURF_free(ss, f);
623 }
624 static void _face_unlinkMarkAndFree(CCGFace *f, CCGSubSurf *ss) {
625         int j;
626         for (j=0; j<f->numVerts; j++) {
627                 _vert_remFace(FACE_getVerts(f)[j], f);
628                 _edge_remFace(FACE_getEdges(f)[j], f);
629                 FACE_getVerts(f)[j]->flags |= Vert_eEffected;
630         }
631         _face_free(f, ss);
632 }
633
634 /***/
635
636 CCGSubSurf *ccgSubSurf_new(CCGMeshIFC *ifc, int subdivLevels, CCGAllocatorIFC *allocatorIFC, CCGAllocatorHDL allocator) {
637         if (!allocatorIFC) {
638                 allocatorIFC = _getStandardAllocatorIFC();
639                 allocator = NULL;
640         }
641
642         if (subdivLevels<1) {
643                 return NULL;
644         } else {
645                 CCGSubSurf *ss = allocatorIFC->alloc(allocator, sizeof(*ss));
646
647                 ss->allocatorIFC = *allocatorIFC;
648                 ss->allocator = allocator;
649
650                 ss->vMap = _ehash_new(0, &ss->allocatorIFC, ss->allocator);
651                 ss->eMap = _ehash_new(0, &ss->allocatorIFC, ss->allocator);
652                 ss->fMap = _ehash_new(0, &ss->allocatorIFC, ss->allocator);
653
654                 ss->meshIFC = *ifc;
655                 
656                 ss->subdivLevels = subdivLevels;
657                 ss->numGrids = 0;
658                 ss->allowEdgeCreation = 0;
659                 ss->defaultCreaseValue = 0;
660                 ss->defaultEdgeUserData = NULL;
661
662                 ss->useAgeCounts = 0;
663                 ss->vertUserAgeOffset = ss->edgeUserAgeOffset = ss->faceUserAgeOffset = 0;
664
665                 ss->calcVertNormals = 0;
666                 ss->normalDataOffset = 0;
667
668                 ss->q = CCGSUBSURF_alloc(ss, ss->meshIFC.vertDataSize);
669                 ss->r = CCGSUBSURF_alloc(ss, ss->meshIFC.vertDataSize);
670
671                 ss->currentAge = 0;
672
673                 ss->syncState = eSyncState_None;
674
675                 ss->oldVMap = ss->oldEMap = ss->oldFMap = NULL;
676                 ss->lenTempArrays = 0;
677                 ss->tempVerts = NULL;
678                 ss->tempEdges = NULL;   
679
680                 return ss;
681         }
682 }
683
684 void ccgSubSurf_free(CCGSubSurf *ss) {
685         CCGAllocatorIFC allocatorIFC = ss->allocatorIFC;
686         CCGAllocatorHDL allocator = ss->allocator;
687
688         if (ss->syncState) {
689                 _ehash_free(ss->oldFMap, (EHEntryFreeFP) _face_free, ss);
690                 _ehash_free(ss->oldEMap, (EHEntryFreeFP) _edge_free, ss);
691                 _ehash_free(ss->oldVMap, (EHEntryFreeFP) _vert_free, ss);
692
693                 MEM_freeN(ss->tempVerts);
694                 MEM_freeN(ss->tempEdges);
695         }
696
697         CCGSUBSURF_free(ss, ss->r);
698         CCGSUBSURF_free(ss, ss->q);
699         if (ss->defaultEdgeUserData) CCGSUBSURF_free(ss, ss->defaultEdgeUserData);
700
701         _ehash_free(ss->fMap, (EHEntryFreeFP) _face_free, ss);
702         _ehash_free(ss->eMap, (EHEntryFreeFP) _edge_free, ss);
703         _ehash_free(ss->vMap, (EHEntryFreeFP) _vert_free, ss);
704
705         CCGSUBSURF_free(ss, ss);
706
707         if (allocatorIFC.release) {
708                 allocatorIFC.release(allocator);
709         }
710 }
711
712 CCGError ccgSubSurf_setAllowEdgeCreation(CCGSubSurf *ss, int allowEdgeCreation, float defaultCreaseValue, void *defaultUserData) {
713         if (ss->defaultEdgeUserData) {
714                 CCGSUBSURF_free(ss, ss->defaultEdgeUserData);
715         }
716
717         ss->allowEdgeCreation = !!allowEdgeCreation;
718         ss->defaultCreaseValue = defaultCreaseValue;
719         ss->defaultEdgeUserData = CCGSUBSURF_alloc(ss, ss->meshIFC.edgeUserSize);
720
721         if (defaultUserData) {
722                 memcpy(ss->defaultEdgeUserData, defaultUserData, ss->meshIFC.edgeUserSize);
723         } else {
724                 memset(ss->defaultEdgeUserData, 0, ss->meshIFC.edgeUserSize);
725         }
726
727         return eCCGError_None;
728 }
729 void ccgSubSurf_getAllowEdgeCreation(CCGSubSurf *ss, int *allowEdgeCreation_r, float *defaultCreaseValue_r, void *defaultUserData_r) {
730         if (allowEdgeCreation_r) *allowEdgeCreation_r = ss->allowEdgeCreation;
731         if (ss->allowEdgeCreation) {
732                 if (defaultCreaseValue_r) *defaultCreaseValue_r = ss->defaultCreaseValue;
733                 if (defaultUserData_r) memcpy(defaultUserData_r, ss->defaultEdgeUserData, ss->meshIFC.edgeUserSize);
734         }
735 }
736
737 CCGError ccgSubSurf_setSubdivisionLevels(CCGSubSurf *ss, int subdivisionLevels) {
738         if (subdivisionLevels<=0) {
739                 return eCCGError_InvalidValue;
740         } else if (subdivisionLevels!=ss->subdivLevels) {
741                 ss->numGrids = 0;
742                 ss->subdivLevels = subdivisionLevels;
743                 _ehash_free(ss->vMap, (EHEntryFreeFP) _vert_free, ss);
744                 _ehash_free(ss->eMap, (EHEntryFreeFP) _edge_free, ss);
745                 _ehash_free(ss->fMap, (EHEntryFreeFP) _face_free, ss);
746                 ss->vMap = _ehash_new(0, &ss->allocatorIFC, ss->allocator);
747                 ss->eMap = _ehash_new(0, &ss->allocatorIFC, ss->allocator);
748                 ss->fMap = _ehash_new(0, &ss->allocatorIFC, ss->allocator);
749         }
750
751         return eCCGError_None;
752 }
753
754 void ccgSubSurf_getUseAgeCounts(CCGSubSurf *ss, int *useAgeCounts_r, int *vertUserOffset_r, int *edgeUserOffset_r, int *faceUserOffset_r)
755 {
756         *useAgeCounts_r = ss->useAgeCounts;
757
758         if (vertUserOffset_r) *vertUserOffset_r = ss->vertUserAgeOffset;
759         if (edgeUserOffset_r) *edgeUserOffset_r = ss->edgeUserAgeOffset;
760         if (faceUserOffset_r) *faceUserOffset_r = ss->faceUserAgeOffset;
761 }
762
763 CCGError ccgSubSurf_setUseAgeCounts(CCGSubSurf *ss, int useAgeCounts, int vertUserOffset, int edgeUserOffset, int faceUserOffset) {
764         if (useAgeCounts) {
765                 if (    (vertUserOffset+4>ss->meshIFC.vertUserSize) ||
766                                 (edgeUserOffset+4>ss->meshIFC.edgeUserSize) ||
767                                 (faceUserOffset+4>ss->meshIFC.faceUserSize)) {
768                         return eCCGError_InvalidValue;
769                 }  else {
770                         ss->useAgeCounts = 1;
771                         ss->vertUserAgeOffset = vertUserOffset;
772                         ss->edgeUserAgeOffset = edgeUserOffset;
773                         ss->faceUserAgeOffset = faceUserOffset;
774                 }
775         } else {
776                 ss->useAgeCounts = 0;
777                 ss->vertUserAgeOffset = ss->edgeUserAgeOffset = ss->faceUserAgeOffset = 0;
778         }
779
780         return eCCGError_None;
781 }
782
783 CCGError ccgSubSurf_setCalcVertexNormals(CCGSubSurf *ss, int useVertNormals, int normalDataOffset) {
784         if (useVertNormals) {
785                 if (normalDataOffset<0 || normalDataOffset+12>ss->meshIFC.vertDataSize) {
786                         return eCCGError_InvalidValue;
787                 } else {
788                         ss->calcVertNormals = 1;
789                         ss->normalDataOffset = normalDataOffset;
790                 }
791         } else {
792                 ss->calcVertNormals = 0;
793                 ss->normalDataOffset = 0;
794         }
795
796         return eCCGError_None;
797 }
798
799 /***/
800
801 CCGError ccgSubSurf_initFullSync(CCGSubSurf *ss) {
802         if (ss->syncState!=eSyncState_None) {
803                 return eCCGError_InvalidSyncState;
804         }
805
806         ss->currentAge++;
807
808         ss->oldVMap = ss->vMap; 
809         ss->oldEMap = ss->eMap; 
810         ss->oldFMap = ss->fMap;
811
812         ss->vMap = _ehash_new(0, &ss->allocatorIFC, ss->allocator);
813         ss->eMap = _ehash_new(0, &ss->allocatorIFC, ss->allocator);
814         ss->fMap = _ehash_new(0, &ss->allocatorIFC, ss->allocator);
815
816         ss->numGrids = 0;
817
818         ss->lenTempArrays = 12;
819         ss->tempVerts = MEM_mallocN(sizeof(*ss->tempVerts)*ss->lenTempArrays, "CCGSubsurf tempVerts");
820         ss->tempEdges = MEM_mallocN(sizeof(*ss->tempEdges)*ss->lenTempArrays, "CCGSubsurf tempEdges");
821
822         ss->syncState = eSyncState_Vert;
823
824         return eCCGError_None;
825 }
826
827 CCGError ccgSubSurf_initPartialSync(CCGSubSurf *ss) {
828         if (ss->syncState!=eSyncState_None) {
829                 return eCCGError_InvalidSyncState;
830         }
831
832         ss->currentAge++;
833
834         ss->syncState = eSyncState_Partial;
835
836         return eCCGError_None;
837 }
838
839 CCGError ccgSubSurf_syncVertDel(CCGSubSurf *ss, CCGVertHDL vHDL) {
840         if (ss->syncState!=eSyncState_Partial) {
841                 return eCCGError_InvalidSyncState;
842         } else {
843                 void **prevp;
844                 CCGVert *v = _ehash_lookupWithPrev(ss->vMap, vHDL, &prevp);
845
846                 if (!v || v->numFaces || v->numEdges) {
847                         return eCCGError_InvalidValue;
848                 } else {
849                         *prevp = v->next;
850                         _vert_free(v, ss);
851                 }
852         }
853
854         return eCCGError_None;
855 }
856
857 CCGError ccgSubSurf_syncEdgeDel(CCGSubSurf *ss, CCGEdgeHDL eHDL) {
858         if (ss->syncState!=eSyncState_Partial) {
859                 return eCCGError_InvalidSyncState;
860         } else {
861                 void **prevp;
862                 CCGEdge *e = _ehash_lookupWithPrev(ss->eMap, eHDL, &prevp);
863
864                 if (!e || e->numFaces) {
865                         return eCCGError_InvalidValue;
866                 } else {
867                         *prevp = e->next;
868                         _edge_unlinkMarkAndFree(e, ss);
869                 }
870         }
871
872         return eCCGError_None;
873 }
874
875 CCGError ccgSubSurf_syncFaceDel(CCGSubSurf *ss, CCGFaceHDL fHDL) {
876         if (ss->syncState!=eSyncState_Partial) {
877                 return eCCGError_InvalidSyncState;
878         } else {
879                 void **prevp;
880                 CCGFace *f = _ehash_lookupWithPrev(ss->fMap, fHDL, &prevp);
881
882                 if (!f) {
883                         return eCCGError_InvalidValue;
884                 } else {
885                         *prevp = f->next;
886                         _face_unlinkMarkAndFree(f, ss);
887                 }
888         }
889
890         return eCCGError_None;
891 }
892
893 CCGError ccgSubSurf_syncVert(CCGSubSurf *ss, CCGVertHDL vHDL, void *vertData, int seam, CCGVert **v_r) {
894         void **prevp;
895         CCGVert *v = NULL;
896         short seamflag = (seam)? Vert_eSeam: 0;
897         
898         if (ss->syncState==eSyncState_Partial) {
899                 v = _ehash_lookupWithPrev(ss->vMap, vHDL, &prevp);
900                 if (!v) {
901                         v = _vert_new(vHDL, ss);
902                         VertDataCopy(_vert_getCo(v,0,ss->meshIFC.vertDataSize), vertData);
903                         _ehash_insert(ss->vMap, (EHEntry*) v);
904                         v->flags = Vert_eEffected|seamflag;
905                 } else if (!VertDataEqual(vertData, _vert_getCo(v, 0, ss->meshIFC.vertDataSize)) || ((v->flags & Vert_eSeam) != seamflag)) {
906                         int i, j;
907
908                         VertDataCopy(_vert_getCo(v,0,ss->meshIFC.vertDataSize), vertData);
909                         v->flags = Vert_eEffected|seamflag;
910
911                         for (i=0; i<v->numEdges; i++) {
912                                 CCGEdge *e = v->edges[i];
913                                 e->v0->flags |= Vert_eEffected;
914                                 e->v1->flags |= Vert_eEffected;
915                         }
916                         for (i=0; i<v->numFaces; i++) {
917                                 CCGFace *f = v->faces[i];
918                                 for (j=0; j<f->numVerts; j++) {
919                                         FACE_getVerts(f)[j]->flags |= Vert_eEffected;
920                                 }
921                         }
922                 }
923         } else {
924                 if (ss->syncState!=eSyncState_Vert) { 
925                         return eCCGError_InvalidSyncState;
926                 }
927
928                 v = _ehash_lookupWithPrev(ss->oldVMap, vHDL, &prevp);
929                 if (!v) {
930                         v = _vert_new(vHDL, ss);
931                         VertDataCopy(_vert_getCo(v,0,ss->meshIFC.vertDataSize), vertData);
932                         _ehash_insert(ss->vMap, (EHEntry*) v);
933                         v->flags = Vert_eEffected|seamflag;
934                 } else if (!VertDataEqual(vertData, _vert_getCo(v, 0, ss->meshIFC.vertDataSize)) || ((v->flags & Vert_eSeam) != seamflag)) {
935                         *prevp = v->next;
936                         _ehash_insert(ss->vMap, (EHEntry*) v);
937                         VertDataCopy(_vert_getCo(v,0,ss->meshIFC.vertDataSize), vertData);
938                         v->flags = Vert_eEffected|Vert_eChanged|seamflag;
939                 } else {
940                         *prevp = v->next;
941                         _ehash_insert(ss->vMap, (EHEntry*) v);
942                         v->flags = 0;
943                 }
944         }
945
946         if (v_r) *v_r = v;
947         return eCCGError_None;
948 }
949
950 CCGError ccgSubSurf_syncEdge(CCGSubSurf *ss, CCGEdgeHDL eHDL, CCGVertHDL e_vHDL0, CCGVertHDL e_vHDL1, float crease, CCGEdge **e_r) {
951         void **prevp;
952         CCGEdge *e = NULL, *eNew;
953
954         if (ss->syncState==eSyncState_Partial) {
955                 e = _ehash_lookupWithPrev(ss->eMap, eHDL, &prevp);
956                 if (!e || e->v0->vHDL!=e_vHDL0 || e->v1->vHDL!=e_vHDL1 || crease!=e->crease) {
957                         CCGVert *v0 = _ehash_lookup(ss->vMap, e_vHDL0);
958                         CCGVert *v1 = _ehash_lookup(ss->vMap, e_vHDL1);
959
960                         eNew = _edge_new(eHDL, v0, v1, crease, ss);
961
962                         if (e) {
963                                 *prevp = eNew;
964                                 eNew->next = e->next;
965
966                                 _edge_unlinkMarkAndFree(e, ss);
967                         } else {
968                                 _ehash_insert(ss->eMap, (EHEntry*) eNew);
969                         }
970
971                         eNew->v0->flags |= Vert_eEffected;
972                         eNew->v1->flags |= Vert_eEffected;
973                 }
974         } else {
975                 if (ss->syncState==eSyncState_Vert) {
976                         ss->syncState = eSyncState_Edge;
977                 } else if (ss->syncState!=eSyncState_Edge) {
978                         return eCCGError_InvalidSyncState;
979                 }
980
981                 e = _ehash_lookupWithPrev(ss->oldEMap, eHDL, &prevp);
982                 if (!e || e->v0->vHDL!=e_vHDL0 || e->v1->vHDL!=e_vHDL1|| e->crease!=crease) {
983                         CCGVert *v0 = _ehash_lookup(ss->vMap, e_vHDL0);
984                         CCGVert *v1 = _ehash_lookup(ss->vMap, e_vHDL1);
985                         e = _edge_new(eHDL, v0, v1, crease, ss);
986                         _ehash_insert(ss->eMap, (EHEntry*) e);
987                         e->v0->flags |= Vert_eEffected;
988                         e->v1->flags |= Vert_eEffected;
989                 } else {
990                         *prevp = e->next;
991                         _ehash_insert(ss->eMap, (EHEntry*) e);
992                         e->flags = 0;
993                         if ((e->v0->flags|e->v1->flags)&Vert_eChanged) {
994                                 e->v0->flags |= Vert_eEffected;
995                                 e->v1->flags |= Vert_eEffected;
996                         }
997                 }
998         }
999
1000         if (e_r) *e_r = e;
1001         return eCCGError_None;
1002 }
1003
1004 CCGError ccgSubSurf_syncFace(CCGSubSurf *ss, CCGFaceHDL fHDL, int numVerts, CCGVertHDL *vHDLs, CCGFace **f_r) {
1005         void **prevp;
1006         CCGFace *f = NULL, *fNew;
1007         int j, k, topologyChanged = 0;
1008
1009         if (numVerts>ss->lenTempArrays) {
1010                 ss->lenTempArrays = (numVerts<ss->lenTempArrays*2)?ss->lenTempArrays*2:numVerts;
1011                 ss->tempVerts = MEM_reallocN(ss->tempVerts, sizeof(*ss->tempVerts)*ss->lenTempArrays);
1012                 ss->tempEdges = MEM_reallocN(ss->tempEdges, sizeof(*ss->tempEdges)*ss->lenTempArrays);
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                 MEM_freeN(ss->tempEdges);
1128                 MEM_freeN(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 = MEM_mallocN(ss->meshIFC.vertDataSize, "CCGSubsurf q");
1695                         r = MEM_mallocN(ss->meshIFC.vertDataSize, "CCGSubsurf r");
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                         MEM_freeN(q);
1785                         MEM_freeN(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 = MEM_mallocN(sizeof(*effectedV)*ss->vMap->numEntries, "CCGSubsurf effectedV");
1841         effectedE = MEM_mallocN(sizeof(*effectedE)*ss->eMap->numEntries, "CCGSubsurf effectedE");
1842         effectedF = MEM_mallocN(sizeof(*effectedF)*ss->fMap->numEntries, "CCGSubsurf effectedF");
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         MEM_freeN(effectedF);
2101         MEM_freeN(effectedE);
2102         MEM_freeN(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 = MEM_mallocN(sizeof(*array)*ss->fMap->numEntries, "CCGSubsurf allFaces");
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 = MEM_mallocN(sizeof(*arrayV)*ss->vMap->numEntries, "CCGSubsurf arrayV");
2135         arrayE = MEM_mallocN(sizeof(*arrayE)*ss->eMap->numEntries, "CCGSubsurf arrayV");
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) MEM_freeN(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) MEM_freeN(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                         for (x=0; x<gridSize; x++)
2301                                 VertDataZero(FACE_getIECo(f, lvl, S, x));
2302
2303                 for (S=0; S<f->numVerts; S++) {
2304                         int prevS = (S+f->numVerts-1)%f->numVerts;
2305                         CCGEdge *e = FACE_getEdges(f)[S];
2306                         CCGEdge *prevE = FACE_getEdges(f)[prevS];
2307
2308                         VertDataAdd(FACE_getCenterData(f), FACE_getIFCo(f, lvl, S, 0, 0));
2309                         if (FACE_getVerts(f)[S]->flags&Vert_eEffected)
2310                                 VertDataAdd(VERT_getCo(FACE_getVerts(f)[S], lvl), FACE_getIFCo(f, lvl, S, cornerIdx, cornerIdx));
2311
2312                         for (x=1; x<gridSize-1; x++) {
2313                                 VertDataAdd(FACE_getIECo(f, lvl, S, x), FACE_getIFCo(f, lvl, S, x, 0));
2314                                 VertDataAdd(FACE_getIECo(f, lvl, prevS, x), FACE_getIFCo(f, lvl, S, 0, x));
2315                         }
2316
2317                         for (x=0; x<gridSize-1; x++) {
2318                                 int eI = gridSize-1-x;
2319                                 if (FACE_getEdges(f)[S]->flags&Edge_eEffected)
2320                                         VertDataAdd(_edge_getCoVert(e, FACE_getVerts(f)[S], lvl, eI,vertDataSize), FACE_getIFCo(f, lvl, S, cornerIdx, x));
2321                                 if (FACE_getEdges(f)[prevS]->flags&Edge_eEffected)
2322                                         if(x != 0)
2323                                                 VertDataAdd(_edge_getCoVert(prevE, FACE_getVerts(f)[S], lvl, eI,vertDataSize), FACE_getIFCo(f, lvl, S, x, cornerIdx));
2324                         }
2325                 }
2326         }
2327
2328         /* average */
2329         for (i=0; i<numEffectedV; i++) {
2330                 CCGVert *v = effectedV[i];
2331                 VertDataMulN(VERT_getCo(v, lvl), 1.0f/v->numFaces);
2332         }
2333
2334         for (i=0; i<numEffectedE; i++) {
2335                 CCGEdge *e = effectedE[i];
2336
2337                 VertDataCopy(EDGE_getCo(e, lvl, 0), VERT_getCo(e->v0, lvl));
2338                 VertDataCopy(EDGE_getCo(e, lvl, edgeSize-1), VERT_getCo(e->v1, lvl));
2339
2340                 for (x=1; x<edgeSize-1; x++)
2341                         VertDataMulN(EDGE_getCo(e, lvl, x), 1.0f/e->numFaces);
2342         }
2343
2344         /* copy */
2345         for (i=0; i<numEffectedF; i++) {
2346                 CCGFace *f = effectedF[i];
2347
2348                 VertDataMulN(FACE_getCenterData(f), 1.0f/f->numVerts);
2349
2350                 for (S=0; S<f->numVerts; S++)
2351                         for (x=1; x<gridSize-1; x++)
2352                                 VertDataMulN(FACE_getIECo(f, lvl, S, x), 0.5f);
2353
2354                 for (S=0; S<f->numVerts; S++) {
2355                         int prevS = (S+f->numVerts-1)%f->numVerts;
2356                         CCGEdge *e = FACE_getEdges(f)[S];
2357                         CCGEdge *prevE = FACE_getEdges(f)[prevS];
2358
2359                         VertDataCopy(FACE_getIFCo(f, lvl, S, 0, 0), FACE_getCenterData(f));
2360                         VertDataCopy(FACE_getIFCo(f, lvl, S, cornerIdx, cornerIdx), VERT_getCo(FACE_getVerts(f)[S], lvl));
2361
2362                         for (x=1; x<gridSize-1; x++) {
2363                                 VertDataCopy(FACE_getIFCo(f, lvl, S, x, 0), FACE_getIECo(f, lvl, S, x));
2364                                 VertDataCopy(FACE_getIFCo(f, lvl, S, 0, x), FACE_getIECo(f, lvl, prevS, x));
2365                         }
2366
2367                         for (x=0; x<gridSize-1; x++) {
2368                                 int eI = gridSize-1-x;
2369                                 VertDataCopy(FACE_getIFCo(f, lvl, S, cornerIdx, x), _edge_getCoVert(e, FACE_getVerts(f)[S], lvl, eI,vertDataSize));
2370                                 VertDataCopy(FACE_getIFCo(f, lvl, S, x, cornerIdx), _edge_getCoVert(prevE, FACE_getVerts(f)[S], lvl, eI,vertDataSize));
2371                         }
2372
2373                         VertDataCopy(FACE_getIECo(f, lvl, S, 0), FACE_getCenterData(f));
2374                         VertDataCopy(FACE_getIECo(f, lvl, S, gridSize-1), FACE_getIFCo(f, lvl, S, gridSize-1, 0));
2375                 }
2376         }
2377
2378         for (i=0; i<numEffectedV; i++)
2379                 effectedV[i]->flags = 0;
2380         for (i=0; i<numEffectedE; i++)
2381                 effectedE[i]->flags = 0;
2382         for (i=0; i<numEffectedF; i++)
2383                 effectedF[i]->flags = 0;
2384
2385         MEM_freeN(effectedE);
2386         MEM_freeN(effectedV);
2387         if(freeF) MEM_freeN(effectedF);
2388
2389         return eCCGError_None;
2390 }
2391
2392 /* update normals for specified faces */
2393 CCGError ccgSubSurf_updateNormals(CCGSubSurf *ss, CCGFace **effectedF, int numEffectedF) {
2394         CCGVert **effectedV;
2395         CCGEdge **effectedE;
2396         int i, numEffectedV, numEffectedE, freeF;
2397
2398         ccgSubSurf__allFaces(ss, &effectedF, &numEffectedF, &freeF);
2399         ccgSubSurf__effectedFaceNeighbours(ss, effectedF, numEffectedF,
2400                 &effectedV, &numEffectedV, &effectedE, &numEffectedE);
2401
2402         if (ss->calcVertNormals)
2403                 ccgSubSurf__calcVertNormals(ss,
2404                         effectedV, effectedE, effectedF,
2405                         numEffectedV, numEffectedE, numEffectedF);
2406
2407         for (i=0; i<numEffectedV; i++)
2408                 effectedV[i]->flags = 0;
2409         for (i=0; i<numEffectedE; i++)
2410                 effectedE[i]->flags = 0;
2411         for (i=0; i<numEffectedF; i++)
2412                 effectedF[i]->flags = 0;
2413
2414         MEM_freeN(effectedE);
2415         MEM_freeN(effectedV);
2416         if(freeF) MEM_freeN(effectedF);
2417
2418         return eCCGError_None;
2419 }
2420
2421 /* compute subdivision levels from a given starting point, used by
2422    multires subdivide/propagate, by filling in coordinates at a
2423    certain level, and then subdividing that up to the highest level */
2424 CCGError ccgSubSurf_updateLevels(CCGSubSurf *ss, int lvl, CCGFace **effectedF, int numEffectedF)
2425 {
2426         CCGVert **effectedV;
2427         CCGEdge **effectedE;
2428         int numEffectedV, numEffectedE, freeF, i;
2429         int curLvl, subdivLevels = ss->subdivLevels;
2430
2431         ccgSubSurf__allFaces(ss, &effectedF, &numEffectedF, &freeF);
2432         ccgSubSurf__effectedFaceNeighbours(ss, effectedF, numEffectedF,
2433                 &effectedV, &numEffectedV, &effectedE, &numEffectedE);
2434
2435         for (curLvl=lvl; curLvl<subdivLevels; curLvl++) {
2436                 ccgSubSurf__calcSubdivLevel(ss,
2437                         effectedV, effectedE, effectedF,
2438                         numEffectedV, numEffectedE, numEffectedF, curLvl);
2439         }
2440
2441         for (i=0; i<numEffectedV; i++)
2442                 effectedV[i]->flags = 0;
2443         for (i=0; i<numEffectedE; i++)
2444                 effectedE[i]->flags = 0;
2445         for (i=0; i<numEffectedF; i++)
2446                 effectedF[i]->flags = 0;
2447
2448         MEM_freeN(effectedE);
2449         MEM_freeN(effectedV);
2450         if(freeF) MEM_freeN(effectedF);
2451
2452         return eCCGError_None;
2453 }
2454
2455 #undef VERT_getCo
2456 #undef EDGE_getCo
2457 #undef FACE_getIECo
2458 #undef FACE_getIFCo
2459
2460 /*** External API accessor functions ***/
2461
2462 int ccgSubSurf_getNumVerts(CCGSubSurf *ss) {
2463         return ss->vMap->numEntries;
2464 }
2465 int ccgSubSurf_getNumEdges(CCGSubSurf *ss) {
2466         return ss->eMap->numEntries;
2467 }
2468 int ccgSubSurf_getNumFaces(CCGSubSurf *ss) {
2469         return ss->fMap->numEntries;
2470 }
2471
2472 CCGVert *ccgSubSurf_getVert(CCGSubSurf *ss, CCGVertHDL v) {
2473         return (CCGVert*) _ehash_lookup(ss->vMap, v);
2474 }
2475 CCGEdge *ccgSubSurf_getEdge(CCGSubSurf *ss, CCGEdgeHDL e) {
2476         return (CCGEdge*) _ehash_lookup(ss->eMap, e);
2477 }
2478 CCGFace *ccgSubSurf_getFace(CCGSubSurf *ss, CCGFaceHDL f) {
2479         return (CCGFace*) _ehash_lookup(ss->fMap, f);
2480 }
2481
2482 int ccgSubSurf_getSubdivisionLevels(CCGSubSurf *ss) {
2483         return ss->subdivLevels;
2484 }
2485 int ccgSubSurf_getEdgeSize(CCGSubSurf *ss) {
2486         return ccgSubSurf_getEdgeLevelSize(ss, ss->subdivLevels);
2487 }
2488 int ccgSubSurf_getEdgeLevelSize(CCGSubSurf *ss, int level) {
2489         if (level<1 || level>ss->subdivLevels) {
2490                 return -1;
2491         } else {
2492                 return 1 + (1<<level);
2493         }
2494 }
2495 int ccgSubSurf_getGridSize(CCGSubSurf *ss) {
2496         return ccgSubSurf_getGridLevelSize(ss, ss->subdivLevels);
2497 }
2498 int ccgSubSurf_getGridLevelSize(CCGSubSurf *ss, int level) {
2499         if (level<1 || level>ss->subdivLevels) {
2500                 return -1;
2501         } else {
2502                 return 1 + (1<<(level-1));
2503         }
2504 }
2505
2506 /* Vert accessors */
2507
2508 CCGVertHDL ccgSubSurf_getVertVertHandle(CCGVert *v) {
2509         return v->vHDL;
2510 }
2511 int ccgSubSurf_getVertAge(CCGSubSurf *ss, CCGVert *v) {
2512         if (ss->useAgeCounts) {
2513                 byte *userData = ccgSubSurf_getVertUserData(ss, v);
2514                 return ss->currentAge - *((int*) &userData[ss->vertUserAgeOffset]);
2515         } else {
2516                 return 0;
2517         }
2518 }
2519 void *ccgSubSurf_getVertUserData(CCGSubSurf *ss, CCGVert *v) {
2520         return VERT_getLevelData(v) + ss->meshIFC.vertDataSize*(ss->subdivLevels+1);
2521 }
2522 int ccgSubSurf_getVertNumFaces(CCGVert *v) {
2523         return v->numFaces;
2524 }
2525 CCGFace *ccgSubSurf_getVertFace(CCGVert *v, int index) {
2526         if (index<0 || index>=v->numFaces) {
2527                 return NULL;
2528         } else {
2529                 return v->faces[index];
2530         }
2531 }
2532 int ccgSubSurf_getVertNumEdges(CCGVert *v) {
2533         return v->numEdges;
2534 }
2535 CCGEdge *ccgSubSurf_getVertEdge(CCGVert *v, int index) {
2536         if (index<0 || index>=v->numEdges) {
2537                 return NULL;
2538         } else {
2539                 return v->edges[index];
2540         }
2541 }
2542 void *ccgSubSurf_getVertData(CCGSubSurf *ss, CCGVert *v) {
2543         return ccgSubSurf_getVertLevelData(ss, v, ss->subdivLevels);
2544 }
2545 void *ccgSubSurf_getVertLevelData(CCGSubSurf *ss, CCGVert *v, int level) {
2546         if (level<0 || level>ss->subdivLevels) {
2547                 return NULL;
2548         } else {
2549                 return _vert_getCo(v, level, ss->meshIFC.vertDataSize);
2550         }
2551 }
2552
2553 /* Edge accessors */
2554
2555 CCGEdgeHDL ccgSubSurf_getEdgeEdgeHandle(CCGEdge *e) {
2556         return e->eHDL;
2557 }
2558 int ccgSubSurf_getEdgeAge(CCGSubSurf *ss, CCGEdge *e) {
2559         if (ss->useAgeCounts) {
2560                 byte *userData = ccgSubSurf_getEdgeUserData(ss, e);
2561                 return ss->currentAge - *((int*) &userData[ss->edgeUserAgeOffset]);
2562         } else {
2563                 return 0;
2564         }
2565 }
2566 void *ccgSubSurf_getEdgeUserData(CCGSubSurf *ss, CCGEdge *e) {
2567         return EDGE_getLevelData(e) + ss->meshIFC.vertDataSize *((ss->subdivLevels+1) + (1<<(ss->subdivLevels+1))-1);
2568 }
2569 int ccgSubSurf_getEdgeNumFaces(CCGEdge *e) {
2570         return e->numFaces;
2571 }
2572 CCGFace *ccgSubSurf_getEdgeFace(CCGEdge *e, int index) {
2573         if (index<0 || index>=e->numFaces) {
2574                 return NULL;
2575         } else {
2576                 return e->faces[index];
2577         }
2578 }
2579 CCGVert *ccgSubSurf_getEdgeVert0(CCGEdge *e) {
2580         return e->v0;
2581 }
2582 CCGVert *ccgSubSurf_getEdgeVert1(CCGEdge *e) {
2583         return e->v1;
2584 }
2585 void *ccgSubSurf_getEdgeDataArray(CCGSubSurf *ss, CCGEdge *e) {
2586         return ccgSubSurf_getEdgeData(ss, e, 0);
2587 }
2588 void *ccgSubSurf_getEdgeData(CCGSubSurf *ss, CCGEdge *e, int x) {
2589         return ccgSubSurf_getEdgeLevelData(ss, e, x, ss->subdivLevels);
2590 }
2591 void *ccgSubSurf_getEdgeLevelData(CCGSubSurf *ss, CCGEdge *e, int x, int level) {
2592         if (level<0 || level>ss->subdivLevels) {
2593                 return NULL;
2594         } else {
2595                 return _edge_getCo(e, level, x, ss->meshIFC.vertDataSize);
2596         }
2597 }
2598 float ccgSubSurf_getEdgeCrease(CCGEdge *e) {
2599         return e->crease;
2600 }
2601
2602 /* Face accessors */
2603
2604 CCGFaceHDL ccgSubSurf_getFaceFaceHandle(CCGSubSurf *ss, CCGFace *f) {
2605         return f->fHDL;
2606 }
2607 int ccgSubSurf_getFaceAge(CCGSubSurf *ss, CCGFace *f) {
2608         if (ss->useAgeCounts) {
2609                 byte *userData = ccgSubSurf_getFaceUserData(ss, f);
2610                 return ss->currentAge - *((int*) &userData[ss->faceUserAgeOffset]);
2611         } else {
2612                 return 0;
2613         }
2614 }
2615 void *ccgSubSurf_getFaceUserData(CCGSubSurf *ss, CCGFace *f) {
2616         int maxGridSize = 1 + (1<<(ss->subdivLevels-1));
2617         return FACE_getCenterData(f) + ss->meshIFC.vertDataSize *(1 + f->numVerts*maxGridSize + f->numVerts*maxGridSize*maxGridSize);
2618 }
2619 int ccgSubSurf_getFaceNumVerts(CCGFace *f) {
2620         return f->numVerts;
2621 }
2622 CCGVert *ccgSubSurf_getFaceVert(CCGSubSurf *ss, CCGFace *f, int index) {
2623         if (index<0 || index>=f->numVerts) {
2624                 return NULL;
2625         } else {
2626                 return FACE_getVerts(f)[index];
2627         }
2628 }
2629 CCGEdge *ccgSubSurf_getFaceEdge(CCGSubSurf *ss, CCGFace *f, int index) {
2630         if (index<0 || index>=f->numVerts) {
2631                 return NULL;
2632         } else {
2633                 return FACE_getEdges(f)[index];
2634         }
2635 }
2636 int ccgSubSurf_getFaceEdgeIndex(CCGFace *f, CCGEdge *e) {
2637         int i;
2638
2639         for (i=0; i<f->numVerts; i++)
2640                 if (FACE_getEdges(f)[i]==e)
2641                         return i;
2642
2643         return -1;
2644 }
2645 void *ccgSubSurf_getFaceCenterData(CCGFace *f) {
2646         return FACE_getCenterData(f);
2647 }
2648 void *ccgSubSurf_getFaceGridEdgeDataArray(CCGSubSurf *ss, CCGFace *f, int gridIndex) {
2649         return ccgSubSurf_getFaceGridEdgeData(ss, f, gridIndex, 0);
2650 }
2651 void *ccgSubSurf_getFaceGridEdgeData(CCGSubSurf *ss, CCGFace *f, int gridIndex, int x) {
2652         return _face_getIECo(f, ss->subdivLevels, gridIndex, x, ss->subdivLevels, ss->meshIFC.vertDataSize);
2653 }
2654 void *ccgSubSurf_getFaceGridDataArray(CCGSubSurf *ss, CCGFace *f, int gridIndex) {
2655         return ccgSubSurf_getFaceGridData(ss, f, gridIndex, 0, 0);
2656 }
2657 void *ccgSubSurf_getFaceGridData(CCGSubSurf *ss, CCGFace *f, int gridIndex, int x, int y) {
2658         return _face_getIFCo(f, ss->subdivLevels, gridIndex, x, y, ss->subdivLevels, ss->meshIFC.vertDataSize);
2659 }
2660
2661 /*** External API iterator functions ***/
2662
2663 CCGVertIterator *ccgSubSurf_getVertIterator(CCGSubSurf *ss) {
2664         return (CCGVertIterator*) _ehashIterator_new(ss->vMap);
2665 }
2666 CCGEdgeIterator *ccgSubSurf_getEdgeIterator(CCGSubSurf *ss) {
2667         return (CCGEdgeIterator*) _ehashIterator_new(ss->eMap);
2668 }
2669 CCGFaceIterator *ccgSubSurf_getFaceIterator(CCGSubSurf *ss) {
2670         return (CCGFaceIterator*) _ehashIterator_new(ss->fMap);
2671 }
2672
2673 CCGVert *ccgVertIterator_getCurrent(CCGVertIterator *vi) {
2674         return (CCGVert*) _ehashIterator_getCurrent((EHashIterator*) vi);
2675 }
2676 int ccgVertIterator_isStopped(CCGVertIterator *vi) {
2677         return _ehashIterator_isStopped((EHashIterator*) vi);
2678 }
2679 void ccgVertIterator_next(CCGVertIterator *vi) {
2680         _ehashIterator_next((EHashIterator*) vi); 
2681 }
2682 void ccgVertIterator_free(CCGVertIterator *vi) {
2683         _ehashIterator_free((EHashIterator*) vi);
2684 }
2685
2686 CCGEdge *ccgEdgeIterator_getCurrent(CCGEdgeIterator *vi) {
2687         return (CCGEdge*) _ehashIterator_getCurrent((EHashIterator*) vi);
2688 }
2689 int ccgEdgeIterator_isStopped(CCGEdgeIterator *vi) {
2690         return _ehashIterator_isStopped((EHashIterator*) vi);
2691 }
2692 void ccgEdgeIterator_next(CCGEdgeIterator *vi) {
2693         _ehashIterator_next((EHashIterator*) vi); 
2694 }
2695 void ccgEdgeIterator_free(CCGEdgeIterator *vi) {
2696         _ehashIterator_free((EHashIterator*) vi);
2697 }
2698
2699 CCGFace *ccgFaceIterator_getCurrent(CCGFaceIterator *vi) {
2700         return (CCGFace*) _ehashIterator_getCurrent((EHashIterator*) vi);
2701 }
2702 int ccgFaceIterator_isStopped(CCGFaceIterator *vi) {
2703         return _ehashIterator_isStopped((EHashIterator*) vi);
2704 }
2705 void ccgFaceIterator_next(CCGFaceIterator *vi) {
2706         _ehashIterator_next((EHashIterator*) vi); 
2707 }
2708 void ccgFaceIterator_free(CCGFaceIterator *vi) {
2709         _ehashIterator_free((EHashIterator*) vi);
2710 }
2711
2712 /*** Extern API final vert/edge/face interface ***/
2713
2714 int ccgSubSurf_getNumFinalVerts(CCGSubSurf *ss) {
2715         int edgeSize = 1 + (1<<ss->subdivLevels);
2716         int gridSize = 1 + (1<<(ss->subdivLevels-1));
2717         int numFinalVerts = ss->vMap->numEntries + ss->eMap->numEntries*(edgeSize-2) + ss->fMap->numEntries + ss->numGrids*((gridSize-2) + ((gridSize-2)*(gridSize-2)));
2718         return numFinalVerts;
2719 }
2720 int ccgSubSurf_getNumFinalEdges(CCGSubSurf *ss) {
2721         int edgeSize = 1 + (1<<ss->subdivLevels);
2722         int gridSize = 1 + (1<<(ss->subdivLevels-1));
2723         int numFinalEdges = ss->eMap->numEntries*(edgeSize-1) + ss->numGrids*((gridSize-1) + 2*((gridSize-2)*(gridSize-1)));
2724         return numFinalEdges;
2725 }
2726 int ccgSubSurf_getNumFinalFaces(CCGSubSurf *ss) {
2727         int gridSize = 1 + (1<<(ss->subdivLevels-1));
2728         int numFinalFaces = ss->numGrids*((gridSize-1)*(gridSize-1));
2729         return numFinalFaces;
2730 }