Bresenham Algorithmus

algo n00b schrieb:

der b-algorithmus arbeitet mit ganzen zahlen. für die ansteuerung einer fräschmaschine wohl etwas ungeeignet, oder?

naja, das geht ja noch. blöd ist nur, dass diese bresenham-algos alle für 2d sind. aber bestimmt findet man irgendwo 'ne erweiterung auf 3d. such doch mal im internet nach 'bresenham 3d' (für linien hab' ich schon mal was gesehen).

pointercrash**

Käsekuchen schrieb:

Hallo
Ich soll in der Schule ein Fräsmaschine in 3D ansteuern. Zur Ansteuerung der Motoren zum fräsen von nicht geraden Linien würde ich gerne den Bresenham Algorithmus verwenden. Für 2 Achsen ist mir das Prinzip auch klar, aber leider hab ich irgendwe keinen Plan wie ich das für 3 Achsen verwenden könnte. Ich hab versucht das im Internet zu recherchieren aber irgendwie finde ich da nicht wirklich was. Könnte mir das vielleicht irgendwer erklären? bzw mir vielleicht auch tipps geben wie man so etwas programmiert, weil ich weiß da nicht mehr weiter
lg

Die Erweiterung auf 3D/4D/xD ist völlig trivial, weil Du immer die Achse mit dem längsten Weg ermitteln und anhand derer die Bresenhamdaten für die Folgeachsen.
Bei mir sieht das in einem Dreiachssystem so aus:

// ***********************************************************
// ********** CalcBres ***************************************
// ***********************************************************
/*
Verwendet:
- Relativkoordinaten abs_x, abs_y, abs_z
Berechnet:
- Bresenham- Grunddaten inc_e1, inc_e2, inc_ne1, inc_ne2, d1, d2
- way als längsten Achsweg
Sonstiges:
xyz haben zyklischen Bezug zueinander. 
Führachse x erzeugt d1 etc.		für y- Achse, d2 für z- Achse
Führachse y erzeugt d1 etc.		für z- Achse, d2 für x- Achse
Führachse z erzeugt d1 etc.		für x- Achse, d2 für y- Achse

Entnommen aus:
"Bresenham.doc"
dx:=x2-x1; dy:=y2-y1;
incE:=2*dy; incNE:=2*(dy-dx); 
x:=x1; y:=y1; 
d:=2*dy-dx; 

Beeinflußte BYTE- Flags:
- leader: 'x', 'y', 'z' Kennzeichnet die Führachse mit dem längsten Weg
*/
void CalcBres(long int *abs_x, long int *abs_y, long int *abs_z, long int *way, BYTE *leader, 
			  long int *d1, long int *inc_e1, long int *inc_ne1, 
			  long int *d2, long int *inc_e2, long int *inc_ne2 )
{
	// Führachse ermitteln
	if ((*abs_x >= *abs_y) && (*abs_x >= *abs_z))
		*leader = 'x';
	else
		if (*abs_y >= *abs_z)
			*leader = 'y';
		else
			*leader = 'z';

	switch (*leader)
	{
	case 'x':
		{
			*way = *abs_x;
			// Bresenham- Grunddaten 1. Folgeachse
			*inc_e1		=	((long int) *abs_y *2);	
			*inc_ne1	=	(((long int)*abs_y - (long int)*abs_x) * 2);
			*d1			=	*inc_e1 - (long int)*abs_x;
			// Bresenham- Grunddaten 2. Folgeachse
			*inc_e2		=	((long int) *abs_z *2);	// *2
			*inc_ne2	=	(((long int)*abs_z - (long int)*abs_x) *2);
			*d2			=	*inc_e2 - (long int)*abs_x;
		}
		break;

	case 'y':
		{
			*way = *abs_y;
			// Bresenham- Grunddaten 1. Folgeachse
			*inc_e1		=	((long int)*abs_z * 2);	// *2
			*inc_ne1	=	(((long int)*abs_z - (long int)*abs_y) *2);
			*d1			=	*inc_e1- (long int)*abs_y;
			// Bresenham- Grunddaten 2. Folgeachse
			*inc_e2		=	((long int)*abs_x * 2);	// *2
			*inc_ne2	=	(((long int)*abs_x - (long int)*abs_y) * 2);
			*d2			=	*inc_e2 - (long int)*abs_y;
		}
		break;

	case 'z':
		{
			*way = *abs_z;
			// Bresenham- Grunddaten 1. Folgeachse
			*inc_e1		=	((long int)*abs_x * 2);	// *2
			*inc_ne1	=	(((long int)*abs_x - (long int)*abs_z) * 2);
			*d1			=	*inc_e1 - *abs_z;
			// Bresenham- Grunddaten 2. Folgeachse
			*inc_e2		=	((long int)*abs_y * 2);	// *2
			*inc_ne2	=	(((long int)*abs_y - (long int)*abs_z) * 2);
			*d2			=	*inc_e2 - (long int)*abs_z;
		}
		break;
	}

}

Du hast also kein 3D- Problem, sondern nur mehrfach den "Normalfall" - und das ist wohl einfach zu bewältigen.

pointercrash() schrieb:

void CalcBres(long int *abs_x, long int *abs_y, long int *abs_z, long int *way, BYTE *leader, 
			  long int *d1, long int *inc_e1, long int *inc_ne1, 
			  long int *d2, long int *inc_e2, long int *inc_ne2 )

das sieht struct-verdächtig aus. dann hätteste nur noch ein argument und so.

pointercrash**

Die aktuelle Version funktioniert sowieso ganz anders, aber ich glaube, es macht einfach keinen Sinn, einen Anfänger mit einer rekursiven n-Achsberechnung über Argumentliste zu verwirren.

danke für die ganzen tipps, ist echt super.
Ich werde das mal gleich ausprobieren.

lg und schönen Tag noch

pointercrash**

algo n00b schrieb:

der b-algorithmus arbeitet mit ganzen zahlen. für die ansteuerung einer fräschmaschine wohl etwas ungeeignet, oder?

Dazu muß ich dann doch etwas sagen. Alle digital kontrollierten Systeme bilden letztendlich diskret ab, egal, ob Servo- Driven oder Stepper- Driven.
Beim Servo bekommt man i.d.R. ein diskretes Winkelgebersignal zur Positionskontrolle zurück, während man beim Stepper davon ausgeht, daß die Anzahl der eingespeisten Steps auch den ausgeführten entspricht.
An der Präzision ändert die Ganzzahlsache gar nichts, weil eben 360 Winkelgeberimpulse oder 200 Steps pro mm aus der mechanischen Anordnung hervorgehen. Genauer geht es nicht, weil es keine 200.27 Steps gibt.

C++ Forumbot

Dieser Thread wurde von Moderator/in rüdiger aus dem Forum ANSI C in das Forum Rund um die Programmierung verschoben.

Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

Dieses Posting wurde automatisch erzeugt.

Gregor

Ich habe vor längerer Zeit auch mal einen n-Dimensionalen Bresenham-Algorithmus realisiert. Ist in der Klasse da zu finden. ...etwas weiter unten:

/*
 * LineCaster.java
 *
 * Created on 8. März 2005, 01:25
 */

package jaradap.model.algorithm;

import jaradap.model.algorithm.multiPointProcessor.RaycastProcessor;
import jaradap.model.data.BasicRaster;
import jaradap.model.data.SingleChannelStandardRaster;
import math.linearAlgebra.Vector;

/**
 * This class represents Objects which can analyze lines in a given raster. The analysis
 * projects a line into a single value which is given by a RaycastProcessor, the raster and the line. 
 *
 * @author Gregor
 */
public class LineCaster
{
   private final RaycastProcessor pointProcessor;
   private final SingleChannelStandardRaster raster;
   private final int dimension;

   /** 
    * Creates a new LineCaster with the given parameters.
    *
    * @param pointProcessor This is the RaycastProcessor that will be used to analyze the lines 
    *                       in the method castLine.
    * @param raster This is the raster in that this LineCaster analyzes lines.
    */
   public LineCaster(final RaycastProcessor pointProcessor, final SingleChannelStandardRaster raster)
   {
      this.pointProcessor = pointProcessor;
      this.raster = raster;
      dimension = raster.getDimensions();
   }

   /**
    * This method analyzes the line specified by the parameters startPoint and endPoint. 
    * The pointProcessor of this LineCaster is used to compute the resulting value, while the 
    * raster of this LineCaster is the environment for the analysis.
    *
    * @param startPoint This is the start point of the line.
    * @param endPoint This is the end point of the line.
    * @return The value of the pointProcessor after processing all points of the line inside the raster
    *         will be returned. If the line has no points inside the raster, 0 will be returned.
    */
   public float castLine(final Vector startPoint, final Vector endPoint)
   {
      // Check parameters.
      if (startPoint.getDimension() != dimension)
         throw new IllegalArgumentException("startPoint has wrong dimension.");
      if (endPoint.getDimension() != dimension)
         throw new IllegalArgumentException("endPoint has wrong dimension.");

      // Clip line: 
      // Resulting line is given by rasterStartPoint and rasterEndPoint.
      final int[] rasterStartPoint = new int[dimension];
      final int[] rasterEndPoint = new int[dimension];
      if(!setFirstPointInRaster(rasterStartPoint,startPoint,endPoint)) return 0.0f;
      if(!setFirstPointInRaster(rasterEndPoint,endPoint,startPoint)) return 0.0f;

      // Init helper variables.
      int maxDiffIndex = 0;
      final int[] intDifferences = new int[dimension];
      final int[] relativePosition = new int[dimension];
      final int[] position = new int[dimension];
      final int[] increments = new int[dimension];
      for(int i = 0 ; i < dimension ; ++i)
      {
         intDifferences[i] = rasterEndPoint[i] - rasterStartPoint[i];
         increments[i] = (intDifferences[i] > 0) ? 1 : -1;
         intDifferences[i] = Math.abs(intDifferences[i]);
         if (intDifferences[i] > intDifferences[maxDiffIndex]) maxDiffIndex = i;
         relativePosition[i] = intDifferences[i] >> 1;
         position[i] = rasterStartPoint[i];
      }
      final int maxDifference = intDifferences[maxDiffIndex];
      final int maxIncrement = increments[maxDiffIndex];

      // Process line: 
      // 1. Reset pointProcessor.
      // 2. Process Bresenham-Line-Algorithm
      // 3. Return value of pointProcessor
      pointProcessor.reset();
      for(;position[maxDiffIndex] != rasterEndPoint[maxDiffIndex] ; position[maxDiffIndex] += maxIncrement)
      {
         if (pointProcessor.addPoint(raster,position)) return pointProcessor.getValue();
         for(int i = 0 ; i < dimension ; ++i)
         {
            if (i == maxDiffIndex) continue;
            relativePosition[i] += intDifferences[i];
            if (relativePosition[i] < maxDifference) continue;
            position[i] += increments[i];
            relativePosition[i] -= maxDifference;
         }
      }
      pointProcessor.addPoint(raster,position);
      return pointProcessor.getValue();
   }

   private final boolean setFirstPointInRaster(final int[] target, final Vector firstLinePoint,
                                               final Vector lastLinePoint)
   {
      // Compute the distance of the line's start- and endpoint in each direction.
      final double[] distances = new double[dimension];
      double fraction = 0.0;
      for (int i = 0 ; i < dimension ; ++i)
      {
         distances[i] = (float)(lastLinePoint.getComponent(i) - firstLinePoint.getComponent(i));
      }

      // Compute the fraction that represents the point where the line enters the raster.
      for (int i = 0 ; i < dimension ; ++i)
      {
         double newFraction = 0.0;
         final double component = firstLinePoint.getComponent(i);
         final double difference = distances[i];
         final double maxValue = raster.getSize(i) - 1;
         if (component < 0.0)
         {
            if (difference <= 0.0) return false;
            newFraction = component / difference;
         }
         else if (component > maxValue)
         {
            if (difference >= 0.0) return false;
            newFraction = (component - maxValue) / difference;
         }
         if (newFraction < fraction) fraction = newFraction;
      }

      // Use the fraction to compute the first point of the line that lies within the raster
      // and check if the point really lies within the raster.
      // The point may not lie within the raster if there is no point of the line in the raster.
      for (int i = 0 ; i < dimension ; ++i)
      {
         target[i] = Math.round((float)(firstLinePoint.getComponent(i) - fraction * distances[i]));
         if (target[i] < 0) return false;
         if (target[i] > raster.getSize(i) - 1) return false;
      }
      return true;
   }
}

abc.w

pointercrash() schrieb:

...
	// Führachse ermitteln
	if ((*abs_x >= *abs_y) && (*abs_x >= *abs_z))
		*leader = 'x';
	else
		if (*abs_y >= *abs_z)
			*leader = 'y';
		else
			*leader = 'z';
...

...

Schön ist diese Stelle im Code nicht.
Und bitte, bitte keine Tabulatoren im Quellcode und bitte kein C-Chinesisch... in Anlehnung an die Diskussion hier http://www.c-plusplus.net/forum/viewtopic-var-t-is-229653-and-start-is-40-and-postdays-is-0-and-postorder-is-asc-and-highlight-is-.html

abc.w schrieb:

Schön ist diese Stelle im Code nicht.

stören dich die vielen sternchen?

abc.w

~fricky schrieb:

stören dich die vielen sternchen?

Nein, warum denn nicht so:

*leader = ((*abs_x >= *abs_y) && (*abs_x >= *abs_z)) ? 'x' : (*abs_y >= *abs_z) ? 'y' : 'z';

Aber jetzt im Ernst, ich würde natürlich diese ?: Kombination auch nicht akzeptieren.
Ich habe nichts gegen if else if else Kombination. Es ist nur, dass man 2-3 mal drüberschauen muss, um zu erkennen, was pointercrash() da mit seiner Einrückung gemeint hat. Das ist nicht "soldatensicher" und auch nicht "idiotensicher". Und ich finde, der Konstrukt wäre auf folgende Weise optimal:

if ((*abs_x >= *abs_y) && (*abs_x >= *abs_z))
{
    *leader = 'x';
}
else if (*abs_y >= *abs_z)
{
    *leader = 'y';
}
else
{
    *leader = 'z';
}

^^du hast recht, es ist falsch eingerückt und ich bin voll drauf reingefallen.

Jester

~fricky schrieb:

^^du hast recht, es ist falsch eingerückt und ich bin voll drauf reingefallen.

Was heißt hier falsch eingerückt. Das was der Compiler da rausliest entspricht wohl eher der dargestellten Einrückung. Ich finde zwar auch, dass die andere Variante besser lesbar ist, aber "falsch" ist die dargestellte Einrückung sicher nicht.

Jester schrieb:

~fricky schrieb:

^^du hast recht, es ist falsch eingerückt und ich bin voll drauf reingefallen.

Was heißt hier falsch eingerückt.

der original-code suggeriert aber, dass alles hinter dem ersten else ein zusammengehöriger block ist, also sich dass 'innere' else nur auf das if direkt davor bezieht.

Jester

~fricky schrieb:

Jester schrieb:

~fricky schrieb:

^^du hast recht, es ist falsch eingerückt und ich bin voll drauf reingefallen.

Was heißt hier falsch eingerückt.

der original-code suggeriert aber, dass alles hinter dem ersten else ein zusammengehöriger block ist, also sich dass 'innere' else nur auf das if direkt davor bezieht.

Überraschung: genau so ist es auch. Es gibt kein separates else-if-Konstrukt in C++ -- braucht man ja auch nicht. Mal Dir doch einfach mal den entsprechenden Parse-Baum auf.

es gibt aber sowas:

if (...)
{
 ...
}
else if (...)
{
 ...
}
else if (...)
{
 ...
}
else
{
 ...
}

und verschachtelte konstrukte, wie z.b. das hier:

if (...)
{
  if (...)
  {
   ...
  }
  else 
  {
   ...
  }
}
else 
{
  if (...)
  {
   ...
  }
  else 
  {
   ...
  }
}

nach der irreführenden einrückung von pc() sieht's aus wie ein verschachteltes if...else{if...else}, was es aber in wirklichkeit nicht ist. deswegen ist die einrückung von abc.w besser (auch ohne klammern).

Jester

~fricky schrieb:

nach der irreführenden einrückung von pc() sieht's aus wie ein verschachteltes if...else{if...else}, was es aber in wirklichkeit nicht ist.

Das versuche ich doch die ganze Zeit zu erklären, es *ist* in Wirklichkeit (nämlich so wie es die Grammatik definiert und der Parser parst) ein verschachteltes if ... else {if ... else ...}.

Die Regel für das if sieht in etwa so aus:
statement -> if (bedingung) statement [else statement]

Das nachfolgende zweite if gehört syntaktisch zu dem statement im else-Zweig.

Hier kann man sich's auch anschauen: http://linuxsoftware.co.nz/cppgrammar.html#selection-statement

*schluck*, du hast recht! da programmiert man schon jahrelang in C und hat ein völlig falsches bild von einfachen if/else konstrukten (das dazu noch funktioniert?!).

pointercrash**

Huiui! Hätte nicht gedacht, einen Glaubenskrieg ums Indenting auszulösen . Aber mir erschien das damals einfach so logisch, weil's wirklich geschachtelt ist. Es gibt ja auch kein "else do" oder "else for", weshalb sollte ich genau dem "if" die Einrückung verweigern ?
Ist übrigens auch der Default meines Lieblingseditors.

Jester

pointercrash() schrieb:

Huiui! Hätte nicht gedacht, einen Glaubenskrieg ums Indenting auszulösen . Aber mir erschien das damals einfach so logisch, weil's wirklich geschachtelt ist. Es gibt ja auch kein "else do" oder "else for", weshalb sollte ich genau dem "if" die Einrückung verweigern ?
Ist übrigens auch der Default meines Lieblingseditors.

Das ist doch kein Glaubenskrieg. Wir haben uns eigentlich mit einer rein fachlichen Fragestellung auseinandergesetzt. Ich sagte ja, ich würde es auch nicht einrücken. Ich habe nur der Behauptung die Einrückung sei falsch widersprochen.

Ein Grund warum man auf die Einrückung verzichten könnte, ist dass es sich semantisch eigentlich um drei gleichberechtigte Fälle handelt: es wird genau einer davon angesprochen. Das kommt ohne Einrückung imo deutlicher raus.