Qbasicnews.com

Qbasicnews.com > QBasic > QB Discussion & Programming Help > Filling Polygons
Full Version: Filling Polygons
You're currently viewing a stripped down version of our content. View the full version with proper formatting.

Rokkuman

06-28-2003, 03:41 PM
Well I have an understanding of SIN and COS (thanks nate, aether and bluekb!), but how do people fill polygons in? I'm thinking there may be a paint command that is only used when the "paint point" is in view, but how would I make the computer calculate whether it's in view or not?

Agamemnus

06-28-2003, 06:08 PM
hm........

you could just draw lines that form into polygons. therefore, no painting...

na_th_an

06-28-2003, 08:29 PM
There is a method called "scan line filler". I think ninkazu showed some stuff a while ago.

Basicly, you have to find the highest vertex in your polygon, and the lowest. Also you have to find the vertices most left and most right. You make a loop from top to bottom then, and an inner loop from left to right (using the values you have calculated). Using geometry and maths, you determine in each loop whether if you are inside your polygon or outside, and act consequently (if you are inside, you plot pixels).

This is not trivial, but maybe I can find some code... Keep in tune.

aetherfox

06-29-2003, 01:09 AM
Is the undoubted slowness worth the colour? I honestly don't thing so...

Just use a graphic and rotate it, just like we talked about on msn.

Rokkuman

06-29-2003, 04:26 AM
Thanks Nathan, I'm interested in seeing this code... because I have next to no clue what you just said. It looks like it's right though.

na_th_an

06-29-2003, 07:49 AM
Lotsa maths, but easy to understand pseudocode:

http://www.mat.uni.torun.pl/~wrona/3d_tu...llers.html

relsoft

06-30-2003, 10:42 AM
If you use SETVIDEOSEG you can use PAINT

Just do this:

'Assuming you use Tris
xc=(x1+x2+x3)\3
yc=(y1+y2+y3)\3
Paint(xc,yc)

Or this:



Code:
DEFINT A-Z
DECLARE SUB Hline (xx1%, xx2%, y%, Colour%)
DECLARE SUB CalcNormals (Model() AS ANY, ModelConnect() AS ANY, V() AS ANY)
DECLARE SUB FlatTri (x1%, y1%, x2%, y2%, x3%, y3%, Col%)
DECLARE SUB DrawCube (Model() AS ANY, Vector() AS ANY)
DECLARE SUB LoadCube (Model() AS ANY, Vector() AS ANY)
DECLARE SUB RotateAndProject (Model() AS ANY, AngleX%, AngleY%, AngleZ%)
DECLARE SUB RotNormals (V() AS ANY, V2() AS ANY, AngleX%, AngleY%, AngleZ%)
DECLARE SUB BLine (x1, y1, x2, y2, Colour)
'$DYNAMIC
DIM SHARED buffer(32001)
'$STATIC
DIM SHARED lutsegy(199) AS LONG

CONST pi180 = 3.141592654# / 180

FOR N& = 0 TO 199
lutsegy(N&) = N& * 320 + 4
NEXT

TYPE Point3d
x AS SINGLE 'Normal 3d coords
y AS SINGLE
Z AS SINGLE
Xr AS SINGLE
Yr AS SINGLE
Zr AS SINGLE
ScrX AS INTEGER 'Translated and projected
ScrY AS INTEGER '2d Coords
END TYPE

TYPE PolyType
p1 AS INTEGER
p2 AS INTEGER
p3 AS INTEGER
Clr1 AS INTEGER
Clr2 AS INTEGER
Clr3 AS INTEGER
END TYPE

TYPE VectorType
x AS SINGLE
y AS SINGLE
Z AS SINGLE
END TYPE


CONST LENS = 256 'Z
CONST XCENTER = 160 '??
CONST YCENTER = 100 '??


CONST PI = 3.14151693#

DIM SHARED LCOS(359) AS SINGLE
DIM SHARED LSIN(359) AS SINGLE

REDIM SHARED CubeModel(1) AS Point3d
REDIM SHARED CubePoly(1) AS PolyType
REDIM SHARED CubeNormal(1) AS VectorType
REDIM SHARED CubeNormal2(1) AS VectorType
DIM SHARED ThetaX, ThetaY, ThetaZ
DIM SHARED Zcenter, CamX, CamY
DIM SHARED LightNormal AS VectorType

'PreCalc sin and cos lookuptable

FOR I = 0 TO 359
A! = I * PI / 180
LCOS(I) = COS(A!)
LSIN(I) = SIN(A!)
NEXT I

LightNormal.x = 0 'Light is from the camera
LightNormal.y = 0
LightNormal.Z = -1

LoadCube CubeModel(), CubePoly()
RotateAndProject CubeModel(), ThetaX, ThetaY, ThetaZ
CalcNormals CubeModel(), CubePoly(), CubeNormal()

CLS
SCREEN 13
RANDOMIZE TIMER

'Grey Scale the Palette
FOR I = 0 TO 255
OUT &H3C8, I
OUT &H3C9, (I \ 4)
OUT &H3C9, (I \ 4) * .9
OUT &H3C9, (I \ 4) * .1
NEXT I


ThetaX = 0
ThetaY = 0
ThetaZ = 0
Zcenter = LENS


buffer(0) = 2560: buffer(1) = 200
DEF SEG = VARSEG(buffer(0))

t# = TIMER
DO


ThetaX = (ThetaX + 1) MOD 360
ThetaY = (ThetaY + 1) MOD 360
ThetaZ = (ThetaZ + 1) MOD 360


RotateAndProject CubeModel(), ThetaX, ThetaY, ThetaZ
RotNormals CubeNormal(), CubeNormal2(), ThetaX, ThetaY, ThetaZ
REDIM buffer(32001)
buffer(0) = 2560: buffer(1) = 200
DrawCube CubeModel(), CubePoly()
PUT (0, 0), buffer, PSET
frames& = frames& + 1
LOOP UNTIL INKEY$ <> ""
COLOR 63
PRINT frames& / (TIMER - t#)
DO: LOOP UNTIL LEN(INKEY$)

END

'numPoints
NumPoints:
DATA 8


'vertices of Cube
VertexData:
DATA -50,50,50
DATA 50,50,50
DATA 50,50,-50
DATA -50,50,-50
DATA -50,-50,50
DATA 50,-50,50
DATA 50,-50,-50
DATA -50,-50,-50

NumPoly:
DATA 12
ConnectData:
DATA 5,4,0, 5,0,1
DATA 6,2,3, 3,7,6
DATA 6,5,1, 6,1,2
DATA 7,0,4, 7,3,0
DATA 6,7,4, 6,4,5
DATA 0,3,2, 1,0,2

SUB BLine (x1, y1, x2, y2, Colour)
DIM addr AS LONG
  x = x1: xinc = 1
  y = y1: yinc = 1: ainc = 320

  dy = y2 - y1 'Determine delta y
  dx = x2 - x1 'Determine delta x

  IF dy < 0 THEN dy = -dy: yinc = -1: ainc = -320 'Correct negative delta y
  IF dx < 0 THEN dx = -dx: xinc = -1                     'Correct negative delta x

  addr = lutsegy(y1) + x1 'Determine starting location

  IF (x >= 0) AND (x <= 319) AND (y >= 0) AND (y <= 199) THEN POKE addr, Colour

  IF dx > dy THEN
    d = dy + dy - dx       'Determine initial "check" value
    d0 = dy + dy           'Determine constant y increment
    d1 = 2 * (dy - dx)     'Determine variable y increment
    DO WHILE x <> x2       'Draw line if line not a point
      x = x + xinc         'Increment x value
      addr = addr + xinc   'Increment address value accordingly
      IF d < 0 THEN
        d = d + d0
      ELSE
        d = d + d1
        y = y + yinc
        addr = addr + ainc
      END IF
      IF (x >= 0) AND (x <= 319) AND (y >= 0) AND (y <= 199) THEN POKE addr, Colour
    LOOP
  ELSE
    d = dx + dx - dy     'Determine initial 'check' value
    d0 = dx + dx         'Determine constant x increment
    d1 = 2 * (dx - dy)   'Determine variable x increment
    DO WHILE y <> y2     'Draw line if line not a point
      y = y + yinc       'Increment y value
      addr = addr + ainc 'Increment address value accordingly
      IF d < 0 THEN
        d = d + d0
      ELSE
        d = d + d1
        x = x + xinc
        addr = addr + xinc
      END IF
      IF (x >= 0) AND (x <= 319) AND (y >= 0) AND (y <= 199) THEN POKE addr, Colour
    LOOP
  END IF

END SUB

SUB CalcNormals (Model() AS Point3d, ModelConnect() AS PolyType, V() AS VectorType)

FOR I = 1 TO UBOUND(V)

p1 = ModelConnect(I).p1
p2 = ModelConnect(I).p2
p3 = ModelConnect(I).p3
x1 = Model(p1).x
x2 = Model(p2).x
x3 = Model(p3).x
y1 = Model(p1).y
y2 = Model(p2).y
y3 = Model(p3).y
Z1 = Model(p1).Z
Z2 = Model(p2).Z
Z3 = Model(p3).Z

ax! = x2 - x1
bx! = x3 - x2
ay! = y2 - y1
by! = y3 - y2
az! = Z2 - Z1
bz! = Z3 - Z2

'Cross product
xnormal! = ay! * bz! - az! * by!
ynormal! = az! * bx! - ax! * bz!
Znormal! = ax! * by! - ay! * bx!

'Normalize
Mag! = SQR(xnormal! ^ 2 + ynormal! ^ 2 + Znormal! ^ 2)
IF Mag! <> 0 THEN
xnormal! = xnormal! / Mag!
ynormal! = ynormal! / Mag!
Znormal! = Znormal! / Mag!
END IF

IF Znormal! < -1 THEN
Znormal! = -1
ELSEIF Znormal! > 1 THEN
Znormal! = 1
END IF

IF xnormal! < -1 THEN
xnormal! = -1
ELSEIF xnormal! > 1 THEN
xnormal! = 1
END IF

IF ynormal! < -1 THEN
yxnormal! = -1
ELSEIF ynormal! > 1 THEN
ynormal! = 1
END IF

V(I).x = xnormal!
V(I).y = ynormal!
V(I).Z = Znormal!

NEXT I
END SUB

SUB DrawCube (Model() AS Point3d, Poly() AS PolyType) STATIC

FOR I = 1 TO UBOUND(Poly)
x1 = Model(Poly(I).p1).ScrX 'Get triangles from "projected"
x2 = Model(Poly(I).p2).ScrX 'X and Y coords since Znormal
x3 = Model(Poly(I).p3).ScrX 'Does not require a Z coord
y1 = Model(Poly(I).p1).ScrY 'V1= Point1 connected to V2 then
y2 = Model(Poly(I).p2).ScrY 'V2 to V3 and so on...
y3 = Model(Poly(I).p3).ScrY


'Use the Znormal,the Ray perpendicular(Orthogonal) to the XY plane
'Defined by the Triangle (X1,Y1,X2,Y2,X3,Y3)
'if Less(<) 0 then its facing in the opposite direction so
'don't plot. If =>0 then its facing towards you so Plot.
Znormal = (x2 - x1) * (y1 - y3) - (y2 - y1) * (x1 - x3)
IF Znormal < 0 THEN
nx! = CubeNormal2(I).x
ny! = CubeNormal2(I).y
nz! = CubeNormal2(I).Z
lx! = LightNormal.x
ly! = LightNormal.y
lz! = LightNormal.Z
Dot! = (nx! * lx!) + (ny! * ly!) + (nz! * lz!)
IF Dot! < 0 OR Dot! > 1 THEN
Dot! = 0
END IF
Clr = Dot! * 255
C1 = Poly(I).Clr1
C2 = Poly(I).Clr2
C3 = Poly(I).Clr3
FlatTri x1, y1, x2, y2, x3, y3, Clr
END IF

NEXT I

END SUB

SUB FlatTri (x1%, y1%, x2%, y2%, x3%, y3%, c%)
DIM addr AS LONG
'DRAWS TRIANGLE WITH FLAT SHADING
'
'reorder coords so y1<y2<y3
'
BLine x1%, y1%, x2%, y2%, c% ' triangle outline
BLine x2%, y2%, x3%, y3%, c% '
BLine x3%, y3%, x1%, y1%, c% '

IF y1% > y2% THEN SWAP y1%, y2%: SWAP x1%, x2%
IF y1% > y3% THEN SWAP y1%, y3%: SWAP x1%, x3%
IF y2% > y3% THEN SWAP y2%, y3%: SWAP x2%, x3%

' need to check for divide by zero..

ydiffa% = y2% - y1%
IF ydiffa% THEN d1! = ((x2% - x1%)) / ydiffa%

ydiffb% = y3% - y2%
IF ydiffb% THEN d2! = ((x3% - x2%)) / ydiffb%

ydiffc% = 1 + y3% - y1%
IF ydiffc% THEN d3! = ((x3% - x1%)) / ydiffc%

lx! = x1%
rx! = x1%

FOR y% = y1% TO y2% - 1
'''''BLine INT(lx!), y%, INT(rx!), y%, c%
Hline INT(lx!), INT(rx!), y%, c%
lx! = lx! + d1!
rx! = rx! + d3!
NEXT

lx! = x2%

FOR y% = y2% TO y3%
'''''''''BLine INT(lx!), y%, INT(rx!), y%, c%
Hline INT(lx!), INT(rx!), y%, c%
lx! = lx! + d2!
rx! = rx! + d3!
NEXT y%
END SUB

SUB Hline (xx1, xx2, y, Colour)

'This is faster as this only uses scanline Hpoke
x1 = xx1
x2 = xx2
y1 = yy1
y2 = yy2

IF x1 > x2 THEN SWAP x1, x2
IF y1 > y2 THEN SWAP y1, y2

IF x1 < 0 THEN
    xxd = x1 + (x2 - x1) + 1
    IF xxd < 0 THEN EXIT SUB
    x1 = 0
ELSEIF x1 > 319 THEN
    EXIT SUB
END IF

IF x2 > 319 THEN
    xxd = x2 - ((x2 - x1) + 1)
    IF xxd > 319 THEN EXIT SUB
    x2 = 319
ELSEIF x2 < 0 THEN
    EXIT SUB
END IF


IF y < 0 OR y > 199 THEN EXIT SUB

addr& = lutsegy(y) + x1

sx = 0
FOR xx = x1 TO x2
    POKE addr& + sx, Colour
    sx = sx + 1
NEXT xx


END SUB

SUB LoadCube (Model() AS Point3d, Tri() AS PolyType) STATIC

RESTORE NumPoints
READ MaxVertex
REDIM Model(1 TO MaxVertex) AS Point3d


RESTORE VertexData
FOR V = 1 TO UBOUND(Model)
READ Xt, Yt, Zt
Model(V).x = Xt
Model(V).y = Yt
Model(V).Z = Zt
NEXT V

RESTORE NumPoly
READ MaxPoly
REDIM Tri(MaxPoly) AS PolyType

RESTORE ConnectData

FOR V = 1 TO UBOUND(Tri)
READ T1, T2, T3
Tri(V).p1 = T1 + 1
Tri(V).p2 = T2 + 1
Tri(V).p3 = T3 + 1
Tri(V).Clr1 = 50 + INT(RND * 100)
NEXT V


REDIM CubeNormal(1 TO UBOUND(Tri)) AS VectorType
REDIM CubeNormal2(1 TO UBOUND(Tri)) AS VectorType




END SUB

SUB RotateAndProject (Model() AS Point3d, AngleX, AngleY, AngleZ) STATIC

'Precalculate the SIN and COS of each angle
CX! = LCOS(AngleX)
sx! = LSIN(AngleX)
CY! = LCOS(AngleY)
SY! = LSIN(AngleY)
CZ! = LCOS(AngleZ)
SZ! = LSIN(AngleZ)

'Transformation matrix formula
'This is actually 16(or 12) equations but I pared it down to 9
'since TX4=0,TY4=0,TZ4=0,13 to 16th =0,0,0,1 (yes Doom!!!)

TX1! = CY! * CZ!
TX2! = CY! * SZ!
TX3! = -SY!
TY1! = CX! * -SZ! + sx! * SY! * CZ!
TY2! = CX! * CZ! + sx! * SY! * SZ!
TY3! = sx! * CY!
TZ1! = -sx! * -SZ! + CX! * SY! * CZ!
TZ2! = -sx! * CZ! + CZ! * SY! * SZ!
TZ3! = CX! * CY!


FOR I = 1 TO UBOUND(Model)

x! = Model(I).x 'Load Original model
y! = Model(I).y
Z! = Model(I).Z

RotX! = (x! * TX1! + y! * TY1! + Z! * TZ1!)
RotY! = (x! * TX2! + y! * TY2! + Z! * TZ2!)
RotZ! = (x! * TX3! + y! * TY3! + Z! * TZ3!)

Model(I).Xr = RotX!
Model(I).Yr = RotY!
Model(I).Zr = RotZ!


'Project
Distance% = (LENS - RotZ!)
IF Distance% THEN
Model(I).ScrX = (Zcenter * RotX! / Distance%) + XCENTER + CamX
Model(I).ScrY = -(Zcenter * RotY! / Distance%) + YCENTER + CamY
ELSE
END IF
NEXT I

END SUB

SUB RotNormals (V() AS VectorType, V2() AS VectorType, AngleX, AngleY, AngleZ)

'Precalculate the SIN and COS of each angle
CX! = LCOS(AngleX)
sx! = LSIN(AngleX)
CY! = LCOS(AngleY)
SY! = LSIN(AngleY)
CZ! = LCOS(AngleZ)
SZ! = LSIN(AngleZ)

'Transformation matrix formula
'This is actually 16(or 12) equations but I pared it down to 9
'since TX4=0,TY4=0,TZ4=0,13 to 16th =0,0,0,1 (yes Doom!!!)

TX1! = CY! * CZ!
TX2! = CY! * SZ!
TX3! = -SY!
TY1! = CX! * -SZ! + sx! * SY! * CZ!
TY2! = CX! * CZ! + sx! * SY! * SZ!
TY3! = sx! * CY!
TZ1! = -sx! * -SZ! + CX! * SY! * CZ!
TZ2! = -sx! * CZ! + CZ! * SY! * SZ!
TZ3! = CX! * CY!


FOR I = 1 TO UBOUND(V)

x! = V(I).x 'Load Original vector
y! = V(I).y
Z! = V(I).Z

RotX! = (x! * TX1! + y! * TY1! + Z! * TZ1!)
RotY! = (x! * TX2! + y! * TY2! + Z! * TZ2!)
RotZ! = (x! * TX3! + y! * TY3! + Z! * TZ3!)

IF RotZ! < -1 THEN
RotZ! = -1
ELSEIF RotZ! > 1 THEN
RotZ! = 1
END IF

IF RotX! < -1 THEN
RotX! = -1
ELSEIF RotX! > 1 THEN
RotX! = 1
END IF

IF RotY! < -1 THEN
RotY! = -1
ELSEIF RotY! > 1 THEN
RotY! = 1
END IF


V2(I).x = RotX!
V2(I).y = RotY!
V2(I).Z = RotZ!
NEXT I

END SUB

Blitz

06-30-2003, 02:59 PM
There's a x86 instructions that's called fillpoly, it magically does that job.

heehe, j/k.
I'll try to explain this as simple as possible. But it really depends on how much knowledge you have. If you know how to draw a line it will help you greatly.

Let's say you have a three points that form a triangle like this.
Code:
a
            .
           . .
          .   .
         .     .
        .       .
       .         .
      .           .
     .             .
    .               .
    c               b


Points a-c forms the left edge (line) and points a-b form the right edge. Now, what you're interest in is the points between a-c and a-b. If you have these points, you can just draw a straight line from the left side to the right. If you continue to do this for the entire height you have your polygon filled. So how do you do this? Well it's simple. You have to calculate the change in x position along each edge. You calculate the delta ( the change ) like so.

x2-x1/y2-y1
Or in this case

left_dxdy = (c.x-a.x) / (c.y-a.y)
rght_dxdy = (b.x-a.x) / (b.y-a.y)

Now that you have the change you can do this

Code:
left_x = a.x
rght_x = a.x

for  y = a.y to c.y
    line ( left_x, y )-( rght_x, y ), col
    left_x = left_x + left_dxdy
    rght_x = rght_x + rght_dxdy
next y

This will fill the triangle one scanline (horizontal line) at a time like so

Code:
a
            .
           ...
          .   .
         .     .
        .       .
       .         .
      .           .
     .             .
    .               .
    c               b

Code:
a
            .
           ...
          .....
         .     .
        .       .
       .         .
      .           .
     .             .
    .               .
    c               b

Code:
a
            .
           ...
          .....
         .......
        .       .
       .         .
      .           .
     .             .
    .               .
    c               b

And so on, of course this only applies to this case where you have a flat bottom triangle. There are two other cases, but both are filled the same way, but with different setup code. But this should be enough to get you started. Try it.
Qbasicnews.com > QBasic > QB Discussion & Programming Help > Filling Polygons