SAF
|
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. | |
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
CBLAS (optional) for speed ups, especially for very large meshes
Definition in file convhull_3d.c.
#define CH_FLT_MAX DBL_MAX |
Definition at line 74 of file convhull_3d.c.
#define CH_FLT_MIN DBL_MIN |
Definition at line 73 of file convhull_3d.c.
#define CH_MAX_NUM_FACES 50000 |
Definition at line 83 of file convhull_3d.c.
#define CH_NOISE_VAL 0.0000001 |
Definition at line 75 of file convhull_3d.c.
#define CONVHULL_3D_USE_CBLAS |
Definition at line 58 of file convhull_3d.c.
#define CONVHULL_ND_MAX_DIMENSIONS ( 5 ) |
Definition at line 54 of file convhull_3d.c.
#define CV_STRCAT | ( | a, | |
b ) strcat(a,b); |
Definition at line 66 of file convhull_3d.c.
#define CV_STRNCPY | ( | a, | |
b, | |||
c ) strncpy(a,b,c); |
Definition at line 65 of file convhull_3d.c.
#define MAX | ( | a, | |
b ) (( (a) > (b) ) ? (a) : (b) ) |
Definition at line 81 of file convhull_3d.c.
#define MIN | ( | a, | |
b ) (( (a) < (b) ) ? (a) : (b) ) |
Definition at line 78 of file convhull_3d.c.
|
static |
Definition at line 110 of file convhull_3d.c.
|
static |
Definition at line 126 of file convhull_3d.c.
|
static |
Definition at line 118 of file convhull_3d.c.
|
static |
Definition at line 134 of file convhull_3d.c.
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].
[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 |
Definition at line 367 of file convhull_3d.c.
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.
[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.
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.
[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.
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].
[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 |
Definition at line 849 of file convhull_3d.c.
Definition at line 206 of file convhull_3d.c.
|
static |
Definition at line 216 of file convhull_3d.c.
|
static |
Definition at line 232 of file convhull_3d.c.
void extractVerticesFromObjFile | ( | char *const | obj_filename, |
ch_vertex ** | out_vertices, | ||
int * | out_nVert ) |
Reads an '.obj' file and extracts only the vertices.
[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.
|
static |
Definition at line 342 of file convhull_3d.c.
|
static |
Definition at line 244 of file convhull_3d.c.
|
static |
Definition at line 291 of file convhull_3d.c.
|
static |
Definition at line 142 of file convhull_3d.c.
|
static |
Definition at line 174 of file convhull_3d.c.