diff options
author | Campbell Barton <ideasman42@gmail.com> | 2016-01-09 01:12:06 +0300 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2016-01-09 01:17:18 +0300 |
commit | 70028e73dcbf4494c7584be3266268eb44c0ac4b (patch) | |
tree | 7401908b40b70705c415e35b4794eb8b8cbfc986 /source | |
parent | 2d973f44e2fd47fa2fd4c1f59247c56517fcb26c (diff) |
Readfile: use hash lookup for bones
Bone loop for reconstructing links was O(n^2)
Diffstat (limited to 'source')
-rw-r--r-- | source/blender/blenkernel/BKE_armature.h | 5 | ||||
-rw-r--r-- | source/blender/blenkernel/intern/armature.c | 57 | ||||
-rw-r--r-- | source/blender/blenloader/intern/readfile.c | 41 |
3 files changed, 72 insertions, 31 deletions
diff --git a/source/blender/blenkernel/BKE_armature.h b/source/blender/blenkernel/BKE_armature.h index e1885e46b24..6d00110e318 100644 --- a/source/blender/blenkernel/BKE_armature.h +++ b/source/blender/blenkernel/BKE_armature.h @@ -34,6 +34,7 @@ */ struct Bone; +struct GHash; struct Main; struct bArmature; struct bPoseChannel; @@ -72,6 +73,7 @@ extern "C" { struct bArmature *BKE_armature_add(struct Main *bmain, const char *name); struct bArmature *BKE_armature_from_object(struct Object *ob); +int BKE_armature_bonelist_count(struct ListBase *lb); void BKE_armature_bonelist_free(struct ListBase *lb); void BKE_armature_free(struct bArmature *arm); void BKE_armature_make_local(struct bArmature *arm); @@ -84,7 +86,8 @@ bool BKE_pose_minmax(struct Object *ob, float r_min[3], float r_max[3], bool use int bone_autoside_name(char name[64], int strip_number, short axis, float head, float tail); -struct Bone *BKE_armature_find_bone_name(struct bArmature *arm, const char *name); +struct Bone *BKE_armature_find_bone_name(struct bArmature *arm, const char *name); +struct GHash *BKE_armature_bone_from_name_map(struct bArmature *arm); bool BKE_armature_bone_flag_test_recursive(const struct Bone *bone, int flag); diff --git a/source/blender/blenkernel/intern/armature.c b/source/blender/blenkernel/intern/armature.c index f5d732b5551..74fffdd664f 100644 --- a/source/blender/blenkernel/intern/armature.c +++ b/source/blender/blenkernel/intern/armature.c @@ -38,7 +38,9 @@ #include "MEM_guardedalloc.h" #include "BLI_math.h" -#include "BLI_blenlib.h" +#include "BLI_listbase.h" +#include "BLI_string.h" +#include "BLI_ghash.h" #include "BLI_utildefines.h" #include "DNA_anim_types.h" @@ -91,6 +93,16 @@ bArmature *BKE_armature_from_object(Object *ob) return NULL; } +int BKE_armature_bonelist_count(ListBase *lb) +{ + int i = 0; + for (Bone *bone = lb->first; bone; bone = bone->next) { + i += 1 + BKE_armature_bonelist_count(&bone->childbase); + } + + return i; +} + void BKE_armature_bonelist_free(ListBase *lb) { Bone *bone; @@ -229,15 +241,15 @@ bArmature *BKE_armature_copy(bArmature *arm) return newArm; } -static Bone *get_named_bone_bonechildren(Bone *bone, const char *name) +static Bone *get_named_bone_bonechildren(ListBase *lb, const char *name) { Bone *curBone, *rbone; - if (STREQ(bone->name, name)) - return bone; + for (curBone = lb->first; curBone; curBone = curBone->next) { + if (STREQ(curBone->name, name)) + return curBone; - for (curBone = bone->childbase.first; curBone; curBone = curBone->next) { - rbone = get_named_bone_bonechildren(curBone, name); + rbone = get_named_bone_bonechildren(&curBone->childbase, name); if (rbone) return rbone; } @@ -246,21 +258,38 @@ static Bone *get_named_bone_bonechildren(Bone *bone, const char *name) } -/* Walk the list until the bone is found */ +/** + * Walk the list until the bone is found (slow!), + * use #BKE_armature_bone_from_name_map for multiple lookups. + */ Bone *BKE_armature_find_bone_name(bArmature *arm, const char *name) { - Bone *bone = NULL, *curBone; - if (!arm) return NULL; - for (curBone = arm->bonebase.first; curBone; curBone = curBone->next) { - bone = get_named_bone_bonechildren(curBone, name); - if (bone) - return bone; + return get_named_bone_bonechildren(&arm->bonebase, name); +} + +static void armature_bone_from_name_insert_recursive(GHash *bone_hash, ListBase *lb) +{ + for (Bone *bone = lb->first; bone; bone = bone->next) { + BLI_ghash_insert(bone_hash, bone->name, bone); + armature_bone_from_name_insert_recursive(bone_hash, &bone->childbase); } +} - return bone; +/** + * Create a (name -> bone) map. + * + * \note typically #bPose.chanhash us used via #BKE_pose_channel_find_name + * this is for the cases we can't use pose channels. + */ +GHash *BKE_armature_bone_from_name_map(bArmature *arm) +{ + const int bones_count = BKE_armature_bonelist_count(&arm->bonebase); + GHash *bone_hash = BLI_ghash_str_new_ex(__func__, bones_count); + armature_bone_from_name_insert_recursive(bone_hash, &arm->bonebase); + return bone_hash; } bool BKE_armature_bone_flag_test_recursive(const Bone *bone, int flag) diff --git a/source/blender/blenloader/intern/readfile.c b/source/blender/blenloader/intern/readfile.c index 84565fcb89f..fd144c0ebc0 100644 --- a/source/blender/blenloader/intern/readfile.c +++ b/source/blender/blenloader/intern/readfile.c @@ -3185,18 +3185,23 @@ static void direct_link_constraints(FileData *fd, ListBase *lb) static void lib_link_pose(FileData *fd, Main *bmain, Object *ob, bPose *pose) { - bPoseChannel *pchan; bArmature *arm = ob->data; - int rebuild = 0; if (!pose || !arm) return; /* always rebuild to match proxy or lib changes, but on Undo */ - if (fd->memfile == NULL) - if (ob->proxy || (ob->id.lib==NULL && arm->id.lib)) - rebuild = 1; - + bool rebuild = false; + + if (fd->memfile == NULL) { + if (ob->proxy || (ob->id.lib==NULL && arm->id.lib)) { + rebuild = true; + } + } + + /* avoid string */ + GHash *bone_hash = BKE_armature_bone_from_name_map(arm); + if (ob->proxy) { /* sync proxy layer */ if (pose->proxy_layer) @@ -3204,28 +3209,32 @@ static void lib_link_pose(FileData *fd, Main *bmain, Object *ob, bPose *pose) /* sync proxy active bone */ if (pose->proxy_act_bone[0]) { - Bone *bone = BKE_armature_find_bone_name(arm, pose->proxy_act_bone); - if (bone) + Bone *bone = BLI_ghash_lookup(bone_hash, pose->proxy_act_bone); + if (bone) { arm->act_bone = bone; + } } } - - for (pchan = pose->chanbase.first; pchan; pchan=pchan->next) { + + for (bPoseChannel *pchan = pose->chanbase.first; pchan; pchan = pchan->next) { lib_link_constraints(fd, (ID *)ob, &pchan->constraints); - - /* hurms... loop in a loop, but yah... later... (ton) */ - pchan->bone = BKE_armature_find_bone_name(arm, pchan->name); + + pchan->bone = BLI_ghash_lookup(bone_hash, pchan->name); pchan->custom = newlibadr_us(fd, arm->id.lib, pchan->custom); - if (pchan->bone == NULL) - rebuild= 1; - else if (ob->id.lib==NULL && arm->id.lib) { + if (UNLIKELY(pchan->bone == NULL)) { + rebuild = true; + } + else if ((ob->id.lib == NULL) && arm->id.lib) { /* local pose selection copied to armature, bit hackish */ pchan->bone->flag &= ~BONE_SELECTED; pchan->bone->flag |= pchan->selectflag; } } + + BLI_ghash_free(bone_hash, NULL, NULL); + if (rebuild) { DAG_id_tag_update_ex(bmain, &ob->id, OB_RECALC_OB | OB_RECALC_DATA | OB_RECALC_TIME); BKE_pose_tag_recalc(bmain, pose); |