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

Changeset View

Standalone View

source/blender/blenkernel/intern/mesh_validate.cc

Show All 17 Lines
* \ingroup bke		* \ingroup bke
*/		*/

#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_multi_value_map.hh"
#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 "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 {
▲ Show 20 Lines • Show All 225 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_2 {

		using calc_edges::OrderedEdge;

		constexpr int expected_incident_edges = 4;

		struct EdgeData {
		int v_high;
		};

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

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

		struct LocalData {
		Map<int, ExtraVertexData> extra_vertex_data_map;
		};

		static void calc_edges_for_new_mesh(Mesh *mesh)
		{
		Array<VertexData> vertex_data_array(mesh->totvert, NoInitialization{});
		constexpr int create_map_thread_count = 10;
		int create_map_thread_divider = mesh->totvert / create_map_thread_count + 1;
		threading::EnumerableThreadSpecific<std::array<Vector<OrderedEdge>, create_map_thread_count>>
		gathered_edges;

		{
		SCOPED_TIMER("initialization");
		threading::parallel_invoke(
		[&]() {
		threading::parallel_for(IndexRange(mesh->totvert), 1000, [&](IndexRange range) {
		default_construct_n(vertex_data_array.data() + range.start(), range.size());
		});
		},
		[&]() {
		threading::parallel_for(IndexRange(mesh->totpoly), 1000, [&](IndexRange range) {
		std::array<Vector<OrderedEdge>, create_map_thread_count> &local =
		gathered_edges.local();
		for (const int poly_index : range) {
		const MPoly &poly = mesh->mpoly[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 = mesh->mloop[i];
		const MLoop &loop_prev = mesh->mloop[i - 1];
		const OrderedEdge ordered_edge{loop_prev.v, loop.v};
		local[ordered_edge.v_low / create_map_thread_divider].append(ordered_edge);
		}
		const OrderedEdge ordered_edge{mesh->mloop[loop_start].v,
		mesh->mloop[loop_end - 1].v};
		local[ordered_edge.v_low / create_map_thread_divider].append(ordered_edge);
		}
		});
		});
		}

		threading::EnumerableThreadSpecific<LocalData> local_data_map;

		auto check_and_override = [&](MutableSpan<EdgeData> edges_data, int v_high) {
		for (EdgeData &edge_data : edges_data) {
		if (edge_data.v_high == v_high) {
		/* Edge is inserted already. */
		return true;
		}
		}
		return false;
		};

		auto add_edge = [&](const OrderedEdge ordered_edge, LocalData &local_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};
		if (check_and_override(existing_edges, v_high)) {
		return false;
		}
		if (vertex_data.count < expected_incident_edges) {
		EdgeData &new_edge_data = vertex_data.edges[vertex_data.count];
		new_edge_data.v_high = v_high;
		}
		else {
		MutableSpan<EdgeData> extra_existing_edges =
		local_data.extra_vertex_data_map.lookup(v_low).edges;
		if (check_and_override(extra_existing_edges, v_high)) {
		return false;
		}
		EdgeData new_edge_data;
		new_edge_data.v_high = v_high;
		local_data.extra_vertex_data_map.lookup_or_add_default(v_low).edges.append(new_edge_data);
		}
		vertex_data.count++;
		return true;
		};

		std::array<int, create_map_thread_count> thread_ids;
		for (const int i : IndexRange(create_map_thread_count)) {
		thread_ids[i] = i;
		}
		std::array<int, create_map_thread_count> count_by_thread;

		{
		SCOPED_TIMER("add edges to map");
		threading::parallel_for_each(thread_ids, [&](const int thread_id) {
		LocalData &local_data = local_data_map.local();
		int edge_count = 0;
		for (const std::array<Vector<OrderedEdge>, create_map_thread_count> &edges_vectors :
		gathered_edges) {
		Span<OrderedEdge> ordered_edges = edges_vectors[thread_id];
		for (const OrderedEdge &ordered_edge : ordered_edges) {
		if (add_edge(ordered_edge, local_data)) {
		edge_count++;
		}
		}
		}

		count_by_thread[thread_id] = edge_count;
		});
		}

		int tot_edges = 0;
		for (int count : count_by_thread) {
		tot_edges += count;
		}

		MutableSpan<MEdge> new_edges;
		{
		SCOPED_TIMER("allocate");
		new_edges = {(MEdge *)MEM_malloc_arrayN(tot_edges, sizeof(MEdge), __func__), tot_edges};
		}

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

		{
		SCOPED_TIMER("Add final edges");
		threading::parallel_for_each(thread_ids, [&](const int thread_id) {
		const int range_start = thread_id * create_map_thread_divider;
		const int range_end = std::min(range_start + create_map_thread_divider, mesh->totvert);

		int edge_index = 0;
		for (const int i : IndexRange(thread_id)) {
		edge_index += count_by_thread[i];
		}

		for (int v_low = range_start; v_low < range_end; v_low++) {
		VertexData &vertex_data = vertex_data_array[v_low];
		vertex_data.final_index_start = edge_index;
		for (const int i : IndexRange(vertex_data.count)) {
		add_final_edge(v_low, vertex_data.edges[i], edge_index);
		}
		}
		/* TODO */
		// for (LocalData &local_data : local_data_map) {
		// for (auto item : local_data.extra_vertex_data_map.items()) {
		// const int v_low = item.key;
		// ExtraVertexData &extra_vertex_data = item.value;
		// extra_vertex_data.final_index_start = edge_index;
		// for (EdgeData &edge_data : extra_vertex_data.edges) {
		// add_final_edge(v_low, edge_data, edge_index);
		// }
		// }
		// }
		});
		}

		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;
		}
		}
		for (LocalData &local_data : local_data_map) {
		const ExtraVertexData *extra_vertex_data = local_data.extra_vertex_data_map.lookup_ptr(
		v_low);
		if (extra_vertex_data != nullptr) {
		for (const int i : extra_vertex_data->edges.index_range()) {
		const EdgeData &edge_data = vertex_data.edges[i];
		if (v_high == edge_data.v_high) {
		return extra_vertex_data->final_index_start + i;
		}
		}
		}
		}
		BLI_assert_unreachable();
		return -1;
		};

		{
		SCOPED_TIMER("update loops");
		threading::parallel_for(IndexRange(mesh->totpoly), 1000, [&](IndexRange poly_range) {
		for (const int poly_index : poly_range) {
		MPoly &poly = mesh->mpoly[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 = mesh->mloop[i];
		MLoop &loop_prev = mesh->mloop[i - 1];
		const OrderedEdge ordered_edge{loop_prev.v, loop.v};
		loop_prev.e = find_edge_index(ordered_edge);
		}
		MLoop &loop_first = mesh->mloop[loop_start];
		MLoop &loop_last = mesh->mloop[loop_end - 1];
		const OrderedEdge ordered_edge{loop_first.v, loop_last.v};
		loop_last.e = find_edge_index(ordered_edge);
		}
		});
		}

		CustomData_free_layer(&mesh->edata, CD_MEDGE, mesh->totedge, 0);
		mesh->totedge = tot_edges;
		mesh->medge = new_edges.data();
		CustomData_add_layer(&mesh->edata, CD_MEDGE, CD_ASSIGN, mesh->medge, tot_edges);

		{
		SCOPED_TIMER("destruct array");
		vertex_data_array.reinitialize(0);
		}
		}

		} // namespace blender::bke::calc_edges_2

		void BKE_mesh_calc_edges_from_polys(Mesh *mesh)
		{
		blender::bke::calc_edges_2::calc_edges_for_new_mesh(mesh);
		}