[Bf-blender-cvs] [86494af] mesh-transfer-data: Islands 'TubeCase' WIP: More fixes, everything is mostly hooked up now.
Bastien Montagne
noreply at git.blender.org
Tue Nov 25 20:16:13 CET 2014
Commit: 86494af8cd5d04e8ace089a95d126a0a33d69206
Author: Bastien Montagne
Date: Tue Nov 25 20:05:09 2014 +0100
Branches: mesh-transfer-data
https://developer.blender.org/rB86494af8cd5d04e8ace089a95d126a0a33d69206
Islands 'TubeCase' WIP: More fixes, everything is mostly hooked up now.
Quick tests shows everything seems to work as expected so far.
And, divine surprise, performances seem pretty good!
Note we limit AStar to a small number of steps (4 currently),
reasoning is, if we map highpoly (dst) onto lowpoly (src), this should be
enough in most cases (smaller dst polys onto larger ones are unlikely to span
over more than two or three src polys). And in reverse case, taking care of
islands does not make much sense anyway, result shall be crappy anyway.
Remaining TODOs:
* Finish cutting edges handling (right now nothing is done yet to solve issues!).
* Cleanup/reorganization (AStar part has been designed as generic as possible,
will go to BLI), names, etc.
* Double, triple and quadruple checks of mem handling (*very* easy to get a mem leak
in such code :/ ).
===================================================================
M source/blender/blenkernel/intern/mesh_mapping.c
M source/blender/blenkernel/intern/mesh_remap.c
===================================================================
diff --git a/source/blender/blenkernel/intern/mesh_mapping.c b/source/blender/blenkernel/intern/mesh_mapping.c
index fcf95ac..9e490ae 100644
--- a/source/blender/blenkernel/intern/mesh_mapping.c
+++ b/source/blender/blenkernel/intern/mesh_mapping.c
@@ -398,6 +398,7 @@ static void poly_edge_loop_islands_calc(
int *poly_stack;
BLI_bitmap *edge_borders = NULL;
+ int num_edgeborders = 0;
int poly_prev = 0;
const int temp_poly_group_id = 3; /* Placeholder value. */
@@ -413,6 +414,7 @@ static void poly_edge_loop_islands_calc(
*r_poly_groups = NULL;
if (r_edge_borders) {
*r_edge_borders = NULL;
+ *r_totedgeborder = 0;
}
return;
}
@@ -485,7 +487,7 @@ static void poly_edge_loop_islands_calc(
else {
if (edge_borders && !BLI_BITMAP_TEST(edge_borders, me_idx)) {
BLI_BITMAP_ENABLE(edge_borders, me_idx);
- r_totedgeborder++;
+ num_edgeborders++;
}
if (use_bitflags) {
/* Find contiguous smooth groups already assigned, these are the values we can't reuse! */
@@ -558,6 +560,7 @@ static void poly_edge_loop_islands_calc(
*r_poly_groups = poly_groups;
if (r_edge_borders) {
*r_edge_borders = edge_borders;
+ *r_totedgeborder = num_edgeborders;
}
}
@@ -731,7 +734,7 @@ bool BKE_mesh_calc_islands_loop_poly_uv(
int num_edge_borders;
char *edge_border_count = NULL;
int *edge_innercut_indices = NULL;
- int num_einnercut_idx = 0;
+ int num_einnercuts = 0;
int grp_idx, p_idx, pl_idx, l_idx;
@@ -759,7 +762,7 @@ bool BKE_mesh_calc_islands_loop_poly_uv(
for (grp_idx = 1; grp_idx <= num_poly_groups; grp_idx++) {
num_pidx = num_lidx = 0;
if (num_edge_borders) {
- num_einnercut_idx = 0;
+ num_einnercuts = 0;
memset(edge_border_count, 0, sizeof(*edge_border_count) * (size_t)totedge);
}
@@ -778,14 +781,14 @@ bool BKE_mesh_calc_islands_loop_poly_uv(
if (num_edge_borders && BLI_BITMAP_TEST(edge_borders, ml->e) && (edge_border_count[ml->e] < 2)) {
edge_border_count[ml->e]++;
if (edge_border_count[ml->e] == 2) {
- edge_innercut_indices[num_einnercut_idx++] = (int)ml->e;
+ edge_innercut_indices[num_einnercuts++] = (int)ml->e;
}
}
}
}
BKE_mesh_loop_islands_add(r_island_store, num_lidx, loop_indices, num_pidx, poly_indices,
- num_einnercut_idx, edge_innercut_indices);
+ num_einnercuts, edge_innercut_indices);
}
MEM_freeN(poly_indices);
diff --git a/source/blender/blenkernel/intern/mesh_remap.c b/source/blender/blenkernel/intern/mesh_remap.c
index 8e4b4d6..6b63474 100644
--- a/source/blender/blenkernel/intern/mesh_remap.c
+++ b/source/blender/blenkernel/intern/mesh_remap.c
@@ -834,6 +834,14 @@ static void astar_path_graph_init(AStarPathGraph *as_graph, const int node_num,
as_graph->custom_data = custom_data;
}
+static void astar_path_graph_free(AStarPathGraph *as_graph)
+{
+ if (as_graph->mem) {
+ BLI_memarena_free(as_graph->mem);
+ as_graph->mem = NULL;
+ }
+}
+
static void astar_path_node_init(AStarPathGraph *as_graph, const int node_index, void *custom_data)
{
as_graph->nodes[node_index].custom_data = custom_data;
@@ -921,13 +929,17 @@ static bool astar_solve(
float *g_costs = r_solution->g_costs;
int *g_steps = r_solution->g_steps;
- todo_nodes = BLI_heap_new();
-
prev_nodes[node_index_src] = -1;
+ BLI_BITMAP_SET_ALL(done_nodes, false, as_graph->node_num);
fill_vn_fl(g_costs, as_graph->node_num, FLT_MAX);
g_costs[node_index_src] = 0.0f;
g_steps[node_index_src] = 0;
+ if (node_index_src == node_index_dst) {
+ return true;
+ }
+
+ todo_nodes = BLI_heap_new();
BLI_heap_insert(todo_nodes,
f_cost_cb(as_graph, r_solution, NULL, -1, node_index_src, node_index_dst),
SET_INT_IN_POINTER(node_index_src));
@@ -942,9 +954,9 @@ static bool astar_solve(
continue;
}
- /* If we are limited in amount of steps to find a path, fail if we reached limit. */
+ /* If we are limited in amount of steps to find a path, skip if we reached limit. */
if (max_steps && g_steps[node_curr_idx] > max_steps) {
- break;
+ continue;
}
if (node_curr_idx == node_index_dst) {
@@ -1000,7 +1012,7 @@ static void mesh_island_to_astar_path_graph_edge_process(
MeshIslandStore *islands, const int island_index, AStarPathGraph *as_graph,
MVert *verts, MPoly *polys, MLoop *loops,
const int edge_idx, BLI_bitmap *done_edges, MeshElemMap *edge_to_poly_map, const bool is_einnercut,
- int *poly_isld_indices, float (*poly_centers)[3], unsigned char *poly_status)
+ int *poly_isld_index_map, float (*poly_centers)[3], unsigned char *poly_status)
{
int *p_isld_indices = BLI_array_alloca(p_isld_indices, (size_t)edge_to_poly_map[edge_idx].count);
int i, j;
@@ -1008,7 +1020,7 @@ static void mesh_island_to_astar_path_graph_edge_process(
for (i = 0; i < edge_to_poly_map[edge_idx].count; i++) {
const int p_idx = edge_to_poly_map[edge_idx].indices[i];
MPoly *mp = &polys[p_idx];
- const int p_isld_idx = islands ? poly_isld_indices[p_idx] : p_idx;
+ const int p_isld_idx = islands ? poly_isld_index_map[p_idx] : p_idx;
if (UNLIKELY(islands && (islands->items_to_islands[mp->loopstart] != island_index))) {
/* poly not in current island, happens with border edges... */
@@ -1053,7 +1065,7 @@ static void mesh_island_to_astar_path_graph(
MeshElemMap *island_poly_map = islands ? islands->islands[island_index] : NULL;
MeshElemMap *island_einnercut_map = islands ? islands->innercuts[island_index] : NULL;
- int *poly_isld_indices = islands ? MEM_mallocN(sizeof(*poly_isld_indices) * (size_t)numpolys, __func__) : NULL;
+ int *poly_isld_index_map = NULL;
BLI_bitmap *done_edges = BLI_BITMAP_NEW(numedges, __func__);
const int node_num = islands ? island_poly_map->count : numpolys;
@@ -1064,19 +1076,23 @@ static void mesh_island_to_astar_path_graph(
int i;
astar_path_graph_init(r_as_graph, node_num, NULL);
- /* polycenters are owned by graph memarena. */
+ /* poly_centers is owned by graph memarena. */
poly_centers = BLI_memarena_calloc(r_as_graph->mem, sizeof(*poly_centers) * (size_t)node_num);
if (islands) {
+ /* poly_isld_index_map is owned by graph memarena. */
+ poly_isld_index_map = BLI_memarena_calloc(r_as_graph->mem, sizeof(*poly_isld_index_map) * (size_t)numpolys);
for (i = island_poly_map->count; i--;) {
- poly_isld_indices[island_poly_map->indices[i]] = i;
+ poly_isld_index_map[island_poly_map->indices[i]] = i;
}
+ r_as_graph->custom_data = poly_isld_index_map;
+
for (i = island_einnercut_map->count; i--;) {
mesh_island_to_astar_path_graph_edge_process(
islands, island_index, r_as_graph, verts, polys, loops,
island_einnercut_map->indices[i], done_edges, edge_to_poly_map, true,
- poly_isld_indices, poly_centers, poly_status);
+ poly_isld_index_map, poly_centers, poly_status);
}
}
@@ -1099,14 +1115,11 @@ static void mesh_island_to_astar_path_graph(
mesh_island_to_astar_path_graph_edge_process(
islands, island_index, r_as_graph, verts, polys, loops,
(int)ml->e, done_edges, edge_to_poly_map, false,
- poly_isld_indices, poly_centers, poly_status);
+ poly_isld_index_map, poly_centers, poly_status);
}
poly_status[p_isld_idx] = POLY_COMPLETE;
}
- if (islands) {
- MEM_freeN(poly_isld_indices);
- }
MEM_freeN(done_edges);
MEM_freeN(poly_status);
}
@@ -1115,6 +1128,29 @@ static void mesh_island_to_astar_path_graph(
#undef POLY_CENTER_INIT
#undef POLY_COMPLETE
+/* Our 'f_cost' callback func, to find shortest poly-path between two remapped-loops.
+ * Note we do not want to make innercuts 'walls' here, just detect when the shortest path goes by those. */
+static float mesh_remap_calc_loops_astar_f_cost(
+ AStarPathGraph *as_graph, AStarPathSolution *as_solution, AStarPathLink *link,
+ const int node_idx_curr, const int node_idx_next, const int node_idx_dst)
+{
+ float *co_next, *co_dest;
+
+ if (link && GET_INT_FROM_POINTER(link->custom_data)) {
+ /* An innercut edge... We tag our solution as potentially crossing innercuts.
+ * Note it might not be the case in the end (AStar will explore around optimal path), but helps
+ * trimming off some processing later... */
+ if (!GET_INT_FROM_POINTER(as_solution->custom_data)) {
+ as_solution->custom_data = SET_INT_IN_POINTER(true);
+ }
+ }
+
+ /* Our heuristic part of current f_cost is distance from next node to destination one.
+ * It is guaranteed to be less than actual shortest poly-path between next node and destination one. */
+ co_next = (float *)as_graph->nodes[node_idx_next].custom_data;
+ co_dest = (float *)as_graph->nodes[node_idx_dst].custom_data;
+ return (link ? (as_solution->g_costs[node_idx_curr] + link->cost) : 0.0f) + len_v3v3(co_next, co_dest);
+}
void BKE_mesh_remap_calc_loops_from_dm(
const int mode, const SpaceTransform *space_transform, const float max_dist, const float ray_radius,
@@ -1149,9 +1185,11 @@ void BKE_mesh_remap_calc_loops_from_dm(
const bool use_from_vert = (mode & MREMAP_USE_VERT);
MeshIslandStore island_store = {0};
- AStarPathGraph *as_graphdata = NULL;
bool use_islands = false;
+ AStarPathGraph *as_graphdata = NULL;
+ AStarPathSolution as_solution = {{0}};
+
float (*poly_nors_src)[3] = NULL;
float (*loop_nors_src)[3] = NULL;
float (*poly_nors_dst)[3] = NULL;
@@ -1163,6 +1201,7 @@ void BKE_mesh_remap_calc_loops_from_dm(
int *vert_to_poly_map_src_buff = NULL;
MeshElemMap *edge_to_poly_map = NULL;
int *edge_to_poly_map_buff = NULL;
+ int *loop_to_poly_map_src = NULL;
bool verts_allocated_src;
MVert *verts_src = DM_get_vert_array(dm_src, &verts_allocated_src);
@@ -1260,6 +1299,15 @@ void BKE_mesh_remap_calc_loops_from_dm(
/* Needed for islands (or plain mesh) to AStar graph conversion. */
BKE_mesh_edge_poly_map_create(&edge_to_poly_map, &edge_to_poly_map_buff,
edges_src, num_edges_src, polys_src, num_polys_src, loops_src, num_loops_src);
+ if (use_from_vert) {
+ loop_to_poly_map_src = MEM_mallocN(sizeof(*loop_to_poly_map_src) * (size_
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list