Path: utzoo!mnetor!uunet!lll-winken!lll-lcc!ames!ucsd!sdcsvax!ucsdhub!hp-sdd!hplabs!hpcea!hpfcdc!hpldola!paul
From: paul@hpldola.HP.COM (Paul Bame)
Newsgroups: comp.graphics
Subject: Re: Help Wanted: Filling Voxels
Message-ID: <11390006@hpldola.HP.COM>
Date: 2 Mar 88 00:51:03 GMT
References: <198@dutrun.UUCP>
Organization: HP Elec. Design Div. -ColoSpgs
Lines: 39

> / comp.graphics / ph@degas.Berkeley.EDU (Paul Heckbert) /
> 
> 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.

Just an idea, but at this point you could perhaps use standard conic
scan-conversion algorithms.  If I'm not being stupid or something,
the algorithm listed below will be limited similarly to integer
scan-conversions.  The problem which might arise is that scan
conversions do not usually select all pixels (voxels) on the curve
but only approximate it.  The missing pixels (voxels in your case)
could leave small holes in your image.  Two possible solutions might
be reasonable:  1) "know" there may be holes and do a search of nearest
neighbor voxels when looking for possible intersections - only look for
objects not listed in the initial voxel (shouldn't be too expensive in
use) or 2) use a grid for scan conversion (or the algorithm below) which
is sufficiently smaller than your voxel grid to leave no holes large enough
to be distracting (an ill-defined problem I'm afraid).

> 	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

	--Paul Bame
	hplabs!hpldola!paul
	hpldola!paul@hp-labs.csnet
	303-590-5557 (Starting March 5, 719-590-5557)