commit efaad32a88ee0b8c4d239117cc6d871e3abd0507
parent 7e38ca7227aa5f65400773b9c59df11f62924421
Author: Christophe Coustet <christophe.coustet@meso-star.com>
Date: Tue, 28 Feb 2023 12:06:14 +0100
Merge remote-tracking branch 'origin/feature_check_intersections' into develop
Diffstat:
8 files changed, 1438 insertions(+), 41 deletions(-)
diff --git a/cmake/CMakeLists.txt b/cmake/CMakeLists.txt
@@ -29,7 +29,7 @@ set(Clipper2_DIR ${_current_source_dir}/)
find_package(RCMake REQUIRED)
find_package(RSys 0.6 REQUIRED)
-find_package(Clipper2 1.1 REQUIRED)
+find_package(Clipper2 1.2 REQUIRED)
find_package(Polygon 0.0.5 REQUIRED)
include_directories(
@@ -53,6 +53,7 @@ set(VERSION ${VERSION_MAJOR}.${VERSION_MINOR}.${VERSION_PATCH})
set(SCPR_FILES_SRC
scpr_device.c
+ scpr_intersector.c
scpr_mesh.c
scpr_polygon.c)
set(SCPR_FILES_INC_API scpr.h)
@@ -97,6 +98,7 @@ if(NOT NO_TEST)
endfunction()
new_test(test_scpr_clip)
new_test(test_scpr_device)
+ new_test(test_scpr_intersector)
new_test(test_scpr_offset)
new_test(test_scpr_mesh)
new_test(test_scpr_polygon)
diff --git a/src/scpr.h b/src/scpr.h
@@ -60,6 +60,7 @@ struct mem_allocator;
struct scpr_device;
struct scpr_polygon;
struct scpr_mesh;
+struct scpr_intersector;
/* Input arguments of the scpr_device_create function */
struct scpr_device_create_args {
@@ -74,6 +75,32 @@ struct scpr_device_create_args {
static const struct scpr_device_create_args SCPR_DEVICE_CREATE_ARGS_DEFAULT =
SCPR_DEVICE_CREATE_ARGS_DEFAULT__;
+/* A struct to represent segments when calling user callbacks. */
+struct scpr_callback_segment {
+ struct scpr_polygon* polygon;
+ size_t component;
+ size_t first_vertex;
+ size_t last_vertex;
+};
+
+/* A struct holding callbacks that are called when carying an intersection check
+ * on a bunch of segments.
+ * If a callbacks is NULL, the corresponding events are unreported, but at least
+ * 1 callback must be non NULL.
+ * If a callback call returns non-zero, the whole scpr_intersector_check call
+ * exits whith a RES_BAD_ARG error status without further processing. */
+struct scpr_intersector_check_callbacks {
+ int(*simple_intersection)
+ (struct scpr_callback_segment* segment1,
+ struct scpr_callback_segment* segment2,
+ void* ctx);
+ int(*collinear_segments)
+ (struct scpr_callback_segment* segment1,
+ struct scpr_callback_segment* segment2,
+ void* ctx);
+};
+#define SCPR_INTERSECTOR_CHECK_CALLBACKS_NULL__ { NULL, NULL }
+
BEGIN_DECLS
/*******************************************************************************
@@ -211,6 +238,17 @@ scpr_polygon_eq
const struct scpr_polygon* polygon2,
int* is_eq);
+SCPR_API res_T
+scpr_polygon_dump_to_obj
+ (struct scpr_polygon* polygon,
+ FILE* stream);
+
+SCPR_API res_T
+scpr_polygon_dump_component_to_obj
+ (struct scpr_polygon* polygon,
+ const size_t icomponent,
+ FILE* stream);
+
/*******************************************************************************
* Type of meshes, as manipulated by star-cpr.
* Meshes can be made of any number of triangles and are subject to a range
@@ -267,6 +305,41 @@ scpr_mesh_get_position
const size_t ivert,
double position[2]);
+/*******************************************************************************
+ * An intersector provide a way to check for polygon intersections, either
+ * self intersections or intersections between polygons.
+ ******************************************************************************/
+SCPR_API res_T
+scpr_intersector_create
+ (struct scpr_device* dev,
+ struct scpr_intersector** intersector);
+
+SCPR_API res_T
+scpr_intersector_ref_get
+ (struct scpr_intersector* intersector);
+
+SCPR_API res_T
+scpr_intersector_ref_put
+ (struct scpr_intersector* intersector);
+
+/* Register a polygon's a polygon or a component for further analysis */
+SCPR_API res_T
+scpr_intersector_register_polygon
+ (struct scpr_intersector* intersector,
+ struct scpr_polygon* polygon);
+
+SCPR_API res_T
+scpr_intersector_register_component
+ (struct scpr_intersector* intersector,
+ struct scpr_polygon* polygon,
+ const size_t icomponent);
+
+SCPR_API res_T
+scpr_intersector_check
+ (struct scpr_intersector* intersector,
+ struct scpr_intersector_check_callbacks* callbacks,
+ void* data); /* Client data set as the last param of the callbacks */
+
END_DECLS
#endif /* SCPR_H */
diff --git a/src/scpr_c.h b/src/scpr_c.h
@@ -18,11 +18,11 @@
#include "scpr.h"
+#include <cstddef>
#include <rsys/rsys.h>
#include <rsys/ref_count.h>
#include <rsys/double2.h>
#include <rsys/dynamic_array.h>
-#include <rsys/dynamic_array_size_t.h>
#include <rsys/hash_table.h>
#include <math.h>
@@ -30,6 +30,10 @@
#undef PI
#include <clipper2/clipper.h>
+#define DARRAY_NAME uint32
+#define DARRAY_DATA uint32_t
+#include <rsys/dynamic_array.h>
+
#define DARRAY_NAME int64
#define DARRAY_DATA int64_t
#include <rsys/dynamic_array.h>
@@ -58,7 +62,7 @@ vertex_eq(const struct vertex* a, const struct vertex* b)
/* Define the vertex to index hash table */
#define HTABLE_NAME vertex
-#define HTABLE_DATA size_t
+#define HTABLE_DATA uint32_t
#define HTABLE_KEY struct vertex
#define HTABLE_KEY_FUNCTOR_EQ vertex_eq
#include <rsys/hash_table.h>
@@ -84,10 +88,199 @@ struct scpr_polygon {
struct scpr_mesh {
struct darray_int64 coords;
- struct darray_size_t indices;
+ struct darray_uint32 indices;
ref_T ref;
struct scpr_device* device;
};
+struct intersector_segment {
+ uint32_t component, first_vertex;
+};
+#define DARRAY_NAME segments
+#define DARRAY_DATA struct intersector_segment
+#include <rsys/dynamic_array.h>
+
+/* A segment htable links a count (1 or 2) to a segment index in the segments
+ * darray.
+ * The count is the number of ends of the segment at some range_point. */
+#define HTABLE_NAME segment_idx
+#define HTABLE_KEY uint32_t
+#define HTABLE_DATA char
+#include <rsys/hash_table.h>
+
+/* Each range_point stores the segments that have 1 or 2 ends there */
+struct intersector_range_point {
+ struct htable_segment_idx segments;
+ int64_t coord;
+};
+static FINLINE void
+range_point_init
+ (struct mem_allocator* alloc, struct intersector_range_point* data)
+{
+ data->coord = INT64_MIN;
+ htable_segment_idx_init(alloc, &data->segments);
+}
+static FINLINE void
+range_point_release(struct intersector_range_point* data)
+{
+ htable_segment_idx_release(&data->segments);
+}
+static FINLINE res_T
+range_point_copy
+ (struct intersector_range_point* dst, struct intersector_range_point const* src)
+{
+ dst->coord = src->coord;
+ return htable_segment_idx_copy(&dst->segments, &src->segments);
+}
+static FINLINE res_T
+range_point_copy_and_release
+ (struct intersector_range_point* dst, struct intersector_range_point* src)
+{
+ dst->coord = src->coord;
+ return htable_segment_idx_copy_and_release(&dst->segments, &src->segments);
+}
+/* A darray of range_point. */
+#define DARRAY_NAME range_points
+#define DARRAY_DATA struct intersector_range_point
+#define DARRAY_FUNCTOR_INIT range_point_init
+#define DARRAY_FUNCTOR_COPY range_point_copy
+#define DARRAY_FUNCTOR_RELEASE range_point_release
+#define DARRAY_FUNCTOR_COPY_AND_RELEASE range_point_copy_and_release
+#include <rsys/dynamic_array.h>
+
+/* An htable to link a pointer to a range_point to an 1D coordinate */
+#define HTABLE_NAME range_point_idx
+#define HTABLE_KEY int64_t
+#define HTABLE_DATA uint32_t
+#include <rsys/hash_table.h>
+
+enum segment_interaction {
+ NO_INTERACTION = 0,
+ OVERLAP_X = BIT(0),
+ CONTACT_X = BIT(1),
+ OVERLAP_Y = BIT(2),
+ CONTACT_Y = BIT(3),
+ SOMETHING_X = OVERLAP_X | CONTACT_X,
+ SOMETHING_Y = OVERLAP_Y | CONTACT_Y,
+ SOME_OVERLAP = OVERLAP_X | OVERLAP_Y
+};
+/* A dimension is a structure containing all the points where a segment starts
+ * or ends, each one storing a link to all the segments involved there. */
+struct intersector_dimension {
+ /* Unsorted 1D points registered against this dimension */
+ struct htable_range_point_idx unsorted;
+ /* Same points, but sorted by increasing coordinates along this dimension */
+ struct darray_range_points sorted;
+ /* Range on this dimension */
+ int64_t range[2];
+ /* Flags about segments interaction for this dimension */
+ enum segment_interaction overlap, contact;
+};
+
+/* An htable to store overlapping information */
+struct intersector_segment_pair {
+ uint32_t rank1, rank2;
+};
+static INLINE char
+pair_eq
+ (struct intersector_segment_pair const* a,
+ struct intersector_segment_pair const* b)
+{
+ ASSERT(a && b);
+ return a->rank1 == b->rank1 && a->rank2 == b->rank2;
+}
+#define HTABLE_NAME interacting_segments
+#define HTABLE_KEY struct intersector_segment_pair
+#define HTABLE_DATA unsigned char
+#define HTABLE_KEY_FUNCTOR_EQ pair_eq
+#include <rsys/hash_table.h>
+
+/* An htable to keep track of registered components */
+#pragma pack(push, 1) /* Avoid padding */
+struct intersector_component {
+ scpr_polygon* polygon;
+ uint32_t component;
+ /* If there is padding, hashing reports uninitialized data in htable code */
+};
+#pragma pack(pop)
+static FINLINE void
+component_init(struct mem_allocator* alloc, struct intersector_component* key)
+{
+ ASSERT(alloc && key);
+ (void)alloc;
+ key->polygon = NULL;
+ key->component = UINT32_MAX;
+}
+static INLINE char
+component_eq
+ (struct intersector_component const* a,
+ struct intersector_component const* b)
+{
+ ASSERT(a && b);
+ return a->polygon == b->polygon && a->component == b->component;
+}
+static FINLINE void
+component_release(struct intersector_component* key)
+{
+ ASSERT(key);
+ if(key->polygon) SCPR(polygon_ref_put(key->polygon));
+}
+static FINLINE res_T
+component_copy
+ (struct intersector_component* dst, struct intersector_component const* src)
+{
+ ASSERT(dst && src);
+ dst->polygon = src->polygon;
+ dst->component = src->component;
+ if(dst->polygon) SCPR(polygon_ref_get(dst->polygon));
+ return RES_OK;
+}
+static FINLINE res_T
+component_copy_and_release
+ (struct intersector_component* dst, struct intersector_component* src)
+{
+ ASSERT(dst && src);
+ dst->polygon = src->polygon;
+ dst->component = src->component;
+ return RES_OK;
+}
+#define HTABLE_NAME registered_components
+#define HTABLE_KEY struct intersector_component
+#define HTABLE_DATA char
+#define HTABLE_KEY_FUNCTOR_INIT component_init
+#define HTABLE_KEY_FUNCTOR_EQ component_eq
+#define HTABLE_KEY_FUNCTOR_COPY component_copy
+#define HTABLE_KEY_FUNCTOR_RELEASE component_release
+#define HTABLE_KEY_FUNCTOR_COPY_AND_RELEASE component_copy_and_release
+#include <rsys/hash_table.h>
+
+#define DARRAY_NAME components
+#define DARRAY_DATA struct intersector_component
+#define DARRAY_FUNCTOR_INIT component_init
+#define DARRAY_FUNCTOR_EQ component_eq
+#define DARRAY_FUNCTOR_COPY component_copy
+#define DARRAY_FUNCTOR_RELEASE component_release
+#define DARRAY_FUNCTOR_COPY_AND_RELEASE component_copy_and_release
+#include <rsys/dynamic_array.h>
+
+/* A set of segments from different polygons spatially sorted to help find
+ * (self-)intersections. */
+struct scpr_intersector {
+ struct scpr_device* device;
+ /* All the registered segments */
+ struct darray_segments segments;
+ /* Spatial partition of the segments along the 2 dimensions */
+ struct intersector_dimension dimensions[2];
+ /* All the pairs of segment that are in interaction in some way or another.
+ * They are all the candidates for actual intersection plus some others that
+ * are just close, but are without interaction. */
+ struct htable_interacting_segments interacting_segments;
+ /* All the registererd components (an htable to check for unicity and a darray
+ * to store the components with indexing capability) */
+ struct htable_registered_components registererd_components;
+ struct darray_components components;
+ ref_T ref;
+};
+
#endif
diff --git a/src/scpr_intersector.c b/src/scpr_intersector.c
@@ -0,0 +1,802 @@
+/* Copyright (C) 2016-2018, 2021 |Meso|Star> (contact@meso-star.com)
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>. */
+
+#include "scpr.h"
+#include "scpr_c.h"
+
+#include <polygon.h>
+#include <rsys/logger.h>
+#include <rsys/ref_count.h>
+#include <rsys/mem_allocator.h>
+#include <rsys/rsys.h>
+#include <rsys/double2.h>
+#include <rsys/double3.h>
+
+#undef PI
+#include <clipper2/clipper.h>
+
+#include <new>
+#include <stdlib.h>
+#include <math.h>
+
+/*******************************************************************************
+ * Helper functions
+ ******************************************************************************/
+static void
+init_dimension
+ (struct mem_allocator* allocator,
+ struct intersector_dimension* dim,
+ enum segment_interaction overlap,
+ enum segment_interaction share)
+{
+ ASSERT(dim && allocator);
+ htable_range_point_idx_init(allocator, &dim->unsorted);
+ darray_range_points_init(allocator, &dim->sorted);
+ dim->range[0] = INT64_MAX;
+ dim->range[1] = INT64_MIN;
+ dim->overlap= overlap;
+ dim->contact = share;
+}
+
+static void
+release_dimension
+ (struct intersector_dimension* dim)
+{
+ ASSERT(dim);
+ htable_range_point_idx_release(&dim->unsorted);
+ darray_range_points_release(&dim->sorted);
+}
+
+static void
+intersector_release(ref_T* ref)
+{
+ struct scpr_intersector* intersector;
+ struct mem_allocator* allocator;
+ ASSERT(ref);
+ intersector = CONTAINER_OF(ref, struct scpr_intersector, ref);
+ allocator = intersector->device->allocator;
+ darray_segments_release(&intersector->segments);
+ release_dimension(intersector->dimensions);
+ release_dimension(intersector->dimensions + 1);
+ SCPR(device_ref_put(intersector->device));
+ htable_interacting_segments_release(&intersector->interacting_segments);
+ htable_registered_components_release(&intersector->registererd_components);
+ darray_components_release(&intersector->components);
+ MEM_RM(allocator, intersector);
+}
+
+/* Register a point (a segment end) against a dimension */
+static res_T
+register_point
+ (struct scpr_intersector* intersector,
+ const int dim_idx,
+ const int64_t coord,
+ const uint32_t seg_idx)
+{
+ uint32_t* pidx;
+ uint32_t rp_idx;
+ struct intersector_dimension* dim;
+ struct intersector_range_point* sorted;
+ res_T res = RES_OK;
+ ASSERT(intersector);
+
+ dim = intersector->dimensions + dim_idx;
+ pidx = htable_range_point_idx_find(&dim->unsorted, &coord);
+ if(!pidx) {
+ /* First time this point: create it in sorted and store its index in unsorted */
+ char one = 1;
+ size_t count = darray_range_points_size_get(&dim->sorted);
+ ERR(darray_range_points_resize(&dim->sorted, 1+count));
+ sorted = darray_range_points_data_get(&dim->sorted);
+ rp_idx = (uint32_t)count;
+ sorted[rp_idx].coord = coord;
+ /* Register this segment at this range point */
+ ERR(htable_segment_idx_set(&sorted[rp_idx].segments, &seg_idx, &one));
+ /* Update range */
+ if(dim->range[0] > coord) dim->range[0] = coord;
+ if(dim->range[1] < coord) dim->range[1] = coord;
+ } else {
+ /* This point is already known: look for seg_idx already there */
+ char *found, one_or_two;
+ rp_idx = *pidx;
+ sorted = darray_range_points_data_get(&dim->sorted);
+ found = htable_segment_idx_find(&sorted[rp_idx].segments, &seg_idx);
+ one_or_two = found ? 2 : 1;
+ ERR(htable_segment_idx_set(&sorted[rp_idx].segments, &seg_idx, &one_or_two));
+ }
+ ERR(htable_range_point_idx_set(&dim->unsorted, &coord, &rp_idx));
+
+exit:
+ return res;
+error:
+ goto exit;
+}
+
+/* Compare 2 range_points */
+static int
+compare_range_points(const void* a, const void* b)
+{
+ struct intersector_range_point *pa = (struct intersector_range_point*)a;
+ struct intersector_range_point *pb = (struct intersector_range_point*)b;
+ ASSERT(a && b && pa->coord != pb->coord);
+ return (int)(pa->coord - pb->coord);
+}
+
+/* Sort the range points by increasing coordinates */
+static void
+sort_points
+ (struct intersector_dimension* dim)
+{
+ size_t count;
+ struct intersector_range_point* sorted;
+ ASSERT(dim);
+
+ /* All the range points are already in sorted; just need to sort them */
+ count = darray_range_points_size_get(&dim->sorted);
+ ASSERT(count == htable_range_point_idx_size_get(&dim->unsorted));
+ sorted = darray_range_points_data_get(&dim->sorted);
+ qsort(sorted, count, sizeof(*sorted), compare_range_points);
+}
+
+/* Create a segment pair suitable for use as an htable key
+ * To ensure unicity, pairs are ordered */
+static void
+init_segment_pair
+ (struct intersector_segment_pair* pair,
+ const uint32_t seg_idx1,
+ const uint32_t seg_idx2)
+{
+ ASSERT(pair);
+ pair->rank1 = seg_idx1;
+ pair->rank2 = seg_idx2;
+ if(pair->rank1 > pair->rank2) {
+ SWAP(uint32_t, pair->rank1, pair->rank2);
+ }
+}
+
+#ifndef NDEBUG
+static int
+segments_bbox_interacts_1_core
+ (int64_t lower1, int64_t upper1, int64_t lower2, int64_t upper2)
+{
+ if(lower1 > upper2) return 0;
+ if(lower2 > upper1) return 0;
+ return 1;
+}
+
+/* Check if 2 polygon Bbox interact */
+static int
+segments_bbox_interacts
+ (Clipper2Lib::Point64 *v11,
+ Clipper2Lib::Point64 *v12,
+ Clipper2Lib::Point64 *v21,
+ Clipper2Lib::Point64 *v22)
+{
+ int64_t lower1[2], upper1[2], lower2[2], upper2[2];
+ ASSERT(v11 && v12 && v21 && v22);
+ lower1[0] = MMIN(v11->x, v12->x);
+ lower1[1] = MMIN(v11->y, v12->y);
+ lower2[0] = MMIN(v21->x, v22->x);
+ lower2[1] = MMIN(v21->y, v22->y);
+ upper1[0] = MMAX(v11->x, v12->x);
+ upper1[1] = MMAX(v11->y, v12->y);
+ upper2[0] = MMAX(v21->x, v22->x);
+ upper2[1] = MMAX(v21->y, v22->y);
+ if(!segments_bbox_interacts_1_core(lower1[0], upper1[0], lower2[0], upper2[0]))
+ return 0;
+ return segments_bbox_interacts_1_core(lower1[1], upper1[1], lower2[1], upper2[1]);
+}
+
+static int
+segments_bbox_interacts_1
+ (uint32_t seg_idx1,
+ uint32_t seg_idx2,
+ enum segment_interaction inter,
+ struct scpr_intersector* intersector)
+{
+ const struct intersector_segment *segments, *seg1, *seg2;
+ Clipper2Lib::Point64 *v11, * v12, *v21, *v22;
+ int64_t lower1, upper1, lower2, upper2;
+ size_t count, r11, r12, r21, r22;
+ const struct intersector_component* components;
+ struct scpr_polygon *polygon1, *polygon2;
+ uint32_t comp_idx1, comp_idx2;
+
+ segments = darray_segments_cdata_get(&intersector->segments);
+ seg1 = segments + seg_idx1;
+ seg2 = segments + seg_idx2;
+ components = darray_components_cdata_get(&intersector->components);
+ comp_idx1 = components[seg1->component].component;
+ comp_idx2 = components[seg2->component].component;
+ polygon1 = components[seg1->component].polygon;
+ polygon2 = components[seg2->component].polygon;
+
+ /* Get vertices */
+ r11 = seg1->first_vertex;
+ SCPR(polygon_get_vertices_count(polygon1, comp_idx1, &count));
+ r12 = (r11 + 1) % count;
+ r21 = seg2->first_vertex;
+ SCPR(polygon_get_vertices_count(polygon2, comp_idx2, &count));
+ r22 = (r21 + 1) % count;
+ v11 = &polygon1->paths[comp_idx1][r11];
+ v12 = &polygon1->paths[comp_idx1][r12];
+ v21 = &polygon2->paths[comp_idx2][r21];
+ v22 = &polygon2->paths[comp_idx2][r22];
+ if(inter & SOMETHING_X) {
+ lower1 = MMIN(v11->x, v12->x);
+ upper1 = MMAX(v11->x, v12->x);
+ lower2 = MMIN(v21->x, v22->x);
+ upper2 = MMAX(v21->x, v22->x);
+ } else {
+ lower1 = MMIN(v11->y, v12->y);
+ upper1 = MMAX(v11->y, v12->y);
+ lower2 = MMIN(v21->y, v22->y);
+ upper2 = MMAX(v21->y, v22->y);
+ }
+ return segments_bbox_interacts_1_core(lower1, upper1, lower2, upper2);
+}
+#endif
+
+/* Register interaction of 2 segments along 1 dimension */
+static res_T
+register_segment_interaction
+ (const uint32_t seg_idx1,
+ const uint32_t seg_idx2,
+ const int allow_pair_creation,
+ const enum segment_interaction inter,
+ struct scpr_intersector* intersector)
+{
+ res_T res = RES_OK;
+ struct intersector_segment_pair pair;
+ unsigned char *pinteract;
+
+ ASSERT(intersector);
+ if(seg_idx1 != seg_idx2) {
+ ASSERT(segments_bbox_interacts_1(seg_idx1, seg_idx2, inter, intersector));
+
+ /* Fill a record for this pair of segments */
+ init_segment_pair(&pair, seg_idx1, seg_idx2);
+ pinteract =
+ htable_interacting_segments_find(&intersector->interacting_segments, &pair);
+ if(pinteract || allow_pair_creation) {
+ unsigned char interact;
+ if(!pinteract) { /* First occurence of this pair: create empty record */
+ interact = (unsigned char)inter;
+ } else {
+ ASSERT((*pinteract | inter) < UCHAR_MAX);
+ interact = (unsigned char)(*pinteract | inter);
+ }
+
+ /* Register this interaction */
+ ERR(htable_interacting_segments_set(&intersector->interacting_segments,
+ &pair, &interact));
+ }
+ }
+
+exit:
+ return res;
+error:
+ goto exit;
+}
+
+/* Register interaction of segment of seg_idx with all the segments in
+ * open_segments along 1 dimension */
+static res_T
+register_segment_interactions
+ (const uint32_t seg_idx,
+ struct htable_segment_idx* open_segments,
+ const int allow_pair_creation,
+ const enum segment_interaction inter,
+ struct scpr_intersector* intersector)
+{
+ res_T res = RES_OK;
+ struct htable_segment_idx_iterator it, end;
+
+ ASSERT(open_segments && intersector);
+
+ htable_segment_idx_begin(open_segments, &it);
+ htable_segment_idx_end(open_segments, &end);
+ /* Loop on segments using this point */
+ while(!htable_segment_idx_iterator_eq(&it, &end)) {
+ uint32_t seg2_idx = *htable_segment_idx_iterator_key_get(&it);
+ ERR(register_segment_interaction(seg_idx, seg2_idx, allow_pair_creation,
+ inter, intersector));
+ htable_segment_idx_iterator_next(&it);
+ }
+
+exit:
+ return res;
+error:
+ goto exit;
+}
+
+/* Register segments interaction along 1 dimension */
+static res_T
+register_interaction
+ (const int dim_idx,
+ struct scpr_intersector* intersector)
+{
+ res_T res = RES_OK;
+ size_t count, i;
+ struct intersector_range_point* points;
+ struct htable_segment_idx open_segments;
+ struct mem_allocator* allocator;
+ struct intersector_dimension* dimension;
+ char *begins = NULL, *ends = NULL;
+ uint32_t* seg_index = NULL;
+ ASSERT(intersector);
+
+ allocator = intersector->device->allocator;
+ dimension = intersector->dimensions + dim_idx;
+ htable_segment_idx_init(allocator, &open_segments);
+ count = darray_range_points_size_get(&dimension->sorted);
+ points = darray_range_points_data_get(&dimension->sorted);
+ for(i = 0; i < count; i++) {
+ struct intersector_range_point* point = points + i;
+ struct htable_segment_idx_iterator it, end;
+ size_t scount, s;
+
+ /* 0) Init begins, ends and seg_index
+ * Cannot recompute them on the fly as found will change */
+ scount = htable_segment_idx_size_get(&point->segments);
+ begins = (char*)MEM_REALLOC(allocator, begins, scount * sizeof(*begins));
+ ends = (char*)MEM_REALLOC(allocator, ends, scount * sizeof(*ends));
+ seg_index = (uint32_t*)MEM_REALLOC(allocator, seg_index,
+ scount * sizeof(*seg_index));
+ if(!begins || !ends || !seg_index) {
+ res = RES_MEM_ERR;
+ goto error;
+ }
+ s = 0;
+ htable_segment_idx_begin(&point->segments, &it);
+ htable_segment_idx_end(&point->segments, &end);
+ while(!htable_segment_idx_iterator_eq(&it, &end)) {
+ char c = *htable_segment_idx_iterator_data_get(&it);
+ uint32_t seg_idx = *htable_segment_idx_iterator_key_get(&it);
+ if(c == 2) { /* Both ends of the segment at this point */
+ ends[s] = begins[s] = 1;
+ } else {
+ char* found = htable_segment_idx_find(&open_segments, &seg_idx);
+ begins[s] = (found == NULL);
+ ends[s] = (found != NULL);
+ }
+ seg_index[s] = seg_idx;
+ s++;
+ htable_segment_idx_iterator_next(&it);
+ }
+ ASSERT(s == scount);
+
+ /* 1) Segments beginning and ending at this point overlap other segments that
+ * begin and end at the same point and contact segments that only begin or
+ * only end at this point */
+ for(s = 0; s < scount; s++) {
+ if(begins[s] && ends[s]) {
+ size_t j;
+ for(j = 0; j < scount; j++) {
+ if(j > s && begins[j] && ends[j]) {
+ ERR(register_segment_interaction(seg_index[s], seg_index[j], !dim_idx,
+ dimension->overlap, intersector));
+ }
+ else if(begins[j] ^ ends[j]) {
+ ERR(register_segment_interaction(seg_index[s], seg_index[j], !dim_idx,
+ dimension->contact, intersector));
+ }
+ }
+ }
+ }
+
+ /* 2) Segments only ending at this point overlap open segments */
+ for(s = 0; s < scount; s++) {
+ if(!begins[s] && ends[s]) {
+ ERR(register_segment_interactions(seg_index[s], &open_segments, !dim_idx,
+ dimension->overlap, intersector));
+ }
+ }
+
+ /* 3) Segments ending at this point are now closed */
+ for(s = 0; s < scount; s++) {
+ if(ends[s]) {
+ size_t n = htable_segment_idx_erase(&open_segments, seg_index + s);
+ CHK(n == (begins[s] ? 0 : 1));
+ }
+ }
+
+ /* 4) Segments beginning and ending at this point overlap open segments */
+ for(s = 0; s < scount; s++) {
+ if(begins[s] && ends[s]) {
+ ERR(register_segment_interactions(seg_index[s], &open_segments, !dim_idx,
+ dimension->overlap, intersector));
+ }
+ }
+
+ /* 5) Segments only beginning at this point are now open */
+ for(s = 0; s < scount; s++) {
+ if(begins[s] && !ends[s]) {
+ char one = 1;
+ ERR(htable_segment_idx_set(&open_segments, seg_index + s, &one));
+ }
+ }
+
+ /* 6) Segments only beginning at this point overlap open segments */
+ for(s = 0; s < scount; s++) {
+ if(begins[s] && !ends[s]) {
+ ERR(register_segment_interactions(seg_index[s], &open_segments, !dim_idx,
+ dimension->overlap, intersector));
+ }
+ }
+ }
+
+exit:
+ MEM_RM(allocator, begins);
+ MEM_RM(allocator, ends);
+ MEM_RM(allocator, seg_index);
+ htable_segment_idx_release(&open_segments);
+ return res;
+error:
+ goto exit;
+}
+
+static int64_t
+safe_mul
+ (int64_t a,
+ int64_t b,
+ int* ovflw)
+{
+ if(*ovflw) return 0;
+ if(b != 0 && abs(a) > 1 + (INT64_MAX / abs(b))) goto error;
+ return a * b;
+error:
+ *ovflw = 1;
+ return 0;
+}
+
+/* Check if a triangle is CCW (>0), CW (<0), or flat (=0) */
+static int
+is_ccw
+ (Clipper2Lib::Point64* v1,
+ Clipper2Lib::Point64* v2,
+ Clipper2Lib::Point64* v3,
+ int* ovflw)
+{
+ int64_t tmp1, tmp2;
+ ASSERT(v1 && v2 && v3);
+ /* Limited coordinate range garanties that sub computations stay in int64_t
+ * range */
+ tmp1 = safe_mul(v2->x - v1->x, v3->y - v1->y, ovflw);
+ tmp2 = safe_mul(v3->x - v1->x, v2->y - v1->y, ovflw);
+ if(tmp1 < tmp2) return -1;
+ if(tmp1 > tmp2) return +1;
+ return 0;
+}
+
+/* Check if 2 segments intersect */
+static res_T
+check_two_segments_intersection
+ (const struct intersector_segment* seg1,
+ const struct intersector_segment* seg2,
+ struct scpr_intersector_check_callbacks* callbacks,
+ struct scpr_intersector* intersector,
+ void* data)
+{
+ res_T res = RES_OK;
+ size_t count, r11, r12, r21, r22;
+ Clipper2Lib::Point64 *v11, * v12, *v21, *v22;
+ int ccw1, ccw2, ccw3, ccw4, ovflw = 0;
+ const struct intersector_component* components;
+ struct scpr_polygon *polygon1, *polygon2;
+ uint32_t comp_idx1, comp_idx2;
+
+ ASSERT(seg1 && seg2 && callbacks);
+
+ components = darray_components_cdata_get(&intersector->components);
+ comp_idx1 = components[seg1->component].component;
+ comp_idx2 = components[seg2->component].component;
+ polygon1 = components[seg1->component].polygon;
+ polygon2 = components[seg2->component].polygon;
+
+ /* Get vertices */
+ r11 = seg1->first_vertex;
+ ERR(scpr_polygon_get_vertices_count(polygon1, comp_idx1, &count));
+ r12 = (r11 + 1) % count;
+ r21 = seg2->first_vertex;
+ ERR(scpr_polygon_get_vertices_count(polygon2, comp_idx2, &count));
+ r22 = (r21 + 1) % count;
+ v11 = &polygon1->paths[comp_idx1][r11];
+ v12 = &polygon1->paths[comp_idx1][r12];
+ v21 = &polygon2->paths[comp_idx2][r21];
+ v22 = &polygon2->paths[comp_idx2][r22];
+ ASSERT(segments_bbox_interacts(v11, v12, v21, v22));
+
+ /* Test triangles orientation */
+ ccw1 = is_ccw(v11, v12, v21, &ovflw);
+ ccw2 = is_ccw(v11, v12, v22, &ovflw);
+ ccw3 = is_ccw(v21, v22, v11, &ovflw);
+ ccw4 = is_ccw(v21, v22, v12, &ovflw);
+ if(ovflw) {
+ res = RES_BAD_ARG;
+ goto error;
+ }
+ /* Analyse ccw results */
+ if(ccw1 * ccw2 > 0 && ccw3 * ccw4 > 0) {
+ /* No intersection at all */
+ }
+ else if(ccw1 == 0 && ccw2 == 0 && ccw3 == 0 && ccw4 == 0) {
+ /* collinear segments */
+ struct scpr_callback_segment arg1, arg2;
+ arg1.polygon = polygon1;
+ arg1.component = comp_idx1;
+ arg1.first_vertex = r11;
+ arg1.last_vertex = r12;
+ arg2.polygon = polygon2;
+ arg2.component = comp_idx2;
+ arg2.first_vertex = r21;
+ arg2.last_vertex = r22;
+ if(callbacks->collinear_segments
+ && callbacks->collinear_segments(&arg1, &arg2, data))
+ {
+ res = RES_BAD_ARG;
+ goto error;
+ }
+ }
+ else if(ccw1 * ccw2 < 0 && ccw3 * ccw4 < 0) {
+ /* Basic segment intersection */
+ struct scpr_callback_segment arg1, arg2;
+ arg1.polygon = polygon1;
+ arg1.component = comp_idx1;
+ arg1.first_vertex = r11;
+ arg1.last_vertex = r12;
+ arg2.polygon = polygon2;
+ arg2.component = comp_idx2;
+ arg2.first_vertex = r21;
+ arg2.last_vertex = r22;
+ if(callbacks->simple_intersection
+ && callbacks->simple_intersection(&arg1, &arg2, data))
+ {
+ res = RES_BAD_ARG;
+ goto error;
+ }
+}
+
+exit:
+ return res;
+error:
+ goto exit;
+}
+
+/* Test intersection of all the registered pairs of interacting segments */
+static res_T
+check_interacting_pairs
+ (struct scpr_intersector* intersector,
+ struct scpr_intersector_check_callbacks* callbacks,
+ void* data)
+{
+ res_T res = RES_OK;
+ struct htable_interacting_segments_iterator it, end;
+ const struct intersector_segment* segments;
+
+ ASSERT(intersector && callbacks);
+
+ segments = darray_segments_cdata_get(&intersector->segments);
+ htable_interacting_segments_begin(&intersector->interacting_segments, &it);
+ htable_interacting_segments_end(&intersector->interacting_segments, &end);
+ /* Loop on interacting segments */
+ while(!htable_interacting_segments_iterator_eq(&it, &end)) {
+ unsigned char overlapping
+ = *htable_interacting_segments_iterator_data_get(&it);
+ if(overlapping & SOME_OVERLAP
+ && overlapping & SOMETHING_X && overlapping & SOMETHING_Y)
+ {
+ struct intersector_segment_pair* pair
+ = htable_interacting_segments_iterator_key_get(&it);
+ const struct intersector_segment* seg1 = segments + pair->rank1;
+ const struct intersector_segment* seg2 = segments + pair->rank2;
+ ERR(check_two_segments_intersection(seg1, seg2, callbacks, intersector, data));
+ }
+ htable_interacting_segments_iterator_next(&it);
+ }
+
+exit:
+ return res;
+error:
+ goto exit;
+}
+
+/*******************************************************************************
+ * Exported functions
+ ******************************************************************************/
+res_T
+scpr_intersector_create
+ (struct scpr_device* device,
+ struct scpr_intersector** out_intersector)
+{
+ res_T res = RES_OK;
+ struct scpr_intersector* intersector = NULL;
+ struct mem_allocator* allocator;
+
+ if(!device || ! out_intersector) {
+ res = RES_BAD_ARG;
+ goto error;
+ }
+
+ allocator = device->allocator;
+ intersector = (struct scpr_intersector*)MEM_ALLOC(allocator, sizeof(*intersector));
+ if(!intersector) {
+ res = RES_MEM_ERR;
+ goto error;
+ }
+ ref_init(&intersector->ref);
+ intersector->device = device;
+ ERR(scpr_device_ref_get(device));
+ darray_segments_init(allocator, &intersector->segments);
+ init_dimension(allocator, intersector->dimensions, OVERLAP_X, CONTACT_X);
+ init_dimension(allocator, intersector->dimensions + 1, OVERLAP_Y, CONTACT_Y);
+ htable_interacting_segments_init(allocator, &intersector->interacting_segments);
+ htable_registered_components_init(allocator, &intersector->registererd_components);
+ darray_components_init(allocator, &intersector->components);
+
+exit:
+ if(out_intersector) *out_intersector = intersector;
+ return res;
+error:
+ if(intersector) {
+ SCPR(intersector_ref_put(intersector));
+ intersector = NULL;
+ }
+ goto exit;
+}
+
+res_T
+scpr_intersector_ref_get
+ (struct scpr_intersector* intersector)
+{
+ if(!intersector) return RES_BAD_ARG;
+ ref_get(&intersector->ref);
+ return RES_OK;
+}
+
+res_T
+scpr_intersector_ref_put
+ (struct scpr_intersector* intersector)
+{
+ if(!intersector) return RES_BAD_ARG;
+ ref_put(&intersector->ref, intersector_release);
+ return RES_OK;
+}
+
+res_T
+scpr_intersector_register_polygon
+ (struct scpr_intersector* intersector,
+ struct scpr_polygon* polygon)
+{
+ res_T res = RES_OK;
+ size_t i;
+
+ if(!intersector || !polygon) {
+ res = RES_BAD_ARG;
+ goto error;
+ }
+
+ for(i = 0; i < polygon->paths.size(); i++) {
+ ERR(scpr_intersector_register_component(intersector, polygon, i));
+ }
+
+exit:
+ return res;
+error:
+ goto exit;
+}
+
+res_T
+scpr_intersector_register_component
+ (struct scpr_intersector* intersector,
+ struct scpr_polygon* polygon,
+ const size_t icomponent)
+{
+ res_T res = RES_OK;
+ uint32_t i;
+ size_t new_count, prev_count, c;
+ struct intersector_component comp;
+ char *found, one = 1;
+
+ if(!intersector || !polygon || icomponent >= polygon->paths.size()) {
+ res = RES_BAD_ARG;
+ goto error;
+ }
+
+ /* Check single registration */
+ comp.polygon = polygon;
+ comp.component = (uint32_t)icomponent;
+ found = htable_registered_components_find(&intersector->registererd_components,
+ &comp);
+ if(found) {
+ logger_print(intersector->device->logger, LOG_ERROR,
+ "Component %zu already registered.\n", icomponent);
+ res = RES_BAD_ARG;
+ goto error;
+ }
+ c = htable_registered_components_size_get(&intersector->registererd_components);
+ if(c >= UINT32_MAX) {
+ logger_print(intersector->device->logger, LOG_ERROR,
+ "Too many components registered.\n");
+ res = RES_BAD_ARG;
+ goto error;
+ }
+ ASSERT(c == darray_components_size_get(&intersector->components));
+ ERR(htable_registered_components_set(&intersector->registererd_components,
+ &comp, &one));
+ ERR(darray_components_push_back(&intersector->components, &comp));
+
+ prev_count = darray_segments_size_get(&intersector->segments);
+ ASSERT(prev_count <= UINT32_MAX);
+ new_count = polygon->paths[icomponent].size();
+ if(prev_count + new_count > UINT32_MAX) {
+ logger_print(intersector->device->logger, LOG_ERROR,
+ "Too many segments registered.\n");
+ res = RES_BAD_ARG;
+ goto error;
+ }
+ ERR(darray_segments_resize(&intersector->segments,
+ (uint32_t)(prev_count + new_count)));
+
+ for(i = 0; i < new_count; i++) {
+ Clipper2Lib::Point64 *p0, *p1;
+ uint32_t seg_idx = (uint32_t)(prev_count + i);
+ struct intersector_segment* segment
+ = darray_segments_data_get(&intersector->segments) + seg_idx;
+ segment->component = (uint32_t)c;
+ segment->first_vertex = i;
+ p0 = &polygon->paths[icomponent][i];
+ p1 = &polygon->paths[icomponent][(i+1)%new_count];
+ ERR(register_point(intersector, 0, p0->x, seg_idx));
+ ERR(register_point(intersector, 0, p1->x, seg_idx));
+ ERR(register_point(intersector, 1, p0->y, seg_idx));
+ ERR(register_point(intersector, 1, p1->y, seg_idx));
+ }
+
+exit:
+ return res;
+error:
+ goto exit;
+}
+
+res_T
+scpr_intersector_check
+ (struct scpr_intersector* intersector,
+ struct scpr_intersector_check_callbacks* callbacks,
+ void* data)
+{
+ int i;
+ res_T res = RES_OK;
+
+ if(!intersector || !callbacks
+ || (!callbacks->simple_intersection && !callbacks->collinear_segments))
+ {
+ res = RES_BAD_ARG;
+ goto error;
+ }
+
+ /* Construct candidates for intersection */
+ for(i = 0; i < 2; i++) {
+ sort_points(&intersector->dimensions[i]);
+ ERR(register_interaction(i, intersector));
+ }
+ /* Check intersections */
+ ERR(check_interacting_pairs(intersector, callbacks, data));
+
+exit:
+ return res;
+error:
+ goto exit;
+}
diff --git a/src/scpr_mesh.c b/src/scpr_mesh.c
@@ -17,6 +17,7 @@
#include "scpr_c.h"
#include <rsys/mem_allocator.h>
+#include <rsys/logger.h>
#include <polygon.h>
#undef PI
@@ -68,7 +69,7 @@ triangle_compute_aabb
ASSERT(tri && lower && upper);
lower[0] = lower[1] = INT64_MAX;
- upper[0] = upper[1] = -INT64_MAX;
+ upper[0] = upper[1] = INT64_MIN;
FOR_EACH(ivert, 0, 3) {
int i;
for(i = 0; i < 2; i++) {
@@ -82,11 +83,11 @@ static res_T
register_vertex
(const int64_t pos[2],
struct darray_int64* coords,
- struct darray_size_t* indices,
+ struct darray_uint32* indices,
struct htable_vertex* vertices)
{
struct vertex v;
- size_t* pid, id;
+ uint32_t* pid, id;
unsigned i;
res_T res = RES_OK;
ASSERT(pos && coords && indices && vertices);
@@ -103,14 +104,15 @@ register_vertex
} else {
const size_t count = darray_int64_size_get(coords);
+ ASSERT(count <= UINT32_MAX);
ERR(darray_int64_resize(coords, count+2/*#coords*/));
for(i = 0; i < 2; i++) darray_int64_data_get(coords)[count+i] = pos[i];
- id = count / 2;
+ id = (uint32_t)count / 2;
ERR(htable_vertex_set(vertices, &v, &id));
}
- ERR(darray_size_t_push_back(indices, &id));
+ ERR(darray_uint32_push_back(indices, &id));
exit:
return res;
@@ -122,7 +124,7 @@ static FINLINE res_T
register_triangle
(int64_t tri[3][2],
struct darray_int64* coords, /* Vertex buffer */
- struct darray_size_t* indices, /* Index buffer */
+ struct darray_uint32* indices, /* Index buffer */
struct htable_vertex* vertices) /* Map a vertex to its index */
{
size_t ivert;
@@ -143,7 +145,7 @@ register_paths
(struct scpr_device* dev,
const Clipper2Lib::Paths64& paths,
struct darray_int64* coords, /* Vertex buffer */
- struct darray_size_t* indices, /* Index buffer */
+ struct darray_uint32* indices, /* Index buffer */
struct htable_vertex* vertices, /* Map a vertex to its index */
struct polygon* polygon) /* Used to triangulate the clipped polygons */
{
@@ -209,7 +211,7 @@ mesh_compute_aabb
SCPR(mesh_get_triangles_count(mesh, &ntris));
lower[0] = lower[1] = INT64_MAX;
- upper[0] = upper[1] = -INT64_MAX;
+ upper[0] = upper[1] = INT64_MIN;
FOR_EACH(itri, 0, ntris) {
size_t ids[3], ivert;
@@ -237,7 +239,7 @@ mesh_release(ref_T* ref)
allocator = mesh->device->allocator;
SCPR(device_ref_put(mesh->device));
darray_int64_release(&mesh->coords);
- darray_size_t_release(&mesh->indices);
+ darray_uint32_release(&mesh->indices);
MEM_RM(allocator, mesh);
}
@@ -267,7 +269,7 @@ scpr_mesh_create
mesh->device = dev;
SCPR(device_ref_get(dev));
darray_int64_init(dev->allocator, &mesh->coords);
- darray_size_t_init(dev->allocator, &mesh->indices);
+ darray_uint32_init(dev->allocator, &mesh->indices);
exit:
if(out_mesh) *out_mesh = mesh;
@@ -307,8 +309,8 @@ scpr_mesh_setup_indexed_vertices
void* data)
{
int64_t* pos = NULL;
- size_t* ids = NULL;
- size_t i;
+ uint32_t* ids = NULL;
+ size_t i, j;
res_T res = RES_OK;
if(!mesh || !ntris || !get_indices || !nverts || !get_position || !data) {
@@ -316,8 +318,22 @@ scpr_mesh_setup_indexed_vertices
goto error;
}
+ if(ntris > UINT32_MAX) {
+ logger_print(mesh->device->logger, LOG_ERROR,
+ "Too many triangles.\n");
+ res = RES_BAD_ARG;
+ goto error;
+ }
+
+ if(nverts > UINT32_MAX) {
+ logger_print(mesh->device->logger, LOG_ERROR,
+ "Too many vertices.\n");
+ res = RES_BAD_ARG;
+ goto error;
+ }
+
ERR(darray_int64_resize(&mesh->coords, nverts*2/*#coords per vertex*/));
- ERR(darray_size_t_resize(&mesh->indices, ntris*3/*#vertices per triangle*/));
+ ERR(darray_uint32_resize(&mesh->indices, ntris*3/*#vertices per triangle*/));
/* Fetch mesh positions */
pos = darray_int64_data_get(&mesh->coords);
@@ -328,15 +344,15 @@ scpr_mesh_setup_indexed_vertices
}
/* Fetch mesh indices */
- ids = darray_size_t_data_get(&mesh->indices);
+ ids = darray_uint32_data_get(&mesh->indices);
FOR_EACH(i, 0, ntris) {
- get_indices(i, ids + i*3, data);
- if(ids[i*3+0] >= nverts
- || ids[i*3+1] >= nverts
- || ids[i*3+2] >= nverts) {
+ size_t tmp[3];
+ get_indices(i, tmp, data);
+ if(tmp[0] >= nverts || tmp[1] >= nverts || tmp[2] >= nverts) {
res = RES_BAD_ARG;
goto error;
}
+ for(j = 0; j < 3; j++) ids[i*3 + j] = (uint32_t)tmp[j];
}
exit:
@@ -344,7 +360,7 @@ exit:
error:
if(mesh) {
darray_int64_clear(&mesh->coords);
- darray_size_t_clear(&mesh->indices);
+ darray_uint32_clear(&mesh->indices);
}
goto exit;
}
@@ -362,8 +378,8 @@ res_T
scpr_mesh_get_triangles_count(const struct scpr_mesh* mesh, size_t* ntris)
{
if(!mesh || !ntris) return RES_BAD_ARG;
- ASSERT((darray_size_t_size_get(&mesh->indices)%3/*#vertices per triangle*/)==0);
- *ntris = darray_size_t_size_get(&mesh->indices) / 3/*#vertices per triangle*/;
+ ASSERT((darray_uint32_size_get(&mesh->indices)%3/*#vertices per triangle*/)==0);
+ *ntris = darray_uint32_size_get(&mesh->indices) / 3/*#vertices per triangle*/;
return RES_OK;
}
@@ -376,9 +392,9 @@ scpr_mesh_get_indices
if(!mesh || !ids) return RES_BAD_ARG;
SCPR(mesh_get_triangles_count(mesh, &ntris));
if(itri >= ntris) return RES_BAD_ARG;
- ids[0] = darray_size_t_cdata_get(&mesh->indices)[i+0];
- ids[1] = darray_size_t_cdata_get(&mesh->indices)[i+1];
- ids[2] = darray_size_t_cdata_get(&mesh->indices)[i+2];
+ ids[0] = darray_uint32_cdata_get(&mesh->indices)[i+0];
+ ids[1] = darray_uint32_cdata_get(&mesh->indices)[i+1];
+ ids[2] = darray_uint32_cdata_get(&mesh->indices)[i+2];
return RES_OK;
}
@@ -407,7 +423,7 @@ scpr_mesh_clip
int64_t lower[2], upper[2];
struct polygon* polygon = NULL; /* Use to triangulate clipped polygons */
struct darray_int64 coords; /* Coordinates of the clipped mesh */
- struct darray_size_t indices; /* Indices of the clipped mesh */
+ struct darray_uint32 indices; /* Indices of the clipped mesh */
struct htable_vertex vertices; /* Map a coordinate to its index */
Clipper2Lib::Clipper64 clipper;
Clipper2Lib::Paths64 output; /* Contour of the clipped polgyon */
@@ -427,7 +443,7 @@ scpr_mesh_clip
clip_type = scpr_operation_to_clip_type(op);
darray_int64_init(allocator, &coords);
- darray_size_t_init(allocator, &indices);
+ darray_uint32_init(allocator, &indices);
htable_vertex_init(allocator, &vertices);
if(aabb_is_degenerated(poly_desc->lower, poly_desc->upper)) goto exit;
@@ -491,12 +507,12 @@ scpr_mesh_clip
}
ERR(darray_int64_copy_and_clear(&mesh->coords, &coords));
- ERR(darray_size_t_copy_and_clear(&mesh->indices, &indices));
+ ERR(darray_uint32_copy_and_clear(&mesh->indices, &indices));
exit:
if(polygon) POLYGON(ref_put(polygon));
darray_int64_release(&coords);
- darray_size_t_release(&indices);
+ darray_uint32_release(&indices);
htable_vertex_release(&vertices);
return res;
error:
diff --git a/src/scpr_polygon.c b/src/scpr_polygon.c
@@ -19,9 +19,9 @@
#include <new>
#include <polygon.h>
#include <rsys/logger.h>
+#include <rsys/ref_count.h>
#include <rsys/mem_allocator.h>
#include <rsys/rsys.h>
-#include <rsys/double2.h>
#undef PI
#include <clipper2/clipper.h>
@@ -101,7 +101,7 @@ one_path_is_eq
sz = pp->size();
FOR_EACH(i, 0, sz) {
if(matched[i]) continue;
- if(path_is_eq(&pp->at(i), p)) {
+ if(path_is_eq(&(*pp)[i], p)) {
matched[i] = 1;
return 1;
}
@@ -137,7 +137,7 @@ scpr_polygon_create
/* Allocate paths the C++ way (placement new) */
new (&polygon->paths) Clipper2Lib::PathsD;
polygon->lower[0] = polygon->lower[1] = INT64_MAX;
- polygon->upper[0] = polygon->upper[1] = -INT64_MAX;
+ polygon->upper[0] = polygon->upper[1] = INT64_MIN;
exit:
if(out_polygon) *out_polygon = polygon;
@@ -172,7 +172,7 @@ scpr_polygon_ref_put
res_T
scpr_polygon_setup_indexed_vertices
(struct scpr_polygon* polygon,
- const size_t ncomponents, /* #connex components */
+ const size_t ncomponents,
void (*get_nverts)(const size_t icomponent, size_t *nverts, void* ctx),
void (*get_position)
(const size_t icomponent, const size_t ivert, double pos[2], void* ctx),
@@ -189,6 +189,13 @@ scpr_polygon_setup_indexed_vertices
goto error;
}
+ if(ncomponents > UINT32_MAX) {
+ logger_print(polygon->device->logger, LOG_ERROR,
+ "Too many components.\n");
+ res = RES_BAD_ARG;
+ goto error;
+ }
+
dev = polygon->device;
TRY(paths.resize(ncomponents));
@@ -197,6 +204,12 @@ scpr_polygon_setup_indexed_vertices
/* Get count for connex component c */
get_nverts(c, &nverts, data);
+ if(nverts > UINT32_MAX) {
+ logger_print(polygon->device->logger, LOG_ERROR,
+ "Too many vertices for component %zu.\n", c);
+ res = RES_BAD_ARG;
+ goto error;
+ }
TRY(paths[c].resize(nverts));
/* Fetch polygon positions for connex component c */
@@ -216,8 +229,9 @@ scpr_polygon_setup_indexed_vertices
/* Merge vertices, ... */
TRY(paths = Clipper2Lib::SimplifyPaths(paths, dev->inv_scale));
polygon->paths = std::move(paths);
+ paths.Clipper2Lib::Paths64::~Paths64();
changedc = (ncomponents != polygon->paths.size());
- for(c = 0; !changedv && c < paths.size(); c++) {
+ for(c = 0; !changedv && c < polygon->paths.size(); c++) {
size_t nv;
get_nverts(c, &nv, data);
changedv |= (nv != polygon->paths[c].size());
@@ -230,7 +244,7 @@ scpr_polygon_setup_indexed_vertices
/* Build bounding box */
polygon->lower[0] = polygon->lower[1] = INT64_MAX;
- polygon->upper[0] = polygon->upper[1] = -INT64_MAX;
+ polygon->upper[0] = polygon->upper[1] = INT64_MIN;
FOR_EACH(c, 0, ncomponents) {
size_t i, nverts;
get_nverts(c, &nverts, data);
@@ -252,7 +266,7 @@ error:
if(polygon) {
polygon->paths.clear();
polygon->lower[0] = polygon->lower[1] = INT64_MAX;
- polygon->upper[0] = polygon->upper[1] = -INT64_MAX;
+ polygon->upper[0] = polygon->upper[1] = INT64_MIN;
}
goto exit;
}
@@ -422,7 +436,7 @@ scpr_offset_polygon
/* Rebuild AABB */
poly_desc->lower[0] = poly_desc->lower[1] = INT64_MAX;
- poly_desc->upper[0] = poly_desc->upper[1] = -INT64_MAX;
+ poly_desc->upper[0] = poly_desc->upper[1] = INT64_MIN;
FOR_EACH(c, 0, poly_desc->paths.size()) {
size_t i, nverts;
nverts = poly_desc->paths[c].size();
@@ -477,7 +491,7 @@ scpr_polygon_eq
/* Check actual coordinates */
matched = (char*)calloc(sz, sizeof(*matched));
FOR_EACH(i, 0, sz) {
- if(!one_path_is_eq(&polygon1->paths, &polygon2->paths.at(i), matched)) {
+ if(!one_path_is_eq(&polygon1->paths, &polygon2->paths[i], matched)) {
*is_eq = 0;
goto exit;
}
@@ -490,3 +504,73 @@ exit:
error:
goto exit;
}
+
+res_T
+scpr_polygon_dump_to_obj
+ (struct scpr_polygon* polygon,
+ FILE* stream)
+{
+ res_T res = RES_OK;
+ size_t i, j, n = 1;
+
+ if(!polygon || !stream) {
+ res = RES_BAD_ARG;
+ goto error;
+ }
+
+ /* Vertice */
+ for(i = 0; i < polygon->paths.size(); i++) {
+ for(j = 0; j < polygon->paths[i].size(); j++) {
+ Clipper2Lib::Point64& pt = polygon->paths[i][j];
+ fprintf(stream, "v %zu %zu 0\n", pt.x, pt.y);
+ }
+ }
+
+ /* Lines */
+ for(i = 0; i < polygon->paths.size(); i++) {
+ size_t fst = n;
+ fprintf(stream, "l ");
+ for(j = 0; j < polygon->paths[i].size(); j++) {
+ fprintf(stream, " %zu", n++);
+ }
+ fprintf(stream, " %zu\n", fst);
+ }
+
+exit:
+ return res;
+error:
+ goto exit;
+}
+
+res_T
+scpr_polygon_dump_component_to_obj
+ (struct scpr_polygon* polygon,
+ const size_t icomponent,
+ FILE* stream)
+{
+ res_T res = RES_OK;
+ size_t i;
+
+ if(!polygon || !stream || icomponent >= polygon->paths.size()) {
+ res = RES_BAD_ARG;
+ goto error;
+ }
+
+ /* Vertice */
+ for(i = 0; i < polygon->paths[icomponent].size(); i++) {
+ Clipper2Lib::Point64& pt = polygon->paths[icomponent][i];
+ fprintf(stream, "v %zu %zu 0\n", pt.x, pt.y);
+ }
+
+ /* Line */
+ fprintf(stream, "l ");
+ for(i = 0; i < polygon->paths[icomponent].size(); i++) {
+ fprintf(stream, " %zu", ++i);
+ }
+ fprintf(stream, " 1\n");
+
+exit:
+ return res;
+error:
+ goto exit;
+}
diff --git a/src/test_scpr_intersector.c b/src/test_scpr_intersector.c
@@ -0,0 +1,206 @@
+/* Copyright (C) 2016-2018, 2021 |Meso|Star> (contact@meso-star.com)
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>. */
+
+#define _POSIX_C_SOURCE 200112L
+
+#include "scpr.h"
+#include "test_scpr_utils.h"
+
+#include <rsys/rsys.h>
+
+#include <memory.h>
+
+struct cpt {
+ size_t simple, collinear;
+};
+
+static int
+simple_intersection
+ (struct scpr_callback_segment* segment1,
+ struct scpr_callback_segment* segment2,
+ void* data)
+{
+ struct cpt* cpt = (struct cpt*)data;
+ (void)segment1; (void)segment2;
+ ASSERT(cpt);
+ cpt->simple++;
+ return 0;
+}
+
+static int
+collinear_segments
+ (struct scpr_callback_segment* segment1,
+ struct scpr_callback_segment* segment2,
+ void* data)
+{
+ struct cpt* cpt = (struct cpt*)data;
+ (void)segment1; (void)segment2;
+ ASSERT(cpt);
+ cpt->collinear++;
+ return 0;
+}
+
+int
+main(int argc, char** argv)
+{
+ struct mem_allocator allocator;
+ struct scpr_device* dev;
+ struct scpr_device_create_args args = SCPR_DEVICE_CREATE_ARGS_DEFAULT;
+ struct scpr_intersector* inter;
+ struct scpr_intersector_check_callbacks cb
+ = SCPR_INTERSECTOR_CHECK_CALLBACKS_NULL__ ;
+ struct polygon_context ctx;
+ struct scpr_polygon *p01, *p23, *p4;
+ size_t ncomps = 2;
+ double** coords;
+ /* 1,1
+ * +-----------+----+
+ * | / | /
+ * | / | /
+ * +-----------+-C2--+
+ * | | | |
+ * | | | |
+ * | +-C0--+-+---+----+----+
+ * | 0,0 |/ | |
+ * | +-C3-------+-C4-+
+ * +-C1--------+
+ * -0.5,-0.5
+ */
+ double coords0[] = {
+ 0.0, 0.0,
+ 1.0, 0.0,
+ 1.0, 1.0,
+ 0.0, 1.0
+ };
+ double coords1[] = {
+ -0.5, -0.5,
+ 0.5, -0.5,
+ 0.5, 0.5,
+ -0.5, 0.5
+ };
+ double coords2[] = {
+ 0.5, 0.5,
+ 1.0, 0.5,
+ 1.5, 1.0,
+ 1.0, 1.0
+ };
+ double coords3[] = {
+ 0.5, -0.3,
+ 1.5, -0.3,
+ 1.5, 0.0,
+ 0.7, 0.0
+ };
+ double coords4[] = {
+ 1.5, -0.3,
+ 2.0, -0.3,
+ 2.0, 0.0,
+ 1.5, 0
+ };
+ size_t nverts[] = { 4, 4 };
+ struct cpt cpt = { 0, 0 };
+ (void)argc, (void)argv;
+
+ mem_init_proxy_allocator(&allocator, &mem_default_allocator);
+ args.allocator = &allocator;
+ args.verbosity_level = 3;
+ args.precision = 6;
+ OK(scpr_device_create(&args, &dev));
+
+ BAD(scpr_intersector_create(NULL, NULL));
+ BAD(scpr_intersector_create(dev, NULL));
+ BAD(scpr_intersector_create(NULL, &inter));
+ OK(scpr_intersector_create(dev, &inter));
+
+ BAD(scpr_intersector_ref_get(NULL));
+ OK(scpr_intersector_ref_get(inter));
+
+ BAD(scpr_intersector_ref_put(NULL));
+ OK(scpr_intersector_ref_put(inter));
+
+ OK(scpr_polygon_create(dev, &p01));
+ OK(scpr_polygon_create(dev, &p23));
+ OK(scpr_polygon_create(dev, &p4));
+ coords = (double**)MEM_CALLOC(&allocator, ncomps, sizeof(*coords));
+ coords[0] = (double*)MEM_CALLOC(&allocator, nverts[0], 2*sizeof(**coords));
+ coords[1] = (double*)MEM_CALLOC(&allocator, nverts[1], 2*sizeof(**coords));
+
+ ctx.coords = coords;
+ ctx.nverts = nverts;
+ ctx.ncomps = ncomps;
+
+ #define SETUP scpr_polygon_setup_indexed_vertices
+ memcpy(coords[0], coords0, 2*nverts[0]*sizeof(**coords));
+ memcpy(coords[1], coords1, 2*nverts[1]*sizeof(**coords));
+ OK(SETUP(p01, ncomps, pget_nverts, pget_pos, &ctx));
+
+ memcpy(coords[0], coords2, 2*nverts[0]*sizeof(**coords));
+ memcpy(coords[1], coords3, 2*nverts[1]*sizeof(**coords));
+ OK(SETUP(p23, ncomps, pget_nverts, pget_pos, &ctx));
+
+ memcpy(coords[0], coords4, 2*nverts[0]*sizeof(**coords));
+ OK(SETUP(p4, 1, pget_nverts, pget_pos, &ctx));
+
+ BAD(scpr_intersector_register_component(NULL, NULL, ncomps));
+ BAD(scpr_intersector_register_component(NULL, NULL, 0));
+ BAD(scpr_intersector_register_component(NULL, p01, ncomps));
+ BAD(scpr_intersector_register_component(inter, NULL, ncomps));
+ BAD(scpr_intersector_register_component(NULL, p01, 0));
+ BAD(scpr_intersector_register_component(inter, NULL, 0));
+ BAD(scpr_intersector_register_component(inter, p01, ncomps));
+ OK(scpr_intersector_register_component(inter, p01, 0));
+ OK(scpr_intersector_register_component(inter, p01, 1));
+ OK(scpr_intersector_register_component(inter, p23, 0));
+ OK(scpr_intersector_register_component(inter, p23, 1));
+ BAD(scpr_intersector_register_component(inter, p23, 1)); /* Registered twice */
+
+ BAD(scpr_intersector_register_polygon(NULL, NULL));
+ BAD(scpr_intersector_register_polygon(NULL, p01));
+ BAD(scpr_intersector_register_polygon(inter, NULL));
+ OK(scpr_intersector_register_polygon(inter, p4));
+ BAD(scpr_intersector_register_polygon(inter, p4)); /* Registered twice */
+
+ BAD(scpr_intersector_check(NULL, NULL, NULL));
+ BAD(scpr_intersector_check(NULL, &cb, NULL));
+ BAD(scpr_intersector_check(inter, NULL, NULL));
+ BAD(scpr_intersector_check(inter, &cb, NULL));
+ BAD(scpr_intersector_check(inter, &cb, &cpt)); /* Callbacks are all NULL */
+ /* Report only intersections */
+ cb.simple_intersection = simple_intersection;
+ OK(scpr_intersector_check(inter, &cb, &cpt));
+ CHK(cpt.simple == 2);
+ CHK(cpt.collinear == 0);
+ /* Report intersections and collinearity */
+ cb.collinear_segments = collinear_segments;
+ cpt.simple = cpt.collinear = 0;
+ OK(scpr_intersector_check(inter, &cb, &cpt));
+ CHK(cpt.simple == 2);
+ CHK(cpt.collinear == 2);
+
+ OK(scpr_polygon_ref_put(p01));
+ OK(scpr_polygon_ref_put(p23));
+ OK(scpr_polygon_ref_put(p4));
+ OK(scpr_intersector_ref_put(inter));
+ OK(scpr_device_ref_put(dev));
+
+ MEM_RM(&allocator, coords[0]);
+ MEM_RM(&allocator, coords[1]);
+ MEM_RM(&allocator, coords);
+
+ check_memory_allocator(&allocator);
+ mem_shutdown_proxy_allocator(&allocator);
+ CHK(mem_allocated_size() == 0);
+ return 0;
+}
+
diff --git a/src/test_scpr_polygon.c b/src/test_scpr_polygon.c
@@ -13,6 +13,7 @@
* You should have received a copy of the GNU General Public License
* along with this program. If not, see <http://www.gnu.org/licenses/>. */
+#include <stdio.h>
#define _POSIX_C_SOURCE 200112L
#include "scpr.h"
@@ -59,6 +60,7 @@ main(int argc, char** argv)
struct scpr_device_create_args args = SCPR_DEVICE_CREATE_ARGS_DEFAULT;
int eq, in;
double low[2] = {0, 0}, up[2] = {1, 1};
+ FILE* stream = NULL;
(void)argc, (void)argv;
mem_init_proxy_allocator(&allocator, &mem_default_allocator);
@@ -206,6 +208,25 @@ main(int argc, char** argv)
BAD(scpr_offset_polygon(NULL, 0, SCPR_JOIN_MITER));
OK(scpr_offset_polygon(polygon, 0, SCPR_JOIN_MITER));
+ BAD(scpr_polygon_dump_to_obj(NULL, NULL));
+ BAD(scpr_polygon_dump_to_obj(polygon, NULL));
+ BAD(scpr_polygon_dump_to_obj(NULL, stream));
+ BAD(scpr_polygon_dump_to_obj(polygon, stream));
+ stream = tmpfile();
+ OK(scpr_polygon_dump_to_obj(polygon, stream));
+ fclose(stream);
+ stream = NULL;
+
+ BAD(scpr_polygon_dump_component_to_obj(NULL, ncomps, NULL));
+ BAD(scpr_polygon_dump_component_to_obj(polygon, ncomps, NULL));
+ BAD(scpr_polygon_dump_component_to_obj(NULL, 0, NULL));
+ BAD(scpr_polygon_dump_component_to_obj(NULL, ncomps, stream));
+ BAD(scpr_polygon_dump_component_to_obj(polygon, ncomps, stream));
+ BAD(scpr_polygon_dump_component_to_obj(polygon, 0, stream));
+ stream = tmpfile();
+ OK(scpr_polygon_dump_component_to_obj(polygon, 0, stream));
+ fclose(stream);
+
OK(scpr_device_ref_put(dev));
OK(scpr_polygon_ref_put(polygon));
OK(scpr_polygon_ref_put(copy));
