Revision: 74249
http://sourceforge.net/p/brlcad/code/74249
Author: starseeker
Date: 2019-10-26 19:42:49 +0000 (Sat, 26 Oct 2019)
Log Message:
-----------
Use the ON_FindLocalMinimum function from openNURBS to more properly implement
the NURBS curve get closest point function.
Modified Paths:
--------------
brlcad/trunk/src/libbrep/cdt_ovlps.cpp
brlcad/trunk/src/libbrep/opennurbs_ext.cpp
Modified: brlcad/trunk/src/libbrep/cdt_ovlps.cpp
===================================================================
--- brlcad/trunk/src/libbrep/cdt_ovlps.cpp 2019-10-25 22:07:41 UTC (rev
74248)
+++ brlcad/trunk/src/libbrep/cdt_ovlps.cpp 2019-10-26 19:42:49 UTC (rev
74249)
@@ -1538,7 +1538,7 @@
std::set<cdt_mesh::bedge_seg_t *> segs;
segs.insert(ev_it->first);
#if 0
- ON_3dPoint problem(3.44525,7.67444,22.9198);
+ ON_3dPoint problem(3.06294,7.5,24.2775);
std::set<overt_t *>::iterator v_it;
for (v_it = verts.begin(); v_it != verts.end(); v_it++) {
overt_t *v = *v_it;
@@ -1772,6 +1772,14 @@
// If this point is also close to a brep face edge, list that
edge/vert
// combination for splitting
ON_3dPoint vp = v->vpnt();
+
+#if 1
+ ON_3dPoint problem(3.06294,7.5,24.2775);
+ if (problem.DistanceTo(vp) < 0.01) {
+ std::cout << "problem\n";
+ }
+#endif
+
cdt_mesh::uedge_t closest_edge =
omesh1->fmesh->closest_uedge(t1, vp);
if (omesh1->fmesh->brep_edges.find(closest_edge) !=
omesh1->fmesh->brep_edges.end()) {
cdt_mesh::bedge_seg_t *bseg =
omesh1->fmesh->ue2b_map[closest_edge];
@@ -1976,26 +1984,31 @@
double dist = ov->bb.Diagonal().Length() * 10;
closest_surf_pnt(spnt, sn, *omesh->fmesh, &ovpnt, 2*dist);
- // TODO - check this point against the mesh vert tree - if we're
+ // Check this point against the mesh vert tree - if we're
// extremely close to an existing vertex, we don't want to split
// and create extremely tiny triangles - vertex adjustment should
// handle super-close points...
ON_BoundingBox pbb(spnt, spnt);
std::set<overt_t *> cverts = omesh->vert_search(pbb);
- std::cout << "Found " << cverts.size() << " close verts\n";
- // Maybe try something like this - if we're close to a vertex, find
- // the vertices from the other mesh that overlap with that vertex.
- // If there are none (can that happen?) adjust the vertex. If
- // there are, if the surface point is closer than the closest vert
- // from the other mesh, adjust, otherwise skip.
+
+ // If we're close to a vertex, find the vertices from the other
+ // mesh that overlap with that vertex. If there are, and if the
+ // surface point is close to them per the vert bbox dimension,
+ // skip that point as a refinement point in this step.
if (cverts.size()) {
double spdist = ovpnt.DistanceTo(spnt);
+
if (spdist < ON_ZERO_TOLERANCE) {
+ // If we're on the vertex point, we don't need to check
+ // further - we're not splitting there.
omesh->refine_pnt_remove(ov);
continue;
}
+
+ // Find the closest vertex, and use its bounding box size as a
+ // gauge for how close is too close for the surface point
double vdist = DBL_MAX;
- double bbdiag;
+ double bbdiag = DBL_MAX;
std::set<overt_t *>::iterator v_it;
for (v_it = cverts.begin(); v_it != cverts.end(); v_it++) {
ON_3dPoint cvpnt = (*v_it)->vpnt();
@@ -2010,11 +2023,9 @@
omesh->refine_pnt_remove(ov);
continue;
}
- std::cout << "spdist: " << spdist << "\n";
- std::cout << "bbdiag: " << bbdiag << "\n";
}
- // Find the closest edges
+ // If we passed the above filter, find the closest edges
std::set<cdt_mesh::uedge_t> close_edges =
omesh->interior_uedges_search(ov->bb);
double mindist = DBL_MAX;
Modified: brlcad/trunk/src/libbrep/opennurbs_ext.cpp
===================================================================
--- brlcad/trunk/src/libbrep/opennurbs_ext.cpp 2019-10-25 22:07:41 UTC (rev
74248)
+++ brlcad/trunk/src/libbrep/opennurbs_ext.cpp 2019-10-26 19:42:49 UTC (rev
74249)
@@ -176,10 +176,37 @@
return 0;
}
-/* Implement the algorithm from https://github.com/pboyer/verb - specifically:
+
+/* Implement the closest point on curve algorithm from
+ * https://github.com/pboyer/verb - specifically:
+ *
* verb/src/verb/eval/Tess.hx
* verb/src/verb/eval/Analyze.hx
*/
+
+struct curve_search_args {
+ const ON_NurbsCurve *nc;
+ ON_3dPoint tp;
+};
+
+int
+curve_closest_search_func(void *farg, double t, double *ft, double *dft)
+{
+ struct curve_search_args *cargs = (struct curve_search_args *)farg;
+ const ON_NurbsCurve *nc = cargs->nc;
+ ON_3dPoint tp = cargs->tp;
+ ON_3dPoint crv_pnt;
+ ON_3dVector crv_d1;
+ ON_3dVector crv_d2;
+ if (!nc->Ev2Der(t, crv_pnt, crv_d1, crv_d2)) return -1;
+ ON_3dVector fparam2 = crv_pnt - tp;
+ *ft = ON_DotProduct(crv_d1, fparam2);
+ *dft = ON_DotProduct(crv_d2, fparam2) + ON_DotProduct(crv_d1, crv_d1);
+
+ if (*ft < ON_ZERO_TOLERANCE) return 1;
+ return 0;
+}
+
bool
ON_NurbsCurve_GetClosestPoint(
double *t,
@@ -201,10 +228,9 @@
pnts.push_back(nc->PointAt(st));
}
- // Find an initial guess based on the breakdown into segments
+ // Find an initial domain subset based on the breakdown into segments
double d1 = domain.Min();
double d2 = domain.Max();
- double u = 0.0;
double vmin = DBL_MAX;
for (size_t i = 0; i < pnts.size() - 1; i++) {
ON_Line l(pnts[i], pnts[i+1]);
@@ -211,37 +237,58 @@
double lt;
l.ClosestPointTo(p, <);
ON_3dPoint pl = l.PointAt(lt);
+ if ((lt < 0 || NEAR_ZERO(lt, ON_ZERO_TOLERANCE))) {
+ pl = l.PointAt(0);
+ }
+ if ((lt > 1 || NEAR_EQUAL(lt, 1, ON_ZERO_TOLERANCE))) {
+ pl = l.PointAt(1);
+ }
if (pl.DistanceTo(p) < vmin) {
vmin = pl.DistanceTo(p);
d1 = domain.ParameterAt(i*span);
d2 = domain.ParameterAt((i+1)*span);
- //u = d1 + (d2 - d1)*lt;
}
}
- // TODO - verb uses Newton iteration, and so should we - for the moment,
- // this is a quick and dirty (and undoubtedly slower) binary search
+ // Iterate to find the closest point
double vdist = DBL_MAX;
- double vmin_delta = DBL_MAX;
- double vmin_prev = vmin;
- ON_3dPoint p1 = nc->PointAt(d1);
- ON_3dPoint p2 = nc->PointAt(d2);
- while (vmin_delta > ON_ZERO_TOLERANCE) {
- u = (d1 + d2) * 0.5;
- if (p1.DistanceTo(p) < p2.DistanceTo(p)) {
- d2 = u;
- p2 = nc->PointAt(u);
- } else {
- d1 = u;
- p1 = nc->PointAt(u);
+ double u = (d1 + d2) * 0.5;
+ struct curve_search_args cargs;
+ cargs.nc = nc;
+ cargs.tp = p;
+ double st;
+ int osearch = ON_FindLocalMinimum(curve_closest_search_func, &cargs, d1,
u, d2, ON_EPSILON, 0.5*ON_ZERO_TOLERANCE, 100, &st);
+
+ if (osearch == 1) {
+
+ (*t) = st;
+ vdist = (p.DistanceTo(nc->PointAt(st)));
+
+ } else {
+
+ // ON_FindLocalMinimum failed, fall back on binary search
+ double vmin_delta = DBL_MAX;
+ double vmin_prev = vmin;
+ ON_3dPoint p1 = nc->PointAt(d1);
+ ON_3dPoint p2 = nc->PointAt(d2);
+ while (vmin_delta > ON_ZERO_TOLERANCE) {
+ u = (d1 + d2) * 0.5;
+ if (p1.DistanceTo(p) < p2.DistanceTo(p)) {
+ d2 = u;
+ p2 = nc->PointAt(u);
+ } else {
+ d1 = u;
+ p1 = nc->PointAt(u);
+ }
+ vdist = (p.DistanceTo(nc->PointAt(u)));
+ vmin_delta = fabs(vmin_prev - vmin);
+ vmin_prev = vmin;
}
- vdist = (p.DistanceTo(nc->PointAt(u)));
- vmin_delta = fabs(vmin_prev - vmin);
- vmin_prev = vmin;
+
+ (*t) = u;
+
}
- (*t) = u;
-
if (maximum_distance > 0 && vdist > maximum_distance) return false;
return true;
This was sent by the SourceForge.net collaborative development platform, the
world's largest Open Source development site.
_______________________________________________
BRL-CAD Source Commits mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/brlcad-commits
