Applied Dynamic Paint 1.18f patch as a codebase for GSoC.
[blender.git] / source / blender / blenkernel / intern / dynamicpaint.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  * Contributor(s): Miika Hämäläinen
10  *
11  * ***** END GPL LICENSE BLOCK *****
12  */
13
14
15 #include "MEM_guardedalloc.h"
16
17 #include <math.h>
18 #include "stdio.h"
19
20 #include "BLI_blenlib.h"
21 #include "BLI_math.h"
22 #include "BLI_kdtree.h"
23 #include "BLI_utildefines.h"
24
25 #include "BKE_bvhutils.h"       /* bvh tree     */
26 #include "BKE_blender.h"
27 #include "BKE_cdderivedmesh.h"
28 #include "BKE_context.h"
29 #include "BKE_customdata.h"
30 #include "BKE_colortools.h"
31 #include "BKE_DerivedMesh.h"
32 #include "BKE_global.h"
33 #include "BKE_main.h"
34 #include "BKE_material.h"
35 #include "BKE_modifier.h"
36 #include "BKE_particle.h"
37 #include "BKE_report.h"
38 #include "BKE_texture.h"
39
40 #include "DNA_dynamicpaint_types.h"
41 #include "DNA_mesh_types.h"
42 #include "DNA_meshdata_types.h"
43 #include "DNA_modifier_types.h"
44 #include "DNA_object_types.h"
45 #include "DNA_scene_types.h"
46 #include "DNA_userdef_types.h"  /* to get temp file path        */
47
48 /* for bake operator    */
49 #include "ED_screen.h"
50 #include "WM_types.h"
51 #include "WM_api.h"
52
53 /* for image output     */
54 #include "IMB_imbuf_types.h"
55 #include "IMB_imbuf.h"
56 #include "BKE_image.h"
57 #include "intern/IMB_filetype.h"
58 #ifdef WITH_OPENEXR
59 #include "intern/openexr/openexr_api.h"
60 #endif
61
62 /* uv validate  */
63 #include "intern/MOD_util.h"
64
65 /* Platform independend time    */
66 #include "PIL_time.h"
67
68 /* to read object material color        */
69 #include "DNA_texture_types.h"
70 #include "../render/intern/include/render_types.h"
71 #include "../render/intern/include/voxeldata.h"
72 #include "DNA_material_types.h"
73 #include "RE_render_ext.h"
74
75 #include "BKE_dynamicpaint.h"
76
77
78 #define DPOUTPUT_JPEG 0
79 #define DPOUTPUT_PNG 1
80 #define DPOUTPUT_OPENEXR 2
81
82 #define DPOUTPUT_PAINT 0
83 #define DPOUTPUT_WET 1
84 #define DPOUTPUT_DISPLACE 2
85
86 struct Object;
87 struct Scene;
88 struct DerivedMesh;
89 struct DynamicPaintModifierData;
90
91 /*
92 *       Init predefined antialias jitter data
93 */
94 float jitterDistances[5] = {0.0f,
95                                                         0.447213595f,
96                                                         0.447213595f,
97                                                         0.447213595f,
98                                                         0.5f};
99
100 /* precalculated gaussian factors for 5x super sampling */
101 float gaussianFactors[5] = {    0.996849f,
102                                                                 0.596145f,
103                                                                 0.596145f,
104                                                                 0.596145f,
105                                                                 0.524141f};
106 float gaussianTotal = 3.309425f;
107
108 /*
109 *       Neighbouring pixel table x and y list
110 */
111 int neighX[8] = {1,1,0,-1,-1,-1, 0, 1};
112 int neighY[8] = {0,1,1, 1, 0,-1,-1,-1};
113
114
115 /*
116 *       Modifier call. Updates derived mesh data if baking.
117 */
118 void dynamicPaint_Modifier_update(struct DynamicPaintModifierData *pmd, DerivedMesh *dm)
119 {
120
121         if (!pmd->baking) return;
122
123         if((pmd->type & MOD_DYNAMICPAINT_TYPE_CANVAS) && pmd->canvas) {
124
125                 if (pmd->canvas->dm) pmd->canvas->dm->release(pmd->canvas->dm);
126                 pmd->canvas->dm = CDDM_copy(dm);
127         }
128         else if((pmd->type & MOD_DYNAMICPAINT_TYPE_PAINT) && pmd->paint) {
129
130                 if (pmd->paint->dm) pmd->paint->dm->release(pmd->paint->dm);
131                 pmd->paint->dm = CDDM_copy(dm);
132         }
133
134 }
135
136 /*
137 *       Free canvas data.
138 */
139 static void dynamicPaint_Modifier_freeCanvas(struct DynamicPaintModifierData *pmd)
140 {
141         if(pmd->canvas)
142         {
143                 if (pmd->canvas->dm)
144                         pmd->canvas->dm->release(pmd->canvas->dm);
145                 pmd->canvas->dm = NULL;
146         }
147 }
148
149 /*
150 *       Free paint data.
151 */
152 static void dynamicPaint_Modifier_freePaint(struct DynamicPaintModifierData *pmd)
153 {
154         if(pmd->paint)
155         {
156                 if(pmd->paint->dm)
157                         pmd->paint->dm->release(pmd->paint->dm);
158                 pmd->paint->dm = NULL;
159
160
161                 if(pmd->paint->paint_ramp)
162                          MEM_freeN(pmd->paint->paint_ramp);
163                 pmd->paint->paint_ramp = NULL;
164         }
165 }
166
167 /*
168 *       Free whole dp modifier.
169 */
170 void dynamicPaint_Modifier_free(struct DynamicPaintModifierData *pmd)
171 {
172         if(pmd)
173         {
174                 dynamicPaint_Modifier_freeCanvas(pmd);
175                 dynamicPaint_Modifier_freePaint(pmd);
176         }
177 }
178
179 /*
180 *       Initialize modifier data.
181 */
182 void dynamicPaint_Modifier_createType(struct DynamicPaintModifierData *pmd)
183 {
184         if(pmd)
185         {
186                 if(pmd->type & MOD_DYNAMICPAINT_TYPE_CANVAS)
187                 {
188                         if(pmd->canvas)
189                                 dynamicPaint_Modifier_freeCanvas(pmd);
190
191                         pmd->canvas = MEM_callocN(sizeof(DynamicPaintCanvasSettings), "DynamicPaintCanvas");
192                         pmd->canvas->pmd = pmd;
193
194                         pmd->canvas->flags = MOD_DPAINT_ANTIALIAS | MOD_DPAINT_MULALPHA | MOD_DPAINT_DRY_LOG;
195                         pmd->canvas->output = MOD_DPAINT_OUT_PAINT;
196                         pmd->canvas->effect = 0;
197                         pmd->canvas->effect_ui = 1;
198
199                         pmd->canvas->diss_speed = 300;
200                         pmd->canvas->dry_speed = 300;
201                         pmd->canvas->dflat_speed = 300;
202
203                         pmd->canvas->disp_depth = 1.0f;
204                         pmd->canvas->disp_type = MOD_DPAINT_DISP_DISPLACE;
205                         pmd->canvas->disp_format = MOD_DPAINT_DISPFOR_PNG;
206
207                         pmd->canvas->resolution = 256;
208                         pmd->canvas->start_frame = 1;
209                         pmd->canvas->end_frame = 100;
210                         pmd->canvas->substeps = 0;
211
212                         pmd->canvas->spread_speed = 1.0f;
213                         pmd->canvas->drip_speed = 1.0f;
214                         pmd->canvas->shrink_speed = 1.0f;
215
216                         sprintf(pmd->canvas->paint_output_path, "%spaintmap", "/tmp\\");
217                         sprintf(pmd->canvas->wet_output_path, "%swetmap", "/tmp\\");
218                         sprintf(pmd->canvas->displace_output_path, "%sdispmap", "/tmp\\");
219
220                         pmd->canvas->ui_info[0] = '\0';
221
222
223                         pmd->canvas->dm = NULL;
224
225                 }
226                 else if(pmd->type & MOD_DYNAMICPAINT_TYPE_PAINT)
227                 {
228                         if(pmd->paint)
229                                 dynamicPaint_Modifier_freePaint(pmd);
230
231                         pmd->paint = MEM_callocN(sizeof(DynamicPaintPainterSettings), "DynamicPaint Paint");
232                         pmd->paint->pmd = pmd;
233
234                         pmd->paint->psys = NULL;
235
236                         pmd->paint->flags = MOD_DPAINT_DO_PAINT | MOD_DPAINT_DO_WETNESS | MOD_DPAINT_DO_DISPLACE | MOD_DPAINT_ABS_ALPHA;
237                         pmd->paint->collision = MOD_DPAINT_COL_VOLUME;
238                         
239                         pmd->paint->mat = NULL;
240                         pmd->paint->r = 1.0f;
241                         pmd->paint->g = 1.0f;
242                         pmd->paint->b = 1.0f;
243                         pmd->paint->alpha = 1.0f;
244                         pmd->paint->wetness = 1.0f;
245
246                         pmd->paint->paint_distance = 0.1f;
247                         pmd->paint->proximity_falloff = MOD_DPAINT_PRFALL_SHARP;
248
249                         pmd->paint->displace_distance = 0.5f;
250                         pmd->paint->prox_displace_strength = 0.5f;
251
252                         pmd->paint->particle_radius = 0.2;
253                         pmd->paint->particle_smooth = 0.05;
254
255                         pmd->paint->dm = NULL;
256
257                         /*
258                         *       Paint proximity falloff colorramp.
259                         */
260                         {
261                                 CBData *ramp;
262
263                                 pmd->paint->paint_ramp = add_colorband(0);
264                                 ramp = pmd->paint->paint_ramp->data;
265                                 /* Add default smooth-falloff ramp.     */
266                                 ramp[0].r = ramp[0].g = ramp[0].b = ramp[0].a = 1.0f;
267                                 ramp[0].pos = 0.0f;
268                                 ramp[1].r = ramp[1].g = ramp[1].b = ramp[1].pos = 1.0f;
269                                 ramp[1].a = 0.0f;
270                                 pmd->paint->paint_ramp->tot = 2;
271                         }
272                 }
273         }
274 }
275
276 void dynamicPaint_Modifier_copy(struct DynamicPaintModifierData *pmd, struct DynamicPaintModifierData *tpmd)
277 {
278         /* Init modifier        */
279         tpmd->type = pmd->type;
280         dynamicPaint_Modifier_createType(tpmd);
281
282         /* Copy data    */
283         if (tpmd->canvas) {
284                 pmd->canvas->pmd = tpmd;
285
286                 tpmd->canvas->flags = pmd->canvas->flags;
287                 tpmd->canvas->output = pmd->canvas->output;
288                 tpmd->canvas->disp_type = pmd->canvas->disp_type;
289                 tpmd->canvas->disp_format = pmd->canvas->disp_format;
290                 tpmd->canvas->effect = pmd->canvas->effect;
291                 tpmd->canvas->effect_ui = 1;
292
293                 tpmd->canvas->resolution = pmd->canvas->resolution;
294                 tpmd->canvas->start_frame = pmd->canvas->start_frame;
295                 tpmd->canvas->end_frame = pmd->canvas->end_frame;
296                 tpmd->canvas->substeps = pmd->canvas->substeps;
297
298                 tpmd->canvas->dry_speed = pmd->canvas->dry_speed;
299                 tpmd->canvas->diss_speed = pmd->canvas->diss_speed;
300                 tpmd->canvas->disp_depth = pmd->canvas->disp_depth;
301                 tpmd->canvas->dflat_speed = pmd->canvas->dflat_speed;
302
303                 strncpy(tpmd->canvas->paint_output_path, pmd->canvas->paint_output_path, 240);
304                 strncpy(tpmd->canvas->wet_output_path, pmd->canvas->wet_output_path, 240);
305                 strncpy(tpmd->canvas->displace_output_path, pmd->canvas->displace_output_path, 240);
306
307                 tpmd->canvas->spread_speed = pmd->canvas->spread_speed;
308                 tpmd->canvas->drip_speed = pmd->canvas->drip_speed;
309                 tpmd->canvas->shrink_speed = pmd->canvas->shrink_speed;
310
311                 strncpy(tpmd->canvas->uvlayer_name, tpmd->canvas->uvlayer_name, 32);
312
313         } else if (tpmd->paint) {
314                 pmd->paint->pmd = tpmd;
315
316                 tpmd->paint->flags = pmd->paint->flags;
317                 tpmd->paint->collision = pmd->paint->collision;
318
319                 tpmd->paint->r = pmd->paint->r;
320                 tpmd->paint->g = pmd->paint->g;
321                 tpmd->paint->b = pmd->paint->b;
322                 tpmd->paint->alpha = pmd->paint->alpha;
323                 tpmd->paint->wetness = pmd->paint->wetness;
324
325                 tpmd->paint->particle_radius = pmd->paint->particle_radius;
326                 tpmd->paint->particle_smooth = pmd->paint->particle_smooth;
327                 tpmd->paint->paint_distance = pmd->paint->paint_distance;
328                 tpmd->paint->psys = pmd->paint->psys;
329                 tpmd->paint->displace_distance = pmd->paint->displace_distance;
330                 tpmd->paint->prox_displace_strength = pmd->paint->prox_displace_strength;
331
332                 tpmd->paint->paint_ramp = pmd->paint->paint_ramp;
333
334                 tpmd->paint->proximity_falloff = pmd->paint->proximity_falloff;
335         }
336 }
337
338
339
340 void dynamicPaint_Modifier_do(DynamicPaintModifierData *pmd, Scene *scene, Object *ob, DerivedMesh *dm)
341 {       
342         /* Update derived mesh data to modifier if baking       */
343         dynamicPaint_Modifier_update(pmd, dm);
344 }
345
346
347 /*
348 *       Tries to find the neighbouring pixel in given (uv space) direction.
349 *       Result is used by effect system to move paint on the surface.
350 *
351 *   px,py : origin pixel x and y
352 *       n_index : lookup direction index (use neighX,neighY to get final index)
353 */
354 static int dynamicPaint_findNeighbourPixel(DynamicPaintCanvasSettings *canvas, int px, int py, int n_index)
355 {
356         /* Note: Current method only uses polygon edges to detect neighbouring pixels.
357         *  -> It doesn't always lead to the optimum pixel but is accurate enough
358         *  and faster/simplier than including possible face tip point links)
359         */
360
361         int x,y;
362         PaintSurfacePoint *tPoint = NULL;
363         PaintSurfacePoint *cPoint = NULL;
364         PaintSurface *surface = NULL;
365
366         surface = canvas->surface;
367
368         x = px + neighX[n_index];
369         y = py + neighY[n_index];
370
371         if (x<0 || x>=surface->w) return -1;
372         if (y<0 || y>=surface->h) return -1;
373
374         tPoint = (&surface->point[x+surface->w*y]);             /* UV neighbour */
375         
376         cPoint = (&surface->point[px+surface->w*py]);   /* Origin point */
377
378         /*
379         *       Check if target point is on same face -> mark it as neighbour
380         *   (and if it isn't marked as an "edge pixel")
381         */
382         if ((tPoint->index == cPoint->index) && (tPoint->neighbour_pixel == -1)) {
383                 /* If it's on the same face, it has to be a correct neighbour   */
384                 return (x+surface->w*y);
385         }
386
387
388         /*
389         *       If the uv neighbour is mapped directly to
390         *       a face -> use this point.
391         *       
392         *       !! Replace with "is uv faces linked" check !!
393         *       This should work fine as long as uv island
394         *       margin is > 1 pixel.
395         */
396         if ((tPoint->index != -1) && (tPoint->neighbour_pixel == -1)) {
397                 return (x+surface->w*y);
398         }
399
400         /*
401         *       If we get here, the actual neighbouring pixel
402         *       points to a non-linked uv face, and we have to find
403         *       it's "real" neighbour.
404         *
405         *       Simple neighbouring face finding algorithm:
406         *       - find closest uv edge to that pixel and get
407         *         the other face connected to that edge on actual mesh
408         *       - find corresponding position of that new face edge
409         *         in uv space
410         *
411         *       TODO: Implement something more accurate / optimized?
412         */
413         {
414                 int numOfFaces = canvas->dm->getNumFaces(canvas->dm);
415                 MVert *mvert = NULL;
416                 MFace *mface = NULL;
417                 MTFace *tface = NULL;
418
419                 mvert = canvas->dm->getVertArray(canvas->dm);
420                 mface = canvas->dm->getFaceArray(canvas->dm);
421                 tface = DM_get_face_data_layer(canvas->dm, CD_MTFACE);
422
423                 /* Get closest edge to that subpixel on UV map  */
424                 {
425                         float pixel[2], dist, t_dist;
426                         int i, uindex[2], edge1_index, edge2_index, e1_index, e2_index, target_face;
427
428                         float closest_point[2], lambda, dir_vec[2];
429                         int target_uv1, target_uv2, final_pixel[2], final_index;
430
431                         float (*s_uv1),(*s_uv2), (*t_uv1), (*t_uv2);
432
433                         pixel[0] = ((float)(px + neighX[n_index]) + 0.5f) / (float)surface->w;
434                         pixel[1] = ((float)(py + neighY[n_index]) + 0.5f) / (float)surface->h;
435
436                         /* Get uv indexes for current face part */
437                         if (cPoint->quad) {
438                                 uindex[0] = 0; uindex[1] = 2; uindex[2] = 3;
439                         }
440                         else {
441                                 uindex[0] = 0; uindex[1] = 1; uindex[2] = 2;
442                         }
443
444                         /*
445                         *       Find closest edge to that pixel
446                         */
447                         /* Dist to first edge   */
448                         e1_index = cPoint->v1; e2_index = cPoint->v2; edge1_index = uindex[0]; edge2_index = uindex[1];
449                         dist = dist_to_line_segment_v2(pixel, tface[cPoint->index].uv[edge1_index], tface[cPoint->index].uv[edge2_index]);
450
451                         /* Dist to second edge  */
452                         t_dist = dist_to_line_segment_v2(pixel, tface[cPoint->index].uv[uindex[1]], tface[cPoint->index].uv[uindex[2]]);
453                         if (t_dist < dist) {e1_index = cPoint->v2; e2_index = cPoint->v3; edge1_index = uindex[1]; edge2_index = uindex[2]; dist = t_dist;}
454
455                         /* Dist to third edge   */
456                         t_dist = dist_to_line_segment_v2(pixel, tface[cPoint->index].uv[uindex[2]], tface[cPoint->index].uv[uindex[0]]);
457                         if (t_dist < dist) {e1_index = cPoint->v3; e2_index = cPoint->v1;  edge1_index = uindex[2]; edge2_index = uindex[0]; dist = t_dist;}
458
459
460                         /*
461                         *       Now find another face that is linked to that edge
462                         */
463                         target_face = -1;
464
465                         for (i=0; i<numOfFaces; i++) {
466                                 /*
467                                 *       Check if both edge vertices share this face
468                                 */
469                                 int v4 = -1;
470                                 if (mface[i].v4) v4 = mface[i].v4;
471
472                                 if ((e1_index == mface[i].v1 || e1_index == mface[i].v2 || e1_index == mface[i].v3 || e1_index == v4) &&
473                                         (e2_index == mface[i].v1 || e2_index == mface[i].v2 || e2_index == mface[i].v3 || e2_index == v4)) {
474                                         if (i == cPoint->index) continue;
475
476                                         target_face = i;
477
478                                         /*
479                                         *       Get edge UV index
480                                         */
481                                         if (e1_index == mface[i].v1) target_uv1 = 0;
482                                         else if (e1_index == mface[i].v2) target_uv1 = 1;
483                                         else if (e1_index == mface[i].v3) target_uv1 = 2;
484                                         else target_uv1 = 3;
485
486                                         if (e2_index == mface[i].v1) target_uv2 = 0;
487                                         else if (e2_index == mface[i].v2) target_uv2 = 1;
488                                         else if (e2_index == mface[i].v3) target_uv2 = 2;
489                                         else target_uv2 = 3;
490
491                                         break;
492                                 }
493                         }
494
495                         /* If none found return -1      */
496                         if (target_face == -1) return -1;
497
498                         /*
499                         *       If target face is connected in UV space as well, just use original index
500                         */
501                         s_uv1 = (float *)tface[cPoint->index].uv[edge1_index];
502                         s_uv2 = (float *)tface[cPoint->index].uv[edge2_index];
503                         t_uv1 = (float *)tface[target_face].uv[target_uv1];
504                         t_uv2 = (float *)tface[target_face].uv[target_uv2];
505
506                         //printf("connected UV : %f,%f & %f,%f - %f,%f & %f,%f\n", s_uv1[0], s_uv1[1], s_uv2[0], s_uv2[1], t_uv1[0], t_uv1[1], t_uv2[0], t_uv2[1]);
507
508                         if (((s_uv1[0] == t_uv1[0] && s_uv1[1] == t_uv1[1]) &&
509                                  (s_uv2[0] == t_uv2[0] && s_uv2[1] == t_uv2[1]) ) ||
510                                 ((s_uv2[0] == t_uv1[0] && s_uv2[1] == t_uv1[1]) &&
511                                  (s_uv1[0] == t_uv2[0] && s_uv1[1] == t_uv2[1]) )) return ((px+neighX[n_index]) + surface->w*(py+neighY[n_index]));
512
513                         /*
514                         *       Find a point that is relatively at same edge position
515                         *       on this other face UV
516                         */
517                         lambda = closest_to_line_v2(closest_point, pixel, tface[cPoint->index].uv[edge1_index], tface[cPoint->index].uv[edge2_index]);
518                         if (lambda < 0.0f) lambda = 0.0f;
519                         if (lambda > 1.0f) lambda = 1.0f;
520
521                         sub_v2_v2v2(dir_vec, tface[target_face].uv[target_uv2], tface[target_face].uv[target_uv1]);
522
523                         mul_v2_fl(dir_vec, lambda);
524
525                         copy_v2_v2(pixel, tface[target_face].uv[target_uv1]);
526                         add_v2_v2(pixel, dir_vec);
527                         pixel[0] = (pixel[0] * (float)surface->w) - 0.5f;
528                         pixel[1] = (pixel[1] * (float)surface->h) - 0.5f;
529
530                         final_pixel[0] = (int)floor(pixel[0]);
531                         final_pixel[1] = (int)floor(pixel[1]);
532
533                         /* If current pixel uv is outside of texture    */
534                         if (final_pixel[0] < 0 || final_pixel[0] >= surface->w) return -1;
535                         if (final_pixel[1] < 0 || final_pixel[1] >= surface->h) return -1;
536
537                         final_index = final_pixel[0] + surface->w * final_pixel[1];
538
539                         /* If we ended up to our origin point ( mesh has smaller than pixel sized faces)        */
540                         if (final_index == (px+surface->w*py)) return -1;
541                         /* If found pixel still lies on wrong face ( mesh has smaller than pixel sized faces)   */
542                         if (surface->point[final_index].index != target_face) return -1;
543
544                         /*
545                         *       If final point is an "edge pixel", use it's "real" neighbour instead
546                         */
547                         if (surface->point[final_index].neighbour_pixel != -1) final_index = cPoint->neighbour_pixel;
548
549                         return final_index;
550                 }
551         }
552 }
553
554 /*
555 *       Output error message to both ui and console
556 */
557 static void dpError(DynamicPaintCanvasSettings *canvas, char *string)
558 {
559
560         if (strlen(string)>64) string[63] = '\0';
561
562         /* Add error to canvas ui info label */
563         sprintf(canvas->error, string);
564
565         /* Print console output */
566         printf("DynamicPaint bake failed: %s\n", canvas->error);
567 }
568
569 /*
570 *       Create Canvas Surface for baking
571 */
572 static int dynamicPaint_createCanvasSurface(DynamicPaintCanvasSettings *canvas)
573 {
574
575                 int yy;
576                 int w,h;
577
578                 /* Antialias jitter point relative coords       */
579                 float jitter5sample[10] =  {0.0f, 0.0f,
580                                                                 -0.2f, -0.4f,
581                                                                 0.2f, 0.4f,
582                                                                 0.4f, -0.2f,
583                                                                 -0.4f, 0.3f};
584
585                 DerivedMesh *dm = canvas->dm;
586                 int numOfFaces;
587                 MVert *mvert = NULL;
588                 MFace *mface = NULL;
589                 MTFace *tface = NULL;
590
591                 PaintSurface *surface = NULL;
592                 BB2d *faceBB = NULL;
593                 char uvname[32];
594
595                 if (!dm) { dpError(canvas, "Canvas mesh not updated."); return 0;}
596                 numOfFaces = dm->getNumFaces(dm);
597
598
599                 /* Allocate memory for surface  */
600                 canvas->surface = (struct PaintSurface *) MEM_callocN(sizeof(struct PaintSurface), "MPCanvasSurface");
601                 if (canvas->surface == NULL) {dpError(canvas, "Not enough free memory."); return 0;}
602
603                 surface = canvas->surface;
604                 surface->point = NULL;
605
606                 mvert = dm->getVertArray(dm);
607                 mface = dm->getFaceArray(dm);
608
609                 validate_layer_name(&dm->faceData, CD_MTFACE, canvas->uvlayer_name, uvname);
610                 tface = CustomData_get_layer_named(&dm->faceData, CD_MTFACE, uvname);
611
612                 /* Check for validity   */
613                 if (!tface) {dpError(canvas, "No UV data on canvas."); return 0;}
614                 if (canvas->resolution < 16 || canvas->resolution > 8096) {dpError(canvas, "Invalid resolution."); return 0;}
615         
616                 w = h = canvas->resolution;
617                 surface->w = w;
618                 surface->h = h;
619
620                 /*
621                 *       Start generating the surface
622                 */
623                 printf("DynamicPaint: Preparing canvas of %ix%i pixels and %i faces.\n", w, h, numOfFaces);
624
625                 surface->pixelSamples = (canvas->flags & MOD_DPAINT_ANTIALIAS) ? 5 : 1;
626                 surface->point = (struct PaintSurfacePoint *) MEM_callocN(w*h*sizeof(struct PaintSurfacePoint), "PaintSurfaceData");
627                 if (surface->point == NULL) {dpError(canvas, "Not enough free memory."); return 0;}
628
629                 /*
630                 *       Generate a temporary bounding box array for UV faces to optimize
631                 *       the pixel-inside-a-face search.
632                 */
633                 faceBB = (struct BB2d *) MEM_mallocN(numOfFaces*sizeof(struct BB2d), "MPCanvasFaceBB");
634                 if (faceBB == NULL) {dpError(canvas, "Not enough free memory."); return 0;}
635
636                 for (yy=0; yy<numOfFaces; yy++) {
637
638                         int numOfVert = (mface[yy].v4) ? 4 : 3;
639                         int i;
640         
641                         VECCOPY2D(faceBB[yy].min, tface[yy].uv[0]);
642                         VECCOPY2D(faceBB[yy].max, tface[yy].uv[0]);
643
644                         for (i = 1; i<numOfVert; i++) {
645                                 
646                                 if (tface[yy].uv[i][0] < faceBB[yy].min[0]) faceBB[yy].min[0] = tface[yy].uv[i][0];
647                                 if (tface[yy].uv[i][1] < faceBB[yy].min[1]) faceBB[yy].min[1] = tface[yy].uv[i][1];
648
649                                 if (tface[yy].uv[i][0] > faceBB[yy].max[0]) faceBB[yy].max[0] = tface[yy].uv[i][0];
650                                 if (tface[yy].uv[i][1] > faceBB[yy].max[1]) faceBB[yy].max[1] = tface[yy].uv[i][1];
651
652                         }
653                 }       // end face loop
654
655                 /*
656                 *       Allocate antialias sample data (without threads due to malloc)
657                 *       (Non threadable?)
658                 */
659                 for (yy = 0; yy < h; yy++)
660                 {
661                         int xx;
662                         for (xx = 0; xx < w; xx++)
663                         {
664                                 int index = xx+w*yy;
665                                 PaintSurfacePoint *cPoint = (&surface->point[index]);
666
667                                 /* Initialize barycentricWeights        */
668                                 cPoint->barycentricWeights = (struct Vec3f *) malloc( surface->pixelSamples * sizeof(struct Vec3f ));
669                                 if (cPoint->barycentricWeights == NULL) {dpError(canvas, "Not enough free memory."); return 0;}
670
671                         }
672                 } // end pixel loop
673
674                 /*
675                 *       Loop through every pixel and check
676                 *       if pixel is uv-mapped on a canvas face.
677                 */
678                 #pragma omp parallel for schedule(static)
679                 for (yy = 0; yy < h; yy++)
680                 {
681                         int xx;
682                         for (xx = 0; xx < w; xx++)
683                         {
684                                 int i, sample;
685                                 int index = xx+w*yy;
686                                 PaintSurfacePoint *cPoint = (&surface->point[index]);
687
688                                 short isInside = 0;     /* if point is inside a uv face */
689
690                                 float d1[2], d2[2], d3[2], point[5][2];
691                                 float dot00,dot01,dot02,dot11,dot12, invDenom, u,v;
692
693                                 /*
694                                 *       Init per pixel settings
695                                 */
696                                 cPoint->color[0] = 0.0f;
697                                 cPoint->color[1] = 0.0f;
698                                 cPoint->color[2] = 0.0f;
699                                 cPoint->alpha = 0.0f;
700                                 cPoint->depth = 0.0f;
701
702                                 cPoint->wetness = 0.0f;
703                                 cPoint->e_alpha = 0.0f;
704                                 cPoint->e_color[0] = 0.0f;
705                                 cPoint->e_color[1] = 0.0f;
706                                 cPoint->e_color[2] = 0.0f;
707                                 cPoint->state = 0;
708
709                                 cPoint->index = -1;
710                                 cPoint->neighbour_pixel = -1;
711
712                                 /* Actual pixel center, used when collision is found    */
713                                 point[0][0] = ((float)xx + 0.5f) / w;
714                                 point[0][1] = ((float)yy + 0.5f) / h;
715
716                                 /*
717                                 * A pixel middle sample isn't enough to find very narrow polygons
718                                 * So using 4 samples of each corner too
719                                 */
720                                 point[1][0] = ((float)xx) / w;
721                                 point[1][1] = ((float)yy) / h;
722
723                                 point[2][0] = ((float)xx+1) / w;
724                                 point[2][1] = ((float)yy) / h;
725
726                                 point[3][0] = ((float)xx) / w;
727                                 point[3][1] = ((float)yy+1) / h;
728
729                                 point[4][0] = ((float)xx+1) / w;
730                                 point[4][1] = ((float)yy+1) / h;
731
732
733                                 /* Loop through pixel samples, starting from middle point       */
734                                 for (sample=0; sample<5; sample++) {
735                                                 
736                                                 /* Loop through every face in the mesh  */
737                                                 for (i=0; i<numOfFaces; i++) {
738
739                                                         /* Check uv bb  */
740                                                         if (faceBB[i].min[0] > (point[sample][0])) continue;
741                                                         if (faceBB[i].min[1] > (point[sample][1])) continue;
742                                                         if (faceBB[i].max[0] < (point[sample][0])) continue;
743                                                         if (faceBB[i].max[1] < (point[sample][1])) continue;
744
745                                                         /*
746                                                         *       Calculate point inside a triangle check
747                                                         *       for uv0,1,2
748                                                         */
749                                                         VECSUB2D(d1,  tface[i].uv[2], tface[i].uv[0]);  // uv2 - uv0
750                                                         VECSUB2D(d2,  tface[i].uv[1], tface[i].uv[0]);  // uv1 - uv0
751                                                         VECSUB2D(d3,  point[sample], tface[i].uv[0]);   // point - uv0
752
753
754                                                         dot00 = d1[0]*d1[0] + d1[1]*d1[1];
755                                                         dot01 = d1[0]*d2[0] + d1[1]*d2[1];
756                                                         dot02 = d1[0]*d3[0] + d1[1]*d3[1];
757                                                         dot11 = d2[0]*d2[0] + d2[1]*d2[1];
758                                                         dot12 = d2[0]*d3[0] + d2[1]*d3[1];
759
760                                                         invDenom = 1 / (dot00 * dot11 - dot01 * dot01);
761                                                         u = (dot11 * dot02 - dot01 * dot12) * invDenom;
762                                                         v = (dot00 * dot12 - dot01 * dot02) * invDenom;
763
764                                                         if ((u > 0) && (v > 0) && (u + v < 1)) {isInside=1;} /* is inside a triangle */
765
766                                                         /*
767                                                         *       If collision wasn't found but the face is a quad
768                                                         *       do another check for the second half
769                                                         */
770                                                         if ((!isInside) && mface[i].v4)
771                                                         {
772
773                                                                 /* change d2 to test the other half     */
774                                                                 VECSUB2D(d2,  tface[i].uv[3], tface[i].uv[0]);  // uv3 - uv0
775
776                                                                 /* test again   */
777                                                                 dot00 = d1[0]*d1[0] + d1[1]*d1[1];
778                                                                 dot01 = d1[0]*d2[0] + d1[1]*d2[1];
779                                                                 dot02 = d1[0]*d3[0] + d1[1]*d3[1];
780                                                                 dot11 = d2[0]*d2[0] + d2[1]*d2[1];
781                                                                 dot12 = d2[0]*d3[0] + d2[1]*d3[1];
782
783                                                                 invDenom = 1 / (dot00 * dot11 - dot01 * dot01);
784                                                                 u = (dot11 * dot02 - dot01 * dot12) * invDenom;
785                                                                 v = (dot00 * dot12 - dot01 * dot02) * invDenom;
786
787                                                                 if ((u > 0) && (v > 0) && (u + v < 1)) {isInside=2;} /* is inside the second half of the quad */
788
789                                                         }
790
791                                                         /*
792                                                         *       If point was inside the face
793                                                         */
794                                                         if (isInside != 0) {
795
796                                                                 float uv1co[2], uv2co[2], uv3co[2], uv[2];
797                                                                 int j;
798
799                                                                 /* Get triagnle uvs     */
800                                                                 if (isInside==1) {
801                                                                         VECCOPY2D(uv1co, tface[i].uv[0]);
802                                                                         VECCOPY2D(uv2co, tface[i].uv[1]);
803                                                                         VECCOPY2D(uv3co, tface[i].uv[2]);
804                                                                 }
805                                                                 else {
806                                                                         VECCOPY2D(uv1co, tface[i].uv[0]);
807                                                                         VECCOPY2D(uv2co, tface[i].uv[2]);
808                                                                         VECCOPY2D(uv3co, tface[i].uv[3]);
809                                                                 }
810
811                                                                 /* Add b-weights per anti-aliasing sample       */
812                                                                 for (j=0; j<surface->pixelSamples; j++) {
813
814                                                                         uv[0] = point[0][0] + jitter5sample[j*2] / w;
815                                                                         uv[1] = point[0][1] + jitter5sample[j*2+1] / h;
816
817                                                                         barycentric_weights_v2(uv1co, uv2co, uv3co, uv, cPoint->barycentricWeights[j].v);
818                                                                 }
819
820                                                                 /* Set surface point face values        */
821                                                                 cPoint->index = i;                                                      /* face index */
822                                                                 cPoint->quad = (isInside == 2) ? 1 : 0;         /* quad or tri part*/
823
824                                                                 /* save vertex indexes  */
825                                                                 cPoint->v1 = (isInside == 2) ? mface[i].v1 : mface[i].v1;
826                                                                 cPoint->v2 = (isInside == 2) ? mface[i].v3 : mface[i].v2;
827                                                                 cPoint->v3 = (isInside == 2) ? mface[i].v4 : mface[i].v3;
828                                                                 
829                                                                 sample = 5;     /* make sure we exit sample loop as well */
830                                                                 break;
831                                                         }       // end isInside
832                                                 } // end face loop
833                                 }        // end sample
834                         }       // end of yy loop
835                 }       // end of xx loop
836
837
838
839                 /*
840                 *       Now loop through every pixel that was left without index
841                 *       and find if they have neighbouring pixels that have an index.
842                 *       If so use that polygon as pixel surface.
843                 *       (To avoid seams on uv island edges.)
844                 */
845                 #pragma omp parallel for schedule(static)
846                 for (yy = 0; yy < h; yy++)
847                 {
848                         int xx;
849                         for (xx = 0; xx < w; xx++)
850                         {
851                                 int index = xx+w*yy;
852                                 PaintSurfacePoint *cPoint = (&surface->point[index]);
853
854                                 /* If point isnt't on canvas mesh       */
855                                 if (cPoint->index == -1) {
856                                         int u_min, u_max, v_min, v_max;
857                                         int u,v, ind;
858                                         float point[2];
859
860                                         /* get loop area        */
861                                         u_min = (xx > 0) ? -1 : 0;
862                                         u_max = (xx < (w-1)) ? 1 : 0;
863                                         v_min = (yy > 0) ? -1 : 0;
864                                         v_max = (yy < (h-1)) ? 1 : 0;
865
866                                         point[0] = ((float)xx + 0.5f) / w;
867                                         point[1] = ((float)yy + 0.5f) / h;
868
869                                         /* search through defined area for neighbour    */
870                                         for (u=u_min; u<=u_max; u++)
871                                                 for (v=v_min; v<=v_max; v++) {
872
873                                                         /* if not this pixel itself     */
874                                                         if (u!=0 || v!=0) {
875                                                                 ind = (xx+u)+w*(yy+v);
876
877                                                                 /* if neighbour has index       */
878                                                                 if (surface->point[ind].index != -1) {
879
880                                                                         float uv1co[2], uv2co[2], uv3co[2], uv[2];
881                                                                         int i = surface->point[ind].index, j;
882
883                                                                         /*
884                                                                         *       Now calculate pixel data for this pixel as it was on polygon surface
885                                                                         */
886                                                                         if (!surface->point[ind].quad) {
887                                                                                 VECCOPY2D(uv1co, tface[i].uv[0]);
888                                                                                 VECCOPY2D(uv2co, tface[i].uv[1]);
889                                                                                 VECCOPY2D(uv3co, tface[i].uv[2]);
890                                                                         }
891                                                                         else {
892                                                                                 VECCOPY2D(uv1co, tface[i].uv[0]);
893                                                                                 VECCOPY2D(uv2co, tface[i].uv[2]);
894                                                                                 VECCOPY2D(uv3co, tface[i].uv[3]);
895                                                                         }
896
897                                                                         /* Add b-weights per anti-aliasing sample       */
898                                                                         for (j=0; j<surface->pixelSamples; j++) {
899
900                                                                                 uv[0] = point[0] + jitter5sample[j*2] / w;
901                                                                                 uv[1] = point[1] + jitter5sample[j*2+1] / h;
902                                                                                 barycentric_weights_v2(uv1co, uv2co, uv3co, uv, cPoint->barycentricWeights[j].v);
903                                                                         }
904
905                                                                         /* Set values   */
906                                                                         cPoint->neighbour_pixel = ind;                          // face index
907                                                                         cPoint->quad = surface->point[ind].quad;                // quad or tri
908
909                                                                         /* save vertex indexes  */
910                                                                         cPoint->v1 = (cPoint->quad) ? mface[i].v1 : mface[i].v1;
911                                                                         cPoint->v2 = (cPoint->quad) ? mface[i].v3 : mface[i].v2;
912                                                                         cPoint->v3 = (cPoint->quad) ? mface[i].v4 : mface[i].v3;
913
914                                                                         u = u_max + 1;  /* make sure we exit outer loop as well */
915                                                                         break;
916                                                                 }
917
918                                                 } // end itself check
919                                         } // end uv loop
920                                 }       // end if has index
921                         }
922                 } // end pixel loop
923
924                 /*
925                 *       When base loop is over convert found neighbour indexes to real ones
926                 *       Also count the final number of active surface points
927                 */
928                 surface->active_points = 0;
929
930                 #pragma omp parallel for schedule(static)
931                 for (yy = 0; yy < h; yy++)
932                 {
933                         int xx;
934                         for (xx = 0; xx < w; xx++)
935                         {
936                                 int index = xx+w*yy;
937                                 PaintSurfacePoint *cPoint = (&surface->point[index]);
938
939                                 if (cPoint->index == -1 && cPoint->neighbour_pixel != -1) cPoint->index = surface->point[cPoint->neighbour_pixel].index;
940                                 if (cPoint->index != -1) surface->active_points++;
941                         }
942                 } // end pixel loop
943
944 #if 0
945                 /*
946                 *       -----------------------------------------------------------------
947                 *       For debug, output pixel statuses to the color map
948                 *       -----------------------------------------------------------------
949                 */
950                 #pragma omp parallel for schedule(static)
951                 for (yy = 0; yy < h; yy++)
952                 {
953                         int xx;
954                         for (xx = 0; xx < w; xx++)
955                         {
956                                 int index = xx+w*yy;
957                                 PaintSurfacePoint *cPoint = (&surface->point[index]);
958                                 cPoint->alpha=1.0f;
959
960                                 /* Every pixel that is assigned as "edge pixel" gets blue color */
961                                 if (cPoint->neighbour_pixel != -1) cPoint->color[2] = 1.0f;
962                                 /* and every pixel that finally got an polygon gets red color   */
963                                 if (cPoint->index != -1) cPoint->color[0] = 1.0f;
964                                 /* green color shows pixel face index hash      */
965                                 if (cPoint->index != -1) cPoint->color[1] = (float)(cPoint->index % 255)/256.0f;
966                         }
967                 } // end pixel loop
968
969 #endif
970
971                 /*
972                 *       If any effect enabled, create surface effect / wet layer
973                 *       neighbour lists. Processes possibly moving data.
974                 */
975                 if (canvas->effect) {
976
977                         #pragma omp parallel for schedule(static)
978                         for (yy = 0; yy < h; yy++)
979                         {
980                                 int xx;
981                                 for (xx = 0; xx < w; xx++)
982                                 {
983                                         int i;
984                                         PaintSurfacePoint *cPoint = (&surface->point[xx+w*yy]);
985
986                                         /* If current point exists find all it's neighbouring pixels    */
987                                         if (cPoint->index != -1)
988                                         for (i=0; i<8; i++) {
989
990                                                 /* Try to find a neighbouring pixel in defined direction
991                                                 *  If not found, -1 is returned */
992                                                 cPoint->neighbours[i] = dynamicPaint_findNeighbourPixel(canvas, xx, yy, i);
993                                         }
994                                 }
995                         } // end pixel loop
996                 } // effect
997
998                 MEM_freeN(faceBB);
999
1000                 return 1;
1001 }
1002
1003
1004 /*
1005 *       Free canvas surface
1006 */
1007 static void dynamicPaint_cleanCanvasSurface(DynamicPaintCanvasSettings *canvas)
1008 {
1009
1010         int w,h,k;
1011         
1012         if (!canvas) return;
1013         if (!canvas->surface) return;
1014
1015         w = canvas->surface->w;
1016         h = canvas->surface->h;
1017
1018         #pragma omp parallel for schedule(static,1)
1019         for (k = 0; k < w*h; k++)
1020         {
1021                 free(canvas->surface->point[k].barycentricWeights);
1022         }
1023
1024         if (canvas->surface->point) MEM_freeN(canvas->surface->point);
1025         MEM_freeN(canvas->surface);
1026 }
1027
1028 /*  A modified callback to bvh tree raycast. The tree must bust have been built using bvhtree_from_mesh_faces.
1029 *   userdata must be a BVHMeshCallbackUserdata built from the same mesh as the tree.
1030 *  
1031 *       To optimize paint detection speed this doesn't calculate hit coordinates or normal.
1032 *       If ray hit the second half of a quad, no[0] is set to 1.0f.
1033 */
1034 static void mesh_faces_spherecast_dp(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit)
1035 {
1036         const BVHTreeFromMesh *data = (BVHTreeFromMesh*) userdata;
1037         MVert *vert     = data->vert;
1038         MFace *face = data->face + index;
1039         short quad = 0;
1040
1041         float *t0, *t1, *t2, *t3;
1042         t0 = vert[ face->v1 ].co;
1043         t1 = vert[ face->v2 ].co;
1044         t2 = vert[ face->v3 ].co;
1045         t3 = face->v4 ? vert[ face->v4].co : NULL;
1046
1047         do
1048         {       
1049                 float dist;
1050                 dist = ray_tri_intersection(ray, hit->dist, t0, t1, t2);
1051
1052                 if(dist >= 0 && dist < hit->dist)
1053                 {
1054                         hit->index = index;
1055                         hit->dist = dist;
1056                         //VECADDFAC(hit->co, ray->origin, ray->direction, dist);
1057                         //normal_tri_v3( hit->no,t0, t1, t2);
1058                         hit->no[0] = (quad) ? 1.0f : 0.0f;
1059                 }
1060
1061                 t1 = t2;
1062                 t2 = t3;
1063                 t3 = NULL;
1064                 quad = 1;
1065
1066         } while(t2);
1067 }
1068
1069 /* A modified callback to bvh tree nearest point. The tree must bust have been built using bvhtree_from_mesh_faces.
1070 *  userdata must be a BVHMeshCallbackUserdata built from the same mesh as the tree.
1071 *  
1072 *       To optimize paint detection speed this doesn't calculate hit normal.
1073 *       If ray hit the second half of a quad, no[0] is set to 1.0f, else 0.0f
1074 */
1075 static void mesh_faces_nearest_point_dp(void *userdata, int index, const float *co, BVHTreeNearest *nearest)
1076 {
1077         const BVHTreeFromMesh *data = (BVHTreeFromMesh*) userdata;
1078         MVert *vert     = data->vert;
1079         MFace *face = data->face + index;
1080         short quad = 0;
1081
1082         float *t0, *t1, *t2, *t3;
1083         t0 = vert[ face->v1 ].co;
1084         t1 = vert[ face->v2 ].co;
1085         t2 = vert[ face->v3 ].co;
1086         t3 = face->v4 ? vert[ face->v4].co : NULL;
1087
1088         do
1089         {       
1090                 float nearest_tmp[3], dist;
1091                 int vertex, edge;
1092                 
1093                 dist = nearest_point_in_tri_surface(t0, t1, t2, co, &vertex, &edge, nearest_tmp);
1094                 if(dist < nearest->dist)
1095                 {
1096                         nearest->index = index;
1097                         nearest->dist = dist;
1098                         VECCOPY(nearest->co, nearest_tmp);
1099                         //normal_tri_v3( nearest->no,t0, t1, t2);
1100                         nearest->no[0] = (quad) ? 1.0f : 0.0f;
1101                 }
1102
1103                 t1 = t2;
1104                 t2 = t3;
1105                 t3 = NULL;
1106                 quad = 1;
1107
1108         } while(t2);
1109 }
1110
1111
1112 /*
1113 *       Calculate inverse matrices for material related objects
1114 *       in case texture is mapped to an object.
1115 *       (obj->imat isn't auto-updated)
1116 */
1117 static void DynamicPaint_UpdateMaterial(Material *mat)
1118 {
1119         MTex *mtex = NULL;
1120         Tex *tex = NULL;
1121         int tex_nr;
1122
1123         if (mat == NULL) return;
1124
1125         /*
1126         *       Loop through every material texture and check
1127         *       if they are mapped by other object
1128         */
1129         
1130         for(tex_nr=0; tex_nr<MAX_MTEX; tex_nr++) {
1131                 /* separate tex switching */
1132                 if(mat->septex & (1<<tex_nr)) continue;
1133         
1134                 if(mat->mtex[tex_nr]) {
1135                         mtex= mat->mtex[tex_nr];
1136                         tex= mtex->tex;
1137
1138                         if(tex==0) continue;
1139                         
1140                         /* which coords */
1141                         if(mtex->texco==TEXCO_OBJECT) { 
1142                                 Object *ob= mtex->object;
1143                                 if(ob) {                                                
1144                                         invert_m4_m4(ob->imat, ob->obmat);
1145                                 }
1146                         }
1147
1148                 }
1149         }       // end texture loop
1150
1151 }
1152
1153
1154 static void DynamicPaint_InitMaterialObjects(Object *paintOb, Material *ui_mat)
1155 {
1156
1157         /*
1158         *       Calculate inverse transformation matrix
1159         *       for this object
1160         */
1161         invert_m4_m4(paintOb->imat, paintOb->obmat);
1162
1163         /* Now process every material linked to this Paint object,
1164         *  and check if any material uses object mapping. */
1165         if ((ui_mat == NULL) && paintOb->totcol) {
1166                 /* If using materials that are linked to mesh,
1167                 *  check every material linked to this object*/
1168                 int i;
1169
1170                 for (i=0; i<paintOb->totcol; i++) {
1171                                 if (paintOb->matbits[i]) DynamicPaint_UpdateMaterial(paintOb->mat[i]);
1172                         }
1173         }
1174         else {
1175                 DynamicPaint_UpdateMaterial(ui_mat);
1176         }
1177
1178 }
1179         
1180
1181
1182 /* a modified part of shadeinput.c -> shade_input_set_uv() / shade_input_set_shade_texco() */
1183 static void textured_face_generate_uv(float *uv, float *normal, float *hit, float *v1, float *v2, float *v3)
1184 {
1185
1186         float detsh, t00, t10, t01, t11, xn, yn, zn;
1187         int axis1, axis2;
1188
1189         /* find most stable axis to project */
1190         xn= fabs(normal[0]);
1191         yn= fabs(normal[1]);
1192         zn= fabs(normal[2]);
1193
1194         if(zn>=xn && zn>=yn) { axis1= 0; axis2= 1; }
1195         else if(yn>=xn && yn>=zn) { axis1= 0; axis2= 2; }
1196         else { axis1= 1; axis2= 2; }
1197
1198         /* compute u,v and derivatives */
1199         t00= v3[axis1]-v1[axis1]; t01= v3[axis2]-v1[axis2];
1200         t10= v3[axis1]-v2[axis1]; t11= v3[axis2]-v2[axis2];
1201
1202         detsh= 1.0f/(t00*t11-t10*t01);
1203         t00*= detsh; t01*=detsh; 
1204         t10*=detsh; t11*=detsh;
1205
1206         uv[0] = (hit[axis1]-v3[axis1])*t11-(hit[axis2]-v3[axis2])*t10;
1207         uv[1] = (hit[axis2]-v3[axis2])*t00-(hit[axis1]-v3[axis1])*t01;
1208
1209         /* u and v are in range -1 to 0, we allow a little bit extra but not too much, screws up speedvectors */
1210         CLAMP(uv[0], -2.0f, 1.0f);
1211         CLAMP(uv[1], -2.0f, 1.0f);
1212 }
1213
1214 /* a modified part of shadeinput.c -> shade_input_set_uv() / shade_input_set_shade_texco() */
1215 static void textured_face_get_uv(float *uv_co, float *normal, float *uv, int faceIndex, short quad, MTFace *tface)
1216 {
1217         float *uv1, *uv2, *uv3;
1218         float l;
1219
1220         l= 1.0f+uv[0]+uv[1];
1221                 
1222         uv1= tface[faceIndex].uv[0];
1223         uv2= (quad) ? tface[faceIndex].uv[2] : tface[faceIndex].uv[1];
1224         uv3= (quad) ? tface[faceIndex].uv[3] : tface[faceIndex].uv[2];
1225                                 
1226         uv_co[0]= -1.0f + 2.0f*(l*uv3[0]-uv[0]*uv1[0]-uv[1]*uv2[0]);
1227         uv_co[1]= -1.0f + 2.0f*(l*uv3[1]-uv[0]*uv1[1]-uv[1]*uv2[1]);
1228         uv_co[2]= 0.0f; /* texture.c assumes there are 3 coords */
1229 }
1230
1231 /*
1232 *       Edited version of do_material_tex()
1233 *
1234 *       Samples color and alpha from a "Surface" type material
1235 *       on a given point, without need for ShadeInput.
1236 *
1237 *       Keep up-to-date with new mapping settings
1238 *
1239 *       also see shade_input_set_shade_texco() for ORCO settings
1240 *       and shade_input_set_uv() for face uv calculation
1241 */
1242 void DynamicPaint_SampleSolidMaterial(float color[3], float *alpha, Material *mat, Object *paintOb, float xyz[3], int faceIndex, short isQuad, DerivedMesh *orcoDm)
1243 {
1244         MTex *mtex = NULL;
1245         Tex *tex = NULL;
1246         TexResult texres= {0.0f, 0.0f, 0.0f, 0.0f, 0.0f, 0, NULL};
1247         float co[3], xyz_local[3];
1248         float fact, stencilTin=1.0;
1249         float texvec[3];
1250         int tex_nr, rgbnor= 0;
1251         float uv[3], normal[3];
1252         MFace *mface;
1253         int v1, v2, v3;
1254         MVert *mvert;
1255         
1256         /* Get face data        */
1257         mvert = orcoDm->getVertArray(orcoDm);
1258         mface = orcoDm->getFaceArray(orcoDm);
1259         v1=mface[faceIndex].v1, v2=mface[faceIndex].v2, v3=mface[faceIndex].v3;
1260         if (isQuad) {v2=mface[faceIndex].v3; v3=mface[faceIndex].v4;}
1261
1262         normal_tri_v3( normal, mvert[v1].co, mvert[v2].co, mvert[v3].co);
1263
1264         /* Assign material base values  */
1265         color[0] = mat->r;
1266         color[1] = mat->g;
1267         color[2] = mat->b;
1268         *alpha = mat->alpha;
1269
1270         VECCOPY(xyz_local, xyz);
1271         mul_m4_v3(paintOb->imat, xyz_local);
1272
1273         for(tex_nr=0; tex_nr<MAX_MTEX; tex_nr++) {
1274                 
1275                 /* separate tex switching */
1276                 if(mat->septex & (1<<tex_nr)) continue;
1277                 
1278                 if(mat->mtex[tex_nr]) {
1279                         mtex= mat->mtex[tex_nr];
1280                         tex= mtex->tex;
1281                         
1282                         tex= mtex->tex;
1283                         if(tex==0) continue;
1284
1285                         /* which coords */
1286                         if(mtex->texco==TEXCO_ORCO) {
1287                                 float l;
1288
1289                                 /*
1290                                 *       Get generated UV
1291                                 */
1292                                 textured_face_generate_uv(uv, normal, xyz_local, mvert[v1].co, mvert[v2].co, mvert[v3].co);
1293
1294                                 l= 1.0f+uv[0]+uv[1];
1295
1296                                 /* calculate generated coordinate
1297                                 *  ** Keep up-to-date with shadeinput.c -> shade_input_set_shade_texco() **/
1298                                 co[0]= l*mvert[v3].co[0]-uv[0]*mvert[v1].co[0]-uv[1]*mvert[v2].co[0];
1299                                 co[1]= l*mvert[v3].co[1]-uv[0]*mvert[v1].co[1]-uv[1]*mvert[v2].co[1];
1300                                 co[2]= l*mvert[v3].co[2]-uv[0]*mvert[v1].co[2]-uv[1]*mvert[v2].co[2];
1301                         }
1302                         else if(mtex->texco==TEXCO_OBJECT) {
1303                                 Object *ob= mtex->object;
1304
1305                                 VECCOPY(co, xyz);
1306                                 /* convert from world space to paint space */
1307                                 mul_m4_v3(paintOb->imat, co);
1308                                 if(ob) {
1309                                         mul_m4_v3(ob->imat, co);
1310                                 }
1311                         }
1312                         else if(mtex->texco==TEXCO_GLOB) {
1313                                 VECCOPY(co, xyz);
1314                         }
1315                         else if(mtex->texco==TEXCO_UV) {
1316                                 MTFace *tface;
1317
1318                                 /* Get UV layer */
1319                                 if(mtex->uvname[0] != 0) {
1320                                         tface = CustomData_get_layer_named(&orcoDm->faceData, CD_MTFACE, mtex->uvname);
1321                                 }
1322                                 else tface = DM_get_face_data_layer(orcoDm, CD_MTFACE);
1323
1324                                 /* Get generated coordinates to calculate UV from */
1325                                 textured_face_generate_uv(uv, normal, xyz_local, mvert[v1].co, mvert[v2].co, mvert[v3].co);
1326
1327                                 /* Get UV mapping coordinate */
1328                                 textured_face_get_uv(co, normal, uv, faceIndex, isQuad, tface);
1329                         }
1330                         else continue;  /* non-supported types get just skipped:
1331                                                         TEXCO_REFL, TEXCO_NORM, TEXCO_TANGENT
1332                                                         TEXCO_WINDOW, TEXCO_STRAND, TEXCO_STRESS etc.
1333                                                         */
1334
1335                         /* get texture mapping */
1336                         texco_mapping_ext(normal, tex, mtex, co, 0, 0, texvec);
1337
1338                         if(tex->use_nodes && tex->nodetree) {
1339                                 /* No support for nodes (yet). */
1340                                 continue;
1341                         }
1342                         else {
1343                                 rgbnor = multitex_ext(mtex->tex, co, 0, 0, 0, &texres);
1344                         }
1345
1346                         /* texture output */
1347                         if( (rgbnor & TEX_RGB) && (mtex->texflag & MTEX_RGBTOINT)) {
1348                                 texres.tin= (0.35*texres.tr+0.45*texres.tg+0.2*texres.tb);
1349                                 rgbnor-= TEX_RGB;
1350                         }
1351
1352                         /* Negate and stencil masks */
1353                         if(mtex->texflag & MTEX_NEGATIVE) {
1354                                 if(rgbnor & TEX_RGB) {
1355                                         texres.tr= 1.0-texres.tr;
1356                                         texres.tg= 1.0-texres.tg;
1357                                         texres.tb= 1.0-texres.tb;
1358                                 }
1359                                 texres.tin= 1.0-texres.tin;
1360                         }
1361                         if(mtex->texflag & MTEX_STENCIL) {
1362                                 if(rgbnor & TEX_RGB) {
1363                                         fact= texres.ta;
1364                                         texres.ta*= stencilTin;
1365                                         stencilTin*= fact;
1366                                 }
1367                                 else {
1368                                         fact= texres.tin;
1369                                         texres.tin*= stencilTin;
1370                                         stencilTin*= fact;
1371                                 }
1372                         }
1373
1374                         /* mapping */
1375                         if(mtex->mapto & (MAP_COL)) {
1376                                 float tcol[3];
1377                                 
1378                                 /* stencil maps on the texture control slider, not texture intensity value */
1379                                 tcol[0]=texres.tr; tcol[1]=texres.tg; tcol[2]=texres.tb;
1380                                 
1381                                 if((rgbnor & TEX_RGB)==0) {
1382                                         tcol[0]= mtex->r;
1383                                         tcol[1]= mtex->g;
1384                                         tcol[2]= mtex->b;
1385                                 }
1386                                 else if(mtex->mapto & MAP_ALPHA) {
1387                                         texres.tin= stencilTin;
1388                                 }
1389                                 else texres.tin= texres.ta;
1390                                 
1391                                 if(mtex->mapto & MAP_COL) {
1392                                         float colfac= mtex->colfac*stencilTin;
1393                                         texture_rgb_blend(color, tcol, color, texres.tin, colfac, mtex->blendtype);
1394                                 }
1395                         }
1396
1397                         if(mtex->mapto & MAP_VARS) {
1398                                 /* stencil maps on the texture control slider, not texture intensity value */
1399                                 
1400                                 if(rgbnor & TEX_RGB) {
1401                                         if(texres.talpha) texres.tin= texres.ta;
1402                                         else texres.tin= (0.35*texres.tr+0.45*texres.tg+0.2*texres.tb);
1403                                 }
1404
1405                                 if(mtex->mapto & MAP_ALPHA) {
1406                                         float alphafac= mtex->alphafac*stencilTin;
1407
1408                                         *alpha= texture_value_blend(mtex->def_var, *alpha, texres.tin, alphafac, mtex->blendtype);
1409                                         if(*alpha<0.0) *alpha= 0.0;
1410                                         else if(*alpha>1.0) *alpha= 1.0;
1411                                 }
1412                         }
1413                 }
1414         }
1415 }
1416
1417
1418 /*
1419 *       Edited version of texture.c -> do_volume_tex()
1420 *
1421 *       Samples color and density from a volume type texture
1422 *       without need for ShadeInput.
1423 *
1424 *       Keep up-to-date with new mapping settings
1425 */
1426 void DynamicPaint_SampleVolumeMaterial(float color[3], float *alpha, Material *mat, Object *paintOb, float xyz[3])
1427 {
1428
1429         int mapto_flag  = MAP_DENSITY | MAP_REFLECTION_COL | MAP_TRANSMISSION_COL;
1430         float *col = color;
1431
1432         MTex *mtex = NULL;
1433         Tex *tex = NULL;
1434         TexResult texres= {0.0f, 0.0f, 0.0f, 0.0f, 0.0f, 0, NULL};
1435         int tex_nr, rgbnor= 0;
1436         float co[3], texvec[3];
1437         float fact, stencilTin=1.0;
1438
1439         /* set base color */
1440         color[0] = mat->vol.reflection_col[0];
1441         color[1] = mat->vol.reflection_col[1];
1442         color[2] = mat->vol.reflection_col[2];
1443         *alpha = mat->vol.density;
1444         
1445         for(tex_nr=0; tex_nr<MAX_MTEX; tex_nr++) {
1446
1447                 /* separate tex switching */
1448                 if(mat->septex & (1<<tex_nr)) continue;
1449                 
1450                 if(mat->mtex[tex_nr]) {
1451                         mtex= mat->mtex[tex_nr];
1452                         tex= mtex->tex;
1453
1454                         if(tex==0) continue;
1455
1456                         /* only process if this texture is mapped 
1457                                 * to one that we're interested in */
1458                         if (!(mtex->mapto & mapto_flag)) continue;
1459                         texres.nor= NULL;
1460                         
1461                         /* which coords */
1462                         if(mtex->texco==TEXCO_OBJECT) { 
1463                                 Object *ob= mtex->object;
1464                                 ob= mtex->object;
1465                                 if(ob) {                                                
1466                                         VECCOPY(co, xyz);
1467                                         mul_m4_v3(ob->imat, co);
1468                                 }
1469                         }
1470                         else if(mtex->texco==TEXCO_ORCO) {
1471                                 
1472                                 {
1473                                         Object *ob= paintOb;
1474                                         VECCOPY(co, xyz);
1475                                         mul_m4_v3(ob->imat, co);
1476                                 }
1477                         }
1478                         else if(mtex->texco==TEXCO_GLOB) {                                                      
1479                                 VECCOPY(co, xyz);
1480                         }
1481                         else continue;  /* Skip unsupported types */
1482                         
1483
1484                         if(tex->type==TEX_IMAGE) {
1485                                 continue;       /* not supported yet */                         
1486                         }
1487                         else {
1488                                 /* placement */
1489                                 if(mtex->projx) texvec[0]= mtex->size[0]*(co[mtex->projx-1]+mtex->ofs[0]);
1490                                 else texvec[0]= mtex->size[0]*(mtex->ofs[0]);
1491
1492                                 if(mtex->projy) texvec[1]= mtex->size[1]*(co[mtex->projy-1]+mtex->ofs[1]);
1493                                 else texvec[1]= mtex->size[1]*(mtex->ofs[1]);
1494
1495                                 if(mtex->projz) texvec[2]= mtex->size[2]*(co[mtex->projz-1]+mtex->ofs[2]);
1496                                 else texvec[2]= mtex->size[2]*(mtex->ofs[2]);
1497                         }
1498                         rgbnor= multitex_ext(tex, texvec, NULL, NULL, 0, &texres);
1499                         
1500                         /* texture output */
1501                         if( (rgbnor & TEX_RGB) && (mtex->texflag & MTEX_RGBTOINT)) {
1502                                 texres.tin= (0.35*texres.tr+0.45*texres.tg+0.2*texres.tb);
1503                                 rgbnor-= TEX_RGB;
1504                         }
1505
1506                         /* Negate and stencil */
1507                         if(mtex->texflag & MTEX_NEGATIVE) {
1508                                 if(rgbnor & TEX_RGB) {
1509                                         texres.tr= 1.0-texres.tr;
1510                                         texres.tg= 1.0-texres.tg;
1511                                         texres.tb= 1.0-texres.tb;
1512                                 }
1513                                 texres.tin= 1.0-texres.tin;
1514                         }
1515                         if(mtex->texflag & MTEX_STENCIL) {
1516                                 if(rgbnor & TEX_RGB) {
1517                                         fact= texres.ta;
1518                                         texres.ta*= stencilTin;
1519                                         stencilTin*= fact;
1520                                 }
1521                                 else {
1522                                         fact= texres.tin;
1523                                         texres.tin*= stencilTin;
1524                                         stencilTin*= fact;
1525                                 }
1526                         }
1527                         
1528                         /* Map values */
1529                         if((mapto_flag & (MAP_EMISSION_COL+MAP_TRANSMISSION_COL+MAP_REFLECTION_COL)) && (mtex->mapto & (MAP_EMISSION_COL+MAP_TRANSMISSION_COL+MAP_REFLECTION_COL))) {
1530                                 float tcol[3];
1531                                 
1532                                 /* stencil maps on the texture control slider, not texture intensity value */
1533                 
1534                                 if((rgbnor & TEX_RGB)==0) {
1535                                         tcol[0]= mtex->r;
1536                                         tcol[1]= mtex->g;
1537                                         tcol[2]= mtex->b;
1538                                 } else {
1539                                         tcol[0]=texres.tr;
1540                                         tcol[1]=texres.tg;
1541                                         tcol[2]=texres.tb;
1542                                         if(texres.talpha)
1543                                                 texres.tin= texres.ta;
1544                                 }
1545                                 
1546                                 /* used for emit */
1547                                 if((mapto_flag & MAP_EMISSION_COL) && (mtex->mapto & MAP_EMISSION_COL)) {
1548                                         float colemitfac= mtex->colemitfac*stencilTin;
1549                                         texture_rgb_blend(col, tcol, col, texres.tin, colemitfac, mtex->blendtype);
1550                                 }
1551                                 
1552                                 if((mapto_flag & MAP_REFLECTION_COL) && (mtex->mapto & MAP_REFLECTION_COL)) {
1553                                         float colreflfac= mtex->colreflfac*stencilTin;
1554                                         texture_rgb_blend(col, tcol, col, texres.tin, colreflfac, mtex->blendtype);
1555                                 }
1556                                 
1557                                 if((mapto_flag & MAP_TRANSMISSION_COL) && (mtex->mapto & MAP_TRANSMISSION_COL)) {
1558                                         float coltransfac= mtex->coltransfac*stencilTin;
1559                                         texture_rgb_blend(col, tcol, col, texres.tin, coltransfac, mtex->blendtype);
1560                                 }
1561                         }
1562                         
1563                         if((mapto_flag & MAP_VARS) && (mtex->mapto & MAP_VARS)) {
1564                                 /* stencil maps on the texture control slider, not texture intensity value */
1565                                 
1566                                 /* convert RGB to intensity if intensity info isn't provided */
1567                                 if (!(rgbnor & TEX_INT)) {
1568                                         if (rgbnor & TEX_RGB) {
1569                                                 if(texres.talpha) texres.tin= texres.ta;
1570                                                 else texres.tin= (0.35*texres.tr+0.45*texres.tg+0.2*texres.tb);
1571                                         }
1572                                 }
1573                                 if((mapto_flag & MAP_DENSITY) && (mtex->mapto & MAP_DENSITY)) {
1574                                         float densfac= mtex->densfac*stencilTin;
1575
1576                                         *alpha = texture_value_blend(mtex->def_var, *alpha, texres.tin, densfac, mtex->blendtype);
1577                                         CLAMP(*alpha, 0.0, 1.0);
1578                                 }
1579                         }
1580                 }
1581         }
1582 }
1583
1584 /*
1585 *       Get material (including linked textures) diffuse color and alpha in given coordinates
1586 *       
1587 *       color,paint : input/output color values
1588 *       pixelCoord : canvas pixel coordinates in global space. used if material is volumetric
1589 *
1590 *       paintHit : point on paint object surface in global space. used by "surface" type materials
1591 *       faceIndex : paintHit face index
1592 *       orcoDm : orco state derived mesh of paint object
1593 *       ui_mat : force material. if NULL, material linked to paintOb mesh is used.
1594 *
1595 *       *"paint object" = object to sample material color from
1596 */
1597 void DynamicPaint_GetMaterialColor(float *color, float *alpha, Object *paintOb, float pixelCoord[3], float paintHit[3], int faceIndex, short isQuad, DerivedMesh *orcoDm, Material *ui_mat)
1598 {
1599
1600         Material *material = ui_mat;
1601
1602         /*
1603         *       Get face material
1604         */
1605         if (material == NULL) {
1606                 MFace *mface = NULL;
1607                 mface = orcoDm->getFaceArray(orcoDm);
1608                 material = give_current_material(paintOb, mface[faceIndex].mat_nr+1);
1609
1610                 if (material == NULL) return;   /* No material assigned */
1611         }
1612
1613         /*
1614         *       Sample textured material color in given position depending on material type
1615         */
1616         if (material->material_type == MA_TYPE_SURFACE) {
1617                 /* Solid material */
1618                 DynamicPaint_SampleSolidMaterial(color, alpha, material, paintOb, paintHit, faceIndex, isQuad, orcoDm);
1619         }
1620         else if (material->material_type == MA_TYPE_VOLUME) {
1621                 /* Volumetric material */
1622                 DynamicPaint_SampleVolumeMaterial(color, alpha, material, paintOb, pixelCoord);
1623         }
1624         else if (material->material_type == MA_TYPE_HALO) {
1625                 /* Halo type not supported */
1626         }
1627 }
1628
1629
1630 /*
1631 *       Mix color values to canvas point.
1632 *
1633 *       cPoint : canvas surface point to do the changes
1634 *       paintFlags : paint object flags
1635 *   paintColor,Alpha,Wetness : to be mixed paint values
1636 *
1637 *       timescale : value used to adjust time dependand
1638 *                           operations when using substeps
1639 */
1640 void DynamicPaint_MixPaintColors(PaintSurfacePoint *cPoint, int paintFlags, float *paintColor, float *paintAlpha, float *paintWetness, float *timescale)
1641 {
1642
1643         /* Add paint    */
1644         if (!(paintFlags & MOD_DPAINT_ERASE)) {
1645                 float wetness;
1646
1647                 /* If point has previous paint  */
1648                 if (cPoint->e_alpha > 0)
1649                 {
1650                         /*
1651                         *       Mix colors by the factor, use timescale
1652                         */
1653                         float factor = (*paintAlpha) * (*timescale);
1654                         float invFact = 1.0f - factor;
1655                         cPoint->e_color[0] = cPoint->e_color[0]*invFact + paintColor[0]*factor;
1656                         cPoint->e_color[1] = cPoint->e_color[1]*invFact + paintColor[1]*factor;
1657                         cPoint->e_color[2] = cPoint->e_color[2]*invFact + paintColor[2]*factor;
1658                 }
1659                 else
1660                 {
1661                         /* else set first color value straight to paint color   */
1662                         cPoint->e_color[0] = paintColor[0];
1663                         cPoint->e_color[1] = paintColor[1];
1664                         cPoint->e_color[2] = paintColor[2];
1665                 }
1666
1667                 /* alpha */
1668                 if (paintFlags & MOD_DPAINT_ABS_ALPHA) {
1669                         if (cPoint->e_alpha < (*paintAlpha)) cPoint->e_alpha = (*paintAlpha);
1670                 }
1671                 else {
1672                         cPoint->e_alpha += (*paintAlpha) * (*timescale);
1673                         if (cPoint->e_alpha > 1.0f) cPoint->e_alpha = 1.0f;
1674                 }
1675
1676                 /* only increase wetness if it's below paint level      */
1677                 wetness = (*paintWetness) * cPoint->e_alpha;
1678                 if (cPoint->wetness < wetness) cPoint->wetness = wetness;
1679         }
1680         /* Erase paint  */
1681         else {
1682                 float a_ratio, a_highest;
1683                 float wetness;
1684                 float invFact = 1.0f - (*paintAlpha);
1685
1686                 /*
1687                 *       Make highest alpha to match erased value
1688                 *       but maintain alpha ratio
1689                 */
1690                 if (paintFlags & MOD_DPAINT_ABS_ALPHA) {
1691                         a_highest = (cPoint->e_alpha > cPoint->alpha) ? cPoint->e_alpha : cPoint->alpha;
1692                         if (a_highest > invFact) {
1693                                 a_ratio = invFact / a_highest;
1694
1695                                 cPoint->e_alpha *= a_ratio;
1696                                 cPoint->alpha *= a_ratio;
1697                         }
1698                 }
1699                 else {
1700                         cPoint->e_alpha -= (*paintAlpha) * (*timescale);
1701                         if (cPoint->e_alpha < 0.0f) cPoint->e_alpha = 0.0f;
1702                         cPoint->alpha -= (*paintAlpha) * (*timescale);
1703                         if (cPoint->alpha < 0.0f) cPoint->alpha = 0.0f;
1704                 }
1705
1706                 wetness = (1.0f - (*paintWetness)) * cPoint->e_alpha;
1707                 if (cPoint->wetness > wetness) cPoint->wetness = wetness;
1708         }
1709 }
1710
1711
1712 /*
1713 *       Paint an object mesh to canvas
1714 */
1715 static int DynamicPaint_PaintMesh(DynamicPaintCanvasSettings *canvas, Vec3f *canvasVerts, DynamicPaintPainterSettings *paint, Object *canvasOb, Object *paintOb, float timescale)
1716 {
1717         DerivedMesh *dm = NULL;
1718         MVert *mvert = NULL;
1719         MFace *mface = NULL;
1720         PaintSurface *surface = canvas->surface;
1721
1722         if (!paint->dm) {
1723                 printf("DynamicPaint: Invalid paint dm.\n");
1724                 return 0;
1725         }
1726
1727         /* If using material color, we prepare required stuff on texture related objects first  */
1728         if (paint->flags & MOD_DPAINT_USE_MATERIAL) DynamicPaint_InitMaterialObjects(paintOb, paint->mat);
1729
1730         {
1731                 BVHTreeFromMesh treeData = {0};
1732                 int yy;
1733                 int tWidth = surface->w;
1734                 int tHeight = surface->h;
1735
1736                 int numOfVerts;
1737                 int ii;
1738
1739                 /*
1740                 *       Transform collider vertices to world space
1741                 *       (Faster than transforming per pixel
1742                 *   coordinates and normals to object space)
1743                 */
1744                 dm = CDDM_copy(paint->dm);
1745                 mvert = dm->getVertArray(dm);
1746                 mface = dm->getFaceArray(dm);
1747                 numOfVerts = dm->getNumVerts(dm);
1748
1749                 for (ii=0; ii<numOfVerts; ii++) {
1750                         mul_m4_v3(paintOb->obmat, mvert[ii].co);
1751                 }
1752
1753                 /* Build a bvh tree from transformed vertices   */
1754                 bvhtree_from_mesh_faces(&treeData, dm, 0.0f, 4, 6);
1755
1756                 if(treeData.tree) {
1757                         #pragma omp parallel for schedule(static)
1758                         for (yy = 0; yy < tHeight; yy++)
1759                         {
1760                                 int xx,i;
1761                                 for (xx = 0; xx < tWidth; xx++)
1762                                 {
1763                                         PaintSurfacePoint *cPoint = (&surface->point[xx+tWidth*yy]);
1764                                         i = cPoint->index;
1765
1766                                         if (i >= 0)
1767                                         {
1768                                                 int ss;
1769                                                 float ssFactor = 0.0f;  /* super-sampling factor */
1770                                                 float depth = 0.0f;             /* displace depth */
1771
1772                                                 float paintColor[3] = {0.0f, 0.0f, 0.0f};
1773                                                 int numOfHits = 0;
1774                                                 float paintAlpha = 0.0f;
1775
1776                                                 /* Supersampling        */
1777                                                 for (ss=0; ss<surface->pixelSamples; ss++) {
1778
1779                                                         float ray_start[3], ray_dir[3];
1780                                                         float gaus_factor;
1781                                                         BVHTreeRayHit hit;
1782                                                         BVHTreeNearest nearest;
1783                                                         short hit_found = 0;
1784                                                         float realPos[3];
1785
1786                                                         /* If it's a proximity hit, store distance rate */
1787                                                         float distRate = -1.0f;
1788
1789                                                         /* hit data     */
1790                                                         float hitCoord[3];              /* mid-sample hit coordinate */
1791                                                         int hitFace = -1;               /* mid-sample hit face */
1792                                                         short hitQuad;                  /* mid-sample hit quad status */
1793
1794                                                         /* Supersampling factor */
1795                                                         if (surface->pixelSamples > 1) {
1796                                                                 gaus_factor = gaussianFactors[ss];
1797                                                         }
1798                                                         else {
1799                                                                 gaus_factor = 1.0f;
1800                                                         }
1801
1802                                                         /* Get current sample position in world coordinates     */
1803                                                         interp_v3_v3v3v3(realPos,
1804                                                                                         canvasVerts[cPoint->v1].v,
1805                                                                                         canvasVerts[cPoint->v2].v,
1806                                                                                         canvasVerts[cPoint->v3].v, cPoint->barycentricWeights[ss].v);
1807                                                         VECCOPY(ray_start, realPos);
1808                                                         VECCOPY(ray_dir, cPoint->invNorm);
1809
1810                                                         hit.index = -1;
1811                                                         hit.dist = 9999;
1812                                                         nearest.index = -1;
1813                                                         nearest.dist = paint->paint_distance * paint->paint_distance; /* find_nearest search uses squared distance */
1814
1815                                                         /* Check volume collision       */
1816                                                         if (paint->collision == MOD_DPAINT_COL_VOLUME || paint->collision == MOD_DPAINT_COL_VOLDIST)
1817                                                         if(BLI_bvhtree_ray_cast(treeData.tree, ray_start, ray_dir, 0.0f, &hit, mesh_faces_spherecast_dp, &treeData) != -1)
1818                                                         {
1819                                                                 /* We hit a triangle, now check if collision point normal is facing the point   */
1820
1821
1822                                                                 /*      For optimization sake, hit point normal isn't calculated in ray cast loop       */
1823                                                                 int v1=mface[hit.index].v1, v2=mface[hit.index].v2, v3=mface[hit.index].v3, quad=(hit.no[0] == 1.0f);
1824                                                                 float dot;
1825
1826                                                                 if (quad) {v2=mface[hit.index].v3; v3=mface[hit.index].v4;}
1827                                                         
1828                                                                 /* Get hit normal       */
1829                                                                 normal_tri_v3( hit.no, mvert[v1].co, mvert[v2].co, mvert[v3].co);
1830                                                                 dot = ray_dir[0]*hit.no[0] + ray_dir[1]*hit.no[1] + ray_dir[2]*hit.no[2];
1831
1832                                                                 /*
1833                                                                 *       If ray and hit normal are facing same direction
1834                                                                 *       hit point is inside a closed mesh.
1835                                                                 */
1836                                                                 if (dot>=0)
1837                                                                 {
1838                                                                         /* Add factor on supersample filter     */
1839                                                                         ssFactor += gaus_factor;
1840                                                                         depth += hit.dist;
1841                                                                         hit_found = 1;
1842
1843                                                                         /*
1844                                                                         *       Mark hit info
1845                                                                         */
1846                                                                         if (hitFace == -1) {
1847                                                                                 VECADDFAC(hitCoord, ray_start, ray_dir, hit.dist);      /* Calculate final hit coordinates */
1848                                                                                 hitQuad = quad;
1849                                                                                 hitFace = hit.index;
1850                                                                         }
1851                                                                 }
1852                                                         }       // end of raycast
1853                                                 
1854                                                         /* Check proximity collision    */
1855                                                         if ((paint->collision == MOD_DPAINT_COL_DIST || paint->collision == MOD_DPAINT_COL_VOLDIST) && (!hit_found))
1856                                                         {
1857                                                                 float proxDist = -1.0f;
1858                                                                 float hitCo[3];
1859                                                                 short hQuad;
1860                                                                 int face;
1861
1862                                                                 /*
1863                                                                 *       If pure distance proximity, find the nearest point on the mesh
1864                                                                 */
1865                                                                 if (!(paint->flags & MOD_DPAINT_PROX_FACEALIGNED)) {
1866                                                                         if (BLI_bvhtree_find_nearest(treeData.tree, ray_start, &nearest, mesh_faces_nearest_point_dp, &treeData) != -1) {
1867                                                                                 proxDist = sqrt(nearest.dist);  /* find_nearest returns a squared distance, so gotta change it back to real distance */
1868                                                                                 copy_v3_v3(hitCo, nearest.co);
1869                                                                                 hQuad = (nearest.no[0] == 1.0f);
1870                                                                                 face = nearest.index;
1871                                                                         }
1872                                                                 }
1873                                                                 else { /*  else cast a ray in surface normal direction  */
1874                                                                         negate_v3(ray_dir);
1875                                                                         hit.index = -1;
1876                                                                         hit.dist = paint->paint_distance;
1877
1878                                                                         /* Do a face normal directional raycast, and use that distance  */
1879                                                                         if(BLI_bvhtree_ray_cast(treeData.tree, ray_start, ray_dir, 0.0f, &hit, mesh_faces_spherecast_dp, &treeData) != -1)
1880                                                                         {
1881                                                                                 proxDist = hit.dist;
1882                                                                                 VECADDFAC(hitCo, ray_start, ray_dir, hit.dist); /* Calculate final hit coordinates */
1883                                                                                 hQuad = (hit.no[0] == 1.0f);
1884                                                                                 face = hit.index;
1885                                                                         }
1886                                                                 }
1887
1888                                                                 /* If a hit was found, calculate required values        */
1889                                                                 if (proxDist >= 0.0f) {
1890                                                                         float dist_rate = proxDist / paint->paint_distance;
1891
1892                                                                                 /* Smooth range or color ramp   */
1893                                                                                 if (paint->proximity_falloff == MOD_DPAINT_PRFALL_SMOOTH ||
1894                                                                                         paint->proximity_falloff == MOD_DPAINT_PRFALL_RAMP) {
1895
1896                                                                                         /* Limit distance to 0.0 - 1.0 */
1897                                                                                         if (dist_rate > 1.0f) dist_rate = 1.0f;
1898                                                                                         if (dist_rate < 0.0f) dist_rate = 0.0f;
1899
1900                                                                                         /* if using smooth falloff, multiply gaussian factor */
1901                                                                                         if (paint->proximity_falloff == MOD_DPAINT_PRFALL_SMOOTH) {
1902                                                                                                 ssFactor += (1.0f - dist_rate) * gaus_factor;
1903                                                                                         }
1904                                                                                         else ssFactor += gaus_factor;
1905
1906                                                                                         if (hitFace == -1) {
1907                                                                                                 distRate = dist_rate;
1908                                                                                         }
1909                                                                                 }
1910                                                                                 else ssFactor += gaus_factor;
1911
1912                                                                                 hit_found = 1;
1913
1914                                                                                 if (hitFace == -1) {
1915                                                                                         copy_v3_v3(hitCoord, hitCo);
1916                                                                                         hitQuad = hQuad;
1917                                                                                         hitFace = face;
1918                                                                                 }
1919                                                                 }       // proxDist
1920                                                         }       // end proximity check
1921
1922                                                         /*
1923                                                         *       Process color and alpha
1924                                                         */
1925                                                         if (hit_found)
1926                                                         {
1927                                                                 float sampleColor[3];
1928                                                                 float sampleAlpha = 1.0f;
1929                                                                 float bandres[4];
1930
1931                                                                 sampleColor[0] = paint->r;
1932                                                                 sampleColor[1] = paint->g;
1933                                                                 sampleColor[2] = paint->b;
1934                                                         
1935                                                                 /* Get material+textures color on hit point if required */
1936                                                                 if (paint->flags & MOD_DPAINT_USE_MATERIAL) DynamicPaint_GetMaterialColor(sampleColor, &sampleAlpha, paintOb, realPos, hitCoord, hitFace, hitQuad, paint->dm, paint->mat);
1937
1938                                                                 /* Sample colorband if required */
1939                                                                 if ((distRate >= 0.0f) && (paint->proximity_falloff == MOD_DPAINT_PRFALL_RAMP) && do_colorband(paint->paint_ramp, distRate, bandres)) {
1940                                                                         if (!(paint->flags & MOD_DPAINT_RAMP_ALPHA)) {
1941                                                                                 sampleColor[0] = bandres[0];
1942                                                                                 sampleColor[1] = bandres[1];
1943                                                                                 sampleColor[2] = bandres[2];
1944                                                                         }
1945                                                                         sampleAlpha *= bandres[3];
1946                                                                 }
1947
1948                                                                 /* Add AA sample        */
1949                                                                 paintColor[0] += sampleColor[0];
1950                                                                 paintColor[1] += sampleColor[1];
1951                                                                 paintColor[2] += sampleColor[2];
1952
1953                                                                 paintAlpha += sampleAlpha;
1954                                                                 numOfHits++;
1955                                                         }
1956                                                 } // end supersampling
1957
1958
1959                                                 /* if any sample was inside paint range */
1960                                                 if (ssFactor > 0.01f) {
1961
1962                                                         /* apply supersampling results  */
1963                                                         if (surface->pixelSamples > 1) {
1964                                                                 ssFactor /= gaussianTotal;
1965                                                         }
1966
1967                                                         cPoint->state = 2;
1968
1969                                                         if (paint->flags & MOD_DPAINT_DO_PAINT) {
1970
1971                                                                 float paintWetness = paint->wetness * ssFactor;
1972
1973                                                                 /* Get final pixel color and alpha      */
1974                                                                 paintColor[0] /= numOfHits;
1975                                                                 paintColor[1] /= numOfHits;
1976                                                                 paintColor[2] /= numOfHits;
1977                                                                 paintAlpha /= numOfHits;
1978
1979                                                                 /* Multiply alpha value by the ui multiplier    */
1980                                                                 paintAlpha = paintAlpha * ssFactor * paint->alpha;
1981                                                                 if (paintAlpha > 1.0f) paintAlpha = 1.0f;
1982
1983                                                                 /*
1984                                                                 *       Mix paint to the surface
1985                                                                 */
1986                                                                 DynamicPaint_MixPaintColors(cPoint, paint->flags, paintColor, &paintAlpha, &paintWetness, &timescale);
1987                                                         }
1988
1989                                                         if (paint->flags & MOD_DPAINT_DO_DISPLACE) {
1990
1991                                                                 if (paint->flags & MOD_DPAINT_ERASE) {
1992                                                                         cPoint->depth *= (1.0f - ssFactor);
1993                                                                         if (cPoint->depth < 0.0f) cPoint->depth = 0.0f;
1994                                                                 }
1995                                                                 else {
1996                                                                         float normal_scale, tempNorm[3];
1997                                                                         /*
1998                                                                         *       Calculate normal directional scale of canvas object.
1999                                                                         *       (Displace maps work in object space)
2000                                                                         */
2001                                                                         MVert *canMvert = NULL;
2002                                                                         canMvert = canvas->dm->getVertArray(canvas->dm);
2003                                                                         normal_tri_v3( tempNorm, canMvert[cPoint->v1].co, canMvert[cPoint->v2].co, canMvert[cPoint->v3].co);
2004                                                                         mul_v3_v3 (tempNorm, canvasOb->size);
2005                                                                         normal_scale = len_v3(tempNorm);
2006                                                                         if (normal_scale<0.01) normal_scale = 0.01;
2007
2008                                                                         depth /= canvas->disp_depth * surface->pixelSamples * normal_scale;
2009                                                                         /* do displace  */
2010                                                                         if (cPoint->depth < depth) cPoint->depth = depth;
2011                                                                 }
2012                                                         }
2013                                                 }
2014                                         } // end i>0
2015                                 } // yy
2016                         } // end of pixel loop
2017                 } // end if tree exists
2018
2019                 /* free bhv tree */
2020                 free_bvhtree_from_mesh(&treeData);
2021                 dm->release(dm);
2022
2023         }
2024
2025         return 1;
2026 }
2027
2028
2029
2030 /*
2031 *       Paint a particle system to canvas
2032 */
2033 static int DynamicPaint_PaintParticles(DynamicPaintCanvasSettings *canvas, ParticleSystem *psys, DynamicPaintPainterSettings *paint, Object *canvasOb, float timescale)
2034 {
2035         int yy;
2036         ParticleSettings *part=psys->part;
2037         ParticleData *pa = NULL;
2038         PaintSurface *surface = canvas->surface;
2039
2040         int tWidth = surface->w;
2041         int tHeight = surface->h;
2042         KDTree *tree;
2043         int particlesAdded = 0;
2044         int invalidParticles = 0;
2045         int p = 0;
2046
2047         if (psys->totpart < 1) return 1;
2048
2049         /*
2050         *       Build a kd-tree to optimize distance search
2051         */
2052         tree= BLI_kdtree_new(psys->totpart);
2053
2054         /* loop through particles and insert valid ones to the tree     */
2055         for(p=0, pa=psys->particles; p<psys->totpart; p++, pa++)        {
2056
2057                 /* Proceed only if particle is active   */
2058                 if(pa->alive == PARS_UNBORN && (part->flag & PART_UNBORN)==0) continue;                                                                 
2059                 else if(pa->alive == PARS_DEAD && (part->flag & PART_DIED)==0) continue;                                                                        
2060                 else if(pa->flag & PARS_NO_DISP || pa->flag & PARS_UNEXIST) continue;
2061
2062                 /*      for debug purposes check if any NAN particle proceeds
2063                 *       For some reason they get past activity check, this should rule most of them out */
2064                 if (isnan(pa->state.co[0]) || isnan(pa->state.co[1]) || isnan(pa->state.co[2])) {invalidParticles++;continue;}
2065
2066                 BLI_kdtree_insert(tree, p, pa->state.co, NULL);
2067                 particlesAdded++;
2068         }
2069
2070
2071         if (invalidParticles) {
2072                 printf("Warning: Invalid particle(s) found!\n");
2073         }
2074
2075         /* If no suitable particles were found, exit    */
2076         if (particlesAdded < 1) {
2077                 BLI_kdtree_free(tree);
2078                 return 1;
2079         }
2080
2081         /* balance tree */
2082         BLI_kdtree_balance(tree);
2083
2084
2085         /*
2086         *       Loop through every pixel
2087         */
2088         #pragma omp parallel for schedule(static)
2089         for (yy = 0; yy < tHeight; yy++)
2090         {
2091                 int xx;
2092                 for (xx = 0; xx < tWidth; xx++) {
2093
2094                         int index = xx+tWidth*yy;
2095                         PaintSurfacePoint *cPoint = (&surface->point[index]);
2096                         int i = cPoint->index;
2097
2098                         /* If this canvas point exists  */
2099                         if (i >= 0)
2100                         {
2101                                 int index;
2102                                 float disp_intersect = 0;
2103                                 float radius;
2104                                 float solidradius = paint->particle_radius;
2105                                 float smooth = paint->particle_smooth;
2106                                 float strength = 0.0f;
2107
2108                                 /* If using per particle radius */
2109                                 if (paint->flags & MOD_DPAINT_PART_RAD) {
2110                                         /*
2111                                         *       If we use per particle radius, we have to sample all particles
2112                                         *       within max radius range
2113                                         */
2114                                         KDTreeNearest *nearest = NULL;
2115                                         int n, particles = 0;
2116                                         float range = psys->part->size + smooth;
2117
2118                                         particles = BLI_kdtree_range_search(tree, range, cPoint->realCoord, NULL, &nearest);
2119                                         for(n=0; n<particles; n++) {
2120
2121                                                 /*
2122                                                 *       Find particle that produces highest influence
2123                                                 */
2124                                                 ParticleData *pa = psys->particles + nearest[n].index;
2125                                                 float rad = pa->size + smooth;
2126                                                 float str,smooth_range;
2127
2128                                                 if (nearest[n].dist > rad) continue; /* if outside range, continue to next one */
2129
2130                                                 if ((rad-nearest[n].dist) > disp_intersect) {
2131                                                         disp_intersect = rad-nearest[n].dist;
2132                                                         radius = rad;
2133                                                 }
2134
2135                                                 /* Continue with paint check    */
2136                                                 if (nearest[n].dist < pa->size) {
2137                                                         /*
2138                                                         *       If particle is inside the solid range, no need to continue further
2139                                                         *       since no other particle can have higher influence
2140                                                         */
2141                                                         strength = 1.0f;
2142                                                         break;
2143                                                 }
2144
2145                                                 smooth_range = (nearest[n].dist - pa->size);
2146
2147                                                 /* do smoothness if enabled     */
2148                                                 if (smooth) smooth_range/=smooth;
2149                                                 str = 1.0f - smooth_range;
2150
2151                                                 /* if influence is greater, use this one        */
2152                                                 if (str > strength) strength = str;
2153
2154                                         }       // end particle loop
2155
2156                                         if (nearest) MEM_freeN(nearest);
2157
2158                                 }
2159                                 else {
2160                                         /*
2161                                         *       With predefined radius, there is no variation between particles.
2162                                         *       It's enough to just find the nearest one.
2163                                         */
2164                                         KDTreeNearest nearest;
2165                                         float smooth_range;
2166                                         radius = solidradius + smooth;
2167
2168                                         /* Find nearest particle and get distance to it */
2169                                         index = BLI_kdtree_find_nearest(tree, cPoint->realCoord, NULL, &nearest);
2170                                         if (nearest.dist > radius) continue;
2171
2172                                         /* distances inside solid radius have maximum influence -> dist = 0     */
2173                                         smooth_range = (nearest.dist - solidradius);
2174                                         if (smooth_range<0) smooth_range=0.0f;
2175
2176                                         /* do smoothness if enabled     */
2177                                         if (smooth) smooth_range/=smooth;
2178
2179                                         strength = 1.0f - smooth_range;
2180                                         disp_intersect = radius - nearest.dist;
2181                                 }
2182
2183                                 if (strength <= 0.0f) continue;
2184
2185                                 cPoint->state = 2;
2186
2187                                 if (paint->flags & MOD_DPAINT_DO_PAINT) {
2188
2189                                         float paintAlpha = paint->alpha * strength;
2190                                         float paintWetness = paint->wetness * strength;
2191                                         float paintColor[3];
2192
2193                                         paintColor[0] = paint->r;
2194                                         paintColor[1] = paint->g;
2195                                         paintColor[2] = paint->b;
2196
2197                                         if (paintAlpha > 1.0f) paintAlpha = 1.0f;
2198
2199                                         DynamicPaint_MixPaintColors(cPoint, paint->flags, paintColor, &paintAlpha, &paintWetness, &timescale);
2200
2201                                 }
2202
2203                                 if (paint->flags & MOD_DPAINT_DO_WETNESS) {
2204                                         if (cPoint->wetness < (paint->wetness*strength)) cPoint->wetness = paint->wetness*strength;
2205                                 }
2206
2207                                 if (paint->flags & MOD_DPAINT_DO_DISPLACE) {
2208                                         float sdepth, disp, normal_scale, tempNorm[3];
2209                                         MVert *canMvert = NULL;
2210                                         canMvert = canvas->dm->getVertArray(canvas->dm);
2211
2212                                         /*
2213                                         *       Calculate normal directional scale of canvas object.
2214                                         *       (Displace maps work in object space)
2215                                         */
2216                                         normal_tri_v3( tempNorm, canMvert[cPoint->v1].co, canMvert[cPoint->v2].co, canMvert[cPoint->v3].co);
2217                                         mul_v3_v3 (tempNorm, canvasOb->size);
2218                                         normal_scale = len_v3(tempNorm);
2219                                         if (normal_scale<0.01) normal_scale = 0.01;
2220
2221                                         /* change falloff type to inverse square to match real displace depth   */
2222                                         disp_intersect = (1.0f - sqrt(disp_intersect / radius)) * radius;
2223                                                 
2224                                         /* get displace depth   */
2225                                         sdepth = (radius - disp_intersect) / normal_scale;
2226
2227                                         if (sdepth<0.0f) sdepth = 0.0f;
2228                                         disp = sdepth / canvas->disp_depth;
2229                                         if (cPoint->depth < disp) cPoint->depth = disp;
2230                                 }
2231                         }
2232                 }
2233         }
2234
2235         BLI_kdtree_free(tree);
2236
2237         return 1;
2238 }
2239
2240
2241 /*
2242 *       Prepare data required by effects for current frame.
2243 *       Returns number of steps required
2244 */
2245 static int DynamicPaint_Prepare_EffectStep(DynamicPaintCanvasSettings *canvas, float timescale)
2246 {
2247         double average_dist = 0.0f;
2248         float minimum_dist = 9999.0f;
2249         unsigned int count = 0;
2250         int steps = 1;
2251         PaintSurface *surface = canvas->surface;
2252         int yy, w=surface->w, h=surface->h;
2253
2254         float fastest_effect, speed_factor;
2255
2256         /*
2257         *       Calculate current frame neighbouring pixel distances
2258         *       and average distance between those neighbours
2259         */
2260         #pragma omp parallel for schedule(static)
2261         for (yy = 0; yy < h; yy++)
2262         {
2263                 int xx;
2264                 for (xx = 0; xx < w; xx++)
2265                 {
2266                         int i;
2267                         PaintSurfacePoint *cPoint = (&surface->point[xx+w*yy]);
2268
2269                         if (cPoint->index != -1)
2270                         for (i=0; i<8; i++) {
2271                                 int x,y, index;
2272                                 PaintSurfacePoint *tPoint;
2273
2274                                 x = xx + neighX[i];
2275                                 y = yy + neighY[i];
2276
2277                                 index = x+w*y;
2278                                 if (cPoint->neighbours[i] != -1) {
2279
2280                                         tPoint = (&surface->point[index]);
2281                                         cPoint->neighbour_dist[i] = len_v3v3(cPoint->realCoord, tPoint->realCoord);
2282                                         if (cPoint->neighbour_dist[i] < minimum_dist) minimum_dist = cPoint->neighbour_dist[i];
2283
2284                                         average_dist += cPoint->neighbour_dist[i];
2285                                         count++;
2286                                 }
2287                         }
2288                 }
2289
2290         } // end pixel loop
2291                         
2292         /*
2293         *       Note: some other method could be better
2294         *       Right now double precision may cause noticable error on huge
2295         *       texture sizes (8096*8096*8 = 500 000 000 added values)
2296         */
2297         average_dist /= (double)count;
2298
2299         /*      Limit minimum distance (used to define substeps)
2300         *       to 1/2 of the average
2301         */
2302         if (minimum_dist < (average_dist/2.0f)) minimum_dist=average_dist/2.0f;
2303
2304         /* Get fastest effect speed and scale other effects according to it     */
2305         fastest_effect = canvas->spread_speed;
2306         if (canvas->drip_speed > fastest_effect) fastest_effect = canvas->drip_speed;
2307         if (canvas->shrink_speed > fastest_effect) fastest_effect = canvas->shrink_speed;
2308
2309         /* Number of steps depends on surface res, effect speed and timescale   */
2310         speed_factor = (float)surface->w/256.0f * timescale;
2311         steps = (int)ceil(speed_factor*fastest_effect);
2312
2313         speed_factor /= (float)steps;
2314
2315         /*
2316         *       Now calculate final per pixel speed ratio to neighbour_dist[] array
2317         */
2318         #pragma omp parallel for schedule(static)
2319         for (yy = 0; yy < h; yy++)
2320         {
2321                 int xx;
2322                 float dd;
2323                 for (xx = 0; xx < w; xx++)
2324                 {
2325                         int i;
2326                         PaintSurfacePoint *cPoint = (&surface->point[xx+w*yy]);
2327
2328                         if (cPoint->index != -1)
2329                         for (i=0; i<8; i++) {
2330                                 if (cPoint->neighbours[i] != -1) {
2331                                         dd = (cPoint->neighbour_dist[i]<minimum_dist) ? minimum_dist : cPoint->neighbour_dist[i];
2332                                         cPoint->neighbour_dist[i] = minimum_dist / dd * speed_factor;
2333                                 }
2334                         }
2335                 }
2336         } // end pixel loop
2337
2338         //printf("Average distance is %f, minimum distance is %f\n", average_dist, minimum_dist);
2339
2340         return steps;
2341 }
2342
2343
2344 /*
2345 *       Clean effect data
2346 */
2347 static void DynamicPaint_Clean_EffectStep(DynamicPaintCanvasSettings *canvas, float timescale)
2348 {
2349         //PaintSurface *surface = canvas->surface;
2350 }
2351
2352
2353 /*
2354 *       Processes active effect step.
2355 */
2356 static void DynamicPaint_Do_EffectStep(DynamicPaintCanvasSettings *canvas, PaintSurfacePoint *prevPoint, float timescale)
2357 {
2358         PaintSurface *surface = canvas->surface;
2359         int yy, w=surface->w, h=surface->h;
2360
2361         /*
2362         *       Spread Effect
2363         */
2364         if (canvas->effect & MOD_DPAINT_EFFECT_DO_SPREAD)  {
2365
2366                 #pragma omp parallel for schedule(static)
2367                 for (yy = 0; yy < h; yy++)
2368                 {
2369                         int xx;
2370                         for (xx = 0; xx < w; xx++)
2371                         {
2372                                 int index = xx+w*yy;
2373                                 int i, validPoints = 0;
2374                                 float totalAlpha = 0.0f;
2375                                 PaintSurfacePoint *cPoint = (&surface->point[index]);   /* Current source point */
2376                                 PaintSurfacePoint *ePoint;                                                      /* Effect point to shift values into */
2377
2378                                 /*
2379                                 *       Only reads values from the surface copy (prevPoint[]),
2380                                 *       so this one is thread safe
2381                                 */
2382
2383                                 /*      Loop through neighbouring pixels        */
2384                                 for (i=0; i<8; i++) {
2385                                         int nIndex;
2386                                         float factor, alphaAdd = 0.0f;
2387
2388                                         nIndex = surface->point[index].neighbours[i];
2389                                         if (nIndex == -1) continue;
2390
2391                                         /*
2392                                         *       Find neighbour cells that have higher wetness
2393                                         *       and expand it to this cell as well.
2394                                         */
2395                                         ePoint = (&prevPoint[nIndex]);
2396                                         validPoints++;
2397                                         totalAlpha += ePoint->e_alpha;
2398
2399                                         if (ePoint->wetness <= cPoint->wetness) continue;
2400                                         factor = ePoint->wetness/8 * (ePoint->wetness - cPoint->wetness) * surface->point[index].neighbour_dist[i] * canvas->spread_speed;
2401
2402                                         if (ePoint->e_alpha > cPoint->e_alpha) {
2403                                                 alphaAdd = ePoint->e_alpha/8 * (ePoint->wetness*ePoint->e_alpha - cPoint->wetness*cPoint->e_alpha) * surface->point[index].neighbour_dist[i] * canvas->spread_speed;
2404                                         }
2405
2406
2407                                         /* If this pixel has existing paint, we have to blend it properly       */
2408                                         if (cPoint->e_alpha) {
2409                                                 float invFactor = 1.0f - factor;
2410                                                 cPoint->e_color[0] = cPoint->e_color[0]*invFactor + ePoint->e_color[0]*factor;
2411                                                 cPoint->e_color[1] = cPoint->e_color[1]*invFactor + ePoint->e_color[1]*factor;
2412                                                 cPoint->e_color[2] = cPoint->e_color[2]*invFactor + ePoint->e_color[2]*factor;
2413                                                         
2414                                                 cPoint->e_alpha += alphaAdd;
2415                                                 cPoint->wetness += factor;
2416                                         }
2417                                         else {
2418                                                 /* If there is no existing paint, just replace the color */
2419                                                 cPoint->e_color[0] = ePoint->e_color[0];
2420                                                 cPoint->e_color[1] = ePoint->e_color[1];
2421                                                 cPoint->e_color[2] = ePoint->e_color[2];
2422
2423                                                 cPoint->e_alpha += alphaAdd;
2424                                                 cPoint->wetness += factor;
2425                                         }
2426
2427                                         if (cPoint->e_alpha > 1.0f) cPoint->e_alpha = 1.0f;
2428                                 }
2429
2430                                 /* For antialiasing sake, don't let alpha go much higher than average alpha of neighbours       */
2431                                 if (validPoints && (cPoint->e_alpha > (totalAlpha/validPoints+0.25f))) {
2432                                         cPoint->e_alpha = (totalAlpha/validPoints+0.25f);
2433                                         if (cPoint->e_alpha>1.0f) cPoint->e_alpha = 1.0f;
2434                                 }
2435                         }
2436                 } // end pixel loop
2437         } // end spread effect
2438
2439
2440         /*
2441         *       Drip Effect
2442         */
2443         if (canvas->effect & MOD_DPAINT_EFFECT_DO_DRIP) 
2444         {
2445                 memcpy(prevPoint, surface->point, surface->w*surface->h*sizeof(struct PaintSurfacePoint));
2446
2447                 //#pragma omp parallel for schedule(static)
2448                 for (yy = 1; yy < h-1; yy++)
2449                 {
2450                         int xx;
2451                         for (xx = 1; xx < w-1; xx++)
2452                         {
2453                                 int index = xx+w*yy;
2454                                 float factor = 0.0f, drip_strength = 0.0f;
2455                                 PaintSurfacePoint *cPoint = (&prevPoint[index]);        /* Current source point to read */
2456                                 PaintSurfacePoint *dPoint = (&surface->point[index]);   /* Current source point to write */
2457                                 PaintSurfacePoint *ePoint;                                                      /* Effect point to shift values into */
2458                                 PaintSurfacePoint *ePoint2;                                                     /* Effect point to shift values into */
2459                                 int nIndex;
2460
2461                                 /*
2462                                 *       Because the neighbour pixels go in 45 degree (pi/4) slices
2463                                 *       get drip factor in that range
2464                                 */
2465                                 float dirMod = fmod(cPoint->gravity_dir,0.785398163);
2466                                 float stFac=dirMod/0.785398163;
2467                                 float facTotal;
2468                                 int neighPixel,neighPixel2;
2469
2470                                 /* Skip if wetness is too low   */
2471                                 drip_strength = cPoint->wetness - 0.1f;
2472                                 if (drip_strength < 0) continue;
2473
2474
2475                                 /* Get first neighpixel index for neighbours[] array */
2476                                 neighPixel = (int)floor(cPoint->gravity_dir/6.2831853f * 8.0f);
2477
2478                                 if (neighPixel > 7) neighPixel = 7;     /* Shouldn't happen but just in case */
2479                                 if (neighPixel < 0) neighPixel = 0;
2480
2481                                 /* Make sure the neighbour exists       */
2482                                 nIndex = surface->point[index].neighbours[neighPixel];
2483                                 if (nIndex == -1) continue;
2484                                 ePoint = (&surface->point[nIndex]);
2485
2486
2487                                 /*
2488                                 *       Second neighbouring point
2489                                 */
2490                                 neighPixel2 = neighPixel + 1;
2491                                 if (neighPixel2 > 7) neighPixel2 = 0;
2492
2493                                 /* Make sure the neighbour exists       */
2494                                 nIndex = surface->point[index].neighbours[neighPixel2];
2495                                 if (nIndex == -1) continue;
2496                                 ePoint2 = (&surface->point[nIndex]);
2497
2498
2499                                 /* Do some adjustments to dripping speed        */
2500                                 factor = 0.3 * canvas->drip_speed;
2501                                 if (drip_strength < 2.5f) factor *= drip_strength;
2502
2503                                 /* Add values to the pixel below -> drip        */
2504                                 ePoint->e_color[0] = cPoint->e_color[0];
2505                                 ePoint->e_color[1] = cPoint->e_color[1];
2506                                 ePoint->e_color[2] = cPoint->e_color[2];
2507
2508                                 ePoint->e_alpha += cPoint->e_alpha * factor * surface->point[index].neighbour_dist[neighPixel] * (1.0f - stFac);
2509                                 ePoint->wetness += cPoint->wetness * factor * surface->point[index].neighbour_dist[neighPixel] * (1.0f - stFac);
2510
2511                                 if (stFac > 0.0f) {
2512                                         ePoint2->e_color[0] = cPoint->e_color[0];
2513                                         ePoint2->e_color[1] = cPoint->e_color[1];
2514                                         ePoint2->e_color[2] = cPoint->e_color[2];
2515                                 }
2516
2517                                 ePoint2->e_alpha += cPoint->e_alpha * factor * surface->point[index].neighbour_dist[neighPixel2] * stFac;
2518                                 ePoint2->wetness += cPoint->wetness * factor * surface->point[index].neighbour_dist[neighPixel2] * stFac;
2519
2520                                 //dPoint->e_alpha -= cPoint->e_alpha * factor;
2521                                 facTotal = surface->point[index].neighbour_dist[neighPixel] * (1.0f - stFac) + surface->point[index].neighbour_dist[neighPixel2] * stFac;
2522                                 dPoint->wetness -= cPoint->wetness * factor * facTotal;
2523
2524                         }
2525                 } // end pixel loop
2526
2527                 /* Keep wetness values within acceptable range */
2528                 #pragma omp parallel for schedule(static)
2529                 for (yy = 0; yy < h; yy++)
2530                 {
2531                         int xx;
2532                         for (xx = 0; xx < w; xx++)
2533                         {
2534                                 int index = xx+w*yy;
2535
2536                                 PaintSurfacePoint *cPoint = (&surface->point[index]);
2537
2538                                 if (cPoint->e_alpha > 1.0f) cPoint->e_alpha=1.0f;
2539                                 if (cPoint->wetness > 3.5f) cPoint->wetness=3.5f;
2540
2541                                 if (cPoint->e_alpha < 0.0f) cPoint->e_alpha=0.0f;
2542                                 if (cPoint->wetness < 0.0f) cPoint->wetness=0.0f;
2543
2544                         }
2545                 } // end pixel loop
2546         } // end dripping effect
2547
2548
2549
2550         /*
2551         *       Shrink Effect
2552         */
2553         if (canvas->effect & MOD_DPAINT_EFFECT_DO_SHRINK)  {
2554
2555                 #pragma omp parallel for schedule(static)
2556                 for (yy = 0; yy < h; yy++)
2557                 {
2558                         int xx;
2559                         for (xx = 0; xx < w; xx++)
2560                         {
2561                                 int index = xx+w*yy;
2562                                 int i, validPoints = 0;
2563                                 float totalAlpha = 0.0f;
2564                                 PaintSurfacePoint *cPoint = (&surface->point[index]);   /* Current source point */
2565                                 PaintSurfacePoint *ePoint;                                                      /* Effect point to shift values into */
2566
2567                                 /*      Loop through neighbouring pixels        */
2568                                 for (i=0; i<8; i++) {
2569                                         int nIndex;
2570                                         float factor, e_factor, w_factor;
2571
2572                                         nIndex = surface->point[index].neighbours[i];
2573
2574                                         if (nIndex == -1) continue;
2575
2576                                         /*
2577                                         *       Find neighbouring cells that have lower alpha
2578                                         *       and decrease this point alpha towards that level.
2579                                         */
2580                                         ePoint = (&prevPoint[nIndex]);
2581                                         validPoints++;
2582                                         totalAlpha += ePoint->e_alpha;
2583
2584                                         if (cPoint->alpha <= 0.0f && cPoint->e_alpha <= 0.0f && cPoint->wetness <= 0.0f) continue;
2585                                         factor = (1.0f - ePoint->alpha)/8 * (cPoint->alpha - ePoint->alpha) * surface->point[index].neighbour_dist[i] * canvas->shrink_speed;
2586                                         if (factor < 0.0f) factor = 0.0f;
2587
2588                                         e_factor = (1.0f - ePoint->e_alpha)/8 * (cPoint->e_alpha - ePoint->e_alpha) * surface->point[index].neighbour_dist[i] * canvas->shrink_speed;
2589                                         if (e_factor < 0.0f) e_factor = 0.0f;
2590
2591                                         w_factor = (1.0f - ePoint->wetness)/8 * (cPoint->wetness - ePoint->wetness) * surface->point[index].neighbour_dist[i] * canvas->shrink_speed;
2592                                         if (w_factor < 0.0f) w_factor = 0.0f;
2593
2594
2595                                         if (factor) {
2596                                                 cPoint->alpha -=&nbs