How fast are splines?

How fast are splines?

Post by Dr Ted Marst » Thu, 23 Feb 1995 22:57:21

Quote:> While the forward difference method is fine for plotting an
> approximation to a curve made of short straight lines spanning several
> pixels, it is not so good for rendering.  I was trying to develop an
> incremental method for rendering anti-aliased Bezier cubics one pixel
> at a time analagous to Bresenham's method for circles.

> The trouble with the forward difference method is that equal t-steps
> do not produce equal steps in x or y, and if you make 1/dt small
> enough not to skip pixels along some portions of the curve you finish
> up rendering most pixels more than once.


There is a similar problem with some of the general ellipse plotting methods.
For example, Fellner and Helmberg, in ACM TOG Vol 12, No 3, July 93, pp 251-76,
used a delayed output tactic to filter the duplicate pixels and (nearly all of)
the uneccessary 4-connected pixels. I implemented their method in C as follows:

typedef struct { int x, y; }    P2i;    /* 2D position vector of integers */

/* do_put: decide when to output another pixel                  */
/*      by filtering out most duplicate or 4-connected pixels.  */
/*      p - current position                                    */
/*      dp - change in position since last call                 */
/*      sp - slope at current position                          */
static void do_put(p, dp, sp)
P2i *p, *dp, *sp;
        static P2i  prev;       /* delayed point */
        static P2i  pend;       /* steps pending */
        int         doit = False;

        /* make sure position has changed */
        if (dp->x || dp->y) {

                /* diagonal steps or double steps always output */
                if ((dp->x && dp->y)||(dp->x && pend.x)||(dp->y && pend.y)) {
                        pend.x = (dp->x != 0);
                        pend.y = (dp->y != 0);
                        doit = True;
                else {
                        if (dp->x) {
                                /* x-step */
                                pend.x = True;
                                if (pend.y && ((sp->x < 0) != (sp->y < 0)))
                                      { pend.y = False; doit = True; }
                        } else {
                                /* y-step */
                                pend.y = True;
                                if (pend.x && ((sp->x < 0) == (sp->y < 0)))
                                      { pend.x = False; doit = True; }
        if (doit)
                draw_point(prev.x, prev.y);

        prev.x = p->x; prev.y = p->y;


Unfortunately, this still missess a (very) few unneccessary 4-connected pixels.
I guess a better approach might be to buffer the pixels until the shading is
completed, then filter them and write them into the display after all affected
pixels are known.


| Dr. R. E.(Ted) Marston    Computer Science Dept, University of Nottingham, |
|                           University Park, Nottingham. NG7 2RD.   England. |



How fast are splines?

Post by klassen.wbst1 » Sun, 26 Feb 1995 03:05:06

You will find in the current issue of TOG an article
on using forward differencing after you've done a handful of
subdivisions.   The subdivisions make the parameterization much
more uniform, so when you go to do the differencing you rarely
hit the same pixel twice.  And you can easily guarantee that you
hit each pixel at least once.   It all works in integers for fairly
big raster spaces containing the curve.

About four years back there's an article on using adaptive
forward differencing to do antialiased Bezier cubics.  Same author.


1. The faster it runs - the happier a man I am

Hi There ,
Wondering if any of you can help me, Whilst in conversation with a
software rep
some time ago , he told me that my cyrix processing chip was useless
compared to the pentium
and that the cyrix (I have a 330) is useless in high end graphics.

Is there any truth in this , or was he trying to fob me off with a new
processing chip.

come to think of it, photoshop 5 is quite slow on my machine, where I
have 128MB Ram
and Cyrix 330 processor. Even when I top up the File-Preferences-Image &
cache levels.




2. Logo Creation

3. Help, conic/conic, conic/spline, spline/spline, intersections?

4. Minimum system requirements for Lightwave 3D for Windows

5. Very fast spline algorithm ???

6. South FL May 30th Alias | Wavefront Demo

7. Fast Spline Algorithm

8. Advice needed on GIF animator

9. Fast spline drawing needed !!!

10. Very fast spline algorithm ???

11. Fast Spline Algorithm

12. fast bezier splines and de Casteljaus alg.

13. How fast are splines?