Monday, 17 March 2014

Polygon mesh data structure

My first tests with OpenGL use a triangle soup which is basically a collection of triangles with no relationship whatsoever. In order to implement a more complex shader I need to work on a more complex and powerful data structure: the polygon mesh
A polygon mesh is a collection of vertices, edges and faces that defines the shape of a polyhedral object in 3D computer graphics and solid modeling. The faces usually consist of triangles, quadrilaterals or other simple convex polygons, since this simplifies rendering, but may also be composed of more general concave polygons, or polygons with holes.
[Wiki Polygon Mesh]

There's a variety of ways to represent a polygon mesh and they basically differ in how the vertex and topology information are stored. One of the most used representation in the filed computer graphics and geometry processing is the halfedge data structure.
Polygonal meshes consist of geometry (vertices) and topology (edges, faces). Data structure for polygonal meshes mainly differ in the way they store the topology information. While face-based structures lack the explicit representation of edges, and edge-based structures loose efficiency because of their missing orientation of edges, halfedge-based structures overcome this disadvantages. The halfedges (that result in splitting the edges in two oriented parts) store the main connectivity information:
Intuitively, this provides a natural and simple way to represent vertices, edges and faces, as well as arbitrary polygons. 
Many operations and queries are very natural on the halfedge data structure, in particular the circulation on the neighbors of vertices and faces.
Traversal of one-ring neighbors of a center vertex. From left to right: 
  1. Start from center vertex. 
  2. Select outgoing halfedge (and access its target vertex). 
  3. Move to previous halfedge. 
  4. Move to opposite halfedge (access its target vertex)

As far as i know the high-quality publicly C++ libraries available are:
  1. CGAL
  2. OpenMesh
  3. SurfaceMesh
  4. CGAL Logo
  5. Mesquite
I have never used Mesquite. This is mainly focused on the mesh optimization [BFKLM03]. Although the CGAL is a very powerful library for the compuational geometry, its polygonal mesh implementation has a major drawback: all the custom properties associated with a mesh entity must be declared at compile time.

Aachen University
Computer GraphicsLogo
OpenMesh and SurfaceMesh are more flexible and much easier to use than CGAL. OpenMesh was originally developed at the Aachen University [BSBK02] and the version 3.0 was recently released. On the other hand SurfaceMesh is more recent [SB11] and it was developed at the Bielefeld university.
They have very much in common, starting with one of their developers, Mario Botsch who is also the head of the Computer Graphics & Geometry Processing Group at Bielefeld.

Based on our experience in academic research and teaching as well as in industrial cooperations, our primary design goal [of the SurfaceMesh] is ease of use. An easy-to-use data structure is learned faster, allows to focus on the main problem (instead of on the details of the data structure), and fosters code exchange between academic or industrial research partners. The data structure should therefore be just as flexible and generic as needed, but should otherwise be free of unnecessary switches and parameters. At the same time, however, we have to make sure not to compromise computational performance and memory consumption. Otherwise the data structure would be easy to use, but not useful, and hence would probably not be used at all.
The SurfaceMesh primary design goal is the ease of use, therefore it satisfy the requirements for the OpenGL-Sandbox very well, therefore I will adopt it as a polygonal mesh data structure in my program.

In the end I'll show you an example of the SurfaceMesh which computes the mean valence of the mesh vertices


[SB11] Design, Implementation, and Evaluation of the Surface_mesh Data Structure
[BFKLM03] The Mesquite mesh quality improvement toolkit
[BSBK02] OpenMesh – a generic and efficient polygon mesh data structure
[Wiki Polygon Mesh]

1 comment :

  1. Dr. Imoloa has really made me so much believe in him by getting me cured with his herbal treatment. i really appreciate you Dr.imoloa for bringing back happiness to my life again. thank you so much,friends join me to thank him for what he has actually done for me i pray to you all for a good life and good health, and most especially to you Dr. imoloa Thanks

    I have been suffering from (HERPES SIMPLEX VIRUS) disease for the past four years and had constant pain, especially in my knees. During the first year,I had faith in God that i would be healed someday.This disease started circulating all over my body and i have been taking treatment from my doctors, few months ago i came on search on the internet if i could get any information concerning the cure of this disease, on my search i saw a testimony of someone who has been healed from (HERPES SIMPLEX VIRUS) by this Man Dr imoloa and she drop the email address of this man and advise we should contact him for any sickness that he would be of help, so i wrote to Dr. imoloa telling him about my (HERPES Virus) well after all the procedures and remedy given to me by this man few weeks later i started experiencing changes all over me. I am now here to testify that i am no longer a herpes patient, I have experience a total transformation in my life,for all herpes patients get your herbal medicine to cure your sickness. And there has being rapid improvement in my health, I no longer feel pains and I wake up each morning feeling revived. So friends my advise is if you have such sickness or any other at all,you can contact him on, you can still reach him on whatssap- +2347081986098
    HEPATITIS A B and C.