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