3D 큐브 그리드가있는 경우 반경 r 및 위치 p의 구와 교차하는 모든 큐브를 어떻게 효율적으로 찾을 수 있습니까?

좌표계와 알고리즘을 작업하는 데 여전히 문제가있는 경우 다이어그램으로 시작하십시오.

본질적으로 당신이 가진 것은 큐브의 3D 그리드이며 당신의 포인트 p는 큐브를 완전히 설명하는 한 당신이 좋아하는 방식으로 선택할 수 있습니다. 결정하려는 것은 반경 r이 큐브의 일부와 교차하는 큐브에 대한 것입니다. 세 개의 벡터로 처리 할 수 ​​있습니다. 큐브 원점을 벡터로 취급하기 만하면됩니다. 큐브 에서 가장 먼 지점을 결정하기 위해 원점 벡터에 추가 할 수 d / n있는 두 번째 벡터 ( p또는 범위라고 함)를 형성하는 데 사용할 수있는 각 큐브 ( ) 의 측면 길이를 알고 p_extent있습니다. 그래서 p_extent같을 것이다 d/n된 I + d/nJ의 +의 d/n케이 .

좌표를 벡터로 처리하는 데 도움이되는 구조체를 만들 수 있습니다. 예 :

typedef struct {
    double x, y, z;
} vect_pos;

두 벡터를 사용하여 간단히 더하기 (예 : p+ p_extent)하여 원점에서 큐브의 가장 먼 점을 설명하는 벡터를 형성 할 수 있습니다 . (입방체 내부의 벡터 방향이 원점 벡터와 동일한 부호 방향을 갖기를 원합니다 (그러므로 해당 방향의 단위 벡터로 간단히 곱할 수 있습니다). 예를 들어 점이 -3i -1j 및 2k입니다 . i j k를p_extent 벡터로 곱합니다 . ( 각 8 사분면 의 입방체 원점 벡터와 각 사분면에있는 값을 상상해보십시오 .-1 -1 1x, y, z

두 개를 더하려면 vector_pos간단히 벡터 더하기를 사용할 수 있습니다.

/* vector addition */
vect_pos vect_add (const vect_pos *a, const vect_pos *b)
{
    vect_pos c = { .x = 0. };
    
    c.x = a->x + b->x;
    c.y = a->y + b->y;
    c.z = a->z + b->z;
    
    return c;
}

큐브의 모서리에서 좌표를 선택해야하는 마지막 주름은 원점 벡터가 항상 원점에 가장 가까운 모서리를 가리 키지 않는다는 것입니다 (위 다이어그램의 그림에서 p원점을 시계 반대 방향으로 회전하면 가리키는 위치). 축을 기준으로 90도만큼. (대안은 큐브의 중심을 원점으로 선택하는 것이지만 계산 횟수가 두 배가됩니다).

가장 가까운 모서리 문제는 간단한 확인과 r가장 가까운 모서리와 가장 먼 모서리 사이 에 있는지 여부를 계산하기 위해 원점의 모서리를 큐브 측면 길이만큼 이동하여 처리 할 수 ​​있습니다 (큐브는 여전히 동일한 큐브 임) 큐브 원점으로 설명 된 가장 먼 모서리에서 벡터 거리 공식을 사용하여 각각 원점으로부터의 거리를 계산할 수 r있으며 둘 사이에 있으면 구가 해당 큐브와 교차합니다.

거리를 계산하기 전에 원점에 가장 가까운 점을 선택하려면 다음을 사용할 수 있습니다.

/* point in cube closest to origin */
vect_pos closest_pt (const vect_pos *p, const int len)
{
    vect_pos c = {  p->x >= 0 ? p->x : p->x + len,
                    p->y >= 0 ? p->y : p->y + len,
                    p->z >= 0 ? p->z : p->z + len  };
    
    return c;
}

( 0, 0, 0양의면이 있는 원점 에서 큐브를 선택하면 좌표가 음수 인 경우 큐브의 측면 길이를 추가하여 큐브에서 가장 가까운 점을 원점으로 선택하기 만하면됩니다)

거리 계산의 경우 제곱합의 단순 제곱근 :

/* vector distance */
double vect_dist (const vect_pos *p)
{
    return sqrt (p->x * p->x + p->y * p->y + p->z * p->z);
}

있는지 확인하려면 r각 큐브 내에서 가장 가깝고 먼 거리 사이의 폭포는 당신이 핸들 원점으로 같은 방향으로 어느 정도 벡터를 선택하는 간단한 기능을 모두 넣을 수, 벡터를 추가하고 각의 거리를 비교 r, 예를

/* does r intersect cube at postition p */
int intersect (vect_pos *p, const double r, const int len)
{
    vect_pos c = closest_pt (p, len),                   /* closest pt to origin */
            p_extent = { .x = c.x >= 0 ? len : -len,    /* length, unit vector */
                         .y = c.y >= 0 ? len : -len,    /* pointing outward */
                         .z = c.z >= 0 ? len : -len },
             p_farthest = vect_add (&c, &p_extent);     /* farthest point in cube */
    double   nearest  = vect_dist (&c),                 /* distance to nearest */
             farthest = vect_dist (&p_farthest);        /* distance to farthest */
    
    return nearest <= r && r <= farthest;               /* return radius in between */
}

그게 기본입니다. 편의상 포인트를 출력하는 짧은 기능을 추가 할 수 있습니다.

void prn_pos (const vect_pos *p)
{
    printf ("(% d, % d, % d)\n",
            (int)p->x, (int)p->y, (int)p->z);
}

다음, 추가 main()의 입력을 허용하는 r, d그리고 n그 결과를 출력한다 :

int main (int argc, char **argv) {
    
    double  r = argc > 1 ? strtod (argv[1], NULL) : .9;     /* r */
    int     d = argc > 2 ? strtol (argv[2], NULL, 0) : 1,   /* d */
            n = argc > 3 ? strtol (argv[3], NULL, 0) : d,   /* n */
            dn = 0,             /* d/n */
            nc = 0,             /* number of cubes in each direction */
            total = 0,          /* total cubes in search grid */
            intersecting = 0;   /* number of cubes that intersect sphere */
    
    if (r < 0 || d < 0) {   /* validate length inputs */
        fputs ("error: negtive length in input of r or d.\n", stderr);
        return 1;
    }
    if (!n || n < 0) {      /* validate n not zero or negative */
        fputs ("error: n - divide by zero or negative.\n", stderr);
        return 1;
    }
    if (d < r) {            /* ensure d >= r */
        int min_d = ceil (r);
        n *= min_d / d;
        d = min_d;
    }
    if (d % n) {            /* validate d equally divisible by n */
        fputs ("error: d not equally divisible by n.\n", stderr);
        return 1;
    }
    
    dn = d / n;                     /* cube side length */
    nc = ceil (r / dn) + 1;         /* limit of cubes needed per-direction */
    total = nc * nc * nc * 8;       /* total number of cubes in search grid */
    
    printf ("\nOut of %d cubes, the following intersect sphere of radius %.2f\n\n",
            total, r);
    
    for (int i = -d; i <= d; i += dn)               /* loop -d to d */
        for (int j = -d; j <= d; j += dn)
            for (int k = -d; k <= d; k += dn) {
                vect_pos p = { i, j, k };           /* vector to cube origin */
                if (intersect (&p, r, dn)) {        /* does it intersect sphere? */
                    prn_pos (&p);                   /* output cube origin */
                    intersecting++;                 /* increment count */
                }
            }
    
    printf ("\nintersecting cubes: %d\n", intersecting);
}

헤더 추가 :

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

그런 다음 수학 라이브러리에 대한 링크를 컴파일 -lm하면 테스트 할 작업 프로그램이 있습니다. 에 대한 인수하는 경우 r, d또는이 n코드가 사용이 제공되지 않습니다 .90, 1및 1기본값으로. 루프 제한은 각 차원 에서 최소 -(next int above r)~ ~ (next int above r)또는 d보다 크거나 짧지 않은 값 으로 지정됩니다 r.

사용 / 출력 예시

r = .9and d = 1와 함께 기본 케이스 n = 1:

$ ./bin/cube-sphere-intersect

Out of 64 cubes, the following intersect sphere of radius 0.90

(-1, -1, -1)
(-1, -1,  0)
(-1,  0, -1)
(-1,  0,  0)
( 0, -1, -1)
( 0, -1,  0)
( 0,  0, -1)
( 0,  0,  0)

intersecting cubes: 8

그리드에 큐브를 그리면 원점을 둘러싼 8 개의 큐브입니다.

선택 r = 5.5, d = 6그리고 n = 1다른 길이되는 큐브의 측면 이외의 동일한 결과를 줄 것이다 :

$ ./bin/cube-sphere-intersect 5.5 6 1

Out of 64 cubes, the following intersect sphere of radius 5.50

(-6, -6, -6)
(-6, -6,  0)
(-6,  0, -6)
(-6,  0,  0)
( 0, -6, -6)
( 0, -6,  0)
( 0,  0, -6)
( 0,  0,  0)

intersecting cubes: 8

r길이를 exacly로 입력하면 1여기 r에서 최소 또는 최대 길이와 같은 것으로 간주할지 여부를 선택할 수 있습니다. 큐브 정말이 점으로 거리를 알아,하지만 말을 동등하게 좋은 인수가 있음을 접선에 거짓말을 기술적으로합니다 교차 의미하지 않는다 "감동"말의 인수가 있습니다 그 교차 (사용할지 여부의 선택 <=또는 <비교에서 당신에게 맡겨져 있습니다)

예를 들어 1.0 < sqrt(2)( 1.414...) 사이에 입력 하면 32 개의 큐브가 교차합니다.

$ ./bin/cube-sphere-intersect 1.1

Out of 216 cubes, the following intersect sphere of radius 1.10

(-2, -1, -1)
(-2, -1,  0)
(-2,  0, -1)
(-2,  0,  0)
(-1, -2, -1)
(-1, -2,  0)
(-1, -1, -2)
(-1, -1, -1)
(-1, -1,  0)
(-1, -1,  1)
(-1,  0, -2)
(-1,  0, -1)
(-1,  0,  0)
(-1,  0,  1)
(-1,  1, -1)
(-1,  1,  0)
( 0, -2, -1)
( 0, -2,  0)
( 0, -1, -2)
( 0, -1, -1)
( 0, -1,  0)
( 0, -1,  1)
( 0,  0, -2)
( 0,  0, -1)
( 0,  0,  0)
( 0,  0,  1)
( 0,  1, -1)
( 0,  1,  0)
( 1, -1, -1)
( 1, -1,  0)
( 1,  0, -1)
( 1,  0,  0)

intersecting cubes: 32

그런 다음 반경에 sqrt(2) <= sqrt(3)대해 56 큐브 교차 등을 찾을 수 있습니다.

이것은 그것을 구현하는 한 가지 방법 일뿐입니다. 궁금하다면 각 큐브의 중심을 큐브의 원점으로 사용하도록 다시 작성하십시오. 구조체를 사용할 필요가 없으며 각각에 대해 x, y, z직접 작업 할 수 있지만 구조체는 논리를 명확하게 유지하는 데 도움이됩니다. 자세히 살펴보고 추가 질문이 있으면 알려주세요.