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