Fix T47038: Particles in Particle Edit Mode get added in completely wrong location.
[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
55 #include "MEM_guardedalloc.h"
56
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_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_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_callocN(sizeof(int) * totface, "explode_facesplit");
561         int *vertpa = MEM_callocN(sizeof(int) * totvert, "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(dm, totesplit, 0, totface + totfsplit, 0, 0);
638         numlayer = CustomData_number_of_layers(&splitdm->faceData, CD_MTFACE);
639
640         /* copy new faces & verts (is it really this painful with custom data??) */
641         for (i = 0; i < totvert; i++) {
642                 MVert source;
643                 MVert *dest;
644                 dm->getVert(dm, i, &source);
645                 dest = CDDM_get_vert(splitdm, i);
646
647                 DM_copy_vert_data(dm, splitdm, i, i, 1);
648                 *dest = source;
649         }
650
651         /* override original facepa (original pointer is saved in caller function) */
652
653         /* BMESH_TODO, (totfsplit * 2) over allocation is used since the quads are
654          * later interpreted as tri's, for this to work right I think we probably
655          * have to stop using tessface - campbell */
656
657         facepa = MEM_callocN(sizeof(int) * (totface + (totfsplit * 2)), "explode_facepa");
658         //memcpy(facepa, emd->facepa, totface*sizeof(int));
659         emd->facepa = facepa;
660
661         /* create new verts */
662         ehi = BLI_edgehashIterator_new(edgehash);
663         for (; !BLI_edgehashIterator_isDone(ehi); BLI_edgehashIterator_step(ehi)) {
664                 BLI_edgehashIterator_getKey(ehi, &ed_v1, &ed_v2);
665                 esplit = GET_INT_FROM_POINTER(BLI_edgehashIterator_getValue(ehi));
666                 mv = CDDM_get_vert(splitdm, ed_v2);
667                 dupve = CDDM_get_vert(splitdm, esplit);
668
669                 DM_copy_vert_data(splitdm, splitdm, ed_v2, esplit, 1);
670
671                 *dupve = *mv;
672
673                 mv = CDDM_get_vert(splitdm, ed_v1);
674
675                 mid_v3_v3v3(dupve->co, dupve->co, mv->co);
676         }
677         BLI_edgehashIterator_free(ehi);
678
679         /* create new faces */
680         curdupface = 0; //=totface;
681         //curdupin=totesplit;
682         for (i = 0, fs = facesplit; i < totface; i++, fs++) {
683                 mf = dm->getTessFaceData(dm, i, CD_MFACE);
684
685                 switch (*fs) {
686                         case 3:
687                         case 10:
688                         case 11:
689                         case 15:
690                                 SET_VERTS(1, 2, 3, 4);
691                                 break;
692                         case 5:
693                         case 6:
694                         case 7:
695                                 SET_VERTS(2, 3, 4, 1);
696                                 break;
697                         case 9:
698                         case 13:
699                                 SET_VERTS(4, 1, 2, 3);
700                                 break;
701                         case 12:
702                         case 14:
703                                 SET_VERTS(3, 4, 1, 2);
704                                 break;
705                         case 21:
706                         case 23:
707                                 SET_VERTS(1, 2, 3, 4);
708                                 break;
709                         case 19:
710                                 SET_VERTS(2, 3, 1, 4);
711                                 break;
712                         case 22:
713                                 SET_VERTS(3, 1, 2, 4);
714                                 break;
715                 }
716
717                 switch (*fs) {
718                         case 3:
719                         case 6:
720                         case 9:
721                         case 12:
722                                 remap_faces_3_6_9_12(dm, splitdm, mf, facepa, vertpa, i, edgehash, curdupface, v[0], v[1], v[2], v[3]);
723                                 if (numlayer)
724                                         remap_uvs_3_6_9_12(dm, splitdm, numlayer, i, curdupface, uv[0], uv[1], uv[2], uv[3]);
725                                 break;
726                         case 5:
727                         case 10:
728                                 remap_faces_5_10(dm, splitdm, mf, facepa, vertpa, i, edgehash, curdupface, v[0], v[1], v[2], v[3]);
729                                 if (numlayer)
730                                         remap_uvs_5_10(dm, splitdm, numlayer, i, curdupface, uv[0], uv[1], uv[2], uv[3]);
731                                 break;
732                         case 15:
733                                 remap_faces_15(dm, splitdm, mf, facepa, vertpa, i, edgehash, curdupface, v[0], v[1], v[2], v[3]);
734                                 if (numlayer)
735                                         remap_uvs_15(dm, splitdm, numlayer, i, curdupface, uv[0], uv[1], uv[2], uv[3]);
736                                 break;
737                         case 7:
738                         case 11:
739                         case 13:
740                         case 14:
741                                 remap_faces_7_11_13_14(dm, splitdm, mf, facepa, vertpa, i, edgehash, curdupface, v[0], v[1], v[2], v[3]);
742                                 if (numlayer)
743                                         remap_uvs_7_11_13_14(dm, splitdm, numlayer, i, curdupface, uv[0], uv[1], uv[2], uv[3]);
744                                 break;
745                         case 19:
746                         case 21:
747                         case 22:
748                                 remap_faces_19_21_22(dm, splitdm, mf, facepa, vertpa, i, edgehash, curdupface, v[0], v[1], v[2]);
749                                 if (numlayer)
750                                         remap_uvs_19_21_22(dm, splitdm, numlayer, i, curdupface, uv[0], uv[1], uv[2]);
751                                 break;
752                         case 23:
753                                 remap_faces_23(dm, splitdm, mf, facepa, vertpa, i, edgehash, curdupface, v[0], v[1], v[2]);
754                                 if (numlayer)
755                                         remap_uvs_23(dm, splitdm, numlayer, i, curdupface, uv[0], uv[1], uv[2]);
756                                 break;
757                         case 0:
758                         case 16:
759                                 df1 = get_dface(dm, splitdm, curdupface, i, mf);
760                                 facepa[curdupface] = vertpa[mf->v1];
761
762                                 if (df1->v4)
763                                         df1->flag |= ME_FACE_SEL;
764                                 else
765                                         df1->flag &= ~ME_FACE_SEL;
766                                 break;
767                 }
768
769                 curdupface += add_faces[*fs] + 1;
770         }
771
772         for (i = 0; i < curdupface; i++) {
773                 mf = CDDM_get_tessface(splitdm, i);
774                 test_index_face(mf, &splitdm->faceData, i, ((mf->flag & ME_FACE_SEL) ? 4 : 3));
775         }
776
777         BLI_edgehash_free(edgehash, NULL);
778         MEM_freeN(facesplit);
779         MEM_freeN(vertpa);
780
781         CDDM_calc_edges_tessface(splitdm);
782         CDDM_tessfaces_to_faces(splitdm); /*builds ngon faces from tess (mface) faces*/
783
784         return splitdm;
785 }
786 static DerivedMesh *explodeMesh(ExplodeModifierData *emd,
787                                 ParticleSystemModifierData *psmd, Scene *scene, Object *ob,
788                                 DerivedMesh *to_explode)
789 {
790         DerivedMesh *explode, *dm = to_explode;
791         MFace *mf = NULL, *mface;
792         /* ParticleSettings *part=psmd->psys->part; */ /* UNUSED */
793         ParticleSimulationData sim = {NULL};
794         ParticleData *pa = NULL, *pars = psmd->psys->particles;
795         ParticleKey state, birth;
796         EdgeHash *vertpahash;
797         EdgeHashIterator *ehi;
798         float *vertco = NULL, imat[4][4];
799         float rot[4];
800         float cfra;
801         /* float timestep; */
802         const int *facepa = emd->facepa;
803         int totdup = 0, totvert = 0, totface = 0, totpart = 0, delface = 0;
804         int i, v, u;
805         unsigned int ed_v1, ed_v2, mindex = 0;
806         MTFace *mtface = NULL, *mtf;
807
808         totface = dm->getNumTessFaces(dm);
809         totvert = dm->getNumVerts(dm);
810         mface = dm->getTessFaceArray(dm);
811         totpart = psmd->psys->totpart;
812
813         sim.scene = scene;
814         sim.ob = ob;
815         sim.psys = psmd->psys;
816         sim.psmd = psmd;
817
818         /* timestep = psys_get_timestep(&sim); */
819
820         cfra = BKE_scene_frame_get(scene);
821
822         /* hash table for vertice <-> particle relations */
823         vertpahash = BLI_edgehash_new(__func__);
824
825         for (i = 0; i < totface; i++) {
826                 if (facepa[i] != totpart) {
827                         pa = pars + facepa[i];
828
829                         if ((pa->alive == PARS_UNBORN && (emd->flag & eExplodeFlag_Unborn) == 0) ||
830                             (pa->alive == PARS_ALIVE && (emd->flag & eExplodeFlag_Alive) == 0) ||
831                             (pa->alive == PARS_DEAD && (emd->flag & eExplodeFlag_Dead) == 0))
832                         {
833                                 delface++;
834                                 continue;
835                         }
836                 }
837
838                 /* do mindex + totvert to ensure the vertex index to be the first
839                  * with BLI_edgehashIterator_getKey */
840                 if (facepa[i] == totpart || cfra < (pars + facepa[i])->time)
841                         mindex = totvert + totpart;
842                 else 
843                         mindex = totvert + facepa[i];
844
845                 mf = &mface[i];
846
847                 /* set face vertices to exist in particle group */
848                 BLI_edgehash_reinsert(vertpahash, mf->v1, mindex, NULL);
849                 BLI_edgehash_reinsert(vertpahash, mf->v2, mindex, NULL);
850                 BLI_edgehash_reinsert(vertpahash, mf->v3, mindex, NULL);
851                 if (mf->v4)
852                         BLI_edgehash_reinsert(vertpahash, mf->v4, mindex, NULL);
853         }
854
855         /* make new vertice indexes & count total vertices after duplication */
856         ehi = BLI_edgehashIterator_new(vertpahash);
857         for (; !BLI_edgehashIterator_isDone(ehi); BLI_edgehashIterator_step(ehi)) {
858                 BLI_edgehashIterator_setValue(ehi, SET_INT_IN_POINTER(totdup));
859                 totdup++;
860         }
861         BLI_edgehashIterator_free(ehi);
862
863         /* the final duplicated vertices */
864         explode = CDDM_from_template_ex(dm, totdup, 0, totface - delface, 0, 0, CD_MASK_DERIVEDMESH | CD_MASK_FACECORNERS);
865         mtface = CustomData_get_layer_named(&explode->faceData, CD_MTFACE, emd->uvname);
866         /*dupvert = CDDM_get_verts(explode);*/
867
868         /* getting back to object space */
869         invert_m4_m4(imat, ob->obmat);
870
871         psmd->psys->lattice_deform_data = psys_create_lattice_deform_data(&sim);
872
873         /* duplicate & displace vertices */
874         ehi = BLI_edgehashIterator_new(vertpahash);
875         for (; !BLI_edgehashIterator_isDone(ehi); BLI_edgehashIterator_step(ehi)) {
876                 MVert source;
877                 MVert *dest;
878
879                 /* get particle + vertex from hash */
880                 BLI_edgehashIterator_getKey(ehi, &ed_v1, &ed_v2);
881                 ed_v2 -= totvert;
882                 v = GET_INT_FROM_POINTER(BLI_edgehashIterator_getValue(ehi));
883
884                 dm->getVert(dm, ed_v1, &source);
885                 dest = CDDM_get_vert(explode, v);
886
887                 DM_copy_vert_data(dm, explode, ed_v1, v, 1);
888                 *dest = source;
889
890                 if (ed_v2 != totpart) {
891                         /* get particle */
892                         pa = pars + ed_v2;
893
894                         psys_get_birth_coords(&sim, pa, &birth, 0, 0);
895
896                         state.time = cfra;
897                         psys_get_particle_state(&sim, ed_v2, &state, 1);
898
899                         vertco = CDDM_get_vert(explode, v)->co;
900                         mul_m4_v3(ob->obmat, vertco);
901
902                         sub_v3_v3(vertco, birth.co);
903
904                         /* apply rotation, size & location */
905                         sub_qt_qtqt(rot, state.rot, birth.rot);
906                         mul_qt_v3(rot, vertco);
907
908                         if (emd->flag & eExplodeFlag_PaSize)
909                                 mul_v3_fl(vertco, pa->size);
910
911                         add_v3_v3(vertco, state.co);
912
913                         mul_m4_v3(imat, vertco);
914                 }
915         }
916         BLI_edgehashIterator_free(ehi);
917
918         /*map new vertices to faces*/
919         for (i = 0, u = 0; i < totface; i++) {
920                 MFace source;
921                 int orig_v4;
922
923                 if (facepa[i] != totpart) {
924                         pa = pars + facepa[i];
925
926                         if (pa->alive == PARS_UNBORN && (emd->flag & eExplodeFlag_Unborn) == 0) continue;
927                         if (pa->alive == PARS_ALIVE && (emd->flag & eExplodeFlag_Alive) == 0) continue;
928                         if (pa->alive == PARS_DEAD && (emd->flag & eExplodeFlag_Dead) == 0) continue;
929                 }
930
931                 dm->getTessFace(dm, i, &source);
932                 mf = CDDM_get_tessface(explode, u);
933                 
934                 orig_v4 = source.v4;
935
936                 if (facepa[i] != totpart && cfra < pa->time)
937                         mindex = totvert + totpart;
938                 else 
939                         mindex = totvert + facepa[i];
940
941                 source.v1 = edgecut_get(vertpahash, source.v1, mindex);
942                 source.v2 = edgecut_get(vertpahash, source.v2, mindex);
943                 source.v3 = edgecut_get(vertpahash, source.v3, mindex);
944                 if (source.v4)
945                         source.v4 = edgecut_get(vertpahash, source.v4, mindex);
946
947                 DM_copy_tessface_data(dm, explode, i, u, 1);
948
949                 *mf = source;
950
951                 /* override uv channel for particle age */
952                 if (mtface) {
953                         float age = (cfra - pa->time) / pa->lifetime;
954                         /* Clamp to this range to avoid flipping to the other side of the coordinates. */
955                         CLAMP(age, 0.001f, 0.999f);
956
957                         mtf = mtface + u;
958
959                         mtf->uv[0][0] = mtf->uv[1][0] = mtf->uv[2][0] = mtf->uv[3][0] = age;
960                         mtf->uv[0][1] = mtf->uv[1][1] = mtf->uv[2][1] = mtf->uv[3][1] = 0.5f;
961                 }
962
963                 test_index_face(mf, &explode->faceData, u, (orig_v4 ? 4 : 3));
964                 u++;
965         }
966
967         /* cleanup */
968         BLI_edgehash_free(vertpahash, NULL);
969
970         /* finalization */
971         CDDM_calc_edges_tessface(explode);
972         CDDM_tessfaces_to_faces(explode);
973         explode->dirty |= DM_DIRTY_NORMALS;
974
975         if (psmd->psys->lattice_deform_data) {
976                 end_latt_deform(psmd->psys->lattice_deform_data);
977                 psmd->psys->lattice_deform_data = NULL;
978         }
979
980         return explode;
981 }
982
983 static ParticleSystemModifierData *findPrecedingParticlesystem(Object *ob, ModifierData *emd)
984 {
985         ModifierData *md;
986         ParticleSystemModifierData *psmd = NULL;
987
988         for (md = ob->modifiers.first; emd != md; md = md->next) {
989                 if (md->type == eModifierType_ParticleSystem)
990                         psmd = (ParticleSystemModifierData *) md;
991         }
992         return psmd;
993 }
994 static DerivedMesh *applyModifier(ModifierData *md, Object *ob,
995                                   DerivedMesh *derivedData,
996                                   ModifierApplyFlag UNUSED(flag))
997 {
998         DerivedMesh *dm = derivedData;
999         ExplodeModifierData *emd = (ExplodeModifierData *) md;
1000         ParticleSystemModifierData *psmd = findPrecedingParticlesystem(ob, md);
1001
1002         DM_ensure_tessface(dm); /* BMESH - UNTIL MODIFIER IS UPDATED FOR MPoly */
1003
1004         if (psmd) {
1005                 ParticleSystem *psys = psmd->psys;
1006
1007                 if (psys == NULL || psys->totpart == 0) return derivedData;
1008                 if (psys->part == NULL || psys->particles == NULL) return derivedData;
1009                 if (psmd->dm_final== NULL) return derivedData;
1010
1011                 /* 1. find faces to be exploded if needed */
1012                 if (emd->facepa == NULL ||
1013                     psmd->flag & eParticleSystemFlag_Pars ||
1014                     emd->flag & eExplodeFlag_CalcFaces ||
1015                     MEM_allocN_len(emd->facepa) / sizeof(int) != dm->getNumTessFaces(dm))
1016                 {
1017                         if (psmd->flag & eParticleSystemFlag_Pars)
1018                                 psmd->flag &= ~eParticleSystemFlag_Pars;
1019                         
1020                         if (emd->flag & eExplodeFlag_CalcFaces)
1021                                 emd->flag &= ~eExplodeFlag_CalcFaces;
1022
1023                         createFacepa(emd, psmd, derivedData);
1024                 }
1025                 /* 2. create new mesh */
1026                 if (emd->flag & eExplodeFlag_EdgeCut) {
1027                         int *facepa = emd->facepa;
1028                         DerivedMesh *splitdm = cutEdges(emd, dm);
1029                         DerivedMesh *explode = explodeMesh(emd, psmd, md->scene, ob, splitdm);
1030
1031                         MEM_freeN(emd->facepa);
1032                         emd->facepa = facepa;
1033                         splitdm->release(splitdm);
1034                         return explode;
1035                 }
1036                 else
1037                         return explodeMesh(emd, psmd, md->scene, ob, derivedData);
1038         }
1039         return derivedData;
1040 }
1041
1042
1043 ModifierTypeInfo modifierType_Explode = {
1044         /* name */              "Explode",
1045         /* structName */        "ExplodeModifierData",
1046         /* structSize */        sizeof(ExplodeModifierData),
1047         /* type */              eModifierTypeType_Constructive,
1048         /* flags */             eModifierTypeFlag_AcceptsMesh,
1049         /* copyData */          copyData,
1050         /* deformVerts */       NULL,
1051         /* deformMatrices */    NULL,
1052         /* deformVertsEM */     NULL,
1053         /* deformMatricesEM */  NULL,
1054         /* applyModifier */     applyModifier,
1055         /* applyModifierEM */   NULL,
1056         /* initData */          initData,
1057         /* requiredDataMask */  requiredDataMask,
1058         /* freeData */          freeData,
1059         /* isDisabled */        NULL,
1060         /* updateDepgraph */    NULL,
1061         /* updateDepsgraph */   NULL,
1062         /* dependsOnTime */     dependsOnTime,
1063         /* dependsOnNormals */  NULL,
1064         /* foreachObjectLink */ NULL,
1065         /* foreachIDLink */     NULL,
1066         /* foreachTexLink */    NULL,
1067 };