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 EigenSTL
{
typedef std::vector<Eigen::Vector3i, Eigen::aligned_allocator<Eigen::Vector3i>> vector_Vector3i;
}

namespace distance_field
{
struct compareEigen_Vector3i
{
  bool operator()(const Eigen::Vector3i& loc_1, const 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; 
  EIGEN_MAKE_ALIGNED_OPERATOR_NEW
};

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, Eigen::aligned_allocator<Eigen::Vector3i>> VoxelSet;
  void initialize();

  void addNewObstacleVoxels(const EigenSTL::vector_Vector3i& voxel_points);

  void removeObstacleVoxels(const EigenSTL::vector_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_; 
  VoxelGrid<PropDistanceFieldVoxel>::Ptr voxel_grid_; 
  std::vector<EigenSTL::vector_Vector3i> bucket_queue_; 
  std::vector<EigenSTL::vector_Vector3i> negative_bucket_queue_; 
  double max_distance_; 
  int max_distance_sq_; 
  std::vector<double> sqrt_table_; 
  std::vector<std::vector<EigenSTL::vector_Vector3i>> neighborhoods_;

  EigenSTL::vector_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