Game Maker's Garage Forum
Game Creation => Other Languages & Tools => Topic started by: WarHampster on July 30, 2012, 12:45:32 AM
-
I'd like to share my progress with the voxel renderer that I started in SilverCreator (http://www.silvercreator.net/cgi-bin/yabb2/YaBB.pl?num=1268372695) two years ago and then ported to .NET and Mono. I've expanded the basic height map rendering algorithm with the ability to render arbitrary 3d scenes built with voxels.
A voxel is a 3d pixel. Voxel renders therefore do not render polygons built out of triangles like most 3d renderers, but instead render lots of little cubes. Games like Minecraft use a voxel data structure to store their world, but convert the world into polygons and render it conventionally. On the other hand, renderers like mine draw the voxels directly.
Voxels are interesting because they easily solve problems that are extremely complicated in polygon renderers such as modifying the environment at runtime and rendering fine details and rough surfaces. In my engine, it only takes a few lines of code to blast a shockwave from under the player that ripples the world dramatically. I think that a world built of voxels has the potential to feel much more dynamic and malleable than one built of polygons, which intrigues my artistic side.
Nightmare test land.
(http://i43.servimg.com/u/f43/11/03/78/78/voxeng10.jpg)
No graphics test is complete without shaded cubes.
(http://i43.servimg.com/u/f43/11/03/78/78/voxeng11.jpg)
The world is stored as a 2d array of linked lists of vertical voxel spans. I use raycasting to project spans of voxels to the screen one vertical scanline at a time with no overdraw. The major limitation of this technique is that the camera is restricted to four degrees of freedom: translation along the three axes and rotation around the vertical. I use a perspective distortion hack to achieve tilting and haven't yet implemented rolling. It is possible to achieve six degrees of mathematically correct freedom in a renderer like this, but in my opinion if it looks right, then it is.
The next step for this project is adding voxel-built models to the scene and transforming them. Then optimization. Then maybe a game.
-
That looks epic!
I'd love to play with a nice ™WarHampster Voxel Game Engine.
-
That's awesome! I wish I could see it in action. The shockwave effect sounds intriguing.
-
Ace of Spades uses both kinds of voxel rendering! The world has polygons and the models are rendered with squares.
(http://www.rockpapershotgun.com/images/11/apr/spade/ace2.jpg)
-
Actually Ace of Spades uses the Voxlap engine, which is an old school voxel render that uses a similar algorithm to mine! The world boxes are made of lots of little boxes I believe.
-
That game was kindof fun. but it got boring because people are idiots
-
Sometimes flag caps it that game are too easy.
I just tunnel all the way underneath the thing and dig up, it literally falls down into your hole and then you just run.
-
I played exactly one fun game of Ace of Spades, then everything turned to shit. It was one really fun game though.
I've been experimenting with different methods of representing the camera. Originally I used euclidean angles: rotationX = x degrees, fov = x degrees, etc. Then I could cast rays within the view frustum formed by the field of view angle at the camera's current orientation. I tried switching everything to vectors: I stored a vector representing the direction of the camera and cast rays along a plane perpendicular to it, the field of view being implicit according to the length of the plane. This worked but required more calculations per ray (linear algebra to calculate the vector representation of each ray). On the other hand, working with vectors is much more natural when it comes to perspective projection of models, which is what I'm working on next. I'll probably settle for a hybrid approach.
-
Finished changing the camera data to vectors. Going to work on projecting objects: first step is 2d Doom style sprites, then 3d voxel models.
-
Sweet!
-
Sprites are in:
(http://i33.servimg.com/u/f33/11/03/78/78/them_t10.jpg)
-
Hahahahahha. I like them sprites.
-
My word. It looks like an anthropomorphic Pikachu with the lower half of its body shaved. This is 10 times more horrifying than Doom. :o
-
Er, um, Circuit said it for me. ???
-
You're scared? ...
Not scared enough.
-
I've been working on packaging games based on the engine for distribution.
http://www.mediafire.com/?ty24xu0djcia4e0
Could someone let me know if this works on their intel mac?
Arrow keys move and pan, shift and option tilt, w and s float. Space spawns sprites.
-
Works
-
Pretty cool.
-
It works on the iMac. Cool stuff.
-
It works well on my unibody Intel MacBook, and it looks awesome! It has a magical and dreamlike feel to it. When I move around the landscape, I can't "break it down" and explain how it was constructed, as I do with polygon graphics. Very cool. Also, I'm relieved to know that the man-pikachu is wearing track pants, and not his birthday pants as I previously believed. ;D
Nothing seems to happen when I press either shift or option. All of the other keys work though.
-
Wow, thanks Circuit! That's exactly why I'm so interested in voxels.
Haha, friend of mine made that graphic for the last Glorious Trainwrecks Pirate Kart and I've been using it wherever placeholder art is needed.
Should have mentioned, it's the right shift/ option. Do those work?
-
I noticed it seems to be constructed with a height map, since no platform is underneath or overlapping others. Will it render maps with multiple layers?
Also is each voxel one tall box or many stacked on top of each other?
-
Oh, it can render arbitrary scenes (so overlapping, yes), but I haven't specified a data structure that supports that yet so yeah, you're seeing a height map.
The renderer works with vertical columns of voxels of the same color. So if I want a bunch of green voxels stacked on top of each other I give the renderer a green column however many voxels high.
-
Should have mentioned, it's the right shift/ option. Do those work?
Sorry I'm so late to answer your question WarHampster. The answer is yes, those keys do work! And it's a pretty cool effect, BTW.
-
Basic voxel models are in. Here's a 3d curve thing:
(http://i33.servimg.com/u/f33/11/03/78/78/_tiff10.jpg)
What's important is that it can rotate independently.
-
Why has it got holes innit?
JK Circuit it sounds really cool is there any chance of your posting a video?
-
Oooooooooooooh.
The fact that it's purple, is that what distinguishes it and allows you to rotate it independently?
-
*pink
-
*Magenta
-
It's magenta ;)
Model rendering is still very rough so next step is to clean up and optimize... then support for real voxel model formats.
-
Oooh, question. Is it very efficient in rotation or does the CPU have to loop through every piece on the Magenta and hand rotate it using some fancy trigonometry?
How many chunks are in the purple piece? Is it CPU friendly to do the calculations live? I wanna see more of this in action.
-
Just a thought: you could accelerate a lot of the geometry calculations by doing them as a batch in OpenCL, and offloading them to the GPU.
-
Currently the renderer transforms every vertical column of an object by its rotation matrix. Do you know any more efficient algorithms? The purple thing is 10x10x10.
One of my goals for this project is to determine if it's possible to write a efficient voxel renderer in software. I'm going for light, portable, and easy to use. That said there is some very interesting research being done along exactly those lines.
Optimizations to work on:
Interval tree coverage buffer clipping
Quadtree spatial partitioning
-
Holy cow that sounds pretty epic. Those words, they must become part of my vocabulary.
-
::)
An interval tree is a recursive data structure (tree) that optimizes checking for intersections between line segments, such as lines that may or may not be visible on the screen.
A quadtree is just a method of organizing physical space to reduce the area that must be searched for visibility, collisions, etc.
-
I'm becoming more and more interested to see how you apply this.
-
::)
An interval tree is a recursive data structure (tree) that optimizes checking for intersections between line segments, such as lines that may or may not be visible on the screen.
A quadtree is just a method of organizing physical space to reduce the area that must be searched for visibility, collisions, etc.
Wait... what? Correct me if I'm wrong by quadtrees are generally used to cull collisions in 2 dimensional space--thats the only time I've ever needed to code one. 3 dimensional space requires an octree to be logical/efficient. I would suggest a BSP tree for 3d also, but I'm not sure how it would translate to a voxel engine; I've only ever used it with classical polygonal rendering.
As per matrix multiplication: no, I don't know of anything more efficient. I think that there is only one correct way to do matrix multiplications anyways. You could always do a parallel matrix multiplication (each column is calculated in its own thread), that should give you a near linear speedup.
-
Logically, yes, an octree is the 3d extension of a quadtree. However, the first law of computer graphics ("if it looks right, then it is") supersedes logic ;) My world data structure is a 2d array of linked lists of axially aligned columns so a 2d rectangular spatial partitioning method is easiest.
That's a really good idea, dispatch a bunch of worker threads to handle transformation. Maybe even spawn a new thread for each ray... yeah there's a lot of optimization I could do on that front.
-
Logically, yes, an octree is the 3d extension of a quadtree. However, the first law of computer graphics ("if it looks right, then it is") supersedes logic ;) My world data structure is a 2d array of linked lists of axially aligned columns so a 2d rectangular spatial partitioning method is easiest.
That's a really good idea, dispatch a bunch of worker threads to handle transformation. Maybe even spawn a new thread for each ray... yeah there's a lot of optimization I could do on that front.
Well yeh, raytracing is traditionally done in parallel (as far as I understand) with as many rays as there are cores being done in parallel. Rendering of graphics is perhaps the easiest place to do parallel algorithms (eg. massively parallel modern GPU pipelines with >100 cores). Also from your description what you are doing is called 'spatial hashing'--I think--and is not any kind of quad/oct tree. One more idea for optimization: vectors/arraylists are almost always faster than linked-lists merely because of cache coherency. Maybe try both and see which works better.
These are just things that are occurring to me as I write (I have a little experience with computer graphics myself), take any ideas you like, leave the ones you dont.
-
Yeah that's definitely something I'm looking into. One of the innovations(?) of the method I'm using is that the world is rendered in one "pass." That is, I don't maintain a zbuffer and then project models after the world is rendered but include them in the raycasting algorithm, so I won't have to worry about buffer access issues between threads.
Spatial hashing is different (it uses a grid of fixed size cells) but in this case is a good idea considering I want the world to be dynamic.
Interesting. I actually just implemented my own basic linked list class that does what I need but I'll look into that. Only problem is that I need it to be dynamic and an ArrayList might use more memory.
Right now I'm working on cleaning the math up a little, some weird things happen to models when they're rendered at certain angles that is probably caused by some floating point errors somewhere. I'll probably need to implement filtering of some sort to make up for it.
-
Spatial hashing can by dynamic--aka the dynamic nature of hash-tables and rehashing algorithms.
-
I was working on some aliasing issues with the models and realized that it's a problem with the coverage buffer. I think that using an interval tree would avoid the bug so I'm going to implement that now.
-
My nerdy senses are tingling.
Can't wait to check this fahizzle out. Or play with it, can't wait until you release a coolio API.
-
I've implemented a new coverage buffering algorithm and optimized the raycasting for multiple threads - On my quad-core I get 30+ FPS with as many models as I can spawn before I get bored hitting the spacebar.
For your testing pleasure: http://www.arcadeoftheabsurd.com/files/macvoxels.app.zip
Spacebar to make a model and R to rotate it. W up, S down, LShift look up, LOption look down. Arrows move and turn.
Give me an average FPS and what CPU you're using.
-
That's pretty epic. Runs fast. At first is was 100-200fps. Then a solid 30 after I got some models in it.
I really like it and the way it's rendered, the voxels seem to meld together. Is it possible to distinctly color certain pixels or voxel blocks?
-
Brilliant! I can think of a few more optimizations, then I'll add support for loading .vox models.
Thanks :) I think it will look really cool when I get lights and shadows in. Yeah, of course.
-
I got similar results to Gan, between 100-200 fps, and when I added a some models it was around 60, and I kept adding them but it was never lower than about 20 fps. I'd like to see how shading looks.