commit ad87d8924defd730ac9fa1b557b61b9fa35dae06
parent ec498207cd1ca73395ce4ede7e884a66217d090b
Author: Christophe Coustet <christophe.coustet@meso-star.com>
Date: Wed, 1 Feb 2023 16:04:57 +0100
Manage precision and range in clipping operations.
Diffstat:
5 files changed, 80 insertions(+), 39 deletions(-)
diff --git a/src/scpr.h b/src/scpr.h
@@ -85,8 +85,8 @@ scpr_polygon_ref_put
* limited range. Range checking along with the associated truncation process
* occur at vertices setup.
* The range of the coordinates is [-INT64_MAX*0.25E-6 +INT64_MAX*0.25E-6], that
- * is approximately [-2.3E18 + 2.3E18], and vertex coordinates are truncated
- * past the 6th decimal place. It is an error to use out-of-range values.
+ * is approximately [-2.3E18 +2.3E18], and vertex coordinates are truncated past
+ * the 6th decimal place. It is an error to use out-of-range values.
* Truncated coordinates can be retrieved using the appropriate getters. */
SCPR_API res_T
scpr_polygon_setup_indexed_vertices
@@ -142,6 +142,11 @@ SCPR_API res_T
scpr_mesh_ref_put
(struct scpr_mesh* mesh);
+/* In a way similar to polygons, meshes have their vertices coordinates range
+ * limited and truncated.
+ * However, there is currently a difference between the 2 setup operations that
+ * prevent to share the same coordinate space.
+ * Fixing this will require a change in the Clipper2 library. */
SCPR_API res_T
scpr_mesh_setup_indexed_vertices
(struct scpr_mesh* mesh,
@@ -151,7 +156,7 @@ scpr_mesh_setup_indexed_vertices
void (*get_position)(const size_t ivert, double pos[2], void* ctx),
void* data); /* Client data set as the last param of the callbacks */
-/* Clip the mesh against the polygon using the EvenOdd filling rule */
+/* Clip the mesh against the polygon using the EvenOdd filling rule. */
SCPR_API res_T
scpr_mesh_clip
(struct scpr_mesh* mesh, /* Candidate mesh to clip */
diff --git a/src/scpr_c.h b/src/scpr_c.h
@@ -25,11 +25,24 @@
#include <rsys/dynamic_array_size_t.h>
#include <rsys/hash_table.h>
+#include <math.h>
+
#undef PI
#include <clipper2/clipper.h>
#define ERR(Expr) { if((res = (Expr)) != RES_OK) goto error; } (void)0
+/* Sets the precision parameter, as expected by Clipper2.
+ * Allowed range is [-8 +8].
+ * This parameter defines both the floating point precision for the coordinates
+ * and the range of the coordinates.
+ * With a precision of 0, coordinates are truncated to the nearest integer and
+ * the coordinate range is [-INT64_MAX/4 +INT64_MAX/4] (that is approximately
+ * [-2.3E18 + 2.3E18]).
+ * Increasing precision by 1 adds 1 more decimal place to the coordinate
+ * precision and divides the coordinate range by 10. */
+#define PRECISION 6
+
struct mem_allocator;
struct vertex { double pos[2]; };
@@ -60,4 +73,27 @@ struct scpr_mesh {
struct mem_allocator* allocator;
};
+res_T INLINE
+check_and_truncate_vertex
+ (double pt[2])
+{
+ double scale = pow(10, PRECISION);
+ double tmp[2];
+ int64_t tmp2[2];
+ /* Truncate precision to ensure further consistency */
+ tmp2[0] = std::llround(pt[0] * scale);
+ tmp2[1] = std::llround(pt[1] * scale);
+ /* Store truncated vertex */
+ tmp[0] = (double)tmp2[0] / scale;
+ tmp[1] = (double)tmp2[1] / scale;
+ if(fabs(tmp[0] - pt[0]) > scale) {
+ return RES_BAD_ARG;
+ }
+ if(fabs(tmp[1] - pt[1]) * scale > 1) {
+ return RES_BAD_ARG;
+ }
+ d2_set(pt, tmp);
+ return RES_OK;
+}
+
#endif
diff --git a/src/scpr_mesh.c b/src/scpr_mesh.c
@@ -304,6 +304,8 @@ scpr_mesh_setup_indexed_vertices
pos = darray_double_data_get(&mesh->coords);
FOR_EACH(i, 0, nverts) {
get_position(i, pos+i*2, data);
+ /* Check range and truncate precision to ensure further consistency */
+ ERR(check_and_truncate_vertex(pos+i*2));
}
/* Fetch mesh indices */
@@ -386,7 +388,7 @@ scpr_mesh_clip
struct darray_double coords; /* Coordinates of the clipped mesh */
struct darray_size_t indices; /* Indices of the clipped mesh */
struct htable_vertex vertices; /* Map a coordinate to its index */
- Clipper2Lib::ClipperD clipper;
+ Clipper2Lib::ClipperD clipper(PRECISION);
Clipper2Lib::PathsD output; /* Contour of the clipped polgyon */
Clipper2Lib::PathsD cand_path; /* Contour of the candidate polygon */
Clipper2Lib::PathD tmp;
diff --git a/src/scpr_polygon.c b/src/scpr_polygon.c
@@ -13,7 +13,6 @@
* 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 <clipper2/clipper.h>
#include "scpr.h"
#include "scpr_c.h"
@@ -28,17 +27,6 @@
#include <math.h>
-/* Sets the precision parameter, as expected by Clipper2.
- * Allowed range is [-8 +8].
- * This parameter defines both the floating point precision for the coordinates
- * and the range of the coordinates.
- * With a precision of 0, coordinates are truncated to the nearest integer and
- * the coordinate range is [-INT64_MAX/4 +INT64_MAX/4] (that is approximately
- * [-2.3E18 + 2.3E18]).
- * Increasing precision by 1 adds 1 more decimal place to the coordinate
- * precision and divides the coordinate range by 10. */
-#define PRECISION 6
-
/*******************************************************************************
* Helper functions
******************************************************************************/
@@ -202,6 +190,7 @@ scpr_polygon_setup_indexed_vertices
{
size_t c;
double scale = pow(10, PRECISION);
+ Clipper2Lib::PathsD paths;
res_T res = RES_OK;
if(!polygon || !get_nverts || !get_position || !data) {
@@ -209,40 +198,42 @@ scpr_polygon_setup_indexed_vertices
goto error;
}
- TRY(polygon->paths.resize(ncomponents));
-
- d2_splat(polygon->lower, DBL_MAX);
- d2_splat(polygon->upper,-DBL_MAX);
+ TRY(paths.resize(ncomponents));
FOR_EACH(c, 0, ncomponents) {
size_t i, nverts;
/* Get count for connex component c */
get_nverts(c, &nverts, data);
- TRY(polygon->paths[c].resize(nverts));
+ TRY(paths[c].resize(nverts));
/* Fetch polygon positions for connex component c */
FOR_EACH(i, 0, nverts) {
double tmp[2];
- int64_t tmp2[2];
Clipper2Lib::PointD pt;
get_position(c, i, tmp, data);
- /* Truncate precision to ensure further consistency */
- tmp2[0] = std::llround(tmp[0] * scale);
- tmp2[1] = std::llround(tmp[1] * scale);
- /* Store truncated vertex */
- pt.x = (double)tmp2[0] / scale;
- pt.y = (double)tmp2[1] / scale;
- if(fabs(tmp[0] - pt.x) > scale) {
- res = RES_BAD_ARG;
- goto error;
- }
- if(fabs(tmp[1] - pt.y) * scale > 1) {
- res = RES_BAD_ARG;
- goto error;
- }
- polygon->paths[c][i] = pt;
+ /* Check range and truncate precision to ensure further consistency */
+ ERR(check_and_truncate_vertex(tmp));
+ pt.x = tmp[0];
+ pt.y = tmp[1];
+ paths[c][i] = pt;
+ }
+ }
+ /* Merge vertices, ... */
+ TRY(Clipper2Lib::SimplifyPaths(paths, 1/scale));
+ polygon->paths = std::move(paths);
+
+ /* Build bounding box */
+ d2_splat(polygon->lower, DBL_MAX);
+ d2_splat(polygon->upper,-DBL_MAX);
+ FOR_EACH(c, 0, ncomponents) {
+ size_t i, nverts;
+ get_nverts(c, &nverts, data);
+ FOR_EACH(i, 0, nverts) {
+ double tmp[2];
+ tmp[0] = polygon->paths[c][i].x;
+ tmp[1] = polygon->paths[c][i].y;
d2_min(polygon->lower, polygon->lower, tmp);
d2_max(polygon->upper, polygon->upper, tmp);
}
@@ -250,6 +241,7 @@ scpr_polygon_setup_indexed_vertices
exit:
return res;
+ paths.clear();
error:
if(polygon) {
polygon->paths.clear();
diff --git a/src/test_scpr_clip.c b/src/test_scpr_clip.c
@@ -52,7 +52,8 @@ test_triangle
(struct mem_allocator* allocator,
struct scpr_mesh* mesh)
{
- const double triangle_pos[] = { 0.0, 0.0, 0.0, 1.0, 1.0, 0.0 };
+ const double triangle_pos1[] = { 0, 0, 0, 1, 1, 0 };
+ const double triangle_pos2[] = { 0e20, 0e20, 0e20, 1e20, 1e20, 0e20 };
const size_t triangle_ids[] = { 0, 1, 2 };
double** clip_pos;
size_t nverts[] = { 3 };
@@ -74,11 +75,16 @@ test_triangle
CHK(scpr_polygon_setup_indexed_vertices(poly, ncomps, pget_nverts, pget_pos, &pctx)
== RES_OK);
- mctx.coords = triangle_pos;
+ /* Check out-of-range */
+ mctx.coords = triangle_pos2;
mctx.nverts = 3;
mctx.indices = triangle_ids;
mctx.ntris = 1;
CHK(scpr_mesh_setup_indexed_vertices
+ (mesh, mctx.ntris, mget_ids, 3, mget_pos, &mctx) == RES_BAD_ARG);
+
+ mctx.coords = triangle_pos1;
+ CHK(scpr_mesh_setup_indexed_vertices
(mesh, mctx.ntris, mget_ids, 3, mget_pos, &mctx) == RES_OK);
CHK(scpr_mesh_clip(NULL, SCPR_OPERATIONS_COUNT__, NULL) == RES_BAD_ARG);
