Reason

The Squrf library is intended to provide a triangulated representation of an arbitrary three dimensional surface. Specifically, a procedurally generated one. There are alot of other libraries around for doing this, so why add another?

A particularly common method is to generate voxels (a 3D array of points which are either inside or outside the surface) and to generate a set of triangles which divide the inside from the outside. Algorithms for doing this include the infamous marching cubes, although there are several alternatives. Advantages of these approaches are that it can be done very fast, and the underlying data structure is easy to store and to modify, which together mean you can, for example, generate a landscape for a game and blow holes in it in real time. I do have some problems with it, however, not least of which being that the results are often ugly - even after several iterations of a smoothing algorithm the normals for calculating diffuse lighting etc are likely to be less than perfect.

The voxels themselves are generally an approximation to something else, however. If we give our algorithm knowledge of the underlying data from which the voxels were created, we should be able to obtain a much better normal, and possibly a much better approach to smoothing the results.

In Squrf the surface is defined as the points in space at which a continuous field is equal to zero (an iso-surface, infact). Once the initial set of triangles has been created, therefore, the smoothing algorithm and vertex normal generation can both be performed using the original field definitions, which results in much smoother looking surfaces. There is a price to pay for this - although reasonably fast, squrf is less appropriate to run-time changes than a purely voxel based solution, especially since the addition of more and more fields will slow the generation of triangles down, whereas with voxels, the speed will be more or less consistent - there is still only one data set to consider.

The other, far more justifiable reason for making this is because I felt like it. :p

Quick Start

Those looking for a quick start / crib / whatever could do worse than looking in the examples directory. You might also want to have a look at the cut and paste crib sheet.

Overview

Squrf basically consists of a set of C++ classes, some used for defining fields, and some for generating surfaces over them. These are kept fairly independent. New fields and new triangulation algorithms should both be easy to add without modifying existing code. Everything within Squrf is in the namespace 'squrf'.

Defining a field

There is a pure-virtual base class called 'Field'. This declares three functions: 'Strength', 'Gradient' and 'StrengthAndGradient'. The latter two both have empirical default implementations, but can be overridden by any field that can provide a better or faster alternative. The Strength function is not defined, and must be overridden by all field types. Generally, a positive strength is considered to be 'inside' the surface, and a negative strength is 'outside', but this is really open to interpretation - it depends on how the resulting triangles are used. They will be anti-clockwise as viewed from 'outside'. The gradient should set the rate of change of strength over distance, as a vector. The StrengthAndGradient function is provided because both are often required at once and there are some very obvious optimizations to be made in most cases.

Some basic fields are provided. For an example program which uses fields without generating surfaces over them, see squrf/examples/FieldExample.cpp. Note that most fields simply declare their data members public. This is not laziness, this is a design decision. Those with data which needs looking after declare it protected or private.

class FieldAmbient

This is a very simple field. It has a single data item called 'mStrength' and returns this for all points in space. The gradient is always 0,0,0.

class FieldSphere

This defines a sphere. Note that this is not defined as an inverse relationship to the radius, or anything similar, since the field would be too aggresive that way, in most cases. Nor is it defined with a step function, since that would not have a well behaved gradient, which would be a bad thing. It is defined instead using a sigmoid function.

class FieldPlane

A plane is defined as a normal vector and the distance to the origin along it. The field changes state with a sigmoid function, as per FieldSphere, as the plane is crossed.

class FieldCapsule

A capsule is a cylinder with rounded ends. In this case it is defined as a start point, end point, and radius.

class FieldTripsule

A tripsule is to a triangle what a capsule is to a line.

Capsules, Tripsules and Planes are demonstrated in squrf/examples/Geometry.cpp

class FieldNoise

This defines the field strength as a 3D perlin noise function.

There is an Init function also, which can be used to provide an alternative random number generator for the noise. By default, rand() is used.

class FieldUnion

This class contains pointers to a number of other fields, and implements the strength and gradient functions as the summation over all contained fields. Fields are added through the Add() function.

class FieldTranslate

This class translates other fields (a FieldSphere is always centered on the origin - use this class to move it). It is implemented as a decorator. Create the other field first, then set the mDecorates member of this to the address of that field, and set the mTranslation vector. Then, use this object in place of the original field when generating.

class FieldMatrix

This class transforms other fields by the matrix given. It can rotate, scale, and do anything else you can do with a matrix. It is implemented as a decorator. Create the other field first, then set the mDecorates member of this to the address of that field, and set the matrix using the SetMatrix function. Then, use this object in place of the original field when generating.

Examples of using translate and rotate are provided in squrf/examples/transform.cpp

class FieldTurbulence1

This field is a decorator for adding turbulence to other fields. It takes a direction vector along which the turbulence is applied. The turbulence function can be initialised in the same way as for FieldNoise.

class FieldTurbulence3

This field is a decorator for adding turbulence to other fields. Using this class is more or less equivalent to using 3 FieldTurbulence1 classes, each with an amplitude defined parallel to a different axis.

Turbulence is demonstrated in squrf/examples/Decorators.cpp

Generating a Surface

A surface is a set of triangles representing the iso-surface of a field. It is possible that many versions of this will be provided in the future, but for now only 'Tile' exists.

Tile

A Tile represents a volume of space. They are carefully designed such that two tiles which touch each other will have vertices that exactly line up, so that many small tiles can be rendered in the place of one large one, hence the name. This allows for easy culling of triangles in both rendering and collision detection, or whatever else it is you want your triangles for.

Usage is straight forward - after creating an instance of a field, and a Tile object, call 'Generate' on the Tile. The parameters are the field, the coordinates of the bottom/left/near corner, the coordinates of the top/right/far corner, and a resolution as a float. The coordinates are given as integers, which will be multiplied by the resolution to get the actual coordinates. A resolution of 1 will result in approximately 1 vertex per unit-cube of the fields surface. To combine multiple fields, use the FieldUnion class.

The Tile class provides functions for obtaining the vertex, normal and index arrays, in the form of arrays of floats and ints.

For an example of using a Tile, see squrf/examples/TileExample.cpp. For an example of multiple tiles joined together, see squrf/examples/Tiles.cpp.

For examples of surfaces which changes over time, at the moment using brute force and regenerating the entire surface every frame, see 'Bounce' and 'Fourd'. Bounce is a number of spherical fields bouncing around. It occasionally crosses the tile boundary, but that is a bug in the example, not the squrf :p. Fourd is probably amazing to watch if you have a super computer, but it spends almost all its time calculating perlin noise values in four dimensions so it's a little slow on mine :/

Please note all of these examples use SDL and OpenGL. You almost certainly have OpenGL available. If your program won't run atall, you might want to try running squrf/examples/SdlTest. SDL can be obtained from www.libsdl.org if you don't already have it.

Hints

If you want to apply the same decorator to multiple fields, it will be faster to place all of the fields into a union and decorate that. This will execute faster, as well as being easier to read and write.

If you want copies of the same field, you can define it once and then add it multiple times (or more likely, apply different decorators to it and add those). See the 'transform' example for an example of this.

Problems

The first guess for vertex position is midway between any set of 8 reference points in the field that are not either all inside or all outside the field. If there are sharply changing gradients near the surface the smoothing algorithm may produce strange spikes and holes. If this is becoming a problem, try decreasing the 'mHard' value of any sigmoid functions involved.

TODO

Add LOD to the tile class

Add small-area-triangle removal to the tile class

Create container class for multiple tiles/LOD levels/automatic tile regeneration

Make the FieldUnion class a bit less childish in its implementation

Add bounding spheres/boxes (being careful with the gradients) or some other form of field culling

Add standardized factory class for scripting purposes

Add LUA script example