VRS - The Virtual Rendering System

version 3.3

algorithm.h

Go to the documentation of this file.

/******************************************************************************
 * VRS - The Virtual Rendering System
 * Copyright (C) 2000-2007 Computer Graphics Systems Group at the 
 * Hasso-Plattner-Institute (HPI), Potsdam, Germany.
 *
 * This  library  is  free  software; you can redistribute it and/or  modify it
 * under the terms of the GNU Lesser General Public  License  as  published  by
 * the  Free  Software  Foundation;  either  version 2.1 of the License, or (at
 * your option) any later version. This library  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 Lesser General Public License for more details. You should have received
 * a copy of the GNU Lesser+ General Public License along with this library; if
 * not, write to the FreeSoftware Foundation, Inc., 59 Temple Place, Suite 330,
 * Boston, MA, 02111-1307, USA.
 ******************************************************************************/

// $Id: algorithm.h 6519 2008-10-20 13:54:10Z Anselm_Kegel $

#ifndef VRS_ALGORITHM_H
#define VRS_ALGORITHM_H

#include <vrs/matrix.h>
#include <vrs/vector.h>
#include <vrs/bounds.h>
#include <vrs/container/packedvertexiterator.h>

namespace VRS {

class Disc;
class PolygonSet;
class Ray;
class Sphere;
class Facet;



template<unsigned int DIM_X, unsigned int DIM_Y, unsigned int DIM_Z>
class VRS_CORE_API AlgorithmImpl {
public:
    static SO<PolygonSet> convexHull3D(
        SO<Iterator<Vector> > points
    );
    static SO<Iterator<Vector> > convexHull2D(  SO<Iterator<Vector> > points );
    static SO<Iterator<Vector> > convexHull2D(
        SO<Iterator<Vector> > points,
        const Vector& planeNormal,
        const Vector& onPlane = Vector::origin
    );
    static Vector projectOntoPlane(
        const Vector& point, 
        const Vector& planeNormal,
        const Vector& onPlane = Vector(0,0,0)
    );
    static SO<Iterator<Vector> > projectOntoPlane(
        SO<Iterator<Vector> > points,
        const Vector& planeNormal,
        const Vector& onPlane = Vector(0,0,0)
    );

    static bool intersectPlanes(
        const Vector& planeNormal1, const Vector& onPlane1,
        const Vector& planeNormal2, const Vector& onPlane2,
        const Vector& planeNormal3, const Vector& onPlane3,
        Vector& intersectionPoint
    );
    static bool linePlaneIntersection(
        const Vector& planeNormal,
        const Vector& onPlane,
        const Vector& a,
        const Vector& b,
        Vector& intersectionPoint,
        bool checkSection = true
    );
    static bool rayTriangleIntersection(
        const Ray& ray,
        const Vector& t1, const Vector& t2, const Vector& t3,
        Vector& intersectionPoint
    );
    static double signedDistance(const Vector& planeNormal, const Vector& onPlane, const Vector& p);
    static SO<Iterator<Vector> > transform(SO<Iterator<Vector> > points, const Matrix& matrix);
    static SO<PackedVertexIterator> translate(
        SO<Iterator<Vector> > vertices,
        const Vector& offset
    );
    static Bounds boundingBox(SO<Iterator<Vector> > vertices);
    static bool pointInPolygon(SO<Iterator<Vector> > polygon, const Vector& p);
    static bool polygonInPolygon(SO<Iterator<Vector> > polygon1, SO<Iterator<Vector> > polygon2);
    static Vector projectOntoLine(const Vector& p, const Vector& a, const Vector& b, double edgeLengthHint = -1.0);
    static Vector nearestPointOnSegment(const Vector& p, const Vector& a, const Vector& b, double edgeLengthHint = -1.0);
    static double pointLineDistance(const Vector& p, const Vector& a, const Vector& b, double edgeLengthHint = -1.0);
    static bool collinear(
        const Vector& a1,
        const Vector& b1,
        const Vector& a2,
        const Vector& b2, 
        double errorTolerance = 1.e-10
    );
    static bool parallel(
        const Vector& a1,
        const Vector& b1,
        const Vector& a2,
        const Vector& b2,
        double cosMaxAngle = 1. - 1.e-10
    );
    static Vector normal(SO<Iterator<Vector> > polygon);
    static double signedArea(SO<Iterator<Vector> > polygon);
    static bool counterclockwise(SO<Iterator<Vector> > polygon);
    static SO<Iterator<Vector> > orientLoop(SO<Iterator<Vector> > loop, bool ccw = true);
    static Vector bisectorRay(const Vector& a, const Vector& b, const Vector& c);
    static bool intersectLines(
        const Vector& a1,
        const Vector& b1,
        const Vector& a2,
        const Vector& b2,
        Vector& intersectionPoint,
        bool ignoreSection = true,
        double cosMaxAngle = 1. - 1.e-10
    );




    enum LineSection {
        SCR_BEFORE_A,     
        SCR_AT_A,   
        SCR_BETWEEN_AB,     
        SCR_AT_B,
        SCR_AFTER_B,      
    };
    static LineSection CheckLineSection(const Vector& a, const Vector& b, const Vector& p, double tolerance = -1.0);

    static double calculateAngleCCW(const Vector& a, const Vector& b, const Vector& c);



    static double calculateAngleCCW(const Vector& a, const Vector& b);

    static Vector rotateCCW(const Vector& a, double angle);

    static double forceAngleToRange(double angle);

    static bool anglesAreCCWOrdered(double alpha, double beta, double gamma);
        
    static Vector findPerpendicularVector(const Vector& v);
    static SO<Iterator<Vector> > boundingRectangle(SO<Iterator<Vector> > polygon);
    static SO<Iterator<Vector> > boundingRectangle(const Vector& a, const Vector& b, const Vector& c);
    static SO<Iterator<SO<Iterator<SO<Iterator<Vector > > > > > >
                        clipPolygons(SO<Iterator<SO<Iterator<Vector> > > > sp,
                                     SO<Iterator<SO<Iterator<Vector> > > > cp);




    static SO<Iterator<Vector> > clipConvexPolygons(
        SO<Iterator<Vector> > poly1,
        SO<Iterator<Vector> > poly2
    );

    static Vector nearestPoint(const Vector& point, const Bounds& bounds);

    static Vector furthestPoint(const Vector& point, const Bounds& bounds);

    static SO<Iterator<Vector> > expandLoop(SO<Iterator<Vector> > loop, double delta);

    static Vector centerOfLoop(SO<Iterator<Vector> > loop);

    static Matrix quadrilateralToQuadTransform(
        const Vector& t0,
        const Vector& t1,
        const Vector& t2,
        const Vector& t3,
        const Vector& min = Vector(-1.0, -1.0),
        const Vector& max = Vector( 1.0,  1.0)
    );

    static Matrix rotateToXZPlane(const Vector& planeNormal);

    static Vector getEdgeNormal(const Vector& a, const Vector& b, const Vector& c, bool xyPlane, bool normalized = true);

    static void growTriangle(Vector& a, Vector& b, Vector& c, int pixels, int atlasSize, bool xyPlane);

    static bool intersectionTest(
        const Vector& a1, const Vector& b1, const Vector& c1,
        const Vector& a2, const Vector& b2, const Vector& c2,
        bool xyPlane
    );

    static bool computeVertexTf(
        const Vector& a1, const Vector& a2, const Vector& a3,
        const Vector& b1, const Vector& b2, const Vector& b3,
        Matrix& result
    );

    static Vector polar2Cartesian(const Vector& p, const Vector& up = Vector(0,1,0));
    static Vector cartesian2Polar(const Vector& p, const Vector& up = Vector(0,1,0));

    static SO<Iterator<Vector> > generatePoissonDiskDistribution(SO<Facet> polygon, double radius);
    static SO<Iterator<Vector> > generatePoissonDiskDistribution(const Bounds& bounds, double radius, bool tiling = false);

    static SO<Iterator<Vector> > singleStepPoissonDiskDistribution(SO<Facet> polygon, double radius, bool clear = false);
    static SO<Iterator<Vector> > singleStepPoissonDiskDistribution(const Bounds& bounds, double radius, bool tiling, bool clear = false);


    static bool IntersectCircles(
        const VRS::Vector& m0, double radius0, 
        const VRS::Vector& m1, double radius1, 
        VRS::Vector& firstIntersection,
        VRS::Vector& secondIntersection
    );

    static bool LineSphereIntersection(
        const Vector& m, double r,
        const Vector& a, const Vector& b,
        Vector& firstIntersection,
        Vector& secondIntersection
    );    
};

typedef AlgorithmImpl<0,2,1> AlgorithmXZY;
typedef AlgorithmImpl<0,1,2> AlgorithmXYZ;
typedef AlgorithmXZY Algorithm;

} // namespace VRS

#endif // VRS_ALGORITHM_H

---

Generated on Fri May 18 06:00:13 2012 by Doxygen 1.5.6

© 2001-2010 Hasso-Plattner-Institut | Impressum | Contact