Ray tracing implementation using a Metal framework
Already wellknown Metal framework has become an indispensable tool for building the great games and applications, which you can find in Metal by Example. Metal is available for devices using the Apple A7, Apple A8, and Apple A8X, combines the similar functionality with such wellknown API as OpenGL and OpenCL. How did this tool become useful for Indeema engineers I will tell you below.
Our team of developers faced the issue of simulating different prism shapes that are between the object (image) and the camera so that the prism refracts and reflects the picture as the most realistic and yet get other lighting effects such as chromatic aberration and chromatic glow. Also, the prism should be movable, and all this for mobile platform iOS8.
Related: New trend of image editing – iOS apps?
First of all, our programmers started to search for the current solutions in order to save time. They found a good resource where a small tutorial or source code can be downloaded. Our team undertook to examine the code and the first change was the replacement of shapes (prisms), ball looked impressive.
However, changing in triangular prism we’ve got the following result:
At first glance it looks nice and fair, but after deeper investigation it became clear that the algorithm for the solution of the problem does not fit.
The point is that the algorithm, programmers found, works in the way that the image is refracted only on the visible sides of the cube, meaning that there is no internal refraction and reflection, and this, in turn, makes the result less realistic.
Looking for the solution further…
Looking for the solution in the Internet, we found out the principle of ray tracing.
During the implementation our team showed creativity being aware how Metal Framework works. After thinking about everything that we had found and analyzing all we had known, we came up to the next:
 We decided to get rid of 3D world and realize everything using the shaders.
 We simulated 3D world with one figure and area with the image in it.
It looks just about that:

Then, trail rays for each pixel of the image and check if the beam crosses planes figures. When crossing, calculate the refraction and reflection of the beam.

We form a new image.
And here is the result we get
In details we will examine the algorithm below.
After the implementation of this algorithm we got the result that we comforted. However, if you examine the technology of ray tracing you will find out that all sources claim that this method is resource intensive. As the result, it has created a new obstacle for us, as the mobile device processor is not very powerful.
The resource intensity of algorithm led to restrictions on the complexity of the prism, namely the number of triangular planes that form the shape. This means that the algorithm is suitable to a small variety of shapes exposed to the current ray tracing technology. In the case of more complex shapes FPS reduced to 10. We avoided this issue by creating the ray distribution map. If the figure does not change the location and is not rotating, the refraction/reflection are the same for prism. In that case, we decided to generate the map of refractions only when changes are made. Hence, the 3D simulation can be created more realistic.
Pros:
 after the map is generated for certain prism provision, image processing is performed with FPS 60;
 easy of shader’s implementation.
Cons:
 the map takes a lot of RAM;
 by changing the position or turning the figure, user does not see the results right away, but only as the changes are over. When rotating figure’s frame is displayed on the screen.
Check out Ray tracing with Metal framework at Indeema Software video that is filmed as a result of algorithm realization.
Related: How Much Does It Cost to Develop an App?
Algorithm
Basic structures and types
enum MaterialType {
MaterialTypeAir,
MaterialTypePrism
};
typedef float3 Point3D;
typedef float3 Vector3D;
With these types we define the beam structure:
struct Ray {
MaterialType materialType;
Point3D origin;
Vector3D direction;
};
materialType  it is one of predefined types of MaterialType, which indicates where current ray spreads;
origin  ray’s start point in coordinate space;
direction  ray spread direction;
Then we create structure for intersections. It is used to calculate/compute new ray when ray intersects some object:
struct Intersection {
Ray newRay;
Point3D position;
Vector3D direction;
Vector3D normal;
bool intersect;
IntersectionType intersectionType;
float distanse;
bool intersectPrism;
int prismIntersectionCount;
};
newRay  ray which we got as a result of intersection of old ray and triangle;
position  intersection point in coordinate space;
normal  object’s normal that intersects with a ray in “position” point;
prismIntersectionCount  number of the ray’s refractions or reflections with the object.
As we have mentioned earlier all the objects are a set of triangles, so we need an appropriate structure:
struct Triangle {
Vector3D normal;
Point3D points[3];
Vector3D edge1, edge2;
float eta;
};
normal  object’s normal that intersecs with the ray in “position” point;
points  array of points of a triangle (V0, V1, V2).
edge1, edge2  vectors of triangle’s coordinate system with a centre point V0.
edge1 = Vector3D(V1 V0), edge2 = Vector3D(V2 V0).
Below is a structure that is used to render textures to simplify certain provisions of the prism. This structure is designed for full HD pictures (1920x1080).
It works by the following rule: each pixel with coordinate (x, y) assigns to three coordinates for each color RGB, thus realizing simultaneously chromatic aberration effect.
The map for one position is formed and used to process the image to its next change.
struct ImageMap {
uint2 map[1920][1080][3];
bool needRegenerateMap;
bool findOnlyIntersection;
};
To make things simple, we need to describe the structure of the plane, which consists of two triangles.
struct Plane {
Triangle triangles[2];
float eta;
Vector3D normal;
};
triangles  triangles forming plane.
eta  refractive index.
normal  plane’s normal.
The structure of imaginary world which is represented as a cube.
struct Skybox {
Plane planes[6];
};
planes  planes forming a cube.
As a test object, let’s consider a triangular prism:
described with a structure:
struct TrianglePrism {
Point3D center;
Plane planes[3];
Triangle triangles[2];
float eta;
};
eta  coefficient of prism’s refraction (for the glass eta ≈ 1.6).
The structure which describes the scene contains the skybox object and a triangular prism.
struct SceneTrianglePrism {
Skybox skybox;
TrianglePrism trianglePrism;
};
Main functions
The function of ray’s intersection with triangle.
Intersection intersectTriangle(Triangle triangle, Ray ray) {
Vector3D tvec, pvec, qvec;
float det;
pvec = cross(ray.direction, triangle.edge2);
det = dot(triangle.edge1, pvec);
if (det > EPSILON && det < EPSILON) {
return Intersection();
}
tvec = ray.origin  triangle.points[0];
float u = dot(tvec, pvec) / det;
if (u < 0.0  u > 1.0) {
return Intersection();
}
qvec = cross(tvec, triangle.edge1);
float v = dot(ray.direction, qvec) / det;
if (v < 0.0  u + v > 1.0)
return Intersection();
float t = dot(triangle.edge2, qvec) / det;
if(t < 20 * EPSILON) {
return Intersection();
}
if(angleBetweenTwoVectors(ray.direction, triangle.normal) < PI / 2) {
triangle.normal = triangle.normal;
}
return Intersection(ray, t, triangle.normal, triangle.eta);
}
This method is based on the algorithm described in details in the article.
The method takes the triangle and the beam, and after calculation returns the object “intersection”.
The following method implements the intersection of a beam with a plane using the method of beam crossing with a triangle, which is implemented above.
Intersection intersectTriangle(Triangle triangle, Ray ray).
Intersection intersectPlane(Plane plane, Ray ray) {
Intersection i = intersectTriangle(plane.triangles[0], ray);
if(i.intersect) {
return i;
} else {
i = intersectTriangle(plane.triangles[1], ray);
if(i.intersect) {
return i;
} else {
return Intersection();
}
}
}
Method which calculates the intersection of the beam with an object of a triangular prism.
Intersection intersectTrianglePrism(TrianglePrism trianglePrism, Ray ray) {
Intersection t_min = Intersection();
Intersection t;
t = intersectTriangle(trianglePrism.triangles[0], ray);
if(t.intersect) {
if(t_min.intersect == false  t_min.distanse > t.distanse) {
t_min = t;
}
}
t = intersectTriangle(trianglePrism.triangles[1], ray);
if(t.intersect) {
if(t_min.intersect == false  t_min.distanse > t.distanse) {
t_min = t;
}
}
t = intersectPlane(trianglePrism.planes[0], ray);
if(t.intersect) {
if(t_min.intersect == false  t_min.distanse > t.distanse) {
t_min = t;
}
}
t = intersectPlane(trianglePrism.planes[1], ray);
if(t.intersect) {
if(t_min.intersect == false  t_min.distanse > t.distanse) {
t_min = t;
}
}
t = intersectPlane(trianglePrism.planes[2], ray);
if(t.intersect) {
if(t_min.intersect == false  t_min.distanse > t.distanse) {
t_min = t;
}
}
return t_min;
}
The function of ray tracing through the scene with triangular prism. This function is used in the main shader. The function replaces a recursive passage of ray tracing with a “while” cycle, as the Metal shader language doesn’t support the recursion. The result of this function is the intersection of the resulting beam with a skybox.
Intersection traceSceneTrianglePrism(SceneTrianglePrism scene, Ray ray) {
Intersection i1 = intersectTrianglePrism(scene.trianglePrism, ray);
bool intersectPrism = false;
int prismIntersectionCount = 0;
bool iterate = i1.intersect;
while(iterate == true) {
prismIntersectionCount++;
intersectPrism = true;
ray = i1.newRay;
i1 = intersectTrianglePrism(scene.trianglePrism, ray);
iterate = i1.intersect;
}
i1 = intersectSkybox(scene.skybox, ray);
i1.intersectPrism = intersectPrism;
i1.prismIntersectionCount = prismIntersectionCount;
return i1;
}
Shader
The next shader is used for the map generating in conjunction with an output (resulting) structure. That means that for the certain prism provision this shader is performed only for the first time, next time the structure is processed by the other shader, which uses a map to calculate an output texture.
kernel void trianglePrismRaytracer(texture2d<float, access::read> inTexture [[texture(0)]],texture2d<float, access::write> outTexture [[texture(1)]],
constant TrianglePrism &tp [[buffer(0)]],
device ImageMap &imageMap [[buffer(1)]],
constant Skybox &skybox [[buffer(2)]],
uint2 gid [[thread_position_in_grid]]){
// 1
float height = (float)inTexture.get_height();
float width = (float)inTexture.get_width();
// 2
if(gid.x > width  10 && gid.y > height  10) {
imageMap.needRegenerateMap = false;
}
// 3
float aspectRatio = height / width;
float2 textureCoordinateToUse = float2( (gid.x) / width, ((gid.y) / height) * aspectRatio);
// 4
Ray r = Ray(Point3D(0.5, 0.5 * aspectRatio, 0.0), Point3D(textureCoordinateToUse.x, textureCoordinateToUse.y, 1 * aspectRatio));
// 5
SceneTrianglePrism scene = SceneTrianglePrism(skybox, tp);
// 6
Intersection i1 = traceSceneTrianglePrism(scene, r);
if(i1.prismIntersectionCount) {
// 6.a
float2 positionR;
float2 positionG;
float2 positionB;
float maxWH = height > width ? height : width;
maxWH = maxWH / 5.0;
if(abs(i1.position.z  aspectRatio) < EPSILON) {
positionR = (i1.position  (i1.prismIntersectionCount / maxWH) * i1.direction).xy;
positionG = (i1.position).xy;
positionB = (i1.position + (i1.prismIntersectionCount / maxWH) * i1.direction).xy;
} else if(abs(i1.position.y  aspectRatio) < EPSILON  i1.position.y < EPSILON) {
positionR = (i1.position  (i1.prismIntersectionCount / maxWH) * i1.direction).xz;
positionG = (i1.position).xz;
positionB = (i1.position + (i1.prismIntersectionCount / maxWH) * i1.direction).xz;
} else if(abs(i1.position.x  aspectRatio) < EPSILON  i1.position.x < EPSILON) {
positionR = (i1.position  (i1.prismIntersectionCount / maxWH) * i1.direction).yz;
positionG = (i1.position).yz;
positionB = (i1.position + (i1.prismIntersectionCount / maxWH) * i1.direction).yz;
}
imageMap.map[gid.x][gid.y][0] = uint2(positionR.x * width, positionR.y * height / aspectRatio);
imageMap.map[gid.x][gid.y][1] = uint2(positionG.x * width, positionG.y * height / aspectRatio);
imageMap.map[gid.x][gid.y][2] = uint2(positionB.x * width, positionB.y * height / aspectRatio);
outTexture.write(float4(inTexture.read(imageMap.map[gid.x][gid.y][0]).r, inTexture.read(imageMap.map[gid.x][gid.y][1]).g, inTexture.read(imageMap.map[gid.x][gid.y][2]).b, 1), gid);
} else {
// 6.b
imageMap.map[gid.x][gid.y][0] = gid;
imageMap.map[gid.x][gid.y][1] = gid;
imageMap.map[gid.x][gid.y][2] = gid;
outTexture.write(inTexture.read(gid), gid);
}
}
Explanation to the code above:
 Get the height and width of the input texture.
 Condition of an output map generation stop.
 Conversion of texture coordinates, taking into account the ratio of height to width (aspect ratio).
 Create a beam object with the beginning at the point of camera location (0.5, 0.5, 0.0), with the direction to the current texture coordinates in the point z = 1.
 Create a scene object.
 Start the process of calculating the intersection of the beam with a prism, which returns an object “Intersection” with the characteristics of the beam current passing through the scene.
 If the section of the prism is found, which is checked by the number of crossings in the object “Intersection”, we calculate the RGB colors for the current pixel and store them in the map.
 If the intersection with the prism is not found  record the color of input texture for the current pixel in the map.
This shader can also be used for the other prisms: cube, pyramid, octahedron and others. In this case you need to write appropriate structures for these prisms, describe object scenes and realize the ray tracing function for the scene.
We are looking forward to seeing the release of new iPhone 6S GPU which will implement the ray tracing, that will allow us to make the small changes in the algorithm and to get excellent results as well.