GQ/GQ_Detail.h

Go to the documentation of this file.

/*
 * PROPRIETARY INFORMATION.  This software is proprietary to
 * Side Effects Software Inc., and is not to be reproduced,
 * transmitted, or disclosed in any way without written permission.
 *
 * Produced by:
 *      David Wong
 *      Side Effects
 *      477 Richmond Street West
 *      Toronto, Ontario
 *      Canada   M5V 3E7
 *      416-504-9876
 *
 * NAME:        Quad Edge Library (C++)
 *
 */

#ifndef _GQ_Detail_h_
#define _GQ_Detail_h_

#include "GQ_API.h"
#include <UT/UT_PtrArray.h>
#include <UT/UT_IntArray.h>
#include <UT/UT_Plane.h>
#include <UT/UT_FloatArray.h>
#include <UT/UT_RefArray.h>

#include <GEO/GEO_Primitive.h>
#include <GU/GU_RayIntersect.h>
#include <GU/GU_PrimPoly.h>
#include <GU/GU_Types.h>
#include "GQ_Error.h"

class GU_Detail;
class GQ_Edge;
class GQ_Face;
class GQ_Point;
class GEO_Point;
class GEO_PrimPoly;
class GB_PrimitiveGroup;
class GB_Edge;
class GB_EdgeGroup;
class GQ_StitchParms;
class GQ_SubdivideParms;

enum GQ_BooleanOpType {
    GQ_BOOLEAN_INTERSECT        = 0,
    GQ_BOOLEAN_UNION            = 1,
    GQ_BOOLEAN_A_MINUS_B        = 2,
    GQ_BOOLEAN_B_MINUS_A        = 3,
    GQ_BOOLEAN_A_EDGE           = 4,
    GQ_BOOLEAN_B_EDGE           = 5 
};  

/// Quad Edge data structure for topological manipulation of polygonal data.
///
/// The Quad Edge data structure was invented by Guibas & Stolfi in their
/// 1985 paper, "Primitives for the Manipulation of General Subdivisions and
/// the Computation of Voronoi Diagrams", ACM Transactions on Graphics,
/// 4(2):74-123, April 1985.
///
/// That paper has a good description of the capabilities of the data
/// structure, and the definition of its basic operators, makeedge and splice().
class GQ_API GQ_Detail {
public:
    /// The super_point_tolerance should probably be set to -1 which flags
    /// for no super points to be generated.  Super points often cause
    /// confusing (for the caller) results.
                                 GQ_Detail(GU_Detail *gdp,
                                           GB_PrimitiveGroup * = 0,
                                           float super_point_tolerance = 1E-6);
                                ~GQ_Detail();

    void                         clearAndDestroy(void);
    /// Cusp polygons which have adjacent edges larger than angle (in degrees)
    void                         cusp(float angle, bool no_cut = false);

    /// Cusp edges in a group
    void                         cusp(const GB_EdgeGroup &edges,
                                      bool do_cut = false);


    /// Both clip() and crease() will invalidate this GQ_Detail. If you wish
    /// to do another GQ_Detail operation, create a new GQ_Detail.
    /// {
    void                         clip(UT_Vector3 &norm, float distance,
                                      int normalize);
    int                          crease(UT_Vector3 &norm, float distance,
                                        int normalize, int outputGroups,
                                        GB_PrimitiveGroup *primitive_above=0, 
                                        GB_PrimitiveGroup *primitive_below=0);
    /// }
    
    void                         bricker(float sizex = 1.0, float sizey = 1.0,
                                         float sizez = 1.0, float offx = 0.0,
                                         float offy = 0.0, float offz = 0.0,
                                         float anglex = 0.0, float angley = 0.0,
                                         float anglez = 0.0,
                                         bool fixsharededges = false);
    void                         doBoolean(const GU_Detail *A,
                                         const GU_Detail *B, 
                                         GQ_BooleanOpType op, 
                                         const int outputGroups = 0,
                                         const char *AgroupName = 0, 
                                         const char *BgroupName = 0,
                                         int accurateAttrib = 0,
                                         int trials = 5);
    void                         smooth(int divisions, float relativeSize,
                                        float weight);

    // For polygon smoothing (fairing).
    // Can smooth float attributes too.  If useptattrib and attriboffset >= 0,
    // then use point attribute, otherwise if useptattrib is false and
    // attriboffset >= 0, then use vertex attributes, otherwise use
    // point positions.
    void                         smoothPolygons(int iterations,
                                            GU_WeightingType type,
                                            float lambda, float mu,
                                            bool useptattrib,
                                            const GB_AttributeRef &attriboffset,
                                            int  attribsize);

    // Adds edge weights to the GQ_Detail. (If not already present)
    void                         createEdgeWeights();

    // This is used to set up the edge weights:
    // The following method assumes that poly is not in the GQ_Detail.  It can
    // be, but it is not a requirement.
    void                         setCreaseWeight(const GEO_PrimPoly &poly,
                                                float weight);
    // With the following method the poly can be in the GQ_Detail or in another
    // gdp.  It requires the creaseweight attribute on the polygon or on the
    // vertices of the polygon.  If either the vtxoff or primoff is >= 0, that
    // attribute will be used...
    void                         setCreaseWeight(const GEO_PrimPoly &poly,
                                        const GB_AttributeRef &vtxoff,
                                        const GB_AttributeRef &primoff);

    // Given a GB_Edge, we can map this to a GQ_Edge and set the corresponding
    // weight.
    void                         setCreaseWeight(const GB_Edge &edge,
                                                float weight);

    // This is similar to the setCreaseWeight method for GEO_PrimPoly,
    // but the edge supplied is the only one affected.  This edge must
    // belong to a poly (so that the attribute can be grabbed).
    void                         setCreaseWeight(const GB_Edge &gedge,
                                        const GB_AttributeRef &vtxoff,
                                        const GB_AttributeRef &primoff);
    

    float                        getEdgeWeight(const GB_Edge &edge);
    void                         subdivide(const GQ_SubdivideParms &parms,
                                    GB_PrimitiveGroup *nonsubdivprims);
    void                         dual();
    void                         stitch(const GQ_StitchParms &parms);
    int                          stitchEdges(GU_PrimPoly &polya,
                                    const UT_PtrArray<GU_PrimPoly *> &facea,
                                    GU_PrimPoly &polyb,
                                    const UT_PtrArray<GU_PrimPoly *> &faceb,
                                    GB_PrimitiveGroup &changedpolys, 
                                    float tol, int clamp, int consolidate);
    void                         makeWire(float radius, int doSpheres,
                                          int doCaps);
    void                         buildGeometry();
    void                         buildCreases(GB_PrimitiveGroup *group = 0);
    void                         copyEdgeWeightToVertex();
    void                         unHole(int maintain);
    void                         boundary();
    void                         createCuspGroup(float, GB_PrimitiveGroup*grp);
    void                         createBoundaryGroup(GB_PrimitiveGroup &grp);
    void                         createBoundaryGroup(GB_PointGroup &grp,
                                    UT_IntArray *arr);
    void                         createBoundaryGroup(const GEO_Point *ppt,
                                                     GB_PointGroup &pointgroup);
    void                         createBoundaryGroup(const GB_Edge  &edge,
                                                     GB_PointGroup  &grp,
                                                     GEO_PrimPoly  *&poly);
    /// For each boundary loop a separate UT_IntArray is added to the ptlist.
    /// These intarrays will contain the point numbers, in order, of the
    /// points that belong to those boundaries.
    /// This is preferable to the group based approach becausae it can
    /// handle duplicate points that show up on the boundary of certain
    /// degenerate geometry..
    void                         createBoundaryList(UT_RefArray<UT_IntArray> &ptlist);
                                            

//  Creates a point group of those points which are adjacent by the certain
//  given number of edges.
    void                         groupEdgePoints(const GEO_Point *ppt,
                                                 int depth,
                                                 GB_PointGroup &point_group);

    int                          isClose();
                                 
    // deleteAllShareEdges is only for testing deleteShareEdge
    // which will be used for polygon reduction.
    // Don't use it for deleting all shared edges (ie. want only the boundary)
    void                         deleteAllShareEdges();


    GQ_Point                    *appendPoint(const GQ_Point *src=0);
    GQ_Edge                     *appendEdge();
    GQ_Face                     *appendFace(GEO_PrimPoly *poly);
    void                         removePoint(GQ_Point *p);
    void                         removePoint(int i);
    void                         removeEdge(GQ_Edge *e);
    void                         removeEdge(int i);
    void                         removeFace(GQ_Face *f);
    void                         removeFace(int i);
    void                         collapseEdgeList() { myEdges.collapse(); }
    void                         collapseFaceList() { myFaces.collapse(); }
    UT_PtrArray<GQ_Point *>     &getPointList()     { return myPoints; }
    const UT_PtrArray<GQ_Point *>&getPointList() const { return myPoints; }
    UT_PtrArray<GQ_Edge *>      &getEdgeList()      { return myEdges; }
    const UT_PtrArray<GQ_Edge *>&getEdgeList() const{ return myEdges; }
    UT_FloatArray               &getEdgeWeights()   { return myEdgeWeights; }
    const UT_FloatArray         &getEdgeWeights() const { return myEdgeWeights; }
    UT_PtrArray<GQ_Face *>      &getFaceList()      { return myFaces; }
    const UT_PtrArray<GQ_Face *>&getFaceList() const{ return myFaces; }
    GU_Detail                   *getGdp()           { return myGdp; }
    const GU_Detail             *getGdp() const     { return myGdp; }
    GU_RayIntersect             *getRay()           { return myRay; }
    void                         buildRay()
                                 {
                                    if (myRay) delete myRay;
                                    myRay = new GU_RayIntersect(myGdp, myGroup);
                                 }
    UT_RefArray<GB_AttributeRef> &getOffsets()       { return myOffsets; }
    

    /// Split edge will return 0 if t is too close to 0 or 1.
    GQ_Point                    *splitEdge(GQ_Edge *edge, float t);
    void                         splitEdge(GQ_Edge *edge, GQ_Detail *B);
    GQ_Edge                     *splitEdge(GQ_Edge *, GQ_Point &pt);
    void                         deleteShareEdge(GQ_Edge *edge, 
                                         GB_PrimitiveGroup *deletePrimGroup=0);

    void                         wireEdge(GQ_Edge *edge, float radius,
                                          int doCaps);
    void                         pointSphere(GQ_Point *pt, float radius);

    int                          nEdges(void) const { return myEdges.entries();}
    int                          nFaces(void) const { return myFaces.entries();}
    int                          nPoints(void) const{return myPoints.entries();}
    GU_Detail                   *getDetail(void) const { return myGdp; }
    // Only test a point of face
    int                          aboveOrBelow(GQ_Face *face);
    void                         markPoints(GQ_Detail *B);
    void                         markEdges(GQ_Detail *B);
    void                         markFaces(GQ_Detail *B);
    void                         markFace(GQ_Face *f, GQ_Detail *B);
    void                         markComponent(GQ_Face *f, unsigned mark);
    void                         markComponent();
    void                         buildAllSplitFaces(GQ_Detail *B);
    void                         buildSplitFaces(GQ_Face *face, 
                                                 GQ_Edge *edge, GQ_Detail *B);
    void                         traceIntersectEdges();
    void                         traceIntersectEdges(GQ_Edge *edge);
    void                         cleanOffsets();
    void                         setupOffsets();
    void                         deleteAllFaces(GB_PrimitiveGroup *);
    void                         deleteAllMaskFaces(unsigned mask, 
                                                    GB_PrimitiveGroup *);
    void                         correctAllFaceMarkings();
    void                         flipAllFaceNormals();

    // Methods used by decimation
    void                         simpleDecimate(int targetPolys);
    void                         meshOptimize(float tol = 1E-5);
    void                         decCollapse(GQ_Edge *e, GB_PrimitiveGroup *);
    void                         decSplit(GQ_Edge *e);
    void                         decSwap(GQ_Edge *e);
    // End of the decimation methods

    void                         save(ostream &os) const;
    friend ostream              &operator<<(ostream &os, const GQ_Detail &d)
                                 { d.save(os); return os; }

    /// Given a GB_Edge, return the equivalent GQ_Edge. Relatively
    /// efficient: O(degree(org)), not O(nedges)
    GQ_Edge                     *findEdge(const GB_Edge *edge);
    GQ_Edge                     *findEdge(const GQ_Point *org, const GQ_Point *dest);
    GEO_Point                   *stepForward(const GB_Edge *edge);

    //Returns the first point encountered connected to the org, otherwise
    //null
    GEO_Point                   *pickArbitraryConnectedPoint(const GEO_Point *org);
    
    //Rotates the edge around a specified origin and resturns the new
    //destination point
    GEO_Point                   *rotateAboutOrigin(GB_Edge &edge, int dir);

    /// Be very, very careful using this method. GQ_Detail was never
    /// designed to be duplicated, and this method doesn't make a true
    /// copy. It does do a deep copy of the edge/face/point structures, but
    /// the two GQ_Detail objects still reference the same GDP, and could
    /// hence easily cause problems.
    ///
    /// Also, several parts of the member data are *not* currently
    /// duplicated, including
    /// - edge weights
    /// - ray info
    /// - attribs used during subdivide
    /// - spare pointers on faces/points
    ///
    /// Finally, this method will modify this GQ_Detail by changing the
    /// faces' index member data. Be forewarned!
    ///
    /// This method was written for GQ_PolyDelaunay, which needed a way to
    /// "backup" a GQ_Detail and revert if an error occurred. That code is
    /// very careful to avoid making any changes to the underlying gdp.
    GQ_Detail                   *duplicate() const
                                 { return new GQ_Detail(*this); }
    
    // Returns the face that is adjacent to 'face' on the edge indexed by 'edge'
    GEO_PrimPoly                *adjacentFace(const GEO_Face &face, int edge);

private:
    /// Very dangerous. See duplicate() for details.
                                 GQ_Detail(const GQ_Detail &);

    /// Prohibited. Copying a GQ_Detail is too dangerous to be encouraged.
    /// See duplicate() for more details.
    /// @{
    GQ_Detail                   &operator=(const GQ_Detail &);
    /// @}

    void                         snapToPlane(UT_Vector3 &norm, float dist);
    void                         buildSuperPoints(float distance);
    GQ_Edge                     *findEdgeToShare(GQ_Point *org, GQ_Point *dest);
    GB_PrimitiveGroup           *convertToQuadEdge(GB_PrimitiveGroup *,
                                                   float sp_tol=0.001F);
    void                         addEdgeToPt(GQ_Edge *e, GQ_Point *p);
    void                         cleanEdgeToPt(GQ_Point *p);
    int                          buildFace(GQ_Face *face);
    int                          getVertexNum(const GQ_Face *face,
                                              const GEO_Point *prevPt,
                                              const GEO_Point *pt) const;
    void                         creaseFace(GQ_Face *face, UT_Vector3 &norm,
                                            float dist, 
                                            int outputGroups,
                                            GB_PrimitiveGroup *prim_above = 0,
                                            GB_PrimitiveGroup *prim_below = 0);
    void                         createCreaseFace(GQ_Edge *edge,
                                          UT_Vector3 &norm, float dist,
                                          int outputGroups,
                                          GB_PrimitiveGroup *prim_above = 0,
                                          GB_PrimitiveGroup *prim_below = 0);
    void                         addIntersectEdges(GQ_Face *face,
                                                   UT_Vector3 &normal);

    /// Follows e->lnext() checking if e->org() has flag set, returns true
    /// if it does.  The nonBridge component meanss when it hits a bridge
    /// it doesn't follow it, but runs e->oprev() instead.
    bool                         nonBridgeLoopHasFlag(GQ_Edge *e, int flag);

    /// Removes all the bridges on the face that are no longer necessary
    /// if we connect together points that are GQ_SELECTED.
    /// The bridges array is filled with any bridge edges that have
    /// GQ_INTERSECT flag and weren't deleted.  (It is hard to get
    /// this afterwards since you'll no longer have a single face)
    void                         removeAllPossibleBridges(GQ_Face *face,
                                        UT_PtrArray<GQ_Edge *> &bridges);
    GQ_Edge *                    removePossibleBridge(GQ_Edge *bridgeEdge,
                                        bool hasisect,
                                        int depth,
                                        UT_PtrArray<GQ_Edge *> &bridges);
    void                         reBridge(UT_PtrArray<GQ_Edge *> &bridges);
    void                         reBridgeForCrease(UT_PtrArray<GQ_Edge *>
                                                            &intersectBridges);
    UT_PtrArray<GQ_Face *>      *split(UT_Vector3 &normal, float distance,
                                       int outputGroups = 0,
                                       GB_PrimitiveGroup *prim_above = 0,
                                       GB_PrimitiveGroup *prim_below = 0);
    void                         expandPoint(GQ_Point *pt);
    void                         plugGap(GQ_Edge *edge);
    void                         shrinkFace(GQ_Face *face, float a, float b);
    void                         unHole(GQ_Face *face, int maintain);
    GQ_Edge *                    unBridge(GQ_Edge *bridgeEdge, int maintain);
    void                         changeGeoPoint(GQ_Face *face, GEO_Point *opt, 
                                                GEO_Point *npt, int all);
    void                         uniqueEdge(GQ_Edge *edge);
    void                         uniquePoint(GQ_Point *point);
    void                         cleanFace(GQ_Face *face);
    int                          twoFacesShareAllEdges(GQ_Edge *edge, 
                                           GB_PrimitiveGroup *deletePrimGroup);

    // Semi-smooth Catmull-Clark subdivision:
    void                 calcFacePoints(int numfaces);
    void                 calcEdgePoints(int numedges, 
                                        GEO_Vertex **oldEdgeAttribs,
                                        bool smoothvertex);
    void                 calcVertexPoints(int numpoints,
                                        GEO_Vertex **oldEdgeAttribs,
                                        GB_AttributeData *newVertexAttribs,
                                        bool smoothvertex);

    // This has one vertex attribute per point which will be copied in
    // to all the edge attributes comeing out of that point.
    void                 copyVertexAttributeByPoint(int numpoints,
                                        GB_AttributeData *newVertexAttribs);
    void                 calcEdgeAttribs(int numedge);
    // This is used after the edge attributes are calculated.  It will
    // then set the GQ_VTXBOUNDARY appropriately for all points.
    void                 flagVertexBoundaries();
    void                 subdivideEdges(int numedges, bool linear);
    void                 subdivideFaces(int numfaces);

    // This copies the myEdgeAttribs into the geometrie's polygons:
    void                 copyVertexAttributes(int numedges);

    void                 splitPolysWithMultipleHoles(GB_PrimitiveGroup *,
                            UT_PtrArray<GQ_Point *> &);
    GEO_PrimPoly        *findNonSubDivPolyWithEdge(const GEO_Point *,
                            const GEO_Point *, GB_PrimitiveGroup *, int &,
                            int &);
    GEO_PrimPoly        *findNonSubDivPolyWithEdge(const GEO_Point *,
                            const GEO_Point *, GB_PrimitiveGroup *);
    GQ_Edge             *findBoundEdge(const GQ_Point *, const GQ_Point *,
                            UT_Vector4 &, UT_Vector4 &, int &);
    int                  addSubDivBoundaryPoints(GQ_Edge *, const GQ_Point *,
                            GB_PointGroup *);
    void                 createVirtualEdgePoints(const UT_Vector4 &,
                            const UT_Vector4 &, GB_PointGroup *,
                            UT_Vector4Array &);
    void                 createActualEdgePoints(const UT_Vector4 &,
                            const UT_Vector4 &, GB_PointGroup *,
                            GB_PointGroup *);
    void                 triangulateNonSubDivPoly(GEO_PrimPoly *,
                            GB_PointGroup *, GB_PrimitiveGroup *,
                            GEO_Point *, GEO_Point *, GEO_Point *, GEO_Point *,
                            int);
    GEO_PrimPoly        *dividePolygonContainingEdge(GB_PointGroup *,
                            const GEO_Point *, const GEO_Point *,
                            GB_PrimitiveGroup *, int,
                            GEO_Point *&, GEO_Point *&);
    void                 pullHolesUsingBias(GB_PointGroup *,
                            UT_Vector4Array &, float);
    void                 stitchHoles(GB_PointGroup *, GB_PointGroup *,
                            GEO_PrimPoly *, int);
    void                 pullToEndPoints(GB_PointGroup *, GEO_Point *,
                            GEO_Point *);
    void                 closeHolesAfterSubdivide(UT_PtrArray<GQ_Point *> &,
                            GB_PrimitiveGroup *, const GQ_SubdivideParms &);

    // Goes through the edges of p and modifies vertex attributes of edges
    // with a GQ_CUSP flag to make them cusp'd
    void cuspPoint(GQ_Point *p, GB_AttributeRef normalOffset, int i);

    
    UT_PtrArray<GQ_Edge *>       myEdges;
    UT_FloatArray                myEdgeWeights;
    UT_PtrArray<GQ_Point *>      myEdgePoints;
    UT_PtrArray<GQ_Face *>       myFaces;
    UT_PtrArray<GQ_Point *>      myPoints;
    UT_RefArray<GB_AttributeRef> myOffsets;
    GB_PrimitiveGroup           *myGroup;       // Primitive group
    GU_Detail                   *myGdp;
    GU_RayIntersect             *myRay;

    // This data is used by subdivide:
    // For most of subdivide, myEdgeAttribs maps edge indices into vertex data,
    // but in the edge-closing situation it is reinterpreted to map
    // point numbers into vertex data.
    UT_PtrArray<GEO_Vertex *>    myEdgeAttribs;
    UT_PtrArray<GEO_Vertex *>    myFaceAttribs;
};

#endif

---