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