Tugas Kecil 2 IF2211 Strategi Algoritma - 3D Voxelizer

Voxelization Objek 3D Menggunakan Octree

Deskripsi

3D Voxelizer adalah program berbasis C++ yang dirancang untuk mengonversi representasi model 3D geometris (berformat .obj) yang tersusun dari poligon sembarang menjadi susunan kubus bervolume (voxel) yang berukuran seragam.

Program ini menyelesaikan permasalahan pembagian ruang dengan menghindari komputasi pada ruang kosong. Program mengimplementasikan pendekatan algoritma berikut:

1. Algoritma Divide and Conquer (Octree): Memecah ruang pembatas (Bounding Box) secara rekursif menjadi delapan subruang (octants) yang lebih kecil hingga mencapai tingkat kedalaman (depth) maksimum.
2. Separating Axis Theorem (SAT): Melakukan collision detection antara kubus pembatas ruang dengan segitiga-segitiga penyusun model 3D menggunakan 13 sumbu uji. Jika sebuah ruang terdeteksi kosong, program akan melakukan pruning cabang penelusuran.
3. Optimasi Face Culling: Menggunakan struktur data Hash Table ($O(1)$) untuk mendeteksi voxel yang saling bertetangga, sehingga program hanya menulis bidang permukaan luar ke file output untuk menghemat ukuran file.

Fitur

• Kustomisasi Kedalaman (Depth): Pengguna dapat menentukan tingkat kedalaman rekursi Octree yang secara langsung mempengaruhi tingkat kehalusan dan ukuran voxel yang dihasilkan.
• Laporan Eksekusi: Program mencetak statistik setelah proses selesai, mencakup metrik waktu eksekusi, total titik dan bidang yang diproses, jumlah node pohon yang terbentuk, serta jumlah node yang di-prune.
• 3D Viewer: Memiliki subsistem Viewer kustom terintegrasi menggunakan pustaka grafis Raylib. Memungkinkan pengguna me-render hasil .obj secara real-time di jendela 3D dengan fitur kamera orbital (pan, zoom, rotate).

Prasyarat dan Cara Menjalankan Program

Unduh kode sumber atau clone repositori ini:

git clone https://github.com/NikSamSim/Tucil2_13524029.git
cd Tucil2_13524029

Windows

Prasyarat Dasar

Pastikan sudah menginstal g++ (C++ Compiler) dan program make. Hal ini bisa didapatkan dengan menginstal MinGW atau MSYS2.

Menjalankan Program Utama (Voxelizer)

Program utama tidak memerlukan library tambahan apapun.

1. Buka terminal (PowerShell atau Command Prompt) di folder root repository ini.
2. Lakukan kompilasi program utama dengan perintah:

mingw32-make clean-all  
mingw32-make 

3. Jalankan program dengan perintah:

mingw32-make run-voxelizer     

4. Program akan berjalan secara interaktif. Masukkan path file model, nama output, dan depth yang diinginkan.

Menjalankan Program 3D Viewer

Program membutuhkan library Raylib untuk MinGW terlebih dahulu. Jika menggunakan MSYS2, buka terminal MSYS2 UCRT64 dan jalankan:

pacman -S mingw-w64-ucrt-x86_64-raylib

1. Setelah Raylib terinstal, lakukan kompilasi khusus untuk viewer dengan perintah:

mingw32-make view         

2. Jalankan viewer dengan perintah:

mingw32-make run-viewer        

3. Masukkan path file .obj.

Linux

Prasyarat Dasar

Pastikan sudah memiliki compiler dan paket pembangunan dasar Linux. Buka Terminal dan jalankan:

sudo apt update
sudo apt install build-essential

Menjalankan Program Utama (Voxelizer)

Program utama tidak memerlukan library tambahan apapun.

1. Buka terminal di folder root repository ini.
2. Lakukan kompilasi program utama dengan perintah:

make clean-all  
make 

3. Jalankan program dengan perintah:

make run-voxelizer     

4. Program akan berjalan secara interaktif. Masukkan path file model, nama output, dan depth yang diinginkan.

Menjalankan Program 3D Viewer

Program membutuhkan library Raylib yang dapat diperoleh melalui build dari source code. Jalankan baris perintah berikut:

sudo apt install -y git cmake libasound2-dev mesa-common-dev libx11-dev libxrandr-dev libxi-dev xorg-dev libgl1-mesa-dev libglu1-mesa-dev
git clone https://github.com/raysan5/raylib.git
cd raylib/src
make PLATFORM=PLATFORM_DESKTOP
sudo make install
cd ../..

1. Setelah Raylib terinstal, lakukan kompilasi khusus untuk viewer dengan perintah:

make view         

2. Jalankan viewer dengan perintah:

make run-viewer        

3. Masukkan path file .obj.

Struktur Folder

Tucil2_13524029/
├── .git/
├── doc/                 # Berisi laporan
├── src/                 # Berisi source code program
│   ├── Geometry.hpp     # Definisi struktur geometri dasar
│   ├── main.cpp         # Program utama voxelizer
│   ├── main_viewer.cpp  # Program utama viewer
│   ├── ObjParser.cpp    # Implementasi pembacaan file .obj
│   ├── ObjParser.hpp    # Header parser .obj
│   ├── Octree.cpp       # Implementasi struktur data Octree
│   ├── Octree.hpp       # Header struktur data Octree
│   ├── Utils.hpp        # Utilitas tambahan
│   ├── Viewer.cpp       # Implementasi viewer 3D
│   ├── Viewer.hpp       # Header viewer 3D
│   ├── Voxelizer.cpp    # Implementasi proses voxelization
│   └── Voxelizer.hpp    # Header voxelizer
├── test/                # Berisi data uji
├── Makefile             # Build script program
├── .gitignore
├── LICENSE
└── README.md

Author

Niko Samuel Simanjuntak (13524029)