Realtime raytracing

Fundamentally you cannot make raytracing more efficient than scanconversion for first hits (without DOF) and hits for resulting shadow rays for point light sources. As long as those 2 calculations remain the most important intersections needed for realtime rendering raytracing has only very limited application there, because it only poorly fits methods designed to speed up those far more important tasks. So we will just be sticking with environment maps and such for a while longer.

(I should point out that the usual pro raytracing arguements about overdraw and scene complexity independence of raytracing are complete bunk, the same hierarchical descriptions used in raytracing can remove overdraw with scanconversion as Greene showed a long time ago ... and the scene complexity independence for raytracing only works when you are willing to forget about aliasing.)

[edited by - PinkyAndThaBrain on October 1, 2003 5:09:59 PM]

I agree, realtime raytracing will not occur, because of the complexity (as in complexity theory, not that its hard) of the calculation. The more objects, the slower it is to render, and its far more than a linear increase. Once could optimise a raytracer with specialy made rendering engines for each object type, and shadow interaction... but then it starts shifting form a true raytracer to a render, like a gfx card. Until quantum computers are invented... the complexity issue will stop any viable realtime raytracing engines (capable of large enviroments) from being made. This being said, who wants a realtime raytracer, when a quantum computer could probably hand realtiem radiosity lighting... now that would be nice :D :D :D, or even a raytracing radiosity hybrid :D :D :D :D :D :D :D. Video realistic lighting and environments, here we come .

That simply isn't true, look at the SaarCOR site. Raytracing actually has *better* complexity compared to rasterization. Raytracing is essentially limited by resolution rather than number of primitives (for anything other than a naive implementation).

EDIT (after davepermen): Yeah, but the SaarCor part specifically mentions the time complexity was all I meant by 'the site'.

[edited by - JuNC on October 1, 2003 6:02:43 PM]

www.openrt.de is FULL of documents (saarcor is just a subpart of it:D).

they have tons of how-to and how-to-not-do realtime raytracing. they fokus on a full working solution, without hacking around (except for gi, but there it will always just be approximating anyways..). the combination of what openrt presents, and what realstorm shows, could get rather cool to look at..

impossible? no way. it makes life in the end so much more easy for everyone.. as well for software developers as for the hw-developers in the backend. saarcor is a primitive gpu, just compare its specs to a gf3. still it gets about equal in speed. and raytracers could do much bether than just tracing triangles. voxel-worlds, more complex mathematical equations (yeah, who needs spheres anyways.. but there are others, wich are useful, for example "meshes".. you don''t need to trace every triangle individually.. there are much bether ways to intersect and render a mesh:D)

---

If that''s not the help you''re after then you''re going to have to explain the problem better than what you have. - joanusdmentia

davepermen.net

Raytracing versus scanconversion for first hits and shadow rays is actually a contest between forward mapping (objects to image-space) and inverse mapping (image-samples to world/object-space).

Ignoring memory access and with rasterization which treats pixels individually there is no advantage to either approach (assuming hierarchical occlusion culling ala Greene, which is not possible to do efficiently with present day hardware of course ... but we are talking theoretically here). The advantage of forward mapping is the coherency, in the past coherency inside primitives which allowed cheap rasterization ... in the future coherency inside the scene description, which with dense geometry would generate more bandwith with raytracing.

You can not drop the number of samples lower than the number of visible primitives without introducing aliasing. This isnt a viable option, you need ways to deal with that aliasing ... and if you have them the "advantage" for raytracing is removed.

Does that hold true, say if you have a random poly soup of small polys (inserted into individually appropriate structures for the two approaches). Now intuitively I''d say that raytracing performs better in this case, since for occlusion culling to work effectively you need reasonably large occluders. To get large occluders you need to fuse all of those small polygons together (e.g. by rasterizing them), now to me that sounds like it costs a hell of a lot more to transform/rasterize all of those little occluders than to trace rays through an appropriate structure.

That is the beauty of Greene''s hierarchical Z-buffer, depth testing and occluder fusion in one pretty package.

You get the same benefits from HOM, but you still need to rasterize polygons to achieve the fusion. I just reread the original Greene HZB so I''m not fully in possession of all the implications, is there a paper which demonstrates the equivalent time complexity?

Potentially visible polygons are rasterized, but most of them will be culled simply by testing the branch of the bounding volume hierarchy they are in against the hierarchical Z-buffer (which is rendered front to back, just like rays traverse it front to back).

Rasterization in itself does not present overhead, rasterization == intersection testing. Raytracing also has to test a ray against a set of potentially visible primitives after traversing a bounding volume hierarchy.

It works like HOMs, but HOMs are a practical approach meant to be used with hardware. It needs to work with special occluders since otherwise it would need to use software rendering for all tris.

Greene never went into timecomplexity, and everyone else has pretty much ignored the issue ever since ... raytracing researchers had better things to do than research on an area where they had very little to proof. Scanconversion has always been a standard way to speedup first hits simply because it worked (even without hierarchical occlusion culling!).

[edited by - PinkyAndThaBrain on October 1, 2003 7:14:30 PM]

How do you support your assertion that they are equivalent then? (admittedly I don''t have much support for my assertion either so I won''t make it a big issue )

The point I was trying to make is that if we take rasterization == intersection test of a primitive, you need to do more rasterizations for HZB or HOM (I gather now that the complexity is likely to be similar) than you do intersection tests for raytracing (since you can eliminate whole branches of tracing after a single intersection, whereas you still need to do BB checks *after* rasterizing all the potential occluders). But again I don''t have any hard evidence, just a gut feeling so unless someone has some hard figures I wouldn''t like to stake anything on this.

It might be very interesting to look into the time complexity of HZB/HOM against a comparable raytracing acceleration structure, don''t you think?

first hit is just the first part of any realistic image. and its the place where rastericers stop to work exactly.. except for pointlight shadows, possibly..

they cannot do any correct lighting calculations except LDE and LSE, if at all. and thats the most poor part of the lighting calculation. definitely not where the realistic part happen..

and then, when you start to try to render MORE than LDE and LSE (i typed LSD accidentally:D:D:D), rastericers stop to perform well.. one pass for each flat mirror, one (six) pass(es) for each approximated cubemapped object, etc. gi is nearly impossible to even SOLVE with rastericing only. (not that its not doable.. you can do EVERYTHING. ALWAYS.).

raytracers just take every lighting situation and say.. give me enough rays and i''ll solve exactly the equation you want. no additional work needed. and THAT makes them so general useful..

and raytracers will come more and more. reasons? we need more and more fast raytracing to actually generate data.. from lowpoly meshes with bumpaps, generated from highpoly meshes, to levels, wich get spherical harmonics and radiosity style lighting precalculated, to lowres runtime photonmaps (hehe:D), to what ever you want. raytracing gets needed more and more, so there will be more and more solutions to map the task directly to hw..

till we''re there..

and then, nothing is in the way to the full montecarlo solution of each scene with every complexity. theoretically.. and even practically. limits: memory, wich scales linearly with the scene, and renderingtime, logarithmically with the scene.

and thats about it..

---

If that''s not the help you''re after then you''re going to have to explain the problem better than what you have. - joanusdmentia

davepermen.net

I''m not and I hope noone is disputing that. Still, a large cost is the first-hit rays since they tend to contribute the most to the image.

My main interest is in Bi-directional path tracing and MLT so I know what you''re saying. Still I don''t think they will be viable real-time techniques very soon. I do hope that hardware implementations of raytracing (both first-intersect and shadow) become consumer level as they will greatly enhance the possibilites of the path-integral formulation.

Well, I''ve been interested in a hardware raytracer for a while, and was thinking about developing a synthesizable open source hardware raytracer based on the saarcor. Of course I have a couple of other ideas to include, but was wondering if anybody else would be interesting on working on a project like this.

LinaInverse

You can write a raycaster that emulates a raytracer. For every pixel (not row, pixel) you cast a ray and intersect it with stuff. From there you have several options... you can bounce it off the surface and look for lights the bounced ray goes near, adjusting the color as appropriate... or you can somehow statically calculate/approximate the lighting and use that information (lightmaps are an example of that).

~CGameProgrammer( );

_{-- Post screenshots of your projects. 100+ posts already in the archives.}

quote:

---

Original post by JuNC
How do you support your assertion that they are equivalent then?

---

Cause they both have near zero overdraw.

quote:

---

The point I was trying to make is that if we take rasterization == intersection test of a primitive, you need to do more rasterizations for HZB or HOM (I gather now that the complexity is likely to be similar) than you do intersection tests for raytracing (since you can eliminate whole branches of tracing after a single intersection, whereas you still need to do BB checks *after* rasterizing all the potential occluders).

---

Raytracing has to traverse the BB hierarchy more often than the rasterizer. I just look at what happens at the individual tri/pixel level, hierarchy will cut down the work needed at higher levels.

quote:

---

It might be very interesting to look into the time complexity of HZB/HOM against a comparable raytracing acceleration structure, don''t you think?

---

I dont have the necessary theoretical background to do the math, if you want to try dont use a pure BSP as a scene description though ... it is just not practical, at least not for gamedev

LinaInverse2010, as a purely for fun project it seems a lot of work for little return. FPGAs are a poor fit if you need a lot of high precision arithmetic, and are bloody expensive at that, so you will only ever see it perform in software simulation. I think most people would like something more tangible out of it, like a published paper for instance

quote:

---

Original post by PinkyAndThaBrain
Cause they both have near zero overdraw.

---

Hmm, that doesn''t necessarily mean the amount of work done to achieve the low overdraw is the same, I mean you could use beam trees to achieve zero overdraw in a polygon rasterizer, but I don''t think many people would claim that would be as quick as image space occlusion culling

quote:

---

Raytracing has to traverse the BB hierarchy more often than the rasterizer. I just look at what happens at the individual tri/pixel level, hierarchy will cut down the work needed at higher levels.

---

What I was trying to get at is that the occlusion culling still needs to render a hell of a lot of those little polygons to achieve correct occlusion culling, whereas the raytracer can very quickly determine the intersections by only looking at a tiny number of nodes. Now admittedly in real world situations things are different (larger occluders etc.) so it is probably a close run thing.

quote:

---

if you want to try dont use a pure BSP as a scene description though ... it is just not practical, at least not for gamedev

---

Hehe, for gamedev it''s still rasterization all the way

The BSP has nice properties for hardware implementation I suppose, but there are definitely better structures for ray acceleration.

quote:

---

What I was trying to get at is that the occlusion culling still needs to render a hell of a lot of those little polygons to achieve correct occlusion culling

---

Only what is potentially visible anyway.

quote:

---

whereas the raytracer can very quickly determine the intersections by only looking at a tiny number of nodes. Now admittedly in real world situations things are different (larger occluders etc.) so it is probably a close run thing.

---

Consider a single pixel frame. Which primitives are tested by the raytracing for that pixel? All the primitives in all the front to back sorted nodes crossed by the ray upto and including the node containing the first hit. Which primitives are rasterized with hierarchical Z-buffering to fill the pixel, the exact same set.

first hit is really unimportant, people. for realistic looking good lit scenes, you need from 50 upwards secondary, arbitarily distributed rays to gather global illumation. speed up ray<->scene AS MUCH AS POSSIBLE. every optimisation helps.

you can precalc even a full bsp of every mesh to trace them faster, this can even get faster than simply tracing individual triangles...

but so what..

its not a rastericers can do the rastericing-task faster than raytracers. thats LOGICAL. its the "can we get the additional parts of raytracing fast enough to surpass rastericers at all?". we can do more than every rastericer. simply try to rasterice a general scene with much reflections and refractions, say some ice-and-snow-cave with ice-walls and all. such scenes are about impossible to rasterice fast and good, need tons of passes to render partial usable reflectionmaps. it is easy and very fast for raytracers.. say 1 reflection and one refraction? => 1/3fps as no reflections and refractions.. normally you should have 2 refractions, and 1 reflection with two possible refractions.. so its at max 5 rays (should look good to choose only those possible paths..), and that means at MAX 5times as much rays. now part of the cave would be snow => no reflections/refractions go on there so it would be at about 2 rays in average in a normal such cave i guess..

---

If that''s not the help you''re after then you''re going to have to explain the problem better than what you have. - joanusdmentia

davepermen.net

oh, and, to say that.. THATS where you gain. the 0-overdraw helps extremely for the recursive parts of the raytracing. emulating THOSE is hell for rastericers..

---

If that''s not the help you''re after then you''re going to have to explain the problem better than what you have. - joanusdmentia

davepermen.net