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