winffhp@dutrun.UUCP (Frits Post) (02/25/88)
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 ?
Thanks in advance,
ruud waij UUCP: dutrun!winffhp
--
...mcvax!dutrun!frits
Faculty of Mathematics and Informatics
Delft University of Technologysaponara@batcomputer.tn.cornell.edu (John Saponara) (03/01/88)
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)
ph@degas.Berkeley.EDU (Paul Heckbert) (03/01/88)
[ 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.edupaul@hpldola.HP.COM (Paul Bame) (03/02/88)
> / 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)
glassner@unc.cs.unc.edu (Andrew S. Glassner) (03/02/88)
In article <198@dutrun.UUCP> winffhp@dutrun.UUCP (ruud waij) writes: > >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 and I have discussed this in person, but I thought I'd respond anyway - both to summarize our discussions and offer some comments on the technique. The central question of the posting was how to assign the surfaces of various objects to volume cells, in order to use some form spatial subdivision to accelerate ray tracing. Notice that there are at least two assumptions underlying this method. The first assumes that the interior of each object is homogeneous in all respects, and thus uninteresting from a ray-tracing point of view. As a counterexample, if we have smoke swirling around inside a crystal ball, then this "homogeneous-contents" assumption breaks down fast. To compensate, we either must include the volume inside each object to each cell's object list (and support a more complex object description encompassing both the surface and the contents), or include as new objects the stuff within the original. The other assumption is that objects have hard edges; otherwise we have to revise our definition of "surface" in this context. This can begin to be a problem with implicit surfaces, though I haven't seen this really discussed yet in print. But so as long as we're using hard-edged objects with homogeneous interiors, the "surface in a cell" approach is still attractive. From here on I'll assume that cells are rectangular boxes. So to which cells do we attach a particular surface? Ruud's current technique (gathered from his posting) finds the bounding box of the surface and marks every cell that is even partly within the bounding volume. Sure, this marks a lot of cells that need not be marked. One way to reduce the marked cell count is to notice that if the object is convex, we can unmark any cell that is completely within the object; we test the 8 corners with an inside/outside test (fast and simple for quadrics; only slightly slower and harder for polyhedra). If all 8 corners are "inside", unmark the cell. Of course, this assumes convex cells - like boxes. Note that some quadrics are not convex (e.g. hyperboloid of one sheet) so you must be at least a little careful here. The opposite doesn't hold - just because all 8 corners are outside does NOT mean a cell may be unmarked. Consider the end of a cylinder poking into one side of a box, like an ice-cream bar on a stick, where the ice-cream bar itself is our cell. The stick is within the ice cream, but all the corners of the ice cream bar are outside the stick. Since this box contains some of the stick's surface, the box should still be marked. So our final cells have either some inside and some outside corners, or all outside corners. What do we lose by having lots of extra cells marked? Probably not much. By storing the ray intersection parameter with each object after an intersection has been computed, we don't ever need to actually repeat an intersection. If the ray id# that is being traced matches the ray id# for which the object holds the intersection parameter, we simply return the intersection value. This requires getting access to the object's description and then a comparison - probably the object access is the most expensive step. But most objects are locally coherent (if you hit a cell containing object A, the next time you need object A again will probably be pretty soon). So "false positives" - cells who claim to contain an object they really don't - aren't so bad, since the pages containing an object will probably still be resident when we need it again. We do need to protect ourselves, though, against a little gotcha that I neglected to discuss in my '84 CG&A paper. If you enter a cell and find that you hit an object it claims to contain, you must check that the intersection you computed actually resides within that cell. It's possible that the cell is a false positive, so the object itself isn't even in the cell. It's also possible that the object is something like a boomerang, where it really is within the current cell but the actual intersection is in another cell. The loss comes in when the intersection is actually in the next cell, but another surface in the next cell (but not in this one) is actually in front. Even worse, if you're doing CSG, that phony intersection can distort your entire precious CSG status tree! The moral is not to be fooled just because you hit an object in a cell; check to be sure that the intersection itself is also within the cell. How to find the bounding box of a quadric? A really simple way is to find the bounding box of the quadric in its canonical space, and then transform the box into the object's position. Fit a new bounding box around the eight transformed corners of the original bounding box. This will not make a very tight volume at all, (imagine a slanted, tilted cylinder and its bounding box), but it's quick and dirty and I use it for getting code debugged and at least running. If you have a convex hull program, you can compute the hull for concave polyhedra and use its bounding box; obviously you needn't bother for convex polyhedra. For parametric curved surfaces you can try to find a polyhedral shell the is guaranteed to enclose the surface; again you can find the shell's convex hull and then find the extreme values along each co-ordinate. If your boxes don't have to be axis-aligned, then the problem changes significantly. Consider a sphere: an infinite number of equally-sized boxes at different orientation will enclose the sphere minimally. More complicated shapes appear more formidable. An O(n^3) algorithm for non-aligned bounding boxes can be found in "Finding Minimal Enclosing Boxes" by O'Rourke (International Journal of Computer and Information Sciences, Vol 14, No 3, 1985, pp. 183-199). Other approaches include traditional 3-d scan conversion, which I think should be easily convertable into an adaptive octree environment. Or you can grab the bull by the horns and go for raw octree encoding, approximating the surface with lots of little sugar cubes. Then mark any cell in your space subdivision tree that encloses (some or all of) any of these cubes. -Andrew (P.S. to Rudi: I've had no luck trying to get through to dutrun!winffhp via electronic mail. If you can reach me at glassner@cs.unc.edu or uunet!mcnc!unc!glassner (or anything else that might work) then I can try to get back to you along that path. -A) - -- ---- ------- ------------ -------------------- --------------------- Andrew Glassner UUCP:decvax!mcnc!unc!glassner ARPA:glassner@cs.unc.edu
sow@cad.luth.se (Sven-Ove Westberg) (03/06/88)
In article <23153@ucbvax.BERKELEY.EDU> ph@degas.Berkeley.EDU.UUCP (Paul Heckbert) writes: |[ 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. | Yes this is a real interesting problem. But it is similar to the problem of converting a boundary representation to a block model. So it is possible to find good algorithms in the cad literature. One reference that converts a polyhedon to a block model is: Tamminen M, Samet H, Efficient Octree Conversion by Connectivity Labeling, Computer Graphics 18 (3), pp 43-51, July, 1984. Perhaps Markko Tamminen or Martti Mantyla, at Helsinki University of Technology, Finland could give us some good comments on this problem. Sven-Ove Westberg, CAD, University of Lulea, S-951 87 Lulea, Sweden. Tel: +46-920-91677 (work) +46-920-48390 (home) UUCP: {uunet,mcvax}!enea!cad.luth.se!sow Internet: sow@cad.luth.se