eGospodarka.pl
eGospodarka.pl poleca

eGospodarka.plGrupypl.comp.programmingAlgorytm przycinania odcinkaj do okna
Ilość wypowiedzi w tym wątku: 6

  • 1. Data: 2009-11-14 22:01:14
    Temat: Algorytm przycinania odcinkaj do okna
    Od: Sebastian Biały <h...@p...onet.pl>

    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.


  • 2. Data: 2009-11-14 22:21:02
    Temat: Re: Algorytm przycinania odcinkaj do okna
    Od: Dariusz Zolna <a...@u...com>

    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


  • 3. Data: 2009-11-14 22:34:56
    Temat: Re: Algorytm przycinania odcinkaj do okna
    Od: Sebastian Biały <h...@p...onet.pl>

    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.


  • 4. Data: 2009-11-15 00:39:46
    Temat: Re: Algorytm przycinania odcinkaj do okna
    Od: Wojciech Muła <w...@p...null.onet.pl.invalid>

    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.


  • 5. Data: 2009-11-15 02:32:31
    Temat: Re: Algorytm przycinania odcinkaj do okna
    Od: Mateusz Loskot <s...@s...net>

    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


  • 6. Data: 2009-11-15 12:45:24
    Temat: Re: Algorytm przycinania odcinkaj do okna
    Od: Sebastian Biały <h...@p...onet.pl>

    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ę.

strony : [ 1 ]


Szukaj w grupach

Szukaj w grupach

Eksperci egospodarka.pl

1 1 1

Wpisz nazwę miasta, dla którego chcesz znaleźć jednostkę ZUS.

Wzory dokumentów

Bezpłatne wzory dokumentów i formularzy.
Wyszukaj i pobierz za darmo: