Câu hỏi thuật toán phổ biến

Question

Giả sử chúng ta có một số lưới (xem hình minh họa từ CorelDraw, sử dụng cùng kỹ thuật trong "Lưới điền" cụ).

alt text http://www.sonic.net/mnitepub/pccafe/reviews/coreldraw9/meshfill.jpg

Rõ ràng loại lưới được thể hiện bằng một tập hợp các điểm và ranh giới giữa họ đang thực sự xác định sử dụng rằng tập hợp các điểm (có thể bằng cách nào đó nội suy). Công cụ này cũng có các nút để tăng độ phân giải lưới.

Câu hỏi của tôi là như sau - những thứ như thế được tính như thế nào? Giả sử tôi có một số điểm mà thực sự đại diện cho một lưới (đối với trường hợp dễ dàng, ngay cả giả sử, rằng điểm trên "biên giới" là tĩnh và không thể di chuyển). Và tôi muốn tăng độ phân giải lưới, ví dụ, trong 4 lần (để số điểm lưới thực sự trở thành 4 * initial_points_count).

Tôi nên tính toán vị trí của các điểm mới như thế nào nếu dữ liệu duy nhất tôi có là ma trận điểm ban đầu?

Phương pháp nhanh nhất (thậm chí gần đúng) phù hợp với tôi, nhưng tôi không biết tìm kiếm ở đâu hoặc cách phát triển loại thuật toán như vậy.

Cảm ơn bạn.

Answer 1

Tôi sẽ bắt đầu bằng cách thêm điểm nửa chừng trên tất cả các dòng bằng cách nội suy (các đường cong trong hình minh họa là rất có thể là Bézier curves của một số loại, vì vậy tôi sẽ nội suy chúng như vậy, hoặc sử dụng nội suy hai chiều như Mau đề xuất) và đặt các điểm mới giữa những cái cũ, cho tôi gấp 3 lần độ phân giải. Sau đó tôi sẽ nội suy giữa các điểm mới này (cả hai cách nếu độ chính xác là khóa) và đặt một điểm mới tại giao lộ (hoặc nửa chừng). Xem "hình minh họa" bên dưới.

Initial state => Interpolate => Place points => Interpolate => Final state 
    x  x   x-------x  x x x   x x x  x x x 
        |  |        |  
        |  |  x  x   x---+---x  x x x 
        |  |        | 
    x  x   x-------x  x x x   x x x  x x x 

Answer 2

Âm thanh như một công việc cho Bilinear Interpolation (trong đó hệ tọa độ trên bề mặt hình cầu).

Answer 3

Bạn đã xem subdivision chưa? Nên làm việc để tinh chỉnh mắt lưới như thế.

Answer 4

Điều bạn đang tìm kiếm là thuật toán lưới mịn. Rất tiếc, tôi không có bất kỳ tài nguyên nào có sẵn, vì vậy tôi chỉ có thể đề xuất với google về "làm mịn lưới". Đó là một lĩnh vực rất lớn.

EDIT

Đây là một tốt đẹp, ngắn, roundup của một vài phương pháp/thuật toán để đạt được lưới mịn: http://www.mpi-inf.mpg.de/~ag4-gm/handouts/06gm_surf3.pdf

Answer 5

Các bình luận về câu trả lời hiện:

Dường như với tôi rằng Mau và câu trả lời martient của mô tả một giải pháp cho vấn đề của xấp xỉ một hình thức được biết đến với polygon mesh (và bạn không có một hình thức được biết đến) .

Thuật toán mà Dave đề cập sẽ mịn bất kỳ hình thức nào, nhưng không nhất thiết phải theo cách dự định.

Nếu bạn nhìn vào câu trả lời của Bạn, bạn sẽ thấy rằng các điểm mới đến từ nội suy tuyến tính giữa các điểm và nếu đủ tốt cho tất cả các giải pháp có thể so sánh (trừ Dave).

Sự gia tăng mật độ lưới như vậy sẽ không làm cho lưới kết quả trông đẹp hơn - giống với hình thức ban đầu hơn. Nếu điều đó không đủ tốt thì trước tiên bạn phải quyết định hình dạng/hình dạng thực tế mà bạn đang cố gắng đại diện với lưới (nếu bạn có thể mở rộng trên ví dụ của bạn có thể rõ ràng hơn một chút), công cụ này chỉ tạo ra các vòng tròn hoặc nó có thể mất bất kỳ hình dạng và 'lưới điền' nó?). Ngoài ra, bạn sẽ nhận thấy rằng bạn không làm việc với một lưới đa giác, nhưng với lưới đường cong (có lẽ là bezier), đó là một lý do khác tại sao một số câu trả lời sẽ không trực tiếp áp dụng cho vấn đề của bạn.

EDIT: Sau khi xem xét kỹ hơn về cách corel thực hiện điều này và giả định rằng bạn thực sự biết các đường cong không chỉ là điểm (!):

• Bạn bắt đầu với bộ các đường cong, và có vẻ như với tôi rằng bạn có các đường cong ngang và dọc để bắt đầu với
• Nếu bạn muốn tăng độ phân giải (ví dụ như độ phân giải ngang), bạn có thể lấy hai đường thẳng dọc liên tiếp và chia từng đoạn đường cong ngang mà chúng đi qua tại do đó tạo ra một thiết lập các điểm xác định đường cong mới; bạn cũng có thể suy góc mà tại đó các đường cong đi qua điểm

alt text http://img706.imageshack.us/img706/5693/path5818.png

The (bằng tay vẽ) hình ảnh trên cho thấy cố gắng để minh họa a) thêm của đường cong mới (màu đỏ) mà bạn sẽ tạo ra theo cách này. b) thêm polyline nội suy tuyến tính (màu xanh), mà đi nhiều hơn đối với cách tiếp cận lưới đa giác (do đó bạn có thể đánh giá nếu đó là có thể chấp nhận cho bạn)

Note: Tùy thuộc vào các thuật toán mà bạn đang chuẩn bị lưới bạn có thể hoặc có thể không có bất kỳ lợi ích nào trong việc xem xét các đường lưới là đường cong (sự khác biệt giữa các giải pháp màu đỏ và xanh có thể không đáng kể đối với thuật toán nhất định và quan trọng đối với thuật toán khác). Nếu thuật toán chỉ đơn giản là mong đợi các điểm sau đó bạn cũng nên xem xét làm thế nào để gần đúng đường cong bezier với các điểm (đọc qua this có thể giúp đỡ, mặc dù bạn không cần độ chính xác pixel).

Để có độ chính xác cao nhất/kết quả tốt nhất, trước tiên bạn nên tăng mật độ đường cong và ước tính chúng bằng đường kẻ.