Thư viện earstrip: tam giác hóa 3,7 triệu đa giác bản đồ chỉ trong 489 ms, nhanh hơn earcut

GPU chỉ biết tô kín các tam giác, trong khi bản đồ lại chủ yếu là đa giác: tòa nhà, công viên, bãi đỗ xe, dải cỏ giữa hai đường ray tàu điện. Trước khi bất kỳ hình nào được tô màu, mọi đường viền đều phải được cắt thành tam giác. Đây chính là bài toán mà nhóm Globus Software đã giải quyết, và họ vừa công bố kết quả dưới dạng một thư viện nhỏ mang tên earstrip.

Bài toán: tam giác hóa đa giác ở quy mô bản đồ

Để hình dung quy mô, hãy lấy dữ liệu thực tế của họ. Vài dãy phố ở quận Śródmieście, Warsaw chứa 331 đa giác với 5.151 đỉnh, biến thành 4.514 tam giác. Nhưng đó chỉ là một góc rất nhỏ: riêng mức zoom 13 của bản đồ ngoại tuyến tỉnh Masovian quanh Warsaw đã có 3.740.425 đa giác.

Trên một lõi M4 Pro, bộ tam giác hóa Delaunay có ràng buộc trong engine của họ cần 2,93 giây để cắt hết chỗ đa giác đó. Tháng 10 vừa qua, nhóm đã thay nó bằng thuật toán ear clipping và rút ngắn thời gian xuống chỉ còn 489 ms.

Vì sao Delaunay là quá mức cần thiết

Tam giác hóa Delaunay có một tính chất đẹp: không điểm nào nằm bên trong đường tròn ngoại tiếp của bất kỳ tam giác nào, nhờ đó các tam giác có hình dạng cân đối nhất. Điều này rất quan trọng khi cần nội suy giá trị giữa các đỉnh hoặc chạy mô phỏng, nhưng việc tô màu phẳng thì không quan tâm: GPU tô một tam giác mảnh như kim cũng chính xác như một tam giác đầy đặn.

Vấn đề nằm ở chỗ gần một nửa số đa giác của Masovian, tức 1,8 triệu đa giác, có từ bốn đỉnh trở xuống. Một tam giác không cần cắt gì cả, một tứ giác lồi chỉ cần hai tam giác, vậy mà mã Delaunay vẫn tiêu tốn 419 ms chỉ để dựng lại từ đầu từng cấu trúc tam giác cho chúng.

Ý tưởng ear clipping: cắt tai từng nhút một

Một "tai" của đa giác là một góc có thể cắt bỏ bằng một đường thẳng. Lấy ba đỉnh liên tiếp a, b, c: nếu góc tại b lồi và không phần nào khác của đa giác lọt vào tam giác abc, thì tam giác đó là một tai. Cắt nó đi, phần còn lại là đa giác ít hơn một đỉnh.

Năm 1975, Gary Meisters đã chứng minh rằng mọi đa giác đơn giản có hơn ba đỉnh đều có ít nhất hai tai không chồng lấn. Vì vậy luôn còn tai để cắt, và một đa giác n đỉnh sẽ vỡ thành n − 2 tam giác.

Thuật toán cơ bản chỉ cần một phép kiểm tra "góc này có phải tai không?", nhưng phiên bản ngây thơ phải duyệt qua toàn bộ đỉnh còn lại của đường viền cho mỗi lần kiểm tra. Nhóm Globus đã tối ưu dần qua nhiều bước, mỗi ý tưởng là một commit, và đo thời gian trên đúng 3,7 triệu đa giác đó.

Chuỗi tối ưu đưa thời gian từ giây xuống mili-giây

Các bước chính trong quá trình tinh chỉnh:

• Chỉ kiểm tra các "vết lõm": thay vì duyệt mọi đỉnh, chỉ những đỉnh lồi hướng vào trong mới có thể chặn một tai, nên thuật toán giữ một danh sách riêng các đỉnh này.
• Kiểm tra bằng bucket: với danh sách dài, chia điểm thành các nhóm 64 điểm và dùng bit mask để loại nhanh, đưa tổng thời gian xuống 519 ms. Các đa giác từ 33 đến 256 đỉnh hưởng lợi nhiều nhất, giảm từ 327 xuống 216 ms.
• Chỉ kiểm tra các vết lõm đã đánh dấu: lượt đầu đặt một bit cho mỗi điểm trúng thay vì đếm, lượt kiểm tra chính xác sau đó chỉ đọc những vết lõm đó. Số điểm phải đọc giảm từ 128 triệu xuống 120 triệu.

Kết quả cuối cùng chính là mã nguồn của earstrip như được công bố: 489 ms, nhanh gấp 6 lần Delaunay trên cùng tập đa giác.

Khi dữ liệu bản đồ không còn "đơn giản"

Định lý Meisters chỉ đúng với đa giác đơn giản. Dữ liệu bản đồ được làm tròn về lưới ô, và việc làm tròn có thể phá vỡ tính đơn giản đó. Lấy ví dụ ga đường sắt Warszawa Śródmieście, cách các dãy phố trên chưa đầy một cây số:

• Ở mức 14 bit, bước lưới 18 cm, có 31 trong 154 đỉnh bị gộp vào đỉnh bên cạnh dù đường viền vẫn còn nguyên.
• Ở 12 bit, gần một nửa số đỉnh bị gộp, nhưng bộ cắt vẫn xử lý được.
• Ở 11 bit, đường viền chạm vào chính nó theo cách không còn tai nào cả.
• Ở 10 bit, mọi thứ lại may mắn hoạt động trở lại.

Khi không tìm được tai nào, bộ cắt sẽ bỏ các góc không có diện tích rồi thử lại một lượt. Nếu vẫn thất bại, engine chuyển đa giác đó sang mã Delaunay, vốn vẫn được giữ lại cho mục đích này. Trong dữ liệu Masovian có 76 đa giác rơi vào trường hợp đó, và bộ sinh bản đồ mới hiện đã làm tròn mọi đa giác bằng snap rounding của GEOS rồi kiểm tra trước xem ear clipping có cắt được không.

Delaunay còn một nhiệm vụ khác: mỗi lỗ hổng cần một cầu nối, và việc tìm cầu nối phải quét toàn bộ đường viền, nên đa giác có hàng nghìn lỗ hổng sẽ rất tốn kém. Bản đồ thế giới của họ có một đa giác với 11.675 lỗ hổng: ear clipping cần 606 ms, còn Delaunay chỉ 17 ms. Vì thế engine chuyển mọi đa giác có từ 128 lỗ hổng trở lên sang Delaunay.

Hiệu năng trên trình duyệt so với earcut

Khi đem so với earcut, bộ cắt tai đứng sau MapLibre và Mapbox GL, kết quả khá thú vị. Ở dạng C++ gốc, hai bên rất sát nhau: earcut.hpp 3.2.4 chậm hơn earstrip 14%. Nhưng khi biên dịch sang WebAssembly:

• Trong V8, earstrip mất 23% hiệu năng còn earcut.hpp mất tới 67%, gần như toàn bộ nằm ở vòng lặp chính tìm tai.
• earcut.hpp trong WebAssembly chỉ còn nhanh hơn earcut.js thuần JavaScript 19%, và chỉ 10% nếu mỗi đa giác là một lần gọi riêng từ JavaScript.
• Gói npm của earstrip, với cùng cách gọi thay thế earcut, nhanh hơn 1,4 lần trong V8 và 1,6 lần trong JavaScriptCore.
• Với các lệnh gọi trực tiếp, đa giác đi thẳng vào bộ nhớ của module và trả về một bộ đệm chỉ số duy nhất cho WebGL 2 hoặc WebGPU, nhanh hơn 1,7 lần trong V8 và 2,1 lần trong JavaScriptCore.

Điều đáng chú ý là mọi bản dựng WebAssembly đều cho ra tam giác giống hệt bản gốc trên toàn bộ 4,4 triệu đa giác của mức zoom 13 và 9.

Ý nghĩa với cộng đồng phát triển bản đồ web

earcut đã làm rất tốt một số việc mà earstrip kế thừa, chẳng hạn nguyên lý chỉ vết lõm mới chặn được tai. Nhưng earcut thiếu bước tắt nhanh cho đa giác lồi, thiếu cách sinh ra dải chỉ số, và dừng ngay ở điểm đầu tiên nằm trong tam giác thay vì đếm nhánh. Với dữ liệu zoom 13 mà tai không cắt chính xác được, tam giác của earcut lệch khỏi phép tô chẵn-lẻ của các vành trên 31% số điểm ảnh, còn earstrip chỉ lệch 0,15%.

Với các nhà phát triển bản đồ web tại Việt Nam đang xây dựng ứng dụng hiển thị dữ liệu không gian quy mô lớn, đây là một lựa chọn đáng cân nhắc: thư viện chỉ gồm một header C++, có bản dựng WebAssembly trên npm với cùng tham số như earcut, và được phát hành dưới giấy phép ISC, cùng loại giấy phép mà earcut đang dùng.

Mã nguồn earstrip có trên GitHub và npm, kèm theo các đa giác trong bài viết và mã để bạn tự đo thời gian so với earcut trên máy của mình.