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