View Full Version : NURBS and Tracking algorithms

Joe Drumm
04-05-2005, 11:25 AM

I've been programming in C++ for about 12 or so years, but mainly in areas other then computer graphics. Anyway, lately I've been playing around in my free time with some graphics programming lately (has always interested me, but never did much more then draw and rotate a cube on my Amiga back in the day) and am interested in being able to display and interact with b-splines. What I'm looking for is an interactive way for the user to click points and have the curve build up, for example the way it works in some applications such as Commotion, Combustion, AfterEffects, Photoshop, etc. Can anyone point me in the right direction where I could find some information on the algorithms behind this? I have come across some the of the math, and while I can follow some of it, I'm no math expert. I'm looking for something more oriented to a programmer with some code examples or something that explains the math in a bit more down to earth level. The rest of the application I can handle no problem, but it's the rendering of the b-splines that I'm stuck on.

Also, out of curiousity, I am interested in reading about the techniques behind image morphing as well a tracking (i.e. tracker in combustion / after effects).

Thanks for any tips,


04-06-2005, 07:23 AM
For practical implementation advice on graphics topics, I generally find gamasutra to touch most topics, although sometimes they don't go too in-depth. They have an article on nurbs (http://www.gamasutra.com/features/19991117/macri_01.htm) that might be good (haven't actually read it), although they require a free registration. It looks like they have sample code.
In terms of your problem, I think the main question is whether you're looking to place points on the curve, or the actual control vertices of the curve. If you're just looking to place the CVs, it's a matter of converting from mouse space to world space, then drawing. For drawing, if you're using openGL, you can take advantage of openGL evaluators, which take in data for a Nurbs and do all the rendering for you - it's pretty nice. The openGL red book is a good place to start - they have a Nurbs rendering example (http://fly.cc.fer.hr/~unreal/theredbook/chapter11.html) in chapter 11. If the link I posted ever stops working, a google for "openGL red book" will generally turn up several copies across the web.

In case you're interested, most of my experience comes from a class I took in college - the textbook is available (http://tom.cs.byu.edu/~557/) online - I think chapter 5 covers Nurbs. Looking at how other places teach the theory, I'm really glad I learned using knot intervals and polar labels rather than tackling the recursive blending functions right off the bat.

04-06-2005, 07:35 AM
I forgot to mention, I worked on an automatic morphing program for a while. Generating the morph was actually pretty easy, it was find the correspondences that was trickier, which was the part we were trying to automate.

Different morphing programs use different algorithms, but in general the actual morph is composed of two parts:
- A warp of one image to the other
- A cross-fade of the warped pixel colors from one image to the other

For our program, we used a triangle mesh, where each vertex had two positions, one for each image in the morph. We used a parameter value t, which went from 0 to 1, respectively the start image to the end image. We would do a linear interpolation of the positions of both meshes. In other words, the warped vertex position at t,
vt = v0*(1-t) + v1*t.
We texture mapped the rendering from the original images, and did it in two passes - first, we'd render image 0 with full alpha, and then render image 1 with an alpha of t. This will give you a proper morph.

As for tracking, I'd google for "optical flow", which is probably the technique they use. It's fast and doesn't suck too much.

CGTalk Moderation
04-06-2005, 07:35 AM
This thread has been automatically closed as it remained inactive for 12 months. If you wish to continue the discussion, please create a new thread in the appropriate forum.