mfisher@tictoc.cis.ohio-state.edu (matthew eric fisher) (01/15/91)
I looking for code, algorithim, or an explanation of the three dimensional
digital difference analyzer. I have implemented a uniform spacial subdivision
ray tracer. I am having problems getting it perfect. I have implemented a 3dda
but it is a major hack and I suspect it to be the cause of my problems. Also
for ray tracing the 3dda needs to identify every pixel hit not just the closest
one. I saw a listing for an article in Eurographics 87 that seemed applicable.
Where can I get a copy of Eurographics 87 though? I would be thankful for any
help.
Matthew Fisherjsp@cs.ed.ac.uk (John Spackman) (01/16/91)
In article <5933@exodus.Eng.Sun.COM> gilles@cannes.Eng.Sun.COM (Patrick-Gilles Maillot) writes: > > Sender: news@tut.cis.ohio-state.edu > >> I looking for code, algorithim, or an explanation of the three dimensional >> digital difference analyzer. I have implemented a uniform spacial >> subdivision ray tracer. I am having problems getting it perfect. I have >> implemented a 3dda but it is a major hack and I suspect it to be the cause >> of my problems. Also or ray tracing the 3dda needs to identify every pixel >> hit not just the closest one. >> Matthew Fisher > >You may find interesting to look at the work of Thierry Excoffier, >PhD. Thesis, 1988, "CSG and raytracing algorithms acceleration", pp 74-75 he >describes the use of dda rendering in order to accelerate the raytracing. >The 3ddda algorithm itself is fully described in another PhD. Thesis from >Patrick Maillot, "Contribution to the study of graphics systems, Software and >hardware architectures", 1986, pp 141-148 >Both PhD. thesis are in French and can be obtained by writing to: > etc 3d-dda's are prone to many special cases, especially when line slopes approach zero (so the the inverse line slope, generally used as the increment a la ARTS) approaches inifinity. A more numerically stable & hence more robust generalisation of Bressenham's algorithm to 3D, which navigates ALL the voxels intersected by the ray is described in `Scene Decompositions for Accelerated Ray Tracing', John Spackman, PhD Thesis The University of Bath, UK, 1990. Available as Bath Computer Science Technical Report 90/33 and what's more in following English prose. Copies can be ordered from Angela Coburn at JANET: `amc@uk.ac.bath.maths' or ARPA: `amc%maths.bath.ac.uk@nsfnet-relay.ac.uk'. Any surface mail should be addressed to:- Angla Coburn Mathematical Sciences The University of Bath Claverton Down Bath AVON BA2 7AY UK However, uniform spatial division is generally wasteful in memory costs, being non-adaptive. I prefer octtrees - the above thesis describes an incremental ray navigation of octtrees & techniques for octtree construction (& indeed for building Uniform grids). - `My way's better than everyone elses' :-) -- o---------------------------------------------------------------------------o |: JANET: jsp@uk.ac.ed.lfcs :: ARPA: jsp%lfcs.ed.ac.uk@nsfnet-relay.ac.uk :| |: JANET: jsp@uk.ac.ed.castle: ARPA: jsp%castle.ed.ac.uk@nsfnet-relay.ac.uk:| |: John Spackman, Computer Science, Edinburgh University, Room 2417 JCMB, :|