| List of features | ||
| Feature | Description | Example |
| Displacement Mapping | It is the core element of my tracer as many other features depend on it.
It can be used both at global scale to shape the scene (i.e. terrain)
as well as at detail level to add realsim (i.e. candle surface). Main component of my displacement mapping is the HeightMap class. It works similarly to a texture - it is a two-dimentional matrix of sampled positive height numbers. Arbitrary two dimentional coordinates of the heightmap may be applied to a vertex of a triangle primitive (HeightTriangle, SmoothHeightTriangle) pritty much the same as it is done with texture. HeightMap provides an intersect(Ray,minT,maxT) method to check if and where the given ray intersects the map. HeightMap has no information about spatial location of the triangle(s) it is used on, so the ray must be transformed into local reference system of the map. Map lies on XY surface and perturbation goes into Z direction. Whole array is spread over square [0..1]x[0..1] (later the ray is scaled internally). minT and maxT are the extreme points where ray is over the triangle we are intersecting. This saves time and increases quality - we do not want to intersect heightmap somewhere while not being over the triangle. Very naive implementation of HeightMap could be done by spawning all its triangles, putting them into kdtree and rendering by already written algorithms. This would actually spawn a great number of triangles. Displacement array of dimension 256 would generate at least 131072 triangles and would take a lot of time to compute even with good kd-tree. (For comparison - cow.obj uses less than 6000 triangles) My implementation of HeightMap takes advantage over spatial organisation of its triangles. It temporarly spawns four triangles only at the last step of the algorithm, when it localised the hit position there. Before that, my algorithm projects the ray over a grid and checks z coordinate at each point where x or y coordinate is integer (when unit distance is the distance between two height samples). The value is checked against linearly interpolated height from two closest grid points. Such check is very fast to compute in comparison to triangle intersection, and it is quick even without additional structuring of the matrix. Additional global value of max height is stored to avoid unnecessary checks. Also algorithm is terminated when we pass behind maxT. Special care is taken for rays incoming from perpendicular angle to the heightmap, when ray never intersects any integer coordinate and maxT is infinite. This approach is extreamly fast if incoming rays are nearly perpendicular to heightmap or maximal height is small - in that case only few comparison are being made before hitpoint is found. The algorithm is slower when maximal height is big but there are vast low regions and the ray is parallel to the surface. In that case intersection time is linear to the dimension of height array. This can be resolved by adding 2d quad-tree to the array. At each node the maximal height of its children would be stored which would hopefully be smaller than global maximal height. This way if height is big only at one or few positions, ray traversal elsewhere will be fast. I was attempting to implement the structure, but time was pressing on and there were still lots of bugs elsewhere, so I reverted back to the simpler - yet sufficently fast version. Additionaly, heightmap interpolates gradient value at given 2D point, which is later used by HeightTriangle and SmoothHeightTriangle to compute perturbed normals. While HeightTriangle adds up vector to the gradient, SmoothHeightTriangle combines interpolated normal vector to it. SmoothHeightTriangle is used on the candle, everywhere else simpler HeightTriangle is being used. | Displacement mapping can be seen everywhere:
Terrain, Candle, Table, Water. Frame 1054 - candle just before falling On this frame it is probably seen the best, how it interacts with world. The candle is not just a straight cylinder, and it is unevenly illuminated. Also note the shadow of a mountain right from view point casted across the table. The mountain is also driven by the displacement map |
| Fractal Geometry | Fractal geometry is used in two cases: Firstly it is used to generate terrain simply by applying 2d perlin noise to generate heightmap. The heightmap is generated at the beginning of program and then stored in raw format in memory. Secondly it is used in a candle. Basicly it uses perlin noise as well, but the heightmap is slightly streached and convolved with weighted motion blur to simulate frozen vax on the surface of the candle. | For candle - same as above Frame 1054 - candle just before falling Terrain (not on the video): Terrain map This image shows terrain seen from top, with different lightning and replaced texture to emphasise height differences. Approximated camera path for first part of video is marked. |
| Water simulation Reflective and Refractive Transparency | To simulate water surface a special WaterShader is created. For given incoming ray it generates two new rays, one for reflected component and one for refracted one (provided it exists). It uses Snell's law to compute refraction and Fresnel equations to weight the resulting colors. Additionaly, an additional attenuation for refracted ray is applied depending on the hit distance. Water surface uses small displacement map as well to generate tiny waves and make use of perturbed normals to add realism to water surface. It can be particularly seen by distortions of reflected objects. | Frame 317 - wavy water Frame 317 with increased brightness Frame 220 - aproaching the pond Here, on the bottom of the image, you can see how the rocky surface is refracted. Below the water surface it seems to be flatter than above. |
| 3D texturing | Usage of heightmap allows to store third coordinate after a hit, which can be used later for texturing. This is being done with landscape texture. Terrain uses a single texture, which checks height coordinate and applies different color based on it. There are main 3 regions - ground, grass and rocks which are slightly melted one with another to avoid ugly straight lines. Also using 3d texture allowed me to avoid ugly streching artefacts at high gradient regions. | Frame 501 - aproaching the candle Here all three levels can be easily seen. The slightly brighter brown surface at the horison is a background texture and is not a part of heightmap. |
| Procedural Texturing | There are no external textures in the animation, all are generated at run-time, mostly using different combination of perlin noise. Main two textures is the landscape texture and wood texture. Wood texture takes a value of perlin noise as an argument for a cosine function. This way I obtain repetitive curves which - when streached - simulate wood quite well. Landscape 3d texture is more complicated one. The rocks use several layers of perlin noise to generate rocks of different size. The biggest ones are allowed to appear lower, over the grass. Edges of the rocks are blended with whatever they hide to avoid sharp edges. | Frame 770 - after a jump Viewer is very close to the table here, you can observe the texture in detail, especially in the brightened part at the bottom of the image. Frame 128 - rocky ground Rocky region. Observe different sizes of rocks. There is a single component on the second plan on the left, while lots of smaller rocks on the right. You can also see rocks on the grass on the first plan. This is all generated by a single texture object! Table object (not on the video) Edges at main image Main image with applied edge detection filter to emphasise the pattern of the wooden texture |
| Remote texturing | The sky texture is not associated with any object, instead it is applied to world itself. The texture is not shaded just applied directly when ray does not hit any object in the scene. It has to be a 3d texture because it takes ray direction vector as an argument to get a pixel. As a result you see a unit sphere curved out of the texture, seen from the point [0,0,0] which does not depend on camera location. This approach guarantees you will never see nothingness. At least you see a brown ground instead of black, green or pink(!) background color. | Frame 501 - aproaching the candle You can see stars when direction vector goes up and brown surface when it is moving down. Thus horison is exactly where it should be - at the height of camera. |
| Simplified Integrated Intensity Volume Rendering | A very simple integration aproach was applied to render the fire. It is controled by GlassShader which projects ray inside and behind the object and then blends the background color with the object's color depending linearly on traversal length inside the object. Mathematically it can be seen as integraction over box-like-function scalar field. The flame is rather opaque but this aproach smooths its edges and it no longer looks like quake1 squarish fire meshes. | Frame 1036 - The Candle Here if you look closely, you will see how top of the fire object blends with dark edge of a mountain behind. Observe, the edge is less visible in the middle, because flame is wider there and thus less transparent. Similar effect can be seen on the main image |
| Cubic B-Spline Camera Path | Camera movement is defined by a path route. Knot points are explicitly provided and a smooth path is generated by joining cubic B-splines. It is guaranteed that camera moves through the knot points. A nice webpage on splines was helpful for me to code it: http://www.ibiblio.org/e-notes/Splines/Intro.htm | N/A |
| Implementation specific | ||||||||||
| Element | Description | Example (if applicable) | ||||||||
| Vectors | Vector class has been highly edited. It is now a template, taking dimension as a parameter. To avoid time loss and increase functionality 2d and 3d class instances are specifically written. | N/A | ||||||||
| Matrices | Square matrices are also templates, depending on their dimension. I use only 2d and 3d matrices, some functionality of higher dimension matrices are not implemented (i.e. inversing) because efficient algorithms are not that easy and there would be of no use for the rendering. Matrices are used to change coordinate system of a HeightMap and optionaly, for entities (see below) | N/A | ||||||||
| Quaternions | Provide basic operation in the quaternion number space, and some useful vector transformation - namely rotation. Used to rotate entities (see below) | Frame 1062 - Falling candle Candle being rotated when falling | ||||||||
| BVH | In my version of MicroTracer the Object class is a derivative of Primitive. This way one object may be an element of another forming a hierarchy. What is more, one object may be referenced many times. Very simple garbage collector is implemented to free memory of such object only when it is not referenced by anything. There are also Entities, which are more advanced objects (thus also primitives!). Entity allow transformations - translation, rotation or even (optionally) arbitrary linear transformation. When ray hits the bounding box of entity, it is transformed into local reference system and intersection procedure continues. Care has been taken to correctly transform back hit time (ray.t), and normals. All objects in the video are entities (terrain, table, candle, candle fire). They could be easily tested, modeled etc, and then put together using translations. It would be difficult for me to put all primitives into one huge object, it would be against the design of my raytracer. Therefore I am unable to make time comparison between those two approaches. | Table object (not on video) All table legs is only a signle object in memory, with four references by Entities with applied different translation vectors. | ||||||||
| Volume Heuristic KD-Tree | Equivalent of 2D Surface Area Heuristc. To find minimum of cost function i project bounding boxes of all primitives into one axis, then I convert them into points with flags "beginning" and "end", and then sort them. When it is done, I go through all points and compute the cost function. At each point I know many "begin"-s and "end"-s I encountered so far, so I know how many primitives are on the left and right side of my point. This way I can compute cost function in constant time at each position. Algorithm complexity is equal to sorting time. STL sort function has guaranteed O(n log n) complexity including the worst case. More primitive heuristic, which I denote AVG-SD, computes center of mass of all primitives (average) and standard deviation in three directions parallel to axis. Split goes through the center, against the axis with highest SD |
| ||||||||
| Files | |
| File name | Description |
| box.h | Extendable bounding box |
| camera.h cameraperspective.h | Perspective camera model |
| cameramover.h | Controls the movement of a camera |
| candle.h candle.cpp | Creates the candle without flame |
| candlefire.h candlefire.cpp | Creates flame of the candle |
| config.h | Main configuration file which controls the scene and algorithms |
| debug.h | Set of useful macros for debugging |
| entity.h | Implements the Entity described above. Uses ref.h for transformations |
| generator.h generator.cpp | A set of useful functions for generating objects in scene, i.e. cones, cut-cones, quads etc. |
| heightmap.h heightmap.cpp | Implementation of the dismplacement map. |
| image.h image.cpp | I/O for images |
| interpolation.h | A set of useful interpolation functions |
| interval.h intervalset.h | classes used to store primitive extremes in Volume Heristic for kd-tree |
| kdtree.h kdtree.cpp | Implementation of KD tree |
| landscape.h landscape.cpp | Creates the terrain and water. Also the 3d landscape texture is here |
| light.h | Abstract light source |
| lightdistant.h | A distant light source with no attenuation |
| lightpoint.h | Simple point source |
| lightquadarea.h | Quad light source approximated by numerous point lights. Actually it is never used in the rendering |
| lightsphere.h | A simpler version to Quad Area light. Random point lights are taken from a ball of some radius. No normal vector is defined, light intensity is equal in all direction. |
| mat.h | Implementation of quare matrices |
| object.h object.cpp | Simplest object which can contain primitives and keeps kd-tree over them. |
| pngHelper.h | Interface to the PNG library |
| primitive.h | Abstract primitive |
| primheighttriangle.h | Triangle with applied heightmap |
| priminfiniteplane.h | Infinite plane. It was used at some version of my program, but it isn't anymore |
| primsmoothheighttriangle.h | Triangle with applied heightmap and per-vertex base normals, which are later combined with the computed gradient |
| primsmoothtriangle.h | Flat triangle with per-vertex normals |
| primtexturedsmoothtriangle.h | Textured flat triangle with per-vertex normals |
| primtexturedtriangle.h | Textured triangle |
| primtriangle.h | A single triangle with no additional attributes |
| quaterion.h | Implements quaternions |
| rand.h rand.cpp | Interface to some simple random functions, including repetitive random functions and Perlin noise |
| ray.h | Ray object used for raytracing |
| ref.h | Implements neccessary transformations between two reference systems |
| sampler.h | Abstract sampler for pixel coloring |
| samplerrandom.h samplerregular.h samplerstraitified.h | Different kind of samplers. The straitified version is used in the rendering |
| shader.h | Abstract shader |
| shadercoud.h | Generates coulds. Never used. |
| shaderflattransparent.h | To be used with textures with alpha channel. Never used. |
| shaderglass.h | Implements ray traversal through dimm object i.e. dimm glass. Used for candle fire |
| shaderphong.h | Implements simple illumination function for given point. |
| shadersimple.h | Simply takes the color of given object or texture texel and returns it. No lightning etc. Used mainly for debugging |
| shaderwater.h | Reflets and refracts the ray and later blends them |
| table.h table.cpp | Creates the table on which the candle is standing |
| texture.h | Abstract texture class with defined 2 and 3 argument getTexel function |
| textureperlin.h texture3dperlin.h | Parametisable texture using 2D/3D perlin noise |
| texturestars.h | Implement stars and ground for the world |
| texturewood.h | Imitates wood using perlin noise |
| utils.h | A bunch of useful functions |
| vec.h vec2f.h vec3f.h | Implements the vector template and two specialistions |
| world.h | This holds the whole scene |
| Trivia | |
| Video length | 55 seconds |
| Number of frames | 1320 |
| Render time | approx. 2 days |
| Frame longest render time | 3 hours |
| Frame shortest render time | 4 seconds |
| Number of rays per pixel | 4 |
| Number of light sources | 70 |
| Number of explicit triangles | approx. 640 -terrain: 2 -water: 6 -candle: 101 -table: 22 -fire: approx 509 |
| Number of all triangles including heightmap virtual triangles | approx. 210000 -terrain: 32768 -water: 119000 -candle: 8261 -table: 51221 -fire: approx 509) |
| Memory consuption | 9 megabytes |
| Source code size | approx. 10000 lines approx. 250 kilobytes |
| Rendering location | |
| Frames | Computer |
| 0-350 | My laptop |
| 351-599 | Maciek's mac |
| 600-609 | virgo.ii.uj.edu.pl |
| 610 | Maciek's mac |
| 611-614 | virgo.ii.uj.edu.pl |
| 615-619 | Maciek's mac |
| 620-646 | virgo.ii.uj.edu.pl |
| 647-764 | Maciek's mac |
| 765-784 | virgo.ii.uj.edu.pl |
| 785 | My laptop |
| 786-809 | Maciek's mac |
| 810-884 | virgo.ii.uj.edu.pl |
| 885 | tsk |
| 886-1320 | Maciek's mac |