/* SPDX-License-Identifier: GPL-2.0-or-later * Copyright 2018 Blender Foundation. All rights reserved. */ /** \file * \ingroup bke */ #include #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_mesh_mapping.h" #include "BKE_subdiv.h" #include "BKE_subdiv_eval.h" #include "BKE_subdiv_foreach.h" #include "BKE_subdiv_mesh.h" #include "MEM_guardedalloc.h" using blender::float3; using blender::Span; /* -------------------------------------------------------------------- */ /** \name Subdivision Context * \{ */ struct SubdivMeshContext { const SubdivToMeshSettings *settings; const Mesh *coarse_mesh; const float (*coarse_positions)[3]; const MEdge *coarse_edges; const MPoly *coarse_polys; const MLoop *coarse_loops; Subdiv *subdiv; Mesh *subdiv_mesh; float3 *subdiv_positions; MEdge *subdiv_edges; MPoly *subdiv_polys; MLoop *subdiv_loops; /* 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; /* 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) { 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; ctx->subdiv_positions = subdiv_mesh->positions_for_write().data(); ctx->subdiv_edges = BKE_mesh_edges_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( 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); MEM_SAFE_FREE(ctx->vert_to_edge_buffer); MEM_SAFE_FREE(ctx->vert_to_edge_map); } /** \} */ /* -------------------------------------------------------------------- */ /** \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_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. * * 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 = 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; 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_SET_DEFAULT, 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 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. */ 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] = { int(coarse_mloop[first_loop_index].v), int(coarse_mloop[coarse_poly->loopstart + (first_loop_index - coarse_poly->loopstart + 1) % coarse_poly->totloop] .v)}; const int last_indices[2] = { int(coarse_mloop[first_loop_index].v), int(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; /* 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]; }; 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_SET_DEFAULT, 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 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. */ 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] = { int(loops_of_ptex.last_loop - coarse_mloop), int(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, const int subdiv_vertex_index) { /* Accumulate displacement. */ Subdiv *subdiv = ctx->subdiv; 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); ctx->subdiv_positions[subdiv_vertex_index] += 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 * /*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. Crease values should also not be interpolated. */ CustomData_MeshMasks mask = CD_MASK_EVERYTHING; mask.lmask &= ~CD_MASK_MULTIRES_GRIDS; mask.vmask &= ~CD_MASK_CREASE; mask.emask &= ~CD_MASK_CREASE; 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 int coarse_vertex_index, const int subdiv_vertex_index) { const Mesh *coarse_mesh = ctx->coarse_mesh; 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, const int subdiv_vertex_index, const VerticesForInterpolation *vertex_interpolation, const float u, const float v) { 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 int coarse_vertex_index, const int subdiv_vertex_index) { float3 &subdiv_position = ctx->subdiv_positions[subdiv_vertex_index]; /* 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_position); mul_v3_fl(D, inv_num_accumulated); } /* Copy custom data and evaluate position. */ subdiv_vertex_data_copy(ctx, coarse_vertex_index, subdiv_vertex_index); BKE_subdiv_eval_limit_point(ctx->subdiv, ptex_face_index, u, v, subdiv_position); /* Apply displacement. */ subdiv_position += D; /* Evaluate undeformed texture coordinate. */ subdiv_vertex_orco_evaluate(ctx, ptex_face_index, u, v, subdiv_vertex_index); /* 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); } 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, const int subdiv_vertex_index) { float3 &subdiv_position = ctx->subdiv_positions[subdiv_vertex_index]; /* 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_position); mul_v3_fl(D, inv_num_accumulated); } /* Interpolate custom data and evaluate position. */ subdiv_vertex_data_interpolate(ctx, subdiv_vertex_index, vertex_interpolation, u, v); BKE_subdiv_eval_limit_point(ctx->subdiv, ptex_face_index, u, v, subdiv_position); /* Apply displacement. */ add_v3_v3(subdiv_position, 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 * /*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); subdiv_accumulate_vertex_displacement(ctx, ptex_face_index, u, v, subdiv_vertex_index); } 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 /*coarse_vertex_index*/, const int /*coarse_poly_index*/, const int /*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 /*coarse_edge_index*/, const int /*coarse_poly_index*/, const int /*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 * /*tls*/, const int ptex_face_index, const float u, const float v, const int coarse_vertex_index, const int /*coarse_poly_index*/, const int /*coarse_corner*/, const int subdiv_vertex_index) { BLI_assert(coarse_vertex_index != ORIGINDEX_NONE); SubdivMeshContext *ctx = static_cast(foreach_context->user_data); evaluate_vertex_and_apply_displacement_copy( ctx, ptex_face_index, u, v, coarse_vertex_index, subdiv_vertex_index); } 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 /*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 MPoly *coarse_poly = &ctx->coarse_polys[coarse_poly_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_vertex_index); } 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 MPoly *coarse_poly = &ctx->coarse_polys[coarse_poly_index]; Mesh *subdiv_mesh = ctx->subdiv_mesh; float3 &subdiv_position = ctx->subdiv_positions[subdiv_vertex_index]; subdiv_mesh_ensure_vertex_interpolation(ctx, tls, coarse_poly, coarse_corner); subdiv_vertex_data_interpolate(ctx, subdiv_vertex_index, &tls->vertex_interpolation, u, v); BKE_subdiv_eval_final_point(subdiv, ptex_face_index, u, v, subdiv_position); 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_edges; if (coarse_edge == nullptr) { /* TODO: Ensure crease layer isn't copied to result. */ subdiv_edge->flag = 0; if (!ctx->settings->use_optimal_display) { subdiv_edge->flag |= ME_EDGEDRAW; } if (ctx->edge_origindex != nullptr) { ctx->edge_origindex[subdiv_edge_index] = ORIGINDEX_NONE; } return; } 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_EDGEDRAW; } static void subdiv_mesh_edge(const SubdivForeachContext *foreach_context, void * /*tls*/, const int coarse_edge_index, const int subdiv_edge_index, const bool /*is_loose*/, const int subdiv_v1, const int subdiv_v2) { SubdivMeshContext *ctx = static_cast(foreach_context->user_data); 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 MEdge *coarse_medge = ctx->coarse_edges; 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_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, 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_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); } } 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 /*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 MPoly *coarse_mpoly = ctx->coarse_polys; const MPoly *coarse_poly = &coarse_mpoly[coarse_poly_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); 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_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); } static void subdiv_mesh_poly(const SubdivForeachContext *foreach_context, void * /*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 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; } /** \} */ /* -------------------------------------------------------------------- */ /** \name Loose elements subdivision process * \{ */ static void subdiv_mesh_vertex_loose(const SubdivForeachContext *foreach_context, void * /*tls*/, const int coarse_vertex_index, const int subdiv_vertex_index) { SubdivMeshContext *ctx = static_cast(foreach_context->user_data); subdiv_vertex_data_copy(ctx, coarse_vertex_index, subdiv_vertex_index); } /* 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 MEdge *coarse_edges, const MeshElemMap *vert_to_edge_map, const int edge_index, const MEdge *neighbors[2]) { const MEdge *edge = &coarse_edges[edge_index]; neighbors[0] = nullptr; neighbors[1] = nullptr; int neighbor_counters[2] = {0, 0}; 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, coarse_edges[i].v1, coarse_edges[i].v2)) { neighbors[0] = &coarse_edges[i]; ++neighbor_counters[0]; } } 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]; } } /* 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 float (*coarse_positions)[3], const MEdge *coarse_edge, const MEdge *neighbors[2], float points_r[4][3]) { /* Middle points corresponds to the edge. */ copy_v3_v3(points_r[1], coarse_positions[coarse_edge->v1]); copy_v3_v3(points_r[2], coarse_positions[coarse_edge->v2]); /* 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_positions[neighbors[0]->v2]); } else { copy_v3_v3(points_r[0], coarse_positions[neighbors[0]->v1]); } } 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_positions[neighbors[1]->v2]); } else { copy_v3_v3(points_r[3], coarse_positions[neighbors[1]->v1]); } } 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 float (*coarse_positions)[3], 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) { interp_v3_v3v3(pos_r, coarse_positions[coarse_edge->v1], coarse_positions[coarse_edge->v2], u); } else { /* Find neighbors of the coarse edge. */ const MEdge *neighbors[2]; find_edge_neighbors(coarse_edges, vert_to_edge_map, coarse_edge_index, neighbors); float points[4][3]; points_for_loose_edges_interpolation_get(coarse_positions, 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] = {int(coarse_edge->v1), int(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 * /*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 = &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 == nullptr) { std::lock_guard lock{ctx->vert_to_edge_map_mutex}; if (ctx->vert_to_edge_map == nullptr) { 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)) { subdiv_mesh_vertex_of_loose_edge_interpolate(ctx, coarse_edge, u, subdiv_vertex_index); } /* Interpolate coordinate. */ BKE_subdiv_mesh_interpolate_position_on_edge(ctx->coarse_positions, ctx->coarse_edges, ctx->vert_to_edge_map, coarse_edge_index, is_simple, u, ctx->subdiv_positions[subdiv_vertex_index]); } /** \} */ /* -------------------------------------------------------------------- */ /** \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{}; subdiv_context.settings = settings; subdiv_context.coarse_mesh = coarse_mesh; subdiv_context.coarse_positions = BKE_mesh_positions(coarse_mesh); subdiv_context.coarse_edges = BKE_mesh_edges(coarse_mesh); subdiv_context.coarse_polys = BKE_mesh_polys(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. */ BKE_subdiv_stats_begin(&subdiv->stats, SUBDIV_STATS_SUBDIV_TO_MESH_GEOMETRY); SubdivForeachContext foreach_context; setup_foreach_callbacks(&subdiv_context, &foreach_context); SubdivMeshTLS tls{}; 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; } /** \} */