Path: utzoo!mnetor!uunet!lll-winken!lll-lcc!mordor!sri-spam!ames!pasteur!agate!ig!uwmcsd1!bbn!rochester!cornell!batcomputer!saponara
From: saponara@batcomputer.tn.cornell.edu (John Saponara)
Newsgroups: comp.graphics
Subject: Re: Help Wanted: Filling Voxels
Message-ID: <3892@batcomputer.tn.cornell.edu>
Date: 29 Feb 88 20:20:08 GMT
References: <198@dutrun.UUCP>
Reply-To: saponara@tcgould.tn.cornell.edu (Eric Haines)
Organization: Cornell Theory Center, Cornell University, Ithaca NY
Lines: 45
Summary: What's so slow?

In article <198@dutrun.UUCP> winffhp@dutrun.UUCP (ruud waij) writes:
>My ray tracing program, which can display the 
>primitives block, sphere cone and cylinder, 
>uses spatial enumeration of the object space 
>(subdivision in regularly located cubical cells 
>(voxels)) to speed up computation.
>
>The voxels each have a list of primitives.
>If the surface of a primitive is inside a voxel,
>this primitive will be put in the list of the voxel.
>
>I am currently using bounding boxes around the 
>primitives: if part of the bounding box is 
>inside the voxel, the surface of the primitive 
>is said to be inside the voxel.
>This is a very easy method but also very s-l-o-w.
>
>I am trying to find a better way of determining 
>whether the surface of a primitive is in a voxel 
>or not, but I am not very succesful.
>Does anyone out there have any suggestions ?


Ruud,
	Why do you consider BV (Bounding Volume) box comparison to voxel
extents slow?  This has to be the fastest comparison there is: some 6 tests
(2 pairs of x,y,z for the box and voxel).

	If box.hi.x < voxel.lo.x OR
	   box.hi.y < voxel.lo.y OR
	   box.hi.z < voxel.lo.z,
		- OR -
	If box.lo.x > voxel.hi.x OR
	   box.lo.y > voxel.hi.y OR
	   box.lo.z > voxel.hi.z,
	Then the box and voxel don't overlap.

A time-saver is to compute the BV's once for each object, storing them
temporarily.  Then, for each voxel and subvoxel you immediately have the data
at hand.  The only thing I can figure you mean as "slow" would be if you
recomputed the BV box extents for a primitive for EACH comparison.  This would
indeed be an incredible waste of time.

All for now,

Eric Haines (not John Saponara)