SAF
Loading...
Searching...
No Matches
convhull_3d.c File Reference

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"

Go to the source code of this file.

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_verticesVector of input vertices; nVert x 1
[in]nVertNumber 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]verticesVector of input vertices; nVert x 1
[in]nVertNumber of vertices
[in]facesFace indices; flat: nFaces x 3
[in]nFacesNumber 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]verticesVector of input vertices; nVert x 1
[in]nVertNumber of vertices
[in]facesFace indices; flat: nFaces x 3
[in]nFacesNumber 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_verticesMatrix of nVertices in 'd' dimensions; FLAT:nVert x d
[in]nVertNumber of vertices
[in]dNumber 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.