QSAS_2_4/QSAS_dist/src/Ext/Particles/triangulation_utils.cc File Reference

#include "triangulation.h"

Functions
void	convertToElementsList (Facet3D *f, list< Element2D > &hull)
void	cleanUp (Facet3D *f, list< Facet3D * > &facets, list< Ridge3D * > &ridges)
Facet3D *	getImprovableFacet (Facet3D *f)
Ridge3D *	getRidge (list< Ridge3D * > &Ridges, Point3D *p1, Point3D *p2)
void	removeVisibleFacets (Facet3D *f, Point3D *ref, Facet3D *link, list< Ridge3D * > &orphanRidges, list< Point3D * > &halfspace, list< Facet3D * > &facetsToDelete, list< Ridge3D * > &ridgesToDelete)
Facet3D *	buildFirstFacet (list< Point3D * > &points)
void	quickHull (list< Point3D * > &points, list< Element2D > &hull)
void	convertToElementsList (Facet4D *f, list< Element3D > &delaunay)
void	cleanUp (Facet4D *f, list< Facet4D * > &facets, list< Ridge4D * > &ridges)
Facet4D *	getImprovableFacet (Facet4D *f)
Ridge4D *	getRidge (list< Ridge4D * > &Ridges, Point4D *p1, Point4D *p2, Point4D *p3)
void	removeVisibleFacets (Facet4D *f, Point4D *ref, Facet4D *link, list< Ridge4D * > &orphanRidges, list< Point4D * > &halfspace, list< Facet4D * > &facetsToDelete, list< Ridge4D * > &ridgesToDelete)
Facet4D *	buildFirstFacet (list< Point4D * > &points)
bool	sortCriterionRidges (Ridge4D *r1, Ridge4D *r2)
bool	uniqueCriterionRidges (Ridge4D *r1, Ridge4D *r2)
void	quickHull (list< Point4D * > &points, list< Element3D > &hull)

---

Function Documentation

Facet4D* buildFirstFacet

(

list< Point4D * > &

points

)

Creates the first facet of the set. To approximate properly the hull with one facet, creating a facet with distant points.

Precondition:

"points" must be sorted so that the first and last points are distant.

Parameters:

points

The set of points.

Returns:

Pointer to a facet.

Author:

Alban Rochel

Facet3D* buildFirstFacet

(

list< Point3D * > &

points

)

Creates the first facet of the set. To approximate properly the hull with one facet, creating a facet with distant points.

Precondition:

"points" must be sorted so that the first and last points are distant.

Parameters:

points

The set of points.

Returns:

Pointer to a facet.

Author:

Alban Rochel

void cleanUp	(	Facet4D *	f,
		list< Facet4D * > &	facets,
		list< Ridge4D * > &	ridges
	)

Collects the pointers to the facets and ridges to be deleted.

Warning:

Deletion is not performed

Parameters:

	f	1st 3D facet. The attached ones will be found recursively.
	facets	List of pointers to facets to be deleted.
	ridges	List of pointers to ridges to be deleted.

Author:

Alban Rochel

void cleanUp	(	Facet3D *	f,
		list< Facet3D * > &	facets,
		list< Ridge3D * > &	ridges
	)

Collects the pointers to the facets and ridges to be deleted.

Warning:

Deletion is not performed

Parameters:

	f	1st 3D facet. The attached ones will be found recursively.
	facets	List of pointers to facets to be deleted.
	ridges	List of pointers to ridges to be deleted.

Author:

Alban Rochel

void convertToElementsList	(	Facet4D *	f,
		list< Element3D > &	delaunay
	)

Converts linked 4D facets to the related Delaunay tetraedrisation Dimension reduction (4D to 3D). Only the facets of the lower part of the hull are relevant.

Parameters:

	f	1st 4D facet. The attached ones will be found recursively.
	hull	Output delaunay tetraedrisation. The elements are added in hull.

Author:

Alban Rochel

void convertToElementsList	(	Facet3D *	f,
		list< Element2D > &	hull
	)

Converts linked 3D facets to the related Delaunay triangulation Dimension reduction (3D to 2D). Only the facets of the lower part of the hull are relevant.

Parameters:

	f	1st 3D facet. The attached ones will be found recursively.
	hull	Output delaunay triangulation. The elements are added in hull.

Author:

Alban Rochel

Facet4D* getImprovableFacet

(

Facet4D *

f

)

Returns a pointer to a facet that has to be improved (non-empty visibility list). The neighbours are visited randomly: this prevents the function to loop a long time in the same set of neighbours, and increases dramatically the performance. Each neighbour is visited once at most.

Parameters:

f

1st 4D facet. The attached ones will be found recursively.

Returns:

An improvable 4D facet, or NULL if the facets define the convex hull of the set of points (end of algorithm).

Author:

Alban Rochel

Facet3D* getImprovableFacet

(

Facet3D *

f

)

Returns a pointer to a facet that has to be improved (non-empty visibility list). The neighbours are visited randomly: this prevents the function to loop a long time in the same set of neighbours, and increases dramatically the performance. Each neighbour is visited once at most.

Parameters:

f

1st 3D facet. The attached ones will be found recursively.

Returns:

An improvable 3D facet, or NULL if the facets define the convex hull of the set of points (end of algorithm).

Author:

Alban Rochel

Ridge4D* getRidge	(	list< Ridge4D * > &	Ridges,
		Point4D *	p1,
		Point4D *	p2,
		Point4D *	p3
	)

Returns a pointer to a ridge. Creates the ridge if not exisiting. Deletes a ridge when getRidge was called twice on this ridge (1 ridge = 2 and only 2 neighbours). First call with an empty ridge list. The subsequent calls will create or delete ridges in the list. If used properly, after the last call, the ridge list is empty (pairs of ridges were created).

Parameters:

	Ridges	The current list of ridges.
	p1	First point of the ridge (the order is not significant)
	p2	Second point of the ridge (the order is not significant)
	p3	Third point of the ridge (the order is not significant)

Returns:

Pointer to a ridge

Author:

Alban Rochel

Ridge3D* getRidge	(	list< Ridge3D * > &	Ridges,
		Point3D *	p1,
		Point3D *	p2
	)

Returns a pointer to a ridge. Creates the ridge if not exisiting. Deletes a ridge when getRidge was called twice on this ridge (1 ridge = 2 and only 2 neighbours). First call with an empty ridge list. The subsequent calls will create or delete ridges in the list. If used properly, after the last call, the ridge list is empty (pairs of ridges were created).

Parameters:

	Ridges	The current list of ridges.
	p1	First point of the ridge (the order is not significant)
	p2	Second point of the ridge (the order is not significant)

Returns:

Pointer to a ridge

Author:

Alban Rochel

void quickHull	(	list< Point4D * > &	points,
		list< Element3D > &	hull
	)

Computes the Delaunay triangulation of the (x,y,z) projection of a set of 4D points, using the QuickHull algorithm.

Parameters:

	points	The set of 4D points
	hull	The output list of Element3D (Delaunay trangulation)

Precondition:

There must be at least 5 points in the input set of points.

Author:

Alban Rochel

void quickHull	(	list< Point3D * > &	points,
		list< Element2D > &	hull
	)

Computes the Delaunay triangulation of the (x,y) projection of a set of 3D points, using the QuickHull algorithm.

Parameters:

	points	The set of 3D points
	hull	The output list of Element2D (Delaunay trangulation)

Precondition:

There must be at least 4 points in the input set of points.

Author:

Alban Rochel

void removeVisibleFacets	(	Facet4D *	f,
		Point4D *	ref,
		Facet4D *	link,
		list< Ridge4D * > &	orphanRidges,
		list< Point4D * > &	halfspace,
		list< Facet4D * > &	facetsToDelete,
		list< Ridge4D * > &	ridgesToDelete
	)

Being given a facet and a point visible from this facet, computes the neighbouring facets that "see" the point (and, thus, that will be removed), as well as the set of ridges on which to build the new facets (ridges with only one facet after deletion): those facets will link the ridges to the point.

Parameters:

	f	An improvable facet (non-empty visibility list)
	ref	The reference point, visible from the facet (ideally, the farthest one)
	link	After calling removeVisibleFacets, this points to a safe facet, that will not be removed.
	orphanRidges	Ridges on the border of the hole to fill, having only one neighbour. Needs to be sorted and having doubles removed after call.
	halfspace	List of the points that were visible from the set of removed facets. Needs to be sorted and having doubles removed after call.
	facetsToDelete	List of pointers to delete.
	ridgesToDelete	List of pointers to delete.

Author:

Alban Rochel

void removeVisibleFacets	(	Facet3D *	f,
		Point3D *	ref,
		Facet3D *	link,
		list< Ridge3D * > &	orphanRidges,
		list< Point3D * > &	halfspace,
		list< Facet3D * > &	facetsToDelete,
		list< Ridge3D * > &	ridgesToDelete
	)

Being given a facet and a point visible from this facet, computes the neighbouring facets that "see" the point (and, thus, that will be removed), as well as the set of ridges on which to build the new facets (ridges with only one facet after deletion): those facets will link the ridges to the point.

Parameters:

	f	An improvable facet (non-empty visibility list)
	ref	The reference point, visible from the facet (ideally, the farthest one)
	link	After calling removeVisibleFacets, this points to a safe facet, that will not be removed.
	orphanRidges	Ridges on the border of the hole to fill, having only one neighbour. Needs to be sorted and having doubles removed after call.
	halfspace	List of the points that were visible from the set of removed facets. Needs to be sorted and having doubles removed after call.
	facetsToDelete	List of pointers to delete.
	ridgesToDelete	List of pointers to delete.

Author:

Alban Rochel

bool sortCriterionRidges	(	Ridge4D *	r1,
		Ridge4D *	r2
	)

bool uniqueCriterionRidges	(	Ridge4D *	r1,
		Ridge4D *	r2
	)