Computergrafik: Kreis

[Samuel]

Es geht nicht um explizit Java Code, sondern nur um die theoretische Überlegungen.

Da Computergrafik jeden jungen Mann früher oder später trifft
Hatte ich heute Nacht um 3 Uhr in der Disko das Verlangen über Computergrafik nachzudenken
Da etwaige Vorlesungen für sowas noch in sehr weiter Ferne liegen, brauch ich akkut n bisschen Hirn von euch, hehe.

Ohja, das Thema, ich hab mich erstmal mit dem Grundelement Kreis beschäftigt.
Sagen wir , wir haben keine API, die uns einen Kreis gibt, wir haben also nur die Möglichkeit Pixel an Koordinate xy an oder aus zu machen und sagen wir weiter, dass wir nun einen Kreis am Monitor darstellen wollen, Mitte sei (0,0) mit dem Radius r.
Sinus und Cosinus sind hier kein Problem um jeden möglilchen Punkt auf der Kreislinie zu finden, ABER wir brauchen ja den Winkel alpha, der im Intervall[0,359] liegt um die Punktposition zu bestimmen.
Nun, da ist mein erstes Problem, im Intervall [0,359] gibt es unendlich viele Elemente, da wir ja das Abbild des Kreises aber auf eine Pixelfläche mit 72 DPI abbilden wollen(Bildschirm? Aber in späteren Überlegungen ist das nur relevant, wenn man Radien in cm usw angibt), frag ich mich die ganze Zeit, was für eine Einteilung muss alpha haben?
[0,359] sind in Einerschritten 360 Winkelstellungen und damit auch 360 Punkte auf dem Kreis.
Jetzt spielt aber noch der Radius des Kreises eine signifikante Rolle;
ein sehr kleiner Radius hat einen sehr kleinen Kreis zur Folge, dh der Kreis hat vielleicht nur 40 Punkte , ist der Radius groß, hat der Kreisrand mehr und wesendlich mehr als nur 360 Punkte.
Da bin ich mit dem Denken in einer lauten Disko gescheitert.
Wie wähle ich alpha? Kann es natürlich in 0.01 Schritten durchackern, aber dann ist 1. jeder noch so kleine Kreis äußerst performancelastig und 2. Kann damit ein großer Radius nicht voll abgedeckt sein.
Wie wähle ich nun alpha?

Gerade ist mir noch eine Idee gekommen, müsste ein Radius von 10 Pixeln nicht laut dem Gesetz zur Berechnung des Kreisumfangs U=2*r*Pi ergo für Radius r = 10 U ca 68 Pixel lang sein?
Ist sowas hilfreich? Kann ich damit rechnen, dass ich nur 68 Pixel für diesen Kreis brauche und meine alpha Einteilung so wählen, dass ich nur 68 Punkte berechne?

 

[Beni]

alpha = 36°, dann die 10 Punkte mit Geraden verbinden. Daumen * PI, das sieht schon ganz gut nach einem Kreis aus. Vielleicht sind auch 20 Punkte notwendig, müsste man ausprobieren :wink:

 

[Thammi]

Wenn ich dich richtig verstanden habe geht es dir darum, wie oft bzw, an welchen Punkten die Position ausgerechnet werden muss und ein Pixel gesetzt werden muss ohne einen Pixel doppelt zu setzen oder Lücken zu lassen, oder?

Wenn du den Radius (in Pixeln) kennst kannst du ja mit der Umkehrfunktion von cos und sin (acos und asin, oder so) herausfinden für welchen Winkel die jeweiligen Pixel zuständig sind. Für diesen Winkel kann man dann noch den jeweils anderen Wert ausrechnen. Das müsste man dann natürlich noch spiegeln, weil die Umkehrfunktionen ja theoretisch ein mögliches Ergebniss "unterschlagen". Ich will jetzt nicht mehr schreiben, weil ich ziemliche Angst habe im Verständiss der Frage daneben zu liegen ;-)

Das ist meine Theorie, die ich mir in ein paar langweiligen Schulstungen ausgedacht habe ...

Edit:
mit dem Umfang kommt man Meiner Meinung nach nicht wirklich weiter. Ich hab mal als Beispiel nen Radius von 2 Pixeln genommen und ungefähr 12 rausbekommen, da würden ja nur noch 4 Pixel zu nem vollständig gefülltem Quadrat fehlen (wenn ich deine Theorie richtig verstanden habe)

 

[Samuel]

Die Frage hast du schon richtig verstanden, aber deine Umkehrlogik würde ja vorraussetzen, dass ich die Pixel des Kreises kenne, um von denen den Winkle zu berechnen

 

[Thammi]

Ich brauche doch nur einen Wert, und nicht sowohl X als auch Y zu kennen.
Wenn ich weiss, dass ich einen Radius von 50 Pixeln kann man diese doch als 50 X-Werte betrachten, von denen man dann asin ausrechnen kann. Diese Winkel kann man dann ja schon mal fertig ausrechnen und "anzeichnen". Dann könnte man das noch mit den 50 Y-Werten machen, weil ja evtl. um 0° und 180° mehrere Punkte zu einem X-Wert angetragen werden müssen (Bei relativ großem Pixel-Radius wird das wohl nicht der Fall sein).

So hat man doch dann einen schönen Kreis, wobei man die Punkte höchstens 2x berechnet (besser als gar kein Anhaltspunkt ;-)).

 

[Samuel]

Wie kommst du denn auf 50 X Werte?
Wenn Radius r = 50 ist: Gehen wir mal vom I Quadranten in einem gedachten Achsenkreuz mit 0,0 als Mittelpunkt aus.

Radius 50 bedeutet es gibt einen Punkt 0,50 und einen Punkt 50,0, verbinden wir diese Punkte, haben wir ein Dreieck, mit Pythagoras erfahren wir, dass diese Gerade, also die Hypotenuse: 50^2+50^2=c^2 ergo ca 70 oder -70 ist.
Das bedeutet bei einem Kreis mit Radius 50 ist die Gerade zu zwei Punkten im 90° Winkel schon 70, und da der Kreisbogen gekrümmt ist und im I Quadranten oberhalb der Hypotenuse liegt, muss der Viertelkreis ja meiner Meinung nach schon wesendlich mehr als 50 Punkte haben

 

[Thammi]

Ich habe den Radius 50 so gemeint, dass genau 50 Pixel den Radius bilden. Eigentlich sind es dann ja auch 100 X-Werte von denen ich vorerst ausgehe ...

Stelle dir ein Koordinatensystem vor, dessen Ursprung der Mittelpunkt des Kreises ist. Ein Pixel entspricht einer Längeneinheit. Jedem X-Wert in diesem Koordinatensystem, dessen Betrag nicht grösser als der Radius des Kreises ist (im Beispiel -50 bis 50) muss mindestens ein Y-Wert zugeordnet sein (also mindestens ein Pixel an). Also kann ich mir ausrechnen welcher Winkel zu den einzelnen X-Werten gehört, und daraus kann man dann ja die Pixel-Position errechnen.

Ich gehe also nicht von einem Winkel aus, der jeweils addiert wird um alle Punkte zu setzen, sondern von vorherbestimmten Stellen (ohne Y-Wert) an denen ich einen Punkt setzen will. Ist eben ein anderer Ansatz.

Wie im letzten Post gesagt ist der Kreis so noch nicht ganz fertig. Das ganze muss nochmal gespiegelt werden, weil so nur ein Halbkreis rauskommt. Um einen Kreis ohne Lücken zu haben das ganze noch einmal "umdrehen", also die Prozedur wiederholen wobei X- und Y-Werte vertauscht sind.

btw: Gehört das vielleicht eher in den Mathematik-Bereich?

 

[Samuel]

Ein Kreis hat aber für ein X Wert 1, 2 oder mehr Y Werte, wann weißt du denn, dass du fertig mit suchen bist?
Das sieht mehr nach einen druchlaufen aller möglichen Werte aus, oder verstehe ich dich falsch?

 

[Thammi]

Für einen X-Wert existieren zwei oder ein (bei 0° und 180°) Wert. Durch das erwähnte spiegeln (geht am einfachsten indem man jeden Punkt einmal mit positivem und einmal mit negativem Y-Wert zeichnet) kommt man dann zu dem 2. Wert, der aber nicht errechnet werden muss. Dort wo mehrere Pixel untereinander sind greift der durchlauf bei dem X und Y vertauscht werden. Das hat eigentlich gar nichts mir "durchprobieren" zu tun, weil man genau 200 mal (für den Radius von 50 Pixeln) die Umkehrfunktion von Sinus oder Kosinus ausführt, darauf Sinus oder Kosinus anwendet und dann zeichnen kann.

Ich hoffe jetzt hab ich's verständlicher beschrieben.

 

[Samuel]

http://img507.imageshack.us/img507/4782/kreis7sj.jpg

Ist ein Kreis, aber die äußeren Kanten haben mehr als nur 2 Werte und der Kreis sieht tatsächlich so aus.
Ein Kreis kann wesendlich mehr als nur 2 Punkte pro X Koordinate haben

 

[Thammi]

Man muss X-Koordinate und Pixel unterscheiden ... aber ich hab das ja selber ein bisschen eingeführt ;-)
Die mehreren Pixel in einer "Reihe" kommen vom Runden. Gerade diesen Effekt beziehe ich ja durch das durchführen der gleichen Prozedur mit umgekehrtem X- und Y-Wert mit ein. So wird wirklich jeder deiner Punkte auf dem Kreis gezeichnet. Schau es dir mal an, keiner der Pixel hat sowohl über/unter und rechts/links einen Nachbarn. Meine 2 Punkte pro Koordinate kommen übrigens daher, das sowohl unter als auch über der Y-Achse jeweils ein Wert ist.

Das mit dem doppeltem ausführen, einmal mit umgedrehten X- und Y-Wert ist vielleicht noch nicht ganz klar geworden. Ich versuch's nochmal, hier der gesamte Ablauf:

asin von allen X-Werten errechnen, in den cos einsetzen und schon hat man den passenden Y-Wert zum X
kurz: Y=cos(asin(X)) für alle X Element N -r<Y<r

acos von allen Y-Werten errechnen, in den sin einsetzen und schon hat man den passenden X-Wert zum Y
kurz: X=cos(asin(Y)) für alle Y Element N -r<X<r

Alle errechneten Wertepaare kann man jetzt einzeichnen und fertig ist der leicht löchrige Dreiviertelkreis (im 1. Quatranden ohne Löscher). Wenn man jetzt noch alle Punkte mit negativiertem Wert einträgt ist der ganze Kreis fertig.

 

[Bert Brenner]

Hab da mal kurz etwas Code zusammengebastelt:

import javax.swing.*;
import java.awt.*;


public class Kreis extends JPanel {
  private int radius;
  
  
  
  public Kreis(int radius){
    this.radius=radius;
    this.setPreferredSize(new Dimension((radius<<1) + 20, (radius<<1) + 20));
  }
  
  
  
  public void paintComponent(Graphics g){
    super.paintComponent(g);
    g.setColor(Color.BLACK);
    g.translate(radius+10, radius+10);
    for (int dy = 0; dy <= radius; dy++) {
      int dx = (int) (Math.sin(Math.acos( (double) dy / radius)) * radius);
      g.drawRect(-dx, -dy, dx*2, dy*2);
    }
  }
  
  
  
  public static void main(String[] args) {
    JFrame frame = new JFrame("Kreis");
    frame.getContentPane().add(new Kreis(100));
    frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
    frame.pack();
    frame.setVisible(true);
  }
}

 

[Samuel]

Ne so wirds nicht gemacht.
Float Zahlen sind zulangsam bei Zeichnen von Rastergrafiken.
Ausserdem, wie ist denn dein dy unterteilt? In einer Schritte? gibt das nicht löcher?

Sowieso hat Bresenham einen viel tolleren Algorithmus erfunden und das ist der, der benutzt wird, aber mein Prof meint, solange ich nicht bei Ati oder nVidia die 2d Chipprogrammierung übernehmen will, brauch ihc das auch nicht zu wissen )