CCD IK (Cylic Coordinate Descent IK ) : IK

 

chain 의 Root Node(=base)

각 chain 들의 노드(=link) 라 네이밍을 가정 하고 시작한다

 

root node 의 반대편 즉 chain 의 끝 노드(Chain End)에서부터 root node 까지 노드(Link)를 방문 하면서

Chain End 노드가 target 에 접근 하도록 각 노드(link)의 각도를 taret 방향으로 회전 시켜주는 방식이다

 

나중엔 Chain End 가 Target 과 같거나 가장 근접한 결과를 뽑아내는 알고리즘이다

FABRIK 와 달리 알고리즘의 해가 정확하지 존재하지 않을 수 있다

 

즉 CCD 는 가장 근사한 해를 찾는 알고리즘임으로 해를 찾지 못하는 경우를 대비하여

loop count 를 두고 그 횟수를 제한해야 하는 부분이 필요하다

 

 

 

CCD 영상

 

 

 

언리얼 에서의 CCD 영상

 

CCDIK (Cyclic Coordinate Descent Inverse Kinematics, 순환 좌표 하강 역운동학) 스켈레탈 컨트롤 노드는 경량 IK 솔버로 (FABRIK 과 비슷하며) 보통 본 체인 구동에 쓰입니다. 하지만 FABRIK 와 달리, CCDIK 는 솔브 도중 본의 회전을 제한하려는 경우 유용하게 쓰일 수 있는 각 컨스트레인트를 정의하는 기능을 제공합니다.

CCDIK 노드는 아래 그림처럼 절차적 애니메이션 구동에 쓰일 수 있습니다.

 

 

 

 

 

위 비디오에서 CCDIK 노드 프로퍼티의 Solver (솔버) 섹션을 사용하여 캐릭터의 왼쪽 어깨에 Root Bone (루트 본)을 설정했습니다. 그런 다음 Tip Bone (끝 본)을 캐릭터 검지 마지막 숫자로 설정합니다. Effector Location (이펙터 위치)를 조정할 때, IK 솔버가 인계하면, 체인의 본 각각이 따르고, 정의한 Rotation Limit Per Joints (조인트 당 회전 제한) 값을 기반으로 합니다. 이 각 제한은 본이 이상하게 회전하는 것을 방지하며 원하는 결과를 내기 위해서는 (본 단위로) 값을 조정해야 할 수 있습니다.

 

=> CCD는 조인트당 회전 되는 각도의 제한을 두어서 팔이 의도하지 않은 관절 형태로 회전 되는 것을 방지  할 수 있다

 

 

Tip bone : 본의 끝 노드로 오른손 검지 끝마디로 설정하고

Root bone 은 오른쪽 어깨 본으로 세팅 해놓으면 Root bone 부터 tip bone 까지에 걸처 본들에 대한 제한 각도들을 설정 할 수 있다(각 본에 대해 회전 제한 각도를 설정하기 위한 본들은 알아서 잡힌다, 본의 개수에 맞게끔) 가장 아래 쪽 7번 인덱스가 검지 끝 본을 말하며 6번은 검지 끝 본 이전 것노드를 말하며 각 숫자는 회저회전 할 수 있는 각도를 설정할 수 있다, 이 각도로 IK 도 중 본이 이상하게 꺽이는 현상을 방지할 수 있다

위 그림에서 보면 오른손 손가락이 타겟 즉 Effector Location 을 향하고 있는 것을 볼 수 있다, 하지만 각도를 0~2에 해당 하는 부분에 대해 0 으로 설정해 놓았기 때문에 회전 추적 되지 않고 어깨부터 3개 의 본들은 그자리에 있는 것을 볼 수 있다

 

 

나머지 3개에 대해서도 30도 정도의 회전각 반경을 주면 아래 그림 처럼 오른쪽 어깨부터 오른손 검지 손가락이 

타겟지점으로 향하는 것을 볼 수 있다

 

 

 

 

 

Using an iterative technique to determine orientations

for a multiple link IK chain

The way we will study here was first presented by Chris Welman in his

masters thesis on IK as an extension to work developed by Li-Chun

Tommy Wang and Chih Cheng Chen in an IEEE paper 'Transactions on

Robotics and Automation'. The technique is called Cyclic Coordinate

Descent. The principal algorithm is as follows:

 

1 Set a loop counter to zero.

2 Start with the last link in the chain.

3 Rotate this link to point towards the target.

4 Move down the chain and repeat step 2.

5 When the base object is reached, determine if the target has been

reached or a loop limit has been reached. If so exit, if not increment

loop counter and repeat from step 2.

This algorithm has the benefit of simplicity and can be easily

implemented.

To derive the angle

, we go back to the familiar methods of using

vectors. Remember that the dot product of vectors is given by

 

Unfortunately, the angle does not imply direction and we are interested in

both the angle and the direction. Since the cross product of two vectors

gives a perpendicular vector, we can use this to determine the direction.

By extending the vectors from two to three dimensions, we then have a z

value. The sign of this z value will give the direction in which to rotate.

 

 

defines the direction of rotation.

When using the algorithm, we start by iterating through the link chain to

find the last link. We then create unit vectors from the pivot point of the link

to the chain end and from the pivot point to the target. The inverse cosine

of the dot product of these two vectors gives the angle of rotation and the

third term of the result of the three-value vector cross product gives the

direction of rotation. We generate a rotation matrix using this information

and record the current chain end position.

 

 

We then move one link down the chain and determine new vectors from

the pivot point of the new link to the chain end and target and repeat the

dot product and cross product calculations. We then create a rotation

matrix and calculate the new location for the chain end. This procedure is

repeated until the base object is rotated. At this point we determine if we

are close enough to the target to exit the function. If not, we must repeat

the procedure. It is possible that the target cannot be reached. The

function needs to ensure that under such circumstances the program

does not enter an infinite loop. A simple technique to avoid this is to limit

the looping to a certain number of times; if this is exceeded then the

function exits.

If the total length of the links is less than the distance to the target, then

the goal can never be achieved and it can be useful to add this condition

to the code. Under these circumstances we return to the problem of

orientating a single link, the base link, and setting all other links to zero

rotation.

The code for the Cyclic Coordinate Descent method is as follows:

 

void CIKDemoDoc::SolveMultiLink() 
{
    //links.next 시작 부분 base 에 해당 하는 노드
    CLink* link = links.next, * lastlink, * tmplink; 
    int loopcount = 0; 
    double x, y, totallength, linkslength = 0.0, dotprod;
 
    double mag, theta, sign, sqdist; VECTOR pe, pt;
    
    //Check solution is possible
    //시작 부분 base link 와 target 까지의 거리를 구한다
    x = target.x - link->pos.x;
    y = -target.y - link->pos.y;
    totallength = sqrt(x*x + y*y);
    
    //Find the last link and links length
    
    //link(chain)들의 총 길이를 구한다
    while (link->next)
    {
        linkslength += link->length;
        lastlink = link;
        link = link->next;
    }
 
    //lastlink : chain End 마지막 노드
 
    //체인의 총 길이가 타겟에 닿을 수 있는 범위에 있는지 판단 
    //즉 체인이 타겟을 추적할 수 있는 범위안에 있는지 판단
    if (totallength < linkslength)
    {
        //Calculate Cyclic Coordinate Descent solution
        //link 마지막 노드
        link = lastlink;
 
        //최대 20 번까지 접근을 한다 : 완전한 해를 구하지 못하는 경우는 도중에 끊어야 한다
        while(link && loopcount<20)
        {
            //end effector 따라가는 target에 해당, right 는 chain end 로 가는 단위 벡터인듯
            //Calculate current endeffector position
            //endeffector = lastlink->length * lastlink->right + lastlink->pos;
            //endeffector 현재 chain 의 끝 지점을 endeffector 로 칭하는 듯
            endeffector.x = lastlink->length * lastlink->right.x +lastlink->pos.x;
            endeffector.y = lastlink->length * lastlink->right.y +lastlink->pos.y;
            
            //chain end 와 target 사이의 거리를 구한다
            //Calculate the squared distance from end effector to//target
            x = target.x - endeffector.x;
            y = target.y - endeffector.y;
            
            //chain end 와 target 사이의 거리가 0.1 보다 작다면 추적을 중지한다
            sqdist = x*x + y*y;
            if (sqdist < 0.1) 
                break;
            
            //link : pivot 에서 target 까지의 거리를 구한다
            //Calculate pivot to target vector
            pt.x = target.x - link->pos.x;
            pt.y = target.y - link->pos.y;
            pt.z = 0;
            
            //Calculate pivot to end effector vector
            
            //pivot 위치에서 endeffector( 첫번째 실행할때는 endeffector 가 chain End) 
 //까지의 거리를 구한다
            pe.x = endeffector.x - link->pos.x;
            pe.y = endeffector.y - link->pos.y;
            pe.z = 0;
 
            //Convert to unit vectors
            mag = sqrt(pt.x * pt.x + pt.y * pt.y);
            pt.x/=mag; 
            pt.y/=mag;
 
            mag = sqrt(pe.x * pe.x + pe.y * pe.y);
            pe.x/=mag; 
            pe.y/=mag;
            
            //Calculate dot product
            //endeffector 와 Target 의 내적을 구한다 => 1 * 1 * cos(theta)
            dotprod = pe.x * pt.x + pe.y * pt.y;
            
            //Calculate cross product for direction
            //외적 z 성분을 통해 회전 부호를 결정할 수 있다 
            sign = pe.x * pt.y - pe.y * pt.x;
            
            //각도를 구한다
            if (sign > 0.0)
            {
                theta = -acos(dotprod);
            }
            else
            {
                theta = acos(dotprod);
            }
            
            //각도를 구한다음 pivot 위치에서 end effector  가 target 로 까지 회전 
 //되어야 하는 각도를 더해준다
            link->rot.z += theta;
            
            //Set matrices for current link and all children
            
            tmplink = link;
            while(link)
            {
                link->CreateMatrix();
                link = link->next;
            }
            
            link = tmplink;
            
            //Move on to next link
            //link 가 첫번째 link 와 같다면 loopcount 를 증가 시키고 
            //(chain end) 끝 노드 부터 다시 반복을 시도하여 해를 구하기 위한 시도를 한다
            if (link==links.next)
            {
                loopcount++;
                link = lastlink;        
            }
            else
            {
                //나음 link 로 이동한다
                link = link->parent;
            }
        }
    }
    else
    {
        //chain 범위 밖에 있는 경우 첫번째  link 에는 target 으로 향하는 각도를 넣어주고
        //나머지 자식에해당하는 노드들은 0 도로 채우준다(체인이 닿을 수 있는 범위 
 //밖임으로 뻗는 형태가 된다)
        //Just use the single link solution
        link = links.next;
        x = target.x - link->pos.x;
        y = -target.y - link->pos.x;
 
        //첫번째 base  link 에서 target 까지의 거리를 구한다음
 
        //taret으로 향하는 절대 각을 구한다
        link->rot.z = atan(y/x);
 
        if (x<0) 
            link->rot.z = PI + link->rot.z;
 
        //나머지 
        while (link->next)
        { 
            link = link->next; 
            link->rot.z = 0.0; 
        }
    }
 
    link = links.next; 
 
    while (link) 
    {
        link->CreateMatrix(); 
        link = link->next; 
    }
}

 

 

 

 ref :

http://nedrilad.com/Tutorial/topic-73/Real-time-3D-Character-Animation-with-Visual-C-197.html

http://nedrilad.com/Tutorial/topic-73/Real-time-3D-Character-Animation-with-Visual-C-198.html

https://docs.unrealengine.com/ko/Engine/Animation/NodeReference/SkeletalControls/CCDIK/index.html