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