3D 전개도 앱 개발기-2

1편에서는 Probuilder를 이용한 고정된 형태의 입체도형를 보여주는 것에서 시작하여, 도형의 Property를 이용해 어떠한 형태의 입체도형이든 그려내기까지의 삽질기를 다뤘다.

 

이 포스팅에서는, 입체도형을 전개도로 펼치는 방법과 한 입체도형에서 가능한 모든 형태의 전개도를 찾는 방법에 대해 다룬다.

 

---

입체도형을 전개도로 펼치기

 

 

어떻게 입체도형을 전개도로 만들 수 있을 것인가?

먼저, 입체도형을 전개도로 만드는 행위를 분석해보면 다음의 사실을 발견할 수 있다.

• 우리는 n개의 면을 가진 입체도형에 대해 바닥면을 제외한 n-1번의 시행을 통해 전개도를 만든다.
• 면 x를 접기 위해서는 접고자 하는 방향에 닿아 있는 면 y에 '자식'으로 귀속됨을 의미한다.
• 면 x를 접거나 펴기 위해서는 각도 d가 필요하며, 각도 d는 이 두 행위에 공통적으로 적용된다.
• 각도 d는 면 x와 면 y의 벡터연산을 통해 구할 수 있다.

 

예외적으로, 면을 접을 수 없는 상황이 발생하는데 그 경우는 다음과 같다.

• 접고자 하는 면x을 기준으로, 접고자 하는 방향에 접하고 있는 면 y가 없는 경우
• 접고자 하는 면x가 이미 접혀 있는 경우

이러한 예외 사항을 판단하는 데에는 Fake cuboid를 사용하는데, 면 x의 특정 변 y의 중점에서 게임오브젝트를 하나 만들어 겹침 확인을 한 뒤 fake cuboid는 삭제하는 것이다. 코드는 다음과 같다.

 

public static Collider[] getOverlappingCollidersWithinCertainPosition(Vector3 centerPositionOfAxis){
        GameObject fakeCuboid = new GameObject("faceCuboid");
        fakeCuboid.transform.position = centerPositionOfAxis;
        var rigid = fakeCuboid.AddComponent<Rigidbody>();
        rigid.isKinematic = true;
        rigid.useGravity = false;

        var box = fakeCuboid.AddComponent<BoxCollider>();
        box.size = Vector3.one * 0.1f;
        box.isTrigger = true;

        Collider[] colliders = Physics.OverlapBox(centerPositionOfAxis, box.size); //Plane이름을 가진 것만 추출
        List<Collider> list = new List<Collider>(); 
        for(int i=0; i<colliders.Length; i++){
            if(colliders[i].transform.name.Contains("Plane")){
                list.Add(colliders[i]);
            }
        }

        Destroy(fakeCuboid);
        return list.ToArray();
    }    

 

이런 식으로 예외 상황을 확인 뒤, 실제 특정 면을 특정 방향으로 접도록 하였다.

실제 활동은 접고자 하는 면 선택 -> 접을 수 있는 가능한 방향을 화살표로 표시 -> 화살표 클릭하면 해당 방향으로 접기로 구성된다. 이러한 활동은 미리 준비된 시나리오 활동이 아닌 알고리즘적 활동으로서, 학생들은 본인이 원하는 면을 본인이 원하는 방향으로 접어볼 수 있다.

 

 

 

 

---

가능한한 모든 전개도 형태 구하기

 

 

하지만, 입체도형을 전개도로 만드는 기능이 본 프로그램에 충분조건인 것은 아니다. 입체도형을 전개도로 만드는 기능과 전개도를 입체도형으로 만드는 기능은 완전 다른 이야기로, 위에서 개발한 알고리즘을 이용해 전개도를 입체도형으로 만들 수는 없다. 위 알고리즘은 단순히 학습자의 접는 활동을 모방한 것에 불과하다.

 

전개도를 입체도형으로 만들기 위해서는, 먼저 입체도형이 전개도가 되는 과정에 대한 데이터가 필요하다.

이러한 데이터는 "A0 B1 C2 D3"와 같이 표현될 수 있는데, 면 A를 0번 방향으로 접고 나서 면 B를 1번 방향으로 접고, 면 C를 2번 방향으로 접고 면 D를 3번 방향으로 접는 행위로 설명할 수 있다.

 

예를 들어, 피라미드 모양의 삼각뿔을 생각해보면, 밑면을 제외한 면의 수는 4개이고, 각 면에서 가능한 접는 방향의 수(변의 수)는 3개씩이며, 전개도를 만들기 위한 시행횟수는 4회이다.

 

따라서 이 입체도형에서 가능한 모든 경우의 접는 행위는

A0 B0 C0 D0

A0 B0 C0 D1

A0 B0 C0 D2

.......

 

와 같이 나타낼 수 있고, 이러한 경우의 수는 총 81가지가 나온다.

 

하지만, 이게 끝이 아닌데,

면을 선택하는 순서가 ABCD가 아닌, ABDC, DCBA 등 다양할 수 있다는 것이다.

 

따라서, 이를 정리하면 바닥면을 제외한 입체도형의 면의 수가 n개이고, 각각의 면이 갖고 있는 변의 수가 a,b,c...일 때, 가능한한 모든 경우의 수는 n! * (a*b*c*...)로 나타낼 수 있다. 

 

이제 Test 클래스를 만들고, 기계의 힘을 이용해 한 입체도형이 만들어낼 수 있는 모든 전개도의 가능한 형태를 구해보자. 먼저, 입체도형의 면을 선택하는 순서에 대한 순열 배열을 하나 만들자. 그리고 이 순열 배열을 입력받은 코루틴에서 각 면의 순서에 맞게 특정 방향으로 면을 접도록 한다.

 

그러나, 이 n!의 값이 너무 크므로 멀티스레딩 유사 기능을 만들기 위해, 전개도를 찾을 오브젝트를 여러개 만들어 놓고, 각각의 오브젝트에 공평하게 순열 배열을 나눠주도록 하자. 코드는 다음과 같다.

IEnumerator startComputingAllAnswers(int imitationNumber){ 
        GameObject testParent = new GameObject("Test Parent");
        Utils.Permutation permutation = new Utils.Permutation( figureGameObject.GetComponent<FigureManager>().mainFigure.facesList.Count -1 );  //바닥면은 제외해야 하므로 면 수에서 -1개 함
        List<string> permutationStr = new List<String>();          //0 1 2   , 0 1 2 와 같은 순열 배열이 str형태로 들어 있음
        while(permutation != null){
            permutationStr.Add(permutation.ToString()); 
            permutation = permutation.Successor(); 
        }

        if(permutationStr.Count % imitationNumber != 0) //위의 go[]에 공평히 담을 수 없으면 작동 안함
        {
            Debug.Log("size error "+permutationStr.Count);
            yield break;
        }

        GameObject[] imitatedFigures = new GameObject[imitationNumber];             //imitationNumber에 맞게 기존 도형과 arrows를 복제한다
        
        int zPostion = diff;
        int xPosition = diff;
        for(int i=0; i<imitationNumber; i++){  
            GameObject figure = Instantiate(figureGameObject, new Vector3(xPosition, yPosition, zPostion), Quaternion.identity);
            yield return StartCoroutine(startInitializing_FigureGO(figure));   
            figure.name = "FigureClone: "+(i+1); 
            imitatedFigures[i] = figure; 

            xPosition = xPosition + diff;
        }  
        List<string> tempPermutationStr = new List<string>();       //imitaionNumber개씩 묶어서 코루틴 시작
        int share = permutationStr.Count / imitationNumber;     //예를 들어 24개를 6개씩 담으니 몫은 4임
        for(int i =0; i<permutationStr.Count; i++){
            if(tempPermutationStr.Count < share){
                tempPermutationStr.Add(permutationStr[i]);
            }

            if(tempPermutationStr.Count == share){        //list가 꽉차면 코루틴 실행 후 리셋. 예를 들어 몫이 4인데 4개가 담겼으면
                int GOarrayNum = i / share;     //총 24개이므로 0,1,2,3,4,5 이렇게 나올거임
                string[] newPermutationStr = new string[share]; //새로운 배열 생성
                tempPermutationStr.CopyTo(newPermutationStr);
                StartCoroutine(makePermuationForFaceAndDoAutomation(testParent, newPermutationStr, imitatedFigures[GOarrayNum]));
                tempPermutationStr.Clear(); 
                yield return new WaitForSeconds(0.2f);
            } 
        }  
    }

 

이제 순열 배열을 입력받은 코루틴에서 면을 하나씩 선택하며 특정 방향으로 선택된 면을 접기 시작하는데, 이러한 작동을 가장 기초적인 방법으로 나타내면 다음과 같이 표현할 수 있다.

 

 //i는 face를 순회하는 번호를 의미한다
            for(int a=0; a<3; a++){
                for(int b=0; b<3; b++){
                    for(int c=0; c<3; c++){
                        for(int d=0; d<3; d++){ 
                            for(int i=0; i< figureFaceCount_ExceptBottomFace; i++){  
                                figure.setCurrentFace( newFaces[i] );   
                                List<int> faceNum = new List<int>();      
                                faceNum.Add(d);
                                faceNum.Add(c);
                                faceNum.Add(b);
                                faceNum.Add(a); 
                                yield return StartCoroutine(figure.selectArrow(i, faceNum, 0.5f));

 

그리고 이러한 기초적 방법으로도 잘 작동하며, 열심히 일하며 가능한 모든 전개도를 찾는 모습은 다음과 같다.

 

 

그러나, 이 방법은 크게 두 가지 문제가 있었다.

첫째, 유지보수가 어렵다.

둘째, 불필요한 시행이 계속된다.

 

여기서 중요한 것은 불필요한 시행이라는 것인데, 상기 언급한 알고리즘에서는 그냥 무식하게 모든 경우를 다 검사하지만 실제 그럴 필요가 없다. 예를 들어, 두번째 면을 클릭했을 때나 세번째 면을 클릭했을 때, 그 면이 접힐 수 있는 방향은 4개가 아니라 1개 또는 2개일 수가 있는 것이다.

 

그래서, 나는 Node를 사용하기로 하고 코드를 수정하게 되었다. 효율성을 높이기 위한 방법으로, 일단 모든 경우의 수에 대한 node tree를 만들어 놓고, 면 x를 클릭했을 때 알게되는 불가능한 방향에 대한 정보를 바탕으로 해당 terminal node들을 삭제하는 방식을 사용하였다. 이를 통해 약 40%의 시행 횟수 감소를 가져올 수 있었다.

 

자세한건 다음에...