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