/* ---------------------------------------------------------
   Bresenham Line Drawing Alogrithm

   This is a Prolog implementation of the bresenham line drawing
   algorithm, used for 2D ray tracing. The coordinate system used
   has its origin at the top left, and the first coordinate is the
   offset to the left, i.e.:
   [0,0] ............. [n,0]
    ...
   [m,0] ............. [n,m]

   -------------------------------------------------------------
   @author: Christian Fritz <fritz at cs toronto edu>

   @date: 22.7.2008
   -------------------------------------------------------------

   This program is free software: you can redistribute it and/or
   modify it under the terms of the GNU General Public License as
   published by the Free Software Foundation, either version 3 of
   the License, or (at your option) any later version.
   
   This program is distributed in the hope that it will be
   useful, but WITHOUT ANY WARRANTY; without even the implied
   warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
   PURPOSE. See the GNU General Public License for more details.
   
   You should have received a copy of the GNU General Public
   License along with this program. If not, see
   <http://www.gnu.org/licenses/>.
   
   --------------------------------------------------------- */

/** bresenham(+[X1,Y1], +[X2,Y2], -Trail) holds iff Trail is the
 ** list of points [X,Y] traversed when moving from [X1,Y1] to
 ** [X2,Y2] */
bresenham( [X1, Y1], [X2, Y2], Trail) :-
	Steps is abs(Y2 - Y1) + abs(X2 - X1),
	( Y2 > Y1 -> IncY = 1 ; IncY = -1),
	( X2 > X1 -> IncX = 1 ; IncX = -1),
	IncAuxY is (X2-X1) * IncY,
	IncAuxX is (Y1-Y2) * IncX,
	Aux1 is 2 * (IncAuxX - IncAuxY),
	Aux2 is (IncAuxY * IncAuxY - IncAuxX * IncAuxX),
	bresenham_aux( Steps, [X1,Y1], 0, Aux1, Aux2,
		       [IncX, IncY], [IncAuxX, IncAuxY], Trail).

/* -------------------------------
   Auxiliaries
*/

bresenham_aux( 0, [X,Y], _A, _A1, _A2, _I, _IA, [[X,Y]]) :- !.
bresenham_aux( Steps, [X,Y], Aux, Aux1, Aux2,
	       [IncX, IncY], [IncAuxX, IncAuxY], [[X,Y]|TrailT]) :-
	(
	  Aux * Aux1 =< Aux2
	->
	  NY = Y,
	  NX is X + IncX,
	  NAux is Aux + IncAuxX
	;
	  NX = X,
	  NY is Y + IncY,
	  NAux is Aux + IncAuxY
	),
	NSteps is Steps - 1,
	bresenham_aux( NSteps, [NX,NY], NAux, Aux1, Aux2, [IncX, IncY],
		       [IncAuxX, IncAuxY], TrailT).