Software Fragments 
This page is for little pieces of software that I wrote because
I needed them or needed to learn something. the only substantial
piece of software is CGLA which I use for each and every one
of my own projects.

A Very Simple OpenGL Scenegraph ParserTOGLdistribpc.zip 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 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:
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 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

DownloadCGLA referenceCGLA25082003.tgz and mail feedback to jab 'at' imm.dtu.dk. 
Comments and disclaimersI 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 kd 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 online 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
DownloadGet: kdtree.tgz

NVIDIA DEMOthis 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. 
DownloadThe 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 :) 
XSplinesXSplines are an alternative to traditional splines that was introduced by Carole Blanc and Christophe Schlick in 1995. 
TheoryXSplines 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 XSplines. The discussion below regards general XSplines ... the most general form) An XSpline 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 XSpline corresponds closely to a cubic, uniform BSpline. 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 CatmullRom 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. 
DownloadGet: xsplines.tgz
or xsplines.zip

Expression templates 
The really complicated ideaExpression 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 likeVector V3 = V0 + V1 + V2; is really computed in the following way:
Vector tmp0 = V1 + V2; 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 notsoneat 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.

DownloadAnyway, 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 ProgramI 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 75 wavelets click here DownloadGet: wavelet.tgz

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