Subversion Repositories gelsvn

\textit{An informal introduction to the GEL library with many examples of usage}.}

\begin{verbatim}

#include <HMesh/Manifold.h>

#include <HMesh/FaceCirculator.h>

#include <HMesh/VertexCirculator.h>

\end{verbatim}

\subsection{Extended Example: Edge Flipping}

The following example demonstrates how to create a Manifold and add polygons (in this case triangles) and finally how to flip edges of a manifold. First, let us define some vertices

\begin{verbatim}

	vector<Vec3f> vertices(3);

	vertices[0] = p1;

	vertices[1] = p2;

	vertices[2] = p3;

\end{verbatim}

and then a vector of faces. The faces vector contains the number of vertices of each face in the mesh we want tor produce. Initially, we want to make a mesh with just one single triangle, so we produce a vector of one element and set that element to 3.

\begin{verbatim}

vector<int> faces(1);

faces[0] = 3;

\end{verbatim}

Next, we need the index vector. This vector is a long list of indices to vertices. For each face, we store the indices to its vertices in this vector. Since we just have a triangle, we store three vertices in the vector.

\begin{verbatim}

vector<int> indices(3);

indices[0]=0;

indices[1]=1;

indices[2]=2;

\end{verbatim}

So, if we had had two triangles, we would have stored six indices. Finally, we call \texttt{build\_manifold} with the indexed face set data, we have compiled. 

\begin{verbatim}

build_manifold(mani,        	// The triangle mesh.

			 3,           		// Number of vertices.

			 &vertices[0],	// Pointer to vertices.

			 1,           		// Number of faces.

			 &faces[0],  	// Pointer to faces.

			 &indices[0]);	// Pointer to indices.

\end{verbatim}

The result of the above is a mesh with a single triangle. Note that \texttt{build\_manifold} is in

\begin{verbatim}

#include <HMesh/build_manifold.h>

\end{verbatim}

Next, we try to split an edge. We grab the first halfedge and split it: Now we have two triangles. Splitting the halfedge changes the containing triangle to a quadrilateral, and we call triangulate to divide it into two triangls again.

\begin{verbatim}

	HalfEdgeIter h = m.halfedges_begin();

	m.split_edge(h);

	m.triangulate(h->face); 

\end{verbatim}

Now, we obtain an iterator to the first of our (two) triangles.

\begin{verbatim}

	FaceIter f1 =m.faces_begin();

\end{verbatim}

We create a vertex, \texttt{v}, at centre of \texttt{f1} and insert it in that face:

\begin{verbatim}

	VertexIter v=m.create_vertex(centre(f1));

	m.face_insert_point(f1,v);

\end{verbatim}

The code below, marks one of a pair of halfedges (with the value 1).

\begin{verbatim}

for(HalfEdgeIter h = m.halfedges_begin(); h!=m.halfedges_end(); ++h)

  h->touched =0;

for(HalfEdgeIter h = m.halfedges_begin(); h!=m.halfedges_end(); ++h)

  if(h->opp->touched == 0)

    h->touched = 1;

\end{verbatim}

Next, we set the \texttt{flipper} variable to point to the first of these halfedges:

\begin{verbatim}

	flipper = m.halfedges_begin();

\end{verbatim}

The long piece of code below examines a halfedge pointed to by \texttt{flipper}, and if it is not a boundary halfedge it tries to flip it. Then it increments the \texttt{flipper} variable until it lands on a halfedge marked with 1. If \texttt{flipper} reaches the end of the list of halfedges, we start over.

\begin{verbatim}

if(is_boundary(flipper))

  cout << "boundary edge: could not flip" << endl;

else

  if(!m.flip(flipper))

    cout << "could not flip" << endl;

do

{

  ++flipper;

  if(flipper==m.halfedges_end())

    flipper = m.halfedges_begin();

}

while(flipper->touched == 0); 

\end{verbatim}

\subsection{Extended Example: Implicit Surface Polygonization}

This example demonstrates how we can produce an HMesh Manifold from an implicitly defined object. Say, we have some function, \texttt{f}, which represents an object by what we sometimes call a characteristic function (\texttt{f<0} inside the object, \texttt{f>0} outside, \texttt{f=0}  on the surface). We wish to extract the 0 set as a Manifold.

First, we create a 3D grid of floating point values as shown below.

\begin{verbatim}

RGrid<float> grid(Vec3i(N,N,N)); // Voxel grid on which to sample 

\end{verbatim}

We sample \texttt{f} on that grid

\begin{verbatim}

for(int i=0;i<N;++i)

  for(int j=0;j<N;++j)

    for(int k=0;k<N;++k)

      grid[Vec3i(i,j,k)] = f(i,j,k);

\end{verbatim}

Next, we call a function which polygonizes the 0 set. The first two arguments are the grid and the manifold, the third argument is set to 0, since we want the zero level set, and the final argument tells the polygonizer to push the vertices onto the zero set (as opposed to leaving them in their initial position which is close to but not actually on the zero set).

\begin{verbatim}

cuberille_polygonize(grid, mani, 0.0, true);

\end{verbatim}

In post-processing, we triangulate \texttt{mani} and remove ugly triangles. Caps are triangles with one big angle (close to 180 degrees). Needles are triangles with one very short edge.

\begin{verbatim}

triangulate(mani);

remove_caps_from_trimesh(mani, M_PI * 0.85);

remove_needles_from_trimesh(mani, 1e-2);

\end{verbatim}

Note that you need the following header files:

\begin{verbatim}

#include <Geometry/RGrid.h>

#include <HMesh/volume_polygonize.h>

\end{verbatim}

to use the grid and the polygonizer, respectively.

\section{GLGraphics}

GLGraphics contains a set of tools needed for visualization of geometrical objects. In particular, this namespace contains mesh rendering facilities, and in the following, a very simple example is given. This section is basically a walk through of the simplest GEL program that draws a mesh. Apart from GEL, we also use OpenGL and that requires a toolkit for connecting with the window system. With GEL programs, one generally uses GLUT, and this example is not an exception.

For starters, we need to include some files mostly from GLGraphics but also the header file for the mesh load function of HMesh and the GLEW header. Why incude glew.h rather than just gl.h? Well, HMesh/draw.h contains some draw functions which rely on shaders, and since gl.h is normally not up to date, it makes sense to use glew.h instead of gl.h even though it inflicts a dependency. We include GLGraphics/gel\_glut.h rather than the normal glut.h. That is because the GEL version works the same on Windows, OSX, Linux and probably other platforms.

We also open the namespaces we will need and declare two globals: The view controller \texttt{view\_ctrl} and the mesh \texttt{mani}. The view controller class is rather complex. It more or less insulates you from having to deal directly with the projections and transformations of OpenGL: It sets up a perspective projection and also the modelview transformation needed to view the object. From a user interface perspective, it defines a virtual trackball which allows you to rotate the object.

\begin{verbatim}

#include <GL/glew.h>

#include <GLGraphics/gel_glut.h>

#include <GLGraphics/draw.h>

#include <GLGraphics/GLViewController.h>

#include <HMesh/load.h>

using namespace std;

using namespace HMesh;

using namespace CGLA;

using namespace GLGraphics;

GLViewController* view_ctrl;

Manifold mani;

\end{verbatim}

Below is the display function which is called from the GLUT event loop whenever an event that requires redrawing is received. All drawing takes place inside this function. In this case, it is simple since all we need to do is clear the screen (and depth buffer), set up a new modelview transformation with the view controller and then call the draw function followed by a swap of buffers.

The draw function sends the polygons to the graphics card. It is very inefficient and uses the fixed function pipeline. At a minimum one should draw the polygons to a display list, but for a simple example, this works. The buffer swap is because we use double buffering; in other words, we draw to the back buffer.

\begin{verbatim}

void display() {

    glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);

    view_ctrl->set_gl_modelview();

    draw(mani);

    glutSwapBuffers();

}

\end{verbatim}

The mouse callback below is called when a mouse event has occurred. This is where user input  for the virtual trackball is registered. We check whether a mouse is pressed or released. If it is pressed, we detect which button and then ``grab'' the virtual trackball in order to rotate, zoom, or pan depending on which button is pressed. If the button is released, we inform the view controller of this.

\begin{verbatim}

void mouse(int button, int state, int x, int y)  {

    Vec2i pos(x,y);

    if (state==GLUT_DOWN) 

    {

        if (button==GLUT_LEFT_BUTTON) 

            view_ctrl->grab_ball(ROTATE_ACTION,pos);

        else if (button==GLUT_MIDDLE_BUTTON) 

            view_ctrl->grab_ball(ZOOM_ACTION,pos);

        else if (button==GLUT_RIGHT_BUTTON) 

            view_ctrl->grab_ball(PAN_ACTION,pos);

    }

    else if (state==GLUT_UP)

        view_ctrl->release_ball();

}

\end{verbatim}

If the mouse moves with a button depressed, we register motion in the function below. The new mouse position is sent to the view controller

which then, e.g., rotates the trackball accordingly. Note that this function ends by posting a redisplay event, i.e. informs GLUT that display should be called at the earliest convenience.

\begin{verbatim}

void motion(int x, int y) {

    Vec2i pos(x,y);

    view_ctrl->roll_ball(Vec2i(x,y));

    glutPostRedisplay();

}

\end{verbatim}

Finally, in the main function, we first load the mesh and then setup glut. This mostly involves defining the callback function just described. We set up the view controller passing it window dimensions and the size and position of the bounding sphere of the object just loaded. Finally, we do some minimal OpenGL set up: Essentially clearing the depth buffer and enabling lights. Finally, we pass control to the GLUT event loop.

\begin{verbatim}

int main(int argc, char** argv) {

    string file = "bunny-little.x3d";

    load(file, mani);

    glutInitDisplayMode(GLUT_RGBA|GLUT_DOUBLE|GLUT_DEPTH);

    glutInitWindowSize(800, 800);

    glutInit(&argc, argv);

    glutCreateWindow("GEL Example Program");

    glutDisplayFunc(display);

    glutMouseFunc(mouse);

    glutMotionFunc(motion);

    Vec3f bsphere_center(0,0,0);   

    float bsphere_radius = 3;

    mani.get_bsphere(bsphere_center,bsphere_radius);

    view_ctrl = new GLViewController(800,800, 

        bsphere_center,bsphere_radius*2);

    glClearColor(0.0f, 0.0f, .5f, 0.f);

    glEnable(GL_DEPTH_TEST);

    glEnable(GL_LIGHTING);

    glEnable(GL_LIGHT0);

    glutMainLoop();

}

\end{verbatim}

Note that the mesh can be either an X3D, OBJ, PLY, or OFF files. However, only the geometry is loaded not the textures. In the case of OBJ files, we also convert all polygons to triangles, because the TriMesh loader (see the geometry class) is in fact used.

Apart from the drawing functions and the viewcontroller, GLGraphics also contains  other useful pieces: A few functions which greatly simplify shader loading and SOIL. SOIL is a small library for loading images. It is designed for OpenGL and makes it easy to e.g. save screen shots or load an image for use as a texture. While the need for image loading is fairly obvious, it might be more difficult to see the need for shader loading functions. However, it \textit{is} a little tricky to make shader programs in C++ using GLSL but the problems are almost all silly little things. For instance, how do you robustly read from a text file? How do you compile a shader and check for errors? In OpenGL What is the difference between a GLSL program and a shader anyway?

The short answer to the last question is this: A "shader" can be either a vertex shader, a geometry shader (in OpenGL 2.0) or a fragment shader. A "program" is a linked combination of these three types of shaders. Note that you don't have to have a geometry shader.

These functions attempt to obviate the need for an answer to the first two questions by providing an API for loading and compiling shaders and checking for errors. However, I don't include functions for creating the program, attaching shaders and linking. Why not? Because the need for flexibility means that the API would be just as complex as just using the OpenGL functions directly! However, loading shaders and checking for errors in compiled shaders is different. It makes sense to wrap that. It also makes sense to wrap the error checking for programs that are linked, so there is a function for that too.

Since shader loading and error check sandwhich the two calls needed for compilation, the most important function in this API, \texttt{create\_glsl\_shader}, loads a shader, compiles it, checks for errors and returns the shader handle. There is also a version which creates a shader from a string.

There is some code below to illustrate usage.	

\begin{verbatim}

GLuint vs = create_glsl_shader(GL_VERTEX_SHADER, 

  shader_path, "tri.vert");

GLuint gs = create_glsl_shader(GL_GEOMETRY_SHADER_EXT, 

  shader_path, "tri.geom");

GLuint fs = create_glsl_shader(GL_FRAGMENT_SHADER, 

  shader_path, "tri.frag");

prog_P0 = glCreateProgram();

if(vs) glAttachShader(prog_P0, vs);

if(gs) glAttachShader(prog_P0, gs);

if(fs) glAttachShader(prog_P0, fs);

// Specify input and output for the geometry shader.

// Note that this must be done before linking the program.

glProgramParameteriEXT(prog_P0,GL_GEOMETRY_INPUT_TYPE_EXT,

  GL_TRIANGLES);

glProgramParameteriEXT(prog_P0,GL_GEOMETRY_VERTICES_OUT_EXT,3);

glProgramParameteriEXT(prog_P0,GL_GEOMETRY_OUTPUT_TYPE_EXT,

  GL_TRIANGLE_STRIP);

// Link the program object and print out the info log

glLinkProgram(prog_P0);

print_glsl_program_log(prog_P0);

// Install program object as part of current state

glUseProgram(prog_P0);

// Set the value of a uniform

glUniform2f(glGetUniformLocation(prog_P0,"WIN_SCALE"), 

  win_size_x/2.0, win_size_y/2.0);

\end{verbatim}

\section{LinAlg}

Sometimes the simple 2,3,4 dimensional vectors from CGLA just don't cut it. We often need to solve large linear systems. The LinAlg namespace contains some vector and matrix classes and an interface to Lapack. This provides fairly easy way to do many numerical computations.

In the example below, we  find coefficients for $a x^2 + b y^2 +cxy + dx + ey + f$ such that the surface contains six specific points. The coefficients are found by solving the linear system $\mathbf A \mathbf x = \mathbf b$ where the rows of the $\mathbf A$ matrix contains $x^2 \; y^2 \; xy \; x \; y \; 1$ computed from the $xy$ positions of each point, $\mathbf x$ contains the unknown coefficients, and $\mathbf b$ on the right hand side contains the $z$ values of the six points. Using LinAlg, we implement it as follows: 

\begin{verbatim}

    CMatrix A(6,6);

    CVector b(6);

    for(int i=0;i<6;++i)

    {

        A.set(i,0,pts[i][0]*pts[i][0]);

        A.set(i,1,pts[i][1]*pts[i][1]);

        A.set(i,2,pts[i][0]*pts[i][1]);

        A.set(i,3,pts[i][0]);

        A.set(i,4,pts[i][1]);

        A.set(i,5,1);

        b[i] = pts[i][2];

    }

    CVector x;

    LinearSolve(A,b,x);

\end{verbatim}

While this example shows only the function for solving a system which should have a solution, there are also functions for solving overdetermined systems in the least square sense and finding the minimum norm solution to underdetermined systems using singular value decomposition. There is also a function for finding eigenvalues and eigenvectors of symmetric matrices and more.

\section{Geometry}

The Geometry namespace contains many different classes and functions. Roughly, we can divide the contents into

\begin{itemize}

\item Spatial data structures such as kd tress, bounding box hierarchies, and BSP trees.

\item A Triangle mesh data structure called TriMesh. TriMesh is different from HMesh in that it only contains triangles. It is much more an API for real time rendering which also facilitates material properties and not just geometry.

\item Classes and functions for dealing with volume data. HGrid and RGrid are, respectively, a class for hierarchically stored voxel grids (sparse grids) and regular grids. There is a number of functions for traversing voxel grids systematically and along rays.

\item Surprisingly, you will also find my C++ port of Jules Bloomenthals isosurface polygonizer and an implementation of Luiz Velho's parametric surface tiler in this namespace.

\end{itemize}

One of the most frequently used tools in Geometry is the kD tree class which merits an example. In the code below, we create a kD tree which had \texttt{Vec3f}s as keys and integers as data. Note that since the kD tree is a template, we could use any other type as both key and data, however, only CGLA vectors have been tested as key types, but there are no restrictions on data types.

\begin{verbatim}

    KDTree<Vec3f,int> tree;

    for(int i=0;i<N;++i)

        {

            Vec3f p0;

            make_ran_point(p0);

            tree.insert(p0, i);

        }

    tree.build();

\end{verbatim}

Note also, that before we use the tree it needs to be built. This is because the internal representation is a balanced binary heap which it is easier to build at the end rather than maintain during insertion of new points. To look for the points near a given point, we can call

\begin{verbatim}

    Vec3f p0;

    // ...

    std::vector<Vec3f> keys;

    std::vector<int> vals;

    float radius = 1.95f;

    int N = tree.in_sphere(p0, radius , keys, vals);

\end{verbatim}

This will find all points in a radius of 1.95 units from \texttt{p0}. The keys and values are stored in \texttt{keys} and \texttt{vals} when the functions returns. The return value of the function is the number of points found within the radius. 

Sometimes, we simply want the point closest to a given point \texttt{p0} which is done using \texttt{tree.closest\_point(p0, d, pos, x)} where the two first arguments indicate the point and the maximum search radius. The two last arguments are set to the key and data of the point found to be closest to \texttt{p0}. The function returns true if a closest point was found.

\section{Util}

The Util namespace contains a rather mixed bag of utilities many of which are quite useful and very diverse. 

\begin{trivlist}

\item The XML parser for instance is written from scratch and the basis for our X3D loader although it will load any XML file. 

\item \texttt{Grid2D} is often useful when we want to deal with e.g. simulation on a 2D grid. 

\item The \texttt{Timer} class is nearly indispensable when we need to time something, and it is very easy to use. 

\item \texttt{ArgExtracter} is a class for getting the command line arguments to a program. 

\item There is more - for instance a resource manager template, some string utility templates and a hash table implementation.

\end{trivlist}

Arguably, it would be more pretty if these pieces had been more thematically linked, but many are used a lot, and it seemed reasonable to have somewhere to stick various functions and classes that did not naturally belong elsewhere.