Path: utzoo!mnetor!uunet!lll-winken!lll-lcc!ames!pasteur!ucbvax!degas.Berkeley.EDU!ph
From: ph@degas.Berkeley.EDU (Paul Heckbert)
Newsgroups: comp.graphics
Subject: Re: Help Wanted: Filling Voxels
Message-ID: <23153@ucbvax.BERKELEY.EDU>
Date: 29 Feb 88 20:48:04 GMT
References: <198@dutrun.UUCP>
Sender: usenet@ucbvax.BERKELEY.EDU
Reply-To: ph@degas.Berkeley.EDU.UUCP (Paul Heckbert)
Organization: University of California, Berkeley
Lines: 33
Summary: compute plane-quadric intersections
Keywords:


[ In article <198@dutrun.UUCP> winffhp@dutrun.UUCP (ruud waij) asks
  how to find the set of voxels intersecting various modeling primitives,
  such as boxes, spheres, cones, and cylinders.  ]
  
Yes, interesting problem!  Fitting a bounding box around the object and listing
that object in all voxels intersected by the bounding box will be inefficient as
it can list the object in many voxels not intersected by the object itself.
Imagine a long, thin cylinder at an angle to the voxel grid.

I've never implemented this, but I think it would solve your
problem for general quadrics:

    find zmin and zmax for the object.
    loop over z from zmin to zmax, stepping from grid plane to grid plane.
	find the conic curve of the intersection of the quadric with the plane.
	this will be a second degree equation in x and y (an ellipse,
	    parabola, hyperbola, or line).
	note that you'll have to deal with the end caps of your cylinders
	    and similar details.
	find ymin and ymax for the conic curve.
	loop over y from ymin to ymax,
	    stepping from grid line to grid line within the current z-plane
	    find the intersection points of the current y line with the conic.
	    this will be zero, one, or two points.
	    find xmin and xmax of these points.
	    loop over x from xmin to xmax.
		the voxel at (x, y, z) intersects the object

Perhaps others out there have actually implemented stuff like this and will
enlighten us with their experience.

Paul Heckbert, CS grad student
508-7 Evans Hall, UC Berkeley		UUCP: ucbvax!degas.berkeley.edu!ph
Berkeley, CA 94720			ARPA: ph@degas.berkeley.edu