diff options
-rw-r--r-- | source/blender/blenkernel/BKE_blender_version.h | 2 | ||||
-rw-r--r-- | source/blender/blenkernel/BKE_deform.h | 11 | ||||
-rw-r--r-- | source/blender/blenkernel/intern/customdata.c | 2 | ||||
-rw-r--r-- | source/blender/blenkernel/intern/deform.c | 107 | ||||
-rw-r--r-- | source/blender/blenkernel/intern/object_deform.c | 1 | ||||
-rw-r--r-- | source/blender/blenloader/intern/versioning_290.c | 24 | ||||
-rw-r--r-- | source/blender/blenloader/intern/writefile.c | 2 | ||||
-rw-r--r-- | source/blender/editors/gpencil/gpencil_data.c | 1 | ||||
-rw-r--r-- | source/blender/makesdna/DNA_meshdata_types.h | 1 |
9 files changed, 134 insertions, 17 deletions
diff --git a/source/blender/blenkernel/BKE_blender_version.h b/source/blender/blenkernel/BKE_blender_version.h index 57f22a8d709..556c1c961dc 100644 --- a/source/blender/blenkernel/BKE_blender_version.h +++ b/source/blender/blenkernel/BKE_blender_version.h @@ -40,7 +40,7 @@ extern "C" { /* Blender file format version. */ #define BLENDER_FILE_VERSION BLENDER_VERSION -#define BLENDER_FILE_SUBVERSION 6 +#define BLENDER_FILE_SUBVERSION 7 /* Minimum Blender version that supports reading file written with the current * version. Older Blender versions will test this and show a warning if the file diff --git a/source/blender/blenkernel/BKE_deform.h b/source/blender/blenkernel/BKE_deform.h index 04b85aebb39..b5a7df9ff57 100644 --- a/source/blender/blenkernel/BKE_deform.h +++ b/source/blender/blenkernel/BKE_deform.h @@ -54,6 +54,7 @@ void BKE_object_defgroup_unique_name(struct bDeformGroup *dg, struct Object *ob) struct MDeformWeight *BKE_defvert_find_index(const struct MDeformVert *dv, const int defgroup); struct MDeformWeight *BKE_defvert_ensure_index(struct MDeformVert *dv, const int defgroup); +void BKE_defvert_array_sort_weights(struct MDeformVert *dv, const int num_verts); void BKE_defvert_add_index_notest(struct MDeformVert *dv, int defgroup, const float weight); void BKE_defvert_remove_group(struct MDeformVert *dvert, struct MDeformWeight *dw); void BKE_defvert_clear(struct MDeformVert *dvert); @@ -163,6 +164,16 @@ void BKE_defvert_extract_vgroup_to_polyweights(struct MDeformVert *dvert, void BKE_defvert_weight_to_rgb(float r_rgb[3], const float weight); +#ifndef NDEBUG +bool BKE_defvert_is_sorted_for_assert(const struct MDeformVert *dv); +# define BKE_DEFVERT_IS_SORTED_ASSERT(dv) BLI_assert(BKE_defvert_is_sorted_for_assert(dv)) +#else +# define BKE_DEFVERT_IS_SORTED_ASSERT(dv) \ + if (false) { \ + (void)(dv); \ + } +#endif + #ifdef __cplusplus } #endif diff --git a/source/blender/blenkernel/intern/customdata.c b/source/blender/blenkernel/intern/customdata.c index c11fa69db76..6843c4c58fa 100644 --- a/source/blender/blenkernel/intern/customdata.c +++ b/source/blender/blenkernel/intern/customdata.c @@ -47,6 +47,7 @@ #include "BKE_customdata.h" #include "BKE_customdata_file.h" +#include "BKE_deform.h" #include "BKE_main.h" #include "BKE_mesh_mapping.h" #include "BKE_mesh_remap.h" @@ -320,6 +321,7 @@ static void layerInterp_mdeformvert(const void **sources, } dvert->dw[i] = node->dw; } + BKE_defvert_array_sort_weights(dvert, count); } else { memset(dvert, 0, sizeof(*dvert)); diff --git a/source/blender/blenkernel/intern/deform.c b/source/blender/blenkernel/intern/deform.c index b97935d57f2..7e924db5ae4 100644 --- a/source/blender/blenkernel/intern/deform.c +++ b/source/blender/blenkernel/intern/deform.c @@ -216,6 +216,47 @@ void BKE_defvert_sync(MDeformVert *dvert_dst, const MDeformVert *dvert_src, cons } } +/* -------------------------------------------------------------------- */ +/** \name Deform Weights - Sorting + * + * \{ */ + +/* Reorder the weights so they are sorted. It is required that all `MDeformVert` weights are sorted + * so we can use binary search. + */ +static int defweight_cmp(const void *a, const void *b) +{ + const MDeformWeight *dw1 = a; + const MDeformWeight *dw2 = b; + if (dw1->def_nr < dw2->def_nr) { + return -1; + } + else if (dw1->def_nr > dw2->def_nr) { + return 1; + } + else { + return 0; + } +} + +static void defvert_sort_weights(struct MDeformVert *dvert) +{ + if (dvert->dw) { + qsort(dvert->dw, dvert->totweight, sizeof(MDeformWeight), defweight_cmp); + } +} + +void BKE_defvert_array_sort_weights(struct MDeformVert *dvert, const int num_verts) +{ + if (!dvert) { + return; + } + for (int i = 0; i < num_verts; i++) { + defvert_sort_weights(&dvert[i]); + } +} +/* \} */ + /** * be sure all flip_map values are valid */ @@ -260,6 +301,7 @@ void BKE_defvert_remap(MDeformVert *dvert, int *map, const int map_len) dw->def_nr = map[dw->def_nr]; } } + defvert_sort_weights(dvert); } /** @@ -459,6 +501,7 @@ void BKE_defvert_flip(MDeformVert *dvert, const int *flip_map, const int flip_ma } } } + defvert_sort_weights(dvert); } void BKE_defvert_flip_merged(MDeformVert *dvert, const int *flip_map, const int flip_map_len) @@ -665,23 +708,40 @@ float BKE_defvert_array_find_weight_safe(const struct MDeformVert *dvert, return BKE_defvert_find_weight(dvert + index, defgroup); } +static int defvert_index_get(const MDeformVert *dvert, const int defgroup) +{ + int low = 0; + int high = dvert->totweight - 1; + int mid; + while (low < high) { + mid = (low + high) / 2; + MDeformWeight *dweight = &dvert->dw[mid]; + const unsigned int dweight_def_nr = dweight->def_nr; + if (dweight_def_nr == defgroup) { + return mid; + } + if (dweight_def_nr < defgroup) { + low = mid + 1; + } + else { + high = mid - 1; + } + } + return -1; +} + MDeformWeight *BKE_defvert_find_index(const MDeformVert *dvert, const int defgroup) { - if (dvert && defgroup >= 0) { - MDeformWeight *dw = dvert->dw; - unsigned int i; + BLI_assert(dvert); + BLI_assert(defgroup >= 0); - for (i = dvert->totweight; i != 0; i--, dw++) { - if (dw->def_nr == defgroup) { - return dw; - } - } + int index = defvert_index_get(dvert, defgroup); + if (index == -1) { + return NULL; } else { - BLI_assert(0); + return &dvert->dw[index]; } - - return NULL; } /** @@ -706,17 +766,18 @@ MDeformWeight *BKE_defvert_ensure_index(MDeformVert *dvert, const int defgroup) dw_new = MEM_mallocN(sizeof(MDeformWeight) * (dvert->totweight + 1), "deformWeight"); if (dvert->dw) { - memcpy(dw_new, dvert->dw, sizeof(MDeformWeight) * dvert->totweight); + memcpy(dw_new + 1, dvert->dw, sizeof(MDeformWeight) * dvert->totweight); MEM_freeN(dvert->dw); } dvert->dw = dw_new; - dw_new += dvert->totweight; dw_new->weight = 0.0f; dw_new->def_nr = defgroup; /* Group index */ dvert->totweight++; + defvert_sort_weights(dvert); + return dw_new; } @@ -740,14 +801,15 @@ void BKE_defvert_add_index_notest(MDeformVert *dvert, int defgroup, const float dw_new = MEM_callocN(sizeof(MDeformWeight) * (dvert->totweight + 1), "defvert_add_to group, new deformWeight"); if (dvert->dw) { - memcpy(dw_new, dvert->dw, sizeof(MDeformWeight) * dvert->totweight); + memcpy(dw_new + 1, dvert->dw, sizeof(MDeformWeight) * dvert->totweight); MEM_freeN(dvert->dw); } dvert->dw = dw_new; - dw_new += dvert->totweight; dw_new->weight = weight; dw_new->def_nr = defgroup; dvert->totweight++; + + defvert_sort_weights(dvert); } /** @@ -773,7 +835,7 @@ void BKE_defvert_remove_group(MDeformVert *dvert, MDeformWeight *dw) BLI_assert(dvert->dw != NULL); if (i != dvert->totweight) { - dvert->dw[i] = dvert->dw[dvert->totweight]; + memmove(&dvert->dw[i], &dvert->dw[i + 1], sizeof(MDeformWeight) * dvert->totweight - i); } dvert->dw = MEM_reallocN(dvert->dw, sizeof(MDeformWeight) * dvert->totweight); @@ -1525,4 +1587,17 @@ void BKE_defvert_weight_to_rgb(float r_rgb[3], const float weight) } } +#ifndef NDEBUG +bool BKE_defvert_is_sorted_for_assert(const MDeformVert *dv) +{ + const MDeformWeight *dw = dv->dw; + for (int i = 1; i < dv->totweight; i++) { + if (dw[i - 1].def_nr > dw[i].def_nr) { + return false; + } + } + return true; +} +#endif + /** \} */ diff --git a/source/blender/blenkernel/intern/object_deform.c b/source/blender/blenkernel/intern/object_deform.c index 6ca1442497a..f7d22f300ef 100644 --- a/source/blender/blenkernel/intern/object_deform.c +++ b/source/blender/blenkernel/intern/object_deform.c @@ -534,6 +534,7 @@ void BKE_object_defgroup_index_map_apply(MDeformVert *dvert, dv->totweight = totweight; } } + BKE_defvert_array_sort_weights(dv, dvert_len); } /** diff --git a/source/blender/blenloader/intern/versioning_290.c b/source/blender/blenloader/intern/versioning_290.c index 0d16b58d28f..a99da5eb333 100644 --- a/source/blender/blenloader/intern/versioning_290.c +++ b/source/blender/blenloader/intern/versioning_290.c @@ -27,6 +27,9 @@ #include "DNA_constraint_types.h" #include "DNA_genfile.h" #include "DNA_gpencil_modifier_types.h" +#include "DNA_gpencil_types.h" +#include "DNA_lattice_types.h" +#include "DNA_mesh_types.h" #include "DNA_modifier_types.h" #include "DNA_object_types.h" #include "DNA_screen_types.h" @@ -34,6 +37,7 @@ #include "BKE_collection.h" #include "BKE_colortools.h" +#include "BKE_deform.h" #include "BKE_lib_id.h" #include "BKE_main.h" @@ -354,6 +358,26 @@ void blo_do_versions_290(FileData *fd, Library *UNUSED(lib), Main *bmain) } } + /* Make sure that all weights of MDeformVert are sorted. */ + if (!MAIN_VERSION_ATLEAST(bmain, 290, 7)) { + for (Mesh *mesh = bmain->meshes.first; mesh != NULL; mesh = mesh->id.next) { + BKE_defvert_array_sort_weights(mesh->dvert, mesh->totvert); + } + for (Lattice *lt = bmain->lattices.first; lt != NULL; lt = lt->id.next) { + const int totvert = lt->pntsu * lt->pntsv * lt->pntsw; + BKE_defvert_array_sort_weights(lt->dvert, totvert); + } + for (bGPdata *gp = bmain->gpencils.first; gp != NULL; gp = gp->id.next) { + LISTBASE_FOREACH (bGPDlayer *, layer, &gp->layers) { + LISTBASE_FOREACH (bGPDframe *, frame, &layer->frames) { + LISTBASE_FOREACH (bGPDstroke *, stroke, &frame->strokes) { + BKE_defvert_array_sort_weights(stroke->dvert, stroke->totpoints); + } + } + } + } + } + /** * Versioning code until next subversion bump goes here. * diff --git a/source/blender/blenloader/intern/writefile.c b/source/blender/blenloader/intern/writefile.c index 4e2b4fef9a0..29461298cea 100644 --- a/source/blender/blenloader/intern/writefile.c +++ b/source/blender/blenloader/intern/writefile.c @@ -159,6 +159,7 @@ #include "BKE_constraint.h" #include "BKE_curve.h" #include "BKE_curveprofile.h" +#include "BKE_deform.h" #include "BKE_fcurve.h" #include "BKE_fcurve_driver.h" #include "BKE_global.h" // for G @@ -2044,6 +2045,7 @@ static void write_dverts(BlendWriter *writer, int count, MDeformVert *dvlist) /* Write deformation data for each dvert */ for (int i = 0; i < count; i++) { if (dvlist[i].dw) { + BKE_DEFVERT_IS_SORTED_ASSERT(&dvlist[i]); BLO_write_struct_array(writer, MDeformWeight, dvlist[i].totweight, dvlist[i].dw); } } diff --git a/source/blender/editors/gpencil/gpencil_data.c b/source/blender/editors/gpencil/gpencil_data.c index 96b0296a7de..9fd74ef2c46 100644 --- a/source/blender/editors/gpencil/gpencil_data.c +++ b/source/blender/editors/gpencil/gpencil_data.c @@ -2642,6 +2642,7 @@ int ED_gpencil_join_objects_exec(bContext *C, wmOperator *op) dvert->dw->def_nr = idx; } } + BKE_defvert_array_sort_weights(gps->dvert, gps->totpoints); } } } diff --git a/source/blender/makesdna/DNA_meshdata_types.h b/source/blender/makesdna/DNA_meshdata_types.h index cc2ba3fb999..a4299d3c6a2 100644 --- a/source/blender/makesdna/DNA_meshdata_types.h +++ b/source/blender/makesdna/DNA_meshdata_types.h @@ -286,6 +286,7 @@ typedef struct MDeformWeight { } MDeformWeight; typedef struct MDeformVert { + /* Mut be sorted by def_nr due to binary search. */ struct MDeformWeight *dw; int totweight; /** Flag is only in use as a run-time tag at the moment. */ |