Algorytm przycinania odcinkaj do okna
Sebastian Biały
Mam wydawało by się trywialny problem:
Musze narysowac odcinek która nie mieści się w obszarze wyswietlacza
rastrowego. Powiedzmy, ze mam 1-bitowy kolor a jeden z punktów odcinka
leży poza oknem wyświetlania. Oczywiście używam jakiegoś algorytmu, np.
Cohena-Sutherlanda czy cokololwiek innego co daje w wyniku punkty na
krawedziach okna po przycięciu odcinka.
Większośc osób powie w tym wypadku "ok, to wiemy wszystko".
Ale ja mam taki problem, że przecież odcinek może przeciąć krawędź okna
w miejscu, które matematycznie wypada _pomiedzy_ pikselami. oznacza to
że musze teraz zaokraglić w gore lub w dół do najbliższego piksela i z
tego miejsca rozpocząć rysowanie odcinka standardowymi algorytmami.
No wlasnie: narysowanie odcinka bez obcięcia przebiega przez inne
piksele niż narysowanie odcinka dociętego do okna. Ze względu na
zaokraglenia punktów przecięcia do pełnych pikseli.
Czy ktos może wie czy jest jakieś rozsadne rozwiązanie tego problemu?
Oglądam sobie pare implementacji tu i tam i widzę, że autorzy po prostu
olewaja ten problem zakładając, że tych drobnych niedokładności i tak
nikt nie zobaczy. Ale zanim tez przyjme taką koncepcję wole zapytać co
poczytać i gdzie aby mieć lepszy wgląd w problem.
Tak naprawde wydaje mi się, że powinienem posiadac w tym wypadku
algorytm Bresenhama ktory startuje nie od piksela tylko z prawidlowo
ustalonymi przyrostami. Ale nie potrafie znaleźć implementacji tego typu
więc nie mam pewności czy to prawidłowa droga.
Dariusz Zolna
> Tak naprawde wydaje mi się, że powinienem posiadac w tym wypadku
> algorytm Bresenhama ktory startuje nie od piksela tylko z prawidlowo
> ustalonymi przyrostami. Ale nie potrafie znaleźć implementacji tego typu
> więc nie mam pewności czy to prawidłowa droga.
Dokładnie tak ja bym to zrobił. Bresenham (bo i tak pewnie będziesz go
używał do rysowania linii), a jak już go zaimplementujesz, to łatwo
zrobisz przycinanie do prostokąta.
Dariusz Żołna
Sebastian Biały
>> Tak naprawde wydaje mi si�, �e powinienem posiadac w tym wypadku
>> typu wi�c nie mam pewno�ci czy to prawid�owa droga.
> Dok�adnie tak ja bym to zrobi�.
Wobec tego pytanie: czy jest mo�liwe w czasie O(1) (w sensie niezale�nym
od k) wyliczenie wszelkich zmiennych decyzyjnych algorytmu Bresenham dla
k-tego kroku ? Zak�adam �e k jest odleglo�ci� pionow�|poziom� punktu
startu do kraw�dzi od kt�rej zaczynam rysowanie. Wydaje mi si�, �e tak,
ale niech ktoďż˝ potwierdzi.
Wojciech Muła
> Wobec tego pytanie: czy jest możliwe w czasie O(1) (w sensie niezależnym
> od k) wyliczenie wszelkich zmiennych decyzyjnych algorytmu Bresenham dla
> k-tego kroku ? Zakładam że k jest odleglością pionową|poziomą punktu
> startu do krawędzi od której zaczynam rysowanie. Wydaje mi się, że tak,
> ale niech ktoś potwierdzi.
Od strony 10 masz zarys rozwiązania:
http://alamos.math.arizona.edu/~rychlik/CourseDir/535/resources/Lec02_Bresenham.pdf
We "Wprowadzeniu do grafiki komputerowej" Foleya (wyd. polskie) jest
też odrobina informacji.
w.
Mateusz Loskot
> Ale ja mam taki problem, że przecież odcinek może przeciąć krawędź okna
> w miejscu, które matematycznie wypada _pomiedzy_ pikselami. oznacza to
> że musze teraz zaokraglić w gore lub w dół do najbliższego piksela i z
> tego miejsca rozpocząć rysowanie odcinka standardowymi algorytmami.
>
> No wlasnie: narysowanie odcinka bez obcięcia przebiega przez inne
> piksele niż narysowanie odcinka dociętego do okna. Ze względu na
> zaokraglenia punktów przecięcia do pełnych pikseli.
Tak, jest to podstawowy problem przy tego typu rasteryzacji.
> Czy ktos może wie czy jest jakieś rozsadne rozwiązanie tego problemu?
> Oglądam sobie pare implementacji tu i tam i widzę, że autorzy po prostu
> olewaja ten problem zakładając, że tych drobnych niedokładności i tak
> nikt nie zobaczy.
Potwierdzam, że też w większości implementacji jakie widziałem
błąd pomiędzy matematycznym segmentem/pikselem a faktycznie rysowanym
jest po prostu ignorowany.
> Ale zanim tez przyjme taką koncepcję wole zapytać co
> poczytać i gdzie aby mieć lepszy wgląd w problem.
http://portal.acm.org/citation.cfm?id=607963
oraz podana tam referencja do
Steven Eker, Faster linear interpolation, Graphics gems IV
oraz niepodana do
Steven Eker "Faster Pixel-Perfect Line Clipping" z Graphics gems V
Ten ostatni tekst podaje rozwiązanie dokładnie problemu o który pytasz,
klip linia/prostokąt w miejscy pomiędzy pixelami.
> Tak naprawde wydaje mi się, że powinienem posiadac w tym wypadku
> algorytm Bresenhama ktory startuje nie od piksela tylko z prawidlowo
> ustalonymi przyrostami. Ale nie potrafie znaleźć implementacji tego typu
> więc nie mam pewności czy to prawidłowa droga.
AFAICT, jest prawidłowa, tzn. startujesz z x i określasz y na podstawie
wcześniej wyznaczonego nachylenia.
Pozdrawiam
--
Mateusz Loskot, http://mateusz.loskot.net
Charter Member of OSGeo, http://osgeo.org
Sebastian Biały
> http://portal.acm.org/citation.cfm?id=607963
"32-bit fixed-point arithmetic; 16 bits for the integer and 16 bits for
the decimal part"
Tak sobie pomyślałem, ze gdyby uzyć standardowego algorytmu rysowania
linii, tylko wartości X,Y oraz wszelkie zmienne decyzyjne pomnozyć przez
dużą liczbe można by ten bład zredukować, bo zaokraglenie bedzie wtedy
do ułamka piksela.
> Steven Eker "Faster Pixel-Perfect Line Clipping" z Graphics gems V
> Ten ostatni tekst podaje rozwiązanie dokładnie problemu o który pytasz,
> klip linia/prostokąt w miejscy pomiędzy pixelami.
OK. Sprawdzę.