Blender V5.3
sculpt_flood_fill.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2024 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
8
10
11#include "BKE_attribute.hh"
12#include "BKE_mesh.hh"
13#include "BKE_object_types.hh"
14
15#include "DNA_mesh_types.h"
16
17#include "../paint_intern.hh"
18#include "sculpt_hide.hh"
19#include "sculpt_intern.hh"
20
21#include "bmesh.hh"
22
23/* -------------------------------------------------------------------- */
28
30
32{
33 this->queue.push(vertex);
34}
35
37{
38 for (const int vert : verts) {
39 this->add_initial(vert);
40 }
41}
42
44{
45 this->queue.push(vertex);
46}
47
48void FillDataGrids::add_initial(const CCGKey &key, const Span<int> verts)
49{
50 for (const int vert : verts) {
52 }
53}
54
56{
57 this->queue.push(vertex);
58}
59
61{
62 for (const int vert : verts) {
63 this->add_initial(BM_vert_at_index(&bm, vert));
64 }
65}
66
68{
69 this->queue.push(vertex);
70 this->visited_verts[vertex].set();
71}
72
74{
75 this->queue.push(vertex);
76 this->visited_verts[index].set();
77}
78
80{
81 this->queue.push(vertex);
82 this->visited_verts[index].set();
83}
84
86 const GroupedSpan<int> vert_to_face_map,
87 FunctionRef<bool(int from_v, int to_v)> func)
88{
89 Mesh &mesh = *id_cast<Mesh *>(object.data);
90 const OffsetIndices faces = mesh.faces();
91 const Span<int> corner_verts = mesh.corner_verts();
92 const bke::AttributeAccessor attributes = mesh.attributes();
93 const VArraySpan hide_poly = *attributes.lookup<bool>(".hide_poly", bke::AttrDomain::Face);
94 const VArray hide_vert = *attributes.lookup_or_default<bool>(
95 ".hide_vert", bke::AttrDomain::Point, false);
96
97 Vector<int> neighbors;
98 while (!this->queue.empty()) {
99 const int from_v = this->queue.front();
100 this->queue.pop();
101
102 vert_neighbors_get_mesh(faces, corner_verts, vert_to_face_map, hide_poly, from_v, neighbors);
103 if (!this->fake_neighbors.is_empty() && this->fake_neighbors[from_v] != FAKE_NEIGHBOR_NONE) {
104 neighbors.append(this->fake_neighbors[from_v]);
105 }
106
107 for (const int neighbor : neighbors) {
108 if (this->visited_verts[neighbor]) {
109 continue;
110 }
111
112 if (!hide_vert.is_empty() && hide_vert[neighbor]) {
113 continue;
114 }
115
116 this->visited_verts[neighbor].set();
117 if (func(from_v, neighbor)) {
118 this->queue.push(neighbor);
119 }
120 }
121 }
122}
123
125 Object & /*object*/,
126 const SubdivCCG &subdiv_ccg,
127 FunctionRef<bool(SubdivCCGCoord from_v, SubdivCCGCoord to_v, bool is_duplicate)> func)
128{
129 const CCGKey key = BKE_subdiv_ccg_key_top_level(subdiv_ccg);
130 while (!this->queue.empty()) {
131 SubdivCCGCoord from_v = this->queue.front();
132 this->queue.pop();
133
134 SubdivCCGNeighbors neighbors;
135 BKE_subdiv_ccg_neighbor_coords_get(subdiv_ccg, from_v, true, neighbors);
136 if (!this->fake_neighbors.is_empty() &&
137 this->fake_neighbors[from_v.to_index(key)] != FAKE_NEIGHBOR_NONE)
138 {
139 neighbors.coords.insert(
140 0, SubdivCCGCoord::from_index(key, this->fake_neighbors[from_v.to_index(key)]));
141 }
142
143 const int num_unique = neighbors.coords.size() - neighbors.num_duplicates;
144
145 /* Flood fill expects the duplicate entries to be passed to the per-neighbor lambda first, so
146 * iterate from the end of the vector to the beginning. */
147 for (int i = neighbors.coords.size() - 1; i >= 0; i--) {
148 SubdivCCGCoord neighbor = neighbors.coords[i];
149 const int index_in_grid = neighbor.y * key.grid_size + neighbor.x;
150 const int index = neighbor.grid_index * key.grid_area + index_in_grid;
151 if (this->visited_verts[index]) {
152 continue;
153 }
154
155 if (!subdiv_ccg.grid_hidden.is_empty() &&
156 subdiv_ccg.grid_hidden[neighbor.grid_index][index_in_grid])
157 {
158 continue;
159 }
160
161 this->visited_verts[index].set();
162 const bool is_duplicate = i >= num_unique;
163 if (func(from_v, neighbor, is_duplicate)) {
164 this->queue.push(neighbor);
165 }
166 }
167 }
168}
169
170void FillDataBMesh::execute(Object &object, FunctionRef<bool(BMVert *from_v, BMVert *to_v)> func)
171{
172 BMesh *bm = object.runtime->sculpt_session->bm;
173 BMeshNeighborVerts neighbors;
174 while (!this->queue.empty()) {
175 BMVert *from_v = this->queue.front();
176 this->queue.pop();
177
178 if (!this->fake_neighbors.is_empty() &&
179 this->fake_neighbors[BM_elem_index_get(from_v)] != FAKE_NEIGHBOR_NONE)
180 {
181 neighbors.append(BM_vert_at_index(bm, this->fake_neighbors[BM_elem_index_get(from_v)]));
182 }
183
184 for (BMVert *neighbor : vert_neighbors_get_bmesh(*from_v, neighbors)) {
185 const int neighbor_idx = BM_elem_index_get(neighbor);
186 if (this->visited_verts[neighbor_idx]) {
187 continue;
188 }
189
190 if (BM_elem_flag_test(neighbor, BM_ELEM_HIDDEN)) {
191 continue;
192 }
193
194 this->visited_verts[neighbor_idx].set();
195 if (func(from_v, neighbor)) {
196 this->queue.push(neighbor);
197 }
198 }
199 }
200}
201
202} // namespace blender::ed::sculpt_paint::flood_fill
203
#define BM_elem_index_get(ele)
#define BM_elem_flag_test(ele, hflag)
int64_t size() const
void append(const T &value)
void insert(const int64_t insert_index, const T &value)
GAttributeReader lookup_or_default(StringRef name, AttrDomain domain, AttrType data_type, const void *default_value=nullptr) const
GAttributeReader lookup(const StringRef name) const
#define vertex
#define FAKE_NEIGHBOR_NONE
Vector< BMVert *, 64 > BMeshNeighborVerts
Span< BMVert * > vert_neighbors_get_bmesh(BMVert &vert, BMeshNeighborVerts &r_neighbors)
Definition sculpt.cc:490
Span< int > vert_neighbors_get_mesh(const OffsetIndices< int > faces, const Span< int > corner_verts, const GroupedSpan< int > vert_to_face, const Span< bool > hide_poly, const int vert, Vector< int > &r_neighbors)
Definition sculpt.cc:534
CCGKey BKE_subdiv_ccg_key_top_level(const SubdivCCG &subdiv_ccg)
void BKE_subdiv_ccg_neighbor_coords_get(const SubdivCCG &subdiv_ccg, const SubdivCCGCoord &coord, bool include_duplicates, SubdivCCGNeighbors &r_neighbors)
BMesh const char void * data
BLI_INLINE BMVert * BM_vert_at_index(BMesh *bm, const int index)
static SubdivCCGCoord from_index(const CCGKey &key, int index)
int to_index(const CCGKey &key) const
SubdivCCGNeighborCoords coords
BitGroupVector grid_hidden
void execute(Object &object, FunctionRef< bool(BMVert *from_v, BMVert *to_v)> func)
void execute(Object &object, const SubdivCCG &subdiv_ccg, FunctionRef< bool(SubdivCCGCoord from_v, SubdivCCGCoord to_v, bool is_duplicate)> func)
void add_and_skip_initial(SubdivCCGCoord vertex, int index)
void execute(Object &object, GroupedSpan< int > vert_to_face_map, FunctionRef< bool(int from_v, int to_v)> func)