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