On Oct 9, 2008, at 2:55 AM, Peter Clifton wrote: > On Wed, 2008-10-08 at 20:49 -0700, [EMAIL PROTECTED] wrote: >> This patch includes support functions for hatching arbitrary >> polygons. Currently only private functions within libgeda have been >> created. The public interface for this functionality has not been >> designed. However, these functions have been tested using a kludge >> by calling them directly from gschem. >> >> From my initial design, the file m_geometry.c was getting a bit >> "heavy," and needed to be split up. So, this patch contains an >> m_transform.c and an m_hatch.c. > > Very cool. What algorithm does this use?
I believe it is referred to as a scan-line algorithm for filling. > Looking at the line output code, it appears that it iterates over a > starting y coordinate for begining a sweep. Does that necessarily work > for non-convex polygons, where we might have two hashings starting at > the same Y coordinate? > > e.g.: > ___________ > |///////////| > |///////////| > \/////\////| > \/// \/// > \/ \/ Yes. Each (leading) vertex represents an event. All the intersections represent the sweep status. The algorithm can move multiple events to the status list. The polygon is rotated so the sweep line runs parallel to the hatch lines. Resulting hatch line segments are rotated back to the original space. So the sweep line runs at an angle through the shape to be filled. >> For the public interface, I'm suspecting wrapper functions in files >> like s_box*, s_circle*, o_box*, or o_circle*. I'm open for ideas on >> the function signatures. > > Or we could expose the m_hash_... functions. I'd rather abstract the functions a bit more. It leaves the opportunity for algorithm changes, such as lazy evaluation, as you suggest below. These functions don't lend themselves to lazy evaluation. However, if the OBJECT was passed in, that would work quite nicely. Also, if the pitch gets small enough, the program should probably just use a solid fill. > I wonder though, we could actually calculate these lines as > "prim_objs" > of the element being hashed, e.g. cache the geometry in libgeda, then > stuff them through the normal drawing routines. Libgeda would > regenerate > the prim_objs just like regenerating text, when any hashed fill is > selected, and the object is changed in any way. (I'm presuming no > hashing during rubberbanding). Probably a good idea. Subdivided paths could also be cached, but I believe there is a Bezier subdivision algorithm fast enough not to worry. > The only thing which niggles at the back of my mind, is that I just > almost killed prim_objs for text, as rendering lots of little lines > (cairo especially) turned out to be slow compared to using pango. > Hashing using cairo patterns is a possibility, even if it doesn't help > our postscript output. Didn't try the algorithm with Cairo. However, I'd prefer the same algorithm for both display and print to preserve the WYSIWYG. Cheers, Ed _______________________________________________ geda-dev mailing list [email protected] http://www.seul.org/cgi-bin/mailman/listinfo/geda-dev
