Subversion Repositories gelsvn

\href{http://www.imm.dtu.dk/GEL/}{http://www.imm.dtu.dk/GEL/}

This document pertains to the version of GEL which is distributed on CampusNet for 02585. This version of GEL comes with project files for Visual Studio 9 and XCode and examples relevant for the course are included in the distribution.

GEL is not sufficiently documented, but a fair amount of Doxygen documentation is provided for those parts of GEL which are used a lot. The goal of this document is to provide more detail and to help people getting started. In particular, this document focuses on functionality in the CGLA and HMesh namespaces, but we shall also take a look at some other parts of GEL. Unfortunately, it is rather difficult to be complete: There is functionality in GEL not covered here. Consequently, if you are looking for something particular, we \textbf{entreat }you to look at the Doxygen web (start at the GEL homepage). Most functions and classes are in fact described in the auto-generated documentation.

GEL is not documented as well as we would like, but a fair amount of Doxygen documentation is provided for those parts of GEL which are used a lot. You will find the reference manual at \href{http://www2.imm.dtu.dk/courses/02585/GELref/index.html}{http://www2.imm.dtu.dk/courses/02585/GELref/index.html}

Another strong point of GEL is the fact that it contains good support for converting between representations; especially between meshes and voxel grids. There are several tools for polygonizing isosurfaces and also converting meshes to distance fields.  The tools pertaining to the Manifold data structure are in the HMesh namespace. The other geometry related tools are in the Geometry namespace.

Please use it. Autogenerated documentation is not eminently readable, but it is much better than no documentation and it should be relatively complete for the parts of GEL needed in the course. 

Apart from the namespaces (sublibraries) we have a number of demo applications. Some of these might be useful in themselves. One example is a tool for converting a mesh to a signed distance field and an OBJ viewer  which is also able to load X3D and PLY meshes. We are working on the MeshEdit application which is already a highly useful swiss knife for geometry processing.

The goal of \textit{this} document is to provide more detail and to help people getting started. In particular, this document focuses on functionality in the CGLA and HMesh namespaces, but we shall also take a look at some other parts of GEL. Unfortunately, it is rather difficult to be complete: There is functionality in GEL not covered here. Consequently, if you are looking for something particular, we \textbf{entreat } you to look at the reference linked to above

\section{Compilation and Installation}

GEL contains many tools for geometry processing and a number of data structures. Perhaps the most important is the \texttt{Manifold} class which resides in the \texttt{HMesh} namespace. A \texttt{Manifold} is a halfedge based representation of a polygonal mesh. There is also a simpler triangle mesh data structure, \texttt{TriMesh}, based on an indexed face set. There are several voxel grid data structures, a fairly efficient k-D tree for storing points, bounding box hierarchies etc.

Life would be easier if one's library did not rely on dependencies. We try hard to have only a minimal set, but the following libraries \textit{are} required in order to build GEL. 

A number of algorithms exist for manipulating these representations of geometric data. For instance, \texttt{Manifold} has a function for mesh simplification, several functions for smoothing (including anisotropic), mesh optimization, and mesh clean up.

OpenGL is typically installed on any platform. GLUT is typically available for any platform. A replacement such as FreeGLUT should be an option. Lapack is typically also available everywhere. The only problem is GLConsole. As of writing only MeshEdit depends on GLConsole which can be obtained from SourceForge:

Another strong point of GEL is the fact that it contains good support for converting between representations; especially between meshes and voxel grids. There are several tools for polygonizing isosurfaces and also converting meshes to distance fields.  The tools pertaining to the Manifold data structure are in the \texttt{HMesh} namespace. The other geometry related tools are in the \texttt{Geometry} namespace.

\href{http://sourceforge.net/projects/glconsole/}{http://sourceforge.net/projects/glconsole/}

There are two packages for linear algebra: \texttt{CGLA} is strictly for small vectors and matrices (dimensions 2,3, and 4). \texttt{LinAlg} is a Lapack wrapper for slightly larger problems. At this point, it is fairly simple but includes a number of functions for solving linear systems, factoring matrices and finding eigensolutions for symmetric matrices.

GLConsole is extremely convenient but a well kept, little documented secret. Please do not try to install it unless you need MeshEdit. We will update this text if we either include it in GEL (assuming the authors allow it) or change to some other library.

\texttt{GLGraphics} contains facilities for drawing entities from other parts of GEL via OpenGL. Especially \texttt{TriMesh} and Manifold have good support. For instance, there is a nice wireframe drawing class. There are also two virtual trackballs for interactive programs and some tools for viewing in interactive programs and SOIL a small open source library for image loading by Jonathan Dummer.

GEL is compiled using CMake. Currently CMake is the official way of producing Visual Studio Solution files. A separate Mac OSX XCode project file is also maintained but may be removed if CMake makes it redundant. A set of Makefiles for various unices are also found in the package but no longer maintained.

Finally there are some utilities in \texttt{Util}: Getting command line arguments, hash table classes, a 2D grid class, a resource manager, an XML parser by Jeppe Frisvad and other tools.

CGLA is a set of numerical C++ vector and matrix classes and class

\texttt{CGLA} is a set of numerical C++ vector and matrix classes and class

templates designed with computer graphics in mind. CGLA stands for

templates designed with computer graphics in mind. \texttt{CGLA} stands for

Well, CGLA evolved from a few matrix and vector classes because I

Well, \texttt{CGLA} evolved from a few matrix and vector classes because I

didn't have anything better. Also, I created CGLA to experiment with

didn't have anything better. Also, I created \texttt{CGLA} to experiment with

feature of CGLA, namely the fact that all vector types are derived

feature of \texttt{CGLA}, namely the fact that all vector types are derived

It is important to note that CGLA was designed for Computer Graphics 

It is important to note that \texttt{CGLA} was designed for Computer Graphics 

of dimension 2,3, or 4 CGLA was designed for vectors of low

of dimension 2,3, or 4 \texttt{CGLA} was designed for vectors of low

is decided by its type at compile time. CGLA does not use dynamic

is decided by its type at compile time. \texttt{CGLA} does not use dynamic

memory. CGLA also does not use virtual functions, and most functions

memory. \texttt{CGLA} also does not use virtual functions, and most functions

are inline. These features all help making CGLA relatively fast. 

are inline. These features all help making \texttt{CGLA} relatively fast. 

a template (\texttt{ArithVec})that gets both type

a template (\texttt{ArithVec}) that gets both type

From a users perspective CGLA contains a number of vector and matrix

From a users perspective \texttt{CGLA} contains a number of vector and matrix

Vectors in CGLA are named \texttt{VecDT} where \texttt{D} stands for

Vectors in \texttt{CGLA} are named \texttt{VecDT} where \texttt{D} stands for

If you need a given CGLA class you can find the header file that

If you need a given \texttt{CGLA} class you can find the header file that

the class. Remember also that all CGLA functions and classes live in

the class. Remember also that all \texttt{CGLA} functions and classes live in

the CGLA namespace! Lastly, look at the example programs that came

the \texttt{CGLA} namespace! Lastly, look at the example programs that came

that I haven't defined. If so, it is fortunate that CGLA is easy to

that I haven't defined. If so, it is fortunate that \texttt{CGLA} is easy to

takes the dot product. Finally the vector is normalized using the

arguments. Finally the vector is normalized using the

HMesh's \texttt{Manifold} class is a halfedge based mesh data structure. This type of data structure restricts you to manifolds, but allows for general N-gons for arbitrary N and makes manipulation somewhat simpler than other types of data structures for meshes.  Note that this particular implementation does not allow more than one loop per face. 

HMesh's \texttt{Manifold} class is a halfedge based mesh data structure. To use the basic functionality you need to include the Manifold.h header and use the appropriate name space:

for(FaceIter f = m.faces_begin(); f != m.faces_end(); ++f)

#include <Manifold.h>

  f->touched = -1;

using namespace HMesh;

The loop above visited each face f of m and assigned -1 to a variable called touched. The touched variables are simply integers, and a touched variable is associated with each face.

Since the halfedge representation can only represent polygonized manifolds, the name of the data structure is

  h->touched = -1;

Manifold m;

What would be the use of setting the touched values to -1? Well, if we want to keep track of whether we have visited a given halfedge, we can initially set the touched values of all halfedges to -1 and then as we visit a halfedge set its value to something different. The same idea can be applied to faces and vertices.

A vertex has an integer index referencing one of the halfedges which emanate from the vertex, and a face has the index of one of the halfedges in the loop around the face. The entities and the integer indices used to refer from one entity to another are illustrated in Figure~\ref{fig:halfedge}. Note also that the pointers from an entity to another, e.g. from a halfedge to its next edge is the mechanism that allows us to traverse the mesh.

\caption{A halfedge and related entities. The halfedge has pointers to the \texttt{next} and previous (\texttt{prev}) halfedges in the counterclockwise loop around its face. It also has a pointer to the opposite (\texttt{opp}) halfedge, which corresponds to the same geometric edge but is part of the loop around the adjacent face. Finally, the halfedge has a pointer to the next \texttt{vertex} in the direction of the halfedge and to its \texttt{face}. A face has a pointer to exactly one halfedge (\texttt{last}) and a vertex has a pointer to one outgoing halfedge (\texttt{h}). The word ``pointer'' is a bit of a misnomer. In GEL we use integer indices instead of memory pointers. }

Another common use of the touched values is as indices into an array. In this way, you can store auxiliary data with the mesh. In fact, there is a function\\ \texttt{enumerate\_vertices()} which enumerates all vertices (so each has a unique positive (or zero) integer. Similar functions exist for faces and halfedges.

\label{fig:halfedge}

So far, we have only discussed touched, but halfedges, faces, and vertices contain other data members. Most of these are iterators pointing to other edges, faces, or vertices. In the following, we briefly mention each member of the datastructures and show how to get to it. To get the opposite halfedge, use

The integer indices are not only used to store references from one entity to another. In GEL, we do not directly access entities but use integer IDs to refer to them. For instance to get the position of a vertex, which is stored as a \texttt{Vec3d}, we need

HalfEdgeIter h2 = h1->opp;

// ... obtain a vertex ID

To get the next halfedge (in counterclockwise cycle around the vertex), 

\texttt{VertexID}, \texttt{FaceID}, and \texttt{HalfEdgeID} are simply indices which we use to refer to entities in the mesh. These types are used to communicate with the \texttt{Manifold} class. For instance to get the position of a vertex, but many other functions -- both inside and outside the \texttt{Manifold} class take one of the ID types as argument. For instance,

HalfEdgeIter h2 = h1->next;

VertexID Manifold::split_edge(HalfEdgeID h);

HalfEdgeIter h2 = h1->prev;

bool boundary(const Manifold& m, HalfEdgeID h);

the vertex they point at, 

returns true if the halfedge identified by \texttt{h} is a boundary edge in \texttt{m}.

\end{verbatim}

and the face whose counter clockwise halfedge loop they are one segment of.

We might somewhere have stored the \texttt{VertexID}, but frequently we simply iterate through our vertices. In other words, we loop over all vertices. Such a loop requires another type, namely the \texttt{VertexIDIterator}

FaceIter f = h->face;

  Vec3d p = mani.pos(*v);

A vertex knows its position which is a Vec3f. To get the position, use

An ID iterator is only useful for iterating over elements in the mesh. However, from the iterator we can obtain the ID by using the dereference operator \texttt{*} as shown above. We also have \texttt{HalfEdgeID}, \texttt{HalfEdgeIDIterator}, \texttt{FaceID}, and \texttt{FaceIDIterator}. Thus, similar code could have been used to iterate over halfedges or faces. Clearly, iterating over elements is just the beginning. The iterators expose how the mesh entities are stored in the \texttt{Manifold} but not how they relate geometrically to one another. 

Vec3f pos = v->pos;

Vec3d p(0);

A vertex also knows one outgoing halfedge:

The code above computes the centroid for the first face in the mesh. The benefit of the walker is that it allows us to move from a halfedge to all connected halfedges. The simple traversal functions are \texttt{next}, \texttt{prev}, and \texttt{opp}:

HalfEdgeIter h = v->he;

Walker w;

A face knows one halfedge in its counterclockwise cycle

\texttt{prev} does the same as \texttt{circulate\_face\_cw} and \texttt{next} does the same as \\\texttt{circulate\_face\_ccw}. The longer names are indicative of the geometric operation while \texttt{prev} and \texttt{next} highlight the connection with the data structure.    It is important to note that all of the functions which operate on \texttt{Walker} instances return a new \texttt{Walker} and do not alter the state of the current walker. Thus to walk around a face, we use \texttt{w = w.next()} as opposed to just \texttt{w.next()} in the for loop above. 

HalfEdgeIter h = face->last;

Walker w = m.walker(*v);

To move around a face, we can repeatedly ask for the next halfedge. Likewise, to move around a vertex, we can repeatedly ask for \texttt{h->opp->next} but it is not elegant, and in both cases we need a stop condition. Circulators encapsulate the task of visiting all edges delimiting a face or radiating from a vertex in a nice(r) way.

From a walker we can easily obtain any of the mesh entities that the halfedge it refers to are incident upon. For instance \texttt{vertex()} returns the \texttt{VertexID} of the vertex which the halfedge points to, \texttt{face()} gives us the \texttt{FaceID} of the incident face and \texttt{halfedge()} simply returns the \texttt{HalfEdgeID}.

Given 

\item ID iterators \texttt{VertexIDIterator}, \texttt{HalfEdgeIDIterator}, and\\ \texttt{FaceIDIterator} as their names imply can be used to iterate over the entities of a mesh. As such they reflect how the mesh is stored in memory. Dereferencing an ID iterator will give an ID. 

\begin{verbatim}

\end{itemize}

VertexIter v

It might seem tiresome that you have to deal with three different methods for referring to mesh entities, but they do very different jobs. The IDs are simply indices (wrapped in a class) referring to mesh elements. The iterators combine this indices with a reference to the actual data structures. The walker contains functions that allow us to move from halfedge to halfedge and additionally keeps track of the starting point and number of steps taken.

\end{verbatim}

\subsection{Attributes}

we can go:

Given a \texttt{VertexID},  \texttt{v}, and a \texttt{Manifold}, \texttt{m}, we can obtain the geometric position of the vertex with the method call \texttt{m.pos(v)}. If is fairly important to note that a reference to the position is returned. Thus, we can assign the position of a vertex:

Vec3f p(0.0);

Vec3d p;

for( ; !vc.end(); ++vc)

VertexID v;

  p += vc.get_vertex()->pos;

// ...

p/= vc.no_steps();

m.pos(v) = p;

So what does the code above do? It visits each neighboring vertex to a given vertex and computes the average position which is useful in a number of situations.

Geometric position is in fact the only attribute that is stored for a vertex. That might seem strange since we would very often like to associate any number of attributes with mesh entities. For instance, we might need to associate normals, colors, curvature tensors, counters, etc. with vertices, faces, or even edges.

We can do the same thing with a FaceCirculator

Unfortunately, what precise attributes we need depends greatly on the precise application. To resolve this issue, we have introduces three attribute vector class templates which allow the user to create his own attribute vectors:

FaceCirculator fc(f);

FaceAttributeVector<T> face_ttrib_vector;

Vec3f p(0.0);

\end{verbatim}

for( ; !fc.end(); ++fc)

\texttt{VertexAttributeVector} is indexed with a \texttt{VertexID} and likewise for the other types. To give a simple example of how this is used consider smoothing a mesh. The simplest way of smoothing is to replace the vertex with the average of its neighbors. However, if we copy the average value back before the average value for some neighbor has been computed, then we clearly use one average to compute another average and thereby introduce an unfortunate dependence on the ordering of the vertices. Consequently, we need to first compute all of the averages and then update the original vertices. The code looks as follows:

  p += fc.get_vertex()->pos;

              v != m.vertices_end(); ++v)

p/= fc.no_steps();

          Vec3f avg_pos(0);

Internally, both the vertex and face circulators simply keep track of a single halfedge. So \texttt{get\_vertex()} returns the vertex pointed to by that halfedge. There are similar functions for getting the halfedge itself, the face it points to or its opposite halfedge.

In the smoothing example the \texttt{VertexAttributeVector} containing the new positions is initialized to a size equal to the actual number of vertices. That is not strictly necessary since the attribute vectors automatically resize if the index stored in the ID is out of bounds. Thus, we never explicitly need to increase the size of an attribute vector. What if there are suddenly fewer vertices? In that case, we can clean up the attribute vector. However, we also need to clean up the manifold. The procedure looks as follows:

#include <HMesh/Manifold.h>

Manifold m;

#include <HMesh/FaceCirculator.h>

m.cleanup(remap);

#include <HMesh/VertexCirculator.h>

vertex_attrib_vector.cleanup(remap);

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

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

	vector<Vec3f> vertices(3);

  vector<Vec3f> vertices(3);

	vertices[0] = p1;

  vertices[0] = p1;

	vertices[1] = p2;

  vertices[1] = p2;

	vertices[2] = p3;

  vertices[2] = p3;

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. 

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

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

m.build(3, reinterpret_cast<float*>(&vertices[0]),1,

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

   &faces[0], &indices[0]);

	HalfEdgeIter h = m.halfedges_begin();

HalfEdgeIDIterator h = m.halfedges_begin();

	m.split_edge(h);

m.split_edge(*h); 

	m.triangulate(h->face); 

triangulate_face_by_edge_split(m, m.walker(*h).face());

	FaceIter f1 =m.faces_begin();

FaceIDIterator f1 =m.faces_begin();

	m.face_insert_point(f1,v);

m.split_face_by_vertex(*f1);

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

for(HalfEdgeIDIterator h = m.halfedges_begin(); 

  h->touched =0;

   h!=m.halfedges_end(); ++h)

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

        if(m.walker(*h).opp().halfedge() < *h)

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

            touched[*h] =0;

    h->touched = 1;

            touched[*h] =1;

	flipper = m.halfedges_begin();

flipper = m.halfedges_begin();

if(is_boundary(flipper))

  if(!boundary(m, *flipper)) 

  if(!m.flip(flipper))

      if(precond_flip_edge(m,*flipper))

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

                m.flip_edge(*flipper);

do

  do

{

    {

  ++flipper;

      ++flipper;

  if(flipper==m.halfedges_end())

      if(flipper==m.halfedges_end())

    flipper = m.halfedges_begin();

          flipper = m.halfedges_begin();

}

    }

while(flipper->touched == 0); 

  while(touched[*flipper] == 0);

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.

This example may not serve much of a purpose but illustrates how we can iterate over all edges and flip them. From this example, we are fairly close to Delaunay triangulation.

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).

\subsection{HMesh tools}

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.

\texttt{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.

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

There is some code below to illustrate usage.	

There is some code below to illustrate usage.  

\section{Authors and License}  

\section{Authors}  

Many other people contribute, but the core of GEL was written (mostly) by Andreas B{\ae}entzen (jab{@}imm.dtu.dk), and any bug fixes, contributions, or questions should be addressed to me, unless you know precisely who could take care of the problem.

\item Anders Wang Kristensen has been a great help in the process of reworking HMesh and also contributed some code for an OpenGL console.

in my opinion. Instead, I list a few rules below. The most

\section{License}  

for the rules:

\begin{trivlist}

\item

particular, you are welcome to give GEL to students as a basis for 

You are allowed to use GEL for academic or commercial purposes. In particular, you are welcome to give GEL to students as a basis for academic work or to use it in your own applications.

\item

GEL in any way. You are not allowed to distribute another library which

Regarding the use of GEL in other libraries. GEL does exist in slightly different versions, since we have created pared down packages for various courses. We would like to retain the prerogative of repackaging. If you would like to use GEL in its entirety in another library  that is fine, but we do not allow you not to take bits and pieces and put them into a different library.

changed form. If you want changes to be made, contact me.

If you use GEL, we would be grateful for due credit.

\item

held responsible in any way, under any circumstances what so ever - no

Finally, we follow the MIT license as regards warranty:

\item

GEL for a bigger project, I'd appreciate an email to jab@imm.dtu.dk

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

\item

In a project such as this, it is almost impossible to completely avoid

If anything is unclear, please send an email to jab@imm.dtu.dk. 

from Graphics Gems have also been used. Moreover, I have included

\end{trivlist}

Jonathan Dummer.  All of this amounts to only a fraction of the GEL source code and it should not be in violation of any license. In particular, SOIL and RPLY are under the MIT license and it is acceptable to include these packages as long as the copyright notice is retained (which it is.)

\section{Open Source Code used in GEL}