convhull_3d.h File Reference

An implementation of the 3-D quickhull algorithm [1]. More...

Go to the source code of this file.

Data Structures
struct	ch_vertex
	vertex structure, used by convhull_3d More...

Typedefs
typedef double	CH_FLOAT
typedef ch_vertex	ch_vec3

Functions
void	convhull_3d_build (ch_vertex *const in_vertices, const int nVert, int **out_faces, CH_FLOAT **out_cf, CH_FLOAT **out_df, int *nOut_faces)
	Builds the 3-D convexhull using the quickhull algorithm [1].
void	convhull_nd_build (CH_FLOAT *const in_vertices, const int nVert, const int d, int **out_faces, CH_FLOAT **out_cf, CH_FLOAT **out_df, int *nOut_faces)
	Builds the N-D convexhull using the quickhull algorithm [1].
void	convhull_3d_export_obj (ch_vertex *const vertices, const int nVert, int *const faces, const int nFaces, const int keepOnlyUsedVerticesFLAG, char *const obj_filename)
	Exports the vertices, face indices, and face normals, as an '.obj' file, ready for the GPU.
void	convhull_3d_export_m (ch_vertex *const vertices, const int nVert, int *const faces, const int nFaces, char *const m_filename)
	Exports the vertices, face indices, and face normals, as an '.m' file, for Matlab verification.
void	extractVerticesFromObjFile (char *const obj_filename, ch_vertex **out_vertices, int *out_nVert)
	Reads an '.obj' file and extracts only the vertices.

Detailed Description

An implementation of the 3-D quickhull algorithm [1].

The code is largely derived from the "computational-geometry-toolbox" by George Papazafeiropoulos (c) 2014, originally distributed under the BSD (2-clause) license. Taken from: https://github.com/leomccormack/convhull_3d

Dependencies

CBLAS (optional) for speed ups, especially for very large meshes

See also

[1] C. Bradford, Barber, David P. Dobkin and Hannu Huhdanpaa, "The Quickhull Algorithm for Convex Hull". Geometry Center Technical Report GCG53, July 30, 1993

Author

Leo McCormack

Date

02.10.2017

License

MIT

Definition in file convhull_3d.h.

Typedef Documentation

CH_FLOAT

typedef double CH_FLOAT

Definition at line 57 of file convhull_3d.h.

ch_vec3

typedef ch_vertex ch_vec3

Definition at line 70 of file convhull_3d.h.

Function Documentation

convhull_3d_build()

void convhull_3d_build	(	ch_vertex *const	in_vertices,
		const int	nVert,
		int **	out_faces,
		CH_FLOAT **	out_cf,
		CH_FLOAT **	out_df,
		int *	nOut_faces )

Builds the 3-D convexhull using the quickhull algorithm [1].

Parameters

[in]	in_vertices	Vector of input vertices; nVert x 1
[in]	nVert	Number of vertices
[out]	out_faces	(&) output face indices; FLAT: nOut_faces x 3
[out]	out_cf	(&) contains the coefficients of the planes (set to NULL if not wanted); FLAT: nOut_faces x 3
[out]	out_df	(&) contains the constant terms of the planes (set to NULL if not wanted); nOut_faces x 1
[out]	nOut_faces	(&) number of output face indices

See also

[1] C. Bradford, Barber, David P. Dobkin and Hannu Huhdanpaa, "The Quickhull Algorithm for Convex Hull". Geometry Center Technical Report GCG53, July 30, 1993

Definition at line 367 of file convhull_3d.c.

convhull_3d_export_m()

void convhull_3d_export_m	(	ch_vertex *const	vertices,
		const int	nVert,
		int *const	faces,
		const int	nFaces,
		char *const	m_filename )

Exports the vertices, face indices, and face normals, as an '.m' file, for Matlab verification.

Parameters

[in]	vertices	Vector of input vertices; nVert x 1
[in]	nVert	Number of vertices
[in]	faces	Face indices; flat: nFaces x 3
[in]	nFaces	Number of faces in hull
[in]	m_filename	*.m filename, WITHOUT extension

Definition at line 1416 of file convhull_3d.c.

convhull_3d_export_obj()

void convhull_3d_export_obj	(	ch_vertex *const	vertices,
		const int	nVert,
		int *const	faces,
		const int	nFaces,
		const int	keepOnlyUsedVerticesFLAG,
		char *const	obj_filename )

Exports the vertices, face indices, and face normals, as an '.obj' file, ready for the GPU.

Parameters

[in]	vertices	Vector of input vertices; nVert x 1
[in]	nVert	Number of vertices
[in]	faces	Face indices; flat: nFaces x 3
[in]	nFaces	Number of faces in hull
[in]	keepOnlyUsedVerticesFLAG	'0' exports in_vertices, '1': exports Only used vertices
[in]	obj_filename	*.obj filename, WITHOUT extension

Definition at line 1336 of file convhull_3d.c.

convhull_nd_build()

void convhull_nd_build	(	CH_FLOAT *const	in_vertices,
		const int	nVert,
		const int	d,
		int **	out_faces,
		CH_FLOAT **	out_cf,
		CH_FLOAT **	out_df,
		int *	nOut_faces )

Builds the N-D convexhull using the quickhull algorithm [1].

Parameters

[in]	in_vertices	Matrix of nVertices in 'd' dimensions; FLAT:nVert x d
[in]	nVert	Number of vertices
[in]	d	Number of dimensions
[out]	out_faces	(&) output face indices; FLAT: nOut_faces x d
[out]	out_cf	(&) contains the coefficients of the planes (set to NULL if not wanted); FLAT: nOut_faces x d
[out]	out_df	(&) contains the constant terms of the planes (set to NULL if not wanted); nOut_faces x 1
[out]	nOut_faces	(&) number of output face indices

See also

[1] C. Bradford, Barber, David P. Dobkin and Hannu Huhdanpaa, "The Quickhull Algorithm for Convex Hull". Geometry Center Technical Report GCG53, July 30, 1993

Definition at line 849 of file convhull_3d.c.

extractVerticesFromObjFile()

void extractVerticesFromObjFile	(	char *const	obj_filename,
		ch_vertex **	out_vertices,
		int *	out_nVert )

Reads an '.obj' file and extracts only the vertices.

Parameters

[in]	obj_filename	*.obj filename, WITHOUT extension
[out]	out_vertices	(&) output vertices; out_nVert x 1
[out]	out_nVert	(&) number of vertices

Definition at line 1452 of file convhull_3d.c.