/home/hauberg/Dokumenter/Capture/humim-tracker-0.1/src/OpenTissue/OpenTissue/collision/spatial_hashing/spatial_hashing_query.h

Go to the documentation of this file.

#ifndef OPENTISSUE_COLLISION_SPATIAL_HASHING_SPATIAL_HASHING_QUERY_H
#define OPENTISSUE_COLLISION_SPATIAL_HASHING_SPATIAL_HASHING_QUERY_H
//
// OpenTissue Template Library
// - A generic toolbox for physics-based modeling and simulation.
// Copyright (C) 2008 Department of Computer Science, University of Copenhagen.
//
// OTTL is licensed under zlib: http://opensource.org/licenses/zlib-license.php
//
#include <OpenTissue/configuration.h>

#include <boost/cast.hpp> // needed for boost::numeric_cast

#include <list>
#include <map>
#include <cassert>

namespace OpenTissue
{
  namespace spatial_hashing
  {

    template<typename child_type,typename hash_grid, typename collision_policy>
    class Query 
      : public hash_grid
      , public collision_policy
    {
    protected:

      typedef typename hash_grid::cell_type        cell_type;
      typedef typename hash_grid::triplet_type     triplet_type;
      typedef typename hash_grid::point_type       point_type;
      typedef typename hash_grid::real_type        real_type;
      typedef typename hash_grid::data_type        data_type;
      typedef typename std::list<cell_type*>       cell_queue;
      typedef typename std::map<data_type*,bool>   data_tag_queue;

    protected:

      size_t m_query_stamp;  

    public:

      struct no_collisions_tag {};

      struct all_tag {};

    public:

      template< typename data_iterator, typename query_iterator,typename result_container,typename report_type >
      void operator()(
        data_iterator d0
        , data_iterator d1
        , query_iterator q0
        , query_iterator q1
        , result_container & results
        , report_type const & type
        )
      {
        child_type & self = static_cast<child_type &>(*this);
        this->clear();
        self.first_pass(d0,d1);

        reset(results);
        init_query();
        for(query_iterator q=q0;q!=q1;++q)
          query( (*q), results, type);
      }

      template< typename query_iterator,typename result_container,typename report_type >
      void operator()(
        query_iterator q0
        , query_iterator q1
        , result_container & results
        , report_type const & type
        )
      {
        reset(results);
        init_query();
        for(query_iterator q=q0;q!=q1;++q)
          query( (*q), results, type );
      }

      template< typename query_type,typename result_container,typename report_type >
      void operator()( 
        query_type const & q
        , result_container & results
        , report_type const & type
        )
      {
        reset(results);
        query(q, results, type );
      }

      template< typename data_iterator  >
      void init_data(  data_iterator d0, data_iterator d1 )
      {
        child_type & self = static_cast<child_type &>(*this);
        this->clear();
        self.first_pass(d0,d1);
        init_query();
      }

      template< typename data_iterator  >
      void add_data(  data_iterator d0, data_iterator d1 )
      {
        child_type & self = static_cast<child_type &>(*this);
        self.first_pass(d0,d1);
      }

      template< typename data_iterator  >
      void remove_data(  data_iterator d0, data_iterator d1 )
      {
        child_type & self = static_cast<child_type &>(*this);
        self.remove_data(d0,d1);
      }

      template<typename iterator  >
      void auto_init_settings ( iterator begin, iterator end)
      {
        using std::max;
        using std::min;

        size_t cnt = 0;
        point_type mean;      
        mean.clear();

        for(iterator cur = begin;cur!=end;++cur,++cnt)
        {
          point_type d = max_coord(*cur) - min_coord(*cur);//--- min_coord and max_coord by collision_policy
          mean += d;
        }
        mean /= boost::numeric_cast<typename point_type::value_type>( cnt );
        size_t size = cnt;//--- KE 06-05-2005: Hmmm, cnt , appears to be a better value than  cnt/ 4?
        real_type spacing =  max (mean(0),  max( mean(1), mean(2) ) );
        this->resize( size );
        set_spacing( spacing  );
      }

    protected:

      void init_query()
      {
        m_query_stamp = 0;
        typename hash_grid::cell_iterator Cbegin = this->begin();
        typename hash_grid::cell_iterator Cend = this->end();
        for( typename hash_grid::cell_iterator cell = Cbegin;cell!=Cend;++cell)
          cell->m_query_stamp = m_query_stamp;
      }

      template< typename query_type,typename result_container >
      void query(query_type const & query, result_container & results, no_collisions_tag )
      {
        assert(m_query_stamp<~0u || !"Query stamp overflow, did you forget to map data?");

        ++m_query_stamp;

        point_type       min_corner = min_coord(query); //--- by collision_policy
        point_type       max_corner = max_coord(query); //--- by collision_policy
        triplet_type     m          = get_triplet(min_corner);
        triplet_type     M          = get_triplet(max_corner);

        assert( m(0) <= M(0) || !"Minimum was larger than maximum");
        assert( m(1) <= M(1) || !"Minimum was larger than maximum");
        assert( m(2) <= M(2) || !"Minimum was larger than maximum");

        triplet_type     triplet(m);
        data_tag_queue   data_tag;
        for ( triplet(0)= m(0) ; triplet(0) <= M(0); ++triplet(0) )
          for ( triplet(1)= m(1) ; triplet(1) <= M(1); ++triplet(1) )
            for ( triplet(2)= m(2) ; triplet(2) <= M(2); ++triplet(2) )
            {
              cell_type & cell = get_cell(triplet);

              if(cell.empty())
                continue;

              if(cell.m_query_stamp==m_query_stamp)
                continue;
              cell.m_query_stamp=m_query_stamp;

              typename cell_type::data_iterator Dbegin = cell.begin();
              typename cell_type::data_iterator Dend = cell.end();
              for( typename cell_type::data_iterator data = Dbegin;data!=Dend;++data)
              {
                bool & seen_before = data_tag[ &(*data) ];
                if(seen_before)
                  continue;
                seen_before = true;

                report( (*data), query, results);
              }
            }
      }

      template< typename query_type,typename result_container >
      void query(query_type const & query, result_container & results,  all_tag )
      {
        assert(m_query_stamp<~0u || !"Query stamp overflow, did you forget to map data?");

        ++m_query_stamp;

        point_type       min_corner = min_coord(query);  //--- by collision policy
        point_type       max_corner = max_coord(query);  //--- by collision policy
        triplet_type     m          = get_triplet(min_corner);
        triplet_type     M          = get_triplet(max_corner);

        assert( m(0) <= M(0) || !"Minimum was larger than maximum");
        assert( m(1) <= M(1) || !"Minimum was larger than maximum");
        assert( m(2) <= M(2) || !"Minimum was larger than maximum");

        triplet_type     triplet(m);
        for ( triplet(0)= m(0) ; triplet(0) <= M(0); ++triplet(0) )
          for ( triplet(1)= m(1) ; triplet(1) <= M(1); ++triplet(1) )
            for ( triplet(2)= m(2) ; triplet(2) <= M(2); ++triplet(2) )
            {
              cell_type & cell = get_cell(triplet);

              if(cell.empty())
                continue;

              if(cell.m_query_stamp==m_query_stamp)
                continue;
              cell.m_query_stamp=m_query_stamp;

              typename cell_type::data_iterator Dbegin = cell.begin();
              typename cell_type::data_iterator Dend = cell.end();
              for(typename cell_type::data_iterator data = Dbegin;data!=Dend;++data)
                report( (*data), query, results);
            }
      }

    };

  } // namespace spatial_hashing
} // namespace OpenTissue

// OPENTISSUE_COLLISION_SPATIAL_HASHING_SPATIAL_HASHING_QUERY_H
#endif