Jak renderować grube linie 2D jako wielokąty?

Question

Mam ścieżkę złożoną z listy punktów 2D. Chcę zamienić je w pasek trójkątów, aby utworzyć teksturowaną linię o określonej grubości (i inne tego typu rzeczy). Zasadniczo lista punktów 2D musi stać się listą wierzchołków określających obrys wieloboku, który w przypadku renderowania renderowałby linię. Problem polega na obsłudze połączeń narożnych, miterów, czapek itp. Powstały wielokąt musi być "idealny" w sensie bez nadmiernego przeciągania, czystych połączeń itp., Aby można było go wytłaczać lub w inny sposób bawić się.

Czy istnieją jakieś proste zasoby o wartości , które mogą zapewnić wgląd algorytmu, kod lub dodatkowe informacje na temat robienia tego w wydajny sposób?

Absolutnie NIE chcę pełnej biblioteki wektorowej 2D (cairo, antigrain, OpenVG itp.) Z krzywymi, łukami, kreskami i wszystkimi dzwonkami i gwizdkami. Kopałem w wielu drzewach źródłowych dla implementacji OpenVG i innych rzeczy, aby znaleźć wgląd, ale to wszystko jest okropnie zawiłe.

Zdecydowanie jestem gotów samemu go zakodować, ale istnieje wiele zdegenerowanych przypadków (małe segmenty + grube szerokości + ostre rogi), które tworzą wszelkiego rodzaju problemy z łączeniem. Nawet niewielka pomoc zaoszczędziłaby mi godzin próbując poradzić sobie z nimi wszystkimi.

EDYCJA: Oto przykład jednego z tych zdegenerowanych przypadków, który powoduje brzydotę, jeśli po prostu przechodzisz od wierzchołka do wierzchołka. Czerwony to oryginalna ścieżka. Pomarańczowe bloki to prostokąty rysowane na określonej szerokości wyrównane i wyśrodkowane na każdym segmencie.

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

Answer 1

No cóż - sam próbowałem rozwiązać ten problem. Zmarnowałem dwa miesiące na rozwiązanie, które próbowało rozwiązać problem z nadmiernym przeciążeniem. Jak już się dowiedziałeś, nie możesz zajmować się wszystkimi zdegenerowanymi sprawami i jednocześnie mieć zero overdraw.

Można jednak używać hybrydowego podejścia:

Napisz sobie rutynę, która sprawdza czy przyłącza może być wykonany z prostej geometrii bez problemów. Aby to zrobić, należy sprawdzić kąt łączenia, szerokość linii i długość połączonych segmentów linii (segmenty linii, które są krótsze niż ich szerokość, są PITA). Przy niektórych heurystyce powinieneś być w stanie uporządkować wszystkie trywialne przypadki.

Nie wiem, jak wyglądają twoje średnie dane linii, ale w moim przypadku ponad 90% szerokich linii nie miało zdegenerowanych przypadków.

Dla wszystkich innych liniach:

pan najprawdopodobniej już okazało się, że jeśli tolerować overdraw, generowanie geometrii jest dużo łatwiejsze. Zrób tak, a niech algorytm wieloboków CSG i algorytm tesselacji wykonają ciężką pracę.

Oceniłem większość dostępnych pakietów tesselation, a skończyłem z tesselatorem GLU. Był szybki, niezawodny, niezniszczalny (w przeciwieństwie do większości innych algorytmów). To było darmowe, a licencja pozwoliła mi włączyć go do komercyjnego programu. Jakość i szybkość tesselation jest w porządku. Nie dostaniesz jakości triangulacji delaunay, ale ponieważ potrzebujesz trójkątów do renderowania, który nie jest problemem.

Ponieważ nie podobało mi się to, że interfejs API tesselator podniósł kod tesselation z darmowej implementacji referencyjnej SGI OpenGL, przepisałem całą partycję front-end i dodałem pule pamięci, aby zmniejszyć liczbę alokacji. Trwało to dwa dni, ale było warto (jak poprawa wydajności piątego czynnika). Rozwiązanie znalazło się w komercyjnej implementacji OpenVG btw :-)

Jeśli renderujesz z OpenGL na komputerze PC, możesz przenieść zadanie tesselation/CSG z CPU na GPU i użyć bufora matrycowego lub sztuczki z-bufora, aby usunąć overdraw. To jest o wiele łatwiejsze i może być nawet szybsze niż tesselacja procesora.

Answer 2

myślę, że dotrzeć do algorytmu teselacji. Prawdą jest, że w większości przypadków, gdy są one używane, celem jest zmniejszenie liczby wierzchołków w celu zoptymalizowania renderowania, ale w twoim przypadku można sparametryzować, aby zachować wszystkie szczegóły - a możliwość optymalizacji może się przydać.

Istnieje wiele algorytmów tesselowania i kodu w Internecie - w parę lat później zawarłem czysty plik DLL w bibliotece DLL do użytku z rendererem krajobrazu Delphi i nie są one rzadkim tematem dla zaawansowanych samouczków kodowania grafiki i tym podobne.

Answer 3

Ja też się tym interesuję, ponieważ chcę udoskonalić rysunek dróg z mapowania aplikacji (Kosmos). Jednym z rozwiązań, których używałem, było dwukrotne narysowanie polilinii, jeden raz grubszą linią, a raz cieńszą, z innym kolorem. Ale to nie jest wielobok, to tylko szybki sposób na symulację. Zobacz kilka przykładów tutaj: http://wiki.openstreetmap.org/wiki/Kosmos_Rendering_Help#Rendering_Options

Nie jestem pewien, czy tego właśnie potrzebujesz.

Answer 4

Sprawdź, czy Delaunay triangulation może pomóc.

Answer 5

Prosta metoda z mojej góry.

Bisect kąt każdego 2d Vertex, to stworzy miłe ukośne linii. Następnie przesuń wzdłuż tej linii, zarówno do wewnątrz, jak i na zewnątrz, ilość twojej "grubości" (lub grubość podzieloną przez dwie?), Teraz masz swoje wewnętrzne i zewnętrzne punkty wielokąta. Przejdź do następnego punktu, powtórz ten sam proces, budując nowe punkty wielokąta po drodze. Następnie zastosuj triangualtion, aby uzyskać gotowe vertexy do renderowania.

Answer 6

W moim przypadku mogłem pozwolić sobie na przekroczenie. Ja po prostu drążę koła o promieniu = szerokość/2 wyśrodkowane na każdym z wierzchołków polilinii.

Artefakty są zamaskowane w ten sposób i bardzo łatwe do zrealizowania, jeśli możesz żyć z "zaokrąglonymi" rogami i nadmiarowaniem.

Answer 7

Wygląda na to, że rysujesz pole wokół segmentów linii z WYPEŁNIENIEM i używanie koloru pomarańczowego. Czyniąc to, na pewno stworzysz złe overdraws. Pierwszą rzeczą do zrobienia nie będzie renderowanie czarnych obramowań, a kolor wypełnienia może być nieprzejrzysty.

Dlaczego nie możesz użyć prymitywu GL_LINES, aby zrobić to, co masz zamiar zrobić? Możesz określić szerokość, filtrowanie, gładkość, cokolwiek teksturę. Możesz renderować wszystkie wierzchołki za pomocą glDrawArrays(). Wiem, że nie jest to coś, o czym myślisz, ale ponieważ koncentrujesz się na rysunku 2D, może to być łatwiejsze podejście. (szukaj Teksturowanych linii itp.)

Answer 8

Skończyło się na tym, że musiałem zabrudzić sobie ręce i napisać małą wstążkę, aby rozwiązać podobny problem.

Dla mnie problemem było to, że chciałem grubych linii w OpenGL, które nie miały rodzajów artefaktów, które widziałem z OpenGL na iPhonie. Po obejrzeniu różnych rozwiązań; Krzywe Beziera i tym podobne - uznałem, że najprościej byłoby po prostu stworzyć własną. Istnieje kilka różnych podejść.

Jednym ze sposobów jest znalezienie kąta przecięcia między dwoma segmentami, a następnie przesuwanie się wzdłuż tej linii przecięcia w pewnej odległości od powierzchni i traktowanie jej jako wierzchołka wstążki. Próbowałem tego i nie wyglądało to intuicyjnie; szerokość wstążki byłaby różna.

Innym podejściem jest faktyczne obliczenie normalnej do powierzchni segmentów linii i wykorzystanie jej do obliczenia idealnej krawędzi taśmy dla tego segmentu i wykonanie rzeczywistych testów przecięcia między segmentami wstążki. To działało dobrze, z wyjątkiem tego, że w przypadku ostrych zakrętów przecięcia segmentów linii wstążkowej były zbyt daleko (jeśli kąt między segmentami zbliżał się do 180 ').

Pracowałem nad kwestią ostrych kątów z dwoma podejściami. Algorytm przecięcia linii Paul Bourke (którego użyłem w sposób niezoptymalizowany) sugerował wykrycie, czy przecięcie znajduje się wewnątrz segmentów. Ponieważ oba segmenty są identyczne, musiałem tylko przetestować jeden z segmentów na skrzyżowanie. Mógłbym wtedy rozstrzygnąć, jak rozwiązać ten problem; albo przez fudowanie najlepszego punktu pomiędzy dwoma końcami, albo przez zakładanie zaślepki - oba podejścia wyglądają dobrze - podejście z nakładką końcową może zrzucić wielokąt przedni/tylny w kolejności zamawiania dla opengl.

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

Zobacz mój kod źródłowy tutaj: https://gist.github.com/1474156

Answer 9

Właśnie znalazłem tę niesamowitą pracę:

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

Wydaje zrobić dokładnie to, co chcesz, a jej licencja zezwala używać go nawet w aplikacjach komercyjnych. Poza tym autor wykonał naprawdę świetną robotę, aby szczegółowo opisać swoją metodę. Pewnie dam mu szansę, żeby zastąpić moją własną, prawie niezupełnie idealną implementację.