GU_EdgeMesh.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_EdgeMesh.h ( GU Library, C++)
 *
 * COMMENTS:
 *      GU_EdgeMesh represents a mesh with edge connectivity information. There
 *      is support for solving the Eikonal equation (propagates from source
 *      points with the given speed, along edges), the Poisson equation (finds
 *      a smooth field whose gradient aligns best with gradient of a target
 *      field and satisfies the given boundary conditions), and a timestep of
 *      the diffusion equation (models propagation of heat at the vertices along
 *      the edges).
 */

#ifndef __GU_EdgeMesh_h__
#define __GU_EdgeMesh_h__

#include "GU_API.h"
#include "GU_Detail.h"

#include <UT/UT_Array.h>
#include <UT/UT_Map.h>
#include <UT/UT_Set.h>

/// Forward-declaration of the internal cache class.
template<typename T>
class gu_EMSolveCache;

/// This base class implements the low-level solve routines for GU_EdgeMesh.
template<typename T>
class GU_API GU_EdgeMeshBase
{
public:
    /// The constructor does nothing... The programmer should interface with a
    /// concrete subclass which implements buildMesh() (like GU_EdgeMesh).
    GU_EdgeMeshBase();
    virtual ~GU_EdgeMeshBase();
    virtual void buildMesh(const GU_Detail* gdp) = 0;

    /// Set the minimum distance between adjacent nodes used by the solver.
    void setMinimumDistance(T min_dist);

    /// This function calculates arrival times for vertices given the starting
    /// vertices and propagation speeds.
    /// If USE_SPEEDS is false, the speeds array is unused; in this case, each
    /// vertex is assumed to have a speed of 1.
    /// times and speeds should come in pre-initialized. times(x) should be set
    /// to the respective arrival time for starters; for non-starters, it should
    /// be set to a large value (preferrably infinity).
    template<bool USE_SPEEDS>
    void solveEikonal(UT_Array<T>& times, const UT_Array<T>& speeds,
                      const UT_Set<int>& starters) const;

    /// Computes the Laplacian of the function defined in vals.
    void laplacian(UT_Array<T>& result, const UT_Array<T>& vals) const;
    /// Computes the weighted Laplacian (divergence of product of weights with
    /// the gradient of vals).
    void weightedLaplacian(UT_Array<T>& result, const UT_Array<T>& vals,
                           const UT_Array<T>& weights) const;

    /// Solves the boundary value problem for the Poisson equation. Vertices in
    /// pinned are the boundary conditions, with their values given by the
    /// respective entry in sol.
    /// def is the default value to give to unpinned components.
    void solvePoisson(UT_Array<T>& sol, const UT_Array<T>& rhs,
                      const UT_Set<int>& pinned, T def = 0) const;

    /// Solves the boundary value problem for the heat equation. Vertices in
    /// pineed are the fixed Dirichlet boundary conditions, with their values
    /// given by the respective entry in sol. dt is size of the time step: its
    /// value must be positive. If provided, the rates array is assumed to
    /// contain conductivities at the vertices.
    void solveDiffusion(UT_Array<T>& sol, const UT_Array<T>* rates,
                        const UT_Set<int>& pinned, T dt) const;

protected:
    /// Internal function to signal that the diffusion rates will be used for
    /// the next diffusion solve. This is for caching optimization.
    void setDiffusionRatesCacheIds(bool used, GA_DataId id, float min_rate)
        const;

    /// Resets the internal cache. Should only be called if the graph changed.
    void resetCache() const;

protected:
    /// Number of vertices in this graph.
    int                         myNumVertices;
    /// Adjacency list for each vertex.
    UT_Array<UT_Set<int>>       myVertexConnections;
    /// Array of point locations in space.
    UT_Array<UT_Vector3T<T>>    myVertexPositions;
    /// Our solve cache to speed up subsequent similar solves.
    gu_EMSolveCache<T>*         mySolveCache;

    /// Minimum squared distance between nodes; maximum edge weight is the
    /// reciprocal of this value.
    T                           myMinDist2;
};

template<typename T>
class GU_API GU_EdgeMesh : public GU_EdgeMeshBase<T>
{
public:
    using Base = GU_EdgeMeshBase<T>;

    GU_EdgeMesh();
    ~GU_EdgeMesh() override {}

    /// Constructs the edge mesh from its detail. This function must be called
    /// before the solve routines can be invoked.
    /// NOTE: the graph will only be rebuilt if the topology or point positions
    /// changed.
    void buildMesh(const GU_Detail* gdp) override;

    /// This function calculates arrival times for all points in the mesh, given
    /// the starting vertices (the ones in the pinned group, which are arrived
    /// at the current value of the dst attribute) and propagation speeds (read
    /// from the speeds point attribute).
    /// Results are written in the destination point attribute. Points that are
    /// not reachable from the starters get the value of unreachable.
    /// The attributes and the group must be defined for points and be for the
    /// same detail as the one this mesh was built from. If speeds are not
    /// provided, speed of 1 is assumed for every point.
    void solveEikonalAttrib(GA_Attribute* dst, const GA_Attribute* speeds,
                            const GA_PointGroup* pinned, T unreachable) const;

    /// This function solves the Poisson boundary value problem. Points in the
    /// pinned group are the boundary conditions, and the field will be as close
    /// as possible to the values defined in the source attribute; if a source
    /// attribute is not given, it will be assumed to be constant.
    /// Matching weights can also be provided; if given, they control how
    /// closely the source field is to be matched at each point (weight values
    /// should be between 0 and 1). Alternatively, the actual field to match is
    /// a convex combination of the incoming source field and a linear function;
    /// the weight then controls the contribution of the source field.
    /// Results are written in the destination point attribute.
    /// The attributes and the group must be defined for points and be for the
    /// same detail as the one this mesh was built from.
    void solvePoissonAttrib(GA_Attribute* dst, const GA_Attribute* src,
                            const GA_Attribute* weights,
                            const GA_PointGroup* pinned) const;

    /// This function solves a single time step of the heat equation. Points
    /// in the pinned group are assumed to be fixed boundary conditions (this
    /// can be NULL if there are no fixed boundaries). The conductivity rates
    /// can vary per attribute (specified in rates, values are clamped from
    /// below at min_rate).
    void solveDiffusionAttrib(GA_Attribute* dst, const GA_Attribute* rates,
                              const GA_PointGroup* pinned, T dt, T min_rate)
        const;

protected:
    /// Writes the contents of the array (indexed within this mesh) to the
    /// given attribute. The attribute must live on points of this mesh's
    /// detail.
    /// If WRITE_TO_ALL is true, points not in the mesh will write the value of
    /// def.
    /// If CHECK_EQUALITY is true, def is written for points whose value in src
    /// is the same as equal. If CHECK_EQUALITY is false, this parameter is not
    /// used.
    template<bool WRITE_TO_ALL, bool CHECK_EQUALITY = false>
    void writeArrayToAttribute(GA_Attribute* dst, const UT_Array<T>& src,
                               int comp, T def, T equal) const;

    /// Reads values from the given attribute and writes them to the destination
    /// array. Also adds every point in the given source group to the
    /// destination set.
    void copyArrayFromAttributeAndSetPinned(UT_Array<T>& dst_a,
                                            UT_Set<int>& dst_s,
                                            const GA_Attribute* src_a,
                                            const GA_PointGroup* src_s) const;

    /// Reads values from the given attributes and writes them to the
    /// destination arrays. Also adds every point in the given source group to
    /// the destination set.
    /// The second attribute and point group must be non-null. a1 is left
    /// untouched if ar1 is null. a2 is set to the value of the attribute for
    /// each pinned point; it is set to def for points not in the group.
    void copyArraysFromAttributesAndSetPinned(UT_Array<T>& a1,
                                              const GA_Attribute* ar1,
                                              UT_Array<T>& a2,
                                              const GA_Attribute* ar2,
                                              T def,
                                              UT_Set<int>& dst_s,
                                              const GA_PointGroup* src_s) const;

    /// Adds every point in the given source group to the destination set.
    void setPinnedFromGroup(UT_Set<int>& dst, const GA_PointGroup* src) const;

    /// Reads values from the given attribute and writes them to the destination
    /// array.
    /// If CLAMP_* is true, values will be clamped beyond that endpoint (given
    /// by below and above function arguments).
    template<bool CLAMP_BELOW = false, bool CLAMP_ABOVE = false>
    void copyArrayFromAttribute(UT_Array<T>& dst, const GA_Attribute* src,
                                int comp, T below = 0, T above = 1) const;

protected:
    /// Pointer to the detail this is to be built from.
    const GU_Detail*            myDetail;
    /// Data ID for mesh topology of the last built graph.
    GA_DataId                   myTopologyId;
    /// Data ID for the position attribute of the last built graph.
    GA_DataId                   myPositionId;
    /// Mapping of point offsets in the detail to indices in the mesh.
    UT_Map<GA_Offset, int>      myIndexMap;
};

GU_EXTERN_TEMPLATE(GU_EdgeMeshBase<fpreal32>);
GU_EXTERN_TEMPLATE(GU_EdgeMeshBase<fpreal64>);
GU_EXTERN_TEMPLATE(GU_EdgeMesh<fpreal32>);
GU_EXTERN_TEMPLATE(GU_EdgeMesh<fpreal64>);

#endif