Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!swrinde!elroy.jpl.nasa.gov!decwrl!deccrl!bloom-beacon!eru!hagbard!sunic!mcsun!cernvax!chx400!chx400!sicsun!disuns2!/!moreillo
From: moreillo@disuns2.epfl.ch (Guy Moreillon)
Newsgroups: comp.graphics
Subject: Triangles in uniform spatial subivision
Keywords: 3DDDA, uniform spatial subdivision, ray-tracing
Message-ID: <1991Apr11.144339@disuns2.epfl.ch>
Date: 11 Apr 91 12:43:39 GMT
Sender: news@disuns2.epfl.ch
Reply-To: moreillo@disuns2.epfl.ch (Guy Moreillon)
Organization: Ecole Polytechnique Federale de Lausanne
Lines: 17


  I've got a problem concerning space subdivision and triangles:

  Let's say the space is subdivided in NxNxN voxels. The length, width and
height of the voxels need not be equal, most likely there're not. Now, let's
consider a triangle in that space. My question is : how do I find ALL the
voxels that the triangle cuts? When I mean cut, I mean that the list of the
voxels in which you can find a corner of the triangle will not do. If a part of
the triangle goes through a voxel, then that voxel has to be in the list.
  I guess one could use some kind of incremental algorithm (like a 3DDDA, but
I was wondering if there wasn't something niftier around...

  Anyone got any idea ?
  
Guy Moreillon
moreillo@disun20.epfl.ch
moreillon@eldi.epfl.ch