Làm cách nào để hiển thị các đường 2D dày như đa giác?

Question

Tôi có một đường dẫn được tạo thành từ danh sách các điểm 2D. Tôi muốn biến chúng thành một dải hình tam giác để hiển thị một đường kết cấu với độ dày được chỉ định (và các thứ khác). Vì vậy, về cơ bản danh sách các điểm 2D cần phải trở thành một danh sách các đỉnh xác định đường viền của đa giác nếu kết xuất sẽ hiển thị dòng. Vấn đề là xử lý các góc tham gia, miters, mũ vv Các đa giác kết quả cần phải được "hoàn hảo" trong ý nghĩa của không overdraw, sạch tham gia, vv để nó có thể có thể được ép đùn hoặc nếu không toyed với.

Có bất kỳ tài nguyên đơn giản nào xung quanh có thể cung cấp thông tin chi tiết về thuật toán, mã hoặc bất kỳ thông tin nào khác về cách thực hiện điều này một cách hiệu quả không?

Tôi hoàn toàn KHÔNG muốn thư viện vector 2D đầy đủ (cairo, antigrain, OpenVG, v.v.) với các đường cong, cung, dấu gạch ngang và tất cả các chuông và còi. Tôi đã đào sâu trong nhiều cây nguồn để triển khai OpenVG và những thứ khác để tìm thấy một số thông tin chi tiết, nhưng tất cả đều phức tạp khủng khiếp.

Tôi chắc chắn sẵn sàng tự viết mã, nhưng có nhiều trường hợp suy thoái (phân đoạn nhỏ + chiều rộng dày + góc nhọn) tạo ra tất cả các loại sự cố tham gia. Ngay cả một chút giúp đỡ cũng giúp tôi tiết kiệm được hàng giờ cố gắng đối phó với tất cả.

EDIT: Đây là một ví dụ về một trong những trường hợp thoái hóa gây ra sự xấu nếu bạn chỉ đơn giản là đi từ đỉnh đến đỉnh. Màu đỏ là đường dẫn ban đầu. Các khối màu cam là hình chữ nhật được vẽ theo chiều rộng được chỉ định căn chỉnh và căn giữa trên mỗi đoạn.

http://www.freeimagehosting.net/uploads/52dc639727.png

Answer 1

Oh well - Tôi đã cố tự mình giải quyết vấn đề đó. Tôi lãng phí hai tháng trên một giải pháp đã cố gắng để giải quyết vấn đề overdraw zero. Như bạn đã phát hiện ra, bạn không thể đối phó với tất cả các trường hợp bị thoái hóa và không được rút quá mức cùng một lúc.

Bạn tuy nhiên có thể sử dụng một phương pháp lai:

Viết cho mình một thói quen để kiểm tra nếu tham gia có thể được xây dựng từ hình học đơn giản mà không vấn đề. Để làm như vậy bạn phải kiểm tra góc kết nối, chiều rộng của đường thẳng và độ dài của các đoạn đường nối (các đoạn thẳng ngắn hơn chiều rộng của chúng là một PITA). Với một số chẩn đoán, bạn sẽ có thể phân loại tất cả các trường hợp tầm thường.

Tôi không biết dòng dữ liệu trung bình của bạn trông như thế nào, nhưng trong trường hợp của tôi, hơn 90% số dòng rộng không có trường hợp bị thoái hóa.

Đối với tất cả các dòng khác:

Bạn đã có lẽ hầu hết đã phát hiện ra rằng nếu bạn dung túng viết chi phiếu quá, tạo ra các hình học là dễ dàng hơn nhiều. Làm như vậy, và để cho một thuật toán CSG đa giác và một thuật toán tesselation làm công việc khó khăn.

Tôi đã đánh giá hầu hết các gói tesselation có sẵn và tôi đã kết thúc bằng tesselator GLU. Nó nhanh, mạnh mẽ, không bao giờ bị rơi (không giống như hầu hết các thuật toán khác). Nó hoàn toàn miễn phí và giấy phép cho phép tôi đưa nó vào một chương trình thương mại. Chất lượng và tốc độ của tesselation là okay. Bạn sẽ không nhận được chất lượng tam giác tối ưu, nhưng vì bạn chỉ cần hình tam giác để hiển thị đó không phải là vấn đề.

Vì tôi không thích API tesselator, tôi đã dỡ mã tesselation khỏi triển khai tham chiếu SGI OpenGL miễn phí, viết lại toàn bộ front-end và thêm các vùng bộ nhớ để nhận số lượng phân bổ xuống. Phải mất hai ngày để làm điều này, nhưng nó cũng có giá trị nó (như yếu tố năm cải thiện hiệu suất). Các giải pháp đã kết thúc trong một triển khai OpenVG thương mại btw :-)

Nếu bạn đang kết xuất với OpenGL trên PC, bạn có thể di chuyển tesselation/CSG-job từ CPU sang GPU và sử dụng bộ đệm stencil hoặc thủ thuật z-buffer để loại bỏ việc rút tiền. Đó là dễ dàng hơn rất nhiều và thậm chí có thể nhanh hơn so với tesselation CPU.

Answer 2

Tôi nghĩ rằng tôi sẽ tiếp cận với thuật toán tessellation. Đúng là trong hầu hết trường hợp, chúng được sử dụng nhằm giảm số lượng đỉnh để tối ưu hóa hiển thị, nhưng trong trường hợp của bạn, bạn có thể tham số để giữ lại tất cả chi tiết - và khả năng tối ưu hóa có thể hữu ích.

Có rất nhiều thuật toán tessellation và mã xung quanh trên web - tôi gói gọn một C thuần túy trong một DLL một vài năm trước để sử dụng với trình kết xuất khung cảnh Delphi và chúng không phải là chủ đề phổ biến cho các hướng dẫn mã hóa đồ họa tiên tiến và những thứ tương tự.

Answer 3

Tôi cũng quan tâm đến điều này vì tôi muốn hoàn thiện bản vẽ của các ứng dụng ánh xạ (Kosmos) của đường. Một cách giải quyết khác mà tôi sử dụng là vẽ polyline hai lần, một lần với một đường kẻ dày hơn và một lần với một đường mảnh hơn, với màu khác. Nhưng đây không thực sự là một đa giác, nó chỉ là một cách nhanh chóng để mô phỏng một. Xem một số mẫu tại đây: http://wiki.openstreetmap.org/wiki/Kosmos_Rendering_Help#Rendering_Options

Tôi không chắc đây có phải là thứ bạn cần hay không.

Answer 4

Xem liệu Delaunay triangulation có thể trợ giúp không.

Answer 5

Một phương pháp đơn giản nằm ngoài đầu của tôi.

Bẻ góc của mỗi đỉnh 2d, điều này sẽ tạo ra một đường kẻ sọc đẹp. Sau đó di chuyển dọc theo dòng đó, cả trong và ngoài, số lượng "độ dày" của bạn (hoặc độ dày chia cho hai?), Bây giờ bạn có các điểm đa giác bên trong và bên ngoài của bạn. Di chuyển đến điểm tiếp theo, lặp lại quá trình tương tự, xây dựng các điểm đa giác mới của bạn trên đường đi. Sau đó, áp dụng một triangualtion để có được các vertex render sẵn sàng của bạn.

Answer 6

Trong trường hợp của tôi, tôi có thể đủ khả năng để rút tiền. Tôi chỉ drow vòng tròn với radius = width/2 tập trung vào mỗi đỉnh của polyline.

Hiện vật được đeo mặt nạ theo cách này và rất dễ thực hiện, nếu bạn có thể sống với các góc "tròn" và một số quá mức.

Answer 7

Từ hình ảnh của bạn, có vẻ như bạn đang vẽ hộp quanh các đoạn đường có FILL và sử dụng màu cam. Làm như vậy là sẽ tạo ra overdraws xấu cho chắc chắn. Vì vậy, điều đầu tiên cần làm sẽ không làm cho viền màu đen và màu tô có thể mờ đục.

Tại sao bạn không thể sử dụng GL_LINES nguyên thủy để làm những gì bạn định làm? Bạn có thể chỉ định chiều rộng, lọc, mượt mà, kết cấu bất cứ thứ gì. Bạn có thể hiển thị tất cả các đỉnh bằng cách sử dụng glDrawArrays(). Tôi biết đây không phải là điều bạn có trong tâm trí nhưng vì bạn đang tập trung vào bản vẽ 2D, đây có thể là cách tiếp cận dễ dàng hơn. (tìm kiếm các dòng đã kết cấu, v.v.)

Answer 8

Tôi đã bị bẩn tay và viết một dải băng nhỏ để giải quyết vấn đề tương tự.

Đối với tôi vấn đề là tôi muốn các dòng chất béo trong OpenGL không có các loại hiện vật mà tôi đã thấy với OpenGL trên iPhone. Sau khi xem xét các giải pháp khác nhau; đường cong bezier và những thứ tương tự - tôi quyết định có lẽ là dễ nhất để tự làm. Có một vài cách tiếp cận khác nhau.

Một cách tiếp cận là tìm góc giao nhau giữa hai đoạn và sau đó di chuyển dọc theo đường giao nhau đó một khoảng cách nhất định ra khỏi bề mặt và coi đó là đỉnh băng. Tôi đã thử nó và nó không nhìn trực quan; chiều rộng băng sẽ thay đổi.

Cách tiếp cận khác là tính toán bình thường với bề mặt của đoạn đường và sử dụng tính toán mép băng lý tưởng cho phân khúc đó và thực hiện kiểm tra giao điểm thực tế giữa các đoạn băng. Điều này làm việc tốt ngoại trừ cho các góc sắc nét các đoạn đường giao nhau dải băng quá xa (nếu góc liên đoạn tiếp cận 180 ').

Tôi đã giải quyết vấn đề góc sắc nét với hai cách tiếp cận. Thuật toán giao cắt đường Paul Bourke (mà tôi đã sử dụng theo cách chưa được tối ưu hóa) đề xuất phát hiện xem giao lộ có nằm trong các phân đoạn hay không. Vì cả hai phân đoạn đều giống nhau nên tôi chỉ cần kiểm tra một trong các phân đoạn cho giao lộ. Sau đó tôi có thể phân xử cách giải quyết vấn đề này; hoặc bằng cách fudging một điểm tốt nhất giữa hai đầu hoặc bằng cách đặt trên một nắp kết thúc - cả hai cách tiếp cận nhìn tốt - phương pháp tiếp cận nắp kết thúc có thể ném ra phía trước đa giác/quay trở lại đặt hàng cho opengl.

Xem http://paulbourke.net/geometry/lineline2d/

Xem mã nguồn của tôi ở đây: https://gist.github.com/1474156

Answer 9

Tôi chỉ tìm thấy công việc tuyệt vời này:

http://www.codeproject.com/Articles/226569/Drawing-polylines-by-tessellation

Có vẻ như để làm chính xác những gì bạn muốn, và giấy phép cho phép để sử dụng ngay cả trong các ứng dụng thương mại. Thêm vào đó, tác giả đã làm một công việc thực sự tuyệt vời để trình bày chi tiết phương pháp của mình. Tôi có lẽ sẽ cho nó một shot tại một số điểm để thay thế thực hiện không gần như hoàn hảo của riêng tôi.