Computing normal of all vertices in CGAL::Polyhedron_3

In this post I will show how to compute normal vector at a vector in CGAL::Polyhedron_3.

ComputeVertexNormal() Functor

ComputeVertexNormal() is a thread-safe functor for computing the normal vector at a given vertex in a CGAL::Polyhedron_3. The normal vector at a vertex is the average of the normal vectors of all facets incident on the vertex. The facet normals must be be initialized using the ComputeVertexNormal()’s constructor. The code for computing the facet normals is presented in this post: Computing normal of all facets in CGAL::Polyhedron_3.

#ifndef _SMESHLIB_OPERATIONS_COMPUTEVERTEXNORMAL_H_
#define _SMESHLIB_OPERATIONS_COMPUTEVERTEXNORMAL_H_

#include "PropertyMap.h"

namespace SMeshLib   {
namespace Operations {
;

// The ComputeVertexNormal is a functor (delegate) to compute the normal of a vertex in CGAL::Polyhdeon_3.
// operator() is thread-safe.
// TPolyhedron is a type of CGAL::Polyhdeon_3.
// TFacetNormals is a property map which associates a normal vector to each facet in the CGAL::Polyhdeon_3.
// The vertex normal is the average of all facet normals incident on it.
template<class TPolyhedron, class TFacetNormals>
struct ComputeVertexNormal
{
public:
	
	// Redefine types from TPoly for convenience.
	typedef typename TPolyhedron::Vertex                                  Vertex;
	typedef typename TPolyhedron::Facet                                   Facet;
	typedef typename TPolyhedron::Traits::Vector_3                        Vector3;
	typedef typename TPolyhedron::Halfedge_around_vertex_const_circulator HalfEdgeConstCirculator;
	
	// Return type of operator() required by QtConcurrent.
	typedef Vector3 result_type;
	
public:
	
	ComputeVertexNormal(const TFacetNormals& facetNormals_)
		: facetNormals(facetNormals_)
	{}
	
	// Compute normal of the given vertex.
	inline Vector3 operator() (const Vertex& v) const
	{
		Vector3                 n = CGAL::NULL_VECTOR;
		HalfEdgeConstCirculator s = v.vertex_begin();
		HalfEdgeConstCirculator e = s;
		CGAL_For_all(s, e)
		{
			// Border edge doesn't have facet and hence no normal.
			if(!s->is_border())
			{
				n = n + facetNormals.value(&*(s->facet()));
			}
		}
		return n/std::sqrt(n*n);
	}
	
public:
	
	const TFacetNormals& facetNormals;
};

};	// End namespace Operations.
};	// End namespace SMeshLib.

#endif // _SMESHLIB_OPERATIONS_COMPUTEVERTEXNORMAL_H_

Using ComputeVertexNormal() Functor

Normal vector at a vertex v can be computed as Vector3 normal = ComputeVertexNormal(f); .

For most purposes, it is better to compute area of all facets once and cache them for later use. It is best to store the results in an associative container which associates the facet handle with the area. In the following example, I use PropertyMap which is a wrapper for std::set.

#include "ImportOBJ.h"
#include "ComputeFacetNormal.h"
#include "ComputeVertexNormal.h"
#include "PropertyMap.h"
#include "CGAL/Simple_cartesian.h"
#include <CGAL/Polyhedron_items_3.h>
#include "CGAL/HalfedgeDS_list.h"
#include "CGAL/Polyhedron_3.h"

typedef CGAL::Simple_cartesian<double> Kernel;
typedef CGAL::Polyhedron_3<Kernel, 
	                       CGAL::Polyhedron_items_3, 
						   CGAL::HalfedgeDS_list> CgalPolyhedron;

// Compute the normal of all vertices in a CGAL::Polyhedron_3 and stores it in 
// vertexNormals.
// TPolyhedron is a type of CGAL::Polyhedron_3.
// TVertexNormals is a property map which associates a normal vector to vertex 
// in the CGAL::Polyhdeon_3.
// TFacetNormals is a property map which associates a normal vector to facet 
// in the CGAL::Polyhdeon_3.
template<class TPolyhedron, class TVertexNormals, class TFacetNormals>
void computeVertexNormals(const TPolyhedron& polyhedron, TVertexNormals* vertexNormals, const TFacetNormals& facetNormals)
{
	if(vertexNormals == 0)
	{
		return;
	}
	
	typename TPolyhedron::Vertex_const_iterator _begin = polyhedron.vertices_begin();
	typename TPolyhedron::Vertex_const_iterator _end   = polyhedron.vertices_end();
	
	SMeshLib::Operations::ComputeVertexNormal<TPolyhedron, TFacetNormals> _computeVertexNormal(facetNormals);
	CGAL_For_all(_begin, _end)
	{
		vertexNormals->setValue(&*_begin, _computeVertexNormal(*_begin));
	}
}

// Compute the normal of all facets in a CGAL::Polyhedron_3 and stores it in facetNormals.
// TPolyhedron is a type of CGAL::Polyhedron_3.
// TFacetNormals is a property map which associates a normal vector to facet in the CGAL::Polyhdeon_3. 
template<class TPolyhedron, class TFacetNormals>
void computeFacetNormals(const TPolyhedron& polyhedron, TFacetNormals* facetNormals)
{
	if(facetNormals == 0)
	{
		return;
	}
	
	typename TPolyhedron::Facet_const_iterator _begin = polyhedron.facets_begin();
	typename TPolyhedron::Facet_const_iterator _end   = polyhedron.facets_end();

	SMeshLib::Operations::ComputeFacetNormal<TPolyhedron> _computeFacetNormal;
	CGAL_For_all(_begin, _end)
	{
		facetNormals->setValue(&*_begin, _computeFacetNormal(*_begin));
	}
}

void testComputeVertexNormal()
{
	CgalPolyhedron _poly;
	SMeshLib::IO::importOBJ("Venus.obj", &_poly);
	
	typedef SMeshLib::PropertyMap<const CgalPolyhedron::Facet*, CgalPolyhedron::Traits::Vector_3> FacetNormalPM;
	FacetNormalPM _facetNormals;
	computeFacetNormals(_poly, &_facetNormals);
	
	typedef SMeshLib::PropertyMap<const CgalPolyhedron::Vertex*, CgalPolyhedron::Traits::Vector_3> VertexNormalPM;
	VertexNormalPM _vertexNormals;
	computeVertexNormals(_poly, &_vertexNormals, _facetNormals);
}

Downloads

ImportOBJ.h
PropertyMap.h
ComputeFacetNormal.h
ComputeVertexNormal.h
TestComputeVertexNormal.cpp
Venus.obj
ComputeVertexNormal.zip