SfSfIntersector.h

//===========================================================================
// GoTools - SINTEF Geometry Tools
//
// GoTools module: Intersections, version 1.0
//
// Copyright (C) 2000-2007 SINTEF ICT, Applied Mathematics, Norway.
//
// This program is free software; you can redistribute it and/or          
// modify it under the terms of the GNU General Public License            
// as published by the Free Software Foundation version 2 of the License. 
//
// This program is distributed in the hope that it will be useful,        
// but WITHOUT ANY WARRANTY; without even the implied warranty of         
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the          
// GNU General Public License for more details.                           
//
// You should have received a copy of the GNU General Public License      
// along with this program; if not, write to the Free Software            
// Foundation, Inc.,                                                      
// 59 Temple Place - Suite 330,                                           
// Boston, MA  02111-1307, USA.                                           
//
// Contact information: E-mail: tor.dokken@sintef.no                      
// SINTEF ICT, Department of Applied Mathematics,                         
// P.O. Box 124 Blindern,                                                 
// 0314 Oslo, Norway.                                                     
//
// Other licenses are also available for this software, notably licenses
// for:
// - Building commercial software.                                        
// - Building software whose source code you wish to keep private.        
//===========================================================================
#ifndef _SFSFINTERSECTOR_H
#define _SFSFINTERSECTOR_H


#include "Intersector2Obj.h"
#include "IntersectionPoint.h"
#include "IntersectionPool.h"


namespace Go {



class Param2FunctionInt;



class SfSfIntersector : public Intersector2Obj {
public:

    friend class SfSelfIntersector;

    SfSfIntersector() {}

    SfSfIntersector(boost::shared_ptr<ParamGeomInt> obj1, 
                    boost::shared_ptr<ParamGeomInt> obj2,
                    boost::shared_ptr<GeoTol> epsge, 
                    Intersector* prev = 0);

   SfSfIntersector(boost::shared_ptr<ParamGeomInt> obj1, 
                    boost::shared_ptr<ParamGeomInt> obj2,
                    double epsge, 
                    Intersector* prev = 0);
    virtual ~SfSfIntersector();

    virtual int numParams() const
    { return 4; }

    void postIterate3(int nmb_orig, int dir)
        {
            postIterate(nmb_orig, dir, false);
        }

    friend class IntersectionPool;

protected:

    virtual boost::shared_ptr<Intersector> 
      lowerOrderIntersector(boost::shared_ptr<ParamGeomInt> obj1,
                            boost::shared_ptr<ParamGeomInt> obj2, 
                            Intersector* prev = 0,
                            int eliminated_parameter = -1,
                            double eliminated_value = 0);

    virtual int performRotatedBoxTest(double eps1, double eps2);

    virtual bool foundIntersectionNearBoundary();

    virtual int performInterceptionByImplicitization();

    virtual int interceptionBySeparationSurface();

    virtual int simpleCase2(Point& axis1, Point& axis2);

    virtual int simpleCaseByImplicitization();

    virtual bool complexityReduced();

    virtual void handleComplexity();

    virtual int checkCoincidence();
    
    virtual void microCase();
    
    virtual bool degTriangleSimple();

    virtual int updateIntersections();

    virtual int repairIntersections();

    void repairSingularityBox();

    void repairFalseBranchPoints();

    void removeIsolatedPoints();

    void repairMissingLinks();

    bool connectIfPossible(boost::shared_ptr<IntersectionPoint> pt1,
                           boost::shared_ptr<IntersectionPoint> pt2);

    void fixCrossingLinks();

    bool checkCloseEndpoint(boost::shared_ptr<IntersectionPoint> pnt, 
                            boost::shared_ptr<IntersectionLink> link);

    void iterateOnIntersectionPoints();

    void getSingularityBox(boost::shared_ptr<IntersectionPoint> sing,
                           double frompar[], double topar[]);

    boost::shared_ptr<SfSfIntersector>
    getSubIntersector(double frompar[], double topar[]);

    virtual int linearCase();

    virtual int doSubdivide();

    void getApproxImplicit(std::vector<std::vector<boost::
                           shared_ptr<Param2FunctionInt> > >& approx_implicit,
                           std::vector<double>& approx_implicit_err,
                           std::vector<double>& approx_implicit_gradsize,
                           std::vector<double>& approx_implicit_gradvar);
    
private:

    // Implicitization related data members

    // This object contains the result of plugging in the two surfaces
    // into the two approximate implicitizations. The convention is
    // that
    //
    // approx_implicit_[implicit][surface] ,
    //
    // where implicit = 0 or 1, and surface = 0 or 1, means the result
    // of plugging surface 'surface' into implicit function
    // 'implicit'.
    std::vector<std::vector<boost::shared_ptr<Param2FunctionInt> > >
    approx_implicit_;

    // The "error" of the implicitizations. Equals the smallest
    // singular values of the implicitization "D-matrix", and bounds
    // the algebraic distance between the exact object and the
    // implicit approximation. The index (0 or 1) refers to the
    // implicit surface.
    std::vector<double> approx_implicit_err_;

    // The size of the gradient of the implicit surface over the
    // inserted surface. The measure of the size is taken to be the
    // l2-norm of the control points of approx_implicit_[0][1] and
    // approx_implicit_[1][0]. The index (0 or 1) refers to the
    // inserted parametric surface.
    std::vector<double> approx_implicit_gradsize_;

    // The variation of the gradient of the implicit surface over the
    // inserted surface. The measure of the variation is taken to be
    // max length divided by min length of the control vectors of
    // approx_implicit_[0][1] and approx_implicit_[1][0]. The index (0
    // or 1) refers to the inserted parametric surface.
    std::vector<double> approx_implicit_gradvar_;

    // Indicates if the results is fetched from this or the previous
    // level of the recursion
    bool prev_implicit_[2];

    // VSK, 0806. Information about monotone trend in simple case
    int sorting_obj_[2];  // -1 if not set, otherwise 0 or 1
    Point sorting_dir_[2];  // Direction along which to sort intersection
                         // points in the parameter domain of object sorting_obj_
    bool sorting_pardir_[2];  // Indicates whether the parameter directions in
                              // the intersection points are consistent

    // Service funtionality for subdivision
    int sortParameterDirections(int perm[], int deg_edge[]);

    SubdivisionClassification 
    getSubdivisionParameter(int dir, int deg_edge, double& par);

    bool getSubdivParDegEdge(ParamSurfaceInt *surf, int dir, int pdir, 
                             int deg_edge, double treshhold, double& par);

    void setDegTriangle(std::vector<boost::shared_ptr<ParamGeomInt> >&
                        sub_objects,
                        int deg_edge, int pdir, double par);

    int checkSubdivParam(int dir, double par, double ta, double tb,
                         std::vector<boost::shared_ptr<IntersectionPoint> >&
                         int_pts);

    int checkIsoCurve(int pdir, bool first, double par,
                      std::vector<boost::shared_ptr<IntersectionPoint> >&
                      int_pts);

    bool getSubdivAtSing(int dir, double ta, double tb, double& par);
    
    int splitIntResults(std::vector<boost::shared_ptr<IntersectionPoint> >&
                         int_pts, int pardir, double par, double start, 
                         double end, bool large_move);

    void doIterate(int pardir, double parval, double param[], double& dist,
                   double seed[]);

    void doIterate(int pardir, double param[], double limit1[], double w1,
                   double limit2[], double w2, double& dist, double *seed = 0);

    virtual void postIterate(int nmb_orig, int dir, bool keep_endpt=true);

    void postIterate2(int nmb_orig, int dir, double par,
                      bool along = true, bool only_isolated = true);

    virtual void removeDegenerateConnections();

    // Service functionality for connecting intersection points at the 
    // boundaries in a simple case situation
    bool isConnected(std::vector<boost::shared_ptr<IntersectionPoint> >&
                     bd_ints);

    bool isConnected(std::vector<std::
                     pair<boost::shared_ptr<IntersectionPoint>,
                     IntPtClassification> >& bd_ints, 
                     int nmb_nottouch);

    bool connectDirected(std::vector<std::
                         pair<boost::shared_ptr<IntersectionPoint>,
                         IntPtClassification> >& bd_ints, 
                         int nmb_nottouch);

    bool canConnect(boost::shared_ptr<IntersectionPoint> pt1,
                    boost::shared_ptr<IntersectionPoint> pt2);

    bool findMiddlePoint(boost::shared_ptr<IntersectionPoint> pt1,
                         boost::shared_ptr<IntersectionPoint> pt2,
                         double param[], double& dist);

    // Service funtionality for handling tiny, degenerate triangles
    void getPointsAtDegEdges(std::vector<boost::
                             shared_ptr<IntersectionPoint> >& result);

    void getPointsOppositeDegEdges(std::vector<std::pair<boost::
                                   shared_ptr<IntersectionPoint>, int> >&
                                   result);

    void getLinksAtDegEdges(std::vector<boost::shared_ptr<IntersectionPoint> >& deg_pnts, 
                            int idx, boost::shared_ptr<IntersectionPoint> curr,
                            std::vector<boost::shared_ptr<IntersectionLink> >& links);

    // Service funtionality and structure for handling of sub problems
    // that are recognize as complex and not recommended for further
    // subdivision

    struct IntersectionGroup {
        std::vector<boost::shared_ptr<IntersectionPoint> > points;
        std::vector<IntPtClassification> type;
        IntPtClassification main_type;
        bool tangential;
        bool iso[4];
        
        IntersectionGroup(std::vector<boost::
                          shared_ptr<IntersectionPoint> >& pts)
        {
            points = pts;
            type.resize(pts.size());
            for (size_t ki=0; ki<type.size(); ki++)
                type[ki] = DIR_UNDEF;
            main_type = DIR_UNDEF;
            tangential = false;
            for (int dir=0; dir<4; dir++)
                iso[dir] = false;
        }

        void classifyPoints(ParamSurface *srf1, ParamSurface *srf2);
        void classifyCurve();
        boost::shared_ptr<IntersectionPoint> 
        closestToPoint(IntersectionPoint* pnt);
        boost::shared_ptr<IntersectionPoint> getBranchPoint();
        boost::shared_ptr<IntersectionPoint> 
        getMainPoint(IntPtClassification &type_curr, 
                     IntPtClassification type_other);
        bool isIso()
        {
            for (int ki=0; ki<4; ki++)
                if (iso[ki])
                    return true;
            return false;
        }
    };
    
    void makeIntersectionGroups(std::vector<boost::
                                shared_ptr<IntersectionPoint> >& pts,
                                std::vector<boost::
                                shared_ptr<IntersectionGroup> >& groups);

    void classifyGroups(std::vector<boost::
                        shared_ptr<IntersectionGroup> >& groups);

    void tryConnectGroups(boost::shared_ptr<IntersectionGroup> group1,
                          boost::shared_ptr<IntersectionGroup> group2);

    void mergeGroups(std::vector<boost::shared_ptr<IntersectionGroup> >& group,
                     IntersectionPoint *sing);

    void connectToSing(boost::shared_ptr<IntersectionGroup> group,
                       IntersectionPoint *sing);

    void selfintComplex(IntersectionPoint *sing);
 
    void selfintComplex2();
 
    // Perform an approximate implicitization on both surfaces, then
    // plug both surfaces into the resulting algebraic
    // expressions. This results in (up to) four combinations of
    // plugged in objects, as well as the two implicitization errors.
    void createApproxImplicit(double tol, int recursion_limit = 10);

    // If object has a prev intersector (i.e. a parent), we initialize
    // appr_impl_tol_ based on that.
    void setApproxImplicitFromPrev();

    // Set the values of approx_implicit_gradsize_[i] and
    // approx_implicit_gradvar_[i], where 'i' is the index (0 or 1) of
    // the inserted parametric surface.
    void setGradValues(int i);

    // DEBUG
    void writeDebugConnect(std::vector<std::
                           pair<boost::shared_ptr<IntersectionPoint>,
                           IntPtClassification> >& bd_ints);

    void writeDebugLinear(std::vector<boost::
                          shared_ptr<IntersectionPoint> >&  bd_ints);

};


} // namespace Go


#endif  // _SFSFINTERSECTOR_H

---