grahaf@otago.ac.nz (06/08/91)
In article <1991May31.175154.4496@pixar.com>, markv@pixar.com (Mark VandeWettering) writes: > 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.. :-) Very. We have been using a ray-tracer for commercial TV animation for the last 3+ years. This system is a Constructive Solid Geometry (CSG) system which uses ray-tracing for ALL picture output. This includes B&W sketch prototyping and full colour, full texture, full transparency pictures. Three years ago I completed an MSc. which compared our system with two polygon/wire frame systems. For reasonably complex pictures the ray-tracer was orders of magnitude faster! The system uses a number of strategies to achieve this. > 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. 1). Adaptive space division with octree. This alows the sub-division of 'busy' voxels without bothering with the ones that are empty.( Geoff Wyvill ) > 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. 2). Octree flattening. This takes the adaptive division from 1) and converts it into a regular space division. This allows the use of a fast voxel skipping algorithm. ( John Cleary and Geoff Wyvill ) 3). Edge following. This uses the fact that in any picture each colour will cover more than a few pixels. This means that rays are cast only on the edges of areas of colour; the inside areas can be flood filled without casting extra rays. This has resulted in casting less than %10 of the rays for a full ray trace in some cases. Note that the resulting picture is identical to the fully traced version. ( Geoff Wyvill, Alistair Ward and Tim Brown ) 4). Fast antialiasing. Because the edges of colour patches are where aliasing occurs it is possible to perform antialiasing only on colour boundaries, saving an enourmous number of rays, again without affecting the resulting image. ( Geoff Wyvill and Paul Sharp ) The system is fast enough that we can do commercial work with one SG Personal Iris and one DEC Station 3100. It is written in standard K&R C and uses no special hardware. All the techniques used in our system are published, mostly in CGI proceedings and "The Visual Computer". If you are interested, e-mail me and I will send you a list of the refences. As you may have noticed Geoff Wyvill plays a large part in all this. He is the head of the Graphics Research Group here at the University of Otago. BTW We got the loan of an IBM 6000. Just the baby one apparently BUT boy what a mess. The salesman said it was an early version of the system but surely it should go faster than a DEC Station 5000 (30 MFlops vs 3 MFlops :). Graham Furniss, PhD student, Graphics Research Lab, University of Otago, Dunedin, New Zealand.
matt@genius.Berkeley.EDU (new user) (06/08/91)
Graham Furniss, PhD student, Graphics Research Lab, University of Otago, writes |> We have been using a ray-tracer for commercial TV animation for the last |> 3+ years. This system is a Constructive Solid Geometry (CSG) system which uses |> ray-tracing for ALL picture output. This includes B&W sketch prototyping and |> full colour, full texture, full transparency pictures. Three years ago I |> completed an MSc. which compared our system with two polygon/wire frame |> systems. For reasonably complex pictures the ray-tracer was orders of magnitude |> faster! |> I find this hard to believe. Are you saying that ray tracing a wire frame image was faster than using a line drawing algorithm. |> 2). Octree flattening. This takes the adaptive division from 1) and converts it |> into a regular space division. This allows the use of a fast voxel skipping |> algorithm. ( John Cleary and Geoff Wyvill ) |> This sounds like an interesting idea. How do turn an octree into uniform space division without losing the advantages the octree gave in the first place. |> 3). Edge following. This uses the fact that in any picture each colour will |> cover more than a few pixels. This means that rays are cast only on the edges |> of areas of colour; the inside areas can be flood filled without casting extra |> rays. This has resulted in casting less than %10 of the rays for a full ray |> trace in some cases. Note that the resulting picture is identical to the fully |> traced version. ( Geoff Wyvill, Alistair Ward and Tim Brown ) |> How do you determine where the color edges are without casting rays? |> All the techniques used in our system are published, mostly |> in CGI proceedings and "The Visual Computer". Can you post the specific month and year? take it easy Matthew Fisher
grahaf@otago.ac.nz (06/09/91)
In article <1991Jun7.190058.23133@infonode.ingr.com>, matt@genius.Berkeley.EDU (new user) writes: > > Graham Furniss, PhD student, Graphics Research Lab, University of Otago, writes > |> We have been using a ray-tracer for commercial TV animation for the last > |> 3+ years. This system is a Constructive Solid Geometry (CSG) system which uses > |> ray-tracing for ALL picture output. This includes B&W sketch prototyping and > |> full colour, full texture, full transparency pictures. Three years ago I > |> completed an MSc. which compared our system with two polygon/wire frame > |> systems. For reasonably complex pictures the ray-tracer was orders of magnitude > |> faster! > |> > > I find this hard to believe. Are you saying that ray tracing a wire frame image > was faster than using a line drawing algorithm. No. For extracting a wire frame from a CSG model. The problem is that as the number of primitives increases the amount of work goes up real quick and a wire frame is made from plane primitives whereas the raytracer uses mathematical definitions for shpheres, cylinders, etc. The other advantage for the ray tracer is that it doesn't have to worry about hidden lines, it never sees them. ( I must admit I exagerate the advantage a little too :) but not much). > > |> 2). Octree flattening. This takes the adaptive division from 1) and converts it > |> into a regular space division. This allows the use of a fast voxel skipping > |> algorithm. ( John Cleary and Geoff Wyvill ) > |> > This sounds like an interesting idea. How do turn an octree into uniform space > division without losing the advantages the octree gave in the first place. If you have a voxel which is not divided to the bottom level yet, generate the number of bottom level voxels it contains and put the same sub-model in each. No calculation required, just a flood fill (sort of). This is a gross simplification but gives the flavour. > > |> 3). Edge following. This uses the fact that in any picture each colour will > |> cover more than a few pixels. This means that rays are cast only on the edges > |> of areas of colour; the inside areas can be flood filled without casting extra > |> rays. This has resulted in casting less than %10 of the rays for a full ray > |> trace in some cases. Note that the resulting picture is identical to the fully > |> traced version. ( Geoff Wyvill, Alistair Ward and Tim Brown ) > |> > How do you determine where the color edges are without casting rays? Dare I say it? "By casting rays". To begin with we cast a sparse grid of rays over the image space. If two adjacent rays have different colour values we search for the point or points of change, then use these as seeds for the edge follower. This grid represents a small over head and there is the chance that if the grid is too coarse it will miss small objects but this proves to be relatively rare. Typicaly we use a 50 x 50 grid for a picture 512 x 512. > > |> All the techniques used in our system are published, mostly > |> in CGI proceedings and "The Visual Computer". > > Can you post the specific month and year? You asked for it... List of publications describing or involving Katachi (our solid modeller) in chronological order. Wyvill G and Kunii T L (1985) A functional model for constructive solid geometry, The Visual Computer, Vol 1, No 1, 3-14 Wyvill G, Kunii T L and Shirai Y (1986) Space Division for Ray Tracing in CSG, IEEE CG&A, Vol 6, No 4, 28-34 Wyvill G, Ward A and Brown T (1987) Sketches by Ray Tracing. Computer Graphics 1987 (Proc. CG International '87, Karuizawa) 315-333 Wyvill G and Sharp P (1988) Volume and Surface Properties in CSG. New Trends in Computer Graphics (Proc. CG International '88, Geneva) 257-266 Cleary, J. G. & Wyvill, G. Analysis of an Algorithm for Fast Ray Tracing Using Uniform Space Subdivision. The Visual Computer, International Journal of Computer Graphics 4(2):65-83 (1988) Wyvill G and Sharp P (1989) Fast Antialiasing of Ray Traced Images. New Advances in Computer Graphics (Proc. CG International '89, Leeds) 579-588 Spencer-Smith T and Wyvill G (1989) Four Dimensional Splines for Motion Control in Computer Animation State-of-the-art in Computer Animation (Proc. Computer Animation '89) 153-167 Wyvill G and McNaughton C (1990) Optical Models. CG International '90 (Proc. CG International '90, Singapore) 83-93 Wyvill G and Trotman A (1990) Ray-Tracing Soft Objects CG International '90 (Proc. CG International '90, Singapore) 469-476 We would still like to hear from other people working in this area, it's a bit lonely out here in the South Pacific (but peacefull :). Graham.
matt@genius.Berkeley.EDU (new user) (06/10/91)
|> > |> > Graham Furniss, PhD student, Graphics Research Lab, University of Otago, writes |> > |> 2). Octree flattening. This takes the adaptive division from 1) and converts it |> > |> into a regular space division. This allows the use of a fast voxel skipping |> > |> algorithm. ( John Cleary and Geoff Wyvill ) |> > |> |> > This sounds like an interesting idea. How do turn an octree into uniform space |> > division without losing the advantages the octree gave in the first place. |> |> If you have a voxel which is not divided to the bottom level yet, generate the |> number of bottom level voxels it contains and put the same sub-model in each. |> No calculation required, just a flood fill (sort of). This is a gross |> simplification but gives the flavour. |> |> > How is this different fom regular uniform division? It seems like USS is the same as an octree method that has been divided to the lowest level. I'm not sure what is meant by sub-model. Are the same object that intersect the higher level voxel associated with all the lower level voxels? |> > |> 3). Edge following. This uses the fact that in any picture each colour will |> > |> cover more than a few pixels. This means that rays are cast only on the edges |> > |> of areas of colour; the inside areas can be flood filled without casting extra |> > |> rays. This has resulted in casting less than %10 of the rays for a full ray |> > |> trace in some cases. Note that the resulting picture is identical to the fully |> > |> traced version. ( Geoff Wyvill, Alistair Ward and Tim Brown ) |> > |> |> > How do you determine where the color edges are without casting rays? |> |> Dare I say it? "By casting rays". To begin with we cast a sparse grid of rays |> over the image space. If two adjacent rays have different colour values we |> search for the point or points of change, then use these as seeds for the edge |> follower. This grid represents a small over head and there is the chance that |> if the grid is too coarse it will miss small objects but this proves to be |> relatively rare. Typicaly we use a 50 x 50 grid for a picture 512 x 512. |> |> > This sounds very much like adapative anti-aliasing. How do you known when to do the flood fill? How is a boundary generated and saved? Is this method effective with textured surfaces? Could this method be used to generate shadows? |> > |> All the techniques used in our system are published, mostly |> > |> in CGI proceedings and "The Visual Computer". |> > |> > Can you post the specific month and year? |> |> You asked for it... |> Are these papers available at any ftp sites? take it easy Matthew