Mikktspace: Optimized port to C++
This commit is a big overhaul to the Mikktspace module, which is used to compute tangents. I'm not calling it a rewrite since it's the result of a lot of iterations on the original code, but pretty much everything is reworked somehow. Overall goal was to a) make it faster and b) make it maintainable. Notable changes: - Since the callbacks for requesting geometry data were a big bottleneck before, I've ported it to C++ and made it header-only, templating on the data source. That way, the compiler generates code specific to the caller, which allows it to inline the data source and specialize for some cases (e.g. subd vs. non-subd in Cycles). - The one input parameter, an optional angle threshold, was not used anywhere. Turns out that removing it allows for considerable algorithmic simplification, removing a lot of the complexity in the later stages. Therefore, I've just removed the option in the new code. - The code computes several outputs, but only one (the tangent itself) is ever used in Blender. Therefore, I've removed the others to simplify the code. They could easily be brought back if needed, none of the algorithmic simplifications are conflicting with them. - The original code had fallback paths for many steps in case temporary memory allocation fails, but that never actually gets used anyways since malloc() doesn't really ever return NULL in practise, so I removed them. - In general, I've restructured A LOT of the code to make the algorithms clearer and make use of some C++ features (vectors, std::array, booleans, classes), though there's still some of cleanup that could be done. - Parallelized duplicate detection, neighbor detection, triangle tangent computation, degenerate triangle handling and tangent space accumulation. - Replaced several algorithms with faster equivalents: Duplicate detection uses a (concurrent) hash set now, neighbor detection uses Radixsort and splits vertices by index pairs etc. As for results, the exact speedup depends on the scene of course, but let's consider the file from T97378: - Blender 3.1 (before D14675): 6.07sec - Blender 3.2 (with D14675): 4.62sec - rBf0a36599007d (last nightly build): 4.42sec - With this commit: 0.90sec This speedup will mostly be noticed at the start of Cycles renders and, even more importantly, in Eevee when doing something that changes the geometry (e.g. animating) on a model using normal maps. Differential Revision: https://developer.blender.org/D15589
This commit is contained in:
parent
6b6428fcbc
commit
6951e8890a
Notes:
blender-bot
2023-02-14 05:53:42 +01:00
Referenced by issue #101185, Regression: Certain mesh cause crash on render
|
@ -65,6 +65,8 @@ set(LIB
|
|||
cycles_subd
|
||||
cycles_util
|
||||
|
||||
bf_intern_mikktspace
|
||||
|
||||
${Epoxy_LIBRARIES}
|
||||
${PYTHON_LINKFLAGS}
|
||||
${PYTHON_LIBRARIES}
|
||||
|
@ -101,6 +103,10 @@ if(WITH_MOD_FLUID)
|
|||
add_definitions(-DWITH_FLUID)
|
||||
endif()
|
||||
|
||||
if(WITH_TBB)
|
||||
add_definitions(-DWITH_TBB)
|
||||
endif()
|
||||
|
||||
if(WITH_OPENVDB)
|
||||
add_definitions(-DWITH_OPENVDB ${OPENVDB_DEFINITIONS})
|
||||
list(APPEND INC_SYS
|
||||
|
|
|
@ -24,7 +24,7 @@
|
|||
#include "util/log.h"
|
||||
#include "util/math.h"
|
||||
|
||||
#include "mikktspace.h"
|
||||
#include "mikktspace.hh"
|
||||
|
||||
#include "DNA_meshdata_types.h"
|
||||
|
||||
|
@ -32,16 +32,15 @@ CCL_NAMESPACE_BEGIN
|
|||
|
||||
/* Tangent Space */
|
||||
|
||||
struct MikkUserData {
|
||||
MikkUserData(const BL::Mesh &b_mesh,
|
||||
const char *layer_name,
|
||||
const Mesh *mesh,
|
||||
float3 *tangent,
|
||||
float *tangent_sign)
|
||||
template<bool is_subd> struct MikkMeshWrapper {
|
||||
MikkMeshWrapper(const BL::Mesh &b_mesh,
|
||||
const char *layer_name,
|
||||
const Mesh *mesh,
|
||||
float3 *tangent,
|
||||
float *tangent_sign)
|
||||
: mesh(mesh), texface(NULL), orco(NULL), tangent(tangent), tangent_sign(tangent_sign)
|
||||
{
|
||||
const AttributeSet &attributes = (mesh->get_num_subd_faces()) ? mesh->subd_attributes :
|
||||
mesh->attributes;
|
||||
const AttributeSet &attributes = is_subd ? mesh->subd_attributes : mesh->attributes;
|
||||
|
||||
Attribute *attr_vN = attributes.find(ATTR_STD_VERTEX_NORMAL);
|
||||
vertex_normal = attr_vN->data_float3();
|
||||
|
@ -51,7 +50,9 @@ struct MikkUserData {
|
|||
|
||||
if (attr_orco) {
|
||||
orco = attr_orco->data_float3();
|
||||
float3 orco_size;
|
||||
mesh_texture_space(*(BL::Mesh *)&b_mesh, orco_loc, orco_size);
|
||||
inv_orco_size = 1.0f / orco_size;
|
||||
}
|
||||
}
|
||||
else {
|
||||
|
@ -62,160 +63,126 @@ struct MikkUserData {
|
|||
}
|
||||
}
|
||||
|
||||
int GetNumFaces()
|
||||
{
|
||||
if constexpr (is_subd) {
|
||||
return mesh->get_num_subd_faces();
|
||||
}
|
||||
else {
|
||||
return mesh->num_triangles();
|
||||
}
|
||||
}
|
||||
|
||||
int GetNumVerticesOfFace(const int face_num)
|
||||
{
|
||||
if constexpr (is_subd) {
|
||||
return mesh->get_subd_num_corners()[face_num];
|
||||
}
|
||||
else {
|
||||
return 3;
|
||||
}
|
||||
}
|
||||
|
||||
int CornerIndex(const int face_num, const int vert_num)
|
||||
{
|
||||
if constexpr (is_subd) {
|
||||
const Mesh::SubdFace &face = mesh->get_subd_face(face_num);
|
||||
return face.start_corner + vert_num;
|
||||
}
|
||||
else {
|
||||
return face_num * 3 + vert_num;
|
||||
}
|
||||
}
|
||||
|
||||
int VertexIndex(const int face_num, const int vert_num)
|
||||
{
|
||||
int corner = CornerIndex(face_num, vert_num);
|
||||
if constexpr (is_subd) {
|
||||
return mesh->get_subd_face_corners()[corner];
|
||||
}
|
||||
else {
|
||||
return mesh->get_triangles()[corner];
|
||||
}
|
||||
}
|
||||
|
||||
mikk::float3 GetPosition(const int face_num, const int vert_num)
|
||||
{
|
||||
const float3 vP = mesh->get_verts()[VertexIndex(face_num, vert_num)];
|
||||
return mikk::float3(vP.x, vP.y, vP.z);
|
||||
}
|
||||
|
||||
mikk::float3 GetTexCoord(const int face_num, const int vert_num)
|
||||
{
|
||||
/* TODO: Check whether introducing a template boolean in order to
|
||||
* turn this into a constexpr is worth it. */
|
||||
if (texface != NULL) {
|
||||
const int corner_index = CornerIndex(face_num, vert_num);
|
||||
float2 tfuv = texface[corner_index];
|
||||
return mikk::float3(tfuv.x, tfuv.y, 1.0f);
|
||||
}
|
||||
else if (orco != NULL) {
|
||||
const int vertex_index = VertexIndex(face_num, vert_num);
|
||||
const float2 uv = map_to_sphere((orco[vertex_index] + orco_loc) * inv_orco_size);
|
||||
return mikk::float3(uv.x, uv.y, 1.0f);
|
||||
}
|
||||
else {
|
||||
return mikk::float3(0.0f, 0.0f, 1.0f);
|
||||
}
|
||||
}
|
||||
|
||||
mikk::float3 GetNormal(const int face_num, const int vert_num)
|
||||
{
|
||||
float3 vN;
|
||||
if (is_subd) {
|
||||
const Mesh::SubdFace &face = mesh->get_subd_face(face_num);
|
||||
if (face.smooth) {
|
||||
const int vertex_index = VertexIndex(face_num, vert_num);
|
||||
vN = vertex_normal[vertex_index];
|
||||
}
|
||||
else {
|
||||
vN = face.normal(mesh);
|
||||
}
|
||||
}
|
||||
else {
|
||||
if (mesh->get_smooth()[face_num]) {
|
||||
const int vertex_index = VertexIndex(face_num, vert_num);
|
||||
vN = vertex_normal[vertex_index];
|
||||
}
|
||||
else {
|
||||
const Mesh::Triangle tri = mesh->get_triangle(face_num);
|
||||
vN = tri.compute_normal(&mesh->get_verts()[0]);
|
||||
}
|
||||
}
|
||||
return mikk::float3(vN.x, vN.y, vN.z);
|
||||
}
|
||||
|
||||
void SetTangentSpace(const int face_num, const int vert_num, mikk::float3 T, bool orientation)
|
||||
{
|
||||
const int corner_index = CornerIndex(face_num, vert_num);
|
||||
tangent[corner_index] = make_float3(T.x, T.y, T.z);
|
||||
if (tangent_sign != NULL) {
|
||||
tangent_sign[corner_index] = orientation ? 1.0f : -1.0f;
|
||||
}
|
||||
}
|
||||
|
||||
const Mesh *mesh;
|
||||
int num_faces;
|
||||
|
||||
float3 *vertex_normal;
|
||||
float2 *texface;
|
||||
float3 *orco;
|
||||
float3 orco_loc, orco_size;
|
||||
float3 orco_loc, inv_orco_size;
|
||||
|
||||
float3 *tangent;
|
||||
float *tangent_sign;
|
||||
};
|
||||
|
||||
static int mikk_get_num_faces(const SMikkTSpaceContext *context)
|
||||
{
|
||||
const MikkUserData *userdata = (const MikkUserData *)context->m_pUserData;
|
||||
if (userdata->mesh->get_num_subd_faces()) {
|
||||
return userdata->mesh->get_num_subd_faces();
|
||||
}
|
||||
else {
|
||||
return userdata->mesh->num_triangles();
|
||||
}
|
||||
}
|
||||
|
||||
static int mikk_get_num_verts_of_face(const SMikkTSpaceContext *context, const int face_num)
|
||||
{
|
||||
const MikkUserData *userdata = (const MikkUserData *)context->m_pUserData;
|
||||
if (userdata->mesh->get_num_subd_faces()) {
|
||||
const Mesh *mesh = userdata->mesh;
|
||||
return mesh->get_subd_num_corners()[face_num];
|
||||
}
|
||||
else {
|
||||
return 3;
|
||||
}
|
||||
}
|
||||
|
||||
static int mikk_vertex_index(const Mesh *mesh, const int face_num, const int vert_num)
|
||||
{
|
||||
if (mesh->get_num_subd_faces()) {
|
||||
const Mesh::SubdFace &face = mesh->get_subd_face(face_num);
|
||||
return mesh->get_subd_face_corners()[face.start_corner + vert_num];
|
||||
}
|
||||
else {
|
||||
return mesh->get_triangles()[face_num * 3 + vert_num];
|
||||
}
|
||||
}
|
||||
|
||||
static int mikk_corner_index(const Mesh *mesh, const int face_num, const int vert_num)
|
||||
{
|
||||
if (mesh->get_num_subd_faces()) {
|
||||
const Mesh::SubdFace &face = mesh->get_subd_face(face_num);
|
||||
return face.start_corner + vert_num;
|
||||
}
|
||||
else {
|
||||
return face_num * 3 + vert_num;
|
||||
}
|
||||
}
|
||||
|
||||
static void mikk_get_position(const SMikkTSpaceContext *context,
|
||||
float P[3],
|
||||
const int face_num,
|
||||
const int vert_num)
|
||||
{
|
||||
const MikkUserData *userdata = (const MikkUserData *)context->m_pUserData;
|
||||
const Mesh *mesh = userdata->mesh;
|
||||
const int vertex_index = mikk_vertex_index(mesh, face_num, vert_num);
|
||||
const float3 vP = mesh->get_verts()[vertex_index];
|
||||
P[0] = vP.x;
|
||||
P[1] = vP.y;
|
||||
P[2] = vP.z;
|
||||
}
|
||||
|
||||
static void mikk_get_texture_coordinate(const SMikkTSpaceContext *context,
|
||||
float uv[2],
|
||||
const int face_num,
|
||||
const int vert_num)
|
||||
{
|
||||
const MikkUserData *userdata = (const MikkUserData *)context->m_pUserData;
|
||||
const Mesh *mesh = userdata->mesh;
|
||||
if (userdata->texface != NULL) {
|
||||
const int corner_index = mikk_corner_index(mesh, face_num, vert_num);
|
||||
float2 tfuv = userdata->texface[corner_index];
|
||||
uv[0] = tfuv.x;
|
||||
uv[1] = tfuv.y;
|
||||
}
|
||||
else if (userdata->orco != NULL) {
|
||||
const int vertex_index = mikk_vertex_index(mesh, face_num, vert_num);
|
||||
const float3 orco_loc = userdata->orco_loc;
|
||||
const float3 orco_size = userdata->orco_size;
|
||||
const float3 orco = (userdata->orco[vertex_index] + orco_loc) / orco_size;
|
||||
|
||||
const float2 tmp = map_to_sphere(orco);
|
||||
uv[0] = tmp.x;
|
||||
uv[1] = tmp.y;
|
||||
}
|
||||
else {
|
||||
uv[0] = 0.0f;
|
||||
uv[1] = 0.0f;
|
||||
}
|
||||
}
|
||||
|
||||
static void mikk_get_normal(const SMikkTSpaceContext *context,
|
||||
float N[3],
|
||||
const int face_num,
|
||||
const int vert_num)
|
||||
{
|
||||
const MikkUserData *userdata = (const MikkUserData *)context->m_pUserData;
|
||||
const Mesh *mesh = userdata->mesh;
|
||||
float3 vN;
|
||||
if (mesh->get_num_subd_faces()) {
|
||||
const Mesh::SubdFace &face = mesh->get_subd_face(face_num);
|
||||
if (face.smooth) {
|
||||
const int vertex_index = mikk_vertex_index(mesh, face_num, vert_num);
|
||||
vN = userdata->vertex_normal[vertex_index];
|
||||
}
|
||||
else {
|
||||
vN = face.normal(mesh);
|
||||
}
|
||||
}
|
||||
else {
|
||||
if (mesh->get_smooth()[face_num]) {
|
||||
const int vertex_index = mikk_vertex_index(mesh, face_num, vert_num);
|
||||
vN = userdata->vertex_normal[vertex_index];
|
||||
}
|
||||
else {
|
||||
const Mesh::Triangle tri = mesh->get_triangle(face_num);
|
||||
vN = tri.compute_normal(&mesh->get_verts()[0]);
|
||||
}
|
||||
}
|
||||
N[0] = vN.x;
|
||||
N[1] = vN.y;
|
||||
N[2] = vN.z;
|
||||
}
|
||||
|
||||
static void mikk_set_tangent_space(const SMikkTSpaceContext *context,
|
||||
const float T[],
|
||||
const float sign,
|
||||
const int face_num,
|
||||
const int vert_num)
|
||||
{
|
||||
MikkUserData *userdata = (MikkUserData *)context->m_pUserData;
|
||||
const Mesh *mesh = userdata->mesh;
|
||||
const int corner_index = mikk_corner_index(mesh, face_num, vert_num);
|
||||
userdata->tangent[corner_index] = make_float3(T[0], T[1], T[2]);
|
||||
if (userdata->tangent_sign != NULL) {
|
||||
userdata->tangent_sign[corner_index] = sign;
|
||||
}
|
||||
}
|
||||
|
||||
static void mikk_compute_tangents(
|
||||
const BL::Mesh &b_mesh, const char *layer_name, Mesh *mesh, bool need_sign, bool active_render)
|
||||
{
|
||||
/* Create tangent attributes. */
|
||||
AttributeSet &attributes = (mesh->get_num_subd_faces()) ? mesh->subd_attributes :
|
||||
mesh->attributes;
|
||||
const bool is_subd = mesh->get_num_subd_faces();
|
||||
AttributeSet &attributes = is_subd ? mesh->subd_attributes : mesh->attributes;
|
||||
Attribute *attr;
|
||||
ustring name;
|
||||
if (layer_name != NULL) {
|
||||
|
@ -251,24 +218,18 @@ static void mikk_compute_tangents(
|
|||
}
|
||||
tangent_sign = attr_sign->data_float();
|
||||
}
|
||||
|
||||
/* Setup userdata. */
|
||||
MikkUserData userdata(b_mesh, layer_name, mesh, tangent, tangent_sign);
|
||||
/* Setup interface. */
|
||||
SMikkTSpaceInterface sm_interface;
|
||||
memset(&sm_interface, 0, sizeof(sm_interface));
|
||||
sm_interface.m_getNumFaces = mikk_get_num_faces;
|
||||
sm_interface.m_getNumVerticesOfFace = mikk_get_num_verts_of_face;
|
||||
sm_interface.m_getPosition = mikk_get_position;
|
||||
sm_interface.m_getTexCoord = mikk_get_texture_coordinate;
|
||||
sm_interface.m_getNormal = mikk_get_normal;
|
||||
sm_interface.m_setTSpaceBasic = mikk_set_tangent_space;
|
||||
/* Setup context. */
|
||||
SMikkTSpaceContext context;
|
||||
memset(&context, 0, sizeof(context));
|
||||
context.m_pUserData = &userdata;
|
||||
context.m_pInterface = &sm_interface;
|
||||
/* Compute tangents. */
|
||||
genTangSpaceDefault(&context);
|
||||
if (is_subd) {
|
||||
MikkMeshWrapper<true> userdata(b_mesh, layer_name, mesh, tangent, tangent_sign);
|
||||
/* Compute tangents. */
|
||||
mikk::Mikktspace(userdata).genTangSpace();
|
||||
}
|
||||
else {
|
||||
MikkMeshWrapper<false> userdata(b_mesh, layer_name, mesh, tangent, tangent_sign);
|
||||
/* Compute tangents. */
|
||||
mikk::Mikktspace(userdata).genTangSpace();
|
||||
}
|
||||
}
|
||||
|
||||
template<typename TypeInCycles, typename GetValueAtIndex>
|
||||
|
|
|
@ -886,16 +886,16 @@ ccl_device_inline float2 map_to_tube(const float3 co)
|
|||
|
||||
ccl_device_inline float2 map_to_sphere(const float3 co)
|
||||
{
|
||||
float l = len(co);
|
||||
float l = dot(co, co);
|
||||
float u, v;
|
||||
if (l > 0.0f) {
|
||||
if (UNLIKELY(co.x == 0.0f && co.y == 0.0f)) {
|
||||
u = 0.0f; /* Otherwise domain error. */
|
||||
}
|
||||
else {
|
||||
u = (1.0f - atan2f(co.x, co.y) / M_PI_F) / 2.0f;
|
||||
u = (0.5f - atan2f(co.x, co.y) * M_1_2PI_F);
|
||||
}
|
||||
v = 1.0f - safe_acosf(co.z / l) / M_PI_F;
|
||||
v = 1.0f - safe_acosf(co.z / sqrtf(l)) * M_1_PI_F;
|
||||
}
|
||||
else {
|
||||
u = v = 0.0f;
|
||||
|
|
|
@ -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"
|
||||
)
|
||||
add_library(bf_intern_mikktspace INTERFACE)
|
||||
target_include_directories(bf_intern_mikktspace INTERFACE .)
|
||||
|
||||
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()
|
||||
|
||||
set(INC
|
||||
.
|
||||
)
|
||||
|
||||
set(INC_SYS
|
||||
|
||||
)
|
||||
|
||||
set(SRC
|
||||
mikktspace.c
|
||||
|
||||
mikktspace.h
|
||||
)
|
||||
|
||||
set(LIB
|
||||
)
|
||||
|
||||
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()
|
||||
|
|
|
@ -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
|
|
@ -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
|
|
@ -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 onwards.
|
||||
* This works in practise 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
|
File diff suppressed because it is too large
Load Diff
|
@ -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
|
|
@ -0,0 +1,823 @@
|
|||
/* 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();
|
||||
|
||||
// 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
|
|
@ -20,7 +20,7 @@
|
|||
#include "MEM_guardedalloc.h"
|
||||
|
||||
/* interface */
|
||||
#include "mikktspace.h"
|
||||
#include "mikktspace.hh"
|
||||
|
||||
/* -------------------------------------------------------------------- */
|
||||
/** \name Tangent Space Calculation
|
||||
|
@ -30,6 +30,107 @@
|
|||
#define USE_LOOPTRI_DETECT_QUADS
|
||||
|
||||
struct SGLSLEditMeshToTangent {
|
||||
uint GetNumFaces()
|
||||
{
|
||||
#ifdef USE_LOOPTRI_DETECT_QUADS
|
||||
return (uint)num_face_as_quad_map;
|
||||
#else
|
||||
return (uint)numTessFaces;
|
||||
#endif
|
||||
}
|
||||
|
||||
uint GetNumVerticesOfFace(const uint face_num)
|
||||
{
|
||||
#ifdef USE_LOOPTRI_DETECT_QUADS
|
||||
if (face_as_quad_map) {
|
||||
if (looptris[face_as_quad_map[face_num]][0]->f->len == 4) {
|
||||
return 4;
|
||||
}
|
||||
}
|
||||
return 3;
|
||||
#else
|
||||
UNUSED_VARS(pContext, face_num);
|
||||
return 3;
|
||||
#endif
|
||||
}
|
||||
|
||||
const BMLoop *GetLoop(const uint face_num, uint vert_index)
|
||||
{
|
||||
// BLI_assert(vert_index >= 0 && vert_index < 4);
|
||||
const BMLoop **lt;
|
||||
const BMLoop *l;
|
||||
|
||||
#ifdef USE_LOOPTRI_DETECT_QUADS
|
||||
if (face_as_quad_map) {
|
||||
lt = looptris[face_as_quad_map[face_num]];
|
||||
if (lt[0]->f->len == 4) {
|
||||
l = BM_FACE_FIRST_LOOP(lt[0]->f);
|
||||
while (vert_index--) {
|
||||
l = l->next;
|
||||
}
|
||||
return l;
|
||||
}
|
||||
/* fall through to regular triangle */
|
||||
}
|
||||
else {
|
||||
lt = looptris[face_num];
|
||||
}
|
||||
#else
|
||||
lt = looptris[face_num];
|
||||
#endif
|
||||
return lt[vert_index];
|
||||
}
|
||||
|
||||
mikk::float3 GetPosition(const uint face_num, const uint vert_index)
|
||||
{
|
||||
const BMLoop *l = GetLoop(face_num, vert_index);
|
||||
return mikk::float3(l->v->co);
|
||||
}
|
||||
|
||||
mikk::float3 GetTexCoord(const uint face_num, const uint vert_index)
|
||||
{
|
||||
const BMLoop *l = GetLoop(face_num, vert_index);
|
||||
if (cd_loop_uv_offset != -1) {
|
||||
const float *uv = (const float *)BM_ELEM_CD_GET_VOID_P(l, cd_loop_uv_offset);
|
||||
return mikk::float3(uv[0], uv[1], 1.0f);
|
||||
}
|
||||
else {
|
||||
const float *orco_p = orco[BM_elem_index_get(l->v)];
|
||||
float u, v;
|
||||
map_to_sphere(&u, &v, orco_p[0], orco_p[1], orco_p[2]);
|
||||
return mikk::float3(u, v, 1.0f);
|
||||
}
|
||||
}
|
||||
|
||||
mikk::float3 GetNormal(const uint face_num, const uint vert_index)
|
||||
{
|
||||
const BMLoop *l = GetLoop(face_num, vert_index);
|
||||
if (precomputedLoopNormals) {
|
||||
return mikk::float3(precomputedLoopNormals[BM_elem_index_get(l)]);
|
||||
}
|
||||
else if (BM_elem_flag_test(l->f, BM_ELEM_SMOOTH) == 0) { /* flat */
|
||||
if (precomputedFaceNormals) {
|
||||
return mikk::float3(precomputedFaceNormals[BM_elem_index_get(l->f)]);
|
||||
}
|
||||
else {
|
||||
return mikk::float3(l->f->no);
|
||||
}
|
||||
}
|
||||
else {
|
||||
return mikk::float3(l->v->no);
|
||||
}
|
||||
}
|
||||
|
||||
void SetTangentSpace(const uint face_num,
|
||||
const uint vert_index,
|
||||
mikk::float3 T,
|
||||
bool orientation)
|
||||
{
|
||||
const BMLoop *l = GetLoop(face_num, vert_index);
|
||||
float *p_res = tangent[BM_elem_index_get(l)];
|
||||
copy_v4_fl4(p_res, T.x, T.y, T.z, orientation ? 1.0f : -1.0f);
|
||||
}
|
||||
|
||||
const float (*precomputedFaceNormals)[3];
|
||||
const float (*precomputedLoopNormals)[3];
|
||||
const BMLoop *(*looptris)[3];
|
||||
|
@ -46,217 +147,12 @@ struct SGLSLEditMeshToTangent {
|
|||
#endif
|
||||
};
|
||||
|
||||
#ifdef USE_LOOPTRI_DETECT_QUADS
|
||||
/* seems weak but only used on quads */
|
||||
static const BMLoop *bm_loop_at_face_index(const BMFace *f, int vert_index)
|
||||
{
|
||||
const BMLoop *l = BM_FACE_FIRST_LOOP(f);
|
||||
while (vert_index--) {
|
||||
l = l->next;
|
||||
}
|
||||
return l;
|
||||
}
|
||||
#endif
|
||||
|
||||
static int emdm_ts_GetNumFaces(const SMikkTSpaceContext *pContext)
|
||||
{
|
||||
SGLSLEditMeshToTangent *pMesh = static_cast<SGLSLEditMeshToTangent *>(pContext->m_pUserData);
|
||||
|
||||
#ifdef USE_LOOPTRI_DETECT_QUADS
|
||||
return pMesh->num_face_as_quad_map;
|
||||
#else
|
||||
return pMesh->numTessFaces;
|
||||
#endif
|
||||
}
|
||||
|
||||
static int emdm_ts_GetNumVertsOfFace(const SMikkTSpaceContext *pContext, const int face_num)
|
||||
{
|
||||
#ifdef USE_LOOPTRI_DETECT_QUADS
|
||||
SGLSLEditMeshToTangent *pMesh = static_cast<SGLSLEditMeshToTangent *>(pContext->m_pUserData);
|
||||
if (pMesh->face_as_quad_map) {
|
||||
const BMLoop **lt = pMesh->looptris[pMesh->face_as_quad_map[face_num]];
|
||||
if (lt[0]->f->len == 4) {
|
||||
return 4;
|
||||
}
|
||||
}
|
||||
return 3;
|
||||
#else
|
||||
UNUSED_VARS(pContext, face_num);
|
||||
return 3;
|
||||
#endif
|
||||
}
|
||||
|
||||
static void emdm_ts_GetPosition(const SMikkTSpaceContext *pContext,
|
||||
float r_co[3],
|
||||
const int face_num,
|
||||
const int vert_index)
|
||||
{
|
||||
// BLI_assert(vert_index >= 0 && vert_index < 4);
|
||||
SGLSLEditMeshToTangent *pMesh = static_cast<SGLSLEditMeshToTangent *>(pContext->m_pUserData);
|
||||
const BMLoop **lt;
|
||||
const BMLoop *l;
|
||||
|
||||
#ifdef USE_LOOPTRI_DETECT_QUADS
|
||||
if (pMesh->face_as_quad_map) {
|
||||
lt = pMesh->looptris[pMesh->face_as_quad_map[face_num]];
|
||||
if (lt[0]->f->len == 4) {
|
||||
l = bm_loop_at_face_index(lt[0]->f, vert_index);
|
||||
goto finally;
|
||||
}
|
||||
/* fall through to regular triangle */
|
||||
}
|
||||
else {
|
||||
lt = pMesh->looptris[face_num];
|
||||
}
|
||||
#else
|
||||
lt = pMesh->looptris[face_num];
|
||||
#endif
|
||||
l = lt[vert_index];
|
||||
|
||||
const float *co;
|
||||
|
||||
finally:
|
||||
co = l->v->co;
|
||||
copy_v3_v3(r_co, co);
|
||||
}
|
||||
|
||||
static void emdm_ts_GetTextureCoordinate(const SMikkTSpaceContext *pContext,
|
||||
float r_uv[2],
|
||||
const int face_num,
|
||||
const int vert_index)
|
||||
{
|
||||
// BLI_assert(vert_index >= 0 && vert_index < 4);
|
||||
SGLSLEditMeshToTangent *pMesh = static_cast<SGLSLEditMeshToTangent *>(pContext->m_pUserData);
|
||||
const BMLoop **lt;
|
||||
const BMLoop *l;
|
||||
|
||||
#ifdef USE_LOOPTRI_DETECT_QUADS
|
||||
if (pMesh->face_as_quad_map) {
|
||||
lt = pMesh->looptris[pMesh->face_as_quad_map[face_num]];
|
||||
if (lt[0]->f->len == 4) {
|
||||
l = bm_loop_at_face_index(lt[0]->f, vert_index);
|
||||
goto finally;
|
||||
}
|
||||
/* fall through to regular triangle */
|
||||
}
|
||||
else {
|
||||
lt = pMesh->looptris[face_num];
|
||||
}
|
||||
#else
|
||||
lt = pMesh->looptris[face_num];
|
||||
#endif
|
||||
l = lt[vert_index];
|
||||
|
||||
finally:
|
||||
if (pMesh->cd_loop_uv_offset != -1) {
|
||||
const float *uv = BM_ELEM_CD_GET_FLOAT_P(l, pMesh->cd_loop_uv_offset);
|
||||
copy_v2_v2(r_uv, uv);
|
||||
}
|
||||
else {
|
||||
const float *orco = pMesh->orco[BM_elem_index_get(l->v)];
|
||||
map_to_sphere(&r_uv[0], &r_uv[1], orco[0], orco[1], orco[2]);
|
||||
}
|
||||
}
|
||||
|
||||
static void emdm_ts_GetNormal(const SMikkTSpaceContext *pContext,
|
||||
float r_no[3],
|
||||
const int face_num,
|
||||
const int vert_index)
|
||||
{
|
||||
// BLI_assert(vert_index >= 0 && vert_index < 4);
|
||||
SGLSLEditMeshToTangent *pMesh = static_cast<SGLSLEditMeshToTangent *>(pContext->m_pUserData);
|
||||
const BMLoop **lt;
|
||||
const BMLoop *l;
|
||||
|
||||
#ifdef USE_LOOPTRI_DETECT_QUADS
|
||||
if (pMesh->face_as_quad_map) {
|
||||
lt = pMesh->looptris[pMesh->face_as_quad_map[face_num]];
|
||||
if (lt[0]->f->len == 4) {
|
||||
l = bm_loop_at_face_index(lt[0]->f, vert_index);
|
||||
goto finally;
|
||||
}
|
||||
/* fall through to regular triangle */
|
||||
}
|
||||
else {
|
||||
lt = pMesh->looptris[face_num];
|
||||
}
|
||||
#else
|
||||
lt = pMesh->looptris[face_num];
|
||||
#endif
|
||||
l = lt[vert_index];
|
||||
|
||||
finally:
|
||||
if (pMesh->precomputedLoopNormals) {
|
||||
copy_v3_v3(r_no, pMesh->precomputedLoopNormals[BM_elem_index_get(l)]);
|
||||
}
|
||||
else if (BM_elem_flag_test(l->f, BM_ELEM_SMOOTH) == 0) { /* flat */
|
||||
if (pMesh->precomputedFaceNormals) {
|
||||
copy_v3_v3(r_no, pMesh->precomputedFaceNormals[BM_elem_index_get(l->f)]);
|
||||
}
|
||||
else {
|
||||
copy_v3_v3(r_no, l->f->no);
|
||||
}
|
||||
}
|
||||
else {
|
||||
copy_v3_v3(r_no, l->v->no);
|
||||
}
|
||||
}
|
||||
|
||||
static void emdm_ts_SetTSpace(const SMikkTSpaceContext *pContext,
|
||||
const float fvTangent[3],
|
||||
const float fSign,
|
||||
const int face_num,
|
||||
const int vert_index)
|
||||
{
|
||||
// BLI_assert(vert_index >= 0 && vert_index < 4);
|
||||
SGLSLEditMeshToTangent *pMesh = static_cast<SGLSLEditMeshToTangent *>(pContext->m_pUserData);
|
||||
const BMLoop **lt;
|
||||
const BMLoop *l;
|
||||
|
||||
#ifdef USE_LOOPTRI_DETECT_QUADS
|
||||
if (pMesh->face_as_quad_map) {
|
||||
lt = pMesh->looptris[pMesh->face_as_quad_map[face_num]];
|
||||
if (lt[0]->f->len == 4) {
|
||||
l = bm_loop_at_face_index(lt[0]->f, vert_index);
|
||||
goto finally;
|
||||
}
|
||||
/* fall through to regular triangle */
|
||||
}
|
||||
else {
|
||||
lt = pMesh->looptris[face_num];
|
||||
}
|
||||
#else
|
||||
lt = pMesh->looptris[face_num];
|
||||
#endif
|
||||
l = lt[vert_index];
|
||||
|
||||
float *pRes;
|
||||
|
||||
finally:
|
||||
pRes = pMesh->tangent[BM_elem_index_get(l)];
|
||||
copy_v3_v3(pRes, fvTangent);
|
||||
pRes[3] = fSign;
|
||||
}
|
||||
|
||||
static void emDM_calc_loop_tangents_thread(TaskPool *__restrict UNUSED(pool), void *taskdata)
|
||||
{
|
||||
SGLSLEditMeshToTangent *mesh2tangent = static_cast<SGLSLEditMeshToTangent *>(taskdata);
|
||||
/* new computation method */
|
||||
{
|
||||
SMikkTSpaceContext sContext{};
|
||||
SMikkTSpaceInterface sInterface{};
|
||||
sContext.m_pUserData = mesh2tangent;
|
||||
sContext.m_pInterface = &sInterface;
|
||||
sInterface.m_getNumFaces = emdm_ts_GetNumFaces;
|
||||
sInterface.m_getNumVerticesOfFace = emdm_ts_GetNumVertsOfFace;
|
||||
sInterface.m_getPosition = emdm_ts_GetPosition;
|
||||
sInterface.m_getTexCoord = emdm_ts_GetTextureCoordinate;
|
||||
sInterface.m_getNormal = emdm_ts_GetNormal;
|
||||
sInterface.m_setTSpaceBasic = emdm_ts_SetTSpace;
|
||||
sInterface.m_setTSpace = nullptr;
|
||||
/* 0 if failed */
|
||||
genTangSpaceDefault(&sContext);
|
||||
}
|
||||
SGLSLEditMeshToTangent *mesh_data = static_cast<SGLSLEditMeshToTangent *>(taskdata);
|
||||
|
||||
mikk::Mikktspace<SGLSLEditMeshToTangent> mikk(*mesh_data);
|
||||
mikk.genTangSpace();
|
||||
}
|
||||
|
||||
void BKE_editmesh_loop_tangent_calc(BMEditMesh *em,
|
||||
|
@ -392,7 +288,7 @@ void BKE_editmesh_loop_tangent_calc(BMEditMesh *em,
|
|||
}
|
||||
BM_mesh_elem_index_ensure(bm, htype_index);
|
||||
|
||||
mesh2tangent->looptris = (const BMLoop *(*)[3])(em->looptris);
|
||||
mesh2tangent->looptris = (const BMLoop *(*)[3])em->looptris;
|
||||
mesh2tangent->tangent = static_cast<float(*)[4]>(loopdata_out->layers[index].data);
|
||||
|
||||
BLI_task_pool_push(
|
||||
|
|
|
@ -27,16 +27,46 @@
|
|||
#include "BLI_strict_flags.h"
|
||||
|
||||
#include "atomic_ops.h"
|
||||
#include "mikktspace.h"
|
||||
#include "mikktspace.hh"
|
||||
|
||||
/* -------------------------------------------------------------------- */
|
||||
/** \name Mesh Tangent Calculations (Single Layer)
|
||||
* \{ */
|
||||
|
||||
/* Tangent space utils. */
|
||||
|
||||
/* User data. */
|
||||
struct BKEMeshToTangent {
|
||||
uint GetNumFaces()
|
||||
{
|
||||
return (uint)num_polys;
|
||||
}
|
||||
|
||||
uint GetNumVerticesOfFace(const uint face_num)
|
||||
{
|
||||
return (uint)mpolys[face_num].totloop;
|
||||
}
|
||||
|
||||
mikk::float3 GetPosition(const uint face_num, const uint vert_num)
|
||||
{
|
||||
const uint loop_idx = (uint)mpolys[face_num].loopstart + vert_num;
|
||||
return mikk::float3(mverts[mloops[loop_idx].v].co);
|
||||
}
|
||||
|
||||
mikk::float3 GetTexCoord(const uint face_num, const uint vert_num)
|
||||
{
|
||||
const float *uv = luvs[(uint)mpolys[face_num].loopstart + vert_num].uv;
|
||||
return mikk::float3(uv[0], uv[1], 1.0f);
|
||||
}
|
||||
|
||||
mikk::float3 GetNormal(const uint face_num, const uint vert_num)
|
||||
{
|
||||
return mikk::float3(lnors[(uint)mpolys[face_num].loopstart + vert_num]);
|
||||
}
|
||||
|
||||
void SetTangentSpace(const uint face_num, const uint vert_num, mikk::float3 T, bool orientation)
|
||||
{
|
||||
float *p_res = tangents[(uint)mpolys[face_num].loopstart + vert_num];
|
||||
copy_v4_fl4(p_res, T.x, T.y, T.z, orientation ? 1.0f : -1.0f);
|
||||
}
|
||||
|
||||
const MPoly *mpolys; /* faces */
|
||||
const MLoop *mloops; /* faces's vertices */
|
||||
const MVert *mverts; /* vertices */
|
||||
|
@ -46,59 +76,6 @@ struct BKEMeshToTangent {
|
|||
int num_polys; /* number of polygons */
|
||||
};
|
||||
|
||||
/* Mikktspace's API */
|
||||
static int get_num_faces(const SMikkTSpaceContext *pContext)
|
||||
{
|
||||
BKEMeshToTangent *p_mesh = static_cast<BKEMeshToTangent *>(pContext->m_pUserData);
|
||||
return p_mesh->num_polys;
|
||||
}
|
||||
|
||||
static int get_num_verts_of_face(const SMikkTSpaceContext *pContext, const int face_idx)
|
||||
{
|
||||
BKEMeshToTangent *p_mesh = static_cast<BKEMeshToTangent *>(pContext->m_pUserData);
|
||||
return p_mesh->mpolys[face_idx].totloop;
|
||||
}
|
||||
|
||||
static void get_position(const SMikkTSpaceContext *pContext,
|
||||
float r_co[3],
|
||||
const int face_idx,
|
||||
const int vert_idx)
|
||||
{
|
||||
BKEMeshToTangent *p_mesh = static_cast<BKEMeshToTangent *>(pContext->m_pUserData);
|
||||
const int loop_idx = p_mesh->mpolys[face_idx].loopstart + vert_idx;
|
||||
copy_v3_v3(r_co, p_mesh->mverts[p_mesh->mloops[loop_idx].v].co);
|
||||
}
|
||||
|
||||
static void get_texture_coordinate(const SMikkTSpaceContext *pContext,
|
||||
float r_uv[2],
|
||||
const int face_idx,
|
||||
const int vert_idx)
|
||||
{
|
||||
BKEMeshToTangent *p_mesh = static_cast<BKEMeshToTangent *>(pContext->m_pUserData);
|
||||
copy_v2_v2(r_uv, p_mesh->luvs[p_mesh->mpolys[face_idx].loopstart + vert_idx].uv);
|
||||
}
|
||||
|
||||
static void get_normal(const SMikkTSpaceContext *pContext,
|
||||
float r_no[3],
|
||||
const int face_idx,
|
||||
const int vert_idx)
|
||||
{
|
||||
BKEMeshToTangent *p_mesh = static_cast<BKEMeshToTangent *>(pContext->m_pUserData);
|
||||
copy_v3_v3(r_no, p_mesh->lnors[p_mesh->mpolys[face_idx].loopstart + vert_idx]);
|
||||
}
|
||||
|
||||
static void set_tspace(const SMikkTSpaceContext *pContext,
|
||||
const float fv_tangent[3],
|
||||
const float face_sign,
|
||||
const int face_idx,
|
||||
const int vert_idx)
|
||||
{
|
||||
BKEMeshToTangent *p_mesh = static_cast<BKEMeshToTangent *>(pContext->m_pUserData);
|
||||
float *p_res = p_mesh->tangents[p_mesh->mpolys[face_idx].loopstart + vert_idx];
|
||||
copy_v3_v3(p_res, fv_tangent);
|
||||
p_res[3] = face_sign;
|
||||
}
|
||||
|
||||
void BKE_mesh_calc_loop_tangent_single_ex(const MVert *mverts,
|
||||
const int UNUSED(numVerts),
|
||||
const MLoop *mloops,
|
||||
|
@ -110,23 +87,8 @@ void BKE_mesh_calc_loop_tangent_single_ex(const MVert *mverts,
|
|||
const int numPolys,
|
||||
ReportList *reports)
|
||||
{
|
||||
BKEMeshToTangent mesh_to_tangent;
|
||||
SMikkTSpaceContext s_context{};
|
||||
SMikkTSpaceInterface s_interface{};
|
||||
|
||||
const MPoly *mp;
|
||||
int mp_index;
|
||||
|
||||
/* First check we do have a tris/quads only mesh. */
|
||||
for (mp = mpolys, mp_index = 0; mp_index < numPolys; mp++, mp_index++) {
|
||||
if (mp->totloop > 4) {
|
||||
BKE_report(
|
||||
reports, RPT_ERROR, "Tangent space can only be computed for tris/quads, aborting");
|
||||
return;
|
||||
}
|
||||
}
|
||||
|
||||
/* Compute Mikktspace's tangent normals. */
|
||||
BKEMeshToTangent mesh_to_tangent;
|
||||
mesh_to_tangent.mpolys = mpolys;
|
||||
mesh_to_tangent.mloops = mloops;
|
||||
mesh_to_tangent.mverts = mverts;
|
||||
|
@ -135,20 +97,18 @@ void BKE_mesh_calc_loop_tangent_single_ex(const MVert *mverts,
|
|||
mesh_to_tangent.tangents = r_looptangent;
|
||||
mesh_to_tangent.num_polys = numPolys;
|
||||
|
||||
s_context.m_pUserData = &mesh_to_tangent;
|
||||
s_context.m_pInterface = &s_interface;
|
||||
s_interface.m_getNumFaces = get_num_faces;
|
||||
s_interface.m_getNumVerticesOfFace = get_num_verts_of_face;
|
||||
s_interface.m_getPosition = get_position;
|
||||
s_interface.m_getTexCoord = get_texture_coordinate;
|
||||
s_interface.m_getNormal = get_normal;
|
||||
s_interface.m_setTSpaceBasic = set_tspace;
|
||||
s_interface.m_setTSpace = nullptr;
|
||||
mikk::Mikktspace<BKEMeshToTangent> mikk(mesh_to_tangent);
|
||||
|
||||
/* 0 if failed */
|
||||
if (genTangSpaceDefault(&s_context) == false) {
|
||||
BKE_report(reports, RPT_ERROR, "Mikktspace failed to generate tangents for this mesh!");
|
||||
/* First check we do have a tris/quads only mesh. */
|
||||
for (int i = 0; i < numPolys; i++) {
|
||||
if (mpolys[i].totloop > 4) {
|
||||
BKE_report(
|
||||
reports, RPT_ERROR, "Tangent space can only be computed for tris/quads, aborting");
|
||||
return;
|
||||
}
|
||||
}
|
||||
|
||||
mikk.genTangSpace();
|
||||
}
|
||||
|
||||
void BKE_mesh_calc_loop_tangent_single(Mesh *mesh,
|
||||
|
@ -203,6 +163,121 @@ void BKE_mesh_calc_loop_tangent_single(Mesh *mesh,
|
|||
#define USE_LOOPTRI_DETECT_QUADS
|
||||
|
||||
struct SGLSLMeshToTangent {
|
||||
uint GetNumFaces()
|
||||
{
|
||||
#ifdef USE_LOOPTRI_DETECT_QUADS
|
||||
return (uint)num_face_as_quad_map;
|
||||
#else
|
||||
return (uint)numTessFaces;
|
||||
#endif
|
||||
}
|
||||
|
||||
uint GetNumVerticesOfFace(const uint face_num)
|
||||
{
|
||||
#ifdef USE_LOOPTRI_DETECT_QUADS
|
||||
if (face_as_quad_map) {
|
||||
const MLoopTri *lt = &looptri[face_as_quad_map[face_num]];
|
||||
const MPoly *mp = &mpoly[lt->poly];
|
||||
if (mp->totloop == 4) {
|
||||
return 4;
|
||||
}
|
||||
}
|
||||
return 3;
|
||||
#else
|
||||
UNUSED_VARS(pContext, face_num);
|
||||
return 3;
|
||||
#endif
|
||||
}
|
||||
|
||||
uint GetLoop(const uint face_num, const uint vert_num, const MLoopTri *<)
|
||||
{
|
||||
#ifdef USE_LOOPTRI_DETECT_QUADS
|
||||
if (face_as_quad_map) {
|
||||
lt = &looptri[face_as_quad_map[face_num]];
|
||||
const MPoly *mp = &mpoly[lt->poly];
|
||||
if (mp->totloop == 4) {
|
||||
return ((uint)mp->loopstart + vert_num);
|
||||
}
|
||||
/* fall through to regular triangle */
|
||||
}
|
||||
else {
|
||||
lt = &looptri[face_num];
|
||||
}
|
||||
#else
|
||||
lt = &looptri[face_num];
|
||||
#endif
|
||||
return lt->tri[vert_num];
|
||||
}
|
||||
|
||||
mikk::float3 GetPosition(const uint face_num, const uint vert_num)
|
||||
{
|
||||
const MLoopTri *lt;
|
||||
uint loop_index = GetLoop(face_num, vert_num, lt);
|
||||
return mikk::float3(mvert[mloop[loop_index].v].co);
|
||||
}
|
||||
|
||||
mikk::float3 GetTexCoord(const uint face_num, const uint vert_num)
|
||||
{
|
||||
const MLoopTri *lt;
|
||||
uint loop_index = GetLoop(face_num, vert_num, lt);
|
||||
if (mloopuv != nullptr) {
|
||||
const float *uv = mloopuv[loop_index].uv;
|
||||
return mikk::float3(uv[0], uv[1], 1.0f);
|
||||
}
|
||||
else {
|
||||
const float *l_orco = orco[mloop[loop_index].v];
|
||||
float u, v;
|
||||
map_to_sphere(&u, &v, l_orco[0], l_orco[1], l_orco[2]);
|
||||
return mikk::float3(u, v, 1.0f);
|
||||
}
|
||||
}
|
||||
|
||||
mikk::float3 GetNormal(const uint face_num, const uint vert_num)
|
||||
{
|
||||
const MLoopTri *lt;
|
||||
uint loop_index = GetLoop(face_num, vert_num, lt);
|
||||
if (precomputedLoopNormals) {
|
||||
return mikk::float3(precomputedLoopNormals[loop_index]);
|
||||
}
|
||||
else if ((mpoly[lt->poly].flag & ME_SMOOTH) == 0) { /* flat */
|
||||
if (precomputedFaceNormals) {
|
||||
return mikk::float3(precomputedFaceNormals[lt->poly]);
|
||||
}
|
||||
else {
|
||||
#ifdef USE_LOOPTRI_DETECT_QUADS
|
||||
const MPoly *mp = &mpoly[lt->poly];
|
||||
float normal[3];
|
||||
if (mp->totloop == 4) {
|
||||
normal_quad_v3(normal,
|
||||
mvert[mloop[mp->loopstart + 0].v].co,
|
||||
mvert[mloop[mp->loopstart + 1].v].co,
|
||||
mvert[mloop[mp->loopstart + 2].v].co,
|
||||
mvert[mloop[mp->loopstart + 3].v].co);
|
||||
}
|
||||
else
|
||||
#endif
|
||||
{
|
||||
normal_tri_v3(normal,
|
||||
mvert[mloop[lt->tri[0]].v].co,
|
||||
mvert[mloop[lt->tri[1]].v].co,
|
||||
mvert[mloop[lt->tri[2]].v].co);
|
||||
}
|
||||
return mikk::float3(normal);
|
||||
}
|
||||
}
|
||||
else {
|
||||
return mikk::float3(vert_normals[mloop[loop_index].v]);
|
||||
}
|
||||
}
|
||||
|
||||
void SetTangentSpace(const uint face_num, const uint vert_num, mikk::float3 T, bool orientation)
|
||||
{
|
||||
const MLoopTri *lt;
|
||||
uint loop_index = GetLoop(face_num, vert_num, lt);
|
||||
|
||||
copy_v4_fl4(tangent[loop_index], T.x, T.y, T.z, orientation ? 1.0f : -1.0f);
|
||||
}
|
||||
|
||||
const float (*precomputedFaceNormals)[3];
|
||||
const float (*precomputedLoopNormals)[3];
|
||||
const MLoopTri *looptri;
|
||||
|
@ -223,228 +298,12 @@ struct SGLSLMeshToTangent {
|
|||
#endif
|
||||
};
|
||||
|
||||
/* interface */
|
||||
static int dm_ts_GetNumFaces(const SMikkTSpaceContext *pContext)
|
||||
{
|
||||
SGLSLMeshToTangent *pMesh = static_cast<SGLSLMeshToTangent *>(pContext->m_pUserData);
|
||||
|
||||
#ifdef USE_LOOPTRI_DETECT_QUADS
|
||||
return pMesh->num_face_as_quad_map;
|
||||
#else
|
||||
return pMesh->numTessFaces;
|
||||
#endif
|
||||
}
|
||||
|
||||
static int dm_ts_GetNumVertsOfFace(const SMikkTSpaceContext *pContext, const int face_num)
|
||||
{
|
||||
#ifdef USE_LOOPTRI_DETECT_QUADS
|
||||
SGLSLMeshToTangent *pMesh = static_cast<SGLSLMeshToTangent *>(pContext->m_pUserData);
|
||||
if (pMesh->face_as_quad_map) {
|
||||
const MLoopTri *lt = &pMesh->looptri[pMesh->face_as_quad_map[face_num]];
|
||||
const MPoly *mp = &pMesh->mpoly[lt->poly];
|
||||
if (mp->totloop == 4) {
|
||||
return 4;
|
||||
}
|
||||
}
|
||||
return 3;
|
||||
#else
|
||||
UNUSED_VARS(pContext, face_num);
|
||||
return 3;
|
||||
#endif
|
||||
}
|
||||
|
||||
static void dm_ts_GetPosition(const SMikkTSpaceContext *pContext,
|
||||
float r_co[3],
|
||||
const int face_num,
|
||||
const int vert_index)
|
||||
{
|
||||
// assert(vert_index >= 0 && vert_index < 4);
|
||||
SGLSLMeshToTangent *pMesh = static_cast<SGLSLMeshToTangent *>(pContext->m_pUserData);
|
||||
const MLoopTri *lt;
|
||||
uint loop_index;
|
||||
const float *co;
|
||||
|
||||
#ifdef USE_LOOPTRI_DETECT_QUADS
|
||||
if (pMesh->face_as_quad_map) {
|
||||
lt = &pMesh->looptri[pMesh->face_as_quad_map[face_num]];
|
||||
const MPoly *mp = &pMesh->mpoly[lt->poly];
|
||||
if (mp->totloop == 4) {
|
||||
loop_index = (uint)(mp->loopstart + vert_index);
|
||||
goto finally;
|
||||
}
|
||||
/* fall through to regular triangle */
|
||||
}
|
||||
else {
|
||||
lt = &pMesh->looptri[face_num];
|
||||
}
|
||||
#else
|
||||
lt = &pMesh->looptri[face_num];
|
||||
#endif
|
||||
loop_index = lt->tri[vert_index];
|
||||
|
||||
finally:
|
||||
co = pMesh->mvert[pMesh->mloop[loop_index].v].co;
|
||||
copy_v3_v3(r_co, co);
|
||||
}
|
||||
|
||||
static void dm_ts_GetTextureCoordinate(const SMikkTSpaceContext *pContext,
|
||||
float r_uv[2],
|
||||
const int face_num,
|
||||
const int vert_index)
|
||||
{
|
||||
// assert(vert_index >= 0 && vert_index < 4);
|
||||
SGLSLMeshToTangent *pMesh = static_cast<SGLSLMeshToTangent *>(pContext->m_pUserData);
|
||||
const MLoopTri *lt;
|
||||
uint loop_index;
|
||||
|
||||
#ifdef USE_LOOPTRI_DETECT_QUADS
|
||||
if (pMesh->face_as_quad_map) {
|
||||
lt = &pMesh->looptri[pMesh->face_as_quad_map[face_num]];
|
||||
const MPoly *mp = &pMesh->mpoly[lt->poly];
|
||||
if (mp->totloop == 4) {
|
||||
loop_index = (uint)(mp->loopstart + vert_index);
|
||||
goto finally;
|
||||
}
|
||||
/* fall through to regular triangle */
|
||||
}
|
||||
else {
|
||||
lt = &pMesh->looptri[face_num];
|
||||
}
|
||||
#else
|
||||
lt = &pMesh->looptri[face_num];
|
||||
#endif
|
||||
loop_index = lt->tri[vert_index];
|
||||
|
||||
finally:
|
||||
if (pMesh->mloopuv != nullptr) {
|
||||
const float *uv = pMesh->mloopuv[loop_index].uv;
|
||||
copy_v2_v2(r_uv, uv);
|
||||
}
|
||||
else {
|
||||
const float *orco = pMesh->orco[pMesh->mloop[loop_index].v];
|
||||
map_to_sphere(&r_uv[0], &r_uv[1], orco[0], orco[1], orco[2]);
|
||||
}
|
||||
}
|
||||
|
||||
static void dm_ts_GetNormal(const SMikkTSpaceContext *pContext,
|
||||
float r_no[3],
|
||||
const int face_num,
|
||||
const int vert_index)
|
||||
{
|
||||
// assert(vert_index >= 0 && vert_index < 4);
|
||||
SGLSLMeshToTangent *pMesh = static_cast<SGLSLMeshToTangent *>(pContext->m_pUserData);
|
||||
const MLoopTri *lt;
|
||||
uint loop_index;
|
||||
|
||||
#ifdef USE_LOOPTRI_DETECT_QUADS
|
||||
if (pMesh->face_as_quad_map) {
|
||||
lt = &pMesh->looptri[pMesh->face_as_quad_map[face_num]];
|
||||
const MPoly *mp = &pMesh->mpoly[lt->poly];
|
||||
if (mp->totloop == 4) {
|
||||
loop_index = (uint)(mp->loopstart + vert_index);
|
||||
goto finally;
|
||||
}
|
||||
/* fall through to regular triangle */
|
||||
}
|
||||
else {
|
||||
lt = &pMesh->looptri[face_num];
|
||||
}
|
||||
#else
|
||||
lt = &pMesh->looptri[face_num];
|
||||
#endif
|
||||
loop_index = lt->tri[vert_index];
|
||||
|
||||
finally:
|
||||
if (pMesh->precomputedLoopNormals) {
|
||||
copy_v3_v3(r_no, pMesh->precomputedLoopNormals[loop_index]);
|
||||
}
|
||||
else if ((pMesh->mpoly[lt->poly].flag & ME_SMOOTH) == 0) { /* flat */
|
||||
if (pMesh->precomputedFaceNormals) {
|
||||
copy_v3_v3(r_no, pMesh->precomputedFaceNormals[lt->poly]);
|
||||
}
|
||||
else {
|
||||
#ifdef USE_LOOPTRI_DETECT_QUADS
|
||||
const MPoly *mp = &pMesh->mpoly[lt->poly];
|
||||
if (mp->totloop == 4) {
|
||||
normal_quad_v3(r_no,
|
||||
pMesh->mvert[pMesh->mloop[mp->loopstart + 0].v].co,
|
||||
pMesh->mvert[pMesh->mloop[mp->loopstart + 1].v].co,
|
||||
pMesh->mvert[pMesh->mloop[mp->loopstart + 2].v].co,
|
||||
pMesh->mvert[pMesh->mloop[mp->loopstart + 3].v].co);
|
||||
}
|
||||
else
|
||||
#endif
|
||||
{
|
||||
normal_tri_v3(r_no,
|
||||
pMesh->mvert[pMesh->mloop[lt->tri[0]].v].co,
|
||||
pMesh->mvert[pMesh->mloop[lt->tri[1]].v].co,
|
||||
pMesh->mvert[pMesh->mloop[lt->tri[2]].v].co);
|
||||
}
|
||||
}
|
||||
}
|
||||
else {
|
||||
copy_v3_v3(r_no, pMesh->vert_normals[pMesh->mloop[loop_index].v]);
|
||||
}
|
||||
}
|
||||
|
||||
static void dm_ts_SetTSpace(const SMikkTSpaceContext *pContext,
|
||||
const float fvTangent[3],
|
||||
const float fSign,
|
||||
const int face_num,
|
||||
const int vert_index)
|
||||
{
|
||||
// assert(vert_index >= 0 && vert_index < 4);
|
||||
SGLSLMeshToTangent *pMesh = static_cast<SGLSLMeshToTangent *>(pContext->m_pUserData);
|
||||
const MLoopTri *lt;
|
||||
uint loop_index;
|
||||
|
||||
#ifdef USE_LOOPTRI_DETECT_QUADS
|
||||
if (pMesh->face_as_quad_map) {
|
||||
lt = &pMesh->looptri[pMesh->face_as_quad_map[face_num]];
|
||||
const MPoly *mp = &pMesh->mpoly[lt->poly];
|
||||
if (mp->totloop == 4) {
|
||||
loop_index = (uint)(mp->loopstart + vert_index);
|
||||
goto finally;
|
||||
}
|
||||
/* fall through to regular triangle */
|
||||
}
|
||||
else {
|
||||
lt = &pMesh->looptri[face_num];
|
||||
}
|
||||
#else
|
||||
lt = &pMesh->looptri[face_num];
|
||||
#endif
|
||||
loop_index = lt->tri[vert_index];
|
||||
|
||||
float *pRes;
|
||||
|
||||
finally:
|
||||
pRes = pMesh->tangent[loop_index];
|
||||
copy_v3_v3(pRes, fvTangent);
|
||||
pRes[3] = fSign;
|
||||
}
|
||||
|
||||
static void DM_calc_loop_tangents_thread(TaskPool *__restrict UNUSED(pool), void *taskdata)
|
||||
{
|
||||
SGLSLMeshToTangent *mesh2tangent = static_cast<SGLSLMeshToTangent *>(taskdata);
|
||||
/* new computation method */
|
||||
{
|
||||
SMikkTSpaceContext sContext{};
|
||||
SMikkTSpaceInterface sInterface{};
|
||||
SGLSLMeshToTangent *mesh_data = static_cast<SGLSLMeshToTangent *>(taskdata);
|
||||
|
||||
sContext.m_pUserData = mesh2tangent;
|
||||
sContext.m_pInterface = &sInterface;
|
||||
sInterface.m_getNumFaces = dm_ts_GetNumFaces;
|
||||
sInterface.m_getNumVerticesOfFace = dm_ts_GetNumVertsOfFace;
|
||||
sInterface.m_getPosition = dm_ts_GetPosition;
|
||||
sInterface.m_getTexCoord = dm_ts_GetTextureCoordinate;
|
||||
sInterface.m_getNormal = dm_ts_GetNormal;
|
||||
sInterface.m_setTSpaceBasic = dm_ts_SetTSpace;
|
||||
sInterface.m_setTSpace = nullptr;
|
||||
|
||||
/* 0 if failed */
|
||||
genTangSpaceDefault(&sContext);
|
||||
}
|
||||
mikk::Mikktspace<SGLSLMeshToTangent> mikk(*mesh_data);
|
||||
mikk.genTangSpace();
|
||||
}
|
||||
|
||||
void BKE_mesh_add_loop_tangent_named_layer_for_uv(CustomData *uv_data,
|
||||
|
|
Loading…
Reference in New Issue