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