Added scn.objects.new(obbdata) as a way of adding object data to a scene and createin...
[blender.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                 /* follow the chain of merges to the end */
653                 while(indexMap[mergeVert].merge >= 0
654                       && indexMap[mergeVert].merge != mergeVert)
655                         mergeVert = indexMap[mergeVert].merge;
656
657                 if(indexMap[mergeVert].merge == mergeVert)
658                         /* vert merged with vert that was merged with itself */
659                         newVert = indexMap[mergeVert].new;
660                 else
661                         /* use copy of the vert this vert was merged with */
662                         newVert = indexMap[mergeVert].new + copy;
663         }
664
665         return newVert;
666 }
667
668 static DispListMesh *arrayModifier_doArray(ArrayModifierData *amd,
669                                            Object *ob, DispListMesh *inDLM,
670                                            float (*vertexCos)[3],
671                                            int initFlags)
672 {
673         int i, j;
674         /* offset matrix */
675         float offset[4][4];
676         float final_offset[4][4];
677         float tmp_mat[4][4];
678         float length = amd->length;
679         int count = amd->count;
680         DispListMesh *dlm = MEM_callocN(sizeof(*dlm), "array_dlm");
681
682         IndexMapEntry *indexMap;
683
684         EdgeHash *edges;
685
686         MTC_Mat4One(offset);
687
688         if(amd->offset_type & MOD_ARR_OFF_CONST)
689                 VecAddf(offset[3], offset[3], amd->offset);
690         if(amd->offset_type & MOD_ARR_OFF_RELATIVE) {
691                 for(j = 0; j < 3; j++)
692                         offset[3][j] += amd->scale[j] * displistmesh_width(inDLM, j);
693         }
694
695         if((amd->offset_type & MOD_ARR_OFF_OBJ) && (amd->offset_ob)) {
696                 float obinv[4][4];
697                 float result_mat[4][4];
698
699                 if(ob)
700                         MTC_Mat4Invert(obinv, ob->obmat);
701                 else
702                         MTC_Mat4One(obinv);
703
704                 MTC_Mat4MulSerie(result_mat, offset,
705                                  obinv, amd->offset_ob->obmat,
706                                  NULL, NULL, NULL, NULL, NULL);
707                 MTC_Mat4CpyMat4(offset, result_mat);
708         }
709
710         if(amd->fit_type == MOD_ARR_FITCURVE && amd->curve_ob) {
711                 Curve *cu = amd->curve_ob->data;
712                 if(cu) {
713                         if(!cu->path)
714                                 calc_curvepath(amd->curve_ob);
715
716                         if(cu->path)
717                                 length = cu->path->totdist;
718                 }
719         }
720
721         /* calculate the maximum number of copies which will fit within the
722            prescribed length */
723         if(amd->fit_type == MOD_ARR_FITLENGTH
724            || amd->fit_type == MOD_ARR_FITCURVE) {
725                 float dist = sqrt(MTC_dot3Float(offset[3], offset[3]));
726
727                 if(dist != 0)
728                         /* this gives length = first copy start to last copy end
729                            add a tiny offset for floating point rounding errors */
730                         count = (length + 0.00001) / dist;
731                 else
732                         /* if the offset has no translation, just make one copy */
733                         count = 1;
734         }
735
736         if(count < 1)
737                 count = 1;
738
739         dlm->totvert = dlm->totedge = dlm->totface = 0;
740         indexMap = MEM_callocN(sizeof(*indexMap)*inDLM->totvert, "indexmap");
741
742         /* allocate memory for count duplicates (including original) */
743         dlm->mvert = MEM_callocN(sizeof(*dlm->mvert)*inDLM->totvert*count,
744                                  "dlm_mvert");
745         dlm->mface = MEM_callocN(sizeof(*dlm->mface)*inDLM->totface*count,
746                                  "dlm_mface");
747
748         if (inDLM->medge)
749                 dlm->medge = MEM_callocN(sizeof(*dlm->medge)*inDLM->totedge*count,
750                                          "dlm_medge");
751         if (inDLM->tface)
752                 dlm->tface = MEM_callocN(sizeof(*dlm->tface)*inDLM->totface*count,
753                                          "dlm_tface");
754         if (inDLM->mcol)
755                 dlm->mcol = MEM_callocN(sizeof(*dlm->mcol)*inDLM->totface*4*count,
756                                         "dlm_mcol");
757
758         /* calculate the offset matrix of the final copy (for merging) */ 
759         MTC_Mat4One(final_offset);
760
761         for(j=0; j < count - 1; j++) {
762                 MTC_Mat4MulMat4(tmp_mat, final_offset, offset);
763                 MTC_Mat4CpyMat4(final_offset, tmp_mat);
764         }
765
766         for (i=0; i<inDLM->totvert; i++) {
767                 MVert *inMV = &inDLM->mvert[i];
768                 MVert *mv = &dlm->mvert[dlm->totvert++];
769                 MVert *mv2;
770                 float co[3];
771
772                 *mv = *inMV;
773
774                 if (vertexCos) {
775                         VECCOPY(mv->co, vertexCos[i]);
776                 }
777                 if (initFlags) mv->flag |= ME_VERT_STEPINDEX;
778
779                 indexMap[i].new = dlm->totvert-1;
780                 indexMap[i].merge = -1; /* default to no merge */
781                 indexMap[i].merge_final = 0; /* default to no merge */
782
783                 VECCOPY(co, mv->co);
784                 
785                 /* Attempts to merge verts from one duplicate with verts from the
786                  * next duplicate which are closer than amd->merge_dist.
787                  * Only the first such vert pair is merged.
788                  * If verts are merged in the first duplicate pair, they are merged
789                  * in all pairs.
790                  */
791                 if((count > 1) && (amd->flags & MOD_ARR_MERGE)) {
792                         float tmp_co[3];
793                         VECCOPY(tmp_co, mv->co);
794                         MTC_Mat4MulVecfl(offset, tmp_co);
795
796                         for(j = 0; j < inDLM->totvert; j++) {
797                                 inMV = &inDLM->mvert[j];
798                                 /* if this vert is within merge limit, merge */
799                                 if(VecLenCompare(tmp_co, inMV->co, amd->merge_dist)) {
800                                         indexMap[i].merge = j;
801
802                                         /* test for merging with final copy of merge target */
803                                         if(amd->flags & MOD_ARR_MERGEFINAL) {
804                                                 inMV = &inDLM->mvert[i];
805                                                 VECCOPY(tmp_co, inDLM->mvert[j].co);
806                                                 MTC_Mat4MulVecfl(final_offset, tmp_co);
807                                                 if(VecLenCompare(tmp_co, inMV->co, amd->merge_dist))
808                                                         indexMap[i].merge_final = 1;
809                                         }
810                                         break;
811                                 }
812                         }
813                 }
814
815                 /* if no merging, generate copies of this vert */
816                 if(indexMap[i].merge < 0) {
817                         for(j=0; j < count - 1; j++) {
818                                 mv2 = &dlm->mvert[dlm->totvert++];
819
820                                 *mv2 = *mv;
821                                 MTC_Mat4MulVecfl(offset, co);
822                                 VECCOPY(mv2->co, co);
823                                 mv2->flag &= ~ME_VERT_STEPINDEX;
824                         }
825                 } else if(indexMap[i].merge != i && indexMap[i].merge_final) {
826                         /* if this vert is not merging with itself, and it is merging
827                          * with the final copy of its merge target, remove the first copy
828                          */
829                         dlm->totvert--;
830                 }
831         }
832
833         /* make a hashtable so we can avoid duplicate edges from merging */
834         edges = BLI_edgehash_new();
835
836         for (i=0; i<inDLM->totedge; i++) {
837                 MEdge *inMED = &inDLM->medge[i];
838                 MEdge med;
839                 MEdge *med2;
840                 int vert1, vert2;
841
842                 med = *inMED;
843                 med.v1 = indexMap[inMED->v1].new;
844                 med.v2 = indexMap[inMED->v2].new;
845
846                 /* if vertices are to be merged with the final copies of their
847                  * merge targets, calculate that final copy
848                  */
849                 if(indexMap[inMED->v1].merge_final) {
850                         med.v1 = calc_mapping(indexMap, indexMap[inMED->v1].merge,
851                                               count - 2);
852                 }
853                 if(indexMap[inMED->v2].merge_final) {
854                         med.v2 = calc_mapping(indexMap, indexMap[inMED->v2].merge,
855                                               count - 2);
856                 }
857
858                 if (initFlags) {
859                         med.flag |= ME_EDGEDRAW|ME_EDGERENDER|ME_EDGE_STEPINDEX;
860                 }
861
862                 if(!BLI_edgehash_haskey(edges, med.v1, med.v2)) {
863                         dlm->medge[dlm->totedge++] = med;
864                         BLI_edgehash_insert(edges, med.v1, med.v2, NULL);
865                 }
866
867                 for(j=0; j < count - 1; j++)
868                 {
869                         vert1 = calc_mapping(indexMap, inMED->v1, j);
870                         vert2 = calc_mapping(indexMap, inMED->v2, j);
871                         /* avoid duplicate edges */
872                         if(!BLI_edgehash_haskey(edges, vert1, vert2)) {
873                                 med2 = &dlm->medge[dlm->totedge++];
874
875                                 *med2 = med;
876                                 med2->v1 = vert1;
877                                 med2->v2 = vert2;
878                                 med2->flag &= ~ME_EDGE_STEPINDEX;
879
880                                 BLI_edgehash_insert(edges, med2->v1, med2->v2, NULL);
881                         }
882                 }
883         }
884
885         /* don't need the hashtable any more */
886         BLI_edgehash_free(edges, NULL);
887
888         for (i=0; i<inDLM->totface; i++) {
889                 MFace *inMF = &inDLM->mface[i];
890                 MFace *mf = &dlm->mface[dlm->totface++];
891                 MFace *mf2;
892                 TFace *tf = NULL;
893                 MCol *mc = NULL;
894
895                 *mf = *inMF;
896                 mf->v1 = indexMap[inMF->v1].new;
897                 mf->v2 = indexMap[inMF->v2].new;
898                 mf->v3 = indexMap[inMF->v3].new;
899                 if(inMF->v4)
900                         mf->v4 = indexMap[inMF->v4].new;
901
902                 /* if vertices are to be merged with the final copies of their
903                  * merge targets, calculate that final copy
904                  */
905                 if(indexMap[inMF->v1].merge_final)
906                         mf->v1 = calc_mapping(indexMap, indexMap[inMF->v1].merge, count-2);
907                 if(indexMap[inMF->v2].merge_final)
908                         mf->v2 = calc_mapping(indexMap, indexMap[inMF->v2].merge, count-2);
909                 if(indexMap[inMF->v3].merge_final)
910                         mf->v3 = calc_mapping(indexMap, indexMap[inMF->v3].merge, count-2);
911                 if(inMF->v4 && indexMap[inMF->v4].merge_final)
912                         mf->v4 = calc_mapping(indexMap, indexMap[inMF->v4].merge, count-2);
913
914                 if (initFlags) mf->flag |= ME_FACE_STEPINDEX;
915
916                 if (inDLM->tface) {
917                         TFace *inTF = &inDLM->tface[i];
918                         tf = &dlm->tface[dlm->totface-1];
919
920                         *tf = *inTF;
921                 } else if (inDLM->mcol) {
922                         MCol *inMC = &inDLM->mcol[i*4];
923                         mc = &dlm->mcol[(dlm->totface-1)*4];
924
925                         mc[0] = inMC[0];
926                         mc[1] = inMC[1];
927                         mc[2] = inMC[2];
928                         mc[3] = inMC[3];
929                 }
930                 
931                 test_index_face(mf, mc, tf, inMF->v4?4:3);
932
933                 /* if the face has fewer than 3 vertices, don't create it */
934                 if(mf->v3 == 0)
935                         dlm->totface--;
936
937                 for(j=0; j < count - 1; j++)
938                 {
939                         mf2 = &dlm->mface[dlm->totface++];
940
941                         *mf2 = *mf;
942
943                         mf2->v1 = calc_mapping(indexMap, inMF->v1, j);
944                         mf2->v2 = calc_mapping(indexMap, inMF->v2, j);
945                         mf2->v3 = calc_mapping(indexMap, inMF->v3, j);
946                         if (inMF->v4)
947                                 mf2->v4 = calc_mapping(indexMap, inMF->v4, j);
948
949                         mf2->flag &= ~ME_FACE_STEPINDEX;
950
951                         if (inDLM->tface) {
952                                 TFace *inTF = &inDLM->tface[i];
953                                 tf = &dlm->tface[dlm->totface-1];
954
955                                 *tf = *inTF;
956                         } else if (inDLM->mcol) {
957                                 MCol *inMC = &inDLM->mcol[i*4];
958                                 mc = &dlm->mcol[(dlm->totface-1)*4];
959
960                                 mc[0] = inMC[0];
961                                 mc[1] = inMC[1];
962                                 mc[2] = inMC[2];
963                                 mc[3] = inMC[3];
964                         }
965
966                         test_index_face(mf2, mc, tf, inMF->v4?4:3);
967
968                         /* if the face has fewer than 3 vertices, don't create it */
969                         if(mf2->v3 == 0)
970                                 dlm->totface--;
971                 }
972         }
973
974         MEM_freeN(indexMap);
975
976         return dlm;
977 }
978
979 static void *arrayModifier_applyModifier_internal(ModifierData *md,
980                                                   Object *ob,
981                                                   void *derivedData,
982                                                   float (*vertexCos)[3],
983                                                   int useRenderParams,
984                                                   int isFinalCalc)
985 {
986         DerivedMesh *dm = derivedData;
987         ArrayModifierData *amd = (ArrayModifierData*) md;
988         DispListMesh *outDLM, *inDLM;
989
990         if (dm) {
991                 inDLM = dm->convertToDispListMesh(dm, 1);
992         } else {
993                 Mesh *me = ob->data;
994
995                 inDLM = MEM_callocN(sizeof(*inDLM), "inDLM");
996                 inDLM->dontFreeVerts = inDLM->dontFreeOther = 1;
997                 inDLM->mvert = me->mvert;
998                 inDLM->medge = me->medge;
999                 inDLM->mface = me->mface;
1000                 inDLM->tface = me->tface;
1001                 inDLM->mcol = me->mcol;
1002                 inDLM->totvert = me->totvert;
1003                 inDLM->totedge = me->totedge;
1004                 inDLM->totface = me->totface;
1005         }
1006
1007         outDLM = arrayModifier_doArray(amd, ob, inDLM, vertexCos, dm?0:1);
1008
1009         displistmesh_free(inDLM);
1010         
1011         mesh_calc_normals(outDLM->mvert, outDLM->totvert, outDLM->mface,
1012                           outDLM->totface, &outDLM->nors);
1013
1014         return derivedmesh_from_displistmesh(outDLM, NULL);
1015 }
1016
1017 static void *arrayModifier_applyModifier(ModifierData *md,
1018                                          Object *ob,
1019                                          void *derivedData,
1020                                          float (*vertexCos)[3],
1021                                          int useRenderParams,
1022                                          int isFinalCalc)
1023 {
1024         return arrayModifier_applyModifier_internal(md, ob, derivedData,
1025                                                     vertexCos, 0, 1);
1026 }
1027
1028 static void *arrayModifier_applyModifierEM(ModifierData *md,
1029                                            Object *ob,
1030                                            void *editData,
1031                                            void *derivedData,
1032                                            float (*vertexCos)[3])
1033 {
1034         if (derivedData) {
1035                 return arrayModifier_applyModifier_internal(md, ob, derivedData,
1036                                                             vertexCos, 0, 1);
1037         } else {
1038                 ArrayModifierData *amd = (ArrayModifierData*) md;
1039                 DispListMesh *outDLM, *inDLM = displistmesh_from_editmesh(editData);
1040
1041                 outDLM = arrayModifier_doArray(amd, ob, inDLM, vertexCos, 0);
1042
1043                 displistmesh_free(inDLM);
1044
1045                 mesh_calc_normals(outDLM->mvert, outDLM->totvert,
1046                                   outDLM->mface, outDLM->totface, &outDLM->nors);
1047
1048                 return derivedmesh_from_displistmesh(outDLM, NULL);
1049         }
1050 }
1051
1052 /* Mirror */
1053
1054 static void mirrorModifier_initData(ModifierData *md)
1055 {
1056         MirrorModifierData *mmd = (MirrorModifierData*) md;
1057
1058         mmd->tolerance = 0.001;
1059 }
1060
1061 static void mirrorModifier_copyData(ModifierData *md, ModifierData *target)
1062 {
1063         MirrorModifierData *mmd = (MirrorModifierData*) md;
1064         MirrorModifierData *tmmd = (MirrorModifierData*) target;
1065
1066         tmmd->axis = mmd->axis;
1067         tmmd->tolerance = mmd->tolerance;
1068 }
1069
1070 static DispListMesh *mirrorModifier__doMirror(MirrorModifierData *mmd, DispListMesh *inDLM, float (*vertexCos)[3], int initFlags)
1071 {
1072         int i, axis = mmd->axis;
1073         float tolerance = mmd->tolerance;
1074         DispListMesh *dlm = MEM_callocN(sizeof(*dlm), "mirror_dlm");
1075         int (*indexMap)[2];
1076
1077         dlm->totvert = dlm->totedge = dlm->totface = 0;
1078         indexMap = MEM_mallocN(sizeof(*indexMap)*inDLM->totvert, "indexmap");
1079         dlm->mvert = MEM_callocN(sizeof(*dlm->mvert)*inDLM->totvert*2, "dlm_mvert");
1080         dlm->mface = MEM_callocN(sizeof(*dlm->mface)*inDLM->totface*2, "dlm_mface");
1081
1082         if (inDLM->medge) dlm->medge = MEM_callocN(sizeof(*dlm->medge)*inDLM->totedge*2, "dlm_medge");
1083         if (inDLM->tface) dlm->tface = MEM_callocN(sizeof(*dlm->tface)*inDLM->totface*2, "dlm_tface");
1084         if (inDLM->mcol) dlm->mcol = MEM_callocN(sizeof(*dlm->mcol)*inDLM->totface*4*2, "dlm_mcol");
1085
1086         for (i=0; i<inDLM->totvert; i++) {
1087                 MVert *inMV = &inDLM->mvert[i];
1088                 MVert *mv = &dlm->mvert[dlm->totvert++];
1089                 int isShared = ABS(inMV->co[axis])<=tolerance;
1090
1091                                 /* Because the topology result (# of vertices) must be the same
1092                                  * if the mesh data is overridden by vertex cos, have to calc sharedness
1093                                  * based on original coordinates. This is why we test before copy.
1094                                  */
1095                 *mv = *inMV;
1096                 if (vertexCos) {
1097                         VECCOPY(mv->co, vertexCos[i]);
1098                 }
1099                 if (initFlags) mv->flag |= ME_VERT_STEPINDEX;
1100
1101                 indexMap[i][0] = dlm->totvert-1;
1102                 indexMap[i][1] = !isShared;
1103
1104                 if (isShared) {
1105                         mv->co[axis] = 0;
1106                         mv->flag |= ME_VERT_MERGED;
1107                 } else {
1108                         MVert *mv2 = &dlm->mvert[dlm->totvert++];
1109
1110                         *mv2 = *mv;
1111                         mv2->co[axis] = -mv2->co[axis];
1112                         mv2->flag &= ~ME_VERT_STEPINDEX;
1113                 }
1114         }
1115
1116         for (i=0; i<inDLM->totedge; i++) {
1117                 MEdge *inMED = &inDLM->medge[i];
1118                 MEdge *med = &dlm->medge[dlm->totedge++];
1119
1120                 *med = *inMED;
1121                 med->v1 = indexMap[inMED->v1][0];
1122                 med->v2 = indexMap[inMED->v2][0];
1123                 if (initFlags) med->flag |= ME_EDGEDRAW|ME_EDGERENDER|ME_EDGE_STEPINDEX;
1124
1125                 if (indexMap[inMED->v1][1] || indexMap[inMED->v2][1]) {
1126                         MEdge *med2 = &dlm->medge[dlm->totedge++];
1127
1128                         *med2 = *med;
1129                         med2->v1 += indexMap[inMED->v1][1];
1130                         med2->v2 += indexMap[inMED->v2][1];
1131                         med2->flag &= ~ME_EDGE_STEPINDEX;
1132                 }
1133         }
1134
1135         for (i=0; i<inDLM->totface; i++) {
1136                 MFace *inMF = &inDLM->mface[i];
1137                 MFace *mf = &dlm->mface[dlm->totface++];
1138
1139                 *mf = *inMF;
1140                 mf->v1 = indexMap[inMF->v1][0];
1141                 mf->v2 = indexMap[inMF->v2][0];
1142                 mf->v3 = indexMap[inMF->v3][0];
1143                 mf->v4 = indexMap[inMF->v4][0];
1144                 if (initFlags) mf->flag |= ME_FACE_STEPINDEX;
1145
1146                 if (inDLM->tface) {
1147                         TFace *inTF = &inDLM->tface[i];
1148                         TFace *tf = &dlm->tface[dlm->totface-1];
1149
1150                         *tf = *inTF;
1151                 } else if (inDLM->mcol) {
1152                         MCol *inMC = &inDLM->mcol[i*4];
1153                         MCol *mc = &dlm->mcol[(dlm->totface-1)*4];
1154
1155                         mc[0] = inMC[0];
1156                         mc[1] = inMC[1];
1157                         mc[2] = inMC[2];
1158                         mc[3] = inMC[3];
1159                 }
1160                 
1161                 if (indexMap[inMF->v1][1] || indexMap[inMF->v2][1] || indexMap[inMF->v3][1] || (mf->v4 && indexMap[inMF->v4][1])) {
1162                         MFace *mf2 = &dlm->mface[dlm->totface++];
1163                         TFace *tf = NULL;
1164                         MCol *mc = NULL;
1165
1166                         *mf2 = *mf;
1167                         mf2->v1 += indexMap[inMF->v1][1];
1168                         mf2->v2 += indexMap[inMF->v2][1];
1169                         mf2->v3 += indexMap[inMF->v3][1];
1170                         if (inMF->v4) mf2->v4 += indexMap[inMF->v4][1];
1171                         mf2->flag &= ~ME_FACE_STEPINDEX;
1172
1173                         if (inDLM->tface) {
1174                                 TFace *inTF = &inDLM->tface[i];
1175                                 tf = &dlm->tface[dlm->totface-1];
1176
1177                                 *tf = *inTF;
1178                         } else if (inDLM->mcol) {
1179                                 MCol *inMC = &inDLM->mcol[i*4];
1180                                 mc = &dlm->mcol[(dlm->totface-1)*4];
1181
1182                                 mc[0] = inMC[0];
1183                                 mc[1] = inMC[1];
1184                                 mc[2] = inMC[2];
1185                                 mc[3] = inMC[3];
1186                         }
1187
1188                                 /* Flip face normal */
1189                         SWAP(int, mf2->v1, mf2->v3);
1190                         if (tf) {
1191                                 SWAP(unsigned int, tf->col[0], tf->col[2]);
1192                                 SWAP(float, tf->uv[0][0], tf->uv[2][0]);
1193                                 SWAP(float, tf->uv[0][1], tf->uv[2][1]);
1194                         } else if (mc) {
1195                                 SWAP(MCol, mc[0], mc[2]);
1196                         }
1197
1198                         test_index_face(mf2, mc, tf, inMF->v4?4:3);
1199                 }
1200         }
1201
1202         MEM_freeN(indexMap);
1203
1204         return dlm;
1205 }
1206
1207 static void *mirrorModifier_applyModifier__internal(ModifierData *md, Object *ob, void *derivedData, float (*vertexCos)[3], int useRenderParams, int isFinalCalc)
1208 {
1209         DerivedMesh *dm = derivedData;
1210         MirrorModifierData *mmd = (MirrorModifierData*) md;
1211         DispListMesh *outDLM, *inDLM;
1212
1213         if (dm) {
1214                 inDLM = dm->convertToDispListMesh(dm, 1);
1215         } else {
1216                 Mesh *me = ob->data;
1217
1218                 inDLM = MEM_callocN(sizeof(*inDLM), "inDLM");
1219                 inDLM->dontFreeVerts = inDLM->dontFreeOther = 1;
1220                 inDLM->mvert = me->mvert;
1221                 inDLM->medge = me->medge;
1222                 inDLM->mface = me->mface;
1223                 inDLM->tface = me->tface;
1224                 inDLM->mcol = me->mcol;
1225                 inDLM->totvert = me->totvert;
1226                 inDLM->totedge = me->totedge;
1227                 inDLM->totface = me->totface;
1228         }
1229
1230         outDLM = mirrorModifier__doMirror(mmd, inDLM, vertexCos, dm?0:1);
1231
1232         displistmesh_free(inDLM);
1233         
1234         mesh_calc_normals(outDLM->mvert, outDLM->totvert, outDLM->mface, outDLM->totface, &outDLM->nors);
1235         
1236         return derivedmesh_from_displistmesh(outDLM, NULL);
1237 }
1238
1239 static void *mirrorModifier_applyModifier(ModifierData *md, Object *ob, void *derivedData, float (*vertexCos)[3], int useRenderParams, int isFinalCalc)
1240 {
1241         return mirrorModifier_applyModifier__internal(md, ob, derivedData, vertexCos, 0, 1);
1242 }
1243
1244 static void *mirrorModifier_applyModifierEM(ModifierData *md, Object *ob, void *editData, void *derivedData, float (*vertexCos)[3])
1245 {
1246         if (derivedData) {
1247                 return mirrorModifier_applyModifier__internal(md, ob, derivedData, vertexCos, 0, 1);
1248         } else {
1249                 DispListMesh *inDLM, *outDLM;
1250                 MirrorModifierData *mmd = (MirrorModifierData*) md;
1251                 
1252                 inDLM = displistmesh_from_editmesh((EditMesh*)editData);
1253                 outDLM = mirrorModifier__doMirror(mmd, inDLM, vertexCos, 0);
1254                 displistmesh_free(inDLM);
1255
1256                 mesh_calc_normals(outDLM->mvert, outDLM->totvert, outDLM->mface, outDLM->totface, &outDLM->nors);
1257
1258                 return derivedmesh_from_displistmesh(outDLM, NULL);
1259         }
1260 }
1261
1262 /* Decimate */
1263
1264 static void decimateModifier_initData(ModifierData *md)
1265 {
1266         DecimateModifierData *dmd = (DecimateModifierData*) md;
1267
1268         dmd->percent = 1.0;
1269 }
1270
1271 static void decimateModifier_copyData(ModifierData *md, ModifierData *target)
1272 {
1273         DecimateModifierData *dmd = (DecimateModifierData*) md;
1274         DecimateModifierData *tdmd = (DecimateModifierData*) target;
1275
1276         tdmd->percent = dmd->percent;
1277 }
1278
1279 static void *decimateModifier_applyModifier(ModifierData *md, Object *ob, void *derivedData, float (*vertexCos)[3], int useRenderParams, int isFinalCalc)
1280 {
1281         DecimateModifierData *dmd = (DecimateModifierData*) md;
1282         DerivedMesh *dm = derivedData;
1283         Mesh *me = ob->data;
1284         MVert *mvert;
1285         MFace *mface;
1286         DispListMesh *ndlm=NULL, *dlm=NULL;
1287         LOD_Decimation_Info lod;
1288         int totvert, totface;
1289         int a, numTris;
1290
1291         if (dm) {
1292                 dlm = dm->convertToDispListMesh(dm, 1);
1293                 mvert = dlm->mvert;
1294                 mface = dlm->mface;
1295                 totvert = dlm->totvert;
1296                 totface = dlm->totface;
1297         } else {
1298                 mvert = me->mvert;
1299                 mface = me->mface;
1300                 totvert = me->totvert;
1301                 totface = me->totface;
1302         }
1303
1304         numTris = 0;
1305         for (a=0; a<totface; a++) {
1306                 MFace *mf = &mface[a];
1307                 numTris++;
1308                 if (mf->v4) numTris++;
1309         }
1310
1311         if(numTris<3) {
1312                 modifier_setError(md, "There must be more than 3 input faces (triangles).");
1313                 goto exit;
1314         }
1315
1316         lod.vertex_buffer= MEM_mallocN(3*sizeof(float)*totvert, "vertices");
1317         lod.vertex_normal_buffer= MEM_mallocN(3*sizeof(float)*totvert, "normals");
1318         lod.triangle_index_buffer= MEM_mallocN(3*sizeof(int)*numTris, "trias");
1319         lod.vertex_num= totvert;
1320         lod.face_num= numTris;
1321
1322         for(a=0; a<totvert; a++) {
1323                 MVert *mv = &mvert[a];
1324                 float *vbCo = &lod.vertex_buffer[a*3];
1325                 float *vbNo = &lod.vertex_normal_buffer[a*3];
1326
1327                 if (vertexCos) {
1328                         VECCOPY(vbCo, vertexCos[a]);
1329                 } else {
1330                         VECCOPY(vbCo, mv->co);
1331                 }
1332
1333                 vbNo[0] = mv->no[0]/32767.0f;
1334                 vbNo[1] = mv->no[1]/32767.0f;
1335                 vbNo[2] = mv->no[2]/32767.0f;
1336         }
1337
1338         numTris = 0;
1339         for(a=0; a<totface; a++) {
1340                 MFace *mf = &mface[a];
1341                 int *tri = &lod.triangle_index_buffer[3*numTris++];
1342                 tri[0]= mf->v1;
1343                 tri[1]= mf->v2;
1344                 tri[2]= mf->v3;
1345
1346                 if(mf->v4) {
1347                         tri = &lod.triangle_index_buffer[3*numTris++];
1348                         tri[0]= mf->v1;
1349                         tri[1]= mf->v3;
1350                         tri[2]= mf->v4;
1351                 }
1352         }
1353
1354         dmd->faceCount = 0;
1355         if(LOD_LoadMesh(&lod) ) {
1356                 if( LOD_PreprocessMesh(&lod) ) {
1357                         /* we assume the decim_faces tells how much to reduce */
1358
1359                         while(lod.face_num > numTris*dmd->percent) {
1360                                 if( LOD_CollapseEdge(&lod)==0) break;
1361                         }
1362
1363                         ndlm= MEM_callocN(sizeof(DispListMesh), "dispmesh");
1364                         ndlm->mvert= MEM_callocN(lod.vertex_num*sizeof(MVert), "mvert");
1365                         ndlm->totvert= lod.vertex_num;
1366                         if(lod.vertex_num>2) {
1367                                 ndlm->mface= MEM_callocN(lod.face_num*sizeof(MFace), "mface");
1368                                 ndlm->totface= dmd->faceCount = lod.face_num;
1369                         }
1370                         for(a=0; a<lod.vertex_num; a++) {
1371                                 MVert *mv = &ndlm->mvert[a];
1372                                 float *vbCo = &lod.vertex_buffer[a*3];
1373                                 
1374                                 VECCOPY(mv->co, vbCo);
1375                         }
1376
1377                         if(lod.vertex_num>2) {
1378                                 for(a=0; a<lod.face_num; a++) {
1379                                         MFace *mf = &ndlm->mface[a];
1380                                         int *tri = &lod.triangle_index_buffer[a*3];
1381                                         mf->v1 = tri[0];
1382                                         mf->v2 = tri[1];
1383                                         mf->v3 = tri[2];
1384                                         test_index_face(mf, NULL, NULL, 3);
1385                                 }
1386                                 displistmesh_add_edges(ndlm);
1387                         }
1388                 }
1389                 else {
1390                         modifier_setError(md, "Out of memory.");
1391                 }
1392
1393                 LOD_FreeDecimationData(&lod);
1394         }
1395         else {
1396                 modifier_setError(md, "Non-manifold mesh as input.");
1397         }
1398
1399         MEM_freeN(lod.vertex_buffer);
1400         MEM_freeN(lod.vertex_normal_buffer);
1401         MEM_freeN(lod.triangle_index_buffer);
1402
1403 exit:
1404         if (dlm) displistmesh_free(dlm);
1405
1406         if (ndlm) {
1407                 mesh_calc_normals(ndlm->mvert, ndlm->totvert, ndlm->mface, ndlm->totface, &ndlm->nors);
1408
1409                 return derivedmesh_from_displistmesh(ndlm, NULL);
1410         } else {
1411                 return NULL;
1412         }
1413 }
1414
1415 /* Wave */
1416
1417 static void waveModifier_initData(ModifierData *md) 
1418 {
1419         WaveModifierData *wmd = (WaveModifierData*) md; // whadya know, moved here from Iraq
1420                 
1421         wmd->flag |= (WAV_X+WAV_Y+WAV_CYCL);
1422         
1423         wmd->height= 0.5f;
1424         wmd->width= 1.5f;
1425         wmd->speed= 0.5f;
1426         wmd->narrow= 1.5f;
1427         wmd->lifetime= 0.0f;
1428         wmd->damp= 10.0f;
1429 }
1430
1431 static void waveModifier_copyData(ModifierData *md, ModifierData *target)
1432 {
1433         WaveModifierData *wmd = (WaveModifierData*) md;
1434         WaveModifierData *twmd = (WaveModifierData*) target;
1435
1436         twmd->damp = wmd->damp;
1437         twmd->flag = wmd->flag;
1438         twmd->height = wmd->height;
1439         twmd->lifetime = wmd->lifetime;
1440         twmd->narrow = wmd->narrow;
1441         twmd->speed = wmd->speed;
1442         twmd->startx = wmd->startx;
1443         twmd->starty = wmd->starty;
1444         twmd->timeoffs = wmd->timeoffs;
1445         twmd->width = wmd->width;
1446 }
1447
1448 static int waveModifier_dependsOnTime(ModifierData *md)
1449 {
1450         return 1;
1451 }
1452
1453 static void waveModifier_deformVerts(ModifierData *md, Object *ob, void *derivedData, float (*vertexCos)[3], int numVerts)
1454 {
1455         WaveModifierData *wmd = (WaveModifierData*) md;
1456         float ctime = bsystem_time(ob, 0, (float)G.scene->r.cfra, 0.0);
1457         float minfac = (float)(1.0/exp(wmd->width*wmd->narrow*wmd->width*wmd->narrow));
1458         float lifefac = wmd->height;
1459
1460         if(wmd->damp==0) wmd->damp= 10.0f;
1461
1462         if(wmd->lifetime!=0.0) {
1463                 float x= ctime - wmd->timeoffs;
1464
1465                 if(x>wmd->lifetime) {
1466                         lifefac= x-wmd->lifetime;
1467                         
1468                         if(lifefac > wmd->damp) lifefac= 0.0;
1469                         else lifefac= (float)(wmd->height*(1.0 - sqrt(lifefac/wmd->damp)));
1470                 }
1471         }
1472
1473         if(lifefac!=0.0) {
1474                 int i;
1475
1476                 for (i=0; i<numVerts; i++) {
1477                         float *co = vertexCos[i];
1478                         float x= co[0]-wmd->startx;
1479                         float y= co[1]-wmd->starty;
1480                         float amplit= 0.0f;
1481
1482                         if(wmd->flag & WAV_X) {
1483                                 if(wmd->flag & WAV_Y) amplit= (float)sqrt( (x*x + y*y));
1484                                 else amplit= x;
1485                         }
1486                         else if(wmd->flag & WAV_Y) 
1487                                 amplit= y;
1488                         
1489                         /* this way it makes nice circles */
1490                         amplit-= (ctime-wmd->timeoffs)*wmd->speed;
1491
1492                         if(wmd->flag & WAV_CYCL) {
1493                                 amplit = (float)fmod(amplit-wmd->width, 2.0*wmd->width) + wmd->width;
1494                         }
1495
1496                                 /* GAUSSIAN */
1497                         if(amplit> -wmd->width && amplit<wmd->width) {
1498                                 amplit = amplit*wmd->narrow;
1499                                 amplit= (float)(1.0/exp(amplit*amplit) - minfac);
1500
1501                                 co[2]+= lifefac*amplit;
1502                         }
1503                 }
1504         }
1505 }
1506
1507 static void waveModifier_deformVertsEM(ModifierData *md, Object *ob, void *editData, void *derivedData, float (*vertexCos)[3], int numVerts)
1508 {
1509         waveModifier_deformVerts(md, ob, NULL, vertexCos, numVerts);
1510 }
1511
1512 /* Armature */
1513
1514 static void armatureModifier_initData(ModifierData *md)
1515 {
1516         ArmatureModifierData *amd = (ArmatureModifierData*) md;
1517         
1518         amd->deformflag = ARM_DEF_ENVELOPE|ARM_DEF_VGROUP;
1519 }
1520
1521 static void armatureModifier_copyData(ModifierData *md, ModifierData *target)
1522 {
1523         ArmatureModifierData *amd = (ArmatureModifierData*) md;
1524         ArmatureModifierData *tamd = (ArmatureModifierData*) target;
1525
1526         tamd->object = amd->object;
1527         tamd->deformflag = amd->deformflag;
1528 }
1529
1530 static int armatureModifier_isDisabled(ModifierData *md)
1531 {
1532         ArmatureModifierData *amd = (ArmatureModifierData*) md;
1533
1534         return !amd->object;
1535 }
1536
1537 static void armatureModifier_foreachObjectLink(ModifierData *md, Object *ob, void (*walk)(void *userData, Object *ob, Object **obpoin), void *userData)
1538 {
1539         ArmatureModifierData *amd = (ArmatureModifierData*) md;
1540
1541         walk(userData, ob, &amd->object);
1542 }
1543
1544 static void armatureModifier_updateDepgraph(ModifierData *md, DagForest *forest, Object *ob, DagNode *obNode)
1545 {
1546         ArmatureModifierData *amd = (ArmatureModifierData*) md;
1547
1548         if (amd->object) {
1549                 DagNode *curNode = dag_get_node(forest, amd->object);
1550
1551                 dag_add_relation(forest, curNode, obNode, DAG_RL_DATA_DATA|DAG_RL_OB_DATA);
1552         }
1553 }
1554
1555 static void armatureModifier_deformVerts(ModifierData *md, Object *ob, void *derivedData, float (*vertexCos)[3], int numVerts)
1556 {
1557         ArmatureModifierData *amd = (ArmatureModifierData*) md;
1558
1559         armature_deform_verts(amd->object, ob, vertexCos, numVerts, amd->deformflag);
1560 }
1561
1562 static void armatureModifier_deformVertsEM(ModifierData *md, Object *ob, void *editData, void *derivedData, float (*vertexCos)[3], int numVerts)
1563 {
1564         ArmatureModifierData *amd = (ArmatureModifierData*) md;
1565
1566         armature_deform_verts(amd->object, ob, vertexCos, numVerts, amd->deformflag);
1567 }
1568
1569 /* Hook */
1570
1571 static void hookModifier_initData(ModifierData *md) 
1572 {
1573         HookModifierData *hmd = (HookModifierData*) md;
1574
1575         hmd->force= 1.0;
1576 }
1577
1578 static void hookModifier_copyData(ModifierData *md, ModifierData *target)
1579 {
1580         HookModifierData *hmd = (HookModifierData*) md;
1581         HookModifierData *thmd = (HookModifierData*) target;
1582
1583         VECCOPY(thmd->cent, hmd->cent);
1584         thmd->falloff = hmd->falloff;
1585         thmd->force = hmd->force;
1586         thmd->object = hmd->object;
1587         thmd->totindex = hmd->totindex;
1588         thmd->indexar = MEM_dupallocN(hmd->indexar);
1589         memcpy(thmd->parentinv, hmd->parentinv, sizeof(hmd->parentinv));
1590 }
1591
1592 static void hookModifier_freeData(ModifierData *md)
1593 {
1594         HookModifierData *hmd = (HookModifierData*) md;
1595
1596         if (hmd->indexar) MEM_freeN(hmd->indexar);
1597 }
1598
1599 static int hookModifier_isDisabled(ModifierData *md)
1600 {
1601         HookModifierData *hmd = (HookModifierData*) md;
1602
1603         return !hmd->object;
1604 }
1605
1606 static void hookModifier_foreachObjectLink(ModifierData *md, Object *ob, void (*walk)(void *userData, Object *ob, Object **obpoin), void *userData)
1607 {
1608         HookModifierData *hmd = (HookModifierData*) md;
1609
1610         walk(userData, ob, &hmd->object);
1611 }
1612
1613 static void hookModifier_updateDepgraph(ModifierData *md, DagForest *forest, Object *ob, DagNode *obNode)
1614 {
1615         HookModifierData *hmd = (HookModifierData*) md;
1616
1617         if (hmd->object) {
1618                 DagNode *curNode = dag_get_node(forest, hmd->object);
1619
1620                 dag_add_relation(forest, curNode, obNode, DAG_RL_OB_DATA);
1621         }
1622 }
1623
1624 static void hookModifier_deformVerts(ModifierData *md, Object *ob, void *derivedData, float (*vertexCos)[3], int numVerts)
1625 {
1626         HookModifierData *hmd = (HookModifierData*) md;
1627         float vec[3], mat[4][4];
1628         int i;
1629
1630         Mat4Invert(ob->imat, ob->obmat);
1631         Mat4MulSerie(mat, ob->imat, hmd->object->obmat, hmd->parentinv, NULL, NULL, NULL, NULL, NULL);
1632
1633         /* vertex indices? */
1634         if(hmd->indexar) {
1635                 for (i=0; i<hmd->totindex; i++) {
1636                         int index = hmd->indexar[i];
1637
1638                                 /* This should always be true and I don't generally like 
1639                                  * "paranoid" style code like this, but old files can have
1640                                  * indices that are out of range because old blender did
1641                                  * not correct them on exit editmode. - zr
1642                                  */
1643                         if (index<numVerts) {
1644                                 float *co = vertexCos[index];
1645                                 float fac = hmd->force;
1646
1647                                 if(hmd->falloff!=0.0) {
1648                                         float len= VecLenf(co, hmd->cent);
1649                                         if(len > hmd->falloff) fac = 0.0;
1650                                         else if(len>0.0) fac *= sqrt(1.0 - len/hmd->falloff);
1651                                 }
1652
1653                                 if(fac!=0.0) {
1654                                         VecMat4MulVecfl(vec, mat, co);
1655                                         VecLerpf(co, co, vec, fac);
1656                                 }
1657                         }
1658                 }
1659         }
1660         else {  /* vertex group hook */
1661                 bDeformGroup *curdef;
1662                 Mesh *me= ob->data;
1663                 int index=0;
1664                 
1665                 /* find the group (weak loop-in-loop) */
1666                 for (curdef = ob->defbase.first; curdef; curdef=curdef->next, index++)
1667                         if (!strcmp(curdef->name, hmd->name))
1668                                 break;
1669                 
1670                 if(curdef && me->dvert) {
1671                         MDeformVert *dvert= me->dvert;
1672                         int i, j;
1673                         
1674                         for (i=0; i < me->totvert; i++, dvert++) {
1675                                 for(j=0; j<dvert->totweight; j++) {
1676                                         if (dvert->dw[j].def_nr == index) {
1677                                                 float fac = hmd->force*dvert->dw[j].weight;
1678                                                 float *co = vertexCos[i];
1679                                                 
1680                                                 if(hmd->falloff!=0.0) {
1681                                                         float len= VecLenf(co, hmd->cent);
1682                                                         if(len > hmd->falloff) fac = 0.0;
1683                                                         else if(len>0.0) fac *= sqrt(1.0 - len/hmd->falloff);
1684                                                 }
1685                                                 
1686                                                 VecMat4MulVecfl(vec, mat, co);
1687                                                 VecLerpf(co, co, vec, fac);
1688
1689                                         }
1690                                 }
1691                         }
1692                 }
1693
1694         }
1695 }
1696
1697 static void hookModifier_deformVertsEM(ModifierData *md, Object *ob, void *editData, void *derivedData, float (*vertexCos)[3], int numVerts)
1698 {
1699         hookModifier_deformVerts(md, ob, derivedData, vertexCos, numVerts);
1700 }
1701
1702 /* Softbody */
1703
1704 static void softbodyModifier_deformVerts(ModifierData *md, Object *ob, void *derivedData, float (*vertexCos)[3], int numVerts)
1705 {
1706         sbObjectStep(ob, (float)G.scene->r.cfra, vertexCos, numVerts);
1707 }
1708
1709 /* Boolean */
1710
1711 static void booleanModifier_copyData(ModifierData *md, ModifierData *target)
1712 {
1713         BooleanModifierData *bmd = (BooleanModifierData*) md;
1714         BooleanModifierData *tbmd = (BooleanModifierData*) target;
1715
1716         tbmd->object = bmd->object;
1717         tbmd->operation = bmd->operation;
1718 }
1719
1720 static int booleanModifier_isDisabled(ModifierData *md)
1721 {
1722         BooleanModifierData *bmd = (BooleanModifierData*) md;
1723
1724         return !bmd->object;
1725 }
1726
1727 static void booleanModifier_foreachObjectLink(ModifierData *md, Object *ob, void (*walk)(void *userData, Object *ob, Object **obpoin), void *userData)
1728 {
1729         BooleanModifierData *bmd = (BooleanModifierData*) md;
1730
1731         walk(userData, ob, &bmd->object);
1732 }
1733
1734 static void booleanModifier_updateDepgraph(ModifierData *md, DagForest *forest, Object *ob, DagNode *obNode)
1735 {
1736         BooleanModifierData *bmd = (BooleanModifierData*) md;
1737
1738         if (bmd->object) {
1739                 DagNode *curNode = dag_get_node(forest, bmd->object);
1740
1741                 dag_add_relation(forest, curNode, obNode, DAG_RL_DATA_DATA|DAG_RL_OB_DATA);
1742         }
1743 }
1744
1745 static void *booleanModifier_applyModifier(ModifierData *md, Object *ob, void *derivedData, float (*vertexCos)[3], int useRenderParams, int isFinalCalc)
1746 {       
1747                 // XXX doesn't handle derived data
1748         BooleanModifierData *bmd = (BooleanModifierData*) md;
1749         
1750         /* we do a quick sanity check */
1751         if( ((Mesh *)ob->data)->totface>3 && bmd->object && ((Mesh *)bmd->object->data)->totface>3) {
1752                 DispListMesh *dlm= NewBooleanMeshDLM(bmd->object, ob, 1+bmd->operation);
1753                 
1754                 /* if new mesh returned, get derived mesh; otherwise there was
1755                  * an error, so delete the modifier object */
1756
1757                 if( dlm )
1758                         return derivedmesh_from_displistmesh(dlm, NULL);
1759                 else
1760                         bmd->object = NULL;
1761         }
1762         return derivedData;
1763 }
1764
1765 /***/
1766
1767 static ModifierTypeInfo typeArr[NUM_MODIFIER_TYPES];
1768 static int typeArrInit = 1;
1769
1770 ModifierTypeInfo *modifierType_getInfo(ModifierType type)
1771 {
1772         if (typeArrInit) {
1773                 ModifierTypeInfo *mti;
1774
1775                 memset(typeArr, 0, sizeof(typeArr));
1776
1777                 /* Initialize and return the appropriate type info structure,
1778                  * assumes that modifier has:
1779                  *  name == typeName, 
1780                  *  structName == typeName + 'ModifierData'
1781                  */
1782 #define INIT_TYPE(typeName) \
1783         (       strcpy(typeArr[eModifierType_##typeName].name, #typeName), \
1784                 strcpy(typeArr[eModifierType_##typeName].structName, #typeName "ModifierData"), \
1785                 typeArr[eModifierType_##typeName].structSize = sizeof(typeName##ModifierData), \
1786                 &typeArr[eModifierType_##typeName])
1787
1788                 mti = &typeArr[eModifierType_None];
1789                 strcpy(mti->name, "None");
1790                 strcpy(mti->structName, "ModifierData");
1791                 mti->structSize = sizeof(ModifierData);
1792                 mti->type = eModifierType_None;
1793                 mti->flags = eModifierTypeFlag_AcceptsMesh|eModifierTypeFlag_AcceptsCVs;
1794                 mti->isDisabled = noneModifier_isDisabled;
1795
1796                 mti = INIT_TYPE(Curve);
1797                 mti->type = eModifierTypeType_OnlyDeform;
1798                 mti->flags = eModifierTypeFlag_AcceptsCVs | eModifierTypeFlag_SupportsEditmode | eModifierTypeFlag_RequiresOriginalData;
1799                 mti->copyData = curveModifier_copyData;
1800                 mti->isDisabled = curveModifier_isDisabled;
1801                 mti->foreachObjectLink = curveModifier_foreachObjectLink;
1802                 mti->updateDepgraph = curveModifier_updateDepgraph;
1803                 mti->deformVerts = curveModifier_deformVerts;
1804                 mti->deformVertsEM = curveModifier_deformVertsEM;
1805
1806                 mti = INIT_TYPE(Lattice);
1807                 mti->type = eModifierTypeType_OnlyDeform;
1808                 mti->flags = eModifierTypeFlag_AcceptsCVs | eModifierTypeFlag_SupportsEditmode | eModifierTypeFlag_RequiresOriginalData;
1809                 mti->copyData = latticeModifier_copyData;
1810                 mti->isDisabled = latticeModifier_isDisabled;
1811                 mti->foreachObjectLink = latticeModifier_foreachObjectLink;
1812                 mti->updateDepgraph = latticeModifier_updateDepgraph;
1813                 mti->deformVerts = latticeModifier_deformVerts;
1814                 mti->deformVertsEM = latticeModifier_deformVertsEM;
1815
1816                 mti = INIT_TYPE(Subsurf);
1817                 mti->type = eModifierTypeType_Constructive;
1818                 mti->flags = eModifierTypeFlag_AcceptsMesh | eModifierTypeFlag_SupportsMapping | eModifierTypeFlag_SupportsEditmode | eModifierTypeFlag_EnableInEditmode;
1819                 mti->initData = subsurfModifier_initData;
1820                 mti->copyData = subsurfModifier_copyData;
1821                 mti->freeData = subsurfModifier_freeData;
1822                 mti->applyModifier = subsurfModifier_applyModifier;
1823                 mti->applyModifierEM = subsurfModifier_applyModifierEM;
1824
1825                 mti = INIT_TYPE(Build);
1826                 mti->type = eModifierTypeType_Nonconstructive;
1827                 mti->flags = eModifierTypeFlag_AcceptsMesh;
1828                 mti->initData = buildModifier_initData;
1829                 mti->copyData = buildModifier_copyData;
1830                 mti->dependsOnTime = buildModifier_dependsOnTime;
1831                 mti->applyModifier = buildModifier_applyModifier;
1832
1833                 mti = INIT_TYPE(Array);
1834                 mti->type = eModifierTypeType_Constructive;
1835                 mti->flags = eModifierTypeFlag_AcceptsMesh
1836                              | eModifierTypeFlag_SupportsMapping
1837                              | eModifierTypeFlag_SupportsEditmode
1838                              | eModifierTypeFlag_EnableInEditmode;
1839                 mti->initData = arrayModifier_initData;
1840                 mti->copyData = arrayModifier_copyData;
1841                 mti->foreachObjectLink = arrayModifier_foreachObjectLink;
1842                 mti->updateDepgraph = arrayModifier_updateDepgraph;
1843                 mti->applyModifier = arrayModifier_applyModifier;
1844                 mti->applyModifierEM = arrayModifier_applyModifierEM;
1845
1846                 mti = INIT_TYPE(Mirror);
1847                 mti->type = eModifierTypeType_Constructive;
1848                 mti->flags = eModifierTypeFlag_AcceptsMesh | eModifierTypeFlag_SupportsMapping | eModifierTypeFlag_SupportsEditmode | eModifierTypeFlag_EnableInEditmode;
1849                 mti->initData = mirrorModifier_initData;
1850                 mti->copyData = mirrorModifier_copyData;
1851                 mti->applyModifier = mirrorModifier_applyModifier;
1852                 mti->applyModifierEM = mirrorModifier_applyModifierEM;
1853
1854                 mti = INIT_TYPE(Decimate);
1855                 mti->type = eModifierTypeType_Nonconstructive;
1856                 mti->flags = eModifierTypeFlag_AcceptsMesh;
1857                 mti->initData = decimateModifier_initData;
1858                 mti->copyData = decimateModifier_copyData;
1859                 mti->applyModifier = decimateModifier_applyModifier;
1860
1861                 mti = INIT_TYPE(Wave);
1862                 mti->type = eModifierTypeType_OnlyDeform;
1863                 mti->flags = eModifierTypeFlag_AcceptsCVs | eModifierTypeFlag_SupportsEditmode;
1864                 mti->initData = waveModifier_initData;
1865                 mti->copyData = waveModifier_copyData;
1866                 mti->dependsOnTime = waveModifier_dependsOnTime;
1867                 mti->deformVerts = waveModifier_deformVerts;
1868                 mti->deformVertsEM = waveModifier_deformVertsEM;
1869
1870                 mti = INIT_TYPE(Armature);
1871                 mti->type = eModifierTypeType_OnlyDeform;
1872                 mti->flags = eModifierTypeFlag_AcceptsCVs | eModifierTypeFlag_SupportsEditmode | eModifierTypeFlag_RequiresOriginalData;
1873                 mti->initData = armatureModifier_initData;
1874                 mti->copyData = armatureModifier_copyData;
1875                 mti->isDisabled = armatureModifier_isDisabled;
1876                 mti->foreachObjectLink = armatureModifier_foreachObjectLink;
1877                 mti->updateDepgraph = armatureModifier_updateDepgraph;
1878                 mti->deformVerts = armatureModifier_deformVerts;
1879                 mti->deformVertsEM = armatureModifier_deformVertsEM;
1880
1881                 mti = INIT_TYPE(Hook);
1882                 mti->type = eModifierTypeType_OnlyDeform;
1883                 mti->flags = eModifierTypeFlag_AcceptsCVs | eModifierTypeFlag_SupportsEditmode | eModifierTypeFlag_RequiresOriginalData;
1884                 mti->initData = hookModifier_initData;
1885                 mti->copyData = hookModifier_copyData;
1886                 mti->freeData = hookModifier_freeData;
1887                 mti->isDisabled = hookModifier_isDisabled;
1888                 mti->foreachObjectLink = hookModifier_foreachObjectLink;
1889                 mti->updateDepgraph = hookModifier_updateDepgraph;
1890                 mti->deformVerts = hookModifier_deformVerts;
1891                 mti->deformVertsEM = hookModifier_deformVertsEM;
1892
1893                 mti = INIT_TYPE(Softbody);
1894                 mti->type = eModifierTypeType_OnlyDeform;
1895                 mti->flags = eModifierTypeFlag_AcceptsCVs | eModifierTypeFlag_RequiresOriginalData;
1896                 mti->deformVerts = softbodyModifier_deformVerts;
1897
1898                 mti = INIT_TYPE(Boolean);
1899                 mti->type = eModifierTypeType_Nonconstructive;
1900                 mti->flags = eModifierTypeFlag_AcceptsMesh | eModifierTypeFlag_RequiresOriginalData;
1901                 mti->copyData = booleanModifier_copyData;
1902                 mti->isDisabled = booleanModifier_isDisabled;
1903                 mti->applyModifier = booleanModifier_applyModifier;
1904                 mti->foreachObjectLink = booleanModifier_foreachObjectLink;
1905                 mti->updateDepgraph = booleanModifier_updateDepgraph;
1906
1907                 typeArrInit = 0;
1908 #undef INIT_TYPE
1909         }
1910
1911         if (type>=0 && type<NUM_MODIFIER_TYPES && typeArr[type].name[0]!='\0') {
1912                 return &typeArr[type];
1913         } else {
1914                 return NULL;
1915         }
1916 }
1917
1918 /***/
1919
1920 ModifierData *modifier_new(int type)
1921 {
1922         ModifierTypeInfo *mti = modifierType_getInfo(type);
1923         ModifierData *md = MEM_callocN(mti->structSize, mti->structName);
1924
1925         strcpy(md->name, mti->name);
1926
1927         md->type = type;
1928         md->mode = eModifierMode_Realtime|eModifierMode_Render|eModifierMode_Expanded;
1929
1930         if (mti->flags&eModifierTypeFlag_EnableInEditmode)
1931                 md->mode |= eModifierMode_Editmode;
1932
1933         if (mti->initData) mti->initData(md);
1934
1935         return md;
1936 }
1937
1938 void modifier_free(ModifierData *md) 
1939 {
1940         ModifierTypeInfo *mti = modifierType_getInfo(md->type);
1941
1942         if (mti->freeData) mti->freeData(md);
1943         if (md->error) MEM_freeN(md->error);
1944
1945         MEM_freeN(md);
1946 }
1947
1948 int modifier_dependsOnTime(ModifierData *md) 
1949 {
1950         ModifierTypeInfo *mti = modifierType_getInfo(md->type);
1951
1952         return mti->dependsOnTime && mti->dependsOnTime(md);
1953 }
1954
1955 int modifier_supportsMapping(ModifierData *md)
1956 {
1957         ModifierTypeInfo *mti = modifierType_getInfo(md->type);
1958
1959         return (        (mti->flags&eModifierTypeFlag_SupportsEditmode) &&
1960                                 (       (mti->type==eModifierTypeType_OnlyDeform ||
1961                                         (mti->flags&eModifierTypeFlag_SupportsMapping))) );
1962 }
1963
1964 ModifierData *modifiers_findByType(Object *ob, ModifierType type)
1965 {
1966         ModifierData *md = ob->modifiers.first;
1967
1968         for (; md; md=md->next)
1969                 if (md->type==type)
1970                         break;
1971
1972         return md;
1973 }
1974
1975 void modifiers_clearErrors(Object *ob)
1976 {
1977         ModifierData *md = ob->modifiers.first;
1978         int qRedraw = 0;
1979
1980         for (; md; md=md->next) {
1981                 if (md->error) {
1982                         MEM_freeN(md->error);
1983                         md->error = NULL;
1984
1985                         qRedraw = 1;
1986                 }
1987         }
1988
1989         if (qRedraw) allqueue(REDRAWBUTSEDIT, 0);
1990 }
1991
1992 void modifiers_foreachObjectLink(Object *ob, void (*walk)(void *userData, Object *ob, Object **obpoin), void *userData)
1993 {
1994         ModifierData *md = ob->modifiers.first;
1995
1996         for (; md; md=md->next) {
1997                 ModifierTypeInfo *mti = modifierType_getInfo(md->type);
1998
1999                 if (mti->foreachObjectLink) mti->foreachObjectLink(md, ob, walk, userData);
2000         }
2001 }
2002
2003 void modifier_copyData(ModifierData *md, ModifierData *target)
2004 {
2005         ModifierTypeInfo *mti = modifierType_getInfo(md->type);
2006
2007         target->mode = md->mode;
2008
2009         if (mti->copyData)
2010                 mti->copyData(md, target);
2011 }
2012
2013 int modifier_couldBeCage(ModifierData *md)
2014 {
2015         ModifierTypeInfo *mti = modifierType_getInfo(md->type);
2016
2017         return (        (md->mode&eModifierMode_Realtime) &&
2018                                 (md->mode&eModifierMode_Editmode) &&
2019                                 (!mti->isDisabled || !mti->isDisabled(md)) &&
2020                                 modifier_supportsMapping(md));  
2021 }
2022
2023 void modifier_setError(ModifierData *md, char *format, ...)
2024 {
2025         char buffer[2048];
2026         va_list ap;
2027
2028         va_start(ap, format);
2029         vsprintf(buffer, format, ap);
2030         va_end(ap);
2031
2032         if (md->error)
2033                 MEM_freeN(md->error);
2034
2035         md->error = BLI_strdup(buffer);
2036
2037         allqueue(REDRAWBUTSEDIT, 0);
2038 }
2039
2040 /* used for buttons, to find out if the 'draw deformed in editmode' option is there */
2041 /* also used in transform_conversion.c, to detect CrazySpace [tm] (2nd arg then is NULL) */
2042 int modifiers_getCageIndex(Object *ob, int *lastPossibleCageIndex_r)
2043 {
2044         ModifierData *md = ob->modifiers.first;
2045         int i, cageIndex = -1;
2046
2047                 /* Find the last modifier acting on the cage. */
2048         for (i=0; md; i++,md=md->next) {
2049                 ModifierTypeInfo *mti = modifierType_getInfo(md->type);
2050
2051                 if (!(md->mode&eModifierMode_Realtime)) continue;
2052                 if (!(md->mode&eModifierMode_Editmode)) continue;
2053                 if (mti->isDisabled && mti->isDisabled(md)) continue;
2054                 if (!(mti->flags&eModifierTypeFlag_SupportsEditmode)) continue;
2055
2056                 if (!modifier_supportsMapping(md))
2057                         break;
2058
2059                 if (lastPossibleCageIndex_r) *lastPossibleCageIndex_r = i;
2060                 if (md->mode&eModifierMode_OnCage)
2061                         cageIndex = i;
2062         }
2063
2064         return cageIndex;
2065 }
2066
2067
2068 int modifiers_isSoftbodyEnabled(Object *ob)
2069 {
2070         ModifierData *md = modifiers_findByType(ob, eModifierType_Softbody);
2071
2072                 /* Softbody not allowed in this situation, enforce! */
2073         /* if (md && ob->pd && ob->pd->deflect) {       */
2074         /* no reason for that any more BM */
2075         if (0) {
2076                 md->mode &= ~(eModifierMode_Realtime|eModifierMode_Render|eModifierMode_Editmode);
2077                 md = NULL;
2078         }
2079
2080         return (md && md->mode&(eModifierMode_Realtime|eModifierMode_Render));
2081 }
2082
2083 ModifierData *modifiers_getVirtualModifierList(Object *ob)
2084 {
2085                 /* Kinda hacky, but should be fine since we are never
2086                  * reentrant and avoid free hassles.
2087                  */
2088         static ArmatureModifierData amd;
2089         static CurveModifierData cmd;
2090         static LatticeModifierData lmd;
2091         static int init = 1;
2092
2093         if (init) {
2094                 ModifierData *md;
2095
2096                 md = modifier_new(eModifierType_Armature);
2097                 amd = *((ArmatureModifierData*) md);
2098                 modifier_free(md);
2099
2100                 md = modifier_new(eModifierType_Curve);
2101                 cmd = *((CurveModifierData*) md);
2102                 modifier_free(md);
2103
2104                 md = modifier_new(eModifierType_Lattice);
2105                 lmd = *((LatticeModifierData*) md);
2106                 modifier_free(md);
2107
2108                 amd.modifier.mode |= eModifierMode_Virtual;
2109                 cmd.modifier.mode |= eModifierMode_Virtual;
2110                 lmd.modifier.mode |= eModifierMode_Virtual;
2111
2112                 init = 0;
2113         }
2114
2115         if (ob->parent) {
2116                 if(ob->parent->type==OB_ARMATURE && ob->partype==PARSKEL) {
2117                         amd.object = ob->parent;
2118                         amd.modifier.next = ob->modifiers.first;
2119                         amd.deformflag= ((bArmature *)(ob->parent->data))->deformflag;
2120                         return &amd.modifier;
2121                 } else if(ob->parent->type==OB_CURVE && ob->partype==PARSKEL) {
2122                         cmd.object = ob->parent;
2123                         cmd.modifier.next = ob->modifiers.first;
2124                         return &cmd.modifier;
2125                 } else if(ob->parent->type==OB_LATTICE && ob->partype==PARSKEL) {
2126                         lmd.object = ob->parent;
2127                         lmd.modifier.next = ob->modifiers.first;
2128                         return &lmd.modifier;
2129                 }
2130         }
2131
2132         return ob->modifiers.first;
2133 }
2134 /* Takes an object and returns its first selected armature, else just its armature
2135    This should work for multiple armatures per object */
2136 Object *modifiers_isDeformedByArmature(Object *ob)
2137 {
2138         ModifierData *md = modifiers_getVirtualModifierList(ob);
2139         ArmatureModifierData *amd= NULL;
2140         
2141         /* return the first selected armaturem, this lets us use multiple armatures */
2142         for (; md; md=md->next) {
2143                 if (md->type==eModifierType_Armature) {
2144                         amd = (ArmatureModifierData*) md;
2145                         if (amd->object && (amd->object->flag & SELECT))
2146                                 return amd->object;
2147                 }
2148         }
2149         
2150         if (amd) /* if were still here then return the last armature */
2151                 return amd->object;
2152         
2153         return NULL;
2154 }
2155
2156 int modifiers_usesArmature(Object *ob, bArmature *arm)
2157 {
2158         ModifierData *md = modifiers_getVirtualModifierList(ob);
2159
2160         for (; md; md=md->next) {
2161                 if (md->type==eModifierType_Armature) {
2162                         ArmatureModifierData *amd = (ArmatureModifierData*) md;
2163                         if (amd->object && amd->object->data==arm) 
2164                                 return 1;
2165                 }
2166         }
2167
2168         return 0;
2169 }
2170
2171 int modifiers_isDeformed(Object *ob)
2172 {
2173         ModifierData *md = modifiers_getVirtualModifierList(ob);
2174         
2175         for (; md; md=md->next) {
2176                 if(ob==G.obedit && (md->mode & eModifierMode_Editmode)==0);
2177                 else {
2178                         if (md->type==eModifierType_Armature)
2179                                 return 1;
2180                         if (md->type==eModifierType_Curve)
2181                                 return 1;
2182                         if (md->type==eModifierType_Lattice)
2183                                 return 1;
2184                 }
2185         }
2186         return 0;
2187 }