Revert "Fix T78296: Performance - Use Binary Search for MDeformWeight"
This reverts commit39b525e0f0
and3121015dce
as tests are failing.
This commit is contained in:
parent
d5208c45fa
commit
3e4f49fe71
Notes:
blender-bot
2023-02-14 05:37:19 +01:00
Referenced by issue #78296, Use binary search for MDeformVert
|
@ -40,7 +40,7 @@ extern "C" {
|
|||
|
||||
/* Blender file format version. */
|
||||
#define BLENDER_FILE_VERSION BLENDER_VERSION
|
||||
#define BLENDER_FILE_SUBVERSION 7
|
||||
#define BLENDER_FILE_SUBVERSION 6
|
||||
|
||||
/* 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
|
||||
|
|
|
@ -54,7 +54,6 @@ 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);
|
||||
|
@ -164,16 +163,6 @@ 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
|
||||
|
|
|
@ -47,7 +47,6 @@
|
|||
|
||||
#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"
|
||||
|
@ -321,7 +320,6 @@ static void layerInterp_mdeformvert(const void **sources,
|
|||
}
|
||||
dvert->dw[i] = node->dw;
|
||||
}
|
||||
BKE_defvert_array_sort_weights(dvert, totweight);
|
||||
}
|
||||
else {
|
||||
memset(dvert, 0, sizeof(*dvert));
|
||||
|
|
|
@ -216,47 +216,6 @@ 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
|
||||
*/
|
||||
|
@ -301,7 +260,6 @@ void BKE_defvert_remap(MDeformVert *dvert, int *map, const int map_len)
|
|||
dw->def_nr = map[dw->def_nr];
|
||||
}
|
||||
}
|
||||
defvert_sort_weights(dvert);
|
||||
}
|
||||
|
||||
/**
|
||||
|
@ -501,7 +459,6 @@ 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)
|
||||
|
@ -708,40 +665,23 @@ 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)
|
||||
{
|
||||
BLI_assert(dvert);
|
||||
BLI_assert(defgroup >= 0);
|
||||
if (dvert && defgroup >= 0) {
|
||||
MDeformWeight *dw = dvert->dw;
|
||||
unsigned int i;
|
||||
|
||||
int index = defvert_index_get(dvert, defgroup);
|
||||
if (index == -1) {
|
||||
return NULL;
|
||||
for (i = dvert->totweight; i != 0; i--, dw++) {
|
||||
if (dw->def_nr == defgroup) {
|
||||
return dw;
|
||||
}
|
||||
}
|
||||
}
|
||||
else {
|
||||
return &dvert->dw[index];
|
||||
BLI_assert(0);
|
||||
}
|
||||
|
||||
return NULL;
|
||||
}
|
||||
|
||||
/**
|
||||
|
@ -766,18 +706,17 @@ 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 + 1, dvert->dw, sizeof(MDeformWeight) * dvert->totweight);
|
||||
memcpy(dw_new, 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;
|
||||
}
|
||||
|
||||
|
@ -801,15 +740,14 @@ 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 + 1, dvert->dw, sizeof(MDeformWeight) * dvert->totweight);
|
||||
memcpy(dw_new, 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);
|
||||
}
|
||||
|
||||
/**
|
||||
|
@ -835,7 +773,7 @@ void BKE_defvert_remove_group(MDeformVert *dvert, MDeformWeight *dw)
|
|||
BLI_assert(dvert->dw != NULL);
|
||||
|
||||
if (i != dvert->totweight) {
|
||||
memmove(&dvert->dw[i], &dvert->dw[i + 1], sizeof(MDeformWeight) * dvert->totweight - i);
|
||||
dvert->dw[i] = dvert->dw[dvert->totweight];
|
||||
}
|
||||
|
||||
dvert->dw = MEM_reallocN(dvert->dw, sizeof(MDeformWeight) * dvert->totweight);
|
||||
|
@ -1587,17 +1525,4 @@ 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
|
||||
|
||||
/** \} */
|
||||
|
|
|
@ -534,7 +534,6 @@ void BKE_object_defgroup_index_map_apply(MDeformVert *dvert,
|
|||
dv->totweight = totweight;
|
||||
}
|
||||
}
|
||||
BKE_defvert_array_sort_weights(dv, dvert_len);
|
||||
}
|
||||
|
||||
/**
|
||||
|
|
|
@ -27,9 +27,6 @@
|
|||
#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"
|
||||
|
@ -37,7 +34,6 @@
|
|||
|
||||
#include "BKE_collection.h"
|
||||
#include "BKE_colortools.h"
|
||||
#include "BKE_deform.h"
|
||||
#include "BKE_lib_id.h"
|
||||
#include "BKE_main.h"
|
||||
|
||||
|
@ -358,26 +354,6 @@ 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.
|
||||
*
|
||||
|
|
|
@ -159,7 +159,6 @@
|
|||
#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
|
||||
|
@ -2045,7 +2044,6 @@ 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);
|
||||
}
|
||||
}
|
||||
|
|
|
@ -2642,7 +2642,6 @@ int ED_gpencil_join_objects_exec(bContext *C, wmOperator *op)
|
|||
dvert->dw->def_nr = idx;
|
||||
}
|
||||
}
|
||||
BKE_defvert_array_sort_weights(gps->dvert, gps->totpoints);
|
||||
}
|
||||
}
|
||||
}
|
||||
|
|
|
@ -286,7 +286,6 @@ 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. */
|
||||
|
|
Loading…
Reference in New Issue