SIGSEGV

Final adjustments

Sat, 20 May 2017 00:00:00 +0000

The final adjustments to this small project comprehended a refactoring of the folder structure and the addition of a small portion of code to recompute the normals of the vertices composing the cloth mesh at each time step. This was necessary to achieve a correct illumination of the mesh. The strategy employed consisted in resetting the normals to a zero-vector and then recomputing the one of each vertex as an average of the normals of the different triangles the vertex belongs to. The computation is done on each triangle using the cross product of two sides. This methods tries to create a smooth looking surface even though it is effectively composed by triangular sections.

// Reset normals
...
// Recompute normals
for (unsigned int i = 0; i < stripCount; i++) {
    for (unsigned int j = 0; j < hres - 1; j++) {
        index = i * hres + j;

        // Upper triangle of the quad
        norm = glm::cross(
            vertices[index + hres].position - vertices[index].position,
            vertices[index + 1].position - vertices[index].position
        );
        vertices[index].normal += norm;
        vertices[index + 1].normal += norm;
        vertices[index + hres].normal += norm;

        // Lower triangle of the quad
        norm = glm::cross(
            vertices[index + 1].position - vertices[index + hres + 1].position,
            vertices[index + hres].position - vertices[index + hres + 1].position
        );
        vertices[index + 1].normal += norm;
        vertices[index + hres].normal += norm;
        vertices[index + hres + 1].normal += norm;
    }
}
// Normalize normals
for (auto it = vertices.begin(); it != vertices.end(); it++)
    it->normal = glm::normalize(it->normal);

The result can be seen in the short video below in which the cloth assumes shaded or bright colors depending on the position of the particles relative to the light source.

The code of the whole project will be made public on this repository as soon as the final grade for the course DH2323 is registered.

Collision detection

Wed, 17 May 2017 00:00:00 +0000

I decided to implement collision detection and response for two different objects: a sphere and a cube. For the sphere mesh, detecting collision is very simple: it is sufficient to check if the distance between a particle and the center of the sphere is less than the radius of the sphere. In case this test is positive, the particle is translated back to the point of the sphere defined as the intersection between its surface and the line on which lies the vector joining the center with the particle. It must be noted that in order to avoid glitching surface intersections in the rendering phase, the radius used to detect the collision is slightly larger than the actual radius of the sphere.

void Sphere::collide(Particle& p) const {
    glm::vec3 direction = p.v.position - center;
    if (glm::length(direction) < collision_radius) {
        p.resetPosition(glm::normalize(direction) * collision_radius + center);
    }
}

Moving to the cube mesh, the strategy employed could be considered as a custom application of the slabs method. It must be noted that this mesh is defined to always be aligned to the world axis so that an AABB could be used. The collision is detected by evaluating the vector between the center of the cube and the particle and then checking if its components are shorter than the dimensions of the bounding box (just like in the previous case, the box size is slightly larger than the actual mesh). If the particle is found to be inside the cube, the previously evaluated vector is extended and then clipped to find its intersection with the bounding box which is then used as new position for the particle.

void Cube::collide(Particle& p) const {
    glm::vec3 ray = p.v.position - center;
    if (glm::abs(ray.x) < halfsideColl
     && glm::abs(ray.y) < halfsideColl
     && glm::abs(ray.z) < halfsideColl) {
        ray = glm::normalize(ray) * halfsideColl * 2.0f;
        if (glm::abs(ray.x) > halfsideColl && ray.x != 0.f)
            ray *= halfsideColl / glm::abs(ray.x);
        if (glm::abs(ray.y) > halfsideColl && ray.y != 0.f)
            ray *= halfsideColl / glm::abs(ray.y);
        if (glm::abs(ray.z) > halfsideColl && ray.z != 0.f)
            ray *= halfsideColl / glm::abs(ray.z);
        p.resetPosition(center + ray);
    }
}

(I hope you will forgive me, but I could not resist texturing the mesh as a Companion Cube)

Constraint system

Thu, 11 May 2017 00:00:00 +0000

In the previous post I presented the issue of the “explosive” nature of my mass-spring model when using strong springs. This had to be addressed somehow in order to build a stable simulation and the possible ways which I could come up with to solve the problem were basically three: give up the idea of an interactive demo and use small fixed time steps, change the integration method to an implicit one or change the physics model for the cloth. The first option did not look appealing since one of the premises of this small project was to have a real time demonstration and the second was not really employable as well due to the complexity which would have introduced. As a consequence, looking for alternatives to a spring based system, I ended up reading about the possibility to use a simple fixed constraint system. This basically meant to substitute each spring with a constraint trying to keep the distance between the two particles attached at each end constant. The code portion applying Hooke’s law was then replaced with:

void Particle::offsetPosition(const glm::vec3& offset) {
    if (!fixed) v.position += offset;
}

...

void Spring::update() {
    // Non-elastic constraint
    glm::vec3 direction = b.v.position - a.v.position;
    glm::vec3 correction = direction * (1 - restLen / glm::length(direction));
    if (!(a.isFixed() || b.isFixed())) correction *= 0.5f;
    a.offsetPosition(correction);
    b.offsetPosition(-correction);
}

First the vector between the two particles is evaluated and it is then used to calculate the amount of correction needed to bring the particles back to the rest distance (in case one of the particles is fixed, the correction factor for the other particle is doubled). Since these constraints are rigid and directly modify the position of the particle, in order to find a state satisfying all the ones defining the cloth object at the same time, it would be necessary to solve a very large linear system. Fortunately this can avoided by “relaxing” the system and this is achieved by applying the constraint rules iteratively:

for (int i = 0; i < ITERATIONS; i++) {
    for (auto it = springs.begin(); it != springs.end(); it++) {
        it->update();
    }
}

Obviously the number of iteration cannot be too large since it would significantly slow down the simulation, but, by manual testing, a value between 3 and 5 iteration was found to be sufficient to achieve a good looking result. The result is shown in the short video clip below, where the top-left corner of the cloth is fixed and the top-right corner is moved back and forth to demonstrate the flexibility of the mesh.

Now that the cloth object is ready, it is possible to start thinking about implementing in it collision detection and response.

The mass-spring model

Tue, 09 May 2017 00:00:00 +0000

It is now time to start creating a mesh with cloth-like properties. The technique which will be employed to achieve that is called Mass-Spring Model since it uses a system of springs and particles to simulate the flexibility of fabric materials. The particles are disposed as a 2-dimensional grid and are connected using horizontal, vertical and oblique springs as shown in the image below.

This structure provides to the cloth flexibility and at the same time should not allow too big deformation (which would not look natural). Once the system is in place, we need to define the physics to control its behavior. First, each particle is subjected to the force of gravity, which can be represented just as a vector point down on the Y axis, then the internal forces generated by the springs must be evaluated. This is done using Hooke’s law which states that the force generated by a spring is proportional to its displacement times the spring constant: F = K * dx. This force is then applied in opposite directions to the two particles attached to the ends of the springs. After calculating the forces in place, those must be applied using the equations of motion to evaluate the position of the particles at the next time step. Different integration methods exist to perform this operation and they are mainly divided in two categories: explicit methods and implicit methods. The first ones derive the next state of the system from the current one and are usually easy to compute though often leading the mathematical instability. The seconds use both the current and the future state in the calculations and are usually more precise and stable though being more computationally complex. The final decision was made in favor of the Verlet explicit integration method as it was suggested by different sources for providing solid results:

dx = (position - old_position) * (1 - DAMP) + acceleration * dt * dt

In the formula, position is the current position in 3D space of the particle, old_position is the position at the previous time step, DAMP is a dampening factor and acceleration is the acceleration derived from the forces accumulated on the particle. After implementing this, we were ready to execute the cloth simulation for the first time and the results is shown in the short video clip below.

It is clear that the cloth is stretching too much because the forces generated by the springs are not strong enough to balance with the acceleration of gravity. To correct this behavior, the spring constants were incremented and this caused the previously mentioned instability problems to verify as shown in the clip below. The reason for this is that the employed equations are so called stiff which means that when plugging in large numerical values (big time steps or forces) they have the tendency to diverge to infinite values.

In the next posts I will try to find a good strategy to solve these issues and have a stable model and, successively, implement collision detection for the cloth object.

Time to move around

Tue, 02 May 2017 00:00:00 +0000

As I said in the previous post, the natural next feature to add to this little piece of software is the ability for the user to move around in the scene. The first thing to do is to get input from keyboard and mouse and, fortunately, SDL2 provides a very simple interface for that:

int mousedx, mousedy;
Uint8* keystate = SDL_GetKeyboardState(NULL);
SDL_GetRelativeMouseState(&mousedx, &mousedy);

Now that we have this input information it is possible to translate it into transformations of the camera object. For translation the keys WASD were used and, depending on the key pressed, the camera center is translated alongside the forward vector or the cross product between the forward and the up vectors (which will end up pointing to the right of the view). The amount of movement is evaluated taking into account the time passed from the last frame and multiplying it for a fixed velocity value. A bit more work is necessary to calculate the camera rotation from the mouse input, but it is not too complicated overall. First, it is necessary to transform the mouse movement on the screen from pixels to radians. Then the forward vector is recalculated accordingly to spherical coordinates while the up vector can be left lying on the Y axis just modifying its orientation in case the view goes upside down.

// Eval rotation angle in radians
angle.x += glm::radians((dx / screenSize.x) * fov.x);
angle.y += glm::radians((dy / screenSize.y) * fov.y);
// Update forward and up vectors
forward.x = glm::cos(angle.y) * glm::sin(angle.x);
forward.y = -glm::sin(angle.y);
forward.z = -glm::cos(angle.x) * glm::cos(angle.y);
up.y = glm::cos(angle.y) < 0.0f ? -1.0f : 1.0f;

The result can be observed in the short video demonstration below.

Now everything is really ready and probably the next post will start discussing about cloth physics.

We can see something

Sun, 30 Apr 2017 00:00:00 +0000

Quite a lot of progress happened from the first post, but I have not felt the necessity to write about it since most of the code I wrote is just boilerplate to setup the environment. Just to make short summary:

Setup SDL2 together with OpenGL to have a window on which meshes can be drawn.
Created a class to load and compile vertex and fragment shader which will be used in the graphics pipeline to render images.
Created a class to read images from files and load them in GPU memory as textures.
Created a class to represent the camera in the 3D OpenGL world (with position, FOV, far plane, etc.).
Created a structure to represent a white omni light with 3D position and intensity.

Now that the foundations have been built, we can start drawing meshes on the screen. The building block will be the Vertex data structure which represents a point in 3D space with its normal vector and corresponding texture coordinates.

struct Vertex {
    glm::vec3 position;     // Position of the vertex in 3D space
    glm::vec2 texCoord;     // UV texture coordinate
    glm::vec3 normal;       // Normal vector to the surface the vertex defines
};

With this piece of data defined, the next step is to write shader code to instruct the GPU on how to handle it. The Vertex Shader is going to take as input the vertex data and the various model-view-perspective parameters and evaluate the vertex projection. Moreover, to allow the following lighting calculation, the vertex components will also be transformed in varying data which will then be automatically interpolated and passed to the Fragment Shader

attribute vec3 position;        // Position of the vertex
attribute vec2 texCoord;        // UV texture coordinates
attribute vec3 normal;          // Normal vector to the vertex

varying vec2 texCoord0;         // To interpolate UV values
varying vec3 position0;         // To interpolate position values
varying vec3 normal0;           // To interpolate normal values

uniform mat4 perspective;       // Camera perspective matrix
uniform mat4 model;             // Transformation matrix
uniform mat4 view;              // Camera view matrix

void main() {
    // Evaluate model view matrix
    mat4 model_view = view * model;
    // Evaluate vertex projection
    gl_Position = perspective * model_view * vec4(position, 1.0);
    // Copy values to interpolate
    position0 = (model_view * vec4(position, 1.0)).xyz;
    normal0 = transpose(inverse(mat3(model_view))) * normal;
    texCoord0 = texCoord;
}

The Fragment Shader implements Lambertian lighting model to evaluate the color of a pixel. It takes as input the texture data, the light position and intensity and the interpolated values passed from the Vertex Shader.

varying vec2 texCoord0;             // Interpolated UV texture coordinate
varying vec3 position0;             // Interpolated vertex position
varying vec3 normal0;               // Interpolated vertex normal

uniform sampler2D diffuse;          // Texture
uniform vec3 light_pos;             // Position of omni light in 3D space
uniform float light_intensity;      // Intensity of omni light

void main() {
    // Evaluate light ray
    vec3 r = (position0 - light_pos);
    // Evaluate direct illumination
    float direct = light_intensity * max(-dot(normalize(r), normal0), 0.0) / (4 * 3.14 * dot(r, r));
    // Evaluate fragment color
    gl_FragColor = texture2D(diffuse, texCoord0) * (direct + 0.1);
}

Now all the pieces of the puzzle are in place and it is possible to actually start sending data to the GPU. My first draw attempt was dome by simply sending a buffer with 3 vertices and using GL_TRIANGLES as draw method (as you may notice, I chose the Swedish flag as texture):

A textured triangle is nice but not too much interesting, so the next mesh I tried to draw was a sphere. I achieved that by creating a bi-dimensional array of vertices and by disposing them using spherical coordinates. To effectively display the mesh, I took each couple of rows in the bi-dimensional array and rendered that using GL_TRIANGLE_STRIP as draw method. And, again, I used the Swedish flag as texture:

The system seems ready to display more or less any kind of geometry. The next step will be to add the possibility for the user to move around and explore the scene. After that, everything will be ready to start working on creating a small physics system for cloth simulation.

Hello World

Fri, 28 Apr 2017 00:00:00 +0000

All projects must start somewhere, and when you are a software developer they usually do with that familiar “Hello World!” on a black terminal. This is the first post for what will a blog telling the progress of my small project for the 2017 instance of the course DH2323 Computer Graphics and Interaction. The project specification has been sent and I am now waiting for it to be approved. If everything goes as expected, this blog will describe the creation of a cloth simulation using the OpenGL graphics library.