igl::geodesic::GeodesicAlgorithmExact Class Reference

Inheritance diagram for igl::geodesic::GeodesicAlgorithmExact:

Collaboration diagram for igl::geodesic::GeodesicAlgorithmExact:

Public Types
enum	AlgorithmType { EXACT , DIJKSTRA , SUBDIVISION , UNDEFINED_ALGORITHM }

Public Member Functions
	GeodesicAlgorithmExact (geodesic::Mesh *mesh)
	~GeodesicAlgorithmExact ()
void	propagate (std::vector< SurfacePoint > &sources, double max_propagation_distance=GEODESIC_INF, std::vector< SurfacePoint > *stop_points=NULL)
void	trace_back (SurfacePoint &destination, std::vector< SurfacePoint > &path)
unsigned	best_source (SurfacePoint &point, double &best_source_distance)
void	print_statistics ()
void	geodesic (SurfacePoint &source, SurfacePoint &destination, std::vector< SurfacePoint > &path)
void	geodesic (std::vector< SurfacePoint > &sources, std::vector< SurfacePoint > &destinations, std::vector< std::vector< SurfacePoint > > &paths)
AlgorithmType	type ()
virtual std::string	name ()
geodesic::Mesh *	mesh ()

Protected Types
typedef std::pair< vertex_pointer, double >	stop_vertex_with_distace_type

Protected Member Functions
void	set_stop_conditions (std::vector< SurfacePoint > *stop_points, double stop_distance)
double	stop_distance ()

Protected Attributes
AlgorithmType	m_type
std::vector< stop_vertex_with_distace_type >	m_stop_vertices
double	m_max_propagation_distance
geodesic::Mesh *	m_mesh
double	m_time_consumed
double	m_propagation_distance_stopped

Private Types
enum	MapType { OLD , NEW }
typedef std::set< interval_pointer, Interval >	IntervalQueue

Private Member Functions
void	update_list_and_queue (list_pointer list, IntervalWithStop *candidates, unsigned num_candidates)
unsigned	compute_propagated_parameters (double pseudo_x, double pseudo_y, double d, double start, double end, double alpha, double L, bool first_interval, bool last_interval, bool turn_left, bool turn_right, IntervalWithStop *candidates)
void	construct_propagated_intervals (bool invert, edge_pointer edge, face_pointer face, IntervalWithStop *candidates, unsigned &num_candidates, interval_pointer source_interval)
double	compute_positive_intersection (double start, double pseudo_x, double pseudo_y, double sin_alpha, double cos_alpha)
unsigned	intersect_intervals (interval_pointer zero, IntervalWithStop *one)
interval_pointer	best_first_interval (SurfacePoint &point, double &best_total_distance, double &best_interval_position, unsigned &best_source_index)
bool	check_stop_conditions (unsigned &index)
void	clear ()
list_pointer	interval_list (edge_pointer e)
void	set_sources (std::vector< SurfacePoint > &sources)
void	initialize_propagation_data ()
void	list_edges_visible_from_source (MeshElementBase *p, std::vector< edge_pointer > &storage)
long	visible_from_source (SurfacePoint &point)
void	best_point_on_the_edge_set (SurfacePoint &point, std::vector< edge_pointer > const &storage, interval_pointer &best_interval, double &best_total_distance, double &best_interval_position)
void	possible_traceback_edges (SurfacePoint &point, std::vector< edge_pointer > &storage)
bool	erase_from_queue (interval_pointer p)

Private Attributes
IntervalQueue	m_queue
MemoryAllocator< Interval >	m_memory_allocator
std::vector< IntervalList >	m_edge_interval_lists
MapType	map [5]
double	start [6]
interval_pointer	i_new [5]
unsigned	m_queue_max_size
unsigned	m_iterations
SortedSources	m_sources

Detailed Description

Member Typedef Documentation

IntervalQueue

typedef std::set<interval_pointer, Interval> igl::geodesic::GeodesicAlgorithmExact::IntervalQueue

private

stop_vertex_with_distace_type

typedef std::pair<vertex_pointer, double> igl::geodesic::GeodesicAlgorithmBase::stop_vertex_with_distace_type

protectedinherited

Member Enumeration Documentation

AlgorithmType

enum igl::geodesic::GeodesicAlgorithmBase::AlgorithmType

inherited

Enumerator
EXACT
DIJKSTRA
SUBDIVISION
UNDEFINED_ALGORITHM

    {
        EXACT,
    DIJKSTRA,
        SUBDIVISION,
    UNDEFINED_ALGORITHM
    };

MapType

enum igl::geodesic::GeodesicAlgorithmExact::MapType

private

Enumerator
OLD
NEW

{OLD, NEW};   //used for interval intersection

Constructor & Destructor Documentation

GeodesicAlgorithmExact()

igl::geodesic::GeodesicAlgorithmExact::GeodesicAlgorithmExact ( geodesic::Mesh *  mesh )

inline

                                            :
      GeodesicAlgorithmBase(mesh),
    m_memory_allocator(mesh->edges().size(), mesh->edges().size()),
    m_edge_interval_lists(mesh->edges().size())
  {
    m_type = EXACT;
 
    for(unsigned i=0; i<m_edge_interval_lists.size(); ++i)
    {
      m_edge_interval_lists[i].initialize(&mesh->edges()[i]);
    }
  };  

References igl::geodesic::Mesh::edges(), igl::geodesic::GeodesicAlgorithmBase::EXACT, m_edge_interval_lists, igl::geodesic::GeodesicAlgorithmBase::m_type, and igl::geodesic::GeodesicAlgorithmBase::mesh().

Here is the call graph for this function:

~GeodesicAlgorithmExact()

igl::geodesic::GeodesicAlgorithmExact::~GeodesicAlgorithmExact ( )

inline

{};

Member Function Documentation

best_first_interval()

interval_pointer igl::geodesic::GeodesicAlgorithmExact::best_first_interval ( SurfacePoint &  point, double &  best_total_distance, double &  best_interval_position, unsigned &  best_source_index  )

inlineprivate

{
  assert(point.type() != UNDEFINED_POINT);
 
  interval_pointer best_interval = NULL;  
  best_total_distance = GEODESIC_INF;
 
  if(point.type() == EDGE)    
  {
    edge_pointer e = static_cast<edge_pointer>(point.base_element());
    list_pointer list = interval_list(e);
 
    best_interval_position = point.distance(e->v0());
    best_interval = list->covering_interval(best_interval_position);
    if(best_interval)
    {
      //assert(best_interval && best_interval->d() < GEODESIC_INF);
      best_total_distance = best_interval->signal(best_interval_position);
      best_source_index = best_interval->source_index();
    }
  }
  else if(point.type() == FACE)   
  {
    face_pointer f = static_cast<face_pointer>(point.base_element());
    for(unsigned i=0; i<3; ++i)
    {
      edge_pointer e = f->adjacent_edges()[i];
      list_pointer list = interval_list(e);
 
      double offset;
      double distance;
      interval_pointer interval;
 
      list->find_closest_point(&point, 
                   offset, 
                   distance, 
                   interval);
 
      if(interval && distance < best_total_distance)
      {
        best_interval = interval;
        best_total_distance = distance;
        best_interval_position = offset;
        best_source_index = interval->source_index();
      }
    }
 
      //check for all sources that might be located inside this face
    SortedSources::sorted_iterator_pair local_sources = m_sources.sources(f);
    for(SortedSources::sorted_iterator it=local_sources.first; it != local_sources.second; ++it)
    {
      SurfacePointWithIndex* source = *it;
      double distance = point.distance(source);
      if(distance < best_total_distance)
      {
        best_interval = NULL;
        best_total_distance = distance;
        best_interval_position = 0.0;
        best_source_index = source->index();
      }
    }
  }
  else if(point.type() == VERTEX)   
  {
    vertex_pointer v = static_cast<vertex_pointer>(point.base_element());
    for(unsigned i=0; i<v->adjacent_edges().size(); ++i)
    {
      edge_pointer e = v->adjacent_edges()[i];
      list_pointer list = interval_list(e);
      
      double position = e->v0()->id() == v->id() ? 0.0 : e->length();
      interval_pointer interval = list->covering_interval(position);
      if(interval)
      {
        double distance = interval->signal(position);
 
        if(distance < best_total_distance)
        {
          best_interval = interval;
          best_total_distance = distance;
          best_interval_position = position;
          best_source_index = interval->source_index();
        }
      }
    }
  }
 
  if(best_total_distance > m_propagation_distance_stopped)    //result is unreliable
  {
    best_total_distance = GEODESIC_INF;
    return NULL;
  }
  else
  {
    return best_interval;
  }
}

References igl::geodesic::MeshElementBase::adjacent_edges(), igl::geodesic::SurfacePoint::base_element(), igl::geodesic::IntervalList::covering_interval(), igl::geodesic::Point3D::distance(), igl::geodesic::EDGE, igl::geodesic::FACE, igl::geodesic::IntervalList::find_closest_point(), igl::geodesic::GEODESIC_INF, igl::geodesic::MeshElementBase::id(), igl::geodesic::SurfacePointWithIndex::index(), interval_list(), igl::geodesic::Edge::length(), igl::geodesic::GeodesicAlgorithmBase::m_propagation_distance_stopped, m_sources, igl::geodesic::Interval::signal(), igl::geodesic::SimpleVector< Data >::size(), igl::geodesic::Interval::source_index(), igl::geodesic::SortedSources::sources(), igl::geodesic::SurfacePoint::type(), igl::geodesic::UNDEFINED_POINT, igl::geodesic::Edge::v0(), and igl::geodesic::VERTEX.

Referenced by best_source(), and trace_back().

Here is the call graph for this function:

Here is the caller graph for this function:

best_point_on_the_edge_set()

void igl::geodesic::GeodesicAlgorithmExact::best_point_on_the_edge_set ( SurfacePoint &  point, std::vector< edge_pointer > const &  storage, interval_pointer &  best_interval, double &  best_total_distance, double &  best_interval_position  )

inlineprivate

{
  best_total_distance = 1e100;
  for(unsigned i=0; i<storage.size(); ++i)
  {
    edge_pointer e = storage[i];
    list_pointer list = interval_list(e);
 
    double offset;
    double distance;
    interval_pointer interval;
 
    list->find_closest_point(&point, 
                 offset, 
                 distance, 
                 interval);
 
    if(distance < best_total_distance)
    {
      best_interval = interval;
      best_total_distance = distance;
      best_interval_position = offset;
    }
  }
}

References igl::geodesic::IntervalList::find_closest_point(), and interval_list().

Referenced by trace_back().

Here is the call graph for this function:

Here is the caller graph for this function:

best_source()

unsigned igl::geodesic::GeodesicAlgorithmExact::best_source ( SurfacePoint &  point, double &  best_source_distance  )

inlinevirtual

Implements igl::geodesic::GeodesicAlgorithmBase.

{
  double best_interval_position; 
  unsigned best_source_index;
 
  best_first_interval(point, 
            best_source_distance, 
            best_interval_position, 
            best_source_index);
  
  return best_source_index;
} 

References best_first_interval().

Here is the call graph for this function:

check_stop_conditions()

bool igl::geodesic::GeodesicAlgorithmExact::check_stop_conditions ( unsigned &  index )

inlineprivate

{
  double queue_distance = (*m_queue.begin())->min();
  if(queue_distance < stop_distance())
  {
    return false;
  }
 
  while(index < m_stop_vertices.size())
  {
    vertex_pointer v = m_stop_vertices[index].first;
    edge_pointer edge = v->adjacent_edges()[0];       //take any edge
 
    double distance = edge->v0()->id() == v->id() ? 
              interval_list(edge)->signal(0.0) :
              interval_list(edge)->signal(edge->length());
 
    if(queue_distance < distance + m_stop_vertices[index].second)
    {
      return false;
    }
 
    ++index;
  }
  return true;
}

References igl::geodesic::MeshElementBase::adjacent_edges(), igl::geodesic::MeshElementBase::id(), interval_list(), igl::geodesic::Edge::length(), m_queue, igl::geodesic::GeodesicAlgorithmBase::m_stop_vertices, igl::min(), igl::geodesic::IntervalList::signal(), igl::geodesic::GeodesicAlgorithmBase::stop_distance(), and igl::geodesic::Edge::v0().

Referenced by propagate().

Here is the call graph for this function:

Here is the caller graph for this function:

clear()

void igl::geodesic::GeodesicAlgorithmExact::clear ( )

inlineprivate

  {
    m_memory_allocator.clear();
    m_queue.clear();
    for(unsigned i=0; i<m_edge_interval_lists.size(); ++i)
    {
      m_edge_interval_lists[i].clear();
    }
    m_propagation_distance_stopped = GEODESIC_INF;
  };

References igl::geodesic::GEODESIC_INF, m_edge_interval_lists, m_memory_allocator, igl::geodesic::GeodesicAlgorithmBase::m_propagation_distance_stopped, and m_queue.

Referenced by initialize_propagation_data().

Here is the caller graph for this function:

compute_positive_intersection()

double igl::geodesic::GeodesicAlgorithmExact::compute_positive_intersection ( double  start, double  pseudo_x, double  pseudo_y, double  sin_alpha, double  cos_alpha  )

inlineprivate

{
  assert(pseudo_y < 0);
 
  double denominator = sin_alpha*(pseudo_x - start) - cos_alpha*pseudo_y;
  if(denominator<0.0)
  {
    return -1.0;
  }
 
  double numerator = -pseudo_y*start;
 
  if(numerator < 1e-30)
  {
    return 0.0;
  }
 
  if(denominator < 1e-30)
  {
    return -1.0;
  }
 
  return numerator/denominator;
}

References start.

Referenced by compute_propagated_parameters().

Here is the caller graph for this function:

compute_propagated_parameters()

unsigned igl::geodesic::GeodesicAlgorithmExact::compute_propagated_parameters ( double  pseudo_x, double  pseudo_y, double  d, double  start, double  end, double  alpha, double  L, bool  first_interval, bool  last_interval, bool  turn_left, bool  turn_right, IntervalWithStop *  candidates  )

inlineprivate

{       
  assert(pseudo_y<=0.0);
  assert(d<GEODESIC_INF/10.0);
  assert(begin<=end);
  assert(first_interval ? (begin == 0.0) : true);
 
  IntervalWithStop* p = candidates;
 
  if(std::abs(pseudo_y) <= 1e-30)       //pseudo-source is on the edge
  {
    if(first_interval && pseudo_x <= 0.0)
    {
      p->start() = 0.0;
      p->stop() = L;
      p->d() = d - pseudo_x;
      p->pseudo_x() = 0.0;
      p->pseudo_y() = 0.0;
      return 1;
    }
    else if(last_interval && pseudo_x >= end)
    {
      p->start() = 0.0;
      p->stop() = L;
      p->d() = d + pseudo_x-end;
      p->pseudo_x() = end*cos(alpha);
      p->pseudo_y() = -end*sin(alpha);
      return 1;
    }
    else if(pseudo_x >= begin && pseudo_x <= end)
    {
      p->start() = 0.0;
      p->stop() = L;
      p->d() = d;
      p->pseudo_x() = pseudo_x*cos(alpha);
      p->pseudo_y() = -pseudo_x*sin(alpha);
      return 1;
    }
    else
    {
      return 0;
    }
  }
 
  double sin_alpha = sin(alpha);
  double cos_alpha = cos(alpha);
 
  //important: for the first_interval, this function returns zero only if the new edge is "visible" from the source
  //if the new edge can be covered only after turn_over, the value is negative (-1.0)
  double L1 = compute_positive_intersection(begin, 
                        pseudo_x, 
                        pseudo_y, 
                          sin_alpha, 
                          cos_alpha);
 
  if(L1 < 0 || L1 >= L)
  {
    if(first_interval && turn_left)
    {
      p->start() = 0.0;
      p->stop() = L;
      p->d() = d + sqrt(pseudo_x*pseudo_x + pseudo_y*pseudo_y);
      p->pseudo_y() = 0.0;
      p->pseudo_x() = 0.0;
      return 1;
    }
    else
    {
      return 0;
    }
  }
 
  double L2 = compute_positive_intersection(end, 
                        pseudo_x, 
                        pseudo_y, 
                        sin_alpha, 
                        cos_alpha);
 
  if(L2 < 0 || L2 >= L)
  {
    p->start() = L1;
    p->stop() = L;
    p->d() = d;
    p->pseudo_x() = cos_alpha*pseudo_x + sin_alpha*pseudo_y;
    p->pseudo_y() = -sin_alpha*pseudo_x + cos_alpha*pseudo_y;
 
    return 1;
  }
 
  p->start() = L1;
  p->stop() = L2;
  p->d() = d;
  p->pseudo_x() = cos_alpha*pseudo_x + sin_alpha*pseudo_y;
  p->pseudo_y() = -sin_alpha*pseudo_x + cos_alpha*pseudo_y;
  assert(p->pseudo_y() <= 0.0);
 
  if(!(last_interval && turn_right))
  {
    return 1;
  }
  else
  {
    p = candidates + 1;
 
    p->start() = L2;
    p->stop() = L;
    double dx = pseudo_x - end;
    p->d() = d + sqrt(dx*dx + pseudo_y*pseudo_y);
    p->pseudo_x() = end*cos_alpha;
    p->pseudo_y() = -end*sin_alpha;
 
    return 2;
  }
}

References compute_positive_intersection(), cos(), igl::geodesic::GEODESIC_INF, L, sin(), sqrt(), and igl::geodesic::Interval::start().

Referenced by propagate().

Here is the call graph for this function:

Here is the caller graph for this function:

construct_propagated_intervals()

void igl::geodesic::GeodesicAlgorithmExact::construct_propagated_intervals ( bool  invert, edge_pointer  edge, face_pointer  face, IntervalWithStop *  candidates, unsigned &  num_candidates, interval_pointer  source_interval  )

inlineprivate

{
  double edge_length = edge->length();
  double local_epsilon = SMALLEST_INTERVAL_RATIO * edge_length;
    
    //kill very small intervals in order to avoid precision problems
  if(num_candidates == 2)   
  {
    double start = std::min(candidates->start(), (candidates+1)->start());
    double stop = std::max(candidates->stop(), (candidates+1)->stop());
    if(candidates->stop()-candidates->start() < local_epsilon) // kill interval 0
    {
      *candidates = *(candidates+1);
      num_candidates = 1;
      candidates->start() = start;
      candidates->stop() = stop;
    }
    else if ((candidates+1)->stop() - (candidates+1)->start() < local_epsilon)
    {
      num_candidates = 1;
      candidates->start() = start;
      candidates->stop() = stop;
    }
  }
 
  IntervalWithStop* first; 
  IntervalWithStop* second; 
  if(num_candidates == 1)
  {
    first = candidates;
    second = candidates;
  }
  else
  {
    if(candidates->start() <= (candidates+1)->start())
    {
      first = candidates;
      second = candidates+1;
    }
    else 
    {
      first = candidates+1;
      second = candidates;
    }
    assert(first->stop() == second->start());
  }
 
  if(first->start() < local_epsilon)
  {
    first->start() = 0.0;
  }
  if(edge_length - second->stop() < local_epsilon)
  {
    second->stop() = edge_length;
  }
 
    //invert intervals if necessary; fill missing data and set pointers correctly
  Interval::DirectionType direction = edge->adjacent_faces()[0]->id() == face->id() ? 
                    Interval::FROM_FACE_0 : 
                    Interval::FROM_FACE_1;
 
  if(!invert)         //in this case everything is straighforward, we do not have to invert the intervals
  {
    for(unsigned i=0; i<num_candidates; ++i)
    {
      IntervalWithStop* p = candidates + i;
 
      p->next() = (i == num_candidates - 1) ? NULL : candidates + i + 1;
      p->edge() = edge;
      p->direction() = direction;
      p->source_index() = source_interval->source_index();
 
      p->min() = 0.0;         //it will be changed later on
 
      assert(p->start() < p->stop());
    }
  }
  else        //now we have to invert the intervals 
  {
    for(unsigned i=0; i<num_candidates; ++i)
    {
      IntervalWithStop* p = candidates + i;
 
      p->next() = (i == 0) ? NULL : candidates + i - 1;
      p->edge() = edge;
      p->direction() = direction;
      p->source_index() = source_interval->source_index();
 
      double length = edge_length;
      p->pseudo_x() = length - p->pseudo_x();
 
      double start = length - p->stop();
      p->stop() = length - p->start();
      p->start() = start;
 
      p->min() = 0;
 
      assert(p->start() < p->stop());
      assert(p->start() >= 0.0);
      assert(p->stop() <= edge->length());
    }
  }
}

References igl::geodesic::MeshElementBase::adjacent_faces(), igl::geodesic::Interval::direction(), igl::geodesic::Interval::edge(), igl::geodesic::Interval::FROM_FACE_0, igl::geodesic::Interval::FROM_FACE_1, igl::geodesic::MeshElementBase::id(), igl::geodesic::Edge::length(), igl::geodesic::length(), igl::geodesic::Interval::min(), igl::geodesic::Interval::next(), igl::geodesic::Interval::pseudo_x(), igl::geodesic::SMALLEST_INTERVAL_RATIO, igl::geodesic::Interval::source_index(), igl::geodesic::Interval::start(), start, and igl::geodesic::IntervalWithStop::stop().

Referenced by propagate().

Here is the call graph for this function:

Here is the caller graph for this function:

erase_from_queue()

bool igl::geodesic::GeodesicAlgorithmExact::erase_from_queue ( interval_pointer  p )

inlineprivate

{
  if(p->min() < GEODESIC_INF/10.0)// && p->min >= queue->begin()->first)
  {
    assert(m_queue.count(p)<=1);      //the set is unique
 
    IntervalQueue::iterator it = m_queue.find(p);
 
    if(it != m_queue.end())
    {
      m_queue.erase(it);
      return true;
    }
  }
 
  return false;
}

References igl::geodesic::GEODESIC_INF, m_queue, and igl::geodesic::Interval::min().

Referenced by update_list_and_queue().

Here is the call graph for this function:

Here is the caller graph for this function:

geodesic() [1/2]

void igl::geodesic::GeodesicAlgorithmBase::geodesic ( std::vector< SurfacePoint > &  sources, std::vector< SurfacePoint > &  destinations, std::vector< std::vector< SurfacePoint > > &  paths  )

inlineinherited

{
  double const max_propagation_distance = GEODESIC_INF;
 
  propagate(sources, 
        max_propagation_distance,
        &destinations);   //we use desinations as stop points
 
  paths.resize(destinations.size());
 
  for(unsigned i=0; i<paths.size(); ++i)
  {
    trace_back(destinations[i], paths[i]);
  }
}

References igl::geodesic::GEODESIC_INF, igl::geodesic::GeodesicAlgorithmBase::propagate(), and igl::geodesic::GeodesicAlgorithmBase::trace_back().

Here is the call graph for this function:

geodesic() [2/2]

void igl::geodesic::GeodesicAlgorithmBase::geodesic ( SurfacePoint &  source, SurfacePoint &  destination, std::vector< SurfacePoint > &  path  )

inlineinherited

{
  std::vector<SurfacePoint> sources(1, source);
  std::vector<SurfacePoint> stop_points(1, destination);
  double const max_propagation_distance = GEODESIC_INF;
 
  propagate(sources, 
        max_propagation_distance,
        &stop_points);
 
  trace_back(destination, path);
}

References igl::geodesic::GEODESIC_INF, igl::geodesic::GeodesicAlgorithmBase::propagate(), and igl::geodesic::GeodesicAlgorithmBase::trace_back().

Referenced by igl::geodesic::GeodesicAlgorithmBase::trace_back().

Here is the call graph for this function:

Here is the caller graph for this function:

initialize_propagation_data()

void igl::geodesic::GeodesicAlgorithmExact::initialize_propagation_data ( )

inlineprivate

{
  clear();
 
  IntervalWithStop candidate;
  std::vector<edge_pointer> edges_visible_from_source;
  for(unsigned i=0; i<m_sources.size(); ++i)    //for all edges adjacent to the starting vertex     
  {
    SurfacePoint* source = &m_sources[i];
    
    edges_visible_from_source.clear();
    list_edges_visible_from_source(source->base_element(), 
                     edges_visible_from_source);
    
    for(unsigned j=0; j<edges_visible_from_source.size(); ++j)
    {
      edge_pointer e = edges_visible_from_source[j];
      candidate.initialize(e, source, i);
            candidate.stop() = e->length();
      candidate.compute_min_distance(candidate.stop());
      candidate.direction() = Interval::FROM_SOURCE;
 
      update_list_and_queue(interval_list(e), &candidate, 1);
    }
  }
}

References igl::geodesic::SurfacePoint::base_element(), clear(), igl::geodesic::Interval::compute_min_distance(), igl::geodesic::Interval::direction(), igl::geodesic::Interval::FROM_SOURCE, igl::geodesic::Interval::initialize(), interval_list(), igl::geodesic::Edge::length(), list_edges_visible_from_source(), m_sources, igl::geodesic::IntervalWithStop::stop(), and update_list_and_queue().

Referenced by propagate().

Here is the call graph for this function:

Here is the caller graph for this function:

intersect_intervals()

unsigned igl::geodesic::GeodesicAlgorithmExact::intersect_intervals ( interval_pointer  zero, IntervalWithStop *  one  )

inlineprivate

{
  assert(zero->edge()->id() == one->edge()->id());
  assert(zero->stop() > one->start() && zero->start() < one->stop());
  assert(one->min() < GEODESIC_INF/10.0);
 
  double const local_epsilon = SMALLEST_INTERVAL_RATIO*one->edge()->length(); 
 
  unsigned N=0;
  if(zero->min() > GEODESIC_INF/10.0)
  {
    start[0] = zero->start();
    if(zero->start() < one->start() - local_epsilon)
    {
      map[0] = OLD;
      start[1] = one->start();
      map[1] = NEW;
      N = 2;
    }
    else
    {
      map[0] = NEW;
      N = 1;
    }
 
    if(zero->stop() > one->stop() + local_epsilon)
    {
      map[N] = OLD;             //"zero" interval
      start[N++] = one->stop();
    }
 
    start[N+1] = zero->stop();
    return N;
  }
 
  double const local_small_epsilon = 1e-8*one->edge()->length(); 
 
  double D = zero->d() - one->d();
  double x0 = zero->pseudo_x();
  double x1 = one->pseudo_x();
  double R0 = x0*x0 + zero->pseudo_y()*zero->pseudo_y();
  double R1 = x1*x1 + one->pseudo_y()*one->pseudo_y();
 
  double inter[2];                  //points of intersection
  char Ninter=0;                    //number of the points of the intersection
 
  if(std::abs(D)<local_epsilon)         //if d1 == d0, equation is linear
  {
    double denom = x1 - x0;
    if(std::abs(denom)>local_small_epsilon)
    {
      inter[0] =  (R1 - R0)/(2.*denom);         //one solution
      Ninter = 1;
    }
  }
  else
  {
    double D2 = D*D;
    double Q = 0.5*(R1-R0-D2);
    double X = x0 - x1;
 
    double A = X*X - D2;
    double B = Q*X + D2*x0;
    double C = Q*Q - D2*R0;
 
    if (std::abs(A)<local_small_epsilon)              //if A == 0, linear equation
    {
      if(std::abs(B)>local_small_epsilon)
      {
        inter[0] =  -C/B;             //one solution
        Ninter = 1;
      }
    }
    else
    {
      double det = B*B-A*C;
      if(det>local_small_epsilon*local_small_epsilon)     //two roots
      {
        det = sqrt(det);
        if(A>0.0)               //make sure that the roots are ordered
        {
          inter[0] = (-B - det)/A;
          inter[1] = (-B + det)/A;
        }
        else
        {
          inter[0] = (-B + det)/A;
          inter[1] = (-B - det)/A;
        }
        
        if(inter[1] - inter[0] > local_small_epsilon)
        {
          Ninter = 2;
        }
        else
        {
          Ninter = 1;
        }
      }
      else if(det>=0.0)         //single root
      {
        inter[0] = -B/A;
        Ninter = 1;
      }
    }
  }
  //---------------------------find possible intervals---------------------------------------
  double left = std::max(zero->start(), one->start());    //define left and right boundaries of the intersection of the intervals
  double right = std::min(zero->stop(), one->stop());
 
  double good_start[4];                   //points of intersection within the (left, right) limits +"left" + "right"
  good_start[0] = left;
  char Ngood_start=1;                   //number of the points of the intersection  
 
  for(char i=0; i<Ninter; ++i)              //for all points of intersection
  {
    double x = inter[i];
    if(x > left + local_epsilon && x < right - local_epsilon)
    {
      good_start[Ngood_start++] = x;
    }
  }
  good_start[Ngood_start++] = right;
 
  MapType mid_map[3];
  for(char i=0; i<Ngood_start-1; ++i)
  {
    double mid = (good_start[i] + good_start[i+1])*0.5;
    mid_map[i] = zero->signal(mid) <= one->signal(mid) ? OLD : NEW;
  }
 
  //-----------------------------------output----------------------------------
  N = 0;
  if(zero->start() < left - local_epsilon)            //additional "zero" interval
  {
    if(mid_map[0] == OLD)       //first interval in the map is already the old one
    {
      good_start[0] = zero->start();
    }
    else
    {
      map[N] = OLD;         //"zero" interval
      start[N++] = zero->start();
    }
  }
 
  for(long i=0;i<Ngood_start-1;++i)             //for all intervals
  {
    MapType current_map = mid_map[i];
    if(N==0 || map[N-1] != current_map)
    {
      map[N] = current_map;       
      start[N++] = good_start[i];
    }
  }
 
  if(zero->stop() > one->stop() + local_epsilon)
  {
    if(N==0 || map[N-1] == NEW)
    {
      map[N] = OLD;             //"zero" interval
      start[N++] = one->stop();
    }
  }
 
  start[0] = zero->start();   // just to make sure that epsilons do not damage anything
  //start[N] = zero->stop();
 
  return N; 
}

References igl::geodesic::Interval::d(), igl::geodesic::Interval::edge(), igl::geodesic::GEODESIC_INF, igl::geodesic::MeshElementBase::id(), igl::geodesic::Edge::length(), map, igl::geodesic::Interval::min(), NEW, OLD, igl::geodesic::Interval::pseudo_x(), igl::geodesic::Interval::pseudo_y(), igl::geodesic::Interval::signal(), igl::geodesic::SMALLEST_INTERVAL_RATIO, sqrt(), igl::geodesic::Interval::start(), start, igl::geodesic::Interval::stop(), and igl::geodesic::IntervalWithStop::stop().

Referenced by update_list_and_queue().

Here is the call graph for this function:

Here is the caller graph for this function:

interval_list()

list_pointer igl::geodesic::GeodesicAlgorithmExact::interval_list ( edge_pointer  e )

inlineprivate

  {
    return &m_edge_interval_lists[e->id()];
  };

References igl::geodesic::MeshElementBase::id(), and m_edge_interval_lists.

Referenced by best_first_interval(), best_point_on_the_edge_set(), check_stop_conditions(), initialize_propagation_data(), propagate(), and visible_from_source().

Here is the call graph for this function:

Here is the caller graph for this function:

list_edges_visible_from_source()

void igl::geodesic::GeodesicAlgorithmExact::list_edges_visible_from_source ( MeshElementBase *  p, std::vector< edge_pointer > &  storage  )

inlineprivate

{
  assert(p->type() != UNDEFINED_POINT);
 
  if(p->type() == FACE)
  {
    face_pointer f = static_cast<face_pointer>(p);
    for(unsigned i=0; i<3; ++i)
    {
      storage.push_back(f->adjacent_edges()[i]);
    }
  }
  else if(p->type() == EDGE)
  {
    edge_pointer e = static_cast<edge_pointer>(p);
    storage.push_back(e);
  }
  else      //VERTEX
  {
    vertex_pointer v = static_cast<vertex_pointer>(p);
    for(unsigned i=0; i<v->adjacent_edges().size(); ++i)
    {
      storage.push_back(v->adjacent_edges()[i]);
    }
 
  }
}

References igl::geodesic::MeshElementBase::adjacent_edges(), igl::geodesic::EDGE, igl::geodesic::FACE, igl::geodesic::SimpleVector< Data >::size(), igl::geodesic::MeshElementBase::type(), and igl::geodesic::UNDEFINED_POINT.

Referenced by initialize_propagation_data().

Here is the call graph for this function:

Here is the caller graph for this function:

mesh()

geodesic::Mesh * igl::geodesic::GeodesicAlgorithmBase::mesh ( )

inlineinherited

{return m_mesh;};

References igl::geodesic::GeodesicAlgorithmBase::m_mesh.

Referenced by GeodesicAlgorithmExact().

Here is the caller graph for this function:

name()

std::string igl::geodesic::GeodesicAlgorithmBase::name ( )

inlinevirtualinherited

{
  switch(m_type)
  {
  case EXACT:
    return "exact";
  case DIJKSTRA:
    return "dijkstra";
  case SUBDIVISION:
    return "subdivision";
  default:
  case UNDEFINED_ALGORITHM:
    return "undefined";
  }
}

References igl::geodesic::GeodesicAlgorithmBase::DIJKSTRA, igl::geodesic::GeodesicAlgorithmBase::EXACT, igl::geodesic::GeodesicAlgorithmBase::m_type, igl::geodesic::GeodesicAlgorithmBase::SUBDIVISION, and igl::geodesic::GeodesicAlgorithmBase::UNDEFINED_ALGORITHM.

possible_traceback_edges()

void igl::geodesic::GeodesicAlgorithmExact::possible_traceback_edges ( SurfacePoint &  point, std::vector< edge_pointer > &  storage  )

inlineprivate

{
  storage.clear();
 
  if(point.type() == VERTEX)
  {
    vertex_pointer v = static_cast<vertex_pointer>(point.base_element());
    for(unsigned i=0; i<v->adjacent_faces().size(); ++i)
    {
      face_pointer f = v->adjacent_faces()[i];
      storage.push_back(f->opposite_edge(v));
    }
  }
  else if(point.type() == EDGE)
  {
    edge_pointer e = static_cast<edge_pointer>(point.base_element());
    for(unsigned i=0; i<e->adjacent_faces().size(); ++i)
    {
      face_pointer f = e->adjacent_faces()[i];
 
      storage.push_back(f->next_edge(e,e->v0()));
      storage.push_back(f->next_edge(e,e->v1()));
    }
  }
  else
  {
    face_pointer f = static_cast<face_pointer>(point.base_element());
    storage.push_back(f->adjacent_edges()[0]);
    storage.push_back(f->adjacent_edges()[1]);
    storage.push_back(f->adjacent_edges()[2]);
  }
}

References igl::geodesic::MeshElementBase::adjacent_edges(), igl::geodesic::MeshElementBase::adjacent_faces(), igl::geodesic::SurfacePoint::base_element(), igl::geodesic::EDGE, igl::geodesic::Face::next_edge(), igl::geodesic::Face::opposite_edge(), igl::geodesic::SimpleVector< Data >::size(), igl::geodesic::SurfacePoint::type(), igl::geodesic::Edge::v0(), igl::geodesic::Edge::v1(), and igl::geodesic::VERTEX.

Referenced by trace_back().

Here is the call graph for this function:

Here is the caller graph for this function:

print_statistics()

void igl::geodesic::GeodesicAlgorithmExact::print_statistics ( )

inlinevirtual

Reimplemented from igl::geodesic::GeodesicAlgorithmBase.

{
  GeodesicAlgorithmBase::print_statistics();
 
  unsigned interval_counter = 0;
  for(unsigned i=0; i<m_edge_interval_lists.size(); ++i)
  {
    interval_counter += m_edge_interval_lists[i].number_of_intervals();
  }
  double intervals_per_edge = (double)interval_counter/(double)m_edge_interval_lists.size();
 
  double memory = m_edge_interval_lists.size()*sizeof(IntervalList) + 
          interval_counter*sizeof(Interval);
 
  std::cout << "uses about " << memory/1e6 << "Mb of memory" <<std::endl;
  std::cout << interval_counter << " total intervals, or " 
        << intervals_per_edge << " intervals per edge"
        << std::endl;
  std::cout << "maximum interval queue size is " << m_queue_max_size << std::endl;
  std::cout << "number of interval propagations is " << m_iterations << std::endl;
}

References m_edge_interval_lists, m_iterations, m_queue_max_size, and igl::geodesic::GeodesicAlgorithmBase::print_statistics().

Here is the call graph for this function:

propagate()

void igl::geodesic::GeodesicAlgorithmExact::propagate ( std::vector< SurfacePoint > &  sources, double  max_propagation_distance = GEODESIC_INF, std::vector< SurfacePoint > *  stop_points = NULL  )

inlinevirtual

Implements igl::geodesic::GeodesicAlgorithmBase.

{
  set_stop_conditions(stop_points, max_propagation_distance);
  set_sources(sources);
  initialize_propagation_data();
 
  clock_t start = clock();
 
  unsigned satisfied_index = 0;
 
  m_iterations = 0;   //for statistics
  m_queue_max_size = 0;
 
  IntervalWithStop candidates[2];
 
  while(!m_queue.empty())
  {
    m_queue_max_size = std::max(static_cast<unsigned int>(m_queue.size()), m_queue_max_size);
 
    unsigned const check_period = 10;
      if(++m_iterations % check_period == 0)    //check if we covered all required vertices
    {
      if (check_stop_conditions(satisfied_index))
      {
        break;
      }
    }
 
    interval_pointer min_interval = *m_queue.begin();
    m_queue.erase(m_queue.begin());
    edge_pointer edge = min_interval->edge();
    list_pointer list = interval_list(edge);
 
    assert(min_interval->d() < GEODESIC_INF);
 
    bool const first_interval = min_interval->start() == 0.0;
    //bool const last_interval = min_interval->stop() == edge->length();
    bool const last_interval = min_interval->next() == NULL;
 
    bool const turn_left = edge->v0()->saddle_or_boundary();
    bool const turn_right = edge->v1()->saddle_or_boundary();
 
    for(unsigned i=0; i<edge->adjacent_faces().size(); ++i)   //two possible faces to propagate
    {
      if(!edge->is_boundary())    //just in case, always propagate boundary edges
      {
        if((i == 0 && min_interval->direction() == Interval::FROM_FACE_0) ||
          (i == 1 && min_interval->direction() == Interval::FROM_FACE_1))
        {
          continue;
        }
      }
 
      face_pointer face = edge->adjacent_faces()[i];      //if we come from 1, go to 2
      edge_pointer next_edge = face->next_edge(edge,edge->v0());
 
      unsigned num_propagated = compute_propagated_parameters(min_interval->pseudo_x(), 
                                   min_interval->pseudo_y(), 
                                   min_interval->d(),   //parameters of the interval
                                   min_interval->start(), 
                                   min_interval->stop(),    //start/end of the interval
                                   face->vertex_angle(edge->v0()),  //corner angle
                                   next_edge->length(),   //length of the new edge
                                   first_interval,    //if it is the first interval on the edge
                                   last_interval,
                                   turn_left,
                                   turn_right,
                                   candidates);   //if it is the last interval on the edge
      bool propagate_to_right = true;
 
      if(num_propagated)
      {
        if(candidates[num_propagated-1].stop() != next_edge->length()) 
        {
          propagate_to_right = false;
        }
        
        bool const invert = next_edge->v0()->id() != edge->v0()->id(); //if the origins coinside, do not invert intervals
 
        construct_propagated_intervals(invert,    //do not inverse 
                       next_edge, 
                       face,
                       candidates,
                       num_propagated,
                       min_interval);
        
        update_list_and_queue(interval_list(next_edge), 
                    candidates, 
                    num_propagated);
      }
 
      if(propagate_to_right)
      {
                  //propogation to the right edge
        double length = edge->length();
        next_edge = face->next_edge(edge,edge->v1());
 
        num_propagated = compute_propagated_parameters(length - min_interval->pseudo_x(), 
                               min_interval->pseudo_y(), 
                               min_interval->d(),   //parameters of the interval
                               length - min_interval->stop(), 
                               length - min_interval->start(),    //start/end of the interval
                               face->vertex_angle(edge->v1()),  //corner angle
                               next_edge->length(),   //length of the new edge
                               last_interval,   //if it is the first interval on the edge
                               first_interval,
                               turn_right,
                               turn_left,
                               candidates);   //if it is the last interval on the edge
 
        if(num_propagated)
        {
          bool const invert = next_edge->v0()->id() != edge->v1()->id();    //if the origins coinside, do not invert intervals
 
          construct_propagated_intervals(invert,    //do not inverse 
                         next_edge, 
                         face,
                         candidates,
                         num_propagated,
                         min_interval);
 
          update_list_and_queue(interval_list(next_edge), 
                        candidates, 
                      num_propagated);
        }
      }
    } 
  } 
 
  m_propagation_distance_stopped = m_queue.empty() ? GEODESIC_INF : (*m_queue.begin())->min();
  clock_t stop = clock();
  m_time_consumed = (static_cast<double>(stop)-static_cast<double>(start))/CLOCKS_PER_SEC;
 
/*  for(unsigned i=0; i<m_edge_interval_lists.size(); ++i)
  {
    list_pointer list = &m_edge_interval_lists[i];
    interval_pointer p = list->first();
    assert(p->start() == 0.0);
    while(p->next())
    {
      assert(p->stop() == p->next()->start());
      assert(p->d() < GEODESIC_INF);
      p = p->next();
    }
  }*/
}

References igl::geodesic::MeshElementBase::adjacent_faces(), check_stop_conditions(), compute_propagated_parameters(), construct_propagated_intervals(), igl::geodesic::Interval::d(), igl::geodesic::Interval::direction(), igl::geodesic::Interval::edge(), igl::geodesic::Interval::FROM_FACE_0, igl::geodesic::Interval::FROM_FACE_1, igl::geodesic::GEODESIC_INF, igl::geodesic::MeshElementBase::id(), initialize_propagation_data(), interval_list(), igl::geodesic::Edge::is_boundary(), igl::geodesic::Edge::length(), igl::geodesic::length(), m_iterations, igl::geodesic::GeodesicAlgorithmBase::m_propagation_distance_stopped, m_queue, m_queue_max_size, igl::geodesic::GeodesicAlgorithmBase::m_time_consumed, igl::min(), igl::geodesic::Interval::next(), igl::geodesic::Face::next_edge(), igl::geodesic::Interval::pseudo_x(), igl::geodesic::Interval::pseudo_y(), igl::geodesic::Vertex::saddle_or_boundary(), set_sources(), igl::geodesic::GeodesicAlgorithmBase::set_stop_conditions(), igl::geodesic::Interval::start(), start, igl::geodesic::Interval::stop(), update_list_and_queue(), igl::geodesic::Edge::v0(), igl::geodesic::Edge::v1(), and igl::geodesic::Face::vertex_angle().

Referenced by igl::exact_geodesic().

Here is the call graph for this function:

Here is the caller graph for this function:

set_sources()

void igl::geodesic::GeodesicAlgorithmExact::set_sources ( std::vector< SurfacePoint > &  sources )

inlineprivate

  {
    m_sources.initialize(sources);
  }

References igl::geodesic::SortedSources::initialize(), and m_sources.

Referenced by propagate().

Here is the call graph for this function:

Here is the caller graph for this function:

set_stop_conditions()

void igl::geodesic::GeodesicAlgorithmBase::set_stop_conditions ( std::vector< SurfacePoint > *  stop_points, double  stop_distance  )

inlineprotectedinherited

{
  m_max_propagation_distance = stop_distance;
 
  if(!stop_points)
  {
    m_stop_vertices.clear();
    return;
  }
 
  m_stop_vertices.resize(stop_points->size());
 
  std::vector<vertex_pointer> possible_vertices;
  for(unsigned i = 0; i < stop_points->size(); ++i)
  {
    SurfacePoint* point = &(*stop_points)[i];
 
    possible_vertices.clear();
    m_mesh->closest_vertices(point, &possible_vertices);
    
    vertex_pointer closest_vertex = NULL;
    double min_distance = 1e100;
    for(unsigned j = 0; j < possible_vertices.size(); ++j)
    {
      double distance = point->distance(possible_vertices[j]);
      if(distance < min_distance)
      {
        min_distance = distance;
        closest_vertex = possible_vertices[j];
      }
    }
    assert(closest_vertex);
 
    m_stop_vertices[i].first = closest_vertex;
    m_stop_vertices[i].second = min_distance;
  }
}

References igl::geodesic::Mesh::closest_vertices(), igl::geodesic::Point3D::distance(), igl::geodesic::GeodesicAlgorithmBase::m_max_propagation_distance, igl::geodesic::GeodesicAlgorithmBase::m_mesh, igl::geodesic::GeodesicAlgorithmBase::m_stop_vertices, and igl::geodesic::GeodesicAlgorithmBase::stop_distance().

Referenced by propagate().

Here is the call graph for this function:

Here is the caller graph for this function:

stop_distance()

double igl::geodesic::GeodesicAlgorithmBase::stop_distance ( )

inlineprotectedinherited

  {
    return m_max_propagation_distance;
  }

References igl::geodesic::GeodesicAlgorithmBase::m_max_propagation_distance.

Referenced by check_stop_conditions(), and igl::geodesic::GeodesicAlgorithmBase::set_stop_conditions().

Here is the caller graph for this function:

trace_back()

void igl::geodesic::GeodesicAlgorithmExact::trace_back ( SurfacePoint &  destination, std::vector< SurfacePoint > &  path  )

inlinevirtual

Implements igl::geodesic::GeodesicAlgorithmBase.

{         
  path.clear();
  double best_total_distance; 
  double best_interval_position;
  unsigned source_index = std::numeric_limits<unsigned>::max();
  interval_pointer best_interval = best_first_interval(destination, 
                             best_total_distance, 
                             best_interval_position, 
                             source_index);
 
  if(best_total_distance >= GEODESIC_INF/2.0)   //unable to find the right path
  {
    return;
  }
 
  path.push_back(destination);
 
  if(best_interval) //if we did not hit the face source immediately  
  {
    std::vector<edge_pointer> possible_edges;
    possible_edges.reserve(10);
  
    while(visible_from_source(path.back()) < 0)   //while this point is not in the direct visibility of some source (if we are inside the FACE, we obviously hit the source)
    {
      SurfacePoint& q = path.back();
 
      possible_traceback_edges(q, possible_edges);
 
      interval_pointer interval;
      double total_distance;
      double position;
 
      best_point_on_the_edge_set(q, 
                     possible_edges,
                     interval,
                     total_distance,
                     position);
 
      //std::cout << total_distance + length(path) << std::endl;
      assert(total_distance<GEODESIC_INF);
      source_index = interval->source_index();
 
      edge_pointer e = interval->edge();
      double local_epsilon = SMALLEST_INTERVAL_RATIO*e->length();
      if(position < local_epsilon)
      {
        path.push_back(SurfacePoint(e->v0()));
      }
      else if(position > e->length()-local_epsilon)
      {
        path.push_back(SurfacePoint(e->v1()));
      }
      else
      {
        double normalized_position = position/e->length();
        path.push_back(SurfacePoint(e, normalized_position));
      }
    }
  }
 
  SurfacePoint& source = static_cast<SurfacePoint&>(m_sources[source_index]);
  if(path.back().distance(&source) > 0)
  {
    path.push_back(source);
  }
}

References best_first_interval(), best_point_on_the_edge_set(), igl::geodesic::Interval::edge(), igl::geodesic::GEODESIC_INF, igl::geodesic::Edge::length(), m_sources, possible_traceback_edges(), igl::geodesic::SMALLEST_INTERVAL_RATIO, igl::geodesic::Interval::source_index(), igl::geodesic::Edge::v0(), igl::geodesic::Edge::v1(), and visible_from_source().

Referenced by igl::exact_geodesic().

Here is the call graph for this function:

Here is the caller graph for this function:

type()

AlgorithmType igl::geodesic::GeodesicAlgorithmBase::type ( )

inlineinherited

{return m_type;};

References igl::geodesic::GeodesicAlgorithmBase::m_type.

update_list_and_queue()

void igl::geodesic::GeodesicAlgorithmExact::update_list_and_queue ( list_pointer  list, IntervalWithStop *  candidates, unsigned  num_candidates  )

inlineprivate

{
  assert(num_candidates <= 2);
  //assert(list->first() != NULL);
  edge_pointer edge = list->edge();
  double const local_epsilon = SMALLEST_INTERVAL_RATIO * edge->length(); 
 
  if(list->first() == NULL) 
  {
    interval_pointer* p = &list->first();
    IntervalWithStop* first;
    IntervalWithStop* second; 
 
    if(num_candidates == 1)
    {
      first = candidates;
      second = candidates;
      first->compute_min_distance(first->stop());
    }
    else 
    { 
      if(candidates->start() <= (candidates+1)->start())
      {
        first = candidates;
        second = candidates+1;
      }
      else 
      {
        first = candidates+1;
        second = candidates;
      }
      assert(first->stop() == second->start());
 
      first->compute_min_distance(first->stop());
      second->compute_min_distance(second->stop());
    }
 
    if(first->start() > 0.0)
    {
      *p = m_memory_allocator.allocate();
      (*p)->initialize(edge);
      p = &(*p)->next();
    }
 
    *p = m_memory_allocator.allocate();
    memcpy(*p,first,sizeof(Interval));
    m_queue.insert(*p);
 
    if(num_candidates == 2)
    {
      p = &(*p)->next();
      *p = m_memory_allocator.allocate();
      memcpy(*p,second,sizeof(Interval));
      m_queue.insert(*p);
    }
 
    if(second->stop() < edge->length())
    {
      p = &(*p)->next();
      *p = m_memory_allocator.allocate();
      (*p)->initialize(edge);
      (*p)->start() = second->stop();
    }
    else
    {
      (*p)->next() = NULL;
    }
    return;
  }
 
  bool propagate_flag;
 
  for(unsigned i=0; i<num_candidates; ++i)        //for all new intervals
  {
    IntervalWithStop* q = &candidates[i];
  
    interval_pointer previous = NULL;
 
    interval_pointer p = list->first();
    assert(p->start() == 0.0);
 
    while(p != NULL && p->stop() - local_epsilon < q->start())
    {
      p = p->next(); 
    }
 
    while(p != NULL && p->start() < q->stop() - local_epsilon)      //go through all old intervals
    {
      unsigned const N = intersect_intervals(p, q);               //interset two intervals
 
      if(N == 1)      
      {
        if(map[0]==OLD) //if "p" is always better, we do not need to update anything)
        {
          if(previous)    //close previous interval and put in into the queue
          {
            previous->next() = p;
            previous->compute_min_distance(p->start());
            m_queue.insert(previous);
            previous = NULL;
          }
 
          p = p->next(); 
          
        }
        else if(previous) //extend previous interval to cover everything; remove p
        {
          previous->next() = p->next(); 
          erase_from_queue(p);
          m_memory_allocator.deallocate(p);
 
          p = previous->next();
        }
        else        //p becomes "previous"
        {
          previous = p;
          interval_pointer next = p->next();
          erase_from_queue(p);
 
          memcpy(previous,q,sizeof(Interval));
 
          previous->start() = start[0];
          previous->next() = next;
 
          p = next; 
        }
        continue;
      }
 
      //update_flag = true;
 
      Interval swap(*p);              //used for swapping information
      propagate_flag = erase_from_queue(p);
 
      for(unsigned j=1; j<N; ++j)       //no memory is needed for the first one
      {
        i_new[j] = m_memory_allocator.allocate(); //create new intervals
      }
 
      if(map[0]==OLD) //finish previous, if any
      {
        if(previous)
        {
          previous->next() = p;
          previous->compute_min_distance(previous->stop());
          m_queue.insert(previous);
          previous = NULL;
        }
        i_new[0] = p;
        p->next() = i_new[1];
        p->start() = start[0];
      }
      else if(previous) //extend previous interval to cover everything; remove p
      {
        i_new[0] = previous;
        previous->next() = i_new[1]; 
        m_memory_allocator.deallocate(p);
        previous = NULL;
      }
      else        //p becomes "previous"
      {
        i_new[0] = p;
        memcpy(p,q,sizeof(Interval));
 
        p->next() = i_new[1];
        p->start() = start[0];
      }
 
      assert(!previous);
 
      for(unsigned j=1; j<N; ++j)         
      {
        interval_pointer current_interval = i_new[j];
 
        if(map[j] == OLD) 
        {
          memcpy(current_interval,&swap,sizeof(Interval));
        }
        else
        {
          memcpy(current_interval,q,sizeof(Interval));
        }
        
        if(j == N-1)  
        {
          current_interval->next() = swap.next();
        }
        else      
        {
          current_interval->next() = i_new[j+1];
        }
 
        current_interval->start() = start[j];
      }
 
      for(unsigned j=0; j<N; ++j)               //find "min" and add the intervals to the queue
      {
        if(j==N-1 && map[j]==NEW)
        {
          previous = i_new[j];
        }
        else
        {
          interval_pointer current_interval = i_new[j];
 
          current_interval->compute_min_distance(current_interval->stop());         //compute minimal distance
 
          if(map[j]==NEW || (map[j]==OLD && propagate_flag))
          {
            m_queue.insert(current_interval);
          }
        }
      }
 
      p = swap.next();
    }
 
    if(previous)    //close previous interval and put in into the queue
    {
      previous->compute_min_distance(previous->stop());
      m_queue.insert(previous);
      previous = NULL;
    }
  }
}

References igl::geodesic::Interval::compute_min_distance(), igl::geodesic::IntervalList::edge(), erase_from_queue(), igl::geodesic::IntervalList::first(), i_new, intersect_intervals(), igl::geodesic::Edge::length(), m_memory_allocator, m_queue, map, NEW, igl::geodesic::Interval::next(), OLD, igl::geodesic::SMALLEST_INTERVAL_RATIO, igl::geodesic::Interval::start(), start, igl::geodesic::Interval::stop(), and igl::geodesic::IntervalWithStop::stop().

Referenced by initialize_propagation_data(), and propagate().

Here is the call graph for this function:

Here is the caller graph for this function:

visible_from_source()

long igl::geodesic::GeodesicAlgorithmExact::visible_from_source ( SurfacePoint &  point )

inlineprivate

{
  assert(point.type() != UNDEFINED_POINT);
 
  if(point.type() == EDGE)    
  {
    edge_pointer e = static_cast<edge_pointer>(point.base_element());
    list_pointer list = interval_list(e);
    double position = std::min(point.distance(e->v0()), e->length());
    interval_pointer interval = list->covering_interval(position);
    //assert(interval);
    if(interval && interval->visible_from_source())
    {
      return (long)interval->source_index();
    }
    else
    {
      return -1;
    }
  }
  else if(point.type() == FACE)   
  {
    return -1;
  }
  else if(point.type() == VERTEX)   
  {
    vertex_pointer v = static_cast<vertex_pointer>(point.base_element());
    for(unsigned i=0; i<v->adjacent_edges().size(); ++i)
    {
      edge_pointer e = v->adjacent_edges()[i];
      list_pointer list = interval_list(e);
 
      double position = e->v0()->id() == v->id() ? 0.0 : e->length();
      interval_pointer interval = list->covering_interval(position);
      if(interval && interval->visible_from_source())
      {
        return (long)interval->source_index();
      }
    }
 
    return -1;
  }
 
  assert(0);
  return 0;
}

References igl::geodesic::MeshElementBase::adjacent_edges(), igl::geodesic::SurfacePoint::base_element(), igl::geodesic::IntervalList::covering_interval(), igl::geodesic::Point3D::distance(), igl::geodesic::EDGE, igl::geodesic::FACE, igl::geodesic::MeshElementBase::id(), interval_list(), igl::geodesic::Edge::length(), igl::geodesic::SimpleVector< Data >::size(), igl::geodesic::Interval::source_index(), igl::geodesic::SurfacePoint::type(), igl::geodesic::UNDEFINED_POINT, igl::geodesic::Edge::v0(), igl::geodesic::VERTEX, and igl::geodesic::Interval::visible_from_source().

Referenced by trace_back().

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

i_new

interval_pointer igl::geodesic::GeodesicAlgorithmExact::i_new[5]

private

Referenced by update_list_and_queue().

m_edge_interval_lists

std::vector<IntervalList> igl::geodesic::GeodesicAlgorithmExact::m_edge_interval_lists

private

Referenced by GeodesicAlgorithmExact(), clear(), interval_list(), and print_statistics().

m_iterations

unsigned igl::geodesic::GeodesicAlgorithmExact::m_iterations

private

Referenced by print_statistics(), and propagate().

m_max_propagation_distance

double igl::geodesic::GeodesicAlgorithmBase::m_max_propagation_distance

protectedinherited

Referenced by igl::geodesic::GeodesicAlgorithmBase::set_stop_conditions(), and igl::geodesic::GeodesicAlgorithmBase::stop_distance().

m_memory_allocator

MemoryAllocator<Interval> igl::geodesic::GeodesicAlgorithmExact::m_memory_allocator

private

Referenced by clear(), and update_list_and_queue().

m_mesh

geodesic::Mesh* igl::geodesic::GeodesicAlgorithmBase::m_mesh

protectedinherited

Referenced by igl::geodesic::GeodesicAlgorithmBase::mesh(), and igl::geodesic::GeodesicAlgorithmBase::set_stop_conditions().

m_propagation_distance_stopped

double igl::geodesic::GeodesicAlgorithmBase::m_propagation_distance_stopped

protectedinherited

Referenced by best_first_interval(), clear(), and propagate().

m_queue

IntervalQueue igl::geodesic::GeodesicAlgorithmExact::m_queue

private

Referenced by check_stop_conditions(), clear(), erase_from_queue(), propagate(), and update_list_and_queue().

m_queue_max_size

unsigned igl::geodesic::GeodesicAlgorithmExact::m_queue_max_size

private

Referenced by print_statistics(), and propagate().

m_sources

SortedSources igl::geodesic::GeodesicAlgorithmExact::m_sources

private

Referenced by best_first_interval(), initialize_propagation_data(), set_sources(), and trace_back().

m_stop_vertices

std::vector<stop_vertex_with_distace_type> igl::geodesic::GeodesicAlgorithmBase::m_stop_vertices

protectedinherited

Referenced by check_stop_conditions(), and igl::geodesic::GeodesicAlgorithmBase::set_stop_conditions().

m_time_consumed

double igl::geodesic::GeodesicAlgorithmBase::m_time_consumed

protectedinherited

Referenced by igl::geodesic::GeodesicAlgorithmBase::print_statistics(), and propagate().

m_type

AlgorithmType igl::geodesic::GeodesicAlgorithmBase::m_type

protectedinherited

Referenced by GeodesicAlgorithmExact(), igl::geodesic::GeodesicAlgorithmBase::name(), and igl::geodesic::GeodesicAlgorithmBase::type().

map

MapType igl::geodesic::GeodesicAlgorithmExact::map[5]

private

Referenced by intersect_intervals(), and update_list_and_queue().

start

double igl::geodesic::GeodesicAlgorithmExact::start[6]

private

Referenced by compute_positive_intersection(), construct_propagated_intervals(), intersect_intervals(), propagate(), and update_list_and_queue().

---

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

• src/libigl/igl/exact_geodesic.cpp