404e433d6cd3a636c0f5cca9a20d1063e44afbfc
[blender.git] / source / blender / blenkernel / intern / cdderivedmesh.c
1 /*
2 * $Id$
3 *
4 * ***** BEGIN GPL LICENSE BLOCK *****
5 *
6 * This program is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU General Public License
8 * as published by the Free Software Foundation; either version 2
9 * of the License, or (at your option) any later version.
10 *
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software  Foundation,
18 * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
19 *
20 * The Original Code is Copyright (C) 2006 Blender Foundation.
21 * All rights reserved.
22 *
23 * The Original Code is: all of this file.
24 *
25 * Contributor(s): Ben Batt <benbatt@gmail.com>
26 *
27 * ***** END GPL LICENSE BLOCK *****
28 *
29 * Implementation of CDDerivedMesh.
30 *
31 * BKE_cdderivedmesh.h contains the function prototypes for this file.
32 *
33 */ 
34
35 /* TODO maybe BIF_gl.h should include string.h? */
36 #include <string.h>
37 #include "BIF_gl.h"
38
39 #include "BKE_cdderivedmesh.h"
40 #include "BKE_customdata.h"
41 #include "BKE_DerivedMesh.h"
42 #include "BKE_displist.h"
43 #include "BKE_global.h"
44 #include "BKE_mesh.h"
45 #include "BKE_utildefines.h"
46
47 #include "BLI_arithb.h"
48 #include "BLI_blenlib.h"
49 #include "BLI_edgehash.h"
50 #include "BLI_editVert.h"
51 #include "BLI_ghash.h"
52
53 #include "DNA_mesh_types.h"
54 #include "DNA_meshdata_types.h"
55 #include "DNA_object_types.h"
56 #include "DNA_scene_types.h"
57
58 #include "MEM_guardedalloc.h"
59
60 #include <string.h>
61 #include <limits.h>
62
63 typedef struct {
64         DerivedMesh dm;
65
66         /* these point to data in the DerivedMesh custom data layers,
67            they are only here for efficiency and convenience **/
68         MVert *mvert;
69         MEdge *medge;
70         MFace *mface;
71 } CDDerivedMesh;
72
73 /**************** DerivedMesh interface functions ****************/
74 static int cdDM_getNumVerts(DerivedMesh *dm)
75 {
76         return dm->numVertData;
77 }
78
79 static int cdDM_getNumEdges(DerivedMesh *dm)
80 {
81         return dm->numEdgeData;
82 }
83
84 static int cdDM_getNumFaces(DerivedMesh *dm)
85 {
86         return dm->numFaceData;
87 }
88
89 static void cdDM_getVert(DerivedMesh *dm, int index, MVert *vert_r)
90 {
91         CDDerivedMesh *cddm = (CDDerivedMesh *)dm;
92         *vert_r = cddm->mvert[index];
93 }
94
95 static void cdDM_getEdge(DerivedMesh *dm, int index, MEdge *edge_r)
96 {
97         CDDerivedMesh *cddm = (CDDerivedMesh *)dm;
98         *edge_r = cddm->medge[index];
99 }
100
101 static void cdDM_getFace(DerivedMesh *dm, int index, MFace *face_r)
102 {
103         CDDerivedMesh *cddm = (CDDerivedMesh *)dm;
104         *face_r = cddm->mface[index];
105 }
106
107 static void cdDM_copyVertArray(DerivedMesh *dm, MVert *vert_r)
108 {
109         CDDerivedMesh *cddm = (CDDerivedMesh *)dm;
110         memcpy(vert_r, cddm->mvert, sizeof(*vert_r) * dm->numVertData);
111 }
112
113 static void cdDM_copyEdgeArray(DerivedMesh *dm, MEdge *edge_r)
114 {
115         CDDerivedMesh *cddm = (CDDerivedMesh *)dm;
116         memcpy(edge_r, cddm->medge, sizeof(*edge_r) * dm->numEdgeData);
117 }
118
119 void cdDM_copyFaceArray(DerivedMesh *dm, MFace *face_r)
120 {
121         CDDerivedMesh *cddm = (CDDerivedMesh *)dm;
122         memcpy(face_r, cddm->mface, sizeof(*face_r) * dm->numFaceData);
123 }
124
125 static void cdDM_getMinMax(DerivedMesh *dm, float min_r[3], float max_r[3])
126 {
127         CDDerivedMesh *cddm = (CDDerivedMesh*) dm;
128         int i;
129
130         if (dm->numVertData) {
131                 for (i=0; i<dm->numVertData; i++) {
132                         DO_MINMAX(cddm->mvert[i].co, min_r, max_r);
133                 }
134         } else {
135                 min_r[0] = min_r[1] = min_r[2] = max_r[0] = max_r[1] = max_r[2] = 0.0;
136         }
137 }
138
139 static void cdDM_getVertCo(DerivedMesh *dm, int index, float co_r[3])
140 {
141         CDDerivedMesh *cddm = (CDDerivedMesh*) dm;
142
143         VECCOPY(co_r, cddm->mvert[index].co);
144 }
145
146 static void cdDM_getVertCos(DerivedMesh *dm, float (*cos_r)[3])
147 {
148         MVert *mv = CDDM_get_verts(dm);
149         int i;
150
151         for(i = 0; i < dm->numVertData; i++, mv++)
152                 VECCOPY(cos_r[i], mv->co);
153 }
154
155 static void cdDM_getVertNo(DerivedMesh *dm, int index, float no_r[3])
156 {
157         CDDerivedMesh *cddm = (CDDerivedMesh*) dm;
158         short *no = cddm->mvert[index].no;
159
160         no_r[0] = no[0]/32767.f;
161         no_r[1] = no[1]/32767.f;
162         no_r[2] = no[2]/32767.f;
163 }
164
165 static void cdDM_drawVerts(DerivedMesh *dm)
166 {
167         CDDerivedMesh *cddm = (CDDerivedMesh*) dm;
168         MVert *mv = cddm->mvert;
169         int i;
170
171         glBegin(GL_POINTS);
172         for(i = 0; i < dm->numVertData; i++, mv++)
173                 glVertex3fv(mv->co);
174         glEnd();
175 }
176
177 static void cdDM_drawUVEdges(DerivedMesh *dm)
178 {
179         CDDerivedMesh *cddm = (CDDerivedMesh*) dm;
180         MTFace *tf = DM_get_face_data_layer(dm, CD_MTFACE);
181         MFace *mf = cddm->mface;
182         int i;
183
184         if(tf) {
185                 glBegin(GL_LINES);
186                 for(i = 0; i < dm->numFaceData; i++, tf++, mf++) {
187                         if(!(tf->flag&TF_HIDE)) {
188                                 glVertex2fv(tf->uv[0]);
189                                 glVertex2fv(tf->uv[1]);
190
191                                 glVertex2fv(tf->uv[1]);
192                                 glVertex2fv(tf->uv[2]);
193
194                                 if(!mf->v4) {
195                                         glVertex2fv(tf->uv[2]);
196                                         glVertex2fv(tf->uv[0]);
197                                 } else {
198                                         glVertex2fv(tf->uv[2]);
199                                         glVertex2fv(tf->uv[3]);
200
201                                         glVertex2fv(tf->uv[3]);
202                                         glVertex2fv(tf->uv[0]);
203                                 }
204                         }
205                 }
206                 glEnd();
207         }
208 }
209
210 static void cdDM_drawEdges(DerivedMesh *dm, int drawLooseEdges)
211 {
212         CDDerivedMesh *cddm = (CDDerivedMesh*) dm;
213         MVert *mvert = cddm->mvert;
214         MEdge *medge = cddm->medge;
215         int i;
216                 
217         glBegin(GL_LINES);
218         for(i = 0; i < dm->numEdgeData; i++, medge++) {
219                 if((medge->flag&ME_EDGEDRAW)
220                    && (drawLooseEdges || !(medge->flag&ME_LOOSEEDGE))) {
221                         glVertex3fv(mvert[medge->v1].co);
222                         glVertex3fv(mvert[medge->v2].co);
223                 }
224         }
225         glEnd();
226 }
227
228 static void cdDM_drawLooseEdges(DerivedMesh *dm)
229 {
230         CDDerivedMesh *cddm = (CDDerivedMesh*) dm;
231         MVert *mvert = cddm->mvert;
232         MEdge *medge = cddm->medge;
233         int i;
234
235         glBegin(GL_LINES);
236         for(i = 0; i < dm->numEdgeData; i++, medge++) {
237                 if(medge->flag&ME_LOOSEEDGE) {
238                         glVertex3fv(mvert[medge->v1].co);
239                         glVertex3fv(mvert[medge->v2].co);
240                 }
241         }
242         glEnd();
243 }
244
245 static void cdDM_drawFacesSolid(DerivedMesh *dm, int (*setMaterial)(int))
246 {
247         CDDerivedMesh *cddm = (CDDerivedMesh*) dm;
248         MVert *mvert = cddm->mvert;
249         MFace *mface = cddm->mface;
250         float *nors= dm->getFaceDataArray(dm, CD_NORMAL);
251         int a, glmode = -1, shademodel = -1, matnr = -1, drawCurrentMat = 1;
252
253 #define PASSVERT(index) {                                               \
254         if(shademodel == GL_SMOOTH) {                           \
255                 short *no = mvert[index].no;                    \
256                 glNormal3sv(no);                                                \
257         }                                                                                       \
258         glVertex3fv(mvert[index].co);   \
259 }
260
261         glBegin(glmode = GL_QUADS);
262         for(a = 0; a < dm->numFaceData; a++, mface++) {
263                 int new_glmode, new_matnr, new_shademodel;
264
265                 new_glmode = mface->v4?GL_QUADS:GL_TRIANGLES;
266                 new_matnr = mface->mat_nr + 1;
267                 new_shademodel = (mface->flag & ME_SMOOTH)?GL_SMOOTH:GL_FLAT;
268                 
269                 if(new_glmode != glmode || new_matnr != matnr
270                    || new_shademodel != shademodel) {
271                         glEnd();
272
273                         drawCurrentMat = setMaterial(matnr = new_matnr);
274
275                         glShadeModel(shademodel = new_shademodel);
276                         glBegin(glmode = new_glmode);
277                 } 
278                 
279                 if(drawCurrentMat) {
280                         if(shademodel == GL_FLAT) {
281                                 if (nors) {
282                                         glNormal3fv(nors);
283                                 }
284                                 else {
285                                         /* TODO make this better (cache facenormals as layer?) */
286                                         float nor[3];
287                                         if(mface->v4) {
288                                                 CalcNormFloat4(mvert[mface->v1].co, mvert[mface->v2].co,
289                                                                            mvert[mface->v3].co, mvert[mface->v4].co,
290                                                                            nor);
291                                         } else {
292                                                 CalcNormFloat(mvert[mface->v1].co, mvert[mface->v2].co,
293                                                                           mvert[mface->v3].co, nor);
294                                         }
295                                         glNormal3fv(nor);
296                                 }
297                         }
298
299                         PASSVERT(mface->v1);
300                         PASSVERT(mface->v2);
301                         PASSVERT(mface->v3);
302                         if(mface->v4) {
303                                 PASSVERT(mface->v4);
304                         }
305                 }
306
307                 if(nors) nors += 3;
308         }
309         glEnd();
310
311         glShadeModel(GL_FLAT);
312 #undef PASSVERT
313 }
314
315 static void cdDM_drawFacesColored(DerivedMesh *dm, int useTwoSided, unsigned char *col1, unsigned char *col2)
316 {
317         CDDerivedMesh *cddm = (CDDerivedMesh*) dm;
318         int a, glmode;
319         unsigned char *cp1, *cp2;
320         MVert *mvert = cddm->mvert;
321         MFace *mface = cddm->mface;
322
323         cp1 = col1;
324         if(col2) {
325                 cp2 = col2;
326         } else {
327                 cp2 = NULL;
328                 useTwoSided = 0;
329         }
330
331         /* there's a conflict here... twosided colors versus culling...? */
332         /* defined by history, only texture faces have culling option */
333         /* we need that as mesh option builtin, next to double sided lighting */
334         if(col1 && col2)
335                 glEnable(GL_CULL_FACE);
336         
337         glShadeModel(GL_SMOOTH);
338         glBegin(glmode = GL_QUADS);
339         for(a = 0; a < dm->numFaceData; a++, mface++, cp1 += 16) {
340                 int new_glmode = mface->v4?GL_QUADS:GL_TRIANGLES;
341
342                 if(new_glmode != glmode) {
343                         glEnd();
344                         glBegin(glmode = new_glmode);
345                 }
346                         
347                 glColor3ub(cp1[0], cp1[1], cp1[2]);
348                 glVertex3fv(mvert[mface->v1].co);
349                 glColor3ub(cp1[4], cp1[5], cp1[6]);
350                 glVertex3fv(mvert[mface->v2].co);
351                 glColor3ub(cp1[8], cp1[9], cp1[10]);
352                 glVertex3fv(mvert[mface->v3].co);
353                 if(mface->v4) {
354                         glColor3ub(cp1[12], cp1[13], cp1[14]);
355                         glVertex3fv(mvert[mface->v4].co);
356                 }
357                         
358                 if(useTwoSided) {
359                         glColor3ub(cp2[8], cp2[9], cp2[10]);
360                         glVertex3fv(mvert[mface->v3].co );
361                         glColor3ub(cp2[4], cp2[5], cp2[6]);
362                         glVertex3fv(mvert[mface->v2].co );
363                         glColor3ub(cp2[0], cp2[1], cp2[2]);
364                         glVertex3fv(mvert[mface->v1].co );
365                         if(mface->v4) {
366                                 glColor3ub(cp2[12], cp2[13], cp2[14]);
367                                 glVertex3fv(mvert[mface->v4].co );
368                         }
369                 }
370                 if(col2) cp2 += 16;
371         }
372         glEnd();
373
374         glShadeModel(GL_FLAT);
375         glDisable(GL_CULL_FACE);
376 }
377
378 static void cdDM_drawFacesTex_common(DerivedMesh *dm,
379                int (*drawParams)(MTFace *tface, MCol *mcol, int matnr),
380                int (*drawParamsMapped)(void *userData, int index),
381                void *userData) 
382 {
383         CDDerivedMesh *cddm = (CDDerivedMesh*) dm;
384         MVert *mv = cddm->mvert;
385         MFace *mf = cddm->mface;
386         MCol *mcol = dm->getFaceDataArray(dm, CD_MCOL);
387         float *nors= dm->getFaceDataArray(dm, CD_NORMAL);
388         MTFace *tf = DM_get_face_data_layer(dm, CD_MTFACE);
389         int i, orig, *index = DM_get_face_data_layer(dm, CD_ORIGINDEX);
390
391         for(i = 0; i < dm->numFaceData; i++, mf++) {
392                 MVert *mvert;
393                 int flag;
394                 unsigned char *cp = NULL;
395
396                 if(drawParams) {
397                         flag = drawParams(tf? &tf[i]: NULL, mcol? &mcol[i*4]: NULL, mf->mat_nr);
398                 }
399                 else {
400                         if(index) {
401                                 orig = *index++;
402                                 if(orig == ORIGINDEX_NONE) continue;
403                                 flag = drawParamsMapped(userData, orig);
404                         }
405                         else
406                                 flag = drawParamsMapped(userData, i);
407                 }
408
409                 if(flag == 0)
410                         continue;
411                 else if (flag==1 && mcol)
412                         cp= (unsigned char*) &mcol[i*4];
413
414                 if(!(mf->flag&ME_SMOOTH)) {
415                         if (nors) {
416                                 glNormal3fv(nors);
417                         }
418                         else {
419                                 /* TODO make this better (cache facenormals as layer?) */
420                                 float nor[3];
421                                 if(mf->v4) {
422                                         CalcNormFloat4(mv[mf->v1].co, mv[mf->v2].co,
423                                                                    mv[mf->v3].co, mv[mf->v4].co,
424                                                                    nor);
425                                 } else {
426                                         CalcNormFloat(mv[mf->v1].co, mv[mf->v2].co,
427                                                                   mv[mf->v3].co, nor);
428                                 }
429                                 glNormal3fv(nor);
430                         }
431                 }
432
433                 glBegin(mf->v4?GL_QUADS:GL_TRIANGLES);
434                 if(tf) glTexCoord2fv(tf[i].uv[0]);
435                 if(cp) glColor3ub(cp[3], cp[2], cp[1]);
436                 mvert = &mv[mf->v1];
437                 if(mf->flag&ME_SMOOTH) glNormal3sv(mvert->no);
438                 glVertex3fv(mvert->co);
439                         
440                 if(tf) glTexCoord2fv(tf[i].uv[1]);
441                 if(cp) glColor3ub(cp[7], cp[6], cp[5]);
442                 mvert = &mv[mf->v2];
443                 if(mf->flag&ME_SMOOTH) glNormal3sv(mvert->no);
444                 glVertex3fv(mvert->co);
445
446                 if(tf) glTexCoord2fv(tf[i].uv[2]);
447                 if(cp) glColor3ub(cp[11], cp[10], cp[9]);
448                 mvert = &mv[mf->v3];
449                 if(mf->flag&ME_SMOOTH) glNormal3sv(mvert->no);
450                 glVertex3fv(mvert->co);
451
452                 if(mf->v4) {
453                         if(tf) glTexCoord2fv(tf[i].uv[3]);
454                         if(cp) glColor3ub(cp[15], cp[14], cp[13]);
455                         mvert = &mv[mf->v4];
456                         if(mf->flag&ME_SMOOTH) glNormal3sv(mvert->no);
457                         glVertex3fv(mvert->co);
458                 }
459                 glEnd();
460
461                 if(nors) nors += 3;
462         }
463 }
464
465 static void cdDM_drawFacesTex(DerivedMesh *dm, int (*setDrawOptions)(MTFace *tface, MCol *mcol, int matnr))
466 {
467         cdDM_drawFacesTex_common(dm, setDrawOptions, NULL, NULL);
468 }
469
470 static void cdDM_drawMappedFaces(DerivedMesh *dm, int (*setDrawOptions)(void *userData, int index, int *drawSmooth_r), void *userData, int useColors)
471 {
472         CDDerivedMesh *cddm = (CDDerivedMesh*) dm;
473         MVert *mv = cddm->mvert;
474         MFace *mf = cddm->mface;
475         MCol *mc = DM_get_face_data_layer(dm, CD_MCOL);
476         float *nors= dm->getFaceDataArray(dm, CD_NORMAL);
477         int i, orig, *index = DM_get_face_data_layer(dm, CD_ORIGINDEX);
478
479         for(i = 0; i < dm->numFaceData; i++, mf++) {
480                 int drawSmooth = (mf->flag & ME_SMOOTH);
481
482                 if(index) {
483                         orig = *index++;
484                         if(setDrawOptions && orig == ORIGINDEX_NONE) continue;
485                 }
486                 else
487                         orig = i;
488
489                 if(!setDrawOptions || setDrawOptions(userData, orig, &drawSmooth)) {
490                         unsigned char *cp = NULL;
491
492                         if(useColors && mc)
493                                 cp = (unsigned char *)&mc[i * 4];
494
495                         glShadeModel(drawSmooth?GL_SMOOTH:GL_FLAT);
496                         glBegin(mf->v4?GL_QUADS:GL_TRIANGLES);
497
498                         if (!drawSmooth) {
499                                 if (nors) {
500                                         glNormal3fv(nors);
501                                 }
502                                 else {
503                                         /* TODO make this better (cache facenormals as layer?) */
504                                         float nor[3];
505                                         if(mf->v4) {
506                                                 CalcNormFloat4(mv[mf->v1].co, mv[mf->v2].co,
507                                                                            mv[mf->v3].co, mv[mf->v4].co,
508                                                                            nor);
509                                         } else {
510                                                 CalcNormFloat(mv[mf->v1].co, mv[mf->v2].co,
511                                                                           mv[mf->v3].co, nor);
512                                         }
513                                         glNormal3fv(nor);
514                                 }
515
516                                 if(cp) glColor3ub(cp[3], cp[2], cp[1]);
517                                 glVertex3fv(mv[mf->v1].co);
518                                 if(cp) glColor3ub(cp[7], cp[6], cp[5]);
519                                 glVertex3fv(mv[mf->v2].co);
520                                 if(cp) glColor3ub(cp[11], cp[10], cp[9]);
521                                 glVertex3fv(mv[mf->v3].co);
522                                 if(mf->v4) {
523                                         if(cp) glColor3ub(cp[15], cp[14], cp[13]);
524                                         glVertex3fv(mv[mf->v4].co);
525                                 }
526                         } else {
527                                 if(cp) glColor3ub(cp[3], cp[2], cp[1]);
528                                 glNormal3sv(mv[mf->v1].no);
529                                 glVertex3fv(mv[mf->v1].co);
530                                 if(cp) glColor3ub(cp[7], cp[6], cp[5]);
531                                 glNormal3sv(mv[mf->v2].no);
532                                 glVertex3fv(mv[mf->v2].co);
533                                 if(cp) glColor3ub(cp[11], cp[10], cp[9]);
534                                 glNormal3sv(mv[mf->v3].no);
535                                 glVertex3fv(mv[mf->v3].co);
536                                 if(mf->v4) {
537                                         if(cp) glColor3ub(cp[15], cp[14], cp[13]);
538                                         glNormal3sv(mv[mf->v4].no);
539                                         glVertex3fv(mv[mf->v4].co);
540                                 }
541                         }
542
543                         glEnd();
544                 }
545                 
546                 if (nors) nors += 3;
547         }
548 }
549
550 static void cdDM_drawMappedFacesTex(DerivedMesh *dm, int (*setDrawOptions)(void *userData, int index), void *userData)
551 {
552         cdDM_drawFacesTex_common(dm, NULL, setDrawOptions, userData);
553 }
554
555 static void cdDM_drawMappedEdges(DerivedMesh *dm, int (*setDrawOptions)(void *userData, int index), void *userData)
556 {
557         CDDerivedMesh *cddm = (CDDerivedMesh*) dm;
558         MVert *vert = cddm->mvert;
559         MEdge *edge = cddm->medge;
560         int i, orig, *index = DM_get_edge_data_layer(dm, CD_ORIGINDEX);
561
562         glBegin(GL_LINES);
563         for(i = 0; i < dm->numEdgeData; i++, edge++) {
564                 if(index) {
565                         orig = *index++;
566                         if(setDrawOptions && orig == ORIGINDEX_NONE) continue;
567                 }
568                 else
569                         orig = i;
570
571                 if(!setDrawOptions || setDrawOptions(userData, orig)) {
572                         glVertex3fv(vert[edge->v1].co);
573                         glVertex3fv(vert[edge->v2].co);
574                 }
575         }
576         glEnd();
577 }
578
579 static void cdDM_foreachMappedVert(
580                            DerivedMesh *dm,
581                            void (*func)(void *userData, int index, float *co,
582                                         float *no_f, short *no_s),
583                            void *userData)
584 {
585         MVert *mv = CDDM_get_verts(dm);
586         int i, orig, *index = DM_get_vert_data_layer(dm, CD_ORIGINDEX);
587
588         for(i = 0; i < dm->numVertData; i++, mv++) {
589                 if(index) {
590                         orig = *index++;
591                         if(orig == ORIGINDEX_NONE) continue;
592                         func(userData, orig, mv->co, NULL, mv->no);
593                 }
594                 else
595                         func(userData, i, mv->co, NULL, mv->no);
596         }
597 }
598
599 static void cdDM_foreachMappedEdge(
600                            DerivedMesh *dm,
601                            void (*func)(void *userData, int index,
602                                         float *v0co, float *v1co),
603                            void *userData)
604 {
605         CDDerivedMesh *cddm = (CDDerivedMesh*) dm;
606         MVert *mv = cddm->mvert;
607         MEdge *med = cddm->medge;
608         int i, orig, *index = DM_get_edge_data_layer(dm, CD_ORIGINDEX);
609
610         for(i = 0; i < dm->numEdgeData; i++, med++) {
611                 if (index) {
612                         orig = *index++;
613                         if(orig == ORIGINDEX_NONE) continue;
614                         func(userData, orig, mv[med->v1].co, mv[med->v2].co);
615                 }
616                 else
617                         func(userData, i, mv[med->v1].co, mv[med->v2].co);
618         }
619 }
620
621 static void cdDM_foreachMappedFaceCenter(
622                            DerivedMesh *dm,
623                            void (*func)(void *userData, int index,
624                                         float *cent, float *no),
625                            void *userData)
626 {
627         CDDerivedMesh *cddm = (CDDerivedMesh*)dm;
628         MVert *mv = cddm->mvert;
629         MFace *mf = cddm->mface;
630         int i, orig, *index = DM_get_face_data_layer(dm, CD_ORIGINDEX);
631
632         for(i = 0; i < dm->numFaceData; i++, mf++) {
633                 float cent[3];
634                 float no[3];
635
636                 if (index) {
637                         orig = *index++;
638                         if(orig == ORIGINDEX_NONE) continue;
639                 }
640                 else
641                         orig = i;
642
643                 VECCOPY(cent, mv[mf->v1].co);
644                 VecAddf(cent, cent, mv[mf->v2].co);
645                 VecAddf(cent, cent, mv[mf->v3].co);
646
647                 if (mf->v4) {
648                         CalcNormFloat4(mv[mf->v1].co, mv[mf->v2].co,
649                                        mv[mf->v3].co, mv[mf->v4].co, no);
650                         VecAddf(cent, cent, mv[mf->v4].co);
651                         VecMulf(cent, 0.25f);
652                 } else {
653                         CalcNormFloat(mv[mf->v1].co, mv[mf->v2].co,
654                                       mv[mf->v3].co, no);
655                         VecMulf(cent, 0.33333333333f);
656                 }
657
658                 func(userData, orig, cent, no);
659         }
660 }
661
662 static void cdDM_release(DerivedMesh *dm)
663 {
664         CDDerivedMesh *cddm = (CDDerivedMesh*)dm;
665
666         if (DM_release(dm))
667                 MEM_freeN(cddm);
668 }
669
670 /**************** CDDM interface functions ****************/
671 static CDDerivedMesh *cdDM_create(const char *desc)
672 {
673         CDDerivedMesh *cddm;
674         DerivedMesh *dm;
675
676         cddm = MEM_callocN(sizeof(*cddm), desc);
677         dm = &cddm->dm;
678
679         dm->getMinMax = cdDM_getMinMax;
680
681         dm->getNumVerts = cdDM_getNumVerts;
682         dm->getNumFaces = cdDM_getNumFaces;
683         dm->getNumEdges = cdDM_getNumEdges;
684
685         dm->getVert = cdDM_getVert;
686         dm->getEdge = cdDM_getEdge;
687         dm->getFace = cdDM_getFace;
688         dm->copyVertArray = cdDM_copyVertArray;
689         dm->copyEdgeArray = cdDM_copyEdgeArray;
690         dm->copyFaceArray = cdDM_copyFaceArray;
691         dm->getVertData = DM_get_vert_data;
692         dm->getEdgeData = DM_get_edge_data;
693         dm->getFaceData = DM_get_face_data;
694         dm->getVertDataArray = DM_get_vert_data_layer;
695         dm->getEdgeDataArray = DM_get_edge_data_layer;
696         dm->getFaceDataArray = DM_get_face_data_layer;
697
698         dm->getVertCos = cdDM_getVertCos;
699         dm->getVertCo = cdDM_getVertCo;
700         dm->getVertNo = cdDM_getVertNo;
701
702         dm->drawVerts = cdDM_drawVerts;
703
704         dm->drawUVEdges = cdDM_drawUVEdges;
705         dm->drawEdges = cdDM_drawEdges;
706         dm->drawLooseEdges = cdDM_drawLooseEdges;
707         dm->drawMappedEdges = cdDM_drawMappedEdges;
708
709         dm->drawFacesSolid = cdDM_drawFacesSolid;
710         dm->drawFacesColored = cdDM_drawFacesColored;
711         dm->drawFacesTex = cdDM_drawFacesTex;
712         dm->drawMappedFaces = cdDM_drawMappedFaces;
713         dm->drawMappedFacesTex = cdDM_drawMappedFacesTex;
714
715         dm->foreachMappedVert = cdDM_foreachMappedVert;
716         dm->foreachMappedEdge = cdDM_foreachMappedEdge;
717         dm->foreachMappedFaceCenter = cdDM_foreachMappedFaceCenter;
718
719         dm->release = cdDM_release;
720
721         return cddm;
722 }
723
724 DerivedMesh *CDDM_new(int numVerts, int numEdges, int numFaces)
725 {
726         CDDerivedMesh *cddm = cdDM_create("CDDM_new dm");
727         DerivedMesh *dm = &cddm->dm;
728
729         DM_init(dm, numVerts, numEdges, numFaces);
730
731         CustomData_add_layer(&dm->vertData, CD_MVERT, CD_CALLOC, NULL, numVerts);
732         CustomData_add_layer(&dm->edgeData, CD_MEDGE, CD_CALLOC, NULL, numEdges);
733         CustomData_add_layer(&dm->faceData, CD_MFACE, CD_CALLOC, NULL, numFaces);
734
735         cddm->mvert = CustomData_get_layer(&dm->vertData, CD_MVERT);
736         cddm->medge = CustomData_get_layer(&dm->edgeData, CD_MEDGE);
737         cddm->mface = CustomData_get_layer(&dm->faceData, CD_MFACE);
738
739         return dm;
740 }
741
742 DerivedMesh *CDDM_from_mesh(Mesh *mesh, Object *ob)
743 {
744         CDDerivedMesh *cddm = cdDM_create("CDDM_from_mesh dm");
745         DerivedMesh *dm = &cddm->dm;
746         int i, *index;
747
748         /* this does a referenced copy, the only new layers being ORIGINDEX */
749
750         DM_init(dm, mesh->totvert, mesh->totedge, mesh->totface);
751
752         CustomData_merge(&mesh->vdata, &dm->vertData, CD_MASK_MESH, CD_REFERENCE,
753                          mesh->totvert);
754         CustomData_merge(&mesh->edata, &dm->edgeData, CD_MASK_MESH, CD_REFERENCE,
755                          mesh->totedge);
756         CustomData_merge(&mesh->fdata, &dm->faceData, CD_MASK_MESH, CD_REFERENCE,
757                          mesh->totface);
758
759         cddm->mvert = CustomData_get_layer(&dm->vertData, CD_MVERT);
760         cddm->medge = CustomData_get_layer(&dm->edgeData, CD_MEDGE);
761         cddm->mface = CustomData_get_layer(&dm->faceData, CD_MFACE);
762
763         index = CustomData_get_layer(&dm->vertData, CD_ORIGINDEX);
764         for(i = 0; i < mesh->totvert; ++i, ++index)
765                 *index = i;
766
767         index = CustomData_get_layer(&dm->edgeData, CD_ORIGINDEX);
768         for(i = 0; i < mesh->totedge; ++i, ++index)
769                 *index = i;
770
771         index = CustomData_get_layer(&dm->faceData, CD_ORIGINDEX);
772         for(i = 0; i < mesh->totface; ++i, ++index)
773                 *index = i;
774         
775         /* works in conjunction with hack during modifier calc, where active mcol
776            layer with weight paint colors is temporarily added */
777         if ((G.f & G_WEIGHTPAINT) &&
778                 (ob && ob==(G.scene->basact?G.scene->basact->object:NULL)))
779                 CustomData_duplicate_referenced_layer(&dm->faceData, CD_MCOL);
780
781         return dm;
782 }
783
784 DerivedMesh *CDDM_from_editmesh(EditMesh *em, Mesh *me)
785 {
786         DerivedMesh *dm = CDDM_new(BLI_countlist(&em->verts),
787                                    BLI_countlist(&em->edges),
788                                    BLI_countlist(&em->faces));
789         CDDerivedMesh *cddm = (CDDerivedMesh*)dm;
790         EditVert *eve;
791         EditEdge *eed;
792         EditFace *efa;
793         MVert *mvert = cddm->mvert;
794         MEdge *medge = cddm->medge;
795         MFace *mface = cddm->mface;
796         int i, *index;
797
798         CustomData_merge(&em->vdata, &dm->vertData, CD_MASK_DERIVEDMESH,
799                          CD_CALLOC, dm->numVertData);
800         /* CustomData_merge(&em->edata, &dm->edgeData, CD_MASK_DERIVEDMESH,
801                          CD_CALLOC, dm->numEdgeData); */
802         CustomData_merge(&em->fdata, &dm->faceData, CD_MASK_DERIVEDMESH,
803                          CD_CALLOC, dm->numFaceData);
804
805         /* set eve->hash to vert index */
806         for(i = 0, eve = em->verts.first; eve; eve = eve->next, ++i)
807                 eve->tmp.l = i;
808
809         /* Need to be able to mark loose edges */
810         for(eed = em->edges.first; eed; eed = eed->next) {
811                 eed->f2 = 0;
812         }
813         for(efa = em->faces.first; efa; efa = efa->next) {
814                 efa->e1->f2 = 1;
815                 efa->e2->f2 = 1;
816                 efa->e3->f2 = 1;
817                 if(efa->e4) efa->e4->f2 = 1;
818         }
819
820         index = dm->getVertDataArray(dm, CD_ORIGINDEX);
821         for(i = 0, eve = em->verts.first; i < dm->numVertData;
822             i++, eve = eve->next, index++) {
823                 MVert *mv = &mvert[i];
824
825                 VECCOPY(mv->co, eve->co);
826
827                 mv->no[0] = eve->no[0] * 32767.0;
828                 mv->no[1] = eve->no[1] * 32767.0;
829                 mv->no[2] = eve->no[2] * 32767.0;
830
831                 mv->mat_nr = 0;
832                 mv->flag = 0;
833
834                 *index = i;
835
836                 CustomData_from_em_block(&em->vdata, &dm->vertData, eve->data, i);
837         }
838
839         index = dm->getEdgeDataArray(dm, CD_ORIGINDEX);
840         for(i = 0, eed = em->edges.first; i < dm->numEdgeData;
841             i++, eed = eed->next, index++) {
842                 MEdge *med = &medge[i];
843
844                 med->v1 = eed->v1->tmp.l;
845                 med->v2 = eed->v2->tmp.l;
846                 med->crease = (unsigned char) (eed->crease * 255.0f);
847                 med->flag = ME_EDGEDRAW|ME_EDGERENDER;
848                 
849                 if(eed->seam) med->flag |= ME_SEAM;
850                 if(eed->sharp) med->flag |= ME_SHARP;
851                 if(!eed->f2) med->flag |= ME_LOOSEEDGE;
852
853                 *index = i;
854
855                 /* CustomData_from_em_block(&em->edata, &dm->edgeData, eed->data, i); */
856         }
857
858         index = dm->getFaceDataArray(dm, CD_ORIGINDEX);
859         for(i = 0, efa = em->faces.first; i < dm->numFaceData;
860             i++, efa = efa->next, index++) {
861                 MFace *mf = &mface[i];
862
863                 mf->v1 = efa->v1->tmp.l;
864                 mf->v2 = efa->v2->tmp.l;
865                 mf->v3 = efa->v3->tmp.l;
866                 mf->v4 = efa->v4 ? efa->v4->tmp.l : 0;
867                 mf->mat_nr = efa->mat_nr;
868                 mf->flag = efa->flag;
869
870                 *index = i;
871
872                 CustomData_from_em_block(&em->fdata, &dm->faceData, efa->data, i);
873                 test_index_face(mf, &dm->faceData, i, efa->v4?4:3);
874         }
875
876         return dm;
877 }
878
879 DerivedMesh *CDDM_copy(DerivedMesh *source)
880 {
881         CDDerivedMesh *cddm = cdDM_create("CDDM_copy cddm");
882         DerivedMesh *dm = &cddm->dm;
883         int numVerts = source->numVertData;
884         int numEdges = source->numEdgeData;
885         int numFaces = source->numFaceData;
886
887         /* this initializes dm, and copies all non mvert/medge/mface layers */
888         DM_from_template(dm, source, numVerts, numEdges, numFaces);
889
890         CustomData_copy_data(&source->vertData, &dm->vertData, 0, 0, numVerts);
891         CustomData_copy_data(&source->edgeData, &dm->edgeData, 0, 0, numEdges);
892         CustomData_copy_data(&source->faceData, &dm->faceData, 0, 0, numFaces);
893
894         /* now add mvert/medge/mface layers */
895         cddm->mvert = source->dupVertArray(source);
896         cddm->medge = source->dupEdgeArray(source);
897         cddm->mface = source->dupFaceArray(source);
898
899         CustomData_add_layer(&dm->vertData, CD_MVERT, CD_ASSIGN, cddm->mvert, numVerts);
900         CustomData_add_layer(&dm->edgeData, CD_MEDGE, CD_ASSIGN, cddm->medge, numEdges);
901         CustomData_add_layer(&dm->faceData, CD_MFACE, CD_ASSIGN, cddm->mface, numFaces);
902
903         return dm;
904 }
905
906 DerivedMesh *CDDM_from_template(DerivedMesh *source,
907                                 int numVerts, int numEdges, int numFaces)
908 {
909         CDDerivedMesh *cddm = cdDM_create("CDDM_from_template dest");
910         DerivedMesh *dm = &cddm->dm;
911
912         /* this does a copy of all non mvert/medge/mface layers */
913         DM_from_template(dm, source, numVerts, numEdges, numFaces);
914
915         /* now add mvert/medge/mface layers */
916         CustomData_add_layer(&dm->vertData, CD_MVERT, CD_CALLOC, NULL, numVerts);
917         CustomData_add_layer(&dm->edgeData, CD_MEDGE, CD_CALLOC, NULL, numEdges);
918         CustomData_add_layer(&dm->faceData, CD_MFACE, CD_CALLOC, NULL, numFaces);
919
920         cddm->mvert = CustomData_get_layer(&dm->vertData, CD_MVERT);
921         cddm->medge = CustomData_get_layer(&dm->edgeData, CD_MEDGE);
922         cddm->mface = CustomData_get_layer(&dm->faceData, CD_MFACE);
923
924         return dm;
925 }
926
927 void CDDM_apply_vert_coords(DerivedMesh *dm, float (*vertCoords)[3])
928 {
929         CDDerivedMesh *cddm = (CDDerivedMesh*)dm;
930         MVert *vert;
931         int i;
932
933         /* this will just return the pointer if it wasn't a referenced layer */
934         vert = CustomData_duplicate_referenced_layer(&dm->vertData, CD_MVERT);
935         cddm->mvert = vert;
936
937         for(i = 0; i < dm->numVertData; ++i, ++vert)
938                 VECCOPY(vert->co, vertCoords[i]);
939 }
940
941 void CDDM_apply_vert_normals(DerivedMesh *dm, short (*vertNormals)[3])
942 {
943         CDDerivedMesh *cddm = (CDDerivedMesh*)dm;
944         MVert *vert;
945         int i;
946
947         /* this will just return the pointer if it wasn't a referenced layer */
948         vert = CustomData_duplicate_referenced_layer(&dm->vertData, CD_MVERT);
949         cddm->mvert = vert;
950
951         for(i = 0; i < dm->numVertData; ++i, ++vert)
952                 VECCOPY(vert->no, vertNormals[i]);
953 }
954
955 /* adapted from mesh_calc_normals */
956 void CDDM_calc_normals(DerivedMesh *dm)
957 {
958         CDDerivedMesh *cddm = (CDDerivedMesh*)dm;
959         float (*temp_nors)[3];
960         float (*face_nors)[3];
961         int i;
962         int numVerts = dm->numVertData;
963         int numFaces = dm->numFaceData;
964         MFace *mf;
965         MVert *mv;
966
967         if(numVerts == 0) return;
968
969         temp_nors = MEM_callocN(numVerts * sizeof(*temp_nors),
970                                 "CDDM_calc_normals temp_nors");
971
972         /* we don't want to overwrite any referenced layers */
973         mv = CustomData_duplicate_referenced_layer(&dm->vertData, CD_MVERT);
974         cddm->mvert = mv;
975
976         /* make a face normal layer if not present */
977         face_nors = CustomData_get_layer(&dm->faceData, CD_NORMAL);
978         if(!face_nors)
979                 face_nors = CustomData_add_layer(&dm->faceData, CD_NORMAL, CD_CALLOC,
980                                                  NULL, dm->numFaceData);
981
982         /* calculate face normals and add to vertex normals */
983         mf = CDDM_get_faces(dm);
984         for(i = 0; i < numFaces; i++, mf++) {
985                 float *f_no = face_nors[i];
986
987                 if(mf->v4)
988                         CalcNormFloat4(mv[mf->v1].co, mv[mf->v2].co,
989                                        mv[mf->v3].co, mv[mf->v4].co, f_no);
990                 else
991                         CalcNormFloat(mv[mf->v1].co, mv[mf->v2].co,
992                                       mv[mf->v3].co, f_no);
993                 
994                 VecAddf(temp_nors[mf->v1], temp_nors[mf->v1], f_no);
995                 VecAddf(temp_nors[mf->v2], temp_nors[mf->v2], f_no);
996                 VecAddf(temp_nors[mf->v3], temp_nors[mf->v3], f_no);
997                 if(mf->v4)
998                         VecAddf(temp_nors[mf->v4], temp_nors[mf->v4], f_no);
999         }
1000
1001         /* normalize vertex normals and assign */
1002         for(i = 0; i < numVerts; i++, mv++) {
1003                 float *no = temp_nors[i];
1004                 
1005                 if (Normalize(no) == 0.0) {
1006                         VECCOPY(no, mv->co);
1007                         Normalize(no);
1008                 }
1009
1010                 mv->no[0] = (short)(no[0] * 32767.0);
1011                 mv->no[1] = (short)(no[1] * 32767.0);
1012                 mv->no[2] = (short)(no[2] * 32767.0);
1013         }
1014         
1015         MEM_freeN(temp_nors);
1016 }
1017
1018 void CDDM_calc_edges(DerivedMesh *dm)
1019 {
1020         CDDerivedMesh *cddm = (CDDerivedMesh*)dm;
1021         CustomData edgeData;
1022         EdgeHashIterator *ehi;
1023         MFace *mf = cddm->mface;
1024         MEdge *med;
1025         EdgeHash *eh = BLI_edgehash_new();
1026         int i, *index, numEdges, maxFaces = dm->numFaceData;
1027
1028         for (i = 0; i < maxFaces; i++, mf++) {
1029                 if (!BLI_edgehash_haskey(eh, mf->v1, mf->v2))
1030                         BLI_edgehash_insert(eh, mf->v1, mf->v2, NULL);
1031                 if (!BLI_edgehash_haskey(eh, mf->v2, mf->v3))
1032                         BLI_edgehash_insert(eh, mf->v2, mf->v3, NULL);
1033                 
1034                 if (mf->v4) {
1035                         if (!BLI_edgehash_haskey(eh, mf->v3, mf->v4))
1036                                 BLI_edgehash_insert(eh, mf->v3, mf->v4, NULL);
1037                         if (!BLI_edgehash_haskey(eh, mf->v4, mf->v1))
1038                                 BLI_edgehash_insert(eh, mf->v4, mf->v1, NULL);
1039                 } else {
1040                         if (!BLI_edgehash_haskey(eh, mf->v3, mf->v1))
1041                                 BLI_edgehash_insert(eh, mf->v3, mf->v1, NULL);
1042                 }
1043         }
1044
1045         numEdges = BLI_edgehash_size(eh);
1046
1047         /* write new edges into a temporary CustomData */
1048         memset(&edgeData, 0, sizeof(edgeData));
1049         CustomData_add_layer(&edgeData, CD_MEDGE, CD_CALLOC, NULL, numEdges);
1050         CustomData_add_layer(&edgeData, CD_ORIGINDEX, CD_CALLOC, NULL, numEdges);
1051
1052         ehi = BLI_edgehashIterator_new(eh);
1053         med = CustomData_get_layer(&edgeData, CD_MEDGE);
1054         index = CustomData_get_layer(&edgeData, CD_ORIGINDEX);
1055         for(i = 0; !BLI_edgehashIterator_isDone(ehi);
1056             BLI_edgehashIterator_step(ehi), ++i, ++med, ++index) {
1057                 BLI_edgehashIterator_getKey(ehi, (int*)&med->v1, (int*)&med->v2);
1058
1059                 med->flag = ME_EDGEDRAW|ME_EDGERENDER;
1060                 *index = ORIGINDEX_NONE;
1061         }
1062         BLI_edgehashIterator_free(ehi);
1063
1064         /* free old CustomData and assign new one */
1065         CustomData_free(&dm->edgeData, dm->numVertData);
1066         dm->edgeData = edgeData;
1067         dm->numEdgeData = numEdges;
1068
1069         cddm->medge = CustomData_get_layer(&dm->edgeData, CD_MEDGE);
1070
1071         BLI_edgehash_free(eh, NULL);
1072 }
1073
1074 void CDDM_lower_num_verts(DerivedMesh *dm, int numVerts)
1075 {
1076         if (numVerts < dm->numVertData)
1077                 CustomData_free_elem(&dm->vertData, numVerts, dm->numVertData-numVerts);
1078
1079         dm->numVertData = numVerts;
1080 }
1081
1082 void CDDM_lower_num_edges(DerivedMesh *dm, int numEdges)
1083 {
1084         if (numEdges < dm->numEdgeData)
1085                 CustomData_free_elem(&dm->edgeData, numEdges, dm->numEdgeData-numEdges);
1086
1087         dm->numEdgeData = numEdges;
1088 }
1089
1090 void CDDM_lower_num_faces(DerivedMesh *dm, int numFaces)
1091 {
1092         if (numFaces < dm->numFaceData)
1093                 CustomData_free_elem(&dm->faceData, numFaces, dm->numFaceData-numFaces);
1094
1095         dm->numFaceData = numFaces;
1096 }
1097
1098 MVert *CDDM_get_vert(DerivedMesh *dm, int index)
1099 {
1100         return &((CDDerivedMesh*)dm)->mvert[index];
1101 }
1102
1103 MEdge *CDDM_get_edge(DerivedMesh *dm, int index)
1104 {
1105         return &((CDDerivedMesh*)dm)->medge[index];
1106 }
1107
1108 MFace *CDDM_get_face(DerivedMesh *dm, int index)
1109 {
1110         return &((CDDerivedMesh*)dm)->mface[index];
1111 }
1112
1113 MVert *CDDM_get_verts(DerivedMesh *dm)
1114 {
1115         return ((CDDerivedMesh*)dm)->mvert;
1116 }
1117
1118 MEdge *CDDM_get_edges(DerivedMesh *dm)
1119 {
1120         return ((CDDerivedMesh*)dm)->medge;
1121 }
1122
1123 MFace *CDDM_get_faces(DerivedMesh *dm)
1124 {
1125         return ((CDDerivedMesh*)dm)->mface;
1126 }
1127