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