/* MIT License Copyright (c) 2018-2020 Jonathan Young Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions: The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ /* thekla_atlas https://github.com/Thekla/thekla_atlas MIT License Copyright (c) 2013 Thekla, Inc Copyright NVIDIA Corporation 2006 -- Ignacio Castano <[email protected]> Fast-BVH https://github.com/brandonpelfrey/Fast-BVH MIT License Copyright (c) 2012 Brandon Pelfrey */ #include "xatlas.h" #ifndef XATLAS_C_API #define XATLAS_C_API … #endif #if XATLAS_C_API #include "xatlas_c.h" #endif #include <atomic> #include <condition_variable> #include <mutex> #include <thread> #include <assert.h> #include <float.h> // FLT_MAX #include <limits.h> #include <math.h> #define __STDC_LIMIT_MACROS #include <stdint.h> #include <stdio.h> #include <string.h> #ifndef XA_DEBUG #ifdef NDEBUG #define XA_DEBUG … #else #define XA_DEBUG … #endif #endif #ifndef XA_PROFILE #define XA_PROFILE … #endif #if XA_PROFILE #include <chrono> #endif #ifndef XA_MULTITHREADED #define XA_MULTITHREADED … #endif #define XA_STR(x) … #define XA_XSTR(x) … #ifndef XA_ASSERT #define XA_ASSERT(exp) … #endif #ifndef XA_DEBUG_ASSERT #define XA_DEBUG_ASSERT(exp) … #endif #ifndef XA_PRINT #define XA_PRINT(...) … #endif #ifndef XA_PRINT_WARNING #define XA_PRINT_WARNING(...) … #endif #define XA_ALLOC(tag, type) … #define XA_ALLOC_ARRAY(tag, type, num) … #define XA_REALLOC(tag, ptr, type, num) … #define XA_REALLOC_SIZE(tag, ptr, size) … #define XA_FREE(ptr) … #define XA_NEW(tag, type) … #define XA_NEW_ARGS(tag, type, ...) … #ifdef _MSC_VER #define XA_INLINE … #else #define XA_INLINE … #endif #if defined(__clang__) || defined(__GNUC__) #define XA_NODISCARD … #elif defined(_MSC_VER) #define XA_NODISCARD … #else #define XA_NODISCARD #endif #define XA_UNUSED(a) … #define XA_MERGE_CHARTS … #define XA_MERGE_CHARTS_MIN_NORMAL_DEVIATION … #define XA_RECOMPUTE_CHARTS … #define XA_CHECK_PARAM_WINDING … #define XA_CHECK_PIECEWISE_CHART_QUALITY … #define XA_CHECK_T_JUNCTIONS … #define XA_DEBUG_HEAP … #define XA_DEBUG_SINGLE_CHART … #define XA_DEBUG_ALL_CHARTS_INVALID … #define XA_DEBUG_EXPORT_ATLAS_IMAGES … #define XA_DEBUG_EXPORT_ATLAS_IMAGES_PER_CHART … #define XA_DEBUG_EXPORT_BOUNDARY_GRID … #define XA_DEBUG_EXPORT_TGA … #define XA_DEBUG_EXPORT_OBJ_FACE_GROUPS … #define XA_DEBUG_EXPORT_OBJ_CHART_GROUPS … #define XA_DEBUG_EXPORT_OBJ_PLANAR_REGIONS … #define XA_DEBUG_EXPORT_OBJ_CHARTS … #define XA_DEBUG_EXPORT_OBJ_TJUNCTION … #define XA_DEBUG_EXPORT_OBJ_CHARTS_AFTER_PARAMETERIZATION … #define XA_DEBUG_EXPORT_OBJ_INVALID_PARAMETERIZATION … #define XA_DEBUG_EXPORT_OBJ_RECOMPUTED_CHARTS … #define XA_DEBUG_EXPORT_OBJ … #ifdef _MSC_VER #define XA_FOPEN … #define XA_SPRINTF … #else #define XA_FOPEN(_file, _filename, _mode) … #define XA_SPRINTF(_buffer, _size, _format, ...) … #endif namespace xatlas { namespace internal { static ReallocFunc s_realloc = …; static FreeFunc s_free = …; static PrintFunc s_print = …; static bool s_printVerbose = …; #if XA_PROFILE typedef uint64_t Duration; #define XA_PROFILE_START … #define XA_PROFILE_END … #define XA_PROFILE_PRINT_AND_RESET … #define XA_PROFILE_ALLOC … struct ProfileData { #if XA_PROFILE_ALLOC std::atomic<Duration> alloc; #endif std::chrono::time_point<std::chrono::high_resolution_clock> addMeshRealStart; Duration addMeshReal; Duration addMeshCopyData; std::atomic<Duration> addMeshThread; std::atomic<Duration> addMeshCreateColocals; Duration computeChartsReal; std::atomic<Duration> computeChartsThread; std::atomic<Duration> createFaceGroups; std::atomic<Duration> extractInvalidMeshGeometry; std::atomic<Duration> chartGroupComputeChartsReal; std::atomic<Duration> chartGroupComputeChartsThread; std::atomic<Duration> createChartGroupMesh; std::atomic<Duration> createChartGroupMeshColocals; std::atomic<Duration> createChartGroupMeshBoundaries; std::atomic<Duration> buildAtlas; std::atomic<Duration> buildAtlasInit; std::atomic<Duration> planarCharts; std::atomic<Duration> originalUvCharts; std::atomic<Duration> clusteredCharts; std::atomic<Duration> clusteredChartsPlaceSeeds; std::atomic<Duration> clusteredChartsPlaceSeedsBoundaryIntersection; std::atomic<Duration> clusteredChartsRelocateSeeds; std::atomic<Duration> clusteredChartsReset; std::atomic<Duration> clusteredChartsGrow; std::atomic<Duration> clusteredChartsGrowBoundaryIntersection; std::atomic<Duration> clusteredChartsMerge; std::atomic<Duration> clusteredChartsFillHoles; std::atomic<Duration> copyChartFaces; std::atomic<Duration> createChartMeshAndParameterizeReal; std::atomic<Duration> createChartMeshAndParameterizeThread; std::atomic<Duration> createChartMesh; std::atomic<Duration> parameterizeCharts; std::atomic<Duration> parameterizeChartsOrthogonal; std::atomic<Duration> parameterizeChartsLSCM; std::atomic<Duration> parameterizeChartsRecompute; std::atomic<Duration> parameterizeChartsPiecewise; std::atomic<Duration> parameterizeChartsPiecewiseBoundaryIntersection; std::atomic<Duration> parameterizeChartsEvaluateQuality; Duration packCharts; Duration packChartsAddCharts; std::atomic<Duration> packChartsAddChartsThread; std::atomic<Duration> packChartsAddChartsRestoreTexcoords; Duration packChartsRasterize; Duration packChartsDilate; Duration packChartsFindLocation; Duration packChartsBlit; Duration buildOutputMeshes; }; static ProfileData s_profile; static double durationToMs(Duration c) { return (double)c * 0.001; } static double durationToSeconds(Duration c) { return (double)c * 0.000001; } #else #define XA_PROFILE_START(var) … #define XA_PROFILE_END(var) … #define XA_PROFILE_PRINT_AND_RESET(label, var) … #define XA_PROFILE_ALLOC … #endif struct MemTag { … }; #if XA_DEBUG_HEAP struct AllocHeader { size_t size; const char *file; int line; int tag; uint32_t id; AllocHeader *prev, *next; bool free; }; static std::mutex s_allocMutex; static AllocHeader *s_allocRoot = nullptr; static size_t s_allocTotalCount = 0, s_allocTotalSize = 0, s_allocPeakSize = 0, s_allocCount[MemTag::Count] = { 0 }, s_allocTotalTagSize[MemTag::Count] = { 0 }, s_allocPeakTagSize[MemTag::Count] = { 0 }; static uint32_t s_allocId =0 ; static constexpr uint32_t kAllocRedzone = 0x12345678; static void *Realloc(void *ptr, size_t size, int tag, const char *file, int line) { std::unique_lock<std::mutex> lock(s_allocMutex); if (!size && !ptr) return nullptr; uint8_t *realPtr = nullptr; AllocHeader *header = nullptr; if (ptr) { realPtr = ((uint8_t *)ptr) - sizeof(AllocHeader); header = (AllocHeader *)realPtr; } if (realPtr && size) { s_allocTotalSize -= header->size; s_allocTotalTagSize[header->tag] -= header->size; // realloc, remove. if (header->prev) header->prev->next = header->next; else s_allocRoot = header->next; if (header->next) header->next->prev = header->prev; } if (!size) { s_allocTotalSize -= header->size; s_allocTotalTagSize[header->tag] -= header->size; XA_ASSERT(!header->free); // double free header->free = true; return nullptr; } size += sizeof(AllocHeader) + sizeof(kAllocRedzone); uint8_t *newPtr = (uint8_t *)s_realloc(realPtr, size); if (!newPtr) return nullptr; header = (AllocHeader *)newPtr; header->size = size; header->file = file; header->line = line; header->tag = tag; header->id = s_allocId++; header->free = false; if (!s_allocRoot) { s_allocRoot = header; header->prev = header->next = 0; } else { header->prev = nullptr; header->next = s_allocRoot; s_allocRoot = header; header->next->prev = header; } s_allocTotalCount++; s_allocTotalSize += size; if (s_allocTotalSize > s_allocPeakSize) s_allocPeakSize = s_allocTotalSize; s_allocCount[tag]++; s_allocTotalTagSize[tag] += size; if (s_allocTotalTagSize[tag] > s_allocPeakTagSize[tag]) s_allocPeakTagSize[tag] = s_allocTotalTagSize[tag]; auto redzone = (uint32_t *)(newPtr + size - sizeof(kAllocRedzone)); *redzone = kAllocRedzone; return newPtr + sizeof(AllocHeader); } static void ReportLeaks() { printf("Checking for memory leaks...\n"); bool anyLeaks = false; AllocHeader *header = s_allocRoot; while (header) { if (!header->free) { printf(" Leak: ID %u, %zu bytes, %s %d\n", header->id, header->size, header->file, header->line); anyLeaks = true; } auto redzone = (const uint32_t *)((const uint8_t *)header + header->size - sizeof(kAllocRedzone)); if (*redzone != kAllocRedzone) printf(" Redzone corrupted: %zu bytes %s %d\n", header->size, header->file, header->line); header = header->next; } if (!anyLeaks) printf(" No memory leaks\n"); header = s_allocRoot; while (header) { AllocHeader *destroy = header; header = header->next; s_realloc(destroy, 0); } s_allocRoot = nullptr; s_allocTotalSize = s_allocPeakSize = 0; for (int i = 0; i < MemTag::Count; i++) s_allocTotalTagSize[i] = s_allocPeakTagSize[i] = 0; } static void PrintMemoryUsage() { XA_PRINT("Total allocations: %zu\n", s_allocTotalCount); XA_PRINT("Memory usage: %0.2fMB current, %0.2fMB peak\n", internal::s_allocTotalSize / 1024.0f / 1024.0f, internal::s_allocPeakSize / 1024.0f / 1024.0f); static const char *labels[] = { // Sync with MemTag "Default", "BitImage", "BVH", "Matrix", "Mesh", "MeshBoundaries", "MeshColocals", "MeshEdgeMap", "MeshIndices", "MeshNormals", "MeshPositions", "MeshTexcoords", "OpenNL", "SegmentAtlasChartCandidates", "SegmentAtlasChartFaces", "SegmentAtlasMeshData", "SegmentAtlasPlanarRegions" }; for (int i = 0; i < MemTag::Count; i++) { XA_PRINT(" %s: %zu allocations, %0.2fMB current, %0.2fMB peak\n", labels[i], internal::s_allocCount[i], internal::s_allocTotalTagSize[i] / 1024.0f / 1024.0f, internal::s_allocPeakTagSize[i] / 1024.0f / 1024.0f); } } #define XA_PRINT_MEM_USAGE … #else static void *Realloc(void *ptr, size_t size, int /*tag*/, const char * /*file*/, int /*line*/) { … } #define XA_PRINT_MEM_USAGE #endif static constexpr float kPi = …; static constexpr float kPi2 = …; static constexpr float kEpsilon = …; static constexpr float kAreaEpsilon = …; static constexpr float kNormalEpsilon = …; static int align(int x, int a) { … } template <typename T> static T max(const T &a, const T &b) { … } template <typename T> static T min(const T &a, const T &b) { … } template <typename T> static T max3(const T &a, const T &b, const T &c) { … } /// Return the maximum of the three arguments. template <typename T> static T min3(const T &a, const T &b, const T &c) { … } /// Clamp between two values. template <typename T> static T clamp(const T &x, const T &a, const T &b) { … } template <typename T> static void swap(T &a, T &b) { … } FloatUint32; static bool isFinite(float f) { … } static bool isNan(float f) { … } // Robust floating point comparisons: // http://realtimecollisiondetection.net/blog/?p=89 static bool equal(const float f0, const float f1, const float epsilon) { … } static int ftoi_ceil(float val) { … } static bool isZero(const float f, const float epsilon) { … } static float square(float f) { … } /** Return the next power of two. * @see http://graphics.stanford.edu/~seander/bithacks.html * @warning Behaviour for 0 is undefined. * @note isPowerOfTwo(x) == true -> nextPowerOfTwo(x) == x * @note nextPowerOfTwo(x) = 2 << log2(x-1) */ static uint32_t nextPowerOfTwo(uint32_t x) { … } class Vector2 { … }; static bool operator==(const Vector2 &a, const Vector2 &b) { … } static bool operator!=(const Vector2 &a, const Vector2 &b) { … } /*static Vector2 operator+(const Vector2 &a, const Vector2 &b) { return Vector2(a.x + b.x, a.y + b.y); }*/ static Vector2 operator-(const Vector2 &a, const Vector2 &b) { … } static Vector2 operator*(const Vector2 &v, float s) { … } static float dot(const Vector2 &a, const Vector2 &b) { … } static float lengthSquared(const Vector2 &v) { … } static float length(const Vector2 &v) { … } #if XA_DEBUG static bool isNormalized(const Vector2 &v, float epsilon = kNormalEpsilon) { return equal(length(v), 1, epsilon); } #endif static Vector2 normalize(const Vector2 &v) { … } static Vector2 normalizeSafe(const Vector2 &v, const Vector2 &fallback) { … } static bool equal(const Vector2 &v1, const Vector2 &v2, float epsilon) { … } static Vector2 min(const Vector2 &a, const Vector2 &b) { … } static Vector2 max(const Vector2 &a, const Vector2 &b) { … } static bool isFinite(const Vector2 &v) { … } static float triangleArea(const Vector2 &a, const Vector2 &b, const Vector2 &c) { … } static bool linesIntersect(const Vector2 &a1, const Vector2 &a2, const Vector2 &b1, const Vector2 &b2, float epsilon) { … } struct Vector2i { … }; class Vector3 { … }; static Vector3 operator+(const Vector3 &a, const Vector3 &b) { … } static Vector3 operator-(const Vector3 &a, const Vector3 &b) { … } static bool operator==(const Vector3 &a, const Vector3 &b) { … } static Vector3 cross(const Vector3 &a, const Vector3 &b) { … } static Vector3 operator*(const Vector3 &v, float s) { … } static Vector3 operator/(const Vector3 &v, float s) { … } static float dot(const Vector3 &a, const Vector3 &b) { … } static float lengthSquared(const Vector3 &v) { … } static float length(const Vector3 &v) { … } static bool isNormalized(const Vector3 &v, float epsilon = kNormalEpsilon) { … } static Vector3 normalize(const Vector3 &v) { … } static Vector3 normalizeSafe(const Vector3 &v, const Vector3 &fallback) { … } static bool equal(const Vector3 &v0, const Vector3 &v1, float epsilon) { … } static Vector3 min(const Vector3 &a, const Vector3 &b) { … } static Vector3 max(const Vector3 &a, const Vector3 &b) { … } #if XA_DEBUG bool isFinite(const Vector3 &v) { return isFinite(v.x) && isFinite(v.y) && isFinite(v.z); } #endif struct Extents2 { … }; // From Fast-BVH struct AABB { … }; struct ArrayBase { … }; template<typename T> class Array { … }; template<typename T> struct ArrayView { … }; template<typename T> struct ConstArrayView { … }; /// Basis class to compute tangent space basis, ortogonalizations and to transform vectors from one space to another. struct Basis { … }; // Simple bit array. class BitArray { … }; class BitImage { … }; // From Fast-BVH class BVH { … }; struct Fit { … }; static uint32_t sdbmHash(const void *data_in, uint32_t size, uint32_t h = 5381) { … } template <typename T> static uint32_t hash(const T &t, uint32_t h = 5381) { … } template <typename Key> struct Hash { … }; template <typename Key> struct PassthroughHash { … }; template <typename Key> struct Equal { … }; template<typename Key, typename H = Hash<Key>, typename E = Equal<Key> > class HashMap { … }; template<typename T> static void insertionSort(T *data, uint32_t length) { … } class KISSRng { … }; // Based on Pierre Terdiman's and Michael Herf's source code. // http://www.codercorner.com/RadixSortRevisited.htm // http://www.stereopsis.com/radix.html class RadixSort { … }; // Wrapping this in a class allows temporary arrays to be re-used. class BoundingBox2D { … }; struct EdgeKey { … }; struct EdgeHash { … }; static uint32_t meshEdgeFace(uint32_t edge) { … } static uint32_t meshEdgeIndex0(uint32_t edge) { … } static uint32_t meshEdgeIndex1(uint32_t edge) { … } struct MeshFlags { … }; class Mesh { … }; struct MeshFaceGroups { … }; constexpr MeshFaceGroups::Handle MeshFaceGroups::kInvalid; #if XA_CHECK_T_JUNCTIONS static bool lineIntersectsPoint(const Vector3 &point, const Vector3 &lineStart, const Vector3 &lineEnd, float *t, float epsilon) { float tt; if (!t) t = &tt; *t = 0.0f; if (equal(lineStart, point, epsilon) || equal(lineEnd, point, epsilon)) return false; // Vertex lies on either line vertices. const Vector3 v01 = point - lineStart; const Vector3 v21 = lineEnd - lineStart; const float l = length(v21); const float d = length(cross(v01, v21)) / l; if (!isZero(d, epsilon)) return false; *t = dot(v01, v21) / (l * l); return *t > kEpsilon && *t < 1.0f - kEpsilon; } // Returns the number of T-junctions found. static int meshCheckTJunctions(const Mesh &inputMesh) { int count = 0; const uint32_t vertexCount = inputMesh.vertexCount(); const uint32_t edgeCount = inputMesh.edgeCount(); for (uint32_t v = 0; v < vertexCount; v++) { if (!inputMesh.isBoundaryVertex(v)) continue; // Find edges that this vertex overlaps with. const Vector3 &pos = inputMesh.position(v); for (uint32_t e = 0; e < edgeCount; e++) { if (!inputMesh.isBoundaryEdge(e)) continue; const Vector3 &edgePos1 = inputMesh.position(inputMesh.vertexAt(meshEdgeIndex0(e))); const Vector3 &edgePos2 = inputMesh.position(inputMesh.vertexAt(meshEdgeIndex1(e))); float t; if (lineIntersectsPoint(pos, edgePos1, edgePos2, &t, inputMesh.epsilon())) count++; } } return count; } #endif // References invalid faces and vertices in a mesh. struct InvalidMeshGeometry { … }; struct Progress { … }; struct Spinlock { … }; struct TaskGroupHandle { … }; struct Task { … }; #if XA_MULTITHREADED class TaskScheduler { … }; thread_local uint32_t TaskScheduler::m_threadIndex; #else class TaskScheduler { public: ~TaskScheduler() { for (uint32_t i = 0; i < m_groups.size(); i++) destroyGroup({ i }); } uint32_t threadCount() const { return 1; } TaskGroupHandle createTaskGroup(void *userData = nullptr, uint32_t reserveSize = 0) { TaskGroup *group = XA_NEW(MemTag::Default, TaskGroup); group->queue.reserve(reserveSize); group->userData = userData; m_groups.push_back(group); TaskGroupHandle handle; handle.value = m_groups.size() - 1; return handle; } void run(TaskGroupHandle handle, Task task) { m_groups[handle.value]->queue.push_back(task); } void wait(TaskGroupHandle *handle) { if (handle->value == UINT32_MAX) { XA_DEBUG_ASSERT(false); return; } TaskGroup *group = m_groups[handle->value]; for (uint32_t i = 0; i < group->queue.size(); i++) group->queue[i].func(group->userData, group->queue[i].userData); group->queue.clear(); destroyGroup(*handle); handle->value = UINT32_MAX; } static uint32_t currentThreadIndex() { return 0; } private: void destroyGroup(TaskGroupHandle handle) { TaskGroup *group = m_groups[handle.value]; if (group) { group->~TaskGroup(); XA_FREE(group); m_groups[handle.value] = nullptr; } } struct TaskGroup { Array<Task> queue; void *userData; }; Array<TaskGroup *> m_groups; }; #endif #if XA_DEBUG_EXPORT_TGA const uint8_t TGA_TYPE_RGB = 2; const uint8_t TGA_ORIGIN_UPPER = 0x20; #pragma pack(push, 1) struct TgaHeader { uint8_t id_length; uint8_t colormap_type; uint8_t image_type; uint16_t colormap_index; uint16_t colormap_length; uint8_t colormap_size; uint16_t x_origin; uint16_t y_origin; uint16_t width; uint16_t height; uint8_t pixel_size; uint8_t flags; enum { Size = 18 }; }; #pragma pack(pop) static void WriteTga(const char *filename, const uint8_t *data, uint32_t width, uint32_t height) { XA_DEBUG_ASSERT(sizeof(TgaHeader) == TgaHeader::Size); FILE *f; XA_FOPEN(f, filename, "wb"); if (!f) return; TgaHeader tga; tga.id_length = 0; tga.colormap_type = 0; tga.image_type = TGA_TYPE_RGB; tga.colormap_index = 0; tga.colormap_length = 0; tga.colormap_size = 0; tga.x_origin = 0; tga.y_origin = 0; tga.width = (uint16_t)width; tga.height = (uint16_t)height; tga.pixel_size = 24; tga.flags = TGA_ORIGIN_UPPER; fwrite(&tga, sizeof(TgaHeader), 1, f); fwrite(data, sizeof(uint8_t), width * height * 3, f); fclose(f); } #endif template<typename T> class ThreadLocal { … }; // Implemented as a struct so the temporary arrays can be reused. struct Triangulator { … }; class UniformGrid2 { … }; struct UvMeshChart { … }; struct UvMesh { … }; struct UvMeshInstance { … }; /* * Copyright (c) 2004-2010, Bruno Levy * All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are met: * * * Redistributions of source code must retain the above copyright notice, * this list of conditions and the following disclaimer. * * Redistributions in binary form must reproduce the above copyright notice, * this list of conditions and the following disclaimer in the documentation * and/or other materials provided with the distribution. * * Neither the name of the ALICE Project-Team nor the names of its * contributors may be used to endorse or promote products derived from this * software without specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE * POSSIBILITY OF SUCH DAMAGE. * * If you modify this software, you should include a notice giving the * name of the person performing the modification, the date of modification, * and the reason for such modification. * * Contact: Bruno Levy * * [email protected] * * ALICE Project * LORIA, INRIA Lorraine, * Campus Scientifique, BP 239 * 54506 VANDOEUVRE LES NANCY CEDEX * FRANCE */ namespace opennl { #define NL_NEW(T) … #define NL_NEW_ARRAY(T,NB) … #define NL_RENEW_ARRAY(T,x,NB) … #define NL_DELETE(x) … #define NL_DELETE_ARRAY(x) … #define NL_CLEAR(x, T) … #define NL_CLEAR_ARRAY(T,x,NB) … #define NL_NEW_VECTOR(dim) … #define NL_DELETE_VECTOR(ptr) … struct NLMatrixStruct; NLMatrix; NLDestroyMatrixFunc; NLMultMatrixVectorFunc; #define NL_MATRIX_SPARSE_DYNAMIC … #define NL_MATRIX_CRS … #define NL_MATRIX_OTHER … struct NLMatrixStruct { … }; /* Dynamic arrays for sparse row/columns */ struct NLCoeff { … }; struct NLRowColumn { … }; /* Compressed Row Storage */ struct NLCRSMatrix { … }; /* SparseMatrix data structure */ struct NLSparseMatrix { … }; /* NLContext data structure */ struct NLBufferBinding { … }; #define NL_BUFFER_ITEM(B,i) … struct NLContext { … }; static void nlDeleteMatrix(NLMatrix M) { … } static void nlMultMatrixVector(NLMatrix M, const double* x, double* y) { … } static void nlRowColumnConstruct(NLRowColumn* c) { … } static void nlRowColumnDestroy(NLRowColumn* c) { … } static void nlRowColumnGrow(NLRowColumn* c) { … } static void nlRowColumnAdd(NLRowColumn* c, uint32_t index, double value) { … } /* Does not check whether the index already exists */ static void nlRowColumnAppend(NLRowColumn* c, uint32_t index, double value) { … } static void nlRowColumnZero(NLRowColumn* c) { … } static void nlRowColumnClear(NLRowColumn* c) { … } static int nlCoeffCompare(const void* p1, const void* p2) { … } static void nlRowColumnSort(NLRowColumn* c) { … } /* CRSMatrix data structure */ static void nlCRSMatrixDestroy(NLCRSMatrix* M) { … } static void nlCRSMatrixMultSlice(NLCRSMatrix* M, const double* x, double* y, uint32_t Ibegin, uint32_t Iend) { … } static void nlCRSMatrixMult(NLCRSMatrix* M, const double* x, double* y) { … } static void nlCRSMatrixConstruct(NLCRSMatrix* M, uint32_t m, uint32_t n, uint32_t nnz, uint32_t nslices) { … } /* SparseMatrix data structure */ static void nlSparseMatrixDestroyRowColumns(NLSparseMatrix* M) { … } static void nlSparseMatrixDestroy(NLSparseMatrix* M) { … } static void nlSparseMatrixAdd(NLSparseMatrix* M, uint32_t i, uint32_t j, double value) { … } /* Returns the number of non-zero coefficients */ static uint32_t nlSparseMatrixNNZ(NLSparseMatrix* M) { … } static void nlSparseMatrixSort(NLSparseMatrix* M) { … } /* SparseMatrix x Vector routines, internal helper routines */ static void nlSparseMatrix_mult_rows(NLSparseMatrix* A, const double* x, double* y) { … } static void nlSparseMatrixMult(NLSparseMatrix* A, const double* x, double* y) { … } static void nlSparseMatrixConstruct(NLSparseMatrix* M, uint32_t m, uint32_t n) { … } static NLMatrix nlCRSMatrixNewFromSparseMatrix(NLSparseMatrix* M) { … } static void nlMatrixCompress(NLMatrix* M) { … } static NLContext *nlNewContext() { … } static void nlDeleteContext(NLContext *context) { … } static double ddot(int n, const double *x, const double *y) { … } static void daxpy(int n, double a, const double *x, double *y) { … } static void dscal(int n, double a, double *x) { … } /* * The implementation of the solvers is inspired by * the lsolver library, by Christian Badura, available from: * http://www.mathematik.uni-freiburg.de * /IAM/Research/projectskr/lin_solver/ * * About the Conjugate Gradient, details can be found in: * Ashby, Manteuffel, Saylor * A taxononmy for conjugate gradient methods * SIAM J Numer Anal 27, 1542-1568 (1990) * * This version is completely abstract, the same code can be used for * CPU/GPU, dense matrix / sparse matrix etc... * Abstraction is realized through: * - Abstract matrix interface (NLMatrix), that can implement different * versions of matrix x vector product (CPU/GPU, sparse/dense ...) */ static uint32_t nlSolveSystem_PRE_CG(NLMatrix M, NLMatrix P, double* b, double* x, double eps, uint32_t max_iter, double *sq_bnorm, double *sq_rnorm) { … } static uint32_t nlSolveSystemIterative(NLContext *context, NLMatrix M, NLMatrix P, double* b_in, double* x_in, double eps, uint32_t max_iter) { … } static bool nlSolveIterative(NLContext *context) { … } struct NLJacobiPreconditioner { … }; static void nlJacobiPreconditionerDestroy(NLJacobiPreconditioner* M) { … } static void nlJacobiPreconditionerMult(NLJacobiPreconditioner* M, const double* x, double* y) { … } static NLMatrix nlNewJacobiPreconditioner(NLMatrix M_in) { … } #define NL_NB_VARIABLES … #define NL_MAX_ITERATIONS … static void nlSolverParameteri(NLContext *context, uint32_t pname, int param) { … } static void nlSetVariable(NLContext *context, uint32_t index, double value) { … } static double nlGetVariable(NLContext *context, uint32_t index) { … } static void nlLockVariable(NLContext *context, uint32_t index) { … } static void nlVariablesToVector(NLContext *context) { … } static void nlVectorToVariables(NLContext *context) { … } static void nlCoefficient(NLContext *context, uint32_t index, double value) { … } #define NL_SYSTEM … #define NL_MATRIX … #define NL_ROW … static void nlBegin(NLContext *context, uint32_t prim) { … } static void nlEnd(NLContext *context, uint32_t prim) { … } static bool nlSolve(NLContext *context) { … } } // namespace opennl namespace raster { class ClippedTriangle { … }; /// A callback to sample the environment. Return false to terminate rasterization. SamplingCallback; /// A triangle for rasterization. struct Triangle { … }; // Process the given triangle. Returns false if rasterization was interrupted by the callback. static bool drawTriangle(const Vector2 &extents, const Vector2 v[3], SamplingCallback cb, void *param) { … } } // namespace raster namespace segment { // - Insertion is o(n) // - Smallest element goes at the end, so that popping it is o(1). struct CostQueue { … }; struct AtlasData { … }; // If MeshDecl::vertexUvData is set on input meshes, find charts by floodfilling faces in world/model space without crossing UV seams. struct OriginalUvCharts { … }; #if XA_DEBUG_EXPORT_OBJ_PLANAR_REGIONS static uint32_t s_planarRegionsCurrentRegion; static uint32_t s_planarRegionsCurrentVertex; #endif struct PlanarCharts { … }; struct ClusteredCharts { … }; struct ChartGeneratorType { … }; struct Atlas { … }; struct ComputeUvMeshChartsTaskArgs { … }; // Charts are found by floodfilling faces without crossing UV seams. struct ComputeUvMeshChartsTask { … }; static void runComputeUvMeshChartsTask(void * /*groupUserData*/, void *taskUserData) { … } static bool computeUvMeshCharts(TaskScheduler *taskScheduler, ArrayView<UvMesh *> meshes, ProgressFunc progressFunc, void *progressUserData) { … } } // namespace segment namespace param { // Fast sweep in 3 directions static bool findApproximateDiameterVertices(Mesh *mesh, uint32_t *a, uint32_t *b) { … } // From OpenNL LSCM example. // Computes the coordinates of the vertices of a triangle in a local 2D orthonormal basis of the triangle's plane. static void projectTriangle(Vector3 p0, Vector3 p1, Vector3 p2, Vector2 *z0, Vector2 *z1, Vector2 *z2) { … } // Conformal relations from Brecht Van Lommel (based on ABF): static float vec_angle_cos(const Vector3 &v1, const Vector3 &v2, const Vector3 &v3) { … } static float vec_angle(const Vector3 &v1, const Vector3 &v2, const Vector3 &v3) { … } static void triangle_angles(const Vector3 &v1, const Vector3 &v2, const Vector3 &v3, float *a1, float *a2, float *a3) { … } static bool setup_abf_relations(opennl::NLContext *context, int id0, int id1, int id2, const Vector3 &p0, const Vector3 &p1, const Vector3 &p2) { … } static bool computeLeastSquaresConformalMap(Mesh *mesh) { … } struct PiecewiseParam { … }; // Estimate quality of existing parameterization. struct Quality { … }; struct ChartCtorBuffers { … }; class Chart { … }; struct CreateAndParameterizeChartTaskGroupArgs { … }; struct CreateAndParameterizeChartTaskArgs { … }; static void runCreateAndParameterizeChartTask(void *groupUserData, void *taskUserData) { … } // Set of charts corresponding to mesh faces in the same face group. class ChartGroup { … }; struct ChartGroupComputeChartsTaskGroupArgs { … }; static void runChartGroupComputeChartsTask(void *groupUserData, void *taskUserData) { … } struct MeshComputeChartsTaskGroupArgs { … }; struct MeshComputeChartsTaskArgs { … }; #if XA_DEBUG_EXPORT_OBJ_FACE_GROUPS static uint32_t s_faceGroupsCurrentVertex = 0; #endif static void runMeshComputeChartsTask(void *groupUserData, void *taskUserData) { … } /// An atlas is a set of chart groups. class Atlas { … }; } // namespace param namespace pack { class AtlasImage { … }; struct Chart { … }; struct AddChartTaskArgs { … }; static void runAddChartTask(void *groupUserData, void *taskUserData) { … } struct Atlas { … }; } // namespace pack } // namespace internal // Used to map triangulated polygons back to polygons. struct MeshPolygonMapping { … }; struct Context { … }; Atlas *Create() { … } static void DestroyOutputMeshes(Context *ctx) { … } void Destroy(Atlas *atlas) { … } static void runAddMeshTask(void *groupUserData, void *taskUserData) { … } static internal::Vector3 DecodePosition(const MeshDecl &meshDecl, uint32_t index) { … } static internal::Vector3 DecodeNormal(const MeshDecl &meshDecl, uint32_t index) { … } static internal::Vector2 DecodeUv(const MeshDecl &meshDecl, uint32_t index) { … } static uint32_t DecodeIndex(IndexFormat format, const void *indexData, int32_t offset, uint32_t i) { … } AddMeshError AddMesh(Atlas *atlas, const MeshDecl &meshDecl, uint32_t meshCountHint) { … } void AddMeshJoin(Atlas *atlas) { … } AddMeshError AddUvMesh(Atlas *atlas, const UvMeshDecl &decl) { … } void ComputeCharts(Atlas *atlas, ChartOptions options) { … } void PackCharts(Atlas *atlas, PackOptions packOptions) { … } void Generate(Atlas *atlas, ChartOptions chartOptions, PackOptions packOptions) { … } void SetProgressCallback(Atlas *atlas, ProgressFunc progressFunc, void *progressUserData) { … } void SetAlloc(ReallocFunc reallocFunc, FreeFunc freeFunc) { … } void SetPrint(PrintFunc print, bool verbose) { … } const char *StringForEnum(AddMeshError error) { … } const char *StringForEnum(ProgressCategory category) { … } } // namespace xatlas #if XATLAS_C_API static_assert(sizeof(xatlas::Chart) == sizeof(xatlasChart), "xatlasChart size mismatch"); static_assert(sizeof(xatlas::Vertex) == sizeof(xatlasVertex), "xatlasVertex size mismatch"); static_assert(sizeof(xatlas::Mesh) == sizeof(xatlasMesh), "xatlasMesh size mismatch"); static_assert(sizeof(xatlas::Atlas) == sizeof(xatlasAtlas), "xatlasAtlas size mismatch"); static_assert(sizeof(xatlas::MeshDecl) == sizeof(xatlasMeshDecl), "xatlasMeshDecl size mismatch"); static_assert(sizeof(xatlas::UvMeshDecl) == sizeof(xatlasUvMeshDecl), "xatlasUvMeshDecl size mismatch"); static_assert(sizeof(xatlas::ChartOptions) == sizeof(xatlasChartOptions), "xatlasChartOptions size mismatch"); static_assert(sizeof(xatlas::PackOptions) == sizeof(xatlasPackOptions), "xatlasPackOptions size mismatch"); #ifdef __cplusplus extern "C" { #endif xatlasAtlas *xatlasCreate() { return (xatlasAtlas *)xatlas::Create(); } void xatlasDestroy(xatlasAtlas *atlas) { xatlas::Destroy((xatlas::Atlas *)atlas); } xatlasAddMeshError xatlasAddMesh(xatlasAtlas *atlas, const xatlasMeshDecl *meshDecl, uint32_t meshCountHint) { return (xatlasAddMeshError)xatlas::AddMesh((xatlas::Atlas *)atlas, *(const xatlas::MeshDecl *)meshDecl, meshCountHint); } void xatlasAddMeshJoin(xatlasAtlas *atlas) { xatlas::AddMeshJoin((xatlas::Atlas *)atlas); } xatlasAddMeshError xatlasAddUvMesh(xatlasAtlas *atlas, const xatlasUvMeshDecl *decl) { return (xatlasAddMeshError)xatlas::AddUvMesh((xatlas::Atlas *)atlas, *(const xatlas::UvMeshDecl *)decl); } void xatlasComputeCharts(xatlasAtlas *atlas, const xatlasChartOptions *chartOptions) { xatlas::ComputeCharts((xatlas::Atlas *)atlas, chartOptions ? *(xatlas::ChartOptions *)chartOptions : xatlas::ChartOptions()); } void xatlasPackCharts(xatlasAtlas *atlas, const xatlasPackOptions *packOptions) { xatlas::PackCharts((xatlas::Atlas *)atlas, packOptions ? *(xatlas::PackOptions *)packOptions : xatlas::PackOptions()); } void xatlasGenerate(xatlasAtlas *atlas, const xatlasChartOptions *chartOptions, const xatlasPackOptions *packOptions) { xatlas::Generate((xatlas::Atlas *)atlas, chartOptions ? *(xatlas::ChartOptions *)chartOptions : xatlas::ChartOptions(), packOptions ? *(xatlas::PackOptions *)packOptions : xatlas::PackOptions()); } void xatlasSetProgressCallback(xatlasAtlas *atlas, xatlasProgressFunc progressFunc, void *progressUserData) { xatlas::ProgressFunc pf; *(void **)&pf = (void *)progressFunc; xatlas::SetProgressCallback((xatlas::Atlas *)atlas, pf, progressUserData); } void xatlasSetAlloc(xatlasReallocFunc reallocFunc, xatlasFreeFunc freeFunc) { xatlas::SetAlloc((xatlas::ReallocFunc)reallocFunc, (xatlas::FreeFunc)freeFunc); } void xatlasSetPrint(xatlasPrintFunc print, bool verbose) { xatlas::SetPrint((xatlas::PrintFunc)print, verbose); } const char *xatlasAddMeshErrorString(xatlasAddMeshError error) { return xatlas::StringForEnum((xatlas::AddMeshError)error); } const char *xatlasProgressCategoryString(xatlasProgressCategory category) { return xatlas::StringForEnum((xatlas::ProgressCategory)category); } void xatlasMeshDeclInit(xatlasMeshDecl *meshDecl) { xatlas::MeshDecl init; memcpy(meshDecl, &init, sizeof(init)); } void xatlasUvMeshDeclInit(xatlasUvMeshDecl *uvMeshDecl) { xatlas::UvMeshDecl init; memcpy(uvMeshDecl, &init, sizeof(init)); } void xatlasChartOptionsInit(xatlasChartOptions *chartOptions) { xatlas::ChartOptions init; memcpy(chartOptions, &init, sizeof(init)); } void xatlasPackOptionsInit(xatlasPackOptions *packOptions) { xatlas::PackOptions init; memcpy(packOptions, &init, sizeof(init)); } #ifdef __cplusplus } // extern "C" #endif #endif // XATLAS_C_API
Codebase Browser
godot