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