Phương pháp Voronoi tốc độ cao cho OpenSCAD

Lấy cảm hứng từ OpenSCAD Voronoi Generator của Felipe Sanches.

Có hai tệp .scad được cung cấp:

• fastvoronoi.scad có thể được sử dụng độc lập mà không cần thư viện nào khác.
• fastvoronoi_func_bosl2.scad dùng cho BOSL2. Nó cung cấp phiên bản hàm của fastvoronoi để trả về các mảng điểm (vertices), dùng với các thao tác của BOSL2 như offset_sweep() để bo tròn cạnh. Việc xử lý mọi thứ bằng mảng đỉnh thay vì các đối tượng nội tại của OpenSCAD sẽ chậm hơn đáng kể nhưng hữu ích cho các hiệu ứng phức tạp.

Kết quả kiểm tra (Benchmark)

Thử nghiệm với 400 tâm điểm. Thời gian là mức trung bình xấp xỉ từ nhiều lần chạy. Fastvoronoi nhanh hơn khoảng 12 lần.

Thời gian Voronoi bao gồm 0.27 giây khởi tạo mảng:

• fastvoronoi() = 1.3 giây
• Voronoi gốc dùng offset() thay vì minkowski() = ~16 giây
• Voronoi gốc của Felipe Sanches (dùng minkowski) = ~16 giây

Cách sử dụng fastvoronoi.scad

use <fastvoronoi.scad>

// hiển thị họa tiết voronoi nhanh với các ô có kích thước trung bình là 'cellsize',
// trong một hình chữ nhật giới hạn bởi [xmin,ymin], [xmax,ymax] với
// độ dày 'thickness' và bán kính góc 'rcorner' giữa các ranh giới

random_voronoi(cellsize, [xmin], [xmax], [ymin], [ymax], [thickness], [rcorner], [$fn]);

Module random_voronoi() ở trên thực hiện các bước sau, bạn có thể tách rời chúng:

// 1. Tạo một mảng các điểm ngẫu nhiên tương thích với fast voronoi
points = voronoi_array(cellsize, [xmin], [xmax], [ymin], [ymax], [allowable], [seed]);

// 2. hiển thị họa tiết voronoi
fastvoronoi(points, cellsize, [thickness], [rcorner]);

Sau đó, bạn có thể dùng linear_extrude() trên kết quả đầu ra của fastvoronoi() để tạo độ dày cho họa tiết.

Cách sử dụng fastvoronoi_func_bosl2.scad

// phải dùng "include" thay vì "use"!
include <fastvoronoi_func_bosl2.scad> // bao gồm các thư viện BOSL2 tiêu chuẩn và bo tròn 

// 1. Tạo một mảng các điểm ngẫu nhiên tương thích với fast voronoi
points = voronoi_array(cellsize, [xmin], [xmax], [ymin], [ymax], [allowable], [seed]);

// 2. Tạo mảng các đỉnh đa giác cho họa tiết voronoi
polygon_vertices = fastvoronoi(points, cellsize, [thickness], [rcorner]);

Hàm hỗ trợ voronoi_array() (từ fastvoronoi.scad) tạo ra một mảng các vị trí tâm ngẫu nhiên sao cho mỗi ô lưới chứa một tâm, đây là điều cần thiết để fastvoronoi() hoạt động.

Hàm fastvoronoi() tạo ra một mảng các đỉnh đa giác 2D. Mỗi đa giác có thể được render riêng lẻ bằng linear_extrude() và polygon(), hoặc dùng các hàm BOSL2 như offset_sweep() để đùn khối với các cạnh được bo tròn.

Cải thiện tốc độ

Thuật toán Voronoi ban đầu yêu cầu N^2 thao tác intersection(), rất chậm. Ví dụ, tạo 400 ô Voronoi cần 160,000 (400^2) phép giao.

Ngược lại, phương pháp fastvoronoi này chỉ cần 24*N phép giao mỗi ô (trung bình). Do đó, 400 tâm điểm chỉ cần khoảng 9,600 phép giao, tức là chỉ 6% so với bản gốc! Hơn nữa, thời gian thực thi tăng tuyến tính theo số lượng điểm thay vì theo cấp số mũ.

Nó hoạt động như thế nào?

Chúng tôi tạo ra một mảng các tâm điểm nằm ngẫu nhiên trên lưới, sao cho mỗi ô vuông lưới chứa chính xác một tâm. Tâm có thể nằm bất cứ đâu trong ô vuông đó (và có thể bị giới hạn thêm bởi tham số allowable). Sự sắp xếp này vẫn trông ngẫu nhiên nhưng đảm bảo mỗi ô Voronoi được tạo thành từ các tâm cách nhau không quá hai ô lưới. Do đó, để tạo bất kỳ ô Voronoi nào quanh một tâm cho trước, ta có thể bỏ qua các tâm cách xa khoảng cách này.

Vì mỗi ô vuông lưới (trừ các ô ở cạnh và góc) có 8 ô vuông khác xung quanh, tâm trong một ô nhất định không bao giờ cách xa quá hai ô theo đường chéo so với bất kỳ tâm nào khác. Vì hai tâm có thể cách nhau hai ô, chúng ta không cần quá 24 phép giao để tính toán hình dạng ô Voronoi cho một tâm nhất định (hai vòng ô đồng tâm quanh tâm, vòng trong là 8 ô và vòng tiếp theo là 16 ô).