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