Unions¶

As discussed in Signed distance fields, a union of signed distance fields can be created provided that the objects do not touch or overlap. EBGeometry provides two implementations:

Standard union where one looks through every primitive in the union.
BVH-enabled union where bounding volume hierarchies are used to find the closest object.

Standard union¶

The standard union is template as

class Union : public ImplicitFunction<T>
{
public:
  // Regular CSG union only requires implicit functions.
  static_assert(std::is_base_of<EBGeometry::ImplicitFunction<T>, P>::value,
                "Union requires an implicit function (for now)");

  /*!
    @brief Disallowed, use the full constructor
  */
  Union() = delete;

  /*!
    @brief Full constructor. Computes the CSG union
    @param[in] a_primitives List of primitives
    @param[in] a_flipSign   Hook for turning inside to outside
  */
  Union(const std::vector<std::shared_ptr<P>>& a_primitives, const bool a_flipSign);

  /*!
    @brief Destructor (does nothing)
  */
  virtual ~Union() = default;

  /*!
    @brief Value function
    @param[in] a_point 3D point.
  */
  T
  value(const Vec3T<T>& a_point) const noexcept override;

protected:
  /*!
    @brief List of primitives
  */
  std::vector<std::shared_ptr<const P>> m_primitives;

  /*!
    @brief Hook for turning inside to outside
  */
  bool m_flipSign;
};

#include "EBGeometry_NamespaceFooter.hpp"

Note that EBGeometry::Union inherits from EBGeometry::SignedDistanceFunction and thus provides a signedDistance(...) function. The implementation of the standard union is

Union<T, P>::Union(const std::vector<std::shared_ptr<P>>& a_primitives, const bool a_flipSign)
{
  for (const auto& prim : a_primitives) {
    m_primitives.emplace_back(prim);
  }

  m_flipSign = a_flipSign;
}

template <class T, class P>
T
Union<T, P>::value(const Vec3T<T>& a_point) const noexcept
{
  T ret = std::numeric_limits<T>::infinity();

  for (const auto& prim : m_primitives) {
    ret = std::min(ret, prim->value(a_point));
  }

  T sign = (m_flipSign) ? -1.0 : 1.0;

  return sign * ret;
}

#include "EBGeometry_NamespaceFooter.hpp"

That is, it iterates through all the objects in order to find the signed distance.

BVH-enabled union¶

The BVH-enabled union is implemented by EBGeometry::UnionBVH as follows:

*/
template <class T, class P, class BV, size_t K>
class UnionBVH : public ImplicitFunction<T>
{
public:
  static_assert(std::is_base_of<EBGeometry::SignedDistanceFunction<T>, P>::value, "UnionBVH requires an SDF (for now)");

  using BVConstructor = EBGeometry::BVH::BVConstructorT<P, BV>;

  /*!
    @brief Disallowed, use the full constructor
  */
  UnionBVH() = delete;

  /*!
    @brief Full constructor.
    @param[in] a_distanceFunctions Signed distance functions.
    @param[in] a_flipSign          Hook for turning inside to outside
    @param[in] a_bvConstructor     Bounding volume constructor.
  */
  UnionBVH(const std::vector<std::shared_ptr<P>>& a_distanceFunctions,
           const bool                             a_flipSign,
           const BVConstructor&                   a_bvConstructor);

  /*!
    @brief Destructor (does nothing)
  */
  virtual ~UnionBVH() = default;

  /*!
    @brief Value function
    @param[in] a_point 3D point.
  */
  T
  value(const Vec3T<T>& a_point) const noexcept override;

  /*!
    @brief Get the bounding volume
  */
  const BV&
  getBoundingVolume() const noexcept;

protected:
  /*!
    @brief Root node for linearized BVH tree
  */
  std::shared_ptr<EBGeometry::BVH::LinearBVH<T, P, BV, K>> m_rootNode;

  /*!
    @brief Hook for turning inside to outside
  */
  bool m_flipSign;

  /*!
    @brief Build BVH tree for the input objects. User must supply a partitioner
    and a BV constructor for the SDF objects.
    @param[in] a_bvConstructor Constructor for building a bounding volume that
    encloses an object.
  */
  inline void
  buildTree(const std::vector<std::shared_ptr<P>>& a_distanceFunctions, const BVConstructor& a_bvConstructor) noexcept;
};

#include "EBGeometry_NamespaceFooter.hpp"

#include "EBGeometry_UnionBVHImplem.hpp"

#endif

As always, the template parameter T indicates the precision, BV the bounding volume type and K the tree degree. UnionBVH takes a bounding volume constructor in addition to the list of primitives, see Construction.

Internally, UnionBVH defines its own partitioning function which is identical to the implementation for DCEL meshes (see BVH integration), with the exception that the partitioning is based on the centroids of the bounding volumes rather than the centroid of the primitives. After partitioning the primitives, the original BVH tree is flattened onto the compact representation.

The implementation of the signed distance function for the BVH-enabled union is

  // distance but there is still a CSG union, and the BVH is still a useful thing.
  // So, we can't use LinearNode::signedDistanceFunction because it returns the
  // closest object and not the object with the smallest value function.
  //
  // Fortunately, when I wrote the LinearNode accelerator I wrote it such that we can determine
  // how to update the "shortest" distance using externally supplied criteria.
  // So, we just update this as f = min(f1,f2,f3) etc, and prune nodes accordingly.
  // The criteria for that are below...

That is, it relies on pruning from the BVH functionality for finding the signed distance to the closest object.