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