Age | Commit message (Collapse) | Author |
|
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
|
|
The current code for computing tangents is not exactly fast.
This has been a long-standing issue, and recently came up again with T97378.
The main bottleneck is fetching the mesh data, since it's handled through a callback system and each vertex might have its data queried dozens of times.
I've tried a lot of things to optimize `mikktspace.c`, but unfortunately most weren't that useful:
- Vectorizing SVec3 gives a ~5% speedup, but I'm not sure if the additional ~70 lines of code are worth it
- Keeping an internal copy of the data instead of re-querying all the time helps a lot (~50-60% time reduction), but requires a lot of extra memory (~100 byte per face)
- Going C++ and replacing the internal quicksort with std::sort shows no difference
- Restructuring the entire file to be a header-only library so that the callbacks can be inlined gives ~10% reduction, but is a major change and deviation from the original library
In the end, two simple fixes that actually help remain:
- Don't re-query the number of faces in each loop iteration
- Don't bother looking for identical vertices if there's only one vertex with that hash
With this, time for the test case in T97378 goes from 6.64sec to 4.92sec. It's something I guess.
I feel like completely refactoring this library would not be a bad idea at some point, but for now it does the job...
Differential Revision: https://developer.blender.org/D14675
|
|
Mainly -Wset-but-unused-variable.
Makes default compilation on macOS way less noisy.
Differential Revision: https://developer.blender.org/D14357
|
|
|
|
|
|
|
|
|
|
Corrects incorrect usage of contraction for 'it is', when possessive 'its' was required.
Differential Revision: https://developer.blender.org/D9250
Reviewed by Campbell Barton
|
|
|
|
Ref D6677
|
|
Use an improved implementation for circular shift.
Differential Revision: https://developer.blender.org/D6677
|
|
|
|
|
|
|
|
Apply clang format as proposed in T53211.
For details on usage and instructions for migrating branches
without conflicts, see:
https://wiki.blender.org/wiki/Tools/ClangFormat
|
|
While \file doesn't need an argument, it can't have another doxy
command after it.
|
|
Move \ingroup onto same line to be more compact and
make it clear the file is in the group.
|
|
Previously, Mikktspace just bucketed the vertices based on one spatial coordinate and then ran full pairwise comparisons inside each bucket.
However, since models are three-dimensional, the bucketing has a massive false-positive rate, and since pairwise comparison is O(n^2), the merging process is very slow.
But, since we only care about exactly identical vertices, there is a much more efficient approach - we can just hash all values belonging to each vertex and form buckets based on the hash.
Since the hash has 32 bits and considers all values, false-positives are very unlikely - and since both hashing and the radixsort that's used for bucketing are O(n), both asymptotical and
real-world performance (as well as code complexity) are significantly improved.
|
|
with degenerated topology
Now we replace O(N^2) computational complexity with O(N) extra memory penalty.
Memory is much cheaper than CPU time. Keep in mind, memory penalty is like
4 megabytes per 1M vertices.
|
|
|
|
|
|
|
|
Don't use quick sort for small arrays, bubble sort works way faster for small
arrays due to cache coherency. This is what qsort() from libc is doing actually.
We can also experiment unrolling some extra small arrays, for example 3 and 4
element arrays.
This reduces tangent space calculation for dragon from 3.1sec to 2.9sec.
|
|
Brings tangent space calculation from 4.6sec to 3.1sec for dragon model in BI.
Cycles is also somewhat faster, but it has other bottlenecks.
Funny thing, using simple `static inline` already gives a lot of speedup here.
That's just answering question whether it's OK to leave decision on what to
inline up to a compiler..
|
|
Add a safe version of normalize since all uses of normalize
did zero length checks, move this into a function.
Also avoid unnecessary conversion.
Gives minor speedup here (approx 3-5%).
|
|
|
|
|
|
|
|
|
|
the error was that the range check was done on the float before converting to an int.
now convert to and int first and ensure a valid range on that.
|
|
intended, make local vars and functions static.
|
|
or good to keep for completeness. quieted some warnings and add flags -Wmissing-include-dirs and -Wno-div-by-zero to cmake/gcc
|
|
C with gcc.
helps for finding unused functions and making functions static, also did some minor code cleanup.
|
|
|
|
|
|
|
|
|
|
|
|
its such a common problem.
|
|
|
|
adjust to use floats.
+ minor update to demo_mode
|
|
|
|
|
|
|
|
If some plataform really needs malloc.h, that is the exception to get #ifdef.
|
|
FreeBSD. Patch attached.
also check for NetBSD.
note: we probably should use define HAVE_MALLOC_H, seems common for other projects.
|
|
This is a patch proposed by sparky_ on irc.
|
|
|
|
|
|
intended as a standalone library for use in other applications that
want the same tangent space as Blender.
This also keeps blenkernel clean(er) from extra math functions.
|