Keskustelu: Koodit: C: Bresenhamin ympyrä

peki [29.01.2005 20:56:18]

Erittäin nopea algoritmi ympyrän piirtämiseen ilman trigonometriaa.
Lisää voit lukea täältä:
http://www.funducode.com/freec/graphics/graphics2.htm
Muista linkata mukaan SDL.lib ja SDLMain.lib.

#include <stdlib.h>
#include "SDL.h"

enum {
  SCREENWIDTH = 640,
  SCREENHEIGHT = 480,
  SCREENBPP = 32,
  SCREENFLAGS = SDL_ANYFORMAT
};

void DrawScene(SDL_Surface* surface)
{
    if ( SDL_MUSTLOCK(surface) ) {
        if ( SDL_LockSurface(surface) < 0 ) {
            fprintf(stderr, "Can't lock the screen: %s\n", SDL_GetError());
            return;
        }
    }

    int x = 200; // koordinaatit
    int y = 200;
    int r = 100; // säde

    int x1 = 0; // sisäisiä koordinaatteja
    int y1 = r;
    int pe = 3 - 2 * r;

    Uint8 *p = (Uint8 *)surface->pixels;
    while (x1 < y1)
    {
            // piirrä segmentti
            *(Uint32 *)(p + (y + y1) * surface->pitch + ((x + x1) << 2)) = 255;
            *(Uint32 *)(p + (y + y1) * surface->pitch + ((x - x1) << 2)) = 255;
            *(Uint32 *)(p + (y - y1) * surface->pitch + ((x + x1) << 2)) = 255;
            *(Uint32 *)(p + (y - y1) * surface->pitch + ((x - x1) << 2)) = 255;
            *(Uint32 *)(p + (y + x1) * surface->pitch + ((x + y1) << 2)) = 255;
            *(Uint32 *)(p + (y - x1) * surface->pitch + ((x + y1) << 2)) = 255;
            *(Uint32 *)(p + (y + x1) * surface->pitch + ((x - y1) << 2)) = 255;
            *(Uint32 *)(p + (y - x1) * surface->pitch + ((x - y1) << 2)) = 255;

             // korjaa sijaintia
            if (pe < 0)
                pe += 4 * x1 + 6;
            else
            {
                pe += 4 * (x1 - y1) + 10;
                y1 -= 1;
            }
            x1 += 1;
    }
    if (x1 == y1)
    {
        *(Uint32 *)(p + (y + y1) * surface->pitch + ((x + x1) << 2)) = 255;
        *(Uint32 *)(p + (y + y1) * surface->pitch + ((x - x1) << 2)) = 255;
        *(Uint32 *)(p + (y - y1) * surface->pitch + ((x + x1) << 2)) = 255;
        *(Uint32 *)(p + (y - y1) * surface->pitch + ((x - x1) << 2)) = 255;
        *(Uint32 *)(p + (y + x1) * surface->pitch + ((x + y1) << 2)) = 255;
        *(Uint32 *)(p + (y + x1) * surface->pitch + ((x - y1) << 2)) = 255;
        *(Uint32 *)(p + (y - x1) * surface->pitch + ((x + y1) << 2)) = 255;
        *(Uint32 *)(p + (y - x1) * surface->pitch + ((x - y1) << 2)) = 255;
    }
    // poistetaan lukitus
    if ( SDL_MUSTLOCK(surface) ) {
        SDL_UnlockSurface(surface);
    }

    //päivitä pinta
    SDL_UpdateRect(surface, 0, 0, 0, 0);
}

int main(int argc, char* argv[])
{
  //Alusta SDL
  SDL_Init(SDL_INIT_VIDEO);

  //Aseta exit funktio
  atexit(SDL_Quit);

  //luo ikkuna
  SDL_Surface* pSurface = SDL_SetVideoMode ( SCREENWIDTH, SCREENHEIGHT, SCREENBPP, SCREENFLAGS );

  SDL_Event event;

  for (;;)
  {
    if ( SDL_PollEvent ( &event ) )
    {
      if ( event.type == SDL_QUIT ) break;
    }
    DrawScene(pSurface);
  }

  SDL_FreeSurface(pSurface);

  return(0);
}

tejeez [30.01.2005 20:55:00]

MISSÄS Se NELIöJUUri on ;DDdd

peki [30.01.2005 20:58:00]

Voit sen kotitehtävänä itse lisätä sopivaan kohtaan. ;)

tn [30.01.2005 21:44:19]

Jep, tuo on hyvä ja yksinkertainen algoritmi ilman mitään raskaita laskutoimituksia. On ollut itselläni jo jonkin aikaa käytössä.
Mutta onkos kukaan sattunut löytämään mitään samanlaista tapaa missä tahansa asennossa olevan ellipsin piirtämiseen? Siihenkin kait lienee olemassa jonkinnäköinen bresenham-algoritmi (tai sitten ei), mutta enpä ole sellaista mistään löytänyt.

peki [30.01.2005 22:14:56]

if (pe < 0)
    pe += 4 * x1 + 6;  // näitä lukuja muuttamalla saa algoritmin käyrää muutettua
else
{
    pe += 4 * (x1 - y1) + 10; // näitä lukuja muuttamalla saa algoritmin käyrää muutettua
    y1 -= 1;
}

Pienillä muutoksilla sain esimerkiksi aikaan pyöristetyn neliön. Tosin pyöristyksen kulmaa ei voi muokata.

tn: Jos ellipsiä muistuttavalle käyrälle on olemassa funktio, voidaan siitä johtaa bresenham-algoritmi soveltamalla linkin osoittamia keinoja.

Edit: Sori, en sitten lukenutkaan viestiäsi riittävän tarkasti :)
Missä tahansa kulmassa oleva ellipsi vaatii varmasti trigonometriaa sisältävän funktion, koska silloinhan täytyy funktion, josta bresenham johdetaan, sisältää kulma muutettuna koordinaateiksi.
Saattaa tulla jopa nopeammaksi käyttää avattua 2x2 matriisia pyöritykseen, sillä silloin pyöritykseen tarvitaan 4 rigonometristä laskutoimitusta.
Kaavan johtaminen vie todennäköisesti enemmän tehoa, mutta tietenkään ei voi olla varma ennen kuin on kokeillut.

Heikki [31.01.2005 21:44:09]

Pitäisikö tuon piirtää oikea ympyrä vai ellipsi? (Ps. Huono shotti, en tiedä miksi mutta jotenkin Gimp bugasi)

Koodi ainakin mukavan nopeanoloista.

peki [31.01.2005 22:49:51]

Sininen ympyrä siitä pitäisi tulla ainakin Windowsissa.
Ehkä tuo bittisyvyys vaikuttaa asiaan? Tuo minun koodini nimittäin olettaa, että taustapuskuri on 4 bytes/pixel ( << 2).
Asetuksessa tosin säädetään bittisyvyydeksi 32 bittiä, joten tiedähäntä.
Värit johtunevat siitä gimpin bugauksesta?
Algoritmissa vikaa ei pitäisi olla.

T.M. [01.03.2005 21:22:59]

Käänsin tuon PHP:lle, ja huomasin että tuossa on saman pikselin piirto kahteen kertaan:

            *(Uint32 *)(p + (y + y1) * surface->pitch + ((x + x1) << 2)) = 255;
            *(Uint32 *)(p + (y + y1) * surface->pitch + ((x - x1) << 2)) = 255;
            *(Uint32 *)(p + (y - y1) * surface->pitch + ((x + x1) << 2)) = 255;
            *(Uint32 *)(p + (y - y1) * surface->pitch + ((x - x1) << 2)) = 255;
            *(Uint32 *)(p + (y + x1) * surface->pitch + ((x + y1) << 2)) = 255;
    tämä -> *(Uint32 *)(p + (y + x1) * surface->pitch + ((x - y1) << 2)) = 255;
            *(Uint32 *)(p + (y - x1) * surface->pitch + ((x + y1) << 2)) = 255;
    tämä -> *(Uint32 *)(p + (y + x1) * surface->pitch + ((x - y1) << 2)) = 255;
            *(Uint32 *)(p + (y - x1) * surface->pitch + ((x - y1) << 2)) = 255;

peki [01.03.2005 22:57:41]

Virhe korjattu. Kiitoksia T.M. :)

Sahrah [25.04.2008 13:07:44]

SIinä tuleee ympy rää jos toistakin ;:PO;PO

Metabolix [19.02.2012 18:29:22]

Tässä on näitä klassisia SDL-mokia eli virheellinen näyttöpinnan vapautus ja SDL_PollEvent-funktion väärinkäyttö. Turha sitä samaa kuvaa on myöskään jatkuvasti piirtää uudestaan.

Sivun alkuun

Vastaus

Aihe on jo aika vanha, joten et voi enää vastata siihen.

Kirjautuminen

Haku

Tehtävät