Poisson Disk Sampling của Bridson: Nhanh hơn, Dày đặc hơn, và Vẫn Ngẫu nhiên

Poisson disk sampling là công cụ chính đằng sau các khu rừng thủ tục, stippling, và kết cấu blue-noise. Thuật toán một trang của Bridson năm 2007 vẫn là lựa chọn hàng đầu, nhưng nó không tối ưu. Hai điều chỉnh — một để bỏ qua các mẫu góc lãng phí, một để thiên vị bán kính lấy mẫu — có thể giảm đáng kể số lần lặp và xếp các điểm chặt hơn mà không hy sinh tính ngẫu nhiên làm cho đầu ra trông tự nhiên.

Thuật toán của Bridson trong một câu

Mục tiêu: đặt các điểm ngẫu nhiên trong không gian sao cho không có hai điểm nào gần hơn khoảng cách tối thiểu r. Phương pháp lấy mẫu loại bỏ ngây thơ suy giảm nhanh khi không gian lấp đầy. Mẹo của Bridson là giữ một danh sách active các điểm có thể vẫn chấp nhận hàng xóm mới. Với mỗi điểm hoạt động, lấy mẫu vành khăn giữa r và 2r tối đa k lần, sử dụng lưới nền để kiểm tra va chạm trong thời gian hằng số. Nếu tìm thấy điểm hợp lệ, thêm nó vào danh sách hoạt động; nếu không, loại bỏ điểm hiện tại. Giá trị khuyến nghị k=30 cân bằng tỷ lệ thành công với số lần thử lãng phí.

Tối ưu hóa 1: Bỏ qua vùng bóng của điểm cha

Khi một điểm mới q được sinh ra từ p, vành khăn quanh q hướng về p một phần không hợp lệ — bất kỳ điểm nào ở đó sẽ quá gần p. Bằng cách lưu trữ điểm cha của mỗi điểm, bạn có thể tính góc hình nón của các hướng không hợp lệ và chỉ lấy mẫu trong phạm vi hợp lệ. Nửa góc của hình nón được tính bằng tối thiểu của hai số hạng arccos, tùy thuộc vào việc vòng tròn trong hay ngoài giới hạn nó. Việc ghi chép đơn giản này giảm số lần lặp cần thiết để lấp đầy một vùng, như các thí nghiệm của tác giả cho thấy.

Tối ưu hóa 2: Thiên vị bán kính

Thay vì lấy mẫu vành khăn đồng đều, bạn có thể làm lệch phân phối khoảng cách về phía mép ngoài. CDF của khoảng cách tỷ lệ với x^d trong không gian d chiều, nhưng bạn có thể thay thế số mũ d bằng một hằng số điều chỉnh được c. Giá trị âm của c đẩy các điểm xa hơn khỏi điểm cha, giúp xếp nhiều điểm hơn vào không gian. Tác giả nhận thấy theo kinh nghiệm rằng c = -1.4 - 17/sqrt(k) hoạt động tốt cho k từ 15 đến 40, tạo ra mật độ gần với mật độ lý thuyết tối đa cho hấp phụ tuần tự ngẫu nhiên. Nhưng hãy cẩn thận: nếu quá âm, đầu ra trở nên có hoa văn rõ ràng, với các chuỗi và khoảng trống phá hỏng tính ngẫu nhiên.

Stippling và các biến thể song song

Poisson disk sampling không giới hạn ở r không đổi. Bằng cách làm cho r trở thành một hàm của vị trí, bạn có thể stipple hình ảnh — các vùng tối hơn nhận được điểm dày đặc hơn. Tác giả cũng nhấn mạnh PixelPie, một thuật toán song song trên GPU cho phép stippling thời gian thực, và đề cập đến một phương pháp xác định năm 2022 của Scott Mitchell đáng được chú ý hơn.

Những điểm chính

• Thuật toán của Bridson hiệu quả nhưng vẫn còn chỗ để tối ưu hóa.
• Lưu trữ điểm cha cho phép bạn bỏ qua các phạm vi góc không hợp lệ, giảm số lần lặp.
• Thiên vị bán kính lấy mẫu với số mũ âm làm tăng mật độ điểm.
• Thiên vị quá mức phá hủy tính ngẫu nhiên, vì vậy hãy điều chỉnh cẩn thận.
• Các biến thể song song trên GPU như PixelPie cho phép các ứng dụng thời gian thực.