Software Fragments

A Very Simple OpenGL Scenegraph Parser TOGL-distrib-pc.zip TOGL-distrib-mac.zip This zip contains a small program which requires only GLUT and OpenGL. To help people who use windows I have included GLUT for windows and a precompiled version. This program is only useful for teaching. It parses a very simple scenegraph file format which is similar to VRML but much simpler. There are several demo files for your perusal. Surprisingly, there is also documentation Even more surprising may be that there are exercises exercise.txt The point of the whole thing is that without any programming, just by messing with a simple text file containing graphics commands, you can learn about hierarchical transformations, shading and perspective. If you find it useful, please let me know. It was written as an exercise in computer graphics for the DADIU joint curriculum teaching. CGLA (Computer Graphics Linear Algebra) Is a set of numerical C++ vector and matrix classes and class templates designed with computer graphics in mind.

Why another linear algebra package? Like so much software, CGLA was created to scratch an itch. CGLA evolved from a few matrix and vector classes because I didn't have anything better. However, CGLA does have one probably unique feature, namely the fact that all vector types are derived from the same template: This makes it easy to ensure identical semantics. CGLA was designed for Computer Graphics - not numerical computations, and this had a few design implications: CGLA is designed only for vectors of small dimensionality (2,3 and 4D vectors mainly) CGLA is designed to be reasonably fast: No dynamic memory is used. No virtual functions are used. Most functions are inline. Of course, other libraries of vector templates for computer graphics exist, but to my knowledge none where the fundamental templates are parametrized w.r.t. dimension as well as type. In other words, we have a template (ArithVec)that gets both type (e.g. float) and dimension (e.g. 3) as arguments. the intended use of this template is as ancestor of concrete types such as Vec3f - a 3D floating point type. The use of just one template as basis is very important, I believe, since it makes it extremely simple to add new types of vectors. Another very generic template is ArithMat which is a template for matrix classes. (and not necessarily NxN matrices).

Features of CGLA Class Template for arithmetic vectors of arbitrary type and dimension. Class Template for arithmetic matrices of arbitrary type and dimension (NxM). A number of 2, 3 and 4 d vector classes. A number of Matrix classes. A Quaternion class. Some test programs. Works well with OpenGL.

Download CGLA reference CGLA-25082003.tgz and mail feedback to jab 'at' imm.dtu.dk.

Comments and disclaimers I find these classes and templates very useful, but they do represent work in progress. Also, I do not simply add a feature to all classes because it might come in handy one day. This (hopefully) makes the code less buggy but also less complete. I have not included support for expression templates, because that technique adds an incredible amount of complexity to the source. Also, I believe that the performance gain is small when one compares to expressions that are rewritten using assignment operators. There is more about the ET technique elsewhere on this page.

kD Trees

kD Trees are a well known data structure for finding the point closest to some given point or for finding a set of points in some range. kD Trees are very useful in many places. In computer graphics, kD Trees are used, for instance, in Photon Mapping. This is just my implementation. There are others, and some may balance the tree correctly, but I have not found any documents describing the left balancing in detail - they do exist but not electronically or only somewhere where I cannot find them. What I mean by correct left balancing is as follows. A balanced k-d tree with N nodes can be stored in an array of dimension N+1 so that the root is in element 1 and the children of the node in element i are 2*i and 2*i+1. This is compact, cache efficient and the traversal is efficient. A document describing how to balance in this fashion is found here. If there are other on-line resources describing this balancing, I'd be interested in pointers. The algorithm is homegrown but the idea is due to Henrik Wann Jensen. (The code for his kD Tree is in his book "Realistic Image Synthesis Using Photon Mapping".) My own implementation which is a KD Tree template is found below. Note that it is based on CGLA Download Get: kdtree.tgz

NVIDIA DEMO this is a demo showing how to use the agp memory for fast dma transfer of geometry from main memory to the graphics board. This demo is probably of interest only if you have (1) a pc with an NVIDIA based board and (2) run linux.

Download nvtest.tgz The README.1st is a shell script that does final unpacking and installation, but it is perhaps a bit too automatic and you probably need to plug the right compiler path into Makefile.global (a vi with this file automatically pops up). You may also have to edit the Makefile in the directory of the actual program soruce file. Not all the source files are relevant since my code tree is maybe a little bit too coarse grained. Finally note that you need a more recent glext.h than the one redhat provides with 6.2 and 7.0. I am too lazy to solve the above problems, but to a Linux user this demo is still a more useful example of the DMA stuff than the learning_VAR program NVIDIA has made public :)

X-Splines X-Splines are an alternative to traditional splines that was introduced by Carole Blanc and Christophe Schlick in 1995.

Theory XSplines have the very nice property that they can interpolate (go through) a control point as well as just approximate it. Sharp edges are also possible,  but the curve is always C2 continuous, hence the sharp edges are only possible when the first derivative drops to zero. (There are basic, extended and general X-Splines. The discussion below regards general X-Splines ... the most general form) An X-Spline is completely defined by a set of control point (vertices) and a set of parameters. One parameter sk is associated with each control point vk. The parameter sk lies in the interval [-1,1]. For sk=1 the curve only approximates the control point and if all sk are 1 the X-Spline corresponds closely to a cubic, uniform B-Spline. When the parameter drops to zero, the first derivative becomes 0 (and - according to the article from Proceedings of Siggraph '95 also the second derivative, although I don't see how this is possible) which allows for a sharp bend. So, for sk=0 the curve interpolates the control point, but - unless three control points are alignes - there is a sharp edge. When the parameter becomes negative, the curve still interpolates vk, but in more geometrically continuous way. For sk=-1 the XSplines are very similar to cubic Catmull-Rom splines. In the downloadable demo, you can move the control points by dragging and dropping, and you can control the corresponding parameters with the `+´ and `-´ keys. `esc' quits. The demo requires OpenGL and GLUT.

Download Get: xsplines.tgz  or  xsplines.zip

Expression templates

The really complicated idea Expression templates were introduced by several people, most notably Todd Veldhuizen. The purpose of expression templates is to bring down the overhead that is otherwise paid as ``the price'' of the higher level of abstraction in C++. For instance, vector algebra is usually slower in C++ than in C because an operation like Vector V3 = V0 + V1 + V2; is really computed in the following way: Vector tmp0 = V1 + V2; Vector tmp1 = V0 + tmp0; Vector V3(tmp1); If we use expression templates, the + operator for two Vectors does not return a new vector but an instantiation of a template for binary expressions. Another + operator, then, must accept this template together with a vector to produce a new instantiation of the binary expression template. To sum up: An expression produces an object of a very complex type which represents the expression. This object has a tree structure, and it is possible to traverse this tree for each vector index and compute the value separately. The neat thing is that, although there are also temporary objects using this scheme, the expression template nodes tend to be smaller than the vectors themselves, and they don't use dynamic memory. This means that the constructor call overhead incurred by the building of the expression template tree is negligible compared to the fact that there are no temporary Vector objects. The not-so-neat thing is that this only holds for big vector classes with lots of overhead. I tried implementing the technique for my own nimble 2, 3 and 4D vectors, but it turned out to be counterproductive. In hindsight, this is pretty obvious! (...) Or so I thought. Recently, Jim Blinn has implemented 3D vector operations using expression templates, and he claims to get a very nice speedup. The thing that makes the difference is whether the expressions contain pointers to sub expressions or copies. His expressions contain copies of sub expresssions - except if the subexpression is, in fact a vector. In this case it is just referenced. I am still not so sure it is a good thing to use that scheme. We can get nearly the same efficiency using assignment operators, and ETs do add a great deal of complexity. Furthermore, I am not convinced that the scheme implemented by Blinn might not have problems with temporaries that suddenly vanish if an operand is really a temp vector returned by a function. I am not sure about that though, so read his installment called ``Optimizing C++ Vector Expressions'' in Jim Blinn's corner - Computer Graphics & Applications July/August 2000.

Download Anyway, for my own edification, I wrote a small example expression_templates.cc which is probably easier to understand than the available libraries that implement the techniques. It implements 1D vectors using expression templates. Of course, this is useful ONLY for gleaning the technique. For more information on this technique see Todd Veldhuizen's homepage.

Wavelets

A Simple Program I will not explain what wavelets are ... that is entirely beyond the scope of this page. I have written a very simple program to convert an image into wavelet coefficients. It is also possible to convert the other way. Also the program can be instructed to keep only a specified fraction of the coefficients. The main (only) advantage of this program is that it is less than 400 lines of C++. This is more manageable than what I have seen elsewhere. On the other hand the program is only useful for learning the technique. To see a comparison of Haar and 7-5 wavelets click here Download Get: wavelet.tgz

Maintained by: Andreas Bærentzen, jab 'at' imm.dtu.dk Last modified: Tue Aug 26 11:14:48 CEST 2003