Blender  V3.3
mesh_tessellate.cc
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later
2  * Copyright 2001-2002 NaN Holding BV. All rights reserved. */
3 
13 #include <climits>
14 
15 #include "MEM_guardedalloc.h"
16 
17 #include "DNA_mesh_types.h"
18 #include "DNA_meshdata_types.h"
19 
20 #include "BLI_math.h"
21 #include "BLI_memarena.h"
22 #include "BLI_polyfill_2d.h"
23 #include "BLI_task.h"
24 #include "BLI_utildefines.h"
25 
26 #include "BKE_customdata.h"
27 #include "BKE_mesh.h" /* Own include. */
28 
29 #include "BLI_strict_flags.h"
30 
32 #define MESH_FACE_TESSELLATE_THREADED_LIMIT 4096
33 
34 /* -------------------------------------------------------------------- */
44  const MPoly *mpoly,
45  const MVert *mvert,
46  uint poly_index,
47  MLoopTri *mlt,
48  MemArena **pf_arena_p,
49  const bool face_normal,
50  const float normal_precalc[3])
51 {
52  const uint mp_loopstart = (uint)mpoly[poly_index].loopstart;
53  const uint mp_totloop = (uint)mpoly[poly_index].totloop;
54 
55 #define ML_TO_MLT(i1, i2, i3) \
56  { \
57  ARRAY_SET_ITEMS(mlt->tri, mp_loopstart + i1, mp_loopstart + i2, mp_loopstart + i3); \
58  mlt->poly = poly_index; \
59  } \
60  ((void)0)
61 
62  switch (mp_totloop) {
63  case 3: {
64  ML_TO_MLT(0, 1, 2);
65  break;
66  }
67  case 4: {
68  ML_TO_MLT(0, 1, 2);
69  MLoopTri *mlt_a = mlt++;
70  ML_TO_MLT(0, 2, 3);
71  MLoopTri *mlt_b = mlt;
72 
74  /* Simpler calculation (using the normal). */
75  mvert[mloop[mlt_a->tri[0]].v].co,
76  mvert[mloop[mlt_a->tri[1]].v].co,
77  mvert[mloop[mlt_a->tri[2]].v].co,
78  mvert[mloop[mlt_b->tri[2]].v].co,
79  normal_precalc) :
81  /* Expensive calculation (no normal). */
82  mvert[mloop[mlt_a->tri[0]].v].co,
83  mvert[mloop[mlt_a->tri[1]].v].co,
84  mvert[mloop[mlt_a->tri[2]].v].co,
85  mvert[mloop[mlt_b->tri[2]].v].co))) {
86  /* Flip out of degenerate 0-2 state. */
87  mlt_a->tri[2] = mlt_b->tri[2];
88  mlt_b->tri[0] = mlt_a->tri[1];
89  }
90  break;
91  }
92  default: {
93  const MLoop *ml;
94  float axis_mat[3][3];
95 
96  /* Calculate `axis_mat` to project verts to 2D. */
97  if (face_normal == false) {
98  float normal[3];
99  const float *co_curr, *co_prev;
100 
101  zero_v3(normal);
102 
103  /* Calc normal, flipped: to get a positive 2D cross product. */
104  ml = mloop + mp_loopstart;
105  co_prev = mvert[ml[mp_totloop - 1].v].co;
106  for (uint j = 0; j < mp_totloop; j++, ml++) {
107  co_curr = mvert[ml->v].co;
108  add_newell_cross_v3_v3v3(normal, co_prev, co_curr);
109  co_prev = co_curr;
110  }
111  if (UNLIKELY(normalize_v3(normal) == 0.0f)) {
112  normal[2] = 1.0f;
113  }
115  }
116  else {
117  axis_dominant_v3_to_m3_negate(axis_mat, normal_precalc);
118  }
119 
120  const uint totfilltri = mp_totloop - 2;
121 
122  MemArena *pf_arena = *pf_arena_p;
123  if (UNLIKELY(pf_arena == nullptr)) {
124  pf_arena = *pf_arena_p = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, __func__);
125  }
126 
127  uint(*tris)[3] = static_cast<uint(*)[3]>(
128  BLI_memarena_alloc(pf_arena, sizeof(*tris) * (size_t)totfilltri));
129  float(*projverts)[2] = static_cast<float(*)[2]>(
130  BLI_memarena_alloc(pf_arena, sizeof(*projverts) * (size_t)mp_totloop));
131 
132  ml = mloop + mp_loopstart;
133  for (uint j = 0; j < mp_totloop; j++, ml++) {
134  mul_v2_m3v3(projverts[j], axis_mat, mvert[ml->v].co);
135  }
136 
137  BLI_polyfill_calc_arena(projverts, mp_totloop, 1, tris, pf_arena);
138 
139  /* Apply fill. */
140  for (uint j = 0; j < totfilltri; j++, mlt++) {
141  const uint *tri = tris[j];
142  ML_TO_MLT(tri[0], tri[1], tri[2]);
143  }
144 
145  BLI_memarena_clear(pf_arena);
146 
147  break;
148  }
149  }
150 #undef ML_TO_MLT
151 }
152 
153 static void mesh_calc_tessellation_for_face(const MLoop *mloop,
154  const MPoly *mpoly,
155  const MVert *mvert,
156  uint poly_index,
157  MLoopTri *mlt,
158  MemArena **pf_arena_p)
159 {
161  mloop, mpoly, mvert, poly_index, mlt, pf_arena_p, false, nullptr);
162 }
163 
165  const MPoly *mpoly,
166  const MVert *mvert,
167  uint poly_index,
168  MLoopTri *mlt,
169  MemArena **pf_arena_p,
170  const float normal_precalc[3])
171 {
173  mloop, mpoly, mvert, poly_index, mlt, pf_arena_p, true, normal_precalc);
174 }
175 
177  const MPoly *mpoly,
178  const MVert *mvert,
179  int totloop,
180  int totpoly,
181  MLoopTri *mlooptri,
182  const float (*poly_normals)[3])
183 {
184  MemArena *pf_arena = nullptr;
185  const MPoly *mp = mpoly;
186  uint tri_index = 0;
187 
188  if (poly_normals != nullptr) {
189  for (uint poly_index = 0; poly_index < (uint)totpoly; poly_index++, mp++) {
191  mpoly,
192  mvert,
193  poly_index,
194  &mlooptri[tri_index],
195  &pf_arena,
196  poly_normals[poly_index]);
197  tri_index += (uint)(mp->totloop - 2);
198  }
199  }
200  else {
201  for (uint poly_index = 0; poly_index < (uint)totpoly; poly_index++, mp++) {
203  mloop, mpoly, mvert, poly_index, &mlooptri[tri_index], &pf_arena);
204  tri_index += (uint)(mp->totloop - 2);
205  }
206  }
207 
208  if (pf_arena) {
209  BLI_memarena_free(pf_arena);
210  pf_arena = nullptr;
211  }
212  BLI_assert(tri_index == (uint)poly_to_tri_count(totpoly, totloop));
213  UNUSED_VARS_NDEBUG(totloop);
214 }
215 
217  const MLoop *mloop;
218  const MPoly *mpoly;
219  const MVert *mvert;
220 
223 
225  const float (*poly_normals)[3];
226 };
227 
230 };
231 
232 static void mesh_calc_tessellation_for_face_fn(void *__restrict userdata,
233  const int index,
234  const TaskParallelTLS *__restrict tls)
235 {
236  const TessellationUserData *data = static_cast<const TessellationUserData *>(userdata);
237  TessellationUserTLS *tls_data = static_cast<TessellationUserTLS *>(tls->userdata_chunk);
238  const int tri_index = poly_to_tri_count(index, data->mpoly[index].loopstart);
240  data->mpoly,
241  data->mvert,
242  (uint)index,
243  &data->mlooptri[tri_index],
244  &tls_data->pf_arena,
245  false,
246  nullptr);
247 }
248 
249 static void mesh_calc_tessellation_for_face_with_normal_fn(void *__restrict userdata,
250  const int index,
251  const TaskParallelTLS *__restrict tls)
252 {
253  const TessellationUserData *data = static_cast<const TessellationUserData *>(userdata);
254  TessellationUserTLS *tls_data = static_cast<TessellationUserTLS *>(tls->userdata_chunk);
255  const int tri_index = poly_to_tri_count(index, data->mpoly[index].loopstart);
257  data->mpoly,
258  data->mvert,
259  (uint)index,
260  &data->mlooptri[tri_index],
261  &tls_data->pf_arena,
262  true,
263  data->poly_normals[index]);
264 }
265 
266 static void mesh_calc_tessellation_for_face_free_fn(const void *__restrict UNUSED(userdata),
267  void *__restrict tls_v)
268 {
269  TessellationUserTLS *tls_data = static_cast<TessellationUserTLS *>(tls_v);
270  if (tls_data->pf_arena) {
271  BLI_memarena_free(tls_data->pf_arena);
272  }
273 }
274 
276  const MPoly *mpoly,
277  const MVert *mvert,
278  int UNUSED(totloop),
279  int totpoly,
280  MLoopTri *mlooptri,
281  const float (*poly_normals)[3])
282 {
283  struct TessellationUserTLS tls_data_dummy = {nullptr};
284 
285  struct TessellationUserData data {
286  };
287  data.mloop = mloop;
288  data.mpoly = mpoly;
289  data.mvert = mvert;
290  data.mlooptri = mlooptri;
291  data.poly_normals = poly_normals;
292 
293  TaskParallelSettings settings;
295 
296  settings.userdata_chunk = &tls_data_dummy;
297  settings.userdata_chunk_size = sizeof(tls_data_dummy);
298 
300 
302  totpoly,
303  &data,
306  &settings);
307 }
308 
309 void BKE_mesh_recalc_looptri(const MLoop *mloop,
310  const MPoly *mpoly,
311  const MVert *mvert,
312  int totloop,
313  int totpoly,
314  MLoopTri *mlooptri)
315 {
316  if (totloop < MESH_FACE_TESSELLATE_THREADED_LIMIT) {
317  mesh_recalc_looptri__single_threaded(mloop, mpoly, mvert, totloop, totpoly, mlooptri, nullptr);
318  }
319  else {
320  mesh_recalc_looptri__multi_threaded(mloop, mpoly, mvert, totloop, totpoly, mlooptri, nullptr);
321  }
322 }
323 
325  const MPoly *mpoly,
326  const MVert *mvert,
327  int totloop,
328  int totpoly,
329  MLoopTri *mlooptri,
330  const float (*poly_normals)[3])
331 {
332  BLI_assert(poly_normals != nullptr);
333  if (totloop < MESH_FACE_TESSELLATE_THREADED_LIMIT) {
335  mloop, mpoly, mvert, totloop, totpoly, mlooptri, poly_normals);
336  }
337  else {
339  mloop, mpoly, mvert, totloop, totpoly, mlooptri, poly_normals);
340  }
341 }
342 
typedef float(TangentPoint)[2]
CustomData interface, see also DNA_customdata_types.h.
#define BLI_assert(a)
Definition: BLI_assert.h:46
#define BLI_INLINE
bool is_quad_flip_v3_first_third_fast_with_normal(const float v1[3], const float v2[3], const float v3[3], const float v4[3], const float normal[3])
Definition: math_geom.c:5882
bool is_quad_flip_v3_first_third_fast(const float v1[3], const float v2[3], const float v3[3], const float v4[3])
Definition: math_geom.c:5867
void axis_dominant_v3_to_m3_negate(float r_mat[3][3], const float normal[3])
Definition: math_geom.c:3544
MINLINE int poly_to_tri_count(int poly_count, int corner_count)
void mul_v2_m3v3(float r[2], const float M[3][3], const float a[3])
Definition: math_matrix.c:917
MINLINE float normalize_v3(float r[3])
MINLINE void add_newell_cross_v3_v3v3(float n[3], const float v_prev[3], const float v_curr[3])
MINLINE void zero_v3(float r[3])
void BLI_memarena_free(struct MemArena *ma) ATTR_NONNULL(1)
Definition: BLI_memarena.c:94
struct MemArena * BLI_memarena_new(size_t bufsize, const char *name) ATTR_WARN_UNUSED_RESULT ATTR_RETURNS_NONNULL ATTR_NONNULL(2) ATTR_MALLOC
Definition: BLI_memarena.c:64
#define BLI_MEMARENA_STD_BUFSIZE
Definition: BLI_memarena.h:20
void * BLI_memarena_alloc(struct MemArena *ma, size_t size) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1) ATTR_MALLOC ATTR_ALLOC_SIZE(2)
Definition: BLI_memarena.c:116
void void BLI_memarena_clear(MemArena *ma) ATTR_NONNULL(1)
Definition: BLI_memarena.c:208
void BLI_polyfill_calc_arena(const float(*coords)[2], unsigned int coords_num, int coords_sign, unsigned int(*r_tris)[3], struct MemArena *arena)
Definition: polyfill_2d.c:830
Strict compiler flags for areas of code we want to ensure don't do conversions without us knowing abo...
unsigned int uint
Definition: BLI_sys_types.h:67
void BLI_task_parallel_range(int start, int stop, void *userdata, TaskParallelRangeFunc func, const TaskParallelSettings *settings)
Definition: task_range.cc:94
BLI_INLINE void BLI_parallel_range_settings_defaults(TaskParallelSettings *settings)
Definition: BLI_task.h:293
#define UNUSED_VARS_NDEBUG(...)
#define UNUSED(x)
#define UNLIKELY(x)
Read Guarded memory(de)allocation.
IconTextureDrawCall normal
void BKE_mesh_recalc_looptri(const MLoop *mloop, const MPoly *mpoly, const MVert *mvert, int totloop, int totpoly, MLoopTri *mlooptri)
static void mesh_calc_tessellation_for_face_with_normal_fn(void *__restrict userdata, const int index, const TaskParallelTLS *__restrict tls)
static void mesh_recalc_looptri__multi_threaded(const MLoop *mloop, const MPoly *mpoly, const MVert *mvert, int UNUSED(totloop), int totpoly, MLoopTri *mlooptri, const float(*poly_normals)[3])
#define ML_TO_MLT(i1, i2, i3)
static void mesh_calc_tessellation_for_face_with_normal(const MLoop *mloop, const MPoly *mpoly, const MVert *mvert, uint poly_index, MLoopTri *mlt, MemArena **pf_arena_p, const float normal_precalc[3])
static void mesh_calc_tessellation_for_face_fn(void *__restrict userdata, const int index, const TaskParallelTLS *__restrict tls)
#define MESH_FACE_TESSELLATE_THREADED_LIMIT
static void mesh_calc_tessellation_for_face_free_fn(const void *__restrict UNUSED(userdata), void *__restrict tls_v)
BLI_INLINE void mesh_calc_tessellation_for_face_impl(const MLoop *mloop, const MPoly *mpoly, const MVert *mvert, uint poly_index, MLoopTri *mlt, MemArena **pf_arena_p, const bool face_normal, const float normal_precalc[3])
void BKE_mesh_recalc_looptri_with_normals(const MLoop *mloop, const MPoly *mpoly, const MVert *mvert, int totloop, int totpoly, MLoopTri *mlooptri, const float(*poly_normals)[3])
static void mesh_recalc_looptri__single_threaded(const MLoop *mloop, const MPoly *mpoly, const MVert *mvert, int totloop, int totpoly, MLoopTri *mlooptri, const float(*poly_normals)[3])
static void mesh_calc_tessellation_for_face(const MLoop *mloop, const MPoly *mpoly, const MVert *mvert, uint poly_index, MLoopTri *mlt, MemArena **pf_arena_p)
unsigned int tri[3]
unsigned int v
float co[3]
TaskParallelFreeFunc func_free
Definition: BLI_task.h:183
size_t userdata_chunk_size
Definition: BLI_task.h:169
const float(* poly_normals)[3]