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