Skip navigation

Monthly Archives: March 2010

OpenOffice.org Product Development!

This is in response to Martin’s posting about OOo product development, and my candidature for the OOo Community Council in particular:

The only candidate now for the non-code contributing projects for the next round of council elections will be Thorsten Behrens. he’s a well known great supporter of the hacker driven “Product Development”, from my perspective a good representative of the code contributors. But not for the non-code contributing PD projects of OOo as the charter of the CC states. It’s difficult to do a “no” vote against the only candidate for this seat, especially if the candidate does good things for the project and I consider him as a good friend of mine. But we need a general review of the PD part of the project, and therefore I want to see a person representing the classical school of product development and call for a no-vote and call for new candidates.

I wonder, does anyone really think someone capable of working on the strategic marketing plan will have more time doing so when being a member of the CC? 😉

More seriously, and as I wrote in my introduction mail, I firmly believe that CC’s central function is arbitration – i.e. talking to people, convincing folks, finding compromise. It’s decidedly not the place to vote people into, because you need specific jobs A, B, or C done – that’s what the different projects are for, for the example at hand the marketing project. My selling point is surely not decades of marketing experience, but rather my ties into the wider community, for which I know very many people in person, and would call quite a few of them friends.

I’ve done QA work on CWS & sponsoring a tinderbox, I know a fair bit about the economies & strategies in FLOSS communities – and I do my legwork in advertising OOo, e.g. at CeBIT. As stated in my introduction mail, I’m explicitely running for this seat representing projects outside of raw code contribution in the council – in fact, I’ve always frowned upon the notion of being purely “code contributor”, “qa engineer”, or “marketer” – core to my motivation is my love for this project, that is OOo, and everything that’s necessary to further its success. Across all camps.

And finally, I find the act of lobbying for a “no” vote against a CC candidate quite without precedent, even more so since there was not even a single question, neither public nor privately, about my intentions or motivations, let alone a discussion. I can only ask everyone involved to check the facts objectively, and keep up with the tradition of having the CC be a place of collaboration & compromise, instead of exclusionism & camp mentality.

Note: I’d prefer to have the actual discussion on the dev list, rather than via blog. Please follow up there.

Advertisement

Clipping Boxes

Introduction

Beside the problem of general polygon clipping, which has been thoroughly researched in the past twenty or so years, it is sometimes the case that only rectangular areas have to be clipped against each other. Two very prominent examples are the calculation of redraw areas in a GUI application – widget and application content areas are, because of performance and simplicity, often represented as rectangles, and quick, approximative spatial indexing, e.g. for GIS data.

It turns out that constraining clip calculations to axis-aligned bounding boxes (aka AABB) allows for noticeable simplifications in the algorithm – regarding code and time complexity, as well as numerical stability.

The algorithm

For clipping a set of AABBs against each other, the common sweep line algorithm is employed, in this case sweeping a vertical line from the leftmost box over to the rightmost. Therefore, each box B_i contributes two sweep line events E_l_i and E_r_i to the algorithm, one for its left and one for its right edge. After sorting those events in ascending order, a line is swept horizontally across all boxes:

Each time a box’s left edge is hit by the sweep line, two horizontal edges H_u_i and H_l_i are inserted into a list of currently-active horizontal segments. This list is kept sorted with ascending y values, and every vertical edge event is checked against intersection with all active horizontal edge segments.

At the core of every polygon clipping algorithm, mutual edge intersections need to be computed. Fortunately, as rectangles are convex polygons and free of self-intersections, a lot of the more complicated preprocessing steps involved for generic polygon clipping can be avoided. One of the most notable aspects is the fact that this algorithm is numericable stable also when performing intersection calculations with finite-precision floating-point math, because no precision-reducing operations need to be performed (this is in contrast to general polygon clipping, which gets notoriously instable under floating-point math, since the (sometimes repeated) calculation of intersection points introduces round-off errors – obvious for oblique edges).

For intersection calculations of AABBs, no calculations whatsoever are necessary on the coordinate elements, the resulting intersection vertices are just element-wise merged input coordinates.

Basically, four cases of edge intersections can be distinguished:

Note that, since the sweep line is vertical, it is always a right or a left edge of a rectangle, that needs to be intersected with either an upper or a lower edge. Degenerate cases, such as rectangles with zero height or width, or two exactly identical rectangles, are handled in a defined, but consistent way without affecting the general algorithm.

For each sweep line event (being either a left or a right rectangle edge), all currently active horizontal edge segments are processed, starting with the one with the smallest y value. Each left edge sweep line event creates a polygon, into which intersecting horizontal edges are merged. Therefore, when processing the horizontal edge segments, the sweep line will carry a current polygon P_c. The sweep line’s current polygon may change, naturally, as it intersects horizontal edges, taking up the associated polygon of the intersecting edge and in turn passing the current polygon to that horizontal edge:

For the sake of clarity, I have omitted symmetric cases here, which you get when polygon orientation is reversed (denoting reversed inside and outside areas). Those follow rather straight-forward. A version of the algorithm that handles those cases, and is thus able to perform the usual boolean operations on AABB-defined polygons, is implemented in c++, and used in OpenOffice.org’s graphic subsystem. A standalone version can be found here.