Tantangan Performa Viewport CAD pada Browser

Saat mem-porting aplikasi CAD seperti LibreCAD ke arsitektur web, performa rendering sering kali anjlok drastis saat memuat file DXF berskala menengah hingga besar (50.000 hingga 500.000 entitas). Setiap kali pengguna melakukan operasi pan atau zoom, loop rendering utama harus mengevaluasi entitas mana yang berada di dalam area pandang (viewport).

Pendekatan naif menguji koordinat setiap garis, busur (arc), dan poligon secara berurutan di thread JavaScript atau C++/WASM. Operasi ini membutuhkan kompleksitas waktu O(N). Pada 100.000 entitas, full-scan terus-menerus pada 60 FPS akan memicu frame drop parah dan membekukan UI thread. Solusi arsitektural untuk masalah ini adalah memotong proses evaluasi menggunakan spatial indexing R-Tree SQLite via WASM (seperti sql.js atau modul resmi SQLite WASM).

Konsep Bounding Box dan Index R-Tree

Ekstensi R-Tree SQLite mengorganisasi data spasial multidimensi ke dalam struktur pohon seimbang hierarkis berbasis Minimum Bounding Box (MBR atau AABB). R-Tree mengelompokkan objek geometris berdekatan ke dalam node induk. Saat query rentang koordinat (window query) dijalankan, SQLite melintasi cabang pohon yang beririsan saja, mengeliminasi mayoritas data tanpa membaca koordinat detail satu per satu.

1. Skema Tabel SQLite R-Tree

Ekstensi R-Tree memerlukan virtual table dengan kolom ID integer 64-bit diikuti pasangan batas minimum dan maksimum untuk setiap dimensi koordinat (2D: minX, maxX, minY, maxY).

-- Tabel metadata entitas CAD asli
CREATE TABLE cad_entities (
    id INTEGER PRIMARY KEY,
    layer_name TEXT NOT NULL,
    entity_type TEXT NOT NULL, -- LINE, ARC, CIRCLE, LWPOLYLINE
    raw_geometry BLOB NOT NULL
);

-- Virtual table R-Tree untuk spatial indexing (Bounding Box)
CREATE VIRTUAL TABLE cad_spatial_idx USING rtree(
    id,              -- Integer PK, foreign key ke cad_entities.id
    minX, maxX,      -- Batas horizontal (float)
    minY, maxY       -- Batas vertikal (float)
);

2. Populasi Data Bounding Box dari Entitas DXF

Saat file DXF diparsing, hitung AABB dari setiap primitif geometris sebelum menyimpannya ke database:

-- Contoh insert entitas garis dari (-10.5, 20.0) ke (5.0, 45.0)
INSERT INTO cad_entities (id, layer_name, entity_type, raw_geometry)
VALUES (101, 'WALLS', 'LINE', X'010203...');

INSERT INTO cad_spatial_idx (id, minX, maxX, minY, maxY)
VALUES (101, -10.5, 5.0, 20.0, 45.0);

Query Window Filter (Viewport Intersection)

Saat kamera CAD bergerak, dapatkan koordinat batas viewport dunia: viewport_minX, viewport_maxX, viewport_minY, dan viewport_maxY. Eksekusi query intersection berikut untuk mengambil entitas yang harus digambar:

SELECT 
    e.id,
    e.layer_name,
    e.entity_type,
    e.raw_geometry
FROM cad_entities e
JOIN cad_spatial_idx idx ON e.id = idx.id
WHERE idx.maxX >= :vp_minX 
  AND idx.minX <= :vp_maxX 
  AND idx.maxY >= :vp_minY 
  AND idx.minY <= :vp_maxY;

Verifikasi Query Plan: Eliminasi Full-Table Scan

Uji eksekusi query menggunakan EXPLAIN QUERY PLAN untuk memverifikasi bahwa SQLite tidak melakukan pemindaian linear.

EXPLAIN QUERY PLAN
SELECT e.id 
FROM cad_entities e
JOIN cad_spatial_idx idx ON e.id = idx.id
WHERE idx.maxX >= -50.0 AND idx.minX <= 50.0 
  AND idx.maxY >= -50.0 AND idx.minY <= 50.0;

Output Eksekusi:

QUERY PLAN
|--SCAN idx VIRTUAL TABLE INDEX 1:r-tree [minX <= ? AND maxX >= ? AND minY <= ? AND maxY >= ?]
`--SEARCH e USING INTEGER PRIMARY KEY (rowid=?)

Analisis output:

  • SQLite menandai SCAN idx VIRTUAL TABLE INDEX 1:r-tree, yang berarti pencarian langsung memanfaatkan pohon R-Tree berindeks, bukan memindai semua baris satu demi satu.
  • Pengambilan detail entitas dari tabel utama menggunakan lookup O(1) melalui primary key (INTEGER PRIMARY KEY (rowid=?)).
  • Full-table scan pada data geometri berhasil dieliminasi seluruhnya.

Karakteristik Latensi Read Query

Pada pengujian dataset DXF arsitektural berukuran ~120.000 entitas yang dijalankan pada SQLite WASM di browser (Chrome 122, M2 chip):

  • Tanpa Index (Full-Table Scan): Latensi filter berkisar antara 35ms - 60ms per frame. Melebihi budget 16.6ms (batas 60 FPS), menyebabkan viewport tersendat (jank).
  • Dengan R-Tree Index (Viewport ~5% dari total kanvas): Latensi query turun menjadi 0.8ms - 2.5ms, mengembalikan sekitar 2.000 - 5.000 entitas yang relevan secara instan.

Trade-off dan Limitasi

Meskipun R-Tree SQLite sangat efisien untuk query baca, terdapat konsekuensi teknis yang harus diperhitungkan:

  • Overhead Ingestion: Penyisipan data baru (INSERT) ke dalam tabel R-Tree membutuhkan waktu tambahan untuk split node saat pohon diseimbangkan kembali. Parsing file DXF awal akan memakan waktu 15-25% lebih lama.
  • Ukuran Memori SQLite WASM: Virtual table R-Tree memerlukan ruang penyimpanan internal ekstra di memori WebAssembly atau IndexedDB.
  • False Positives pada Geometri Miring: Garis diagonal panjang akan menghasilkan bounding box yang besar. Filter R-Tree dapat mengembalikan entitas tersebut meskipun garis aslinya tidak menyentuh viewport. Diperlukan pengujian interseksi eksak tingkat kedua (broad-phase vs narrow-phase) di canvas renderer.