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