code cleanup: make bmesh operator names more consistant since python has access to...
[blender.git] / source / blender / modifiers / intern / MOD_explode.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software  Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * The Original Code is Copyright (C) 2005 by the Blender Foundation.
19  * All rights reserved.
20  *
21  * Contributor(s): Daniel Dunbar
22  *                 Ton Roosendaal,
23  *                 Ben Batt,
24  *                 Brecht Van Lommel,
25  *                 Campbell Barton
26  *
27  * ***** END GPL LICENSE BLOCK *****
28  *
29  */
30
31 /** \file blender/modifiers/intern/MOD_explode.c
32  *  \ingroup modifiers
33  */
34
35
36 #include "DNA_meshdata_types.h"
37 #include "DNA_scene_types.h"
38 #include "DNA_object_types.h"
39
40 #include "BLI_kdtree.h"
41 #include "BLI_rand.h"
42 #include "BLI_math.h"
43 #include "BLI_edgehash.h"
44 #include "BLI_utildefines.h"
45
46 #include "BKE_cdderivedmesh.h"
47 #include "BKE_deform.h"
48 #include "BKE_lattice.h"
49 #include "BKE_mesh.h"
50 #include "BKE_modifier.h"
51 #include "BKE_object.h"
52 #include "BKE_particle.h"
53 #include "BKE_scene.h"
54
55
56 #include "MEM_guardedalloc.h"
57
58 #include "MOD_util.h"
59
60 static void initData(ModifierData *md)
61 {
62         ExplodeModifierData *emd = (ExplodeModifierData *) md;
63
64         emd->facepa = NULL;
65         emd->flag |= eExplodeFlag_Unborn + eExplodeFlag_Alive + eExplodeFlag_Dead;
66 }
67 static void freeData(ModifierData *md)
68 {
69         ExplodeModifierData *emd = (ExplodeModifierData *) md;
70         
71         if (emd->facepa) MEM_freeN(emd->facepa);
72 }
73 static void copyData(ModifierData *md, ModifierData *target)
74 {
75         ExplodeModifierData *emd = (ExplodeModifierData *) md;
76         ExplodeModifierData *temd = (ExplodeModifierData *) target;
77
78         temd->facepa = NULL;
79         temd->flag = emd->flag;
80         temd->protect = emd->protect;
81         temd->vgroup = emd->vgroup;
82 }
83 static int dependsOnTime(ModifierData *UNUSED(md)) 
84 {
85         return 1;
86 }
87 static CustomDataMask requiredDataMask(Object *UNUSED(ob), ModifierData *md)
88 {
89         ExplodeModifierData *emd = (ExplodeModifierData *) md;
90         CustomDataMask dataMask = 0;
91
92         if (emd->vgroup)
93                 dataMask |= CD_MASK_MDEFORMVERT;
94
95         return dataMask;
96 }
97
98 static void createFacepa(ExplodeModifierData *emd,
99                          ParticleSystemModifierData *psmd,
100                          DerivedMesh *dm)
101 {
102         ParticleSystem *psys = psmd->psys;
103         MFace *fa = NULL, *mface = NULL;
104         MVert *mvert = NULL;
105         ParticleData *pa;
106         KDTree *tree;
107         float center[3], co[3];
108         int *facepa = NULL, *vertpa = NULL, totvert = 0, totface = 0, totpart = 0;
109         int i, p, v1, v2, v3, v4 = 0;
110
111         mvert = dm->getVertArray(dm);
112         mface = dm->getTessFaceArray(dm);
113         totface = dm->getNumTessFaces(dm);
114         totvert = dm->getNumVerts(dm);
115         totpart = psmd->psys->totpart;
116
117         BLI_srandom(psys->seed);
118
119         if (emd->facepa)
120                 MEM_freeN(emd->facepa);
121
122         facepa = emd->facepa = MEM_callocN(sizeof(int) * totface, "explode_facepa");
123
124         vertpa = MEM_callocN(sizeof(int) * totvert, "explode_vertpa");
125
126         /* initialize all faces & verts to no particle */
127         for (i = 0; i < totface; i++)
128                 facepa[i] = totpart;
129
130         for (i = 0; i < totvert; i++)
131                 vertpa[i] = totpart;
132
133         /* set protected verts */
134         if (emd->vgroup) {
135                 MDeformVert *dvert = dm->getVertDataArray(dm, CD_MDEFORMVERT);
136                 if (dvert) {
137                         const int defgrp_index = emd->vgroup - 1;
138                         for (i = 0; i < totvert; i++, dvert++) {
139                                 float val = BLI_frand();
140                                 val = (1.0f - emd->protect) * val + emd->protect * 0.5f;
141                                 if (val < defvert_find_weight(dvert, defgrp_index))
142                                         vertpa[i] = -1;
143                         }
144                 }
145         }
146
147         /* make tree of emitter locations */
148         tree = BLI_kdtree_new(totpart);
149         for (p = 0, pa = psys->particles; p < totpart; p++, pa++) {
150                 psys_particle_on_emitter(psmd, psys->part->from, pa->num, pa->num_dmcache, pa->fuv, pa->foffset, co, NULL, NULL, NULL, NULL, NULL);
151                 BLI_kdtree_insert(tree, p, co, NULL);
152         }
153         BLI_kdtree_balance(tree);
154
155         /* set face-particle-indexes to nearest particle to face center */
156         for (i = 0, fa = mface; i < totface; i++, fa++) {
157                 add_v3_v3v3(center, mvert[fa->v1].co, mvert[fa->v2].co);
158                 add_v3_v3(center, mvert[fa->v3].co);
159                 if (fa->v4) {
160                         add_v3_v3(center, mvert[fa->v4].co);
161                         mul_v3_fl(center, 0.25);
162                 }
163                 else
164                         mul_v3_fl(center, 0.3333f);
165
166                 p = BLI_kdtree_find_nearest(tree, center, NULL, NULL);
167
168                 v1 = vertpa[fa->v1];
169                 v2 = vertpa[fa->v2];
170                 v3 = vertpa[fa->v3];
171                 if (fa->v4)
172                         v4 = vertpa[fa->v4];
173
174                 if (v1 >= 0 && v2 >= 0 && v3 >= 0 && (fa->v4 == 0 || v4 >= 0))
175                         facepa[i] = p;
176
177                 if (v1 >= 0) vertpa[fa->v1] = p;
178                 if (v2 >= 0) vertpa[fa->v2] = p;
179                 if (v3 >= 0) vertpa[fa->v3] = p;
180                 if (fa->v4 && v4 >= 0) vertpa[fa->v4] = p;
181         }
182
183         if (vertpa) MEM_freeN(vertpa);
184         BLI_kdtree_free(tree);
185 }
186
187 static int edgecut_get(EdgeHash *edgehash, unsigned int v1, unsigned int v2)
188 {
189         return GET_INT_FROM_POINTER(BLI_edgehash_lookup(edgehash, v1, v2));
190 }
191
192  
193 static const short add_faces[24] = {
194         0,
195         0, 0, 2, 0, 1, 2, 2, 0, 2, 1,
196         2, 2, 2, 2, 3, 0, 0, 0, 1, 0,
197         1, 1, 2
198 };
199
200 static MFace *get_dface(DerivedMesh *dm, DerivedMesh *split, int cur, int i, MFace *mf)
201 {
202         MFace *df = CDDM_get_tessface(split, cur);
203         DM_copy_tessface_data(dm, split, i, cur, 1);
204         *df = *mf;
205         return df;
206 }
207
208 #define SET_VERTS(a, b, c, d)           \
209         {                                   \
210                 v[0] = mf->v##a; uv[0] = a - 1; \
211                 v[1] = mf->v##b; uv[1] = b - 1; \
212                 v[2] = mf->v##c; uv[2] = c - 1; \
213                 v[3] = mf->v##d; uv[3] = d - 1; \
214         } (void)0
215
216 #define GET_ES(v1, v2) edgecut_get(eh, v1, v2)
217 #define INT_UV(uvf, c0, c1) interp_v2_v2v2(uvf, mf->uv[c0], mf->uv[c1], 0.5f)
218
219 static void remap_faces_3_6_9_12(DerivedMesh *dm, DerivedMesh *split, MFace *mf, int *facepa, int *vertpa, int i, EdgeHash *eh, int cur, int v1, int v2, int v3, int v4)
220 {
221         MFace *df1 = get_dface(dm, split, cur, i, mf);
222         MFace *df2 = get_dface(dm, split, cur + 1, i, mf);
223         MFace *df3 = get_dface(dm, split, cur + 2, i, mf);
224
225         facepa[cur] = vertpa[v1];
226         df1->v1 = v1;
227         df1->v2 = GET_ES(v1, v2);
228         df1->v3 = GET_ES(v2, v3);
229         df1->v4 = v3;
230         df1->flag |= ME_FACE_SEL;
231
232         facepa[cur + 1] = vertpa[v2];
233         df2->v1 = GET_ES(v1, v2);
234         df2->v2 = v2;
235         df2->v3 = GET_ES(v2, v3);
236         df2->v4 = 0;
237         df2->flag &= ~ME_FACE_SEL;
238
239         facepa[cur + 2] = vertpa[v1];
240         df3->v1 = v1;
241         df3->v2 = v3;
242         df3->v3 = v4;
243         df3->v4 = 0;
244         df3->flag &= ~ME_FACE_SEL;
245 }
246
247 static void remap_uvs_3_6_9_12(DerivedMesh *dm, DerivedMesh *split, int numlayer, int i, int cur, int c0, int c1, int c2, int c3)
248 {
249         MTFace *mf, *df1, *df2, *df3;
250         int l;
251
252         for (l = 0; l < numlayer; l++) {
253                 mf = CustomData_get_layer_n(&split->faceData, CD_MTFACE, l);
254                 df1 = mf + cur;
255                 df2 = df1 + 1;
256                 df3 = df1 + 2;
257                 mf = CustomData_get_layer_n(&dm->faceData, CD_MTFACE, l);
258                 mf += i;
259
260                 copy_v2_v2(df1->uv[0], mf->uv[c0]);
261                 INT_UV(df1->uv[1], c0, c1);
262                 INT_UV(df1->uv[2], c1, c2);
263                 copy_v2_v2(df1->uv[3], mf->uv[c2]);
264
265                 INT_UV(df2->uv[0], c0, c1);
266                 copy_v2_v2(df2->uv[1], mf->uv[c1]);
267                 INT_UV(df2->uv[2], c1, c2);
268
269                 copy_v2_v2(df3->uv[0], mf->uv[c0]);
270                 copy_v2_v2(df3->uv[1], mf->uv[c2]);
271                 copy_v2_v2(df3->uv[2], mf->uv[c3]);
272         }
273 }
274
275 static void remap_faces_5_10(DerivedMesh *dm, DerivedMesh *split, MFace *mf, int *facepa, int *vertpa, int i, EdgeHash *eh, int cur, int v1, int v2, int v3, int v4)
276 {
277         MFace *df1 = get_dface(dm, split, cur, i, mf);
278         MFace *df2 = get_dface(dm, split, cur + 1, i, mf);
279
280         facepa[cur] = vertpa[v1];
281         df1->v1 = v1;
282         df1->v2 = v2;
283         df1->v3 = GET_ES(v2, v3);
284         df1->v4 = GET_ES(v1, v4);
285         df1->flag |= ME_FACE_SEL;
286
287         facepa[cur + 1] = vertpa[v3];
288         df2->v1 = GET_ES(v1, v4);
289         df2->v2 = GET_ES(v2, v3);
290         df2->v3 = v3;
291         df2->v4 = v4;
292         df2->flag |= ME_FACE_SEL;
293 }
294
295 static void remap_uvs_5_10(DerivedMesh *dm, DerivedMesh *split, int numlayer, int i, int cur, int c0, int c1, int c2, int c3)
296 {
297         MTFace *mf, *df1, *df2;
298         int l;
299
300         for (l = 0; l < numlayer; l++) {
301                 mf = CustomData_get_layer_n(&split->faceData, CD_MTFACE, l);
302                 df1 = mf + cur;
303                 df2 = df1 + 1;
304                 mf = CustomData_get_layer_n(&dm->faceData, CD_MTFACE, l);
305                 mf += i;
306
307                 copy_v2_v2(df1->uv[0], mf->uv[c0]);
308                 copy_v2_v2(df1->uv[1], mf->uv[c1]);
309                 INT_UV(df1->uv[2], c1, c2);
310                 INT_UV(df1->uv[3], c0, c3);
311
312                 INT_UV(df2->uv[0], c0, c3);
313                 INT_UV(df2->uv[1], c1, c2);
314                 copy_v2_v2(df2->uv[2], mf->uv[c2]);
315                 copy_v2_v2(df2->uv[3], mf->uv[c3]);
316
317         }
318 }
319
320 static void remap_faces_15(DerivedMesh *dm, DerivedMesh *split, MFace *mf, int *facepa, int *vertpa, int i, EdgeHash *eh, int cur, int v1, int v2, int v3, int v4)
321 {
322         MFace *df1 = get_dface(dm, split, cur, i, mf);
323         MFace *df2 = get_dface(dm, split, cur + 1, i, mf);
324         MFace *df3 = get_dface(dm, split, cur + 2, i, mf);
325         MFace *df4 = get_dface(dm, split, cur + 3, i, mf);
326
327         facepa[cur] = vertpa[v1];
328         df1->v1 = v1;
329         df1->v2 = GET_ES(v1, v2);
330         df1->v3 = GET_ES(v1, v3);
331         df1->v4 = GET_ES(v1, v4);
332         df1->flag |= ME_FACE_SEL;
333
334         facepa[cur + 1] = vertpa[v2];
335         df2->v1 = GET_ES(v1, v2);
336         df2->v2 = v2;
337         df2->v3 = GET_ES(v2, v3);
338         df2->v4 = GET_ES(v1, v3);
339         df2->flag |= ME_FACE_SEL;
340
341         facepa[cur + 2] = vertpa[v3];
342         df3->v1 = GET_ES(v1, v3);
343         df3->v2 = GET_ES(v2, v3);
344         df3->v3 = v3;
345         df3->v4 = GET_ES(v3, v4);
346         df3->flag |= ME_FACE_SEL;
347
348         facepa[cur + 3] = vertpa[v4];
349         df4->v1 = GET_ES(v1, v4);
350         df4->v2 = GET_ES(v1, v3);
351         df4->v3 = GET_ES(v3, v4);
352         df4->v4 = v4;
353         df4->flag |= ME_FACE_SEL;
354 }
355
356 static void remap_uvs_15(DerivedMesh *dm, DerivedMesh *split, int numlayer, int i, int cur, int c0, int c1, int c2, int c3)
357 {
358         MTFace *mf, *df1, *df2, *df3, *df4;
359         int l;
360
361         for (l = 0; l < numlayer; l++) {
362                 mf = CustomData_get_layer_n(&split->faceData, CD_MTFACE, l);
363                 df1 = mf + cur;
364                 df2 = df1 + 1;
365                 df3 = df1 + 2;
366                 df4 = df1 + 3;
367                 mf = CustomData_get_layer_n(&dm->faceData, CD_MTFACE, l);
368                 mf += i;
369
370                 copy_v2_v2(df1->uv[0], mf->uv[c0]);
371                 INT_UV(df1->uv[1], c0, c1);
372                 INT_UV(df1->uv[2], c0, c2);
373                 INT_UV(df1->uv[3], c0, c3);
374
375                 INT_UV(df2->uv[0], c0, c1);
376                 copy_v2_v2(df2->uv[1], mf->uv[c1]);
377                 INT_UV(df2->uv[2], c1, c2);
378                 INT_UV(df2->uv[3], c0, c2);
379
380                 INT_UV(df3->uv[0], c0, c2);
381                 INT_UV(df3->uv[1], c1, c2);
382                 copy_v2_v2(df3->uv[2], mf->uv[c2]);
383                 INT_UV(df3->uv[3], c2, c3);
384
385                 INT_UV(df4->uv[0], c0, c3);
386                 INT_UV(df4->uv[1], c0, c2);
387                 INT_UV(df4->uv[2], c2, c3);
388                 copy_v2_v2(df4->uv[3], mf->uv[c3]);
389         }
390 }
391
392 static void remap_faces_7_11_13_14(DerivedMesh *dm, DerivedMesh *split, MFace *mf, int *facepa, int *vertpa, int i, EdgeHash *eh, int cur, int v1, int v2, int v3, int v4)
393 {
394         MFace *df1 = get_dface(dm, split, cur, i, mf);
395         MFace *df2 = get_dface(dm, split, cur + 1, i, mf);
396         MFace *df3 = get_dface(dm, split, cur + 2, i, mf);
397
398         facepa[cur] = vertpa[v1];
399         df1->v1 = v1;
400         df1->v2 = GET_ES(v1, v2);
401         df1->v3 = GET_ES(v2, v3);
402         df1->v4 = GET_ES(v1, v4);
403         df1->flag |= ME_FACE_SEL;
404
405         facepa[cur + 1] = vertpa[v2];
406         df2->v1 = GET_ES(v1, v2);
407         df2->v2 = v2;
408         df2->v3 = GET_ES(v2, v3);
409         df2->v4 = 0;
410         df2->flag &= ~ME_FACE_SEL;
411
412         facepa[cur + 2] = vertpa[v4];
413         df3->v1 = GET_ES(v1, v4);
414         df3->v2 = GET_ES(v2, v3);
415         df3->v3 = v3;
416         df3->v4 = v4;
417         df3->flag |= ME_FACE_SEL;
418 }
419
420 static void remap_uvs_7_11_13_14(DerivedMesh *dm, DerivedMesh *split, int numlayer, int i, int cur, int c0, int c1, int c2, int c3)
421 {
422         MTFace *mf, *df1, *df2, *df3;
423         int l;
424
425         for (l = 0; l < numlayer; l++) {
426                 mf = CustomData_get_layer_n(&split->faceData, CD_MTFACE, l);
427                 df1 = mf + cur;
428                 df2 = df1 + 1;
429                 df3 = df1 + 2;
430                 mf = CustomData_get_layer_n(&dm->faceData, CD_MTFACE, l);
431                 mf += i;
432
433                 copy_v2_v2(df1->uv[0], mf->uv[c0]);
434                 INT_UV(df1->uv[1], c0, c1);
435                 INT_UV(df1->uv[2], c1, c2);
436                 INT_UV(df1->uv[3], c0, c3);
437
438                 INT_UV(df2->uv[0], c0, c1);
439                 copy_v2_v2(df2->uv[1], mf->uv[c1]);
440                 INT_UV(df2->uv[2], c1, c2);
441
442                 INT_UV(df3->uv[0], c0, c3);
443                 INT_UV(df3->uv[1], c1, c2);
444                 copy_v2_v2(df3->uv[2], mf->uv[c2]);
445                 copy_v2_v2(df3->uv[3], mf->uv[c3]);
446         }
447 }
448
449 static void remap_faces_19_21_22(DerivedMesh *dm, DerivedMesh *split, MFace *mf, int *facepa, int *vertpa, int i, EdgeHash *eh, int cur, int v1, int v2, int v3)
450 {
451         MFace *df1 = get_dface(dm, split, cur, i, mf);
452         MFace *df2 = get_dface(dm, split, cur + 1, i, mf);
453
454         facepa[cur] = vertpa[v1];
455         df1->v1 = v1;
456         df1->v2 = GET_ES(v1, v2);
457         df1->v3 = GET_ES(v1, v3);
458         df1->v4 = 0;
459         df1->flag &= ~ME_FACE_SEL;
460
461         facepa[cur + 1] = vertpa[v2];
462         df2->v1 = GET_ES(v1, v2);
463         df2->v2 = v2;
464         df2->v3 = v3;
465         df2->v4 = GET_ES(v1, v3);
466         df2->flag |= ME_FACE_SEL;
467 }
468
469 static void remap_uvs_19_21_22(DerivedMesh *dm, DerivedMesh *split, int numlayer, int i, int cur, int c0, int c1, int c2)
470 {
471         MTFace *mf, *df1, *df2;
472         int l;
473
474         for (l = 0; l < numlayer; l++) {
475                 mf = CustomData_get_layer_n(&split->faceData, CD_MTFACE, l);
476                 df1 = mf + cur;
477                 df2 = df1 + 1;
478                 mf = CustomData_get_layer_n(&dm->faceData, CD_MTFACE, l);
479                 mf += i;
480
481                 copy_v2_v2(df1->uv[0], mf->uv[c0]);
482                 INT_UV(df1->uv[1], c0, c1);
483                 INT_UV(df1->uv[2], c0, c2);
484
485                 INT_UV(df2->uv[0], c0, c1);
486                 copy_v2_v2(df2->uv[1], mf->uv[c1]);
487                 copy_v2_v2(df2->uv[2], mf->uv[c2]);
488                 INT_UV(df2->uv[3], c0, c2);
489         }
490 }
491
492 static void remap_faces_23(DerivedMesh *dm, DerivedMesh *split, MFace *mf, int *facepa, int *vertpa, int i, EdgeHash *eh, int cur, int v1, int v2, int v3)
493 {
494         MFace *df1 = get_dface(dm, split, cur, i, mf);
495         MFace *df2 = get_dface(dm, split, cur + 1, i, mf);
496         MFace *df3 = get_dface(dm, split, cur + 2, i, mf);
497
498         facepa[cur] = vertpa[v1];
499         df1->v1 = v1;
500         df1->v2 = GET_ES(v1, v2);
501         df1->v3 = GET_ES(v2, v3);
502         df1->v4 = GET_ES(v1, v3);
503         df1->flag |= ME_FACE_SEL;
504
505         facepa[cur + 1] = vertpa[v2];
506         df2->v1 = GET_ES(v1, v2);
507         df2->v2 = v2;
508         df2->v3 = GET_ES(v2, v3);
509         df2->v4 = 0;
510         df2->flag &= ~ME_FACE_SEL;
511
512         facepa[cur + 2] = vertpa[v3];
513         df3->v1 = GET_ES(v1, v3);
514         df3->v2 = GET_ES(v2, v3);
515         df3->v3 = v3;
516         df3->v4 = 0;
517         df3->flag &= ~ME_FACE_SEL;
518 }
519
520 static void remap_uvs_23(DerivedMesh *dm, DerivedMesh *split, int numlayer, int i, int cur, int c0, int c1, int c2)
521 {
522         MTFace *mf, *df1, *df2;
523         int l;
524
525         for (l = 0; l < numlayer; l++) {
526                 mf = CustomData_get_layer_n(&split->faceData, CD_MTFACE, l);
527                 df1 = mf + cur;
528                 df2 = df1 + 1;
529                 mf = CustomData_get_layer_n(&dm->faceData, CD_MTFACE, l);
530                 mf += i;
531
532                 copy_v2_v2(df1->uv[0], mf->uv[c0]);
533                 INT_UV(df1->uv[1], c0, c1);
534                 INT_UV(df1->uv[2], c1, c2);
535                 INT_UV(df1->uv[3], c0, c2);
536
537                 INT_UV(df2->uv[0], c0, c1);
538                 copy_v2_v2(df2->uv[1], mf->uv[c1]);
539                 INT_UV(df2->uv[2], c1, c2);
540
541                 INT_UV(df2->uv[0], c0, c2);
542                 INT_UV(df2->uv[1], c1, c2);
543                 copy_v2_v2(df2->uv[2], mf->uv[c2]);
544         }
545 }
546
547 static DerivedMesh *cutEdges(ExplodeModifierData *emd, DerivedMesh *dm)
548 {
549         DerivedMesh *splitdm;
550         MFace *mf = NULL, *df1 = NULL;
551         MFace *mface = dm->getTessFaceArray(dm);
552         MVert *dupve, *mv;
553         EdgeHash *edgehash;
554         EdgeHashIterator *ehi;
555         int totvert = dm->getNumVerts(dm);
556         int totface = dm->getNumTessFaces(dm);
557
558         int *facesplit = MEM_callocN(sizeof(int) * totface, "explode_facesplit");
559         int *vertpa = MEM_callocN(sizeof(int) * totvert, "explode_vertpa2");
560         int *facepa = emd->facepa;
561         int *fs, totesplit = 0, totfsplit = 0, curdupface = 0;
562         int i, v1, v2, v3, v4, esplit,
563             v[4]  = {0, 0, 0, 0}, /* To quite gcc barking... */
564             uv[4] = {0, 0, 0, 0}; /* To quite gcc barking... */
565         int numlayer;
566         unsigned int ed_v1, ed_v2;
567
568         edgehash = BLI_edgehash_new();
569
570         /* recreate vertpa from facepa calculation */
571         for (i = 0, mf = mface; i < totface; i++, mf++) {
572                 vertpa[mf->v1] = facepa[i];
573                 vertpa[mf->v2] = facepa[i];
574                 vertpa[mf->v3] = facepa[i];
575                 if (mf->v4)
576                         vertpa[mf->v4] = facepa[i];
577         }
578
579         /* mark edges for splitting and how to split faces */
580         for (i = 0, mf = mface, fs = facesplit; i < totface; i++, mf++, fs++) {
581                 v1 = vertpa[mf->v1];
582                 v2 = vertpa[mf->v2];
583                 v3 = vertpa[mf->v3];
584
585                 if (v1 != v2) {
586                         BLI_edgehash_insert(edgehash, mf->v1, mf->v2, NULL);
587                         (*fs) |= 1;
588                 }
589
590                 if (v2 != v3) {
591                         BLI_edgehash_insert(edgehash, mf->v2, mf->v3, NULL);
592                         (*fs) |= 2;
593                 }
594
595                 if (mf->v4) {
596                         v4 = vertpa[mf->v4];
597
598                         if (v3 != v4) {
599                                 BLI_edgehash_insert(edgehash, mf->v3, mf->v4, NULL);
600                                 (*fs) |= 4;
601                         }
602
603                         if (v1 != v4) {
604                                 BLI_edgehash_insert(edgehash, mf->v1, mf->v4, NULL);
605                                 (*fs) |= 8;
606                         }
607
608                         /* mark center vertex as a fake edge split */
609                         if (*fs == 15)
610                                 BLI_edgehash_insert(edgehash, mf->v1, mf->v3, NULL);
611                 }
612                 else {
613                         (*fs) |= 16; /* mark face as tri */
614
615                         if (v1 != v3) {
616                                 BLI_edgehash_insert(edgehash, mf->v1, mf->v3, NULL);
617                                 (*fs) |= 4;
618                         }
619                 }
620         }
621
622         /* count splits & create indexes for new verts */
623         ehi = BLI_edgehashIterator_new(edgehash);
624         totesplit = totvert;
625         for (; !BLI_edgehashIterator_isDone(ehi); BLI_edgehashIterator_step(ehi)) {
626                 BLI_edgehashIterator_setValue(ehi, SET_INT_IN_POINTER(totesplit));
627                 totesplit++;
628         }
629         BLI_edgehashIterator_free(ehi);
630
631         /* count new faces due to splitting */
632         for (i = 0, fs = facesplit; i < totface; i++, fs++)
633                 totfsplit += add_faces[*fs];
634         
635         splitdm = CDDM_from_template(dm, totesplit, 0, totface + totfsplit, 0, 0);
636         numlayer = CustomData_number_of_layers(&splitdm->faceData, CD_MTFACE);
637
638         /* copy new faces & verts (is it really this painful with custom data??) */
639         for (i = 0; i < totvert; i++) {
640                 MVert source;
641                 MVert *dest;
642                 dm->getVert(dm, i, &source);
643                 dest = CDDM_get_vert(splitdm, i);
644
645                 DM_copy_vert_data(dm, splitdm, i, i, 1);
646                 *dest = source;
647         }
648
649         /* override original facepa (original pointer is saved in caller function) */
650
651         /* BMESH_TODO, (totfsplit * 2) over allocation is used since the quads are
652          * later interpreted as tri's, for this to work right I think we probably
653          * have to stop using tessface - campbell */
654
655         facepa = MEM_callocN(sizeof(int) * (totface + (totfsplit * 2)), "explode_facepa");
656         //memcpy(facepa, emd->facepa, totface*sizeof(int));
657         emd->facepa = facepa;
658
659         /* create new verts */
660         ehi = BLI_edgehashIterator_new(edgehash);
661         for (; !BLI_edgehashIterator_isDone(ehi); BLI_edgehashIterator_step(ehi)) {
662                 BLI_edgehashIterator_getKey(ehi, &ed_v1, &ed_v2);
663                 esplit = GET_INT_FROM_POINTER(BLI_edgehashIterator_getValue(ehi));
664                 mv = CDDM_get_vert(splitdm, ed_v2);
665                 dupve = CDDM_get_vert(splitdm, esplit);
666
667                 DM_copy_vert_data(splitdm, splitdm, ed_v2, esplit, 1);
668
669                 *dupve = *mv;
670
671                 mv = CDDM_get_vert(splitdm, ed_v1);
672
673                 mid_v3_v3v3(dupve->co, dupve->co, mv->co);
674         }
675         BLI_edgehashIterator_free(ehi);
676
677         /* create new faces */
678         curdupface = 0; //=totface;
679         //curdupin=totesplit;
680         for (i = 0, fs = facesplit; i < totface; i++, fs++) {
681                 mf = dm->getTessFaceData(dm, i, CD_MFACE);
682
683                 switch (*fs) {
684                         case 3:
685                         case 10:
686                         case 11:
687                         case 15:
688                                 SET_VERTS(1, 2, 3, 4);
689                                 break;
690                         case 5:
691                         case 6:
692                         case 7:
693                                 SET_VERTS(2, 3, 4, 1);
694                                 break;
695                         case 9:
696                         case 13:
697                                 SET_VERTS(4, 1, 2, 3);
698                                 break;
699                         case 12:
700                         case 14:
701                                 SET_VERTS(3, 4, 1, 2);
702                                 break;
703                         case 21:
704                         case 23:
705                                 SET_VERTS(1, 2, 3, 4);
706                                 break;
707                         case 19:
708                                 SET_VERTS(2, 3, 1, 4);
709                                 break;
710                         case 22:
711                                 SET_VERTS(3, 1, 2, 4);
712                                 break;
713                 }
714
715                 switch (*fs) {
716                         case 3:
717                         case 6:
718                         case 9:
719                         case 12:
720                                 remap_faces_3_6_9_12(dm, splitdm, mf, facepa, vertpa, i, edgehash, curdupface, v[0], v[1], v[2], v[3]);
721                                 if (numlayer)
722                                         remap_uvs_3_6_9_12(dm, splitdm, numlayer, i, curdupface, uv[0], uv[1], uv[2], uv[3]);
723                                 break;
724                         case 5:
725                         case 10:
726                                 remap_faces_5_10(dm, splitdm, mf, facepa, vertpa, i, edgehash, curdupface, v[0], v[1], v[2], v[3]);
727                                 if (numlayer)
728                                         remap_uvs_5_10(dm, splitdm, numlayer, i, curdupface, uv[0], uv[1], uv[2], uv[3]);
729                                 break;
730                         case 15:
731                                 remap_faces_15(dm, splitdm, mf, facepa, vertpa, i, edgehash, curdupface, v[0], v[1], v[2], v[3]);
732                                 if (numlayer)
733                                         remap_uvs_15(dm, splitdm, numlayer, i, curdupface, uv[0], uv[1], uv[2], uv[3]);
734                                 break;
735                         case 7:
736                         case 11:
737                         case 13:
738                         case 14:
739                                 remap_faces_7_11_13_14(dm, splitdm, mf, facepa, vertpa, i, edgehash, curdupface, v[0], v[1], v[2], v[3]);
740                                 if (numlayer)
741                                         remap_uvs_7_11_13_14(dm, splitdm, numlayer, i, curdupface, uv[0], uv[1], uv[2], uv[3]);
742                                 break;
743                         case 19:
744                         case 21:
745                         case 22:
746                                 remap_faces_19_21_22(dm, splitdm, mf, facepa, vertpa, i, edgehash, curdupface, v[0], v[1], v[2]);
747                                 if (numlayer)
748                                         remap_uvs_19_21_22(dm, splitdm, numlayer, i, curdupface, uv[0], uv[1], uv[2]);
749                                 break;
750                         case 23:
751                                 remap_faces_23(dm, splitdm, mf, facepa, vertpa, i, edgehash, curdupface, v[0], v[1], v[2]);
752                                 if (numlayer)
753                                         remap_uvs_23(dm, splitdm, numlayer, i, curdupface, uv[0], uv[1], uv[2]);
754                                 break;
755                         case 0:
756                         case 16:
757                                 df1 = get_dface(dm, splitdm, curdupface, i, mf);
758                                 facepa[curdupface] = vertpa[mf->v1];
759
760                                 if (df1->v4)
761                                         df1->flag |= ME_FACE_SEL;
762                                 else
763                                         df1->flag &= ~ME_FACE_SEL;
764                                 break;
765                 }
766
767                 curdupface += add_faces[*fs] + 1;
768         }
769
770         for (i = 0; i < curdupface; i++) {
771                 mf = CDDM_get_tessface(splitdm, i);
772                 test_index_face(mf, &splitdm->faceData, i, (mf->flag & ME_FACE_SEL ? 4 : 3));
773         }
774
775         BLI_edgehash_free(edgehash, NULL);
776         MEM_freeN(facesplit);
777         MEM_freeN(vertpa);
778
779         CDDM_calc_edges_tessface(splitdm);
780         CDDM_tessfaces_to_faces(splitdm); /*builds ngon faces from tess (mface) faces*/
781
782         return splitdm;
783 }
784 static DerivedMesh *explodeMesh(ExplodeModifierData *emd,
785                                 ParticleSystemModifierData *psmd, Scene *scene, Object *ob,
786                                 DerivedMesh *to_explode)
787 {
788         DerivedMesh *explode, *dm = to_explode;
789         MFace *mf = NULL, *mface;
790         /* ParticleSettings *part=psmd->psys->part; */ /* UNUSED */
791         ParticleSimulationData sim = {NULL};
792         ParticleData *pa = NULL, *pars = psmd->psys->particles;
793         ParticleKey state, birth;
794         EdgeHash *vertpahash;
795         EdgeHashIterator *ehi;
796         float *vertco = NULL, imat[4][4];
797         float rot[4];
798         float cfra;
799         /* float timestep; */
800         int *facepa = emd->facepa;
801         int totdup = 0, totvert = 0, totface = 0, totpart = 0, delface = 0;
802         int i, v, u;
803         unsigned int ed_v1, ed_v2, mindex = 0;
804         MTFace *mtface = NULL, *mtf;
805
806         totface = dm->getNumTessFaces(dm);
807         totvert = dm->getNumVerts(dm);
808         mface = dm->getTessFaceArray(dm);
809         totpart = psmd->psys->totpart;
810
811         sim.scene = scene;
812         sim.ob = ob;
813         sim.psys = psmd->psys;
814         sim.psmd = psmd;
815
816         /* timestep = psys_get_timestep(&sim); */
817
818         cfra = BKE_scene_frame_get(scene);
819
820         /* hash table for vertice <-> particle relations */
821         vertpahash = BLI_edgehash_new();
822
823         for (i = 0; i < totface; i++) {
824                 if (facepa[i] != totpart) {
825                         pa = pars + facepa[i];
826
827                         if ((pa->alive == PARS_UNBORN && (emd->flag & eExplodeFlag_Unborn) == 0) ||
828                             (pa->alive == PARS_ALIVE && (emd->flag & eExplodeFlag_Alive) == 0) ||
829                             (pa->alive == PARS_DEAD && (emd->flag & eExplodeFlag_Dead) == 0))
830                         {
831                                 delface++;
832                                 continue;
833                         }
834                 }
835
836                 /* do mindex + totvert to ensure the vertex index to be the first
837                  * with BLI_edgehashIterator_getKey */
838                 if (facepa[i] == totpart || cfra < (pars + facepa[i])->time)
839                         mindex = totvert + totpart;
840                 else 
841                         mindex = totvert + facepa[i];
842
843                 mf = &mface[i];
844
845                 /* set face vertices to exist in particle group */
846                 BLI_edgehash_insert(vertpahash, mf->v1, mindex, NULL);
847                 BLI_edgehash_insert(vertpahash, mf->v2, mindex, NULL);
848                 BLI_edgehash_insert(vertpahash, mf->v3, mindex, NULL);
849                 if (mf->v4)
850                         BLI_edgehash_insert(vertpahash, mf->v4, mindex, NULL);
851         }
852
853         /* make new vertice indexes & count total vertices after duplication */
854         ehi = BLI_edgehashIterator_new(vertpahash);
855         for (; !BLI_edgehashIterator_isDone(ehi); BLI_edgehashIterator_step(ehi)) {
856                 BLI_edgehashIterator_setValue(ehi, SET_INT_IN_POINTER(totdup));
857                 totdup++;
858         }
859         BLI_edgehashIterator_free(ehi);
860
861         /* the final duplicated vertices */
862         explode = CDDM_from_template(dm, totdup, 0, totface - delface, 0, 0);
863         mtface = CustomData_get_layer_named(&explode->faceData, CD_MTFACE, emd->uvname);
864         /*dupvert = CDDM_get_verts(explode);*/
865
866         /* getting back to object space */
867         invert_m4_m4(imat, ob->obmat);
868
869         psmd->psys->lattice = psys_get_lattice(&sim);
870
871         /* duplicate & displace vertices */
872         ehi = BLI_edgehashIterator_new(vertpahash);
873         for (; !BLI_edgehashIterator_isDone(ehi); BLI_edgehashIterator_step(ehi)) {
874                 MVert source;
875                 MVert *dest;
876
877                 /* get particle + vertex from hash */
878                 BLI_edgehashIterator_getKey(ehi, &ed_v1, &ed_v2);
879                 ed_v2 -= totvert;
880                 v = GET_INT_FROM_POINTER(BLI_edgehashIterator_getValue(ehi));
881
882                 dm->getVert(dm, ed_v1, &source);
883                 dest = CDDM_get_vert(explode, v);
884
885                 DM_copy_vert_data(dm, explode, ed_v1, v, 1);
886                 *dest = source;
887
888                 if (ed_v2 != totpart) {
889                         /* get particle */
890                         pa = pars + ed_v2;
891
892                         psys_get_birth_coordinates(&sim, pa, &birth, 0, 0);
893
894                         state.time = cfra;
895                         psys_get_particle_state(&sim, ed_v2, &state, 1);
896
897                         vertco = CDDM_get_vert(explode, v)->co;
898                         mul_m4_v3(ob->obmat, vertco);
899
900                         sub_v3_v3(vertco, birth.co);
901
902                         /* apply rotation, size & location */
903                         sub_qt_qtqt(rot, state.rot, birth.rot);
904                         mul_qt_v3(rot, vertco);
905
906                         if (emd->flag & eExplodeFlag_PaSize)
907                                 mul_v3_fl(vertco, pa->size);
908
909                         add_v3_v3(vertco, state.co);
910
911                         mul_m4_v3(imat, vertco);
912                 }
913         }
914         BLI_edgehashIterator_free(ehi);
915
916         /*map new vertices to faces*/
917         for (i = 0, u = 0; i < totface; i++) {
918                 MFace source;
919                 int orig_v4;
920
921                 if (facepa[i] != totpart) {
922                         pa = pars + facepa[i];
923
924                         if (pa->alive == PARS_UNBORN && (emd->flag & eExplodeFlag_Unborn) == 0) continue;
925                         if (pa->alive == PARS_ALIVE && (emd->flag & eExplodeFlag_Alive) == 0) continue;
926                         if (pa->alive == PARS_DEAD && (emd->flag & eExplodeFlag_Dead) == 0) continue;
927                 }
928
929                 dm->getTessFace(dm, i, &source);
930                 mf = CDDM_get_tessface(explode, u);
931                 
932                 orig_v4 = source.v4;
933
934                 if (facepa[i] != totpart && cfra < pa->time)
935                         mindex = totvert + totpart;
936                 else 
937                         mindex = totvert + facepa[i];
938
939                 source.v1 = edgecut_get(vertpahash, source.v1, mindex);
940                 source.v2 = edgecut_get(vertpahash, source.v2, mindex);
941                 source.v3 = edgecut_get(vertpahash, source.v3, mindex);
942                 if (source.v4)
943                         source.v4 = edgecut_get(vertpahash, source.v4, mindex);
944
945                 DM_copy_tessface_data(dm, explode, i, u, 1);
946
947                 *mf = source;
948
949                 /* override uv channel for particle age */
950                 if (mtface) {
951                         float age = (cfra - pa->time) / pa->lifetime;
952                         /* Clamp to this range to avoid flipping to the other side of the coordinates. */
953                         CLAMP(age, 0.001f, 0.999f);
954
955                         mtf = mtface + u;
956
957                         mtf->uv[0][0] = mtf->uv[1][0] = mtf->uv[2][0] = mtf->uv[3][0] = age;
958                         mtf->uv[0][1] = mtf->uv[1][1] = mtf->uv[2][1] = mtf->uv[3][1] = 0.5f;
959                 }
960
961                 test_index_face(mf, &explode->faceData, u, (orig_v4 ? 4 : 3));
962                 u++;
963         }
964
965         /* cleanup */
966         BLI_edgehash_free(vertpahash, NULL);
967
968         /* finalization */
969         CDDM_calc_edges_tessface(explode);
970         CDDM_tessfaces_to_faces(explode);
971         CDDM_calc_normals(explode);
972
973         if (psmd->psys->lattice) {
974                 end_latt_deform(psmd->psys->lattice);
975                 psmd->psys->lattice = NULL;
976         }
977
978         return explode;
979 }
980
981 static ParticleSystemModifierData *findPrecedingParticlesystem(Object *ob, ModifierData *emd)
982 {
983         ModifierData *md;
984         ParticleSystemModifierData *psmd = NULL;
985
986         for (md = ob->modifiers.first; emd != md; md = md->next) {
987                 if (md->type == eModifierType_ParticleSystem)
988                         psmd = (ParticleSystemModifierData *) md;
989         }
990         return psmd;
991 }
992 static DerivedMesh *applyModifier(ModifierData *md, Object *ob,
993                                   DerivedMesh *derivedData,
994                                   ModifierApplyFlag UNUSED(flag))
995 {
996         DerivedMesh *dm = derivedData;
997         ExplodeModifierData *emd = (ExplodeModifierData *) md;
998         ParticleSystemModifierData *psmd = findPrecedingParticlesystem(ob, md);
999
1000         DM_ensure_tessface(dm); /* BMESH - UNTIL MODIFIER IS UPDATED FOR MPoly */
1001
1002         if (psmd) {
1003                 ParticleSystem *psys = psmd->psys;
1004
1005                 if (psys == NULL || psys->totpart == 0) return derivedData;
1006                 if (psys->part == NULL || psys->particles == NULL) return derivedData;
1007                 if (psmd->dm == NULL) return derivedData;
1008
1009                 /* 1. find faces to be exploded if needed */
1010                 if (emd->facepa == NULL ||
1011                     psmd->flag & eParticleSystemFlag_Pars ||
1012                     emd->flag & eExplodeFlag_CalcFaces ||
1013                     MEM_allocN_len(emd->facepa) / sizeof(int) != dm->getNumTessFaces(dm))
1014                 {
1015                         if (psmd->flag & eParticleSystemFlag_Pars)
1016                                 psmd->flag &= ~eParticleSystemFlag_Pars;
1017                         
1018                         if (emd->flag & eExplodeFlag_CalcFaces)
1019                                 emd->flag &= ~eExplodeFlag_CalcFaces;
1020
1021                         createFacepa(emd, psmd, derivedData);
1022                 }
1023                 /* 2. create new mesh */
1024                 if (emd->flag & eExplodeFlag_EdgeCut) {
1025                         int *facepa = emd->facepa;
1026                         DerivedMesh *splitdm = cutEdges(emd, dm);
1027                         DerivedMesh *explode = explodeMesh(emd, psmd, md->scene, ob, splitdm);
1028
1029                         MEM_freeN(emd->facepa);
1030                         emd->facepa = facepa;
1031                         splitdm->release(splitdm);
1032                         return explode;
1033                 }
1034                 else
1035                         return explodeMesh(emd, psmd, md->scene, ob, derivedData);
1036         }
1037         return derivedData;
1038 }
1039
1040
1041 ModifierTypeInfo modifierType_Explode = {
1042         /* name */              "Explode",
1043         /* structName */        "ExplodeModifierData",
1044         /* structSize */        sizeof(ExplodeModifierData),
1045         /* type */              eModifierTypeType_Constructive,
1046         /* flags */             eModifierTypeFlag_AcceptsMesh,
1047         /* copyData */          copyData,
1048         /* deformVerts */       NULL,
1049         /* deformMatrices */    NULL,
1050         /* deformVertsEM */     NULL,
1051         /* deformMatricesEM */  NULL,
1052         /* applyModifier */     applyModifier,
1053         /* applyModifierEM */   NULL,
1054         /* initData */          initData,
1055         /* requiredDataMask */  requiredDataMask,
1056         /* freeData */          freeData,
1057         /* isDisabled */        NULL,
1058         /* updateDepgraph */    NULL,
1059         /* dependsOnTime */     dependsOnTime,
1060         /* dependsOnNormals */  NULL,
1061         /* foreachObjectLink */ NULL,
1062         /* foreachIDLink */     NULL,
1063         /* foreachTexLink */    NULL,
1064 };