Path: utzoo!mnetor!uunet!lll-winken!lll-lcc!ames!umd5!uvaarpa!mcnc!thorin!unc!glassner From: glassner@unc.cs.unc.edu (Andrew S. Glassner) Newsgroups: comp.graphics Subject: Re: Help Wanted: Filling Voxels Message-ID: <1527@thorin.cs.unc.edu> Date: 2 Mar 88 15:55:07 GMT References: <198@dutrun.UUCP> Sender: news@thorin.cs.unc.edu Reply-To: glassner@unc.UUCP (Andrew S. Glassner) Organization: University Of North Carolina, Chapel Hill Lines: 119 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