WebSVN – gelsvn – Diff – /branches/cpp11-devel/doc/intro.tex

   Vec3f p2 = p0 + p1;
   p2 += p1; // Same as p2 = p2 + p1
 \end{verbatim}
 Thus both the normal form of \texttt{+} and the assignment form are supported for \texttt{Vec3f}. The same is true of the other arithmetic operators \texttt{-*/} and the operators are supported for most  CGLA entities including all matrix and vector types.
-Multiplication is also supported for matrix vector products. Below an example with 4D double precision vector and matrix:
+Multiplication is also supported for matrix vector products:
 \begin{verbatim}
-  Vec4d x(1,1,0,1);
+  Vec4d p0(1,1,0,1);
   Mat4x4d m = rotation_Mat4x4d(ZAXIS, 3.14);
-  Vec4d y = m * x;
+  Vec4d p1 = m * p0;
 \end{verbatim}
 but all vectors are column vectors, so only right multiplication is supported. We cannot multiply a vector on the left side of a matrix. However, there is, of course, a \texttt{dot} function which computes the dot product of two vectors.
 A very common operation is to compute the normal of a triangle from
 \subsection{Walker}
 To loop over all vertices is one way of traversing the mesh. It ensures that we visit all vertices, but it does not relate to the connectivity of the mesh.
 To traverse the mesh in a way that respects connectivity, we use the \texttt{Walker} class. A \texttt{Walker} always points to a specific halfedge, but unlike a \texttt{HalfEdgeID}, it can be used to move from edge to edge. For instance, to compute the centroid for a given face, we can use the following code:
 \begin{verbatim}
 Vec3d p(0);
-FaceID f = *m.faces_begin();
+FaceID f = m.faces();
+Walker w = m.walker(f);
-for(Walker w = m.walker(f); !w.full_circle(); w = w.next())
+for(; !w.full_circle(); w = w.next())
   p += m.pos(w.vertex());
 p /= w.no_steps();
 \end{verbatim}
 The code above computes the centroid for the first face in the mesh. It does so by jumping from edge to edge until it has come full circle. For each jump, we add the vertex pointed to by the halfedge to \texttt{p}. The benefit of the \texttt{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}:
 \begin{verbatim}
 That might seem inconvenient but it is more flexible since we can obtain, say, a nearby vertex just by concatenating some traversal functions. For instance \texttt{w.next().opp().next().vertex()} returns an ID to a vertex nearby  -- without changing \texttt{w}. The sequence \texttt{w.next().opp().next()} creates three anonymous walkers. If, on the other hand, the functions used for walking updated the state of  \texttt{w}, we would have needed to first make a named copy of \texttt{w} before updating its state, so that we could get back to the original state.
 \texttt{Walker} can be used to circulate around both faces and vertices. Below, we use vertex circulation to compute the average of the neighbors of a vertex
 \begin{verbatim}
 Vec3d p(0);
-VertexID v = *m.vertices_begin();
+VertexID v = m.vertices();
-for(Walker w = m.walker(v);!w.full_circle();
+Walker w = m.walker(v)
-     w = w.circulate_vertex_ccw()){
+for(;!w.full_circle(); w = w.circulate_vertex_ccw()){
   p += m.pos(w.vertex());
 p /= w.no_steps();
 \end{verbatim}
 Again, the \texttt{full\_circle()} function tests whether the walker has returned to the original halfedge whence it was created. We can also call  \texttt{no\_steps() } which returns the number of steps taken. In this regard, a step of vertex circulation is considered atomic - even though \texttt{w.circulate\_vertex\_ccw()} is the same as  \texttt{w.prev().opp()}.
 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}. There is one more option for circulation. The following code does precisely the same as the code above, i.e. it computes the average of the neighboring vertices.
 \begin{verbatim}
-        Vec3d p(0);
+Vec3d p(0);
-        int n = circulate_vertex_ccw(m, v,
+int n = circulate_vertex_ccw(m, v,
-                   [&](VertexID v){ p += m.pos(v); });
+          [&](VertexID v){ p += m.pos(v); });
-        return p / n;
+return p / n;
 \end{verbatim}
 Here the function \texttt{circulate\_vertex\_ccw} takes three arguments. The \texttt{Manifold}, \texttt{m}, and the vertex, \texttt{v}, around which we circulate, and, finally, a function that accepts a \texttt{VertexID}. This function gets called for every vertex adjacent to \texttt{v}. In this example, the function is given as a so called \textit{lambda} function. This allows us to write things compactly and to have the body of the function where it is needed. We could also have passed a function which accepts a \texttt{FaceID} or a \texttt{HalfEdgeID} or a \texttt{Walker}. Thus, we can visit incident faces and edges during circulation if that is what we need, and if we need go get some entity other than adjacent vertices, edges, or faces, we can use the \texttt{Walker} option which is the most generic.
-To sum up, there are two datatypes that we use to refer to mesh entitites.
+To summarize there are three datatypes that we use to refer to mesh entitites.
 \begin{itemize}
 \item IDs \texttt{VertexID}, \texttt{HalfEdgeID}, and \texttt{FaceID} are simply indices. These types are what we use when calling functions that take arguments which refer to mesh entities.
+\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.
 \item \texttt{Walker} is used to walk from halfedge to halfedge on the mesh. It utilizes the references stored in halfedges to other halfedges in order to facilitate this traversal. Again, we can obtain an ID from a walker.
 \end{itemize}
-It might seem tiresome that you have to deal with two 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 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. In fact there are also three iterator classes, but we do not mention them, because the user does not need them; they are only a tool which allows for loops that visit all faces, edges, or vertices.
+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.
+We could have combined two or all three of these concepts, but would have led to rather bloated datatypes.
 \subsection{Attributes}
 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:
 \begin{verbatim}
 Vec3d p;
 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.
 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:
 \begin{verbatim}
-VertexAttributeVector<T> vertex_attrib_vector;
+VertexAttributeVector<T>   vertex_attrib_vector;
-FaceAttributeVector<T> face_ttrib_vector;
+FaceAttributeVector<T>     face_ttrib_vector;
 HalfEdgeAttributeVector<T> halfedge_attrib_vector;
 \end{verbatim}
 where \texttt{T} is a typename. Attribute vectors are indexed with indices. Thus, a
-\texttt{VertexAttributeVector} is indexed with a \texttt{VertexID} and likewise for the other types.
+\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:
 \begin{verbatim}
-VertexAttributeVector<Vec3d> my_attrib;
-VertexID v;
-// assign some vertex ID to v
-my_attrib[v] = Vec3d(1,2,3);
-\end{verbatim}
-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. What we do is to copy \textit{all} vertex positions to a new attribute vector. Then we compute a new position for each vertex storing it in the new attribute vector. Finally, we copy the positions back. Some complexity is due to the treatment of boundaries. Boundary vertices are not smoothed in this example. However, since we have copied the old vertex positions to the new attribute vector this means that boundary vertices are simply left where they are. The code looks as follows:
+void smooth(Manifold& m, float t)
-\begin{verbatim}
-void laplacian_smooth_example(Manifold& m)
+{
-    VertexAttributeVector<Vec3d> new_pos =
+  VertexAttributeVector<Vec3f> pos(m.total_vertices());
-        m.positions_attribute_vector();
-    for(VertexID v : m.vertices())
+  for(VertexID v : m.vertices())
+  {
-        if(!boundary(m, v))
+    if(!boundary(m, v))
-        {
+    {
-            Vec3d L(0);
+      Vec3f avg_pos(0);
+      Walker w = m.walker(v)
-            int n = circulate_vertex_ccw(m,v,
+      for(; !w.full_circle(); w = w.circulate_vertex_cw())
-                [&](VertexID v){
+        avg_pos += m.pos(w.vertex());
-                    L += m.pos(v);
+      pos[v] =  avg_pos / w.no_steps();
-            });
+    }
+  }
-            new_pos[v] = L/n;
+  for(VertexID v : m.vertices())
-        }
+  {
+    if(!boundary(m, v))
-   m.positions_attribute_vector() = new_pos;
+      m.pos(v) = pos[v];
+  }
+}
 \end{verbatim}
-What if we were to write to a position in the attribute vector which did not contain a value? For instance, what happens if we add vertices to the mesh, somehow, and then assign attribute values to the added vertices. One would hope that the attribute vector is resized automatically, and that is the case, fortunately. 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:
+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:
 \begin{verbatim}
 VertexAttributeVector<T> vertex_attrib_vector;
 Manifold m;
 // ....
 vertex_attrib_vector.cleanup(remap);
 \end{verbatim}
 Calling \texttt{cleanup} on the \texttt{Manifold} removes unused mesh entities, resizes, and resize the vectors containing these entities. When we subsequently call cleanup on the attribute vector, the same reorganization is carried out on the attribute vector keeping it in sync. Strictly speaking cleanup is rarely needed, but it removes unused memory which can be a performance advantage.
 \subsection{Extended Example: Edge Flipping}
-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. This is just a vector of 3D points:
+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
 \begin{verbatim}
   vector<Vec3f> vertices(3);
   vertices[0] = p1;
   vertices[1] = p2;
   vertices[2] = p3;
    &faces[0], &indices[0]);
 \end{verbatim}
 The result of the above is a mesh with a single triangle.
 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}
-HalfEdgeIDIterator h = m.halfedges_begin();
+HalfEdgeID h = m.halfedge();
-m.split_edge(*h);
+m.split_edge(h);
-triangulate_face_by_edge_split(m, m.walker(*h).face());
+triangulate_face_by_edge_split(m, m.walker(h).face());
 \end{verbatim}
 Now, we obtain an iterator to the first of our (two) triangles.
 \begin{verbatim}
-FaceIDIterator f1 =m.faces_begin();
+FaceID f1 = m.faces();
 \end{verbatim}
 We create a vertex, \texttt{v}, at centre of \texttt{f1} and insert it in that face:
 \begin{verbatim}
-m.split_face_by_vertex(*f1);
+m.split_face_by_vertex(f1);
 \end{verbatim}
 The code below, marks one of a pair of halfedges (with the value 1).
 \begin{verbatim}
 HalfEdgeAttributeVector<int> touched;
 // ....
-for(HalfEdgeIDIterator h = m.halfedges_begin();
+for(HalfEdgeID h : m.halfedges())
-   h!=m.halfedges_end(); ++h)
-    {
+{
-        if(m.walker(*h).opp().halfedge() < *h)
+  if(m.walker(h).opp().halfedge() < h)
-            touched[*h] =0;
+    touched[h] =0;
-        else
+  else
-            touched[*h] =1;
+    touched[h] =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}

Subversion Repositories gelsvn

(root)/branches/cpp11-devel/doc/intro.tex @ 654 – Rev 635 → 636