[interfacekit] Re: Clipping - what to do, what to do?

Sorry about taking so long to respond on this stuff.  For a start on 
explanation, I should clarify some terminology since Adi and I aren't using 
the same definition of high and low level.  For clarity, I propose that we 
use the following scheme.  High level clipping is determining the clipping 
regions.  Medium level clipping is taking a graphical figure and combining it 
with a clipping region such that we get a set of zero or more graphical 
figures which are entirely contained with the region (in my previous 
comments, this is what I ment by high-level).  Low level clipping is taking a 
graphical figure and a clipping region and determining on a per-pixel basis 
whether we should be drawing or not.  If medium level is complete, low-level 
is unnecessary.

> > A filled ellipse really isn't that much harder since it is drawn as a
> > series of horizontal lines which can be clipped individually.
>
>       How do you clip a line with a region full of holes?

For each rectangle in the region, clip the line to the rectangle.  Then draw 
the set of lines.

>
> > Working at the pixel level is definitely overworking the CPU.  It is a
> > relatively simple procedure to transform figures into lines and then clip
> > each of the lines.
>
>       Please, explain us how are you planning to do low level clipping. This
> is a complex thing and it must be as fast as possible.

I plan to do things using the defintion of medium-level clipping that I 
mentioned above.  Lines with width 1 are simple to clip to rectangles.  Lines 
with width greater than 1 can be treated as polygons (this is more efficient 
than my current code for drawing thick lines).  Clipping a polygon to a 
rectangle isn't very difficult (there are well known algorithms for this 
stuff).  Curves are the trickiest part.  For a finite resolution, a curve can 
be approximated as a polygon.  Given proper thresholds, the polygon should 
appear identical to the curve.  Once the approximation is found, we can 
simply clip the polygon, so we don't have to maintain separate curve clipping 
code.  Developing the polygon approximation now will also make things easier 
when we eventually start supporting an OpenGL back end (OpenGL drawing 
primitives are all line and polygon based).  For bezier curves, generating an 
approximation with lines solved a number of issues that were a royal pain 
when using the parametric equations to plot the curve (most notably, the 
issue of how to implement FillBezier).  I am currently looking into picking 
an initial method for converting ellipses into a sequence of lines.  The plan 
is to get an initial algorithm that works, and then later investigate 
possible methods for optimization.  The biggest drawback is that in some 
cases, the lines will be very short and might not gain anything over clipping 
on a pixel by pixel basis.


Gabe

Other related posts: