b796d8f0216e8a90ef79fe20d40587c4f552a950
[blender-staging.git] / source / blender / blenkernel / intern / modifier.c
1 #include "string.h"
2 #include "stdarg.h"
3 #include "math.h"
4
5 #include "BLI_blenlib.h"
6 #include "BLI_rand.h"
7 #include "BLI_arithb.h"
8 #include "BLI_edgehash.h"
9
10 #include "MEM_guardedalloc.h"
11
12 #include "DNA_armature_types.h"
13 #include "DNA_effect_types.h"
14 #include "DNA_mesh_types.h"
15 #include "DNA_meshdata_types.h"
16 #include "DNA_modifier_types.h"
17 #include "DNA_object_types.h"
18 #include "DNA_object_force.h"
19 #include "DNA_scene_types.h"
20 #include "DNA_curve_types.h"
21
22 #include "BLI_editVert.h"
23
24 #include "MTC_matrixops.h"
25 #include "MTC_vectorops.h"
26
27 #include "BKE_anim.h"
28 #include "BKE_bad_level_calls.h"
29 #include "BKE_global.h"
30 #include "BKE_utildefines.h"
31 #include "BKE_DerivedMesh.h"
32 #include "BKE_booleanops.h"
33 #include "BKE_displist.h"
34 #include "BKE_modifier.h"
35 #include "BKE_lattice.h"
36 #include "BKE_subsurf.h"
37 #include "BKE_object.h"
38 #include "BKE_mesh.h"
39 #include "BKE_softbody.h"
40 #include "depsgraph_private.h"
41
42 #include "LOD_DependKludge.h"
43 #include "LOD_decimation.h"
44
45 #include "CCGSubSurf.h"
46
47 /* helper function for modifiers - usage is of this is discouraged, but
48    avoids duplicate modifier code for DispListMesh and EditMesh */
49
50 DispListMesh *displistmesh_from_editmesh(EditMesh *em)
51 {
52         DispListMesh *outDLM = MEM_callocN(sizeof(*outDLM), "em_mod_dlm");
53         EditVert *eve, *preveve;
54         EditEdge *eed;
55         EditFace *efa;
56         int i;
57
58         for (i=0,eve=em->verts.first; eve; eve= eve->next)
59                 eve->prev = (EditVert*) i++;
60
61         outDLM->totvert = BLI_countlist(&em->verts);
62         outDLM->totedge = BLI_countlist(&em->edges);
63         outDLM->totface = BLI_countlist(&em->faces);
64
65         outDLM->mvert = MEM_mallocN(sizeof(*outDLM->mvert)*outDLM->totvert,
66                                    "em_mod_mv");
67         outDLM->medge = MEM_mallocN(sizeof(*outDLM->medge)*outDLM->totedge,
68                                    "em_mod_med");
69         outDLM->mface = MEM_mallocN(sizeof(*outDLM->mface)*outDLM->totface,
70                                    "em_mod_mf");
71
72         /* Need to be able to mark loose edges */
73         for (eed=em->edges.first; eed; eed=eed->next) {
74                 eed->f2 = 0;
75         }
76         for (efa=em->faces.first; efa; efa=efa->next) {
77                 efa->e1->f2 = 1;
78                 efa->e2->f2 = 1;
79                 efa->e3->f2 = 1;
80                 if (efa->e4) efa->e4->f2 = 1;
81         }
82
83         for (i=0,eve=em->verts.first; i<outDLM->totvert; i++,eve=eve->next) {
84                 MVert *mv = &outDLM->mvert[i];
85
86                 VECCOPY(mv->co, eve->co);
87                 mv->mat_nr = 0;
88                 mv->flag = ME_VERT_STEPINDEX;
89         }
90         for (i=0,eed=em->edges.first; i<outDLM->totedge; i++,eed=eed->next) {
91                 MEdge *med = &outDLM->medge[i];
92
93                 med->v1 = (int) eed->v1->prev;
94                 med->v2 = (int) eed->v2->prev;
95                 med->crease = (unsigned char) (eed->crease*255.0f);
96                 med->flag = ME_EDGEDRAW|ME_EDGERENDER|ME_EDGE_STEPINDEX;
97                 
98                 if (eed->seam) med->flag |= ME_SEAM;
99                 if (!eed->f2) med->flag |= ME_LOOSEEDGE;
100         }
101         for (i=0,efa=em->faces.first; i<outDLM->totface; i++,efa=efa->next) {
102                 MFace *mf = &outDLM->mface[i];
103                 mf->v1 = (int) efa->v1->prev;
104                 mf->v2 = (int) efa->v2->prev;
105                 mf->v3 = (int) efa->v3->prev;
106                 mf->v4 = efa->v4?(int) efa->v4->prev:0;
107                 mf->mat_nr = efa->mat_nr;
108                 mf->flag = efa->flag|ME_FACE_STEPINDEX;
109                 test_index_face(mf, NULL, NULL, efa->v4?4:3);
110         }
111
112         for (preveve=NULL, eve=em->verts.first; eve; preveve=eve, eve= eve->next)
113                 eve->prev = preveve;
114
115         return outDLM;
116 }
117
118 /***/
119
120 static int noneModifier_isDisabled(ModifierData *md)
121 {
122         return 1;
123 }
124
125 /* Curve */
126
127 static void curveModifier_copyData(ModifierData *md, ModifierData *target)
128 {
129         CurveModifierData *cmd = (CurveModifierData*) md;
130         CurveModifierData *tcmd = (CurveModifierData*) target;
131
132         tcmd->object = cmd->object;
133 }
134
135 static int curveModifier_isDisabled(ModifierData *md)
136 {
137         CurveModifierData *cmd = (CurveModifierData*) md;
138
139         return !cmd->object;
140 }
141
142 static void curveModifier_foreachObjectLink(ModifierData *md, Object *ob, void (*walk)(void *userData, Object *ob, Object **obpoin), void *userData)
143 {
144         CurveModifierData *cmd = (CurveModifierData*) md;
145
146         walk(userData, ob, &cmd->object);
147 }
148
149 static void curveModifier_updateDepgraph(ModifierData *md, DagForest *forest, Object *ob, DagNode *obNode)
150 {
151         CurveModifierData *cmd = (CurveModifierData*) md;
152
153         if (cmd->object) {
154                 DagNode *curNode = dag_get_node(forest, cmd->object);
155
156                 dag_add_relation(forest, curNode, obNode, DAG_RL_DATA_DATA|DAG_RL_OB_DATA);
157         }
158 }
159
160 static void curveModifier_deformVerts(ModifierData *md, Object *ob, void *derivedData, float (*vertexCos)[3], int numVerts)
161 {
162         CurveModifierData *cmd = (CurveModifierData*) md;
163
164         curve_deform_verts(cmd->object, ob, vertexCos, numVerts, cmd->name);
165 }
166
167 static void curveModifier_deformVertsEM(ModifierData *md, Object *ob, void *editData, void *derivedData, float (*vertexCos)[3], int numVerts)
168 {
169         curveModifier_deformVerts(md, ob, NULL, vertexCos, numVerts);
170 }
171
172 /* Lattice */
173
174 static void latticeModifier_copyData(ModifierData *md, ModifierData *target)
175 {
176         LatticeModifierData *lmd = (LatticeModifierData*) md;
177         LatticeModifierData *tlmd = (LatticeModifierData*) target;
178
179         tlmd->object = lmd->object;
180 }
181
182 static int latticeModifier_isDisabled(ModifierData *md)
183 {
184         LatticeModifierData *lmd = (LatticeModifierData*) md;
185
186         return !lmd->object;
187 }
188
189 static void latticeModifier_foreachObjectLink(ModifierData *md, Object *ob, void (*walk)(void *userData, Object *ob, Object **obpoin), void *userData)
190 {
191         LatticeModifierData *lmd = (LatticeModifierData*) md;
192
193         walk(userData, ob, &lmd->object);
194 }
195
196 static void latticeModifier_updateDepgraph(ModifierData *md, DagForest *forest, Object *ob, DagNode *obNode)
197 {
198         LatticeModifierData *lmd = (LatticeModifierData*) md;
199
200         if (lmd->object) {
201                 DagNode *latNode = dag_get_node(forest, lmd->object);
202
203                 dag_add_relation(forest, latNode, obNode, DAG_RL_DATA_DATA|DAG_RL_OB_DATA);
204         }
205 }
206
207 static void latticeModifier_deformVerts(ModifierData *md, Object *ob, void *derivedData, float (*vertexCos)[3], int numVerts)
208 {
209         LatticeModifierData *lmd = (LatticeModifierData*) md;
210
211         lattice_deform_verts(lmd->object, ob, vertexCos, numVerts, lmd->name);
212 }
213
214 static void latticeModifier_deformVertsEM(ModifierData *md, Object *ob, void *editData, void *derivedData, float (*vertexCos)[3], int numVerts)
215 {
216         latticeModifier_deformVerts(md, ob, NULL, vertexCos, numVerts);
217 }
218
219 /* Subsurf */
220
221 static void subsurfModifier_initData(ModifierData *md)
222 {
223         SubsurfModifierData *smd = (SubsurfModifierData*) md;
224         
225         smd->levels = 1;
226         smd->renderLevels = 2;
227         smd->flags |= eSubsurfModifierFlag_SubsurfUv;
228 }
229
230 static void subsurfModifier_copyData(ModifierData *md, ModifierData *target)
231 {
232         SubsurfModifierData *smd = (SubsurfModifierData*) md;
233         SubsurfModifierData *tsmd = (SubsurfModifierData*) target;
234
235         tsmd->flags = smd->flags;
236         tsmd->levels = smd->levels;
237         tsmd->renderLevels = smd->renderLevels;
238         tsmd->subdivType = smd->subdivType;
239 }
240
241 static void subsurfModifier_freeData(ModifierData *md)
242 {
243         SubsurfModifierData *smd = (SubsurfModifierData*) md;
244
245         if (smd->mCache) {
246                 ccgSubSurf_free(smd->mCache);
247         }
248         if (smd->emCache) {
249                 ccgSubSurf_free(smd->emCache);
250         }
251 }       
252
253 static void *subsurfModifier_applyModifier(ModifierData *md, Object *ob, void *derivedData, float (*vertexCos)[3], int useRenderParams, int isFinalCalc)
254 {
255         DerivedMesh *dm = derivedData;
256         SubsurfModifierData *smd = (SubsurfModifierData*) md;
257         Mesh *me = ob->data;
258
259         if (dm) {
260                 DispListMesh *dlm = dm->convertToDispListMesh(dm, 0);
261                 int i;
262
263                 if (vertexCos) {
264                         int numVerts = dm->getNumVerts(dm);
265
266                         for (i=0; i<numVerts; i++) {
267                                 VECCOPY(dlm->mvert[i].co, vertexCos[i]);
268                         }
269                 }
270
271                 dm = subsurf_make_derived_from_mesh(me, dlm, smd, useRenderParams, NULL, isFinalCalc);
272
273                 return dm;
274         } else {
275                 return subsurf_make_derived_from_mesh(me, NULL, smd, useRenderParams, vertexCos, isFinalCalc);
276         }
277 }
278
279 static void *subsurfModifier_applyModifierEM(ModifierData *md, Object *ob, void *editData, void *derivedData, float (*vertexCos)[3])
280 {
281         EditMesh *em = editData;
282         DerivedMesh *dm = derivedData;
283         SubsurfModifierData *smd = (SubsurfModifierData*) md;
284
285         if (dm) {
286                 DispListMesh *dlm = dm->convertToDispListMesh(dm, 0);
287
288                 dm = subsurf_make_derived_from_dlm_em(dlm, smd, vertexCos);
289
290                 return dm;
291         } else {
292                 return subsurf_make_derived_from_editmesh(em, smd, vertexCos);
293         }
294 }
295
296 /* Build */
297
298 static void buildModifier_initData(ModifierData *md)
299 {
300         BuildModifierData *bmd = (BuildModifierData*) md;
301
302         bmd->start = 1.0;
303         bmd->length = 100.0;
304 }
305
306 static void buildModifier_copyData(ModifierData *md, ModifierData *target)
307 {
308         BuildModifierData *bmd = (BuildModifierData*) md;
309         BuildModifierData *tbmd = (BuildModifierData*) target;
310
311         tbmd->start = bmd->start;
312         tbmd->length = bmd->length;
313         tbmd->randomize = bmd->randomize;
314         tbmd->seed = bmd->seed;
315 }
316
317 static int buildModifier_dependsOnTime(ModifierData *md)
318 {
319         return 1;
320 }
321
322 static void *buildModifier_applyModifier(ModifierData *md, Object *ob, void *derivedData, float (*vertexCos)[3], int useRenderParams, int isFinalCalc)
323 {
324         DerivedMesh *dm = derivedData;
325         BuildModifierData *bmd = (BuildModifierData*) md;
326         DispListMesh *dlm=NULL, *ndlm = MEM_callocN(sizeof(*ndlm), "build_dlm");
327         MVert *mvert;
328         MEdge *medge;
329         MFace *mface;
330         MCol *mcol;
331         TFace *tface;
332         int totvert, totedge, totface;
333         int i,j;
334         float frac;
335
336         if (dm) {
337                 dlm = dm->convertToDispListMesh(dm, 1);
338                 mvert = dlm->mvert;
339                 medge = dlm->medge;
340                 mface = dlm->mface;
341                 mcol = dlm->mcol;
342                 tface = dlm->tface;
343                 totvert = dlm->totvert;
344                 totedge = dlm->totedge;
345                 totface = dlm->totface;
346         } else {
347                 Mesh *me = ob->data;
348                 mvert = me->mvert;
349                 medge = me->medge;
350                 mface = me->mface;
351                 mcol = me->mcol;
352                 tface = me->tface;
353                 totvert = me->totvert;
354                 totedge = me->totedge;
355                 totface = me->totface;
356         }
357
358         if (ob) {
359                 frac = bsystem_time(ob, 0, (float)G.scene->r.cfra, bmd->start-1.0f)/bmd->length;
360         } else {
361                 frac = G.scene->r.cfra - bmd->start/bmd->length;
362         }
363         CLAMP(frac, 0.0, 1.0);
364
365         ndlm->totface = totface*frac;
366         ndlm->totedge = totedge*frac;
367         if (ndlm->totface) {
368                 ndlm->mvert = MEM_mallocN(sizeof(*ndlm->mvert)*totvert, "build_mvert");
369                 memcpy(ndlm->mvert, mvert, sizeof(*mvert)*totvert);
370                 for (i=0; i<totvert; i++) {
371                         if (vertexCos)
372                                 VECCOPY(ndlm->mvert[i].co, vertexCos[i]);
373                         ndlm->mvert[i].flag = 0;
374                 }
375
376                 if (bmd->randomize) {
377                         ndlm->mface = MEM_dupallocN(mface);
378                         BLI_array_randomize(ndlm->mface, sizeof(*mface), totface, bmd->seed);
379
380                         if (tface) {
381                                 ndlm->tface = MEM_dupallocN(tface);
382                                 BLI_array_randomize(ndlm->tface, sizeof(*tface), totface, bmd->seed);
383                         } else if (mcol) {
384                                 ndlm->mcol = MEM_dupallocN(mcol);
385                                 BLI_array_randomize(ndlm->mcol, sizeof(*mcol)*4, totface, bmd->seed);
386                         }
387                 } else {
388                         ndlm->mface = MEM_mallocN(sizeof(*ndlm->mface)*ndlm->totface, "build_mf");
389                         memcpy(ndlm->mface, mface, sizeof(*mface)*ndlm->totface);
390
391                         if (tface) {
392                                 ndlm->tface = MEM_mallocN(sizeof(*ndlm->tface)*ndlm->totface, "build_tf");
393                                 memcpy(ndlm->tface, tface, sizeof(*tface)*ndlm->totface);
394                         } else if (mcol) {
395                                 ndlm->mcol = MEM_mallocN(sizeof(*ndlm->mcol)*4*ndlm->totface, "build_mcol");
396                                 memcpy(ndlm->mcol, mcol, sizeof(*mcol)*4*ndlm->totface);
397                         }
398                 }
399
400                 for (i=0; i<ndlm->totface; i++) {
401                         MFace *mf = &ndlm->mface[i];
402
403                         ndlm->mvert[mf->v1].flag = 1;
404                         ndlm->mvert[mf->v2].flag = 1;
405                         ndlm->mvert[mf->v3].flag = 1;
406                         if (mf->v4) ndlm->mvert[mf->v4].flag = 1;
407                 }
408
409                         /* Store remapped indices in *((int*) mv->no) */
410                 ndlm->totvert = 0;
411                 for (i=0; i<totvert; i++) {
412                         MVert *mv = &ndlm->mvert[i];
413
414                         if (mv->flag) 
415                                 *((int*) mv->no) = ndlm->totvert++;
416                 }
417
418                         /* Remap face vertex indices */
419                 for (i=0; i<ndlm->totface; i++) {
420                         MFace *mf = &ndlm->mface[i];
421
422                         mf->v1 = *((int*) ndlm->mvert[mf->v1].no);
423                         mf->v2 = *((int*) ndlm->mvert[mf->v2].no);
424                         mf->v3 = *((int*) ndlm->mvert[mf->v3].no);
425                         if (mf->v4) mf->v4 = *((int*) ndlm->mvert[mf->v4].no);
426                 }
427                         /* Copy in all edges that have both vertices (remap in process) */
428                 if (totedge) {
429                         ndlm->totedge = 0;
430                         ndlm->medge = MEM_mallocN(sizeof(*ndlm->medge)*totedge, "build_med");
431
432                         for (i=0; i<totedge; i++) {
433                                 MEdge *med = &medge[i];
434
435                                 if (ndlm->mvert[med->v1].flag && ndlm->mvert[med->v2].flag) {
436                                         MEdge *nmed = &ndlm->medge[ndlm->totedge++];
437
438                                         memcpy(nmed, med, sizeof(*med));
439
440                                         nmed->v1 = *((int*) ndlm->mvert[nmed->v1].no);
441                                         nmed->v2 = *((int*) ndlm->mvert[nmed->v2].no);
442                                 }
443                         }
444                 }
445
446                         /* Collapse vertex array to remove unused verts */
447                 for(i=j=0; i<totvert; i++) {
448                         MVert *mv = &ndlm->mvert[i];
449
450                         if (mv->flag) {
451                                 if (j!=i) 
452                                         memcpy(&ndlm->mvert[j], mv, sizeof(*mv));
453                                 j++;
454                         }
455                 }
456         } else if (ndlm->totedge) {
457                 ndlm->mvert = MEM_mallocN(sizeof(*ndlm->mvert)*totvert, "build_mvert");
458                 memcpy(ndlm->mvert, mvert, sizeof(*mvert)*totvert);
459                 for (i=0; i<totvert; i++) {
460                         if (vertexCos)
461                                 VECCOPY(ndlm->mvert[i].co, vertexCos[i]);
462                         ndlm->mvert[i].flag = 0;
463                 }
464
465                 if (bmd->randomize) {
466                         ndlm->medge = MEM_dupallocN(medge);
467                         BLI_array_randomize(ndlm->medge, sizeof(*medge), totedge, bmd->seed);
468                 } else {
469                         ndlm->medge = MEM_mallocN(sizeof(*ndlm->medge)*ndlm->totedge, "build_mf");
470                         memcpy(ndlm->medge, medge, sizeof(*medge)*ndlm->totedge);
471                 }
472
473                 for (i=0; i<ndlm->totedge; i++) {
474                         MEdge *med = &ndlm->medge[i];
475
476                         ndlm->mvert[med->v1].flag = 1;
477                         ndlm->mvert[med->v2].flag = 1;
478                 }
479
480                         /* Store remapped indices in *((int*) mv->no) */
481                 ndlm->totvert = 0;
482                 for (i=0; i<totvert; i++) {
483                         MVert *mv = &ndlm->mvert[i];
484
485                         if (mv->flag) 
486                                 *((int*) mv->no) = ndlm->totvert++;
487                 }
488
489                         /* Remap edge vertex indices */
490                 for (i=0; i<ndlm->totedge; i++) {
491                         MEdge *med = &ndlm->medge[i];
492
493                         med->v1 = *((int*) ndlm->mvert[med->v1].no);
494                         med->v2 = *((int*) ndlm->mvert[med->v2].no);
495                 }
496
497                         /* Collapse vertex array to remove unused verts */
498                 for(i=j=0; i<totvert; i++) {
499                         MVert *mv = &ndlm->mvert[i];
500
501                         if (mv->flag) {
502                                 if (j!=i) 
503                                         memcpy(&ndlm->mvert[j], mv, sizeof(*mv));
504                                 j++;
505                         }
506                 }
507         } else {
508                 ndlm->totvert = totvert*frac;
509
510                 if (bmd->randomize) {
511                         ndlm->mvert = MEM_dupallocN(mvert);
512                         BLI_array_randomize(ndlm->mvert, sizeof(*mvert), totvert, bmd->seed);
513                 } else {
514                         ndlm->mvert = MEM_mallocN(sizeof(*ndlm->mvert)*ndlm->totvert, "build_mvert");
515                         memcpy(ndlm->mvert, mvert, sizeof(*mvert)*ndlm->totvert);
516                 }
517
518                 if (vertexCos) {
519                         for (i=0; i<ndlm->totvert; i++) {
520                                 VECCOPY(ndlm->mvert[i].co, vertexCos[i]);
521                         }
522                 }
523         }
524
525         if (dlm) displistmesh_free(dlm);
526
527         mesh_calc_normals(ndlm->mvert, ndlm->totvert, ndlm->mface, ndlm->totface, &ndlm->nors);
528         
529         return derivedmesh_from_displistmesh(ndlm, NULL);
530 }
531
532 /* Array */
533 /* Array modifier: duplicates the object multiple times along an axis
534 */
535
536 static void arrayModifier_initData(ModifierData *md)
537 {
538         ArrayModifierData *amd = (ArrayModifierData*) md;
539
540         /* default to 2 duplicates distributed along the x-axis by an
541            offset of 1 object-width
542         */
543         amd->curve_ob = amd->offset_ob = NULL;
544         amd->count = 2;
545         amd->offset[0] = amd->offset[1] = amd->offset[2] = 0;
546         amd->scale[0] = 1;
547         amd->scale[1] = amd->scale[2] = 0;
548         amd->length = 0;
549         amd->merge_dist = 0.01;
550         amd->fit_type = MOD_ARR_FIXEDCOUNT;
551         amd->offset_type = MOD_ARR_OFF_RELATIVE;
552         amd->flags = 0;
553 }
554
555 static void arrayModifier_copyData(ModifierData *md, ModifierData *target)
556 {
557         ArrayModifierData *amd = (ArrayModifierData*) md;
558         ArrayModifierData *tamd = (ArrayModifierData*) target;
559
560         tamd->curve_ob = amd->curve_ob;
561         tamd->offset_ob = amd->offset_ob;
562         tamd->count = amd->count;
563         VECCOPY(tamd->offset, amd->offset);
564         VECCOPY(tamd->scale, amd->scale);
565         tamd->length = amd->length;
566         tamd->merge_dist = amd->merge_dist;
567         tamd->fit_type = amd->fit_type;
568         tamd->offset_type = amd->offset_type;
569         tamd->flags = amd->flags;
570 }
571
572 static void arrayModifier_foreachObjectLink(ModifierData *md,
573                   Object *ob,
574                   void (*walk)(void *userData, Object *ob, Object **obpoin),
575                   void *userData)
576 {
577         ArrayModifierData *amd = (ArrayModifierData*) md;
578
579         walk(userData, ob, &amd->curve_ob);
580         walk(userData, ob, &amd->offset_ob);
581 }
582
583 static void arrayModifier_updateDepgraph(ModifierData *md,
584                                          DagForest *forest,
585                                          Object *ob,
586                                          DagNode *obNode)
587 {
588         ArrayModifierData *amd = (ArrayModifierData*) md;
589
590         if (amd->curve_ob) {
591                 DagNode *curNode = dag_get_node(forest, amd->curve_ob);
592
593                 dag_add_relation(forest, curNode, obNode,
594                                  DAG_RL_DATA_DATA|DAG_RL_OB_DATA);
595         }
596         if (amd->offset_ob) {
597                 DagNode *curNode = dag_get_node(forest, amd->offset_ob);
598
599                 dag_add_relation(forest, curNode, obNode,
600                                  DAG_RL_DATA_DATA|DAG_RL_OB_DATA);
601         }
602 }
603
604 float displistmesh_width(DispListMesh *dlm, int axis)
605 {
606         int i;
607         float min_co, max_co;
608         MVert *mv;
609
610         /* if there are no vertices, width is 0 */
611         if(dlm->totvert == 0) return 0;
612
613         /* find the minimum and maximum coordinates on the desired axis */
614         min_co = max_co = dlm->mvert[0].co[axis];
615         for (i=1; i < dlm->totvert; i++) {
616                 mv = &dlm->mvert[i];
617
618                 if(mv->co[axis] < min_co) min_co = mv->co[axis];
619                 if(mv->co[axis] > max_co) max_co = mv->co[axis];
620         }
621
622         return max_co - min_co;
623 }
624
625 typedef struct IndexMapEntry {
626         /* the new vert index that this old vert index maps to */
627         int new;
628         /* -1 if this vert isn't merged, otherwise the old vert index it
629          * should be replaced with
630          */
631         int merge;
632         /* 1 if this vert's first copy is merged with the last copy of its
633          * merge target, otherwise 0
634          */
635         short merge_final;
636 } IndexMapEntry;
637
638 static int calc_mapping(IndexMapEntry *indexMap, int oldVert, int copy)
639 {
640         int newVert;
641
642         if(indexMap[oldVert].merge < 0) {
643                 /* vert wasn't merged, so use copy of this vert */
644                 newVert = indexMap[oldVert].new + copy + 1;
645         } else if(indexMap[oldVert].merge == oldVert) {
646                 /* vert was merged with itself */
647                 newVert = indexMap[oldVert].new;
648         } else {
649                 /* vert was merged with another vert */
650                 int mergeVert = indexMap[oldVert].merge;
651
652                 if (mergeVert == indexMap[mergeVert].merge)
653                         /* vert merged with vert that was merged with itself */
654                         newVert = indexMap[mergeVert].new;
655                 else
656                         /* use copy of the vert this vert was merged with */
657                         newVert = indexMap[mergeVert].new + copy;
658         }
659
660         return newVert;
661 }
662
663 static DispListMesh *arrayModifier_doArray(ArrayModifierData *amd,
664                                            Object *ob, DispListMesh *inDLM,
665                                            float (*vertexCos)[3],
666                                            int initFlags)
667 {
668         int i, j;
669         /* offset matrix */
670         float offset[4][4];
671         float final_offset[4][4];
672         float tmp_mat[4][4];
673         float length = amd->length;
674         int count = amd->count;
675         DispListMesh *dlm = MEM_callocN(sizeof(*dlm), "array_dlm");
676
677         IndexMapEntry *indexMap;
678
679         EdgeHash *edges;
680
681         MTC_Mat4One(offset);
682
683         if(amd->offset_type & MOD_ARR_OFF_CONST)
684                 VecAddf(offset[3], offset[3], amd->offset);
685         if(amd->offset_type & MOD_ARR_OFF_RELATIVE) {
686                 for(j = 0; j < 3; j++)
687                         offset[3][j] += amd->scale[j] * displistmesh_width(inDLM, j);
688         }
689
690         if((amd->offset_type & MOD_ARR_OFF_OBJ) && (amd->offset_ob)) {
691                 float obinv[4][4];
692                 float result_mat[4][4];
693
694                 if(ob)
695                         MTC_Mat4Invert(obinv, ob->obmat);
696                 else
697                         MTC_Mat4One(obinv);
698
699                 MTC_Mat4MulSerie(result_mat, offset,
700                                  obinv, amd->offset_ob->obmat,
701                                  NULL, NULL, NULL, NULL, NULL);
702                 MTC_Mat4CpyMat4(offset, result_mat);
703         }
704
705         if(amd->fit_type == MOD_ARR_FITCURVE && amd->curve_ob) {
706                 Curve *cu = amd->curve_ob->data;
707                 if(cu) {
708                         if(!cu->path)
709                                 calc_curvepath(amd->curve_ob);
710
711                         if(cu->path)
712                                 length = cu->path->totdist;
713                 }
714         }
715
716         /* calculate the maximum number of copies which will fit within the
717            prescribed length */
718         if(amd->fit_type == MOD_ARR_FITLENGTH
719            || amd->fit_type == MOD_ARR_FITCURVE) {
720                 float dist = sqrt(MTC_dot3Float(offset[3], offset[3]));
721
722                 if(dist != 0)
723                         /* this gives length = first copy start to last copy end
724                            add a tiny offset for floating point rounding errors */
725                         count = (length + 0.00001) / dist;
726                 else
727                         /* if the offset has no translation, just make one copy */
728                         count = 1;
729         }
730
731         if(count < 1)
732                 count = 1;
733
734         dlm->totvert = dlm->totedge = dlm->totface = 0;
735         indexMap = MEM_callocN(sizeof(*indexMap)*inDLM->totvert, "indexmap");
736
737         /* allocate memory for count duplicates (including original) */
738         dlm->mvert = MEM_callocN(sizeof(*dlm->mvert)*inDLM->totvert*count,
739                                  "dlm_mvert");
740         dlm->mface = MEM_callocN(sizeof(*dlm->mface)*inDLM->totface*count,
741                                  "dlm_mface");
742
743         if (inDLM->medge)
744                 dlm->medge = MEM_callocN(sizeof(*dlm->medge)*inDLM->totedge*count,
745                                          "dlm_medge");
746         if (inDLM->tface)
747                 dlm->tface = MEM_callocN(sizeof(*dlm->tface)*inDLM->totface*count,
748                                          "dlm_tface");
749         if (inDLM->mcol)
750                 dlm->mcol = MEM_callocN(sizeof(*dlm->mcol)*inDLM->totface*4*count,
751                                         "dlm_mcol");
752
753         /* calculate the offset matrix of the final copy (for merging) */ 
754         MTC_Mat4One(final_offset);
755
756         for(j=0; j < count - 1; j++) {
757                 MTC_Mat4MulMat4(tmp_mat, final_offset, offset);
758                 MTC_Mat4CpyMat4(final_offset, tmp_mat);
759         }
760
761         for (i=0; i<inDLM->totvert; i++) {
762                 MVert *inMV = &inDLM->mvert[i];
763                 MVert *mv = &dlm->mvert[dlm->totvert++];
764                 MVert *mv2;
765                 float co[3];
766
767                 *mv = *inMV;
768
769                 if (vertexCos) {
770                         VECCOPY(mv->co, vertexCos[i]);
771                 }
772                 if (initFlags) mv->flag |= ME_VERT_STEPINDEX;
773
774                 indexMap[i].new = dlm->totvert-1;
775                 indexMap[i].merge = -1; /* default to no merge */
776                 indexMap[i].merge_final = 0; /* default to no merge */
777
778                 VECCOPY(co, mv->co);
779                 
780                 /* Attempts to merge verts from one duplicate with verts from the
781                  * next duplicate which are closer than amd->merge_dist.
782                  * Only the first such vert pair is merged.
783                  * If verts are merged in the first duplicate pair, they are merged
784                  * in all pairs.
785                  */
786                 if((count > 1) && (amd->flags & MOD_ARR_MERGE)) {
787                         float tmp_co[3];
788                         VECCOPY(tmp_co, mv->co);
789                         MTC_Mat4MulVecfl(offset, tmp_co);
790
791                         for(j = 0; j < inDLM->totvert; j++) {
792                                 inMV = &inDLM->mvert[j];
793                                 /* if this vert is within merge limit, merge */
794                                 if(VecLenCompare(tmp_co, inMV->co, amd->merge_dist)) {
795                                         indexMap[i].merge = j;
796
797                                         /* test for merging with final copy of merge target */
798                                         if(amd->flags & MOD_ARR_MERGEFINAL) {
799                                                 inMV = &inDLM->mvert[i];
800                                                 VECCOPY(tmp_co, inDLM->mvert[j].co);
801                                                 MTC_Mat4MulVecfl(final_offset, tmp_co);
802                                                 if(VecLenCompare(tmp_co, inMV->co, amd->merge_dist))
803                                                         indexMap[i].merge_final = 1;
804                                         }
805                                         break;
806                                 }
807                         }
808                 }
809
810                 /* if no merging, generate copies of this vert */
811                 if(indexMap[i].merge < 0) {
812                         for(j=0; j < count - 1; j++) {
813                                 mv2 = &dlm->mvert[dlm->totvert++];
814
815                                 *mv2 = *mv;
816                                 MTC_Mat4MulVecfl(offset, co);
817                                 VECCOPY(mv2->co, co);
818                                 mv2->flag &= ~ME_VERT_STEPINDEX;
819                         }
820                 } else if(indexMap[i].merge != i && indexMap[i].merge_final) {
821                         /* if this vert is not merging with itself, and it is merging
822                          * with the final copy of its merge target, remove the first copy
823                          */
824                         dlm->totvert--;
825                 }
826         }
827
828         /* make a hashtable so we can avoid duplicate edges from merging */
829         edges = BLI_edgehash_new();
830
831         for (i=0; i<inDLM->totedge; i++) {
832                 MEdge *inMED = &inDLM->medge[i];
833                 MEdge med;
834                 MEdge *med2;
835                 int vert1, vert2;
836
837                 med = *inMED;
838                 med.v1 = indexMap[inMED->v1].new;
839                 med.v2 = indexMap[inMED->v2].new;
840
841                 /* if vertices are to be merged with the final copies of their
842                  * merge targets, calculate that final copy
843                  */
844                 if(indexMap[inMED->v1].merge_final) {
845                         med.v1 = calc_mapping(indexMap, indexMap[inMED->v1].merge,
846                                               count - 2);
847                 }
848                 if(indexMap[inMED->v2].merge_final) {
849                         med.v2 = calc_mapping(indexMap, indexMap[inMED->v2].merge,
850                                               count - 2);
851                 }
852
853                 if (initFlags) {
854                         med.flag |= ME_EDGEDRAW|ME_EDGERENDER|ME_EDGE_STEPINDEX;
855                 }
856
857                 if(!BLI_edgehash_haskey(edges, med.v1, med.v2)) {
858                         dlm->medge[dlm->totedge++] = med;
859                         BLI_edgehash_insert(edges, med.v1, med.v2, NULL);
860                 }
861
862                 for(j=0; j < count - 1; j++)
863                 {
864                         vert1 = calc_mapping(indexMap, inMED->v1, j);
865                         vert2 = calc_mapping(indexMap, inMED->v2, j);
866                         /* avoid duplicate edges */
867                         if(!BLI_edgehash_haskey(edges, vert1, vert2)) {
868                                 med2 = &dlm->medge[dlm->totedge++];
869
870                                 *med2 = med;
871                                 med2->v1 = vert1;
872                                 med2->v2 = vert2;
873                                 med2->flag &= ~ME_EDGE_STEPINDEX;
874
875                                 BLI_edgehash_insert(edges, med2->v1, med2->v2, NULL);
876                         }
877                 }
878         }
879
880         /* don't need the hashtable any more */
881         BLI_edgehash_free(edges, NULL);
882
883         for (i=0; i<inDLM->totface; i++) {
884                 MFace *inMF = &inDLM->mface[i];
885                 MFace *mf = &dlm->mface[dlm->totface++];
886                 MFace *mf2;
887                 TFace *tf = NULL;
888                 MCol *mc = NULL;
889
890                 *mf = *inMF;
891                 mf->v1 = indexMap[inMF->v1].new;
892                 mf->v2 = indexMap[inMF->v2].new;
893                 mf->v3 = indexMap[inMF->v3].new;
894                 if(inMF->v4)
895                         mf->v4 = indexMap[inMF->v4].new;
896
897                 /* if vertices are to be merged with the final copies of their
898                  * merge targets, calculate that final copy
899                  */
900                 if(indexMap[inMF->v1].merge_final)
901                         mf->v1 = calc_mapping(indexMap, indexMap[inMF->v1].merge, count-2);
902                 if(indexMap[inMF->v2].merge_final)
903                         mf->v2 = calc_mapping(indexMap, indexMap[inMF->v2].merge, count-2);
904                 if(indexMap[inMF->v3].merge_final)
905                         mf->v3 = calc_mapping(indexMap, indexMap[inMF->v3].merge, count-2);
906                 if(inMF->v4 && indexMap[inMF->v4].merge_final)
907                         mf->v4 = calc_mapping(indexMap, indexMap[inMF->v4].merge, count-2);
908
909                 if (initFlags) mf->flag |= ME_FACE_STEPINDEX;
910
911                 if (inDLM->tface) {
912                         TFace *inTF = &inDLM->tface[i];
913                         tf = &dlm->tface[dlm->totface-1];
914
915                         *tf = *inTF;
916                 } else if (inDLM->mcol) {
917                         MCol *inMC = &inDLM->mcol[i*4];
918                         mc = &dlm->mcol[(dlm->totface-1)*4];
919
920                         mc[0] = inMC[0];
921                         mc[1] = inMC[1];
922                         mc[2] = inMC[2];
923                         mc[3] = inMC[3];
924                 }
925                 
926                 test_index_face(mf, mc, tf, inMF->v4?4:3);
927
928                 /* if the face has fewer than 3 vertices, don't create it */
929                 if(mf->v3 == 0)
930                         dlm->totface--;
931
932                 for(j=0; j < count - 1; j++)
933                 {
934                         mf2 = &dlm->mface[dlm->totface++];
935
936                         *mf2 = *mf;
937
938                         mf2->v1 = calc_mapping(indexMap, inMF->v1, j);
939                         mf2->v2 = calc_mapping(indexMap, inMF->v2, j);
940                         mf2->v3 = calc_mapping(indexMap, inMF->v3, j);
941                         if (inMF->v4)
942                                 mf2->v4 = calc_mapping(indexMap, inMF->v4, j);
943
944                         mf2->flag &= ~ME_FACE_STEPINDEX;
945
946                         if (inDLM->tface) {
947                                 TFace *inTF = &inDLM->tface[i];
948                                 tf = &dlm->tface[dlm->totface-1];
949
950                                 *tf = *inTF;
951                         } else if (inDLM->mcol) {
952                                 MCol *inMC = &inDLM->mcol[i*4];
953                                 mc = &dlm->mcol[(dlm->totface-1)*4];
954
955                                 mc[0] = inMC[0];
956                                 mc[1] = inMC[1];
957                                 mc[2] = inMC[2];
958                                 mc[3] = inMC[3];
959                         }
960
961                         test_index_face(mf2, mc, tf, inMF->v4?4:3);
962
963                         /* if the face has fewer than 3 vertices, don't create it */
964                         if(mf2->v3 == 0)
965                                 dlm->totface--;
966                 }
967         }
968
969         MEM_freeN(indexMap);
970
971         return dlm;
972 }
973
974 static void *arrayModifier_applyModifier_internal(ModifierData *md,
975                                                   Object *ob,
976                                                   void *derivedData,
977                                                   float (*vertexCos)[3],
978                                                   int useRenderParams,
979                                                   int isFinalCalc)
980 {
981         DerivedMesh *dm = derivedData;
982         ArrayModifierData *amd = (ArrayModifierData*) md;
983         DispListMesh *outDLM, *inDLM;
984
985         if (dm) {
986                 inDLM = dm->convertToDispListMesh(dm, 1);
987         } else {
988                 Mesh *me = ob->data;
989
990                 inDLM = MEM_callocN(sizeof(*inDLM), "inDLM");
991                 inDLM->dontFreeVerts = inDLM->dontFreeOther = 1;
992                 inDLM->mvert = me->mvert;
993                 inDLM->medge = me->medge;
994                 inDLM->mface = me->mface;
995                 inDLM->tface = me->tface;
996                 inDLM->mcol = me->mcol;
997                 inDLM->totvert = me->totvert;
998                 inDLM->totedge = me->totedge;
999                 inDLM->totface = me->totface;
1000         }
1001
1002         outDLM = arrayModifier_doArray(amd, ob, inDLM, vertexCos, dm?0:1);
1003
1004         displistmesh_free(inDLM);
1005         
1006         mesh_calc_normals(outDLM->mvert, outDLM->totvert, outDLM->mface,
1007                           outDLM->totface, &outDLM->nors);
1008
1009         return derivedmesh_from_displistmesh(outDLM, NULL);
1010 }
1011
1012 static void *arrayModifier_applyModifier(ModifierData *md,
1013                                          Object *ob,
1014                                          void *derivedData,
1015                                          float (*vertexCos)[3],
1016                                          int useRenderParams,
1017                                          int isFinalCalc)
1018 {
1019         return arrayModifier_applyModifier_internal(md, ob, derivedData,
1020                                                     vertexCos, 0, 1);
1021 }
1022
1023 static void *arrayModifier_applyModifierEM(ModifierData *md,
1024                                            Object *ob,
1025                                            void *editData,
1026                                            void *derivedData,
1027                                            float (*vertexCos)[3])
1028 {
1029         if (derivedData) {
1030                 return arrayModifier_applyModifier_internal(md, ob, derivedData,
1031                                                             vertexCos, 0, 1);
1032         } else {
1033                 ArrayModifierData *amd = (ArrayModifierData*) md;
1034                 DispListMesh *outDLM, *inDLM = displistmesh_from_editmesh(editData);
1035
1036                 outDLM = arrayModifier_doArray(amd, ob, inDLM, vertexCos, 0);
1037
1038                 displistmesh_free(inDLM);
1039
1040                 mesh_calc_normals(outDLM->mvert, outDLM->totvert,
1041                                   outDLM->mface, outDLM->totface, &outDLM->nors);
1042
1043                 return derivedmesh_from_displistmesh(outDLM, NULL);
1044         }
1045 }
1046
1047 /* Mirror */
1048
1049 static void mirrorModifier_initData(ModifierData *md)
1050 {
1051         MirrorModifierData *mmd = (MirrorModifierData*) md;
1052
1053         mmd->tolerance = 0.001;
1054 }
1055
1056 static void mirrorModifier_copyData(ModifierData *md, ModifierData *target)
1057 {
1058         MirrorModifierData *mmd = (MirrorModifierData*) md;
1059         MirrorModifierData *tmmd = (MirrorModifierData*) target;
1060
1061         tmmd->axis = mmd->axis;
1062         tmmd->tolerance = mmd->tolerance;
1063 }
1064
1065 static DispListMesh *mirrorModifier__doMirror(MirrorModifierData *mmd, DispListMesh *inDLM, float (*vertexCos)[3], int initFlags)
1066 {
1067         int i, axis = mmd->axis;
1068         float tolerance = mmd->tolerance;
1069         DispListMesh *dlm = MEM_callocN(sizeof(*dlm), "mirror_dlm");
1070         int (*indexMap)[2];
1071
1072         dlm->totvert = dlm->totedge = dlm->totface = 0;
1073         indexMap = MEM_mallocN(sizeof(*indexMap)*inDLM->totvert, "indexmap");
1074         dlm->mvert = MEM_callocN(sizeof(*dlm->mvert)*inDLM->totvert*2, "dlm_mvert");
1075         dlm->mface = MEM_callocN(sizeof(*dlm->mface)*inDLM->totface*2, "dlm_mface");
1076
1077         if (inDLM->medge) dlm->medge = MEM_callocN(sizeof(*dlm->medge)*inDLM->totedge*2, "dlm_medge");
1078         if (inDLM->tface) dlm->tface = MEM_callocN(sizeof(*dlm->tface)*inDLM->totface*2, "dlm_tface");
1079         if (inDLM->mcol) dlm->mcol = MEM_callocN(sizeof(*dlm->mcol)*inDLM->totface*4*2, "dlm_mcol");
1080
1081         for (i=0; i<inDLM->totvert; i++) {
1082                 MVert *inMV = &inDLM->mvert[i];
1083                 MVert *mv = &dlm->mvert[dlm->totvert++];
1084                 int isShared = ABS(inMV->co[axis])<=tolerance;
1085
1086                                 /* Because the topology result (# of vertices) must be the same
1087                                  * if the mesh data is overridden by vertex cos, have to calc sharedness
1088                                  * based on original coordinates. This is why we test before copy.
1089                                  */
1090                 *mv = *inMV;
1091                 if (vertexCos) {
1092                         VECCOPY(mv->co, vertexCos[i]);
1093                 }
1094                 if (initFlags) mv->flag |= ME_VERT_STEPINDEX;
1095
1096                 indexMap[i][0] = dlm->totvert-1;
1097                 indexMap[i][1] = !isShared;
1098
1099                 if (isShared) {
1100                         mv->co[axis] = 0;
1101                         mv->flag |= ME_VERT_MERGED;
1102                 } else {
1103                         MVert *mv2 = &dlm->mvert[dlm->totvert++];
1104
1105                         *mv2 = *mv;
1106                         mv2->co[axis] = -mv2->co[axis];
1107                         mv2->flag &= ~ME_VERT_STEPINDEX;
1108                 }
1109         }
1110
1111         for (i=0; i<inDLM->totedge; i++) {
1112                 MEdge *inMED = &inDLM->medge[i];
1113                 MEdge *med = &dlm->medge[dlm->totedge++];
1114
1115                 *med = *inMED;
1116                 med->v1 = indexMap[inMED->v1][0];
1117                 med->v2 = indexMap[inMED->v2][0];
1118                 if (initFlags) med->flag |= ME_EDGEDRAW|ME_EDGERENDER|ME_EDGE_STEPINDEX;
1119
1120                 if (indexMap[inMED->v1][1] || indexMap[inMED->v2][1]) {
1121                         MEdge *med2 = &dlm->medge[dlm->totedge++];
1122
1123                         *med2 = *med;
1124                         med2->v1 += indexMap[inMED->v1][1];
1125                         med2->v2 += indexMap[inMED->v2][1];
1126                         med2->flag &= ~ME_EDGE_STEPINDEX;
1127                 }
1128         }
1129
1130         for (i=0; i<inDLM->totface; i++) {
1131                 MFace *inMF = &inDLM->mface[i];
1132                 MFace *mf = &dlm->mface[dlm->totface++];
1133
1134                 *mf = *inMF;
1135                 mf->v1 = indexMap[inMF->v1][0];
1136                 mf->v2 = indexMap[inMF->v2][0];
1137                 mf->v3 = indexMap[inMF->v3][0];
1138                 mf->v4 = indexMap[inMF->v4][0];
1139                 if (initFlags) mf->flag |= ME_FACE_STEPINDEX;
1140
1141                 if (inDLM->tface) {
1142                         TFace *inTF = &inDLM->tface[i];
1143                         TFace *tf = &dlm->tface[dlm->totface-1];
1144
1145                         *tf = *inTF;
1146                 } else if (inDLM->mcol) {
1147                         MCol *inMC = &inDLM->mcol[i*4];
1148                         MCol *mc = &dlm->mcol[(dlm->totface-1)*4];
1149
1150                         mc[0] = inMC[0];
1151                         mc[1] = inMC[1];
1152                         mc[2] = inMC[2];
1153                         mc[3] = inMC[3];
1154                 }
1155                 
1156                 if (indexMap[inMF->v1][1] || indexMap[inMF->v2][1] || indexMap[inMF->v3][1] || (mf->v4 && indexMap[inMF->v4][1])) {
1157                         MFace *mf2 = &dlm->mface[dlm->totface++];
1158                         TFace *tf = NULL;
1159                         MCol *mc = NULL;
1160
1161                         *mf2 = *mf;
1162                         mf2->v1 += indexMap[inMF->v1][1];
1163                         mf2->v2 += indexMap[inMF->v2][1];
1164                         mf2->v3 += indexMap[inMF->v3][1];
1165                         if (inMF->v4) mf2->v4 += indexMap[inMF->v4][1];
1166                         mf2->flag &= ~ME_FACE_STEPINDEX;
1167
1168                         if (inDLM->tface) {
1169                                 TFace *inTF = &inDLM->tface[i];
1170                                 tf = &dlm->tface[dlm->totface-1];
1171
1172                                 *tf = *inTF;
1173                         } else if (inDLM->mcol) {
1174                                 MCol *inMC = &inDLM->mcol[i*4];
1175                                 mc = &dlm->mcol[(dlm->totface-1)*4];
1176
1177                                 mc[0] = inMC[0];
1178                                 mc[1] = inMC[1];
1179                                 mc[2] = inMC[2];
1180                                 mc[3] = inMC[3];
1181                         }
1182
1183                                 /* Flip face normal */
1184                         SWAP(int, mf2->v1, mf2->v3);
1185                         if (tf) {
1186                                 SWAP(unsigned int, tf->col[0], tf->col[2]);
1187                                 SWAP(float, tf->uv[0][0], tf->uv[2][0]);
1188                                 SWAP(float, tf->uv[0][1], tf->uv[2][1]);
1189                         } else if (mc) {
1190                                 SWAP(MCol, mc[0], mc[2]);
1191                         }
1192
1193                         test_index_face(mf2, mc, tf, inMF->v4?4:3);
1194                 }
1195         }
1196
1197         MEM_freeN(indexMap);
1198
1199         return dlm;
1200 }
1201
1202 static void *mirrorModifier_applyModifier__internal(ModifierData *md, Object *ob, void *derivedData, float (*vertexCos)[3], int useRenderParams, int isFinalCalc)
1203 {
1204         DerivedMesh *dm = derivedData;
1205         MirrorModifierData *mmd = (MirrorModifierData*) md;
1206         DispListMesh *outDLM, *inDLM;
1207
1208         if (dm) {
1209                 inDLM = dm->convertToDispListMesh(dm, 1);
1210         } else {
1211                 Mesh *me = ob->data;
1212
1213                 inDLM = MEM_callocN(sizeof(*inDLM), "inDLM");
1214                 inDLM->dontFreeVerts = inDLM->dontFreeOther = 1;
1215                 inDLM->mvert = me->mvert;
1216                 inDLM->medge = me->medge;
1217                 inDLM->mface = me->mface;
1218                 inDLM->tface = me->tface;
1219                 inDLM->mcol = me->mcol;
1220                 inDLM->totvert = me->totvert;
1221                 inDLM->totedge = me->totedge;
1222                 inDLM->totface = me->totface;
1223         }
1224
1225         outDLM = mirrorModifier__doMirror(mmd, inDLM, vertexCos, dm?0:1);
1226
1227         displistmesh_free(inDLM);
1228         
1229         mesh_calc_normals(outDLM->mvert, outDLM->totvert, outDLM->mface, outDLM->totface, &outDLM->nors);
1230         
1231         return derivedmesh_from_displistmesh(outDLM, NULL);
1232 }
1233
1234 static void *mirrorModifier_applyModifier(ModifierData *md, Object *ob, void *derivedData, float (*vertexCos)[3], int useRenderParams, int isFinalCalc)
1235 {
1236         return mirrorModifier_applyModifier__internal(md, ob, derivedData, vertexCos, 0, 1);
1237 }
1238
1239 static void *mirrorModifier_applyModifierEM(ModifierData *md, Object *ob, void *editData, void *derivedData, float (*vertexCos)[3])
1240 {
1241         if (derivedData) {
1242                 return mirrorModifier_applyModifier__internal(md, ob, derivedData, vertexCos, 0, 1);
1243         } else {
1244                 DispListMesh *inDLM, *outDLM;
1245                 MirrorModifierData *mmd = (MirrorModifierData*) md;
1246                 
1247                 inDLM = displistmesh_from_editmesh((EditMesh*)editData);
1248                 outDLM = mirrorModifier__doMirror(mmd, inDLM, vertexCos, 0);
1249                 displistmesh_free(inDLM);
1250
1251                 mesh_calc_normals(outDLM->mvert, outDLM->totvert, outDLM->mface, outDLM->totface, &outDLM->nors);
1252
1253                 return derivedmesh_from_displistmesh(outDLM, NULL);
1254         }
1255 }
1256
1257 /* Decimate */
1258
1259 static void decimateModifier_initData(ModifierData *md)
1260 {
1261         DecimateModifierData *dmd = (DecimateModifierData*) md;
1262
1263         dmd->percent = 1.0;
1264 }
1265
1266 static void decimateModifier_copyData(ModifierData *md, ModifierData *target)
1267 {
1268         DecimateModifierData *dmd = (DecimateModifierData*) md;
1269         DecimateModifierData *tdmd = (DecimateModifierData*) target;
1270
1271         tdmd->percent = dmd->percent;
1272 }
1273
1274 static void *decimateModifier_applyModifier(ModifierData *md, Object *ob, void *derivedData, float (*vertexCos)[3], int useRenderParams, int isFinalCalc)
1275 {
1276         DecimateModifierData *dmd = (DecimateModifierData*) md;
1277         DerivedMesh *dm = derivedData;
1278         Mesh *me = ob->data;
1279         MVert *mvert;
1280         MFace *mface;
1281         DispListMesh *ndlm=NULL, *dlm=NULL;
1282         LOD_Decimation_Info lod;
1283         int totvert, totface;
1284         int a, numTris;
1285
1286         if (dm) {
1287                 dlm = dm->convertToDispListMesh(dm, 1);
1288                 mvert = dlm->mvert;
1289                 mface = dlm->mface;
1290                 totvert = dlm->totvert;
1291                 totface = dlm->totface;
1292         } else {
1293                 mvert = me->mvert;
1294                 mface = me->mface;
1295                 totvert = me->totvert;
1296                 totface = me->totface;
1297         }
1298
1299         numTris = 0;
1300         for (a=0; a<totface; a++) {
1301                 MFace *mf = &mface[a];
1302                 numTris++;
1303                 if (mf->v4) numTris++;
1304         }
1305
1306         if(numTris<3) {
1307                 modifier_setError(md, "There must be more than 3 input faces (triangles).");
1308                 goto exit;
1309         }
1310
1311         lod.vertex_buffer= MEM_mallocN(3*sizeof(float)*totvert, "vertices");
1312         lod.vertex_normal_buffer= MEM_mallocN(3*sizeof(float)*totvert, "normals");
1313         lod.triangle_index_buffer= MEM_mallocN(3*sizeof(int)*numTris, "trias");
1314         lod.vertex_num= totvert;
1315         lod.face_num= numTris;
1316
1317         for(a=0; a<totvert; a++) {
1318                 MVert *mv = &mvert[a];
1319                 float *vbCo = &lod.vertex_buffer[a*3];
1320                 float *vbNo = &lod.vertex_normal_buffer[a*3];
1321
1322                 if (vertexCos) {
1323                         VECCOPY(vbCo, vertexCos[a]);
1324                 } else {
1325                         VECCOPY(vbCo, mv->co);
1326                 }
1327
1328                 vbNo[0] = mv->no[0]/32767.0f;
1329                 vbNo[1] = mv->no[1]/32767.0f;
1330                 vbNo[2] = mv->no[2]/32767.0f;
1331         }
1332
1333         numTris = 0;
1334         for(a=0; a<totface; a++) {
1335                 MFace *mf = &mface[a];
1336                 int *tri = &lod.triangle_index_buffer[3*numTris++];
1337                 tri[0]= mf->v1;
1338                 tri[1]= mf->v2;
1339                 tri[2]= mf->v3;
1340
1341                 if(mf->v4) {
1342                         tri = &lod.triangle_index_buffer[3*numTris++];
1343                         tri[0]= mf->v1;
1344                         tri[1]= mf->v3;
1345                         tri[2]= mf->v4;
1346                 }
1347         }
1348
1349         dmd->faceCount = 0;
1350         if(LOD_LoadMesh(&lod) ) {
1351                 if( LOD_PreprocessMesh(&lod) ) {
1352                         /* we assume the decim_faces tells how much to reduce */
1353
1354                         while(lod.face_num > numTris*dmd->percent) {
1355                                 if( LOD_CollapseEdge(&lod)==0) break;
1356                         }
1357
1358                         ndlm= MEM_callocN(sizeof(DispListMesh), "dispmesh");
1359                         ndlm->mvert= MEM_callocN(lod.vertex_num*sizeof(MVert), "mvert");
1360                         ndlm->totvert= lod.vertex_num;
1361                         if(lod.vertex_num>2) {
1362                                 ndlm->mface= MEM_callocN(lod.face_num*sizeof(MFace), "mface");
1363                                 ndlm->totface= dmd->faceCount = lod.face_num;
1364                         }
1365                         for(a=0; a<lod.vertex_num; a++) {
1366                                 MVert *mv = &ndlm->mvert[a];
1367                                 float *vbCo = &lod.vertex_buffer[a*3];
1368                                 
1369                                 VECCOPY(mv->co, vbCo);
1370                         }
1371
1372                         if(lod.vertex_num>2) {
1373                                 for(a=0; a<lod.face_num; a++) {
1374                                         MFace *mf = &ndlm->mface[a];
1375                                         int *tri = &lod.triangle_index_buffer[a*3];
1376                                         mf->v1 = tri[0];
1377                                         mf->v2 = tri[1];
1378                                         mf->v3 = tri[2];
1379                                         test_index_face(mf, NULL, NULL, 3);
1380                                 }
1381                                 displistmesh_add_edges(ndlm);
1382                         }
1383                 }
1384                 else {
1385                         modifier_setError(md, "Out of memory.");
1386                 }
1387
1388                 LOD_FreeDecimationData(&lod);
1389         }
1390         else {
1391                 modifier_setError(md, "Non-manifold mesh as input.");
1392         }
1393
1394         MEM_freeN(lod.vertex_buffer);
1395         MEM_freeN(lod.vertex_normal_buffer);
1396         MEM_freeN(lod.triangle_index_buffer);
1397
1398 exit:
1399         if (dlm) displistmesh_free(dlm);
1400
1401         if (ndlm) {
1402                 mesh_calc_normals(ndlm->mvert, ndlm->totvert, ndlm->mface, ndlm->totface, &ndlm->nors);
1403
1404                 return derivedmesh_from_displistmesh(ndlm, NULL);
1405         } else {
1406                 return NULL;
1407         }
1408 }
1409
1410 /* Wave */
1411
1412 static void waveModifier_initData(ModifierData *md) 
1413 {
1414         WaveModifierData *wmd = (WaveModifierData*) md; // whadya know, moved here from Iraq
1415                 
1416         wmd->flag |= (WAV_X+WAV_Y+WAV_CYCL);
1417         
1418         wmd->height= 0.5f;
1419         wmd->width= 1.5f;
1420         wmd->speed= 0.5f;
1421         wmd->narrow= 1.5f;
1422         wmd->lifetime= 0.0f;
1423         wmd->damp= 10.0f;
1424 }
1425
1426 static void waveModifier_copyData(ModifierData *md, ModifierData *target)
1427 {
1428         WaveModifierData *wmd = (WaveModifierData*) md;
1429         WaveModifierData *twmd = (WaveModifierData*) target;
1430
1431         twmd->damp = wmd->damp;
1432         twmd->flag = wmd->flag;
1433         twmd->height = wmd->height;
1434         twmd->lifetime = wmd->lifetime;
1435         twmd->narrow = wmd->narrow;
1436         twmd->speed = wmd->speed;
1437         twmd->startx = wmd->startx;
1438         twmd->starty = wmd->starty;
1439         twmd->timeoffs = wmd->timeoffs;
1440         twmd->width = wmd->width;
1441 }
1442
1443 static int waveModifier_dependsOnTime(ModifierData *md)
1444 {
1445         return 1;
1446 }
1447
1448 static void waveModifier_deformVerts(ModifierData *md, Object *ob, void *derivedData, float (*vertexCos)[3], int numVerts)
1449 {
1450         WaveModifierData *wmd = (WaveModifierData*) md;
1451         float ctime = bsystem_time(ob, 0, (float)G.scene->r.cfra, 0.0);
1452         float minfac = (float)(1.0/exp(wmd->width*wmd->narrow*wmd->width*wmd->narrow));
1453         float lifefac = wmd->height;
1454
1455         if(wmd->damp==0) wmd->damp= 10.0f;
1456
1457         if(wmd->lifetime!=0.0) {
1458                 float x= ctime - wmd->timeoffs;
1459
1460                 if(x>wmd->lifetime) {
1461                         lifefac= x-wmd->lifetime;
1462                         
1463                         if(lifefac > wmd->damp) lifefac= 0.0;
1464                         else lifefac= (float)(wmd->height*(1.0 - sqrt(lifefac/wmd->damp)));
1465                 }
1466         }
1467
1468         if(lifefac!=0.0) {
1469                 int i;
1470
1471                 for (i=0; i<numVerts; i++) {
1472                         float *co = vertexCos[i];
1473                         float x= co[0]-wmd->startx;
1474                         float y= co[1]-wmd->starty;
1475                         float amplit= 0.0f;
1476
1477                         if(wmd->flag & WAV_X) {
1478                                 if(wmd->flag & WAV_Y) amplit= (float)sqrt( (x*x + y*y));
1479                                 else amplit= x;
1480                         }
1481                         else if(wmd->flag & WAV_Y) 
1482                                 amplit= y;
1483                         
1484                         /* this way it makes nice circles */
1485                         amplit-= (ctime-wmd->timeoffs)*wmd->speed;
1486
1487                         if(wmd->flag & WAV_CYCL) {
1488                                 amplit = (float)fmod(amplit-wmd->width, 2.0*wmd->width) + wmd->width;
1489                         }
1490
1491                                 /* GAUSSIAN */
1492                         if(amplit> -wmd->width && amplit<wmd->width) {
1493                                 amplit = amplit*wmd->narrow;
1494                                 amplit= (float)(1.0/exp(amplit*amplit) - minfac);
1495
1496                                 co[2]+= lifefac*amplit;
1497                         }
1498                 }
1499         }
1500 }
1501
1502 static void waveModifier_deformVertsEM(ModifierData *md, Object *ob, void *editData, void *derivedData, float (*vertexCos)[3], int numVerts)
1503 {
1504         waveModifier_deformVerts(md, ob, NULL, vertexCos, numVerts);
1505 }
1506
1507 /* Armature */
1508
1509 static void armatureModifier_initData(ModifierData *md)
1510 {
1511         ArmatureModifierData *amd = (ArmatureModifierData*) md;
1512         
1513         amd->deformflag = ARM_DEF_ENVELOPE|ARM_DEF_VGROUP;
1514 }
1515
1516 static void armatureModifier_copyData(ModifierData *md, ModifierData *target)
1517 {
1518         ArmatureModifierData *amd = (ArmatureModifierData*) md;
1519         ArmatureModifierData *tamd = (ArmatureModifierData*) target;
1520
1521         tamd->object = amd->object;
1522         tamd->deformflag = amd->deformflag;
1523 }
1524
1525 static int armatureModifier_isDisabled(ModifierData *md)
1526 {
1527         ArmatureModifierData *amd = (ArmatureModifierData*) md;
1528
1529         return !amd->object;
1530 }
1531
1532 static void armatureModifier_foreachObjectLink(ModifierData *md, Object *ob, void (*walk)(void *userData, Object *ob, Object **obpoin), void *userData)
1533 {
1534         ArmatureModifierData *amd = (ArmatureModifierData*) md;
1535
1536         walk(userData, ob, &amd->object);
1537 }
1538
1539 static void armatureModifier_updateDepgraph(ModifierData *md, DagForest *forest, Object *ob, DagNode *obNode)
1540 {
1541         ArmatureModifierData *amd = (ArmatureModifierData*) md;
1542
1543         if (amd->object) {
1544                 DagNode *curNode = dag_get_node(forest, amd->object);
1545
1546                 dag_add_relation(forest, curNode, obNode, DAG_RL_DATA_DATA|DAG_RL_OB_DATA);
1547         }
1548 }
1549
1550 static void armatureModifier_deformVerts(ModifierData *md, Object *ob, void *derivedData, float (*vertexCos)[3], int numVerts)
1551 {
1552         ArmatureModifierData *amd = (ArmatureModifierData*) md;
1553
1554         armature_deform_verts(amd->object, ob, vertexCos, numVerts, amd->deformflag);
1555 }
1556
1557 static void armatureModifier_deformVertsEM(ModifierData *md, Object *ob, void *editData, void *derivedData, float (*vertexCos)[3], int numVerts)
1558 {
1559         ArmatureModifierData *amd = (ArmatureModifierData*) md;
1560
1561         armature_deform_verts(amd->object, ob, vertexCos, numVerts, amd->deformflag);
1562 }
1563
1564 /* Hook */
1565
1566 static void hookModifier_initData(ModifierData *md) 
1567 {
1568         HookModifierData *hmd = (HookModifierData*) md;
1569
1570         hmd->force= 1.0;
1571 }
1572
1573 static void hookModifier_copyData(ModifierData *md, ModifierData *target)
1574 {
1575         HookModifierData *hmd = (HookModifierData*) md;
1576         HookModifierData *thmd = (HookModifierData*) target;
1577
1578         VECCOPY(thmd->cent, hmd->cent);
1579         thmd->falloff = hmd->falloff;
1580         thmd->force = hmd->force;
1581         thmd->object = hmd->object;
1582         thmd->totindex = hmd->totindex;
1583         thmd->indexar = MEM_dupallocN(hmd->indexar);
1584         memcpy(thmd->parentinv, hmd->parentinv, sizeof(hmd->parentinv));
1585 }
1586
1587 static void hookModifier_freeData(ModifierData *md)
1588 {
1589         HookModifierData *hmd = (HookModifierData*) md;
1590
1591         if (hmd->indexar) MEM_freeN(hmd->indexar);
1592 }
1593
1594 static int hookModifier_isDisabled(ModifierData *md)
1595 {
1596         HookModifierData *hmd = (HookModifierData*) md;
1597
1598         return !hmd->object;
1599 }
1600
1601 static void hookModifier_foreachObjectLink(ModifierData *md, Object *ob, void (*walk)(void *userData, Object *ob, Object **obpoin), void *userData)
1602 {
1603         HookModifierData *hmd = (HookModifierData*) md;
1604
1605         walk(userData, ob, &hmd->object);
1606 }
1607
1608 static void hookModifier_updateDepgraph(ModifierData *md, DagForest *forest, Object *ob, DagNode *obNode)
1609 {
1610         HookModifierData *hmd = (HookModifierData*) md;
1611
1612         if (hmd->object) {
1613                 DagNode *curNode = dag_get_node(forest, hmd->object);
1614
1615                 dag_add_relation(forest, curNode, obNode, DAG_RL_OB_DATA);
1616         }
1617 }
1618
1619 static void hookModifier_deformVerts(ModifierData *md, Object *ob, void *derivedData, float (*vertexCos)[3], int numVerts)
1620 {
1621         HookModifierData *hmd = (HookModifierData*) md;
1622         float vec[3], mat[4][4];
1623         int i;
1624
1625         Mat4Invert(ob->imat, ob->obmat);
1626         Mat4MulSerie(mat, ob->imat, hmd->object->obmat, hmd->parentinv, NULL, NULL, NULL, NULL, NULL);
1627
1628         /* vertex indices? */
1629         if(hmd->indexar) {
1630                 for (i=0; i<hmd->totindex; i++) {
1631                         int index = hmd->indexar[i];
1632
1633                                 /* This should always be true and I don't generally like 
1634                                  * "paranoid" style code like this, but old files can have
1635                                  * indices that are out of range because old blender did
1636                                  * not correct them on exit editmode. - zr
1637                                  */
1638                         if (index<numVerts) {
1639                                 float *co = vertexCos[index];
1640                                 float fac = hmd->force;
1641
1642                                 if(hmd->falloff!=0.0) {
1643                                         float len= VecLenf(co, hmd->cent);
1644                                         if(len > hmd->falloff) fac = 0.0;
1645                                         else if(len>0.0) fac *= sqrt(1.0 - len/hmd->falloff);
1646                                 }
1647
1648                                 if(fac!=0.0) {
1649                                         VecMat4MulVecfl(vec, mat, co);
1650                                         VecLerpf(co, co, vec, fac);
1651                                 }
1652                         }
1653                 }
1654         }
1655         else {  /* vertex group hook */
1656                 bDeformGroup *curdef;
1657                 Mesh *me= ob->data;
1658                 int index=0;
1659                 
1660                 /* find the group (weak loop-in-loop) */
1661                 for (curdef = ob->defbase.first; curdef; curdef=curdef->next, index++)
1662                         if (!strcmp(curdef->name, hmd->name))
1663                                 break;
1664                 
1665                 if(curdef && me->dvert) {
1666                         MDeformVert *dvert= me->dvert;
1667                         int i, j;
1668                         
1669                         for (i=0; i < me->totvert; i++, dvert++) {
1670                                 for(j=0; j<dvert->totweight; j++) {
1671                                         if (dvert->dw[j].def_nr == index) {
1672                                                 float fac = hmd->force*dvert->dw[j].weight;
1673                                                 float *co = vertexCos[i];
1674                                                 
1675                                                 if(hmd->falloff!=0.0) {
1676                                                         float len= VecLenf(co, hmd->cent);
1677                                                         if(len > hmd->falloff) fac = 0.0;
1678                                                         else if(len>0.0) fac *= sqrt(1.0 - len/hmd->falloff);
1679                                                 }
1680                                                 
1681                                                 VecMat4MulVecfl(vec, mat, co);
1682                                                 VecLerpf(co, co, vec, fac);
1683
1684                                         }
1685                                 }
1686                         }
1687                 }
1688
1689         }
1690 }
1691
1692 static void hookModifier_deformVertsEM(ModifierData *md, Object *ob, void *editData, void *derivedData, float (*vertexCos)[3], int numVerts)
1693 {
1694         hookModifier_deformVerts(md, ob, derivedData, vertexCos, numVerts);
1695 }
1696
1697 /* Softbody */
1698
1699 static void softbodyModifier_deformVerts(ModifierData *md, Object *ob, void *derivedData, float (*vertexCos)[3], int numVerts)
1700 {
1701         sbObjectStep(ob, (float)G.scene->r.cfra, vertexCos, numVerts);
1702 }
1703
1704 /* Boolean */
1705
1706 static void booleanModifier_copyData(ModifierData *md, ModifierData *target)
1707 {
1708         BooleanModifierData *bmd = (BooleanModifierData*) md;
1709         BooleanModifierData *tbmd = (BooleanModifierData*) target;
1710
1711         tbmd->object = bmd->object;
1712         tbmd->operation = bmd->operation;
1713 }
1714
1715 static int booleanModifier_isDisabled(ModifierData *md)
1716 {
1717         BooleanModifierData *bmd = (BooleanModifierData*) md;
1718
1719         return !bmd->object;
1720 }
1721
1722 static void booleanModifier_foreachObjectLink(ModifierData *md, Object *ob, void (*walk)(void *userData, Object *ob, Object **obpoin), void *userData)
1723 {
1724         BooleanModifierData *bmd = (BooleanModifierData*) md;
1725
1726         walk(userData, ob, &bmd->object);
1727 }
1728
1729 static void booleanModifier_updateDepgraph(ModifierData *md, DagForest *forest, Object *ob, DagNode *obNode)
1730 {
1731         BooleanModifierData *bmd = (BooleanModifierData*) md;
1732
1733         if (bmd->object) {
1734                 DagNode *curNode = dag_get_node(forest, bmd->object);
1735
1736                 dag_add_relation(forest, curNode, obNode, DAG_RL_DATA_DATA|DAG_RL_OB_DATA);
1737         }
1738 }
1739
1740 static void *booleanModifier_applyModifier(ModifierData *md, Object *ob, void *derivedData, float (*vertexCos)[3], int useRenderParams, int isFinalCalc)
1741 {       
1742                 // XXX doesn't handle derived data
1743         BooleanModifierData *bmd = (BooleanModifierData*) md;
1744         
1745         /* we do a quick sanity check */
1746         if( ((Mesh *)ob->data)->totface>3 && bmd->object && ((Mesh *)bmd->object->data)->totface>3) {
1747                 DispListMesh *dlm= NewBooleanMeshDLM(bmd->object, ob, 1+bmd->operation);
1748                 
1749                 /* if new mesh returned, get derived mesh; otherwise there was
1750                  * an error, so delete the modifier object */
1751
1752                 if( dlm )
1753                         return derivedmesh_from_displistmesh(dlm, NULL);
1754                 else
1755                         bmd->object = NULL;
1756         }
1757         return derivedData;
1758 }
1759
1760 /***/
1761
1762 static ModifierTypeInfo typeArr[NUM_MODIFIER_TYPES];
1763 static int typeArrInit = 1;
1764
1765 ModifierTypeInfo *modifierType_getInfo(ModifierType type)
1766 {
1767         if (typeArrInit) {
1768                 ModifierTypeInfo *mti;
1769
1770                 memset(typeArr, 0, sizeof(typeArr));
1771
1772                 /* Initialize and return the appropriate type info structure,
1773                  * assumes that modifier has:
1774                  *  name == typeName, 
1775                  *  structName == typeName + 'ModifierData'
1776                  */
1777 #define INIT_TYPE(typeName) \
1778         (       strcpy(typeArr[eModifierType_##typeName].name, #typeName), \
1779                 strcpy(typeArr[eModifierType_##typeName].structName, #typeName "ModifierData"), \
1780                 typeArr[eModifierType_##typeName].structSize = sizeof(typeName##ModifierData), \
1781                 &typeArr[eModifierType_##typeName])
1782
1783                 mti = &typeArr[eModifierType_None];
1784                 strcpy(mti->name, "None");
1785                 strcpy(mti->structName, "ModifierData");
1786                 mti->structSize = sizeof(ModifierData);
1787                 mti->type = eModifierType_None;
1788                 mti->flags = eModifierTypeFlag_AcceptsMesh|eModifierTypeFlag_AcceptsCVs;
1789                 mti->isDisabled = noneModifier_isDisabled;
1790
1791                 mti = INIT_TYPE(Curve);
1792                 mti->type = eModifierTypeType_OnlyDeform;
1793                 mti->flags = eModifierTypeFlag_AcceptsCVs | eModifierTypeFlag_SupportsEditmode | eModifierTypeFlag_RequiresOriginalData;
1794                 mti->copyData = curveModifier_copyData;
1795                 mti->isDisabled = curveModifier_isDisabled;
1796                 mti->foreachObjectLink = curveModifier_foreachObjectLink;
1797                 mti->updateDepgraph = curveModifier_updateDepgraph;
1798                 mti->deformVerts = curveModifier_deformVerts;
1799                 mti->deformVertsEM = curveModifier_deformVertsEM;
1800
1801                 mti = INIT_TYPE(Lattice);
1802                 mti->type = eModifierTypeType_OnlyDeform;
1803                 mti->flags = eModifierTypeFlag_AcceptsCVs | eModifierTypeFlag_SupportsEditmode | eModifierTypeFlag_RequiresOriginalData;
1804                 mti->copyData = latticeModifier_copyData;
1805                 mti->isDisabled = latticeModifier_isDisabled;
1806                 mti->foreachObjectLink = latticeModifier_foreachObjectLink;
1807                 mti->updateDepgraph = latticeModifier_updateDepgraph;
1808                 mti->deformVerts = latticeModifier_deformVerts;
1809                 mti->deformVertsEM = latticeModifier_deformVertsEM;
1810
1811                 mti = INIT_TYPE(Subsurf);
1812                 mti->type = eModifierTypeType_Constructive;
1813                 mti->flags = eModifierTypeFlag_AcceptsMesh | eModifierTypeFlag_SupportsMapping | eModifierTypeFlag_SupportsEditmode | eModifierTypeFlag_EnableInEditmode;
1814                 mti->initData = subsurfModifier_initData;
1815                 mti->copyData = subsurfModifier_copyData;
1816                 mti->freeData = subsurfModifier_freeData;
1817                 mti->applyModifier = subsurfModifier_applyModifier;
1818                 mti->applyModifierEM = subsurfModifier_applyModifierEM;
1819
1820                 mti = INIT_TYPE(Build);
1821                 mti->type = eModifierTypeType_Nonconstructive;
1822                 mti->flags = eModifierTypeFlag_AcceptsMesh;
1823                 mti->initData = buildModifier_initData;
1824                 mti->copyData = buildModifier_copyData;
1825                 mti->dependsOnTime = buildModifier_dependsOnTime;
1826                 mti->applyModifier = buildModifier_applyModifier;
1827
1828                 mti = INIT_TYPE(Array);
1829                 mti->type = eModifierTypeType_Constructive;
1830                 mti->flags = eModifierTypeFlag_AcceptsMesh
1831                              | eModifierTypeFlag_SupportsMapping
1832                              | eModifierTypeFlag_SupportsEditmode
1833                              | eModifierTypeFlag_EnableInEditmode;
1834                 mti->initData = arrayModifier_initData;
1835                 mti->copyData = arrayModifier_copyData;
1836                 mti->foreachObjectLink = arrayModifier_foreachObjectLink;
1837                 mti->updateDepgraph = arrayModifier_updateDepgraph;
1838                 mti->applyModifier = arrayModifier_applyModifier;
1839                 mti->applyModifierEM = arrayModifier_applyModifierEM;
1840
1841                 mti = INIT_TYPE(Mirror);
1842                 mti->type = eModifierTypeType_Constructive;
1843                 mti->flags = eModifierTypeFlag_AcceptsMesh | eModifierTypeFlag_SupportsMapping | eModifierTypeFlag_SupportsEditmode | eModifierTypeFlag_EnableInEditmode;
1844                 mti->initData = mirrorModifier_initData;
1845                 mti->copyData = mirrorModifier_copyData;
1846                 mti->applyModifier = mirrorModifier_applyModifier;
1847                 mti->applyModifierEM = mirrorModifier_applyModifierEM;
1848
1849                 mti = INIT_TYPE(Decimate);
1850                 mti->type = eModifierTypeType_Nonconstructive;
1851                 mti->flags = eModifierTypeFlag_AcceptsMesh;
1852                 mti->initData = decimateModifier_initData;
1853                 mti->copyData = decimateModifier_copyData;
1854                 mti->applyModifier = decimateModifier_applyModifier;
1855
1856                 mti = INIT_TYPE(Wave);
1857                 mti->type = eModifierTypeType_OnlyDeform;
1858                 mti->flags = eModifierTypeFlag_AcceptsCVs | eModifierTypeFlag_SupportsEditmode;
1859                 mti->initData = waveModifier_initData;
1860                 mti->copyData = waveModifier_copyData;
1861                 mti->dependsOnTime = waveModifier_dependsOnTime;
1862                 mti->deformVerts = waveModifier_deformVerts;
1863                 mti->deformVertsEM = waveModifier_deformVertsEM;
1864
1865                 mti = INIT_TYPE(Armature);
1866                 mti->type = eModifierTypeType_OnlyDeform;
1867                 mti->flags = eModifierTypeFlag_AcceptsCVs | eModifierTypeFlag_SupportsEditmode | eModifierTypeFlag_RequiresOriginalData;
1868                 mti->initData = armatureModifier_initData;
1869                 mti->copyData = armatureModifier_copyData;
1870                 mti->isDisabled = armatureModifier_isDisabled;
1871                 mti->foreachObjectLink = armatureModifier_foreachObjectLink;
1872                 mti->updateDepgraph = armatureModifier_updateDepgraph;
1873                 mti->deformVerts = armatureModifier_deformVerts;
1874                 mti->deformVertsEM = armatureModifier_deformVertsEM;
1875
1876                 mti = INIT_TYPE(Hook);
1877                 mti->type = eModifierTypeType_OnlyDeform;
1878                 mti->flags = eModifierTypeFlag_AcceptsCVs | eModifierTypeFlag_SupportsEditmode | eModifierTypeFlag_RequiresOriginalData;
1879                 mti->initData = hookModifier_initData;
1880                 mti->copyData = hookModifier_copyData;
1881                 mti->freeData = hookModifier_freeData;
1882                 mti->isDisabled = hookModifier_isDisabled;
1883                 mti->foreachObjectLink = hookModifier_foreachObjectLink;
1884                 mti->updateDepgraph = hookModifier_updateDepgraph;
1885                 mti->deformVerts = hookModifier_deformVerts;
1886                 mti->deformVertsEM = hookModifier_deformVertsEM;
1887
1888                 mti = INIT_TYPE(Softbody);
1889                 mti->type = eModifierTypeType_OnlyDeform;
1890                 mti->flags = eModifierTypeFlag_AcceptsCVs | eModifierTypeFlag_RequiresOriginalData;
1891                 mti->deformVerts = softbodyModifier_deformVerts;
1892
1893                 mti = INIT_TYPE(Boolean);
1894                 mti->type = eModifierTypeType_Nonconstructive;
1895                 mti->flags = eModifierTypeFlag_AcceptsMesh | eModifierTypeFlag_RequiresOriginalData;
1896                 mti->copyData = booleanModifier_copyData;
1897                 mti->isDisabled = booleanModifier_isDisabled;
1898                 mti->applyModifier = booleanModifier_applyModifier;
1899                 mti->foreachObjectLink = booleanModifier_foreachObjectLink;
1900                 mti->updateDepgraph = booleanModifier_updateDepgraph;
1901
1902                 typeArrInit = 0;
1903 #undef INIT_TYPE
1904         }
1905
1906         if (type>=0 && type<NUM_MODIFIER_TYPES && typeArr[type].name[0]!='\0') {
1907                 return &typeArr[type];
1908         } else {
1909                 return NULL;
1910         }
1911 }
1912
1913 /***/
1914
1915 ModifierData *modifier_new(int type)
1916 {
1917         ModifierTypeInfo *mti = modifierType_getInfo(type);
1918         ModifierData *md = MEM_callocN(mti->structSize, mti->structName);
1919
1920         strcpy(md->name, mti->name);
1921
1922         md->type = type;
1923         md->mode = eModifierMode_Realtime|eModifierMode_Render|eModifierMode_Expanded;
1924
1925         if (mti->flags&eModifierTypeFlag_EnableInEditmode)
1926                 md->mode |= eModifierMode_Editmode;
1927
1928         if (mti->initData) mti->initData(md);
1929
1930         return md;
1931 }
1932
1933 void modifier_free(ModifierData *md) 
1934 {
1935         ModifierTypeInfo *mti = modifierType_getInfo(md->type);
1936
1937         if (mti->freeData) mti->freeData(md);
1938         if (md->error) MEM_freeN(md->error);
1939
1940         MEM_freeN(md);
1941 }
1942
1943 int modifier_dependsOnTime(ModifierData *md) 
1944 {
1945         ModifierTypeInfo *mti = modifierType_getInfo(md->type);
1946
1947         return mti->dependsOnTime && mti->dependsOnTime(md);
1948 }
1949
1950 int modifier_supportsMapping(ModifierData *md)
1951 {
1952         ModifierTypeInfo *mti = modifierType_getInfo(md->type);
1953
1954         return (        (mti->flags&eModifierTypeFlag_SupportsEditmode) &&
1955                                 (       (mti->type==eModifierTypeType_OnlyDeform ||
1956                                         (mti->flags&eModifierTypeFlag_SupportsMapping))) );
1957 }
1958
1959 ModifierData *modifiers_findByType(Object *ob, ModifierType type)
1960 {
1961         ModifierData *md = ob->modifiers.first;
1962
1963         for (; md; md=md->next)
1964                 if (md->type==type)
1965                         break;
1966
1967         return md;
1968 }
1969
1970 void modifiers_clearErrors(Object *ob)
1971 {
1972         ModifierData *md = ob->modifiers.first;
1973         int qRedraw = 0;
1974
1975         for (; md; md=md->next) {
1976                 if (md->error) {
1977                         MEM_freeN(md->error);
1978                         md->error = NULL;
1979
1980                         qRedraw = 1;
1981                 }
1982         }
1983
1984         if (qRedraw) allqueue(REDRAWBUTSEDIT, 0);
1985 }
1986
1987 void modifiers_foreachObjectLink(Object *ob, void (*walk)(void *userData, Object *ob, Object **obpoin), void *userData)
1988 {
1989         ModifierData *md = ob->modifiers.first;
1990
1991         for (; md; md=md->next) {
1992                 ModifierTypeInfo *mti = modifierType_getInfo(md->type);
1993
1994                 if (mti->foreachObjectLink) mti->foreachObjectLink(md, ob, walk, userData);
1995         }
1996 }
1997
1998 void modifier_copyData(ModifierData *md, ModifierData *target)
1999 {
2000         ModifierTypeInfo *mti = modifierType_getInfo(md->type);
2001
2002         target->mode = md->mode;
2003
2004         if (mti->copyData)
2005                 mti->copyData(md, target);
2006 }
2007
2008 int modifier_couldBeCage(ModifierData *md)
2009 {
2010         ModifierTypeInfo *mti = modifierType_getInfo(md->type);
2011
2012         return (        (md->mode&eModifierMode_Realtime) &&
2013                                 (md->mode&eModifierMode_Editmode) &&
2014                                 (!mti->isDisabled || !mti->isDisabled(md)) &&
2015                                 modifier_supportsMapping(md));  
2016 }
2017
2018 void modifier_setError(ModifierData *md, char *format, ...)
2019 {
2020         char buffer[2048];
2021         va_list ap;
2022
2023         va_start(ap, format);
2024         vsprintf(buffer, format, ap);
2025         va_end(ap);
2026
2027         if (md->error)
2028                 MEM_freeN(md->error);
2029
2030         md->error = BLI_strdup(buffer);
2031
2032         allqueue(REDRAWBUTSEDIT, 0);
2033 }
2034
2035 /* used for buttons, to find out if the 'draw deformed in editmode' option is there */
2036 /* also used in transform_conversion.c, to detect CrazySpace [tm] (2nd arg then is NULL) */
2037 int modifiers_getCageIndex(Object *ob, int *lastPossibleCageIndex_r)
2038 {
2039         ModifierData *md = ob->modifiers.first;
2040         int i, cageIndex = -1;
2041
2042                 /* Find the last modifier acting on the cage. */
2043         for (i=0; md; i++,md=md->next) {
2044                 ModifierTypeInfo *mti = modifierType_getInfo(md->type);
2045
2046                 if (!(md->mode&eModifierMode_Realtime)) continue;
2047                 if (!(md->mode&eModifierMode_Editmode)) continue;
2048                 if (mti->isDisabled && mti->isDisabled(md)) continue;
2049                 if (!(mti->flags&eModifierTypeFlag_SupportsEditmode)) continue;
2050
2051                 if (!modifier_supportsMapping(md))
2052                         break;
2053
2054                 if (lastPossibleCageIndex_r) *lastPossibleCageIndex_r = i;
2055                 if (md->mode&eModifierMode_OnCage)
2056                         cageIndex = i;
2057         }
2058
2059         return cageIndex;
2060 }
2061
2062
2063 int modifiers_isSoftbodyEnabled(Object *ob)
2064 {
2065         ModifierData *md = modifiers_findByType(ob, eModifierType_Softbody);
2066
2067                 /* Softbody not allowed in this situation, enforce! */
2068         /* if (md && ob->pd && ob->pd->deflect) {       */
2069         /* no reason for that any more BM */
2070         if (0) {
2071                 md->mode &= ~(eModifierMode_Realtime|eModifierMode_Render|eModifierMode_Editmode);
2072                 md = NULL;
2073         }
2074
2075         return (md && md->mode&(eModifierMode_Realtime|eModifierMode_Render));
2076 }
2077
2078 ModifierData *modifiers_getVirtualModifierList(Object *ob)
2079 {
2080                 /* Kinda hacky, but should be fine since we are never
2081                  * reentrant and avoid free hassles.
2082                  */
2083         static ArmatureModifierData amd;
2084         static CurveModifierData cmd;
2085         static LatticeModifierData lmd;
2086         static int init = 1;
2087
2088         if (init) {
2089                 ModifierData *md;
2090
2091                 md = modifier_new(eModifierType_Armature);
2092                 amd = *((ArmatureModifierData*) md);
2093                 modifier_free(md);
2094
2095                 md = modifier_new(eModifierType_Curve);
2096                 cmd = *((CurveModifierData*) md);
2097                 modifier_free(md);
2098
2099                 md = modifier_new(eModifierType_Lattice);
2100                 lmd = *((LatticeModifierData*) md);
2101                 modifier_free(md);
2102
2103                 amd.modifier.mode |= eModifierMode_Virtual;
2104                 cmd.modifier.mode |= eModifierMode_Virtual;
2105                 lmd.modifier.mode |= eModifierMode_Virtual;
2106
2107                 init = 0;
2108         }
2109
2110         if (ob->parent) {
2111                 if(ob->parent->type==OB_ARMATURE && ob->partype==PARSKEL) {
2112                         amd.object = ob->parent;
2113                         amd.modifier.next = ob->modifiers.first;
2114                         amd.deformflag= ((bArmature *)(ob->parent->data))->deformflag;
2115                         return &amd.modifier;
2116                 } else if(ob->parent->type==OB_CURVE && ob->partype==PARSKEL) {
2117                         cmd.object = ob->parent;
2118                         cmd.modifier.next = ob->modifiers.first;
2119                         return &cmd.modifier;
2120                 } else if(ob->parent->type==OB_LATTICE && ob->partype==PARSKEL) {
2121                         lmd.object = ob->parent;
2122                         lmd.modifier.next = ob->modifiers.first;
2123                         return &lmd.modifier;
2124                 }
2125         }
2126
2127         return ob->modifiers.first;
2128 }
2129 /* Takes an object and returns its first selected armature, else just its armature
2130    This should work for multiple armatures per object */
2131 Object *modifiers_isDeformedByArmature(Object *ob)
2132 {
2133         ModifierData *md = modifiers_getVirtualModifierList(ob);
2134         ArmatureModifierData *amd= NULL;
2135         
2136         /* return the first selected armaturem, this lets us use multiple armatures */
2137         for (; md; md=md->next) {
2138                 if (md->type==eModifierType_Armature) {
2139                         amd = (ArmatureModifierData*) md;
2140                         if (amd->object && (amd->object->flag & SELECT))
2141                                 return amd->object;
2142                 }
2143         }
2144         
2145         if (amd) /* if were still here then return the last armature */
2146                 return amd->object;
2147         
2148         return NULL;
2149 }
2150
2151 int modifiers_usesArmature(Object *ob, bArmature *arm)
2152 {
2153         ModifierData *md = modifiers_getVirtualModifierList(ob);
2154
2155         for (; md; md=md->next) {
2156                 if (md->type==eModifierType_Armature) {
2157                         ArmatureModifierData *amd = (ArmatureModifierData*) md;
2158                         if (amd->object && amd->object->data==arm) 
2159                                 return 1;
2160                 }
2161         }
2162
2163         return 0;
2164 }
2165
2166 int modifiers_isDeformed(Object *ob)
2167 {
2168         ModifierData *md = modifiers_getVirtualModifierList(ob);
2169         
2170         for (; md; md=md->next) {
2171                 if(ob==G.obedit && (md->mode & eModifierMode_Editmode)==0);
2172                 else {
2173                         if (md->type==eModifierType_Armature)
2174                                 return 1;
2175                         if (md->type==eModifierType_Curve)
2176                                 return 1;
2177                         if (md->type==eModifierType_Lattice)
2178                                 return 1;
2179                 }
2180         }
2181         return 0;
2182 }