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