A matter of perspective...

[xlucas]

Alright, my life as a programmer has been pretty two-dimensional. I have made some very simple approaches to 3D when I have needed to calculate a few things, but never before tried to create any kind of 3D engine. Now I have to do it. It's a very simple one, and I'm having the most elemental of the confusions here. I don't seem to completely understand how to properly apply perspective.

To some of you, this will be a very typical confusion and will point me in the right direction. My reasoning is like this: I have a set of 3D verteces (x, y, z) that I've already rotated and added offsets to so that I'm looking at it from the camera. That's all wonderful. Now I want the 2D projections of them on the screen. If the vertex is further, the deltas should be smaller, so I should divide the Xs and the Ys by their Zs, right? When I do that, everything is so tiny, so I figure I need to scale it up. Makes sense, since the screen is not 1 pixel wide. Then I figure:

x' = screen_height * x / z
y' = screen_height * y / z

I use height in both because I don't want the image streched and the height is smaller than the width and I don't want the image cropped either. Well, it looks a lot better, but I have the following problems:

- Objects are somewhat smaller than I wanted, but if I use a larger scale, that affects how "near" an object looks to the one just behind it, which I don't want.
- When I want to draw a polygon which has some verteces in front of the camera and some behind the camera, I can't just skip it, but the projection goes crazy because lines cross. If I saturate it, so that every z < 0 becomes 0, then I have the next problem.
- If a vertex is at zero or near zero, the projection shoots up to infinity. This not necessarily is a problem. I can just replace it with a very high number and seems to work fine. But I reason that if I do this, then I'm reaching a singularity and now what happens with negative Z?
- Lastly, I don't see where in the game plays the angle of view, that is, how can I make sure that, say, my screen width be set to a certain angle, say, 30 degrees or 45 degrees. Same way, I don't know where in the equation to put the distance from my eyes to the screen. I know these two variables have to be parameters of this thing, but I get lost on where.

I'll appreciate all help. Only please help me do this myself. I don't want to use a library.

[paul doe]

Hola compis,

Do you have any code handy? It can help immensely if both of us can work on the same code. I need to see how you define your camera, and what your conventions are. Are you using a right handed coordinate system, or a left handed one? The math is slightly different for both, so be aware of this, lest you mix the two and end up with strange results XD

Have a look at this:
viewtopic.php?f=8&t=26000

There are a lot of interesting stuff there. The paper plane demo uses 4x4 matrices, to be able to do perspective calculations both ways (to-from). You would eventually end using all the math that's included in the demo, and then some more, so it's a good idea to have it handy. It's really the same math as OpenGL uses (I use it precisely for that), only in software as you requested =D

We'll address the questions as soon as you post some code, ok? Looking forward.

[paul doe]

I'll try to very quickly address some of the problems you're having:

- When I want to draw a polygon which has some verteces in front of the camera and some behind the camera, I can't just skip it, but the projection goes crazy because lines cross. If I saturate it, so that every z < 0 becomes 0, then I have the next problem.

This happens because you have to clip drawing coordinates to the near clipping plane, so they don't get negative coordinates (the near clipping plane is always in front of the camera). Look at the drawLine3d procedure of the paper plane demo (which is, by the way, very haphazardly built):

Code: Select all

sub drawLine3d( byref cam as camera, byref p1 As vec4, byref p2 As vec4, byval c as uint32 )
    dim as vec4 pos1, pos2
		
	'' project the points
    pos1 = cam.transform( p1 - cam.getPos() )
    pos2 = cam.transform( p2 - cam.getPos() )

	dim as single x1, y1, x2, y2
		
	'' clip the segment
    dim as integer visible = clipSegment( cam, pos1, pos2 )
		
	'' if its visible, draw it
    if( visible ) then
      dim as single z1, z2
			
			'' do the perspective projection
      cam.perspective( pos1, cam.projectionPlane, x1, y1, z1 )
      cam.perspective( pos2, cam.projectionPlane, x2, y2, z2 )

      line( x1, y1 ) - ( x2, y2 ), c

    end if
end sub

As you can see, you have to clip the segments before drawing them. And the clipSegment procedure is defined as:

Code: Select all

function clipSegment( byref cam as camera, byref s1 as vec4, byref s2 as vec4 ) as integer
	/'
		clip both vertices of a line if necessary
		
		note that this 'clipping' is only done on the near plane, not on the scene
		
		the sensible (and correct) way to do this would be to clip them against
		the view frustum; but alas, in order to keep the code short and clear
		the calculation of the frustum was removed from the camera class. Hence
		this crappy function.
		
		Clipping (especially against the near plane) is important, because if you
		don't clip, when one of the line endpoints goes behind the near clipping
		plane, it gets a negative coordinate (due to the projection), and the line
		segment is no longer valid
	'/
	if( s1.z >= cam.nearClip() and s2.z >= cam.nearClip() ) then
	    ' Neither one is behind the camera, draw them both
	    return( -1 )
	elseIf( s1.z < cam.nearClip() and s2.z >= cam.nearClip() ) then
	    ' First coordinate behind the camera, clip it
	    s1.x = s1.x + ((cam.nearClip() - s1.z) / (s2.z - s1.z)) * (s2.x - s1.x)
	    s1.y = s1.y + ((cam.nearClip() - s1.z) / (s2.z - s1.z)) * (s2.y - s1.y)
	    s1.z = cam.nearClip()
	
	    return( -1 )
	elseIf( s1.z >= cam.nearClip() and s2.z < cam.nearClip() ) then
	    ' Second coordinate behind the camera, clip it
	    s2.x = s1.x + ((cam.nearClip() - s1.z) / (s2.z - s1.z)) * (s2.x - s1.x)
	    s2.y = s1.y + ((cam.nearClip() - s1.z) / (s2.z - s1.z)) * (s2.y - s1.y)
	    s2.z = cam.nearClip()
	
	    return( -1 )
	else
	    ' Both coordinates behind the camera, don't draw
	    return( 0 )
	end if
end function

So you see, if either one of the endpoints lie behind the near clipping plane, it gets clipped and assigned a coordinate that lies exactly on it. This way you avoid the problem that you're having.

- If a vertex is at zero or near zero, the projection shoots up to infinity. This not necessarily is a problem. I can just replace it with a very high number and seems to work fine. But I reason that if I do this, then I'm reaching a singularity and now what happens with negative Z?

This looks like a problem with the perspective routine to me. If/when you post it, we can address this issue.

- Lastly, I don't see where in the game plays the angle of view, that is, how can I make sure that, say, my screen width be set to a certain angle, say, 30 degrees or 45 degrees. Same way, I don't know where in the equation to put the distance from my eyes to the screen. I know these two variables have to be parameters of this thing, but I get lost on where.

Otherwise known as the field of view =D
This, again, have to do with the perspective projection. Have a look at this:
http://www.opengl-tutorial.org/es/begin ... -matrices/

Nevermind that the tutorial is for OpenGL. The math is the same. And, as an added bonus, if you learn all this, the only thing that you need to learn is GLSL to make a full blown 3D engine! ;)

Also, I've found the old 3D tutorial in which the paperplane demo is based. You can download it in my GitHub repo:
https://github.com/glasyalabolas/3D-basics

Sorry I can't be of any more help, I'm a little busy right now. See you later.

[dodicat]

Whatever type of rotater you use to turn your 3D vectors, one function will produce the perspective.
You must define an eyepoint.
In general.
All +ve z values are into the screen, -ve z values are out of the screen.

Here is a simple cube:
use arrow keys and z,x and space

Code: Select all

Screen 19

Type V3
    As Single x,y,z
    As Ulong col 'unused here
End Type

Type angle 'to pre calculate all the sines and cosines needed for 3D rotate
    As Single a(1 To 6)
    Declare Sub set(As V3)
End Type

Sub angle.set(a As V3)
This=Type({Sin(a.x),Sin(a.y),Sin(a.z),Cos(a.x),Cos(a.y),Cos(a.z)})
End Sub

Function Rotate(c As V3,p As V3,a As angle,scale As V3=Type(1,1,1)) As V3
    Dim As Single dx=p.x-c.x,dy=p.y-c.y,dz=p.z-c.z
    Return Type((scale.x)*((a.a(5)*a.a(6))*dx+(-a.a(4)*a.a(3)+a.a(1)*a.a(2)*a.a(6))*dy+(a.a(1)*a.a(3)+a.a(4)*a.a(2)*a.a(6))*dz)+c.x,_
    (scale.y)*((a.a(5)*a.a(3))*dx+(a.a(4)*a.a(6)+a.a(1)*a.a(2)*a.a(3))*dy+(-a.a(1)*a.a(6)+a.a(4)*a.a(2)*a.a(3))*dz)+c.y,_
    (scale.z)*((-a.a(2))*dx+(a.a(1)*a.a(5))*dy+(a.a(4)*a.a(5))*dz)+c.z,p.col)
End Function

Function perspective(p As V3,eyepoint As V3) As V3
    Dim As Single   w=1+(p.z/eyepoint.z)
    Return Type((p.x-eyepoint.x)/w+eyepoint.x,_
    (p.y-eyepoint.y)/w+eyepoint.y,_
    (p.z-eyepoint.z)/w+eyepoint.z,p.col)
End Function 

Sub joinpoints(p() As v3)   'to see a wireframe cube
    #define j(p1,p2) Line (p1.x,p1.y)-(p2.x,p2.y),4
    j(p(1),p(2)) 'front face
    j(p(2),p(3))
    j(p(3),p(4))
    j(p(4),p(1))
   
    j(p(5),p(6)) 'back face
    j(p(6),p(7))
    j(p(7),p(8))
    j(p(8),p(5))
    
    j(p(1),p(5)) 'front to back
    j(p(2),p(6))
    j(p(3),p(7))
    j(p(4),p(8))
End Sub

Dim As V3 R(1 To 8)       'to hold rotated points
Dim As V3 p(1 To 8)={ (300,200,-100), _  'FRONT top left
                      (500,200,-100), _  'FRONT top right
                      (500,400,-100), _  'FRONT bottom right 
                      (300,400,-100), _  'FRONT bottom left
                      (300,200,100), _   'The same except BACK
                      (500,200,100), _   
                      (500,400,100), _
                      (300,400,100) }
 Dim As String key 
 Dim As V3 ang,screencentre=Type(400,300,0)
 Dim As angle A
 Dim As V3 eyepoint=Type(400,300,500)
Do
    key=Inkey
    If key=Chr(255)+"K" Then ang.y+=.1     'left
    If key=Chr(255)+"M" Then ang.y-=.1     'right
    If key=Chr(255)+"P" Then ang.x+=.1     'down
    If key=Chr(255)+"H" Then ang.x-=.1     'up
    If key="z"          Then ang.z -=.1        
    If key="x"          Then ang.z +=.1
    If key=" "          Then ang=Type(0,0,0):key="" 'reset
    A.set(ang)
    For n As Long=1 To 8
        R(n)=rotate(screencentre,p(n),A)
        R(n)=Perspective(R(n),eyepoint)'<---------- HERE
    Next
    Screenlock
    Cls
    joinpoints(R())
    Screenunlock
    Sleep 1,1
        
    Loop Until key=Chr(27)
     

[paul doe]

Whatever type of rotater you use to turn your 3D vectors, one function will produce the perspective.

Precisely. The process to displaying something 3D into the screen can be roughly summarized as follows:

• Transform the points that belong to any particular object (called 'model' in the literature) to a global coordinate system (called the 'world' coordinates)
• Transform these points (which are now expressed in world coordinates) to the coordinate system of the camera (called the 'view' transformation)
• Transform these points (which are now expressed in the coordinate system of the camera, remember) with the perspective transform to the coordinate system of the screen (called the 'projection' transformation)

These series of transformations are commonly called 'model-view-projection' matrices in the literature about 3D. Here, dodicat refers to the 'camera' as the 'eyepoint', it's the same concept.
See how dodicat performs the perspective divide in the code:

Code: Select all

w=1+(p.z/eyepoint.z)

This avoids the issue you're having here:

- If a vertex is at zero or near zero, the projection shoots up to infinity. This not necessarily is a problem. I can just replace it with a very high number and seems to work fine. But I reason that if I do this, then I'm reaching a singularity and now what happens with negative Z?

[BasicCoder2]

@dodicat,
Added some code to circle the points using your way of coding which is unfamiliar to me and it worked.
Ultimately you need to fill visible polygons with a color or texture which I remember you doing by computing the distance between centroids.

Code: Select all

Screen 19

Type V3
    As Single x,y,z
    As Ulong col 'unused here
End Type

Type angle 'to pre calculate all the sines and cosines needed for 3D rotate
    As Single a(1 To 6)
    Declare Sub set(As V3)
End Type

Sub angle.set(a As V3)
    This=Type({Sin(a.x),Sin(a.y),Sin(a.z),Cos(a.x),Cos(a.y),Cos(a.z)})
End Sub

Function Rotate(c As V3,p As V3,a As angle,scale As V3=Type(1,1,1)) As V3
    Dim As Single dx=p.x-c.x,dy=p.y-c.y,dz=p.z-c.z
    Return Type((scale.x)*((a.a(5)*a.a(6))*dx+(-a.a(4)*a.a(3)+a.a(1)*a.a(2)*a.a(6))*dy+(a.a(1)*a.a(3)+a.a(4)*a.a(2)*a.a(6))*dz)+c.x,_
    (scale.y)*((a.a(5)*a.a(3))*dx+(a.a(4)*a.a(6)+a.a(1)*a.a(2)*a.a(3))*dy+(-a.a(1)*a.a(6)+a.a(4)*a.a(2)*a.a(3))*dz)+c.y,_
    (scale.z)*((-a.a(2))*dx+(a.a(1)*a.a(5))*dy+(a.a(4)*a.a(5))*dz)+c.z,p.col)
End Function

Function perspective(p As V3,eyepoint As V3) As V3
    Dim As Single   w=1+(p.z/eyepoint.z)
    Return Type((p.x-eyepoint.x)/w+eyepoint.x,_
    (p.y-eyepoint.y)/w+eyepoint.y,_
    (p.z-eyepoint.z)/w+eyepoint.z,p.col)
End Function 

Sub joinpoints(p() As v3)   'to see a wireframe cube
    #define j(p1,p2) Line (p1.x,p1.y)-(p2.x,p2.y),4
    j(p(1),p(2)) 'front face
    j(p(2),p(3))
    j(p(3),p(4))
    j(p(4),p(1))
   
    j(p(5),p(6)) 'back face
    j(p(6),p(7))
    j(p(7),p(8))
    j(p(8),p(5))
    
    j(p(1),p(5)) 'front to back
    j(p(2),p(6))
    j(p(3),p(7))
    j(p(4),p(8))
End Sub

sub drawPoints(p() AS v3)
    #define jj(p1) circle (p1.x,p1.y),4,15
    for i as integer = 1 to 8
        jj(p(i))
    next i
end sub

Dim As V3 R(1 To 8)       'to hold rotated points

Dim As V3 p(1 To 8)={ (300,200,-100), _  'FRONT top left
                      (500,200,-100), _  'FRONT top right
                      (500,400,-100), _  'FRONT bottom right 
                      (300,400,-100), _  'FRONT bottom left
                      (300,200,100), _   'The same except BACK
                      (500,200,100), _   
                      (500,400,100), _
                      (300,400,100) }
                      
Dim As String key
Dim As V3 ang,screencentre=Type(400,300,0)
Dim As angle A
Dim As V3 eyepoint=Type(400,300,500)
 
Do
    key=Inkey
    If key=Chr(255)+"K" Then ang.y+=.1     'left
    If key=Chr(255)+"M" Then ang.y-=.1     'right
    If key=Chr(255)+"P" Then ang.x+=.1     'down
    If key=Chr(255)+"H" Then ang.x-=.1     'up
    If key="z"          Then ang.z -=.1        
    If key="x"          Then ang.z +=.1
    If key=" "          Then ang=Type(0,0,0):key="" 'reset
    A.set(ang)
    For n As Long=1 To 8
        R(n)=rotate(screencentre,p(n),A)
        R(n)=Perspective(R(n),eyepoint)'<---------- HERE
    Next
    Screenlock
    Cls
    joinpoints(R())
    drawPoints(R())  ' <------------------ DRAW POINTS
    Screenunlock
    Sleep 1,1
        
Loop Until key=Chr(27)

[xlucas]

Thank you so much, guys!

w=1+(p.z/eyepoint.z)

Dodicat: What if your eyepoint Z were zero? You'd have a zero-divide on all perspective divisions. Then how come it works when it's not zero? This gets me confused.

Paul Doe: Now I have a lot to read, but I was able to understand the 3D clipping. I was doing something similar, but not quite. My code came out of my brain without me reading anything, so it will look completely different from the way it's supposed to be. I'll share it and I'll explain it a little. I will have to share a link to some data files too.

In my code, not only there are bugs, but also many things are not optimal at all and I know it, because I first wanted to make it work well before any optimisation. For example, I use all doubles, I don't caché the trigonometric functions, I use my own triangle-drawing subs that use FreeBasic Line statements only to draw horizontal lines, but are supposed to be translated to assembly once the whole thing works.

Code: Select all

#include "file.bi"

#define SCREEN_WIDTH 800
#define SCREEN_HEIGHT 600
#define HALFSW 400
#define HALFSH 300
#define MAP_WIDTH 30
#define MAP_HEIGHT 30

Type Vector3D Field = 1
	x As Double
	y As Double
	z As Double
End Type

Type Camera
	x As Double
	y As Double
	z As Double
	azimuth As Double
	pitch As Double
	bank As Double
End Type

Type Triangle Field = 1
	p(1 To 3) As UShort
	colour As ULong
	twosided As Boolean
	layer As UByte
	backlayer As UByte
	texture As UByte	'Transparent grid?
End Type

Type Segment Field = 1
	p(1 To 2) As UShort
	colour As ULong
	layer As UByte
	reserved As UByte
End Type

Type Element
	n As UShort		'Number of triangle/segment
	t As UByte		'Element type (triangle or segment)
End Type

Type TrackObject
	fvertex As UShort
	verteces As UShort
	ftriangle As UShort
	triangles As UShort
	fsegment As UShort
	segments As UShort
	layers As UByte
End Type

Type ObjectToBeDrawn
	x As Double
	y As Double
	z As Double
	dist As Double
	id As UShort
End Type


Global_Variables:
Dim Shared vpool(1 To 1000) As Vector3D, vpools As UShort
Dim Shared tpool(1 To 500) As Triangle, tpools As UShort
Dim Shared spool(1 To 500) As Segment, spools As UShort
Dim Shared layers As UByte
Dim Shared track_object(1 To 10) As TrackObject, track_objects As UShort
Dim Shared oblist(1 To 400) As ObjectToBeDrawn, oblists As UShort
Dim Shared vertex(1 To 200) As Vector3D, verteces As UShort
Dim Shared triangle(1 To 100) As Triangle, triangles As UShort
Dim Shared segment(1 To 50) As Segment, segments As UShort
Dim Shared e(1 To 1000) As Element, elements As UShort
Dim Shared theta As Double, phi As Double, distance As Double
Dim Shared DTS As Double = 500	'Proportional distance
Dim Shared DDTS As Double = 1	'Displacement distance
Dim Shared c As Camera, visibility As Byte = 7
Dim Shared map(0 To MAP_WIDTH - 1, 0 To MAP_HEIGHT - 1) As UByte


Rendering_Functions:
Sub LoadTrackObject (o As String)
	Dim f As Integer, i As Short
	Dim t As TrackObject
	
	If Not FileExists(o) Then Exit Sub
	
	track_objects += 1
	
	f = FreeFile
	Open o For Binary Access Read As f
	Get #f, 5, t.verteces
	Get #f, , t.segments
	Get #f, , t.triangles
	t.fvertex = vpools + 1 : vpools += t.verteces
	t.fsegment = spools + 1 : spools += t.segments
	t.ftriangle = tpools + 1 : tpools += t.triangles
	t.layers = 0
		
	For i = 0 To t.verteces - 1
		Get #f, , vpool(t.fvertex + i)
		vpool(t.fvertex + i).x /= 2
		vpool(t.fvertex + i).y /= 2
		vpool(t.fvertex + i).z /= 2
		vpool(t.fvertex + i).y += .5
	Next i
	For i = 0 To t.segments - 1
		Get #f, , spool(t.fsegment + i)
		If spool(t.fsegment + i).layer > t.layers Then t.layers = spool(t.fsegment + i).layer
		If spool(t.fsegment + i).layer = 0 Then spool(t.fsegment + i).layer = 1
	Next i
	For i = 0 To t.triangles - 1
		Get #f, , tpool(t.ftriangle + i)
		If tpool(t.ftriangle + i).layer > t.layers Then t.layers = tpool(t.ftriangle + i).layer
		If tpool(t.ftriangle + i).backlayer > t.layers Then t.layers = tpool(t.ftriangle + i).backlayer
		If tpool(t.ftriangle + i).layer = 0 Then tpool(t.ftriangle + i).layer = 1
		If tpool(t.ftriangle + i).backlayer = 0 Then tpool(t.ftriangle + i).backlayer = tpool(t.ftriangle + i).layer
	Next i
	
	track_object(track_objects) = t
	Close f
End Sub


Sub RotateX (angle As Double)
	Dim v As Vector3D
	
	For i As Short = 1 To verteces
		v = vertex(i)
		vertex(i).y = v.y * Cos(angle) - v.z * Sin(angle)
		vertex(i).z = v.y * Sin(angle) + v.z * Cos(angle)
	Next i
End Sub


Sub RotateY (angle As Double)
	Dim v As Vector3D
	
	For i As Short = 1 To verteces
		v = vertex(i)
		vertex(i).x = v.x * Cos(angle) + v.z * Sin(angle)
		vertex(i).z = -v.x * Sin(angle) + v.z * Cos(angle)
	Next i
End Sub


Sub RotateZ (angle As Double)
	Dim v As Vector3D
	
	For i As Short = 1 To verteces
		v = vertex(i)
		vertex(i).x = v.x * Cos(angle) + v.y * Sin(angle)
		vertex(i).y = -v.x * Sin(angle) + v.y * Cos(angle)
	Next i
End Sub


Sub SortTriangles
	Dim zt(1 To triangles + segments) As Double, min As Double, minv As Short
	Dim As Short i, j
	
	elements = triangles + segments
	For i = 1 To triangles
		zt(i) = vertex(triangle(i).p(1)).z + vertex(triangle(i).p(2)).z + vertex(triangle(i).p(3)).z
		e(i).n = i
		e(i).t = 0
	Next i
	For i = 1 to segments
		zt(i + triangles) = 1.5 * (vertex(segment(i).p(1)).z + vertex(segment(i).p(2)).z)
		e(i + triangles).n = i
		e(i + triangles).t = 1
	Next i
	
	For i = 1 To elements - 1
		min = zt(i) : minv = i
		For j = i To elements
			If zt(j) < min Then
				min = zt(j)
				minv = j
			End If
		Next j
		If minv <> i Then
			'~ If curtriangle = i Then
				'~ curtriangle = minv
			'~ ElseIf curtriangle = minv Then
				'~ curtriangle = i
			'~ End If
			'~ Swap triangle(i), triangle(minv)
			Swap e(i), e(minv)
			Swap zt(i), zt(minv)
		End If
	Next i
End Sub


Function TFront(t As Triangle) As Boolean
	Dim As Double r, r2
	
	'This works fine, but unless the operation is performed
	'AFTER perspective was applied, the result will look
	'awkward.
	
	r = vertex(t.p(1)).x * vertex(t.p(2)).y
	r += vertex(t.p(2)).x * vertex(t.p(3)).y
	r += vertex(t.p(3)).x * vertex(t.p(1)).y
	
	r2 = vertex(t.p(2)).x * vertex(t.p(1)).y
	r2 += vertex(t.p(3)).x * vertex(t.p(2)).y
	r2 += vertex(t.p(1)).x * vertex(t.p(3)).y
	
	Return r > r2
End Function


Sub ApplyPerspective
	Dim i As Short
	Dim z As Double
	
	For i = 1 to verteces
		z = -vertex(i).z
		If z < 0.0001 Then z = 0.0001
		vertex(i).x = DTS * vertex(i).x / z
		vertex(i).y = DTS * vertex(i).y / z
		If vertex(i).x > 1000000 Then vertex(i).x = 1000000
		If vertex(i).y > 1000000 Then vertex(i).y = 1000000
		If vertex(i).x < -1000000 Then vertex(i).x = -1000000
		If vertex(i).y < -1000000 Then vertex(i).y = -1000000
	Next i
End Sub


Sub drawtriangle(ByVal x1 As Short, ByVal y1 As Short, _
				ByVal x2 As Short, ByVal y2 As Short, _
				ByVal x3 As Short, ByVal y3 As Short, col As ULong)

	'STEPS TO FOLLOW:
	'Step 1: Sort point by Y
	'Step 2: Drop all triangles out of Y bounds
	'Step 3: Classify as top, bottom or mixed
	'Step 4: If mixed, split the triangle and call the sub twice and exit
	'Step 5: Obtain initial Y and X1 and X2 for first line, plus deltas
	'Step 6: Apply deltas till Y is onscreen
	'Step 7: Draw lines till triangle is complete or out of screen

	Dim currenty As Long
	Dim As Long deltaxi, deltaxf, currentxi, currentxf
	
	'Step 1: Sort point by Y
	If y1 > y2 Then Swap y1, y2 : Swap x1, x2
	If y2 > y3 Then Swap y2, y3 : Swap x2, x3
	If y1 > y2 Then Swap y1, y2 : Swap x1, x2
	
	'Step 2: Drop all triangles out of Y bounds
	If y3 < 0 Or y1 >= SCREEN_HEIGHT Then Exit Sub
	
	'Step 3: Classify as top, bottom or mixed
	If y1 = y2 AndAlso y2 = y3 Then
		'Just a horizontal line
		'... not drawing anything so far
	ElseIf y2 = y3 Then			'Top
		'Step 5: Obtain initial Y and X1 and X2 for first line, plus deltas
		If x2 > x3 Then Swap x2, x3 : Swap y2, y3	'Sort by X
		currenty = y1
		currentxi = 256 * x1 : currentxf = 256 * x1
		deltaxi = 256 * (x2 - x1) / (y2 - y1)	'Add some precision
		deltaxf = 256 * (x3 - x1) / (y3 - y1)
	ElseIf y1 = y2 Then		'Bottom
		'Step 5: Obtain initial Y and X1 and X2 for first line, plus deltas
		If x1 > x2 Then Swap x1, x2 : Swap y1, y2	'Sort by X
		currenty = y1
		currentxi = 256 * x1 : currentxf = 256 * x2
		deltaxi = 256 * (x3 - x1) / (y3 - y1)	'Add some precision
		deltaxf = 256 * (x3 - x2) / (y3 - y2)
	Else					'Mixed
		'Step 4: If mixed, split the triangle and call the sub twice and exit
		Dim otherx As Short
		
		otherx = (y2 - y1) * (x3 - x1) / (y3 - y1) + x1
		drawtriangle x1, y1, x2, y2, otherx, y2, col
		drawtriangle x2, y2, otherx, y2, x3, y3, col
		Exit Sub
	End If
	
	'Step 6: Apply deltas till Y is onscreen
	If currenty < 0 Then
		currentxi += Abs(currenty) * deltaxi
		currentxf += Abs(currenty) * deltaxf
		currenty = 0
	End If
	
	'Step 7: Draw lines till triangle is complete or out of screen
	Dim As Short tempxi, tempxf
	Do
		'Only draw if onscreen
		If currentxf >= 0 And currentxi / 256 < SCREEN_WIDTH Then
			'Clip the line
			If currentxi >= 0 Then tempxi = currentxi / 256 Else tempxi = 0
			If currentxf / 256 < SCREEN_WIDTH Then tempxf = currentxf / 256 Else tempxf = SCREEN_WIDTH - 1
			'Draw it
			Line (tempxi, currenty)-(tempxf, currenty), col
		End If
		
		'If triangle is done or we go offscreen, then exit
		If currenty >= y3 OrElse currenty >= SCREEN_HEIGHT - 1 Then Exit Do
	
		'Update coordinates
		currentxi += deltaxi
		currentxf += deltaxf
		currenty += 1
	Loop
End Sub


Sub drawtranstriangle(ByVal x1 As Short, ByVal y1 As Short, _
				ByVal x2 As Short, ByVal y2 As Short, _
				ByVal x3 As Short, ByVal y3 As Short, col As ULong)

	'STEPS TO FOLLOW:
	'Step 1: Sort point by Y
	'Step 2: Drop all triangles out of Y bounds
	'Step 3: Classify as top, bottom or mixed
	'Step 4: If mixed, split the triangle and call the sub twice and exit
	'Step 5: Obtain initial Y and X1 and X2 for first line, plus deltas
	'Step 6: Apply deltas till Y is onscreen
	'Step 7: Draw lines till triangle is complete or out of screen

	Dim currenty As Long
	Dim As Long deltaxi, deltaxf, currentxi, currentxf
	
	'Step 1: Sort point by Y
	If y1 > y2 Then Swap y1, y2 : Swap x1, x2
	If y2 > y3 Then Swap y2, y3 : Swap x2, x3
	If y1 > y2 Then Swap y1, y2 : Swap x1, x2
	
	'Step 2: Drop all triangles out of Y bounds
	If y3 < 0 Or y1 >= SCREEN_HEIGHT Then Exit Sub
	
	'Step 3: Classify as top, bottom or mixed
	If y1 = y2 AndAlso y2 = y3 Then
		'Just a horizontal line
		'... not drawing anything so far
	ElseIf y2 = y3 Then			'Top
		'Step 5: Obtain initial Y and X1 and X2 for first line, plus deltas
		If x2 > x3 Then Swap x2, x3 : Swap y2, y3	'Sort by X
		currenty = y1
		currentxi = 256 * x1 : currentxf = 256 * x1
		deltaxi = 256 * (x2 - x1) / (y2 - y1)	'Add some precision
		deltaxf = 256 * (x3 - x1) / (y3 - y1)
	ElseIf y1 = y2 Then		'Bottom
		'Step 5: Obtain initial Y and X1 and X2 for first line, plus deltas
		If x1 > x2 Then Swap x1, x2 : Swap y1, y2	'Sort by X
		currenty = y1
		currentxi = 256 * x1 : currentxf = 256 * x2
		deltaxi = 256 * (x3 - x1) / (y3 - y1)	'Add some precision
		deltaxf = 256 * (x3 - x2) / (y3 - y2)
	Else					'Mixed
		'Step 4: If mixed, split the triangle and call the sub twice and exit
		Dim otherx As Short
		
		otherx = (y2 - y1) * (x3 - x1) / (y3 - y1) + x1
		drawtranstriangle x1, y1, x2, y2, otherx, y2, col
		drawtranstriangle x2, y2, otherx, y2, x3, y3, col
		Exit Sub
	End If
	
	'Step 6: Apply deltas till Y is onscreen
	If currenty < 0 Then
		currentxi += Abs(currenty) * deltaxi
		currentxf += Abs(currenty) * deltaxf
		currenty = 0
	End If
	
	'Step 7: Draw lines till triangle is complete or out of screen
	Dim As Short tempxi, tempxf
	Do
		'Only draw if onscreen
		If currentxf >= 0 And currentxi / 256 < SCREEN_WIDTH Then
			'Clip the line
			If currentxi >= 0 Then tempxi = currentxi / 256 Else tempxi = 0
			If currentxf / 256 < SCREEN_WIDTH Then tempxf = currentxf / 256 Else tempxf = SCREEN_WIDTH - 1
			'Draw it
			If currenty And 1 Then
				If ((currenty ShR 1) XOr tempxi) And 1 Then
					Line (tempxi, currenty)-(tempxf, currenty), col, , &HAAAA
				Else
					Line (tempxi, currenty)-(tempxf, currenty), col, , &H5555
				End If
			Else
				Line (tempxi, currenty)-(tempxf, currenty), col
			End If
		End If
		
		'If triangle is done or we go offscreen, then exit
		If currenty >= y3 OrElse currenty >= SCREEN_HEIGHT - 1 Then Exit Do
	
		'Update coordinates
		currentxi += deltaxi
		currentxf += deltaxf
		currenty += 1
	Loop
End Sub


Sub DrawIt
	Dim i As Short, l As Byte
	Dim As Double x1, y1, x2, y2, x3, y3, z
	
	For l = 1 To layers
		For i = 1 To elements
			If e(i).t Then	'It's a segment
				If segment(e(i).n).layer = l Then
					x1 = vertex(segment(e(i).n).p(1)).x
					y1 = vertex(segment(e(i).n).p(1)).y
					x2 = vertex(segment(e(i).n).p(2)).x
					y2 = vertex(segment(e(i).n).p(2)).y
					Line (x1 + HALFSW, HALFSH - y1)-(x2 + HALFSW, HALFSH - y2), segment(e(i).n).colour
				End If
			Else			'It's a triangle
				Dim f As Boolean
					
				f = TFront(triangle(e(i).n))
				If ((f = True) And (triangle(e(i).n).layer = l)) OrElse ((f = False) And (triangle(e(i).n).backlayer = l)) Then
					If triangle(e(i).n).twosided OrElse f Then
						If triangle(e(i).n).p(1) > 0 And triangle(e(i).n).p(2) > 0 And triangle(e(i).n).p(3) > 0 Then
							x1 = vertex(triangle(e(i).n).p(1)).x
							y1 = vertex(triangle(e(i).n).p(1)).y
							x2 = vertex(triangle(e(i).n).p(2)).x
							y2 = vertex(triangle(e(i).n).p(2)).y
							x3 = vertex(triangle(e(i).n).p(3)).x
							y3 = vertex(triangle(e(i).n).p(3)).y
							
							If vertex(triangle(e(i).n).p(1)).z < -.5 _
								AndAlso vertex(triangle(e(i).n).p(2)).z < -.5 _
								AndAlso vertex(triangle(e(i).n).p(3)).z < -.5 Then
								
								If triangle(e(i).n).texture = 1 Then
									drawtranstriangle HALFSW + x1, HALFSH - y1, _
												HALFSW + x2, HALFSH - y2, _
												HALFSW + x3, HALFSH - y3, triangle(e(i).n).colour							
								Else
									drawtriangle HALFSW + x1, HALFSH - y1, _
												HALFSW + x2, HALFSH - y2, _
												HALFSW + x3, HALFSH - y3, triangle(e(i).n).colour
								End If							
							End If
						End If
					End If
				End If			
			End If
		Next i
	Next l
End Sub


Sub DrawHorizon
	If c.pitch < -0.8 Then	'All ground
		Line (0, 0)-(SCREEN_WIDTH - 1, SCREEN_HEIGHT - 1), RGB(0, 100, 0), BF
		Exit Sub
	End If
	
	'Paint sky
	Line (0, 0)-(SCREEN_WIDTH - 1, SCREEN_HEIGHT - 1), RGB(0, 200, 200), BF
	If c.pitch > 0.8 Then Exit Sub		'All sky

	'Create largest ground triangle necessary to cover the screen
	Dim p(1 To 3) As Vector3D
	
	p(1).x = -2 * SCREEN_WIDTH : p(2).x = -p(1).x
	p(1).y = .707 * SCREEN_WIDTH : p(2).y = p(1).y : p(3).y = p(1).y
	p(1).z = 0 : p(2).z = 0
	p(3).x = 0 : p(3).z = -4 * SCREEN_WIDTH
	
	For i As Short = 1 To 3
		Dim tempy As Double
		
		tempy = p(i).y * Cos(c.pitch) - p(i).z * Sin(c.pitch)
		p(i).z = -p(i).y * Sin(c.pitch) + p(i).z * Cos(c.pitch)
		p(i).y = tempy
	Next i
	
	For i As Short = 1 To 3
		Dim tempx As Double
		
		tempx = p(i).x * Cos(c.bank) - p(i).z * Sin(c.bank)
		p(i).z = p(i).x * Sin(c.bank) + p(i).z * Cos(c.bank)
		p(i).x = tempx
	Next i
	
	drawtriangle HALFSW + p(1).x, HALFSH - p(1).z, _
		HALFSW + p(2).x, HALFSH - p(2).z, _
		HALFSW + p(3).x, HALFSH - p(3).z, RGB(0, 100, 0)
End Sub


'Step 1 - Calculate and saturate minimum and maximum X and Y around
'         camera location with given visibility.
'Step 2 - Scan the rectangle and push objects being found, together
'         with their locations to a list.
'Step 3 - Calculate distance to each of the objects found (centre)
'Step 4 - Sort object list by distance.

'FOR EACH OBJECT IN THE LIST:
'Step 5 - Use azimuth to estimate if object is behind or otherwise
'         out of the viewport and if so, skip it.
'Step 6 - Load object verteces, triangles and segments into the working
'         arrays.
'Step 7 - Rotate object according to camera angles.
'Step 8 - Move object according to camera location.
'Step 9 - Apply perspective, effectively converting verteces to 2D
'Step 10 - Draw object
'Step 11 - Reset working variables

Sub Render
	Dim As Short x1, y1, x2, y2
	
	'Step 1: -------------------------------
	x1 = Int(c.x) - visibility
	If x1 < 0 Then x1 = 0
	x2 = Int(c.x) + visibility
	If x2 >= MAP_WIDTH Then x2 = MAP_WIDTH - 1
	y1 = Int(c.y) - visibility
	If y1 < 0 Then y1 = 0
	y2 = Int(c.y) + visibility
	If y2 >= MAP_HEIGHT Then y2 = MAP_HEIGHT - 1
	
	'Step 2: --------------------------------
	oblists = 0
	
	For y As Short = y1 To y2
		For x As Short = x1 To x2
			If map(x, y) Then
				oblists += 1
				oblist(oblists).x = x + .5
				oblist(oblists).y = y + .5
				oblist(oblists).z = .5
				oblist(oblists).id = map(x, y)
			End If
		Next x
	Next y
	
	'Step 3: ----------------------------------
	For i As Short = 1 To oblists
		oblist(i).dist = Abs(oblist(i).x - c.x) + Abs(oblist(i).y - c.y)
	Next i
	
	'Step 4: ----------------------------------
	For i As Short = 1 To oblists - 1
		Dim maxo As Short, maxd As Double
		
		maxd = 0
		For j As Short = i To oblists
			If oblist(j).dist > maxd Then
				maxd = oblist(j).dist
				maxo = j
			End If
		Next j
		
		If i <> maxo Then Swap oblist(i), oblist(maxo)
	Next i
	
	'THE REST =================================
	For i As Short = 1 To oblists
		'Step 5: --------------------------------
		Dim As Double rx, ry
		
		rx = oblist(i).x - c.x
		ry = oblist(i).y - c.y
		ry = rx * Sin(c.azimuth) + ry * Cos(c.azimuth)
		If ry >= 0 Then	'Should be drawn
			'Step 6: -----------------------------
			Dim j As Short
			verteces = track_object(oblist(i).id).verteces
			For j = 1 To verteces
				vertex(j) = vpool(track_object(oblist(i).id).fvertex + j - 1)
			Next j
			segments = track_object(oblist(i).id).segments
			For j = 1 To verteces
				segment(j) = spool(track_object(oblist(i).id).fsegment + j - 1)
			Next j
			triangles = track_object(oblist(i).id).triangles
			For j = 1 To triangles
				triangle(j) = tpool(track_object(oblist(i).id).ftriangle + j - 1)
			Next j
			layers = track_object(oblist(i).id).layers
			
			'SWAPPED STEPS 7 AND 8
			'Step 8: -------------------------------
			For j = 1 To verteces
				vertex(j).x -= oblist(i).x - c.x
				vertex(j).y -= oblist(i).z - c.z
				vertex(j).z -= oblist(i).y - c.y
			Next j
			
			'Step 7: -------------------------------
			RotateY -c.azimuth
			RotateX -c.pitch
			RotateZ -c.bank
			
			'Add the distance from the person to the screen
			For j = 1 To verteces
				vertex(j).z -= DDTS
			Next j
			
			'Step 9: -------------------------------
			ApplyPerspective
			
			'Step 10: -------------------------------
			layers = track_object(oblist(i).id).layers
			SortTriangles
			DrawIt
		End If
	Next i
End Sub


LoadTrackObject "rampa.g3d"
LoadTrackObject "s-road.g3d"
LoadTrackObject "edif.g3d"
LoadTrackObject "otrocoso.g3d"

ScreenRes SCREEN_WIDTH, SCREEN_HEIGHT, 32
visibility = 7
For i As Short = 0 To 29
	map(i, 2) = 1
	map(i, 8) = 2
	map(2, i) = 3
	map(8, i) = 4
	map(5, i) = 2
Next i
map(5, 5) = 2
map(5, 6) = 2
c.x = 5.5 : c.y = 5.5 : c.z = .25
c.azimuth = 0 : c.pitch = 0 : c.bank = 0

DDTS = 0

Dim akey As String, redraw As Boolean

redraw = True
Do
	If redraw Then
		CLS
		DrawHorizon
		Render
		redraw = False
	End If
	
	akey = InKey
	Select Case akey
		Case Chr(255, 77)
			c.azimuth -= .1
			redraw = True
		Case Chr(255, 75)
			c.azimuth += .1
			redraw = True
		Case Chr(255, 72)
			c.pitch -= .1
			redraw = True
		Case Chr(255, 80)
			c.pitch += .1
			redraw = True
		Case ","
			c.bank -= .1
			redraw = True
		Case "."
			c.bank += .1
			redraw = True
		Case "+", "="
			c.z -= .05
			redraw = True
		Case "-"
			c.z += .05
			redraw = True
		Case "q" : DTS /= 1.5 :	redraw = True
		Case "w" : DTS *= 1.5 : redraw = True
		Case "a" : DDTS -= .5 : redraw = True
		Case "s" : DDTS += .5 : redraw = True
		Case Chr(27) : Exit Do
	End Select
Loop

Data files necessary are here: https://mega.nz/#!gNQXUBIa!7ixJia3wUH8I ... Gzgvxe9NnU

- I am using two different right-handed coordinate systems. The 3D objects use one in which Z represents depth. The map itself uses another in which Z represents the height from the ground. I originally considered to use only one system, but I found it easy to make them work together and it turns out it's comfortable to have Z for depth in the graphic editor I made (not included) while it makes more sense to turn it into altitude at map-level. The camera can be moved up and down and rotated.

- The variable DTS is the scaling factor. Everything looks better when DTS is around 500. No idea why. Objects look a little two small, though. For instance, getting close to the ground, the road is still narrow. So I try increasing DTS and it does widen up, but now objects seem to lose depth, which makes sense, as I'm effectively performing a "zoom". It's not the same running toward the moon than zooming in at the moon. When you run, the moon remains small. When you zoom in, it gets enlarged in the same proportion as the buildings. This is what's happening and I don't know how to prevent it.

- The DDTS variable, I created for experimentation. It creates a displacement. Result is awful.

- Playing with DTS and DDTS craps up the horizon. This is telling me I should have included DTS somewhere in the DrawHorizon sub. That sub uses a trick to draw the horizon. It creates a large triangle and rotates it after setting it off centre by a certain degree.

- I'm having trouble drawing triangles that are too close to the camera even if they are fully in front of it. Not quite sure why that is. I've set a threshold to prevent artifacts, but that causes some triangles to not be drawn.

[paul doe]

In my code, not only there are bugs, but also many things are not optimal at all and I know it, because I first wanted to make it work well before any optimisation.

Which is a very good idea, don't worry about it for now.

Now I have a lot to read, but I was able to understand the 3D clipping.

Good. I updated my repo. Even more to read =D :https://github.com/glasyalabolas/3D-basics

My code came out of my brain without me reading anything, so it will look completely different from the way it's supposed to be. I'll share it and I'll explain it a little. I will have to share a link to some data files too.

Which is quite impressive =D
Can I suggest GitHub to share files? You can cram whatever you want in the suppository repository, even data files. So we can simply download the repo and have everything needed.

I will have a look at the code tonight, for I'm busy at the time being. We can address the problems then. See you later!

[xlucas]

Can I suggest GitHub to share files?

I've never used GitHub. I've seen many projects there, but I need to become more familiar with it. I'll read more about how it works. I've always worked alone, mostly, and I think GitHub is probably designed for team work, so never tried it. Also, for the same reason, I'm not used to reading other people's code and it's so hard for me to understand something written by somebody else, especially if it's OOP-based. I have to work on that, I know.

[paul doe]

Can I suggest GitHub to share files?

I've never used GitHub. I've seen many projects there, but I need to become more familiar with it. I'll read more about how it works. I've always worked alone, mostly, and I think GitHub is probably designed for team work, so never tried it. Also, for the same reason, I'm not used to reading other people's code and it's so hard for me to understand something written by somebody else, especially if it's OOP-based. I have to work on that, I know.

It's really easy to work with, don't worry. About OOP: viewtopic.php?f=15&t=26050. See the code of that demo and tell me if you can manage to understand it, for that's how I code. If not, then we will have a problem, indeed ;)
Nonetheless, I had a look at your code, and this is what I can tell you so far:

- I am using two different right-handed coordinate systems. The 3D objects use one in which Z represents depth. The map itself uses another in which Z represents the height from the ground. I originally considered to use only one system, but I found it easy to make them work together and it turns out it's comfortable to have Z for depth in the graphic editor I made (not included) while it makes more sense to turn it into altitude at map-level. The camera can be moved up and down and rotated.

You don't need to use two coordinate systems (this, in the end, will prove confusing and prone to errors, not to mention very cumbersome to transform from one coordinate system to another). If you're using a right handed coordinate system, it makes a lot more sense to have the Y component represent altitude. Nevermind that in the editor you treat it differently, you can change that at map loading time. Trust me, it will make it easier to work with, as almost all math that you'll found on the subject assumes that convention. Did you look at the paper plane demo? It uses a right handed coordinate system, with the Y component representing altitude and the Z component representing the facing direction (the direction the object is looking).

I also see that you're using Euler Angles to represent the camera orientation. Long story short: don't. While it's fairly easy for a beginner to understand and code, you'll be in for a lot of trouble, including Gimbal Lock (not to mention the awful lot of trigonometry you'll need for otherwise simple tasks, such as finding a normal). The most basic representations for doing 3D work are vectors and matrices. In the case of 3D graphics, normally you'd use 4x4 matrices and vectors. Any representation is fine, but I'd suggest column matrices (you'll discover why soon enough)

All in all, pretty cool =D
I'd have to study it a little more of course (I'll see if I can prepare something for you to use as a base, but you will have to give me a little more time, sorry), mostly because of your very strange conventions ;)

[dafhi]

imo this deserves to be pinned

The process to displaying something 3D into the screen can be roughly summarized as follows:

• Transform the points that belong to any particular object (called 'model' in the literature) to a global coordinate system (called the 'world' coordinates)
• Transform these points (which are now expressed in world coordinates) to the coordinate system of the camera (called the 'view' transformation)
• Transform these points (which are now expressed in the coordinate system of the camera, remember) with the perspective transform to the coordinate system of the screen (called the 'projection' transformation)

These series of transformations are commonly called 'model-view-projection' matrices in the literature about 3D.

[paul doe]

imo this deserves to be pinned

Why? This is pretty standard fare, I plucked it from the OpenGL documentation (added some little personal appreciations only)
=D

[dafhi]

pinned may be a little extreme but if i were to put together a 3d how-to ..

it's one of those things that can take a while to piece together mentally, yet is very simple

[dafhi]

D.J. Peters - the link was interesting - thanks for sharing!

[xlucas]

You don't need to use two coordinate systems[...]

I know. I did it that way because I'm working at the same time on the editor and the renderer and for each, a different system is convenient. Once I make a final thing, I would just transform the 3D models to the same system as that of the renderer. I prefer to use Z for up because that is how a "player" would feel the world (unless in space). One tends to imagine a map and maps usually go by X and Y, not X and Z. Minecraft uses X/Z maps and I don't like that much, ha, ha. Of course, if the renderer were for an X-Wing and not for a Stunts, then it'd make more sense to use Y for up. But yes, I do agree in the end it should be just one system.

I also see that you're using Euler Angles to represent the camera orientation

Nice to meet you, Euler! Ha, ha. Well, actually, I do know who Leonard Euler was. I just didn't know about Euler's Angles. I sat and thought how I should do this and well, I remember the nights playing with the telescope. I love Astronomy, but I'm not an astronomer. So that's how I came to set up that system. I also realised that using the system with azimuth first would mean that I can just ignore azimuth when solving for the horizon. Still, after reading about the gimbal lock, I know exactly what you mean. Since I recalculate from 0/0/0 degrees and execute all three rotations for each frame (with the purpose of not losing accuracy), I assumed there'd be no risk of locking, but to be honest, I haven't played much with 3D in the past, so I may be totally wrong.

I can understand your code. It only takes me longer to read than my own, of course... and your code is long, man... ha, ha. I've been playing with the paper plane. Really great. I'm kind of concerned on how I will trim my triangles. It's easier to do it with segments. I know my rotation is not the best, but so far, it works (I will of course keep on reading and will consider other systems). But truly, my real problem is with perspective and clipping.