효율적인 큐브 행진 - 에지 계산의 3/4 시간을 줄일 수 있습니까?

Question

일반적인 행진 큐브는 큐브 당 12 개의 가장자리를 찾습니다. 그러나 큐브 당 3 개의 가장자리를 만들고 배열을 가장자리에 저장 한 다음 큐브를 다시 살펴보고 인접한 큐브의 가장자리를 계산하는 대신 참조하십시오.

인접한 큐브를 참조하는 프로세스가 인터넷에서 명확하게 논의되지 않아 행진 큐브를 사용하는 모든 사용자가 솔루션의 세부 정보를 찾는 데 도움이 될 것입니다. 이미 구현을 알고 있습니까? 그것은 단지 일부 있지만 여기

대신 12

난 그냥이 솔루션을 발견

편집 -, 당신은 각 큐브에 필요한 노란색의 세 모서리를 보여주는 사진입니다 :

낮은 관심 좌표를 가진 입방체 모서리에서 오는 3 개의 가장자리를 상상해보십시오. 다른 모든 모서리는 다른 큐브에 속합니다. 우리 큐브가 좌표 (x, y, z)를 가지면, 신경질 큐브는 ​​좌표 (x + 1, y, z), (x, y + 1, z), (x, y, z + 1), (x + 1, y, z + 1), (x, y + 1, z + 1) 가장자리를 벡터로 상상할 수 있습니다. 그런 다음 입방체 모서리에 모서리 (1,0,0), (0,1,0), (0,0,1)이 있습니다. 좌표 (x + 1, y, z)를 갖는 입방체는 큐브에 속하는 (0,1,0) 및 (0,0,1) 에지를 갖습니다. 큐브 (x + 1, y + 1, z)는 큐브에 속한 하나의 가장자리 (0,0,1) 만 갖습니다. 따라서 큐브에 대해 4 개의 요소를 저장하면 다음과 같이 액세스 할 수 있습니다.

edge1 = cube[x][y][z][0]; 
edge2 = cube[x][y][z][1]; 
edge3 = cube[x][y][z][2]; 
edge4 = cube[x+1][y][z][1]; 
edge5 = cube[x+1][y][z][2]; 
edge6 = cube[x][y+1][z][0]; 
edge7 = cube[x][y+1][z][2]; 
edge8 = cube[x][y][z+1][0]; 
edge9 = cube[x][y][z+1][1]; 
edge10 = cube[x+1][y+1][z][2]; 
edge11 = cube[x+1][y][z+1][1]; 
edge12 = cube[x][y+1][z+1][0]; 

이제는 edge7을 연결합니까? 답은 (x, y + 1, z)와 (x, y + 1, z) + (0,0,1) = (x, y + 1, z + 1)입니다.

이제 어떤 큐브 에지 7에 연결됩니까? 더 어렵습니다. 좌표 z는 모서리를 따라 변화하는 것을 보았습니다. 이것은 neibour 큐브가 같은 z 좌표를 가짐을 의미합니다. 이제는 다른 모든 사람들이 변화를 조정합니다. 우리가 +1을 가지고 있다면, 큐브는 큰 좌표를가집니다. 우리가 +0을 가지면 큐브의 좌표가 작아집니다. 그래서 가장자리는 큐브 (x, y, z)와 (x-1, y + 1, z)를 연결합니다. 같은 가장자리를 가진 다른 2 개의 큐브는 (x, y + 1, z)와 (x-1, y, z)입니다.

- = - = - = - = - = - = - = - = - = - = - = - = - = - = - = - = - = - = - = - =

EDIT2- 그래서 나는 이것을하고 있으며, 그렇게 간단하지 않습니다. 나는 동시에 8 점, 12 가장자리, 가장자리의 보간, 비트 값 및 꼭지점의 값을 하나의 루프로 계산하는 루프를 가지고 있습니다.

그래서 나는 가능한 한 많이 계산하고 복잡한 루프에서 사용하기 위해 배열에 배치하기 위해 이전에 새로운 루프를 만들고 있습니다.

나는 복잡한 루프에서 모든 포인트를 다시 계산해야하지만, 에지에서 교차점의 보간 된 값을 재사용 할 수 있습니다. 참조 할 비트 수를 결정할 때 사용한 점의 값 버텍스 테이블의 값. 그것은 나를 혼란스럽게한다! 일단 가장자리 교차 값을 얻으면 다시 점을 계산할 필요없이 직접 삼각형 표를 구할 수 있다고 생각했습니다!

사실 아니요. 어쨌든, 이미 읽을 수있는 사람이 있다면 이미 다른 사람과 정보를 공유하고 있습니다. http://www.new-npac.org/projects/sv2all/sv2/vtk/patented/vtkImageMarchingCubes.cxx 이 줄로 스크롤하십시오. 큐브는 최소면의 가장자리를 담당합니다.

Answer 1

재미있는 점은, 나 자신의 MC를 구현할 때도 비슷한 해결책을 찾았 기 때문입니다.

MC로 작업하기 시작할 때 고유 한 큐브로 처리하지만 높은 성능을 원한다면 전체 메시 전체를 생성해야하며 꼭지점 인덱스 등을 작성하는 것이 쉽지는 않습니다. 매끄러운 per-vertex 법선을 추가하고자 할 때 더욱 흥미 롭습니다.

이 문제를 해결하기 위해 각 가장자리의 꼭지점 인덱스를 저장하는 간단한 인덱스 캐시 메커니즘을 만들었습니다.

For each axis: 
    if the edge is on '+' side of axis: 
     replace edge index with its '-' side sibling 
     increment cube position along axis 

이 간단한 조작 내게 0,1 올바른 큐브 위치와 에지 인덱스를 제공한다 : 다음 그런 다음 각 계산 된 에지 I 큐브 위치 X, Y, Z 에지 인덱스가 나는 할 2. 그런 다음 간단한 비트 회전으로 x, y, z, edgeIndex 값에서 전체 캐시 인덱스를 계산합니다.

캐시 색인이있는 경우 -1보다 큰지 확인합니다. 그렇다면이 가장자리에 이미 계산 된 정점이 있으며 다시 사용할 수 있습니다. 만약 그것이라면 -1 나는 새로운 버텍스를 만들고 그 인덱스를 캐시에 저장할 필요가있다. 이렇게하면 각 꼭지점을 한 번만 계산할 수 있으며 꼭지점이 포함 된 모든 삼각형 사이에 공유되는 일반 값을 추가 할 수도 있습니다.

Answer 2

제안하는 방식으로 모서리 계산을 줄이는 간단한 방법은 한 번에 하나의 축으로 정렬 된 평면을 큐브로 계산하는 것입니다.

모서리가있는 모든 큐브를 메모리에 보관하면 각 모서리를 한 번만 계산하고 인덱싱을 통해 인접한 모서리를 쉽게 찾을 수 있습니다. 그러나 일반적으로 공간 요구 사항 때문에 모든 큐브를 한 번에 메모리에 보관하지 않으려합니다.

이 문제에 대한 해결책은 한 번에 하나의 큐브 평면을 계산하는 것입니다. 즉 일 측면으로부터 시작하여 대향 측면으로 진행하는 축 정렬 된 단면을 갖는다. 그런 다음 한 번에 최대 2 개의 큐브 전체 평면을 메모리에 유지하면됩니다. 각 평면을 이동하면서 이전 평면의 공유 에지와 현재 평면의 이전에 계산 된 큐브를 참조 할 수 있습니다. 다음 비행기로 이동할 때 더 이상 필요하지 않은 비행기의 할당을 해제 할 수 있습니다.

편집 :이 문서에는 내가 제안 무엇 단지 일을 설명합니다은 : http://alphanew.net/index.php?section=articles&site=marchoptim&lang=eng