----------------------------------- zero-impact Tue Jan 27, 2009 12:07 pm 3D Display Engine ----------------------------------- You can change the filename in 3d.t to open any of the .raw files. Also if you want to try your ownl models just export as a .raw and make sure to convert it to tris first. There are 3 different resolutions for the monkey head: monkSmall, monk, and monkHiRes. monkSmall should run smoothly on most computers but if you have a newer computer you can try out the other ones. Rotate by clicking and dragging. Zoom with 'z' and 'x'. Any tips for optimization or anything I could improve are appreciated :) ----------------------------------- saltpro15 Tue Jan 27, 2009 3:08 pm RE:3D Display Engine ----------------------------------- won't work for me :( ----------------------------------- zero-impact Tue Jan 27, 2009 3:30 pm Re: 3D Display Engine ----------------------------------- Fixed ----------------------------------- saltpro15 Tue Jan 27, 2009 3:44 pm RE:3D Display Engine ----------------------------------- cool, you have way too much free time to make all these :D + 5 bits ----------------------------------- Zren Tue Jan 27, 2009 4:42 pm Re: 3D Display Engine ----------------------------------- I like how it continues to rotate after you let go of the mouse. -Lighting's next prob. Not much you could improve on a wireframe. You could put in a total polys and FPS counter I guess though. Maybe make the zoom speed faster... ----------------------------------- saltpro15 Tue Jan 27, 2009 5:39 pm RE:3D Display Engine ----------------------------------- you definitely have to rub this in paul's face :D ----------------------------------- zero-impact Tue Jan 27, 2009 5:44 pm Re: 3D Display Engine ----------------------------------- OK update. Thanks Zren, lighting is what I will be working on next but for this I have added solid faces. also I did increase the zoom speed :) ----------------------------------- andrew. Tue Jan 27, 2009 9:03 pm RE:3D Display Engine ----------------------------------- That is truly amazing. Well done zero-impact. I could never program something 3D like that in Turing. ----------------------------------- DemonWasp Wed Jan 28, 2009 12:54 am RE:3D Display Engine ----------------------------------- Very nicely done. I'm still looking at the code, but the first thing that jumps out at me as an easy fix is this: You're loading your data so that you have some N triangles with 3N points. That's great, and it works, but it's an awful lot of storage, since you tend to have multiple triangles sharing points. That means you're doing additional work, and storing more information! Instead, try this: For each model (or for the whole program, since you seem to be loading exactly one), have an array of Point objects. Load each point independent of the triangles. Then, have an array of Triangles - all these need are three integers, each an index into the Points() array. This allows you to re-use points in your geometry and simplifies your rotate methods (which now only need to rotate points). You will probably find that you need around 1/3rd as many points. This means: 1/3 as many point-rotate operations 1/3 as many point-draw operations 1/3 as much space required for point storage This would require that you either update your input files (save a backup first!) or re-interpret on-the-fly after loading. If you're not going past wireframe, it's also possible to just have an array of indices for each point indicating all the other points its connected to. Edit 1: Fixed some grammar. Edit 2: As a point of interest, it's generally poor style to have drawX() methods modify data. I realise it's just the x2 and y2 fields of Point, but either comment that behaviour, or comment in the Point object that x2 and y2 are just for graphics. Even so, it's probably best to move the "point.x2 := round (ZOOM * point.x) + XOFFSET" bit into drawObject(). This may happen as a result of the optimisation noted above. Edit 3: In your revised version (note: using version numbers helps us all keep them straight; the first one can be 0.01, this is then 0.02 or whatever), you're quicksorting. This appears to be in an attempt to make sure that your model is drawn in the "correct" order, so that polygons on the back don't appear over polygons on the front. Unfortunately, the only true solution to this is a depth buffer for every pixel on the screen (impractical, methinks); your solution is alright but not fantastic (look carefully at monkey's ears). ----------------------------------- CodeMonkey2000 Wed Jan 28, 2009 1:27 am RE:3D Display Engine ----------------------------------- You should also try back face culling (compare the normal vector to the view vector). You will be drawing roughly half as many polygons. ----------------------------------- zero-impact Wed Jan 28, 2009 2:53 am RE:3D Display Engine ----------------------------------- Thanks DemonWasp I have thought of a few ways of optimizing it but I just wanted to get it working :p unfortunately I have to completely redesign most of it to optimize it. Also for the quicksort, I have noticed the glitches in the monkey and especially the gun. It seems to happen with very elongated polygons.. which makes sense considering how it calculates it. Thanks for the tip CodeMonkey I will look into that. ----------------------------------- SNIPERDUDE Wed Jan 28, 2009 10:03 am RE:3D Display Engine ----------------------------------- ... Makes me want to dust off my old 3D engine and start working on that again. I never did post the thing because I kept wanting to refine it better. Anywho pretty good job Zero-impact. ----------------------------------- saltpro15 Wed Jan 28, 2009 11:21 am RE:3D Display Engine ----------------------------------- I just had an idea for this thing, being able to zoom in on a specific area on the models would be interesting. For example, zooming in to only look at the trigger of the gun ----------------------------------- DemonWasp Wed Jan 28, 2009 1:09 pm RE:3D Display Engine ----------------------------------- Update: I did a quick-and-dirty modification of your program to eliminate duplicate points as I'd suggested. I ran it on the monk.raw model; I had it give output: Of 2904 points, 2399 were duplicates (82.61%) and 505 (17.39%) were unique What this means is that you could potentially use around 20% of the space and computation time as your current method uses. This modification didn't take very long, maybe about 30-60 minutes. I can post code if you want, but it'll need a cleanup first. ----------------------------------- zero-impact Wed Jan 28, 2009 2:31 pm Re: 3D Display Engine ----------------------------------- That would be very much appreciated DemonWasp. I have been racking my brain for hours on how to eliminate duplicates.. easily.. that is. I would love to see the code for it regardless :D Codemonkey: I think I have the back face culling working pretty well as well as simple Lambertian reflectance. Here is the updated code ----------------------------------- saltpro15 Wed Jan 28, 2009 2:46 pm RE:3D Display Engine ----------------------------------- awesome, you have been on fire the last 2 days :P ----------------------------------- CodeMonkey2000 Wed Jan 28, 2009 2:47 pm Re: 3D Display Engine ----------------------------------- 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. %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 Wed Jan 28, 2009 3:31 pm RE:3D Display Engine ----------------------------------- 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 Wed Jan 28, 2009 3:31 pm RE:3D Display Engine ----------------------------------- Thanks codemonkey but I dont see how that speeds up the quicksort at all? ----------------------------------- DemonWasp Wed Jan 28, 2009 3:34 pm RE:3D Display Engine ----------------------------------- 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 Wed Jan 28, 2009 3:37 pm RE:3D Display Engine ----------------------------------- 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 Wed Jan 28, 2009 4:10 pm Re: 3D Display Engine ----------------------------------- 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 Wed Jan 28, 2009 5:29 pm RE:3D Display Engine ----------------------------------- Wow! That is an amazing improvement! +Bits ----------------------------------- Clayton Wed Jan 28, 2009 6:12 pm RE:3D Display Engine ----------------------------------- 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 Wed Jan 28, 2009 6:34 pm RE:3D Display Engine ----------------------------------- 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 Wed Jan 28, 2009 6:36 pm RE:3D Display Engine ----------------------------------- 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 Wed Jan 28, 2009 6:38 pm RE:3D Display Engine ----------------------------------- DemonWasp, do you know if it's possible to output FPS in a game? that would be really handy for my raycaster... ----------------------------------- zero-impact Wed Jan 28, 2009 7:15 pm RE:3D Display Engine ----------------------------------- I'm just wondering.. does anybody know if I'm on the right track with this [url=http://en.wikipedia.org/wiki/Lambertian_reflectance]Lambertian Reflectance? ----------------------------------- DemonWasp Wed Jan 28, 2009 7:47 pm RE:3D Display Engine ----------------------------------- @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 Wed Jan 28, 2009 7:52 pm RE:3D Display Engine ----------------------------------- alright, if i were to guess I have mine running at around 10 fps, we shall see how close my guess was :D ----------------------------------- zero-impact Wed Jan 28, 2009 10:57 pm RE:3D Display Engine ----------------------------------- DemonWasp: I looked at your code and redid the quicksort to draw the faces semi correctly (havn't done the back face culling yet) and it seems that the quick sort really is the biggest bottle neck. On monkHiRes it only gives an improvement of about 3-5 fps.. Does anyone know of any other practical ways of determining the order of the polygons? back face culling by itself is not enough as there is still some glitches with overlapping polys. ----------------------------------- DemonWasp Thu Jan 29, 2009 2:30 pm Re: 3D Display Engine ----------------------------------- I've done some more code updates: - Returned the quickSort, but refactored to improve its efficiency slightly. Draw order is now determined by an array of indices to faces, with back-culled faces removed beforehand. There's probably something that can be done to improve this, but I'm not seeing it offhand. Maybe when I've had some sleep. - Added a display for the number of points, faces, duplicated points and FPS - Added a logger stream (WARNING: logging severely reduces performance and generates a lot of data (if you uncomment the logger-writing lines) ) - Added the Vector3f class in Vector3f.t ; the API is largely the same as the jME Vector3f class. This class can replace Point soon. You will need to put Vector3f.t in the same folder as the main turing file and all the raw objects. Comments / recommendations / suggestions are all welcome. ----------------------------------- CodeMonkey2000 Thu Jan 29, 2009 3:32 pm RE:3D Display Engine ----------------------------------- Too bad turing doesn't support operator overloading. ----------------------------------- DemonWasp Thu Jan 29, 2009 5:06 pm RE:3D Display Engine ----------------------------------- Yeah, operator overloading could have made this a little easier. It'd also have helped if they hadn't grabbed "length" and "set" as reserved keywords. Most of what jME has are sorta useless though; their code for some of the multiply methods calls another multiply method. This works out fine in the JVM, which can short-circuit that, but Turing won't, so I cut it out: methods do what they're supposed to and return the result immediately. ----------------------------------- zero-impact Thu Jan 29, 2009 11:11 pm Re: 3D Display Engine ----------------------------------- Here is a small update with the lighting (still using my original procedural version) using Lambertian Reflectance. ----------------------------------- DemonWasp Fri Jan 30, 2009 4:34 pm Re: 3D Display Engine ----------------------------------- Updates: - Integrated zero-impact's Lambertian Reflectance. - Removed the Point type entirely. Use the Vector3f class instead. For projected pixel coordinates (formerly x2, y2), use pointProjectX, pointProjectY. - Added pervasive keyword so that certain classes / methods / variables do not need to be imported into classes. Performance: On this 2.4Ghz P4, I get about 5-9 FPS with monk.raw, depending on model angle. This represents a slight improvement over the version posted by zero-impact, which ran at about 4FPS on the same machine with the same file, regardless of model orientation. ----------------------------------- zero-impact Sun Feb 01, 2009 4:35 pm Re: 3D Display Engine ----------------------------------- Interesting.. I ran monkHiRes.raw on your newest update and walked away for about 5 minutes. When I got back Turing had crashed due to a "fatal error". Any ideas? ----------------------------------- DemonWasp Sun Feb 01, 2009 8:03 pm RE:3D Display Engine ----------------------------------- Sorry, no ideas. I can't reproduce the issue on my home PC. It spends about 10 seconds loading, then draws at about 3-4 fps. I should mention: the machine in question is incredibly powerful (q9450, 6GB ram, high-end hard disks). Is your machine perhaps short on RAM or CPU? If so, try a smaller model; monk or monkSmall or gun or whatever really, so long as it's not the high-res model. Load time is still an issue; I'm considering implementing some of the Java Collections framework so I can use a hashtable or similar to cut down loading from O ( numPoints^2 ) to O ( numPoints ) ----------------------------------- zylum Mon Feb 02, 2009 6:01 am RE:3D Display Engine ----------------------------------- Try using transformation/rotation matrices.. They should speed up your program a bit. My old engine used them but I'm not sure I posted a version with matrices.. Also look into the .ply file format -- it's a bit more efficient than .raw as it doesn't store multiple instances of the same point. Also, if you are aiming for speed, you'll want to minimize function calls and the number of classes you have. This is really bad practice but it helps a lot. ----------------------------------- DemonWasp Mon Feb 02, 2009 9:50 am RE:3D Display Engine ----------------------------------- @zylum: I inlined the swap() method used by qSort() and that resulted in a 0.5 FPS average increase (averages about 5.25FPS on this machine now). Inlining rotatePoint() wasn't quite as effective, but did provide a slight boost. Inlining drawFace improved by another 0.25 FPS or so. At this point I think we're rapidly approaching Turing's limits on speed. No matter how much we destroy real design for speed, it's never going to exceed 7-8 FPS on this machine. Turing is just too slow. For reference, the only testing I've ever done seems to indicate that Turing is about 1% the speed of compiled C / C++ or Java. ----------------------------------- zylum Mon Feb 02, 2009 2:51 pm RE:3D Display Engine ----------------------------------- Hmm... I remember my engine being quite a bit faster and I remember having ideas on how to improve the speed. Your implementation looks very similar to mine though... Do you cull the faces before sorting?? Check out my engine for more ideas.. ----------------------------------- DemonWasp Mon Feb 02, 2009 3:43 pm RE:3D Display Engine ----------------------------------- Faces are "culled" before sorting, in that the indices of drawable faces are input into an array which is then sorted. Perhaps some speed can be gained by allocating that array differently...nope. Even allocating the array so that it's not new'd at each frame-draw doesn't produce any meaningful performance boost. Remember, speed varies substantially from one version of Turing to another, and from one machine to another. I'm on a dreadfully slow and overburdened machine (Firefox + WinAmp + a server + Lotus Notes + remote-desktop software, with only 2.4Ghz CPU and 2GB RAM). ----------------------------------- zylum Mon Feb 02, 2009 5:28 pm RE:3D Display Engine ----------------------------------- I just tested my old engine and it can run two monkey models at 10-16 fps depending on the rotation. And like I said, there's tons of room for improvement... You must have some sort of bottle neck somewhere. Try timing each major section of code to see where the biggest slow down is. Check the rotation function, sorting and drawing.. Here's my engine btw http://compsci.ca/v3/viewtopic.php?t=9639&highlight=zylum+engine ----------------------------------- zero-impact Mon Feb 02, 2009 8:57 pm RE:3D Display Engine ----------------------------------- DemonWasp: no power issues here. I'm running a q660 with 2Gb of RAM. I get about 12 - 20 fps on monk.raw Zylum: That is amazing :D