# 3D Cube (Bresenham-Alg.)



## Levitas (16. Nov 2010)

Hallo Java-Gemeinde,

ich bin mal wieder bei einem Problem und hoffe, dass ihr mir vllt. dabei weiterhelfen könnt, da ich schon echt lange daran sitze und nicht weiter weiss. Es geht um ein Programm, das 3D-Figuren ein- bzw. auslesen soll (nur nebenbei als Info). Konkret geht es um Folgendes:

Wir sollen (Aufgabe aus dem Studium) die Linien eines Würfels (3D) mit Hilfe des Bresenham-Geraden-Algrithmus programmieren, ohne dazu die Java-Biblithek zu verwenden. (Würfel ist eine drehbarer Körper)

Ich denke der Algorithmus sollte soweit passen, allerdings ist das Programm durch Fehler nicht ausführbar. Ich kann allerdings mir nichts aus den Fehlermeldung reimen, was zu einer Lösung führen würde, deshalb wäre es super wenn ihr vllt. mal drüberschaut.

Zunächst einmal nur ein Codeausschnitt der entsprechenden Klasse. (Im Anhang dann das Projekt)


```
package cog1;
 
 import java.awt.Color;
 import java.text.DecimalFormat;
 import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.Collections;
 import java.util.Iterator;
 
 
 // Rasterization algorithms, called by Render class.
 public class Raster {
 
     // View-port, size of window or canvas.
     private int viewWidth;
     private int viewHeight;
 
     // Plane equation of polygon.
     private float A;
     private float B;
     private float C;
     private float D;
     private float AdivC; // Pre-calculate for speed-up.
 
     DecimalFormat format = new DecimalFormat("+#.##;-#.##"); // For debug.
     
     // For each polygon we store all points from all edges 
     // generated by the Bresenham algorithm.
     // The are use for the scan-line fill algorithm.
     // After processing a polygon the data structures are reset.
     
     // One ArrayList for every scan-line.
     private ArrayList<ArrayList<Integer>> scanlineIntersection;
     
     public Raster( final int viewWidth, final int viewHeight ) {        
         this.viewWidth = viewWidth;
         this.viewHeight = viewHeight;
 
         scanlineIntersection = new ArrayList<ArrayList<Integer>>();        
         for (int y = 0; y < viewHeight; y++) {
             scanlineIntersection.add(new ArrayList<Integer>());
         }        
     }
     
     private void addIntersection( int x, int y ) {
         if ( x >= 0 && x < viewWidth && y >= 0 && y < viewHeight ) {
             //scanlineIntersection.getyes.add( new Integer(x) );
        	 scanlineIntersection.get(y).add( x );
             } else {
             //System.out.println("Error in addIntersection (out of screen):"+x+","+y); //debug
         }
     }
     
     private void clearIntersections() {
         for (ArrayList<Integer> line : scanlineIntersection) {
             line.clear();
         }
     }
     
     private int abs( int val) {        
         return val >= 0 ? 1 : -1; 
     }
     
     public void bresenham( Framebuffer framebuffer,
             int startX, int startY, int endX, int endY, 
             final Color color, boolean toFrameBuffer ) {
         
      
         final int dX = endX - startX; 
         final int dY = endY - startY;
         
         final int dXAbs = Math.abs(dX);// - !!!!!!!!!!!!!!!!!
         final int dYAbs = Math.abs(dY);// - !!!!!!!!!!!!!!!!!
         
         final int dXSign = (int)abs(dX);
         final int dYSign = (int)abs(dY);
 
         
         final int dXAbs2 = 2 * dXAbs; // - !!!!!!!!!!!!!!!!!
         final int dYAbs2 = 2 * dYAbs; // - !!!!!!!!!!!!!!!!!
         final int dXdYdiff2 = 2 * (dXAbs - dYAbs); // shortcut for speedup. 
         final int dYdXdiff2 = 2 * (dYAbs - dXAbs); // shortcut for speedup. - Inc2 
         
         int x = startX;
         int y = startY;
         double e = 0.0; //Entscheidungsvariable       
         
       //Farbe festlegen
    	 Color c = new Color(178,034,034);
         
    	 
         // ... start here.....
    	 //Wertevergaben der Inkremente/Dekremente für fallende und steigende Linien
    	 final int inc_x;
    	 final int inc_y;
    	 
    	 if(dX > 0)			// Wenn Linie nach rechts
		    inc_x = 1;		// x inkrementieren
		  else				// Wenn Linie nach links
		    inc_x = -1;		// x dekrementieren

		  if(dY > 0)		// Wenn Linie nach unten
		    inc_y = 1;		// y inkrementieren
		  else				// Wenn Linie nach oben
		    inc_y = -1;		// y dekrementieren

	 
    	 

	    	 //wenn x länger oder gleich y - langsam steigend/fallend
	    	 if(dX >= dY){
	    		 e = -Math.abs(dX);
	    		 int step = (int) (2*e);
		    	 while (x <= endX){
					drawPoint(framebuffer,x,y,c);
		    		 x += inc_x;
		    		 e += dYAbs2;
		    		 if (e>0){
		    			 y += inc_y;
		    			 e += step;
		    		 }
		    	 }
	    	 }
	    	 else{	//wenn x kürzer als y - schnell steigend
	    		 e = -Math.abs(dX);
	    		 int step = (int) (2*e);
		    	 while (y <= endY){
					drawPoint(framebuffer,x,y,c);
		    		 y += inc_y;
		    		 e += dXAbs2;
		    		 if (e>0){
		    			 x += inc_x;
		    			 e += step;
		    		 }
		    	 }
	    	 }
    	 
    	 
    	
    	 
    	 
 }// Ende bresenham()
     
     //die Werte, welche mit dem Alg. erzeugt werden müssen nun in den framebuffer
     private void drawPoint(Framebuffer framebuffer, int x, int y, Color c) {
    	 if((this.viewHeight>y)&&(this.viewWidth>x)){
	    	 framebuffer.buf[x][y].color=c;
	    	 framebuffer.buf[x][y].keep=true;
	    	 framebuffer.buf[x][y].changed = false;
    	 }
    }
     

     
     
     
     
 
     private int calcDerivative( final int currY, final int nextY) {
         // y axis from top to bottom.
         if( currY < nextY ) {
             return -1;
         } else if ( currY > nextY ) {
             return +1;
         } else  {
             return 0;
         }
     }
         
     private void calcPlaneEquation( float[][] vertex, int[] polygon ) {
         // We assume that all vertices of the polygon are in one plane.
         // Two edge-vectors dim 3:
         float e[][] = new float[2][3];
         // Calculate two (non parallel) vectors inside the plane of the polygon.
         // We assume that at least two (consecutive) vertices of a polygon
         // are not on a straight line with the first vertex.
         
         
         // ....
         
         //System.out.println("Plane: A="+format.format(A)+" B="+format.format(B)+" C="+format.format(C)+" D="+format.format(D)+
         //            "   nLength="+nLength+"    A/C="+A/C); // debug
     }
 
     
     
     
     
     //Hier wird die Bresenham-Methode aufgerufen
     public void scanlineDrawPolygon( Framebuffer framebuffer, 
             float[][] vertex, int[] polygon, final Color color, boolean fill) {
         
         /*
         // We want at least a triangle to proceed.
         if( polygon.length < 3 ) { return; }
                 
         // Draw edges or register interactions.
         if(fill) { clearIntersections(); }
         int lastDerivative = calcDerivative(
                 (int)vertex[polygon[polygon.length-2]][1], 
                 (int)vertex[polygon[polygon.length-1]][1]);
         int derivative = lastDerivative;
         */
         
         //System.out.println("______Start next Polygon_______"); //debug.
         for(int v = 0; v < polygon.length - 1; v++) { // Polygon-Vertices loop.
             final int currX = (int)vertex[polygon[v]][0];
             final int currY = (int)vertex[polygon[v]][1];
             final int nextX = (int)vertex[polygon[v+1]][0];
             final int nextY = (int)vertex[polygon[v+1]][1];
 
             bresenham( framebuffer, 
                     (int) currX, (int) currY,
                     (int) nextX, (int) nextY, 
                     color, ! fill );
             
             // ...
         }            
         
         // ...
     }
     
     private float getZ( final float x, final float y) {
         // We assume that the plane equation is upto date 
         // with the current polygon.
         return -(A*x + B*y + D)/C;
     }
 
 }
```

Die Fehlermeldung beim Ausführen der entsprechenden Klasse:

1.0Exception in thread "AWT-EventQueue-0" java.lang.ArrayIndexOutOfBoundsException: -1
	at cog1.Raster.drawPoint(Raster.java:170)
	at cog1.Raster.bresenham(Raster.java:128)
	at cog1.Raster.scanlineDrawPolygon(Raster.java:235)
	at cog1.Render.raster(Render.java:199)
	at cog1.Render.paintComponent(Render.java:217)
	at javax.swing.JComponent.paint(Unknown Source)
	at javax.swing.JComponent.paintChildren(Unknown Source)
	at javax.swing.JComponent.paint(Unknown Source)
	at javax.swing.JComponent.paintChildren(Unknown Source)
	at javax.swing.JComponent.paint(Unknown Source)
	at javax.swing.JLayeredPane.paint(Unknown Source)
	at javax.swing.JComponent.paintChildren(Unknown Source)
	at javax.swing.JComponent.paintToOffscreen(Unknown Source)
	at javax.swing.RepaintManager$PaintManager.paintDoubleBuffered(Unknown Source)
	at javax.swing.RepaintManager$PaintManager.paint(Unknown Source)
	at javax.swing.RepaintManager.paint(Unknown Source)
	at javax.swing.JComponent.paint(Unknown Source)
	at java.awt.GraphicsCallback$PaintCallback.run(Unknown Source)
	at sun.awt.SunGraphicsCallback.runOneComponent(Unknown Source)
	at sun.awt.SunGraphicsCallback.runComponents(Unknown Source)
	at java.awt.Container.paint(Unknown Source)
	at java.awt.Window.paint(Unknown Source)
	at javax.swing.RepaintManager.paintDirtyRegions(Unknown Source)
	at javax.swing.RepaintManager.paintDirtyRegions(Unknown Source)
	at javax.swing.RepaintManager.seqPaintDirtyRegions(Unknown Source)
	at javax.swing.SystemEventQueueUtilities$ComponentWorkRequest.run(Unknown Source)
	at java.awt.event.InvocationEvent.dispatch(Unknown Source)
	at java.awt.EventQueue.dispatchEvent(Unknown Source)
	at java.awt.EventDispatchThread.pumpOneEventForFilters(Unknown Source)
	at java.awt.EventDispatchThread.pumpEventsForFilter(Unknown Source)
	at java.awt.EventDispatchThread.pumpEventsForHierarchy(Unknown Source)
	at java.awt.EventDispatchThread.pumpEvents(Unknown Source)
	at java.awt.EventDispatchThread.pumpEvents(Unknown Source)
	at java.awt.EventDispatchThread.run(Unknown Source)

Ich hoffe ihr könnt damit was anfangen. Bin langsam echt am verzweifeln


----------



## Marco13 (16. Nov 2010)

Nur drübergeschaut, aber bei dem Namen "Raster" und "drawPoint" und einer Abfrage wie
if((this.viewHeight>y)&&(this.viewWidth>x)){
sieht es aus, als sollten da die Punkte NICHT gezeichnet werden, die Außerhalb des Bildschrims liegen. Die Abfrage müßte dann aber 
if(x>=0 && y>=0 && (this.viewHeight>y)&&(this.viewWidth>x)){
sein...


----------



## Levitas (17. Nov 2010)

Zunächst danke füür die Antwort!

Aber leider bringt die Vermutung nicht die erhoffte Lösung. 
ABER: Das Programm wird ausführbar, allerdings bekomme ich ein komplett schwarzes Fenster, dass sich dann aufhängt. Scheinbar werden mit der Änderung Linien auf dem ganzen Fenster gemalt... 

Hm... habt ihr vllt. sonst noch Vorschläge? :-(


----------



## Marco13 (17. Nov 2010)

while-Schleifen sind da heiße Kandidaten... Raster#bresenham:

```
//wenn x länger oder gleich y - langsam steigend/fallend
             if(dX >= dY){
                 e = -Math.abs(dX);
                 int step = (int) (2*e);
                 while (x <= endX){
                     [b]System.out.println("ladida...");[/b]
                    drawPoint(framebuffer,x,y,c);
                     x += inc_x;
                     e += dYAbs2;
                     if (e>0){
                         y += inc_y;
                         e += step;
                     }
                 }
             }
             else{  //wenn x kürzer als y - schnell steigend
                 e = -Math.abs(dX);
                 int step = (int) (2*e);
                 while (y <= endY){
                     [b]System.out.println("ladida...");[/b]
                    drawPoint(framebuffer,x,y,c);
                     y += inc_y;
                     e += dXAbs2;
                     if (e>0){
                         x += inc_x;
                         e += step;
                     }
                 }
             }
```

Die Ursache darfst du selbst suchen


----------



## Levitas (18. Nov 2010)

hey... programm ausführbar! Aber zeigt nichts an...

Ausgabe der Konsole:

vertex[0]:
OrgCoord     :-1.0	 -1.0	 -1.0	 1.0
ModelCoord     :-0.8111595	 1.0000001	 -1.1584558	 1.0
NormDisplayCoord :-0.08111595	 -0.10000002	 -0.11584558	 1.0
ScreenCoord      :229.72101	 225.0	 221.0386	 1.0
vertex[1]:
OrgCoord     :1.0	 -1.0	 -1.0	 1.0
ModelCoord     :-1.158456	 0.99999994	 0.81115955	 1.0
NormDisplayCoord :-0.1158456	 -0.099999994	 0.08111595	 1.0
ScreenCoord      :221.03859	 225.0	 270.279	 1.0
vertex[2]:
OrgCoord     :1.0	 -1.0	 1.0	 1.0
ModelCoord     :0.8111595	 0.99999994	 1.158456	 1.0
NormDisplayCoord :0.08111595	 -0.099999994	 0.1158456	 1.0
ScreenCoord      :270.279	 225.0	 278.9614	 1.0
vertex[3]:
OrgCoord     :-1.0	 -1.0	 1.0	 1.0
ModelCoord     :1.158456	 1.0000001	 -0.81115943	 1.0
NormDisplayCoord :0.1158456	 -0.10000002	 -0.081115946	 1.0
ScreenCoord      :278.9614	 225.0	 229.72101	 1.0
vertex[4]:
OrgCoord     :-1.0	 1.0	 -1.0	 1.0
ModelCoord     :-0.8111595	 -0.99999994	 -1.158456	 1.0
NormDisplayCoord :-0.08111595	 0.099999994	 -0.1158456	 1.0
ScreenCoord      :229.72101	 275.0	 221.03859	 1.0
vertex[5]:
OrgCoord     :1.0	 1.0	 -1.0	 1.0
ModelCoord     :-1.158456	 -1.0000001	 0.81115943	 1.0
NormDisplayCoord :-0.1158456	 0.10000002	 0.081115946	 1.0
ScreenCoord      :221.03859	 275.0	 270.279	 1.0
vertex[6]:
OrgCoord     :1.0	 1.0	 1.0	 1.0
ModelCoord     :0.8111595	 -1.0000001	 1.1584558	 1.0
NormDisplayCoord :0.08111595	 0.10000002	 0.11584558	 1.0
ScreenCoord      :270.279	 275.0	 278.9614	 1.0
vertex[7]:
OrgCoord     :-1.0	 1.0	 1.0	 1.0
ModelCoord     :1.158456	 -0.99999994	 -0.81115955	 1.0
NormDisplayCoord :0.1158456	 0.099999994	 -0.08111595	 1.0
ScreenCoord      :278.9614	 275.0	 229.72101	 1.0
ladida...
ladida...
ladida...
ladida...
ladida...
ladida...
ladida...
ladida...
ladida...
ladida...
ladida...
ladida...
ladida...
ladida...
ladida...
ladida...
ladida...
ladida...
ladida...
ladida...
ladida...
ladida...
ladida...
ladida...
ladida...
ladida...
ladida...
ladida...
ladida...
ladida...
ladida...
ladida...
ladida...
ladida...
ladida...
ladida...
ladida...
ladida...
ladida...
ladida...
ladida...
ladida...
ladida...
ladida...
ladida...
...





Die obere Ausgabe sind Koordinaten, die das Programm ausgeben soll...
Wie soll cih nun weiter vorgehen?


----------



## Levitas (18. Nov 2010)

achja... weiter unten kommt auch nochmal die selbe fehlermeldung...


----------



## Levitas (18. Nov 2010)

Wenn ich nur die erste Bedigung ausführe, also bei langsam steigenden Linien kommt keine Fehlermeldung. Wenn ich nur die zweite bedinnung ausführe kommen die Fehlermeldungen. Allerdings wird so oder so nichts dargestellt.


----------



## Marco13 (18. Nov 2010)

Das "ladida" sollte deutlich machen, dass er dort anscheinend in einer Endlosschleife hängt. Lass' dir mit Konsolenausgaben alles ausgeben, was nötig ist, um herauszufinden, warum die while-Schleife nie beendet wird...


----------



## Levitas (18. Nov 2010)

OK... ich konnte das Problem soweit beheben... Hier mein überarbeiteter Code:


```
public void bresenham( Framebuffer framebuffer,
             int startX, int startY, int endX, int endY, 
             final Color color, boolean toFrameBuffer) {
         
      
         final int dX = endX - startX; 
         final int dY = endY - startY;
         
         final int dXAbs = Math.abs(dX);// - !!!!!!!!!!!!!!!!!
         final int dYAbs = Math.abs(dY);// - !!!!!!!!!!!!!!!!!
         
         final int dXSign = (int)abs(dX);
         final int dYSign = (int)abs(dY);
 
         
         final int dXAbs2 = 2 * dXAbs; // - !!!!!!!!!!!!!!!!!
         final int dYAbs2 = 2 * dYAbs; // - !!!!!!!!!!!!!!!!!
         final int dXdYdiff2 = 2 * (dXAbs - dYAbs); // shortcut for speedup. 
         final int dYdXdiff2 = 2 * (dYAbs - dXAbs); // shortcut for speedup. - Inc2 
         
         int x = startX;
         int y = startY;
         double e = 0.0; //Entscheidungsvariable       
         
       //Farbe festlegen
    	 Color c = new Color(178,034,034);
    	 Raster ra = null;
         
    	 
         // ... start here.....
    	 //Wertevergaben der Inkremente/Dekremente für fallende und steigende Linien
    	 final int inc_x;
    	 final int inc_y;
    	 
    	 if(dX > 0)			// Wenn Linie nach rechts
		    inc_x = 1;		// x inkrementieren
		  else				// Wenn Linie nach links
		    inc_x = -1;		// x dekrementieren

		  if(dY > 0)		// Wenn Linie nach unten
		    inc_y = 1;		// y inkrementieren
		  else				// Wenn Linie nach oben
		    inc_y = -1;		// y dekrementieren

	 
    	 

	    	 //wenn x länger y - langsam steigend/fallend
	    	 if(dY < dX){
	    		 e = -dXAbs;
	    		 int step = (int) (2*e);
		    	 while (x != endX){		    		 
					drawPoint(framebuffer,x,y,c);
		    		 x += inc_x;
		    		 e += dYAbs2;	//dYAbs2 = 2 * dYAbs
		    		 if (e>0){
		    			 y += inc_y;
		    			 e += step;
		    		 }
		    	 }
	    	 }
	    	 else{	//wenn x kürzer als y - schnell steigend
	    		 e = -dYAbs;
	    		 int step = (int) (2*e);
		    	 while (y != endY){
					drawPoint(framebuffer,x,y,c);
		    		 y += inc_y;
		    		 e += dXAbs2;	//dXAbs2 = 2 * dXAbs
		    		 if (e>0){
		    			 x += inc_x;
		    			 e += step;
		    		 }
		    	 }
	    	 }
	    	 drawPoint(framebuffer,endX,endY,c);	//Letztes Pixel zeichnen, wenn (x==endX) && (y==endY)
```

Leider werden immer noch nicht alle Linien 100%ig richtig gezeichnet. Im Anhang mal die aktuelle Ausgabe. Vllt. fällt jemand dazu noch was ein... @Marco13: du hattest recht, es war ein Schleifen-Problem


----------



## Marco13 (18. Nov 2010)

Wenn das NUR ein Würfel sein soll, werden einige Linien doppelt gezeichnet !? (Und einige falsch, aber das ist ein anderer Punkt...)


----------



## Levitas (19. Nov 2010)

hm... ja das dachte ich mir schon... kannst du mir evtl sagen was ich ändern sollte, damit es richtig gezeichnet wird? ich programmiere leider noch nicht so lange Java und tu mir noch etwas schwer.


----------



## Marco13 (19. Nov 2010)

Ich werd mir das frühestens (wenn überhaupt) nächste Woche näher ansehen können, und selbst dann ist fremden Code zu Debuggen ungefähr so, wie jemand anderem in der Nase zu bohren...
Du solltest versuchen, dir einen Testfall zu machen, wo NUR eine Linie gezeichnet wird, und (falls das nicht zu aufwändig ist) eine Möglichkeit, beide (oder zumindest einen) Endpunkt der Linie mit der Maus zu verschieben. Waagerecht wird sie wohl noch richtig gezeichnet, und sobald beim Bewegen was falsch wird, erkennt man vielleicht eher die Bedinungen, unter denen der Fehler auftritt....


----------



## Levitas (19. Nov 2010)

wär echt klasse, wenn du mal drüberschauen könntest.. ja ok ich werd's dann mal nochmal so versuchen... danke nochmal!


----------



## Marco13 (25. Nov 2010)

Hat sich hier noch was getan?


----------



## Levitas (25. Nov 2010)

hey marco,
ich bin immer noch am tüfteln und hoffe noch auf hilfe  
aber ich bekomms beim besten willen nicht besser hin...


----------



## LaPhi (5. Jan 2012)

Auch wenn das hier schon etwas älter ist.

Schau dir mal die stelle bei 
	
	
	
	





```
e += step;
```
 genauer an.
Ich glaube in dem Bereich liegt dein Fehler

Mit dem Code läuft es:


```
//slow
             if(dYAbs < dXAbs){
            	 e = -Math.abs(dX);
                 //e = -dXAbs;
            	 d = 2 * Math.abs(dY);
            	 s = 2 * e;
                 
                 while (x != endX){                  
                    drawPoint(framebuffer,x,y,c);
                     x += inc_x;
                     e = e + d;
                     if (e>0){
                         y += inc_y;
                         e = e + s;
                     }
                 }
             }
             else{  //fast
            	 e = -Math.abs(dY);
            	 d = 2 * Math.abs(dX);
            	 s = 2 * e;
                 while (y != endY){
                    drawPoint(framebuffer,x,y,c);
                     y += inc_y;
                     e = e + d;
                     if (e>0){
                         x += inc_x;
                         e = e + s;    
                     }
                 }
             }
             drawPoint(framebuffer,endX,endY,c);
```


----------



## Marco13 (5. Jan 2012)

Da ist der letzte Hilfeschrei wohl untergegangen


----------

