[Bf-blender-cvs] [d464fb0996] master: Dynamic Paint: recursively search for island border edges.
Alexander Gavrilov
noreply at git.blender.org
Thu Jan 12 20:26:03 CET 2017
Commit: d464fb0996d71cafcde865657affd145518108ab
Author: Alexander Gavrilov
Date: Tue Jan 3 19:11:59 2017 +0300
Branches: master
https://developer.blender.org/rBd464fb0996d71cafcde865657affd145518108ab
Dynamic Paint: recursively search for island border edges.
It is quite likely in a triangulated mesh that the actual island edge
belongs to a different triangle than the current pixel; for example
consider corners of a triangulated axis aligned rectangle face that
have the additional edge: a pixel there will have to be assigned to
one of the triangles, but one of the edges of the original rectangle
can only be accessed through the other triangle.
Thus for robust operation it is necessary to do a recursive search.
The search is limited by requiring that it only goes through edges
that bring it closer to the target point, and also by depth as a
safeguard.
Differential Revision: https://developer.blender.org/D2409
===================================================================
M source/blender/blenkernel/intern/dynamicpaint.c
===================================================================
diff --git a/source/blender/blenkernel/intern/dynamicpaint.c b/source/blender/blenkernel/intern/dynamicpaint.c
index 9e3f123d5d..de3dfd772f 100644
--- a/source/blender/blenkernel/intern/dynamicpaint.c
+++ b/source/blender/blenkernel/intern/dynamicpaint.c
@@ -2320,6 +2320,18 @@ static float dist_squared_to_looptri_uv_edges(const MLoopTri *mlooptri, const ML
return min_distance;
}
+typedef struct DynamicPaintFindIslandBorderData {
+ const MeshElemMap *vert_to_looptri_map;
+ int w, h, px, py;
+
+ int best_index;
+ float best_weight;
+} DynamicPaintFindIslandBorderData;
+
+static void dynamic_paint_find_island_border(
+ const DynamicPaintCreateUVSurfaceData *data, DynamicPaintFindIslandBorderData *bdata,
+ int tri_index, const float pixel[2], int in_edge, int depth);
+
/* Tries to find the neighboring pixel in given (uv space) direction.
* Result is used by effect system to move paint on the surface.
*
@@ -2370,164 +2382,162 @@ static int dynamic_paint_find_neighbour_pixel(
* TODO: Implement something more accurate / optimized?
*/
{
- const MLoop *mloop = data->mloop;
- const MLoopTri *mlooptri = data->mlooptri;
- const MLoopUV *mloopuv = data->mloopuv;
-
- /* Get closest edge to that subpixel on UV map */
+ DynamicPaintFindIslandBorderData bdata = {
+ .vert_to_looptri_map = vert_to_looptri_map,
+ .w = w, .h = h, .px = px, .py = py,
+ .best_index = NOT_FOUND, .best_weight = 1.0f
+ };
float pixel[2];
- /* distances only used for comparison */
- float dist_squared, t_dist_squared;
-
- int edge1_index, edge2_index;
- int e1_index, e2_index, target_tri;
- float closest_point[2], lambda, dir_vec[2];
- int target_uv1 = 0, target_uv2 = 0, final_pixel[2], final_index;
-
- const float *s_uv1, *s_uv2, *t_uv1, *t_uv2;
pixel[0] = ((float)(px + neighX[n_index]) + 0.5f) / (float)w;
pixel[1] = ((float)(py + neighY[n_index]) + 0.5f) / (float)h;
- /*
- * Find closest edge to that pixel
- */
+ /* Do a small recursive search for the best island edge. */
+ dynamic_paint_find_island_border(data, &bdata, cPoint->tri_index, pixel, -1, 5);
- /* Dist to first edge */
- e1_index = cPoint->v1;
- e2_index = cPoint->v2;
- edge1_index = 0;
- edge2_index = 1;
- dist_squared = dist_squared_to_line_segment_v2(
- pixel,
- mloopuv[mlooptri[cPoint->tri_index].tri[0]].uv,
- mloopuv[mlooptri[cPoint->tri_index].tri[1]].uv);
-
- /* Dist to second edge */
- t_dist_squared = dist_squared_to_line_segment_v2(
- pixel,
- mloopuv[mlooptri[cPoint->tri_index].tri[1]].uv,
- mloopuv[mlooptri[cPoint->tri_index].tri[2]].uv);
- if (t_dist_squared < dist_squared) {
- e1_index = cPoint->v2;
- e2_index = cPoint->v3;
- edge1_index = 1;
- edge2_index = 2;
- dist_squared = t_dist_squared;
- }
-
- /* Dist to third edge */
- t_dist_squared = dist_squared_to_line_segment_v2(
- pixel,
- mloopuv[mlooptri[cPoint->tri_index].tri[2]].uv,
- mloopuv[mlooptri[cPoint->tri_index].tri[0]].uv);
- if (t_dist_squared < dist_squared) {
- e1_index = cPoint->v3;
- e2_index = cPoint->v1;
- edge1_index = 2;
- edge2_index = 0;
- dist_squared = t_dist_squared;
- }
+ return bdata.best_index;
+ }
+}
- /*
- * Now find another face that is linked to that edge
- */
- target_tri = -1;
+static void dynamic_paint_find_island_border(
+ const DynamicPaintCreateUVSurfaceData *data, DynamicPaintFindIslandBorderData *bdata,
+ int tri_index, const float pixel[2], int in_edge, int depth)
+{
+ const MLoop *mloop = data->mloop;
+ const MLoopTri *mlooptri = data->mlooptri;
+ const MLoopUV *mloopuv = data->mloopuv;
- /* Use a pre-computed vert-to-looptri mapping, speeds up things a lot compared to looping over all loopti. */
- for (int i = 0; i < vert_to_looptri_map[e1_index].count; i++) {
- const int lt_index = vert_to_looptri_map[e1_index].indices[i];
- const int v0 = mloop[mlooptri[lt_index].tri[0]].v;
- const int v1 = mloop[mlooptri[lt_index].tri[1]].v;
- const int v2 = mloop[mlooptri[lt_index].tri[2]].v;
+ const unsigned int *loop_idx = mlooptri[tri_index].tri;
- BLI_assert(ELEM(e1_index, v0, v1, v2));
+ /* Enumerate all edges of the triangle, rotating the vertex list accordingly. */
+ for (int edge_idx = 0; edge_idx < 3; edge_idx++) {
+ /* but not the edge we have just recursed through */
+ if (edge_idx == in_edge)
+ continue;
- if (ELEM(e2_index, v0, v1, v2)) {
- if (lt_index == cPoint->tri_index)
- continue;
+ float uv0[2], uv1[2], uv2[2];
- target_tri = lt_index;
+ copy_v2_v2(uv0, mloopuv[loop_idx[(edge_idx + 0)]].uv);
+ copy_v2_v2(uv1, mloopuv[loop_idx[(edge_idx + 1) % 3]].uv);
+ copy_v2_v2(uv2, mloopuv[loop_idx[(edge_idx + 2) % 3]].uv);
- /* Get edge UV index */
- target_uv1 = (e1_index == v0) ? 0 : ((e1_index == v1) ? 1 : 2);
- target_uv2 = (e2_index == v0) ? 0 : ((e2_index == v1) ? 1 : 2);
- break;
- }
- }
+ /* Verify the target point is on the opposite side of the edge from the third triangle
+ * vertex, to ensure that we always move closer to the goal point. */
+ const float sidep = line_point_side_v2(uv0, uv1, pixel);
+ const float side2 = line_point_side_v2(uv0, uv1, uv2);
+
+ if (side2 == 0.0f)
+ continue;
- /* If none found pixel is on mesh edge */
- if (target_tri == -1)
- return ON_MESH_EDGE;
+ /* Hack: allow all edges of the original triangle */
+ const bool correct_side = (in_edge == -1) || (sidep < 0 && side2 > 0) || (sidep > 0 && side2 < 0);
- /*
- * If target face is connected in UV space as well, just use original index
- */
- s_uv1 = mloopuv[mlooptri[cPoint->tri_index].tri[edge1_index]].uv;
- s_uv2 = mloopuv[mlooptri[cPoint->tri_index].tri[edge2_index]].uv;
- t_uv1 = mloopuv[mlooptri[target_tri].tri[target_uv1]].uv;
- t_uv2 = mloopuv[mlooptri[target_tri].tri[target_uv2]].uv;
+ /* Allow exactly on edge for the non-recursive case */
+ if (!correct_side && sidep != 0.0f)
+ continue;
- //printf("connected UV : %f,%f & %f,%f - %f,%f & %f,%f\n", s_uv1[0], s_uv1[1], s_uv2[0], s_uv2[1], t_uv1[0], t_uv1[1], t_uv2[0], t_uv2[1]);
+ /* Now find another face that is linked to that edge. */
+ const int vert0 = mloop[loop_idx[(edge_idx + 0)]].v;
+ const int vert1 = mloop[loop_idx[(edge_idx + 1) % 3]].v;
- if (((s_uv1[0] == t_uv1[0] && s_uv1[1] == t_uv1[1]) &&
- (s_uv2[0] == t_uv2[0] && s_uv2[1] == t_uv2[1])) ||
- ((s_uv2[0] == t_uv1[0] && s_uv2[1] == t_uv1[1]) &&
- (s_uv1[0] == t_uv2[0] && s_uv1[1] == t_uv2[1])))
- {
- final_index = x + w * y;
+ /* Use a pre-computed vert-to-looptri mapping, speeds up things a lot compared to looping over all loopti. */
+ const MeshElemMap *map = &bdata->vert_to_looptri_map[vert0];
+
+ bool found_other = false;
+ int target_tri = -1;
+ int target_edge = -1;
+
+ float ouv0[2], ouv1[2];
+
+ for (int i = 0; i < map->count && !found_other; i++) {
+ const int lt_index = map->indices[i];
+
+ if (lt_index == tri_index)
+ continue;
+
+ const unsigned int *other_loop_idx = mlooptri[lt_index].tri;
+
+ /* Check edges for match, looping in the same order as the outer loop. */
+ for (int j = 0; j < 3; j++)
+ {
+ const int overt0 = mloop[other_loop_idx[(j + 0)]].v;
+ const int overt1 = mloop[other_loop_idx[(j + 1) % 3]].v;
+
+ /* Allow for swapped vertex order */
+ if (overt0 == vert0 && overt1 == vert1) {
+ found_other = true;
+ copy_v2_v2(ouv0, mloopuv[other_loop_idx[(j + 0)]].uv);
+ copy_v2_v2(ouv1, mloopuv[other_loop_idx[(j + 1) % 3]].uv);
+ }
+ else if (overt0 == vert1 && overt1 == vert0) {
+ found_other = true;
+ copy_v2_v2(ouv1, mloopuv[other_loop_idx[(j + 0)]].uv);
+ copy_v2_v2(ouv0, mloopuv[other_loop_idx[(j + 1) % 3]].uv);
+ }
+
+ if (found_other) {
+ target_tri = lt_index;
+ target_edge = j;
+ break;
+ }
+ }
+ }
- /* If not an active pixel, bail out */
- if (tempPoints[final_index].tri_index == -1)
- return NOT_FOUND;
+ if (!found_other) {
+ if (bdata->best_index < 0)
+ bdata->best_index = ON_MESH_EDGE;
- /* If final point is an "edge pixel", use it's "real" neighbor instead */
- if (tempPoints[final_index].neighbour_pixel != -1) {
- final_index = tempPoints[final_index].neighbour_pixel;
+ continue;
+ }
- /* If we ended up to our origin point */
- if (final_index == (px + w * py))
- return NOT_FOUND;
+ /* If this edge is connected in UV space too, recurse */
+ if (equals_v2v2(uv0, ouv0) && equals_v2v2(uv1, ouv1)) {
+ if (depth > 0 && correct_side) {
+ dynamic_paint_find_island_border(data, bdata, target_tri, pixel, target_edge, depth - 1);
}
- return final_index;
+ continue;
}
+ /* Otherwise try to map to the other side of the edge.
+ * First check if there already is a better solution. */
+ const float dist_squared = dist_squared_to_line_segment_v2(pixel, uv0, uv1);
+
+ if (bdata->best_index >= 0 && dist_squared >= bdata->best_weight)
+ continue;
+
/*
* Find a point that is relatively at same edge position
* on this other face UV
*/
- lambda = closest_to_line_v2(
- closest_point, pixel,
- mloopuv[mlooptri[cPoint->tri_index].tri[edge1_index]].uv,
- mloopuv[mlooptri[cPoint->tri_index].tri[edge2_index]].uv);
- CLAMP(lambda, 0.0f, 1.0f);
+ float closest_point[2], dir_vec[2], tgt_pixel[2];
- sub_v2_v2v2(
- dir_vec,
- mloopuv[mlooptri[target_tri].tri[target_uv2]].uv,
- mloopuv[mlooptri[target_tri].tri[target_uv1]].uv);
+ float lambda = closest_to_line_v2(closest_point, pixel, uv0, uv1);
+ CLAMP(lambda, 0.0f, 1.0f);
- mul_v2_fl(dir_vec, lambda);
+ sub_v2_v2v2(dir_vec, ouv1, ouv0);
+ madd_v2_v2v2fl(tgt_pixel, ouv0, dir_vec, lambda);
- copy_v2_v2(pixel, mloopuv[mlooptri[target_tri].tri[target_uv1]].uv);
- add_v2_v2(pixel, dir_vec);
- pixel[0] = (pixel[0] * (float)w);
- pixel[1] = (pixel[1] * (float)h);
+ int w = bdata->w, h = bdata->h, px = bdata->px, py = bdata->py;
- final_pixel[0] = (int)floorf(pixel[0]);
- final_pixel[1] = (int)floorf(pixel[1]);
+ int final_pixel[2] = { (int)floorf(tgt_pixel[0] * w), (int)floorf(tgt_pixel[1] * h) };
/*
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list