Welcome to mirror list, hosted at ThFree Co, Russian Federation.

git.blender.org/blender.git - Unnamed repository; edit this file 'description' to name the repository.
summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorCampbell Barton <ideasman42@gmail.com>2020-08-27 11:18:47 +0300
committerCampbell Barton <ideasman42@gmail.com>2020-08-27 11:18:47 +0300
commite0cb02587012b4b2f4b18363dc7d0a7da2c02093 (patch)
treed574c9585e2010d10d074b6da88ab50191b36bb2 /source/blender/blenlib
parent94884777b20dc612863690171b958eef41a4b6fd (diff)
Cleanup: mostly comments, use doxy syntax & typos
- Use doxy syntax for functions. - Use `pragma once` for header guard.
Diffstat (limited to 'source/blender/blenlib')
-rw-r--r--source/blender/blenlib/BLI_delaunay_2d.h11
-rw-r--r--source/blender/blenlib/BLI_double2.hh4
-rw-r--r--source/blender/blenlib/BLI_double3.hh9
-rw-r--r--source/blender/blenlib/BLI_math_mpq.hh4
-rw-r--r--source/blender/blenlib/BLI_mesh_boolean.hh11
-rw-r--r--source/blender/blenlib/BLI_mesh_intersect.hh75
-rw-r--r--source/blender/blenlib/BLI_mpq2.hh9
-rw-r--r--source/blender/blenlib/BLI_mpq3.hh6
-rw-r--r--source/blender/blenlib/intern/delaunay_2d.cc283
-rw-r--r--source/blender/blenlib/intern/math_vec.cc180
-rw-r--r--source/blender/blenlib/intern/math_vector.c2
-rw-r--r--source/blender/blenlib/intern/mesh_boolean.cc333
-rw-r--r--source/blender/blenlib/intern/mesh_intersect.cc352
-rw-r--r--source/blender/blenlib/tests/BLI_mesh_intersect_test.cc9
14 files changed, 706 insertions, 582 deletions
diff --git a/source/blender/blenlib/BLI_delaunay_2d.h b/source/blender/blenlib/BLI_delaunay_2d.h
index cd5838d9b29..7027477ac7f 100644
--- a/source/blender/blenlib/BLI_delaunay_2d.h
+++ b/source/blender/blenlib/BLI_delaunay_2d.h
@@ -239,9 +239,10 @@ template<typename Arith_t> class CDT_result {
Array<vec2<Arith_t>> vert;
Array<std::pair<int, int>> edge;
Array<Vector<int>> face;
- /* For each output vert, which input verts correspond to it? */
+ /** For each output vert, which input verts correspond to it? */
Array<Vector<int>> vert_orig;
- /* For each output edge, which input edges does it overlap?
+ /**
+ * For each output edge, which input edges does it overlap?
* The input edge ids are encoded as follows:
* if the value is less than face_edge_offset, then it is
* an index into the input edge[] array.
@@ -250,9 +251,9 @@ template<typename Arith_t> class CDT_result {
* and "b" will be a position within that face.
*/
Array<Vector<int>> edge_orig;
- /* For each output face, which original faces does it overlap? */
+ /** For each output face, which original faces does it overlap? */
Array<Vector<int>> face_orig;
- /* Used to encode edge_orig (see above). */
+ /** Used to encode edge_orig (see above). */
int face_edge_offset;
};
@@ -265,4 +266,4 @@ CDT_result<mpq_class> delaunay_2d_calc(const CDT_input<mpq_class> &input,
} /* namespace blender::meshintersect */
-#endif /* __cplusplus */ \ No newline at end of file
+#endif /* __cplusplus */
diff --git a/source/blender/blenlib/BLI_double2.hh b/source/blender/blenlib/BLI_double2.hh
index 654207d98f1..37584729498 100644
--- a/source/blender/blenlib/BLI_double2.hh
+++ b/source/blender/blenlib/BLI_double2.hh
@@ -16,6 +16,10 @@
#pragma once
+/** \file
+ * \ingroup bli
+ */
+
#include "BLI_double3.hh"
namespace blender {
diff --git a/source/blender/blenlib/BLI_double3.hh b/source/blender/blenlib/BLI_double3.hh
index 4884b8f287c..f783055590a 100644
--- a/source/blender/blenlib/BLI_double3.hh
+++ b/source/blender/blenlib/BLI_double3.hh
@@ -16,6 +16,10 @@
#pragma once
+/** \file
+ * \ingroup bli
+ */
+
#include <iostream>
#include "BLI_math_vector.h"
@@ -237,11 +241,10 @@ struct double3 {
static double3 cross_poly(Span<double3> poly);
- /* orient3d gives the exact result, using multiprecision artihmetic when result
+ /* #orient3d gives the exact result, using multi-precision arithmetic when result
* is close to zero. orient3d_fast just uses double arithmetic, so may be
* wrong if the answer is very close to zero.
- * Similarly, for insphere and insphere_fast.
- */
+ * Similarly, for #insphere and #insphere_fast. */
static int orient3d(const double3 &a, const double3 &b, const double3 &c, const double3 &d);
static int orient3d_fast(const double3 &a, const double3 &b, const double3 &c, const double3 &d);
diff --git a/source/blender/blenlib/BLI_math_mpq.hh b/source/blender/blenlib/BLI_math_mpq.hh
index 2ed0c9549c8..dd973bf9f64 100644
--- a/source/blender/blenlib/BLI_math_mpq.hh
+++ b/source/blender/blenlib/BLI_math_mpq.hh
@@ -16,6 +16,10 @@
#pragma once
+/** \file
+ * \ingroup bli
+ */
+
#ifdef WITH_GMP
/* This file uses an external file header to define the multiprecision
diff --git a/source/blender/blenlib/BLI_mesh_boolean.hh b/source/blender/blenlib/BLI_mesh_boolean.hh
index 2b5afb2bffc..693639f20f2 100644
--- a/source/blender/blenlib/BLI_mesh_boolean.hh
+++ b/source/blender/blenlib/BLI_mesh_boolean.hh
@@ -28,17 +28,19 @@
namespace blender::meshintersect {
-/* Enum values after BOOLEAN_NONE need to match BMESH_ISECT_BOOLEAN_... values in
+/**
+ * Enum values after BOOLEAN_NONE need to match BMESH_ISECT_BOOLEAN_... values in
* editmesh_intersect.c. */
enum class BoolOpType {
None = -1,
- /* Aligned with BooleanModifierOp. */
+ /* Aligned with #BooleanModifierOp. */
Intersect = 0,
Union = 1,
Difference = 2,
};
-/* Do the boolean operation op on the mesh pm_in.
+/**
+ * Do the boolean operation op on the mesh pm_in.
* The boolean operation has nshapes input shapes. Each is a disjoint subset of the input mesh.
* The shape_fn argument, when applied to an input face argument, says which shape it is in
* (should be a value from -1 to nshapes - 1: if -1, it is not part of any shape).
@@ -60,7 +62,8 @@ IMesh boolean_mesh(IMesh &imesh,
IMesh *pm_triangulated,
IMeshArena *arena);
-/* This is like boolean, but operates on IMesh's whose faces are all triangles.
+/**
+ * This is like boolean, but operates on IMesh's whose faces are all triangles.
* It is exposed mainly for unit testing, at the moment: boolean_mesh() uses
* it to do most of its work.
*/
diff --git a/source/blender/blenlib/BLI_mesh_intersect.hh b/source/blender/blenlib/BLI_mesh_intersect.hh
index 6e2a9a6424b..877363b998a 100644
--- a/source/blender/blenlib/BLI_mesh_intersect.hh
+++ b/source/blender/blenlib/BLI_mesh_intersect.hh
@@ -41,7 +41,8 @@ namespace blender::meshintersect {
constexpr int NO_INDEX = -1;
-/* Vertex coordinates are stored both as double3 and mpq3, which should agree.
+/**
+ * Vertex coordinates are stored both as #double3 and #mpq3, which should agree.
* Most calculations are done in exact arithmetic, using the mpq3 version,
* but some predicates can be sped up by operating on doubles and using error analysis
* to find the cases where that is good enough.
@@ -49,8 +50,8 @@ constexpr int NO_INDEX = -1;
* is useful for making algorithms that don't depend on pointers.
* Also, they are easier to read while debugging.
* They also carry an orig index, which can be used to tie them back to
- * vertices that tha caller may have in a different way (e.g., BMVerts).
- * An orig index can be NO_INDEX, indicating the Vert was created by
+ * vertices that the caller may have in a different way (e.g., #BMVert).
+ * An orig index can be #NO_INDEX, indicating the Vert was created by
* the algorithm and doesn't match an original Vert.
* Vertices can be reliably compared for equality,
* and hashed (on their co_exact field).
@@ -65,20 +66,21 @@ struct Vert {
Vert(const mpq3 &mco, const double3 &dco, int id, int orig);
~Vert() = default;
- /* Test equality on the co_exact field. */
+ /** Test equality on the co_exact field. */
bool operator==(const Vert &other) const;
- /* Hash on the co_exact field. */
+ /** Hash on the co_exact field. */
uint64_t hash() const;
};
std::ostream &operator<<(std::ostream &os, const Vert *v);
-/* A Plane whose equation is dot(norm, p) + d = 0.
+/**
+ * A Plane whose equation is `dot(norm, p) + d = 0`.
* The norm and d fields are always present, but the norm_exact
* and d_exact fields may be lazily populated. Since we don't
* store degenerate planes, we can tell if a the exact versions
- * are not populated yet by having norm_exact == 0.
+ * are not populated yet by having `norm_exact == 0`.
*/
struct Plane {
mpq3 norm_exact;
@@ -103,9 +105,10 @@ struct Plane {
std::ostream &operator<<(std::ostream &os, const Plane *plane);
-/* A Face has a sequence of Verts that for a CCW ordering around them.
+/**
+ * A #Face has a sequence of Verts that for a CCW ordering around them.
* Faces carry an index, created at allocation time, useful for making
- * pointer-indenpendent algorithms, and for debugging.
+ * pointer-independent algorithms, and for debugging.
* They also carry an original index, meaningful to the caller.
* And they carry original edge indices too: each is a number meaningful
* to the caller for the edge starting from the corresponding face position.
@@ -115,7 +118,7 @@ std::ostream &operator<<(std::ostream &os, const Plane *plane);
* for each edge whether or not it is the result of intersecting
* with another face in the intersect algorithm.
* Since the intersect algorithm needs the plane for each face,
- * a Face also stores the Plane of the face, but this is only
+ * a #Face also stores the Plane of the face, but this is only
* populate later because not all faces will be intersected.
*/
struct Face : NonCopyable {
@@ -189,11 +192,12 @@ struct Face : NonCopyable {
std::ostream &operator<<(std::ostream &os, const Face *f);
-/* IMeshArena is the owner of the Vert and Face resources used
- * during a run of one of the meshintersect main functions.
+/**
+ * #IMeshArena is the owner of the Vert and Face resources used
+ * during a run of one of the mesh-intersect main functions.
* It also keeps has a hash table of all Verts created so that it can
* ensure that only one instance of a Vert with a given co_exact will
- * exist. I.e., it dedups the vertices.
+ * exist. I.e., it de-duplicates the vertices.
*/
class IMeshArena : NonCopyable, NonMovable {
class IMeshArenaImpl;
@@ -203,7 +207,8 @@ class IMeshArena : NonCopyable, NonMovable {
IMeshArena();
~IMeshArena();
- /* Provide hints to number of expected Verts and Faces expected
+ /**
+ * Provide hints to number of expected Verts and Faces expected
* to be allocated.
*/
void reserve(int vert_num_hint, int face_num_hint);
@@ -211,7 +216,8 @@ class IMeshArena : NonCopyable, NonMovable {
int tot_allocated_verts() const;
int tot_allocated_faces() const;
- /* These add routines find and return an existing Vert with the same
+ /**
+ * These add routines find and return an existing Vert with the same
* co_exact, if it exists (the orig argument is ignored in this case),
* or else allocates and returns a new one. The index field of a
* newly allocated Vert will be the index in creation order.
@@ -226,23 +232,24 @@ class IMeshArena : NonCopyable, NonMovable {
Face *add_face(Span<const Vert *> verts, int orig, Span<int> edge_origs);
Face *add_face(Span<const Vert *> verts, int orig);
- /* The following return nullptr if not found. */
+ /** The following return #nullptr if not found. */
const Vert *find_vert(const mpq3 &co) const;
const Face *find_face(Span<const Vert *> verts) const;
};
-/* A blender::meshintersect::IMesh is a self-contained mesh structure
- * that can be used in Blenlib without depending on the rest of Blender.
- * The Vert and Face resources used in the IMesh should be owned by
- * some IMeshArena.
- * The Verts used by a IMesh can be recovered from the Faces, so
- * are usually not stored, but on request, the IMesh can populate
+/**
+ * A #blender::meshintersect::IMesh is a self-contained mesh structure
+ * that can be used in `blenlib` without depending on the rest of Blender.
+ * The Vert and #Face resources used in the #IMesh should be owned by
+ * some #IMeshArena.
+ * The Verts used by a #IMesh can be recovered from the Faces, so
+ * are usually not stored, but on request, the #IMesh can populate
* internal structures for indexing exactly the set of needed Verts,
* and also going from a Vert pointer to the index in that system.
*/
class IMesh {
- Array<Face *> face_; /* Not const so can lazily populate planes. */
+ 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;
@@ -281,9 +288,7 @@ class IMesh {
vert_ = Array<const Vert *>();
}
- /* Use the second of these if there is a good bound
- * estimate on the maximum number of verts.
- */
+ /* 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);
@@ -293,7 +298,7 @@ class IMesh {
return vert_[index];
}
- /* Returns index in vert_ where v is, or NO_INDEX. */
+ /** Returns index in vert_ where v is, or #NO_INDEX. */
int lookup_vert(const Vert *v) const;
IndexRange vert_index_range() const
@@ -318,7 +323,8 @@ class IMesh {
return Span<Face *>(face_);
}
- /* Replace face at given index with one that elides the
+ /**
+ * Replace face at given index with one that elides the
* vertices at the positions in face_pos_erase that are true.
* Use arena to allocate the new face in.
*/
@@ -327,13 +333,14 @@ class IMesh {
std::ostream &operator<<(std::ostream &os, const IMesh &mesh);
-/* The output will have dup vertices merged and degenerate triangles ignored.
- * If the input has overlapping coplanar triangles, then there will be
+/**
+ * The output will have duplicate vertices merged and degenerate triangles ignored.
+ * If the input has overlapping co-planar triangles, then there will be
* as many duplicates as there are overlaps in each overlapping triangular region.
- * The orig field of each IndexedTriangle will give the orig index in the input IMesh
+ * The orig field of each #IndexedTriangle will give the orig index in the input #IMesh
* that the output triangle was a part of (input can have -1 for that field and then
- * the index in tri[] will be used as the original index).
- * The orig structure of the output IMesh gives the originals for vertices and edges.
+ * the index in `tri[]` will be used as the original index).
+ * The orig structure of the output #IMesh gives the originals for vertices and edges.
* Note: if the input tm_in has a non-empty orig structure, then it is ignored.
*/
IMesh trimesh_self_intersect(const IMesh &tm_in, IMeshArena *arena);
@@ -344,7 +351,7 @@ IMesh trimesh_nary_intersect(const IMesh &tm_in,
bool use_self,
IMeshArena *arena);
-/* This has the side effect of populating verts in the IMesh. */
+/** This has the side effect of populating verts in the #IMesh. */
void write_obj_mesh(IMesh &m, const std::string &objname);
} /* namespace blender::meshintersect */
diff --git a/source/blender/blenlib/BLI_mpq2.hh b/source/blender/blenlib/BLI_mpq2.hh
index 86a7b0ac3a8..c7d8eaeeeb6 100644
--- a/source/blender/blenlib/BLI_mpq2.hh
+++ b/source/blender/blenlib/BLI_mpq2.hh
@@ -16,6 +16,10 @@
#pragma once
+/** \file
+ * \ingroup bli
+ */
+
#ifdef WITH_GMP
# include "BLI_math_mpq.hh"
@@ -76,7 +80,8 @@ struct mpq2 {
return &x;
}
- /* Cannot do this exactly in rational arithmetic!
+ /**
+ * Cannot do this exactly in rational arithmetic!
* Approximate by going in and out of doubles.
*/
mpq_class length() const
@@ -174,7 +179,7 @@ struct mpq2 {
static int incircle(const mpq2 &a, const mpq2 &b, const mpq2 &c, const mpq2 &d);
- /* There is a sensible use for hashing on exact arithmetic types. */
+ /** There is a sensible use for hashing on exact arithmetic types. */
uint64_t hash() const;
};
diff --git a/source/blender/blenlib/BLI_mpq3.hh b/source/blender/blenlib/BLI_mpq3.hh
index a0f1b342d06..fc59448b104 100644
--- a/source/blender/blenlib/BLI_mpq3.hh
+++ b/source/blender/blenlib/BLI_mpq3.hh
@@ -16,6 +16,10 @@
#pragma once
+/** \file
+ * \ingroup bli
+ */
+
#ifdef WITH_GMP
# include <iostream>
@@ -268,7 +272,7 @@ struct mpq3 {
static int orient3d(const mpq3 &a, const mpq3 &b, const mpq3 &c, const mpq3 &d);
- /* There is a sensible use for hashing on exact arithmetic types. */
+ /** There is a sensible use for hashing on exact arithmetic types. */
uint64_t hash() const;
};
diff --git a/source/blender/blenlib/intern/delaunay_2d.cc b/source/blender/blenlib/intern/delaunay_2d.cc
index 18ce976da82..69c453f1dd9 100644
--- a/source/blender/blenlib/intern/delaunay_2d.cc
+++ b/source/blender/blenlib/intern/delaunay_2d.cc
@@ -14,6 +14,10 @@
* Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
*/
+/** \file
+ * \ingroup bli
+ */
+
#include <algorithm>
#include <fstream>
#include <iostream>
@@ -31,8 +35,7 @@
namespace blender::meshintersect {
/* Throughout this file, template argument T will be an
- * arithmetic-like type, like float, double, or mpq_class.
- */
+ * arithmetic-like type, like float, double, or mpq_class. */
template<typename T> T math_abs(const T v)
{
@@ -69,10 +72,11 @@ template<> double math_to_double<double>(const double v)
return v;
}
-/* Define a templated 2D arrangment of vertices, edges, and faces.
- * The SymEdge data structure is the basis for a structure that allows
- * easy traversal to neighboring (by toplogy) geometric elements.
- * Each of CDTVert, CDTEdge, and CDTFace have an input_id linked list,
+/**
+ * Define a templated 2D arrangement of vertices, edges, and faces.
+ * The #SymEdge data structure is the basis for a structure that allows
+ * easy traversal to neighboring (by topology) geometric elements.
+ * Each of #CDTVert, #CDTEdge, and #CDTFace have an input_id linked list,
* whose nodes contain integers that keep track of which input verts, edges,
* and faces, respectively, that the element was derived from.
*
@@ -84,44 +88,46 @@ template<typename Arith_t> struct CDTEdge;
template<typename Arith_t> struct CDTFace;
template<typename Arith_t> struct SymEdge {
- /* Next SymEdge in face, doing CCW traversal of face. */
+ /** Next #SymEdge in face, doing CCW traversal of face. */
SymEdge<Arith_t> *next{nullptr};
- /* Next SymEdge CCW around vert. */
+ /** Next #SymEdge CCW around vert. */
SymEdge<Arith_t> *rot{nullptr};
- /* Vert at origin. */
+ /** Vert at origin. */
CDTVert<Arith_t> *vert{nullptr};
- /* Undirected edge this is for. */
+ /** Un-directed edge this is for. */
CDTEdge<Arith_t> *edge{nullptr};
- /* Face on left side. */
+ /** Face on left side. */
CDTFace<Arith_t> *face{nullptr};
SymEdge() = default;
};
-/* Return other SymEdge for same CDTEdge as se. */
+/**
+ * Return other #SymEdge for same #CDTEdge as \a se.
+ */
template<typename T> inline SymEdge<T> *sym(const SymEdge<T> *se)
{
return se->next->rot;
}
-/* Return SymEdge whose next is se. */
+/** Return #SymEdge whose next is \a se. */
template<typename T> inline SymEdge<T> *prev(const SymEdge<T> *se)
{
return se->rot->next->rot;
}
template<typename Arith_t> struct CDTVert {
- /* Coordinate. */
+ /** Coordinate. */
vec2<Arith_t> co;
- /* Some edge attached to it. */
+ /** Some edge attached to it. */
SymEdge<Arith_t> *symedge{nullptr};
- /* List of corresponding vertex input ids. */
+ /** List of corresponding vertex input ids. */
LinkNode *input_ids{nullptr};
- /* Index into array that CDTArrangement keeps. */
+ /** Index into array that #CDTArrangement keeps. */
int index{-1};
- /* Index of a CDTVert that this has merged to. -1 if no merge. */
+ /** Index of a CDTVert that this has merged to. -1 if no merge. */
int merge_to_index{-1};
- /* Used by algorithms operating on CDT structures. */
+ /** Used by algorithms operating on CDT structures. */
int visit_index{0};
CDTVert() = default;
@@ -129,22 +135,22 @@ template<typename Arith_t> struct CDTVert {
};
template<typename Arith_t> struct CDTEdge {
- /* List of input edge ids that this is part of. */
+ /** List of input edge ids that this is part of. */
LinkNode *input_ids{nullptr};
- /* The directed edges for this edge. */
+ /** The directed edges for this edge. */
SymEdge<Arith_t> symedges[2]{SymEdge<Arith_t>(), SymEdge<Arith_t>()};
CDTEdge() = default;
};
template<typename Arith_t> struct CDTFace {
- /* A symedge in face; only used during output, so only valid then. */
+ /** A symedge in face; only used during output, so only valid then. */
SymEdge<Arith_t> *symedge{nullptr};
- /* List of input face ids that this is part of. */
+ /** List of input face ids that this is part of. */
LinkNode *input_ids{nullptr};
- /* Used by algorithms operating on CDT structures. */
+ /** Used by algorithms operating on CDT structures. */
int visit_index{0};
- /* Marks this face no longer used. */
+ /** Marks this face no longer used. */
bool deleted{false};
CDTFace() = default;
@@ -153,70 +159,81 @@ template<typename Arith_t> struct CDTFace {
template<typename Arith_t> struct CDTArrangement {
/* The arrangement owns the memory pointed to by the pointers in these vectors.
* They are pointers instead of actual structures because these vectors may be resized and
- * other elements refer to the elements by pointer.
- */
+ * other elements refer to the elements by pointer. */
- /* The verts. Some may be merged to others (see their merge_to_index). */
+ /** The verts. Some may be merged to others (see their merge_to_index). */
Vector<CDTVert<Arith_t> *> verts;
- /* The edges. Some may be deleted (SymEdge next and rot pointers are null). */
+ /** The edges. Some may be deleted (SymEdge next and rot pointers are null). */
Vector<CDTEdge<Arith_t> *> edges;
- /* The faces. Some may be deleted (see their delete member). */
+ /** The faces. Some may be deleted (see their delete member). */
Vector<CDTFace<Arith_t> *> faces;
- /* Which CDTFace is the outer face. */
+ /** Which CDTFace is the outer face. */
CDTFace<Arith_t> *outer_face{nullptr};
CDTArrangement() = default;
~CDTArrangement();
- /* Hint to how much space to reserve in the Vectors of the arrangement, based on these counts of
- * input elements. */
+ /** Hint to how much space to reserve in the Vectors of the arrangement,
+ * based on these counts of input elements. */
void reserve(int num_verts, int num_edges, int num_faces);
- /* Add a new vertex to the arrangement, with the given 2D coordinate. It will not be connected to
- * anything yet. */
+ /**
+ * Add a new vertex to the arrangement, with the given 2D coordinate.
+ * It will not be connected to anything yet.
+ */
CDTVert<Arith_t> *add_vert(const vec2<Arith_t> &pt);
- /* Add an edge from v1 to v2. The edge will have a left face and a right face, specified by fleft
- * and fright. The edge will not be connected to anything yet. If the vertices do not yet have a
- * symedge pointer, their pointer is set to the symedge in this new edge.
+ /**
+ * Add an edge from v1 to v2. The edge will have a left face and a right face,
+ * specified by \a fleft and \a fright. The edge will not be connected to anything yet.
+ * If the vertices do not yet have a #SymEdge pointer,
+ * their pointer is set to the #SymEdge in this new edge.
*/
CDTEdge<Arith_t> *add_edge(CDTVert<Arith_t> *v1,
CDTVert<Arith_t> *v2,
CDTFace<Arith_t> *fleft,
CDTFace<Arith_t> *fright);
- /* Add a new face. It is disconnected until an add_edge makes it the left or right face of an
- * edge. */
+ /**
+ * Add a new face. It is disconnected until an add_edge makes it the
+ * left or right face of an edge.
+ */
CDTFace<Arith_t> *add_face();
- /* Make a new edge from v to se->vert, splicing it in. */
+ /** Make a new edge from v to se->vert, splicing it in. */
CDTEdge<Arith_t> *add_vert_to_symedge_edge(CDTVert<Arith_t> *v, SymEdge<Arith_t> *se);
- /* Assuming s1 and s2 are both SymEdges in a face with > 3 sides and one is not the next of the
- * other, Add an edge from s1->v to s2->v, splitting the face in two. The original face will be
- * the one that s1 has as left face, and a new face will be added and made s2 and its
+ /**
+ * Assuming s1 and s2 are both #SymEdge's in a face with > 3 sides and one is not the next of the
+ * other, Add an edge from `s1->v` to `s2->v`, splitting the face in two. The original face will
+ * be the one that s1 has as left face, and a new face will be added and made s2 and its
* next-cycle's left face.
*/
CDTEdge<Arith_t> *add_diagonal(SymEdge<Arith_t> *s1, SymEdge<Arith_t> *s2);
- /* Connect the verts of se1 and se2, assuming that currently those two SymEdges are on teh outer
- * boundary (have face == outer_face) of two components that are isolated from each other.
+ /**
+ * Connect the verts of se1 and se2, assuming that currently those two #SymEdge's are on the
+ * outer boundary (have face == outer_face) of two components that are isolated from each other.
*/
CDTEdge<Arith_t> *connect_separate_parts(SymEdge<Arith_t> *se1, SymEdge<Arith_t> *se2);
- /* Split se at fraction lambda, and return the new CDTEdge that is the new second half.
+ /**
+ * Split se at fraction lambda, and return the new #CDTEdge that is the new second half.
* Copy the edge input_ids into the new one.
*/
CDTEdge<Arith_t> *split_edge(SymEdge<Arith_t> *se, Arith_t lambda);
- /* Delete an edge. The new combined face on either side of the deleted edge will be the one that
+ /**
+ * Delete an edge. The new combined face on either side of the deleted edge will be the one that
* was e's face. There will now be an unused face, which will be marked deleted, and an unused
- * CDTEdge, marked by setting the next and rot pointers of its SymEdges to nullptr.
+ * #CDTEdge, marked by setting the next and rot pointers of its #SymEdge's to #nullptr.
*/
void delete_edge(SymEdge<Arith_t> *se);
- /* If the vertex with index i in the vert array has not been merge, return it.
- * Else return the one that it has merged to. */
+ /**
+ * If the vertex with index i in the vert array has not been merge, return it.
+ * Else return the one that it has merged to.
+ */
CDTVert<Arith_t> *get_vert_resolve_merge(int i)
{
CDTVert<Arith_t> *v = this->verts[i];
@@ -230,15 +247,16 @@ template<typename Arith_t> struct CDTArrangement {
template<typename T> class CDT_state {
public:
CDTArrangement<T> cdt;
- /* How many verts were in input (will be first in vert_array). */
+ /** How many verts were in input (will be first in vert_array). */
int input_vert_tot;
- /* Used for visiting things without having to initialized their visit fields. */
+ /** Used for visiting things without having to initialized their visit fields. */
int visit_count;
- /* Edge ids for face start with this, and each face gets this much index space
+ /**
+ * Edge ids for face start with this, and each face gets this much index space
* to encode positions within the face.
*/
int face_edge_offset;
- /* How close before coords considered equal. */
+ /** How close before coords considered equal. */
T epsilon;
explicit CDT_state(int num_input_verts, int num_input_edges, int num_input_faces, T epsilon);
@@ -388,7 +406,7 @@ template<typename T> void cdt_draw(const std::string &label, const CDTArrangemen
{
static bool append = false; /* Will be set to true after first call. */
-/* Would like to use BKE_tempdir_base() here, but that brings in dependence on kernel library.
+/* Would like to use #BKE_tempdir_base() here, but that brings in dependence on kernel library.
* This is just for developer debugging anyway, and should never be called in production Blender.
*/
# ifdef _WIN32
@@ -501,10 +519,11 @@ template<typename T> void cdt_draw(const std::string &label, const CDTArrangemen
}
#endif
-/*
- * Return true if a -- b -- c are in that order, assuming they are on a straight line according to
- * orient2d and we know the order is either `abc` or `bac`.
- * This means `ab . ac` and `bc . ac` must both be non-negative. */
+/**
+ * Return true if `a -- b -- c` are in that order, assuming they are on a straight line according
+ * to #orient2d and we know the order is either `abc` or `bac`.
+ * This means `ab . ac` and `bc . ac` must both be non-negative.
+ */
template<typename T> bool in_line(const vec2<T> &a, const vec2<T> &b, const vec2<T> &c)
{
vec2<T> ab = b - a;
@@ -661,7 +680,9 @@ SymEdge<T> *find_symedge_between_verts(const CDTVert<T> *v1, const CDTVert<T> *v
return nullptr;
}
-/* Return the SymEdge attached to v that has face f, if it exists, else return nullptr. */
+/**
+ * Return the SymEdge attached to v that has face f, if it exists, else return nullptr.
+ */
template<typename T> SymEdge<T> *find_symedge_with_face(const CDTVert<T> *v, const CDTFace<T> *f)
{
SymEdge<T> *t = v->symedge;
@@ -674,13 +695,17 @@ template<typename T> SymEdge<T> *find_symedge_with_face(const CDTVert<T> *v, con
return nullptr;
}
-/* Is there already an edge between a and b? */
+/**
+ * Is there already an edge between a and b?
+ */
template<typename T> inline bool exists_edge(const CDTVert<T> *v1, const CDTVert<T> *v2)
{
return find_symedge_between_verts(v1, v2) != nullptr;
}
-/* Is the vertex v incident on face f? */
+/**
+ * Is the vertex v incident on face f?
+ */
template<typename T> bool vert_touches_face(const CDTVert<T> *v, const CDTFace<T> *f)
{
SymEdge<T> *se = v->symedge;
@@ -692,13 +717,13 @@ template<typename T> bool vert_touches_face(const CDTVert<T> *v, const CDTFace<T
return false;
}
-/*
- * Assume s1 and s2 are both SymEdges in a face with > 3 sides,
+/**
+ * Assume s1 and s2 are both #SymEdges in a face with > 3 sides,
* and one is not the next of the other.
- * Add an edge from s1->v to s2->v, splitting the face in two.
- * The original face will continue to be associated with the subface
+ * Add an edge from `s1->v` to `s2->v`, splitting the face in two.
+ * The original face will continue to be associated with the sub-face
* that has s1, and a new face will be made for s2's new face.
- * Return the new diagonal's CDTEdge *.
+ * Return the new diagonal's #CDTEdge pointer.
*/
template<typename T> CDTEdge<T> *CDTArrangement<T>::add_diagonal(SymEdge<T> *s1, SymEdge<T> *s2)
{
@@ -744,7 +769,8 @@ CDTEdge<T> *CDTArrangement<T>::add_vert_to_symedge_edge(CDTVert<T> *v, SymEdge<T
return e;
}
-/* Connect the verts of se1 and se2, assuming that currently those two SymEdges are on
+/**
+ * Connect the verts of se1 and se2, assuming that currently those two #SymEdge's are on
* the outer boundary (have face == outer_face) of two components that are isolated from
* each other.
*/
@@ -770,9 +796,9 @@ CDTEdge<T> *CDTArrangement<T>::connect_separate_parts(SymEdge<T> *se1, SymEdge<T
return e;
}
-/*
+/**
* Split se at fraction lambda,
- * and return the new CDTEdge that is the new second half.
+ * and return the new #CDTEdge that is the new second half.
* Copy the edge input_ids into the new one.
*/
template<typename T> CDTEdge<T> *CDTArrangement<T>::split_edge(SymEdge<T> *se, T lambda)
@@ -804,12 +830,12 @@ template<typename T> CDTEdge<T> *CDTArrangement<T>::split_edge(SymEdge<T> *se, T
return e;
}
-/*
+/**
* Delete an edge from the structure. The new combined face on either side of
* the deleted edge will be the one that was e's face.
* There will be now an unused face, marked by setting its deleted flag,
* and an unused #CDTEdge, marked by setting the next and rot pointers of
- * its SymEdges to NULL.
+ * its #SymEdges to #nullptr.
* <pre>
* . v2 .
* / \ / \
@@ -886,7 +912,9 @@ template<typename T> class SiteInfo {
int orig_index;
};
-/* Compare function for lexicographic sort: x, then y, then index. */
+/**
+ * Compare function for lexicographic sort: x, then y, then index.
+ */
template<typename T> bool site_lexicographic_sort(const SiteInfo<T> &a, const SiteInfo<T> &b)
{
const vec2<T> &co_a = a.v->co;
@@ -942,9 +970,10 @@ inline bool dc_tri_valid(SymEdge<T> *se, SymEdge<T> *basel, SymEdge<T> *basel_sy
return vec2<T>::orient2d(se->next->vert->co, basel_sym->vert->co, basel->vert->co) > 0;
}
-/* Delaunay triangulate sites[start} to sites[end-1].
+/**
+ * Delaunay triangulate sites[start} to sites[end-1].
* Assume sites are lexicographically sorted by coordinate.
- * Return SymEdge of ccw convex hull at left-most point in *r_le
+ * Return #SymEdge of ccw convex hull at left-most point in *r_le
* and that of right-most point of cw convex null in *r_re.
*/
template<typename T>
@@ -1114,9 +1143,8 @@ void dc_tri(CDTArrangement<T> *cdt,
if (!valid_lcand && !valid_rcand) {
break;
}
- /* The next cross edge to be connected is to either lcand->next->vert or rcand->next->vert;
- * if both are valid, choose the appropriate one using the incircle test.
- */
+ /* The next cross edge to be connected is to either `lcand->next->vert` or `rcand->next->vert`;
+ * if both are valid, choose the appropriate one using the #incircle test. */
if (!valid_lcand || (valid_rcand && vec2<T>::incircle(lcand->next->vert->co,
lcand->vert->co,
rcand->vert->co,
@@ -1171,7 +1199,7 @@ template<typename T> void dc_triangulate(CDTArrangement<T> *cdt, Array<SiteInfo<
dc_tri(cdt, sites, 0, n, &le, &re);
}
-/*
+/**
* Do a Delaunay Triangulation of the points in cdt.verts.
* This is only a first step in the Constrained Delaunay triangulation,
* because it doesn't yet deal with the segment constraints.
@@ -1205,7 +1233,7 @@ template<typename T> void initial_triangulation(CDTArrangement<T> *cdt)
dc_triangulate(cdt, sites);
}
-/*
+/**
* Re-triangulates, assuring constrained delaunay condition,
* the pseudo-polygon that cycles from se.
* "pseudo" because a vertex may be repeated.
@@ -1263,27 +1291,27 @@ template<typename T> inline int tri_orient(const SymEdge<T> *t)
return vec2<T>::orient2d(t->vert->co, t->next->vert->co, t->next->next->vert->co);
}
-/*
- * The CrossData class defines either an endpoint or an intermediate point
+/**
+ * The #CrossData class defines either an endpoint or an intermediate point
* in the path we will take to insert an edge constraint.
* Each such point will either be
* (a) a vertex or
- * (b) a fraction lambda (0 < lambda < 1) along some SymEdge.]
+ * (b) a fraction lambda (0 < lambda < 1) along some #SymEdge.]
*
* In general, lambda=0 indicates case a and lambda != 0 indicates case be.
* The 'in' edge gives the destination attachment point of a diagonal from the previous crossing,
* and the 'out' edge gives the origin attachment point of a diagonal to the next crossing.
* But in some cases, 'in' and 'out' are undefined or not needed, and will be NULL.
*
- * For case (a), 'vert' will be the vertex, and lambda will be 0, and 'in' will be the SymEdge from
- * 'vert' that has as face the one that you go through to get to this vertex. If you go exactly
- * along an edge then we set 'in' to NULL, since it won't be needed. The first crossing will have
- * 'in' = NULL. We set 'out' to the SymEdge that has the face we go though to get to the next
- * crossing, or, if the next crossing is a case (a), then it is the edge that goes to that next
- * vertex. 'out' wlll be NULL for the last one.
+ * For case (a), 'vert' will be the vertex, and lambda will be 0, and 'in' will be the #SymEdge
+ * from 'vert' that has as face the one that you go through to get to this vertex. If you go
+ * exactly along an edge then we set 'in' to NULL, since it won't be needed. The first crossing
+ * will have 'in' = NULL. We set 'out' to the #SymEdge that has the face we go though to get to the
+ * next crossing, or, if the next crossing is a case (a), then it is the edge that goes to that
+ * next vertex. 'out' will be NULL for the last one.
*
* For case (b), vert will be NULL at first, and later filled in with the created split vertex,
- * and 'in' will be the SymEdge that we go through, and lambda will be between 0 and 1,
+ * and 'in' will be the #SymEdge that we go through, and lambda will be between 0 and 1,
* the fraction from in's vert to in->next's vert to put the split vertex.
* 'out' is not needed in this case, since the attachment point will be the sym of the first
* half of the split edge.
@@ -1339,7 +1367,7 @@ bool get_next_crossing_from_vert(CDT_state<T> *cdt_state,
CrossData<T> *cd_next,
const CDTVert<T> *v2);
-/*
+/**
* As part of finding crossings, we found a case where the next crossing goes through vert v.
* If it came from a previous vert in cd, then cd_out is the edge that leads from that to v.
* Else cd_out can be NULL, because it won't be used.
@@ -1375,10 +1403,10 @@ void fill_crossdata_for_through_vert(CDTVert<T> *v,
}
}
-/*
+/**
* As part of finding crossings, we found a case where orient tests say that the next crossing
- * is on the SymEdge t, while intersecting with the ray from curco to v2.
- * Find the intersection point and fill in the CrossData for that point.
+ * is on the #SymEdge t, while intersecting with the ray from \a curco to \a v2.
+ * Find the intersection point and fill in the #CrossData for that point.
* It may turn out that when doing the intersection, we get an answer that says that
* this case is better handled as through-vertex case instead, so we may do that.
* In the latter case, we want to avoid a situation where the current crossing is on an edge
@@ -1478,7 +1506,7 @@ void fill_crossdata_for_intersect(const vec2<T> &curco,
}
} // namespace blender::meshintersect
-/*
+/**
* As part of finding the crossings of a ray to v2, find the next crossing after 'cd', assuming
* 'cd' represents a crossing that goes through a vertex.
*
@@ -1496,14 +1524,12 @@ bool get_next_crossing_from_vert(CDT_state<T> *cdt_state,
CDTVert<T> *vcur = cd->vert;
bool ok = false;
do {
- /*
- * The ray from vcur to v2 has to go either between two successive
- * edges around vcur or exactly along them. This time through the
- * loop, check to see if the ray goes along vcur-va
- * or between vcur-va and vcur-vb, where va is the end of t
+ /* The ray from `vcur` to v2 has to go either between two successive
+ * edges around `vcur` or exactly along them. This time through the
+ * loop, check to see if the ray goes along `vcur-va`
+ * or between `vcur-va` and `vcur-vb`, where va is the end of t
* and vb is the next vertex (on the next rot edge around vcur, but
- * should also be the next vert of triangle starting with vcur-va.
- */
+ * should also be the next vert of triangle starting with `vcur-va`. */
if (t->face != cdt_state->cdt.outer_face && tri_orient(t) < 0) {
BLI_assert(false); /* Shouldn't happen. */
}
@@ -1530,13 +1556,13 @@ bool get_next_crossing_from_vert(CDT_state<T> *cdt_state,
return ok;
}
-/*
- * As part of finding the crossings of a ray to v2, find the next crossing after 'cd', assuming
+/**
+ * As part of finding the crossings of a ray to `v2`, find the next crossing after 'cd', assuming
* 'cd' represents a crossing that goes through a an edge, not at either end of that edge.
*
- * We have the triangle vb-va-vc, where va and vb are the split edge and vc is the third vertex on
- * that new side of the edge (should be closer to v2). The next crossing should be through vc or
- * intersecting vb-vc or va-vc.
+ * We have the triangle `vb-va-vc`, where `va` and vb are the split edge and `vc` is the third
+ * vertex on that new side of the edge (should be closer to `v2`).
+ * The next crossing should be through `vc` or intersecting `vb-vc` or `va-vc`.
*/
template<typename T>
void get_next_crossing_from_edge(CrossData<T> *cd,
@@ -1583,7 +1609,7 @@ void dump_crossings(const Vector<CrossData<T>, inline_crossings_size> &crossings
}
}
-/*
+/**
* Add a constrained edge between v1 and v2 to cdt structure.
* This may result in a number of #CDTEdges created, due to intersections
* and partial overlaps with existing cdt vertices and edges.
@@ -1678,7 +1704,7 @@ void add_edge_constraint(
}
/*
- * Postprocess crossings.
+ * Post-process crossings.
* Some crossings may have an intersection crossing followed
* by a vertex crossing that is on the same edge that was just
* intersected. We prefer to go directly from the previous
@@ -1813,9 +1839,10 @@ void add_edge_constraint(
}
}
-/* Incrementally add edge input edge as a constraint. This may cause the graph structure
+/**
+ * Incrementally add edge input edge as a constraint. This may cause the graph structure
* to change, in cases where the constraints intersect existing edges.
- * The code will ensure that CDTEdges created will have ids that tie them back
+ * The code will ensure that #CDTEdge's created will have ids that tie them back
* to the original edge constraint index.
*/
template<typename T> void add_edge_constraints(CDT_state<T> *cdt_state, const CDT_input<T> &input)
@@ -1836,10 +1863,10 @@ template<typename T> void add_edge_constraints(CDT_state<T> *cdt_state, const CD
cdt_state->face_edge_offset = ne;
}
-/*
+/**
* Add face_id to the input_ids lists of all #CDTFace's on the interior of the input face with that
* id. face_symedge is on edge of the boundary of the input face, with assumption that interior is
- * on the left of that SymEdge.
+ * on the left of that #SymEdge.
*
* The algorithm is: starting from the #CDTFace for face_symedge, add the face_id and then
* process all adjacent faces where the adjacency isn't across an edge that was a constraint added
@@ -1848,11 +1875,11 @@ template<typename T> void add_edge_constraints(CDT_state<T> *cdt_state, const CD
*
* Note: if the input face is not CCW oriented, we'll be labeling the outside, not the inside.
* Note 2: if the boundary has self-crossings, this method will arbitrarily pick one of the
- * contiguous set of faces enclosed by parts of the boundary, leaving the other such untagged. This
- * may be a feature instead of a bug if the first contiguous section is most of the face and the
- * others are tiny self-crossing triangles at some parts of the boundary. On the other hand, if
- * decide we want to handle these in full generality, then will need a more complicated algorithm
- * (using "inside" tests and a parity rule) to decide on the interior.
+ * contiguous set of faces enclosed by parts of the boundary, leaving the other such un-tagged.
+ * This may be a feature instead of a bug if the first contiguous section is most of the face and
+ * the others are tiny self-crossing triangles at some parts of the boundary.
+ * On the other hand, if decide we want to handle these in full generality, then will need a more
+ * complicated algorithm (using "inside" tests and a parity rule) to decide on the interior.
*/
template<typename T>
void add_face_ids(
@@ -1898,8 +1925,9 @@ static int power_of_10_greater_equal_to(int x)
return ans;
}
-/* Incrementally each edge of each input face as an edge constraint.
- * The code will ensure that the CDTEdges created will have ids that tie them
+/**
+ Incrementally each edge of each input face as an edge constraint.
+ * The code will ensure that the #CDTEdge's created will have ids that tie them
* back to the original face edge (using a numbering system for those edges
* that starts with cdt->face_edge_offset, and continues with the edges in
* order around each face in turn. And then the next face starts at
@@ -1998,7 +2026,9 @@ template<typename T> void dissolve_symedge(CDT_state<T> *cdt_state, SymEdge<T> *
cdt->delete_edge(se);
}
-/* Remove all non-constraint edges. */
+/**
+ * Remove all non-constraint edges.
+ */
template<typename T> void remove_non_constraint_edges(CDT_state<T> *cdt_state)
{
for (CDTEdge<T> *e : cdt_state->cdt.edges) {
@@ -2011,7 +2041,7 @@ template<typename T> void remove_non_constraint_edges(CDT_state<T> *cdt_state)
/*
* Remove the non-constraint edges, but leave enough of them so that all of the
- * faces that would be bmesh faces (that is, the faces that have some input representative)
+ * faces that would be #BMesh faces (that is, the faces that have some input representative)
* are valid: they can't have holes, they can't have repeated vertices, and they can't have
* repeated edges.
*
@@ -2153,7 +2183,7 @@ template<typename T> void remove_outer_edges_until_constraints(CDT_state<T> *cdt
}
}
-/*
+/**
* Remove edges and merge faces to get desired output, as per options.
* \note the cdt cannot be further changed after this.
*/
@@ -2333,8 +2363,9 @@ blender::meshintersect::CDT_result<mpq_class> delaunay_2d_calc(const CDT_input<m
/* C interface. */
-/* This function uses the double version of CDT::delaunay_calc.
- * Almost all of the work here is to convert between C++ Arrays<Vector<int>>
+/**
+ This function uses the double version of #CDT::delaunay_calc.
+ * Almost all of the work here is to convert between C++ #Arrays<Vector<int>>
* and a C version that linearizes all the elements and uses a "start"
* and "len" array to say where the individual vectors start and how
* long they are.
diff --git a/source/blender/blenlib/intern/math_vec.cc b/source/blender/blenlib/intern/math_vec.cc
index cfeee6266a9..1194f3ed30e 100644
--- a/source/blender/blenlib/intern/math_vec.cc
+++ b/source/blender/blenlib/intern/math_vec.cc
@@ -189,7 +189,8 @@ uint64_t mpq3::hash() const
return hashx ^ (hashy * 33) ^ (hashz * 33 * 37);
}
-/* Return +1 if a, b, c are in CCW order around a circle in the plane.
+/**
+ * Return +1 if a, b, c are in CCW order around a circle in the plane.
* Return -1 if they are in CW order, and 0 if they are in line.
*/
int mpq2::orient2d(const mpq2 &a, const mpq2 &b, const mpq2 &c)
@@ -200,7 +201,8 @@ int mpq2::orient2d(const mpq2 &a, const mpq2 &b, const mpq2 &c)
return sgn(det);
}
-/* Return +1 if d is in the oriented circle through a, b, and c.
+/**
+ Return +1 if d is in the oriented circle through a, b, and c.
* The oriented circle goes CCW through a, b, and c.
* Return -1 if d is outside, and 0 if it is on the circle.
*/
@@ -230,7 +232,8 @@ int mpq2::incircle(const mpq2 &a, const mpq2 &b, const mpq2 &c, const mpq2 &d)
return sgn(det);
}
-/* Return +1 if d is below the plane containing a, b, c (which appear
+/**
+ * Return +1 if d is below the plane containing a, b, c (which appear
* CCW when viewed from above the plane).
* Return -1 if d is above the plane.
* Return 0 if it is on the plane.
@@ -261,7 +264,8 @@ int mpq3::orient3d(const mpq3 &a, const mpq3 &b, const mpq3 &c, const mpq3 &d)
}
#endif /* WITH_GMP */
-/* For double versions of orient and incircle functions, use robust predicates
+/**
+ * For double versions of orient and incircle functions, use robust predicates
* that give exact answers for double inputs.
* First, encapsulate functions frm Jonathan Shewchuk's implementation.
* After this namespace, see the implementation of the double3 primitives.
@@ -300,79 +304,78 @@ class RobustInitCaller {
static RobustInitCaller init_caller;
-/* Routines for Arbitrary Precision Floating-point Arithmetic
- * and Fast Robust Geometric Predicates
- * (predicates.c)
+/* Routines for Arbitrary Precision Floating-point Arithmetic
+ * and Fast Robust Geometric Predicates
+ * (predicates.c)
*
- * May 18, 1996
+ * May 18, 1996
*
- * Placed in the public domain by
- * Jonathan Richard Shewchuk
- * School of Computer Science
- * Carnegie Mellon University
- * 5000 Forbes Avenue
- * Pittsburgh, Pennsylvania 15213-3891
- * jrs@cs.cmu.edu
+ * Placed in the public domain by
+ * Jonathan Richard Shewchuk
+ * School of Computer Science
+ * Carnegie Mellon University
+ * 5000 Forbes Avenue
+ * Pittsburgh, Pennsylvania 15213-3891
+ * jrs@cs.cmu.edu
*
- * This file contains C implementation of algorithms for exact addition
- * and multiplication of floating-point numbers, and predicates for
- * robustly performing the orientation and incircle tests used in
- * computational geometry. The algorithms and underlying theory are
- * described in Jonathan Richard Shewchuk. "Adaptive Precision Floating-
- * Point Arithmetic and Fast Robust Geometric Predicates." Technical
- * Report CMU-CS-96-140, School of Computer Science, Carnegie Mellon
- * University, Pittsburgh, Pennsylvania, May 1996. (Submitted to
- * Discrete & Computational Geometry.)
+ * This file contains C implementation of algorithms for exact addition
+ * and multiplication of floating-point numbers, and predicates for
+ * robustly performing the orientation and incircle tests used in
+ * computational geometry. The algorithms and underlying theory are
+ * described in Jonathan Richard Shewchuk. "Adaptive Precision Floating-
+ * Point Arithmetic and Fast Robust Geometric Predicates." Technical
+ * Report CMU-CS-96-140, School of Computer Science, Carnegie Mellon
+ * University, Pittsburgh, Pennsylvania, May 1996. (Submitted to
+ * Discrete & Computational Geometry.)
*
- * This file, the paper listed above, and other information are available
- * from the Web page http://www.cs.cmu.edu/~quake/robust.html .
+ * This file, the paper listed above, and other information are available
+ * from the Web page http://www.cs.cmu.edu/~quake/robust.html .
*
*
- * Using this code:
+ * Using this code:
*
- * First, read the short or long version of the paper (from the Web page
- * above).
+ * First, read the short or long version of the paper (from the Web page above).
*
- * Be sure to call exactinit() once, before calling any of the arithmetic
- * functions or geometric predicates. Also be sure to turn on the
- * optimizer when compiling this file.
+ * Be sure to call #exactinit() once, before calling any of the arithmetic
+ * functions or geometric predicates. Also be sure to turn on the
+ * optimizer when compiling this file.
*/
/* On some machines, the exact arithmetic routines might be defeated by the
- * use of internal extended precision floating-point registers. Sometimes
- * this problem can be fixed by defining certain values to be volatile,
- * thus forcing them to be stored to memory and rounded off. This isn't
- * a great solution, though, as it slows the arithmetic down.
+ * use of internal extended precision floating-point registers. Sometimes
+ * this problem can be fixed by defining certain values to be volatile,
+ * thus forcing them to be stored to memory and rounded off. This isn't
+ * a great solution, though, as it slows the arithmetic down.
*
* To try this out, write "#define INEXACT volatile" below. Normally,
- * however, INEXACT should be defined to be nothing. ("#define INEXACT".)
+ * however, INEXACT should be defined to be nothing. ("#define INEXACT".)
*/
#define INEXACT /* Nothing */
/* #define INEXACT volatile */
/* Which of the following two methods of finding the absolute values is
- * fastest is compiler-dependent. A few compilers can inline and optimize
- * the fabs() call; but most will incur the overhead of a function call,
- * which is disastrously slow. A faster way on IEEE machines might be to
- * mask the appropriate bit, but that's difficult to do in C.
+ * fastest is compiler-dependent. A few compilers can inline and optimize
+ * the fabs() call; but most will incur the overhead of a function call,
+ * which is disastrously slow. A faster way on IEEE machines might be to
+ * mask the appropriate bit, but that's difficult to do in C.
*/
#define Absolute(a) ((a) >= 0.0 ? (a) : -(a))
/* #define Absolute(a) fabs(a) */
/* Many of the operations are broken up into two pieces, a main part that
- * performs an approximate operation, and a "tail" that computes the
- * roundoff error of that operation.
+ * performs an approximate operation, and a "tail" that computes the
+ * round-off error of that operation.
*
* The operations Fast_Two_Sum(), Fast_Two_Diff(), Two_Sum(), Two_Diff(),
- * Split(), and Two_Product() are all implemented as described in the
- * reference. Each of these macros requires certain variables to be
- * defined in the calling routine. The variables `bvirt', `c', `abig',
- * `_i', `_j', `_k', `_l', `_m', and `_n' are declared `INEXACT' because
- * they store the result of an operation that may incur roundoff error.
- * The input parameter `x' (or the highest numbered `x_' parameter) must
- * also be declared `INEXACT'.
+ * Split(), and Two_Product() are all implemented as described in the
+ * reference. Each of these macros requires certain variables to be
+ * defined in the calling routine. The variables `bvirt', `c', `abig',
+ * `_i', `_j', `_k', `_l', `_m', and `_n' are declared `INEXACT' because
+ * they store the result of an operation that may incur roundoff error.
+ * The input parameter `x' (or the highest numbered `x_' parameter) must
+ * also be declared `INEXACT'.
*/
#define Fast_Two_Sum_Tail(a, b, x, y) \
@@ -583,11 +586,11 @@ static double o3derrboundA, o3derrboundB, o3derrboundC;
static double iccerrboundA, iccerrboundB, iccerrboundC;
static double isperrboundA, isperrboundB, isperrboundC;
-/*
+/**
* exactinit() Initialize the variables used for exact arithmetic.
*
* `epsilon' is the largest power of two such that 1.0 + epsilon = 1.0 in
- * floating-point arithmetic. `epsilon' bounds the relative roundoff
+ * floating-point arithmetic. `epsilon' bounds the relative round-off
* error. It is used for floating-point error analysis.
*
* `splitter' is used to split floating-point numbers into two half-
@@ -611,10 +614,10 @@ void exactinit()
epsilon = 1.0;
splitter = 1.0;
check = 1.0;
- /* Repeatedly divide `epsilon' by two until it is too small to add to */
- /* one without causing roundoff. (Also check if the sum is equal to */
- /* the previous sum, for machines that round up instead of using exact */
- /* rounding. Not that this library will work on such machines anyway. */
+ /* Repeatedly divide `epsilon' by two until it is too small to add to
+ * one without causing round-off. (Also check if the sum is equal to
+ * the previous sum, for machines that round up instead of using exact
+ * rounding. Not that this library will work on such machines anyway. */
do {
lastcheck = check;
epsilon *= half;
@@ -626,7 +629,7 @@ void exactinit()
} while ((check != 1.0) && (check != lastcheck));
splitter += 1.0;
- /* Error bounds for orientation and incircle tests. */
+ /* Error bounds for orientation and #incircle tests. */
resulterrbound = (3.0 + 8.0 * epsilon) * epsilon;
ccwerrboundA = (3.0 + 16.0 * epsilon) * epsilon;
ccwerrboundB = (2.0 + 12.0 * epsilon) * epsilon;
@@ -642,7 +645,8 @@ void exactinit()
isperrboundC = (71.0 + 1408.0 * epsilon) * epsilon * epsilon;
}
-/* fast_expansion_sum_zeroelim() Sum two expansions, eliminating zero
+/**
+ * fast_expansion_sum_zeroelim() Sum two expansions, eliminating zero
* components from the output expansion.
*
* Sets h = e + f. See the long version of my paper for details.
@@ -780,21 +784,22 @@ static double estimate(int elen, const double *e)
return Q;
}
-/* orient2dfast() Approximate 2D orientation test. Nonrobust.
- * orient2d() Adaptive exact 2D orientation test. Robust.
+/**
+ * orient2dfast() Approximate 2D orientation test. Nonrobust.
+ * orient2d() Adaptive exact 2D orientation test. Robust.
* Return a positive value if the points pa, pb, and pc occur
* in counterclockwise order; a negative value if they occur
- * in clockwise order; and zero if they are collinear. The
+ * in clockwise order; and zero if they are co-linear. The
* result is also a rough approximation of twice the signed
* area of the triangle defined by the three points.
*
- * The second uses exact arithmetic to ensure a correct answer. The
- * result returned is the determinant of a matrix. In orient2d() only,
- * this determinant is computed adaptively, in the sense that exact
- * arithmetic is used only to the degree it is needed to ensure that the
- * returned value has the correct sign. Hence, orient2d() is usually quite
- * fast, but will run more slowly when the input points are collinear or
- * nearly so.
+ * The second uses exact arithmetic to ensure a correct answer. The
+ * result returned is the determinant of a matrix. In orient2d() only,
+ * this determinant is computed adaptively, in the sense that exact
+ * arithmetic is used only to the degree it is needed to ensure that the
+ * returned value has the correct sign. Hence, orient2d() is usually quite
+ * fast, but will run more slowly when the input points are co-linear or
+ * nearly so.
*/
double orient2dfast(const double *pa, const double *pb, const double *pc)
@@ -918,25 +923,26 @@ double orient2d(const double *pa, const double *pb, const double *pc)
return orient2dadapt(pa, pb, pc, detsum);
}
-/* orient3dfast() Approximate 3D orientation test. Nonrobust.
- * orient3d() Adaptive exact 3D orientation test. Robust.
+/**
+ * orient3dfast() Approximate 3D orientation test. Nonrobust.
+ * orient3d() Adaptive exact 3D orientation test. Robust.
*
* Return a positive value if the point pd lies below the
* plane passing through pa, pb, and pc; "below" is defined so
* that pa, pb, and pc appear in counterclockwise order when
* viewed from above the plane. Returns a negative value if
* pd lies above the plane. Returns zero if the points are
- * coplanar. The result is also a rough approximation of six
+ * co-planar. The result is also a rough approximation of six
* times the signed volume of the tetrahedron defined by the
* four points.
*
- * The second uses exact arithmetic to ensure a correct answer. The
- * result returned is the determinant of a matrix. In orient3d() only,
- * this determinant is computed adaptively, in the sense that exact
- * arithmetic is used only to the degree it is needed to ensure that the
- * returned value has the correct sign. Hence, orient3d() is usually quite
- * fast, but will run more slowly when the input points are coplanar or
- * nearly so.
+ * The second uses exact arithmetic to ensure a correct answer. The
+ * result returned is the determinant of a matrix. In orient3d() only,
+ * this determinant is computed adaptively, in the sense that exact
+ * arithmetic is used only to the degree it is needed to ensure that the
+ * returned value has the correct sign. Hence, orient3d() is usually quite
+ * fast, but will run more slowly when the input points are co-planar or
+ * nearly so.
*/
double orient3dfast(const double *pa, const double *pb, const double *pc, const double *pd)
@@ -959,9 +965,11 @@ double orient3dfast(const double *pa, const double *pb, const double *pc, const
cdx * (ady * bdz - adz * bdy);
}
-/* Note: since this code comes from an external source, prefer not to break it
+/**
+ * \note since this code comes from an external source, prefer not to break it
* up to fix this clang-tidy warning.
- * NOLINTNEXTLINE: readability-function-size */
+ * NOLINTNEXTLINE: readability-function-size
+ */
static double orient3dadapt(
const double *pa, const double *pb, const double *pc, const double *pd, double permanent)
{
@@ -1429,7 +1437,8 @@ double orient3d(const double *pa, const double *pb, const double *pc, const doub
return orient3dadapt(pa, pb, pc, pd, permanent);
}
-/* incirclefast() Approximate 2D incircle test. Nonrobust.
+/**
+ * incirclefast() Approximate 2D incircle test. Nonrobust.
* incircle()
*
* Return a positive value if the point pd lies inside the
@@ -1470,9 +1479,11 @@ double incirclefast(const double *pa, const double *pb, const double *pc, const
return alift * bcdet + blift * cadet + clift * abdet;
}
-/* Note: since this code comes from an external source, prefer not to break it
+/**
+ * \note since this code comes from an external source, prefer not to break it
* up to fix this clang-tidy warning.
- * NOLINTNEXTLINE: readability-function-size */
+ * NOLINTNEXTLINE: readability-function-size
+ */
static double incircleadapt(
const double *pa, const double *pb, const double *pc, const double *pd, double permanent)
{
@@ -2035,7 +2046,8 @@ double incircle(const double *pa, const double *pb, const double *pc, const doub
return incircleadapt(pa, pb, pc, pd, permanent);
}
-/* inspherefast() Approximate 3D insphere test. Nonrobust.
+/**
+ * inspherefast() Approximate 3D insphere test. Nonrobust.
* insphere() Adaptive exact 3D insphere test. Robust.
*
* Return a positive value if the point pe lies inside the
diff --git a/source/blender/blenlib/intern/math_vector.c b/source/blender/blenlib/intern/math_vector.c
index 32d728f28d4..fb3ea539df1 100644
--- a/source/blender/blenlib/intern/math_vector.c
+++ b/source/blender/blenlib/intern/math_vector.c
@@ -809,7 +809,7 @@ void reflect_v3_v3v3_db(double out[3], const double v[3], const double normal[3]
{
const double dot2 = 2.0 * dot_v3v3_db(v, normal);
- /* BLI_ASSERT_UNIT_V3_DB(normal); this assert is not knownn? */
+ /* BLI_ASSERT_UNIT_V3_DB(normal); this assert is not known? */
out[0] = v[0] - (dot2 * normal[0]);
out[1] = v[1] - (dot2 * normal[1]);
diff --git a/source/blender/blenlib/intern/mesh_boolean.cc b/source/blender/blenlib/intern/mesh_boolean.cc
index a628cfa500f..2196680141a 100644
--- a/source/blender/blenlib/intern/mesh_boolean.cc
+++ b/source/blender/blenlib/intern/mesh_boolean.cc
@@ -14,6 +14,10 @@
* Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
*/
+/** \file
+ * \ingroup bli
+ */
+
#ifdef WITH_GMP
# include <algorithm>
@@ -39,7 +43,8 @@
namespace blender::meshintersect {
-/* Edge as two const Vert *'s, in a canonical order (lower vert id first).
+/**
+ * Edge as two `const` Vert *'s, in a canonical order (lower vert id first).
* We use the Vert id field for hashing to get algorithms
* that yield predictable results from run-to-run and machine-to-machine.
*/
@@ -118,19 +123,19 @@ static std::ostream &operator<<(std::ostream &os, const Array<int> &iarr)
return os;
}
-/* Holds information about topology of an IMesh that is all triangles. */
+/** Holds information about topology of an #IMesh that is all triangles. */
class TriMeshTopology : NonCopyable {
- /* Triangles that contain a given Edge (either order). */
+ /** Triangles that contain a given Edge (either order). */
Map<Edge, Vector<int> *> edge_tri_;
- /* Edges incident on each vertex. */
+ /** Edges incident on each vertex. */
Map<const Vert *, Vector<Edge>> vert_edges_;
public:
TriMeshTopology(const IMesh &tm);
~TriMeshTopology();
- /* If e is manifold, return index of the other triangle (not t) that has it. Else return
- * NO_INDEX. */
+ /* If e is manifold, return index of the other triangle (not t) that has it.
+ * Else return NO_INDEX. */
int other_tri_if_manifold(Edge e, int t) const
{
if (edge_tri_.contains(e)) {
@@ -149,8 +154,7 @@ class TriMeshTopology : NonCopyable {
}
/* Which edges are incident on the given vertex?
- * We assume v has some incident edges.
- */
+ * We assume v has some incident edges. */
const Vector<Edge> &vert_edges(const Vert *v) const
{
return vert_edges_.lookup(v);
@@ -168,9 +172,8 @@ TriMeshTopology::TriMeshTopology(const IMesh &tm)
if (dbg_level > 0) {
std::cout << "TRIMESHTOPOLOGY CONSTRUCTION\n";
}
- /* If everything were manifold, F+V-E=2 and E=3F/2.
- * So an likely overestimate, allowing for non-manifoldness, is E=2F and V=F.
- */
+ /* If everything were manifold, `F+V-E=2` and `E=3F/2`.
+ * So an likely overestimate, allowing for non-manifoldness, is `E=2F` and `V=F`. */
const int estimate_num_edges = 2 * tm.face_size();
const int estimate_num_verts = tm.face_size();
edge_tri_.reserve(estimate_num_edges);
@@ -221,7 +224,7 @@ TriMeshTopology::~TriMeshTopology()
}
}
-/* A Patch is a maximal set of triangles that share manifold edges only. */
+/** A Patch is a maximal set of triangles that share manifold edges only. */
class Patch {
Vector<int> tri_; /* Indices of triangles in the Patch. */
@@ -277,11 +280,11 @@ static std::ostream &operator<<(std::ostream &os, const Patch &patch)
}
class PatchesInfo {
- /* All of the Patches for a IMesh. */
+ /** All of the Patches for a #IMesh. */
Vector<Patch> patch_;
- /* Patch index for corresponding triangle. */
+ /** Patch index for corresponding triangle. */
Array<int> tri_patch_;
- /* Shared edge for incident patches; (-1, -1) if none. */
+ /** Shared edge for incident patches; (-1, -1) if none. */
Map<std::pair<int, int>, Edge> pp_edge_;
public:
@@ -368,7 +371,8 @@ class PatchesInfo {
static bool apply_bool_op(BoolOpType bool_optype, const Array<int> &winding);
-/* A Cell is a volume of 3-space, surrounded by patches.
+/**
+ * A Cell is a volume of 3-space, surrounded by patches.
* We will partition all 3-space into Cells.
* One cell, the Ambient cell, contains all other cells.
*/
@@ -453,7 +457,8 @@ class Cell {
merged_to_ = c;
}
- /* Call this when it is possible that this Cell has zero volume,
+ /**
+ * Call this when it is possible that this Cell has zero volume,
* and if it does, set zero_volume_ to true.
*/
void check_for_zero_volume(const PatchesInfo &pinfo, const IMesh &mesh);
@@ -490,7 +495,8 @@ static bool tris_have_same_verts(const IMesh &mesh, int t1, int t2)
return false;
}
-/* A Cell will have zero volume if it is bounded by exactly two patches and those
+/**
+ * A Cell will have zero volume if it is bounded by exactly two patches and those
* patches are geometrically identical triangles (perhaps flipped versions of each other).
* If this Cell has zero volume, set its zero_volume_ member to true.
*/
@@ -568,16 +574,18 @@ class CellsInfo {
}
};
-/* For Debugging: write a .obj file showing the patch/cell structure or just the cells. */
+/**
+ * For Debugging: write a .obj file showing the patch/cell structure or just the cells.
+ */
static void write_obj_cell_patch(const IMesh &m,
const CellsInfo &cinfo,
const PatchesInfo &pinfo,
bool cells_only,
const std::string &name)
{
- /* Would like to use BKE_tempdir_base() here, but that brings in dependence on kernel library.
- * This is just for developer debugging anyway, and should never be called in production Blender.
- */
+ /* Would like to use #BKE_tempdir_base() here, but that brings in dependence on kernel library.
+ * This is just for developer debugging anyway,
+ * and should never be called in production Blender. */
# ifdef _WIN_32
const char *objdir = BLI_getenv("HOME");
# else
@@ -658,7 +666,9 @@ static void merge_cells(int merge_to, int merge_from, CellsInfo &cinfo, PatchesI
merge_from_cell.set_merged_to(final_merge_to);
}
-/* Partition the triangles of tm into Patches. */
+/**
+ * Partition the triangles of \a tm into Patches.
+ */
static PatchesInfo find_patches(const IMesh &tm, const TriMeshTopology &tmtopo)
{
const int dbg_level = 0;
@@ -754,7 +764,8 @@ static PatchesInfo find_patches(const IMesh &tm, const TriMeshTopology &tmtopo)
return pinfo;
}
-/* If e is an edge in tri, return the vertex that isn't part of tri,
+/**
+ * If e is an edge in tri, return the vertex that isn't part of tri,
* the "flap" vertex, or nullptr if e is not part of tri.
* Also, e may be reversed in tri.
* Set *r_rev to true if it is reversed, else false.
@@ -808,12 +819,12 @@ static const Vert *find_flap_vert(const Face &tri, const Edge e, bool *r_rev)
return flapv;
}
-/*
- * Triangle tri and tri0 share edge e.
- * Classify tri with respect to tri0 as described in
- * sort_tris_around_edge, and return 1, 2, 3, or 4 as tri is:
- * (1) coplanar with tri0 and on same side of e
- * (2) coplanar with tri0 and on opposite side of e
+/**
+ * Triangle \a tri and tri0 share edge e.
+ * Classify \a tri with respect to tri0 as described in
+ * sort_tris_around_edge, and return 1, 2, 3, or 4 as \a tri is:
+ * (1) co-planar with tri0 and on same side of e
+ * (2) co-planar with tri0 and on opposite side of e
* (3) below plane of tri0
* (4) above plane of tri0
* For "above" and "below", we use the orientation of non-reversed
@@ -863,7 +874,8 @@ static int sort_tris_class(const Face &tri, const Face &tri0, const Edge e)
constexpr int EXTRA_TRI_INDEX = INT_MAX;
-/* To ensure consistent ordering of coplanar triangles if they happen to be sorted around
+/**
+ * To ensure consistent ordering of co-planar triangles if they happen to be sorted around
* more than one edge, sort the triangle indices in g (in place) by their index -- but also apply
* a sign to the index: positive if the triangle has edge e in the same orientation,
* otherwise negative.
@@ -887,10 +899,10 @@ static void sort_by_signed_triangle_index(Vector<int> &g,
}
}
-/*
- * Sort the triangles tris, which all share edge e, as they appear
+/**
+ * Sort the triangles \a tris, which all share edge e, as they appear
* geometrically clockwise when looking down edge e.
- * Triangle t0 is the first triangle in the toplevel call
+ * Triangle t0 is the first triangle in the top-level call
* to this recursive routine. The merge step below differs
* for the top level call and all the rest, so this distinguishes those cases.
* Care is taken in the case of duplicate triangles to have
@@ -908,17 +920,16 @@ static Array<int> sort_tris_around_edge(const IMesh &tm,
const int t0,
const Face *extra_tri)
{
- /* Divide and conquer, quicksort-like sort.
+ /* Divide and conquer, quick-sort-like sort.
* Pick a triangle t0, then partition into groups:
- * (1) coplanar with t0 and on same side of e
- * (2) coplanar with t0 and on opposite side of e
+ * (1) co-planar with t0 and on same side of e
+ * (2) co-planar with t0 and on opposite side of e
* (3) below plane of t0
* (4) above plane of t0
* Each group is sorted and then the sorts are merged to give the answer.
* We don't expect the input array to be very large - should typically
* be only 3 or 4 - so OK to make copies of arrays instead of swapping
- * around in a single array.
- */
+ * around in a single array. */
const int dbg_level = 0;
if (tris.size() == 0) {
return Array<int>();
@@ -1006,10 +1017,11 @@ static Array<int> sort_tris_around_edge(const IMesh &tm,
return ans;
}
-/* Find the Cells around edge e.
- * This possibly makes new cells in cinfo, and sets up the
+/**
+ * Find the Cells around edge e.
+ * This possibly makes new cells in \a cinfo, and sets up the
* bipartite graph edges between cells and patches.
- * Will modify pinfo and cinfo and the patches and cells they contain.
+ * Will modify \a pinfo and \a cinfo and the patches and cells they contain.
*/
static void find_cells_from_edge(const IMesh &tm,
const TriMeshTopology &tmtopo,
@@ -1105,7 +1117,8 @@ static void find_cells_from_edge(const IMesh &tm,
}
}
-/* Find the partition of 3-space into Cells.
+/**
+ * Find the partition of 3-space into Cells.
* This assigns the cell_above and cell_below for each Patch.
*/
static CellsInfo find_cells(const IMesh &tm, const TriMeshTopology &tmtopo, PatchesInfo &pinfo)
@@ -1133,8 +1146,7 @@ static CellsInfo find_cells(const IMesh &tm, const TriMeshTopology &tmtopo, Patc
* (a) a closed manifold patch only incident on itself (sphere, torus, klein bottle, etc.).
* (b) an open manifold patch only incident on itself (has non-manifold boundaries).
* Make above and below cells for these patches. This will create a disconnected patch-cell
- * bipartite graph, which will have to be fixed later.
- */
+ * bipartite graph, which will have to be fixed later. */
for (int p : pinfo.index_range()) {
Patch &patch = pinfo.patch(p);
if (patch.cell_above == NO_INDEX) {
@@ -1166,7 +1178,8 @@ static CellsInfo find_cells(const IMesh &tm, const TriMeshTopology &tmtopo, Patc
return cinfo;
}
-/* Find the connected patch components (connects are via intermediate cells), and put
+/**
+ * Find the connected patch components (connects are via intermediate cells), and put
* component numbers in each patch.
* Return a Vector of components - each a Vector of the patch ids in the component.
*/
@@ -1217,7 +1230,8 @@ static Vector<Vector<int>> find_patch_components(const CellsInfo &cinfo, Patches
return ans;
}
-/* Do all patches have cell_above and cell_below set?
+/**
+ * Do all patches have cell_above and cell_below set?
* Is the bipartite graph connected?
*/
static bool patch_cell_graph_ok(const CellsInfo &cinfo, const PatchesInfo &pinfo)
@@ -1253,7 +1267,8 @@ static bool patch_cell_graph_ok(const CellsInfo &cinfo, const PatchesInfo &pinfo
return true;
}
-/* Is trimesh tm PWN ("piecewise constant winding number")?
+/**
+ * Is trimesh tm PWN ("Piece-wise constant Winding Number")?
* See Zhou et al. paper for exact definition, but roughly
* means that the faces connect so as to form closed volumes.
* The actual definition says that if you calculate the
@@ -1261,7 +1276,7 @@ static bool patch_cell_graph_ok(const CellsInfo &cinfo, const PatchesInfo &pinfo
* the mesh, it will always be an integer.
* Necessary (but not sufficient) conditions that a mesh be PWN:
* No edges with a non-zero sum of incident face directions.
- * I think that cases like Klein bottles are likly to satisfy
+ * I think that cases like Klein bottles are likely to satisfy
* this without being PWN. So this routine will be only
* approximately right.
*/
@@ -1272,8 +1287,7 @@ static bool is_pwn(const IMesh &tm, const TriMeshTopology &tmtopo)
const Edge &edge = item.key;
int tot_orient = 0;
/* For each face t attached to edge, add +1 if the edge
- * is positively in t, and -1 if negatively in t.
- */
+ * is positively in t, and -1 if negatively in t. */
for (int t : *item.value) {
const Face &face = *tm.face(t);
BLI_assert(face.size() == 3);
@@ -1299,7 +1313,8 @@ static bool is_pwn(const IMesh &tm, const TriMeshTopology &tmtopo)
return true;
}
-/* Find which of the cells around edge e contains point p.
+/**
+ * Find which of the cells around edge e contains point p.
* Do this by inserting a dummy triangle containing v and sorting the
* triangles around the edge to find out where in the sort order
* the dummy triangle lies, then finding which cell is between
@@ -1355,7 +1370,7 @@ static int find_cell_for_point_near_edge(mpq3 p,
return c;
}
-/*
+/**
* Find the ambient cell -- that is, the cell that is outside
* all other cells.
* If component_patches != nullptr, restrict consideration to patches
@@ -1380,7 +1395,7 @@ static int find_ambient_cell(const IMesh &tm,
std::cout << "FIND_AMBIENT_CELL\n";
}
/* First find a vertex with the maximum x value. */
- /* Prefer not to populate the verts in the IMesh just for this. */
+ /* Prefer not to populate the verts in the #IMesh just for this. */
const Vert *v_extreme;
mpq_class extreme_x;
if (component_patches == nullptr) {
@@ -1420,9 +1435,8 @@ static int find_ambient_cell(const IMesh &tm,
std::cout << "v_extreme = " << v_extreme << "\n";
}
/* Find edge attached to v_extreme with max absolute slope
- * when projected onto the xy plane. That edge is guaranteed to
- * be on the convex hull of the mesh.
- */
+ * when projected onto the XY plane. That edge is guaranteed to
+ * be on the convex hull of the mesh. */
const Vector<Edge> &edges = tmtopo.vert_edges(v_extreme);
const mpq_class extreme_y = v_extreme->co_exact.y;
Edge ehull;
@@ -1456,13 +1470,14 @@ static int find_ambient_cell(const IMesh &tm,
return c_ambient;
}
-/* We need an edge on the convex hull of the edges incident on closestp
- * in order to sort around, including a dummy triangle that has testp and
- * the sorting edge vertices. So we don't want an edge that is collinear
- * with the line through testp and closestp.
- * The method is to project onto a plane that contains testp-closestp,
+/**
+ * We need an edge on the convex hull of the edges incident on \a closestp
+ * in order to sort around, including a dummy triangle that has \a testp and
+ * the sorting edge vertices. So we don't want an edge that is co-llinear
+ * with the line through \a testp and \a closestp.
+ * The method is to project onto a plane that contains `testp-closestp`,
* and then choose the edge that, when projected, has the maximum absolute
- * slope (regarding the line testp-closestp as the xaxis for slope computation).
+ * slope (regarding the line `testp-closestp` as the x-axis for slope computation).
*/
static Edge find_good_sorting_edge(const Vert *testp,
const Vert *closestp,
@@ -1477,8 +1492,7 @@ static Edge find_good_sorting_edge(const Vert *testp,
* and whose abscissa direction is some perpendicular to that.
* A perpendicular direction can be found by swapping two coordinates
* and negating one, and zeroing out the third, being careful that one
- * of the swapped vertices is non-zero.
- */
+ * of the swapped vertices is non-zero. */
const mpq3 &co_closest = closestp->co_exact;
const mpq3 &co_test = testp->co_exact;
BLI_assert(co_test != co_closest);
@@ -1516,8 +1530,7 @@ static Edge find_good_sorting_edge(const Vert *testp,
mpq3 proj_evec = evec - (mpq3::dot(evec, normal) / nlen2) * normal;
/* The projection calculations along the abscissa and ordinate should
* be scaled by 1/abscissa and 1/ordinate respectively,
- * but we can skip: it won't affect which evec has the maximum slope.
- */
+ * but we can skip: it won't affect which `evec` has the maximum slope. */
mpq_class evec_a = mpq3::dot(proj_evec, abscissa);
mpq_class evec_o = mpq3::dot(proj_evec, ordinate);
if (dbg_level > 0) {
@@ -1546,9 +1559,10 @@ static Edge find_good_sorting_edge(const Vert *testp,
return esort;
}
-/* Find the cell that contains v. Consider the cells adjacent to triangle t.
+/**
+ * Find the cell that contains v. Consider the cells adjacent to triangle t.
* The close_edge and close_vert values are what were returned by
- * closest_on_tri_to_point when determining that v was close to t.
+ * #closest_on_tri_to_point when determining that v was close to t.
* They will indicate whether the point of closest approach to t is to
* an edge of t, a vertex of t, or somewhere inside t.
*
@@ -1616,13 +1630,14 @@ static int find_containing_cell(const Vert *v,
return c;
}
-/* Find the closest point in triangle (a, b, c) to point p.
+/**
+ * Find the closest point in triangle (a, b, c) to point p.
* Return the distance squared to that point.
* Also, if the closest point in the triangle is on a vertex,
* return 0, 1, or 2 for a, b, c in *r_vert; else -1.
* If the closest point is on an edge, return 0, 1, or 2
* for edges ab, bc, or ca in *r_edge; else -1.
- * (Adapted from closest_on_tri_to_point_v3()).
+ * (Adapted from #closest_on_tri_to_point_v3()).
*/
static mpq_class closest_on_tri_to_point(
const mpq3 &p, const mpq3 &a, const mpq3 &b, const mpq3 &c, int *r_edge, int *r_vert)
@@ -1740,7 +1755,8 @@ struct ComponentContainer {
}
};
-/* Find out all the components, not equal to comp, that contain a point
+/**
+ * Find out all the components, not equal to comp, that contain a point
* in comp in a non-ambient cell of those components.
* In other words, find the components that comp is nested inside
* (maybe not directly nested, which is why there can be more than one).
@@ -1829,7 +1845,8 @@ static Vector<ComponentContainer> find_component_containers(int comp,
return ans;
}
-/* The cells and patches are supposed to form a bipartite graph.
+/**
+ * The cells and patches are supposed to form a bipartite graph.
* The graph may be disconnected (if parts of meshes are nested or side-by-side
* without intersection with other each other).
* Connect the bipartite graph. This involves discovering the connected components
@@ -1939,9 +1956,10 @@ static void finish_patch_cell_graph(const IMesh &tm,
}
}
-/* Starting with ambient cell c_ambient, with all zeros for winding numbers,
+/**
+ * Starting with ambient cell c_ambient, with all zeros for winding numbers,
* propagate winding numbers to all the other cells.
- * There will be a vector of nshapes winding numbers in each cell, one per
+ * There will be a vector of \a nshapes winding numbers in each cell, one per
* input shape.
* As one crosses a patch into a new cell, the original shape (mesh part)
* that that patch was part of dictates which winding number changes.
@@ -2009,7 +2027,8 @@ static void propagate_windings_and_in_output_volume(PatchesInfo &pinfo,
}
}
-/* Given an array of winding numbers, where the ith entry is a cell's winding
+/**
+ * Given an array of winding numbers, where the ith entry is a cell's winding
* number with respect to input shape (mesh part) i, return true if the
* cell should be included in the output of the boolean operation.
* Intersection: all the winding numbers must be nonzero.
@@ -2058,7 +2077,8 @@ static bool apply_bool_op(BoolOpType bool_optype, const Array<int> &winding)
}
}
-/* Special processing for extract_from_in_output_volume_diffs to handle
+/**
+ * Special processing for extract_from_in_output_volume_diffs to handle
* triangles that are part of stacks of geometrically identical
* triangles enclosing zero volume cells.
*/
@@ -2096,10 +2116,9 @@ static void extract_zero_volume_cell_tris(Vector<Face *> &r_tris,
Vector<bool> flipped{false};
allocated_to_stack[p] = true;
/* We arbitrarily choose p's above and below directions as above and below for whole stack.
- * Triangles in the stack that don't follow that convention are makred with flipped = true.
+ * Triangles in the stack that don't follow that convention are marked with flipped = true.
* The non-zero-volume cell above the whole stack, following this convention, is
- * above_stack_cell. The non-zero-volume cell below the whole stack is below_stack_cell.
- */
+ * above_stack_cell. The non-zero-volume cell below the whole stack is #below_stack_cell. */
/* First, walk in the above_cell direction from p. */
int pwalk = p;
const Patch *pwalk_patch = &pinfo.patch(pwalk);
@@ -2178,12 +2197,13 @@ static void extract_zero_volume_cell_tris(Vector<Face *> &r_tris,
}
}
-/* Extract the output mesh from tm_subdivided and return it as a new mesh.
- * The cells in cinfo must have cells-to-be-retained with in_output_volume set.
+/**
+ * Extract the output mesh from tm_subdivided and return it as a new mesh.
+ * The cells in \a cinfo must have cells-to-be-retained with in_output_volume set.
* We keep only triangles between those in the output volume and those not in.
* We flip the normals of any triangle that has an in_output_volume cell above
* and a not-in_output_volume cell below.
- * For all stacks of exact duplicate coplanar triangles, we want to
+ * For all stacks of exact duplicate co-planar triangles, we want to
* include either one version of the triangle or none, depending on
* whether the in_output_volume in_output_volumes on either side of the stack are
* different or the same.
@@ -2267,7 +2287,8 @@ static mpq3 calc_point_inside_tri(const Face &tri)
return ans;
}
-/* Return the Generalized Winding Number of point testp wih respect to the
+/**
+ * Return the Generalized Winding Number of point \a testp with respect to the
* volume implied by the faces for which shape_fn returns the value shape.
* See "Robust Inside-Outside Segmentation using Generalized Winding Numbers"
* by Jacobson, Kavan, and Sorkine-Hornung.
@@ -2275,8 +2296,8 @@ static mpq3 calc_point_inside_tri(const Face &tri)
* is inside the volume. But it is tolerant of not-completely-watertight
* volumes, still doing a passable job of classifying inside/outside
* as we intuitively understand that to mean.
- * TOOD: speed up this calculation using the heirarchical algorithm in
- * that paper.
+ *
+ * TOOD: speed up this calculation using the hierarchical algorithm in that paper.
*/
static double generalized_winding_number(const IMesh &tm,
std::function<int(int)> shape_fn,
@@ -2303,8 +2324,7 @@ static double generalized_winding_number(const IMesh &tm,
double3 c = v2->co - testp;
/* Calculate the solid angle of abc relative to origin.
* See "The Solid Angle of a Plane Triangle" by Oosterom and Strackee
- * for the derivation of the formula.
- */
+ * for the derivation of the formula. */
double alen = a.length();
double blen = b.length();
double clen = c.length();
@@ -2333,7 +2353,8 @@ static double generalized_winding_number(const IMesh &tm,
return gwn;
}
-/* Return true if point testp is inside the volume implied by the
+/**
+ * Return true if point \a testp is inside the volume implied by the
* faces for which the shape_fn returns the value shape.
*/
static bool point_is_inside_shape(const IMesh &tm,
@@ -2345,12 +2366,12 @@ static bool point_is_inside_shape(const IMesh &tm,
/* Due to floating point error, an outside point should get a value
* of zero for gwn, but may have a very slightly positive value instead.
* It is not important to get this epsilon very small, because practical
- * cases of interest will have gwn at least 0.2 if it is not zero.
- */
+ * cases of interest will have gwn at least 0.2 if it is not zero. */
return (gwn > 0.01);
}
-/* Use the Generalized Winding Number method for deciding if a patch of the
+/**
+ * Use the Generalized Winding Number method for deciding if a patch of the
* mesh is supposed to be included or excluded in the boolean result,
* and return the mesh that is the boolean result.
*/
@@ -2372,8 +2393,7 @@ static IMesh gwn_boolean(const IMesh &tm,
for (int p : pinfo.index_range()) {
const Patch &patch = pinfo.patch(p);
/* For test triangle, choose one in the middle of patch list
- * as the ones near the beginning may be very near other patches.
- */
+ * as the ones near the beginning may be very near other patches. */
int test_t_index = patch.tri(patch.tot_tri() / 2);
Face &tri_test = *tm.face(test_t_index);
/* Assume all triangles in a patch are in the same shape. */
@@ -2444,8 +2464,10 @@ static IMesh gwn_boolean(const IMesh &tm,
return ans;
}
-/* Which CDT output edge index is for an edge between output verts
- * v1 and v2 (in either order)? Return -1 if none.
+/**
+ * Which CDT output edge index is for an edge between output verts
+ * v1 and v2 (in either order)?
+ * \return -1 if none.
*/
static int find_cdt_edge(const CDT_result<mpq_class> &cdt_out, int v1, int v2)
{
@@ -2458,12 +2480,13 @@ static int find_cdt_edge(const CDT_result<mpq_class> &cdt_out, int v1, int v2)
return -1;
}
-/* Tesselate face f into triangles and return an array of const Face *
+/**
+ * Tessellate face f into triangles and return an array of `const Face *`
* giving that triangulation.
* Care is taken so that the original edge index associated with
* each edge in the output triangles either matches the original edge
* for the (identical) edge of f, or else is -1. So diagonals added
- * for triangulation can later be indentified by having NO_INDEX for original.
+ * for triangulation can later be identified by having #NO_INDEX for original.
*/
static Array<Face *> triangulate_poly(Face *f, IMeshArena *arena)
{
@@ -2484,8 +2507,7 @@ static Array<Face *> triangulate_poly(Face *f, IMeshArena *arena)
/* If project down y axis as opposed to x or z, the orientation
* of the polygon will be reversed.
* Yet another reversal happens if the poly normal in the dominant
- * direction is opposite that of the positive dominant axis.
- */
+ * direction is opposite that of the positive dominant axis. */
bool rev1 = (axis == 1);
bool rev2 = poly_normal[axis] < 0;
bool rev = rev1 ^ rev2;
@@ -2533,10 +2555,11 @@ static Array<Face *> triangulate_poly(Face *f, IMeshArena *arena)
return ans;
}
-/* Return an IMesh that is a triangulation of a mesh with general
- * polygonal faces, imesh.
+/**
+ * Return an #IMesh that is a triangulation of a mesh with general
+ * polygonal faces, #imesh.
* Added diagonals will be distinguishable by having edge original
- * indices of NO_INDEX.
+ * indices of #NO_INDEX.
*/
static IMesh triangulate_polymesh(IMesh &imesh, IMeshArena *arena)
{
@@ -2544,7 +2567,7 @@ static IMesh triangulate_polymesh(IMesh &imesh, IMeshArena *arena)
constexpr int estimated_tris_per_face = 3;
face_tris.reserve(estimated_tris_per_face * imesh.face_size());
for (Face *f : imesh.faces()) {
- /* Tesselate face f, following plan similar to BM_face_calc_tesselation. */
+ /* Tessellate face f, following plan similar to #BM_face_calc_tesselation. */
int flen = f->size();
if (flen == 3) {
face_tris.append(f);
@@ -2573,8 +2596,9 @@ static IMesh triangulate_polymesh(IMesh &imesh, IMeshArena *arena)
return IMesh(face_tris);
}
-/* If tri1 and tri2 have a common edge (in opposite orientation), return the indices into tri1 and
- * tri2 where that common edge starts. Else return (-1,-1).
+/**
+ * If \a tri1 and \a tri2 have a common edge (in opposite orientation),
+ * return the indices into \a tri1 and \a tri2 where that common edge starts. Else return (-1,-1).
*/
static std::pair<int, int> find_tris_common_edge(const Face &tri1, const Face &tri2)
{
@@ -2589,18 +2613,19 @@ static std::pair<int, int> find_tris_common_edge(const Face &tri1, const Face &t
}
struct MergeEdge {
- /* Length (squared) of the edge, used for sorting. */
+ /** Length (squared) of the edge, used for sorting. */
double len_squared = 0.0;
- /* v1 and v2 are the ends of the edge, ordered so that v1->id < v2->id */
+ /* v1 and v2 are the ends of the edge, ordered so that `v1->id < v2->id` */
const Vert *v1 = nullptr;
const Vert *v2 = nullptr;
- /* left_face and right_face are indices into FaceMergeState->face. */
+ /* left_face and right_face are indices into #FaceMergeState.face. */
int left_face = -1;
int right_face = -1;
int orig = -1; /* An edge orig index that can be used for this edge. */
- /* Is it allowed to dissolve this edge? */
+ /** Is it allowed to dissolve this edge? */
bool dissolvable = false;
- bool is_intersect = false; /* Is this an intersect edge? */
+ /** Is this an intersect edge? */
+ bool is_intersect = false;
MergeEdge() = default;
@@ -2618,24 +2643,28 @@ struct MergeEdge {
};
struct MergeFace {
- /* The current sequence of Verts forming this face. */
+ /** The current sequence of Verts forming this face. */
Vector<const Vert *> vert;
- /* For each position in face, what is index in FaceMergeState of edge for that position? */
+ /** For each position in face, what is index in #FaceMergeState of edge for that position? */
Vector<int> edge;
- /* If not -1, merge_to gives a face index in FaceMergeState that this is merged to. */
+ /** If not -1, merge_to gives a face index in #FaceMergeState that this is merged to. */
int merge_to = -1;
- /* A face->orig that can be used for the merged face. */
+ /** A face->orig that can be used for the merged face. */
int orig = -1;
};
struct FaceMergeState {
- /* The faces being considered for merging. Some will already have been merge (merge_to != -1). */
+ /**
+ * The faces being considered for merging. Some will already have been merge (merge_to != -1).
+ */
Vector<MergeFace> face;
- /* The edges that are part of the faces in face[], together with current topological
+ /**
+ * The edges that are part of the faces in face[], together with current topological
* information (their left and right faces) and whether or not they are dissolvable.
*/
Vector<MergeEdge> edge;
- /* edge_map maps a pair of const Vert * ids (in canonical order: smaller id first)
- * to the index in the above edge vector in which to find the corresonding MergeEdge.
+ /**
+ * `edge_map` maps a pair of `const Vert *` ids (in canonical order: smaller id first)
+ * to the index in the above edge vector in which to find the corresponding #MergeEdge.
*/
Map<std::pair<int, int>, int> edge_map;
};
@@ -2663,8 +2692,9 @@ static std::ostream &operator<<(std::ostream &os, const FaceMergeState &fms)
return os;
}
-/* tris all have the same original face.
- * Find the 2d edge/tri topology for these triangles, but only the ones facing in the
+/**
+ * \a tris all have the same original face.
+ * Find the 2d edge/triangle topology for these triangles, but only the ones facing in the
* norm direction, and whether each edge is dissolvable or not.
*/
static void init_face_merge_state(FaceMergeState *fms,
@@ -2772,7 +2802,8 @@ static void init_face_merge_state(FaceMergeState *fms,
}
}
-/* To have a valid bmesh, there are constraints on what edges can be removed.
+/**
+ * To have a valid #BMesh, there are constraints on what edges can be removed.
* We cannot remove an edge if (a) it would create two disconnected boundary parts
* (which will happen if there's another edge sharing the same two faces);
* or (b) it would create a face with a repeated vertex.
@@ -2798,8 +2829,8 @@ static bool dissolve_leaves_valid_bmesh(FaceMergeState *fms,
}
}
/* Is there a vert in A, not me.v1 or me.v2, that is also in B?
- * One could avoid this O(n^2) algorithm if had a structure saying which faces a vertex touches.
- */
+ * One could avoid this O(n^2) algorithm if had a structure
+ * saying which faces a vertex touches. */
for (int a_v_index = 0; ok && a_v_index < alen; ++a_v_index) {
const Vert *a_v = mf_left.vert[a_v_index];
if (a_v != me.v1 && a_v != me.v2) {
@@ -2814,7 +2845,8 @@ static bool dissolve_leaves_valid_bmesh(FaceMergeState *fms,
return ok;
}
-/* mf_left and mf_right should share a MergeEdge me, having index me_index.
+/**
+ * mf_left and mf_right should share a #MergeEdge me, having index me_index.
* We change mf_left to remove edge me and insert the appropriate edges of
* mf_right in between the start and end vertices of that edge.
* We change the left face of the spliced-in edges to be mf_left's index.
@@ -2869,8 +2901,9 @@ static void splice_faces(
me.right_face = -1;
}
-/* Given that fms has been properly initialized to contain a set of faces that
- * together form a face or part of a face of the original IMesh, and that
+/**
+ * Given that fms has been properly initialized to contain a set of faces that
+ * together form a face or part of a face of the original #IMesh, and that
* it has properly recorded with faces are dissolvable, dissolve as many edges as possible.
* We try to dissolve in decreasing order of edge length, so that it is more likely
* that the final output doesn't have awkward looking long edges with extreme angles.
@@ -2919,13 +2952,14 @@ static void do_dissolve(FaceMergeState *fms)
}
}
-/* Given that tris form a triangulation of a face or part of a face that was in imesh_in,
+/**
+ * Given that \a tris form a triangulation of a face or part of a face that was in \a imesh_in,
* merge as many of the triangles together as possible, by dissolving the edges between them.
* We can only dissolve triangulation edges that don't overlap real input edges, and we
- * can only dissolve them if doing so leaves the remaining faces able to create valid BMesh.
+ * can only dissolve them if doing so leaves the remaining faces able to create valid #BMesh.
* We can tell edges that don't overlap real input edges because they will have an
- * "original edge" that is different from NO_INDEX.
- * Note: it is possible that some of the triangles in tris have reversed orientation
+ * "original edge" that is different from #NO_INDEX.
+ * \note it is possible that some of the triangles in \a tris have reversed orientation
* to the rest, so we have to handle the two cases separately.
*/
static Vector<Face *> merge_tris_for_face(Vector<int> tris,
@@ -2950,8 +2984,7 @@ static Vector<Face *> merge_tris_for_face(Vector<int> tris,
double3 second_tri_normal = tm.face(tris[1])->plane->norm;
if (tris.size() == 2 && double3::dot(first_tri_normal, second_tri_normal) > 0.0) {
/* Is this a case where quad with one diagonal remained unchanged?
- * Worth special handling because this case will be very common.
- */
+ * Worth special handling because this case will be very common. */
Face &tri1 = *tm.face(tris[0]);
Face &tri2 = *tm.face(tris[1]);
Face *in_face = imesh_in.face(tri1.orig);
@@ -3010,7 +3043,8 @@ static Vector<Face *> merge_tris_for_face(Vector<int> tris,
return ans;
}
-/* Return an array, paralleling imesh_out.vert, saying which vertices can be dissolved.
+/**
+ * Return an array, paralleling imesh_out.vert, saying which vertices can be dissolved.
* A vertex v can be dissolved if (a) it is not an input vertex; (b) it has valence 2;
* and (c) if v's two neighboring vertices are u and w, then (u,v,w) forms a straight line.
* Return the number of dissolvable vertices in r_count_dissolve.
@@ -3026,8 +3060,7 @@ static Array<bool> find_dissolve_verts(IMesh &imesh_out, int *r_count_dissolve)
}
/* neighbors[i] will be a pair giving the up-to-two neighboring vertices
* of the vertex v in position i of imesh_out.vert.
- * If we encounter a third, then v will not be dissolvable.
- */
+ * If we encounter a third, then v will not be dissolvable. */
Array<std::pair<const Vert *, const Vert *>> neighbors(
imesh_out.vert_size(), std::pair<const Vert *, const Vert *>(nullptr, nullptr));
for (int f : imesh_out.face_index_range()) {
@@ -3081,9 +3114,10 @@ static Array<bool> find_dissolve_verts(IMesh &imesh_out, int *r_count_dissolve)
return dissolve;
}
-/* The dissolve array parallels the imesh.vert array. Wherever it is true,
+/**
+ * The dissolve array parallels the `imesh.vert` array. Wherever it is true,
* remove the corresponding vertex from the vertices in the faces of
- * imesh.faces to account for the close-up of the gaps in imesh.vert.
+ * `imesh.faces` to account for the close-up of the gaps in `imesh.vert`.
*/
static void dissolve_verts(IMesh *imesh, const Array<bool> dissolve, IMeshArena *arena)
{
@@ -3111,14 +3145,15 @@ static void dissolve_verts(IMesh *imesh, const Array<bool> dissolve, IMeshArena
imesh->set_dirty_verts();
}
-/* The main boolean function operates on a triangle IMesh and produces a
- * Triangle IMesh as output.
+/**
+ * The main boolean function operates on a triangle #IMesh and produces a
+ * Triangle #IMesh as output.
* This function converts back into a general polygonal mesh by removing
* any possible triangulation edges (which can be identified because they
* will have an original edge that is NO_INDEX.
* Not all triangulation edges can be removed: if they ended up non-trivially overlapping a real
* input edge, then we need to keep it. Also, some are necessary to make the output satisfy
- * the "valid BMesh" property: we can't produce output faces that have repeated vertices in them,
+ * the "valid #BMesh" property: we can't produce output faces that have repeated vertices in them,
* or have several disconnected boundaries (e.g., faces with holes).
*/
static IMesh polymesh_from_trimesh_with_dissolve(const IMesh &tm_out,
@@ -3135,8 +3170,7 @@ static IMesh polymesh_from_trimesh_with_dissolve(const IMesh &tm_out,
}
/* Gather all output triangles that are part of each input face.
* face_output_tris[f] will be indices of triangles in tm_out
- * that have f as their original face.
- */
+ * that have f as their original face. */
int tot_in_face = imesh_in.face_size();
Array<Vector<int>> face_output_tris(tot_in_face);
for (int t : tm_out.face_index_range()) {
@@ -3153,8 +3187,7 @@ static IMesh polymesh_from_trimesh_with_dissolve(const IMesh &tm_out,
/* Merge triangles that we can from face_output_tri to make faces for output.
* face_output_face[f] will be new original const Face *'s that
- * make up whatever part of the boolean output remains of input face f.
- */
+ * make up whatever part of the boolean output remains of input face f. */
Array<Vector<Face *>> face_output_face(tot_in_face);
int tot_out_face = 0;
for (int in_f : imesh_in.face_index_range()) {
@@ -3180,8 +3213,7 @@ static IMesh polymesh_from_trimesh_with_dissolve(const IMesh &tm_out,
IMesh imesh_out(face);
/* Dissolve vertices that were (a) not original; and (b) now have valence 2 and
* are between two other vertices that are exactly in line with them.
- * These were created because of triangulation edges that have been dissolved.
- */
+ * These were created because of triangulation edges that have been dissolved. */
int count_dissolve;
Array<bool> v_dissolve = find_dissolve_verts(imesh_out, &count_dissolve);
if (count_dissolve > 0) {
@@ -3194,11 +3226,11 @@ static IMesh polymesh_from_trimesh_with_dissolve(const IMesh &tm_out,
return imesh_out;
}
-/*
+/**
* This function does a boolean operation on a TriMesh with nshapes inputs.
* All the shapes are combined in tm_in.
* The shape_fn function should take a triangle index in tm_in and return
- * a number in the range 0 to nshapes-1, to say which shape that triangle is in.
+ * a number in the range 0 to `nshapes-1`, to say which shape that triangle is in.
*/
IMesh boolean_trimesh(IMesh &tm_in,
BoolOpType op,
@@ -3296,7 +3328,8 @@ static void dump_test_spec(IMesh &imesh)
}
}
-/* Do the boolean operation op on the polygon mesh imesh_in.
+/**
+ * Do the boolean operation op on the polygon mesh imesh_in.
* See the header file for a complete description.
*/
IMesh boolean_mesh(IMesh &imesh,
diff --git a/source/blender/blenlib/intern/mesh_intersect.cc b/source/blender/blenlib/intern/mesh_intersect.cc
index 8e4f95e89cb..0c1c77e1c49 100644
--- a/source/blender/blenlib/intern/mesh_intersect.cc
+++ b/source/blender/blenlib/intern/mesh_intersect.cc
@@ -14,7 +14,11 @@
* Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
*/
-/* The blender::meshintersect API needs GMP. */
+/** \file
+ * \ingroup bli
+ */
+
+/* The #blender::meshintersect API needs GMP. */
#ifdef WITH_GMP
# include <algorithm>
@@ -55,7 +59,7 @@ static void doperfmax(int maxnum, int val);
static void dump_perfdata(void);
# endif
-/* For debugging, can disable threading in intersect code with this static constant. */
+/** For debugging, can disable threading in intersect code with this static constant. */
static constexpr bool intersect_use_threading = true;
Vert::Vert(const mpq3 &mco, const double3 &dco, int id, int orig)
@@ -127,7 +131,7 @@ Plane::Plane(const double3 &norm, const double d) : norm(norm), d(d)
norm_exact = mpq3(0, 0, 0); /* Marks as "exact not yet populated". */
}
-/* This is wrong for degenerate planes, but we don't expect to call it on those. */
+/** This is wrong for degenerate planes, but we don't expect to call it on those. */
bool Plane::exact_populated() const
{
return norm_exact[0] != 0 || norm_exact[1] != 0 || norm_exact[2] != 0;
@@ -219,8 +223,7 @@ bool Face::operator==(const Face &other) const
}
for (FacePos i : index_range()) {
/* Can test pointer equality since we will have
- * unique vert pointers for unique co_equal's.
- */
+ * unique vert pointers for unique co_equal's. */
if (this->vert[i] != other.vert[i]) {
return false;
}
@@ -282,25 +285,27 @@ std::ostream &operator<<(std::ostream &os, const Face *f)
return os;
}
-/* IMeshArena is the owner of the Vert and Face resources used
- * during a run of one of the meshintersect main functions.
- * It also keeps has a hash table of all Verts created so that it can
- * ensure that only one instance of a Vert with a given co_exact will
- * exist. I.e., it dedups the vertices.
- */
-
-/* Uncomment the following to try using a spinlock instead of
+/**
+ * Un-comment the following to try using a spin-lock instead of
* a mutex in the arena allocation routines.
* Initial tests showed that it doesn't seem to help very much,
- * if at all, to use a spinlock.
+ * if at all, to use a spin-lock.
*/
// #define USE_SPINLOCK
+/**
+ * #IMeshArena is the owner of the Vert and Face resources used
+ * during a run of one of the mesh-intersect main functions.
+ * It also keeps has a hash table of all Verts created so that it can
+ * ensure that only one instance of a Vert with a given co_exact will
+ * exist. I.e., it de-duplicates the vertices.
+ */
class IMeshArena::IMeshArenaImpl : NonCopyable, NonMovable {
- /* Don't use Vert itself as key since resizing may move
+ /**
+ * Don't use Vert itself as key since resizing may move
* pointers to the Vert around, and we need to have those pointers
- * stay the same throughout the lifetime of the IMeshArena.
+ * stay the same throughout the lifetime of the #IMeshArena.
*/
struct VSetKey {
Vert *vert;
@@ -322,8 +327,11 @@ class IMeshArena::IMeshArenaImpl : NonCopyable, NonMovable {
VectorSet<VSetKey> vset_; /* TODO: replace with Set */
- /* Ownership of the Vert memory is here, so destroying this reclaims that memory. */
- /* TODO: replace these with pooled allocation, and just destory the pools at the end. */
+ /**
+ * Ownership of the Vert memory is here, so destroying this reclaims that memory.
+ *
+ * TODO: replace these with pooled allocation, and just destroy the pools at the end.
+ */
Vector<std::unique_ptr<Vert>> allocated_verts_;
Vector<std::unique_ptr<Face>> allocated_faces_;
@@ -331,7 +339,7 @@ class IMeshArena::IMeshArenaImpl : NonCopyable, NonMovable {
int next_vert_id_ = 0;
int next_face_id_ = 0;
- /* Need a lock when multithreading to protect allocation of new elements. */
+ /* Need a lock when multi-threading to protect allocation of new elements. */
# ifdef USE_SPINLOCK
SpinLock lock_;
# else
@@ -452,7 +460,8 @@ class IMeshArena::IMeshArenaImpl : NonCopyable, NonMovable {
return ans;
}
- /* This is slow. Only used for unit tests right now.
+ /**
+ * This is slow. Only used for unit tests right now.
* Since it is only used for that purpose, access is not lock-protected.
* The argument vs can be a cyclic shift of the actual stored Face.
*/
@@ -491,13 +500,11 @@ class IMeshArena::IMeshArenaImpl : NonCopyable, NonMovable {
ans = vskey.vert;
}
else {
- /* It was a dup, so return the existing one.
+ /* It was a duplicate, so return the existing one.
* Note that the returned Vert may have a different orig.
* This is the intended semantics: if the Vert already
* exists then we are merging verts and using the first-seen
- * one as the canonical one.
- */
-
+ * one as the canonical one. */
ans = vset_[i].vert;
}
if (intersect_use_threading) {
@@ -587,8 +594,7 @@ int IMesh::lookup_vert(const Vert *v) const
void IMesh::populate_vert()
{
/* This is likely an overestimate, since verts are shared between
- * faces. It is ok if estimate is over or even under.
- */
+ * faces. It is ok if estimate is over or even under. */
constexpr int ESTIMATE_VERTS_PER_FACE = 4;
int estimate_num_verts = ESTIMATE_VERTS_PER_FACE * face_.size();
populate_vert(estimate_num_verts);
@@ -621,8 +627,7 @@ void IMesh::populate_vert(int max_verts)
}
/* Easier debugging (at least when there are no merged input verts)
* if output vert order is same as input, with new verts at the end.
- * TODO: when all debugged, set fix_order = false.
- */
+ * TODO: when all debugged, set fix_order = false. */
const bool fix_order = true;
if (fix_order) {
std::sort(vert_.begin(), vert_.end(), [](const Vert *a, const Vert *b) {
@@ -776,7 +781,8 @@ struct BoundingBox {
}
};
-/* Assume bounding boxes have been expanded by a sufficient epislon on all sides
+/**
+ * Assume bounding boxes have been expanded by a sufficient epsilon on all sides
* so that the comparisons against the bb bounds are sufficient to guarantee that
* if an overlap or even touching could happen, this will return true.
*/
@@ -785,7 +791,8 @@ static bool bbs_might_intersect(const BoundingBox &bb_a, const BoundingBox &bb_b
return isect_aabb_aabb_v3(bb_a.min, bb_a.max, bb_b.min, bb_b.max);
}
-/* Data and functions to calculate bounding boxes and pad them, in parallel.
+/**
+ * Data and functions to calculate bounding boxes and pad them, in parallel.
* The bounding box calculation has the additional task of calculating the maximum
* absolute value of any coordinate in the mesh, which will be used to calculate
* the pad value.
@@ -843,7 +850,8 @@ static void calc_face_bb_reduce(const void *__restrict UNUSED(userdata),
bbchunk_join->max_abs_val = max_dd(bbchunk_join->max_abs_val, bbchunk->max_abs_val);
}
-/* We will expand the bounding boxes by an epsilon on all sides so that
+/**
+ * We will expand the bounding boxes by an epsilon on all sides so that
* the "less than" tests in isect_aabb_aabb_v3 are sufficient to detect
* touching or overlap.
*/
@@ -874,12 +882,13 @@ static Array<BoundingBox> calc_face_bounding_boxes(const IMesh &m)
return ans;
}
-/* A cluster of coplanar triangles, by index.
- * A pair of triangles T0 and T1 is said to "nontrivially coplanar-intersect"
- * if they are coplanar, intersect, and their intersection is not just existing
+/**
+ * A cluster of co-planar triangles, by index.
+ * A pair of triangles T0 and T1 is said to "non-trivially co-planar-intersect"
+ * if they are co-planar, intersect, and their intersection is not just existing
* elements (verts, edges) of both triangles.
- * A coplanar cluster is said to be "nontrivial" if it has more than one triangle
- * and every triangle in it nontrivially coplanar-intersects with at least one other
+ * A co-planar cluster is said to be "nontrivial" if it has more than one triangle
+ * and every triangle in it non-trivially co-planar-intersects with at least one other
* triangle in the cluster.
*/
class CoplanarCluster {
@@ -944,10 +953,11 @@ class CoplanarCluster {
}
};
-/* Maintains indexed set of CoplanarCluster, with the added ability
+/**
+ * Maintains indexed set of #CoplanarCluster, with the added ability
* to efficiently find the cluster index of any given triangle
* (the max triangle index needs to be given in the initializer).
- * The tri_cluster(t) function returns -1 if t is not part of any cluster.
+ * The #tri_cluster(t) function returns -1 if t is not part of any cluster.
*/
class CoplanarClusterInfo {
Vector<CoplanarCluster> clusters_;
@@ -1067,7 +1077,8 @@ struct ITT_value {
static std::ostream &operator<<(std::ostream &os, const ITT_value &itt);
-/* Project a 3d vert to a 2d one by eliding proj_axis. This does not create
+/**
+ * Project a 3d vert to a 2d one by eliding proj_axis. This does not create
* degeneracies as long as the projection axis is one where the corresponding
* component of the originating plane normal is non-zero.
*/
@@ -1096,11 +1107,12 @@ static mpq2 project_3d_to_2d(const mpq3 &p3d, int proj_axis)
return p2d;
}
-/* Is a point in the interior of a 2d triangle or on one of its
+/**
+ Is a point in the interior of a 2d triangle or on one of its
* edges but not either endpoint of the edge?
* orient[pi][i] is the orientation test of the point pi against
* the side of the triangle starting at index i.
- * Assume the triangele is non-degenerate and CCW-oriented.
+ * Assume the triangle is non-degenerate and CCW-oriented.
* Then answer is true if p is left of or on all three of triangle a's edges,
* and strictly left of at least on of them.
*/
@@ -1113,9 +1125,10 @@ static bool non_trivially_2d_point_in_tri(const int orients[3][3], int pi)
(p_left_01 + p_left_12 + p_left_20) >= 2);
}
-/* Given orients as defined in non_trivially_2d_intersect, do the triangles
+/**
+ * Given orients as defined in non_trivially_2d_intersect, do the triangles
* overlap in a "hex" pattern? That is, the overlap region is a hexagon, which
- * one gets by having, each point of one triangle being strictly rightof one
+ * one gets by having, each point of one triangle being strictly right-of one
* edge of the other and strictly left of the other two edges; and vice versa.
*/
static bool non_trivially_2d_hex_overlap(int orients[2][3][3])
@@ -1132,10 +1145,11 @@ static bool non_trivially_2d_hex_overlap(int orients[2][3][3])
return true;
}
-/* Given orients as defined in non_trivially_2d_intersect, do the triangles
+/**
+ * Given orients as defined in non_trivially_2d_intersect, do the triangles
* have one shared edge in a "folded-over" configuration?
* As well as a shared edge, the third vertex of one triangle needs to be
- * rightof one and leftof the other two edges of the other triangle.
+ * right-of one and left-of the other two edges of the other triangle.
*/
static bool non_trivially_2d_shared_edge_overlap(int orients[2][3][3],
const mpq2 *a[3],
@@ -1149,10 +1163,9 @@ static bool non_trivially_2d_shared_edge_overlap(int orients[2][3][3],
int jnn = (j + 2) % 3;
if (*a[i] == *b[j] && *a[in] == *b[jn]) {
/* Edge from a[i] is shared with edge from b[j]. */
- /* See if a[inn] is rightof or on one of the other edges of b.
- * If it is on, then it has to be rightof or leftof the shared edge,
- * depending on which edge it is.
- */
+ /* See if a[inn] is right-of or on one of the other edges of b.
+ * If it is on, then it has to be right-of or left-of the shared edge,
+ * depending on which edge it is. */
if (orients[0][inn][jn] < 0 || orients[0][inn][jnn] < 0) {
return true;
}
@@ -1162,7 +1175,7 @@ static bool non_trivially_2d_shared_edge_overlap(int orients[2][3][3],
if (orients[0][inn][jnn] == 0 && orients[0][inn][j] == -1) {
return true;
}
- /* Similarly for b[jnn]. */
+ /* Similarly for `b[jnn]`. */
if (orients[1][jnn][in] < 0 || orients[1][jnn][inn] < 0) {
return true;
}
@@ -1178,7 +1191,9 @@ static bool non_trivially_2d_shared_edge_overlap(int orients[2][3][3],
return false;
}
-/* Are the triangles the same, perhaps with some permutation of vertices? */
+/**
+ * Are the triangles the same, perhaps with some permutation of vertices?
+ */
static bool same_triangles(const mpq2 *a[3], const mpq2 *b[3])
{
for (int i = 0; i < 3; ++i) {
@@ -1189,19 +1204,19 @@ static bool same_triangles(const mpq2 *a[3], const mpq2 *b[3])
return false;
}
-/* Do 2d triangles (a[0], a[1], a[2]) and (b[0], b[1], b2[2]) intersect at more than just shared
- * vertices or a shared edge? This is true if any point of one tri is non-trivially inside the
+/**
+ * Do 2d triangles (a[0], a[1], a[2]) and (b[0], b[1], b2[2]) intersect at more than just shared
+ * vertices or a shared edge? This is true if any point of one triangle is non-trivially inside the
* other. NO: that isn't quite sufficient: there is also the case where the verts are all mutually
* outside the other's triangle, but there is a hexagonal overlap region where they overlap.
*/
static bool non_trivially_2d_intersect(const mpq2 *a[3], const mpq2 *b[3])
{
/* TODO: Could experiment with trying bounding box tests before these.
- * TODO: Find a less expensive way than 18 orient tests to do this.
- */
- /* orients[0][ai][bi] is orient of point a[ai] compared to seg starting at b[bi].
- * orients[1][bi][ai] is orient of point b[bi] compared to seg starting at a[ai].
- */
+ * TODO: Find a less expensive way than 18 orient tests to do this. */
+
+ /* `orients[0][ai][bi]` is orient of point `a[ai]` compared to segment starting at `b[bi]`.
+ * `orients[1][bi][ai]` is orient of point `b[bi]` compared to segment starting at `a[ai]`. */
int orients[2][3][3];
for (int ab = 0; ab < 2; ++ab) {
for (int ai = 0; ai < 3; ++ai) {
@@ -1225,8 +1240,9 @@ static bool non_trivially_2d_intersect(const mpq2 *a[3], const mpq2 *b[3])
return true;
}
-/* Does triangle t in tm non-trivially non-coplanar intersect any triangle
- * in CoplanarCluster cl? Assume t is known to be in the same plane as all
+/**
+ * Does triangle t in tm non-trivially non-co-planar intersect any triangle
+ * in `CoplanarCluster cl`? Assume t is known to be in the same plane as all
* the triangles in cl, and that proj_axis is a good axis to project down
* to solve this problem in 2d.
*/
@@ -1267,9 +1283,10 @@ static bool non_trivially_coplanar_intersects(const IMesh &tm,
* trivial intersects are found before calling intersect_tri_tri now.
*/
# if 0
-/* Do tri1 and tri2 intersect at all, and if so, is the intersection
+/**
+ * Do tri1 and tri2 intersect at all, and if so, is the intersection
* something other than a common vertex or a common edge?
- * The itt value is the result of calling intersect_tri_tri on tri1, tri2.
+ * The \a itt value is the result of calling intersect_tri_tri on tri1, tri2.
*/
static bool non_trivial_intersect(const ITT_value &itt, const Face * tri1, const Face * tri2)
{
@@ -1327,7 +1344,8 @@ static bool non_trivial_intersect(const ITT_value &itt, const Face * tri1, const
}
# endif
-/* The sup and index functions are defined in the paper:
+/**
+ * The sup and index functions are defined in the paper:
* EXACT GEOMETRIC COMPUTATION USING CASCADING, by
* Burnikel, Funke, and Seel. They are used to find absolute
* bounds on the error due to doing a calculation in double
@@ -1356,24 +1374,23 @@ static bool non_trivial_intersect(const ITT_value &itt, const Face * tri1, const
* be calculated ahead of time. The global max could be passed
* from above.
*/
-
static double supremum_dot_cross(const double3 &a, const double3 &b)
{
double3 abs_a = double3::abs(a);
double3 abs_b = double3::abs(b);
double3 c;
- /* This is dot(cross(a, b), cross(a,b)) but using absoluate values for a and b
- * and always using + when operation is + or -.
- */
+ /* This is dot(cross(a, b), cross(a,b)) but using absolute values for a and b
+ * and always using + when operation is + or -. */
c[0] = abs_a[1] * abs_b[2] + abs_a[2] * abs_b[1];
c[1] = abs_a[2] * abs_b[0] + abs_a[0] * abs_b[2];
c[2] = abs_a[0] * abs_b[1] + abs_a[1] * abs_b[0];
return double3::dot(c, c);
}
-/* Used with supremum to get error bound. See Burnikel et al paper.
+/**
+ * Used with supremum to get error bound. See Burnikel et al paper.
* index_plane_coord is the index of a plane coordinate calculated
- * for a triangle using the usual formuala, assuming the input
+ * for a triangle using the usual formula, assuming the input
* coordinates have index 1.
* index_cross is the index of each coordinate of the cross product.
* It is actually 2 + 2 * (max index of input coords).
@@ -1427,10 +1444,11 @@ static double supremum_orient3d(const double3 &a,
return det;
}
-/* Actually index_orient3d = 10 + 4 * (max degree of input coordinates) */
+/** Actually index_orient3d = 10 + 4 * (max degree of input coordinates) */
constexpr int index_orient3d = 14;
-/* Return the approximate orient3d of the four double3's, with
+/**
+ * Return the approximate orient3d of the four double3's, with
* the guarantee that if the value is -1 or 1 then the underlying
* mpq3 test would also have returned that value.
* When the return value is 0, we are not sure of the sign.
@@ -1448,7 +1466,8 @@ static int filter_orient3d(const double3 &a, const double3 &b, const double3 &c,
return 0;
}
-/* Return the approximate orient3d of the tri plane points and v, with
+/**
+ * Return the approximate orient3d of the triangle plane points and v, with
* the guarantee that if the value is -1 or 1 then the underlying
* mpq3 test would also have returned that value.
* When the return value is 0, we are not sure of the sign.
@@ -1458,7 +1477,8 @@ static int filter_tri_plane_vert_orient3d(const Face &tri, const Vert *v)
return filter_orient3d(tri[0]->co, tri[1]->co, tri[2]->co, v->co);
}
-/* Are vectors a and b parallel or nearly parallel?
+/**
+ * Are vectors a and b parallel or nearly parallel?
* This routine should only return false if we are certain
* that they are not parallel, taking into account the
* possible numeric errors and input value approximation.
@@ -1477,7 +1497,8 @@ static bool near_parallel_vecs(const double3 &a, const double3 &b)
return true;
}
-/* Return true if we are sure that dot(a,b) > 0, taking into
+/**
+ * Return true if we are sure that dot(a,b) > 0, taking into
* account the error bounds due to numeric errors and input value
* approximation.
*/
@@ -1494,13 +1515,14 @@ static bool dot_must_be_positive(const double3 &a, const double3 &b)
return false;
}
-/* Return the approximate side of point p on a plane with normal plane_no and point plane_p.
+/**
+ * Return the approximate side of point p on a plane with normal plane_no and point plane_p.
* The answer will be 1 if p is definitely above the plane, -1 if it is definitely below.
* If the answer is 0, we are unsure about which side of the plane (or if it is on the plane).
- * In exact arithmetic, the answer is just sgn(dot(p - plane_p, plane_no)).
+ * In exact arithmetic, the answer is just `sgn(dot(p - plane_p, plane_no))`.
+ *
+ * The plane_no input is constructed, so has a higher index.
*/
-
-/* The plane_no input is constructed, so has a higher index. */
constexpr int index_plane_side = 3 + 2 * index_dot_plane_coords;
static int filter_plane_side(const double3 &p,
@@ -1522,11 +1544,12 @@ static int filter_plane_side(const double3 &p,
return 0;
}
-/* A fast, non-exhaustive test for non_trivial intersection.
+/**
+ * A fast, non-exhaustive test for non_trivial intersection.
* If this returns false then we are sure that tri1 and tri2
* do not intersect. If it returns true, they may or may not
* non-trivially intersect.
- * We assume that boundinb box overlap tests have already been
+ * We assume that bounding box overlap tests have already been
* done, so don't repeat those here. This routine is checking
* for the very common cases (when doing mesh self-intersect)
* where triangles share an edge or a vertex, but don't
@@ -1553,15 +1576,13 @@ static bool may_non_trivially_intersect(Face *t1, Face *t2)
}
if (n_shared == 2) {
/* t1 and t2 share an entire edge.
- * If their normals are not parallel, they cannot non-trivially intersect.
- */
+ * If their normals are not parallel, they cannot non-trivially intersect. */
if (!near_parallel_vecs(tri1.plane->norm, tri2.plane->norm)) {
return false;
}
/* The normals are parallel or nearly parallel.
* If the normals are in the same direction and the edges have opposite
- * directions in the two triangles, they cannot non-trivially intersect.
- */
+ * directions in the two triangles, they cannot non-trivially intersect. */
bool erev1 = tri1.prev_pos(share1_pos[0]) == share1_pos[1];
bool erev2 = tri2.prev_pos(share2_pos[0]) == share2_pos[1];
if (erev1 != erev2) {
@@ -1575,8 +1596,7 @@ static bool may_non_trivially_intersect(Face *t1, Face *t2)
* If the two non-shared verts of t2 are both on the same
* side of tri1's plane, then they cannot non-trivially intersect.
* (There are some other cases that could be caught here but
- * they are more expensive to check).
- */
+ * they are more expensive to check). */
Face::FacePos p = share2_pos[0];
const Vert *v2a = p == 0 ? tri2[1] : tri2[0];
const Vert *v2b = (p == 0 || p == 1) ? tri2[2] : tri2[1];
@@ -1606,7 +1626,8 @@ static bool may_non_trivially_intersect(Face *t1, Face *t2)
* github.com/erich666/jgt-code/tree/master/Volume_08/Number_1/Guigue2003
*/
-/* Return the point on ab where the plane with normal n containing point c intersects it.
+/**
+ * Return the point on ab where the plane with normal n containing point c intersects it.
* Assumes ab is not perpendicular to n.
* This works because the ratio of the projections of ab and ac onto n is the same as
* the ratio along the line ab of the intersection point to the whole of ab.
@@ -1620,9 +1641,10 @@ static inline mpq3 tti_interp(const mpq3 &a, const mpq3 &b, const mpq3 &c, const
return a - alpha * ab;
}
-/* Return +1, 0, -1 as a + ad is above, on, or below the oriented plane containing a, b, c in CCW
+/**
+ * Return +1, 0, -1 as a + ad is above, on, or below the oriented plane containing a, b, c in CCW
* order. This is the same as -oriented(a, b, c, a + ad), but uses fewer arithmetic operations.
- * TODO: change arguments to const Vert * and use floating filters.
+ * TODO: change arguments to `const Vert *` and use floating filters.
*/
static inline int tti_above(const mpq3 &a, const mpq3 &b, const mpq3 &c, const mpq3 &ad)
{
@@ -1630,7 +1652,8 @@ static inline int tti_above(const mpq3 &a, const mpq3 &b, const mpq3 &c, const m
return sgn(mpq3::dot(ad, n));
}
-/* Given that triangles (p1, q1, r1) and (p2, q2, r2) are in canonical order,
+/**
+ * Given that triangles (p1, q1, r1) and (p2, q2, r2) are in canonical order,
* use the classification chart in the Guigue and Devillers paper to find out
* how the intervals [i,j] and [k,l] overlap, where [i,j] is where p1r1 and p1q1
* intersect the plane-plane intersection line, L, and [k,l] is where p2q2 and p2r2
@@ -1728,7 +1751,7 @@ static ITT_value itt_canon2(const mpq3 &p1,
if (dbg_level > 0) {
std::cout << "overlap [i [k j] l]\n";
}
- /* k is intersect with p2q2. j is intersect with p1q1. */
+ /* k is intersect with p2q2. j is intersect with p1q1. */
intersect_1 = tti_interp(p2, q2, p1, n1);
intersect_2 = tti_interp(p1, q1, p2, n2);
}
@@ -1801,7 +1824,7 @@ static ITT_value itt_canon1(const mpq3 &p1,
return itt_canon2(p1, r1, q1, r2, p2, q2, n1, n2);
}
if (dbg_level > 0) {
- std::cout << "triangles are coplanar\n";
+ std::cout << "triangles are co-planar\n";
}
return ITT_value(ICOPLANAR);
}
@@ -1835,8 +1858,7 @@ static ITT_value intersect_tri_tri(const IMesh &tm, int t1, int t2)
/* Try first getting signs with double arithmetic, with error bounds.
* If the signs calculated in this section are not 0, they are the same
- * as what they would be using exact arithmetic.
- */
+ * as what they would be using exact arithmetic. */
const double3 &d_p1 = vp1->co;
const double3 &d_q1 = vq1->co;
const double3 &d_r1 = vr1->co;
@@ -1909,7 +1931,7 @@ static ITT_value intersect_tri_tri(const IMesh &tm, int t1, int t2)
std::cout << "no intersection, all t1's verts above or below t2 (exact)\n";
}
# ifdef PERFDEBUG
- incperfcount(3); /* Tri tri interects decided by exact plane tests. */
+ incperfcount(3); /* Tri tri intersects decided by exact plane tests. */
# endif
return ITT_value(INONE);
}
@@ -1935,15 +1957,14 @@ static ITT_value intersect_tri_tri(const IMesh &tm, int t1, int t2)
std::cout << "no intersection, all t2's verts above or below t1 (exact)\n";
}
# ifdef PERFDEBUG
- incperfcount(3); /* Tri tri interects decided by exact plane tests. */
+ incperfcount(3); /* Tri tri intersects decided by exact plane tests. */
# endif
return ITT_value(INONE);
}
/* Do rest of the work with vertices in a canonical order, where p1 is on
- * postive side of plane and q1, r1 are not, or p1 is on the plane and
- * q1 and r1 are off the plane on the same side.
- */
+ * positive side of plane and q1, r1 are not, or p1 is on the plane and
+ * q1 and r1 are off the plane on the same side. */
ITT_value ans;
if (sp1 > 0) {
if (sq1 > 0) {
@@ -1993,7 +2014,7 @@ static ITT_value intersect_tri_tri(const IMesh &tm, int t1, int t2)
}
else {
if (dbg_level > 0) {
- std::cout << "triangles are coplanar\n";
+ std::cout << "triangles are co-planar\n";
}
ans = ITT_value(ICOPLANAR);
}
@@ -2016,13 +2037,18 @@ struct CDT_data {
Vector<mpq2> vert;
Vector<std::pair<int, int>> edge;
Vector<Vector<int>> face;
- Vector<int> input_face; /* Parallels face, gives id from input IMesh of input face. */
- Vector<bool> is_reversed; /* Parallels face, says if input face orientation is opposite. */
- CDT_result<mpq_class> cdt_out; /* Result of running CDT on input with (vert, edge, face). */
+ /** Parallels face, gives id from input #IMesh of input face. */
+ Vector<int> input_face;
+ /** Parallels face, says if input face orientation is opposite. */
+ Vector<bool> is_reversed;
+ /** Result of running CDT on input with (vert, edge, face). */
+ CDT_result<mpq_class> cdt_out;
int proj_axis;
};
-/* We could dedup verts here, but CDT routine will do that anyway. */
+/**
+ * We could de-duplicate verts here, but CDT routine will do that anyway.
+ */
static int prepare_need_vert(CDT_data &cd, const mpq3 &p3d)
{
mpq2 p2d = project_3d_to_2d(p3d, cd.proj_axis);
@@ -2030,7 +2056,8 @@ static int prepare_need_vert(CDT_data &cd, const mpq3 &p3d)
return v;
}
-/* To unproject a 2d vert that was projected along cd.proj_axis, we copy the coordinates
+/**
+ * To un-project a 2d vert that was projected along cd.proj_axis, we copy the coordinates
* from the two axes not involved in the projection, and use the plane equation of the
* originating 3d plane, cd.t_plane, to derive the coordinate of the projected axis.
* The plane equation says a point p is on the plane if dot(p, plane.n()) + plane.d() == 0.
@@ -2088,9 +2115,8 @@ static void prepare_need_tri(CDT_data &cd, const IMesh &tm, int t)
int v1 = prepare_need_vert(cd, tri[1]->co_exact);
int v2 = prepare_need_vert(cd, tri[2]->co_exact);
bool rev;
- /* How to get CCW orientation of projected tri? Note that when look down y axis
- * as opposed to x or z, the orientation of the other two axes is not right-and-up.
- */
+ /* How to get CCW orientation of projected triangle? Note that when look down y axis
+ * as opposed to x or z, the orientation of the other two axes is not right-and-up. */
BLI_assert(cd.t_plane->exact_populated());
if (tri.plane->norm_exact[cd.proj_axis] >= 0) {
rev = cd.proj_axis == 1;
@@ -2175,7 +2201,9 @@ static CDT_data prepare_cdt_input_for_cluster(const IMesh &tm,
return ans;
}
-/* Fills in cd.cdt_out with result of doing the cdt calculation on (vert, edge, face). */
+/**
+ * Fills in cd.cdt_out with result of doing the cdt calculation on (vert, edge, face).
+ */
static void do_cdt(CDT_data &cd)
{
constexpr int dbg_level = 0;
@@ -2246,16 +2274,14 @@ static int get_cdt_edge_orig(
if ((edge.first == i0 && edge.second == i1) || (edge.first == i1 && edge.second == i0)) {
/* Pick an arbitrary orig, but not one equal to NO_INDEX, if we can help it. */
/* TODO: if edge has origs from more than on part of the nary input,
- * then want to set *r_is_intersect to true.
- */
+ * then want to set *r_is_intersect to true. */
for (int orig_index : cd.cdt_out.edge_orig[e]) {
/* orig_index encodes the triangle and pos within the triangle of the input edge. */
if (orig_index >= foff) {
int in_face_index = (orig_index / foff) - 1;
int pos = orig_index % foff;
/* We need to retrieve the edge orig field from the Face used to populate the
- * in_face_index'th face of the CDT, at the pos'th position of the face.
- */
+ * in_face_index'th face of the CDT, at the pos'th position of the face. */
int in_tm_face_index = cd.input_face[in_face_index];
BLI_assert(in_tm_face_index < in_tm.face_size());
const Face *facep = in_tm.face(in_tm_face_index);
@@ -2268,13 +2294,11 @@ static int get_cdt_edge_orig(
}
else {
/* This edge came from an edge input to the CDT problem,
- * so it is an intersect edge.
- */
+ * so it is an intersect edge. */
*r_is_intersect = true;
/* TODO: maybe there is an orig index:
* This happens if an input edge was formed by an input face having
- * an edge that is coplanar with the cluster, while the face as a whole is not.
- */
+ * an edge that is co-planar with the cluster, while the face as a whole is not. */
return NO_INDEX;
}
}
@@ -2284,7 +2308,8 @@ static int get_cdt_edge_orig(
return NO_INDEX;
}
-/* Using the result of CDT in cd.cdt_out, extract an IMesh representing the subdivision
+/**
+ * Using the result of CDT in cd.cdt_out, extract an #IMesh representing the subdivision
* of input triangle t, which should be an element of cd.input_face.
*/
static IMesh extract_subdivided_tri(const CDT_data &cd,
@@ -2318,8 +2343,7 @@ static IMesh extract_subdivided_tri(const CDT_data &cd,
mpq3 v2co = unproject_cdt_vert(cd, cdt_out.vert[i2]);
/* No need to provide an original index: if coord matches
* an original one, then it will already be in the arena
- * with the correct orig field.
- */
+ * with the correct orig field. */
const Vert *v0 = arena->add_or_find_vert(v0co, NO_INDEX);
const Vert *v1 = arena->add_or_find_vert(v1co, NO_INDEX);
const Vert *v2 = arena->add_or_find_vert(v2co, NO_INDEX);
@@ -2391,8 +2415,7 @@ class TriOverlaps {
/* Tree type is 8 => octtree; axis = 6 => using XYZ axes only. */
tree_ = BLI_bvhtree_new(tm.face_size(), FLT_EPSILON, 8, 6);
/* In the common case of a binary boolean and no self intersection in
- * each shape, we will use two trees and simple bounding box overlap.
- */
+ * each shape, we will use two trees and simple bounding box overlap. */
bool two_trees_no_self = nshapes == 2 && !use_self;
if (two_trees_no_self) {
tree_b_ = BLI_bvhtree_new(tm.face_size(), FLT_EPSILON, 8, 6);
@@ -2428,8 +2451,7 @@ class TriOverlaps {
if (nshapes == 1 && use_self) {
/* Expect a lot of trivial intersects from quads that are triangulated
* and faces that share vertices.
- * Filter them out with a callback.
- */
+ * Filter them out with a callback. */
overlap_ = BLI_bvhtree_overlap(
tree_, tree_, &overlap_tot_, only_nontrivial_intersects, &cbdata);
}
@@ -2440,8 +2462,7 @@ class TriOverlaps {
}
/* The rest of the code is simpler and easier to parallelize if, in the two-trees case,
* we repeat the overlaps with indexA and indexB reversed. It is important that
- * in the repeated part, sorting will then bring things with indexB together.
- */
+ * in the repeated part, sorting will then bring things with indexB together. */
if (two_trees_no_self) {
overlap_ = static_cast<BVHTreeOverlap *>(
MEM_reallocN(overlap_, 2 * overlap_tot_ * sizeof(overlap_[0])));
@@ -2451,7 +2472,7 @@ class TriOverlaps {
}
overlap_tot_ += overlap_tot_;
}
- /* Sort the overlaps to bring all the intersects with a given indexA together. */
+ /* Sort the overlaps to bring all the intersects with a given indexA together. */
std::sort(overlap_, overlap_ + overlap_tot_, bvhtreeverlap_cmp);
if (dbg_level > 0) {
std::cout << overlap_tot_ << " overlaps found:\n";
@@ -2496,7 +2517,9 @@ class TriOverlaps {
}
};
-/* Data needed for parallelization of calc_overlap_itts. */
+/**
+ * Data needed for parallelization of #calc_overlap_itts.
+ */
struct OverlapIttsData {
Vector<std::pair<int, int>> intersect_pairs;
Map<std::pair<int, int>, ITT_value> &itt_map;
@@ -2509,7 +2532,8 @@ struct OverlapIttsData {
}
};
-/* Return a std::pair containing a and b in canonical order:
+/**
+ * Return a std::pair containing a and b in canonical order:
* With a <= b.
*/
static std::pair<int, int> canon_int_pair(int a, int b)
@@ -2540,9 +2564,10 @@ static void calc_overlap_itts_range_func(void *__restrict userdata,
data->itt_map.add_overwrite(tri_pair, itt);
}
-/* Fill in itt_map with the vector of ITT_values that result from intersecting the triangles in ov.
+/**
+ * Fill in itt_map with the vector of ITT_values that result from intersecting the triangles in ov.
* Use a canonical order for triangles: (a,b) where a < b.
- * Don't bother doing this if both a and b are part of the same coplanar cluster, as the
+ * Don't bother doing this if both a and b are part of the same co-planar cluster, as the
* intersection for those will be handled by CDT, later.
*/
static void calc_overlap_itts(Map<std::pair<int, int>, ITT_value> &itt_map,
@@ -2552,9 +2577,9 @@ static void calc_overlap_itts(Map<std::pair<int, int>, ITT_value> &itt_map,
IMeshArena *arena)
{
OverlapIttsData data(itt_map, tm, arena);
- /* Put dummy values in itt_map intially, so map entries will exist when doing the range function.
- * This means we won't have to protect the itt_map.add_overwrite function with a lock.
- */
+ /* Put dummy values in `itt_map` initially,
+ * so map entries will exist when doing the range function.
+ * This means we won't have to protect the `itt_map.add_overwrite` function with a lock. */
for (const BVHTreeOverlap &olap : ov.overlap()) {
std::pair<int, int> key = canon_int_pair(olap.indexA, olap.indexB);
if (!itt_map.contains(key)) {
@@ -2574,8 +2599,9 @@ static void calc_overlap_itts(Map<std::pair<int, int>, ITT_value> &itt_map,
BLI_task_parallel_range(0, tot_intersect_pairs, &data, calc_overlap_itts_range_func, &settings);
}
-/* Data needed for parallelization of calc_subdivided_tris. */
-
+/**
+ * Data needed for parallelization of calc_subdivided_tris.
+ */
struct OverlapTriRange {
int tri_index;
int overlap_start;
@@ -2588,11 +2614,10 @@ struct SubdivideTrisData {
Span<BVHTreeOverlap> overlap;
IMeshArena *arena;
- /* This vector gives, for each tri in tm that has an intersection
- * we want to calculate: what the index of that tri in tm is,
+ /* This vector gives, for each triangle in tm that has an intersection
+ * we want to calculate: what the index of that triangle in tm is,
* where it starts in the ov structure as indexA, and how many
- * overlap pairs have that same indexA (they will be continguous).
- */
+ * overlap pairs have that same indexA (they will be continuous). */
Vector<OverlapTriRange> overlap_tri_range;
SubdivideTrisData(Array<IMesh> &r_tri_subdivided,
@@ -2648,7 +2673,8 @@ static void calc_subdivided_tri_range_func(void *__restrict userdata,
}
}
-/* For each triangle in tm, fill in the corresponding slot in
+/**
+ * For each triangle in tm, fill in the corresponding slot in
* r_tri_subdivided with the result of intersecting it with
* all the other triangles in the mesh, if it intersects any others.
* But don't do this for triangles that are part of a cluster.
@@ -2679,8 +2705,7 @@ static void calc_subdivided_tris(Array<IMesh> &r_tri_subdivided,
}
/* Now overlap[overlap_index] to overlap[i] have indexA == t.
* We only record ranges for triangles that are not in clusters,
- * because the ones in clusters are handled separately.
- */
+ * because the ones in clusters are handled separately. */
if (clinfo.tri_cluster(t) == NO_INDEX) {
int len = i - overlap_index + 1;
if (!(len == 1 && overlap[overlap_index].indexB == t)) {
@@ -2735,9 +2760,8 @@ static CDT_data calc_cluster_subdivided(const CoplanarClusterInfo &clinfo,
std::cout << "CALC_CLUSTER_SUBDIVIDED for cluster " << c << " = " << cl << "\n";
}
/* Get vector itts of all intersections of a triangle of cl with any triangle of tm not
- * in cl and not coplanar with it (for that latter, if there were an intersection,
- * it should already be in cluster cl).
- */
+ * in cl and not co-planar with it (for that latter, if there were an intersection,
+ * it should already be in cluster cl). */
Vector<ITT_value> itts;
Span<BVHTreeOverlap> ovspan = ov.overlap();
for (int t : cl) {
@@ -2796,17 +2820,15 @@ static CoplanarClusterInfo find_clusters(const IMesh &tm, const Array<BoundingBo
std::cout << "FIND_CLUSTERS\n";
}
CoplanarClusterInfo ans(tm.face_size());
- /* There can be more than one CoplanarCluster per plane. Accumulate them in
+ /* There can be more than one #CoplanarCluster per plane. Accumulate them in
* a Vector. We will have to merge some elements of the Vector as we discover
- * triangles that form intersection bridges between two or more clusters.
- */
+ * triangles that form intersection bridges between two or more clusters. */
Map<Plane, Vector<CoplanarCluster>> plane_cls;
plane_cls.reserve(tm.face_size());
for (int t : tm.face_index_range()) {
/* Use a canonical version of the plane for map index.
* We can't just store the canonical version in the face
- * since canonicalizing loses the orientation of the normal.
- */
+ * since canonicalizing loses the orientation of the normal. */
Plane tplane = *tm.face(t)->plane;
BLI_assert(tplane.exact_populated());
tplane.make_canonical();
@@ -2820,7 +2842,7 @@ static CoplanarClusterInfo find_clusters(const IMesh &tm, const Array<BoundingBo
std::cout << "already has " << curcls.size() << " clusters\n";
}
int proj_axis = mpq3::dominant_axis(tplane.norm_exact);
- /* Paritition curcls into those that intersect t non-trivially, and those that don't. */
+ /* Partition `curcls` into those that intersect t non-trivially, and those that don't. */
Vector<CoplanarCluster *> int_cls;
Vector<CoplanarCluster *> no_int_cls;
for (CoplanarCluster &cl : curcls) {
@@ -2854,8 +2876,7 @@ static CoplanarClusterInfo find_clusters(const IMesh &tm, const Array<BoundingBo
}
else {
/* t intersections 2 or more existing clusters: need to merge them and replace all the
- * originals with the merged one in curcls.
- */
+ * originals with the merged one in `curcls`. */
if (dbg_level > 1) {
std::cout << "merging\n";
}
@@ -2882,8 +2903,7 @@ static CoplanarClusterInfo find_clusters(const IMesh &tm, const Array<BoundingBo
}
}
/* Does this give deterministic order for cluster ids? I think so, since
- * hash for planes is on their values, not their addresses.
- */
+ * hash for planes is on their values, not their addresses. */
for (auto item : plane_cls.items()) {
for (const CoplanarCluster &cl : item.value) {
if (cl.tot_tri() > 1) {
@@ -2951,7 +2971,7 @@ static void degenerate_reduce(const void *__restrict UNUSED(userdata),
degen_chunk_join->has_degenerate_tri |= degen_chunk->has_degenerate_tri;
}
-/* Does triangle IMesh tm have any triangles with zero area? */
+/* Does triangle #IMesh tm have any triangles with zero area? */
static bool has_degenerate_tris(const IMesh &tm)
{
DegenData degen_data = {tm};
@@ -3015,8 +3035,7 @@ IMesh trimesh_nary_intersect(const IMesh &tm_in,
std::cout << "trimesh_nary_intersect start\n";
# endif
/* Usually can use tm_in but if it has degenerate or illegal triangles,
- * then need to work on a copy of it without those triangles.
- */
+ * then need to work on a copy of it without those triangles. */
const IMesh *tm_clean = &tm_in;
IMesh tm_cleaned;
if (has_degenerate_tris(tm_in)) {
@@ -3060,8 +3079,7 @@ IMesh trimesh_nary_intersect(const IMesh &tm_in,
doperfmax(2, tri_ov.overlap().size());
# endif
/* itt_map((a,b)) will hold the intersection value resulting from intersecting
- * triangles with indices a and b, where a < b.
- */
+ * triangles with indices a and b, where a < b. */
Map<std::pair<int, int>, ITT_value> itt_map;
itt_map.reserve(tri_ov.overlap().size());
calc_overlap_itts(itt_map, *tm_clean, clinfo, tri_ov, arena);
@@ -3151,18 +3169,20 @@ static std::ostream &operator<<(std::ostream &os, const ITT_value &itt)
os << "segment " << itt.p1 << " " << itt.p2;
break;
case ICOPLANAR:
- os << "coplanar t" << itt.t_source;
+ os << "co-planar t" << itt.t_source;
break;
}
return os;
}
-/* Writing the obj_mesh has the side effect of populating verts. */
+/**
+ * Writing the obj_mesh has the side effect of populating verts.
+ */
void write_obj_mesh(IMesh &m, const std::string &objname)
{
- /* Would like to use BKE_tempdir_base() here, but that brings in dependence on kernel library.
- * This is just for developer debugging anyway, and should never be called in production Blender.
- */
+ /* Would like to use #BKE_tempdir_base() here, but that brings in dependence on kernel library.
+ * This is just for developer debugging anyway,
+ * and should never be called in production Blender. */
# ifdef _WIN_32
const char *objdir = BLI_getenv("HOME");
# else
diff --git a/source/blender/blenlib/tests/BLI_mesh_intersect_test.cc b/source/blender/blenlib/tests/BLI_mesh_intersect_test.cc
index aafaae7e0d5..6d24c4e6c03 100644
--- a/source/blender/blenlib/tests/BLI_mesh_intersect_test.cc
+++ b/source/blender/blenlib/tests/BLI_mesh_intersect_test.cc
@@ -269,8 +269,7 @@ TEST(mesh_intersect, TriTri)
TEST(mesh_intersect, TriTriReversed)
{
/* Like TriTri but with triangles of opposite orientation.
- * This matters because projection to 2D will now need reversed triangles.
- */
+ * This matters because projection to 2D will now need reversed triangles. */
const char *spec = R"(6 2
0 0 0
4 0 0
@@ -462,8 +461,7 @@ TEST(mesh_intersect, OverlapCluster)
{
/* Chain of 5 overlapping coplanar tris.
* Ordered so that clustering will make two separate clusters
- * that it will have to merge into one cluster with everything.
- */
+ * that it will have to merge into one cluster with everything. */
const char *spec = R"(15 5
0 0 0
1 0 0
@@ -1001,8 +999,7 @@ static void spheregrid_test(int nrings, int grid_level, double z_offset, bool us
* The sphere is radius 1, has nrings rings and 2 * nrings segs,
* and is centered at (0,0,z_offset).
* The plane is 4x4, has 2**grid_level subdivisions x and y,
- * and is centered at the origin.
- */
+ * and is centered at the origin. */
if (nrings < 2 || grid_level < 1) {
return;
}