igl::WindingNumberTree< Point, DerivedV, DerivedF > Class Template Reference

#include <src/libigl/igl/WindingNumberTree.h>

Inheritance diagram for igl::WindingNumberTree< Point, DerivedV, DerivedF >:

Collaboration diagram for igl::WindingNumberTree< Point, DerivedV, DerivedF >:

Public Member Functions
	WindingNumberTree ()
	WindingNumberTree (const Eigen::MatrixBase< DerivedV > &V, const Eigen::MatrixBase< DerivedF > &F)
	WindingNumberTree (const WindingNumberTree< Point, DerivedV, DerivedF > &parent, const Eigen::MatrixBase< DerivedF > &F)
virtual	~WindingNumberTree ()
void	delete_children ()
virtual void	set_mesh (const Eigen::MatrixBase< DerivedV > &V, const Eigen::MatrixBase< DerivedF > &F)
void	set_method (const WindingNumberMethod &m)
const DerivedV &	getV () const
const MatrixXF &	getF () const
const MatrixXF &	getcap () const
virtual void	grow ()
virtual bool	inside (const Point &p) const
DerivedV::Scalar	winding_number (const Point &p) const
DerivedV::Scalar	winding_number_all (const Point &p) const
DerivedV::Scalar	winding_number_boundary (const Point &p) const
void	print (const char *tab="")
virtual DerivedV::Scalar	max_abs_winding_number (const Point &p) const
virtual DerivedV::Scalar	max_simple_abs_winding_number (const Point &p) const
virtual DerivedV::Scalar	cached_winding_number (const WindingNumberTree &that, const Point &p) const

Static Public Attributes
static std::map< std::pair< const WindingNumberTree *, const WindingNumberTree * >, typename DerivedV::Scalar >	cached
static DerivedV	dummyV

Protected Types
typedef Eigen::Matrix< typename DerivedV::Scalar, Eigen::Dynamic, Eigen::Dynamic >	MatrixXS
typedef Eigen::Matrix< typename DerivedF::Scalar, Eigen::Dynamic, Eigen::Dynamic >	MatrixXF

Protected Attributes
WindingNumberMethod	method
const WindingNumberTree *	parent
std::list< WindingNumberTree * >	children
DerivedV &	V
MatrixXS	SV
MatrixXF	F
MatrixXF	cap
DerivedV::Scalar	radius
Point	center

Detailed Description

template<typename Point, typename DerivedV, typename DerivedF>
class igl::WindingNumberTree< Point, DerivedV, DerivedF >

Member Typedef Documentation

MatrixXF

template<typename Point , typename DerivedV , typename DerivedF >

typedef Eigen::Matrix<typename DerivedF::Scalar,Eigen::Dynamic,Eigen::Dynamic> igl::WindingNumberTree< Point, DerivedV, DerivedF >::MatrixXF

protected

MatrixXS

template<typename Point , typename DerivedV , typename DerivedF >

typedef Eigen::Matrix<typename DerivedV::Scalar,Eigen::Dynamic,Eigen::Dynamic> igl::WindingNumberTree< Point, DerivedV, DerivedF >::MatrixXS

protected

Constructor & Destructor Documentation

WindingNumberTree() [1/3]

template<typename Point , typename DerivedV , typename DerivedF >

igl::WindingNumberTree< Point, DerivedV, DerivedF >::WindingNumberTree

inline

                                                                       :
  method(EXACT_WINDING_NUMBER_METHOD),
  parent(NULL),
  V(dummyV),
  SV(),
  F(),
  //boundary(igl::boundary_facets<Eigen::MatrixXi,Eigen::MatrixXi>(F))
  cap(),
  radius(std::numeric_limits<typename DerivedV::Scalar>::infinity()),
  center(0,0,0)
{
}

References igl::EXACT_WINDING_NUMBER_METHOD.

WindingNumberTree() [2/3]

template<typename Point , typename DerivedV , typename DerivedF >

igl::WindingNumberTree< Point, DerivedV, DerivedF >::WindingNumberTree ( const Eigen::MatrixBase< DerivedV > &  V, const Eigen::MatrixBase< DerivedF > &  F  )

inline

                                       :
  method(EXACT_WINDING_NUMBER_METHOD),
  parent(NULL),
  V(dummyV),
  SV(),
  F(),
  //boundary(igl::boundary_facets<Eigen::MatrixXi,Eigen::MatrixXi>(F))
  cap(),
  radius(std::numeric_limits<typename DerivedV::Scalar>::infinity()),
  center(0,0,0)
{
  set_mesh(_V,_F);
}

References igl::WindingNumberTree< Point, DerivedV, DerivedF >::set_mesh().

Here is the call graph for this function:

WindingNumberTree() [3/3]

template<typename Point , typename DerivedV , typename DerivedF >

igl::WindingNumberTree< Point, DerivedV, DerivedF >::WindingNumberTree ( const WindingNumberTree< Point, DerivedV, DerivedF > &  parent, const Eigen::MatrixBase< DerivedF > &  F  )

inline

                                       :
  method(parent.method),
  parent(&parent),
  V(parent.V),
  SV(),
  F(_F),
  cap(triangle_fan(igl::exterior_edges(_F)))
{
}

~WindingNumberTree()

template<typename Point , typename DerivedV , typename DerivedF >

igl::WindingNumberTree< Point, DerivedV, DerivedF >::~WindingNumberTree

inlinevirtual

{
  delete_children();
}

Member Function Documentation

cached_winding_number()

template<typename Point , typename DerivedV , typename DerivedF >

DerivedV::Scalar igl::WindingNumberTree< Point, DerivedV, DerivedF >::cached_winding_number ( const WindingNumberTree< Point, DerivedV, DerivedF > &  that, const Point &  p  ) const

inlinevirtual

{
  using namespace std;
  // Simple metric for `is_far`
  //
  //   this             that
  //                   --------
  //   -----          /   |    \ .
  //  /  r  \        /    R     \ .
  // | p !   |      |     !      |
  //  \_____/        \          /
  //                  \________/
  //
  // 
  // a = angle formed by trapazoid formed by raising sides with lengths r and R
  // at respective centers.
  //
  // a = atan2(R-r,d), where d is the distance between centers
 
  // That should be bigger (what about parent? what about sister?)
  bool is_far = this->radius<that.radius;
  if(is_far)
  {
    typename DerivedV::Scalar a = atan2(
      that.radius - this->radius,
      (that.center - this->center).norm());
    assert(a>0);
    is_far = (a<PI/8.0);
  }
 
  if(is_far)
  {
    // Not implemented yet
    pair<const WindingNumberTree*,const WindingNumberTree*> this_that(this,&that);
    // Need to compute it for first time?
    if(cached.count(this_that)==0)
    {
      cached[this_that] = 
        that.winding_number_boundary(this->center);
    }
    return cached[this_that];
  }else if(children.size() == 0)
  {
    // not far and hierarchy ended too soon: can't use cache
    return that.winding_number_boundary(p);
  }else
  {
    for(
      typename list<WindingNumberTree<Point,DerivedV,DerivedF>* >::const_iterator cit = children.begin();
      cit != children.end();
      cit++)
    {
      if((*cit)->inside(p))
      {
        return (*cit)->cached_winding_number(that,p);
      }
    }
    // Not inside any children? This can totally happen because bounding boxes
    // are set to bound contained facets. So sibilings may overlap and their
    // union may not contain their parent (though, their union is certainly a
    // subset of their parent).
    assert(false);
  }
  return 0;
}

References igl::WindingNumberTree< Point, DerivedV, DerivedF >::center, igl::PI, igl::WindingNumberTree< Point, DerivedV, DerivedF >::radius, and igl::WindingNumberTree< Point, DerivedV, DerivedF >::winding_number_boundary().

Here is the call graph for this function:

delete_children()

template<typename Point , typename DerivedV , typename DerivedF >

void igl::WindingNumberTree< Point, DerivedV, DerivedF >::delete_children

inline

{
  using namespace std;
  // Delete children
  typename list<WindingNumberTree<Point,DerivedV,DerivedF>* >::iterator cit = children.begin();
  while(cit != children.end())
  {
    // clear the memory of this item
    delete (* cit);
    // erase from list, returns next element in iterator
    cit = children.erase(cit);
  }
}

getcap()

template<typename Point , typename DerivedV , typename DerivedF >

const igl::WindingNumberTree< Point, DerivedV, DerivedF >::MatrixXF & igl::WindingNumberTree< Point, DerivedV, DerivedF >::getcap

inline

{
  return cap;
}

getF()

template<typename Point , typename DerivedV , typename DerivedF >

const igl::WindingNumberTree< Point, DerivedV, DerivedF >::MatrixXF & igl::WindingNumberTree< Point, DerivedV, DerivedF >::getF

inline

{
  return F;
}

getV()

template<typename Point , typename DerivedV , typename DerivedF >

const DerivedV & igl::WindingNumberTree< Point, DerivedV, DerivedF >::getV

inline

{
  return V;
}

grow()

template<typename Point , typename DerivedV , typename DerivedF >

void igl::WindingNumberTree< Point, DerivedV, DerivedF >::grow

inlinevirtual

Reimplemented in igl::WindingNumberAABB< Point, DerivedV, DerivedF >.

{
  // Don't grow
  return;
}

inside()

template<typename Point , typename DerivedV , typename DerivedF >

bool igl::WindingNumberTree< Point, DerivedV, DerivedF >::inside ( const Point &  p ) const

inlinevirtual

Reimplemented in igl::WindingNumberAABB< Point, DerivedV, DerivedF >.

{
  return true;
}

max_abs_winding_number()

template<typename Point , typename DerivedV , typename DerivedF >

DerivedV::Scalar igl::WindingNumberTree< Point, DerivedV, DerivedF >::max_abs_winding_number ( const Point &  p ) const

inlinevirtual

Reimplemented in igl::WindingNumberAABB< Point, DerivedV, DerivedF >.

{
  return std::numeric_limits<typename DerivedV::Scalar>::infinity();
}

max_simple_abs_winding_number()

template<typename Point , typename DerivedV , typename DerivedF >

DerivedV::Scalar igl::WindingNumberTree< Point, DerivedV, DerivedF >::max_simple_abs_winding_number ( const Point &  p ) const

inlinevirtual

Reimplemented in igl::WindingNumberAABB< Point, DerivedV, DerivedF >.

{
  using namespace std;
  return numeric_limits<typename DerivedV::Scalar>::infinity();
}

print()

template<typename Point , typename DerivedV , typename DerivedF >

void igl::WindingNumberTree< Point, DerivedV, DerivedF >::print ( const char *  tab = "" )

inline

{
  using namespace std;
  // Print all facets
  cout<<tab<<"["<<endl<<F<<endl<<"]";
  // Print children
  for(
      typename list<WindingNumberTree<Point,DerivedV,DerivedF>* >::iterator cit = children.begin();
      cit != children.end();
      cit++)
  {
    cout<<","<<endl;
    (*cit)->print((string(tab)+"").c_str());
  }
}

set_mesh()

template<typename Point , typename DerivedV , typename DerivedF >

void igl::WindingNumberTree< Point, DerivedV, DerivedF >::set_mesh ( const Eigen::MatrixBase< DerivedV > &  V, const Eigen::MatrixBase< DerivedF > &  F  )

inlinevirtual

Reimplemented in igl::WindingNumberAABB< Point, DerivedV, DerivedF >.

{
  using namespace std;
  // Remove any exactly duplicate vertices
  // Q: Can this ever increase the complexity of the boundary?
  // Q: Would we gain even more by remove almost exactly duplicate vertices?
  MatrixXF SF,SVI,SVJ;
  igl::remove_duplicate_vertices(_V,_F,0.0,SV,SVI,SVJ,F);
  triangle_fan(igl::exterior_edges(F),cap);
  V = SV;
}

References igl::exterior_edges(), igl::remove_duplicate_vertices(), and igl::triangle_fan().

Referenced by igl::WindingNumberTree< Point, DerivedV, DerivedF >::WindingNumberTree(), and igl::WindingNumberAABB< Point, DerivedV, DerivedF >::set_mesh().

Here is the call graph for this function:

Here is the caller graph for this function:

set_method()

template<typename Point , typename DerivedV , typename DerivedF >

void igl::WindingNumberTree< Point, DerivedV, DerivedF >::set_method ( const WindingNumberMethod &  m )

inline

{
  this->method = m;
  for(auto child : children)
  {
    child->set_method(m);
  }
}

winding_number()

template<typename Point , typename DerivedV , typename DerivedF >

DerivedV::Scalar igl::WindingNumberTree< Point, DerivedV, DerivedF >::winding_number ( const Point &  p ) const

inline

{
  using namespace std;
  //cout<<"+"<<boundary.rows();
  // If inside then we need to be careful
  if(inside(p))
  {
    // If not a leaf then recurse
    if(children.size()>0)
    {
      // Recurse on each child and accumulate
      typename DerivedV::Scalar sum = 0;
      for(
        typename list<WindingNumberTree<Point,DerivedV,DerivedF>* >::const_iterator cit = children.begin();
        cit != children.end();
        cit++)
      {
        switch(method)
        {
          case EXACT_WINDING_NUMBER_METHOD:
            sum += (*cit)->winding_number(p);
            break;
          case APPROX_SIMPLE_WINDING_NUMBER_METHOD:
          case APPROX_CACHE_WINDING_NUMBER_METHOD:
            //if((*cit)->max_simple_abs_winding_number(p) > min_max_w)
            //{
              sum += (*cit)->winding_number(p);
            //}
            break;
          default:
            assert(false);
            break;
        }
      }
      return sum;
    }else
    {
      return winding_number_all(p);
    }
  }else{
    // Otherwise we can just consider boundary
    // Q: If we using the "multipole" method should we also subdivide the
    // boundary case?
    if((cap.rows() - 2) < F.rows())
    {
      switch(method)
      {
        case EXACT_WINDING_NUMBER_METHOD:
          return winding_number_boundary(p);
        case APPROX_SIMPLE_WINDING_NUMBER_METHOD:
        {
          typename DerivedV::Scalar dist = (p-center).norm();
          // Radius is already an overestimate of inside
          if(dist>1.0*radius)
          {
            return 0;
          }else
          {
            return winding_number_boundary(p);
          }
        }
        case APPROX_CACHE_WINDING_NUMBER_METHOD:
        {
          return parent->cached_winding_number(*this,p);
        }
        default: assert(false);break;
      }
    }else
    {
      // doesn't pay off to use boundary
      return winding_number_all(p);
    }
  }
  return 0;
}

References igl::APPROX_CACHE_WINDING_NUMBER_METHOD, igl::APPROX_SIMPLE_WINDING_NUMBER_METHOD, igl::EXACT_WINDING_NUMBER_METHOD, and igl::sum().

Referenced by igl::signed_distance(), and igl::signed_distance_winding_number().

Here is the call graph for this function:

Here is the caller graph for this function:

winding_number_all()

template<typename Point , typename DerivedV , typename DerivedF >

DerivedV::Scalar igl::WindingNumberTree< Point, DerivedV, DerivedF >::winding_number_all ( const Point &  p ) const

inline

{
  return igl::winding_number(V,F,p);
}

References igl::winding_number().

Here is the call graph for this function:

winding_number_boundary()

template<typename Point , typename DerivedV , typename DerivedF >

DerivedV::Scalar igl::WindingNumberTree< Point, DerivedV, DerivedF >::winding_number_boundary ( const Point &  p ) const

inline

{
  using namespace Eigen;
  using namespace std;
  return igl::winding_number(V,cap,p);
}

References igl::winding_number().

Referenced by igl::WindingNumberTree< Point, DerivedV, DerivedF >::cached_winding_number().

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

cached

template<typename Point , typename DerivedV , typename DerivedF >

std::map< std::pair< const igl::WindingNumberTree< Point, DerivedV, DerivedF > *, const igl::WindingNumberTree< Point, DerivedV, DerivedF > * >, typename DerivedV::Scalar > igl::WindingNumberTree< Point, DerivedV, DerivedF >::cached

static

cap

template<typename Point , typename DerivedV , typename DerivedF >

MatrixXF igl::WindingNumberTree< Point, DerivedV, DerivedF >::cap

protected

center

template<typename Point , typename DerivedV , typename DerivedF >

Point igl::WindingNumberTree< Point, DerivedV, DerivedF >::center

protected

Referenced by igl::WindingNumberTree< Point, DerivedV, DerivedF >::cached_winding_number().

children

template<typename Point , typename DerivedV , typename DerivedF >

std::list<WindingNumberTree * > igl::WindingNumberTree< Point, DerivedV, DerivedF >::children

protected

dummyV

template<typename Point , typename DerivedV , typename DerivedF >

DerivedV igl::WindingNumberTree< Point, DerivedV, DerivedF >::dummyV

static

F

template<typename Point , typename DerivedV , typename DerivedF >

MatrixXF igl::WindingNumberTree< Point, DerivedV, DerivedF >::F

protected

method

template<typename Point , typename DerivedV , typename DerivedF >

WindingNumberMethod igl::WindingNumberTree< Point, DerivedV, DerivedF >::method

protected

parent

template<typename Point , typename DerivedV , typename DerivedF >

const WindingNumberTree* igl::WindingNumberTree< Point, DerivedV, DerivedF >::parent

protected

radius

template<typename Point , typename DerivedV , typename DerivedF >

DerivedV::Scalar igl::WindingNumberTree< Point, DerivedV, DerivedF >::radius

protected

Referenced by igl::WindingNumberTree< Point, DerivedV, DerivedF >::cached_winding_number().

SV

template<typename Point , typename DerivedV , typename DerivedF >

MatrixXS igl::WindingNumberTree< Point, DerivedV, DerivedF >::SV

protected

V

template<typename Point , typename DerivedV , typename DerivedF >

DerivedV& igl::WindingNumberTree< Point, DerivedV, DerivedF >::V

protected

---

The documentation for this class was generated from the following file:

• src/libigl/igl/WindingNumberTree.h