skinner@saturn.ucsc.edu (Robert Skinner) (03/17/88)
In the 1987 Siggraph article on the REYES architecture, Cook, Carpenter & Catmull state that a sphere can be defined by 32 patches. They give Computational Geometry for Design and Manufacture, by Faux and Pratt, as the reference. For some reason, I can't find anything in F&P that says how to do this. The closest I get is a formula for a Bezier CURVE that is very close to a circular arc of 90 degrees. Starting with that, I can define 3 of the Bezier boundaries as great arcs on the sphere and the fourth is a point at the pole. This still leaves the center 4 points of patch undefined. Besides that, this would only use 8 patches. So I suspect that this has more error than using 32 patches. Can someone point out where in F&P this info is encoded? Better yet, if you've worked it out already, can you post the patch definition of the sphere? (Only 4 patches need to be defined from symetry (sp)) aTdHvAaNnKcSe ------------- Robert Skinner skinner%saturn.ucsc.edu@ucscc.ucsc.edu
efo@pixar.UUCP (efo) (03/22/88)
In article <2390@saturn.ucsc.edu>, skinner@saturn.ucsc.edu (Robert Skinner) writes: > In the 1987 Siggraph article on the REYES architecture, Cook, Carpenter > & Catmull state that a sphere can be defined by 32 patches. They give > > The closest I get is a formula for a Bezier CURVE that is very close > to a circular arc of 90 degrees. Starting with that, I can define 3 > of the Bezier boundaries as great arcs on the sphere and the fourth is > a point at the pole. This still leaves the center 4 points of patch > undefined. Besides that, this would only use 8 patches. So I suspect If you have a 2d Bezier curve that approximates a circular arc, you have enough information to fabricate a chunk of a sphere. Since you have the location of the tangent (internal) control points at each end of the curve, you of course have the edges of the patch defined nicely. Let me label the points in one patch: 00 01 02 03 10 11 12 13 20 21 22 23 30 31 32 33 You're still missing points 11, 12, 21, and 23. However, you also know how this patch must attach to its neighbor. Suppose points 00-03 are at the pole and 30-33 are on the equator. Points 22,23,32,and 33 all must lie on the plane tangent to the sphere at point 33. This plane also passes through points 20,21,30,and 31 of the patch to our patch's "right", and similarly for the patch below and below-and-to-the-right of this patch. Since points 22,23, and point 21 of the patch to our right must be collinear, and similarly for 22, 32, and 12 of the patch below us, we can choose point 22 to be point 23 + point 32 - 2*(point 33). You will also find that point 12 is not so hard to pick. If you say that the n.pole is on the positive z axis, and the equator lies on the xy plane, you can pick point 12 such that points 12, 13 and 11-of-the patch to your right are collinear and the projection on the xy plane of points 02, 12, 22, and 32 are collinear. Note that the tangent of the point (x,y) on a circle is (-y, x) (that is, has slope -y/x) and maybe this will become clearer. You can do this with arcs of less than 90 degrees and you get correspondingly closer to a true sphere. Eben Ostby / Pixar
efo@pixar.UUCP (efo) (03/23/88)
Mr. Robert Reed has noted that there is a typo in my posting. The unknown points are 11, 12, 21, and 22.
rustcat@csli.STANFORD.EDU (Vallury Prabhakar) (03/29/88)
It seems to me that using Bezier patches to generate a spherical surface is a rather inefficient method. A sphere can easily be generated as a surface of revolution. Simply rotate a circular arc about an axis. The arc itself can be generated using Bezier or any other parametric cubic approximation. I think Michael Mortenson discusses this in his book "Geometric Modelling". -- Vallury Prabhakar -- rustcat@cnc-sun.stanford.edu
jmd@granite.dec.com (John Danskin) (03/30/88)
In article <3150@csli.STANFORD.EDU> rustcat@csli.UUCP (Vallury Prabhakar) writes: > >It seems to me that using Bezier patches to generate a spherical surface >is a rather inefficient method. A sphere can easily be generated as a >surface of revolution. Simply rotate a circular arc about an axis. The >arc itself can be generated using Bezier or any other parametric cubic >approximation. I think Michael Mortenson discusses this in his book >"Geometric Modelling". > > -- Vallury Prabhakar > -- rustcat@cnc-sun.stanford.edu Ah, but what if your modeler only supports Beziers? And, what do you mean by more efficient? o Takes up less space o Easier to do ray surface intersections o Easier to tesselate into polygons on the fly o Better numerical characteristics o Bounding box generations on subsets of the sphere are easier o Your sphere modeler needs less total code space Since you don't win on all of these measures, your posting would be more helpful if you were more specific. -- John Danskin | decwrl!jmd DEC Workstation Systems Engineering | (415)853-6724 100 Hamilton Avenue | My comments are my own. Palo Alto, CA 94306 | I do not speak for DEC.
rustcat@csli.STANFORD.EDU (Vallury Prabhakar) (03/30/88)
In article <209@granite.dec.com> jmd@granite.UUCP (John Danskin) writes:
# Ah, but what if your modeler only supports Beziers? And, what do you mean
# by more efficient?
#
# o Takes up less space
# o Easier to do ray surface intersections
# o Easier to tesselate into polygons on the fly
# o Better numerical characteristics
# o Bounding box generations on subsets of the sphere are easier
# o Your sphere modeler needs less total code space
#
#
# Since you don't win on all of these measures, your posting would be more
# helpful if you were more specific.
This is true. I was speaking strictly from a modelling point of view.
Sorry for not being more specific.
Of course if you modeller can produce only Bezier approximations, then there
is nothing to discuss here, is there?
1) Space
-----
I haven't tried it, but it seems to me that the surface of revolution method
would win over the Bezier approach in terms of computational efficiency.
Consider the Bezier method. Assuming that you're using a bicubic representa-
tion, you will need a 4 x 4 matrix for each of the geometric matrices Bx, By
and Bz. That makes it 3 matrices of order 4 at least. 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.
2) Ray surface intersections
-------------------------
I'm not too familiar with shading in computer graphics. I was speaking
strictly from a modelling point of view. However I assume that these
ray-surface intersections will be necessary for shading and probably hidden
line removal computations. Once again, I think the surface of revolution
approach (SOR) is better. You've got (at least) 4 patches in the Bezier
approximation to deal with and the algorithm will be messy. In the SOR
method, you can easily determine whether and where the ray will intersect
the surface. In general, the properties of the surface in the SOR method
are simpler to calculate. Also, (I think) calculations of reflected light
etc., for shading involve trignometric functions and this would be in the
spirit of the SOR method. Or rather, vice versa.
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.
4) Polygonisation
--------------
The Bezier approach is probably better with reference to the characteristic
Bezier polygon. After all, the basic method of generating the surface is
via these characteristic polygons. On the other hand, if you need to have
polygons that are different from the above then I don't see how either
approach is better. A polygon can be generated as a patch in the SOR method
by considering small ranges of the two characteristic angles, but generating
patches over the entire surface will take time, depending on how fine or
coarse your net needs to be. I don't know which approach would be faster.
5) Bounding boxes
--------------
I have no idea whatsoever.
6) Total code space
----------------
From the above points, the SOR approach will produce cleaner and shorter
code.
For all of the above reasons, I think that the SOR approach is a more
"efficient" method of generating a spherical surface.
-- Vallury Prabhakar
-- rustcat@cnc-sun.stanford.eduskinner@saturn.ucsc.edu (Robert Skinner) (03/31/88)
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
jcobb@utah-gr.UUCP (Jim Cobb) (04/02/88)
It is impossible to exactly parametrize a sphere with polynomial
patches. I will describe here a simple rational quadratic Bezier patch
that IS exact. This patch covers an octant of the sphere.
Let sq = sqrt(2)/2. Define homogeneous control points P_ij as
P_00 = [ 0 0 -1 1 ]
P_01 = [ sq 0 -sq sq ]
P_02 = [ 1 0 0 1 ]
P_10 = [ 0 0 -sq sq ]
P_11 = [ 0.5 0.5 -0.5 0.5 ]
P_12 = [ sq sq 0 sq ]
P_20 = [ 0 0 -1 1 ]
P_21 = [ 0 sq -sq sq ]
P_22 = [ 0 1 0 1 ]
A note about the interpretation of these coefficients: There are two
conflicting conventions for the meaning of control points for a rational
Bezier curve or surface. I am using the convention that denotes the
components of the points as [ X Y Z W ], with resulting surface
evaluation given by
sum [X_ij Y_ij Z_ij] theta_i(u) theta_j(v)
S( u, v ) = ------------------------------------------
sum W_ij theta_i(u) theta_j(v)
There is a slight problem with this parametrization: the patch is
degenerate along one of its edges (an entire edge curve collapses into a
single point). There are alternative schemes to avoid this difficulty,
and there are ways of dealing with the degeneracy (see Faux & Pratt p.
235 ff.).
Jimefo@pixar.UUCP (efo) (04/02/88)
In article <3183@csli.STANFORD.EDU>, rustcat@csli.STANFORD.EDU (Vallury Prabhakar) writes: > In article <209@granite.dec.com> jmd@granite.UUCP (John Danskin) writes: > > # Ah, but what if your modeler only supports Beziers? And, what do you mean > # by more efficient? Thus begins an analysis of the relative merits of modelling using Bezier patches and surfaces of revolution. In defense of the original questioner, I should point out that there are plenty of reasons to want to define a sphere in terms of Bezier patches. For instance, as Danskin mentions, your modeller may support only Beziers. Better yet, your renderer may support only Beziers. Since the Bezier is a pretty general surface (other patches may be better, eg, nurbs) you can create an entire renderer which knows only Beziers. This may (or may not) make your renderer considerably simpler than one which supports a range of other surfaces -- surfaces of revolution, for instance, would be of little use in modelling rectilinear things or bendy-twisty things. You can turn all manner of higher level primitives into patches as a prepass to rendering. This method of abstraction may be very useful in the modelling-rendering paradigm. However, if you're not interested in the rendering phase a different division of labor might be useful. More interesting is what you might be able to do with a sphere modelled as patches. For instance, you might wish to use your Bezier patch sphere as raw data to be manipulated. You might be trying to construct something quite unlike a sphere in the end, but the sphere data is a useful starting point. In this case, the ability to turn a variety of things into patches and then mung up the patches and push them together might be an interesting way to model stuff. For strict efficiency's sake, there are many places where Prabhakar's arguments are the limiting ones. Regards - Eben Ostby