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