Merge branch 'master' into blender2.8
[blender.git] / source / blender / blenkernel / intern / cdderivedmesh.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) 2006 Blender Foundation.
19  * All rights reserved.
20  *
21  * The Original Code is: all of this file.
22  *
23  * Contributor(s): Ben Batt <benbatt@gmail.com>
24  *
25  * ***** END GPL LICENSE BLOCK *****
26  *
27  * Implementation of CDDerivedMesh.
28  *
29  * BKE_cdderivedmesh.h contains the function prototypes for this file.
30  *
31  */
32
33 /** \file blender/blenkernel/intern/cdderivedmesh.c
34  *  \ingroup bke
35  */
36
37 #include "atomic_ops.h"
38
39 #include "BLI_math.h"
40 #include "BLI_edgehash.h"
41 #include "BLI_utildefines.h"
42 #include "BLI_utildefines_stack.h"
43
44 #include "BKE_pbvh.h"
45 #include "BKE_cdderivedmesh.h"
46 #include "BKE_global.h"
47 #include "BKE_mesh.h"
48 #include "BKE_mesh_mapping.h"
49 #include "BKE_paint.h"
50 #include "BKE_editmesh.h"
51 #include "BKE_curve.h"
52
53 #include "DNA_mesh_types.h"
54 #include "DNA_meshdata_types.h"
55 #include "DNA_object_types.h"
56 #include "DNA_curve_types.h" /* for Curve */
57
58 #include "MEM_guardedalloc.h"
59
60 #include "GPU_buffers.h"
61 #include "GPU_draw.h"
62 #include "GPU_glew.h"
63 #include "GPU_immediate.h"
64 #include "GPU_shader.h"
65 #include "GPU_basic_shader.h"
66
67 #include "DEG_depsgraph.h"
68
69 #include <string.h>
70 #include <limits.h>
71 #include <math.h>
72
73 typedef struct {
74         DerivedMesh dm;
75
76         /* these point to data in the DerivedMesh custom data layers,
77          * they are only here for efficiency and convenience **/
78         MVert *mvert;
79         MEdge *medge;
80         MFace *mface;
81         MLoop *mloop;
82         MPoly *mpoly;
83
84         /* Cached */
85         struct PBVH *pbvh;
86         bool pbvh_draw;
87
88         /* Mesh connectivity */
89         MeshElemMap *pmap;
90         int *pmap_mem;
91 } CDDerivedMesh;
92
93 /**************** DerivedMesh interface functions ****************/
94 static int cdDM_getNumVerts(DerivedMesh *dm)
95 {
96         return dm->numVertData;
97 }
98
99 static int cdDM_getNumEdges(DerivedMesh *dm)
100 {
101         return dm->numEdgeData;
102 }
103
104 static int cdDM_getNumTessFaces(DerivedMesh *dm)
105 {
106         /* uncomment and add a breakpoint on the printf()
107          * to help debug tessfaces issues since BMESH merge. */
108 #if 0
109         if (dm->numTessFaceData == 0 && dm->numPolyData != 0) {
110                 printf("%s: has no faces!, call DM_ensure_tessface() if you need them\n");
111         }
112 #endif
113         return dm->numTessFaceData;
114 }
115
116 static int cdDM_getNumLoops(DerivedMesh *dm)
117 {
118         return dm->numLoopData;
119 }
120
121 static int cdDM_getNumPolys(DerivedMesh *dm)
122 {
123         return dm->numPolyData;
124 }
125
126 static void cdDM_getVert(DerivedMesh *dm, int index, MVert *r_vert)
127 {
128         CDDerivedMesh *cddm = (CDDerivedMesh *)dm;
129         *r_vert = cddm->mvert[index];
130 }
131
132 static void cdDM_getEdge(DerivedMesh *dm, int index, MEdge *r_edge)
133 {
134         CDDerivedMesh *cddm = (CDDerivedMesh *)dm;
135         *r_edge = cddm->medge[index];
136 }
137
138 static void cdDM_getTessFace(DerivedMesh *dm, int index, MFace *r_face)
139 {
140         CDDerivedMesh *cddm = (CDDerivedMesh *)dm;
141         *r_face = cddm->mface[index];
142 }
143
144 static void cdDM_copyVertArray(DerivedMesh *dm, MVert *r_vert)
145 {
146         CDDerivedMesh *cddm = (CDDerivedMesh *)dm;
147         memcpy(r_vert, cddm->mvert, sizeof(*r_vert) * dm->numVertData);
148 }
149
150 static void cdDM_copyEdgeArray(DerivedMesh *dm, MEdge *r_edge)
151 {
152         CDDerivedMesh *cddm = (CDDerivedMesh *)dm;
153         memcpy(r_edge, cddm->medge, sizeof(*r_edge) * dm->numEdgeData);
154 }
155
156 static void cdDM_copyTessFaceArray(DerivedMesh *dm, MFace *r_face)
157 {
158         CDDerivedMesh *cddm = (CDDerivedMesh *)dm;
159         memcpy(r_face, cddm->mface, sizeof(*r_face) * dm->numTessFaceData);
160 }
161
162 static void cdDM_copyLoopArray(DerivedMesh *dm, MLoop *r_loop)
163 {
164         CDDerivedMesh *cddm = (CDDerivedMesh *)dm;
165         memcpy(r_loop, cddm->mloop, sizeof(*r_loop) * dm->numLoopData);
166 }
167
168 static void cdDM_copyPolyArray(DerivedMesh *dm, MPoly *r_poly)
169 {
170         CDDerivedMesh *cddm = (CDDerivedMesh *)dm;
171         memcpy(r_poly, cddm->mpoly, sizeof(*r_poly) * dm->numPolyData);
172 }
173
174 static void cdDM_getMinMax(DerivedMesh *dm, float r_min[3], float r_max[3])
175 {
176         CDDerivedMesh *cddm = (CDDerivedMesh *) dm;
177         int i;
178
179         if (dm->numVertData) {
180                 for (i = 0; i < dm->numVertData; i++) {
181                         minmax_v3v3_v3(r_min, r_max, cddm->mvert[i].co);
182                 }
183         }
184         else {
185                 zero_v3(r_min);
186                 zero_v3(r_max);
187         }
188 }
189
190 static void cdDM_getVertCo(DerivedMesh *dm, int index, float r_co[3])
191 {
192         CDDerivedMesh *cddm = (CDDerivedMesh *) dm;
193
194         copy_v3_v3(r_co, cddm->mvert[index].co);
195 }
196
197 static void cdDM_getVertCos(DerivedMesh *dm, float (*r_cos)[3])
198 {
199         MVert *mv = CDDM_get_verts(dm);
200         int i;
201
202         for (i = 0; i < dm->numVertData; i++, mv++)
203                 copy_v3_v3(r_cos[i], mv->co);
204 }
205
206 static void cdDM_getVertNo(DerivedMesh *dm, int index, float r_no[3])
207 {
208         CDDerivedMesh *cddm = (CDDerivedMesh *) dm;
209         normal_short_to_float_v3(r_no, cddm->mvert[index].no);
210 }
211
212 static const MeshElemMap *cdDM_getPolyMap(Object *ob, DerivedMesh *dm)
213 {
214         CDDerivedMesh *cddm = (CDDerivedMesh *) dm;
215
216         if (!cddm->pmap && ob->type == OB_MESH) {
217                 Mesh *me = ob->data;
218
219                 BKE_mesh_vert_poly_map_create(
220                         &cddm->pmap, &cddm->pmap_mem,
221                         me->mpoly, me->mloop,
222                         me->totvert, me->totpoly, me->totloop);
223         }
224
225         return cddm->pmap;
226 }
227
228 static bool check_sculpt_object_deformed(Object *object, bool for_construction)
229 {
230         bool deformed = false;
231
232         /* Active modifiers means extra deformation, which can't be handled correct
233          * on birth of PBVH and sculpt "layer" levels, so use PBVH only for internal brush
234          * stuff and show final DerivedMesh so user would see actual object shape.
235          */
236         deformed |= object->sculpt->modifiers_active;
237
238         if (for_construction) {
239                 deformed |= object->sculpt->kb != NULL;
240         }
241         else {
242                 /* As in case with modifiers, we can't synchronize deformation made against
243                  * PBVH and non-locked keyblock, so also use PBVH only for brushes and
244                  * final DM to give final result to user.
245                  */
246                 deformed |= object->sculpt->kb && (object->shapeflag & OB_SHAPE_LOCK) == 0;
247         }
248
249         return deformed;
250 }
251
252 static bool can_pbvh_draw(Object *ob, DerivedMesh *dm)
253 {
254         CDDerivedMesh *cddm = (CDDerivedMesh *) dm;
255         Mesh *me = ob->data;
256         bool deformed = check_sculpt_object_deformed(ob, false);
257
258         if (deformed) {
259                 return false;
260         }
261
262         return cddm->mvert == me->mvert || ob->sculpt->kb;
263 }
264
265 static PBVH *cdDM_getPBVH(
266         Object *ob, DerivedMesh *dm, eObjectMode UNUSED(object_mode))
267 {
268         CDDerivedMesh *cddm = (CDDerivedMesh *) dm;
269
270         if (!ob) {
271                 cddm->pbvh = NULL;
272                 return NULL;
273         }
274
275         if (!ob->sculpt)
276                 return NULL;
277
278         if (ob->sculpt->pbvh) {
279                 cddm->pbvh = ob->sculpt->pbvh;
280                 cddm->pbvh_draw = can_pbvh_draw(ob, dm);
281         }
282
283         /* Sculpting on a BMesh (dynamic-topology) gets a special PBVH */
284         if (!cddm->pbvh && ob->sculpt->bm) {
285                 cddm->pbvh = BKE_pbvh_new();
286                 cddm->pbvh_draw = true;
287
288                 BKE_pbvh_build_bmesh(cddm->pbvh, ob->sculpt->bm,
289                                      ob->sculpt->bm_smooth_shading,
290                                      ob->sculpt->bm_log, ob->sculpt->cd_vert_node_offset,
291                                      ob->sculpt->cd_face_node_offset);
292
293                 pbvh_show_diffuse_color_set(cddm->pbvh, ob->sculpt->show_diffuse_color);
294                 pbvh_show_mask_set(cddm->pbvh, ob->sculpt->show_mask);
295         }
296                 
297
298         /* always build pbvh from original mesh, and only use it for drawing if
299          * this derivedmesh is just original mesh. it's the multires subsurf dm
300          * that this is actually for, to support a pbvh on a modified mesh */
301         if (!cddm->pbvh && ob->type == OB_MESH) {
302                 Mesh *me = ob->data;
303                 const int looptris_num = poly_to_tri_count(me->totpoly, me->totloop);
304                 MLoopTri *looptri;
305                 bool deformed;
306
307                 cddm->pbvh = BKE_pbvh_new();
308                 cddm->pbvh_draw = can_pbvh_draw(ob, dm);
309
310                 looptri = MEM_malloc_arrayN(looptris_num, sizeof(*looptri), __func__);
311
312                 BKE_mesh_recalc_looptri(
313                         me->mloop, me->mpoly,
314                         me->mvert,
315                         me->totloop, me->totpoly,
316                         looptri);
317                 
318                 BKE_pbvh_build_mesh(
319                         cddm->pbvh,
320                         me->mpoly, me->mloop,
321                         me->mvert, me->totvert, &me->vdata,
322                         looptri, looptris_num);
323
324                 pbvh_show_diffuse_color_set(cddm->pbvh, ob->sculpt->show_diffuse_color);
325                 pbvh_show_mask_set(cddm->pbvh, ob->sculpt->show_mask);
326
327                 deformed = check_sculpt_object_deformed(ob, true);
328
329                 if (deformed && ob->derivedDeform) {
330                         DerivedMesh *deformdm = ob->derivedDeform;
331                         float (*vertCos)[3];
332                         int totvert;
333
334                         totvert = deformdm->getNumVerts(deformdm);
335                         vertCos = MEM_malloc_arrayN(totvert, sizeof(float[3]), "cdDM_getPBVH vertCos");
336                         deformdm->getVertCos(deformdm, vertCos);
337                         BKE_pbvh_apply_vertCos(cddm->pbvh, vertCos);
338                         MEM_freeN(vertCos);
339                 }
340         }
341
342         return cddm->pbvh;
343 }
344
345 /* update vertex normals so that drawing smooth faces works during sculpt
346  * TODO: proper fix is to support the pbvh in all drawing modes */
347 static void cdDM_update_normals_from_pbvh(DerivedMesh *dm)
348 {
349         CDDerivedMesh *cddm = (CDDerivedMesh *) dm;
350         float (*face_nors)[3];
351
352         /* Some callbacks do not use optimal PBVH draw, so needs all the
353          * possible data (like normals) to be copied from PBVH back to DM.
354          *
355          * This is safe to do if PBVH and DM are representing the same mesh,
356          * which could be wrong when modifiers are enabled for sculpt.
357          * So here we only doing update when there's no modifiers applied
358          * during sculpt.
359          *
360          * It's safe to do nothing if there are modifiers, because in this
361          * case modifier stack is re-constructed from scratch on every
362          * update.
363          */
364         if (!cddm->pbvh_draw) {
365                 return;
366         }
367
368         face_nors = CustomData_get_layer(&dm->polyData, CD_NORMAL);
369
370         BKE_pbvh_update(cddm->pbvh, PBVH_UpdateNormals, face_nors);
371 }
372
373 static void cdDM_drawVerts(DerivedMesh *dm)
374 {
375         GPU_vertex_setup(dm);
376         if (dm->drawObject->tot_loop_verts)
377                 glDrawArrays(GL_POINTS, 0, dm->drawObject->tot_loop_verts);
378         else
379                 glDrawArrays(GL_POINTS, 0, dm->drawObject->tot_loose_point);
380         GPU_buffers_unbind();
381 }
382
383 static void cdDM_drawEdges(DerivedMesh *dm, bool UNUSED(drawLooseEdges), bool UNUSED(drawAllEdges))
384 {
385         CDDerivedMesh *cddm = (CDDerivedMesh *) dm;
386
387         if (cddm->pbvh && cddm->pbvh_draw &&
388             BKE_pbvh_type(cddm->pbvh) == PBVH_BMESH)
389         {
390                 BKE_pbvh_draw(cddm->pbvh, NULL, NULL, NULL, true, false);
391
392                 return;
393         }
394
395         MVert *vert = cddm->mvert;
396         MEdge *edge = cddm->medge;
397
398         Gwn_VertFormat *format = immVertexFormat();
399         unsigned int pos = GWN_vertformat_attr_add(format, "pos", GWN_COMP_F32, 3, GWN_FETCH_FLOAT);
400
401         /* NOTE: This is active object color, which is not really perfect.
402          * But we can't query color set by glColor() :(
403          */
404         float color[4] = {1.0f, 0.667f, 0.251f, 1.0f};
405
406         immBindBuiltinProgram(GPU_SHADER_3D_UNIFORM_COLOR);
407         immUniformColor4fv(color);
408
409         const int chunk_size = 1024;
410         const int num_chunks = (dm->numEdgeData + chunk_size - 1) / chunk_size;
411
412         for (int chunk = 0; chunk < num_chunks; ++chunk) {
413                 const int num_current_edges = (chunk < num_chunks - 1)
414                         ? chunk_size
415                         : dm->numEdgeData - chunk_size * (num_chunks - 1);
416                 immBeginAtMost(GWN_PRIM_LINES, num_current_edges * 2);
417                 for (int i = 0; i < num_current_edges; i++, edge++) {
418                         immVertex3fv(pos, vert[edge->v1].co);
419                         immVertex3fv(pos, vert[edge->v2].co);
420                 }
421                 immEnd();
422         }
423
424         immUnbindProgram();
425 }
426
427 static void cdDM_drawLooseEdges(DerivedMesh *dm)
428 {
429         int start;
430         int count;
431
432         GPU_edge_setup(dm);
433
434         start = (dm->drawObject->loose_edge_offset * 2);
435         count = (dm->drawObject->totedge - dm->drawObject->loose_edge_offset) * 2;
436
437         if (count) {
438                 GPU_buffer_draw_elements(dm->drawObject->edges, GL_LINES, start, count);
439         }
440
441         GPU_buffers_unbind();
442 }
443
444 static void cdDM_drawFacesSolid(
445         DerivedMesh *dm,
446         float (*partial_redraw_planes)[4],
447         bool fast, DMSetMaterial setMaterial)
448 {
449         UNUSED_VARS(partial_redraw_planes, fast, setMaterial);
450         CDDerivedMesh *cddm = (CDDerivedMesh *) dm;
451         int a;
452
453         if (cddm->pbvh) {
454                 if (cddm->pbvh_draw && BKE_pbvh_has_faces(cddm->pbvh)) {
455                         float (*face_nors)[3] = CustomData_get_layer(&dm->polyData, CD_NORMAL);
456
457                         BKE_pbvh_draw(cddm->pbvh, partial_redraw_planes, face_nors,
458                                       setMaterial, false, false);
459                         return;
460                 }
461         }
462
463         const MVert *mvert = cddm->mvert;
464         const MLoop *mloop = cddm->mloop;
465         const MPoly *mpoly = cddm->mpoly;
466         const int num_looptris = dm->getNumLoopTri(dm);
467         const MLoopTri *looptri = dm->getLoopTriArray(dm);
468         const float (*nors)[3] = dm->getPolyDataArray(dm, CD_NORMAL);
469         const float (*lnors)[3] = dm->getLoopDataArray(dm, CD_NORMAL);
470
471         Gwn_VertFormat *format = immVertexFormat();
472         unsigned int pos = GWN_vertformat_attr_add(format, "pos", GWN_COMP_F32, 3, GWN_FETCH_FLOAT);
473         unsigned int nor = GWN_vertformat_attr_add(format, "nor", GWN_COMP_F32, 3, GWN_FETCH_FLOAT);
474
475         float color[4] = {0.8f, 0.8f, 0.8f, 1.0f};
476         const float light_vec[3] = {0.0f, 0.0f, 1.0f};
477
478         immBindBuiltinProgram(GPU_SHADER_SIMPLE_LIGHTING);
479         immUniformColor4fv(color);
480         immUniform3fv("light", light_vec);
481
482         const int chunk_size = 1024;
483         const int num_chunks = (num_looptris + chunk_size - 1) / chunk_size;
484
485         for (int chunk = 0; chunk < num_chunks; ++chunk) {
486                 const int num_current_looptris = (chunk < num_chunks - 1)
487                         ? chunk_size
488                         : num_looptris - chunk_size * (num_chunks - 1);
489
490                 immBeginAtMost(GWN_PRIM_TRIS, num_current_looptris * 3);
491
492                 for (a = 0; a < num_current_looptris; a++, looptri++) {
493                         const MPoly *mp = &mpoly[looptri->poly];
494                         const bool smoothnormal = (lnors != NULL) || (mp->flag & ME_SMOOTH);
495                         const unsigned int vtri[3] = {mloop[looptri->tri[0]].v,
496                                                       mloop[looptri->tri[1]].v,
497                                                       mloop[looptri->tri[2]].v};
498                         const unsigned int *ltri = looptri->tri;
499                         float normals[3][3];
500                         if (!smoothnormal) {
501                                 if (nors != NULL) {
502                                         copy_v3_v3(normals[0], nors[looptri->poly]);
503                                 }
504                                 else {
505                                         normal_tri_v3(normals[0],
506                                                       mvert[vtri[0]].co,
507                                                       mvert[vtri[1]].co,
508                                                       mvert[vtri[2]].co);
509                                 }
510                                 copy_v3_v3(normals[1], normals[0]);
511                                 copy_v3_v3(normals[2], normals[0]);
512                         }
513                         else if (lnors != NULL) {
514                                 copy_v3_v3(normals[0], lnors[ltri[0]]);
515                                 copy_v3_v3(normals[1], lnors[ltri[1]]);
516                                 copy_v3_v3(normals[2], lnors[ltri[2]]);
517                         }
518                         else {
519                                 normal_short_to_float_v3(normals[0], mvert[vtri[0]].no);
520                                 normal_short_to_float_v3(normals[1], mvert[vtri[1]].no);
521                                 normal_short_to_float_v3(normals[2], mvert[vtri[2]].no);
522                         }
523
524                         immAttrib3fv(nor, normals[0]);
525                         immVertex3fv(pos, mvert[vtri[0]].co);
526                         immAttrib3fv(nor, normals[1]);
527                         immVertex3fv(pos, mvert[vtri[1]].co);
528                         immAttrib3fv(nor, normals[2]);
529                         immVertex3fv(pos, mvert[vtri[2]].co);
530                 }
531                 immEnd();
532         }
533
534         immUnbindProgram();
535 }
536
537 static void cdDM_drawMappedFaces(
538         DerivedMesh *dm,
539         DMSetDrawOptions setDrawOptions,
540         DMSetMaterial setMaterial,
541         DMCompareDrawOptions compareDrawOptions,
542         void *userData, DMDrawFlag flag)
543 {
544         CDDerivedMesh *cddm = (CDDerivedMesh *) dm;
545         const MPoly *mpoly = cddm->mpoly;
546         const MLoopCol *mloopcol = NULL;
547         const bool use_colors = (flag & DM_DRAW_USE_COLORS) != 0;
548         const bool use_hide = (flag & DM_DRAW_SKIP_HIDDEN) != 0;
549         int colType;
550         int i, j;
551         int start_element = 0, tot_element, tot_drawn;
552         int totpoly;
553         int tot_tri_elem;
554         int mat_index;
555         GPUBuffer *findex_buffer = NULL;
556
557         const int *index_mp_to_orig  = dm->getPolyDataArray(dm, CD_ORIGINDEX);
558
559         if (cddm->pbvh) {
560                 if (G.debug_value == 14)
561                         BKE_pbvh_draw_BB(cddm->pbvh);
562         }
563
564         /* fist, setup common buffers */
565         GPU_vertex_setup(dm);
566         GPU_triangle_setup(dm);
567
568         totpoly = dm->getNumPolys(dm);
569
570         /* if we do selection, fill the selection buffer color */
571         if (G.f & G_BACKBUFSEL) {
572                 if (!(flag & DM_DRAW_SKIP_SELECT)) {
573                         Mesh *me = NULL;
574                         BMesh *bm = NULL;
575                         unsigned int *fi_map;
576
577                         if (flag & DM_DRAW_SELECT_USE_EDITMODE)
578                                 bm = userData;
579                         else
580                                 me = userData;
581
582                         findex_buffer = GPU_buffer_alloc(dm->drawObject->tot_loop_verts * sizeof(int));
583                         fi_map = GPU_buffer_lock(findex_buffer, GPU_BINDING_ARRAY);
584
585                         if (fi_map) {
586                                 for (i = 0; i < totpoly; i++, mpoly++) {
587                                         int selcol = 0xFFFFFFFF;
588                                         const int orig = (index_mp_to_orig) ? index_mp_to_orig[i] : i;
589                                         bool is_hidden;
590
591                                         if (orig != ORIGINDEX_NONE) {
592                                                 if (use_hide) {
593                                                         if (flag & DM_DRAW_SELECT_USE_EDITMODE) {
594                                                                 BMFace *efa = BM_face_at_index(bm, orig);
595                                                                 is_hidden = BM_elem_flag_test(efa, BM_ELEM_HIDDEN) != 0;
596                                                         }
597                                                         else {
598                                                                 is_hidden = (me->mpoly[orig].flag & ME_HIDE) != 0;
599                                                         }
600
601                                                         if (!is_hidden) {
602                                                                 GPU_select_index_get(orig + 1, &selcol);
603                                                         }
604                                                 }
605                                                 else {
606                                                         GPU_select_index_get(orig + 1, &selcol);
607                                                 }
608                                         }
609
610                                         for (j = 0; j < mpoly->totloop; j++)
611                                                 fi_map[start_element++] = selcol;
612                                 }
613
614                                 start_element = 0;
615                                 mpoly = cddm->mpoly;
616
617                                 GPU_buffer_unlock(findex_buffer, GPU_BINDING_ARRAY);
618                                 GPU_buffer_bind_as_color(findex_buffer);
619                         }
620                 }
621         }
622         else {
623                 GPU_normal_setup(dm);
624
625                 if (use_colors) {
626                         colType = CD_TEXTURE_MLOOPCOL;
627                         mloopcol = DM_get_loop_data_layer(dm, colType);
628                         if (!mloopcol) {
629                                 colType = CD_PREVIEW_MLOOPCOL;
630                                 mloopcol = DM_get_loop_data_layer(dm, colType);
631                         }
632                         if (!mloopcol) {
633                                 colType = CD_MLOOPCOL;
634                                 mloopcol = DM_get_loop_data_layer(dm, colType);
635                         }
636
637                         if (use_colors && mloopcol) {
638                                 GPU_color_setup(dm, colType);
639                         }
640                 }
641         }
642
643         tot_tri_elem = dm->drawObject->tot_triangle_point;
644
645         if (tot_tri_elem == 0) {
646                 /* avoid buffer problems in following code */
647         }
648         else if (setDrawOptions == NULL) {
649                 /* just draw the entire face array */
650                 GPU_buffer_draw_elements(dm->drawObject->triangles, GL_TRIANGLES, 0, tot_tri_elem);
651         }
652         else {
653                 for (mat_index = 0; mat_index < dm->drawObject->totmaterial; mat_index++) {
654                         GPUBufferMaterial *bufmat = dm->drawObject->materials + mat_index;
655                         DMDrawOption draw_option = DM_DRAW_OPTION_NORMAL;
656                         int next_actualFace = bufmat->polys[0];
657                         totpoly = use_hide ? bufmat->totvisiblepolys : bufmat->totpolys;
658
659                         tot_element = 0;
660                         start_element = 0;
661                         tot_drawn = 0;
662
663                         if (setMaterial)
664                                 draw_option = setMaterial(bufmat->mat_nr + 1, NULL);
665
666                         if (draw_option != DM_DRAW_OPTION_SKIP) {
667                                 DMDrawOption last_draw_option = DM_DRAW_OPTION_NORMAL;
668
669                                 for (i = 0; i < totpoly; i++) {
670                                         int actualFace = next_actualFace;
671                                         int flush = 0;
672                                         int tot_tri_verts;
673
674                                         draw_option = DM_DRAW_OPTION_NORMAL;
675
676                                         if (i != totpoly - 1)
677                                                 next_actualFace = bufmat->polys[i + 1];
678
679                                         if (setDrawOptions) {
680                                                 const int orig = (index_mp_to_orig) ? index_mp_to_orig[actualFace] : actualFace;
681
682                                                 if (orig != ORIGINDEX_NONE) {
683                                                         draw_option = setDrawOptions(userData, orig);
684                                                 }
685                                         }
686
687                                         /* Goal is to draw as long of a contiguous triangle
688                                          * array as possible, so draw when we hit either an
689                                          * invisible triangle or at the end of the array */
690
691                                         /* flush buffer if current triangle isn't drawable or it's last triangle... */
692                                         flush = (draw_option != last_draw_option) || (i == totpoly - 1);
693
694                                         if (!flush && compareDrawOptions) {
695                                                 flush |= compareDrawOptions(userData, actualFace, next_actualFace) == 0;
696                                         }
697
698                                         tot_tri_verts = ME_POLY_TRI_TOT(&mpoly[actualFace]) * 3;
699                                         tot_element += tot_tri_verts;
700
701                                         if (flush) {
702                                                 if (draw_option != DM_DRAW_OPTION_SKIP) {
703                                                         tot_drawn += tot_tri_verts;
704
705                                                         if (last_draw_option != draw_option) {
706                                                                 if (draw_option == DM_DRAW_OPTION_STIPPLE) {
707                                                                         GPU_basic_shader_bind(GPU_SHADER_STIPPLE | GPU_SHADER_USE_COLOR);
708                                                                         GPU_basic_shader_stipple(GPU_SHADER_STIPPLE_QUARTTONE);
709                                                                 }
710                                                                 else {
711                                                                         GPU_basic_shader_bind(GPU_SHADER_USE_COLOR);
712                                                                 }
713                                                         }
714                                                 }
715
716                                                 if (tot_drawn) {
717                                                         GPU_buffer_draw_elements(dm->drawObject->triangles, GL_TRIANGLES, bufmat->start + start_element, tot_drawn);
718                                                         tot_drawn = 0;
719                                                 }
720
721                                                 last_draw_option = draw_option;
722                                                 start_element = tot_element;
723                                         }
724                                         else {
725                                                 if (draw_option != DM_DRAW_OPTION_SKIP) {
726                                                         tot_drawn += tot_tri_verts;
727                                                 }
728                                                 else {
729                                                         start_element = tot_element;
730                                                 }
731                                         }
732                                 }
733                         }
734                 }
735         }
736
737         GPU_basic_shader_bind(GPU_SHADER_USE_COLOR);
738
739         GPU_buffers_unbind();
740
741         if (findex_buffer)
742                 GPU_buffer_free(findex_buffer);
743
744 }
745
746 static void cddm_draw_attrib_vertex(
747         DMVertexAttribs *attribs, const MVert *mvert, int a, int index, int loop, int vert,
748         const float *lnor, const bool smoothnormal)
749 {
750         DM_draw_attrib_vertex(attribs, a, index, vert, loop);
751
752         /* vertex normal */
753         if (lnor) {
754                 glNormal3fv(lnor);
755         }
756         else if (smoothnormal) {
757                 glNormal3sv(mvert[index].no);
758         }
759
760         /* vertex coordinate */
761         glVertex3fv(mvert[index].co);
762 }
763
764 typedef struct {
765         DMVertexAttribs attribs;
766         int numdata;
767
768         GPUAttrib datatypes[GPU_MAX_ATTRIB]; /* TODO, messing up when switching materials many times - [#21056]*/
769 } GPUMaterialConv;
770
771 static void cdDM_drawMappedFacesGLSL(
772         DerivedMesh *dm,
773         DMSetMaterial setMaterial,
774         DMSetDrawOptions setDrawOptions,
775         void *userData)
776 {
777         CDDerivedMesh *cddm = (CDDerivedMesh *) dm;
778         GPUVertexAttribs gattribs;
779         const MVert *mvert = cddm->mvert;
780         const MPoly *mpoly = cddm->mpoly;
781         const MLoop *mloop = cddm->mloop;
782         const MLoopTri *lt = dm->getLoopTriArray(dm);
783         const int tottri = dm->getNumLoopTri(dm);
784         /* MTFace *tf = dm->getTessFaceDataArray(dm, CD_MTFACE); */ /* UNUSED */
785         const float (*nors)[3] = dm->getPolyDataArray(dm, CD_NORMAL);
786         const float (*lnors)[3] = dm->getLoopDataArray(dm, CD_NORMAL);
787         const int totpoly = dm->getNumPolys(dm);
788         const short dm_totmat = dm->totmat;
789         int a, b, matnr, new_matnr;
790         bool do_draw;
791         int orig;
792
793         const int *index_mp_to_orig  = dm->getPolyDataArray(dm, CD_ORIGINDEX);
794
795         /* TODO: same as for solid draw, not entirely correct, but works fine for now,
796          *       will skip using textures (dyntopo currently destroys UV anyway) and
797          *       works fine for matcap
798          */
799         if (cddm->pbvh) {
800                 if (cddm->pbvh_draw &&
801                     BKE_pbvh_type(cddm->pbvh) == PBVH_BMESH &&
802                     BKE_pbvh_has_faces(cddm->pbvh))
803                 {
804                         setMaterial(1, &gattribs);
805                         BKE_pbvh_draw(cddm->pbvh, NULL, NULL, NULL, false, false);
806                         return;
807                 }
808                 else {
809                         cdDM_update_normals_from_pbvh(dm);
810                 }
811         }
812
813         matnr = -1;
814         do_draw = false;
815
816         if (setDrawOptions != NULL) {
817                 DMVertexAttribs attribs;
818                 DEBUG_VBO("Using legacy code. cdDM_drawMappedFacesGLSL\n");
819                 memset(&attribs, 0, sizeof(attribs));
820
821                 glBegin(GL_TRIANGLES);
822
823                 for (a = 0; a < tottri; a++, lt++) {
824                         const MPoly *mp = &mpoly[lt->poly];
825                         const unsigned int  vtri[3] = {mloop[lt->tri[0]].v, mloop[lt->tri[1]].v, mloop[lt->tri[2]].v};
826                         const unsigned int *ltri = lt->tri;
827                         const float *ln1 = NULL, *ln2 = NULL, *ln3 = NULL;
828                         const bool smoothnormal = lnors || (mp->flag & ME_SMOOTH);
829                         new_matnr = mp->mat_nr;
830
831                         if (new_matnr != matnr) {
832                                 glEnd();
833
834                                 matnr = new_matnr;
835                                 do_draw = setMaterial(matnr + 1, &gattribs);
836                                 if (do_draw) {
837                                         DM_vertex_attributes_from_gpu(dm, &gattribs, &attribs);
838                                         DM_draw_attrib_vertex_uniforms(&attribs);
839                                 }
840
841                                 glBegin(GL_TRIANGLES);
842                         }
843
844                         if (!do_draw) {
845                                 continue;
846                         }
847                         else /* if (setDrawOptions) */ {
848                                 orig = (index_mp_to_orig) ? index_mp_to_orig[lt->poly] : lt->poly;
849
850                                 if (orig == ORIGINDEX_NONE) {
851                                         /* since the material is set by setMaterial(), faces with no
852                                          * origin can be assumed to be generated by a modifier */ 
853                                         
854                                         /* continue */
855                                 }
856                                 else if (setDrawOptions(userData, orig) == DM_DRAW_OPTION_SKIP)
857                                         continue;
858                         }
859
860                         if (!smoothnormal) {
861                                 if (nors) {
862                                         glNormal3fv(nors[lt->poly]);
863                                 }
864                                 else {
865                                         /* TODO ideally a normal layer should always be available */
866                                         float nor[3];
867                                         normal_tri_v3(nor, mvert[vtri[0]].co, mvert[vtri[1]].co, mvert[vtri[2]].co);
868                                         glNormal3fv(nor);
869                                 }
870                         }
871                         else if (lnors) {
872                                 ln1 = lnors[ltri[0]];
873                                 ln2 = lnors[ltri[1]];
874                                 ln3 = lnors[ltri[2]];
875                         }
876                         
877                         cddm_draw_attrib_vertex(&attribs, mvert, a, vtri[0], ltri[0], 0, ln1, smoothnormal);
878                         cddm_draw_attrib_vertex(&attribs, mvert, a, vtri[1], ltri[1], 1, ln2, smoothnormal);
879                         cddm_draw_attrib_vertex(&attribs, mvert, a, vtri[2], ltri[2], 2, ln3, smoothnormal);
880                 }
881                 glEnd();
882         }
883         else {
884                 GPUMaterialConv *matconv;
885                 int offset;
886                 int *mat_orig_to_new;
887                 int tot_active_mat;
888                 GPUBuffer *buffer = NULL;
889                 unsigned char *varray;
890                 size_t max_element_size = 0;
891                 int tot_loops = 0;
892
893                 GPU_vertex_setup(dm);
894                 GPU_normal_setup(dm);
895                 GPU_triangle_setup(dm);
896
897                 tot_active_mat = dm->drawObject->totmaterial;
898
899                 matconv = MEM_calloc_arrayN(tot_active_mat, sizeof(*matconv),
900                                       "cdDM_drawMappedFacesGLSL.matconv");
901                 mat_orig_to_new = MEM_malloc_arrayN(dm->totmat, sizeof(*mat_orig_to_new),
902                                               "cdDM_drawMappedFacesGLSL.mat_orig_to_new");
903
904                 /* part one, check what attributes are needed per material */
905                 for (a = 0; a < tot_active_mat; a++) {
906                         new_matnr = dm->drawObject->materials[a].mat_nr;
907
908                         /* map from original material index to new
909                          * GPUBufferMaterial index */
910                         mat_orig_to_new[new_matnr] = a;
911                         do_draw = setMaterial(new_matnr + 1, &gattribs);
912
913                         if (do_draw) {
914                                 int numdata = 0;
915                                 DM_vertex_attributes_from_gpu(dm, &gattribs, &matconv[a].attribs);
916
917                                 if (matconv[a].attribs.totorco && matconv[a].attribs.orco.array) {
918                                         matconv[a].datatypes[numdata].index = matconv[a].attribs.orco.gl_index;
919                                         matconv[a].datatypes[numdata].info_index = matconv[a].attribs.orco.gl_info_index;
920                                         matconv[a].datatypes[numdata].size = 3;
921                                         matconv[a].datatypes[numdata].type = GL_FLOAT;
922                                         numdata++;
923                                 }
924                                 for (b = 0; b < matconv[a].attribs.tottface; b++) {
925                                         if (matconv[a].attribs.tface[b].array) {
926                                                 matconv[a].datatypes[numdata].index = matconv[a].attribs.tface[b].gl_index;
927                                                 matconv[a].datatypes[numdata].info_index = matconv[a].attribs.tface[b].gl_info_index;
928                                                 matconv[a].datatypes[numdata].size = 2;
929                                                 matconv[a].datatypes[numdata].type = GL_FLOAT;
930                                                 numdata++;
931                                         }
932                                 }
933                                 for (b = 0; b < matconv[a].attribs.totmcol; b++) {
934                                         if (matconv[a].attribs.mcol[b].array) {
935                                                 matconv[a].datatypes[numdata].index = matconv[a].attribs.mcol[b].gl_index;
936                                                 matconv[a].datatypes[numdata].info_index = matconv[a].attribs.mcol[b].gl_info_index;
937                                                 matconv[a].datatypes[numdata].size = 4;
938                                                 matconv[a].datatypes[numdata].type = GL_UNSIGNED_BYTE;
939                                                 numdata++;
940                                         }
941                                 }
942                                 for (b = 0; b < matconv[a].attribs.tottang; b++) {
943                                         if (matconv[a].attribs.tang[b].array) {
944                                                 matconv[a].datatypes[numdata].index = matconv[a].attribs.tang[b].gl_index;
945                                                 matconv[a].datatypes[numdata].info_index = matconv[a].attribs.tang[b].gl_info_index;
946                                                 matconv[a].datatypes[numdata].size = 4;
947                                                 matconv[a].datatypes[numdata].type = GL_FLOAT;
948                                                 numdata++;
949                                         }
950                                 }
951                                 if (numdata != 0) {
952                                         matconv[a].numdata = numdata;
953                                         max_element_size = max_ii(GPU_attrib_element_size(matconv[a].datatypes, numdata), max_element_size);
954                                 }
955                         }
956                 }
957
958                 /* part two, generate and fill the arrays with the data */
959                 if (max_element_size > 0) {
960                         buffer = GPU_buffer_alloc(max_element_size * dm->drawObject->tot_loop_verts);
961
962                         varray = GPU_buffer_lock_stream(buffer, GPU_BINDING_ARRAY);
963                         if (varray == NULL) {
964                                 GPU_buffers_unbind();
965                                 GPU_buffer_free(buffer);
966                                 MEM_freeN(mat_orig_to_new);
967                                 MEM_freeN(matconv);
968                                 fprintf(stderr, "Out of memory, can't draw object\n");
969                                 return;
970                         }
971
972                         for (a = 0; a < totpoly; a++, mpoly++) {
973                                 const short mat_nr = ME_MAT_NR_TEST(mpoly->mat_nr, dm_totmat);
974                                 int j;
975                                 int i = mat_orig_to_new[mat_nr];
976                                 offset = tot_loops * max_element_size;
977
978                                 if (matconv[i].numdata != 0) {
979                                         if (matconv[i].attribs.totorco && matconv[i].attribs.orco.array) {
980                                                 for (j = 0; j < mpoly->totloop; j++)
981                                                         copy_v3_v3((float *)&varray[offset + j * max_element_size],
982                                                                    (float *)matconv[i].attribs.orco.array[mloop[mpoly->loopstart + j].v]);
983                                                 offset += sizeof(float) * 3;
984                                         }
985                                         for (b = 0; b < matconv[i].attribs.tottface; b++) {
986                                                 if (matconv[i].attribs.tface[b].array) {
987                                                         const MLoopUV *mloopuv = matconv[i].attribs.tface[b].array;
988                                                         for (j = 0; j < mpoly->totloop; j++)
989                                                                 copy_v2_v2((float *)&varray[offset + j * max_element_size], mloopuv[mpoly->loopstart + j].uv);
990                                                         offset += sizeof(float) * 2;
991                                                 }
992                                         }
993                                         for (b = 0; b < matconv[i].attribs.totmcol; b++) {
994                                                 if (matconv[i].attribs.mcol[b].array) {
995                                                         const MLoopCol *mloopcol = matconv[i].attribs.mcol[b].array;
996                                                         for (j = 0; j < mpoly->totloop; j++)
997                                                                 copy_v4_v4_uchar(&varray[offset + j * max_element_size], &mloopcol[mpoly->loopstart + j].r);
998                                                         offset += sizeof(unsigned char) * 4;
999                                                 }
1000                                         }
1001                                         for (b = 0; b < matconv[i].attribs.tottang; b++) {
1002                                                 if (matconv[i].attribs.tottang && matconv[i].attribs.tang[b].array) {
1003                                                         const float (*looptang)[4] = (const float (*)[4])matconv[i].attribs.tang[b].array;
1004                                                         for (j = 0; j < mpoly->totloop; j++)
1005                                                                 copy_v4_v4((float *)&varray[offset + j * max_element_size], looptang[mpoly->loopstart + j]);
1006                                                         offset += sizeof(float) * 4;
1007                                                 }
1008                                         }
1009                                 }
1010
1011                                 tot_loops += mpoly->totloop;
1012                         }
1013                         GPU_buffer_unlock(buffer, GPU_BINDING_ARRAY);
1014                 }
1015
1016                 for (a = 0; a < tot_active_mat; a++) {
1017                         new_matnr = dm->drawObject->materials[a].mat_nr;
1018
1019                         do_draw = setMaterial(new_matnr + 1, &gattribs);
1020
1021                         if (do_draw) {
1022                                 if (matconv[a].numdata) {
1023                                         GPU_interleaved_attrib_setup(buffer, matconv[a].datatypes, matconv[a].numdata, max_element_size);
1024                                 }
1025                                 GPU_buffer_draw_elements(dm->drawObject->triangles, GL_TRIANGLES,
1026                                                          dm->drawObject->materials[a].start, dm->drawObject->materials[a].totelements);
1027                                 if (matconv[a].numdata) {
1028                                         GPU_interleaved_attrib_unbind();
1029                                 }
1030                         }
1031                 }
1032
1033                 GPU_buffers_unbind();
1034                 if (buffer)
1035                         GPU_buffer_free(buffer);
1036
1037                 MEM_freeN(mat_orig_to_new);
1038                 MEM_freeN(matconv);
1039         }
1040 }
1041
1042 static void cdDM_drawFacesGLSL(DerivedMesh *dm, DMSetMaterial setMaterial)
1043 {
1044         dm->drawMappedFacesGLSL(dm, setMaterial, NULL, NULL);
1045 }
1046
1047 static void cdDM_drawMappedFacesMat(
1048         DerivedMesh *dm,
1049         void (*setMaterial)(void *userData, int matnr, void *attribs),
1050         bool (*setFace)(void *userData, int index), void *userData)
1051 {
1052         CDDerivedMesh *cddm = (CDDerivedMesh *) dm;
1053         GPUVertexAttribs gattribs;
1054         DMVertexAttribs attribs;
1055         MVert *mvert = cddm->mvert;
1056         const MPoly *mpoly = cddm->mpoly;
1057         const MLoop *mloop = cddm->mloop;
1058         const MLoopTri *lt = dm->getLoopTriArray(dm);
1059         const int tottri = dm->getNumLoopTri(dm);
1060         const float (*nors)[3] = dm->getPolyDataArray(dm, CD_NORMAL);
1061         const float (*lnors)[3] = dm->getLoopDataArray(dm, CD_NORMAL);
1062         int a, matnr, new_matnr;
1063         int orig;
1064
1065         const int *index_mp_to_orig  = dm->getPolyDataArray(dm, CD_ORIGINDEX);
1066
1067         /* TODO: same as for solid draw, not entirely correct, but works fine for now,
1068          *       will skip using textures (dyntopo currently destroys UV anyway) and
1069          *       works fine for matcap
1070          */
1071
1072         if (cddm->pbvh) {
1073                 if (cddm->pbvh_draw &&
1074                     BKE_pbvh_type(cddm->pbvh) == PBVH_BMESH &&
1075                     BKE_pbvh_has_faces(cddm->pbvh))
1076                 {
1077                         setMaterial(userData, 1, &gattribs);
1078                         BKE_pbvh_draw(cddm->pbvh, NULL, NULL, NULL, false, false);
1079                         return;
1080                 }
1081                 else {
1082                         cdDM_update_normals_from_pbvh(dm);
1083                 }
1084         }
1085
1086         matnr = -1;
1087
1088         memset(&attribs, 0, sizeof(attribs));
1089
1090         glBegin(GL_TRIANGLES);
1091
1092         for (a = 0; a < tottri; a++, lt++) {
1093                 const MPoly *mp = &mpoly[lt->poly];
1094                 const unsigned int  vtri[3] = {mloop[lt->tri[0]].v, mloop[lt->tri[1]].v, mloop[lt->tri[2]].v};
1095                 const unsigned int *ltri = lt->tri;
1096                 const bool smoothnormal = lnors || (mp->flag & ME_SMOOTH);
1097                 const float *ln1 = NULL, *ln2 = NULL, *ln3 = NULL;
1098
1099                 /* material */
1100                 new_matnr = mp->mat_nr + 1;
1101
1102                 if (new_matnr != matnr) {
1103                         glEnd();
1104
1105                         setMaterial(userData, matnr = new_matnr, &gattribs);
1106                         DM_vertex_attributes_from_gpu(dm, &gattribs, &attribs);
1107                         DM_draw_attrib_vertex_uniforms(&attribs);
1108
1109                         glBegin(GL_TRIANGLES);
1110                 }
1111
1112                 /* skipping faces */
1113                 if (setFace) {
1114                         orig = (index_mp_to_orig) ? index_mp_to_orig[lt->poly] : lt->poly;
1115
1116                         if (orig != ORIGINDEX_NONE && !setFace(userData, orig))
1117                                 continue;
1118                 }
1119
1120                 /* smooth normal */
1121                 if (!smoothnormal) {
1122                         if (nors) {
1123                                 glNormal3fv(nors[lt->poly]);
1124                         }
1125                         else {
1126                                 /* TODO ideally a normal layer should always be available */
1127                                 float nor[3];
1128                                 normal_tri_v3(nor, mvert[vtri[0]].co, mvert[vtri[1]].co, mvert[vtri[2]].co);
1129                                 glNormal3fv(nor);
1130                         }
1131                 }
1132                 else if (lnors) {
1133                         ln1 = lnors[ltri[0]];
1134                         ln2 = lnors[ltri[1]];
1135                         ln3 = lnors[ltri[2]];
1136                 }
1137
1138                 /* vertices */
1139                 cddm_draw_attrib_vertex(&attribs, mvert, a, vtri[0], ltri[0], 0, ln1, smoothnormal);
1140                 cddm_draw_attrib_vertex(&attribs, mvert, a, vtri[1], ltri[1], 1, ln2, smoothnormal);
1141                 cddm_draw_attrib_vertex(&attribs, mvert, a, vtri[2], ltri[2], 2, ln3, smoothnormal);
1142         }
1143         glEnd();
1144 }
1145
1146 static void cdDM_drawMappedEdges(DerivedMesh *dm, DMSetDrawOptions setDrawOptions, void *userData)
1147 {
1148         CDDerivedMesh *cddm = (CDDerivedMesh *) dm;
1149         MVert *vert = cddm->mvert;
1150         MEdge *edge = cddm->medge;
1151         int i, orig, *index = DM_get_edge_data_layer(dm, CD_ORIGINDEX);
1152
1153         glBegin(GL_LINES);
1154         for (i = 0; i < dm->numEdgeData; i++, edge++) {
1155                 if (index) {
1156                         orig = *index++;
1157                         if (setDrawOptions && orig == ORIGINDEX_NONE) continue;
1158                 }
1159                 else
1160                         orig = i;
1161
1162                 if (!setDrawOptions || (setDrawOptions(userData, orig) != DM_DRAW_OPTION_SKIP)) {
1163                         glVertex3fv(vert[edge->v1].co);
1164                         glVertex3fv(vert[edge->v2].co);
1165                 }
1166         }
1167         glEnd();
1168 }
1169
1170 typedef struct FaceCount {
1171         unsigned int i_visible;
1172         unsigned int i_hidden;
1173         unsigned int i_tri_visible;
1174         unsigned int i_tri_hidden;
1175 } FaceCount;
1176
1177 static void cdDM_buffer_copy_triangles(
1178         DerivedMesh *dm, unsigned int *varray,
1179         const int *mat_orig_to_new)
1180 {
1181         GPUBufferMaterial *gpumat, *gpumaterials = dm->drawObject->materials;
1182         int i, j, start;
1183
1184         const int gpu_totmat = dm->drawObject->totmaterial;
1185         const short dm_totmat = dm->totmat;
1186         const MPoly *mpoly = dm->getPolyArray(dm);
1187         const MLoopTri *lt = dm->getLoopTriArray(dm);
1188         const int totpoly = dm->getNumPolys(dm);
1189
1190         FaceCount *fc = MEM_malloc_arrayN(gpu_totmat, sizeof(*fc), "gpumaterial.facecount");
1191
1192         for (i = 0; i < gpu_totmat; i++) {
1193                 fc[i].i_visible = 0;
1194                 fc[i].i_tri_visible = 0;
1195                 fc[i].i_hidden = gpumaterials[i].totpolys - 1;
1196                 fc[i].i_tri_hidden = gpumaterials[i].totelements - 1;
1197         }
1198
1199         for (i = 0; i < totpoly; i++) {
1200                 const short mat_nr = ME_MAT_NR_TEST(mpoly[i].mat_nr, dm_totmat);
1201                 int tottri = ME_POLY_TRI_TOT(&mpoly[i]);
1202                 int mati = mat_orig_to_new[mat_nr];
1203                 gpumat = gpumaterials + mati;
1204
1205                 if (mpoly[i].flag & ME_HIDE) {
1206                         for (j = 0; j < tottri; j++, lt++) {
1207                                 start = gpumat->start + fc[mati].i_tri_hidden;
1208                                 /* v1 v2 v3 */
1209                                 varray[start--] = lt->tri[2];
1210                                 varray[start--] = lt->tri[1];
1211                                 varray[start--] = lt->tri[0];
1212                                 fc[mati].i_tri_hidden -= 3;
1213                         }
1214                         gpumat->polys[fc[mati].i_hidden--] = i;
1215                 }
1216                 else {
1217                         for (j = 0; j < tottri; j++, lt++) {
1218                                 start = gpumat->start + fc[mati].i_tri_visible;
1219                                 /* v1 v2 v3 */
1220                                 varray[start++] = lt->tri[0];
1221                                 varray[start++] = lt->tri[1];
1222                                 varray[start++] = lt->tri[2];
1223                                 fc[mati].i_tri_visible += 3;
1224                         }
1225                         gpumat->polys[fc[mati].i_visible++] = i;
1226                 }
1227         }
1228
1229         /* set the visible polygons */
1230         for (i = 0; i < gpu_totmat; i++) {
1231                 gpumaterials[i].totvisiblepolys = fc[i].i_visible;
1232         }
1233
1234         MEM_freeN(fc);
1235 }
1236
1237 static void cdDM_buffer_copy_vertex(
1238         DerivedMesh *dm, float *varray)
1239 {
1240         const MVert *mvert;
1241         const MPoly *mpoly;
1242         const MLoop *mloop;
1243
1244         int i, j, start, totpoly;
1245
1246         mvert = dm->getVertArray(dm);
1247         mpoly = dm->getPolyArray(dm);
1248         mloop = dm->getLoopArray(dm);
1249         totpoly = dm->getNumPolys(dm);
1250
1251         start = 0;
1252
1253         for (i = 0; i < totpoly; i++, mpoly++) {
1254                 for (j = 0; j < mpoly->totloop; j++) {
1255                         copy_v3_v3(&varray[start], mvert[mloop[mpoly->loopstart + j].v].co);
1256                         start += 3;
1257                 }
1258         }
1259
1260         /* copy loose points */
1261         j = dm->drawObject->tot_loop_verts * 3;
1262         for (i = 0; i < dm->drawObject->totvert; i++) {
1263                 if (dm->drawObject->vert_points[i].point_index >= dm->drawObject->tot_loop_verts) {
1264                         copy_v3_v3(&varray[j], mvert[i].co);
1265                         j += 3;
1266                 }
1267         }
1268 }
1269
1270 static void cdDM_buffer_copy_normal(
1271         DerivedMesh *dm, short *varray)
1272 {
1273         CDDerivedMesh *cddm = (CDDerivedMesh *)dm;
1274         int i, j, totpoly;
1275         int start;
1276
1277         const float (*nors)[3] = dm->getPolyDataArray(dm, CD_NORMAL);
1278         const float (*lnors)[3] = dm->getLoopDataArray(dm, CD_NORMAL);
1279
1280         const MVert *mvert;
1281         const MPoly *mpoly;
1282         const MLoop *mloop;
1283
1284         mvert = dm->getVertArray(dm);
1285         mpoly = dm->getPolyArray(dm);
1286         mloop = dm->getLoopArray(dm);
1287         totpoly = dm->getNumPolys(dm);
1288
1289         /* we are in sculpt mode, disable loop normals (since they won't get updated) */
1290         if (cddm->pbvh)
1291                 lnors = NULL;
1292
1293         start = 0;
1294         for (i = 0; i < totpoly; i++, mpoly++) {
1295                 const bool smoothnormal = (mpoly->flag & ME_SMOOTH) != 0;
1296
1297                 if (lnors) {
1298                         /* Copy loop normals */
1299                         for (j = 0; j < mpoly->totloop; j++, start += 4) {
1300                                 normal_float_to_short_v3(&varray[start], lnors[mpoly->loopstart + j]);
1301                         }
1302                 }
1303                 else if (smoothnormal) {
1304                         /* Copy vertex normal */
1305                         for (j = 0; j < mpoly->totloop; j++, start += 4) {
1306                                 copy_v3_v3_short(&varray[start], mvert[mloop[mpoly->loopstart + j].v].no);
1307                         }
1308                 }
1309                 else {
1310                         /* Copy cached OR calculated face normal */
1311                         short f_no_s[3];
1312
1313                         if (nors) {
1314                                 normal_float_to_short_v3(f_no_s, nors[i]);
1315                         }
1316                         else {
1317                                 float f_no[3];
1318                                 BKE_mesh_calc_poly_normal(mpoly, &mloop[mpoly->loopstart], mvert, f_no);
1319                                 normal_float_to_short_v3(f_no_s, f_no);
1320                         }
1321
1322                         for (j = 0; j < mpoly->totloop; j++, start += 4) {
1323                                 copy_v3_v3_short(&varray[start], f_no_s);
1324                         }
1325                 }
1326         }
1327 }
1328
1329 static void cdDM_buffer_copy_uv(
1330         DerivedMesh *dm, float *varray)
1331 {
1332         int i, j, totpoly;
1333         int start;
1334
1335         const MPoly *mpoly;
1336         const MLoopUV *mloopuv;
1337
1338         if ((mloopuv = DM_get_loop_data_layer(dm, CD_MLOOPUV)) == NULL) {
1339                 return;
1340         }
1341
1342         mpoly = dm->getPolyArray(dm);
1343         totpoly = dm->getNumPolys(dm);
1344
1345         start = 0;
1346         for (i = 0; i < totpoly; i++, mpoly++) {
1347                 for (j = 0; j < mpoly->totloop; j++) {
1348                         copy_v2_v2(&varray[start], mloopuv[mpoly->loopstart + j].uv);
1349                         start += 2;
1350                 }
1351         }
1352 }
1353
1354 static void cdDM_buffer_copy_uv_texpaint(
1355         DerivedMesh *dm, float *varray)
1356 {
1357         int i, j, totpoly;
1358         int start;
1359
1360         const MPoly *mpoly;
1361
1362         int totmaterial = dm->totmat;
1363         const MLoopUV **uv_base;
1364         const MLoopUV  *uv_stencil_base;
1365         int stencil;
1366
1367         totpoly = dm->getNumPolys(dm);
1368
1369         /* should have been checked for before, reassert */
1370         BLI_assert(DM_get_loop_data_layer(dm, CD_MLOOPUV));
1371         uv_base = MEM_malloc_arrayN(totmaterial, sizeof(*uv_base), "texslots");
1372
1373         for (i = 0; i < totmaterial; i++) {
1374                 uv_base[i] = DM_paint_uvlayer_active_get(dm, i);
1375         }
1376
1377         stencil = CustomData_get_stencil_layer(&dm->loopData, CD_MLOOPUV);
1378         uv_stencil_base = CustomData_get_layer_n(&dm->loopData, CD_MLOOPUV, stencil);
1379
1380         mpoly = dm->getPolyArray(dm);
1381         start = 0;
1382
1383         for (i = 0; i < totpoly; i++, mpoly++) {
1384                 int mat_i = mpoly->mat_nr;
1385
1386                 for (j = 0; j < mpoly->totloop; j++) {
1387                         copy_v2_v2(&varray[start], uv_base[mat_i][mpoly->loopstart + j].uv);
1388                         copy_v2_v2(&varray[start + 2], uv_stencil_base[mpoly->loopstart + j].uv);
1389                         start += 4;
1390                 }
1391         }
1392
1393         MEM_freeN((void *)uv_base);
1394 }
1395
1396 /* treat varray_ as an array of MCol, four MCol's per face */
1397 static void cdDM_buffer_copy_mcol(
1398         DerivedMesh *dm, unsigned char *varray,
1399         const void *user_data)
1400 {
1401         int i, j, totpoly;
1402         int start;
1403
1404         const MLoopCol *mloopcol = user_data;
1405         const MPoly *mpoly = dm->getPolyArray(dm);
1406
1407         totpoly = dm->getNumPolys(dm);
1408
1409         start = 0;
1410
1411         for (i = 0; i < totpoly; i++, mpoly++) {
1412                 for (j = 0; j < mpoly->totloop; j++) {
1413                         copy_v4_v4_uchar(&varray[start], &mloopcol[mpoly->loopstart + j].r);
1414                         start += 4;
1415                 }
1416         }
1417 }
1418
1419 static void cdDM_buffer_copy_edge(
1420         DerivedMesh *dm, unsigned int *varray)
1421 {
1422         MEdge *medge, *medge_base;
1423         int i, totedge, iloose, inorm, iloosehidden, inormhidden;
1424         int tot_loose_hidden = 0, tot_loose = 0;
1425         int tot_hidden = 0, tot = 0;
1426
1427         medge_base = medge = dm->getEdgeArray(dm);
1428         totedge = dm->getNumEdges(dm);
1429
1430         for (i = 0; i < totedge; i++, medge++) {
1431                 if (medge->flag & ME_EDGEDRAW) {
1432                         if (medge->flag & ME_LOOSEEDGE) tot_loose++;
1433                         else tot++;
1434                 }
1435                 else {
1436                         if (medge->flag & ME_LOOSEEDGE) tot_loose_hidden++;
1437                         else tot_hidden++;
1438                 }
1439         }
1440
1441         inorm = 0;
1442         inormhidden = tot;
1443         iloose = tot + tot_hidden;
1444         iloosehidden = iloose + tot_loose;
1445
1446         medge = medge_base;
1447         for (i = 0; i < totedge; i++, medge++) {
1448                 if (medge->flag & ME_EDGEDRAW) {
1449                         if (medge->flag & ME_LOOSEEDGE) {
1450                                 varray[iloose * 2] = dm->drawObject->vert_points[medge->v1].point_index;
1451                                 varray[iloose * 2 + 1] = dm->drawObject->vert_points[medge->v2].point_index;
1452                                 iloose++;
1453                         }
1454                         else {
1455                                 varray[inorm * 2] = dm->drawObject->vert_points[medge->v1].point_index;
1456                                 varray[inorm * 2 + 1] = dm->drawObject->vert_points[medge->v2].point_index;
1457                                 inorm++;
1458                         }
1459                 }
1460                 else {
1461                         if (medge->flag & ME_LOOSEEDGE) {
1462                                 varray[iloosehidden * 2] = dm->drawObject->vert_points[medge->v1].point_index;
1463                                 varray[iloosehidden * 2 + 1] = dm->drawObject->vert_points[medge->v2].point_index;
1464                                 iloosehidden++;
1465                         }
1466                         else {
1467                                 varray[inormhidden * 2] = dm->drawObject->vert_points[medge->v1].point_index;
1468                                 varray[inormhidden * 2 + 1] = dm->drawObject->vert_points[medge->v2].point_index;
1469                                 inormhidden++;
1470                         }
1471                 }
1472         }
1473
1474         dm->drawObject->tot_loose_edge_drawn = tot_loose;
1475         dm->drawObject->loose_edge_offset = tot + tot_hidden;
1476         dm->drawObject->tot_edge_drawn = tot;
1477 }
1478
1479 static void cdDM_buffer_copy_uvedge(
1480         DerivedMesh *dm, float *varray)
1481 {
1482         int i, j, totpoly;
1483         int start;
1484         const MLoopUV *mloopuv;
1485         const MPoly *mpoly = dm->getPolyArray(dm);
1486
1487         if ((mloopuv = DM_get_loop_data_layer(dm, CD_MLOOPUV)) == NULL) {
1488                 return;
1489         }
1490
1491         totpoly = dm->getNumPolys(dm);
1492         start = 0;
1493
1494         for (i = 0; i < totpoly; i++, mpoly++) {
1495                 for (j = 0; j < mpoly->totloop; j++) {
1496                         copy_v2_v2(&varray[start], mloopuv[mpoly->loopstart + j].uv);
1497                         copy_v2_v2(&varray[start + 2], mloopuv[mpoly->loopstart + (j + 1) % mpoly->totloop].uv);
1498                         start += 4;
1499                 }
1500         }
1501 }
1502
1503 static void cdDM_copy_gpu_data(
1504         DerivedMesh *dm, int type, void *varray_p,
1505         const int *mat_orig_to_new, const void *user_data)
1506 {
1507         /* 'varray_p' cast is redundant but include for self-documentation */
1508         switch (type) {
1509                 case GPU_BUFFER_VERTEX:
1510                         cdDM_buffer_copy_vertex(dm, (float *)varray_p);
1511                         break;
1512                 case GPU_BUFFER_NORMAL:
1513                         cdDM_buffer_copy_normal(dm, (short *)varray_p);
1514                         break;
1515                 case GPU_BUFFER_COLOR:
1516                         cdDM_buffer_copy_mcol(dm, (unsigned char *)varray_p, user_data);
1517                         break;
1518                 case GPU_BUFFER_UV:
1519                         cdDM_buffer_copy_uv(dm, (float *)varray_p);
1520                         break;
1521                 case GPU_BUFFER_UV_TEXPAINT:
1522                         cdDM_buffer_copy_uv_texpaint(dm, (float *)varray_p);
1523                         break;
1524                 case GPU_BUFFER_EDGE:
1525                         cdDM_buffer_copy_edge(dm, (unsigned int *)varray_p);
1526                         break;
1527                 case GPU_BUFFER_UVEDGE:
1528                         cdDM_buffer_copy_uvedge(dm, (float *)varray_p);
1529                         break;
1530                 case GPU_BUFFER_TRIANGLES:
1531                         cdDM_buffer_copy_triangles(dm, (unsigned int *)varray_p, mat_orig_to_new);
1532                         break;
1533                 default:
1534                         break;
1535         }
1536 }
1537
1538 /* add a new point to the list of points related to a particular
1539  * vertex */
1540 #ifdef USE_GPU_POINT_LINK
1541
1542 static void cdDM_drawobject_add_vert_point(GPUDrawObject *gdo, int vert_index, int point_index)
1543 {
1544         GPUVertPointLink *lnk;
1545
1546         lnk = &gdo->vert_points[vert_index];
1547
1548         /* if first link is in use, add a new link at the end */
1549         if (lnk->point_index != -1) {
1550                 /* get last link */
1551                 for (; lnk->next; lnk = lnk->next) ;
1552
1553                 /* add a new link from the pool */
1554                 lnk = lnk->next = &gdo->vert_points_mem[gdo->vert_points_usage];
1555                 gdo->vert_points_usage++;
1556         }
1557
1558         lnk->point_index = point_index;
1559 }
1560
1561 #else
1562
1563 static void cdDM_drawobject_add_vert_point(GPUDrawObject *gdo, int vert_index, int point_index)
1564 {
1565         GPUVertPointLink *lnk;
1566         lnk = &gdo->vert_points[vert_index];
1567         if (lnk->point_index == -1) {
1568                 lnk->point_index = point_index;
1569         }
1570 }
1571
1572 #endif  /* USE_GPU_POINT_LINK */
1573
1574 /* for each vertex, build a list of points related to it; these lists
1575  * are stored in an array sized to the number of vertices */
1576 static void cdDM_drawobject_init_vert_points(
1577         GPUDrawObject *gdo,
1578         const MPoly *mpoly, const MLoop *mloop,
1579         int tot_poly)
1580 {
1581         int i;
1582         int tot_loops = 0;
1583
1584         /* allocate the array and space for links */
1585         gdo->vert_points = MEM_malloc_arrayN(gdo->totvert, sizeof(GPUVertPointLink),
1586                                        "GPUDrawObject.vert_points");
1587 #ifdef USE_GPU_POINT_LINK
1588         gdo->vert_points_mem = MEM_calloc_arrayN(gdo->totvert, sizeof(GPUVertPointLink),
1589                                            "GPUDrawObject.vert_points_mem");
1590         gdo->vert_points_usage = 0;
1591 #endif
1592
1593         /* -1 indicates the link is not yet used */
1594         for (i = 0; i < gdo->totvert; i++) {
1595 #ifdef USE_GPU_POINT_LINK
1596                 gdo->vert_points[i].link = NULL;
1597 #endif
1598                 gdo->vert_points[i].point_index = -1;
1599         }
1600
1601         for (i = 0; i < tot_poly; i++) {
1602                 int j;
1603                 const MPoly *mp = &mpoly[i];
1604
1605                 /* assign unique indices to vertices of the mesh */
1606                 for (j = 0; j < mp->totloop; j++) {
1607                         cdDM_drawobject_add_vert_point(gdo, mloop[mp->loopstart + j].v, tot_loops + j);
1608                 }
1609                 tot_loops += mp->totloop;
1610         }
1611
1612         /* map any unused vertices to loose points */
1613         for (i = 0; i < gdo->totvert; i++) {
1614                 if (gdo->vert_points[i].point_index == -1) {
1615                         gdo->vert_points[i].point_index = gdo->tot_loop_verts + gdo->tot_loose_point;
1616                         gdo->tot_loose_point++;
1617                 }
1618         }
1619 }
1620
1621 /* see GPUDrawObject's structure definition for a description of the
1622  * data being initialized here */
1623 static GPUDrawObject *cdDM_GPUobject_new(DerivedMesh *dm)
1624 {
1625         GPUDrawObject *gdo;
1626         const MPoly *mpoly;
1627         const MLoop *mloop;
1628         const short dm_totmat = dm->totmat;
1629         GPUBufferMaterial *mat_info;
1630         int i, totloops, totpolys;
1631
1632         /* object contains at least one material (default included) so zero means uninitialized dm */
1633         BLI_assert(dm_totmat != 0);
1634
1635         mpoly = dm->getPolyArray(dm);
1636         mloop = dm->getLoopArray(dm);
1637
1638         totpolys = dm->getNumPolys(dm);
1639         totloops = dm->getNumLoops(dm);
1640
1641         /* get the number of points used by each material, treating
1642          * each quad as two triangles */
1643         mat_info = MEM_calloc_arrayN(dm_totmat, sizeof(*mat_info), "GPU_drawobject_new.mat_orig_to_new");
1644
1645         for (i = 0; i < totpolys; i++) {
1646                 const short mat_nr = ME_MAT_NR_TEST(mpoly[i].mat_nr, dm_totmat);
1647                 mat_info[mat_nr].totpolys++;
1648                 mat_info[mat_nr].totelements += 3 * ME_POLY_TRI_TOT(&mpoly[i]);
1649                 mat_info[mat_nr].totloops += mpoly[i].totloop;
1650         }
1651         /* create the GPUDrawObject */
1652         gdo = MEM_callocN(sizeof(GPUDrawObject), "GPUDrawObject");
1653         gdo->totvert = dm->getNumVerts(dm);
1654         gdo->totedge = dm->getNumEdges(dm);
1655
1656         GPU_buffer_material_finalize(gdo, mat_info, dm_totmat);
1657
1658         gdo->tot_loop_verts = totloops;
1659
1660         /* store total number of points used for triangles */
1661         gdo->tot_triangle_point = poly_to_tri_count(totpolys, totloops) * 3;
1662
1663         cdDM_drawobject_init_vert_points(gdo, mpoly, mloop, totpolys);
1664
1665         return gdo;
1666 }
1667
1668 static void cdDM_foreachMappedVert(
1669         DerivedMesh *dm,
1670         void (*func)(void *userData, int index, const float co[3], const float no_f[3], const short no_s[3]),
1671         void *userData,
1672         DMForeachFlag flag)
1673 {
1674         MVert *mv = CDDM_get_verts(dm);
1675         const int *index = DM_get_vert_data_layer(dm, CD_ORIGINDEX);
1676         int i;
1677
1678         if (index) {
1679                 for (i = 0; i < dm->numVertData; i++, mv++) {
1680                         const short *no = (flag & DM_FOREACH_USE_NORMAL) ? mv->no : NULL;
1681                         const int orig = *index++;
1682                         if (orig == ORIGINDEX_NONE) continue;
1683                         func(userData, orig, mv->co, NULL, no);
1684                 }
1685         }
1686         else {
1687                 for (i = 0; i < dm->numVertData; i++, mv++) {
1688                         const short *no = (flag & DM_FOREACH_USE_NORMAL) ? mv->no : NULL;
1689                         func(userData, i, mv->co, NULL, no);
1690                 }
1691         }
1692 }
1693
1694 static void cdDM_foreachMappedEdge(
1695         DerivedMesh *dm,
1696         void (*func)(void *userData, int index, const float v0co[3], const float v1co[3]),
1697         void *userData)
1698 {
1699         CDDerivedMesh *cddm = (CDDerivedMesh *) dm;
1700         MVert *mv = cddm->mvert;
1701         MEdge *med = cddm->medge;
1702         int i, orig, *index = DM_get_edge_data_layer(dm, CD_ORIGINDEX);
1703
1704         for (i = 0; i < dm->numEdgeData; i++, med++) {
1705                 if (index) {
1706                         orig = *index++;
1707                         if (orig == ORIGINDEX_NONE) continue;
1708                         func(userData, orig, mv[med->v1].co, mv[med->v2].co);
1709                 }
1710                 else
1711                         func(userData, i, mv[med->v1].co, mv[med->v2].co);
1712         }
1713 }
1714
1715 static void cdDM_foreachMappedLoop(
1716         DerivedMesh *dm,
1717         void (*func)(void *userData, int vertex_index, int face_index, const float co[3], const float no[3]),
1718         void *userData,
1719         DMForeachFlag flag)
1720 {
1721         /* We can't use dm->getLoopDataLayout(dm) here, we want to always access dm->loopData, EditDerivedBMesh would
1722          * return loop data from bmesh itself. */
1723         const float (*lnors)[3] = (flag & DM_FOREACH_USE_NORMAL) ? DM_get_loop_data_layer(dm, CD_NORMAL) : NULL;
1724
1725         const MVert *mv = CDDM_get_verts(dm);
1726         const MLoop *ml = CDDM_get_loops(dm);
1727         const MPoly *mp = CDDM_get_polys(dm);
1728         const int *v_index = DM_get_vert_data_layer(dm, CD_ORIGINDEX);
1729         const int *f_index = DM_get_poly_data_layer(dm, CD_ORIGINDEX);
1730         int p_idx, i;
1731
1732         for (p_idx = 0; p_idx < dm->numPolyData; ++p_idx, ++mp) {
1733                 for (i = 0; i < mp->totloop; ++i, ++ml) {
1734                         const int v_idx = v_index ? v_index[ml->v] : ml->v;
1735                         const int f_idx = f_index ? f_index[p_idx] : p_idx;
1736                         const float *no = lnors ? *lnors++ : NULL;
1737                         if (!ELEM(ORIGINDEX_NONE, v_idx, f_idx)) {
1738                                 func(userData, v_idx, f_idx, mv[ml->v].co, no);
1739                         }
1740                 }
1741         }
1742 }
1743
1744 static void cdDM_foreachMappedFaceCenter(
1745         DerivedMesh *dm,
1746         void (*func)(void *userData, int index, const float cent[3], const float no[3]),
1747         void *userData,
1748         DMForeachFlag flag)
1749 {
1750         CDDerivedMesh *cddm = (CDDerivedMesh *)dm;
1751         MVert *mvert = cddm->mvert;
1752         MPoly *mp;
1753         MLoop *ml;
1754         int i, orig, *index;
1755
1756         index = CustomData_get_layer(&dm->polyData, CD_ORIGINDEX);
1757         mp = cddm->mpoly;
1758         for (i = 0; i < dm->numPolyData; i++, mp++) {
1759                 float cent[3];
1760                 float *no, _no[3];
1761
1762                 if (index) {
1763                         orig = *index++;
1764                         if (orig == ORIGINDEX_NONE) continue;
1765                 }
1766                 else {
1767                         orig = i;
1768                 }
1769                 
1770                 ml = &cddm->mloop[mp->loopstart];
1771                 BKE_mesh_calc_poly_center(mp, ml, mvert, cent);
1772
1773                 if (flag & DM_FOREACH_USE_NORMAL) {
1774                         BKE_mesh_calc_poly_normal(mp, ml, mvert, (no = _no));
1775                 }
1776                 else {
1777                         no = NULL;
1778                 }
1779
1780                 func(userData, orig, cent, no);
1781         }
1782
1783 }
1784
1785 void CDDM_recalc_tessellation_ex(DerivedMesh *dm, const bool do_face_nor_cpy)
1786 {
1787         CDDerivedMesh *cddm = (CDDerivedMesh *)dm;
1788
1789         dm->numTessFaceData = BKE_mesh_recalc_tessellation(
1790                 &dm->faceData, &dm->loopData, &dm->polyData,
1791                 cddm->mvert,
1792                 dm->numTessFaceData, dm->numLoopData, dm->numPolyData,
1793                 do_face_nor_cpy);
1794
1795         cddm->mface = CustomData_get_layer(&dm->faceData, CD_MFACE);
1796
1797         /* Tessellation recreated faceData, and the active layer indices need to get re-propagated
1798          * from loops and polys to faces */
1799         CustomData_bmesh_update_active_layers(&dm->faceData, &dm->loopData);
1800 }
1801
1802 void CDDM_recalc_tessellation(DerivedMesh *dm)
1803 {
1804         CDDM_recalc_tessellation_ex(dm, true);
1805 }
1806
1807 void CDDM_recalc_looptri(DerivedMesh *dm)
1808 {
1809         CDDerivedMesh *cddm = (CDDerivedMesh *)dm;
1810         const unsigned int totpoly = dm->numPolyData;
1811         const unsigned int totloop = dm->numLoopData;
1812
1813         DM_ensure_looptri_data(dm);
1814         BLI_assert(totpoly == 0 || cddm->dm.looptris.array_wip != NULL);
1815
1816         BKE_mesh_recalc_looptri(
1817                 cddm->mloop, cddm->mpoly,
1818                 cddm->mvert,
1819                 totloop, totpoly,
1820                 cddm->dm.looptris.array_wip);
1821
1822         BLI_assert(cddm->dm.looptris.array == NULL);
1823         atomic_cas_ptr((void **)&cddm->dm.looptris.array, cddm->dm.looptris.array, cddm->dm.looptris.array_wip);
1824         cddm->dm.looptris.array_wip = NULL;
1825 }
1826
1827 static void cdDM_free_internal(CDDerivedMesh *cddm)
1828 {
1829         if (cddm->pmap) MEM_freeN(cddm->pmap);
1830         if (cddm->pmap_mem) MEM_freeN(cddm->pmap_mem);
1831 }
1832
1833 static void cdDM_release(DerivedMesh *dm)
1834 {
1835         CDDerivedMesh *cddm = (CDDerivedMesh *)dm;
1836
1837         if (DM_release(dm)) {
1838                 cdDM_free_internal(cddm);
1839                 MEM_freeN(cddm);
1840         }
1841 }
1842
1843 /**************** CDDM interface functions ****************/
1844 static CDDerivedMesh *cdDM_create(const char *desc)
1845 {
1846         CDDerivedMesh *cddm;
1847         DerivedMesh *dm;
1848
1849         cddm = MEM_callocN(sizeof(*cddm), desc);
1850         dm = &cddm->dm;
1851
1852         dm->getMinMax = cdDM_getMinMax;
1853
1854         dm->getNumVerts = cdDM_getNumVerts;
1855         dm->getNumEdges = cdDM_getNumEdges;
1856         dm->getNumTessFaces = cdDM_getNumTessFaces;
1857         dm->getNumLoops = cdDM_getNumLoops;
1858         dm->getNumPolys = cdDM_getNumPolys;
1859
1860         dm->getVert = cdDM_getVert;
1861         dm->getEdge = cdDM_getEdge;
1862         dm->getTessFace = cdDM_getTessFace;
1863
1864         dm->copyVertArray = cdDM_copyVertArray;
1865         dm->copyEdgeArray = cdDM_copyEdgeArray;
1866         dm->copyTessFaceArray = cdDM_copyTessFaceArray;
1867         dm->copyLoopArray = cdDM_copyLoopArray;
1868         dm->copyPolyArray = cdDM_copyPolyArray;
1869
1870         dm->getVertData = DM_get_vert_data;
1871         dm->getEdgeData = DM_get_edge_data;
1872         dm->getTessFaceData = DM_get_tessface_data;
1873         dm->getVertDataArray = DM_get_vert_data_layer;
1874         dm->getEdgeDataArray = DM_get_edge_data_layer;
1875         dm->getTessFaceDataArray = DM_get_tessface_data_layer;
1876
1877         dm->calcNormals = CDDM_calc_normals;
1878         dm->calcLoopNormals = CDDM_calc_loop_normals;
1879         dm->calcLoopNormalsSpaceArray = CDDM_calc_loop_normals_spacearr;
1880         dm->calcLoopTangents = DM_calc_loop_tangents;
1881         dm->recalcTessellation = CDDM_recalc_tessellation;
1882         dm->recalcLoopTri = CDDM_recalc_looptri;
1883
1884         dm->getVertCos = cdDM_getVertCos;
1885         dm->getVertCo = cdDM_getVertCo;
1886         dm->getVertNo = cdDM_getVertNo;
1887
1888         dm->getPBVH = cdDM_getPBVH;
1889         dm->getPolyMap = cdDM_getPolyMap;
1890
1891         dm->drawVerts = cdDM_drawVerts;
1892
1893         dm->drawEdges = cdDM_drawEdges;
1894         dm->drawLooseEdges = cdDM_drawLooseEdges;
1895         dm->drawMappedEdges = cdDM_drawMappedEdges;
1896
1897         dm->drawFacesSolid = cdDM_drawFacesSolid;
1898         dm->drawFacesGLSL = cdDM_drawFacesGLSL;
1899         dm->drawMappedFaces = cdDM_drawMappedFaces;
1900         dm->drawMappedFacesGLSL = cdDM_drawMappedFacesGLSL;
1901         dm->drawMappedFacesMat = cdDM_drawMappedFacesMat;
1902
1903         dm->gpuObjectNew = cdDM_GPUobject_new;
1904         dm->copy_gpu_data = cdDM_copy_gpu_data;
1905
1906         dm->foreachMappedVert = cdDM_foreachMappedVert;
1907         dm->foreachMappedEdge = cdDM_foreachMappedEdge;
1908         dm->foreachMappedLoop = cdDM_foreachMappedLoop;
1909         dm->foreachMappedFaceCenter = cdDM_foreachMappedFaceCenter;
1910
1911         dm->release = cdDM_release;
1912
1913         return cddm;
1914 }
1915
1916 DerivedMesh *CDDM_new(int numVerts, int numEdges, int numTessFaces, int numLoops, int numPolys)
1917 {
1918         CDDerivedMesh *cddm = cdDM_create("CDDM_new dm");
1919         DerivedMesh *dm = &cddm->dm;
1920
1921         DM_init(dm, DM_TYPE_CDDM, numVerts, numEdges, numTessFaces, numLoops, numPolys);
1922
1923         CustomData_add_layer(&dm->vertData, CD_ORIGINDEX, CD_CALLOC, NULL, numVerts);
1924         CustomData_add_layer(&dm->edgeData, CD_ORIGINDEX, CD_CALLOC, NULL, numEdges);
1925         CustomData_add_layer(&dm->faceData, CD_ORIGINDEX, CD_CALLOC, NULL, numTessFaces);
1926         CustomData_add_layer(&dm->polyData, CD_ORIGINDEX, CD_CALLOC, NULL, numPolys);
1927
1928         CustomData_add_layer(&dm->vertData, CD_MVERT, CD_CALLOC, NULL, numVerts);
1929         CustomData_add_layer(&dm->edgeData, CD_MEDGE, CD_CALLOC, NULL, numEdges);
1930         CustomData_add_layer(&dm->faceData, CD_MFACE, CD_CALLOC, NULL, numTessFaces);
1931         CustomData_add_layer(&dm->loopData, CD_MLOOP, CD_CALLOC, NULL, numLoops);
1932         CustomData_add_layer(&dm->polyData, CD_MPOLY, CD_CALLOC, NULL, numPolys);
1933
1934         cddm->mvert = CustomData_get_layer(&dm->vertData, CD_MVERT);
1935         cddm->medge = CustomData_get_layer(&dm->edgeData, CD_MEDGE);
1936         cddm->mface = CustomData_get_layer(&dm->faceData, CD_MFACE);
1937         cddm->mloop = CustomData_get_layer(&dm->loopData, CD_MLOOP);
1938         cddm->mpoly = CustomData_get_layer(&dm->polyData, CD_MPOLY);
1939
1940         return dm;
1941 }
1942
1943 DerivedMesh *CDDM_from_mesh(Mesh *mesh)
1944 {
1945         CDDerivedMesh *cddm = cdDM_create(__func__);
1946         DerivedMesh *dm = &cddm->dm;
1947         CustomDataMask mask = CD_MASK_MESH & (~CD_MASK_MDISPS);
1948         int alloctype;
1949
1950         /* this does a referenced copy, with an exception for fluidsim */
1951
1952         DM_init(dm, DM_TYPE_CDDM, mesh->totvert, mesh->totedge, 0 /* mesh->totface */,
1953                 mesh->totloop, mesh->totpoly);
1954
1955         dm->deformedOnly = 1;
1956         dm->cd_flag = mesh->cd_flag;
1957
1958         alloctype = CD_REFERENCE;
1959
1960         CustomData_merge(&mesh->vdata, &dm->vertData, mask, alloctype,
1961                          mesh->totvert);
1962         CustomData_merge(&mesh->edata, &dm->edgeData, mask, alloctype,
1963                          mesh->totedge);
1964         CustomData_merge(&mesh->fdata, &dm->faceData, mask | CD_MASK_ORIGINDEX, alloctype,
1965                          0 /* mesh->totface */);
1966         CustomData_merge(&mesh->ldata, &dm->loopData, mask, alloctype,
1967                          mesh->totloop);
1968         CustomData_merge(&mesh->pdata, &dm->polyData, mask, alloctype,
1969                          mesh->totpoly);
1970
1971         cddm->mvert = CustomData_get_layer(&dm->vertData, CD_MVERT);
1972         cddm->medge = CustomData_get_layer(&dm->edgeData, CD_MEDGE);
1973         cddm->mloop = CustomData_get_layer(&dm->loopData, CD_MLOOP);
1974         cddm->mpoly = CustomData_get_layer(&dm->polyData, CD_MPOLY);
1975 #if 0
1976         cddm->mface = CustomData_get_layer(&dm->faceData, CD_MFACE);
1977 #else
1978         cddm->mface = NULL;
1979 #endif
1980
1981         /* commented since even when CD_ORIGINDEX was first added this line fails
1982          * on the default cube, (after editmode toggle too) - campbell */
1983 #if 0
1984         BLI_assert(CustomData_has_layer(&cddm->dm.faceData, CD_ORIGINDEX));
1985 #endif
1986
1987         return dm;
1988 }
1989
1990 DerivedMesh *CDDM_from_curve(Object *ob)
1991 {
1992         ListBase disp = {NULL, NULL};
1993
1994         if (ob->curve_cache) {
1995                 disp = ob->curve_cache->disp;
1996         }
1997
1998         return CDDM_from_curve_displist(ob, &disp);
1999 }
2000
2001 DerivedMesh *CDDM_from_curve_displist(Object *ob, ListBase *dispbase)
2002 {
2003         Curve *cu = (Curve *) ob->data;
2004         DerivedMesh *dm;
2005         CDDerivedMesh *cddm;
2006         MVert *allvert;
2007         MEdge *alledge;
2008         MLoop *allloop;
2009         MPoly *allpoly;
2010         MLoopUV *alluv = NULL;
2011         int totvert, totedge, totloop, totpoly;
2012         bool use_orco_uv = (cu->flag & CU_UV_ORCO) != 0;
2013
2014         if (BKE_mesh_nurbs_displist_to_mdata(
2015                 ob, dispbase, &allvert, &totvert, &alledge,
2016                 &totedge, &allloop, &allpoly, (use_orco_uv) ? &alluv : NULL,
2017                 &totloop, &totpoly) != 0)
2018         {
2019                 /* Error initializing mdata. This often happens when curve is empty */
2020                 return CDDM_new(0, 0, 0, 0, 0);
2021         }
2022
2023         dm = CDDM_new(totvert, totedge, 0, totloop, totpoly);
2024         dm->deformedOnly = 1;
2025         dm->dirty |= DM_DIRTY_NORMALS;
2026
2027         cddm = (CDDerivedMesh *)dm;
2028
2029         memcpy(cddm->mvert, allvert, totvert * sizeof(MVert));
2030         memcpy(cddm->medge, alledge, totedge * sizeof(MEdge));
2031         memcpy(cddm->mloop, allloop, totloop * sizeof(MLoop));
2032         memcpy(cddm->mpoly, allpoly, totpoly * sizeof(MPoly));
2033
2034         if (alluv) {
2035                 const char *uvname = "Orco";
2036                 CustomData_add_layer_named(&cddm->dm.loopData, CD_MLOOPUV, CD_ASSIGN, alluv, totloop, uvname);
2037         }
2038
2039         MEM_freeN(allvert);
2040         MEM_freeN(alledge);
2041         MEM_freeN(allloop);
2042         MEM_freeN(allpoly);
2043
2044         return dm;
2045 }
2046
2047 static void loops_to_customdata_corners(
2048         BMesh *bm, CustomData *facedata,
2049         int cdindex, const BMLoop *l3[3],
2050         int numCol, int numUV)
2051 {
2052         const BMLoop *l;
2053 //      BMFace *f = l3[0]->f;
2054         MTFace *texface;
2055         MCol *mcol;
2056         MLoopCol *mloopcol;
2057         MLoopUV *mloopuv;
2058         int i, j, hasPCol = CustomData_has_layer(&bm->ldata, CD_PREVIEW_MLOOPCOL);
2059
2060         for (i = 0; i < numUV; i++) {
2061                 texface = CustomData_get_n(facedata, CD_MTFACE, cdindex, i);
2062         
2063                 for (j = 0; j < 3; j++) {
2064                         l = l3[j];
2065                         mloopuv = CustomData_bmesh_get_n(&bm->ldata, l->head.data, CD_MLOOPUV, i);
2066                         copy_v2_v2(texface->uv[j], mloopuv->uv);
2067                 }
2068         }
2069
2070         for (i = 0; i < numCol; i++) {
2071                 mcol = CustomData_get_n(facedata, CD_MCOL, cdindex, i);
2072                 
2073                 for (j = 0; j < 3; j++) {
2074                         l = l3[j];
2075                         mloopcol = CustomData_bmesh_get_n(&bm->ldata, l->head.data, CD_MLOOPCOL, i);
2076                         MESH_MLOOPCOL_TO_MCOL(mloopcol, &mcol[j]);
2077                 }
2078         }
2079
2080         if (hasPCol) {
2081                 mcol = CustomData_get(facedata, cdindex, CD_PREVIEW_MCOL);
2082
2083                 for (j = 0; j < 3; j++) {
2084                         l = l3[j];
2085                         mloopcol = CustomData_bmesh_get(&bm->ldata, l->head.data, CD_PREVIEW_MLOOPCOL);
2086                         MESH_MLOOPCOL_TO_MCOL(mloopcol, &mcol[j]);
2087                 }
2088         }
2089 }
2090
2091 /* used for both editbmesh and bmesh */
2092 static DerivedMesh *cddm_from_bmesh_ex(
2093         struct BMesh *bm, const bool use_mdisps,
2094         /* EditBMesh vars for use_tessface */
2095         const bool use_tessface,
2096         const int em_tottri, const BMLoop *(*em_looptris)[3])
2097 {
2098         DerivedMesh *dm = CDDM_new(bm->totvert,
2099                                    bm->totedge,
2100                                    use_tessface ? em_tottri : 0,
2101                                    bm->totloop,
2102                                    bm->totface);
2103
2104         CDDerivedMesh *cddm = (CDDerivedMesh *)dm;
2105         BMIter iter;
2106         BMVert *eve;
2107         BMEdge *eed;
2108         BMFace *efa;
2109         MVert *mvert = cddm->mvert;
2110         MEdge *medge = cddm->medge;
2111         MFace *mface = cddm->mface;
2112         MLoop *mloop = cddm->mloop;
2113         MPoly *mpoly = cddm->mpoly;
2114         int numCol = CustomData_number_of_layers(&bm->ldata, CD_MLOOPCOL);
2115         int numUV  = CustomData_number_of_layers(&bm->ldata, CD_MLOOPUV);
2116         int *index, add_orig;
2117         CustomDataMask mask;
2118         unsigned int i, j;
2119         
2120         const int cd_vert_bweight_offset = CustomData_get_offset(&bm->vdata, CD_BWEIGHT);
2121         const int cd_edge_bweight_offset = CustomData_get_offset(&bm->edata, CD_BWEIGHT);
2122         const int cd_edge_crease_offset  = CustomData_get_offset(&bm->edata, CD_CREASE);
2123         
2124         dm->deformedOnly = 1;
2125         
2126         /* don't add origindex layer if one already exists */
2127         add_orig = !CustomData_has_layer(&bm->pdata, CD_ORIGINDEX);
2128
2129         mask = use_mdisps ? CD_MASK_DERIVEDMESH | CD_MASK_MDISPS : CD_MASK_DERIVEDMESH;
2130         
2131         /* don't process shapekeys, we only feed them through the modifier stack as needed,
2132          * e.g. for applying modifiers or the like*/
2133         mask &= ~CD_MASK_SHAPEKEY;
2134         CustomData_merge(&bm->vdata, &dm->vertData, mask,
2135                          CD_CALLOC, dm->numVertData);
2136         CustomData_merge(&bm->edata, &dm->edgeData, mask,
2137                          CD_CALLOC, dm->numEdgeData);
2138         CustomData_merge(&bm->ldata, &dm->loopData, mask,
2139                          CD_CALLOC, dm->numLoopData);
2140         CustomData_merge(&bm->pdata, &dm->polyData, mask,
2141                          CD_CALLOC, dm->numPolyData);
2142
2143         /* add tessellation mface layers */
2144         if (use_tessface) {
2145                 CustomData_from_bmeshpoly(&dm->faceData, &dm->loopData, em_tottri);
2146         }
2147
2148         index = dm->getVertDataArray(dm, CD_ORIGINDEX);
2149
2150         BM_ITER_MESH_INDEX (eve, &iter, bm, BM_VERTS_OF_MESH, i) {
2151                 MVert *mv = &mvert[i];
2152
2153                 copy_v3_v3(mv->co, eve->co);
2154
2155                 BM_elem_index_set(eve, i); /* set_inline */
2156
2157                 normal_float_to_short_v3(mv->no, eve->no);
2158
2159                 mv->flag = BM_vert_flag_to_mflag(eve);
2160
2161                 if (cd_vert_bweight_offset != -1) mv->bweight = BM_ELEM_CD_GET_FLOAT_AS_UCHAR(eve, cd_vert_bweight_offset);
2162
2163                 if (add_orig) *index++ = i;
2164
2165                 CustomData_from_bmesh_block(&bm->vdata, &dm->vertData, eve->head.data, i);
2166         }
2167         bm->elem_index_dirty &= ~BM_VERT;
2168
2169         index = dm->getEdgeDataArray(dm, CD_ORIGINDEX);
2170         BM_ITER_MESH_INDEX (eed, &iter, bm, BM_EDGES_OF_MESH, i) {
2171                 MEdge *med = &medge[i];
2172
2173                 BM_elem_index_set(eed, i); /* set_inline */
2174
2175                 med->v1 = BM_elem_index_get(eed->v1);
2176                 med->v2 = BM_elem_index_get(eed->v2);
2177
2178                 med->flag = BM_edge_flag_to_mflag(eed);
2179
2180                 /* handle this differently to editmode switching,
2181                  * only enable draw for single user edges rather then calculating angle */
2182                 if ((med->flag & ME_EDGEDRAW) == 0) {
2183                         if (eed->l && eed->l == eed->l->radial_next) {
2184                                 med->flag |= ME_EDGEDRAW;
2185                         }
2186                 }
2187
2188                 if (cd_edge_crease_offset  != -1) med->crease  = BM_ELEM_CD_GET_FLOAT_AS_UCHAR(eed, cd_edge_crease_offset);
2189                 if (cd_edge_bweight_offset != -1) med->bweight = BM_ELEM_CD_GET_FLOAT_AS_UCHAR(eed, cd_edge_bweight_offset);
2190
2191                 CustomData_from_bmesh_block(&bm->edata, &dm->edgeData, eed->head.data, i);
2192                 if (add_orig) *index++ = i;
2193         }
2194         bm->elem_index_dirty &= ~BM_EDGE;
2195
2196         /* avoid this where possiblem, takes extra memory */
2197         if (use_tessface) {
2198
2199                 BM_mesh_elem_index_ensure(bm, BM_FACE);
2200
2201                 index = dm->getTessFaceDataArray(dm, CD_ORIGINDEX);
2202                 for (i = 0; i < dm->numTessFaceData; i++) {
2203                         MFace *mf = &mface[i];
2204                         const BMLoop **l = em_looptris[i];
2205                         efa = l[0]->f;
2206
2207                         mf->v1 = BM_elem_index_get(l[0]->v);
2208                         mf->v2 = BM_elem_index_get(l[1]->v);
2209                         mf->v3 = BM_elem_index_get(l[2]->v);
2210                         mf->v4 = 0;
2211                         mf->mat_nr = efa->mat_nr;
2212                         mf->flag = BM_face_flag_to_mflag(efa);
2213
2214                         /* map mfaces to polygons in the same cddm intentionally */
2215                         *index++ = BM_elem_index_get(efa);
2216
2217                         loops_to_customdata_corners(bm, &dm->faceData, i, l, numCol, numUV);
2218                         test_index_face(mf, &dm->faceData, i, 3);
2219                 }
2220         }
2221         
2222         index = CustomData_get_layer(&dm->polyData, CD_ORIGINDEX);
2223         j = 0;
2224         BM_ITER_MESH_INDEX (efa, &iter, bm, BM_FACES_OF_MESH, i) {
2225                 BMLoop *l_iter;
2226                 BMLoop *l_first;
2227                 MPoly *mp = &mpoly[i];
2228
2229                 BM_elem_index_set(efa, i); /* set_inline */
2230
2231                 mp->totloop = efa->len;
2232                 mp->flag = BM_face_flag_to_mflag(efa);
2233                 mp->loopstart = j;
2234                 mp->mat_nr = efa->mat_nr;
2235
2236                 l_iter = l_first = BM_FACE_FIRST_LOOP(efa);
2237                 do {
2238                         mloop->v = BM_elem_index_get(l_iter->v);
2239                         mloop->e = BM_elem_index_get(l_iter->e);
2240                         CustomData_from_bmesh_block(&bm->ldata, &dm->loopData, l_iter->head.data, j);
2241
2242                         BM_elem_index_set(l_iter, j); /* set_inline */
2243
2244                         j++;
2245                         mloop++;
2246                 } while ((l_iter = l_iter->next) != l_first);
2247
2248                 CustomData_from_bmesh_block(&bm->pdata, &dm->polyData, efa->head.data, i);
2249
2250                 if (add_orig) *index++ = i;
2251         }
2252         bm->elem_index_dirty &= ~(BM_FACE | BM_LOOP);
2253
2254         dm->cd_flag = BM_mesh_cd_flag_from_bmesh(bm);
2255
2256         return dm;
2257 }
2258
2259 struct DerivedMesh *CDDM_from_bmesh(struct BMesh *bm, const bool use_mdisps)
2260 {
2261         return cddm_from_bmesh_ex(
2262                 bm, use_mdisps, false,
2263                 /* these vars are for editmesh only */
2264                 0, NULL);
2265 }
2266
2267 DerivedMesh *CDDM_from_editbmesh(BMEditMesh *em, const bool use_mdisps, const bool use_tessface)
2268 {
2269         return cddm_from_bmesh_ex(
2270                 em->bm, use_mdisps,
2271                 /* editmesh */
2272                 use_tessface, em->tottri, (const BMLoop *(*)[3])em->looptris);
2273 }
2274
2275 static DerivedMesh *cddm_copy_ex(DerivedMesh *source,
2276                                  const bool need_tessface_data,
2277                                  const bool faces_from_tessfaces)
2278 {
2279         const bool copy_tessface_data = (faces_from_tessfaces || need_tessface_data);
2280         CDDerivedMesh *cddm = cdDM_create("CDDM_copy cddm");
2281         DerivedMesh *dm = &cddm->dm;
2282         int numVerts = source->numVertData;
2283         int numEdges = source->numEdgeData;
2284         int numTessFaces = copy_tessface_data ? source->numTessFaceData : 0;
2285         int numLoops = source->numLoopData;
2286         int numPolys = source->numPolyData;
2287
2288         /* NOTE: Don't copy tessellation faces if not requested explicitly. */
2289
2290         /* ensure these are created if they are made on demand */
2291         source->getVertDataArray(source, CD_ORIGINDEX);
2292         source->getEdgeDataArray(source, CD_ORIGINDEX);
2293         source->getPolyDataArray(source, CD_ORIGINDEX);
2294         if (copy_tessface_data) {
2295                 source->getTessFaceDataArray(source, CD_ORIGINDEX);
2296         }
2297
2298         /* this initializes dm, and copies all non mvert/medge/mface layers */
2299         DM_from_template(dm, source, DM_TYPE_CDDM, numVerts, numEdges, numTessFaces,
2300                          numLoops, numPolys);
2301         dm->deformedOnly = source->deformedOnly;
2302         dm->cd_flag = source->cd_flag;
2303         dm->dirty = source->dirty;
2304
2305         /* Tessellation data is never copied, so tag it here.
2306          * Only tag dirty layers if we really ignored tessellation faces.
2307          */
2308         if (!copy_tessface_data) {
2309                 dm->dirty |= DM_DIRTY_TESS_CDLAYERS;
2310         }
2311
2312         CustomData_copy_data(&source->vertData, &dm->vertData, 0, 0, numVerts);
2313         CustomData_copy_data(&source->edgeData, &dm->edgeData, 0, 0, numEdges);
2314         if (copy_tessface_data) {
2315                 CustomData_copy_data(&source->faceData, &dm->faceData, 0, 0, numTessFaces);
2316         }
2317
2318         /* now add mvert/medge/mface layers */
2319         cddm->mvert = source->dupVertArray(source);
2320         cddm->medge = source->dupEdgeArray(source);
2321
2322         CustomData_add_layer(&dm->vertData, CD_MVERT, CD_ASSIGN, cddm->mvert, numVerts);
2323         CustomData_add_layer(&dm->edgeData, CD_MEDGE, CD_ASSIGN, cddm->medge, numEdges);
2324
2325         if (faces_from_tessfaces || copy_tessface_data) {
2326                 cddm->mface = source->dupTessFaceArray(source);
2327                 CustomData_add_layer(&dm->faceData, CD_MFACE, CD_ASSIGN, cddm->mface, numTessFaces);
2328         }
2329
2330         if (!faces_from_tessfaces) {
2331                 DM_DupPolys(source, dm);
2332         }
2333         else {
2334                 CDDM_tessfaces_to_faces(dm);
2335         }
2336
2337         cddm->mloop = CustomData_get_layer(&dm->loopData, CD_MLOOP);
2338         cddm->mpoly = CustomData_get_layer(&dm->polyData, CD_MPOLY);
2339
2340         return dm;
2341 }
2342
2343 DerivedMesh *CDDM_copy(DerivedMesh *source)
2344 {
2345         return cddm_copy_ex(source, false, false);
2346 }
2347
2348 DerivedMesh *CDDM_copy_from_tessface(DerivedMesh *source)
2349 {
2350         return cddm_copy_ex(source, false, true);
2351 }
2352
2353 DerivedMesh *CDDM_copy_with_tessface(DerivedMesh *source)
2354 {
2355         return cddm_copy_ex(source, true, false);
2356 }
2357
2358 /* note, the CD_ORIGINDEX layers are all 0, so if there is a direct
2359  * relationship between mesh data this needs to be set by the caller. */
2360 DerivedMesh *CDDM_from_template_ex(
2361         DerivedMesh *source,
2362         int numVerts, int numEdges, int numTessFaces,
2363         int numLoops, int numPolys,
2364         CustomDataMask mask)
2365 {
2366         CDDerivedMesh *cddm = cdDM_create("CDDM_from_template dest");
2367         DerivedMesh *dm = &cddm->dm;
2368
2369         /* ensure these are created if they are made on demand */
2370         source->getVertDataArray(source, CD_ORIGINDEX);
2371         source->getEdgeDataArray(source, CD_ORIGINDEX);
2372         source->getTessFaceDataArray(source, CD_ORIGINDEX);
2373         source->getPolyDataArray(source, CD_ORIGINDEX);
2374
2375         /* this does a copy of all non mvert/medge/mface layers */
2376         DM_from_template_ex(
2377                 dm, source, DM_TYPE_CDDM,
2378                 numVerts, numEdges, numTessFaces,
2379                 numLoops, numPolys,
2380                 mask);
2381
2382         /* now add mvert/medge/mface layers */
2383         CustomData_add_layer(&dm->vertData, CD_MVERT, CD_CALLOC, NULL, numVerts);
2384         CustomData_add_layer(&dm->edgeData, CD_MEDGE, CD_CALLOC, NULL, numEdges);
2385         CustomData_add_layer(&dm->faceData, CD_MFACE, CD_CALLOC, NULL, numTessFaces);
2386         CustomData_add_layer(&dm->loopData, CD_MLOOP, CD_CALLOC, NULL, numLoops);
2387         CustomData_add_layer(&dm->polyData, CD_MPOLY, CD_CALLOC, NULL, numPolys);
2388
2389         if (!CustomData_get_layer(&dm->vertData, CD_ORIGINDEX))
2390                 CustomData_add_layer(&dm->vertData, CD_ORIGINDEX, CD_CALLOC, NULL, numVerts);
2391         if (!CustomData_get_layer(&dm->edgeData, CD_ORIGINDEX))
2392                 CustomData_add_layer(&dm->edgeData, CD_ORIGINDEX, CD_CALLOC, NULL, numEdges);
2393         if (!CustomData_get_layer(&dm->faceData, CD_ORIGINDEX))
2394                 CustomData_add_layer(&dm->faceData, CD_ORIGINDEX, CD_CALLOC, NULL, numTessFaces);
2395
2396         cddm->mvert = CustomData_get_layer(&dm->vertData, CD_MVERT);
2397         cddm->medge = CustomData_get_layer(&dm->edgeData, CD_MEDGE);
2398         cddm->mface = CustomData_get_layer(&dm->faceData, CD_MFACE);
2399         cddm->mloop = CustomData_get_layer(&dm->loopData, CD_MLOOP);
2400         cddm->mpoly = CustomData_get_layer(&dm->polyData, CD_MPOLY);
2401
2402         return dm;
2403 }
2404 DerivedMesh *CDDM_from_template(
2405         DerivedMesh *source,
2406         int numVerts, int numEdges, int numTessFaces,
2407         int numLoops, int numPolys)
2408 {
2409         return CDDM_from_template_ex(
2410                 source, numVerts, numEdges, numTessFaces,
2411                 numLoops, numPolys,
2412                 CD_MASK_DERIVEDMESH);
2413 }
2414
2415 void CDDM_apply_vert_coords(DerivedMesh *dm, float (*vertCoords)[3])
2416 {
2417         CDDerivedMesh *cddm = (CDDerivedMesh *)dm;
2418         MVert *vert;
2419         int i;
2420
2421         /* this will just return the pointer if it wasn't a referenced layer */
2422         vert = CustomData_duplicate_referenced_layer(&dm->vertData, CD_MVERT, dm->numVertData);
2423         cddm->mvert = vert;
2424
2425         for (i = 0; i < dm->numVertData; ++i, ++vert)
2426                 copy_v3_v3(vert->co, vertCoords[i]);
2427
2428         cddm->dm.dirty |= DM_DIRTY_NORMALS;
2429 }
2430
2431 void CDDM_apply_vert_normals(DerivedMesh *dm, short (*vertNormals)[3])
2432 {
2433         CDDerivedMesh *cddm = (CDDerivedMesh *)dm;
2434         MVert *vert;
2435         int i;
2436
2437         /* this will just return the pointer if it wasn't a referenced layer */
2438         vert = CustomData_duplicate_referenced_layer(&dm->vertData, CD_MVERT, dm->numVertData);
2439         cddm->mvert = vert;
2440
2441         for (i = 0; i < dm->numVertData; ++i, ++vert)
2442                 copy_v3_v3_short(vert->no, vertNormals[i]);
2443
2444         cddm->dm.dirty &= ~DM_DIRTY_NORMALS;
2445 }
2446
2447 void CDDM_calc_normals_mapping_ex(DerivedMesh *dm, const bool only_face_normals)
2448 {
2449         CDDerivedMesh *cddm = (CDDerivedMesh *)dm;
2450         float (*face_nors)[3] = NULL;
2451
2452         if (dm->numVertData == 0) {
2453                 cddm->dm.dirty &= ~DM_DIRTY_NORMALS;
2454                 return;
2455         }
2456
2457         /* now we skip calculating vertex normals for referenced layer,
2458          * no need to duplicate verts.
2459          * WATCH THIS, bmesh only change!,
2460          * need to take care of the side effects here - campbell */
2461 #if 0
2462         /* we don't want to overwrite any referenced layers */
2463         cddm->mvert = CustomData_duplicate_referenced_layer(&dm->vertData, CD_MVERT, dm->numVertData);
2464 #endif
2465
2466 #if 0
2467         if (dm->numTessFaceData == 0) {
2468                 /* No tessellation on this mesh yet, need to calculate one.
2469                  *
2470                  * Important not to update face normals from polys since it
2471                  * interferes with assigning the new normal layer in the following code.
2472                  */
2473                 CDDM_recalc_tessellation_ex(dm, false);
2474         }
2475         else {
2476                 /* A tessellation already exists, it should always have a CD_ORIGINDEX */
2477                 BLI_assert(CustomData_has_layer(&dm->faceData, CD_ORIGINDEX));
2478                 CustomData_free_layers(&dm->faceData, CD_NORMAL, dm->numTessFaceData);
2479         }
2480 #endif
2481
2482         face_nors = MEM_malloc_arrayN(dm->numPolyData, sizeof(*face_nors), "face_nors");
2483
2484         /* calculate face normals */
2485         BKE_mesh_calc_normals_poly(
2486                 cddm->mvert, NULL, dm->numVertData, CDDM_get_loops(dm), CDDM_get_polys(dm),
2487                 dm->numLoopData, dm->numPolyData, face_nors,
2488                 only_face_normals);
2489
2490         CustomData_add_layer(&dm->polyData, CD_NORMAL, CD_ASSIGN, face_nors, dm->numPolyData);
2491
2492         cddm->dm.dirty &= ~DM_DIRTY_NORMALS;
2493 }
2494
2495 void CDDM_calc_normals_mapping(DerivedMesh *dm)
2496 {
2497         /* use this to skip calculating normals on original vert's, this may need to be changed */
2498         const bool only_face_normals = CustomData_is_referenced_layer(&dm->vertData, CD_MVERT);
2499
2500         CDDM_calc_normals_mapping_ex(dm, only_face_normals);
2501 }
2502
2503 #if 0
2504 /* bmesh note: this matches what we have in trunk */
2505 void CDDM_calc_normals(DerivedMesh *dm)
2506 {
2507         CDDerivedMesh *cddm = (CDDerivedMesh *)dm;
2508         float (*poly_nors)[3];
2509
2510         if (dm->numVertData == 0) return;
2511
2512         /* we don't want to overwrite any referenced layers */
2513         cddm->mvert = CustomData_duplicate_referenced_layer(&dm->vertData, CD_MVERT, dm->numVertData);
2514
2515         /* fill in if it exists */
2516         poly_nors = CustomData_get_layer(&dm->polyData, CD_NORMAL);
2517         if (!poly_nors) {
2518                 poly_nors = CustomData_add_layer(&dm->polyData, CD_NORMAL, CD_CALLOC, NULL, dm->numPolyData);
2519         }
2520
2521         BKE_mesh_calc_normals_poly(cddm->mvert, dm->numVertData, CDDM_get_loops(dm), CDDM_get_polys(dm),
2522                                        dm->numLoopData, dm->numPolyData, poly_nors, false);
2523
2524         cddm->dm.dirty &= ~DM_DIRTY_NORMALS;
2525 }
2526 #else
2527
2528 /* poly normal layer is now only for final display */
2529 void CDDM_calc_normals(DerivedMesh *dm)
2530 {
2531         CDDerivedMesh *cddm = (CDDerivedMesh *)dm;
2532
2533         /* we don't want to overwrite any referenced layers */
2534         cddm->mvert = CustomData_duplicate_referenced_layer(&dm->vertData, CD_MVERT, dm->numVertData);
2535
2536         BKE_mesh_calc_normals_poly(cddm->mvert, NULL, dm->numVertData, CDDM_get_loops(dm), CDDM_get_polys(dm),
2537                                    dm->numLoopData, dm->numPolyData, NULL, false);
2538
2539         cddm->dm.dirty &= ~DM_DIRTY_NORMALS;
2540 }
2541
2542 #endif
2543
2544 void CDDM_calc_loop_normals(DerivedMesh *dm, const bool use_split_normals, const float split_angle)
2545 {
2546         CDDM_calc_loop_normals_spacearr(dm, use_split_normals, split_angle, NULL);
2547 }
2548
2549 /* #define DEBUG_CLNORS */
2550 #ifdef DEBUG_CLNORS
2551 #  include "BLI_linklist.h"
2552 #endif
2553
2554 void CDDM_calc_loop_normals_spacearr(
2555         DerivedMesh *dm, const bool use_split_normals, const float split_angle, MLoopNorSpaceArray *r_lnors_spacearr)
2556 {
2557         MVert *mverts = dm->getVertArray(dm);
2558         MEdge *medges = dm->getEdgeArray(dm);
2559         MLoop *mloops = dm->getLoopArray(dm);
2560         MPoly *mpolys = dm->getPolyArray(dm);
2561
2562         CustomData *ldata, *pdata;
2563
2564         float (*lnors)[3];
2565         short (*clnor_data)[2];
2566         float (*pnors)[3];
2567
2568         const int numVerts = dm->getNumVerts(dm);
2569         const int numEdges = dm->getNumEdges(dm);
2570         const int numLoops = dm->getNumLoops(dm);
2571         const int numPolys = dm->getNumPolys(dm);
2572
2573         ldata = dm->getLoopDataLayout(dm);
2574         if (CustomData_has_layer(ldata, CD_NORMAL)) {
2575                 lnors = CustomData_get_layer(ldata, CD_NORMAL);
2576         }
2577         else {
2578                 lnors = CustomData_add_layer(ldata, CD_NORMAL, CD_CALLOC, NULL, numLoops);
2579         }
2580
2581         /* Compute poly (always needed) and vert normals. */
2582         /* Note we can't use DM_ensure_normals, since it won't keep computed poly nors... */
2583         pdata = dm->getPolyDataLayout(dm);
2584         pnors = CustomData_get_layer(pdata, CD_NORMAL);
2585         if (!pnors) {
2586                 pnors = CustomData_add_layer(pdata, CD_NORMAL, CD_CALLOC, NULL, numPolys);
2587         }
2588         BKE_mesh_calc_normals_poly(mverts, NULL, numVerts, mloops, mpolys, numLoops, numPolys, pnors,
2589                                    (dm->dirty & DM_DIRTY_NORMALS) ? false : true);
2590
2591         dm->dirty &= ~DM_DIRTY_NORMALS;
2592
2593         clnor_data = CustomData_get_layer(ldata, CD_CUSTOMLOOPNORMAL);
2594
2595         BKE_mesh_normals_loop_split(mverts, numVerts, medges, numEdges, mloops, lnors, numLoops,
2596                                     mpolys, (const float (*)[3])pnors, numPolys,
2597                                     use_split_normals, split_angle,
2598                                     r_lnors_spacearr, clnor_data, NULL);
2599 #ifdef DEBUG_CLNORS
2600         if (r_lnors_spacearr) {
2601                 int i;
2602                 for (i = 0; i < numLoops; i++) {
2603                         if (r_lnors_spacearr->lspacearr[i]->ref_alpha != 0.0f) {
2604                                 LinkNode *loops = r_lnors_spacearr->lspacearr[i]->loops;
2605                                 printf("Loop %d uses lnor space %p:\n", i, r_lnors_spacearr->lspacearr[i]);
2606                                 print_v3("\tfinal lnor", lnors[i]);
2607                                 print_v3("\tauto lnor", r_lnors_spacearr->lspacearr[i]->vec_lnor);
2608                                 print_v3("\tref_vec", r_lnors_spacearr->lspacearr[i]->vec_ref);
2609                                 printf("\talpha: %f\n\tbeta: %f\n\tloops: %p\n", r_lnors_spacearr->lspacearr[i]->ref_alpha,
2610                                        r_lnors_spacearr->lspacearr[i]->ref_beta, r_lnors_spacearr->lspacearr[i]->loops);
2611                                 printf("\t\t(shared with loops");
2612                                 while (loops) {
2613                                         printf(" %d", GET_INT_FROM_POINTER(loops->link));
2614                                         loops = loops->next;
2615                                 }
2616                                 printf(")\n");
2617                         }
2618                         else {
2619                                 printf("Loop %d has no lnor space\n", i);
2620                         }
2621                 }
2622         }
2623 #endif
2624 }
2625
2626
2627 void CDDM_calc_normals_tessface(DerivedMesh *dm)
2628 {
2629         CDDerivedMesh *cddm = (CDDerivedMesh *)dm;
2630         float (*face_nors)[3];
2631
2632         if (dm->numVertData == 0) return;
2633
2634         /* we don't want to overwrite any referenced layers */
2635         cddm->mvert = CustomData_duplicate_referenced_layer(&dm->vertData, CD_MVERT, dm->numVertData);
2636
2637         /* fill in if it exists */
2638         face_nors = CustomData_get_layer(&dm->faceData, CD_NORMAL);
2639         if (!face_nors) {
2640                 face_nors = CustomData_add_layer(&dm->faceData, CD_NORMAL, CD_CALLOC, NULL, dm->numTessFaceData);
2641         }
2642
2643         BKE_mesh_calc_normals_tessface(cddm->mvert, dm->numVertData,
2644                                        cddm->mface, dm->numTessFaceData, face_nors);
2645
2646         cddm->dm.dirty &= ~DM_DIRTY_NORMALS;
2647 }
2648
2649 #if 1
2650
2651 /**
2652  * Poly compare with vtargetmap
2653  * Function used by #CDDM_merge_verts.
2654  * The function compares poly_source after applying vtargetmap, with poly_target.
2655  * The two polys are identical if they share the same vertices in the same order, or in reverse order,
2656  * but starting position loopstart may be different.
2657  * The function is called with direct_reverse=1 for same order (i.e. same normal),
2658  * and may be called again with direct_reverse=-1 for reverse order.
2659  * \return 1 if polys are identical,  0 if polys are different.
2660  */
2661 static int cddm_poly_compare(
2662         MLoop *mloop_array,
2663         MPoly *mpoly_source, MPoly *mpoly_target,
2664         const int *vtargetmap, const int direct_reverse)
2665 {
2666         int vert_source, first_vert_source, vert_target;
2667         int i_loop_source;
2668         int i_loop_target, i_loop_target_start, i_loop_target_offset, i_loop_target_adjusted;
2669         bool compare_completed = false;
2670         bool same_loops = false;
2671
2672         MLoop *mloop_source, *mloop_target;
2673
2674         BLI_assert(direct_reverse == 1 || direct_reverse == -1);
2675
2676         i_loop_source = 0;
2677         mloop_source = mloop_array + mpoly_source->loopstart;
2678         vert_source = mloop_source->v;
2679
2680         if (vtargetmap[vert_source] != -1) {
2681                 vert_source = vtargetmap[vert_source];
2682         }
2683         else {
2684                 /* All source loop vertices should be mapped */
2685                 BLI_assert(false);
2686         }
2687
2688         /* Find same vertex within mpoly_target's loops */
2689         mloop_target = mloop_array + mpoly_target->loopstart;
2690         for (i_loop_target = 0; i_loop_target < mpoly_target->totloop; i_loop_target++, mloop_target++) {
2691                 if (mloop_target->v == vert_source) {
2692                         break;
2693                 }
2694         }
2695
2696         /* If same vertex not found, then polys cannot be equal */
2697         if (i_loop_target >= mpoly_target->totloop) {
2698                 return false;
2699         }
2700
2701         /* Now mloop_source and m_loop_target have one identical vertex */
2702         /* mloop_source is at position 0, while m_loop_target has advanced to find identical vertex */
2703         /* Go around the loop and check that all vertices match in same order */
2704         /* Skipping source loops when consecutive source vertices are mapped to same target vertex */
2705
2706         i_loop_target_start = i_loop_target;
2707         i_loop_target_offset = 0;
2708         first_vert_source = vert_source;
2709
2710         compare_completed = false;
2711         same_loops = false;
2712
2713         while (!compare_completed) {
2714
2715                 vert_target = mloop_target->v;
2716
2717                 /* First advance i_loop_source, until it points to different vertex, after mapping applied */
2718                 do {
2719                         i_loop_source++;
2720
2721                         if (i_loop_source == mpoly_source->totloop) {
2722                                 /* End of loops for source, must match end of loop for target.  */
2723                                 if (i_loop_target_offset == mpoly_target->totloop - 1) {
2724                                         compare_completed = true;
2725                                         same_loops = true;
2726                                         break;  /* Polys are identical */
2727                                 }
2728                                 else {
2729                                         compare_completed = true;
2730                                         same_loops = false;
2731                                         break;  /* Polys are different */
2732                                 }
2733                         }
2734
2735                         mloop_source++;
2736                         vert_source = mloop_source->v;
2737
2738                         if (vtargetmap[vert_source] != -1) {
2739                                 vert_source = vtargetmap[vert_source];
2740                         }
2741                         else {
2742                                 /* All source loop vertices should be mapped */
2743                                 BLI_assert(false);
2744                         }
2745
2746                 } while (vert_source == vert_target);
2747
2748                 if (compare_completed) {
2749                         break;
2750                 }
2751
2752                 /* Now advance i_loop_target as well */
2753                 i_loop_target_offset++;
2754
2755                 if (i_loop_target_offset == mpoly_target->totloop) {
2756                         /* End of loops for target only, that means no match */
2757                         /* except if all remaining source vertices are mapped to first target */
2758                         for (; i_loop_source < mpoly_source->totloop; i_loop_source++, mloop_source++) {
2759                                 vert_source = vtargetmap[mloop_source->v];
2760                                 if (vert_source != first_vert_source) {
2761                                         compare_completed = true;
2762                                         same_loops = false;
2763                                         break;
2764                                 }
2765                         }
2766                         if (!compare_completed) {
2767                                 same_loops = true;
2768                         }
2769                         break;
2770                 }
2771
2772                 /* Adjust i_loop_target for cycling around and for direct/reverse order defined by delta = +1 or -1 */
2773                 i_loop_target_adjusted = (i_loop_target_start + direct_reverse * i_loop_target_offset) % mpoly_target->totloop;
2774                 if (i_loop_target_adjusted < 0) {
2775                         i_loop_target_adjusted += mpoly_target->totloop;
2776                 }
2777                 mloop_target = mloop_array + mpoly_target->loopstart + i_loop_target_adjusted;
2778                 vert_target = mloop_target->v;
2779
2780                 if (vert_target != vert_source) {
2781                         same_loops = false;  /* Polys are different */
2782                         break;
2783                 }
2784         }
2785         return same_loops;
2786 }
2787
2788 /* Utility stuff for using GHash with polys */
2789
2790 typedef struct PolyKey {
2791         int poly_index;   /* index of the MPoly within the derived mesh */
2792         int totloops;     /* number of loops in the poly */
2793         unsigned int hash_sum;  /* Sum of all vertices indices */
2794         unsigned int hash_xor;  /* Xor of all vertices indices */
2795 } PolyKey;
2796
2797
2798 static unsigned int poly_gset_hash_fn(const void *key)
2799 {
2800         const PolyKey *pk = key;
2801         return pk->hash_sum;
2802 }
2803
2804 static bool poly_gset_compare_fn(const void *k1, const void *k2)
2805 {
2806         const PolyKey *pk1 = k1;
2807         const PolyKey *pk2 = k2;
2808         if ((pk1->hash_sum == pk2->hash_sum) &&
2809             (pk1->hash_xor == pk2->hash_xor) &&
2810             (pk1->totloops == pk2->totloops))
2811         {
2812                 /* Equality - note that this does not mean equality of polys */
2813                 return false;
2814         }
2815         else {
2816                 return true;
2817         }
2818 }
2819
2820 /**
2821  * Merge Verts
2822  *
2823  * This frees dm, and returns a new one.
2824  *
2825  * \param vtargetmap  The table that maps vertices to target vertices.  a value of -1
2826  * indicates a vertex is a target, and is to be kept.
2827  * This array is aligned with 'dm->numVertData'
2828  * \warning \a vtergatmap must **not** contain any chained mapping (v1 -> v2 -> v3 etc.), this is not supported
2829  * and will likely generate corrupted geometry.
2830  *
2831  * \param tot_vtargetmap  The number of non '-1' values in vtargetmap. (not the size)
2832  *
2833  * \param merge_mode enum with two modes.
2834  * - #CDDM_MERGE_VERTS_DUMP_IF_MAPPED
2835  * When called by the Mirror Modifier,
2836  * In this mode it skips any faces that have all vertices merged (to avoid creating pairs
2837  * of faces sharing the same set of vertices)
2838  * - #CDDM_MERGE_VERTS_DUMP_IF_EQUAL
2839  * When called by the Array Modifier,
2840  * In this mode, faces where all vertices are merged are double-checked,
2841  * to see whether all target vertices actually make up a poly already.
2842  * Indeed it could be that all of a poly's vertices are merged,
2843  * but merged to vertices that do not make up a single poly,
2844  * in which case the original poly should not be dumped.
2845  * Actually this later behavior could apply to the Mirror Modifier as well, but the additional checks are
2846  * costly and not necessary in the case of mirror, because each vertex is only merged to its own mirror.
2847  *
2848  * \note #CDDM_recalc_tessellation has to run on the returned DM if you want to access tessfaces.
2849  */
2850 DerivedMesh *CDDM_merge_verts(DerivedMesh *dm, const int *vtargetmap, const int tot_vtargetmap, const int merge_mode)
2851 {
2852 // #define USE_LOOPS
2853         CDDerivedMesh *cddm = (CDDerivedMesh *)dm;
2854         CDDerivedMesh *cddm2 = NULL;
2855
2856         const int totvert = dm->numVertData;
2857         const int totedge = dm->numEdgeData;
2858         const int totloop = dm->numLoopData;
2859         const int totpoly = dm->numPolyData;
2860
2861         const int totvert_final = totvert - tot_vtargetmap;
2862
2863         MVert *mv, *mvert = MEM_malloc_arrayN(totvert_final, sizeof(*mvert), __func__);
2864         int *oldv         = MEM_malloc_arrayN(totvert_final, sizeof(*oldv), __func__);
2865         int *newv         = MEM_malloc_arrayN(totvert, sizeof(*newv), __func__);
2866         STACK_DECLARE(mvert);
2867         STACK_DECLARE(oldv);
2868
2869         /* Note: create (totedge + totloop) elements because partially invalid polys due to merge may require
2870          * generating new edges, and while in 99% cases we'll still end with less final edges than totedge,
2871          * cases can be forged that would end requiring more... */
2872         MEdge *med, *medge = MEM_malloc_arrayN((totedge + totloop), sizeof(*medge), __func__);
2873         int *olde          = MEM_malloc_arrayN((totedge + totloop), sizeof(*olde), __func__);
2874         int *newe          = MEM_malloc_arrayN((totedge + totloop), sizeof(*newe), __func__);
2875         STACK_DECLARE(medge);
2876         STACK_DECLARE(olde);
2877
2878         MLoop *ml, *mloop = MEM_malloc_arrayN(totloop, sizeof(*mloop), __func__);
2879         int *oldl         = MEM_malloc_arrayN(totloop, sizeof(*oldl), __func__);
2880 #ifdef USE_LOOPS
2881         int newl          = MEM_malloc_arrayN(totloop, sizeof(*newl), __func__);
2882 #endif
2883         STACK_DECLARE(mloop);
2884         STACK_DECLARE(oldl);
2885
2886         MPoly *mp, *mpoly = MEM_malloc_arrayN(totpoly, sizeof(*medge), __func__);
2887         int *oldp         = MEM_malloc_arrayN(totpoly, sizeof(*oldp), __func__);
2888         STACK_DECLARE(mpoly);
2889         STACK_DECLARE(oldp);
2890
2891         EdgeHash *ehash = BLI_edgehash_new_ex(__func__, totedge);
2892
2893         int i, j, c;
2894
2895         PolyKey *poly_keys;
2896         GSet *poly_gset = NULL;
2897
2898         STACK_INIT(oldv, totvert_final);
2899         STACK_INIT(olde, totedge);
2900         STACK_INIT(oldl, totloop);
2901         STACK_INIT(oldp, totpoly);
2902
2903         STACK_INIT(mvert, totvert_final);
2904         STACK_INIT(medge, totedge);
2905         STACK_INIT(mloop, totloop);
2906         STACK_INIT(mpoly, totpoly);
2907
2908         /* fill newv with destination vertex indices */
2909         mv = cddm->mvert;
2910         c = 0;
2911         for (i = 0; i < totvert; i++, mv++) {
2912                 if (vtargetmap[i] == -1) {
2913                         STACK_PUSH(oldv, i);
2914                         STACK_PUSH(mvert, *mv);
2915                         newv[i] = c++;
2916                 }
2917                 else {
2918                         /* dummy value */
2919                         newv[i] = 0;
2920                 }
2921         }
2922         
2923         /* now link target vertices to destination indices */
2924         for (i = 0; i < totvert; i++) {
2925                 if (vtargetmap[i] != -1) {
2926                         newv[i] = newv[vtargetmap[i]];
2927                 }
2928         }
2929
2930         /* Don't remap vertices in cddm->mloop, because we need to know the original
2931          * indices in order to skip faces with all vertices merged.
2932          * The "update loop indices..." section further down remaps vertices in mloop.
2933          */
2934
2935         /* now go through and fix edges and faces */
2936         med = cddm->medge;
2937         c = 0;
2938         for (i = 0; i < totedge; i++, med++) {
2939                 const unsigned int v1 = (vtargetmap[med->v1] != -1) ? vtargetmap[med->v1] : med->v1;
2940                 const unsigned int v2 = (vtargetmap[med->v2] != -1) ? vtargetmap[med->v2] : med->v2;
2941                 if (LIKELY(v1 != v2)) {
2942                         void **val_p;
2943
2944                         if (BLI_edgehash_ensure_p(ehash, v1, v2, &val_p)) {
2945                                 newe[i] = GET_INT_FROM_POINTER(*val_p);
2946                         }
2947                         else {
2948                                 STACK_PUSH(olde, i);
2949                                 STACK_PUSH(medge, *med);
2950                                 newe[i] = c;
2951                                 *val_p = SET_INT_IN_POINTER(c);
2952                                 c++;
2953                         }
2954                 }
2955                 else {
2956                         newe[i] = -1;
2957                 }
2958         }
2959         
2960         if (merge_mode == CDDM_MERGE_VERTS_DUMP_IF_EQUAL) {
2961                 /* In this mode, we need to determine,  whenever a poly' vertices are all mapped */
2962                 /* if the targets already make up a poly, in which case the new poly is dropped */
2963                 /* This poly equality check is rather complex.   We use a BLI_ghash to speed it up with a first level check */
2964                 PolyKey *mpgh;
2965                 poly_keys = MEM_malloc_arrayN(totpoly, sizeof(PolyKey), __func__);
2966                 poly_gset = BLI_gset_new_ex(poly_gset_hash_fn, poly_gset_compare_fn, __func__, totpoly);
2967                 /* Duplicates allowed because our compare function is not pure equality */
2968                 BLI_gset_flag_set(poly_gset, GHASH_FLAG_ALLOW_DUPES);
2969
2970                 mp = cddm->mpoly;
2971                 mpgh = poly_keys;
2972                 for (i = 0; i < totpoly; i++, mp++, mpgh++) {
2973                         mpgh->poly_index = i;
2974                         mpgh->totloops = mp->totloop;
2975                         ml = cddm->mloop + mp->loopstart;
2976                         mpgh->hash_sum = mpgh->hash_xor = 0;
2977                         for (j = 0; j < mp->totloop; j++, ml++) {
2978                                 mpgh->hash_sum += ml->v;
2979                                 mpgh->hash_xor ^= ml->v;
2980                         }
2981                         BLI_gset_insert(poly_gset, mpgh);
2982                 }
2983
2984                 if (cddm->pmap) {
2985                         MEM_freeN(cddm->pmap);
2986                         MEM_freeN(cddm->pmap_mem);
2987                 }
2988                 /* Can we optimise by reusing an old pmap ?  How do we know an old pmap is stale ?  */
2989                 /* When called by MOD_array.c, the cddm has just been created, so it has no valid pmap.   */
2990                 BKE_mesh_vert_poly_map_create(&cddm->pmap, &cddm->pmap_mem,
2991                                               cddm->mpoly, cddm->mloop,
2992                                               totvert, totpoly, totloop);
2993         }  /* done preparing for fast poly compare */
2994
2995
2996         mp = cddm->mpoly;
2997         mv = cddm->mvert;
2998         for (i = 0; i < totpoly; i++, mp++) {
2999                 MPoly *mp_new;
3000                 
3001                 ml = cddm->mloop + mp->loopstart;
3002
3003                 /* check faces with all vertices merged */
3004                 bool all_vertices_merged = true;
3005
3006                 for (j = 0; j < mp->totloop; j++, ml++) {
3007                         if (vtargetmap[ml->v] == -1) {
3008                                 all_vertices_merged = false;
3009                                 /* This will be used to check for poly using several time the same vert. */
3010                                 mv[ml->v].flag &= ~ME_VERT_TMP_TAG;
3011                         }
3012                         else {
3013                                 /* This will be used to check for poly using several time the same vert. */
3014                                 mv[vtargetmap[ml->v]].flag &= ~ME_VERT_TMP_TAG;
3015                         }
3016                 }
3017
3018                 if (UNLIKELY(all_vertices_merged)) {
3019                         if (merge_mode == CDDM_MERGE_VERTS_DUMP_IF_MAPPED) {
3020                                 /* In this mode, all vertices merged is enough to dump face */
3021                                 continue;
3022                         }
3023                         else if (merge_mode == CDDM_MERGE_VERTS_DUMP_IF_EQUAL) {
3024                                 /* Additional condition for face dump:  target vertices must make up an identical face */
3025                                 /* The test has 2 steps:  (1) first step is fast ghash lookup, but not failproof       */
3026                                 /*                        (2) second step is thorough but more costly poly compare     */
3027                                 int i_poly, v_target;
3028                                 bool found = false;
3029                                 PolyKey pkey;
3030
3031                                 /* Use poly_gset for fast (although not 100% certain) identification of same poly */
3032                                 /* First, make up a poly_summary structure */
3033                                 ml = cddm->mloop + mp->loopstart;
3034                                 pkey.hash_sum = pkey.hash_xor = 0;
3035                                 pkey.totloops = 0;
3036                                 for (j = 0; j < mp->totloop; j++, ml++) {
3037                                         v_target = vtargetmap[ml->v];   /* Cannot be -1, they are all mapped */
3038                                         pkey.hash_sum += v_target;
3039                                         pkey.hash_xor ^= v_target;
3040                                         pkey.totloops++;
3041                                 }
3042                                 if (BLI_gset_haskey(poly_gset, &pkey)) {
3043
3044                                         /* There might be a poly that matches this one.
3045                                          * We could just leave it there and say there is, and do a "continue".
3046                                          * ... but we are checking whether there is an exact poly match.
3047                                          * It's not so costly in terms of CPU since it's very rare, just a lot of complex code.
3048                                          */
3049
3050                                         /* Consider current loop again */
3051                                         ml = cddm->mloop + mp->loopstart;
3052                                         /* Consider the target of the loop's first vert */
3053                                         v_target = vtargetmap[ml->v];
3054                                         /* Now see if v_target belongs to a poly that shares all vertices with source poly,
3055                                          * in same order, or reverse order */
3056
3057                                         for (i_poly = 0; i_poly < cddm->pmap[v_target].count; i_poly++) {
3058                                                 MPoly *target_poly = cddm->mpoly + *(cddm->pmap[v_target].indices + i_poly);
3059
3060                                                 if (cddm_poly_compare(cddm->mloop, mp, target_poly, vtargetmap, +1) ||
3061                                                     cddm_poly_compare(cddm->mloop, mp, target_poly, vtargetmap, -1))
3062                                                 {
3063                                                         found = true;
3064                                                         break;
3065                                                 }
3066                                         }
3067                                         if (found) {
3068                                                 /* Current poly's vertices are mapped to a poly that is strictly identical */
3069                                                 /* Current poly is dumped */
3070           &