The Dimension Library
*********************

Copyright © 2009 Tavian Barnes

Introduction
************

The Dimension Library is a C library for rendering photo-realistic 3-D scenes.  It is designed to be the workhorse for the future ``dimension'' program.  The Dimension Library will in the future be a full-fledged high-performance raytracing library, but right now is in very early stages and heavy development.

The C library is probably not the interface you want to use; the C++ interface is much nicer.  libdimension was written in C to facilitate easy bindings for other languages.  Currently the only language binding is C++, but more languages, such as scripting languages, will be added in the future.  As such, this documentation gives a bottom-up overview of the Dimension Library, to allow someone reading it to have a full and complete understanding of the library, rather than a simple top-down overview.

Error Handling
**************

     typedef enum {
       DMNSN_SEVERITY_LOW,    /* Only die on low resilience */
       DMNSN_SEVERITY_MEDIUM, /* Die on low or medium resilience */
       DMNSN_SEVERITY_HIGH    /* Always die */
     } dmnsn_severity;

     #define dmnsn_error(severity, str) /* ... */

     dmnsn_severity dmnsn_get_resilience();
     void dmnsn_set_resilience(dmnsn_severity resilience);

When it makes sense, libdimension reports errors by returning error codes from its functions.  However, when errors are not severe, when said function should not fail, or when the error is very serious, libdimension reports errors using the macro dmnsn_error().  dmnsn_error() takes two parameters: the severity of the error, and a string description of the error.  The macro will conveniently report the description, as well as the function name and code line where the error occured, to standard error.  The severity can be either DMNSN_SEVERITY_LOW, DMNSN_SEVERITY_MEDIUM, or DMNSN_SEVERITY_HIGH.

The Dimension Library has also has a user-settable resilience.  The resilience controls the minimum severity at which the library considers an error to be fatal, and calls exit(EXIT_FAILURE).  As such, errors of severity DMNSN_SEVERITY_HIGH are always fatal.  libdimension's resilience defaults to DMNSN_SEVERITY_MEDIUM, but can be inspected or changed thread-safely by dmnsn_get_resilience() or dmnsn_set_resilience(), respectively.  Warnings (non-fatal errors) are formatted like this:

     Dimension WARNING: <function>, line <line>: <description>

while errors are formatted like this:

     Dimension ERROR: <function>, line <line>: <description>

Arrays
******

     typedef struct {
       /* ... */
     } dmnsn_array;

     /* Array allocation */
     dmnsn_array *dmnsn_new_array(size_t obj_size);
     void dmnsn_delete_array(dmnsn_array *array);

     /* Thread-safe atomic array access */

     void dmnsn_array_push(dmnsn_array *array, const void *obj);
     void dmnsn_array_pop(dmnsn_array *array, void *obj);
     void dmnsn_array_get(const dmnsn_array *array, size_t i, void *obj);
     void dmnsn_array_set(dmnsn_array *array, size_t i, const void *obj);
     void *dmnsn_array_at(dmnsn_array *array, size_t i);

     size_t dmnsn_array_size(const dmnsn_array *array);
     void   dmnsn_array_resize(dmnsn_array *array, size_t length);

The Dimension Library often has cause to work with adjustable-size arrays.  It provides an interface for dynamically-allocated arrays of arbitrary objects.  Arrays are allocated with the dmnsn_new_array() function, and freed with the dmnsn_delete_array() function, a pattern common in libdimension.  dmnsn_new_array() takes the size of the new array's elements as its parameter.  Unlike other allocation functions throughout libdimension, dmnsn_new_array() cannot fail if it returns (other allocators may return NULL).  In fact, all array operations are guaranteed to either succeed or report a fatal error, which may happen if memory allocation fails.

Arrays support the push, pop, get, and set operations for arrays, taking a pointer to an object to read or write as their last parameter, the array index when applicable as the second-last parameter, and the dmnsn_array * as the first parameter.  The get operation is bounds-checked; other operations dynamically resize the array as needed.  The array's length may be queried with dmnsn_array_size(), or set with dmnsn_array_resize(), and a pointer to the i'th object may be obtained with dmnsn_array_at().

Asynchronicity
**************

     typedef struct {
       /* ... */
     } dmnsn_progress;

     /* Progress allocation */
     dmnsn_progress *dmnsn_new_progress();
     void dmnsn_delete_progress(dmnsn_progress *progress);

     /* Ensures completion of the worker thread */
     int dmnsn_finish_progress(dmnsn_progress *progress);

     /* Routines for user */
     double dmnsn_get_progress(const dmnsn_progress *progress);
     void dmnsn_wait_progress(const dmnsn_progress *progress, double prog);

     /* Routines for worker thread */
     void dmnsn_new_progress_element(dmnsn_progress *progress,
                                     unsigned int total);
     void dmnsn_increment_progress(dmnsn_progress *progress);
     void dmnsn_done_progress(dmnsn_progress *progress);

As the Dimension Library is a raytracing engine, some routines are likely to take a long time.  These routines may be run in a background thread, and controlled with a common interface.  Routines supporting this interface end in _async, such as dmnsn_raytrace_scene_async(), and return a dmnsn_progress * object, so named because it allows an application to be query the progress of the background task.  By necessity, all dmnsn_progress * operations are atomic and thread-safe.

Progress objects are allocated and deallocated in the standard libdimension way, but also support a unique dmnsn_finish_progress() function.  This function waits for the background thread to complete, and then destroys the dmnsn_progress * object.  Never use the result of a background task before calling dmnsn_finish_progress(), even if the progress seems to be at 100%!  dmnsn_delete_progress() should only be called from within failed *_async() functions, to deallocate a progress object before it is associated with a running thread.

Users of these asynchronous tasks will mainly be interested in the functions dmnsn_get_progress() and dmnsn_wait_progress().  dmnsn_get_progress() returns the progress of the background task, a value between 0.0 and 1.0.  dmnsn_wait_progress() simply waits for dmnsn_get_progress() to be >= prog, but in a much better way than spinlocking (internally, a condition variable is used).

Background tasks themselves will be interested in three more functions.  To indicate progress to the user, progress objects store one "element" for each level of loop nesting a task would like to report the progress of.  Only the innermost loop need increment the progress counter, as in this example:

     dmnsn_new_progress_element(progress, i_max);
     for (i = 0; i < i_max; ++i) {
       dmnsn_new_progress_element(progress, j_max);
       for (j = 0; j < j_max; ++j) {
         /* Do stuff */
         dmnsn_increment_progress(progress);
       }
     }

For robustness, tasks should call dmnsn_done_progress() when they finish, even if they fail.  This function immediately sets the progress to 100%, which wakes up all waiters.  Otherwise, a user's application may hang calling dmnsn_wait_progress().

Geometry
********

     /* Vector and matrix types. */

     typedef struct {
       double x, y, z;
     } dmnsn_vector;

     typedef struct {
       double n[4][4];
     } dmnsn_matrix;

     /* A line, or ray. */
     typedef struct {
       dmnsn_vector x0; /* A point on the line */
       dmnsn_vector n;  /* A normal vector; the direction of the line */
     } dmnsn_line;

     /* Vector/matrix construction */

     dmnsn_vector dmnsn_vector_construct(double x, double y, double z);

     dmnsn_matrix
     dmnsn_matrix_construct(double a0, double a1, double a2, double a3,
                            double b0, double b1, double b2, double b3,
                            double c0, double c1, double c2, double c3,
                            double d0, double d1, double d2, double d3);

     dmnsn_matrix dmnsn_identity_matrix();
     dmnsn_matrix dmnsn_scale_matrix(dmnsn_vector s);
     dmnsn_matrix dmnsn_translation_matrix(dmnsn_vector d);
     dmnsn_matrix dmnsn_rotation_matrix(dmnsn_vector theta);

     dmnsn_line dmnsn_line_construct(dmnsn_vector x0, dmnsn_vector n);

     /* Vector and matrix arithmetic */

     dmnsn_vector dmnsn_vector_add(dmnsn_vector lhs, dmnsn_vector rhs);
     dmnsn_vector dmnsn_vector_sub(dmnsn_vector lhs, dmnsn_vector rhs);
     dmnsn_vector dmnsn_vector_mul(double lhs, dmnsn_vector rhs);
     dmnsn_vector dmnsn_vector_div(dmnsn_vector lhs, double rhs);

     double       dmnsn_vector_dot(dmnsn_vector lhs, dmnsn_vector rhs);
     dmnsn_vector dmnsn_vector_cross(dmnsn_vector lhs, dmnsn_vector rhs);

     double       dmnsn_vector_norm(dmnsn_vector n);
     dmnsn_vector dmnsn_vector_normalize(dmnsn_vector n);

     dmnsn_matrix dmnsn_matrix_inverse(dmnsn_matrix A);
     dmnsn_matrix dmnsn_matrix_mul(dmnsn_matrix lhs, dmnsn_matrix rhs);
     dmnsn_vector dmnsn_matrix_vector_mul(dmnsn_matrix lhs,
                                          dmnsn_vector rhs);
     dmnsn_line   dmnsn_matrix_line_mul(dmnsn_matrix lhs, dmnsn_line rhs);

     dmnsn_vector dmnsn_line_point(dmnsn_line l, double t);
     double dmnsn_line_index(dmnsn_line l, dmnsn_vector x);

For performing 3-D computational geometry, the Dimension Library supports geometric types and many operations on these types.  libdimension defines the dmnsn_vector, dmnsn_matrix, and dmnsn_line geometric types.  They may be easily constructed by the self-explanatory dmnsn_vector_construct(), dmnsn_matrix_construct(), or dmnsn_line_construct().

Vectors support addition and subtraction, multiplication and division by a scalar, the dot and cross products, the norm and normalization operations, and transformation by a matrix (dmnsn_matrix_vector_mul()).

Matricies support matrix multiplication, and inversion.  Inversion uses a very fast partitioning algorithm.  As well, there are four special matrix constructors.  dmnsn_identity_matrix() simply returns the identity matrix.  dmnsn_scale_matrix(s) returns a matrix which scales each dimension by a factor of the corresponding dimension of the s.  dmnsn_translate_matrix(d) returns a matrix which translates by d.  Finally, dmnsn_rotation_matrix(theta) returns a matrix which rotates by an angle of norm(theta), about the axis normalized(theta).

Lines support transformation by a matrix (dmnsn_matrix_line_mul(A, l) = dmnsn_line_construct(A*l.x0, A*(l.x0 + l.n) - A*l.x0)).  Also, dmnsn_line_point(l, t) = l.x0 + t*l.n gives the point t on the line, and dmnsn_line_index(l, x) gives the t value such that dmnsn_line_point(l, t) == x.

Color
*****

     typedef struct {
       double filter, trans; /* Filter transparancy only lets light of this
                                color through; regular transparancy lets all
                                colors through.  filter + trans should be
                                <= 1.0. */
       /* ... */
     } dmnsn_color;

     typedef struct {
       double X, Y, Z; /* X, Y, and Z are tristimulus values, unbounded
                          above zero.  Diffuse white is (0.9505, 1,
                          1.089). */
     } dmnsn_CIE_XYZ;

     typedef struct {
       double x, y, Y; /* x and y are chromaticity coordinates, and Y is
                          luminance, in the CIE 1931 xyZ color space.  We
                          use an unlimited light model, so x,y in [0, 1] and
                          Y >= 0, with 1 = diffuse white */
     } dmnsn_CIE_xyY;

     typedef struct {
       double L, a, b; /* L is luminence (100 = diffuse white); a and b are
                          color-opponent dimensions.  This color space is
                          used for color arithmetic. */
     } dmnsn_CIE_Lab;

     typedef struct {
       double L, u, v; /* L is luminence (100 = diffuse white); u and v are
                          chromaticity coordinates. */
     } dmnsn_CIE_Luv;

     typedef struct {
       double R, G, B; /* sRGB R, G, and B values */
     } dmnsn_sRGB;

     /* Standard whitepoint, determined by the conversion of sRGB white to
        CIE XYZ */
     extern const dmnsn_CIE_XYZ dmnsn_whitepoint;

     /* Color conversions */

     dmnsn_color dmnsn_color_from_XYZ(dmnsn_CIE_XYZ XYZ);
     dmnsn_color dmnsn_color_from_xyY(dmnsn_CIE_xyY xyY);
     dmnsn_color dmnsn_color_from_Lab(dmnsn_CIE_Lab Lab,
                                      dmnsn_CIE_XYZ white);
     dmnsn_color dmnsn_color_from_Luv(dmnsn_CIE_Luv Luv,
                                      dmnsn_CIE_XYZ white);
     dmnsn_color dmnsn_color_from_sRGB(dmnsn_sRGB sRGB);

     dmnsn_CIE_XYZ dmnsn_XYZ_from_color(dmnsn_color color);
     dmnsn_CIE_xyY dmnsn_xyY_from_color(dmnsn_color color);
     dmnsn_CIE_Lab dmnsn_Lab_from_color(dmnsn_color color,
                                        dmnsn_CIE_XYZ white);
     dmnsn_CIE_Luv dmnsn_Luv_from_color(dmnsn_color color,
                                        dmnsn_CIE_XYZ white);
     dmnsn_sRGB    dmnsn_sRGB_from_color(dmnsn_color color);

     /* Perceptually correct color combination */
     dmnsn_color dmnsn_color_add(dmnsn_color color1, dmnsn_color color2);

     /* Perceptual color difference */
     double dmnsn_color_difference(dmnsn_color color1, dmnsn_color color2);

The Dimension Library supports many different representations of color.  The details of each representation are beyond the scope of this manual, but libdimension supports CIE XYZ, xyY, L*a*b*, L*u*v*, and sRGB color.  CIE L*a*b* and L*u*v* are designed to be perceptually uniform, meaning changes in their color coordinates correspond to perceptual changes of equal magnitude.  The dmnsn_color type libdimension itself to represent colors, in an unspecified format.  The .filter field gives the color's filtered transparency, which lets same-colored light through, while the .trans field stores non-filtered transparency.

The dmnsn_color_from_*() and dmnsn_*_from_color() functions are used to convert to and from the dmnsn_color type.  The conversions to dmnsn_color set the .filter and .trans fields to zero, and those fields are ignored by the inverse conversions.  Conversions to and from CIE L*a*b* and L*u*v* colors take an extra parameter, which specifies the absolute color value of the whitepoint the conversions are relative to.  dmnsn_whitepoint is a good value for this parameter.

dmnsn_color_add() adds two colors in a perceptually-correct way, and dmnsn_color_difference() returns the magnatude of the perceptual difference between two colors.

Canvases
********

     typedef struct {
       /* width, height */
       unsigned int x, y;

       /* ... */
     } dmnsn_canvas;

     /* Allocate and free a canvas */
     dmnsn_canvas *dmnsn_new_canvas(unsigned int x, unsigned int y);
     void dmnsn_delete_canvas(dmnsn_canvas *canvas);

     /* Pixel accessors */
     dmnsn_color dmnsn_get_pixel(const dmnsn_canvas *canvas,
                                 unsigned int x, unsigned int y);
     void dmnsn_set_pixel(dmnsn_canvas *canvas,
                          unsigned int x, unsigned int y,
                          dmnsn_color color);
     dmnsn_color *dmnsn_pixel_at(dmnsn_canvas *canvas,
                                 unsigned int x, unsigned int y);

The target of a rendering operation in the Dimension Library is a canvas object, represented by the type dmnsn_canvas *.  This type stores a dmnsn_color for each pixel in the ->pixels field, as well as the dimensions of the canvas in the ->x and ->y fields.  The pixel at (x,y) can be examined or set by the accessors dmnsn_get_pixel() and dmnsn_set_pixel(), and referenced by dmnsn_pixel_at().

Canvases may be imported from or exported to images.  In the future, canvases will also be able to be treated as object textures, to support images as textures.

PNG Import and Export
=====================

     /* Write canvas to file in PNG format.  Returns 0 on success, nonzero
        on failure */
     int dmnsn_png_write_canvas(const dmnsn_canvas *canvas, FILE *file);
     dmnsn_progress *
     dmnsn_png_write_canvas_async(const dmnsn_canvas *canvas, FILE *file);

     /* Read a canvas from a PNG file.  Returns NULL on failure. */
     dmnsn_canvas *dmnsn_png_read_canvas(FILE *file);
     dmnsn_progress *dmnsn_png_read_canvas_async(dmnsn_canvas **canvas,
                                                 FILE *file);

The Dimension Library supports import and export of canvas to and from PNG files; this is currently the only supported image type.  The interface is simple: dmnsn_png_write_canvas() writes the canvas in PNG format to the given file, at maximum quality; dmnsn_png_read_canvas() imports a PNG file to a canvas.  The *_async() versions work as described in Asynchronicity.

Objects
*******

     typedef struct {
       /* Generic pointer for object info */
       void *ptr;

       /* Transformation matrix */
       dmnsn_matrix trans;

       /* Callback functions */
       dmnsn_object_intersections_fn *intersections_fn;
       dmnsn_object_inside_fn        *inside_fn;
     } dmnsn_object;

     /* Object callback types */
     typedef dmnsn_array *
     dmnsn_object_intersections_fn(const dmnsn_object *object,
                                   dmnsn_line line);
     typedef int dmnsn_object_inside_fn(const dmnsn_object *object,
                                        dmnsn_vector point);

     /* Allocate a dummy object */
     dmnsn_object *dmnsn_new_object();
     void dmnsn_delete_object(dmnsn_object *object);

The Dimension Library renders 3-D objects, represented by the dmnsn_object * type.  This type has callback functions for determining if and where a ray intersects the object, and whether a point is inside the object.  In the future, many more callbacks will be added.  libdimension comes with a few simple object types like spheres and cubes, or you may create your own by customizing the object callbacks.  The field ->ptr is a void pointer which may be used to store additional information about an object.  The ->trans field is a transformation matrix, transforming the rays which intersect the object, rather than the object itself.  Thus, ->trans should be set to the inverse of the transformations you wish to apply to the object.

The ->intersections_fn callback should point to a function with the same signature as the dmnsn_object_intersections_fn type.  It should return a dmnsn_array of double's, holding each t-value of the given line which intersects with the object.  In the case that there are no intersections, an empty array should be returned.

The ->inside_fn callback should point to a function matching the signature of the dmnsn_object_inside_fn type.  It should return 0 if the given point is outside the object, and nonzero when that point is inside the object.  The callback is free to return any value in the case that the point lies directly on the surface of the object.

Spheres
=======

     dmnsn_object *dmnsn_new_sphere();
     void dmnsn_delete_sphere(dmnsn_object *sphere);

The Dimension Library has a few built-in basic shape primitives.  One of them is the sphere; dmnsn_new_sphere() returns a sphere of radius 1, centered at the origin.  Use the object's transformation matrix to scale, translate, and/or rotate it.

Cubes
=====

     dmnsn_object *dmnsn_new_cube();
     void dmnsn_delete_cube(dmnsn_object *cube);

dmnsn_new_cube() returns a cube, axis-aligned, from (-1, -1, -1) to (1, 1, 1).  Use its transformation matrix to scale, translate, and/or rotate it.

Cameras
*******

     typedef struct {
       /* Generic pointer for camera info */
       void *ptr;

       /* Callback function */
       dmnsn_camera_ray_fn *ray_fn;
     } dmnsn_camera;

     /* Camera callback types */
     typedef dmnsn_line dmnsn_camera_ray_fn(const dmnsn_camera *camera,
                                            const dmnsn_canvas *canvas,
                                            unsigned int x, unsigned int y);

     dmnsn_camera *dmnsn_new_camera();
     void dmnsn_delete_camera(dmnsn_camera *camera);

In order to project a 3-D scene onto a 2-D plane, the Dimension Library uses a generic camera type.  A camera provides the Dimension Library the camera ray corresponding to each pixel in the canvas, by its ->ray_fn callback.

->ray_fn should point to a function matching the signature of the type dmnsn_camera_ray_fn, and should return the ray corresponding to the pixel at (x, y) in the given canvas.

Perspective Cameras
===================

     dmnsn_camera *dmnsn_new_perspective_camera(dmnsn_matrix trans);
     void dmnsn_delete_perspective_camera(dmnsn_camera *camera);

The function dmnsn_new_perspective_camera creates a perspective camera, situated at the origin, looking toward (0, 0, 1), and aiming at a screen from (-0.5, -0.5) to (0.5, 0.5) on the z = 1 plane.  Camera rays are transformed by the parameter trans.

Scenes
******

     typedef struct {
       dmnsn_color background;
       dmnsn_array *objects;
       dmnsn_camera *camera;
       dmnsn_canvas *canvas;
     } dmnsn_scene;

     dmnsn_scene *dmnsn_new_scene();
     void dmnsn_delete_scene(dmnsn_scene *scene);

The dmnsn_scene * type ties all the components of a 3-D world together.  A scene stores a background color in its ->background field, an array of const dmnsn_object *'s in its ->objects field, a dmnsn_camera * in its ->camera field, and a dmnsn_canvas * in its ->canvas field.  Scenes can be rendered, producing an image in their canvas field.

Raytracing
==========

     int dmnsn_raytrace_scene(dmnsn_scene *scene);
     dmnsn_progress *dmnsn_raytrace_scene_async(dmnsn_scene *scene);

The dmnsn_raytrace_scene() function renders a scene by raytracing - casting rays from the camera to objects in its view.  Currently, the raytracing engine is quite simple - it shades pixels where objects appear according to their distance from the camera, closer objects being brighter.  The ..._async() version works as described in Asynchronicity.