1 // This is brl/bbas/imesh/algo/imesh_imls_surface.cxx
2 #include <iostream>
3 #include <cmath>
4 #include <limits>
5 #include "imesh_imls_surface.h"
6 //:
7 // \file
8
9 #include <imesh/imesh_operations.h>
10 #include <imesh/algo/imesh_intersect.h>
11 #include <imesh/algo/imesh_kd_tree.hxx>
12 #ifdef _MSC_VER
13 # include "vcl_msvc_warnings.h"
14 #endif
15 #include <cassert>
16
17 #include "vnl/vnl_math.h"
18 #include "vnl/vnl_double_3.h"
19
20
21 //: Constructor
imesh_imls_surface(const imesh_mesh & mesh,double eps,double lambda,bool enforce_bounded,const std::set<unsigned int> & no_normal_faces)22 imesh_imls_surface::imesh_imls_surface(const imesh_mesh& mesh, double eps, double lambda,
23 bool enforce_bounded,
24 const std::set<unsigned int>& no_normal_faces)
25 : verts_(mesh.num_verts()), phi_(mesh.num_verts(),0.0),
26 eps2_(eps*eps), lambda_(lambda), iso_level_(0.0), bounded_(enforce_bounded)
27 {
28 const imesh_vertex_array<3>& v = mesh.vertices<3>();
29
30 for (unsigned int i=0; i<v.size(); ++i)
31 verts_[i] = vgl_point_3d<double>(v[i]);
32
33 if (mesh.faces().regularity() != 3)
34 triangles_ = imesh_triangulate(mesh.faces());
35 else
36 triangles_.reset(static_cast<imesh_regular_face_array<3>*>
37 (mesh.faces().clone()));
38
39 if (bounded_)
40 {
41 // build enclosure
42 vgl_box_3d<double> box;
43 for (const auto & vert : verts_) {
44 box.add(vert);
45 }
46 box.expand_about_centroid(1);
47 unsigned int base = verts_.size();
48 verts_.emplace_back(box.min_x(),box.min_y(),box.min_z());
49 verts_.emplace_back(box.min_x(),box.min_y(),box.max_z());
50 verts_.emplace_back(box.min_x(),box.max_y(),box.min_z());
51 verts_.emplace_back(box.min_x(),box.max_y(),box.max_z());
52 verts_.emplace_back(box.max_x(),box.min_y(),box.min_z());
53 verts_.emplace_back(box.max_x(),box.min_y(),box.max_z());
54 verts_.emplace_back(box.max_x(),box.max_y(),box.min_z());
55 verts_.emplace_back(box.max_x(),box.max_y(),box.max_z());
56 triangles_->push_back(imesh_tri(base+0,base+1,base+2));
57 triangles_->push_back(imesh_tri(base+1,base+3,base+2));
58 triangles_->push_back(imesh_tri(base+0,base+6,base+4));
59 triangles_->push_back(imesh_tri(base+0,base+2,base+6));
60 triangles_->push_back(imesh_tri(base+2,base+7,base+6));
61 triangles_->push_back(imesh_tri(base+2,base+3,base+7));
62 triangles_->push_back(imesh_tri(base+3,base+5,base+7));
63 triangles_->push_back(imesh_tri(base+3,base+1,base+5));
64 triangles_->push_back(imesh_tri(base+1,base+4,base+5));
65 triangles_->push_back(imesh_tri(base+1,base+0,base+4));
66 triangles_->push_back(imesh_tri(base+4,base+7,base+5));
67 triangles_->push_back(imesh_tri(base+4,base+6,base+7));
68 phi_.resize(verts_.size(),1.0);
69 }
70
71 std::vector<vgl_box_3d<double> > boxes(triangles_->size());
72 for ( unsigned int i=0; i<boxes.size(); ++i ) {
73 const imesh_regular_face<3>& tri = (*triangles_)[i];
74 boxes[i].add(verts_[tri[0]]);
75 boxes[i].add(verts_[tri[1]]);
76 boxes[i].add(verts_[tri[2]]);
77 }
78
79 kd_tree_ = imesh_build_kd_tree(boxes);
80 unsigned num_tree_nodes = triangles_->size()*2-1;
81
82 unweighted_.resize(num_tree_nodes);
83 centroid_.resize(num_tree_nodes);
84 normals_.resize(num_tree_nodes);
85 normal_len_.resize(num_tree_nodes);
86 area_.resize(num_tree_nodes);
87
88
89 compute_centroids_rec(kd_tree_, no_normal_faces);
90 compute_unweighed_rec(kd_tree_);
91
92 compute_enclosing_phi();
93 }
94
95
96 //: Copy Constructor
imesh_imls_surface(const imesh_imls_surface & other)97 imesh_imls_surface::imesh_imls_surface(const imesh_imls_surface& other)
98 : verts_(other.verts_),
99 triangles_(other.triangles_.get() ?
100 new imesh_regular_face_array<3>(*other.triangles_) :
101 nullptr),
102 kd_tree_(other.kd_tree_.get() ?
103 new imesh_kd_tree_node(*other.kd_tree_) :
104 nullptr),
105 phi_(other.phi_),
106 area_(other.area_),
107 unweighted_(other.unweighted_),
108 centroid_(other.centroid_),
109 normals_(other.normals_),
110 normal_len_(other.normal_len_),
111 eps2_(other.eps2_),
112 lambda_(other.lambda_),
113 iso_level_(other.iso_level_)
114 {
115 }
116
117
118 //: compute the iso value such that the mean value at the vertices is zero
compute_iso_level()119 void imesh_imls_surface::compute_iso_level()
120 {
121 double mean = 0.0;
122 for (const auto & vert : verts_)
123 mean += (*this)(vert);
124 iso_level_ = mean / verts_.size();
125 }
126
127
128 //: adjust the phi values until all vertices are within the iso surface
129 // Also computes the iso level
compute_enclosing_phi()130 void imesh_imls_surface::compute_enclosing_phi()
131 {
132 typedef std::pair<unsigned int,double> pair_id;
133 std::vector<pair_id> outside;
134 double mean = 0.0;
135 const unsigned int num_verts = bounded_ ?
136 verts_.size() :
137 verts_.size() - 8;
138 for (unsigned int i=0; i<num_verts; ++i) {
139 double val = (*this)(verts_[i]);
140 mean += val;
141 if (val > 0)
142 outside.emplace_back(i,val);
143 }
144 iso_level_ = mean / verts_.size();
145
146 for (double s=1.0; !outside.empty(); s*=2) {
147 std::cout << outside.size() << " outside" << std::endl;
148 for (std::vector<pair_id>::const_iterator i=outside.begin();
149 i!=outside.end(); ++i) {
150 phi_[i->first] -= s*i->second;
151 }
152 compute_unweighed_rec(kd_tree_);
153 std::vector<pair_id> next_outside;
154 for (std::vector<pair_id>::const_iterator i=outside.begin();
155 i!=outside.end(); ++i) {
156 double val = (*this)(verts_[i->first]);
157 if (val > std::abs(std::numeric_limits<double>::epsilon()*phi_[i->first])) {
158 next_outside.emplace_back(i->first,val);
159 }
160 }
161 outside.swap(next_outside);
162 }
163 }
164
165
166 //: recursively compute the area weighted centroids
167 void imesh_imls_surface::
compute_centroids_rec(const std::unique_ptr<imesh_kd_tree_node> & node,const std::set<unsigned int> & no_normal_faces)168 compute_centroids_rec(const std::unique_ptr<imesh_kd_tree_node>& node,
169 const std::set<unsigned int>& no_normal_faces)
170 {
171 const unsigned int& i = node->index_;
172 if (node->is_leaf()) {
173 const imesh_regular_face<3>& tri = (*triangles_)[i];
174 const vgl_point_3d<double>& v0 = verts_[tri[0]];
175 const vgl_point_3d<double>& v1 = verts_[tri[1]];
176 const vgl_point_3d<double>& v2 = verts_[tri[2]];
177 vgl_vector_3d<double>& n = normals_[i];
178 n = cross_product(v1-v0,v2-v0)/2.0;
179 normal_len_[i] = n.length();
180 area_[i] = normal_len_[i];
181 centroid_[i] = centre(v0,v1,v2);
182 if (no_normal_faces.find(i) != no_normal_faces.end()) {
183 n = vgl_vector_3d<double>(0,0,0);
184 normal_len_[i] = 0.0;
185 }
186 return;
187 }
188
189 compute_centroids_rec(node->left_,no_normal_faces);
190 compute_centroids_rec(node->right_,no_normal_faces);
191
192 const unsigned int& i_left = node->left_->index_;
193 const unsigned int& i_right = node->right_->index_;
194
195 const vgl_point_3d<double>& cl = centroid_[i_left];
196 const double& al = area_[i_left];
197 const vgl_point_3d<double>& cr = centroid_[i_right];
198 const double& ar = area_[i_right];
199 double& at = area_[i];
200 at = al + ar;
201 centroid_[i].set((ar*cr.x() + al*cl.x()) / at,
202 (ar*cr.y() + al*cl.y()) / at,
203 (ar*cr.z() + al*cl.z()) / at);
204 //normals_[i] = normalized(normals_[i_left]*al + normals_[i_right]*ar);
205 normals_[i] = normals_[i_left] + normals_[i_right];
206 normal_len_[i] = normals_[i].length();
207 }
208
209
210 //: recursively compute the unweighted integrals
211 void imesh_imls_surface::
compute_unweighed_rec(const std::unique_ptr<imesh_kd_tree_node> & node)212 compute_unweighed_rec(const std::unique_ptr<imesh_kd_tree_node>& node)
213 {
214 const unsigned int& i = node->index_;
215 if (node->is_leaf()) {
216 const imesh_regular_face<3>& tri = (*triangles_)[i];
217 unweighted_[i] = (phi_[tri[0]]
218 + phi_[tri[1]]
219 + phi_[tri[2]])/3.0 * area_[i];
220 //- dot_product(normals_[i],centroid_[i]-vgl_point_3d<double>(0,0,0));
221 return;
222 }
223
224 compute_unweighed_rec(node->left_);
225 compute_unweighed_rec(node->right_);
226
227 const unsigned int& i_left = node->left_->index_;
228 const unsigned int& i_right = node->right_->index_;
229 unweighted_[i] = unweighted_[i_left] + unweighted_[i_right];
230 }
231
232
233 //: return a bounding box for the original input mesh
bounding_box() const234 vgl_box_3d<double> imesh_imls_surface::bounding_box() const
235 {
236 return kd_tree_->inner_box_;
237 }
238
239
240 //: change the epsilon (smoothness) of the surface
set_epsilon(double eps)241 void imesh_imls_surface::set_epsilon(double eps)
242 {
243 eps2_ = eps*eps;
244 iso_level_ = 0.0;
245
246 // reset the phi values at each vertex
247 for (double & i : phi_)
248 i = 0.0;
249
250 compute_unweighed_rec(kd_tree_);
251
252 compute_enclosing_phi();
253 }
254
255
256 namespace {
257 class tri_dist_func
258 {
259 public:
tri_dist_func(const std::vector<vgl_point_3d<double>> & v,const imesh_regular_face_array<3> & t)260 tri_dist_func(const std::vector<vgl_point_3d<double> >& v,
261 const imesh_regular_face_array<3>& t)
262 : verts(v), tris(t), closest_index(static_cast<unsigned int>(-1)),
263 closest_dist(std::numeric_limits<double>::infinity()) {}
264 const std::vector<vgl_point_3d<double> >& verts;
265 const imesh_regular_face_array<3>& tris;
266 unsigned int closest_index;
267 double closest_dist, closest_u, closest_v;
268
operator ()(const vgl_point_3d<double> & pt,unsigned int i)269 double operator () (const vgl_point_3d<double>& pt, unsigned int i)
270 {
271 const imesh_regular_face<3>& tri = tris[i];
272 double dist,u,v;
273 /* unsigned char s = */
274 imesh_triangle_closest_point(pt,
275 verts[tri[0]], verts[tri[1]], verts[tri[2]],
276 dist, u, v);
277 if (dist < closest_dist) {
278 closest_dist = dist;
279 closest_index = i;
280 closest_u = u;
281 closest_v = v;
282 }
283 return dist;
284 }
285 };
286 // end of namespace
287 }
288
289
290 //: evaluate the implicit surface at a point
operator ()(const vgl_point_3d<double> & p) const291 double imesh_imls_surface::operator() (const vgl_point_3d<double>& p) const
292 {
293 double sum=0.0, sum_phi = 0.0;
294
295 std::vector<imesh_kd_tree_queue_entry> remain;
296 tri_dist_func dist(verts_,*triangles_);
297 /* unsigned int ind = */
298 imesh_closest_index<tri_dist_func&>(p,kd_tree_,dist,&remain);
299
300 // compute the (negative) maximum error of integration
301 // stored negative so that the max error is first when sorted by <
302 auto itr = remain.begin();
303 for (; itr != remain.end(); ++itr) {
304 double min = w2(itr->val_);
305 double max = w2(imesh_max_sq_dist(p,itr->node_->inner_box_));
306 itr->val_ = (max - min)*area_[itr->node_->index_];
307 }
308 std::make_heap( remain.begin(), remain.end() );
309
310 std::pop_heap( remain.begin(), remain.end() );
311 while (!remain.empty() && -remain.back().val_ > lambda_*sum)
312 {
313 imesh_kd_tree_node* current = remain.back().node_;
314 remain.pop_back();
315
316 if (current->is_leaf())
317 {
318 unsigned int i = current->index_;
319 const imesh_regular_face<3>& tri = (*triangles_)[i];
320 unsigned int i1=tri[0], i2=tri[1], i3=tri[2];
321 typedef vgl_vector_2d<double> T;
322 typedef vgl_vector_2d<double> (*F) (const vgl_point_3d<double>&, const vgl_point_3d<double>&,
323 const vgl_point_3d<double>&, const vgl_point_3d<double>&,
324 double, double, double, double);
325 vgl_vector_2d<double> I = triangle_quadrature<T,F>(split_triangle_quadrature,
326 p,verts_[i1],verts_[i2],verts_[i3],
327 normals_[i]*2.0,
328 phi_[i1],phi_[i2],phi_[i3],eps2_);
329 assert(!vnl_math::isnan(I.x()) && !vnl_math::isnan(I.y()));
330
331 sum_phi += I.x();
332 if (normal_len_[i]>0.0)
333 sum_phi += dot_product(normals_[i],p-verts_[i1]) * I.y() / normal_len_[i];
334 sum += I.y();
335 }
336 else
337 {
338 double min = w2(imesh_min_sq_dist(p,current->left_->inner_box_));
339 double max = w2(imesh_max_sq_dist(p,current->left_->inner_box_));
340 remain.emplace_back((max - min)*area_[current->left_->index_],
341 current->left_.get());
342 std::push_heap(remain.begin(), remain.end());
343
344 min = w2(imesh_min_sq_dist(p,current->right_->inner_box_));
345 max = w2(imesh_max_sq_dist(p,current->right_->inner_box_));
346 remain.emplace_back((max - min)*area_[current->right_->index_],
347 current->right_.get());
348 std::push_heap(remain.begin(), remain.end());
349 }
350 if (!remain.empty())
351 std::pop_heap( remain.begin(), remain.end() );
352 }
353
354 // approximate the contribution from the remain nodes
355 for (itr = remain.begin(); itr != remain.end(); ++itr) {
356 // Use approximation assuming the weight is constant
357 unsigned int i = itr->node_->index_;
358 vgl_vector_3d<double> v(p-centroid_[i]);
359 double w = w2(v.sqr_length());
360
361 sum_phi += w*unweighted_[i] + dot_product(normals_[i],v)*w;
362 sum += w*area_[i];
363 }
364
365 assert(sum != 0.0);
366 return sum_phi / sum - iso_level_;
367 }
368
369
370 //: evaluate the function and its derivative (returned by reference)
deriv(const vgl_point_3d<double> & p,vgl_vector_3d<double> & dp) const371 double imesh_imls_surface::deriv(const vgl_point_3d<double>& p,
372 vgl_vector_3d<double>& dp) const
373 {
374 integral_data sums;
375
376 std::vector<imesh_kd_tree_queue_entry> remain;
377 tri_dist_func dist(verts_,*triangles_);
378 /* unsigned int ind = */
379 imesh_closest_index<tri_dist_func&>(p,kd_tree_,dist,&remain);
380
381 // compute the (negative) maximum error of integration
382 // stored negative so that the max error is first when sorted by <
383 auto itr = remain.begin();
384 for (; itr != remain.end(); ++itr) {
385 double min = w2(itr->val_);
386 double max = w2(imesh_max_sq_dist(p,itr->node_->inner_box_));
387 itr->val_ = (max - min)*area_[itr->node_->index_];
388 }
389 std::make_heap( remain.begin(), remain.end() );
390
391 std::pop_heap( remain.begin(), remain.end() );
392 while (!remain.empty() && -remain.back().val_ > lambda_*sums.I)
393 {
394 imesh_kd_tree_node* current = remain.back().node_;
395 remain.pop_back();
396
397 if (current->is_leaf())
398 {
399 unsigned int i = current->index_;
400 const imesh_regular_face<3>& tri = (*triangles_)[i];
401 unsigned int i1=tri[0], i2=tri[1], i3=tri[2];
402 typedef integral_data T;
403 typedef integral_data (*F) (const vgl_point_3d<double>&, const vgl_point_3d<double>&,
404 const vgl_point_3d<double>&, const vgl_point_3d<double>&,
405 double, double, double, double);
406 integral_data Id = triangle_quadrature<T,F>(split_triangle_quadrature_with_deriv,
407 p,verts_[i1],verts_[i2],verts_[i3],
408 normals_[i]*2.0,
409 phi_[i1],phi_[i2],phi_[i3],eps2_);
410 assert(!vnl_math::isnan(Id.I) && !vnl_math::isnan(Id.I_phi));
411 //assert(!vnl_math::isnan(Id.dI) && !vnl_math::isnan(Id.dI_phi));
412
413 sums.I += Id.I;
414 sums.I_phi += Id.I_phi;
415 sums.dI += Id.dI;
416 sums.dI_phi += Id.dI_phi;
417 // terms involving the normal constraints
418 if (normal_len_[i]>0.0) {
419 const vgl_vector_3d<double>& n = normals_[i];
420 double plane_dist = dot_product(n,p-verts_[i1])/normal_len_[i];
421 sums.I_phi += plane_dist*Id.I;
422 sums.dI_phi += n*(Id.I/normal_len_[i]) + plane_dist*Id.dI;
423 }
424 }
425 else
426 {
427 double min = w2(imesh_min_sq_dist(p,current->left_->inner_box_));
428 double max = w2(imesh_max_sq_dist(p,current->left_->inner_box_));
429 remain.emplace_back((max - min)*area_[current->left_->index_],
430 current->left_.get());
431 std::push_heap(remain.begin(), remain.end());
432
433 min = w2(imesh_min_sq_dist(p,current->right_->inner_box_));
434 max = w2(imesh_max_sq_dist(p,current->right_->inner_box_));
435 remain.emplace_back((max - min)*area_[current->right_->index_],
436 current->right_.get());
437 std::push_heap(remain.begin(), remain.end());
438 }
439 if (!remain.empty())
440 std::pop_heap( remain.begin(), remain.end() );
441 }
442
443 // approximate the contribution from the remain nodes
444 for (itr = remain.begin(); itr != remain.end(); ++itr) {
445 // Use approximation assuming the weight is constant
446 unsigned int i = itr->node_->index_;
447 vgl_vector_3d<double> v(p-centroid_[i]);
448 double w = 1.0/(v.sqr_length() + eps2_);
449 vgl_vector_3d<double> dw(v);
450 dw *= -4*w;
451 w *= w;
452 dw *= w;
453
454 const vgl_vector_3d<double>& n = normals_[i];
455 double plane_dist = dot_product(n,v);
456 sums.I += w*area_[i];
457 sums.I_phi += w*unweighted_[i] + plane_dist*w;
458 sums.dI += dw*area_[i];
459 sums.dI_phi += n*w + dw*(unweighted_[i] + plane_dist);
460 }
461
462
463 assert(sums.I != 0.0);
464 dp = (-sums.I_phi/(sums.I*sums.I))*sums.dI + sums.dI_phi/sums.I;
465 return sums.I_phi / sums.I - iso_level_;
466 }
467
468
469 //: evaluate the function and its first and second derivatives (returned by reference)
deriv2(const vgl_point_3d<double> & p,vgl_vector_3d<double> & dp,vnl_double_3x3 & ddp) const470 double imesh_imls_surface::deriv2(const vgl_point_3d<double>& p,
471 vgl_vector_3d<double>& dp,
472 vnl_double_3x3& ddp) const
473 {
474 double eps = 1e-8;
475 double val = this->deriv(p,dp);
476 vgl_vector_3d<double> dpx,dpy,dpz;
477 this->deriv(p+vgl_vector_3d<double>(eps,0,0),dpx);
478 this->deriv(p+vgl_vector_3d<double>(0,eps,0),dpy);
479 this->deriv(p+vgl_vector_3d<double>(0,0,eps),dpz);
480 dpx -= dp;
481 dpx /= eps;
482 dpy -= dp;
483 dpy /= eps;
484 dpz -= dp;
485 dpz /= eps;
486 ddp(0,0) = dpx.x(); ddp(0,1) = dpy.x(); ddp(0,2) = dpz.x();
487 ddp(1,0) = dpx.y(); ddp(1,1) = dpy.y(); ddp(1,2) = dpz.y();
488 ddp(2,0) = dpx.z(); ddp(2,1) = dpy.z(); ddp(2,2) = dpz.z();
489 return val;
490 }
491
492 //: integrals of f(x)dx and x*f(x)dx over [0,1] where f(x)= 1/((x+k1)^2 + k2)^2
493 //
494 // These equations are wrong in the paper, they should be (for a=1):
495 // Beta = atan( k1/sqrt(k2) ) - atan( (k1+1)/sqrt(k2) )
496 // I1 = -Beta * 1/(2*k2^(3/2)) + (k2 - k1*(k1+1)) / (2*k2*(k1^2+k2)*((k1+1)^2+k2))
497 // Ix = Beta * k1/(2*k2^(3/2)) + (k1 + 1) / (2*k2*((k1+1)^2+k2))
498 void
line_integrals(double k1,double k2,double & I1,double & Ix)499 imesh_imls_surface::line_integrals(double k1, double k2, double& I1, double& Ix)
500 {
501 double sqrt_k2 = std::sqrt(k2);
502 double k1_p1 = k1+1.0;
503 I1 = Ix = (std::atan(k1_p1/sqrt_k2) - std::atan(k1/sqrt_k2) ) / (2.0*k2*sqrt_k2);
504 Ix *= -k1;
505
506 double denom = 1.0/(2.0*k2*(k1_p1*k1_p1+k2));
507
508 Ix += k1_p1 * denom;
509 I1 += (k2 - k1*k1_p1)*denom / (k1*k1+k2);
510 }
511
512
513 //: integrals of f(x)dx and x*f(x)dx over [0,1] where f(x)= 1/((x+k1)^2 + k2)^2
514 // Also compute the integrals when f(x)=1/((x+k1)^2 + k2)^3 (for use in derivatives)
515 //
516 // Beta = atan( k1/sqrt(k2) ) - atan( (k1+1)/sqrt(k2) )
517 // I1 = -Beta * 1/(2*k2^(3/2)) + (k2 - k1*(k1+1)) / (2*k2*(k1^2+k2)*((k1+1)^2+k2))
518 // Ix = Beta * k1/(2*k2^(3/2)) + (k1 + 1) / (2*k2*((k1+1)^2+k2))
519 // dI1 = 1/8 * ( -Beta*3/k2^(5/2) +
520 // (5*k2^3 - (k1*(k1+1)-3)*k2^2 - k1*(k1+1)*(9*k1*(k1+1)+5)*k2 - 3*k1^3*(k1+1)^3)
521 // / (k2^2*(k1^2+k2)^2*((k1+1)^2+k2)^2) )
522 // dIx = 1/8 * ( Beta*3*k1/k2^(5/2) +
523 // ((k1^2+k2)*((3*(k1+1)+1)*k2^2 + (k1+1)*(6*k1^2+3*k1+2)*k2 + 3*k1^2*(k1+1)^3))
524 // /(k2^2*(k1^2+k2)^2*((k1+1)^2+k2)^2) )
525 // dIx2 = 1/8 * ( -Beta*(3*k1^2+k2)/k2^(5/2) -
526 // ((k1^2+k2)^2*(k2^2 + (k1+1)*(4*k1-1)*k2 + 3*k1*(k1+1)^3))
527 // /(k2^2*(k1^2+k2)^2*((k1+1)^2+k2)^2) )
528 void
line_integrals(double k1,double k2,double & I1,double & Ix,double & dI1,double & dIx,double & dIx2)529 imesh_imls_surface::line_integrals(double k1, double k2,
530 double& I1, double& Ix,
531 double& dI1, double& dIx, double& dIx2)
532 {
533 double sqrt_k2 = std::sqrt(k2);
534 double k1_p1 = k1+1.0;
535 double k1_2 = k1*k1;
536 double k2_2 = k2*k2;
537 double k1_p1_2 = k1_p1*k1_p1;
538 double t1 = k2 + k1_p1_2;
539 double t2 = k2 + k1_2;
540 double t3 = 3*k1_p1_2*k1_p1*k1;
541
542
543 I1 = dI1 = (std::atan(k1_p1/sqrt_k2) - std::atan(k1/sqrt_k2) ) / (2.0*k2*sqrt_k2);
544 dI1 *= 0.75/k2;
545 Ix = -k1 * I1;
546 dIx = -k1 * dI1;
547 dIx2 = 0.25*I1*(3*k1_2+k2)/k2;
548
549
550 double denom = 0.5/(k2*t1);
551 double ddenom = 0.125/(k2_2*t2*t2*t1*t1);
552
553 I1 += (k2 - k1*k1_p1)*denom / t2;
554 Ix += k1_p1 * denom;
555
556 dI1 += (5*k2*k2_2 - (k1*k1_p1-3)*k2_2 - k1*k1_p1*(9*k1*k1_p1+5)*k2 - k1_2*t3 )*ddenom;
557 dIx += t2*((3*k1_p1+1)*k2_2 + k1_p1*(6*k1_2+3*k1+2)*k2 + k1*t3)*ddenom;
558 dIx2 -= t2*t2*(k2_2 + k1_p1*(4*k1-1)*k2 + t3)*ddenom;
559 }
560
561
562 //: line integral of the squared weight function times a linear value on the line from p0 to p1
563 // (value at p0 is v0 and at p1 is v1)
564 // \a eps2 is epsilon^2
565 double
line_integral(const vgl_point_3d<double> & x,const vgl_point_3d<double> & p0,const vgl_point_3d<double> & p1,double v0,double v1,double eps2)566 imesh_imls_surface::line_integral(const vgl_point_3d<double>& x,
567 const vgl_point_3d<double>& p0,
568 const vgl_point_3d<double>& p1,
569 double v0, double v1, double eps2)
570 {
571 vgl_vector_3d<double> ab(p1-p0);
572 vgl_vector_3d<double> xa(p0-x);
573 double denom = 1.0/ab.sqr_length();
574 double k1 = dot_product(ab,xa)*denom;
575 double k2 = (xa.sqr_length()+eps2)*denom - k1*k1;
576 double I1,Ix;
577 line_integrals(k1,k2,I1,Ix);
578 return (v0*I1 + (v1-v0)*Ix)*std::sqrt(denom)*denom;
579 }
580
581
582 //: The derivative of the line integral with respect to x
583 vgl_vector_3d<double>
line_integral_deriv(const vgl_point_3d<double> & x,const vgl_point_3d<double> & p0,const vgl_point_3d<double> & p1,double v0,double v1,double eps2)584 imesh_imls_surface::line_integral_deriv(const vgl_point_3d<double>& x,
585 const vgl_point_3d<double>& p0,
586 const vgl_point_3d<double>& p1,
587 double v0, double v1, double eps2)
588 {
589 vgl_vector_3d<double> ab(p1-p0);
590 vgl_vector_3d<double> xa(p0-x);
591 double denom = 1.0/ab.sqr_length();
592 double k1 = dot_product(ab,xa)*denom;
593 double k2 = (xa.sqr_length()+eps2)*denom - k1*k1;
594 double I1,Ix,dI1,dIx,dIx2;
595 line_integrals(k1,k2,I1,Ix,dI1,dIx,dIx2);
596 denom = 4*std::sqrt(denom)*denom*denom;
597
598 return (xa*(v0*dI1+(v1-v0)*dIx)
599 + ab*(v0*dIx + (v1-v0)*dIx2))*denom;//4*std::sqrt(denom)*denom*denom;
600 }
601
602
603 //: area integral of the squared weight function times a linearly interpolated value
604 // \a m is the point closest point on the triangle to sample point \a x
605 // \a p0 and \a p1 are the other vertices
606 // call triangle_quadrature to first split an arbitrary triangle
607 // \a eps2 is epsilon^2
608 vgl_vector_2d<double>
split_triangle_quadrature(const vgl_point_3d<double> & x,const vgl_point_3d<double> & pm,const vgl_point_3d<double> & p1,const vgl_point_3d<double> & p2,double vm,double v1,double v2,double eps)609 imesh_imls_surface::split_triangle_quadrature(const vgl_point_3d<double>& x,
610 const vgl_point_3d<double>& pm,
611 const vgl_point_3d<double>& p1,
612 const vgl_point_3d<double>& p2,
613 double vm, double v1, double v2,
614 double eps)
615 {
616 vgl_point_3d<double> pp(p1), pn(p2);
617 double vp(v1), vn(v2);
618 if ((pp-x).length() > (pn-x).length()) {
619 // swap so that pp is closest to x
620 pp = p2; pn = p1;
621 vp = v2; vn = v1;
622 }
623
624 vgl_vector_3d<double> d1(pp-pm);
625 vgl_vector_3d<double> d2(pn-pm);
626 vgl_vector_3d<double> d3(pm-x);
627
628 double t1 = d1.sqr_length();
629 double t2 = dot_product(d1,d2);
630 double t3 = dot_product(d1,d3);
631 double t4 = d2.sqr_length();
632 double t5 = dot_product(d2,d3) * 2;
633 double t6 = d3.sqr_length() + eps;
634
635 // compute height (divided by 2*sqrt(t1))
636 // early exit if triangle flat
637 double height = t4/t1 - t2*t2/(t1*t1);
638 if (!(height > 0.0))
639 return {0,0};
640 height = std::sqrt(height)/2.0;
641
642 double vt1 = vn-vm;
643 double vt2 = vp-vm;
644
645 double alpha = 2.0/3.0;
646 double sum1 = 0.0, sum2 = 0.0;
647 double weight = (1.0/alpha-alpha);
648 double I1,Ix,u_1,denom,k1,k2;
649 double u = alpha;
650 double last_li1 = 0.0, last_li2 = 0.0;
651 // integrate using the trapezoid rule with non-uniform sampling
652 for (; u>0.01; u*=alpha) {
653 sum1 += last_li1;
654 sum2 += last_li2;
655 u_1 = 1.0-u;
656 denom = 1.0/(u_1*u_1*t1);
657 k1 = (t3 + u*t2)*u_1*denom;
658 k2 = (t6 + u*t5 + u*u*t4)*denom - k1*k1;
659 line_integrals(k1,k2,I1,Ix);
660 denom *= u / u_1;
661 last_li1 = ((vm+u*vt1)*I1 + u_1*vt2*Ix) * denom;
662 last_li2 = I1 * denom;
663 }
664 sum1 *= weight;
665 sum1 += last_li1/alpha;
666 sum2 *= weight;
667 sum2 += last_li2/alpha;
668
669 // add the last trapezoid covering the remaining area
670 denom = 1.0/t1;
671 k1 = t3*denom;
672 k2 = t6*denom - k1*k1;
673 line_integrals(k1,k2,I1,Ix);
674 denom *= u/alpha;
675 sum1 += (vm*I1 + vt2*Ix) * denom;
676 sum2 += I1 * denom;
677
678 sum1 *= height;
679 sum2 *= height;
680
681
682 return {sum1,sum2};
683 }
684
685
686 //: area integral of the squared weight function times a linearly interpolated value
687 // Also computes vector term used in the derivative
688 // \a m is the point closest point on the triangle to sample point \a x
689 // \a p0 and \a p1 are the other vertices
690 // call triangle_quadrature to first split an arbitrary triangle
691 // \a eps2 is epsilon^2
692 imesh_imls_surface::integral_data imesh_imls_surface::
split_triangle_quadrature_with_deriv(const vgl_point_3d<double> & x,const vgl_point_3d<double> & pm,const vgl_point_3d<double> & p1,const vgl_point_3d<double> & p2,double vm,double v1,double v2,double eps)693 split_triangle_quadrature_with_deriv(const vgl_point_3d<double>& x,
694 const vgl_point_3d<double>& pm,
695 const vgl_point_3d<double>& p1,
696 const vgl_point_3d<double>& p2,
697 double vm, double v1, double v2,
698 double eps)
699 {
700 vgl_point_3d<double> pp(p1), pn(p2);
701 double vp(v1), vn(v2);
702 if ((pp-x).length() > (pn-x).length()) {
703 // swap so that pp is closest to x
704 pp = p2; pn = p1;
705 vp = v2; vn = v1;
706 }
707
708 vgl_vector_3d<double> d1(pp-pm);
709 vgl_vector_3d<double> d2(pn-pm);
710 vgl_vector_3d<double> d3(pm-x);
711
712 double t1 = d1.sqr_length();
713 double t2 = dot_product(d1,d2);
714 double t3 = dot_product(d1,d3);
715 double t4 = d2.sqr_length();
716 double t5 = dot_product(d2,d3) * 2;
717 double t6 = d3.sqr_length() + eps;
718
719 // compute height (divided by 2*sqrt(t1))
720 // early exit if triangle flat
721 double height = t4/t1 - t2*t2/(t1*t1);
722 if (!(height > 0.0))
723 return {};
724 height = std::sqrt(height)/2.0;
725
726 double vt1 = vn-vm;
727 double vt2 = vp-vm;
728
729 double alpha = 2.0/3.0;
730 integral_data i_data, last_i_data;
731 double weight = (1.0/alpha-alpha);
732 double I1,Ix,dI1,dIx,dIx2,u_1,denom,k1,k2;
733 double u = alpha;
734 // integrate using the trapezoid rule with non-uniform sampling
735 constexpr double lower_bound = 0.01;//((t6<t4)?(t6/t4):1.0) * 0.01;
736 for (; u>lower_bound; u*=alpha) {
737 i_data += last_i_data;
738 u_1 = 1.0-u;
739 denom = 1.0/(u_1*u_1*t1);
740 k1 = (t3 + u*t2)*u_1*denom;
741 k2 = (t6 + u*t5 + u*u*t4)*denom - k1*k1;
742 line_integrals(k1,k2,I1,Ix,dI1,dIx,dIx2);
743 double phi_c = vm+u*vt1;
744 double phi_x = u_1*vt2;
745 last_i_data.I = I1;
746 last_i_data.I_phi = (phi_c*I1 + phi_x*Ix);
747
748 vgl_vector_3d<double> d_c(d3+u*d2), d_x(d1*u_1);
749 last_i_data.dI = (d_c*dI1 + d_x*dIx)*denom;
750 last_i_data.dI_phi = ( d_c*(phi_c*dI1 + phi_x*dIx)
751 + d_x*(phi_c*dIx + phi_x*dIx2) ) * denom;
752
753 denom *= u / u_1;
754 last_i_data *= denom;
755 }
756 i_data *= weight;
757 last_i_data *= 1.0/alpha;
758 i_data += last_i_data;
759
760
761 // add the last trapezoid covering the remaining area
762 denom = 1.0/t1;
763 k1 = t3*denom;
764 k2 = t6*denom - k1*k1;
765 line_integrals(k1,k2,I1,Ix,dI1,dIx,dIx2);
766 denom *= u/alpha;
767
768 i_data.I += I1 * denom;
769 i_data.I_phi += (vm*I1 + vt2*Ix) * denom;
770 denom /= t1;
771 i_data.dI += (d3*dI1 + d1*dIx)*denom;
772 i_data.dI_phi += ( d3*(vm*dI1 + vt2*dIx)
773 + d1*(vm*dIx + vt2*dIx2) ) * denom;
774
775 i_data *= height;
776 i_data.dI *= 4.0;
777 i_data.dI_phi *= 4.0;
778
779 return i_data;
780 }
781
782
783 //=============================================================================
784 // External functions
785
786 //: find the zero crossing point by bisection between positive point \a pp and negative point \a pn
787 // Stops searching when $||pp-pn|| < xeps$ or $|f(pm)| < feps$
bisect(const imesh_imls_surface & f,vgl_point_3d<double> pp,vgl_point_3d<double> pn,double feps,double xeps)788 vgl_point_3d<double> bisect(const imesh_imls_surface& f,
789 vgl_point_3d<double> pp,
790 vgl_point_3d<double> pn,
791 double feps, double xeps)
792 {
793 assert(f(pp) > 0.0);
794 assert(f(pn) < 0.0);
795 vgl_point_3d<double> pm=centre(pp,pn);
796 const unsigned num_itr =
797 static_cast<unsigned>(std::ceil(std::log((pp-pn).length()
798 / xeps)
799 / 0.301029995663981)); // log_2
800 vgl_vector_3d<double> dp;
801 double val = f.deriv(pm,dp);
802 val /= dp.length();
803 for (unsigned int i=0; i<num_itr; ++i) {
804 if (std::abs(val) < feps)
805 return pm;
806 else if (val > 0.0)
807 pp = pm;
808 else
809 pn = pm;
810 pm=centre(pp,pn);
811 val = f.deriv(pm,dp);
812 val /= dp.length();
813 }
814 return pm;
815 }
816
817
818 //: Move the point \a p along the gradient direction until reaching a zero crossing of \a f (within \a eps).
819 // Return true if successful
snap_to_surface(const imesh_imls_surface & f,vgl_point_3d<double> & p,double step,double eps)820 bool snap_to_surface(const imesh_imls_surface& f,
821 vgl_point_3d<double>& p,
822 double step, double eps)
823 {
824 vgl_point_3d<double> p1(p);
825 vgl_vector_3d<double> dp;
826 double val1 = f.deriv(p1,dp);
827 double dl = dp.length();
828 val1 /= dl;
829 if (std::abs(val1) < eps)
830 return true;
831
832 vgl_point_3d<double> p2 = p1 - (step*val1/dl)*dp;
833 dl = dp.length();
834 double val2 = f.deriv(p2,dp);
835 val2 /= dl;
836 unsigned int i=0;
837 for (; i<100 && val1*val2 > 0.0; ++i) {
838 p1 = p2;
839 val1 = val2;
840 p2 -= (step*val2/dl)*dp;
841 val2 = f.deriv(p2,dp);
842 dl = dp.length();
843 val2 /= dl;
844 if (std::abs(val2) < eps) {
845 p = p2;
846 return true;
847 }
848 }
849 if (i >= 100)
850 return false;
851
852 if (val1 > 0.0)
853 p = bisect(f,p1,p2,eps);
854 else
855 p = bisect(f,p2,p1,eps);
856
857
858 return true;
859 }
860
861
862 namespace{
func(const vgl_vector_3d<double> & n,double v,const vgl_vector_3d<double> & dp)863 double func(const vgl_vector_3d<double>& n,
864 double v,
865 const vgl_vector_3d<double>& dp)
866 {
867 v *= v;
868 v /= dp.sqr_length();
869 double tmp = dot_product(n,dp)/dp.length() - 1.0;
870 return v + tmp*tmp;
871 }
872
dfunc(const vgl_vector_3d<double> & n,double v,const vgl_vector_3d<double> & dp,const vnl_double_3x3 & ddp)873 vgl_vector_3d<double> dfunc(const vgl_vector_3d<double>& n,
874 double v,
875 const vgl_vector_3d<double>& dp,
876 const vnl_double_3x3& ddp)
877 {
878 vnl_double_3 nn(n.x(),n.y(),n.z());
879 vnl_double_3 ndp(dp.x(), dp.y(), dp.z());
880 double sqr_len = dp.sqr_length();
881 double len = std::sqrt(sqr_len);
882 double n_dot_dp = dot_product(nn,ndp);
883 vnl_double_3 df = (2*v/sqr_len)*ndp;
884 df += ddp.transpose() * ( ((-2*v*v/(sqr_len*sqr_len))*ndp) +
885 (2/len*(n_dot_dp/len - 1)*(nn - (n_dot_dp/sqr_len)*ndp)) );
886 return {df[0],df[1],df[2]};
887 }
888 // end of namespace
889 }
890
891 //: Move the point \a p to minimize $(f^2 + (n*f' - 1)^2)/f'*f'$ a zero crossing of \a f (within \a eps).
892 // Return true if successful
snap_to_surface_with_normal(const imesh_imls_surface & f,vgl_point_3d<double> & p,vgl_vector_3d<double> n,double step,double eps)893 bool snap_to_surface_with_normal(const imesh_imls_surface& f,
894 vgl_point_3d<double>& p,
895 vgl_vector_3d<double> n,
896 double step, double eps)
897 {
898 vgl_point_3d<double> p1(p);
899 normalize(n);
900 vgl_vector_3d<double> dp;
901 vnl_double_3x3 ddp;
902 double val = f.deriv2(p1, dp, ddp);
903 double f1 = func(n,val,dp);
904 if (f1 < eps)
905 return true;
906
907 vgl_vector_3d<double> df = dfunc(n,val,dp,ddp);
908 double dl = df.sqr_length();
909 unsigned int i;
910 for (i=0; i<1000; ++i) {
911 vgl_point_3d<double> p2 = p1 - (step*f1/dl)*df;
912 val = f.deriv2(p2,dp,ddp);
913 double f2 = func(n,val,dp);
914 //std::cout << i<<" f: "<<f2<<" step: "<< step<<std::endl;
915 if ( f2 > f1) {
916 step /= 2;
917 continue;
918 }
919 if (f2 < eps || step < eps) {
920 p = p2;
921 return true;
922 }
923 f1 = f2;
924 p1 = p2;
925 df = dfunc(n,val,dp,ddp);
926 dl = df.sqr_length();
927 step *= 2;
928 }
929 if (i >= 100)
930 return true;
931
932 p = p1;
933 return true;
934 }
935
936
937 //: Move the point \a p along direction \a dir until reaching a zero crossing of \a f (within \a eps).
938 // Return true if successful
snap_to_surface(const imesh_imls_surface & f,vgl_vector_3d<double> dir,vgl_point_3d<double> & p,double step,double eps)939 bool snap_to_surface(const imesh_imls_surface& f,
940 vgl_vector_3d<double> dir,
941 vgl_point_3d<double>& p,
942 double step, double eps)
943 {
944 vgl_point_3d<double> p1(p);
945 normalize(dir);
946 vgl_vector_3d<double> dp;
947 double val1 = f.deriv(p1,dp);
948 dp = dir * dot_product(dp,dir);
949 double dl = dp.length();
950 val1 /= dl;
951 if (std::abs(val1) < eps)
952 return true;
953
954 vgl_point_3d<double> p2 = p1 - (step*val1/dl)*dp;
955 dl = dp.length();
956 double val2 = f.deriv(p2,dp);
957 val2 /= dl;
958 unsigned int i=0;
959 for (; i<100 && val1*val2 > 0.0; ++i) {
960 p1 = p2;
961 val1 = val2;
962 p2 -= (step*val2/dl)*dp;
963 val2 = f.deriv(p2,dp);
964 dp = dir * dot_product(dp,dir);
965 dl = dp.length();
966 val2 /= dl;
967 if (std::abs(val2) < eps) {
968 p = p2;
969 return true;
970 }
971 }
972 if (i >= 100)
973 return false;
974
975 if (val1 > 0.0)
976 p = bisect(f,p1,p2,eps);
977 else
978 p = bisect(f,p2,p1,eps);
979
980
981 return true;
982 }
983