Merge branch 'master' into blender2.8
[blender.git] / source / blender / blenkernel / intern / shrinkwrap.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  * The Original Code is Copyright (C) Blender Foundation.
19  * All rights reserved.
20  *
21  * The Original Code is: all of this file.
22  *
23  * Contributor(s): Andr Pinto
24  *
25  * ***** END GPL LICENSE BLOCK *****
26  */
27
28 /** \file blender/blenkernel/intern/shrinkwrap.c
29  *  \ingroup bke
30  */
31
32 #include <string.h>
33 #include <float.h>
34 #include <math.h>
35 #include <memory.h>
36 #include <stdio.h>
37 #include <time.h>
38 #include <assert.h>
39
40 #include "DNA_object_types.h"
41 #include "DNA_modifier_types.h"
42 #include "DNA_meshdata_types.h"
43 #include "DNA_mesh_types.h"
44
45 #include "BLI_math.h"
46 #include "BLI_utildefines.h"
47 #include "BLI_task.h"
48
49 #include "BKE_shrinkwrap.h"
50 #include "BKE_cdderivedmesh.h"
51 #include "BKE_DerivedMesh.h"
52 #include "BKE_lattice.h"
53 #include "BKE_library.h"
54 #include "BKE_modifier.h"
55
56 #include "BKE_deform.h"
57 #include "BKE_editmesh.h"
58 #include "BKE_mesh.h"  /* for OMP limits. */
59 #include "BKE_subsurf.h"
60
61 #include "BLI_strict_flags.h"
62
63 /* for timing... */
64 #if 0
65 #  include "PIL_time_utildefines.h"
66 #else
67 #  define TIMEIT_BENCH(expr, id) (expr)
68 #endif
69
70 /* Util macros */
71 #define OUT_OF_MEMORY() ((void)printf("Shrinkwrap: Out of memory\n"))
72
73 typedef struct ShrinkwrapCalcCBData {
74         ShrinkwrapCalcData *calc;
75
76         void *treeData;
77         void *auxData;
78         BVHTree *targ_tree;
79         BVHTree *aux_tree;
80         void *targ_callback;
81         void *aux_callback;
82
83         float *proj_axis;
84         SpaceTransform *local2aux;
85 } ShrinkwrapCalcCBData;
86
87 /*
88  * Shrinkwrap to the nearest vertex
89  *
90  * it builds a kdtree of vertexs we can attach to and then
91  * for each vertex performs a nearest vertex search on the tree
92  */
93 static void shrinkwrap_calc_nearest_vertex_cb_ex(
94         void *__restrict userdata,
95         const int i,
96         const ParallelRangeTLS *__restrict tls)
97 {
98         ShrinkwrapCalcCBData *data = userdata;
99
100         ShrinkwrapCalcData *calc = data->calc;
101         BVHTreeFromMesh *treeData = data->treeData;
102         BVHTreeNearest *nearest = tls->userdata_chunk;
103
104         float *co = calc->vertexCos[i];
105         float tmp_co[3];
106         float weight = defvert_array_find_weight_safe(calc->dvert, i, calc->vgroup);
107
108         if (calc->invert_vgroup) {
109                 weight = 1.0f - weight;
110         }
111
112         if (weight == 0.0f) {
113                 return;
114         }
115
116         /* Convert the vertex to tree coordinates */
117         if (calc->vert) {
118                 copy_v3_v3(tmp_co, calc->vert[i].co);
119         }
120         else {
121                 copy_v3_v3(tmp_co, co);
122         }
123         BLI_space_transform_apply(&calc->local2target, tmp_co);
124
125         /* Use local proximity heuristics (to reduce the nearest search)
126          *
127          * If we already had an hit before.. we assume this vertex is going to have a close hit to that other vertex
128          * so we can initiate the "nearest.dist" with the expected value to that last hit.
129          * This will lead in pruning of the search tree. */
130         if (nearest->index != -1)
131                 nearest->dist_sq = len_squared_v3v3(tmp_co, nearest->co);
132         else
133                 nearest->dist_sq = FLT_MAX;
134
135         BLI_bvhtree_find_nearest(treeData->tree, tmp_co, nearest, treeData->nearest_callback, treeData);
136
137
138         /* Found the nearest vertex */
139         if (nearest->index != -1) {
140                 /* Adjusting the vertex weight,
141                  * so that after interpolating it keeps a certain distance from the nearest position */
142                 if (nearest->dist_sq > FLT_EPSILON) {
143                         const float dist = sqrtf(nearest->dist_sq);
144                         weight *= (dist - calc->keepDist) / dist;
145                 }
146
147                 /* Convert the coordinates back to mesh coordinates */
148                 copy_v3_v3(tmp_co, nearest->co);
149                 BLI_space_transform_invert(&calc->local2target, tmp_co);
150
151                 interp_v3_v3v3(co, co, tmp_co, weight);  /* linear interpolation */
152         }
153 }
154
155 static void shrinkwrap_calc_nearest_vertex(ShrinkwrapCalcData *calc)
156 {
157         BVHTreeFromMesh treeData = NULL_BVHTreeFromMesh;
158         BVHTreeNearest nearest  = NULL_BVHTreeNearest;
159
160         if (calc->target != NULL && calc->target->totvert == 0) {
161                 return;
162         }
163
164         TIMEIT_BENCH(BKE_bvhtree_from_mesh_get(&treeData, calc->target, BVHTREE_FROM_VERTS, 2), bvhtree_verts);
165         if (treeData.tree == NULL) {
166                 OUT_OF_MEMORY();
167                 return;
168         }
169         
170         /* Setup nearest */
171         nearest.index = -1;
172         nearest.dist_sq = FLT_MAX;
173
174         ShrinkwrapCalcCBData data = {.calc = calc, .treeData = &treeData};
175         ParallelRangeSettings settings;
176         BLI_parallel_range_settings_defaults(&settings);
177         settings.use_threading = (calc->numVerts > BKE_MESH_OMP_LIMIT);
178         settings.userdata_chunk = &nearest;
179         settings.userdata_chunk_size = sizeof(nearest);
180         BLI_task_parallel_range(0, calc->numVerts,
181                                 &data, shrinkwrap_calc_nearest_vertex_cb_ex,
182                                 &settings);
183
184         free_bvhtree_from_mesh(&treeData);
185 }
186
187
188 /*
189  * This function raycast a single vertex and updates the hit if the "hit" is considered valid.
190  * Returns true if "hit" was updated.
191  * Opts control whether an hit is valid or not
192  * Supported options are:
193  *      MOD_SHRINKWRAP_CULL_TARGET_FRONTFACE (front faces hits are ignored)
194  *      MOD_SHRINKWRAP_CULL_TARGET_BACKFACE (back faces hits are ignored)
195  */
196 bool BKE_shrinkwrap_project_normal(
197         char options, const float vert[3], const float dir[3],
198         const float ray_radius, const SpaceTransform *transf,
199         BVHTree *tree, BVHTreeRayHit *hit,
200         BVHTree_RayCastCallback callback, void *userdata)
201 {
202         /* don't use this because this dist value could be incompatible
203          * this value used by the callback for comparing prev/new dist values.
204          * also, at the moment there is no need to have a corrected 'dist' value */
205 // #define USE_DIST_CORRECT
206
207         float tmp_co[3], tmp_no[3];
208         const float *co, *no;
209         BVHTreeRayHit hit_tmp;
210
211         /* Copy from hit (we need to convert hit rays from one space coordinates to the other */
212         memcpy(&hit_tmp, hit, sizeof(hit_tmp));
213
214         /* Apply space transform (TODO readjust dist) */
215         if (transf) {
216                 copy_v3_v3(tmp_co, vert);
217                 BLI_space_transform_apply(transf, tmp_co);
218                 co = tmp_co;
219
220                 copy_v3_v3(tmp_no, dir);
221                 BLI_space_transform_apply_normal(transf, tmp_no);
222                 no = tmp_no;
223
224 #ifdef USE_DIST_CORRECT
225                 hit_tmp.dist *= mat4_to_scale(((SpaceTransform *)transf)->local2target);
226 #endif
227         }
228         else {
229                 co = vert;
230                 no = dir;
231         }
232
233         hit_tmp.index = -1;
234
235         BLI_bvhtree_ray_cast(tree, co, no, ray_radius, &hit_tmp, callback, userdata);
236
237         if (hit_tmp.index != -1) {
238                 /* invert the normal first so face culling works on rotated objects */
239                 if (transf) {
240                         BLI_space_transform_invert_normal(transf, hit_tmp.no);
241                 }
242
243                 if (options & (MOD_SHRINKWRAP_CULL_TARGET_FRONTFACE | MOD_SHRINKWRAP_CULL_TARGET_BACKFACE)) {
244                         /* apply backface */
245                         const float dot = dot_v3v3(dir, hit_tmp.no);
246                         if (((options & MOD_SHRINKWRAP_CULL_TARGET_FRONTFACE) && dot <= 0.0f) ||
247                             ((options & MOD_SHRINKWRAP_CULL_TARGET_BACKFACE)  && dot >= 0.0f))
248                         {
249                                 return false;  /* Ignore hit */
250                         }
251                 }
252
253                 if (transf) {
254                         /* Inverting space transform (TODO make coeherent with the initial dist readjust) */
255                         BLI_space_transform_invert(transf, hit_tmp.co);
256 #ifdef USE_DIST_CORRECT
257                         hit_tmp.dist = len_v3v3(vert, hit_tmp.co);
258 #endif
259                 }
260
261                 BLI_assert(hit_tmp.dist <= hit->dist);
262
263                 memcpy(hit, &hit_tmp, sizeof(hit_tmp));
264                 return true;
265         }
266         return false;
267 }
268
269 static void shrinkwrap_calc_normal_projection_cb_ex(
270         void *__restrict userdata,
271         const int i,
272         const ParallelRangeTLS *__restrict tls)
273 {
274         ShrinkwrapCalcCBData *data = userdata;
275
276         ShrinkwrapCalcData *calc = data->calc;
277         void *treeData = data->treeData;
278         void *auxData = data->auxData;
279         BVHTree *targ_tree = data->targ_tree;
280         BVHTree *aux_tree = data->aux_tree;
281         void *targ_callback = data->targ_callback;
282         void *aux_callback = data->aux_callback;
283
284         float *proj_axis = data->proj_axis;
285         SpaceTransform *local2aux = data->local2aux;
286
287         BVHTreeRayHit *hit = tls->userdata_chunk;
288
289         const float proj_limit_squared = calc->smd->projLimit * calc->smd->projLimit;
290         float *co = calc->vertexCos[i];
291         float tmp_co[3], tmp_no[3];
292         float weight = defvert_array_find_weight_safe(calc->dvert, i, calc->vgroup);
293
294         if (calc->invert_vgroup) {
295                 weight = 1.0f - weight;
296         }
297
298         if (weight == 0.0f) {
299                 return;
300         }
301
302         if (calc->vert) {
303                 /* calc->vert contains verts from derivedMesh  */
304                 /* this coordinated are deformed by vertexCos only for normal projection (to get correct normals) */
305                 /* for other cases calc->varts contains undeformed coordinates and vertexCos should be used */
306                 if (calc->smd->projAxis == MOD_SHRINKWRAP_PROJECT_OVER_NORMAL) {
307                         copy_v3_v3(tmp_co, calc->vert[i].co);
308                         normal_short_to_float_v3(tmp_no, calc->vert[i].no);
309                 }
310                 else {
311                         copy_v3_v3(tmp_co, co);
312                         copy_v3_v3(tmp_no, proj_axis);
313                 }
314         }
315         else {
316                 copy_v3_v3(tmp_co, co);
317                 copy_v3_v3(tmp_no, proj_axis);
318         }
319
320
321         hit->index = -1;
322         hit->dist = BVH_RAYCAST_DIST_MAX; /* TODO: we should use FLT_MAX here, but sweepsphere code isn't prepared for that */
323
324         /* Project over positive direction of axis */
325         if (calc->smd->shrinkOpts & MOD_SHRINKWRAP_PROJECT_ALLOW_POS_DIR) {
326                 if (aux_tree) {
327                         BKE_shrinkwrap_project_normal(
328                                 0, tmp_co, tmp_no, 0.0,
329                                 local2aux, aux_tree, hit,
330                                 aux_callback, auxData);
331                 }
332
333                 BKE_shrinkwrap_project_normal(
334                         calc->smd->shrinkOpts, tmp_co, tmp_no, 0.0,
335                         &calc->local2target, targ_tree, hit,
336                         targ_callback, treeData);
337         }
338
339         /* Project over negative direction of axis */
340         if (calc->smd->shrinkOpts & MOD_SHRINKWRAP_PROJECT_ALLOW_NEG_DIR) {
341                 float inv_no[3];
342                 negate_v3_v3(inv_no, tmp_no);
343
344                 if (aux_tree) {
345                         BKE_shrinkwrap_project_normal(
346                                 0, tmp_co, inv_no, 0.0,
347                                 local2aux, aux_tree, hit,
348                                 aux_callback, auxData);
349                 }
350
351                 BKE_shrinkwrap_project_normal(
352                         calc->smd->shrinkOpts, tmp_co, inv_no, 0.0,
353                         &calc->local2target, targ_tree, hit,
354                         targ_callback, treeData);
355         }
356
357         /* don't set the initial dist (which is more efficient),
358          * because its calculated in the targets space, we want the dist in our own space */
359         if (proj_limit_squared != 0.0f) {
360                 if (len_squared_v3v3(hit->co, co) > proj_limit_squared) {
361                         hit->index = -1;
362                 }
363         }
364
365         if (hit->index != -1) {
366                 madd_v3_v3v3fl(hit->co, hit->co, tmp_no, calc->keepDist);
367                 interp_v3_v3v3(co, co, hit->co, weight);
368         }
369 }
370
371 static void shrinkwrap_calc_normal_projection(ShrinkwrapCalcData *calc)
372 {
373         /* Options about projection direction */
374         float proj_axis[3]      = {0.0f, 0.0f, 0.0f};
375
376         /* Raycast and tree stuff */
377
378         /** \note 'hit.dist' is kept in the targets space, this is only used
379          * for finding the best hit, to get the real dist,
380          * measure the len_v3v3() from the input coord to hit.co */
381         BVHTreeRayHit hit;
382         void *treeData = NULL;
383
384         /* auxiliary target */
385         Mesh *auxMesh = NULL;
386         bool auxMesh_free;
387         void *auxData = NULL;
388         SpaceTransform local2aux;
389
390         /* If the user doesn't allows to project in any direction of projection axis
391          * then theres nothing todo. */
392         if ((calc->smd->shrinkOpts & (MOD_SHRINKWRAP_PROJECT_ALLOW_POS_DIR | MOD_SHRINKWRAP_PROJECT_ALLOW_NEG_DIR)) == 0)
393                 return;
394
395         if (calc->target != NULL && calc->target->totpoly == 0) {
396                 return;
397         }
398
399         /* Prepare data to retrieve the direction in which we should project each vertex */
400         if (calc->smd->projAxis == MOD_SHRINKWRAP_PROJECT_OVER_NORMAL) {
401                 if (calc->vert == NULL) return;
402         }
403         else {
404                 /* The code supports any axis that is a combination of X,Y,Z
405                  * although currently UI only allows to set the 3 different axis */
406                 if (calc->smd->projAxis & MOD_SHRINKWRAP_PROJECT_OVER_X_AXIS) proj_axis[0] = 1.0f;
407                 if (calc->smd->projAxis & MOD_SHRINKWRAP_PROJECT_OVER_Y_AXIS) proj_axis[1] = 1.0f;
408                 if (calc->smd->projAxis & MOD_SHRINKWRAP_PROJECT_OVER_Z_AXIS) proj_axis[2] = 1.0f;
409
410                 normalize_v3(proj_axis);
411
412                 /* Invalid projection direction */
413                 if (len_squared_v3(proj_axis) < FLT_EPSILON) {
414                         return;
415                 }
416         }
417
418         if (calc->smd->auxTarget) {
419                 auxMesh = BKE_modifier_get_evaluated_mesh_from_evaluated_object(calc->smd->auxTarget, &auxMesh_free);
420                 if (!auxMesh)
421                         return;
422                 BLI_SPACE_TRANSFORM_SETUP(&local2aux, calc->ob, calc->smd->auxTarget);
423         }
424
425         /* use editmesh to avoid array allocation */
426         BMEditMesh *emtarget = NULL, *emaux = NULL;
427         union {
428                 BVHTreeFromEditMesh emtreedata;
429                 BVHTreeFromMesh dmtreedata;
430         } treedata_stack, auxdata_stack;
431
432         BVHTree *targ_tree;
433         void *targ_callback;
434         if ((targ_tree = BKE_bvhtree_from_mesh_get(
435                  &treedata_stack.dmtreedata, calc->target, BVHTREE_FROM_LOOPTRI, 4)))
436         {
437                 targ_callback = treedata_stack.dmtreedata.raycast_callback;
438                 treeData = &treedata_stack.dmtreedata;
439
440                 BVHTree *aux_tree = NULL;
441                 void *aux_callback = NULL;
442                 if (auxMesh != NULL && auxMesh->totpoly != 0) {
443                         /* use editmesh to avoid array allocation */
444                         if ((aux_tree = BKE_bvhtree_from_mesh_get(
445                                  &auxdata_stack.dmtreedata, auxMesh, BVHTREE_FROM_LOOPTRI, 4)) != NULL)
446                         {
447                                 aux_callback = auxdata_stack.dmtreedata.raycast_callback;
448                                 auxData = &auxdata_stack.dmtreedata;
449                         }
450                 }
451                 /* After sucessufuly build the trees, start projection vertexs */
452                 ShrinkwrapCalcCBData data = {
453                         .calc = calc,
454                         .treeData = treeData, .targ_tree = targ_tree, .targ_callback = targ_callback,
455                         .auxData = auxData, .aux_tree = aux_tree, .aux_callback = aux_callback,
456                         .proj_axis = proj_axis, .local2aux = &local2aux,
457                 };
458                 ParallelRangeSettings settings;
459                 BLI_parallel_range_settings_defaults(&settings);
460                 settings.use_threading = (calc->numVerts > BKE_MESH_OMP_LIMIT);
461                 settings.userdata_chunk = &hit;
462                 settings.userdata_chunk_size = sizeof(hit);
463                 BLI_task_parallel_range(0, calc->numVerts,
464                                         &data,
465                                         shrinkwrap_calc_normal_projection_cb_ex,
466                                         &settings);
467         }
468
469         /* free data structures */
470         if (treeData) {
471                 if (emtarget) {
472                         free_bvhtree_from_editmesh(treeData);
473                 }
474                 else {
475                         free_bvhtree_from_mesh(treeData);
476                 }
477         }
478
479         if (auxData) {
480                 if (emaux) {
481                         free_bvhtree_from_editmesh(auxData);
482                 }
483                 else {
484                         free_bvhtree_from_mesh(auxData);
485                 }
486         }
487         if (auxMesh != NULL && auxMesh_free) {
488                 BKE_id_free(NULL, auxMesh);
489         }
490 }
491
492 /*
493  * Shrinkwrap moving vertexs to the nearest surface point on the target
494  *
495  * it builds a BVHTree from the target mesh and then performs a
496  * NN matches for each vertex
497  */
498 static void shrinkwrap_calc_nearest_surface_point_cb_ex(
499         void *__restrict userdata,
500         const int i,
501         const ParallelRangeTLS *__restrict tls)
502 {
503         ShrinkwrapCalcCBData *data = userdata;
504
505         ShrinkwrapCalcData *calc = data->calc;
506         BVHTreeFromMesh *treeData = data->treeData;
507         BVHTreeNearest *nearest = tls->userdata_chunk;
508
509         float *co = calc->vertexCos[i];
510         float tmp_co[3];
511         float weight = defvert_array_find_weight_safe(calc->dvert, i, calc->vgroup);
512
513         if (calc->invert_vgroup) {
514                 weight = 1.0f - weight;
515         }
516
517         if (weight == 0.0f) {
518                 return;
519         }
520
521         /* Convert the vertex to tree coordinates */
522         if (calc->vert) {
523                 copy_v3_v3(tmp_co, calc->vert[i].co);
524         }
525         else {
526                 copy_v3_v3(tmp_co, co);
527         }
528         BLI_space_transform_apply(&calc->local2target, tmp_co);
529
530         /* Use local proximity heuristics (to reduce the nearest search)
531          *
532          * If we already had an hit before.. we assume this vertex is going to have a close hit to that other vertex
533          * so we can initiate the "nearest.dist" with the expected value to that last hit.
534          * This will lead in pruning of the search tree. */
535         if (nearest->index != -1)
536                 nearest->dist_sq = len_squared_v3v3(tmp_co, nearest->co);
537         else
538                 nearest->dist_sq = FLT_MAX;
539
540         BLI_bvhtree_find_nearest(treeData->tree, tmp_co, nearest, treeData->nearest_callback, treeData);
541
542         /* Found the nearest vertex */
543         if (nearest->index != -1) {
544                 if (calc->smd->shrinkOpts & MOD_SHRINKWRAP_KEEP_ABOVE_SURFACE) {
545                         /* Make the vertex stay on the front side of the face */
546                         madd_v3_v3v3fl(tmp_co, nearest->co, nearest->no, calc->keepDist);
547                 }
548                 else {
549                         /* Adjusting the vertex weight,
550                          * so that after interpolating it keeps a certain distance from the nearest position */
551                         const float dist = sasqrt(nearest->dist_sq);
552                         if (dist > FLT_EPSILON) {
553                                 /* linear interpolation */
554                                 interp_v3_v3v3(tmp_co, tmp_co, nearest->co, (dist - calc->keepDist) / dist);
555                         }
556                         else {
557                                 copy_v3_v3(tmp_co, nearest->co);
558                         }
559                 }
560
561                 /* Convert the coordinates back to mesh coordinates */
562                 BLI_space_transform_invert(&calc->local2target, tmp_co);
563                 interp_v3_v3v3(co, co, tmp_co, weight);  /* linear interpolation */
564         }
565 }
566
567 static void shrinkwrap_calc_nearest_surface_point(ShrinkwrapCalcData *calc)
568 {
569         BVHTreeFromMesh treeData = NULL_BVHTreeFromMesh;
570         BVHTreeNearest nearest  = NULL_BVHTreeNearest;
571
572         if (calc->target->totpoly == 0) {
573                 return;
574         }
575
576         /* Create a bvh-tree of the given target */
577         BKE_bvhtree_from_mesh_get(&treeData, calc->target, BVHTREE_FROM_LOOPTRI, 2);
578         if (treeData.tree == NULL) {
579                 OUT_OF_MEMORY();
580                 return;
581         }
582
583         /* Setup nearest */
584         nearest.index = -1;
585         nearest.dist_sq = FLT_MAX;
586
587         /* Find the nearest vertex */
588         ShrinkwrapCalcCBData data = {.calc = calc, .treeData = &treeData};
589         ParallelRangeSettings settings;
590         BLI_parallel_range_settings_defaults(&settings);
591         settings.use_threading = (calc->numVerts > BKE_MESH_OMP_LIMIT);
592         settings.userdata_chunk = &nearest;
593         settings.userdata_chunk_size = sizeof(nearest);
594         BLI_task_parallel_range(0, calc->numVerts,
595                                 &data,
596                                 shrinkwrap_calc_nearest_surface_point_cb_ex,
597                                 &settings);
598
599         free_bvhtree_from_mesh(&treeData);
600 }
601
602 /* Main shrinkwrap function */
603 void shrinkwrapModifier_deform(ShrinkwrapModifierData *smd, Object *ob, Mesh *mesh,
604                                float (*vertexCos)[3], int numVerts)
605 {
606
607         DerivedMesh *ss_mesh    = NULL;
608         ShrinkwrapCalcData calc = NULL_ShrinkwrapCalcData;
609         bool target_free;
610
611         /* remove loop dependencies on derived meshes (TODO should this be done elsewhere?) */
612         if (smd->target == ob) smd->target = NULL;
613         if (smd->auxTarget == ob) smd->auxTarget = NULL;
614
615
616         /* Configure Shrinkwrap calc data */
617         calc.smd = smd;
618         calc.ob = ob;
619         calc.numVerts = numVerts;
620         calc.vertexCos = vertexCos;
621         calc.invert_vgroup = (smd->shrinkOpts & MOD_SHRINKWRAP_INVERT_VGROUP) != 0;
622
623         /* DeformVertex */
624         calc.vgroup = defgroup_name_index(calc.ob, calc.smd->vgroup_name);
625         if (mesh) {
626                 calc.dvert = mesh->dvert;
627         }
628         else if (calc.ob->type == OB_LATTICE) {
629                 calc.dvert = BKE_lattice_deform_verts_get(calc.ob);
630         }
631
632
633         if (smd->target) {
634                 calc.target = BKE_modifier_get_evaluated_mesh_from_evaluated_object(smd->target, &target_free);
635
636                 /* TODO there might be several "bugs" on non-uniform scales matrixs
637                  * because it will no longer be nearest surface, not sphere projection
638                  * because space has been deformed */
639                 BLI_SPACE_TRANSFORM_SETUP(&calc.local2target, ob, smd->target);
640
641                 /* TODO: smd->keepDist is in global units.. must change to local */
642                 calc.keepDist = smd->keepDist;
643         }
644
645
646
647         calc.vgroup = defgroup_name_index(calc.ob, smd->vgroup_name);
648
649         if (mesh != NULL && smd->shrinkType == MOD_SHRINKWRAP_PROJECT) {
650                 /* Setup arrays to get vertexs positions, normals and deform weights */
651                 calc.vert   = mesh->mvert;
652                 calc.dvert  = mesh->dvert;
653
654                 /* Using vertexs positions/normals as if a subsurface was applied */
655                 if (smd->subsurfLevels) {
656                         SubsurfModifierData ssmd = {{NULL}};
657                         ssmd.subdivType = ME_CC_SUBSURF;        /* catmull clark */
658                         ssmd.levels     = smd->subsurfLevels;   /* levels */
659
660                         /* TODO to be moved to Mesh once we are done with changes in subsurf code. */
661                         DerivedMesh *dm = CDDM_from_mesh(mesh);
662
663                         ss_mesh = subsurf_make_derived_from_derived(dm, &ssmd, NULL, (ob->mode & OB_MODE_EDIT) ? SUBSURF_IN_EDIT_MODE : 0);
664
665                         if (ss_mesh) {
666                                 calc.vert = ss_mesh->getVertDataArray(ss_mesh, CD_MVERT);
667                                 if (calc.vert) {
668                                         /* TRICKY: this code assumes subsurface will have the transformed original vertices
669                                          * in their original order at the end of the vert array. */
670                                         calc.vert = calc.vert + ss_mesh->getNumVerts(ss_mesh) - dm->getNumVerts(dm);
671                                 }
672                         }
673
674                         /* Just to make sure we are not leaving any memory behind */
675                         BLI_assert(ssmd.emCache == NULL);
676                         BLI_assert(ssmd.mCache == NULL);
677
678                         dm->release(dm);
679                 }
680         }
681
682         /* Projecting target defined - lets work! */
683         if (calc.target) {
684                 switch (smd->shrinkType) {
685                         case MOD_SHRINKWRAP_NEAREST_SURFACE:
686                                 TIMEIT_BENCH(shrinkwrap_calc_nearest_surface_point(&calc), deform_surface);
687                                 break;
688
689                         case MOD_SHRINKWRAP_PROJECT:
690                                 TIMEIT_BENCH(shrinkwrap_calc_normal_projection(&calc), deform_project);
691                                 break;
692
693                         case MOD_SHRINKWRAP_NEAREST_VERTEX:
694                                 TIMEIT_BENCH(shrinkwrap_calc_nearest_vertex(&calc), deform_vertex);
695                                 break;
696                 }
697         }
698
699         /* free memory */
700         if (ss_mesh)
701                 ss_mesh->release(ss_mesh);
702
703         if (target_free && calc.target) {
704                 BKE_id_free(NULL, calc.target);
705         }
706 }