구의 표면에 점들을 균등하게 분포시키는 방법 (Three.js)

구면 상에 점들을 고르게 분포시키는 문제는 기하학에서 고전적인 문제 중 하나이며, 컴퓨터 그래픽, 분자 모델링, 물리학 등 다양한 분야에서 활용됩니다.

실용적으로 가장 적절한 방법 중 하나는 "Fibonacci Sphere"를 사용하는 것입니다. 이 방법은 피보나치 나선형 구를 기반으로 하여 구의 표면에 점들을 나선형 패턴으로 배치합니다. 각 나선층마다 포인트 수가 피보나치 수열에 따라 증가하여, 결과적으로 점들이 대략 고르게 분포하게 됩니다.

다른 방법으로 "Geodesic Sphere (측지식 구)"를 사용할 수 있는 데, 측지선의 개념에 기반하여 점들을 구에 분배합니다. 측지식 구는 일정한 점의 수를 제어할 수 있지만, 분포가 고르지 않을 수 있으며, 피보나치 구처럼 조절성이 좋지 않습니다.

또 다른 방법으로는 "Equivalent Angle Sphere(등각 거리 구)"가 있습니다. 이 방법은 정확하게 고르게 각도를 나눠줌으로써 극 지방 밀집 문제를 피할 수 있습니다. 그러나 원주를 각도로 나누는 방식의 특성상 점의 개수 조절이 불가능합니다.

한 가지 주목할 점은, 특정한 개수의 점에 대해 구면 상에서 정확하게 고르게 분포하는 점을 찾는 것은 수학적으로 불가능할 수 있습니다. 예를 들어, 수학자 오일러가 증명한 것처럼, 구면 상에서 5개의 점을 정확하게 고르게 배치하는 것은 불가능합니다. 그러나 위에서 언급한 방법을 사용하면 대략적으로 고르게 분포하는 것은 가능합니다.

아래 예시에서는 피보나치 구, 측지식 구, 등각 거리 구의 실시간 테스트 샘플을 보여줍니다.

고려해야 할 사항

구면 상에 점을 분배하는 방법을 선택할 때 고려해야 할 다양한 요소가 있는 데, 다음은 주요 고려 사항의 개략적인 요약입니다.

• 점 분포 품질: 각각의 방법들은 점 분포에서 균일성 수준이 다릅니다. 점들이 더 고르게 분포되어야 하는지, 더 구조적이고 격자 모양의 분포가 적합한지 고려해야 합니다.
• 점의 개수 제어성: 알고리즘에서 생성되는 점의 개수를 제어할 수 있는 능력은 응용 프로그램 별로 중요도가 다를 수 있습니다. 원하는 점의 개수를 지정할 수 있는 방법을 선택하거나, 요구 사항에 기반하여 적절한 수준의 제어 기능을 제공하는 방법을 선택해야 합니다.
• 극점 밀집성: 측지식 구와 같은 일부 방법들은, 극 주변에서 점들이 서로 모여지는 극점 밀집 현상이 발생합니다. 이러한 균일하지 않은 분포는 텍스처 매핑, 데이터 샘플링 또는 계산 시뮬레이션과 같은 특정 응용 분야에서 시각적인 불균형 및 정확성 문제를 초래할 수 있습니다.
• 계산 효율성: 알고리즘의 복잡성 및 점 생성에 필요한 시간은 성능에 영향을 미칠 수 있습니다. 프로젝트의 요구 사항에 따라 알고리즘의 효율성이 분배 품질보다 더 중요한지 고려해야 합니다.
• 구현의 용이성: 일부 방법은 다른 방법보다 구현이 더 쉽습니다. 방법의 복잡성 및 외부 라이브러리 또는 도구에 대한 의존성을 고려해야 합니다.

이러한 요소들과 함께 프로젝트의 특정 요구 사항에 따른 고려 사항을 포함하면 구면 상에 점을 분배하는 적절한 방법을 선택할 수 있습니다. 각 방법은 장단점이 있으므로, 프로젝트의 고유한 요구 사항과 목표에 따라 선택하는 것이 좋습니다.

점 좌표를 방향 (법선) 벡터로 사용하기

점을 균일하게 분포시키는 것의 중요한 활용 사례 중 하나는 점을 구의 중심으로부터 뻗어 나오는 법선 벡터로 사용하는 것입니다. 이러한 활용 방식은 특히 컴퓨터 그래픽, 렌더링 및 기하학적 처리 분야에서 많이 사용됩니다. 이러한 법선 벡터를 사용하는 몇 가지 예시는 다음과 같습니다.

• 파티클 시스템: 시뮬레이션 및 파티클 시스템에서, 균일하게 분포된 점은 구의 표면에서 방출되는 입자의 초기 방향으로 사용될 수 있습니다. 이를 통해 폭발 또는 유체 시뮬레이션과 같은 더 현실적인 입자 효과를 만들 수 있습니다.
• 빛 또는 음파 파동 방출: 광선 추적 또는 글로벌 조명 효과 같은 빛 파동 방출과 오디오 시뮬레이션 또는 음향 모델링과 같은 음파 파동 방출을 포함하는 응용 프로그램에서, 구면 상에 균일하게 분포된 점을 사용하여 파동의 방향을 나타낼 수 있습니다. 이를 통해 파동이 어떻게 전파되고 환경과 상호작용하는지 더 정확하게 시뮬레이션할 수 있습니다.
• 조명 효과: 컴퓨터 그래픽에서, 표면 법선은 3D 개체의 조명 및 음영을 계산하는 데 중요합니다. 균일하게 분포된 점을 법선으로 사용하면 다양한 조명 조건에서 개체의 모습을 보다 정확하게 나타낼 수 있습니다.
• 환경 매핑: 반사 매핑과 같은 환경 매핑에서, 표면 법선은 3D 개체에서 환경이 반사되는 방식을 결정하는 데 사용됩니다. 이 경우에 균일하게 분포된 점의 법선들은 환경의 반사를 더 정확하게 나타낼 수 있습니다.
• Spherical Harmonics: 구형 고조파(高調波)는 글로벌 조명, 앰비언트 오클루전 및 환경 매핑의 압축과 같이 컴퓨터 그래픽에서 다양한 목적으로 사용됩니다. 구면 상에 균일하게 분포된 점은 구면 하모닉스와 함께 사용하여 더 정확한 표현을 제공할 수 있습니다.
• 세분화 및 변위 매핑: 3D 모델의 지오메트리를 세분화(Tessellation)하거나 변위(Displacement)시킬 때, 균일하게 분포된 법선을 사용하면 원래 표면으로부터 더 균일하고 정확하게 변환하는 데 도움이 됩니다. 

이러한 경우, 피보나치 나선 구와 같이 균일하게 분포된 점을 생성하는 알고리즘이 특히 유용할 수 있습니다. 이는 구의 표면에서 더 균일한 점 분포를 제공하여 점 군집화 또는 밀집화로 인해 발생하는 문제를 최소화하고 위에서 언급한 응용 프로그램에서 더 정확한 결과를 제공합니다.

1. Fibonacci Spiral Sphere

피보나치 나선 구 알고리즘은 황금 비율과 관련된 황금 각도 개념을 활용하여 점을 균일하게 분포시키는 것으로 구의 표면 에서 균일한 점 분포를 제공합니다. 피보나치 나선 구는 점을 피보나치 나선 패턴으로 구면 위에 분포시키는 패턴으로 구면 상에서 균일하게 분포된 점을 생성하는 데 흔히 사용됩니다.

아래의 코드는 fibonacci_spiral_sphere 함수를 정의하며 인자 num_points를 사용하여 구의 점의 수를 결정합니다. 이 계산 함수는 황금 각도 개념을 사용하여 각 점의 위치를 계산하고 3D 공간의 점 배열을 반환합니다

const cos = Math.cos, sin = Math.sin, asin = Math.asin, sqrt = Math.sqrt;
const M_PI = Math.PI;
function fibonacci_spiral_sphere(num_points) {
    const goldenRatio = (sqrt(5.0) + 1.0) / 2.0;                // golden ratio = 1.6180339887498948482
    const goldenAngle = (2.0 - goldenRatio) * (2.0 * M_PI);     // golden angle = 2.39996322972865332
    let points = [];
    let lat, lon;
    let x, y, z;
    for (let i=1; i <= num_points; ++i) {
        lat = asin(-1.0 + 2.0 * (i / (num_points+1)));
        lon = goldenAngle * i;
        x = cos(lon)*cos(lat);
        y = sin(lon)*cos(lat);
        z = sin(lat);
        points.push(x, y, z);
    }
    return points;
}

여기서 알고리즘의 분포 품질은 지정한 점의 갯수에 따라 달라집니다. 점의 수가 증가할수록 분포는 더 균일해집니다. 이 알고리즘은 구면 상의 점을 생성하는 데 점의 갯수만으로 제어할 수 있어 간단하고 효율적입니다. 

더 구체적인 수학적 정보는 다음 링크에서 확인할 수 있습니다:

https://observablehq.com/@meetamit/fibonacci-lattices

Fibonacci Lattices

2. Geodesic Sphere

지오데식 구는 곡면 상에서 두 점 사이의 최단 경로인 측지선의 개념을 기반으로 구면 상의 점을 분포시키는 다른 방법입니다. 지오데식 구에서는 지오데식 선의 네트워크를 사용하여 구의 다면체 근사형을 만들고, 결과적인 다면체의 꼭지점을 구의 표면으로 투영하여 대략 균일하게 분포된 점 집합을 얻을 수 있습니다.
지오데식 구의 점의 수는 초기 다면체의 세분화 빈도에 따라 달라지기 때문에, 어느 정도 제어 가능 한 측면이 있습니다. 그러나 생성된 분포가 완전히 균일하지 않을 수 있고, 일부 응용 프로그램에 대해 최적인 점의 수가 아닐 수 있습니다.

지오데식 구는 지오데식 돔의 설계 및 3D 모델링에서 곡면의 근사에 사용되는 등 컴퓨터 그래픽 및 공학 분야에서 많이 사용됩니다. 지리 공간 분석을 위해 지구 표면에 점을 분포시키는 데에도 사용됩니다. 지오데식 구는 점의 수가 비교적 적은 근사 구를 만드는 데에 효과적인 방법입니다. 

앞서 언급한 피보나치 나선 구 알고리즘은 구의 표면에 더 균일하게 분포된 점 집합을 제공하는 대안적인 방법입니다. 황금 각도를 사용하여 알고리즘이 점 간의 반발력을 최소화하므로 구의 표면에 더 균일한 분포를 제공합니다. 이는 점의 균등 분포가 우선적인 경우 더 나은 선택입니다.

더 자세한 정보는 다음 링크에서 참조할 수 있습니다:

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

Geodesic polyhedron - Wikipedia

3. 동일 각도 거리의 구

구면 상의 점을 분포시키는 또 다른 방법은 각도 거리가 동일한 구입니다. 이 방법은 수평 원을 수직 각도로 계산한 각도 거리로 나누어 구현합니다.이 방법은 구를 동일한 위도와 경도 각도로 분할하여 점을 분포시키는 방식의 변형입니다. 이 방법에서 구는 수직 각도 증분에 따라 분리된 각도가 동일한 수평 원으로 분할됩니다. 그런 다음 각 수평 원의 점은 계산된 수직 분리 각도를 기반으로 동일한 각도 거리로 분배됩니다.

function equivalent_distribution_sphere(angleDegree) {
    const angle = THREE.Math.degToRad(angleDegree);
    let lat, lon;
    let x, y, z;
    let vertices = [];
    let up_indices = [];
    let dn_indices = [];
    let indices = [];
    let index = 0;
    let num_vert_points = M_PI / angle;
    for (let v = 0; v < num_vert_points+1; ++v) {
        lat = (M_PI * 0.5) - (v * angle);    // 90 ~ 0 ~ -90
        let radius = cos(lat);
        let height = sin(lat);
        let num_horz_points = Math.floor((2.0 * M_PI * radius) / angle);
        dn_indices = [];
        if (num_horz_points > 0) {
            let angle_step = (M_PI * 2.0) / num_horz_points;
            for (let h = 0; h < num_horz_points; ++h) {
                lon = h * angle_step;
                x = sin(lon) * radius;
                z = cos(lon) * radius;
                y = height;
                vertices.push(x, y, z);
                dn_indices.push(index++);
            }
        } else {
            vertices.push(0, height, 0);
            dn_indices.push(index++);
        }
        // compute triangle face indices
        if (up_indices.length > 0) {
            let up_count = up_indices.length;
            let dn_count = dn_indices.length;
            let total_count = up_count * dn_count;
            let up_step = up_count / total_count;
            let dn_step = dn_count / total_count;
            let u0 = 0, u1 = 0;
            let d0 = 0, d1 = 0;
            for (let i = 1; i < total_count+1; ++i) { // total_count+1
                if ((d1 = (i*dn_step)) % 1 === 0) { // is integer index
                    d1 = d1 % dn_count;
                    indices.push(up_indices[u0], dn_indices[d0], dn_indices[d1]);
                    d0 = d1;
                }
                if ((u1 = (i*up_step)) % 1 === 0) { // is integer index
                    u1 = u1 % up_count;
                    indices.push(up_indices[u0], dn_indices[d0], up_indices[u1]);
                    u0 = u1;
                }
            }
        }
        up_indices = dn_indices;
    }
    return { vertices, indices };
}

결론

전반적으로, Fibonacci 나선 구 방법은 구의 표면에 균일하게 분포된 점 집합을 생성하는 가장 널리 사용되고 효율적인 방법입니다. 이 방법은 점 클러스터링이나 고조밀도 부분에서 발생하는 문제를 최소화하고 데이터 샘플링이나 텍스처 매핑 등 다양한 응용 분야에서 보다 정확한 결과를 보장하기 위해 구의 표면에 더 균일하게 점을 분포시킵니다. 반면에, 지오데식 구나 각도 거리가 동일한 구 방법은 각각 다른 장단점을 가지고 있으며 서로 다른 응용 분야에 적합합니다. 그러나 지오데식 구 방법은 점의 수를 제어하기 어렵고, 각도 거리가 동일한 구 방법은 총 점 수를 제어할 수 없지만 정확한 균일 각 거리를 제공합니다.

최종적으로, 이런 구현 방법의 선택은 프로젝트의 특정 요구 사항과 목표에 따라 다릅니다. 따라서 모든 요소를 고려하고 다양한 알고리즘을 평가하여 최상의 솔루션을 찾아야 합니다.