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