include/shape/ssi/ssi_qsegment.hpp

Go to the documentation of this file.

#ifndef SYNAPS_SHAPE_GAIA_QSEGMENT_H
#define SYNAPS_SHAPE_GAIA_QSEGMENT_H

#include <shape/ssi/ssi_lsegment.hpp>
#include <shape/ssi/ssi_qnode.hpp>

#define TMPL template<class C, class V>
//#define ParametricSurface shape::parametric_surface<double>

namespace mmx {
namespace ssi {

void shiftm( vector3 * v, unsigned sz, const aabb3 & box );
void scale( vector3 * p, double s );

TMPL
struct lrnode
{
    coord_t umin, umax, lmin, rmin, lmax, rmax;
    lrnode<C,V> *rs, *ls;
    static lrnode<C,V> * alloc( unsigned size );
    static lrnode<C,V> * make( lrnode<C,V> * data, unsigned size );
};

TMPL
std::ostream & operator<<( std::ostream& o, const lrnode<C,V>& l )
{
  o << l.lmin << " " << l.lmax << " " << l.rmin << " " << l.rmax << std::endl;
  return o;
};

TMPL
lrnode<C,V> * lrnode<C,V>::alloc( unsigned size )
  {
    unsigned i, acc;
    i = size, acc =0;
    do { acc += i, i = i / 2 + i % 2; } while ( i > 1 );
    return new lrnode<C,V>[acc+1];
  };

TMPL
lrnode<C,V> * lrnode<C,V>::make( lrnode<C,V> * data, unsigned size )
{
#define Mmin(a,b) std::min(a,b)
#define Mmax(a,b) std::max(a,b)

  //std::cout<<"Enter lrnode make "<<size<< std::endl;
  unsigned bsize = size;
  bool     right = true;
  lrnode<C,V> * built = data;
  lrnode<C,V> * curr  = data + size;
  unsigned i,j;
  do
    {
      if ( right )
        {
          for ( i = 0, j = 0; i < bsize-(bsize%2); i += 2, j++ )
            {
              curr[j].umin = built[i].umin;
              curr[j].umax = built[i+1].umax;
              curr[j].lmin = Mmin(built[i].lmin,
                                  built[i+1].lmin);
              curr[j].lmax = Mmax(built[i].lmax,
                                  built[i+1].lmax);
              curr[j].rmin = Mmin(built[i].rmin,
                                  built[i+1].rmin);
              curr[j].rmax = Mmax(built[i].rmax,
                                  built[i+1].rmax);
              curr[j].ls   = built + i;
              curr[j].rs   = built + i + 1;
            };

          if ( bsize%2 ) { curr[j++] = built[bsize-1];  };
          built = curr;
          curr += j;
        }
      else
        {
          unsigned next_size = bsize/2 + bsize % 2;
          //built += bsize-1;
          //curr  += next_size-1;
          for ( i = 0, j = 0; i < bsize-(bsize%2); i += 2, j++ )
          {
                         curr[next_size-1-j].umin = built[bsize-1-i-1].umin;
                         curr[next_size-1-j].umax = built[bsize-1-i].umax;
                         curr[next_size-1-j].lmin = Mmin(built[bsize-1-i].lmin, built[bsize-1-i-1].lmin);
                         curr[next_size-1-j].lmax = Mmax(built[bsize-1-i].lmax, built[bsize-1-i-1].lmax);
                         curr[next_size-1-j].rmin = Mmin(built[bsize-1-i].rmin, built[bsize-1-i-1].rmin);
                         curr[next_size-1-j].rmax = Mmax(built[bsize-1-i].rmax, built[bsize-1-i-1].rmax);
                         curr[next_size-1-j].ls   = built +(bsize-1- i - 1);
                         curr[next_size-1-j].rs   = built +(bsize-1- i);
          };

          if ( bsize%2 ) { curr[next_size-1-j] = built[bsize-1-bsize+1];  };
          built = curr; //- next_size+1;
          curr  += next_size-1;
          curr++;
        };
      right = !right;
      bsize = bsize/2 + bsize%2;
    }
  while( bsize > 1 );
  //std::cout<<"Exit  lrnode make"<<std::endl;
  return --curr;
};



//typedef lrnode<C,V> * lrtree;

TMPL
struct qsegment : public lsegment<C,V>
{
    typedef typename lsegment<C,V>::ParametricSurface ParametricSurface;
    typedef qnode<C,V>* qtree;
    typedef lrnode<C,V> * lrtree;

    std::vector<qtree> trees;
    void scale_conflict( vector3 a[4], vector3 b[4], qtree qa, qtree qb );
    void make_box( rid_t id, qnode<C,V> * q );
    qnode<C,V> * make( rid_t id, coord_t vmin, coord_t vmax, lrnode<C,V> * lr );
    inline unsigned size() const { return trees.size(); };
    inline qtree operator[]( unsigned i ) { return trees[i]; };
    double _qt;
    qsegment( const ParametricSurface * s, unsigned w, unsigned h  );
    ~qsegment();
};



TMPL
void qsegment<C,V>::scale_conflict( vector3 * a, vector3 * b, qtree qa, qtree qb )
{

    aabb3 h;
    hull(h,qa->box,qb->box);
    double s = 1.0/lmax(h);
    qa->fill(a,this);
    qb->fill(b,this);
    shiftm(a,4,h);
    shiftm(b,4,h);
    scale(a,s);
    scale(b,s);
};

TMPL
void print( std::ostream& o, typename qsegment<C,V>::qtree q )
{
    o << *q << std::endl;
    if ( q->r) print( o, q->r );
    if ( q->l ) print( o, q->l );
};

TMPL
qnode<C,V> * qsegment<C,V>::make( rid_t id, coord_t vmin, coord_t vmax, lrnode<C,V> * lr )
{
    qnode<C,V> * curr, * l, * r;
    curr = l = r = 0;

    if (  vmax  <=  lr->lmin || vmin >=  lr->rmax ) return 0;
    if (  vmin  <   lr->lmax || vmax >  lr->rmin  )
    {
        if ( lr->umax-lr->umin > vmax-vmin)
        {
            l = make( id, vmin, vmax, lr->ls );
            r = make( id, vmin, vmax, lr->rs );
        }
        else
        {
            unsigned m = (vmin + vmax)/2;
            l = make( id, vmin, m, lr );
            r = make( id, m, vmax, lr );
        };

        if ( l && r )
        {
            curr = new qnode<C,V>();
            curr->umin = lr->umin;
            curr->umax = lr->umax;
            curr->vmin = vmin;
            curr->vmax = vmax;
            hull(curr->box,l->box,r->box);
            curr->l = l;
            curr->r = r;
            l->father = curr;
            r->father = curr;
            return curr;
        };

        if ( l ) { return l; };
        if ( r ) { return r; };
    }
    else
    {
        curr = new qnode<C,V>();
        curr->l    = 0;
        curr->r    = 0;
        curr->umin = lr->umin;
        curr->umax = lr->umax;
        curr->vmin = vmin;
        curr->vmax = vmax;
        curr->mbox(this);

        return curr;
    };
    return curr;
};

TMPL
qsegment<C,V>::qsegment( const ParametricSurface * s, unsigned w, unsigned h  ) : lsegment<C,V>( s, w, h )
{
    //    _qt = time();
    lrnode<C,V> * lr_chunk   = lrnode<C,V>::alloc(h);
    std::cout<<"QSegment "<<this->regions.size()<<std::endl;
    for ( unsigned i = 0; i < this->regions.size(); i++ )
    {
        lr_chunk -= this->regions[i].umin();
        for ( coord_t u = this->regions[i].umin(); u < this->regions[i].umax(); u++  )
        {
            lr_chunk[u].umin = u;
            lr_chunk[u].umax = u+1;
            lr_chunk[u].lmax = (lr_chunk[u].lmin = this->regions[i].min(u));
            lr_chunk[u].rmax = (lr_chunk[u].rmin = this->regions[i].max(u));
            lr_chunk[u].ls   = lr_chunk[u].rs = 0;
        };

        lr_chunk += this->regions[i].umin();

        lrnode<C,V> * lrt = lrnode<C,V>::make(lr_chunk,
                                    this->regions[i].umax()-this->regions[i].umin());
        //std::cout<<"Qsegment make "<<i<<std::endl;
        qtree tmp = make( i, lrt->lmin, lrt->rmax, lrt );
        tmp->father = 0;
        trees.push_back( tmp  );
    };
    //std::cout<<"QSegment"<<std::endl;
    delete[] lr_chunk;
    //    std::cout << "q = " << (time()-_qt) << std::endl;
};

TMPL
qsegment<C,V>::~qsegment()
{
    for ( unsigned i = 0; i < size(); delete trees[i], i++ );
};

} //namespace shape_ssi
} //namespace mmx

# undef ParametricSurface
# undef TMPL
# endif

---