diff options
author | Sergey Sharybin <sergey@blender.org> | 2022-10-07 15:52:28 +0300 |
---|---|---|
committer | Sergey Sharybin <sergey@blender.org> | 2022-10-07 15:55:23 +0300 |
commit | 7383c6c309ca7c474253b7e50cc5042e23e2eb40 (patch) | |
tree | e5583c8951015df2d4765ba695fcc2e759d47aa1 /intern/mikktspace | |
parent | a56a90a8e2f3f029b9828ffaea21edc3e6679014 (diff) | |
parent | 87ef423e6ebdb90e0e8937b7e749d470a000b3e4 (diff) |
Merge branch 'master' into tracking_toolstracking_tools
Diffstat (limited to 'intern/mikktspace')
-rw-r--r-- | intern/mikktspace/CMakeLists.txt | 42 | ||||
-rw-r--r-- | intern/mikktspace/mikk_atomic_hash_set.hh | 189 | ||||
-rw-r--r-- | intern/mikktspace/mikk_float3.hh | 128 | ||||
-rw-r--r-- | intern/mikktspace/mikk_util.hh | 156 | ||||
-rw-r--r-- | intern/mikktspace/mikktspace.c | 1906 | ||||
-rw-r--r-- | intern/mikktspace/mikktspace.h | 152 | ||||
-rw-r--r-- | intern/mikktspace/mikktspace.hh | 829 |
7 files changed, 1321 insertions, 2081 deletions
diff --git a/intern/mikktspace/CMakeLists.txt b/intern/mikktspace/CMakeLists.txt index f968e0b2de4..4ad1bea9c8a 100644 --- a/intern/mikktspace/CMakeLists.txt +++ b/intern/mikktspace/CMakeLists.txt @@ -1,28 +1,24 @@ # SPDX-License-Identifier: GPL-2.0-or-later # Copyright 2006 Blender Foundation. All rights reserved. -if(CMAKE_COMPILER_IS_GNUCC) - remove_cc_flag( - "-Wshadow" - "-Werror=shadow" - ) -endif() - -set(INC - . -) - -set(INC_SYS - -) +add_library(bf_intern_mikktspace INTERFACE) +target_include_directories(bf_intern_mikktspace INTERFACE .) -set(SRC - mikktspace.c - - mikktspace.h -) - -set(LIB -) +if(WITH_TBB) + target_compile_definitions(bf_intern_mikktspace INTERFACE -DWITH_TBB) + target_include_directories(bf_intern_mikktspace INTERFACE ${TBB_INCLUDE_DIRS}) + target_link_libraries(bf_intern_mikktspace INTERFACE ${TBB_LIBRARIES}) +endif() -blender_add_lib(bf_intern_mikktspace "${SRC}" "${INC}" "${INC_SYS}" "${LIB}") +# CMake 3.19+ allows one to populate the interface library with +# source files to show in the IDE. +if(${CMAKE_VERSION} VERSION_GREATER_EQUAL "3.19") + set(SRC + mikk_atomic_hash_set.hh + mikk_float3.hh + mikk_util.hh + mikktspace.hh + ) + target_sources(bf_intern_mikktspace PRIVATE ${SRC}) + blender_source_group(bf_intern_mikktspace ${SRC}) +endif() diff --git a/intern/mikktspace/mikk_atomic_hash_set.hh b/intern/mikktspace/mikk_atomic_hash_set.hh new file mode 100644 index 00000000000..11d2a659966 --- /dev/null +++ b/intern/mikktspace/mikk_atomic_hash_set.hh @@ -0,0 +1,189 @@ +/* SPDX-License-Identifier: Apache-2.0 + * + * Original code: + * Copyright (c) Meta Platforms, Inc. and affiliates. + * + * Modifications: + * Copyright 2022 Blender Foundation. All rights reserved. + */ + +/* Simplified version of Folly's AtomicHashArray + * (https://github.com/facebook/folly/blob/main/folly/AtomicHashArray.h). + * + * Notable changes: + * - Standalone and header-only. + * - Behaves like a set, not like a map: There's no value type anymore, only keys. + * - Capacity check logic have been removed, the code assumes you know the required size in + * advance. + * - Custom allocator support has been removed. + * - Erase has been removed. + * - Find has been removed. + */ + +/** \file + * \ingroup mikktspace + */ + +#pragma once + +#ifdef _MSC_VER +# include <intrin.h> +#endif + +#include <atomic> +#include <type_traits> + +namespace mikk { + +struct AtomicHashSetLinearProbeFcn { + inline size_t operator()(size_t idx, size_t /* numProbes */, size_t capacity) const + { + idx += 1; // linear probing + + // Avoid modulus because it's slow + return LIKELY(idx < capacity) ? idx : (idx - capacity); + } +}; + +struct AtomicHashSetQuadraticProbeFcn { + inline size_t operator()(size_t idx, size_t numProbes, size_t capacity) const + { + idx += numProbes; // quadratic probing + + // Avoid modulus because it's slow + return LIKELY(idx < capacity) ? idx : (idx - capacity); + } +}; + +template<class KeyT, + bool isAtomic, + class KeyHash = std::hash<KeyT>, + class KeyEqual = std::equal_to<KeyT>, + class ProbeFcn = AtomicHashSetLinearProbeFcn> +class AtomicHashSet { + static_assert((std::is_convertible<KeyT, int32_t>::value || + std::is_convertible<KeyT, int64_t>::value || + std::is_convertible<KeyT, const void *>::value), + "You are trying to use AtomicHashSet with disallowed key " + "types. You must use atomically compare-and-swappable integer " + "keys, or a different container class."); + + public: + const size_t capacity_; + const KeyT kEmptyKey_; + + KeyHash hasher_; + KeyEqual equalityChecker_; + + private: + size_t kAnchorMask_; + /* When using a single thread, we can avoid overhead by not bothering with atomic cells. */ + typedef typename std::conditional<isAtomic, std::atomic<KeyT>, KeyT>::type cell_type; + std::vector<cell_type> cells_; + + public: + struct Config { + KeyT emptyKey; + double maxLoadFactor; + double growthFactor; + size_t capacity; // if positive, overrides maxLoadFactor + + // Cannot have constexpr ctor because some compilers rightly complain. + Config() : emptyKey((KeyT)-1), maxLoadFactor(0.8), growthFactor(-1), capacity(0) + { + } + }; + + /* Instead of a mess of arguments, we take a max size and a Config struct to + * simulate named ctor parameters. The Config struct has sensible defaults + * for everything, but is overloaded - if you specify a positive capacity, + * that will be used directly instead of computing it based on maxLoadFactor. + */ + AtomicHashSet(size_t maxSize, + KeyHash hasher = KeyHash(), + KeyEqual equalityChecker = KeyEqual(), + const Config &c = Config()) + : capacity_(size_t(double(maxSize) / c.maxLoadFactor) + 1), + kEmptyKey_(c.emptyKey), + hasher_(hasher), + equalityChecker_(equalityChecker), + cells_(capacity_) + { + /* Get next power of two. Could be done more effiently with builtin_clz, but this is not + * performance-critical. */ + kAnchorMask_ = 1; + while (kAnchorMask_ < capacity_) + kAnchorMask_ *= 2; + /* Get mask for lower bits. */ + kAnchorMask_ -= 1; + + /* Not great, but the best we can do to support both atomic and non-atomic cells + * since std::atomic doesn't have a copy constructor so cells_(capacity_, kEmptyKey_) + * in the initializer list won't work. */ + std::fill((KeyT *)cells_.data(), (KeyT *)cells_.data() + capacity_, kEmptyKey_); + } + + AtomicHashSet(const AtomicHashSet &) = delete; + AtomicHashSet &operator=(const AtomicHashSet &) = delete; + + ~AtomicHashSet() = default; + + /* Sequential specialization. */ + bool tryUpdateCell(KeyT *cell, KeyT &existingKey, KeyT newKey) + { + if (*cell == existingKey) { + *cell = newKey; + return true; + } + existingKey = *cell; + return false; + } + + /* Atomic specialization. */ + bool tryUpdateCell(std::atomic<KeyT> *cell, KeyT &existingKey, KeyT newKey) + { + return cell->compare_exchange_strong(existingKey, newKey, std::memory_order_acq_rel); + } + + std::pair<KeyT, bool> emplace(KeyT key) + { + size_t idx = keyToAnchorIdx(key); + size_t numProbes = 0; + for (;;) { + cell_type *cell = &cells_[idx]; + KeyT existingKey = kEmptyKey_; + /* Try to replace empty cell with our key. */ + if (tryUpdateCell(cell, existingKey, key)) { + /* Cell was empty, we're done. */ + return std::make_pair(key, true); + } + + /* Cell was not empty, check if the existing key is equal. */ + if (equalityChecker_(existingKey, key)) { + /* Found equal element, we're done. */ + return std::make_pair(existingKey, false); + } + + /* Continue to next cell according to probe strategy. */ + ++numProbes; + if (UNLIKELY(numProbes >= capacity_)) { + // probed every cell...fail + assert(false); + return std::make_pair(kEmptyKey_, false); + } + + idx = ProbeFcn()(idx, numProbes, capacity_); + } + } + + private: + inline size_t keyToAnchorIdx(const KeyT k) const + { + const size_t hashVal = hasher_(k); + const size_t probe = hashVal & kAnchorMask_; + return LIKELY(probe < capacity_) ? probe : hashVal % capacity_; + } + +}; // AtomicHashSet + +} // namespace mikk diff --git a/intern/mikktspace/mikk_float3.hh b/intern/mikktspace/mikk_float3.hh new file mode 100644 index 00000000000..1340aa08356 --- /dev/null +++ b/intern/mikktspace/mikk_float3.hh @@ -0,0 +1,128 @@ +/* SPDX-License-Identifier: Apache-2.0 */ + +/** \file + * \ingroup mikktspace + */ + +#pragma once + +#include <cmath> + +namespace mikk { + +struct float3 { + float x, y, z; + + float3() = default; + + float3(const float *ptr) : x{ptr[0]}, y{ptr[1]}, z{ptr[2]} + { + } + + float3(const float (*ptr)[3]) : float3((const float *)ptr) + { + } + + explicit float3(float value) : x(value), y(value), z(value) + { + } + + explicit float3(int value) : x((float)value), y((float)value), z((float)value) + { + } + + float3(float x_, float y_, float z_) : x{x_}, y{y_}, z{z_} + { + } + + static float3 zero() + { + return {0.0f, 0.0f, 0.0f}; + } + + friend float3 operator*(const float3 &a, float b) + { + return {a.x * b, a.y * b, a.z * b}; + } + + friend float3 operator*(float b, const float3 &a) + { + return {a.x * b, a.y * b, a.z * b}; + } + + friend float3 operator-(const float3 &a, const float3 &b) + { + return {a.x - b.x, a.y - b.y, a.z - b.z}; + } + + friend float3 operator-(const float3 &a) + { + return {-a.x, -a.y, -a.z}; + } + + friend bool operator==(const float3 &a, const float3 &b) + { + return a.x == b.x && a.y == b.y && a.z == b.z; + } + + float length_squared() const + { + return x * x + y * y + z * z; + } + + float length() const + { + return sqrt(length_squared()); + } + + static float distance(const float3 &a, const float3 &b) + { + return (a - b).length(); + } + + friend float3 operator+(const float3 &a, const float3 &b) + { + return {a.x + b.x, a.y + b.y, a.z + b.z}; + } + + void operator+=(const float3 &b) + { + this->x += b.x; + this->y += b.y; + this->z += b.z; + } + + friend float3 operator*(const float3 &a, const float3 &b) + { + return {a.x * b.x, a.y * b.y, a.z * b.z}; + } + + float3 normalize() const + { + const float len = length(); + return (len != 0.0f) ? *this * (1.0f / len) : *this; + } + + float reduce_add() const + { + return x + y + z; + } +}; + +inline float dot(const float3 &a, const float3 &b) +{ + return a.x * b.x + a.y * b.y + a.z * b.z; +} + +inline float distance(const float3 &a, const float3 &b) +{ + return float3::distance(a, b); +} + +/* Projects v onto the surface with normal n. */ +inline float3 project(const float3 &n, const float3 &v) +{ + return (v - n * dot(n, v)).normalize(); +} + +} // namespace mikk diff --git a/intern/mikktspace/mikk_util.hh b/intern/mikktspace/mikk_util.hh new file mode 100644 index 00000000000..4064d2af617 --- /dev/null +++ b/intern/mikktspace/mikk_util.hh @@ -0,0 +1,156 @@ +/* SPDX-License-Identifier: Apache-2.0 */ + +/** \file + * \ingroup mikktspace + */ + +#pragma once + +#include <cassert> +#include <cmath> + +#ifndef M_PI_F +# define M_PI_F (3.1415926535897932f) /* pi */ +#endif + +namespace mikk { + +inline bool not_zero(const float fX) +{ + return fabsf(fX) > FLT_MIN; +} + +/* Helpers for (un)packing a 2-bit vertex index and a 30-bit face index to one integer. */ +static uint pack_index(const uint face, const uint vert) +{ + assert((vert & 0x3) == vert); + return (face << 2) | (vert & 0x3); +} + +static void unpack_index(uint &face, uint &vert, const uint indexIn) +{ + vert = indexIn & 0x3; + face = indexIn >> 2; +} + +/* From intern/cycles/util/math_fast.h */ +inline float fast_acosf(float x) +{ + const float f = fabsf(x); + /* clamp and crush denormals. */ + const float m = (f < 1.0f) ? 1.0f - (1.0f - f) : 1.0f; + /* Based on http://www.pouet.net/topic.php?which=9132&page=2 + * 85% accurate (ulp 0) + * Examined 2130706434 values of acos: + * 15.2000597 avg ulp diff, 4492 max ulp, 4.51803e-05 max error // without "denormal crush" + * Examined 2130706434 values of acos: + * 15.2007108 avg ulp diff, 4492 max ulp, 4.51803e-05 max error // with "denormal crush" + */ + const float a = sqrtf(1.0f - m) * + (1.5707963267f + m * (-0.213300989f + m * (0.077980478f + m * -0.02164095f))); + return x < 0 ? M_PI_F - a : a; +} + +static uint rotl(uint x, uint k) +{ + return (x << k) | (x >> (32 - k)); +} + +static uint hash_uint3(uint kx, uint ky, uint kz) +{ + uint a, b, c; + a = b = c = 0xdeadbeef + (2 << 2) + 13; + + c += kz; + b += ky; + a += kx; + + c = (c ^ b) - rotl(b, 14); + a = (a ^ c) - rotl(c, 11); + b = (b ^ a) - rotl(a, 25); + c = (c ^ b) - rotl(b, 16); + + return c; +} + +static uint hash_uint3_fast(const uint x, const uint y, const uint z) +{ + return (x * 73856093) ^ (y * 19349663) ^ (z * 83492791); +} + +static uint float_as_uint(const float v) +{ + return *((uint *)(&v)); +} + +static float uint_as_float(const uint v) +{ + return *((float *)(&v)); +} + +static uint hash_float3_fast(const float x, const float y, const float z) +{ + return hash_uint3_fast(float_as_uint(x), float_as_uint(y), float_as_uint(z)); +} + +static uint hash_float3x3(const float3 &x, const float3 &y, const float3 &z) +{ + return hash_uint3(hash_float3_fast(x.x, x.y, x.z), + hash_float3_fast(y.x, y.y, y.z), + hash_float3_fast(z.x, z.y, z.z)); +} + +template<typename T, typename KeyGetter> +void radixsort(std::vector<T> &data, std::vector<T> &data2, KeyGetter getKey) +{ + typedef decltype(getKey(data[0])) key_t; + constexpr size_t datasize = sizeof(key_t); + static_assert(datasize % 2 == 0); + static_assert(std::is_integral<key_t>::value); + + uint bins[datasize][257] = {{0}}; + + /* Count number of elements per bin. */ + for (const T &item : data) { + key_t key = getKey(item); + for (uint pass = 0; pass < datasize; pass++) + bins[pass][((key >> (8 * pass)) & 0xff) + 1]++; + } + + /* Compute prefix sum to find position of each bin in the sorted array. */ + for (uint pass = 0; pass < datasize; pass++) { + for (uint i = 2; i < 256; i++) { + bins[pass][i] += bins[pass][i - 1]; + } + } + + int shift = 0; + for (uint pass = 0; pass < datasize; pass++, shift += 8) { + /* Insert the elements in their correct location based on their bin. */ + for (const T &item : data) { + uint pos = bins[pass][(getKey(item) >> shift) & 0xff]++; + data2[pos] = item; + } + + /* Swap arrays. */ + std::swap(data, data2); + } +} + +static void float_add_atomic(float *val, float add) +{ + /* Hacky, but atomic floats are only supported from C++20 onward. + * This works in practice since `std::atomic<uint32_t>` is really just an `uint32_t` in memory, + * so this cast lets us do a 32-bit CAS operation (which is used to build the atomic float + * operation) without needing any external libraries or compiler-specific builtins. */ + std::atomic<uint32_t> *atomic_val = reinterpret_cast<std::atomic<uint32_t> *>(val); + for (;;) { + uint32_t old_v = atomic_val->load(); + uint32_t new_v = float_as_uint(uint_as_float(old_v) + add); + if (atomic_val->compare_exchange_weak(old_v, new_v)) { + return; + } + } +} + +} // namespace mikk diff --git a/intern/mikktspace/mikktspace.c b/intern/mikktspace/mikktspace.c deleted file mode 100644 index e39ac4bb6ef..00000000000 --- a/intern/mikktspace/mikktspace.c +++ /dev/null @@ -1,1906 +0,0 @@ -/* SPDX-License-Identifier: Zlib - * Copyright 2011 by Morten S. Mikkelsen. */ - -/** \file - * \ingroup mikktspace - */ - -#include <assert.h> -#include <float.h> -#include <limits.h> -#include <math.h> -#include <stdio.h> -#include <stdlib.h> -#include <string.h> - -#include "mikktspace.h" - -#define TFALSE 0 -#define TTRUE 1 - -#ifndef M_PI -# define M_PI 3.1415926535897932384626433832795 -#endif - -#define INTERNAL_RND_SORT_SEED 39871946 - -#ifdef _MSC_VER -# define MIKK_INLINE static __forceinline -#else -# define MIKK_INLINE static inline __attribute__((always_inline)) __attribute__((unused)) -#endif - -// internal structure -typedef struct { - float x, y, z; -} SVec3; - -MIKK_INLINE tbool veq(const SVec3 v1, const SVec3 v2) -{ - return (v1.x == v2.x) && (v1.y == v2.y) && (v1.z == v2.z); -} - -MIKK_INLINE SVec3 vadd(const SVec3 v1, const SVec3 v2) -{ - SVec3 vRes; - - vRes.x = v1.x + v2.x; - vRes.y = v1.y + v2.y; - vRes.z = v1.z + v2.z; - - return vRes; -} - -MIKK_INLINE SVec3 vsub(const SVec3 v1, const SVec3 v2) -{ - SVec3 vRes; - - vRes.x = v1.x - v2.x; - vRes.y = v1.y - v2.y; - vRes.z = v1.z - v2.z; - - return vRes; -} - -MIKK_INLINE SVec3 vscale(const float fS, const SVec3 v) -{ - SVec3 vRes; - - vRes.x = fS * v.x; - vRes.y = fS * v.y; - vRes.z = fS * v.z; - - return vRes; -} - -MIKK_INLINE float LengthSquared(const SVec3 v) -{ - return v.x * v.x + v.y * v.y + v.z * v.z; -} - -MIKK_INLINE float Length(const SVec3 v) -{ - return sqrtf(LengthSquared(v)); -} - -#if 0 // UNUSED -MIKK_INLINE SVec3 Normalize(const SVec3 v) -{ - return vscale(1.0f / Length(v), v); -} -#endif - -MIKK_INLINE SVec3 NormalizeSafe(const SVec3 v) -{ - const float len = Length(v); - if (len != 0.0f) { - return vscale(1.0f / len, v); - } - else { - return v; - } -} - -MIKK_INLINE float vdot(const SVec3 v1, const SVec3 v2) -{ - return v1.x * v2.x + v1.y * v2.y + v1.z * v2.z; -} - -MIKK_INLINE tbool NotZero(const float fX) -{ - // could possibly use FLT_EPSILON instead - return fabsf(fX) > FLT_MIN; -} - -#if 0 // UNUSED -MIKK_INLINE tbool VNotZero(const SVec3 v) -{ - // might change this to an epsilon based test - return NotZero(v.x) || NotZero(v.y) || NotZero(v.z); -} -#endif - -// Shift operations in C are only defined for shift values which are -// not negative and smaller than sizeof(value) * CHAR_BIT. -// The mask, used with bitwise-and (&), prevents undefined behavior -// when the shift count is 0 or >= the width of unsigned int. -MIKK_INLINE unsigned int rotl(unsigned int value, unsigned int count) -{ - const unsigned int mask = CHAR_BIT * sizeof(value) - 1; - count &= mask; - return (value << count) | (value >> (-count & mask)); -} - -typedef struct { - int iNrFaces; - int *pTriMembers; -} SSubGroup; - -typedef struct { - int iNrFaces; - int *pFaceIndices; - int iVertexRepresentitive; - tbool bOrientPreservering; -} SGroup; - -// -#define MARK_DEGENERATE 1 -#define QUAD_ONE_DEGEN_TRI 2 -#define GROUP_WITH_ANY 4 -#define ORIENT_PRESERVING 8 - -typedef struct { - int FaceNeighbors[3]; - SGroup *AssignedGroup[3]; - - // normalized first order face derivatives - SVec3 vOs, vOt; - float fMagS, fMagT; // original magnitudes - - // determines if the current and the next triangle are a quad. - int iOrgFaceNumber; - int iFlag, iTSpacesOffs; - unsigned char vert_num[4]; -} STriInfo; - -typedef struct { - SVec3 vOs; - float fMagS; - SVec3 vOt; - float fMagT; - int iCounter; // this is to average back into quads. - tbool bOrient; -} STSpace; - -static int GenerateInitialVerticesIndexList(STriInfo pTriInfos[], - int piTriList_out[], - const SMikkTSpaceContext *pContext, - const int iNrTrianglesIn); -static void GenerateSharedVerticesIndexList(int piTriList_in_and_out[], - const SMikkTSpaceContext *pContext, - const int iNrTrianglesIn); -static void InitTriInfo(STriInfo pTriInfos[], - const int piTriListIn[], - const SMikkTSpaceContext *pContext, - const int iNrTrianglesIn); -static int Build4RuleGroups(STriInfo pTriInfos[], - SGroup pGroups[], - int piGroupTrianglesBuffer[], - const int piTriListIn[], - const int iNrTrianglesIn); -static tbool GenerateTSpaces(STSpace psTspace[], - const STriInfo pTriInfos[], - const SGroup pGroups[], - const int iNrActiveGroups, - const int piTriListIn[], - const float fThresCos, - const SMikkTSpaceContext *pContext); - -MIKK_INLINE int MakeIndex(const int iFace, const int iVert) -{ - assert(iVert >= 0 && iVert < 4 && iFace >= 0); - return (iFace << 2) | (iVert & 0x3); -} - -MIKK_INLINE void IndexToData(int *piFace, int *piVert, const int iIndexIn) -{ - piVert[0] = iIndexIn & 0x3; - piFace[0] = iIndexIn >> 2; -} - -static STSpace AvgTSpace(const STSpace *pTS0, const STSpace *pTS1) -{ - STSpace ts_res; - - // this if is important. Due to floating point precision - // averaging when ts0==ts1 will cause a slight difference - // which results in tangent space splits later on - if (pTS0->fMagS == pTS1->fMagS && pTS0->fMagT == pTS1->fMagT && veq(pTS0->vOs, pTS1->vOs) && - veq(pTS0->vOt, pTS1->vOt)) { - ts_res.fMagS = pTS0->fMagS; - ts_res.fMagT = pTS0->fMagT; - ts_res.vOs = pTS0->vOs; - ts_res.vOt = pTS0->vOt; - } - else { - ts_res.fMagS = 0.5f * (pTS0->fMagS + pTS1->fMagS); - ts_res.fMagT = 0.5f * (pTS0->fMagT + pTS1->fMagT); - ts_res.vOs = vadd(pTS0->vOs, pTS1->vOs); - ts_res.vOt = vadd(pTS0->vOt, pTS1->vOt); - ts_res.vOs = NormalizeSafe(ts_res.vOs); - ts_res.vOt = NormalizeSafe(ts_res.vOt); - } - - return ts_res; -} - -MIKK_INLINE SVec3 GetPosition(const SMikkTSpaceContext *pContext, const int index); -MIKK_INLINE SVec3 GetNormal(const SMikkTSpaceContext *pContext, const int index); -MIKK_INLINE SVec3 GetTexCoord(const SMikkTSpaceContext *pContext, const int index); - -// degen triangles -static void DegenPrologue(STriInfo pTriInfos[], - int piTriList_out[], - const int iNrTrianglesIn, - const int iTotTris); -static void DegenEpilogue(STSpace psTspace[], - STriInfo pTriInfos[], - int piTriListIn[], - const SMikkTSpaceContext *pContext, - const int iNrTrianglesIn, - const int iTotTris); - -tbool genTangSpaceDefault(const SMikkTSpaceContext *pContext) -{ - return genTangSpace(pContext, 180.0f); -} - -tbool genTangSpace(const SMikkTSpaceContext *pContext, const float fAngularThreshold) -{ - // count nr_triangles - int *piTriListIn = NULL, *piGroupTrianglesBuffer = NULL; - STriInfo *pTriInfos = NULL; - SGroup *pGroups = NULL; - STSpace *psTspace = NULL; - int iNrTrianglesIn = 0, f = 0, t = 0, i = 0; - int iNrTSPaces = 0, iTotTris = 0, iDegenTriangles = 0, iNrMaxGroups = 0; - int iNrActiveGroups = 0, index = 0; - const int iNrFaces = pContext->m_pInterface->m_getNumFaces(pContext); - tbool bRes = TFALSE; - const float fThresCos = cosf((fAngularThreshold * (float)M_PI) / 180.0f); - - // verify all call-backs have been set - if (pContext->m_pInterface->m_getNumFaces == NULL || - pContext->m_pInterface->m_getNumVerticesOfFace == NULL || - pContext->m_pInterface->m_getPosition == NULL || - pContext->m_pInterface->m_getNormal == NULL || pContext->m_pInterface->m_getTexCoord == NULL) - return TFALSE; - - // count triangles on supported faces - for (f = 0; f < iNrFaces; f++) { - const int verts = pContext->m_pInterface->m_getNumVerticesOfFace(pContext, f); - if (verts == 3) - ++iNrTrianglesIn; - else if (verts == 4) - iNrTrianglesIn += 2; - } - if (iNrTrianglesIn <= 0) - return TFALSE; - - // allocate memory for an index list - piTriListIn = (int *)malloc(sizeof(int[3]) * iNrTrianglesIn); - pTriInfos = (STriInfo *)malloc(sizeof(STriInfo) * iNrTrianglesIn); - if (piTriListIn == NULL || pTriInfos == NULL) { - if (piTriListIn != NULL) - free(piTriListIn); - if (pTriInfos != NULL) - free(pTriInfos); - return TFALSE; - } - - // make an initial triangle --> face index list - iNrTSPaces = GenerateInitialVerticesIndexList(pTriInfos, piTriListIn, pContext, iNrTrianglesIn); - - // make a welded index list of identical positions and attributes (pos, norm, texc) - // printf("gen welded index list begin\n"); - GenerateSharedVerticesIndexList(piTriListIn, pContext, iNrTrianglesIn); - // printf("gen welded index list end\n"); - - // Mark all degenerate triangles - iTotTris = iNrTrianglesIn; - iDegenTriangles = 0; - for (t = 0; t < iTotTris; t++) { - const int i0 = piTriListIn[t * 3 + 0]; - const int i1 = piTriListIn[t * 3 + 1]; - const int i2 = piTriListIn[t * 3 + 2]; - const SVec3 p0 = GetPosition(pContext, i0); - const SVec3 p1 = GetPosition(pContext, i1); - const SVec3 p2 = GetPosition(pContext, i2); - if (veq(p0, p1) || veq(p0, p2) || veq(p1, p2)) // degenerate - { - pTriInfos[t].iFlag |= MARK_DEGENERATE; - ++iDegenTriangles; - } - } - iNrTrianglesIn = iTotTris - iDegenTriangles; - - // mark all triangle pairs that belong to a quad with only one - // good triangle. These need special treatment in DegenEpilogue(). - // Additionally, move all good triangles to the start of - // pTriInfos[] and piTriListIn[] without changing order and - // put the degenerate triangles last. - DegenPrologue(pTriInfos, piTriListIn, iNrTrianglesIn, iTotTris); - - // evaluate triangle level attributes and neighbor list - // printf("gen neighbors list begin\n"); - InitTriInfo(pTriInfos, piTriListIn, pContext, iNrTrianglesIn); - // printf("gen neighbors list end\n"); - - // based on the 4 rules, identify groups based on connectivity - iNrMaxGroups = iNrTrianglesIn * 3; - pGroups = (SGroup *)malloc(sizeof(SGroup) * iNrMaxGroups); - piGroupTrianglesBuffer = (int *)malloc(sizeof(int[3]) * iNrTrianglesIn); - if (pGroups == NULL || piGroupTrianglesBuffer == NULL) { - if (pGroups != NULL) - free(pGroups); - if (piGroupTrianglesBuffer != NULL) - free(piGroupTrianglesBuffer); - free(piTriListIn); - free(pTriInfos); - return TFALSE; - } - // printf("gen 4rule groups begin\n"); - iNrActiveGroups = Build4RuleGroups( - pTriInfos, pGroups, piGroupTrianglesBuffer, piTriListIn, iNrTrianglesIn); - // printf("gen 4rule groups end\n"); - - // - - psTspace = (STSpace *)malloc(sizeof(STSpace) * iNrTSPaces); - if (psTspace == NULL) { - free(piTriListIn); - free(pTriInfos); - free(pGroups); - free(piGroupTrianglesBuffer); - return TFALSE; - } - memset(psTspace, 0, sizeof(STSpace) * iNrTSPaces); - for (t = 0; t < iNrTSPaces; t++) { - psTspace[t].vOs.x = 1.0f; - psTspace[t].vOs.y = 0.0f; - psTspace[t].vOs.z = 0.0f; - psTspace[t].fMagS = 1.0f; - psTspace[t].vOt.x = 0.0f; - psTspace[t].vOt.y = 1.0f; - psTspace[t].vOt.z = 0.0f; - psTspace[t].fMagT = 1.0f; - } - - // make tspaces, each group is split up into subgroups if necessary - // based on fAngularThreshold. Finally a tangent space is made for - // every resulting subgroup - // printf("gen tspaces begin\n"); - bRes = GenerateTSpaces( - psTspace, pTriInfos, pGroups, iNrActiveGroups, piTriListIn, fThresCos, pContext); - // printf("gen tspaces end\n"); - - // clean up - free(pGroups); - free(piGroupTrianglesBuffer); - - if (!bRes) // if an allocation in GenerateTSpaces() failed - { - // clean up and return false - free(pTriInfos); - free(piTriListIn); - free(psTspace); - return TFALSE; - } - - // degenerate quads with one good triangle will be fixed by copying a space from - // the good triangle to the coinciding vertex. - // all other degenerate triangles will just copy a space from any good triangle - // with the same welded index in piTriListIn[]. - DegenEpilogue(psTspace, pTriInfos, piTriListIn, pContext, iNrTrianglesIn, iTotTris); - - free(pTriInfos); - free(piTriListIn); - - index = 0; - for (f = 0; f < iNrFaces; f++) { - const int verts = pContext->m_pInterface->m_getNumVerticesOfFace(pContext, f); - if (verts != 3 && verts != 4) { - continue; - } - - // I've decided to let degenerate triangles and group-with-anythings - // vary between left/right hand coordinate systems at the vertices. - // All healthy triangles on the other hand are built to always be either or. -#if 0 - // force the coordinate system orientation to be uniform for every face. - // (this is already the case for good triangles but not for - // degenerate ones and those with bGroupWithAnything==true) - bool bOrient = psTspace[index].bOrient; - if (psTspace[index].iCounter == 0) // tspace was not derived from a group - { - // look for a space created in GenerateTSpaces() by iCounter>0 - bool bNotFound = true; - int i=1; - while (i<verts && bNotFound) - { - if (psTspace[index+i].iCounter > 0) bNotFound=false; - else ++i; - } - if (!bNotFound) bOrient = psTspace[index+i].bOrient; - } -#endif - - // set data - for (i = 0; i < verts; i++) { - const STSpace *pTSpace = &psTspace[index]; - float tang[] = {pTSpace->vOs.x, pTSpace->vOs.y, pTSpace->vOs.z}; - float bitang[] = {pTSpace->vOt.x, pTSpace->vOt.y, pTSpace->vOt.z}; - if (pContext->m_pInterface->m_setTSpace != NULL) - pContext->m_pInterface->m_setTSpace( - pContext, tang, bitang, pTSpace->fMagS, pTSpace->fMagT, pTSpace->bOrient, f, i); - if (pContext->m_pInterface->m_setTSpaceBasic != NULL) - pContext->m_pInterface->m_setTSpaceBasic( - pContext, tang, pTSpace->bOrient == TTRUE ? 1.0f : (-1.0f), f, i); - - ++index; - } - } - - free(psTspace); - - return TTRUE; -} - -/////////////////////////////////////////////////////////////////////////////////////////////////// - -static void GenerateSharedVerticesIndexListSlow(int piTriList_in_and_out[], - const SMikkTSpaceContext *pContext, - const int iNrTrianglesIn); - -typedef unsigned int uint; - -static uint float_as_uint(const float v) -{ - return *((uint *)(&v)); -} - -#define HASH(x, y, z) (((x)*73856093) ^ ((y)*19349663) ^ ((z)*83492791)) -#define HASH_F(x, y, z) HASH(float_as_uint(x), float_as_uint(y), float_as_uint(z)) - -/* Sort comp and data based on comp. - * comp2 and data2 are used as temporary storage. */ -static void radixsort_pair(uint *comp, int *data, uint *comp2, int *data2, int n) -{ - int shift = 0; - for (int pass = 0; pass < 4; pass++, shift += 8) { - int bins[257] = {0}; - /* Count number of elements per bin. */ - for (int i = 0; i < n; i++) { - bins[((comp[i] >> shift) & 0xff) + 1]++; - } - /* Compute prefix sum to find position of each bin in the sorted array. */ - for (int i = 2; i < 256; i++) { - bins[i] += bins[i - 1]; - } - /* Insert the elements in their correct location based on their bin. */ - for (int i = 0; i < n; i++) { - int pos = bins[(comp[i] >> shift) & 0xff]++; - comp2[pos] = comp[i]; - data2[pos] = data[i]; - } - - /* Swap arrays. */ - int *tmpdata = data; - data = data2; - data2 = tmpdata; - uint *tmpcomp = comp; - comp = comp2; - comp2 = tmpcomp; - } -} - -/* Merge identical vertices. - * To find vertices with identical position, normal and texcoord, we calculate a hash of the 9 - * values. Then, by sorting based on that hash, identical elements (having identical hashes) will - * be moved next to each other. Since there might be hash collisions, the elements of each block - * are then compared with each other and duplicates are merged. - */ -static void GenerateSharedVerticesIndexList(int piTriList_in_and_out[], - const SMikkTSpaceContext *pContext, - const int iNrTrianglesIn) -{ - int numVertices = iNrTrianglesIn * 3; - - uint *hashes = (uint *)malloc(sizeof(uint) * numVertices); - int *indices = (int *)malloc(sizeof(int) * numVertices); - uint *temp_hashes = (uint *)malloc(sizeof(uint) * numVertices); - int *temp_indices = (int *)malloc(sizeof(int) * numVertices); - - if (hashes == NULL || indices == NULL || temp_hashes == NULL || temp_indices == NULL) { - free(hashes); - free(indices); - free(temp_hashes); - free(temp_indices); - - GenerateSharedVerticesIndexListSlow(piTriList_in_and_out, pContext, iNrTrianglesIn); - return; - } - - for (int i = 0; i < numVertices; i++) { - const int index = piTriList_in_and_out[i]; - - const SVec3 vP = GetPosition(pContext, index); - const uint hashP = HASH_F(vP.x, vP.y, vP.z); - - const SVec3 vN = GetNormal(pContext, index); - const uint hashN = HASH_F(vN.x, vN.y, vN.z); - - const SVec3 vT = GetTexCoord(pContext, index); - const uint hashT = HASH_F(vT.x, vT.y, vT.z); - - hashes[i] = HASH(hashP, hashN, hashT); - indices[i] = i; - } - - radixsort_pair(hashes, indices, temp_hashes, temp_indices, numVertices); - - free(temp_hashes); - free(temp_indices); - - /* Process blocks of vertices with the same hash. - * Vertices in the block might still be separate, but we know for sure that - * vertices in different blocks will never be identical. */ - int blockstart = 0; - while (blockstart < numVertices) { - /* Find end of this block (exclusive). */ - uint hash = hashes[blockstart]; - int blockend = blockstart + 1; - for (; blockend < numVertices; blockend++) { - if (hashes[blockend] != hash) - break; - } - - /* If there's only one vertex with this hash, we don't have anything to compare. */ - if (blockend > blockstart + 1) { - for (int i = blockstart; i < blockend; i++) { - int index1 = piTriList_in_and_out[indices[i]]; - const SVec3 vP = GetPosition(pContext, index1); - const SVec3 vN = GetNormal(pContext, index1); - const SVec3 vT = GetTexCoord(pContext, index1); - for (int i2 = i + 1; i2 < blockend; i2++) { - int index2 = piTriList_in_and_out[indices[i2]]; - if (index1 == index2) - continue; - - if (veq(vP, GetPosition(pContext, index2)) && veq(vN, GetNormal(pContext, index2)) && - veq(vT, GetTexCoord(pContext, index2))) { - piTriList_in_and_out[indices[i2]] = index1; - /* Once i2>i has been identified as a duplicate, we can stop since any - * i3>i2>i that is a duplicate of i (and therefore also i2) will also be - * compared to i2 and therefore be identified there anyways. */ - break; - } - } - } - } - - /* Advance to next block. */ - blockstart = blockend; - } - - free(hashes); - free(indices); -} - -static void GenerateSharedVerticesIndexListSlow(int piTriList_in_and_out[], - const SMikkTSpaceContext *pContext, - const int iNrTrianglesIn) -{ - int iNumUniqueVerts = 0, t = 0, i = 0; - for (t = 0; t < iNrTrianglesIn; t++) { - for (i = 0; i < 3; i++) { - const int offs = t * 3 + i; - const int index = piTriList_in_and_out[offs]; - - const SVec3 vP = GetPosition(pContext, index); - const SVec3 vN = GetNormal(pContext, index); - const SVec3 vT = GetTexCoord(pContext, index); - - tbool bFound = TFALSE; - int t2 = 0, index2rec = -1; - while (!bFound && t2 <= t) { - int j = 0; - while (!bFound && j < 3) { - const int index2 = piTriList_in_and_out[t2 * 3 + j]; - const SVec3 vP2 = GetPosition(pContext, index2); - const SVec3 vN2 = GetNormal(pContext, index2); - const SVec3 vT2 = GetTexCoord(pContext, index2); - - if (veq(vP, vP2) && veq(vN, vN2) && veq(vT, vT2)) - bFound = TTRUE; - else - ++j; - } - if (!bFound) - ++t2; - } - - assert(bFound); - // if we found our own - if (index2rec == index) { - ++iNumUniqueVerts; - } - - piTriList_in_and_out[offs] = index2rec; - } - } -} - -static int GenerateInitialVerticesIndexList(STriInfo pTriInfos[], - int piTriList_out[], - const SMikkTSpaceContext *pContext, - const int iNrTrianglesIn) -{ - int iTSpacesOffs = 0, f = 0, t = 0; - int iDstTriIndex = 0; - const int iNrFaces = pContext->m_pInterface->m_getNumFaces(pContext); - for (f = 0; f < iNrFaces; f++) { - const int verts = pContext->m_pInterface->m_getNumVerticesOfFace(pContext, f); - if (verts != 3 && verts != 4) - continue; - - pTriInfos[iDstTriIndex].iOrgFaceNumber = f; - pTriInfos[iDstTriIndex].iTSpacesOffs = iTSpacesOffs; - - if (verts == 3) { - unsigned char *pVerts = pTriInfos[iDstTriIndex].vert_num; - pVerts[0] = 0; - pVerts[1] = 1; - pVerts[2] = 2; - piTriList_out[iDstTriIndex * 3 + 0] = MakeIndex(f, 0); - piTriList_out[iDstTriIndex * 3 + 1] = MakeIndex(f, 1); - piTriList_out[iDstTriIndex * 3 + 2] = MakeIndex(f, 2); - ++iDstTriIndex; // next - } - else { - { - pTriInfos[iDstTriIndex + 1].iOrgFaceNumber = f; - pTriInfos[iDstTriIndex + 1].iTSpacesOffs = iTSpacesOffs; - } - - { - // need an order independent way to evaluate - // tspace on quads. This is done by splitting - // along the shortest diagonal. - const int i0 = MakeIndex(f, 0); - const int i1 = MakeIndex(f, 1); - const int i2 = MakeIndex(f, 2); - const int i3 = MakeIndex(f, 3); - const SVec3 T0 = GetTexCoord(pContext, i0); - const SVec3 T1 = GetTexCoord(pContext, i1); - const SVec3 T2 = GetTexCoord(pContext, i2); - const SVec3 T3 = GetTexCoord(pContext, i3); - const float distSQ_02 = LengthSquared(vsub(T2, T0)); - const float distSQ_13 = LengthSquared(vsub(T3, T1)); - tbool bQuadDiagIs_02; - if (distSQ_02 < distSQ_13) - bQuadDiagIs_02 = TTRUE; - else if (distSQ_13 < distSQ_02) - bQuadDiagIs_02 = TFALSE; - else { - const SVec3 P0 = GetPosition(pContext, i0); - const SVec3 P1 = GetPosition(pContext, i1); - const SVec3 P2 = GetPosition(pContext, i2); - const SVec3 P3 = GetPosition(pContext, i3); - const float distSQ_02 = LengthSquared(vsub(P2, P0)); - const float distSQ_13 = LengthSquared(vsub(P3, P1)); - - bQuadDiagIs_02 = distSQ_13 < distSQ_02 ? TFALSE : TTRUE; - } - - if (bQuadDiagIs_02) { - { - unsigned char *pVerts_A = pTriInfos[iDstTriIndex].vert_num; - pVerts_A[0] = 0; - pVerts_A[1] = 1; - pVerts_A[2] = 2; - } - piTriList_out[iDstTriIndex * 3 + 0] = i0; - piTriList_out[iDstTriIndex * 3 + 1] = i1; - piTriList_out[iDstTriIndex * 3 + 2] = i2; - ++iDstTriIndex; // next - { - unsigned char *pVerts_B = pTriInfos[iDstTriIndex].vert_num; - pVerts_B[0] = 0; - pVerts_B[1] = 2; - pVerts_B[2] = 3; - } - piTriList_out[iDstTriIndex * 3 + 0] = i0; - piTriList_out[iDstTriIndex * 3 + 1] = i2; - piTriList_out[iDstTriIndex * 3 + 2] = i3; - ++iDstTriIndex; // next - } - else { - { - unsigned char *pVerts_A = pTriInfos[iDstTriIndex].vert_num; - pVerts_A[0] = 0; - pVerts_A[1] = 1; - pVerts_A[2] = 3; - } - piTriList_out[iDstTriIndex * 3 + 0] = i0; - piTriList_out[iDstTriIndex * 3 + 1] = i1; - piTriList_out[iDstTriIndex * 3 + 2] = i3; - ++iDstTriIndex; // next - { - unsigned char *pVerts_B = pTriInfos[iDstTriIndex].vert_num; - pVerts_B[0] = 1; - pVerts_B[1] = 2; - pVerts_B[2] = 3; - } - piTriList_out[iDstTriIndex * 3 + 0] = i1; - piTriList_out[iDstTriIndex * 3 + 1] = i2; - piTriList_out[iDstTriIndex * 3 + 2] = i3; - ++iDstTriIndex; // next - } - } - } - - iTSpacesOffs += verts; - assert(iDstTriIndex <= iNrTrianglesIn); - } - - for (t = 0; t < iNrTrianglesIn; t++) - pTriInfos[t].iFlag = 0; - - // return total amount of tspaces - return iTSpacesOffs; -} - -MIKK_INLINE SVec3 GetPosition(const SMikkTSpaceContext *pContext, const int index) -{ - int iF, iI; - SVec3 res; - float pos[3]; - IndexToData(&iF, &iI, index); - pContext->m_pInterface->m_getPosition(pContext, pos, iF, iI); - res.x = pos[0]; - res.y = pos[1]; - res.z = pos[2]; - return res; -} - -MIKK_INLINE SVec3 GetNormal(const SMikkTSpaceContext *pContext, const int index) -{ - int iF, iI; - SVec3 res; - float norm[3]; - IndexToData(&iF, &iI, index); - pContext->m_pInterface->m_getNormal(pContext, norm, iF, iI); - res.x = norm[0]; - res.y = norm[1]; - res.z = norm[2]; - return res; -} - -MIKK_INLINE SVec3 GetTexCoord(const SMikkTSpaceContext *pContext, const int index) -{ - int iF, iI; - SVec3 res; - float texc[2]; - IndexToData(&iF, &iI, index); - pContext->m_pInterface->m_getTexCoord(pContext, texc, iF, iI); - res.x = texc[0]; - res.y = texc[1]; - res.z = 1.0f; - return res; -} - -/////////////////////////////////////////////////////////////////////////////////////////////////// -/////////////////////////////////////////////////////////////////////////////////////////////////// - -typedef union { - struct { - int i0, i1, f; - }; - int array[3]; -} SEdge; - -static void BuildNeighborsFast(STriInfo pTriInfos[], - SEdge *pEdges, - const int piTriListIn[], - const int iNrTrianglesIn); -static void BuildNeighborsSlow(STriInfo pTriInfos[], - const int piTriListIn[], - const int iNrTrianglesIn); - -// returns the texture area times 2 -static float CalcTexArea(const SMikkTSpaceContext *pContext, const int indices[]) -{ - const SVec3 t1 = GetTexCoord(pContext, indices[0]); - const SVec3 t2 = GetTexCoord(pContext, indices[1]); - const SVec3 t3 = GetTexCoord(pContext, indices[2]); - - const float t21x = t2.x - t1.x; - const float t21y = t2.y - t1.y; - const float t31x = t3.x - t1.x; - const float t31y = t3.y - t1.y; - - const float fSignedAreaSTx2 = t21x * t31y - t21y * t31x; - - return fSignedAreaSTx2 < 0 ? (-fSignedAreaSTx2) : fSignedAreaSTx2; -} - -static void InitTriInfo(STriInfo pTriInfos[], - const int piTriListIn[], - const SMikkTSpaceContext *pContext, - const int iNrTrianglesIn) -{ - int f = 0, i = 0, t = 0; - // pTriInfos[f].iFlag is cleared in GenerateInitialVerticesIndexList() - // which is called before this function. - - // generate neighbor info list - for (f = 0; f < iNrTrianglesIn; f++) - for (i = 0; i < 3; i++) { - pTriInfos[f].FaceNeighbors[i] = -1; - pTriInfos[f].AssignedGroup[i] = NULL; - - pTriInfos[f].vOs.x = 0.0f; - pTriInfos[f].vOs.y = 0.0f; - pTriInfos[f].vOs.z = 0.0f; - pTriInfos[f].vOt.x = 0.0f; - pTriInfos[f].vOt.y = 0.0f; - pTriInfos[f].vOt.z = 0.0f; - pTriInfos[f].fMagS = 0; - pTriInfos[f].fMagT = 0; - - // assumed bad - pTriInfos[f].iFlag |= GROUP_WITH_ANY; - } - - // evaluate first order derivatives - for (f = 0; f < iNrTrianglesIn; f++) { - // initial values - const SVec3 v1 = GetPosition(pContext, piTriListIn[f * 3 + 0]); - const SVec3 v2 = GetPosition(pContext, piTriListIn[f * 3 + 1]); - const SVec3 v3 = GetPosition(pContext, piTriListIn[f * 3 + 2]); - const SVec3 t1 = GetTexCoord(pContext, piTriListIn[f * 3 + 0]); - const SVec3 t2 = GetTexCoord(pContext, piTriListIn[f * 3 + 1]); - const SVec3 t3 = GetTexCoord(pContext, piTriListIn[f * 3 + 2]); - - const float t21x = t2.x - t1.x; - const float t21y = t2.y - t1.y; - const float t31x = t3.x - t1.x; - const float t31y = t3.y - t1.y; - const SVec3 d1 = vsub(v2, v1); - const SVec3 d2 = vsub(v3, v1); - - const float fSignedAreaSTx2 = t21x * t31y - t21y * t31x; - // assert(fSignedAreaSTx2!=0); - SVec3 vOs = vsub(vscale(t31y, d1), vscale(t21y, d2)); // eq 18 - SVec3 vOt = vadd(vscale(-t31x, d1), vscale(t21x, d2)); // eq 19 - - pTriInfos[f].iFlag |= (fSignedAreaSTx2 > 0 ? ORIENT_PRESERVING : 0); - - if (NotZero(fSignedAreaSTx2)) { - const float fAbsArea = fabsf(fSignedAreaSTx2); - const float fLenOs = Length(vOs); - const float fLenOt = Length(vOt); - const float fS = (pTriInfos[f].iFlag & ORIENT_PRESERVING) == 0 ? (-1.0f) : 1.0f; - if (NotZero(fLenOs)) - pTriInfos[f].vOs = vscale(fS / fLenOs, vOs); - if (NotZero(fLenOt)) - pTriInfos[f].vOt = vscale(fS / fLenOt, vOt); - - // evaluate magnitudes prior to normalization of vOs and vOt - pTriInfos[f].fMagS = fLenOs / fAbsArea; - pTriInfos[f].fMagT = fLenOt / fAbsArea; - - // if this is a good triangle - if (NotZero(pTriInfos[f].fMagS) && NotZero(pTriInfos[f].fMagT)) - pTriInfos[f].iFlag &= (~GROUP_WITH_ANY); - } - } - - // force otherwise healthy quads to a fixed orientation - while (t < (iNrTrianglesIn - 1)) { - const int iFO_a = pTriInfos[t].iOrgFaceNumber; - const int iFO_b = pTriInfos[t + 1].iOrgFaceNumber; - if (iFO_a == iFO_b) // this is a quad - { - const tbool bIsDeg_a = (pTriInfos[t].iFlag & MARK_DEGENERATE) != 0 ? TTRUE : TFALSE; - const tbool bIsDeg_b = (pTriInfos[t + 1].iFlag & MARK_DEGENERATE) != 0 ? TTRUE : TFALSE; - - // bad triangles should already have been removed by - // DegenPrologue(), but just in case check bIsDeg_a and bIsDeg_a are false - if ((bIsDeg_a || bIsDeg_b) == TFALSE) { - const tbool bOrientA = (pTriInfos[t].iFlag & ORIENT_PRESERVING) != 0 ? TTRUE : TFALSE; - const tbool bOrientB = (pTriInfos[t + 1].iFlag & ORIENT_PRESERVING) != 0 ? TTRUE : TFALSE; - // if this happens the quad has extremely bad mapping!! - if (bOrientA != bOrientB) { - // printf("found quad with bad mapping\n"); - tbool bChooseOrientFirstTri = TFALSE; - if ((pTriInfos[t + 1].iFlag & GROUP_WITH_ANY) != 0) - bChooseOrientFirstTri = TTRUE; - else if (CalcTexArea(pContext, &piTriListIn[t * 3 + 0]) >= - CalcTexArea(pContext, &piTriListIn[(t + 1) * 3 + 0])) - bChooseOrientFirstTri = TTRUE; - - // force match - { - const int t0 = bChooseOrientFirstTri ? t : (t + 1); - const int t1 = bChooseOrientFirstTri ? (t + 1) : t; - pTriInfos[t1].iFlag &= (~ORIENT_PRESERVING); // clear first - pTriInfos[t1].iFlag |= (pTriInfos[t0].iFlag & ORIENT_PRESERVING); // copy bit - } - } - } - t += 2; - } - else - ++t; - } - - // match up edge pairs - { - SEdge *pEdges = (SEdge *)malloc(sizeof(SEdge[3]) * iNrTrianglesIn); - if (pEdges == NULL) - BuildNeighborsSlow(pTriInfos, piTriListIn, iNrTrianglesIn); - else { - BuildNeighborsFast(pTriInfos, pEdges, piTriListIn, iNrTrianglesIn); - - free(pEdges); - } - } -} - -/////////////////////////////////////////////////////////////////////////////////////////////////// -/////////////////////////////////////////////////////////////////////////////////////////////////// - -static tbool AssignRecur(const int piTriListIn[], - STriInfo psTriInfos[], - const int iMyTriIndex, - SGroup *pGroup); -MIKK_INLINE void AddTriToGroup(SGroup *pGroup, const int iTriIndex); - -static int Build4RuleGroups(STriInfo pTriInfos[], - SGroup pGroups[], - int piGroupTrianglesBuffer[], - const int piTriListIn[], - const int iNrTrianglesIn) -{ - const int iNrMaxGroups = iNrTrianglesIn * 3; - int iNrActiveGroups = 0; - int iOffset = 0, f = 0, i = 0; - (void)iNrMaxGroups; /* quiet warnings in non debug mode */ - for (f = 0; f < iNrTrianglesIn; f++) { - for (i = 0; i < 3; i++) { - // if not assigned to a group - if ((pTriInfos[f].iFlag & GROUP_WITH_ANY) == 0 && pTriInfos[f].AssignedGroup[i] == NULL) { - tbool bOrPre; - int neigh_indexL, neigh_indexR; - const int vert_index = piTriListIn[f * 3 + i]; - assert(iNrActiveGroups < iNrMaxGroups); - pTriInfos[f].AssignedGroup[i] = &pGroups[iNrActiveGroups]; - pTriInfos[f].AssignedGroup[i]->iVertexRepresentitive = vert_index; - pTriInfos[f].AssignedGroup[i]->bOrientPreservering = (pTriInfos[f].iFlag & - ORIENT_PRESERVING) != 0; - pTriInfos[f].AssignedGroup[i]->iNrFaces = 0; - pTriInfos[f].AssignedGroup[i]->pFaceIndices = &piGroupTrianglesBuffer[iOffset]; - ++iNrActiveGroups; - - AddTriToGroup(pTriInfos[f].AssignedGroup[i], f); - bOrPre = (pTriInfos[f].iFlag & ORIENT_PRESERVING) != 0 ? TTRUE : TFALSE; - neigh_indexL = pTriInfos[f].FaceNeighbors[i]; - neigh_indexR = pTriInfos[f].FaceNeighbors[i > 0 ? (i - 1) : 2]; - if (neigh_indexL >= 0) // neighbor - { - const tbool bAnswer = AssignRecur( - piTriListIn, pTriInfos, neigh_indexL, pTriInfos[f].AssignedGroup[i]); - - const tbool bOrPre2 = (pTriInfos[neigh_indexL].iFlag & ORIENT_PRESERVING) != 0 ? TTRUE : - TFALSE; - const tbool bDiff = bOrPre != bOrPre2 ? TTRUE : TFALSE; - assert(bAnswer || bDiff); - (void)bAnswer, (void)bDiff; /* quiet warnings in non debug mode */ - } - if (neigh_indexR >= 0) // neighbor - { - const tbool bAnswer = AssignRecur( - piTriListIn, pTriInfos, neigh_indexR, pTriInfos[f].AssignedGroup[i]); - - const tbool bOrPre2 = (pTriInfos[neigh_indexR].iFlag & ORIENT_PRESERVING) != 0 ? TTRUE : - TFALSE; - const tbool bDiff = bOrPre != bOrPre2 ? TTRUE : TFALSE; - assert(bAnswer || bDiff); - (void)bAnswer, (void)bDiff; /* quiet warnings in non debug mode */ - } - - // update offset - iOffset += pTriInfos[f].AssignedGroup[i]->iNrFaces; - // since the groups are disjoint a triangle can never - // belong to more than 3 groups. Subsequently something - // is completely screwed if this assertion ever hits. - assert(iOffset <= iNrMaxGroups); - } - } - } - - return iNrActiveGroups; -} - -MIKK_INLINE void AddTriToGroup(SGroup *pGroup, const int iTriIndex) -{ - pGroup->pFaceIndices[pGroup->iNrFaces] = iTriIndex; - ++pGroup->iNrFaces; -} - -static tbool AssignRecur(const int piTriListIn[], - STriInfo psTriInfos[], - const int iMyTriIndex, - SGroup *pGroup) -{ - STriInfo *pMyTriInfo = &psTriInfos[iMyTriIndex]; - - // track down vertex - const int iVertRep = pGroup->iVertexRepresentitive; - const int *pVerts = &piTriListIn[3 * iMyTriIndex + 0]; - int i = -1; - if (pVerts[0] == iVertRep) - i = 0; - else if (pVerts[1] == iVertRep) - i = 1; - else if (pVerts[2] == iVertRep) - i = 2; - assert(i >= 0 && i < 3); - - // early out - if (pMyTriInfo->AssignedGroup[i] == pGroup) - return TTRUE; - else if (pMyTriInfo->AssignedGroup[i] != NULL) - return TFALSE; - if ((pMyTriInfo->iFlag & GROUP_WITH_ANY) != 0) { - // first to group with a group-with-anything triangle - // determines its orientation. - // This is the only existing order dependency in the code!! - if (pMyTriInfo->AssignedGroup[0] == NULL && pMyTriInfo->AssignedGroup[1] == NULL && - pMyTriInfo->AssignedGroup[2] == NULL) { - pMyTriInfo->iFlag &= (~ORIENT_PRESERVING); - pMyTriInfo->iFlag |= (pGroup->bOrientPreservering ? ORIENT_PRESERVING : 0); - } - } - { - const tbool bOrient = (pMyTriInfo->iFlag & ORIENT_PRESERVING) != 0 ? TTRUE : TFALSE; - if (bOrient != pGroup->bOrientPreservering) - return TFALSE; - } - - AddTriToGroup(pGroup, iMyTriIndex); - pMyTriInfo->AssignedGroup[i] = pGroup; - - { - const int neigh_indexL = pMyTriInfo->FaceNeighbors[i]; - const int neigh_indexR = pMyTriInfo->FaceNeighbors[i > 0 ? (i - 1) : 2]; - if (neigh_indexL >= 0) - AssignRecur(piTriListIn, psTriInfos, neigh_indexL, pGroup); - if (neigh_indexR >= 0) - AssignRecur(piTriListIn, psTriInfos, neigh_indexR, pGroup); - } - - return TTRUE; -} - -/////////////////////////////////////////////////////////////////////////////////////////////////// -/////////////////////////////////////////////////////////////////////////////////////////////////// - -static tbool CompareSubGroups(const SSubGroup *pg1, const SSubGroup *pg2); -static void QuickSort(int *pSortBuffer, int iLeft, int iRight, unsigned int uSeed); -static STSpace EvalTspace(const int face_indices[], - const int iFaces, - const int piTriListIn[], - const STriInfo pTriInfos[], - const SMikkTSpaceContext *pContext, - const int iVertexRepresentitive); - -static tbool GenerateTSpaces(STSpace psTspace[], - const STriInfo pTriInfos[], - const SGroup pGroups[], - const int iNrActiveGroups, - const int piTriListIn[], - const float fThresCos, - const SMikkTSpaceContext *pContext) -{ - STSpace *pSubGroupTspace = NULL; - SSubGroup *pUniSubGroups = NULL; - int *pTmpMembers = NULL; - int iMaxNrFaces = 0, g = 0, i = 0; - for (g = 0; g < iNrActiveGroups; g++) - if (iMaxNrFaces < pGroups[g].iNrFaces) - iMaxNrFaces = pGroups[g].iNrFaces; - - if (iMaxNrFaces == 0) - return TTRUE; - - // make initial allocations - pSubGroupTspace = (STSpace *)malloc(sizeof(STSpace) * iMaxNrFaces); - pUniSubGroups = (SSubGroup *)malloc(sizeof(SSubGroup) * iMaxNrFaces); - pTmpMembers = (int *)malloc(sizeof(int) * iMaxNrFaces); - if (pSubGroupTspace == NULL || pUniSubGroups == NULL || pTmpMembers == NULL) { - if (pSubGroupTspace != NULL) - free(pSubGroupTspace); - if (pUniSubGroups != NULL) - free(pUniSubGroups); - if (pTmpMembers != NULL) - free(pTmpMembers); - return TFALSE; - } - - for (g = 0; g < iNrActiveGroups; g++) { - const SGroup *pGroup = &pGroups[g]; - int iUniqueSubGroups = 0, s = 0; - - for (i = 0; i < pGroup->iNrFaces; i++) // triangles - { - const int f = pGroup->pFaceIndices[i]; // triangle number - int index = -1, iVertIndex = -1, iOF_1 = -1, iMembers = 0, j = 0, l = 0; - SSubGroup tmp_group; - tbool bFound; - SVec3 n, vOs, vOt; - if (pTriInfos[f].AssignedGroup[0] == pGroup) - index = 0; - else if (pTriInfos[f].AssignedGroup[1] == pGroup) - index = 1; - else if (pTriInfos[f].AssignedGroup[2] == pGroup) - index = 2; - assert(index >= 0 && index < 3); - - iVertIndex = piTriListIn[f * 3 + index]; - assert(iVertIndex == pGroup->iVertexRepresentitive); - - // is normalized already - n = GetNormal(pContext, iVertIndex); - - // project - vOs = NormalizeSafe(vsub(pTriInfos[f].vOs, vscale(vdot(n, pTriInfos[f].vOs), n))); - vOt = NormalizeSafe(vsub(pTriInfos[f].vOt, vscale(vdot(n, pTriInfos[f].vOt), n))); - - // original face number - iOF_1 = pTriInfos[f].iOrgFaceNumber; - - iMembers = 0; - for (j = 0; j < pGroup->iNrFaces; j++) { - const int t = pGroup->pFaceIndices[j]; // triangle number - const int iOF_2 = pTriInfos[t].iOrgFaceNumber; - - // project - SVec3 vOs2 = NormalizeSafe(vsub(pTriInfos[t].vOs, vscale(vdot(n, pTriInfos[t].vOs), n))); - SVec3 vOt2 = NormalizeSafe(vsub(pTriInfos[t].vOt, vscale(vdot(n, pTriInfos[t].vOt), n))); - - { - const tbool bAny = ((pTriInfos[f].iFlag | pTriInfos[t].iFlag) & GROUP_WITH_ANY) != 0 ? - TTRUE : - TFALSE; - // make sure triangles which belong to the same quad are joined. - const tbool bSameOrgFace = iOF_1 == iOF_2 ? TTRUE : TFALSE; - - const float fCosS = vdot(vOs, vOs2); - const float fCosT = vdot(vOt, vOt2); - - assert(f != t || bSameOrgFace); // sanity check - if (bAny || bSameOrgFace || (fCosS > fThresCos && fCosT > fThresCos)) - pTmpMembers[iMembers++] = t; - } - } - - // sort pTmpMembers - tmp_group.iNrFaces = iMembers; - tmp_group.pTriMembers = pTmpMembers; - if (iMembers > 1) { - unsigned int uSeed = INTERNAL_RND_SORT_SEED; // could replace with a random seed? - QuickSort(pTmpMembers, 0, iMembers - 1, uSeed); - } - - // look for an existing match - bFound = TFALSE; - l = 0; - while (l < iUniqueSubGroups && !bFound) { - bFound = CompareSubGroups(&tmp_group, &pUniSubGroups[l]); - if (!bFound) - ++l; - } - - assert(bFound || l == iUniqueSubGroups); - - // if no match was found we allocate a new subgroup - if (!bFound) { - // insert new subgroup - int *pIndices = (int *)malloc(sizeof(int) * iMembers); - if (pIndices == NULL) { - // clean up and return false - int s = 0; - for (s = 0; s < iUniqueSubGroups; s++) - free(pUniSubGroups[s].pTriMembers); - free(pUniSubGroups); - free(pTmpMembers); - free(pSubGroupTspace); - return TFALSE; - } - pUniSubGroups[iUniqueSubGroups].iNrFaces = iMembers; - pUniSubGroups[iUniqueSubGroups].pTriMembers = pIndices; - memcpy(pIndices, tmp_group.pTriMembers, sizeof(int) * iMembers); - pSubGroupTspace[iUniqueSubGroups] = EvalTspace(tmp_group.pTriMembers, - iMembers, - piTriListIn, - pTriInfos, - pContext, - pGroup->iVertexRepresentitive); - ++iUniqueSubGroups; - } - - // output tspace - { - const int iOffs = pTriInfos[f].iTSpacesOffs; - const int iVert = pTriInfos[f].vert_num[index]; - STSpace *pTS_out = &psTspace[iOffs + iVert]; - assert(pTS_out->iCounter < 2); - assert(((pTriInfos[f].iFlag & ORIENT_PRESERVING) != 0) == pGroup->bOrientPreservering); - if (pTS_out->iCounter == 1) { - *pTS_out = AvgTSpace(pTS_out, &pSubGroupTspace[l]); - pTS_out->iCounter = 2; // update counter - pTS_out->bOrient = pGroup->bOrientPreservering; - } - else { - assert(pTS_out->iCounter == 0); - *pTS_out = pSubGroupTspace[l]; - pTS_out->iCounter = 1; // update counter - pTS_out->bOrient = pGroup->bOrientPreservering; - } - } - } - - // clean up - for (s = 0; s < iUniqueSubGroups; s++) - free(pUniSubGroups[s].pTriMembers); - } - - // clean up - free(pUniSubGroups); - free(pTmpMembers); - free(pSubGroupTspace); - - return TTRUE; -} - -static STSpace EvalTspace(const int face_indices[], - const int iFaces, - const int piTriListIn[], - const STriInfo pTriInfos[], - const SMikkTSpaceContext *pContext, - const int iVertexRepresentitive) -{ - STSpace res; - float fAngleSum = 0; - int face = 0; - res.vOs.x = 0.0f; - res.vOs.y = 0.0f; - res.vOs.z = 0.0f; - res.vOt.x = 0.0f; - res.vOt.y = 0.0f; - res.vOt.z = 0.0f; - res.fMagS = 0; - res.fMagT = 0; - - for (face = 0; face < iFaces; face++) { - const int f = face_indices[face]; - - // only valid triangles get to add their contribution - if ((pTriInfos[f].iFlag & GROUP_WITH_ANY) == 0) { - SVec3 n, vOs, vOt, p0, p1, p2, v1, v2; - float fCos, fAngle, fMagS, fMagT; - int i = -1, index = -1, i0 = -1, i1 = -1, i2 = -1; - if (piTriListIn[3 * f + 0] == iVertexRepresentitive) - i = 0; - else if (piTriListIn[3 * f + 1] == iVertexRepresentitive) - i = 1; - else if (piTriListIn[3 * f + 2] == iVertexRepresentitive) - i = 2; - assert(i >= 0 && i < 3); - - // project - index = piTriListIn[3 * f + i]; - n = GetNormal(pContext, index); - vOs = NormalizeSafe(vsub(pTriInfos[f].vOs, vscale(vdot(n, pTriInfos[f].vOs), n))); - vOt = NormalizeSafe(vsub(pTriInfos[f].vOt, vscale(vdot(n, pTriInfos[f].vOt), n))); - - i2 = piTriListIn[3 * f + (i < 2 ? (i + 1) : 0)]; - i1 = piTriListIn[3 * f + i]; - i0 = piTriListIn[3 * f + (i > 0 ? (i - 1) : 2)]; - - p0 = GetPosition(pContext, i0); - p1 = GetPosition(pContext, i1); - p2 = GetPosition(pContext, i2); - v1 = vsub(p0, p1); - v2 = vsub(p2, p1); - - // project - v1 = NormalizeSafe(vsub(v1, vscale(vdot(n, v1), n))); - v2 = NormalizeSafe(vsub(v2, vscale(vdot(n, v2), n))); - - // weight contribution by the angle - // between the two edge vectors - fCos = vdot(v1, v2); - fCos = fCos > 1 ? 1 : (fCos < (-1) ? (-1) : fCos); - fAngle = (float)acos(fCos); - fMagS = pTriInfos[f].fMagS; - fMagT = pTriInfos[f].fMagT; - - res.vOs = vadd(res.vOs, vscale(fAngle, vOs)); - res.vOt = vadd(res.vOt, vscale(fAngle, vOt)); - res.fMagS += (fAngle * fMagS); - res.fMagT += (fAngle * fMagT); - fAngleSum += fAngle; - } - } - - // normalize - res.vOs = NormalizeSafe(res.vOs); - res.vOt = NormalizeSafe(res.vOt); - if (fAngleSum > 0) { - res.fMagS /= fAngleSum; - res.fMagT /= fAngleSum; - } - - return res; -} - -static tbool CompareSubGroups(const SSubGroup *pg1, const SSubGroup *pg2) -{ - tbool bStillSame = TTRUE; - int i = 0; - if (pg1->iNrFaces != pg2->iNrFaces) - return TFALSE; - while (i < pg1->iNrFaces && bStillSame) { - bStillSame = pg1->pTriMembers[i] == pg2->pTriMembers[i] ? TTRUE : TFALSE; - if (bStillSame) - ++i; - } - return bStillSame; -} - -static void QuickSort(int *pSortBuffer, int iLeft, int iRight, unsigned int uSeed) -{ - int iL, iR, n, index, iMid, iTmp; - - // Random - unsigned int t = uSeed & 31; - t = rotl(uSeed, t); - uSeed = uSeed + t + 3; - // Random end - - iL = iLeft; - iR = iRight; - n = (iR - iL) + 1; - assert(n >= 0); - index = (int)(uSeed % (unsigned int)n); - - iMid = pSortBuffer[index + iL]; - - do { - while (pSortBuffer[iL] < iMid) - ++iL; - while (pSortBuffer[iR] > iMid) - --iR; - - if (iL <= iR) { - iTmp = pSortBuffer[iL]; - pSortBuffer[iL] = pSortBuffer[iR]; - pSortBuffer[iR] = iTmp; - ++iL; - --iR; - } - } while (iL <= iR); - - if (iLeft < iR) - QuickSort(pSortBuffer, iLeft, iR, uSeed); - if (iL < iRight) - QuickSort(pSortBuffer, iL, iRight, uSeed); -} - -///////////////////////////////////////////////////////////////////////////////////////////// -///////////////////////////////////////////////////////////////////////////////////////////// - -static void QuickSortEdges( - SEdge *pSortBuffer, int iLeft, int iRight, const int channel, unsigned int uSeed); -static void GetEdge(int *i0_out, - int *i1_out, - int *edgenum_out, - const int indices[], - const int i0_in, - const int i1_in); - -static void BuildNeighborsFast(STriInfo pTriInfos[], - SEdge *pEdges, - const int piTriListIn[], - const int iNrTrianglesIn) -{ - // build array of edges - unsigned int uSeed = INTERNAL_RND_SORT_SEED; // could replace with a random seed? - int iEntries = 0, iCurStartIndex = -1, f = 0, i = 0; - for (f = 0; f < iNrTrianglesIn; f++) - for (i = 0; i < 3; i++) { - const int i0 = piTriListIn[f * 3 + i]; - const int i1 = piTriListIn[f * 3 + (i < 2 ? (i + 1) : 0)]; - pEdges[f * 3 + i].i0 = i0 < i1 ? i0 : i1; // put minimum index in i0 - pEdges[f * 3 + i].i1 = !(i0 < i1) ? i0 : i1; // put maximum index in i1 - pEdges[f * 3 + i].f = f; // record face number - } - - // sort over all edges by i0, this is the pricey one. - QuickSortEdges(pEdges, 0, iNrTrianglesIn * 3 - 1, 0, uSeed); // sort channel 0 which is i0 - - // sub sort over i1, should be fast. - // could replace this with a 64 bit int sort over (i0,i1) - // with i0 as msb in the quick-sort call above. - iEntries = iNrTrianglesIn * 3; - iCurStartIndex = 0; - for (i = 1; i < iEntries; i++) { - if (pEdges[iCurStartIndex].i0 != pEdges[i].i0) { - const int iL = iCurStartIndex; - const int iR = i - 1; - // const int iElems = i-iL; - iCurStartIndex = i; - QuickSortEdges(pEdges, iL, iR, 1, uSeed); // sort channel 1 which is i1 - } - } - - // sub sort over f, which should be fast. - // this step is to remain compliant with BuildNeighborsSlow() when - // more than 2 triangles use the same edge (such as a butterfly topology). - iCurStartIndex = 0; - for (i = 1; i < iEntries; i++) { - if (pEdges[iCurStartIndex].i0 != pEdges[i].i0 || pEdges[iCurStartIndex].i1 != pEdges[i].i1) { - const int iL = iCurStartIndex; - const int iR = i - 1; - // const int iElems = i-iL; - iCurStartIndex = i; - QuickSortEdges(pEdges, iL, iR, 2, uSeed); // sort channel 2 which is f - } - } - - // pair up, adjacent triangles - for (i = 0; i < iEntries; i++) { - const int i0 = pEdges[i].i0; - const int i1 = pEdges[i].i1; - const int f = pEdges[i].f; - tbool bUnassigned_A; - - int i0_A, i1_A; - int edgenum_A, edgenum_B = 0; // 0,1 or 2 - GetEdge(&i0_A, - &i1_A, - &edgenum_A, - &piTriListIn[f * 3], - i0, - i1); // resolve index ordering and edge_num - bUnassigned_A = pTriInfos[f].FaceNeighbors[edgenum_A] == -1 ? TTRUE : TFALSE; - - if (bUnassigned_A) { - // get true index ordering - int j = i + 1, t; - tbool bNotFound = TTRUE; - while (j < iEntries && i0 == pEdges[j].i0 && i1 == pEdges[j].i1 && bNotFound) { - tbool bUnassigned_B; - int i0_B, i1_B; - t = pEdges[j].f; - // flip i0_B and i1_B - GetEdge(&i1_B, - &i0_B, - &edgenum_B, - &piTriListIn[t * 3], - pEdges[j].i0, - pEdges[j].i1); // resolve index ordering and edge_num - // assert(!(i0_A==i1_B && i1_A==i0_B)); - bUnassigned_B = pTriInfos[t].FaceNeighbors[edgenum_B] == -1 ? TTRUE : TFALSE; - if (i0_A == i0_B && i1_A == i1_B && bUnassigned_B) - bNotFound = TFALSE; - else - ++j; - } - - if (!bNotFound) { - int t = pEdges[j].f; - pTriInfos[f].FaceNeighbors[edgenum_A] = t; - // assert(pTriInfos[t].FaceNeighbors[edgenum_B]==-1); - pTriInfos[t].FaceNeighbors[edgenum_B] = f; - } - } - } -} - -static void BuildNeighborsSlow(STriInfo pTriInfos[], - const int piTriListIn[], - const int iNrTrianglesIn) -{ - int f = 0, i = 0; - for (f = 0; f < iNrTrianglesIn; f++) { - for (i = 0; i < 3; i++) { - // if unassigned - if (pTriInfos[f].FaceNeighbors[i] == -1) { - const int i0_A = piTriListIn[f * 3 + i]; - const int i1_A = piTriListIn[f * 3 + (i < 2 ? (i + 1) : 0)]; - - // search for a neighbor - tbool bFound = TFALSE; - int t = 0, j = 0; - while (!bFound && t < iNrTrianglesIn) { - if (t != f) { - j = 0; - while (!bFound && j < 3) { - // in rev order - const int i1_B = piTriListIn[t * 3 + j]; - const int i0_B = piTriListIn[t * 3 + (j < 2 ? (j + 1) : 0)]; - // assert(!(i0_A==i1_B && i1_A==i0_B)); - if (i0_A == i0_B && i1_A == i1_B) - bFound = TTRUE; - else - ++j; - } - } - - if (!bFound) - ++t; - } - - // assign neighbors - if (bFound) { - pTriInfos[f].FaceNeighbors[i] = t; - // assert(pTriInfos[t].FaceNeighbors[j]==-1); - pTriInfos[t].FaceNeighbors[j] = f; - } - } - } - } -} - -static void QuickSortEdges( - SEdge *pSortBuffer, int iLeft, int iRight, const int channel, unsigned int uSeed) -{ - unsigned int t; - int iL, iR, n, index, iMid; - - // early out - SEdge sTmp; - const int iElems = iRight - iLeft + 1; - if (iElems < 2) - return; - else if (iElems == 2) { - if (pSortBuffer[iLeft].array[channel] > pSortBuffer[iRight].array[channel]) { - sTmp = pSortBuffer[iLeft]; - pSortBuffer[iLeft] = pSortBuffer[iRight]; - pSortBuffer[iRight] = sTmp; - } - return; - } - else if (iElems < 16) { - int i, j; - for (i = 0; i < iElems - 1; i++) { - for (j = 0; j < iElems - i - 1; j++) { - int index = iLeft + j; - if (pSortBuffer[index].array[channel] > pSortBuffer[index + 1].array[channel]) { - sTmp = pSortBuffer[index]; - pSortBuffer[index] = pSortBuffer[index + 1]; - pSortBuffer[index + 1] = sTmp; - } - } - } - return; - } - - // Random - t = uSeed & 31; - t = rotl(uSeed, t); - uSeed = uSeed + t + 3; - // Random end - - iL = iLeft; - iR = iRight; - n = (iR - iL) + 1; - assert(n >= 0); - index = (int)(uSeed % (unsigned int)n); - - iMid = pSortBuffer[index + iL].array[channel]; - - do { - while (pSortBuffer[iL].array[channel] < iMid) - ++iL; - while (pSortBuffer[iR].array[channel] > iMid) - --iR; - - if (iL <= iR) { - sTmp = pSortBuffer[iL]; - pSortBuffer[iL] = pSortBuffer[iR]; - pSortBuffer[iR] = sTmp; - ++iL; - --iR; - } - } while (iL <= iR); - - if (iLeft < iR) - QuickSortEdges(pSortBuffer, iLeft, iR, channel, uSeed); - if (iL < iRight) - QuickSortEdges(pSortBuffer, iL, iRight, channel, uSeed); -} - -// resolve ordering and edge number -static void GetEdge(int *i0_out, - int *i1_out, - int *edgenum_out, - const int indices[], - const int i0_in, - const int i1_in) -{ - *edgenum_out = -1; - - // test if first index is on the edge - if (indices[0] == i0_in || indices[0] == i1_in) { - // test if second index is on the edge - if (indices[1] == i0_in || indices[1] == i1_in) { - edgenum_out[0] = 0; // first edge - i0_out[0] = indices[0]; - i1_out[0] = indices[1]; - } - else { - edgenum_out[0] = 2; // third edge - i0_out[0] = indices[2]; - i1_out[0] = indices[0]; - } - } - else { - // only second and third index is on the edge - edgenum_out[0] = 1; // second edge - i0_out[0] = indices[1]; - i1_out[0] = indices[2]; - } -} - -///////////////////////////////////////////////////////////////////////////////////////////// -/////////////////////////////////// Degenerate triangles //////////////////////////////////// - -static void DegenPrologue(STriInfo pTriInfos[], - int piTriList_out[], - const int iNrTrianglesIn, - const int iTotTris) -{ - int iNextGoodTriangleSearchIndex = -1; - tbool bStillFindingGoodOnes; - - // locate quads with only one good triangle - int t = 0; - while (t < (iTotTris - 1)) { - const int iFO_a = pTriInfos[t].iOrgFaceNumber; - const int iFO_b = pTriInfos[t + 1].iOrgFaceNumber; - if (iFO_a == iFO_b) // this is a quad - { - const tbool bIsDeg_a = (pTriInfos[t].iFlag & MARK_DEGENERATE) != 0 ? TTRUE : TFALSE; - const tbool bIsDeg_b = (pTriInfos[t + 1].iFlag & MARK_DEGENERATE) != 0 ? TTRUE : TFALSE; - if ((bIsDeg_a ^ bIsDeg_b) != 0) { - pTriInfos[t].iFlag |= QUAD_ONE_DEGEN_TRI; - pTriInfos[t + 1].iFlag |= QUAD_ONE_DEGEN_TRI; - } - t += 2; - } - else - ++t; - } - - // reorder list so all degen triangles are moved to the back - // without reordering the good triangles - iNextGoodTriangleSearchIndex = 1; - t = 0; - bStillFindingGoodOnes = TTRUE; - while (t < iNrTrianglesIn && bStillFindingGoodOnes) { - const tbool bIsGood = (pTriInfos[t].iFlag & MARK_DEGENERATE) == 0 ? TTRUE : TFALSE; - if (bIsGood) { - if (iNextGoodTriangleSearchIndex < (t + 2)) - iNextGoodTriangleSearchIndex = t + 2; - } - else { - int t0, t1; - // search for the first good triangle. - tbool bJustADegenerate = TTRUE; - while (bJustADegenerate && iNextGoodTriangleSearchIndex < iTotTris) { - const tbool bIsGood = (pTriInfos[iNextGoodTriangleSearchIndex].iFlag & MARK_DEGENERATE) == - 0 ? - TTRUE : - TFALSE; - if (bIsGood) - bJustADegenerate = TFALSE; - else - ++iNextGoodTriangleSearchIndex; - } - - t0 = t; - t1 = iNextGoodTriangleSearchIndex; - ++iNextGoodTriangleSearchIndex; - assert(iNextGoodTriangleSearchIndex > (t + 1)); - - // swap triangle t0 and t1 - if (!bJustADegenerate) { - int i = 0; - for (i = 0; i < 3; i++) { - const int index = piTriList_out[t0 * 3 + i]; - piTriList_out[t0 * 3 + i] = piTriList_out[t1 * 3 + i]; - piTriList_out[t1 * 3 + i] = index; - } - { - const STriInfo tri_info = pTriInfos[t0]; - pTriInfos[t0] = pTriInfos[t1]; - pTriInfos[t1] = tri_info; - } - } - else - bStillFindingGoodOnes = TFALSE; // this is not supposed to happen - } - - if (bStillFindingGoodOnes) - ++t; - } - - assert(bStillFindingGoodOnes); // code will still work. - assert(iNrTrianglesIn == t); -} - -typedef struct VertReverseLookupContext { - tbool bIsInitialized; - int *pLookup; - int iMaxVertIndex; -} VertReverseLookupContext; - -static void GenerateReverseLookup(const int piTriListIn[], - const int iNrTrianglesIn, - VertReverseLookupContext *pLookupCtx) -{ - int t; - // Figure out what size of lookup array we need. - pLookupCtx->iMaxVertIndex = -1; - for (t = 0; t < 3 * iNrTrianglesIn; t++) { - int iVertIndex = piTriListIn[t]; - if (iVertIndex > pLookupCtx->iMaxVertIndex) { - pLookupCtx->iMaxVertIndex = iVertIndex; - } - } - // Allocate memory. - if (pLookupCtx->iMaxVertIndex < 1) { - // Nothing to allocate, all triangles are degenerate. - return; - } - pLookupCtx->pLookup = malloc(sizeof(int) * (pLookupCtx->iMaxVertIndex + 1)); - if (pLookupCtx->pLookup == NULL) { - // Most likely run out of memory. - return; - } - // Fill in lookup. - for (t = 0; t <= pLookupCtx->iMaxVertIndex; t++) { - pLookupCtx->pLookup[t] = -1; - } - for (t = 0; t < 3 * iNrTrianglesIn; t++) { - int iVertIndex = piTriListIn[t]; - if (pLookupCtx->pLookup[iVertIndex] != -1) { - continue; - } - pLookupCtx->pLookup[iVertIndex] = t; - } -} - -static int LookupVertexIndexFromGoodTriangle(VertReverseLookupContext *pLookupCtx, - int piTriListIn[], - const int iNrTrianglesIn, - const int iVertexIndex) -{ - // Allocate lookup on demand. - if (!pLookupCtx->bIsInitialized) { - GenerateReverseLookup(piTriListIn, iNrTrianglesIn, pLookupCtx); - pLookupCtx->bIsInitialized = TTRUE; - } - // Make sure vertex index is in the mapping. - if (iVertexIndex > pLookupCtx->iMaxVertIndex) { - return -1; - } - if (pLookupCtx->pLookup == NULL) { - return -1; - } - // Perform actual lookup. - return pLookupCtx->pLookup[iVertexIndex]; -} - -static void FreeReverseLookup(VertReverseLookupContext *pLookupCtx) -{ - if (!pLookupCtx->bIsInitialized) { - return; - } - if (pLookupCtx->pLookup != NULL) { - free(pLookupCtx->pLookup); - } -} - -static void DegenEpilogue(STSpace psTspace[], - STriInfo pTriInfos[], - int piTriListIn[], - const SMikkTSpaceContext *pContext, - const int iNrTrianglesIn, - const int iTotTris) -{ - int t = 0, i = 0; - VertReverseLookupContext lookupCtx = {TFALSE}; - // deal with degenerate triangles - // punishment for degenerate triangles is O(iNrTrianglesIn) extra memory. - for (t = iNrTrianglesIn; t < iTotTris; t++) { - // degenerate triangles on a quad with one good triangle are skipped - // here but processed in the next loop - const tbool bSkip = (pTriInfos[t].iFlag & QUAD_ONE_DEGEN_TRI) != 0 ? TTRUE : TFALSE; - if (bSkip) { - continue; - } - - for (i = 0; i < 3; i++) { - const int index1 = piTriListIn[t * 3 + i]; - int j = LookupVertexIndexFromGoodTriangle(&lookupCtx, piTriListIn, iNrTrianglesIn, index1); - if (j < 0) { - // Matching vertex from good triangle is not found. - continue; - } - - const int iTri = j / 3; - const int iVert = j % 3; - const int iSrcVert = pTriInfos[iTri].vert_num[iVert]; - const int iSrcOffs = pTriInfos[iTri].iTSpacesOffs; - const int iDstVert = pTriInfos[t].vert_num[i]; - const int iDstOffs = pTriInfos[t].iTSpacesOffs; - // copy tspace - psTspace[iDstOffs + iDstVert] = psTspace[iSrcOffs + iSrcVert]; - } - } - FreeReverseLookup(&lookupCtx); - - // deal with degenerate quads with one good triangle - for (t = 0; t < iNrTrianglesIn; t++) { - // this triangle belongs to a quad where the - // other triangle is degenerate - if ((pTriInfos[t].iFlag & QUAD_ONE_DEGEN_TRI) != 0) { - SVec3 vDstP; - int iOrgF = -1, i = 0; - tbool bNotFound; - unsigned char *pV = pTriInfos[t].vert_num; - int iFlag = (1 << pV[0]) | (1 << pV[1]) | (1 << pV[2]); - int iMissingIndex = 0; - if ((iFlag & 2) == 0) - iMissingIndex = 1; - else if ((iFlag & 4) == 0) - iMissingIndex = 2; - else if ((iFlag & 8) == 0) - iMissingIndex = 3; - - iOrgF = pTriInfos[t].iOrgFaceNumber; - vDstP = GetPosition(pContext, MakeIndex(iOrgF, iMissingIndex)); - bNotFound = TTRUE; - i = 0; - while (bNotFound && i < 3) { - const int iVert = pV[i]; - const SVec3 vSrcP = GetPosition(pContext, MakeIndex(iOrgF, iVert)); - if (veq(vSrcP, vDstP) == TTRUE) { - const int iOffs = pTriInfos[t].iTSpacesOffs; - psTspace[iOffs + iMissingIndex] = psTspace[iOffs + iVert]; - bNotFound = TFALSE; - } - else - ++i; - } - assert(!bNotFound); - } - } -} diff --git a/intern/mikktspace/mikktspace.h b/intern/mikktspace/mikktspace.h deleted file mode 100644 index 30c0584c2fb..00000000000 --- a/intern/mikktspace/mikktspace.h +++ /dev/null @@ -1,152 +0,0 @@ -/* SPDX-License-Identifier: Zlib - * Copyright 2011 by Morten S. Mikkelsen. */ - -/** \file - * \ingroup mikktspace - */ - -#ifndef __MIKKTSPACE_H__ -#define __MIKKTSPACE_H__ - -#ifdef __cplusplus -extern "C" { -#endif - -/* Author: Morten S. Mikkelsen - * Version: 1.0 - * - * The files mikktspace.h and mikktspace.c are designed to be - * stand-alone files and it is important that they are kept this way. - * Not having dependencies on structures/classes/libraries specific - * to the program, in which they are used, allows them to be copied - * and used as is into any tool, program or plugin. - * The code is designed to consistently generate the same - * tangent spaces, for a given mesh, in any tool in which it is used. - * This is done by performing an internal welding step and subsequently an order-independent - * evaluation of tangent space for meshes consisting of triangles and quads. - * This means faces can be received in any order and the same is true for - * the order of vertices of each face. The generated result will not be affected - * by such reordering. Additionally, whether degenerate (vertices or texture coordinates) - * primitives are present or not will not affect the generated results either. - * Once tangent space calculation is done the vertices of degenerate primitives will simply - * inherit tangent space from neighboring non degenerate primitives. - * The analysis behind this implementation can be found in my master's thesis - * which is available for download --> http://image.diku.dk/projects/media/morten.mikkelsen.08.pdf - * Note that though the tangent spaces at the vertices are generated in an order-independent way, - * by this implementation, the interpolated tangent space is still affected by which diagonal is - * chosen to split each quad. A sensible solution is to have your tools pipeline always - * split quads by the shortest diagonal. This choice is order-independent and works with mirroring. - * If these have the same length then compare the diagonals defined by the texture coordinates. - * XNormal which is a tool for baking normal maps allows you to write your own tangent space plugin - * and also quad triangulator plugin. - */ - -typedef int tbool; -typedef struct SMikkTSpaceContext SMikkTSpaceContext; - -typedef struct { - // Returns the number of faces (triangles/quads) on the mesh to be processed. - int (*m_getNumFaces)(const SMikkTSpaceContext *pContext); - - // Returns the number of vertices on face number iFace - // iFace is a number in the range {0, 1, ..., getNumFaces()-1} - int (*m_getNumVerticesOfFace)(const SMikkTSpaceContext *pContext, const int iFace); - - // returns the position/normal/texcoord of the referenced face of vertex number iVert. - // iVert is in the range {0,1,2} for triangles and {0,1,2,3} for quads. - void (*m_getPosition)(const SMikkTSpaceContext *pContext, - float fvPosOut[], - const int iFace, - const int iVert); - void (*m_getNormal)(const SMikkTSpaceContext *pContext, - float fvNormOut[], - const int iFace, - const int iVert); - void (*m_getTexCoord)(const SMikkTSpaceContext *pContext, - float fvTexcOut[], - const int iFace, - const int iVert); - - // either (or both) of the two setTSpace callbacks can be set. - // The call-back m_setTSpaceBasic() is sufficient for basic normal mapping. - - // This function is used to return the tangent and fSign to the application. - // fvTangent is a unit length vector. - // For normal maps it is sufficient to use the following simplified version of the bitangent - // which is generated at pixel/vertex level. - // bitangent = fSign * cross(vN, tangent); - // Note that the results are returned unindexed. It is possible to generate a new index list - // But averaging/overwriting tangent spaces by using an already existing index list WILL produce - // INCRORRECT results. - // DO NOT! use an already existing index list. - void (*m_setTSpaceBasic)(const SMikkTSpaceContext *pContext, - const float fvTangent[], - const float fSign, - const int iFace, - const int iVert); - - // This function is used to return tangent space results to the application. - // fvTangent and fvBiTangent are unit length vectors and fMagS and fMagT are their - // true magnitudes which can be used for relief mapping effects. - // fvBiTangent is the "real" bitangent and thus may not be perpendicular to fvTangent. - // However, both are perpendicular to the vertex normal. - // For normal maps it is sufficient to use the following simplified version of the bitangent - // which is generated at pixel/vertex level. - // fSign = bIsOrientationPreserving ? 1.0f : (-1.0f); - // bitangent = fSign * cross(vN, tangent); - // Note that the results are returned unindexed. It is possible to generate a new index list - // But averaging/overwriting tangent spaces by using an already existing index list WILL produce - // INCRORRECT results. DO NOT! use an already existing index list. - void (*m_setTSpace)(const SMikkTSpaceContext *pContext, - const float fvTangent[], - const float fvBiTangent[], - const float fMagS, - const float fMagT, - const tbool bIsOrientationPreserving, - const int iFace, - const int iVert); -} SMikkTSpaceInterface; - -struct SMikkTSpaceContext { - // initialized with callback functions - SMikkTSpaceInterface *m_pInterface; - // pointer to client side mesh data etc. - // (passed as the first parameter with every interface call) - void *m_pUserData; -}; - -// these are both thread safe! -// Default (recommended) fAngularThreshold is 180 degrees (which means threshold disabled) -tbool genTangSpaceDefault(const SMikkTSpaceContext *pContext); -tbool genTangSpace(const SMikkTSpaceContext *pContext, const float fAngularThreshold); - -// To avoid visual errors (distortions/unwanted hard edges in lighting), when using sampled normal -// maps, the normal map sampler must use the exact inverse of the pixel shader transformation. -// The most efficient transformation we can possibly do in the pixel shader is achieved by using, -// directly, the "unnormalized" interpolated tangent, bitangent and vertex normal: vT, vB and vN. -// pixel shader (fast transform out) -// vNout = normalize( vNt.x * vT + vNt.y * vB + vNt.z * vN ); -// where vNt is the tangent space normal. The normal map sampler must likewise use the -// interpolated and "unnormalized" tangent, bitangent and vertex normal to be compliant with the -// pixel shader. sampler does (exact inverse of pixel shader): -// float3 row0 = cross(vB, vN); -// float3 row1 = cross(vN, vT); -// float3 row2 = cross(vT, vB); -// float fSign = dot(vT, row0)<0 ? -1 : 1; -// vNt = normalize( fSign * float3(dot(vNout,row0), dot(vNout,row1), dot(vNout,row2)) ); -// where vNout is the sampled normal in some chosen 3D space. -// -// Should you choose to reconstruct the bitangent in the pixel shader instead -// of the vertex shader, as explained earlier, then be sure to do this in the normal map sampler -// also. Finally, beware of quad triangulations. If the normal map sampler doesn't use the same -// triangulation of quads as your renderer then problems will occur since the interpolated tangent -// spaces will differ eventhough the vertex level tangent spaces match. This can be solved either -// by triangulating before sampling/exporting or by using the order-independent choice of diagonal -// for splitting quads suggested earlier. However, this must be used both by the sampler and your -// tools/rendering pipeline. - -#ifdef __cplusplus -} -#endif - -#endif diff --git a/intern/mikktspace/mikktspace.hh b/intern/mikktspace/mikktspace.hh new file mode 100644 index 00000000000..e2c7084566f --- /dev/null +++ b/intern/mikktspace/mikktspace.hh @@ -0,0 +1,829 @@ +/* SPDX-License-Identifier: Apache-2.0 + * + * Original C code: + * Copyright 2011 by Morten S. Mikkelsen. + * + * C++ rewrite: + * Copyright 2022 Blender Foundation. All rights reserved. + */ + +/** \file + * \ingroup mikktspace + */ + +#include <algorithm> +#include <cassert> + +#ifdef WITH_TBB +# include <tbb/parallel_for.h> +#endif + +#include "mikk_atomic_hash_set.hh" +#include "mikk_float3.hh" +#include "mikk_util.hh" + +namespace mikk { + +static constexpr uint UNSET_ENTRY = 0xffffffffu; + +template<typename Mesh> class Mikktspace { + struct Triangle { + /* Stores neighboring triangle for group assignment. */ + std::array<uint, 3> neighbor; + /* Stores assigned group of each vertex. */ + std::array<uint, 3> group; + /* Stores vertex indices that make up the triangle. */ + std::array<uint, 3> vertices; + + /* Computed face tangent, will be accumulated into group. */ + float3 tangent; + + /* Index of the face that this triangle belongs to. */ + uint faceIdx; + /* Index of the first of this triangle's vertices' TSpaces. */ + uint tSpaceIdx; + + /* Stores mapping from this triangle's vertices to the original + * face's vertices (relevant for quads). */ + std::array<uint8_t, 3> faceVertex; + + // flags + bool markDegenerate : 1; + bool quadOneDegenTri : 1; + bool groupWithAny : 1; + bool orientPreserving : 1; + + Triangle(uint faceIdx_, uint tSpaceIdx_) + : tangent{0.0f}, + faceIdx{faceIdx_}, + tSpaceIdx{tSpaceIdx_}, + markDegenerate{false}, + quadOneDegenTri{false}, + groupWithAny{true}, + orientPreserving{false} + { + neighbor.fill(UNSET_ENTRY); + group.fill(UNSET_ENTRY); + } + + void setVertices(uint8_t i0, uint8_t i1, uint8_t i2) + { + faceVertex[0] = i0; + faceVertex[1] = i1; + faceVertex[2] = i2; + vertices[0] = pack_index(faceIdx, i0); + vertices[1] = pack_index(faceIdx, i1); + vertices[2] = pack_index(faceIdx, i2); + } + }; + + struct Group { + float3 tangent; + uint vertexRepresentative; + bool orientPreserving; + + Group(uint vertexRepresentative_, bool orientPreserving_) + : tangent{0.0f}, + vertexRepresentative{vertexRepresentative_}, + orientPreserving{orientPreserving_} + { + } + + void normalizeTSpace() + { + tangent = tangent.normalize(); + } + + void accumulateTSpaceAtomic(float3 v_tangent) + { + float_add_atomic(&tangent.x, v_tangent.x); + float_add_atomic(&tangent.y, v_tangent.y); + float_add_atomic(&tangent.z, v_tangent.z); + } + + void accumulateTSpace(float3 v_tangent) + { + tangent += v_tangent; + } + }; + + struct TSpace { + float3 tangent = float3(1.0f, 0.0f, 0.0f); + uint counter = 0; + bool orientPreserving = false; + + void accumulateGroup(const Group &group) + { + assert(counter < 2); + + if (counter == 0) { + tangent = group.tangent; + } + else if (tangent == group.tangent) { + // this if is important. Due to floating point precision + // averaging when ts0==ts1 will cause a slight difference + // which results in tangent space splits later on, so do nothing + } + else { + tangent = (tangent + group.tangent).normalize(); + } + + counter++; + orientPreserving = group.orientPreserving; + } + }; + + Mesh &mesh; + + std::vector<Triangle> triangles; + std::vector<TSpace> tSpaces; + std::vector<Group> groups; + + uint nrTSpaces, nrFaces, nrTriangles, totalTriangles; + + int nrThreads; + bool isParallel; + + public: + Mikktspace(Mesh &mesh_) : mesh(mesh_) + { + } + + void genTangSpace() + { + nrFaces = uint(mesh.GetNumFaces()); + +#ifdef WITH_TBB + nrThreads = tbb::this_task_arena::max_concurrency(); + isParallel = (nrThreads > 1) && (nrFaces > 10000); +#else + nrThreads = 1; + isParallel = false; +#endif + + // make an initial triangle --> face index list + generateInitialVerticesIndexList(); + + if (nrTriangles == 0) { + return; + } + + // make a welded index list of identical positions and attributes (pos, norm, texc) + generateSharedVerticesIndexList(); + + // mark all triangle pairs that belong to a quad with only one + // good triangle. These need special treatment in degenEpilogue(). + // Additionally, move all good triangles to the start of + // triangles[] without changing order and + // put the degenerate triangles last. + degenPrologue(); + + if (nrTriangles == 0) { + // No point in building tangents if there are no non-degenerate triangles, so just zero them + tSpaces.resize(nrTSpaces); + } + else { + // evaluate triangle level attributes and neighbor list + initTriangle(); + + // match up edge pairs + buildNeighbors(); + + // based on the 4 rules, identify groups based on connectivity + build4RuleGroups(); + + // make tspaces, each group is split up into subgroups. + // Finally a tangent space is made for every resulting subgroup + generateTSpaces(); + + // degenerate quads with one good triangle will be fixed by copying a space from + // the good triangle to the coinciding vertex. + // all other degenerate triangles will just copy a space from any good triangle + // with the same welded index in vertices[]. + degenEpilogue(); + } + + uint index = 0; + for (uint f = 0; f < nrFaces; f++) { + const uint verts = mesh.GetNumVerticesOfFace(f); + if (verts != 3 && verts != 4) { + continue; + } + + // set data + for (uint i = 0; i < verts; i++) { + const TSpace &tSpace = tSpaces[index++]; + mesh.SetTangentSpace(f, i, tSpace.tangent, tSpace.orientPreserving); + } + } + } + + protected: + template<typename F> void runParallel(uint start, uint end, F func) + { +#ifdef WITH_TBB + if (isParallel) { + tbb::parallel_for(start, end, func); + } + else +#endif + { + for (uint i = start; i < end; i++) { + func(i); + } + } + } + + /////////////////////////////////////////////////////////////////////////////////////////////////// + /////////////////////////////////////////////////////////////////////////////////////////////////// + + float3 getPosition(uint vertexID) + { + uint f, v; + unpack_index(f, v, vertexID); + return mesh.GetPosition(f, v); + } + + float3 getNormal(uint vertexID) + { + uint f, v; + unpack_index(f, v, vertexID); + return mesh.GetNormal(f, v); + } + + float3 getTexCoord(uint vertexID) + { + uint f, v; + unpack_index(f, v, vertexID); + return mesh.GetTexCoord(f, v); + } + + /////////////////////////////////////////////////////////////////////////////////////////////////// + /////////////////////////////////////////////////////////////////////////////////////////////////// + + void generateInitialVerticesIndexList() + { + nrTriangles = 0; + for (uint f = 0; f < nrFaces; f++) { + const uint verts = mesh.GetNumVerticesOfFace(f); + if (verts == 3) { + nrTriangles += 1; + } + else if (verts == 4) { + nrTriangles += 2; + } + } + + triangles.reserve(nrTriangles); + + nrTSpaces = 0; + for (uint f = 0; f < nrFaces; f++) { + const uint verts = mesh.GetNumVerticesOfFace(f); + if (verts != 3 && verts != 4) + continue; + + uint tA = uint(triangles.size()); + triangles.emplace_back(f, nrTSpaces); + Triangle &triA = triangles[tA]; + + if (verts == 3) { + triA.setVertices(0, 1, 2); + } + else { + uint tB = uint(triangles.size()); + triangles.emplace_back(f, nrTSpaces); + Triangle &triB = triangles[tB]; + + // need an order independent way to evaluate + // tspace on quads. This is done by splitting + // along the shortest diagonal. + float distSQ_02 = (mesh.GetTexCoord(f, 2) - mesh.GetTexCoord(f, 0)).length_squared(); + float distSQ_13 = (mesh.GetTexCoord(f, 3) - mesh.GetTexCoord(f, 1)).length_squared(); + bool quadDiagIs_02; + if (distSQ_02 != distSQ_13) + quadDiagIs_02 = (distSQ_02 < distSQ_13); + else { + distSQ_02 = (mesh.GetPosition(f, 2) - mesh.GetPosition(f, 0)).length_squared(); + distSQ_13 = (mesh.GetPosition(f, 3) - mesh.GetPosition(f, 1)).length_squared(); + quadDiagIs_02 = !(distSQ_13 < distSQ_02); + } + + if (quadDiagIs_02) { + triA.setVertices(0, 1, 2); + triB.setVertices(0, 2, 3); + } + else { + triA.setVertices(0, 1, 3); + triB.setVertices(1, 2, 3); + } + } + + nrTSpaces += verts; + } + } + + struct VertexHash { + Mikktspace<Mesh> *mikk; + inline uint operator()(const uint &k) const + { + return hash_float3x3(mikk->getPosition(k), mikk->getNormal(k), mikk->getTexCoord(k)); + } + }; + + struct VertexEqual { + Mikktspace<Mesh> *mikk; + inline bool operator()(const uint &kA, const uint &kB) const + { + return mikk->getTexCoord(kA) == mikk->getTexCoord(kB) && + mikk->getNormal(kA) == mikk->getNormal(kB) && + mikk->getPosition(kA) == mikk->getPosition(kB); + } + }; + + /* Merge identical vertices. + * To find vertices with identical position, normal and texcoord, we calculate a hash of the 9 + * values. Then, by sorting based on that hash, identical elements (having identical hashes) will + * be moved next to each other. Since there might be hash collisions, the elements of each block + * are then compared with each other and duplicates are merged. + */ + template<bool isAtomic> void generateSharedVerticesIndexList_impl() + { + uint numVertices = nrTriangles * 3; + AtomicHashSet<uint, isAtomic, VertexHash, VertexEqual> set(numVertices, {this}, {this}); + runParallel(0u, nrTriangles, [&](uint t) { + for (uint i = 0; i < 3; i++) { + auto res = set.emplace(triangles[t].vertices[i]); + if (!res.second) { + triangles[t].vertices[i] = res.first; + } + } + }); + } + void generateSharedVerticesIndexList() + { + if (isParallel) { + generateSharedVerticesIndexList_impl<true>(); + } + else { + generateSharedVerticesIndexList_impl<false>(); + } + } + + ///////////////////////////////////////////////////////////////////////////////////////////// + /////////////////////////////////// Degenerate triangles //////////////////////////////////// + + void degenPrologue() + { + // Mark all degenerate triangles + totalTriangles = nrTriangles; + std::atomic<uint> degenTriangles(0); + runParallel(0u, totalTriangles, [&](uint t) { + const float3 p0 = getPosition(triangles[t].vertices[0]); + const float3 p1 = getPosition(triangles[t].vertices[1]); + const float3 p2 = getPosition(triangles[t].vertices[2]); + if (p0 == p1 || p0 == p2 || p1 == p2) // degenerate + { + triangles[t].markDegenerate = true; + degenTriangles.fetch_add(1); + } + }); + nrTriangles -= degenTriangles.load(); + + if (totalTriangles == nrTriangles) { + return; + } + + // locate quads with only one good triangle + runParallel(0u, totalTriangles - 1, [&](uint t) { + Triangle &triangleA = triangles[t], &triangleB = triangles[t + 1]; + if (triangleA.faceIdx != triangleB.faceIdx) { + /* Individual triangle, skip. */ + return; + } + if (triangleA.markDegenerate != triangleB.markDegenerate) { + triangleA.quadOneDegenTri = true; + triangleB.quadOneDegenTri = true; + } + }); + + std::stable_partition(triangles.begin(), triangles.end(), [](const Triangle &tri) { + return !tri.markDegenerate; + }); + } + + void degenEpilogue() + { + if (nrTriangles == totalTriangles) { + return; + } + + std::unordered_map<uint, uint> goodTriangleMap; + for (uint t = 0; t < nrTriangles; t++) { + for (uint i = 0; i < 3; i++) { + goodTriangleMap.emplace(triangles[t].vertices[i], pack_index(t, i)); + } + } + + // deal with degenerate triangles + // punishment for degenerate triangles is O(nrTriangles) extra memory. + for (uint t = nrTriangles; t < totalTriangles; t++) { + // degenerate triangles on a quad with one good triangle are skipped + // here but processed in the next loop + if (triangles[t].quadOneDegenTri) { + continue; + } + + for (uint i = 0; i < 3; i++) { + const auto entry = goodTriangleMap.find(triangles[t].vertices[i]); + if (entry == goodTriangleMap.end()) { + // Matching vertex from good triangle is not found. + continue; + } + + uint tSrc, iSrc; + unpack_index(tSrc, iSrc, entry->second); + const uint iSrcVert = triangles[tSrc].faceVertex[iSrc]; + const uint iSrcOffs = triangles[tSrc].tSpaceIdx; + const uint iDstVert = triangles[t].faceVertex[i]; + const uint iDstOffs = triangles[t].tSpaceIdx; + // copy tspace + tSpaces[iDstOffs + iDstVert] = tSpaces[iSrcOffs + iSrcVert]; + } + } + + // deal with degenerate quads with one good triangle + for (uint t = 0; t < nrTriangles; t++) { + // this triangle belongs to a quad where the + // other triangle is degenerate + if (!triangles[t].quadOneDegenTri) { + continue; + } + uint vertFlag = (1u << triangles[t].faceVertex[0]) | (1u << triangles[t].faceVertex[1]) | + (1u << triangles[t].faceVertex[2]); + uint missingFaceVertex = 0; + if ((vertFlag & 2) == 0) + missingFaceVertex = 1; + else if ((vertFlag & 4) == 0) + missingFaceVertex = 2; + else if ((vertFlag & 8) == 0) + missingFaceVertex = 3; + + uint faceIdx = triangles[t].faceIdx; + float3 dstP = mesh.GetPosition(faceIdx, missingFaceVertex); + bool found = false; + for (uint i = 0; i < 3; i++) { + const uint faceVertex = triangles[t].faceVertex[i]; + const float3 srcP = mesh.GetPosition(faceIdx, faceVertex); + if (srcP == dstP) { + const uint offset = triangles[t].tSpaceIdx; + tSpaces[offset + missingFaceVertex] = tSpaces[offset + faceVertex]; + found = true; + break; + } + } + assert(found); + (void)found; + } + } + + /////////////////////////////////////////////////////////////////////////////////////////////////// + /////////////////////////////////////////////////////////////////////////////////////////////////// + + // returns the texture area times 2 + float calcTexArea(uint tri) + { + const float3 t1 = getTexCoord(triangles[tri].vertices[0]); + const float3 t2 = getTexCoord(triangles[tri].vertices[1]); + const float3 t3 = getTexCoord(triangles[tri].vertices[2]); + + const float t21x = t2.x - t1.x; + const float t21y = t2.y - t1.y; + const float t31x = t3.x - t1.x; + const float t31y = t3.y - t1.y; + + const float signedAreaSTx2 = t21x * t31y - t21y * t31x; + return fabsf(signedAreaSTx2); + } + + void initTriangle() + { + // triangles[f].iFlag is cleared in generateInitialVerticesIndexList() + // which is called before this function. + + // evaluate first order derivatives + runParallel(0u, nrTriangles, [&](uint t) { + Triangle &triangle = triangles[t]; + + // initial values + const float3 v1 = getPosition(triangle.vertices[0]); + const float3 v2 = getPosition(triangle.vertices[1]); + const float3 v3 = getPosition(triangle.vertices[2]); + const float3 t1 = getTexCoord(triangle.vertices[0]); + const float3 t2 = getTexCoord(triangle.vertices[1]); + const float3 t3 = getTexCoord(triangle.vertices[2]); + + const float t21x = t2.x - t1.x; + const float t21y = t2.y - t1.y; + const float t31x = t3.x - t1.x; + const float t31y = t3.y - t1.y; + const float3 d1 = v2 - v1, d2 = v3 - v1; + + const float signedAreaSTx2 = t21x * t31y - t21y * t31x; + const float3 vOs = (t31y * d1) - (t21y * d2); // eq 18 + const float3 vOt = (-t31x * d1) + (t21x * d2); // eq 19 + + triangle.orientPreserving = (signedAreaSTx2 > 0); + + if (not_zero(signedAreaSTx2)) { + const float lenOs2 = vOs.length_squared(); + const float lenOt2 = vOt.length_squared(); + const float fS = triangle.orientPreserving ? 1.0f : (-1.0f); + if (not_zero(lenOs2)) + triangle.tangent = vOs * (fS / sqrtf(lenOs2)); + + // if this is a good triangle + if (not_zero(lenOs2) && not_zero(lenOt2)) + triangle.groupWithAny = false; + } + }); + + // force otherwise healthy quads to a fixed orientation + runParallel(0u, nrTriangles - 1, [&](uint t) { + Triangle &triangleA = triangles[t], &triangleB = triangles[t + 1]; + if (triangleA.faceIdx != triangleB.faceIdx) { + // this is not a quad + return; + } + + // bad triangles should already have been removed by + // degenPrologue(), but just in case check that neither are degenerate + if (!(triangleA.markDegenerate || triangleB.markDegenerate)) { + // if this happens the quad has extremely bad mapping!! + if (triangleA.orientPreserving != triangleB.orientPreserving) { + bool chooseOrientFirstTri = false; + if (triangleB.groupWithAny) + chooseOrientFirstTri = true; + else if (calcTexArea(t) >= calcTexArea(t + 1)) + chooseOrientFirstTri = true; + + // force match + const uint t0 = chooseOrientFirstTri ? t : (t + 1); + const uint t1 = chooseOrientFirstTri ? (t + 1) : t; + triangles[t1].orientPreserving = triangles[t0].orientPreserving; + } + } + }); + } + + ///////////////////////////////////////////////////////////////////////////////////////////// + /////////////////////////////////////////// Edges /////////////////////////////////////////// + + struct NeighborShard { + struct Entry { + Entry(uint32_t key_, uint data_) : key(key_), data(data_) + { + } + uint key, data; + }; + std::vector<Entry> entries; + + NeighborShard(size_t capacity) + { + entries.reserve(capacity); + } + + void buildNeighbors(Mikktspace<Mesh> *mikk) + { + /* Entries are added by iterating over t, so by using a stable sort, + * we don't have to compare based on t as well. */ + { + std::vector<Entry> tempEntries(entries.size(), {0, 0}); + radixsort(entries, tempEntries, [](const Entry &e) { return e.key; }); + } + + for (uint i = 0; i < entries.size(); i++) { + const Entry &a = entries[i]; + uint tA, iA; + unpack_index(tA, iA, a.data); + Mikktspace<Mesh>::Triangle &triA = mikk->triangles[tA]; + + if (triA.neighbor[iA] != UNSET_ENTRY) { + continue; + } + + uint i0A = triA.vertices[iA], i1A = triA.vertices[(iA != 2) ? (iA + 1) : 0]; + for (uint j = i + 1; j < entries.size(); j++) { + const Entry &b = entries[j]; + uint tB, iB; + unpack_index(tB, iB, b.data); + Mikktspace<Mesh>::Triangle &triB = mikk->triangles[tB]; + + if (b.key != a.key) + break; + + if (triB.neighbor[iB] != UNSET_ENTRY) { + continue; + } + + uint i1B = triB.vertices[iB], i0B = triB.vertices[(iB != 2) ? (iB + 1) : 0]; + if (i0A == i0B && i1A == i1B) { + triA.neighbor[iA] = tB; + triB.neighbor[iB] = tA; + break; + } + } + } + } + }; + + void buildNeighbors() + { + /* In order to parallelize the processing, we divide the vertices into shards. + * Since only vertex pairs with the same key will be checked, we can process + * shards independently as long as we ensure that all vertices with the same + * key go into the same shard. + * This is done by hashing the key to get the shard index of each vertex. + */ + // TODO: Two-step filling that first counts and then fills? Could be parallel then. + uint targetNrShards = isParallel ? uint(4 * nrThreads) : 1; + uint nrShards = 1, hashShift = 32; + while (nrShards < targetNrShards) { + nrShards *= 2; + hashShift -= 1; + } + + /* Reserve 25% extra to account for variation due to hashing. */ + size_t reserveSize = size_t(double(3 * nrTriangles) * 1.25 / nrShards); + std::vector<NeighborShard> shards(nrShards, {reserveSize}); + + for (uint t = 0; t < nrTriangles; t++) { + Triangle &triangle = triangles[t]; + for (uint i = 0; i < 3; i++) { + const uint i0 = triangle.vertices[i]; + const uint i1 = triangle.vertices[(i != 2) ? (i + 1) : 0]; + const uint high = std::max(i0, i1), low = std::min(i0, i1); + const uint hash = hash_uint3(high, low, 0); + /* TODO: Reusing the hash here means less hash space inside each shard. + * Computing a second hash with a different seed it probably not worth it? */ + const uint shard = isParallel ? (hash >> hashShift) : 0; + shards[shard].entries.emplace_back(hash, pack_index(t, i)); + } + } + + runParallel(0u, nrShards, [&](uint s) { shards[s].buildNeighbors(this); }); + } + + /////////////////////////////////////////////////////////////////////////////////////////////////// + /////////////////////////////////////////////////////////////////////////////////////////////////// + + void assignRecur(const uint t, uint groupId) + { + if (t == UNSET_ENTRY) { + return; + } + + Triangle &triangle = triangles[t]; + Group &group = groups[groupId]; + + // track down vertex + const uint vertRep = group.vertexRepresentative; + uint i = 3; + if (triangle.vertices[0] == vertRep) + i = 0; + else if (triangle.vertices[1] == vertRep) + i = 1; + else if (triangle.vertices[2] == vertRep) + i = 2; + assert(i < 3); + + // early out + if (triangle.group[i] != UNSET_ENTRY) + return; + + if (triangle.groupWithAny) { + // first to group with a group-with-anything triangle + // determines its orientation. + // This is the only existing order dependency in the code!! + if (triangle.group[0] == UNSET_ENTRY && triangle.group[1] == UNSET_ENTRY && + triangle.group[2] == UNSET_ENTRY) { + triangle.orientPreserving = group.orientPreserving; + } + } + + if (triangle.orientPreserving != group.orientPreserving) + return; + + triangle.group[i] = groupId; + + const uint t_L = triangle.neighbor[i]; + const uint t_R = triangle.neighbor[i > 0 ? (i - 1) : 2]; + assignRecur(t_L, groupId); + assignRecur(t_R, groupId); + } + + void build4RuleGroups() + { + /* Note: This could be parallelized by grouping all [t, i] pairs into + * shards by hash(triangles[t].vertices[i]). This way, each shard can be processed + * independently and in parallel. + * However, the groupWithAny logic needs special handling (e.g. lock a mutex when + * encountering a groupWithAny triangle, then sort it out, then unlock and proceed). + */ + for (uint t = 0; t < nrTriangles; t++) { + Triangle &triangle = triangles[t]; + for (uint i = 0; i < 3; i++) { + // if not assigned to a group + if (triangle.groupWithAny || triangle.group[i] != UNSET_ENTRY) { + continue; + } + + const uint newGroupId = uint(groups.size()); + triangle.group[i] = newGroupId; + + groups.emplace_back(triangle.vertices[i], bool(triangle.orientPreserving)); + + const uint t_L = triangle.neighbor[i]; + const uint t_R = triangle.neighbor[i > 0 ? (i - 1) : 2]; + assignRecur(t_L, newGroupId); + assignRecur(t_R, newGroupId); + } + } + } + + /////////////////////////////////////////////////////////////////////////////////////////////////// + /////////////////////////////////////////////////////////////////////////////////////////////////// + + template<bool atomic> void accumulateTSpaces(uint t) + { + const Triangle &triangle = triangles[t]; + // only valid triangles get to add their contribution + if (triangle.groupWithAny) { + return; + } + + /* Todo: Vectorize? + * Also: Could add special case for flat shading, when all normals are equal half of the fCos + * projections and two of the three tangent projections are unnecessary. */ + std::array<float3, 3> n, p; + for (uint i = 0; i < 3; i++) { + n[i] = getNormal(triangle.vertices[i]); + p[i] = getPosition(triangle.vertices[i]); + } + + std::array<float, 3> fCos = {dot(project(n[0], p[1] - p[0]), project(n[0], p[2] - p[0])), + dot(project(n[1], p[2] - p[1]), project(n[1], p[0] - p[1])), + dot(project(n[2], p[0] - p[2]), project(n[2], p[1] - p[2]))}; + + for (uint i = 0; i < 3; i++) { + uint groupId = triangle.group[i]; + if (groupId != UNSET_ENTRY) { + float3 tangent = project(n[i], triangle.tangent) * + fast_acosf(std::clamp(fCos[i], -1.0f, 1.0f)); + if constexpr (atomic) { + groups[groupId].accumulateTSpaceAtomic(tangent); + } + else { + groups[groupId].accumulateTSpace(tangent); + } + } + } + } + + void generateTSpaces() + { + if (isParallel) { + runParallel(0u, nrTriangles, [&](uint t) { accumulateTSpaces<true>(t); }); + } + else { + for (uint t = 0; t < nrTriangles; t++) { + accumulateTSpaces<false>(t); + } + } + + /* TODO: Worth parallelizing? Probably not. */ + for (Group &group : groups) { + group.normalizeTSpace(); + } + + tSpaces.resize(nrTSpaces); + + for (uint t = 0; t < nrTriangles; t++) { + Triangle &triangle = triangles[t]; + for (uint i = 0; i < 3; i++) { + uint groupId = triangle.group[i]; + if (groupId == UNSET_ENTRY) { + continue; + } + const Group group = groups[groupId]; + assert(triangle.orientPreserving == group.orientPreserving); + + // output tspace + const uint offset = triangle.tSpaceIdx; + const uint faceVertex = triangle.faceVertex[i]; + tSpaces[offset + faceVertex].accumulateGroup(group); + } + } + } +}; + +} // namespace mikk |