43 #include "ICPPlugin.hh" 44 #include <QGridLayout> 45 #include <QPushButton> 49 ICPPlugin::ICPPlugin() :
56 ICPPlugin::~ICPPlugin()
61 void ICPPlugin::initializePlugin()
63 if ( OpenFlipper::Options::gui() ) {
66 connect( tool_->btnICP, SIGNAL(clicked()),
this, SLOT(toolbarICP()) );
68 QLabel* label = tool_->img_step_1;
69 QPixmap pixmap(OpenFlipper::Options::iconDirStr()+OpenFlipper::Options::dirSeparator()+
"icp_step1.png");
70 label->setPixmap(pixmap);
71 label->setMask(pixmap.mask());
75 toolIcon_ =
new QIcon(OpenFlipper::Options::iconDirStr()+OpenFlipper::Options::dirSeparator()+
"ICPPluginIcon.png");
76 emit addToolbox( tr(
"ICP") , tool_, toolIcon_ );
81 void ICPPlugin::pluginsInitialized() {
89 static bool compare_ev(
const Eigen::VectorXd& _lhs,
const Eigen::VectorXd& _rhs) {
90 return std::abs(_lhs(_lhs.rows()-1)) > std::abs(_rhs(_rhs.rows()-1));
96 static Eigen::MatrixXd sorted_cols_by_ev(Eigen::MatrixXd _A, Eigen::MatrixXd _EV)
99 _A.conservativeResize(_A.rows()+1, _A.cols());
100 for (int64_t i=0;i<_A.cols();i++) {
101 _A(_A.rows()-1, i) = _EV(i, 0);
103 std::vector<Eigen::VectorXd> vec;
104 for (int64_t i = 0; i < _A.cols(); ++i)
105 vec.push_back(_A.col(i));
108 std::sort(vec.begin(), vec.end(), &compare_ev);
110 for (
unsigned int i = 0; i < _A.cols(); ++i)
120 template<
typename MeshT >
129 for (
auto v_it : _mesh->vertices() ) {
135 typename MeshT::Normal n = invTranspMat.
transform_vector(_mesh->normal(v_it));
139 _mesh->set_normal(v_it,n);
142 for (
auto f_it : _mesh->faces() ) {
145 typename MeshT::Normal n = invTranspMat.
transform_vector(_mesh->normal(f_it));
149 _mesh->set_normal(f_it,n);
156 static void getMeshPoints(TriMesh* _mesh,
ICPContext* _context, VertexList* _result) {
157 unsigned long counter = 0;
159 for (
auto v_it : _mesh->vertices() ) {
161 if (counter % 10000 == 0) {
162 if (_context->params_->debugOutput_)
163 std::cout << counter <<
"/" << _mesh->n_vertices() <<
" mesh point copy" << std::endl << std::flush;
165 PolyMesh::VertexHandle point = v_it;
167 _result->push_back(point);
174 static void findAllNearestPoints(VertexList &_sourcePoints,
ICPContext* _context, PointList* _result) {
176 for (VertexList::iterator it = _sourcePoints.begin() ; it != _sourcePoints.end() ; ++it) {
177 PolyMesh::VertexHandle closest;
178 double closestDistance = DBL_MAX;
179 PolyMesh::Point referencePoint = _context->sourceMesh_->point(*it);
183 for (
auto it2 : _context->targetMesh_->vertices()) {
184 PolyMesh::Point delta = referencePoint - _context->targetMesh_->point(it2);
185 double distance = delta[0]*delta[0] + delta[1]*delta[1] + delta[2]*delta[2];
186 if (distance < 0) distance *= -1;
187 if (distance < closestDistance) {
189 closestDistance = distance;
196 info.point_ = _context->targetMesh_->point(closest);
197 info.normal_ = _context->targetMesh_->normal(closest);
198 _result->push_back(info);
205 static void findAllNearestPointsBSP(VertexList &_sourcePoints,
ICPContext* _context, PointList* _result) {
206 if (_context->params_->debugOutput_)
207 std::cout <<
"generate BSP ... " << std::flush;
212 if (_context->params_->debugOutput_)
213 std::cout <<
"done. nearest point calculation" << std::endl << std::flush;
215 unsigned long long counter = 0;
218 for (VertexList::iterator it = _sourcePoints.begin() ; it != _sourcePoints.end() ; ++it) {
220 if (counter % 1000 == 0) {
221 if (_context->params_->debugOutput_)
222 std::cout << counter <<
"/" << _sourcePoints.
size() <<
" nearest point calculation" << std::endl << std::flush;
226 PolyMesh::Point point = _context->sourceMesh_->point(*it);
227 TriMeshObject::OMTriangleBSP::NearestNeighbor nearest = targetBSP->
nearest(point);
228 PolyMesh::FaceHandle face = nearest.handle;
229 PolyMesh::HalfedgeHandle he = _context->targetMesh_->halfedge_handle(face);
230 PolyMesh::VertexHandle vh = _context->targetMesh_->to_vertex_handle(he);
231 PolyMesh::Point pivot = _context->targetMesh_->point(vh);
238 info.point_ = projected;
239 info.normal_ = faceNormal;
244 PolyMesh::VertexHandle adjacentVH[3];
245 auto faceIterator = _context->targetMesh_->fv_iter(face);
247 if (faceIterator.is_valid()) { adjacentVH[0] = *faceIterator; faceIterator++; }
else error =
true;
248 if (faceIterator.is_valid()) { adjacentVH[1] = *faceIterator; faceIterator++; }
else error =
true;
249 if (faceIterator.is_valid()) { adjacentVH[2] = *faceIterator; faceIterator++; }
else error =
true;
253 projectedACG[0] = projected[0];
254 projectedACG[1] = projected[1];
255 projectedACG[2] = projected[2];
257 if (!error && _context->params_->interpolateNormals_) {
259 for (
int i=0;i<3;i++) {
260 const PolyMesh::Point p1 = _context->targetMesh_->point(adjacentVH[i]);
261 adjacentV[i][0] = p1[0];
262 adjacentV[i][1] = p1[1];
263 adjacentV[i][2] = p1[2];
273 baryCoord[0] * _context->targetMesh_->normal(adjacentVH[0]) +
274 baryCoord[1] * _context->targetMesh_->normal(adjacentVH[1]) +
275 baryCoord[2] * _context->targetMesh_->normal(adjacentVH[2])
279 if (_context->params_->debugOutput_)
280 std::cout <<
"barycoord failed" << std::endl << std::flush;
283 if (_context->params_->debugOutput_)
284 std::cout <<
"circulator failed" << std::endl << std::flush;
287 _result->push_back(info);
294 static double mse(VertexList &_pointsSource, PointList &_pointsTarget,
ICPContext* _context) {
296 VertexList::iterator itSource = _pointsSource.begin();
297 PointList::iterator itTarget = _pointsTarget.begin();
300 for (
unsigned int i=0;i<_pointsSource.size();i++) {
301 PolyMesh::VertexHandle source = *itSource;
302 PolyMesh::Point target = itTarget->point_;
303 PolyMesh::Point delta = target-_context->sourceMesh_->point(source);
305 sum += delta[0]*delta[0] + delta[1]*delta[1] + delta[2]*delta[2];
306 ++itSource; ++itTarget;
309 return sum /
static_cast<double>(_pointsSource.size());
315 static PolyMesh::Point calculateCOG(VertexList& _points, TriMesh* _mesh) {
316 PolyMesh::Point sum(0,0,0);
317 for (VertexList::iterator it=_points.begin() ; it != _points.end() ; ++it) {
318 sum += _mesh->point(*it);
320 return sum /
static_cast<double>(_points.size());
326 static PolyMesh::Point calculateCOG(PointList& _points) {
327 PolyMesh::Point sum(0,0,0);
328 for (PointList::iterator it=_points.begin() ; it != _points.end() ; ++it) {
331 return sum /
static_cast<double>(_points.size());
337 template <
typename VectorT >
338 static VectorT calculateCOG(
const std::vector<VectorT>& _points) {
340 for (
unsigned int i=0;i<sum.dim();i++) sum[i] = 0;
342 for (
unsigned int i=0;i<_points.size();i++) {
346 return sum /
static_cast<double>(_points.size());
352 static double calculateSize(VertexList* _points, TriMesh* _mesh, PolyMesh::Point &_origin) {
354 for (VertexList::iterator it=_points->begin() ; it != _points->end() ; ++it) {
355 PolyMesh::Point p = _mesh->point(*it);
356 PolyMesh::Point delta = p - _origin;
358 sum += (delta[0]*delta[0] + delta[1]*delta[1] + delta[2]*delta[2]);
361 sum = std::sqrt(sum);
363 sum /=
static_cast<double>(_points->size());
371 static double calculateSize(PointList* _points, PolyMesh::Point &_origin) {
373 for (PointList::iterator it=_points->begin() ; it != _points->end() ; ++it) {
374 PolyMesh::Point p = it->point_;
375 PolyMesh::Point delta = p - _origin;
377 sum += (delta[0]*delta[0] + delta[1]*delta[1] + delta[2]*delta[2]);
380 sum = std::sqrt(sum);
382 sum /=
static_cast<double>(_points->size());
391 static void deleteNonPairs(VertexList &_sourceP, PointList &_targetP,
ICPContext* _context) {
392 if (_context->params_->debugOutput_)
393 std::cout <<
"delete non pairs" << std::endl << std::flush;
395 VertexList::iterator itSource = _sourceP.begin();
396 PointList::iterator itTarget = _targetP.begin();
398 const double distanceThreshold = _context->params_->distanceThreshold_;
399 const double distanceThreasholdSquared = distanceThreshold * distanceThreshold;
401 const double normalDotThreshold = _context->params_->normalDotThreshold_ / 100.0;
403 unsigned long rmDistance = 0;
404 unsigned long rmNormal = 0;
407 while (itSource != _sourceP.end()) {
408 PolyMesh::Point source = _context->sourceMesh_->point(*itSource);
409 PolyMesh::Point target = itTarget->point_;
414 PolyMesh::Point delta = target - source;
416 double distanceSquared = delta[0]*delta[0] + delta[1]*delta[1] + delta[2]*delta[2];
417 double normalDot = sourceN[0]*targetN[0] + sourceN[1]*targetN[1] + sourceN[2]*targetN[2];
423 if (distanceSquared > distanceThreasholdSquared) {
428 _sourceP.erase(itSource++);
429 _targetP.erase(itTarget++);
432 }
else if ( normalDot < normalDotThreshold || normalDot < 0.0) {
437 _sourceP.erase(itSource++);
438 _targetP.erase(itTarget++);
447 if (_context->params_->debugOutput_)
448 std::cout <<
"after deletion " << _sourceP.size() <<
" points left | rmDistance:" << rmDistance <<
",rmNormal:" << rmNormal << std::endl << std::flush;
454 template <
typename VectorT >
455 static Eigen::MatrixXd estimatedRigidTransform(
const std::vector<VectorT>& _sourceCloud,
const std::vector<VectorT>& _targetCloud) {
456 assert(_sourceCloud.size() == _targetCloud.size());
457 unsigned int dim = 3;
459 VectorT assertVector;
460 dim = assertVector.dim();
464 VectorT cogSource = calculateCOG(_sourceCloud);
465 VectorT cogTarget = calculateCOG(_targetCloud);
467 Eigen::MatrixXd centroid_A(dim,1);
468 Eigen::MatrixXd centroid_B(dim,1);
470 for (
unsigned int i=0;i<dim;i++) {
471 centroid_A(i,0) = cogSource[i];
472 centroid_B(i,0) = cogTarget[i];
475 Eigen::MatrixXd Am(dim, _sourceCloud.size());
476 Eigen::MatrixXd Bm(dim, _targetCloud.size());
479 for (
unsigned int i=0;i<_sourceCloud.size();i++) {
480 VectorT a = _sourceCloud[i];
481 VectorT b = _targetCloud[i];
483 for (
unsigned int d=0 ; d<dim ; d++) {
484 Am(d, i) = a[d] - cogSource[d];
485 Bm(d, i) = b[d] - cogTarget[d];
490 Eigen::MatrixXd H = Am * Bm.transpose();
491 Eigen::JacobiSVD<Eigen::MatrixXd> svd(H, Eigen::ComputeFullU | Eigen::ComputeFullV);
493 Eigen::MatrixXd R = svd.matrixV() * svd.matrixU().transpose();
495 if (R.determinant() < 0) {
496 Eigen::MatrixXd V = svd.matrixV();
498 for (
unsigned int i=0 ; i<dim ; i++) {
499 V(i,dim-1) = V(i,dim-1) * -1.0;
502 R = V * svd.matrixU().transpose();
505 Eigen::MatrixXd t = -R * centroid_A + centroid_B;
507 R.conservativeResize(R.rows()+1, R.cols()+1);
509 for (
unsigned int i=0;i<dim+1;i++) {
510 R(dim, i) = i==dim ? 1 : 0;
511 R(i, dim) = i==dim ? 1 : t(i, 0);
521 assert(_sourceP.size() == _targetP.size());
523 std::vector<ACG::Vec3d> sourceCloud(_sourceP.size()), targetCloud(_sourceP.size());
524 VertexList::iterator iterA = _sourceP.begin();
525 PointList::iterator iterB = _targetP.begin();
527 for (
unsigned int i=0;i<_sourceP.size();i++) {
528 sourceCloud[i] = _context->sourceMesh_->point(*iterA);
529 targetCloud[i] = iterB->point_;
535 Eigen::MatrixXd rotEigen = estimatedRigidTransform(sourceCloud, targetCloud);
539 if (_context->params_->debugOutput_)
540 std::cout <<
"Final rotation matrix:" << std::endl << rotEigen << std::endl << std::flush;
542 for (
unsigned int x=0;x<3;x++) {
543 for (
unsigned int y=0;y<3;y++) {
544 rot(x,y) = rotEigen(x,y);
554 static void debugOutPairs(
ICPContext* _context, VertexList& _source, PointList& _target) {
555 if (!_context->params_->debugOutput_)
return;
557 VertexList::iterator sourceIt = _source.begin();
558 PointList::iterator targetIt = _target.begin();
560 for (;sourceIt != _source.end();) {
562 PolyMesh::Point a = _context->sourceMesh_->point(*sourceIt);
563 PolyMesh::Point b = targetIt->point_;
564 double dist = (a[0]-b[0])*(a[0]-b[0]) + (a[1]-b[1])*(a[1]-b[1]) + (a[2]-b[2])*(a[2]-b[2]);
565 dist = std::sqrt(dist);
566 std::cout << a <<
" -> " << b <<
" distance: " << dist << std::endl << std::flush;
577 const int maxIterations = _context->params_->maxIterations_;
578 const double errorThreshold = _context->params_->errorThreshold_;
580 double currentError = DBL_MAX;
583 for (i=0; (i<maxIterations && currentError > errorThreshold) || maxIterations == 0 ; i++) {
584 VertexList meshPointsSource;
585 getMeshPoints(_context->sourceMesh_, _context, &meshPointsSource);
587 if (_context->params_->debugOutput_)
588 std::cout <<
"ICP Iteration " << i+1 <<
"/" << maxIterations <<
" mse: " << ( (currentError<DBL_MAX-1e3) ? currentError : -1.0 ) << std::endl << std::flush;
591 PointList closestsPointOnTarget;
592 findAllNearestPointsBSP(meshPointsSource, _context, &closestsPointOnTarget);
595 deleteNonPairs(meshPointsSource, closestsPointOnTarget, _context);
598 if (meshPointsSource.size() <=6) {
599 if (_context->params_->debugOutput_)
600 std::cout <<
"ICP not enough points" << std::endl << std::flush;
605 PolyMesh::Point cogSource = calculateCOG(meshPointsSource, _context->sourceMesh_);
608 double sizeSource = calculateSize(&meshPointsSource, _context->sourceMesh_, cogSource);
609 double sizeTarget = calculateSize(&closestsPointOnTarget, cogTarget);
611 double sizeAvg = (1.0/sizeSource+1.0/sizeTarget)/2.0;
612 if (_context->params_->doResize_)
613 _context->params_->distanceThreshold_ *= sizeAvg;
615 if (_context->params_->debugOutput_)
616 std::cout <<
"translate source by " << -cogSource <<
" and scale by " << 1.0/sizeSource << std::endl
617 <<
"translate target by " << -cogTarget <<
" and scale by " << 1.0/sizeTarget << std::endl << std::flush;
619 ACG::GLMatrixd rotMat = calculateRotationMatrix(meshPointsSource, closestsPointOnTarget, _context);
621 if (maxIterations == 0) {
627 _context->sourceMesh_);
629 cogSource = calculateCOG(meshPointsSource, _context->sourceMesh_);
630 cogTarget = calculateCOG(closestsPointOnTarget);
638 _context->sourceMesh_);
644 currentError = mse(meshPointsSource, closestsPointOnTarget, _context);
647 if (_context->params_->debugOutput_)
648 std::cout <<
"Exited ICP with error: " << currentError <<
" after " << i <<
"/" << maxIterations <<
" iterations" << std::endl << std::flush;
658 void ICPPlugin::icp(
int _maxIterations,
double _errorThreshold,
double _distanceThreshold,
double _normalDotThreshold,
bool _debugOutput,
bool _doResize,
bool _interpolateNormals,
int _sourceObjectID,
int _targetObjectID) {
661 icpParams.distanceThreshold_ = _distanceThreshold;
662 icpParams.errorThreshold_ = _errorThreshold;
663 icpParams.maxIterations_ = _maxIterations;
664 icpParams.normalDotThreshold_ = _normalDotThreshold;
665 icpParams.debugOutput_ = _debugOutput;
666 icpParams.doResize_ = _doResize;
667 icpParams.interpolateNormals_ = _interpolateNormals;
674 icpContext.sourceID_ = _sourceObjectID;
675 icpContext.targetID_ = _targetObjectID;
676 icpContext.params_ = &icpParams;
687 if(OpenFlipper::Options::nogui()) {
688 emit log(
LOGERR,
"no gui detected - use icp(...) instead");
694 icpParams.distanceThreshold_ = this->tool_->icp_distanceThreshold->value();
695 icpParams.errorThreshold_ = this->tool_->icp_errorThreshold->value();
696 icpParams.maxIterations_ = this->tool_->icp_maxIterations->value();
697 icpParams.normalDotThreshold_ = this->tool_->icp_normalDotThreshold->value();
698 icpParams.debugOutput_ = this->tool_->ck_debugOutput->isChecked();
699 icpParams.doResize_ = this->tool_->ck_doResize->isChecked();
700 icpParams.interpolateNormals_ = this->tool_->ck_interpolateNormals->isChecked();
703 icpContext.sourceMesh_ =
nullptr;
704 icpContext.targetMesh_ =
nullptr;
705 icpContext.sourceObject_ =
nullptr;
706 icpContext.targetObject_ =
nullptr;
707 icpContext.sourceID_ = icpContext.targetID_ = -1;
708 icpContext.params_ = &icpParams;
713 if (icpContext.targetMesh_ ==
nullptr) {
715 icpContext.targetID_ = o_it->id();
718 emit log(
LOGERR,
"Only one target is supported");
721 emit log(
LOGERR,
"DataType not supported.");
724 if (icpContext.targetMesh_ ==
nullptr) {
725 emit log(
LOGERR,
"no target selected");
733 icpContext.sourceID_ = o_it->id();
738 emit log(
LOGERR,
"DataType not supported.");
#define DATA_TRIANGLE_MESH
OMTriangleBSP * requestTriangleBsp()
void doICP(ICPContext *_context)
Kernel::Normal Normal
Normal type.
void transpose()
transpose matrix
Kernel::Point Point
Coordinate type.
void translate(Scalar _x, Scalar _y, Scalar _z, MultiplyFrom _mult_from=MULT_FROM_RIGHT)
multiply self with translation matrix (x,y,z)
void icp(int _maxIterations, double _errorThreshold, double _distanceThreshold, double _normalDotThreshold, bool _debugOutput, bool _doResize, bool _interpolateNormals, int _sourceObjectID, int _targetObjectID)
TriMesh * triMesh(BaseObjectData *_object)
Get a triangle mesh from an object.
const QStringList SOURCE_OBJECTS("source")
Iterable object range.
void identity()
setup an identity matrix
VectorT< T, 3 > transform_point(const VectorT< T, 3 > &_v) const
transform point (x',y',z',1) = M * (x,y,z,1)
const UpdateType UPDATE_GEOMETRY(UpdateTypeSet(4))
Geometry updated.
void transformMesh(ACG::Matrix4x4d _matrix, MeshT &_mesh)
bool invert()
matrix inversion (returns true on success)
bool baryCoord(const VectorT< Scalar, 3 > &_p, const VectorT< Scalar, 3 > &_u, const VectorT< Scalar, 3 > &_v, const VectorT< Scalar, 3 > &_w, VectorT< Scalar, 3 > &_result)
VectorT< T, 3 > transform_vector(const VectorT< T, 3 > &_v) const
transform vector (x',y',z',0) = A * (x,y,z,0)
TriMeshObject * triMeshObject(BaseObjectData *_object)
Cast an BaseObject to a TriMeshObject if possible.
const QStringList TARGET_OBJECTS("target")
Iterable object range.
NearestNeighbor nearest(const Point &_p) const
Return handle of the nearest neighbor face.
ObjectRange objects(IteratorRestriction _restriction, DataType _dataType)
Iterable object range.
VectorT projectToPlane(const VectorT &_porigin, const VectorT &_pnormal, const VectorT &_point)
projects a point to a plane