From 0a84cc691d7945624ff83256ba083d35f80c3191 Mon Sep 17 00:00:00 2001 From: Hans Goudey Date: Wed, 17 Aug 2022 18:11:01 -0400 Subject: Cleanup: Move subdiv_mesh.c to C++ --- source/blender/blenkernel/intern/subdiv_mesh.cc | 1208 +++++++++++++++++++++++ 1 file changed, 1208 insertions(+) create mode 100644 source/blender/blenkernel/intern/subdiv_mesh.cc (limited to 'source/blender/blenkernel/intern/subdiv_mesh.cc') diff --git a/source/blender/blenkernel/intern/subdiv_mesh.cc b/source/blender/blenkernel/intern/subdiv_mesh.cc new file mode 100644 index 00000000000..d914318b8a5 --- /dev/null +++ b/source/blender/blenkernel/intern/subdiv_mesh.cc @@ -0,0 +1,1208 @@ +/* SPDX-License-Identifier: GPL-2.0-or-later + * Copyright 2018 Blender Foundation. All rights reserved. */ + +/** \file + * \ingroup bke + */ + +#include "atomic_ops.h" + +#include "DNA_key_types.h" +#include "DNA_mesh_types.h" +#include "DNA_meshdata_types.h" + +#include "BLI_array.hh" +#include "BLI_bitmap.h" +#include "BLI_math_vector.h" + +#include "BKE_customdata.h" +#include "BKE_key.h" +#include "BKE_mesh.h" +#include "BKE_subdiv.h" +#include "BKE_subdiv_eval.h" +#include "BKE_subdiv_foreach.h" +#include "BKE_subdiv_mesh.h" + +#include "MEM_guardedalloc.h" + +/* -------------------------------------------------------------------- */ +/** \name Subdivision Context + * \{ */ + +struct SubdivMeshContext { + const SubdivToMeshSettings *settings; + const Mesh *coarse_mesh; + Subdiv *subdiv; + Mesh *subdiv_mesh; + /* Cached custom data arrays for faster access. */ + int *vert_origindex; + int *edge_origindex; + int *loop_origindex; + int *poly_origindex; + /* UV layers interpolation. */ + int num_uv_layers; + MLoopUV *uv_layers[MAX_MTFACE]; + /* Original coordinates (ORCO) interpolation. */ + float (*orco)[3]; + float (*cloth_orco)[3]; + /* Per-subdivided vertex counter of averaged values. */ + int *accumulated_counters; + bool have_displacement; +}; + +static void subdiv_mesh_ctx_cache_uv_layers(SubdivMeshContext *ctx) +{ + Mesh *subdiv_mesh = ctx->subdiv_mesh; + ctx->num_uv_layers = CustomData_number_of_layers(&subdiv_mesh->ldata, CD_MLOOPUV); + for (int layer_index = 0; layer_index < ctx->num_uv_layers; layer_index++) { + ctx->uv_layers[layer_index] = static_cast( + CustomData_get_layer_n(&subdiv_mesh->ldata, CD_MLOOPUV, layer_index)); + } +} + +static void subdiv_mesh_ctx_cache_custom_data_layers(SubdivMeshContext *ctx) +{ + Mesh *subdiv_mesh = ctx->subdiv_mesh; + /* Pointers to original indices layers. */ + ctx->vert_origindex = static_cast( + CustomData_get_layer(&subdiv_mesh->vdata, CD_ORIGINDEX)); + ctx->edge_origindex = static_cast( + CustomData_get_layer(&subdiv_mesh->edata, CD_ORIGINDEX)); + ctx->loop_origindex = static_cast( + CustomData_get_layer(&subdiv_mesh->ldata, CD_ORIGINDEX)); + ctx->poly_origindex = static_cast( + CustomData_get_layer(&subdiv_mesh->pdata, CD_ORIGINDEX)); + /* UV layers interpolation. */ + subdiv_mesh_ctx_cache_uv_layers(ctx); + /* Orco interpolation. */ + ctx->orco = static_cast(CustomData_get_layer(&subdiv_mesh->vdata, CD_ORCO)); + ctx->cloth_orco = static_cast( + CustomData_get_layer(&subdiv_mesh->vdata, CD_CLOTH_ORCO)); +} + +static void subdiv_mesh_prepare_accumulator(SubdivMeshContext *ctx, int num_vertices) +{ + if (!ctx->have_displacement) { + return; + } + ctx->accumulated_counters = static_cast( + MEM_calloc_arrayN(num_vertices, sizeof(*ctx->accumulated_counters), __func__)); +} + +static void subdiv_mesh_context_free(SubdivMeshContext *ctx) +{ + MEM_SAFE_FREE(ctx->accumulated_counters); +} + +/** \} */ + +/* -------------------------------------------------------------------- */ +/** \name Loop custom data copy helpers + * \{ */ + +struct LoopsOfPtex { + /* First loop of the ptex, starts at ptex (0, 0) and goes in u direction. */ + const MLoop *first_loop; + /* Last loop of the ptex, starts at ptex (0, 0) and goes in v direction. */ + const MLoop *last_loop; + /* For quad coarse faces only. */ + const MLoop *second_loop; + const MLoop *third_loop; +}; + +static void loops_of_ptex_get(const SubdivMeshContext *ctx, + LoopsOfPtex *loops_of_ptex, + const MPoly *coarse_poly, + const int ptex_of_poly_index) +{ + const MLoop *coarse_mloop = ctx->coarse_mesh->mloop; + const int first_ptex_loop_index = coarse_poly->loopstart + ptex_of_poly_index; + /* Loop which look in the (opposite) V direction of the current + * ptex face. + * + * TODO(sergey): Get rid of using module on every iteration. */ + const int last_ptex_loop_index = coarse_poly->loopstart + + (ptex_of_poly_index + coarse_poly->totloop - 1) % + coarse_poly->totloop; + loops_of_ptex->first_loop = &coarse_mloop[first_ptex_loop_index]; + loops_of_ptex->last_loop = &coarse_mloop[last_ptex_loop_index]; + if (coarse_poly->totloop == 4) { + loops_of_ptex->second_loop = loops_of_ptex->first_loop + 1; + loops_of_ptex->third_loop = loops_of_ptex->first_loop + 2; + } + else { + loops_of_ptex->second_loop = nullptr; + loops_of_ptex->third_loop = nullptr; + } +} + +/** \} */ + +/* -------------------------------------------------------------------- */ +/** \name Vertex custom data interpolation helpers + * \{ */ + +/* TODO(sergey): Somehow de-duplicate with loops storage, without too much + * exception cases all over the code. */ + +struct VerticesForInterpolation { + /* This field points to a vertex data which is to be used for interpolation. + * The idea is to avoid unnecessary allocations for regular faces, where + * we can simply use corner vertices. */ + const CustomData *vertex_data; + /* Vertices data calculated for ptex corners. There are always 4 elements + * in this custom data, aligned the following way: + * + * index 0 -> uv (0, 0) + * index 1 -> uv (0, 1) + * index 2 -> uv (1, 1) + * index 3 -> uv (1, 0) + * + * Is allocated for non-regular faces (triangles and n-gons). */ + CustomData vertex_data_storage; + bool vertex_data_storage_allocated; + /* Indices within vertex_data to interpolate for. The indices are aligned + * with uv coordinates in a similar way as indices in loop_data_storage. */ + int vertex_indices[4]; +}; + +static void vertex_interpolation_init(const SubdivMeshContext *ctx, + VerticesForInterpolation *vertex_interpolation, + const MPoly *coarse_poly) +{ + const Mesh *coarse_mesh = ctx->coarse_mesh; + const MLoop *coarse_mloop = coarse_mesh->mloop; + if (coarse_poly->totloop == 4) { + vertex_interpolation->vertex_data = &coarse_mesh->vdata; + vertex_interpolation->vertex_indices[0] = coarse_mloop[coarse_poly->loopstart + 0].v; + vertex_interpolation->vertex_indices[1] = coarse_mloop[coarse_poly->loopstart + 1].v; + vertex_interpolation->vertex_indices[2] = coarse_mloop[coarse_poly->loopstart + 2].v; + vertex_interpolation->vertex_indices[3] = coarse_mloop[coarse_poly->loopstart + 3].v; + vertex_interpolation->vertex_data_storage_allocated = false; + } + else { + vertex_interpolation->vertex_data = &vertex_interpolation->vertex_data_storage; + /* Allocate storage for loops corresponding to ptex corners. */ + CustomData_copy(&ctx->coarse_mesh->vdata, + &vertex_interpolation->vertex_data_storage, + CD_MASK_EVERYTHING.vmask, + CD_CALLOC, + 4); + /* Initialize indices. */ + vertex_interpolation->vertex_indices[0] = 0; + vertex_interpolation->vertex_indices[1] = 1; + vertex_interpolation->vertex_indices[2] = 2; + vertex_interpolation->vertex_indices[3] = 3; + vertex_interpolation->vertex_data_storage_allocated = true; + /* Interpolate center of poly right away, it stays unchanged for all + * ptex faces. */ + const float weight = 1.0f / (float)coarse_poly->totloop; + blender::Array weights(coarse_poly->totloop); + blender::Array indices(coarse_poly->totloop); + for (int i = 0; i < coarse_poly->totloop; i++) { + weights[i] = weight; + indices[i] = coarse_mloop[coarse_poly->loopstart + i].v; + } + CustomData_interp(&coarse_mesh->vdata, + &vertex_interpolation->vertex_data_storage, + indices.data(), + weights.data(), + nullptr, + coarse_poly->totloop, + 2); + } +} + +static void vertex_interpolation_from_corner(const SubdivMeshContext *ctx, + VerticesForInterpolation *vertex_interpolation, + const MPoly *coarse_poly, + const int corner) +{ + if (coarse_poly->totloop == 4) { + /* Nothing to do, all indices and data is already assigned. */ + } + else { + const CustomData *vertex_data = &ctx->coarse_mesh->vdata; + const Mesh *coarse_mesh = ctx->coarse_mesh; + const MLoop *coarse_mloop = coarse_mesh->mloop; + LoopsOfPtex loops_of_ptex; + loops_of_ptex_get(ctx, &loops_of_ptex, coarse_poly, corner); + /* Ptex face corner corresponds to a poly loop with same index. */ + CustomData_copy_data(vertex_data, + &vertex_interpolation->vertex_data_storage, + coarse_mloop[coarse_poly->loopstart + corner].v, + 0, + 1); + /* Interpolate remaining ptex face corners, which hits loops + * middle points. + * + * TODO(sergey): Re-use one of interpolation results from previous + * iteration. */ + const float weights[2] = {0.5f, 0.5f}; + const int first_loop_index = loops_of_ptex.first_loop - coarse_mloop; + const int last_loop_index = loops_of_ptex.last_loop - coarse_mloop; + const int first_indices[2] = { + static_cast(coarse_mloop[first_loop_index].v), + static_cast( + coarse_mloop[coarse_poly->loopstart + + (first_loop_index - coarse_poly->loopstart + 1) % coarse_poly->totloop] + .v)}; + const int last_indices[2] = { + static_cast(coarse_mloop[first_loop_index].v), + static_cast(coarse_mloop[last_loop_index].v), + }; + CustomData_interp(vertex_data, + &vertex_interpolation->vertex_data_storage, + first_indices, + weights, + nullptr, + 2, + 1); + CustomData_interp(vertex_data, + &vertex_interpolation->vertex_data_storage, + last_indices, + weights, + nullptr, + 2, + 3); + } +} + +static void vertex_interpolation_end(VerticesForInterpolation *vertex_interpolation) +{ + if (vertex_interpolation->vertex_data_storage_allocated) { + CustomData_free(&vertex_interpolation->vertex_data_storage, 4); + } +} + +/** \} */ + +/* -------------------------------------------------------------------- */ +/** \name Loop custom data interpolation helpers + * \{ */ + +struct LoopsForInterpolation { + /* This field points to a loop data which is to be used for interpolation. + * The idea is to avoid unnecessary allocations for regular faces, where + * we can simply interpolate corner vertices. */ + const CustomData *loop_data; + /* Loops data calculated for ptex corners. There are always 4 elements + * in this custom data, aligned the following way: + * + * index 0 -> uv (0, 0) + * index 1 -> uv (0, 1) + * index 2 -> uv (1, 1) + * index 3 -> uv (1, 0) + * + * Is allocated for non-regular faces (triangles and n-gons). */ + CustomData loop_data_storage; + bool loop_data_storage_allocated; + /* Infices within loop_data to interpolate for. The indices are aligned with + * uv coordinates in a similar way as indices in loop_data_storage. */ + int loop_indices[4]; +}; + +static void loop_interpolation_init(const SubdivMeshContext *ctx, + LoopsForInterpolation *loop_interpolation, + const MPoly *coarse_poly) +{ + const Mesh *coarse_mesh = ctx->coarse_mesh; + if (coarse_poly->totloop == 4) { + loop_interpolation->loop_data = &coarse_mesh->ldata; + loop_interpolation->loop_indices[0] = coarse_poly->loopstart + 0; + loop_interpolation->loop_indices[1] = coarse_poly->loopstart + 1; + loop_interpolation->loop_indices[2] = coarse_poly->loopstart + 2; + loop_interpolation->loop_indices[3] = coarse_poly->loopstart + 3; + loop_interpolation->loop_data_storage_allocated = false; + } + else { + loop_interpolation->loop_data = &loop_interpolation->loop_data_storage; + /* Allocate storage for loops corresponding to ptex corners. */ + CustomData_copy(&ctx->coarse_mesh->ldata, + &loop_interpolation->loop_data_storage, + CD_MASK_EVERYTHING.lmask, + CD_CALLOC, + 4); + /* Initialize indices. */ + loop_interpolation->loop_indices[0] = 0; + loop_interpolation->loop_indices[1] = 1; + loop_interpolation->loop_indices[2] = 2; + loop_interpolation->loop_indices[3] = 3; + loop_interpolation->loop_data_storage_allocated = true; + /* Interpolate center of poly right away, it stays unchanged for all + * ptex faces. */ + const float weight = 1.0f / (float)coarse_poly->totloop; + blender::Array weights(coarse_poly->totloop); + blender::Array indices(coarse_poly->totloop); + for (int i = 0; i < coarse_poly->totloop; i++) { + weights[i] = weight; + indices[i] = coarse_poly->loopstart + i; + } + CustomData_interp(&coarse_mesh->ldata, + &loop_interpolation->loop_data_storage, + indices.data(), + weights.data(), + nullptr, + coarse_poly->totloop, + 2); + } +} + +static void loop_interpolation_from_corner(const SubdivMeshContext *ctx, + LoopsForInterpolation *loop_interpolation, + const MPoly *coarse_poly, + const int corner) +{ + if (coarse_poly->totloop == 4) { + /* Nothing to do, all indices and data is already assigned. */ + } + else { + const CustomData *loop_data = &ctx->coarse_mesh->ldata; + const Mesh *coarse_mesh = ctx->coarse_mesh; + const MLoop *coarse_mloop = coarse_mesh->mloop; + LoopsOfPtex loops_of_ptex; + loops_of_ptex_get(ctx, &loops_of_ptex, coarse_poly, corner); + /* Ptex face corner corresponds to a poly loop with same index. */ + CustomData_free_elem(&loop_interpolation->loop_data_storage, 0, 1); + CustomData_copy_data( + loop_data, &loop_interpolation->loop_data_storage, coarse_poly->loopstart + corner, 0, 1); + /* Interpolate remaining ptex face corners, which hits loops + * middle points. + * + * TODO(sergey): Re-use one of interpolation results from previous + * iteration. */ + const float weights[2] = {0.5f, 0.5f}; + const int base_loop_index = coarse_poly->loopstart; + const int first_loop_index = loops_of_ptex.first_loop - coarse_mloop; + const int second_loop_index = base_loop_index + + (first_loop_index - base_loop_index + 1) % coarse_poly->totloop; + const int first_indices[2] = {first_loop_index, second_loop_index}; + const int last_indices[2] = { + static_cast(loops_of_ptex.last_loop - coarse_mloop), + static_cast(loops_of_ptex.first_loop - coarse_mloop), + }; + CustomData_interp( + loop_data, &loop_interpolation->loop_data_storage, first_indices, weights, nullptr, 2, 1); + CustomData_interp( + loop_data, &loop_interpolation->loop_data_storage, last_indices, weights, nullptr, 2, 3); + } +} + +static void loop_interpolation_end(LoopsForInterpolation *loop_interpolation) +{ + if (loop_interpolation->loop_data_storage_allocated) { + CustomData_free(&loop_interpolation->loop_data_storage, 4); + } +} + +/** \} */ + +/* -------------------------------------------------------------------- */ +/** \name TLS + * \{ */ + +struct SubdivMeshTLS { + bool vertex_interpolation_initialized; + VerticesForInterpolation vertex_interpolation; + const MPoly *vertex_interpolation_coarse_poly; + int vertex_interpolation_coarse_corner; + + bool loop_interpolation_initialized; + LoopsForInterpolation loop_interpolation; + const MPoly *loop_interpolation_coarse_poly; + int loop_interpolation_coarse_corner; +}; + +static void subdiv_mesh_tls_free(void *tls_v) +{ + SubdivMeshTLS *tls = static_cast(tls_v); + if (tls->vertex_interpolation_initialized) { + vertex_interpolation_end(&tls->vertex_interpolation); + } + if (tls->loop_interpolation_initialized) { + loop_interpolation_end(&tls->loop_interpolation); + } +} + +/** \} */ + +/* -------------------------------------------------------------------- */ +/** \name Evaluation helper functions + * \{ */ + +static void subdiv_vertex_orco_evaluate(const SubdivMeshContext *ctx, + const int ptex_face_index, + const float u, + const float v, + const int subdiv_vertex_index) +{ + if (ctx->orco || ctx->cloth_orco) { + float vertex_data[6]; + BKE_subdiv_eval_vertex_data(ctx->subdiv, ptex_face_index, u, v, vertex_data); + + if (ctx->orco) { + copy_v3_v3(ctx->orco[subdiv_vertex_index], vertex_data); + if (ctx->cloth_orco) { + copy_v3_v3(ctx->orco[subdiv_vertex_index], vertex_data + 3); + } + } + else if (ctx->cloth_orco) { + copy_v3_v3(ctx->orco[subdiv_vertex_index], vertex_data); + } + } +} + +/** \} */ + +/* -------------------------------------------------------------------- */ +/** \name Accumulation helpers + * \{ */ + +static void subdiv_accumulate_vertex_displacement(SubdivMeshContext *ctx, + const int ptex_face_index, + const float u, + const float v, + MVert *subdiv_vert) +{ + /* Accumulate displacement. */ + Subdiv *subdiv = ctx->subdiv; + const int subdiv_vertex_index = subdiv_vert - ctx->subdiv_mesh->mvert; + float dummy_P[3], dPdu[3], dPdv[3], D[3]; + BKE_subdiv_eval_limit_point_and_derivatives(subdiv, ptex_face_index, u, v, dummy_P, dPdu, dPdv); + + /* NOTE: The subdivided mesh is allocated in this module, and its vertices are kept at zero + * locations as a default calloc(). */ + BKE_subdiv_eval_displacement(subdiv, ptex_face_index, u, v, dPdu, dPdv, D); + add_v3_v3(subdiv_vert->co, D); + + if (ctx->accumulated_counters) { + ++ctx->accumulated_counters[subdiv_vertex_index]; + } +} + +/** \} */ + +/* -------------------------------------------------------------------- */ +/** \name Callbacks + * \{ */ + +static bool subdiv_mesh_topology_info(const SubdivForeachContext *foreach_context, + const int num_vertices, + const int num_edges, + const int num_loops, + const int num_polygons, + const int *UNUSED(subdiv_polygon_offset)) +{ + /* Multi-resolution grid data will be applied or become invalid after subdivision, + * so don't try to preserve it and use memory. */ + CustomData_MeshMasks mask = CD_MASK_EVERYTHING; + mask.lmask &= ~CD_MASK_MULTIRES_GRIDS; + + SubdivMeshContext *subdiv_context = static_cast(foreach_context->user_data); + subdiv_context->subdiv_mesh = BKE_mesh_new_nomain_from_template_ex( + subdiv_context->coarse_mesh, num_vertices, num_edges, 0, num_loops, num_polygons, mask); + subdiv_mesh_ctx_cache_custom_data_layers(subdiv_context); + subdiv_mesh_prepare_accumulator(subdiv_context, num_vertices); + MEM_SAFE_FREE(subdiv_context->subdiv_mesh->runtime.subsurf_face_dot_tags); + subdiv_context->subdiv_mesh->runtime.subsurf_face_dot_tags = BLI_BITMAP_NEW(num_vertices, + __func__); + return true; +} + +/** \} */ + +/* -------------------------------------------------------------------- */ +/** \name Vertex subdivision process + * \{ */ + +static void subdiv_vertex_data_copy(const SubdivMeshContext *ctx, + const MVert *coarse_vertex, + MVert *subdiv_vertex) +{ + const Mesh *coarse_mesh = ctx->coarse_mesh; + Mesh *subdiv_mesh = ctx->subdiv_mesh; + const int coarse_vertex_index = coarse_vertex - coarse_mesh->mvert; + const int subdiv_vertex_index = subdiv_vertex - subdiv_mesh->mvert; + CustomData_copy_data( + &coarse_mesh->vdata, &ctx->subdiv_mesh->vdata, coarse_vertex_index, subdiv_vertex_index, 1); +} + +static void subdiv_vertex_data_interpolate(const SubdivMeshContext *ctx, + MVert *subdiv_vertex, + const VerticesForInterpolation *vertex_interpolation, + const float u, + const float v) +{ + const int subdiv_vertex_index = subdiv_vertex - ctx->subdiv_mesh->mvert; + const float weights[4] = {(1.0f - u) * (1.0f - v), u * (1.0f - v), u * v, (1.0f - u) * v}; + CustomData_interp(vertex_interpolation->vertex_data, + &ctx->subdiv_mesh->vdata, + vertex_interpolation->vertex_indices, + weights, + nullptr, + 4, + subdiv_vertex_index); + if (ctx->vert_origindex != nullptr) { + ctx->vert_origindex[subdiv_vertex_index] = ORIGINDEX_NONE; + } +} + +static void evaluate_vertex_and_apply_displacement_copy(const SubdivMeshContext *ctx, + const int ptex_face_index, + const float u, + const float v, + const MVert *coarse_vert, + MVert *subdiv_vert) +{ + const int subdiv_vertex_index = subdiv_vert - ctx->subdiv_mesh->mvert; + /* Displacement is accumulated in subdiv vertex position. + * Needs to be backed up before copying data from original vertex. */ + float D[3] = {0.0f, 0.0f, 0.0f}; + if (ctx->have_displacement) { + const float inv_num_accumulated = 1.0f / ctx->accumulated_counters[subdiv_vertex_index]; + copy_v3_v3(D, subdiv_vert->co); + mul_v3_fl(D, inv_num_accumulated); + } + /* Copy custom data and evaluate position. */ + subdiv_vertex_data_copy(ctx, coarse_vert, subdiv_vert); + BKE_subdiv_eval_limit_point(ctx->subdiv, ptex_face_index, u, v, subdiv_vert->co); + /* Apply displacement. */ + add_v3_v3(subdiv_vert->co, D); + /* Evaluate undeformed texture coordinate. */ + subdiv_vertex_orco_evaluate(ctx, ptex_face_index, u, v, subdiv_vertex_index); + /* Remove facedot flag. This can happen if there is more than one subsurf modifier. */ + BLI_BITMAP_DISABLE(ctx->subdiv_mesh->runtime.subsurf_face_dot_tags, subdiv_vertex_index); +} + +static void evaluate_vertex_and_apply_displacement_interpolate( + const SubdivMeshContext *ctx, + const int ptex_face_index, + const float u, + const float v, + VerticesForInterpolation *vertex_interpolation, + MVert *subdiv_vert) +{ + const int subdiv_vertex_index = subdiv_vert - ctx->subdiv_mesh->mvert; + /* Displacement is accumulated in subdiv vertex position. + * Needs to be backed up before copying data from original vertex. */ + float D[3] = {0.0f, 0.0f, 0.0f}; + if (ctx->have_displacement) { + const float inv_num_accumulated = 1.0f / ctx->accumulated_counters[subdiv_vertex_index]; + copy_v3_v3(D, subdiv_vert->co); + mul_v3_fl(D, inv_num_accumulated); + } + /* Interpolate custom data and evaluate position. */ + subdiv_vertex_data_interpolate(ctx, subdiv_vert, vertex_interpolation, u, v); + BKE_subdiv_eval_limit_point(ctx->subdiv, ptex_face_index, u, v, subdiv_vert->co); + /* Apply displacement. */ + add_v3_v3(subdiv_vert->co, D); + /* Evaluate undeformed texture coordinate. */ + subdiv_vertex_orco_evaluate(ctx, ptex_face_index, u, v, subdiv_vertex_index); +} + +static void subdiv_mesh_vertex_displacement_every_corner_or_edge( + const SubdivForeachContext *foreach_context, + void *UNUSED(tls), + const int ptex_face_index, + const float u, + const float v, + const int subdiv_vertex_index) +{ + SubdivMeshContext *ctx = static_cast(foreach_context->user_data); + Mesh *subdiv_mesh = ctx->subdiv_mesh; + MVert *subdiv_mvert = subdiv_mesh->mvert; + MVert *subdiv_vert = &subdiv_mvert[subdiv_vertex_index]; + subdiv_accumulate_vertex_displacement(ctx, ptex_face_index, u, v, subdiv_vert); +} + +static void subdiv_mesh_vertex_displacement_every_corner( + const SubdivForeachContext *foreach_context, + void *tls, + const int ptex_face_index, + const float u, + const float v, + const int UNUSED(coarse_vertex_index), + const int UNUSED(coarse_poly_index), + const int UNUSED(coarse_corner), + const int subdiv_vertex_index) +{ + subdiv_mesh_vertex_displacement_every_corner_or_edge( + foreach_context, tls, ptex_face_index, u, v, subdiv_vertex_index); +} + +static void subdiv_mesh_vertex_displacement_every_edge(const SubdivForeachContext *foreach_context, + void *tls, + const int ptex_face_index, + const float u, + const float v, + const int UNUSED(coarse_edge_index), + const int UNUSED(coarse_poly_index), + const int UNUSED(coarse_corner), + const int subdiv_vertex_index) +{ + subdiv_mesh_vertex_displacement_every_corner_or_edge( + foreach_context, tls, ptex_face_index, u, v, subdiv_vertex_index); +} + +static void subdiv_mesh_vertex_corner(const SubdivForeachContext *foreach_context, + void *UNUSED(tls), + const int ptex_face_index, + const float u, + const float v, + const int coarse_vertex_index, + const int UNUSED(coarse_poly_index), + const int UNUSED(coarse_corner), + const int subdiv_vertex_index) +{ + BLI_assert(coarse_vertex_index != ORIGINDEX_NONE); + SubdivMeshContext *ctx = static_cast(foreach_context->user_data); + const Mesh *coarse_mesh = ctx->coarse_mesh; + const MVert *coarse_mvert = coarse_mesh->mvert; + Mesh *subdiv_mesh = ctx->subdiv_mesh; + MVert *subdiv_mvert = subdiv_mesh->mvert; + const MVert *coarse_vert = &coarse_mvert[coarse_vertex_index]; + MVert *subdiv_vert = &subdiv_mvert[subdiv_vertex_index]; + evaluate_vertex_and_apply_displacement_copy( + ctx, ptex_face_index, u, v, coarse_vert, subdiv_vert); +} + +static void subdiv_mesh_ensure_vertex_interpolation(SubdivMeshContext *ctx, + SubdivMeshTLS *tls, + const MPoly *coarse_poly, + const int coarse_corner) +{ + /* Check whether we've moved to another corner or polygon. */ + if (tls->vertex_interpolation_initialized) { + if (tls->vertex_interpolation_coarse_poly != coarse_poly || + tls->vertex_interpolation_coarse_corner != coarse_corner) { + vertex_interpolation_end(&tls->vertex_interpolation); + tls->vertex_interpolation_initialized = false; + } + } + /* Initialize the interpolation. */ + if (!tls->vertex_interpolation_initialized) { + vertex_interpolation_init(ctx, &tls->vertex_interpolation, coarse_poly); + } + /* Update it for a new corner if needed. */ + if (!tls->vertex_interpolation_initialized || + tls->vertex_interpolation_coarse_corner != coarse_corner) { + vertex_interpolation_from_corner(ctx, &tls->vertex_interpolation, coarse_poly, coarse_corner); + } + /* Store settings used for the current state of interpolator. */ + tls->vertex_interpolation_initialized = true; + tls->vertex_interpolation_coarse_poly = coarse_poly; + tls->vertex_interpolation_coarse_corner = coarse_corner; +} + +static void subdiv_mesh_vertex_edge(const SubdivForeachContext *foreach_context, + void *tls_v, + const int ptex_face_index, + const float u, + const float v, + const int UNUSED(coarse_edge_index), + const int coarse_poly_index, + const int coarse_corner, + const int subdiv_vertex_index) +{ + SubdivMeshContext *ctx = static_cast(foreach_context->user_data); + SubdivMeshTLS *tls = static_cast(tls_v); + const Mesh *coarse_mesh = ctx->coarse_mesh; + const MPoly *coarse_mpoly = coarse_mesh->mpoly; + const MPoly *coarse_poly = &coarse_mpoly[coarse_poly_index]; + Mesh *subdiv_mesh = ctx->subdiv_mesh; + MVert *subdiv_mvert = subdiv_mesh->mvert; + MVert *subdiv_vert = &subdiv_mvert[subdiv_vertex_index]; + subdiv_mesh_ensure_vertex_interpolation(ctx, tls, coarse_poly, coarse_corner); + evaluate_vertex_and_apply_displacement_interpolate( + ctx, ptex_face_index, u, v, &tls->vertex_interpolation, subdiv_vert); +} + +static bool subdiv_mesh_is_center_vertex(const MPoly *coarse_poly, const float u, const float v) +{ + if (coarse_poly->totloop == 4) { + if (u == 0.5f && v == 0.5f) { + return true; + } + } + else { + if (u == 1.0f && v == 1.0f) { + return true; + } + } + return false; +} + +static void subdiv_mesh_tag_center_vertex(const MPoly *coarse_poly, + const int subdiv_vertex_index, + const float u, + const float v, + Mesh *subdiv_mesh) +{ + if (subdiv_mesh_is_center_vertex(coarse_poly, u, v)) { + BLI_BITMAP_ENABLE(subdiv_mesh->runtime.subsurf_face_dot_tags, subdiv_vertex_index); + } +} + +static void subdiv_mesh_vertex_inner(const SubdivForeachContext *foreach_context, + void *tls_v, + const int ptex_face_index, + const float u, + const float v, + const int coarse_poly_index, + const int coarse_corner, + const int subdiv_vertex_index) +{ + SubdivMeshContext *ctx = static_cast(foreach_context->user_data); + SubdivMeshTLS *tls = static_cast(tls_v); + Subdiv *subdiv = ctx->subdiv; + const Mesh *coarse_mesh = ctx->coarse_mesh; + const MPoly *coarse_mpoly = coarse_mesh->mpoly; + const MPoly *coarse_poly = &coarse_mpoly[coarse_poly_index]; + Mesh *subdiv_mesh = ctx->subdiv_mesh; + MVert *subdiv_mvert = subdiv_mesh->mvert; + MVert *subdiv_vert = &subdiv_mvert[subdiv_vertex_index]; + subdiv_mesh_ensure_vertex_interpolation(ctx, tls, coarse_poly, coarse_corner); + subdiv_vertex_data_interpolate(ctx, subdiv_vert, &tls->vertex_interpolation, u, v); + BKE_subdiv_eval_final_point(subdiv, ptex_face_index, u, v, subdiv_vert->co); + subdiv_mesh_tag_center_vertex(coarse_poly, subdiv_vertex_index, u, v, subdiv_mesh); + subdiv_vertex_orco_evaluate(ctx, ptex_face_index, u, v, subdiv_vertex_index); +} + +/** \} */ + +/* -------------------------------------------------------------------- */ +/** \name Edge subdivision process + * \{ */ + +static void subdiv_copy_edge_data(SubdivMeshContext *ctx, + MEdge *subdiv_edge, + const MEdge *coarse_edge) +{ + const int subdiv_edge_index = subdiv_edge - ctx->subdiv_mesh->medge; + if (coarse_edge == nullptr) { + subdiv_edge->crease = 0; + subdiv_edge->bweight = 0; + subdiv_edge->flag = 0; + if (!ctx->settings->use_optimal_display) { + subdiv_edge->flag |= ME_EDGERENDER; + } + if (ctx->edge_origindex != nullptr) { + ctx->edge_origindex[subdiv_edge_index] = ORIGINDEX_NONE; + } + return; + } + const int coarse_edge_index = coarse_edge - ctx->coarse_mesh->medge; + CustomData_copy_data( + &ctx->coarse_mesh->edata, &ctx->subdiv_mesh->edata, coarse_edge_index, subdiv_edge_index, 1); + subdiv_edge->flag |= ME_EDGERENDER; +} + +static void subdiv_mesh_edge(const SubdivForeachContext *foreach_context, + void *UNUSED(tls), + const int coarse_edge_index, + const int subdiv_edge_index, + const bool UNUSED(is_loose), + const int subdiv_v1, + const int subdiv_v2) +{ + SubdivMeshContext *ctx = static_cast(foreach_context->user_data); + Mesh *subdiv_mesh = ctx->subdiv_mesh; + MEdge *subdiv_medge = subdiv_mesh->medge; + MEdge *subdiv_edge = &subdiv_medge[subdiv_edge_index]; + const MEdge *coarse_edge = nullptr; + if (coarse_edge_index != ORIGINDEX_NONE) { + const Mesh *coarse_mesh = ctx->coarse_mesh; + const MEdge *coarse_medge = coarse_mesh->medge; + coarse_edge = &coarse_medge[coarse_edge_index]; + } + subdiv_copy_edge_data(ctx, subdiv_edge, coarse_edge); + subdiv_edge->v1 = subdiv_v1; + subdiv_edge->v2 = subdiv_v2; +} + +/** \} */ + +/* -------------------------------------------------------------------- */ +/** \name Loops creation/interpolation + * \{ */ + +static void subdiv_interpolate_loop_data(const SubdivMeshContext *ctx, + MLoop *subdiv_loop, + const LoopsForInterpolation *loop_interpolation, + const float u, + const float v) +{ + const int subdiv_loop_index = subdiv_loop - ctx->subdiv_mesh->mloop; + const float weights[4] = {(1.0f - u) * (1.0f - v), u * (1.0f - v), u * v, (1.0f - u) * v}; + CustomData_interp(loop_interpolation->loop_data, + &ctx->subdiv_mesh->ldata, + loop_interpolation->loop_indices, + weights, + nullptr, + 4, + subdiv_loop_index); + /* TODO(sergey): Set ORIGINDEX. */ +} + +static void subdiv_eval_uv_layer(SubdivMeshContext *ctx, + MLoop *subdiv_loop, + const int ptex_face_index, + const float u, + const float v) +{ + if (ctx->num_uv_layers == 0) { + return; + } + Subdiv *subdiv = ctx->subdiv; + const int mloop_index = subdiv_loop - ctx->subdiv_mesh->mloop; + for (int layer_index = 0; layer_index < ctx->num_uv_layers; layer_index++) { + MLoopUV *subdiv_loopuv = &ctx->uv_layers[layer_index][mloop_index]; + BKE_subdiv_eval_face_varying(subdiv, layer_index, ptex_face_index, u, v, subdiv_loopuv->uv); + } +} + +static void subdiv_mesh_ensure_loop_interpolation(SubdivMeshContext *ctx, + SubdivMeshTLS *tls, + const MPoly *coarse_poly, + const int coarse_corner) +{ + /* Check whether we've moved to another corner or polygon. */ + if (tls->loop_interpolation_initialized) { + if (tls->loop_interpolation_coarse_poly != coarse_poly || + tls->loop_interpolation_coarse_corner != coarse_corner) { + loop_interpolation_end(&tls->loop_interpolation); + tls->loop_interpolation_initialized = false; + } + } + /* Initialize the interpolation. */ + if (!tls->loop_interpolation_initialized) { + loop_interpolation_init(ctx, &tls->loop_interpolation, coarse_poly); + } + /* Update it for a new corner if needed. */ + if (!tls->loop_interpolation_initialized || + tls->loop_interpolation_coarse_corner != coarse_corner) { + loop_interpolation_from_corner(ctx, &tls->loop_interpolation, coarse_poly, coarse_corner); + } + /* Store settings used for the current state of interpolator. */ + tls->loop_interpolation_initialized = true; + tls->loop_interpolation_coarse_poly = coarse_poly; + tls->loop_interpolation_coarse_corner = coarse_corner; +} + +static void subdiv_mesh_loop(const SubdivForeachContext *foreach_context, + void *tls_v, + const int ptex_face_index, + const float u, + const float v, + const int UNUSED(coarse_loop_index), + const int coarse_poly_index, + const int coarse_corner, + const int subdiv_loop_index, + const int subdiv_vertex_index, + const int subdiv_edge_index) +{ + SubdivMeshContext *ctx = static_cast(foreach_context->user_data); + SubdivMeshTLS *tls = static_cast(tls_v); + const Mesh *coarse_mesh = ctx->coarse_mesh; + const MPoly *coarse_mpoly = coarse_mesh->mpoly; + const MPoly *coarse_poly = &coarse_mpoly[coarse_poly_index]; + Mesh *subdiv_mesh = ctx->subdiv_mesh; + MLoop *subdiv_mloop = subdiv_mesh->mloop; + MLoop *subdiv_loop = &subdiv_mloop[subdiv_loop_index]; + subdiv_mesh_ensure_loop_interpolation(ctx, tls, coarse_poly, coarse_corner); + subdiv_interpolate_loop_data(ctx, subdiv_loop, &tls->loop_interpolation, u, v); + subdiv_eval_uv_layer(ctx, subdiv_loop, ptex_face_index, u, v); + subdiv_loop->v = subdiv_vertex_index; + subdiv_loop->e = subdiv_edge_index; +} + +/** \} */ + +/* -------------------------------------------------------------------- */ +/** \name Polygons subdivision process + * \{ */ + +static void subdiv_copy_poly_data(const SubdivMeshContext *ctx, + MPoly *subdiv_poly, + const MPoly *coarse_poly) +{ + const int coarse_poly_index = coarse_poly - ctx->coarse_mesh->mpoly; + const int subdiv_poly_index = subdiv_poly - ctx->subdiv_mesh->mpoly; + CustomData_copy_data( + &ctx->coarse_mesh->pdata, &ctx->subdiv_mesh->pdata, coarse_poly_index, subdiv_poly_index, 1); +} + +static void subdiv_mesh_poly(const SubdivForeachContext *foreach_context, + void *UNUSED(tls), + const int coarse_poly_index, + const int subdiv_poly_index, + const int start_loop_index, + const int num_loops) +{ + BLI_assert(coarse_poly_index != ORIGINDEX_NONE); + SubdivMeshContext *ctx = static_cast(foreach_context->user_data); + const Mesh *coarse_mesh = ctx->coarse_mesh; + const MPoly *coarse_mpoly = coarse_mesh->mpoly; + const MPoly *coarse_poly = &coarse_mpoly[coarse_poly_index]; + Mesh *subdiv_mesh = ctx->subdiv_mesh; + MPoly *subdiv_mpoly = subdiv_mesh->mpoly; + MPoly *subdiv_poly = &subdiv_mpoly[subdiv_poly_index]; + subdiv_copy_poly_data(ctx, subdiv_poly, coarse_poly); + subdiv_poly->loopstart = start_loop_index; + subdiv_poly->totloop = num_loops; +} + +/** \} */ + +/* -------------------------------------------------------------------- */ +/** \name Loose elements subdivision process + * \{ */ + +static void subdiv_mesh_vertex_loose(const SubdivForeachContext *foreach_context, + void *UNUSED(tls), + const int coarse_vertex_index, + const int subdiv_vertex_index) +{ + SubdivMeshContext *ctx = static_cast(foreach_context->user_data); + const Mesh *coarse_mesh = ctx->coarse_mesh; + const MVert *coarse_mvert = coarse_mesh->mvert; + const MVert *coarse_vertex = &coarse_mvert[coarse_vertex_index]; + Mesh *subdiv_mesh = ctx->subdiv_mesh; + MVert *subdiv_mvert = subdiv_mesh->mvert; + MVert *subdiv_vertex = &subdiv_mvert[subdiv_vertex_index]; + subdiv_vertex_data_copy(ctx, coarse_vertex, subdiv_vertex); +} + +/* Get neighbor edges of the given one. + * - neighbors[0] is an edge adjacent to edge->v1. + * - neighbors[1] is an edge adjacent to edge->v2. */ +static void find_edge_neighbors(const Mesh *coarse_mesh, + const MEdge *edge, + const MEdge *neighbors[2]) +{ + const MEdge *coarse_medge = coarse_mesh->medge; + neighbors[0] = nullptr; + neighbors[1] = nullptr; + int neighbor_counters[2] = {0, 0}; + for (int edge_index = 0; edge_index < coarse_mesh->totedge; edge_index++) { + const MEdge *current_edge = &coarse_medge[edge_index]; + if (current_edge == edge) { + continue; + } + if (ELEM(edge->v1, current_edge->v1, current_edge->v2)) { + neighbors[0] = current_edge; + ++neighbor_counters[0]; + } + if (ELEM(edge->v2, current_edge->v1, current_edge->v2)) { + neighbors[1] = current_edge; + ++neighbor_counters[1]; + } + } + /* Vertices which has more than one neighbor are considered infinitely + * sharp. This is also how topology factory treats vertices of a surface + * which are adjacent to a loose edge. */ + if (neighbor_counters[0] > 1) { + neighbors[0] = nullptr; + } + if (neighbor_counters[1] > 1) { + neighbors[1] = nullptr; + } +} + +static void points_for_loose_edges_interpolation_get(const Mesh *coarse_mesh, + const MEdge *coarse_edge, + const MEdge *neighbors[2], + float points_r[4][3]) +{ + const MVert *coarse_mvert = coarse_mesh->mvert; + /* Middle points corresponds to the edge. */ + copy_v3_v3(points_r[1], coarse_mvert[coarse_edge->v1].co); + copy_v3_v3(points_r[2], coarse_mvert[coarse_edge->v2].co); + /* Start point, duplicate from edge start if no neighbor. */ + if (neighbors[0] != nullptr) { + if (neighbors[0]->v1 == coarse_edge->v1) { + copy_v3_v3(points_r[0], coarse_mvert[neighbors[0]->v2].co); + } + else { + copy_v3_v3(points_r[0], coarse_mvert[neighbors[0]->v1].co); + } + } + else { + sub_v3_v3v3(points_r[0], points_r[1], points_r[2]); + add_v3_v3(points_r[0], points_r[1]); + } + /* End point, duplicate from edge end if no neighbor. */ + if (neighbors[1] != nullptr) { + if (neighbors[1]->v1 == coarse_edge->v2) { + copy_v3_v3(points_r[3], coarse_mvert[neighbors[1]->v2].co); + } + else { + copy_v3_v3(points_r[3], coarse_mvert[neighbors[1]->v1].co); + } + } + else { + sub_v3_v3v3(points_r[3], points_r[2], points_r[1]); + add_v3_v3(points_r[3], points_r[2]); + } +} + +void BKE_subdiv_mesh_interpolate_position_on_edge(const Mesh *coarse_mesh, + const MEdge *coarse_edge, + const bool is_simple, + const float u, + float pos_r[3]) +{ + if (is_simple) { + const MVert *coarse_mvert = coarse_mesh->mvert; + const MVert *vert_1 = &coarse_mvert[coarse_edge->v1]; + const MVert *vert_2 = &coarse_mvert[coarse_edge->v2]; + interp_v3_v3v3(pos_r, vert_1->co, vert_2->co, u); + } + else { + /* Find neighbors of the coarse edge. */ + const MEdge *neighbors[2]; + find_edge_neighbors(coarse_mesh, coarse_edge, neighbors); + float points[4][3]; + points_for_loose_edges_interpolation_get(coarse_mesh, coarse_edge, neighbors, points); + float weights[4]; + key_curve_position_weights(u, weights, KEY_BSPLINE); + interp_v3_v3v3v3v3(pos_r, points[0], points[1], points[2], points[3], weights); + } +} + +static void subdiv_mesh_vertex_of_loose_edge_interpolate(SubdivMeshContext *ctx, + const MEdge *coarse_edge, + const float u, + const int subdiv_vertex_index) +{ + const Mesh *coarse_mesh = ctx->coarse_mesh; + Mesh *subdiv_mesh = ctx->subdiv_mesh; + /* This is never used for end-points (which are copied from the original). */ + BLI_assert(u > 0.0f); + BLI_assert(u < 1.0f); + const float interpolation_weights[2] = {1.0f - u, u}; + const int coarse_vertex_indices[2] = {static_cast(coarse_edge->v1), + static_cast(coarse_edge->v2)}; + CustomData_interp(&coarse_mesh->vdata, + &subdiv_mesh->vdata, + coarse_vertex_indices, + interpolation_weights, + nullptr, + 2, + subdiv_vertex_index); + if (ctx->vert_origindex != nullptr) { + ctx->vert_origindex[subdiv_vertex_index] = ORIGINDEX_NONE; + } +} + +static void subdiv_mesh_vertex_of_loose_edge(const SubdivForeachContext *foreach_context, + void *UNUSED(tls), + const int coarse_edge_index, + const float u, + const int subdiv_vertex_index) +{ + SubdivMeshContext *ctx = static_cast(foreach_context->user_data); + const Mesh *coarse_mesh = ctx->coarse_mesh; + const MEdge *coarse_edge = &coarse_mesh->medge[coarse_edge_index]; + Mesh *subdiv_mesh = ctx->subdiv_mesh; + MVert *subdiv_mvert = subdiv_mesh->mvert; + const bool is_simple = ctx->subdiv->settings.is_simple; + /* Interpolate custom data when not an end point. + * This data has already been copied from the original vertex by #subdiv_mesh_vertex_loose. */ + if (!ELEM(u, 0.0, 1.0)) { + subdiv_mesh_vertex_of_loose_edge_interpolate(ctx, coarse_edge, u, subdiv_vertex_index); + } + /* Interpolate coordinate. */ + MVert *subdiv_vertex = &subdiv_mvert[subdiv_vertex_index]; + BKE_subdiv_mesh_interpolate_position_on_edge( + coarse_mesh, coarse_edge, is_simple, u, subdiv_vertex->co); + /* Reset flags and such. */ + subdiv_vertex->flag = 0; + /* TODO(sergey): This matches old behavior, but we can as well interpolate + * it. Maybe even using vertex varying attributes. */ + subdiv_vertex->bweight = 0.0f; +} + +/** \} */ + +/* -------------------------------------------------------------------- */ +/** \name Initialization + * \{ */ + +static void setup_foreach_callbacks(const SubdivMeshContext *subdiv_context, + SubdivForeachContext *foreach_context) +{ + memset(foreach_context, 0, sizeof(*foreach_context)); + /* General information. */ + foreach_context->topology_info = subdiv_mesh_topology_info; + /* Every boundary geometry. Used for displacement averaging. */ + if (subdiv_context->have_displacement) { + foreach_context->vertex_every_corner = subdiv_mesh_vertex_displacement_every_corner; + foreach_context->vertex_every_edge = subdiv_mesh_vertex_displacement_every_edge; + } + foreach_context->vertex_corner = subdiv_mesh_vertex_corner; + foreach_context->vertex_edge = subdiv_mesh_vertex_edge; + foreach_context->vertex_inner = subdiv_mesh_vertex_inner; + foreach_context->edge = subdiv_mesh_edge; + foreach_context->loop = subdiv_mesh_loop; + foreach_context->poly = subdiv_mesh_poly; + foreach_context->vertex_loose = subdiv_mesh_vertex_loose; + foreach_context->vertex_of_loose_edge = subdiv_mesh_vertex_of_loose_edge; + foreach_context->user_data_tls_free = subdiv_mesh_tls_free; +} + +/** \} */ + +/* -------------------------------------------------------------------- */ +/** \name Public entry point + * \{ */ + +Mesh *BKE_subdiv_to_mesh(Subdiv *subdiv, + const SubdivToMeshSettings *settings, + const Mesh *coarse_mesh) +{ + BKE_subdiv_stats_begin(&subdiv->stats, SUBDIV_STATS_SUBDIV_TO_MESH); + /* Make sure evaluator is up to date with possible new topology, and that + * it is refined for the new positions of coarse vertices. */ + if (!BKE_subdiv_eval_begin_from_mesh( + subdiv, coarse_mesh, nullptr, SUBDIV_EVALUATOR_TYPE_CPU, nullptr)) { + /* This could happen in two situations: + * - OpenSubdiv is disabled. + * - Something totally bad happened, and OpenSubdiv rejected our + * topology. + * In either way, we can't safely continue. */ + if (coarse_mesh->totpoly) { + BKE_subdiv_stats_end(&subdiv->stats, SUBDIV_STATS_SUBDIV_TO_MESH); + return nullptr; + } + } + /* Initialize subdivision mesh creation context. */ + SubdivMeshContext subdiv_context = {0}; + subdiv_context.settings = settings; + subdiv_context.coarse_mesh = coarse_mesh; + subdiv_context.subdiv = subdiv; + subdiv_context.have_displacement = (subdiv->displacement_evaluator != nullptr); + /* Multi-threaded traversal/evaluation. */ + BKE_subdiv_stats_begin(&subdiv->stats, SUBDIV_STATS_SUBDIV_TO_MESH_GEOMETRY); + SubdivForeachContext foreach_context; + setup_foreach_callbacks(&subdiv_context, &foreach_context); + SubdivMeshTLS tls = {0}; + foreach_context.user_data = &subdiv_context; + foreach_context.user_data_tls_size = sizeof(SubdivMeshTLS); + foreach_context.user_data_tls = &tls; + BKE_subdiv_foreach_subdiv_geometry(subdiv, &foreach_context, settings, coarse_mesh); + BKE_subdiv_stats_end(&subdiv->stats, SUBDIV_STATS_SUBDIV_TO_MESH_GEOMETRY); + Mesh *result = subdiv_context.subdiv_mesh; + // BKE_mesh_validate(result, true, true); + BKE_subdiv_stats_end(&subdiv->stats, SUBDIV_STATS_SUBDIV_TO_MESH); + /* Using normals from the limit surface gives different results than Blender's vertex normal + * calculation. Since vertex normals are supposed to be a consistent cache, don't bother + * calculating them here. The work may have been pointless anyway if the mesh is deformed or + * changed afterwards. */ + BLI_assert(BKE_mesh_vertex_normals_are_dirty(result) || BKE_mesh_poly_normals_are_dirty(result)); + /* Free used memory. */ + subdiv_mesh_context_free(&subdiv_context); + return result; +} + +/** \} */ -- cgit v1.2.3 From cfe5bf4b2222f7cd1b41e7ee7f6fa84e807aaeb0 Mon Sep 17 00:00:00 2001 From: Campbell Barton Date: Thu, 18 Aug 2022 08:46:24 +1000 Subject: Cleanup: spelling, format --- source/blender/blenkernel/intern/subdiv_mesh.cc | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'source/blender/blenkernel/intern/subdiv_mesh.cc') diff --git a/source/blender/blenkernel/intern/subdiv_mesh.cc b/source/blender/blenkernel/intern/subdiv_mesh.cc index d914318b8a5..e026a013498 100644 --- a/source/blender/blenkernel/intern/subdiv_mesh.cc +++ b/source/blender/blenkernel/intern/subdiv_mesh.cc @@ -297,7 +297,7 @@ struct LoopsForInterpolation { * Is allocated for non-regular faces (triangles and n-gons). */ CustomData loop_data_storage; bool loop_data_storage_allocated; - /* Infices within loop_data to interpolate for. The indices are aligned with + /* Indices within loop_data to interpolate for. The indices are aligned with * uv coordinates in a similar way as indices in loop_data_storage. */ int loop_indices[4]; }; @@ -570,7 +570,7 @@ static void evaluate_vertex_and_apply_displacement_copy(const SubdivMeshContext add_v3_v3(subdiv_vert->co, D); /* Evaluate undeformed texture coordinate. */ subdiv_vertex_orco_evaluate(ctx, ptex_face_index, u, v, subdiv_vertex_index); - /* Remove facedot flag. This can happen if there is more than one subsurf modifier. */ + /* Remove face-dot flag. This can happen if there is more than one subsurf modifier. */ BLI_BITMAP_DISABLE(ctx->subdiv_mesh->runtime.subsurf_face_dot_tags, subdiv_vertex_index); } -- cgit v1.2.3 From 25237d2625078c6d14d744f288776299efd3c7c8 Mon Sep 17 00:00:00 2001 From: Hans Goudey Date: Tue, 30 Aug 2022 14:54:53 -0500 Subject: Attributes: Improve custom data initialization options When allocating new `CustomData` layers, often we do redundant initialization of arrays. For example, it's common that values are allocated, set to their default value, and then set to some other value. This is wasteful, and it negates the benefits of optimizations to the allocator like D15082. There are two reasons for this. The first is array-of-structs storage that makes it annoying to initialize values manually, and the second is confusing options in the Custom Data API. This patch addresses the latter. The `CustomData` "alloc type" options are rearranged. Now, besides the options that use existing layers, there are two remaining: * `CD_SET_DEFAULT` sets the default value. * Usually zeroes, but for colors this is white (how it was before). * Should be used when you add the layer but don't set all values. * `CD_CONSTRUCT` refers to the "default construct" C++ term. * Only necessary or defined for non-trivial types like vertex groups. * Doesn't do anything for trivial types like `int` or `float3`. * Should be used every other time, when all values will be set. The attribute API's `AttributeInit` types are updated as well. To update code, replace `CD_CALLOC` with `CD_SET_DEFAULT` and `CD_DEFAULT` with `CD_CONSTRUCT`. This doesn't cause any functional changes yet. Follow-up commits will change to avoid initializing new layers where the correctness is clear. Differential Revision: https://developer.blender.org/D15617 --- source/blender/blenkernel/intern/subdiv_mesh.cc | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'source/blender/blenkernel/intern/subdiv_mesh.cc') diff --git a/source/blender/blenkernel/intern/subdiv_mesh.cc b/source/blender/blenkernel/intern/subdiv_mesh.cc index e026a013498..da22ee6fd47 100644 --- a/source/blender/blenkernel/intern/subdiv_mesh.cc +++ b/source/blender/blenkernel/intern/subdiv_mesh.cc @@ -186,7 +186,7 @@ static void vertex_interpolation_init(const SubdivMeshContext *ctx, CustomData_copy(&ctx->coarse_mesh->vdata, &vertex_interpolation->vertex_data_storage, CD_MASK_EVERYTHING.vmask, - CD_CALLOC, + CD_SET_DEFAULT, 4); /* Initialize indices. */ vertex_interpolation->vertex_indices[0] = 0; @@ -321,7 +321,7 @@ static void loop_interpolation_init(const SubdivMeshContext *ctx, CustomData_copy(&ctx->coarse_mesh->ldata, &loop_interpolation->loop_data_storage, CD_MASK_EVERYTHING.lmask, - CD_CALLOC, + CD_SET_DEFAULT, 4); /* Initialize indices. */ loop_interpolation->loop_indices[0] = 0; -- cgit v1.2.3 From 05952aa94d33eeb504fa63618ba35c2bcc8bd19b Mon Sep 17 00:00:00 2001 From: Hans Goudey Date: Mon, 5 Sep 2022 11:56:34 -0500 Subject: Mesh: Remove redundant custom data pointers For copy-on-write, we want to share attribute arrays between meshes where possible. Mutable pointers like `Mesh.mvert` make that difficult by making ownership vague. They also make code more complex by adding redundancy. The simplest solution is just removing them and retrieving layers from `CustomData` as needed. Similar changes have already been applied to curves and point clouds (e9f82d3dc7ee, 410a6efb747f). Removing use of the pointers generally makes code more obvious and more reusable. Mesh data is now accessed with a C++ API (`Mesh::edges()` or `Mesh::edges_for_write()`), and a C API (`BKE_mesh_edges(mesh)`). The CoW changes this commit makes possible are described in T95845 and T95842, and started in D14139 and D14140. The change also simplifies the ongoing mesh struct-of-array refactors from T95965. **RNA/Python Access Performance** Theoretically, accessing mesh elements with the RNA API may become slower, since the layer needs to be found on every random access. However, overhead is already high enough that this doesn't make a noticible differenc, and performance is actually improved in some cases. Random access can be up to 10% faster, but other situations might be a bit slower. Generally using `foreach_get/set` are the best way to improve performance. See the differential revision for more discussion about Python performance. Cycles has been updated to use raw pointers and the internal Blender mesh types, mostly because there is no sense in having this overhead when it's already compiled with Blender. In my tests this roughly halves the Cycles mesh creation time (0.19s to 0.10s for a 1 million face grid). Differential Revision: https://developer.blender.org/D15488 --- source/blender/blenkernel/intern/subdiv_mesh.cc | 125 +++++++++++------------- 1 file changed, 57 insertions(+), 68 deletions(-) (limited to 'source/blender/blenkernel/intern/subdiv_mesh.cc') diff --git a/source/blender/blenkernel/intern/subdiv_mesh.cc b/source/blender/blenkernel/intern/subdiv_mesh.cc index da22ee6fd47..c222fc46800 100644 --- a/source/blender/blenkernel/intern/subdiv_mesh.cc +++ b/source/blender/blenkernel/intern/subdiv_mesh.cc @@ -32,8 +32,18 @@ struct SubdivMeshContext { const SubdivToMeshSettings *settings; const Mesh *coarse_mesh; + const MVert *coarse_verts; + const MEdge *coarse_edges; + const MPoly *coarse_polys; + const MLoop *coarse_loops; + Subdiv *subdiv; Mesh *subdiv_mesh; + MVert *subdiv_verts; + MEdge *subdiv_edges; + MPoly *subdiv_polys; + MLoop *subdiv_loops; + /* Cached custom data arrays for faster access. */ int *vert_origindex; int *edge_origindex; @@ -63,6 +73,10 @@ static void subdiv_mesh_ctx_cache_uv_layers(SubdivMeshContext *ctx) static void subdiv_mesh_ctx_cache_custom_data_layers(SubdivMeshContext *ctx) { Mesh *subdiv_mesh = ctx->subdiv_mesh; + ctx->subdiv_verts = BKE_mesh_vertices_for_write(subdiv_mesh); + ctx->subdiv_edges = BKE_mesh_edges_for_write(subdiv_mesh); + ctx->subdiv_polys = BKE_mesh_polygons_for_write(subdiv_mesh); + ctx->subdiv_loops = BKE_mesh_loops_for_write(subdiv_mesh); /* Pointers to original indices layers. */ ctx->vert_origindex = static_cast( CustomData_get_layer(&subdiv_mesh->vdata, CD_ORIGINDEX)); @@ -115,7 +129,7 @@ static void loops_of_ptex_get(const SubdivMeshContext *ctx, const MPoly *coarse_poly, const int ptex_of_poly_index) { - const MLoop *coarse_mloop = ctx->coarse_mesh->mloop; + const MLoop *coarse_mloop = ctx->coarse_loops; const int first_ptex_loop_index = coarse_poly->loopstart + ptex_of_poly_index; /* Loop which look in the (opposite) V direction of the current * ptex face. @@ -171,7 +185,7 @@ static void vertex_interpolation_init(const SubdivMeshContext *ctx, const MPoly *coarse_poly) { const Mesh *coarse_mesh = ctx->coarse_mesh; - const MLoop *coarse_mloop = coarse_mesh->mloop; + const MLoop *coarse_mloop = ctx->coarse_loops; if (coarse_poly->totloop == 4) { vertex_interpolation->vertex_data = &coarse_mesh->vdata; vertex_interpolation->vertex_indices[0] = coarse_mloop[coarse_poly->loopstart + 0].v; @@ -223,8 +237,7 @@ static void vertex_interpolation_from_corner(const SubdivMeshContext *ctx, } else { const CustomData *vertex_data = &ctx->coarse_mesh->vdata; - const Mesh *coarse_mesh = ctx->coarse_mesh; - const MLoop *coarse_mloop = coarse_mesh->mloop; + const MLoop *coarse_mloop = ctx->coarse_loops; LoopsOfPtex loops_of_ptex; loops_of_ptex_get(ctx, &loops_of_ptex, coarse_poly, corner); /* Ptex face corner corresponds to a poly loop with same index. */ @@ -358,8 +371,7 @@ static void loop_interpolation_from_corner(const SubdivMeshContext *ctx, } else { const CustomData *loop_data = &ctx->coarse_mesh->ldata; - const Mesh *coarse_mesh = ctx->coarse_mesh; - const MLoop *coarse_mloop = coarse_mesh->mloop; + const MLoop *coarse_mloop = ctx->coarse_loops; LoopsOfPtex loops_of_ptex; loops_of_ptex_get(ctx, &loops_of_ptex, coarse_poly, corner); /* Ptex face corner corresponds to a poly loop with same index. */ @@ -466,7 +478,7 @@ static void subdiv_accumulate_vertex_displacement(SubdivMeshContext *ctx, { /* Accumulate displacement. */ Subdiv *subdiv = ctx->subdiv; - const int subdiv_vertex_index = subdiv_vert - ctx->subdiv_mesh->mvert; + const int subdiv_vertex_index = subdiv_vert - ctx->subdiv_verts; float dummy_P[3], dPdu[3], dPdv[3], D[3]; BKE_subdiv_eval_limit_point_and_derivatives(subdiv, ptex_face_index, u, v, dummy_P, dPdu, dPdv); @@ -520,9 +532,8 @@ static void subdiv_vertex_data_copy(const SubdivMeshContext *ctx, MVert *subdiv_vertex) { const Mesh *coarse_mesh = ctx->coarse_mesh; - Mesh *subdiv_mesh = ctx->subdiv_mesh; - const int coarse_vertex_index = coarse_vertex - coarse_mesh->mvert; - const int subdiv_vertex_index = subdiv_vertex - subdiv_mesh->mvert; + const int coarse_vertex_index = coarse_vertex - ctx->coarse_verts; + const int subdiv_vertex_index = subdiv_vertex - ctx->subdiv_verts; CustomData_copy_data( &coarse_mesh->vdata, &ctx->subdiv_mesh->vdata, coarse_vertex_index, subdiv_vertex_index, 1); } @@ -533,7 +544,7 @@ static void subdiv_vertex_data_interpolate(const SubdivMeshContext *ctx, const float u, const float v) { - const int subdiv_vertex_index = subdiv_vertex - ctx->subdiv_mesh->mvert; + const int subdiv_vertex_index = subdiv_vertex - ctx->subdiv_verts; const float weights[4] = {(1.0f - u) * (1.0f - v), u * (1.0f - v), u * v, (1.0f - u) * v}; CustomData_interp(vertex_interpolation->vertex_data, &ctx->subdiv_mesh->vdata, @@ -554,7 +565,7 @@ static void evaluate_vertex_and_apply_displacement_copy(const SubdivMeshContext const MVert *coarse_vert, MVert *subdiv_vert) { - const int subdiv_vertex_index = subdiv_vert - ctx->subdiv_mesh->mvert; + const int subdiv_vertex_index = subdiv_vert - ctx->subdiv_verts; /* Displacement is accumulated in subdiv vertex position. * Needs to be backed up before copying data from original vertex. */ float D[3] = {0.0f, 0.0f, 0.0f}; @@ -582,7 +593,7 @@ static void evaluate_vertex_and_apply_displacement_interpolate( VerticesForInterpolation *vertex_interpolation, MVert *subdiv_vert) { - const int subdiv_vertex_index = subdiv_vert - ctx->subdiv_mesh->mvert; + const int subdiv_vertex_index = subdiv_vert - ctx->subdiv_verts; /* Displacement is accumulated in subdiv vertex position. * Needs to be backed up before copying data from original vertex. */ float D[3] = {0.0f, 0.0f, 0.0f}; @@ -609,9 +620,7 @@ static void subdiv_mesh_vertex_displacement_every_corner_or_edge( const int subdiv_vertex_index) { SubdivMeshContext *ctx = static_cast(foreach_context->user_data); - Mesh *subdiv_mesh = ctx->subdiv_mesh; - MVert *subdiv_mvert = subdiv_mesh->mvert; - MVert *subdiv_vert = &subdiv_mvert[subdiv_vertex_index]; + MVert *subdiv_vert = &ctx->subdiv_verts[subdiv_vertex_index]; subdiv_accumulate_vertex_displacement(ctx, ptex_face_index, u, v, subdiv_vert); } @@ -656,12 +665,8 @@ static void subdiv_mesh_vertex_corner(const SubdivForeachContext *foreach_contex { BLI_assert(coarse_vertex_index != ORIGINDEX_NONE); SubdivMeshContext *ctx = static_cast(foreach_context->user_data); - const Mesh *coarse_mesh = ctx->coarse_mesh; - const MVert *coarse_mvert = coarse_mesh->mvert; - Mesh *subdiv_mesh = ctx->subdiv_mesh; - MVert *subdiv_mvert = subdiv_mesh->mvert; - const MVert *coarse_vert = &coarse_mvert[coarse_vertex_index]; - MVert *subdiv_vert = &subdiv_mvert[subdiv_vertex_index]; + const MVert *coarse_vert = &ctx->coarse_verts[coarse_vertex_index]; + MVert *subdiv_vert = &ctx->subdiv_verts[subdiv_vertex_index]; evaluate_vertex_and_apply_displacement_copy( ctx, ptex_face_index, u, v, coarse_vert, subdiv_vert); } @@ -706,12 +711,8 @@ static void subdiv_mesh_vertex_edge(const SubdivForeachContext *foreach_context, { SubdivMeshContext *ctx = static_cast(foreach_context->user_data); SubdivMeshTLS *tls = static_cast(tls_v); - const Mesh *coarse_mesh = ctx->coarse_mesh; - const MPoly *coarse_mpoly = coarse_mesh->mpoly; - const MPoly *coarse_poly = &coarse_mpoly[coarse_poly_index]; - Mesh *subdiv_mesh = ctx->subdiv_mesh; - MVert *subdiv_mvert = subdiv_mesh->mvert; - MVert *subdiv_vert = &subdiv_mvert[subdiv_vertex_index]; + const MPoly *coarse_poly = &ctx->coarse_polys[coarse_poly_index]; + MVert *subdiv_vert = &ctx->subdiv_verts[subdiv_vertex_index]; subdiv_mesh_ensure_vertex_interpolation(ctx, tls, coarse_poly, coarse_corner); evaluate_vertex_and_apply_displacement_interpolate( ctx, ptex_face_index, u, v, &tls->vertex_interpolation, subdiv_vert); @@ -755,12 +756,9 @@ static void subdiv_mesh_vertex_inner(const SubdivForeachContext *foreach_context SubdivMeshContext *ctx = static_cast(foreach_context->user_data); SubdivMeshTLS *tls = static_cast(tls_v); Subdiv *subdiv = ctx->subdiv; - const Mesh *coarse_mesh = ctx->coarse_mesh; - const MPoly *coarse_mpoly = coarse_mesh->mpoly; - const MPoly *coarse_poly = &coarse_mpoly[coarse_poly_index]; + const MPoly *coarse_poly = &ctx->coarse_polys[coarse_poly_index]; Mesh *subdiv_mesh = ctx->subdiv_mesh; - MVert *subdiv_mvert = subdiv_mesh->mvert; - MVert *subdiv_vert = &subdiv_mvert[subdiv_vertex_index]; + MVert *subdiv_vert = &ctx->subdiv_verts[subdiv_vertex_index]; subdiv_mesh_ensure_vertex_interpolation(ctx, tls, coarse_poly, coarse_corner); subdiv_vertex_data_interpolate(ctx, subdiv_vert, &tls->vertex_interpolation, u, v); BKE_subdiv_eval_final_point(subdiv, ptex_face_index, u, v, subdiv_vert->co); @@ -778,7 +776,7 @@ static void subdiv_copy_edge_data(SubdivMeshContext *ctx, MEdge *subdiv_edge, const MEdge *coarse_edge) { - const int subdiv_edge_index = subdiv_edge - ctx->subdiv_mesh->medge; + const int subdiv_edge_index = subdiv_edge - ctx->subdiv_edges; if (coarse_edge == nullptr) { subdiv_edge->crease = 0; subdiv_edge->bweight = 0; @@ -791,7 +789,7 @@ static void subdiv_copy_edge_data(SubdivMeshContext *ctx, } return; } - const int coarse_edge_index = coarse_edge - ctx->coarse_mesh->medge; + const int coarse_edge_index = coarse_edge - ctx->coarse_edges; CustomData_copy_data( &ctx->coarse_mesh->edata, &ctx->subdiv_mesh->edata, coarse_edge_index, subdiv_edge_index, 1); subdiv_edge->flag |= ME_EDGERENDER; @@ -806,13 +804,11 @@ static void subdiv_mesh_edge(const SubdivForeachContext *foreach_context, const int subdiv_v2) { SubdivMeshContext *ctx = static_cast(foreach_context->user_data); - Mesh *subdiv_mesh = ctx->subdiv_mesh; - MEdge *subdiv_medge = subdiv_mesh->medge; + MEdge *subdiv_medge = ctx->subdiv_edges; MEdge *subdiv_edge = &subdiv_medge[subdiv_edge_index]; const MEdge *coarse_edge = nullptr; if (coarse_edge_index != ORIGINDEX_NONE) { - const Mesh *coarse_mesh = ctx->coarse_mesh; - const MEdge *coarse_medge = coarse_mesh->medge; + const MEdge *coarse_medge = ctx->coarse_edges; coarse_edge = &coarse_medge[coarse_edge_index]; } subdiv_copy_edge_data(ctx, subdiv_edge, coarse_edge); @@ -832,7 +828,7 @@ static void subdiv_interpolate_loop_data(const SubdivMeshContext *ctx, const float u, const float v) { - const int subdiv_loop_index = subdiv_loop - ctx->subdiv_mesh->mloop; + const int subdiv_loop_index = subdiv_loop - ctx->subdiv_loops; const float weights[4] = {(1.0f - u) * (1.0f - v), u * (1.0f - v), u * v, (1.0f - u) * v}; CustomData_interp(loop_interpolation->loop_data, &ctx->subdiv_mesh->ldata, @@ -854,7 +850,7 @@ static void subdiv_eval_uv_layer(SubdivMeshContext *ctx, return; } Subdiv *subdiv = ctx->subdiv; - const int mloop_index = subdiv_loop - ctx->subdiv_mesh->mloop; + const int mloop_index = subdiv_loop - ctx->subdiv_loops; for (int layer_index = 0; layer_index < ctx->num_uv_layers; layer_index++) { MLoopUV *subdiv_loopuv = &ctx->uv_layers[layer_index][mloop_index]; BKE_subdiv_eval_face_varying(subdiv, layer_index, ptex_face_index, u, v, subdiv_loopuv->uv); @@ -903,12 +899,9 @@ static void subdiv_mesh_loop(const SubdivForeachContext *foreach_context, { SubdivMeshContext *ctx = static_cast(foreach_context->user_data); SubdivMeshTLS *tls = static_cast(tls_v); - const Mesh *coarse_mesh = ctx->coarse_mesh; - const MPoly *coarse_mpoly = coarse_mesh->mpoly; + const MPoly *coarse_mpoly = ctx->coarse_polys; const MPoly *coarse_poly = &coarse_mpoly[coarse_poly_index]; - Mesh *subdiv_mesh = ctx->subdiv_mesh; - MLoop *subdiv_mloop = subdiv_mesh->mloop; - MLoop *subdiv_loop = &subdiv_mloop[subdiv_loop_index]; + MLoop *subdiv_loop = &ctx->subdiv_loops[subdiv_loop_index]; subdiv_mesh_ensure_loop_interpolation(ctx, tls, coarse_poly, coarse_corner); subdiv_interpolate_loop_data(ctx, subdiv_loop, &tls->loop_interpolation, u, v); subdiv_eval_uv_layer(ctx, subdiv_loop, ptex_face_index, u, v); @@ -926,8 +919,8 @@ static void subdiv_copy_poly_data(const SubdivMeshContext *ctx, MPoly *subdiv_poly, const MPoly *coarse_poly) { - const int coarse_poly_index = coarse_poly - ctx->coarse_mesh->mpoly; - const int subdiv_poly_index = subdiv_poly - ctx->subdiv_mesh->mpoly; + const int coarse_poly_index = coarse_poly - ctx->coarse_polys; + const int subdiv_poly_index = subdiv_poly - ctx->subdiv_polys; CustomData_copy_data( &ctx->coarse_mesh->pdata, &ctx->subdiv_mesh->pdata, coarse_poly_index, subdiv_poly_index, 1); } @@ -941,12 +934,8 @@ static void subdiv_mesh_poly(const SubdivForeachContext *foreach_context, { BLI_assert(coarse_poly_index != ORIGINDEX_NONE); SubdivMeshContext *ctx = static_cast(foreach_context->user_data); - const Mesh *coarse_mesh = ctx->coarse_mesh; - const MPoly *coarse_mpoly = coarse_mesh->mpoly; - const MPoly *coarse_poly = &coarse_mpoly[coarse_poly_index]; - Mesh *subdiv_mesh = ctx->subdiv_mesh; - MPoly *subdiv_mpoly = subdiv_mesh->mpoly; - MPoly *subdiv_poly = &subdiv_mpoly[subdiv_poly_index]; + const MPoly *coarse_poly = &ctx->coarse_polys[coarse_poly_index]; + MPoly *subdiv_poly = &ctx->subdiv_polys[subdiv_poly_index]; subdiv_copy_poly_data(ctx, subdiv_poly, coarse_poly); subdiv_poly->loopstart = start_loop_index; subdiv_poly->totloop = num_loops; @@ -964,12 +953,8 @@ static void subdiv_mesh_vertex_loose(const SubdivForeachContext *foreach_context const int subdiv_vertex_index) { SubdivMeshContext *ctx = static_cast(foreach_context->user_data); - const Mesh *coarse_mesh = ctx->coarse_mesh; - const MVert *coarse_mvert = coarse_mesh->mvert; - const MVert *coarse_vertex = &coarse_mvert[coarse_vertex_index]; - Mesh *subdiv_mesh = ctx->subdiv_mesh; - MVert *subdiv_mvert = subdiv_mesh->mvert; - MVert *subdiv_vertex = &subdiv_mvert[subdiv_vertex_index]; + const MVert *coarse_vertex = &ctx->coarse_verts[coarse_vertex_index]; + MVert *subdiv_vertex = &ctx->subdiv_verts[subdiv_vertex_index]; subdiv_vertex_data_copy(ctx, coarse_vertex, subdiv_vertex); } @@ -980,12 +965,12 @@ static void find_edge_neighbors(const Mesh *coarse_mesh, const MEdge *edge, const MEdge *neighbors[2]) { - const MEdge *coarse_medge = coarse_mesh->medge; + const blender::Span coarse_edges = coarse_mesh->edges(); neighbors[0] = nullptr; neighbors[1] = nullptr; int neighbor_counters[2] = {0, 0}; for (int edge_index = 0; edge_index < coarse_mesh->totedge; edge_index++) { - const MEdge *current_edge = &coarse_medge[edge_index]; + const MEdge *current_edge = &coarse_edges[edge_index]; if (current_edge == edge) { continue; } @@ -1014,7 +999,7 @@ static void points_for_loose_edges_interpolation_get(const Mesh *coarse_mesh, const MEdge *neighbors[2], float points_r[4][3]) { - const MVert *coarse_mvert = coarse_mesh->mvert; + const MVert *coarse_mvert = BKE_mesh_vertices(coarse_mesh); /* Middle points corresponds to the edge. */ copy_v3_v3(points_r[1], coarse_mvert[coarse_edge->v1].co); copy_v3_v3(points_r[2], coarse_mvert[coarse_edge->v2].co); @@ -1053,7 +1038,7 @@ void BKE_subdiv_mesh_interpolate_position_on_edge(const Mesh *coarse_mesh, float pos_r[3]) { if (is_simple) { - const MVert *coarse_mvert = coarse_mesh->mvert; + const MVert *coarse_mvert = BKE_mesh_vertices(coarse_mesh); const MVert *vert_1 = &coarse_mvert[coarse_edge->v1]; const MVert *vert_2 = &coarse_mvert[coarse_edge->v2]; interp_v3_v3v3(pos_r, vert_1->co, vert_2->co, u); @@ -1103,9 +1088,7 @@ static void subdiv_mesh_vertex_of_loose_edge(const SubdivForeachContext *foreach { SubdivMeshContext *ctx = static_cast(foreach_context->user_data); const Mesh *coarse_mesh = ctx->coarse_mesh; - const MEdge *coarse_edge = &coarse_mesh->medge[coarse_edge_index]; - Mesh *subdiv_mesh = ctx->subdiv_mesh; - MVert *subdiv_mvert = subdiv_mesh->mvert; + const MEdge *coarse_edge = &ctx->coarse_edges[coarse_edge_index]; const bool is_simple = ctx->subdiv->settings.is_simple; /* Interpolate custom data when not an end point. * This data has already been copied from the original vertex by #subdiv_mesh_vertex_loose. */ @@ -1113,7 +1096,7 @@ static void subdiv_mesh_vertex_of_loose_edge(const SubdivForeachContext *foreach subdiv_mesh_vertex_of_loose_edge_interpolate(ctx, coarse_edge, u, subdiv_vertex_index); } /* Interpolate coordinate. */ - MVert *subdiv_vertex = &subdiv_mvert[subdiv_vertex_index]; + MVert *subdiv_vertex = &ctx->subdiv_verts[subdiv_vertex_index]; BKE_subdiv_mesh_interpolate_position_on_edge( coarse_mesh, coarse_edge, is_simple, u, subdiv_vertex->co); /* Reset flags and such. */ @@ -1179,7 +1162,13 @@ Mesh *BKE_subdiv_to_mesh(Subdiv *subdiv, /* Initialize subdivision mesh creation context. */ SubdivMeshContext subdiv_context = {0}; subdiv_context.settings = settings; + subdiv_context.coarse_mesh = coarse_mesh; + subdiv_context.coarse_verts = BKE_mesh_vertices(coarse_mesh); + subdiv_context.coarse_edges = BKE_mesh_edges(coarse_mesh); + subdiv_context.coarse_polys = BKE_mesh_polygons(coarse_mesh); + subdiv_context.coarse_loops = BKE_mesh_loops(coarse_mesh); + subdiv_context.subdiv = subdiv; subdiv_context.have_displacement = (subdiv->displacement_evaluator != nullptr); /* Multi-threaded traversal/evaluation. */ -- cgit v1.2.3 From be038b844cb53bc228d3e98bfe09071560930cde Mon Sep 17 00:00:00 2001 From: Hans Goudey Date: Wed, 7 Sep 2022 00:06:31 -0500 Subject: Cleanup: Tweak naming for recently added mesh accessors Use `verts` instead of `vertices` and `polys` instead of `polygons` in the API added in 05952aa94d33eeb50. This aligns better with existing naming where the shorter names are much more common. --- source/blender/blenkernel/intern/subdiv_mesh.cc | 12 ++++++------ 1 file changed, 6 insertions(+), 6 deletions(-) (limited to 'source/blender/blenkernel/intern/subdiv_mesh.cc') diff --git a/source/blender/blenkernel/intern/subdiv_mesh.cc b/source/blender/blenkernel/intern/subdiv_mesh.cc index c222fc46800..5a2af36e83c 100644 --- a/source/blender/blenkernel/intern/subdiv_mesh.cc +++ b/source/blender/blenkernel/intern/subdiv_mesh.cc @@ -73,9 +73,9 @@ static void subdiv_mesh_ctx_cache_uv_layers(SubdivMeshContext *ctx) static void subdiv_mesh_ctx_cache_custom_data_layers(SubdivMeshContext *ctx) { Mesh *subdiv_mesh = ctx->subdiv_mesh; - ctx->subdiv_verts = BKE_mesh_vertices_for_write(subdiv_mesh); + ctx->subdiv_verts = BKE_mesh_verts_for_write(subdiv_mesh); ctx->subdiv_edges = BKE_mesh_edges_for_write(subdiv_mesh); - ctx->subdiv_polys = BKE_mesh_polygons_for_write(subdiv_mesh); + ctx->subdiv_polys = BKE_mesh_polys_for_write(subdiv_mesh); ctx->subdiv_loops = BKE_mesh_loops_for_write(subdiv_mesh); /* Pointers to original indices layers. */ ctx->vert_origindex = static_cast( @@ -999,7 +999,7 @@ static void points_for_loose_edges_interpolation_get(const Mesh *coarse_mesh, const MEdge *neighbors[2], float points_r[4][3]) { - const MVert *coarse_mvert = BKE_mesh_vertices(coarse_mesh); + const MVert *coarse_mvert = BKE_mesh_verts(coarse_mesh); /* Middle points corresponds to the edge. */ copy_v3_v3(points_r[1], coarse_mvert[coarse_edge->v1].co); copy_v3_v3(points_r[2], coarse_mvert[coarse_edge->v2].co); @@ -1038,7 +1038,7 @@ void BKE_subdiv_mesh_interpolate_position_on_edge(const Mesh *coarse_mesh, float pos_r[3]) { if (is_simple) { - const MVert *coarse_mvert = BKE_mesh_vertices(coarse_mesh); + const MVert *coarse_mvert = BKE_mesh_verts(coarse_mesh); const MVert *vert_1 = &coarse_mvert[coarse_edge->v1]; const MVert *vert_2 = &coarse_mvert[coarse_edge->v2]; interp_v3_v3v3(pos_r, vert_1->co, vert_2->co, u); @@ -1164,9 +1164,9 @@ Mesh *BKE_subdiv_to_mesh(Subdiv *subdiv, subdiv_context.settings = settings; subdiv_context.coarse_mesh = coarse_mesh; - subdiv_context.coarse_verts = BKE_mesh_vertices(coarse_mesh); + subdiv_context.coarse_verts = BKE_mesh_verts(coarse_mesh); subdiv_context.coarse_edges = BKE_mesh_edges(coarse_mesh); - subdiv_context.coarse_polys = BKE_mesh_polygons(coarse_mesh); + subdiv_context.coarse_polys = BKE_mesh_polys(coarse_mesh); subdiv_context.coarse_loops = BKE_mesh_loops(coarse_mesh); subdiv_context.subdiv = subdiv; -- cgit v1.2.3 From 12c235a1c515d41a18c497d6647253698579c01d Mon Sep 17 00:00:00 2001 From: Hans Goudey Date: Fri, 9 Sep 2022 08:13:37 -0500 Subject: Subdiv: Avoid quadratic runtime for loose edges Currently, when subdividing every single vertex on every loose edge, Blender iterates over all other edges to find neighbors. This has quadratic runtime and can be very slow. Instead, first create a map of edges connected to each vertex. With about 10000 edges, the performance goes from very slow to very smooth in my tests. Because of the nature of quadratic runtime, the improvement will depend massively on the number of elements. The only downside to this is that the map will still be built when there are only a couple loose edges, but that case is probably not so common. Differential Revision: https://developer.blender.org/D15923 --- source/blender/blenkernel/intern/subdiv_mesh.cc | 79 ++++++++++++++++++------- 1 file changed, 58 insertions(+), 21 deletions(-) (limited to 'source/blender/blenkernel/intern/subdiv_mesh.cc') diff --git a/source/blender/blenkernel/intern/subdiv_mesh.cc b/source/blender/blenkernel/intern/subdiv_mesh.cc index 5a2af36e83c..dc9fc3dee09 100644 --- a/source/blender/blenkernel/intern/subdiv_mesh.cc +++ b/source/blender/blenkernel/intern/subdiv_mesh.cc @@ -5,6 +5,8 @@ * \ingroup bke */ +#include + #include "atomic_ops.h" #include "DNA_key_types.h" @@ -18,6 +20,7 @@ #include "BKE_customdata.h" #include "BKE_key.h" #include "BKE_mesh.h" +#include "BKE_mesh_mapping.h" #include "BKE_subdiv.h" #include "BKE_subdiv_eval.h" #include "BKE_subdiv_foreach.h" @@ -25,6 +28,8 @@ #include "MEM_guardedalloc.h" +using blender::Span; + /* -------------------------------------------------------------------- */ /** \name Subdivision Context * \{ */ @@ -58,6 +63,11 @@ struct SubdivMeshContext { /* Per-subdivided vertex counter of averaged values. */ int *accumulated_counters; bool have_displacement; + + /* Lazily initialize a map from vertices to connected edges. */ + std::mutex vert_to_edge_map_mutex; + int *vert_to_edge_buffer; + MeshElemMap *vert_to_edge_map; }; static void subdiv_mesh_ctx_cache_uv_layers(SubdivMeshContext *ctx) @@ -106,6 +116,8 @@ static void subdiv_mesh_prepare_accumulator(SubdivMeshContext *ctx, int num_vert static void subdiv_mesh_context_free(SubdivMeshContext *ctx) { MEM_SAFE_FREE(ctx->accumulated_counters); + MEM_SAFE_FREE(ctx->vert_to_edge_buffer); + MEM_SAFE_FREE(ctx->vert_to_edge_map); } /** \} */ @@ -961,25 +973,30 @@ static void subdiv_mesh_vertex_loose(const SubdivForeachContext *foreach_context /* Get neighbor edges of the given one. * - neighbors[0] is an edge adjacent to edge->v1. * - neighbors[1] is an edge adjacent to edge->v2. */ -static void find_edge_neighbors(const Mesh *coarse_mesh, - const MEdge *edge, +static void find_edge_neighbors(const MEdge *coarse_edges, + const MeshElemMap *vert_to_edge_map, + const int edge_index, const MEdge *neighbors[2]) { - const blender::Span coarse_edges = coarse_mesh->edges(); + const MEdge *edge = &coarse_edges[edge_index]; neighbors[0] = nullptr; neighbors[1] = nullptr; int neighbor_counters[2] = {0, 0}; - for (int edge_index = 0; edge_index < coarse_mesh->totedge; edge_index++) { - const MEdge *current_edge = &coarse_edges[edge_index]; - if (current_edge == edge) { + for (const int i : Span(vert_to_edge_map[edge->v1].indices, vert_to_edge_map[edge->v1].count)) { + if (i == edge_index) { continue; } - if (ELEM(edge->v1, current_edge->v1, current_edge->v2)) { - neighbors[0] = current_edge; + if (ELEM(edge->v1, coarse_edges[i].v1, coarse_edges[i].v2)) { + neighbors[0] = &coarse_edges[i]; ++neighbor_counters[0]; } - if (ELEM(edge->v2, current_edge->v1, current_edge->v2)) { - neighbors[1] = current_edge; + } + for (const int i : Span(vert_to_edge_map[edge->v2].indices, vert_to_edge_map[edge->v2].count)) { + if (i == edge_index) { + continue; + } + if (ELEM(edge->v2, coarse_edges[i].v1, coarse_edges[i].v2)) { + neighbors[1] = &coarse_edges[i]; ++neighbor_counters[1]; } } @@ -994,12 +1011,11 @@ static void find_edge_neighbors(const Mesh *coarse_mesh, } } -static void points_for_loose_edges_interpolation_get(const Mesh *coarse_mesh, +static void points_for_loose_edges_interpolation_get(const MVert *coarse_mvert, const MEdge *coarse_edge, const MEdge *neighbors[2], float points_r[4][3]) { - const MVert *coarse_mvert = BKE_mesh_verts(coarse_mesh); /* Middle points corresponds to the edge. */ copy_v3_v3(points_r[1], coarse_mvert[coarse_edge->v1].co); copy_v3_v3(points_r[2], coarse_mvert[coarse_edge->v2].co); @@ -1031,24 +1047,26 @@ static void points_for_loose_edges_interpolation_get(const Mesh *coarse_mesh, } } -void BKE_subdiv_mesh_interpolate_position_on_edge(const Mesh *coarse_mesh, - const MEdge *coarse_edge, +void BKE_subdiv_mesh_interpolate_position_on_edge(const MVert *coarse_verts, + const MEdge *coarse_edges, + const MeshElemMap *vert_to_edge_map, + const int coarse_edge_index, const bool is_simple, const float u, float pos_r[3]) { + const MEdge *coarse_edge = &coarse_edges[coarse_edge_index]; if (is_simple) { - const MVert *coarse_mvert = BKE_mesh_verts(coarse_mesh); - const MVert *vert_1 = &coarse_mvert[coarse_edge->v1]; - const MVert *vert_2 = &coarse_mvert[coarse_edge->v2]; + const MVert *vert_1 = &coarse_verts[coarse_edge->v1]; + const MVert *vert_2 = &coarse_verts[coarse_edge->v2]; interp_v3_v3v3(pos_r, vert_1->co, vert_2->co, u); } else { /* Find neighbors of the coarse edge. */ const MEdge *neighbors[2]; - find_edge_neighbors(coarse_mesh, coarse_edge, neighbors); + find_edge_neighbors(coarse_edges, vert_to_edge_map, coarse_edge_index, neighbors); float points[4][3]; - points_for_loose_edges_interpolation_get(coarse_mesh, coarse_edge, neighbors, points); + points_for_loose_edges_interpolation_get(coarse_verts, coarse_edge, neighbors, points); float weights[4]; key_curve_position_weights(u, weights, KEY_BSPLINE); interp_v3_v3v3v3v3(pos_r, points[0], points[1], points[2], points[3], weights); @@ -1090,6 +1108,20 @@ static void subdiv_mesh_vertex_of_loose_edge(const SubdivForeachContext *foreach const Mesh *coarse_mesh = ctx->coarse_mesh; const MEdge *coarse_edge = &ctx->coarse_edges[coarse_edge_index]; const bool is_simple = ctx->subdiv->settings.is_simple; + + /* Lazily initialize a vertex to edge map to avoid quadratic runtime when subdividing loose + * edges. Do this here to avoid the cost in common cases when there are no loose edges at all. */ + if (ctx->vert_to_edge_map == NULL) { + std::lock_guard lock{ctx->vert_to_edge_map_mutex}; + if (ctx->vert_to_edge_map == NULL) { + BKE_mesh_vert_edge_map_create(&ctx->vert_to_edge_map, + &ctx->vert_to_edge_buffer, + ctx->coarse_edges, + coarse_mesh->totvert, + ctx->coarse_mesh->totedge); + } + } + /* Interpolate custom data when not an end point. * This data has already been copied from the original vertex by #subdiv_mesh_vertex_loose. */ if (!ELEM(u, 0.0, 1.0)) { @@ -1097,8 +1129,13 @@ static void subdiv_mesh_vertex_of_loose_edge(const SubdivForeachContext *foreach } /* Interpolate coordinate. */ MVert *subdiv_vertex = &ctx->subdiv_verts[subdiv_vertex_index]; - BKE_subdiv_mesh_interpolate_position_on_edge( - coarse_mesh, coarse_edge, is_simple, u, subdiv_vertex->co); + BKE_subdiv_mesh_interpolate_position_on_edge(ctx->coarse_verts, + ctx->coarse_edges, + ctx->vert_to_edge_map, + coarse_edge_index, + is_simple, + u, + subdiv_vertex->co); /* Reset flags and such. */ subdiv_vertex->flag = 0; /* TODO(sergey): This matches old behavior, but we can as well interpolate -- cgit v1.2.3 From 291c313f80b4cccc8fcce3035584caeaa654844f Mon Sep 17 00:00:00 2001 From: Hans Goudey Date: Fri, 9 Sep 2022 08:29:07 -0500 Subject: Mesh: Move bevel weight out of MVert and MEdge As described in T95966, the goal is to move to a "struct of arrays" approach rather than gathering an arbitrary set of data in hard-coded structs. This has performance benefits, but also code complexity benefits (this patch removes plenty of code, though the boilerplate for the new operators outweighs that here). To mirror the internal change, the options for storing mesh bevel weights are converted into operators that add or remove the layer, like for some other layers. The most complex change is to the solidify modifier, where bevel weights had special handling. Other than that, most changes are removing clearing of the weights, boilerplate for the add/remove operators, and removing the manual transfer of bevel weights in bmesh - mesh conversion. Eventually bevel weights can become a fully generic attribute, but for now this patch aims to avoid most functional changes. Bevel weights are still written and read from the mesh in the old way, so neither forward nor backward compatibility are affected. As described in T95965, writing in the old format will be done until 4.0. Differential Revision: https://developer.blender.org/D14077 --- source/blender/blenkernel/intern/subdiv_mesh.cc | 4 ---- 1 file changed, 4 deletions(-) (limited to 'source/blender/blenkernel/intern/subdiv_mesh.cc') diff --git a/source/blender/blenkernel/intern/subdiv_mesh.cc b/source/blender/blenkernel/intern/subdiv_mesh.cc index dc9fc3dee09..44bdd6e6d06 100644 --- a/source/blender/blenkernel/intern/subdiv_mesh.cc +++ b/source/blender/blenkernel/intern/subdiv_mesh.cc @@ -791,7 +791,6 @@ static void subdiv_copy_edge_data(SubdivMeshContext *ctx, const int subdiv_edge_index = subdiv_edge - ctx->subdiv_edges; if (coarse_edge == nullptr) { subdiv_edge->crease = 0; - subdiv_edge->bweight = 0; subdiv_edge->flag = 0; if (!ctx->settings->use_optimal_display) { subdiv_edge->flag |= ME_EDGERENDER; @@ -1138,9 +1137,6 @@ static void subdiv_mesh_vertex_of_loose_edge(const SubdivForeachContext *foreach subdiv_vertex->co); /* Reset flags and such. */ subdiv_vertex->flag = 0; - /* TODO(sergey): This matches old behavior, but we can as well interpolate - * it. Maybe even using vertex varying attributes. */ - subdiv_vertex->bweight = 0.0f; } /** \} */ -- cgit v1.2.3