mikhaley@images.cs.und.ac.za (05/14/91)
I am writing a ray-tracer as an honours research project, which renders tesselated shapes from Mathemtica, and am also looking into implementing CSG for some non-tesselated shapes to be input. Basically the hardcore is that I will normally be rendering lists of approx. 2000+ triangles or other primitives, and the program is currently being implemented on a 386PC in 'C'. However this machine is not the fastest machine on earth and as a result I am forced to find some very HOT acceleration algorithms. I have been working on algorithms for traversing voxels in an octree,(ie. Have been using non-uniform spatial subdivision techniques) and I have come up with some fairly good routines but I just want to know if any of the other methods are better and am I thus just wasting my time barking up the wrong tree. Also I would appreciate it, if any of you have any really efficient voxel traversal routines that you would like to compare with mine, to contact me! Thanx a million... Mike Haley mikhaley@images.CS.UND.AC.ZA
chrisg@cbmvax.commodore.com (Chris Green) (05/16/91)
In article <1991May14.070444.18261@images.cs.und.ac.za> mikhaley@images.cs.und.ac.za writes: >I am writing a ray-tracer as an honours research project, which renders tesselated shapes from >Mathemtica, and am also looking into implementing CSG for some non-tesselated shapes to be input. > >Basically the hardcore is that I will normally be rendering lists of approx. 2000+ triangles or >other primitives, and the program is currently being implemented on a 386PC in 'C'. However this >machine is not the fastest machine on earth and as a result I am forced to find some very HOT >acceleration algorithms. > >I have been working on algorithms for traversing voxels in an octree,(ie. Have been using >non-uniform spatial subdivision techniques) and I have come up with some fairly good routines >but I just want to know if any of the other methods are better and am I thus just wasting my >time barking up the wrong tree. Also I would appreciate it, if any of you have any really >efficient voxel traversal routines that you would like to compare with mine, to contact me! > >Thanx a million... > >Mike Haley >mikhaley@images.CS.UND.AC.ZA Since you are rendering tesselated shapes, your triangles are probably all of roughly uniform size. If this is the case, then you might be better off using uniform spatial subdivision. If implemented using integers (and hopefully in assembly language), this should really fly on a 386. -- *-------------------------------------------*---------------------------* |Chris Green - Graphics Software Engineer - chrisg@commodore.COM f | Commodore-Amiga - uunet!cbmvax!chrisg n |My opinions are my own, and do not - killyouridolssonicdeath o |necessarily represent those of my employer.- itstheendoftheworld r *-------------------------------------------*---------------------------d
wilson@cs.ucf.edu (tom wilson) (05/18/91)
In article <1991May14.070444.18261@images.cs.und.ac.za> mikhaley@images.cs.und.ac.za writes: >I have been working on algorithms for traversing voxels in an octree,(ie. Have been using >non-uniform spatial subdivision techniques) and I have come up with some fairly good routines >but I just want to know if any of the other methods are better and am I thus just wasting my >time barking up the wrong tree. Also I would appreciate it, if any of you have any really >efficient voxel traversal routines that you would like to compare with mine, to contact me! I have been trying to determine which subdivision schemes work best and in which situations. I have implemented my own nonuniform subdivision scheme, a (US) uniform subdivision scheme, a BSP tree, and an octree. To avoid tree traversal, I used a voxel index grid along with the leaves of the tree (octree and BSP tree). I haven't finished testing, but I can make some comments. While US isn't always the fastest (but often is), it does seem to perform best on the average. The BSP tree seems to outperform the octree. The BSP tree that I've implemented divides along the axis with the largest dimension (this may not be the best "simple" approach, but it does seem to outperform the octree so far). My scheme (which I won't explain) is comparable to the others. I have picked at the code for my scheme so that I doubt I can speed it up any more. I haven't had the time to do that with the other schemes. I doubt I can improve the US scheme any more since it is so simplistic. The BSP tree and octree may be improved, but I don't know. A question I asked the net was whether a pure tree (octree/BSP tree) is slower than the index grid. I received no replies, but perhaps it didn't go out. I would say, without a doubt, that implementing US is by far the easiest. If anyone wants to implement a speedup scheme, I would suggest US. I would like to implement some other schemes (e.g. ray classification), but I don't think I can devote the amount of time to write and debug other schemes (which tend to be much more complicated than the ones I've already done). No one seems to have other techniques implemented that they are willing to give away. One last note concerns octrees and BSP trees. There are several papers that discuss heuristics for determining how much or where to subdivide. I haven't tried to implement any of these. Tom
markv@pixar.com (Mark VandeWettering) (06/01/91)
In article <1991May14.070444.18261@images.cs.und.ac.za> mikhaley@images.cs.und.ac.za writes:
[ What's the best ray accleration technique? ]
Well, the best technique (in a way) is not to do ray tracing if you don't
have too. I take it for granted that you have considered this solution.
Now that you have decided on ray tracing, you have an enormous number of
ray accelerators to choose from. First of all, I believe that most of
the common ones (uniform subdivision, octrees, Kay/Kajiya bounding volumes,
BSP trees, etc...) are all pretty good and a good implementation of any
of them is probably within a factor of two of any of the others. (ooooh,
bold statement.. :-)
Some personal comments about some of the more important ones.
1. Uniform subdivision is great because the cost of casting
rays is kept very low, and the object data base is searched from
the eye out. Its only unfortunate characteristic occurs when a
large number of primitive objects happen to fall within a single
voxel. This makes certain scenes render very fast, while others
crawl along, even with the same number of pixels. I have yet to
see a really nice way of automatically detecting this condition
and "regridding" the environment. What is usually done is to arrange
these grids hierarchically. For example, Eric Haines usually brings
up the "teapot in the football stadium" as an example of where all
the triangles which make up the teapot happen to fall within a voxel. The solution is to have two separate grids, one surrounding the
stadium and the other surrounding the teapot. Usually this is done
by hand.
2. Octrees seem fine to me, once you actually get code that handles
some of the nasty cases worked out (ray leaves a cube via a face,
edge or vertex). Many people swear by these, I have little
experience.
3. Kay/Kajiya bounding volumes are what I used in the MTV raytracer,
with an automatic hierarchy generator. When compared against
Craig Kolb's ray tracer, MTV was definitely slower, but not by
as great an amount as I would have imagined. I believe that the
chief advantage of an automatic hierarchy generator is that
performance never seems to get AWFUL or other than you might
reasonably expect.
4. BSP trees are sort of midway between Kay Kajiya and Octrees.
If you were confined to polygonal models, you could implement
CSG nicely using this. Good stuff.
Anyway, you might try reading the chapter "A Survey of Ray Acceleration
Techniques" in Introduction to Ray Tracing edited by Andrew Glassner.
Mark VandeWettering, Pixar (disclaim disclaim disclaim)