propagation_distance_field.h

Go to the documentation of this file.

/*********************************************************************
 * Software License Agreement (BSD License)
 *
 *  Copyright (c) 2009, Willow Garage, Inc.
 *  All rights reserved.
 *
 *  Redistribution and use in source and binary forms, with or without
 *  modification, are permitted provided that the following conditions
 *  are met:
 *
 *   * Redistributions of source code must retain the above copyright
 *     notice, this list of conditions and the following disclaimer.
 *   * Redistributions in binary form must reproduce the above
 *     copyright notice, this list of conditions and the following
 *     disclaimer in the documentation and/or other materials provided
 *     with the distribution.
 *   * Neither the name of Willow Garage nor the names of its
 *     contributors may be used to endorse or promote products derived
 *     from this software without specific prior written permission.
 *
 *  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 *  "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 *  LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
 *  FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
 *  COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
 *  INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
 *  BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 *  LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
 *  CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 *  LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
 *  ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 *  POSSIBILITY OF SUCH DAMAGE.
 *********************************************************************/

/* Author: Mrinal Kalakrishnan, Ken Anderson */

#ifndef MOVEIT_DISTANCE_FIELD_PROPAGATION_DISTANCE_FIELD_
#define MOVEIT_DISTANCE_FIELD_PROPAGATION_DISTANCE_FIELD_

#include <moveit/distance_field/voxel_grid.h>
#include <moveit/distance_field/distance_field.h>
#include <vector>
#include <list>
#include <Eigen/Core>
#include <set>
#include <octomap/octomap.h>

namespace distance_field
{

struct compareEigen_Vector3i
{
  bool operator()(Eigen::Vector3i loc_1, Eigen::Vector3i loc_2) const
  {
    if( loc_1.z() != loc_2.z() )
      return ( loc_1.z() < loc_2.z() );
    else if( loc_1.y() != loc_2.y() )
      return ( loc_1.y() < loc_2.y() );
    else if( loc_1.x() != loc_2.x() )
      return ( loc_1.x() < loc_2.x() );
    return false;
  }
};

struct PropDistanceFieldVoxel
{

  PropDistanceFieldVoxel();

  PropDistanceFieldVoxel(int distance_sq_positive, int distance_sq_negative);

  int distance_square_;         
  int negative_distance_square_; 
  Eigen::Vector3i closest_point_; 
  Eigen::Vector3i closest_negative_point_; 
  int update_direction_;        
  int negative_update_direction_;        
  static const int UNINITIALIZED=-1; 
};

class PropagationDistanceField: public DistanceField
{
public:


  PropagationDistanceField(double size_x,
                           double size_y,
                           double size_z,
                           double resolution,
                           double origin_x, double origin_y, double origin_z,
                           double max_distance,
                           bool propagate_negative_distances=false);

  PropagationDistanceField(const octomap::OcTree& octree,
                           const octomap::point3d& bbx_min,
                           const octomap::point3d& bbx_max,
                           double max_distance,
                           bool propagate_negative_distances=false);

  PropagationDistanceField(std::istream& stream,
                           double max_distance,
                           bool propagate_negative_distances=false);
  virtual ~PropagationDistanceField(){}

  virtual void addPointsToField(const EigenSTL::vector_Vector3d& points);

  virtual void removePointsFromField(const EigenSTL::vector_Vector3d& points);

  virtual void updatePointsInField(const EigenSTL::vector_Vector3d& old_points,
                                   const EigenSTL::vector_Vector3d& new_points);

  virtual void reset();

  virtual double getDistance(double x, double y, double z) const;

  virtual double getDistance(int x, int y, int z) const;

  virtual bool isCellValid(int x, int y, int z) const;
  virtual int getXNumCells() const;
  virtual int getYNumCells() const;
  virtual int getZNumCells() const;
  virtual bool gridToWorld(int x, int y, int z, double& world_x, double& world_y, double& world_z) const;
  virtual bool worldToGrid(double world_x, double world_y, double world_z, int& x, int& y, int& z) const;

  virtual bool writeToStream(std::ostream& stream) const;

  virtual bool readFromStream(std::istream& stream);

  //passthrough docs to DistanceField
  virtual double getUninitializedDistance() const
  {
    return max_distance_;
  }

  const PropDistanceFieldVoxel& getCell(int x, int y, int z) const 
  {
    return voxel_grid_->getCell(x, y, z);
  }

  const PropDistanceFieldVoxel* getNearestCell(int x, int y, int z, double& dist, Eigen::Vector3i& pos) const
  {
    const PropDistanceFieldVoxel* cell = &voxel_grid_->getCell(x, y, z);
    if (cell->distance_square_ > 0)
    {
      dist = sqrt_table_[cell->distance_square_];
      pos = cell->closest_point_;
      const PropDistanceFieldVoxel* ncell = &voxel_grid_->getCell(pos.x(), pos.y(), pos.z());
      return ncell == cell ? NULL : ncell;
    }
    if (cell->negative_distance_square_ > 0)
    {
      dist = -sqrt_table_[cell->negative_distance_square_];
      pos = cell->closest_negative_point_;
      const PropDistanceFieldVoxel* ncell = &voxel_grid_->getCell(pos.x(), pos.y(), pos.z());
      return ncell == cell ? NULL : ncell;
    }
    dist = 0.0;
    pos.x() = x;
    pos.y() = y;
    pos.z() = z;
    return NULL;
  }

  int getMaximumDistanceSquared() const
  {
    return max_distance_sq_;
  }

private:

  typedef std::set<Eigen::Vector3i, compareEigen_Vector3i> VoxelSet; 
  void initialize();

  void addNewObstacleVoxels(const std::vector<Eigen::Vector3i>& voxel_points);

  void removeObstacleVoxels(const std::vector<Eigen::Vector3i>& voxel_points);

  void propagatePositive();

  void propagateNegative();

  virtual double getDistance(const PropDistanceFieldVoxel& object) const;

  int getDirectionNumber(int dx, int dy, int dz) const;

  Eigen::Vector3i getLocationDifference(int directionNumber) const;

  void initNeighborhoods();

  void print(const VoxelSet & set);

  void print(const EigenSTL::vector_Vector3d& points);

  static int eucDistSq(Eigen::Vector3i point1, Eigen::Vector3i point2);

  bool propagate_negative_;     
  boost::shared_ptr<VoxelGrid<PropDistanceFieldVoxel> > voxel_grid_; 

  std::vector<std::vector<Eigen::Vector3i> > bucket_queue_; 
  std::vector<std::vector<Eigen::Vector3i> > negative_bucket_queue_;
  double max_distance_;         
  int max_distance_sq_;         
  std::vector<double> sqrt_table_; 
  std::vector<std::vector<std::vector<Eigen::Vector3i > > > neighborhoods_;

  std::vector<Eigen::Vector3i > direction_number_to_direction_; 
};


inline PropDistanceFieldVoxel::PropDistanceFieldVoxel(int distance_square, int negative_distance_squared):
  distance_square_(distance_square),
  negative_distance_square_(negative_distance_squared)
{
  closest_point_.x() = PropDistanceFieldVoxel::UNINITIALIZED;
  closest_point_.y() = PropDistanceFieldVoxel::UNINITIALIZED;
  closest_point_.z() = PropDistanceFieldVoxel::UNINITIALIZED;
  closest_negative_point_.x() = PropDistanceFieldVoxel::UNINITIALIZED;
  closest_negative_point_.y() = PropDistanceFieldVoxel::UNINITIALIZED;
  closest_negative_point_.z() = PropDistanceFieldVoxel::UNINITIALIZED;
}

inline PropDistanceFieldVoxel::PropDistanceFieldVoxel()
{
}

inline double PropagationDistanceField::getDistance(const PropDistanceFieldVoxel& object) const
{
  return sqrt_table_[object.distance_square_]-sqrt_table_[object.negative_distance_square_];
}

}

#endif