Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!usc!snorkelwacker.mit.edu!bloom-beacon!dont-send-mail-to-path-lines
From: mouse@lightning.mcrcim.mcgill.EDU (der Mouse)
Newsgroups: comp.windows.x
Subject: Re:  How to clip Regions in X11R4?
Message-ID: <9103220550.AA05776@lightning.McRCIM.McGill.EDU>
Date: 22 Mar 91 05:50:41 GMT
Sender: daemon@athena.mit.edu (Mr Background)
Organization: The Internet
Lines: 55

> I have been trying to implement some polygon clipping routines.
> Someone mentioned to me that since X-windows X11R4 has a concept of a
> Region which is a a general polygon,

The Xlib document says

	10.5.  Generating Regions
	
	Regions are arbitrary sets of pixel locations.

I just checked the MIT source for XPolygonRegion, and it scan-converts
the polygon.  Regions allow you to work with sets of pixels, not really
with polygons per se.

That out of the way,

> I've looked over the code briefly.  It mentions a method called Y-X
> banding, that it employs to perform the polygon clip.  What is Y-X
> banding?

It is a term used to describe a region represented by a list of
(coordinate-axis-aligned) rectangles such that:

	- For a given rectangle R, every rectangle whose Y extent
	  overlaps with that of R has Y bounds exactly matching R's.

	- For rectangles R1 and R2, with R1 appearing the list before
	  R2, either R1's Y origin is less than R2's, or the Y origins
	  are equal and R1's X origin is less than R2's.

I expected to find some comment about rectangles not overlapping, but
didn't.  (The first condition prohibits partial overlap in the Y
direction, but it appears they can overlap in the X direction.)

> [...], I gather that a region is basically an array of rectangles.
> Is this right?

Yes.  Or rather, that's how it's implemented.  A list of (x,y)
coordinate pairs would be an alternative implementation (probably
ruinously inefficient in memory :-).

> But how can this be?  A region is supposed to be a general polygon,
> specified with (x,y) vertices.

Sorry, that's not the spec, as far as I can tell.

> More importantly, how does one recover the original list of vertices
> of the polygon from the array of rectangles?

One doesn't.  Scan conversion is generally a one-way operation.

					der Mouse

			old: mcgill-vision!mouse
			new: mouse@larry.mcrcim.mcgill.edu