starseeker (Dec 01 2023 at 14:48): starseeker (Dec 01 2023 at 14:48):@Alexis Naveros Am I correct that if we were going to set up a "make install" rule for the meshdecimation code as a library, only the meshdecimation.h header would need to be installed? (I.e. the rest are needed only at compile time?)
Alexis Naveros (Dec 01 2023 at 18:26):Hey. Yes, that's correct. Although I'm reusing many of these extra files in about everything I write, so you could either strip the symbols or handle reuse (box collapse algorithm will use them)
Alexis Naveros (Dec 01 2023 at 18:30):Oh by the way, something that might perhaps be of general interest: the included cchash.h
The story is that I needed hash tables for billions of items, my hash functions were performing... poorly. So I wrote some very exhaustive statistical analysis, in order to find the "best" hash functions.
Surprising twist of the story: every hash function I could find failed my statistical analysis, including the built-in hash functions for many popular languages (for their dictionaries or whatever)
starseeker (Dec 01 2023 at 18:31):My initial thought was to create a "mmesh" library that could supply both algorithms - then we can just reuse the common files for building both.
Oh - did you see my question about the mmthread.c file?
Alexis Naveros (Dec 01 2023 at 18:32):So... I wrote some genetic algorithm that would converge on functions that would maximize the statistical analysis score, while being the cheapest possible for CPUs to run. cchash.h is the result, to me they are the "perfect" hash functions. Maybe you want to reuse them somewhere
starseeker (Dec 01 2023 at 18:32):Sweet!
Alexis Naveros (Dec 01 2023 at 18:32):Yes, mmthread.c wasn't necessary, it's only using the static inline functions in mmthread.h
starseeker (Dec 01 2023 at 18:33):OK, I'll set up a BRL-CAD/mmesh github project and get the CMake and DLL import/export foo going.
Alexis Naveros (Dec 01 2023 at 18:33):All right, cool
starseeker (Dec 01 2023 at 18:34):Will be basic initially - compiler flags for optimization can come once the basic setup is in place. Any recommendations for what might constitute good functionality/regression testing, beyond just tossing in a mesh and running the algorithm?
Alexis Naveros (Dec 01 2023 at 18:36):The best benchmark would be evaluating the change of "shape" for the object, comparing before and after. I have that somewhere but it's heavy. I would just toss a mesh ;)
Alexis Naveros (Dec 01 2023 at 18:43):Oh, and give cchash.h a try, it really made a nice difference for me in a bunch of projects. If I were in academia, it would be worth a paper or something, but I'm not
starseeker (Dec 01 2023 at 18:44):I've been using xxhash, but it sounds like your cchash would be a step up
starseeker (Dec 01 2023 at 18:51):https://github.com/BRL-CAD/mmesh is up
starseeker (Dec 01 2023 at 18:52):@Alexis Naveros Would you like to throw together a README for it? I can rough in something basic, but if you're interested it seems more fitting for you to create it
Alexis Naveros (Dec 01 2023 at 18:56):Hrm. I guess that would be a good idea. I usually just document the .h
starseeker (Dec 01 2023 at 19:06):@Alexis Naveros are you able to see build results here? https://github.com/BRL-CAD/mmesh/actions
starseeker (Dec 01 2023 at 19:09):Looks like MSVC and Mac are unhappy out of the gate
Alexis Naveros (Dec 01 2023 at 19:11):I never cared much about either, but yes, it would be good to fix that. Can that emit compiler output error messages?
starseeker (Dec 01 2023 at 19:12):Yes - the logs are generated. If you can't see them I can post them
starseeker (Dec 01 2023 at 19:13):First MSVC error in various files:
src\meshdecimation.c(1431,3): error C2059: syntax error: '{' [D:\a\mmesh\mmesh\build\src\mmesh.vcxproj]
src\mmhashinternal.h(52,28): error C2054: expected '(' to follow 'mmHashPage' [D:\a\mmesh\mmesh\build\src\mmesh.vcxproj]
starseeker (Dec 01 2023 at 19:16):OSX:
In file included from /Users/runner/work/mmesh/mmesh/src/meshdecimation.c:298:
/Users/runner/work/mmesh/mmesh/src/mathshewchuk.h:46:15: warning: unknown attribute '__optimize__' ignored [-Wunknown-attributes]
static inline CC_STRICT_MATH void mathShewchukInit( mathShewchukSum *sum )
^~~~~~~~~~~~~~
/Users/runner/work/mmesh/mmesh/src/mathshewchuk.h:28:41: note: expanded from macro 'CC_STRICT_MATH'
#define CC_STRICT_MATH __attribute__((__optimize__("no-associative-math", "no-unsafe-math-optimizations", "no-fast-math")))
^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/Users/runner/work/mmesh/mmesh/src/mathshewchuk.h:53:15: warning: unknown attribute '__optimize__' ignored [-Wunknown-attributes]
static inline CC_STRICT_MATH void mathShewchukAdd( mathShewchukSum *sum, double x )
^~~~~~~~~~~~~~
/Users/runner/work/mmesh/mmesh/src/mathshewchuk.h:28:41: note: expanded from macro 'CC_STRICT_MATH'
#define CC_STRICT_MATH __attribute__((__optimize__("no-associative-math", "no-unsafe-math-optimizations", "no-fast-math")))
^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/Users/runner/work/mmesh/mmesh/src/mathshewchuk.h:84:15: warning: unknown attribute '__optimize__' ignored [-Wunknown-attributes]
static inline CC_STRICT_MATH void mathShewchukMultiply( mathShewchukSum *sum, double x )
^~~~~~~~~~~~~~
/Users/runner/work/mmesh/mmesh/src/mathshewchuk.h:28:41: note: expanded from macro 'CC_STRICT_MATH'
#define CC_STRICT_MATH __attribute__((__optimize__("no-associative-math", "no-unsafe-math-optimizations", "no-fast-math")))
^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/Users/runner/work/mmesh/mmesh/src/mathshewchuk.h:92:15: warning: unknown attribute '__optimize__' ignored [-Wunknown-attributes]
static inline CC_STRICT_MATH double mathShewchukTotal( mathShewchukSum *sum )
^~~~~~~~~~~~~~
/Users/runner/work/mmesh/mmesh/src/mathshewchuk.h:28:41: note: expanded from macro 'CC_STRICT_MATH'
#define CC_STRICT_MATH __attribute__((__optimize__("no-associative-math", "no-unsafe-math-optimizations", "no-fast-math")))
^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/Users/runner/work/mmesh/mmesh/src/meshdecimation.c:4366:5: warning: array index 3 is past the end of the array (which contains 3 elements) [-Warray-bounds]
vertex->point[3] = 0.0;
^ ~
/Users/runner/work/mmesh/mmesh/src/meshdecimation.c:805:3: note: array 'point' declared here
mdf point[3];
Alexis Naveros (Dec 01 2023 at 19:17):Oh hrm, I guess __declspec(align(64)) needs to be placed somewhere else in the declaration. That's me trying to be portable to MSVC without ever touching the thing
starseeker (Dec 01 2023 at 19:17):/Users/runner/work/mmesh/mmesh/src/mm.c:3017:49: error: use of undeclared identifier 'MAP_LOCKED'
2023-12-01T19:04:32.8918770Z mmapflags = MAP_PRIVATE | MAP_ANONYMOUS | MAP_LOCKED;
Alexis Naveros (Dec 01 2023 at 19:18):I thought clang supported GCC's __attribute__ syntax, but clearly not all of it. No MAP_LOCKED on OSX? Okay
Alexis Naveros (Dec 01 2023 at 19:18):mathshewchuk.h will be GCC only then. All other compilers will produce less accurate results
starseeker (Dec 01 2023 at 19:20):We might be able to ping some clang experts later and ask them how to do it there
Alexis Naveros (Dec 01 2023 at 19:31):So MSVC doesn't like this for some reason
#define MD_VectorCrossProduct(x,y,z) ({(x)[0]=((y)[1](z)[2])-((y)[2](z)[1]);(x)[1]=((y)[2](z)[0])-((y)[0](z)[2]);(x)[2]=((y)[0](z)[1])-((y)[1](z)[0]);})
I guess I'll convert everything to static inline. sigh
starseeker (Dec 01 2023 at 20:07):@Alexis Naveros OSX built, MSVC is failing with:
D:\a\mmesh\mmesh\src\meshdecimation.c(3324): error C2059: syntax error: '{'
D:\a\mmesh\mmesh\src\meshdecimation.c(3324): error C2143: syntax error: missing ';' before ')'
starseeker (Dec 01 2023 at 22:03):@Alexis Naveros Yep, that got it!
starseeker (Dec 01 2023 at 22:03):Noticed a warning from MSVC: src\mmhash.c(2340) : warning C4700: uninitialized local variable 'accumscore' used
Alexis Naveros (Dec 01 2023 at 22:05):Hey, that's a real warning, will fix that. You can just initialize to zero on your end. Nothing important, it's just in a debugging function (asking a hash table how healthy it's feeling today)
starseeker (Dec 01 2023 at 22:07):Done. Compile also succeed on FreeBSD.
Alexis Naveros (Dec 01 2023 at 22:08):(That health function can be used to check how well the hash function is working, it's the function that launched the long quest that ended up with cchash.h)
Alexis Naveros (Dec 01 2023 at 22:08):Cool, glad to hear it
starseeker (Dec 01 2023 at 22:11):Alpine Linux builds too. OpenBSD and HaikuOS are the other traditionally iffy platforms, but I'll have to check those next week.
starseeker (Dec 01 2023 at 22:13):Also will be time to hook it up under facetize and see how it does <grin> Looking forward to that.
starseeker (Dec 01 2023 at 22:56):@Alexis Naveros Looking at the code we are using in librt, there's also a "moOptimizeMesh" function that is run after the main decimation is complete. Is that still something we would want for the modern decimation implementation?
Alexis Naveros (Dec 01 2023 at 23:49):@starseeker It's unrelated to mesh decimation.
Mesh optimization is mostly optimizing the order of vertex indices to maximize the use of the GPU post-transform vertex caches. You can get a significant performance boost for rendering optimized meshes, when the GPU is a bit strained. Although note I have reused that same code in various non-GPU contexts, such as optimizing the vertex storage order in a graph for CPU pathfinding, boosting performance by 5% (better use of the CPU caches).
Alexis Naveros (Dec 01 2023 at 23:51):This is good code, I have had significant performance boosts by applying it on game-like models
starseeker (Dec 02 2023 at 04:24):Is there a version of moOptimizeMesh that we could include with the mmesh repo? I can try to refactor the one we have in librt to work with the modern support files if need be, but I'm not sure how tricky that would be - it probably dates to the same era as the ball-pivot code
Alexis Naveros (Dec 02 2023 at 04:25):Sure, sending that
Alexis Naveros (Dec 02 2023 at 04:42):On the topic of mesh manipulation, I have other algorithms... There's one to convert an indexed mesh into an indexed triangle strip, but highly optimized to minimize the count of swaps/jumps (it beats the numbers I found in some paper). Too bad no one cares about triangle strips anymore (in modern GPUs with large post-transform vertex caches, heavy vertex data, and expensive shaders, cache optimized indexed meshes are better than indexed strips in most cases).
Alexis Naveros (Dec 02 2023 at 04:44):I'm touching that topic because I have a question that only old timers who have played with IRIS GL 30 years ago could answer. ;) That code can generate GL/VK strips, but also "IRIS GL strips" where swaps are encoded in the top bit (handy when you really want to minimize memory usage for a 3D mesh, not necessarily draw the stuff)
starseeker (Dec 02 2023 at 04:44):Hmm. Our software fallback for OpenGL rendering is an old version of Mesa's swrast - I wonder if the CPU software rendering of that code would benefit from that sort of optimization.
Alexis Naveros (Dec 02 2023 at 04:44):My question is: was that actually how IRIS GL strips worked? I couldn't find the documentation, just some very indirect hints scattered over the place. I should change how it's called in the API if these are actually not IRIS GL strips
Alexis Naveros (Dec 02 2023 at 04:45):Mesh optimization for GPU post-transform vertex caches works best for gaming-like models, where you have heavy vertex data and complicated shaders. The gain will be small otherwise, but it's always something
starseeker (Dec 02 2023 at 04:49):Got a failure of the optimizer code on OSX:
Undefined symbols for architecture x86_64:
"_mtSleepBarrierDestroy", referenced from:
_moMeshOptimizationEnd in meshoptimizer.c.o
"_mtSleepBarrierInit", referenced from:
_moMeshOptimizationInit in meshoptimizer.c.o
"_mtSleepBarrierSync", referenced from:
_moMeshOptimizationThread in meshoptimizer.c.o
Alexis Naveros (Dec 02 2023 at 04:50):Oh. That's the mmthread.c I told you wasn't needed
starseeker (Dec 02 2023 at 04:50):heh :-)
starseeker (Dec 02 2023 at 04:50):MSVC is unhappy as well, but for a different reason:
D:\a\mmesh\mmesh\src\meshoptimizer.c(513): error C2059: syntax error: '{'
Alexis Naveros (Dec 02 2023 at 04:52):Once again it's the #define FOO ({...}) thing, fixing.
starseeker (Dec 02 2023 at 04:55):As far as IRIS GL is concerned, I'm afraid I'm not enough of an old-timer to have played with it myself. I don't know if anybody involved with the original implementation of our GL code would still be active online to ask.
Alexis Naveros (Dec 02 2023 at 04:56):Eh, I figured... It's not important, I just would like to get my terminology right, as a tiny homage to the SGI legacy
Alexis Naveros (Dec 02 2023 at 04:58):(I'm actually using these "IRIS GL" strips internally, I have had to reduce memory usage for meshes with billions of triangles... I'm running out of RAM with 256gb)
starseeker (Dec 02 2023 at 05:00):Looks like that got the compiler error on MSVC - now it's failing to link the same way OSX does.
Alexis Naveros (Dec 02 2023 at 05:00):Just bring back that mmthread.c, it's still in the first tarball I sent by email
starseeker (Dec 02 2023 at 05:01):OK. Should I use the same license statement as in the other files? (IIRC it was one of the ones that had the "don't distribute" statement.)
Alexis Naveros (Dec 02 2023 at 05:01):Yes. Sorry about that.
Alexis Naveros (Dec 02 2023 at 05:02):I would love to keep one copy for all these files I'm reusing everywhere, with symbolic links, but every project needs a different header. It's a mess
starseeker (Dec 02 2023 at 05:02):No worries - I just wanted to be sure, I'm twitchy about changing license statements myself without an explicit OK
starseeker (Dec 02 2023 at 05:06):OSX is now good. Windows is cranky about mmthread.c:
D:\a\mmesh\mmesh\src\mmthread.h(575): error C2037: left of 'tv_sec' specifies undefined struct/union 'timeval'
D:\a\mmesh\mmesh\src\mmthread.h(576): error C2037: left of 'tv_usec' specifies undefined struct/union 'timeval'
D:\a\mmesh\mmesh\src\mmthread.h(584): error C2079: 'lntime' uses undefined struct 'timeval'
D:\a\mmesh\mmesh\src\mmthread.h(585): warning C4133: 'function': incompatible types - from 'int *' to 'timeval *'
D:\a\mmesh\mmesh\src\mmthread.h(586): error C2224: left of '.tv_sec' must have struct/union type
D:\a\mmesh\mmesh\src\mmthread.h(586): error C2224: left of '.tv_usec' must have struct/union type
D:\a\mmesh\mmesh\src\mmthread.h(594): error C2079: 'lntime' uses undefined struct 'timeval'
D:\a\mmesh\mmesh\src\mmthread.h(595): warning C4133: 'function': incompatible types - from 'int *' to 'timeval *'
D:\a\mmesh\mmesh\src\mmthread.h(596): error C2224: left of '.tv_sec' must have struct/union type
D:\a\mmesh\mmesh\src\mmthread.h(596): error C2224: left of '.tv_usec' must have struct/union type
Alexis Naveros (Dec 02 2023 at 05:08):Urgh. But wait, that header was fine when #included for mesh decimation? Perhaps it's missing a Windows header
starseeker (Dec 02 2023 at 05:09):Maybe winsock.h? https://learn.microsoft.com/en-us/windows/win32/api/winsock/ns-winsock-timeval
I'll give that a shot
Alexis Naveros (Dec 02 2023 at 05:09):cc.h: #include <winsock2.h> /* For struct timeval, don't ask me how that makes any sense */
I love my old comments
Alexis Naveros (Dec 02 2023 at 05:10):Just #include mm.h before mmthread.h in mmthread.c and it's all good
starseeker (Dec 02 2023 at 05:13):That did the trick - we're clean on Windows, OSX and Linux again.
starseeker (Dec 02 2023 at 05:13):Checking BSD...
starseeker (Dec 02 2023 at 05:14):Yep, good there.
Alexis Naveros (Dec 02 2023 at 05:15):Cool. (Also fixed here, I'm all for writing portable code, it's just not frequently a concern)
starseeker (Dec 02 2023 at 05:16):I'll take a look next week (getting too tired to trust myself now) but I think that should be everything we need to allow for a straight up switch from the old embedded librt version to mmesh.
Alexis Naveros (Dec 02 2023 at 05:18):Great. And it's good you are making that code public somewhere. Frankly, I have a ton of code that I think is worth sharing, but I just don't want to maintain a github and do customer support
starseeker (Dec 02 2023 at 05:19):Oh - if you want to incorporate the define stuff for dll import/export, probably want to wait until I've done functionality testing with BRL-CAD to make sure all the linking bits work as expected. When I'm shooting blind on that stuff it's not uncommon for me to mess up the first time.
starseeker (Dec 02 2023 at 05:19):Our pleasure - thank you for sharing the improvements you've been making!
starseeker (Dec 02 2023 at 15:43):@Alexis Naveros question - a quick experiment suggests that it might not be all that hard to make mmesh compile as C++, in addition to C - looks like mostly needing to specify explicit type casts for void * -> something else assignments and fixing some cases where C++ doesn't allow static strings to be passed to things wanting (char *). Would there be any objections to doing that? (Might be interesting to see if there's any performance difference between a C and C++ build...)
starseeker (Dec 02 2023 at 15:45):Microsoft tends to put a lot more work into their C++ compiler, so one of BRL-CAD's longer term goals is to try and get our code to the point where everything can compile as C++ if we want to.
Alexis Naveros (Dec 02 2023 at 20:21):You are free to do so but, personally, I have no interest whatsoever in C++. I profoundly dislike the language. I hate how the code isn't explicit, it can be doing a bunch of things everywhere that you don't even see just by looking at the code. I hate how bloated the C++ standard library is (did you know they added garbage collection, then removed it because no one was using it?). C++ doesn't offer me anything that I want over my beloved C
starseeker (Nov 01 2024 at 15:09):@Alexis Naveros If you get a chance, we could use a little assistance integrating the new decimation code into librt
starseeker (Dec 31 2024 at 02:47):@Alexis Naveros Still have a few mmesh questions - any chance you'll have a window available where you could give us a quick hand?
Last updated: Jan 09 2025 at 00:46 UTC