AbsurdEngine Voxels

[Gan]

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.

[x]

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.

[WarHampster]

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

[Gan]

Holy cow that sounds pretty epic. Those words, they must become part of my vocabulary.

[WarHampster]

 

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.

[Connors]

I'm becoming more and more interested to see how you apply this.

[x]

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.

[WarHampster]

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.

[x]

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.

[WarHampster]

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.

[x]

Spatial hashing can by dynamic--aka the dynamic nature of hash-tables and rehashing algorithms.

[WarHampster]

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.

[Gan]

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.

[WarHampster]

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.

[Gan]

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?