Vẽ đường iso của trường vô hướng 2D ẩn

Question

Tôi có trường vô hướng ẩn được xác định trong 2D, cho mỗi điểm trong 2D tôi có thể tính toán giá trị vô hướng chính xác nhưng tính toán hơi phức tạp.
Tôi muốn vẽ một đường iso của bề mặt đó, nói dòng của giá trị '0'. Chức năng chính nó là liên tục nhưng 'iso' dòng có thể có nhiều trường hợp liên tục và nó không được đảm bảo rằng tất cả chúng được kết nối.
Tính toán giá trị cho mỗi pixel không phải là một tùy chọn vì điều đó sẽ mất quá nhiều thời gian - theo thứ tự vài giây và điều này cần phải là thời gian thực nhất có thể.

Những gì tôi hiện đang sử dụng là một bộ phận đệ quy của không gian có thể được coi là một loại quad-tree. Tôi lấy mẫu ban đầu, rất thô của không gian và nếu tôi tìm thấy một hình vuông chứa chuyển tiếp từ giá trị dương sang âm, tôi đệ quy chia nó thành 4 ô vuông nhỏ hơn và kiểm tra lại, dừng ở mức pixel. Quá trình chuyển đổi dương tính âm được phát hiện bằng cách lấy mẫu một sqaure ở 4 góc của nó. Công việc này khá tốt, trừ khi không. Các đường đẳng đôi được vẽ đôi khi bị cắt vì phát hiện chuyển tiếp không thành công cho các chuyển tiếp xảy ra trong một khu vực nhỏ của cạnh và không vượt qua một góc của hình vuông.

Có cách nào tốt hơn để thực hiện vẽ đường đẳng trong cài đặt này không?

Answer 1

Tôi đã có rất nhiều thành công với các thuật toán được mô tả ở đây http://web.archive.org/web/20140718130446/http://members.bellatlantic.net/~vze2vrva/thesis.html thảo luận về đường cong thích ứng (tương tự như bạn mô tả) và một số vấn đề khác với đường viền nói chung.

Không có cách chung để đảm bảo việc tìm kiếm tất cả các đường nét của một hàm, mà không cần nhìn vào từng điểm ảnh. Có thể có một đường bao khép kín rất nhỏ, trong đó một vùng chỉ có kích thước của một điểm ảnh mà hàm này là dương, trong một vùng mà hàm này nói chung là âm. Trừ khi bạn lấy mẫu đủ mịn để bạn đặt một mẫu bên trong khu vực tích cực, không có cách chung nào để biết rằng nó ở đó.

Nếu chức năng của bạn đủ mịn, bạn có thể đoán được những đường bao khép kín nhỏ nằm ở đâu, vì mô đun của hàm nhỏ trong một vùng xung quanh. Việc lấy mẫu chỉ có thể được tinh chế ở những vùng này.