HN Books @HNBooksMonth

Indeed :)

Curious, did you use any other information or was this a wild guess?

As a side note, if anyone wants to go into more depth, Samet's "Foundations of Multidimansional and Metric Data Structures" (http://www.amazon.com/Foundations-Multidimensional-Structure...) is an extensive survey of a lot of spatial data structures.

⬐ dandroid17

Simply mentioning PR and P Quadtrees tipped me off since that class is the only time I've ever heard of those data structures mentioned. Then I checked out your website and saw you went to UMD. Case closed, haha.

The article sensationally positions this as some incredible breakthrough that the "old guard" of gaming is trying to suppress. More likely, the code works, but has limitations -- the same limitations that led old guard luminaries like Carmack to defer the idea for another few years.

As others have pointed out, voxel-based games have been around for a long time; a recent example is the whimsical "3D Dot Game Hero" for PS3, in which they use the low-res nature of the voxel world as a fun design element.

Voxel-based approaches have huge advantages ("infinite" detail, background details that are deformable at the pixel level, simpler simulation of particle-based phenomena like flowing water, etc.) but they'll only win once computing power reaches an important crossover point. That point is where rendering an organic world a voxel at a time looks better than rendering zillions of polygons to approximate an organic world. Furthermore, much of the effort that's gone into visually simulating real-world phenomena (read the last 30 years of Siggraph conference proceedings) will mostly have to be reapplied to voxel rendering. Simply put: lighting, caustics, organic elements like human faces and hair, etc. will have to be "figured out all over again" for the new era of voxel engines. It will therefore likely take a while for voxel approaches to produce results that look as good, even once the crossover point of level of detail is reached.

I don't mean to take anything away from the hard and impressive coding work this team has done, but if they had more academic background, they'd know that much of what they've "pioneered" has been studied in tremendous detail for two decades. Hanan Samet's treatise on the subject tells you absolutely everything you need to know, and more: (http://www.amazon.com/Foundations-Multidimensional-Structure...) and even goes into detail about the application of these spatial data structures to other areas like machine learning. Ultimately, Samet's book is all about the "curse of dimensionality" and how (and how much) data structures can help address it.

In the late 90s at Naughty Dog, I used Samet's ideas (octrees in particular) for collision detection in the Crash Bandicoot games. In those games, the world was visually rendered with polygons, but physically modeled -- for collision detection purposes, at least -- with an octree. The nice thing about octrees is that they are very simple to work with and self-calibrate their resolution dynamically, making them very space-efficient. Intuitively, a big region of empty air tends to be represented by a handful of huge cubes, while the individual fronds of a fern get coated with dozens or hundreds of tiny cubes, because there's more surface detail to account for in the latter example.

I think the crossover point I mentioned earlier will come when GPUs become general-purpose enough to allow massively parallel voxel rendering implementations. That's what surprised me most about this article: they crow that it's a CPU-only technology... why? GPUs excel at tasks involving vast amounts of relatively simple parallel computation.

Prior to the crossover point, we'll see a bunch of cool games that use voxel rendering primarily for gameplay reasons. These games will look chunky compared to their polygonal peers, but will offer unique experiences. Minecraft is a good example. (I'm assuming it's voxel-based, but don't really know.)

⬐ wladimir

I think the crossover point I mentioned earlier will come when GPUs become general-purpose enough to allow massively parallel voxel rendering implementations

Indeed. This is certainly possible with modern GPUs, and has been for a while. Voxels are pretty well-suited to GPU rendering. See the research I linked to in another reply in this thread.

I didn't get around to reading their entire article, but if they call it a CPU-only technique they are behind the curve instead of ahead.

⬐ tripzilch

Well on the other hand, if they can already do this with just CPU, it can only get better as they unleash the power of a GPU as well, right? Especially as you say, voxels are pretty well-suited to parallel rendering like that.

⬐ buff-a

That's what surprised me most about this article: they crow that it's a CPU-only technology... why?

Because they don't know where raytracing research has gotten to with GPGPUs. Indeed if a few years ago you had told me that GPGPUs would be handling the insanely branching search of raytracing I'd have told you you were mad. Now we have iray. Bottom line: yes, its a staggeringly inefficient algorithm compared to a CPU, but I've got 480 cores!!!

I'll place money that this technique is just raytracing with a nice, hierarchical voxel tree. Plenty of work being/been done on combining such spatial subdivisions with SIMD. Usually the search ends on a polygon with a collision test. The idea here, which I havent come across (but I've not read every paper) is to store the subdivision down to sub-poly level so that you can skip the collision test. I hope they still share surface information between voxels, but maybe not. Essentially there are plenty of researchers who could implement their algorithm right now by adding "return true" for their poly hit test and increasing the subdivision threshold.

As Carmack said 114 days ago, "Nice idea. Be a few years till its viable."

But I'd be surprised if its this team that delivers the goods. They seem woefully uninterested in the wealth of research in the area.

⬐ kranner

In the context of voxel-based games, a vote for Voxatron: http://www.lexaloffle.com/voxatron.php

⬐ Shabaz

Someone correct me if I'm wrong, but I'm not sure that either Voxatron or 3D Dot Game Heroes actually use voxel based rendering. They may or may not store their models as voxels but I'm pretty sure that at some point it's converted into a polygonal model and shoved into a traditional polygon based rasterizing pipeline. As opposed to doing some raycasting into a datastructure containing voxels (e.g. an octree), which from my very limited understanding is roughly what a voxel based rendering pipeline looks like.

Doesn't take away the fact that both games look pretty damn nifty though.

⬐ skymt

Voxatron absolutely uses "true" voxel rendering.

> Voxatron is based on a virtual 128x128x64 display. It's a buffer of 3d video memory that is rendered out to the screen at the end of each frame, much as an old-school 2d display is. You can POKE bytes into the virtual memory, and they come out as voxels. I don't compromise on this -- even the menus are drawn into the voxel display. Hopefully one day I can get hold of a real physical 128x128x64 display and play Voxatron on it with almost no modification.

> The renderer is written in software (C + SDL). Each frame, scan through the virtual video memory back to front and look for voxels that have empty neighbours. If they are exposed, I transform the corners of a cube intro screen space and scan-render the polygon. Shadows are done with a traditional shadow-map but sampled with a filter to get the soft shadows.

http://www.lexaloffle.com/bbs/?tid=260

⬐ Shabaz

I didn't realize they use their own renderer. Pretty neat.

I guess I was thinking that the raycasting approach I've seen used in some of the sparse voxel octree stuff I read wouldn't make sense when you want the blockiness of voxels to actually show up very clearly, plus that it looked like you could achieve the same look using polygon based cubes. Guess I should've done a bit more research.

⬐ extension

You can do something like Voxatron with raycasting and it will look the same. It would just be inefficient with such big voxels. It becomes efficient when the voxels approach the size of 2D screen pixels.

⬐ Terretta

In the Comanche series, "voxels" were a selling point on the box.

http://www.youtube.com/watch?v=Ku-ICQvQJGI&sns=em

http://en.wikipedia.org/wiki/Comanche_series

No story I've seen on this engine seems to mention that series.

⬐ tripzilch

"voxels" are also a demoscene term for a method of rendering height-mapped landscapes in 3D, using a kind of raycasting technique. Technically they are "voxels", but the algorithm and their use is quite different from the sort of thing talked about here.

one thing is that only the landscape is rendered as "voxels" and it's mostly a textured height map, so it can't contain multi-level structures such as bridges, etc. it's best suited for mountain ranges and beaches and things like that.

just the term "voxels" is quite generic already, and doesn't really describe one algorithm over another, except that you're not using polygons.

⬐ lloeki

The problem with NovaLogic's VoxelSpace engine (used in Delta Force, Comanche and Armored Fist series) is that it's using a height map, and to speed up rendering, "locks" the Z axis to simplify a bunch of formulas to render voxels comprising the terrain much faster. Comanche 1 and 2 used sprites so that wasn't as noticeable, but Comanche 3 introduced polygon-based models, where the third axis speedup produces uneven deformation when looking up or down (you can see it in the video). You can see the same problem in OutCast. The choice of an engine with such limitations for a tank an helicopter and a ground soldier game is interesting, and you can notice how most of the gameplay in those games involves long range action along the horizontal plane. Notice how NovaLogic jet fighters games do not use VoxelSpace but a polygon-based terrain engine.

Today voxel-based renderers must allow correctly projected 6-DOF orientation of the viewport, and not just render terrain but arbitrary objects, and integrate together with various lightning and shader effects to stand any chance outside the neo-retro or abstract category.

⬐ chipsy

W/R to low-res voxel and octree engines, I think we can develop their visual detail considerably further without throwing over the table and trying to eliminate polygons. Nadeo has been taking the "large model blocks" approach and refining it for almost a decade now:

http://www.pcgamer.com/2011/05/27/mad-mad-world/

⬐ idspispopd

I was going to mention minecraft here, as it's using a voxel system where by the local volume is divided into "chunks" that are generated based on an algorithm or saved data. This has simulation advantages over similar software which uses a polygon mesh(e.g. 'From Dust'). Editing in polygons are merely computational changes to the surface, rather than removing voxel by voxel.) Editing the world in 'From Dust' is thus not too dissimilar to polygon geometry modelling in 3d software.

A simple example of the difference this affords is that large dynamic changes(e.g. a tornado 'mod') are the result of simply moving voxels around and letting the world renderer do it's thing. Where a polygon based system has to computationally alter the various surfaces to represent the changes made, which can be quite a bit more 'work' for programming the various scenarios.

⬐ buff-a

Unfortunately, this engine can only create an entire world out of voxels because it uses insane levels of repetition, i.e. compression. As soon as you do any of the kinds of interesting things that voxels let you do, you have instantly lost that repetition, and your "42 trillion" voxels are suddenly 42 trillion bytes. GLWT.

Ironically, I see pretty effective tornado effects in movies all the time, using polygons. An audience will happily believe that a tornado is composed of solid pieces of geometry (such as a car, or a cow, or individual roofing tiles) because they've seen it on TV. Tornadoes do not deconstitute matter as far as I'm aware. Thus hierarchical polygon models are ideal for tornadoes.

⬐ idspispopd

I feel like you didn't actually read my comment. Minecraft is a perfect example of how non-repetitive voxel worlds are processor intensive, and rather, this serves as a demonstration that unless fractal-like repetition is used then current day computers are not up to the task of detailed voxel worlds. (minecraft is a cpu hog.) It's trivially clear that this example is the result of repetition and not any breakthrough technology.

Also I feel like your example is confused, I'm trying to be polite, but I think you should do some research about what this is before writing a counterpoint like you have. (what you've written isn't really meaningful.)

Let's take an example of a whirl wind in a desert or dusty plain, in a polygon mesh you're not seeing individual sand grains being lifted from the polygon surface then flying around and landing somewhere else forming a pile, as you have suggested. In a voxel simulation you would however see just that.

Now ignoring post production, what you're seeing is a well textured, but (crucially) introduced, particle effect and maybe some surface deformation for the sandy hill that is being destroyed. (This isn't how the effect is done in film by the way.)

Translating (i.e moving) cows and other objects is actually more on par with how voxels work. I.e. moving an object through space and placing it somewhere else. So you were half right in your thinking that way.

To finalise my point, the tornado "mod" example that I cited wasn't me discounting polygons as you've interpreted, it was referencing this video specifically(i.e showing how voxels can trivialise the programming of advanced motion effects): http://www.youtube.com/watch?v=fSEwU5IqZ4A

⬐ None

None

⬐ ldar15

I thought I'd read the whole article since some are still commenting on it. First of all, if someone were to post an article on HN about a new technology that gets recursive compression (you can compress something 80%, and then do that again and again) because "they have a new algorithm", they would be laughed off the front page. Some people just don't know that that is impossible. Is this is what is being claimed here? There are three ways to get "unlimited detail" in computer worlds. 1) magical compression. 2) algorithmic generation 3) hierarchical composition, and as we know, 1 doesnt exist.

Looking at the article, this is clearly using method 3. Lets look at this "new" hierarchical composition. Hiearchical composition is when any given space is composed of smaller objects, and those smaller objects may also be composed of smaller objects.

When you do this in 2D games from 1980, we use the technical term "tiling the crap out of everything". You have a bunch of obviously repetitive pieces. If each tile is 16x16, and there are 256x256 tiles on a map, then one could say that there are 16 million pixels in the world, on a computer that had only 1Mb of memory.

So that right there is your clue that this guy is a fraud. 42 trillion voxels? Are they 42 trillion unique voxels, or are they tiled? [1] Right. (a "voxel" is the 3d equivalent of a 2D pixel).

The thing about tiling is it doesn't just apply to pixels or voxels. Tiling is just a spatial subdivision algorithm that splits space up in to 2d or 3d grids. You can store a color in each grid cell, and then its a voxel. But you can just as easily store the head of a linked list of polygons. And you can also store a pointer to another tile array, and that tile array can then store voxels, or polygons, or more tile arrays. When you do this, its a hierarchical data structure.

Do games/graphics programmers know all about this? Yes. Do we use hierarchical composition? Yes! All the time! Do we use axis-aligned hierarchies? Yes, e.g. octrees? Do we use regular grid composition all the way down? Fuck no. Why not? Because splitting up space along predetermined, regular, axis-aligned divisions is fucking awful for modeling interesting 3D worlds [3]. What you get is a brick world: [2]. Such rigid, regular, axis aligned hierarchy fits the real world poorly.

[1] http://media1.gameinformer.com/imagefeed/featured/gameinform... [2] http://media1.gameinformer.com/imagefeed/featured/gameinform... [3] Ok, minecraft being the exception =)

⬐ idspispopd

Minecraft demonstrates that (despite its possibly-inefficient coding) unique voxel based geometry is cpu heavy, and to pretend otherwise is fraud. From the outset it's obvious that recursion is affording the 'infinite' tag for this technology.

Interestingly this technology or even this idea isn't anything new. A nice way of summarising it is 3d fractals, sure it's infinite and richly detailed. But it's the same thing over and over again.

⬐ ldar15

No it doesn't. It demonstrates that Minecraft's solution is heavy. Minecraft is a cellular automaton. That's why its slow. It would be a mistake to believe that minecraft demonstrates the effectiveness of voxel technology.

⬐ idspispopd

Try to reply with examples(and when you do avoid choosing examples that follow confirmation bias) instead of broad-unbased refutations.

Minecraft clearly demonstrates the comparitive heaviness of using voxel arrays to represent a world in contrast to a polygon mesh. This point is trivial, and is not unique to Minecraft.

Additionally I'm finding a large number of comments that begin with "No it doesn't", then either stating an identical argument to the parent, or not attempting to refute the parent comment at all. If you're doing this for "points" then shame on you.

⬐ Geee

You have missed the point. The claim is that Unlimited Detail offers real-time voxel rendering with unlimited detail now, not when there's more powerful computers. It doesn't need a GPU. They supposedly have a new algorithm, which would indeed be revolutionary if true.

⬐ ldar15

If someone were to post an article on HN about a new technology that gets recursive compression (you can compress something 80%, and then do that again and again) because "they have a new algorithm", they would be laughed off the front page.

⬐ Geee

I don't argue for or against that 'new algorithm', just the topic we are talking about. Nevertheless, I haven't seen a proof that voxels can't be rendered more efficiently (although I think it's very improbable), while infinite compressibility is easy to prove to be impossible.

Edit: You didn't clearly get what is claimed here. 'Infinite detail' is just a marketing speech, the claim is that the algorithm can render up to screen resolution any data set whose size is limited only by memory. I.e. rendering speed isn't bounded by the size of the data set. The method has nothing to do with compression, and indeed the data set will be huge if everything is 'infinitely' detailed.

If the kind of query you are interested in running is a "K Nearest Neighbor Query" (that is for a give point give me the K nearest objects) you should also consider looking at metric trees. To have a metric tree you must have a metric function which takes two objects and returns a distance between them. The distance must satisfy:

   1. d(x, y) ≥ 0 (non-negativity)
   2. d(x, y) = 0 if and only if x = y (identity of indiscernibles)
   3. d(x, y) = d(y, x) (symmetry)
   4. d(x, z) ≤ d(x, y) + d(y, z) (triangle inequality).

Metric trees can be highly useful for data which is either highly dimensional (ie having greater than 3 or 4 dimensions) or non dimensional (like strings for instance DNA sequences).

The M-Tree is probably the most generally useful metric tree: http://en.wikipedia.org/wiki/M-tree

If you data is static or only updated very infrequently you should use an MVP tree. It is probably the best static structure, closely followed by Sergey Brin's GNAT structure.

MVP Tree: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.43.7... GNAT: http://infolab.stanford.edu/~sergey/near.html

Finally for some data (like strings) it can be very expensive to calculate the distance function. Therefore, there is another set of structures which relax the triangle inequality and are "near metric" trees. These can be useful for pruning your search space.

For more info on metric data structures see: http://www.amazon.com/Foundations-Multidimensional-Metric-Da...

⬐ crux_

Agreed. Also: R-trees don't do so well as you add data dimensions. (This is partly received wisdom; my rough understanding is that the empty volume in each node becomes cavernous and nice splitting becomes much less achievable.)

Another reference dump: If you haven't seen them I found spill trees a nice extension of metric trees for certain types of problems (CV anyone?); found via surfing links from some forgotten HN article: http://books.nips.cc/papers/files/nips17/NIPS2004_0187.pdf

If you want an overview, the bible right now is Samet's Foundations of Multidimensional and Metric Data Structures:

http://www.amazon.com/Foundations-Multidimensional-Structure...