Merge branch 'blender2.7'
[blender.git] / source / blender / blenkernel / intern / subsurf_ccg.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  * The Original Code is Copyright (C) 2005 Blender Foundation.
17  * All rights reserved.
18  */
19
20 /** \file
21  * \ingroup bke
22  */
23
24 #if defined(__STDC_VERSION__) && __STDC_VERSION__ >= 199901L
25 #  ifdef __GNUC__
26 #    pragma GCC diagnostic ignored "-Wvla"
27 #  endif
28 #  define USE_DYNSIZE
29 #endif
30
31 #include <stdlib.h>
32 #include <string.h>
33 #include <stdio.h>
34 #include <math.h>
35 #include <float.h>
36
37 #include "atomic_ops.h"
38
39 #include "MEM_guardedalloc.h"
40
41 #include "DNA_mesh_types.h"
42 #include "DNA_meshdata_types.h"
43 #include "DNA_modifier_types.h"
44 #include "DNA_object_types.h"
45 #include "DNA_scene_types.h"
46
47 #include "BLI_utildefines.h"
48 #include "BLI_bitmap.h"
49 #include "BLI_blenlib.h"
50 #include "BLI_edgehash.h"
51 #include "BLI_math.h"
52 #include "BLI_memarena.h"
53 #include "BLI_task.h"
54 #include "BLI_threads.h"
55
56 #include "BKE_pbvh.h"
57 #include "BKE_ccg.h"
58 #include "BKE_cdderivedmesh.h"
59 #include "BKE_mesh.h"
60 #include "BKE_mesh_mapping.h"
61 #include "BKE_modifier.h"
62 #include "BKE_multires.h"
63 #include "BKE_object.h"
64 #include "BKE_paint.h"
65 #include "BKE_scene.h"
66 #include "BKE_subsurf.h"
67
68 #ifndef USE_DYNSIZE
69 #  include "BLI_array.h"
70 #endif
71
72 #include "CCGSubSurf.h"
73
74 #ifdef WITH_OPENSUBDIV
75 #  include "opensubdiv_capi.h"
76 #endif
77
78 /* assumes MLoop's are laid out 4 for each poly, in order */
79 #define USE_LOOP_LAYOUT_FAST
80
81 static CCGDerivedMesh *getCCGDerivedMesh(CCGSubSurf *ss,
82                                          int drawInteriorEdges,
83                                          int useSubsurfUv,
84                                          DerivedMesh *dm,
85                                          bool use_gpu_backend);
86 static int ccgDM_use_grid_pbvh(CCGDerivedMesh *ccgdm);
87
88 ///
89
90 static void *arena_alloc(CCGAllocatorHDL a, int numBytes)
91 {
92   return BLI_memarena_alloc(a, numBytes);
93 }
94
95 static void *arena_realloc(CCGAllocatorHDL a, void *ptr, int newSize, int oldSize)
96 {
97   void *p2 = BLI_memarena_alloc(a, newSize);
98   if (ptr) {
99     memcpy(p2, ptr, oldSize);
100   }
101   return p2;
102 }
103
104 static void arena_free(CCGAllocatorHDL UNUSED(a), void *UNUSED(ptr))
105 {
106   /* do nothing */
107 }
108
109 static void arena_release(CCGAllocatorHDL a)
110 {
111   BLI_memarena_free(a);
112 }
113
114 typedef enum {
115   CCG_USE_AGING = 1,
116   CCG_USE_ARENA = 2,
117   CCG_CALC_NORMALS = 4,
118   /* add an extra four bytes for a mask layer */
119   CCG_ALLOC_MASK = 8,
120   CCG_SIMPLE_SUBDIV = 16,
121 } CCGFlags;
122
123 static CCGSubSurf *_getSubSurf(CCGSubSurf *prevSS, int subdivLevels, int numLayers, CCGFlags flags)
124 {
125   CCGMeshIFC ifc;
126   CCGSubSurf *ccgSS;
127   int useAging = !!(flags & CCG_USE_AGING);
128   int useArena = flags & CCG_USE_ARENA;
129   int normalOffset = 0;
130
131   /* (subdivLevels == 0) is not allowed */
132   subdivLevels = MAX2(subdivLevels, 1);
133
134   if (prevSS) {
135     int oldUseAging;
136
137     ccgSubSurf_getUseAgeCounts(prevSS, &oldUseAging, NULL, NULL, NULL);
138
139     if ((oldUseAging != useAging) ||
140         (ccgSubSurf_getSimpleSubdiv(prevSS) != !!(flags & CCG_SIMPLE_SUBDIV))) {
141       ccgSubSurf_free(prevSS);
142     }
143     else {
144       ccgSubSurf_setSubdivisionLevels(prevSS, subdivLevels);
145
146       return prevSS;
147     }
148   }
149
150   if (useAging) {
151     ifc.vertUserSize = ifc.edgeUserSize = ifc.faceUserSize = 12;
152   }
153   else {
154     ifc.vertUserSize = ifc.edgeUserSize = ifc.faceUserSize = 8;
155   }
156   ifc.numLayers = numLayers;
157   ifc.vertDataSize = sizeof(float) * numLayers;
158   normalOffset += sizeof(float) * numLayers;
159   if (flags & CCG_CALC_NORMALS) {
160     ifc.vertDataSize += sizeof(float) * 3;
161   }
162   if (flags & CCG_ALLOC_MASK) {
163     ifc.vertDataSize += sizeof(float);
164   }
165   ifc.simpleSubdiv = !!(flags & CCG_SIMPLE_SUBDIV);
166
167   if (useArena) {
168     CCGAllocatorIFC allocatorIFC;
169     CCGAllocatorHDL allocator = BLI_memarena_new(MEM_SIZE_OPTIMAL(1 << 16), "subsurf arena");
170
171     allocatorIFC.alloc = arena_alloc;
172     allocatorIFC.realloc = arena_realloc;
173     allocatorIFC.free = arena_free;
174     allocatorIFC.release = arena_release;
175
176     ccgSS = ccgSubSurf_new(&ifc, subdivLevels, &allocatorIFC, allocator);
177   }
178   else {
179     ccgSS = ccgSubSurf_new(&ifc, subdivLevels, NULL, NULL);
180   }
181
182   if (useAging) {
183     ccgSubSurf_setUseAgeCounts(ccgSS, 1, 8, 8, 8);
184   }
185
186   if (flags & CCG_ALLOC_MASK) {
187     normalOffset += sizeof(float);
188     /* mask is allocated after regular layers */
189     ccgSubSurf_setAllocMask(ccgSS, 1, sizeof(float) * numLayers);
190   }
191
192   if (flags & CCG_CALC_NORMALS) {
193     ccgSubSurf_setCalcVertexNormals(ccgSS, 1, normalOffset);
194   }
195   else {
196     ccgSubSurf_setCalcVertexNormals(ccgSS, 0, 0);
197   }
198
199   return ccgSS;
200 }
201
202 static int getEdgeIndex(CCGSubSurf *ss, CCGEdge *e, int x, int edgeSize)
203 {
204   CCGVert *v0 = ccgSubSurf_getEdgeVert0(e);
205   CCGVert *v1 = ccgSubSurf_getEdgeVert1(e);
206   int v0idx = *((int *)ccgSubSurf_getVertUserData(ss, v0));
207   int v1idx = *((int *)ccgSubSurf_getVertUserData(ss, v1));
208   int edgeBase = *((int *)ccgSubSurf_getEdgeUserData(ss, e));
209
210   if (x == 0) {
211     return v0idx;
212   }
213   else if (x == edgeSize - 1) {
214     return v1idx;
215   }
216   else {
217     return edgeBase + x - 1;
218   }
219 }
220
221 static int getFaceIndex(
222     CCGSubSurf *ss, CCGFace *f, int S, int x, int y, int edgeSize, int gridSize)
223 {
224   int faceBase = *((int *)ccgSubSurf_getFaceUserData(ss, f));
225   int numVerts = ccgSubSurf_getFaceNumVerts(f);
226
227   if (x == gridSize - 1 && y == gridSize - 1) {
228     CCGVert *v = ccgSubSurf_getFaceVert(f, S);
229     return *((int *)ccgSubSurf_getVertUserData(ss, v));
230   }
231   else if (x == gridSize - 1) {
232     CCGVert *v = ccgSubSurf_getFaceVert(f, S);
233     CCGEdge *e = ccgSubSurf_getFaceEdge(f, S);
234     int edgeBase = *((int *)ccgSubSurf_getEdgeUserData(ss, e));
235     if (v == ccgSubSurf_getEdgeVert0(e)) {
236       return edgeBase + (gridSize - 1 - y) - 1;
237     }
238     else {
239       return edgeBase + (edgeSize - 2 - 1) - ((gridSize - 1 - y) - 1);
240     }
241   }
242   else if (y == gridSize - 1) {
243     CCGVert *v = ccgSubSurf_getFaceVert(f, S);
244     CCGEdge *e = ccgSubSurf_getFaceEdge(f, (S + numVerts - 1) % numVerts);
245     int edgeBase = *((int *)ccgSubSurf_getEdgeUserData(ss, e));
246     if (v == ccgSubSurf_getEdgeVert0(e)) {
247       return edgeBase + (gridSize - 1 - x) - 1;
248     }
249     else {
250       return edgeBase + (edgeSize - 2 - 1) - ((gridSize - 1 - x) - 1);
251     }
252   }
253   else if (x == 0 && y == 0) {
254     return faceBase;
255   }
256   else if (x == 0) {
257     S = (S + numVerts - 1) % numVerts;
258     return faceBase + 1 + (gridSize - 2) * S + (y - 1);
259   }
260   else if (y == 0) {
261     return faceBase + 1 + (gridSize - 2) * S + (x - 1);
262   }
263   else {
264     return faceBase + 1 + (gridSize - 2) * numVerts + S * (gridSize - 2) * (gridSize - 2) +
265            (y - 1) * (gridSize - 2) + (x - 1);
266   }
267 }
268
269 static void get_face_uv_map_vert(
270     UvVertMap *vmap, struct MPoly *mpoly, struct MLoop *ml, int fi, CCGVertHDL *fverts)
271 {
272   UvMapVert *v, *nv;
273   int j, nverts = mpoly[fi].totloop;
274
275   for (j = 0; j < nverts; j++) {
276     for (nv = v = BKE_mesh_uv_vert_map_get_vert(vmap, ml[j].v); v; v = v->next) {
277       if (v->separate) {
278         nv = v;
279       }
280       if (v->poly_index == fi) {
281         break;
282       }
283     }
284
285     fverts[j] = POINTER_FROM_UINT(mpoly[nv->poly_index].loopstart + nv->loop_of_poly_index);
286   }
287 }
288
289 static int ss_sync_from_uv(CCGSubSurf *ss, CCGSubSurf *origss, DerivedMesh *dm, MLoopUV *mloopuv)
290 {
291   MPoly *mpoly = dm->getPolyArray(dm);
292   MLoop *mloop = dm->getLoopArray(dm);
293   int totvert = dm->getNumVerts(dm);
294   int totface = dm->getNumPolys(dm);
295   int i, seam;
296   UvMapVert *v;
297   UvVertMap *vmap;
298   float limit[2];
299 #ifndef USE_DYNSIZE
300   CCGVertHDL *fverts = NULL;
301   BLI_array_declare(fverts);
302 #endif
303   EdgeSet *eset;
304   float uv[3] = {0.0f, 0.0f, 0.0f}; /* only first 2 values are written into */
305
306   limit[0] = limit[1] = STD_UV_CONNECT_LIMIT;
307   /* previous behavior here is without accounting for winding, however this causes stretching in
308    * UV map in really simple cases with mirror + subsurf, see second part of T44530. Also, initially
309    * intention is to treat merged vertices from mirror modifier as seams.
310    * This fixes a very old regression (2.49 was correct here) */
311   vmap = BKE_mesh_uv_vert_map_create(mpoly, mloop, mloopuv, totface, totvert, limit, false, true);
312   if (!vmap) {
313     return 0;
314   }
315
316   ccgSubSurf_initFullSync(ss);
317
318   /* create vertices */
319   for (i = 0; i < totvert; i++) {
320     if (!BKE_mesh_uv_vert_map_get_vert(vmap, i)) {
321       continue;
322     }
323
324     for (v = BKE_mesh_uv_vert_map_get_vert(vmap, i)->next; v; v = v->next) {
325       if (v->separate) {
326         break;
327       }
328     }
329
330     seam = (v != NULL);
331
332     for (v = BKE_mesh_uv_vert_map_get_vert(vmap, i); v; v = v->next) {
333       if (v->separate) {
334         CCGVert *ssv;
335         int loopid = mpoly[v->poly_index].loopstart + v->loop_of_poly_index;
336         CCGVertHDL vhdl = POINTER_FROM_INT(loopid);
337
338         copy_v2_v2(uv, mloopuv[loopid].uv);
339
340         ccgSubSurf_syncVert(ss, vhdl, uv, seam, &ssv);
341       }
342     }
343   }
344
345   /* create edges */
346   eset = BLI_edgeset_new_ex(__func__, BLI_EDGEHASH_SIZE_GUESS_FROM_POLYS(totface));
347
348   for (i = 0; i < totface; i++) {
349     MPoly *mp = &mpoly[i];
350     int nverts = mp->totloop;
351     int j, j_next;
352     CCGFace *origf = ccgSubSurf_getFace(origss, POINTER_FROM_INT(i));
353     /* unsigned int *fv = &mp->v1; */
354     MLoop *ml = mloop + mp->loopstart;
355
356 #ifdef USE_DYNSIZE
357     CCGVertHDL fverts[nverts];
358 #else
359     BLI_array_clear(fverts);
360     BLI_array_grow_items(fverts, nverts);
361 #endif
362
363     get_face_uv_map_vert(vmap, mpoly, ml, i, fverts);
364
365     for (j = 0, j_next = nverts - 1; j < nverts; j_next = j++) {
366       unsigned int v0 = POINTER_AS_UINT(fverts[j_next]);
367       unsigned int v1 = POINTER_AS_UINT(fverts[j]);
368
369       if (BLI_edgeset_add(eset, v0, v1)) {
370         CCGEdge *e, *orige = ccgSubSurf_getFaceEdge(origf, j_next);
371         CCGEdgeHDL ehdl = POINTER_FROM_INT(mp->loopstart + j_next);
372         float crease = ccgSubSurf_getEdgeCrease(orige);
373
374         ccgSubSurf_syncEdge(ss, ehdl, fverts[j_next], fverts[j], crease, &e);
375       }
376     }
377   }
378
379   BLI_edgeset_free(eset);
380
381   /* create faces */
382   for (i = 0; i < totface; i++) {
383     MPoly *mp = &mpoly[i];
384     MLoop *ml = &mloop[mp->loopstart];
385     int nverts = mp->totloop;
386     CCGFace *f;
387
388 #ifdef USE_DYNSIZE
389     CCGVertHDL fverts[nverts];
390 #else
391     BLI_array_clear(fverts);
392     BLI_array_grow_items(fverts, nverts);
393 #endif
394
395     get_face_uv_map_vert(vmap, mpoly, ml, i, fverts);
396     ccgSubSurf_syncFace(ss, POINTER_FROM_INT(i), nverts, fverts, &f);
397   }
398
399 #ifndef USE_DYNSIZE
400   BLI_array_free(fverts);
401 #endif
402
403   BKE_mesh_uv_vert_map_free(vmap);
404   ccgSubSurf_processSync(ss);
405
406   return 1;
407 }
408
409 #ifdef WITH_OPENSUBDIV
410 static void UNUSED_FUNCTION(set_subsurf_osd_ccg_uv)(CCGSubSurf *ss,
411                                                     DerivedMesh *dm,
412                                                     DerivedMesh *result,
413                                                     int layer_index)
414 {
415   CCGFace **faceMap;
416   MTFace *tf;
417   MLoopUV *mluv;
418   CCGFaceIterator fi;
419   int index, gridSize, gridFaces, totface, x, y, S;
420   MLoopUV *dmloopuv = CustomData_get_layer_n(&dm->loopData, CD_MLOOPUV, layer_index);
421   /* need to update both CD_MTFACE & CD_MLOOPUV, hrmf, we could get away with
422    * just tface except applying the modifier then looses subsurf UV */
423   MTFace *tface = CustomData_get_layer_n(&result->faceData, CD_MTFACE, layer_index);
424   MLoopUV *mloopuv = CustomData_get_layer_n(&result->loopData, CD_MLOOPUV, layer_index);
425
426   if (dmloopuv == NULL || (tface == NULL && mloopuv == NULL)) {
427     return;
428   }
429
430   ccgSubSurf_evaluatorSetFVarUV(ss, dm, layer_index);
431
432   /* get some info from CCGSubSurf */
433   totface = ccgSubSurf_getNumFaces(ss);
434   gridSize = ccgSubSurf_getGridSize(ss);
435   gridFaces = gridSize - 1;
436
437   /* make a map from original faces to CCGFaces */
438   faceMap = MEM_mallocN(totface * sizeof(*faceMap), "facemapuv");
439   for (ccgSubSurf_initFaceIterator(ss, &fi); !ccgFaceIterator_isStopped(&fi);
440        ccgFaceIterator_next(&fi)) {
441     CCGFace *f = ccgFaceIterator_getCurrent(&fi);
442     faceMap[POINTER_AS_INT(ccgSubSurf_getFaceFaceHandle(f))] = f;
443   }
444
445   /* load coordinates from uvss into tface */
446   tf = tface;
447   mluv = mloopuv;
448   for (index = 0; index < totface; index++) {
449     CCGFace *f = faceMap[index];
450     int numVerts = ccgSubSurf_getFaceNumVerts(f);
451     for (S = 0; S < numVerts; S++) {
452       for (y = 0; y < gridFaces; y++) {
453         for (x = 0; x < gridFaces; x++) {
454           const int delta[4][2] = {{0, 0}, {0, 1}, {1, 1}, {1, 0}};
455           float uv[4][2];
456           int i;
457           for (i = 0; i < 4; i++) {
458             const int dx = delta[i][0], dy = delta[i][1];
459             const float grid_u = ((float)(x + dx)) / (gridSize - 1),
460                         grid_v = ((float)(y + dy)) / (gridSize - 1);
461             ccgSubSurf_evaluatorFVarUV(ss, index, S, grid_u, grid_v, uv[i]);
462           }
463           if (tf) {
464             copy_v2_v2(tf->uv[0], uv[0]);
465             copy_v2_v2(tf->uv[1], uv[1]);
466             copy_v2_v2(tf->uv[2], uv[2]);
467             copy_v2_v2(tf->uv[3], uv[3]);
468             tf++;
469           }
470           if (mluv) {
471             copy_v2_v2(mluv[0].uv, uv[0]);
472             copy_v2_v2(mluv[1].uv, uv[1]);
473             copy_v2_v2(mluv[2].uv, uv[2]);
474             copy_v2_v2(mluv[3].uv, uv[3]);
475             mluv += 4;
476           }
477         }
478       }
479     }
480   }
481   MEM_freeN(faceMap);
482 }
483 #endif /* WITH_OPENSUBDIV */
484
485 static void set_subsurf_legacy_uv(CCGSubSurf *ss, DerivedMesh *dm, DerivedMesh *result, int n)
486 {
487   CCGSubSurf *uvss;
488   CCGFace **faceMap;
489   MTFace *tf;
490   MLoopUV *mluv;
491   CCGFaceIterator fi;
492   int index, gridSize, gridFaces, /*edgeSize,*/ totface, x, y, S;
493   MLoopUV *dmloopuv = CustomData_get_layer_n(&dm->loopData, CD_MLOOPUV, n);
494   /* need to update both CD_MTFACE & CD_MLOOPUV, hrmf, we could get away with
495    * just tface except applying the modifier then looses subsurf UV */
496   MTFace *tface = CustomData_get_layer_n(&result->faceData, CD_MTFACE, n);
497   MLoopUV *mloopuv = CustomData_get_layer_n(&result->loopData, CD_MLOOPUV, n);
498
499   if (!dmloopuv || (!tface && !mloopuv)) {
500     return;
501   }
502
503   /* create a CCGSubSurf from uv's */
504   uvss = _getSubSurf(NULL, ccgSubSurf_getSubdivisionLevels(ss), 2, CCG_USE_ARENA);
505
506   if (!ss_sync_from_uv(uvss, ss, dm, dmloopuv)) {
507     ccgSubSurf_free(uvss);
508     return;
509   }
510
511   /* get some info from CCGSubSurf */
512   totface = ccgSubSurf_getNumFaces(uvss);
513   /* edgeSize = ccgSubSurf_getEdgeSize(uvss); */ /*UNUSED*/
514   gridSize = ccgSubSurf_getGridSize(uvss);
515   gridFaces = gridSize - 1;
516
517   /* make a map from original faces to CCGFaces */
518   faceMap = MEM_mallocN(totface * sizeof(*faceMap), "facemapuv");
519   for (ccgSubSurf_initFaceIterator(uvss, &fi); !ccgFaceIterator_isStopped(&fi);
520        ccgFaceIterator_next(&fi)) {
521     CCGFace *f = ccgFaceIterator_getCurrent(&fi);
522     faceMap[POINTER_AS_INT(ccgSubSurf_getFaceFaceHandle(f))] = f;
523   }
524
525   /* load coordinates from uvss into tface */
526   tf = tface;
527   mluv = mloopuv;
528
529   for (index = 0; index < totface; index++) {
530     CCGFace *f = faceMap[index];
531     int numVerts = ccgSubSurf_getFaceNumVerts(f);
532
533     for (S = 0; S < numVerts; S++) {
534       float(*faceGridData)[2] = ccgSubSurf_getFaceGridDataArray(uvss, f, S);
535
536       for (y = 0; y < gridFaces; y++) {
537         for (x = 0; x < gridFaces; x++) {
538           float *a = faceGridData[(y + 0) * gridSize + x + 0];
539           float *b = faceGridData[(y + 0) * gridSize + x + 1];
540           float *c = faceGridData[(y + 1) * gridSize + x + 1];
541           float *d = faceGridData[(y + 1) * gridSize + x + 0];
542
543           if (tf) {
544             copy_v2_v2(tf->uv[0], a);
545             copy_v2_v2(tf->uv[1], d);
546             copy_v2_v2(tf->uv[2], c);
547             copy_v2_v2(tf->uv[3], b);
548             tf++;
549           }
550
551           if (mluv) {
552             copy_v2_v2(mluv[0].uv, a);
553             copy_v2_v2(mluv[1].uv, d);
554             copy_v2_v2(mluv[2].uv, c);
555             copy_v2_v2(mluv[3].uv, b);
556             mluv += 4;
557           }
558         }
559       }
560     }
561   }
562
563   ccgSubSurf_free(uvss);
564   MEM_freeN(faceMap);
565 }
566
567 static void set_subsurf_uv(CCGSubSurf *ss, DerivedMesh *dm, DerivedMesh *result, int layer_index)
568 {
569 #ifdef WITH_OPENSUBDIV
570   if (!ccgSubSurf_needGrids(ss)) {
571     /* GPU backend is used, no need to evaluate UVs on CPU. */
572     /* TODO(sergey): Think of how to support edit mode of UVs. */
573   }
574   else
575 #endif
576   {
577     set_subsurf_legacy_uv(ss, dm, result, layer_index);
578   }
579 }
580
581 /* face weighting */
582 #define SUB_ELEMS_FACE 50
583 typedef float FaceVertWeight[SUB_ELEMS_FACE][SUB_ELEMS_FACE];
584
585 typedef struct FaceVertWeightEntry {
586   FaceVertWeight *weight;
587   float *w;
588   int valid;
589 } FaceVertWeightEntry;
590
591 typedef struct WeightTable {
592   FaceVertWeightEntry *weight_table;
593   int len;
594 } WeightTable;
595
596 static float *get_ss_weights(WeightTable *wtable, int gridCuts, int faceLen)
597 {
598   int x, y, i, j;
599   float *w, w1, w2, w4, fac, fac2, fx, fy;
600
601   if (wtable->len <= faceLen) {
602     void *tmp = MEM_callocN(sizeof(FaceVertWeightEntry) * (faceLen + 1), "weight table alloc 2");
603
604     if (wtable->len) {
605       memcpy(tmp, wtable->weight_table, sizeof(FaceVertWeightEntry) * wtable->len);
606       MEM_freeN(wtable->weight_table);
607     }
608
609     wtable->weight_table = tmp;
610     wtable->len = faceLen + 1;
611   }
612
613   if (!wtable->weight_table[faceLen].valid) {
614     wtable->weight_table[faceLen].valid = 1;
615     wtable->weight_table[faceLen].w = w = MEM_callocN(
616         sizeof(float) * faceLen * faceLen * (gridCuts + 2) * (gridCuts + 2), "weight table alloc");
617     fac = 1.0f / (float)faceLen;
618
619     for (i = 0; i < faceLen; i++) {
620       for (x = 0; x < gridCuts + 2; x++) {
621         for (y = 0; y < gridCuts + 2; y++) {
622           fx = 0.5f - (float)x / (float)(gridCuts + 1) / 2.0f;
623           fy = 0.5f - (float)y / (float)(gridCuts + 1) / 2.0f;
624
625           fac2 = faceLen - 4;
626           w1 = (1.0f - fx) * (1.0f - fy) + (-fac2 * fx * fy * fac);
627           w2 = (1.0f - fx + fac2 * fx * -fac) * (fy);
628           w4 = (fx) * (1.0f - fy + -fac2 * fy * fac);
629
630           /* these values aren't used for tri's and cause divide by zero */
631           if (faceLen > 3) {
632             fac2 = 1.0f - (w1 + w2 + w4);
633             fac2 = fac2 / (float)(faceLen - 3);
634             for (j = 0; j < faceLen; j++) {
635               w[j] = fac2;
636             }
637           }
638
639           w[i] = w1;
640           w[(i - 1 + faceLen) % faceLen] = w2;
641           w[(i + 1) % faceLen] = w4;
642
643           w += faceLen;
644         }
645       }
646     }
647   }
648
649   return wtable->weight_table[faceLen].w;
650 }
651
652 static void free_ss_weights(WeightTable *wtable)
653 {
654   int i;
655
656   for (i = 0; i < wtable->len; i++) {
657     if (wtable->weight_table[i].valid) {
658       MEM_freeN(wtable->weight_table[i].w);
659     }
660   }
661
662   if (wtable->weight_table) {
663     MEM_freeN(wtable->weight_table);
664   }
665 }
666
667 static void ss_sync_ccg_from_derivedmesh(CCGSubSurf *ss,
668                                          DerivedMesh *dm,
669                                          float (*vertexCos)[3],
670                                          int useFlatSubdiv)
671 {
672   float creaseFactor = (float)ccgSubSurf_getSubdivisionLevels(ss);
673 #ifndef USE_DYNSIZE
674   CCGVertHDL *fVerts = NULL;
675   BLI_array_declare(fVerts);
676 #endif
677   MVert *mvert = dm->getVertArray(dm);
678   MEdge *medge = dm->getEdgeArray(dm);
679   /* MFace *mface = dm->getTessFaceArray(dm); */ /* UNUSED */
680   MVert *mv;
681   MEdge *me;
682   MLoop *mloop = dm->getLoopArray(dm), *ml;
683   MPoly *mpoly = dm->getPolyArray(dm), *mp;
684   /*MFace *mf;*/ /*UNUSED*/
685   int totvert = dm->getNumVerts(dm);
686   int totedge = dm->getNumEdges(dm);
687   /*int totface = dm->getNumTessFaces(dm);*/ /*UNUSED*/
688   /*int totpoly = dm->getNumFaces(dm);*/     /*UNUSED*/
689   int i, j;
690   int *index;
691
692   ccgSubSurf_initFullSync(ss);
693
694   mv = mvert;
695   index = (int *)dm->getVertDataArray(dm, CD_ORIGINDEX);
696   for (i = 0; i < totvert; i++, mv++) {
697     CCGVert *v;
698
699     if (vertexCos) {
700       ccgSubSurf_syncVert(ss, POINTER_FROM_INT(i), vertexCos[i], 0, &v);
701     }
702     else {
703       ccgSubSurf_syncVert(ss, POINTER_FROM_INT(i), mv->co, 0, &v);
704     }
705
706     ((int *)ccgSubSurf_getVertUserData(ss, v))[1] = (index) ? *index++ : i;
707   }
708
709   me = medge;
710   index = (int *)dm->getEdgeDataArray(dm, CD_ORIGINDEX);
711   for (i = 0; i < totedge; i++, me++) {
712     CCGEdge *e;
713     float crease;
714
715     crease = useFlatSubdiv ? creaseFactor : me->crease * creaseFactor / 255.0f;
716
717     ccgSubSurf_syncEdge(
718         ss, POINTER_FROM_INT(i), POINTER_FROM_UINT(me->v1), POINTER_FROM_UINT(me->v2), crease, &e);
719
720     ((int *)ccgSubSurf_getEdgeUserData(ss, e))[1] = (index) ? *index++ : i;
721   }
722
723   mp = mpoly;
724   index = (int *)dm->getPolyDataArray(dm, CD_ORIGINDEX);
725   for (i = 0; i < dm->numPolyData; i++, mp++) {
726     CCGFace *f;
727
728 #ifdef USE_DYNSIZE
729     CCGVertHDL fVerts[mp->totloop];
730 #else
731     BLI_array_clear(fVerts);
732     BLI_array_grow_items(fVerts, mp->totloop);
733 #endif
734
735     ml = mloop + mp->loopstart;
736     for (j = 0; j < mp->totloop; j++, ml++) {
737       fVerts[j] = POINTER_FROM_UINT(ml->v);
738     }
739
740     /* this is very bad, means mesh is internally inconsistent.
741      * it is not really possible to continue without modifying
742      * other parts of code significantly to handle missing faces.
743      * since this really shouldn't even be possible we just bail.*/
744     if (ccgSubSurf_syncFace(ss, POINTER_FROM_INT(i), mp->totloop, fVerts, &f) ==
745         eCCGError_InvalidValue) {
746       static int hasGivenError = 0;
747
748       if (!hasGivenError) {
749         //XXX error("Unrecoverable error in SubSurf calculation,"
750         //      " mesh is inconsistent.");
751
752         hasGivenError = 1;
753       }
754
755       return;
756     }
757
758     ((int *)ccgSubSurf_getFaceUserData(ss, f))[1] = (index) ? *index++ : i;
759   }
760
761   ccgSubSurf_processSync(ss);
762
763 #ifndef USE_DYNSIZE
764   BLI_array_free(fVerts);
765 #endif
766 }
767
768 #ifdef WITH_OPENSUBDIV
769 static void ss_sync_osd_from_derivedmesh(CCGSubSurf *ss, DerivedMesh *dm)
770 {
771   ccgSubSurf_initFullSync(ss);
772   ccgSubSurf_prepareTopologyRefiner(ss, dm);
773   ccgSubSurf_processSync(ss);
774 }
775 #endif /* WITH_OPENSUBDIV */
776
777 static void ss_sync_from_derivedmesh(CCGSubSurf *ss,
778                                      DerivedMesh *dm,
779                                      float (*vertexCos)[3],
780                                      int use_flat_subdiv,
781                                      bool use_subdiv_uvs)
782 {
783 #ifndef WITH_OPENSUBDIV
784   UNUSED_VARS(use_subdiv_uvs);
785 #endif
786
787 #ifdef WITH_OPENSUBDIV
788   /* Reset all related descriptors if actual mesh topology changed or if
789    * other evaluation-related settings changed.
790    */
791   if (!ccgSubSurf_needGrids(ss)) {
792     /* TODO(sergey): Use vertex coordinates and flat subdiv flag. */
793     ccgSubSurf__sync_subdivUvs(ss, use_subdiv_uvs);
794     ccgSubSurf_checkTopologyChanged(ss, dm);
795     ss_sync_osd_from_derivedmesh(ss, dm);
796   }
797   else
798 #endif
799   {
800     ss_sync_ccg_from_derivedmesh(ss, dm, vertexCos, use_flat_subdiv);
801   }
802 }
803
804 /***/
805
806 static int ccgDM_getVertMapIndex(CCGSubSurf *ss, CCGVert *v)
807 {
808   return ((int *)ccgSubSurf_getVertUserData(ss, v))[1];
809 }
810
811 static int ccgDM_getEdgeMapIndex(CCGSubSurf *ss, CCGEdge *e)
812 {
813   return ((int *)ccgSubSurf_getEdgeUserData(ss, e))[1];
814 }
815
816 static int ccgDM_getFaceMapIndex(CCGSubSurf *ss, CCGFace *f)
817 {
818   return ((int *)ccgSubSurf_getFaceUserData(ss, f))[1];
819 }
820
821 static void minmax_v3_v3v3(const float vec[3], float min[3], float max[3])
822 {
823   if (min[0] > vec[0]) {
824     min[0] = vec[0];
825   }
826   if (min[1] > vec[1]) {
827     min[1] = vec[1];
828   }
829   if (min[2] > vec[2]) {
830     min[2] = vec[2];
831   }
832   if (max[0] < vec[0]) {
833     max[0] = vec[0];
834   }
835   if (max[1] < vec[1]) {
836     max[1] = vec[1];
837   }
838   if (max[2] < vec[2]) {
839     max[2] = vec[2];
840   }
841 }
842
843 static void ccgDM_getMinMax(DerivedMesh *dm, float r_min[3], float r_max[3])
844 {
845   CCGDerivedMesh *ccgdm = (CCGDerivedMesh *)dm;
846   CCGSubSurf *ss = ccgdm->ss;
847   CCGVertIterator vi;
848   CCGEdgeIterator ei;
849   CCGFaceIterator fi;
850   CCGKey key;
851   int i, edgeSize = ccgSubSurf_getEdgeSize(ss);
852   int gridSize = ccgSubSurf_getGridSize(ss);
853
854 #ifdef WITH_OPENSUBDIV
855   if (ccgdm->useGpuBackend) {
856     ccgSubSurf_getMinMax(ccgdm->ss, r_min, r_max);
857     return;
858   }
859 #endif
860
861   CCG_key_top_level(&key, ss);
862
863   if (!ccgSubSurf_getNumVerts(ss)) {
864     r_min[0] = r_min[1] = r_min[2] = r_max[0] = r_max[1] = r_max[2] = 0.0;
865   }
866
867   for (ccgSubSurf_initVertIterator(ss, &vi); !ccgVertIterator_isStopped(&vi);
868        ccgVertIterator_next(&vi)) {
869     CCGVert *v = ccgVertIterator_getCurrent(&vi);
870     float *co = ccgSubSurf_getVertData(ss, v);
871
872     minmax_v3_v3v3(co, r_min, r_max);
873   }
874
875   for (ccgSubSurf_initEdgeIterator(ss, &ei); !ccgEdgeIterator_isStopped(&ei);
876        ccgEdgeIterator_next(&ei)) {
877     CCGEdge *e = ccgEdgeIterator_getCurrent(&ei);
878     CCGElem *edgeData = ccgSubSurf_getEdgeDataArray(ss, e);
879
880     for (i = 0; i < edgeSize; i++) {
881       minmax_v3_v3v3(CCG_elem_offset_co(&key, edgeData, i), r_min, r_max);
882     }
883   }
884
885   for (ccgSubSurf_initFaceIterator(ss, &fi); !ccgFaceIterator_isStopped(&fi);
886        ccgFaceIterator_next(&fi)) {
887     CCGFace *f = ccgFaceIterator_getCurrent(&fi);
888     int S, x, y, numVerts = ccgSubSurf_getFaceNumVerts(f);
889
890     for (S = 0; S < numVerts; S++) {
891       CCGElem *faceGridData = ccgSubSurf_getFaceGridDataArray(ss, f, S);
892
893       for (y = 0; y < gridSize; y++) {
894         for (x = 0; x < gridSize; x++) {
895           minmax_v3_v3v3(CCG_grid_elem_co(&key, faceGridData, x, y), r_min, r_max);
896         }
897       }
898     }
899   }
900 }
901
902 static int ccgDM_getNumVerts(DerivedMesh *dm)
903 {
904   CCGDerivedMesh *ccgdm = (CCGDerivedMesh *)dm;
905
906   return ccgSubSurf_getNumFinalVerts(ccgdm->ss);
907 }
908
909 static int ccgDM_getNumEdges(DerivedMesh *dm)
910 {
911   CCGDerivedMesh *ccgdm = (CCGDerivedMesh *)dm;
912
913   return ccgSubSurf_getNumFinalEdges(ccgdm->ss);
914 }
915
916 static int ccgDM_getNumPolys(DerivedMesh *dm)
917 {
918   CCGDerivedMesh *ccgdm = (CCGDerivedMesh *)dm;
919
920   return ccgSubSurf_getNumFinalFaces(ccgdm->ss);
921 }
922
923 static int ccgDM_getNumTessFaces(DerivedMesh *dm)
924 {
925   return dm->numTessFaceData;
926 }
927
928 static int ccgDM_getNumLoops(DerivedMesh *dm)
929 {
930   CCGDerivedMesh *ccgdm = (CCGDerivedMesh *)dm;
931
932   /* All subsurf faces are quads */
933   return 4 * ccgSubSurf_getNumFinalFaces(ccgdm->ss);
934 }
935
936 static void ccgDM_getFinalVert(DerivedMesh *dm, int vertNum, MVert *mv)
937 {
938   CCGDerivedMesh *ccgdm = (CCGDerivedMesh *)dm;
939   CCGSubSurf *ss = ccgdm->ss;
940   CCGElem *vd;
941   CCGKey key;
942   int i;
943
944   CCG_key_top_level(&key, ss);
945   memset(mv, 0, sizeof(*mv));
946
947   if ((vertNum < ccgdm->edgeMap[0].startVert) && (ccgSubSurf_getNumFaces(ss) > 0)) {
948     /* this vert comes from face data */
949     int lastface = ccgSubSurf_getNumFaces(ss) - 1;
950     CCGFace *f;
951     int x, y, grid, numVerts;
952     int offset;
953     int gridSize = ccgSubSurf_getGridSize(ss);
954     int gridSideVerts;
955     int gridInternalVerts;
956     int gridSideEnd;
957     int gridInternalEnd;
958
959     i = 0;
960     while (i < lastface && vertNum >= ccgdm->faceMap[i + 1].startVert) {
961       i++;
962     }
963
964     f = ccgdm->faceMap[i].face;
965     numVerts = ccgSubSurf_getFaceNumVerts(f);
966
967     gridSideVerts = gridSize - 2;
968     gridInternalVerts = gridSideVerts * gridSideVerts;
969
970     gridSideEnd = 1 + numVerts * gridSideVerts;
971     gridInternalEnd = gridSideEnd + numVerts * gridInternalVerts;
972
973     offset = vertNum - ccgdm->faceMap[i].startVert;
974     if (offset < 1) {
975       vd = ccgSubSurf_getFaceCenterData(f);
976       copy_v3_v3(mv->co, CCG_elem_co(&key, vd));
977       normal_float_to_short_v3(mv->no, CCG_elem_no(&key, vd));
978     }
979     else if (offset < gridSideEnd) {
980       offset -= 1;
981       grid = offset / gridSideVerts;
982       x = offset % gridSideVerts + 1;
983       vd = ccgSubSurf_getFaceGridEdgeData(ss, f, grid, x);
984       copy_v3_v3(mv->co, CCG_elem_co(&key, vd));
985       normal_float_to_short_v3(mv->no, CCG_elem_no(&key, vd));
986     }
987     else if (offset < gridInternalEnd) {
988       offset -= gridSideEnd;
989       grid = offset / gridInternalVerts;
990       offset %= gridInternalVerts;
991       y = offset / gridSideVerts + 1;
992       x = offset % gridSideVerts + 1;
993       vd = ccgSubSurf_getFaceGridData(ss, f, grid, x, y);
994       copy_v3_v3(mv->co, CCG_elem_co(&key, vd));
995       normal_float_to_short_v3(mv->no, CCG_elem_no(&key, vd));
996     }
997   }
998   else if ((vertNum < ccgdm->vertMap[0].startVert) && (ccgSubSurf_getNumEdges(ss) > 0)) {
999     /* this vert comes from edge data */
1000     CCGEdge *e;
1001     int lastedge = ccgSubSurf_getNumEdges(ss) - 1;
1002     int x;
1003
1004     i = 0;
1005     while (i < lastedge && vertNum >= ccgdm->edgeMap[i + 1].startVert) {
1006       i++;
1007     }
1008
1009     e = ccgdm->edgeMap[i].edge;
1010
1011     x = vertNum - ccgdm->edgeMap[i].startVert + 1;
1012     vd = ccgSubSurf_getEdgeData(ss, e, x);
1013     copy_v3_v3(mv->co, CCG_elem_co(&key, vd));
1014     normal_float_to_short_v3(mv->no, CCG_elem_no(&key, vd));
1015   }
1016   else {
1017     /* this vert comes from vert data */
1018     CCGVert *v;
1019     i = vertNum - ccgdm->vertMap[0].startVert;
1020
1021     v = ccgdm->vertMap[i].vert;
1022     vd = ccgSubSurf_getVertData(ss, v);
1023     copy_v3_v3(mv->co, CCG_elem_co(&key, vd));
1024     normal_float_to_short_v3(mv->no, CCG_elem_no(&key, vd));
1025   }
1026 }
1027
1028 static void ccgDM_getFinalVertCo(DerivedMesh *dm, int vertNum, float r_co[3])
1029 {
1030   MVert mvert;
1031
1032   ccgDM_getFinalVert(dm, vertNum, &mvert);
1033   copy_v3_v3(r_co, mvert.co);
1034 }
1035
1036 static void ccgDM_getFinalVertNo(DerivedMesh *dm, int vertNum, float r_no[3])
1037 {
1038   MVert mvert;
1039
1040   ccgDM_getFinalVert(dm, vertNum, &mvert);
1041   normal_short_to_float_v3(r_no, mvert.no);
1042 }
1043
1044 static void ccgDM_getFinalEdge(DerivedMesh *dm, int edgeNum, MEdge *med)
1045 {
1046   CCGDerivedMesh *ccgdm = (CCGDerivedMesh *)dm;
1047   CCGSubSurf *ss = ccgdm->ss;
1048   int i;
1049
1050   memset(med, 0, sizeof(*med));
1051
1052   if (edgeNum < ccgdm->edgeMap[0].startEdge) {
1053     /* this edge comes from face data */
1054     int lastface = ccgSubSurf_getNumFaces(ss) - 1;
1055     CCGFace *f;
1056     int x, y, grid /*, numVerts*/;
1057     int offset;
1058     int gridSize = ccgSubSurf_getGridSize(ss);
1059     int edgeSize = ccgSubSurf_getEdgeSize(ss);
1060     int gridSideEdges;
1061     int gridInternalEdges;
1062
1063     i = 0;
1064     while (i < lastface && edgeNum >= ccgdm->faceMap[i + 1].startEdge) {
1065       i++;
1066     }
1067
1068     f = ccgdm->faceMap[i].face;
1069     /* numVerts = ccgSubSurf_getFaceNumVerts(f); */ /*UNUSED*/
1070
1071     gridSideEdges = gridSize - 1;
1072     gridInternalEdges = (gridSideEdges - 1) * gridSideEdges * 2;
1073
1074     offset = edgeNum - ccgdm->faceMap[i].startEdge;
1075     grid = offset / (gridSideEdges + gridInternalEdges);
1076     offset %= (gridSideEdges + gridInternalEdges);
1077
1078     if (offset < gridSideEdges) {
1079       x = offset;
1080       med->v1 = getFaceIndex(ss, f, grid, x, 0, edgeSize, gridSize);
1081       med->v2 = getFaceIndex(ss, f, grid, x + 1, 0, edgeSize, gridSize);
1082     }
1083     else {
1084       offset -= gridSideEdges;
1085       x = (offset / 2) / gridSideEdges + 1;
1086       y = (offset / 2) % gridSideEdges;
1087       if (offset % 2 == 0) {
1088         med->v1 = getFaceIndex(ss, f, grid, x, y, edgeSize, gridSize);
1089         med->v2 = getFaceIndex(ss, f, grid, x, y + 1, edgeSize, gridSize);
1090       }
1091       else {
1092         med->v1 = getFaceIndex(ss, f, grid, y, x, edgeSize, gridSize);
1093         med->v2 = getFaceIndex(ss, f, grid, y + 1, x, edgeSize, gridSize);
1094       }
1095     }
1096   }
1097   else {
1098     /* this vert comes from edge data */
1099     CCGEdge *e;
1100     int edgeSize = ccgSubSurf_getEdgeSize(ss);
1101     int x;
1102     short *edgeFlag;
1103     unsigned int flags = 0;
1104
1105     i = (edgeNum - ccgdm->edgeMap[0].startEdge) / (edgeSize - 1);
1106
1107     e = ccgdm->edgeMap[i].edge;
1108
1109     if (!ccgSubSurf_getEdgeNumFaces(e)) {
1110       flags |= ME_LOOSEEDGE;
1111     }
1112
1113     x = edgeNum - ccgdm->edgeMap[i].startEdge;
1114
1115     med->v1 = getEdgeIndex(ss, e, x, edgeSize);
1116     med->v2 = getEdgeIndex(ss, e, x + 1, edgeSize);
1117
1118     edgeFlag = (ccgdm->edgeFlags) ? &ccgdm->edgeFlags[i] : NULL;
1119     if (edgeFlag) {
1120       flags |= (*edgeFlag & (ME_SEAM | ME_SHARP)) | ME_EDGEDRAW | ME_EDGERENDER;
1121     }
1122     else {
1123       flags |= ME_EDGEDRAW | ME_EDGERENDER;
1124     }
1125
1126     med->flag = flags;
1127   }
1128 }
1129
1130 static void ccgDM_getFinalFace(DerivedMesh *dm, int faceNum, MFace *mf)
1131 {
1132   CCGDerivedMesh *ccgdm = (CCGDerivedMesh *)dm;
1133   CCGSubSurf *ss = ccgdm->ss;
1134   int gridSize = ccgSubSurf_getGridSize(ss);
1135   int edgeSize = ccgSubSurf_getEdgeSize(ss);
1136   int gridSideEdges = gridSize - 1;
1137   int gridFaces = gridSideEdges * gridSideEdges;
1138   int i;
1139   CCGFace *f;
1140   /*int numVerts;*/
1141   int offset;
1142   int grid;
1143   int x, y;
1144   /*int lastface = ccgSubSurf_getNumFaces(ss) - 1;*/ /*UNUSED*/
1145   DMFlagMat *faceFlags = ccgdm->faceFlags;
1146
1147   memset(mf, 0, sizeof(*mf));
1148   if (faceNum >= ccgdm->dm.numTessFaceData) {
1149     return;
1150   }
1151
1152   i = ccgdm->reverseFaceMap[faceNum];
1153
1154   f = ccgdm->faceMap[i].face;
1155   /*numVerts = ccgSubSurf_getFaceNumVerts(f);*/ /*UNUSED*/
1156
1157   offset = faceNum - ccgdm->faceMap[i].startFace;
1158   grid = offset / gridFaces;
1159   offset %= gridFaces;
1160   y = offset / gridSideEdges;
1161   x = offset % gridSideEdges;
1162
1163   mf->v1 = getFaceIndex(ss, f, grid, x + 0, y + 0, edgeSize, gridSize);
1164   mf->v2 = getFaceIndex(ss, f, grid, x + 0, y + 1, edgeSize, gridSize);
1165   mf->v3 = getFaceIndex(ss, f, grid, x + 1, y + 1, edgeSize, gridSize);
1166   mf->v4 = getFaceIndex(ss, f, grid, x + 1, y + 0, edgeSize, gridSize);
1167
1168   if (faceFlags) {
1169     mf->flag = faceFlags[i].flag;
1170     mf->mat_nr = faceFlags[i].mat_nr;
1171   }
1172   else {
1173     mf->flag = ME_SMOOTH;
1174   }
1175
1176   mf->edcode = 0;
1177 }
1178
1179 /* Translate GridHidden into the ME_HIDE flag for MVerts. Assumes
1180  * vertices are in the order output by ccgDM_copyFinalVertArray. */
1181 void subsurf_copy_grid_hidden(DerivedMesh *dm,
1182                               const MPoly *mpoly,
1183                               MVert *mvert,
1184                               const MDisps *mdisps)
1185 {
1186   CCGDerivedMesh *ccgdm = (CCGDerivedMesh *)dm;
1187   CCGSubSurf *ss = ccgdm->ss;
1188   int level = ccgSubSurf_getSubdivisionLevels(ss);
1189   int gridSize = ccgSubSurf_getGridSize(ss);
1190   int edgeSize = ccgSubSurf_getEdgeSize(ss);
1191   int totface = ccgSubSurf_getNumFaces(ss);
1192   int i, j, x, y;
1193
1194   for (i = 0; i < totface; i++) {
1195     CCGFace *f = ccgdm->faceMap[i].face;
1196
1197     for (j = 0; j < mpoly[i].totloop; j++) {
1198       const MDisps *md = &mdisps[mpoly[i].loopstart + j];
1199       int hidden_gridsize = BKE_ccg_gridsize(md->level);
1200       int factor = BKE_ccg_factor(level, md->level);
1201       BLI_bitmap *hidden = md->hidden;
1202
1203       if (!hidden) {
1204         continue;
1205       }
1206
1207       for (y = 0; y < gridSize; y++) {
1208         for (x = 0; x < gridSize; x++) {
1209           int vndx, offset;
1210
1211           vndx = getFaceIndex(ss, f, j, x, y, edgeSize, gridSize);
1212           offset = (y * factor) * hidden_gridsize + (x * factor);
1213           if (BLI_BITMAP_TEST(hidden, offset)) {
1214             mvert[vndx].flag |= ME_HIDE;
1215           }
1216         }
1217       }
1218     }
1219   }
1220 }
1221
1222 /* Translate GridPaintMask into vertex paint masks. Assumes vertices
1223  * are in the order output by ccgDM_copyFinalVertArray. */
1224 void subsurf_copy_grid_paint_mask(DerivedMesh *dm,
1225                                   const MPoly *mpoly,
1226                                   float *paint_mask,
1227                                   const GridPaintMask *grid_paint_mask)
1228 {
1229   CCGDerivedMesh *ccgdm = (CCGDerivedMesh *)dm;
1230   CCGSubSurf *ss = ccgdm->ss;
1231   int level = ccgSubSurf_getSubdivisionLevels(ss);
1232   int gridSize = ccgSubSurf_getGridSize(ss);
1233   int edgeSize = ccgSubSurf_getEdgeSize(ss);
1234   int totface = ccgSubSurf_getNumFaces(ss);
1235   int i, j, x, y, factor, gpm_gridsize;
1236
1237   for (i = 0; i < totface; i++) {
1238     CCGFace *f = ccgdm->faceMap[i].face;
1239     const MPoly *p = &mpoly[i];
1240
1241     for (j = 0; j < p->totloop; j++) {
1242       const GridPaintMask *gpm = &grid_paint_mask[p->loopstart + j];
1243       if (!gpm->data) {
1244         continue;
1245       }
1246
1247       factor = BKE_ccg_factor(level, gpm->level);
1248       gpm_gridsize = BKE_ccg_gridsize(gpm->level);
1249
1250       for (y = 0; y < gridSize; y++) {
1251         for (x = 0; x < gridSize; x++) {
1252           int vndx, offset;
1253
1254           vndx = getFaceIndex(ss, f, j, x, y, edgeSize, gridSize);
1255           offset = y * factor * gpm_gridsize + x * factor;
1256           paint_mask[vndx] = gpm->data[offset];
1257         }
1258       }
1259     }
1260   }
1261 }
1262
1263 /* utility function */
1264 BLI_INLINE void ccgDM_to_MVert(MVert *mv, const CCGKey *key, CCGElem *elem)
1265 {
1266   copy_v3_v3(mv->co, CCG_elem_co(key, elem));
1267   normal_float_to_short_v3(mv->no, CCG_elem_no(key, elem));
1268   mv->flag = mv->bweight = 0;
1269 }
1270
1271 static void ccgDM_copyFinalVertArray(DerivedMesh *dm, MVert *mvert)
1272 {
1273   CCGDerivedMesh *ccgdm = (CCGDerivedMesh *)dm;
1274   CCGSubSurf *ss = ccgdm->ss;
1275   CCGElem *vd;
1276   CCGKey key;
1277   int index;
1278   int totvert, totedge, totface;
1279   int gridSize = ccgSubSurf_getGridSize(ss);
1280   int edgeSize = ccgSubSurf_getEdgeSize(ss);
1281   unsigned int i = 0;
1282
1283   CCG_key_top_level(&key, ss);
1284
1285   totface = ccgSubSurf_getNumFaces(ss);
1286   for (index = 0; index < totface; index++) {
1287     CCGFace *f = ccgdm->faceMap[index].face;
1288     int x, y, S, numVerts = ccgSubSurf_getFaceNumVerts(f);
1289
1290     vd = ccgSubSurf_getFaceCenterData(f);
1291     ccgDM_to_MVert(&mvert[i++], &key, vd);
1292
1293     for (S = 0; S < numVerts; S++) {
1294       for (x = 1; x < gridSize - 1; x++) {
1295         vd = ccgSubSurf_getFaceGridEdgeData(ss, f, S, x);
1296         ccgDM_to_MVert(&mvert[i++], &key, vd);
1297       }
1298     }
1299
1300     for (S = 0; S < numVerts; S++) {
1301       for (y = 1; y < gridSize - 1; y++) {
1302         for (x = 1; x < gridSize - 1; x++) {
1303           vd = ccgSubSurf_getFaceGridData(ss, f, S, x, y);
1304           ccgDM_to_MVert(&mvert[i++], &key, vd);
1305         }
1306       }
1307     }
1308   }
1309
1310   totedge = ccgSubSurf_getNumEdges(ss);
1311   for (index = 0; index < totedge; index++) {
1312     CCGEdge *e = ccgdm->edgeMap[index].edge;
1313     int x;
1314
1315     for (x = 1; x < edgeSize - 1; x++) {
1316       /* This gives errors with -debug-fpe
1317        * the normals don't seem to be unit length.
1318        * this is most likely caused by edges with no
1319        * faces which are now zerod out, see comment in:
1320        * ccgSubSurf__calcVertNormals(), - campbell */
1321       vd = ccgSubSurf_getEdgeData(ss, e, x);
1322       ccgDM_to_MVert(&mvert[i++], &key, vd);
1323     }
1324   }
1325
1326   totvert = ccgSubSurf_getNumVerts(ss);
1327   for (index = 0; index < totvert; index++) {
1328     CCGVert *v = ccgdm->vertMap[index].vert;
1329
1330     vd = ccgSubSurf_getVertData(ss, v);
1331     ccgDM_to_MVert(&mvert[i++], &key, vd);
1332   }
1333 }
1334
1335 /* utility function */
1336 BLI_INLINE void ccgDM_to_MEdge(MEdge *med, const int v1, const int v2, const short flag)
1337 {
1338   med->v1 = v1;
1339   med->v2 = v2;
1340   med->crease = med->bweight = 0;
1341   med->flag = flag;
1342 }
1343
1344 static void ccgDM_copyFinalEdgeArray(DerivedMesh *dm, MEdge *medge)
1345 {
1346   CCGDerivedMesh *ccgdm = (CCGDerivedMesh *)dm;
1347   CCGSubSurf *ss = ccgdm->ss;
1348   int index;
1349   int totedge, totface;
1350   int gridSize = ccgSubSurf_getGridSize(ss);
1351   int edgeSize = ccgSubSurf_getEdgeSize(ss);
1352   unsigned int i = 0;
1353   short *edgeFlags = ccgdm->edgeFlags;
1354   const short ed_interior_flag = ccgdm->drawInteriorEdges ? (ME_EDGEDRAW | ME_EDGERENDER) : 0;
1355
1356   totface = ccgSubSurf_getNumFaces(ss);
1357   for (index = 0; index < totface; index++) {
1358     CCGFace *f = ccgdm->faceMap[index].face;
1359     int x, y, S, numVerts = ccgSubSurf_getFaceNumVerts(f);
1360
1361     for (S = 0; S < numVerts; S++) {
1362       for (x = 0; x < gridSize - 1; x++) {
1363         ccgDM_to_MEdge(&medge[i++],
1364                        getFaceIndex(ss, f, S, x, 0, edgeSize, gridSize),
1365                        getFaceIndex(ss, f, S, x + 1, 0, edgeSize, gridSize),
1366                        ed_interior_flag);
1367       }
1368
1369       for (x = 1; x < gridSize - 1; x++) {
1370         for (y = 0; y < gridSize - 1; y++) {
1371           ccgDM_to_MEdge(&medge[i++],
1372                          getFaceIndex(ss, f, S, x, y, edgeSize, gridSize),
1373                          getFaceIndex(ss, f, S, x, y + 1, edgeSize, gridSize),
1374                          ed_interior_flag);
1375           ccgDM_to_MEdge(&medge[i++],
1376                          getFaceIndex(ss, f, S, y, x, edgeSize, gridSize),
1377                          getFaceIndex(ss, f, S, y + 1, x, edgeSize, gridSize),
1378                          ed_interior_flag);
1379         }
1380       }
1381     }
1382   }
1383
1384   totedge = ccgSubSurf_getNumEdges(ss);
1385   for (index = 0; index < totedge; index++) {
1386     CCGEdge *e = ccgdm->edgeMap[index].edge;
1387     short ed_flag = 0;
1388     int x;
1389     int edgeIdx = POINTER_AS_INT(ccgSubSurf_getEdgeEdgeHandle(e));
1390
1391     if (!ccgSubSurf_getEdgeNumFaces(e)) {
1392       ed_flag |= ME_LOOSEEDGE;
1393     }
1394
1395     if (edgeFlags) {
1396       if (edgeIdx != -1) {
1397         ed_flag |= ((edgeFlags[index] & (ME_SEAM | ME_SHARP)) | ME_EDGEDRAW | ME_EDGERENDER);
1398       }
1399     }
1400     else {
1401       ed_flag |= ME_EDGEDRAW | ME_EDGERENDER;
1402     }
1403
1404     for (x = 0; x < edgeSize - 1; x++) {
1405       ccgDM_to_MEdge(&medge[i++],
1406                      getEdgeIndex(ss, e, x, edgeSize),
1407                      getEdgeIndex(ss, e, x + 1, edgeSize),
1408                      ed_flag);
1409     }
1410   }
1411 }
1412
1413 static void ccgDM_copyFinalFaceArray(DerivedMesh *dm, MFace *mface)
1414 {
1415   CCGDerivedMesh *ccgdm = (CCGDerivedMesh *)dm;
1416   CCGSubSurf *ss = ccgdm->ss;
1417   int index;
1418   int totface;
1419   int gridSize = ccgSubSurf_getGridSize(ss);
1420   int edgeSize = ccgSubSurf_getEdgeSize(ss);
1421   int i = 0;
1422   DMFlagMat *faceFlags = ccgdm->faceFlags;
1423
1424   totface = dm->getNumTessFaces(dm);
1425   for (index = 0; index < totface; index++) {
1426     CCGFace *f = ccgdm->faceMap[index].face;
1427     int x, y, S, numVerts = ccgSubSurf_getFaceNumVerts(f);
1428     /* keep types in sync with MFace, avoid many conversions */
1429     char flag = (faceFlags) ? faceFlags[index].flag : ME_SMOOTH;
1430     short mat_nr = (faceFlags) ? faceFlags[index].mat_nr : 0;
1431
1432     for (S = 0; S < numVerts; S++) {
1433       for (y = 0; y < gridSize - 1; y++) {
1434         for (x = 0; x < gridSize - 1; x++) {
1435           MFace *mf = &mface[i];
1436           mf->v1 = getFaceIndex(ss, f, S, x + 0, y + 0, edgeSize, gridSize);
1437           mf->v2 = getFaceIndex(ss, f, S, x + 0, y + 1, edgeSize, gridSize);
1438           mf->v3 = getFaceIndex(ss, f, S, x + 1, y + 1, edgeSize, gridSize);
1439           mf->v4 = getFaceIndex(ss, f, S, x + 1, y + 0, edgeSize, gridSize);
1440           mf->mat_nr = mat_nr;
1441           mf->flag = flag;
1442           mf->edcode = 0;
1443
1444           i++;
1445         }
1446       }
1447     }
1448   }
1449 }
1450
1451 typedef struct CopyFinalLoopArrayData {
1452   CCGDerivedMesh *ccgdm;
1453   MLoop *mloop;
1454   int grid_size;
1455   int *grid_offset;
1456   int edge_size;
1457   size_t mloop_index;
1458 } CopyFinalLoopArrayData;
1459
1460 static void copyFinalLoopArray_task_cb(void *__restrict userdata,
1461                                        const int iter,
1462                                        const ParallelRangeTLS *__restrict UNUSED(tls))
1463 {
1464   CopyFinalLoopArrayData *data = userdata;
1465   CCGDerivedMesh *ccgdm = data->ccgdm;
1466   CCGSubSurf *ss = ccgdm->ss;
1467   const int grid_size = data->grid_size;
1468   const int edge_size = data->edge_size;
1469   CCGFace *f = ccgdm->faceMap[iter].face;
1470   const int num_verts = ccgSubSurf_getFaceNumVerts(f);
1471   const int grid_index = data->grid_offset[iter];
1472   const size_t loop_index = 4 * (size_t)grid_index * (grid_size - 1) * (grid_size - 1);
1473   MLoop *ml = &data->mloop[loop_index];
1474   for (int S = 0; S < num_verts; S++) {
1475     for (int y = 0; y < grid_size - 1; y++) {
1476       for (int x = 0; x < grid_size - 1; x++) {
1477
1478         uint v1 = getFaceIndex(ss, f, S, x + 0, y + 0, edge_size, grid_size);
1479         uint v2 = getFaceIndex(ss, f, S, x + 0, y + 1, edge_size, grid_size);
1480         uint v3 = getFaceIndex(ss, f, S, x + 1, y + 1, edge_size, grid_size);
1481         uint v4 = getFaceIndex(ss, f, S, x + 1, y + 0, edge_size, grid_size);
1482
1483         ml->v = v1;
1484         ml->e = POINTER_AS_UINT(BLI_edgehash_lookup(ccgdm->ehash, v1, v2));
1485         ml++;
1486
1487         ml->v = v2;
1488         ml->e = POINTER_AS_UINT(BLI_edgehash_lookup(ccgdm->ehash, v2, v3));
1489         ml++;
1490
1491         ml->v = v3;
1492         ml->e = POINTER_AS_UINT(BLI_edgehash_lookup(ccgdm->ehash, v3, v4));
1493         ml++;
1494
1495         ml->v = v4;
1496         ml->e = POINTER_AS_UINT(BLI_edgehash_lookup(ccgdm->ehash, v4, v1));
1497         ml++;
1498       }
1499     }
1500   }
1501 }
1502
1503 static void ccgDM_copyFinalLoopArray(DerivedMesh *dm, MLoop *mloop)
1504 {
1505   CCGDerivedMesh *ccgdm = (CCGDerivedMesh *)dm;
1506   CCGSubSurf *ss = ccgdm->ss;
1507
1508   if (!ccgdm->ehash) {
1509     BLI_mutex_lock(&ccgdm->loops_cache_lock);
1510     if (!ccgdm->ehash) {
1511       MEdge *medge;
1512       EdgeHash *ehash;
1513
1514       ehash = BLI_edgehash_new_ex(__func__, ccgdm->dm.numEdgeData);
1515       medge = ccgdm->dm.getEdgeArray((DerivedMesh *)ccgdm);
1516
1517       for (int i = 0; i < ccgdm->dm.numEdgeData; i++) {
1518         BLI_edgehash_insert(ehash, medge[i].v1, medge[i].v2, POINTER_FROM_INT(i));
1519       }
1520
1521       atomic_cas_ptr((void **)&ccgdm->ehash, ccgdm->ehash, ehash);
1522     }
1523     BLI_mutex_unlock(&ccgdm->loops_cache_lock);
1524   }
1525
1526   CopyFinalLoopArrayData data;
1527   data.ccgdm = ccgdm;
1528   data.mloop = mloop;
1529   data.grid_size = ccgSubSurf_getGridSize(ss);
1530   data.grid_offset = dm->getGridOffset(dm);
1531   data.edge_size = ccgSubSurf_getEdgeSize(ss);
1532
1533   /* NOTE: For a dense subdivision we've got enough work for each face and
1534    * hence can dedicate whole thread to single face. For less dense
1535    * subdivision we handle multiple faces per thread.
1536    */
1537   data.mloop_index = data.grid_size >= 5 ? 1 : 8;
1538
1539   ParallelRangeSettings settings;
1540   BLI_parallel_range_settings_defaults(&settings);
1541   settings.min_iter_per_thread = 1;
1542
1543   BLI_task_parallel_range(
1544       0, ccgSubSurf_getNumFaces(ss), &data, copyFinalLoopArray_task_cb, &settings);
1545 }
1546
1547 static void ccgDM_copyFinalPolyArray(DerivedMesh *dm, MPoly *mpoly)
1548 {
1549   CCGDerivedMesh *ccgdm = (CCGDerivedMesh *)dm;
1550   CCGSubSurf *ss = ccgdm->ss;
1551   int index;
1552   int totface;
1553   int gridSize = ccgSubSurf_getGridSize(ss);
1554   /* int edgeSize = ccgSubSurf_getEdgeSize(ss); */ /* UNUSED */
1555   int i = 0, k = 0;
1556   DMFlagMat *faceFlags = ccgdm->faceFlags;
1557
1558   totface = ccgSubSurf_getNumFaces(ss);
1559   for (index = 0; index < totface; index++) {
1560     CCGFace *f = ccgdm->faceMap[index].face;
1561     int x, y, S, numVerts = ccgSubSurf_getFaceNumVerts(f);
1562     int flag = (faceFlags) ? faceFlags[index].flag : ME_SMOOTH;
1563     int mat_nr = (faceFlags) ? faceFlags[index].mat_nr : 0;
1564
1565     for (S = 0; S < numVerts; S++) {
1566       for (y = 0; y < gridSize - 1; y++) {
1567         for (x = 0; x < gridSize - 1; x++) {
1568           MPoly *mp = &mpoly[i];
1569
1570           mp->mat_nr = mat_nr;
1571           mp->flag = flag;
1572           mp->loopstart = k;
1573           mp->totloop = 4;
1574
1575           k += 4;
1576           i++;
1577         }
1578       }
1579     }
1580   }
1581 }
1582
1583 static void ccgdm_getVertCos(DerivedMesh *dm, float (*cos)[3])
1584 {
1585   CCGDerivedMesh *ccgdm = (CCGDerivedMesh *)dm;
1586   CCGSubSurf *ss = ccgdm->ss;
1587   int edgeSize = ccgSubSurf_getEdgeSize(ss);
1588   int gridSize = ccgSubSurf_getGridSize(ss);
1589   int i;
1590   CCGVertIterator vi;
1591   CCGEdgeIterator ei;
1592   CCGFaceIterator fi;
1593   CCGFace **faceMap2;
1594   CCGEdge **edgeMap2;
1595   CCGVert **vertMap2;
1596   int index, totvert, totedge, totface;
1597
1598   totvert = ccgSubSurf_getNumVerts(ss);
1599   vertMap2 = MEM_mallocN(totvert * sizeof(*vertMap2), "vertmap");
1600   for (ccgSubSurf_initVertIterator(ss, &vi); !ccgVertIterator_isStopped(&vi);
1601        ccgVertIterator_next(&vi)) {
1602     CCGVert *v = ccgVertIterator_getCurrent(&vi);
1603
1604     vertMap2[POINTER_AS_INT(ccgSubSurf_getVertVertHandle(v))] = v;
1605   }
1606
1607   totedge = ccgSubSurf_getNumEdges(ss);
1608   edgeMap2 = MEM_mallocN(totedge * sizeof(*edgeMap2), "edgemap");
1609   for (ccgSubSurf_initEdgeIterator(ss, &ei), i = 0; !ccgEdgeIterator_isStopped(&ei);
1610        i++, ccgEdgeIterator_next(&ei)) {
1611     CCGEdge *e = ccgEdgeIterator_getCurrent(&ei);
1612
1613     edgeMap2[POINTER_AS_INT(ccgSubSurf_getEdgeEdgeHandle(e))] = e;
1614   }
1615
1616   totface = ccgSubSurf_getNumFaces(ss);
1617   faceMap2 = MEM_mallocN(totface * sizeof(*faceMap2), "facemap");
1618   for (ccgSubSurf_initFaceIterator(ss, &fi); !ccgFaceIterator_isStopped(&fi);
1619        ccgFaceIterator_next(&fi)) {
1620     CCGFace *f = ccgFaceIterator_getCurrent(&fi);
1621
1622     faceMap2[POINTER_AS_INT(ccgSubSurf_getFaceFaceHandle(f))] = f;
1623   }
1624
1625   i = 0;
1626   for (index = 0; index < totface; index++) {
1627     CCGFace *f = faceMap2[index];
1628     int x, y, S, numVerts = ccgSubSurf_getFaceNumVerts(f);
1629
1630     copy_v3_v3(cos[i++], ccgSubSurf_getFaceCenterData(f));
1631
1632     for (S = 0; S < numVerts; S++) {
1633       for (x = 1; x < gridSize - 1; x++) {
1634         copy_v3_v3(cos[i++], ccgSubSurf_getFaceGridEdgeData(ss, f, S, x));
1635       }
1636     }
1637
1638     for (S = 0; S < numVerts; S++) {
1639       for (y = 1; y < gridSize - 1; y++) {
1640         for (x = 1; x < gridSize - 1; x++) {
1641           copy_v3_v3(cos[i++], ccgSubSurf_getFaceGridData(ss, f, S, x, y));
1642         }
1643       }
1644     }
1645   }
1646
1647   for (index = 0; index < totedge; index++) {
1648     CCGEdge *e = edgeMap2[index];
1649     int x;
1650
1651     for (x = 1; x < edgeSize - 1; x++) {
1652       copy_v3_v3(cos[i++], ccgSubSurf_getEdgeData(ss, e, x));
1653     }
1654   }
1655
1656   for (index = 0; index < totvert; index++) {
1657     CCGVert *v = vertMap2[index];
1658     copy_v3_v3(cos[i++], ccgSubSurf_getVertData(ss, v));
1659   }
1660
1661   MEM_freeN(vertMap2);
1662   MEM_freeN(edgeMap2);
1663   MEM_freeN(faceMap2);
1664 }
1665
1666 static void ccgDM_foreachMappedVert(DerivedMesh *dm,
1667                                     void (*func)(void *userData,
1668                                                  int index,
1669                                                  const float co[3],
1670                                                  const float no_f[3],
1671                                                  const short no_s[3]),
1672                                     void *userData,
1673                                     DMForeachFlag flag)
1674 {
1675   CCGDerivedMesh *ccgdm = (CCGDerivedMesh *)dm;
1676   CCGVertIterator vi;
1677   CCGKey key;
1678   CCG_key_top_level(&key, ccgdm->ss);
1679
1680   for (ccgSubSurf_initVertIterator(ccgdm->ss, &vi); !ccgVertIterator_isStopped(&vi);
1681        ccgVertIterator_next(&vi)) {
1682     CCGVert *v = ccgVertIterator_getCurrent(&vi);
1683     const int index = ccgDM_getVertMapIndex(ccgdm->ss, v);
1684
1685     if (index != -1) {
1686       CCGElem *vd = ccgSubSurf_getVertData(ccgdm->ss, v);
1687       const float *no = (flag & DM_FOREACH_USE_NORMAL) ? CCG_elem_no(&key, vd) : NULL;
1688       func(userData, index, CCG_elem_co(&key, vd), no, NULL);
1689     }
1690   }
1691 }
1692
1693 static void ccgDM_foreachMappedEdge(
1694     DerivedMesh *dm,
1695     void (*func)(void *userData, int index, const float v0co[3], const float v1co[3]),
1696     void *userData)
1697 {
1698   CCGDerivedMesh *ccgdm = (CCGDerivedMesh *)dm;
1699   CCGSubSurf *ss = ccgdm->ss;
1700   CCGEdgeIterator ei;
1701   CCGKey key;
1702   int i, edgeSize = ccgSubSurf_getEdgeSize(ss);
1703
1704   CCG_key_top_level(&key, ss);
1705
1706   for (ccgSubSurf_initEdgeIterator(ss, &ei); !ccgEdgeIterator_isStopped(&ei);
1707        ccgEdgeIterator_next(&ei)) {
1708     CCGEdge *e = ccgEdgeIterator_getCurrent(&ei);
1709     const int index = ccgDM_getEdgeMapIndex(ss, e);
1710
1711     if (index != -1) {
1712       CCGElem *edgeData = ccgSubSurf_getEdgeDataArray(ss, e);
1713       for (i = 0; i < edgeSize - 1; i++) {
1714         func(userData,
1715              index,
1716              CCG_elem_offset_co(&key, edgeData, i),
1717              CCG_elem_offset_co(&key, edgeData, i + 1));
1718       }
1719     }
1720   }
1721 }
1722
1723 static void ccgDM_foreachMappedLoop(DerivedMesh *dm,
1724                                     void (*func)(void *userData,
1725                                                  int vertex_index,
1726                                                  int face_index,
1727                                                  const float co[3],
1728                                                  const float no[3]),
1729                                     void *userData,
1730                                     DMForeachFlag flag)
1731 {
1732   /* We can't use dm->getLoopDataLayout(dm) here, we want to always access dm->loopData, EditDerivedBMesh would
1733    * return loop data from bmesh itself. */
1734   const float(*lnors)[3] = (flag & DM_FOREACH_USE_NORMAL) ? DM_get_loop_data_layer(dm, CD_NORMAL) :
1735                                                             NULL;
1736
1737   MVert *mv = dm->getVertArray(dm);
1738   MLoop *ml = dm->getLoopArray(dm);
1739   MPoly *mp = dm->getPolyArray(dm);
1740   const int *v_index = dm->getVertDataArray(dm, CD_ORIGINDEX);
1741   const int *f_index = dm->getPolyDataArray(dm, CD_ORIGINDEX);
1742   int p_idx, i;
1743
1744   for (p_idx = 0; p_idx < dm->numPolyData; ++p_idx, ++mp) {
1745     for (i = 0; i < mp->totloop; ++i, ++ml) {
1746       const int v_idx = v_index ? v_index[ml->v] : ml->v;
1747       const int f_idx = f_index ? f_index[p_idx] : p_idx;
1748       const float *no = lnors ? *lnors++ : NULL;
1749       if (!ELEM(ORIGINDEX_NONE, v_idx, f_idx)) {
1750         func(userData, v_idx, f_idx, mv[ml->v].co, no);
1751       }
1752     }
1753   }
1754 }
1755
1756 static void UNUSED_FUNCTION(ccgdm_pbvh_update)(CCGDerivedMesh *ccgdm)
1757 {
1758   if (ccgdm->pbvh && ccgDM_use_grid_pbvh(ccgdm)) {
1759     CCGFace **faces;
1760     int totface;
1761
1762     BKE_pbvh_get_grid_updates(ccgdm->pbvh, 1, (void ***)&faces, &totface);
1763     if (totface) {
1764       ccgSubSurf_updateFromFaces(ccgdm->ss, 0, faces, totface);
1765       ccgSubSurf_updateNormals(ccgdm->ss, faces, totface);
1766       MEM_freeN(faces);
1767     }
1768   }
1769 }
1770
1771 static void ccgDM_foreachMappedFaceCenter(
1772     DerivedMesh *dm,
1773     void (*func)(void *userData, int index, const float co[3], const float no[3]),
1774     void *userData,
1775     DMForeachFlag flag)
1776 {
1777   CCGDerivedMesh *ccgdm = (CCGDerivedMesh *)dm;
1778   CCGSubSurf *ss = ccgdm->ss;
1779   CCGKey key;
1780   CCGFaceIterator fi;
1781
1782   CCG_key_top_level(&key, ss);
1783
1784   for (ccgSubSurf_initFaceIterator(ss, &fi); !ccgFaceIterator_isStopped(&fi);
1785        ccgFaceIterator_next(&fi)) {
1786     CCGFace *f = ccgFaceIterator_getCurrent(&fi);
1787     const int index = ccgDM_getFaceMapIndex(ss, f);
1788
1789     if (index != -1) {
1790       /* Face center data normal isn't updated atm. */
1791       CCGElem *vd = ccgSubSurf_getFaceGridData(ss, f, 0, 0, 0);
1792       const float *no = (flag & DM_FOREACH_USE_NORMAL) ? CCG_elem_no(&key, vd) : NULL;
1793       func(userData, index, CCG_elem_co(&key, vd), no);
1794     }
1795   }
1796 }
1797
1798 static void ccgDM_release(DerivedMesh *dm)
1799 {
1800   CCGDerivedMesh *ccgdm = (CCGDerivedMesh *)dm;
1801
1802   if (DM_release(dm)) {
1803     /* Before freeing, need to update the displacement map */
1804     if (ccgdm->multires.modified_flags) {
1805       /* Check that mmd still exists */
1806       if (!ccgdm->multires.local_mmd &&
1807           BLI_findindex(&ccgdm->multires.ob->modifiers, ccgdm->multires.mmd) < 0) {
1808         ccgdm->multires.mmd = NULL;
1809       }
1810
1811       if (ccgdm->multires.mmd) {
1812         if (ccgdm->multires.modified_flags & MULTIRES_COORDS_MODIFIED) {
1813           multires_modifier_update_mdisps(dm, NULL);
1814         }
1815         if (ccgdm->multires.modified_flags & MULTIRES_HIDDEN_MODIFIED) {
1816           multires_modifier_update_hidden(dm);
1817         }
1818       }
1819     }
1820
1821     if (ccgdm->ehash) {
1822       BLI_edgehash_free(ccgdm->ehash, NULL);
1823     }
1824
1825     if (ccgdm->reverseFaceMap) {
1826       MEM_freeN(ccgdm->reverseFaceMap);
1827     }
1828     if (ccgdm->gridFaces) {
1829       MEM_freeN(ccgdm->gridFaces);
1830     }
1831     if (ccgdm->gridData) {
1832       MEM_freeN(ccgdm->gridData);
1833     }
1834     if (ccgdm->gridOffset) {
1835       MEM_freeN(ccgdm->gridOffset);
1836     }
1837     if (ccgdm->gridFlagMats) {
1838       MEM_freeN(ccgdm->gridFlagMats);
1839     }
1840     if (ccgdm->gridHidden) {
1841       /* Using dm->getNumGrids(dm) accesses freed memory */
1842       uint numGrids = ccgdm->numGrid;
1843       for (uint i = 0; i < numGrids; i++) {
1844         if (ccgdm->gridHidden[i]) {
1845           MEM_freeN(ccgdm->gridHidden[i]);
1846         }
1847       }
1848       MEM_freeN(ccgdm->gridHidden);
1849     }
1850     if (ccgdm->freeSS) {
1851       ccgSubSurf_free(ccgdm->ss);
1852     }
1853     if (ccgdm->pmap) {
1854       MEM_freeN(ccgdm->pmap);
1855     }
1856     if (ccgdm->pmap_mem) {
1857       MEM_freeN(ccgdm->pmap_mem);
1858     }
1859     MEM_freeN(ccgdm->edgeFlags);
1860     MEM_freeN(ccgdm->faceFlags);
1861     if (ccgdm->useGpuBackend == false) {
1862       MEM_freeN(ccgdm->vertMap);
1863       MEM_freeN(ccgdm->edgeMap);
1864       MEM_freeN(ccgdm->faceMap);
1865     }
1866
1867     BLI_mutex_end(&ccgdm->loops_cache_lock);
1868     BLI_rw_mutex_end(&ccgdm->origindex_cache_rwlock);
1869
1870     MEM_freeN(ccgdm);
1871   }
1872 }
1873
1874 static void *ccgDM_get_vert_data_layer(DerivedMesh *dm, int type)
1875 {
1876   if (type == CD_ORIGINDEX) {
1877     /* create origindex on demand to save memory */
1878     CCGDerivedMesh *ccgdm = (CCGDerivedMesh *)dm;
1879     CCGSubSurf *ss = ccgdm->ss;
1880     int *origindex;
1881     int a, index, totnone, totorig;
1882
1883     /* Avoid re-creation if the layer exists already */
1884     BLI_rw_mutex_lock(&ccgdm->origindex_cache_rwlock, THREAD_LOCK_READ);
1885     origindex = DM_get_vert_data_layer(dm, CD_ORIGINDEX);
1886     BLI_rw_mutex_unlock(&ccgdm->origindex_cache_rwlock);
1887     if (origindex) {
1888       return origindex;
1889     }
1890
1891     BLI_rw_mutex_lock(&ccgdm->origindex_cache_rwlock, THREAD_LOCK_WRITE);
1892     DM_add_vert_layer(dm, CD_ORIGINDEX, CD_CALLOC, NULL);
1893     origindex = DM_get_vert_data_layer(dm, CD_ORIGINDEX);
1894
1895     totorig = ccgSubSurf_getNumVerts(ss);
1896     totnone = dm->numVertData - totorig;
1897
1898     /* original vertices are at the end */
1899     for (a = 0; a < totnone; a++) {
1900       origindex[a] = ORIGINDEX_NONE;
1901     }
1902
1903     for (index = 0; index < totorig; index++, a++) {
1904       CCGVert *v = ccgdm->vertMap[index].vert;
1905       origindex[a] = ccgDM_getVertMapIndex(ccgdm->ss, v);
1906     }
1907     BLI_rw_mutex_unlock(&ccgdm->origindex_cache_rwlock);
1908
1909     return origindex;
1910   }
1911
1912   return DM_get_vert_data_layer(dm, type);
1913 }
1914
1915 static void *ccgDM_get_edge_data_layer(DerivedMesh *dm, int type)
1916 {
1917   if (type == CD_ORIGINDEX) {
1918     /* create origindex on demand to save memory */
1919     CCGDerivedMesh *ccgdm = (CCGDerivedMesh *)dm;
1920     CCGSubSurf *ss = ccgdm->ss;
1921     int *origindex;
1922     int a, i, index, totnone, totorig, totedge;
1923     int edgeSize = ccgSubSurf_getEdgeSize(ss);
1924
1925     /* Avoid re-creation if the layer exists already */
1926     origindex = DM_get_edge_data_layer(dm, CD_ORIGINDEX);
1927     if (origindex) {
1928       return origindex;
1929     }
1930
1931     DM_add_edge_layer(dm, CD_ORIGINDEX, CD_CALLOC, NULL);
1932     origindex = DM_get_edge_data_layer(dm, CD_ORIGINDEX);
1933
1934     totedge = ccgSubSurf_getNumEdges(ss);
1935     totorig = totedge * (edgeSize - 1);
1936     totnone = dm->numEdgeData - totorig;
1937
1938     /* original edges are at the end */
1939     for (a = 0; a < totnone; a++) {
1940       origindex[a] = ORIGINDEX_NONE;
1941     }
1942
1943     for (index = 0; index < totedge; index++) {
1944       CCGEdge *e = ccgdm->edgeMap[index].edge;
1945       int mapIndex = ccgDM_getEdgeMapIndex(ss, e);
1946
1947       for (i = 0; i < edgeSize - 1; i++, a++) {
1948         origindex[a] = mapIndex;
1949       }
1950     }
1951
1952     return origindex;
1953   }
1954
1955   return DM_get_edge_data_layer(dm, type);
1956 }
1957
1958 static void *ccgDM_get_tessface_data_layer(DerivedMesh *dm, int type)
1959 {
1960   if (type == CD_ORIGINDEX) {
1961     /* create origindex on demand to save memory */
1962     int *origindex;
1963
1964     /* Avoid re-creation if the layer exists already */
1965     origindex = DM_get_tessface_data_layer(dm, CD_ORIGINDEX);
1966     if (origindex) {
1967       return origindex;
1968     }
1969
1970     DM_add_tessface_layer(dm, CD_ORIGINDEX, CD_CALLOC, NULL);
1971     origindex = DM_get_tessface_data_layer(dm, CD_ORIGINDEX);
1972
1973     /* silly loop counting up */
1974     range_vn_i(origindex, dm->getNumTessFaces(dm), 0);
1975
1976     return origindex;
1977   }
1978
1979   if (type == CD_TESSLOOPNORMAL) {
1980     /* Create tessloopnormal on demand to save memory. */
1981     /* Note that since tessellated face corners are the same a loops in CCGDM, and since all faces have four
1982      * loops/corners, we can simplify the code here by converting tessloopnormals from 'short (*)[4][3]'
1983      * to 'short (*)[3]'.
1984      */
1985     short(*tlnors)[3];
1986
1987     /* Avoid re-creation if the layer exists already */
1988     tlnors = DM_get_tessface_data_layer(dm, CD_TESSLOOPNORMAL);
1989     if (!tlnors) {
1990       float(*lnors)[3];
1991       short(*tlnors_it)[3];
1992       const int numLoops = ccgDM_getNumLoops(dm);
1993       int i;
1994
1995       lnors = dm->getLoopDataArray(dm, CD_NORMAL);
1996       if (!lnors) {
1997         return NULL;
1998       }
1999
2000       DM_add_tessface_layer(dm, CD_TESSLOOPNORMAL, CD_CALLOC, NULL);
2001       tlnors = tlnors_it = (short(*)[3])DM_get_tessface_data_layer(dm, CD_TESSLOOPNORMAL);
2002
2003       /* With ccgdm, we have a simple one to one mapping between loops and tessellated face corners. */
2004       for (i = 0; i < numLoops; ++i, ++tlnors_it, ++lnors) {
2005         normal_float_to_short_v3(*tlnors_it, *lnors);
2006       }
2007     }
2008
2009     return tlnors;
2010   }
2011
2012   return DM_get_tessface_data_layer(dm, type);
2013 }
2014
2015 static void *ccgDM_get_poly_data_layer(DerivedMesh *dm, int type)
2016 {
2017   if (type == CD_ORIGINDEX) {
2018     /* create origindex on demand to save memory */
2019     CCGDerivedMesh *ccgdm = (CCGDerivedMesh *)dm;
2020     CCGSubSurf *ss = ccgdm->ss;
2021     int *origindex;
2022     int a, i, index, totface;
2023     int gridFaces = ccgSubSurf_getGridSize(ss) - 1;
2024
2025     /* Avoid re-creation if the layer exists already */
2026     origindex = DM_get_poly_data_layer(dm, CD_ORIGINDEX);
2027     if (origindex) {
2028       return origindex;
2029     }
2030
2031     DM_add_poly_layer(dm, CD_ORIGINDEX, CD_CALLOC, NULL);
2032     origindex = DM_get_poly_data_layer(dm, CD_ORIGINDEX);
2033
2034     totface = ccgSubSurf_getNumFaces(ss);
2035
2036     for (a = 0, index = 0; index < totface; index++) {
2037       CCGFace *f = ccgdm->faceMap[index].face;
2038       int numVerts = ccgSubSurf_getFaceNumVerts(f);
2039       int mapIndex = ccgDM_getFaceMapIndex(ss, f);
2040
2041       for (i = 0; i < gridFaces * gridFaces * numVerts; i++, a++) {
2042         origindex[a] = mapIndex;
2043       }
2044     }
2045
2046     return origindex;
2047   }
2048
2049   return DM_get_poly_data_layer(dm, type);
2050 }
2051
2052 static void *ccgDM_get_vert_data(DerivedMesh *dm, int index, int type)
2053 {
2054   if (type == CD_ORIGINDEX) {
2055     /* ensure creation of CD_ORIGINDEX layer */
2056     ccgDM_get_vert_data_layer(dm, type);
2057   }
2058
2059   return DM_get_vert_data(dm, index, type);
2060 }
2061
2062 static void *ccgDM_get_edge_data(DerivedMesh *dm, int index, int type)
2063 {
2064   if (type == CD_ORIGINDEX) {
2065     /* ensure creation of CD_ORIGINDEX layer */
2066     ccgDM_get_edge_data_layer(dm, type);
2067   }
2068
2069   return DM_get_edge_data(dm, index, type);
2070 }
2071
2072 static void *ccgDM_get_tessface_data(DerivedMesh *dm, int index, int type)
2073 {
2074   if (ELEM(type, CD_ORIGINDEX, CD_TESSLOOPNORMAL)) {
2075     /* ensure creation of CD_ORIGINDEX/CD_TESSLOOPNORMAL layers */
2076     ccgDM_get_tessface_data_layer(dm, type);
2077   }
2078
2079   return DM_get_tessface_data(dm, index, type);
2080 }
2081
2082 static void *ccgDM_get_poly_data(DerivedMesh *dm, int index, int type)
2083 {
2084   if (type == CD_ORIGINDEX) {
2085     /* ensure creation of CD_ORIGINDEX layer */
2086     ccgDM_get_tessface_data_layer(dm, type);
2087   }
2088
2089   return DM_get_poly_data(dm, index, type);
2090 }
2091
2092 static int ccgDM_getNumGrids(DerivedMesh *dm)
2093 {
2094   CCGDerivedMesh *ccgdm = (CCGDerivedMesh *)dm;
2095   int index, numFaces, numGrids;
2096
2097   numFaces = ccgSubSurf_getNumFaces(ccgdm->ss);
2098   numGrids = 0;
2099
2100   for (index = 0; index < numFaces; index++) {
2101     CCGFace *f = ccgdm->faceMap[index].face;
2102     numGrids += ccgSubSurf_getFaceNumVerts(f);
2103   }
2104
2105   return numGrids;
2106 }
2107
2108 static int ccgDM_getGridSize(DerivedMesh *dm)
2109 {
2110   CCGDerivedMesh *ccgdm = (CCGDerivedMesh *)dm;
2111   return ccgSubSurf_getGridSize(ccgdm->ss);
2112 }
2113
2114 static void ccgdm_create_grids(DerivedMesh *dm)
2115 {
2116   CCGDerivedMesh *ccgdm = (CCGDerivedMesh *)dm;
2117   CCGSubSurf *ss = ccgdm->ss;
2118   CCGElem **gridData;
2119   DMFlagMat *gridFlagMats;
2120   CCGFace **gridFaces;
2121   int *gridOffset;
2122   int index, numFaces, numGrids, S, gIndex /*, gridSize*/;
2123
2124   if (ccgdm->gridData) {
2125     return;
2126   }
2127
2128   numGrids = ccgDM_getNumGrids(dm);
2129   numFaces = ccgSubSurf_getNumFaces(ss);
2130   /*gridSize = ccgDM_getGridSize(dm);*/ /*UNUSED*/
2131
2132   /* compute offset into grid array for each face */
2133   gridOffset = MEM_mallocN(sizeof(int) * numFaces, "ccgdm.gridOffset");
2134
2135   for (gIndex = 0, index = 0; index < numFaces; index++) {
2136     CCGFace *f = ccgdm->faceMap[index].face;
2137     int numVerts = ccgSubSurf_getFaceNumVerts(f);
2138
2139     gridOffset[index] = gIndex;
2140     gIndex += numVerts;
2141   }
2142
2143   /* compute grid data */
2144   gridData = MEM_mallocN(sizeof(CCGElem *) * numGrids, "ccgdm.gridData");
2145   gridFaces = MEM_mallocN(sizeof(CCGFace *) * numGrids, "ccgdm.gridFaces");
2146   gridFlagMats = MEM_mallocN(sizeof(DMFlagMat) * numGrids, "ccgdm.gridFlagMats");
2147
2148   ccgdm->gridHidden = MEM_callocN(sizeof(*ccgdm->gridHidden) * numGrids, "ccgdm.gridHidden");
2149
2150   for (gIndex = 0, index = 0; index < numFaces; index++) {
2151     CCGFace *f = ccgdm->faceMap[index].face;
2152     int numVerts = ccgSubSurf_getFaceNumVerts(f);
2153
2154     for (S = 0; S < numVerts; S++, gIndex++) {
2155       gridData[gIndex] = ccgSubSurf_getFaceGridDataArray(ss, f, S);
2156       gridFaces[gIndex] = f;
2157       gridFlagMats[gIndex] = ccgdm->faceFlags[index];
2158     }
2159   }
2160
2161   ccgdm->gridData = gridData;
2162   ccgdm->gridFaces = gridFaces;
2163   ccgdm->gridOffset = gridOffset;
2164   ccgdm->gridFlagMats = gridFlagMats;
2165   ccgdm->numGrid = numGrids;
2166 }
2167
2168 static CCGElem **ccgDM_getGridData(DerivedMesh *dm)
2169 {
2170   CCGDerivedMesh *ccgdm = (CCGDerivedMesh *)dm;
2171
2172   ccgdm_create_grids(dm);
2173   return ccgdm->gridData;
2174 }
2175
2176 static int *ccgDM_getGridOffset(DerivedMesh *dm)
2177 {
2178   CCGDerivedMesh *ccgdm = (CCGDerivedMesh *)dm;
2179
2180   ccgdm_create_grids(dm);
2181   return ccgdm->gridOffset;
2182 }
2183
2184 static void ccgDM_getGridKey(DerivedMesh *dm, CCGKey *key)
2185 {
2186   CCGDerivedMesh *ccgdm = (CCGDerivedMesh *)dm;
2187   CCG_key_top_level(key, ccgdm->ss);
2188 }
2189
2190 static DMFlagMat *ccgDM_getGridFlagMats(DerivedMesh *dm)
2191 {
2192   CCGDerivedMesh *ccgdm = (CCGDerivedMesh *)dm;
2193
2194   ccgdm_create_grids(dm);
2195   return ccgdm->gridFlagMats;
2196 }
2197
2198 static BLI_bitmap **ccgDM_getGridHidden(DerivedMesh *dm)
2199 {
2200   CCGDerivedMesh *ccgdm = (CCGDerivedMesh *)dm;
2201
2202   ccgdm_create_grids(dm);
2203   return ccgdm->gridHidden;
2204 }
2205
2206 static const MeshElemMap *ccgDM_getPolyMap(Object *ob, DerivedMesh *dm)
2207 {
2208   CCGDerivedMesh *ccgdm = (CCGDerivedMesh *)dm;
2209
2210   if (!ccgdm->multires.mmd && !ccgdm->pmap && ob->type == OB_MESH) {
2211     Mesh *me = ob->data;
2212
2213     BKE_mesh_vert_poly_map_create(&ccgdm->pmap,
2214                                   &ccgdm->pmap_mem,
2215                                   me->mpoly,
2216                                   me->mloop,
2217                                   me->totvert,
2218                                   me->totpoly,
2219                                   me->totloop);
2220   }
2221
2222   return ccgdm->pmap;
2223 }
2224
2225 static int ccgDM_use_grid_pbvh(CCGDerivedMesh *ccgdm)
2226 {
2227   MultiresModifierData *mmd = ccgdm->multires.mmd;
2228
2229   /* both of multires and subsurf modifiers are CCG, but
2230    * grids should only be used when sculpting on multires */
2231   if (!mmd) {
2232     return 0;
2233   }
2234
2235   return 1;
2236 }
2237
2238 static struct PBVH *ccgDM_getPBVH(Object *ob, DerivedMesh *dm)
2239 {
2240   CCGDerivedMesh *ccgdm = (CCGDerivedMesh *)dm;
2241   CCGKey key;
2242   int numGrids;
2243
2244   CCG_key_top_level(&key, ccgdm->ss);
2245
2246   if (!ob) {
2247     ccgdm->pbvh = NULL;
2248     return NULL;
2249   }
2250
2251   if (!ob->sculpt) {
2252     return NULL;
2253   }
2254
2255   bool grid_pbvh = ccgDM_use_grid_pbvh(ccgdm);
2256   if ((ob->mode & OB_MODE_SCULPT) == 0) {
2257     /* In vwpaint, we may use a grid_pbvh for multires/subsurf, under certain conditions.
2258      * More complex cases break 'history' trail back to original vertices, in that case we fall back to
2259      * deformed cage only (i.e. original deformed mesh). */
2260     VirtualModifierData virtualModifierData;
2261     ModifierData *md = modifiers_getVirtualModifierList(ob, &virtualModifierData);
2262
2263     grid_pbvh = true;
2264     bool has_one_ccg_modifier = false;
2265     for (; md; md = md->next) {
2266       /* We can only accept to use this ccgdm if:
2267        *   - it's the only active ccgdm in the stack.
2268        *   - there is no topology-modifying modifier in the stack.
2269        * Otherwise, there is no way to map back to original geometry from grid-generated PBVH.
2270        */
2271       const ModifierTypeInfo *mti = modifierType_getInfo(md->type);
2272
2273       if (!modifier_isEnabled(NULL, md, eModifierMode_Realtime)) {
2274         continue;
2275       }
2276       if (ELEM(mti->type, eModifierTypeType_OnlyDeform, eModifierTypeType_NonGeometrical)) {
2277         continue;
2278       }
2279
2280       if (ELEM(md->type, eModifierType_Subsurf, eModifierType_Multires)) {
2281         if (has_one_ccg_modifier) {
2282           /* We only allow a single active ccg modifier in the stack. */
2283           grid_pbvh = false;
2284           break;
2285         }
2286         has_one_ccg_modifier = true;
2287         continue;
2288       }
2289
2290       /* Any other non-deforming modifier makes it impossible to use grid pbvh. */
2291       grid_pbvh = false;
2292       break;
2293     }
2294   }
2295
2296   if (ob->sculpt->pbvh) {
2297     /* Note that we have to clean up exisitng pbvh instead of updating it in case it does not match current
2298      * grid_pbvh status. */
2299     const PBVHType pbvh_type = BKE_pbvh_type(ob->sculpt->pbvh);
2300     if (grid_pbvh) {
2301       if (pbvh_type == PBVH_GRIDS) {
2302         /* pbvh's grids, gridadj and gridfaces points to data inside ccgdm
2303          * but this can be freed on ccgdm release, this updates the pointers
2304          * when the ccgdm gets remade, the assumption is that the topology
2305          * does not change. */
2306         ccgdm_create_grids(dm);
2307         BKE_pbvh_grids_update(ob->sculpt->pbvh,
2308                               ccgdm->gridData,
2309                               (void **)ccgdm->gridFaces,
2310                               ccgdm->gridFlagMats,
2311                               ccgdm->gridHidden);
2312       }
2313       else {
2314         BKE_pbvh_free(ob->sculpt->pbvh);
2315         ob->sculpt->pbvh = NULL;
2316       }
2317     }
2318     else if (pbvh_type == PBVH_GRIDS) {
2319       BKE_pbvh_free(ob->sculpt->pbvh);
2320       ob->sculpt->pbvh = NULL;
2321     }
2322
2323     ccgdm->pbvh = ob->sculpt->pbvh;
2324   }
2325
2326   if (ccgdm->pbvh) {
2327     return ccgdm->pbvh;
2328   }
2329
2330   /* No pbvh exists yet, we need to create one. only in case of multires
2331    * we build a pbvh over the modified mesh, in other cases the base mesh
2332    * is being sculpted, so we build a pbvh from that. */
2333   /* Note: vwpaint tries to always build a pbvh over the modified mesh. */
2334   if (grid_pbvh) {
2335     ccgdm_create_grids(dm);
2336
2337     numGrids = ccgDM_getNumGrids(dm);
2338
2339     ob->sculpt->pbvh = ccgdm->pbvh = BKE_pbvh_new();
2340     BKE_pbvh_build_grids(ccgdm->pbvh,
2341                          ccgdm->gridData,
2342                          numGrids,
2343                          &key,
2344                          (void **)ccgdm->gridFaces,
2345                          ccgdm->gridFlagMats,
2346                          ccgdm->gridHidden);
2347   }
2348   else if (ob->type == OB_MESH) {
2349     Mesh *me = BKE_object_get_original_mesh(ob);
2350     const int looptris_num = poly_to_tri_count(me->totpoly, me->totloop);
2351     MLoopTri *looptri;
2352
2353     looptri = MEM_mallocN(sizeof(*looptri) * looptris_num, __func__);
2354
2355     BKE_mesh_recalc_looptri(me->mloop, me->mpoly, me->mvert, me->totloop, me->totpoly, looptri);
2356
2357     ob->sculpt->pbvh = ccgdm->pbvh = BKE_pbvh_new();
2358     BKE_pbvh_build_mesh(ccgdm->pbvh,
2359                         me->mpoly,
2360                         me->mloop,
2361                         me->mvert,
2362                         me->totvert,
2363                         &me->vdata,
2364                         &me->ldata,
2365                         looptri,
2366                         looptris_num);
2367
2368     if (ob->sculpt->modifiers_active && ob->derivedDeform != NULL) {
2369       DerivedMesh *deformdm = ob->derivedDeform;
2370       float(*vertCos)[3];
2371       int totvert;
2372
2373       totvert = deformdm->getNumVerts(deformdm);
2374       vertCos = MEM_malloc_arrayN(totvert, sizeof(float[3]), "ccgDM_getPBVH vertCos");
2375       deformdm->getVertCos(deformdm, vertCos);
2376       BKE_pbvh_apply_vertCos(ccgdm->pbvh, vertCos, totvert);
2377       MEM_freeN(vertCos);
2378     }
2379   }
2380
2381   if (ccgdm->pbvh != NULL) {
2382     pbvh_show_diffuse_color_set(ccgdm->pbvh, ob->sculpt->show_diffuse_color);
2383     pbvh_show_mask_set(ccgdm->pbvh, ob->sculpt->show_mask);
2384   }
2385
2386   return ccgdm->pbvh;
2387 }
2388
2389 static void ccgDM_recalcTessellation(DerivedMesh *UNUSED(dm))
2390 {
2391   /* Nothing to do: CCG handles creating its own tessfaces */
2392 }
2393
2394 /* WARNING! *MUST* be called in an 'loops_cache_rwlock' protected thread context! */
2395 static void ccgDM_recalcLoopTri(DerivedMesh *dm)
2396 {
2397   MLoopTri *mlooptri = dm->looptris.array;
2398   const int tottri = dm->numPolyData * 2;
2399   int i, poly_index;
2400
2401   DM_ensure_looptri_data(dm);
2402   mlooptri = dm->looptris.array_wip;
2403
2404   BLI_assert(tottri == 0 || mlooptri != NULL);
2405   BLI_assert(poly_to_tri_count(dm->numPolyData, dm->numLoopData) == dm->looptris.num);
2406   BLI_assert(tottri == dm->looptris.num);
2407
2408   for (i = 0, poly_index = 0; i < tottri; i += 2, poly_index += 1) {
2409     MLoopTri *lt;
2410     lt = &mlooptri[i];
2411     /* quad is (0, 3, 2, 1) */
2412     lt->tri[0] = (poly_index * 4) + 0;
2413     lt->tri[1] = (poly_index * 4) + 2;
2414     lt->tri[2] = (poly_index * 4) + 3;
2415     lt->poly = poly_index;
2416
2417     lt = &mlooptri[i + 1];
2418     lt->tri[0] = (poly_index * 4) + 0;
2419     lt->tri[1] = (poly_index * 4) + 1;
2420     lt->tri[2] = (poly_index * 4) + 2;
2421     lt->poly = poly_index;
2422   }
2423
2424   BLI_assert(dm->looptris.array == NULL);
2425   atomic_cas_ptr((void **)&dm->looptris.array, dm->looptris.array, dm->looptris.array_wip);
2426   dm->looptris.array_wip = NULL;
2427 }
2428
2429 static void ccgDM_calcNormals(DerivedMesh *dm)
2430 {
2431   /* Nothing to do: CCG calculates normals during drawing */
2432   dm->dirty &= ~DM_DIRTY_NORMALS;
2433 }
2434
2435 static void set_default_ccgdm_callbacks(CCGDerivedMesh *ccgdm)
2436 {
2437   ccgdm->dm.getMinMax = ccgDM_getMinMax;
2438   ccgdm->dm.getNumVerts = ccgDM_getNumVerts;
2439   ccgdm->dm.getNumEdges = ccgDM_getNumEdges;
2440   ccgdm->dm.getNumLoops = ccgDM_getNumLoops;
2441   /* reuse of ccgDM_getNumTessFaces is intentional here: subsurf polys are just created from tessfaces */
2442   ccgdm->dm.getNumPolys = ccgDM_getNumPolys;
2443   ccgdm->dm.getNumTessFaces = ccgDM_getNumTessFaces;
2444
2445   ccgdm->dm.getVert = ccgDM_getFinalVert;
2446   ccgdm->dm.getEdge = ccgDM_getFinalEdge;
2447   ccgdm->dm.getTessFace = ccgDM_getFinalFace;
2448
2449   ccgdm->dm.getVertCo = ccgDM_getFinalVertCo;
2450   ccgdm->dm.getVertNo = ccgDM_getFinalVertNo;
2451
2452   ccgdm->dm.copyVertArray = ccgDM_copyFinalVertArray;
2453   ccgdm->dm.copyEdgeArray = ccgDM_copyFinalEdgeArray;
2454   ccgdm->dm.copyTessFaceArray = ccgDM_copyFinalFaceArray;
2455   ccgdm->dm.copyLoopArray = ccgDM_copyFinalLoopArray;
2456   ccgdm->dm.copyPolyArray = ccgDM_copyFinalPolyArray;
2457
2458   ccgdm->dm.getVertData = ccgDM_get_vert_data;
2459   ccgdm->dm.getEdgeData = ccgDM_get_edge_data;
2460   ccgdm->dm.getTessFaceData = ccgDM_get_tessface_data;
2461   ccgdm->dm.getPolyData = ccgDM_get_poly_data;
2462   ccgdm->dm.getVertDataArray = ccgDM_get_vert_data_layer;
2463   ccgdm->dm.getEdgeDataArray = ccgDM_get_edge_data_layer;
2464   ccgdm->dm.getTessFaceDataArray = ccgDM_get_tessface_data_layer;
2465   ccgdm->dm.getPolyDataArray = ccgDM_get_poly_data_layer;
2466   ccgdm->dm.getNumGrids = ccgDM_getNumGrids;
2467   ccgdm->dm.getGridSize = ccgDM_getGridSize;
2468   ccgdm->dm.getGridData = ccgDM_getGridData;
2469   ccgdm->dm.getGridOffset = ccgDM_getGridOffset;
2470   ccgdm->dm.getGridKey = ccgDM_getGridKey;
2471   ccgdm->dm.getGridFlagMats = ccgDM_getGridFlagMats;
2472   ccgdm->dm.getGridHidden = ccgDM_getGridHidden;
2473   ccgdm->dm.getPolyMap = ccgDM_getPolyMap;
2474   ccgdm->dm.getPBVH = ccgDM_getPBVH;
2475
2476   ccgdm->dm.calcNormals = ccgDM_calcNormals;
2477   ccgdm->dm.calcLoopNormals = CDDM_calc_loop_normals;
2478   ccgdm->dm.calcLoopNormalsSpaceArray = CDDM_calc_loop_normals_spacearr;
2479   ccgdm->dm.calcLoopTangents = DM_calc_loop_tangents;
2480   ccgdm->dm.recalcTessellation = ccgDM_recalcTessellation;
2481   ccgdm->dm.recalcLoopTri = ccgDM_recalcLoopTri;
2482
2483   ccgdm->dm.getVertCos = ccgdm_getVertCos;
2484   ccgdm->dm.foreachMappedVert = ccgDM_foreachMappedVert;
2485   ccgdm->dm.foreachMappedEdge = ccgDM_foreachMappedEdge;
2486   ccgdm->dm.foreachMappedLoop = ccgDM_foreachMappedLoop;
2487   ccgdm->dm.foreachMappedFaceCenter = ccgDM_foreachMappedFaceCenter;
2488
2489   ccgdm->dm.release = ccgDM_release;
2490 }
2491
2492 static void create_ccgdm_maps(CCGDerivedMesh *ccgdm, CCGSubSurf *ss)
2493 {
2494   CCGVertIterator vi;
2495   CCGEdgeIterator ei;
2496   CCGFaceIterator fi;
2497   int totvert, totedge, totface;
2498
2499   totvert = ccgSubSurf_getNumVerts(ss);
2500   ccgdm->vertMap = MEM_mallocN(totvert * sizeof(*ccgdm->vertMap), "vertMap");
2501   for (ccgSubSurf_initVertIterator(ss, &vi); !ccgVertIterator_isStopped(&vi);
2502        ccgVertIterator_next(&vi)) {
2503     CCGVert *v = ccgVertIterator_getCurrent(&vi);
2504
2505     ccgdm->vertMap[POINTER_AS_INT(ccgSubSurf_getVertVertHandle(v))].vert = v;
2506   }
2507
2508   totedge = ccgSubSurf_getNumEdges(ss);
2509   ccgdm->edgeMap = MEM_mallocN(totedge * sizeof(*ccgdm->edgeMap), "edgeMap");
2510   for (ccgSubSurf_initEdgeIterator(ss, &ei); !ccgEdgeIterator_isStopped(&ei);
2511        ccgEdgeIterator_next(&ei)) {
2512     CCGEdge *e = ccgEdgeIterator_getCurrent(&ei);
2513
2514     ccgdm->edgeMap[POINTER_AS_INT(ccgSubSurf_getEdgeEdgeHandle(e))].edge = e;
2515   }
2516
2517   totface = ccgSubSurf_getNumFaces(ss);
2518   ccgdm->faceMap = MEM_mallocN(totface * sizeof(*ccgdm->faceMap), "faceMap");
2519   for (ccgSubSurf_initFaceIterator(ss, &fi); !ccgFaceIterator_isStopped(&fi);
2520        ccgFaceIterator_next(&fi)) {
2521     CCGFace *f = ccgFaceIterator_getCurrent(&fi);
2522
2523     ccgdm->faceMap[POINTER_AS_INT(ccgSubSurf_getFaceFaceHandle(f))].face = f;
2524   }
2525 }
2526
2527 /* Fill in all geometry arrays making it possible to access any
2528  * hires data from the CPU.
2529  */
2530 static void set_ccgdm_all_geometry(CCGDerivedMesh *ccgdm,
2531                                    CCGSubSurf *ss,
2532                                    DerivedMesh *dm,
2533                                    bool useSubsurfUv)
2534 {
2535   const int totvert = ccgSubSurf_getNumVerts(ss);
2536   const int totedge = ccgSubSurf_getNumEdges(ss);
2537   const int totface = ccgSubSurf_getNumFaces(ss);
2538   int index;
2539   int i;
2540   int vertNum = 0, edgeNum = 0, faceNum = 0;
2541   int *vertOrigIndex, *faceOrigIndex, *polyOrigIndex, *base_polyOrigIndex, *edgeOrigIndex;
2542   short *edgeFlags = ccgdm->edgeFlags;
2543   DMFlagMat *faceFlags = ccgdm->faceFlags;
2544   int *polyidx = NULL;
2545 #ifndef USE_DYNSIZE
2546   int *loopidx = NULL, *vertidx = NULL;
2547   BLI_array_declare(loopidx);
2548   BLI_array_declare(vertidx);
2549 #endif
2550   int loopindex, loopindex2;
2551   int edgeSize;
2552   int gridSize;
2553   int gridFaces, gridCuts;
2554   int gridSideEdges;
2555   int gridInternalEdges;
2556   WeightTable wtable = {NULL};
2557   MEdge *medge = NULL;
2558   MPoly *mpoly = NULL;
2559   bool has_edge_cd;
2560
2561   edgeSize = ccgSubSurf_getEdgeSize(ss);
2562   gridSize = ccgSubSurf_getGridSize(ss);
2563   gridFaces = gridSize - 1;
2564   gridCuts = gridSize - 2;
2565   /*gridInternalVerts = gridSideVerts * gridSideVerts; - as yet, unused */
2566   gridSideEdges = gridSize - 1;
2567   gridInternalEdges = (gridSideEdges - 1) * gridSideEdges * 2;
2568
2569   /* mvert = dm->getVertArray(dm); */ /* UNUSED */
2570   medge = dm->getEdgeArray(dm);
2571   /* mface = dm->getTessFaceArray(dm); */ /* UNUSED */
2572
2573   mpoly = CustomData_get_layer(&dm->polyData, CD_MPOLY);
2574   base_polyOrigIndex = CustomData_get_layer(&dm->polyData, CD_ORIGINDEX);
2575
2576   vertOrigIndex = DM_get_vert_data_layer(&ccgdm->dm, CD_ORIGINDEX);
2577   edgeOrigIndex = DM_get_edge_data_layer(&ccgdm->dm, CD_ORIGINDEX);
2578
2579   faceOrigIndex = DM_get_tessface_data_layer(&ccgdm->dm, CD_ORIGINDEX);
2580   polyOrigIndex = DM_get_poly_data_layer(&ccgdm->dm, CD_ORIGINDEX);
2581
2582   has_edge_cd = ((ccgdm->dm.edgeData.totlayer - (edgeOrigIndex ? 1 : 0)) != 0);
2583
2584   loopindex = loopindex2 = 0; /* current loop index */
2585   for (index = 0; index < totface; index++) {
2586     CCGFace *f = ccgdm->faceMap[index].face;
2587     int numVerts = ccgSubSurf_getFaceNumVerts(f);
2588     int numFinalEdges = numVerts * (gridSideEdges + gridInternalEdges);
2589     int origIndex = POINTER_AS_INT(ccgSubSurf_getFaceFaceHandle(f));
2590     int g2_wid = gridCuts + 2;
2591     float *w, *w2;
2592     int s, x, y;
2593 #ifdef USE_DYNSIZE
2594     int loopidx[numVerts], vertidx[numVerts];
2595 #endif
2596     w = get_ss_weights(&wtable, gridCuts, numVerts);
2597
2598     ccgdm->faceMap[index].startVert = vertNum;
2599     ccgdm->faceMap[index].startEdge = edgeNum;
2600     ccgdm->faceMap[index].startFace = faceNum;
2601
2602     faceFlags->flag = mpoly ? mpoly[origIndex].flag : 0;
2603     faceFlags->mat_nr = mpoly ? mpoly[origIndex].mat_nr : 0;
2604     faceFlags++;
2605
2606     /* set the face base vert */
2607     *((int *)ccgSubSurf_getFaceUserData(ss, f)) = vertNum;
2608
2609 #ifndef USE_DYNSIZE
2610     BLI_array_clear(loopidx);
2611     BLI_array_grow_items(loopidx, numVerts);
2612 #endif
2613     for (s = 0; s < numVerts; s++) {
2614       loopidx[s] = loopindex++;
2615     }
2616
2617 #ifndef USE_DYNSIZE
2618     BLI_array_clear(vertidx);
2619     BLI_array_grow_items(vertidx, numVerts);
2620 #endif
2621     for (s = 0; s < numVerts; s++) {
2622       CCGVert *v = ccgSubSurf_getFaceVert(f, s);
2623       vertidx[s] = POINTER_AS_INT(ccgSubSurf_getVertVertHandle(v));
2624     }
2625
2626     /*I think this is for interpolating the center vert?*/
2627     w2 = w;  // + numVerts*(g2_wid-1) * (g2_wid-1); //numVerts*((g2_wid-1) * g2_wid+g2_wid-1);
2628     DM_interp_vert_data(dm, &ccgdm->dm, vertidx, w2, numVerts, vertNum);
2629     if (vertOrigIndex) {
2630       *vertOrigIndex = ORIGINDEX_NONE;
2631       vertOrigIndex++;
2632     }
2633
2634     vertNum++;
2635
2636     /*interpolate per-vert data*/
2637     for (s = 0; s < numVerts; s++) {
2638       for (x = 1; x < gridFaces; x++) {
2639         w2 = w + s * numVerts * g2_wid * g2_wid + x * numVerts;
2640         DM_interp_vert_data(dm, &ccgdm->dm, vertidx, w2, numVerts, vertNum);
2641
2642         if (vertOrigIndex) {
2643           *vertOrigIndex = ORIGINDEX_NONE;
2644           vertOrigIndex++;
2645         }
2646
2647         vertNum++;
2648       }
2649     }
2650
2651     /*interpolate per-vert data*/
2652     for (s = 0; s < numVerts; s++) {
2653       for (y = 1; y < gridFaces; y++) {
2654         for (x = 1; x < gridFaces; x++) {
2655           w2 = w + s * numVerts * g2_wid * g2_wid + (y * g2_wid + x) * numVerts;
2656           DM_interp_vert_data(dm, &ccgdm->dm, vertidx, w2, numVerts, vertNum);
2657
2658           if (vertOrigIndex) {
2659             *vertOrigIndex = ORIGINDEX_NONE;
2660             vertOrigIndex++;
2661           }
2662
2663           vertNum++;
2664         }
2665       }
2666     }
2667
2668     if (edgeOrigIndex) {
2669       for (i = 0; i < numFinalEdges; ++i) {
2670         edgeOrigIndex[edgeNum + i] = ORIGINDEX_NONE;
2671       }
2672     }
2673
2674     for (s = 0; s < numVerts; s++) {
2675       /*interpolate per-face data*/
2676       for (y = 0; y < gridFaces; y++) {
2677         for (x = 0; x < gridFaces; x++) {
2678           w2 = w + s * numVerts * g2_wid * g2_wid + (y * g2_wid + x) * numVerts;
2679           CustomData_interp(
2680               &dm->loopData, &ccgdm->dm.loopData, loopidx, w2, NULL, numVerts, loopindex2);
2681           loopindex2++;
2682
2683           w2 = w + s * numVerts * g2_wid * g2_wid + ((y + 1) * g2_wid + (x)) * numVerts;
2684           CustomData_interp(
2685               &dm->loopData, &ccgdm->dm.loopData, loopidx, w2, NULL, numVerts, loopindex2);
2686           loopindex2++;
2687
2688           w2 = w + s * numVerts * g2_wid * g2_wid + ((y + 1) * g2_wid + (x + 1)) * numVerts;
2689           CustomData_interp(
2690               &dm->loopData, &ccgdm->dm.loopData, loopidx, w2, NULL, numVerts, loopindex2);
2691           loopindex2++;
2692
2693           w2 = w + s * numVerts * g2_wid * g2_wid + ((y)*g2_wid + (x + 1)) * numVerts;
2694           CustomData_interp(
2695               &dm->loopData, &ccgdm->dm.loopData, loopidx, w2, NULL, numVerts, loopindex2);
2696           loopindex2++;
2697
2698           /*copy over poly data, e.g. mtexpoly*/
2699           CustomData_copy_data(&dm->polyData, &ccgdm->dm.polyData, origIndex, faceNum, 1);
2700
2701           /*set original index data*/
2702           if (faceOrigIndex) {
2703             /* reference the index in 'polyOrigIndex' */
2704             *faceOrigIndex = faceNum;
2705             faceOrigIndex++;
2706           }
2707           if (polyOrigIndex) {
2708             *polyOrigIndex = base_polyOrigIndex ? base_polyOrigIndex[origIndex] : origIndex;
2709             polyOrigIndex++;
2710           }
2711
2712           ccgdm->reverseFaceMap[faceNum] = index;
2713
2714           /* This is a simple one to one mapping, here... */
2715           if (polyidx) {
2716             polyidx[faceNum] = faceNum;
2717           }
2718
2719           faceNum++;
2720         }
2721       }
2722     }
2723
2724     edgeNum += numFinalEdges;
2725   }
2726
2727   for (index = 0; index < totedge; ++index) {
2728     CCGEdge *e = ccgdm->edgeMap[index].edge;
2729     int numFinalEdges = edgeSize - 1;
2730     int mapIndex = ccgDM_getEdgeMapIndex(ss, e);
2731     int x;
2732     int vertIdx[2];
2733     int edgeIdx = POINTER_AS_INT(ccgSubSurf_getEdgeEdgeHandle(e));
2734
2735     CCGVert *v;
2736     v = ccgSubSurf_getEdgeVert0(e);
2737     vertIdx[0] = POINTER_AS_INT(ccgSubSurf_getVertVertHandle(v));
2738     v = ccgSubSurf_getEdgeVert1(e);
2739     vertIdx[1] = POINTER_AS_INT(ccgSubSurf_getVertVertHandle(v));
2740
2741     ccgdm->edgeMap[index].startVert = vertNum;
2742     ccgdm->edgeMap[index].startEdge = edgeNum;
2743
2744     if (edgeIdx >= 0 && edgeFlags) {
2745       edgeFlags[edgeIdx] = medge[edgeIdx].flag;
2746     }
2747
2748     /* set the edge base vert */
2749     *((int *)ccgSubSurf_getEdgeUserData(ss, e)) = vertNum;
2750
2751     for (x = 1; x < edgeSize - 1; x++) {
2752       float w[2];
2753       w[1] = (float)x / (edgeSize - 1);
2754       w[0] = 1 - w[1];
2755       DM_interp_vert_data(dm, &ccgdm->dm, vertIdx, w, 2, vertNum);
2756       if (vertOrigIndex) {
2757         *vertOrigIndex = ORIGINDEX_NONE;
2758         vertOrigIndex++;
2759       }
2760       vertNum++;
2761     }
2762
2763     if (has_edge_cd) {
2764       BLI_assert(edgeIdx >= 0 && edgeIdx < dm->getNumEdges(dm));
2765       for (i = 0; i < numFinalEdges; ++i) {
2766         CustomData_copy_data(&dm->edgeData, &ccgdm->dm.edgeData, edgeIdx, edgeNum + i, 1);
2767       }
2768     }
2769
2770     if (edgeOrigIndex) {
2771       for (i = 0; i < numFinalEdges; ++i) {
2772         edgeOrigIndex[edgeNum + i] = mapIndex;
2773       }
2774     }
2775
2776     edgeNum += numFinalEdges;
2777   }
2778
2779   if (useSubsurfUv) {
2780     CustomData *ldata = &ccgdm->dm.loopData;
2781     CustomData *dmldata = &dm->loopData;
2782     int numlayer = CustomData_number_of_layers(ldata, CD_MLOOPUV);
2783     int dmnumlayer = CustomData_number_of_layers(dmldata, CD_MLOOPUV);
2784
2785     for (i = 0; i < numlayer && i < dmnumlayer; i++) {
2786       set_subsurf_uv(ss, dm, &ccgdm->dm, i);
2787     }
2788   }
2789
2790   for (index = 0; index < totvert; ++index) {
2791     CCGVert *v = ccgdm->vertMap[index].vert;
2792     int mapIndex = ccgDM_getVertMapIndex(ccgdm->ss, v);
2793     int vertIdx;
2794
2795     vertIdx = POINTER_AS_INT(ccgSubSurf_getVertVertHandle(v));
2796
2797     ccgdm->vertMap[index].startVert = vertNum;
2798
2799     /* set the vert base vert */
2800     *((int *)ccgSubSurf_getVertUserData(ss, v)) = vertNum;
2801
2802     DM_copy_vert_data(dm, &ccgdm->dm, vertIdx, vertNum, 1);
2803
2804     if (vertOrigIndex) {
2805       *vertOrigIndex = mapIndex;
2806       vertOrigIndex++;
2807     }
2808     vertNum++;
2809   }
2810
2811 #ifndef USE_DYNSIZE
2812   BLI_array_free(vertidx);
2813   BLI_array_free(loopidx);
2814 #endif
2815   free_ss_weights(&wtable);
2816
2817   BLI_assert(vertNum == ccgSubSurf_getNumFinalVerts(ss));
2818   BLI_assert(edgeNum == ccgSubSurf_getNumFinalEdges(ss));
2819   BLI_assert(loopindex2 == ccgSubSurf_getNumFinalFaces(ss) * 4);
2820   BLI_assert(faceNum == ccgSubSurf_getNumFinalFaces(ss));
2821 }
2822
2823 /* Fill in only geometry arrays needed for the GPU tessellation. */
2824 static void set_ccgdm_gpu_geometry(CCGDerivedMesh *ccgdm, DerivedMesh *dm)
2825 {
2826   const int totface = dm->getNumPolys(dm);
2827   MPoly *mpoly = CustomData_get_layer(&dm->polyData, CD_MPOLY);
2828   int index;
2829   DMFlagMat *faceFlags = ccgdm->faceFlags;
2830
2831   for (index = 0; index < totface; index++) {
2832     faceFlags->flag = mpoly ? mpoly[index].flag : 0;
2833     faceFlags->mat_nr = mpoly ? mpoly[index].mat_nr : 0;
2834     faceFlags++;
2835   }
2836
2837   /* TODO(sergey): Fill in edge flags. */
2838 }
2839
2840 static CCGDerivedMesh *getCCGDerivedMesh(
2841     CCGSubSurf *ss, int drawInteriorEdges, int useSubsurfUv, DerivedMesh *dm, bool use_gpu_backend)
2842 {
2843 #ifdef WITH_OPENSUBDIV
2844   const int totedge = dm->getNumEdges(dm);
2845   const int totface = dm->getNumPolys(dm);
2846 #else
2847   const int totedge = ccgSubSurf_getNumEdges(ss);
2848   const int totface = ccgSubSurf_getNumFaces(ss);
2849 #endif
2850   CCGDerivedMesh *ccgdm = MEM_callocN(sizeof(*ccgdm), "ccgdm");
2851
2852   if (use_gpu_backend == false) {
2853     BLI_assert(totedge == ccgSubSurf_getNumEdges(ss));
2854     BLI_assert(totface == ccgSubSurf_getNumFaces(ss));
2855     DM_from_template(&ccgdm->dm,
2856                      dm,
2857                      DM_TYPE_CCGDM,
2858                      ccgSubSurf_getNumFinalVerts(ss),
2859                      ccgSubSurf_getNumFinalEdges(ss),
2860                      0,
2861                      ccgSubSurf_getNumFinalFaces(ss) * 4,
2862                      ccgSubSurf_getNumFinalFaces(ss));
2863
2864     CustomData_free_layer_active(&ccgdm->dm.polyData, CD_NORMAL, ccgdm->dm.numPolyData);
2865
2866     ccgdm->reverseFaceMap = MEM_callocN(sizeof(int) * ccgSubSurf_getNumFinalFaces(ss),
2867                                         "reverseFaceMap");
2868
2869     create_ccgdm_maps(ccgdm, ss);
2870   }
2871   else {
2872     DM_from_template(&ccgdm->dm, dm, DM_TYPE_CCGDM, 0, 0, 0, 0, dm->getNumPolys(dm));
2873     CustomData_copy_data(&dm->polyData, &ccgdm->dm.polyData, 0, 0, dm->getNumPolys(dm));
2874   }
2875
2876   set_default_ccgdm_callbacks(ccgdm);
2877
2878   ccgdm->ss = ss;
2879   ccgdm->drawInteriorEdges = drawInteriorEdges;
2880   ccgdm->useSubsurfUv = useSubsurfUv;
2881   ccgdm->useGpuBackend = use_gpu_backend;
2882
2883   /* CDDM hack. */
2884   ccgdm->edgeFlags = MEM_callocN(sizeof(short) * totedge, "edgeFlags");
2885   ccgdm->faceFlags = MEM_callocN(sizeof(DMFlagMat) * totface, "faceFlags");
2886
2887   if (use_gpu_backend == false) {
2888     set_ccgdm_all_geometry(ccgdm, ss, dm, useSubsurfUv != 0);
2889   }
2890   else {
2891     set_ccgdm_gpu_geometry(ccgdm, dm);
2892   }
2893
2894   ccgdm->dm.numVertData = ccgSubSurf_getNumFinalVerts(ss);
2895   ccgdm->dm.numEdgeData = ccgSubSurf_getNumFinalEdges(ss);
2896   ccgdm->dm.numPolyData = ccgSubSurf_getNumFinalFaces(ss);
2897   ccgdm->dm.numLoopData = ccgdm->dm.numPolyData * 4;
2898   ccgdm->dm.numTessFaceData = 0;
2899
2900   BLI_mutex_init(&ccgdm->loops_cache_lock);
2901   BLI_rw_mutex_init(&ccgdm->origindex_cache_rwlock);
2902
2903   return ccgdm;
2904 }
2905
2906 /***/
2907
2908 static bool subsurf_use_gpu_backend(SubsurfFlags flags)
2909 {
2910 #ifdef WITH_OPENSUBDIV
2911   /* Use GPU backend if it's a last modifier in the stack
2912    * and user chose to use any of the OSD compute devices,
2913    * but also check if GPU has all needed features.
2914    */
2915   return (flags & SUBSURF_USE_GPU_BACKEND) != 0 &&
2916          (U.opensubdiv_compute_type != USER_OPENSUBDIV_COMPUTE_NONE);
2917 #else
2918   (void)flags;
2919   return false;
2920 #endif
2921 }
2922
2923 struct DerivedMesh *subsurf_make_derived_from_derived(struct DerivedMesh *dm,
2924                                                       struct SubsurfModifierData *smd,
2925                                                       struct Scene *scene,
2926                                                       float (*vertCos)[3],
2927                                                       SubsurfFlags flags)
2928 {
2929   const int useSimple = (smd->subdivType == ME_SIMPLE_SUBSURF) ? CCG_SIMPLE_SUBDIV : 0;
2930   const CCGFlags useAging = (smd->flags & eSubsurfModifierFlag_DebugIncr) ? CCG_USE_AGING : 0;
2931   const int useSubsurfUv = (smd->uv_smooth != SUBSURF_UV_SMOOTH_NONE);
2932   const int drawInteriorEdges = !(smd->flags & eSubsurfModifierFlag_ControlEdges);
2933   const bool use_gpu_backend = subsurf_use_gpu_backend(flags);
2934   const bool ignore_simplify = (flags & SUBSURF_IGNORE_SIMPLIFY);
2935   CCGDerivedMesh *result;
2936
2937   /* note: editmode calculation can only run once per
2938    * modifier stack evaluation (uses freed cache) [#36299] */
2939   if (flags & SUBSURF_FOR_EDIT_MODE) {
2940     int levels = (scene != NULL && !ignore_simplify) ?
2941                      get_render_subsurf_level(&scene->r, smd->levels, false) :
2942                      smd->levels;
2943
2944     /* TODO(sergey): Same as emCache below. */
2945     if ((flags & SUBSURF_IN_EDIT_MODE) && smd->mCache) {
2946       ccgSubSurf_free(smd->mCache);
2947       smd->mCache = NULL;
2948     }
2949
2950     smd->emCache = _getSubSurf(smd->emCache, levels, 3, useSimple | useAging | CCG_CALC_NORMALS);
2951
2952 #ifdef WITH_OPENSUBDIV
2953     ccgSubSurf_setSkipGrids(smd->emCache, use_gpu_backend);
2954 #endif
2955     ss_sync_from_derivedmesh(smd->emCache, dm, vertCos, useSimple, useSubsurfUv);
2956     result = getCCGDerivedMesh(smd->emCache, drawInteriorEdges, useSubsurfUv, dm, use_gpu_backend);
2957   }
2958   else if (flags & SUBSURF_USE_RENDER_PARAMS) {
2959     /* Do not use cache in render mode. */
2960     CCGSubSurf *ss;
2961     int levels = (scene != NULL && !ignore_simplify) ?
2962                      get_render_subsurf_level(&scene->r, smd->renderLevels, true) :
2963                      smd->renderLevels;
2964
2965     if (levels == 0) {
2966       return dm;
2967     }
2968
2969     ss = _getSubSurf(NULL, levels, 3, useSimple | CCG_USE_ARENA | CCG_CALC_NORMALS);
2970
2971     ss_sync_from_derivedmesh(ss, dm, vertCos, useSimple, useSubsurfUv);
2972
2973     result = getCCGDerivedMesh(ss, drawInteriorEdges, useSubsurfUv, dm, false);
2974
2975     result->freeSS = 1;
2976   }
2977   else {
2978     int useIncremental = (smd->flags & eSubsurfModifierFlag_Incremental);
2979     int levels = (scene != NULL && !ignore_simplify) ?
2980                      get_render_subsurf_level(&scene->r, smd->levels, false) :
2981                      smd->levels;
2982     CCGSubSurf *ss;
2983
2984     /* It is quite possible there is a much better place to do this. It
2985      * depends a bit on how rigorously we expect this function to never
2986      * be called in editmode. In semi-theory we could share a single
2987      * cache, but the handles used inside and outside editmode are not
2988      * the same so we would need some way of converting them. Its probably
2989      * not worth the effort. But then why am I even writing this long
2990      * comment that no one will read? Hmmm. - zr
2991      *
2992      * Addendum: we can't really ensure that this is never called in edit
2993      * mode, so now we have a parameter to verify it. - brecht
2994      */
2995     if (!(flags & SUBSURF_IN_EDIT_MODE) && smd->emCache) {
2996       ccgSubSurf_free(smd->emCache);
2997       smd->emCache = NULL;
2998     }
2999
3000     if (useIncremental && (flags & SUBSURF_IS_FINAL_CALC)) {
3001       smd->mCache = ss = _getSubSurf(
3002           smd->mCache, levels, 3, useSimple | useAging | CCG_CALC_NORMALS);
3003
3004       ss_sync_from_derivedmesh(ss, dm, vertCos, useSimple, useSubsurfUv);
3005
3006       result = getCCGDerivedMesh(smd->mCache, drawInteriorEdges, useSubsurfUv, dm, false);
3007     }
3008     else {
3009       CCGFlags ccg_flags = useSimple | CCG_USE_ARENA | CCG_CALC_NORMALS;
3010       CCGSubSurf *prevSS = NULL;
3011
3012       if (smd->mCache && (flags & SUBSURF_IS_FINAL_CALC)) {
3013 #ifdef WITH_OPENSUBDIV
3014         /* With OpenSubdiv enabled we always tries to re-use previous
3015          * subsurf structure in order to save computation time since
3016          * re-creation is rather a complicated business.
3017          *
3018          * TODO(sergey): There was a good eason why final calculation
3019          * used to free entirely cached subsurf structure. reason of
3020          * this is to be investigated still to be sure we don't have
3021          * regressions here.
3022          */
3023         if (use_gpu_backend) {
3024           prevSS = smd->mCache;
3025         }
3026         else
3027 #endif
3028         {
3029           ccgSubSurf_free(smd->mCache);
3030           smd->mCache = NULL;
3031         }
3032       }
3033
3034       if (flags & SUBSURF_ALLOC_PAINT_MASK) {
3035         ccg_flags |= CCG_ALLOC_MASK;
3036       }
3037
3038       ss = _getSubSurf(prevSS, levels, 3, ccg_flags);
3039 #ifdef WITH_OPENSUBDIV
3040       ccgSubSurf_setSkipGrids(ss, use_gpu_backend);
3041 #endif
3042       ss_sync_from_derivedmesh(ss, dm, vertCos, useSimple, useSubsurfUv);
3043
3044       result = getCCGDerivedMesh(ss, drawInteriorEdges, useSubsurfUv, dm, use_gpu_backend);
3045
3046       if (flags & SUBSURF_IS_FINAL_CALC) {
3047         smd->mCache = ss;
3048       }
3049       else {
3050         result->freeSS = 1;
3051       }
3052
3053       if (flags & SUBSURF_ALLOC_PAINT_MASK) {
3054         ccgSubSurf_setNumLayers(ss, 4);
3055       }
3056     }
3057   }
3058
3059   return (DerivedMesh *)result;
3060 }
3061
3062 void subsurf_calculate_limit_positions(Mesh *me, float (*r_positions)[3])
3063 {
3064   /* Finds the subsurf limit positions for the verts in a mesh
3065    * and puts them in an array of floats. Please note that the
3066    * calculated vert positions is incorrect for the verts
3067    * on the boundary of the mesh.
3068    */
3069   CCGSubSurf *ss = _getSubSurf(NULL, 1, 3, CCG_USE_ARENA);
3070   float edge_sum[3], face_sum[3];
3071   CCGVertIterator vi;
3072   DerivedMesh *dm = CDDM_from_mesh(me);
3073
3074   ss_sync_from_derivedmesh(ss, dm, NULL, 0, 0);
3075
3076   for (ccgSubSurf_initVertIterator(ss, &vi); !ccgVertIterator_isStopped(&vi);
3077        ccgVertIterator_next(&vi)) {
3078     CCGVert *v = ccgVertIterator_getCurrent(&vi);
3079     int idx = POINTER_AS_INT(ccgSubSurf_getVertVertHandle(v));
3080     int N = ccgSubSurf_getVertNumEdges(v);
3081     int numFaces = ccgSubSurf_getVertNumFaces(v);
3082     float *co;
3083     int i;
3084
3085     zero_v3(edge_sum);
3086     zero_v3(face_sum);
3087
3088     for (i = 0; i < N; i++) {
3089       CCGEdge *e = ccgSubSurf_getVertEdge(v, i);
3090       add_v3_v3v3(edge_sum, edge_sum, ccgSubSurf_getEdgeData(ss, e, 1));
3091     }
3092     for (i = 0; i < numFaces; i++) {
3093       CCGFace *f = ccgSubSurf_getVertFace(v, i);
3094       add_v3_v3(face_sum, ccgSubSurf_getFaceCenterData(f));
3095     }
3096
3097     /* ad-hoc correction for boundary vertices, to at least avoid them
3098      * moving completely out of place (brecht) */
3099     if (numFaces && numFaces != N) {
3100       mul_v3_fl(face_sum, (float)N / (float)numFaces);
3101     }
3102
3103     co = ccgSubSurf_getVertData(ss, v);
3104     r_positions[idx][0] = (co[0] * N * N + edge_sum[0] * 4 + face_sum[0]) / (N * (N + 5));
3105     r_positions[idx][1] = (co[1] * N * N + edge_sum[1] * 4 + face_sum[1]) / (N * (N + 5));
3106     r_positions[idx][2] = (co[2] * N * N + edge_sum[2] * 4 + face_sum[2]) / (N * (N + 5));
3107   }
3108
3109   ccgSubSurf_free(ss);
3110
3111   dm->release(dm);
3112 }
3113
3114 bool subsurf_has_edges(DerivedMesh *dm)
3115 {
3116   CCGDerivedMesh *ccgdm = (CCGDerivedMesh *)dm;
3117 #ifdef WITH_OPENSUBDIV
3118   if (ccgdm->useGpuBackend) {
3119     return true;
3120   }
3121 #else
3122   (void)ccgdm;
3123 #endif
3124   return dm->getNumEdges(dm) != 0;
3125 }
3126
3127 bool subsurf_has_faces(DerivedMesh *dm)
3128 {
3129   CCGDerivedMesh *ccgdm = (CCGDerivedMesh *)dm;
3130 #ifdef WITH_OPENSUBDIV
3131   if (ccgdm->useGpuBackend) {
3132     return true;
3133   }
3134 #else
3135   (void)ccgdm;
3136 #endif
3137   return dm->getNumPolys(dm) != 0;
3138 }