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

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <float.h>
#include <ctype.h>
#include "convhull_3d.h"
#include "../modules/saf_utilities/saf_utilities.h"
#include "saf_externals.h"

Data Structures
struct	float_w_idx
	Helper struct for qsort in convhull_3d_build() More...

struct	int_w_idx
	Helper struct for qsort in convhull_3d_build() More...

Macros
#define	CONVHULL_ND_MAX_DIMENSIONS ( 5 )

#define	CONVHULL_3D_USE_CBLAS

#define	CV_STRNCPY(a, b, c) strncpy(a,b,c);

#define	CV_STRCAT(a, b) strcat(a,b);

#define	CH_FLT_MIN DBL_MIN

#define	CH_FLT_MAX DBL_MAX

#define	CH_NOISE_VAL 0.0000001

#define	MIN(a, b) (( (a) < (b) ) ? (a) : (b) )

#define	MAX(a, b) (( (a) > (b) ) ? (a) : (b) )

#define	CH_MAX_NUM_FACES 50000

Functions
static int	cmp_asc_float (const void , const void )

static int	cmp_desc_float (const void , const void )

static int	cmp_asc_int (const void , const void )

static int	cmp_desc_int (const void , const void )

static void	sort_float (CH_FLOAT , CH_FLOAT , int *, int, int)

static void	sort_int (int , int , int *, int, int)

static ch_vec3	cross (ch_vec3 , ch_vec3 )

static CH_FLOAT	det_4x4 (CH_FLOAT *)

static void	plane_3d (CH_FLOAT , CH_FLOAT , CH_FLOAT *)

static void	ismember (int , int , int *, int, int)

static CH_FLOAT	det_NxN (CH_FLOAT *m, int d)

static void	plane_nd (const int Nd, CH_FLOAT p, CH_FLOAT c, CH_FLOAT *d)

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.c.

Macro Definition Documentation

◆ CH_FLT_MAX

#define CH_FLT_MAX DBL_MAX

Definition at line 74 of file convhull_3d.c.

◆ CH_FLT_MIN

#define CH_FLT_MIN DBL_MIN

Definition at line 73 of file convhull_3d.c.

◆ CH_MAX_NUM_FACES

#define CH_MAX_NUM_FACES 50000

Definition at line 83 of file convhull_3d.c.

◆ CH_NOISE_VAL

#define CH_NOISE_VAL 0.0000001

Definition at line 75 of file convhull_3d.c.

◆ CONVHULL_3D_USE_CBLAS

#define CONVHULL_3D_USE_CBLAS

Definition at line 58 of file convhull_3d.c.

◆ CONVHULL_ND_MAX_DIMENSIONS

#define CONVHULL_ND_MAX_DIMENSIONS ( 5 )

Definition at line 54 of file convhull_3d.c.

◆ CV_STRCAT

#define CV_STRCAT	(		a,
			b ) strcat(a,b);

Definition at line 66 of file convhull_3d.c.

◆ CV_STRNCPY

#define CV_STRNCPY	(	a,
		b,
		c ) strncpy(a,b,c);

Definition at line 65 of file convhull_3d.c.

◆ MAX

#define MAX	(		a,
			b ) (( (a) > (b) ) ? (a) : (b) )

Definition at line 81 of file convhull_3d.c.

◆ MIN

#define MIN	(		a,
			b ) (( (a) < (b) ) ? (a) : (b) )

Definition at line 78 of file convhull_3d.c.

Function Documentation

◆ cmp_asc_float()

static int cmp_asc_float	(	const void *	a,
		const void *	b )

static

Definition at line 110 of file convhull_3d.c.

◆ cmp_asc_int()

static int cmp_asc_int	(	const void *	a,
		const void *	b )

static

Definition at line 126 of file convhull_3d.c.

◆ cmp_desc_float()

static int cmp_desc_float	(	const void *	a,
		const void *	b )

static

Definition at line 118 of file convhull_3d.c.

◆ cmp_desc_int()

static int cmp_desc_int	(	const void *	a,
		const void *	b )

static

Definition at line 134 of file convhull_3d.c.

◆ 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.

◆ cross()

static ch_vec3 cross	(	ch_vec3 *	v1,
		ch_vec3 *	v2 )

static

Definition at line 206 of file convhull_3d.c.

◆ det_4x4()

static CH_FLOAT det_4x4 ( CH_FLOAT * m )

static

Definition at line 216 of file convhull_3d.c.

◆ det_NxN()

static CH_FLOAT det_NxN	(	CH_FLOAT *	m,
		int	d )

static

Definition at line 232 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.

◆ ismember()

static void ismember	(	int *	pLeft,
		int *	pRight,
		int *	pOut,
		int	nLeftElements,
		int	nRightElements )

static

Definition at line 342 of file convhull_3d.c.

◆ plane_3d()

static void plane_3d	(	CH_FLOAT *	p,
		CH_FLOAT *	c,
		CH_FLOAT *	d )

static

Definition at line 244 of file convhull_3d.c.

◆ plane_nd()

static void plane_nd	(	const int	Nd,
		CH_FLOAT *	p,
		CH_FLOAT *	c,
		CH_FLOAT *	d )

static

Definition at line 291 of file convhull_3d.c.

◆ sort_float()

static void sort_float	(	CH_FLOAT *	in_vec,
		CH_FLOAT *	out_vec,
		int *	new_idices,
		int	len,
		int	descendFLAG )

static

Definition at line 142 of file convhull_3d.c.

◆ sort_int()

static void sort_int	(	int *	in_vec,
		int *	out_vec,
		int *	new_idices,
		int	len,
		int	descendFLAG )

static

Definition at line 174 of file convhull_3d.c.

Data Structures

Macros

Functions

Detailed Description

Dependencies

Macro Definition Documentation

◆ CH_FLT_MAX

◆ CH_FLT_MIN

◆ CH_MAX_NUM_FACES

◆ CH_NOISE_VAL

◆ CONVHULL_3D_USE_CBLAS

◆ CONVHULL_ND_MAX_DIMENSIONS

◆ CV_STRCAT

◆ CV_STRNCPY

◆ MAX

◆ MIN

Function Documentation

◆ cmp_asc_float()

◆ cmp_asc_int()

◆ cmp_desc_float()

◆ cmp_desc_int()

◆ convhull_3d_build()

◆ convhull_3d_export_m()

◆ convhull_3d_export_obj()

◆ convhull_nd_build()

◆ cross()

◆ det_4x4()

◆ det_NxN()

◆ extractVerticesFromObjFile()

◆ ismember()

◆ plane_3d()

◆ plane_nd()

◆ sort_float()

◆ sort_int()