source/blender/editors/transform/transform_snap_object.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  * ***** END GPL LICENSE BLOCK *****
  19  */
  20
  21 /** \file blender/editors/transform/transform_snap_object.c
  22  *  \ingroup edtransform
  23  */
  24
  25 #include <stdlib.h>
  26 #include <math.h>
  27 #include <float.h>
  28 #include <stdio.h>
  29
  30 #include "MEM_guardedalloc.h"
  31
  32 #include "BLI_math.h"
  33 #include "BLI_kdopbvh.h"
  34 #include "BLI_memarena.h"
  35 #include "BLI_ghash.h"
  36 #include "BLI_linklist.h"
  37 #include "BLI_listbase.h"
  38 #include "BLI_utildefines.h"
  39
  40 #include "DNA_armature_types.h"
  41 #include "DNA_curve_types.h"
  42 #include "DNA_scene_types.h"
  43 #include "DNA_object_types.h"
  44 #include "DNA_meshdata_types.h"
  45 #include "DNA_screen_types.h"
  46 #include "DNA_view3d_types.h"
  47
  48 #include "BKE_DerivedMesh.h"
  49 #include "BKE_object.h"
  50 #include "BKE_anim.h"  /* for duplis */
  51 #include "BKE_editmesh.h"
  52 #include "BKE_main.h"
  53 #include "BKE_tracking.h"
  54
  55 #include "ED_transform.h"
  56 #include "ED_transform_snap_object_context.h"
  57 #include "ED_view3d.h"
  58 #include "ED_armature.h"
  59
  60 #include "transform.h"
  61
  62 typedef struct SnapObjectData {
  63         enum {
  64                 SNAP_MESH = 1,
  65                 SNAP_EDIT_MESH,
  66         } type;
  67 } SnapObjectData;
  68
  69 typedef struct SnapObjectData_Mesh {
  70         SnapObjectData sd;
  71         BVHTreeFromMesh *bvh_trees[2];
  72
  73 } SnapObjectData_Mesh;
  74
  75 typedef struct SnapObjectData_EditMesh {
  76         SnapObjectData sd;
  77         BVHTreeFromEditMesh *bvh_trees[2];
  78
  79 } SnapObjectData_EditMesh;
  80
  81 struct SnapObjectContext {
  82         Main *bmain;
  83         Scene *scene;
  84         int flag;
  85
  86         /* Optional: when performing screen-space projection.
  87          * otherwise this doesn't take viewport into account. */
  88         bool use_v3d;
  89         struct {
  90                 struct View3D *v3d;
  91                 struct ARegion *ar;
  92         } v3d_data;
  93
  94
  95         /* Object -> SnapObjectData map */
  96         struct {
  97                 GHash *object_map;
  98                 MemArena *mem_arena;
  99         } cache;
 100
 101         /* Filter data, returns true to check this value */
 102         struct {
 103                 struct {
 104                         bool (*test_vert_fn)(BMVert *, void *user_data);
 105                         bool (*test_edge_fn)(BMEdge *, void *user_data);
 106                         bool (*test_face_fn)(BMFace *, void *user_data);
 107                         void *user_data;
 108                 } edit_mesh;
 109         } callbacks;
 110
 111 };
 112
 113 static int dm_looptri_to_poly_index(DerivedMesh *dm, const MLoopTri *lt);
 114
 115
 116 /* -------------------------------------------------------------------- */
 117
 118 /** \name Support for storing all depths, not just the first (raycast 'all')
 119  *
 120  * This uses a list of #SnapObjectHitDepth structs.
 121  *
 122  * \{ */
 123
 124 /* Store all ray-hits */
 125 struct RayCastAll_Data {
 126         void *bvhdata;
 127
 128         /* internal vars for adding depths */
 129         BVHTree_RayCastCallback raycast_callback;
 130
 131         const float(*obmat)[4];
 132         const float(*timat)[3];
 133
 134         float len_diff;
 135         float local_scale;
 136
 137         Object *ob;
 138         unsigned int ob_uuid;
 139
 140         /* DerivedMesh only */
 141         DerivedMesh *dm;
 142         const struct MLoopTri *dm_looptri;
 143
 144         /* output data */
 145         ListBase *hit_list;
 146         bool retval;
 147 };
 148
 149 static struct SnapObjectHitDepth *hit_depth_create(
 150         const float depth, const float co[3], const float no[3], int index,
 151         Object *ob, const float obmat[4][4], unsigned int ob_uuid)
 152 {
 153         struct SnapObjectHitDepth *hit = MEM_mallocN(sizeof(*hit), __func__);
 154
 155         hit->depth = depth;
 156         copy_v3_v3(hit->co, co);
 157         copy_v3_v3(hit->no, no);
 158         hit->index = index;
 159
 160         hit->ob = ob;
 161         copy_m4_m4(hit->obmat, (float(*)[4])obmat);
 162         hit->ob_uuid = ob_uuid;
 163
 164         return hit;
 165 }
 166
 167 static int hit_depth_cmp(const void *arg1, const void *arg2)
 168 {
 169         const struct SnapObjectHitDepth *h1 = arg1;
 170         const struct SnapObjectHitDepth *h2 = arg2;
 171         int val = 0;
 172
 173         if (h1->depth < h2->depth) {
 174                 val = -1;
 175         }
 176         else if (h1->depth > h2->depth) {
 177                 val = 1;
 178         }
 179
 180         return val;
 181 }
 182
 183 static void raycast_all_cb(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit)
 184 {
 185         struct RayCastAll_Data *data = userdata;
 186         data->raycast_callback(data->bvhdata, index, ray, hit);
 187         if (hit->index != -1) {
 188                 /* get all values in worldspace */
 189                 float location[3], normal[3];
 190                 float depth;
 191
 192                 /* worldspace location */
 193                 mul_v3_m4v3(location, (float(*)[4])data->obmat, hit->co);
 194                 depth = (hit->dist + data->len_diff) / data->local_scale;
 195
 196                 /* worldspace normal */
 197                 copy_v3_v3(normal, hit->no);
 198                 mul_m3_v3((float(*)[3])data->timat, normal);
 199                 normalize_v3(normal);
 200
 201                 /* currently unused, and causes issues when looptri's havn't been calculated.
 202                  * since theres some overhead in ensuring this data is valid, it may need to be optional. */
 203 #if 0
 204                 if (data->dm) {
 205                         hit->index = dm_looptri_to_poly_index(data->dm, &data->dm_looptri[hit->index]);
 206                 }
 207 #endif
 208
 209                 struct SnapObjectHitDepth *hit_item = hit_depth_create(
 210                         depth, location, normal, hit->index,
 211                         data->ob, data->obmat, data->ob_uuid);
 212                 BLI_addtail(data->hit_list, hit_item);
 213         }
 214 }
 215
 216 /** \} */
 217
 218
 219 /* -------------------------------------------------------------------- */
 220
 221 /** \name Internal Object Snapping API
 222  * \{ */
 223
 224 static bool snapEdge(
 225         ARegion *ar, const float v1co[3], const short v1no[3], const float v2co[3], const short v2no[3],
 226         float obmat[4][4], float timat[3][3], const float mval_fl[2], float *dist_px,
 227         const float ray_start[3], const float ray_start_local[3], const float ray_normal_local[3], float *ray_depth,
 228         float r_loc[3], float r_no[3])
 229 {
 230         float intersect[3] = {0, 0, 0}, ray_end[3], dvec[3];
 231         int result;
 232         bool retval = false;
 233
 234         copy_v3_v3(ray_end, ray_normal_local);
 235         mul_v3_fl(ray_end, 2000);
 236         add_v3_v3v3(ray_end, ray_start_local, ray_end);
 237
 238         /* dvec used but we don't care about result */
 239         result = isect_line_line_v3(v1co, v2co, ray_start_local, ray_end, intersect, dvec);
 240
 241         if (result) {
 242                 float edge_loc[3], vec[3];
 243                 float mul;
 244
 245                 /* check for behind ray_start */
 246                 sub_v3_v3v3(dvec, intersect, ray_start_local);
 247
 248                 sub_v3_v3v3(edge_loc, v1co, v2co);
 249                 sub_v3_v3v3(vec, intersect, v2co);
 250
 251                 mul = dot_v3v3(vec, edge_loc) / dot_v3v3(edge_loc, edge_loc);
 252
 253                 if (mul > 1) {
 254                         mul = 1;
 255                         copy_v3_v3(intersect, v1co);
 256                 }
 257                 else if (mul < 0) {
 258                         mul = 0;
 259                         copy_v3_v3(intersect, v2co);
 260                 }
 261
 262                 if (dot_v3v3(ray_normal_local, dvec) > 0) {
 263                         float location[3];
 264                         float new_depth;
 265                         float screen_loc[2];
 266                         float new_dist;
 267
 268                         copy_v3_v3(location, intersect);
 269
 270                         mul_m4_v3(obmat, location);
 271
 272                         new_depth = len_v3v3(location, ray_start);
 273
 274                         if (ED_view3d_project_float_global(ar, location, screen_loc, V3D_PROJ_TEST_NOP) == V3D_PROJ_RET_OK) {
 275                                 new_dist = len_manhattan_v2v2(mval_fl, screen_loc);
 276                         }
 277                         else {
 278                                 new_dist = TRANSFORM_DIST_MAX_PX;
 279                         }
 280
 281                         /* 10% threshold if edge is closer but a bit further
 282                          * this takes care of series of connected edges a bit slanted w.r.t the viewport
 283                          * otherwise, it would stick to the verts of the closest edge and not slide along merrily
 284                          * */
 285                         if (new_dist <= *dist_px && new_depth < *ray_depth * 1.001f) {
 286                                 float n1[3], n2[3];
 287
 288                                 *ray_depth = new_depth;
 289                                 retval = true;
 290
 291                                 sub_v3_v3v3(edge_loc, v1co, v2co);
 292                                 sub_v3_v3v3(vec, intersect, v2co);
 293
 294                                 mul = dot_v3v3(vec, edge_loc) / dot_v3v3(edge_loc, edge_loc);
 295
 296                                 if (r_no) {
 297                                         normal_short_to_float_v3(n1, v1no);
 298                                         normal_short_to_float_v3(n2, v2no);
 299                                         interp_v3_v3v3(r_no, n2, n1, mul);
 300                                         mul_m3_v3(timat, r_no);
 301                                         normalize_v3(r_no);
 302                                 }
 303
 304                                 copy_v3_v3(r_loc, location);
 305
 306                                 *dist_px = new_dist;
 307                         }
 308                 }
 309         }
 310
 311         return retval;
 312 }
 313
 314 static bool snapVertex(
 315         ARegion *ar, const float vco[3], const float vno[3],
 316         float obmat[4][4], float timat[3][3], const float mval_fl[2], float *dist_px,
 317         const float ray_start[3], const float ray_start_local[3], const float ray_normal_local[3], float *ray_depth,
 318         float r_loc[3], float r_no[3])
 319 {
 320         bool retval = false;
 321         float dvec[3];
 322
 323         sub_v3_v3v3(dvec, vco, ray_start_local);
 324
 325         if (dot_v3v3(ray_normal_local, dvec) > 0) {
 326                 float location[3];
 327                 float new_depth;
 328                 float screen_loc[2];
 329                 float new_dist;
 330
 331                 copy_v3_v3(location, vco);
 332
 333                 mul_m4_v3(obmat, location);
 334
 335                 new_depth = len_v3v3(location, ray_start);
 336
 337                 if (ED_view3d_project_float_global(ar, location, screen_loc, V3D_PROJ_TEST_NOP) == V3D_PROJ_RET_OK) {
 338                         new_dist = len_manhattan_v2v2(mval_fl, screen_loc);
 339                 }
 340                 else {
 341                         new_dist = TRANSFORM_DIST_MAX_PX;
 342                 }
 343
 344
 345                 if (new_dist <= *dist_px && new_depth < *ray_depth) {
 346                         *ray_depth = new_depth;
 347                         retval = true;
 348
 349                         copy_v3_v3(r_loc, location);
 350
 351                         if (r_no) {
 352                                 copy_v3_v3(r_no, vno);
 353                                 mul_m3_v3(timat, r_no);
 354                                 normalize_v3(r_no);
 355                         }
 356
 357                         *dist_px = new_dist;
 358                 }
 359         }
 360
 361         return retval;
 362 }
 363
 364 static bool snapArmature(
 365         ARegion *ar, Object *ob, bArmature *arm, float obmat[4][4],
 366         const float mval[2], float *dist_px, const short snap_to,
 367         const float ray_start[3], const float ray_normal[3], float *ray_depth,
 368         float r_loc[3], float *UNUSED(r_no))
 369 {
 370         float imat[4][4];
 371         float ray_start_local[3], ray_normal_local[3];
 372         bool retval = false;
 373
 374         invert_m4_m4(imat, obmat);
 375
 376         mul_v3_m4v3(ray_start_local, imat, ray_start);
 377         mul_v3_mat3_m4v3(ray_normal_local, imat, ray_normal);
 378
 379         if (arm->edbo) {
 380                 EditBone *eBone;
 381
 382                 for (eBone = arm->edbo->first; eBone; eBone = eBone->next) {
 383                         if (eBone->layer & arm->layer) {
 384                                 /* skip hidden or moving (selected) bones */
 385                                 if ((eBone->flag & (BONE_HIDDEN_A | BONE_ROOTSEL | BONE_TIPSEL)) == 0) {
 386                                         switch (snap_to) {
 387                                                 case SCE_SNAP_MODE_VERTEX:
 388                                                         retval |= snapVertex(
 389                                                                 ar, eBone->head, NULL, obmat, NULL, mval, dist_px,
 390                                                                 ray_start, ray_start_local, ray_normal_local, ray_depth,
 391                                                                 r_loc, NULL);
 392                                                         retval |= snapVertex(
 393                                                                 ar, eBone->tail, NULL, obmat, NULL, mval, dist_px,
 394                                                                 ray_start, ray_start_local, ray_normal_local, ray_depth,
 395                                                                 r_loc, NULL);
 396                                                         break;
 397                                                 case SCE_SNAP_MODE_EDGE:
 398                                                         retval |= snapEdge(
 399                                                                 ar, eBone->head, NULL, eBone->tail, NULL,
 400                                                                 obmat, NULL, mval, dist_px,
 401                                                                 ray_start, ray_start_local, ray_normal_local,
 402                                                                 ray_depth, r_loc, NULL);
 403                                                         break;
 404                                         }
 405                                 }
 406                         }
 407                 }
 408         }
 409         else if (ob->pose && ob->pose->chanbase.first) {
 410                 bPoseChannel *pchan;
 411                 Bone *bone;
 412
 413                 for (pchan = ob->pose->chanbase.first; pchan; pchan = pchan->next) {
 414                         bone = pchan->bone;
 415                         /* skip hidden bones */
 416                         if (bone && !(bone->flag & (BONE_HIDDEN_P | BONE_HIDDEN_PG))) {
 417                                 const float *head_vec = pchan->pose_head;
 418                                 const float *tail_vec = pchan->pose_tail;
 419
 420                                 switch (snap_to) {
 421                                         case SCE_SNAP_MODE_VERTEX:
 422                                                 retval |= snapVertex(
 423                                                         ar, head_vec, NULL, obmat, NULL, mval, dist_px,
 424                                                         ray_start, ray_start_local, ray_normal_local,
 425                                                         ray_depth, r_loc, NULL);
 426                                                 retval |= snapVertex(
 427                                                         ar, tail_vec, NULL, obmat, NULL, mval, dist_px,
 428                                                         ray_start, ray_start_local, ray_normal_local, ray_depth,
 429                                                         r_loc, NULL);
 430                                                 break;
 431                                         case SCE_SNAP_MODE_EDGE:
 432                                                 retval |= snapEdge(
 433                                                         ar, head_vec, NULL, tail_vec, NULL,
 434                                                         obmat, NULL, mval, dist_px,
 435                                                         ray_start, ray_start_local, ray_normal_local,
 436                                                         ray_depth, r_loc, NULL);
 437                                                 break;
 438                                 }
 439                         }
 440                 }
 441         }
 442
 443         return retval;
 444 }
 445
 446 static bool snapCurve(
 447         ARegion *ar, Object *ob, Curve *cu, float obmat[4][4],
 448         const float mval[2], float *dist_px, const short snap_to,
 449         const float ray_start[3], const float ray_normal[3], float *ray_depth,
 450         float r_loc[3], float *UNUSED(r_no))
 451 {
 452         float imat[4][4];
 453         float ray_start_local[3], ray_normal_local[3];
 454         bool retval = false;
 455         int u;
 456
 457         Nurb *nu;
 458
 459         /* only vertex snapping mode (eg control points and handles) supported for now) */
 460         if (snap_to != SCE_SNAP_MODE_VERTEX) {
 461                 return retval;
 462         }
 463
 464         invert_m4_m4(imat, obmat);
 465
 466         copy_v3_v3(ray_start_local, ray_start);
 467         copy_v3_v3(ray_normal_local, ray_normal);
 468
 469         mul_m4_v3(imat, ray_start_local);
 470         mul_mat3_m4_v3(imat, ray_normal_local);
 471
 472         for (nu = (ob->mode == OB_MODE_EDIT ? cu->editnurb->nurbs.first : cu->nurb.first); nu; nu = nu->next) {
 473                 for (u = 0; u < nu->pntsu; u++) {
 474                         switch (snap_to) {
 475                                 case SCE_SNAP_MODE_VERTEX:
 476                                 {
 477                                         if (ob->mode == OB_MODE_EDIT) {
 478                                                 if (nu->bezt) {
 479                                                         /* don't snap to selected (moving) or hidden */
 480                                                         if (nu->bezt[u].f2 & SELECT || nu->bezt[u].hide != 0) {
 481                                                                 break;
 482                                                         }
 483                                                         retval |= snapVertex(
 484                                                                 ar, nu->bezt[u].vec[1], NULL, obmat, NULL,  mval, dist_px,
 485                                                                 ray_start, ray_start_local, ray_normal_local, ray_depth,
 486                                                                 r_loc, NULL);
 487                                                         /* don't snap if handle is selected (moving), or if it is aligning to a moving handle */
 488                                                         if (!(nu->bezt[u].f1 & SELECT) &&
 489                                                             !(nu->bezt[u].h1 & HD_ALIGN && nu->bezt[u].f3 & SELECT))
 490                                                         {
 491                                                                 retval |= snapVertex(
 492                                                                         ar, nu->bezt[u].vec[0], NULL, obmat, NULL, mval, dist_px,
 493                                                                         ray_start, ray_start_local, ray_normal_local, ray_depth,
 494                                                                         r_loc, NULL);
 495                                                         }
 496                                                         if (!(nu->bezt[u].f3 & SELECT) &&
 497                                                             !(nu->bezt[u].h2 & HD_ALIGN && nu->bezt[u].f1 & SELECT))
 498                                                         {
 499                                                                 retval |= snapVertex(
 500                                                                         ar, nu->bezt[u].vec[2], NULL, obmat, NULL, mval, dist_px,
 501                                                                         ray_start, ray_start_local, ray_normal_local, ray_depth,
 502                                                                         r_loc, NULL);
 503                                                         }
 504                                                 }
 505                                                 else {
 506                                                         /* don't snap to selected (moving) or hidden */
 507                                                         if (nu->bp[u].f1 & SELECT || nu->bp[u].hide != 0) {
 508                                                                 break;
 509                                                         }
 510                                                         retval |= snapVertex(
 511                                                                 ar, nu->bp[u].vec, NULL, obmat, NULL, mval, dist_px,
 512                                                                 ray_start, ray_start_local, ray_normal_local, ray_depth,
 513                                                                 r_loc, NULL);
 514                                                 }
 515                                         }
 516                                         else {
 517                                                 /* curve is not visible outside editmode if nurb length less than two */
 518                                                 if (nu->pntsu > 1) {
 519                                                         if (nu->bezt) {
 520                                                                 retval |= snapVertex(
 521                                                                         ar, nu->bezt[u].vec[1], NULL, obmat, NULL, mval, dist_px,
 522                                                                         ray_start, ray_start_local, ray_normal_local, ray_depth,
 523                                                                         r_loc, NULL);
 524                                                         }
 525                                                         else {
 526                                                                 retval |= snapVertex(
 527                                                                         ar, nu->bp[u].vec, NULL, obmat, NULL, mval, dist_px,
 528                                                                         ray_start, ray_start_local, ray_normal_local, ray_depth,
 529                                                                         r_loc, NULL);
 530                                                         }
 531                                                 }
 532                                         }
 533                                         break;
 534                                 }
 535                                 default:
 536                                         break;
 537                         }
 538                 }
 539         }
 540         return retval;
 541 }
 542
 543 /* may extend later (for now just snaps to empty center) */
 544 static bool snapEmpty(
 545         ARegion *ar, Object *ob, float obmat[4][4],
 546         const float mval[2], float *dist_px, const short snap_to,
 547         const float ray_start[3], const float ray_normal[3], float *ray_depth,
 548         float r_loc[3], float *UNUSED(r_no))
 549 {
 550         float imat[4][4];
 551         float ray_start_local[3], ray_normal_local[3];
 552         bool retval = false;
 553
 554         if (ob->transflag & OB_DUPLI) {
 555                 return retval;
 556         }
 557         /* for now only vertex supported */
 558         if (snap_to != SCE_SNAP_MODE_VERTEX) {
 559                 return retval;
 560         }
 561
 562         invert_m4_m4(imat, obmat);
 563
 564         mul_v3_m4v3(ray_start_local, imat, ray_start);
 565         mul_v3_mat3_m4v3(ray_normal_local, imat, ray_normal);
 566
 567         switch (snap_to) {
 568                 case SCE_SNAP_MODE_VERTEX:
 569                 {
 570                         const float zero_co[3] = {0.0f};
 571                         retval |= snapVertex(
 572                                 ar, zero_co, NULL, obmat, NULL, mval, dist_px,
 573                                 ray_start, ray_start_local, ray_normal_local, ray_depth,
 574                                 r_loc, NULL);
 575                         break;
 576                 }
 577                 default:
 578                         break;
 579         }
 580
 581         return retval;
 582 }
 583
 584 static bool snapCamera(
 585         ARegion *ar, Scene *scene, Object *object, float obmat[4][4],
 586         const float mval[2], float *dist_px, const short snap_to,
 587         const float ray_start[3], const float ray_normal[3], float *ray_depth,
 588         float r_loc[3], float *UNUSED(r_no))
 589 {
 590         float orig_camera_mat[4][4], orig_camera_imat[4][4], imat[4][4];
 591         bool retval = false;
 592         MovieClip *clip = BKE_object_movieclip_get(scene, object, false);
 593         MovieTracking *tracking;
 594         float ray_start_local[3], ray_normal_local[3];
 595
 596         if (clip == NULL) {
 597                 return retval;
 598         }
 599         if (object->transflag & OB_DUPLI) {
 600                 return retval;
 601         }
 602
 603         tracking = &clip->tracking;
 604
 605         BKE_tracking_get_camera_object_matrix(scene, object, orig_camera_mat);
 606
 607         invert_m4_m4(orig_camera_imat, orig_camera_mat);
 608         invert_m4_m4(imat, obmat);
 609
 610         switch (snap_to) {
 611                 case SCE_SNAP_MODE_VERTEX:
 612                 {
 613                         MovieTrackingObject *tracking_object;
 614
 615                         for (tracking_object = tracking->objects.first;
 616                              tracking_object;
 617                              tracking_object = tracking_object->next)
 618                         {
 619                                 ListBase *tracksbase = BKE_tracking_object_get_tracks(tracking, tracking_object);
 620                                 MovieTrackingTrack *track;
 621                                 float reconstructed_camera_mat[4][4],
 622                                       reconstructed_camera_imat[4][4];
 623                                 float (*vertex_obmat)[4];
 624
 625                                 copy_v3_v3(ray_start_local, ray_start);
 626                                 copy_v3_v3(ray_normal_local, ray_normal);
 627
 628                                 if ((tracking_object->flag & TRACKING_OBJECT_CAMERA) == 0) {
 629                                         BKE_tracking_camera_get_reconstructed_interpolate(tracking, tracking_object,
 630                                                                                           CFRA, reconstructed_camera_mat);
 631
 632                                         invert_m4_m4(reconstructed_camera_imat, reconstructed_camera_mat);
 633                                 }
 634
 635                                 for (track = tracksbase->first; track; track = track->next) {
 636                                         float bundle_pos[3];
 637
 638                                         if ((track->flag & TRACK_HAS_BUNDLE) == 0) {
 639                                                 continue;
 640                                         }
 641
 642                                         copy_v3_v3(bundle_pos, track->bundle_pos);
 643                                         if (tracking_object->flag & TRACKING_OBJECT_CAMERA) {
 644                                                 mul_m4_v3(orig_camera_imat, ray_start_local);
 645                                                 mul_mat3_m4_v3(orig_camera_imat, ray_normal_local);
 646                                                 vertex_obmat = orig_camera_mat;
 647                                         }
 648                                         else {
 649                                                 mul_m4_v3(reconstructed_camera_imat, bundle_pos);
 650                                                 mul_m4_v3(imat, ray_start_local);
 651                                                 mul_mat3_m4_v3(imat, ray_normal_local);
 652                                                 vertex_obmat = obmat;
 653                                         }
 654
 655                                         retval |= snapVertex(
 656                                                 ar, bundle_pos, NULL, vertex_obmat, NULL, mval, dist_px,
 657                                                 ray_start, ray_start_local, ray_normal_local, ray_depth,
 658                                                 r_loc, NULL);
 659                                 }
 660                         }
 661
 662                         break;
 663                 }
 664                 default:
 665                         break;
 666         }
 667
 668         return retval;
 669 }
 670
 671 static int dm_looptri_to_poly_index(DerivedMesh *dm, const MLoopTri *lt)
 672 {
 673         const int *index_mp_to_orig = dm->getPolyDataArray(dm, CD_ORIGINDEX);
 674         return index_mp_to_orig ? index_mp_to_orig[lt->poly] : lt->poly;
 675 }
 676
 677 static bool snapDerivedMesh(
 678         SnapObjectContext *sctx,
 679         Object *ob, DerivedMesh *dm, float obmat[4][4],
 680         const float mval[2], float *dist_px, const short snap_to, bool do_bb,
 681         const float ray_start[3], const float ray_normal[3], const float ray_origin[3],
 682         float *ray_depth, unsigned int ob_index,
 683         float r_loc[3], float r_no[3], int *r_index,
 684         ListBase *r_hit_list)
 685 {
 686         ARegion *ar = sctx->v3d_data.ar;
 687         bool retval = false;
 688
 689         if (snap_to == SCE_SNAP_MODE_FACE) {
 690                 if (dm->getNumPolys(dm) == 0) {
 691                         return retval;
 692                 }
 693         }
 694         if (snap_to == SCE_SNAP_MODE_EDGE) {
 695                 if (dm->getNumEdges(dm) == 0) {
 696                         return retval;
 697                 }
 698         }
 699         else {
 700                 if (dm->getNumVerts(dm) == 0) {
 701                         return retval;
 702                 }
 703         }
 704
 705         {
 706                 const bool do_ray_start_correction = (
 707                          ELEM(snap_to, SCE_SNAP_MODE_FACE, SCE_SNAP_MODE_VERTEX) &&
 708                          (sctx->use_v3d && !((RegionView3D *)sctx->v3d_data.ar->regiondata)->is_persp));
 709                 bool need_ray_start_correction_init = do_ray_start_correction;
 710
 711                 float imat[4][4];
 712                 float timat[3][3]; /* transpose inverse matrix for normals */
 713                 float ray_start_local[3], ray_normal_local[3];
 714                 float local_scale, local_depth, len_diff;
 715
 716                 invert_m4_m4(imat, obmat);
 717                 transpose_m3_m4(timat, imat);
 718
 719                 copy_v3_v3(ray_start_local, ray_start);
 720                 copy_v3_v3(ray_normal_local, ray_normal);
 721
 722                 mul_m4_v3(imat, ray_start_local);
 723                 mul_mat3_m4_v3(imat, ray_normal_local);
 724
 725                 /* local scale in normal direction */
 726                 local_scale = normalize_v3(ray_normal_local);
 727                 local_depth = *ray_depth;
 728                 if (local_depth != BVH_RAYCAST_DIST_MAX) {
 729                         local_depth *= local_scale;
 730                 }
 731
 732                 if (do_bb) {
 733                         BoundBox *bb = BKE_object_boundbox_get(ob);
 734
 735                         if (bb) {
 736                                 BoundBox bb_temp;
 737
 738                                 /* We cannot aford a bbox with some null dimension, which may happen in some cases...
 739                                  * Threshold is rather high, but seems to be needed to get good behavior, see T46099. */
 740                                 bb = BKE_boundbox_ensure_minimum_dimensions(bb, &bb_temp, 1e-1f);
 741
 742                                 /* Exact value here is arbitrary (ideally we would scale in pixel-space based on 'dist_px'),
 743                                  * scale up so we can snap against verts & edges on the boundbox, see T46816. */
 744                                 if (ELEM(snap_to, SCE_SNAP_MODE_VERTEX, SCE_SNAP_MODE_EDGE)) {
 745                                         BKE_boundbox_scale(&bb_temp, bb, 1.0f + 1e-1f);
 746                                         bb = &bb_temp;
 747                                 }
 748
 749                                 /* was local_depth, see: T47838 */
 750                                 len_diff = BVH_RAYCAST_DIST_MAX;
 751
 752                                 if (!BKE_boundbox_ray_hit_check(bb, ray_start_local, ray_normal_local, &len_diff)) {
 753                                         return retval;
 754                                 }
 755                                 need_ray_start_correction_init = false;
 756                         }
 757                 }
 758
 759                 SnapObjectData_Mesh *sod = NULL;
 760                 BVHTreeFromMesh *treedata = NULL, treedata_stack;
 761
 762                 if (sctx->flag & SNAP_OBJECT_USE_CACHE) {
 763                         void **sod_p;
 764                         if (BLI_ghash_ensure_p(sctx->cache.object_map, ob, &sod_p)) {
 765                                 sod = *sod_p;
 766                         }
 767                         else {
 768                                 sod = *sod_p = BLI_memarena_calloc(sctx->cache.mem_arena, sizeof(*sod));
 769                                 sod->sd.type = SNAP_MESH;
 770                         }
 771
 772                         int tree_index = -1;
 773                         switch (snap_to) {
 774                                 case SCE_SNAP_MODE_FACE:
 775                                         tree_index = 1;
 776                                         break;
 777                                 case SCE_SNAP_MODE_VERTEX:
 778                                         tree_index = 0;
 779                                         break;
 780                         }
 781                         if (tree_index != -1) {
 782                                 if (sod->bvh_trees[tree_index] == NULL) {
 783                                         sod->bvh_trees[tree_index] = BLI_memarena_calloc(sctx->cache.mem_arena, sizeof(*treedata));
 784                                 }
 785                                 treedata = sod->bvh_trees[tree_index];
 786
 787                                 /* the tree is owned by the DM and may have been freed since we last used! */
 788                                 if (treedata && treedata->tree) {
 789                                         if (treedata->cached && !bvhcache_has_tree(dm->bvhCache, treedata->tree)) {
 790                                                 free_bvhtree_from_mesh(treedata);
 791                                         }
 792                                 }
 793                         }
 794                 }
 795                 else {
 796                         if (ELEM(snap_to, SCE_SNAP_MODE_FACE, SCE_SNAP_MODE_VERTEX)) {
 797                                 treedata = &treedata_stack;
 798                                 memset(treedata, 0, sizeof(*treedata));
 799                         }
 800                 }
 801
 802                 if (treedata && treedata->tree == NULL) {
 803                         switch (snap_to) {
 804                                 case SCE_SNAP_MODE_FACE:
 805                                         bvhtree_from_mesh_looptri(treedata, dm, 0.0f, 4, 6);
 806                                         break;
 807                                 case SCE_SNAP_MODE_VERTEX:
 808                                         bvhtree_from_mesh_verts(treedata, dm, 0.0f, 2, 6);
 809                                         break;
 810                         }
 811                 }
 812
 813                 if (need_ray_start_correction_init) {
 814                         /* We *need* a reasonably valid len_diff in this case.
 815                          * Use BHVTree to find the closest face from ray_start_local.
 816                          */
 817                         if (treedata && treedata->tree != NULL) {
 818                                 BVHTreeNearest nearest;
 819                                 nearest.index = -1;
 820                                 nearest.dist_sq = FLT_MAX;
 821                                 /* Compute and store result. */
 822                                 BLI_bvhtree_find_nearest(
 823                                             treedata->tree, ray_start_local, &nearest, treedata->nearest_callback, treedata);
 824                                 if (nearest.index != -1) {
 825                                         len_diff = sqrtf(nearest.dist_sq);
 826                                 }
 827                         }
 828                 }
 829                 /* Only use closer ray_start in case of ortho view! In perspective one, ray_start may already
 830                  * been *inside* boundbox, leading to snap failures (see T38409).
 831                  * Note also ar might be null (see T38435), in this case we assume ray_start is ok!
 832                  */
 833                 if (do_ray_start_correction) {
 834                         float ray_org_local[3];
 835
 836                         copy_v3_v3(ray_org_local, ray_origin);
 837                         mul_m4_v3(imat, ray_org_local);
 838
 839                         /* We pass a temp ray_start, set from object's boundbox, to avoid precision issues with very far
 840                          * away ray_start values (as returned in case of ortho view3d), see T38358.
 841                          */
 842                         len_diff -= local_scale;  /* make temp start point a bit away from bbox hit point. */
 843                         madd_v3_v3v3fl(ray_start_local, ray_org_local, ray_normal_local,
 844                                        len_diff - len_v3v3(ray_start_local, ray_org_local));
 845                         local_depth -= len_diff;
 846                 }
 847                 else {
 848                         len_diff = 0.0f;
 849                 }
 850
 851                 switch (snap_to) {
 852                         case SCE_SNAP_MODE_FACE:
 853                         {
 854                                 if (r_hit_list) {
 855                                         struct RayCastAll_Data data;
 856
 857                                         data.bvhdata = treedata;
 858                                         data.raycast_callback = treedata->raycast_callback;
 859                                         data.obmat = obmat;
 860                                         data.timat = timat;
 861                                         data.len_diff = len_diff;
 862                                         data.local_scale = local_scale;
 863                                         data.ob = ob;
 864                                         data.ob_uuid = ob_index,
 865                                         data.dm = dm;
 866                                         data.hit_list = r_hit_list;
 867                                         data.retval = retval;
 868
 869                                         BLI_bvhtree_ray_cast_all(
 870                                                 treedata->tree, ray_start_local, ray_normal_local, 0.0f,
 871                                                 *ray_depth, raycast_all_cb, &data);
 872
 873                                         retval = data.retval;
 874                                 }
 875                                 else {
 876                                         BVHTreeRayHit hit;
 877
 878                                         hit.index = -1;
 879                                         hit.dist = local_depth;
 880
 881                                         if (treedata->tree &&
 882                                             BLI_bvhtree_ray_cast(
 883                                                 treedata->tree, ray_start_local, ray_normal_local, 0.0f,
 884                                                 &hit, treedata->raycast_callback, treedata) != -1)
 885                                         {
 886                                                 hit.dist += len_diff;
 887                                                 hit.dist /= local_scale;
 888                                                 if (hit.dist <= *ray_depth) {
 889                                                         *ray_depth = hit.dist;
 890                                                         copy_v3_v3(r_loc, hit.co);
 891                                                         copy_v3_v3(r_no, hit.no);
 892
 893                                                         /* back to worldspace */
 894                                                         mul_m4_v3(obmat, r_loc);
 895                                                         mul_m3_v3(timat, r_no);
 896                                                         normalize_v3(r_no);
 897
 898                                                         retval = true;
 899
 900                                                         if (r_index) {
 901                                                                 *r_index = dm_looptri_to_poly_index(dm, &treedata->looptri[hit.index]);
 902                                                         }
 903                                                 }
 904                                         }
 905                                 }
 906                                 break;
 907                         }
 908                         case SCE_SNAP_MODE_VERTEX:
 909                         {
 910                                 BVHTreeNearest nearest;
 911
 912                                 nearest.index = -1;
 913                                 nearest.dist_sq = local_depth * local_depth;
 914                                 if (treedata->tree &&
 915                                     BLI_bvhtree_find_nearest_to_ray(
 916                                         treedata->tree, ray_start_local, ray_normal_local,
 917                                         &nearest, NULL, NULL) != -1)
 918                                 {
 919                                         const MVert *v = &treedata->vert[nearest.index];
 920                                         float vno[3];
 921                                         normal_short_to_float_v3(vno, v->no);
 922                                         retval = snapVertex(
 923                                                      ar, v->co, vno, obmat, timat, mval, dist_px,
 924                                                      ray_start, ray_start_local, ray_normal_local, ray_depth,
 925                                                      r_loc, r_no);
 926                                 }
 927                                 break;
 928                         }
 929                         case SCE_SNAP_MODE_EDGE:
 930                         {
 931                                 MVert *verts = dm->getVertArray(dm);
 932                                 MEdge *edges = dm->getEdgeArray(dm);
 933                                 int totedge = dm->getNumEdges(dm);
 934
 935                                 for (int i = 0; i < totedge; i++) {
 936                                         MEdge *e = edges + i;
 937                                         retval |= snapEdge(
 938                                                 ar, verts[e->v1].co, verts[e->v1].no, verts[e->v2].co, verts[e->v2].no,
 939                                                 obmat, timat, mval, dist_px,
 940                                                 ray_start, ray_start_local, ray_normal_local, ray_depth,
 941                                                 r_loc, r_no);
 942                                 }
 943
 944                                 break;
 945                         }
 946                 }
 947
 948                 if ((sctx->flag & SNAP_OBJECT_USE_CACHE) == 0) {
 949                         if (treedata) {
 950                                 free_bvhtree_from_mesh(treedata);
 951                         }
 952                 }
 953         }
 954
 955         return retval;
 956 }
 957
 958
 959 static bool snapEditMesh(
 960         SnapObjectContext *sctx,
 961         Object *ob, BMEditMesh *em, float obmat[4][4],
 962         const float mval[2], float *dist_px, const short snap_to,
 963         const float ray_start[3], const float ray_normal[3], const float ray_origin[3],
 964         float *ray_depth, const unsigned int ob_index,
 965         float r_loc[3], float r_no[3], int *r_index,
 966         ListBase *r_hit_list)
 967 {
 968         ARegion *ar = sctx->v3d_data.ar;
 969         bool retval = false;
 970
 971         if (snap_to == SCE_SNAP_MODE_FACE) {
 972                 if (em->bm->totface == 0) {
 973                         return retval;
 974                 }
 975         }
 976         if (snap_to == SCE_SNAP_MODE_EDGE) {
 977                 if (em->bm->totedge == 0) {
 978                         return retval;
 979                 }
 980         }
 981         else {
 982                 if (em->bm->totvert == 0) {
 983                         return retval;
 984                 }
 985         }
 986
 987         {
 988                 const bool do_ray_start_correction = (
 989                         ELEM(snap_to, SCE_SNAP_MODE_FACE, SCE_SNAP_MODE_VERTEX) &&
 990                         (sctx->use_v3d && !((RegionView3D *)sctx->v3d_data.ar->regiondata)->is_persp));
 991
 992                 float imat[4][4];
 993                 float timat[3][3]; /* transpose inverse matrix for normals */
 994                 float ray_start_local[3], ray_normal_local[3];
 995                 float local_scale, local_depth;
 996
 997                 invert_m4_m4(imat, obmat);
 998                 transpose_m3_m4(timat, imat);
 999
1000                 copy_v3_v3(ray_start_local, ray_start);
1001                 copy_v3_v3(ray_normal_local, ray_normal);
1002
1003                 mul_m4_v3(imat, ray_start_local);
1004                 mul_mat3_m4_v3(imat, ray_normal_local);
1005
1006                 /* local scale in normal direction */
1007                 local_scale = normalize_v3(ray_normal_local);
1008                 local_depth = *ray_depth;
1009                 if (local_depth != BVH_RAYCAST_DIST_MAX) {
1010                         local_depth *= local_scale;
1011                 }
1012
1013                 SnapObjectData_EditMesh *sod = NULL;
1014
1015                 BVHTreeFromEditMesh *treedata = NULL, treedata_stack;
1016
1017                 if (sctx->flag & SNAP_OBJECT_USE_CACHE) {
1018                         void **sod_p;
1019                         if (BLI_ghash_ensure_p(sctx->cache.object_map, ob, &sod_p)) {
1020                                 sod = *sod_p;
1021                         }
1022                         else {
1023                                 sod = *sod_p = BLI_memarena_calloc(sctx->cache.mem_arena, sizeof(*sod));
1024                                 sod->sd.type = SNAP_EDIT_MESH;
1025                         }
1026
1027                         int tree_index = -1;
1028                         switch (snap_to) {
1029                                 case SCE_SNAP_MODE_FACE:
1030                                         tree_index = 1;
1031                                         break;
1032                                 case SCE_SNAP_MODE_VERTEX:
1033                                         tree_index = 0;
1034                                         break;
1035                         }
1036                         if (tree_index != -1) {
1037                                 if (sod->bvh_trees[tree_index] == NULL) {
1038                                         sod->bvh_trees[tree_index] = BLI_memarena_calloc(sctx->cache.mem_arena, sizeof(*treedata));
1039                                 }
1040                                 treedata = sod->bvh_trees[tree_index];
1041                         }
1042                 }
1043                 else {
1044                         if (ELEM(snap_to, SCE_SNAP_MODE_FACE, SCE_SNAP_MODE_VERTEX)) {
1045                                 treedata = &treedata_stack;
1046                                 memset(treedata, 0, sizeof(*treedata));
1047                         }
1048                 }
1049
1050                 if (treedata && treedata->tree == NULL) {
1051                         switch (snap_to) {
1052                                 case SCE_SNAP_MODE_FACE:
1053                                 {
1054                                         BLI_bitmap *looptri_mask = NULL;
1055                                         int looptri_num_active = -1;
1056                                         if (sctx->callbacks.edit_mesh.test_face_fn) {
1057                                                 looptri_mask = BLI_BITMAP_NEW(em->tottri, __func__);
1058                                                 looptri_num_active = BM_iter_mesh_bitmap_from_filter_tessface(
1059                                                         em->bm, looptri_mask,
1060                                                         sctx->callbacks.edit_mesh.test_face_fn, sctx->callbacks.edit_mesh.user_data);
1061                                         }
1062                                         bvhtree_from_editmesh_looptri_ex(treedata, em, looptri_mask, looptri_num_active, 0.0f, 4, 6);
1063                                         if (looptri_mask) {
1064                                                 MEM_freeN(looptri_mask);
1065                                         }
1066                                         break;
1067                                 }
1068                                 case SCE_SNAP_MODE_VERTEX:
1069                                 {
1070                                         BLI_bitmap *verts_mask = NULL;
1071                                         int verts_num_active = -1;
1072                                         if (sctx->callbacks.edit_mesh.test_vert_fn) {
1073                                                 verts_mask = BLI_BITMAP_NEW(em->bm->totvert, __func__);
1074                                                 verts_num_active = BM_iter_mesh_bitmap_from_filter(
1075                                                         BM_VERTS_OF_MESH, em->bm, verts_mask,
1076                                                         (bool (*)(BMElem *, void *))sctx->callbacks.edit_mesh.test_vert_fn,
1077                                                         sctx->callbacks.edit_mesh.user_data);
1078                                         }
1079                                         bvhtree_from_editmesh_verts_ex(treedata, em, verts_mask, verts_num_active, 0.0f, 2, 6);
1080                                         if (verts_mask) {
1081                                                 MEM_freeN(verts_mask);
1082                                         }
1083                                         break;
1084                                 }
1085                         }
1086                 }
1087
1088                 /* Only use closer ray_start in case of ortho view! In perspective one, ray_start may already
1089                  * been *inside* boundbox, leading to snap failures (see T38409).
1090                  * Note also ar might be null (see T38435), in this case we assume ray_start is ok!
1091                  */
1092                 float len_diff = 0.0f;
1093                 if (do_ray_start_correction) {
1094                         /* We *need* a reasonably valid len_diff in this case.
1095                          * Use BHVTree to find the closest face from ray_start_local.
1096                          */
1097                         if (treedata && treedata->tree != NULL) {
1098                                 BVHTreeNearest nearest;
1099                                 nearest.index = -1;
1100                                 nearest.dist_sq = FLT_MAX;
1101                                 /* Compute and store result. */
1102                                 if (BLI_bvhtree_find_nearest(
1103                                         treedata->tree, ray_start_local, &nearest, treedata->nearest_callback, treedata) != -1)
1104                                 {
1105                                         len_diff = sqrtf(nearest.dist_sq);
1106                                         float ray_org_local[3];
1107
1108                                         copy_v3_v3(ray_org_local, ray_origin);
1109                                         mul_m4_v3(imat, ray_org_local);
1110
1111                                         /* We pass a temp ray_start, set from object's boundbox, to avoid precision issues with very far
1112                                         * away ray_start values (as returned in case of ortho view3d), see T38358.
1113                                         */
1114                                         len_diff -= local_scale;  /* make temp start point a bit away from bbox hit point. */
1115                                         madd_v3_v3v3fl(ray_start_local, ray_org_local, ray_normal_local,
1116                                                        len_diff - len_v3v3(ray_start_local, ray_org_local));
1117                                         local_depth -= len_diff;
1118                                 }
1119                         }
1120                 }
1121
1122                 switch (snap_to) {
1123                         case SCE_SNAP_MODE_FACE:
1124                         {
1125                                 if (r_hit_list) {
1126                                         struct RayCastAll_Data data;
1127
1128                                         data.bvhdata = treedata;
1129                                         data.raycast_callback = treedata->raycast_callback;
1130                                         data.obmat = obmat;
1131                                         data.timat = timat;
1132                                         data.len_diff = len_diff;
1133                                         data.local_scale = local_scale;
1134                                         data.ob = ob;
1135                                         data.ob_uuid = ob_index;
1136                                         data.dm = NULL;
1137                                         data.hit_list = r_hit_list;
1138                                         data.retval = retval;
1139
1140                                         BLI_bvhtree_ray_cast_all(
1141                                                 treedata->tree, ray_start_local, ray_normal_local, 0.0f,
1142                                                 *ray_depth, raycast_all_cb, &data);
1143
1144                                         retval = data.retval;
1145                                 }
1146                                 else {
1147                                         BVHTreeRayHit hit;
1148
1149                                         hit.index = -1;
1150                                         hit.dist = local_depth;
1151
1152                                         if (treedata->tree &&
1153                                             BLI_bvhtree_ray_cast(
1154                                                 treedata->tree, ray_start_local, ray_normal_local, 0.0f,
1155                                                 &hit, treedata->raycast_callback, treedata) != -1)
1156                                         {
1157                                                 hit.dist += len_diff;
1158                                                 hit.dist /= local_scale;
1159                                                 if (hit.dist <= *ray_depth) {
1160                                                         *ray_depth = hit.dist;
1161                                                         copy_v3_v3(r_loc, hit.co);
1162                                                         copy_v3_v3(r_no, hit.no);
1163
1164                                                         /* back to worldspace */
1165                                                         mul_m4_v3(obmat, r_loc);
1166                                                         mul_m3_v3(timat, r_no);
1167                                                         normalize_v3(r_no);
1168
1169                                                         retval = true;
1170
1171                                                         if (r_index) {
1172                                                                 *r_index = hit.index;
1173                                                         }
1174                                                 }
1175                                         }
1176                                 }
1177                                 break;
1178                         }
1179                         case SCE_SNAP_MODE_VERTEX:
1180                         {
1181                                 BVHTreeNearest nearest;
1182
1183                                 nearest.index = -1;
1184                                 nearest.dist_sq = local_depth * local_depth;
1185                                 if (treedata->tree &&
1186                                     BLI_bvhtree_find_nearest_to_ray(
1187                                             treedata->tree, ray_start_local, ray_normal_local,
1188                                             &nearest, NULL, NULL) != -1)
1189                                 {
1190                                         const BMVert *v = BM_vert_at_index(em->bm, nearest.index);
1191                                         retval = snapVertex(
1192                                                 ar, v->co, v->no, obmat, timat, mval, dist_px,
1193                                                 ray_start, ray_start_local, ray_normal_local, ray_depth,
1194                                                 r_loc, r_no);
1195                                 }
1196                                 break;
1197                         }
1198                         case SCE_SNAP_MODE_EDGE:
1199                         {
1200                                 BM_mesh_elem_table_ensure(em->bm, BM_EDGE);
1201                                 int totedge = em->bm->totedge;
1202                                 for (int i = 0; i < totedge; i++) {
1203                                         BMEdge *eed = BM_edge_at_index(em->bm, i);
1204
1205                                         if (!BM_elem_flag_test(eed, BM_ELEM_HIDDEN) &&
1206                                             !BM_elem_flag_test(eed->v1, BM_ELEM_SELECT) &&
1207                                             !BM_elem_flag_test(eed->v2, BM_ELEM_SELECT))
1208                                         {
1209                                                 short v1no[3], v2no[3];
1210                                                 normal_float_to_short_v3(v1no, eed->v1->no);
1211                                                 normal_float_to_short_v3(v2no, eed->v2->no);
1212                                                 retval |= snapEdge(
1213                                                         ar, eed->v1->co, v1no, eed->v2->co, v2no,
1214                                                         obmat, timat, mval, dist_px,
1215                                                         ray_start, ray_start_local, ray_normal_local, ray_depth,
1216                                                         r_loc, r_no);
1217                                         }
1218                                 }
1219
1220                                 break;
1221                         }
1222                 }
1223
1224                 if ((sctx->flag & SNAP_OBJECT_USE_CACHE) == 0) {
1225                         if (treedata) {
1226                                 free_bvhtree_from_editmesh(treedata);
1227                         }
1228                 }
1229         }
1230
1231         return retval;
1232 }
1233
1234 static bool snapObject(
1235         SnapObjectContext *sctx,
1236         Object *ob, float obmat[4][4], bool use_obedit, const short snap_to,
1237         const float mval[2], float *dist_px, const unsigned int ob_index,
1238         const float ray_start[3], const float ray_normal[3], const float ray_origin[3],
1239         float *ray_depth,
1240         /* return args */
1241         float r_loc[3], float r_no[3], int *r_index,
1242         Object **r_ob, float r_obmat[4][4],
1243         ListBase *r_hit_list)
1244 {
1245         ARegion *ar = sctx->v3d_data.ar;
1246         bool retval = false;
1247
1248         if (ob->type == OB_MESH) {
1249                 BMEditMesh *em;
1250
1251                 if (use_obedit) {
1252                         em = BKE_editmesh_from_object(ob);
1253                         retval = snapEditMesh(
1254                                 sctx, ob, em, obmat, mval, dist_px, snap_to,
1255                                 ray_start, ray_normal, ray_origin,
1256                                 ray_depth, ob_index,
1257                                 r_loc, r_no, r_index,
1258                                 r_hit_list);
1259                 }
1260                 else {
1261                         /* in this case we want the mesh from the editmesh, avoids stale data. see: T45978.
1262                          * still set the 'em' to NULL, since we only want the 'dm'. */
1263                         DerivedMesh *dm;
1264                         em = BKE_editmesh_from_object(ob);
1265                         if (em) {
1266                                 editbmesh_get_derived_cage_and_final(sctx->scene, ob, em, CD_MASK_BAREMESH, &dm);
1267                         }
1268                         else {
1269                                 dm = mesh_get_derived_final(sctx->scene, ob, CD_MASK_BAREMESH);
1270                         }
1271                         retval = snapDerivedMesh(
1272                                 sctx, ob, dm, obmat, mval, dist_px, snap_to, true,
1273                                 ray_start, ray_normal, ray_origin,
1274                                 ray_depth, ob_index,
1275                                 r_loc, r_no, r_index, r_hit_list);
1276
1277                         dm->release(dm);
1278                 }
1279         }
1280         else if (ob->type == OB_ARMATURE) {
1281                 retval = snapArmature(
1282                         ar, ob, ob->data, obmat, mval, dist_px, snap_to,
1283                         ray_start, ray_normal, ray_depth,
1284                         r_loc, r_no);
1285         }
1286         else if (ob->type == OB_CURVE) {
1287                 retval = snapCurve(
1288                         ar, ob, ob->data, obmat, mval, dist_px, snap_to,
1289                         ray_start, ray_normal, ray_depth,
1290                         r_loc, r_no);
1291         }
1292         else if (ob->type == OB_EMPTY) {
1293                 retval = snapEmpty(
1294                         ar, ob, obmat, mval, dist_px, snap_to,
1295                         ray_start, ray_normal, ray_depth,
1296                         r_loc, r_no);
1297         }
1298         else if (ob->type == OB_CAMERA) {
1299                 retval = snapCamera(
1300                         ar, sctx->scene, ob, obmat, mval, dist_px, snap_to,
1301                         ray_start, ray_normal, ray_depth,
1302                         r_loc, r_no);
1303         }
1304
1305         if (retval) {
1306                 if (r_ob) {
1307                         *r_ob = ob;
1308                         copy_m4_m4(r_obmat, obmat);
1309                 }
1310         }
1311
1312         return retval;
1313 }
1314
1315 static bool snapObjectsRay(
1316         SnapObjectContext *sctx,
1317         const unsigned short snap_to, const SnapSelect snap_select,
1318         const bool use_object_edit_cage,
1319         const float mval[2], float *dist_px,
1320         const float ray_start[3], const float ray_normal[3], const float ray_origin[3], float *ray_depth,
1321         /* return args */
1322         float r_loc[3], float r_no[3], int *r_index,
1323         Object **r_ob, float r_obmat[4][4],
1324         ListBase *r_hit_list)
1325 {
1326         bool retval = false;
1327         unsigned int ob_index = 0;
1328         Object *obedit = use_object_edit_cage ? sctx->scene->obedit : NULL;
1329         Base *base_act = sctx->scene->basact;
1330
1331         bool ignore_object_selected = false, ignore_object_active = false;
1332         switch (snap_select) {
1333                 case SNAP_ALL:
1334                         break;
1335                 case SNAP_NOT_SELECTED:
1336                         ignore_object_selected = true;
1337                         break;
1338                 case SNAP_NOT_ACTIVE:
1339                         ignore_object_active = true;
1340                         break;
1341         }
1342         for (Base *base = sctx->scene->base.first; base != NULL; base = base->next) {
1343                 if ((BASE_VISIBLE_BGMODE(sctx->v3d_data.v3d, sctx->scene, base)) &&
1344                     (base->flag & (BA_HAS_RECALC_OB | BA_HAS_RECALC_DATA)) == 0 &&
1345
1346                     !((ignore_object_selected && (base->flag & (SELECT | BA_WAS_SEL))) ||
1347                       (ignore_object_active && base == base_act)))
1348                 {
1349                         Object *ob = base->object;
1350
1351                         if (ob->transflag & OB_DUPLI) {
1352                                 DupliObject *dupli_ob;
1353                                 ListBase *lb = object_duplilist(sctx->bmain->eval_ctx, sctx->scene, ob);
1354
1355                                 for (dupli_ob = lb->first; dupli_ob; dupli_ob = dupli_ob->next) {
1356                                         bool use_obedit_dupli = (obedit && dupli_ob->ob->data == obedit->data);
1357                                         Object *dupli_snap = (use_obedit_dupli) ? obedit : dupli_ob->ob;
1358
1359                                         retval |= snapObject(
1360                                                 sctx, dupli_snap, dupli_ob->mat, use_obedit_dupli, snap_to,
1361                                                 mval, dist_px, ob_index++,
1362                                                 ray_start, ray_normal, ray_origin, ray_depth,
1363                                                 r_loc, r_no, r_index, r_ob, r_obmat, r_hit_list);
1364                                 }
1365
1366                                 free_object_duplilist(lb);
1367                         }
1368
1369                         bool use_obedit = (obedit != NULL) && (ob->data == obedit->data);
1370                         Object *ob_snap = use_obedit ? obedit : ob;
1371
1372                         retval |= snapObject(
1373                                 sctx, ob_snap, ob->obmat, use_obedit, snap_to,
1374                                 mval, dist_px, ob_index++,
1375                                 ray_start, ray_normal, ray_origin, ray_depth,
1376                                 r_loc, r_no, r_index, r_ob, r_obmat, r_hit_list);
1377                 }
1378         }
1379
1380         return retval;
1381 }
1382
1383 /** \} */
1384
1385
1386 /* -------------------------------------------------------------------- */
1387
1388 /** \name Public Object Snapping API
1389  * \{ */
1390
1391 SnapObjectContext *ED_transform_snap_object_context_create(
1392         Main *bmain, Scene *scene, int flag)
1393 {
1394         SnapObjectContext *sctx = MEM_callocN(sizeof(*sctx), __func__);
1395
1396         sctx->flag = flag;
1397
1398         sctx->bmain = bmain;
1399         sctx->scene = scene;
1400
1401         return sctx;
1402 }
1403
1404 SnapObjectContext *ED_transform_snap_object_context_create_view3d(
1405         Main *bmain, Scene *scene, int flag,
1406         /* extra args for view3d */
1407         ARegion *ar, View3D *v3d)
1408 {
1409         SnapObjectContext *sctx = ED_transform_snap_object_context_create(bmain, scene, flag);
1410
1411         sctx->use_v3d = true;
1412         sctx->v3d_data.ar = ar;
1413         sctx->v3d_data.v3d = v3d;
1414
1415         if (sctx->flag & SNAP_OBJECT_USE_CACHE) {
1416                 sctx->cache.object_map = BLI_ghash_ptr_new(__func__);
1417                 sctx->cache.mem_arena = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, __func__);
1418         }
1419
1420         return sctx;
1421 }
1422
1423 static void snap_object_data_free(void *sod_v)
1424 {
1425         switch (((SnapObjectData *)sod_v)->type) {
1426                 case SNAP_MESH:
1427                 {
1428                         SnapObjectData_Mesh *sod = sod_v;
1429                         for (int i = 0; i < ARRAY_SIZE(sod->bvh_trees); i++) {
1430                                 if (sod->bvh_trees[i]) {
1431                                         free_bvhtree_from_mesh(sod->bvh_trees[i]);
1432                                 }
1433                         }
1434                         break;
1435                 }
1436                 case SNAP_EDIT_MESH:
1437                 {
1438                         SnapObjectData_EditMesh *sod = sod_v;
1439                         for (int i = 0; i < ARRAY_SIZE(sod->bvh_trees); i++) {
1440                                 if (sod->bvh_trees[i]) {
1441                                         free_bvhtree_from_editmesh(sod->bvh_trees[i]);
1442                                 }
1443                         }
1444                         break;
1445                 }
1446         }
1447 }
1448
1449 void ED_transform_snap_object_context_destroy(SnapObjectContext *sctx)
1450 {
1451         if (sctx->flag & SNAP_OBJECT_USE_CACHE) {
1452                 BLI_ghash_free(sctx->cache.object_map, NULL, snap_object_data_free);
1453                 BLI_memarena_free(sctx->cache.mem_arena);
1454         }
1455
1456         MEM_freeN(sctx);
1457 }
1458
1459 void ED_transform_snap_object_context_set_editmesh_callbacks(
1460         SnapObjectContext *sctx,
1461         bool (*test_vert_fn)(BMVert *, void *user_data),
1462         bool (*test_edge_fn)(BMEdge *, void *user_data),
1463         bool (*test_face_fn)(BMFace *, void *user_data),
1464         void *user_data)
1465 {
1466         sctx->callbacks.edit_mesh.test_vert_fn = test_vert_fn;
1467         sctx->callbacks.edit_mesh.test_edge_fn = test_edge_fn;
1468         sctx->callbacks.edit_mesh.test_face_fn = test_face_fn;
1469
1470         sctx->callbacks.edit_mesh.user_data = user_data;
1471 }
1472
1473 bool ED_transform_snap_object_project_ray_ex(
1474         SnapObjectContext *sctx,
1475         const unsigned short snap_to,
1476         const struct SnapObjectParams *params,
1477         const float ray_start[3], const float ray_normal[3], float *ray_depth,
1478         float r_loc[3], float r_no[3], int *r_index,
1479         Object **r_ob, float r_obmat[4][4])
1480 {
1481         return snapObjectsRay(
1482                 sctx,
1483                 snap_to, params->snap_select, params->use_object_edit_cage,
1484                 NULL, NULL,
1485                 ray_start, ray_normal, ray_start, ray_depth,
1486                 r_loc, r_no, r_index, r_ob, r_obmat, NULL);
1487 }
1488
1489 /**
1490  * Fill in a list of all hits.
1491  *
1492  * \param ray_depth: Only depths in this range are considered, -1.0 for maximum.
1493  * \param sort: Optionally sort the hits by depth.
1494  * \param r_hit_list: List of #SnapObjectHitDepth (caller must free).
1495  */
1496 bool ED_transform_snap_object_project_ray_all(
1497         SnapObjectContext *sctx,
1498         const unsigned short snap_to,
1499         const struct SnapObjectParams *params,
1500         const float ray_start[3], const float ray_normal[3],
1501         float ray_depth, bool sort,
1502         ListBase *r_hit_list)
1503 {
1504         if (ray_depth == -1.0f) {
1505                 ray_depth = BVH_RAYCAST_DIST_MAX;
1506         }
1507
1508 #ifdef DEBUG
1509         float ray_depth_prev = ray_depth;
1510 #endif
1511
1512         bool retval = snapObjectsRay(
1513                 sctx,
1514                 snap_to, params->snap_select, params->use_object_edit_cage,
1515                 NULL, NULL,
1516                 ray_start, ray_normal, ray_start, &ray_depth,
1517                 NULL, NULL, NULL, NULL, NULL,
1518                 r_hit_list);
1519
1520         /* meant to be readonly for 'all' hits, ensure it is */
1521 #ifdef DEBUG
1522         BLI_assert(ray_depth_prev == ray_depth);
1523 #endif
1524
1525         if (sort) {
1526                 BLI_listbase_sort(r_hit_list, hit_depth_cmp);
1527         }
1528
1529         return retval;
1530 }
1531
1532 /**
1533  * Convenience function for snap ray-casting.
1534  *
1535  * Given a ray, cast it into the scene (snapping to faces).
1536  *
1537  * \return Snap success
1538  */
1539 static bool transform_snap_context_project_ray_impl(
1540         SnapObjectContext *sctx,
1541         const struct SnapObjectParams *params,
1542         const float ray_start[3], const float ray_normal[3], float *ray_depth,
1543         float r_co[3], float r_no[3])
1544 {
1545         bool ret;
1546
1547         /* try snap edge, then face if it fails */
1548         ret = ED_transform_snap_object_project_ray_ex(
1549                 sctx,
1550                 SCE_SNAP_MODE_FACE,
1551                 params,
1552                 ray_start, ray_normal, ray_depth,
1553                 r_co, r_no, NULL,
1554                 NULL, NULL);
1555
1556         return ret;
1557 }
1558
1559 bool ED_transform_snap_object_project_ray(
1560         SnapObjectContext *sctx,
1561         const struct SnapObjectParams *params,
1562         const float ray_origin[3], const float ray_direction[3], float *ray_depth,
1563         float r_co[3], float r_no[3])
1564 {
1565         float ray_depth_fallback;
1566         if (ray_depth == NULL) {
1567                 ray_depth_fallback = BVH_RAYCAST_DIST_MAX;
1568                 ray_depth = &ray_depth_fallback;
1569         }
1570
1571         float no_fallback[3];
1572         if (r_no == NULL) {
1573                 r_no = no_fallback;
1574         }
1575
1576         return transform_snap_context_project_ray_impl(
1577                 sctx,
1578                 params,
1579                 ray_origin, ray_direction, ray_depth,
1580                 r_co, r_no);
1581 }
1582
1583 static bool transform_snap_context_project_view3d_mixed_impl(
1584         SnapObjectContext *sctx,
1585         const unsigned short snap_to_flag,
1586         const struct SnapObjectParams *params,
1587         const float mval[2], float *dist_px,
1588         bool use_depth,
1589         float r_co[3], float r_no[3])
1590 {
1591         float ray_depth = BVH_RAYCAST_DIST_MAX;
1592         bool is_hit = false;
1593
1594         float r_no_dummy[3];
1595         if (r_no == NULL) {
1596                 r_no = r_no_dummy;
1597         }
1598
1599         const int  elem_type[3] = {SCE_SNAP_MODE_VERTEX, SCE_SNAP_MODE_EDGE, SCE_SNAP_MODE_FACE};
1600
1601         BLI_assert(snap_to_flag != 0);
1602         BLI_assert((snap_to_flag & ~(1 | 2 | 4)) == 0);
1603
1604         for (int i = 0; i < 3; i++) {
1605                 if ((snap_to_flag & (1 << i)) && (is_hit == false || use_depth)) {
1606                         if (use_depth == false) {
1607                                 ray_depth = BVH_RAYCAST_DIST_MAX;
1608                         }
1609
1610                         if (ED_transform_snap_object_project_view3d(
1611                                 sctx,
1612                                 elem_type[i], params,
1613                                 mval, dist_px, &ray_depth,
1614                                 r_co, r_no))
1615                         {
1616                                 is_hit = true;
1617                         }
1618                 }
1619         }
1620
1621         return is_hit;
1622 }
1623
1624 /**
1625  * Convenience function for performing snapping.
1626  *
1627  * Given a 2D region value, snap to vert/edge/face.
1628  *
1629  * \param sctx: Snap context.
1630  * \param mval: Screenspace coordinate.
1631  * \param dist_px: Maximum distance to snap (in pixels).
1632  * \param use_depth: Snap to the closest element, use when using more than one snap type.
1633  * \param r_co: hit location.
1634  * \param r_no: hit normal (optional).
1635  * \return Snap success
1636  */
1637 bool ED_transform_snap_object_project_view3d_mixed(
1638         SnapObjectContext *sctx,
1639         const unsigned short snap_to_flag,
1640         const struct SnapObjectParams *params,
1641         const float mval_fl[2], float *dist_px,
1642         bool use_depth,
1643         float r_co[3], float r_no[3])
1644 {
1645         return transform_snap_context_project_view3d_mixed_impl(
1646                 sctx,
1647                 snap_to_flag, params,
1648                 mval_fl, dist_px, use_depth,
1649                 r_co, r_no);
1650 }
1651
1652 bool ED_transform_snap_object_project_view3d_ex(
1653         SnapObjectContext *sctx,
1654         const unsigned short snap_to,
1655         const struct SnapObjectParams *params,
1656         const float mval[2], float *dist_px,
1657         float *ray_depth,
1658         float r_loc[3], float r_no[3], int *r_index)
1659 {
1660         float ray_start[3], ray_normal[3], ray_orgigin[3];
1661
1662         float ray_depth_fallback;
1663         if (ray_depth == NULL) {
1664                 ray_depth_fallback = BVH_RAYCAST_DIST_MAX;
1665                 ray_depth = &ray_depth_fallback;
1666         }
1667
1668         if (!ED_view3d_win_to_ray_ex(
1669                 sctx->v3d_data.ar, sctx->v3d_data.v3d,
1670                 mval, ray_orgigin, ray_normal, ray_start, true))
1671         {
1672                 return false;
1673         }
1674
1675         return snapObjectsRay(
1676                 sctx,
1677                 snap_to, params->snap_select, params->use_object_edit_cage,
1678                 mval, dist_px,
1679                 ray_start, ray_normal, ray_orgigin, ray_depth,
1680                 r_loc, r_no, r_index, NULL, NULL, NULL);
1681 }
1682
1683 bool ED_transform_snap_object_project_view3d(
1684         SnapObjectContext *sctx,
1685         const unsigned short snap_to,
1686         const struct SnapObjectParams *params,
1687         const float mval[2], float *dist_px,
1688         float *ray_depth,
1689         float r_loc[3], float r_no[3])
1690 {
1691         return ED_transform_snap_object_project_view3d_ex(
1692                 sctx,
1693                 snap_to,
1694                 params,
1695                 mval, dist_px,
1696                 ray_depth,
1697                 r_loc, r_no, NULL);
1698 }
1699
1700 /**
1701  * see: #ED_transform_snap_object_project_ray_all
1702  */
1703 bool ED_transform_snap_object_project_all_view3d_ex(
1704         SnapObjectContext *sctx,
1705         const struct SnapObjectParams *params,
1706         const float mval[2],
1707         float ray_depth, bool sort,
1708         ListBase *r_hit_list)
1709 {
1710         float ray_start[3], ray_normal[3];
1711
1712         if (!ED_view3d_win_to_ray_ex(
1713                 sctx->v3d_data.ar, sctx->v3d_data.v3d,
1714                 mval, NULL, ray_normal, ray_start, true))
1715         {
1716                 return false;
1717         }
1718
1719         return ED_transform_snap_object_project_ray_all(
1720                 sctx,
1721                 SCE_SNAP_MODE_FACE,
1722                 params,
1723                 ray_start, ray_normal, ray_depth, sort,
1724                 r_hit_list);
1725 }
1726
1727 /** \} */