Path: utzoo!mnetor!uunet!lll-winken!lll-tis!ames!pasteur!agate!saturn!skinner From: skinner@saturn.ucsc.edu (Robert Skinner) Newsgroups: comp.graphics Subject: Re: Defining a sphere with Bezier patches Message-ID: <2552@saturn.ucsc.edu> Date: 30 Mar 88 18:38:20 GMT References: <2390@saturn.ucsc.edu> <1632@pixar.UUCP> <1639@pixar.UUCP> <3183@csli.STANFORD.EDU> Organization: U.C. Santa Cruz, CIS/CE. Lines: 136 Keywords: sphere, Bezier, REYES Summary: clarification of the goals (long) Since I started this, I feel that I should clarify why I want to define a sphere in terms of Bezier patches: I'm writing a renderer that is borrowing many ideas from the REYES renderer used at Pixar (SIGGRAPH proceedings, 1987). The REYES approach to rendering is (to me, at least) a generalization of the Lane-Carpenter patch rendering algorithm. As an abbreviated overview, here's what REYES does for each primitive: 1. Compute the primitive's screen bound. 2. If the screen bound is small enough to be _efficiently_ rendered with polygons, do so. (Diced) 3. Otherwise, split the primitive into one or more primitives of the same or different type. 4. Repeat until you run out of primitives. The important thing here is that you don't resort to polygons until the primitive is small. That way, you can generate enough polygons to do a good job (no faceting), without overloading the renderer or using too much memory. This still generates n*n polygons, but at least n is small. I planned on supporting Bezier patches anyway, because they are such a _good thing_. Now, if I define my sphere with patches, I get the sphere for almost free. Faux and Pratt state that a Bezier approximation of a circular arc deviates at most by .13%. So I assume that the surface approximation would be on the order of .26%. In article <3183@csli.STANFORD.EDU>, rustcat@csli.STANFORD.EDU (Vallury Prabhakar) writes: > > This is true. I was speaking strictly from a modelling point of view. > Sorry for not being more specific. > > For all of the above reasons, I think that the SOR approach is a more > "efficient" method of generating a spherical surface. > You speak of "modeling point of view", but in what context? You have to _do_ something with the model, either render it, construct some other model from it, store it in a file, etc. I agree that the two most efficient ways of defining a sphere are implicitly: (x-x0)^2 + (y-y0)^2 + (z-z0)^2 = r^2 and parametricly: f(u,v) = (r*sin(u)*cos(v)+x0) i + (r*sin(u)*sin(v)+y0) j + (r*cos(u)+z0) k The parametric equation is very close to Prabhaka's SOR approach. Niether of these fits the above rendering steps, in particular, how do you split these primitives into other primitives? The parametric equation could be split by restricting it to sub-ranges of u-v, but how do you generate the bound? > 1) Space > ----- > ... Generating the entire > sphere using a bicubic approximation is bad for health. You'd need to break > it down into at least 4 patches. Figuring out details to ensure that the > patches are C^n continuous (n = 0, 1 and 2 if you wish) is going to take up > time. In contrast, the surface of revolution method needs only a single > arc which may be stored as a single vector. Generating the surface from this > would also be much faster than using Bezier patches with all the > considerations above. It takes 8 patches for the sphere. It does take time to compute those patches, but you only do it once for the unit sphere, then scale and translate it to the correct location/size. At what resolution are you going to store the arc you are going to revolve? Are you going to compute sin/cosine when you do the revolution, or are you going to precompute them and use linear or higher order interpolation? You can't just use one resolution, the sphere may be large or small on the screen. This adds computation to the SOR method. > 2) Ray surface intersections > ------------------------- Raytracing uses the implicit equation, coupled with the parametric equation for a ray, and solves the quadratic equation for the parameter of the ray. If the solution is real, it intersects, and the normal to the surface is from the center of the sphere to the intersection. The SOR is not appropriate here. > 3) Numerical characteristics (Accuracy?) > ------------------------------------- > > The SOR method wins again. The error from the Bezier method will get magnified > as we go from a 1-D curve to a surface. This error will probably not increase > as you increase the number of patches, since symmetry of the spherical > surface can be used. The SOR method is exact. True, the error will increase, but as noted above it is pretty small anyway. > 4) Polygonisation > -------------- > depending on how fine or coarse your net needs to be. Both methods can generate a polygonal mesh, no problem. The key here is the coarseness of the mesh. The REYES approach ensures that you can make fine meshes on _small_ patches. > 5) Bounding boxes > -------------- > I have no idea whatsoever. Its not straightforward for the SOR, but it could be simplified if the splits were done carefully. The Bezier patch lies within the convex-hull, so its bound is just the bound of the control polygon. > 6) Total code space > ---------------- > From the above points, the SOR approach will produce cleaner and shorter > code. > I'm not convinced it produces either, but those things are hard for me to judge without really doing it. When I started this reply, I thought that the SOR wouldn't fit at all with the REYES approach. Now my impression has improved. I think that Splitting would be trivial, but Bounding would be tricky (lots of special cases, nested if-then-elses, etc.) Dicing is also easy if you want to use sine/cosine, I DON'T. I would have to approximate the sin/cos in some way, and that is no longer exact. As for the Bezier; Splitting is reasonable, Bounding is almost trivial, and the Dicing can be done in a matrix form. (Dicing speed can be increased by using forward differencing.) And as I said in the beginning, I was going to implement Bezier patches anyway... Robert Skinner skinner@saturn.ucsc.edu