Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!snorkelwacker.mit.edu!bloom-beacon!eru!hagbard!sunic!mcsun!ukc!tcdcs!bofin!cjmchale From: cjmchale@cs.tcd.ie (Ciaran McHale) Newsgroups: comp.windows.x Subject: Re: How to clip Regions in X11R4? Message-ID: <1991Mar23.151906.29656@cs.tcd.ie> Date: 23 Mar 91 15:19:06 GMT References: <3725@nosc.NOSC.MIL> Organization: DSG, Dept. of Comp. Sci., Trinity College, Dublin. Lines: 174 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