Restored from previous forum. Originally posted by fweil.
Hello,
Here is a copy of a document I made for a young friend of mine, to explain him how to use geometry for drawings, and how to tackle textured facets for 3D drawings.
Hope this will please other friends here.
How to fill a triangle
Basics are described here with a sample program to explain how to go from theory to application.
Drawing a triangle is rather easy to do. You have just to draw three lines based on three points A, B, C, drawing then vectors (A,B) (A,C) and (B,C).
But it is a bit more complicate to fill this triangle using low level method like painting it pixel by pixel or line by line.
Here we assume the only tool we have is a line by line painting. A pixel by pixel system would not make much difference as a line is a set of pixels.
Depending on the language you use, it may exist a paint tool painting with a given color from a point in all directions, until the paint tool arrives to a given border color to stop in that direction.
This simple paint tool is much more complicate it seems at start.
Using our basic lien by line painting system will make necessary to think ‘how to’ build a method not able to go in any directions.
Assuming a regular triangle is defined by points A(xA, yA), B(xB, yB) and C(xC, yC), we can draw easily the triangle using a set of commands :
LineXY(xA, yA, xB, yB)
LineXY(xA, yA, xC, yC)
LineXY(xB, yB, xC, yC)
Now we would like to paint this triangle.
Our paint tool is a line by line system. So it is necessary to draw a list of lines from one starting point to the opposite border of the triangle. Line by line here means horizontal.
Considering a regular triangle significates that we have to know which point is the lowest or highest, to start from it and go line by line to the other side.
We can for example sort the points to have finally point1 the highest, point2 and point3 being lower in Y direction.
First we need a tool to compare y coordinates of all points to find the highest … and the lowest.
But when we will paint the triangle from top to bottom, we will reach point2 or point3 at different times.
So we have to know about the highest point, the medium point and the lowest. Then we can fill using horizontal lines from highest to medium, and then from lowest to medium using computable limits represented by lines.
Initial formulas we need are :
Equation of a regular line :
y = a * x + b
Equation of the line containing A(xA, yA) and B(xB, yB) points :
yA = a * xA + b
yB = a * xB + b
(yA – yB) = a * xA + b – a * xB - b
(yA – yB) = a * (xA – xB)
a = (yA – yB) / (xA – xB)
b = yA – a * xA
Based on this formulas, we can now find the equations to know about the limits of each line to draw between both lines from the reference point to other points :
If A is the reference point and B and C the other points, we have to know the A,B A,C equations to draw horizontal lines from A to the closest y coordinate point B or C. After it will remain lines to draw from the last point to its opposites using two other lines equations.
The following sample source is PureBasic code using the preceeding explanations.
Procedure.l IMin(a.l, b.l)
If a b
ProcedureReturn a
Else
ProcedureReturn b
EndIf
EndProcedure
Procedure.l IMin3(a.l, b.l, c.l)
d.l = IMin(a, b)
d.l = IMin(d, c)
ProcedureReturn d
EndProcedure
Procedure.l IMax3(a.l, b.l, c.l)
d.l = IMax(a, b)
d.l = IMax(d, c)
ProcedureReturn d
EndProcedure
Procedure.l IMed3(a.l, b.l, c.l)
x = IMin3(a, b, c)
y = IMax3(a, b, c)
If a x And a y
z = a
EndIf
If b x And b y
z = b
EndIf
If c x And c y
z = c
EndIf
ProcedureReturn z
EndProcedure
Procedure DrawFacet(Xa.l, Ya.l, Xb.l, Yb.l, Xc.l, Yc.l)
A2.Point
B2.Point
C2.Point
;
; The way to find the rectangle that contains the triangle
;
A2\x = IMin3(Xa, Xb, Xc)
A2\y = IMin3(Ya, Yb, Yc)
B2\x = IMax3(Xa, Xb, Xc)
B2\y = IMax3(Ya, Yb, Yc)
C2\x = IMed3(Xa, Xb, Xc)
C2\y = IMed3(Ya, Yb, Yc)
; Debug "Xa=" + Str(Xa) + " Ya=" + Str(Ya) + " Xb=" + Str(Xb) + " Yb=" + Str(Yb) + " Xc=" + Str(Xc) + " Yc=" + Str(Yc) + " A2\x=" + Str(A2\x) + " A2\y=" + Str(A2\y) + " B2\x=" + Str(B2\x) + " B2\y=" + Str(B2\y)
LineXY(A2\x, A2\y, A2\x, B2\y, #blue)
LineXY(A2\x, B2\y, B2\x, B2\y, #blue)
LineXY(B2\x, B2\y, B2\x, A2\y, #blue)
LineXY(B2\x, A2\y, A2\x, A2\y, #blue)
DrawingMode(5)
Box(Xa - 4, Ya - 4, 8, 8, #red)
FrontColor(0, 255, 0)
Locate(Xa + 4, Ya + 4)
DrawText("A")
Box(Xb - 4, Yb - 4, 8, 8, #red)
FrontColor(0, 255, 0)
Locate(Xb + 4, Yb + 4)
DrawText("B")
Box(Xc - 4, Yc - 4, 8, 8, #red)
FrontColor(0, 255, 0)
Locate(Xc + 4, Yc + 4)
DrawText("C")
;
; Look for :
; A, B line with coeffs aAB, bAB
; A, C line with coeffs aAC, bAC
; B, C line with coeffs aBC, bBC
;
aAB.f = (Yb - Ya) / (Xb - Xa)
bAB.f = Yb - aAB * Xb
aAC.f = (Yc - Ya) / (Xc - Xa)
bAC.f = Yc - aAC * Xc
aBC.f = (Yc - Yb) / (Xc - Xb)
bBC.f = Yc - aBC * Xc
; Debug "aAB=" + StrF(aAB) + " bAB=" + StrF(bAB) + " aAC=" + StrF(aAC) + " bAC=" + StrF(bAC) + " aBC=" + StrF(aBC) + " bBC=" + StrF(bBC)
;
; Draw lines from x = 0 to x = 1024
;
LineXY(0, bAB, 1024, aAB * 1024 + bAB, #yellow)
LineXY(0, bAC, 1024, aAC * 1024 + bAC, #yellow)
LineXY(0, bBC, 1024, aBC * 1024 + bBC, #yellow)
If B2\y = Ya ; A is the upper point, we draw between A,B and A,C
For i = B2\y To C2\y Step -1
LineXY((i - bAB) / aAB, i, (i - bAC) / aAC, i, #cyan)
Next
If C2\y = Yb ; If the drawing stopped at level of B, we must still draw from C,A and C,B
For i = A2\y To C2\y
LineXY((i - bAC) / aAC, i, (i - bBC) / aBC, i, #magenta)
Next
Else ; If the drawing stopped at level of C, we must still draw from B,A and C,B
For i = A2\y To C2\y
LineXY((i - bAB) / aAB, i, (i - bBC) / aBC, i, #magenta)
Next
EndIf
ElseIf B2\y = Yb ; B is the upper point, we draw between B,A and B,C
For i = B2\y To C2\y Step -1
LineXY((i - bAB) / aAB, i, (i - bBC) / aBC, i, #cyan)
Next
If C2\y = Ya ; If the drawing stopped at level of A, we must still draw from C,A and C,B
For i = A2\y To C2\y
LineXY((i - bAC) / aAC, i, (i - bBC) / aBC, i, #magenta)
Next
Else ; If the drawing stopped at level of C, we must still draw from A,C and A,B
For i = A2\y To C2\y
LineXY((i - bAB) / aAB, i, (i - bAC) / aAC, i, #magenta)
Next
EndIf
ElseIf B2\y = Yc ; C is the upper point, we draw between A,C and B,C
For i = B2\y To C2\y Step -1
LineXY((i - bAC) / aAC, i, (i - bBC) / aBC, i, #cyan)
Next
If C2\y = Ya ; If the drawing stopped at level of A, we must still draw from A,B and B,C
For i = A2\y To C2\y
LineXY((i - bAB) / aAB, i, (i - bBC) / aBC, i, #magenta)
Next
Else ; If the drawing stopped at level of B, we must still draw from A,C and A,B
For i = A2\y To C2\y
LineXY((i - bAB) / aAB, i, (i - bAC) / aAC, i, #magenta)
Next
EndIf
EndIf
EndProcedure
A.Point
B.Point
C.Point
InitSprite()
If OpenScreen(1024, 768, 24, "")
If InitKeyboard()
Quit.l = #FALSE
Repeat
A\x = Random(300) + 200
A\y = Random(300) + 200
B\x = Random(300) + 200
B\y = Random(300) + 200
C\x = Random(300) + 200
C\y = Random(300) + 200
ClearScreen(0, 0, 0)
StartDrawing(ScreenOutput())
LineXY(A\x, A\y, B\x, B\y, #white)
LineXY(B\x, B\y, C\x, C\y, #white)
LineXY(C\x, C\y, A\x, A\y, #white)
DrawFacet(A\x, A\y, B\x, B\y, C\x, C\y)
StopDrawing()
FlipBuffers()
ExamineKeyboard()
If KeyboardPushed(#PB_Key_Escape)
Quit = #TRUE
EndIf
Delay(1000)
Until Quit
EndIf
EndIf
End
PureBasic allows to create sprites, which are textures primitives to draw a bitmap image pattern with given properties.
PureBasic has some transformations features on sprites to draw directly a sprite with given coordinates, size and position.
The same effect as described above could have a really short way to be coded using sprites.
This corresponds to a higher level paint tool than we explained.
Assuming a sprite can be defined with a given texture, this sprite, using the so called 3Dsprite mode, can have transformations to paint a facet (4 vertices based) with given vertices coordinates. As sprite library runs an optimised code this is powerful to use it for drawing fast textured triangles.
The following source draws triangles in the same way than above, but using sprites.
A.Point
B.Point
C.Point
InitSprite()
If OpenScreen(1024, 768, 24, "")
InitSprite3D()
CreateSprite(1, 32, 32, #PB_Sprite_Texture)
StartDrawing(SpriteOutput(1))
Box(0, 0, 32, 32, #green)
StopDrawing()
CreateSprite3D(1, 1)
Sprite3DQuality(1)
If InitKeyboard()
Quit.l = #FALSE
Repeat
A\x = Random(300) + 200
A\y = Random(300) + 200
B\x = Random(300) + 200
B\y = Random(300) + 200
C\x = Random(300) + 200
C\y = Random(300) + 200
ClearScreen(0, 0, 0)
Start3D()
TransformSprite3D(1, A\x, A\y, B\x, B\y, A\x, A\y, C\x, C\y)
DisplaySprite3D(1, 0, 0, 255)
Stop3D()
FlipBuffers()
ExamineKeyboard()
If KeyboardPushed(#PB_Key_Escape)
Quit = #TRUE
EndIf
Delay(1000)
Until Quit
EndIf
EndIf
End
Francois Weil
14, rue Douer
F64100 Bayonne