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