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