Bezier curves and rasterization

SDL Development
1

Yesterday I started writing a small library that will handle drawing
using the SDL and a sub-set / variation on the Postscript language.
Basically, the goal is to create a small embedable Forth-ish engine
that will be useful in developing scalable fonts, vector images, and
the like within programs that use SDL.

I’m using the Postscript Language Reference Manual (3rd Ed) as the basis,
when I can’t decide on policy, but I’d like to go with nice antialiased
lines. So I have three questions to the peanut gallery:

1.) Do I fudge 8bit support, or do I drop it and concentrate
	on optimizing the 16 bit code?

2.) Should I go with a simple / fast alpha blend, with user
	setable step_size on the raster code, or should I
	do a slow and elegant version.

3.) Has anyone already tackled this problem and has code that
	I could borrow, abuse, tweak, and reuse?
2

Wow, I really want(ed) to do this myself as I really want support for vector
graphics in my next project. If you did it right, someone could even import
other vector formats (ala libWMF). This is a pretty good idea.

1.) Do I fudge 8bit support, or do I drop it and concentrate
on optimizing the 16 bit code?

8 bit = paletted? I’d suggest just going with full 32bit, and let the app
dither it down if it desires.

2.) Should I go with a simple / fast alpha blend, with user
setable step_size on the raster code, or should I
do a slow and elegant version.

Again, I’d suggest higher quality.

3.) Has anyone already tackled this problem and has code that
I could borrow, abuse, tweak, and reuse?

The only suggestions that comes to mind are GhostScript (blech) and the
various PDF libraries (don’t know what the license issues are tho).

Matt–
/* Matt Slot, Bitwise Operator * One box, two box, yellow box, blue box *

3

Wow, I really want(ed) to do this myself as I really want support for vector
graphics in my next project. If you did it right, someone could even import
other vector formats (ala libWMF). This is a pretty good idea.

Then I think it would be wise if we worked together on getting
it right in the first place :)  What I have done so far is 
take the equations as they appear in the Postscript manual
and do them up in c.  My Curve datastruct looks like this:

typedef struct point *POINT;
typedef struct curve *CURVE;

struct point {
	double x,y;
};

struct curve {
	double a,b,c,d,e,f;
	Point zero, one, two, three;
	int (*draw)(CURVE self, SDL_Surface *surface);
};

where a,b,c,d,e,f are the coefficients of the two 
linear equations, and Point zero -> three are the
control points for future reference.  Technically
once you get a -> f you can then just use transformations
to move the shape wherever.

I'm using function pointers in the C structs to store the
drawing routines, to make it easy to use custom drawing
routines, and give it more of a object feel, which makes
it easier to create interfaces to perl and python.

for example, my_curve->draw(my_curve,surface) just feels
like perl :)

for the number of datapoints to use I was going to use
d|(X0,Y0),(X3,Y3)| * max (d|(X0,Y0),(X1,Y1)| , d|(X3,Y3),(X2,Y2)|)
this is basically drawing one or more points for each point
contained in the quadrilateral which bounds the curve.  In other
words,  it is pretty high quality, and should never really barf
out.

I was then going to use a proportional alpha blend for each
point, adjusted by how the line fell upon the pixels.  So
if a line went through (1.5,1.5) it would be on the boundary
of four pixels, (1,1), (1,2), (2,1) and (2,2) each of which
would have 25% of the lines color "overlaid" using the
v = v1 * A + v2 * (1 - A) alpha blend equation.

This is going to be a slow function, but it should produce
nice smooth lines. Only problems come in with doing fatter lines.

	Any suggestions?On Sun, 28 May 2000, Matt Slot wrote:
4

sdl at lokigames.com wrote:

Then I think it would be wise if we worked together on getting
it right in the first place :slight_smile: What I have done so far is
take the equations as they appear in the Postscript manual
and do them up in c.

That’s a good start. I’d also recommend picking up the Graphics Gems books
and Foley+VanDam for good background material. The reason I didn’t start
such a project was that I didn’t have the time for the requisite research.

    This is going to be a slow function, but it should produce
    nice smooth lines. Only problems come in with doing fatter lines.

Implement it piecemeal then. Work on specific features (lines, shapes, paths,
clipping), then move on to the more difficult stuff (transforms, line styles,
etc.)

Matt–
/* Matt Slot, Bitwise Operator * One box, two box, yellow box, blue box *

5

Matt wrote
Implement it piecemeal then. Work on specific features (lines, shapes, paths,
clipping), then move on to the more difficult stuff (transforms, line styles,
etc.)
Matt

Actually Matt, the transforms are the simplest thing.  Its just

linear algebra, and matrix math. Anyways, the basic deal is this, I’ve
finished a working vector graphics package! The antialiasing needs a
little work, but it’s nothing one couldn’t fake with a nice quick rle
blur… :slight_smile:

I did some research into look ahead optimization of bezier curve

rasterization, and basically I’ve decided to go for simplicity. I’ve
broken every bezier curve into 1000 vectors. This is roughly what
libart does, and it gives you decent curves. Since the length of any
curve is unlikely to be more than 3000 at 1024 x 768, the typical
vector is much less than 3 pixels long. Most curves however, have
10s of vectors per pixel, which means it is very fine grained indeed.

The vector structure which makes up all paths is as follows:

	typedef struct vector *Vector;
	enum drawable { line, bezier, not };	

	struct vector {
		enum drawable type;
		double x,y,u,v;
		Vector next;
	}

As you will undoubtly have noticed, all vectors form nice linked lists.
Hence a path is little more than a list of vectors, and a scratch SDL
surface for rendering.

If the vector is a bezier, that indicates it is the start of a three
vector list which describes the control points for the curve. Naturally
the two vectors after a bezier are of type “not” and as simply not drawn.

I have three cases for drawing a vector:

width = 1
width = 2
width > 2

The first case draws one line, the second three lines, and the last
four bounding lines and then does a recusive flood_fill to fill the
contents. This is reasonably fast a a P75, but I’m sure it can be
optimized in the future.

When a path is painted, it is painted to an SDL surface, and its
values are technically the alpha levels. Then to draw that curve
onto anther surface, like the screen, it uses a selective blit command
preforming an alpha blend between the existing image, and any color or
source image specified, using the path’s SDL_Surface as an Alpha mask.

This lets one selectively copy from one image to another, along a path.
(ie you can use it to copy non-rectangle shapes) or simply draw solid
color, with transparency.

I will be releasing the code probably on Sunday after I finish off the
Forth based scripting engine / language. I hope to make it Adobe
Postscript compatible for the most part, but I doubt in this release
it will cover anything more than

newpath
moveto
lineto
rlineto
curveto
rcurveto
stroke

and also

image
set-line-width
set-line-color
set-line-alpha

and a set line width, and set color options… I’ll probably add image
suppport through SDL_image (because that’ll be simple). In the end
however it will be a fully functional programming language, with the
ability to load new modules, like python or perl. So chances are
it will be ultimately known SDLscript or something like that.

6

[…]

set-line-color
set-line-alpha

and a set line width, and set color options… I’ll probably add image
suppport through SDL_image (because that’ll be simple). In the end
however it will be a fully functional programming language, with the
ability to load new modules, like python or perl. So chances are
it will be ultimately known SDLscript or something like that.

Sweet!
Let me know when it’s available and I’ll link to it from the SDL website.

See ya,
-Sam Lantinga, Lead Programmer, Loki Entertainment Software

7

Anyways, the basic deal is this, I’ve
finished a working vector graphics package!

Yay!

The antialiasing needs a
little work, but it’s nothing one couldn’t fake with a nice quick rle
blur… :slight_smile:

Take a look at the vector emu code of MAME. It’s reasonably fast, antialiases,
and supports translucent vectors, wide beams, and flicker :). And it was
written by people with intimate knowledge of old vector hardware.

I’ve
broken every bezier curve into 1000 vectors. This is roughly what
libart does, and it gives you decent curves. Since the length of any
curve is unlikely to be more than 3000 at 1024 x 768, the typical
vector is much less than 3 pixels long. Most curves however, have
10s of vectors per pixel, which means it is very fine grained indeed.

Why not estimate the length of the curve and use a proportional number of
segments, with a settable number of segments/unit length?
Ideally the segment length should be a function of the curvature, of course.

8

Anyways, the basic deal is this, I’ve
finished a working vector graphics package!

Cool! I can port my Xlib games (3D Pong and ICBM3D) to SDL soon, eh!? :slight_smile:

-bill!