Posts Tagged With ‘c++&8217


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


Computing normal of all facets in CGAL::Polyhedron_3

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

ComputeFacetNormal() Functor

ComputeFacetNormal() is a thread-safe functor for computing the normal vector of a given facet in a CGAL::Polyhedron_3. The facet must be a planar polygon with arbitrary number of sides.

#ifndef _SMESHLIB_OPERATIONS_COMPUTEFACETNORMAL_H_
#define _SMESHLIB_OPERATIONS_COMPUTEFACETNORMAL_H_

namespace SMeshLib   {
namespace Operations {
;

// The ComputeFacetNormal is a functor (delegate) to compute the normal of a facet in CGAL::Polyhdeon_3.
// ComputeFacetNormal is thread-safe.
// TPolyhedron is a type of CGAL::Polyhdeon_3.
template<class TPolyhedron>
struct ComputeFacetNormal
{
public:
	
	// Redefine types from TPolyhedron for convenience.
	typedef typename TPolyhedron::Facet                 Facet;
	typedef typename TPolyhedron::Halfedge_const_handle HalfedgeConstHandle;
	typedef typename TPolyhedron::Traits::Point_3       Point3;
	typedef typename TPolyhedron::Traits::Vector_3      Vector3;
	
	// Return type of operator() required by QtConcurrent.
	typedef Vector3 result_type;
	
public:
	
	// Compute normal of the given facet.
	// Facet can be triangle, quadrilateral or a polygon as long as its planar.
	// Use first three vertices to compute the normal.
	inline Vector3 operator() (const Facet& f) const
	{
		HalfedgeConstHandle h  = f.halfedge();
		Point3              p1 = h->vertex()->point();
		Point3              p2 = h->next()->vertex()->point();
		Point3              p3 = h->next()->next()->vertex()->point();
		Vector3             n  = CGAL::cross_product(p2-p1, p3-p1);
		return n / std::sqrt(n*n);
	}
};

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

#endif // _SMESHLIB_OPERATIONS_COMPUTEFACETNORMAL_H_
Using ComputeFacetNormal() Functor

Normal vector of a facet f can be computed as Vector3 normal = ComputeFacetNormal(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 "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 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 testComputeFacetNormal()
{
	CgalPolyhedron _poly;
	SMeshLib::IO::importOBJ("Venus.obj", &_poly);
	
	typedef SMeshLib::PropertyMap<const CgalPolyhedron::Facet*, CgalPolyhedron::Traits::Vector_3> FacetNormalPM;
	FacetNormalPM _facetNormals;
	computeFacetNormals(_poly, &_facetNormals);
}
Downloads

ImportOBJ.h
PropertyMap.h
ComputeFacetNormal.h
TestComputeFacetNormal.cpp
Venus.obj
ComputeFacetNormal.zip


Computing edge length of all half-edges in CGAL::Polyhedron_3

In this post I will show how to compute edge length for a half-edge in CGAL::Polyhedron_3.

ComputeEdgeLength() Functor

ComputeEdgeLength() is a thread-safe functor for computing the edge length of a given half-edge in a CGAL::Polyhedron_3.

#ifndef _SMESHLIB_OPERATIONS_COMPUTEEDGELENGTH_H_
#define _SMESHLIB_OPERATIONS_COMPUTEEDGELENGTH_H_

namespace SMeshLib   {
namespace Operations {
;

// The ComputeEdgeLength is a functor (delegate) to compute the length of a halfedge in CGAL::Polyhdeon_3.
// ComputeEdgeLength is thread-safe.
// TPolyhedron is a type of CGAL::Polyhdeon_3.
template<class TPolyhedron>
struct ComputeEdgeLength
{
public:
	
	// Redefine types from TPolyhedron for convenience.
	typedef typename TPolyhedron::Point_3  Point3;
	typedef typename TPolyhedron::Halfedge Halfedge;
	
	// Return type of operator() required by QtConcurrent.
	typedef double result_type;
	
public:
	
	// Compute edge length of a given half edge.
	inline double operator () (const Halfedge& h)
	{
		const Point3& p = h.prev()->vertex()->point();
		const Point3& q = h.vertex()->point();
		return CGAL::sqrt(CGAL::squared_distance(p, q));
	}
};

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

#endif // _SMESHLIB_OPERATIONS_COMPUTEEDGELENGTH_H_
Using ComputeEdgeLength() Functor

Edge length of a half-edge h can be computed as double length = ComputeEdgeLength(h);.

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

#include "ImportOBJ.h"
#include "ComputeEdgeLength.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 length of all half-edges in a CGAL::Polyhedron_3 and stores it 
// in edgeLengths.
// TPolyhedron is a type of CGAL::Polyhedron_3.
// TEdgeLengths is a property map which associates the edge length to half-edge 
// in the CGAL::Polyhdeon_3.
template<class TPolyhedron, class TEdgeLengths>
void computeEdgeLengths(const TPolyhedron& polyhedron, TEdgeLengths* edgeLengths)
{
	if(edgeLengths == 0)
	{
		return;
	}
	
	typename TPolyhedron::Halfedge_const_iterator _begin = polyhedron.halfedges_begin();
	typename TPolyhedron::Halfedge_const_iterator _end   = polyhedron.halfedges_end();

	SMeshLib::Operations::ComputeEdgeLength<TPolyhedron> _computeEdgeLength;
	CGAL_For_all(_begin, _end)
	{
		edgeLengths->setValue(&*_begin, _computeEdgeLength(*_begin));
	}
}

void testComputeEdgeLength()
{
	CgalPolyhedron _poly;
	SMeshLib::IO::importOBJ("Venus.obj", &_poly);
	
	typedef SMeshLib::PropertyMap<const CgalPolyhedron::Halfedge*, double> EdgeLengthPM;
	EdgeLengthPM _edgeLengths;
	computeEdgeLengths(_poly, &_edgeLengths);
}
Downloads

ImportOBJ.h
PropertyMap.h
ComputeEdgeLength.h
TestComputeEdgeLength.cpp
Venus.obj
ImportOBJ.zip


Wavefront OBJ reader for building CGAL::Polyhedron_3

CGAL provides high quality generic half-edge data structure for representing polyhedral surfaces as well as many algorithms for mesh processing. However, CGAL doesn’t have any in-build support for building a polyhedron from Wavefront OBJ or PLY file. The following code is a basic OBJ file loader which reads vertex coordinates and faces (can be polygons) from OBJ file. Note that it doesn’t read vertex normals, face normals, or texture coordinates. Code is well commented and should be fairly obvious.

importOBJ() Function
#ifndef _SMESHLIB_IO_IMPORTOBJ_H_
#define _SMESHLIB_IO_IMPORTOBJ_H_

#include "CGAL/Polyhedron_incremental_builder_3.h"
#include "CGAL/Modifier_base.h"
#include "CGAL/exceptions.h"
#include <string>
#include <fstream>
#include <exception>

namespace SMeshLib {
namespace IO       {
;

// The BuildCgalPolyhedronFromObj class builds a CGAL::Polyhedron_3 from Wavefront OBJ file.
// This is very simple reader and only reads vertex coordinates and vertex index for faces.
// Faces can be polygons and doesn't have to be triangles.
template<class HDS>
class BuildCgalPolyhedronFromObj : public CGAL::Modifier_base<HDS>
{
public:
	
	BuildCgalPolyhedronFromObj(const std::string& fileName) : mFileName(fileName) {}
	
	void operator() (HDS& hds)
	{
		typedef typename HDS::Vertex   Vertex;
		typedef typename Vertex::Point Point;
		
		// Open obj file for reading.
		std::ifstream _file(mFileName.c_str());
		if(!_file)
		{
			return;
		}
		
		// Count the number of vertices and facets.
		// This is used to reserve memory in HDS.
		std::string _line;
		int _numVertices = 0;
		int _numFacets   = 0;
		while(_file.good())
		{
			std::getline(_file, _line);
			if(_line.size() > 1)
			{
				if(_line[0]=='v' && _line[1]==' ') {++_numVertices;}
				if(_line[0]=='f' && _line[1]==' ') {++_numFacets;}
			}
		}
		
		// Rewind file to beginning for reading data.
		if(!_file.good())
		{
			_file.clear();
		}
		_file.seekg(0);

		// Postcondition: hds is a valid polyhedral surface.
		CGAL::Polyhedron_incremental_builder_3<HDS> B(hds, true);
		
		// Load the data from OBJ file to HDS.
		B.begin_surface(_numVertices, _numFacets, int((_numVertices + _numFacets - 2)*2.1));
			
			std::string _token;
			while(!_file.eof())
			{
				_token = ""; // Reset token.
				_file >> _token;
				
				// if token is v then its a vertex.
				if(_token=="v")
				{
					double x, y, z;
					_file >> x >> y >> z;
					B.add_vertex(Point(x, y, z));
				}
				
				// There are 4 type of facets.
				// a     only vertex index.
				// a/b   vertex and texture index.
				// a/b/c vertex, texture and normal index.
				// a//c  vertex and normal index.
				else if(_token=="f")
				{
					// Read the remaining line for the facet.
					std::string _line;
					std::getline(_file, _line);
					
					// Split the line into facet's vertices.
					// The length of _vertices is equal to the number of vertices for this face.
					std::istringstream _stream(_line);
					std::vector<std::string> _vertices;
					std::copy(std::istream_iterator<std::string>(_stream), 
							  std::istream_iterator<std::string>(), 
							  std::back_inserter(_vertices));
					
					// For each vertex read only the first number, which is the vertex index.
					B.begin_facet();
					for(size_t i=0 ; i<_vertices.size() ; ++i)
					{
						std::string::size_type _pos = _vertices[i].find('/', 0);
						std::string _indexStr = _vertices[i].substr(0, _pos);
						B.add_vertex_to_facet(stoi(_indexStr)-1); // -1 is because OBJ file uses 1 based index.
					}
					B.end_facet();
				}
			}
			_file.close();
			
		B.end_surface();
	}
	
private:
	
	std::string mFileName;
};


// Import a OBJ file given by fileName to polyhedron.
// TPoly is a type of CGAL::Polyhdeon_3.
template<class TPoly>
void importOBJ(const std::string& fileName, TPoly* polyhedron)
{
	if(polyhedron)
	{
		try
		{
			// Build Polyhedron_3 from the OBJ file.
			BuildCgalPolyhedronFromObj<TPoly::HalfedgeDS> _buildPolyhedron(fileName);
			
			// Calls is_valid at the end. Throws an exception in debug mode if polyhedron is not
			// manifold.
			polyhedron->delegate(_buildPolyhedron);
			
			// CGAL::Assert_exception is thrown in the debug mode when 
			// CGAL::Polyhedron_incremental_builder_3 is destroyed in BuildCgalPolyhedronFromObj.
			// However, in the release mode assertions is disabled and hence no exception is thrown.
			// Thus for uniform error reporting, if the polyhedron is not valid then throw a dummy 
			// exception in release mode.
			if(!polyhedron->is_valid())
			{
				throw CGAL::Assertion_exception("", "", "", 0, "");
			}
		}
		catch(const CGAL::Assertion_exception&)
		{
			std::string _msg = "SMeshLib::importOBJ: Error loading " + fileName;
			throw std::exception(_msg.c_str());
		}
	}
}

};	// End namespace IO.
};	// End namespace SMeshLib.

#endif // _SMESHLIB_IO_IMPORTOBJ_H_
Using importOBJ()
#include "ImportOBJ.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;

void testImportOBJ()
{
	CgalPolyhedron _poly;
	SMeshLib::IO::importOBJ("Venus.obj", &_poly);
}
Downloads

ImportOBJ.h
TestImportOBJ.cpp