I always thought we need a forum dedicated to ken Silverman.
So I would like to start a discussion about the voxlap engine. It's one of the most impressing things I've seen. However, there are some questions I would like to ask ken silverman, and I think some people might be interested too:
- uses voxlap rasterization for the cubes? If voxlap uses that, why not using opengl? If no, I would be interested in how the coverage of the screen is done. Basically I would create planes perpendicular to the base plane and "shoot" them radially. But doing it that way doesnt guarantee that all pixels of the screen are covered.
- there's definitely some sort of LOD Optimization in the engine, hows that done? Static LOD?
- I've implemented a small voxel renderer whcih can be used to display kvx files (currently only the smaller ones) My algorithm goes this way: project the point of view onto the base plane. From that (2d) point render all the columns from front to back using a stencil buffer. This way it's guaranteed that there's no voxel occluded by another one.
would be great to start a discussion about all these things, there aren't really many people out there who are interested in that stuff.
Sebastian
Awesoken at
Sebastian, I think you know more about Voxlap than most people. Before I get to your questions, I want to share some background information on Voxlap so other people know where you're coming from:
--------------------------------------
* Voxlap uses wave surfing (raycasting style) as described by this article: http://www.flipcode.com/voxtut/voxtut-struct.shtml Of course, I discovered the wave surfing idea long before I found this article. I just like giving out this link because I think it's a well-written tutorial. In Voxlap, I have extended the basic wave surfing algorithm in several ways:
* 6 degrees of freedom. For a 4 degree of freedom engine (x,y,z,yaw_angle), wave surfing is simple: you do a raycast through each vertical column of the screen. If you visualize what's happening in 3D, these vertical columns are really vertical planes - or planes perpendicular to the ground plane. In 6D, I still use vertical planes. The trick is allowing these vertical planes to map to diagonal lines on the screen.
* Room over room. The world map is basically a 2D array of pointers (1024x1024), which point to lists of surface voxels on each column. This column is a list of colors and is compressed using an RLE-style algorithm. I wrote my own memory management system to handle fast allocation/deallocation of 1048576 blocks of memory.
* Accurate cube intersections. Naive wave surfing algorithms sample on the x-y grid at pre-specified distance intervals. The simplest ones use linear spacing. More advanced engines will sample at higher density for close voxels. Voxlap goes one step further by sampling exactly at the grid boundaries. This is similar to how a Wolf3D-style engine does raycasting.
--------------------------------------
rasterization for the cubes? If voxlap uses that, why not using opengl?
Voxlap does not render cubes using rasterization! I tried that once and it was way too slow. Also, 3D hardware is not designed for such high polygon counts. For solid color polygons (no texture mapping whatsoever), I believe a well-written software engine can still beat hardware - even on today's cards.
how the coverage of the screen is done.
Voxlap raycasts along vertical planes exactly as you describe. The trick is to use 2 passes. In the first pass, I raycast to a temporary buffer. In the second pass, I copy from this temporary buffer to the screen. As I step through each pixel of the screen, I pick the nearest texel on the temporary buffer. It's the same idea as reverse-mapping when you texture-map polygons.
... LOD Optimization in the engine, hows that done? Static LOD?
Voxlap supports LOD for both world and sprites (separate code for each). I'll just describe the world algorithm because I think that's what you're asking about. My LOD algorithm works in the same way as mip-mapping of textures. For this reason, I like to call it mip-mapping. In Voxlap, the full resolution is 1024x1024x256. The first mip level then is 512x512x128. My engine continues dividing the world in half until it reaches 4x4x1. In case you're wondering, mip-mapping is disabled in the Voxlap Cave Demo. Since we use fog to clip off far voxels, mip-mapping isn't necessary.
KillerQ13 at
Voxlap Demo
I'm sure you've been asked this many times in e-mail but when can we expect another Voxlap demo? Hell...I wouldn't mind seeing the programs used in the screenshots. Also, I was wondering on the progress of the engine and features being made.
Heh...I also have these questions (I don't understand how you don't get annoyed with all the questions you get but I suppose if you survived programming tech support for companies...):
Voxel gravity: Will there be/are there improvements to the voxel fall code? As you've probably already noticed, large clusters of voxels will not fall (and sometimes very small chunks). I understand that going through the voxels to find floating chunks takes up CPU cycles and could cause visual lag if too much time is spent on this check. Is it possible to make precalculated "trees" or perhaps make a low priority thread that uses brute force so they will eventually fall?
Interpolation/anti-aliasing: I realize that, due to the uniqueness of the engine, this is next to impossible to do on hardware but with enough CPU power can be done in software. Are you planning on making this an option so more powerful machines can find it impossible to see voxels close up? (They look great from a distance. Very realistic. It blew my mind that I was looking at a software engine when I first saw the cave demo.)
Anyways, keep up the good work. Before I did a search and found your website, I didn't even know what a voxel was. Now I'm obsessed with them and I want to see hardware support for them...or at least hardware support for ray casting.
Thanks,
Keith R. Weimer
Sebastian at
voxlap
ken,
yeah, I had this idea too with the interpolation. But anyway, couldn't there be a case that you miss a column of voxels to display? Because when you scan along one plane you get all the columns on that path. But since the planes fan out radially, there might be some columns (especially when they are far away) that could be missed.
So basically how do you accomplish that really all visible columns are traced?
How many planes do you shoot out in one pass? do you some extra "shooting" when there are large holes after the first pass?
Voxlap is so astonishing, I showed the demo once at the university in a computer graphics course and the jaws were all down :-)
I hope too that we'll see another demo of the voxlap engine.
btw, if you want to see a hw voxelrenderer, visit my homepage.
thanks,
Sebastian
Awesoken at
Re: KillerQ13:
when can we expect another Voxlap demo?
We have nothing new related to Voxels to release at this time. Sorry, but I can't give you a better answer than "WID" (When It's Done).
progress of the engine and features being made.
I've been rewriting Voxlap to support faster world modification. I haven't had a chance to optimize it though. Tom's been improving his world generation utility. It's much faster now and it supports some new effects. That's about it.
We are still working on Voxlap and thinking about it. The truth is we've been distracted with smaller side projects. Since the release, I put a lot of time into improving Evaldraw and the OpenGL portion of JonoF's Build/Duke port. Tom's been working on Multi-Editoro, his collaborative text editor. Don't hesitate to check them out : P
Will there be/are there improvements to the voxel fall code?
Probably not. Speed is an issue, but memory is more the bottleneck for large pieces than speed.
anti-aliasing .. Are you planning on making this an option
Maybe, but not in the way you think. I've thinking about inverse mip-mapping. I may have invented that term. Let me explain: I would generate a double-resolution voxel grid at run-time. It would work like a sliding window that exists only in the neighborhood of your view point. The benefit of doing it this way is I won't need to change my raycasting algorithm too much.
-----------------------------
Re: Sebastian:
couldn't there be a case that you miss a column of voxels to display?
Yes. All visible columns are not always hit. If there is a thin pole in the distance, it can disappear when viewing it at certain angles. This is even more apparent when you lower the detail (fewer raycasts per frame). Voxlap will never generate the same output as a brute-force raytracing algorithm (the kind that shoots a ray through every pixel of the screen), although it comes pretty close.
How many planes do you shoot out in one pass?
In the Voxlap Cave Demo, it shoots approximately 320 raycasts or planes when you are looking towards the horizon. The number increases somewhat when you look up/down. I do not do any extra passes to fill in the cracks.
I showed the demo once at the university in a computer graphics course and the jaws were all down
: )
Sebastian at
I thought a little bit about combining the wave surfing algorithm with 3d hardware.
What about this: you still shoot the planes in the room, but you never draw anything, instead you determine the visible set of cubes, therby building up a vertex list. When all planes are done, just pass the whole vertex buffer to the hardware. This way, I think you could save a lot of time. Also, cubes look perfect since they're rasterized and you dont have to use a second pass.
When I have time I'll implement that and let you know.
Sebastian
Awesoken at
you determine the visible set of cubes ... pass the whole vertex buffer to the hardware.
That's a nice way to transfer the problem of overdraw from hardware to software. You could speed up the raycasting in software by raycasting into a lower resolution grid - perhaps 4x4x4 or 8x8x8 blocks - at the expense of sending a few extra polygons to the hardware. What this does not solve is the issue of high polygon count. It only reduces it for cases where there happen to be a lot of hidden surfaces. I would be interested to see your results.
Also, cubes look perfect since they're rasterized and you dont have to use a second pass.
The cubes don't look perfect in the Voxlap Cave Demo because I squeeze some things in the 16-bit fields of MMX registers. I can improve cube accuracy by changing these variables to floating point, but that would hurt speed a lot. Also, it wouldn't do anything to improve detail other than to make the blocky cubes look slightly less ugly when viewed up close.
Sebastian at
theres definitely a high polygon count in such an engine. But: when you can eliminte most of the invisible voxels, there isn't much left to draw. And the plane shooting mechanism just fits perfectly for that problem. Also, what I've done for my voxel rendere to improve cube drawing is that I've a specialized Code to merge the (max.) 3 visible planes of the cube to one polygon. This can be done extremely fast becaause al cubes are Axis aligned Cubes.
best Regards,
Sebastian
Sebastian at
Ken,
one more question:
when you scan along one plane, do you calculate the exact border of each sqare on the grid for every square you hit? Or do you do that for the first , lets say, 100 voxels and sample then at specific intervals along the ray to speed up the whole thing?
I have my engine now up and running and even though I optimized so much I get only 20 fps for 360 planes, every plane about 200 Squares with exact border calculation. (i.e. cubes look perfect)
I don't know how you get more than 100 fps with your engine when even scanning the whole grid.
Sebastian
p.s.: one more thing: which sizes do you use for your engine? I have 32x32x32 sized cubes with a map of 1024x1024x1024.
Using these dimensions enables me to use 16bit values for the projection which is perfect for mmx multiplies. Do you have in the cavedemo any support with mmx?
p.p.s: and btw, I don't use rasteriation anymore, I tried that but didn't succeed. The combination of scanning the world and let the hardware do the rasterization was too slow. Right now I'm just scanning along the rays, build a connected line on the screen and fill it. Looks like your engine :P
Awesoken at
when you scan along one plane, do you calculate the exact border of each sqare on the grid for every square you hit?
Yes. The intersection points can be determined very quickly. You should take a look at BLOCKSCAN.KC (it's one of the KC scripts I included with EVALDRAW.ZIP). This script shows exactly how my "supercover" x-y grid scanning algorithm works.
I don't know how you get more than 100 fps with your engine when even scanning the whole grid.
Replacing divides in the inner loop with multiplies helps. Replacing floating point variables with integer variables usually helps. Using assembly language helps. I really can't say much else unless you show me your code.
which sizes do you use for your engine? I have 32x32x32 sized cubes with a map of 1024x1024x1024.
Using these dimensions enables me to use 16bit values for the projection which is perfect for mmx multiplies. Do you have in the cavedemo any support with mmx?
Yes, Voxlap is optimized for MMX. I use it mostly for the extra register space - and for faster multiplies. Since the inner loop is full of branches, I was not able to take advantage of much parallelism in MMX.
In the height direction, I support 16 sub-voxel values, and limit the viewing to -2048<z<(2048). In the x-y direction, I maintain distance with full 32-bit registers, and extract just the high 16 bits of that for multiplies/comparisons.
Looks like your engine
Really? I'd love to see a demo of your latest engine.
Sebastian at
The intersection points can be determined very quickly.
true, I also have a fast, integer only and no slow arithmetic(mul, div) algorithm to generate the borders of the grid.
btw, the idea of the compiler inside the compiler is cool. I once did a similar thing which generated at runtime the machine code of a high speed blitter routine, because I thought I could gain a little bit more speed in the loops when replacing the counter variables with constants so the cpu didn't stall anymore :P
Replacing divides in the inner loop with multiplies helps. Replacing floating point variables with integer variables usually helps. Using assembly language helps. I really can't say much else unless
you show me your code.
Today I tackled down all the problems and realized that I have far too much multiplications and divisions which can be eliminated with lookup tables and reciprocal multiplications.
I'd love to see a demo of your latest engine
I'll implement all the optimizations and other things I want to do first and release then a "cave demo 2" :P
thanks,
Sebastian
KillerQ13 at
Voxel Smoothing
Awesoken said
The cubes don't look perfect in the Voxlap Cave Demo because I squeeze some things in the 16-bit fields of MMX registers.
I rather liked the look of the voxels in the Cave Demo more because they had a kind of a smoother, blurred look to them. Adjoining vertical rows of voxels kind of merge together to form a "smooth" surface. Voxels in Voxed just seem jagged to me. Is this related to something else or just the MMX squeezing?
Awesoken at
voxlap
I rather liked the look of the voxels in the Cave Demo more because they had a kind of a smoother, blurred look to them. Adjoining vertical rows of voxels kind of merge together to form a "smooth" surface. Voxels in Voxed just seem jagged to me. Is this related to something else or just the MMX squeezing?
Voxlap Cave Demo and Voxed both use the same engine. I think you're talking about the difference in lighting model used. Voxlap Cave Demo uses lightmode 1. In this mode, the raw voxel colors are scaled in brightness by the dot product between its estimated normal vector and this global direction vector (1,1,1).
Voxed uses lightmode 0, meaning it does not use normal vectors for lighting. Instead, I enable another mode which shades the faces of voxels based on direction, which makes it look sort of like a "Q-bert" grid. This mode is great for editing geometry because it makes it easy to see where voxels are. Unfortunately, for just about anything else, it looks terrible. You can press '.' on the keypad to disable face shading in Voxed. You can press '`' (tilda with no shift) to enable normal-based lighting (lightmode 1).
ShadowX at
Hey Ken, is there a way to change the size of the voxels in order to increase the "resolution". I didn't see anything that jumped out at me.
Awesoken at
is there a way to change the size of the voxels in order to increase the "resolution"
Sorry, the voxel world size is static. There's no way to change it without fixing some things in the engine source code. I chose 1024x1024x256 because it fits well on a system with 128MB RAM (using my RLE-style compression algorithm).
Sebastian at
ken,
you said once the cave demo doesn't use mip mapping.
Is this also true for distances other than 384? I tried the demo with -d1024 and the visual output just
cant be done without using mipmapping.
In my engine I fill the differences between 2 planes just with the color of the first plane. It looks exactly like when
I increase the Paramter "anginc" in your other demo.
Sebastian
p.s.: as I optimize more and more of my code I'm asking more and more how you actually can get this speed in voxlap. Right now, I dont have
optimized with mmx or any low level assemby, but voxlap is actually 3 times faster than my engine. Even with assembly and packed multiplies and so on, I dont think I could ever get this speed.
It's amazing.
Awesoken at
... the cave demo doesn't use mip mapping. Is this also true for distances other than 384?
Mip-mapping is completely disabled in JUSTFLY.EXE. There is no way to enable it without recompiling the code (or hex-editing the EXE). If you want to compare the difference in speed between Mip-mapping vs. no mip-mapping in Voxlap, you can always view the VXL file from the Cave Demo in VOXED.EXE. In Voxed, Press F10 to enable/disable mip-mapping. Press Numlock, Shift+Numlock, Ctrl+Numlock, or Shift+Ctrl+Numlock to change the scanning distance or mip distance. FYI: JUSTFLY.EXE uses vx5.anginc = 2, while the VOXED defaults to vx5.anginc = 1 (which is must slower), so you'll need to press . once in Voxed to make vx5.anginc = 2. Mip-mapping makes a big difference in speed if you fly high above the map and look down. It does not make much difference if you're near the ground because occlusion hides most of the far surfaces.
Alex at
Hello, Ken
Awesoken said
* 6 degrees of freedom. For a 4 degree of freedom engine (x,y,z,yaw_angle), wave surfing is simple: you do a raycast through each vertical column of the screen. If you visualize what's happening in 3D, these vertical columns are really vertical planes - or planes perpendicular to the ground plane. In 6D, I still use vertical planes. The trick is allowing these vertical planes to map to diagonal lines on the screen.
How do you do it, Ken? How does voxlap map to diagonal lines of the screen?
Awesoken at
How do you do it, Ken? How does voxlap map to diagonal lines of the screen?
These diagonal lines are the intersections between the vertical planes that you raycast along, and the screen plane. If you have done your calculations correctly, all lines should pass through the "zenith" point. I define the "zenith" point as either the highest point in the sky (projected to screen coordinates), or the point on the ground that you're standing over. Only one of them is visible at a time - depending on whether you're looking up or down. If you look towards the horizon, then neither zenith point can be projected to screen coordinates. In this case, all lines are parallel - much like the parallel vertical lines that you get in a standard 4dof voxel height-mapping engine.
Sebastian at
please see also the VoxlapGL Thread, I've released the sourcecode to a similar engine using 6dof raycasting.
Sebastian
Anonymous at
vox
Ken, i think u no who i am when i ask this question. But Why don't you and JonoF or Tom dobrowlski (i cant remeber which) see as releasing that voxlap game that resembles Doom, Quake, worms and leiro will put a dark mark on ur record. i've told10 friends about the cave thing and they said it should have been more like cstrike with weapons and people to obliterate into oblivion.
also in ken-build can u use ur own .ogg files for background music.
Awesoken at
voxlap
People, let's not start a flame war simply over poor grammar. That's just silly. I've seen much worse things than an occasional 'u' or 'ur'. If you can write with proper grammar, then please do so.
As for the Voxlap game, my opinions haven't changed. That's between Tom and I and since it's Tom's game code, he needs to be in the middle of it. At this time, we're both too busy with other things to start dealing with this. If you have an idea for Voxlap, you can always download the Voxlap library and make your own game with it.
Yes, you should be able to use your own OGG file as long as you rename it to NEATSONG.OGG and enable music in the setup program. JonoF implemented OGG support in KenBuild using FMOD just as a quick hack. At the time, it was easier than porting my KDM sound & music library to Windows, etc..
Sebastian at
KEN:
- Will you ever release the source code to Voxlap?
- And while developing voxlap, did you write everything first in C? So does a "Voxlap written completely in C" exist? And if yes, I'm very curious how much speedup you got from transforming the critical aspects to Assembly.
regards
Sebastian
Awesoken at
Will you ever release the source code to Voxlap?
Yes, there's a good chance that I will.
while developing voxlap, did you write everything first in C?
I wrote most of my test programs for algorithms in QuickBasic first. Then I port them to C. For the last few years, I've been better at maintaining equivalent C code for my assembler routines. For Voxlap, some of the C code are a bit out of date, but it still compiles.
So does a "Voxlap written completely in C" exist?
If I throw together the right combination of #ifdef values, then almost.
I'm very curious how much speedup you got from transforming the critical aspects to Assembly.
I believe the assembler code runs about 50% faster than the C code. The assembler code also does more than the equivalent C code, such as the Z-buffer and proper color scaling.
Calypso at
Sure, would it be better to use windows or linux, I am mainly a linux user right now, oh and compiler recommendations?
Digeraticus at
Any help for voxel experiments across the platform divide?
While I would love to use your libraries if I could, you have said yourself that they are totally Mac incompatible. Is there anything you can tell someone like me that you can
Awesoken at
voxlap
Well, here are your options:
1. Hope that I choose to release the source code sooner than later.
2. Attempt to write a competitive voxel engine from scratch.
3. Hope that JonoF gets bored enough to be willing to port Voxlap to the Mac.
4. Hope that the rumor about the new Macs using x86 chips becomes a reality.
Anonymous at
x86 chips? Not gonna happen...
Apple is most likely just getting motherboard chips from Intel again. They do that, from time to time.
I wish the fanboys who keep starting those rumors would get a freakin
Guest at
Mac using Intel x86? I think I
Well, guess the rumors were true after all...
The least they could have done is go with a GOOD x86 implementation, like AMD
Anonymous at
voxlap
Sebastian said
Ken,
one more question:
when you scan along one plane, do you calculate the exact border of each sqare on the grid for every square you hit? Or do you do that for the first , lets say, 100 voxels and sample then at specific intervals along the ray to speed up the whole thing?
I have my engine now up and running and even though I optimized so much I get only 20 fps for 360 planes, every plane about 200 Squares with exact border calculation. (i.e. cubes look perfect)
I don't know how you get more than 100 fps with your engine when even scanning the whole grid.
Sebastian
p.s.: one more thing: which sizes do you use for your engine? I have 32x32x32 sized cubes with a map of 1024x1024x1024.
Using these dimensions enables me to use 16bit values for the projection which is perfect for mmx multiplies. Do you have in the cavedemo any support with mmx?
p.p.s: and btw, I don't use rasteriation anymore, I tried that but didn't succeed. The combination of scanning the world and let the hardware do the rasterization was too slow. Right now I'm just scanning along the rays, build a connected line on the screen and fill it. Looks like your engine :P
Awesoken at
when you scan along one plane, do you calculate the exact border of each sqare on the grid for every square you hit?
Yes, Voxlap checks every grid intersection - there is no interval sampling at all. To speed up far voxels, I use mip-mapping. The best way to explain it is to have you run the Voxlap library demo game, press 't', and then type: /vxlmip=32 [enter].
Yes, Voxlap takes full advantage of MMX. I accumulate the screen projection vectors in the dwords of an MMX register. For 16*16->32 MMX multiplies, I use only the high word of each dword.