BLI_mesh_intersect.hh

Go to the documentation of this file.

/* SPDX-FileCopyrightText: 2023 Blender Authors
 *
 * SPDX-License-Identifier: GPL-2.0-or-later */
 
#pragma once

 
#ifdef WITH_GMP
 
#  include <iosfwd>
 
#  include "BLI_array.hh"
#  include "BLI_function_ref.hh"
#  include "BLI_index_range.hh"
#  include "BLI_map.hh"
#  include "BLI_math_mpq.hh"
#  include "BLI_math_vector_mpq_types.hh"
#  include "BLI_math_vector_types.hh"
#  include "BLI_span.hh"
#  include "BLI_utility_mixins.hh"
 
namespace blender::meshintersect {
 
constexpr int NO_INDEX = -1;

struct Vert {
  mpq3 co_exact;
  double3 co;
  int id = NO_INDEX;
  int orig = NO_INDEX;
 
  Vert() = default;
  Vert(const mpq3 &mco, const double3 &dco, int id, int orig);
  ~Vert() = default;

  bool operator==(const Vert &other) const;

  uint64_t hash() const;
};
 
std::ostream &operator<<(std::ostream &os, const Vert *v);

struct Plane {
  mpq3 norm_exact;
  mpq_class d_exact;
  double3 norm;
  double d;
 
  Plane() = default;
  Plane(const mpq3 &norm_exact, const mpq_class &d_exact);
  Plane(const double3 &norm, double d);

  bool operator==(const Plane &other) const;

  uint64_t hash() const;
 
  void make_canonical();
  bool exact_populated() const;
  void populate_exact();
};
 
std::ostream &operator<<(std::ostream &os, const Plane *plane);

struct Face : NonCopyable {
  Array<const Vert *> vert;
  Array<int> edge_orig;
  Array<bool> is_intersect;
  Plane *plane = nullptr;
  int id = NO_INDEX;
  int orig = NO_INDEX;
 
  using FacePos = int;
 
  Face() = default;
  Face(Span<const Vert *> verts, int id, int orig, Span<int> edge_origs, Span<bool> is_intersect);
  Face(Span<const Vert *> verts, int id, int orig);
  ~Face();
 
  bool is_tri() const
  {
    return vert.size() == 3;
  }
 
  /* Test equality of verts, in same positions. */
  bool operator==(const Face &other) const;
 
  /* Test equality faces allowing cyclic shifts. */
  bool cyclic_equal(const Face &other) const;
 
  FacePos next_pos(FacePos p) const
  {
    return (p + 1) % vert.size();
  }
 
  FacePos prev_pos(FacePos p) const
  {
    return (p + vert.size() - 1) % vert.size();
  }
 
  const Vert *const &operator[](int index) const
  {
    return vert[index];
  }
 
  int size() const
  {
    return vert.size();
  }
 
  const Vert *const *begin() const
  {
    return vert.begin();
  }
 
  const Vert *const *end() const
  {
    return vert.end();
  }
 
  IndexRange index_range() const
  {
    return IndexRange(vert.size());
  }
 
  void populate_plane(bool need_exact);
 
  bool plane_populated() const
  {
    return plane != nullptr;
  }
};
 
std::ostream &operator<<(std::ostream &os, const Face *f);

class IMeshArena : NonCopyable, NonMovable {
  class IMeshArenaImpl;
  std::unique_ptr<IMeshArenaImpl> pimpl_;
 
 public:
  IMeshArena();
  ~IMeshArena();

  void reserve(int vert_num_hint, int face_num_hint);
 
  int tot_allocated_verts() const;
  int tot_allocated_faces() const;

  const Vert *add_or_find_vert(const mpq3 &co, int orig);
  const Vert *add_or_find_vert(const double3 &co, int orig);
  const Vert *add_or_find_vert(Vert *vert);
 
  Face *add_face(Span<const Vert *> verts,
                 int orig,
                 Span<int> edge_origs,
                 Span<bool> is_intersect);
  Face *add_face(Span<const Vert *> verts, int orig, Span<int> edge_origs);
  Face *add_face(Span<const Vert *> verts, int orig);

  const Vert *find_vert(const mpq3 &co) const;
  const Face *find_face(Span<const Vert *> verts) const;
};

class IMesh {
  Array<Face *> face_;                   /* Not `const` so can lazily populate planes. */
  Array<const Vert *> vert_;             /* Only valid if vert_populated_. */
  Map<const Vert *, int> vert_to_index_; /* Only valid if vert_populated_. */
  bool vert_populated_ = false;
 
 public:
  IMesh() = default;
  IMesh(Span<Face *> faces) : face_(faces) {}
 
  void set_faces(Span<Face *> faces);
  Face *face(int index) const
  {
    return face_[index];
  }
 
  int face_size() const
  {
    return face_.size();
  }
 
  int vert_size() const
  {
    return vert_.size();
  }
 
  bool has_verts() const
  {
    return vert_populated_;
  }
 
  void set_dirty_verts()
  {
    vert_populated_ = false;
    vert_to_index_.clear();
    vert_ = Array<const Vert *>();
  }
 
  /* Pass `max_verts` if there is a good bound estimate on the maximum number of verts. */
  void populate_vert();
  void populate_vert(int max_verts);
 
  const Vert *vert(int index) const
  {
    BLI_assert(vert_populated_);
    return vert_[index];
  }

  int lookup_vert(const Vert *v) const;
 
  IndexRange vert_index_range() const
  {
    BLI_assert(vert_populated_);
    return IndexRange(vert_.size());
  }
 
  IndexRange face_index_range() const
  {
    return IndexRange(face_.size());
  }
 
  Span<const Vert *> vertices() const
  {
    BLI_assert(vert_populated_);
    return Span<const Vert *>(vert_);
  }
 
  Span<Face *> faces() const
  {
    return Span<Face *>(face_);
  }

  bool erase_face_positions(int f_index, Span<bool> face_pos_erase, IMeshArena *arena);
 
  void remove_null_faces();
};
 
std::ostream &operator<<(std::ostream &os, const IMesh &mesh);

struct BoundingBox {
  float3 min{FLT_MAX, FLT_MAX, FLT_MAX};
  float3 max{-FLT_MAX, -FLT_MAX, -FLT_MAX};
 
  BoundingBox() = default;
  BoundingBox(const float3 &min, const float3 &max) : min(min), max(max) {}
 
  void combine(const float3 &p)
  {
    math::min_max(p, this->min, this->max);
  }
 
  void combine(const double3 &p)
  {
    math::min_max(float3(p), this->min, this->max);
  }
 
  void combine(const BoundingBox &bb)
  {
    min = math::min(this->min, bb.min);
    max = math::max(this->max, bb.max);
  }
 
  void expand(float pad)
  {
    min -= pad;
    max += pad;
  }
};

bool bbs_might_intersect(const BoundingBox &bb_a, const BoundingBox &bb_b);

IMesh trimesh_self_intersect(const IMesh &tm_in, IMeshArena *arena);
 
IMesh trimesh_nary_intersect(const IMesh &tm_in,
                             int nshapes,
                             FunctionRef<int(int)> shape_fn,
                             bool use_self,
                             IMeshArena *arena);

IMesh triangulate_polymesh(IMesh &imesh, IMeshArena *arena);

void write_obj_mesh(IMesh &m, const std::string &objname);
 
} /* namespace blender::meshintersect */
 
#endif /* WITH_GMP */