A voxel renderer

40fd50c8665e5b5f4233e4c0587a9d47
2
17_Gen_r 105 Aug 11, 2013 at 07:31 algorithm octree

Have people tried novel approaches to CPU voxel rendering? There are many solutions not quite found anywhere.
Here’s one: https://docs.google….dit?usp=sharing & another being implemented now below.

Please, post your experiments.

16 Replies

Please log in or register to post a reply.

Fd80f81596aa1cf809ceb1c2077e190b
0
rouncer 103 Aug 11, 2013 at 08:20

Im sorta only interested in voxels cause they are cool to raytrace with, like for global illumination, not much other reason at this time. but it has to be a gpu implementation, cpu is too slow.
So basicly my opinion is voxels unless procedurally generated are a bit of a waste of time when it comes to representing detailed things, just my opinion.

40fd50c8665e5b5f4233e4c0587a9d47
0
17_Gen_r 105 Aug 11, 2013 at 09:17

The problem is, except on parallel computers (GPUs), ray casting / tracing is hopeless. One has to find something else, an object-order algorithm. The links point to such approaches. Unfortunately one is ridiculously slow & the other isn’t promising.

For Unlimited Detail investigators: https://docs.google….dit?usp=sharing
Are there such investigators here?

B20d81438814b6ba7da7ff8eb502d039
0
Vilem_Otte 117 Aug 11, 2013 at 10:55

Ray tracing is not as hopeless as it seems to be, you can get fairly good approach for standard triangle rendering (using BVHs or KD Trees), but you probably know Arauna ray tracer for example. Of course it uses packet tracing and frustum tracing (to quickly determine which parts of trees are going to be ray traced).

You could use similar approach for voxel tracing, which could be fast enough.

Fd80f81596aa1cf809ceb1c2077e190b
0
rouncer 103 Aug 11, 2013 at 14:58

why so interested in cpu implementations, gpu is where the juice is at, i think.

40fd50c8665e5b5f4233e4c0587a9d47
0
17_Gen_r 105 Aug 11, 2013 at 15:08

I’m sure everybody, though tacitly, is of the opinion that a fast CPU thing is much more satisfactory. People think sequentially, time is the consciousness’ frame. Greedy algorithms are inherently sequential. Btw. rouncer, it’s your voxel renderer that compelled me to post my experiments.

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 167 Aug 11, 2013 at 18:46

@17 Gen r

I’m sure everybody, though tacitly, is of the opinion that a fast CPU thing is much more satisfactory.

Why would “everybody” be satisfied with a fast CPU renderer? I don’t think this is true at all. If you have an embarassingly parallel workload then it’s embarassing not to be doing it on a parallel computer, i.e. a GPU! ;)

6837d514b487de395be51432d9cdd078
1
TheNut 179 Aug 11, 2013 at 23:57

A KD-tree partition should be fast enough for you to find voxel chunks to raytrace. The bigger issue with voxels is memory. If you want any decent render, you have to stream large swaths of voxel data from the disk. Since that’s your slowest component, you’re limited in how fast your CPU algorithm can go.

I personally convert my voxel data into polygons, apply a Catmull-Clark subdivision to smooth the edges, and then pass it into the GPU for rendering. It’s quick, simple, and gets the job done even on older hardware.

40fd50c8665e5b5f4233e4c0587a9d47
0
17_Gen_r 105 Aug 14, 2013 at 13:01

Unlimited Detail is an old school front-to-back octree traversal. Octrees aren’t rejected only if remaining view subpyramids intersect them. It’s a synthesis of http://citeseerx.ist…=10.1.1.56.1295 & http://citeseerx.ist…i=10.1.1.18.397.

VD does this but poorly. It advances & quadrisects transverse sections of view subpyramids while front-to-back traversing the octree. This approach minimizes the working set & is sequential. The number of octree accesses is as the viewport because of the quadtree complexity theorem. I implemented the other link: a catastrophe (but novel “mass 3-D to 2-D conversion”).

Fd80f81596aa1cf809ceb1c2077e190b
0
rouncer 103 Aug 14, 2013 at 13:46

Really, my work?
The interesting thing in my mind wasnt the renderer at all, it was the editing method that I was struggling to get together, took me ages and a gpu flood fill to get my voxel csg going really fast. (for operating on GIANT voxel sparse worlds - complicates the algorythm)
Hand editing millions and millions of voxels (with a csg engine) to make a world is like entering a million data pieces into the cyc database, it takes ages, and I ended up disbanding the project cause I didnt think hand editing was the way to make these voxel worlds, and procedural generation makes more sense.

Just think, a density function (a three dimension equation of matter of space) relates to voxel space without any conversion, so thats what I think the coolest way to make something “big” voxel wise would be.

Making voxel characters is easier, (and hand editing now actually makes more sense) and you can even store the voxels in a brute force lot of data, space and matter, if you were making characters, leave the world/environment to procedural generation, and actually use brute volume stores for the characters themselves, id imagine you could get to 2048x2048x2048 voxels??? (with the latest equipment, mind you) not bad…, doing it gpu wise is what id do.
If your just using brute force volume stores (in lots of textures) then your boolean comparisons to do csg are the easiest thing imaginable to code, just flip bits on and off and its that simple.

you convert to SVO after the modelling is complete and disc stored.

The really cool gpu voxel programs are the realtime liquid/smoke generators, they are the coolest thing i saw. They involve some kind of feedback loop on a finite volume. but im doing everything gpu of course.

Remember, theres no point having a voxel renderer with nothing to render with, so that was my main effort into voxels was for, modelling. :)

3d coat is a cool modeller, i recommend and also purchased the student license for. (and its a christian company, so its like buying a pass into heaven hehe)

40fd50c8665e5b5f4233e4c0587a9d47
0
17_Gen_r 105 Aug 14, 2013 at 17:41

Really, my work?

Yes.
A very talented person’s Unlimited Detail. (The guy was into emulators in the past).

Fd80f81596aa1cf809ceb1c2077e190b
0
rouncer 103 Aug 14, 2013 at 19:18

I see. it is very clever, especially to do it without a turbo card.

40fd50c8665e5b5f4233e4c0587a9d47
0
17_Gen_r 105 Aug 17, 2013 at 13:58

Here’s the last attempt: https://docs.google….dit?usp=sharing

It’s a novel octree splatter involving a “mass 3-D to 2-D conversion”. Slow. No hateful thing (ray, float, / or *) occurs. If one were to properly combine Teller, Yagel & Meagher’s front-to-back octree traversal then success would be his.

7d9fd23a9442ea962df6b5d1ab1d2e55
0
silkroadgame 101 Sep 11, 2013 at 09:03

Haven’t tried this yet,but do agree that GPU rendering will be much faster than renderers.

40fd50c8665e5b5f4233e4c0587a9d47
0
17_Gen_r 105 Dec 26, 2013 at 14:34

It is fast now (archive kept up to date until UD floored). UD is not a secret anymore.

For there is nothing covered, that shall not be revealed; neither hid, that shall not be known. (Luke 12.2)

40fd50c8665e5b5f4233e4c0587a9d47
0
17_Gen_r 105 Jan 24, 2014 at 20:38

It is not that fast actually. Back-face culling should cause much better performance but UD makes do without. A novel thing occurred:

Suppose you are being given a pyramid P & a cube C. Narrow P horizontally & vertically about C with C still in that narrowed P i.e., P’. Let the rectangle R be the intersection between P’ & the view plane. If R not occluded then if R small enough or C is a leaf, output R in the color of C. Otherwise, apply this procedure to P’ & the octants Ci of C, in front-to-back order.

The above admits of a filth-less formulation, meaning free from /, * or those heinous floats. See Q*.c except *M.c in the archive (second link). Am I the only person trying to reverse UD on the whole Internet?

40fd50c8665e5b5f4233e4c0587a9d47
0
17_Gen_r 105 Jan 27, 2014 at 12:18

One is, of a certainty, astonished at the apparent disinterest of the Internet in trying to understand how that which said Internet so much criticizes does work. Except for Russians, nobody seems to pursue the reverse engineering of UD. This is made all the more uncanny by there being a soon to be published patent: is there some evil design, forcing the mass of mediocre programmers/Carmack worshipers to go the parallel octree raycasting route, impractical except on GPUs? UD is a /, * & float-free serial (non-parallel) volume renderer. Such features should be compelling to reasonable men in view of the fact that one can no longer do inelegant programming on pollutant GPUs in impunity.

A novel volume renderer: Take a pyramid P (quadtree) & a cube C (octree), the latter can be not included in the former. Octasect C, building a front-to-back list of cubes while rejecting those cubes that are disjoint from P, until a subcube C’ is included in P. Descend the quadtree pyramid P until pyramid is black, a leaf or C’ is included in no pyramid quadrant (i.e., C’ spans subpyramids), call the reached pyramid P’. If P’ is not black then if P’ is a leaf, paint the corresponding viewport rectangle with the color of C’ & update the pyramid quadtree to reflect the blackening of P’. Otherwise, for each quadrant P’i of P, if P’i is not black then apply this whole procedure to P’i & C’.

Should be implemented shortly.