Discuss and collaborate on GML scripts

You are not logged in.

- Topics: Active | Unanswered

Pages: **1**

**xot****Administrator**- Registered: 2007-08-18
- Posts: 1,240

I've been working on some new graphic trick ideas and I wanted a moderately complex model to test them. I toyed with the idea of making a model in LightWave3D and writing a converter to make a version compatible with GM's d3d_model_load. I've done that sort of thing before for other platforms but I wasn't really relishing the idea of building a general purpose LW3D model parser again. The only reason I considered it is because I'd recently seen this old Beethoven bust model used to test SGI hardware and remembered that I had the model in my LW3D collection and thought it might work for what I needed.

Another image I'd seen on that same webpage was the iconic Utah Teapot, a much more suitable shape. It's become a fetish object for graphics folk like me, a Wilhelm scream for the CGI set, always popping up. It's something I've always wanted to render myself. Many years ago I got my hands on the data but the implementation was beyond my reach.

Last night during some Googling on the teapot I stumbled onto a webpage devoted to its history. It made me realize that I'd seen this same teapot over and over again for more than 20 years and I really didn't know anything about it except its obscure name. I never knew there was a real teapot that it was modelled on, or that the version seen today was apparently squashed to better match the aspect ratio of the monitor it was displayed on. I found it all extremely interesting, and what's more, on the new found webpage was the long lost data. Here was a second chance to bring the teapot to life.

The data are a list of vertices and a group of Bézier patches. The patches are defined by 16 control points indexed to the list of vertices. The geometry is incomplete. It's up to the implementor to mirror the patches across one or two axes to complete the model.

It wasn't long before I had a basic wire rendering of the control mesh, soon followed by solid rendering. Evaluating the patches required a bit more work. I've never worked with spline surfaces outside of a 3D modelling program, and I've never worked with Bézier curves in code. I had some experience with Catmull-Rom splines, so calculating a cubic curve wasn't completely alien to me. First I had to wrap my brain around a way to evaluate a surface rather than a curve, which is what I went to bed last night thinking about as I drowsily jotted down some pseudocode before passing out.

Today when I got the chance to start working on it, it all just clicked. I soon had the patch builder done but I still didn't have a way to evaluate a Bézier curve, just a stub function. I plugged in my Catmull-Rom script instead. The differences between these two types of splines are significant, so the result was pretty far off, but I could see right away that it was working. Even with my meager math skills I was able to find the relevant formula on Wikipedia and soon I had a cubic Bézier function. I switched it in and it worked perfectly. It's such an amazing feeling when code works correctly the first time. It was doubly sweet because I was now looking at something I've been longing to have under my control for what seems like a lifetime.

*Abusing forum power since 1986.*

Offline

**xot****Administrator**- Registered: 2007-08-18
- Posts: 1,240

I'm starting to get a little frustrated now. It's no secret I have really spotty math abilities. Now I need a crash-course in calculus.

The goal: Find the surface normal for any point on a Bézier surface.

The method: Derive a pair of tangents vectors at the point (and then perform a cross product of them to compute the orthogonal).

The problem: I have no idea what I just said.

I tried to adapt some existing code I found on GameDev.net, but I couldn't get it working quite right. Its been highly optimized and is not a general solution so it's a little hard to follow. Since I don't understand how to derive a function, it makes even less sense to me.

HALP! Where is "Calculus for Dummies" when I need it???

*Abusing forum power since 1986.*

Offline

**icuurd12b42****Member**- Registered: 2008-12-11
- Posts: 303

It's right here

Spend a few hours watching, lights will turn on, garanteed.

Offline

**xDanielx****Member**- Registered: 2009-01-02
- Posts: 38

I'll try my hand at an explanation. I don't know too much about your background, so I'm probably assuming much less than I could... but perhaps someone else will benefit from the basic overview.

In single variable calculus, we do all kinds of things with functions in 2D space by treating them as if they were made up of (infinitely) many of straight lines. We can do the same thing with a 3D object by thinking of it as a bunch of tiny polygons. Think of taking a rigid mesh in a traditional modeler and smoothing it more and more until the polygons are so small that the model might as well be continuous.

When we're shading a vertex, we really want to know the orientation of one of the tiny polygons in the neighborhood of that vertex. (For those not familiar with the physics, the shader needs to know the angle of incidence -- that is, the angle at which light hits the surface -- to compute how much light is emitted.)

But since we're not actually storing these tiny polygons in memory, we don't actually give the shader a polygon. Planes are nice simple objects, so instead we give the shader a description of a plane which has the same orientation as the tiny polygons near our vertex. This is called the tangent plane, and is illustrated below:

There are different ways of describing a plane -- we could list three distinct points on it, for example -- but for most purposes we want a normal (aka orthogonal) vector. Orthogonality between vectors and planes is essentially like perpendicularity between lines, we just generalize the concept by adding a dimension.

So for shading a vertex, we want the vector that's normal to our surface at that point, as this vector describes the tangent plane which describes the direction of the surface at that particular point. How then do we compute the normal vector?

One fairly general approach to computing normal vectors involves finding partial derivatives. These are just multivariable calculus's generalized version of simple derivatives. If we have a single variable function [tex]f(x)[/tex], the derivative [tex]\frac{df}{dx}[/tex] describes how f varies with respect to x (the slope of f in a plot of f against x). Given some multivariable function [tex]f(x,y)[/tex], the partial derivative [tex]\frac{\partial f}{\partial x}[/tex] describes how f varies with respect to x, while [tex]\frac{\partial f}{\partial y}[/tex] describes how f varies with respect to y. Note that the partial derivates may potentially still have x and/or y terms, just as the slope of a single-variable function might depend on where we are on the curve.

Given a surface function [tex]f(x,y)[/tex], we are usually interested in the partial derivative for some particular (x, y) (compare to the slope of a single-variable function at a particular x). Say we want to find [tex]\frac{\partial f}{\partial x}[/tex]. This is really another function of x and y, but we might want to evaluate it at (x=a, y=b). Since we're only interested in a particular y value, we can take the cross section of the surface with respect to the plane y=b. Algebraically, this like like substituting b for y in the equation for f. (We can't do this with x yet because we are differentiating f with respect to x.) Now we are left with a simple two-dimensional curve, of which we can easily find the slope at (x=a). This is illustrated below:

Notice that the black line, whose slope is [tex]\frac{\partial f}{\partial x}(a,b)[/tex], is tangent to the surface at (a, b). If we also compute [tex]\frac{\partial f}{\partial y}[/tex], we will get a second vector tangent to the surface at (a, b).

Now, let's accept without proof that the cross product of any two vectors, [tex]u \times v[/tex], yields a third vector which is orthogonal (informally, "perpendicular") to both u and v. Say we need to shade the vertex (x=a, y=b). Since [tex]\frac{\partial f}{\partial x}(a, b)[/tex] and [tex]\frac{\partial f}{\partial y}(a, b)[/tex] are both tangent to the surface f at (a, b), their cross product must be normal to the surface at (a, b). And this normal vector describes the tangent plane at (a, b), which describes the "direction" of the surface at (a, b), which is what the shader needs.

Now let's talk about Bézier surfaces specifically. We can describe a Bézier surface as

[tex]f(u, v) = \sum_{i=0}^n \sum_{j=0}^m B_i^n(u) \; B_j^m(v) \; P_{i,j},[/tex]

where

[tex]B_i^n(u) = {n \choose i} \; u^i (1-u)^{n-i}.[/tex]

We would like to find two partial derivatives; we can write the first one as

[tex]\frac{\partial f}{\partial u} = \frac{\partial}{\partial u} \left( \sum_{i=0}^n \sum_{j=0}^m B_i^n(u) \; B_j^m(v) \; P_{i,j} \right)[/tex]

From here we must apply some rules of calculus, which I assert without proof. First, the derivative of a sum is the sum of the derivatives. This is usually stated as

[tex]\frac{\partial (f + g)}{\partial x} = \frac{\partial f}{\partial x} + \frac{\partial g}{\partial x},[/tex]

but it holds for sums in general. So,

[tex]\frac{\partial f}{\partial u} = \sum_{i=0}^n \sum_{j=0}^m \frac{\partial}{\partial u} \left( B_i^n(u) \; B_j^m(v) \; P_{i,j} \right)[/tex]

Next, the derivative of a scaled function is the scaled derivative of that function, i.e.,

[tex]\frac{\partial (c f)}{\partial x} = c \frac{\partial f}{\partial x}[/tex]

Thus we can "bring out" constant multipliers. More generally, if we're differentiating with respect to u, we can "bring out" any terms which have no u dependence. Conceptually, this makes sense since when we partially differentiate a function with respect to u, we are only interested in its u dependence; unrelated variables might as well be constant. Thus we have

[tex]\frac{\partial f}{\partial u} = \sum_{i=0}^n \sum_{j=0}^m B_j^m(v) \; P_{i,j} \; \frac{\partial}{\partial u} ( B_i^n(u) )[/tex]

[tex]= \sum_{i=0}^n \sum_{j=0}^m B_j^m(v) \; P_{i,j} \; \frac{\partial}{\partial u} \; \left( {n \choose i} u^i (1-u)^{n-i} \right)[/tex]

To deal with the exponents, we must combine the power rule,

[tex]\frac{\partial (x^n)}{\partial x} = n x^{n-1},[/tex]

with the product rule,

[tex]\frac{\partial}{\partial x}(f g) = f \frac{\partial g}{\partial x} + g \frac{\partial f}{\partial x},[/tex]

and the chain rule, which we use to use to differentiate "chains" of functions:

[tex]\frac{\partial y}{\partial x} = \frac{\partial y}{\partial u} \frac{\partial u}{\partial x}.[/tex]

If these rules are unfamiliar, you might want to read about them elsewhere (unless you're just interested in the result).

Applying these rules yields

[tex]\frac{\partial f}{\partial u} = \sum_{i=0}^n \sum_{j=0}^m B_j^m(v) \; P_{i,j} \; \left(\frac{n!}{i! \; (n-i)!}\right) \left( i \; u^{i-1} \; (1-u)^{n-i} - (n-i) \; u^i \; (1-u)^{n-i-1} \right)[/tex]

[tex]= \sum_{i=0}^n \sum_{j=0}^m B_j^m(v) \; P_{i,j} \; \left( \frac{n! \; i \; u^{i-1} \; (1-u)^{n-i}}{i! \; (n-i)!} - \frac{n! \; (n-i) \; u^i \; (1-u)^{n-i-1}}{i! \; (n-i)!} \right)[/tex]

[tex]= \sum_{i=0}^n \sum_{j=0}^m B_j^m(v) \; P_{i,j} \; n \; \left( \frac{(n-1)! \; i \; u^{i-1} \; (1-u)^{n-i}}{i \; (i-1)! \; (n-i)!} - \frac{(n-1)! \; (n-i) \; u^i \; (1-u)^{n-i-1}}{i! \; (n-i) \; (n-i-1)!} \right)[/tex]

[tex]= \sum_{i=0}^n \sum_{j=0}^m B_j^m(v) \; P_{i,j} \; n \; \left( {n-1 \choose i-1} u^{i-1} \; (1-u)^{n-i} - {n-1 \choose i} u^i \; (1-u)^{n-i-1} \right)[/tex]

[tex]= \sum_{i=0}^n \sum_{j=0}^m B_j^m(v) \; P_{i,j} \; n \; \left( B_{i-1}^{n-1}(u) - B_i^{n-1}(u) \right).[/tex]

By the same process, we find that

[tex]\frac{\partial f}{\partial v} = \sum_{i=0}^n \sum_{j=0}^m B_i^n(u) \; P_{i,j} \; m \; \left( B_{j-1}^{m-1}(v) - B_j^{m-1}(v) \right).[/tex]

So, a vector normal to the surface at (u=a, v=b) is given by

[tex]\textbf{n} = \frac{\partial f}{\partial u} \times \frac{\partial f}{\partial v} = \left( \sum_{i=0}^n \sum_{j=0}^m B_j^m(v) \; P_{i,j} \; n \; \left( B_{i-1}^{n-1}(u) - B_i^{n-1}(u) \right) \right) \; \times \; \left( \sum_{i=0}^n \sum_{j=0}^m B_i^n(u) \; P_{i,j} \; m \; \left( B_{j-1}^{m-1}(v) - B_j^{m-1}(v) \right) \right)[/tex]

I suspect that this could be simplified a bit with some more combinatorics, but it's about my bedtime. I hope this is helpful to someone.

*Last edited by xDanielx (2009-12-04 07:16:44)*

Offline

**RaiSoleil****Member**- Registered: 2009-08-02
- Posts: 16

Try these two pages. http://home.scarlet.be/piet.verplancken … ode17.html and http://home.scarlet.be/piet.verplancken … ode19.html

Offline

**xot****Administrator**- Registered: 2007-08-18
- Posts: 1,240

Don't mind me. I'm just scraping up the bits of brain matter that have been blasted through the back of my skull.

A lot to absorb here. I'm sure I'll have questions very soon. Thanks for help, everybody.

*Abusing forum power since 1986.*

Offline

**xot****Administrator**- Registered: 2007-08-18
- Posts: 1,240

I've been going through some of the videos icuurd12b42 suggested. I'm actually going through Algebra first because there is a lot I've forgotten. The videos are pretty helpful, although the errors are annoying. These were matrices examples, where mistakes are easy to make. I hope the others are a little more error-free.

I also managed to get the code I adapted to work but I think the original must be bugged. It goes screwy in the corners. Fixing it should be a good exercise.

*Abusing forum power since 1986.*

Offline

**xot****Administrator**- Registered: 2007-08-18
- Posts: 1,240

I figured out what I was doing wrong. I knew I shouldn't have called someone else's code bugged when I don't know what I'm doing myself. The code seems fine. The problem was passing it a matrix with rows and columns swapped. Now it works pretty good. The only remaining problem is places where an entire patch edge occupies a single point. This happens at the very top and bottom of the model. The normals I'm getting in these areas are pointing the wrong way causing blemishes in the shading.

*Abusing forum power since 1986.*

Offline

**xot****Administrator**- Registered: 2007-08-18
- Posts: 1,240

I just learned that this teapot is has been continuously manufactured since 1954 and you can still get them from Friesland.

*Abusing forum power since 1986.*

Offline

Pages: **1**