wsbe
The example code for the Windowing Systems by Example blog series
5 - Be Clipped
by Joe Marlin
Hey, all you groovy fellas and dames, welcome to yet another week of WSBE. I'll lay it down quick: As it stands, we have a desktop object that holds some window objects and a drawing context object[1]. We set up our desktop object to handle mouse events and do a redraw of its windows whenever it gets one. Then, yesterday, we decided to get a little smarter and begin implementing a simple clipping system made out of rectangles and temporarily replaced our old desktop drawing code to visualize how our function for splitting rectangles into the collection of clipping rectangles works.
Today, we'll finish the clipping framework we started in part 4[2] by updating our basic drawing functions to actually take the clipping rectangles into account, extending our clipping rectangle code a little so that we can both add and remove rectangular regions from the clipping rectangles, and finally use both of those functions to do what we'd originally come here for in part 4: draw our desktop without wasting time drawing bits of windows that won't be visible. And, as a cherry on top, we'll start adding just a touch of chrome to our windows. I'm sure you're already warmed up from last time, so let's shut my yap and dive on in already.
Part 1: Rectangle in a Rectangle
Our context has this list of clipping rectangles now and we can add rectangles to it and remove rectangles from it. Whoopee, what good does that actually do us? The idea, here, is that when we call our drawing functions like Context_fill_rect(), we want them to only render those pixels that are inside of any of the rectangles in context->clip rects. In that way, by setting up the clipping region to only include those areas of a window that aren't going to be covered up by something else[3] we will only end up painting visible pixels when we call on the window to paint itself.
The most naive approach here would be to do our standard drawing but with a check added to test, when we're about to put a pixel in the framebuffer, if that pixel lands within one of the clipping rectangles and skip putting it on screen if it doesn't. This, however, isn't great since we still have to do some work for every single pixel in the shape, including those that are potentially completely invisible. Instead[4], we're going to modify our drawing algorithms slightly so that, for each clipping rectangle, we will pre-calculate the shape that results from trimming the bigger shape by the current clip rectangle and then finally draw that sub-shape.
Thankfully, this is crazy easy for drawing rectangles since to calculate the bit of a rectangle that sits inside of another rectangle you just have to clamp the edges of the one the the edges of the other -- just like we already do to make sure none our rectangle gets drawn offscreen[5]. Every drawing function we have so far -- rectangle outlines, horizontal lines, vertical lines -- rests on our basic filled rectangle function. Therefore, if we make a new, secondary filled rectangle function that will draw things as limited by a provided rectangle and then use that new function at the core of an updated version of our old rectangle drawing function that calls it for each clipping rect, we can quickly make our drawing functions clip the way we want:
//This is our new function. It basically acts exactly like the original
//Context_fill_rect() except that it limits its drawing to the bounds
//of a Rect instead of to the bounds of the screen.
void Context_clipped_rect(Context* context, int x, int y, unsigned int width,
unsigned int height, Rect* clip_area, uint32_t color) {
int cur_x;
int max_x = x + width;
int max_y = y + height;
//Make sure we don't go outside of the clip region:
if(x < clip_area->left)
x = clip_area->left;
if(y < clip_area->top)
y = clip_area->top;
if(max_x > clip_area->right + 1)
max_x = clip_area->right + 1;
if(max_y > clip_area->bottom + 1)
max_y = clip_area->bottom + 1;
//Draw the rectangle into the framebuffer line-by line
//just as we've always done
for(; y < max_y; y++)
for(cur_x = x; cur_x < max_x; cur_x++)
context->buffer[y * context->width + cur_x] = color;
}
//And here is the heavily updated Context_fill_rect that calls on the new
//Context_clipped_rect() above for each Rect in the context->clip_rects
void Context_fill_rect(Context* context, int x, int y,
unsigned int width, unsigned int height, uint32_t color) {
int start_x, cur_x, cur_y, end_x, end_y;
int max_x = x + width;
int max_y = y + height;
int i;
Rect* clip_area;
Rect screen_area;
//If there are clipping rects, draw the rect clipped to
//each of them. Otherwise, draw unclipped (clipped to the screen)
if(context->clip_rects->count) {
for(i = 0; i < context->clip_rects->count; i++) {
clip_area = (Rect*)List_get_at(context->clip_rects, i);
Context_clipped_rect(context, x, y, width, height, clip_area, color);
}
} else {
//Since we have no rects, pass a fake 'screen' one
screen_area.top = 0;
screen_area.left = 0;
screen_area.bottom = context->height - 1;
screen_area.right = context->width - 1;
Context_clipped_rect(context, x, y, width, height, &screen_area, color);
}
}
And that's really it. Now setting up/clearing clipping will actually have an effect on our drawing. Since all of our other drawing primitives ultimately call on Context_fill_rect() to do their work, they'll all end up being clipped.
There's one more quick change to our Context class that I had talked about making at the end of last week's article, though. It's really cool that we can, without overlapping, add rectangles to the clipping rectangle collection. But, in the process of building the visibility clipping for a window as I had described it in passing last week[6], we need to be able to also remove rectangular regions from our clipping. But, as I also mentioned last time, making that happen is going to be pretty trivial. Since we already punch out an area for a rectangle in our Context_add_clip_rect() function, we just need to update it to not add the new rectangle to the collection when it's done clipping and it suddenly becomes a subtraction method:
//This is literally the exact same function but renamed and with a minor change at
//the very very end
//split all existing clip rectangles against the passed rect
void Context_subtract_clip_rect(Context* context, Rect* subtracted_rect) {
//Check each item already in the list to see if it overlaps with
//the new rectangle
int i, j;
Rect* cur_rect;
List* split_rects;
for(i = 0; i < context->clip_rects->count; ) {
cur_rect = List_get_at(context->clip_rects, i);
//Standard rect intersect test (if no intersect, skip to next)
//see here for an example of why this works:
//http://stackoverflow.com/questions/306316/determine-if-two-rectangles-overlap-each-other#tab-top
if(!(cur_rect->left <= subtracted_rect->right &&
cur_rect->right >= subtracted_rect->left &&
cur_rect->top <= subtracted_rect->bottom &&
cur_rect->bottom >= subtracted_rect->top)) {
i++;
continue;
}
//If this rectangle does intersect with the new rectangle,
//we need to split it
List_remove_at(context->clip_rects, i); //Original will be replaced w/splits
split_rects = Rect_split(cur_rect, subtracted_rect); //Do the split
free(cur_rect); //We can throw this away now, we're done with it
//Copy the split, non-overlapping result rectangles into the list
while(split_rects->count) {
cur_rect = (Rect*)List_remove_at(split_rects, 0);
List_add(context->clip_rects, cur_rect);
}
//Free the empty split_rect list
free(split_rects);
//Since we removed an item from the list, we need to start counting over again
//In this way, we'll only exit this loop once nothing in the list overlaps
i = 0;
}
//[~!~] Here we removed List_add();
}
//And with that, our original Context_add_clip_rect() function gets replaced
//by a function that just calls the 'new' subtraction function and then adds
//the passed rectangle into the collection
void Context_add_clip_rect(Context* context, Rect* added_rect) {
Context_subtract_clip_rect(context, added_rect);
//Now that we have made sure none of the existing rectangles overlap
//with the new rectangle, we can finally insert it
List_add(context->clip_rects, added_rect);
}
Really absurdly simple, I don't know why we didn't just do that in the first place[7].
To finish this section up, I just want to make some changes to the desktop drawing function so that you can really see how this new clipping ends up working, and that it is in fact working. To do that, I'm going to continue to forgo actually painting the windows. Instead, we're going to draw a loud image to the screen, then add a rectangle for the desktop to the clipping region, use our 'new' subtraction function to subtract each of our windows from the clipping region, and finally do our usual call to Context_fill_rect() to draw the desktop color. This way, we'll get a good example of our clipping at work in the form of the first image showing through the desktop where our windows would be:
//Paint the desktop
void Desktop_paint(Desktop* desktop) {
//Loop through all of the children and call paint on each of them
unsigned int i;
Window* current_window;
Rect* temp_rect;
//Clear the screen quadrants each to a different bright color
Context_fill_rect(desktop->context, 0, 0, desktop->context->width/2,
desktop->context->height/2, 0xFF0000FF);
Context_fill_rect(desktop->context, desktop->context->width/2, 0, desktop->context->width/2,
desktop->context->height/2, 0xFF00FF00);
Context_fill_rect(desktop->context, 0, desktop->context->height/2, desktop->context->width/2,
desktop->context->height/2, 0xFF00FFFF);
Context_fill_rect(desktop->context, desktop->context->width/2, desktop->context->height/2,
desktop->context->width/2, desktop->context->height/2, 0xFFFF00FF);
//Add a rect for the desktop to the context clipping region
temp_rect = Rect_new(0, 0, desktop->context->height - 1, desktop->context->width - 1);
Context_add_clip_rect(desktop->context, temp_rect);
//Now subtract each of the window rects from the desktop rect
for(i = 0; (current_window = (Window*)List_get_at(desktop->children, i)); i++) {
temp_rect = Rect_new(current_window->y, current_window->x,
current_window->y + current_window->height - 1,
current_window->x + current_window->width - 1);
Context_subtract_clip_rect(desktop->context, temp_rect);
free(temp_rect); //In an add, the allocated rectangle object gets pushed into the
//clipping collection and then eventually freed when we clear it.
//We specifically don't add the rectangle to the collection on a
//subtract, though, so we have to make sure to free it ourselves.
}
//Fill the desktop (shows the clipping)
Context_fill_rect(desktop->context, 0, 0, desktop->context->width,
desktop->context->height, 0xFFFF9933);
//Reset the context clipping for next render
Context_clear_clip_rects(desktop->context);
//simple rectangle for the mouse
Context_fill_rect(desktop->context, desktop->mouse_x,
desktop->mouse_y, 10, 10, 0xFF000000);
}
To understand everything a little better, here's a visual representation of what exactly is happening to the clipping rectangles during the desktop drawing function:
There, you can very clearly see how, after the desktop rectangle gets added into the blank clipping region, each window in turn punches a hole into the existing clipping rectangles using our simple rectangle splitting algorithm, just as I described it at the end of the last article.
Today's code is built in two parts that are completely buildable each on their own, because I wanted to do this demonstration of clipped drawing before we use it to result drawing all of our windows so you can more clearly see the new clipping magic at play. So feel free to fire up the compiler and give this bad boy a spin. For even more clarity, here's a super slowed-down depiction of how the filled rect is getting drawn on each desktop draw:
Okay, that's fun and all, but it's time to cover up all of our hard work and use this new clipped drawing functionality to actually paint our windows[8]
Part 2: Hiding the Artwork
Well, we got the fun spectacle of our working rudimentary clipping out of the way, so I guess it's time to put the hood back over the engine. We're going to focus on taking what we've just built, and rewriting our window drawing to take advantage of it. For double-fun[9], we're going to also update our window painting to look a little more window-like.
Basically, we just need to update the drawing function in our Desktop class to do the use clipping in the same way we just did to punch window holes out of the background, but for each window. However, with the windows there's also one minor twist: Ordering.
Here's the thing: The desktop was super trivial because we know that all of the windows will already be above it and therefore occlude it. But with the windows it's important to note that we only want to subtract from a clipping rectangle where the window is occluded. And a window can only become occluded by the windows above it, not below. In our case, that means the windows further into the list than the window being drawn. So, before we start updating our desktop painting we'll write a quick function to get a list of windows above and overlapping a given window[10]:
//Used to get a list of windows overlapping the passed window
List* Desktop_get_windows_above(Desktop* desktop, Window* window) {
int i;
Window* current_window;
List* return_list;
//Attempt to allocate the output list
if(!(return_list = List_new()))
return return_list;
//We just need to get a list of all items in the
//child list at higher indexes than the passed window
//We start by finding the passed child in the list
for(i = 0; i < desktop->children->count; i++)
if(window == (Window*)List_get_at(desktop->children, i))
break;
//Now we just need to add the remaining items in the list
//to the output (IF they overlap, of course)
//NOTE: As a bonus, this will also automatically fall through
//if the window wasn't found
for(; i < desktop->children->count; i++) {
current_window = (Window*)List_get_at(desktop->children, i);
//Our good old rectangle intersection logic
if(current_window->x <= (window->x + window->width - 1) &&
(current_window->x + current_window->width - 1) >= window->x &&
current_window->y <= (window->y + window->height - 1) &&
(window->y + window->height - 1) >= window->y)
List_add(return_list, current_window); //Insert the overlapping window
}
return return_list;
}
As far as preparing for our window clipping, that's about that. We're ready to update the main paint routine in Desktop. It's been stated before, but I'll reiterate: Our process is going to be first to do exactly what we did to the desktop in part 1 (add desktop rect, subtract all window rects, paint). Then we're going to go through just about the same process to clip and draw each window using the Window_paint() call, but instead of adding the rect of the current window and then subtracting the rect of every window we're going to only subtract the rectangles of the windows returned by the Desktop_get_windows_above() function we just wrote.
This is going to be another really long one, but it's nothing you haven't seen before. It's just rather verbose:
//Paint the desktop
void Desktop_paint(Desktop* desktop) {
//Loop through all of the children and call paint on each of them
unsigned int i, j;
Window *current_window, *clipping_window;
Rect* temp_rect;
List* clip_windows;
//Do the clipping for the desktop just like before
//Add a rect for the desktop
temp_rect = Rect_new(0, 0, desktop->context->height - 1, desktop->context->width - 1);
Context_add_clip_rect(desktop->context, temp_rect);
//Now subtract each of the window rects from the desktop rect
for(i = 0; i < desktop->children->count; i++) {
current_window = (Window*)List_get_at(desktop->children, i);
temp_rect = Rect_new(current_window->y, current_window->x,
current_window->y + current_window->height - 1,
current_window->x + current_window->width - 1);
Context_subtract_clip_rect(desktop->context, temp_rect);
free(temp_rect); //Rect doesn't end up in the clipping list
//during a subtract, so we need to get rid of it
}
//Fill the desktop
Context_fill_rect(desktop->context, 0, 0, desktop->context->width, desktop->context->height, 0xFFFF9933);
//Reset the context clipping
Context_clear_clip_rects(desktop->context);
//Now we do a similar process to draw each window
for(i = 0; i < desktop->children->count; i++) {
current_window = (Window*)List_get_at(desktop->children, i);
//Create and add a base rectangle for the current window
temp_rect = Rect_new(current_window->y, current_window->x,
current_window->y + current_window->height - 1,
current_window->x + current_window->width - 1);
Context_add_clip_rect(desktop->context, temp_rect);
//Now, we need to get and clip any windows overlapping this one
clip_windows = Desktop_get_windows_above(desktop, current_window);
while(clip_windows->count) {
//We do the different loop above and use List_remove_at because
//we want to empty and destroy the list of clipping widows
clipping_window = (Window*)List_remove_at(clip_windows, 0);
//Make sure we don't try and clip the window from itself
if(clipping_window == current_window)
continue;
//Get a rectangle from the window, subtract it from the clipping
//region, and dispose of it
temp_rect = Rect_new(clipping_window->y, clipping_window->x,
clipping_window->y + clipping_window->height - 1,
clipping_window->x + clipping_window->width - 1);
Context_subtract_clip_rect(desktop->context, temp_rect);
free(temp_rect);
}
//Now that we've set up the clipping, we can do the
//normal (but now clipped) window painting
Window_paint(current_window);
//Dispose of the used-up list and clear the clipping we used to draw the window
free(clip_windows);
Context_clear_clip_rects(desktop->context);
}
//Simple rectangle for the mouse
Context_fill_rect(desktop->context, desktop->mouse_x, desktop->mouse_y, 10, 10, 0xFF000000);
}
And now we're painting our windows with clipping! You might think we need to change something about the way Window_paint() does its work, but since we already modified the graphics methods it uses for drawing everything that it paints when we call it in our window drawing loop will already automatically be affected by the clipping that was applied to the context prior.
We could call it there, but I know it's kind of irksome that we've been at this for so long, have written hundreds of lines of code, and yet still have nothing especially resembling a window. So, since we're mucking around with putting window painting back into our screen updates, why don't we spend a quick minute and spruce it up a bit?
Firstly, let's centralize some of our window colors[11]. And since we're not painting random-colored rects anymore, we can go ahead and remove the fill_color property from the Window class while we're at it.
//We're going to centrally define our window colors here
//Feel free to play with this 'theme'
#define WIN_BGCOLOR 0xFFBBBBBB //A generic grey
#define WIN_TITLECOLOR 0xFFBE9270 //A nice subtle blue
#define WIN_BORDERCOLOR 0xFF000000 //Straight-up black
//We're going to draw all of the windows the same, now,
//so we can remove the window color property
typedef struct Window_struct {
int16_t x;
int16_t y;
uint16_t width;
uint16_t height;
Context* context;
} Window;
To match the fact that we're not using the fill_color property anymore, we also have to remove its assignment from the Window constructor while we're at it:
//Only change to the window constructor is that we don't need
//to generate the background color anymore
//Window constructor
Window* Window_new(int16_t x, int16_t y,
uint16_t width, uint16_t height, Context* context) {
//Try to allocate space for a new WindowObj and fail through if malloc fails
Window* window;
if(!(window = (Window*)malloc(sizeof(Window))))
return window;
//Assign the property values
window->x = x;
window->y = y;
window->width = width;
window->height = height;
window->context = context;
return window;
}
Now that we've got that minor housekeeping out of the way, we can move on to overhauling our window painting method. Really, you can do whatever you want here and certainly feel free to play with the style. But I'm going to just do a simple 3px border in WIN_BORDERCOLOR around the edge of the window and along the bottom of a 25px tall WIN_TITLECOLOR colored titlebar rectangle, and finally finish it off by filling the body of the window in with WIN_BGCOLOR. The code should be pretty self-explanatory[12]:
//Let's start making things look like an actual window
void Window_paint(Window* window) {
//Draw a 3px border around the window
Context_draw_rect(window->context, window->x, window->y,
window->width, window->height, WIN_BORDERCOLOR);
Context_draw_rect(window->context, window->x + 1, window->y + 1,
window->width - 2, window->height - 2, WIN_BORDERCOLOR);
Context_draw_rect(window->context, window->x + 2, window->y + 2,
window->width - 4, window->height - 4, WIN_BORDERCOLOR);
//Draw a 3px border line under the titlebar
Context_horizontal_line(window->context, window->x + 3, window->y + 28,
window->width - 6, WIN_BORDERCOLOR);
Context_horizontal_line(window->context, window->x + 3, window->y + 29,
window->width - 6, WIN_BORDERCOLOR);
Context_horizontal_line(window->context, window->x + 3, window->y + 30,
window->width - 6, WIN_BORDERCOLOR);
//Fill in the titlebar background
Context_fill_rect(window->context, window->x + 3, window->y + 3,
window->width - 6, 25, WIN_TITLECOLOR);
//Fill in the window background
Context_fill_rect(window->context, window->x + 3, window->y + 31,
window->width - 6, window->height - 34, WIN_BGCOLOR);
}
Finally, as an added touch, I'm going to change a teensy tiny minor section of our mouse handling code so that, more like a traditional window manager, our windows are only draggable by their titlebars:
void Desktop_process_mouse(Desktop* desktop, uint16_t mouse_x,
uint16_t mouse_y, uint8_t mouse_buttons) {
//[Variable declarations, mouse coordinate capture...]
if(mouse_buttons) {
if(!desktop->last_button_state) {
for(i = desktop->children->count - 1; i >= 0; i--) {
child = (Window*)List_get_at(desktop->children, i);
//Here's our change:
//See if the mouse position lies within the bounds of the current
//window's 31 px tall titlebar by replacing
// mouse_y < (child->y + child->height)
//with
// mouse_y < (child->y + 31)
if(mouse_x >= child->x && mouse_x < (child->x + child->width) &&
mouse_y >= child->y && mouse_y < (child->y + 31)) {
//[Etcetera...]
Such a minor little tweak that I decided to just elide as much of that function as I could because typing it all out wasn't even worth it. But that little change should make this bad boy feel a little more like you're used to.
And that's it for today. Compile that bad boy up and you'll get... well. Some windows. Shocker.
Epilogue
These last two installments have most certainly been, if anything, a good case study of the idea that there is often much more to software than meets the eyes. While a simple painter's algorithm might seem like an easy way to go, and visually gives the exact same results at the end of the day[13], the reality of making a practical stacking window manager that's actually performant[14] involves a lot more that isn't especially obvious.
And even then, we have some improvements to make down the road. Consider this: Even now that we're limiting our drawing to those bits of the windows and/or desktop actually visible on the screen, why are we wasting time redrawing every single window on every single mouse event when, for instance, we might've just moved one window two pixels to the left that didn't affect the visibility of any other window or even just moved the mouse and nothing else?
But at this point, our framework is beginning to get robust enough that we could go off in a lot of different directions from here in terms of what feature we want to tackle next. We could definitely dive into those further improvements to screen update efficiency -- and we will -- but I'm going to finally take a little mercy in recognition of you folks' patience since we can save that for another time. So tune in next week when we start talking about the much more interesting -- not to mention visually rewarding -- topic of implementing controls!
Note: You may notice that you get some wonky-ass issues related to memory sanity [15] if you try to drag a window so it extends past the top or sides[16] of the screen. It's an issue with our new fill rect function, try and solve it!
tags: