diff options
author | Campbell Barton <ideasman42@gmail.com> | 2020-08-27 11:18:47 +0300 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2020-08-27 11:18:47 +0300 |
commit | e0cb02587012b4b2f4b18363dc7d0a7da2c02093 (patch) | |
tree | d574c9585e2010d10d074b6da88ab50191b36bb2 /source/blender/blenlib | |
parent | 94884777b20dc612863690171b958eef41a4b6fd (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.h | 11 | ||||
-rw-r--r-- | source/blender/blenlib/BLI_double2.hh | 4 | ||||
-rw-r--r-- | source/blender/blenlib/BLI_double3.hh | 9 | ||||
-rw-r--r-- | source/blender/blenlib/BLI_math_mpq.hh | 4 | ||||
-rw-r--r-- | source/blender/blenlib/BLI_mesh_boolean.hh | 11 | ||||
-rw-r--r-- | source/blender/blenlib/BLI_mesh_intersect.hh | 75 | ||||
-rw-r--r-- | source/blender/blenlib/BLI_mpq2.hh | 9 | ||||
-rw-r--r-- | source/blender/blenlib/BLI_mpq3.hh | 6 | ||||
-rw-r--r-- | source/blender/blenlib/intern/delaunay_2d.cc | 283 | ||||
-rw-r--r-- | source/blender/blenlib/intern/math_vec.cc | 180 | ||||
-rw-r--r-- | source/blender/blenlib/intern/math_vector.c | 2 | ||||
-rw-r--r-- | source/blender/blenlib/intern/mesh_boolean.cc | 333 | ||||
-rw-r--r-- | source/blender/blenlib/intern/mesh_intersect.cc | 352 | ||||
-rw-r--r-- | source/blender/blenlib/tests/BLI_mesh_intersect_test.cc | 9 |
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; } |