Design Philosophy

The templatized geometry library's design is based on three mechanisms of the C++ language:
  1. templatization,
  2. inlining, and
  3. type definitions.
Together, these three mechanisms are used to achieve the goals described on the project's main page. The following sections describe in more detail how these mechanisms influenced the library's design.

Templatization

The C++ template mechanism offers compile-time genericity. In the context of a geometry library, this genericity is used in two ways: To allow geometry calculations in spaces of arbitrary dimensions, and of arbitrary underlying scalar field types. In other words, templatization is used to implement arbitrary vector spaces of the form Fn, where F is an algebraic field and n is a non-negative integer.

Dimension Genericity

A generic geometry library should provide data types and operations for n-dimensional geometry. This could be achieved in two ways:
  1. Make vectors, points etc. n-dimensional by storing dimension inside each object, and using dynamic data structures to store components.
  2. Templatize all data types and operations by vector space dimension.
The first alternative is typically easier to code, and usually easier to read, but has several serious drawbacks: The major drawback of the template approach is that vector space dimensions are fixed at compile-time. For example, writing a matrix calculator program that can handle matrices of arbitrary sizes is impossible using dimension-templatized data types. But in almost all geometry applications, vector spaces of different dimensions require code that differs so much anyways that fixed dimension of data types is not an issue.

Scalar Type Genericity

Apart from multiple dimensions, vector spaces can also differ in underlying scalar field type. Algebraically, a vector space can be defined over any field, i.e., an algebraic structure that follows the basic rules of arithmetics (addition, multiplication, distributive laws, etc.). Typical examples for fields are rational, real and complex numbers. Even though computer geometry is typically performed on floating-point numbers, scalar type genericity can still be very useful in many applications. Most applications would use the C++ double type to represent geometrical objects and perform operations at maximum accuracy. But sometimes an application has to store large numbers of geometric objects, e.g., millions of valued points in a data visualization application. For such applications, it might be necessary to store these points using the C++ float type to save memory. Without scalar field genericity, it would then be necessary to either re-write all needed geometry operations for float-based points, or to convert all points back and forth during processing. With genericity, all operations can be performed directly on the stored points; all required operations are generated by the compiler as needed. On the other hand, if higher accuracy is needed for operations, points can be converted automatically: as long as elements of two scalar field types can be converted into each other, geometric objects based on those types can be converted as well. For example, a vector of floats can be implicitly converted to a vector of doubles (the reverse will probably generate a compiler warning), and a vector of doubles can be converted to a vector of complex numbers (the reverse does not work, since there is no conversion from complex numbers to type double).

The templatized geometry library is fully independent of scalar type. Even special-purpose user-defined data types can be used to construct geometric objects, as long as they follow the syntax and semantics of an algebraic field. The exact requirements for a scalar field data type are listed in the scalar field type requirements page.

Inlining

Type Definitions

One problem of using templatized data types - especially types templatized by several parameters - is to keep track of template parameters when creating generic operations based on those types, or when using templatized types in non-generic code. For example, assume a vector data type parametrized on scalar field type and dimension: 
template <class ScalarParam,int dimensionParam>
class Vector
	{
	/* ... */
	};
A generic function to calculate the dot product of two such vectors would have to be templatized by the same parameters, and have to look as follows: 
template <class ScalarParam,int dimensionParam>
ScalarParam dot(const Vector<ScalarParam,dimensionParam>& v1,
                const Vector<ScalarParam,dimensionParam>& v2)
	{
	ScalarParam result(0);
	for(int i=0;i<dimensionParam;++i)
		result+=v1[i]*v2[i];
	return result;
	}

Things start getting out of hand if several templatized data types have to interact. Assume a point type templatized on the same parameters as the vector type above, and a function that calculates the squared Euclidean distance between two points: 

template <class ScalarParam,int dimensionParam>
ScalarParam dist2(const Point<ScalarParam,dimensionParam>& p1,
                  const Point<ScalarParam,dimensionParam>& p2)
	{
	Vector<ScalarParam,dimensionParam> dist=p2-p1;
	return dot(dist,dist);
	}
The problem here is that only a specific vector type is "compatible" with the point type the function is called with; and if for some reason the explicit types used lose compatibility (due to code changes, partial updates, API changes etc.) the code might still work - due to implicit conversions provided by templatization - but might lose performance.

An approach to minimize the "viral" property of template parameters - a function that uses several templatized types with several template parameters each must be templatized by all parameters - is to use type definitions as shortcuts inside each templatized data type. For example, the actual vector data type used in the templatized geometry library looks like the following: 

template <class ScalarParam,int dimensionParam>
class Vector
	{
	public:
	typedef ScalarParam Scalar;
	static const int dimension=dimensionParam;
	/* ... */
	};
The typedef and static const int seem redundant, but with them using templatized types becomes much easier. The dot product function can now be written as: 
template <class VectorParam>
VectorParam::Scalar dot(const VectorParam& v1,const VectorParam& v2)
	{
	VectorParam::Scalar result(0);
	for(int i=0;i<VectorParam::dimension;++i)
		result+=v1[i]*v2[i];
	return result;
	}
Granted, this code snippet does not look much less complicated than the first one, but now the function is only templatized by a single parameter. The benefits become larger as functions become more complicated. Consider the following version of the squared distance function: 
template <class PointParam>
PointParam::Scalar dist2(const PointParam& p1,const PointParam& p2)
	{
	PointParam::Vector dist=p2-p1;
	return dot(dist,dist);
	}
The real point data type used in the templatized geometry library contains a type definition for the vector type it is compatible with; thus, a user does not have to know which exact type to use. This style of specifying generic types is a lot safer, especially when larger projects use several different versions of points, vectors etc. in different parts of the code. The templatized geometry library uses embedded type definitions extensively, to minimize the number of parameters any function using it has to be templatized by, and to ensure maximum compatibility if intermediate results of calculations are of a type a user does not have to know or care about.

Another benefit of this style of templatization is on a more semantic level. The templatized geometry library only contains vectors that are of the form Fn, where F is a field, and n is an integer dimension. The parameters for the first versions of the dot and dist2 functions reflected this. The second versions, however, are templatized by vector type. This means, if someone implemented a vector type that is not Fn, any functions not requiring the dimension parameter would still work. The second dot function is still too special, and should therefore be (and is) part of the vector type itself, but the second dist2 function is truly generic - it could as well be used to calculate the distance between two vectors in any Hilbert space.