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