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

1 files changed, 0 insertions, 152 deletions

diff --git a/intern/mikktspace/mikktspace.h b/intern/mikktspace/mikktspace.h
deleted file mode 100644
index 30c0584c2fb..00000000000
--- a/intern/mikktspace/mikktspace.h
+++ /dev/null
@@ -1,152 +0,0 @@
-/* SPDX-License-Identifier: Zlib
- * Copyright 2011 by Morten S. Mikkelsen. */
-
-/** \file
- * \ingroup mikktspace
- */
-
-#ifndef __MIKKTSPACE_H__
-#define __MIKKTSPACE_H__
-
-#ifdef __cplusplus
-extern "C" {
-#endif
-
-/* Author: Morten S. Mikkelsen
- * Version: 1.0
- *
- * The files mikktspace.h and mikktspace.c are designed to be
- * stand-alone files and it is important that they are kept this way.
- * Not having dependencies on structures/classes/libraries specific
- * to the program, in which they are used, allows them to be copied
- * and used as is into any tool, program or plugin.
- * The code is designed to consistently generate the same
- * tangent spaces, for a given mesh, in any tool in which it is used.
- * This is done by performing an internal welding step and subsequently an order-independent
- * evaluation of tangent space for meshes consisting of triangles and quads.
- * This means faces can be received in any order and the same is true for
- * the order of vertices of each face. The generated result will not be affected
- * by such reordering. Additionally, whether degenerate (vertices or texture coordinates)
- * primitives are present or not will not affect the generated results either.
- * Once tangent space calculation is done the vertices of degenerate primitives will simply
- * inherit tangent space from neighboring non degenerate primitives.
- * The analysis behind this implementation can be found in my master's thesis
- * which is available for download --> http://image.diku.dk/projects/media/morten.mikkelsen.08.pdf
- * Note that though the tangent spaces at the vertices are generated in an order-independent way,
- * by this implementation, the interpolated tangent space is still affected by which diagonal is
- * chosen to split each quad. A sensible solution is to have your tools pipeline always
- * split quads by the shortest diagonal. This choice is order-independent and works with mirroring.
- * If these have the same length then compare the diagonals defined by the texture coordinates.
- * XNormal which is a tool for baking normal maps allows you to write your own tangent space plugin
- * and also quad triangulator plugin.
- */
-
-typedef int tbool;
-typedef struct SMikkTSpaceContext SMikkTSpaceContext;
-
-typedef struct {
-  // Returns the number of faces (triangles/quads) on the mesh to be processed.
-  int (*m_getNumFaces)(const SMikkTSpaceContext *pContext);
-
-  // Returns the number of vertices on face number iFace
-  // iFace is a number in the range {0, 1, ..., getNumFaces()-1}
-  int (*m_getNumVerticesOfFace)(const SMikkTSpaceContext *pContext, const int iFace);
-
-  // returns the position/normal/texcoord of the referenced face of vertex number iVert.
-  // iVert is in the range {0,1,2} for triangles and {0,1,2,3} for quads.
-  void (*m_getPosition)(const SMikkTSpaceContext *pContext,
-                        float fvPosOut[],
-                        const int iFace,
-                        const int iVert);
-  void (*m_getNormal)(const SMikkTSpaceContext *pContext,
-                      float fvNormOut[],
-                      const int iFace,
-                      const int iVert);
-  void (*m_getTexCoord)(const SMikkTSpaceContext *pContext,
-                        float fvTexcOut[],
-                        const int iFace,
-                        const int iVert);
-
-  // either (or both) of the two setTSpace callbacks can be set.
-  // The call-back m_setTSpaceBasic() is sufficient for basic normal mapping.
-
-  // This function is used to return the tangent and fSign to the application.
-  // fvTangent is a unit length vector.
-  // For normal maps it is sufficient to use the following simplified version of the bitangent
-  // which is generated at pixel/vertex level.
-  // bitangent = fSign * cross(vN, tangent);
-  // Note that the results are returned unindexed. It is possible to generate a new index list
-  // But averaging/overwriting tangent spaces by using an already existing index list WILL produce
-  // INCRORRECT results.
-  // DO NOT! use an already existing index list.
-  void (*m_setTSpaceBasic)(const SMikkTSpaceContext *pContext,
-                           const float fvTangent[],
-                           const float fSign,
-                           const int iFace,
-                           const int iVert);
-
-  // This function is used to return tangent space results to the application.
-  // fvTangent and fvBiTangent are unit length vectors and fMagS and fMagT are their
-  // true magnitudes which can be used for relief mapping effects.
-  // fvBiTangent is the "real" bitangent and thus may not be perpendicular to fvTangent.
-  // However, both are perpendicular to the vertex normal.
-  // For normal maps it is sufficient to use the following simplified version of the bitangent
-  // which is generated at pixel/vertex level.
-  // fSign = bIsOrientationPreserving ? 1.0f : (-1.0f);
-  // bitangent = fSign * cross(vN, tangent);
-  // Note that the results are returned unindexed. It is possible to generate a new index list
-  // But averaging/overwriting tangent spaces by using an already existing index list WILL produce
-  // INCRORRECT results. DO NOT! use an already existing index list.
-  void (*m_setTSpace)(const SMikkTSpaceContext *pContext,
-                      const float fvTangent[],
-                      const float fvBiTangent[],
-                      const float fMagS,
-                      const float fMagT,
-                      const tbool bIsOrientationPreserving,
-                      const int iFace,
-                      const int iVert);
-} SMikkTSpaceInterface;
-
-struct SMikkTSpaceContext {
-  // initialized with callback functions
-  SMikkTSpaceInterface *m_pInterface;
-  // pointer to client side mesh data etc.
-  // (passed as the first parameter with every interface call)
-  void *m_pUserData;
-};
-
-// these are both thread safe!
-// Default (recommended) fAngularThreshold is 180 degrees (which means threshold disabled)
-tbool genTangSpaceDefault(const SMikkTSpaceContext *pContext);
-tbool genTangSpace(const SMikkTSpaceContext *pContext, const float fAngularThreshold);
-
-// To avoid visual errors (distortions/unwanted hard edges in lighting), when using sampled normal
-// maps, the normal map sampler must use the exact inverse of the pixel shader transformation.
-// The most efficient transformation we can possibly do in the pixel shader is achieved by using,
-// directly, the "unnormalized" interpolated tangent, bitangent and vertex normal: vT, vB and vN.
-// pixel shader (fast transform out)
-// vNout = normalize( vNt.x * vT + vNt.y * vB + vNt.z * vN );
-// where vNt is the tangent space normal. The normal map sampler must likewise use the
-// interpolated and "unnormalized" tangent, bitangent and vertex normal to be compliant with the
-// pixel shader. sampler does (exact inverse of pixel shader):
-// float3 row0 = cross(vB, vN);
-// float3 row1 = cross(vN, vT);
-// float3 row2 = cross(vT, vB);
-// float fSign = dot(vT, row0)<0 ? -1 : 1;
-// vNt = normalize( fSign * float3(dot(vNout,row0), dot(vNout,row1), dot(vNout,row2)) );
-// where vNout is the sampled normal in some chosen 3D space.
-//
-// Should you choose to reconstruct the bitangent in the pixel shader instead
-// of the vertex shader, as explained earlier, then be sure to do this in the normal map sampler
-// also. Finally, beware of quad triangulations. If the normal map sampler doesn't use the same
-// triangulation of quads as your renderer then problems will occur since the interpolated tangent
-// spaces will differ eventhough the vertex level tangent spaces match. This can be solved either
-// by triangulating before sampling/exporting or by using the order-independent choice of diagonal
-// for splitting quads suggested earlier. However, this must be used both by the sampler and your
-// tools/rendering pipeline.
-
-#ifdef __cplusplus
-}
-#endif
-
-#endif