Page MenuHome
Differential D16893 Diff 59975 source/blender/blenkernel/intern/mesh_tessellate.cc

Changeset View

Standalone View

View Options

source/blender/blenkernel/intern/mesh_tessellate.cc

Show All 34 Lines
/** \name Loop Tessellation /** \name Loop Tessellation
* *
* Fill in #MLoopTri data-structure. * Fill in #MLoopTri data-structure.
* \{ */ * \{ */
/** /**
* \param face_normal: This will be optimized out as a constant. * \param face_normal: This will be optimized out as a constant.
*/ */
BLI_INLINE void mesh_calc_tessellation_for_face_impl(const MLoop *mloop, BLI_INLINE void mesh_calc_tessellation_for_face_impl(const int *corner_verts,
const MPoly *mpoly, const MPoly *mpoly,
const float (*positions)[3], const float (*positions)[3],
uint poly_index, uint poly_index,
MLoopTri *mlt, MLoopTri *mlt,
MemArena **pf_arena_p, MemArena **pf_arena_p,
const bool face_normal, const bool face_normal,
const float normal_precalc[3]) const float normal_precalc[3])
{ {
const uint mp_loopstart = uint(mpoly[poly_index].loopstart); const uint mp_loopstart = uint(mpoly[poly_index].loopstart);
const uint mp_totloop = uint(mpoly[poly_index].totloop); const uint mp_totloop = uint(mpoly[poly_index].totloop);
#define ML_TO_MLT(i1, i2, i3) \ auto create_tri = [&](uint i1, uint i2, uint i3) {
{ \ mlt->tri[0] = mp_loopstart + i1;
ARRAY_SET_ITEMS(mlt->tri, mp_loopstart + i1, mp_loopstart + i2, mp_loopstart + i3); \ mlt->tri[1] = mp_loopstart + i2;
mlt->poly = poly_index; \ mlt->tri[2] = mp_loopstart + i3;
} \ mlt->poly = poly_index;
((void)0) };
switch (mp_totloop) { switch (mp_totloop) {
case 3: { case 3: {
ML_TO_MLT(0, 1, 2); create_tri(0, 1, 2);
break; break;
} }
case 4: { case 4: {
ML_TO_MLT(0, 1, 2); create_tri(0, 1, 2);
MLoopTri *mlt_a = mlt++; MLoopTri *mlt_a = mlt++;
ML_TO_MLT(0, 2, 3); create_tri(0, 2, 3);
MLoopTri *mlt_b = mlt; MLoopTri *mlt_b = mlt;
if (UNLIKELY(face_normal ? is_quad_flip_v3_first_third_fast_with_normal( if (UNLIKELY(face_normal ? is_quad_flip_v3_first_third_fast_with_normal(
/* Simpler calculation (using the normal). */ /* Simpler calculation (using the normal). */
positions[mloop[mlt_a->tri[0]].v], positions[corner_verts[mlt_a->tri[0]]],
positions[mloop[mlt_a->tri[1]].v], positions[corner_verts[mlt_a->tri[1]]],
positions[mloop[mlt_a->tri[2]].v], positions[corner_verts[mlt_a->tri[2]]],
positions[mloop[mlt_b->tri[2]].v], positions[corner_verts[mlt_b->tri[2]]],
normal_precalc) : normal_precalc) :
is_quad_flip_v3_first_third_fast( is_quad_flip_v3_first_third_fast(
/* Expensive calculation (no normal). */ /* Expensive calculation (no normal). */
positions[mloop[mlt_a->tri[0]].v], positions[corner_verts[mlt_a->tri[0]]],
positions[mloop[mlt_a->tri[1]].v], positions[corner_verts[mlt_a->tri[1]]],
positions[mloop[mlt_a->tri[2]].v], positions[corner_verts[mlt_a->tri[2]]],
positions[mloop[mlt_b->tri[2]].v]))) { positions[corner_verts[mlt_b->tri[2]]]))) {
/* Flip out of degenerate 0-2 state. */ /* Flip out of degenerate 0-2 state. */
mlt_a->tri[2] = mlt_b->tri[2]; mlt_a->tri[2] = mlt_b->tri[2];
mlt_b->tri[0] = mlt_a->tri[1]; mlt_b->tri[0] = mlt_a->tri[1];
} }
break; break;
} }
default: { default: {
const MLoop *ml;
float axis_mat[3][3]; float axis_mat[3][3];
/* Calculate `axis_mat` to project verts to 2D. */ /* Calculate `axis_mat` to project verts to 2D. */
if (face_normal == false) { if (face_normal == false) {
float normal[3]; float normal[3];
const float *co_curr, *co_prev; const float *co_curr, *co_prev;
zero_v3(normal); zero_v3(normal);
/* Calc normal, flipped: to get a positive 2D cross product. */ /* Calc normal, flipped: to get a positive 2D cross product. */
ml = mloop + mp_loopstart; co_prev = positions[corner_verts[mp_totloop - 1]];
co_prev = positions[ml[mp_totloop - 1].v]; for (uint j = 0; j < mp_totloop; j++) {
for (uint j = 0; j < mp_totloop; j++, ml++) { co_curr = positions[corner_verts[mp_loopstart + j]];
co_curr = positions[ml->v];
add_newell_cross_v3_v3v3(normal, co_prev, co_curr); add_newell_cross_v3_v3v3(normal, co_prev, co_curr);
co_prev = co_curr; co_prev = co_curr;
} }
if (UNLIKELY(normalize_v3(normal) == 0.0f)) { if (UNLIKELY(normalize_v3(normal) == 0.0f)) {
normal[2] = 1.0f; normal[2] = 1.0f;
} }
axis_dominant_v3_to_m3_negate(axis_mat, normal); axis_dominant_v3_to_m3_negate(axis_mat, normal);
} }
else { else {
axis_dominant_v3_to_m3_negate(axis_mat, normal_precalc); axis_dominant_v3_to_m3_negate(axis_mat, normal_precalc);
} }
const uint totfilltri = mp_totloop - 2; const uint totfilltri = mp_totloop - 2;
MemArena *pf_arena = *pf_arena_p; MemArena *pf_arena = *pf_arena_p;
if (UNLIKELY(pf_arena == nullptr)) { if (UNLIKELY(pf_arena == nullptr)) {
pf_arena = *pf_arena_p = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, __func__); pf_arena = *pf_arena_p = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, __func__);
} }
uint(*tris)[3] = static_cast<uint(*)[3]>( uint(*tris)[3] = static_cast<uint(*)[3]>(
BLI_memarena_alloc(pf_arena, sizeof(*tris) * size_t(totfilltri))); BLI_memarena_alloc(pf_arena, sizeof(*tris) * size_t(totfilltri)));
float(*projverts)[2] = static_cast<float(*)[2]>( float(*projverts)[2] = static_cast<float(*)[2]>(
BLI_memarena_alloc(pf_arena, sizeof(*projverts) * size_t(mp_totloop))); BLI_memarena_alloc(pf_arena, sizeof(*projverts) * size_t(mp_totloop)));
ml = mloop + mp_loopstart; for (uint j = 0; j < mp_totloop; j++) {
for (uint j = 0; j < mp_totloop; j++, ml++) { mul_v2_m3v3(projverts[j], axis_mat, positions[corner_verts[mp_loopstart + j]]);
mul_v2_m3v3(projverts[j], axis_mat, positions[ml->v]);
} }
BLI_polyfill_calc_arena(projverts, mp_totloop, 1, tris, pf_arena); BLI_polyfill_calc_arena(projverts, mp_totloop, 1, tris, pf_arena);
/* Apply fill. */ /* Apply fill. */
for (uint j = 0; j < totfilltri; j++, mlt++) { for (uint j = 0; j < totfilltri; j++, mlt++) {
const uint *tri = tris[j]; const uint *tri = tris[j];
ML_TO_MLT(tri[0], tri[1], tri[2]); create_tri(tri[0], tri[1], tri[2]);
} }
BLI_memarena_clear(pf_arena); BLI_memarena_clear(pf_arena);
break; break;
} }
} }
#undef ML_TO_MLT #undef ML_TO_MLT
} }
static void mesh_calc_tessellation_for_face(const MLoop *mloop, static void mesh_calc_tessellation_for_face(const int *corner_verts,
const MPoly *mpoly, const MPoly *mpoly,
const float (*positions)[3], const float (*positions)[3],
uint poly_index, uint poly_index,
MLoopTri *mlt, MLoopTri *mlt,
MemArena **pf_arena_p) MemArena **pf_arena_p)
{ {
mesh_calc_tessellation_for_face_impl( mesh_calc_tessellation_for_face_impl(
mloop, mpoly, positions, poly_index, mlt, pf_arena_p, false, nullptr); corner_verts, mpoly, positions, poly_index, mlt, pf_arena_p, false, nullptr);
} }
static void mesh_calc_tessellation_for_face_with_normal(const MLoop *mloop, static void mesh_calc_tessellation_for_face_with_normal(const int *corner_verts,
const MPoly *mpoly, const MPoly *mpoly,
const float (*positions)[3], const float (*positions)[3],
uint poly_index, uint poly_index,
MLoopTri *mlt, MLoopTri *mlt,
MemArena **pf_arena_p, MemArena **pf_arena_p,
const float normal_precalc[3]) const float normal_precalc[3])
{ {
mesh_calc_tessellation_for_face_impl( mesh_calc_tessellation_for_face_impl(
mloop, mpoly, positions, poly_index, mlt, pf_arena_p, true, normal_precalc); corner_verts, mpoly, positions, poly_index, mlt, pf_arena_p, true, normal_precalc);
} }
static void mesh_recalc_looptri__single_threaded(const MLoop *mloop, static void mesh_recalc_looptri__single_threaded(const int *corner_verts,
const MPoly *mpoly, const MPoly *mpoly,
const float (*positions)[3], const float (*positions)[3],
int totloop, int totloop,
int totpoly, int totpoly,
MLoopTri *mlooptri, MLoopTri *mlooptri,
const float (*poly_normals)[3]) const float (*poly_normals)[3])
{ {
MemArena *pf_arena = nullptr; MemArena *pf_arena = nullptr;
const MPoly *mp = mpoly; const MPoly *mp = mpoly;
uint tri_index = 0; uint tri_index = 0;
if (poly_normals != nullptr) { if (poly_normals != nullptr) {
for (uint poly_index = 0; poly_index < uint(totpoly); poly_index++, mp++) { for (uint poly_index = 0; poly_index < uint(totpoly); poly_index++, mp++) {
mesh_calc_tessellation_for_face_with_normal(mloop, mesh_calc_tessellation_for_face_with_normal(corner_verts,
mpoly, mpoly,
positions, positions,
poly_index, poly_index,
&mlooptri[tri_index], &mlooptri[tri_index],
&pf_arena, &pf_arena,
poly_normals[poly_index]); poly_normals[poly_index]);
tri_index += uint(mp->totloop - 2); tri_index += uint(mp->totloop - 2);
} }
} }
else { else {
for (uint poly_index = 0; poly_index < uint(totpoly); poly_index++, mp++) { for (uint poly_index = 0; poly_index < uint(totpoly); poly_index++, mp++) {
mesh_calc_tessellation_for_face( mesh_calc_tessellation_for_face(
mloop, mpoly, positions, poly_index, &mlooptri[tri_index], &pf_arena); corner_verts, mpoly, positions, poly_index, &mlooptri[tri_index], &pf_arena);
tri_index += uint(mp->totloop - 2); tri_index += uint(mp->totloop - 2);
} }
} }
if (pf_arena) { if (pf_arena) {
BLI_memarena_free(pf_arena); BLI_memarena_free(pf_arena);
pf_arena = nullptr; pf_arena = nullptr;
} }
BLI_assert(tri_index == uint(poly_to_tri_count(totpoly, totloop))); BLI_assert(tri_index == uint(poly_to_tri_count(totpoly, totloop)));
UNUSED_VARS_NDEBUG(totloop); UNUSED_VARS_NDEBUG(totloop);
} }
struct TessellationUserData { struct TessellationUserData {
const MLoop *mloop; const int *corner_verts;
const MPoly *mpoly; const MPoly *mpoly;
const float (*positions)[3]; const float (*positions)[3];
/** Output array. */ /** Output array. */
MLoopTri *mlooptri; MLoopTri *mlooptri;
/** Optional pre-calculated polygon normals array. */ /** Optional pre-calculated polygon normals array. */
const float (*poly_normals)[3]; const float (*poly_normals)[3];
}; };
struct TessellationUserTLS { struct TessellationUserTLS {
MemArena *pf_arena; MemArena *pf_arena;
}; };
static void mesh_calc_tessellation_for_face_fn(void *__restrict userdata, static void mesh_calc_tessellation_for_face_fn(void *__restrict userdata,
const int index, const int index,
const TaskParallelTLS *__restrict tls) const TaskParallelTLS *__restrict tls)
{ {
const TessellationUserData *data = static_cast<const TessellationUserData *>(userdata); const TessellationUserData *data = static_cast<const TessellationUserData *>(userdata);
TessellationUserTLS *tls_data = static_cast<TessellationUserTLS *>(tls->userdata_chunk); TessellationUserTLS *tls_data = static_cast<TessellationUserTLS *>(tls->userdata_chunk);
const int tri_index = poly_to_tri_count(index, data->mpoly[index].loopstart); const int tri_index = poly_to_tri_count(index, data->mpoly[index].loopstart);
mesh_calc_tessellation_for_face_impl(data->mloop, mesh_calc_tessellation_for_face_impl(data->corner_verts,
data->mpoly, data->mpoly,
data->positions, data->positions,
uint(index), uint(index),
&data->mlooptri[tri_index], &data->mlooptri[tri_index],
&tls_data->pf_arena, &tls_data->pf_arena,
false, false,
nullptr); nullptr);
} }
static void mesh_calc_tessellation_for_face_with_normal_fn(void *__restrict userdata, static void mesh_calc_tessellation_for_face_with_normal_fn(void *__restrict userdata,
const int index, const int index,
const TaskParallelTLS *__restrict tls) const TaskParallelTLS *__restrict tls)
{ {
const TessellationUserData *data = static_cast<const TessellationUserData *>(userdata); const TessellationUserData *data = static_cast<const TessellationUserData *>(userdata);
TessellationUserTLS *tls_data = static_cast<TessellationUserTLS *>(tls->userdata_chunk); TessellationUserTLS *tls_data = static_cast<TessellationUserTLS *>(tls->userdata_chunk);
const int tri_index = poly_to_tri_count(index, data->mpoly[index].loopstart); const int tri_index = poly_to_tri_count(index, data->mpoly[index].loopstart);
mesh_calc_tessellation_for_face_impl(data->mloop, mesh_calc_tessellation_for_face_impl(data->corner_verts,
data->mpoly, data->mpoly,
data->positions, data->positions,
uint(index), uint(index),
&data->mlooptri[tri_index], &data->mlooptri[tri_index],
&tls_data->pf_arena, &tls_data->pf_arena,
true, true,
data->poly_normals[index]); data->poly_normals[index]);
} }
static void mesh_calc_tessellation_for_face_free_fn(const void *__restrict /*userdata*/, static void mesh_calc_tessellation_for_face_free_fn(const void *__restrict /*userdata*/,
void *__restrict tls_v) void *__restrict tls_v)
{ {
TessellationUserTLS *tls_data = static_cast<TessellationUserTLS *>(tls_v); TessellationUserTLS *tls_data = static_cast<TessellationUserTLS *>(tls_v);
if (tls_data->pf_arena) { if (tls_data->pf_arena) {
BLI_memarena_free(tls_data->pf_arena); BLI_memarena_free(tls_data->pf_arena);
} }
} }
static void mesh_recalc_looptri__multi_threaded(const MLoop *mloop, static void mesh_recalc_looptri__multi_threaded(const int *corner_verts,
const MPoly *mpoly, const MPoly *mpoly,
const float (*positions)[3], const float (*positions)[3],
int /*totloop*/, int /*totloop*/,
int totpoly, int totpoly,
MLoopTri *mlooptri, MLoopTri *mlooptri,
const float (*poly_normals)[3]) const float (*poly_normals)[3])
{ {
struct TessellationUserTLS tls_data_dummy = {nullptr}; struct TessellationUserTLS tls_data_dummy = {nullptr};
struct TessellationUserData data { struct TessellationUserData data {
}; };
data.mloop = mloop; data.corner_verts = corner_verts;
data.mpoly = mpoly; data.mpoly = mpoly;
data.positions = positions; data.positions = positions;
data.mlooptri = mlooptri; data.mlooptri = mlooptri;
data.poly_normals = poly_normals; data.poly_normals = poly_normals;
TaskParallelSettings settings; TaskParallelSettings settings;
BLI_parallel_range_settings_defaults(&settings); BLI_parallel_range_settings_defaults(&settings);
settings.userdata_chunk = &tls_data_dummy; settings.userdata_chunk = &tls_data_dummy;
settings.userdata_chunk_size = sizeof(tls_data_dummy); settings.userdata_chunk_size = sizeof(tls_data_dummy);
settings.func_free = mesh_calc_tessellation_for_face_free_fn; settings.func_free = mesh_calc_tessellation_for_face_free_fn;
BLI_task_parallel_range(0, BLI_task_parallel_range(0,
totpoly, totpoly,
&data, &data,
poly_normals ? mesh_calc_tessellation_for_face_with_normal_fn : poly_normals ? mesh_calc_tessellation_for_face_with_normal_fn :
mesh_calc_tessellation_for_face_fn, mesh_calc_tessellation_for_face_fn,
&settings); &settings);
} }
void BKE_mesh_recalc_looptri(const MLoop *mloop, void BKE_mesh_recalc_looptri(const int *corner_verts,
const MPoly *mpoly, const MPoly *mpoly,
const float (*vert_positions)[3], const float (*vert_positions)[3],
int totloop, int totloop,
int totpoly, int totpoly,
MLoopTri *mlooptri) MLoopTri *mlooptri)
{ {
if (totloop < MESH_FACE_TESSELLATE_THREADED_LIMIT) { if (totloop < MESH_FACE_TESSELLATE_THREADED_LIMIT) {
mesh_recalc_looptri__single_threaded( mesh_recalc_looptri__single_threaded(
mloop, mpoly, vert_positions, totloop, totpoly, mlooptri, nullptr); corner_verts, mpoly, vert_positions, totloop, totpoly, mlooptri, nullptr);
} }
else { else {
mesh_recalc_looptri__multi_threaded( mesh_recalc_looptri__multi_threaded(
mloop, mpoly, vert_positions, totloop, totpoly, mlooptri, nullptr); corner_verts, mpoly, vert_positions, totloop, totpoly, mlooptri, nullptr);
} }
} }
void BKE_mesh_recalc_looptri_with_normals(const MLoop *mloop, void BKE_mesh_recalc_looptri_with_normals(const int *corner_verts,
const MPoly *mpoly, const MPoly *mpoly,
const float (*vert_positions)[3], const float (*vert_positions)[3],
int totloop, int totloop,
int totpoly, int totpoly,
MLoopTri *mlooptri, MLoopTri *mlooptri,
const float (*poly_normals)[3]) const float (*poly_normals)[3])
{ {
BLI_assert(poly_normals != nullptr); BLI_assert(poly_normals != nullptr);
if (totloop < MESH_FACE_TESSELLATE_THREADED_LIMIT) { if (totloop < MESH_FACE_TESSELLATE_THREADED_LIMIT) {
mesh_recalc_looptri__single_threaded( mesh_recalc_looptri__single_threaded(
mloop, mpoly, vert_positions, totloop, totpoly, mlooptri, poly_normals); corner_verts, mpoly, vert_positions, totloop, totpoly, mlooptri, poly_normals);
} }
else { else {
mesh_recalc_looptri__multi_threaded( mesh_recalc_looptri__multi_threaded(
mloop, mpoly, vert_positions, totloop, totpoly, mlooptri, poly_normals); corner_verts, mpoly, vert_positions, totloop, totpoly, mlooptri, poly_normals);
} }
} }
/** \} */ /** \} */