3D Display Engine

saltpro15 · **Posted:** Wed Jan 28, 2009 2:46 pm

awesome, you have been on fire the last 2 days Razz

CodeMonkey2000 · **Posted:** Wed Jan 28, 2009 2:47 pm

I made a small change. I back cull before quick sorting, thus speeding up the quick sort method slightly, and when you draw, it's not looking at every single polygon. On my computer it made a small difference.

Turing:

%Lawson Fulton%
%%%%27/01/09%%%
%Change zoom with 'x' and 'z'

setscreen ("graphics:max;max;nobuttonbar;offscreenonly")

var stream : int
open : stream, "monk.raw", get

type Point :
record
x : real
y : real
z : real
x2 : int
y2 : int
end record

type Vector :
record
x : real
y : real
z : real
end record

type Face :
record
v1 : Point
v2 : Point
v3 : Point
normal : Vector
view : Vector
dotProd : real
col : int
end record

var chars : array char of boolean
const XOFFSET := maxx div 2
const YOFFSET := 0
const ZOFFSET := maxy div 2
const COL := black
var ZOOM := maxy div 3

var cLoc : Point %camera location
cLoc.x := 0
cLoc.y := ZOOM
cLoc.z := 0

var object1 : flexible array 1 .. 0 of Face
var object2 : flexible array 1 .. 0 of Face

var count := 0.0
for decreasing i : 256 .. 0 %set colours
RGB.SetColor (i, count, count, count)
count += 1 / 256
end for

loop %Load object
exit when eof (stream)

new object1, upper (object1) + 1

get : stream, object1 (upper (object1)).v1.x
get : stream, object1 (upper (object1)).v1.y
get : stream, object1 (upper (object1)).v1.z

get : stream, object1 (upper (object1)).v2.x
get : stream, object1 (upper (object1)).v2.y
get : stream, object1 (upper (object1)).v2.z

get : stream, object1 (upper (object1)).v3.x
get : stream, object1 (upper (object1)).v3.y
get : stream, object1 (upper (object1)).v3.z
end loop

proc drawPoint (var point : Point)
point.x2 := round (ZOOM * point.x) + XOFFSET
point.y2 := round (ZOOM * point.z) + ZOFFSET

%drawdot (point.x2, point.y2, COL)
%drawfilloval (point.x2, point.y2,2,2, white)
end drawPoint

proc drawEdge (v1 : Point, v2 : Point)
drawline (v1.x2, v1.y2, v2.x2, v2.y2, COL)
end drawEdge

proc drawFace (var face : Face)
drawPoint (face.v1)
drawPoint (face.v2)
drawPoint (face.v3)

%drawEdge (face.v1, face.v2)
%drawEdge (face.v2, face.v3)
%drawEdge (face.v3, face.v1)

var x, y : array 1 .. 3 of int %temp array for draw polygoon
x (1) := face.v1.x2
x (2) := face.v2.x2
x (3) := face.v3.x2

y (1) := face.v1.y2
y (2) := face.v2.y2
y (3) := face.v3.y2

drawfillpolygon (x, y, 3, abs (round (cosd (face.dotProd) * 255)))
%drawpolygon (x, y, 3, black)
end drawFace

proc drawObject (var object : array 1 .. * of Face)
for i : 1 .. upper (object)
drawFace (object (i))
end for
end drawObject

proc calcNormals (var object : array 1 .. * of Face)
new object2, 0
for i : 1 .. upper (object)
var vec1 : Vector
vec1.x := object (i).v2.x - object (i).v1.x
vec1.y := object (i).v2.y - object (i).v1.y
vec1.z := object (i).v2.z - object (i).v1.z
var vec2 : Vector
vec2.x := object (i).v3.x - object (i).v1.x
vec2.y := object (i).v3.y - object (i).v1.y
vec2.z := object (i).v3.z - object (i).v1.z

object (i).normal.x := (vec1.y * vec2.z) - (vec1.z * vec2.y)
object (i).normal.y := - ((vec1.z * vec2.x) - (vec1.x * vec2.z))
object (i).normal.z := (vec1.x * vec2.y) - (vec1.y * vec2.x)

var normFactor := (object (i).normal.x ** 2 + object (i).normal.y ** 2 + object (i).normal.z ** 2) ** 0.5

object (i).normal.x := object (i).normal.x / normFactor
object (i).normal.y := object (i).normal.y / normFactor
object (i).normal.z := object (i).normal.z / normFactor

object (i).view.x := cLoc.x - object (i).v1.x %view vector
object (i).view.y := cLoc.y - object (i).v1.y
object (i).view.z := cLoc.z - object (i).v1.z

object (i).dotProd := (object (i).view.x * object (i).normal.x) + (object (i).view.y * object (i).normal.y) + (object (i).view.z * object (i).normal.z)
if object (i).dotProd > 0 then
new object2, upper (object2) + 1
object2 (upper (object2)) := object1 (i)
end if
end for
end calcNormals

procedure rotatePoint (var x, y : real, theta : real)
var x2, y2 : real
x2 := x
y2 := y
x := x2 * cosd (theta) + y2 * sind (theta)
y := y2 * cosd (theta) - x2 * sind (theta)
end rotatePoint

proc rotateObject (var object : array 1 .. * of Face, x, y, z : real)
for i : 1 .. upper (object)
rotatePoint (object (i).v1.x, object (i).v1.y, y) %y axis
rotatePoint (object (i).v2.x, object (i).v2.y, y)
rotatePoint (object (i).v3.x, object (i).v3.y, y)

rotatePoint (object (i).v1.y, object (i).v1.z, x) %x axis
rotatePoint (object (i).v2.y, object (i).v2.z, x)
rotatePoint (object (i).v3.y, object (i).v3.z, x)

rotatePoint (object (i).v1.z, object (i).v1.x, z) %z axis
rotatePoint (object (i).v2.z, object (i).v2.x, z)
rotatePoint (object (i).v3.z, object (i).v3.x, z)
end for
end rotateObject

procedure swap (var list : array 1 .. * of Face, i, j : int)
var temp : Face := list (i)
list (i) := list (j)
list (j) := temp
end swap
procedure quickSort (var list : array 1 .. * of Face, left, right : int) %http://compsci.ca/v3/viewtopic.php?t=4091&highlight=quick+sort
var pivotPlace : int
swap (list, left, (left + right) div 2)
var lastSmall := left
for i : left + 1 .. right
if list (i).v1.y + list (i).v2.y + list (i).v3.y / 3 > list (left).v1.y + list (left).v2.y + list (left).v3.y / 3 then
lastSmall += 1
swap (list, lastSmall, i)
end if
end for
swap (list, left, lastSmall)
pivotPlace := lastSmall
if left < pivotPlace - 1 then
quickSort (list, left, pivotPlace - 1)
end if
if pivotPlace + 1 < right then
quickSort (list, pivotPlace + 1, right)
end if
end quickSort

var mx, my, mx2, my2, mbutton, rx, ry : int := 0
%setObjectColours (object1)

loop
Input.KeyDown (chars)
if chars ('z') then
ZOOM += 10
elsif chars ('x') then
ZOOM -= 10
end if

mx2 := mx
my2 := my
Mouse.Where (mx, my, mbutton)

if mbutton = 1 then
rx := - (my2 - my) div 2 %current rotation
ry := (mx2 - mx) div 2
rotateObject (object1, rx, ry, 0)
else
rotateObject (object1, rx, ry, 0)
end if

drawfillbox (0, 0, maxx, maxy, 255)
calcNormals (object1)
quickSort (object2, 1, upper (object2))

drawObject (object2)
View.Update
Time.DelaySinceLast (10)
end loop

DemonWasp · **Posted:** Wed Jan 28, 2009 3:31 pm

Alright, I'm fixing up the code now. Before I post, I do have to ask to make sure: are you certain that this is NOT going to be used for a school project or any other kind of academic work?

I'm making some pretty severe changes, and if this is for academic credit, I can't contribute to your program without the express consent of your teacher, and possibly not even then.

zero-impact · **Posted:** Wed Jan 28, 2009 3:31 pm

Thanks codemonkey but I dont see how that speeds up the quicksort at all?

DemonWasp · **Posted:** Wed Jan 28, 2009 3:34 pm

It speeds up the quicksort because it only has to sort N/2 polygons on average rather than N polygons.

Edit to my previous comment: as a side note, you only need to specify "var" for any arguments in your procedure list that you intend to modify. If you don't, it's best to leave it off so the interpreter can warn you if you accidentally modify something.

zero-impact · **Posted:** Wed Jan 28, 2009 3:37 pm

Oh no of course not. My grade 11 comSci course ended last week. This is purely personal interest.

Oh and yes I see that now. I didn't realize you were copying the object into another smaller one. That makes more sense. Yet.. it still seems impractical to have another object array. Especially because expanding flexible arrays is so inefficient.

DemonWasp · **Posted:** Wed Jan 28, 2009 4:10 pm

Alright then, I don't feel bad about contributing to personal-interest projects. Be warned before you go into this code: I have made some pretty heavy modifications to your code, including changing the global object1 flexible array to inside a class, splitting it into points() and faces(), and so on. I believe the comments in the file should make it pretty self-explanatory.

WARNING: Load times in this version are quite long. It has to do an O ( N ^ 2 ) amount of work to detect and remove duplicate points. You won't notice it for monkSmall, but for monkHiRes it can easily be 30 seconds. I have plans for how this could be improved drastically; see my comments inside the file.

There are other miscellaneous optimisations, including one to minimise the time required for flexible-array-resizing. This is commented in the file itself at the top.

zero-impact · **Posted:** Wed Jan 28, 2009 5:29 pm

Wow! That is an amazing improvement! +Bits

Clayton · **Posted:** Wed Jan 28, 2009 6:12 pm

Without actually having Turing to run this with (lab machine, emulation software not installed etc. etc) I have one question... why is the FPS limiter set to 100 fps? That's more than triple the "ideal" framerate that humans can see. Why not cut back on how often you're drawing things?

zero-impact · **Posted:** Wed Jan 28, 2009 6:34 pm

Because why not? :p I don't see any reason not to set it that high. it really only matters for the cubes and spheres anyways..

DemonWasp · **Posted:** Wed Jan 28, 2009 6:36 pm

It's limited to a maximum of 100fps. It actually ends up rendering far below that on most machines. I'm on a q9450 and monkHiRes ends up running at perhaps 15FPS (complete guesswork, as it doesn't output rate).

Probably the next step for me on this is to add a BST to improve the loading times (around 15 seconds for monkHiRes on my uber-powered desktop machine...that's about the same as the time required to load a COD4 map).

saltpro15 · **Posted:** Wed Jan 28, 2009 6:38 pm

DemonWasp, do you know if it's possible to output FPS in a game? that would be really handy for my raycaster...

zero-impact · **Posted:** Wed Jan 28, 2009 7:15 pm

I'm just wondering.. does anybody know if I'm on the right track with this Lambertian Reflectance?

DemonWasp · **Posted:** Wed Jan 28, 2009 7:47 pm

@zero-impact: Lambertian Reflectance appears to be used largely for simplistic lighting effects. It's a good next step for the program, and should make it look even nicer. I think it's about time to get started on making the code more object-oriented, so I think I'll get a start on that; we can merge in the changes you're making to the changes I'm making soon.

@saltpro15: There are a few easy ways. Simplest is probably to time each loop (tick) and then divide one second by that, to get the number of frames per second (frames / second = 1 / seconds per frame). That number changes every frame though, so it can change wildly.

Better would be to time some number of frames (10 or so) and update the FPS counter every N frames. This cuts down on the problem of the inaccuracy of Turing's timing system and gives you a more "stable" number that still appears just as animated.

saltpro15 · **Posted:** Wed Jan 28, 2009 7:52 pm

alright, if i were to guess I have mine running at around 10 fps, we shall see how close my guess was Very Happy

	Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB Username: Password: Register
Wiki Blog Search Turing Chat Room Members