bd5ddba9590f7d745dada3d8217981e7eb48df80
[blender.git] / source / blender / blenkernel / intern / CCGSubSurf.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * ***** END GPL LICENSE BLOCK *****
19  */
20
21 /** \file blender/blenkernel/intern/CCGSubSurf.c
22  *  \ingroup bke
23  */
24
25 #include <stdlib.h>
26 #include <string.h>
27 #include <math.h>
28
29 #include "MEM_guardedalloc.h"
30 #include "BLI_sys_types.h" // for intptr_t support
31
32 #include "BLI_utildefines.h" /* for BLI_assert */
33 #include "BLI_math.h"
34
35 #include "BKE_ccg.h"
36 #include "CCGSubSurf.h"
37 #include "CCGSubSurf_intern.h"
38 #include "BKE_subsurf.h"
39
40 #ifdef WITH_OPENSUBDIV
41 #  include "opensubdiv_capi.h"
42 #  include "opensubdiv_converter_capi.h"
43 #endif
44
45 #include "GL/glew.h"
46
47 /***/
48
49 int BKE_ccg_gridsize(int level)
50 {
51         return ccg_gridsize(level);
52 }
53
54 int BKE_ccg_factor(int low_level, int high_level)
55 {
56         BLI_assert(low_level > 0 && high_level > 0);
57         BLI_assert(low_level <= high_level);
58
59         return 1 << (high_level - low_level);
60 }
61
62 /***/
63
64 static CCGVert *_vert_new(CCGVertHDL vHDL, CCGSubSurf *ss)
65 {
66         int num_vert_data = ss->subdivLevels + 1;
67         CCGVert *v = CCGSUBSURF_alloc(ss,
68                                       sizeof(CCGVert) +
69                                       ss->meshIFC.vertDataSize * num_vert_data +
70                                       ss->meshIFC.vertUserSize);
71         byte *userData;
72
73         v->vHDL = vHDL;
74         v->edges = NULL;
75         v->faces = NULL;
76         v->numEdges = v->numFaces = 0;
77         v->flags = 0;
78
79         userData = ccgSubSurf_getVertUserData(ss, v);
80         memset(userData, 0, ss->meshIFC.vertUserSize);
81         if (ss->useAgeCounts) *((int *) &userData[ss->vertUserAgeOffset]) = ss->currentAge;
82
83         return v;
84 }
85 static void _vert_remEdge(CCGVert *v, CCGEdge *e)
86 {
87         int i;
88         for (i = 0; i < v->numEdges; i++) {
89                 if (v->edges[i] == e) {
90                         v->edges[i] = v->edges[--v->numEdges];
91                         break;
92                 }
93         }
94 }
95 static void _vert_remFace(CCGVert *v, CCGFace *f)
96 {
97         int i;
98         for (i = 0; i < v->numFaces; i++) {
99                 if (v->faces[i] == f) {
100                         v->faces[i] = v->faces[--v->numFaces];
101                         break;
102                 }
103         }
104 }
105 static void _vert_addEdge(CCGVert *v, CCGEdge *e, CCGSubSurf *ss)
106 {
107         v->edges = CCGSUBSURF_realloc(ss, v->edges, (v->numEdges + 1) * sizeof(*v->edges), v->numEdges * sizeof(*v->edges));
108         v->edges[v->numEdges++] = e;
109 }
110 static void _vert_addFace(CCGVert *v, CCGFace *f, CCGSubSurf *ss)
111 {
112         v->faces = CCGSUBSURF_realloc(ss, v->faces, (v->numFaces + 1) * sizeof(*v->faces), v->numFaces * sizeof(*v->faces));
113         v->faces[v->numFaces++] = f;
114 }
115 static CCGEdge *_vert_findEdgeTo(const CCGVert *v, const CCGVert *vQ)
116 {
117         int i;
118         for (i = 0; i < v->numEdges; i++) {
119                 CCGEdge *e = v->edges[v->numEdges - 1 - i]; // XXX, note reverse
120                 if ((e->v0 == v && e->v1 == vQ) ||
121                     (e->v1 == v && e->v0 == vQ))
122                 {
123                         return e;
124                 }
125         }
126         return NULL;
127 }
128 static void _vert_free(CCGVert *v, CCGSubSurf *ss)
129 {
130         if (v->edges) {
131                 CCGSUBSURF_free(ss, v->edges);
132         }
133
134         if (v->faces) {
135                 CCGSUBSURF_free(ss, v->faces);
136         }
137
138         CCGSUBSURF_free(ss, v);
139 }
140
141 /***/
142
143 static CCGEdge *_edge_new(CCGEdgeHDL eHDL, CCGVert *v0, CCGVert *v1, float crease, CCGSubSurf *ss)
144 {
145         int num_edge_data = ccg_edgebase(ss->subdivLevels + 1);
146         CCGEdge *e = CCGSUBSURF_alloc(ss,
147                                       sizeof(CCGEdge) +
148                                       ss->meshIFC.vertDataSize * num_edge_data +
149                                       ss->meshIFC.edgeUserSize);
150         byte *userData;
151
152         e->eHDL = eHDL;
153         e->v0 = v0;
154         e->v1 = v1;
155         e->crease = crease;
156         e->faces = NULL;
157         e->numFaces = 0;
158         e->flags = 0;
159         _vert_addEdge(v0, e, ss);
160         _vert_addEdge(v1, e, ss);
161
162         userData = ccgSubSurf_getEdgeUserData(ss, e);
163         memset(userData, 0, ss->meshIFC.edgeUserSize);
164         if (ss->useAgeCounts) *((int *) &userData[ss->edgeUserAgeOffset]) = ss->currentAge;
165
166         return e;
167 }
168 static void _edge_remFace(CCGEdge *e, CCGFace *f)
169 {
170         int i;
171         for (i = 0; i < e->numFaces; i++) {
172                 if (e->faces[i] == f) {
173                         e->faces[i] = e->faces[--e->numFaces];
174                         break;
175                 }
176         }
177 }
178 static void _edge_addFace(CCGEdge *e, CCGFace *f, CCGSubSurf *ss)
179 {
180         e->faces = CCGSUBSURF_realloc(ss, e->faces, (e->numFaces + 1) * sizeof(*e->faces), e->numFaces * sizeof(*e->faces));
181         e->faces[e->numFaces++] = f;
182 }
183 static void *_edge_getCoVert(CCGEdge *e, CCGVert *v, int lvl, int x, int dataSize)
184 {
185         int levelBase = ccg_edgebase(lvl);
186         if (v == e->v0) {
187                 return &EDGE_getLevelData(e)[dataSize * (levelBase + x)];
188         }
189         else {
190                 return &EDGE_getLevelData(e)[dataSize * (levelBase + (1 << lvl) - x)];
191         }
192 }
193
194 static void _edge_free(CCGEdge *e, CCGSubSurf *ss)
195 {
196         if (e->faces) {
197                 CCGSUBSURF_free(ss, e->faces);
198         }
199
200         CCGSUBSURF_free(ss, e);
201 }
202 static void _edge_unlinkMarkAndFree(CCGEdge *e, CCGSubSurf *ss)
203 {
204         _vert_remEdge(e->v0, e);
205         _vert_remEdge(e->v1, e);
206         e->v0->flags |= Vert_eEffected;
207         e->v1->flags |= Vert_eEffected;
208         _edge_free(e, ss);
209 }
210
211 static CCGFace *_face_new(CCGFaceHDL fHDL, CCGVert **verts, CCGEdge **edges, int numVerts, CCGSubSurf *ss)
212 {
213         int maxGridSize = ccg_gridsize(ss->subdivLevels);
214         int num_face_data = (numVerts * maxGridSize +
215                              numVerts * maxGridSize * maxGridSize + 1);
216         CCGFace *f = CCGSUBSURF_alloc(ss,
217                                       sizeof(CCGFace) +
218                                       sizeof(CCGVert *) * numVerts +
219                                       sizeof(CCGEdge *) * numVerts +
220                                       ss->meshIFC.vertDataSize * num_face_data +
221                                       ss->meshIFC.faceUserSize);
222         byte *userData;
223         int i;
224
225         f->numVerts = numVerts;
226         f->fHDL = fHDL;
227         f->flags = 0;
228
229         for (i = 0; i < numVerts; i++) {
230                 FACE_getVerts(f)[i] = verts[i];
231                 FACE_getEdges(f)[i] = edges[i];
232                 _vert_addFace(verts[i], f, ss);
233                 _edge_addFace(edges[i], f, ss);
234         }
235
236         userData = ccgSubSurf_getFaceUserData(ss, f);
237         memset(userData, 0, ss->meshIFC.faceUserSize);
238         if (ss->useAgeCounts) *((int *) &userData[ss->faceUserAgeOffset]) = ss->currentAge;
239
240         return f;
241 }
242 static void _face_free(CCGFace *f, CCGSubSurf *ss)
243 {
244         CCGSUBSURF_free(ss, f);
245 }
246 static void _face_unlinkMarkAndFree(CCGFace *f, CCGSubSurf *ss)
247 {
248         int j;
249         for (j = 0; j < f->numVerts; j++) {
250                 _vert_remFace(FACE_getVerts(f)[j], f);
251                 _edge_remFace(FACE_getEdges(f)[j], f);
252                 FACE_getVerts(f)[j]->flags |= Vert_eEffected;
253         }
254         _face_free(f, ss);
255 }
256
257 /***/
258
259 CCGSubSurf *ccgSubSurf_new(CCGMeshIFC *ifc, int subdivLevels, CCGAllocatorIFC *allocatorIFC, CCGAllocatorHDL allocator)
260 {
261         if (!allocatorIFC) {
262                 allocatorIFC = ccg_getStandardAllocatorIFC();
263                 allocator = NULL;
264         }
265
266         if (subdivLevels < 1) {
267                 return NULL;
268         }
269         else {
270                 CCGSubSurf *ss = allocatorIFC->alloc(allocator, sizeof(*ss));
271
272                 ss->allocatorIFC = *allocatorIFC;
273                 ss->allocator = allocator;
274
275                 ss->vMap = ccg_ehash_new(0, &ss->allocatorIFC, ss->allocator);
276                 ss->eMap = ccg_ehash_new(0, &ss->allocatorIFC, ss->allocator);
277                 ss->fMap = ccg_ehash_new(0, &ss->allocatorIFC, ss->allocator);
278
279                 ss->meshIFC = *ifc;
280                 
281                 ss->subdivLevels = subdivLevels;
282                 ss->numGrids = 0;
283                 ss->allowEdgeCreation = 0;
284                 ss->defaultCreaseValue = 0;
285                 ss->defaultEdgeUserData = NULL;
286
287                 ss->useAgeCounts = 0;
288                 ss->vertUserAgeOffset = ss->edgeUserAgeOffset = ss->faceUserAgeOffset = 0;
289
290                 ss->calcVertNormals = 0;
291                 ss->normalDataOffset = 0;
292
293                 ss->allocMask = 0;
294
295                 ss->q = CCGSUBSURF_alloc(ss, ss->meshIFC.vertDataSize);
296                 ss->r = CCGSUBSURF_alloc(ss, ss->meshIFC.vertDataSize);
297
298                 ss->currentAge = 0;
299
300                 ss->syncState = eSyncState_None;
301
302                 ss->oldVMap = ss->oldEMap = ss->oldFMap = NULL;
303                 ss->lenTempArrays = 0;
304                 ss->tempVerts = NULL;
305                 ss->tempEdges = NULL;
306
307 #ifdef WITH_OPENSUBDIV
308                 ss->osd_evaluator = NULL;
309                 ss->osd_mesh = NULL;
310                 ss->osd_topology_refiner = NULL;
311                 ss->osd_mesh_invalid = false;
312                 ss->osd_coarse_coords_invalid = false;
313                 ss->osd_vao = 0;
314                 ss->skip_grids = false;
315                 ss->osd_compute = 0;
316                 ss->osd_uvs_invalid = true;
317                 ss->osd_subsurf_uv = 0;
318                 ss->osd_uv_index = -1;
319                 ss->osd_next_face_ptex_index = 0;
320                 ss->osd_coarse_coords = NULL;
321                 ss->osd_num_coarse_coords = 0;
322 #endif
323
324                 return ss;
325         }
326 }
327
328 void ccgSubSurf_free(CCGSubSurf *ss)
329 {
330         CCGAllocatorIFC allocatorIFC = ss->allocatorIFC;
331         CCGAllocatorHDL allocator = ss->allocator;
332 #ifdef WITH_OPENSUBDIV
333         if (ss->osd_evaluator != NULL) {
334                 openSubdiv_deleteEvaluatorDescr(ss->osd_evaluator);
335         }
336         if (ss->osd_mesh != NULL) {
337                 /* TODO(sergey): Make sure free happens form the main thread! */
338                 openSubdiv_deleteOsdGLMesh(ss->osd_mesh);
339         }
340         if (ss->osd_vao != 0) {
341                 glDeleteVertexArrays(1, &ss->osd_vao);
342         }
343         if (ss->osd_coarse_coords != NULL) {
344                 MEM_freeN(ss->osd_coarse_coords);
345         }
346         if (ss->osd_topology_refiner != NULL) {
347                 openSubdiv_deleteTopologyRefinerDescr(ss->osd_topology_refiner);
348         }
349 #endif
350
351         if (ss->syncState) {
352                 ccg_ehash_free(ss->oldFMap, (EHEntryFreeFP) _face_free, ss);
353                 ccg_ehash_free(ss->oldEMap, (EHEntryFreeFP) _edge_free, ss);
354                 ccg_ehash_free(ss->oldVMap, (EHEntryFreeFP) _vert_free, ss);
355
356                 MEM_freeN(ss->tempVerts);
357                 MEM_freeN(ss->tempEdges);
358         }
359
360         CCGSUBSURF_free(ss, ss->r);
361         CCGSUBSURF_free(ss, ss->q);
362         if (ss->defaultEdgeUserData) CCGSUBSURF_free(ss, ss->defaultEdgeUserData);
363
364         ccg_ehash_free(ss->fMap, (EHEntryFreeFP) _face_free, ss);
365         ccg_ehash_free(ss->eMap, (EHEntryFreeFP) _edge_free, ss);
366         ccg_ehash_free(ss->vMap, (EHEntryFreeFP) _vert_free, ss);
367
368         CCGSUBSURF_free(ss, ss);
369
370         if (allocatorIFC.release) {
371                 allocatorIFC.release(allocator);
372         }
373 }
374
375 CCGError ccgSubSurf_setAllowEdgeCreation(CCGSubSurf *ss, int allowEdgeCreation, float defaultCreaseValue, void *defaultUserData)
376 {
377         if (ss->defaultEdgeUserData) {
378                 CCGSUBSURF_free(ss, ss->defaultEdgeUserData);
379         }
380
381         ss->allowEdgeCreation = !!allowEdgeCreation;
382         ss->defaultCreaseValue = defaultCreaseValue;
383         ss->defaultEdgeUserData = CCGSUBSURF_alloc(ss, ss->meshIFC.edgeUserSize);
384
385         if (defaultUserData) {
386                 memcpy(ss->defaultEdgeUserData, defaultUserData, ss->meshIFC.edgeUserSize);
387         }
388         else {
389                 memset(ss->defaultEdgeUserData, 0, ss->meshIFC.edgeUserSize);
390         }
391
392         return eCCGError_None;
393 }
394 void ccgSubSurf_getAllowEdgeCreation(CCGSubSurf *ss, int *allowEdgeCreation_r, float *defaultCreaseValue_r, void *defaultUserData_r)
395 {
396         if (allowEdgeCreation_r) *allowEdgeCreation_r = ss->allowEdgeCreation;
397         if (ss->allowEdgeCreation) {
398                 if (defaultCreaseValue_r) *defaultCreaseValue_r = ss->defaultCreaseValue;
399                 if (defaultUserData_r) memcpy(defaultUserData_r, ss->defaultEdgeUserData, ss->meshIFC.edgeUserSize);
400         }
401 }
402
403 CCGError ccgSubSurf_setSubdivisionLevels(CCGSubSurf *ss, int subdivisionLevels)
404 {
405         if (subdivisionLevels <= 0) {
406                 return eCCGError_InvalidValue;
407         }
408         else if (subdivisionLevels != ss->subdivLevels) {
409                 ss->numGrids = 0;
410                 ss->subdivLevels = subdivisionLevels;
411                 ccg_ehash_free(ss->vMap, (EHEntryFreeFP) _vert_free, ss);
412                 ccg_ehash_free(ss->eMap, (EHEntryFreeFP) _edge_free, ss);
413                 ccg_ehash_free(ss->fMap, (EHEntryFreeFP) _face_free, ss);
414                 ss->vMap = ccg_ehash_new(0, &ss->allocatorIFC, ss->allocator);
415                 ss->eMap = ccg_ehash_new(0, &ss->allocatorIFC, ss->allocator);
416                 ss->fMap = ccg_ehash_new(0, &ss->allocatorIFC, ss->allocator);
417         }
418
419         return eCCGError_None;
420 }
421
422 void ccgSubSurf_getUseAgeCounts(CCGSubSurf *ss, int *useAgeCounts_r, int *vertUserOffset_r, int *edgeUserOffset_r, int *faceUserOffset_r)
423 {
424         *useAgeCounts_r = ss->useAgeCounts;
425
426         if (vertUserOffset_r) *vertUserOffset_r = ss->vertUserAgeOffset;
427         if (edgeUserOffset_r) *edgeUserOffset_r = ss->edgeUserAgeOffset;
428         if (faceUserOffset_r) *faceUserOffset_r = ss->faceUserAgeOffset;
429 }
430
431 CCGError ccgSubSurf_setUseAgeCounts(CCGSubSurf *ss, int useAgeCounts, int vertUserOffset, int edgeUserOffset, int faceUserOffset)
432 {
433         if (useAgeCounts) {
434                 if ((vertUserOffset + 4 > ss->meshIFC.vertUserSize) ||
435                     (edgeUserOffset + 4 > ss->meshIFC.edgeUserSize) ||
436                     (faceUserOffset + 4 > ss->meshIFC.faceUserSize))
437                 {
438                         return eCCGError_InvalidValue;
439                 }
440                 else {
441                         ss->useAgeCounts = 1;
442                         ss->vertUserAgeOffset = vertUserOffset;
443                         ss->edgeUserAgeOffset = edgeUserOffset;
444                         ss->faceUserAgeOffset = faceUserOffset;
445                 }
446         }
447         else {
448                 ss->useAgeCounts = 0;
449                 ss->vertUserAgeOffset = ss->edgeUserAgeOffset = ss->faceUserAgeOffset = 0;
450         }
451
452         return eCCGError_None;
453 }
454
455 CCGError ccgSubSurf_setCalcVertexNormals(CCGSubSurf *ss, int useVertNormals, int normalDataOffset)
456 {
457         if (useVertNormals) {
458                 if (normalDataOffset < 0 || normalDataOffset + 12 > ss->meshIFC.vertDataSize) {
459                         return eCCGError_InvalidValue;
460                 }
461                 else {
462                         ss->calcVertNormals = 1;
463                         ss->normalDataOffset = normalDataOffset;
464                 }
465         }
466         else {
467                 ss->calcVertNormals = 0;
468                 ss->normalDataOffset = 0;
469         }
470
471         return eCCGError_None;
472 }
473
474 void ccgSubSurf_setAllocMask(CCGSubSurf *ss, int allocMask, int maskOffset)
475 {
476         ss->allocMask = allocMask;
477         ss->maskDataOffset = maskOffset;
478 }
479
480 void ccgSubSurf_setNumLayers(CCGSubSurf *ss, int numLayers)
481 {
482         ss->meshIFC.numLayers = numLayers;
483 }
484
485 /***/
486
487 CCGError ccgSubSurf_initFullSync(CCGSubSurf *ss)
488 {
489         if (ss->syncState != eSyncState_None) {
490                 return eCCGError_InvalidSyncState;
491         }
492
493         ss->currentAge++;
494
495         ss->oldVMap = ss->vMap; 
496         ss->oldEMap = ss->eMap; 
497         ss->oldFMap = ss->fMap;
498
499         ss->vMap = ccg_ehash_new(0, &ss->allocatorIFC, ss->allocator);
500         ss->eMap = ccg_ehash_new(0, &ss->allocatorIFC, ss->allocator);
501         ss->fMap = ccg_ehash_new(0, &ss->allocatorIFC, ss->allocator);
502
503         ss->numGrids = 0;
504
505         ss->lenTempArrays = 12;
506         ss->tempVerts = MEM_mallocN(sizeof(*ss->tempVerts) * ss->lenTempArrays, "CCGSubsurf tempVerts");
507         ss->tempEdges = MEM_mallocN(sizeof(*ss->tempEdges) * ss->lenTempArrays, "CCGSubsurf tempEdges");
508
509         ss->syncState = eSyncState_Vert;
510 #ifdef WITH_OPENSUBDIV
511         ss->osd_next_face_ptex_index = 0;
512 #endif
513
514         return eCCGError_None;
515 }
516
517 CCGError ccgSubSurf_initPartialSync(CCGSubSurf *ss)
518 {
519         if (ss->syncState != eSyncState_None) {
520                 return eCCGError_InvalidSyncState;
521         }
522
523         ss->currentAge++;
524
525         ss->syncState = eSyncState_Partial;
526
527         return eCCGError_None;
528 }
529
530 CCGError ccgSubSurf_syncVertDel(CCGSubSurf *ss, CCGVertHDL vHDL)
531 {
532         if (ss->syncState != eSyncState_Partial) {
533                 return eCCGError_InvalidSyncState;
534         }
535         else {
536                 void **prevp;
537                 CCGVert *v = ccg_ehash_lookupWithPrev(ss->vMap, vHDL, &prevp);
538
539                 if (!v || v->numFaces || v->numEdges) {
540                         return eCCGError_InvalidValue;
541                 }
542                 else {
543                         *prevp = v->next;
544                         _vert_free(v, ss);
545                 }
546         }
547
548         return eCCGError_None;
549 }
550
551 CCGError ccgSubSurf_syncEdgeDel(CCGSubSurf *ss, CCGEdgeHDL eHDL)
552 {
553         if (ss->syncState != eSyncState_Partial) {
554                 return eCCGError_InvalidSyncState;
555         }
556         else {
557                 void **prevp;
558                 CCGEdge *e = ccg_ehash_lookupWithPrev(ss->eMap, eHDL, &prevp);
559
560                 if (!e || e->numFaces) {
561                         return eCCGError_InvalidValue;
562                 }
563                 else {
564                         *prevp = e->next;
565                         _edge_unlinkMarkAndFree(e, ss);
566                 }
567         }
568
569         return eCCGError_None;
570 }
571
572 CCGError ccgSubSurf_syncFaceDel(CCGSubSurf *ss, CCGFaceHDL fHDL)
573 {
574         if (ss->syncState != eSyncState_Partial) {
575                 return eCCGError_InvalidSyncState;
576         }
577         else {
578                 void **prevp;
579                 CCGFace *f = ccg_ehash_lookupWithPrev(ss->fMap, fHDL, &prevp);
580
581                 if (!f) {
582                         return eCCGError_InvalidValue;
583                 }
584                 else {
585                         *prevp = f->next;
586                         _face_unlinkMarkAndFree(f, ss);
587                 }
588         }
589
590         return eCCGError_None;
591 }
592
593 CCGError ccgSubSurf_syncVert(CCGSubSurf *ss, CCGVertHDL vHDL, const void *vertData, int seam, CCGVert **v_r)
594 {
595         void **prevp;
596         CCGVert *v = NULL;
597         short seamflag = (seam) ? Vert_eSeam : 0;
598         
599         if (ss->syncState == eSyncState_Partial) {
600                 v = ccg_ehash_lookupWithPrev(ss->vMap, vHDL, &prevp);
601                 if (!v) {
602                         v = _vert_new(vHDL, ss);
603                         VertDataCopy(ccg_vert_getCo(v, 0, ss->meshIFC.vertDataSize), vertData, ss);
604                         ccg_ehash_insert(ss->vMap, (EHEntry *) v);
605                         v->flags = Vert_eEffected | seamflag;
606                 }
607                 else if (!VertDataEqual(vertData, ccg_vert_getCo(v, 0, ss->meshIFC.vertDataSize), ss) ||
608                          ((v->flags & Vert_eSeam) != seamflag))
609                 {
610                         int i, j;
611
612                         VertDataCopy(ccg_vert_getCo(v, 0, ss->meshIFC.vertDataSize), vertData, ss);
613                         v->flags = Vert_eEffected | seamflag;
614
615                         for (i = 0; i < v->numEdges; i++) {
616                                 CCGEdge *e = v->edges[i];
617                                 e->v0->flags |= Vert_eEffected;
618                                 e->v1->flags |= Vert_eEffected;
619                         }
620                         for (i = 0; i < v->numFaces; i++) {
621                                 CCGFace *f = v->faces[i];
622                                 for (j = 0; j < f->numVerts; j++) {
623                                         FACE_getVerts(f)[j]->flags |= Vert_eEffected;
624                                 }
625                         }
626                 }
627         }
628         else {
629                 if (ss->syncState != eSyncState_Vert) {
630                         return eCCGError_InvalidSyncState;
631                 }
632
633                 v = ccg_ehash_lookupWithPrev(ss->oldVMap, vHDL, &prevp);
634                 if (!v) {
635                         v = _vert_new(vHDL, ss);
636                         VertDataCopy(ccg_vert_getCo(v, 0, ss->meshIFC.vertDataSize), vertData, ss);
637                         ccg_ehash_insert(ss->vMap, (EHEntry *) v);
638                         v->flags = Vert_eEffected | seamflag;
639                 }
640                 else if (!VertDataEqual(vertData, ccg_vert_getCo(v, 0, ss->meshIFC.vertDataSize), ss) ||
641                          ((v->flags & Vert_eSeam) != seamflag))
642                 {
643                         *prevp = v->next;
644                         ccg_ehash_insert(ss->vMap, (EHEntry *) v);
645                         VertDataCopy(ccg_vert_getCo(v, 0, ss->meshIFC.vertDataSize), vertData, ss);
646                         v->flags = Vert_eEffected | Vert_eChanged | seamflag;
647                 }
648                 else {
649                         *prevp = v->next;
650                         ccg_ehash_insert(ss->vMap, (EHEntry *) v);
651                         v->flags = 0;
652                 }
653 #ifdef WITH_OPENSUBDIV
654                 v->osd_index = ss->vMap->numEntries - 1;
655 #endif
656         }
657
658         if (v_r) *v_r = v;
659         return eCCGError_None;
660 }
661
662 CCGError ccgSubSurf_syncEdge(CCGSubSurf *ss, CCGEdgeHDL eHDL, CCGVertHDL e_vHDL0, CCGVertHDL e_vHDL1, float crease, CCGEdge **e_r)
663 {
664         void **prevp;
665         CCGEdge *e = NULL, *eNew;
666
667         if (ss->syncState == eSyncState_Partial) {
668                 e = ccg_ehash_lookupWithPrev(ss->eMap, eHDL, &prevp);
669                 if (!e || e->v0->vHDL != e_vHDL0 || e->v1->vHDL != e_vHDL1 || crease != e->crease) {
670                         CCGVert *v0 = ccg_ehash_lookup(ss->vMap, e_vHDL0);
671                         CCGVert *v1 = ccg_ehash_lookup(ss->vMap, e_vHDL1);
672
673                         eNew = _edge_new(eHDL, v0, v1, crease, ss);
674
675                         if (e) {
676                                 *prevp = eNew;
677                                 eNew->next = e->next;
678
679                                 _edge_unlinkMarkAndFree(e, ss);
680                         }
681                         else {
682                                 ccg_ehash_insert(ss->eMap, (EHEntry *) eNew);
683                         }
684
685                         eNew->v0->flags |= Vert_eEffected;
686                         eNew->v1->flags |= Vert_eEffected;
687                 }
688         }
689         else {
690                 if (ss->syncState == eSyncState_Vert) {
691                         ss->syncState = eSyncState_Edge;
692                 }
693                 else if (ss->syncState != eSyncState_Edge) {
694                         return eCCGError_InvalidSyncState;
695                 }
696
697                 e = ccg_ehash_lookupWithPrev(ss->oldEMap, eHDL, &prevp);
698                 if (!e || e->v0->vHDL != e_vHDL0 || e->v1->vHDL != e_vHDL1 || e->crease != crease) {
699                         CCGVert *v0 = ccg_ehash_lookup(ss->vMap, e_vHDL0);
700                         CCGVert *v1 = ccg_ehash_lookup(ss->vMap, e_vHDL1);
701                         e = _edge_new(eHDL, v0, v1, crease, ss);
702                         ccg_ehash_insert(ss->eMap, (EHEntry *) e);
703                         e->v0->flags |= Vert_eEffected;
704                         e->v1->flags |= Vert_eEffected;
705                 }
706                 else {
707                         *prevp = e->next;
708                         ccg_ehash_insert(ss->eMap, (EHEntry *) e);
709                         e->flags = 0;
710                         if ((e->v0->flags | e->v1->flags) & Vert_eChanged) {
711                                 e->v0->flags |= Vert_eEffected;
712                                 e->v1->flags |= Vert_eEffected;
713                         }
714                 }
715         }
716
717         if (e_r) *e_r = e;
718         return eCCGError_None;
719 }
720
721 CCGError ccgSubSurf_syncFace(CCGSubSurf *ss, CCGFaceHDL fHDL, int numVerts, CCGVertHDL *vHDLs, CCGFace **f_r)
722 {
723         void **prevp;
724         CCGFace *f = NULL, *fNew;
725         int j, k, topologyChanged = 0;
726
727         if (UNLIKELY(numVerts > ss->lenTempArrays)) {
728                 ss->lenTempArrays = (numVerts < ss->lenTempArrays * 2) ? ss->lenTempArrays * 2 : numVerts;
729                 ss->tempVerts = MEM_reallocN(ss->tempVerts, sizeof(*ss->tempVerts) * ss->lenTempArrays);
730                 ss->tempEdges = MEM_reallocN(ss->tempEdges, sizeof(*ss->tempEdges) * ss->lenTempArrays);
731         }
732
733         if (ss->syncState == eSyncState_Partial) {
734                 f = ccg_ehash_lookupWithPrev(ss->fMap, fHDL, &prevp);
735
736                 for (k = 0; k < numVerts; k++) {
737                         ss->tempVerts[k] = ccg_ehash_lookup(ss->vMap, vHDLs[k]);
738                 }
739                 for (k = 0; k < numVerts; k++) {
740                         ss->tempEdges[k] = _vert_findEdgeTo(ss->tempVerts[k], ss->tempVerts[(k + 1) % numVerts]);
741                 }
742
743                 if (f) {
744                         if (f->numVerts != numVerts ||
745                             memcmp(FACE_getVerts(f), ss->tempVerts, sizeof(*ss->tempVerts) * numVerts) ||
746                             memcmp(FACE_getEdges(f), ss->tempEdges, sizeof(*ss->tempEdges) * numVerts))
747                         {
748                                 topologyChanged = 1;
749                         }
750                 }
751
752                 if (!f || topologyChanged) {
753                         fNew = _face_new(fHDL, ss->tempVerts, ss->tempEdges, numVerts, ss);
754
755                         if (f) {
756                                 ss->numGrids += numVerts - f->numVerts;
757
758                                 *prevp = fNew;
759                                 fNew->next = f->next;
760
761                                 _face_unlinkMarkAndFree(f, ss);
762                         }
763                         else {
764                                 ss->numGrids += numVerts;
765                                 ccg_ehash_insert(ss->fMap, (EHEntry *) fNew);
766                         }
767
768                         for (k = 0; k < numVerts; k++)
769                                 FACE_getVerts(fNew)[k]->flags |= Vert_eEffected;
770                 }
771         }
772         else {
773                 if (ss->syncState == eSyncState_Vert || ss->syncState == eSyncState_Edge) {
774                         ss->syncState = eSyncState_Face;
775                 }
776                 else if (ss->syncState != eSyncState_Face) {
777                         return eCCGError_InvalidSyncState;
778                 }
779
780                 f = ccg_ehash_lookupWithPrev(ss->oldFMap, fHDL, &prevp);
781
782                 for (k = 0; k < numVerts; k++) {
783                         ss->tempVerts[k] = ccg_ehash_lookup(ss->vMap, vHDLs[k]);
784
785                         if (!ss->tempVerts[k])
786                                 return eCCGError_InvalidValue;
787                 }
788                 for (k = 0; k < numVerts; k++) {
789                         ss->tempEdges[k] = _vert_findEdgeTo(ss->tempVerts[k], ss->tempVerts[(k + 1) % numVerts]);
790
791                         if (!ss->tempEdges[k]) {
792                                 if (ss->allowEdgeCreation) {
793                                         CCGEdge *e = ss->tempEdges[k] = _edge_new((CCGEdgeHDL) - 1, ss->tempVerts[k], ss->tempVerts[(k + 1) % numVerts], ss->defaultCreaseValue, ss);
794                                         ccg_ehash_insert(ss->eMap, (EHEntry *) e);
795                                         e->v0->flags |= Vert_eEffected;
796                                         e->v1->flags |= Vert_eEffected;
797                                         if (ss->meshIFC.edgeUserSize) {
798                                                 memcpy(ccgSubSurf_getEdgeUserData(ss, e), ss->defaultEdgeUserData, ss->meshIFC.edgeUserSize);
799                                         }
800                                 }
801                                 else {
802                                         return eCCGError_InvalidValue;
803                                 }
804                         }
805                 }
806
807                 if (f) {
808                         if (f->numVerts != numVerts ||
809                             memcmp(FACE_getVerts(f), ss->tempVerts, sizeof(*ss->tempVerts) * numVerts) ||
810                             memcmp(FACE_getEdges(f), ss->tempEdges, sizeof(*ss->tempEdges) * numVerts))
811                         {
812                                 topologyChanged = 1;
813                         }
814                 }
815
816                 if (!f || topologyChanged) {
817                         f = _face_new(fHDL, ss->tempVerts, ss->tempEdges, numVerts, ss);
818                         ccg_ehash_insert(ss->fMap, (EHEntry *) f);
819                         ss->numGrids += numVerts;
820
821                         for (k = 0; k < numVerts; k++)
822                                 FACE_getVerts(f)[k]->flags |= Vert_eEffected;
823                 }
824                 else {
825                         *prevp = f->next;
826                         ccg_ehash_insert(ss->fMap, (EHEntry *) f);
827                         f->flags = 0;
828                         ss->numGrids += f->numVerts;
829
830                         for (j = 0; j < f->numVerts; j++) {
831                                 if (FACE_getVerts(f)[j]->flags & Vert_eChanged) {
832                                         for (k = 0; k < f->numVerts; k++)
833                                                 FACE_getVerts(f)[k]->flags |= Vert_eEffected;
834                                         break;
835                                 }
836                         }
837                 }
838 #ifdef WITH_OPENSUBDIV
839                 f->osd_index = ss->osd_next_face_ptex_index;
840                 if (numVerts == 4) {
841                         ss->osd_next_face_ptex_index++;
842                 }
843                 else {
844                         ss->osd_next_face_ptex_index += numVerts;
845                 }
846 #endif
847         }
848
849         if (f_r) *f_r = f;
850         return eCCGError_None;
851 }
852
853 static void ccgSubSurf__sync(CCGSubSurf *ss)
854 {
855 #ifdef WITH_OPENSUBDIV
856         if (ss->skip_grids) {
857                 ccgSubSurf__sync_opensubdiv(ss);
858         }
859         else
860 #endif
861         {
862                 ccgSubSurf__sync_legacy(ss);
863         }
864 }
865
866 CCGError ccgSubSurf_processSync(CCGSubSurf *ss)
867 {
868         if (ss->syncState == eSyncState_Partial) {
869                 ss->syncState = eSyncState_None;
870
871                 ccgSubSurf__sync(ss);
872         }
873         else if (ss->syncState) {
874                 ccg_ehash_free(ss->oldFMap, (EHEntryFreeFP) _face_unlinkMarkAndFree, ss);
875                 ccg_ehash_free(ss->oldEMap, (EHEntryFreeFP) _edge_unlinkMarkAndFree, ss);
876                 ccg_ehash_free(ss->oldVMap, (EHEntryFreeFP) _vert_free, ss);
877                 MEM_freeN(ss->tempEdges);
878                 MEM_freeN(ss->tempVerts);
879
880                 ss->lenTempArrays = 0;
881
882                 ss->oldFMap = ss->oldEMap = ss->oldVMap = NULL;
883                 ss->tempVerts = NULL;
884                 ss->tempEdges = NULL;
885
886                 ss->syncState = eSyncState_None;
887
888                 ccgSubSurf__sync(ss);
889         }
890         else {
891                 return eCCGError_InvalidSyncState;
892         }
893
894         return eCCGError_None;
895 }
896
897 void ccgSubSurf__allFaces(CCGSubSurf *ss, CCGFace ***faces, int *numFaces, int *freeFaces)
898 {
899         CCGFace **array;
900         int i, num;
901
902         if (*faces == NULL) {
903                 array = MEM_mallocN(sizeof(*array) * ss->fMap->numEntries, "CCGSubsurf allFaces");
904                 num = 0;
905                 for (i = 0; i < ss->fMap->curSize; i++) {
906                         CCGFace *f = (CCGFace *) ss->fMap->buckets[i];
907
908                         for (; f; f = f->next)
909                                 array[num++] = f;
910                 }
911
912                 *faces = array;
913                 *numFaces = num;
914                 *freeFaces = 1;
915         }
916         else {
917                 *freeFaces = 0;
918         }
919 }
920
921 void ccgSubSurf__effectedFaceNeighbours(CCGSubSurf *ss, CCGFace **faces, int numFaces, CCGVert ***verts, int *numVerts, CCGEdge ***edges, int *numEdges)
922 {
923         CCGVert **arrayV;
924         CCGEdge **arrayE;
925         int numV, numE, i, j;
926
927         arrayV = MEM_mallocN(sizeof(*arrayV) * ss->vMap->numEntries, "CCGSubsurf arrayV");
928         arrayE = MEM_mallocN(sizeof(*arrayE) * ss->eMap->numEntries, "CCGSubsurf arrayV");
929         numV = numE = 0;
930
931         for (i = 0; i < numFaces; i++) {
932                 CCGFace *f = faces[i];
933                 f->flags |= Face_eEffected;
934         }
935
936         for (i = 0; i < ss->vMap->curSize; i++) {
937                 CCGVert *v = (CCGVert *) ss->vMap->buckets[i];
938
939                 for (; v; v = v->next) {
940                         for (j = 0; j < v->numFaces; j++)
941                                 if (!(v->faces[j]->flags & Face_eEffected))
942                                         break;
943                         
944                         if (j == v->numFaces) {
945                                 arrayV[numV++] = v;
946                                 v->flags |= Vert_eEffected;
947                         }
948                 }
949         }
950
951         for (i = 0; i < ss->eMap->curSize; i++) {
952                 CCGEdge *e = (CCGEdge *) ss->eMap->buckets[i];
953
954                 for (; e; e = e->next) {
955                         for (j = 0; j < e->numFaces; j++)
956                                 if (!(e->faces[j]->flags & Face_eEffected))
957                                         break;
958                         
959                         if (j == e->numFaces) {
960                                 e->flags |= Edge_eEffected;
961                                 arrayE[numE++] = e;
962                         }
963                 }
964         }
965
966         *verts = arrayV;
967         *numVerts = numV;
968         *edges = arrayE;
969         *numEdges = numE;
970 }
971
972 /* copy face grid coordinates to other places */
973 CCGError ccgSubSurf_updateFromFaces(CCGSubSurf *ss, int lvl, CCGFace **effectedF, int numEffectedF)
974 {
975         int i, S, x, gridSize, cornerIdx, subdivLevels;
976         int vertDataSize = ss->meshIFC.vertDataSize, freeF;
977
978         subdivLevels = ss->subdivLevels;
979         lvl = (lvl) ? lvl : subdivLevels;
980         gridSize = ccg_gridsize(lvl);
981         cornerIdx = gridSize - 1;
982
983         ccgSubSurf__allFaces(ss, &effectedF, &numEffectedF, &freeF);
984
985         for (i = 0; i < numEffectedF; i++) {
986                 CCGFace *f = effectedF[i];
987
988                 for (S = 0; S < f->numVerts; S++) {
989                         CCGEdge *e = FACE_getEdges(f)[S];
990                         CCGEdge *prevE = FACE_getEdges(f)[(S + f->numVerts - 1) % f->numVerts];
991
992                         VertDataCopy((float *)FACE_getCenterData(f), FACE_getIFCo(f, lvl, S, 0, 0), ss);
993                         VertDataCopy(VERT_getCo(FACE_getVerts(f)[S], lvl), FACE_getIFCo(f, lvl, S, cornerIdx, cornerIdx), ss);
994
995                         for (x = 0; x < gridSize; x++)
996                                 VertDataCopy(FACE_getIECo(f, lvl, S, x), FACE_getIFCo(f, lvl, S, x, 0), ss);
997
998                         for (x = 0; x < gridSize; x++) {
999                                 int eI = gridSize - 1 - x;
1000                                 VertDataCopy(_edge_getCoVert(e, FACE_getVerts(f)[S], lvl, eI, vertDataSize), FACE_getIFCo(f, lvl, S, cornerIdx, x), ss);
1001                                 VertDataCopy(_edge_getCoVert(prevE, FACE_getVerts(f)[S], lvl, eI, vertDataSize), FACE_getIFCo(f, lvl, S, x, cornerIdx), ss);
1002                         }
1003                 }
1004         }
1005
1006         if (freeF) MEM_freeN(effectedF);
1007
1008         return eCCGError_None;
1009 }
1010
1011 /* copy other places to face grid coordinates */
1012 CCGError ccgSubSurf_updateToFaces(CCGSubSurf *ss, int lvl, CCGFace **effectedF, int numEffectedF)
1013 {
1014         int i, S, x, gridSize, cornerIdx, subdivLevels;
1015         int vertDataSize = ss->meshIFC.vertDataSize, freeF;
1016
1017         subdivLevels = ss->subdivLevels;
1018         lvl = (lvl) ? lvl : subdivLevels;
1019         gridSize = ccg_gridsize(lvl);
1020         cornerIdx = gridSize - 1;
1021
1022         ccgSubSurf__allFaces(ss, &effectedF, &numEffectedF, &freeF);
1023
1024         for (i = 0; i < numEffectedF; i++) {
1025                 CCGFace *f = effectedF[i];
1026
1027                 for (S = 0; S < f->numVerts; S++) {
1028                         int prevS = (S + f->numVerts - 1) % f->numVerts;
1029                         CCGEdge *e = FACE_getEdges(f)[S];
1030                         CCGEdge *prevE = FACE_getEdges(f)[prevS];
1031
1032                         for (x = 0; x < gridSize; x++) {
1033                                 int eI = gridSize - 1 - x;
1034                                 VertDataCopy(FACE_getIFCo(f, lvl, S, cornerIdx, x), _edge_getCoVert(e, FACE_getVerts(f)[S], lvl, eI, vertDataSize), ss);
1035                                 VertDataCopy(FACE_getIFCo(f, lvl, S, x, cornerIdx), _edge_getCoVert(prevE, FACE_getVerts(f)[S], lvl, eI, vertDataSize), ss);
1036                         }
1037
1038                         for (x = 1; x < gridSize - 1; x++) {
1039                                 VertDataCopy(FACE_getIFCo(f, lvl, S, 0, x), FACE_getIECo(f, lvl, prevS, x), ss);
1040                                 VertDataCopy(FACE_getIFCo(f, lvl, S, x, 0), FACE_getIECo(f, lvl, S, x), ss);
1041                         }
1042
1043                         VertDataCopy(FACE_getIFCo(f, lvl, S, 0, 0), (float *)FACE_getCenterData(f), ss);
1044                         VertDataCopy(FACE_getIFCo(f, lvl, S, cornerIdx, cornerIdx), VERT_getCo(FACE_getVerts(f)[S], lvl), ss);
1045                 }
1046         }
1047
1048         if (freeF) MEM_freeN(effectedF);
1049
1050         return eCCGError_None;
1051 }
1052
1053 /* stitch together face grids, averaging coordinates at edges
1054  * and vertices, for multires displacements */
1055 CCGError ccgSubSurf_stitchFaces(CCGSubSurf *ss, int lvl, CCGFace **effectedF, int numEffectedF)
1056 {
1057         CCGVert **effectedV;
1058         CCGEdge **effectedE;
1059         int numEffectedV, numEffectedE, freeF;
1060         int i, S, x, gridSize, cornerIdx, subdivLevels, edgeSize;
1061         int vertDataSize = ss->meshIFC.vertDataSize;
1062
1063         subdivLevels = ss->subdivLevels;
1064         lvl = (lvl) ? lvl : subdivLevels;
1065         gridSize = ccg_gridsize(lvl);
1066         edgeSize = ccg_edgesize(lvl);
1067         cornerIdx = gridSize - 1;
1068
1069         ccgSubSurf__allFaces(ss, &effectedF, &numEffectedF, &freeF);
1070         ccgSubSurf__effectedFaceNeighbours(ss, effectedF, numEffectedF,
1071                                            &effectedV, &numEffectedV, &effectedE, &numEffectedE);
1072
1073         /* zero */
1074         for (i = 0; i < numEffectedV; i++) {
1075                 CCGVert *v = effectedV[i];
1076                 if (v->numFaces)
1077                         VertDataZero(VERT_getCo(v, lvl), ss);
1078         }
1079
1080         for (i = 0; i < numEffectedE; i++) {
1081                 CCGEdge *e = effectedE[i];
1082
1083                 if (e->numFaces)
1084                         for (x = 0; x < edgeSize; x++)
1085                                 VertDataZero(EDGE_getCo(e, lvl, x), ss);
1086         }
1087
1088         /* add */
1089         for (i = 0; i < numEffectedF; i++) {
1090                 CCGFace *f = effectedF[i];
1091
1092                 VertDataZero((float *)FACE_getCenterData(f), ss);
1093
1094                 for (S = 0; S < f->numVerts; S++)
1095                         for (x = 0; x < gridSize; x++)
1096                                 VertDataZero(FACE_getIECo(f, lvl, S, x), ss);
1097
1098                 for (S = 0; S < f->numVerts; S++) {
1099                         int prevS = (S + f->numVerts - 1) % f->numVerts;
1100                         CCGEdge *e = FACE_getEdges(f)[S];
1101                         CCGEdge *prevE = FACE_getEdges(f)[prevS];
1102
1103                         VertDataAdd((float *)FACE_getCenterData(f), FACE_getIFCo(f, lvl, S, 0, 0), ss);
1104                         if (FACE_getVerts(f)[S]->flags & Vert_eEffected)
1105                                 VertDataAdd(VERT_getCo(FACE_getVerts(f)[S], lvl), FACE_getIFCo(f, lvl, S, cornerIdx, cornerIdx), ss);
1106
1107                         for (x = 1; x < gridSize - 1; x++) {
1108                                 VertDataAdd(FACE_getIECo(f, lvl, S, x), FACE_getIFCo(f, lvl, S, x, 0), ss);
1109                                 VertDataAdd(FACE_getIECo(f, lvl, prevS, x), FACE_getIFCo(f, lvl, S, 0, x), ss);
1110                         }
1111
1112                         for (x = 0; x < gridSize - 1; x++) {
1113                                 int eI = gridSize - 1 - x;
1114                                 if (FACE_getEdges(f)[S]->flags & Edge_eEffected)
1115                                         VertDataAdd(_edge_getCoVert(e, FACE_getVerts(f)[S], lvl, eI, vertDataSize), FACE_getIFCo(f, lvl, S, cornerIdx, x), ss);
1116                                 if (FACE_getEdges(f)[prevS]->flags & Edge_eEffected)
1117                                         if (x != 0)
1118                                                 VertDataAdd(_edge_getCoVert(prevE, FACE_getVerts(f)[S], lvl, eI, vertDataSize), FACE_getIFCo(f, lvl, S, x, cornerIdx), ss);
1119                         }
1120                 }
1121         }
1122
1123         /* average */
1124         for (i = 0; i < numEffectedV; i++) {
1125                 CCGVert *v = effectedV[i];
1126                 if (v->numFaces)
1127                         VertDataMulN(VERT_getCo(v, lvl), 1.0f / v->numFaces, ss);
1128         }
1129
1130         for (i = 0; i < numEffectedE; i++) {
1131                 CCGEdge *e = effectedE[i];
1132
1133                 VertDataCopy(EDGE_getCo(e, lvl, 0), VERT_getCo(e->v0, lvl), ss);
1134                 VertDataCopy(EDGE_getCo(e, lvl, edgeSize - 1), VERT_getCo(e->v1, lvl), ss);
1135
1136                 if (e->numFaces)
1137                         for (x = 1; x < edgeSize - 1; x++)
1138                                 VertDataMulN(EDGE_getCo(e, lvl, x), 1.0f / e->numFaces, ss);
1139         }
1140
1141         /* copy */
1142         for (i = 0; i < numEffectedF; i++) {
1143                 CCGFace *f = effectedF[i];
1144
1145                 VertDataMulN((float *)FACE_getCenterData(f), 1.0f / f->numVerts, ss);
1146
1147                 for (S = 0; S < f->numVerts; S++)
1148                         for (x = 1; x < gridSize - 1; x++)
1149                                 VertDataMulN(FACE_getIECo(f, lvl, S, x), 0.5f, ss);
1150
1151                 for (S = 0; S < f->numVerts; S++) {
1152                         int prevS = (S + f->numVerts - 1) % f->numVerts;
1153                         CCGEdge *e = FACE_getEdges(f)[S];
1154                         CCGEdge *prevE = FACE_getEdges(f)[prevS];
1155
1156                         VertDataCopy(FACE_getIFCo(f, lvl, S, 0, 0), (float *)FACE_getCenterData(f), ss);
1157                         VertDataCopy(FACE_getIFCo(f, lvl, S, cornerIdx, cornerIdx), VERT_getCo(FACE_getVerts(f)[S], lvl), ss);
1158
1159                         for (x = 1; x < gridSize - 1; x++) {
1160                                 VertDataCopy(FACE_getIFCo(f, lvl, S, x, 0), FACE_getIECo(f, lvl, S, x), ss);
1161                                 VertDataCopy(FACE_getIFCo(f, lvl, S, 0, x), FACE_getIECo(f, lvl, prevS, x), ss);
1162                         }
1163
1164                         for (x = 0; x < gridSize - 1; x++) {
1165                                 int eI = gridSize - 1 - x;
1166
1167                                 VertDataCopy(FACE_getIFCo(f, lvl, S, cornerIdx, x), _edge_getCoVert(e, FACE_getVerts(f)[S], lvl, eI, vertDataSize), ss);
1168                                 VertDataCopy(FACE_getIFCo(f, lvl, S, x, cornerIdx), _edge_getCoVert(prevE, FACE_getVerts(f)[S], lvl, eI, vertDataSize), ss);
1169                         }
1170
1171                         VertDataCopy(FACE_getIECo(f, lvl, S, 0), (float *)FACE_getCenterData(f), ss);
1172                         VertDataCopy(FACE_getIECo(f, lvl, S, gridSize - 1), FACE_getIFCo(f, lvl, S, gridSize - 1, 0), ss);
1173                 }
1174         }
1175
1176         for (i = 0; i < numEffectedV; i++)
1177                 effectedV[i]->flags = 0;
1178         for (i = 0; i < numEffectedE; i++)
1179                 effectedE[i]->flags = 0;
1180         for (i = 0; i < numEffectedF; i++)
1181                 effectedF[i]->flags = 0;
1182
1183         MEM_freeN(effectedE);
1184         MEM_freeN(effectedV);
1185         if (freeF) MEM_freeN(effectedF);
1186
1187         return eCCGError_None;
1188 }
1189
1190 /*** External API accessor functions ***/
1191
1192 int ccgSubSurf_getNumVerts(const CCGSubSurf *ss)
1193 {
1194         return ss->vMap->numEntries;
1195 }
1196 int ccgSubSurf_getNumEdges(const CCGSubSurf *ss)
1197 {
1198         return ss->eMap->numEntries;
1199 }
1200 int ccgSubSurf_getNumFaces(const CCGSubSurf *ss)
1201 {
1202         return ss->fMap->numEntries;
1203 }
1204
1205 CCGVert *ccgSubSurf_getVert(CCGSubSurf *ss, CCGVertHDL v)
1206 {
1207         return (CCGVert *) ccg_ehash_lookup(ss->vMap, v);
1208 }
1209 CCGEdge *ccgSubSurf_getEdge(CCGSubSurf *ss, CCGEdgeHDL e)
1210 {
1211         return (CCGEdge *) ccg_ehash_lookup(ss->eMap, e);
1212 }
1213 CCGFace *ccgSubSurf_getFace(CCGSubSurf *ss, CCGFaceHDL f)
1214 {
1215         return (CCGFace *) ccg_ehash_lookup(ss->fMap, f);
1216 }
1217
1218 int ccgSubSurf_getSubdivisionLevels(const CCGSubSurf *ss)
1219 {
1220         return ss->subdivLevels;
1221 }
1222 int ccgSubSurf_getEdgeSize(const CCGSubSurf *ss)
1223 {
1224         return ccgSubSurf_getEdgeLevelSize(ss, ss->subdivLevels);
1225 }
1226 int ccgSubSurf_getEdgeLevelSize(const CCGSubSurf *ss, int level)
1227 {
1228         if (level < 1 || level > ss->subdivLevels) {
1229                 return -1;
1230         }
1231         else {
1232                 return ccg_edgesize(level);
1233         }
1234 }
1235 int ccgSubSurf_getGridSize(const CCGSubSurf *ss)
1236 {
1237         return ccgSubSurf_getGridLevelSize(ss, ss->subdivLevels);
1238 }
1239 int ccgSubSurf_getGridLevelSize(const CCGSubSurf *ss, int level)
1240 {
1241         if (level < 1 || level > ss->subdivLevels) {
1242                 return -1;
1243         }
1244         else {
1245                 return ccg_gridsize(level);
1246         }
1247 }
1248
1249 int ccgSubSurf_getSimpleSubdiv(const CCGSubSurf *ss)
1250 {
1251         return ss->meshIFC.simpleSubdiv;
1252 }
1253
1254 /* Vert accessors */
1255
1256 CCGVertHDL ccgSubSurf_getVertVertHandle(CCGVert *v)
1257 {
1258         return v->vHDL;
1259 }
1260 int ccgSubSurf_getVertAge(CCGSubSurf *ss, CCGVert *v)
1261 {
1262         if (ss->useAgeCounts) {
1263                 byte *userData = ccgSubSurf_getVertUserData(ss, v);
1264                 return ss->currentAge - *((int *) &userData[ss->vertUserAgeOffset]);
1265         }
1266         else {
1267                 return 0;
1268         }
1269 }
1270 void *ccgSubSurf_getVertUserData(CCGSubSurf *ss, CCGVert *v)
1271 {
1272         return VERT_getLevelData(v) + ss->meshIFC.vertDataSize * (ss->subdivLevels + 1);
1273 }
1274 int ccgSubSurf_getVertNumFaces(CCGVert *v)
1275 {
1276         return v->numFaces;
1277 }
1278 CCGFace *ccgSubSurf_getVertFace(CCGVert *v, int index)
1279 {
1280         if (index < 0 || index >= v->numFaces) {
1281                 return NULL;
1282         }
1283         else {
1284                 return v->faces[index];
1285         }
1286 }
1287 int ccgSubSurf_getVertNumEdges(CCGVert *v)
1288 {
1289         return v->numEdges;
1290 }
1291 CCGEdge *ccgSubSurf_getVertEdge(CCGVert *v, int index)
1292 {
1293         if (index < 0 || index >= v->numEdges) {
1294                 return NULL;
1295         }
1296         else {
1297                 return v->edges[index];
1298         }
1299 }
1300 void *ccgSubSurf_getVertData(CCGSubSurf *ss, CCGVert *v)
1301 {
1302         return ccgSubSurf_getVertLevelData(ss, v, ss->subdivLevels);
1303 }
1304 void *ccgSubSurf_getVertLevelData(CCGSubSurf *ss, CCGVert *v, int level)
1305 {
1306         if (level < 0 || level > ss->subdivLevels) {
1307                 return NULL;
1308         }
1309         else {
1310                 return ccg_vert_getCo(v, level, ss->meshIFC.vertDataSize);
1311         }
1312 }
1313
1314 /* Edge accessors */
1315
1316 CCGEdgeHDL ccgSubSurf_getEdgeEdgeHandle(CCGEdge *e)
1317 {
1318         return e->eHDL;
1319 }
1320 int ccgSubSurf_getEdgeAge(CCGSubSurf *ss, CCGEdge *e)
1321 {
1322         if (ss->useAgeCounts) {
1323                 byte *userData = ccgSubSurf_getEdgeUserData(ss, e);
1324                 return ss->currentAge - *((int *) &userData[ss->edgeUserAgeOffset]);
1325         }
1326         else {
1327                 return 0;
1328         }
1329 }
1330 void *ccgSubSurf_getEdgeUserData(CCGSubSurf *ss, CCGEdge *e)
1331 {
1332         return (EDGE_getLevelData(e) +
1333                 ss->meshIFC.vertDataSize * ccg_edgebase(ss->subdivLevels + 1));
1334 }
1335 int ccgSubSurf_getEdgeNumFaces(CCGEdge *e)
1336 {
1337         return e->numFaces;
1338 }
1339 CCGFace *ccgSubSurf_getEdgeFace(CCGEdge *e, int index)
1340 {
1341         if (index < 0 || index >= e->numFaces) {
1342                 return NULL;
1343         }
1344         else {
1345                 return e->faces[index];
1346         }
1347 }
1348 CCGVert *ccgSubSurf_getEdgeVert0(CCGEdge *e)
1349 {
1350         return e->v0;
1351 }
1352 CCGVert *ccgSubSurf_getEdgeVert1(CCGEdge *e)
1353 {
1354         return e->v1;
1355 }
1356 void *ccgSubSurf_getEdgeDataArray(CCGSubSurf *ss, CCGEdge *e)
1357 {
1358         return ccgSubSurf_getEdgeData(ss, e, 0);
1359 }
1360 void *ccgSubSurf_getEdgeData(CCGSubSurf *ss, CCGEdge *e, int x)
1361 {
1362         return ccgSubSurf_getEdgeLevelData(ss, e, x, ss->subdivLevels);
1363 }
1364 void *ccgSubSurf_getEdgeLevelData(CCGSubSurf *ss, CCGEdge *e, int x, int level)
1365 {
1366         if (level < 0 || level > ss->subdivLevels) {
1367                 return NULL;
1368         }
1369         else {
1370                 return ccg_edge_getCo(e, level, x, ss->meshIFC.vertDataSize);
1371         }
1372 }
1373 float ccgSubSurf_getEdgeCrease(CCGEdge *e)
1374 {
1375         return e->crease;
1376 }
1377
1378 /* Face accessors */
1379
1380 CCGFaceHDL ccgSubSurf_getFaceFaceHandle(CCGFace *f)
1381 {
1382         return f->fHDL;
1383 }
1384 int ccgSubSurf_getFaceAge(CCGSubSurf *ss, CCGFace *f)
1385 {
1386         if (ss->useAgeCounts) {
1387                 byte *userData = ccgSubSurf_getFaceUserData(ss, f);
1388                 return ss->currentAge - *((int *) &userData[ss->faceUserAgeOffset]);
1389         }
1390         else {
1391                 return 0;
1392         }
1393 }
1394 void *ccgSubSurf_getFaceUserData(CCGSubSurf *ss, CCGFace *f)
1395 {
1396         int maxGridSize = ccg_gridsize(ss->subdivLevels);
1397         return FACE_getCenterData(f) + ss->meshIFC.vertDataSize * (1 + f->numVerts * maxGridSize + f->numVerts * maxGridSize * maxGridSize);
1398 }
1399 int ccgSubSurf_getFaceNumVerts(CCGFace *f)
1400 {
1401         return f->numVerts;
1402 }
1403 CCGVert *ccgSubSurf_getFaceVert(CCGFace *f, int index)
1404 {
1405         if (index < 0 || index >= f->numVerts) {
1406                 return NULL;
1407         }
1408         else {
1409                 return FACE_getVerts(f)[index];
1410         }
1411 }
1412 CCGEdge *ccgSubSurf_getFaceEdge(CCGFace *f, int index)
1413 {
1414         if (index < 0 || index >= f->numVerts) {
1415                 return NULL;
1416         }
1417         else {
1418                 return FACE_getEdges(f)[index];
1419         }
1420 }
1421 int ccgSubSurf_getFaceEdgeIndex(CCGFace *f, CCGEdge *e)
1422 {
1423         int i;
1424
1425         for (i = 0; i < f->numVerts; i++) {
1426                 if (FACE_getEdges(f)[i] == e) {
1427                         return i;
1428                 }
1429         }
1430         return -1;
1431 }
1432 void *ccgSubSurf_getFaceCenterData(CCGFace *f)
1433 {
1434         return FACE_getCenterData(f);
1435 }
1436 void *ccgSubSurf_getFaceGridEdgeDataArray(CCGSubSurf *ss, CCGFace *f, int gridIndex)
1437 {
1438         return ccgSubSurf_getFaceGridEdgeData(ss, f, gridIndex, 0);
1439 }
1440 void *ccgSubSurf_getFaceGridEdgeData(CCGSubSurf *ss, CCGFace *f, int gridIndex, int x)
1441 {
1442         return ccg_face_getIECo(f, ss->subdivLevels, gridIndex, x, ss->subdivLevels, ss->meshIFC.vertDataSize);
1443 }
1444 void *ccgSubSurf_getFaceGridDataArray(CCGSubSurf *ss, CCGFace *f, int gridIndex)
1445 {
1446         return ccgSubSurf_getFaceGridData(ss, f, gridIndex, 0, 0);
1447 }
1448 void *ccgSubSurf_getFaceGridData(CCGSubSurf *ss, CCGFace *f, int gridIndex, int x, int y)
1449 {
1450         return ccg_face_getIFCo(f, ss->subdivLevels, gridIndex, x, y, ss->subdivLevels, ss->meshIFC.vertDataSize);
1451 }
1452
1453 /*** External API iterator functions ***/
1454
1455 void ccgSubSurf_initVertIterator(CCGSubSurf *ss, CCGVertIterator *viter)
1456 {
1457         ccg_ehashIterator_init(ss->vMap, viter);
1458 }
1459 void ccgSubSurf_initEdgeIterator(CCGSubSurf *ss, CCGEdgeIterator *eiter)
1460 {
1461         ccg_ehashIterator_init(ss->eMap, eiter);
1462 }
1463 void ccgSubSurf_initFaceIterator(CCGSubSurf *ss, CCGFaceIterator *fiter)
1464 {
1465         ccg_ehashIterator_init(ss->fMap, fiter);
1466 }
1467
1468 CCGVert *ccgVertIterator_getCurrent(CCGVertIterator *vi)
1469 {
1470         return (CCGVert *) ccg_ehashIterator_getCurrent((EHashIterator *) vi);
1471 }
1472 int ccgVertIterator_isStopped(CCGVertIterator *vi)
1473 {
1474         return ccg_ehashIterator_isStopped((EHashIterator *) vi);
1475 }
1476 void ccgVertIterator_next(CCGVertIterator *vi)
1477 {
1478         ccg_ehashIterator_next((EHashIterator *) vi);
1479 }
1480
1481 CCGEdge *ccgEdgeIterator_getCurrent(CCGEdgeIterator *vi)
1482 {
1483         return (CCGEdge *) ccg_ehashIterator_getCurrent((EHashIterator *) vi);
1484 }
1485 int ccgEdgeIterator_isStopped(CCGEdgeIterator *vi)
1486 {
1487         return ccg_ehashIterator_isStopped((EHashIterator *) vi);
1488 }
1489 void ccgEdgeIterator_next(CCGEdgeIterator *vi)
1490 {
1491         ccg_ehashIterator_next((EHashIterator *) vi);
1492 }
1493
1494 CCGFace *ccgFaceIterator_getCurrent(CCGFaceIterator *vi)
1495 {
1496         return (CCGFace *) ccg_ehashIterator_getCurrent((EHashIterator *) vi);
1497 }
1498 int ccgFaceIterator_isStopped(CCGFaceIterator *vi)
1499 {
1500         return ccg_ehashIterator_isStopped((EHashIterator *) vi);
1501 }
1502 void ccgFaceIterator_next(CCGFaceIterator *vi)
1503 {
1504         ccg_ehashIterator_next((EHashIterator *) vi);
1505 }
1506
1507 /*** Extern API final vert/edge/face interface ***/
1508
1509 int ccgSubSurf_getNumFinalVerts(const CCGSubSurf *ss)
1510 {
1511         int edgeSize = ccg_edgesize(ss->subdivLevels);
1512         int gridSize = ccg_gridsize(ss->subdivLevels);
1513         int numFinalVerts = (ss->vMap->numEntries +
1514                              ss->eMap->numEntries * (edgeSize - 2) +
1515                              ss->fMap->numEntries +
1516                              ss->numGrids * ((gridSize - 2) + ((gridSize - 2) * (gridSize - 2))));
1517
1518         return numFinalVerts;
1519 }
1520 int ccgSubSurf_getNumFinalEdges(const CCGSubSurf *ss)
1521 {
1522         int edgeSize = ccg_edgesize(ss->subdivLevels);
1523         int gridSize = ccg_gridsize(ss->subdivLevels);
1524         int numFinalEdges = (ss->eMap->numEntries * (edgeSize - 1) +
1525                              ss->numGrids * ((gridSize - 1) + 2 * ((gridSize - 2) * (gridSize - 1))));
1526
1527         return numFinalEdges;
1528 }
1529 int ccgSubSurf_getNumFinalFaces(const CCGSubSurf *ss)
1530 {
1531         int gridSize = ccg_gridsize(ss->subdivLevels);
1532         int numFinalFaces = ss->numGrids * ((gridSize - 1) * (gridSize - 1));
1533         return numFinalFaces;
1534 }
1535
1536 /***/
1537
1538 void CCG_key(CCGKey *key, const CCGSubSurf *ss, int level)
1539 {
1540         key->level = level;
1541         
1542         key->elem_size = ss->meshIFC.vertDataSize;
1543         key->has_normals = ss->calcVertNormals;
1544         key->num_layers = ss->meshIFC.numLayers;
1545         
1546         /* if normals are present, always the last three floats of an
1547          * element */
1548         if (key->has_normals)
1549                 key->normal_offset = key->elem_size - sizeof(float) * 3;
1550         else
1551                 key->normal_offset = -1;
1552
1553         key->grid_size = ccgSubSurf_getGridLevelSize(ss, level);
1554         key->grid_area = key->grid_size * key->grid_size;
1555         key->grid_bytes = key->elem_size * key->grid_area;
1556
1557         key->has_mask = ss->allocMask;
1558         if (key->has_mask)
1559                 key->mask_offset = ss->maskDataOffset;
1560         else
1561                 key->mask_offset = -1;
1562 }
1563
1564 void CCG_key_top_level(CCGKey *key, const CCGSubSurf *ss)
1565 {
1566         CCG_key(key, ss, ccgSubSurf_getSubdivisionLevels(ss));
1567 }