Giải Thuật Lấy Mẫu Poisson Disk: Từ Bài Toán 10 Phút Đến Kỹ Thuật Tối Ưu Hóa Hiện Đại

Trong khi một nhóm chín nhà toán học năm 2024 công bố một chứng minh đồ sộ gần 1.000 trang cho giả thuyết Langlands hình học, một công trình khác ra đời năm 2007 lại chỉ gói gọn trong một trang giấy với gần 1.000 trích dẫn — và có thể hiểu trọn vẹn trong chưa đầy 10 phút. Đó là giải thuật Poisson Disk Sampling của Robert Bridson, một giải pháp đơn giản nhưng đầy uy lực cho bài toán đặt các vật thể ngẫu nhiên nhưng không quá gần nhau, một vấn đề thường gặp trong đồ họa máy tính và mô phỏng.

Hiểu một cách đơn giản, nếu bạn đang cố gắng tạo một khu rừng theo quy trình (procedurally generate) và cần đặt cây, thì việc lấy mẫu ngẫu nhiên thuần túy sẽ khiến nhiều cây mọc chồng lên nhau. Giải thuật Bridson giải quyết triệt để vấn đề này bằng cách thiết lập một khoảng cách tối thiểu giữa bất kỳ hai điểm nào, tạo ra một phân bố được gọi là phân bố đĩa Poisson.

Thuật toán của Bridson: Tư duy từ góc nhìn hiệu quả

Giả sử khoảng cách tối thiểu mong muốn giữa các điểm là rrr trong không gian ddd chiều. Thuật toán Bridson hoạt động theo nguyên lý sau:

• Chia không gian thành một lưới có cạnh bằng r√drd, đảm bảo mỗi ô lưới chỉ chứa tối đa một điểm. Việc này giúp việc kiểm tra va chạm trở nên cực kỳ nhanh chóng thay vì phải duyệt toàn bộ danh sách điểm.
• Khởi tạo một danh sách "active" với một điểm ngẫu nhiên duy nhất trong không gian.
• Lặp lại cho đến khi danh sách rỗng: Lấy ngẫu nhiên một điểm ppp từ danh sách active. Sau đó, thử lấy mẫu tối đa kkk lần (thường k=30k = 30) trong vùng hình vành khăn từ bán kính rrr đến 2r2r xung quanh ppp. Nếu tìm thấy một điểm hợp lệ, thêm nó vào danh sách active. Nếu không, loại ppp ra khỏi danh sách.

Để lấy mẫu đồng đều trong vùng hình vành khăn, bạn có thể tạo một vector đơn vị ngẫu nhiên và một số thực, sau đó kết hợp chúng để ra tọa độ cuối cùng. Kỹ thuật này tận dụng lợi thế của lưới ô vuông: thay vì kiểm tra khoảng cách tới mọi điểm đã đặt, chỉ cần kiểm tra các ô lân cận, giảm độ phức tạp từ tuyến tính xuống còn hằng số.

Cải tiến thứ nhất: Tận dụng mối quan hệ cha – con

Bridson có một thiếu sót nhỏ: khi đặt một điểm mới qqq từ điểm cha ppp, thuật toán không hề ghi nhớ rằng vùng phía sau qqq (gần ppp) chắc chắn không thể chứa điểm nào khác. Điều này tạo ra một vùng hình nón cấm (forbidden cone) mà ta có thể tính toán và loại bỏ ngay từ đầu.

Dù việc chứng minh công thức hình học khá phức tạp, nhưng ý tưởng rất trực quan: khi lấy mẫu điểm tiếp theo quanh qqq, bạn chỉ cần lấy góc nằm ngoài vùng hình nón này. Theo tác giả, việc áp dụng cải tiến này giúp giảm đáng kể số vòng lặp thất bại và tăng số điểm tạo ra được trong cùng một thời gian.

Cải tiến thứ hai: Điều chỉnh phân bố khoảng cách

Thay vì chọn ngẫu nhiên hoàn toàn khoảng cách trong khoảng [r,2r][r, 2r], tác giả đề xuất thay đổi hàm phân bố bằng cách cho phép một số mũ ccc tùy chỉnh trong công thức lấy mẫu ngược (inverse transform sampling). Khi ccc càng nhỏ (âm), các điểm mới có xu hướng nằm gần điểm cha hơn, tạo ra mật độ dày đặc hơn. Tuy nhiên, nếu ccc quá nhỏ, phân bố sẽ mất đi tính ngẫu nhiên vốn có, tạo ra các chuỗi điểm thẳng và các vùng trống khó lấp.

Qua thử nghiệm, tác giả rút ra công thức thực nghiệm c=−1.4−17√kc=−1.4−17k với giải thuật tối ưu hóa cha-con, giúp số điểm tạo ra xấp xỉ với một bộ lấy mẫu Poisson disk lý tưởng và đạt độ phủ bão hòa khoảng 54.7% diện tích — một con số được biết đến trong mô hình hấp phụ ngẫu nhiên tuần tự.

Stippling: Ứng dụng nghệ thuật từ việc điều chỉnh bán kính

Một trong những ứng dụng thú vị nhất của Poisson Disk Sampling là khi bạn thay đổi bán kính rrr theo một hàm số dựa trên vị trí. Ví dụ, định nghĩa rrr là độ sáng của từng pixel trong một bức ảnh sẽ tạo ra hiệu ứng stippling — một kỹ thuật tạo hình ảnh từ hàng nghìn chấm mực nhỏ. Có thể kết hợp ba bộ lấy mẫu Poisson (mỗi bộ cho một kênh màu RGB) để tạo ra các bức tranh chấm đầy màu sắc và nghệ thuật.

Tác giả cũng chia sẻ dự án Poisson Cam, một công cụ stippling video theo thời gian thực chạy trên GPU dựa trên giải thuật PixelPie — một biến thể song song hóa của Poisson Disk Sampling, dạy cho anh ta về lập trình shader, Rust và thuật toán stream compaction.

Maximality và Uniformity: Trình tạo mẫu không loại bỏ (Rejection-free)

Phần cuối của bài viết giới thiệu một giải thuật mới của Scott A. Mitchell (năm 2022) hứa hẹn hơn hẳn Bridson trên ba khía cạnh quan trọng:

• Maximality: Sau khi kết thúc, chắc chắn không thể thêm một điểm mới nào mà không vi phạm tính chất Poisson disk.
• Uniformity: Giải thuật lấy mẫu từ một phân bố đồng đều trên tất cả các tập hợp điểm Poisson disk cực đại có thể có.
• Determinism: Không sử dụng phương pháp loại bỏ (rejection sampling), do đó không có bất kỳ lần thử thất bại nào.

Ý tưởng cốt lõi rất thanh lịch: thay vì "ném phi tiêu" và loại bỏ, hãy tưởng tượng không gian được chia thành các ô. Từ một ô, ta "đục bỏ" (carve out) một vùng tròn quanh điểm vừa đặt. Sau đó, ta chỉ cần lấy mẫu từ các vùng còn lại với trọng số phù hợp, đảm bảo không bao giờ thất bại và kết quả cuối cùng luôn tối đa.

Mặc dù phức tạp hơn đáng kể, thuật toán của Mitchell chạy nhanh tương đương với bản Bridson đã tối ưu, mở ra hướng đi mới cho các thư viện đồ họa và mô phỏng trong tương lai.

---

Poisson Disk Sampling là một ví dụ hoàn hảo cho thấy một ý tưởng toán học đơn giản có thể tạo nên ảnh hưởng sâu rộng trong nhiều ngành, từ đồ họa máy tính, mô phỏng vật lý, đến các ứng dụng nghệ thuật số như video stippling. Với các cải tiến liên tục trong gần hai thập kỷ, kỹ thuật này vẫn đang được mở rộng và tối ưu cho cả CPU lẫn GPU, giúp nó trở thành một công cụ quan trọng trong bộ kỹ năng của các lập trình viên đồ họa hiện đại.