align.cpp

算断裂的

// ------------------------------------------------------------------
// align.cpp
//
// This file contains the routines for aligning boxes in an orbit.
// Aligning means finding the close point on the brep entity to the
// face, and then making sure the close point is consistent between
// neighboring boxes.  Then vertices of the simplicial complex 
// are generated.
// ------------------------------------------------------------------
// Author: Stephen A. Vavasis
// Copyright (c) 1999 by Cornell University.  All rights reserved.
// 
// See the accompanying file 'Copyright' for authorship information,
// the terms of the license governing this software, and disclaimers
// concerning this software.
// ------------------------------------------------------------------
// This file is part of the QMG software.  
// Version 2.0 of QMG, release date September 3, 1999.
// ------------------------------------------------------------------


#ifdef _MSC_VER
#if _MSC_VER == 1200
#include "qmatvec.h"
#endif
#endif

#include "qboxstack.h"
#include "qlog.h"
#include "qmg_gui.h"



// Routines defined in this file:

namespace QMG {
  namespace MG {
    using namespace QMG;

    void alignInitStaticData(int di); 

    void align_orbit(ActiveBoxVec& alignvec,
      int closefacedim,
      Real maxwarpdist,
      ActiveBoxVec& idlevec,
      ActiveBoxVec& smallboxvec,
      ActiveBoxVec& small_idle_boxvec,
      const Brep::Face_Spec& alignfspec,
      BoxFaceDag& dag,
      SimpComplex_Under_Construction& sc,
      vector<Brep::Face_Spec>& vtx_owner,
      const vector<Real>& asp_degrade,
      Logstream& logstr,
      Meshgen_gui& gui,
      const PatchTable& patchtable,
      IncidenceTable& inc_table,
      ActiveBoxVec::Create_Subbox_Workspace& wkspa);

    void align_orbit_lastphase(ActiveBoxVec& alignvec,
      ActiveBoxVec& smallboxvec,
      const Brep::Face_Spec& alignfspec,
      BoxFaceDag& dag,
      SimpComplex_Under_Construction& sc,
      vector<Brep::Face_Spec>& vtx_owner,
      Logstream& logstr,
      Meshgen_gui& gui);
  }
}



namespace {
  using namespace QMG;
  using namespace QMG::MG;

  ostream* debug_ostream;

  // ------------------------------------------------------------------
  // struct PriorityQueueKey
  // Priority for alignment: align highest-priority close faces first.
  // Priority queue also used so that neighboring boxes find each other.

  struct PriorityQueueKey {
    Real dist;
    Mask flatdim;
    IncidenceTable::Index incind;
    ActiveBoxVec::Index boxind;
    Base3 rindex;
    int my_idx;
    static int base_idx;
    
    // High priority means closer distance or lower incidence index.
    
    bool operator<(const PriorityQueueKey& other) const;
  };
  
  bool PriorityQueueKey::operator<(const PriorityQueueKey& other) const {
    if (this -> dist > other.dist)
      return true;
    if (this -> dist < other.dist)
      return false;
    if ((UInt32)(this -> flatdim) > (UInt32) (other.flatdim))
      return true;
    if ((UInt32)(this -> flatdim) < (UInt32) (other.flatdim))
      return false;
    int cmpind = IncidenceTable::compare_index(this -> incind, other.incind);
    if (cmpind > 0)
      return true;
    if (cmpind < 0)
      return false;
    if (this ->  boxind > other.boxind)
      return true;
    if (this -> boxind < other.boxind)
      return false;
    if ((UInt32) (this -> rindex) > (UInt32) (other.rindex))
      return true;
    if ((UInt32) (this -> rindex) < (UInt32) (other.rindex))
      return false;
    if (my_idx < other.my_idx)
      return true;
    return false;
  }
  

  // ------------------------------------------------------------------
  // struct PriorityQueueKey_lastphase
  // In the last phase, the priority queue is different because there is
  // no close face.  Instead, priority queue is used solely to match neighboring
  // boxes.


  struct PriorityQueueKey_lastphase {
    IntCoord position;
    ActiveBoxVec::Index boxind;
    Base3 rindex;
    bool operator<(const PriorityQueueKey_lastphase& other) const;
    int my_idx;
    static int base_idx;
    static int di;
  };


  int PriorityQueueKey_lastphase::di;
  int PriorityQueueKey::base_idx;
  int PriorityQueueKey_lastphase::base_idx;
  
  bool PriorityQueueKey_lastphase::operator<(const PriorityQueueKey_lastphase& other) const {
    int sgndif = IntCoord::compare(position, other.position);
    if (sgndif > 0)
      return true;
    if (sgndif < 0)
      return false;
    if (boxind > other.boxind)
      return true;
    if (boxind < other.boxind)
      return false;
    if (static_cast<UInt32>(rindex) > static_cast<UInt32>(other.rindex))
      return true;
    if (static_cast<UInt32>(rindex) < static_cast<UInt32>(other.rindex))
      return false;
    if (my_idx < other.my_idx) return true;
    return false;
  };

  // ------------------------------------------------------------------
  // l1_dist_to_boxface
  // Figures out the distance from a box face to the warp point in the l1
  // norm.


  Real l1_dist_to_boxface(const ActiveBox& b, 
    Base3 rindex,
    IncidenceTable::Index inc,
    const IncidenceTable& inc_tab) {

    Real dist = 0.0;
    Point p = b.face_real_lowerleft(rindex);
    Real rwidth = b.real_width();
    const Point& q = inc_tab.real_coord(inc);
    int reldim = 0;
    for (int i = 0; i < b.embedded_dim(); ++i) {
      bool b_is_flat = b.flatdim(i);
      bool face_is_flat = b_is_flat || rindex[reldim] < 2;
      if (face_is_flat)
        dist += fabs(p[i] - q[i]);
      else {
        if (q[i] < p[i] || q[i] > p[i] + rwidth) {
          return BIG_REAL;
        }
      }
      if (!b_is_flat) ++reldim;
    }
    return dist;
  }

  // Abstract base class for incidence priority queues with
  // single virtual void method.

  class IncidencePriorityQueue_ABC {
  public:    
    virtual void insert_box_closefaces(const ActiveBox& b) = 0;
    IncidencePriorityQueue_ABC() { }
    virtual ~IncidencePriorityQueue_ABC() { }
  private:
    // no copying
    IncidencePriorityQueue_ABC(const IncidencePriorityQueue_ABC&) { }
  };



  // Incidence priority queue.
  // Main data structure to align boxes in the orbit to incidences.  
  // Use this priority
  // queue to match up incidences from different boxes with each other, and to
  // favor the highest-priority incidences.  The highest priority
  // incidences are the ones with the smallest warp distance.


  class IncidencePriorityQueue : public IncidencePriorityQueue_ABC {
  private:
    priority_queue<PriorityQueueKey> pq_;
    int closefacedim_;
    Real maxwarpdist_act_;
    Brep::Face_Spec alignfspec_;
    const PatchTable& patchtable_;
    const IncidenceTable& inc_table_;
    Logstream& logstr_;
  public:
    IncidencePriorityQueue(int closefacedim,
      Real maxwarpdist_act,
      Brep::Face_Spec alignfspec,
      const PatchTable& patchtable,
      const IncidenceTable& inc_table,
      Logstream& logstr) :
         closefacedim_(closefacedim),
      maxwarpdist_act_(maxwarpdist_act),
      alignfspec_(alignfspec),
      patchtable_(patchtable),
      inc_table_(inc_table),
      logstr_(logstr)
    { }
    void insert_box_closefaces(const ActiveBox& b);
    PriorityQueueKey top() const {return pq_.top();}
    void pop() {pq_.pop();}
    int size() const {return pq_.size();}
  };


  // ------------------------------------------------------------------
  // insert_box_closeface_into_queue
  // Check which faces of a box are close to the input face.
  // Insert the close ones into the priority queue.

  void IncidencePriorityQueue::insert_box_closefaces(const ActiveBox& b) {
    
    StatVector<Real, MAXDIM_3EXP> dists;
    StatVector<IncidenceTable::Index, MAXDIM_3EXP> closefaces;
    int bdim = b.dim();
    int bdimpower3 = Base3::power3(bdim);
    int di = b.embedded_dim();
    if (logstr_.verbosity() >= 4)
      logstr_.str() << "For box " << b << " close faces are ";
    {
      for (int ri = 0; ri < bdimpower3; ++ri) {
        dists[ri] = BIG_REAL;
      }
    }
    for (ActiveBox::Loop_over_incidences incit(b, patchtable_, alignfspec_);
    incit.notdone();
    ++incit) {
      IncidenceTable::Index inc = incit.index();
      if (inc_table_.flatdim(inc).dim() != di - alignfspec_.fdim()) continue;
      Real bestdist = BIG_REAL;
      Base3 bestri = 0;
      {
        for (int ri = 0; ri < bdimpower3; ++ri) {
          Base3 rindex = ri;
          if (rindex.dim() == closefacedim_) {
            Real dist = l1_dist_to_boxface(b, rindex, inc, inc_table_);
            if (logstr_.verbosity() >= 7) {
              logstr_.str() << "   face = ";
              rindex.output(logstr_.str(), bdim);
              logstr_.str() << " incidence = incd#" << inc_table_.seqno(inc)
                << "# distance = " << dist << " mwd = " << maxwarpdist_act_
                << " dists[ri] = " << dists[ri] << '\n';
            }
            if (dist < bestdist && dist <= maxwarpdist_act_) {
              bestdist = dist;
              bestri = ri;
            }
          }
        }
      }
      if (bestdist < dists[bestri] && bestdist <= maxwarpdist_act_) {
        dists[bestri] = bestdist;
        closefaces[bestri] = inc;
      }
    }
    
    {
      PriorityQueueKey key;
      key.boxind = b.my_index();
      for (int ri = 0; ri < bdimpower3; ++ri) {
        Base3 rindex = ri;
        if (rindex.dim() == closefacedim_) {
          Real dist = dists[ri];
          if (dist <= maxwarpdist_act_) {
            key.dist = dist;
            key.rindex = rindex;
            
            // Compute the flatdim mask of the face of b indexed by rindex.
            
            key.flatdim = b.flatdim();
            int actual_dim = -1;
            for (int j = 0; j < bdim; ++j) {
              while (b.flatdim(++actual_dim));
              if (rindex[j] < 2)
                key.flatdim.set_bit(actual_dim);
            }
            key.incind = closefaces[ri];
            key.my_idx = ++key.base_idx;
            if (logstr_.verbosity() >= 4) {
              logstr_.str() << '{';
              key.rindex.output(logstr_.str(), bdim);
              logstr_.str() << ',' << key.dist 
                << ", incd#" << inc_table_.seqno(key.incind) << "#} ";
            }
            pq_.push(key);
          }
        }
      }
      if (logstr_.verbosity() >= 4)
        logstr_.str() << '\n';
    }
  }




  // Incidence priority queue for last phase.
  // Main data structure to align boxes in the orbit to incidences.  
  // Use this priority
  // queue to match up incidences from different boxes with each other, and to
  // favor the highest-priority incidences.  The highest priority
  // incidences are the ones with the smallest warp distance.


  class IncidencePriorityQueue_LastPhase : public IncidencePriorityQueue_ABC {
  private:
    priority_queue<PriorityQueueKey_lastphase> pq_;
    Logstream& logstr_;
  public:
    explicit IncidencePriorityQueue_LastPhase(Logstream& logstr) :
      logstr_(logstr)
    { }
    void insert_box_closefaces(const ActiveBox& b);
    PriorityQueueKey_lastphase top() const {return pq_.top();}
    int size() const {return pq_.size();}
    void pop() {pq_.pop();}
  };

  
  // ------------------------------------------------------------------
  // insert_box_closefaces_into_queue_lastphase
  // Insert a box's closefaces into the priority queue during last-phase alignment.
  // In this case, all faces are close.  Insert the vertices only.

  void IncidencePriorityQueue_LastPhase::insert_box_closefaces(const ActiveBox& b) {
    
    PriorityQueueKey_lastphase key;
    key.boxind = b.my_index();
    for (ActiveBox::Loop_over_vertices vertit(b);
    vertit.notdone();
    ++vertit) {
      key.position = vertit.intcoord();
      key.rindex = vertit.rindex();
      key.my_idx = ++key.base_idx;
      pq_.push(key);
    }
  }



  // ------------------------------------------------------------------
  // compute_l1_closepoint
  // Compute the closest point (in the l1 norm) among nearby incidences
  // to a box face.

  Point compute_l1_closepoint(const Point& warp_point, 
    const ActiveBox& b, 
    Base3 warp_rindex) {
    Point returnval;
    Real rwidth = b.real_width();
    Point lowerleft = b.face_real_lowerleft(warp_rindex);
    int reldim = 0;
    for (int i = 0; i < b.embedded_dim(); ++i) {
      bool is_flat = b.flatdim(i);
      Real lb = lowerleft[i];
      Real ub = lowerleft[i] + ((is_flat || warp_rindex[reldim] < 2)? 0.0 : rwidth);
      Real wp = warp_point[i];
      if (wp < lb)
        returnval[i] = lb;
      else if (wp > ub)
        returnval[i] = ub;
      else
        returnval[i] = wp;
      if (!is_flat) ++reldim;
    }
    return returnval;
  }



  // ------------------------------------------------------------------
  // warp_ok
  // Check if a proposed warp is OK.  "Warp" means select a close point