suniq.c (10588B)
1 /* Copyright (C) 2025 |Méso|Star> (contact@meso-star.com) 2 * 3 * This program is free software: you can redistribute it and/or modify 4 * it under the terms of the GNU General Public License as published by 5 * the Free Software Foundation, either version 3 of the License, or 6 * (at your option) any later version. 7 * 8 * This program is distributed in the hope that it will be useful, 9 * but WITHOUT ANY WARRANTY; without even the implied warranty of 10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 11 * GNU Lesser General Public License for more details. 12 * 13 * You should have received a copy of the GNU Lesser General Public License 14 * along with this program. If not, see <http://www.gnu.org/licenses/>. */ 15 16 #include "suniq.h" 17 18 #include <rsys/double3.h> 19 #include <rsys/dynamic_array_double.h> 20 #include <rsys/dynamic_array_size_t.h> 21 #include <rsys/hash_table.h> 22 #include <rsys/mem_allocator.h> 23 #include <rsys/ref_count.h> 24 25 struct pos { double xyz[3]; }; 26 static const struct pos POS_NULL = {0}; 27 28 static INLINE size_t 29 pos_hash(const struct pos* pos) 30 { 31 ASSERT(pos); 32 return (size_t)hash_fnv64(pos->xyz, sizeof(pos->xyz)); 33 } 34 35 static INLINE char 36 pos_eq(const struct pos* a, const struct pos* b) 37 { 38 ASSERT(a && b); 39 return (char)d3_eq(a->xyz, b->xyz); 40 } 41 42 struct key { 43 double sorted_vertices[3][3]; 44 }; 45 static const struct key KEY_NULL = {0}; 46 47 static INLINE size_t 48 key_hash(const struct key* key) 49 { 50 double d[9]; 51 ASSERT(key); 52 d3_set(d+0, key->sorted_vertices[0]); 53 d3_set(d+3, key->sorted_vertices[1]); 54 d3_set(d+6, key->sorted_vertices[2]); 55 return (size_t)hash_fnv64(d, sizeof(d)); 56 } 57 58 static INLINE char 59 key_eq(const struct key* a, const struct key* b) 60 { 61 ASSERT(a && b); 62 return (char) 63 ( d3_eq(a->sorted_vertices[0], b->sorted_vertices[0]) 64 && d3_eq(a->sorted_vertices[1], b->sorted_vertices[1]) 65 && d3_eq(a->sorted_vertices[2], b->sorted_vertices[2])); 66 } 67 68 /* Generate the hash table that maps a triangle key to an index */ 69 #define HTABLE_NAME key2itri 70 #define HTABLE_KEY struct key 71 #define HTABLE_KEY_FUNCTOR_HASH key_hash 72 #define HTABLE_KEY_FUNCTOR_EQ key_eq 73 #define HTABLE_DATA size_t 74 #include <rsys/hash_table.h> 75 76 /* Generate the hash table that maps a position to an index */ 77 #define HTABLE_NAME pos2ivtx 78 #define HTABLE_KEY struct pos 79 #define HTABLE_KEY_FUNCTOR_HASH pos_hash 80 #define HTABLE_KEY_FUNCTOR_EQ pos_eq 81 #define HTABLE_DATA size_t 82 #include <rsys/hash_table.h> 83 84 struct suniq { 85 struct mem_allocator* allocator; 86 87 struct htable_key2itri key2itri; 88 struct htable_pos2ivtx pos2ivtx; 89 90 struct darray_size_t indices; /* List of size_t[3] */ 91 struct darray_double positions; /* List of double[3] */ 92 ref_T ref; 93 }; 94 95 /******************************************************************************* 96 * Helper functions 97 ******************************************************************************/ 98 /* Return an integer greater than, equal to, or less than 0, if a is greater 99 * than, equal to, or less than b, respectively */ 100 static INLINE int 101 cmp_d3(const double a[3], const double b[3]) 102 { 103 ASSERT(a && b); 104 return a[0] < b[0] ? -1 : a[0] > b[0] ? +1 105 : a[1] < b[1] ? -1 : a[1] > b[1] ? +1 106 : a[2] < b[2] ? -1 : a[2] > b[2] ? +1 107 : 0; 108 } 109 110 static void 111 key_setup(struct key* key, const struct suniq_triangle* tri) 112 { 113 double (*v)[3] = NULL; 114 115 ASSERT(key && tri); 116 117 d3_set(key->sorted_vertices[0], tri->vertices[0]); 118 d3_set(key->sorted_vertices[1], tri->vertices[1]); 119 d3_set(key->sorted_vertices[2], tri->vertices[2]); 120 121 #define SWAP3(A, B) { \ 122 SWAP(double, A[0], B[0]); \ 123 SWAP(double, A[1], B[1]); \ 124 SWAP(double, A[2], B[2]); \ 125 } (void)0 126 127 /* Bubble sort (ascending order) */ 128 v = key->sorted_vertices; 129 if(cmp_d3(v[0], v[1]) > 0) SWAP3(v[0], v[1]); 130 if(cmp_d3(v[1], v[2]) > 0) SWAP3(v[1], v[2]); 131 if(cmp_d3(v[0], v[1]) > 0) SWAP3(v[0], v[1]); 132 133 #undef SWAP3 134 } 135 136 static res_T 137 save_vertex(struct suniq* suniq, const struct pos* vertex, size_t* out_ivtx) 138 { 139 size_t ivtx = SIZE_MAX; /* Vertex index */ 140 int i = 0; 141 res_T res = RES_OK; 142 143 ASSERT(suniq && vertex && out_ivtx); 144 145 /* Define the vertex index */ 146 ivtx = darray_double_size_get(&suniq->positions) / 3/*#coords per vertex*/; 147 148 /* Save vertex coordinates */ 149 FOR_EACH(i, 0, 3) { 150 res = darray_double_push_back(&suniq->positions, &vertex->xyz[i]); 151 if(res != RES_OK) goto error; 152 } 153 154 /* Register the vertex */ 155 res = htable_pos2ivtx_set(&suniq->pos2ivtx, vertex, &ivtx); 156 if(res != RES_OK) goto error; 157 158 exit: 159 *out_ivtx = ivtx; 160 return res; 161 error: 162 ivtx = SIZE_MAX; 163 goto exit; 164 } 165 166 static res_T 167 register_vertex(struct suniq* suniq, const double vertex[3], size_t* out_id) 168 { 169 struct pos pos = POS_NULL; 170 size_t* vertex_exist = NULL; 171 size_t id = SIZE_MAX; 172 res_T res = RES_OK; 173 174 ASSERT(suniq && vertex && out_id); 175 176 d3_set(pos.xyz, vertex); 177 178 vertex_exist = htable_pos2ivtx_find(&suniq->pos2ivtx, &pos); 179 if(vertex_exist) { 180 id = *vertex_exist; 181 } else { 182 res = save_vertex(suniq, &pos, &id); 183 if(res != RES_OK) goto error; 184 } 185 186 exit: 187 *out_id = id; 188 return res; 189 error: 190 id = SIZE_MAX; 191 goto exit; 192 } 193 194 static res_T 195 save_triangle 196 (struct suniq* suniq, 197 const struct suniq_triangle* triangle, 198 const struct key* key, 199 size_t* out_itri) 200 { 201 size_t itri = SIZE_MAX; /* Trinngle index */ 202 int i = 0; 203 res_T res = RES_OK; 204 205 ASSERT(suniq && triangle && key && out_itri); 206 207 /* Define the triangle index */ 208 itri = darray_size_t_size_get(&suniq->indices) / 3/*#verices par triangle*/; 209 210 /* Save triangle indices */ 211 FOR_EACH(i, 0, 3) { 212 size_t ivtx = 0; 213 214 res = register_vertex(suniq, triangle->vertices[i], &ivtx); 215 if(res != RES_OK) goto error; 216 res = darray_size_t_push_back(&suniq->indices, &ivtx); 217 if(res != RES_OK) goto error; 218 } 219 220 /* Register the triangle */ 221 res = htable_key2itri_set(&suniq->key2itri, key, &itri); 222 if(res != RES_OK) goto error; 223 224 exit: 225 *out_itri = itri; 226 return res; 227 error: 228 itri = SIZE_MAX; 229 goto exit; 230 } 231 232 static void 233 release_suniq(ref_T* ref) 234 { 235 struct suniq* suniq = CONTAINER_OF(ref, struct suniq, ref); 236 237 ASSERT(ref); 238 239 htable_key2itri_release(&suniq->key2itri); 240 htable_pos2ivtx_release(&suniq->pos2ivtx); 241 darray_size_t_release(&suniq->indices); 242 darray_double_release(&suniq->positions); 243 MEM_RM(suniq->allocator, suniq); 244 } 245 246 /******************************************************************************* 247 * Exported functions 248 ******************************************************************************/ 249 res_T 250 suniq_create(struct mem_allocator* allocator, struct suniq** out_suniq) 251 { 252 struct mem_allocator* mem_allocator = NULL; 253 struct suniq* suniq = NULL; 254 res_T res = RES_OK; 255 256 if(!out_suniq) { res = RES_BAD_ARG; goto error; } 257 258 mem_allocator = allocator ? allocator : &mem_default_allocator; 259 suniq = MEM_CALLOC(mem_allocator, 1, sizeof(*suniq)); 260 if(!suniq) { res = RES_MEM_ERR; goto error; } 261 262 ref_init(&suniq->ref); 263 suniq->allocator = mem_allocator; 264 htable_key2itri_init(suniq->allocator, &suniq->key2itri); 265 htable_pos2ivtx_init(suniq->allocator, &suniq->pos2ivtx); 266 darray_size_t_init(suniq->allocator, &suniq->indices); 267 darray_double_init(suniq->allocator, &suniq->positions); 268 269 exit: 270 if(out_suniq) *out_suniq = suniq; 271 return res; 272 error: 273 if(suniq) { SUNIQ(ref_put(suniq)); suniq = NULL; } 274 goto exit; 275 } 276 277 res_T 278 suniq_ref_get(struct suniq* suniq) 279 { 280 return suniq ? ref_get(&suniq->ref), RES_OK : RES_BAD_ARG; 281 } 282 283 res_T 284 suniq_ref_put(struct suniq* suniq) 285 { 286 return suniq ? ref_put(&suniq->ref, release_suniq), RES_OK : RES_BAD_ARG; 287 } 288 289 res_T 290 suniq_register_triangle 291 (struct suniq* suniq, 292 const struct suniq_triangle* tri, 293 size_t* out_id) /* Can be NULL */ 294 { 295 struct key key = KEY_NULL; 296 size_t* triangle_exist = NULL; 297 size_t id = SIZE_MAX; /* Index of the triangle */ 298 res_T res = RES_OK; 299 300 if(!suniq || !tri) { res = RES_BAD_ARG; goto error; } 301 302 key_setup(&key, tri); 303 304 triangle_exist = htable_key2itri_find(&suniq->key2itri, &key); 305 if(triangle_exist) { 306 id = *triangle_exist; 307 } else { 308 res = save_triangle(suniq, tri, &key, &id); 309 if(res != RES_OK) goto error; 310 } 311 312 exit: 313 if(out_id) *out_id = id; 314 return res; 315 error: 316 id = SIZE_MAX; 317 goto exit; 318 } 319 320 res_T 321 suniq_get_triangle 322 (const struct suniq* suniq, 323 const size_t id, 324 struct suniq_triangle* triangle) 325 { 326 struct suniq_desc desc = SUNIQ_DESC_NULL; 327 res_T res = RES_OK; 328 329 if((res = suniq_get_desc(suniq, &desc)) != RES_OK) goto error; 330 if((res = suniq_desc_get_triangle(&desc, id, triangle)) != RES_OK) goto error; 331 332 exit: 333 return res; 334 error: 335 goto exit; 336 } 337 338 res_T 339 suniq_get_desc(const struct suniq* suniq, struct suniq_desc* desc) 340 { 341 if(!suniq || !desc) return RES_BAD_ARG; 342 desc->indices = darray_size_t_cdata_get(&suniq->indices); 343 desc->positions = darray_double_cdata_get(&suniq->positions); 344 desc->ntriangles = darray_size_t_size_get(&suniq->indices)/3/*#ids*/; 345 desc->nvertices = darray_double_size_get(&suniq->positions)/3/*#coords*/; 346 return RES_OK; 347 } 348 349 res_T 350 suniq_desc_get_vertex 351 (const struct suniq_desc* desc, 352 const size_t ivertex, 353 double vertex[3]) 354 { 355 if(!desc || ivertex >= desc->nvertices || !vertex) return RES_BAD_ARG; 356 357 vertex[0] = desc->positions[ivertex*3/*#coords per vertex*/+0]; 358 vertex[1] = desc->positions[ivertex*3/*#coords per vertex*/+1]; 359 vertex[2] = desc->positions[ivertex*3/*#coords per vertex*/+2]; 360 361 return RES_OK; 362 } 363 364 res_T 365 suniq_desc_get_triangle_indices 366 (const struct suniq_desc* desc, 367 const size_t itriangle, 368 size_t indices[3]) 369 { 370 if(!desc || itriangle >= desc->ntriangles || !indices) return RES_BAD_ARG; 371 372 indices[0] = desc->indices[itriangle*3/*#indices per triangle*/+0]; 373 indices[1] = desc->indices[itriangle*3/*#indices per triangle*/+1]; 374 indices[2] = desc->indices[itriangle*3/*#indices per triangle*/+2]; 375 376 return RES_OK; 377 } 378 379 res_T 380 suniq_desc_get_triangle 381 (const struct suniq_desc* desc, 382 const size_t itriangle, 383 struct suniq_triangle* triangle) 384 { 385 size_t indices[3] = {0,0,0}; 386 int i = 0; 387 res_T res = RES_OK; 388 389 if(!triangle) { res = RES_BAD_ARG; goto error; } 390 391 res = suniq_desc_get_triangle_indices(desc, itriangle, indices); 392 if(res != RES_OK) goto error; 393 394 FOR_EACH(i, 0, 3) { 395 res = suniq_desc_get_vertex(desc, indices[i], triangle->vertices[i]); 396 if(res != RES_OK) goto error; 397 } 398 399 exit: 400 return res; 401 error: 402 goto exit; 403 } 404 405 res_T 406 suniq_clear(struct suniq* suniq) 407 { 408 if(!suniq) return RES_BAD_ARG; 409 410 htable_key2itri_clear(&suniq->key2itri); 411 htable_pos2ivtx_clear(&suniq->pos2ivtx); 412 darray_size_t_clear(&suniq->indices); 413 darray_double_clear(&suniq->positions); 414 415 return RES_OK; 416 }