/*
* Copyright (c) 1998 by The XFree86 Project, Inc.
*
* Permission is hereby granted, free of charge, to any person obtaining a
* copy of this software and associated documentation files (the "Software"),
* to deal in the Software without restriction, including without limitation
* the rights to use, copy, modify, merge, publish, distribute, sublicense,
* and/or sell copies of the Software, and to permit persons to whom the
* Software is furnished to do so, subject to the following conditions:
*
* The above copyright notice and this permission notice shall be included in
* all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
* THE XFREE86 PROJECT BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
* WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF
* OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
* SOFTWARE.
*
* Except as contained in this notice, the name of the XFree86 Project shall
* not be used in advertising or otherwise to promote the sale, use or other
* dealings in this Software without prior written authorization from the
* XFree86 Project.
*/
/* $XFree86: xc/lib/Xmu/Clip.c,v 1.1 1998/08/16 10:25:03 dawes Exp $ */
#ifdef HAVE_CONFIG_H
#include <config.h>
#endif
#include <stdlib.h>
#include <X11/IntrinsicP.h>
#include <X11/Xmu/Xmu.h>
#define XmuMax(a, b) ((a) > (b) ? (a) : (b))
#define XmuMin(a, b) ((a) < (b) ? (a) : (b))
/*
* Function:
* XmuNewArea
*
* Parameters:
* x1 - Coordinates of the rectangle
* y1 - ""
* x2 - ""
* y2 - ""
*
* Description:
* Creates a new rectangular clipping area
*/
XmuArea *
XmuNewArea(int x1, int y1, int x2, int y2)
{
XmuArea *area;
area = (XmuArea *)XtMalloc(sizeof(XmuArea));
if (x2 > x1 && y2 > y1)
{
area->scanline = XmuNewScanline(y1, x1, x2);
area->scanline->next = XmuNewScanline(y2, 0, 0);
}
else
area->scanline = (XmuScanline *)NULL;
return (area);
}
/*
* Function:
* XmuAreaDup
*
* Parameters:
* area - Area to copy
*
* Description:
* Returns a copy of its argument
*/
XmuArea *
XmuAreaDup(XmuArea *area)
{
XmuArea *dst;
if (!area)
return ((XmuArea *)NULL);
dst = XmuCreateArea();
XmuAreaCopy(dst, area);
return (dst);
}
/*
* Function:
* XmuAreaCopy
*
* Parameters:
* dst - destination area
* src - source area
*
* Description:
* Minimizes memory alocation, trying to use already alocated memory
* in dst, freeing what is not required anymore.
*/
XmuArea *
XmuAreaCopy(XmuArea *dst, XmuArea *src)
{
XmuScanline *z, *p, *Z;
if (!dst || !src || dst == src)
return (dst);
z = p = dst->scanline;
Z = src->scanline;
/*CONSTCOND*/
while (1)
{
if (!Z)
{
if (z == dst->scanline)
{
XmuDestroyScanlineList(dst->scanline);
dst->scanline = (XmuScanline *)NULL;
}
else
{
XmuDestroyScanlineList(p->next);
p->next = (XmuScanline *)NULL;
}
return (dst);
}
if (z)
{
XmuScanlineCopy(z, Z);
z->y = Z->y;
}
else
{
z = XmuNewScanline(Z->y, 0, 0);
XmuScanlineCopy(z, Z);
if (p == dst->scanline && !dst->scanline)
p = dst->scanline = z;
else
p->next = z;
}
p = z;
z = z->next;
Z = Z->next;
}
return (dst);
}
/*
* Function:
* XmuAreaNot
*
* Parameters:
* area - area to operate
* x1 - retangle to clip the result against
* y1 - ""
* x2 - ""
* y2 - ""
*
* Description:
* (Input)
* (x1, y1) (x2, y1)
* +-------------+
* +------------+ +----+
* | +--------------+
* +----------------+
* (x1, y2) (x2, y2)
*
* (Output)
* (x1, y1) (x2, y1)
* +--------------+ +--------------------------+
* | +------------+ +----+ |
* | | +--------------+ |
* +-+ +------------------------------------+
* (x1, y2) (x2, y2)
*/
XmuArea *
XmuAreaNot(XmuArea *area, int x1, int y1, int x2, int y2)
{
XmuScanline *z;
XmuArea *and;
if (!area)
return (area);
if (x1 > x2)
{
x1 ^= x2; x2 ^= x1; x1 ^= x2;
}
if (y1 > y2)
{
y1 ^= y2; y2 ^= y1; y1 ^= y2;
}
if (!area->scanline)
{
if ((area->scanline = XmuNewScanline(y1, x1, x2)) != NULL)
area->scanline->next = XmuNewScanline(y2, 0, 0);
return (area);
}
and = XmuNewArea(x1, y1, x2, y2);
XmuAreaAnd(area, and);
XmuDestroyArea(and);
z = area->scanline;
if (z->y != y1)
{
XmuScanline *q = XmuNewScanline(y1, x1, x2);
q->next = z;
area->scanline = q;
}
else
{
area->scanline = area->scanline->next;
XmuDestroyScanline(z);
XmuOptimizeArea(area);
if((z = area->scanline) == (XmuScanline *)NULL)
return (area);
}
/* CONSTCOND */
while (1)
{
XmuScanlineNot(z, x1, x2);
if (!z->next)
{
z->next = XmuNewScanline(y2, 0, 0);
break;
}
if (z->next->y == y2)
{
XmuDestroyScanlineList(z->next);
z->next = XmuNewScanline(y2, 0, 0);
break;
}
z = z->next;
}
return (area);
}
/*
* Function:
* XmuAreaOrXor
*
* Parameters:
* dst - destination area
* src - source area
* or - or operation if true, else xor operation
*
* Description:
* Executes Or (Union) or Xor (Reverse intesection) of the areas
*/
XmuArea *
XmuAreaOrXor(XmuArea *dst, XmuArea *src, Bool or)
{
XmuScanline *z, *p, *Z, *P, *ins, *top;
if (!dst || !src)
return (dst);
if (dst == src)
{
if (or)
return (dst);
XmuDestroyScanlineList(dst->scanline);
dst->scanline = (XmuScanline *)NULL;
return (dst);
}
if (!XmuValidArea(src))
return (dst);
if (!XmuValidArea(dst))
{
XmuAreaCopy(dst, src);
return (dst);
}
p = z = dst->scanline;
P = Z = src->scanline;
ins = XmuNewScanline(dst->scanline->y, 0, 0);
top = XmuNewScanline(dst->scanline->y, 0, 0);
XmuScanlineCopy(ins, dst->scanline);
XmuScanlineCopy(top, dst->scanline);
/*CONSTCOND*/
while (1)
{
if (!Z)
break;
else if (Z->y < z->y)
{
XmuScanline *q = XmuNewScanline(Z->y, 0, 0);
XmuScanlineCopy(q, Z);
if (z == dst->scanline)
{
dst->scanline = p = q;
q->next = z;
}
else
{
p->next = q;
q->next = z;
if (Z->y >= p->y)
{
if (ins->y >= top->y
&& (p->y != P->y || !XmuScanlineEqu(p, P)
|| (ins->y <= P->y && !XmuScanlineEqu(ins, P))))
{
if (or)
XmuScanlineOr(q, ins);
else
XmuScanlineXor(q, ins);
}
else if (Z->y >= top->y
&& (top->y == p->y || top->y > ins->y
|| !XmuValidScanline(Z)
|| (p->y == P->y && XmuValidScanline(p)
&& XmuValidScanline(P))
|| XmuScanlineEqu(ins, top)))
{
if (or)
XmuScanlineOr(q, top);
else
XmuScanlineXor(q, top);
}
if (ins->y != p->y && p->y != P->y)
{
XmuScanlineCopy(ins, p);
ins->y = p->y;
}
}
if (!XmuValidScanline(p) || Z->y <= p->y)
{
XmuScanlineCopy(top, p);
top->y = p->y;
}
p = q;
}
P = Z;
Z = Z->next;
continue;
}
else if (Z->y == z->y)
{
if (top->y != z->y)
{
XmuScanlineCopy(top, z);
top->y = z->y;
}
if (or)
XmuScanlineOr(z, Z);
else
XmuScanlineXor(z, Z);
P = Z;
Z = Z->next;
}
else if (P != Z) /* && Z->y > z->y */
{
if (top->y == ins->y && top->y != z->y)
{
XmuScanlineCopy(top, z);
top->y = z->y;
}
if (ins->y != z->y)
{
XmuScanlineCopy(ins, z);
ins->y = z->y;
}
if (or)
XmuScanlineOr(z, P);
else
XmuScanlineXor(z, P);
}
else if (ins->y != z->y)
{
XmuScanlineCopy(ins, z);
ins->y = z->y;
}
p = z;
z = z->next;
if (!z)
{
while (Z)
{
p->next = XmuNewScanline(Z->y, 0, 0);
XmuScanlineCopy(p->next, Z);
p = p->next;
Z = Z->next;
}
break;
}
else if (ins->y > top->y && !XmuValidScanline(z)
&& XmuValidScanline(ins))
{
XmuScanlineCopy(top, ins);
top->y = ins->y;
}
}
XmuOptimizeArea(dst);
XmuDestroyScanline(ins);
XmuDestroyScanline(top);
return (dst);
}
/*
* Function:
* XmuAreaAnd(dst, src)
*
* Parameters:
* dst - destination area
* src - source area
*
* Description:
* Executes And (intersection) of the areas
*/
XmuArea *
XmuAreaAnd(XmuArea *dst, XmuArea *src)
{
XmuScanline *z, *p, *Z, *P, *top;
if (!dst || !src || dst == src)
return (dst);
if (!XmuValidArea(dst) || !XmuValidArea(src))
{
XmuDestroyScanlineList(dst->scanline);
dst->scanline = (XmuScanline *)NULL;
return (dst);
}
z = p = dst->scanline;
Z = P = src->scanline;
top = XmuNewScanline(dst->scanline->y, 0, 0);
XmuScanlineCopy(top, dst->scanline);
while (z)
{
while (Z->next && Z->next->y < z->y)
{
P = Z;
Z = Z->next;
if (Z->y >= p->y)
{
XmuScanline *q = XmuNewScanline(Z->y, 0, 0);
XmuScanlineCopy(q, Z);
XmuScanlineAnd(q, top);
if (p->y != P->y)
{
XmuScanlineAnd(p, P);
p->y = XmuMax(p->y, P->y);
}
p->next = q;
q->next = z;
p = q;
}
}
if (!z->next)
{
z->y = XmuMax(z->y, Z->y);
break;
}
while (Z->y >= z->next->y)
{
if (z == dst->scanline)
{
p = dst->scanline = dst->scanline->next;
XmuDestroyScanline(z);
z = dst->scanline;
}
else
{
p->next = z->next;
XmuDestroyScanline(z);
z = p;
}
if (!z || !z->next)
{
XmuOptimizeArea(dst);
XmuDestroyScanline(top);
return (dst);
}
}
if (Z->y > p->y)
z->y = XmuMax(z->y, Z->y);
if (top->y != z->y)
{
XmuScanlineCopy(top, z);
top->y = z->y;
}
XmuScanlineAnd(z, Z);
p = z;
z = z->next;
}
XmuOptimizeArea(dst);
XmuDestroyScanline(top);
return (dst);
}
/*
* Function:
* XmuValidArea(area)
*
* Parameters:
* area - area to verify
*
* Description:
* Verifies if the area is valid and/or useful
*/
Bool
XmuValidArea(XmuArea *area)
{
XmuScanline *at;
if (!area || !area->scanline)
return (False);
at = area->scanline;
while (at)
{
if (XmuValidScanline(at))
return (True);
at = at->next;
}
return (False);
}
/*
* Function:
* XmuValidScanline
*
* Parameters:
* scanline - scanline to verify
*
* Description:
* Verifies if a scanline is useful
*/
Bool
XmuValidScanline(XmuScanline *scanline)
{
XmuSegment *z;
if (!scanline)
return (False);
z = scanline->segment;
while (z)
{
if (XmuValidSegment(z))
return (True);
z = z->next;
}
return (False);
}
/*
* Function:
* XmuScanlineEqu
*
* Parameters:
* s1 - scanline 1
* s2 - scanline 2
*
* Description:
* Checks if s1 and s2 are equal
*/
Bool
XmuScanlineEqu(XmuScanline *s1, XmuScanline *s2)
{
XmuSegment *z, *Z;
if ((!s1 && !s2) || s1 == s2)
return (True);
if (!s1 || !s2)
return (False);
z = s1->segment;
Z = s2->segment;
/*CONSTCOND*/
while (1)
{
if (!z && !Z)
return (True);
if (!z || !Z)
return (False);
if (!XmuSegmentEqu(z, Z))
return (False);
z = z->next;
Z = Z->next;
}
/*NOTREACHED*/
}
/*
* Function:
* XmuNewSegment
*
* Parameters:
* x1 - coordinates of the segment
* x2 - ""
*
* Description:
* Creates a new segments with the coordinates x1 and x2
*
* Returns:
* New Segment of NULL
*/
XmuSegment *
XmuNewSegment(int x1, int x2)
{
XmuSegment *segment;
if ((segment = (XmuSegment *)XtMalloc(sizeof(XmuSegment))) == NULL)
return (segment);
segment->x1 = x1;
segment->x2 = x2;
segment->next = (XmuSegment *)NULL;
return (segment);
}
/*
* Function:
* XmuDestroySegmentList
*
* Parameters:
* segment - Segment to destroy
*
* Description:
* Frees the memory used by the list headed by segment
*/
void
XmuDestroySegmentList(XmuSegment *segment)
{
XmuSegment *z;
if (!segment)
return;
while (segment)
{
z = segment;
segment = segment->next;
XmuDestroySegment(z);
}
}
/*
* Function:
* XmuScanlineCopy
*
* Parameters:
* dst - destination scanline
* src - source scanline
*
* Description:
* Makes dst contain the same data as src
*/
XmuScanline *
XmuScanlineCopy(XmuScanline *dst, XmuScanline *src)
{
XmuSegment *z, *p, *Z;
if (!dst || !src || dst == src)
return (dst);
z = p = dst->segment;
Z = src->segment;
/*CONSTCOND*/
while (1)
{
if (!Z)
{
if (z == dst->segment)
dst->segment = (XmuSegment *)NULL;
else
p->next = (XmuSegment *)NULL;
XmuDestroySegmentList(z);
return (dst);
}
if (z)
{
z->x1 = Z->x1;
z->x2 = Z->x2;
}
else
{
z = XmuNewSegment(Z->x1, Z->x2);
if (p == dst->segment && !dst->segment)
p = dst->segment = z;
else
p->next = z;
}
p = z;
z = z->next;
Z = Z->next;
}
/*NOTREACHED*/
}
/*
* Function:
* XmuAppendSegment
*
* Parameters:
* segment - destination segment
* append - segment to add
*
* Description:
* Adds a copy of the append list at the end of the segment list
*/
Bool
XmuAppendSegment(XmuSegment *segment, XmuSegment *append)
{
if (!segment || !append)
return (False);
if (segment->next)
/* Should not happen! */
XmuDestroySegmentList(segment->next);
while (append)
{
if (XmuValidSegment(append))
{
if ((segment->next = XmuNewSegment(append->x1, append->x2)) == NULL)
return (False);
segment = segment->next;
}
append = append->next;
}
return (True);
}
/*
* Function:
* XmuOptimizeScanline
*
* Parameters:
* scanline - scanline to optimize
*
* Description:
* Some functions, when transforming Segments of Scanlines, left these
* with unnecessary data (that may cause error in these same functions).
* This function corrects these incorrect segments.
*/
XmuScanline *
XmuOptimizeScanline(XmuScanline *scanline)
{
XmuSegment *z, *p;
while (scanline->segment && !XmuValidSegment(scanline->segment))
{
XmuSegment *s = scanline->segment;
scanline->segment = scanline->segment->next;
XmuDestroySegment(s);
}
for (z = p = scanline->segment; z; p = z, z = z->next)
{
if (!XmuValidSegment(z))
{
p->next = z->next;
XmuDestroySegment(z);
z = p;
}
}
return (scanline);
}
/*
* Name:
* XmuScanlineNot(scanline, minx, maxx)
*
* Parameters:
* scanline - scanlines operate
* minx - minimum x coordinate
* maxx - maximum x coordinate
*
* Description:
* (minx) (maxx)
* + +
* (input) +---------+ +--------+ +--------+
* (output) +-----+ +-----+ +--------+ +------------+
*/
XmuScanline *
XmuScanlineNot(XmuScanline *scanline, int minx, int maxx)
{
XmuSegment *z;
static XmuSegment x = { 0, 0, 0 };
static XmuScanline and = { 0, &x, 0 };
if (!scanline)
return (scanline);
XmuOptimizeScanline(scanline);
if (minx > maxx)
{
minx ^= maxx; maxx ^= minx; minx ^= maxx;
}
and.segment->x1 = minx;
and.segment->x2 = maxx;
XmuScanlineAnd(scanline, &and);
if (!scanline->segment)
{
scanline->segment = XmuNewSegment(minx, maxx);
return (scanline);
}
z = scanline->segment;
if (z->x1 != minx)
{
XmuSegment *q = XmuNewSegment(minx, z->x1);
q->next = z;
scanline->segment = q;
}
/*CONSTCOND*/
while (1)
{
z->x1 = z->x2;
if (!z->next)
{
z->x2 = maxx;
break;
}
z->x2 = z->next->x1;
if (z->next->x2 == maxx)
{
XmuDestroySegment(z->next);
z->next = (XmuSegment *)NULL;
break;
}
z = z->next;
}
return (scanline);
}
#ifndef notdef
/*
* Function:
* XmuScanlineOrSegment
*
* Parameters:
* dst - destionation scanline
* src - source segment
*
* Description:
* (input) +-----------+ +--------+ +---------+
* (src) +-------------------+
* (output) +-------------------------+ +---------+
*/
XmuScanline *
XmuScanlineOrSegment(XmuScanline *dst, XmuSegment *src)
{
XmuSegment *z, *p, ins;
if (!src || !dst || !XmuValidSegment(src))
return (dst);
if (!dst->segment)
{
dst->segment = XmuNewSegment(src->x1, src->x2);
return (dst);
}
z = p = dst->segment;
ins.x1 = src->x1;
ins.x2 = src->x2;
/*CONSTCOND*/
while (1)
{
if (!z)
{
XmuSegment *q = XmuNewSegment(ins.x1, ins.x2);
if (p == dst->segment && z == p)
dst->segment = q;
else
p->next = q;
break;
}
else if (ins.x2 < z->x1)
{
XmuSegment *q = XmuNewSegment(ins.x1, ins.x2);
if (p == dst->segment && z == p)
{
q->next = dst->segment;
dst->segment = q;
}
else
{
p->next = q;
q->next = z;
}
break;
}
else if (ins.x2 <= z->x2)
{
z->x1 = XmuMin(z->x1, ins.x1);
break;
}
else if (ins.x1 <= z->x2)
{
ins.x1 = XmuMin(z->x1, ins.x1);
if (!z->next)
{
z->x1 = ins.x1;
z->x2 = ins.x2;
break;
}
else
{
if (z == dst->segment)
{
p = dst->segment = dst->segment->next;
XmuDestroySegment(z);
z = dst->segment;
continue;
}
else
{
p->next = z->next;
XmuDestroySegment(z);
z = p;
}
}
}
p = z;
z = z->next;
}
return (dst);
}
/*
* Function:
* XmuScanlineAndSegment
*
* Parameters:
* dst - destination scanline
* src - source segment
*
* Description:
* (input) +------------+ +------+ +----------+
* (src) +---------------------+
* (output) +-------+ +------+
*/
XmuScanline *
XmuScanlineAndSegment(XmuScanline *dst, XmuSegment *src)
{
XmuSegment *z, *p;
if (!dst || !src)
return (dst);
if (!XmuValidSegment(src))
{
XmuDestroySegmentList(dst->segment);
dst->segment = (XmuSegment *)NULL;
return (dst);
}
if (!dst->segment)
return (dst);
z = p = dst->segment;
while (z)
{
if (src->x2 <= z->x1 || src->x1 >= z->x2)
{
if (z == dst->segment)
{
p = dst->segment = dst->segment->next;
XmuDestroySegment(z);
z = dst->segment;
continue;
}
else
{
p->next = z->next;
XmuDestroySegment(z);
z = p;
}
}
else
{
z->x1 = XmuMax(z->x1, src->x1);
z->x2 = XmuMin(z->x2, src->x2);
}
p = z;
z = z->next;
}
return (dst);
}
/*
* Function:
* XmuScanlineXorSegment
*
* Parameters:
* dst - destionation scanline
* src - source segment
*
* Descriptipn:
* (input) +------------+ +----------+ +-----------+
* (src) +------------------------+
* (output) +---+ +--+ +-+ +-----------+
*/
XmuScanline *
XmuScanlineXorSegment(XmuScanline *dst, XmuSegment *src)
{
XmuSegment *p, *z, ins;
int tmp1, tmp2;
if (!dst || !src || !XmuValidSegment(src))
return (dst);
if (!dst->segment)
{
dst->segment = XmuNewSegment(src->x1, src->x2);
return (dst);
}
p = z = dst->segment;
ins.x1 = src->x1;
ins.x2 = src->x2;
/*CONSTCOND*/
while (1)
{
if (!XmuValidSegment((&ins)))
break;
if (!z || ins.x2 < z->x1)
{
XmuSegment *q = XmuNewSegment(ins.x1, ins.x2);
q->next = z;
if (z == dst->segment)
dst->segment = q;
else
p->next = q;
break;
}
else if (ins.x2 == z->x1)
{
z->x1 = ins.x1;
break;
}
else if (ins.x1 < z->x2)
{
if (ins.x1 < z->x1)
{
tmp1 = ins.x2;
tmp2 = z->x2;
ins.x2 = XmuMax(ins.x2, z->x2);
z->x2 = z->x1;
z->x1 = ins.x1;
ins.x1 = XmuMin(tmp1, tmp2);
}
else if (ins.x1 > z->x1)
{
tmp1 = ins.x1;
ins.x1 = XmuMin(ins.x2, z->x2);
ins.x2 = XmuMax(z->x2, ins.x2);
z->x2 = tmp1;
}
else /* ins.x1 == z->x1 */
{
if (ins.x2 < z->x2)
{
z->x1 = ins.x2;
break;
}
else
{
ins.x1 = z->x2;
if (z == dst->segment)
p = dst->segment = dst->segment->next;
else
p->next = z->next;
XmuDestroySegment(z);
z = p;
continue;
}
}
}
else if (ins.x1 == z->x2)
{
ins.x1 = z->x1;
if (z == dst->segment)
p = dst->segment = dst->segment->next;
else
p->next = z->next;
XmuDestroySegment(z);
z = p;
continue;
}
p = z;
z = z->next;
}
return (dst);
}
#endif /* notdef */
/*
* Function:
* ScanlineOr
*
* Parameters:
* dst - destionation scanline
* src - source scanline
*
* Description:
* (input) +--------------+ +-----+ +----------+
* (src) +---------------------+ +-----------+
* (output) +-------------------------+ +----------------+
*/
XmuScanline *
XmuScanlineOr(XmuScanline *dst, XmuScanline *src)
{
XmuSegment *z, *p, *Z, ins;
if (!src || !src->segment || !dst || dst == src)
return (dst);
if (!dst->segment)
{
XmuScanlineCopy(dst, src);
return (dst);
}
z = p = dst->segment;
Z = src->segment;
ins.x1 = Z->x1;
ins.x2 = Z->x2;
/*CONSTCOND*/
while (1)
{
while (!XmuValidSegment((&ins)))
{
if ((Z = Z->next) == (XmuSegment *)NULL)
return (dst);
ins.x1 = Z->x1;
ins.x2 = Z->x2;
}
if (!z)
{
XmuSegment *q = XmuNewSegment(ins.x1, ins.x2);
if (p == dst->segment && z == p)
dst->segment = p = q;
else
{
p->next = q;
p = q;
}
Z = Z->next;
XmuAppendSegment(p, Z);
break;
}
else if (ins.x2 < z->x1)
{
XmuSegment *r = XmuNewSegment(ins.x1, ins.x2);
if (p == dst->segment && z == p)
{
r->next = dst->segment;
dst->segment = p = r;
}
else
{
p->next = r;
r->next = z;
p = r;
}
Z = Z->next;
if (!Z)
break;
else
{
ins.x1 = Z->x1;
ins.x2 = Z->x2;
continue;
}
}
else if (ins.x2 <= z->x2)
{
z->x1 = XmuMin(z->x1, ins.x1);
Z = Z->next;
if (!Z)
break;
else
{
ins.x1 = Z->x1;
ins.x2 = Z->x2;
continue;
}
}
else if (ins.x1 <= z->x2)
{
ins.x1 = XmuMin(z->x1, ins.x1);
if (!z->next)
{
z->x1 = ins.x1;
z->x2 = ins.x2;
p = z;
Z = Z->next;
XmuAppendSegment(p, Z);
break;
}
else
{
if (z == dst->segment)
{
p = dst->segment = dst->segment->next;
XmuDestroySegment(z);
z = p;
continue;
}
else
{
p->next = z->next;
XmuDestroySegment(z);
z = p;
}
}
}
p = z;
z = z->next;
}
return (dst);
}
/*
* Function:
* XmuScanlineAnd
*
* Parameters:
* dst - destination scanline
* src - source scanline
*
* Description:
* (input) +--------------+ +-----+ +----------+
* (src) +---------------------+ +-----------+
* (output) +----------+ +-----+ +-----+
*/
XmuScanline *
XmuScanlineAnd(XmuScanline *dst, XmuScanline *src)
{
XmuSegment *z, *p, *Z;
if (!dst || !src || dst == src || !dst->segment) {
return (dst);
}
if (!src->segment)
{
XmuDestroySegmentList(dst->segment);
dst->segment = (XmuSegment *)NULL;
return (dst);
}
z = p = dst->segment;
Z = src->segment;
while (z)
{
while (!XmuValidSegment(Z) || Z->x2 <= z->x1)
{
Z = Z->next;
if (!Z)
{
if (z == dst->segment)
dst->segment = (XmuSegment *)NULL;
else
p->next = (XmuSegment *)0;
XmuDestroySegmentList(z);
return (dst);
}
}
if (Z->x1 >= z->x2)
{
if (z == dst->segment)
{
p = dst->segment = dst->segment->next;
XmuDestroySegment(z);
z = dst->segment;
}
else
{
p->next = z->next;
XmuDestroySegment(z);
z = p->next;
}
if (!z)
return (dst);
else
continue;
}
z->x1 = XmuMax(z->x1, Z->x1);
if (z->x2 > Z->x2)
{
if (Z->next)
{
XmuSegment *q = XmuNewSegment(Z->x2, z->x2);
q->next = z->next;
z->next = q;
}
z->x2 = Z->x2;
}
p = z;
z = z->next;
}
return (dst);
}
/*
* Function:
* ScanlineXor
*
* Parameters:
* dst - destination scanline
* src - source scanline
*
* Description:
* (input) +--------------+ +-----+ +----------+
* (src) +---------------------+ +-----------+
* (output) +---+ +--+ +-+ +----+ +-----+
*/
XmuScanline *
XmuScanlineXor(XmuScanline *dst, XmuScanline *src)
{
XmuSegment *z, *p, *Z, ins;
int tmp1, tmp2;
if (!src || !dst || !src->segment)
return (dst);
if (src == dst)
{
XmuDestroySegmentList(dst->segment);
dst->segment = (XmuSegment *)NULL;
return (dst);
}
if (!dst->segment)
{
XmuScanlineCopy(dst, src);
return (dst);
}
z = p = dst->segment;
Z = src->segment;
ins.x1 = Z->x1;
ins.x2 = Z->x2;
/*CONSTCOND*/
while (1)
{
while (!XmuValidSegment((&ins)))
{
if ((Z = Z->next) == (XmuSegment *)NULL)
return (dst);
ins.x1 = Z->x1;
ins.x2 = Z->x2;
}
if (!z)
{
XmuSegment *q = XmuNewSegment(ins.x1, ins.x2);
if (!dst->segment)
dst->segment = q;
else
p->next = q;
p = q;
Z = Z->next;
XmuAppendSegment(p, Z);
break;
}
else if (ins.x2 < z->x1)
{
XmuSegment *q = XmuNewSegment(ins.x1, ins.x2);
q->next = z;
if (z == dst->segment)
dst->segment = q;
else
p->next = q;
if ((Z = Z->next) == (XmuSegment *)NULL)
return (dst);
p = q;
ins.x1 = Z->x1;
ins.x2 = Z->x2;
continue;
}
else if (ins.x2 == z->x1)
{
z->x1 = ins.x1;
if ((Z = Z->next) == (XmuSegment *)NULL)
break;
ins.x1 = Z->x1;
ins.x2 = Z->x2;
continue;
}
else if (ins.x1 < z->x2)
{
if (ins.x1 == z->x1)
{
if (ins.x2 < z->x2)
{
z->x1 = ins.x2;
if ((Z = Z->next) == (XmuSegment *)NULL)
break;
ins.x1 = Z->x1;
ins.x2 = Z->x2;
continue;
}
else
{
ins.x1 = z->x2;
if (z == dst->segment)
p = dst->segment = dst->segment->next;
else
p->next = z->next;
XmuDestroySegment(z);
z = p;
continue;
}
}
else
{
if (Z->x2 < z->x2)
{
XmuSegment *q = XmuNewSegment(XmuMin(ins.x1, z->x1),
XmuMax(z->x1, ins.x1));
q->next = z;
if (z == dst->segment)
dst->segment = q;
else
p->next = q;
ins.x1 = z->x2;
z->x1 = ins.x2;
p = q;
continue;
}
else
{
tmp1 = ins.x2;
tmp2 = z->x2;
ins.x2 = XmuMax(ins.x2, z->x2);
z->x2 = XmuMax(z->x1, ins.x1);
z->x1 = XmuMin(ins.x1, z->x1);
ins.x1 = XmuMin(tmp1, tmp2);
}
}
}
else if (ins.x1 == z->x2)
{
ins.x1 = z->x1;
if (z == dst->segment)
p = dst->segment = dst->segment->next;
else
p->next = z->next;
XmuDestroySegment(z);
z = p;
continue;
}
p = z;
z = z->next;
}
return (dst);
}
/*
* Function:
* XmuNewScanline
*
* Parameters:
* y - y coordinate
* x1 - left coordinate
* x2 - right coordinate
*
* Description:
* Creates a new Scanline
*/
XmuScanline *
XmuNewScanline(int y, int x1, int x2)
{
XmuScanline *scanline;
scanline = (XmuScanline *)XtMalloc(sizeof(XmuScanline));
scanline->y = y;
if (x1 < x2)
scanline->segment = XmuNewSegment(x1, x2);
else
scanline->segment = (XmuSegment *)NULL;
scanline->next = (XmuScanline *)NULL;
return (scanline);
}
/*
* Function:
* XmuDestroyScanlineList
*
* Parameters:
* scanline - scanline list to destroy
*
* Description:
* Destroy a scanline list
*
* Observation:
* Use as follow:
* XmuDestroyScanlineList(area->scanline);
* area->scanline = (XmuScanline *)NULL;
*/
void
XmuDestroyScanlineList(XmuScanline *scanline)
{
XmuScanline *z;
if (!scanline)
return;
while (scanline)
{
z = scanline;
scanline = scanline->next;
XmuDestroyScanline(z);
}
}
/*
* Function:
* XmuOptimizeArea
*
* Parameters:
* area - area to optimize
*
* Description:
* Optimizes an area. This function is called when finishing a
* operation between areas, since they can end with redundant data,
* and the algorithms for area combination waits a area with
* correct data (but can left unnecessary data in the area, to avoid
* to much paranoia tests).
*/
XmuArea *XmuOptimizeArea(XmuArea *area)
{
XmuScanline *pr, *at;
if (!area || !area->scanline)
return (area);
if (!area->scanline->next)
{
XmuDestroyScanlineList(area->scanline);
area->scanline = (XmuScanline *)0;
return (area);
}
pr = area->scanline;
at = area->scanline->next;
while (area->scanline && (!XmuValidScanline(area->scanline)
|| (area->scanline->next && area->scanline->y
>= area->scanline->next->y)))
{
area->scanline = area->scanline->next;
XmuDestroyScanline(pr);
pr = area->scanline;
if (pr)
at = pr->next;
}
for (; at; pr = at, at = at->next)
{
if (XmuScanlineEqu(at, pr)
|| (!XmuValidScanline(at) && !XmuValidScanline(pr))
|| (at->next && at->y >= at->next->y))
{
pr->next = at->next;
XmuDestroyScanline(at);
at = pr;
}
}
if (pr && XmuValidScanline(pr))
{
XmuDestroySegmentList(pr->segment);
pr->segment = (XmuSegment *)NULL;
}
if (area->scanline && !area->scanline->next)
{
XmuDestroyScanlineList(area->scanline);
area->scanline = (XmuScanline *)NULL;
}
return (area);
}
|
