Welp, @starseeker the new facetize logic just saved me some effort. After nearly 24 hours processing, I got something where I would have gotten nothing:
NMG: tessellating my.ebm...
NMG: failed to generate my.bot
CM: error at size 0.883902
CM: retrying with size 0.0883902
CM: completed in 16 seconds with size 0.0883902
CM: completed in 20 seconds with size 0.0795512
CM: completed in 26 seconds with size 0.0715961
CM: timed out after 30 seconds with size 0.0644365
CM: unable to polygonize at target size (0.0662927), using last successful BoT with 2064364 faces, feature size 0.0715961
CM: decimation succeeded, final BoT has 55724 faces
Lots of bits missing including important details, but enough succeeded that I think I can make it work.
24 HOURS processing..... :)
memory usage never skyrocketed. I think it was just a lot of single-threaded O(N^3) iterations that made it take forever.
Hmm. Was it 24hrs on the NMG for my.ebm, or is my.ebm part of a larger model?
Unfortunately a timeout bail on NMG would be quite a lot of work... IIRC I looked at it back when I did the facetize setup. There's basically a whole lot of individual steps you would need to pass a time limit through. An alternative might be an environment variable, but the problem there would be checking that a whole lot in internal NMG routines. I never did id a path forward that didn't involve basically rewriting it...
Best answer I have so far would be a proper subprocess we could terminate, but that needs an over-the-wire communication of geometry to and from the subprocess.
Poor man's answer of keeping input to a tmp file and dbconcating the output back in might work to get up and running, but we would still need a subprocess based facetize command.
I didn't want it to bail out. If it would have succeeded, it would have been what I wanted. I apparently lost two orders of magnitude polys.
Which wasn't so bad, but then when I went to combine it with another bot, I again lost two more orders and now it's unusable:
mged> facetize tip2.bot tip2.r
NMG: tessellating tip2.r...
NMG: failed to generate tip2.bot
CM: error at size 28.4152
CM: retrying with size 2.84152
CM: error at size 2.84152
CM: retrying with size 1.42076
CM: error at size 1.42076
CM: retrying with size 0.710381
CM: completed in 4 seconds with size 0.710381
CM: successfully polygonized BoT with 150508 faces at feature size 0.497267
CM: decimation succeeded, final BoT has 7370 faces
I was originally just surprised that it worked the first time despite taking 24 hours. It probably was 24 hours on the nmg part. Don't know how long the other part took.
Is there any way to control the quality?
trying --feature-size 0.1
Well, I have to say I'm impressed - https://github.com/elalish/manifold managed to "facetize -r" an xpushed tire with tread successfully:
And it looks like it handled all the valid m35 truck cases as well. Neither case needing the fallback methods.
Not sure about havoc yet - it completes, but the results aren't right - first suspect is my tree walking though.
Ah, the tree walk was faulty. OK, getting more failure cases now. Still impressed it handled tire, but not handling all of m35 and crashing on havoc. Time to isolate some failure inputs.
Heh - forgot to support the trivial case, so a lot of simple things fail. Duh...
Incredible. Only 3 failed regions for facetize -r --MANIFOLD havoc h and only one of those regions shows a non-empty rt image.
To the best of my knowledge, this is the best facetization result that has ever been achieved with the havoc model.
I want to say I recall Havoc facetizing back in the early 2000's ... Around v5 days. Of course that was all pre-richard.. Need that dashboard to see if I'm just wearing rosy-colored history glasses. We do have an edge-case test set stashed somewhere with all possible combinations of two arbs that was set up for conversion testing.
Still that is impressive results. If there's a way to prevent/catch the crashes, I'd say toss it into the mix of multiple methods to try.
@Sean I was able to wrap it in a try/catch, so it looks like it'll work. I've got it wired in now, and building on Windows as well. CI says it builds on Mac as well but I've not tested it personally there.
You can give it a try with latest main if you like - for me, "facetize -r havoc h" succeeds with 1 NMG fallback (the two failures are both evaluate to empty regions). Ditto m35, and if I'm not mistaken this is overall quite fast compared to the NMG evaluations.
Hmm. I noticed an mistake on my part which is probably inflating the success rate of the new boolean logic for more complex cases - if the boolean evaluation fails, my logic was simply reporting an empty result and continuing onward. That resulted (for example) in havoc reporting a successful facetize at a top level, even though it should have failed on the known difficult region that requires NMG fallback.
Need to re-run and get new numbers
Wait... now I'm confused. I corrected the error returns, but the rt_booltree_evaluate accepts the TREE_NULL return from a nested call and keeps going. Looking at the nmg_booltree_evaluate I refactored that from, as far as I can tell that's also what it is doing... is the intent of this to ignore lower level failures and proceed?
I guess that sorta makes sense, as the facetize treewalk logic can't actually tell the difference between an empty bool eval result and a failure to generate output as long as both cases just return the same TREE_NULL result...
I don't know if this is related: I have a lot of geometries, imported from other CAD programs, with plate-mode bots. The tessellation of these objects is however not implemented at all. See rt_bot_tess() in src/librt/primitives/bot/bot.c. The function returns -1 for RT_BOT_PLATE.
It's separate from the booltree_evaluate question, but I'm actually working on the plate mode issue right now. Conversion of plate mode bots to explicit volumes is actually a very difficult problem in general. I'm trying what amounts to a brute force solution, but it's still a work in progress.
@Christopher Here's the ged_tessellate line I'm using:
bin/ged_tessellate --tol-abs 0.00000000000000000 --tol-rel 0.01000000000000000 --tol-norm 0.00000000000000000 --nmg --max-time 15 -O aet.g twisttrc.s
what's with all the trailing zeros...
copy / paste from a "%0.17f" sprintf
and that name could use some work, seems misleading to me as it's not a ged_*() function nor does it correspond with a ged command. If it's strictly a subprocess helper, it should probably not be installed in bin (libexec material).
I presume it was added to more gracefully handle facetizations methods that otherwise crash?
Correct. The command line is generated from the parent facetize command, so those numbers are simply printings of whatever the current tolerance settings are in the current MGED session. It's not normally meant to be edited by humans - it's a library-to-subprocess command line.
It's a subprocess helper. I haven't tried putting it in another location to run yet, so we'll have to see if that can work (particularly on Windows). The naming convention isn't set in stone - I just had to call it something, and the functionality is a) specific to libged and b) intended for internal use in the library's facetize command.
Christopher said:
copy / paste from a "%0.17f" sprintf
I think the desired specifier was maybe "%.17g" ?
I suppose you could argue for _ged_facetize_tessellate if we wanted to denote it as an internal tool for a specific libged command, but I haven't given that aspect much thought yet - I needed to prove the whole idea could work at all technically before the naming conventions became important. I think (knock on wood) it's looking like it can work, so it may be time now to think about that.
then yeah, sounds definitely libexec material. that's defined specifically for binaries/plugins that one might run from library or application code, not by users.
If we wanted to have a shorter string when printf can do something intelligent that'd be correct, but my first concern in that situation was recreating the exact floating point number stored in the parent libged tolerance struct in the child program. My understanding was the reliable way to do that was to put enough digits into the string to ensure per the standards that it would get read out and in the same way.
starseeker said:
I suppose you could argue for _ged_facetize_tessellate if we wanted to denote it as an internal tool for a specific libged command, but I haven't given that aspect much thought yet - I needed to prove the whole idea could work at all technically before the naming conventions became important. I think (knock on wood) it's looking like it can work, so it may be time now to think about that.
If you're at > 99% conversions.. that's not exactly in the realm of "proving the whole idea could work". That's well past proven.
I think everything in libexec right now is a .so/.dll file - I don't think we've figured out yet how to get an exe in there working portably.
starseeker said:
If we wanted to have a shorter string when printf can do something intelligent that'd be correct, but my first concern in that situation was recreating the exact floating point number stored in the parent libged tolerance struct in the child program. My understanding was the reliable way to do that was to put enough digits into the string to ensure per the standards that it would get read out and in the same way.
I got that intent, but that doesn't explain the trailing zeros.. :)
there's no parsing difference I'm aware of between 0.0 and 0.00000000 in any fathomable situation :)
Well, I'm at >99% on one platform - ubuntu linux. With the subprocess tricks, I figured I needed to show it working on at least Linux, Windows and Mac before it could be considered a serious candidate
%g trims trailing zeros, which is why I suggested that -- and I think still applies the same precision requested
Does reading in the string "0" into memory always result in an exact floating point zero? I'm not sure what the exact rules are for that. My only recollection on that topic from back in the day was there's a whole bunch of ways to get it wrong, and since those command lines aren't for humans anyway I wasn't too worried about it. If there's no danger we can certainly go with %g.
The trailing zeros are fine, just a curiosity. I don't think there's any situation where %.17g won't parse back exactly what you wrote. It will resort to scientific notation if the number is really big or really small, but that will still parse back in to the precision that was printed. Not a big deal either way.
Reading in a zero will always be exact floating point zero (i.e., all bits zero) as far as I know and have ever seen. That absolutely holds for IEEE 754, but also non 754's predating.
OK. I think I got the %0.17f bit from back when I was exploring the what and why of std::max_digits10: https://stackoverflow.com/a/22458961/2037687
@Sean I'm down with trying to figure out how to get executables into libexec for these purposes, but I do know I tried to figure out something similar on Windows at least once before, many years back, and struck out. I might have better luck now, but it's basically the "how do you keep a .exe in one place and .dll files in another" problem, and that's one I still don't know the "right" answer for yet.
Guess we would start here: https://learn.microsoft.com/en-us/windows/win32/dlls/dynamic-link-library-search-order
Nothing wrong with the %0.17f, I'd leave it if it's working. Anything else is potential cleanup later but would probably involve a printing helper function, so not as neat code-wise.
.17g is going to ensure 17 significant digits, so that'll work for tolerances, but not if someone has tol > 1 -- though in that situation printing 17 after isn't accurate either as we traded mantissa with exponent to go bigger.
Hmm - I wonder if this might be our ticket to making lib work on Windows: https://learn.microsoft.com/en-us/windows/win32/api/Winbase/nf-winbase-setdlldirectorya
We'd need to do that across the board for all of our executables though. Wonder if there's a clean way to do that without 400 new function calls in the main()s. I suppose we could have bu_setprogname do it under the hood since we do need to call that one everywhere already, but that feels like a violation of the API design since load path altering isn't its job.
starseeker said:
Sean I'm down with trying to figure out how to get executables into libexec for these purposes, but I do know I tried to figure out something similar on Windows at least once before, many years back, and struck out. I might have better luck now, but it's basically the "how do you keep a .exe in one place and .dll files in another" problem, and that's one I still don't know the "right" answer for yet.
My general understand is that for windows, we'd just put it in the bin dir. bin=libexec. The other platforms do the right thing and keep them separate/hidden from prying user eyes.
Maybe make a bu_init or something that takes the progname as an argument, but has a wider scope than just setting the program name?
same as we do with bin=lib
Ah. So you don't want to tangle with trying to make Windows act the same as the other platforms?
Could be wrong, but I think SetDLLDirectoryA() is for the dynamic loader.
that'd be a way to put all the ged/dm libs into a subdir and have them loaded proper
So it wouldn't help with libbu et. al.? That's a bit surprising...
I don't think so
their symbols are resolved at load time, before code is run
now I don't know if the search paths are transitive, though. You might be on to something if they are.
Hmm. Do you happen to know of any documentation that talks about the distinction between the two systems? All I can find is the "Dynamic-link library search" page - I'm not having any luck with "load time search"
that is, ged loads, libbu/libged/etc loads, then modify path to include lib/libexec dirs -- then invoke tessellate program. when it loads, did it inherit the search paths of the parent or does it start fresh. if it's the prior, that would probably work.
I think I saw something about the child inheriting the parents. I guess some testing is in order here. (Ick, windows experiments. Time to get the hip waders...)
only issue would be you couldn't directly run it on the command line without modifying PATH, as the libs would still be in lib/bin at tessellate's load time.
So modifying PATH is the only way to handle things at load time? That's messed up..
same reason it wouldn't work to put all the libs into 'lib'. ged still needs to load them before code is called.
on windows PATH == PATH+LD_LIBRARY_PATH
And there's no equivalent to rpath?
and there's no rpath on the executables iirc
:cry:
that's an elf / mach-o binary thing
/me stubbornly sets out to prove to himself that SetDllDirectory won't work...
now we could get there with "one simple trick"
if we basically make ged/mged's main be compiled into a library, you could have the "app" just add/set the dll directories, then invoke that main in the compiled lib, and all libs could then live elsewhere.
not pretty -- I'd still say just shove the plugins into bin on windows, as that is the most common practice. users are told what to run and/or we install the icons/menus we want them to run. they don't pay attention to the filesystem the same as on linux/mac/bsd
OK. So that circles us back to the name of the subprocess program then, since it'll be stuck in bin on Windows. Thoughts?
If we're going to eventually turn a bunch of ged command functionality into subprocesses so they're interruptible like this, than we definitely do need some sort of convention. I know I need to consolidate a number of ged commands into fewer plugins, but even so there'll be a number of them.
mixed feelings/ideas. tessellate is typically implies regular tiling and the result of facetization is anything but that, except for initial primitives.
we could but don't actually do tessellation on the comb level
OK. Not strongly attached to any of my current names, so happy to adjust to something more appropriate
_ged_facetize_triangulate ?
for interruptibility, I'd hope we can find a general solution instead of per-command, so any ged_whatever() invocation is wrapped by a call through to a binary that invokes ged_whatever()
Sure - I was figuring there'd be one (ged_exec?) level solution to that part. The heavy lift in my mind is setting up the subprocess programs themselves and getting the inter-process communication working.
but yeah, I think iff there's going to be a command-line executable, we make them align as closely as possible, like ged_facetize_triangulate if triangulate is the subcommand to facetize.
I mean not ending up with hundred's of ged_whatever binaries
just one like ged_exec, which is invoked as a subprocess that invokes similarly
Hmm. I wonder if this might be viable to let us use SetDllDirectory: https://stackoverflow.com/a/2003775/2037687
So you mean have ged_facetize_triangulate be a function called by the ged_exec subprocess main, maybe based on the first arg or something like bu_test?
That's interesting (delayload). I'd read about that years back. That might be a way to make it work, but would require a crapton of testing ... especially for things like c/c++ libs with static initialization or complex lib structures like step-g's libs that need things in a particular order.
delayed loading would also means possible runtime hiccups as it searches for a particular lib, if that operation is expensive (e.g., running remote, on server, or on an nfs volume, etc)
<nod> Probably not worth it, in the end, but it's a temptation to try. Maybe something to have a student try out as an experiment.
they basically create a bunch of function pointers that are initialized to a function that calls LoadLibrary()+GetProcAddress(), so once you actually call it at runtime, it loads and uses it from then on.
that's done for every symbol, so startup cost will go up by some measure if there are a lot of lookups.
starseeker said:
So you mean have ged_facetize_triangulate be a function called by the ged_exec subprocess main, maybe based on the first arg or something like bu_test?
Maybe? More like
mged[main()] -> ged_exec() -> subprocess-exec("ged_exec search . -type region") ;
ged_exec[main()] -> dlload("ged_search") -> ged_search() ...
That would be adequate for protecting / interrupting facetize and we'd undo or leave the subprocess stuff it's doing, which just be a second exec if we left it:
mged[main()] -> ged_exec() -> subprocess-exec("ged_exec facetize triangulate ...") ;
ged_exec[main()] -> dlload("ged_facetize") -> ged_search() -> subprocess-exec("ged_facetize_triangulate ...") ;
@starseeker looks like geogram has three different tetrahedral mesh generators, tetgen was only one of them.
This paper reminds me of your DRI...
wu_sgp18_csg.pdf
@Sean General design question for you. Right now, in libged, ged_exec is getting the names of viable commands to run because we're dynamically loading the shared object plugins at runtime. If we wanted to have a mixed solution where ged_exec could know about both the dynamic plugins and a set of "pre-baked" commands just compiled directly into libged, is there a way to handle the "pre-baked" listing of the functions that are part of libged?
The obvious answer is to generate and build a compile-time generated list from the source files, sort of like what the env command does for environment variables, but I was wondering if there is a more elegant technical way to have libged's library initialization do some sort of load-time registration of built-in libged library functions that have some sort of indicator they are ged commands.
...If we wanted to have a mixed solution where ged_exec could know about both the dynamic plugins and a set of "pre-baked" commands just compiled directly into libged,...
@starseeker Background context? Why would you want a mixed solution? Sounds like a path of questioning that can only result in additional complexity. Depending on the issue, there might be other things to consider changing before doing that route. That'd seem likely at least, as the primary reason shells have built-ins is for performance. We've hand-waived performance thus far in the libged call stack.
is there a way to handle the "pre-baked" listing of the functions that are part of libged?
Several ways come to mind...
If you recall, we talked about having a core set years back. It was an optimization (hence why we didn't) to avoid loading all or nothing, just preload a dozen or so used for read-only inspecting and let the rest auto-load. To do it, the proper way would've been a registration table in libged.
Note it would've also likely required some documented criteria so as to avoid ad hoc and/or arbitrary cop-outs and promotions of convenience. Otherwise, it easily all becomes glorified unencapsulated globals. We also talked about potentially needing plugin versioning and/or making sure whatever we came up with would be sane in an ecosystem of 3rd party plugins also.
Potentially useful.... https://github.com/Janos95/mantis
Sweet - between the geogram hole repair and plate->vol BoT conversion, I was able to generate a completely plate mode free, fully manifold Generic Twin (triangle mottling is due to zfighting on very thin volumentric bots)
image.png
@starseeker just fyi, I was test building facetize branch on mac and hit a few snags (hence the commits). I fixed a couple of them, but left one -- not finding glm headers when compiling facetize.cpp
I don't see them specified in CMakeLists.txt so looks legit, but thought you'd like to know in case you know the quick fix.
I've been building using bext for geogram so a couple of the newer bits probably won't work with the src/other manifold right now
I added install logic for the glm headers there
~/brlcad/build (facetize) $ ../sh/conversion.sh --bot MAXTIME=5000 share/db/*.g share/db/*/*.g
[snip]
... Done.
Summary
=======
Converted: 100.0% ( 16230 of 16230 objects, 58 files )
Passed: 16230 ( 16230 BoT )
Failed: 0 ( 0 BoT )
Timeout: 0 ( 0 BoT )
BoT rate: 100.0% ( 16230 of 16230 )
Prim rate: 100.0% ( 9928 of 9928 )
Reg rate: 100.0% ( 4023 of 4023 )
Elapsed: 39803.0 seconds
Average: 2.5 seconds per object
Finished running ../sh/conversion.sh on Tue Mar 5 06:27:15 PM EST 2024
Output was saved to conversion-1542905-run.log from /home/user/brlcad/build
Conversion testing complete.
Full log: https://brlcad.org/~starseeker/first_100percent_facetize_conversion-1542905-run.log
Two observations. 1) Holy crap that's truly awesome, amazing, almost unbelievable, and 2) Holy crap 11 hours...
Yes, agreed it's slow. The culprits are first and foremost the Generic_Twin plate mode evaluations - there's about 500 of them, some of them quite large and slow, and conversion.sh does them over and over processing all the various levels of the hierarchy. The fallback NURBS evaluations with SPSR are also nothing to sneeze at.
What I'll do later today is pre-convert the Generic_Twin plate mode bots as a pre-processing step to take that part out of the timing. With the exception of parallel processing the lower level boolean problems indivdiually, I'm not really sure how to speed up the plate mode conversion - it's a nasty problem.
I mean, unless they're 90% of the time, it's probably not going to make a huge difference.
Not much difference between 4 and 12 hours expectation-wise or practical use-wise. That's conveniently about how many minutes per conversion it took and both are over "coffee break" time.
Order of magnitude would be needed, and that is something SMP would offer if it's not currently parallel. Full conversion in an hour, any given model in about a minute. That would change the UX scale.
Not a priority in the least, just navel-gazing observations..
FWIW pre-converting the plate mode bots in Generic_Twin and running conversion.h on all the top level objects only results in:
=======
Converted: 100.0% ( 197 of 197 objects, 58 files )
Passed: 197 ( 197 BoT )
Failed: 0 ( 0 BoT )
Timeout: 0 ( 0 BoT )
BoT rate: 100.0% ( 197 of 197 )
Prim rate: 100.0% ( 59 of 59 )
Reg rate: 100.0% ( 42 of 42 )
Elapsed: 4511.0 seconds
Average: 22.9 seconds per object
Of that, 2622s was the NIST and brep_pinewood fallback conversions. The Generic_Twin all boolean was still rough, at 840.3s, but quite a bit less than the 3911.3s it took without pre-processing. It'd be interesting to see if Manifold's TBB support could knock the boolean time down on Generic_Twin.
There we go - fixed it so conversion.sh didn't have to exclude the empty trees.
~/brlcad/build (facetize) $ ../sh/conversion.sh --bot MAXTIME=5000 share/db/*.g share/db/*/*.g
[snip]
... Done.
Summary
=======
Converted: 100.0% ( 16278 of 16278 objects, 58 files )
Passed: 16278 ( 16278 BoT )
Failed: 0 ( 0 BoT )
Timeout: 0 ( 0 BoT )
BoT rate: 100.0% ( 16278 of 16278 )
Prim rate: 100.0% ( 9930 of 9930 )
Reg rate: 100.0% ( 4061 of 4061 )
Elapsed: 40258.0 seconds
Average: 2.5 seconds per object
Last updated: Jan 09 2025 at 00:46 UTC