Rastern

[Empire]

Hi zusammen,
Ich will eine eigene kleine 3D Engine schreiben.
Ich hab/weis jetzt auch fast alles was ich brauch
(glaube ich zu mindest), bis auf ein Raster Algo-
rithmus.
Hab schon ein bisschen gegoogelt und bin auf
verschiedene gestoßen. Aber niergens wird
einer so erklärt das ich in ihn java-code um-
setzten könnte.
Kann mir da jemand helfen?
Zum bsp der Gupta-Sproull-Antialiasing Algorithmus
oder ein ähnlicher.

mfg
EMpire

[Xin]

Hi zusammen,
Ich will eine eigene kleine 3D Engine schreiben.
Ich hab/weis jetzt auch fast alles was ich brauch
(glaube ich zu mindest), bis auf ein Raster Algo-
rithmus.
Hab schon ein bisschen gegoogelt und bin auf
verschiedene gestoßen. Aber niergens wird
einer so erklärt das ich in ihn java-code um-
setzten könnte.

Was ist denn überhaupt das Problem?

Kann mir da jemand helfen?
Zum bsp der Gupta-Sproull-Antialiasing Algorithmus
oder ein ähnlicher.

Die Frage ist zu unspezifisch, als dass ich darauf antworten könnte.
Wenn Du sie spezifischer stellst, so werde ich vermutlich auch nicht besser antworten können.

Es geht im Prinzip immer darum, dass Du eine auszumalende Fläche hast, die eventuell nicht genau auf Pixeln abgebildet. Somit geht es darum, heraus zu finden, wieviel Fläche eines Pixels von der auszumalenden Fläche bedeckt wird. Das kannst Du zum Beispiel ausrechnen, wenn eine Linie einen Pixel breit sein soll und schräg verläuft, dann kannst Du so ausrechnen, wo die Seitenlinien die Fläche eines Pixels schneidet und entsprechend, wieviel Fläche des Pixels von der Linie überdeckt werden.

Rechnen kostet aber Zeit.

In OpenGL wird Anti-Aliasing so realisiert, dass die Zeichnung viel zu groß gezeichnet wird. Ein Pixel wird so 2, 4 oder 8 Pixel breit. Nehmen wir 8 Pixel, ein Pixel besteht dann aus 8x8 = 64 Feldern. Eine Linie, die 1 Pixel breit sein soll, wird als 8 Pixel breites Viereck gezeichnet. Auf der Bitmap wird entsprechend ein Teil der 64 Felder übermalt. Vor der Ausgabe wird das Bild wieder verkleinert. Für jeden Pixel existieren 64 Farbwerte, aus denen eine Durchschnittsfarbe errechnet werden kann. Das ist nicht so genau, wie es exakt auszurechnen, aber schonmal nah dran.

[Empire]

Ich brauch einen Algorithmus zum rastern,
hab aber mit Googel keine Erklärung gefunden
an der ich den java-code basteln kann.
Jetzt wollte ich wissen ob es hier jemand
gibt der mir das besser erklären kann.

mfg
Empire

[Xin]

Ich brauch einen Algorithmus zum rastern,
hab aber mit Googel keine Erklärung gefunden
an der ich den java-code basteln kann.
Jetzt wollte ich wissen ob es hier jemand
gibt der mir das besser erklären kann.

Es ist ja stark davon abhängig, was Du für Eingangsdaten hast und was Du für Ansprüche hast. Die Grundlage habe ich Dir ja gerade gesagt. Wenn Deine Eingangsdaten Datenstrukuren sind, so musst Du Deine Koordinaten auf Dein Raster umrechnen.
Wenn Du Fragen beantwortet haben möchtest, so brauche ich etwas konkretere Fragen oder ich schick Dir ein Buch.
Abtippen werde ich's aber nicht so einfach

[Empire]

Danke mir ist grade eine licht aufgegangen.
Ich glaub es hat sich erledigt.

mfg
Empire

[Xin]

Danke mir ist grade eine licht aufgegangen.
Ich glaub es hat sich erledigt.

Vielleicht magst Du Deine Erleuchtung mit uns teilen, damit wenigstens ich weiß, was Du da tust, bzw. wo das Problem eigentlich lag.

[Empire]

Ok ich hab ein Algorithmus fürs rastern gebraucht.
Lösung:
Funktion der Geraden bestimmen, dann immer Testen ob der
Pixel drüber oder der Links vom Aktuellen näher dran ist
und färben.
Anschließend vom großen raster wieder auf ein kleineres runter
rechnen damit es nicht pixelt.

mfg
Empire

[Xin]

Funktion der Geraden bestimmen, dann immer Testen ob der
Pixel drüber oder der Links vom Aktuellen näher dran ist
und färben.

Diesbezüglich schau Dir den Bresenham-Algorithmus an. Er ist leider noch nicht im Wiki vertreten.

Die Implementation hier ist von mir, Point ist ein 2D-Punkt, Distance ist die Differenz zweier Punkte, SetCoordinate eine Funktion, die pro Punkt gerufen wird (z.B. um den Punkt in die Bitmap zu setzen).

Den Algorithmus baust Du Dir am besten Step-By-Step nach oder vermeldest überdeutlich, dass Du eine Erklärung im Wiki haben willst - dann stellt halt sich die Frage, wann jemand Zeit dafür hat. ^^

Code: Alles auswählen

/*
** bresenham.h
**
** May 13th 2006
** Sascha Atrops
***************************************/

#ifndef DE_XSD_ALGORITHM_BRESENHAM_H
#define DE_XSD_ALGORITHM_BRESENHAM_H

#include "de/xsd/unit/unit2d.h"

namespace XSD {
namespace Algorithm {

using namespace XSD::Unit;

/** template function to create straight lines
*** \param T datatype of userData
*** \param SetCoordinate callback-function to set every dot
*** \param userData pointer to whatever you like, i.e. a class. Will be overgiven to every SetCoordinate call.
*** \param start Point where the line should start
*** \param end Point where the line should end
**/

template <class T, void (*SetCoordinate)( int pointno, Point point, T * userData )>
void Bresenham( T * userData, Point start, Point end )
{
  Distance delta    = end - start;
  Distance increase = delta.Direction();
  int h, pointno=0;

  SetCoordinate( pointno++, start, userData );

  delta = delta.Absolute();

  if( delta.x > delta.y )
  {
    h = delta.x;
    delta <<= 1;

    while( start.x != end.x )
    {
      start.x += increase.x;
      h       -= delta.y;

      if( h <= 0 )
      {
        start.y += increase.y;
        h       += delta.x;
      }

      SetCoordinate( pointno++, start, userData );
    }
  }
  else
  {
    h = delta.y;
    delta <<= 1;

    while( start.y != end.y )
    {
      start.y += increase.y;
      h       -= delta.x;

      if( h <= 0 )
      {
        start.x += increase.x;
        h       += delta.y;
      }

      SetCoordinate( pointno++, start, userData );
    }
  }
}

}}

#endif

[Empire]

Mein Problem war nicht das ich den Bresenham-Algorithmus nicht
verstanden hatte. Sondern das ich das ich ihn nicht wollte weil
er ja nur mit einer Farbe arbeitet und das Bild dann pixelt.

Erst als ich deinen VorVorLetzten Beitrag das zweite mal durch
gelesen hab bin ich auf die Idee gekommen, ihn erst auf einem
größerem Raster zu benutzen und dann auf ein kleineres Raster
umzurechnen.

mfg
Empire