diff options
Diffstat (limited to 'source/blender/blenlib')
-rw-r--r-- | source/blender/blenlib/BLI_float2.hh | 13 | ||||
-rw-r--r-- | source/blender/blenlib/BLI_math_geom.h | 5 | ||||
-rw-r--r-- | source/blender/blenlib/BLI_mmap.h | 56 | ||||
-rw-r--r-- | source/blender/blenlib/CMakeLists.txt | 2 | ||||
-rw-r--r-- | source/blender/blenlib/intern/BLI_mmap.c | 233 | ||||
-rw-r--r-- | source/blender/blenlib/intern/math_geom.c | 53 |
6 files changed, 362 insertions, 0 deletions
diff --git a/source/blender/blenlib/BLI_float2.hh b/source/blender/blenlib/BLI_float2.hh index 2a5320e4c35..84dd0e358a2 100644 --- a/source/blender/blenlib/BLI_float2.hh +++ b/source/blender/blenlib/BLI_float2.hh @@ -29,6 +29,14 @@ struct float2 { { } + explicit float2(float value) : x(value), y(value) + { + } + + explicit float2(int value) : x(value), y(value) + { + } + float2(float x, float y) : x(x), y(y) { } @@ -52,6 +60,11 @@ struct float2 { return len_v2(*this); } + float length_squared() const + { + return len_squared_v2(*this); + } + float2 &operator+=(const float2 &other) { x += other.x; diff --git a/source/blender/blenlib/BLI_math_geom.h b/source/blender/blenlib/BLI_math_geom.h index c0a9ea91e75..e7dd1821a82 100644 --- a/source/blender/blenlib/BLI_math_geom.h +++ b/source/blender/blenlib/BLI_math_geom.h @@ -826,6 +826,11 @@ MINLINE float shell_v2v2_mid_normalized_to_dist(const float a[2], const float b[ float cubic_tangent_factor_circle_v3(const float tan_l[3], const float tan_r[3]); +/********************************** Geodesics *********************************/ + +float geodesic_distance_propagate_across_triangle( + const float v0[3], const float v1[3], const float v2[3], const float dist1, const float dist2); + /**************************** Inline Definitions ******************************/ #if BLI_MATH_DO_INLINE diff --git a/source/blender/blenlib/BLI_mmap.h b/source/blender/blenlib/BLI_mmap.h new file mode 100644 index 00000000000..4920152c9d1 --- /dev/null +++ b/source/blender/blenlib/BLI_mmap.h @@ -0,0 +1,56 @@ +/* + * 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 2 + * 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, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * The Original Code is Copyright (C) 2020 Blender Foundation. + * All rights reserved. + */ + +#pragma once + +/** \file + * \ingroup bli + */ + +#include "BLI_compiler_attrs.h" +#include "BLI_utildefines.h" + +#ifdef __cplusplus +extern "C" { +#endif + +/* Memory-mapped file IO that implements all the OS-specific details and error handling. */ + +struct BLI_mmap_file; + +typedef struct BLI_mmap_file BLI_mmap_file; + +/* Prepares an opened file for memory-mapped IO. + * May return NULL if the operation fails. + * Note that this seeks to the end of the file to determine its length. */ +BLI_mmap_file *BLI_mmap_open(int fd) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT; + +/* Reads length bytes from file at the given offset into dest. + * Returns whether the operation was successful (may fail when reading beyond the file + * end or when IO errors occur). */ +bool BLI_mmap_read(BLI_mmap_file *file, void *dest, size_t offset, size_t length) + ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1); + +void *BLI_mmap_get_pointer(BLI_mmap_file *file) ATTR_WARN_UNUSED_RESULT; + +void BLI_mmap_free(BLI_mmap_file *file) ATTR_NONNULL(1); + +#ifdef __cplusplus +} +#endif diff --git a/source/blender/blenlib/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt index aa4c4efe7d4..b7a13596dd0 100644 --- a/source/blender/blenlib/CMakeLists.txt +++ b/source/blender/blenlib/CMakeLists.txt @@ -54,6 +54,7 @@ set(SRC intern/BLI_memblock.c intern/BLI_memiter.c intern/BLI_mempool.c + intern/BLI_mmap.c intern/BLI_timer.c intern/DLRB_tree.c intern/array_store.c @@ -243,6 +244,7 @@ set(SRC BLI_mempool.h BLI_mesh_boolean.hh BLI_mesh_intersect.hh + BLI_mmap.h BLI_mpq2.hh BLI_mpq3.hh BLI_multi_value_map.hh diff --git a/source/blender/blenlib/intern/BLI_mmap.c b/source/blender/blenlib/intern/BLI_mmap.c new file mode 100644 index 00000000000..f0b13183c68 --- /dev/null +++ b/source/blender/blenlib/intern/BLI_mmap.c @@ -0,0 +1,233 @@ +/* + * 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 2 + * 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, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * The Original Code is Copyright (C) 2020 Blender Foundation. + * All rights reserved. + */ + +/** \file + * \ingroup bli + */ + +#include "BLI_mmap.h" +#include "BLI_fileops.h" +#include "BLI_listbase.h" +#include "MEM_guardedalloc.h" + +#include <string.h> + +#ifndef WIN32 +# include <stdlib.h> +# include <signal.h> +# include <sys/mman.h> // for mmap +# include <unistd.h> // for read close +#else +# include "BLI_winstuff.h" +# include <io.h> // for open close read +#endif + +struct BLI_mmap_file { + /* The address to which the file was mapped. */ + char *memory; + + /* The length of the file (and therefore the mapped region). */ + size_t length; + + /* Platform-specific handle for the mapping. */ + void *handle; + + /* Flag to indicate IO errors. Needs to be volatile since it's being set from + * within the signal handler, which is not part of the normal execution flow. */ + volatile bool io_error; +}; + +#ifndef WIN32 +/* When using memory-mapped files, any IO errors will result in a SIGBUS signal. + * Therefore, we need to catch that signal and stop reading the file in question. + * To do so, we keep a list of all current FileDatas that use memory-mapped files, + * and if a SIGBUS is caught, we check if the failed address is inside one of the + * mapped regions. + * If it is, we set a flag to indicate a failed read and remap the memory in + * question to a zero-backed region in order to avoid additional signals. + * The code that actually reads the memory area has to check whether the flag was + * set after it's done reading. + * If the error occurred outside of a memory-mapped region, we call the previous + * handler if one was configured and abort the process otherwise. + */ + +struct error_handler_data { + ListBase open_mmaps; + char configured; + void (*next_handler)(int, siginfo_t *, void *); +} error_handler = {0}; + +static void sigbus_handler(int sig, siginfo_t *siginfo, void *ptr) +{ + /* We only handle SIGBUS here for now. */ + BLI_assert(sig == SIGBUS); + + char *error_addr = (char *)siginfo->si_addr; + /* Find the file that this error belongs to. */ + LISTBASE_FOREACH (LinkData *, link, &error_handler.open_mmaps) { + BLI_mmap_file *file = link->data; + + /* Is the address where the error occurred in this file's mapped range? */ + if (error_addr >= file->memory && error_addr < file->memory + file->length) { + file->io_error = true; + + /* Replace the mapped memory with zeroes. */ + mmap(file->memory, file->length, PROT_READ, MAP_PRIVATE | MAP_ANONYMOUS | MAP_FIXED, -1, 0); + + return; + } + } + + /* Fall back to other handler if there was one. */ + if (error_handler.next_handler) { + error_handler.next_handler(sig, siginfo, ptr); + } + else { + fprintf(stderr, "Unhandled SIGBUS caught\n"); + abort(); + } +} + +/* Ensures that the error handler is set up and ready. */ +static bool sigbus_handler_setup(void) +{ + if (!error_handler.configured) { + struct sigaction newact = {0}, oldact = {0}; + + newact.sa_sigaction = sigbus_handler; + newact.sa_flags = SA_SIGINFO; + + if (sigaction(SIGBUS, &newact, &oldact)) { + return false; + } + + /* Remember the previously configured handler to fall back to it if the error + * does not belong to any of the mapped files. */ + error_handler.next_handler = oldact.sa_sigaction; + error_handler.configured = 1; + } + + return true; +} + +/* Adds a file to the list that the error handler checks. */ +static void sigbus_handler_add(BLI_mmap_file *file) +{ + BLI_addtail(&error_handler.open_mmaps, BLI_genericNodeN(file)); +} + +/* Removes a file from the list that the error handler checks. */ +static void sigbus_handler_remove(BLI_mmap_file *file) +{ + LinkData *link = BLI_findptr(&error_handler.open_mmaps, file, offsetof(LinkData, data)); + BLI_freelinkN(&error_handler.open_mmaps, link); +} +#endif + +BLI_mmap_file *BLI_mmap_open(int fd) +{ + void *memory, *handle = NULL; + size_t length = BLI_lseek(fd, 0, SEEK_END); + +#ifndef WIN32 + /* Ensure that the SIGBUS handler is configured. */ + if (!sigbus_handler_setup()) { + return NULL; + } + + /* Map the given file to memory. */ + memory = mmap(NULL, length, PROT_READ, MAP_PRIVATE, fd, 0); + if (memory == MAP_FAILED) { + return NULL; + } +#else + /* Convert the POSIX-style file descriptor to a Windows handle. */ + void *file_handle = (void *)_get_osfhandle(fd); + /* Memory mapping on Windows is a two-step process - first we create a mapping, + * then we create a view into that mapping. + * In our case, one view that spans the entire file is enough. */ + handle = CreateFileMapping(file_handle, NULL, PAGE_READONLY, 0, 0, NULL); + if (handle == NULL) { + return NULL; + } + memory = MapViewOfFile(handle, FILE_MAP_READ, 0, 0, 0); + if (memory == NULL) { + CloseHandle(handle); + return NULL; + } +#endif + + /* Now that the mapping was successful, allocate memory and set up the BLI_mmap_file. */ + BLI_mmap_file *file = MEM_callocN(sizeof(BLI_mmap_file), __func__); + file->memory = memory; + file->handle = handle; + file->length = length; + +#ifndef WIN32 + /* Register the file with the error handler. */ + sigbus_handler_add(file); +#endif + + return file; +} + +bool BLI_mmap_read(BLI_mmap_file *file, void *dest, size_t offset, size_t length) +{ + /* If a previous read has already failed or we try to read past the end, + * don't even attempt to read any further. */ + if (file->io_error || (offset + length > file->length)) { + return false; + } + +#ifndef WIN32 + /* If an error occurs in this call, sigbus_handler will be called and will set + * file->io_error to true. */ + memcpy(dest, file->memory + offset, length); +#else + /* On Windows, we use exception handling to be notified of errors. */ + __try { + memcpy(dest, file->memory + offset, length); + } + __except (GetExceptionCode() == EXCEPTION_IN_PAGE_ERROR ? EXCEPTION_EXECUTE_HANDLER : + EXCEPTION_CONTINUE_SEARCH) { + file->io_error = true; + return false; + } +#endif + + return !file->io_error; +} + +void *BLI_mmap_get_pointer(BLI_mmap_file *file) +{ + return file->memory; +} + +void BLI_mmap_free(BLI_mmap_file *file) +{ +#ifndef WIN32 + munmap((void *)file->memory, file->length); + sigbus_handler_remove(file); +#else + UnmapViewOfFile(file->memory); + CloseHandle(file->handle); +#endif + + MEM_freeN(file); +} diff --git a/source/blender/blenlib/intern/math_geom.c b/source/blender/blenlib/intern/math_geom.c index 3cc4d03d547..de5f96d3372 100644 --- a/source/blender/blenlib/intern/math_geom.c +++ b/source/blender/blenlib/intern/math_geom.c @@ -6246,3 +6246,56 @@ float cubic_tangent_factor_circle_v3(const float tan_l[3], const float tan_r[3]) const float angle_cos = cosf(angle); return ((1.0f - angle_cos) / (angle_sin * 2.0f)) / angle_sin; } + +/** + * Utility for computing approximate geodesic distances on triangle meshes. + * + * Given triangle with vertex coordinates v0, v1, v2, and known geodesic distances + * dist1 and dist2 at v1 and v2, estimate a geodesic distance at vertex v0. + * + * From "Dart Throwing on Surfaces", EGSR 2009. Section 7, Geodesic Dart Throwing. + */ +float geodesic_distance_propagate_across_triangle( + const float v0[3], const float v1[3], const float v2[3], const float dist1, const float dist2) +{ + /* Vectors along triangle edges. */ + float v10[3], v12[3]; + sub_v3_v3v3(v10, v0, v1); + sub_v3_v3v3(v12, v2, v1); + + if (dist1 != 0.0f && dist2 != 0.0f) { + /* Local coordinate system in the triangle plane. */ + float u[3], v[3], n[3]; + const float d12 = normalize_v3_v3(u, v12); + + if (d12 * d12 > 0.0f) { + cross_v3_v3v3(n, v12, v10); + normalize_v3(n); + cross_v3_v3v3(v, n, u); + + /* v0 in local coordinates */ + const float v0_[2] = {dot_v3v3(v10, u), fabsf(dot_v3v3(v10, v))}; + + /* Compute virtual source point in local coordinates, that we estimate the geodesic + * distance is being computed from. See figure 9 in the paper for the derivation. */ + const float a = 0.5f * (1.0f + (dist1 * dist1 - dist2 * dist2) / (d12 * d12)); + const float hh = dist1 * dist1 - a * a * d12 * d12; + + if (hh > 0.0f) { + const float h = sqrtf(hh); + const float S_[2] = {a * d12, -h}; + + /* Only valid if the line between the source point and v0 crosses + * the edge between v1 and v2. */ + const float x_intercept = S_[0] + h * (v0_[0] - S_[0]) / (v0_[1] + h); + if (x_intercept >= 0.0f && x_intercept <= d12) { + return len_v2v2(S_, v0_); + } + } + } + } + + /* Fall back to Dijsktra approximation in trivial case, or if no valid source + * point found that connects to v0 across the triangle. */ + return min_ff(dist1 + len_v3(v10), dist2 + len_v3v3(v0, v2)); +} |