quickhull.h (3016B)
1 // 2 // LICENCE: 3 // The MIT License (MIT) 4 // 5 // Copyright (c) 2016 Karim Naaji, karim.naaji@gmail.com 6 // 7 // Permission is hereby granted, free of charge, to any person obtaining a copy 8 // of this software and associated documentation files (the "Software"), to deal 9 // in the Software without restriction, including without limitation the rights 10 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 11 // copies of the Software, and to permit persons to whom the Software is 12 // furnished to do so, subject to the following conditions: 13 // 14 // The above copyright notice and this permission notice shall be included in all 15 // copies or substantial portions of the Software. 16 // 17 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 18 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 19 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 20 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 21 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 22 // OUT OF OR IN CONNECTION WITH THE 23 // 24 // REFERENCES: 25 // [1] http://box2d.org/files/GDC2014/DirkGregorius_ImplementingQuickHull.pdf 26 // [2] http://www.cs.smith.edu/~orourke/books/compgeom.html 27 // [3] http://www.flipcode.com/archives/The_Half-Edge_Data_Structure.shtml 28 // [4] http://doc.cgal.org/latest/HalfedgeDS/index.html 29 // [5] http://thomasdiewald.com/blog/?p=1888 30 // [6] https://fgiesen.wordpress.com/2012/02/21/half-edge-based-mesh-representations-theory/ 31 // 32 // HOWTO: 33 // #define QUICKHULL_IMPLEMENTATION 34 // #define QUICKHULL_DEBUG // Only if assertions need to be checked 35 // #include "quickhull.h" 36 // 37 // HISTORY: 38 // - 1.0.1 (2016-11-01): Various improvements over epsilon issues and degenerate faces 39 // Debug functionalities to test final results dynamically 40 // API to export hull meshes in OBJ files 41 // - 1.0 (2016-09-10): Initial 42 // 43 // TODO: 44 // - use float* from public interface 45 // - reduce memory usage 46 47 #ifndef QUICKHULL_H 48 #define QUICKHULL_H 49 50 // ------------------------------------------------------------------------------------------------ 51 // QUICKHULL PUBLIC API 52 // 53 54 typedef struct qh_vertex { 55 union { 56 float v[3]; 57 struct { 58 float x; 59 float y; 60 float z; 61 }; 62 }; 63 } qh_vertex_t; 64 65 typedef qh_vertex_t qh_vec3_t; 66 67 typedef struct qh_mesh { 68 qh_vertex_t* vertices; 69 qh_vec3_t* normals; 70 unsigned int* indices; 71 unsigned int* normalindices; 72 unsigned int nindices; 73 unsigned int nvertices; 74 unsigned int nnormals; 75 } qh_mesh_t; 76 77 qh_mesh_t qh_quickhull3d(qh_vertex_t const* vertices, unsigned int nvertices); 78 79 void qh_mesh_export(qh_mesh_t const* mesh, char const* filename); 80 81 void qh_free_mesh(qh_mesh_t mesh); 82 83 // 84 // END QUICKHULL PUBLIC API 85 // ------------------------------------------------------------------------------------------------ 86 87 #endif // QUICKHULL_H 88