scpr_mesh.c (14270B)
1 /* Copyright (C) 2016-2018, 2021-2024 |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 General Public License for more details. 12 * 13 * You should have received a copy of the GNU General Public License 14 * along with this program. If not, see <http://www.gnu.org/licenses/>. */ 15 16 #include "scpr.h" 17 #include "scpr_c.h" 18 19 #include <rsys/mem_allocator.h> 20 #include <rsys/logger.h> 21 22 #include <polygon.h> 23 24 /******************************************************************************* 25 * Helper functions 26 ******************************************************************************/ 27 static FINLINE Clipper2Lib::ClipType 28 scpr_operation_to_clip_type(const enum scpr_operation op) 29 { 30 Clipper2Lib::ClipType ctype; 31 switch(op) { 32 case SCPR_AND: ctype = Clipper2Lib::ClipType::Intersection; break; 33 case SCPR_SUB: ctype = Clipper2Lib::ClipType::Difference; break; 34 default: FATAL("Unreachable code\n"); break; 35 } 36 return ctype; 37 } 38 39 static INLINE int 40 aabb_intersect 41 (const int64_t lower0[2], 42 const int64_t upper0[2], 43 const int64_t lower1[2], 44 const int64_t upper1[2]) 45 { 46 ASSERT(lower0 && upper0 && lower1 && upper1); 47 return lower0[0] < upper1[0] 48 && lower0[1] < upper1[1] 49 && lower1[0] < upper0[0] 50 && lower1[1] < upper0[1]; 51 } 52 53 static INLINE int 54 aabb_is_degenerated(const int64_t lower[2], const int64_t upper[2]) 55 { 56 ASSERT(lower && upper); 57 return lower[0] >= upper[0] || lower[1] >= upper[1]; 58 } 59 60 static void 61 triangle_compute_aabb 62 (int64_t tri[3][2], 63 int64_t lower[2], 64 int64_t upper[2]) 65 { 66 size_t ivert; 67 ASSERT(tri && lower && upper); 68 69 lower[0] = lower[1] = INT64_MAX; 70 upper[0] = upper[1] = INT64_MIN; 71 FOR_EACH(ivert, 0, 3) { 72 int i; 73 for(i = 0; i < 2; i++) { 74 if(lower[i] > tri[ivert][i]) lower[i] = tri[ivert][i]; 75 if(upper[i] < tri[ivert][i]) upper[i] = tri[ivert][i]; 76 } 77 } 78 } 79 80 static res_T 81 register_vertex 82 (const int64_t pos[2], 83 struct darray_int64* coords, 84 struct darray_uint32* indices, 85 struct htable_vertex* vertices) 86 { 87 struct vertex v; 88 uint32_t* pid, id; 89 unsigned i; 90 res_T res = RES_OK; 91 ASSERT(pos && coords && indices && vertices); 92 93 for(i = 0; i < 2; i++) v.pos[i] = pos[i]; 94 95 v.pos[0] = v.pos[0]; 96 v.pos[1] = v.pos[1]; 97 98 pid = htable_vertex_find(vertices, &v); 99 100 if(pid) { 101 id = *pid; 102 } else { 103 const size_t count = darray_int64_size_get(coords); 104 105 ASSERT(count <= UINT32_MAX); 106 ERR(darray_int64_resize(coords, count+2/*#coords*/)); 107 for(i = 0; i < 2; i++) darray_int64_data_get(coords)[count+i] = pos[i]; 108 109 id = (uint32_t)count / 2; 110 ERR(htable_vertex_set(vertices, &v, &id)); 111 } 112 113 ERR(darray_uint32_push_back(indices, &id)); 114 115 exit: 116 return res; 117 error: 118 goto exit; 119 } 120 121 static FINLINE res_T 122 register_triangle 123 (int64_t tri[3][2], 124 struct darray_int64* coords, /* Vertex buffer */ 125 struct darray_uint32* indices, /* Index buffer */ 126 struct htable_vertex* vertices) /* Map a vertex to its index */ 127 { 128 size_t ivert; 129 res_T res = RES_OK; 130 ASSERT(tri && coords && indices && vertices); 131 FOR_EACH(ivert, 0, 3) { 132 ERR(register_vertex(tri[ivert], coords, indices, vertices)); 133 } 134 exit: 135 return RES_OK; 136 error: 137 goto exit; 138 } 139 140 141 static res_T 142 register_paths 143 (struct scpr_device* dev, 144 const Clipper2Lib::Paths64& paths, 145 struct darray_int64* coords, /* Vertex buffer */ 146 struct darray_uint32* indices, /* Index buffer */ 147 struct htable_vertex* vertices, /* Map a vertex to its index */ 148 struct polygon* polygon) /* Used to triangulate the clipped polygons */ 149 { 150 size_t ivert; 151 size_t ipath; 152 res_T res = RES_OK; 153 ASSERT(coords && indices && vertices); 154 155 FOR_EACH(ipath, 0, paths.size()) { 156 if(paths[ipath].size() == 3) { 157 FOR_EACH(ivert, 0, 3) { 158 int64_t pos[2]; 159 pos[0] = paths[ipath][ivert].x; 160 pos[1] = paths[ipath][ivert].y; 161 ERR(register_vertex(pos, coords, indices, vertices)); 162 } 163 } else { 164 /* Triangulate the clipped primitive */ 165 const uint32_t* ids; 166 uint32_t nids; 167 168 /* Define the contour of the polygon to triangulate */ 169 POLYGON(clear(polygon)); 170 FOR_EACH(ivert, 0, paths[ipath].size()) { 171 float fpos[3] = {0.f, 0.f, 0.f}; 172 double posd[2]; 173 int64_t pos64[2]; 174 175 pos64[0] = paths[ipath][ivert].x; 176 pos64[1] = paths[ipath][ivert].y; 177 SCPR(device_unscale(dev, pos64, 2, posd)); 178 179 fpos[0] = (float)posd[0], fpos[1] = (float)posd[1]; 180 ERR(polygon_vertex_add(polygon, fpos)); 181 } 182 ERR(polygon_triangulate(polygon, &ids, &nids)); 183 184 FOR_EACH(ivert, 0, nids) { 185 float fpos[3]; 186 int64_t pos64[2]; 187 double pos[2]; 188 POLYGON(vertex_get(polygon, ids[ivert], fpos)); 189 pos[0] = (double)fpos[0]; 190 pos[1] = (double)fpos[1]; 191 SCPR(device_scale(dev, pos, 2, pos64)); 192 ERR(register_vertex(pos64, coords, indices, vertices)); 193 } 194 } 195 } 196 exit: 197 return res; 198 error: 199 goto exit; 200 } 201 202 static void 203 mesh_compute_aabb 204 (const struct scpr_mesh* mesh, 205 int64_t lower[2], 206 int64_t upper[2]) 207 { 208 size_t itri, ntris, i; 209 210 SCPR(mesh_get_triangles_count(mesh, &ntris)); 211 lower[0] = lower[1] = INT64_MAX; 212 upper[0] = upper[1] = INT64_MIN; 213 214 FOR_EACH(itri, 0, ntris) { 215 size_t ids[3], ivert; 216 SCPR(mesh_get_indices(mesh, itri, ids)); 217 FOR_EACH(ivert, 0, 3) { 218 double pos[2]; 219 int64_t pos64[2]; 220 SCPR(mesh_get_position(mesh, ids[ivert], pos)); 221 SCPR(device_scale(mesh->device, pos, 2, pos64)); 222 for(i = 0; i < 2; i++) { 223 if(lower[i] > pos64[i]) lower[i] = pos64[i]; 224 if(upper[i] < pos64[i]) upper[i] = pos64[i]; 225 } 226 } 227 } 228 } 229 230 static void 231 mesh_release(ref_T* ref) 232 { 233 struct scpr_mesh* mesh; 234 struct mem_allocator* allocator; 235 ASSERT(ref); 236 mesh = CONTAINER_OF(ref, struct scpr_mesh, ref); 237 allocator = mesh->device->allocator; 238 SCPR(device_ref_put(mesh->device)); 239 darray_int64_release(&mesh->coords); 240 darray_uint32_release(&mesh->indices); 241 MEM_RM(allocator, mesh); 242 } 243 244 /******************************************************************************* 245 * Exported functions 246 ******************************************************************************/ 247 res_T 248 scpr_mesh_create 249 (struct scpr_device* dev, 250 struct scpr_mesh** out_mesh) 251 { 252 struct scpr_mesh* mesh = NULL; 253 res_T res = RES_OK; 254 255 if(!dev || !out_mesh) { 256 res = RES_BAD_ARG; 257 goto error; 258 } 259 260 mesh = (struct scpr_mesh*) 261 MEM_CALLOC(dev->allocator, 1, sizeof(struct scpr_mesh)); 262 if(!mesh) { 263 res = RES_MEM_ERR; 264 goto error; 265 } 266 ref_init(&mesh->ref); 267 mesh->device = dev; 268 SCPR(device_ref_get(dev)); 269 darray_int64_init(dev->allocator, &mesh->coords); 270 darray_uint32_init(dev->allocator, &mesh->indices); 271 272 exit: 273 if(out_mesh) *out_mesh = mesh; 274 return res; 275 276 error: 277 if(mesh) { 278 SCPR(mesh_ref_put(mesh)); 279 mesh = NULL; 280 } 281 goto exit; 282 } 283 284 res_T 285 scpr_mesh_ref_get(struct scpr_mesh* mesh) 286 { 287 if(!mesh) return RES_BAD_ARG; 288 ref_get(&mesh->ref); 289 return RES_OK; 290 } 291 292 res_T 293 scpr_mesh_ref_put(struct scpr_mesh* mesh) 294 { 295 if(!mesh) return RES_BAD_ARG; 296 ref_put(&mesh->ref, mesh_release); 297 return RES_OK; 298 } 299 300 res_T 301 scpr_mesh_setup_indexed_vertices 302 (struct scpr_mesh* mesh, 303 const size_t ntris, 304 void (*get_indices)(const size_t itri, size_t ids[3], void* ctx), 305 const size_t nverts, 306 void (*get_position)(const size_t ivert, double pos[2], void* ctx), 307 void* data) 308 { 309 int64_t* pos = NULL; 310 uint32_t* ids = NULL; 311 size_t i, j; 312 res_T res = RES_OK; 313 314 if(!mesh || !ntris || !get_indices || !nverts || !get_position || !data) { 315 res = RES_BAD_ARG; 316 goto error; 317 } 318 319 if(ntris > UINT32_MAX) { 320 logger_print(mesh->device->logger, LOG_ERROR, 321 "Too many triangles.\n"); 322 res = RES_BAD_ARG; 323 goto error; 324 } 325 326 if(nverts > UINT32_MAX) { 327 logger_print(mesh->device->logger, LOG_ERROR, 328 "Too many vertices.\n"); 329 res = RES_BAD_ARG; 330 goto error; 331 } 332 333 ERR(darray_int64_resize(&mesh->coords, nverts*2/*#coords per vertex*/)); 334 ERR(darray_uint32_resize(&mesh->indices, ntris*3/*#vertices per triangle*/)); 335 336 /* Fetch mesh positions */ 337 pos = darray_int64_data_get(&mesh->coords); 338 FOR_EACH(i, 0, nverts) { 339 double posd[2]; 340 get_position(i, posd, data); 341 ERR(scpr_device_scale(mesh->device, posd, 2, pos + i*2)); 342 } 343 344 /* Fetch mesh indices */ 345 ids = darray_uint32_data_get(&mesh->indices); 346 FOR_EACH(i, 0, ntris) { 347 size_t tmp[3]; 348 get_indices(i, tmp, data); 349 if(tmp[0] >= nverts || tmp[1] >= nverts || tmp[2] >= nverts) { 350 res = RES_BAD_ARG; 351 goto error; 352 } 353 for(j = 0; j < 3; j++) ids[i*3 + j] = (uint32_t)tmp[j]; 354 } 355 356 exit: 357 return res; 358 error: 359 if(mesh) { 360 darray_int64_clear(&mesh->coords); 361 darray_uint32_clear(&mesh->indices); 362 } 363 goto exit; 364 } 365 366 res_T 367 scpr_mesh_get_vertices_count(const struct scpr_mesh* mesh, size_t* nverts) 368 { 369 if(!mesh || !nverts) return RES_BAD_ARG; 370 ASSERT((darray_int64_size_get(&mesh->coords) % 2/*#coords per vertex*/)==0); 371 *nverts = darray_int64_size_get(&mesh->coords) / 2/*#coords per vertex*/; 372 return RES_OK; 373 } 374 375 res_T 376 scpr_mesh_get_triangles_count(const struct scpr_mesh* mesh, size_t* ntris) 377 { 378 if(!mesh || !ntris) return RES_BAD_ARG; 379 ASSERT((darray_uint32_size_get(&mesh->indices)%3/*#vertices per triangle*/)==0); 380 *ntris = darray_uint32_size_get(&mesh->indices) / 3/*#vertices per triangle*/; 381 return RES_OK; 382 } 383 384 res_T 385 scpr_mesh_get_indices 386 (const struct scpr_mesh* mesh, const size_t itri, size_t ids[3]) 387 { 388 size_t ntris; 389 const size_t i = itri * 3/*#vertices per triangle*/; 390 if(!mesh || !ids) return RES_BAD_ARG; 391 SCPR(mesh_get_triangles_count(mesh, &ntris)); 392 if(itri >= ntris) return RES_BAD_ARG; 393 ids[0] = darray_uint32_cdata_get(&mesh->indices)[i+0]; 394 ids[1] = darray_uint32_cdata_get(&mesh->indices)[i+1]; 395 ids[2] = darray_uint32_cdata_get(&mesh->indices)[i+2]; 396 return RES_OK; 397 } 398 399 res_T 400 scpr_mesh_get_position 401 (const struct scpr_mesh* mesh, const size_t ivert, double pos[2]) 402 { 403 size_t nverts; 404 int64_t pos64[2]; 405 const size_t i = ivert * 2/*#coords per vertex*/; 406 if(!mesh || !pos) return RES_BAD_ARG; 407 SCPR(mesh_get_vertices_count(mesh, &nverts)); 408 if(ivert >= nverts) return RES_BAD_ARG; 409 pos64[0] = darray_int64_cdata_get(&mesh->coords)[i+0]; 410 pos64[1] = darray_int64_cdata_get(&mesh->coords)[i+1]; 411 SCPR(device_unscale(mesh->device, pos64, 2, pos)); 412 return RES_OK; 413 } 414 415 res_T 416 scpr_mesh_clip 417 (struct scpr_mesh* mesh, 418 const enum scpr_operation op, 419 struct scpr_polygon* poly_desc) 420 { 421 int64_t lower[2], upper[2]; 422 struct polygon* polygon = NULL; /* Use to triangulate clipped polygons */ 423 struct darray_int64 coords; /* Coordinates of the clipped mesh */ 424 struct darray_uint32 indices; /* Indices of the clipped mesh */ 425 struct htable_vertex vertices; /* Map a coordinate to its index */ 426 Clipper2Lib::Clipper64 clipper; 427 Clipper2Lib::Paths64 output; /* Contour of the clipped polgyon */ 428 Clipper2Lib::Paths64 cand_path; /* Contour of the candidate polygon */ 429 Clipper2Lib::Path64 tmp; 430 Clipper2Lib::ClipType clip_type; /* Type of clipping to perform */ 431 size_t itri, ntris, ivert; 432 struct mem_allocator* allocator; 433 int i; 434 435 res_T res = RES_OK; 436 437 if(!mesh || !poly_desc || (unsigned)op >= SCPR_OPERATIONS_COUNT__) 438 return RES_BAD_ARG; 439 440 allocator = mesh->device->allocator; 441 clip_type = scpr_operation_to_clip_type(op); 442 443 darray_int64_init(allocator, &coords); 444 darray_uint32_init(allocator, &indices); 445 htable_vertex_init(allocator, &vertices); 446 447 if(aabb_is_degenerated(poly_desc->lower, poly_desc->upper)) goto exit; 448 449 mesh_compute_aabb(mesh, lower, upper); 450 if(aabb_is_degenerated(lower, upper)) goto exit; 451 452 /* Compute the overall aabb of the candidate and the clip polygon */ 453 for(i = 0; i < 2; i++) { 454 if(lower[i] > poly_desc->lower[i]) lower[i] = poly_desc->lower[i]; 455 if(upper[i] < poly_desc->upper[i]) upper[i] = poly_desc->upper[i]; 456 } 457 458 /* Create the polygon structure used to triangulate the clipped polygons */ 459 ERR(polygon_create(allocator, &polygon)); 460 461 /* Clip the triangles of the mesh */ 462 SCPR(mesh_get_triangles_count(mesh, &ntris)); 463 FOR_EACH(itri, 0, ntris) { 464 size_t ids[3]; 465 double tri[3][2]; 466 int64_t tri64[3][2]; 467 468 /* Fetch the triangle vertices and compute its AABB */ 469 SCPR(mesh_get_indices(mesh, itri, ids)); 470 SCPR(mesh_get_position(mesh, ids[0], tri[0])); 471 SCPR(mesh_get_position(mesh, ids[1], tri[1])); 472 SCPR(mesh_get_position(mesh, ids[2], tri[2])); 473 SCPR(device_scale(mesh->device, tri[0], 2, tri64[0])); 474 SCPR(device_scale(mesh->device, tri[1], 2, tri64[1])); 475 SCPR(device_scale(mesh->device, tri[2], 2, tri64[2])); 476 triangle_compute_aabb(tri64, lower, upper); 477 478 /* Do not clip triangles that do not intersect the clip AABB */ 479 if(!aabb_intersect(lower, upper, poly_desc->lower, poly_desc->upper)) { 480 if(op != SCPR_AND) { 481 ERR(register_triangle(tri64, &coords, &indices, &vertices)); 482 } 483 continue; 484 } 485 486 /* Setup the candidate path */ 487 cand_path.clear(); 488 tmp.clear(); 489 FOR_EACH(ivert, 0, 3) { 490 Clipper2Lib::Point64 pt; 491 pt.x = tri64[ivert][0]; 492 pt.y = tri64[ivert][1]; 493 tmp.push_back(pt); 494 } 495 cand_path.push_back(tmp); 496 497 /* Clip the polygon */ 498 clipper.Clear(); 499 clipper.AddSubject(cand_path); 500 clipper.AddClip(poly_desc->paths); 501 clipper.Execute(clip_type, Clipper2Lib::FillRule::EvenOdd, output); 502 503 /* Register the resulting clipped polygons */ 504 ERR(register_paths(mesh->device, output, &coords, &indices, &vertices, polygon)); 505 } 506 507 ERR(darray_int64_copy_and_clear(&mesh->coords, &coords)); 508 ERR(darray_uint32_copy_and_clear(&mesh->indices, &indices)); 509 510 exit: 511 if(polygon) POLYGON(ref_put(polygon)); 512 darray_int64_release(&coords); 513 darray_uint32_release(&indices); 514 htable_vertex_release(&vertices); 515 return res; 516 error: 517 goto exit; 518 } 519