Witam.

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.

do góry

Sebastian Biały pisze:
> 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

do góry

Dariusz Zolna wrote:
>> 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ł.

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.

do góry

Sebastian Biały <h...@p...onet.pl> wrote:

> 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/53
5/resources/Lec02_Bresenham.pdf

We "Wprowadzeniu do grafiki komputerowej" Foleya (wyd. polskie) jest
też odrobina informacji.

w.

do góry

Sebastian Biały wrote:
> 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

do góry

Mateusz Loskot wrote:
> 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ę.

do góry