Blender V5.3
BLI_mesh_intersect.hh
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2023 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
5#pragma once
6
13
14#ifdef WITH_GMP
15
16# include <iosfwd>
17
18# include "BLI_array.hh"
19# include "BLI_function_ref.hh"
20# include "BLI_index_range.hh"
21# include "BLI_map.hh"
22# include "BLI_math_mpq.hh"
25# include "BLI_span.hh"
26# include "BLI_utility_mixins.hh"
27
28namespace blender::meshintersect {
29
30constexpr int NO_INDEX = -1;
31
47struct Vert {
48 mpq3 co_exact;
49 double3 co;
50 int id = NO_INDEX;
51 int orig = NO_INDEX;
52
53 Vert() = default;
54 Vert(const mpq3 &mco, const double3 &dco, int id, int orig);
55 ~Vert() = default;
56
58 bool operator==(const Vert &other) const;
59
61 uint64_t hash() const;
62};
63
64std::ostream &operator<<(std::ostream &os, const Vert *v);
65
73struct Plane {
74 mpq3 norm_exact;
75 mpq_class d_exact;
77 double d;
78
79 Plane() = default;
80 Plane(const mpq3 &norm_exact, const mpq_class &d_exact);
81 Plane(const double3 &norm, double d);
82
84 bool operator==(const Plane &other) const;
85
87 uint64_t hash() const;
88
89 void make_canonical();
93 bool exact_populated() const;
94 void populate_exact();
95};
96
97std::ostream &operator<<(std::ostream &os, const Plane *plane);
98
115struct Face : NonCopyable {
116 Array<const Vert *> vert;
117 Array<int> edge_orig;
118 Array<bool> is_intersect;
119 Plane *plane = nullptr;
120 int id = NO_INDEX;
121 int orig = NO_INDEX;
122
123 using FacePos = int;
124
125 Face() = default;
126 Face(Span<const Vert *> verts, int id, int orig, Span<int> edge_origs, Span<bool> is_intersect);
127 Face(Span<const Vert *> verts, int id, int orig);
128 ~Face();
129
130 bool is_tri() const
131 {
132 return vert.size() == 3;
133 }
134
135 /* Test equality of verts, in same positions. */
136 bool operator==(const Face &other) const;
137
138 /* Test equality faces allowing cyclic shifts. */
139 bool cyclic_equal(const Face &other) const;
140
141 FacePos next_pos(FacePos p) const
142 {
143 return (p + 1) % vert.size();
144 }
145
146 FacePos prev_pos(FacePos p) const
147 {
148 return (p + vert.size() - 1) % vert.size();
149 }
150
151 const Vert *const &operator[](int index) const
152 {
153 return vert[index];
154 }
155
156 int size() const
157 {
158 return vert.size();
159 }
160
161 const Vert *const *begin() const
162 {
163 return vert.begin();
164 }
165
166 const Vert *const *end() const
167 {
168 return vert.end();
169 }
170
171 IndexRange index_range() const
172 {
173 return IndexRange(vert.size());
174 }
175
176 void populate_plane(bool need_exact);
177
178 bool plane_populated() const
179 {
180 return plane != nullptr;
181 }
182};
183
184std::ostream &operator<<(std::ostream &os, const Face *f);
185
193class IMeshArena : NonCopyable, NonMovable {
194 class IMeshArenaImpl;
195 std::unique_ptr<IMeshArenaImpl> pimpl_;
196
197 public:
198 IMeshArena();
199 ~IMeshArena();
200
205 void reserve(int vert_num_hint, int face_num_hint);
206
207 int tot_allocated_verts() const;
208 int tot_allocated_faces() const;
209
216 const Vert *add_or_find_vert(const mpq3 &co, int orig);
217 const Vert *add_or_find_vert(const double3 &co, int orig);
218 const Vert *add_or_find_vert(Vert *vert);
219
220 Face *add_face(Span<const Vert *> verts,
221 int orig,
222 Span<int> edge_origs,
223 Span<bool> is_intersect);
224 Face *add_face(Span<const Vert *> verts, int orig, Span<int> edge_origs);
225 Face *add_face(Span<const Vert *> verts, int orig);
226
228 const Vert *find_vert(const mpq3 &co) const;
229 const Face *find_face(Span<const Vert *> verts) const;
230};
231
242class IMesh {
243 Array<Face *> face_; /* Not `const` so can lazily populate planes. */
244 Array<const Vert *> vert_; /* Only valid if vert_populated_. */
245 Map<const Vert *, int> vert_to_index_; /* Only valid if vert_populated_. */
246 bool vert_populated_ = false;
247
248 public:
249 IMesh() = default;
250 IMesh(Span<Face *> faces) : face_(faces) {}
251
252 void set_faces(Span<Face *> faces);
253 Face *face(int index) const
254 {
255 return face_[index];
256 }
257
258 int face_size() const
259 {
260 return face_.size();
261 }
262
263 int vert_size() const
264 {
265 return vert_.size();
266 }
267
268 bool has_verts() const
269 {
270 return vert_populated_;
271 }
272
273 void set_dirty_verts()
274 {
275 vert_populated_ = false;
276 vert_to_index_.clear();
277 vert_ = Array<const Vert *>();
278 }
279
280 /* Pass `max_verts` if there is a good bound estimate on the maximum number of verts. */
281 void populate_vert();
282 void populate_vert(int max_verts);
283
284 const Vert *vert(int index) const
285 {
286 BLI_assert(vert_populated_);
287 return vert_[index];
288 }
289
291 int lookup_vert(const Vert *v) const
292 {
293 BLI_assert(vert_populated_);
294 return vert_to_index_.lookup_default(v, NO_INDEX);
295 }
296
297 IndexRange vert_index_range() const
298 {
299 BLI_assert(vert_populated_);
300 return IndexRange(vert_.size());
301 }
302
303 IndexRange face_index_range() const
304 {
305 return IndexRange(face_.size());
306 }
307
308 Span<const Vert *> vertices() const
309 {
310 BLI_assert(vert_populated_);
311 return Span<const Vert *>(vert_);
312 }
313
314 Span<Face *> faces() const
315 {
316 return Span<Face *>(face_);
317 }
318
328 bool erase_face_positions(int f_index, Span<bool> face_pos_erase, IMeshArena *arena);
329
330 void remove_null_faces();
331};
332
333std::ostream &operator<<(std::ostream &os, const IMesh &mesh);
334
339struct BoundingBox {
342
343 BoundingBox() = default;
344 BoundingBox(const float3 &min, const float3 &max) : min(min), max(max) {}
345
346 void combine(const float3 &p)
347 {
348 math::min_max(p, this->min, this->max);
349 }
350
351 void combine(const double3 &p)
352 {
353 math::min_max(float3(p), this->min, this->max);
354 }
355
356 void combine(const BoundingBox &bb)
357 {
358 min = math::min(this->min, bb.min);
359 max = math::max(this->max, bb.max);
360 }
361
362 void expand(float pad)
363 {
364 min -= pad;
365 max += pad;
366 }
367};
368
374bool bbs_might_intersect(const BoundingBox &bb_a, const BoundingBox &bb_b);
375
388IMesh trimesh_self_intersect(const IMesh &tm_in, IMeshArena *arena);
389
390IMesh trimesh_nary_intersect(const IMesh &tm_in,
391 int nshapes,
392 FunctionRef<int(int)> shape_fn,
393 bool use_self,
394 IMeshArena *arena);
395
402IMesh triangulate_polymesh(IMesh &imesh, IMeshArena *arena);
403
407void write_obj_mesh(IMesh &m, const std::string &objname);
408
409} // namespace blender::meshintersect
410
411#endif /* WITH_GMP */
int pad[32 - sizeof(int)]
#define BLI_assert(a)
unsigned long long int uint64_t
btScalar max
SIMD_FORCE_INLINE btVector3 & operator[](int i)
Get a mutable reference to a row of the matrix as a vector.
SIMD_FORCE_INLINE btScalar norm() const
Return the norm (length) of the vector.
Definition btVector3.h:263
constexpr Span()=default
#define FLT_MAX
#define index(i)
VecBase< float, 3 > float3
ccl_device_inline bool operator==(const float2 a, const float2 b)
int size(const AssetLibraryReference *library_reference)
std::ostream & operator<<(std::ostream &stream, const FatCo< T > &co)
ATTR_WARN_UNUSED_RESULT const BMVert * v
VecBase< double, 3 > double3
iter begin(iter)
void vert(const int vert_id, float4 &position)
#define hash
Definition noise_c.cc:156
#define min(a, b)
Definition sort.cc:38