6c5826c5babc77f45b2c556c77993e38b13cbce6
[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  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * Contributor(s): Miika Hämäläinen
19  *
20  * ***** END GPL LICENSE BLOCK *****
21  */
22
23
24 #include "MEM_guardedalloc.h"
25
26 #include <math.h>
27 #include <stdio.h>
28
29 #include "BLI_blenlib.h"
30 #include "BLI_math.h"
31 #include "BLI_kdtree.h"
32 #include "BLI_threads.h"
33 #include "BLI_utildefines.h"
34
35 #include "DNA_anim_types.h"
36 #include "DNA_constraint_types.h"
37 #include "DNA_dynamicpaint_types.h"
38 #include "DNA_group_types.h" /*GroupObject*/
39 #include "DNA_material_types.h"
40 #include "DNA_mesh_types.h"
41 #include "DNA_meshdata_types.h"
42 #include "DNA_modifier_types.h"
43 #include "DNA_object_types.h"
44 #include "DNA_scene_types.h"
45 #include "DNA_space_types.h"
46 #include "DNA_texture_types.h"
47
48 #include "BKE_animsys.h"
49 #include "BKE_bvhutils.h"       /* bvh tree     */
50 #include "BKE_blender.h"
51 #include "BKE_cdderivedmesh.h"
52 #include "BKE_constraint.h"
53 #include "BKE_context.h"
54 #include "BKE_customdata.h"
55 #include "BKE_colortools.h"
56 #include "BKE_deform.h"
57 #include "BKE_depsgraph.h"
58 #include "BKE_DerivedMesh.h"
59 #include "BKE_dynamicpaint.h"
60 #include "BKE_effect.h"
61 #include "BKE_global.h"
62 #include "BKE_image.h"
63 #include "BKE_main.h"
64 #include "BKE_material.h"
65 #include "BKE_modifier.h"
66 #include "BKE_object.h"
67 #include "BKE_particle.h"
68 #include "BKE_pointcache.h"
69 #include "BKE_scene.h"
70 #include "BKE_texture.h"
71
72 #include "RNA_access.h"
73 #include "RNA_define.h"
74 #include "RNA_enum_types.h"
75
76 /* for image output     */
77 #include "IMB_imbuf_types.h"
78 #include "IMB_imbuf.h"
79
80 /* to read material/texture color       */
81 #include "RE_render_ext.h"
82 #include "RE_shader_ext.h"
83
84 #ifdef _OPENMP
85 #include <omp.h>
86 #endif
87
88 /* precalculated gaussian factors for 5x super sampling */
89 static float gaussianFactors[5] = {     0.996849f,
90                                     0.596145f,
91                                     0.596145f,
92                                     0.596145f,
93                                     0.524141f};
94 static float gaussianTotal = 3.309425f;
95
96 /* UV Image neighboring pixel table x and y list */
97 static int neighX[8] = {1, 1, 0, -1, -1, -1, 0, 1};
98 static int neighY[8] = {0, 1, 1, 1, 0, -1, -1, -1};
99
100 /* subframe_updateObject() flags */
101 #define UPDATE_PARENTS (1<<0)
102 #define UPDATE_MESH (1<<1)
103 #define UPDATE_EVERYTHING (UPDATE_PARENTS|UPDATE_MESH)
104 /* surface_getBrushFlags() return vals */
105 #define BRUSH_USES_VELOCITY (1<<0)
106 /* brush mesh raycast status */
107 #define HIT_VOLUME 1
108 #define HIT_PROXIMITY 2
109 /* dynamicPaint_findNeighbourPixel() return codes */
110 #define NOT_FOUND -1
111 #define ON_MESH_EDGE -2
112 #define OUT_OF_TEXTURE -3
113 /* paint effect default movement per frame in global units */
114 #define EFF_MOVEMENT_PER_FRAME 0.05f
115 /* initial wave time factor */
116 #define WAVE_TIME_FAC (1.0f/24.f)
117 #define CANVAS_REL_SIZE 5.0f
118 /* drying limits */
119 #define MIN_WETNESS 0.001f
120 #define MAX_WETNESS 5.0f
121 /* dissolve macro */
122 #define VALUE_DISSOLVE(VALUE, TIME, SCALE, LOG) (VALUE) = (LOG) ? (VALUE) * (pow(MIN_WETNESS, 1.0f/(1.2f*((float)(TIME))/(SCALE)))) : (VALUE) - 1.0f/(TIME)*(SCALE)
123
124 /***************************** Internal Structs ***************************/
125
126 typedef struct Bounds2D {
127         float min[2], max[2];
128 } Bounds2D;
129
130 typedef struct Bounds3D {
131         int valid;
132         float min[3], max[3];
133 } Bounds3D;
134
135 typedef struct VolumeGrid {
136         int dim[3];
137         Bounds3D grid_bounds; /* whole grid bounds */
138
139         Bounds3D *bounds;       /* (x*y*z) precalculated grid cell bounds */
140         int *s_pos; /* (x*y*z) t_index begin id */
141         int *s_num; /* (x*y*z) number of t_index points */
142         int *t_index; /* actual surface point index,
143                                                    access: (s_pos+s_num) */
144 } VolumeGrid;
145
146 typedef struct Vec3f {
147         float v[3];
148 } Vec3f;
149
150 typedef struct BakeAdjPoint {
151         float dir[3];   /* vector pointing towards this neighbor */
152         float dist;             /* distance to */
153 } BakeAdjPoint;
154
155 /* Surface data used while processing a frame   */
156 typedef struct PaintBakeNormal {
157         float invNorm[3];  /* current pixel world-space inverted normal */
158         float normal_scale; /* normal directional scale for displace mapping */
159 } PaintBakeNormal;
160
161 /* Temp surface data used to process a frame */
162 typedef struct PaintBakeData {
163         /* point space data */
164         PaintBakeNormal *bNormal;
165         int *s_pos;     /* index to start reading point sample realCoord */
166         int *s_num;     /* num of realCoord samples */
167         Vec3f *realCoord;  /* current pixel center world-space coordinates for each sample
168                             *  ordered as (s_pos+s_num)*/
169         Bounds3D mesh_bounds;
170
171         /* adjacency info */
172         BakeAdjPoint *bNeighs; /* current global neighbor distances and directions, if required */
173         double average_dist;
174         /* space partitioning */
175         VolumeGrid *grid;               /* space partitioning grid to optimize brush checks */
176
177         /* velocity and movement */
178         Vec3f *velocity;                /* speed vector in global space movement per frame, if required */
179         Vec3f *prev_velocity;
180         float *brush_velocity;  /* special temp data for post-p velocity based brushes like smudge
181                                                         *  3 float dir vec + 1 float str */
182         MVert *prev_verts;              /* copy of previous frame vertices. used to observe surface movement */
183         float prev_obmat[4][4]; /* previous frame object matrix */
184         int clear;                              /* flag to check if surface was cleared/reset -> have to redo velocity etc. */
185
186 } PaintBakeData;
187
188 /* UV Image sequence format point       */
189 typedef struct PaintUVPoint {
190         /* Pixel / mesh data */
191         unsigned int face_index, pixel_index;   /* face index on domain derived mesh */
192         unsigned int v1, v2, v3;                                /* vertex indexes */
193
194         unsigned int neighbour_pixel;   /* If this pixel isn't uv mapped to any face,
195                                                                            but it's neighboring pixel is */
196         short quad;
197 } PaintUVPoint;
198
199 typedef struct ImgSeqFormatData {
200         PaintUVPoint *uv_p;
201         Vec3f *barycentricWeights;              /* b-weights for all pixel samples */
202 } ImgSeqFormatData;
203
204 /* adjacency data flags */
205 #define ADJ_ON_MESH_EDGE (1<<0)
206
207 typedef struct PaintAdjData {
208         int *n_target;          /* array of neighboring point indexes,
209                                                                for single sample use (n_index+neigh_num) */
210         int *n_index;           /* index to start reading n_target for each point */
211         int *n_num;             /* num of neighs for each point */
212         int *flags;             /* vertex adjacency flags */
213         int total_targets; /* size of n_target */
214 } PaintAdjData;
215
216 /***************************** General Utils ******************************/
217
218 /* Set canvas error string to display at the bake report */
219 static int setError(DynamicPaintCanvasSettings *canvas, const char *string)
220 {
221         /* Add error to canvas ui info label */
222         BLI_strncpy(canvas->error, string, sizeof(canvas->error));
223         return 0;
224 }
225
226 /* Get number of surface points for cached types */
227 static int dynamicPaint_surfaceNumOfPoints(DynamicPaintSurface *surface)
228 {
229         if (surface->format == MOD_DPAINT_SURFACE_F_PTEX) {
230                 return 0; /* not supported atm */
231         }
232         else if (surface->format == MOD_DPAINT_SURFACE_F_VERTEX) {
233                 if (!surface->canvas->dm) return 0; /* invalid derived mesh */
234                 return surface->canvas->dm->getNumVerts(surface->canvas->dm);
235         }
236         else
237                 return 0;
238 }
239
240 /* checks whether surface's format/type has realtime preview */
241 int dynamicPaint_surfaceHasColorPreview(DynamicPaintSurface *surface)
242 {
243         if (surface->format == MOD_DPAINT_SURFACE_F_IMAGESEQ) {
244                 return 0;
245         }
246         else if (surface->format == MOD_DPAINT_SURFACE_F_VERTEX) {
247                 if (surface->type == MOD_DPAINT_SURFACE_T_DISPLACE ||
248                     surface->type == MOD_DPAINT_SURFACE_T_WAVE)
249                 {
250                         return 0;
251                 }
252                 else {
253                         return 1;
254                 }
255         }
256         else {
257                 return 1;
258         }
259 }
260
261 /* get currently active surface (in user interface) */
262 struct DynamicPaintSurface *get_activeSurface(DynamicPaintCanvasSettings *canvas)
263 {
264         DynamicPaintSurface *surface = canvas->surfaces.first;
265         int i;
266
267         for (i=0; surface; surface=surface->next) {
268                 if (i == canvas->active_sur)
269                         return surface;
270                 i++;
271         }
272         return NULL;
273 }
274
275 /* set preview to first previewable surface */
276 void dynamicPaint_resetPreview(DynamicPaintCanvasSettings *canvas)
277 {
278         DynamicPaintSurface *surface = canvas->surfaces.first;
279         int done=0;
280
281         for (; surface; surface=surface->next) {
282                 if (!done && dynamicPaint_surfaceHasColorPreview(surface)) {
283                         surface->flags |= MOD_DPAINT_PREVIEW;
284                         done=1;
285                 }
286                 else
287                         surface->flags &= ~MOD_DPAINT_PREVIEW;
288         }
289 }
290
291 /* set preview to defined surface */
292 static void dynamicPaint_setPreview(DynamicPaintSurface *t_surface)
293 {
294         DynamicPaintSurface *surface = t_surface->canvas->surfaces.first;
295         for (; surface; surface=surface->next) {
296                 if (surface == t_surface)
297                         surface->flags |= MOD_DPAINT_PREVIEW;
298                 else
299                         surface->flags &= ~MOD_DPAINT_PREVIEW;
300         }
301 }
302
303 int dynamicPaint_outputLayerExists(struct DynamicPaintSurface *surface, Object *ob, int output)
304 {
305         char *name;
306
307         if (output == 0)
308                 name = surface->output_name;
309         else if (output == 1)
310                 name = surface->output_name2;
311         else
312                 return 0;
313
314         if (surface->format == MOD_DPAINT_SURFACE_F_VERTEX) {
315                 if (surface->type == MOD_DPAINT_SURFACE_T_PAINT) {
316                         Mesh *me = ob->data;
317                         return (CustomData_get_named_layer_index(&me->fdata, CD_MCOL, name) != -1);
318                 }
319                 else if (surface->type == MOD_DPAINT_SURFACE_T_WEIGHT)
320                         return (defgroup_name_index(ob, surface->output_name) != -1);
321         }
322
323         return 0;
324 }
325
326 static int surface_duplicateOutputExists(void *arg, const char *name)
327 {
328         DynamicPaintSurface *t_surface = (DynamicPaintSurface*)arg;
329         DynamicPaintSurface *surface = t_surface->canvas->surfaces.first;
330
331         for (; surface; surface=surface->next) {
332                 if (surface!=t_surface && surface->type==t_surface->type &&
333                         surface->format==t_surface->format) {
334                         if (surface->output_name[0]!='\0' && !BLI_path_cmp(name, surface->output_name)) return 1;
335                         if (surface->output_name2[0]!='\0' && !BLI_path_cmp(name, surface->output_name2)) return 1;
336                 }
337         }
338         return 0;
339 }
340
341 static void surface_setUniqueOutputName(DynamicPaintSurface *surface, char *basename, int output)
342 {
343         char name[64];
344         BLI_strncpy(name, basename, sizeof(name)); /* in case basename is surface->name use a copy */
345         if (!output)
346                 BLI_uniquename_cb(surface_duplicateOutputExists, surface, name, '.', surface->output_name, sizeof(surface->output_name));
347         if (output)
348                 BLI_uniquename_cb(surface_duplicateOutputExists, surface, name, '.', surface->output_name2, sizeof(surface->output_name2));
349 }
350
351
352 static int surface_duplicateNameExists(void *arg, const char *name)
353 {
354         DynamicPaintSurface *t_surface = (DynamicPaintSurface*)arg;
355         DynamicPaintSurface *surface = t_surface->canvas->surfaces.first;
356
357         for (; surface; surface=surface->next) {
358                 if (surface!=t_surface && !strcmp(name, surface->name)) return 1;
359         }
360         return 0;
361 }
362
363 void dynamicPaintSurface_setUniqueName(DynamicPaintSurface *surface, const char *basename)
364 {
365         char name[64];
366         BLI_strncpy(name, basename, sizeof(name)); /* in case basename is surface->name use a copy */
367         BLI_uniquename_cb(surface_duplicateNameExists, surface, name, '.', surface->name, sizeof(surface->name));
368 }
369
370
371 /* change surface data to defaults on new type */
372 void dynamicPaintSurface_updateType(struct DynamicPaintSurface *surface)
373 {
374         if (surface->format == MOD_DPAINT_SURFACE_F_IMAGESEQ) {
375                 surface->output_name[0]='\0';
376                 surface->output_name2[0]='\0';
377                 surface->flags |= MOD_DPAINT_ANTIALIAS;
378                 surface->depth_clamp = 1.0f;
379         }
380         else {
381                 strcpy(surface->output_name, "dp_");
382                 strcpy(surface->output_name2, surface->output_name);
383                 surface->flags &= ~MOD_DPAINT_ANTIALIAS;
384                 surface->depth_clamp = 0.0f;
385         }
386
387         if (surface->type == MOD_DPAINT_SURFACE_T_PAINT) {
388                 strcat(surface->output_name, "paintmap");
389                 strcat(surface->output_name2, "wetmap");
390                 surface_setUniqueOutputName(surface, surface->output_name2, 1);
391         }
392         else if (surface->type == MOD_DPAINT_SURFACE_T_DISPLACE) {
393                 strcat(surface->output_name, "displace");
394         }
395         else if (surface->type == MOD_DPAINT_SURFACE_T_WEIGHT) {
396                 strcat(surface->output_name, "weight");
397         }
398         else if (surface->type == MOD_DPAINT_SURFACE_T_WAVE) {
399                 strcat(surface->output_name, "wave");
400         }
401
402         surface_setUniqueOutputName(surface, surface->output_name, 0);
403
404         /* update preview */
405         if (dynamicPaint_surfaceHasColorPreview(surface))
406                 dynamicPaint_setPreview(surface);
407         else
408                 dynamicPaint_resetPreview(surface->canvas);
409 }
410
411 static int surface_totalSamples(DynamicPaintSurface *surface)
412 {
413         if (surface->format == MOD_DPAINT_SURFACE_F_IMAGESEQ &&
414             surface->flags & MOD_DPAINT_ANTIALIAS)
415         {
416                 return (surface->data->total_points * 5);
417         }
418         if (surface->format == MOD_DPAINT_SURFACE_F_VERTEX &&
419             surface->flags & MOD_DPAINT_ANTIALIAS && surface->data->adj_data)
420         {
421                 return (surface->data->total_points+surface->data->adj_data->total_targets);
422         }
423
424         return surface->data->total_points;
425 }
426
427 static void blendColors(float t_color[3], float t_alpha, float s_color[3], float s_alpha, float result[4])
428 {
429         int i;
430         float i_alpha = 1.0f - s_alpha;
431         float f_alpha = t_alpha*i_alpha + s_alpha;
432
433         /* blend colors */
434         if (f_alpha) {
435                 for (i=0; i<3; i++) {
436                         result[i] = (t_color[i]*t_alpha*i_alpha + s_color[i]*s_alpha)/f_alpha;
437                 }
438         }
439         else {
440                 copy_v3_v3(result, t_color);
441         }
442         /* return final alpha */
443         result[3] = f_alpha;
444 }
445
446 /* Mix two alpha weighed colors by a defined ratio. output is saved at a_color */
447 static float mixColors(float a_color[3], float a_weight, float b_color[3], float b_weight, float ratio)
448 {
449         float weight_ratio, factor;
450         if (b_weight) {
451                 /* if first value has no weight just use b_color */
452                 if (!a_weight) {
453                         copy_v3_v3(a_color, b_color);
454                         return b_weight*ratio;
455                 }
456                 weight_ratio = b_weight/(a_weight+b_weight);
457         }
458         else return a_weight*(1.0f-ratio);
459
460         /* calculate final interpolation factor */
461         if (ratio<=0.5f) {
462                 factor = weight_ratio*(ratio*2.0f);
463         }
464         else {
465                 ratio = (ratio*2.0f - 1.0f);
466                 factor = weight_ratio*(1.0f-ratio) + ratio;
467         }
468         /* mix final color */
469         interp_v3_v3v3(a_color, a_color, b_color, factor);
470         return (1.0f-factor)*a_weight + factor*b_weight;
471 }
472
473 /* set "ignore cache" flag for all caches on this object */
474 static void object_cacheIgnoreClear(Object *ob, int state)
475 {
476         ListBase pidlist;
477         PTCacheID *pid;
478         BKE_ptcache_ids_from_object(&pidlist, ob, NULL, 0);
479
480         for (pid=pidlist.first; pid; pid=pid->next) {
481                 if (pid->cache) {
482                         if (state)
483                                 pid->cache->flag |= PTCACHE_IGNORE_CLEAR;
484                         else
485                                 pid->cache->flag &= ~PTCACHE_IGNORE_CLEAR;
486                 }
487         }
488
489         BLI_freelistN(&pidlist);
490 }
491
492 static int subframe_updateObject(Scene *scene, Object *ob, int flags, float frame)
493 {
494         DynamicPaintModifierData *pmd = (DynamicPaintModifierData *)modifiers_findByType(ob, eModifierType_DynamicPaint);
495         bConstraint *con;
496
497         /* if other is dynamic paint canvas, don't update */
498         if (pmd && pmd->canvas)
499                 return 1;
500
501         /* if object has parents, update them too */
502         if (flags & UPDATE_PARENTS) {
503                 int is_canvas = 0;
504                 if (ob->parent) is_canvas += subframe_updateObject(scene, ob->parent, 0, frame);
505                 if (ob->track) is_canvas += subframe_updateObject(scene, ob->track, 0, frame);
506
507                 /* skip subframe if object is parented
508                 *  to vertex of a dynamic paint canvas */
509                 if (is_canvas && (ob->partype == PARVERT1 || ob->partype == PARVERT3))
510                         return 0;
511
512                 /* also update constraint targets */
513                 for (con = ob->constraints.first; con; con=con->next) {
514                         bConstraintTypeInfo *cti= constraint_get_typeinfo(con);
515                         ListBase targets = {NULL, NULL};
516
517                         if (cti && cti->get_constraint_targets) {
518                                 bConstraintTarget *ct;
519                                 cti->get_constraint_targets(con, &targets);
520                                 for (ct= targets.first; ct; ct= ct->next) {
521                                         if (ct->tar)
522                                                 subframe_updateObject(scene, ct->tar, 0, frame);
523                                 }
524                                 /* free temp targets */
525                                 if (cti->flush_constraint_targets)
526                                         cti->flush_constraint_targets(con, &targets, 0);
527                         }
528                 }
529         }
530         /* for curve following objects, parented curve has to be updated too */
531         if (ob->type==OB_CURVE) {
532                 Curve *cu= ob->data;
533                 BKE_animsys_evaluate_animdata(scene, &cu->id, cu->adt, frame, ADT_RECALC_ANIM);
534         }
535
536         /* was originally OB_RECALC_ALL - TODO - which flags are really needed??? */
537         ob->recalc |= OB_RECALC_OB | OB_RECALC_DATA | OB_RECALC_TIME;
538         BKE_animsys_evaluate_animdata(scene, &ob->id, ob->adt, frame, ADT_RECALC_ANIM);
539         if (flags & UPDATE_MESH) {
540                 /* ignore cache clear during subframe updates
541                 *  to not mess up cache validity */
542                 object_cacheIgnoreClear(ob, 1);
543                 object_handle_update(scene, ob);
544                 object_cacheIgnoreClear(ob, 0);
545         }
546         else
547                 where_is_object_time(scene, ob, frame);
548
549         return 0;
550 }
551
552 static void scene_setSubframe(Scene *scene, float subframe)
553 {
554         /* dynamic paint subframes must be done on previous frame */
555         scene->r.cfra -= 1;
556         scene->r.subframe = subframe;
557 }
558
559 static int surface_getBrushFlags(DynamicPaintSurface *surface, Scene *scene)
560 {
561         Base *base = NULL;
562         GroupObject *go = NULL; 
563         Object *brushObj = NULL;
564         ModifierData *md = NULL;
565
566         int flags = 0;
567
568         if (surface->brush_group)
569                 go = surface->brush_group->gobject.first;
570         else
571                 base = scene->base.first;
572
573         while (base || go) {
574                 brushObj = NULL;
575
576                 /* select object */
577                 if (surface->brush_group) {                                             
578                         if (go->ob)     brushObj = go->ob;                                      
579                 }                                       
580                 else                                            
581                         brushObj = base->object;
582
583                 if (!brushObj) {
584                         if (surface->brush_group) go = go->next;
585                         else base= base->next;                                  
586                         continue;                       
587                 }
588
589                 if (surface->brush_group)
590                         go = go->next;
591                 else
592                         base= base->next;
593
594                 md = modifiers_findByType(brushObj, eModifierType_DynamicPaint);
595                 if (md && md->mode & (eModifierMode_Realtime | eModifierMode_Render)) {
596                         DynamicPaintModifierData *pmd2 = (DynamicPaintModifierData *)md;
597
598                         if (pmd2->brush) {
599                                 DynamicPaintBrushSettings *brush = pmd2->brush;
600
601                                 if (brush->flags & MOD_DPAINT_USES_VELOCITY)
602                                         flags |= BRUSH_USES_VELOCITY;
603                         }
604                 }
605         }
606
607         return flags;
608 }
609
610 static int brush_usesMaterial(DynamicPaintBrushSettings *brush, Scene *scene)
611 {
612         return ((brush->flags & MOD_DPAINT_USE_MATERIAL) && (!strcmp(scene->r.engine, "BLENDER_RENDER")));
613 }
614
615 /* check whether two bounds intersect */
616 static int boundsIntersect(Bounds3D *b1, Bounds3D *b2)
617 {
618         int i=2;
619         if (!b1->valid || !b2->valid) return 0;
620         for (; i>=0; i-=1)
621                 if (!(b1->min[i] <= b2->max[i] && b1->max[i] >= b2->min[i])) return 0;
622         return 1;
623 }
624
625 /* check whether two bounds intersect inside defined proximity */
626 static int boundsIntersectDist(Bounds3D *b1, Bounds3D *b2, float dist)
627 {
628         int i=2;
629         if (!b1->valid || !b2->valid) return 0;
630         for (; i>=0; i-=1)
631                 if (!(b1->min[i] <= (b2->max[i]+dist) && b1->max[i] >= (b2->min[i]-dist))) return 0;
632         return 1;
633 }
634
635 /* check whether bounds intersects a point with given radius */
636 static int boundIntersectPoint(Bounds3D *b, float point[3], float radius)
637 {
638         int i=2;
639         if (!b->valid) return 0;
640         for (; i>=0; i-=1)
641                 if (!(b->min[i] <= (point[i]+radius) && b->max[i] >= (point[i]-radius))) return 0;
642         return 1;
643 }
644
645 /* expand bounds by a new point */
646 static void boundInsert(Bounds3D *b, float point[3])
647 {
648         int i=2;
649         if (!b->valid) {
650                 copy_v3_v3(b->min, point);
651                 copy_v3_v3(b->max, point);
652                 b->valid = 1;
653         }
654         else {
655                 for (; i>=0; i-=1) {
656                         if (point[i] < b->min[i]) b->min[i]=point[i];
657                         if (point[i] > b->max[i]) b->max[i]=point[i];
658                 }
659         }
660 }
661
662 float getSurfaceDimension(PaintSurfaceData *sData)
663 {
664         Bounds3D *mb = &sData->bData->mesh_bounds;
665         return MAX3((mb->max[0]-mb->min[0]), (mb->max[1]-mb->min[1]), (mb->max[2]-mb->min[2]));
666 }
667
668 static void freeGrid(PaintSurfaceData *data)
669 {
670         PaintBakeData *bData = data->bData;
671         VolumeGrid *grid = bData->grid;
672
673         if (grid->bounds) MEM_freeN(grid->bounds);
674         if (grid->s_pos) MEM_freeN(grid->s_pos);
675         if (grid->s_num) MEM_freeN(grid->s_num);
676         if (grid->t_index) MEM_freeN(grid->t_index);
677
678         MEM_freeN(bData->grid);
679         bData->grid = NULL;
680 }
681
682 static void surfaceGenerateGrid(struct DynamicPaintSurface *surface)
683 {
684         PaintSurfaceData *sData = surface->data;
685         PaintBakeData *bData = sData->bData;
686         Bounds3D *grid_bounds;
687         VolumeGrid *grid;
688         int grid_cells, axis = 3;
689         int *temp_t_index = NULL;
690         int *temp_s_num = NULL;
691
692 #ifdef _OPENMP
693         int num_of_threads = omp_get_max_threads();
694 #else
695         int num_of_threads = 1;
696 #endif
697
698         if (bData->grid)
699                 freeGrid(sData);
700
701         /* allocate separate bounds for each thread */
702         grid_bounds = MEM_callocN(sizeof(Bounds3D)*num_of_threads, "Grid Bounds");
703         bData->grid = MEM_callocN(sizeof(VolumeGrid), "Surface Grid");
704         grid = bData->grid;
705
706         if (grid && grid_bounds) {
707                 int i, error = 0;
708                 float dim_factor, volume, dim[3];
709                 float td[3];
710                 float min_dim;
711
712                 /* calculate canvas dimensions */
713                 #pragma omp parallel for schedule(static)
714                 for (i=0; i<sData->total_points; i++) {
715                         #ifdef _OPENMP
716                         int id = omp_get_thread_num();
717                         boundInsert(&grid_bounds[id], (bData->realCoord[bData->s_pos[i]].v));
718                         #else
719                         boundInsert(&grid_bounds[0], (bData->realCoord[bData->s_pos[i]].v));
720                         #endif
721                 }
722
723                 /* get final dimensions */
724                 for (i=0; i<num_of_threads; i++) {
725                         boundInsert(&grid->grid_bounds, grid_bounds[i].min);
726                         boundInsert(&grid->grid_bounds, grid_bounds[i].max);
727                 }
728
729                 /* get dimensions */
730                 sub_v3_v3v3(dim, grid->grid_bounds.max, grid->grid_bounds.min);
731                 copy_v3_v3(td, dim);
732                 min_dim = MAX3(td[0], td[1], td[2]) / 1000.f;
733
734                 /* deactivate zero axises */
735                 for (i=0; i<3; i++) {
736                         if (td[i]<min_dim) {td[i]=1.0f; axis-=1;}
737                 }
738
739                 if (axis == 0 || MAX3(td[0], td[1], td[2]) < 0.0001f) {
740                         MEM_freeN(grid_bounds);
741                         MEM_freeN(bData->grid);
742                         bData->grid = NULL;
743                         return;
744                 }
745
746                 /* now calculate grid volume/area/width depending on num of active axis */
747                 volume = td[0]*td[1]*td[2];
748
749                 /* determine final grid size by trying to fit average 10.000 points per grid cell */
750                 dim_factor = (float)pow(volume / ((double)sData->total_points / 10000.0), 1.0/(double)axis);
751
752                 /* define final grid size using dim_factor, use min 3 for active axises */
753                 for (i=0; i<3; i++) {
754                         grid->dim[i] = (int)floor(td[i] / dim_factor);
755                         CLAMP(grid->dim[i], (dim[i]>=min_dim) ? 3 : 1, 100);
756                 }
757                 grid_cells = grid->dim[0]*grid->dim[1]*grid->dim[2];
758
759                 /* allocate memory for grids */
760                 grid->bounds = MEM_callocN(sizeof(Bounds3D) * grid_cells, "Surface Grid Bounds");
761                 grid->s_pos = MEM_callocN(sizeof(int) * grid_cells, "Surface Grid Position");
762                 grid->s_num = MEM_callocN(sizeof(int) * grid_cells*num_of_threads, "Surface Grid Points");
763                 temp_s_num = MEM_callocN(sizeof(int) * grid_cells, "Temp Surface Grid Points");
764                 grid->t_index = MEM_callocN(sizeof(int) * sData->total_points, "Surface Grid Target Ids");
765                 temp_t_index = MEM_callocN(sizeof(int) * sData->total_points, "Temp Surface Grid Target Ids");
766
767                 /* in case of an allocation failure abort here */
768                 if (!grid->bounds || !grid->s_pos || !grid->s_num || !grid->t_index || !temp_s_num || !temp_t_index)
769                         error = 1;
770
771                 if (!error) {
772                         /* calculate number of points withing each cell */
773                         #pragma omp parallel for schedule(static)
774                         for (i=0; i<sData->total_points; i++) {
775                                 int co[3], j;
776                                 for (j=0; j<3; j++) {
777                                         co[j] = (int)floor((bData->realCoord[bData->s_pos[i]].v[j] - grid->grid_bounds.min[j])/dim[j]*grid->dim[j]);
778                                         CLAMP(co[j], 0, grid->dim[j]-1);
779                                 }
780
781                                 temp_t_index[i] = co[0] + co[1] * grid->dim[0] + co[2] * grid->dim[0]*grid->dim[1];
782                                 #ifdef _OPENMP
783                                 grid->s_num[temp_t_index[i]+omp_get_thread_num()*grid_cells]++;
784                                 #else
785                                 grid->s_num[temp_t_index[i]]++;
786                                 #endif
787                         }
788
789                         /* for first cell only calc s_num */
790                         for (i=1; i<num_of_threads; i++) {
791                                 grid->s_num[0] += grid->s_num[i*grid_cells];
792                         }
793
794                         /* calculate grid indexes */
795                         for (i=1; i<grid_cells; i++) {
796                                 int id;
797                                 for (id=1; id<num_of_threads; id++) {
798                                         grid->s_num[i] += grid->s_num[i+id*grid_cells];
799                                 }
800                                 grid->s_pos[i] = grid->s_pos[i-1] + grid->s_num[i-1];
801                         }
802
803                         /* save point indexes to final array */
804                         for (i=0; i<sData->total_points; i++) {
805                                 int pos = grid->s_pos[temp_t_index[i]] + temp_s_num[temp_t_index[i]];
806                                 grid->t_index[pos] = i;
807
808                                 temp_s_num[temp_t_index[i]]++;
809                         }
810
811                         /* calculate cell bounds */
812                         {
813                                 int x;
814                                 #pragma omp parallel for schedule(static)
815                                 for (x=0; x<grid->dim[0]; x++) {
816                                         int y;
817                                         for (y=0; y<grid->dim[1]; y++) {
818                                                 int z;
819                                                 for (z=0; z<grid->dim[2]; z++) {
820                                                         int j, b_index = x + y * grid->dim[0] + z * grid->dim[0]*grid->dim[1];
821                                                         /* set bounds */
822                                                         for (j=0; j<3; j++) {
823                                                                 int s = (j==0) ? x : ((j==1) ? y : z);
824                                                                 grid->bounds[b_index].min[j] = grid->grid_bounds.min[j] + dim[j]/grid->dim[j]*s;
825                                                                 grid->bounds[b_index].max[j] = grid->grid_bounds.min[j] + dim[j]/grid->dim[j]*(s+1);
826                                                         }
827                                                         grid->bounds[b_index].valid = 1;
828                                                 }
829                                         }
830                                 }
831                         }
832                 }
833
834                 if (temp_s_num) MEM_freeN(temp_s_num);
835                 if (temp_t_index) MEM_freeN(temp_t_index);
836
837                 /* free per thread s_num values */
838                 grid->s_num = MEM_reallocN(grid->s_num, sizeof(int) * grid_cells);
839
840                 if (error || !grid->s_num) {
841                         setError(surface->canvas, "Not enough free memory.");
842                         freeGrid(sData);
843                 }
844         }
845
846         if (grid_bounds) MEM_freeN(grid_bounds);
847 }
848
849 /***************************** Freeing data ******************************/
850
851 /* Free brush data */
852 void dynamicPaint_freeBrush(struct DynamicPaintModifierData *pmd)
853 {
854         if (pmd->brush) {
855                 if (pmd->brush->dm)
856                         pmd->brush->dm->release(pmd->brush->dm);
857                 pmd->brush->dm = NULL;
858
859                 if (pmd->brush->paint_ramp)
860                          MEM_freeN(pmd->brush->paint_ramp);
861                 pmd->brush->paint_ramp = NULL;
862                 if (pmd->brush->vel_ramp)
863                          MEM_freeN(pmd->brush->vel_ramp);
864                 pmd->brush->vel_ramp = NULL;
865
866                 MEM_freeN(pmd->brush);
867                 pmd->brush = NULL;
868         }
869 }
870
871 static void dynamicPaint_freeAdjData(PaintSurfaceData *data)
872 {
873         if (data->adj_data) {
874                 if (data->adj_data->n_index) MEM_freeN(data->adj_data->n_index);
875                 if (data->adj_data->n_num) MEM_freeN(data->adj_data->n_num);
876                 if (data->adj_data->n_target) MEM_freeN(data->adj_data->n_target);
877                 if (data->adj_data->flags) MEM_freeN(data->adj_data->flags);
878                 MEM_freeN(data->adj_data);
879                 data->adj_data = NULL;
880         }
881 }
882
883 static void free_bakeData(PaintSurfaceData *data)
884 {
885         PaintBakeData *bData = data->bData;
886         if (bData) {
887                 if (bData->bNormal) MEM_freeN(bData->bNormal);
888                 if (bData->s_pos) MEM_freeN(bData->s_pos);
889                 if (bData->s_num) MEM_freeN(bData->s_num);
890                 if (bData->realCoord) MEM_freeN(bData->realCoord);
891                 if (bData->bNeighs) MEM_freeN(bData->bNeighs);
892                 if (bData->grid) freeGrid(data);
893                 if (bData->prev_verts) MEM_freeN(bData->prev_verts);
894                 if (bData->velocity) MEM_freeN(bData->velocity);
895                 if (bData->prev_velocity) MEM_freeN(bData->prev_velocity);
896
897                 MEM_freeN(data->bData);
898                 data->bData = NULL;
899         }
900 }
901
902 /* free surface data if it's not used anymore */
903 void surface_freeUnusedData(DynamicPaintSurface *surface)
904 {
905         if (!surface->data) return;
906
907         /* free bakedata if not active or surface is baked */
908         if (!(surface->flags & MOD_DPAINT_ACTIVE) ||
909             (surface->pointcache && surface->pointcache->flag & PTCACHE_BAKED))
910         {
911                 free_bakeData(surface->data);
912         }
913 }
914
915 void dynamicPaint_freeSurfaceData(DynamicPaintSurface *surface)
916 {
917         PaintSurfaceData *data = surface->data;
918         if (!data) return;
919         if (data->format_data) {
920                 /* format specific free */
921                 if (surface->format == MOD_DPAINT_SURFACE_F_IMAGESEQ) {
922                         ImgSeqFormatData *format_data = (ImgSeqFormatData*)data->format_data;
923                         if (format_data->uv_p)
924                                 MEM_freeN(format_data->uv_p);
925                         if (format_data->barycentricWeights)
926                                 MEM_freeN(format_data->barycentricWeights);
927                 }
928                 MEM_freeN(data->format_data);
929         }
930         /* type data */
931         if (data->type_data) MEM_freeN(data->type_data);
932         dynamicPaint_freeAdjData(data);
933         /* bake data */
934         free_bakeData(data);
935
936         MEM_freeN(surface->data);
937         surface->data = NULL;
938 }
939
940 void dynamicPaint_freeSurface(DynamicPaintSurface *surface)
941 {
942         /* point cache */
943         BKE_ptcache_free_list(&(surface->ptcaches));
944         surface->pointcache = NULL;
945
946         if (surface->effector_weights)
947                 MEM_freeN(surface->effector_weights);
948         surface->effector_weights = NULL;
949
950         BLI_remlink(&(surface->canvas->surfaces), surface);
951         dynamicPaint_freeSurfaceData(surface);
952         MEM_freeN(surface);
953 }
954
955 /* Free canvas data */
956 void dynamicPaint_freeCanvas(DynamicPaintModifierData *pmd)
957 {
958         if (pmd->canvas) {
959                 /* Free surface data */
960                 DynamicPaintSurface *surface = pmd->canvas->surfaces.first;
961                 DynamicPaintSurface *next_surface = NULL;
962
963                 while (surface) {
964                         next_surface = surface->next;
965                         dynamicPaint_freeSurface(surface);
966                         surface = next_surface;
967                 }
968
969                 /* free dm copy */
970                 if (pmd->canvas->dm)
971                         pmd->canvas->dm->release(pmd->canvas->dm);
972                 pmd->canvas->dm = NULL;
973
974                 MEM_freeN(pmd->canvas);
975                 pmd->canvas = NULL;
976         }
977 }
978
979 /* Free whole dp modifier */
980 void dynamicPaint_Modifier_free(struct DynamicPaintModifierData *pmd)
981 {
982         if (pmd) {
983                 dynamicPaint_freeCanvas(pmd);
984                 dynamicPaint_freeBrush(pmd);
985         }
986 }
987
988
989 /***************************** Initialize and reset ******************************/
990
991 /*
992 *       Creates a new surface and adds it to the list
993 *       If scene is null, frame range of 1-250 is used
994 *       A pointer to this surface is returned
995 */
996 struct DynamicPaintSurface *dynamicPaint_createNewSurface(DynamicPaintCanvasSettings *canvas, Scene *scene)
997 {
998         DynamicPaintSurface *surface= MEM_callocN(sizeof(DynamicPaintSurface), "DynamicPaintSurface");
999         if (!surface) return NULL;
1000
1001         surface->canvas = canvas;
1002         surface->format = MOD_DPAINT_SURFACE_F_VERTEX;
1003         surface->type = MOD_DPAINT_SURFACE_T_PAINT;
1004
1005         /* cache */
1006         surface->pointcache = BKE_ptcache_add(&(surface->ptcaches));
1007         surface->pointcache->flag |= PTCACHE_DISK_CACHE;
1008         surface->pointcache->step = 1;
1009
1010         /* Set initial values */
1011         surface->flags = MOD_DPAINT_ANTIALIAS | MOD_DPAINT_MULALPHA | MOD_DPAINT_DRY_LOG | MOD_DPAINT_DISSOLVE_LOG |
1012                                          MOD_DPAINT_ACTIVE | MOD_DPAINT_PREVIEW | MOD_DPAINT_OUT1 | MOD_DPAINT_USE_DRYING;
1013         surface->effect = 0;
1014         surface->effect_ui = 1;
1015
1016         surface->diss_speed = 250;
1017         surface->dry_speed = 500;
1018         surface->color_dry_threshold = 1.0f;
1019         surface->depth_clamp = 0.0f;
1020         surface->disp_factor = 1.0f;
1021         surface->disp_type = MOD_DPAINT_DISP_DISPLACE;
1022         surface->image_fileformat = MOD_DPAINT_IMGFORMAT_PNG;
1023
1024         surface->influence_scale = 1.0f;
1025         surface->radius_scale = 1.0f;
1026
1027         surface->init_color[0] = 1.0f;
1028         surface->init_color[1] = 1.0f;
1029         surface->init_color[2] = 1.0f;
1030         surface->init_color[3] = 1.0f;
1031
1032         surface->image_resolution = 256;
1033         surface->substeps = 0;
1034
1035         if (scene) {
1036                 surface->start_frame = scene->r.sfra;
1037                 surface->end_frame = scene->r.efra;
1038         }
1039         else {
1040                 surface->start_frame = 1;
1041                 surface->end_frame = 250;
1042         }
1043
1044         surface->spread_speed = 1.0f;
1045         surface->color_spread_speed = 1.0f;
1046         surface->shrink_speed = 1.0f;
1047
1048         surface->wave_damping = 0.04f;
1049         surface->wave_speed = 1.0f;
1050         surface->wave_timescale = 1.0f;
1051         surface->wave_spring = 0.20f;
1052
1053         modifier_path_init(surface->image_output_path, sizeof(surface->image_output_path), "cache_dynamicpaint");
1054
1055         dynamicPaintSurface_setUniqueName(surface, "Surface");
1056
1057         surface->effector_weights = BKE_add_effector_weights(NULL);
1058
1059         dynamicPaintSurface_updateType(surface);
1060
1061         BLI_addtail(&canvas->surfaces, surface);
1062
1063         return surface;
1064 }
1065
1066 /*
1067 *       Initialize modifier data
1068 */
1069 int dynamicPaint_createType(struct DynamicPaintModifierData *pmd, int type, struct Scene *scene)
1070 {
1071         if (pmd) {
1072                 if (type == MOD_DYNAMICPAINT_TYPE_CANVAS) {
1073                         DynamicPaintCanvasSettings *canvas;
1074                         if (pmd->canvas)
1075                                 dynamicPaint_freeCanvas(pmd);
1076
1077                         canvas = pmd->canvas = MEM_callocN(sizeof(DynamicPaintCanvasSettings), "DynamicPaint Canvas");
1078                         if (!canvas)
1079                                 return 0;
1080                         canvas->pmd = pmd;
1081                         canvas->dm = NULL;
1082
1083                         /* Create one surface */
1084                         if (!dynamicPaint_createNewSurface(canvas, scene))
1085                                 return 0;
1086
1087                 }
1088                 else if (type == MOD_DYNAMICPAINT_TYPE_BRUSH) {
1089                         DynamicPaintBrushSettings *brush;
1090                         if (pmd->brush)
1091                                 dynamicPaint_freeBrush(pmd);
1092
1093                         brush = pmd->brush = MEM_callocN(sizeof(DynamicPaintBrushSettings), "DynamicPaint Paint");
1094                         if (!brush)
1095                                 return 0;
1096                         brush->pmd = pmd;
1097
1098                         brush->psys = NULL;
1099
1100                         brush->flags = MOD_DPAINT_ABS_ALPHA | MOD_DPAINT_RAMP_ALPHA;
1101                         brush->collision = MOD_DPAINT_COL_VOLUME;
1102                         
1103                         brush->mat = NULL;
1104                         brush->r = 0.15f;
1105                         brush->g = 0.4f;
1106                         brush->b = 0.8f;
1107                         brush->alpha = 1.0f;
1108                         brush->wetness = 1.0f;
1109
1110                         brush->paint_distance = 1.0f;
1111                         brush->proximity_falloff = MOD_DPAINT_PRFALL_SMOOTH;
1112
1113                         brush->particle_radius = 0.2f;
1114                         brush->particle_smooth = 0.05f;
1115
1116                         brush->wave_type = MOD_DPAINT_WAVEB_CHANGE;
1117                         brush->wave_factor = 1.0f;
1118                         brush->wave_clamp = 0.0f;
1119                         brush->smudge_strength = 0.3f;
1120                         brush->max_velocity = 1.0f;
1121
1122                         brush->dm = NULL;
1123
1124                         /* Paint proximity falloff colorramp. */
1125                         {
1126                                 CBData *ramp;
1127
1128                                 brush->paint_ramp = add_colorband(0);
1129                                 if (!brush->paint_ramp)
1130                                         return 0;
1131                                 ramp = brush->paint_ramp->data;
1132                                 /* Add default smooth-falloff ramp.     */
1133                                 ramp[0].r = ramp[0].g = ramp[0].b = ramp[0].a = 1.0f;
1134                                 ramp[0].pos = 0.0f;
1135                                 ramp[1].r = ramp[1].g = ramp[1].b = ramp[1].pos = 1.0f;
1136                                 ramp[1].a = 0.0f;
1137                                 pmd->brush->paint_ramp->tot = 2;
1138                         }
1139
1140                         /* Brush velocity ramp. */
1141                         {
1142                                 CBData *ramp;
1143
1144                                 brush->vel_ramp = add_colorband(0);
1145                                 if (!brush->vel_ramp)
1146                                         return 0;
1147                                 ramp = brush->vel_ramp->data;
1148                                 ramp[0].r = ramp[0].g = ramp[0].b = ramp[0].a = ramp[0].pos = 0.0f;
1149                                 ramp[1].r = ramp[1].g = ramp[1].b = ramp[1].a = ramp[1].pos = 1.0f;
1150                                 brush->paint_ramp->tot = 2;
1151                         }
1152                 }
1153         }
1154         else
1155                 return 0;
1156
1157         return 1;
1158 }
1159
1160 void dynamicPaint_Modifier_copy(struct DynamicPaintModifierData *pmd, struct DynamicPaintModifierData *tpmd)
1161 {
1162         /* Init modifier        */
1163         tpmd->type = pmd->type;
1164         if (pmd->canvas)
1165                 dynamicPaint_createType(tpmd, MOD_DYNAMICPAINT_TYPE_CANVAS, NULL);
1166         if (pmd->brush)
1167                 dynamicPaint_createType(tpmd, MOD_DYNAMICPAINT_TYPE_BRUSH, NULL);
1168
1169         /* Copy data    */
1170         if (tpmd->canvas) {
1171                 tpmd->canvas->pmd = tpmd;
1172         }
1173         else if (tpmd->brush) {
1174                 DynamicPaintBrushSettings *brush = pmd->brush, *t_brush = tpmd->brush;
1175                 t_brush->pmd = tpmd;
1176
1177                 t_brush->flags = brush->flags;
1178                 t_brush->collision = brush->collision;
1179
1180                 t_brush->mat = brush->mat;
1181                 t_brush->r = brush->r;
1182                 t_brush->g = brush->g;
1183                 t_brush->b = brush->b;
1184                 t_brush->alpha = brush->alpha;
1185                 t_brush->wetness = brush->wetness;
1186
1187                 t_brush->particle_radius = brush->particle_radius;
1188                 t_brush->particle_smooth = brush->particle_smooth;
1189                 t_brush->paint_distance = brush->paint_distance;
1190                 t_brush->psys = brush->psys;
1191
1192                 if (brush->paint_ramp)
1193                         memcpy(t_brush->paint_ramp, brush->paint_ramp, sizeof(ColorBand));
1194                 if (brush->vel_ramp)
1195                         memcpy(t_brush->vel_ramp, brush->vel_ramp, sizeof(ColorBand));
1196
1197                 t_brush->proximity_falloff = brush->proximity_falloff;
1198                 t_brush->wave_type = brush->wave_type;
1199                 t_brush->ray_dir = brush->ray_dir;
1200
1201                 t_brush->wave_factor = brush->wave_factor;
1202                 t_brush->wave_clamp = brush->wave_clamp;
1203                 t_brush->max_velocity = brush->max_velocity;
1204                 t_brush->smudge_strength = brush->smudge_strength;
1205         }
1206 }
1207
1208 /* allocates surface data depending on surface type */
1209 static void dynamicPaint_allocateSurfaceType(DynamicPaintSurface *surface)
1210 {
1211         PaintSurfaceData *sData = surface->data;
1212
1213         switch (surface->type) {
1214                 case MOD_DPAINT_SURFACE_T_PAINT:
1215                         sData->type_data = MEM_callocN(sizeof(PaintPoint)*sData->total_points, "DynamicPaintSurface Data");
1216                         break;
1217                 case MOD_DPAINT_SURFACE_T_DISPLACE:
1218                         sData->type_data = MEM_callocN(sizeof(float)*sData->total_points, "DynamicPaintSurface DepthData");
1219                         break;
1220                 case MOD_DPAINT_SURFACE_T_WEIGHT:
1221                         sData->type_data = MEM_callocN(sizeof(float)*sData->total_points, "DynamicPaintSurface WeightData");
1222                         break;
1223                 case MOD_DPAINT_SURFACE_T_WAVE:
1224                         sData->type_data = MEM_callocN(sizeof(PaintWavePoint)*sData->total_points, "DynamicPaintSurface WaveData");
1225                         break;
1226         }
1227
1228         if (sData->type_data == NULL) setError(surface->canvas, "Not enough free memory!");
1229 }
1230
1231 static int surface_usesAdjDistance(DynamicPaintSurface *surface)
1232 {
1233         if (surface->type == MOD_DPAINT_SURFACE_T_PAINT && surface->effect) return 1;
1234         if (surface->type == MOD_DPAINT_SURFACE_T_WAVE) return 1;
1235         return 0;
1236 }
1237
1238 static int surface_usesAdjData(DynamicPaintSurface *surface)
1239 {
1240         if (surface_usesAdjDistance(surface)) return 1;
1241         if (surface->format == MOD_DPAINT_SURFACE_F_VERTEX &&
1242             surface->flags & MOD_DPAINT_ANTIALIAS)
1243         {
1244                 return 1;
1245         }
1246         else {
1247                 return 0;
1248         }
1249 }
1250
1251 /* initialize surface adjacency data */
1252 static void dynamicPaint_initAdjacencyData(DynamicPaintSurface *surface, int force_init)
1253 {
1254         PaintSurfaceData *sData = surface->data;
1255         DerivedMesh *dm = surface->canvas->dm;
1256         PaintAdjData *ad;
1257         int *temp_data;
1258         int neigh_points = 0;
1259
1260         if (!surface_usesAdjData(surface) && !force_init) return;
1261
1262         if (surface->format == MOD_DPAINT_SURFACE_F_VERTEX) {
1263                 /* For vertex format, neighbors are connected by edges */
1264                 neigh_points = 2*dm->getNumEdges(dm);
1265         }
1266         else if (surface->format == MOD_DPAINT_SURFACE_F_IMAGESEQ)
1267                 neigh_points = sData->total_points*8;
1268
1269         if (!neigh_points) return;
1270
1271         /* allocate memory */
1272         ad = sData->adj_data = MEM_callocN(sizeof(PaintAdjData), "Surface Adj Data");
1273         if (!ad) return;
1274         ad->n_index = MEM_callocN(sizeof(int)*sData->total_points, "Surface Adj Index");
1275         ad->n_num = MEM_callocN(sizeof(int)*sData->total_points, "Surface Adj Counts");
1276         temp_data = MEM_callocN(sizeof(int)*sData->total_points, "Temp Adj Data");
1277         ad->n_target = MEM_callocN(sizeof(int)*neigh_points, "Surface Adj Targets");
1278         ad->flags = MEM_callocN(sizeof(int)*sData->total_points, "Surface Adj Flags");
1279         ad->total_targets = neigh_points;
1280
1281         /* in case of allocation error, free memory */
1282         if (!ad->n_index || !ad->n_num || !ad->n_target || !temp_data) {
1283                 dynamicPaint_freeAdjData(sData);
1284                 if (temp_data) MEM_freeN(temp_data);
1285                 setError(surface->canvas, "Not enough free memory.");
1286                 return;
1287         }
1288
1289         if (surface->format == MOD_DPAINT_SURFACE_F_VERTEX) {
1290                 int i;
1291                 int n_pos;
1292
1293                 /* For vertex format, count every vertex that is connected by an edge */
1294                 int numOfEdges = dm->getNumEdges(dm);
1295                 int numOfPolys = dm->getNumPolys(dm);
1296                 struct MEdge *edge =  dm->getEdgeArray(dm);
1297                 struct MPoly *mpoly = dm->getPolyArray(dm);
1298                 struct MLoop *mloop = dm->getLoopArray(dm);
1299
1300                 /* count number of edges per vertex */
1301                 for (i=0; i<numOfEdges; i++) {
1302                         ad->n_num[edge[i].v1]++;
1303                         ad->n_num[edge[i].v2]++;
1304
1305                         temp_data[edge[i].v1]++;
1306                         temp_data[edge[i].v2]++;
1307                 }
1308
1309                 /* also add number of vertices to temp_data
1310                 *  to locate points on "mesh edge" */
1311                 for (i=0; i<numOfPolys; i++) {
1312                         int j=0;
1313                         for (; j<mpoly[i].totloop; j++) {
1314                                 temp_data[mloop[mpoly[i].loopstart + j].v]++;
1315                         }
1316                 }
1317
1318                 /* now check if total number of edges+faces for
1319                 *  each vertex is even, if not -> vertex is on mesh edge */
1320                 for (i=0; i<sData->total_points; i++) {
1321                         if ((temp_data[i] % 2) ||
1322                             (temp_data[i] < 4))
1323                         {
1324                                 ad->flags[i] |= ADJ_ON_MESH_EDGE;
1325                         }
1326
1327                         /* reset temp data */ 
1328                         temp_data[i] = 0;
1329                 }
1330
1331                 /* order n_index array */
1332                 n_pos = 0;
1333                 for (i=0; i<sData->total_points; i++) {
1334                         ad->n_index[i] = n_pos;
1335                         n_pos += ad->n_num[i];
1336                 }
1337
1338                 /* and now add neighbor data using that info */
1339                 for (i=0; i<numOfEdges; i++) {
1340                         /* first vertex */
1341                         int index = edge[i].v1;
1342                         n_pos = ad->n_index[index]+temp_data[index];
1343                         ad->n_target[n_pos] = edge[i].v2;
1344                         temp_data[index]++;
1345
1346                         /* second vertex */
1347                         index = edge[i].v2;
1348                         n_pos = ad->n_index[index]+temp_data[index];
1349                         ad->n_target[n_pos] = edge[i].v1;
1350                         temp_data[index]++;
1351                 }
1352         }
1353         else if (surface->format == MOD_DPAINT_SURFACE_F_IMAGESEQ) {
1354                 /* for image sequences, only allocate memory.
1355                 *  bake initialization takes care of rest */
1356         }
1357
1358         MEM_freeN(temp_data);
1359 }
1360
1361 void dynamicPaint_setInitialColor(DynamicPaintSurface *surface)
1362 {
1363         PaintSurfaceData *sData = surface->data;
1364         PaintPoint* pPoint = (PaintPoint*)sData->type_data;
1365         DerivedMesh *dm = surface->canvas->dm;
1366         int i;
1367
1368         if (surface->type != MOD_DPAINT_SURFACE_T_PAINT)
1369                 return;
1370
1371         if (surface->init_color_type == MOD_DPAINT_INITIAL_NONE)
1372                 return;
1373         /* Single color */
1374         else if (surface->init_color_type == MOD_DPAINT_INITIAL_COLOR) {
1375                 /* apply color to every surface point */
1376                 #pragma omp parallel for schedule(static)
1377                 for (i=0; i<sData->total_points; i++) {
1378                         copy_v3_v3(pPoint[i].color, surface->init_color);
1379                         pPoint[i].alpha = surface->init_color[3];
1380                 }
1381         }
1382         /* UV mapped texture */
1383         else if (surface->init_color_type == MOD_DPAINT_INITIAL_TEXTURE) {
1384                 Tex *tex = surface->init_texture;
1385                 MTFace *tface;
1386                 MFace *mface = dm->getTessFaceArray(dm);
1387                 int numOfFaces = dm->getNumTessFaces(dm);
1388                 char uvname[MAX_CUSTOMDATA_LAYER_NAME];
1389
1390                 if (!tex) return;
1391
1392                 /* get uv map */
1393                 CustomData_validate_layer_name(&dm->faceData, CD_MTFACE, surface->init_layername, uvname);
1394                 tface = CustomData_get_layer_named(&dm->faceData, CD_MTFACE, uvname);
1395                 if (!tface) return;
1396
1397                 /* for vertex surface loop through tfaces and find uv color
1398                 *  that provides highest alpha */
1399                 if (surface->format == MOD_DPAINT_SURFACE_F_VERTEX) {
1400                         #pragma omp parallel for schedule(static)
1401                         for (i=0; i<numOfFaces; i++) {
1402                                 int numOfVert = (mface[i].v4) ? 4 : 3;
1403                                 float uv[3] = {0.0f};
1404                                 int j;
1405                                 for (j=0; j<numOfVert; j++) {
1406                                         TexResult texres = {0};
1407                                         unsigned int *vert = (&mface[i].v1)+j;
1408
1409                                         /* remap to -1.0 to 1.0 */
1410                                         uv[0] = tface[i].uv[j][0]*2.0f - 1.0f;
1411                                         uv[1] = tface[i].uv[j][1]*2.0f - 1.0f;
1412
1413                                         multitex_ext_safe(tex, uv, &texres);
1414
1415                                         if (texres.tin > pPoint[*vert].alpha) {
1416                                                 copy_v3_v3(pPoint[*vert].color, &texres.tr);
1417                                                 pPoint[*vert].alpha = texres.tin;
1418                                         }
1419                                 }
1420                         }
1421                 }
1422                 else if (surface->format == MOD_DPAINT_SURFACE_F_IMAGESEQ) {
1423                         ImgSeqFormatData *f_data = (ImgSeqFormatData*)sData->format_data;
1424                         int samples = (surface->flags & MOD_DPAINT_ANTIALIAS) ? 5 : 1;
1425
1426                         #pragma omp parallel for schedule(static)
1427                         for (i=0; i<sData->total_points; i++) {
1428                                 float uv[9] = {0.0f};
1429                                 float uv_final[3] = {0.0f};
1430                                 int j;
1431                                 TexResult texres = {0};
1432
1433                                 /* collect all uvs */
1434                                 for (j=0; j<3; j++) {
1435                                         int v=(f_data->uv_p[i].quad && j>0) ? j+1 : j;
1436                                         copy_v2_v2(&uv[j*3], tface[f_data->uv_p[i].face_index].uv[v]);
1437                                 }
1438
1439                                 /* interpolate final uv pos */
1440                                 interp_v3_v3v3v3(uv_final, &uv[0], &uv[3], &uv[6],
1441                                                  f_data->barycentricWeights[i*samples].v);
1442                                 /* remap to -1.0 to 1.0 */
1443                                 uv_final[0] = uv_final[0]*2.0f - 1.0f;
1444                                 uv_final[1] = uv_final[1]*2.0f - 1.0f;
1445                                         
1446                                 multitex_ext_safe(tex, uv_final, &texres);
1447
1448                                 /* apply color */
1449                                 copy_v3_v3(pPoint[i].color, &texres.tr);
1450                                 pPoint[i].alpha = texres.tin;
1451                         }
1452                 }
1453         }
1454         /* vertex color layer */
1455         else if (surface->init_color_type == MOD_DPAINT_INITIAL_VERTEXCOLOR) {
1456
1457                 /* for vertex surface, just copy colors from mcol */
1458                 if (surface->format == MOD_DPAINT_SURFACE_F_VERTEX) {
1459                         MLoop *mloop = dm->getLoopArray(dm);
1460                         int numOfLoops = dm->getNumLoops(dm);
1461                         MCol *col = CustomData_get_layer_named(&dm->loopData, CD_MLOOPCOL, surface->init_layername);
1462                         if (!col) return;
1463
1464                         #pragma omp parallel for schedule(static)
1465                         for (i=0; i<numOfLoops; i++) {
1466                                 pPoint[mloop[i].v].color[0] = 1.0f/255.f*(float)col[i].b;
1467                                 pPoint[mloop[i].v].color[1] = 1.0f/255.f*(float)col[i].g;
1468                                 pPoint[mloop[i].v].color[2] = 1.0f/255.f*(float)col[i].r;
1469                                 pPoint[mloop[i].v].alpha = 1.0f/255.f*(float)col[i].a;
1470                         }
1471                 }
1472                 else if (surface->format == MOD_DPAINT_SURFACE_F_IMAGESEQ) {
1473                         ImgSeqFormatData *f_data = (ImgSeqFormatData*)sData->format_data;
1474                         int samples = (surface->flags & MOD_DPAINT_ANTIALIAS) ? 5 : 1;
1475                         MCol *col = CustomData_get_layer_named(&dm->faceData, CD_MCOL, surface->init_layername);
1476                         if (!col) return;
1477
1478                         #pragma omp parallel for schedule(static)
1479                         for (i=0; i<sData->total_points; i++) {
1480                                 int face_ind = f_data->uv_p[i].face_index;
1481                                 float colors[3][4] = {{0.0f, 0.0f, 0.0f, 0.0f}};
1482                                 float final_color[4];
1483                                 int j;
1484                                 /* collect color values */
1485                                 for (j=0; j<3; j++) {
1486                                         int v=(f_data->uv_p[i].quad && j>0) ? j+1 : j;
1487                                         colors[j][0] = 1.0f/255.f*(float)col[face_ind*4+v].b;
1488                                         colors[j][1] = 1.0f/255.f*(float)col[face_ind*4+v].g;
1489                                         colors[j][2] = 1.0f/255.f*(float)col[face_ind*4+v].r;
1490                                         colors[j][3] = 1.0f/255.f*(float)col[face_ind*4+v].a;
1491                                 }
1492                                 
1493                                 /* interpolate final color */
1494                                 interp_v4_v4v4v4(final_color, colors[0], colors[1], colors[2],
1495                                                  f_data->barycentricWeights[i*samples].v);
1496
1497                                 copy_v3_v3(pPoint[i].color, final_color);
1498                                 pPoint[i].alpha = final_color[3];
1499                         }
1500                 }
1501         }
1502 }
1503
1504 /* clears surface data back to zero */
1505 void dynamicPaint_clearSurface(DynamicPaintSurface *surface)
1506 {
1507         PaintSurfaceData *sData = surface->data;
1508         if (sData && sData->type_data) {
1509                 unsigned int data_size;
1510
1511                 if (surface->type == MOD_DPAINT_SURFACE_T_PAINT)
1512                         data_size = sizeof(PaintPoint);
1513                 else if (surface->type == MOD_DPAINT_SURFACE_T_WAVE)
1514                         data_size = sizeof(PaintWavePoint);
1515                 else
1516                         data_size = sizeof(float);
1517
1518                 memset(sData->type_data, 0, data_size * sData->total_points);
1519
1520                 /* set initial color */
1521                 if (surface->type == MOD_DPAINT_SURFACE_T_PAINT)
1522                         dynamicPaint_setInitialColor(surface);
1523
1524                 if (sData->bData)
1525                         sData->bData->clear = 1;
1526         }
1527 }
1528
1529 /* completely (re)initializes surface (only for point cache types)*/
1530 int dynamicPaint_resetSurface(DynamicPaintSurface *surface)
1531 {
1532         int numOfPoints = dynamicPaint_surfaceNumOfPoints(surface);
1533         /* free existing data */
1534         if (surface->data) dynamicPaint_freeSurfaceData(surface);
1535
1536         /* don't reallocate for image sequence types. they get handled only on bake */
1537         if (surface->format == MOD_DPAINT_SURFACE_F_IMAGESEQ) return 1;
1538         if (numOfPoints < 1) return 0;
1539
1540         /* allocate memory */
1541         surface->data = MEM_callocN(sizeof(PaintSurfaceData), "PaintSurfaceData");
1542         if (!surface->data) return 0;
1543
1544         /* allocate data depending on surface type and format */
1545         surface->data->total_points = numOfPoints;
1546         dynamicPaint_allocateSurfaceType(surface);
1547         dynamicPaint_initAdjacencyData(surface, 0);
1548
1549         /* set initial color */
1550         if (surface->type == MOD_DPAINT_SURFACE_T_PAINT)
1551                 dynamicPaint_setInitialColor(surface);
1552
1553         return 1;
1554 }
1555
1556 /* make sure allocated surface size matches current requirements */
1557 static int dynamicPaint_checkSurfaceData(DynamicPaintSurface *surface)
1558 {
1559         if (!surface->data || ((dynamicPaint_surfaceNumOfPoints(surface) != surface->data->total_points))) {
1560                 return dynamicPaint_resetSurface(surface);
1561         }
1562         return 1;
1563 }
1564
1565
1566 /***************************** Modifier processing ******************************/
1567
1568
1569 /* apply displacing vertex surface to the derived mesh */
1570 static void dynamicPaint_applySurfaceDisplace(DynamicPaintSurface *surface, DerivedMesh *result)
1571 {
1572         PaintSurfaceData *sData = surface->data;
1573
1574         if (!sData || surface->format != MOD_DPAINT_SURFACE_F_VERTEX) return;
1575
1576         /* displace paint */
1577         if (surface->type == MOD_DPAINT_SURFACE_T_DISPLACE) {
1578                 MVert *mvert = result->getVertArray(result);
1579                 int i;
1580                 float* value = (float*)sData->type_data;
1581
1582                 #pragma omp parallel for schedule(static)
1583                 for (i=0; i<sData->total_points; i++) {
1584                         float normal[3], val=value[i]*surface->disp_factor;
1585                         normal_short_to_float_v3(normal, mvert[i].no);
1586                         normalize_v3(normal);
1587
1588                         mvert[i].co[0] -= normal[0]*val;
1589                         mvert[i].co[1] -= normal[1]*val;
1590                         mvert[i].co[2] -= normal[2]*val;
1591                 }
1592         }
1593 }
1594
1595 /*
1596 *       Apply canvas data to the object derived mesh
1597 */
1598 static struct DerivedMesh *dynamicPaint_Modifier_apply(DynamicPaintModifierData *pmd,
1599                                                        Object *ob,
1600                                                        DerivedMesh *dm)
1601 {       
1602         DerivedMesh *result = CDDM_copy(dm);
1603
1604         if (pmd->canvas && !(pmd->canvas->flags & MOD_DPAINT_BAKING)) {
1605
1606                 DynamicPaintSurface *surface;
1607                 int update_normals = 0;
1608
1609                 /* loop through surfaces */
1610                 for (surface = pmd->canvas->surfaces.first; surface; surface=surface->next) {
1611                         PaintSurfaceData *sData = surface->data;
1612
1613                         if (surface->format != MOD_DPAINT_SURFACE_F_IMAGESEQ && sData) {
1614                                 if (!(surface->flags & (MOD_DPAINT_ACTIVE))) continue;
1615
1616                                 /* process vertex surface previews */
1617                                 if (surface->format == MOD_DPAINT_SURFACE_F_VERTEX) {
1618
1619                                         /* vertex color paint */
1620                                         if (surface->type == MOD_DPAINT_SURFACE_T_PAINT) {
1621
1622                                                 int i;
1623                                                 PaintPoint* pPoint = (PaintPoint*)sData->type_data;
1624                                                 MLoopCol *col = NULL;
1625                                                 MLoop *mloop = CDDM_get_loops(result);
1626                                                 int totloop = result->numLoopData;
1627
1628                                                 /* paint is stored on dry and wet layers, so mix final color first */
1629                                                 float *fcolor = MEM_callocN(sizeof(float)*sData->total_points*4, "Temp paint color");
1630
1631                                                 #pragma omp parallel for schedule(static)
1632                                                 for (i=0; i<sData->total_points; i++) {
1633                                                         /* blend dry and wet layer */
1634                                                         blendColors(pPoint[i].color, pPoint[i].alpha, pPoint[i].e_color, pPoint[i].e_alpha, &fcolor[i*4]);
1635                                                 }
1636
1637                                                 /* viewport preview */
1638                                                 if (surface->flags & MOD_DPAINT_PREVIEW) {
1639                                                         MPoly *mp = CDDM_get_polys(result);
1640                                                         int totpoly = result->numPolyData;
1641
1642 #if 0
1643                                                         /* XXX We have to create a CD_PREVIEW_MCOL, else it might sigsev
1644                                                          *     (after a SubSurf mod, eg)... */
1645                                                         if (!result->getTessFaceDataArray(result, CD_PREVIEW_MCOL)) {
1646                                                                 int numFaces = result->getNumTessFaces(result);
1647                                                                 CustomData_add_layer(&result->faceData, CD_PREVIEW_MCOL, CD_CALLOC, NULL, numFaces);
1648                                                         }
1649 #endif
1650
1651                                                         /* Save preview results to weight layer to be
1652                                                         *   able to share same drawing methods */
1653                                                         col = CustomData_get_layer(&result->loopData, CD_PREVIEW_MLOOPCOL);
1654                                                         if (!col)
1655                                                                 col = CustomData_add_layer(&result->loopData, CD_PREVIEW_MLOOPCOL, CD_CALLOC,
1656                                                                                            NULL, totloop);
1657
1658                                                         if (col) {
1659                                                                 #pragma omp parallel for schedule(static)
1660                                                                 for (i=0; i<totpoly; i++) {
1661                                                                         int j=0;
1662                                                                         Material *material = give_current_material(ob, mp[i].mat_nr + 1);
1663
1664                                                                         for (; j<mp[i].totloop; j++) {
1665                                                                                 int l_index = mp[i].loopstart + j;
1666                                                                                 int v_index = mloop[l_index].v;
1667
1668                                                                                 if (surface->preview_id == MOD_DPAINT_SURFACE_PREV_PAINT) {
1669                                                                                         float c[3];
1670                                                                                         v_index *= 4;
1671
1672                                                                                         /* Apply material color as base vertex color for preview */
1673                                                                                         col[l_index].a = 255;
1674                                                                                         if (material) {
1675                                                                                                 c[0] = material->r;
1676                                                                                                 c[1] = material->g;
1677                                                                                                 c[2] = material->b;
1678                                                                                         }
1679                                                                                         else { /* default grey */
1680                                                                                                 c[0] = 0.65f;
1681                                                                                                 c[1] = 0.65f;
1682                                                                                                 c[2] = 0.65f;
1683                                                                                         }
1684                                                                                         /* mix surface color */
1685                                                                                         interp_v3_v3v3(c, c, &fcolor[v_index], fcolor[v_index+3]);
1686
1687                                                                                         rgb_float_to_uchar((unsigned char *)&col[l_index].r, c);
1688                                                                                 }
1689                                                                                 else {
1690                                                                                         col[l_index].r =
1691                                                                                         col[l_index].g =
1692                                                                                         col[l_index].b = FTOCHAR(pPoint[v_index].wetness);
1693                                                                                         col[l_index].a = 255;
1694                                                                                 }
1695                                                                         }
1696                                                                 }
1697                                                         }
1698                                                 }
1699
1700
1701                                                 /* save layer data to output layer */
1702
1703                                                 /* paint layer */
1704                                                 col = CustomData_get_layer_named(&result->loopData, CD_MLOOPCOL, surface->output_name);
1705                                                 /* if output layer is lost from a constructive modifier, re-add it */
1706                                                 if (!col && dynamicPaint_outputLayerExists(surface, ob, 0))
1707                                                         col = CustomData_add_layer_named(&result->loopData, CD_MLOOPCOL, CD_CALLOC, NULL, totloop, surface->output_name);
1708                                                 /* apply color */
1709                                                 if (col) {
1710                                                         #pragma omp parallel for schedule(static)
1711                                                         for (i=0; i<totloop; i++) {
1712                                                                 int index = mloop[i].v*4;
1713                                                                 rgb_float_to_uchar((unsigned char *)&col[i].r, &fcolor[index]);
1714                                                                 col[i].a = FTOCHAR(fcolor[index+3]); /* IS THIS NEEDED? */
1715                                                         }
1716                                                 }
1717                                                 
1718                                                 MEM_freeN(fcolor);
1719
1720                                                 /* wet layer */
1721                                                 col = CustomData_get_layer_named(&result->loopData, CD_MLOOPCOL, surface->output_name2);
1722                                                 /* if output layer is lost from a constructive modifier, re-add it */
1723                                                 if (!col && dynamicPaint_outputLayerExists(surface, ob, 1))
1724                                                         col = CustomData_add_layer_named(&result->loopData, CD_MLOOPCOL, CD_CALLOC, NULL, totloop, surface->output_name2);
1725                                                 /* apply color */
1726                                                 if (col) {
1727                                                         #pragma omp parallel for schedule(static)
1728                                                         for (i=0; i<totloop; i++) {
1729                                                                 int index = mloop[i].v;
1730                                                                 col[i].r =
1731                                                                 col[i].g =
1732                                                                 col[i].b = FTOCHAR(pPoint[index].wetness);
1733                                                                 col[i].a = 255;
1734                                                         }
1735                                                 }
1736
1737                                                 /* Mark tessellated CD layers as dirty. */
1738                                                 result->dirty |= DM_DIRTY_TESS_CDLAYERS;
1739                                         }
1740                                         /* vertex group paint */
1741                                         else if (surface->type == MOD_DPAINT_SURFACE_T_WEIGHT) {
1742                                                 int defgrp_index = defgroup_name_index(ob, surface->output_name);
1743                                                 MDeformVert *dvert = result->getVertDataArray(result, CD_MDEFORMVERT);
1744                                                 float *weight = (float*)sData->type_data;
1745
1746                                                 /* viewport preview */
1747                                                 if (surface->flags & MOD_DPAINT_PREVIEW) {
1748                                                         /* Save preview results to weight layer to be
1749                                                          * able to share same drawing methods.
1750                                                          * Note this func also sets DM_DIRTY_TESS_CDLAYERS flag! */
1751                                                         DM_update_weight_mcol(ob, result, 0, weight, 0, NULL);
1752                                                 }
1753
1754                                                 /* apply weights into a vertex group, if doesnt exists add a new layer */
1755                                                 if (defgrp_index >= 0 && !dvert && (surface->output_name[0] != '\0'))
1756                                                         dvert = CustomData_add_layer_named(&result->vertData, CD_MDEFORMVERT, CD_CALLOC,
1757                                                                                                                                 NULL, sData->total_points, surface->output_name);
1758                                                 if (defgrp_index >= 0 && dvert) {
1759                                                         int i;
1760                                                         for (i=0; i<sData->total_points; i++) {
1761                                                                 MDeformVert *dv= &dvert[i];
1762                                                                 MDeformWeight *def_weight = defvert_find_index(dv, defgrp_index);
1763
1764                                                                 /* skip if weight value is 0 and no existing weight is found */
1765                                                                 if ((def_weight != NULL) || (weight[i] != 0.0f)) {
1766
1767                                                                         /* if not found, add a weight for it */
1768                                                                         if (def_weight == NULL) {
1769                                                                                 def_weight= defvert_verify_index(dv, defgrp_index);
1770                                                                         }
1771
1772                                                                         /* set weight value */
1773                                                                         def_weight->weight = weight[i];
1774                                                                 }
1775                                                         }
1776                                                 }
1777                                         }
1778                                         /* wave simulation */
1779                                         else if (surface->type == MOD_DPAINT_SURFACE_T_WAVE) {
1780                                                 MVert *mvert = result->getVertArray(result);
1781                                                 int i;
1782                                                 PaintWavePoint* wPoint = (PaintWavePoint*)sData->type_data;
1783
1784                                                 #pragma omp parallel for schedule(static)
1785                                                 for (i=0; i<sData->total_points; i++) {
1786                                                         float normal[3];
1787                                                         normal_short_to_float_v3(normal, mvert[i].no);
1788                                                         madd_v3_v3fl(mvert[i].co, normal, wPoint[i].height);
1789                                                 }
1790                                                 update_normals = 1;
1791                                         }
1792
1793                                         /* displace */
1794                                         if (surface->type == MOD_DPAINT_SURFACE_T_DISPLACE) {
1795                                                 dynamicPaint_applySurfaceDisplace(surface, result);
1796                                                 update_normals = 1;
1797                                         }
1798                                 }
1799                         }
1800                 }
1801
1802                 if (update_normals)
1803                         CDDM_calc_normals(result);
1804         }
1805         /* make a copy of dm to use as brush data */
1806         if (pmd->brush) {
1807                 if (pmd->brush->dm) pmd->brush->dm->release(pmd->brush->dm);
1808                 pmd->brush->dm = CDDM_copy(result);
1809         }
1810
1811         return result;
1812 }
1813
1814 /* update cache frame range */
1815 void dynamicPaint_cacheUpdateFrames(DynamicPaintSurface *surface)
1816 {
1817         if (surface->pointcache) {
1818                 surface->pointcache->startframe = surface->start_frame;
1819                 surface->pointcache->endframe = surface->end_frame;
1820         }
1821 }
1822
1823 void canvas_copyDerivedMesh(DynamicPaintCanvasSettings *canvas, DerivedMesh *dm)
1824 {
1825         if (canvas->dm) canvas->dm->release(canvas->dm);
1826         canvas->dm = CDDM_copy(dm);
1827 }
1828
1829 /*
1830 *       Updates derived mesh copy and processes dynamic paint step / caches.
1831 */
1832 static void dynamicPaint_frameUpdate(DynamicPaintModifierData *pmd, Scene *scene, Object *ob, DerivedMesh *dm)
1833 {
1834         if (pmd->canvas) {
1835                 DynamicPaintCanvasSettings *canvas = pmd->canvas;
1836                 DynamicPaintSurface *surface = canvas->surfaces.first;
1837
1838                 /* update derived mesh copy */
1839                 canvas_copyDerivedMesh(canvas, dm);
1840
1841                 /* in case image sequence baking, stop here */
1842                 if (canvas->flags & MOD_DPAINT_BAKING) return;
1843
1844                 /* loop through surfaces */
1845                 for (; surface; surface=surface->next) {
1846                         int current_frame = (int)scene->r.cfra;
1847
1848                         /* free bake data if not required anymore */
1849                         surface_freeUnusedData(surface);
1850
1851                         /* image sequences are handled by bake operator */
1852                         if (surface->format == MOD_DPAINT_SURFACE_F_IMAGESEQ) continue;
1853                         if (!(surface->flags & MOD_DPAINT_ACTIVE)) continue;
1854
1855                         /* make sure surface is valid */
1856                         if (!dynamicPaint_checkSurfaceData(surface)) continue;
1857
1858                         /* limit frame range */
1859                         CLAMP(current_frame, surface->start_frame, surface->end_frame);
1860
1861                         if (current_frame != surface->current_frame || (int)scene->r.cfra == surface->start_frame) {
1862                                 PointCache *cache = surface->pointcache;
1863                                 PTCacheID pid;
1864                                 surface->current_frame = current_frame;
1865
1866                                 /* read point cache */
1867                                 BKE_ptcache_id_from_dynamicpaint(&pid, ob, surface);
1868                                 pid.cache->startframe = surface->start_frame;
1869                                 pid.cache->endframe = surface->end_frame;
1870                                 BKE_ptcache_id_time(&pid, scene, (float)scene->r.cfra, NULL, NULL, NULL);
1871
1872                                 /* reset non-baked cache at first frame */
1873                                 if ((int)scene->r.cfra == surface->start_frame && !(cache->flag & PTCACHE_BAKED)) {
1874                                         cache->flag |= PTCACHE_REDO_NEEDED;
1875                                         BKE_ptcache_id_reset(scene, &pid, PTCACHE_RESET_OUTDATED);
1876                                         cache->flag &= ~PTCACHE_REDO_NEEDED;
1877                                 }
1878
1879                                 /* try to read from cache */
1880                                 if (BKE_ptcache_read(&pid, (float)scene->r.cfra)) {
1881                                         BKE_ptcache_validate(cache, (int)scene->r.cfra);
1882                                 }
1883                                 /* if read failed and we're on surface range do recalculate */
1884                                 else if ((int)scene->r.cfra == current_frame && !(cache->flag & PTCACHE_BAKED)) {
1885                                         /* calculate surface frame */
1886                                         canvas->flags |= MOD_DPAINT_BAKING;
1887                                         dynamicPaint_calculateFrame(surface, scene, ob, current_frame);
1888                                         canvas->flags &= ~MOD_DPAINT_BAKING;
1889
1890                                         /* restore canvas derivedmesh if required */
1891                                         if (surface->type == MOD_DPAINT_SURFACE_T_DISPLACE &&
1892                                             surface->flags & MOD_DPAINT_DISP_INCREMENTAL && surface->next)
1893                                         {
1894                                                 canvas_copyDerivedMesh(canvas, dm);
1895                                         }
1896
1897                                         BKE_ptcache_validate(cache, surface->current_frame);
1898                                         BKE_ptcache_write(&pid, surface->current_frame);
1899                                 }
1900                         }
1901                 }
1902         }
1903 }
1904
1905 /* Modifier call. Processes dynamic paint modifier step. */
1906 struct DerivedMesh *dynamicPaint_Modifier_do(DynamicPaintModifierData *pmd, Scene *scene, Object *ob, DerivedMesh *dm)
1907 {       
1908         /* For now generate tessfaces in every case
1909         *  XXX - move/remove when most of dpaint functions are converted to use bmesh types */
1910         DM_ensure_tessface(dm);
1911
1912         /* Update canvas data for a new frame */
1913         dynamicPaint_frameUpdate(pmd, scene, ob, dm);
1914
1915         /* Return output mesh */
1916         return dynamicPaint_Modifier_apply(pmd, ob, dm);
1917 }
1918
1919
1920 /***************************** Image Sequence / UV Image Surface Calls ******************************/
1921
1922 /*
1923 *       Tries to find the neighboring pixel in given (uv space) direction.
1924 *       Result is used by effect system to move paint on the surface.
1925 *
1926 *   px, py : origin pixel x and y
1927 *       n_index : lookup direction index (use neighX, neighY to get final index)
1928 */
1929 static int dynamicPaint_findNeighbourPixel(PaintUVPoint *tempPoints, DerivedMesh *dm,
1930                                            const char *uvname, int w, int h, int px, int py, int n_index)
1931 {
1932         /* Note: Current method only uses polygon edges to detect neighboring pixels.
1933         *  -> It doesn't always lead to the optimum pixel but is accurate enough
1934         *  and faster/simplier than including possible face tip point links)
1935         */
1936
1937         int x, y;
1938         PaintUVPoint *tPoint = NULL;
1939         PaintUVPoint *cPoint = NULL;
1940
1941         /* shift position by given n_index */
1942         x = px + neighX[n_index];
1943         y = py + neighY[n_index];
1944
1945         if (x<0 || x>=w) return OUT_OF_TEXTURE;
1946         if (y<0 || y>=h) return OUT_OF_TEXTURE;
1947
1948         tPoint = &tempPoints[x+w*y];            /* UV neighbor */
1949         cPoint = &tempPoints[px+w*py];          /* Origin point */
1950
1951         /*
1952         *       Check if shifted point is on same face -> it's a correct neighbor
1953         *   (and if it isn't marked as an "edge pixel")
1954         */
1955         if ((tPoint->face_index == cPoint->face_index) && (tPoint->neighbour_pixel == -1))
1956                 return (x+w*y);
1957
1958         /*
1959         *       Even if shifted point is on another face
1960         *       -> use this point.
1961         *       
1962         *       !! Replace with "is uv faces linked" check !!
1963         *       This should work fine as long as uv island
1964         *       margin is > 1 pixel.
1965         */
1966         if ((tPoint->face_index != -1) && (tPoint->neighbour_pixel == -1)) {
1967                 return (x+w*y);
1968         }
1969
1970         /*
1971         *       If we get here, the actual neighboring pixel
1972         *       is located on a non-linked uv face, and we have to find
1973         *       it's "real" position.
1974         *
1975         *       Simple neighboring face finding algorithm:
1976         *       - find closest uv edge to shifted pixel and get
1977         *         the another face that shares that edge
1978         *       - find corresponding position of that new face edge
1979         *         in uv space
1980         *
1981         *       TODO: Implement something more accurate / optimized?
1982         */
1983         {
1984                 int numOfFaces = dm->getNumTessFaces(dm);
1985                 MFace *mface = dm->getTessFaceArray(dm);
1986                 MTFace *tface =  CustomData_get_layer_named(&dm->faceData, CD_MTFACE, uvname);
1987
1988                 /* Get closest edge to that subpixel on UV map  */
1989                 {
1990                         float pixel[2], dist, t_dist;
1991                         int i, uindex[3], edge1_index, edge2_index,
1992                                 e1_index, e2_index, target_face;
1993                         float closest_point[2], lambda, dir_vec[2];
1994                         int target_uv1, target_uv2, final_pixel[2], final_index;
1995
1996                         float *s_uv1, *s_uv2, *t_uv1, *t_uv2;
1997
1998                         pixel[0] = ((float)(px + neighX[n_index]) + 0.5f) / (float)w;
1999                         pixel[1] = ((float)(py + neighY[n_index]) + 0.5f) / (float)h;
2000
2001                         /* Get uv indexes for current face part */
2002                         if (cPoint->quad) {
2003                                 uindex[0] = 0; uindex[1] = 2; uindex[2] = 3;
2004                         }
2005                         else {
2006                                 uindex[0] = 0; uindex[1] = 1; uindex[2] = 2;
2007                         }
2008
2009                         /*
2010                         *       Find closest edge to that pixel
2011                         */
2012                         /* Dist to first edge   */
2013                         e1_index = cPoint->v1; e2_index = cPoint->v2; edge1_index = uindex[0]; edge2_index = uindex[1];
2014                         dist = dist_to_line_segment_v2(pixel, tface[cPoint->face_index].uv[edge1_index], tface[cPoint->face_index].uv[edge2_index]);
2015
2016                         /* Dist to second edge  */
2017                         t_dist = dist_to_line_segment_v2(pixel, tface[cPoint->face_index].uv[uindex[1]], tface[cPoint->face_index].uv[uindex[2]]);
2018                         if (t_dist < dist) {e1_index = cPoint->v2; e2_index = cPoint->v3; edge1_index = uindex[1]; edge2_index = uindex[2]; dist = t_dist;}
2019
2020                         /* Dist to third edge   */
2021                         t_dist = dist_to_line_segment_v2(pixel, tface[cPoint->face_index].uv[uindex[2]], tface[cPoint->face_index].uv[uindex[0]]);
2022                         if (t_dist < dist) {e1_index = cPoint->v3; e2_index = cPoint->v1;  edge1_index = uindex[2]; edge2_index = uindex[0]; dist = t_dist;}
2023
2024
2025                         /*
2026                         *       Now find another face that is linked to that edge
2027                         */
2028                         target_face = -1;
2029
2030                         for (i=0; i<numOfFaces; i++) {
2031                                 /*
2032                                 *       Check if both edge vertices share this face
2033                                 */
2034                                 int v4 = (mface[i].v4) ? mface[i].v4 : -1;
2035
2036                                 if ((e1_index == mface[i].v1 || e1_index == mface[i].v2 || e1_index == mface[i].v3 || e1_index == v4) &&
2037                                         (e2_index == mface[i].v1 || e2_index == mface[i].v2 || e2_index == mface[i].v3 || e2_index == v4)) {
2038                                         if (i == cPoint->face_index) continue;
2039
2040                                         target_face = i;
2041
2042                                         /*
2043                                         *       Get edge UV index
2044                                         */
2045                                         if (e1_index == mface[i].v1) target_uv1 = 0;
2046                                         else if (e1_index == mface[i].v2) target_uv1 = 1;
2047                                         else if (e1_index == mface[i].v3) target_uv1 = 2;
2048                                         else target_uv1 = 3;
2049
2050                                         if (e2_index == mface[i].v1) target_uv2 = 0;
2051                                         else if (e2_index == mface[i].v2) target_uv2 = 1;
2052                                         else if (e2_index == mface[i].v3) target_uv2 = 2;
2053                                         else target_uv2 = 3;
2054
2055                                         break;
2056                                 }
2057                         }
2058
2059                         /* If none found pixel is on mesh edge  */
2060                         if (target_face == -1) return ON_MESH_EDGE;
2061
2062                         /*
2063                         *       If target face is connected in UV space as well, just use original index
2064                         */
2065                         s_uv1 = (float *)tface[cPoint->face_index].uv[edge1_index];
2066                         s_uv2 = (float *)tface[cPoint->face_index].uv[edge2_index];
2067                         t_uv1 = (float *)tface[target_face].uv[target_uv1];
2068                         t_uv2 = (float *)tface[target_face].uv[target_uv2];
2069
2070                         //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]);
2071
2072                         if (((s_uv1[0] == t_uv1[0] && s_uv1[1] == t_uv1[1]) &&
2073                              (s_uv2[0] == t_uv2[0] && s_uv2[1] == t_uv2[1]) ) ||
2074                             ((s_uv2[0] == t_uv1[0] && s_uv2[1] == t_uv1[1]) &&
2075                              (s_uv1[0] == t_uv2[0] && s_uv1[1] == t_uv2[1]) ))
2076                         {
2077                                 return ((px+neighX[n_index]) + w*(py+neighY[n_index]));
2078                         }
2079
2080                         /*
2081                         *       Find a point that is relatively at same edge position
2082                         *       on this other face UV
2083                         */
2084                         lambda = closest_to_line_v2(closest_point, pixel, tface[cPoint->face_index].uv[edge1_index], tface[cPoint->face_index].uv[edge2_index]);
2085                         if (lambda < 0.0f) lambda = 0.0f;
2086                         if (lambda > 1.0f) lambda = 1.0f;
2087
2088                         sub_v2_v2v2(dir_vec, tface[target_face].uv[target_uv2], tface[target_face].uv[target_uv1]);
2089
2090                         mul_v2_fl(dir_vec, lambda);
2091
2092                         copy_v2_v2(pixel, tface[target_face].uv[target_uv1]);
2093                         add_v2_v2(pixel, dir_vec);
2094                         pixel[0] = (pixel[0] * (float)w) - 0.5f;
2095                         pixel[1] = (pixel[1] * (float)h) - 0.5f;
2096
2097                         final_pixel[0] = (int)floor(pixel[0]);
2098                         final_pixel[1] = (int)floor(pixel[1]);
2099
2100                         /* If current pixel uv is outside of texture    */
2101                         if (final_pixel[0] < 0 || final_pixel[0] >= w) return OUT_OF_TEXTURE;
2102                         if (final_pixel[1] < 0 || final_pixel[1] >= h) return OUT_OF_TEXTURE;
2103
2104                         final_index = final_pixel[0] + w * final_pixel[1];
2105
2106                         /* If we ended up to our origin point ( mesh has smaller than pixel sized faces)        */
2107                         if (final_index == (px+w*py)) return NOT_FOUND;
2108                         /* If found pixel still lies on wrong face ( mesh has smaller than pixel sized faces)   */
2109                         if (tempPoints[final_index].face_index != target_face) return NOT_FOUND;
2110
2111                         /*
2112                         *       If final point is an "edge pixel", use it's "real" neighbor instead
2113                         */
2114                         if (tempPoints[final_index].neighbour_pixel != -1) final_index = cPoint->neighbour_pixel;
2115
2116                         return final_index;
2117                 }
2118         }
2119 }
2120
2121 /*
2122 *       Create a surface for uv image sequence format
2123 */
2124 int dynamicPaint_createUVSurface(DynamicPaintSurface *surface)
2125 {
2126         /* Antialias jitter point relative coords       */
2127         float jitter5sample[10] =  {0.0f, 0.0f,
2128                                                         -0.2f, -0.4f,
2129                                                         0.2f, 0.4f,
2130                                                         0.4f, -0.2f,
2131                                                         -0.4f, 0.3f};
2132         int ty;
2133         int w, h;
2134         int numOfFaces;
2135         char uvname[MAX_CUSTOMDATA_LAYER_NAME];
2136         int active_points = 0;
2137         int error = 0;
2138
2139         PaintSurfaceData *sData;
2140         DynamicPaintCanvasSettings *canvas = surface->canvas;
2141         DerivedMesh *dm = canvas->dm;
2142
2143         PaintUVPoint *tempPoints = NULL;
2144         Vec3f *tempWeights = NULL;
2145         MFace *mface = NULL;
2146         MTFace *tface = NULL;
2147         Bounds2D *faceBB = NULL;
2148         int *final_index;
2149         int aa_samples;
2150
2151         if (!dm) return setError(canvas, "Canvas mesh not updated.");
2152         if (surface->format != MOD_DPAINT_SURFACE_F_IMAGESEQ) return setError(canvas, "Can't bake non-\"image sequence\" formats.");
2153
2154         numOfFaces = dm->getNumTessFaces(dm);
2155         mface = dm->getTessFaceArray(dm);
2156
2157         /* get uv map */
2158         CustomData_validate_layer_name(&dm->faceData, CD_MTFACE, surface->uvlayer_name, uvname);
2159         tface = CustomData_get_layer_named(&dm->faceData, CD_MTFACE, uvname);
2160
2161         /* Check for validity   */
2162         if (!tface) return setError(canvas, "No UV data on canvas.");
2163         if (surface->image_resolution < 16 || surface->image_resolution > 8192) return setError(canvas, "Invalid resolution.");
2164
2165         w = h = surface->image_resolution;
2166
2167         /*
2168         *       Start generating the surface
2169         */
2170         printf("DynamicPaint: Preparing UV surface of %ix%i pixels and %i faces.\n", w, h, numOfFaces);
2171
2172         /* Init data struct */
2173         if (surface->data) dynamicPaint_freeSurfaceData(surface);
2174         sData = surface->data = MEM_callocN(sizeof(PaintSurfaceData), "PaintSurfaceData");
2175         if (!surface->data) return setError(canvas, "Not enough free memory.");
2176
2177         aa_samples = (surface->flags & MOD_DPAINT_ANTIALIAS) ? 5 : 1;
2178         tempPoints = (struct PaintUVPoint *) MEM_callocN(w*h*sizeof(struct PaintUVPoint), "Temp PaintUVPoint");
2179         if (!tempPoints) error=1;
2180
2181         final_index = (int *) MEM_callocN(w*h*sizeof(int), "Temp UV Final Indexes");
2182         if (!final_index) error=1;
2183
2184         tempWeights = (struct Vec3f *) MEM_mallocN(w*h*aa_samples*sizeof(struct Vec3f), "Temp bWeights");
2185         if (!tempWeights) error=1;
2186
2187         /*
2188         *       Generate a temporary bounding box array for UV faces to optimize
2189         *       the pixel-inside-a-face search.
2190         */
2191         if (!error) {
2192                 faceBB = (struct Bounds2D *) MEM_mallocN(numOfFaces*sizeof(struct Bounds2D), "MPCanvasFaceBB");
2193                 if (!faceBB) error=1;
2194         }
2195
2196         if (!error)
2197         for (ty=0; ty<numOfFaces; ty++) {
2198                 int numOfVert = (mface[ty].v4) ? 4 : 3;
2199                 int i;
2200
2201                 copy_v2_v2(faceBB[ty].min, tface[ty].uv[0]);
2202                 copy_v2_v2(faceBB[ty].max, tface[ty].uv[0]);
2203
2204                 for (i = 1; i<numOfVert; i++) {
2205                         if (tface[ty].uv[i][0] < faceBB[ty].min[0]) faceBB[ty].min[0] = tface[ty].uv[i][0];
2206                         if (tface[ty].uv[i][1] < faceBB[ty].min[1]) faceBB[ty].min[1] = tface[ty].uv[i][1];
2207                         if (tface[ty].uv[i][0] > faceBB[ty].max[0]) faceBB[ty].max[0] = tface[ty].uv[i][0];
2208                         if (tface[ty].uv[i][1] > faceBB[ty].max[1]) faceBB[ty].max[1] = tface[ty].uv[i][1];
2209
2210                 }
2211         }
2212
2213         /*
2214         *       Loop through every pixel and check
2215         *       if pixel is uv-mapped on a canvas face.
2216         */
2217         if (!error) {
2218                 #pragma omp parallel for schedule(static)
2219                 for (ty = 0; ty < h; ty++) {
2220                         int tx;
2221                         for (tx = 0; tx < w; tx++) {
2222                                 int i, sample;
2223                                 int index = tx+w*ty;
2224                                 PaintUVPoint *tPoint = (&tempPoints[index]);
2225
2226                                 short isInside = 0;     /* if point is inside a uv face */
2227
2228                                 float d1[2], d2[2], d3[2], point[5][2];
2229                                 float dot00, dot01, dot02, dot11, dot12, invDenom, u, v;
2230
2231                                 /* Init per pixel settings */
2232                                 tPoint->face_index = -1;
2233                                 tPoint->neighbour_pixel = -1;
2234                                 tPoint->pixel_index = index;
2235
2236                                 /* Actual pixel center, used when collision is found    */
2237                                 point[0][0] = ((float)tx + 0.5f) / w;
2238                                 point[0][1] = ((float)ty + 0.5f) / h;
2239
2240                                 /*
2241                                 * A pixel middle sample isn't enough to find very narrow polygons
2242                                 * So using 4 samples of each corner too
2243                                 */
2244                                 point[1][0] = ((float)tx) / w;
2245                                 point[1][1] = ((float)ty) / h;
2246
2247                                 point[2][0] = ((float)tx+1) / w;
2248                                 point[2][1] = ((float)ty) / h;
2249
2250                                 point[3][0] = ((float)tx) / w;
2251                                 point[3][1] = ((float)ty+1) / h;
2252
2253                                 point[4][0] = ((float)tx+1) / w;
2254                                 point[4][1] = ((float)ty+1) / h;
2255
2256
2257                                 /* Loop through samples, starting from middle point     */
2258                                 for (sample=0; sample<5; sample++) {
2259                                         
2260                                         /* Loop through every face in the mesh  */
2261                                         for (i=0; i<numOfFaces; i++) {
2262
2263                                                 /* Check uv bb  */
2264                                                 if (faceBB[i].min[0] > (point[sample][0])) continue;
2265                                                 if (faceBB[i].min[1] > (point[sample][1])) continue;
2266                                                 if (faceBB[i].max[0] < (point[sample][0])) continue;
2267                                                 if (faceBB[i].max[1] < (point[sample][1])) continue;
2268
2269                                                 /*  Calculate point inside a triangle check
2270                                                 *       for uv0, 1, 2 */
2271                                                 sub_v2_v2v2(d1,  tface[i].uv[2], tface[i].uv[0]);       // uv2 - uv0
2272                                                 sub_v2_v2v2(d2,  tface[i].uv[1], tface[i].uv[0]);       // uv1 - uv0
2273                                                 sub_v2_v2v2(d3,  point[sample], tface[i].uv[0]);        // point - uv0
2274
2275                                                 dot00 = d1[0]*d1[0] + d1[1]*d1[1];
2276                                                 dot01 = d1[0]*d2[0] + d1[1]*d2[1];
2277                                                 dot02 = d1[0]*d3[0] + d1[1]*d3[1];
2278                                                 dot11 = d2[0]*d2[0] + d2[1]*d2[1];
2279                                                 dot12 = d2[0]*d3[0] + d2[1]*d3[1];
2280
2281                                                 invDenom = 1 / (dot00 * dot11 - dot01 * dot01);
2282                                                 u = (dot11 * dot02 - dot01 * dot12) * invDenom;
2283                                                 v = (dot00 * dot12 - dot01 * dot02) * invDenom;
2284
2285                                                 if ((u > 0) && (v > 0) && (u + v < 1)) {isInside=1;} /* is inside a triangle */
2286
2287                                                 /*  If collision wasn't found but the face is a quad
2288                                                 *       do another check for the second half */
2289                                                 if ((!isInside) && mface[i].v4) {
2290
2291                                                         /* change d2 to test the other half     */
2292                                                         sub_v2_v2v2(d2,  tface[i].uv[3], tface[i].uv[0]);       // uv3 - uv0
2293
2294                                                         /* test again   */
2295                                                         dot00 = d1[0]*d1[0] + d1[1]*d1[1];
2296                                                         dot01 = d1[0]*d2[0] + d1[1]*d2[1];
2297                                                         dot02 = d1[0]*d3[0] + d1[1]*d3[1];
2298                                                         dot11 = d2[0]*d2[0] + d2[1]*d2[1];
2299                                                         dot12 = d2[0]*d3[0] + d2[1]*d3[1];
2300
2301                                                         invDenom = 1 / (dot00 * dot11 - dot01 * dot01);
2302                                                         u = (dot11 * dot02 - dot01 * dot12) * invDenom;
2303                                                         v = (dot00 * dot12 - dot01 * dot02) * invDenom;
2304
2305                                                         if ((u > 0) && (v > 0) && (u + v < 1)) {isInside=2;} /* is inside the second half of the quad */
2306
2307                                                 }
2308
2309                                                 /*
2310                                                 *       If point was inside the face
2311                                                 */
2312                                                 if (isInside != 0) {
2313
2314                                                         float uv1co[2], uv2co[2], uv3co[2], uv[2];
2315                                                         int j;
2316
2317                                                         /* Get triagnle uvs     */
2318                                                         if (isInside==1) {
2319                                                                 copy_v2_v2(uv1co, tface[i].uv[0]);
2320                                                                 copy_v2_v2(uv2co, tface[i].uv[1]);
2321                                                                 copy_v2_v2(uv3co, tface[i].uv[2]);
2322                                                         }
2323                                                         else {
2324                                                                 copy_v2_v2(uv1co, tface[i].uv[0]);
2325                                                                 copy_v2_v2(uv2co, tface[i].uv[2]);
2326                                                                 copy_v2_v2(uv3co, tface[i].uv[3]);
2327                                                         }
2328
2329                                                         /* Add b-weights per anti-aliasing sample       */
2330                                                         for (j=0; j<aa_samples; j++) {
2331                                                                 uv[0] = point[0][0] + jitter5sample[j*2] / w;
2332                                                                 uv[1] = point[0][1] + jitter5sample[j*2+1] / h;
2333
2334                                                                 barycentric_weights_v2(uv1co, uv2co, uv3co, uv, tempWeights[index*aa_samples+j].v);
2335                                                         }
2336
2337                                                         /* Set surface point face values        */
2338                                                         tPoint->face_index = i;                                                 /* face index */
2339                                                         tPoint->quad = (isInside == 2) ? 1 : 0;         /* quad or tri part*/
2340
2341                                                         /* save vertex indexes  */
2342                                                         tPoint->v1 = mface[i].v1;
2343                                                         tPoint->v2 = (isInside == 2) ? mface[i].v3 : mface[i].v2;
2344                                                         tPoint->v3 = (isInside == 2) ? mface[i].v4 : mface[i].v3;
2345
2346                                                         sample = 5;     /* make sure we exit sample loop as well */
2347                                                         break;
2348                                                 }
2349                                         }
2350                                 } /* sample loop */
2351                         }
2352                 }
2353
2354                 /*
2355                 *       Now loop through every pixel that was left without index
2356                 *       and find if they have neighboring pixels that have an index.
2357                 *       If so use that polygon as pixel surface.
2358                 *       (To avoid seams on uv island edges)
2359                 */
2360                 #pragma omp parallel for schedule(static)
2361                 for (ty = 0; ty < h; ty++) {
2362                         int tx;
2363                         for (tx = 0; tx < w; tx++) {
2364                                 int index = tx+w*ty;
2365                                 PaintUVPoint *tPoint = (&tempPoints[index]);
2366
2367                                 /* If point isn't't on canvas mesh      */
2368                                 if (tPoint->face_index == -1) {
2369                                         int u_min, u_max, v_min, v_max;
2370                                         int u, v, ind;
2371                                         float point[2];
2372
2373                                         /* get loop area        */
2374                                         u_min = (tx > 0) ? -1 : 0;
2375                                         u_max = (tx < (w-1)) ? 1 : 0;
2376                                         v_min = (ty > 0) ? -1 : 0;
2377                                         v_max = (ty < (h-1)) ? 1 : 0;
2378
2379                                         point[0] = ((float)tx + 0.5f) / w;
2380                                         point[1] = ((float)ty + 0.5f) / h;
2381
2382                                         /* search through defined area for neighbor     */
2383                                         for (u=u_min; u<=u_max; u++)
2384                                                 for (v=v_min; v<=v_max; v++) {
2385                                                         /* if not this pixel itself     */
2386                                                         if (u!=0 || v!=0) {
2387                                                                 ind = (tx+u)+w*(ty+v);
2388
2389                                                                 /* if neighbor has index        */
2390                                                                 if (tempPoints[ind].face_index != -1) {
2391
2392                                                                         float uv1co[2], uv2co[2], uv3co[2], uv[2];
2393                                                                         int i = tempPoints[ind].face_index, j;
2394
2395                                                                         /* Now calculate pixel data for this pixel as it was on polygon surface */
2396                                                                         if (!tempPoints[ind].quad) {
2397                                                                                 copy_v2_v2(uv1co, tface[i].uv[0]);
2398                                                                                 copy_v2_v2(uv2co, tface[i].uv[1]);
2399                                                                                 copy_v2_v2(uv3co, tface[i].uv[2]);
2400                                                                         }
2401                                                                         else {
2402                                                                                 copy_v2_v2(uv1co, tface[i].uv[0]);
2403                                                                                 copy_v2_v2(uv2co, tface[i].uv[2]);
2404                                                                                 copy_v2_v2(uv3co, tface[i].uv[3]);
2405                                                                         }
2406
2407                                                                         /* Add b-weights per anti-aliasing sample       */
2408                                                                         for (j=0; j<aa_samples; j++) {
2409
2410                                                                                 uv[0] = point[0] + jitter5sample[j*2] / w;
2411                                                                                 uv[1] = point[1] + jitter5sample[j*2+1] / h;
2412                                                                                 barycentric_weights_v2(uv1co, uv2co, uv3co, uv, tempWeights[index*aa_samples+j].v);
2413                                                                         }
2414
2415                                                                         /* Set values   */
2416                                                                         tPoint->neighbour_pixel = ind;                          // face index
2417                                                                         tPoint->quad = tempPoints[ind].quad;            // quad or tri
2418
2419                                                                         /* save vertex indexes  */
2420                                                                         tPoint->v1 = mface[i].v1;
2421                                                                         tPoint->v2 = (tPoint->quad) ? mface[i].v3 : mface[i].v2;
2422                                                                         tPoint->v3 = (tPoint->quad) ? mface[i].v4 : mface[i].v3;
2423
2424                                                                         u = u_max + 1;  /* make sure we exit outer loop as well */
2425                                                                         break;
2426                                                                 }
2427                                                 }
2428                                         }
2429                                 }
2430                         }
2431                 }
2432
2433                 /*
2434                 *       When base loop is over convert found neighbor indexes to real ones
2435                 *       Also count the final number of active surface points
2436                 */
2437                 for (ty = 0; ty < h; ty++) {
2438                         int tx;
2439                         for (tx = 0; tx < w; tx++) {
2440                                 int index = tx+w*ty;
2441                                 PaintUVPoint *tPoint = (&tempPoints[index]);
2442
2443                                 if (tPoint->face_index == -1 && tPoint->neighbour_pixel != -1) tPoint->face_index = tempPoints[tPoint->neighbour_pixel].face_index;
2444                                 if (tPoint->face_index != -1) active_points++;
2445                         }
2446                 }
2447
2448                 /*      Generate surface adjacency data. */
2449                 {
2450                         int i, cursor=0;
2451
2452                         /* Create a temporary array of final indexes (before unassigned
2453                         *  pixels have been dropped) */
2454                         for (i=0; i<w*h; i++) {
2455                                 if (tempPoints[i].face_index != -1) {
2456                                         final_index[i] = cursor;
2457                                         cursor++;
2458                                 }
2459                         }
2460                         /* allocate memory */
2461                         sData->total_points = w*h;
2462                         dynamicPaint_initAdjacencyData(surface, 1);
2463
2464                         if (sData->adj_data) {
2465                                 PaintAdjData *ed = sData->adj_data;
2466                                 unsigned int n_pos = 0;
2467                                 for (ty = 0; ty < h; ty++) {
2468                                         int tx;
2469                                         for (tx = 0; tx < w; tx++) {
2470                                                 int i, index = tx+w*ty;
2471
2472                                                 if (tempPoints[index].face_index != -1) {
2473                                                         ed->n_index[final_index[index]] = n_pos;
2474                                                         ed->n_num[final_index[index]] = 0;
2475
2476                                                         for (i=0; i<8; i++) {
2477
2478                                                                 /* Try to find a neighboring pixel in defined direction
2479                                                                 *  If not found, -1 is returned */
2480                                                                 int n_target = dynamicPaint_findNeighbourPixel(tempPoints, dm, uvname, w, h, tx, ty, i);
2481
2482                                                                 if (n_target >= 0) {
2483                                                                         ed->n_target[n_pos] = final_index[n_target];
2484                                                                         ed->n_num[final_index[index]]++;
2485                                                                         n_pos++;
2486                                                                 }
2487                                                                 else if (n_target == ON_MESH_EDGE || n_target == OUT_OF_TEXTURE) {
2488                                                                         ed->flags[final_index[index]] |= ADJ_ON_MESH_EDGE;
2489                                                                 }
2490                                                         }
2491                                                 }
2492                                         }
2493                                 }
2494                         }
2495                 }
2496
2497                 /* Create final surface data without inactive points */
2498                 {
2499                         ImgSeqFormatData *f_data = MEM_callocN(sizeof(struct ImgSeqFormatData), "ImgSeqFormatData");
2500                         if (f_data) {
2501                                 f_data->uv_p = MEM_callocN(active_points*sizeof(struct PaintUVPoint), "PaintUVPoint");
2502                                 f_data->barycentricWeights = MEM_callocN(active_points*aa_samples*sizeof(struct Vec3f), "PaintUVPoint");
2503
2504                                 if (!f_data->uv_p || !f_data->barycentricWeights) error=1;
2505                         }
2506                         else error=1;
2507
2508                         sData->total_points = active_points;
2509                         
2510                         /* in case of allocation error, free everything */
2511                         if (error) {
2512                                 if (f_data) {
2513                                         if (f_data->uv_p) MEM_freeN(f_data->uv_p);
2514                                         if (f_data->barycentricWeights) MEM_freeN(f_data->barycentricWeights);
2515                                         MEM_freeN(f_data);
2516                                 }
2517                         }
2518                         else {
2519                                 int index, cursor = 0;
2520                                 sData->total_points = active_points;
2521                                 sData->format_data = f_data;
2522
2523                                 for (index = 0; index < (w*h); index++) {
2524                                         if (tempPoints[index].face_index != -1) {
2525                                                 memcpy(&f_data->uv_p[cursor], &tempPoints[index], sizeof(PaintUVPoint));
2526                                                 memcpy(&f_data->barycentricWeights[cursor*aa_samples], &tempWeights[index*aa_samples], sizeof(Vec3f)*aa_samples);
2527                                                 cursor++;
2528                                         }
2529                                 }
2530                         }
2531                 }
2532         }
2533         if (error==1) setError(canvas, "Not enough free memory.");
2534
2535         if (faceBB) MEM_freeN(faceBB);
2536         if (tempPoints) MEM_freeN(tempPoints);
2537         if (tempWeights) MEM_freeN(tempWeights);
2538         if (final_index) MEM_freeN(final_index);
2539
2540         /* Init surface type data */
2541         if (!error) {
2542                 dynamicPaint_allocateSurfaceType(surface);
2543
2544 #if 0
2545                 /*  -----------------------------------------------------------------
2546                 *       For debug, output pixel statuses to the color map
2547                 *       -----------------------------------------------------------------*/
2548                 #pragma omp parallel for schedule(static)
2549                 for (index = 0; index < sData->total_points; index++)
2550                 {
2551                         ImgSeqFormatData *f_data = (ImgSeqFormatData*)sData->format_data;
2552                         PaintUVPoint *uvPoint = &((PaintUVPoint*)f_data->uv_p)[index];
2553                         PaintPoint *pPoint = &((PaintPoint*)sData->type_data)[index];
2554                         pPoint->alpha=1.0f;
2555
2556                         /* Every pixel that is assigned as "edge pixel" gets blue color */
2557                         if (uvPoint->neighbour_pixel != -1) pPoint->color[2] = 1.0f;
2558                         /* and every pixel that finally got an polygon gets red color   */
2559                         if (uvPoint->face_index != -1) pPoint->color[0] = 1.0f;
2560                         /* green color shows pixel face index hash      */
2561                         if (uvPoint->face_index != -1) pPoint->color[1] = (float)(uvPoint->face_index % 255)/256.0f;
2562                 }
2563
2564 #endif
2565                 dynamicPaint_setInitialColor(surface);
2566         }
2567
2568         return (error == 0);
2569 }
2570
2571 /*
2572 *       Outputs an image file from uv surface data.
2573 */
2574 void dynamicPaint_outputSurfaceImage(DynamicPaintSurface *surface, char* filename, short output_layer)
2575 {
2576         int index;
2577         ImBuf* ibuf = NULL;
2578         PaintSurfaceData *sData = surface->data;
2579         ImgSeqFormatData *f_data = (ImgSeqFormatData*)sData->format_data;
2580         /* OpenEXR or PNG       */
2581         int format = (surface->image_fileformat & MOD_DPAINT_IMGFORMAT_OPENEXR) ? R_IMF_IMTYPE_OPENEXR : R_IMF_IMTYPE_PNG;
2582         char output_file[FILE_MAX];
2583
2584         if (!sData || !sData->type_data) {setError(surface->canvas, "Image save failed: Invalid surface.");return;}
2585         /* if selected format is openexr, but current build doesnt support one */
2586         #ifndef WITH_OPENEXR
2587         if (format == R_IMF_IMTYPE_OPENEXR) format = R_IMF_IMTYPE_PNG;
2588         #endif
2589         BLI_strncpy(output_file, filename, sizeof(output_file));
2590         BKE_add_image_extension(output_file, format);
2591
2592         /* Validate output file path    */
2593         BLI_path_abs(output_file, G.main->name);
2594         BLI_make_existing_file(output_file);
2595
2596         /* Init image buffer    */
2597         ibuf = IMB_allocImBuf(surface->image_resolution, surface->image_resolution, 32, IB_rectfloat);
2598         if (ibuf == NULL) {setError(surface->canvas, "Image save failed: Not enough free memory.");return;}
2599
2600         #pragma omp parallel for schedule(static)
2601         for (index = 0; index < sData->total_points; index++) {
2602                 int pos=f_data->uv_p[index].pixel_index*4;      /* image buffer position */
2603
2604                 /* Set values of preferred type */
2605                 if (output_layer == 1) {
2606                         /* wetmap */
2607                         if (surface->type == MOD_DPAINT_SURFACE_T_PAINT) {
2608                                 PaintPoint *point = &((PaintPoint*)sData->type_data)[index];
2609                                 float value = (point->wetness > 1.0f) ? 1.0f : point->wetness;
2610
2611                                 ibuf->rect_float[pos]=value;
2612                                 ibuf->rect_float[pos+1]=value;
2613                                 ibuf->rect_float[pos+2]=value;
2614                                 ibuf->rect_float[pos+3]=1.0f;
2615                         }
2616                 }
2617                 else if (output_layer == 0) {
2618                         /* Paintmap */
2619                         if (surface->type == MOD_DPAINT_SURFACE_T_PAINT) {
2620                                 PaintPoint *point = &((PaintPoint*)sData->type_data)[index];
2621
2622                                 /* blend wet and dry layers */
2623                                 blendColors(point->color, point->alpha, point->e_color, point->e_alpha, &ibuf->rect_float[pos]);
2624
2625                                 /* Multiply color by alpha if enabled   */
2626                                 if (surface->flags & MOD_DPAINT_MULALPHA) {
2627                                         ibuf->rect_float[pos]   *= ibuf->rect_float[pos+3];
2628                                         ibuf->rect_float[pos+1] *= ibuf->rect_float[pos+3];
2629                                         ibuf->rect_float[pos+2] *= ibuf->rect_float[pos+3];
2630                                 }
2631                         }
2632                         /* displace */
2633                         else if (surface->type == MOD_DPAINT_SURFACE_T_DISPLACE) {
2634                                 float depth = ((float*)sData->type_data)[index];
2635                                 if (surface->depth_clamp)
2636                                         depth /= surface->depth_clamp;
2637
2638                                 if (surface->disp_type == MOD_DPAINT_DISP_DISPLACE) {
2639                                         depth = (0.5f - depth/2.0f);
2640                                 }
2641
2642                                 CLAMP(depth, 0.0f, 1.0f);
2643
2644                                 ibuf->rect_float[pos]=depth;
2645                                 ibuf->rect_float[pos+1]=depth;
2646                                 ibuf->rect_float[pos+2]=depth;
2647                                 ibuf->rect_float[pos+3]=1.0f;
2648                         }
2649                         /* waves */
2650                         else if (surface->type == MOD_DPAINT_SURFACE_T_WAVE) {
2651                                 PaintWavePoint *wPoint = &((PaintWavePoint*)sData->type_data)[index];
2652                                 float depth = wPoint->height;
2653                                 if (surface->depth_clamp)
2654                                                 depth /= surface->depth_clamp;
2655                                 depth = (0.5f + depth/2.0f);
2656                                 CLAMP(depth, 0.0f, 1.0f);
2657
2658                                 ibuf->rect_float[pos]=depth;
2659                                 ibuf->rect_float[pos+1]=depth;
2660                                 ibuf->rect_float[pos+2]=depth;
2661                                 ibuf->rect_float[pos+3]=1.0f;
2662                         }
2663                 }
2664         }
2665
2666         /* Set output format, png in case exr isn't supported */
2667         ibuf->ftype= PNG|95;
2668 #ifdef WITH_OPENEXR
2669         if (format == R_IMF_IMTYPE_OPENEXR) {   /* OpenEXR 32-bit float */
2670                 ibuf->ftype = OPENEXR | OPENEXR_COMPRESS;
2671         }
2672 #endif
2673
2674         /* Save image */
2675         IMB_saveiff(ibuf, output_file, IB_rectfloat);
2676         IMB_freeImBuf(ibuf);
2677 }
2678
2679
2680 /***************************** Material / Texture Sampling ******************************/
2681
2682 /* stores a copy of required materials to allow doing adjustments
2683 *  without interfering the render/preview */
2684 typedef struct BrushMaterials {
2685         Material *mat;
2686         Material **ob_mats;
2687         int tot;
2688 } BrushMaterials;
2689
2690 /* Initialize materials for brush object:
2691 *  Calculates inverse matrices for linked objects, updates
2692 *  volume caches etc. */
2693 static void dynamicPaint_updateBrushMaterials(Object *brushOb, Material *ui_mat, Scene *scene, BrushMaterials *bMats)
2694 {
2695         /* Calculate inverse transformation matrix
2696         *  for this object */
2697         invert_m4_m4(brushOb->imat, brushOb->obmat);
2698         copy_m4_m4(brushOb->imat_ren, brushOb->imat);
2699
2700         /* Now process every material linked to this brush object */
2701         if ((ui_mat == NULL) && brushOb->mat && brushOb->totcol) {
2702                 int i, tot=(*give_totcolp(brushOb));
2703
2704                 /* allocate material pointer array */
2705                 if (tot) {
2706                         bMats->ob_mats = MEM_callocN(sizeof(Material*)*(tot), "BrushMaterials");
2707                         for (i=0; i<tot; i++) {
2708                                 bMats->ob_mats[i] = RE_init_sample_material(give_current_material(brushOb, (i+1)), scene);
2709                         }
2710                 }
2711                 bMats->tot = tot;
2712         }
2713         else {
2714                 bMats->mat = RE_init_sample_material(ui_mat, scene);
2715         }
2716 }
2717
2718 /* free all data allocated by dynamicPaint_updateBrushMaterials() */
2719 static void dynamicPaint_freeBrushMaterials(BrushMaterials *bMats)
2720 {
2721         /* Now process every material linked to this brush object */
2722         if (bMats->ob_mats) {
2723                 int i;
2724                 for (i=0; i<bMats->tot; i++) {
2725                         RE_free_sample_material(bMats->ob_mats[i]);
2726                 }
2727                 MEM_freeN(bMats->ob_mats);
2728         }
2729         else if (bMats->mat) {
2730                 RE_free_sample_material(bMats->mat);
2731         }
2732 }
2733
2734 /*
2735 *       Get material diffuse color and alpha (including linked textures) in given coordinates
2736 */
2737 void dynamicPaint_doMaterialTex(BrushMaterials *bMats, float color[3], float *alpha, Object *brushOb, const float volume_co[3], const float surface_co[3], int faceIndex, short isQuad, DerivedMesh *orcoDm)
2738 {
2739         Material *mat = bMats->mat;
2740         MFace *mface = orcoDm->getTessFaceArray(orcoDm);
2741
2742         /* If no material defined, use the one assigned to the mesh face */
2743         if (mat == NULL) {
2744                 if (bMats->ob_mats) {
2745                         int mat_nr = mface[faceIndex].mat_nr;
2746                         if (mat_nr >= (*give_totcolp(brushOb))) return;
2747                         mat = bMats->ob_mats[mat_nr];
2748                         if (mat == NULL) return;        /* No material assigned */
2749                 }
2750                 else return;
2751         }
2752
2753         RE_sample_material_color(mat, color, alpha, volume_co, surface_co, faceIndex, isQuad, orcoDm, brushOb);
2754 }
2755
2756
2757 /***************************** Ray / Nearest Point Utils ******************************/
2758
2759
2760 /*  A modified callback to bvh tree raycast. The tree must bust have been built using bvhtree_from_mesh_faces.
2761 *   userdata must be a BVHMeshCallbackUserdata built from the same mesh as the tree.
2762 *  
2763 *       To optimize brush detection speed this doesn't calculate hit coordinates or normal.
2764 *       If ray hit the second half of a quad, no[0] is set to 1.0f.
2765 */
2766 static void mesh_faces_spherecast_dp(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit)
2767 {
2768         const BVHTreeFromMesh *data = (BVHTreeFromMesh*) userdata;
2769         MVert *vert     = data->vert;
2770         MFace *face = data->face + index;
2771         short quad = 0;
2772
2773         float *t0, *t1, *t2, *t3;
2774         t0 = vert[ face->v1 ].co;
2775         t1 = vert[ face->v2 ].co;
2776         t2 = vert[ face->v3 ].co;
2777         t3 = face->v4 ? vert[ face->v4].co : NULL;
2778
2779         do
2780         {       
2781                 float dist = bvhtree_ray_tri_intersection(ray, hit->dist, t0, t1, t2);
2782
2783                 if (dist >= 0 && dist < hit->dist) {
2784                         hit->index = index;
2785                         hit->dist = dist;
2786                         hit->no[0] = (quad) ? 1.0f : 0.0f;
2787                 }
2788
2789                 t1 = t2;
2790                 t2 = t3;
2791                 t3 = NULL;
2792                 quad = 1;
2793
2794         } while (t2);
2795 }
2796
2797 /* A modified callback to bvh tree nearest point. The tree must bust have been built using bvhtree_from_mesh_faces.
2798 *  userdata must be a BVHMeshCallbackUserdata built from the same mesh as the tree.
2799 *  
2800 *       To optimize brush detection speed this doesn't calculate hit normal.
2801 *       If ray hit the second half&nbs