Blender  V3.3
sculpt_geodesic.c
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later
2  * Copyright 2020 Blender Foundation. All rights reserved. */
3 
8 #include "MEM_guardedalloc.h"
9 
10 #include "BLI_blenlib.h"
11 #include "BLI_linklist_stack.h"
12 #include "BLI_math.h"
13 #include "BLI_task.h"
14 
15 #include "BLT_translation.h"
16 
17 #include "DNA_brush_types.h"
18 #include "DNA_mesh_types.h"
19 #include "DNA_meshdata_types.h"
20 #include "DNA_object_types.h"
21 
22 #include "BKE_brush.h"
23 #include "BKE_ccg.h"
24 #include "BKE_colortools.h"
25 #include "BKE_context.h"
26 #include "BKE_image.h"
27 #include "BKE_mesh.h"
28 #include "BKE_mesh_mapping.h"
29 #include "BKE_multires.h"
30 #include "BKE_node.h"
31 #include "BKE_object.h"
32 #include "BKE_paint.h"
33 #include "BKE_pbvh.h"
34 #include "BKE_scene.h"
35 #include "BKE_subdiv_ccg.h"
36 
37 #include "DEG_depsgraph.h"
38 
39 #include "WM_api.h"
40 #include "WM_message.h"
41 #include "WM_toolsystem.h"
42 #include "WM_types.h"
43 
44 #include "RNA_access.h"
45 #include "RNA_define.h"
46 
47 #include "ED_object.h"
48 #include "ED_screen.h"
49 #include "ED_sculpt.h"
50 #include "ED_view3d.h"
51 #include "paint_intern.h"
52 #include "sculpt_intern.h"
53 
54 #include "IMB_colormanagement.h"
55 #include "IMB_imbuf.h"
56 
57 #include "bmesh.h"
58 
59 #include <math.h>
60 #include <stdlib.h>
61 #define SCULPT_GEODESIC_VERTEX_NONE -1
62 
63 /* Propagate distance from v1 and v2 to v0. */
65  MVert *mvert, const int v0, const int v1, const int v2, float *dists, GSet *initial_vertices)
66 {
67  if (BLI_gset_haskey(initial_vertices, POINTER_FROM_INT(v0))) {
68  return false;
69  }
70 
71  BLI_assert(dists[v1] != FLT_MAX);
72  if (dists[v0] <= dists[v1]) {
73  return false;
74  }
75 
76  float dist0;
78  BLI_assert(dists[v2] != FLT_MAX);
79  if (dists[v0] <= dists[v2]) {
80  return false;
81  }
83  mvert[v0].co, mvert[v1].co, mvert[v2].co, dists[v1], dists[v2]);
84  }
85  else {
86  float vec[3];
87  sub_v3_v3v3(vec, mvert[v1].co, mvert[v0].co);
88  dist0 = dists[v1] + len_v3(vec);
89  }
90 
91  if (dist0 < dists[v0]) {
92  dists[v0] = dist0;
93  return true;
94  }
95 
96  return false;
97 }
98 
100  GSet *initial_vertices,
101  const float limit_radius)
102 {
103  SculptSession *ss = ob->sculpt;
105 
106  const int totvert = mesh->totvert;
107  const int totedge = mesh->totedge;
108 
109  const float limit_radius_sq = limit_radius * limit_radius;
110 
111  MEdge *edges = mesh->medge;
113 
114  float *dists = MEM_malloc_arrayN(totvert, sizeof(float), "distances");
115  BLI_bitmap *edge_tag = BLI_BITMAP_NEW(totedge, "edge tag");
116 
117  if (!ss->epmap) {
119  &ss->epmap_mem,
120  mesh->medge,
121  mesh->totedge,
122  mesh->mpoly,
123  mesh->totpoly,
124  mesh->mloop,
125  mesh->totloop);
126  }
127  if (!ss->vemap) {
129  &ss->vemap, &ss->vemap_mem, mesh->medge, mesh->totvert, mesh->totedge);
130  }
131 
132  /* Both contain edge indices encoded as *void. */
133  BLI_LINKSTACK_DECLARE(queue, void *);
134  BLI_LINKSTACK_DECLARE(queue_next, void *);
135 
137  BLI_LINKSTACK_INIT(queue_next);
138 
139  for (int i = 0; i < totvert; i++) {
140  if (BLI_gset_haskey(initial_vertices, POINTER_FROM_INT(i))) {
141  dists[i] = 0.0f;
142  }
143  else {
144  dists[i] = FLT_MAX;
145  }
146  }
147 
148  /* Masks vertices that are further than limit radius from an initial vertex. As there is no need
149  * to define a distance to them the algorithm can stop earlier by skipping them. */
150  BLI_bitmap *affected_vertex = BLI_BITMAP_NEW(totvert, "affected vertex");
151  GSetIterator gs_iter;
152 
153  if (limit_radius == FLT_MAX) {
154  /* In this case, no need to loop through all initial vertices to check distances as they are
155  * all going to be affected. */
156  BLI_bitmap_set_all(affected_vertex, true, totvert);
157  }
158  else {
159  /* This is an O(n^2) loop used to limit the geodesic distance calculation to a radius. When
160  * this optimization is needed, it is expected for the tool to request the distance to a low
161  * number of vertices (usually just 1 or 2). */
162  GSET_ITER (gs_iter, initial_vertices) {
163  const int v = POINTER_AS_INT(BLI_gsetIterator_getKey(&gs_iter));
164  float *v_co = verts[v].co;
165  for (int i = 0; i < totvert; i++) {
166  if (len_squared_v3v3(v_co, verts[i].co) <= limit_radius_sq) {
167  BLI_BITMAP_ENABLE(affected_vertex, i);
168  }
169  }
170  }
171  }
172 
173  /* Add edges adjacent to an initial vertex to the queue. */
174  for (int i = 0; i < totedge; i++) {
175  const int v1 = edges[i].v1;
176  const int v2 = edges[i].v2;
177  if (!BLI_BITMAP_TEST(affected_vertex, v1) && !BLI_BITMAP_TEST(affected_vertex, v2)) {
178  continue;
179  }
180  if (dists[v1] != FLT_MAX || dists[v2] != FLT_MAX) {
182  }
183  }
184 
185  do {
186  while (BLI_LINKSTACK_SIZE(queue)) {
187  const int e = POINTER_AS_INT(BLI_LINKSTACK_POP(queue));
188  int v1 = edges[e].v1;
189  int v2 = edges[e].v2;
190 
191  if (dists[v1] == FLT_MAX || dists[v2] == FLT_MAX) {
192  if (dists[v1] > dists[v2]) {
193  SWAP(int, v1, v2);
194  }
196  verts, v2, v1, SCULPT_GEODESIC_VERTEX_NONE, dists, initial_vertices);
197  }
198 
199  if (ss->epmap[e].count != 0) {
200  for (int poly_map_index = 0; poly_map_index < ss->epmap[e].count; poly_map_index++) {
201  const int poly = ss->epmap[e].indices[poly_map_index];
202  if (ss->face_sets[poly] <= 0) {
203  continue;
204  }
205  const MPoly *mpoly = &mesh->mpoly[poly];
206 
207  for (int loop_index = 0; loop_index < mpoly->totloop; loop_index++) {
208  const MLoop *mloop = &mesh->mloop[loop_index + mpoly->loopstart];
209  const int v_other = mloop->v;
210  if (ELEM(v_other, v1, v2)) {
211  continue;
212  }
214  verts, v_other, v1, v2, dists, initial_vertices)) {
215  for (int edge_map_index = 0; edge_map_index < ss->vemap[v_other].count;
216  edge_map_index++) {
217  const int e_other = ss->vemap[v_other].indices[edge_map_index];
218  int ev_other;
219  if (edges[e_other].v1 == (uint)v_other) {
220  ev_other = edges[e_other].v2;
221  }
222  else {
223  ev_other = edges[e_other].v1;
224  }
225 
226  if (e_other != e && !BLI_BITMAP_TEST(edge_tag, e_other) &&
227  (ss->epmap[e_other].count == 0 || dists[ev_other] != FLT_MAX)) {
228  if (BLI_BITMAP_TEST(affected_vertex, v_other) ||
229  BLI_BITMAP_TEST(affected_vertex, ev_other)) {
230  BLI_BITMAP_ENABLE(edge_tag, e_other);
231  BLI_LINKSTACK_PUSH(queue_next, POINTER_FROM_INT(e_other));
232  }
233  }
234  }
235  }
236  }
237  }
238  }
239  }
240 
241  for (LinkNode *lnk = queue_next; lnk; lnk = lnk->next) {
242  const int e = POINTER_AS_INT(lnk->link);
243  BLI_BITMAP_DISABLE(edge_tag, e);
244  }
245 
246  BLI_LINKSTACK_SWAP(queue, queue_next);
247 
248  } while (BLI_LINKSTACK_SIZE(queue));
249 
251  BLI_LINKSTACK_FREE(queue_next);
252  MEM_SAFE_FREE(edge_tag);
253  MEM_SAFE_FREE(affected_vertex);
254 
255  return dists;
256 }
257 
258 /* For sculpt mesh data that does not support a geodesic distances algorithm, fallback to the
259  * distance to each vertex. In this case, only one of the initial vertices will be used to
260  * calculate the distance. */
261 static float *SCULPT_geodesic_fallback_create(Object *ob, GSet *initial_vertices)
262 {
263 
264  SculptSession *ss = ob->sculpt;
266  const int totvert = mesh->totvert;
267  float *dists = MEM_malloc_arrayN(totvert, sizeof(float), "distances");
268  int first_affected = SCULPT_GEODESIC_VERTEX_NONE;
269  GSetIterator gs_iter;
270  GSET_ITER (gs_iter, initial_vertices) {
271  first_affected = POINTER_AS_INT(BLI_gsetIterator_getKey(&gs_iter));
272  break;
273  }
274 
275  if (first_affected == SCULPT_GEODESIC_VERTEX_NONE) {
276  for (int i = 0; i < totvert; i++) {
277  dists[i] = FLT_MAX;
278  }
279  return dists;
280  }
281 
282  const float *first_affected_co = SCULPT_vertex_co_get(ss, first_affected);
283  for (int i = 0; i < totvert; i++) {
284  dists[i] = len_v3v3(first_affected_co, SCULPT_vertex_co_get(ss, i));
285  }
286 
287  return dists;
288 }
289 
291  GSet *initial_vertices,
292  const float limit_radius)
293 {
294  SculptSession *ss = ob->sculpt;
295  switch (BKE_pbvh_type(ss->pbvh)) {
296  case PBVH_FACES:
297  return SCULPT_geodesic_mesh_create(ob, initial_vertices, limit_radius);
298  case PBVH_BMESH:
299  case PBVH_GRIDS:
300  return SCULPT_geodesic_fallback_create(ob, initial_vertices);
301  }
302  BLI_assert(false);
303  return NULL;
304 }
305 
307  Object *ob,
308  const int vertex,
309  const float limit_radius)
310 {
311  SculptSession *ss = ob->sculpt;
312  GSet *initial_vertices = BLI_gset_int_new("initial_vertices");
313 
314  const char symm = SCULPT_mesh_symmetry_xyz_get(ob);
315  for (char i = 0; i <= symm; ++i) {
316  if (SCULPT_is_symmetry_iteration_valid(i, symm)) {
317  int v = -1;
318  if (i == 0) {
319  v = vertex;
320  }
321  else {
322  float location[3];
323  flip_v3_v3(location, SCULPT_vertex_co_get(ss, vertex), i);
324  v = SCULPT_nearest_vertex_get(sd, ob, location, FLT_MAX, false);
325  }
326  if (v != -1) {
327  BLI_gset_add(initial_vertices, POINTER_FROM_INT(v));
328  }
329  }
330  }
331 
332  float *dists = SCULPT_geodesic_distances_create(ob, initial_vertices, limit_radius);
333  BLI_gset_free(initial_vertices, NULL);
334  return dists;
335 }
336 
337 float *SCULPT_geodesic_from_vertex(Object *ob, const int vertex, const float limit_radius)
338 {
339  GSet *initial_vertices = BLI_gset_int_new("initial_vertices");
340  BLI_gset_add(initial_vertices, POINTER_FROM_INT(vertex));
341  float *dists = SCULPT_geodesic_distances_create(ob, initial_vertices, limit_radius);
342  BLI_gset_free(initial_vertices, NULL);
343  return dists;
344 }
void BKE_mesh_vert_edge_map_create(MeshElemMap **r_map, int **r_mem, const struct MEdge *medge, int totvert, int totedge)
void BKE_mesh_edge_poly_map_create(MeshElemMap **r_map, int **r_mem, const struct MEdge *medge, int totedge, const struct MPoly *mpoly, int totpoly, const struct MLoop *mloop, int totloop)
General operations, lookup, etc. for blender objects.
struct Mesh * BKE_object_get_original_mesh(const struct Object *object)
A BVH for high poly meshes.
PBVHType BKE_pbvh_type(const PBVH *pbvh)
Definition: pbvh.c:1798
@ PBVH_GRIDS
Definition: BKE_pbvh.h:235
@ PBVH_BMESH
Definition: BKE_pbvh.h:236
@ PBVH_FACES
Definition: BKE_pbvh.h:234
#define BLI_assert(a)
Definition: BLI_assert.h:46
#define BLI_BITMAP_NEW(_num, _alloc_string)
Definition: BLI_bitmap.h:40
#define BLI_BITMAP_TEST(_bitmap, _index)
Definition: BLI_bitmap.h:64
#define BLI_BITMAP_ENABLE(_bitmap, _index)
Definition: BLI_bitmap.h:81
#define BLI_BITMAP_DISABLE(_bitmap, _index)
Definition: BLI_bitmap.h:88
void BLI_bitmap_set_all(BLI_bitmap *bitmap, bool set, size_t bits)
Definition: bitmap.c:17
unsigned int BLI_bitmap
Definition: BLI_bitmap.h:16
struct GSet GSet
Definition: BLI_ghash.h:340
GSet * BLI_gset_int_new(const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT
bool BLI_gset_haskey(const GSet *gs, const void *key) ATTR_WARN_UNUSED_RESULT
Definition: BLI_ghash.c:1007
#define GSET_ITER(gs_iter_, gset_)
Definition: BLI_ghash.h:471
void BLI_gset_free(GSet *gs, GSetKeyFreeFP keyfreefp)
Definition: BLI_ghash.c:1037
BLI_INLINE void * BLI_gsetIterator_getKey(GSetIterator *gsi)
Definition: BLI_ghash.h:458
bool BLI_gset_add(GSet *gs, void *key)
Definition: BLI_ghash.c:969
float geodesic_distance_propagate_across_triangle(const float v0[3], const float v1[3], const float v2[3], float dist1, float dist2)
Definition: math_geom.c:5922
MINLINE float len_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
MINLINE float len_squared_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
MINLINE void sub_v3_v3v3(float r[3], const float a[3], const float b[3])
MINLINE float len_v3(const float a[3]) ATTR_WARN_UNUSED_RESULT
unsigned int uint
Definition: BLI_sys_types.h:67
#define SWAP(type, a, b)
#define POINTER_FROM_INT(i)
#define POINTER_AS_INT(i)
#define ELEM(...)
Object is a sort of wrapper for general info.
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint GLint i2 _GL_VOID_RET _GL_VOID GLint j _GL_VOID_RET _GL_VOID GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble GLdouble GLdouble zFar _GL_VOID_RET _GL_UINT GLdouble *equation _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLenum GLfloat *v _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLfloat *values _GL_VOID_RET _GL_VOID GLushort *values _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLenum GLdouble *params _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_BOOL GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLushort pattern _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint GLdouble v1
Read Guarded memory(de)allocation.
#define MEM_SAFE_FREE(v)
ATTR_WARN_UNUSED_RESULT const BMVert * v2
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
ATTR_WARN_UNUSED_RESULT const BMVert * v
SyclQueue * queue
static float verts[][3]
void *(* MEM_malloc_arrayN)(size_t len, size_t size, const char *str)
Definition: mallocn.c:34
static float limit_radius(const float3 &position_prev, const float3 &position, const float3 &position_next, const float angle_prev, const float angle, const float angle_next, const float radius_prev, const float radius, const float radius_next)
BLI_INLINE void flip_v3_v3(float out[3], const float in[3], const ePaintSymmetryFlags symm)
Definition: paint_intern.h:392
const float * SCULPT_vertex_co_get(SculptSession *ss, int index)
Definition: sculpt.c:125
int SCULPT_nearest_vertex_get(Sculpt *sd, Object *ob, const float co[3], float max_distance, bool use_original)
Definition: sculpt.c:983
bool SCULPT_is_symmetry_iteration_valid(char i, char symm)
Definition: sculpt.c:1025
char SCULPT_mesh_symmetry_xyz_get(Object *object)
Definition: sculpt.c:317
MVert * SCULPT_mesh_deformed_mverts_get(SculptSession *ss)
Definition: sculpt.c:289
static bool sculpt_geodesic_mesh_test_dist_add(MVert *mvert, const int v0, const int v1, const int v2, float *dists, GSet *initial_vertices)
float * SCULPT_geodesic_from_vertex_and_symm(Sculpt *sd, Object *ob, const int vertex, const float limit_radius)
float * SCULPT_geodesic_distances_create(Object *ob, GSet *initial_vertices, const float limit_radius)
float * SCULPT_geodesic_from_vertex(Object *ob, const int vertex, const float limit_radius)
static float * SCULPT_geodesic_fallback_create(Object *ob, GSet *initial_vertices)
static float * SCULPT_geodesic_mesh_create(Object *ob, GSet *initial_vertices, const float limit_radius)
#define SCULPT_GEODESIC_VERTEX_NONE
struct LinkNode * next
Definition: BLI_linklist.h:23
unsigned int v1
unsigned int v2
unsigned int v
struct MEdge * medge
int totedge
int totvert
struct MLoop * mloop
int totpoly
int totloop
struct MPoly * mpoly
struct SculptSession * sculpt
struct MeshElemMap * epmap
Definition: BKE_paint.h:520
int * face_sets
Definition: BKE_paint.h:536
struct MeshElemMap * vemap
Definition: BKE_paint.h:524
int * epmap_mem
Definition: BKE_paint.h:521
struct PBVH * pbvh
Definition: BKE_paint.h:550
int * vemap_mem
Definition: BKE_paint.h:525