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