From cc69f1301387ea920a225b6eb49283e3c03e1b06 Mon Sep 17 00:00:00 2001 From: Joshua Leung Date: Mon, 20 Jul 2009 12:42:31 +0000 Subject: 2.5 - Constraints Editing + Keyframe Drawing Tweaks Constraints: * Adding constraints with targets should now work. -- (When no target is provided, the code to create a new target is not yet in place again yet) * Constraints can be added in Object and PoseModes again using the Ctrl-Shift-C hotkey. * All constraints can now be cleared from the active Object or selected Bones using the Ctrl-Alt-C hotkey. * Added warnings when adding constraints invalid for the current context, and removed the old add_constraint() function. * Buttons window updates correctly after adding keyframes now Keyframes Drawing: * Removed un-necessary extra function-call for RB-Tree implementation, by inlining a special one-off case. * Keyframe diamonds which are not within the viewable area are now not drawn (but filtering will still need to find them). --- source/blender/blenlib/intern/DLRB_tree.c | 48 ++++++++++++++----------------- 1 file changed, 21 insertions(+), 27 deletions(-) (limited to 'source/blender/blenlib/intern/DLRB_tree.c') diff --git a/source/blender/blenlib/intern/DLRB_tree.c b/source/blender/blenlib/intern/DLRB_tree.c index 766547cee05..af9774c6afd 100644 --- a/source/blender/blenlib/intern/DLRB_tree.c +++ b/source/blender/blenlib/intern/DLRB_tree.c @@ -161,7 +161,6 @@ static DLRBT_Node *get_uncle (DLRBT_Node *node) /* *********************************************** */ /* Tree Rotation Utilities */ -/* Left Rotation is only done for Right-Right Case, and Left-Right Case */ static void rotate_left (DLRBT_Tree *tree, DLRBT_Node *root) { DLRBT_Node **root_slot, *pivot; @@ -235,7 +234,6 @@ static void rotate_right (DLRBT_Tree *tree, DLRBT_Node *root) static void insert_check_1(DLRBT_Tree *tree, DLRBT_Node *node); static void insert_check_2(DLRBT_Tree *tree, DLRBT_Node *node); static void insert_check_3(DLRBT_Tree *tree, DLRBT_Node *node); -static void insert_check_4(DLRBT_Tree *tree, DLRBT_Node *node); /* ----- */ @@ -286,7 +284,7 @@ static void insert_check_2 (DLRBT_Tree *tree, DLRBT_Node *node) } } -/* W. 4) Perform rotation on sub-tree containing the 'new' node */ +/* W. 4+5) Perform rotation on sub-tree containing the 'new' node, then do any */ static void insert_check_3 (DLRBT_Tree *tree, DLRBT_Node *node) { DLRBT_Node *gp= get_grandparent(node); @@ -305,34 +303,30 @@ static void insert_check_3 (DLRBT_Tree *tree, DLRBT_Node *node) rotate_right(tree, node); node= node->right; } - // TODO: what about other cases? - /* fix old parent's color-tagging */ - insert_check_4(tree, node); + /* fix old parent's color-tagging, and perform rotation on the old parent in the + * opposite direction if needed for the current situation + * NOTE: in the code above, node pointer is changed to point to the old parent + */ + if (node) { + /* get 'new' grandparent (i.e. grandparent for old-parent (node)) */ + gp= get_grandparent(node); + + /* modify the coloring of the grandparent and parent so that they still satisfy the constraints */ + node->parent->tree_col= DLRBT_BLACK; + gp->tree_col= DLRBT_RED; + + /* if there are several nodes that all form a left chain, do a right rotation to correct this + * (or a rotation in the opposite direction if they all form a right chain) + */ + if ((node == node->parent->left) && (node->parent == gp->left)) + rotate_right(tree, gp); + else //if ((node == node->parent->right) && (node->parent == gp->right)) + rotate_left(tree, gp); + } } } -/* W. 5) Perform rotation in the opposite direction on the parent of the given node */ -static void insert_check_4 (DLRBT_Tree *tree, DLRBT_Node *node) -{ - DLRBT_Node *gp= get_grandparent(node); - - if (node == NULL) - return; - - /* modify the coloring of the grandparent and parent so that they still satisfy the constraints */ - node->parent->tree_col= DLRBT_BLACK; - gp->tree_col= DLRBT_RED; - - /* if there are several nodes that all form a left chain, do a right rotation to correct this - * (or a rotation in the opposite direction if they all form a right chain) - */ - if ((node == node->parent->left) && (node->parent == gp->left)) - rotate_right(tree, gp); - else /* ((node == node->parent->right) && (node->parent == gp->right)) */ - rotate_left(tree, gp); -} - /* ----- */ /* Balance the tree after the given element has been added to it -- cgit v1.2.3