blender
/
blender
128
396
Fork 568
Code Issues 6.2k Pull Requests 749 Projects 19 Wiki Activity

UV: support region fill for path select 

This matches edit-mesh region selection (Ctrl-Shift-Select).
This commit is contained in:
Campbell Barton 2020-07-15 17:35:57 +10:00
parent b3c34011c0
commit 613d314251
6 changed files with 598 additions and 12 deletions
Show Stats Download Patch File Download Diff File Expand all files Collapse all files

5
release/scripts/presets/keyconfig/keymap_data/blender_default.py
View File

@ -850,7 +850,10 @@ def km_uv_editor(params):
{"properties": [("extend", False)]}),
("uv.select_loop", {"type": params.select_mouse, "value": params.select_mouse_value, "shift": True, "alt": True},
{"properties": [("extend", True)]}),
("uv.shortest_path_pick", {"type": params.select_mouse, "value": params.select_mouse_value, "ctrl": True}, None),
("uv.shortest_path_pick", {"type": params.select_mouse, "value": params.select_mouse_value, "ctrl": True},
{"properties": [("use_fill", False)]}),
("uv.shortest_path_pick", {"type": params.select_mouse, "value": params.select_mouse_value, "ctrl": True, "shift": True},
{"properties": [("use_fill", True)]}),
("uv.select_split", {"type": 'Y', "value": 'PRESS'}, None),
("uv.select_box", {"type": 'B', "value": 'PRESS'},
{"properties": [("pinned", False)]}),

2
source/blender/bmesh/CMakeLists.txt
View File

@ -155,6 +155,8 @@ set(SRC
tools/bmesh_path_region.h
tools/bmesh_path_uv.c
tools/bmesh_path_uv.h
tools/bmesh_path_region_uv.c
tools/bmesh_path_region_uv.h
tools/bmesh_region_match.c
tools/bmesh_region_match.h
tools/bmesh_separate.c

1
source/blender/bmesh/bmesh_tools.h
View File

@ -36,6 +36,7 @@ extern "C" {
#include "tools/bmesh_edgesplit.h"
#include "tools/bmesh_path.h"
#include "tools/bmesh_path_region.h"
#include "tools/bmesh_path_region_uv.h"
#include "tools/bmesh_path_uv.h"
#include "tools/bmesh_region_match.h"
#include "tools/bmesh_separate.h"

502
source/blender/bmesh/tools/bmesh_path_region_uv.c Normal file
View File

@ -0,0 +1,502 @@
/*
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License
* as published by the Free Software Foundation; either version 2
* of the License, or (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software Foundation,
* Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
*/
/** \file
* \ingroup bmesh
*
* Find the region defined by the path(s) between 2 UV elements.
* (path isn't ordered).
*
* \note This uses the same behavior as bmesh_path_region.c
* however walking UV's causes enough differences that it's
* impractical to share the code.
*/
#include "MEM_guardedalloc.h"
#include "BLI_alloca.h"
#include "BLI_linklist.h"
#include "BLI_math.h"
#include "BLI_utildefines_stack.h"
#include "bmesh.h"
#include "bmesh_path_region_uv.h" /* own include */
/**
* Special handling of vertices with 2 edges
* (act as if the edge-chain is a single edge).
*
* \note Regarding manifold edge stepping: #BM_vert_is_edge_pair_manifold usage.
* Logic to skip a chain of vertices is not applied at boundaries because it gives
* strange behavior from a user perspective especially with boundary quads, see: T52701
*
* Restrict walking over a vertex chain to cases where the edges share the same faces.
* This is more typical of what a user would consider a vertex chain.
*/
#define USE_EDGE_CHAIN
#ifdef USE_EDGE_CHAIN
/**
* Takes a vertex with 2 edge users and assigns the vertices at each end-point,
*
* \return Success when \a l_end_pair values are set or false if the edges loop back on themselves.
*/
static bool bm_loop_pair_ends(BMLoop *l_pivot, BMLoop *l_end_pair[2])
{
int j;
for (j = 0; j < 2; j++) {
BMLoop *l_other = j ? l_pivot->next : l_pivot->prev;
while (BM_vert_is_edge_pair_manifold(l_other->v)) {
l_other = j ? l_other->next : l_other->prev;
if (l_other == l_pivot) {
return false;
}
}
l_end_pair[j] = l_other;
}
BLI_assert(j == 2);
return true;
}
#endif /* USE_EDGE_CHAIN */
/** \name Loop Vertex in Region Checks
* \{ */
static bool bm_loop_region_test(BMLoop *l, int *const depths[2], const int pass)
{
const int index = BM_elem_index_get(l);
return (((depths[0][index] != -1) && (depths[1][index] != -1)) &&
((depths[0][index] + depths[1][index]) < pass));
}
#ifdef USE_EDGE_CHAIN
static bool bm_loop_region_test_chain(BMLoop *l, int *const depths[2], const int pass)
{
BMLoop *l_end_pair[2];
if (bm_loop_region_test(l, depths, pass)) {
return true;
}
if (BM_vert_is_edge_pair_manifold(l->v) && bm_loop_pair_ends(l, l_end_pair) &&
bm_loop_region_test(l_end_pair[0], depths, pass) &&
bm_loop_region_test(l_end_pair[1], depths, pass)) {
return true;
}
return false;
}
#else
static bool bm_loop_region_test_chain(BMLoop *l, int *const depths[2], const int pass)
{
return bm_loop_region_test(l, depths, pass);
}
#endif
/** \} */
/**
* Main logic for calculating region between 2 elements.
*
* This method works walking (breadth first) over all vertices,
* keeping track of topological distance from the source.
*
* This is done in both directions, after that each vertices 'depth' is added to check
* if its less than the number of passes needed to complete the search.
* When it is, we know the path is one of possible paths
* that have the minimum topological distance.
*
* \note Only verts without BM_ELEM_TAG will be walked over.
*/
static LinkNode *mesh_calc_path_region_elem(BMesh *bm,
BMElem *ele_src,
BMElem *ele_dst,
const uint cd_loop_uv_offset,
const char path_htype)
{
int ele_loops_len[2];
BMLoop **ele_loops[2];
/* Get vertices from any `ele_src/ele_dst` elements. */
for (int side = 0; side < 2; side++) {
BMElem *ele = side ? ele_dst : ele_src;
int j = 0;
if (ele->head.htype == BM_FACE) {
BMFace *f = (BMFace *)ele;
ele_loops[side] = BLI_array_alloca(ele_loops[side], f->len);
BMLoop *l_first, *l_iter;
l_iter = l_first = BM_FACE_FIRST_LOOP(f);
do {
ele_loops[side][j++] = l_iter;
} while ((l_iter = l_iter->next) != l_first);
}
else if (ele->head.htype == BM_LOOP) {
if (path_htype == BM_EDGE) {
BMLoop *l = (BMLoop *)ele;
ele_loops[side] = BLI_array_alloca(ele_loops[side], 2);
ele_loops[side][j++] = l;
ele_loops[side][j++] = l->next;
}
else if (path_htype == BM_VERT) {
BMLoop *l = (BMLoop *)ele;
ele_loops[side] = BLI_array_alloca(ele_loops[side], 1);
ele_loops[side][j++] = l;
}
else {
BLI_assert(0);
}
}
else {
BLI_assert(0);
}
ele_loops_len[side] = j;
}
int *depths[2] = {NULL};
int pass = 0;
BMLoop **stack = MEM_mallocN(sizeof(*stack) * bm->totloop, __func__);
BMLoop **stack_other = MEM_mallocN(sizeof(*stack_other) * bm->totloop, __func__);
STACK_DECLARE(stack);
STACK_INIT(stack, bm->totloop);
STACK_DECLARE(stack_other);
STACK_INIT(stack_other, bm->totloop);
BM_mesh_elem_index_ensure(bm, BM_LOOP);
/* After exhausting all possible elements, we should have found all elements on the 'side_other'.
* otherwise, exit early. */
bool found_all = false;
for (int side = 0; side < 2; side++) {
const int side_other = !side;
/* initialize depths to -1 (un-touched), fill in with the depth as we walk over the edges. */
depths[side] = MEM_mallocN(sizeof(*depths[side]) * bm->totloop, __func__);
copy_vn_i(depths[side], bm->totloop, -1);
/* needed for second side */
STACK_CLEAR(stack);
STACK_CLEAR(stack_other);
for (int i = 0; i < ele_loops_len[side]; i++) {
BMLoop *l = ele_loops[side][i];
depths[side][BM_elem_index_get(l)] = 0;
if (!BM_elem_flag_test(l, BM_ELEM_TAG)) {
STACK_PUSH(stack, l);
}
}
#ifdef USE_EDGE_CHAIN
/* Expand initial state to end-point vertices when they only have 2x edges,
* this prevents odd behavior when source or destination are in the middle
* of a long chain of edges. */
if (ELEM(path_htype, BM_VERT, BM_EDGE)) {
for (int i = 0; i < ele_loops_len[side]; i++) {
BMLoop *l = ele_loops[side][i];
BMLoop *l_end_pair[2];
if (BM_vert_is_edge_pair_manifold(l->v) && bm_loop_pair_ends(l, l_end_pair)) {
for (int j = 0; j < 2; j++) {
const int l_end_index = BM_elem_index_get(l_end_pair[j]);
if (depths[side][l_end_index] == -1) {
depths[side][l_end_index] = 0;
if (!BM_elem_flag_test(l_end_pair[j], BM_ELEM_TAG)) {
STACK_PUSH(stack, l_end_pair[j]);
}
}
}
}
}
}
#endif /* USE_EDGE_CHAIN */
/* Keep walking over connected geometry until we find all the vertices in
* `ele_loops[side_other]`, or exit the loop when there's no connection. */
found_all = false;
for (pass = 1; (STACK_SIZE(stack) != 0); pass++) {
while (STACK_SIZE(stack) != 0) {
BMLoop *l_a = STACK_POP(stack);
const int l_a_index = BM_elem_index_get(l_a);
BMIter iter;
BMLoop *l_iter;
BM_ITER_ELEM (l_iter, &iter, l_a->v, BM_LOOPS_OF_VERT) {
if (BM_elem_flag_test(l_iter, BM_ELEM_TAG)) {
continue;
}
if (!BM_loop_uv_share_vert_check(l_a, l_iter, cd_loop_uv_offset)) {
continue;
}
/* Flush the depth to connected loops (only needed for UV's). */
if (depths[side][BM_elem_index_get(l_iter)] == -1) {
depths[side][BM_elem_index_get(l_iter)] = depths[side][l_a_index];
}
for (int j = 0; j < 2; j++) {
BMLoop *l_b = j ? l_iter->next : l_iter->prev;
int l_b_index = BM_elem_index_get(l_b);
if (depths[side][l_b_index] == -1) {
#ifdef USE_EDGE_CHAIN
/* Walk along the chain, fill in values until we reach a vertex with 3+ edges. */
{
while (BM_vert_is_edge_pair_manifold(l_b->v) &&
((depths[side][l_b_index] == -1) &&
/* Don't walk back to the beginning */
(l_b != (j ? l_iter->prev : l_iter->next)))) {
depths[side][l_b_index] = pass;
l_b = j ? l_b->next : l_b->prev;
l_b_index = BM_elem_index_get(l_b);
}
}
#endif /* USE_EDGE_CHAIN */
/* Add the other vertex to the stack, to be traversed in the next pass. */
if (depths[side][l_b_index] == -1) {
#ifdef USE_EDGE_CHAIN
BLI_assert(!BM_vert_is_edge_pair_manifold(l_b->v));
#endif
BLI_assert(pass == depths[side][BM_elem_index_get(l_a)] + 1);
depths[side][l_b_index] = pass;
if (!BM_elem_flag_test(l_b, BM_ELEM_TAG)) {
STACK_PUSH(stack_other, l_b);
}
}
}
}
}
}
/* Stop searching once there's none left.
* Note that this looks in-efficient, however until the target elements reached,
* it will exit immediately.
* After that, it takes as many passes as the element has edges to finish off. */
found_all = true;
for (int i = 0; i < ele_loops_len[side_other]; i++) {
if (depths[side][BM_elem_index_get(ele_loops[side_other][i])] == -1) {
found_all = false;
break;
}
}
if (found_all == true) {
pass++;
break;
}
STACK_SWAP(stack, stack_other);
}
/* if we have nothing left, and didn't find all elements on the other side,
* exit early and don't continue */
if (found_all == false) {
break;
}
}
MEM_freeN(stack);
MEM_freeN(stack_other);
/* Now we have depths recorded from both sides,
* select elements that use tagged verts. */
LinkNode *path = NULL;
if (found_all == false) {
/* fail! (do nothing) */
}
else if (path_htype == BM_FACE) {
BMIter fiter;
BMFace *f;
BM_ITER_MESH (f, &fiter, bm, BM_FACES_OF_MESH) {
if (!BM_elem_flag_test(f, BM_ELEM_TAG)) {
/* check all verts in face are tagged */
BMLoop *l_first, *l_iter;
l_iter = l_first = BM_FACE_FIRST_LOOP(f);
bool ok = true;
#if 0
do {
if (!bm_loop_region_test_chain(l_iter->v, depths, pass)) {
ok = false;
break;
}
} while ((l_iter = l_iter->next) != l_first);
#else
/* Allowing a single failure on a face gives fewer 'gaps'.
* While correct, in practice they're often part of what
* a user would consider the 'region'. */
int ok_tests = f->len > 3 ? 1 : 0; /* how many times we may fail */
do {
if (!bm_loop_region_test_chain(l_iter, depths, pass)) {
if (ok_tests == 0) {
ok = false;
break;
}
ok_tests--;
}
} while ((l_iter = l_iter->next) != l_first);
#endif
if (ok) {
BLI_linklist_prepend(&path, f);
}
}
}
}
else if (path_htype == BM_EDGE) {
BMIter fiter;
BMFace *f;
BM_ITER_MESH (f, &fiter, bm, BM_FACES_OF_MESH) {
BMIter liter;
BMLoop *l;
/* Check the current and next loop vertices are in the region. */
bool l_in_chain_next = bm_loop_region_test_chain(BM_FACE_FIRST_LOOP(f), depths, pass);
BM_ITER_ELEM (l, &liter, f, BM_LOOPS_OF_FACE) {
const bool l_in_chain = l_in_chain_next;
l_in_chain_next = bm_loop_region_test_chain(l->next, depths, pass);
if (l_in_chain && l_in_chain_next) {
BLI_linklist_prepend(&path, l);
}
}
}
}
else if (path_htype == BM_VERT) {
BMIter fiter;
BMFace *f;
BM_ITER_MESH (f, &fiter, bm, BM_FACES_OF_MESH) {
BMIter liter;
BMLoop *l;
BM_ITER_ELEM (l, &liter, f, BM_LOOPS_OF_FACE) {
if (bm_loop_region_test_chain(l, depths, pass)) {
BLI_linklist_prepend(&path, l);
}
}
}
}
for (int side = 0; side < 2; side++) {
if (depths[side]) {
MEM_freeN(depths[side]);
}
}
return path;
}
#undef USE_EDGE_CHAIN
/** \name Main Functions (exposed externally).
* \{ */
LinkNode *BM_mesh_calc_path_uv_region_vert(BMesh *bm,
BMElem *ele_src,
BMElem *ele_dst,
const uint cd_loop_uv_offset,
bool (*filter_fn)(BMLoop *, void *user_data),
void *user_data)
{
LinkNode *path = NULL;
/* BM_ELEM_TAG flag is used to store visited verts */
BMFace *f;
BMIter fiter;
int i = 0;
BM_ITER_MESH (f, &fiter, bm, BM_FACES_OF_MESH) {
BMIter liter;
BMLoop *l;
BM_ITER_ELEM (l, &liter, f, BM_LOOPS_OF_FACE) {
BM_elem_flag_set(l, BM_ELEM_TAG, !filter_fn(l, user_data));
BM_elem_index_set(l, i); /* set_inline */
i += 1;
}
}
bm->elem_index_dirty &= ~BM_LOOP;
path = mesh_calc_path_region_elem(bm, ele_src, ele_dst, cd_loop_uv_offset, BM_VERT);
return path;
}
LinkNode *BM_mesh_calc_path_uv_region_edge(BMesh *bm,
BMElem *ele_src,
BMElem *ele_dst,
const uint cd_loop_uv_offset,
bool (*filter_fn)(BMLoop *, void *user_data),
void *user_data)
{
LinkNode *path = NULL;
/* BM_ELEM_TAG flag is used to store visited verts */
BMFace *f;
BMIter fiter;
int i = 0;
BM_ITER_MESH (f, &fiter, bm, BM_FACES_OF_MESH) {
BMIter liter;
BMLoop *l;
BM_ITER_ELEM (l, &liter, f, BM_LOOPS_OF_FACE) {
BM_elem_flag_set(l, BM_ELEM_TAG, !filter_fn(l, user_data));
BM_elem_index_set(l, i); /* set_inline */
i += 1;
}
}
bm->elem_index_dirty &= ~BM_LOOP;
path = mesh_calc_path_region_elem(bm, ele_src, ele_dst, cd_loop_uv_offset, BM_EDGE);
return path;
}
LinkNode *BM_mesh_calc_path_uv_region_face(BMesh *bm,
BMElem *ele_src,
BMElem *ele_dst,
const uint cd_loop_uv_offset,
bool (*filter_fn)(BMFace *, void *user_data),
void *user_data)
{
LinkNode *path = NULL;
/* BM_ELEM_TAG flag is used to store visited verts */
BMFace *f;
BMIter fiter;
int i;
/* flush flag to verts */
BM_mesh_elem_hflag_enable_all(bm, BM_VERT, BM_ELEM_TAG, false);
BM_ITER_MESH_INDEX (f, &fiter, bm, BM_FACES_OF_MESH, i) {
bool test;
BM_elem_flag_set(f, BM_ELEM_TAG, test = !filter_fn(f, user_data));
/* flush tag to verts */
if (test == false) {
BMLoop *l_first, *l_iter;
l_iter = l_first = BM_FACE_FIRST_LOOP(f);
do {
BM_elem_flag_disable(l_iter->v, BM_ELEM_TAG);
} while ((l_iter = l_iter->next) != l_first);
}
}
path = mesh_calc_path_region_elem(bm, ele_src, ele_dst, cd_loop_uv_offset, BM_FACE);
return path;
}
/** \} */

48
source/blender/bmesh/tools/bmesh_path_region_uv.h Normal file
View File

@ -0,0 +1,48 @@
/*
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License
* as published by the Free Software Foundation; either version 2
* of the License, or (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software Foundation,
* Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
*/
#ifndef __BMESH_PATH_REGION_UV_H__
#define __BMESH_PATH_REGION_UV_H__
/** \file
* \ingroup bmesh
*/
struct LinkNode *BM_mesh_calc_path_uv_region_vert(BMesh *bm,
BMElem *ele_src,
BMElem *ele_dst,
const uint cd_loop_uv_offset,
bool (*test_fn)(BMLoop *, void *user_data),
void *user_data) ATTR_WARN_UNUSED_RESULT
ATTR_NONNULL(1, 2, 3);
struct LinkNode *BM_mesh_calc_path_uv_region_edge(BMesh *bm,
BMElem *ele_src,
BMElem *ele_dst,
const uint cd_loop_uv_offset,
bool (*test_fn)(BMLoop *, void *user_data),
void *user_data) ATTR_WARN_UNUSED_RESULT
ATTR_NONNULL(1, 2, 3);
struct LinkNode *BM_mesh_calc_path_uv_region_face(BMesh *bm,
BMElem *ele_src,
BMElem *ele_dst,
const uint cd_loop_uv_offset,
bool (*test_fn)(BMFace *, void *user_data),
void *user_data) ATTR_WARN_UNUSED_RESULT
ATTR_NONNULL(1, 2, 3);
#endif /* __BMESH_PATH_REGION_UV_H__ */

52
source/blender/editors/uvedit/uvedit_path.c
View File

@ -70,7 +70,7 @@
#include "bmesh_tools.h"
/* TODO(campbell): region filling, matching mesh selection. */
// #define USE_FILL
#define USE_FILL
/* -------------------------------------------------------------------- */
/** \name Local Utilities
@ -258,10 +258,24 @@ static void mouse_mesh_uv_shortest_path_vert(Scene *scene,
.aspect_y = aspect_y,
.cd_loop_uv_offset = cd_loop_uv_offset,
};
LinkNode *path = BM_mesh_calc_path_uv_vert(
bm, l_src, l_dst, &params, looptag_filter_cb, &user_data);
/* TODO: false when we support region selection. */
bool is_path_ordered = true;
LinkNode *path = NULL;
bool is_path_ordered = false;
if (l_src != l_dst) {
if (op_params->use_fill) {
path = BM_mesh_calc_path_uv_region_vert(bm,
(BMElem *)l_src,
(BMElem *)l_dst,
params.cd_loop_uv_offset,
looptag_filter_cb,
&user_data);
}
else {
is_path_ordered = true;
path = BM_mesh_calc_path_uv_vert(bm, l_src, l_dst, &params, looptag_filter_cb, &user_data);
}
}
BMLoop *l_dst_last = l_dst;
@ -374,10 +388,24 @@ static void mouse_mesh_uv_shortest_path_face(Scene *scene,
.aspect_y = aspect_y,
.cd_loop_uv_offset = cd_loop_uv_offset,
};
LinkNode *path = BM_mesh_calc_path_uv_face(
bm, f_src, f_dst, &params, facetag_filter_cb, &user_data);
/* TODO: false when we support region selection. */
bool is_path_ordered = true;
LinkNode *path = NULL;
bool is_path_ordered = false;
if (f_src != f_dst) {
if (op_params->use_fill) {
path = BM_mesh_calc_path_uv_region_face(bm,
(BMElem *)f_src,
(BMElem *)f_dst,
params.cd_loop_uv_offset,
facetag_filter_cb,
&user_data);
}
else {
is_path_ordered = true;
path = BM_mesh_calc_path_uv_face(bm, f_src, f_dst, &params, facetag_filter_cb, &user_data);
}
}
BMFace *f_dst_last = f_dst;
@ -453,8 +481,10 @@ static bool uv_shortest_path_pick_ex(Scene *scene,
const ToolSettings *ts = scene->toolsettings;
BMElem *ele_dst_final = NULL;
if (ts->uv_selectmode & UV_SELECT_EDGE) {
bm_loop_calc_vert_pair_from_edge_pair(
cd_loop_uv_offset, aspect_y, &ele_src, &ele_dst, &ele_dst_final);
if (op_params->use_fill == false) {
bm_loop_calc_vert_pair_from_edge_pair(
cd_loop_uv_offset, aspect_y, &ele_src, &ele_dst, &ele_dst_final);
}
}
mouse_mesh_uv_shortest_path_vert(scene,
obedit,