removed unused includes, except for physics and particle related files
[blender-staging.git] / source / blender / blenkernel / intern / modifier.c
1 /*
2 * $Id$
3 *
4 * ***** BEGIN GPL LICENSE BLOCK *****
5 *
6 * This program is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU General Public License
8 * as published by the Free Software Foundation; either version 2
9 * of the License, or (at your option) any later version.
10 *
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software  Foundation,
18 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
19 *
20 * The Original Code is Copyright (C) 2005 by the Blender Foundation.
21 * All rights reserved.
22 *
23 * Contributor(s): Daniel Dunbar
24 *                 Ton Roosendaal,
25 *                 Ben Batt,
26 *                 Brecht Van Lommel,
27 *                 Campbell Barton
28 *
29 * ***** END GPL LICENSE BLOCK *****
30 *
31 * Modifier stack implementation.
32 *
33 * BKE_modifier.h contains the function prototypes for this file.
34 *
35 */
36
37 #include "stddef.h"
38 #include "string.h"
39 #include "stdarg.h"
40 #include "math.h"
41 #include "float.h"
42
43 #include "BLI_kdtree.h"
44 #include "BLI_rand.h"
45
46 #include "MEM_guardedalloc.h"
47
48 #include "DNA_armature_types.h"
49 #include "DNA_camera_types.h"
50 #include "DNA_curve_types.h"
51 #include "DNA_key_types.h"
52 #include "DNA_material_types.h"
53 #include "DNA_object_fluidsim.h"
54
55
56 #include "BKE_action.h"
57 #include "BKE_bmesh.h"
58 #include "BKE_booleanops.h"
59 #include "BKE_cloth.h"
60 #include "BKE_cdderivedmesh.h"
61 #include "BKE_displist.h"
62 #include "BKE_fluidsim.h"
63 #include "BKE_global.h"
64 #include "BKE_multires.h"
65 #include "BKE_key.h"
66 #include "BKE_lattice.h"
67 #include "BKE_material.h"
68 #include "BKE_mesh.h"
69 #include "BKE_modifier.h"
70 #include "BKE_object.h"
71 #include "BKE_particle.h"
72 #include "BKE_pointcache.h"
73 #include "BKE_scene.h"
74 #include "BKE_smoke.h"
75 #include "BKE_softbody.h"
76 #include "BKE_subsurf.h"
77 #include "BKE_texture.h"
78
79 #include "depsgraph_private.h"
80 #include "BKE_deform.h"
81 #include "BKE_shrinkwrap.h"
82 #include "BKE_simple_deform.h"
83
84 #include "LOD_decimation.h"
85
86 #include "CCGSubSurf.h"
87
88 #include "RE_shader_ext.h"
89
90 /* Utility */
91
92 static int is_last_displist(Object *ob)
93 {
94         Curve *cu = ob->data;
95         static int curvecount=0, totcurve=0;
96
97         if(curvecount == 0){
98                 DispList *dl;
99
100                 totcurve = 0;
101                 for(dl=cu->disp.first; dl; dl=dl->next)
102                         totcurve++;
103         }
104
105         curvecount++;
106
107         if(curvecount == totcurve){
108                 curvecount = 0;
109                 return 1;
110         }
111
112         return 0;
113 }
114
115 /* returns a derived mesh if dm == NULL, for deforming modifiers that need it */
116 static DerivedMesh *get_dm(Scene *scene, Object *ob, EditMesh *em, DerivedMesh *dm, float (*vertexCos)[3], int orco)
117 {
118         if(dm)
119                 return dm;
120
121         if(ob->type==OB_MESH) {
122                 if(em) dm= CDDM_from_editmesh(em, ob->data);
123                 else dm = CDDM_from_mesh((Mesh*)(ob->data), ob);
124
125                 if(vertexCos) {
126                         CDDM_apply_vert_coords(dm, vertexCos);
127                         //CDDM_calc_normals(dm);
128                 }
129                 
130                 if(orco)
131                         DM_add_vert_layer(dm, CD_ORCO, CD_ASSIGN, get_mesh_orco_verts(ob));
132         }
133         else if(ELEM3(ob->type,OB_FONT,OB_CURVE,OB_SURF)) {
134                 if(is_last_displist(ob)) {
135                         dm= CDDM_from_curve(ob);
136                 }
137         }
138
139         return dm;
140 }
141
142 /* returns a cdderivedmesh if dm == NULL or is another type of derivedmesh */
143 static DerivedMesh *get_cddm(Scene *scene, Object *ob, EditMesh *em, DerivedMesh *dm, float (*vertexCos)[3])
144 {
145         if(dm && dm->type == DM_TYPE_CDDM)
146                 return dm;
147
148         if(!dm) {
149                 dm= get_dm(scene, ob, em, dm, vertexCos, 0);
150         }
151         else {
152                 dm= CDDM_copy(dm);
153                 CDDM_apply_vert_coords(dm, vertexCos);
154         }
155
156         if(dm)
157                 CDDM_calc_normals(dm);
158         
159         return dm;
160 }
161
162 /***/
163
164 static int noneModifier_isDisabled(ModifierData *md, int userRenderParams)
165 {
166         return 1;
167 }
168
169 /* Curve */
170
171 static void curveModifier_initData(ModifierData *md)
172 {
173         CurveModifierData *cmd = (CurveModifierData*) md;
174
175         cmd->defaxis = MOD_CURVE_POSX;
176 }
177
178 static void curveModifier_copyData(ModifierData *md, ModifierData *target)
179 {
180         CurveModifierData *cmd = (CurveModifierData*) md;
181         CurveModifierData *tcmd = (CurveModifierData*) target;
182
183         tcmd->defaxis = cmd->defaxis;
184         tcmd->object = cmd->object;
185         strncpy(tcmd->name, cmd->name, 32);
186 }
187
188 static CustomDataMask curveModifier_requiredDataMask(Object *ob, ModifierData *md)
189 {
190         CurveModifierData *cmd = (CurveModifierData *)md;
191         CustomDataMask dataMask = 0;
192
193         /* ask for vertexgroups if we need them */
194         if(cmd->name[0]) dataMask |= (1 << CD_MDEFORMVERT);
195
196         return dataMask;
197 }
198
199 static int curveModifier_isDisabled(ModifierData *md, int userRenderParams)
200 {
201         CurveModifierData *cmd = (CurveModifierData*) md;
202
203         return !cmd->object;
204 }
205
206 static void curveModifier_foreachObjectLink(
207                                             ModifierData *md, Object *ob,
208          void (*walk)(void *userData, Object *ob, Object **obpoin),
209                 void *userData)
210 {
211         CurveModifierData *cmd = (CurveModifierData*) md;
212
213         walk(userData, ob, &cmd->object);
214 }
215
216 static void curveModifier_updateDepgraph(
217                                          ModifierData *md, DagForest *forest, Scene *scene,
218       Object *ob, DagNode *obNode)
219 {
220         CurveModifierData *cmd = (CurveModifierData*) md;
221
222         if (cmd->object) {
223                 DagNode *curNode = dag_get_node(forest, cmd->object);
224
225                 dag_add_relation(forest, curNode, obNode,
226                                  DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Curve Modifier");
227         }
228 }
229
230 static void curveModifier_deformVerts(
231                                       ModifierData *md, Object *ob, DerivedMesh *derivedData,
232           float (*vertexCos)[3], int numVerts, int useRenderParams, int isFinalCalc)
233 {
234         CurveModifierData *cmd = (CurveModifierData*) md;
235
236         curve_deform_verts(md->scene, cmd->object, ob, derivedData, vertexCos, numVerts,
237                            cmd->name, cmd->defaxis);
238 }
239
240 static void curveModifier_deformVertsEM(
241                                         ModifierData *md, Object *ob, EditMesh *editData,
242      DerivedMesh *derivedData, float (*vertexCos)[3], int numVerts)
243 {
244         DerivedMesh *dm = derivedData;
245
246         if(!derivedData) dm = CDDM_from_editmesh(editData, ob->data);
247
248         curveModifier_deformVerts(md, ob, dm, vertexCos, numVerts, 0, 0);
249
250         if(!derivedData) dm->release(dm);
251 }
252
253 /* Lattice */
254
255 static void latticeModifier_copyData(ModifierData *md, ModifierData *target)
256 {
257         LatticeModifierData *lmd = (LatticeModifierData*) md;
258         LatticeModifierData *tlmd = (LatticeModifierData*) target;
259
260         tlmd->object = lmd->object;
261         strncpy(tlmd->name, lmd->name, 32);
262 }
263
264 static CustomDataMask latticeModifier_requiredDataMask(Object *ob, ModifierData *md)
265 {
266         LatticeModifierData *lmd = (LatticeModifierData *)md;
267         CustomDataMask dataMask = 0;
268
269         /* ask for vertexgroups if we need them */
270         if(lmd->name[0]) dataMask |= (1 << CD_MDEFORMVERT);
271
272         return dataMask;
273 }
274
275 static int latticeModifier_isDisabled(ModifierData *md, int userRenderParams)
276 {
277         LatticeModifierData *lmd = (LatticeModifierData*) md;
278
279         return !lmd->object;
280 }
281
282 static void latticeModifier_foreachObjectLink(
283                                               ModifierData *md, Object *ob,
284            void (*walk)(void *userData, Object *ob, Object **obpoin),
285                   void *userData)
286 {
287         LatticeModifierData *lmd = (LatticeModifierData*) md;
288
289         walk(userData, ob, &lmd->object);
290 }
291
292 static void latticeModifier_updateDepgraph(ModifierData *md, DagForest *forest,  Scene *scene,
293                                            Object *ob, DagNode *obNode)
294 {
295         LatticeModifierData *lmd = (LatticeModifierData*) md;
296
297         if(lmd->object) {
298                 DagNode *latNode = dag_get_node(forest, lmd->object);
299
300                 dag_add_relation(forest, latNode, obNode,
301                                  DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Lattice Modifier");
302         }
303 }
304
305 static void modifier_vgroup_cache(ModifierData *md, float (*vertexCos)[3])
306 {
307         while((md=md->next) && md->type==eModifierType_Armature) {
308                 ArmatureModifierData *amd = (ArmatureModifierData*) md;
309                 if(amd->multi && amd->prevCos==NULL)
310                         amd->prevCos= MEM_dupallocN(vertexCos);
311                 else
312                         break;
313         }
314         /* lattice/mesh modifier too */
315 }
316
317
318 static void latticeModifier_deformVerts(
319                                         ModifierData *md, Object *ob, DerivedMesh *derivedData,
320      float (*vertexCos)[3], int numVerts, int useRenderParams, int isFinalCalc)
321 {
322         LatticeModifierData *lmd = (LatticeModifierData*) md;
323
324
325         modifier_vgroup_cache(md, vertexCos); /* if next modifier needs original vertices */
326         
327         lattice_deform_verts(lmd->object, ob, derivedData,
328                              vertexCos, numVerts, lmd->name);
329 }
330
331 static void latticeModifier_deformVertsEM(
332                                           ModifierData *md, Object *ob, EditMesh *editData,
333        DerivedMesh *derivedData, float (*vertexCos)[3], int numVerts)
334 {
335         DerivedMesh *dm = derivedData;
336
337         if(!derivedData) dm = CDDM_from_editmesh(editData, ob->data);
338
339         latticeModifier_deformVerts(md, ob, dm, vertexCos, numVerts, 0, 0);
340
341         if(!derivedData) dm->release(dm);
342 }
343
344 /* Subsurf */
345
346 static void subsurfModifier_initData(ModifierData *md)
347 {
348         SubsurfModifierData *smd = (SubsurfModifierData*) md;
349
350         smd->levels = 1;
351         smd->renderLevels = 2;
352         smd->flags |= eSubsurfModifierFlag_SubsurfUv;
353 }
354
355 static void subsurfModifier_copyData(ModifierData *md, ModifierData *target)
356 {
357         SubsurfModifierData *smd = (SubsurfModifierData*) md;
358         SubsurfModifierData *tsmd = (SubsurfModifierData*) target;
359
360         tsmd->flags = smd->flags;
361         tsmd->levels = smd->levels;
362         tsmd->renderLevels = smd->renderLevels;
363         tsmd->subdivType = smd->subdivType;
364 }
365
366 static void subsurfModifier_freeData(ModifierData *md)
367 {
368         SubsurfModifierData *smd = (SubsurfModifierData*) md;
369
370         if(smd->mCache) {
371                 ccgSubSurf_free(smd->mCache);
372         }
373         if(smd->emCache) {
374                 ccgSubSurf_free(smd->emCache);
375         }
376 }
377
378 static int subsurfModifier_isDisabled(ModifierData *md, int useRenderParams)
379 {
380         SubsurfModifierData *smd = (SubsurfModifierData*) md;
381         int levels= (useRenderParams)? smd->renderLevels: smd->levels;
382
383         return get_render_subsurf_level(&md->scene->r, levels) == 0;
384 }
385
386 static DerivedMesh *subsurfModifier_applyModifier(
387                 ModifierData *md, Object *ob, DerivedMesh *derivedData,
388   int useRenderParams, int isFinalCalc)
389 {
390         SubsurfModifierData *smd = (SubsurfModifierData*) md;
391         DerivedMesh *result;
392
393         result = subsurf_make_derived_from_derived(derivedData, smd,
394                         useRenderParams, NULL, isFinalCalc, 0);
395         
396         if(useRenderParams || !isFinalCalc) {
397                 DerivedMesh *cddm= CDDM_copy(result);
398                 result->release(result);
399                 result= cddm;
400         }
401
402         return result;
403 }
404
405 static DerivedMesh *subsurfModifier_applyModifierEM(
406                 ModifierData *md, Object *ob, EditMesh *editData,
407   DerivedMesh *derivedData)
408 {
409         SubsurfModifierData *smd = (SubsurfModifierData*) md;
410         DerivedMesh *result;
411
412         result = subsurf_make_derived_from_derived(derivedData, smd, 0,
413                         NULL, 0, 1);
414
415         return result;
416 }
417
418 /* Build */
419
420 static void buildModifier_initData(ModifierData *md)
421 {
422         BuildModifierData *bmd = (BuildModifierData*) md;
423
424         bmd->start = 1.0;
425         bmd->length = 100.0;
426 }
427
428 static void buildModifier_copyData(ModifierData *md, ModifierData *target)
429 {
430         BuildModifierData *bmd = (BuildModifierData*) md;
431         BuildModifierData *tbmd = (BuildModifierData*) target;
432
433         tbmd->start = bmd->start;
434         tbmd->length = bmd->length;
435         tbmd->randomize = bmd->randomize;
436         tbmd->seed = bmd->seed;
437 }
438
439 static int buildModifier_dependsOnTime(ModifierData *md)
440 {
441         return 1;
442 }
443
444 static DerivedMesh *buildModifier_applyModifier(ModifierData *md, Object *ob,
445                 DerivedMesh *derivedData,
446   int useRenderParams, int isFinalCalc)
447 {
448         DerivedMesh *dm = derivedData;
449         DerivedMesh *result;
450         BuildModifierData *bmd = (BuildModifierData*) md;
451         int i;
452         int numFaces, numEdges;
453         int maxVerts, maxEdges, maxFaces;
454         int *vertMap, *edgeMap, *faceMap;
455         float frac;
456         GHashIterator *hashIter;
457         /* maps vert indices in old mesh to indices in new mesh */
458         GHash *vertHash = BLI_ghash_new(BLI_ghashutil_inthash,
459                                         BLI_ghashutil_intcmp);
460         /* maps edge indices in new mesh to indices in old mesh */
461         GHash *edgeHash = BLI_ghash_new(BLI_ghashutil_inthash,
462                                         BLI_ghashutil_intcmp);
463
464         maxVerts = dm->getNumVerts(dm);
465         vertMap = MEM_callocN(sizeof(*vertMap) * maxVerts,
466                               "build modifier vertMap");
467         for(i = 0; i < maxVerts; ++i) vertMap[i] = i;
468
469         maxEdges = dm->getNumEdges(dm);
470         edgeMap = MEM_callocN(sizeof(*edgeMap) * maxEdges,
471                               "build modifier edgeMap");
472         for(i = 0; i < maxEdges; ++i) edgeMap[i] = i;
473
474         maxFaces = dm->getNumFaces(dm);
475         faceMap = MEM_callocN(sizeof(*faceMap) * maxFaces,
476                               "build modifier faceMap");
477         for(i = 0; i < maxFaces; ++i) faceMap[i] = i;
478
479         if (ob) {
480                 frac = bsystem_time(md->scene, ob, md->scene->r.cfra,
481                                     bmd->start - 1.0f) / bmd->length;
482         } else {
483                 frac = md->scene->r.cfra - bmd->start / bmd->length;
484         }
485         CLAMP(frac, 0.0, 1.0);
486
487         numFaces = dm->getNumFaces(dm) * frac;
488         numEdges = dm->getNumEdges(dm) * frac;
489
490         /* if there's at least one face, build based on faces */
491         if(numFaces) {
492                 int maxEdges;
493
494                 if(bmd->randomize)
495                         BLI_array_randomize(faceMap, sizeof(*faceMap),
496                                             maxFaces, bmd->seed);
497
498                 /* get the set of all vert indices that will be in the final mesh,
499                 * mapped to the new indices
500                 */
501                 for(i = 0; i < numFaces; ++i) {
502                         MFace mf;
503                         dm->getFace(dm, faceMap[i], &mf);
504
505                         if(!BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(mf.v1)))
506                                 BLI_ghash_insert(vertHash, SET_INT_IN_POINTER(mf.v1),
507                                         SET_INT_IN_POINTER(BLI_ghash_size(vertHash)));
508                         if(!BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(mf.v2)))
509                                 BLI_ghash_insert(vertHash, SET_INT_IN_POINTER(mf.v2),
510                                         SET_INT_IN_POINTER(BLI_ghash_size(vertHash)));
511                         if(!BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(mf.v3)))
512                                 BLI_ghash_insert(vertHash, SET_INT_IN_POINTER(mf.v3),
513                                         SET_INT_IN_POINTER(BLI_ghash_size(vertHash)));
514                         if(mf.v4 && !BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(mf.v4)))
515                                 BLI_ghash_insert(vertHash, SET_INT_IN_POINTER(mf.v4),
516                                         SET_INT_IN_POINTER(BLI_ghash_size(vertHash)));
517                 }
518
519                 /* get the set of edges that will be in the new mesh (i.e. all edges
520                 * that have both verts in the new mesh)
521                 */
522                 maxEdges = dm->getNumEdges(dm);
523                 for(i = 0; i < maxEdges; ++i) {
524                         MEdge me;
525                         dm->getEdge(dm, i, &me);
526
527                         if(BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(me.v1))
528                                                 && BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(me.v2)))
529                                 BLI_ghash_insert(edgeHash,
530                                         SET_INT_IN_POINTER(BLI_ghash_size(edgeHash)), SET_INT_IN_POINTER(i));
531                 }
532         } else if(numEdges) {
533                 if(bmd->randomize)
534                         BLI_array_randomize(edgeMap, sizeof(*edgeMap),
535                                             maxEdges, bmd->seed);
536
537                 /* get the set of all vert indices that will be in the final mesh,
538                 * mapped to the new indices
539                 */
540                 for(i = 0; i < numEdges; ++i) {
541                         MEdge me;
542                         dm->getEdge(dm, edgeMap[i], &me);
543
544                         if(!BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(me.v1)))
545                                 BLI_ghash_insert(vertHash, SET_INT_IN_POINTER(me.v1),
546                                         SET_INT_IN_POINTER(BLI_ghash_size(vertHash)));
547                         if(!BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(me.v2)))
548                                 BLI_ghash_insert(vertHash, SET_INT_IN_POINTER(me.v2),
549                                         SET_INT_IN_POINTER(BLI_ghash_size(vertHash)));
550                 }
551
552                 /* get the set of edges that will be in the new mesh
553                 */
554                 for(i = 0; i < numEdges; ++i) {
555                         MEdge me;
556                         dm->getEdge(dm, edgeMap[i], &me);
557
558                         BLI_ghash_insert(edgeHash, SET_INT_IN_POINTER(BLI_ghash_size(edgeHash)),
559                                          SET_INT_IN_POINTER(edgeMap[i]));
560                 }
561         } else {
562                 int numVerts = dm->getNumVerts(dm) * frac;
563
564                 if(bmd->randomize)
565                         BLI_array_randomize(vertMap, sizeof(*vertMap),
566                                             maxVerts, bmd->seed);
567
568                 /* get the set of all vert indices that will be in the final mesh,
569                 * mapped to the new indices
570                 */
571                 for(i = 0; i < numVerts; ++i)
572                         BLI_ghash_insert(vertHash, SET_INT_IN_POINTER(vertMap[i]), SET_INT_IN_POINTER(i));
573         }
574
575         /* now we know the number of verts, edges and faces, we can create
576         * the mesh
577         */
578         result = CDDM_from_template(dm, BLI_ghash_size(vertHash),
579                                     BLI_ghash_size(edgeHash), numFaces);
580
581         /* copy the vertices across */
582         for(hashIter = BLI_ghashIterator_new(vertHash);
583                    !BLI_ghashIterator_isDone(hashIter);
584                    BLI_ghashIterator_step(hashIter)) {
585                            MVert source;
586                            MVert *dest;
587                            int oldIndex = GET_INT_FROM_POINTER(BLI_ghashIterator_getKey(hashIter));
588                            int newIndex = GET_INT_FROM_POINTER(BLI_ghashIterator_getValue(hashIter));
589
590                            dm->getVert(dm, oldIndex, &source);
591                            dest = CDDM_get_vert(result, newIndex);
592
593                            DM_copy_vert_data(dm, result, oldIndex, newIndex, 1);
594                            *dest = source;
595                    }
596                    BLI_ghashIterator_free(hashIter);
597
598                    /* copy the edges across, remapping indices */
599                    for(i = 0; i < BLI_ghash_size(edgeHash); ++i) {
600                            MEdge source;
601                            MEdge *dest;
602                            int oldIndex = GET_INT_FROM_POINTER(BLI_ghash_lookup(edgeHash, SET_INT_IN_POINTER(i)));
603
604                            dm->getEdge(dm, oldIndex, &source);
605                            dest = CDDM_get_edge(result, i);
606
607                            source.v1 = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source.v1)));
608                            source.v2 = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source.v2)));
609
610                            DM_copy_edge_data(dm, result, oldIndex, i, 1);
611                            *dest = source;
612                    }
613
614                    /* copy the faces across, remapping indices */
615                    for(i = 0; i < numFaces; ++i) {
616                            MFace source;
617                            MFace *dest;
618                            int orig_v4;
619
620                            dm->getFace(dm, faceMap[i], &source);
621                            dest = CDDM_get_face(result, i);
622
623                            orig_v4 = source.v4;
624
625                            source.v1 = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source.v1)));
626                            source.v2 = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source.v2)));
627                            source.v3 = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source.v3)));
628                            if(source.v4)
629                                    source.v4 = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source.v4)));
630
631                            DM_copy_face_data(dm, result, faceMap[i], i, 1);
632                            *dest = source;
633
634                            test_index_face(dest, &result->faceData, i, (orig_v4 ? 4 : 3));
635                    }
636
637                    CDDM_calc_normals(result);
638
639                    BLI_ghash_free(vertHash, NULL, NULL);
640                    BLI_ghash_free(edgeHash, NULL, NULL);
641
642                    MEM_freeN(vertMap);
643                    MEM_freeN(edgeMap);
644                    MEM_freeN(faceMap);
645
646                    return result;
647 }
648
649 /* Mask */
650
651 static void maskModifier_copyData(ModifierData *md, ModifierData *target)
652 {
653         MaskModifierData *mmd = (MaskModifierData*) md;
654         MaskModifierData *tmmd = (MaskModifierData*) target;
655         
656         strcpy(tmmd->vgroup, mmd->vgroup);
657 }
658
659 static CustomDataMask maskModifier_requiredDataMask(Object *ob, ModifierData *md)
660 {
661         return (1 << CD_MDEFORMVERT);
662 }
663
664 static void maskModifier_foreachObjectLink(
665                                               ModifierData *md, Object *ob,
666            void (*walk)(void *userData, Object *ob, Object **obpoin),
667                   void *userData)
668 {
669         MaskModifierData *mmd = (MaskModifierData *)md;
670         walk(userData, ob, &mmd->ob_arm);
671 }
672
673 static void maskModifier_updateDepgraph(ModifierData *md, DagForest *forest, Scene *scene,
674                                            Object *ob, DagNode *obNode)
675 {
676         MaskModifierData *mmd = (MaskModifierData *)md;
677
678         if (mmd->ob_arm) 
679         {
680                 DagNode *armNode = dag_get_node(forest, mmd->ob_arm);
681                 
682                 dag_add_relation(forest, armNode, obNode,
683                                 DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Mask Modifier");
684         }
685 }
686
687 static DerivedMesh *maskModifier_applyModifier(ModifierData *md, Object *ob,
688                 DerivedMesh *derivedData,
689   int useRenderParams, int isFinalCalc)
690 {
691         MaskModifierData *mmd= (MaskModifierData *)md;
692         DerivedMesh *dm= derivedData, *result= NULL;
693         GHash *vertHash=NULL, *edgeHash, *faceHash;
694         GHashIterator *hashIter;
695         MDeformVert *dvert= NULL;
696         int numFaces=0, numEdges=0, numVerts=0;
697         int maxVerts, maxEdges, maxFaces;
698         int i;
699         
700         /* Overview of Method:
701          *      1. Get the vertices that are in the vertexgroup of interest 
702          *      2. Filter out unwanted geometry (i.e. not in vertexgroup), by populating mappings with new vs old indices
703          *      3. Make a new mesh containing only the mapping data
704          */
705         
706         /* get original number of verts, edges, and faces */
707         maxVerts= dm->getNumVerts(dm);
708         maxEdges= dm->getNumEdges(dm);
709         maxFaces= dm->getNumFaces(dm);
710         
711         /* check if we can just return the original mesh 
712          *      - must have verts and therefore verts assigned to vgroups to do anything useful
713          */
714         if ( !(ELEM(mmd->mode, MOD_MASK_MODE_ARM, MOD_MASK_MODE_VGROUP)) ||
715                  (maxVerts == 0) || (ob->defbase.first == NULL) )
716         {
717                 return derivedData;
718         }
719         
720         /* if mode is to use selected armature bones, aggregate the bone groups */
721         if (mmd->mode == MOD_MASK_MODE_ARM) /* --- using selected bones --- */
722         {
723                 GHash *vgroupHash, *boneHash;
724                 Object *oba= mmd->ob_arm;
725                 bPoseChannel *pchan;
726                 bDeformGroup *def;
727                 
728                 /* check that there is armature object with bones to use, otherwise return original mesh */
729                 if (ELEM(NULL, mmd->ob_arm, mmd->ob_arm->pose))
730                         return derivedData;             
731                 
732                 /* hashes for finding mapping of:
733                  *      - vgroups to indicies -> vgroupHash  (string, int)
734                  *      - bones to vgroup indices -> boneHash (index of vgroup, dummy)
735                  */
736                 vgroupHash= BLI_ghash_new(BLI_ghashutil_strhash, BLI_ghashutil_strcmp);
737                 boneHash= BLI_ghash_new(BLI_ghashutil_inthash, BLI_ghashutil_intcmp);
738                 
739                 /* build mapping of names of vertex groups to indices */
740                 for (i = 0, def = ob->defbase.first; def; def = def->next, i++) 
741                         BLI_ghash_insert(vgroupHash, def->name, SET_INT_IN_POINTER(i));
742                 
743                 /* get selected-posechannel <-> vertexgroup index mapping */
744                 for (pchan= oba->pose->chanbase.first; pchan; pchan= pchan->next) 
745                 {
746                         /* check if bone is selected */
747                         // TODO: include checks for visibility too?
748                         // FIXME: the depsgraph needs extensions to make this work in realtime...
749                         if ( (pchan->bone) && (pchan->bone->flag & BONE_SELECTED) ) 
750                         {
751                                 /* check if hash has group for this bone */
752                                 if (BLI_ghash_haskey(vgroupHash, pchan->name)) 
753                                 {
754                                         int defgrp_index= GET_INT_FROM_POINTER(BLI_ghash_lookup(vgroupHash, pchan->name));
755                                         
756                                         /* add index to hash (store under key only) */
757                                         BLI_ghash_insert(boneHash, SET_INT_IN_POINTER(defgrp_index), pchan);
758                                 }
759                         }
760                 }
761                 
762                 /* if no bones selected, free hashes and return original mesh */
763                 if (BLI_ghash_size(boneHash) == 0)
764                 {
765                         BLI_ghash_free(vgroupHash, NULL, NULL);
766                         BLI_ghash_free(boneHash, NULL, NULL);
767                         
768                         return derivedData;
769                 }
770                 
771                 /* repeat the previous check, but for dverts */
772                 dvert= dm->getVertDataArray(dm, CD_MDEFORMVERT);
773                 if (dvert == NULL)
774                 {
775                         BLI_ghash_free(vgroupHash, NULL, NULL);
776                         BLI_ghash_free(boneHash, NULL, NULL);
777                         
778                         return derivedData;
779                 }
780                 
781                 /* hashes for quickly providing a mapping from old to new - use key=oldindex, value=newindex */
782                 vertHash= BLI_ghash_new(BLI_ghashutil_inthash, BLI_ghashutil_intcmp);
783                 
784                 /* add vertices which exist in vertexgroups into vertHash for filtering */
785                 for (i = 0; i < maxVerts; i++) 
786                 {
787                         MDeformWeight *def_weight = NULL;
788                         int j;
789                         
790                         for (j= 0; j < dvert[i].totweight; j++) 
791                         {
792                                 if (BLI_ghash_haskey(boneHash, SET_INT_IN_POINTER(dvert[i].dw[j].def_nr))) 
793                                 {
794                                         def_weight = &dvert[i].dw[j];
795                                         break;
796                                 }
797                         }
798                         
799                         /* check if include vert in vertHash */
800                         if (mmd->flag & MOD_MASK_INV) {
801                                 /* if this vert is in the vgroup, don't include it in vertHash */
802                                 if (def_weight) continue;
803                         }
804                         else {
805                                 /* if this vert isn't in the vgroup, don't include it in vertHash */
806                                 if (!def_weight) continue;
807                         }
808                         
809                         /* add to ghash for verts (numVerts acts as counter for mapping) */
810                         BLI_ghash_insert(vertHash, SET_INT_IN_POINTER(i), SET_INT_IN_POINTER(numVerts));
811                         numVerts++;
812                 }
813                 
814                 /* free temp hashes */
815                 BLI_ghash_free(vgroupHash, NULL, NULL);
816                 BLI_ghash_free(boneHash, NULL, NULL);
817         }
818         else            /* --- Using Nominated VertexGroup only --- */ 
819         {
820                 int defgrp_index = defgroup_name_index(ob, mmd->vgroup);
821                 
822                 /* get dverts */
823                 if (defgrp_index >= 0)
824                         dvert = dm->getVertDataArray(dm, CD_MDEFORMVERT);
825                         
826                 /* if no vgroup (i.e. dverts) found, return the initial mesh */
827                 if ((defgrp_index < 0) || (dvert == NULL))
828                         return dm;
829                         
830                 /* hashes for quickly providing a mapping from old to new - use key=oldindex, value=newindex */
831                 vertHash= BLI_ghash_new(BLI_ghashutil_inthash, BLI_ghashutil_intcmp);
832                 
833                 /* add vertices which exist in vertexgroup into ghash for filtering */
834                 for (i = 0; i < maxVerts; i++) 
835                 {
836                         MDeformWeight *def_weight = NULL;
837                         int j;
838                         
839                         for (j= 0; j < dvert[i].totweight; j++) 
840                         {
841                                 if (dvert[i].dw[j].def_nr == defgrp_index) 
842                                 {
843                                         def_weight = &dvert[i].dw[j];
844                                         break;
845                                 }
846                         }
847                         
848                         /* check if include vert in vertHash */
849                         if (mmd->flag & MOD_MASK_INV) {
850                                 /* if this vert is in the vgroup, don't include it in vertHash */
851                                 if (def_weight) continue;
852                         }
853                         else {
854                                 /* if this vert isn't in the vgroup, don't include it in vertHash */
855                                 if (!def_weight) continue;
856                         }
857                         
858                         /* add to ghash for verts (numVerts acts as counter for mapping) */
859                         BLI_ghash_insert(vertHash, SET_INT_IN_POINTER(i), SET_INT_IN_POINTER(numVerts));
860                         numVerts++;
861                 }
862         }
863         
864         /* hashes for quickly providing a mapping from old to new - use key=oldindex, value=newindex */
865         edgeHash= BLI_ghash_new(BLI_ghashutil_inthash, BLI_ghashutil_intcmp);
866         faceHash= BLI_ghash_new(BLI_ghashutil_inthash, BLI_ghashutil_intcmp);
867         
868         /* loop over edges and faces, and do the same thing to 
869          * ensure that they only reference existing verts 
870          */
871         for (i = 0; i < maxEdges; i++) 
872         {
873                 MEdge me;
874                 dm->getEdge(dm, i, &me);
875                 
876                 /* only add if both verts will be in new mesh */
877                 if ( BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(me.v1)) &&
878                          BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(me.v2)) )
879                 {
880                         BLI_ghash_insert(edgeHash, SET_INT_IN_POINTER(i), SET_INT_IN_POINTER(numEdges));
881                         numEdges++;
882                 }
883         }
884         for (i = 0; i < maxFaces; i++) 
885         {
886                 MFace mf;
887                 dm->getFace(dm, i, &mf);
888                 
889                 /* all verts must be available */
890                 if ( BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(mf.v1)) &&
891                          BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(mf.v2)) &&
892                          BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(mf.v3)) &&
893                         (mf.v4==0 || BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(mf.v4))) )
894                 {
895                         BLI_ghash_insert(faceHash, SET_INT_IN_POINTER(i), SET_INT_IN_POINTER(numFaces));
896                         numFaces++;
897                 }
898         }
899         
900         
901         /* now we know the number of verts, edges and faces, 
902          * we can create the new (reduced) mesh
903          */
904         result = CDDM_from_template(dm, numVerts, numEdges, numFaces);
905         
906         
907         /* using ghash-iterators, map data into new mesh */
908                 /* vertices */
909         for ( hashIter = BLI_ghashIterator_new(vertHash);
910                   !BLI_ghashIterator_isDone(hashIter);
911                   BLI_ghashIterator_step(hashIter) ) 
912         {
913                 MVert source;
914                 MVert *dest;
915                 int oldIndex = GET_INT_FROM_POINTER(BLI_ghashIterator_getKey(hashIter));
916                 int newIndex = GET_INT_FROM_POINTER(BLI_ghashIterator_getValue(hashIter));
917                 
918                 dm->getVert(dm, oldIndex, &source);
919                 dest = CDDM_get_vert(result, newIndex);
920                 
921                 DM_copy_vert_data(dm, result, oldIndex, newIndex, 1);
922                 *dest = source;
923         }
924         BLI_ghashIterator_free(hashIter);
925                 
926                 /* edges */
927         for ( hashIter = BLI_ghashIterator_new(edgeHash);
928                   !BLI_ghashIterator_isDone(hashIter);
929                   BLI_ghashIterator_step(hashIter) ) 
930         {
931                 MEdge source;
932                 MEdge *dest;
933                 int oldIndex = GET_INT_FROM_POINTER(BLI_ghashIterator_getKey(hashIter));
934                 int newIndex = GET_INT_FROM_POINTER(BLI_ghashIterator_getValue(hashIter));
935                 
936                 dm->getEdge(dm, oldIndex, &source);
937                 dest = CDDM_get_edge(result, newIndex);
938                 
939                 source.v1 = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source.v1)));
940                 source.v2 = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source.v2)));
941                 
942                 DM_copy_edge_data(dm, result, oldIndex, newIndex, 1);
943                 *dest = source;
944         }
945         BLI_ghashIterator_free(hashIter);
946         
947                 /* faces */
948         for ( hashIter = BLI_ghashIterator_new(faceHash);
949                   !BLI_ghashIterator_isDone(hashIter);
950                   BLI_ghashIterator_step(hashIter) ) 
951         {
952                 MFace source;
953                 MFace *dest;
954                 int oldIndex = GET_INT_FROM_POINTER(BLI_ghashIterator_getKey(hashIter));
955                 int newIndex = GET_INT_FROM_POINTER(BLI_ghashIterator_getValue(hashIter));
956                 int orig_v4;
957                 
958                 dm->getFace(dm, oldIndex, &source);
959                 dest = CDDM_get_face(result, newIndex);
960                 
961                 orig_v4 = source.v4;
962                 
963                 source.v1 = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source.v1)));
964                 source.v2 = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source.v2)));
965                 source.v3 = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source.v3)));
966                 if (source.v4)
967                    source.v4 = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source.v4)));
968                 
969                 DM_copy_face_data(dm, result, oldIndex, newIndex, 1);
970                 *dest = source;
971                 
972                 test_index_face(dest, &result->faceData, newIndex, (orig_v4 ? 4 : 3));
973         }
974         BLI_ghashIterator_free(hashIter);
975         
976         /* recalculate normals */
977         CDDM_calc_normals(result);
978         
979         /* free hashes */
980         BLI_ghash_free(vertHash, NULL, NULL);
981         BLI_ghash_free(edgeHash, NULL, NULL);
982         BLI_ghash_free(faceHash, NULL, NULL);
983         
984         /* return the new mesh */
985         return result;
986 }
987
988 /* Array */
989 /* Array modifier: duplicates the object multiple times along an axis
990 */
991
992 static void arrayModifier_initData(ModifierData *md)
993 {
994         ArrayModifierData *amd = (ArrayModifierData*) md;
995
996         /* default to 2 duplicates distributed along the x-axis by an
997         offset of 1 object-width
998         */
999         amd->start_cap = amd->end_cap = amd->curve_ob = amd->offset_ob = NULL;
1000         amd->count = 2;
1001         amd->offset[0] = amd->offset[1] = amd->offset[2] = 0;
1002         amd->scale[0] = 1;
1003         amd->scale[1] = amd->scale[2] = 0;
1004         amd->length = 0;
1005         amd->merge_dist = 0.01;
1006         amd->fit_type = MOD_ARR_FIXEDCOUNT;
1007         amd->offset_type = MOD_ARR_OFF_RELATIVE;
1008         amd->flags = 0;
1009 }
1010
1011 static void arrayModifier_copyData(ModifierData *md, ModifierData *target)
1012 {
1013         ArrayModifierData *amd = (ArrayModifierData*) md;
1014         ArrayModifierData *tamd = (ArrayModifierData*) target;
1015
1016         tamd->start_cap = amd->start_cap;
1017         tamd->end_cap = amd->end_cap;
1018         tamd->curve_ob = amd->curve_ob;
1019         tamd->offset_ob = amd->offset_ob;
1020         tamd->count = amd->count;
1021         VECCOPY(tamd->offset, amd->offset);
1022         VECCOPY(tamd->scale, amd->scale);
1023         tamd->length = amd->length;
1024         tamd->merge_dist = amd->merge_dist;
1025         tamd->fit_type = amd->fit_type;
1026         tamd->offset_type = amd->offset_type;
1027         tamd->flags = amd->flags;
1028 }
1029
1030 static void arrayModifier_foreachObjectLink(
1031                                             ModifierData *md, Object *ob,
1032          void (*walk)(void *userData, Object *ob, Object **obpoin),
1033                 void *userData)
1034 {
1035         ArrayModifierData *amd = (ArrayModifierData*) md;
1036
1037         walk(userData, ob, &amd->start_cap);
1038         walk(userData, ob, &amd->end_cap);
1039         walk(userData, ob, &amd->curve_ob);
1040         walk(userData, ob, &amd->offset_ob);
1041 }
1042
1043 static void arrayModifier_updateDepgraph(ModifierData *md, DagForest *forest, Scene *scene,
1044                                          Object *ob, DagNode *obNode)
1045 {
1046         ArrayModifierData *amd = (ArrayModifierData*) md;
1047
1048         if (amd->start_cap) {
1049                 DagNode *curNode = dag_get_node(forest, amd->start_cap);
1050
1051                 dag_add_relation(forest, curNode, obNode,
1052                                  DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Array Modifier");
1053         }
1054         if (amd->end_cap) {
1055                 DagNode *curNode = dag_get_node(forest, amd->end_cap);
1056
1057                 dag_add_relation(forest, curNode, obNode,
1058                                  DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Array Modifier");
1059         }
1060         if (amd->curve_ob) {
1061                 DagNode *curNode = dag_get_node(forest, amd->curve_ob);
1062
1063                 dag_add_relation(forest, curNode, obNode,
1064                                  DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Array Modifier");
1065         }
1066         if (amd->offset_ob) {
1067                 DagNode *curNode = dag_get_node(forest, amd->offset_ob);
1068
1069                 dag_add_relation(forest, curNode, obNode,
1070                                  DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Array Modifier");
1071         }
1072 }
1073
1074 static float vertarray_size(MVert *mvert, int numVerts, int axis)
1075 {
1076         int i;
1077         float min_co, max_co;
1078
1079         /* if there are no vertices, width is 0 */
1080         if(numVerts == 0) return 0;
1081
1082         /* find the minimum and maximum coordinates on the desired axis */
1083         min_co = max_co = mvert->co[axis];
1084         ++mvert;
1085         for(i = 1; i < numVerts; ++i, ++mvert) {
1086                 if(mvert->co[axis] < min_co) min_co = mvert->co[axis];
1087                 if(mvert->co[axis] > max_co) max_co = mvert->co[axis];
1088         }
1089
1090         return max_co - min_co;
1091 }
1092
1093 typedef struct IndexMapEntry {
1094         /* the new vert index that this old vert index maps to */
1095         int new;
1096         /* -1 if this vert isn't merged, otherwise the old vert index it
1097         * should be replaced with
1098         */
1099         int merge;
1100         /* 1 if this vert's first copy is merged with the last copy of its
1101         * merge target, otherwise 0
1102         */
1103         short merge_final;
1104 } IndexMapEntry;
1105
1106 /* indexMap - an array of IndexMap entries
1107  * oldIndex - the old index to map
1108  * copyNum - the copy number to map to (original = 0, first copy = 1, etc.)
1109  */
1110 static int calc_mapping(IndexMapEntry *indexMap, int oldIndex, int copyNum)
1111 {
1112         if(indexMap[oldIndex].merge < 0) {
1113                 /* vert wasn't merged, so use copy of this vert */
1114                 return indexMap[oldIndex].new + copyNum;
1115         } else if(indexMap[oldIndex].merge == oldIndex) {
1116                 /* vert was merged with itself */
1117                 return indexMap[oldIndex].new;
1118         } else {
1119                 /* vert was merged with another vert */
1120                 /* follow the chain of merges to the end, or until we've passed
1121                 * a number of vertices equal to the copy number
1122                 */
1123                 if(copyNum <= 0)
1124                         return indexMap[oldIndex].new;
1125                 else
1126                         return calc_mapping(indexMap, indexMap[oldIndex].merge,
1127                                             copyNum - 1);
1128         }
1129 }
1130
1131 static DerivedMesh *arrayModifier_doArray(ArrayModifierData *amd,
1132                                           Scene *scene, Object *ob, DerivedMesh *dm,
1133        int initFlags)
1134 {
1135         int i, j;
1136         /* offset matrix */
1137         float offset[4][4];
1138         float final_offset[4][4];
1139         float tmp_mat[4][4];
1140         float length = amd->length;
1141         int count = amd->count;
1142         int numVerts, numEdges, numFaces;
1143         int maxVerts, maxEdges, maxFaces;
1144         int finalVerts, finalEdges, finalFaces;
1145         DerivedMesh *result, *start_cap = NULL, *end_cap = NULL;
1146         MVert *mvert, *src_mvert;
1147         MEdge *medge;
1148         MFace *mface;
1149
1150         IndexMapEntry *indexMap;
1151
1152         EdgeHash *edges;
1153
1154         /* need to avoid infinite recursion here */
1155         if(amd->start_cap && amd->start_cap != ob)
1156                 start_cap = amd->start_cap->derivedFinal;
1157         if(amd->end_cap && amd->end_cap != ob)
1158                 end_cap = amd->end_cap->derivedFinal;
1159
1160         unit_m4(offset);
1161
1162         indexMap = MEM_callocN(sizeof(*indexMap) * dm->getNumVerts(dm),
1163                                "indexmap");
1164
1165         src_mvert = dm->getVertArray(dm);
1166
1167         maxVerts = dm->getNumVerts(dm);
1168
1169         if(amd->offset_type & MOD_ARR_OFF_CONST)
1170                 add_v3_v3v3(offset[3], offset[3], amd->offset);
1171         if(amd->offset_type & MOD_ARR_OFF_RELATIVE) {
1172                 for(j = 0; j < 3; j++)
1173                         offset[3][j] += amd->scale[j] * vertarray_size(src_mvert,
1174                                         maxVerts, j);
1175         }
1176
1177         if((amd->offset_type & MOD_ARR_OFF_OBJ) && (amd->offset_ob)) {
1178                 float obinv[4][4];
1179                 float result_mat[4][4];
1180
1181                 if(ob)
1182                         invert_m4_m4(obinv, ob->obmat);
1183                 else
1184                         unit_m4(obinv);
1185
1186                 mul_serie_m4(result_mat, offset,
1187                                  obinv, amd->offset_ob->obmat,
1188      NULL, NULL, NULL, NULL, NULL);
1189                 copy_m4_m4(offset, result_mat);
1190         }
1191
1192         if(amd->fit_type == MOD_ARR_FITCURVE && amd->curve_ob) {
1193                 Curve *cu = amd->curve_ob->data;
1194                 if(cu) {
1195                         float tmp_mat[3][3];
1196                         float scale;
1197                         
1198                         object_to_mat3(amd->curve_ob, tmp_mat);
1199                         scale = mat3_to_scale(tmp_mat);
1200                                 
1201                         if(!cu->path) {
1202                                 cu->flag |= CU_PATH; // needed for path & bevlist
1203                                 makeDispListCurveTypes(scene, amd->curve_ob, 0);
1204                         }
1205                         if(cu->path)
1206                                 length = scale*cu->path->totdist;
1207                 }
1208         }
1209
1210         /* calculate the maximum number of copies which will fit within the
1211         prescribed length */
1212         if(amd->fit_type == MOD_ARR_FITLENGTH
1213                   || amd->fit_type == MOD_ARR_FITCURVE) {
1214                 float dist = sqrt(dot_v3v3(offset[3], offset[3]));
1215
1216                 if(dist > 1e-6f)
1217                         /* this gives length = first copy start to last copy end
1218                         add a tiny offset for floating point rounding errors */
1219                         count = (length + 1e-6f) / dist;
1220                 else
1221                         /* if the offset has no translation, just make one copy */
1222                         count = 1;
1223                   }
1224
1225                   if(count < 1)
1226                           count = 1;
1227
1228         /* allocate memory for count duplicates (including original) plus
1229                   * start and end caps
1230         */
1231                   finalVerts = dm->getNumVerts(dm) * count;
1232                   finalEdges = dm->getNumEdges(dm) * count;
1233                   finalFaces = dm->getNumFaces(dm) * count;
1234                   if(start_cap) {
1235                           finalVerts += start_cap->getNumVerts(start_cap);
1236                           finalEdges += start_cap->getNumEdges(start_cap);
1237                           finalFaces += start_cap->getNumFaces(start_cap);
1238                   }
1239                   if(end_cap) {
1240                           finalVerts += end_cap->getNumVerts(end_cap);
1241                           finalEdges += end_cap->getNumEdges(end_cap);
1242                           finalFaces += end_cap->getNumFaces(end_cap);
1243                   }
1244                   result = CDDM_from_template(dm, finalVerts, finalEdges, finalFaces);
1245
1246                   /* calculate the offset matrix of the final copy (for merging) */ 
1247                   unit_m4(final_offset);
1248
1249                   for(j=0; j < count - 1; j++) {
1250                           mul_m4_m4m4(tmp_mat, final_offset, offset);
1251                           copy_m4_m4(final_offset, tmp_mat);
1252                   }
1253
1254                   numVerts = numEdges = numFaces = 0;
1255                   mvert = CDDM_get_verts(result);
1256
1257                   for (i = 0; i < maxVerts; i++) {
1258                           indexMap[i].merge = -1; /* default to no merge */
1259                           indexMap[i].merge_final = 0; /* default to no merge */
1260                   }
1261
1262                   for (i = 0; i < maxVerts; i++) {
1263                           MVert *inMV;
1264                           MVert *mv = &mvert[numVerts];
1265                           MVert *mv2;
1266                           float co[3];
1267
1268                           inMV = &src_mvert[i];
1269
1270                           DM_copy_vert_data(dm, result, i, numVerts, 1);
1271                           *mv = *inMV;
1272                           numVerts++;
1273
1274                           indexMap[i].new = numVerts - 1;
1275
1276                           VECCOPY(co, mv->co);
1277                 
1278                 /* Attempts to merge verts from one duplicate with verts from the
1279                           * next duplicate which are closer than amd->merge_dist.
1280                           * Only the first such vert pair is merged.
1281                           * If verts are merged in the first duplicate pair, they are merged
1282                           * in all pairs.
1283                 */
1284                           if((count > 1) && (amd->flags & MOD_ARR_MERGE)) {
1285                                   float tmp_co[3];
1286                                   VECCOPY(tmp_co, mv->co);
1287                                   mul_m4_v3(offset, tmp_co);
1288
1289                                   for(j = 0; j < maxVerts; j++) {
1290                                           /* if vertex already merged, don't use it */
1291                                           if( indexMap[j].merge != -1 ) continue;
1292
1293                                           inMV = &src_mvert[j];
1294                                           /* if this vert is within merge limit, merge */
1295                                           if(compare_len_v3v3(tmp_co, inMV->co, amd->merge_dist)) {
1296                                                   indexMap[i].merge = j;
1297
1298                                                   /* test for merging with final copy of merge target */
1299                                                   if(amd->flags & MOD_ARR_MERGEFINAL) {
1300                                                           VECCOPY(tmp_co, inMV->co);
1301                                                           inMV = &src_mvert[i];
1302                                                           mul_m4_v3(final_offset, tmp_co);
1303                                                           if(compare_len_v3v3(tmp_co, inMV->co, amd->merge_dist))
1304                                                                   indexMap[i].merge_final = 1;
1305                                                   }
1306                                                   break;
1307                                           }
1308                                   }
1309                           }
1310
1311                           /* if no merging, generate copies of this vert */
1312                           if(indexMap[i].merge < 0) {
1313                                   for(j=0; j < count - 1; j++) {
1314                                           mv2 = &mvert[numVerts];
1315
1316                                           DM_copy_vert_data(result, result, numVerts - 1, numVerts, 1);
1317                                           *mv2 = *mv;
1318                                           numVerts++;
1319
1320                                           mul_m4_v3(offset, co);
1321                                           VECCOPY(mv2->co, co);
1322                                   }
1323                           } else if(indexMap[i].merge != i && indexMap[i].merge_final) {
1324                         /* if this vert is not merging with itself, and it is merging
1325                                   * with the final copy of its merge target, remove the first copy
1326                         */
1327                                   numVerts--;
1328                                   DM_free_vert_data(result, numVerts, 1);
1329                           }
1330                   }
1331
1332                   /* make a hashtable so we can avoid duplicate edges from merging */
1333                   edges = BLI_edgehash_new();
1334
1335                   maxEdges = dm->getNumEdges(dm);
1336                   medge = CDDM_get_edges(result);
1337                   for(i = 0; i < maxEdges; i++) {
1338                           MEdge inMED;
1339                           MEdge med;
1340                           MEdge *med2;
1341                           int vert1, vert2;
1342
1343                           dm->getEdge(dm, i, &inMED);
1344
1345                           med = inMED;
1346                           med.v1 = indexMap[inMED.v1].new;
1347                           med.v2 = indexMap[inMED.v2].new;
1348
1349                 /* if vertices are to be merged with the final copies of their
1350                           * merge targets, calculate that final copy
1351                 */
1352                           if(indexMap[inMED.v1].merge_final) {
1353                                   med.v1 = calc_mapping(indexMap, indexMap[inMED.v1].merge,
1354                                                   count - 1);
1355                           }
1356                           if(indexMap[inMED.v2].merge_final) {
1357                                   med.v2 = calc_mapping(indexMap, indexMap[inMED.v2].merge,
1358                                                   count - 1);
1359                           }
1360
1361                           if(med.v1 == med.v2) continue;
1362
1363                           if (initFlags) {
1364                                   med.flag |= ME_EDGEDRAW | ME_EDGERENDER;
1365                           }
1366
1367                           if(!BLI_edgehash_haskey(edges, med.v1, med.v2)) {
1368                                   DM_copy_edge_data(dm, result, i, numEdges, 1);
1369                                   medge[numEdges] = med;
1370                                   numEdges++;
1371
1372                                   BLI_edgehash_insert(edges, med.v1, med.v2, NULL);
1373                           }
1374
1375                           for(j = 1; j < count; j++)
1376                           {
1377                                   vert1 = calc_mapping(indexMap, inMED.v1, j);
1378                                   vert2 = calc_mapping(indexMap, inMED.v2, j);
1379                                   /* avoid duplicate edges */
1380                                   if(!BLI_edgehash_haskey(edges, vert1, vert2)) {
1381                                           med2 = &medge[numEdges];
1382
1383                                           DM_copy_edge_data(dm, result, i, numEdges, 1);
1384                                           *med2 = med;
1385                                           numEdges++;
1386
1387                                           med2->v1 = vert1;
1388                                           med2->v2 = vert2;
1389
1390                                           BLI_edgehash_insert(edges, med2->v1, med2->v2, NULL);
1391                                   }
1392                           }
1393                   }
1394
1395                   maxFaces = dm->getNumFaces(dm);
1396                   mface = CDDM_get_faces(result);
1397                   for (i=0; i < maxFaces; i++) {
1398                           MFace inMF;
1399                           MFace *mf = &mface[numFaces];
1400
1401                           dm->getFace(dm, i, &inMF);
1402
1403                           DM_copy_face_data(dm, result, i, numFaces, 1);
1404                           *mf = inMF;
1405
1406                           mf->v1 = indexMap[inMF.v1].new;
1407                           mf->v2 = indexMap[inMF.v2].new;
1408                           mf->v3 = indexMap[inMF.v3].new;
1409                           if(inMF.v4)
1410                                   mf->v4 = indexMap[inMF.v4].new;
1411
1412                 /* if vertices are to be merged with the final copies of their
1413                           * merge targets, calculate that final copy
1414                 */
1415                           if(indexMap[inMF.v1].merge_final)
1416                                   mf->v1 = calc_mapping(indexMap, indexMap[inMF.v1].merge, count-1);
1417                           if(indexMap[inMF.v2].merge_final)
1418                                   mf->v2 = calc_mapping(indexMap, indexMap[inMF.v2].merge, count-1);
1419                           if(indexMap[inMF.v3].merge_final)
1420                                   mf->v3 = calc_mapping(indexMap, indexMap[inMF.v3].merge, count-1);
1421                           if(inMF.v4 && indexMap[inMF.v4].merge_final)
1422                                   mf->v4 = calc_mapping(indexMap, indexMap[inMF.v4].merge, count-1);
1423
1424                           if(test_index_face(mf, &result->faceData, numFaces, inMF.v4?4:3) < 3)
1425                                   continue;
1426
1427                           numFaces++;
1428
1429                           /* if the face has fewer than 3 vertices, don't create it */
1430                           if(mf->v3 == 0 || (mf->v1 && (mf->v1 == mf->v3 || mf->v1 == mf->v4))) {
1431                                   numFaces--;
1432                                   DM_free_face_data(result, numFaces, 1);
1433                           }
1434
1435                           for(j = 1; j < count; j++)
1436                           {
1437                                   MFace *mf2 = &mface[numFaces];
1438
1439                                   DM_copy_face_data(dm, result, i, numFaces, 1);
1440                                   *mf2 = *mf;
1441
1442                                   mf2->v1 = calc_mapping(indexMap, inMF.v1, j);
1443                                   mf2->v2 = calc_mapping(indexMap, inMF.v2, j);
1444                                   mf2->v3 = calc_mapping(indexMap, inMF.v3, j);
1445                                   if (inMF.v4)
1446                                           mf2->v4 = calc_mapping(indexMap, inMF.v4, j);
1447
1448                                   test_index_face(mf2, &result->faceData, numFaces, inMF.v4?4:3);
1449                                   numFaces++;
1450
1451                                   /* if the face has fewer than 3 vertices, don't create it */
1452                                   if(mf2->v3 == 0 || (mf2->v1 && (mf2->v1 == mf2->v3 || mf2->v1 ==
1453                                                                  mf2->v4))) {
1454                                           numFaces--;
1455                                           DM_free_face_data(result, numFaces, 1);
1456                                                                  }
1457                           }
1458                   }
1459
1460                   /* add start and end caps */
1461                   if(start_cap) {
1462                           float startoffset[4][4];
1463                           MVert *cap_mvert;
1464                           MEdge *cap_medge;
1465                           MFace *cap_mface;
1466                           int *origindex;
1467                           int *vert_map;
1468                           int capVerts, capEdges, capFaces;
1469
1470                           capVerts = start_cap->getNumVerts(start_cap);
1471                           capEdges = start_cap->getNumEdges(start_cap);
1472                           capFaces = start_cap->getNumFaces(start_cap);
1473                           cap_mvert = start_cap->getVertArray(start_cap);
1474                           cap_medge = start_cap->getEdgeArray(start_cap);
1475                           cap_mface = start_cap->getFaceArray(start_cap);
1476
1477                           invert_m4_m4(startoffset, offset);
1478
1479                           vert_map = MEM_callocN(sizeof(*vert_map) * capVerts,
1480                                           "arrayModifier_doArray vert_map");
1481
1482                           origindex = result->getVertDataArray(result, CD_ORIGINDEX);
1483                           for(i = 0; i < capVerts; i++) {
1484                                   MVert *mv = &cap_mvert[i];
1485                                   short merged = 0;
1486
1487                                   if(amd->flags & MOD_ARR_MERGE) {
1488                                           float tmp_co[3];
1489                                           MVert *in_mv;
1490                                           int j;
1491
1492                                           VECCOPY(tmp_co, mv->co);
1493                                           mul_m4_v3(startoffset, tmp_co);
1494
1495                                           for(j = 0; j < maxVerts; j++) {
1496                                                   in_mv = &src_mvert[j];
1497                                                   /* if this vert is within merge limit, merge */
1498                                                   if(compare_len_v3v3(tmp_co, in_mv->co, amd->merge_dist)) {
1499                                                           vert_map[i] = calc_mapping(indexMap, j, 0);
1500                                                           merged = 1;
1501                                                           break;
1502                                                   }
1503                                           }
1504                                   }
1505
1506                                   if(!merged) {
1507                                           DM_copy_vert_data(start_cap, result, i, numVerts, 1);
1508                                           mvert[numVerts] = *mv;
1509                                           mul_m4_v3(startoffset, mvert[numVerts].co);
1510                                           origindex[numVerts] = ORIGINDEX_NONE;
1511
1512                                           vert_map[i] = numVerts;
1513
1514                                           numVerts++;
1515                                   }
1516                           }
1517                           origindex = result->getEdgeDataArray(result, CD_ORIGINDEX);
1518                           for(i = 0; i < capEdges; i++) {
1519                                   int v1, v2;
1520
1521                                   v1 = vert_map[cap_medge[i].v1];
1522                                   v2 = vert_map[cap_medge[i].v2];
1523
1524                                   if(!BLI_edgehash_haskey(edges, v1, v2)) {
1525                                           DM_copy_edge_data(start_cap, result, i, numEdges, 1);
1526                                           medge[numEdges] = cap_medge[i];
1527                                           medge[numEdges].v1 = v1;
1528                                           medge[numEdges].v2 = v2;
1529                                           origindex[numEdges] = ORIGINDEX_NONE;
1530
1531                                           numEdges++;
1532                                   }
1533                           }
1534                           origindex = result->getFaceDataArray(result, CD_ORIGINDEX);
1535                           for(i = 0; i < capFaces; i++) {
1536                                   DM_copy_face_data(start_cap, result, i, numFaces, 1);
1537                                   mface[numFaces] = cap_mface[i];
1538                                   mface[numFaces].v1 = vert_map[mface[numFaces].v1];
1539                                   mface[numFaces].v2 = vert_map[mface[numFaces].v2];
1540                                   mface[numFaces].v3 = vert_map[mface[numFaces].v3];
1541                                   if(mface[numFaces].v4) {
1542                                           mface[numFaces].v4 = vert_map[mface[numFaces].v4];
1543
1544                                           test_index_face(&mface[numFaces], &result->faceData,
1545                                                           numFaces, 4);
1546                                   }
1547                                   else
1548                                   {
1549                                           test_index_face(&mface[numFaces], &result->faceData,
1550                                                           numFaces, 3);
1551                                   }
1552
1553                                   origindex[numFaces] = ORIGINDEX_NONE;
1554
1555                                   numFaces++;
1556                           }
1557
1558                           MEM_freeN(vert_map);
1559                           start_cap->release(start_cap);
1560                   }
1561
1562                   if(end_cap) {
1563                           float endoffset[4][4];
1564                           MVert *cap_mvert;
1565                           MEdge *cap_medge;
1566                           MFace *cap_mface;
1567                           int *origindex;
1568                           int *vert_map;
1569                           int capVerts, capEdges, capFaces;
1570
1571                           capVerts = end_cap->getNumVerts(end_cap);
1572                           capEdges = end_cap->getNumEdges(end_cap);
1573                           capFaces = end_cap->getNumFaces(end_cap);
1574                           cap_mvert = end_cap->getVertArray(end_cap);
1575                           cap_medge = end_cap->getEdgeArray(end_cap);
1576                           cap_mface = end_cap->getFaceArray(end_cap);
1577
1578                           mul_m4_m4m4(endoffset, final_offset, offset);
1579
1580                           vert_map = MEM_callocN(sizeof(*vert_map) * capVerts,
1581                                           "arrayModifier_doArray vert_map");
1582
1583                           origindex = result->getVertDataArray(result, CD_ORIGINDEX);
1584                           for(i = 0; i < capVerts; i++) {
1585                                   MVert *mv = &cap_mvert[i];
1586                                   short merged = 0;
1587
1588                                   if(amd->flags & MOD_ARR_MERGE) {
1589                                           float tmp_co[3];
1590                                           MVert *in_mv;
1591                                           int j;
1592
1593                                           VECCOPY(tmp_co, mv->co);
1594                                           mul_m4_v3(offset, tmp_co);
1595
1596                                           for(j = 0; j < maxVerts; j++) {
1597                                                   in_mv = &src_mvert[j];
1598                                                   /* if this vert is within merge limit, merge */
1599                                                   if(compare_len_v3v3(tmp_co, in_mv->co, amd->merge_dist)) {
1600                                                           vert_map[i] = calc_mapping(indexMap, j, count - 1);
1601                                                           merged = 1;
1602                                                           break;
1603                                                   }
1604                                           }
1605                                   }
1606
1607                                   if(!merged) {
1608                                           DM_copy_vert_data(end_cap, result, i, numVerts, 1);
1609                                           mvert[numVerts] = *mv;
1610                                           mul_m4_v3(endoffset, mvert[numVerts].co);
1611                                           origindex[numVerts] = ORIGINDEX_NONE;
1612
1613                                           vert_map[i] = numVerts;
1614
1615                                           numVerts++;
1616                                   }
1617                           }
1618                           origindex = result->getEdgeDataArray(result, CD_ORIGINDEX);
1619                           for(i = 0; i < capEdges; i++) {
1620                                   int v1, v2;
1621
1622                                   v1 = vert_map[cap_medge[i].v1];
1623                                   v2 = vert_map[cap_medge[i].v2];
1624
1625                                   if(!BLI_edgehash_haskey(edges, v1, v2)) {
1626                                           DM_copy_edge_data(end_cap, result, i, numEdges, 1);
1627                                           medge[numEdges] = cap_medge[i];
1628                                           medge[numEdges].v1 = v1;
1629                                           medge[numEdges].v2 = v2;
1630                                           origindex[numEdges] = ORIGINDEX_NONE;
1631
1632                                           numEdges++;
1633                                   }
1634                           }
1635                           origindex = result->getFaceDataArray(result, CD_ORIGINDEX);
1636                           for(i = 0; i < capFaces; i++) {
1637                                   DM_copy_face_data(end_cap, result, i, numFaces, 1);
1638                                   mface[numFaces] = cap_mface[i];
1639                                   mface[numFaces].v1 = vert_map[mface[numFaces].v1];
1640                                   mface[numFaces].v2 = vert_map[mface[numFaces].v2];
1641                                   mface[numFaces].v3 = vert_map[mface[numFaces].v3];
1642                                   if(mface[numFaces].v4) {
1643                                           mface[numFaces].v4 = vert_map[mface[numFaces].v4];
1644
1645                                           test_index_face(&mface[numFaces], &result->faceData,
1646                                                           numFaces, 4);
1647                                   }
1648                                   else
1649                                   {
1650                                           test_index_face(&mface[numFaces], &result->faceData,
1651                                                           numFaces, 3);
1652                                   }
1653                                   origindex[numFaces] = ORIGINDEX_NONE;
1654
1655                                   numFaces++;
1656                           }
1657
1658                           MEM_freeN(vert_map);
1659                           end_cap->release(end_cap);
1660                   }
1661
1662                   BLI_edgehash_free(edges, NULL);
1663                   MEM_freeN(indexMap);
1664
1665                   CDDM_lower_num_verts(result, numVerts);
1666                   CDDM_lower_num_edges(result, numEdges);
1667                   CDDM_lower_num_faces(result, numFaces);
1668
1669                   return result;
1670 }
1671
1672 static DerivedMesh *arrayModifier_applyModifier(
1673                 ModifierData *md, Object *ob, DerivedMesh *derivedData,
1674   int useRenderParams, int isFinalCalc)
1675 {
1676         DerivedMesh *result;
1677         ArrayModifierData *amd = (ArrayModifierData*) md;
1678
1679         result = arrayModifier_doArray(amd, md->scene, ob, derivedData, 0);
1680
1681         if(result != derivedData)
1682                 CDDM_calc_normals(result);
1683
1684         return result;
1685 }
1686
1687 static DerivedMesh *arrayModifier_applyModifierEM(
1688                 ModifierData *md, Object *ob, EditMesh *editData,
1689   DerivedMesh *derivedData)
1690 {
1691         return arrayModifier_applyModifier(md, ob, derivedData, 0, 1);
1692 }
1693
1694 /* Mirror */
1695
1696 static void mirrorModifier_initData(ModifierData *md)
1697 {
1698         MirrorModifierData *mmd = (MirrorModifierData*) md;
1699
1700         mmd->flag |= (MOD_MIR_AXIS_X | MOD_MIR_VGROUP);
1701         mmd->tolerance = 0.001;
1702         mmd->mirror_ob = NULL;
1703 }
1704
1705 static void mirrorModifier_copyData(ModifierData *md, ModifierData *target)
1706 {
1707         MirrorModifierData *mmd = (MirrorModifierData*) md;
1708         MirrorModifierData *tmmd = (MirrorModifierData*) target;
1709
1710         tmmd->axis = mmd->axis;
1711         tmmd->flag = mmd->flag;
1712         tmmd->tolerance = mmd->tolerance;
1713         tmmd->mirror_ob = mmd->mirror_ob;;
1714 }
1715
1716 static void mirrorModifier_foreachObjectLink(
1717                                              ModifierData *md, Object *ob,
1718           void (*walk)(void *userData, Object *ob, Object **obpoin),
1719                  void *userData)
1720 {
1721         MirrorModifierData *mmd = (MirrorModifierData*) md;
1722
1723         walk(userData, ob, &mmd->mirror_ob);
1724 }
1725
1726 static void mirrorModifier_updateDepgraph(ModifierData *md, DagForest *forest, Scene *scene,
1727                                           Object *ob, DagNode *obNode)
1728 {
1729         MirrorModifierData *mmd = (MirrorModifierData*) md;
1730
1731         if(mmd->mirror_ob) {
1732                 DagNode *latNode = dag_get_node(forest, mmd->mirror_ob);
1733
1734                 dag_add_relation(forest, latNode, obNode,
1735                                  DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Mirror Modifier");
1736         }
1737 }
1738
1739 static DerivedMesh *doMirrorOnAxis(MirrorModifierData *mmd,
1740                 Object *ob,
1741                 DerivedMesh *dm,
1742                 int initFlags,
1743                 int axis)
1744 {
1745         int i;
1746         float tolerance = mmd->tolerance;
1747         DerivedMesh *result;
1748         int numVerts, numEdges, numFaces;
1749         int maxVerts = dm->getNumVerts(dm);
1750         int maxEdges = dm->getNumEdges(dm);
1751         int maxFaces = dm->getNumFaces(dm);
1752         int *flip_map= NULL;
1753         int do_vgroup_mirr= (mmd->flag & MOD_MIR_VGROUP);
1754         int (*indexMap)[2];
1755         float mtx[4][4], imtx[4][4];
1756
1757         numVerts = numEdges = numFaces = 0;
1758
1759         indexMap = MEM_mallocN(sizeof(*indexMap) * maxVerts, "indexmap");
1760
1761         result = CDDM_from_template(dm, maxVerts * 2, maxEdges * 2, maxFaces * 2);
1762
1763
1764         if (do_vgroup_mirr) {
1765                 flip_map= defgroup_flip_map(ob, 0);
1766                 if(flip_map == NULL)
1767                         do_vgroup_mirr= 0;
1768         }
1769
1770         if (mmd->mirror_ob) {
1771                 float obinv[4][4];
1772                 
1773                 invert_m4_m4(obinv, mmd->mirror_ob->obmat);
1774                 mul_m4_m4m4(mtx, ob->obmat, obinv);
1775                 invert_m4_m4(imtx, mtx);
1776         }
1777
1778         for(i = 0; i < maxVerts; i++) {
1779                 MVert inMV;
1780                 MVert *mv = CDDM_get_vert(result, numVerts);
1781                 int isShared;
1782                 float co[3];
1783                 
1784                 dm->getVert(dm, i, &inMV);
1785                 
1786                 copy_v3_v3(co, inMV.co);
1787                 
1788                 if (mmd->mirror_ob) {
1789                         mul_v3_m4v3(co, mtx, co);
1790                 }
1791                 isShared = ABS(co[axis])<=tolerance;
1792                 
1793                 /* Because the topology result (# of vertices) must be the same if
1794                 * the mesh data is overridden by vertex cos, have to calc sharedness
1795                 * based on original coordinates. This is why we test before copy.
1796                 */
1797                 DM_copy_vert_data(dm, result, i, numVerts, 1);
1798                 *mv = inMV;
1799                 numVerts++;
1800                 
1801                 indexMap[i][0] = numVerts - 1;
1802                 indexMap[i][1] = !isShared;
1803                 
1804                 if(isShared) {
1805                         co[axis] = 0;
1806                         if (mmd->mirror_ob) {
1807                                 mul_v3_m4v3(co, imtx, co);
1808                         }
1809                         copy_v3_v3(mv->co, co);
1810                         
1811                         mv->flag |= ME_VERT_MERGED;
1812                 } else {
1813                         MVert *mv2 = CDDM_get_vert(result, numVerts);
1814                         
1815                         DM_copy_vert_data(dm, result, i, numVerts, 1);
1816                         *mv2 = *mv;
1817                         
1818                         co[axis] = -co[axis];
1819                         if (mmd->mirror_ob) {
1820                                 mul_v3_m4v3(co, imtx, co);
1821                         }
1822                         copy_v3_v3(mv2->co, co);
1823                         
1824                         if (do_vgroup_mirr) {
1825                                 MDeformVert *dvert= DM_get_vert_data(result, numVerts, CD_MDEFORMVERT);
1826                                 if(dvert) {
1827                                         defvert_flip(dvert, flip_map);
1828                                 }
1829                         }
1830
1831                         numVerts++;
1832                 }
1833         }
1834
1835         for(i = 0; i < maxEdges; i++) {
1836                 MEdge inMED;
1837                 MEdge *med = CDDM_get_edge(result, numEdges);
1838                 
1839                 dm->getEdge(dm, i, &inMED);
1840                 
1841                 DM_copy_edge_data(dm, result, i, numEdges, 1);
1842                 *med = inMED;
1843                 numEdges++;
1844                 
1845                 med->v1 = indexMap[inMED.v1][0];
1846                 med->v2 = indexMap[inMED.v2][0];
1847                 if(initFlags)
1848                         med->flag |= ME_EDGEDRAW | ME_EDGERENDER;
1849                 
1850                 if(indexMap[inMED.v1][1] || indexMap[inMED.v2][1]) {
1851                         MEdge *med2 = CDDM_get_edge(result, numEdges);
1852                         
1853                         DM_copy_edge_data(dm, result, i, numEdges, 1);
1854                         *med2 = *med;
1855                         numEdges++;
1856                         
1857                         med2->v1 += indexMap[inMED.v1][1];
1858                         med2->v2 += indexMap[inMED.v2][1];
1859                 }
1860         }
1861
1862         for(i = 0; i < maxFaces; i++) {
1863                 MFace inMF;
1864                 MFace *mf = CDDM_get_face(result, numFaces);
1865                 
1866                 dm->getFace(dm, i, &inMF);
1867                 
1868                 DM_copy_face_data(dm, result, i, numFaces, 1);
1869                 *mf = inMF;
1870                 numFaces++;
1871                 
1872                 mf->v1 = indexMap[inMF.v1][0];
1873                 mf->v2 = indexMap[inMF.v2][0];
1874                 mf->v3 = indexMap[inMF.v3][0];
1875                 mf->v4 = indexMap[inMF.v4][0];
1876                 
1877                 if(indexMap[inMF.v1][1]
1878                                  || indexMap[inMF.v2][1]
1879                                  || indexMap[inMF.v3][1]
1880                                  || (mf->v4 && indexMap[inMF.v4][1])) {
1881                         MFace *mf2 = CDDM_get_face(result, numFaces);
1882                         static int corner_indices[4] = {2, 1, 0, 3};
1883                         
1884                         DM_copy_face_data(dm, result, i, numFaces, 1);
1885                         *mf2 = *mf;
1886                         
1887                         mf2->v1 += indexMap[inMF.v1][1];
1888                         mf2->v2 += indexMap[inMF.v2][1];
1889                         mf2->v3 += indexMap[inMF.v3][1];
1890                         if(inMF.v4) mf2->v4 += indexMap[inMF.v4][1];
1891                         
1892                         /* mirror UVs if enabled */
1893                         if(mmd->flag & (MOD_MIR_MIRROR_U | MOD_MIR_MIRROR_V)) {
1894                                 MTFace *tf = result->getFaceData(result, numFaces, CD_MTFACE);
1895                                 if(tf) {
1896                                         int j;
1897                                         for(j = 0; j < 4; ++j) {
1898                                                 if(mmd->flag & MOD_MIR_MIRROR_U)
1899                                                         tf->uv[j][0] = 1.0f - tf->uv[j][0];
1900                                                 if(mmd->flag & MOD_MIR_MIRROR_V)
1901                                                         tf->uv[j][1] = 1.0f - tf->uv[j][1];
1902                                         }
1903                                 }
1904                         }
1905                         
1906                         /* Flip face normal */
1907                         SWAP(int, mf2->v1, mf2->v3);
1908                         DM_swap_face_data(result, numFaces, corner_indices);
1909                         
1910                         test_index_face(mf2, &result->faceData, numFaces, inMF.v4?4:3);
1911                         numFaces++;
1912                 }
1913         }
1914
1915         if (flip_map) MEM_freeN(flip_map);
1916
1917         MEM_freeN(indexMap);
1918
1919         CDDM_lower_num_verts(result, numVerts);
1920         CDDM_lower_num_edges(result, numEdges);
1921         CDDM_lower_num_faces(result, numFaces);
1922
1923         return result;
1924 }
1925
1926 static DerivedMesh *mirrorModifier__doMirror(MirrorModifierData *mmd,
1927                                             Object *ob, DerivedMesh *dm,
1928                                                 int initFlags)
1929 {
1930         DerivedMesh *result = dm;
1931
1932         /* check which axes have been toggled and mirror accordingly */
1933         if(mmd->flag & MOD_MIR_AXIS_X) {
1934                 result = doMirrorOnAxis(mmd, ob, result, initFlags, 0);
1935         }
1936         if(mmd->flag & MOD_MIR_AXIS_Y) {
1937                 DerivedMesh *tmp = result;
1938                 result = doMirrorOnAxis(mmd, ob, result, initFlags, 1);
1939                 if(tmp != dm) tmp->release(tmp); /* free intermediate results */
1940         }
1941         if(mmd->flag & MOD_MIR_AXIS_Z) {
1942                 DerivedMesh *tmp = result;
1943                 result = doMirrorOnAxis(mmd, ob, result, initFlags, 2);
1944                 if(tmp != dm) tmp->release(tmp); /* free intermediate results */
1945         }
1946
1947         return result;
1948 }
1949
1950 static DerivedMesh *mirrorModifier_applyModifier(
1951                 ModifierData *md, Object *ob, DerivedMesh *derivedData,
1952   int useRenderParams, int isFinalCalc)
1953 {
1954         DerivedMesh *result;
1955         MirrorModifierData *mmd = (MirrorModifierData*) md;
1956
1957         result = mirrorModifier__doMirror(mmd, ob, derivedData, 0);
1958
1959         if(result != derivedData)
1960                 CDDM_calc_normals(result);
1961         
1962         return result;
1963 }
1964
1965 static DerivedMesh *mirrorModifier_applyModifierEM(
1966                 ModifierData *md, Object *ob, EditMesh *editData,
1967   DerivedMesh *derivedData)
1968 {
1969         return mirrorModifier_applyModifier(md, ob, derivedData, 0, 1);
1970 }
1971
1972 /* EdgeSplit */
1973 /* EdgeSplit modifier: Splits edges in the mesh according to sharpness flag
1974  * or edge angle (can be used to achieve autosmoothing)
1975 */
1976 #if 0
1977 #define EDGESPLIT_DEBUG_3
1978 #define EDGESPLIT_DEBUG_2
1979 #define EDGESPLIT_DEBUG_1
1980 #define EDGESPLIT_DEBUG_0
1981 #endif
1982
1983 static void edgesplitModifier_initData(ModifierData *md)
1984 {
1985         EdgeSplitModifierData *emd = (EdgeSplitModifierData*) md;
1986
1987         /* default to 30-degree split angle, sharpness from both angle & flag
1988         */
1989         emd->split_angle = 30;
1990         emd->flags = MOD_EDGESPLIT_FROMANGLE | MOD_EDGESPLIT_FROMFLAG;
1991 }
1992
1993 static void edgesplitModifier_copyData(ModifierData *md, ModifierData *target)
1994 {
1995         EdgeSplitModifierData *emd = (EdgeSplitModifierData*) md;
1996         EdgeSplitModifierData *temd = (EdgeSplitModifierData*) target;
1997
1998         temd->split_angle = emd->split_angle;
1999         temd->flags = emd->flags;
2000 }
2001
2002 /* Mesh data for edgesplit operation */
2003 typedef struct SmoothVert {
2004         LinkNode *faces;     /* all faces which use this vert */
2005         int oldIndex; /* the index of the original DerivedMesh vert */
2006         int newIndex; /* the index of the new DerivedMesh vert */
2007 } SmoothVert;
2008
2009 #define SMOOTHEDGE_NUM_VERTS 2
2010
2011 typedef struct SmoothEdge {
2012         SmoothVert *verts[SMOOTHEDGE_NUM_VERTS]; /* the verts used by this edge */
2013         LinkNode *faces;     /* all faces which use this edge */
2014         int oldIndex; /* the index of the original DerivedMesh edge */
2015         int newIndex; /* the index of the new DerivedMesh edge */
2016         short flag; /* the flags from the original DerivedMesh edge */
2017 } SmoothEdge;
2018
2019 #define SMOOTHFACE_MAX_EDGES 4
2020
2021 typedef struct SmoothFace {
2022         SmoothEdge *edges[SMOOTHFACE_MAX_EDGES]; /* nonexistent edges == NULL */
2023         int flip[SMOOTHFACE_MAX_EDGES]; /* 1 = flip edge dir, 0 = don't flip */
2024         float normal[3]; /* the normal of this face */
2025         int oldIndex; /* the index of the original DerivedMesh face */
2026         int newIndex; /* the index of the new DerivedMesh face */
2027 } SmoothFace;
2028
2029 typedef struct SmoothMesh {
2030         SmoothVert *verts;
2031         SmoothEdge *edges;
2032         SmoothFace *faces;
2033         int num_verts, num_edges, num_faces;
2034         int max_verts, max_edges, max_faces;
2035         DerivedMesh *dm;
2036         float threshold; /* the cosine of the smoothing angle */
2037         int flags;
2038         MemArena *arena;
2039         ListBase propagatestack, reusestack;
2040 } SmoothMesh;
2041
2042 static SmoothVert *smoothvert_copy(SmoothVert *vert, SmoothMesh *mesh)
2043 {
2044         SmoothVert *copy = &mesh->verts[mesh->num_verts];
2045
2046         if(mesh->num_verts >= mesh->max_verts) {
2047                 printf("Attempted to add a SmoothMesh vert beyond end of array\n");
2048                 return NULL;
2049         }
2050
2051         *copy = *vert;
2052         copy->faces = NULL;
2053         copy->newIndex = mesh->num_verts;
2054         ++mesh->num_verts;
2055
2056 #ifdef EDGESPLIT_DEBUG_2
2057         printf("copied vert %4d to vert %4d\n", vert->newIndex, copy->newIndex);
2058 #endif
2059         return copy;
2060 }
2061
2062 static SmoothEdge *smoothedge_copy(SmoothEdge *edge, SmoothMesh *mesh)
2063 {
2064         SmoothEdge *copy = &mesh->edges[mesh->num_edges];
2065
2066         if(mesh->num_edges >= mesh->max_edges) {
2067                 printf("Attempted to add a SmoothMesh edge beyond end of array\n");
2068                 return NULL;
2069         }
2070
2071         *copy = *edge;
2072         copy->faces = NULL;
2073         copy->newIndex = mesh->num_edges;
2074         ++mesh->num_edges;
2075
2076 #ifdef EDGESPLIT_DEBUG_2
2077         printf("copied edge %4d to edge %4d\n", edge->newIndex, copy->newIndex);
2078 #endif
2079         return copy;
2080 }
2081
2082 static int smoothedge_has_vert(SmoothEdge *edge, SmoothVert *vert)
2083 {
2084         int i;
2085         for(i = 0; i < SMOOTHEDGE_NUM_VERTS; i++)
2086                 if(edge->verts[i] == vert) return 1;
2087
2088         return 0;
2089 }
2090
2091 static SmoothMesh *smoothmesh_new(int num_verts, int num_edges, int num_faces,
2092                                   int max_verts, int max_edges, int max_faces)
2093 {
2094         SmoothMesh *mesh = MEM_callocN(sizeof(*mesh), "smoothmesh");
2095         mesh->verts = MEM_callocN(sizeof(*mesh->verts) * max_verts,
2096                                   "SmoothMesh.verts");
2097         mesh->edges = MEM_callocN(sizeof(*mesh->edges) * max_edges,
2098                                   "SmoothMesh.edges");
2099         mesh->faces = MEM_callocN(sizeof(*mesh->faces) * max_faces,
2100                                   "SmoothMesh.faces");
2101
2102         mesh->num_verts = num_verts;
2103         mesh->num_edges = num_edges;
2104         mesh->num_faces = num_faces;
2105
2106         mesh->max_verts = max_verts;
2107         mesh->max_edges = max_edges;
2108         mesh->max_faces = max_faces;
2109
2110         return mesh;
2111 }
2112
2113 static void smoothmesh_free(SmoothMesh *mesh)
2114 {
2115         int i;
2116
2117         for(i = 0; i < mesh->num_verts; ++i)
2118                 BLI_linklist_free(mesh->verts[i].faces, NULL);
2119
2120         for(i = 0; i < mesh->num_edges; ++i)
2121                 BLI_linklist_free(mesh->edges[i].faces, NULL);
2122         
2123         if(mesh->arena)
2124                 BLI_memarena_free(mesh->arena);
2125
2126         MEM_freeN(mesh->verts);
2127         MEM_freeN(mesh->edges);
2128         MEM_freeN(mesh->faces);
2129         MEM_freeN(mesh);
2130 }
2131
2132 static void smoothmesh_resize_verts(SmoothMesh *mesh, int max_verts)
2133 {
2134         int i;
2135         SmoothVert *tmp;
2136
2137         if(max_verts <= mesh->max_verts) return;
2138
2139         tmp = MEM_callocN(sizeof(*tmp) * max_verts, "SmoothMesh.verts");
2140
2141         memcpy(tmp, mesh->verts, sizeof(*tmp) * mesh->num_verts);
2142
2143         /* remap vert pointers in edges */
2144         for(i = 0; i < mesh->num_edges; ++i) {
2145                 int j;
2146                 SmoothEdge *edge = &mesh->edges[i];
2147
2148                 for(j = 0; j < SMOOTHEDGE_NUM_VERTS; ++j)
2149                         /* pointer arithmetic to get vert array index */
2150                         edge->verts[j] = &tmp[edge->verts[j] - mesh->verts];
2151         }
2152
2153         MEM_freeN(mesh->verts);
2154         mesh->verts = tmp;
2155         mesh->max_verts = max_verts;
2156 }
2157
2158 static void smoothmesh_resize_edges(SmoothMesh *mesh, int max_edges)
2159 {
2160         int i;
2161         SmoothEdge *tmp;
2162
2163         if(max_edges <= mesh->max_edges) return;
2164
2165         tmp = MEM_callocN(sizeof(*tmp) * max_edges, "SmoothMesh.edges");
2166
2167         memcpy(tmp, mesh->edges, sizeof(*tmp) * mesh->num_edges);
2168
2169         /* remap edge pointers in faces */
2170         for(i = 0; i < mesh->num_faces; ++i) {
2171                 int j;
2172                 SmoothFace *face = &mesh->faces[i];
2173
2174                 for(j = 0; j < SMOOTHFACE_MAX_EDGES; ++j)
2175                         if(face->edges[j])
2176                                 /* pointer arithmetic to get edge array index */
2177                                 face->edges[j] = &tmp[face->edges[j] - mesh->edges];
2178         }
2179
2180         MEM_freeN(mesh->edges);
2181         mesh->edges = tmp;
2182         mesh->max_edges = max_edges;
2183 }
2184
2185 #ifdef EDGESPLIT_DEBUG_0
2186 static void smoothmesh_print(SmoothMesh *mesh)
2187 {
2188         int i, j;
2189         DerivedMesh *dm = mesh->dm;
2190
2191         printf("--- SmoothMesh ---\n");
2192         printf("--- Vertices ---\n");
2193         for(i = 0; i < mesh->num_verts; i++) {
2194                 SmoothVert *vert = &mesh->verts[i];
2195                 LinkNode *node;
2196                 MVert mv;
2197
2198                 dm->getVert(dm, vert->oldIndex, &mv);
2199
2200                 printf("%3d: ind={%3d, %3d}, pos={% 5.1f, % 5.1f, % 5.1f}",
2201                        i, vert->oldIndex, vert->newIndex,
2202          mv.co[0], mv.co[1], mv.co[2]);
2203                 printf(", faces={");
2204                 for(node = vert->faces; node != NULL; node = node->next) {
2205                         printf(" %d", ((SmoothFace *)node->link)->newIndex);
2206                 }
2207                 printf("}\n");
2208         }
2209
2210         printf("\n--- Edges ---\n");
2211         for(i = 0; i < mesh->num_edges; i++) {
2212                 SmoothEdge *edge = &mesh->edges[i];
2213                 LinkNode *node;
2214
2215                 printf("%4d: indices={%4d, %4d}, verts={%4d, %4d}",
2216                        i,
2217          edge->oldIndex, edge->newIndex,
2218   edge->verts[0]->newIndex, edge->verts[1]->newIndex);
2219                 if(edge->verts[0] == edge->verts[1]) printf(" <- DUPLICATE VERTEX");
2220                 printf(", faces={");
2221                 for(node = edge->faces; node != NULL; node = node->next) {
2222                         printf(" %d", ((SmoothFace *)node->link)->newIndex);
2223                 }
2224                 printf("}\n");
2225         }
2226
2227         printf("\n--- Faces ---\n");
2228         for(i = 0; i < mesh->num_faces; i++) {
2229                 SmoothFace *face = &mesh->faces[i];
2230
2231                 printf("%4d: indices={%4d, %4d}, edges={", i,
2232                        face->oldIndex, face->newIndex);
2233                 for(j = 0; j < SMOOTHFACE_MAX_EDGES && face->edges[j]; j++) {
2234                         if(face->flip[j])
2235                                 printf(" -%-2d", face->edges[j]->newIndex);
2236                         else
2237                                 printf("  %-2d", face->edges[j]->newIndex);
2238                 }
2239                 printf("}, verts={");
2240                 for(j = 0; j < SMOOTHFACE_MAX_EDGES && face->edges[j]; j++) {
2241                         printf(" %d", face->edges[j]->verts[face->flip[j]]->newIndex);
2242                 }
2243                 printf("}\n");
2244         }
2245 }
2246 #endif
2247
2248 static SmoothMesh *smoothmesh_from_derivedmesh(DerivedMesh *dm)
2249 {
2250         SmoothMesh *mesh;
2251         EdgeHash *edges = BLI_edgehash_new();
2252         int i;
2253         int totvert, totedge, totface;
2254
2255         totvert = dm->getNumVerts(dm);
2256         totedge = dm->getNumEdges(dm);
2257         totface = dm->getNumFaces(dm);
2258
2259         mesh = smoothmesh_new(totvert, totedge, totface,
2260                               totvert, totedge, totface);
2261
2262         mesh->dm = dm;
2263
2264         for(i = 0; i < totvert; i++) {
2265                 SmoothVert *vert = &mesh->verts[i];
2266
2267                 vert->oldIndex = vert->newIndex = i;
2268         }
2269
2270         for(i = 0; i < totedge; i++) {
2271                 SmoothEdge *edge = &mesh->edges[i];
2272                 MEdge med;
2273
2274                 dm->getEdge(dm, i, &med);
2275                 edge->verts[0] = &mesh->verts[med.v1];
2276                 edge->verts[1] = &mesh->verts[med.v2];
2277                 edge->oldIndex = edge->newIndex = i;
2278                 edge->flag = med.flag;
2279
2280                 BLI_edgehash_insert(edges, med.v1, med.v2, edge);
2281         }
2282
2283         for(i = 0; i < totface; i++) {
2284                 SmoothFace *face = &mesh->faces[i];
2285                 MFace mf;
2286                 MVert v1, v2, v3;
2287                 int j;
2288
2289                 dm->getFace(dm, i, &mf);
2290
2291                 dm->getVert(dm, mf.v1, &v1);
2292                 dm->getVert(dm, mf.v2, &v2);
2293                 dm->getVert(dm, mf.v3, &v3);
2294                 face->edges[0] = BLI_edgehash_lookup(edges, mf.v1, mf.v2);
2295                 if(face->edges[0]->verts[1]->oldIndex == mf.v1) face->flip[0] = 1;
2296                 face->edges[1] = BLI_edgehash_lookup(edges, mf.v2, mf.v3);
2297                 if(face->edges[1]->verts[1]->oldIndex == mf.v2) face->flip[1] = 1;
2298                 if(mf.v4) {
2299                         MVert v4;
2300                         dm->getVert(dm, mf.v4, &v4);
2301                         face->edges[2] = BLI_edgehash_lookup(edges, mf.v3, mf.v4);
2302                         if(face->edges[2]->verts[1]->oldIndex == mf.v3) face->flip[2] = 1;
2303                         face->edges[3] = BLI_edgehash_lookup(edges, mf.v4, mf.v1);
2304                         if(face->edges[3]->verts[1]->oldIndex == mf.v4) face->flip[3] = 1;
2305                         normal_quad_v3( face->normal,v1.co, v2.co, v3.co, v4.co);
2306                 } else {
2307                         face->edges[2] = BLI_edgehash_lookup(edges, mf.v3, mf.v1);
2308                         if(face->edges[2]->verts[1]->oldIndex == mf.v3) face->flip[2] = 1;
2309                         face->edges[3] = NULL;
2310                         normal_tri_v3( face->normal,v1.co, v2.co, v3.co);
2311                 }
2312
2313                 for(j = 0; j < SMOOTHFACE_MAX_EDGES && face->edges[j]; j++) {
2314                         SmoothEdge *edge = face->edges[j];
2315                         BLI_linklist_prepend(&edge->faces, face);
2316                         BLI_linklist_prepend(&edge->verts[face->flip[j]]->faces, face);
2317                 }
2318
2319                 face->oldIndex = face->newIndex = i;
2320         }
2321
2322         BLI_edgehash_free(edges, NULL);
2323
2324         return mesh;
2325 }
2326
2327 static DerivedMesh *CDDM_from_smoothmesh(SmoothMesh *mesh)
2328 {
2329         DerivedMesh *result = CDDM_from_template(mesh->dm,
2330                         mesh->num_verts,
2331    mesh->num_edges,
2332    mesh->num_faces);
2333         MVert *new_verts = CDDM_get_verts(result);
2334         MEdge *new_edges = CDDM_get_edges(result);
2335         MFace *new_faces = CDDM_get_faces(result);
2336         int i;
2337
2338         for(i = 0; i < mesh->num_verts; ++i) {
2339                 SmoothVert *vert = &mesh->verts[i];
2340                 MVert *newMV = &new_verts[vert->newIndex];
2341
2342                 DM_copy_vert_data(mesh->dm, result,
2343                                   vert->oldIndex, vert->newIndex, 1);
2344                 mesh->dm->getVert(mesh->dm, vert->oldIndex, newMV);
2345         }
2346
2347         for(i = 0; i < mesh->num_edges; ++i) {
2348                 SmoothEdge *edge = &mesh->edges[i];
2349                 MEdge *newME = &new_edges[edge->newIndex];
2350
2351                 DM_copy_edge_data(mesh->dm, result,
2352                                   edge->oldIndex, edge->newIndex, 1);
2353                 mesh->dm->getEdge(mesh->dm, edge->oldIndex, newME);
2354                 newME->v1 = edge->verts[0]->newIndex;
2355                 newME->v2 = edge->verts[1]->newIndex;
2356         }
2357
2358         for(i = 0; i < mesh->num_faces; ++i) {
2359                 SmoothFace *face = &mesh->faces[i];
2360                 MFace *newMF = &new_faces[face->newIndex];
2361
2362                 DM_copy_face_data(mesh->dm, result,
2363                                   face->oldIndex, face->newIndex, 1);
2364                 mesh->dm->getFace(mesh->dm, face->oldIndex, newMF);
2365
2366                 newMF->v1 = face->edges[0]->verts[face->flip[0]]->newIndex;
2367                 newMF->v2 = face->edges[1]->verts[face->flip[1]]->newIndex;
2368                 newMF->v3 = face->edges[2]->verts[face->flip[2]]->newIndex;
2369
2370                 if(face->edges[3]) {
2371                         newMF->v4 = face->edges[3]->verts[face->flip[3]]->newIndex;
2372                 } else {
2373                         newMF->v4 = 0;
2374                 }
2375         }
2376
2377         return result;
2378 }
2379
2380 /* returns the other vert in the given edge
2381  */
2382 static SmoothVert *other_vert(SmoothEdge *edge, SmoothVert *vert)
2383 {
2384         if(edge->verts[0] == vert) return edge->verts[1];
2385         else return edge->verts[0];
2386 }
2387
2388 /* returns the other edge in the given face that uses the given vert
2389  * returns NULL if no other edge in the given face uses the given vert
2390  * (this should never happen)
2391  */
2392 static SmoothEdge *other_edge(SmoothFace *face, SmoothVert *vert,
2393                               SmoothEdge *edge)
2394 {
2395         int i,j;
2396         for(i = 0; i < SMOOTHFACE_MAX_EDGES && face->edges[i]; i++) {
2397                 SmoothEdge *tmp_edge = face->edges[i];
2398                 if(tmp_edge == edge) continue;
2399
2400                 for(j = 0; j < SMOOTHEDGE_NUM_VERTS; j++)
2401                         if(tmp_edge->verts[j] == vert) return tmp_edge;
2402         }
2403
2404         /* if we get to here, something's wrong (there should always be 2 edges
2405         * which use the same vert in a face)
2406         */
2407         return NULL;
2408 }
2409
2410 /* returns a face attached to the given edge which is not the given face.
2411  * returns NULL if no other faces use this edge.
2412  */
2413 static SmoothFace *other_face(SmoothEdge *edge, SmoothFace *face)
2414 {
2415         LinkNode *node;
2416
2417         for(node = edge->faces; node != NULL; node = node->next)
2418                 if(node->link != face) return node->link;
2419
2420         return NULL;
2421 }
2422
2423 #if 0
2424 /* copies source list to target, overwriting target (target is not freed)
2425  * nodes in the copy will be in the same order as in source
2426  */
2427 static void linklist_copy(LinkNode **target, LinkNode *source)
2428 {
2429         LinkNode *node = NULL;
2430         *target = NULL;
2431
2432         for(; source; source = source->next) {
2433                 if(node) {
2434                         node->next = MEM_mallocN(sizeof(*node->next), "nlink_copy");
2435                                                                                 node = node->next;
2436 } else {
2437                                                                                 node = *target = MEM_mallocN(sizeof(**target), "nlink_copy");
2438 }
2439                                                                                 node->link = source->link;
2440                                                                                 node->next = NULL;
2441 }
2442 }
2443 #endif
2444
2445                                                                                 /* appends source to target if it's not already in target */
2446                                                                                 static void linklist_append_unique(LinkNode **target, void *source) 
2447 {
2448         LinkNode *node;
2449         LinkNode *prev = NULL;
2450
2451         /* check if source value is already in the list */
2452         for(node = *target; node; prev = node, node = node->next)
2453                 if(node->link == source) return;
2454
2455         node = MEM_mallocN(sizeof(*node), "nlink");
2456         node->next = NULL;
2457         node->link = source;
2458
2459         if(prev) prev->next = node;
2460         else *target = node;
2461 }
2462
2463 /* appends elements of source which aren't already in target to target */
2464 static void linklist_append_list_unique(LinkNode **target, LinkNode *source)
2465 {
2466         for(; source; source = source->next)
2467                 linklist_append_unique(target, source->link);
2468 }
2469
2470 #if 0 /* this is no longer used, it should possibly be removed */
2471 /* prepends prepend to list - doesn't copy nodes, just joins the lists */
2472 static void linklist_prepend_linklist(LinkNode **list, LinkNode *prepend)
2473 {
2474         if(prepend) {
2475                 LinkNode *node = prepend;
2476                 while(node->next) node = node->next;
2477
2478                 node->next = *list;
2479                 *list = prepend;
2480 }
2481 }
2482 #endif
2483
2484 /* returns 1 if the linked list contains the given pointer, 0 otherwise
2485  */
2486 static int linklist_contains(LinkNode *list, void *ptr)
2487 {
2488         LinkNode *node;
2489
2490         for(node = list; node; node = node->next)
2491                 if(node->link == ptr) return 1;
2492
2493         return 0;
2494 }
2495
2496 /* returns 1 if the first linked list is a subset of the second (comparing
2497  * pointer values), 0 if not
2498  */
2499 static int linklist_subset(LinkNode *list1, LinkNode *list2)
2500 {
2501         for(; list1; list1 = list1->next)
2502                 if(!linklist_contains(list2, list1->link))
2503                         return 0;
2504
2505         return 1;
2506 }
2507
2508 #if 0
2509 /* empties the linked list
2510  * frees pointers with freefunc if freefunc is not NULL
2511  */
2512 static void linklist_empty(LinkNode **list, LinkNodeFreeFP freefunc)
2513 {
2514         BLI_linklist_free(*list, freefunc);
2515         *list = NULL;
2516 }
2517 #endif
2518
2519 /* removes the first instance of value from the linked list
2520  * frees the pointer with freefunc if freefunc is not NULL
2521  */
2522 static void linklist_remove_first(LinkNode **list, void *value,
2523                                   LinkNodeFreeFP freefunc)
2524 {
2525         LinkNode *node = *list;
2526         LinkNode *prev = NULL;
2527
2528         while(node && node->link != value) {
2529                 prev = node;
2530                 node = node->next;
2531         }
2532
2533         if(node) {
2534                 if(prev)
2535                         prev->next = node->next;
2536                 else
2537                         *list = node->next;
2538
2539                 if(freefunc)
2540                         freefunc(node->link);
2541
2542                 MEM_freeN(node);
2543         }
2544 }
2545
2546 /* removes all elements in source from target */
2547 static void linklist_remove_list(LinkNode **target, LinkNode *source,
2548                                  LinkNodeFreeFP freefunc)
2549 {
2550         for(; source; source = source->next)
2551                 linklist_remove_first(target, source->link, freefunc);
2552 }
2553
2554 #ifdef EDGESPLIT_DEBUG_0
2555 static void print_ptr(void *ptr)
2556 {
2557         printf("%p\n", ptr);
2558 }
2559
2560 static void print_edge(void *ptr)
2561 {
2562         SmoothEdge *edge = ptr;
2563         printf(" %4d", edge->newIndex);
2564 }
2565
2566 static void print_face(void *ptr)
2567 {
2568         SmoothFace *face = ptr;
2569         printf(" %4d", face->newIndex);
2570 }
2571 #endif
2572
2573 typedef struct ReplaceData {
2574         void *find;
2575         void *replace;
2576 } ReplaceData;
2577
2578 static void edge_replace_vert(void *ptr, void *userdata)
2579 {
2580         SmoothEdge *edge = ptr;
2581         SmoothVert *find = ((ReplaceData *)userdata)->find;
2582         SmoothVert *replace = ((ReplaceData *)userdata)->replace;
2583         int i;
2584
2585 #ifdef EDGESPLIT_DEBUG_3
2586         printf("replacing vert %4d with %4d in edge %4d",
2587                find->newIndex, replace->newIndex, edge->newIndex);
2588         printf(": {%4d, %4d}", edge->verts[0]->newIndex, edge->verts[1]->newIndex);
2589 #endif
2590
2591         for(i = 0; i < SMOOTHEDGE_NUM_VERTS; i++) {
2592                 if(edge->verts[i] == find) {
2593                         linklist_append_list_unique(&replace->faces, edge->faces);
2594                         linklist_remove_list(&find->faces, edge->faces, NULL);
2595
2596                         edge->verts[i] = replace;
2597                 }
2598         }
2599
2600 #ifdef EDGESPLIT_DEBUG_3
2601         printf(" -> {%4d, %4d}\n", edge->verts[0]->newIndex, edge->verts[1]->newIndex);
2602 #endif
2603 }
2604
2605 static void face_replace_vert(void *ptr, void *userdata)
2606 {
2607         SmoothFace *face = ptr;
2608         int i;
2609
2610         for(i = 0; i < SMOOTHFACE_MAX_EDGES && face->edges[i]; i++)
2611                 edge_replace_vert(face->edges[i], userdata);
2612 }
2613
2614 static void face_replace_edge(void *ptr, void *userdata)
2615 {
2616         SmoothFace *face = ptr;
2617         SmoothEdge *find = ((ReplaceData *)userdata)->find;
2618         SmoothEdge *replace = ((ReplaceData *)userdata)->replace;
2619         int i;
2620
2621 #ifdef EDGESPLIT_DEBUG_3
2622         printf("replacing edge %4d with %4d in face %4d",
2623                find->newIndex, replace->newIndex, face->newIndex);
2624         if(face->edges[3])
2625                 printf(": {%2d %2d %2d %2d}",
2626                        face->edges[0]->newIndex, face->edges[1]->newIndex,
2627          face->edges[2]->newIndex, face->edges[3]->newIndex);
2628         else
2629                 printf(": {%2d %2d %2d}",
2630                        face->edges[0]->newIndex, face->edges[1]->newIndex,
2631          face->edges[2]->newIndex);
2632 #endif
2633
2634         for(i = 0; i < SMOOTHFACE_MAX_EDGES && face->edges[i]; i++) {
2635                 if(face->edges[i] == find) {
2636                         linklist_remove_first(&face->edges[i]->faces, face, NULL);
2637                         BLI_linklist_prepend(&replace->faces, face);
2638                         face->edges[i] = replace;
2639                 }
2640         }
2641
2642 #ifdef EDGESPLIT_DEBUG_3
2643         if(face->edges[3])
2644                 printf(" -> {%2d %2d %2d %2d}\n",
2645                        face->edges[0]->newIndex, face->edges[1]->newIndex,
2646          face->edges[2]->newIndex, face->edges[3]->newIndex);
2647         else
2648                 printf(" -> {%2d %2d %2d}\n",
2649                        face->edges[0]->newIndex, face->edges[1]->newIndex,
2650          face->edges[2]->newIndex);
2651 #endif
2652 }
2653
2654 static int edge_is_loose(SmoothEdge *edge)
2655 {
2656         return !(edge->faces && edge->faces->next);
2657 }
2658
2659 static int edge_is_sharp(SmoothEdge *edge, int flags,
2660                          float threshold)
2661 {
2662 #ifdef EDGESPLIT_DEBUG_1
2663         printf("edge %d: ", edge->newIndex);
2664 #endif
2665         if(edge->flag & ME_SHARP) {
2666                 /* edge can only be sharp if it has at least 2 faces */
2667                 if(!edge_is_loose(edge)) {
2668 #ifdef EDGESPLIT_DEBUG_1
2669                         printf("sharp\n");
2670 #endif
2671                         return 1;
2672                 } else {
2673                         /* edge is loose, so it can't be sharp */
2674                         edge->flag &= ~ME_SHARP;
2675                 }
2676         }
2677
2678 #ifdef EDGESPLIT_DEBUG_1
2679         printf("not sharp\n");
2680 #endif
2681         return 0;
2682 }
2683
2684 /* finds another sharp edge which uses vert, by traversing faces around the
2685  * vert until it does one of the following:
2686  * - hits a loose edge (the edge is returned)
2687  * - hits a sharp edge (the edge is returned)
2688  * - returns to the start edge (NULL is returned)
2689  */
2690 static SmoothEdge *find_other_sharp_edge(SmoothVert *vert, SmoothEdge *edge,
2691                                          LinkNode **visited_faces, float threshold, int flags)
2692 {
2693         SmoothFace *face = NULL;
2694         SmoothEdge *edge2 = NULL;
2695         /* holds the edges we've seen so we can avoid looping indefinitely */
2696         LinkNode *visited_edges = NULL;
2697 #ifdef EDGESPLIT_DEBUG_1
2698         printf("=== START === find_other_sharp_edge(edge = %4d, vert = %4d)\n",
2699                edge->newIndex, vert->newIndex);
2700 #endif
2701
2702         /* get a face on which to start */
2703         if(edge->faces) face = edge->faces->link;
2704         else return NULL;
2705
2706         /* record this edge as visited */
2707         BLI_linklist_prepend(&visited_edges, edge);
2708
2709         /* get the next edge */
2710         edge2 = other_edge(face, vert, edge);
2711
2712         /* record this face as visited */
2713         if(visited_faces)
2714                 BLI_linklist_prepend(visited_faces, face);
2715
2716         /* search until we hit a loose edge or a sharp edge or an edge we've
2717         * seen before
2718         */
2719         while(face && !edge_is_sharp(edge2, flags, threshold)
2720                      && !linklist_contains(visited_edges, edge2)) {
2721 #ifdef EDGESPLIT_DEBUG_3
2722                 printf("current face %4d; current edge %4d\n", face->newIndex,
2723                        edge2->newIndex);
2724 #endif
2725                 /* get the next face */
2726                 face = other_face(edge2, face);
2727
2728                 /* if face == NULL, edge2 is a loose edge */
2729                 if(face) {
2730                         /* record this face as visited */
2731                         if(visited_faces)
2732                                 BLI_linklist_prepend(visited_faces, face);
2733
2734                         /* record this edge as visited */
2735                         BLI_linklist_prepend(&visited_edges, edge2);
2736
2737                         /* get the next edge */
2738                         edge2 = other_edge(face, vert, edge2);
2739 #ifdef EDGESPLIT_DEBUG_3
2740                         printf("next face %4d; next edge %4d\n",
2741                                face->newIndex, edge2->newIndex);
2742                 } else {
2743                         printf("loose edge: %4d\n", edge2->newIndex);
2744 #endif
2745                 }
2746                      }
2747
2748                      /* either we came back to the start edge or we found a sharp/loose edge */
2749                      if(linklist_contains(visited_edges, edge2))
2750                              /* we came back to the start edge */
2751                              edge2 = NULL;
2752
2753                      BLI_linklist_free(visited_edges, NULL);
2754
2755 #ifdef EDGESPLIT_DEBUG_1
2756                      printf("=== END === find_other_sharp_edge(edge = %4d, vert = %4d), "
2757                                      "returning edge %d\n",
2758          edge->newIndex, vert->newIndex, edge2 ? edge2->newIndex : -1);
2759 #endif
2760                      return edge2;
2761 }
2762
2763 static void split_single_vert(SmoothVert *vert, SmoothFace *face,
2764                               SmoothMesh *mesh)
2765 {
2766         SmoothVert *copy_vert;
2767         ReplaceData repdata;
2768
2769         copy_vert = smoothvert_copy(vert, mesh);
2770
2771         repdata.find = vert;
2772         repdata.replace = copy_vert;
2773         face_replace_vert(face, &repdata);
2774 }
2775
2776 typedef struct PropagateEdge {
2777         struct PropagateEdge *next, *prev;
2778         SmoothEdge *edge;
2779         SmoothVert *vert;
2780 } PropagateEdge;
2781
2782 static void push_propagate_stack(SmoothEdge *edge, SmoothVert *vert, SmoothMesh *mesh)
2783 {
2784         PropagateEdge *pedge = mesh->reusestack.first;
2785
2786         if(pedge) {
2787                 BLI_remlink(&mesh->reusestack, pedge);
2788         }
2789         else {
2790                 if(!mesh->arena) {
2791                         mesh->arena = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE);
2792                         BLI_memarena_use_calloc(mesh->arena);
2793                 }
2794
2795                 pedge = BLI_memarena_alloc(mesh->arena, sizeof(PropagateEdge));
2796         }
2797
2798         pedge->edge = edge;
2799         pedge->vert = vert;
2800         BLI_addhead(&mesh->propagatestack, pedge);
2801 }
2802
2803 static void pop_propagate_stack(SmoothEdge **edge, SmoothVert **vert, SmoothMesh *mesh)
2804 {
2805         PropagateEdge *pedge = mesh->propagatestack.first;
2806
2807         if(pedge) {
2808                 *edge = pedge->edge;
2809                 *vert = pedge->vert;
2810                 BLI_remlink(&mesh->propagatestack, pedge);
2811                 BLI_addhead(&mesh->reusestack, pedge);
2812         }
2813         else {
2814                 *edge = NULL;
2815                 *vert = NULL;
2816         }
2817 }
2818
2819 static void split_edge(SmoothEdge *edge, SmoothVert *vert, SmoothMesh *mesh);
2820
2821 static void propagate_split(SmoothEdge *edge, SmoothVert *vert,
2822                             SmoothMesh *mesh)
2823 {
2824         SmoothEdge *edge2;
2825         LinkNode *visited_faces = NULL;
2826 #ifdef EDGESPLIT_DEBUG_1
2827         printf("=== START === propagate_split(edge = %4d, vert = %4d)\n",
2828                edge->newIndex, vert->newIndex);
2829 #endif
2830
2831         edge2 = find_other_sharp_edge(vert, edge, &visited_faces,
2832                                       mesh->threshold, mesh->flags);
2833
2834         if(!edge2) {
2835                 /* didn't find a sharp or loose edge, so we've hit a dead end */
2836         } else if(!edge_is_loose(edge2)) {
2837                 /* edge2 is not loose, so it must be sharp */
2838                 if(edge_is_loose(edge)) {
2839                         /* edge is loose, so we can split edge2 at this vert */
2840                         split_edge(edge2, vert, mesh);
2841                 } else if(edge_is_sharp(edge, mesh->flags, mesh->threshold)) {
2842                         /* both edges are sharp, so we can split the pair at vert */
2843                         split_edge(edge, vert, mesh);
2844                 } else {
2845                         /* edge is not sharp, so try to split edge2 at its other vert */
2846                         split_edge(edge2, other_vert(edge2, vert), mesh);
2847                 }
2848         } else { /* edge2 is loose */
2849                 if(edge_is_loose(edge)) {
2850                         SmoothVert *vert2;
2851                         ReplaceData repdata;
2852
2853                         /* can't split edge, what should we do with vert? */
2854                         if(linklist_subset(vert->faces, visited_faces)) {
2855                                 /* vert has only one fan of faces attached; don't split it */
2856                         } else {
2857                                 /* vert has more than one fan of faces attached; split it */
2858                                 vert2 = smoothvert_copy(vert, mesh);
2859
2860                                 /* replace vert with its copy in visited_faces */
2861                                 repdata.find = vert;
2862                                 repdata.replace = vert2;
2863                                 BLI_linklist_apply(visited_faces, face_replace_vert, &repdata);
2864                         }
2865                 } else {
2866                         /* edge is not loose, so it must be sharp; split it */
2867                         split_edge(edge, vert, mesh);
2868                 }
2869         }
2870
2871         BLI_linklist_free(visited_faces, NULL);
2872 #ifdef EDGESPLIT_DEBUG_1
2873         printf("=== END === propagate_split(edge = %4d, vert = %4d)\n",
2874                edge->newIndex, vert->newIndex);
2875 #endif
2876 }
2877
2878 static void split_edge(SmoothEdge *edge, SmoothVert *vert, SmoothMesh *mesh)
2879 {
2880         SmoothEdge *edge2;
2881         SmoothVert *vert2;
2882         ReplaceData repdata;
2883         /* the list of faces traversed while looking for a sharp edge */
2884         LinkNode *visited_faces = NULL;
2885 #ifdef EDGESPLIT_DEBUG_1
2886         printf("=== START === split_edge(edge = %4d, vert = %4d)\n",
2887                edge->newIndex, vert->newIndex);
2888 #endif
2889
2890         edge2 = find_other_sharp_edge(vert, edge, &visited_faces,
2891                                       mesh->threshold, mesh->flags);
2892
2893         if(!edge2) {
2894                 /* didn't find a sharp or loose edge, so try the other vert */
2895                 vert2 = other_vert(edge, vert);
2896                 push_propagate_stack(edge, vert2, mesh);
2897         } else if(!edge_is_loose(edge2)) {
2898                 /* edge2 is not loose, so it must be sharp */
2899                 SmoothEdge *copy_edge = smoothedge_copy(edge, mesh);
2900                 SmoothEdge *copy_edge2 = smoothedge_copy(edge2, mesh);
2901                 SmoothVert *vert2;
2902
2903                 /* replace edge with its copy in visited_faces */
2904                 repdata.find = edge;
2905                 repdata.replace = copy_edge;
2906                 BLI_linklist_apply(visited_faces, face_replace_edge, &repdata);
2907
2908                 /* replace edge2 with its copy in visited_faces */
2909                 repdata.find = edge2;
2910                 repdata.replace = copy_edge2;
2911                 BLI_linklist_apply(visited_faces, face_replace_edge, &repdata);
2912
2913                 vert2 = smoothvert_copy(vert, mesh);
2914
2915                 /* replace vert with its copy in visited_faces (must be done after
2916                 * edge replacement so edges have correct vertices)
2917                 */
2918                 repdata.find = vert;
2919                 repdata.replace = vert2;
2920                 BLI_linklist_apply(visited_faces, face_replace_vert, &repdata);
2921
2922                 /* all copying and replacing is done; the mesh should be consistent.
2923                 * now propagate the split to the vertices at either end
2924                 */
2925                 push_propagate_stack(copy_edge, other_vert(copy_edge, vert2), mesh);
2926                 push_propagate_stack(copy_edge2, other_vert(copy_edge2, vert2), mesh);
2927
2928                 if(smoothedge_has_vert(edge, vert))
2929                         push_propagate_stack(edge, vert, mesh);
2930         } else {
2931                 /* edge2 is loose */
2932                 SmoothEdge *copy_edge = smoothedge_copy(edge, mesh);
2933                 SmoothVert *vert2;
2934
2935                 /* replace edge with its copy in visited_faces */
2936                 repdata.find = edge;
2937                 repdata.replace = copy_edge;
2938                 BLI_linklist_apply(visited_faces, face_replace_edge, &repdata);
2939
2940                 vert2 = smoothvert_copy(vert, mesh);
2941
2942                 /* replace vert with its copy in visited_faces (must be done after
2943                 * edge replacement so edges have correct vertices)
2944                 */
2945                 repdata.find = vert;
2946                 repdata.replace = vert2;
2947                 BLI_linklist_apply(visited_faces, face_replace_vert, &repdata);
2948
2949                 /* copying and replacing is done; the mesh should be consistent.
2950                 * now propagate the split to the vertex at the other end
2951                 */
2952                 push_propagate_stack(copy_edge, other_vert(copy_edge, vert2), mesh);
2953
2954                 if(smoothedge_has_vert(edge, vert))
2955                         push_propagate_stack(edge, vert, mesh);
2956         }
2957
2958         BLI_linklist_free(visited_faces, NULL);
2959 #ifdef EDGESPLIT_DEBUG_1
2960         printf("=== END === split_edge(edge = %4d, vert = %4d)\n",
2961                edge->newIndex, vert->newIndex);
2962 #endif
2963 }
2964
2965 static void tag_and_count_extra_edges(SmoothMesh *mesh, float split_angle,
2966                                       int flags, int *extra_edges)
2967 {
2968         /* if normal1 dot normal2 < threshold, angle is greater, so split */
2969         /* FIXME not sure if this always works */
2970         /* 0.00001 added for floating-point rounding */
2971         float threshold = cos((split_angle + 0.00001) * M_PI / 180.0);
2972         int i;
2973
2974         *extra_edges = 0;
2975
2976         /* loop through edges, counting potential new ones */
2977         for(i = 0; i < mesh->num_edges; i++) {
2978                 SmoothEdge *edge = &mesh->edges[i];
2979                 int sharp = 0;
2980
2981                 /* treat all non-manifold edges (3 or more faces) as sharp */
2982                 if(edge->faces && edge->faces->next && edge->faces->next->next) {
2983                         LinkNode *node;
2984
2985                         /* this edge is sharp */
2986                         sharp = 1;
2987
2988                         /* add an extra edge for every face beyond the first */
2989                         *extra_edges += 2;
2990                         for(node = edge->faces->next->next->next; node; node = node->next)
2991                                 (*extra_edges)++;
2992                 } else if((flags & (MOD_EDGESPLIT_FROMANGLE | MOD_EDGESPLIT_FROMFLAG))
2993                                          && !edge_is_loose(edge)) {
2994                         /* (the edge can only be sharp if we're checking angle or flag,
2995                         * and it has at least 2 faces) */
2996
2997                                                  /* if we're checking the sharp flag and it's set, good */
2998                                                  if((flags & MOD_EDGESPLIT_FROMFLAG) && (edge->flag & ME_SHARP)) {
2999                                                          /* this edge is sharp */
3000                                                          sharp = 1;
3001
3002                                                          (*extra_edges)++;
3003                                                  } else if(flags & MOD_EDGESPLIT_FROMANGLE) {
3004                                                          /* we know the edge has 2 faces, so check the angle */
3005                                                          SmoothFace *face1 = edge->faces->link;
3006                                                          SmoothFace *face2 = edge->faces->next->link;
3007                                                          float edge_angle_cos = dot_v3v3(face1->normal,
3008                                                                          face2->normal);
3009
3010                                                          if(edge_angle_cos < threshold) {
3011                                                                  /* this edge is sharp */
3012                                                                  sharp = 1;
3013
3014                                                                  (*extra_edges)++;
3015                                                          }
3016                                                  }
3017                                          }
3018
3019                                          /* set/clear sharp flag appropriately */
3020                                          if(sharp) edge->flag |= ME_SHARP;
3021                                          else edge->flag &= ~ME_SHARP;
3022         }
3023 }
3024
3025 static void split_sharp_edges(SmoothMesh *mesh, float split_angle, int flags)
3026 {
3027         SmoothVert *vert;
3028         int i;
3029         /* if normal1 dot normal2 < threshold, angle is greater, so split */
3030         /* FIXME not sure if this always works */
3031         /* 0.00001 added for floating-point rounding */
3032         mesh->threshold = cos((split_angle + 0.00001) * M_PI / 180.0);