Blender V5.3
extract_mesh_ibo_lines_adjacency.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2021 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
8
9#include <climits>
10
11#include "BLI_map.hh"
12#include "BLI_ordered_edge.hh"
13
14#include "BKE_editmesh.hh"
15
16#include "GPU_index_buffer.hh"
17
18#include "draw_subdivision.hh"
19#include "extract_mesh.hh"
20
21namespace blender::draw {
22
24#define EDGE_IS_UNSET INT_MAX
36#define EDGE_IS_HANDLED (INT_MAX - 1)
37#define EDGE_IS_UNSET_OR_HANDLED(i) ((i) >= EDGE_IS_HANDLED)
38
40 Map<OrderedEdge, int> &edge_hash,
42 bool &is_manifold)
43{
44 for (const auto item : edge_hash.items()) {
45 int v_data = item.value;
46 if (EDGE_IS_UNSET_OR_HANDLED(v_data)) {
47 continue;
48 }
49
50 int v2 = item.key.v_low;
51 int v3 = item.key.v_high;
52
53 int l1 = uint(abs(v_data)) - 1;
54 if (v_data < 0) { /* `inv_opposite`. */
55 std::swap(v2, v3);
56 }
57 int l2 = vert_to_corner[v2];
58 int l3 = vert_to_corner[v3];
59 GPU_indexbuf_add_line_adj_verts(&elb, l1, l2, l3, l1);
60 is_manifold = false;
61 }
62}
63
64inline void rotate_vector(uint3 &value)
65{
66 const uint tmp = value[0];
67 value[0] = value[2];
68 value[2] = value[1];
69 value[1] = tmp;
70}
71
73inline void lines_adjacency_triangle(uint3 vert_tri,
74 uint3 corner_tri,
75 MutableSpan<int> vert_to_corner,
76 Map<OrderedEdge, int> &edge_hash,
78 bool &is_manifold)
79{
80 /* Iterate around the triangle's edges. */
81 for (int e = 0; e < 3; e++) {
82 rotate_vector(vert_tri);
83 rotate_vector(corner_tri);
84
85 bool inv_indices = (vert_tri[1] > vert_tri[2]);
86 edge_hash.add_or_modify(
87 {vert_tri[1], vert_tri[2]},
88 [&](int *value) {
89 int new_value = int(corner_tri[0]) + 1; /* 0 cannot be signed so add one. */
90 *value = inv_indices ? -new_value : new_value;
91 /* Store loop indices for remaining non-manifold edges. */
92 vert_to_corner[vert_tri[1]] = corner_tri[1];
93 vert_to_corner[vert_tri[2]] = corner_tri[2];
94 },
95 [&](int *value) {
96 int v_data = *value;
97 if (v_data == EDGE_IS_UNSET) {
98 int new_value = int(corner_tri[0]) + 1; /* 0 cannot be signed so add one. */
99 *value = inv_indices ? -new_value : new_value;
100 /* Store loop indices for remaining non-manifold edges. */
101 vert_to_corner[vert_tri[1]] = corner_tri[1];
102 vert_to_corner[vert_tri[2]] = corner_tri[2];
103 }
104 else if (v_data == EDGE_IS_HANDLED) [[unlikely]] {
105 /* Ignore additional faces once this has been handled
106 * as this may exceed the pre-sized index buffer: see #150841 & !151084 for details. */
107
108 /* When there are 3+ users of an edge the mesh is not manifold (by definition). */
109 is_manifold = false;
110 }
111 else {
112 /* HACK Tag as not used.
113 * Prevent overhead of removing from the hash as well as potentially adding
114 * the value back in the case more than 2 triangles use this edge. */
115 *value = EDGE_IS_HANDLED;
116 bool inv_opposite = (v_data < 0);
117 const int corner_opposite = abs(v_data) - 1;
118 /* TODO: Make this part thread-safe. */
119 if (inv_opposite == inv_indices) {
120 /* Don't share edge if triangles have non matching winding. */
122 &elb, corner_tri[0], corner_tri[1], corner_tri[2], corner_tri[0]);
124 &elb, corner_opposite, corner_tri[1], corner_tri[2], corner_opposite);
125 is_manifold = false;
126 }
127 else {
129 &elb, corner_tri[0], corner_tri[1], corner_tri[2], corner_opposite);
130 }
131 }
132 });
133 }
134}
135
136static void calc_adjacency_bm(const MeshRenderData &mr,
137 MutableSpan<int> vert_to_corner,
138 Map<OrderedEdge, int> &edge_hash,
140 bool &is_manifold)
141{
143 for (const int i : looptris.index_range()) {
144 const std::array<BMLoop *, 3> &tri = looptris[i];
145 if (BM_elem_flag_test(tri[0]->f, BM_ELEM_HIDDEN)) {
146 continue;
147 }
149 uint3(BM_elem_index_get(tri[0]->v),
150 BM_elem_index_get(tri[1]->v),
151 BM_elem_index_get(tri[2]->v)),
153 vert_to_corner,
154 edge_hash,
155 elb,
156 is_manifold);
157 }
158}
159
161 MutableSpan<int> vert_to_corner,
162 Map<OrderedEdge, int> &edge_hash,
164 bool &is_manifold)
165{
166 const OffsetIndices faces = mr.faces;
167 const Span<int> corner_verts = mr.corner_verts;
168 const Span<bool> hide_poly = mr.hide_poly;
169 const Span<int3> corner_tris = mr.mesh->corner_tris();
170 for (const int face : faces.index_range()) {
171 if (!hide_poly.is_empty() && hide_poly[face]) {
172 continue;
173 }
174 const IndexRange tris = bke::mesh::face_triangles_range(faces, face);
175 for (const int3 &tri : corner_tris.slice(tris)) {
177 uint3(corner_verts[tri[0]], corner_verts[tri[1]], corner_verts[tri[2]]),
178 uint3(tri),
179 vert_to_corner,
180 edge_hash,
181 elb,
182 is_manifold);
183 }
184 }
185}
186
188{
189 /* Similar to poly_to_tri_count().
190 * There is always (loop + triangle - 1) edges inside a face.
191 * Accumulate for all faces and you get : */
192 const int tess_edge_len = mr.corners_num + mr.corner_tris_num - mr.faces_num;
193 Map<OrderedEdge, int> edge_hash;
194 edge_hash.reserve(tess_edge_len);
195 Array<int> vert_to_corner(mr.verts_num, 0);
196 bool is_manifold = true;
197
198 GPUIndexBufBuilder builder;
199 GPU_indexbuf_init(&builder, GPU_PRIM_LINES_ADJ, tess_edge_len, mr.corners_num);
200
202 calc_adjacency_mesh(mr, vert_to_corner, edge_hash, builder, is_manifold);
203 }
204 else {
205 calc_adjacency_bm(mr, vert_to_corner, edge_hash, builder, is_manifold);
206 }
207
208 create_lines_for_remaining_edges(vert_to_corner, edge_hash, builder, is_manifold);
209
210 r_is_manifold = is_manifold;
211
212 return gpu::IndexBufPtr(GPU_indexbuf_build(&builder));
213}
214
216 bool &r_is_manifold)
217{
218 /* For each face there is (loop + triangle - 1) edges. Since we only have quads, and a quad
219 * is split into 2 triangles, we have (loop + 2 - 1) = (loop + 1) edges for each quad, or in
220 * total: (number_of_loops + number_of_quads). */
221 const uint tess_edge_len = subdiv_cache.num_subdiv_loops + subdiv_cache.num_subdiv_quads;
222
223 Array<int> vert_to_corner(subdiv_cache.num_subdiv_verts, 0);
224 Map<OrderedEdge, int> edge_hash;
225 edge_hash.reserve(tess_edge_len);
226
227 bool is_manifold = true;
228
229 GPUIndexBufBuilder builder;
230 GPU_indexbuf_init(&builder, GPU_PRIM_LINES_ADJ, tess_edge_len, subdiv_cache.num_subdiv_loops);
231
232 for (const int subdiv_quad_index : IndexRange(subdiv_cache.num_subdiv_quads)) {
233 const uint loop_index = subdiv_quad_index * 4;
234 const uint corner_0 = loop_index + 0;
235 const uint corner_1 = loop_index + 1;
236 const uint corner_2 = loop_index + 2;
237 const uint corner_3 = loop_index + 3;
238
239 const uint vert_0 = subdiv_cache.subdiv_loop_subdiv_vert_index[corner_0];
240 const uint vert_1 = subdiv_cache.subdiv_loop_subdiv_vert_index[corner_1];
241 const uint vert_2 = subdiv_cache.subdiv_loop_subdiv_vert_index[corner_2];
242 const uint vert_3 = subdiv_cache.subdiv_loop_subdiv_vert_index[corner_3];
243
244 lines_adjacency_triangle({vert_0, vert_1, vert_2},
245 {corner_0, corner_1, corner_2},
246 vert_to_corner,
247 edge_hash,
248 builder,
249 is_manifold);
250 lines_adjacency_triangle({vert_0, vert_2, vert_3},
251 {corner_0, corner_2, corner_3},
252 vert_to_corner,
253 edge_hash,
254 builder,
255 is_manifold);
256 }
257
258 create_lines_for_remaining_edges(vert_to_corner, edge_hash, builder, is_manifold);
259
260 r_is_manifold = is_manifold;
261
262 return gpu::IndexBufPtr(GPU_indexbuf_build(&builder));
263}
264
265#undef EDGE_IS_UNSET
266#undef EDGE_IS_HANDLED
267#undef EDGE_IS_CHECK
268
269} // namespace blender::draw
#define BM_elem_index_get(ele)
#define BM_elem_flag_test(ele, hflag)
constexpr IndexRange()=default
void reserve(int64_t n)
Definition BLI_map.hh:1028
auto add_or_modify(const Key &key, const CreateValueF &create_value, const ModifyValueF &modify_value) -> decltype(create_value(nullptr))
Definition BLI_map.hh:481
ItemIterator items() const &
Definition BLI_map.hh:902
constexpr Span slice(int64_t start, int64_t size) const
Definition BLI_span.hh:141
constexpr IndexRange index_range() const
Definition BLI_span.hh:405
constexpr bool is_empty() const
Definition BLI_span.hh:264
Extraction of Mesh data into VBO to feed to GPU.
#define EDGE_IS_UNSET_OR_HANDLED(i)
#define abs
IndexRange face_triangles_range(OffsetIndices< int > faces, int face_i)
Definition BKE_mesh.hh:359
gpu::IndexBufPtr extract_lines_adjacency_subdiv(const DRWSubdivCache &subdiv_cache, bool &r_is_manifold)
gpu::IndexBufPtr extract_lines_adjacency(const MeshRenderData &mr, bool &r_is_manifold)
static void calc_adjacency_mesh(const MeshRenderData &mr, MutableSpan< int > vert_to_corner, Map< OrderedEdge, int > &edge_hash, GPUIndexBufBuilder &elb, bool &is_manifold)
void lines_adjacency_triangle(uint3 vert_tri, uint3 corner_tri, MutableSpan< int > vert_to_corner, Map< OrderedEdge, int > &edge_hash, GPUIndexBufBuilder &elb, bool &is_manifold)
static void calc_adjacency_bm(const MeshRenderData &mr, MutableSpan< int > vert_to_corner, Map< OrderedEdge, int > &edge_hash, GPUIndexBufBuilder &elb, bool &is_manifold)
static void create_lines_for_remaining_edges(MutableSpan< int > vert_to_corner, Map< OrderedEdge, int > &edge_hash, GPUIndexBufBuilder &elb, bool &is_manifold)
std::unique_ptr< IndexBuf, IndexBufDeleter > IndexBufPtr
void GPU_indexbuf_init(GPUIndexBufBuilder *, GPUPrimType, uint prim_len, uint vertex_len)
unsigned int uint
Definition BKE_text.h:55
@ GPU_PRIM_LINES_ADJ
void GPU_indexbuf_add_line_adj_verts(GPUIndexBufBuilder *, uint v1, uint v2, uint v3, uint v4)
VecBase< uint32_t, 3 > uint3
ATTR_WARN_UNUSED_RESULT const BMVert * v
gpu::IndexBuf * GPU_indexbuf_build(GPUIndexBufBuilder *)
VecBase< int32_t, 3 > int3
ATTR_WARN_UNUSED_RESULT const BMVert * v2
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
Array< std::array< BMLoop *, 3 > > looptris
OffsetIndices< int > faces