Revision: 76195 http://sourceforge.net/p/brlcad/code/76195 Author: starseeker Date: 2020-06-24 20:14:44 +0000 (Wed, 24 Jun 2020) Log Message: ----------- Demonstrate in principle snapping to the closest point to two line segments if we are close to both of them. Need something much better than a hard coded number for the tolerance, but the mechanism itself seems to function.
Modified Paths: -------------- brlcad/trunk/src/libged/view/snap.c Modified: brlcad/trunk/src/libged/view/snap.c =================================================================== --- brlcad/trunk/src/libged/view/snap.c 2020-06-24 16:09:08 UTC (rev 76194) +++ brlcad/trunk/src/libged/view/snap.c 2020-06-24 20:14:44 UTC (rev 76195) @@ -41,48 +41,154 @@ return GED_ERROR; } +struct ged_cp_info { + double ctol_sq; // square of the distance that defines "close to a line" + + struct bview_data_line_state *c_lset; // container holding closest line + point_t cp; // closest point on closest line + int c_l; // index of closest line + double dsq; // squared distance to closest line + + struct bview_data_line_state *c_lset2; // container holding 2nd closest line + point_t cp2; // closest point on closest line + int c_l2; // index of 2nd closest line + double dsq2; // squared distance to 2nd closest line +}; +#define GED_CP_INFO_INIT {BN_TOL_DIST, NULL, VINIT_ZERO, -1, DBL_MAX, NULL, VINIT_ZERO, -1, DBL_MAX} + +static int +_find_closest_point(struct ged_cp_info *s, point_t *p, struct bview_data_line_state *lines) +{ + int ret = 0; + point_t P0, P1; + + if (lines->gdls_num_points < 2) { + return ret; + } + + // TODO - if we have a large number of lines drawn, we could really benefit + // from an acceleration structure such as the RTree to localize these tests + // rather than checking everything... + for (int i = 0; i < lines->gdls_num_points; i+=2) { + if (s->c_l == i && s->c_lset == lines) { + continue; + } + point_t c; + VMOVE(P0, lines->gdls_points[i]); + VMOVE(P1, lines->gdls_points[i+1]); + double dsq = bg_lseg_pt_dist_sq(&c, P0, P1, *p); + // If this is the closest we've seen, record it + if (s->dsq > dsq) { + // Closest is now second closest + VMOVE(s->cp2, s->cp); + s->dsq2 = s->dsq; + s->c_l2 = s->c_l; + s->c_lset2 = s->c_lset; + + // set new closest + VMOVE(s->cp, c); + s->dsq = dsq; + s->c_l = i; + s->c_lset = lines; + printf("1st: %g: %g %g %g\n", sqrt(dsq), V3ARGS(c)); + ret = 1; + continue; + } + // Not the closest - is it closer than the second closest? + if (s->dsq2 > dsq) { + VMOVE(s->cp2, c); + s->dsq2 = dsq; + s->c_l2 = i; + s->c_lset2 = lines; + printf("2nd: %g: %g %g %g\n", sqrt(dsq), V3ARGS(c)); + ret = 2; + continue; + } + } + + return ret; +} + +void +_find_close_isect(struct ged_cp_info *s, point_t *p) +{ + point_t P0, P1, Q0, Q1; + point_t c1, c2; + + VMOVE(P0, s->c_lset->gdls_points[s->c_l]); + VMOVE(P1, s->c_lset->gdls_points[s->c_l+1]); + + VMOVE(Q0, s->c_lset2->gdls_points[s->c_l2]); + VMOVE(Q1, s->c_lset2->gdls_points[s->c_l2+1]); + + double csdist_sq = bg_lseg_lseg_dist_sq(&c1, &c2, P0, P1, Q0, Q1); + if (csdist_sq > s->ctol_sq) { + // Line segments are too far away to use both of them to override the + // original answer + return; + } + + // If either closest segment point is too far from the test point, go with + // the original answer rather than changing it + double d1_sq = DIST_PNT_PNT_SQ(*p, c1); + if (d1_sq > s->ctol_sq) { + // Too far away to work + return; + } + + double d2_sq = DIST_PNT_PNT_SQ(*p, c2); + if (d2_sq > s->ctol_sq) { + // Too far away to work + return; + } + + // Go with the closest segment point to the original point. If + // the segments intersect the two points should be the same and + // it won't matter which is chosen, but if they don't then the + // intuitive behavior is to prefer the closest point that attempts + // to satisfy both line segments + if (d1_sq < d2_sq) { + VMOVE(s->cp, c1); + } else { + VMOVE(s->cp, c2); + } +} + +int ged_snap_lines_3d(struct ged *gedp, point_t *p) { - struct bview_data_line_state *lines = NULL; + struct ged_cp_info cpinfo = GED_CP_INFO_INIT; + cpinfo.ctol_sq = 100*100; + if (!p || !gedp) return GED_ERROR; - bu_log("%g %g %g\n", V3ARGS(*p)); + // There are some issues with line snapping that don't come up with grid // snapping - in particular, when are we "close enough" to a line to snap, // and how do we handle snapping when close enough to multiple lines? We // probably want to prefer intersections between lines to closest line // point if we are close to multiple lines... + int ret = 0; + ret += _find_closest_point(&cpinfo, p, &gedp->ged_gvp->gv_data_lines); + ret += _find_closest_point(&cpinfo, p, &gedp->ged_gvp->gv_sdata_lines); - lines = &gedp->ged_gvp->gv_data_lines; - - if (lines->gdls_num_points > 1) { - point_t P0, P1; - for (int i = 0; i < lines->gdls_num_points; i+=2) { - point_t c; - VMOVE(P0, lines->gdls_points[i]); - VMOVE(P1, lines->gdls_points[i+1]); - double dsq = bg_lseg_pt_dist_sq(&c, P0, P1, *p); - bu_log("%g: %g %g %g\n", sqrt(dsq), V3ARGS(c)); - } + // Check if we are close enough to two line segments to warrant using the + // closest approach point. The intersection may not be close enough to + // use, but if it is prefer it as it satisfies two lines instead of one. + if (ret > 1) { + _find_close_isect(&cpinfo, p); } - lines = &gedp->ged_gvp->gv_sdata_lines; - - if (lines->gdls_num_points > 1) { - point_t P0, P1; - for (int i = 0; i < lines->gdls_num_points; i+=2) { - point_t c; - VMOVE(P0, lines->gdls_points[i]); - VMOVE(P1, lines->gdls_points[i+1]); - double dsq = bg_lseg_pt_dist_sq(&c, P0, P1, *p); - bu_log("%g: %g %g %g\n", sqrt(dsq), V3ARGS(c)); - } + // If we found something, we can snap + if (ret) { + bu_log("%g %g %g\n", V3ARGS(cpinfo.cp)); + } else { + bu_log("no lines close enough for snapping\n"); } - - return GED_ERROR; + return GED_OK; } int This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site. _______________________________________________ BRL-CAD Source Commits mailing list brlcad-commits@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/brlcad-commits