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