GU_TriDivide.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.
 *
 * NAME:        GU_TriDivide.h ( GU Library, C++)
 *
 * COMMENTS:
 */

#ifndef __GU_TriDivide__
#define __GU_TriDivide__

#include "GU_API.h"
#include <GA/GA_Edge.h>
#include <GA/GA_ElementWrangler.h>
#include <UT/UT_Map.h>
#include <UT/UT_PriorityQueue.h>
#include <UT/UT_Interrupt.h>

class GA_PrimitiveGroup;
class guDivTri;
class guDivTriEdge;
class guDivTriEdgeCompare;
class guEdgeToTrisMap;
class guPointVtxsChunks;
struct guTriVtxPair;
template<exint BUFFERSIZE>
class guTrisStackBufferArray;

class GU_API GU_TriDivide
{
public:
    GU_TriDivide(GU_Detail &gdp, const GU_Detail *refgdp, fpreal minlength, UT_Interrupt *boss = nullptr);

    virtual ~GU_TriDivide();

    /// Wrapper method for TriDivide that does pre-processing, the subdivision,
    /// and post-processing.
    void tridivide(int depth, fpreal minarea,
                   const UT_Matrix4D &projmatrix,
                   const UT_BoundingBoxD &bbox,
                   bool expand,
                   int numsplit, const GA_PrimitiveGroup *grp = nullptr);

private:
    typedef UT_PriorityQueue<guDivTriEdge, guDivTriEdgeCompare, false> guDivTriEdgeQueue;

    /// Builds the triangle list.
    void         buildTopology(const GA_PrimitiveGroup *grp = nullptr);
    
    /// Does root(3) subdivision. If minarea > 0, at each iteration any triangles
    /// with area less than minarea are not processed and left as is in the mesh.
    /// If a projection matrix is supplied, a perspective projection is applied to
    /// each point before measuring area, allowing culling in pixel space, for example.
    /// The point can be further tested for culling against a provided bounding box.
    /// If expand is true, the boundary of the culled triangles is expanded by one ring
    /// outward which gives a smoother subdivision over several iterations.
    void         subdivide(int depth, fpreal minarea,
                          const UT_Matrix4D &projmatrix,
                          const UT_BoundingBoxD &bbox,
                          bool expand);

    /// Equalizes edges by splitting the longest edges.
    /// Splits are done until every edge is less than minlength
    /// or number of splits numsplits has been done. A value of
    /// -1 is ignored.
    void         equalizeEdges(int numsplit);

    /// Transforms the triangle list into actual triangles.
    void         buildGeometry();

    /// If edge is longer than minlength, add the triangle it belongs to
    /// in the mapping of edges to adjacent triangles.
    void         addToEdgeMapIfLong(guEdgeToTrisMap &edgemap, const GA_Edge &edge, const guTriVtxPair &pair, const UT_Vector3Array &refpos) const;

    /// If edge is longer than minlength, add it to the priority queue
    /// of edges to be split, ordered from longest to shortest.
    void         addToEdgeQueueIfLong(guDivTriEdgeQueue &queue, GA_Offset pt_a, GA_Offset pt_b, const UT_Vector3Array &refpos) const;

    /// Calculate square of the distance between points a and b.
    fpreal       calculateLength2(GA_Offset a, GA_Offset b,
                                  const UT_Vector3Array &refpos) const;

    /// Find all tris that either have no points within the provided bbox
    /// or area less than minarea and append them as a new, exactly-sized
    /// chunk onto culledtrischunks (one chunk per call, rather than
    /// growing a single array in place, since culling tends to arrive in
    /// a few enormous bursts rather than gradually -- growing one array
    /// across calls would mean repeatedly re-copying everything collected
    /// by earlier calls).
    /// If a non-identity projection matrix is supplied, the previous tests
    /// are performed after doing a toNDC-style perspective projection.
    /// To index the remaining valid tris, the trioffsetstoindices and
    /// triindicestooffsets are filled where offset refers to a tri's
    /// position in myTriList and index refers to its order among
    /// the valid tris.
    exint        cullByArea(UT_Array<UT_Array<guDivTri>> &culledtrischunks,
                            UT_Array<exint> &trioffsetstoindices,
                            UT_Array<exint> &triindicestooffsets,
                            fpreal minarea, const UT_Matrix4D &proj,
                            const UT_BoundingBoxD &bbox, bool expand,
                            const UT_Vector3Array &refpos,
                            UT_Array<bool> &culledstorage,
                            UT_Array<exint> &culledtriindicestooffsets) const;

    /// Free the arrays in myPointToVtxsList by iterating over the
    /// points in myGdp. This must be done as these buffer arrays
    /// do not have a destructor as they are POD types.
    void         destructMyPointToVtxsList();

    /// Relax points and if depth > 0 then update myPtToVtxsList
    /// for all points excluding the newly added barycenter points.
    /// If depth is 0, then free myPtToVtxsList instead.
    void         relaxPointsAndUpdatePointVtxs(UT_Vector3Array &newpos, UT_Vector3Array &newrefpos,
                                               const UT_Vector3Array &pos, const UT_Vector3Array &refpos, bool useref,
                                               const GA_Range &ptrange,
                                               bool lastdepth, exint nvalid, const UT_Array<exint> *trioffsetstoindicesptr);

    /// Subdivide and flip all unculled triangles and if depth > 0
    /// then update myPtToVtxsList for the newly added barycenter
    /// points. Note that subdividing and flipping is done directly
    /// as a single step, not as two separate steps.
    void         subdivideAndFlipAndUpdateBarycenterVtxs(UT_Array<guDivTri> &newtrilist, GA_Offset barycenters_start_offset, bool lastdepth, exint nvalid,
                                                         const UT_Array<exint> *triindicestooffsetsptr, const UT_Array<exint> *trioffsetstoindicesptr);

    /// Set the mate offsets for the tris adjacent to a point.
    void         setMatesForTrisAtPoint(GA_Offset ptoff);

    /// Split the longest edge longer than minlength.
    void         splitEdge(guEdgeToTrisMap &edgemap, guDivTriEdgeQueue &queue, UT_Vector3Array &refpos,
                           const guDivTriEdge &triedge, fpreal ratio);

    /// The geometry to be subdivided and an optional reference geometry
    /// to be used for point positions if passed in and if it has at
    /// least as many points as myGdp.
    GU_Detail                                                       &myGdp;
    const GU_Detail * const                                     myRefGdp;
    
    // Separate GU_Detail that holds the source primitives IFF we need to
    // copy primitive attributes onto the subdivided result. See
    // buildTopology for where it's built and buildGeometry where it's used
    // for copying then deleted.
    UT_UniquePtr<GU_Detail>                      mySrcGdp;

    /// Array of triangles of the current state of the mesh.
    /// guDivTri is a POD type, so setSizeNoInit() should be used
    /// to grow it and elements should be initialized in parallel
    /// for performance.
    UT_Array<guDivTri>                                          myTriList;

    /// Point wrangler for averaging attribute values and positions
    /// for newly added points. These are either the barycenters
    /// during subdivision or midpoints during edge splits.
    GA_PointWrangler                                            myPointWrangler;

    /// Maps point offsets to the vertex/triangle pairs referencing that
    /// point in myTriList. Backed by chunked storage (guPointVtxsChunks,
    /// defined in GU_TriDivide.C) rather than one flat array grown in place
    /// across subdivide() iterations -- see that class for why. Held by
    /// pointer since guPointVtxsChunks is a private implementation detail
    /// not exposed here, same as guDivTri/guEdgeToTrisMap/etc. above.
    /// There should only be elements at point offsets in myGdp and, since
    /// they do not have a destructor, the point offsets will have to be
    /// iterated over to manually destruct them (destructMyPointToVtxsList()).
    guPointVtxsChunks                                          *myPointToVtxsList;

    /// The min length and its square for edge splitting.
    const fpreal                                                myMinLength;
    const fpreal                                                myMinLength2;

    UT_Interrupt * const                                        myBoss;
};

#endif