Merge from trunk
[blender.git] / source / blender / blenkernel / intern / shrinkwrap.c
1 /**
2  * shrinkwrap.c
3  *
4  * ***** BEGIN GPL LICENSE BLOCK *****
5  *
6  * This program is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU General Public License
8  * as published by the Free Software Foundation; either version 2
9  * of the License, or (at your option) any later version.
10  *
11  * This program is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, write to the Free Software Foundation,
18  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
19  *
20  * The Original Code is Copyright (C) Blender Foundation.
21  * All rights reserved.
22  *
23  * The Original Code is: all of this file.
24  *
25  * Contributor(s): AndrĂ© Pinto
26  *
27  * ***** END GPL LICENSE BLOCK *****
28  */
29 #include <string.h>
30 #include <float.h>
31 #include <math.h>
32 #include <stdio.h>
33 #include <time.h>
34 #include <assert.h>
35 //TODO: its late and I don't fill like adding ifs() printfs (I'll remove them on end)
36
37 #include "DNA_object_types.h"
38 #include "DNA_modifier_types.h"
39 #include "DNA_meshdata_types.h"
40
41 #include "BKE_shrinkwrap.h"
42 #include "BKE_DerivedMesh.h"
43 #include "BKE_utildefines.h"
44 #include "BKE_deform.h"
45 #include "BKE_cdderivedmesh.h"
46 #include "BKE_global.h"
47
48 #include "BLI_arithb.h"
49 #include "BLI_kdtree.h"
50
51 #include "RE_raytrace.h"
52 #include "MEM_guardedalloc.h"
53
54
55 /* Util macros */
56 #define TO_STR(a)       #a
57 #define JOIN(a,b)       a##b
58
59 #define OUT_OF_MEMORY() ((void)printf("Shrinkwrap: Out of memory\n"))
60
61 /* Benchmark macros */
62 #if 1
63
64 #define BENCH(a)        \
65         do {                    \
66                 clock_t _clock_init = clock();  \
67                 (a);                                                    \
68                 printf("%s: %fms\n", #a, (float)(clock()-_clock_init)*1000/CLOCKS_PER_SEC);     \
69         } while(0)
70
71 #define BENCH_VAR(name)         clock_t JOIN(_bench_step,name) = 0, JOIN(_bench_total,name) = 0
72 #define BENCH_BEGIN(name)       JOIN(_bench_step, name) = clock()
73 #define BENCH_END(name)         JOIN(_bench_total,name) += clock() - JOIN(_bench_step,name)
74 #define BENCH_RESET(name)       JOIN(_bench_total, name) = 0
75 #define BENCH_REPORT(name)      printf("%s: %fms\n", TO_STR(name), JOIN(_bench_total,name)*1000.0f/CLOCKS_PER_SEC)
76
77 #else
78
79 #define BENCH(a)        (a)
80 #define BENCH_VAR(name)
81 #define BENCH_BEGIN(name)
82 #define BENCH_END(name)
83 #define BENCH_RESET(name)
84 #define BENCH_REPORT(name)
85
86 #endif
87
88 typedef void ( *Shrinkwrap_ForeachVertexCallback) (DerivedMesh *target, float *co, float *normal);
89
90
91 static void normal_short2float(const short *ns, float *nf)
92 {
93         nf[0] = ns[0] / 32767.0f;
94         nf[1] = ns[1] / 32767.0f;
95         nf[2] = ns[2] / 32767.0f;
96 }
97
98 static float vertexgroup_get_weight(MDeformVert *dvert, int index, int vgroup)
99 {
100         if(dvert && vgroup >= 0)
101         {
102                 int j;
103                 for(j = 0; j < dvert[index].totweight; j++)
104                         if(dvert[index].dw[j].def_nr == vgroup)
105                                 return dvert[index].dw[j].weight;
106         }
107         return 1.0;
108 }
109
110 /*
111  * Raytree from mesh
112  */
113 static MVert *raytree_from_mesh_verts = NULL;
114 static MFace *raytree_from_mesh_faces = NULL;
115 //static float raytree_from_mesh_start[3] = { 0.0f, 0.0f, 0.0f }; 
116 static int raytree_check_always(Isect *is, int ob, RayFace *face)
117 {
118         return TRUE;
119 }
120
121 static void raytree_from_mesh_get_coords(RayFace *face, float **v1, float **v2, float **v3, float **v4)
122 {
123         MFace *mface= raytree_from_mesh_faces + (int)face/2 - 1 ;
124
125         if(face == (RayFace*)(-1))
126         {
127                 *v1 = NULL; //raytree_from_mesh_start;
128                 *v2 = NULL; //raytree_from_mesh_start;
129                 *v3 = NULL; //raytree_from_mesh_start;
130                 *v4 = NULL;
131                 return;
132         }
133
134         //Nasty quad splitting
135         if(((int)face) & 1)     //we want the 2 triangle of the quad
136         {
137                 assert(mface->v4);
138                 *v1= raytree_from_mesh_verts[mface->v1].co;
139                 *v2= raytree_from_mesh_verts[mface->v4].co;
140                 *v3= raytree_from_mesh_verts[mface->v3].co;
141                 *v4= NULL;
142         }
143         else
144         {
145                 *v1= raytree_from_mesh_verts[mface->v1].co;
146                 *v2= raytree_from_mesh_verts[mface->v2].co;
147                 *v3= raytree_from_mesh_verts[mface->v3].co;
148                 *v4= NULL;
149         }
150 }
151
152 /*
153  * Creates a raytree from the given mesh
154  * No copy of the mesh is done, so it must exist and remain
155  * imutable as long the tree is intended to be used
156  *
157  * No more than 1 raytree can exist.. since this code uses a static variable
158  * to pass data to raytree_from_mesh_get_coords
159  */
160 static RayTree* raytree_create_from_mesh(DerivedMesh *mesh)
161 {
162         int i;
163         float min[3], max[3];
164
165         RayTree*tree= NULL;
166
167         int numFaces= mesh->getNumFaces(mesh);
168         MFace *face = mesh->getFaceDataArray(mesh, CD_MFACE);
169         int numVerts= mesh->getNumVerts(mesh);
170
171         //Initialize static vars
172         raytree_from_mesh_verts = mesh->getVertDataArray(mesh, CD_MVERT);
173         raytree_from_mesh_faces = face;
174
175
176         //calculate bounding box
177         INIT_MINMAX(min, max);
178
179         for(i=0; i<numVerts; i++)
180                 DO_MINMAX(raytree_from_mesh_verts[i].co, min, max);
181         
182         tree = RE_ray_tree_create(64, numFaces, min, max, raytree_from_mesh_get_coords, raytree_check_always, NULL, NULL);
183         if(tree == NULL)
184                 return NULL;
185
186         //Add faces to the RayTree (RayTree uses face=0, with some special value to setup things)
187         for(i=1; i<=numFaces; i++)
188         {
189                 RE_ray_tree_add_face(tree, 0, (RayFace*)(i*2) );
190
191                 //Theres some nasty thing with non-coplanar quads (that I can't find the issue)
192                 //so we split quads (an odd numbered face represents the second triangle of the quad)
193                 if(face[i-1].v4)
194                         RE_ray_tree_add_face(tree, 0, (RayFace*)(i*2+1));
195         }
196
197         RE_ray_tree_done(tree);
198
199         return tree;
200 }
201
202 static void free_raytree_from_mesh(RayTree *tree)
203 {
204         raytree_from_mesh_verts = NULL;
205         RE_ray_tree_free(tree);
206 }
207
208 /*
209  * Cast a ray on the specified direction
210  * Returns the distance the ray must travel until intersect something
211  * Returns FLT_MAX in case of nothing intersection
212  */
213 static float raytree_cast_ray(RayTree *tree, const float *coord, const float *direction)
214 {
215         Isect isec = {};
216
217         //Setup intersection
218         isec.mode               = RE_RAY_MIRROR; //We want closest intersection
219         isec.lay                = -1;
220         isec.face_last  = NULL;
221         isec.faceorig   = (RayFace*)(-1);
222         isec.labda              = 1e10f;
223
224         VECCOPY(isec.start, coord);
225         VECCOPY(isec.vec, direction);
226         VECADDFAC(isec.end, isec.start, isec.vec, isec.labda);
227
228         if(!RE_ray_tree_intersect(tree, &isec))
229                 return FLT_MAX;
230
231         isec.labda = ABS(isec.labda);
232         VECADDFAC(isec.end, isec.start, isec.vec, isec.labda);
233         return VecLenf((float*)coord, (float*)isec.end);
234 }
235
236 /*
237  * This calculates the distance (in dir units) that the ray must travel to intersect plane
238  * It can return negative values
239  *
240  * TODO theres probably something like this on blender code
241  *
242  * Returns FLT_MIN in parallel case
243  */
244 static float ray_intersect_plane(const float *point, const float *dir, const float *plane_point, const float *plane_normal)
245 {
246                 float pp[3];
247                 float a, pp_dist;
248
249                 a = INPR(dir, plane_normal);
250
251                 if(fabs(a) < 1e-5f) return FLT_MIN;
252
253                 VECSUB(pp, point, plane_point);
254                 pp_dist = INPR(pp, plane_normal);
255
256                 return -pp_dist/a;
257 }
258
259 /*
260  * This calculates the distance from point to the plane
261  * Distance is negative if point is on the back side of plane
262  */
263 static float point_plane_distance(const float *point, const float *plane_point, const float *plane_normal)
264 {
265         float pp[3];
266         VECSUB(pp, point, plane_point);
267         return INPR(pp, plane_normal);
268 }
269 static float choose_nearest(const float v0[2], const float v1[2], const float point[2], float closest[2])
270 {
271         float d[2][2], sdist[2];
272         VECSUB2D(d[0], v0, point);
273         VECSUB2D(d[1], v1, point);
274
275         sdist[0] = d[0][0]*d[0][0] + d[0][1]*d[0][1];
276         sdist[1] = d[1][0]*d[1][0] + d[1][1]*d[1][1];
277
278         if(sdist[0] < sdist[1])
279         {
280                 if(closest)
281                         VECCOPY2D(closest, v0);
282                 return sdist[0];
283         }
284         else
285         {
286                 if(closest)
287                         VECCOPY2D(closest, v1);
288                 return sdist[1];
289         }
290 }
291 /*
292  * calculates the closest point between point-tri (2D)
293  * returns that tri must be right-handed
294  * Returns square distance
295  */
296 static float closest_point_in_tri2D(const float point[2], const float tri[3][2], float closest[2])
297 {
298         float edge_di[2];
299         float v_point[2];
300         float proj[2];                                  //point projected over edge-dir, edge-normal (witouth normalized edge)
301         const float *v0 = tri[2], *v1;
302         float edge_slen, d;                             //edge squared length
303         int i;
304         const float *nearest_vertex = NULL;
305
306
307         //for each edge
308         for(i=0, v0=tri[2], v1=tri[0]; i < 3; v0=tri[i++], v1=tri[i])
309         {
310                 VECSUB2D(edge_di,    v1, v0);
311                 VECSUB2D(v_point, point, v0);
312
313                 proj[1] =  v_point[0]*edge_di[1] - v_point[1]*edge_di[0];       //dot product with edge normal
314
315                 //point inside this edge
316                 if(proj[1] < 0)
317                         continue;
318
319                 proj[0] = v_point[0]*edge_di[0] + v_point[1]*edge_di[1];
320
321                 //closest to this edge is v0
322                 if(proj[0] < 0)
323                 {
324                         if(nearest_vertex == NULL || nearest_vertex == v0)
325                                 nearest_vertex = v0;
326                         else
327                         {
328                                 //choose nearest
329                                 return choose_nearest(nearest_vertex, v0, point, closest);
330                         }
331                         i++;    //We can skip next edge
332                         continue;
333                 }
334
335                 edge_slen = edge_di[0]*edge_di[0] + edge_di[1]*edge_di[1];      //squared edge len
336                 //closest to this edge is v1
337                 if(proj[0] > edge_slen)
338                 {
339                         if(nearest_vertex == NULL || nearest_vertex == v1)
340                                 nearest_vertex = v1;
341                         else
342                         {
343                                 return choose_nearest(nearest_vertex, v1, point, closest);
344                         }
345                         continue;
346                 }
347
348                 //nearest is on this edge
349                 d= proj[1] / edge_slen;
350                 closest[0] = point[0] - edge_di[1] * d;
351                 closest[1] = point[1] + edge_di[0] * d;
352
353                 return proj[1]*proj[1]/edge_slen;
354         }
355
356         if(nearest_vertex)
357         {
358                 VECSUB2D(v_point, nearest_vertex, point);
359                 VECCOPY2D(closest, nearest_vertex);
360                 return v_point[0]*v_point[0] + v_point[1]*v_point[1];
361         }
362         else
363         {
364                 VECCOPY(closest, point);        //point is already inside
365                 return 0.0f;
366         }
367 }
368
369 /*
370  * Returns the square of the minimum distance between the point and a triangle surface
371  * If nearest is not NULL the nearest surface point is written on it
372  */
373 static float nearest_point_in_tri_surface(const float *point, const float *v0, const float *v1, const float *v2, float *nearest)
374 {
375         //Lets solve the 2D problem (closest point-tri)
376         float normal_dist, plane_sdist, plane_offset;
377         float du[3], dv[3], dw[3];      //orthogonal axis (du=(v0->v1), dw=plane normal)
378
379         float p_2d[2], tri_2d[3][2], nearest_2d[2];
380
381         CalcNormFloat((float*)v0, (float*)v1, (float*)v2, dw);
382
383         //point-plane distance and calculate axis
384         normal_dist = point_plane_distance(point, v0, dw);
385
386         VECSUB(du, v1, v0);
387         Normalize(du);
388         Crossf(dv, dw, du);
389         plane_offset = INPR(v0, dw);
390
391         //project stuff to 2d
392         tri_2d[0][0] = INPR(du, v0);
393         tri_2d[0][1] = INPR(dv, v0);
394
395         tri_2d[1][0] = INPR(du, v1);
396         tri_2d[1][1] = INPR(dv, v1);
397
398         tri_2d[2][0] = INPR(du, v2);
399         tri_2d[2][1] = INPR(dv, v2);
400
401         p_2d[0] = INPR(du, point);
402         p_2d[1] = INPR(dv, point);
403
404         //we always have a right-handed tri
405         //this should always happen because of the way normal is calculated
406         plane_sdist = closest_point_in_tri2D(p_2d, tri_2d, nearest_2d);
407
408         //project back to 3d
409         if(nearest)
410         {
411                 nearest[0] = du[0]*nearest_2d[0] + dv[0] * nearest_2d[1] + dw[0] * plane_offset;
412                 nearest[1] = du[1]*nearest_2d[0] + dv[1] * nearest_2d[1] + dw[1] * plane_offset;
413                 nearest[2] = du[2]*nearest_2d[0] + dv[2] * nearest_2d[1] + dw[2] * plane_offset;
414         }
415
416         return sasqrt(plane_sdist + normal_dist*normal_dist);
417 }
418
419
420
421 /*
422  * Shrink to nearest surface point on target mesh
423  */
424 static void bruteforce_shrinkwrap_calc_nearest_surface_point(DerivedMesh *target, float *co, float *unused)
425 {
426         float minDist = FLT_MAX;
427         float orig_co[3];
428
429         int i;
430         int     numFaces = target->getNumFaces(target);
431         MVert *vert = target->getVertDataArray(target, CD_MVERT);
432         MFace *face = target->getFaceDataArray(target, CD_MFACE);
433
434         VECCOPY(orig_co, co);   
435
436         for (i = 0; i < numFaces; i++)
437         {
438                 float *v0, *v1, *v2, *v3;
439
440                 v0 = vert[ face[i].v1 ].co;
441                 v1 = vert[ face[i].v2 ].co;
442                 v2 = vert[ face[i].v3 ].co;
443                 v3 = face[i].v4 ? vert[ face[i].v4 ].co : 0;
444
445                 while(v2)
446                 {
447                         float dist;
448                         float tmp[3];
449
450                         dist = nearest_point_in_tri_surface(orig_co, v0, v1, v2, tmp);
451
452                         if(dist < minDist)
453                         {
454                                 minDist = dist;
455                                 VECCOPY(co, tmp);
456                         }
457
458                         v1 = v2;
459                         v2 = v3;
460                         v3 = 0;
461                 }
462         }
463 }
464
465 /*
466  * Projects the vertex on the normal direction over the target mesh
467  */
468 static void bruteforce_shrinkwrap_calc_normal_projection(DerivedMesh *target, float *co, float *vnormal)
469 {
470         //TODO: this should use raycast code probably existent in blender
471         float minDist = FLT_MAX;
472         float orig_co[3];
473
474         int i;
475         int     numFaces = target->getNumFaces(target);
476         MVert *vert = target->getVertDataArray(target, CD_MVERT);
477         MFace *face = target->getFaceDataArray(target, CD_MFACE);
478
479         VECCOPY(orig_co, co);
480
481         for (i = 0; i < numFaces; i++)
482         {
483                 float *v0, *v1, *v2, *v3;
484
485                 v0 = vert[ face[i].v1 ].co;
486                 v1 = vert[ face[i].v2 ].co;
487                 v2 = vert[ face[i].v3 ].co;
488                 v3 = face[i].v4 ? vert[ face[i].v4 ].co : 0;
489
490                 while(v2)
491                 {
492                         float dist;
493                         float pnormal[3];
494
495                         CalcNormFloat(v0, v1, v2, pnormal);
496                         dist =  ray_intersect_plane(orig_co, vnormal, v0, pnormal);
497
498                         if(fabs(dist) < minDist)
499                         {
500                                 float tmp[3], nearest[3];
501                                 VECADDFAC(tmp, orig_co, vnormal, dist);
502
503                                 if( fabs(nearest_point_in_tri_surface(tmp, v0, v1, v2, nearest)) < 0.0001)
504                                 {
505                                         minDist = fabs(dist);
506                                         VECCOPY(co, nearest);
507                                 }
508                         }
509                         v1 = v2;
510                         v2 = v3;
511                         v3 = 0;
512                 }
513         }
514 }
515
516 /*
517  * Shrink to nearest vertex on target mesh
518  */
519 static void bruteforce_shrinkwrap_calc_nearest_vertex(DerivedMesh *target, float *co, float *unused)
520 {
521         float minDist = FLT_MAX;
522         float orig_co[3];
523
524         int i;
525         int     numVerts = target->getNumVerts(target);
526         MVert *vert = target->getVertDataArray(target, CD_MVERT);
527
528         VECCOPY(orig_co, co);
529
530         for (i = 0; i < numVerts; i++)
531         {
532                 float diff[3], sdist;
533                 VECSUB(diff, orig_co, vert[i].co);
534                 sdist = INPR(diff, diff);
535                 
536                 if(sdist < minDist)
537                 {
538                         minDist = sdist;
539                         VECCOPY(co, vert[i].co);
540                 }
541         }
542 }
543
544
545 static void shrinkwrap_calc_foreach_vertex(ShrinkwrapCalcData *calc, Shrinkwrap_ForeachVertexCallback callback)
546 {
547         int i;
548         int vgroup              = get_named_vertexgroup_num(calc->ob, calc->smd->vgroup_name);
549         int     numVerts        = 0;
550
551         MDeformVert *dvert = NULL;
552         MVert           *vert  = NULL;
553
554         numVerts = calc->final->getNumVerts(calc->final);
555         dvert = calc->final->getVertDataArray(calc->final, CD_MDEFORMVERT);
556         vert  = calc->final->getVertDataArray(calc->final, CD_MVERT);
557
558         //Shrink (calculate each vertex final position)
559         for(i = 0; i<numVerts; i++)
560         {
561                 float weight = vertexgroup_get_weight(dvert, i, vgroup);
562
563                 float orig[3], final[3]; //Coords relative to target
564                 float normal[3];
565                 float dist;
566
567                 if(weight == 0.0f) continue;    //Skip vertexs where we have no influence
568
569                 VecMat4MulVecfl(orig, calc->local2target, vert[i].co);
570                 VECCOPY(final, orig);
571
572                 //We also need to apply the rotation to normal
573                 if(calc->smd->shrinkType == MOD_SHRINKWRAP_NORMAL)
574                 {
575                         normal_short2float(vert[i].no, normal);
576                         Mat4Mul3Vecfl(calc->local2target, normal);
577                         Normalize(normal);      //Watch out for scaling (TODO: do we really needed a unit-len normal?)
578                 }
579                 (callback)(calc->target, final, normal);
580
581                 VecMat4MulVecfl(final, calc->target2local, final);
582
583                 dist = VecLenf(vert[i].co, final);
584                 if(dist > 1e-5) weight *= (dist - calc->keptDist)/dist;
585                 VecLerpf(vert[i].co, vert[i].co, final, weight);        //linear interpolation
586         }
587 }
588
589
590 /*
591  * This function removes Unused faces, vertexs and edges from calc->target
592  *
593  * This function may modify calc->final. As so no data retrieved from
594  * it before the call to this function  can be considered valid
595  * In case it creates a new DerivedMesh, the old calc->final is freed
596  */
597 //TODO memory checks on allocs
598 static void shrinkwrap_removeUnused(ShrinkwrapCalcData *calc)
599 {
600         int i, t;
601
602         DerivedMesh *old = calc->final, *new = NULL;
603         MFace *new_face = NULL;
604         MVert *new_vert  = NULL;
605
606         int numVerts= old->getNumVerts(old);
607         MVert *vert = old->getVertDataArray(old, CD_MVERT);
608
609         int     numFaces= old->getNumFaces(old);
610         MFace *face = old->getFaceDataArray(old, CD_MFACE);
611
612         BitSet moved_verts = calc->moved;
613
614         //Arrays to translate to new vertexs indexs
615         int *vert_index = (int*)MEM_callocN(sizeof(int)*(numVerts), "shrinkwrap used verts");
616         BitSet used_faces = bitset_new(numFaces, "shrinkwrap used faces");
617         int numUsedFaces = 0;
618
619         //calc real number of faces, and vertices
620         //Count used faces
621         for(i=0; i<numFaces; i++)
622         {
623                 char res = bitset_get(moved_verts, face[i].v1)
624                                  | bitset_get(moved_verts, face[i].v2)
625                                  | bitset_get(moved_verts, face[i].v3)
626                                  | (face[i].v4 ? bitset_get(moved_verts, face[i].v4) : 0);
627
628                 if(res)
629                 {
630                         bitset_set(used_faces, i);      //Mark face to maintain
631                         numUsedFaces++;
632
633                         vert_index[face[i].v1] = 1;
634                         vert_index[face[i].v2] = 1;
635                         vert_index[face[i].v3] = 1;
636                         if(face[i].v4) vert_index[face[i].v4] = 1;
637                 }
638         }
639
640         //DP: Accumulate vertexs indexs.. (will calculate the new vertex index with a 1 offset)
641         for(i=1; i<numVerts; i++)
642                 vert_index[i] += vert_index[i-1];
643                 
644         
645         //Start creating the clean mesh
646         new = CDDM_new(vert_index[numVerts-1], 0, numUsedFaces);
647
648         //Copy vertexs (unused are are removed)
649         new_vert  = new->getVertDataArray(new, CD_MVERT);
650         for(i=0, t=0; i<numVerts; i++)
651         {
652                 if(vert_index[i] != t)
653                 {
654                         t = vert_index[i];
655                         memcpy(new_vert++, vert+i, sizeof(MVert));
656                 }
657         }
658
659         //Copy faces
660         new_face = new->getFaceDataArray(new, CD_MFACE);
661         for(i=0, t=0; i<numFaces; i++)
662         {
663                 if(bitset_get(used_faces, i))
664                 {
665                         memcpy(new_face, face+i, sizeof(MFace));
666                         //update vertices indexs
667                         new_face->v1 = vert_index[new_face->v1]-1;
668                         new_face->v2 = vert_index[new_face->v2]-1;
669                         new_face->v3 = vert_index[new_face->v3]-1;
670                         if(new_face->v4)
671                         {
672                                 new_face->v4 = vert_index[new_face->v4]-1;
673
674                                 //Ups translated vertex ended on 0 .. TODO fix this
675                                 if(new_face->v4 == 0)
676                                 {
677                                 }
678                         }                       
679                         new_face++;
680                 }
681         }
682
683         //Free memory
684         bitset_free(used_faces);
685         MEM_freeN(vert_index);
686         old->release(old);
687
688         //Update edges
689         CDDM_calc_edges(new);
690         CDDM_calc_normals(new);
691
692         calc->final = new;
693 }
694
695 /* Main shrinkwrap function */
696 DerivedMesh *shrinkwrapModifier_do(ShrinkwrapModifierData *smd, Object *ob, DerivedMesh *dm, int useRenderParams, int isFinalCalc)
697 {
698
699         ShrinkwrapCalcData calc = {};
700
701
702         //Init Shrinkwrap calc data
703         calc.smd = smd;
704
705         calc.ob = ob;
706         calc.original = dm;
707         calc.final = CDDM_copy(calc.original);
708
709         if(!calc.final)
710         {
711                 OUT_OF_MEMORY();
712                 return dm;
713         }
714
715         if(smd->target)
716         {
717                 calc.target = (DerivedMesh *)smd->target->derivedFinal;
718
719                 if(!calc.target)
720                 {
721                         printf("Target derived mesh is null! :S\n");
722                 }
723
724                 //TODO should we reduce the number of matrix mults? by choosing applying matrixs to target or to derived mesh?
725                 //Calculate matrixs for local <-> target
726                 Mat4Invert (smd->target->imat, smd->target->obmat);     //inverse is outdated
727                 Mat4MulSerie(calc.local2target, smd->target->imat, ob->obmat, 0, 0, 0, 0, 0, 0);
728                 Mat4Invert(calc.target2local, calc.local2target);
729         
730                 calc.keptDist = smd->keptDist;  //TODO: smd->keptDist is in global units.. must change to local
731         }
732
733         //Projecting target defined - lets work!
734         if(calc.target)
735         {
736                 printf("Shrinkwrap (%s)%d over (%s)%d\n",
737                         calc.ob->id.name,                       calc.final->getNumVerts(calc.final),
738                         calc.smd->target->id.name,      calc.target->getNumVerts(calc.target)
739                 );
740
741                 switch(smd->shrinkType)
742                 {
743                         case MOD_SHRINKWRAP_NEAREST_SURFACE:
744                                 BENCH(shrinkwrap_calc_foreach_vertex(&calc, bruteforce_shrinkwrap_calc_nearest_surface_point));
745                         break;
746
747                         case MOD_SHRINKWRAP_NORMAL:
748                                 BENCH(shrinkwrap_calc_normal_projection(&calc));
749 //                              BENCH(shrinkwrap_calc_foreach_vertex(&calc, bruteforce_shrinkwrap_calc_normal_projection));
750                         break;
751
752                         case MOD_SHRINKWRAP_NEAREST_VERTEX:
753                                 BENCH(shrinkwrap_calc_nearest_vertex(&calc));
754 //                              BENCH(shrinkwrap_calc_foreach_vertex(&calc, bruteforce_shrinkwrap_calc_nearest_vertex));
755                         break;
756                 }
757
758         }
759
760         //Destroy faces, edges and stuff
761         if(calc.moved)
762         {
763                 shrinkwrap_removeUnused(&calc);
764                 bitset_free(calc.moved);
765         }
766
767         CDDM_calc_normals(calc.final);  
768
769         return calc.final;
770 }
771
772
773 /*
774  * Shrinkwrap to the nearest vertex
775  *
776  * it builds a kdtree of vertexs we can attach to and then
777  * for each vertex on performs a nearest vertex search on the tree
778  */
779 void shrinkwrap_calc_nearest_vertex(ShrinkwrapCalcData *calc)
780 {
781         int i;
782         int vgroup              = get_named_vertexgroup_num(calc->ob, calc->smd->vgroup_name);
783
784         KDTree* target = NULL;
785         KDTreeNearest nearest;
786         float tmp_co[3];
787
788         BENCH_VAR(build);
789         BENCH_VAR(query);
790
791         int     numVerts;
792         MVert *vert = NULL;
793         MDeformVert *dvert = NULL;
794
795         //Generate kd-tree with target vertexs
796         BENCH_BEGIN(build);
797
798         target = BLI_kdtree_new(calc->target->getNumVerts(calc->target));
799         if(target == NULL) return OUT_OF_MEMORY();
800
801         numVerts= calc->target->getNumVerts(calc->target);
802         vert    = calc->target->getVertDataArray(calc->target, CD_MVERT);       
803
804
805         for( ;numVerts--; vert++)
806                 BLI_kdtree_insert(target, 0, vert->co, NULL);
807
808         BLI_kdtree_balance(target);
809
810         BENCH_END(build);
811
812
813         //Find the nearest vertex 
814         numVerts= calc->final->getNumVerts(calc->final);
815         vert    = calc->final->getVertDataArray(calc->final, CD_MVERT); 
816         dvert   = calc->final->getVertDataArray(calc->final, CD_MDEFORMVERT);
817
818         for(i=0; i<numVerts; i++)
819         {
820                 int t;
821                 float weight = vertexgroup_get_weight(dvert, i, vgroup);
822                 if(weight == 0.0f) continue;
823
824                 VecMat4MulVecfl(tmp_co, calc->local2target, vert[i].co);
825
826                 BENCH_BEGIN(query);
827                 t = BLI_kdtree_find_nearest(target, tmp_co, 0, &nearest);
828                 BENCH_END(query);
829
830                 if(t != -1)
831                 {
832                         float dist;
833
834                         VecMat4MulVecfl(nearest.co, calc->target2local, nearest.co);
835                         dist = VecLenf(vert[i].co, tmp_co);
836                         if(dist > 1e-5) weight *= (dist - calc->keptDist)/dist;
837                         VecLerpf(vert[i].co, vert[i].co, nearest.co, weight);   //linear interpolation
838                 }
839         }
840
841         BENCH_BEGIN(build);
842         BLI_kdtree_free(target);
843         BENCH_END(build);
844
845
846         BENCH_REPORT(build);
847         BENCH_REPORT(query);
848 }
849
850 /*
851  * Shrinkwrap projecting vertexs allong their normals over the target
852  *
853  * it builds a RayTree from the target mesh and then performs a
854  * raycast for each vertex (ray direction = normal)
855  */
856 void shrinkwrap_calc_normal_projection(ShrinkwrapCalcData *calc)
857 {
858         int i;
859         int vgroup              = get_named_vertexgroup_num(calc->ob, calc->smd->vgroup_name);
860         char use_normal = calc->smd->shrinkOpts;
861         RayTree *target = NULL;
862
863         int     numVerts;
864         MVert *vert = NULL;
865         MDeformVert *dvert = NULL;
866         float tmp_co[3], tmp_no[3];
867
868         if( (use_normal & (MOD_SHRINKWRAP_ALLOW_INVERTED_NORMAL | MOD_SHRINKWRAP_ALLOW_DEFAULT_NORMAL)) == 0)
869                 return; //Nothing todo
870
871         //setup raytracing
872         target = raytree_create_from_mesh(calc->target);
873         if(target == NULL) return OUT_OF_MEMORY();
874
875
876
877         //Project each vertex along normal
878         numVerts= calc->final->getNumVerts(calc->final);
879         vert    = calc->final->getVertDataArray(calc->final, CD_MVERT); 
880         dvert   = calc->final->getVertDataArray(calc->final, CD_MDEFORMVERT);
881
882         if(calc->smd->shrinkOpts & MOD_SHRINKWRAP_REMOVE_UNPROJECTED_FACES)
883                 calc->moved = bitset_new(numVerts, "shrinkwrap bitset data");
884
885         for(i=0; i<numVerts; i++)
886         {
887                 float dist = FLT_MAX;
888                 float weight = vertexgroup_get_weight(dvert, i, vgroup);
889                 if(weight == 0.0f) continue;
890
891                 //Transform coordinates local->target
892                 VecMat4MulVecfl(tmp_co, calc->local2target, vert[i].co);
893
894                 normal_short2float(vert[i].no, tmp_no);
895                 Mat4Mul3Vecfl(calc->local2target, tmp_no);      //Watch out for scaling on normal
896                 Normalize(tmp_no);                                                      //(TODO: do we really needed a unit-len normal? and we could know the scale factor before hand?)
897
898
899                 if(use_normal & MOD_SHRINKWRAP_ALLOW_DEFAULT_NORMAL)
900                 {
901                         dist = raytree_cast_ray(target, tmp_co, tmp_no);
902                 }
903
904                 normal_short2float(vert[i].no, tmp_no);
905                 Mat4Mul3Vecfl(calc->local2target, tmp_no);      //Watch out for scaling on normal
906                 Normalize(tmp_no);                                                      //(TODO: do we really needed a unit-len normal? and we could know the scale factor before hand?)
907
908                 if(use_normal & MOD_SHRINKWRAP_ALLOW_INVERTED_NORMAL)
909                 {
910                         float inv[3]; // = {-tmp_no[0], -tmp_no[1], -tmp_no[2]};
911                         float tdist;
912
913                         inv[0] = -tmp_no[0];
914                         inv[1] = -tmp_no[1];
915                         inv[2] = -tmp_no[2];
916
917                         tdist = raytree_cast_ray(target, tmp_co, inv);
918
919                         if(ABS(tdist) < ABS(dist))
920                                 dist = -tdist;
921                 }
922
923                 if(ABS(dist) != FLT_MAX)
924                 {
925                         float dist_t;
926
927                         VECADDFAC(tmp_co, tmp_co, tmp_no, dist);
928                         VecMat4MulVecfl(tmp_co, calc->target2local, tmp_co);
929
930                         dist_t = VecLenf(vert[i].co, tmp_co);
931                         if(dist_t > 1e-5) weight *= (dist_t - calc->keptDist)/dist_t;
932                         VecLerpf(vert[i].co, vert[i].co, tmp_co, weight);       //linear interpolation
933
934                         if(calc->moved)
935                                 bitset_set(calc->moved, i);
936                 }
937
938         }
939
940         free_raytree_from_mesh(target);
941 }
942
943