scpr_c.h (8513B)
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 #ifndef SCPR_C_H__ 17 #define SCPR_C_H__ 18 19 #include "scpr.h" 20 #include "scpr_clipper.h" 21 22 #include <stddef.h> 23 #include <rsys/rsys.h> 24 #include <rsys/ref_count.h> 25 #include <rsys/double2.h> 26 #include <rsys/dynamic_array.h> 27 #include <rsys/hash_table.h> 28 29 #define DARRAY_NAME uint32 30 #define DARRAY_DATA uint32_t 31 #include <rsys/dynamic_array.h> 32 33 #define DARRAY_NAME int64 34 #define DARRAY_DATA int64_t 35 #include <rsys/dynamic_array.h> 36 37 #define ERR(Expr) { if((res = (Expr)) != RES_OK) goto error; } (void)0 38 39 #define TRY(Expr) \ 40 try { \ 41 (Expr); \ 42 } \ 43 catch(std::bad_alloc &e) { \ 44 res = RES_MEM_ERR; \ 45 goto error; \ 46 } \ 47 catch(...) { \ 48 res = RES_UNKNOWN_ERR; \ 49 goto error; \ 50 } 51 52 struct mem_allocator; 53 54 struct vertex { int64_t pos[2]; }; 55 static FINLINE int 56 vertex_eq(const struct vertex* a, const struct vertex* b) 57 { ASSERT(a && b); return (a->pos[0] == b->pos[0]) && (a->pos[1] == b->pos[1]); } 58 59 /* Define the vertex to index hash table */ 60 #define HTABLE_NAME vertex 61 #define HTABLE_DATA uint32_t 62 #define HTABLE_KEY struct vertex 63 #define HTABLE_KEY_FUNCTOR_EQ vertex_eq 64 #include <rsys/hash_table.h> 65 66 struct scpr_device { 67 int precision; 68 double scale; 69 double inv_scale; 70 double range[2]; 71 72 ref_T ref; 73 struct mem_allocator* allocator; 74 struct logger* logger; 75 }; 76 77 struct scpr_polygon { 78 Clipper2Lib::Paths64 paths; 79 int64_t lower[2], upper[2]; /* Polygon AABB */ 80 81 ref_T ref; 82 struct scpr_device* device; 83 }; 84 85 struct scpr_mesh { 86 struct darray_int64 coords; 87 struct darray_uint32 indices; 88 89 ref_T ref; 90 struct scpr_device* device; 91 }; 92 93 struct intersector_segment { 94 uint32_t component, first_vertex; 95 }; 96 #define DARRAY_NAME segments 97 #define DARRAY_DATA struct intersector_segment 98 #include <rsys/dynamic_array.h> 99 100 /* A segment htable links a count (1 or 2) to a segment index in the segments 101 * darray. 102 * The count is the number of ends of the segment at some range_point. */ 103 #define HTABLE_NAME segment_idx 104 #define HTABLE_KEY uint32_t 105 #define HTABLE_DATA char 106 #include <rsys/hash_table.h> 107 108 /* Each range_point stores the segments that have 1 or 2 ends there */ 109 struct intersector_range_point { 110 struct htable_segment_idx segments; 111 int64_t coord; 112 }; 113 static FINLINE void 114 range_point_init 115 (struct mem_allocator* alloc, struct intersector_range_point* data) 116 { 117 data->coord = INT64_MIN; 118 htable_segment_idx_init(alloc, &data->segments); 119 } 120 static FINLINE void 121 range_point_release(struct intersector_range_point* data) 122 { 123 htable_segment_idx_release(&data->segments); 124 } 125 static FINLINE res_T 126 range_point_copy 127 (struct intersector_range_point* dst, struct intersector_range_point const* src) 128 { 129 dst->coord = src->coord; 130 return htable_segment_idx_copy(&dst->segments, &src->segments); 131 } 132 static FINLINE res_T 133 range_point_copy_and_release 134 (struct intersector_range_point* dst, struct intersector_range_point* src) 135 { 136 dst->coord = src->coord; 137 return htable_segment_idx_copy_and_release(&dst->segments, &src->segments); 138 } 139 /* A darray of range_point. */ 140 #define DARRAY_NAME range_points 141 #define DARRAY_DATA struct intersector_range_point 142 #define DARRAY_FUNCTOR_INIT range_point_init 143 #define DARRAY_FUNCTOR_COPY range_point_copy 144 #define DARRAY_FUNCTOR_RELEASE range_point_release 145 #define DARRAY_FUNCTOR_COPY_AND_RELEASE range_point_copy_and_release 146 #include <rsys/dynamic_array.h> 147 148 /* An htable to link a pointer to a range_point to an 1D coordinate */ 149 #define HTABLE_NAME range_point_idx 150 #define HTABLE_KEY int64_t 151 #define HTABLE_DATA uint32_t 152 #include <rsys/hash_table.h> 153 154 enum segment_interaction { 155 NO_INTERACTION = 0, 156 OVERLAP_X = BIT(0), 157 CONTACT_X = BIT(1), 158 OVERLAP_Y = BIT(2), 159 CONTACT_Y = BIT(3), 160 SOMETHING_X = OVERLAP_X | CONTACT_X, 161 SOMETHING_Y = OVERLAP_Y | CONTACT_Y, 162 SOME_OVERLAP = OVERLAP_X | OVERLAP_Y 163 }; 164 /* A dimension is a structure containing all the points where a segment starts 165 * or ends, each one storing a link to all the segments involved there. */ 166 struct intersector_dimension { 167 /* Unsorted 1D points registered against this dimension */ 168 struct htable_range_point_idx unsorted; 169 /* Same points, but sorted by increasing coordinates along this dimension */ 170 struct darray_range_points sorted; 171 /* Range on this dimension */ 172 int64_t range[2]; 173 /* Flags about segments interaction for this dimension */ 174 enum segment_interaction overlap, contact; 175 }; 176 177 /* An htable to store overlapping information */ 178 struct intersector_segment_pair { 179 uint32_t rank1, rank2; 180 }; 181 static INLINE char 182 pair_eq 183 (struct intersector_segment_pair const* a, 184 struct intersector_segment_pair const* b) 185 { 186 ASSERT(a && b); 187 return a->rank1 == b->rank1 && a->rank2 == b->rank2; 188 } 189 #define HTABLE_NAME interacting_segments 190 #define HTABLE_KEY struct intersector_segment_pair 191 #define HTABLE_DATA unsigned char 192 #define HTABLE_KEY_FUNCTOR_EQ pair_eq 193 #include <rsys/hash_table.h> 194 195 /* An htable to keep track of registered components */ 196 #pragma pack(push, 1) /* Avoid padding */ 197 struct intersector_component { 198 scpr_polygon* polygon; 199 uint32_t component; 200 /* If there is padding, hashing reports uninitialized data in htable code */ 201 }; 202 #pragma pack(pop) 203 static FINLINE void 204 component_init(struct mem_allocator* alloc, struct intersector_component* key) 205 { 206 ASSERT(alloc && key); 207 (void)alloc; 208 key->polygon = NULL; 209 key->component = UINT32_MAX; 210 } 211 static INLINE char 212 component_eq 213 (struct intersector_component const* a, 214 struct intersector_component const* b) 215 { 216 ASSERT(a && b); 217 return a->polygon == b->polygon && a->component == b->component; 218 } 219 static FINLINE void 220 component_release(struct intersector_component* key) 221 { 222 ASSERT(key); 223 if(key->polygon) SCPR(polygon_ref_put(key->polygon)); 224 } 225 static FINLINE res_T 226 component_copy 227 (struct intersector_component* dst, struct intersector_component const* src) 228 { 229 ASSERT(dst && src); 230 dst->polygon = src->polygon; 231 dst->component = src->component; 232 if(dst->polygon) SCPR(polygon_ref_get(dst->polygon)); 233 return RES_OK; 234 } 235 static FINLINE res_T 236 component_copy_and_release 237 (struct intersector_component* dst, struct intersector_component* src) 238 { 239 ASSERT(dst && src); 240 dst->polygon = src->polygon; 241 dst->component = src->component; 242 return RES_OK; 243 } 244 #define HTABLE_NAME registered_components 245 #define HTABLE_KEY struct intersector_component 246 #define HTABLE_DATA char 247 #define HTABLE_KEY_FUNCTOR_INIT component_init 248 #define HTABLE_KEY_FUNCTOR_EQ component_eq 249 #define HTABLE_KEY_FUNCTOR_COPY component_copy 250 #define HTABLE_KEY_FUNCTOR_RELEASE component_release 251 #define HTABLE_KEY_FUNCTOR_COPY_AND_RELEASE component_copy_and_release 252 #include <rsys/hash_table.h> 253 254 #define DARRAY_NAME components 255 #define DARRAY_DATA struct intersector_component 256 #define DARRAY_FUNCTOR_INIT component_init 257 #define DARRAY_FUNCTOR_EQ component_eq 258 #define DARRAY_FUNCTOR_COPY component_copy 259 #define DARRAY_FUNCTOR_RELEASE component_release 260 #define DARRAY_FUNCTOR_COPY_AND_RELEASE component_copy_and_release 261 #include <rsys/dynamic_array.h> 262 263 /* A set of segments from different polygons spatially sorted to help find 264 * (self-)intersections. */ 265 struct scpr_intersector { 266 struct scpr_device* device; 267 /* All the registered segments */ 268 struct darray_segments segments; 269 /* Spatial partition of the segments along the 2 dimensions */ 270 struct intersector_dimension dimensions[2]; 271 /* All the pairs of segment that are in interaction in some way or another. 272 * They are all the candidates for actual intersection plus some others that 273 * are just close, but are without interaction. */ 274 struct htable_interacting_segments interacting_segments; 275 /* All the registererd components (an htable to check for unicity and a darray 276 * to store the components with indexing capability) */ 277 struct htable_registered_components registered_components; 278 struct darray_components components; 279 ref_T ref; 280 }; 281 282 #endif