diff options
Diffstat (limited to 'source/blender/blenlib/BLI_delaunay_2d.h')
| -rw-r--r-- | source/blender/blenlib/BLI_delaunay_2d.h | 85 |
1 files changed, 72 insertions, 13 deletions
diff --git a/source/blender/blenlib/BLI_delaunay_2d.h b/source/blender/blenlib/BLI_delaunay_2d.h index a826a6b2677..7027477ac7f 100644 --- a/source/blender/blenlib/BLI_delaunay_2d.h +++ b/source/blender/blenlib/BLI_delaunay_2d.h @@ -18,6 +18,9 @@ /** \file * \ingroup bli + * + * This header file contains both a C interface and a C++ interface + * to the 2D Constrained Delaunay Triangulation library routine. */ #ifdef __cplusplus @@ -107,11 +110,6 @@ extern "C" { * If zero is supplied for epsilon, an internal value of 1e-8 used * instead, since this code will not work correctly if it is not allowed * to merge "too near" vertices. - * - * Normally, if epsilon is non-zero, there is an "input modify" pass which - * checks to see if some vertices are within epsilon of other edges, and - * snapping them to those edges if so. You can skip this pass by setting - * skip_input_modify to true. (This is also useful in some unit tests.) */ typedef struct CDT_input { int verts_len; @@ -123,7 +121,6 @@ typedef struct CDT_input { int *faces_start_table; int *faces_len_table; float epsilon; - bool skip_input_modify; } CDT_input; /** @@ -150,12 +147,9 @@ typedef struct CDT_input { * - faces_orig, faces_orig_start_table, faces_orig_len_table * * For edges, the edges_orig triple can also say which original face - * edge is part of a given output edge. If an index in edges_orig - * is greater than the input's edges_len, then subtract input's edges_len - * from it to some number i: then the face edge that starts from the - * input vertex at input's faces[i] is the corresponding face edge. - * for convenience, face_edge_offset in the result will be the input's - * edges_len, so that this conversion can be easily done by the caller. + * edge is part of a given output edge. See the comment below + * on the C++ interface for how to decode the entries in the edges_orig + * table. */ typedef struct CDT_result { int verts_len; @@ -207,4 +201,69 @@ void BLI_delaunay_2d_cdt_free(CDT_result *result); #ifdef __cplusplus } -#endif + +/* C++ Interface. */ + +# include "BLI_array.hh" +# include "BLI_double2.hh" +# include "BLI_math_mpq.hh" +# include "BLI_mpq2.hh" +# include "BLI_vector.hh" + +namespace blender::meshintersect { + +/* vec2<Arith_t> is a 2d vector with Arith_t as the type for coordinates. */ +template<typename Arith_t> struct vec2_impl; +template<> struct vec2_impl<double> { + typedef double2 type; +}; + +# ifdef WITH_GMP +template<> struct vec2_impl<mpq_class> { + typedef mpq2 type; +}; +# endif + +template<typename Arith_t> using vec2 = typename vec2_impl<Arith_t>::type; + +template<typename Arith_t> class CDT_input { + public: + Array<vec2<Arith_t>> vert; + Array<std::pair<int, int>> edge; + Array<Vector<int>> face; + Arith_t epsilon{0}; +}; + +template<typename Arith_t> class CDT_result { + public: + 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? */ + Array<Vector<int>> vert_orig; + /** + * 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. + * else let (a, b) = the quotient and remainder of dividing + * the edge index by face_edge_offset; "a" will be the input face + 1, + * and "b" will be a position within that face. + */ + Array<Vector<int>> edge_orig; + /** For each output face, which original faces does it overlap? */ + Array<Vector<int>> face_orig; + /** Used to encode edge_orig (see above). */ + int face_edge_offset; +}; + +CDT_result<double> delaunay_2d_calc(const CDT_input<double> &input, CDT_output_type output_type); + +# ifdef WITH_GMP +CDT_result<mpq_class> delaunay_2d_calc(const CDT_input<mpq_class> &input, + CDT_output_type output_type); +# endif + +} /* namespace blender::meshintersect */ + +#endif /* __cplusplus */ |