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