c4886a2174039a6baae6df70dc85a5ad71e5f7a2
[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_next_face_ptex_index = 0;
317                 ss->osd_coarse_coords = NULL;
318                 ss->osd_num_coarse_coords = 0;
319 #endif
320
321                 return ss;
322         }
323 }
324
325 void ccgSubSurf_free(CCGSubSurf *ss)
326 {
327         CCGAllocatorIFC allocatorIFC = ss->allocatorIFC;
328         CCGAllocatorHDL allocator = ss->allocator;
329 #ifdef WITH_OPENSUBDIV
330         if (ss->osd_evaluator != NULL) {
331                 openSubdiv_deleteEvaluatorDescr(ss->osd_evaluator);
332         }
333         if (ss->osd_mesh != NULL) {
334                 ccgSubSurf__delete_osdGLMesh(ss->osd_mesh);
335         }
336         if (ss->osd_vao != 0) {
337                 ccgSubSurf__delete_vertex_array(ss->osd_vao);
338         }
339         if (ss->osd_coarse_coords != NULL) {
340                 MEM_freeN(ss->osd_coarse_coords);
341         }
342         if (ss->osd_topology_refiner != NULL) {
343                 openSubdiv_deleteTopologyRefinerDescr(ss->osd_topology_refiner);
344         }
345 #endif
346
347         if (ss->syncState) {
348                 ccg_ehash_free(ss->oldFMap, (EHEntryFreeFP) _face_free, ss);
349                 ccg_ehash_free(ss->oldEMap, (EHEntryFreeFP) _edge_free, ss);
350                 ccg_ehash_free(ss->oldVMap, (EHEntryFreeFP) _vert_free, ss);
351
352                 MEM_freeN(ss->tempVerts);
353                 MEM_freeN(ss->tempEdges);
354         }
355
356         CCGSUBSURF_free(ss, ss->r);
357         CCGSUBSURF_free(ss, ss->q);
358         if (ss->defaultEdgeUserData) CCGSUBSURF_free(ss, ss->defaultEdgeUserData);
359
360         ccg_ehash_free(ss->fMap, (EHEntryFreeFP) _face_free, ss);
361         ccg_ehash_free(ss->eMap, (EHEntryFreeFP) _edge_free, ss);
362         ccg_ehash_free(ss->vMap, (EHEntryFreeFP) _vert_free, ss);
363
364         CCGSUBSURF_free(ss, ss);
365
366         if (allocatorIFC.release) {
367                 allocatorIFC.release(allocator);
368         }
369 }
370
371 CCGError ccgSubSurf_setAllowEdgeCreation(CCGSubSurf *ss, int allowEdgeCreation, float defaultCreaseValue, void *defaultUserData)
372 {
373         if (ss->defaultEdgeUserData) {
374                 CCGSUBSURF_free(ss, ss->defaultEdgeUserData);
375         }
376
377         ss->allowEdgeCreation = !!allowEdgeCreation;
378         ss->defaultCreaseValue = defaultCreaseValue;
379         ss->defaultEdgeUserData = CCGSUBSURF_alloc(ss, ss->meshIFC.edgeUserSize);
380
381         if (defaultUserData) {
382                 memcpy(ss->defaultEdgeUserData, defaultUserData, ss->meshIFC.edgeUserSize);
383         }
384         else {
385                 memset(ss->defaultEdgeUserData, 0, ss->meshIFC.edgeUserSize);
386         }
387
388         return eCCGError_None;
389 }
390 void ccgSubSurf_getAllowEdgeCreation(CCGSubSurf *ss, int *allowEdgeCreation_r, float *defaultCreaseValue_r, void *defaultUserData_r)
391 {
392         if (allowEdgeCreation_r) *allowEdgeCreation_r = ss->allowEdgeCreation;
393         if (ss->allowEdgeCreation) {
394                 if (defaultCreaseValue_r) *defaultCreaseValue_r = ss->defaultCreaseValue;
395                 if (defaultUserData_r) memcpy(defaultUserData_r, ss->defaultEdgeUserData, ss->meshIFC.edgeUserSize);
396         }
397 }
398
399 CCGError ccgSubSurf_setSubdivisionLevels(CCGSubSurf *ss, int subdivisionLevels)
400 {
401         if (subdivisionLevels <= 0) {
402                 return eCCGError_InvalidValue;
403         }
404         else if (subdivisionLevels != ss->subdivLevels) {
405                 ss->numGrids = 0;
406                 ss->subdivLevels = subdivisionLevels;
407                 ccg_ehash_free(ss->vMap, (EHEntryFreeFP) _vert_free, ss);
408                 ccg_ehash_free(ss->eMap, (EHEntryFreeFP) _edge_free, ss);
409                 ccg_ehash_free(ss->fMap, (EHEntryFreeFP) _face_free, ss);
410                 ss->vMap = ccg_ehash_new(0, &ss->allocatorIFC, ss->allocator);
411                 ss->eMap = ccg_ehash_new(0, &ss->allocatorIFC, ss->allocator);
412                 ss->fMap = ccg_ehash_new(0, &ss->allocatorIFC, ss->allocator);
413         }
414
415         return eCCGError_None;
416 }
417
418 void ccgSubSurf_getUseAgeCounts(CCGSubSurf *ss, int *useAgeCounts_r, int *vertUserOffset_r, int *edgeUserOffset_r, int *faceUserOffset_r)
419 {
420         *useAgeCounts_r = ss->useAgeCounts;
421
422         if (vertUserOffset_r) *vertUserOffset_r = ss->vertUserAgeOffset;
423         if (edgeUserOffset_r) *edgeUserOffset_r = ss->edgeUserAgeOffset;
424         if (faceUserOffset_r) *faceUserOffset_r = ss->faceUserAgeOffset;
425 }
426
427 CCGError ccgSubSurf_setUseAgeCounts(CCGSubSurf *ss, int useAgeCounts, int vertUserOffset, int edgeUserOffset, int faceUserOffset)
428 {
429         if (useAgeCounts) {
430                 if ((vertUserOffset + 4 > ss->meshIFC.vertUserSize) ||
431                     (edgeUserOffset + 4 > ss->meshIFC.edgeUserSize) ||
432                     (faceUserOffset + 4 > ss->meshIFC.faceUserSize))
433                 {
434                         return eCCGError_InvalidValue;
435                 }
436                 else {
437                         ss->useAgeCounts = 1;
438                         ss->vertUserAgeOffset = vertUserOffset;
439                         ss->edgeUserAgeOffset = edgeUserOffset;
440                         ss->faceUserAgeOffset = faceUserOffset;
441                 }
442         }
443         else {
444                 ss->useAgeCounts = 0;
445                 ss->vertUserAgeOffset = ss->edgeUserAgeOffset = ss->faceUserAgeOffset = 0;
446         }
447
448         return eCCGError_None;
449 }
450
451 CCGError ccgSubSurf_setCalcVertexNormals(CCGSubSurf *ss, int useVertNormals, int normalDataOffset)
452 {
453         if (useVertNormals) {
454                 if (normalDataOffset < 0 || normalDataOffset + 12 > ss->meshIFC.vertDataSize) {
455                         return eCCGError_InvalidValue;
456                 }
457                 else {
458                         ss->calcVertNormals = 1;
459                         ss->normalDataOffset = normalDataOffset;
460                 }
461         }
462         else {
463                 ss->calcVertNormals = 0;
464                 ss->normalDataOffset = 0;
465         }
466
467         return eCCGError_None;
468 }
469
470 void ccgSubSurf_setAllocMask(CCGSubSurf *ss, int allocMask, int maskOffset)
471 {
472         ss->allocMask = allocMask;
473         ss->maskDataOffset = maskOffset;
474 }
475
476 void ccgSubSurf_setNumLayers(CCGSubSurf *ss, int numLayers)
477 {
478         ss->meshIFC.numLayers = numLayers;
479 }
480
481 /***/
482
483 CCGError ccgSubSurf_initFullSync(CCGSubSurf *ss)
484 {
485         if (ss->syncState != eSyncState_None) {
486                 return eCCGError_InvalidSyncState;
487         }
488
489         ss->currentAge++;
490
491         ss->oldVMap = ss->vMap; 
492         ss->oldEMap = ss->eMap; 
493         ss->oldFMap = ss->fMap;
494
495         ss->vMap = ccg_ehash_new(0, &ss->allocatorIFC, ss->allocator);
496         ss->eMap = ccg_ehash_new(0, &ss->allocatorIFC, ss->allocator);
497         ss->fMap = ccg_ehash_new(0, &ss->allocatorIFC, ss->allocator);
498
499         ss->numGrids = 0;
500
501         ss->lenTempArrays = 12;
502         ss->tempVerts = MEM_mallocN(sizeof(*ss->tempVerts) * ss->lenTempArrays, "CCGSubsurf tempVerts");
503         ss->tempEdges = MEM_mallocN(sizeof(*ss->tempEdges) * ss->lenTempArrays, "CCGSubsurf tempEdges");
504
505         ss->syncState = eSyncState_Vert;
506 #ifdef WITH_OPENSUBDIV
507         ss->osd_next_face_ptex_index = 0;
508 #endif
509
510         return eCCGError_None;
511 }
512
513 CCGError ccgSubSurf_initPartialSync(CCGSubSurf *ss)
514 {
515         if (ss->syncState != eSyncState_None) {
516                 return eCCGError_InvalidSyncState;
517         }
518
519         ss->currentAge++;
520
521         ss->syncState = eSyncState_Partial;
522
523         return eCCGError_None;
524 }
525
526 CCGError ccgSubSurf_syncVertDel(CCGSubSurf *ss, CCGVertHDL vHDL)
527 {
528         if (ss->syncState != eSyncState_Partial) {
529                 return eCCGError_InvalidSyncState;
530         }
531         else {
532                 void **prevp;
533                 CCGVert *v = ccg_ehash_lookupWithPrev(ss->vMap, vHDL, &prevp);
534
535                 if (!v || v->numFaces || v->numEdges) {
536                         return eCCGError_InvalidValue;
537                 }
538                 else {
539                         *prevp = v->next;
540                         _vert_free(v, ss);
541                 }
542         }
543
544         return eCCGError_None;
545 }
546
547 CCGError ccgSubSurf_syncEdgeDel(CCGSubSurf *ss, CCGEdgeHDL eHDL)
548 {
549         if (ss->syncState != eSyncState_Partial) {
550                 return eCCGError_InvalidSyncState;
551         }
552         else {
553                 void **prevp;
554                 CCGEdge *e = ccg_ehash_lookupWithPrev(ss->eMap, eHDL, &prevp);
555
556                 if (!e || e->numFaces) {
557                         return eCCGError_InvalidValue;
558                 }
559                 else {
560                         *prevp = e->next;
561                         _edge_unlinkMarkAndFree(e, ss);
562                 }
563         }
564
565         return eCCGError_None;
566 }
567
568 CCGError ccgSubSurf_syncFaceDel(CCGSubSurf *ss, CCGFaceHDL fHDL)
569 {
570         if (ss->syncState != eSyncState_Partial) {
571                 return eCCGError_InvalidSyncState;
572         }
573         else {
574                 void **prevp;
575                 CCGFace *f = ccg_ehash_lookupWithPrev(ss->fMap, fHDL, &prevp);
576
577                 if (!f) {
578                         return eCCGError_InvalidValue;
579                 }
580                 else {
581                         *prevp = f->next;
582                         _face_unlinkMarkAndFree(f, ss);
583                 }
584         }
585
586         return eCCGError_None;
587 }
588
589 CCGError ccgSubSurf_syncVert(CCGSubSurf *ss, CCGVertHDL vHDL, const void *vertData, int seam, CCGVert **v_r)
590 {
591         void **prevp;
592         CCGVert *v = NULL;
593         short seamflag = (seam) ? Vert_eSeam : 0;
594         
595         if (ss->syncState == eSyncState_Partial) {
596                 v = ccg_ehash_lookupWithPrev(ss->vMap, vHDL, &prevp);
597                 if (!v) {
598                         v = _vert_new(vHDL, ss);
599                         VertDataCopy(ccg_vert_getCo(v, 0, ss->meshIFC.vertDataSize), vertData, ss);
600                         ccg_ehash_insert(ss->vMap, (EHEntry *) v);
601                         v->flags = Vert_eEffected | seamflag;
602                 }
603                 else if (!VertDataEqual(vertData, ccg_vert_getCo(v, 0, ss->meshIFC.vertDataSize), ss) ||
604                          ((v->flags & Vert_eSeam) != seamflag))
605                 {
606                         int i, j;
607
608                         VertDataCopy(ccg_vert_getCo(v, 0, ss->meshIFC.vertDataSize), vertData, ss);
609                         v->flags = Vert_eEffected | seamflag;
610
611                         for (i = 0; i < v->numEdges; i++) {
612                                 CCGEdge *e = v->edges[i];
613                                 e->v0->flags |= Vert_eEffected;
614                                 e->v1->flags |= Vert_eEffected;
615                         }
616                         for (i = 0; i < v->numFaces; i++) {
617                                 CCGFace *f = v->faces[i];
618                                 for (j = 0; j < f->numVerts; j++) {
619                                         FACE_getVerts(f)[j]->flags |= Vert_eEffected;
620                                 }
621                         }
622                 }
623         }
624         else {
625                 if (ss->syncState != eSyncState_Vert) {
626                         return eCCGError_InvalidSyncState;
627                 }
628
629                 v = ccg_ehash_lookupWithPrev(ss->oldVMap, vHDL, &prevp);
630                 if (!v) {
631                         v = _vert_new(vHDL, ss);
632                         VertDataCopy(ccg_vert_getCo(v, 0, ss->meshIFC.vertDataSize), vertData, ss);
633                         ccg_ehash_insert(ss->vMap, (EHEntry *) v);
634                         v->flags = Vert_eEffected | seamflag;
635                 }
636                 else if (!VertDataEqual(vertData, ccg_vert_getCo(v, 0, ss->meshIFC.vertDataSize), ss) ||
637                          ((v->flags & Vert_eSeam) != seamflag))
638                 {
639                         *prevp = v->next;
640                         ccg_ehash_insert(ss->vMap, (EHEntry *) v);
641                         VertDataCopy(ccg_vert_getCo(v, 0, ss->meshIFC.vertDataSize), vertData, ss);
642                         v->flags = Vert_eEffected | Vert_eChanged | seamflag;
643                 }
644                 else {
645                         *prevp = v->next;
646                         ccg_ehash_insert(ss->vMap, (EHEntry *) v);
647                         v->flags = 0;
648                 }
649 #ifdef WITH_OPENSUBDIV
650                 v->osd_index = ss->vMap->numEntries - 1;
651 #endif
652         }
653
654         if (v_r) *v_r = v;
655         return eCCGError_None;
656 }
657
658 CCGError ccgSubSurf_syncEdge(CCGSubSurf *ss, CCGEdgeHDL eHDL, CCGVertHDL e_vHDL0, CCGVertHDL e_vHDL1, float crease, CCGEdge **e_r)
659 {
660         void **prevp;
661         CCGEdge *e = NULL, *eNew;
662
663         if (ss->syncState == eSyncState_Partial) {
664                 e = ccg_ehash_lookupWithPrev(ss->eMap, eHDL, &prevp);
665                 if (!e || e->v0->vHDL != e_vHDL0 || e->v1->vHDL != e_vHDL1 || crease != e->crease) {
666                         CCGVert *v0 = ccg_ehash_lookup(ss->vMap, e_vHDL0);
667                         CCGVert *v1 = ccg_ehash_lookup(ss->vMap, e_vHDL1);
668
669                         eNew = _edge_new(eHDL, v0, v1, crease, ss);
670
671                         if (e) {
672                                 *prevp = eNew;
673                                 eNew->next = e->next;
674
675                                 _edge_unlinkMarkAndFree(e, ss);
676                         }
677                         else {
678                                 ccg_ehash_insert(ss->eMap, (EHEntry *) eNew);
679                         }
680
681                         eNew->v0->flags |= Vert_eEffected;
682                         eNew->v1->flags |= Vert_eEffected;
683                 }
684         }
685         else {
686                 if (ss->syncState == eSyncState_Vert) {
687                         ss->syncState = eSyncState_Edge;
688                 }
689                 else if (ss->syncState != eSyncState_Edge) {
690                         return eCCGError_InvalidSyncState;
691                 }
692
693                 e = ccg_ehash_lookupWithPrev(ss->oldEMap, eHDL, &prevp);
694                 if (!e || e->v0->vHDL != e_vHDL0 || e->v1->vHDL != e_vHDL1 || e->crease != crease) {
695                         CCGVert *v0 = ccg_ehash_lookup(ss->vMap, e_vHDL0);
696                         CCGVert *v1 = ccg_ehash_lookup(ss->vMap, e_vHDL1);
697                         e = _edge_new(eHDL, v0, v1, crease, ss);
698                         ccg_ehash_insert(ss->eMap, (EHEntry *) e);
699                         e->v0->flags |= Vert_eEffected;
700                         e->v1->flags |= Vert_eEffected;
701                 }
702                 else {
703                         *prevp = e->next;
704                         ccg_ehash_insert(ss->eMap, (EHEntry *) e);
705                         e->flags = 0;
706                         if ((e->v0->flags | e->v1->flags) & Vert_eChanged) {
707                                 e->v0->flags |= Vert_eEffected;
708                                 e->v1->flags |= Vert_eEffected;
709                         }
710                 }
711         }
712
713         if (e_r) *e_r = e;
714         return eCCGError_None;
715 }
716
717 CCGError ccgSubSurf_syncFace(CCGSubSurf *ss, CCGFaceHDL fHDL, int numVerts, CCGVertHDL *vHDLs, CCGFace **f_r)
718 {
719         void **prevp;
720         CCGFace *f = NULL, *fNew;
721         int j, k, topologyChanged = 0;
722
723         if (UNLIKELY(numVerts > ss->lenTempArrays)) {
724                 ss->lenTempArrays = (numVerts < ss->lenTempArrays * 2) ? ss->lenTempArrays * 2 : numVerts;
725                 ss->tempVerts = MEM_reallocN(ss->tempVerts, sizeof(*ss->tempVerts) * ss->lenTempArrays);
726                 ss->tempEdges = MEM_reallocN(ss->tempEdges, sizeof(*ss->tempEdges) * ss->lenTempArrays);
727         }
728
729         if (ss->syncState == eSyncState_Partial) {
730                 f = ccg_ehash_lookupWithPrev(ss->fMap, fHDL, &prevp);
731
732                 for (k = 0; k < numVerts; k++) {
733                         ss->tempVerts[k] = ccg_ehash_lookup(ss->vMap, vHDLs[k]);
734                 }
735                 for (k = 0; k < numVerts; k++) {
736                         ss->tempEdges[k] = _vert_findEdgeTo(ss->tempVerts[k], ss->tempVerts[(k + 1) % numVerts]);
737                 }
738
739                 if (f) {
740                         if (f->numVerts != numVerts ||
741                             memcmp(FACE_getVerts(f), ss->tempVerts, sizeof(*ss->tempVerts) * numVerts) ||
742                             memcmp(FACE_getEdges(f), ss->tempEdges, sizeof(*ss->tempEdges) * numVerts))
743                         {
744                                 topologyChanged = 1;
745                         }
746                 }
747
748                 if (!f || topologyChanged) {
749                         fNew = _face_new(fHDL, ss->tempVerts, ss->tempEdges, numVerts, ss);
750
751                         if (f) {
752                                 ss->numGrids += numVerts - f->numVerts;
753
754                                 *prevp = fNew;
755                                 fNew->next = f->next;
756
757                                 _face_unlinkMarkAndFree(f, ss);
758                         }
759                         else {
760                                 ss->numGrids += numVerts;
761                                 ccg_ehash_insert(ss->fMap, (EHEntry *) fNew);
762                         }
763
764                         for (k = 0; k < numVerts; k++)
765                                 FACE_getVerts(fNew)[k]->flags |= Vert_eEffected;
766                 }
767         }
768         else {
769                 if (ss->syncState == eSyncState_Vert || ss->syncState == eSyncState_Edge) {
770                         ss->syncState = eSyncState_Face;
771                 }
772                 else if (ss->syncState != eSyncState_Face) {
773                         return eCCGError_InvalidSyncState;
774                 }
775
776                 f = ccg_ehash_lookupWithPrev(ss->oldFMap, fHDL, &prevp);
777
778                 for (k = 0; k < numVerts; k++) {
779                         ss->tempVerts[k] = ccg_ehash_lookup(ss->vMap, vHDLs[k]);
780
781                         if (!ss->tempVerts[k])
782                                 return eCCGError_InvalidValue;
783                 }
784                 for (k = 0; k < numVerts; k++) {
785                         ss->tempEdges[k] = _vert_findEdgeTo(ss->tempVerts[k], ss->tempVerts[(k + 1) % numVerts]);
786
787                         if (!ss->tempEdges[k]) {
788                                 if (ss->allowEdgeCreation) {
789                                         CCGEdge *e = ss->tempEdges[k] = _edge_new((CCGEdgeHDL) - 1, ss->tempVerts[k], ss->tempVerts[(k + 1) % numVerts], ss->defaultCreaseValue, ss);
790                                         ccg_ehash_insert(ss->eMap, (EHEntry *) e);
791                                         e->v0->flags |= Vert_eEffected;
792                                         e->v1->flags |= Vert_eEffected;
793                                         if (ss->meshIFC.edgeUserSize) {
794                                                 memcpy(ccgSubSurf_getEdgeUserData(ss, e), ss->defaultEdgeUserData, ss->meshIFC.edgeUserSize);
795                                         }
796                                 }
797                                 else {
798                                         return eCCGError_InvalidValue;
799                                 }
800                         }
801                 }
802
803                 if (f) {
804                         if (f->numVerts != numVerts ||
805                             memcmp(FACE_getVerts(f), ss->tempVerts, sizeof(*ss->tempVerts) * numVerts) ||
806                             memcmp(FACE_getEdges(f), ss->tempEdges, sizeof(*ss->tempEdges) * numVerts))
807                         {
808                                 topologyChanged = 1;
809                         }
810                 }
811
812                 if (!f || topologyChanged) {
813                         f = _face_new(fHDL, ss->tempVerts, ss->tempEdges, numVerts, ss);
814                         ccg_ehash_insert(ss->fMap, (EHEntry *) f);
815                         ss->numGrids += numVerts;
816
817                         for (k = 0; k < numVerts; k++)
818                                 FACE_getVerts(f)[k]->flags |= Vert_eEffected;
819                 }
820                 else {
821                         *prevp = f->next;
822                         ccg_ehash_insert(ss->fMap, (EHEntry *) f);
823                         f->flags = 0;
824                         ss->numGrids += f->numVerts;
825
826                         for (j = 0; j < f->numVerts; j++) {
827                                 if (FACE_getVerts(f)[j]->flags & Vert_eChanged) {
828                                         for (k = 0; k < f->numVerts; k++)
829                                                 FACE_getVerts(f)[k]->flags |= Vert_eEffected;
830                                         break;
831                                 }
832                         }
833                 }
834 #ifdef WITH_OPENSUBDIV
835                 f->osd_index = ss->osd_next_face_ptex_index;
836                 if (numVerts == 4) {
837                         ss->osd_next_face_ptex_index++;
838                 }
839                 else {
840                         ss->osd_next_face_ptex_index += numVerts;
841                 }
842 #endif
843         }
844
845         if (f_r) *f_r = f;
846         return eCCGError_None;
847 }
848
849 static void ccgSubSurf__sync(CCGSubSurf *ss)
850 {
851 #ifdef WITH_OPENSUBDIV
852         if (ss->skip_grids) {
853                 ccgSubSurf__sync_opensubdiv(ss);
854         }
855         else
856 #endif
857         {
858                 ccgSubSurf__sync_legacy(ss);
859         }
860 }
861
862 CCGError ccgSubSurf_processSync(CCGSubSurf *ss)
863 {
864         if (ss->syncState == eSyncState_Partial) {
865                 ss->syncState = eSyncState_None;
866
867                 ccgSubSurf__sync(ss);
868         }
869         else if (ss->syncState) {
870                 ccg_ehash_free(ss->oldFMap, (EHEntryFreeFP) _face_unlinkMarkAndFree, ss);
871                 ccg_ehash_free(ss->oldEMap, (EHEntryFreeFP) _edge_unlinkMarkAndFree, ss);
872                 ccg_ehash_free(ss->oldVMap, (EHEntryFreeFP) _vert_free, ss);
873                 MEM_freeN(ss->tempEdges);
874                 MEM_freeN(ss->tempVerts);
875
876                 ss->lenTempArrays = 0;
877
878                 ss->oldFMap = ss->oldEMap = ss->oldVMap = NULL;
879                 ss->tempVerts = NULL;
880                 ss->tempEdges = NULL;
881
882                 ss->syncState = eSyncState_None;
883
884                 ccgSubSurf__sync(ss);
885         }
886         else {
887                 return eCCGError_InvalidSyncState;
888         }
889
890         return eCCGError_None;
891 }
892
893 void ccgSubSurf__allFaces(CCGSubSurf *ss, CCGFace ***faces, int *numFaces, int *freeFaces)
894 {
895         CCGFace **array;
896         int i, num;
897
898         if (*faces == NULL) {
899                 array = MEM_mallocN(sizeof(*array) * ss->fMap->numEntries, "CCGSubsurf allFaces");
900                 num = 0;
901                 for (i = 0; i < ss->fMap->curSize; i++) {
902                         CCGFace *f = (CCGFace *) ss->fMap->buckets[i];
903
904                         for (; f; f = f->next)
905                                 array[num++] = f;
906                 }
907
908                 *faces = array;
909                 *numFaces = num;
910                 *freeFaces = 1;
911         }
912         else {
913                 *freeFaces = 0;
914         }
915 }
916
917 void ccgSubSurf__effectedFaceNeighbours(CCGSubSurf *ss, CCGFace **faces, int numFaces, CCGVert ***verts, int *numVerts, CCGEdge ***edges, int *numEdges)
918 {
919         CCGVert **arrayV;
920         CCGEdge **arrayE;
921         int numV, numE, i, j;
922
923         arrayV = MEM_mallocN(sizeof(*arrayV) * ss->vMap->numEntries, "CCGSubsurf arrayV");
924         arrayE = MEM_mallocN(sizeof(*arrayE) * ss->eMap->numEntries, "CCGSubsurf arrayV");
925         numV = numE = 0;
926
927         for (i = 0; i < numFaces; i++) {
928                 CCGFace *f = faces[i];
929                 f->flags |= Face_eEffected;
930         }
931
932         for (i = 0; i < ss->vMap->curSize; i++) {
933                 CCGVert *v = (CCGVert *) ss->vMap->buckets[i];
934
935                 for (; v; v = v->next) {
936                         for (j = 0; j < v->numFaces; j++)
937                                 if (!(v->faces[j]->flags & Face_eEffected))
938                                         break;
939                         
940                         if (j == v->numFaces) {
941                                 arrayV[numV++] = v;
942                                 v->flags |= Vert_eEffected;
943                         }
944                 }
945         }
946
947         for (i = 0; i < ss->eMap->curSize; i++) {
948                 CCGEdge *e = (CCGEdge *) ss->eMap->buckets[i];
949
950                 for (; e; e = e->next) {
951                         for (j = 0; j < e->numFaces; j++)
952                                 if (!(e->faces[j]->flags & Face_eEffected))
953                                         break;
954                         
955                         if (j == e->numFaces) {
956                                 e->flags |= Edge_eEffected;
957                                 arrayE[numE++] = e;
958                         }
959                 }
960         }
961
962         *verts = arrayV;
963         *numVerts = numV;
964         *edges = arrayE;
965         *numEdges = numE;
966 }
967
968 /* copy face grid coordinates to other places */
969 CCGError ccgSubSurf_updateFromFaces(CCGSubSurf *ss, int lvl, CCGFace **effectedF, int numEffectedF)
970 {
971         int i, S, x, gridSize, cornerIdx, subdivLevels;
972         int vertDataSize = ss->meshIFC.vertDataSize, freeF;
973
974         subdivLevels = ss->subdivLevels;
975         lvl = (lvl) ? lvl : subdivLevels;
976         gridSize = ccg_gridsize(lvl);
977         cornerIdx = gridSize - 1;
978
979         ccgSubSurf__allFaces(ss, &effectedF, &numEffectedF, &freeF);
980
981         for (i = 0; i < numEffectedF; i++) {
982                 CCGFace *f = effectedF[i];
983
984                 for (S = 0; S < f->numVerts; S++) {
985                         CCGEdge *e = FACE_getEdges(f)[S];
986                         CCGEdge *prevE = FACE_getEdges(f)[(S + f->numVerts - 1) % f->numVerts];
987
988                         VertDataCopy((float *)FACE_getCenterData(f), FACE_getIFCo(f, lvl, S, 0, 0), ss);
989                         VertDataCopy(VERT_getCo(FACE_getVerts(f)[S], lvl), FACE_getIFCo(f, lvl, S, cornerIdx, cornerIdx), ss);
990
991                         for (x = 0; x < gridSize; x++)
992                                 VertDataCopy(FACE_getIECo(f, lvl, S, x), FACE_getIFCo(f, lvl, S, x, 0), ss);
993
994                         for (x = 0; x < gridSize; x++) {
995                                 int eI = gridSize - 1 - x;
996                                 VertDataCopy(_edge_getCoVert(e, FACE_getVerts(f)[S], lvl, eI, vertDataSize), FACE_getIFCo(f, lvl, S, cornerIdx, x), ss);
997                                 VertDataCopy(_edge_getCoVert(prevE, FACE_getVerts(f)[S], lvl, eI, vertDataSize), FACE_getIFCo(f, lvl, S, x, cornerIdx), ss);
998                         }
999                 }
1000         }
1001
1002         if (freeF) MEM_freeN(effectedF);
1003
1004         return eCCGError_None;
1005 }
1006
1007 /* copy other places to face grid coordinates */
1008 CCGError ccgSubSurf_updateToFaces(CCGSubSurf *ss, int lvl, CCGFace **effectedF, int numEffectedF)
1009 {
1010         int i, S, x, gridSize, cornerIdx, subdivLevels;
1011         int vertDataSize = ss->meshIFC.vertDataSize, freeF;
1012
1013         subdivLevels = ss->subdivLevels;
1014         lvl = (lvl) ? lvl : subdivLevels;
1015         gridSize = ccg_gridsize(lvl);
1016         cornerIdx = gridSize - 1;
1017
1018         ccgSubSurf__allFaces(ss, &effectedF, &numEffectedF, &freeF);
1019
1020         for (i = 0; i < numEffectedF; i++) {
1021                 CCGFace *f = effectedF[i];
1022
1023                 for (S = 0; S < f->numVerts; S++) {
1024                         int prevS = (S + f->numVerts - 1) % f->numVerts;
1025                         CCGEdge *e = FACE_getEdges(f)[S];
1026                         CCGEdge *prevE = FACE_getEdges(f)[prevS];
1027
1028                         for (x = 0; x < gridSize; x++) {
1029                                 int eI = gridSize - 1 - x;
1030                                 VertDataCopy(FACE_getIFCo(f, lvl, S, cornerIdx, x), _edge_getCoVert(e, FACE_getVerts(f)[S], lvl, eI, vertDataSize), ss);
1031                                 VertDataCopy(FACE_getIFCo(f, lvl, S, x, cornerIdx), _edge_getCoVert(prevE, FACE_getVerts(f)[S], lvl, eI, vertDataSize), ss);
1032                         }
1033
1034                         for (x = 1; x < gridSize - 1; x++) {
1035                                 VertDataCopy(FACE_getIFCo(f, lvl, S, 0, x), FACE_getIECo(f, lvl, prevS, x), ss);
1036                                 VertDataCopy(FACE_getIFCo(f, lvl, S, x, 0), FACE_getIECo(f, lvl, S, x), ss);
1037                         }
1038
1039                         VertDataCopy(FACE_getIFCo(f, lvl, S, 0, 0), (float *)FACE_getCenterData(f), ss);
1040                         VertDataCopy(FACE_getIFCo(f, lvl, S, cornerIdx, cornerIdx), VERT_getCo(FACE_getVerts(f)[S], lvl), ss);
1041                 }
1042         }
1043
1044         if (freeF) MEM_freeN(effectedF);
1045
1046         return eCCGError_None;
1047 }
1048
1049 /* stitch together face grids, averaging coordinates at edges
1050  * and vertices, for multires displacements */
1051 CCGError ccgSubSurf_stitchFaces(CCGSubSurf *ss, int lvl, CCGFace **effectedF, int numEffectedF)
1052 {
1053         CCGVert **effectedV;
1054         CCGEdge **effectedE;
1055         int numEffectedV, numEffectedE, freeF;
1056         int i, S, x, gridSize, cornerIdx, subdivLevels, edgeSize;
1057         int vertDataSize = ss->meshIFC.vertDataSize;
1058
1059         subdivLevels = ss->subdivLevels;
1060         lvl = (lvl) ? lvl : subdivLevels;
1061         gridSize = ccg_gridsize(lvl);
1062         edgeSize = ccg_edgesize(lvl);
1063         cornerIdx = gridSize - 1;
1064
1065         ccgSubSurf__allFaces(ss, &effectedF, &numEffectedF, &freeF);
1066         ccgSubSurf__effectedFaceNeighbours(ss, effectedF, numEffectedF,
1067                                            &effectedV, &numEffectedV, &effectedE, &numEffectedE);
1068
1069         /* zero */
1070         for (i = 0; i < numEffectedV; i++) {
1071                 CCGVert *v = effectedV[i];
1072                 if (v->numFaces)
1073                         VertDataZero(VERT_getCo(v, lvl), ss);
1074         }
1075
1076         for (i = 0; i < numEffectedE; i++) {
1077                 CCGEdge *e = effectedE[i];
1078
1079                 if (e->numFaces)
1080                         for (x = 0; x < edgeSize; x++)
1081                                 VertDataZero(EDGE_getCo(e, lvl, x), ss);
1082         }
1083
1084         /* add */
1085         for (i = 0; i < numEffectedF; i++) {
1086                 CCGFace *f = effectedF[i];
1087
1088                 VertDataZero((float *)FACE_getCenterData(f), ss);
1089
1090                 for (S = 0; S < f->numVerts; S++)
1091                         for (x = 0; x < gridSize; x++)
1092                                 VertDataZero(FACE_getIECo(f, lvl, S, x), ss);
1093
1094                 for (S = 0; S < f->numVerts; S++) {
1095                         int prevS = (S + f->numVerts - 1) % f->numVerts;
1096                         CCGEdge *e = FACE_getEdges(f)[S];
1097                         CCGEdge *prevE = FACE_getEdges(f)[prevS];
1098
1099                         VertDataAdd((float *)FACE_getCenterData(f), FACE_getIFCo(f, lvl, S, 0, 0), ss);
1100                         if (FACE_getVerts(f)[S]->flags & Vert_eEffected)
1101                                 VertDataAdd(VERT_getCo(FACE_getVerts(f)[S], lvl), FACE_getIFCo(f, lvl, S, cornerIdx, cornerIdx), ss);
1102
1103                         for (x = 1; x < gridSize - 1; x++) {
1104                                 VertDataAdd(FACE_getIECo(f, lvl, S, x), FACE_getIFCo(f, lvl, S, x, 0), ss);
1105                                 VertDataAdd(FACE_getIECo(f, lvl, prevS, x), FACE_getIFCo(f, lvl, S, 0, x), ss);
1106                         }
1107
1108                         for (x = 0; x < gridSize - 1; x++) {
1109                                 int eI = gridSize - 1 - x;
1110                                 if (FACE_getEdges(f)[S]->flags & Edge_eEffected)
1111                                         VertDataAdd(_edge_getCoVert(e, FACE_getVerts(f)[S], lvl, eI, vertDataSize), FACE_getIFCo(f, lvl, S, cornerIdx, x), ss);
1112                                 if (FACE_getEdges(f)[prevS]->flags & Edge_eEffected)
1113                                         if (x != 0)
1114                                                 VertDataAdd(_edge_getCoVert(prevE, FACE_getVerts(f)[S], lvl, eI, vertDataSize), FACE_getIFCo(f, lvl, S, x, cornerIdx), ss);
1115                         }
1116                 }
1117         }
1118
1119         /* average */
1120         for (i = 0; i < numEffectedV; i++) {
1121                 CCGVert *v = effectedV[i];
1122                 if (v->numFaces)
1123                         VertDataMulN(VERT_getCo(v, lvl), 1.0f / v->numFaces, ss);
1124         }
1125
1126         for (i = 0; i < numEffectedE; i++) {
1127                 CCGEdge *e = effectedE[i];
1128
1129                 VertDataCopy(EDGE_getCo(e, lvl, 0), VERT_getCo(e->v0, lvl), ss);
1130                 VertDataCopy(EDGE_getCo(e, lvl, edgeSize - 1), VERT_getCo(e->v1, lvl), ss);
1131
1132                 if (e->numFaces)
1133                         for (x = 1; x < edgeSize - 1; x++)
1134                                 VertDataMulN(EDGE_getCo(e, lvl, x), 1.0f / e->numFaces, ss);
1135         }
1136
1137         /* copy */
1138         for (i = 0; i < numEffectedF; i++) {
1139                 CCGFace *f = effectedF[i];
1140
1141                 VertDataMulN((float *)FACE_getCenterData(f), 1.0f / f->numVerts, ss);
1142
1143                 for (S = 0; S < f->numVerts; S++)
1144                         for (x = 1; x < gridSize - 1; x++)
1145                                 VertDataMulN(FACE_getIECo(f, lvl, S, x), 0.5f, ss);
1146
1147                 for (S = 0; S < f->numVerts; S++) {
1148                         int prevS = (S + f->numVerts - 1) % f->numVerts;
1149                         CCGEdge *e = FACE_getEdges(f)[S];
1150                         CCGEdge *prevE = FACE_getEdges(f)[prevS];
1151
1152                         VertDataCopy(FACE_getIFCo(f, lvl, S, 0, 0), (float *)FACE_getCenterData(f), ss);
1153                         VertDataCopy(FACE_getIFCo(f, lvl, S, cornerIdx, cornerIdx), VERT_getCo(FACE_getVerts(f)[S], lvl), ss);
1154
1155                         for (x = 1; x < gridSize - 1; x++) {
1156                                 VertDataCopy(FACE_getIFCo(f, lvl, S, x, 0), FACE_getIECo(f, lvl, S, x), ss);
1157                                 VertDataCopy(FACE_getIFCo(f, lvl, S, 0, x), FACE_getIECo(f, lvl, prevS, x), ss);
1158                         }
1159
1160                         for (x = 0; x < gridSize - 1; x++) {
1161                                 int eI = gridSize - 1 - x;
1162
1163                                 VertDataCopy(FACE_getIFCo(f, lvl, S, cornerIdx, x), _edge_getCoVert(e, FACE_getVerts(f)[S], lvl, eI, vertDataSize), ss);
1164                                 VertDataCopy(FACE_getIFCo(f, lvl, S, x, cornerIdx), _edge_getCoVert(prevE, FACE_getVerts(f)[S], lvl, eI, vertDataSize), ss);
1165                         }
1166
1167                         VertDataCopy(FACE_getIECo(f, lvl, S, 0), (float *)FACE_getCenterData(f), ss);
1168                         VertDataCopy(FACE_getIECo(f, lvl, S, gridSize - 1), FACE_getIFCo(f, lvl, S, gridSize - 1, 0), ss);
1169                 }
1170         }
1171
1172         for (i = 0; i < numEffectedV; i++)
1173                 effectedV[i]->flags = 0;
1174         for (i = 0; i < numEffectedE; i++)
1175                 effectedE[i]->flags = 0;
1176         for (i = 0; i < numEffectedF; i++)
1177                 effectedF[i]->flags = 0;
1178
1179         MEM_freeN(effectedE);
1180         MEM_freeN(effectedV);
1181         if (freeF) MEM_freeN(effectedF);
1182
1183         return eCCGError_None;
1184 }
1185
1186 /*** External API accessor functions ***/
1187
1188 int ccgSubSurf_getNumVerts(const CCGSubSurf *ss)
1189 {
1190         return ss->vMap->numEntries;
1191 }
1192 int ccgSubSurf_getNumEdges(const CCGSubSurf *ss)
1193 {
1194         return ss->eMap->numEntries;
1195 }
1196 int ccgSubSurf_getNumFaces(const CCGSubSurf *ss)
1197 {
1198         return ss->fMap->numEntries;
1199 }
1200
1201 CCGVert *ccgSubSurf_getVert(CCGSubSurf *ss, CCGVertHDL v)
1202 {
1203         return (CCGVert *) ccg_ehash_lookup(ss->vMap, v);
1204 }
1205 CCGEdge *ccgSubSurf_getEdge(CCGSubSurf *ss, CCGEdgeHDL e)
1206 {
1207         return (CCGEdge *) ccg_ehash_lookup(ss->eMap, e);
1208 }
1209 CCGFace *ccgSubSurf_getFace(CCGSubSurf *ss, CCGFaceHDL f)
1210 {
1211         return (CCGFace *) ccg_ehash_lookup(ss->fMap, f);
1212 }
1213
1214 int ccgSubSurf_getSubdivisionLevels(const CCGSubSurf *ss)
1215 {
1216         return ss->subdivLevels;
1217 }
1218 int ccgSubSurf_getEdgeSize(const CCGSubSurf *ss)
1219 {
1220         return ccgSubSurf_getEdgeLevelSize(ss, ss->subdivLevels);
1221 }
1222 int ccgSubSurf_getEdgeLevelSize(const CCGSubSurf *ss, int level)
1223 {
1224         if (level < 1 || level > ss->subdivLevels) {
1225                 return -1;
1226         }
1227         else {
1228                 return ccg_edgesize(level);
1229         }
1230 }
1231 int ccgSubSurf_getGridSize(const CCGSubSurf *ss)
1232 {
1233         return ccgSubSurf_getGridLevelSize(ss, ss->subdivLevels);
1234 }
1235 int ccgSubSurf_getGridLevelSize(const CCGSubSurf *ss, int level)
1236 {
1237         if (level < 1 || level > ss->subdivLevels) {
1238                 return -1;
1239         }
1240         else {
1241                 return ccg_gridsize(level);
1242         }
1243 }
1244
1245 int ccgSubSurf_getSimpleSubdiv(const CCGSubSurf *ss)
1246 {
1247         return ss->meshIFC.simpleSubdiv;
1248 }
1249
1250 /* Vert accessors */
1251
1252 CCGVertHDL ccgSubSurf_getVertVertHandle(CCGVert *v)
1253 {
1254         return v->vHDL;
1255 }
1256 int ccgSubSurf_getVertAge(CCGSubSurf *ss, CCGVert *v)
1257 {
1258         if (ss->useAgeCounts) {
1259                 byte *userData = ccgSubSurf_getVertUserData(ss, v);
1260                 return ss->currentAge - *((int *) &userData[ss->vertUserAgeOffset]);
1261         }
1262         else {
1263                 return 0;
1264         }
1265 }
1266 void *ccgSubSurf_getVertUserData(CCGSubSurf *ss, CCGVert *v)
1267 {
1268         return VERT_getLevelData(v) + ss->meshIFC.vertDataSize * (ss->subdivLevels + 1);
1269 }
1270 int ccgSubSurf_getVertNumFaces(CCGVert *v)
1271 {
1272         return v->numFaces;
1273 }
1274 CCGFace *ccgSubSurf_getVertFace(CCGVert *v, int index)
1275 {
1276         if (index < 0 || index >= v->numFaces) {
1277                 return NULL;
1278         }
1279         else {
1280                 return v->faces[index];
1281         }
1282 }
1283 int ccgSubSurf_getVertNumEdges(CCGVert *v)
1284 {
1285         return v->numEdges;
1286 }
1287 CCGEdge *ccgSubSurf_getVertEdge(CCGVert *v, int index)
1288 {
1289         if (index < 0 || index >= v->numEdges) {
1290                 return NULL;
1291         }
1292         else {
1293                 return v->edges[index];
1294         }
1295 }
1296 void *ccgSubSurf_getVertData(CCGSubSurf *ss, CCGVert *v)
1297 {
1298         return ccgSubSurf_getVertLevelData(ss, v, ss->subdivLevels);
1299 }
1300 void *ccgSubSurf_getVertLevelData(CCGSubSurf *ss, CCGVert *v, int level)
1301 {
1302         if (level < 0 || level > ss->subdivLevels) {
1303                 return NULL;
1304         }
1305         else {
1306                 return ccg_vert_getCo(v, level, ss->meshIFC.vertDataSize);
1307         }
1308 }
1309
1310 /* Edge accessors */
1311
1312 CCGEdgeHDL ccgSubSurf_getEdgeEdgeHandle(CCGEdge *e)
1313 {
1314         return e->eHDL;
1315 }
1316 int ccgSubSurf_getEdgeAge(CCGSubSurf *ss, CCGEdge *e)
1317 {
1318         if (ss->useAgeCounts) {
1319                 byte *userData = ccgSubSurf_getEdgeUserData(ss, e);
1320                 return ss->currentAge - *((int *) &userData[ss->edgeUserAgeOffset]);
1321         }
1322         else {
1323                 return 0;
1324         }
1325 }
1326 void *ccgSubSurf_getEdgeUserData(CCGSubSurf *ss, CCGEdge *e)
1327 {
1328         return (EDGE_getLevelData(e) +
1329                 ss->meshIFC.vertDataSize * ccg_edgebase(ss->subdivLevels + 1));
1330 }
1331 int ccgSubSurf_getEdgeNumFaces(CCGEdge *e)
1332 {
1333         return e->numFaces;
1334 }
1335 CCGFace *ccgSubSurf_getEdgeFace(CCGEdge *e, int index)
1336 {
1337         if (index < 0 || index >= e->numFaces) {
1338                 return NULL;
1339         }
1340         else {
1341                 return e->faces[index];
1342         }
1343 }
1344 CCGVert *ccgSubSurf_getEdgeVert0(CCGEdge *e)
1345 {
1346         return e->v0;
1347 }
1348 CCGVert *ccgSubSurf_getEdgeVert1(CCGEdge *e)
1349 {
1350         return e->v1;
1351 }
1352 void *ccgSubSurf_getEdgeDataArray(CCGSubSurf *ss, CCGEdge *e)
1353 {
1354         return ccgSubSurf_getEdgeData(ss, e, 0);
1355 }
1356 void *ccgSubSurf_getEdgeData(CCGSubSurf *ss, CCGEdge *e, int x)
1357 {
1358         return ccgSubSurf_getEdgeLevelData(ss, e, x, ss->subdivLevels);
1359 }
1360 void *ccgSubSurf_getEdgeLevelData(CCGSubSurf *ss, CCGEdge *e, int x, int level)
1361 {
1362         if (level < 0 || level > ss->subdivLevels) {
1363                 return NULL;
1364         }
1365         else {
1366                 return ccg_edge_getCo(e, level, x, ss->meshIFC.vertDataSize);
1367         }
1368 }
1369 float ccgSubSurf_getEdgeCrease(CCGEdge *e)
1370 {
1371         return e->crease;
1372 }
1373
1374 /* Face accessors */
1375
1376 CCGFaceHDL ccgSubSurf_getFaceFaceHandle(CCGFace *f)
1377 {
1378         return f->fHDL;
1379 }
1380 int ccgSubSurf_getFaceAge(CCGSubSurf *ss, CCGFace *f)
1381 {
1382         if (ss->useAgeCounts) {
1383                 byte *userData = ccgSubSurf_getFaceUserData(ss, f);
1384                 return ss->currentAge - *((int *) &userData[ss->faceUserAgeOffset]);
1385         }
1386         else {
1387                 return 0;
1388         }
1389 }
1390 void *ccgSubSurf_getFaceUserData(CCGSubSurf *ss, CCGFace *f)
1391 {
1392         int maxGridSize = ccg_gridsize(ss->subdivLevels);
1393         return FACE_getCenterData(f) + ss->meshIFC.vertDataSize * (1 + f->numVerts * maxGridSize + f->numVerts * maxGridSize * maxGridSize);
1394 }
1395 int ccgSubSurf_getFaceNumVerts(CCGFace *f)
1396 {
1397         return f->numVerts;
1398 }
1399 CCGVert *ccgSubSurf_getFaceVert(CCGFace *f, int index)
1400 {
1401         if (index < 0 || index >= f->numVerts) {
1402                 return NULL;
1403         }
1404         else {
1405                 return FACE_getVerts(f)[index];
1406         }
1407 }
1408 CCGEdge *ccgSubSurf_getFaceEdge(CCGFace *f, int index)
1409 {
1410         if (index < 0 || index >= f->numVerts) {
1411                 return NULL;
1412         }
1413         else {
1414                 return FACE_getEdges(f)[index];
1415         }
1416 }
1417 int ccgSubSurf_getFaceEdgeIndex(CCGFace *f, CCGEdge *e)
1418 {
1419         int i;
1420
1421         for (i = 0; i < f->numVerts; i++) {
1422                 if (FACE_getEdges(f)[i] == e) {
1423                         return i;
1424                 }
1425         }
1426         return -1;
1427 }
1428 void *ccgSubSurf_getFaceCenterData(CCGFace *f)
1429 {
1430         return FACE_getCenterData(f);
1431 }
1432 void *ccgSubSurf_getFaceGridEdgeDataArray(CCGSubSurf *ss, CCGFace *f, int gridIndex)
1433 {
1434         return ccgSubSurf_getFaceGridEdgeData(ss, f, gridIndex, 0);
1435 }
1436 void *ccgSubSurf_getFaceGridEdgeData(CCGSubSurf *ss, CCGFace *f, int gridIndex, int x)
1437 {
1438         return ccg_face_getIECo(f, ss->subdivLevels, gridIndex, x, ss->subdivLevels, ss->meshIFC.vertDataSize);
1439 }
1440 void *ccgSubSurf_getFaceGridDataArray(CCGSubSurf *ss, CCGFace *f, int gridIndex)
1441 {
1442         return ccgSubSurf_getFaceGridData(ss, f, gridIndex, 0, 0);
1443 }
1444 void *ccgSubSurf_getFaceGridData(CCGSubSurf *ss, CCGFace *f, int gridIndex, int x, int y)
1445 {
1446         return ccg_face_getIFCo(f, ss->subdivLevels, gridIndex, x, y, ss->subdivLevels, ss->meshIFC.vertDataSize);
1447 }
1448
1449 /*** External API iterator functions ***/
1450
1451 void ccgSubSurf_initVertIterator(CCGSubSurf *ss, CCGVertIterator *viter)
1452 {
1453         ccg_ehashIterator_init(ss->vMap, viter);
1454 }
1455 void ccgSubSurf_initEdgeIterator(CCGSubSurf *ss, CCGEdgeIterator *eiter)
1456 {
1457         ccg_ehashIterator_init(ss->eMap, eiter);
1458 }
1459 void ccgSubSurf_initFaceIterator(CCGSubSurf *ss, CCGFaceIterator *fiter)
1460 {
1461         ccg_ehashIterator_init(ss->fMap, fiter);
1462 }
1463
1464 CCGVert *ccgVertIterator_getCurrent(CCGVertIterator *vi)
1465 {
1466         return (CCGVert *) ccg_ehashIterator_getCurrent((EHashIterator *) vi);
1467 }
1468 int ccgVertIterator_isStopped(CCGVertIterator *vi)
1469 {
1470         return ccg_ehashIterator_isStopped((EHashIterator *) vi);
1471 }
1472 void ccgVertIterator_next(CCGVertIterator *vi)
1473 {
1474         ccg_ehashIterator_next((EHashIterator *) vi);
1475 }
1476
1477 CCGEdge *ccgEdgeIterator_getCurrent(CCGEdgeIterator *vi)
1478 {
1479         return (CCGEdge *) ccg_ehashIterator_getCurrent((EHashIterator *) vi);
1480 }
1481 int ccgEdgeIterator_isStopped(CCGEdgeIterator *vi)
1482 {
1483         return ccg_ehashIterator_isStopped((EHashIterator *) vi);
1484 }
1485 void ccgEdgeIterator_next(CCGEdgeIterator *vi)
1486 {
1487         ccg_ehashIterator_next((EHashIterator *) vi);
1488 }
1489
1490 CCGFace *ccgFaceIterator_getCurrent(CCGFaceIterator *vi)
1491 {
1492         return (CCGFace *) ccg_ehashIterator_getCurrent((EHashIterator *) vi);
1493 }
1494 int ccgFaceIterator_isStopped(CCGFaceIterator *vi)
1495 {
1496         return ccg_ehashIterator_isStopped((EHashIterator *) vi);
1497 }
1498 void ccgFaceIterator_next(CCGFaceIterator *vi)
1499 {
1500         ccg_ehashIterator_next((EHashIterator *) vi);
1501 }
1502
1503 /*** Extern API final vert/edge/face interface ***/
1504
1505 int ccgSubSurf_getNumFinalVerts(const CCGSubSurf *ss)
1506 {
1507         int edgeSize = ccg_edgesize(ss->subdivLevels);
1508         int gridSize = ccg_gridsize(ss->subdivLevels);
1509         int numFinalVerts = (ss->vMap->numEntries +
1510                              ss->eMap->numEntries * (edgeSize - 2) +
1511                              ss->fMap->numEntries +
1512                              ss->numGrids * ((gridSize - 2) + ((gridSize - 2) * (gridSize - 2))));
1513
1514 #ifdef WITH_OPENSUBDIV
1515         if (ss->skip_grids) {
1516                 return 0;
1517         }
1518 #endif
1519
1520         return numFinalVerts;
1521 }
1522 int ccgSubSurf_getNumFinalEdges(const CCGSubSurf *ss)
1523 {
1524         int edgeSize = ccg_edgesize(ss->subdivLevels);
1525         int gridSize = ccg_gridsize(ss->subdivLevels);
1526         int numFinalEdges = (ss->eMap->numEntries * (edgeSize - 1) +
1527                              ss->numGrids * ((gridSize - 1) + 2 * ((gridSize - 2) * (gridSize - 1))));
1528 #ifdef WITH_OPENSUBDIV
1529         if (ss->skip_grids) {
1530                 return 0;
1531         }
1532 #endif
1533         return numFinalEdges;
1534 }
1535 int ccgSubSurf_getNumFinalFaces(const CCGSubSurf *ss)
1536 {
1537         int gridSize = ccg_gridsize(ss->subdivLevels);
1538         int numFinalFaces = ss->numGrids * ((gridSize - 1) * (gridSize - 1));
1539 #ifdef WITH_OPENSUBDIV
1540         if (ss->skip_grids) {
1541                 return 0;
1542         }
1543 #endif
1544         return numFinalFaces;
1545 }
1546
1547 /***/
1548
1549 void CCG_key(CCGKey *key, const CCGSubSurf *ss, int level)
1550 {
1551         key->level = level;
1552         
1553         key->elem_size = ss->meshIFC.vertDataSize;
1554         key->has_normals = ss->calcVertNormals;
1555         key->num_layers = ss->meshIFC.numLayers;
1556         
1557         /* if normals are present, always the last three floats of an
1558          * element */
1559         if (key->has_normals)
1560                 key->normal_offset = key->elem_size - sizeof(float) * 3;
1561         else
1562                 key->normal_offset = -1;
1563
1564         key->grid_size = ccgSubSurf_getGridLevelSize(ss, level);
1565         key->grid_area = key->grid_size * key->grid_size;
1566         key->grid_bytes = key->elem_size * key->grid_area;
1567
1568         key->has_mask = ss->allocMask;
1569         if (key->has_mask)
1570                 key->mask_offset = ss->maskDataOffset;
1571         else
1572                 key->mask_offset = -1;
1573 }
1574
1575 void CCG_key_top_level(CCGKey *key, const CCGSubSurf *ss)
1576 {
1577         CCG_key(key, ss, ccgSubSurf_getSubdivisionLevels(ss));
1578 }