Main Menu

Building a basic 3D Engine

Started by stevmjon, December 28, 2016, 03:43:19 AM

Previous topic - Next topic

stevmjon

howdy and happy easter

time to release a short demo, to test out my collision routines.

V0.8.7

i used the Seperated Axis Therom (SAT) collision detection, and made my own collision routine as the response to any collision (see above post).
i made a small demo world to test this routine, against different sized objects, and different slopes too. the reason the world size is small, is to keep frames playable, as manually calculating 3D textures slows down frames per second.

> goal is to reach the wood block on the other side of the trench....

i made it a challenge, so i hope there is no rage quitting. if you get there "well done".

  enjoy  stevmjon
It's easy to start a program, but harder to finish it...

I think that means i am getting old and get side tracked too easy.

kevin

#46
 Hey Steve

    Just waiting for the some compo's at revision 2019 and taking a look at the new demo.   Visually it's really looking nice and clean and the collisions seem to work well.


 
Quotei made a small demo world to test this routine, against different sized objects, and different slopes too. the reason the world size is small, is to keep frames playable, as manually calculating 3D textures slows down frames per second.

   Yeah the performance is slowing down in this version, so i've been having a look at the rendering there's some wasted calc's in the inner loops,  it might not seem like a big deal but any redundancy per scan line is then multiplied across the polygon and grows almost exponential as the scene gets more dense.   Imagine something as simple as an extra subtraction on a 100 lines high polygon, well this single subtraction is chewing through at least 25 cpu cycles to execute from the PB vm.    Put a scene full of only a few hundred faces and that's a lot of redundancy for one operation.    


   In other places the convenience of an array is just not worth it, for example it's better to grab the matrix as local variables that apply those to all verts in the like than read a 2d array 12 times per vertex.   Reading an array probably costs a hundred or more cpu cycles.   


PlayBASIC Code: [Select]
Function calc_matrix_4x4(array().tVertex2 , w)

; general matrix:
; NOTE: a-i = vectors _ l-n = perspective _ p-r = transform _ s = scaler
; x y z w
; [a, b, c, p]
  • [x~] : (ax + by + cz + p)
    ; [d, e, f, q] [y] = [y~] : (dx + ey + fz + q)
    ; [g, h, i, r] [z] [z~] : (gx + hy + iz + r)
    ; [l, m, n, s] [1] [w~] : (lx + my + nz + s)

    ; x' = (ax + by + cz + p) / (lx + my + nz + s)
    ; y' = (dx + ey + fz + q) / (lx + my + nz + s)
    ; z' = (gx + hy + iz + r) / (lx + my + nz + s)
    ; w = 1 (lx + my + nz + s) / (lx + my + nz + s)
    ; NOTE: w = 0 or 1 or z _ (depending on use needed)

    ;--- get points coordinates then calc by matrix ---
    max1=GetArrayElements(array(),1) ; points array()
    ;;max2=GetArrayElements(array2(),1) ; obj_data()
    Index=FindArrayCell(Array(),0,1,Max1,0)
    if Index>0

    m00#=m#(0,0)
    m01#=m#(0,1)
    m02#=m#(0,2)
    m03#=m#(0,3)

    m10#=m#(1,0)
    m11#=m#(1,1)
    m12#=m#(1,2)
    m13#=m#(1,3)

    m20#=m#(2,0)
    m21#=m#(2,1)
    m22#=m#(2,2)
    m23#=m#(2,3)

    m30#=m#(3,0)
    m31#=m#(3,1)
    m32#=m#(3,2)
    m33#=m#(3,3)


    For lp=0 To Index-1
    ;If array(lp)= 0 Then ExitFor lp ; if find empty slot exit
    id=array(lp).id
    If id = 0 Then ExitFor lp ; exit if no data _ id=0

    x# = array(lp).x# ; input x
    y# = array(lp).y# ; input y
    z# = array(lp).z# ; input z

    ;--- first calc each row from matrix ---
    xm#=m00#*x# + m01#*y# + m02#*z# + m03#;*w ; calc x
    ym#=m10#*x# + m11#*y# + m12#*z# + m13#;*w ; calc y
    zm#=m20#*x# + m21#*y# + m22#*z# + m23#;*w ; calc z
    wm#=m30#*x# + m31#*y# + m32#*z# + m33#;*w ; calc w : (this gets divided below into xm, ym, zm)
    ; NOTE: in perspective matrix need to use w = input z _ (this ensures z = -1 to +1 in canonical cube)

    If w=1
    If wm#<0.001 ; this check makes sure points can't be divided by zero
    wm#=0.001
    EndIf
    divx#=xm#/wm# : divy#=ym#/wm# : divz#=zm#/wm# ; divide by w
    array(lp).x# = divx# ; x / w
    array(lp).y# = divy# ; y / w
    array(lp).z# = divz# ; z / w
    EndIf

    If w=0
    ; in case w = 0 , keep x, y, z values
    array(lp).x# = xm# ; keep x value
    array(lp).y# = ym# ; keep y value
    array(lp).z# = zm# ; keep z value
    EndIf

    Next lp
    endif
    EndFunction




 

stevmjon

thanks for the tips kev. i have applied what you showed in the code snippet above. already gained a few frames.

the main part that slows the game down is the 3D texture routine (see Draw.pba). i have used as many variables here as i can to break down longer calcs into smaller ones. i even put in TextureStripH into the interperlate polygon line routine, broken into 64 pixel lengths to gain speed. before i added this the game ran much slower.
if you look at the commented out sections, you can see i have done a lot of experimenting in the interperlate routine.

as you say above, maybe i can optimise this still further, by eliminating some calculations, if i can re-use values instead of calc new ones maybe?

i am glad you like this demo, and the collisions are working fine.

i clicked the revision party link in above post, and i have been listening to the music all afternoon while coding. relaxing.

   stevmjon
It's easy to start a program, but harder to finish it...

I think that means i am getting old and get side tracked too easy.

kevin

#48
 Steve.

  Here's my tweak of V087  of your 3d engine.   Long story short most of the overhead was in legacy locking code from some other variation of the draw routine..  I tweak the rendering loop so it's a bit simpler.  These does seem like a good case for a render strip that remembers the last cord / U/V and you only supply the next along this row.



Video:

 





 Download:

kevin

 Made a video gallery of this ..  fantastic progress




stevmjon

thanks for the tips kev. i got a good speed boost.

* start game and don't move player *
> fps = 22    (v0.8.7)
> fps = 35    (v0.8.8 - modified draw routine using kev's tips)

it seemed the biggest speed boost was from removing GetImagePtr(0) command. as you said in the video that this reads from the video card = slow.
i had this command read for every polygon that gets drawn. i didn't realize i did it this way. i wasn't even using this command in the later versions.

also in the videos you noticed i used the artist render method, so all visible polygons get drawn, even the ones behind other polygons that aren't visible.  i left it this way, because i was using the image_EX trick you told me about. so i stopped using the Z buffer array method i used in earlier versions that saved the z pos data in an array that was checked before the polygon scanline got drawn. i was using a rgb array and z buffer array, and drew the screen from the rgb array data.

i should implement this back in again, maybe by using only the z buffer array, and checking this before i draw the polygon scanline to the image_EX ?

   thanks agin for the tips,  stevmjon
It's easy to start a program, but harder to finish it...

I think that means i am getting old and get side tracked too easy.

kevin

#51
 Steve.

Quote
 it seemed the biggest speed boost was from removing GetImagePtr(0) command. as you said in the video that this reads from the video card = slow.
i had this command read for every polygon that gets drawn. i didn't realize i did it this way. i wasn't even using this command in the later versions.

  Yeah it's just a by product of the older methods all hidden within the routine,  hence it's good idea to refactor those things from time to time.   I often just make a new source from the old one (attach a date or version number) so there's like a builtin history of the major changes even if the older source file is no longer in use (not included) it's still within the project if i screw something up..  Which happens!   I Only went looking due to how much time it was taking, which didn't add up.

 
Quote
   i should implement this back in again, maybe by using only the z buffer array, and checking this before i draw the polygon scanline to the image_EX ?

   It seems doable, but the timing (on my machine) is showing a 1/3 of the work is rotation/culling/etc remainder is rendering.  It's just the proportions really, the bigger the screen resolution, the more cycles rendering is going to chew through.   You might win back from speed from using some pre-computed mipmaps of textures.   These are just versions of the texture that 50% of the source size.  So when  the object is proceded, it uses distance from the viewer (z will do) to work out what resolution of the texture to use.   This can have two sided behind, by smoothing out some 'noise' of distance objects and wins back some performance as smaller texture (in powers of 2) are more cache friendly so the render get less cache hits.. Whicih just means on CPUS that can't store the entire textyure on the highest level of cache,  they're constantly fetching chunks from lower levels or even directly from memory..  


  Create mip Maps


  Here's version little zoom demo cut'n paste together. The idea is to only use the high quality texture near the camera and the texture is a power of 2 size it's easier for the render to scale.    Here i've got some logic to sub in the texture detail, but i'd just make this a table...  anyway it can be really beneficially 


 
PlayBASIC Code: [Select]
 openscreen 1280,840,32,1

; Include the Dialogs library in this program
#Include "PBDialogs2"


; Title Of the Dialog
Filename$="Some Cool FIle.txt"
Filter$ ="(*.Images)|*.JPG;*.bmp;*.PNG;*tga" ; Mixture of image files
; Call the dialog
File$=OpenFileDialog("Load Image",Filename$,Filter$)

if fileexist(file$)


loadimage file$,1,8
scaleimage 1,512,512,1


Cls 255

Max=4

Dim MipMaps(Max)
Dim Scaled(Max)
MipMaps(1)=1
Scaled(1)=1





ThisIMage=1
For lp=2 to Max
; Make the mipmap from the Last image
ThisImage=CreateMipMap(ThisImage)
MipMaps(lp)=ThisImage

; make the scaled version (scaling from the original image)
Width =GetImageWidth(thisImage)
Height =GetImageHeight(thisImage)

ScaledIMage=getFreeimage()
CopyImage 1,ScaledIMage
Scaleimage ScaledImage,Width,height,1
Scaled(lp)=Scaledimage


next


; Draw the mip mapped + scaled versions of the images

Xpos=100
For lp=1 to Max
img=MipMaps(lp)
drawimage Img,Xpos,20,false

img=Scaled(lp)
drawimage Img,Xpos,300,false


Xpos=Xpos+getImageWIdth(img)+16
next
else
print "File Not Found"+File$

endif

sync
waitkey
waitnokey


size=512
ProjectionX#=400
ProjectionY#=400

; objects Width and Height and depth in the scene
ObjectWidth=size
ObjectHeight=size
ObjectDepth=3000

SceneMaxZ =5000

img=MipMaps(1)


; use a spritge to represent this object on screen
Spr=NewSprite(0,0,img)
SpriteDrawMode Spr,2
AutoCenterSpriteHandle spr,true

Do
; Clear the screen
Cls

; project the obejcts screenwidth and height at this depth
ScreenWidth# =(ObjectWidth*ProjectionX#)/ObjectDepth
ScreenHeight# =(ObjectHeight*ProjectionY#)/ObjectDepth


// only use the hires texture when really close to camera
if Objectdepth<500
depth=1
// use 50% version
elseif Objectdepth<1500
depth=2

// use 25% versions
elseif Objectdepth<2500
depth=3

elseif Objectdepth<10000
depth=4
endif

img=mipmaps(depth)

ScaleX#=ScreenWidth#/GetImageWidth(img)
ScaleY#=ScreenHeight#/GetImageHeight(img)
spriteimage Spr,Img
positionsprite spr,GetScreenWidth()/2,GetScreenHeight()/2
ScaleSpriteXY spr,scaleX#,scaley#

// hold space to tint
if Spacekey()
SpriteTint Spr, rgbdepthcue($ffffff,0,Objectdepth,500,SceneMaxZ)
else
SpriteTint Spr, -1
endif
drawallsprites

ObjectDepth=wrapvalue(ObjectDepth-10,200,SceneMaxZ)
print "Mip Map Level:"+str$(depth)
print " Image:"+str$(img)
print " Image Width:"+str$(getimagewidth(img))
print " Image Height:"+str$(getimagewidth(img))


Sync
loop

end





Login required to view complete source code



kevin

 Steve,

    One of the old ideas for strip commands was to have auto step form, which fits those situation where you need to draw a series of connected strips .   

     
    This means you'd set the initial starting position, the feed it the target coords.  When it's draws from the last saved coord to the one supplied


    So crude mod of the render loop (original)
PlayBASIC Code: [Select]
         // screen cords of x1->x2
x1 = interpl
x2 = x1+64

pixelu = int(a1#/c1#) * $10000
pixelv = int(a2#/c1#) * $10000


// process chunks from 2 onwards to Chunks
For lps=1 To chunks


t# = (lps*64)/distance#
t2# = 1-t#
;--- 3D texel u & v ---
topu# = t2#*a1# + t#*b1#
bottu# = t2#*c1# + t#*d1#
destU# = topu# / bottu# ; 3D U (dest texel)

topv# = t2#*a2# + t#*b2#
// buttv# is the same as bottu#
;bottv# = t2#*c1# + t#*d1#
destV# = topv# / bottU# ; 3D V (dest texel)


destU = destU#
destU*= $10000
destV = destV#
destV*= $10000

TextureStripH image,x1,pixelu,pixelv,x2,destu,destv,scany


pixelu=destu
pixelv=destv

x1=x2
x2+=64

Next lps






       Could become

PlayBASIC Code: [Select]
         // screen cords of x1->x2
x1 = interpl
x2 = x1+64

pixelu = int(a1#/c1#) * $10000
pixelv = int(a2#/c1#) * $10000

// Call a function to seed the texture cords ...

StartTextureStrip X1, ScanY , PixelU,PixelV

// process chunks from 2 onwards to Chunks
For lps=1 To chunks


t# = (lps*64)/distance#
t2# = 1-t#
;--- 3D texel u & v ---
topu# = t2#*a1# + t#*b1#
bottu# = t2#*c1# + t#*d1#
destU# = topu# / bottu# ; 3D U (dest texel)

topv# = t2#*a2# + t#*b2#
// buttv# is the same as bottu#
;bottv# = t2#*c1# + t#*d1#
destV# = topv# / bottU# ; 3D V (dest texel)


destU = destU#
destU*= $10000
destV = destV#
destV*= $10000

/// this would draw from the last point to the one provided next
RenderTextureStrip image,x2,destu,destv

x2+=64

Next lps






    So the cache version drawn from last save point to the new supplied,  then it copies the new cords to the cords,  that saves a bunch of VM lifting in such and inner loop

     The command names could be anything, and it allows for those functions to have additional feature patched into them. 




stevmjon

are you thinking of a new command kev?  RenderTextureStrip or something.

what would be great is a command that renders the whole polygon scanline, from poly edge to poly edge, using same as TextureStripH , but has the z value added to it, so it can interperlate non-linear (perspective correct). that will save having to break it down to multiple draws across the polygon scanline.

It's easy to start a program, but harder to finish it...

I think that means i am getting old and get side tracked too easy.

kevin


 
Quoteare you thinking of a new command kev?  RenderTextureStrip or something.
 

   always,  since the texture strip functions are drawing strips then it really should cache the last point itself, so we're just feeding it the next unknown point since the last is known .   This takes the need to do 'simple' operations in the VM, even if it's only removing a few assignments per loop.   

   On the opt'ing PB back end to-do list,  is some ideas for detection & implemetation of some common operators into packed opcodes.  It's a blurry line tho as too many can make it slower..   


Quote
what would be great is a command that renders the whole polygon scanline, from poly edge to poly edge, using same as TextureStripH , but has the z value added to it, so it can interperlate non-linear (perspective correct). that will save having to break it down to multiple draws across the polygon scanline.

   Yeah,  but You could do this yourself with PlayBASIC2dLL :) 


stevmjon

V0.9  :  TESTING MIPMAPPING

i thought i would re-write the 3D Engine to make it smaller, and easier to understand by changing comments too. this uses, for now, 2D polygons.

i want to test MipMaps. in the demo i have got several textures that can be changed in game, and also the mipmap distance can be changed in game. seems every 4 meters from camera is a good average, but... i am not sure how to go about calculating when to change to the lower texture. i have every 'set distance' from the camera by default, just to see what is looks like. the texture gets darker with each smaller sampled texture, to make it easier to see on screen.

* i assume there is a calc where you would measure the width/height of the texture in screen coordinates then select the mipmap texture size from this calculation???

thought i would post this for fun, and get any input.
i am thinking of maybe using shapes like polygons, and make a 3D world set up like this. that way no mipmaps needed, or textured polygons. will run faster too. could make 3D objects using software with colored polygons only and load them in.

   stevmjon
It's easy to start a program, but harder to finish it...

I think that means i am getting old and get side tracked too easy.

kevin


  looks cool but  is there an escape key ?

stevmjon

is this reference for a game this reminds you of?
It's easy to start a program, but harder to finish it...

I think that means i am getting old and get side tracked too easy.

kevin

nah, I have to CTRL-ALT-DELETE IT

kevin

#59
 
 I mocked this up for you tonight,   It's a generic version of an object frame work.  So there's one main array of objects and each object has it's own dynamically created vertex / face data etc etc (and all other properties that you need with in it.

 The only tricky thing i guess is that is uses dynamically created array handles,  which you can do by grabbing the return value from the function / psub call that returns an array(), the value coming out of it is the handle.    So we don't need arrays for each object we make.  etc



PlayBASIC Code: [Select]
;===============================================================================
;=== types =====================================================================
;===============================================================================

;--- the coordinates in 3D ---
Type tVertex1
x# , y# , z#
EndType

;--- the coordinates in 3D plus the objects unique id no. ---
Type tVertex2
x# , y# , z#
id ; each object has a unique id number
typ ; the type of object it is (cube, ground etc)
w#
EndType

;--- texture UV ---
Type tUV1
u# , v# ; location in texture image for polygon
;;image
EndType

Type tUV2
x# , y# , z#
u# , v# ; location in texture image for polygon
image
status
w#
EndType

;--- polygon points vertex & UV ---
Type tVertexUV
x# , y# , z#
id ; each object has a unique id number
vertex , vertmax ; vertex number , max vertices
u# , v#
image
w#
typ ; obj type (added for image set)
EndType




//-------------------------------------------------------------------
//-------------------------------------------------------------------
//-------------------------------------------------------------------
//-------------------------------------------------------------------
//-------------------------------------------------------------------


TYPE t3D_OBJECT
Name$ // Name of the Object

Position as tVertex1
Scale as tVertex1


// the Array Buffers this ojbect is using..
// so we don't need globally declared arrays, rather
// we create them dynamically and them within the object
VERTEX_ArrayHandle
FACE_ArrayHANDLE
UV_ArrayHANDLE
EndType

Dim Objects(10000) as t3D_Object




//-------------------------------------------------------------------
//-------------------------------------------------------------------


// Spawn a bunch of cubes

for lp =0 to 20

index =newCube()

// Set this object position
PositionObject index,Rnd(1000),Rnd(1000),Rnd(1000)

// sedt this objects scale
ScaleObject index,Rnd#(100),Rnd(100),Rnd(100)

next
Sync
waitkey


end



//-------------------------------------------------------------------
//-------------------------------------------------------------------
//-------------------------------------------------------------------
//-------------------------------------------------------------------
//-------------------------------------------------------------------
//-------------------------------------------------------------------

Function NewCube()

// Create blank object with space forr 8 verts and 6 faces
index=_Init_Blank_3D_Object(8,6)
if index

// Set the vertex array, so we can just dump to it like a stack
_PRIVATE_SET_VERTEX_ARRAY( Objects(Index).Vertex_ArrayHANDLE )

// New we can dump to this objects vertex array,
// without referencing it directly
_PRIVATE_ADD_VERTEX( -1, 1,-1 ) ; top left front _ 0
_PRIVATE_ADD_VERTEX( -1, 1, 1 ) ; top left back _ 1
_PRIVATE_ADD_VERTEX( 1, 1, 1 ) ; top right back _ 2
_PRIVATE_ADD_VERTEX( 1, 1,-1 ) ; top right front _ 3

_PRIVATE_ADD_VERTEX( -1,-1,-1 ) ; bott left front _ 4
_PRIVATE_ADD_VERTEX( -1,-1, 1 ) ; bott left back _ 5
_PRIVATE_ADD_VERTEX( 1,-1, 1 ) ; bott right back _ 6
_PRIVATE_ADD_VERTEX( 1,-1,-1 ) ; bott right front _ 7

// Set up faces
_PRIVATE_SET_FACE_ARRAY( Objects(Index).FACE_ArrayHANDLE )
_PRIVATE_ADD_QUAD(0,3,7,4) ; front polygon face
_PRIVATE_ADD_QUAD(2,1,5,6) ; back polygon face
_PRIVATE_ADD_QUAD(1,0,4,5) ; left polygon face
_PRIVATE_ADD_QUAD(3,2,6,7) ; right polygon face
_PRIVATE_ADD_QUAD(0,1,2,3) ; top polygon face
_PRIVATE_ADD_QUAD(4,7,6,5) ; bottom polygon face


endif
EndFunction Index





Function PositionObject(index,X#,Y#,Z#)
if GetObjectStatus(index)
Objects(index).Position.x=x#
Objects(index).Position.y=y#
Objects(index).Position.z=z#
endif
Login required to view complete source code





    Example #2


     This version includes a simple display render function so you can visualize it.  There's no camera, but the objects all randomly move left/right so to show it's running.  SPACE / Mouse button to quit


PlayBASIC Code: [Select]
; PROJECT : 3D Object Structure Example For Steve
; AUTHOR :
; CREATED : 2/10/2021
; EDITED : 2/10/2021
; ---------------------------------------------------------------------

;===============================================================================
;=== types =====================================================================
;===============================================================================

;--- the coordinates in 3D ---
Type tVertex1
x# , y# , z#
EndType

;--- the coordinates in 3D plus the objects unique id no. ---
Type tVertex2
x# , y# , z#
id ; each object has a unique id number
typ ; the type of object it is (cube, ground etc)
w#
EndType

;--- texture UV ---
Type tUV1
u# , v# ; location in texture image for polygon
;;image
EndType

Type tUV2
x# , y# , z#
u# , v# ; location in texture image for polygon
image
status
w#
EndType

;--- polygon points vertex & UV ---
Type tVertexUV
x# , y# , z#
id ; each object has a unique id number
vertex , vertmax ; vertex number , max vertices
u# , v#
image
w#
typ ; obj type (added for image set)
EndType




//-------------------------------------------------------------------
//-------------------------------------------------------------------
//-------------------------------------------------------------------
//-------------------------------------------------------------------
//-------------------------------------------------------------------


TYPE t3D_OBJECT
Name$ // Name of the Object

Position as tVertex1
Scale as tVertex1

// the Array Buffers this ojbect is using..
// so we don't need globally declared arrays, rather
// we create them dynamically and them within the object
VERTEX_ArrayHandle
FACE_ArrayHANDLE
UV_ArrayHANDLE
EndType

Dim Objects(10000) as t3D_Object




//-------------------------------------------------------------------
//-------------------------------------------------------------------


// Spawn a bunch of cubes

for lp =0 to 20

index =newCube()

// Set this object position
PositionObject index,Rndrange(-1000,1000),Rndrange(-1000,1000),500+Rnd(1000)

// set this objects scale
ScaleObject index,Rnd(100),Rnd(100),Rnd(100)


next



Do
cls

movecount--
if movecount<0
Dim Move as tVertex1
move= new tVertex1
move.x = rndrange(-10,10)
movecount=rndrange(10,100)
endif


for Index=1 to 1000
if GetObjectStatus(index)
moveobject Index,move.x,move.y,move.z
renderobject Index
endif
next

sync

Loop Spacekey()=true or mousebutton()=1

end

//-------------------------------------------------------------------
//-------------------------------------------------------------------
//-------------------------------------------------------------------
//-------------------------------------------------------------------
//-------------------------------------------------------------------
//-------------------------------------------------------------------

Function NewCube()

// Create blank object with space forr 8 verts and 6 faces
index=_Init_Blank_3D_Object(8,6)
if index

// Set the vertex array, so we can just dump to it like a stack
_PRIVATE_SET_VERTEX_ARRAY( Objects(Index).Vertex_ArrayHANDLE )

// New we can dump to this objects vertex array,
// without referencing it directly
_PRIVATE_ADD_VERTEX( -1, 1,-1 ) ; top left front _ 0
_PRIVATE_ADD_VERTEX( -1, 1, 1 ) ; top left back _ 1
_PRIVATE_ADD_VERTEX( 1, 1, 1 ) ; top right back _ 2
_PRIVATE_ADD_VERTEX( 1, 1,-1 ) ; top right front _ 3

_PRIVATE_ADD_VERTEX( -1,-1,-1 ) ; bott left front _ 4
_PRIVATE_ADD_VERTEX( -1,-1, 1 ) ; bott left back _ 5
Login required to view complete source code