정점이 매쉬 안에 존재하는지 판단하는 방법

포인트 클라우드를 다루거나 각종 3D 시뮬레이션을 만들다 보면 정점이 매쉬 안에 존재하는지 판단해야 할 때가 있다.

이번 글에서 이 문제를 해결하는 방법을 알아보자

 

다각형 안의 정점 판별

어떤 정점이 다각형 안에 존재하는지 판단하는 방법은 여러 가지가 있다. 가장 유명한 방법 중 하나는 barycentric coordinates를 이용하는 것이다.

 

간단히 설명하자면, 아래 그림 1처럼 삼각형 ABC의 정점 3개를 이용해 새로운 좌표계(원점 A, 기저1 A->B, 기저2 A->C)를 만들어서 정점이 삼각형 안에 존재하는지 판별하는 것이다.

 

[그림 1] barycentric coordinates

 

만약 정점 P가 삼각형 바깥에 있다면 그림 1의 초록색 벡터가 기저벡터에 대해서 0보다 작거나 1보다 크게될 것이다. 아래 그림 2는 정점 P가 삼각형 바깥에 있을 때의 모습이다.

 

[그림 2] 정점이 삼각형 바깥에 있을 때

 

그림 2의 초록색 벡터를 보면, basis2에 대해서 반대 방향 벡터가 있음을 알 수 있다. 이처럼 barycentric coordinates를 이용할 때 정점이 삼각형 안에 존재하려면, basis1, basis2에 대해서 정점 P의 좌표가 (0 < P.x < 1, 0 < P.y < 1) 이어야 한다.

 

Ear Clipping Method 등의 알고리즘을 통해 아래 그림 3처럼 다각형을 삼각 분할 후, 각각의 삼각형에 대해 위에서 설명한 방법을 사용할 수 있다.

 

[그림 3] 삼각분할한 다각형

 

이 방법으로도 다각형 안에 정점이 존재하는지 판별할 수 있지만, 다각형을 삼각 분할 해야 하고 각각의 삼각형에 대해 계산을 해야 하므로 비효율적이다.

 

다른 방법은 광선 추적을 이용하는 것이다. 이 방법은 barycentric coordinates를 이용하는 것보다 훨씬 간단하다. 기본 아이디어를 설명하자면 아래와 같다.

 

• 정점 P에 대해서 임의의 방향으로 광선을 발사한다.
• 광선이 다각형 표면에 부딪힌 횟수가 짝수면 바깥, 홀수면 안쪽에 정점이 존재하는 것이다.

이 아이디어를 그림으로 표현하면 아래 그림 4와 같다.

 

[그림 4] 광선 추적

 

이 방법을 사용한다면 2D의 경우 직선 교차 방정식을 이용하여 교차된 횟수를 구하기만 하면, 정점이 다각형 내부에 있는지 외부에 있는지 판단할 수 있다.

 

3D 모델 안의 정점 판별

3D 모델 안에 어떤 정점이 존재하는지 판단하는 방법도 위에서 설명한 방법을 이용하면 간단하다. 3D 모델이 닫힌 도형인 것만 보장되면, 어떤 방향으로 자르든 닫힌 다각형이 나오기 때문이다. 아래 그림 5가 이를 보여준다.

 

[그림 5] 닫힌 3D 도형을 잘랐을 때

 

위 그림 5처럼 닫힌 도형을 자르면 닫힌 다각형이 나오기 때문에, 3D에서도 마찬가지로 광선 추적을 이용하여 어떤 정점이 3D 모델 안에 존재하는지 판단할 수 있다.

 

Unity 3D Mesh 안의 정점 판별

정점이 3D Mesh 안에 존재하는지 판별하는 것은 Unity의 Raycast를 이용하면 쉽게 판단할 수 있다. 위에서 설명한 것처럼 3D Mesh가 닫힌 도형이라면, 2D에서 다각형 안의 정점을 판별하는 방법을 그대로 사용하면 되기 때문이다.

 

아래 코드는 재귀적으로 광선 충돌 횟수를 검사하여 위치가 Mesh 바깥에 있는지 안에 있는지 검사하는 메서드이다.

private bool IsPosInside()
{
    // 현재 위치부터 광선 추적을 시작한다.
    Ray ray = new Ray(this.transform.position, Vector3.up);
    RaycastHit hit;
    int count = 0;

    // 재귀적으로 충돌 횟수를 계산한다.
    while (Physics.Raycast(ray, out hit, float.MaxValue))
    {
        ray.origin = hit.point + ray.direction * 0.01f;
        count++;
    }

    // 충돌 횟수가 짝수면 밖, 홀수면 안에 정점 존재
    if (count % 2 == 0)
        return false;
    else
        return true;
}

 

위의 코드만으로 검사는 완료되지만, 검사 전에 해결해야 할 문제가 있다. Mesh 표면의 노멀 벡터는 모두 바깥쪽을 향하고 있기 때문에, 아래 그림 6처럼 Mesh 안에서 바깥으로 광선이 나갈 때의 충돌이 처리되지 않는 문제가 있다.

 

[그림 6] Mesh 안에서 광선 추적

 

이를 해결하기 위해선 원본 Mesh와 노말벡터가 반대 방향인 Mesh(back-face mesh)를 만들어줘야 이 문제가 해결된다. 아래 코드는 back-face Mesh 및 GameObject 객체를 생성해주는 코드이다.

private void MakeBackFaceObj(GameObject gameObject)
{
    MeshFilter meshFilter = gameObject.GetComponent<MeshFilter>();
    MeshRenderer meshRenderer = gameObject.GetComponent<MeshRenderer>();

    // 원본 Mesh 획득
    Mesh mesh = meshFilter.mesh;
    
    // 안쪽 방향의 Mesh 생성
    Mesh backFaceMesh = Instantiate(mesh);
    backFaceMesh.triangles = backFaceMesh.triangles.Reverse().ToArray();

    // 안쪽 방향의 Mesh를 가지고 있는 GameObject 객체 생성
    GameObject backFaceMeshObj = MakeGameObjectWithMesh(backFaceMesh, meshRenderer.materials);
    backFaceMeshObj.name = gameObject.gameObject.name + "-Backface";
    backFaceMeshObj.tag = gameObject.gameObject.tag;
    backFaceMeshObj.layer = gameObject.gameObject.layer;
    backFaceMeshObj.transform.position = gameObject.transform.position;
    backFaceMeshObj.transform.localScale = gameObject.transform.localScale;
    backFaceMeshObj.transform.rotation = gameObject.transform.rotation;
}

 

테스트

위 알고리즘이 제대로 동작하는지 확인하는 간단한 테스트 프로젝트를 작성하였다.

 

https://github.com/YoonChangKook/UnityCameraInsideMeshesTest

YoonChangKook/UnityCameraInsideMeshesTest

 

아래 그림 7, 8처럼 Scene에 여러 가지 오브젝트를 배치하고, 플레이어의 1인칭 카메라의 위치가 도형 안에 존재하는지 화면 좌측 상단에 표시해주는 프로그램이다.

 

[그림 7] 테스트 프로젝트 화면

[그림 8] 카메라가 도형 안에 존재할 때의 화면

 

카메라의 조작 방법은 레포지토리 README.md에 적어놓았으니 참고하길 바란다.

 

참고

Determine whether 2d point is within a polygon

https://stackoverflow.com/questions/217578/how-can-i-determine-whether-a-2d-point-is-within-a-polygon?fbclid=IwAR30jc6qr3xtmMIBYcC0Exv64AknHWvCcYNcZEX2BcnwmZ-LisGMOQa_Vgc

How can I determine whether a 2D Point is within a Polygon?

 

Polygon Triangulation

https://en.wikipedia.org/wiki/Polygon_triangulation

Polygon triangulation - Wikipedia

 

Barycentric Coordinates

http://www.alecjacobson.com/weblog/?p=1596

Barycentric coordinates and point-triangle queries « Alec's Web Log