Building a basic 3D Engine

[stevmjon]

hello,

it's my turn for a basic 3D Engine.
i have spent ages working out the theory of 3D, then working out all the mathmatics needed.
i am pleased to have a small demo, that works, and has polygon culling.

for the moment only polygons outside the camera view frustum are culled, and also polygons that have any points outside the view frustum are not drawn. so polygons close the the edge of the screen will disappear. this is so i know the routine works, and i can then add polygon clipping to these edge ones later.

i am excited to grow this, and i will post further versions as i add more features.

   happy holidays,  stevmjon

Latest Build V0.8.7 in Reply#45  (page 4)

[kevin]

 Hi Steve,  

   Looking good.  One tip that I would seriously encourage you to take would be to use typed pointers rather than 2D arrays.   It seems logical to use a 2d array for a vertex list for example, but vertex won't actually be stored in emory side by side.  Which can be costly, as CPU's don't like fetching memory randomly.  They rather it that memory be accessed as close as possible.  

   You can use a 1D array (actually it could be any layout, as you'd only be using at as a memory buffer, not an array)  as a cache basically and read/write fields via pointers.   Which is quicker than array access and if you convert to machine code, you'll see a massive performance boast.

PlayBASIC Code: [Select]

      Count=10

      Type tVertex
               x#,y#,Z#
      EndType


      ; Make the array bigg enough that is never needs to resized
      Dim VertBuffer#(Count * (Sizeof(tVertex)/4) )

      ;  Pointer to use to look at read/write vertex structures
      Dim P as tVertex Pointer



      ; get the pointer to vertex 0 
      P = GetArrayPtr(VertBuffer#(),true)
      For lp = 0 to count
      
            P.X = lp
            P.Y = 1000+lp
            P.Z = 2000+lp
      
            ; move pointer to the next vertex
            P += Sizeof(tVertex)
      next



      ; get the pointer to vertex 0 
      P = GetArrayPtr(VertBuffer#(),true)
      For lp = 0 to count
      
            print str$(lp)+"  "+str$(P.X)+","+str$(P.y)+","+str$(P.Z)
      
            ; move pointer to the next vertex
            P += Sizeof(tVertex)
      next


sync
waitkey

[kevin]

  Any progress ?

  In this version we're using a static array and indexing the X,Y,Z fields of the vertex.  It's an emulation of the previous code does, onlu difference is the fields are accessed through and array, rather than named offset such as X,Y,Z in the type structure.   
 

PlayBASIC Code: [Select]

      Count=10

      Type tVertex
               Fields#(3)
      EndType


      ; Make the array bigg enough that is never needs to be resized
      Dim VertBuffer#(Count * (Sizeof(tVertex)/4) )

      ;  Pointer to use,  to read/write vertex structures
      Dim P as tVertex Pointer



      ; get the pointer to vertex 0, which is element 0 in the array
      P = GetArrayPtr(VertBuffer#(),true)
      For lp = 0 to count
      
            P.Fields#(0) = lp
            P.Fields#(1) = 1000+lp
            P.Fields#(2) = 2000+lp
      
            ; move pointer to the next vertex
            P += Sizeof(tVertex)
      next



      ; get the pointer to vertex 0, which is element 0 in the array
      P = GetArrayPtr(VertBuffer#(),true)
      For lp = 0 to count
      
            print str$(lp)+"  "+str$(P.Fields#(0))+","+str$(P.Fields#(1))+","+str$(P.Fields#(2))
      
            ; move pointer to the next vertex
            P += Sizeof(tVertex)
      next


sync
waitkey

[stevmjon]

hello

another update to version v0.2
this version adds polygon face culling. this means any polygons that are facing away from the camera are culled.

next i will work on zbuffer polygon culling. this means any polygons in the background that are covered by foreground polygons (so not seen) will be culled.
there are a few ways to go about this, so i will need to experiment.

> this version doesn't contain types yet, i am currently going about this.
> can passing array types into a function be the same as passing a regular array into a function?
> i can only get variable pointers to point at the array in the function call.

example:
stuff(type_array(n).vertex)

function stuff(me as vertex pointer)
   ; this only points to the array element n
   ; i need to bring in other data like the array element maximum so i can make a loop in here etc. ???
endfunction

i guess pointing to a type array is different from pointing to a normal array.
i shall keep working on it.

  stevmjon

[kevin]

this version adds polygon face culling. this means any polygons that are facing away from the camera are culled.

  Cool. Looking really good!

   It's worth noting that you can save calculation work by linking / grouping faces within your object structure/meshs.    Imagine a cube with 12 triangle faces.  If the first tri is facing away, then so is it's bother.   Cubes have a lots of little opt's like you can compute the direction one a side is facing, then this tells you if the other face is visible or not also.   No big deal in a scene with a few cubes, but can really make the differences in scenes with lots of them.

next i will work on zbuffer polygon culling. this means any polygons in the background that are covered by foreground polygons (so not seen) will be culled. there are a few ways to go about this, so i will need to experiment.

   The standard solution this day and age is per pixel Z buffer, but that's not really doable here without using PB2DLL and writing your polygon filling routines.    For the most basic solution you just throw your triangles into a global pool, sort by depth, then render the far ones before the near one's.   Which is painters algorythm.   You'll pops bwteen faces that intersect each other though.   There are ways around it, which pretty much old PlayStation games use..  


 

> this version doesn't contain types yet, i am currently going about this.
> can passing array types into a function be the same as passing a regular array into a function?
> i can only get variable pointers to point at the array in the function call.

example:
stuff(type_array(n).vertex)

function stuff(me as vertex pointer)
  ; this only points to the array element n
  ; i need to bring in other data like the array element maximum so i can make a loop in here etc. Huh
endfunction

i guess pointing to a type array is different from pointing to a normal array.

   You can't pass an array into a type.  Types are like blades of grass, there might be millions of them, but the don't actually know anything about the others.   If you have a type pointer and just a sgtructure in memory, you can have any crazy structure you want. 


   Above all you do is pass the typed array by handle.  So the function is now looking at a handle of the array. So you can look at all thethings in the  array from inside the function.

PlayBASIC Code: [Select]

   Type vertex
         x#,y#,z#   
   EndType
   
   
   dim type_array(10) as vertex
   

   type_array(5)   = new Vertex
   
   type_array(5).x =1000
   type_array(5).y =2000
   type_array(5).z =3000
   

   stuff(type_array())

   Sync
   waitkey


function stuff(me().vertex)
   ; this only points to the array element n
   ; i need to bring in other data like the array element maximum so i can make a loop in here etc. Huh
      For lp =0 to getarrayelements(me())
            s$=digits$(lp,2)+"="
             
            if me(lp)=0
                   s$+="Empty"      
            else
            
                  s$+="x["+str$(Me(lp).x)+"],"            
                  s$+="y["+str$(Me(lp).y)+"],"            
                  s$+="z["+str$(Me(lp).z)+"]"         
            endif
            
            print s$      
      next

endfunction

[stevmjon]

awsome kev. thanks for the sample code. that is what i was looking for.
there was so many mini samples to look at, i was getting a little confused. types are quite flexible.

in regards to polygon culling, i am only calculating the vectors of the objects, not the individual polygons, so this saves calculating the same point multiple times when it is shared by surrounding polygons. i keep this method right to the end until i draw the polygons themselves. here i look at a polygon table and check if the vector is visible or not, and if all vectors for that polygon are 'on', then draw poly.

it is fun coming up with different idea's and getting them to work.

PB2DLL. i will have a look into this. if this can do per pixel z buffer that is good.

well, going about the z buffer culling. i will experiment and see what i can get working. i wonder if shape collision will work also?

this is getting more fun the further i get into it. i had no idea the amount you need to learn though, and the mathmatics involved.
i almost gave up several times, especially getting all the theory and putting it together.

  stevmjon

[stevmjon]

hello

another update to v0.3
this version adds polygon clipping when a polygon is part inside & outside camera view.

it is kind of cool to watch the polygons divide when rotating the camera slowly.
so far i have kept the vectors all the way through the transformation process right till the screen pixels. it appears to work, but i may change to a polygon list instead.
i thought vectors will save calc time, but they need to be calced twice anyway(at draw routine), so a polygon list will be bigger, but only need to be calced once.

the next version will have polygon textures added.
i have kept camera rotation to heading (left / right only) because there is not enough objects in the scene, so i don't want view getting 'lost'.

  enjoy, stevmjon

[kevin]

Progressing nicely..  The clipping seems to work pretty well,  much like the method used when filling N sided polygons on the Amiga with the blitter.  Generally all i do is compute region codes for the points then, either reject and pass hrough to render routines.   The compares are a drop in the ocean to the rest of the rendering loops..     

[stevmjon]

hello,

i am excited to put up another update to v0.4
this version adds textures to non-clipped polygons. i also modified the clipping routine too. added some sky as well.

the further i go, the more interesting the process gets. it was hard getting started and learning the theory, but once you get started it flows from there.
i have added textures to the non-clipped polygons so far, as it was easier to begin with, and will add textures to the clipped polygons next update.
also, the clipping routine needed to be modified from the earlier version, as it wasn't clipping properly on some angles and when the polygons were half behind camera (all fixed now).
i also added partial sky to see how it looks. seems to be o.k. at the moment.
it is nice to see some colour on the screen too.

  enjoy, stevmjon

[kevin]

Very cool.. keep it up !

[kevin]

was looking at this today and couldn't but think of you :)

[stevmjon]

thanks kev, i can't wait to get to that level in the video (where everything works).

i am just posting a pic to let you all know i am still working on the 3D engine. i am trying to figure out a method of getting more accurate textures (see pic).
quad's work well because they can stretch to the shape of the polygon comparing both sides of the U & V.
tri's can't compare like quads, so have limited stretching.

i am not sure the best method to get around this?
whether to add more polygons to each surface when it is close to the camera,
or redraw the tri-texture taking the z into account using CopyStripH or CopyStripV to re-draw the polygon texture with perspective.

i would of had this done faster, but i have been playing "oxygen not included". it is a fun and addictive game. i got the early alpha release from steam.

  stevmjon

[kevin]

 well.. both  textured TRI and QUAD are linear mapping.  LInear is fine when all Z's are the same but will appear to warp in projected scene like this.  3D engines  (with 6DOF) don't use linear texture mapping, they use perspective texture mapping approximations.  Old hardware like the PSX for example only have linear mapping, so they chop the faces down to smaller chunks to hold better perspective.

In a scene, one idea would be to subidivide take objects that are closest the camera more than those far away..  The small faces will wrap but it's noticable..  The faces get cut up by some required level of detail..   think there's and only spinning cube demo in the source code board that does something like this..

You could always write a perspective texture mapper. and run it through PB2DLL .. which is what I assumed you were doing to do originally   

[stevmjon]

i found the demo code of the spinning cube.
i found it in the projectsv164L learning edition folder. > projects > demos > 3d_textured_cube.

i see you divided the polygon by averaging the outer points giving an extra center point, then averaging the outer with center point giving extra again, then applied this same calculation to the texture UV map. works well.

it is great getting idea's from other people. always helps to expand your knowledge.
just wondering, where did you get your 3D knowledge from? is there some recommended websites or books?

  thanks, stevmjon

[kevin]

  

where did you get your 3D knowledge from? is there some recommended websites or books?

  we did some stuff way back in high schools days..  but by the time It came time use it in the early 90's that was really useless.   There wasn't really any books that i had access to initially,  just me and my amiga and lots of head banging.   The stuff in the PC scene was driving what people were interested in the Amiga scene at the time.  

  around the end of the Id's Quake release perspective texture mapping was becoming the new big thing and there was series in the a programming mag about it.  I can't recall the name kf the mag, but the guy was Chris Hecker (so similar)..  Today there's lots of tidbits all over the place as people try and get retro systems to do things nobody imagined was even possible let alone on some 20 plus year old system

 A Walk Down Kev's Amiga History Lane