Differential D13289 Diff 45036 source/blender/blenkernel/intern/mesh_validate.cc

Changeset View

Standalone View

source/blender/blenkernel/intern/mesh_validate.cc

Show All 12 Lines
* along with this program; if not, write to the Free Software Foundation,		* along with this program; if not, write to the Free Software Foundation,
* Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.		* Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
*/		*/

/** \file		/** \file
* \ingroup bke		* \ingroup bke
*/		*/

		#include <numeric>

#include "DNA_mesh_types.h"		#include "DNA_mesh_types.h"
#include "DNA_meshdata_types.h"		#include "DNA_meshdata_types.h"
#include "DNA_object_types.h"		#include "DNA_object_types.h"

#include "BLI_edgehash.h"		#include "BLI_edgehash.h"
		#include "BLI_enumerable_thread_specific.hh"
#include "BLI_map.hh"		#include "BLI_map.hh"
#include "BLI_math_base.h"		#include "BLI_math_base.h"
#include "BLI_task.hh"		#include "BLI_task.hh"
#include "BLI_threads.h"		#include "BLI_threads.h"
#include "BLI_timeit.hh"		#include "BLI_timeit.hh"
		#include "BLI_vector_list.hh"
		#include "BLI_vector_set.hh"

#include "BKE_customdata.h"		#include "BKE_customdata.h"
#include "BKE_mesh.h"		#include "BKE_mesh.h"

namespace blender::bke::calc_edges {		namespace blender::bke::calc_edges {

/** This is used to uniquely identify edges in a hash map. */		/** This is used to uniquely identify edges in a hash map. */
struct OrderedEdge {		struct OrderedEdge {
▲ Show 20 Lines • Show All 222 Lines • ▼ Show 20 Lines	void BKE_mesh_calc_edges(Mesh *mesh, bool keep_existing_edges, const bool select_new_edges)
CustomData_reset(&mesh->edata);		CustomData_reset(&mesh->edata);
CustomData_add_layer(&mesh->edata, CD_MEDGE, CD_ASSIGN, new_edges.data(), new_totedge);		CustomData_add_layer(&mesh->edata, CD_MEDGE, CD_ASSIGN, new_edges.data(), new_totedge);
mesh->totedge = new_totedge;		mesh->totedge = new_totedge;
mesh->medge = new_edges.data();		mesh->medge = new_edges.data();

/* Explicitly clear edge maps, because that way it can be parallelized. */		/* Explicitly clear edge maps, because that way it can be parallelized. */
clear_hash_tables(edge_maps);		clear_hash_tables(edge_maps);
}		}

		namespace blender ::bke::calc_edges_from_polys {

		using calc_edges::OrderedEdge;

		constexpr int expected_incident_edges = 4;
		constexpr int min_loops_per_bucket = 5000;

		struct EdgeData {
		int v_high;

		uint64_t hash() const
		{
		return v_high;
		}

		friend bool operator==(const EdgeData &a, const EdgeData &b)
		{
		return a.v_high == b.v_high;
		}
		};

		struct VertexData {
		int count = 0;
		int final_index_start;
		std::array<EdgeData, expected_incident_edges> edges;
		};

		struct ExtraVertexData {
		int final_index_start;
		VectorSet<EdgeData> edges;
		};

		struct alignas(64) BucketData {
		Map<int, ExtraVertexData> extra_vertex_data_map;
		int direct_edge_count = 0;
		int extra_edge_count = 0;

		int final_direct_edge_index_start;
		int final_extra_edge_index_start;
		};

		static MutableSpan<MEdge> calc_edges_from_polys(const int tot_verts,
		const Span<MPoly> polys,
		MutableSpan<MLoop> loops)
		{
		const int thread_count = BLI_system_thread_count();
		const int bucket_count = std::max<int>(
		1, std::min<int>(thread_count, loops.size() / min_loops_per_bucket));
		const int bucket_divider = tot_verts / bucket_count + 1;

		Array<BucketData> data_per_bucket(bucket_count);
		Array<VertexData> vertex_data_array(tot_verts, NoInitialization{});
		threading::EnumerableThreadSpecific<Array<VectorList<OrderedEdge>>> gathered_edges(
		[&]() { return Array<VectorList<OrderedEdge>>(bucket_count); });

		threading::parallel_invoke(
		[&]() {
		threading::parallel_for(IndexRange(tot_verts), 10000, [&](IndexRange range) {
		default_construct_n(vertex_data_array.data() + range.start(), range.size());
		});
		},
		[&]() {
		threading::parallel_for(polys.index_range(), 1000, [&](IndexRange range) {
		Array<VectorList<OrderedEdge>> &local = gathered_edges.local();
		for (const int poly_index : range) {
		const MPoly &poly = polys[poly_index];
		const int loop_start = poly.loopstart;
		const int loop_end = loop_start + poly.totloop;
		for (int i = loop_start + 1; i < loop_end; i++) {
		const MLoop &loop = loops[i];
		const MLoop &loop_prev = loops[i - 1];
		const OrderedEdge ordered_edge{loop_prev.v, loop.v};
		const int bucket_index = ordered_edge.v_low / bucket_divider;
		local[bucket_index].append(ordered_edge);
		}
		const OrderedEdge ordered_edge{loops[loop_start].v, loops[loop_end - 1].v};
		const int bucket_index = ordered_edge.v_low / bucket_divider;
		local[bucket_index].append(ordered_edge);
		}
		});
		});

		auto add_edge = [&](const OrderedEdge ordered_edge, BucketData &bucket_data) {
		const int v_low = ordered_edge.v_low;
		const int v_high = ordered_edge.v_high;
		VertexData &vertex_data = vertex_data_array[v_low];
		MutableSpan<EdgeData> existing_edges{vertex_data.edges.data(), vertex_data.count};
		for (EdgeData &edge_data : existing_edges) {
		if (edge_data.v_high == v_high) {
		return;
		}
		}
		if (vertex_data.count < expected_incident_edges) {
		EdgeData &new_edge_data = vertex_data.edges[vertex_data.count];
		new_edge_data.v_high = v_high;
		vertex_data.count++;
		bucket_data.direct_edge_count++;
		return;
		}
		ExtraVertexData &extra_vertex_data = bucket_data.extra_vertex_data_map.lookup(v_low);
		VectorSet<EdgeData> &extra_edges = extra_vertex_data.edges;
		EdgeData new_edge_data;
		new_edge_data.v_high = v_high;
		if (extra_edges.add(new_edge_data)) {
		vertex_data.count++;
		bucket_data.extra_edge_count++;
		}
		};

		threading::parallel_for_each(data_per_bucket, [&](BucketData &bucket_data) {
		const int bucket_index = &bucket_data - data_per_bucket.data();
		for (const Array<VectorList<OrderedEdge>> &edges_vectors : gathered_edges) {
		for (const Span<OrderedEdge> ordered_edges : edges_vectors[bucket_index]) {
		for (const OrderedEdge &ordered_edge : ordered_edges) {
		add_edge(ordered_edge, bucket_data);
		}
		}
		}
		});

		int tot_new_edges = 0;
		for (BucketData &bucket_data : data_per_bucket) {
		bucket_data.final_direct_edge_index_start = tot_new_edges;
		tot_new_edges += bucket_data.direct_edge_count;
		bucket_data.final_extra_edge_index_start = tot_new_edges;
		tot_new_edges += bucket_data.extra_edge_count;
		}

		auto get_bucket_range = [&](const int bucket_index) {
		const int start = bucket_index * bucket_divider;
		const int end = std::min(start + bucket_divider, tot_verts);
		const int size = end - start;
		return IndexRange(start, size);
		};

		threading::parallel_invoke(
		[&]() {
		threading::parallel_for_each(data_per_bucket, [&](BucketData &bucket_data) {
		const int bucket_index = &bucket_data - data_per_bucket.data();
		const IndexRange bucket_range = get_bucket_range(bucket_index);

		int edge_index = bucket_data.final_direct_edge_index_start;
		for (const int v_low : bucket_range) {
		VertexData &vertex_data = vertex_data_array[v_low];
		vertex_data.final_index_start = edge_index;
		edge_index += vertex_data.count;
		}
		});
		},
		[&]() {
		threading::parallel_for_each(data_per_bucket, [&](BucketData &bucket_data) {
		int edge_index = bucket_data.final_extra_edge_index_start;
		for (ExtraVertexData &extra_vertex_data : bucket_data.extra_vertex_data_map.values()) {
		extra_vertex_data.final_index_start = edge_index;
		edge_index += extra_vertex_data.edges.size();
		}
		});
		});

		MutableSpan<MEdge> new_edges = {
		(MEdge *)MEM_malloc_arrayN(tot_new_edges, sizeof(MEdge), __func__), tot_new_edges};

		auto set_final_edge = [&](const int v_low, const EdgeData &edge_data, const int edge_index) {
		MEdge edge = {0};
		edge.v1 = v_low;
		edge.v2 = edge_data.v_high;
		new_edges[edge_index] = edge;
		};

		auto find_edge_index = [&](const OrderedEdge &ordered_edge) {
		const int v_low = ordered_edge.v_low;
		const int v_high = ordered_edge.v_high;
		const VertexData &vertex_data = vertex_data_array[v_low];
		for (const int i : IndexRange(vertex_data.count)) {
		const EdgeData &edge_data = vertex_data.edges[i];
		if (v_high == edge_data.v_high) {
		return vertex_data.final_index_start + i;
		}
		}
		const int bucket_index = v_low / bucket_divider;
		const BucketData &bucket_data = data_per_bucket[bucket_index];
		const ExtraVertexData &extra_vertex_data = bucket_data.extra_vertex_data_map.lookup(v_low);
		const int index_in_extra_data = extra_vertex_data.edges.index_of(EdgeData{v_high});
		return extra_vertex_data.final_index_start + index_in_extra_data;
		};

		threading::parallel_invoke(
		[&]() {
		threading::parallel_for(IndexRange(tot_verts), 1000, [&](const IndexRange range) {
		for (const int v_low : range) {
		const VertexData &vertex_data = vertex_data_array[v_low];
		int edge_index = vertex_data.final_index_start;
		for (const int i : IndexRange(vertex_data.count)) {
		set_final_edge(v_low, vertex_data.edges[i], edge_index);
		edge_index++;
		}
		}
		});
		},
		[&]() {
		threading::parallel_for_each(data_per_bucket, [&](const BucketData &bucket_data) {
		for (auto item : bucket_data.extra_vertex_data_map.items()) {
		const int v_low = item.key;
		const ExtraVertexData &extra_vertex_data = item.value;
		int edge_index = extra_vertex_data.final_index_start;
		for (const EdgeData &edge_data : extra_vertex_data.edges) {
		set_final_edge(v_low, edge_data, edge_index);
		edge_index++;
		}
		}
		});
		},
		[&]() {
		threading::parallel_for(polys.index_range(), 1000, [&](IndexRange poly_range) {
		for (const int poly_index : poly_range) {
		const MPoly &poly = polys[poly_index];
		const int loop_start = poly.loopstart;
		const int loop_end = loop_start + poly.totloop;
		for (int i = loop_start + 1; i < loop_end; i++) {
		MLoop &loop = loops[i];
		MLoop &loop_prev = loops[i - 1];
		const OrderedEdge ordered_edge{loop_prev.v, loop.v};
		loop_prev.e = find_edge_index(ordered_edge);
		}
		MLoop &loop_first = loops[loop_start];
		MLoop &loop_last = loops[loop_end - 1];
		const OrderedEdge ordered_edge{loop_first.v, loop_last.v};
		loop_last.e = find_edge_index(ordered_edge);
		}
		});
		});

		return new_edges;
		}

		} // namespace blender::bke::calc_edges_from_polys

		void BKE_mesh_calc_edges_from_polys(Mesh *mesh)
		{
		using namespace blender;
		MutableSpan<MEdge> edges = blender::bke::calc_edges_from_polys::calc_edges_from_polys(
		mesh->totvert, Span(mesh->mpoly, mesh->totpoly), MutableSpan(mesh->mloop, mesh->totloop));

		CustomData_free_layer(&mesh->edata, CD_MEDGE, mesh->totedge, 0);
		mesh->totedge = edges.size();
		mesh->medge = edges.data();
		CustomData_add_layer(&mesh->edata, CD_MEDGE, CD_ASSIGN, mesh->medge, mesh->totedge);
		}