/* $XFree86: xc/programs/Xserver/mi/mizerclip.c,v 1.1 1999/10/13 22:33:13 dawes Exp $ *//***********************************************************Copyright 1987, 1998  The Open GroupAll Rights Reserved.The above copyright notice and this permission notice shall be included inall copies or substantial portions of the Software.THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS ORIMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THEOPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER INAN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR INCONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.Except as contained in this notice, the name of The Open Group shall not beused in advertising or otherwise to promote the sale, use or other dealingsin this Software without prior written authorization from The Open Group.Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts.                        All Rights ReservedPermission to use, copy, modify, and distribute this software and its documentation for any purpose and without fee is hereby granted, provided that the above copyright notice appear in all copies and thatboth that copyright notice and this permission notice appear in supporting documentation, and that the name of Digital not beused in advertising or publicity pertaining to distribution of thesoftware without specific, written prior permission.  DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDINGALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALLDIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES ORANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THISSOFTWARE.******************************************************************/#include <config.h>#include "mi.h"#include "miline.h"/*The bresenham error equation used in the mi/mfb/cfb line routines is:	e = error	dx = difference in raw X coordinates	dy = difference in raw Y coordinates	M = # of steps in X direction	N = # of steps in Y direction	B = 0 to prefer diagonal steps in a given octant,	    1 to prefer axial steps in a given octant	For X major lines:		e = 2Mdy - 2Ndx - dx - B		-2dx <= e < 0	For Y major lines:		e = 2Ndx - 2Mdy - dy - B		-2dy <= e < 0At the start of the line, we have taken 0 X steps and 0 Y steps,so M = 0 and N = 0:	X major	e = 2Mdy - 2Ndx - dx - B		  = -dx - B	Y major	e = 2Ndx - 2Mdy - dy - B		  = -dy - BAt the end of the line, we have taken dx X steps and dy Y steps,so M = dx and N = dy:	X major	e = 2Mdy - 2Ndx - dx - B		  = 2dxdy - 2dydx - dx - B		  = -dx - B	Y major e = 2Ndx - 2Mdy - dy - B		  = 2dydx - 2dxdy - dy - B		  = -dy - BThus, the error term is the same at the start and end of the line.Let us consider clipping an X coordinate.  There are 4 cases whichrepresent the two independent cases of clipping the start vs. theend of the line and an X major vs. a Y major line.  In any of thesecases, we know the number of X steps (M) and we wish to find thenumber of Y steps (N).  Thus, we will solve our error term equation.If we are clipping the start of the line, we will find the smallestN that satisfies our error term inequality.  If we are clipping theend of the line, we will find the largest number of Y steps thatsatisfies the inequality.  In that case, since we are representingthe Y steps as (dy - N), we will actually want to solve for thesmallest N in that equation.Case 1:  X major, starting X coordinate moved by M steps		-2dx <= 2Mdy - 2Ndx - dx - B < 0	2Ndx <= 2Mdy - dx - B + 2dx	2Ndx > 2Mdy - dx - B	2Ndx <= 2Mdy + dx - B		N > (2Mdy - dx - B) / 2dx	N <= (2Mdy + dx - B) / 2dxSince we are trying to find the smallest N that satisfies theseequations, we should use the > inequality to find the smallest:	N = floor((2Mdy - dx - B) / 2dx) + 1	  = floor((2Mdy - dx - B + 2dx) / 2dx)	  = floor((2Mdy + dx - B) / 2dx)Case 1b: X major, ending X coordinate moved to M stepsSame derivations as Case 1, but we want the largest N that satisfiesthe equations, so we use the <= inequality:	N = floor((2Mdy + dx - B) / 2dx)Case 2: X major, ending X coordinate moved by M steps		-2dx <= 2(dx - M)dy - 2(dy - N)dx - dx - B < 0		-2dx <= 2dxdy - 2Mdy - 2dxdy + 2Ndx - dx - B < 0		-2dx <= 2Ndx - 2Mdy - dx - B < 0	2Ndx >= 2Mdy + dx + B - 2dx	2Ndx < 2Mdy + dx + B	2Ndx >= 2Mdy - dx + B		N < (2Mdy + dx + B) / 2dx	N >= (2Mdy - dx + B) / 2dxSince we are trying to find the highest number of Y steps thatsatisfies these equations, we need to find the smallest N, sowe should use the >= inequality to find the smallest:	N = ceiling((2Mdy - dx + B) / 2dx)	  = floor((2Mdy - dx + B + 2dx - 1) / 2dx)	  = floor((2Mdy + dx + B - 1) / 2dx)Case 2b: X major, starting X coordinate moved to M steps from endSame derivations as Case 2, but we want the smallest number of Ysteps, so we want the highest N, so we use the < inequality:	N = ceiling((2Mdy + dx + B) / 2dx) - 1	  = floor((2Mdy + dx + B + 2dx - 1) / 2dx) - 1	  = floor((2Mdy + dx + B + 2dx - 1 - 2dx) / 2dx)	  = floor((2Mdy + dx + B - 1) / 2dx)Case 3: Y major, starting X coordinate moved by M steps		-2dy <= 2Ndx - 2Mdy - dy - B < 0	2Ndx >= 2Mdy + dy + B - 2dy	2Ndx < 2Mdy + dy + B	2Ndx >= 2Mdy - dy + B		N < (2Mdy + dy + B) / 2dx	N >= (2Mdy - dy + B) / 2dxSince we are trying to find the smallest N that satisfies theseequations, we should use the >= inequality to find the smallest:	N = ceiling((2Mdy - dy + B) / 2dx)	  = floor((2Mdy - dy + B + 2dx - 1) / 2dx)	  = floor((2Mdy - dy + B - 1) / 2dx) + 1Case 3b: Y major, ending X coordinate moved to M stepsSame derivations as Case 3, but we want the largest N that satisfiesthe equations, so we use the < inequality:	N = ceiling((2Mdy + dy + B) / 2dx) - 1	  = floor((2Mdy + dy + B + 2dx - 1) / 2dx) - 1	  = floor((2Mdy + dy + B + 2dx - 1 - 2dx) / 2dx)	  = floor((2Mdy + dy + B - 1) / 2dx)Case 4: Y major, ending X coordinate moved by M steps		-2dy <= 2(dy - N)dx - 2(dx - M)dy - dy - B < 0		-2dy <= 2dxdy - 2Ndx - 2dxdy + 2Mdy - dy - B < 0		-2dy <= 2Mdy - 2Ndx - dy - B < 0	2Ndx <= 2Mdy - dy - B + 2dy	2Ndx > 2Mdy - dy - B	2Ndx <= 2Mdy + dy - B		N > (2Mdy - dy - B) / 2dx	N <= (2Mdy + dy - B) / 2dxSince we are trying to find the highest number of Y steps thatsatisfies these equations, we need to find the smallest N, sowe should use the > inequality to find the smallest:	N = floor((2Mdy - dy - B) / 2dx) + 1Case 4b: Y major, starting X coordinate moved to M steps from endSame analysis as Case 4, but we want the smallest number of Y stepswhich means the largest N, so we use the <= inequality:	N = floor((2Mdy + dy - B) / 2dx)Now let's try the Y coordinates, we have the same 4 cases.Case 5: X major, starting Y coordinate moved by N steps		-2dx <= 2Mdy - 2Ndx - dx - B < 0	2Mdy >= 2Ndx + dx + B - 2dx	2Mdy < 2Ndx + dx + B	2Mdy >= 2Ndx - dx + B		M < (2Ndx + dx + B) / 2dy	M >= (2Ndx - dx + B) / 2dySince we are trying to find the smallest M, we use the >= inequality:	M = ceiling((2Ndx - dx + B) / 2dy)	  = floor((2Ndx - dx + B + 2dy - 1) / 2dy)	  = floor((2Ndx - dx + B - 1) / 2dy) + 1Case 5b: X major, ending Y coordinate moved to N stepsSame derivations as Case 5, but we want the largest M that satisfiesthe equations, so we use the < inequality:	M = ceiling((2Ndx + dx + B) / 2dy) - 1	  = floor((2Ndx + dx + B + 2dy - 1) / 2dy) - 1	  = floor((2Ndx + dx + B + 2dy - 1 - 2dy) / 2dy)	  = floor((2Ndx + dx + B - 1) / 2dy)Case 6: X major, ending Y coordinate moved by N steps		-2dx <= 2(dx - M)dy - 2(dy - N)dx - dx - B < 0		-2dx <= 2dxdy - 2Mdy - 2dxdy + 2Ndx - dx - B < 0		-2dx <= 2Ndx - 2Mdy - dx - B < 0	2Mdy <= 2Ndx - dx - B + 2dx	2Mdy > 2Ndx - dx - B	2Mdy <= 2Ndx + dx - B		M > (2Ndx - dx - B) / 2dy	M <= (2Ndx + dx - B) / 2dyLargest # of X steps means smallest M, so use the > inequality:	M = floor((2Ndx - dx - B) / 2dy) + 1Case 6b: X major, starting Y coordinate moved to N steps from endSame derivations as Case 6, but we want the smallest # of X stepswhich means the largest M, so use the <= inequality:	M = floor((2Ndx + dx - B) / 2dy)Case 7: Y major, starting Y coordinate moved by N steps		-2dy <= 2Ndx - 2Mdy - dy - B < 0	2Mdy <= 2Ndx - dy - B + 2dy	2Mdy > 2Ndx - dy - B	2Mdy <= 2Ndx + dy - B		M > (2Ndx - dy - B) / 2dy	M <= (2Ndx + dy - B) / 2dyTo find the smallest M, use the > inequality:	M = floor((2Ndx - dy - B) / 2dy) + 1	  = floor((2Ndx - dy - B + 2dy) / 2dy)	  = floor((2Ndx + dy - B) / 2dy)Case 7b: Y major, ending Y coordinate moved to N stepsSame derivations as Case 7, but we want the largest M that satisfiesthe equations, so use the <= inequality:	M = floor((2Ndx + dy - B) / 2dy)Case 8: Y major, ending Y coordinate moved by N steps		-2dy <= 2(dy - N)dx - 2(dx - M)dy - dy - B < 0		-2dy <= 2dxdy - 2Ndx - 2dxdy + 2Mdy - dy - B < 0		-2dy <= 2Mdy - 2Ndx - dy - B < 0	2Mdy >= 2Ndx + dy + B - 2dy	2Mdy < 2Ndx + dy + B	2Mdy >= 2Ndx - dy + B		M < (2Ndx + dy + B) / 2dy	M >= (2Ndx - dy + B) / 2dyTo find the highest X steps, find the smallest M, use the >= inequality:	M = ceiling((2Ndx - dy + B) / 2dy)	  = floor((2Ndx - dy + B + 2dy - 1) / 2dy)	  = floor((2Ndx + dy + B - 1) / 2dy)Case 8b: Y major, starting Y coordinate moved to N steps from the endSame derivations as Case 8, but we want to find the smallest # of Xsteps which means the largest M, so we use the < inequality:	M = ceiling((2Ndx + dy + B) / 2dy) - 1	  = floor((2Ndx + dy + B + 2dy - 1) / 2dy) - 1	  = floor((2Ndx + dy + B + 2dy - 1 - 2dy) / 2dy)	  = floor((2Ndx + dy + B - 1) / 2dy)So, our equations are:	1:  X major move x1 to x1+M	floor((2Mdy + dx - B) / 2dx)	1b: X major move x2 to x1+M	floor((2Mdy + dx - B) / 2dx)	2:  X major move x2 to x2-M	floor((2Mdy + dx + B - 1) / 2dx)	2b: X major move x1 to x2-M	floor((2Mdy + dx + B - 1) / 2dx)	3:  Y major move x1 to x1+M	floor((2Mdy - dy + B - 1) / 2dx) + 1	3b: Y major move x2 to x1+M	floor((2Mdy + dy + B - 1) / 2dx)	4:  Y major move x2 to x2-M	floor((2Mdy - dy - B) / 2dx) + 1	4b: Y major move x1 to x2-M	floor((2Mdy + dy - B) / 2dx)	5:  X major move y1 to y1+N	floor((2Ndx - dx + B - 1) / 2dy) + 1	5b: X major move y2 to y1+N	floor((2Ndx + dx + B - 1) / 2dy)	6:  X major move y2 to y2-N	floor((2Ndx - dx - B) / 2dy) + 1	6b: X major move y1 to y2-N	floor((2Ndx + dx - B) / 2dy)	7:  Y major move y1 to y1+N	floor((2Ndx + dy - B) / 2dy)	7b: Y major move y2 to y1+N	floor((2Ndx + dy - B) / 2dy)	8:  Y major move y2 to y2-N	floor((2Ndx + dy + B - 1) / 2dy)	8b: Y major move y1 to y2-N	floor((2Ndx + dy + B - 1) / 2dy)We have the following constraints on all of the above terms: