commit 166331e25ace41eba1c5342b2099dcc53d055fc5 parent 0a6f071ee24a47d854b82f489115fca75bed061a Author: Vincent Forest <vincent.forest@meso-star.com> Date: Thu, 17 Sep 2020 11:30:31 +0200 Merge branch 'release_0.4' Diffstat:
31 files changed, 761 insertions(+), 53 deletions(-)
diff --git a/README.md b/README.md @@ -2,21 +2,22 @@ ## Overview -Star-2D is a C/C++ library whose purpose is to manage a virtual 2D environment -composed of line segments. The resulting virtual world can then be ray-traced -and sampled, providing an efficient way to deal with geometric data of -arbitrary 2D contents. Actually, Star-2D internally manages the 2D scene -through 3D primitives whose Z component is assumed to be 0 or infinity. The -scene ray-tracing can thus be performed in the XY 2D plane or in fictive 3D -world where a line segment is actually a plane extruded to [-infinity, -+infinity] along the Z dimension. To ensure high ray tracing efficiency, the -Star-2D back-end heavily relies on the -[Intel® Rendering Framework](https://software.intel.com/sdvis): -[Embree](https://embree.github.io) -library that provides several ray-tracing kernels optimized for a wide range of -data workloads. The target users of Star-2D are thus programmers that have to -efficiently deal with complex 2D environment as numerical simulation engineers -or researchers in complex systems. +Star-2D is a C library that manages a virtual 2D environment composed of line +segments. The resulting virtual scene can then be accessed through +*ray-tracing*, *uniform sampling* or *closest point query*, providing an +efficient way to deal with geometric data of arbitrary 2D contents. To ensure +the efficiency of these operators, Star-3D internally relies on [Intel(R) +Rendering Framework](https://software.intel.com/en-us/rendering-framework): +[Embree](https://embree.github.io) that provides highly optimized acceleration +structures as well as traversal kernels for a wide range of data workloads. + +To query the scene data one has to create a *view* of the scene. On its +creation, the view internally builds data structures required by the +aforementioned access operators. These data structures are built from the scene +geometry as defined at the moment of the view creation; a view is thus +insensitive to scene updates following its creation. This means that several +views can be used to register different states of the same scene, giving to the +caller a great flexibility to manage the scene data. ## Install @@ -96,6 +97,19 @@ with `<STAR2D_INSTALL_DIR>` the install directory of Star-2D and ## Release notes +### Version 0.4 + +- Add the `s2d_scene_view_closest_point` function. This function retrieves the + closest point into the scene to a query position in a radius from ]0, INF]. + This closest point is returned as a regular hit which means that the function + returns to the caller not only the distance to the query position, but also + the geometric primitive onto which the point lies and its location onto this + primitive. If no segment lies around the query position in a distance lesser + than the one defined by the query radius, the returned hit is invalid which + can be checked with the regular `S2D_HIT_NONE` macro. Finally, this function + supports the filter functions so that the caller can choose to discard + closest hits according to its own criteria. + ### Version 0.3.1 - Fix the `s2d_segment_get_vertex_attrib` function: it could fail and return an @@ -126,7 +140,7 @@ with `<STAR2D_INSTALL_DIR>` the install directory of Star-2D and ## License -Copyright (C) 2016-2019 |Meso|Star> (<contact@meso-star.com>). Star-2D is free +Copyright (C) 2016-2020 |Meso|Star> (<contact@meso-star.com>). Star-2D is free software released under the CeCILL v2.1 license. You are welcome to redistribute it under certain conditions; refer to the COPYING files for details. diff --git a/cmake/CMakeLists.txt b/cmake/CMakeLists.txt @@ -1,4 +1,4 @@ -# Copyright (C) 2016-2019 |Meso|Star> (contact@meso-star.com) +# Copyright (C) 2016-2020 |Meso|Star> (contact@meso-star.com) # # This software is governed by the CeCILL license under French law and # abiding by the rules of distribution of free software. You can use, @@ -36,7 +36,7 @@ option(NO_TEST "Disable the test" OFF) ################################################################################ # Check dependencies ################################################################################ -find_package(Embree 3 REQUIRED) +find_package(Embree 3.6 REQUIRED) find_package(RCMake 0.2.2 REQUIRED) find_package(RSys 0.6 REQUIRED) @@ -56,8 +56,8 @@ endif() # Configure and define targets ################################################################################ set(VERSION_MAJOR 0) -set(VERSION_MINOR 3) -set(VERSION_PATCH 1) +set(VERSION_MINOR 4) +set(VERSION_PATCH 0) set(VERSION ${VERSION_MAJOR}.${VERSION_MINOR}.${VERSION_PATCH}) set(S2D_FILES_SRC @@ -67,6 +67,7 @@ set(S2D_FILES_SRC s2d_primitive.c s2d_scene.c s2d_scene_view.c + s2d_scene_view_closest_point.c s2d_shape.c) set(S2D_FILES_INC_API s2d.h) set(S2D_FILES_INC @@ -132,6 +133,7 @@ if(NOT NO_TEST) register_test(${_name} ${_name}) endfunction() + new_test(test_s2d_closest_point) new_test(test_s2d_device) new_test(test_s2d_primitive) new_test(test_s2d_sample) diff --git a/src/s2d.h b/src/s2d.h @@ -1,4 +1,4 @@ -/* Copyright (C) 2016-2019 |Meso|Star> (contact@meso-star.com) +/* Copyright (C) 2016-2020 |Meso|Star> (contact@meso-star.com) * * This software is governed by the CeCILL license under French law and * abiding by the rules of distribution of free software. You can use, @@ -148,9 +148,10 @@ enum s2d_scene_view_flag { }; /* Filter function data type. One can define such function to discard - * intersections along a ray with respect to user defined criteria, e.g.: - * masked/transparent primitive, etc. Return 0 or the intersection is not - * discarded and a value not equal to zero otherwise. */ + * intersections along a ray or the result of a closest point query with + * respect to user defined criteria, e.g.: masked/transparent primitive, etc. + * Return 0 if the intersection is not discarded and a value not equal to zero + * otherwise. */ typedef int (*s2d_hit_filter_function_T) (const struct s2d_hit* hit, @@ -289,8 +290,26 @@ s2d_scene_view_trace_ray_3d void* ray_data, struct s2d_hit* hit); +/* Return the point onto the scene segments that is the closest of the + * submitted `pos'. Note that even though only one point is returned, several + * position can have the same minimal distance to the queried position. The + * `radius' parameter defines the maximum search distance around `pos'. Each + * candidate position are internally filtered by the hit_filter_function + * attached to the corresponding shape; the user can thus reject a candidate + * position according to its own criteria. This function can be called only if + * the scnview was created with the S2D_TRACE flag which is actually the flag + * used to tell Star-2D to internally build an acceleration structure on which + * this function relies. */ +S2D_API res_T +s2d_scene_view_closest_point + (struct s2d_scene_view* scnview, + const float pos[2], /* Position to query */ + const float radius, /* Search distance in ]0, radius[ */ + void* query_data, /* User data sent to the hit filter func. May be NULL */ + struct s2d_hit* hit); + /* Uniformly sample the scene and returned the sampled primitive and its sample - * position. CCan be called only if the scnview was created with the + * position. Can be called only if the scnview was created with the * S2D_SAMPLE flag */ S2D_API res_T s2d_scene_view_sample @@ -415,7 +434,8 @@ s2d_segment_get_vertex_attrib struct s2d_attrib* attrib); /* Resulting attrib */ /******************************************************************************* - * Line Segments API - manage a list of segments + * Line Segments API - manage a list of segments. Normal segments point toward + * the semi space whose orientation is clock wise. ******************************************************************************/ S2D_API res_T s2d_line_segments_setup_indexed_vertices diff --git a/src/s2d_backend.h b/src/s2d_backend.h @@ -1,4 +1,4 @@ -/* Copyright (C) 2016-2019 |Meso|Star> (contact@meso-star.com) +/* Copyright (C) 2016-2020 |Meso|Star> (contact@meso-star.com) * * This software is a computer program whose purpose is to describe a * virtual 3D environment that can be ray-traced and sampled both robustly diff --git a/src/s2d_buffer.h b/src/s2d_buffer.h @@ -1,4 +1,4 @@ -/* Copyright (C) 2016-2019 |Meso|Star> (contact@meso-star.com) +/* Copyright (C) 2016-2020 |Meso|Star> (contact@meso-star.com) * * This software is governed by the CeCILL license under French law and * abiding by the rules of distribution of free software. You can use, diff --git a/src/s2d_c.h b/src/s2d_c.h @@ -1,4 +1,4 @@ -/* Copyright (C) 2016-2019 |Meso|Star> (contact@meso-star.com) +/* Copyright (C) 2016-2020 |Meso|Star> (contact@meso-star.com) * * This software is governed by the CeCILL license under French law and * abiding by the rules of distribution of free software. You can use, diff --git a/src/s2d_device.c b/src/s2d_device.c @@ -1,4 +1,4 @@ -/* Copyright (C) 2016-2019 |Meso|Star> (contact@meso-star.com) +/* Copyright (C) 2016-2020 |Meso|Star> (contact@meso-star.com) * * This software is governed by the CeCILL license under French law and * abiding by the rules of distribution of free software. You can use, diff --git a/src/s2d_device_c.h b/src/s2d_device_c.h @@ -1,4 +1,4 @@ -/* Copyright (C) 2016-2019 |Meso|Star> (contact@meso-star.com) +/* Copyright (C) 2016-2020 |Meso|Star> (contact@meso-star.com) * * This software is governed by the CeCILL license under French law and * abiding by the rules of distribution of free software. You can use, diff --git a/src/s2d_geometry.c b/src/s2d_geometry.c @@ -1,4 +1,4 @@ -/* Copyright (C) 2016-2019 |Meso|Star> (contact@meso-star.com) +/* Copyright (C) 2016-2020 |Meso|Star> (contact@meso-star.com) * * This software is governed by the CeCILL license under French law and * abiding by the rules of distribution of free software. You can use, diff --git a/src/s2d_geometry.h b/src/s2d_geometry.h @@ -1,4 +1,4 @@ -/* Copyright (C) 2016-2019 |Meso|Star> (contact@meso-star.com) +/* Copyright (C) 2016-2020 |Meso|Star> (contact@meso-star.com) * * This software is governed by the CeCILL license under French law and * abiding by the rules of distribution of free software. You can use, diff --git a/src/s2d_line_segments.c b/src/s2d_line_segments.c @@ -1,4 +1,4 @@ -/* Copyright (C) 2016-2019 |Meso|Star> (contact@meso-star.com) +/* Copyright (C) 2016-2020 |Meso|Star> (contact@meso-star.com) * * This software is governed by the CeCILL license under French law and * abiding by the rules of distribution of free software. You can use, @@ -433,7 +433,7 @@ line_segments_compute_area C = -f2_dot(N, v0); /* N.v0 + C = 0 */ tmp = v0[0]*v1[1] - v0[1]*v1[0]; /* Cross product */ - tmp = sqrt(tmp*tmp); /* 2 * area of the triangle */ + tmp = fabs(tmp); /* 2 * area of the triangle */ area2 += C > 0 ? tmp : -tmp; } return (float)(area2 * 0.5); diff --git a/src/s2d_line_segments.h b/src/s2d_line_segments.h @@ -1,4 +1,4 @@ -/* Copyright (C) 2016-2019 |Meso|Star> (contact@meso-star.com) +/* Copyright (C) 2016-2020 |Meso|Star> (contact@meso-star.com) * * This software is governed by the CeCILL license under French law and * abiding by the rules of distribution of free software. You can use, diff --git a/src/s2d_primitive.c b/src/s2d_primitive.c @@ -1,4 +1,4 @@ -/* Copyright (C) 2016-2019 |Meso|Star> (contact@meso-star.com) +/* Copyright (C) 2016-2020 |Meso|Star> (contact@meso-star.com) * * This software is governed by the CeCILL license under French law and * abiding by the rules of distribution of free software. You can use, diff --git a/src/s2d_scene.c b/src/s2d_scene.c @@ -1,4 +1,4 @@ -/* Copyright (C) 2016-2019 |Meso|Star> (contact@meso-star.com) +/* Copyright (C) 2016-2020 |Meso|Star> (contact@meso-star.com) * * This software is governed by the CeCILL license under French law and * abiding by the rules of distribution of free software. You can use, diff --git a/src/s2d_scene_c.h b/src/s2d_scene_c.h @@ -1,4 +1,4 @@ -/* Copyright (C) 2016-2019 |Meso|Star> (contact@meso-star.com) +/* Copyright (C) 2016-2020 |Meso|Star> (contact@meso-star.com) * * This software is governed by the CeCILL license under French law and * abiding by the rules of distribution of free software. You can use, diff --git a/src/s2d_scene_view.c b/src/s2d_scene_view.c @@ -1,4 +1,4 @@ -/* Copyright (C) 2016-2019 |Meso|Star> (contact@meso-star.com) +/* Copyright (C) 2016-2020 |Meso|Star> (contact@meso-star.com) * * This software is governed by the CeCILL license under French law and * abiding by the rules of distribution of free software. You can use, diff --git a/src/s2d_scene_view_c.h b/src/s2d_scene_view_c.h @@ -1,4 +1,4 @@ -/* Copyright (C) 2016-2019 |Meso|Star> (contact@meso-star.com) +/* Copyright (C) 2016-2020 |Meso|Star> (contact@meso-star.com) * * This software is governed by the CeCILL license under French law and * abiding by the rules of distribution of free software. You can use, diff --git a/src/s2d_scene_view_closest_point.c b/src/s2d_scene_view_closest_point.c @@ -0,0 +1,212 @@ +/* Copyright (C) 2016-2020 |Meso|Star> (contact@meso-star.com) + * + * This software is governed by the CeCILL license under French law and + * abiding by the rules of distribution of free software. You can use, + * modify and/or redistribute the software under the terms of the CeCILL + * license as circulated by CEA, CNRS and INRIA at the following URL + * "http://www.cecill.info". + * + * As a counterpart to the access to the source code and rights to copy, + * modify and redistribute granted by the license, users are provided only + * with a limited warranty and the software's author, the holder of the + * economic rights, and the successive licensors have only limited + * liability. + * + * In this respect, the user's attention is drawn to the risks associated + * with loading, using, modifying and/or developing or reproducing the + * software by the user in light of its specific status of free software, + * that may mean that it is complicated to manipulate, and that also + * therefore means that it is reserved for developers and experienced + * professionals having in-depth computer knowledge. Users are therefore + * encouraged to load and test the software's suitability as regards their + * requirements in conditions enabling the security of their systems and/or + * data to be ensured and, more generally, to use and operate it in the + * same conditions as regards security. + * + * The fact that you are presently reading this means that you have had + * knowledge of the CeCILL license and that you accept its terms. */ + +#include "s2d.h" +#include "s2d_device_c.h" +#include "s2d_geometry.h" +#include "s2d_line_segments.h" +#include "s2d_scene_view_c.h" + +#include <rsys/float2.h> + +struct point_query_context { + struct RTCPointQueryContext rtc; + struct s2d_scene_view* scnview; + void* data; /* Per point query defined data */ +}; + +/******************************************************************************* + * Helper functions + ******************************************************************************/ +static INLINE float* +closest_point_segment + (const float p[2], /* Position */ + const float v0[2], /* 1st segment vertex */ + const float v1[2], /* 2nd segment vertex */ + const float E[2], /* v0 -> v1 vector */ + float closest_pt[2], /* Closest position */ + float* s) /* Parametric coordinate of the closest point onto [v0, v1] */ +{ + float v[2]; /* Vector from v0 to p */ + float segment_len; /* Length of the [v0, v1] */ + float dst; /* Dst from v0 to the orthogonal projection of p onto [v0, v1] */ + ASSERT(p && v0 && v1); + ASSERT(f2_eq(f2_sub(v, v1, v0), E)); + + /* Orthogonally project the point onto the segment */ + f2_sub(v, p, v0); + segment_len = f2_len(E); + dst = f2_dot(v, E); + + /* Check if the closest point is the segment vertex 'v0' */ + if(dst <= 0) { + *s = 0; + return f2_set(closest_pt, v0); + } + /* Check if the closest point is the segment vertex 'v1' */ + if(dst >= segment_len) { + *s = 1; + return f2_set(closest_pt, v1); + } + + /* The closest point is on the segment */ + *s = CLAMP(dst / segment_len, 0, 1); + return f2_add(closest_pt, f2_mulf(closest_pt, E, dst/segment_len), v0); +} + +static bool +closest_point_line_segments + (struct RTCPointQueryFunctionArguments* args, + struct geometry* geom, + void* query_data) +{ + struct s2d_hit hit = S2D_HIT_NULL; + struct s2d_hit* out_hit = NULL; + struct hit_filter* filter = NULL; + const uint32_t* ids = NULL; + float v0[2], v1[2]; /* Segment vertices */ + float E[2]; /* Segment vector */ + float N[2]; /* Segment normal */ + float query_pos[2]; /* Submitted position */ + float closest_point[2]; /* Computed closest point */ + float vec[2]; /* Vector from query pos to the closest point */ + float dst; /* Distance to the closest point */ + float s; /* Parametric coordinate of the closest point */ + ASSERT(args && geom); + ASSERT(args->primID < line_segments_get_nsegments(geom->lines)); + + /* Fetch the line segments indices */ + ids = line_segments_get_ids(geom->lines) + args->primID*2/*#indices per segment*/; + + /* Fetch segments vertices */ + ASSERT(geom->lines->attribs_type[S2D_POSITION] == S2D_FLOAT2); + f2_set(v0, line_segments_get_pos(geom->lines)+ids[0]*2/*#coords per vertex */); + f2_set(v1, line_segments_get_pos(geom->lines)+ids[1]*2/*#coords per vertex */); + f2_sub(E, v1, v0); + + query_pos[0] = args->query->x; + query_pos[1] = args->query->y; + + /* Compute the closest point ont the segment from the sumbitted query_pos */ + closest_point_segment(query_pos, v0, v1, E, closest_point, &s); + + f2_sub(vec, closest_point, query_pos); + dst = f2_len(vec); + if(dst >= args->query->radius) return 0; + + /* Compute the segment normal */ + N[0] = E[1]; + N[1] = E[0]; + + /* Flip the geometry normal wrt the flip line_segments flag */ + if(geom->flip_contour) f2_minus(N, N); + + /* Setup the hit */ + hit.prim.mesh__ = geom; + hit.prim.prim_id = args->primID; + hit.prim.geom_id = geom->name; + hit.prim.scene_prim_id = hit.prim.prim_id + geom->scene_prim_id_offset; + hit.normal[0] = N[0]; + hit.normal[1] = N[1]; + hit.u = s; + hit.distance = dst; + + /* `vec' is the direction along which the closest point was found. Submit it + * to the filter function as the direction of the computed hit. */ + filter = &geom->lines->filter; + if(filter->func + && filter->func(&hit, query_pos, vec, query_data, filter->data)) { + return 0; /* This point is filtered. Discard it! */ + } + + /* Update output data */ + out_hit = args->userPtr; + *out_hit = hit; + args->query->radius = dst; /* Shrink the query radius */ + + return 1; /* Notify that the query radius was updated */ +} + +static bool +closest_point(struct RTCPointQueryFunctionArguments* args) +{ + struct point_query_context* ctx = NULL; + struct geometry* geom = NULL; + ASSERT(args); + + ctx = CONTAINER_OF(args->context, struct point_query_context, rtc); + + /* Instance are not supported by Star-2D */ + ASSERT(args->context->instStackSize == 0); + + geom = scene_view_geometry_from_embree_id(ctx->scnview, args->geomID); + return closest_point_line_segments(args, geom, ctx->data); +} + +/******************************************************************************* + * Exported functions + ******************************************************************************/ +res_T +s2d_scene_view_closest_point + (struct s2d_scene_view* scnview, + const float pos[2], + const float radius, + void* query_data, + struct s2d_hit* hit) +{ + struct RTCPointQuery query; + struct point_query_context query_ctx; + + if(!scnview || !pos || radius <= 0 || !hit) + return RES_BAD_ARG; + + if((scnview->mask & S2D_TRACE) == 0) { + log_error(scnview->scn->dev, + "%s: the S2D_TRACE flag is not active onto the submitted scene view.\n", + FUNC_NAME); + return RES_BAD_OP; + } + + *hit = S2D_HIT_NULL; + + /* Initialise the point query */ + query.x = pos[0]; + query.y = pos[1]; + query.z = 0; + query.radius = radius; + query.time = FLT_MAX; /* Invalid fields */ + + /* Initialise the point query context */ + rtcInitPointQueryContext(&query_ctx.rtc); + query_ctx.scnview = scnview; + query_ctx.data = query_data; + + /* Here we go! */ + rtcPointQuery(scnview->rtc_scn, &query, &query_ctx.rtc, closest_point, hit); + return RES_OK; +} diff --git a/src/s2d_shape.c b/src/s2d_shape.c @@ -1,4 +1,4 @@ -/* Copyright (C) 2016-2019 |Meso|Star> (contact@meso-star.com) +/* Copyright (C) 2016-2020 |Meso|Star> (contact@meso-star.com) * * This software is governed by the CeCILL license under French law and * abiding by the rules of distribution of free software. You can use, diff --git a/src/s2d_shape_c.h b/src/s2d_shape_c.h @@ -1,4 +1,4 @@ -/* Copyright (C) 2016-2019 |Meso|Star> (contact@meso-star.com) +/* Copyright (C) 2016-2020 |Meso|Star> (contact@meso-star.com) * * This software is governed by the CeCILL license under French law and * abiding by the rules of distribution of free software. You can use, diff --git a/src/test_s2d_closest_point.c b/src/test_s2d_closest_point.c @@ -0,0 +1,460 @@ +/* Copyright (C) 2016-2020 |Meso|Star> (contact@meso-star.com) + * + * This software is governed by the CeCILL license under French law and + * abiding by the rules of distribution of free software. You can use, + * modify and/or redistribute the software under the terms of the CeCILL + * license as circulated by CEA, CNRS and INRIA at the following URL + * "http://www.cecill.info". + * + * As a counterpart to the access to the source code and rights to copy, + * modify and redistribute granted by the license, users are provided only + * with a limited warranty and the software's author, the holder of the + * economic rights, and the successive licensors have only limited + * liability. + * + * In this respect, the user's attention is drawn to the risks associated + * with loading, using, modifying and/or developing or reproducing the + * software by the user in light of its specific status of free software, + * that may mean that it is complicated to manipulate, and that also + * therefore means that it is reserved for developers and experienced + * professionals having in-depth computer knowledge. Users are therefore + * encouraged to load and test the software's suitability as regards their + * requirements in conditions enabling the security of their systems and/or + * data to be ensured and, more generally, to use and operate it in the + * same conditions as regards security. + * + * The fact that you are presently reading this means that you have had + * knowledge of the CeCILL license and that you accept its terms. */ + +#include "s2d.h" +#include "test_s2d_utils.h" + +#include <rsys/float2.h> + +#define ON_VERTEX_EPSILON 1.e-4f +#define POSITION_EPSILON 1.e-3f + +struct closest_pt { + float pos[2]; + float normal[2]; + float dst; + unsigned iprim; + unsigned igeom; +}; + +#define CLOSEST_PT_NULL__ { \ + {0,0}, \ + {0,0}, \ + FLT_MAX, \ + S2D_INVALID_ID, \ + S2D_INVALID_ID, \ +} + +static const struct closest_pt CLOSEST_PT_NULL = CLOSEST_PT_NULL__; + +/******************************************************************************* + * Helper functions + ******************************************************************************/ +/* Function that computes the point onto the segment that ensures the minimum + * distance between the submitted `pos' and the segment. Use this routine to + * cross check the result of the s2d_scene_view_closest_point function */ +static float* +closest_point_segment + (const float p[2], /* Input pos */ + const float a[2], /* 1st segment vertex */ + const float b[2], /* 2nd segment vertex */ + float pt[2]) /* Closest point */ +{ + float v[2]; + float E[2]; + float dst; + float len; + + f2_sub(v, p, a); + f2_sub(E, b, a); + dst = f2_dot(v, E); + len = f2_len(E); + + if(dst <= 0) return f2_set(pt, a); + if(dst >= len) return f2_set(pt, b); + + f2_normalize(E, E); + f2_mulf(pt, E, dst); + f2_add(pt, pt, a); + return pt; +} + +static void +closest_point_line_segments + (const float pos[2], + const float* verts, + const unsigned* ids, + const unsigned nsegs, + const unsigned geom_id, + const unsigned prim_to_filter, + struct closest_pt* pt) +{ + unsigned iseg; + CHK(pos && verts && ids && pt); + + *pt = CLOSEST_PT_NULL; + pt->igeom = geom_id; + pt->dst = FLT_MAX; + + /* Find the closest point on the mesh */ + FOR_EACH(iseg, 0, nsegs) { + float v0[2]; + float v1[2]; + float closest_pt[2]; + float vec[2]; + float dst; + + if(iseg == prim_to_filter) continue; + + f2_set(v0, verts+ids[iseg*2+0]*2); + f2_set(v1, verts+ids[iseg*2+1]*2); + + closest_point_segment(pos, v0, v1, closest_pt); + dst = f2_len(f2_sub(vec, closest_pt, pos)); + + if(dst < pt->dst) { + f2_set(pt->pos, closest_pt); + pt->dst = dst; + pt->iprim = iseg; + f2_sub(pt->normal, v1, v0); + SWAP(float, pt->normal[0], pt->normal[1]); + f2_normalize(pt->normal, pt->normal); + } + } +} + +static INLINE int +hit_on_vertex(const struct s2d_hit* hit) +{ + struct s2d_attrib v0, v1, pos; + float E[2]; + float hit_pos[2]; + float segment_len; + float hit_len0; + float hit_len1; + ASSERT(hit && !S2D_HIT_NONE(hit)); + + /* Rertieve the segment vertices */ + S2D(segment_get_vertex_attrib(&hit->prim, 0, S2D_POSITION, &v0)); + S2D(segment_get_vertex_attrib(&hit->prim, 1, S2D_POSITION, &v1)); + + /* Compute the length of the segment */ + segment_len = f2_len(f2_sub(E, v1.value, v0.value)); + + /* Compute the hit position */ + CHK(s2d_primitive_get_attrib(&hit->prim, S2D_POSITION, hit->u, &pos) == RES_OK); + f2_set(hit_pos, pos.value); + + /* Compute the length from hit position to segment vertices */ + hit_len0 = f2_len(f2_sub(E, v0.value, hit_pos)); + hit_len1 = f2_len(f2_sub(E, v1.value, hit_pos)); + + if(hit_len0 / segment_len < ON_VERTEX_EPSILON + || hit_len1 / segment_len < ON_VERTEX_EPSILON) + return 1; + return 0; +} + +static void +check_closest_point + (const struct s2d_hit* hit, + const struct closest_pt* pt) +{ + struct s2d_attrib attr; + float N[2]; + + CHK(hit && pt); + CHK(!S2D_HIT_NONE(hit)); + + CHK(s2d_primitive_get_attrib + (&hit->prim, S2D_POSITION, hit->u, &attr) == RES_OK); + f2_normalize(N, hit->normal); + + if(!hit_on_vertex(hit)) { + CHK(hit->prim.prim_id == pt->iprim); + } + + if(hit->prim.prim_id == pt->iprim + && hit->prim.geom_id == pt->igeom) { + /* Due to numerical inaccuracies and/or the arbitrary order in which + * primitives are treated, 2 points on different primitive can have the + * same distance from the query position while their respective + * coordinates are not equal wrt POSITION_EPSILON. To avoid wrong + * assertion, we thus check the position returned by Star-2D against the + * manually computed position only if these positions lies on the same + * primitive */ + CHK(f2_eq_eps(pt->pos, attr.value, POSITION_EPSILON)); + CHK(f2_eq_eps(pt->normal, N, 1.e-4f)); + } + CHK(eq_epsf(hit->distance, pt->dst, 1.e-3f)); +} + +/******************************************************************************* + * Square test + ******************************************************************************/ +struct square_filter_context { + float query_pos[2]; + unsigned prim_to_filter; +}; + +static int +square_filter + (const struct s2d_hit* hit, + const float org[2], + const float dir[2], + void* query_data, + void* filter_data) +{ + struct square_filter_context* ctx = query_data; + struct s2d_attrib attr; + float pos[3]; + float vec[3]; + + CHK(hit && org && dir && !S2D_HIT_NONE(hit)); + CHK((intptr_t)filter_data == (intptr_t)0xDECAFBAD); + CHK(f2_normalize(vec, dir) != 0); + + f2_add(pos, org, f2_mulf(pos, vec, hit->distance)); + CHK(s2d_primitive_get_attrib + (&hit->prim, S2D_POSITION, hit->u, &attr) == RES_OK); + CHK(f2_eq_eps(attr.value, pos, POSITION_EPSILON)); + + if(!query_data) return 0; + + CHK(f2_eq_eps(ctx->query_pos, org, POSITION_EPSILON)); + + return ctx->prim_to_filter == hit->prim.prim_id; +} + +static void +check_closest_point_square + (const float pos[2], + unsigned igeom, + unsigned prim_to_filter, + struct s2d_hit* hit) +{ + struct closest_pt pt = CLOSEST_PT_NULL; + closest_point_line_segments + (pos, square_verts, square_ids, square_nsegs, igeom, prim_to_filter, &pt); + check_closest_point(hit, &pt); +} + +static void +test_square(struct s2d_device* dev) +{ + struct square_filter_context filter_ctx; + struct s2d_vertex_data vdata = S2D_VERTEX_DATA_NULL; + struct line_segments_desc desc; + struct s2d_hit hit = S2D_HIT_NULL; + struct s2d_scene* scn = NULL; + struct s2d_scene_view* view = NULL; + struct s2d_shape* shape = NULL; + void* ptr = (void*)((intptr_t)0xDECAFBAD); + float low[2], upp[2], mid[2]; + float pos[2]; + unsigned igeom; + size_t i; + + /* Create the Star-2D scene */ + CHK(s2d_scene_create(dev, &scn) == RES_OK); + CHK(s2d_shape_create_line_segments(dev, &shape) == RES_OK); + CHK(s2d_shape_get_id(shape, &igeom) == RES_OK); + CHK(s2d_line_segments_set_hit_filter_function + (shape, square_filter, ptr) == RES_OK); + CHK(s2d_scene_attach_shape(scn, shape) == RES_OK); + + vdata.usage = S2D_POSITION; + vdata.type = S2D_FLOAT2; + vdata.get = line_segments_get_position; + + /* Setup the square */ + desc.vertices = square_verts; + desc.indices = square_ids; + CHK(s2d_line_segments_setup_indexed_vertices(shape, square_nsegs, + line_segments_get_ids, square_nverts, &vdata, 1, &desc) == RES_OK); + + CHK(s2d_scene_view_create(scn, S2D_TRACE, &view) == RES_OK); + CHK(s2d_scene_view_get_aabb(view, low, upp) == RES_OK); + mid[0] = (low[0] + upp[0]) * 0.5f; + mid[1] = (low[1] + upp[1]) * 0.5f; + + /* Check the closest point query on the square */ + FOR_EACH(i, 0, 10000) { + /* Randomly generate a point in a bounding box that is 2 times the size of + * the square AABB */ + pos[0] = mid[0] + (rand_canonic() * 2 - 1) * (upp[0] - low[0]); + pos[1] = mid[1] + (rand_canonic() * 2 - 1) * (upp[1] - low[1]); + CHK(s2d_scene_view_closest_point(view, pos, (float)INF, NULL, &hit) == RES_OK); + check_closest_point_square(pos, igeom, S2D_INVALID_ID, &hit); + } + + /* Check closest point query filtering */ + filter_ctx.prim_to_filter = 2; + FOR_EACH(i, 0, 10000) { + /* Randomly generate a point in a bounding box that is 2 times the size of + * the square AABB */ + pos[0] = mid[0] + (rand_canonic() * 2 - 1) * (upp[0] - low[0]); + pos[1] = mid[1] + (rand_canonic() * 2 - 1) * (upp[1] - low[1]); + + f2_set(filter_ctx.query_pos, pos); + + CHK(s2d_scene_view_closest_point + (view, pos, (float)INF, &filter_ctx, &hit) == RES_OK); + check_closest_point_square(pos, igeom, filter_ctx.prim_to_filter, &hit); + } + + + /* Clean up */ + CHK(s2d_shape_ref_put(shape) == RES_OK); + CHK(s2d_scene_ref_put(scn) == RES_OK); + CHK(s2d_scene_view_ref_put(view) == RES_OK); +} + +/******************************************************************************* + * Single segment test + ******************************************************************************/ +static void +test_single_segment(struct s2d_device* dev) +{ + struct s2d_vertex_data vdata = S2D_VERTEX_DATA_NULL; + struct line_segments_desc desc; + struct s2d_hit hit = S2D_HIT_NULL; + struct s2d_scene* scn = NULL; + struct s2d_scene_view* view = NULL; + struct s2d_shape* shape = NULL; + struct s2d_attrib attr; + float vertices[4]; + float v0[2], v1[2]; + float low[2], upp[2], mid[2]; + float pos[2]; + float closest_pos[2]; + size_t i; + unsigned indices[2] = {0, 1}; + + f2(vertices+0, -0.5f, -0.3f); + f2(vertices+2, -0.4f, 0.2f); + + CHK(s2d_scene_create(dev, &scn) == RES_OK); + CHK(s2d_shape_create_line_segments(dev, &shape) == RES_OK); + CHK(s2d_scene_attach_shape(scn, shape) == RES_OK); + + vdata.usage = S2D_POSITION; + vdata.type = S2D_FLOAT2; + vdata.get = line_segments_get_position; + desc.vertices = vertices; + desc.indices = indices; + CHK(s2d_line_segments_setup_indexed_vertices + (shape, 1, line_segments_get_ids, 2, &vdata, 1, &desc) == RES_OK); + + CHK(s2d_scene_view_create(scn, S2D_TRACE, &view) == RES_OK); + + line_segments_get_position(0, v0, &desc); + line_segments_get_position(1, v1, &desc); + + /* Compute the segment AABB */ + low[0] = MMIN(v0[0], v1[0]); + low[1] = MMIN(v0[1], v1[1]); + upp[0] = MMAX(v0[0], v1[0]); + upp[1] = MMAX(v0[1], v1[1]); + mid[0] = (low[0] + upp[0]) * 0.5f; + mid[1] = (low[1] + upp[1]) * 0.5f; + + FOR_EACH(i, 0, 10000) { + /* Randomly generate a point in a bounding box that is 10 times the size of + * the triangle AABB */ + pos[0] = mid[0] + (rand_canonic() * 2 - 1) * (upp[0] - low[0]) * 5.f; + pos[1] = mid[1] + (rand_canonic() * 2 - 1) * (upp[1] - low[1]) * 5.f; + + CHK(s2d_scene_view_closest_point(view, pos, (float)INF, NULL, &hit) == RES_OK); + CHK(!S2D_HIT_NONE(&hit)); + CHK(s2d_primitive_get_attrib(&hit.prim, S2D_POSITION, hit.u, &attr) == RES_OK); + + /* Cross check the closest point query result */ + closest_point_segment(pos, v0, v1, closest_pos); + CHK(f2_eq_eps(closest_pos, attr.value, 1.e-4f)); + } + + FOR_EACH(i, 0, 10000) { + float radius; + + /* Randomly generate a point in a bounding box that is 10 times the size of + * the triangle AABB */ + pos[0] = mid[0] + (rand_canonic() * 2 - 1) * (upp[0] - low[0]) * 5.f; + pos[1] = mid[1] + (rand_canonic() * 2 - 1) * (upp[1] - low[1]) * 5.f; + + CHK(s2d_scene_view_closest_point(view, pos, (float)INF, NULL, &hit) == RES_OK); + CHK(!S2D_HIT_NONE(&hit)); + + /* Check that the radius is an exclusive upper bound */ + radius = hit.distance; + CHK(s2d_scene_view_closest_point(view, pos, radius, NULL, &hit) == RES_OK); + CHK(S2D_HIT_NONE(&hit)); + radius = nextafterf(radius, FLT_MAX); + CHK(s2d_scene_view_closest_point(view, pos, radius, NULL, &hit) == RES_OK); + CHK(!S2D_HIT_NONE(&hit)); + CHK(hit.distance == nextafterf(radius, 0.f)); + } + + CHK(s2d_scene_view_ref_put(view) == RES_OK); + CHK(s2d_shape_ref_put(shape) == RES_OK); + CHK(s2d_scene_ref_put(scn) == RES_OK); +} + +/******************************************************************************* + * Miscellaneous test + ******************************************************************************/ +static void +test_api(struct s2d_device* dev) +{ + struct s2d_hit hit = S2D_HIT_NULL; + struct s2d_scene* scn = NULL; + struct s2d_scene_view* view = NULL; + float pos[3] = {0}; + + CHK(s2d_scene_create(dev, &scn) == RES_OK); + CHK(s2d_scene_view_create(scn, S2D_TRACE, &view) == RES_OK); + + CHK(s2d_scene_view_closest_point(NULL, pos, 1.f, NULL, &hit) == RES_BAD_ARG); + CHK(s2d_scene_view_closest_point(view, NULL, 1.f, NULL, &hit) == RES_BAD_ARG); + CHK(s2d_scene_view_closest_point(view, pos, 0.f, NULL, &hit) == RES_BAD_ARG); + CHK(s2d_scene_view_closest_point(view, pos, 1.f, NULL, NULL) == RES_BAD_ARG); + CHK(s2d_scene_view_closest_point(view, pos, 1.f, NULL, &hit) == RES_OK); + CHK(S2D_HIT_NONE(&hit)); + + CHK(s2d_scene_view_ref_put(view) == RES_OK); + CHK(s2d_scene_view_create(scn, S2D_SAMPLE, &view) == RES_OK); + CHK(s2d_scene_view_closest_point(view, pos, 1.f, NULL, &hit) == RES_BAD_OP); + + CHK(s2d_scene_view_ref_put(view) == RES_OK); + CHK(s2d_scene_ref_put(scn) == RES_OK); +} + +/******************************************************************************* + * Main function + ******************************************************************************/ +int +main(int argc, char** argv) +{ + struct mem_allocator allocator; + struct s2d_device* dev = NULL; + (void)argc, (void)argv; + + mem_init_proxy_allocator(&allocator, &mem_default_allocator); + CHK(s2d_device_create(NULL, &allocator, 1, &dev) == RES_OK); + + test_api(dev); + test_single_segment(dev); + test_square(dev); + + CHK(s2d_device_ref_put(dev) == RES_OK); + + check_memory_allocator(&allocator); + mem_shutdown_proxy_allocator(&allocator); + CHK(mem_allocated_size() == 0); + return 0; +} diff --git a/src/test_s2d_device.c b/src/test_s2d_device.c @@ -1,4 +1,4 @@ -/* Copyright (C) 2016-2019 |Meso|Star> (contact@meso-star.com) +/* Copyright (C) 2016-2020 |Meso|Star> (contact@meso-star.com) * * This software is governed by the CeCILL license under French law and * abiding by the rules of distribution of free software. You can use, diff --git a/src/test_s2d_primitive.c b/src/test_s2d_primitive.c @@ -1,4 +1,4 @@ -/* Copyright (C) 2016-2019 |Meso|Star> (contact@meso-star.com) +/* Copyright (C) 2016-2020 |Meso|Star> (contact@meso-star.com) * * This software is governed by the CeCILL license under French law and * abiding by the rules of distribution of free software. You can use, diff --git a/src/test_s2d_sample.c b/src/test_s2d_sample.c @@ -1,4 +1,4 @@ -/* Copyright (C) 2016-2019 |Meso|Star> (contact@meso-star.com) +/* Copyright (C) 2016-2020 |Meso|Star> (contact@meso-star.com) * * This software is governed by the CeCILL license under French law and * abiding by the rules of distribution of free software. You can use, diff --git a/src/test_s2d_scene.c b/src/test_s2d_scene.c @@ -1,4 +1,4 @@ -/* Copyright (C) 2016-2019 |Meso|Star> (contact@meso-star.com) +/* Copyright (C) 2016-2020 |Meso|Star> (contact@meso-star.com) * * This software is governed by the CeCILL license under French law and * abiding by the rules of distribution of free software. You can use, diff --git a/src/test_s2d_scene_view.c b/src/test_s2d_scene_view.c @@ -1,4 +1,4 @@ -/* Copyright (C) 2016-2019 |Meso|Star> (contact@meso-star.com) +/* Copyright (C) 2016-2020 |Meso|Star> (contact@meso-star.com) * * This software is governed by the CeCILL license under French law and * abiding by the rules of distribution of free software. You can use, diff --git a/src/test_s2d_scene_view2.c b/src/test_s2d_scene_view2.c @@ -1,4 +1,4 @@ -/* Copyright (C) 2016-2019 |Meso|Star> (contact@meso-star.com) +/* Copyright (C) 2016-2020 |Meso|Star> (contact@meso-star.com) * * This software is governed by the CeCILL license under French law and * abiding by the rules of distribution of free software. You can use, diff --git a/src/test_s2d_shape.c b/src/test_s2d_shape.c @@ -1,4 +1,4 @@ -/* Copyright (C) 2016-2019 |Meso|Star> (contact@meso-star.com) +/* Copyright (C) 2016-2020 |Meso|Star> (contact@meso-star.com) * * This software is governed by the CeCILL license under French law and * abiding by the rules of distribution of free software. You can use, diff --git a/src/test_s2d_trace_ray.c b/src/test_s2d_trace_ray.c @@ -1,4 +1,4 @@ -/* Copyright (C) 2016-2019 |Meso|Star> (contact@meso-star.com) +/* Copyright (C) 2016-2020 |Meso|Star> (contact@meso-star.com) * * This software is governed by the CeCILL license under French law and * abiding by the rules of distribution of free software. You can use, diff --git a/src/test_s2d_trace_ray_3d.c b/src/test_s2d_trace_ray_3d.c @@ -1,4 +1,4 @@ -/* Copyright (C) 2016-2019 |Meso|Star> (contact@meso-star.com) +/* Copyright (C) 2016-2020 |Meso|Star> (contact@meso-star.com) * * This software is governed by the CeCILL license under French law and * abiding by the rules of distribution of free software. You can use, diff --git a/src/test_s2d_utils.h b/src/test_s2d_utils.h @@ -1,4 +1,4 @@ -/* Copyright (C) 2016-2019 |Meso|Star> (contact@meso-star.com) +/* Copyright (C) 2016-2020 |Meso|Star> (contact@meso-star.com) * * This software is governed by the CeCILL license under French law and * abiding by the rules of distribution of free software. You can use,