dwu@halibut.nosc.mil (Daniel Wu) (03/20/91)
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, I should check the X11 sources to see how the Region clipping routines are implemented. I did and I found the file XRegion.c in the mit/lib/X directory of the mit distribution tape. 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? Can someone point me to a source or a reference? Looking over the code, I gather that a region is basically an array of rectangles. Is this right? But how can this be? A region is supposed to be a general polygon, specified with (x,y) vertices. How does it get converted into a bunch of rectangles? More importantly, how does one recover the original list of vertices of the polygon from the array of rectangles? Can someone please point me in the right direction? I would very much like to adopt these clipping routines. They are very nice. The routines are based on set operations so that one can UNION, INTERSECT, AND, OR, take the symmetric DIFFERENCE of 2 polygons. That's exactly what I need. (Actually I need one other requirement that may or may not be satisfied by Xregion.c: the polygons should be general polygons---convex or concave---and perhaps have holes). Looking through Foley & Van Dam, I've considered the other possiblities: Sutherland-Hodgeson (nice and simple but 1 polygon has to be convex), and Weiler (too complex, I'm very short on time). Are there any other possiblities? Daniel dwu@halibut.nosc.mil PS. Please reply via e-mail. I don't read this newsgroup too often.
mouse@lightning.mcrcim.mcgill.EDU (der Mouse) (03/22/91)
> 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
cjmchale@cs.tcd.ie (Ciaran McHale) (03/23/91)
In <3725@nosc.NOSC.MIL> dwu@halibut.nosc.mil (Daniel Wu) writes: >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, I should check the X11 sources to see >how the Region clipping routines are implemented. I did and I found the file >XRegion.c in the mit/lib/X directory of the mit distribution tape. > >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? Can someone point me to a source or a reference? Looking >over the code, I gather that a region is basically an array of rectangles. >Is this right? > >But how can this be? A region is supposed to be a general polygon, specified >with (x,y) vertices. How does it get converted into a bunch of rectangles? The union of the rectanges = the polygon. For example, we can split the following polygon: +--------------------------+ | | | | +---------+ +-----+ /0/ | | +----------------------+ into several rectangles. There are several ways we could perform the split. One way would yield: +---------+----------------+ | | | | A | B | +---------+ +-----+ /1/ | | C | +----------------+-----+ Another way to split it would be: +--------------------------+ | | | A | +---------+----------------+-----+ /2/ | B | +----------------------+ The YX-Banded refers to the constraints which are applied to the way in which the polygon is divided up into rectangles. For the above examples, consider the rectangles to be stored in the list order [A, B, C, ...] /1/ is not YX-Banded (but is XY-Sorted). /2/ is YX-Banded. (If the rectangles in /2/ were stored in the list order [B, A] then it would not be YX-Banded. In fact, it would be unsorted as far as Xlib is concerned.)The exact constraints for Y-Sorted, YX-Sorted, Y-banded & XY-banded are given in the MIT Xlib manual in section 5.4.6 (in the discussion about the function XSetClipRectangles). The function XUnionRectWithRegion can be used to add rectangles to existing regions. For example, combinig /2/ above with: +----+ | | | | +----+ would yield: +--------------------------+ +----+ | | | | | A | | B | +---------+----------------+-----+ +----+ /3/ | C | +----------------------+ Thus, you see how a region can have holes. Since the regions are implemented in terms of rectangles and we can add rectangles to regions, it follows that we can also combine regions together in a similar fashion. The clip mask of a GC can be set to a region. Use the XSetRegion function for this. Then if you redraw the window's contents with this GC, only the parts inside the region will be redraw. This can be useful for handling Expose events. For example (warning---untested code): while (1) { /* main loop of Xlib application */ XEvent ev; XExposeEvent *exp = &ev; XRectangle rect; Region reg; XNextEvent(dpy, &ev); switch (ev.type) { ... case Expose: reg = XCreateRegion(); rect.x = exp->x; rect.y = exp->y; rect.width = exp->width; rect.height = exp->height; XUnionRectWithRegion(&rect, reg, reg); while (exp->count > 0) { XNextEvent(dpy, &ev); rect.x = exp->x; rect.y = exp->y; rect.width = exp->width; rect.height = exp->height; XUnionRectWithRegion(&rect, reg, reg); } /* the exposed region has been accumulated */ XSetRegion(dpy, gc, reg); XdestroyRegion(reg); redraw_window(gc); break; case ... /* handle other event types */ } } Oliver Jones' book (see the X Bibliography regular posting for bib details) has a discussion on handling Expose events in this manner. But I digress. Your posting said: >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 [...] If you want to use Regions for clipping arbitary shaped polygons then you're going to hit a performance barrier. The barrier being the amount of client side CPU time spent computing the region for a polygon. For example, if a polygon contains some diagional lines then the corresponding region will contain lots of rectangles which are 1 pixel high. For example, a right angle triangle could be represented by the following region: +-----------+ | A | +-----------+ +---------+ | B | +---------+ +-------+ | C | +-------+ +-----+ | D | +-----+ +---+ | E | +---+ +-+ |F| +-+ Now imagine if you have a polygon which is the outline of a country. There will be *lots* of diagional lines in it resulting in the region containig a multitude of tiny rectangles. If you compute such regions the your application's performance will suffer. So the question needs to be asked: Why do you want to do extensive work with regions and polygons? If it is to optimise redrawing then I'd suggest trying a different approach such as drawing into a pixmap and use XCopyArea for Expose events. If you want regions simply to detect if a point lies in a polygon then you can find algorithms in books which will do this for you. Sedgewick has a book which contains such an algorithm but I forget the book's name. ("Algorithms" perhaps.) That's my $0.02 worth anyway. (About 0.0003 cents per character in this posting. Well, they do say that talk is cheap:-) Ciaran. -- Ciaran McHale "Verbosity says it all" ____ Department of Computer Science, Trinity College, Dublin 2, Ireland. \ / Telephone: +353-1-772941 ext 1538 FAX: +353-1-772204 \/ Telex: 93782 TCD EI email: cjmchale@cs.tcd.ie