Particles
[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         MFace *mf = cddm->mface;
181         MTFace *tf = DM_get_face_data_layer(dm, CD_MTFACE);
182         int i;
183
184         if(mf) {
185                 glBegin(GL_LINES);
186                 for(i = 0; i < dm->numFaceData; i++, mf++, tf++) {
187                         if(!(mf->flag&ME_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)              { if(nors) nors += 3; continue; }
403                                 if(drawParamsMapped) flag = drawParamsMapped(userData, orig);
404                                 else    { if(nors) nors += 3; continue; }
405                         }
406                         else
407                                 if(drawParamsMapped) flag = drawParamsMapped(userData, i);
408                                 else    { if(nors) nors += 3; continue; }
409                 }
410                 
411                 if(flag != 0) { /* if the flag is 0 it means the face is hidden or invisible */
412                         if (flag==1 && mcol)
413                                 cp= (unsigned char*) &mcol[i*4];
414
415                         if(!(mf->flag&ME_SMOOTH)) {
416                                 if (nors) {
417                                         glNormal3fv(nors);
418                                 }
419                                 else {
420                                         /* TODO make this better (cache facenormals as layer?) */
421                                         float nor[3];
422                                         if(mf->v4) {
423                                                 CalcNormFloat4(mv[mf->v1].co, mv[mf->v2].co,
424                                                                            mv[mf->v3].co, mv[mf->v4].co,
425                                                                            nor);
426                                         } else {
427                                                 CalcNormFloat(mv[mf->v1].co, mv[mf->v2].co,
428                                                                           mv[mf->v3].co, nor);
429                                         }
430                                         glNormal3fv(nor);
431                                 }
432                         }
433
434                         glBegin(mf->v4?GL_QUADS:GL_TRIANGLES);
435                         if(tf) glTexCoord2fv(tf[i].uv[0]);
436                         if(cp) glColor3ub(cp[3], cp[2], cp[1]);
437                         mvert = &mv[mf->v1];
438                         if(mf->flag&ME_SMOOTH) glNormal3sv(mvert->no);
439                         glVertex3fv(mvert->co);
440                                 
441                         if(tf) glTexCoord2fv(tf[i].uv[1]);
442                         if(cp) glColor3ub(cp[7], cp[6], cp[5]);
443                         mvert = &mv[mf->v2];
444                         if(mf->flag&ME_SMOOTH) glNormal3sv(mvert->no);
445                         glVertex3fv(mvert->co);
446
447                         if(tf) glTexCoord2fv(tf[i].uv[2]);
448                         if(cp) glColor3ub(cp[11], cp[10], cp[9]);
449                         mvert = &mv[mf->v3];
450                         if(mf->flag&ME_SMOOTH) glNormal3sv(mvert->no);
451                         glVertex3fv(mvert->co);
452
453                         if(mf->v4) {
454                                 if(tf) glTexCoord2fv(tf[i].uv[3]);
455                                 if(cp) glColor3ub(cp[15], cp[14], cp[13]);
456                                 mvert = &mv[mf->v4];
457                                 if(mf->flag&ME_SMOOTH) glNormal3sv(mvert->no);
458                                 glVertex3fv(mvert->co);
459                         }
460                         glEnd();
461                 }
462                 
463                 if(nors) nors += 3;
464         }
465 }
466
467 static void cdDM_drawFacesTex(DerivedMesh *dm, int (*setDrawOptions)(MTFace *tface, MCol *mcol, int matnr))
468 {
469         cdDM_drawFacesTex_common(dm, setDrawOptions, NULL, NULL);
470 }
471
472 static void cdDM_drawMappedFaces(DerivedMesh *dm, int (*setDrawOptions)(void *userData, int index, int *drawSmooth_r), void *userData, int useColors)
473 {
474         CDDerivedMesh *cddm = (CDDerivedMesh*) dm;
475         MVert *mv = cddm->mvert;
476         MFace *mf = cddm->mface;
477         MCol *mc = DM_get_face_data_layer(dm, CD_MCOL);
478         float *nors= dm->getFaceDataArray(dm, CD_NORMAL);
479         int i, orig, *index = DM_get_face_data_layer(dm, CD_ORIGINDEX);
480
481         for(i = 0; i < dm->numFaceData; i++, mf++) {
482                 int drawSmooth = (mf->flag & ME_SMOOTH);
483
484                 if(index) {
485                         orig = *index++;
486                         if(setDrawOptions && orig == ORIGINDEX_NONE)
487                                 { if(nors) nors += 3; continue; }
488                 }
489                 else
490                         orig = i;
491
492                 if(!setDrawOptions || setDrawOptions(userData, orig, &drawSmooth)) {
493                         unsigned char *cp = NULL;
494
495                         if(useColors && mc)
496                                 cp = (unsigned char *)&mc[i * 4];
497
498                         glShadeModel(drawSmooth?GL_SMOOTH:GL_FLAT);
499                         glBegin(mf->v4?GL_QUADS:GL_TRIANGLES);
500
501                         if (!drawSmooth) {
502                                 if (nors) {
503                                         glNormal3fv(nors);
504                                 }
505                                 else {
506                                         /* TODO make this better (cache facenormals as layer?) */
507                                         float nor[3];
508                                         if(mf->v4) {
509                                                 CalcNormFloat4(mv[mf->v1].co, mv[mf->v2].co,
510                                                                            mv[mf->v3].co, mv[mf->v4].co,
511                                                                            nor);
512                                         } else {
513                                                 CalcNormFloat(mv[mf->v1].co, mv[mf->v2].co,
514                                                                           mv[mf->v3].co, nor);
515                                         }
516                                         glNormal3fv(nor);
517                                 }
518
519                                 if(cp) glColor3ub(cp[3], cp[2], cp[1]);
520                                 glVertex3fv(mv[mf->v1].co);
521                                 if(cp) glColor3ub(cp[7], cp[6], cp[5]);
522                                 glVertex3fv(mv[mf->v2].co);
523                                 if(cp) glColor3ub(cp[11], cp[10], cp[9]);
524                                 glVertex3fv(mv[mf->v3].co);
525                                 if(mf->v4) {
526                                         if(cp) glColor3ub(cp[15], cp[14], cp[13]);
527                                         glVertex3fv(mv[mf->v4].co);
528                                 }
529                         } else {
530                                 if(cp) glColor3ub(cp[3], cp[2], cp[1]);
531                                 glNormal3sv(mv[mf->v1].no);
532                                 glVertex3fv(mv[mf->v1].co);
533                                 if(cp) glColor3ub(cp[7], cp[6], cp[5]);
534                                 glNormal3sv(mv[mf->v2].no);
535                                 glVertex3fv(mv[mf->v2].co);
536                                 if(cp) glColor3ub(cp[11], cp[10], cp[9]);
537                                 glNormal3sv(mv[mf->v3].no);
538                                 glVertex3fv(mv[mf->v3].co);
539                                 if(mf->v4) {
540                                         if(cp) glColor3ub(cp[15], cp[14], cp[13]);
541                                         glNormal3sv(mv[mf->v4].no);
542                                         glVertex3fv(mv[mf->v4].co);
543                                 }
544                         }
545
546                         glEnd();
547                 }
548                 
549                 if (nors) nors += 3;
550         }
551 }
552
553 static void cdDM_drawMappedFacesTex(DerivedMesh *dm, int (*setDrawOptions)(void *userData, int index), void *userData)
554 {
555         cdDM_drawFacesTex_common(dm, NULL, setDrawOptions, userData);
556 }
557
558 static void cdDM_drawMappedEdges(DerivedMesh *dm, int (*setDrawOptions)(void *userData, int index), void *userData)
559 {
560         CDDerivedMesh *cddm = (CDDerivedMesh*) dm;
561         MVert *vert = cddm->mvert;
562         MEdge *edge = cddm->medge;
563         int i, orig, *index = DM_get_edge_data_layer(dm, CD_ORIGINDEX);
564
565         glBegin(GL_LINES);
566         for(i = 0; i < dm->numEdgeData; i++, edge++) {
567                 if(index) {
568                         orig = *index++;
569                         if(setDrawOptions && orig == ORIGINDEX_NONE) continue;
570                 }
571                 else
572                         orig = i;
573
574                 if(!setDrawOptions || setDrawOptions(userData, orig)) {
575                         glVertex3fv(vert[edge->v1].co);
576                         glVertex3fv(vert[edge->v2].co);
577                 }
578         }
579         glEnd();
580 }
581
582 static void cdDM_foreachMappedVert(
583                            DerivedMesh *dm,
584                            void (*func)(void *userData, int index, float *co,
585                                         float *no_f, short *no_s),
586                            void *userData)
587 {
588         MVert *mv = CDDM_get_verts(dm);
589         int i, orig, *index = DM_get_vert_data_layer(dm, CD_ORIGINDEX);
590
591         for(i = 0; i < dm->numVertData; i++, mv++) {
592                 if(index) {
593                         orig = *index++;
594                         if(orig == ORIGINDEX_NONE) continue;
595                         func(userData, orig, mv->co, NULL, mv->no);
596                 }
597                 else
598                         func(userData, i, mv->co, NULL, mv->no);
599         }
600 }
601
602 static void cdDM_foreachMappedEdge(
603                            DerivedMesh *dm,
604                            void (*func)(void *userData, int index,
605                                         float *v0co, float *v1co),
606                            void *userData)
607 {
608         CDDerivedMesh *cddm = (CDDerivedMesh*) dm;
609         MVert *mv = cddm->mvert;
610         MEdge *med = cddm->medge;
611         int i, orig, *index = DM_get_edge_data_layer(dm, CD_ORIGINDEX);
612
613         for(i = 0; i < dm->numEdgeData; i++, med++) {
614                 if (index) {
615                         orig = *index++;
616                         if(orig == ORIGINDEX_NONE) continue;
617                         func(userData, orig, mv[med->v1].co, mv[med->v2].co);
618                 }
619                 else
620                         func(userData, i, mv[med->v1].co, mv[med->v2].co);
621         }
622 }
623
624 static void cdDM_foreachMappedFaceCenter(
625                            DerivedMesh *dm,
626                            void (*func)(void *userData, int index,
627                                         float *cent, float *no),
628                            void *userData)
629 {
630         CDDerivedMesh *cddm = (CDDerivedMesh*)dm;
631         MVert *mv = cddm->mvert;
632         MFace *mf = cddm->mface;
633         int i, orig, *index = DM_get_face_data_layer(dm, CD_ORIGINDEX);
634
635         for(i = 0; i < dm->numFaceData; i++, mf++) {
636                 float cent[3];
637                 float no[3];
638
639                 if (index) {
640                         orig = *index++;
641                         if(orig == ORIGINDEX_NONE) continue;
642                 }
643                 else
644                         orig = i;
645
646                 VECCOPY(cent, mv[mf->v1].co);
647                 VecAddf(cent, cent, mv[mf->v2].co);
648                 VecAddf(cent, cent, mv[mf->v3].co);
649
650                 if (mf->v4) {
651                         CalcNormFloat4(mv[mf->v1].co, mv[mf->v2].co,
652                                        mv[mf->v3].co, mv[mf->v4].co, no);
653                         VecAddf(cent, cent, mv[mf->v4].co);
654                         VecMulf(cent, 0.25f);
655                 } else {
656                         CalcNormFloat(mv[mf->v1].co, mv[mf->v2].co,
657                                       mv[mf->v3].co, no);
658                         VecMulf(cent, 0.33333333333f);
659                 }
660
661                 func(userData, orig, cent, no);
662         }
663 }
664
665 static void cdDM_release(DerivedMesh *dm)
666 {
667         CDDerivedMesh *cddm = (CDDerivedMesh*)dm;
668
669         if (DM_release(dm))
670                 MEM_freeN(cddm);
671 }
672
673 /**************** CDDM interface functions ****************/
674 static CDDerivedMesh *cdDM_create(const char *desc)
675 {
676         CDDerivedMesh *cddm;
677         DerivedMesh *dm;
678
679         cddm = MEM_callocN(sizeof(*cddm), desc);
680         dm = &cddm->dm;
681
682         dm->getMinMax = cdDM_getMinMax;
683
684         dm->getNumVerts = cdDM_getNumVerts;
685         dm->getNumFaces = cdDM_getNumFaces;
686         dm->getNumEdges = cdDM_getNumEdges;
687
688         dm->getVert = cdDM_getVert;
689         dm->getEdge = cdDM_getEdge;
690         dm->getFace = cdDM_getFace;
691         dm->copyVertArray = cdDM_copyVertArray;
692         dm->copyEdgeArray = cdDM_copyEdgeArray;
693         dm->copyFaceArray = cdDM_copyFaceArray;
694         dm->getVertData = DM_get_vert_data;
695         dm->getEdgeData = DM_get_edge_data;
696         dm->getFaceData = DM_get_face_data;
697         dm->getVertDataArray = DM_get_vert_data_layer;
698         dm->getEdgeDataArray = DM_get_edge_data_layer;
699         dm->getFaceDataArray = DM_get_face_data_layer;
700
701         dm->getVertCos = cdDM_getVertCos;
702         dm->getVertCo = cdDM_getVertCo;
703         dm->getVertNo = cdDM_getVertNo;
704
705         dm->drawVerts = cdDM_drawVerts;
706
707         dm->drawUVEdges = cdDM_drawUVEdges;
708         dm->drawEdges = cdDM_drawEdges;
709         dm->drawLooseEdges = cdDM_drawLooseEdges;
710         dm->drawMappedEdges = cdDM_drawMappedEdges;
711
712         dm->drawFacesSolid = cdDM_drawFacesSolid;
713         dm->drawFacesColored = cdDM_drawFacesColored;
714         dm->drawFacesTex = cdDM_drawFacesTex;
715         dm->drawMappedFaces = cdDM_drawMappedFaces;
716         dm->drawMappedFacesTex = cdDM_drawMappedFacesTex;
717
718         dm->foreachMappedVert = cdDM_foreachMappedVert;
719         dm->foreachMappedEdge = cdDM_foreachMappedEdge;
720         dm->foreachMappedFaceCenter = cdDM_foreachMappedFaceCenter;
721
722         dm->release = cdDM_release;
723
724         return cddm;
725 }
726
727 DerivedMesh *CDDM_new(int numVerts, int numEdges, int numFaces)
728 {
729         CDDerivedMesh *cddm = cdDM_create("CDDM_new dm");
730         DerivedMesh *dm = &cddm->dm;
731
732         DM_init(dm, numVerts, numEdges, numFaces);
733
734         CustomData_add_layer(&dm->vertData, CD_MVERT, CD_CALLOC, NULL, numVerts);
735         CustomData_add_layer(&dm->edgeData, CD_MEDGE, CD_CALLOC, NULL, numEdges);
736         CustomData_add_layer(&dm->faceData, CD_MFACE, CD_CALLOC, NULL, numFaces);
737
738         cddm->mvert = CustomData_get_layer(&dm->vertData, CD_MVERT);
739         cddm->medge = CustomData_get_layer(&dm->edgeData, CD_MEDGE);
740         cddm->mface = CustomData_get_layer(&dm->faceData, CD_MFACE);
741
742         return dm;
743 }
744
745 DerivedMesh *CDDM_from_mesh(Mesh *mesh, Object *ob)
746 {
747         CDDerivedMesh *cddm = cdDM_create("CDDM_from_mesh dm");
748         DerivedMesh *dm = &cddm->dm;
749         int i, *index;
750
751         /* this does a referenced copy, the only new layers being ORIGINDEX */
752
753         DM_init(dm, mesh->totvert, mesh->totedge, mesh->totface);
754         dm->deformedOnly = 1;
755
756         CustomData_merge(&mesh->vdata, &dm->vertData, CD_MASK_MESH, CD_REFERENCE,
757                          mesh->totvert);
758         CustomData_merge(&mesh->edata, &dm->edgeData, CD_MASK_MESH, CD_REFERENCE,
759                          mesh->totedge);
760         CustomData_merge(&mesh->fdata, &dm->faceData, CD_MASK_MESH, CD_REFERENCE,
761                          mesh->totface);
762
763         cddm->mvert = CustomData_get_layer(&dm->vertData, CD_MVERT);
764         cddm->medge = CustomData_get_layer(&dm->edgeData, CD_MEDGE);
765         cddm->mface = CustomData_get_layer(&dm->faceData, CD_MFACE);
766
767         index = CustomData_get_layer(&dm->vertData, CD_ORIGINDEX);
768         for(i = 0; i < mesh->totvert; ++i, ++index)
769                 *index = i;
770
771         index = CustomData_get_layer(&dm->edgeData, CD_ORIGINDEX);
772         for(i = 0; i < mesh->totedge; ++i, ++index)
773                 *index = i;
774
775         index = CustomData_get_layer(&dm->faceData, CD_ORIGINDEX);
776         for(i = 0; i < mesh->totface; ++i, ++index)
777                 *index = i;
778         
779         /* works in conjunction with hack during modifier calc, where active mcol
780            layer with weight paint colors is temporarily added */
781         if ((G.f & G_WEIGHTPAINT) &&
782                 (ob && ob==(G.scene->basact?G.scene->basact->object:NULL)))
783                 CustomData_duplicate_referenced_layer(&dm->faceData, CD_MCOL);
784
785         return dm;
786 }
787
788 DerivedMesh *CDDM_from_editmesh(EditMesh *em, Mesh *me)
789 {
790         DerivedMesh *dm = CDDM_new(BLI_countlist(&em->verts),
791                                    BLI_countlist(&em->edges),
792                                    BLI_countlist(&em->faces));
793         CDDerivedMesh *cddm = (CDDerivedMesh*)dm;
794         EditVert *eve;
795         EditEdge *eed;
796         EditFace *efa;
797         MVert *mvert = cddm->mvert;
798         MEdge *medge = cddm->medge;
799         MFace *mface = cddm->mface;
800         int i, *index;
801
802         dm->deformedOnly = 1;
803
804         CustomData_merge(&em->vdata, &dm->vertData, CD_MASK_DERIVEDMESH,
805                          CD_CALLOC, dm->numVertData);
806         /* CustomData_merge(&em->edata, &dm->edgeData, CD_MASK_DERIVEDMESH,
807                          CD_CALLOC, dm->numEdgeData); */
808         CustomData_merge(&em->fdata, &dm->faceData, CD_MASK_DERIVEDMESH,
809                          CD_CALLOC, dm->numFaceData);
810
811         /* set eve->hash to vert index */
812         for(i = 0, eve = em->verts.first; eve; eve = eve->next, ++i)
813                 eve->tmp.l = i;
814
815         /* Need to be able to mark loose edges */
816         for(eed = em->edges.first; eed; eed = eed->next) {
817                 eed->f2 = 0;
818         }
819         for(efa = em->faces.first; efa; efa = efa->next) {
820                 efa->e1->f2 = 1;
821                 efa->e2->f2 = 1;
822                 efa->e3->f2 = 1;
823                 if(efa->e4) efa->e4->f2 = 1;
824         }
825
826         index = dm->getVertDataArray(dm, CD_ORIGINDEX);
827         for(i = 0, eve = em->verts.first; i < dm->numVertData;
828             i++, eve = eve->next, index++) {
829                 MVert *mv = &mvert[i];
830
831                 VECCOPY(mv->co, eve->co);
832
833                 mv->no[0] = eve->no[0] * 32767.0;
834                 mv->no[1] = eve->no[1] * 32767.0;
835                 mv->no[2] = eve->no[2] * 32767.0;
836
837                 mv->mat_nr = 0;
838                 mv->flag = 0;
839
840                 *index = i;
841
842                 CustomData_from_em_block(&em->vdata, &dm->vertData, eve->data, i);
843         }
844
845         index = dm->getEdgeDataArray(dm, CD_ORIGINDEX);
846         for(i = 0, eed = em->edges.first; i < dm->numEdgeData;
847             i++, eed = eed->next, index++) {
848                 MEdge *med = &medge[i];
849
850                 med->v1 = eed->v1->tmp.l;
851                 med->v2 = eed->v2->tmp.l;
852                 med->crease = (unsigned char) (eed->crease * 255.0f);
853                 med->flag = ME_EDGEDRAW|ME_EDGERENDER;
854                 
855                 if(eed->seam) med->flag |= ME_SEAM;
856                 if(eed->sharp) med->flag |= ME_SHARP;
857                 if(!eed->f2) med->flag |= ME_LOOSEEDGE;
858
859                 *index = i;
860
861                 /* CustomData_from_em_block(&em->edata, &dm->edgeData, eed->data, i); */
862         }
863
864         index = dm->getFaceDataArray(dm, CD_ORIGINDEX);
865         for(i = 0, efa = em->faces.first; i < dm->numFaceData;
866             i++, efa = efa->next, index++) {
867                 MFace *mf = &mface[i];
868
869                 mf->v1 = efa->v1->tmp.l;
870                 mf->v2 = efa->v2->tmp.l;
871                 mf->v3 = efa->v3->tmp.l;
872                 mf->v4 = efa->v4 ? efa->v4->tmp.l : 0;
873                 mf->mat_nr = efa->mat_nr;
874                 mf->flag = efa->flag;
875
876                 *index = i;
877
878                 CustomData_from_em_block(&em->fdata, &dm->faceData, efa->data, i);
879                 test_index_face(mf, &dm->faceData, i, efa->v4?4:3);
880         }
881
882         return dm;
883 }
884
885 DerivedMesh *CDDM_copy(DerivedMesh *source)
886 {
887         CDDerivedMesh *cddm = cdDM_create("CDDM_copy cddm");
888         DerivedMesh *dm = &cddm->dm;
889         int numVerts = source->numVertData;
890         int numEdges = source->numEdgeData;
891         int numFaces = source->numFaceData;
892
893         /* this initializes dm, and copies all non mvert/medge/mface layers */
894         DM_from_template(dm, source, numVerts, numEdges, numFaces);
895         dm->deformedOnly = source->deformedOnly;
896
897         CustomData_copy_data(&source->vertData, &dm->vertData, 0, 0, numVerts);
898         CustomData_copy_data(&source->edgeData, &dm->edgeData, 0, 0, numEdges);
899         CustomData_copy_data(&source->faceData, &dm->faceData, 0, 0, numFaces);
900
901         /* now add mvert/medge/mface layers */
902         cddm->mvert = source->dupVertArray(source);
903         cddm->medge = source->dupEdgeArray(source);
904         cddm->mface = source->dupFaceArray(source);
905
906         CustomData_add_layer(&dm->vertData, CD_MVERT, CD_ASSIGN, cddm->mvert, numVerts);
907         CustomData_add_layer(&dm->edgeData, CD_MEDGE, CD_ASSIGN, cddm->medge, numEdges);
908         CustomData_add_layer(&dm->faceData, CD_MFACE, CD_ASSIGN, cddm->mface, numFaces);
909
910         return dm;
911 }
912
913 DerivedMesh *CDDM_from_template(DerivedMesh *source,
914                                 int numVerts, int numEdges, int numFaces)
915 {
916         CDDerivedMesh *cddm = cdDM_create("CDDM_from_template dest");
917         DerivedMesh *dm = &cddm->dm;
918
919         /* this does a copy of all non mvert/medge/mface layers */
920         DM_from_template(dm, source, numVerts, numEdges, numFaces);
921
922         /* now add mvert/medge/mface layers */
923         CustomData_add_layer(&dm->vertData, CD_MVERT, CD_CALLOC, NULL, numVerts);
924         CustomData_add_layer(&dm->edgeData, CD_MEDGE, CD_CALLOC, NULL, numEdges);
925         CustomData_add_layer(&dm->faceData, CD_MFACE, CD_CALLOC, NULL, numFaces);
926
927         cddm->mvert = CustomData_get_layer(&dm->vertData, CD_MVERT);
928         cddm->medge = CustomData_get_layer(&dm->edgeData, CD_MEDGE);
929         cddm->mface = CustomData_get_layer(&dm->faceData, CD_MFACE);
930
931         return dm;
932 }
933
934 void CDDM_apply_vert_coords(DerivedMesh *dm, float (*vertCoords)[3])
935 {
936         CDDerivedMesh *cddm = (CDDerivedMesh*)dm;
937         MVert *vert;
938         int i;
939
940         /* this will just return the pointer if it wasn't a referenced layer */
941         vert = CustomData_duplicate_referenced_layer(&dm->vertData, CD_MVERT);
942         cddm->mvert = vert;
943
944         for(i = 0; i < dm->numVertData; ++i, ++vert)
945                 VECCOPY(vert->co, vertCoords[i]);
946 }
947
948 void CDDM_apply_vert_normals(DerivedMesh *dm, short (*vertNormals)[3])
949 {
950         CDDerivedMesh *cddm = (CDDerivedMesh*)dm;
951         MVert *vert;
952         int i;
953
954         /* this will just return the pointer if it wasn't a referenced layer */
955         vert = CustomData_duplicate_referenced_layer(&dm->vertData, CD_MVERT);
956         cddm->mvert = vert;
957
958         for(i = 0; i < dm->numVertData; ++i, ++vert)
959                 VECCOPY(vert->no, vertNormals[i]);
960 }
961
962 /* adapted from mesh_calc_normals */
963 void CDDM_calc_normals(DerivedMesh *dm)
964 {
965         CDDerivedMesh *cddm = (CDDerivedMesh*)dm;
966         float (*temp_nors)[3];
967         float (*face_nors)[3];
968         int i;
969         int numVerts = dm->numVertData;
970         int numFaces = dm->numFaceData;
971         MFace *mf;
972         MVert *mv;
973
974         if(numVerts == 0) return;
975
976         temp_nors = MEM_callocN(numVerts * sizeof(*temp_nors),
977                                 "CDDM_calc_normals temp_nors");
978
979         /* we don't want to overwrite any referenced layers */
980         mv = CustomData_duplicate_referenced_layer(&dm->vertData, CD_MVERT);
981         cddm->mvert = mv;
982
983         /* make a face normal layer if not present */
984         face_nors = CustomData_get_layer(&dm->faceData, CD_NORMAL);
985         if(!face_nors)
986                 face_nors = CustomData_add_layer(&dm->faceData, CD_NORMAL, CD_CALLOC,
987                                                  NULL, dm->numFaceData);
988
989         /* calculate face normals and add to vertex normals */
990         mf = CDDM_get_faces(dm);
991         for(i = 0; i < numFaces; i++, mf++) {
992                 float *f_no = face_nors[i];
993
994                 if(mf->v4)
995                         CalcNormFloat4(mv[mf->v1].co, mv[mf->v2].co,
996                                        mv[mf->v3].co, mv[mf->v4].co, f_no);
997                 else
998                         CalcNormFloat(mv[mf->v1].co, mv[mf->v2].co,
999                                       mv[mf->v3].co, f_no);
1000                 
1001                 VecAddf(temp_nors[mf->v1], temp_nors[mf->v1], f_no);
1002                 VecAddf(temp_nors[mf->v2], temp_nors[mf->v2], f_no);
1003                 VecAddf(temp_nors[mf->v3], temp_nors[mf->v3], f_no);
1004                 if(mf->v4)
1005                         VecAddf(temp_nors[mf->v4], temp_nors[mf->v4], f_no);
1006         }
1007
1008         /* normalize vertex normals and assign */
1009         for(i = 0; i < numVerts; i++, mv++) {
1010                 float *no = temp_nors[i];
1011                 
1012                 if (Normalize(no) == 0.0) {
1013                         VECCOPY(no, mv->co);
1014                         Normalize(no);
1015                 }
1016
1017                 mv->no[0] = (short)(no[0] * 32767.0);
1018                 mv->no[1] = (short)(no[1] * 32767.0);
1019                 mv->no[2] = (short)(no[2] * 32767.0);
1020         }
1021         
1022         MEM_freeN(temp_nors);
1023 }
1024
1025 void CDDM_calc_edges(DerivedMesh *dm)
1026 {
1027         CDDerivedMesh *cddm = (CDDerivedMesh*)dm;
1028         CustomData edgeData;
1029         EdgeHashIterator *ehi;
1030         MFace *mf = cddm->mface;
1031         MEdge *med;
1032         EdgeHash *eh = BLI_edgehash_new();
1033         int i, *index, numEdges, maxFaces = dm->numFaceData;
1034
1035         for (i = 0; i < maxFaces; i++, mf++) {
1036                 if (!BLI_edgehash_haskey(eh, mf->v1, mf->v2))
1037                         BLI_edgehash_insert(eh, mf->v1, mf->v2, NULL);
1038                 if (!BLI_edgehash_haskey(eh, mf->v2, mf->v3))
1039                         BLI_edgehash_insert(eh, mf->v2, mf->v3, NULL);
1040                 
1041                 if (mf->v4) {
1042                         if (!BLI_edgehash_haskey(eh, mf->v3, mf->v4))
1043                                 BLI_edgehash_insert(eh, mf->v3, mf->v4, NULL);
1044                         if (!BLI_edgehash_haskey(eh, mf->v4, mf->v1))
1045                                 BLI_edgehash_insert(eh, mf->v4, mf->v1, NULL);
1046                 } else {
1047                         if (!BLI_edgehash_haskey(eh, mf->v3, mf->v1))
1048                                 BLI_edgehash_insert(eh, mf->v3, mf->v1, NULL);
1049                 }
1050         }
1051
1052         numEdges = BLI_edgehash_size(eh);
1053
1054         /* write new edges into a temporary CustomData */
1055         memset(&edgeData, 0, sizeof(edgeData));
1056         CustomData_add_layer(&edgeData, CD_MEDGE, CD_CALLOC, NULL, numEdges);
1057         CustomData_add_layer(&edgeData, CD_ORIGINDEX, CD_CALLOC, NULL, numEdges);
1058
1059         ehi = BLI_edgehashIterator_new(eh);
1060         med = CustomData_get_layer(&edgeData, CD_MEDGE);
1061         index = CustomData_get_layer(&edgeData, CD_ORIGINDEX);
1062         for(i = 0; !BLI_edgehashIterator_isDone(ehi);
1063             BLI_edgehashIterator_step(ehi), ++i, ++med, ++index) {
1064                 BLI_edgehashIterator_getKey(ehi, (int*)&med->v1, (int*)&med->v2);
1065
1066                 med->flag = ME_EDGEDRAW|ME_EDGERENDER;
1067                 *index = ORIGINDEX_NONE;
1068         }
1069         BLI_edgehashIterator_free(ehi);
1070
1071         /* free old CustomData and assign new one */
1072         CustomData_free(&dm->edgeData, dm->numVertData);
1073         dm->edgeData = edgeData;
1074         dm->numEdgeData = numEdges;
1075
1076         cddm->medge = CustomData_get_layer(&dm->edgeData, CD_MEDGE);
1077
1078         BLI_edgehash_free(eh, NULL);
1079 }
1080
1081 void CDDM_lower_num_verts(DerivedMesh *dm, int numVerts)
1082 {
1083         if (numVerts < dm->numVertData)
1084                 CustomData_free_elem(&dm->vertData, numVerts, dm->numVertData-numVerts);
1085
1086         dm->numVertData = numVerts;
1087 }
1088
1089 void CDDM_lower_num_edges(DerivedMesh *dm, int numEdges)
1090 {
1091         if (numEdges < dm->numEdgeData)
1092                 CustomData_free_elem(&dm->edgeData, numEdges, dm->numEdgeData-numEdges);
1093
1094         dm->numEdgeData = numEdges;
1095 }
1096
1097 void CDDM_lower_num_faces(DerivedMesh *dm, int numFaces)
1098 {
1099         if (numFaces < dm->numFaceData)
1100                 CustomData_free_elem(&dm->faceData, numFaces, dm->numFaceData-numFaces);
1101
1102         dm->numFaceData = numFaces;
1103 }
1104
1105 MVert *CDDM_get_vert(DerivedMesh *dm, int index)
1106 {
1107         return &((CDDerivedMesh*)dm)->mvert[index];
1108 }
1109
1110 MEdge *CDDM_get_edge(DerivedMesh *dm, int index)
1111 {
1112         return &((CDDerivedMesh*)dm)->medge[index];
1113 }
1114
1115 MFace *CDDM_get_face(DerivedMesh *dm, int index)
1116 {
1117         return &((CDDerivedMesh*)dm)->mface[index];
1118 }
1119
1120 MVert *CDDM_get_verts(DerivedMesh *dm)
1121 {
1122         return ((CDDerivedMesh*)dm)->mvert;
1123 }
1124
1125 MEdge *CDDM_get_edges(DerivedMesh *dm)
1126 {
1127         return ((CDDerivedMesh*)dm)->medge;
1128 }
1129
1130 MFace *CDDM_get_faces(DerivedMesh *dm)
1131 {
1132         return ((CDDerivedMesh*)dm)->mface;
1133 }
1134