Blender  V3.3
BLI_mesh_intersect.hh
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 
3 #pragma once
4 
12 #ifdef WITH_GMP
13 
14 # include <iostream>
15 
16 # include "BLI_array.hh"
17 # include "BLI_index_range.hh"
18 # include "BLI_map.hh"
19 # include "BLI_math_mpq.hh"
20 # include "BLI_math_vec_mpq_types.hh"
21 # include "BLI_math_vec_types.hh"
22 # include "BLI_span.hh"
23 # include "BLI_utility_mixins.hh"
24 # include "BLI_vector.hh"
25 
26 namespace blender::meshintersect {
27 
28 constexpr int NO_INDEX = -1;
29 
45 struct Vert {
46  mpq3 co_exact;
47  double3 co;
48  int id = NO_INDEX;
49  int orig = NO_INDEX;
50 
51  Vert() = default;
52  Vert(const mpq3 &mco, const double3 &dco, int id, int orig);
53  ~Vert() = default;
54 
56  bool operator==(const Vert &other) const;
57 
59  uint64_t hash() const;
60 };
61 
62 std::ostream &operator<<(std::ostream &os, const Vert *v);
63 
71 struct Plane {
72  mpq3 norm_exact;
73  mpq_class d_exact;
74  double3 norm;
75  double d;
76 
77  Plane() = default;
78  Plane(const mpq3 &norm_exact, const mpq_class &d_exact);
79  Plane(const double3 &norm, double d);
80 
82  bool operator==(const Plane &other) const;
83 
85  uint64_t hash() const;
86 
87  void make_canonical();
91  bool exact_populated() const;
92  void populate_exact();
93 };
94 
95 std::ostream &operator<<(std::ostream &os, const Plane *plane);
96 
113 struct Face : NonCopyable {
114  Array<const Vert *> vert;
115  Array<int> edge_orig;
116  Array<bool> is_intersect;
117  Plane *plane = nullptr;
118  int id = NO_INDEX;
119  int orig = NO_INDEX;
120 
121  using FacePos = int;
122 
123  Face() = default;
124  Face(Span<const Vert *> verts, int id, int orig, Span<int> edge_origs, Span<bool> is_intersect);
125  Face(Span<const Vert *> verts, int id, int orig);
126  ~Face();
127 
128  bool is_tri() const
129  {
130  return vert.size() == 3;
131  }
132 
133  /* Test equality of verts, in same positions. */
134  bool operator==(const Face &other) const;
135 
136  /* Test equality faces allowing cyclic shifts. */
137  bool cyclic_equal(const Face &other) const;
138 
139  FacePos next_pos(FacePos p) const
140  {
141  return (p + 1) % vert.size();
142  }
143 
144  FacePos prev_pos(FacePos p) const
145  {
146  return (p + vert.size() - 1) % vert.size();
147  }
148 
149  const Vert *const &operator[](int index) const
150  {
151  return vert[index];
152  }
153 
154  int size() const
155  {
156  return vert.size();
157  }
158 
159  const Vert *const *begin() const
160  {
161  return vert.begin();
162  }
163 
164  const Vert *const *end() const
165  {
166  return vert.end();
167  }
168 
169  IndexRange index_range() const
170  {
171  return IndexRange(vert.size());
172  }
173 
174  void populate_plane(bool need_exact);
175 
176  bool plane_populated() const
177  {
178  return plane != nullptr;
179  }
180 };
181 
182 std::ostream &operator<<(std::ostream &os, const Face *f);
183 
191 class IMeshArena : NonCopyable, NonMovable {
192  class IMeshArenaImpl;
193  std::unique_ptr<IMeshArenaImpl> pimpl_;
194 
195  public:
196  IMeshArena();
197  ~IMeshArena();
198 
203  void reserve(int vert_num_hint, int face_num_hint);
204 
205  int tot_allocated_verts() const;
206  int tot_allocated_faces() const;
207 
214  const Vert *add_or_find_vert(const mpq3 &co, int orig);
215  const Vert *add_or_find_vert(const double3 &co, int orig);
216  const Vert *add_or_find_vert(Vert *vert);
217 
218  Face *add_face(Span<const Vert *> verts,
219  int orig,
220  Span<int> edge_origs,
221  Span<bool> is_intersect);
222  Face *add_face(Span<const Vert *> verts, int orig, Span<int> edge_origs);
223  Face *add_face(Span<const Vert *> verts, int orig);
224 
226  const Vert *find_vert(const mpq3 &co) const;
227  const Face *find_face(Span<const Vert *> verts) const;
228 };
229 
241 class IMesh {
242  Array<Face *> face_; /* Not `const` so can lazily populate planes. */
243  Array<const Vert *> vert_; /* Only valid if vert_populated_. */
244  Map<const Vert *, int> vert_to_index_; /* Only valid if vert_populated_. */
245  bool vert_populated_ = false;
246 
247  public:
248  IMesh() = default;
249  IMesh(Span<Face *> faces) : face_(faces)
250  {
251  }
252 
253  void set_faces(Span<Face *> faces);
254  Face *face(int index) const
255  {
256  return face_[index];
257  }
258 
259  int face_size() const
260  {
261  return face_.size();
262  }
263 
264  int vert_size() const
265  {
266  return vert_.size();
267  }
268 
269  bool has_verts() const
270  {
271  return vert_populated_;
272  }
273 
274  void set_dirty_verts()
275  {
276  vert_populated_ = false;
277  vert_to_index_.clear();
278  vert_ = Array<const Vert *>();
279  }
280 
281  /* Pass `max_verts` if there is a good bound estimate on the maximum number of verts. */
282  void populate_vert();
283  void populate_vert(int max_verts);
284 
285  const Vert *vert(int index) const
286  {
287  BLI_assert(vert_populated_);
288  return vert_[index];
289  }
290 
292  int lookup_vert(const Vert *v) const;
293 
294  IndexRange vert_index_range() const
295  {
296  BLI_assert(vert_populated_);
297  return IndexRange(vert_.size());
298  }
299 
300  IndexRange face_index_range() const
301  {
302  return IndexRange(face_.size());
303  }
304 
305  Span<const Vert *> vertices() const
306  {
307  BLI_assert(vert_populated_);
308  return Span<const Vert *>(vert_);
309  }
310 
311  Span<Face *> faces() const
312  {
313  return Span<Face *>(face_);
314  }
315 
325  bool erase_face_positions(int f_index, Span<bool> face_pos_erase, IMeshArena *arena);
326 
327  void remove_null_faces();
328 };
329 
330 std::ostream &operator<<(std::ostream &os, const IMesh &mesh);
331 
336 struct BoundingBox {
337  float3 min{FLT_MAX, FLT_MAX, FLT_MAX};
338  float3 max{-FLT_MAX, -FLT_MAX, -FLT_MAX};
339 
340  BoundingBox() = default;
341  BoundingBox(const float3 &min, const float3 &max) : min(min), max(max)
342  {
343  }
344 
345  void combine(const float3 &p)
346  {
347  min.x = min_ff(min.x, p.x);
348  min.y = min_ff(min.y, p.y);
349  min.z = min_ff(min.z, p.z);
350  max.x = max_ff(max.x, p.x);
351  max.y = max_ff(max.y, p.y);
352  max.z = max_ff(max.z, p.z);
353  }
354 
355  void combine(const double3 &p)
356  {
357  min.x = min_ff(min.x, static_cast<float>(p.x));
358  min.y = min_ff(min.y, static_cast<float>(p.y));
359  min.z = min_ff(min.z, static_cast<float>(p.z));
360  max.x = max_ff(max.x, static_cast<float>(p.x));
361  max.y = max_ff(max.y, static_cast<float>(p.y));
362  max.z = max_ff(max.z, static_cast<float>(p.z));
363  }
364 
365  void combine(const BoundingBox &bb)
366  {
367  min.x = min_ff(min.x, bb.min.x);
368  min.y = min_ff(min.y, bb.min.y);
369  min.z = min_ff(min.z, bb.min.z);
370  max.x = max_ff(max.x, bb.max.x);
371  max.y = max_ff(max.y, bb.max.y);
372  max.z = max_ff(max.z, bb.max.z);
373  }
374 
375  void expand(float pad)
376  {
377  min.x -= pad;
378  min.y -= pad;
379  min.z -= pad;
380  max.x += pad;
381  max.y += pad;
382  max.z += pad;
383  }
384 };
385 
391 bool bbs_might_intersect(const BoundingBox &bb_a, const BoundingBox &bb_b);
392 
405 IMesh trimesh_self_intersect(const IMesh &tm_in, IMeshArena *arena);
406 
407 IMesh trimesh_nary_intersect(const IMesh &tm_in,
408  int nshapes,
409  std::function<int(int)> shape_fn,
410  bool use_self,
411  IMeshArena *arena);
412 
419 IMesh triangulate_polymesh(IMesh &imesh, IMeshArena *arena);
420 
424 void write_obj_mesh(IMesh &m, const std::string &objname);
425 
426 } /* namespace blender::meshintersect */
427 
428 #endif /* WITH_GMP */
#define BLI_assert(a)
Definition: BLI_assert.h:46
MINLINE float max_ff(float a, float b)
MINLINE float min_ff(float a, float b)
int pad[32 - sizeof(int)]
ATTR_WARN_UNUSED_RESULT const BMVert * v
static DBVT_INLINE btScalar size(const btDbvtVolume &a)
Definition: btDbvt.cpp:52
SIMD_FORCE_INLINE btVector3 & operator[](int i)
Get a mutable reference to a row of the matrix as a vector.
Definition: btMatrix3x3.h:157
SIMD_FORCE_INLINE btScalar norm() const
Return the norm (length) of the vector.
Definition: btVector3.h:263
struct Vert Vert
static float verts[][3]
static char faces[256]
struct Face Face
std::ostream & operator<<(std::ostream &stream, const FatCo< T > &co)
Definition: delaunay_2d.cc:177
constexpr bool operator==(StringRef a, StringRef b)
vec_base< double, 3 > double3
#define hash
Definition: noise.c:153
#define min(a, b)
Definition: sort.c:35
unsigned __int64 uint64_t
Definition: stdint.h:90
float z
float y
float x
float max