Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!crdgw1!uunet!comp.vuw.ac.nz!waikato.ac.nz!canterbury!otago.ac.nz!grahaf From: grahaf@otago.ac.nz Newsgroups: comp.graphics Subject: Re: Ray Tracing Acceleration ... Is non-uniform s Message-ID: <1991Jun8.231208.498@otago.ac.nz> Date: 8 Jun 91 18:16:04 GMT References: <1991May14.070444.18261@images.cs.und.ac.za> <1991May31.175154.4496@pixar.com> <1991Jun7.174920.493@otago.ac.nz> <1991Jun7.190058.23133@infonode.ingr.com> Organization: University of Otago, Dunedin, New Zealand Lines: 96 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.