Fast quad plotter

Fast quad plotter

Post by A.P. Turnbul » Tue, 26 Oct 1999 04:00:00




> My quads were not parallelograms so I am planning on cutting them into four
> triangles and a rectangle. I found the bresenham line routine so I'll be
> able to work on that tonight, thanks.

I would advise you not to use Bresenham, from my experience. A much
better approach is to work with fractions.

To follow an edge from x1,y1 to x2,y2 with y1<y2 first work out dx=x2-x1
and dy=y2-y1. Then divide dx by dy TO GET INTEGER QUOTIENT q AND
REMAINDER r (much quicker than a full divide as the answer is almost
always quotient=0 or quotient=-1). These are effectively a fraction.
Then you set a variable x equal to x1, the integer part of the
x-coordinate, and another n to 0, the numerator of the fractional part.
For each row, add r to n and if it exceeds dy do n-=r and x+=1.

Before anybody remarks that actually this is closely related to
Bresenham: all the algorithms are related to each other, aren't they?

All you need now is a fast way of plotting a row of your texture. Again,
I would not recommend the approach you suggest. A tried and tested
method is to cut your horizontal rows into 16-ish-pixel sections, do a
proper perspective-correct mapping calculation at the junctions, and
interpolate in between. This is just as fast and much easier to write,
after you've done the maths, as managing multiple triangles and making
sure they join up is quite a headache, especially when they get near or
even partially behind the viewpoint. This is less important in a demo,
of course, where you have good control over where the triangles go.

Alistair

 
 
 

Fast quad plotter

Post by Nemo » Wed, 27 Oct 1999 04:00:00



> I would advise you not to use Bresenham, from my experience. A much
> better approach is to work with fractions.

And he then uses a Bresenham method that uses integers throughout ;-)

Quote:> To follow an edge from x1,y1 to x2,y2 with y1<y2 first work out dx=x2-x1
> and dy=y2-y1. Then divide dx by dy TO GET INTEGER QUOTIENT q AND
> REMAINDER r (much quicker than a full divide as the answer is almost
> always quotient=0 or quotient=-1).

Er, no. Quotient q (plus r/dy) is the slope, so gets rather larger than +-1
as the line approaches horizontal.

Quote:> These are effectively a fraction.

Or a Bresenham decision variable ;-)

Quote:> Then you set a variable x equal to x1, the integer part of the
> x-coordinate, and another n to 0, the numerator of the fractional part.
> For each row, add r to n and if it exceeds dy do n-=r and x+=1.

Presumably you meant x+=q.

Quote:> Before anybody remarks that actually this is closely related to
> Bresenham: all the algorithms are related to each other, aren't they?

"Bresenham" type algorithms are typified by the reliance on one or more
decision variables.?In this case 'n', though an element of x+n/dy, is not
being used numerically but as the trigger for the x increment.

Simon.  

--

Everything is possible. Given time.

 
 
 

Fast quad plotter

Post by A.P. Turnbul » Wed, 27 Oct 1999 04:00:00




> > I would advise you not to use Bresenham, from my experience. A much
> > better approach is to work with fractions.

> And he then uses a Bresenham method that uses integers throughout ;-)

Actually what I suggested isn't Bresenham. The principal differences
are:

        - The same code works for left- and right-sloping edges.
        - There is no loop involved in stepping sideways.

Quote:> > To follow an edge from x1,y1 to x2,y2 with y1<y2 first work out dx=x2-x1
> > and dy=y2-y1. Then divide dx by dy TO GET INTEGER QUOTIENT q AND
> > REMAINDER r (much quicker than a full divide as the answer is almost
> > always quotient=0 or quotient=-1).

> Er, no. Quotient q (plus r/dy) is the slope, so gets rather larger than +-1
> as the line approaches horizontal.

I said almost. Strictly, the answer is 0 in 25% of cases and -1 in
another 25% of cases. This allows you to optimise the division routine.
Read it again.

Quote:> > These are effectively a fraction.

> Or a Bresenham decision variable ;-)

> > Then you set a variable x equal to x1, the integer part of the
> > x-coordinate, and another n to 0, the numerator of the fractional part.
> > For each row, add r to n and if it exceeds dy do n-=r and x+=1.

> Presumably you meant x+=q.

At that point I meant x+=1. However, you are right that I omitted to say
that x+=q occurs on every row.

Quote:> > Before anybody remarks that actually this is closely related to
> > Bresenham: all the algorithms are related to each other, aren't they?

> "Bresenham" type algorithms are typified by the reliance on one or more
> decision variables. In this case 'n', though an element of x+n/dy, is not
> being used numerically but as the trigger for the x increment.

It was a rhetorical question, twit!

Thanks for pointing out an omission, but your other remarks are unfair.

Alistair

 
 
 

Fast quad plotter

Post by Nemo » Wed, 27 Oct 1999 04:00:00




> Actually what I suggested isn't Bresenham.

"The"? No. "A"? Well, yes. Not that it matters really, he's dead ;*)

Quote:>  - There is no loop involved in stepping sideways.

This is also the case in Bresenham's classic algorithm when dx<dy

Quote:> I said almost. Read it again.

Oh yes, sorry! I was reading ahead...

Quote:> I omitted to say that x+=q occurs on every row.

q and r can be negative, in which case the, let us say, "Bresenham-like"
decision variable n must be checked for both bounds dy and 0: if n>=dy,x+=1,
n-=dy elseif n<0,x-=1,n+=dy. Is that right? :-/

Quote:> It was a rhetorical question, twit!

Yeah I know! 8^)

Quote:> Thanks

Pleasure

Quote:> your other remarks are unfair.

Boo! ;-)

Simon.

--

It's not a lie! It's a spreadsheet - (Gordon Taylor)

 
 
 

Fast quad plotter

Post by A.P. Turnbul » Fri, 29 Oct 1999 04:00:00


The following extract from private correspondence with Nemo might be
useful:

Alistair

---

This is what I understand to be the Bresenham method:

DEFPROCdrawline(X1,X2,Y1,Y2)
IF Y1>Y2 THEN SWAP X1,X2:SWAP Y1,Y2
DX=X2-X1:DY=Y2-Y1
IF DX>0 THEN
  N=(DY-DX)/2
  POINT X1,Y1
  REPEAT
    IF N>0 THEN N-=DX:Y1+=1 ELSE N+=DY:X1+=1
    POINT X1,Y1
  UNTIL X1=X2 AND Y1=Y2
ELSE
  N=(-DY-DX)/2
  POINT X1,Y1
  REPEAT
    IF N<0 THEN N-=DX:Y1+=1 ELSE N-=DY:X1-=1
    POINT X1,Y1
  UNTIL X1=X2 AND Y1=Y2
ENDIF
ENDPROC

Different code is needed for left- and right-sloping lines. In both
cases,
the decision variable N is (twice) the area of the triangle formed by
the
line we are trying to draw and the point we have reached. It's initial
value is chosen by observing that the plotted points correspond to the
centres of pixels, while the decision points are at the corners, half a
pixel away diagonally.

Here is the method I proposed:

DEFPROCdrawline(X1,Y1,X2,Y2)
IF Y1>Y2 THEN SWAP X1,X2:SWAP Y1,Y2
DX=X2-X1:DY=Y2-Y1
REM The next few lines cope with BASIC's brain-dead treatment of
negative
REM numbers with DIV and MOD, and make it behave like Python's version.
REM The special case of DY=0 is not a problem in machine code: you just
REM make the answer at least as big as the width of the screen.
IF DX>0 THEN
  Q=DX DIV DY:R=DX MOD DY
ELSE
  Q=NOT((NOT DX) DIV DY):R=(DY-1)-((NOT DX)MOD DY)
ENDIF
REM Wouldn't be able to get the next line right if I din't know the
REM Bresenham algorithm too!
oldX=X1:X1=X1+(Q>>1):N=(DY+DX)/2-(Q>>1)*DY
IF N>DY THEN X1+=1:N-=DY
WHILE Y1<Y2
  PROChorizontalline(oldX,X1,Y1)
  oldX=X1:X1+=Q:N+=R:Y1+=1
  IF N>DY THEN X1+=1:N-=DY
ENDWHILE
PROChorizontalline(oldX,X2,Y2)
ENDPROC

DEFPROChorizontalline(X1,X2,Y)
FOR X=X1 TO X2:POINT X,Y:NEXT
ENDPROC

Notes:

  - These routines should do the same thing, but not what the original
question asked. The original question was rasterising a polygon, whereas
these draw lines. This makes a superficial difference.

  - The lines it draws include all pixels through which the geometrical
line passes. This is not the prettiest choice.

  - In machine code, you'd define N'=DY-N as the decision variable for
my
method, as the increment would then double as the test. This makes it
even
more similar to the Bresenham method!

  - In machine code, the IF used for the divide would not involve branch
instructions, merely temporarily setting a mask word to record the sign
of
DX.

  - The implementation of PROChorizontalline should be considered only
as
a specification. Optimise at will.

 
 
 

Fast quad plotter

Post by mark » Fri, 29 Oct 1999 04:00:00




[snip]

Quote:> Notes:

>   - These routines should do the same thing, but not what the original
> question asked. The original question was rasterising a polygon, whereas
> these draw lines. This makes a superficial difference.

>   - The lines it draws include all pixels through which the geometrical
> line passes. This is not the prettiest choice.

There is an algorithm described in '3D Computer Graphics' by Alan Watt
(Addison Wesley) attributed to Swanson & Thayer which is another incremental,
and (more importantly) integer algorithm.

It only draws one pixel per increment on the line (eg. one pixel increments
in one of the axes). The resulting line is discontinuous in many cases - but
then as you are probably going to be filling the polygon with a horizontal
line fill, this is sufficient as there are (in the case of convex polygons)
exactly two points per horizontal line to fill between. There is clearly no
point in drawing the boundary pixels seperately from filling.

The suggested method of rendering the polygon is to build a list of the X
pixels on the polygon boundary per y pixel of the polygon, and then plotting
the boundary pixels at the same time as filling the interior.

Boths halves of the bi-linear interpolation required for Gourrard shading can
also be folded into these two stages.

[snip]

 
 
 

1. Wanted: Fast triangle / quad plot code.

I'm writing some 3D graphics code which, at the moment, uses the standard
plot 85,.. triangle plot to render polygons in the scene. I'm sure somebody
has a faster alternative!? I'm writing it in Acorns Desktop C (not the
current C++ release, the previous one), so I need to be able to integrate
it with this. If anyone can help, and doesn't mind letting me use their
code then I would really appreciate it. Triangle / quadrilateral plotters
would both be useful, preferably mode independant, but I'm using mode 28
if not (256 colours, 640x512 I think).

Thanks in advance, Russell.

2. OWL 2.0 Printer dialog problem

3. Wanted: Quad CD with vertical mounting clips

4. news propagation test

5. YES Quad speed IDE drives/Connecting CD-ROM audio to internal speaker of RISCPC

6. Hotsync settings help request

7. quad speed cd drives and ro3.5

8. Q: To Kermit Gods...fastest possible transfer

9. Quad speed SCSI CD rom drive

10. NEC Quad CD ROM drive

11. Quad-word boundary

12. Panasonic Quad Speed IDE for a RiscPC600

13. Quad floppies 4 sale