Commit: 2ce0bb135892024ffb125acf74a51218ee4eb0bb Author: Howard Trickey Date: Sat Nov 12 14:16:47 2022 -0500 Branches: bevelv2 https://developer.blender.org/rB2ce0bb135892024ffb125acf74a51218ee4eb0bb
Better comments and fixing implicit precision conversion warnings. =================================================================== M source/blender/blenlib/BLI_mesh_inset.hh M source/blender/blenlib/intern/mesh_inset.cc =================================================================== diff --git a/source/blender/blenlib/BLI_mesh_inset.hh b/source/blender/blenlib/BLI_mesh_inset.hh index 599ea061b2e..98a0ec762ce 100644 --- a/source/blender/blenlib/BLI_mesh_inset.hh +++ b/source/blender/blenlib/BLI_mesh_inset.hh @@ -17,6 +17,60 @@ namespace blender::meshinset { +/* + * This is the library interface to a function that can inset + * contours (closed sequences of vertices) of a 3D mesh. + * For generality, the mesh is specified by #Span of faces, + * where each face has the sequence of vertex indices that + * are traversed in CCW order to form the face. + * The indices given the position in a #Span of #float3 entries, + * which are 3D coordinates. + * + * An "inset" of a contour by a given amount is conceptually + * formed as follows: offset each edge of the contour on its left + * side by the specified amount, shortening and joining up each + * offset edge with its neighbor offset edges. If the contour + * forms a face, this is typically known as a "face inset". + * However, that conceptual description fails to describe what + * to do if an offset edge shortens so much that it vanishes, + * or if advancing intersection points of offset edges collide + * into offset edges from another part of the contour (or another + * contour). + * + * An algorithm called the "Straight Skeleton Algorithm" + * (see https://wikipedia.org/wiki/Straight_skeleton) + * deals with such complications, and is what is used in this + * library routine. That algorithm regards each edge of the + * contour as a wavefront that advances at a constant speed, + * dealing with topological changes as wavefront edges collapse + * or crash into opposite ones. The Straight Skeleton is what + * remains if you advance the wavefronts as far as they can go, + * but we can stop at any particular amount of advancement to + * achieve an inset by that amount. + * + * However, the Straight Skeleton Algorithm is a 2D algorithm, + * doesn't deal with internal geometry. This library function + * is adapted to work in 3D and "flow over" internal geometry + * as the wavefronts advance. + * + * Also, an extra feature of this library is to allow the advancing + * wavefronts to raise (along face normals) at a given slope. + * Users like this as an option to a "face inset" function. + * + * Usage: + * Populate a #MeshInset_Input structure with the mesh + * (vertex coordinates and faces), the contours to inset + * (vertex indices forming closed loops to inset), + * and the amount to inset and the slope. + * Pass this to #mesh_inset_calc, and receive a #MeshInset_Result + * as output. + * The #MeshInset_Result has a new mesh, also give by vertex + * coordinates and faces. It also has some data to help understand + * how to map the output back to the input: + * TODO: Document the extras when this interface finally settles down. + */ + +/** #MeshInset_Input is the input structure for #mesh_inset_calc. */ class MeshInset_Input { public: /** The vertices. Can be a superset of the needed vertices. */ @@ -30,6 +84,7 @@ public: bool need_ids; }; +/** #MeshInset_Result is the output structure for #mesh_inset_calc. */ class MeshInset_Result { public: /** The output vertices. A subset (perhaps) of input vertices, plus some new ones. */ @@ -44,6 +99,12 @@ public: Array<int> orig_face; }; +/** + * Calculate a mesh inset -- the offset of a set of contours, dealing with collisions. + * + * \param input: a #MeshInset_Input containing a mesh, contours to offet, and offset parameters. + * \return a #MeshInset_Result giving a new mesh and data to relate the output to the input. + */ MeshInset_Result mesh_inset_calc(const MeshInset_Input &input); } // namespace blender::meshinset diff --git a/source/blender/blenlib/intern/mesh_inset.cc b/source/blender/blenlib/intern/mesh_inset.cc index 228507bdda2..3d04a21a1d4 100644 --- a/source/blender/blenlib/intern/mesh_inset.cc +++ b/source/blender/blenlib/intern/mesh_inset.cc @@ -502,7 +502,7 @@ class TriangleMesh { Vert *add_vert(const float3 co) { Vert *vert = new Vert(co); - int v = verts_.append_and_get_index(vert); + int v = int(verts_.append_and_get_index(vert)); vert->id = v; return vert; } @@ -515,7 +515,7 @@ class TriangleMesh { Triangle *add_triangle(Vert *v0, Vert *v1, Vert *v2) { Triangle *tri = new Triangle(v0, v1, v2); - int t = triangles_.append_and_get_index(tri); + int t = int(triangles_.append_and_get_index(tri)); tri->set_id(t); return tri; } @@ -523,7 +523,7 @@ class TriangleMesh { /** Add pointer to already allocated Triangle \a tri. Takes ownership of memory.*/ void add_allocated_triangle(Triangle *tri) { - int t = triangles_.append_and_get_index(tri); + int t = int(triangles_.append_and_get_index(tri)); tri->set_id(t); } @@ -683,7 +683,7 @@ static void trimesh_draw(const std::string &label, const TriangleMesh &trimesh) axis_dominant_v3_to_m3(axis_mat, avg_normal); Array<float2> proj_vertco(verts.size()); - for (int i : verts.index_range()) { + for (int64_t i : verts.index_range()) { mul_v2_m3v3(proj_vertco[i], axis_mat, verts[i]->co); } @@ -750,7 +750,7 @@ static void trimesh_draw(const std::string &label, const TriangleMesh &trimesh) } else { float2 center(0.0f, 0.0f); - for (int i : IndexRange(3)) { + for (int i = 0; i < 3; ++i) { float2 p0 = mapxy(proj_vertco[tri->vert(i)->id]); float2 p1 = mapxy(proj_vertco[tri->vert(succ_index(i))->id]); /* Make spokes and boundary between in-region and out-region bolder. */ @@ -867,7 +867,7 @@ Vert *TriangleMesh::split_vert(Vert *v, Edge e1, Edge e2) v->e = null_edge; Triangle *tri_new_first = nullptr; Triangle *tri_new_last = nullptr; - for (int i : fan.index_range()) { + for (int64_t i : fan.index_range()) { ecur = fan[i]; if (ecur == e2) { break; @@ -1064,9 +1064,9 @@ static Vector<Vector<Edge>> init_contour_inset(TriangleMesh &trimesh, Span<Vecto ans.reserve(contours.size()); for (const Vector<int> &cont : contours) { /* Find the edges that make up the contour. */ - int n = cont.size(); + int n = int(cont.size()); Array<Edge> cont_edges(n); - for (int i : cont.index_range()) { + for (int i = 0; i < n; ++i) { int v_index = cont[i]; int v_next_index = cont[(i + 1) % n]; Vert *v = trimesh.get_vert_by_index(v_index); @@ -1080,7 +1080,7 @@ static Vector<Vector<Edge>> init_contour_inset(TriangleMesh &trimesh, Span<Vecto Vector<Vert *> split_verts; split_verts.reserve(n); - for (int i : cont.index_range()) { + for (int i = 0; i < n; ++i) { Vert *v = trimesh.get_vert_by_index(cont[i]); Edge e = cont_edges[i]; Edge e_prev_reverse = neighbor_edge(cont_edges[(i + n - 1) % n]); @@ -1093,7 +1093,7 @@ static Vector<Vector<Edge>> init_contour_inset(TriangleMesh &trimesh, Span<Vecto ans.append(Vector<Edge>()); Vector<Edge> &contour_edges = ans.last(); contour_edges.reserve(n); - for (int i : split_verts.index_range()) { + for (int i = 0; i < int(split_verts.size()); ++i) { Vert *v0 = split_verts[i]; Vert *v1 = split_verts[(i + 1) % n]; Edge e = edge_between(v0, v1); @@ -1487,7 +1487,8 @@ void StraightSkeleton::dump_state() const dump_event_queue(); std::cout << trimesh_; trimesh_draw("dump_state", trimesh_); - for (int i : IndexRange(trimesh_.all_tris().size())) { + int num_t = int(trimesh_.all_tris().size()); + for (int i = 0; i < num_t; ++i) { SkeletonVertex *skv = skel_vertex_map_.lookup_default(i, nullptr); if (skv != nullptr) { std::cout << "skv[" << i << "] = " << *skv << "\n"; @@ -1522,7 +1523,7 @@ void StraightSkeleton::calculate_contour_and_region_data() stack.append(seed_tri); while (!stack.is_empty()) { Triangle *tri = stack.pop_last(); - for (int i : IndexRange(3)) { + for (int i = 0; i < 3; ++i) { Edge e = tri->edge(i); /* Cannot cross over contour edges. */ if (!contour_edge_set_.contains(e)) { @@ -1914,7 +1915,7 @@ void StraightSkeleton::add_triangle(Edge edge, float min_height) float res1, res2; int nroots = solve_quadratic(a, b, c, &res1, &res2); float height = inf; - for (int i : IndexRange(nroots)) { + for (int i = 0; i < nroots; ++i) { float h = i == 1 ? res1 : res2; if (0.0f <= h && h < height) { height = h; @@ -2242,8 +2243,8 @@ void StraightSkeleton::compute() /* Create the skeleton vertices, first for the contours. */ int count_non_zero = 0; for (Vector<Edge> &contour : contour_edges_) { - int n = contour.size(); - for (int i : contour.index_range()) { + int n = int(contour.size()); + for (int i = 0; i < n; ++i) { Edge e = contour[i]; Edge e_prev = contour[(i + n - 1) % n]; float e_weight = 1.0f; @@ -2276,7 +2277,7 @@ void StraightSkeleton::compute() continue; } Edge e = tri->edge(0); - for (int i : IndexRange(3)) { + for (int i = 0; i < 3; ++i) { Vert *v = tri->vert(i); float3 vnormal = vertex_normal(v); if (!skel_vertex_map_has_id(v->id)) { @@ -2619,7 +2620,7 @@ void StraightSkeleton::compute() } Triangle *tri = event.edge().tri(); remaining_triangles_set.add(tri); - for (int i : IndexRange(3)) { + for (int i = 0; i < 3; ++i) { Vert *vert = tri->vert(i); SkeletonVertex *skv = skel_vertex_map(vert->id); if (skv != nullptr) { @@ -2640,7 +2641,7 @@ void StraightSkeleton::compute() static float3 poly_normal(Span<Vert *> verts) { Array<float3> poly(verts.size()); - for (const int i : verts.index_range()) { + for (const int64_t i : verts.index_range()) { poly[i] = verts[i]->co; } float3 n = math::cross_poly(poly.as_span()); @@ -2660,7 +2661,7 @@ static int edgepos_by_canon_pair(const Triangle *tri, const std::pair<int, int> { int a = vert_id_pair.first; int b = vert_id_pair.second; - for (const int i : IndexRange(3)) { + for (int i = 0; i < 3; ++i) { if ((tri->vert(i)->id == a && tri->vert(succ_index(i))->id == b) || (tri->vert(i)->id == b && tri->vert(succ_index(i))->id == a)) { @@ Diff output truncated at 10240 characters. @@ _______________________________________________ Bf-blender-cvs mailing list Bf-blender-cvs@blender.org List details, subscription details or unsubscribe: https://lists.blender.org/mailman/listinfo/bf-blender-cvs