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