CPU 기반 매핑(Voxblox, OctoMap)의 한계와 병목 현상

현대 로봇 공학에서 3차원 환경을 정밀하게 인지하고 재구성하는 기술은 자율 주행 차량, 무인 항공기(UAV), 그리고 실내 서비스 로봇의 자율성을 결정짓는 가장 핵심적인 요소이다. 로봇이 미지의 환경에서 안전하게 경로를 계획하고 임무를 수행하기 위해서는 센서로부터 획득된 원시 데이터(Raw Data)를 의미 있는 공간 정보로 변환하는 ‘매핑(Mapping)’ 과정이 필수적이다. 지난 수십 년간 이 분야는 CPU(Central Processing Unit)의 연산 능력을 기반으로 발전해 왔으며, 특히 확률적 점유 그리드(Probabilistic Occupancy Grid) 방식을 채택한 OctoMap과 절단된 부호 거리 장(TSDF: Truncated Signed Distance Field)을 활용하는 Voxblox는 학계와 산업계에서 사실상의 표준(De facto standard)으로 자리 잡아 왔다.1

그러나 최근 라이다(LiDAR) 및 RGB-D 카메라와 같은 3차원 센서 기술이 급격히 발전하여 데이터의 해상도와 수집 빈도가 폭발적으로 증가함에 따라, 기존의 CPU 기반 매핑 프레임워크는 심각한 구조적 한계와 성능 병목(Bottleneck)에 직면하게 되었다. CPU는 복잡한 논리 연산과 제어 흐름(Control Flow) 처리에 최적화된 직렬 처리(Serial Processing) 아키텍처를 가지고 있어, 수백만 개의 데이터 포인트를 동시에 처리해야 하는 대규모 병렬 성격의 매핑 연산을 감당하기에는 근본적인 하드웨어적 불일치가 존재한다.3 본 절에서는 CPU 기반의 대표적인 매핑 시스템인 OctoMap과 Voxblox가 겪고 있는 알고리즘적 한계, 메모리 계층에서의 비효율성, 그리고 이것이 전체 로봇 시스템의 실시간성에 미치는 파급 효과를 심층적으로 분석한다.

1. 레이 캐스팅(Ray-Casting)의 연산 복잡도와 직렬 처리의 한계

CPU 기반 매핑 시스템의 성능을 저하시키는 가장 일차적이고 지배적인 병목 구간은 센서 데이터를 지도 데이터 구조에 통합(Integration)하는 단계, 그중에서도 레이 캐스팅(Ray-Casting) 또는 레이 슈팅(Ray-Shooting)이라 불리는 기하학적 연산 과정이다.1

1.1 레이 캐스팅 알고리즘의 본질적 비용

확률적 볼륨 매핑(PVM: Probabilistic Volumetric Mapping)에서 센서 관측 모델은 센서의 원점(Origin)에서 측정된 물체 표면의 점(Endpoint)까지를 잇는 하나의 광선(Ray)으로 표현된다. 매핑 알고리즘은 이 광선이 통과하는 공간상의 모든 복셀(Voxel)을 추적(Tracing)하여, 광선 경로상에 있는 복셀은 ’비어 있음(Free)’으로, 끝점에 위치한 복셀은 ’점유됨(Occupied)’으로 상태 확률을 갱신해야 한다.

이 과정은 수학적으로 브레즌햄(Bresenham) 알고리즘이나 3DDDA(3D Digital Differential Analyzer) 알고리즘을 통해 수행된다.5 센서로부터 한 번의 스캔(Scan)으로 획득되는 포인트 클라우드가 $N$ 개의 점으로 구성되어 있고, 센서의 최대 감지 범위 내에서 하나의 레이가 통과하는 평균적인 복셀의 개수가 $L$ 이라고 가정하자. 이때 CPU가 한 프레임의 데이터를 처리하기 위해 수행해야 하는 연산의 총량 $C_{total}$ 은 다음과 같이 표현될 수 있다.
$C_{total} \propto O(N \cdot L)$
문제는 $N$ 과 $L$ 이 현대 로봇 시스템에서 기하급수적으로 증가하고 있다는 점이다.

데이터 양( $N$ )의 폭증: 과거의 2D 레이저 스캐너나 저해상도 키넥트(Kinect) 센서와 달리, 최신 64채널 또는 128채널 라이다는 초당 100만 개 이상의 포인트( $N \approx 10^6$ )를 생성한다. CPU는 매 프레임마다 이 백만 개의 레이를 순차적으로, 혹은 제한된 코어 수만큼 병렬로 처리해야 한다.
해상도와 거리( $L$ )의 딜레마: 매핑의 정밀도를 높이기 위해 복셀의 크기(Resolution)를 줄이거나 센서의 탐지 거리를 늘리면, 레이 하나가 통과해야 하는 복셀의 수 $L$ 이 증가한다. 예를 들어, 탐지 거리가 50m이고 복셀 크기가 10cm인 경우, 최악의 경우 하나의 레이는 500개의 복셀을 순회하며 메모리 쓰기 연산을 수행해야 한다.

1.2 CPU 아키텍처와 SIMD 활용의 어려움

CPU는 소수의 고성능 코어를 사용하여 명령어 수준 병렬성(ILP: Instruction Level Parallelism)을 극대화하도록 설계되었다. 그러나 레이 캐스팅 연산은 이러한 CPU의 설계 철학과 상충하는 특성을 가진다.

제어 흐름의 불일치: 레이 캐스팅은 각 광선의 방향과 길이에 따라 서로 다른 메모리 주소를 접근하고 서로 다른 횟수의 루프를 반복한다. 이는 CPU 내부의 분기 예측(Branch Prediction) 유닛에 혼란을 주며, 파이프라인 스톨(Pipeline Stall)을 빈번하게 유발한다.3
SIMD 효율 저하: 현대 CPU는 AVX(Advanced Vector Extensions)와 같은 SIMD(Single Instruction, Multiple Data) 명령어셋을 통해 벡터 연산을 가속화한다. 그러나 레이 캐스팅에서 인접한 레이들은 거리에 따라 서로 다른 옥트리 노드를 순회하거나 조기에 종료(Termination)될 수 있다. 이러한 ‘발산(Divergence)’ 현상은 SIMD 레지스터 내의 데이터들이 동일한 명령어를 수행하지 못하게 만들어, 벡터화(Vectorization)를 통한 성능 향상을 제한한다.7
ALU 대역폭 한계: OctoMap은 확률 업데이트를 위해 로짓(Logit) 변환인 로그-오즈(Log-odds) 방식을 사용한다. 이는 곱셈 연산을 덧셈 연산으로 변환하여 연산 부하를 줄여주지만, 여전히 수백만 번의 부동 소수점 덧셈과 비트 연산이 요구된다. Voxblox의 경우 TSDF 거리 계산을 위해 더 복잡한 부동 소수점 연산이 필요하며, 이는 CPU의 ALU(Arithmetic Logic Unit) 자원을 포화 상태로 만든다.8

특성	OctoMap (Occupancy)	Voxblox (TSDF)	CPU 처리의 한계
기본 연산 단위	Log-odds (덧셈/뺄셈)	가중 평균 (곱셈/나눗셈)	대량의 반복 연산 시 FPU 병목 발생
데이터 접근	레이 경로 전체 순회	투영(Projection) 또는 순회	임의 메모리 접근(Random Access) 과다
병렬성	레이 간 독립성 높음	블록/복셀 간 독립성 높음	코어 수 제한으로 인한 병렬 처리 효율 저하

이러한 연산 부하는 센서 데이터가 입력되는 속도보다 처리 속도가 느려지는 현상을 초래하며, 이는 실시간 시스템에서 치명적인 지연(Latency)의 원인이 된다. 연구 결과에 따르면, 고해상도 환경에서 OctoMap의 전체 처리 시간 중 60% 이상이 레이 캐스팅과 옥트리 탐색에 소요되는 것으로 나타났다.1

2. 메모리 계층 구조와 자료 구조의 비효율성

연산 장치의 속도보다 더 심각한 병목은 메모리 시스템에서 발생한다. 이를 흔히 ’메모리 장벽(Memory Wall)’이라 부르는데, OctoMap과 같은 트리 기반 자료 구조는 CPU의 캐시 메모리 시스템과 최악의 궁합을 보인다.

2.1 옥트리(Octree) 구조와 포인터 체이싱(Pointer Chasing)

OctoMap은 광활한 3차원 공간 중 의미 있는 데이터가 존재하는 부분만을 효율적으로 저장하기 위해 옥트리(Octree) 구조를 사용한다. 옥트리는 루트 노드에서 시작하여 공간을 8분할하며 리프 노드(Leaf Node)까지 내려가는 계층적 구조이다.1 이 구조는 메모리 사용량을 줄이는 데는 탁월하지만, 데이터 접근 속도 면에서는 치명적인 약점을 가진다.

포인터 체이싱: 3차원 좌표 $(x, y, z)$ 에 해당하는 복셀 값을 읽거나 쓰기 위해서는 루트 노드부터 시작하여 리프 노드까지 트리를 탐색해야 한다. 트리 깊이가 $d$ 일 때, 이는 $d$ 번의 포인터 참조(Dereference)를 의미한다. CPU는 현재 노드의 포인터 값을 읽어와야만 다음 자식 노드의 메모리 주소를 알 수 있다(Dependent Load). 따라서 메모리 로드 명령어가 직렬화(Serialization)되며, 현대 CPU의 비순차 실행(Out-of-Order Execution) 엔진이 이를 숨길 수 없다.11
캐시 미스(Cache Miss)의 연속: 옥트리의 노드들은 맵이 확장됨에 따라 힙(Heap) 메모리의 임의 위치에 동적으로 할당된다. 이는 메모리 상의 공간적 지역성(Spatial Locality)을 파괴한다. 레이 캐스팅 과정에서 논리적으로 인접한 복셀을 방문하더라도, 실제 물리적 메모리 주소는 서로 멀리 떨어져 있을 가능성이 높다. 이로 인해 CPU는 L1, L2 캐시에서 데이터를 찾지 못하고 느린 메인 메모리(DRAM)까지 접근해야 하는 ’캐시 미스’를 빈번하게 겪게 된다.11 OctoCache와 같은 최신 연구는 이러한 포인터 체이싱과 캐시 미스가 OctoMap 성능 저하의 가장 주된 원인임을 지목하고 있다.11

2.2 Voxblox의 해시 맵과 메모리 파편화

Voxblox는 옥트리 대신 공간 해싱(Spatial Hashing) 기법을 사용하여 데이터 접근 속도를 $O(1)$ 로 개선하고자 했다.2 그러나 이 방식 역시 CPU 기반 구현에서는 한계를 드러낸다.

해시 충돌과 오버헤드: 해시 맵(Hash Map)은 평균적으로 빠른 접근 속도를 제공하지만, 해시 충돌(Collision)을 처리하는 과정에서 오버헤드가 발생한다. 또한, 수만 개의 복셀 블록(Voxel Block)을 관리하는 거대한 해시 테이블은 CPU 캐시 크기를 훨씬 초과하므로, 옥트리와 마찬가지로 캐시 효율성이 떨어진다.9
동적 할당과 메모리 파편화: Voxblox는 새로운 영역이 탐색될 때마다 복셀 블록을 동적으로 할당한다. 장시간 로봇이 주행하며 맵을 확장할 경우, 힙 메모리는 심각하게 파편화(Fragmentation)된다. 이는 운영체제(OS)의 메모리 관리자(Allocator)에 부하를 주며, 페이지 폴트(Page Fault)와 TLB(Translation Lookaside Buffer) 미스를 증가시켜 전체적인 처리 속도를 늦춘다.12

3. 확장성(Scalability)의 한계와 $O(N^3)$ 의 저주

CPU 기반 매핑 시스템은 환경의 규모가 커지거나 요구되는 정밀도가 높아질수록 성능이 급격히 저하되는 확장성 문제를 안고 있다. 이는 단순히 선형적인 성능 저하가 아니라, 복셀 해상도에 대해 3제곱( $O(R^3)$ )에 비례하는 연산량 및 메모리 증가로 나타난다.13

3.1 복셀 해상도와 TSDF 통합의 딜레마

Voxblox의 성능 벤치마크 결과는 이러한 확장성 문제를 명확히 보여준다. 복셀 크기가 20cm일 때와 2cm일 때의 처리 시간 차이는 수십 배에 달한다.

연산량 폭증: 복셀 크기를 절반으로 줄이면, 동일한 공간을 표현하기 위해 8배( $2^3$ ) 더 많은 복셀이 필요하다. CPU는 이 늘어난 복셀들에 대해 개별적으로 거리 값 업데이트와 가중치 합산 연산을 수행해야 한다.
투영(Projection) 방식의 한계: Voxblox는 속도 향상을 위해 레이 캐스팅 대신, 복셀 중심을 이미지 평면에 투영하여 깊이 값을 조회하는 방식을 사용한다.9 그러나 이 방식은 복셀 크기가 센서의 픽셀 해상도보다 작아질 경우, 여러 픽셀이 하나의 복셀에 매핑되거나 반대로 하나의 픽셀이 여러 복셀에 영향을 주는 앨리어싱(Aliasing) 문제를 야기한다. 이를 해결하기 위해 정확한 레이 캐스팅을 수행하면 연산량은 다시 감당할 수 없는 수준으로 폭증한다.

3.2 ESDF 전파(Propagation)와 전역 업데이트 병목

로봇의 경로 계획(Path Planning)을 위해 TSDF를 유클리드 부호 거리 장(ESDF)으로 변환하는 과정은 CPU 기반 시스템에서 가장 시간이 많이 소요되는 작업 중 하나이다.8

파면 전파(Wavefront Propagation) 알고리즘: ESDF 생성은 장애물 표면에서 시작하여 자유 공간으로 거리 값을 전파해 나가는 과정이다. 이는 본질적으로 너비 우선 탐색(BFS)과 유사하며, 큐(Queue)를 사용하여 변경된 복셀을 관리한다.
연쇄적 부하: 새로운 장애물이 발견되거나 기존 장애물이 사라질 경우, 그 영향은 국소적인 영역에 그치지 않고 맵 전체로 퍼져나갈 수 있다. CPU 단일 코어에서 거대한 큐를 관리하며 수만 개의 복셀 값을 연쇄적으로 업데이트하는 과정은 수백 밀리초(ms) 이상의 지연을 발생시킨다. 실험 결과에 따르면, Voxblox에서 2cm 해상도로 ESDF를 생성할 때 통합 시간은 500ms를 초과하여 실시간 로컬 플래닝을 불가능하게 만든다.15 이는 로봇이 고속으로 이동할 때 맵 업데이트가 로봇의 위치 변화를 따라가지 못하는 상황을 초래한다.

4. 표면 재구성(Meshing)과 시각화의 지연

매핑된 데이터를 사람이 이해하거나 물리 시뮬레이션에 활용하기 위해서는 복셀 그리드를 3차원 메시(Mesh) 형태로 변환해야 한다. 이 과정에서 주로 사용되는 마칭 큐브(Marching Cubes) 알고리즘은 CPU에서 수행하기에 매우 비효율적인 구조를 가지고 있다.12

중복 연산과 조건 분기: 마칭 큐브는 각 복셀의 8개 모서리 값을 확인하여 256가지 경우의 수 중 하나를 선택해 삼각형을 생성한다. $N \times N \times N$ 그리드 전체를 순회해야 하며, 인접한 복셀 간에 정점(Vertex) 정보를 공유하기 위해 복잡한 인덱싱과 조건문 처리가 필요하다. 이는 CPU의 분기 예측 실패를 유도하고 처리 속도를 늦춘다.
메모리 대역폭 포화: 메시 생성 과정은 대량의 삼각형 데이터를 생성하여 메모리에 쓰는 작업이다. CPU 기반 구현은 정점 버퍼(Vertex Buffer)를 구성하기 위해 빈번한 메모리 할당과 복사를 수행하며, 이는 가비지 컬렉션(Garbage Collection) 부하(관리형 언어의 경우)나 힙 메모리 관리 오버헤드를 발생시킨다.12
GPU와의 격차: 연구 결과에 따르면, GPU 가속을 활용한 NvBlox는 CPU 기반의 Voxblox 대비 메시 생성 속도에서 최대 177배의 성능 향상을 보였다.19 이는 CPU가 대규모 병렬 기하 연산에 얼마나 부적합한지를 단적으로 보여주는 지표이다. CPU가 1초 걸려 생성할 메시를 GPU는 0.005초 만에 생성할 수 있다는 뜻이며, 이는 로봇의 원격 조작(Teleoperation)이나 VR 시각화에 필수적인 낮은 지연 시간을 CPU만으로는 달성할 수 없음을 의미한다.

5. 시스템 레벨의 파급 효과: 데이터 유실과 모션 블러

CPU 기반 매핑의 병목 현상은 단순히 지도가 늦게 그려지는 문제를 넘어, 로봇 시스템 전체의 안정성과 안전성을 위협하는 다양한 파급 효과를 낳는다.

5.1 데이터 드롭(Data Drop)과 정보의 사각지대

로봇의 센서는 고정된 주기(예: 10Hz, 30Hz)로 데이터를 쏟아낸다. 그러나 CPU 매핑 프로세스가 이전 프레임의 처리를 완료하지 못한 상태에서 새로운 데이터가 도착하면, 시스템은 큐 오버플로우(Queue Overflow)를 방지하기 위해 최신 데이터를 버릴 수밖에 없다.21

치명적 결과: 이를 ’데이터 드롭’이라 하며, 로봇이 장애물을 감지했음에도 불구하고 매핑 파이프라인의 지연으로 인해 해당 정보가 지도에 반영되지 않고 소실되는 결과를 낳는다. 이는 고속 주행 중인 드론이나 자율 주행 차가 전방의 장애물을 “보고도 못 본 척” 충돌하게 만드는 원인이 된다.23

5.2 모션 블러(Motion Blur)와 맵의 일관성 훼손

매핑 연산이 지연되면 로봇의 위치 추정(Localization) 시점과 맵 업데이트 시점 사이에 시간적 불일치가 발생한다.

동적 왜곡: 로봇이 $t$ 시점에 관측한 데이터를 $t + \Delta t$ 시점에 맵에 통합할 때, $\Delta t$ 만큼의 지연 동안 로봇이 이동했다면 좌표 변환(Transformation)에 오차가 발생한다. 이로 인해 맵 상의 장애물이 번져 보이거나(Motion Blur), 벽면이 이중으로 생성되는 고스트(Ghost) 현상이 나타난다.24
정합 실패: 이러한 왜곡은 다시 로봇의 위치 추정 성능을 저하시키는 악순환(Feedback Loop)을 유발하며, 결과적으로 전체 SLAM(Simultaneous Localization and Mapping) 시스템의 일관성을 무너뜨린다.

5.3 리소스 경쟁(Resource Contention)

CPU는 매핑 외에도 로봇의 제어(Control), 경로 계획(Planning), 인식(Perception) 등 모든 작업을 총괄해야 한다. OctoMap이나 Voxblox가 CPU 자원을 과도하게 점유할 경우(CPU Load 100%), 우선순위가 높은 제어 루프의 실행 주기를 놓치거나 경로 재계산이 지연되는 현상이 발생한다.26 이는 로봇의 움직임을 불안정하게 만들고(Jitter), 동적 장애물에 대한 반응 속도를 떨어뜨린다.

결론적으로, OctoMap과 Voxblox로 대표되는 CPU 기반 매핑 기술은 초기 로봇 공학의 발전을 이끌었으나, 고해상도 센서 데이터의 폭증과 실시간 고속 기동이 요구되는 현대의 응용 환경에서는 명백한 한계에 도달했다. 순차 처리 아키텍처의 연산 한계, 포인터 기반 자료 구조의 메모리 비효율성, 그리고 확장성의 부재는 더 이상 CPU 단일 처리만으로는 해결될 수 없는 문제임을 시사한다. 따라서 대규모 병렬 처리가 가능한 GPU 가속 기술이나 이기종 컴퓨팅(Heterogeneous Computing) 아키텍처의 도입은 차세대 고정밀 매핑 시스템을 위한 선택이 아닌 필수적인 진화 방향이다.

6. 참고 자료

OctoMap-RT: Fast Probabilistic Volumetric Mapping Using Ray …, https://graphics.ewha.ac.kr/octomap-rt/images/RAL/OctoMap-RT_RAL23.pdf
ethz-asl/voxblox: A library for flexible voxel-based mapping, mainly focusing on truncated and Euclidean signed distance fields. - GitHub, https://github.com/ethz-asl/voxblox
Data parallelism for ray casting large scenes on a cpu-gpu cluster - Open Metu, https://open.metu.edu.tr/handle/11511/18229
Accelerating Probabilistic Volumetric Mapping using Ray-Tracing Graphics Hardware - arXiv, https://arxiv.org/pdf/2011.10348
CPU Ray Casting - c++ - Stack Overflow, https://stackoverflow.com/questions/6985186/cpu-ray-casting
Fast Docking on Graphics Processing Units via Ray-Casting | PLOS One, https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0070661
On Ray Reordering Techniques for Faster GPU Ray Tracing - arXiv, https://arxiv.org/html/2506.11273v1
Voxblox: Incremental 3D Euclidean Signed Distance Fields for On …, https://helenol.github.io/publications/iros_2017_voxblox.pdf
Real-Time Metric-Semantic Mapping for Autonomous Navigation in Outdoor Environments - UCL Discovery, https://discovery.ucl.ac.uk/10194629/1/tase2024_metric_semantic_mapping_navigation.pdf
OctoMap: An Efficient Probabilistic 3D Mapping Framework Based on Octrees, https://courses.cs.washington.edu/courses/cse571/16au/slides/hornung13auro.pdf
OctoCache: Caching Voxels for Accelerating 3D … - Alan Zaoxing Liu, https://zaoxing.github.io/papers/2025/ASPLOS25_OctoCache.pdf
why is my marching cubes algorithm so slow? - Stack Overflow, https://stackoverflow.com/questions/74589315/why-is-my-marching-cubes-algorithm-so-slow/74589827
nvblox: GPU-Accelerated Incremental Signed Distance Field Mapping | Request PDF, https://www.researchgate.net/publication/382991572_nvblox_GPU-Accelerated_Incremental_Signed_Distance_Field_Mapping
coVoxSLAM: GPU accelerated globally consistent dense SLAM - arXiv, https://arxiv.org/html/2410.21149v1
Performance — voxblox documentation - Read the Docs, https://voxblox.readthedocs.io/en/latest/pages/Performance.html
nvblox: GPU-Accelerated Incremental Signed Distance Field Mapping - arXiv, https://arxiv.org/html/2311.00626v2
Speeding up marching cubes : r/VoxelGameDev - Reddit, https://www.reddit.com/r/VoxelGameDev/comments/13gzs2/speeding_up_marching_cubes/
Very efficient/fast marching cube implementation - Computer Graphics Stack Exchange, https://computergraphics.stackexchange.com/questions/8730/very-efficient-fast-marching-cube-implementation
Emilie Wirbel - CatalyzeX, https://www.catalyzex.com/author/Emilie%20Wirbel
annika-thomas/MIT-PALS - GitHub, https://github.com/annika-thomas/MIT-PALS
Towards 5G-Enabled Intelligent Machines - Simple search, https://ltu.diva-portal.org/smash/get/diva2:1851743/FULLTEXT02.pdf
Investigating a Demand Access Scheduling Paradigm for NASA’s Deep Space Network - JPL Artificial Intelligence Group, https://ai.jpl.nasa.gov/public/documents/papers/hackett-iwpss2019-demandaccess.pdf
Real-Time 3D Occupancy Mapping by Multi-Agent Map Sharing using GPU Acceleration, https://www.imec-int.com/en/work-at-imec/job-opportunities/real-time-3d-occupancy-mapping-multi-agent-map-sharing-using-gpu
UAV Computing-Assisted Search and Rescue Mission Framework for Disaster and Harsh Environment Mitigation - ResearchGate, https://www.researchgate.net/publication/361557229_UAV_Computing-Assisted_Search_and_Rescue_Mission_Framework_for_Disaster_and_Harsh_Environment_Mitigation
International Conference on Multidisciplinary Breakthroughs and NextGen Technologies (ICMBNT–2025) - Melange Publications, https://melangepublications.com/img/ICMBNT25.pdf
NanoMap: Fast, Uncertainty-Aware Proximity Queries with Lazy Search Over Local 3D Data, https://dspace.mit.edu/bitstream/handle/1721.1/137099/1802.09076.pdf?sequence=2&isAllowed=y