Thuật toán chung cho hình ảnh vector rastering

Question

Thuật toán tổng quát của hình ảnh vecto vector là gì? Tôi đã tìm thấy rất nhiều thuật toán rasterizing nguyên thủy như đường, vòng tròn, đường cong Bezier vv Nhưng nói chung, tôi nên làm gì? Đơn giản, đi tìm hình vector trong hình ảnh vector, lấy điểm ảnh của nó và đưa chúng vào hình ảnh raster? Hay cái gì khác?

Và một câu hỏi khác, làm cách nào tôi có thể cải thiện thời gian xử lý bằng cách sử dụng đồng thời? Ví dụ, tôi có thể tách các hình vectơ riêng biệt và đồng thời lấy các pixel của chúng. Nhưng có lẽ có những phương pháp khác để làm điều này?

Answer 1

Thuật toán rasterization chung là, đối với mỗi đa giác trong hình ảnh.

(Một đa giác được định nghĩa là một hoặc nhiều đường cong được làm từ các đoạn thẳng và đường thẳng tham số - trong thực tế bình thường, đây là thứ tự thứ hai (hình nón bậc hai bậc hai) và bậc ba (Bézier spline). được định nghĩa sao cho bên trong luôn ở bên trái, vì đường cong được di chuyển ngang, vì vậy các hình dạng thông thường chạy ngược chiều kim đồng hồ và các lỗ chạy theo chiều kim đồng hồ.)

(i) (chiếu) Chuyển đổi đa giác sang cùng hệ tọa độ như bitmap đích. Độ phân giải không cần giống nhau và hình ảnh chống răng cưa thường lớn hơn: ví dụ: FreeType sử dụng 64 pixel.

(ii) (làm đơn điệu trong Y) Trong trường hợp cần thiết, hãy chia từng đoạn của đa giác thành các phân đoạn nhỏ hơn chạy liên tục lên trên hoặc xuống dưới. Giai đoạn này là cần thiết chỉ cho các đoạn cong, và tương đối dễ dàng khi sử dụng gai Bezier. Phương pháp thông thường là chia đôi liên tục cho đến khi đạt được tính đơn điệu. Hủy tất cả các phân đoạn ngang.

(iii) (đánh dấu giới hạn chạy) Vẽ từng đoạn vào một bitmap tạm thời. Sử dụng thuật toán của Bresenham cho các đường thẳng; cho các đường cong, chia đôi cho đến khi đường thẳng không xa hơn (nói) 1/8 của một điểm ảnh từ đường cong thực, sau đó sử dụng một đường thẳng từ đầu đến cuối. Khi vẽ, đánh dấu các điểm ảnh theo một cách nào đó để chỉ ra (a) cho dù chúng là bắt đầu hay kết thúc chạy - các đường xuống đang bắt đầu và các đường lên trên sẽ kết thúc; (b) phạm vi phủ sóng - phần nhỏ của pixel bên trong hình dạng. Đây là nơi các thuật toán khác nhau trong các chi tiết, và nơi các quy tắc quanh co (non-zero so với even-odd) được phân biệt.

(iv) (quét) Di chuyển bitmap tạm thời, từng hàng. Đối với mỗi hàng, quét từ trái sang phải. Duy trì trạng thái cho biết vị trí hiện tại có ở bên trong hình dạng hay không (ví dụ) thêm số được lưu trữ trong bitmap vào một số được lưu trữ. Trong rasterization đơn sắc đơn giản số này, được viết ở giai đoạn trước, sẽ là +1 khi vượt qua một cạnh vào hình dạng và -1 khi ra khỏi hình dạng. Tích lũy các điểm ảnh trong cùng một trạng thái. Gửi chạy đến mô-đun bản vẽ của bạn: ví dụ, FreeType phát ra chạy bao gồm toạ độ Y, tọa độ X bắt đầu và kết thúc và độ phủ từ 0 đến 255. Mô-đun bản vẽ có thể sử dụng vùng phủ sóng làm giá trị alpha áp dụng cho màu vẽ hiện tại , hoặc như một mặt nạ áp dụng cho một kết cấu.

Ở trên là sự đơn giản hóa quá mức lớn nhưng mang lại ý tưởng chung.

Hầu hết các chương trình mã nguồn mở sử dụng mã rasterization có nguồn gốc từ một trong các dự án sau:

FreeType - một bộ quét phông chữ mà chứa cả mono và anti-aliasing module bộ quét là tương đối dễ dàng để sử dụng độc lập - đó là, cho bất kỳ hình dạng nào, không chỉ cho phông chữ. Tôi đã sử dụng hệ thống này thành công trong một số dự án C++ di động thương mại.

Hệ thống của FreeType được lấy cảm hứng từ số Libart của Raph Levien.

Anti-Grain là một thư viện C++ phổ biến và có ảnh hưởng khác.

Ngoài ra còn có scan-line edge flag system được thực hiện bởi Kiia Kallio, có vẻ đầy hứa hẹn và có vẻ nhanh hơn Anti-Grain.

Hầu hết nhưng không phải tất cả các thư viện này đều chấp nhận hình dạng được làm từ đường tròn Bézier bậc hai và khối cũng như các đoạn thẳng. Những người không (ví dụ: thư viện của K. Kallio) chỉ sử dụng các đa giác thẳng; nhưng nó khá dễ dàng để 'làm phẳng' một đường cong thành một chuỗi các đoạn thẳng gần hơn khoảng cách tối đa mong muốn từ đường cong thực tế. FreeType thực hiện nội bộ và mã của nó có thể được mượn khi cần thiết.