starseeker (Dec 03 2023 at 03:16): starseeker (Dec 03 2023 at 03:16):@Alexis Naveros I'll let @Sean chime in, but I can give you some background on the SPSR bit... it's an older version of https://github.com/mkazhdan/PoissonRecon reworked for embedding in our library:
As far as the results being satisfactory... not always, unfortunately. It has trouble with sharp edges and doesn't always give us a usable output. It's possible the newer version of the code might do somewhat better, but where it's most useful in practice is when a case fails for some reason but doesn't have a "weird" volume. We're basically using it in place of ball pivot from the original pipeline you worked on - raytrace a whole lot of points to try to sample "dense enough", assemble an initial huge mesh (ball pivot originally, SPSR for us) and then use your decimation code to step the result down to something sane size wise. It doesn't always work, but there are cases where it does work and that's a win for users trying to get conversions to go through.
Alexis Naveros (Dec 03 2023 at 03:18):Damn, that sounds awful. So you don't have any robust solution at all, to that some old problem of converting CSG to closed watertight triangle meshes.
Alexis Naveros (Dec 03 2023 at 03:21):Thinking about my planned algorithm here. When you extract a point cloud from CSG geometry, can you get points exactly on the edges? Imagine a cube, will you get points exactly over the edges and corners? Or do I get only points on the faces, and I should project the planes to reconstruct that sharp edge?
starseeker (Dec 03 2023 at 03:28):There's no way to guarantee sampling on the edges, since the edges themselves can be implicit - think about one sphere being subtracted from another, for example.
Alexis Naveros (Dec 03 2023 at 03:29):Got it. Okay.
starseeker (Dec 03 2023 at 03:29):We could probably do something partial like making sure sample rays go through individual primitive verts and edges, but that won't help when the sharp edge is completely implicit so it's probably best not to depend on that sort of thing
Alexis Naveros (Dec 03 2023 at 03:30):Yeah, right. I'm thinking about needing a third pass in the algorithm, comparing the triangle mesh with the point cloud to "repair" where normals meet...
starseeker (Dec 03 2023 at 03:30):To your earlier point - we're not faced with any particular deadlines. This whole thing came up due to a combination of improvements triggered by using https://github.com/elalish/manifold and some cleanup of the third party codes we include in BRL-CAD.
starseeker (Dec 03 2023 at 03:33):To give you some more context - most of the time, especially in the newer pipeline I'm working on, the point sampling fallback will hopefully be rare and applied to individual primitives NMG can't handle. If Manifold continues to perform as well as it has in early testing, I'm hopeful that we can focus the meshing problem itself solely at the primitive level (essentially, as alternatives to the libnmg ft_tessellate routines) and just feed the resulting meshes into the same evaluation from there.
starseeker (Dec 03 2023 at 03:34):Previously, we were raytracing whole regions to point sample as a means of bypassing the NMG booleval, if it was failing - a point sample of a region could let us jump "straight to the final mesh" and let the CSG raytracing deal with the booleans.
Alexis Naveros (Dec 03 2023 at 03:36):Well, I'm certainly hoping it will handle any primitive. The effort will be a little intense (I'm not sure why my first impression was of an "easy" problem), but it's a nice problem, it's a nice challenge
starseeker (Dec 03 2023 at 03:36):We probably still want to be able to try that as a last resort, but if we can produce inputs that satisfy Manifold's requirements from our primitives (and, barring bad BoTs, we should be able to do that since our primitives are supposed to define closed volumes) I want to push the meshing problem as far down the tree as possible.
starseeker (Dec 03 2023 at 03:38):Since a lot of our "bad" meshes are very close to solid volumes and ought to be amenable to some form of automatic repair, I'd like to incorporate that capability into our BoT processing as well. A couple of the mesh libraries out there have hole filling algorithms which might be useful, although I'm not far enough along yet to have tried any of them.
starseeker (Dec 03 2023 at 03:39):Another alternative to SPSR and ball pivot that I was planning to look into is geogram's Co3Ne https://github.com/BrunoLevy/geogram/wiki/Reconstruction#co3ne-reconstruction-concurrent-co-cones
Alexis Naveros (Dec 03 2023 at 03:39):I tried hole repair in ball pivoting a decade ago, and it was a disaster. I'm planning an algorithm that would iteratively deform a closed watertight mesh, maintaining proper topology all the way until the output
starseeker (Dec 03 2023 at 03:41):<nod> I wasn't planning to use hole repair for that case - the problem I'm thinking about is when someone brings in an stl or something that wasn't watertight to begin with (but is ALMOST watertight). If we can deal with even some of those automatically it would save trouble for users otherwise having to do manual repair for a lot of very tiny little problems.
Alexis Naveros (Dec 03 2023 at 03:43):I think you could feed the vertices and normals of that STL file into the algorithm I'm planning, and it would just repair the holes as well
starseeker (Dec 03 2023 at 03:43):I'm also wondering if https://github.com/wjakob/instant-meshes might be useful, but I've not dug into it enough to have a sense of whether it's applicable to our particular "rebuilding an almost manifold mesh into a manifold" case
starseeker (Dec 03 2023 at 03:44):I was wondering if that might be possible, but I didn't know if the points and normals from a mesh would be too sparse for those types of algorithms to work.
Alexis Naveros (Dec 03 2023 at 03:45):Yeah, that's my concern, I can see cases where the algorithm would get confused while trying to go "in" the hole. But you could generate a ton of extra coplanar points everywhere, and, in theory, the final geometry wouldn't be any more complex
starseeker (Dec 03 2023 at 03:46):@Alexis Naveros don't sink too much of your free time into it if it looks to be too hard - past a certain point, it would probably be more of a win to fix the mesh generating routines for the individual primitives rather than trying to solve a super-hard general problem (at least, if Manifold really can handle the load for the booleval piece)
Alexis Naveros (Dec 03 2023 at 03:48):It's a fun problem and I have had a ton of experience with 2D/3D geometry problems over the years. I was a bit hoping that Mark (from SURVICE) would say "Oh, we need that algorithm too, you can charge the hours"... but that didn't happen :grinning_face_with_smiling_eyes:
starseeker (Dec 03 2023 at 03:49):Am I wrong in thinking of your proposed algorithm as sort of a "shrink wrap" process?
Alexis Naveros (Dec 03 2023 at 03:51):Yes, kind of. The algorithm:
Alexis Naveros (Dec 03 2023 at 03:51):I have no idea what other algorithms are used out there, or how they are named. Checking what others are doing takes the fun out of solving problems. The name "shrink wrap" sounds close enough
starseeker (Dec 03 2023 at 03:52):OK, so this probably isn't relevant then: https://www.sciencedirect.com/science/article/pii/S0010448523001409
Alexis Naveros (Dec 03 2023 at 03:53):Currently, the one point that bothers me a bit is how the collapsing box should reconnect with itself as it goes through holes, on both sides. Meeting with itself, how to best detect that case and get a proper surface out of that step before continuing the process. In case you have ideas
starseeker (Dec 03 2023 at 03:53):Heh - nevermind, if you're not looking for other algorithms that's pointless anyway
starseeker (Dec 03 2023 at 03:55):If it meets itself, shouldn't it "collapse" and form a torus topology? If I'm understanding correctly, the boxes would only meet if they found a path without any volume along it?
Alexis Naveros (Dec 03 2023 at 03:55):For moving vertices to reconstruct sharp edges, I'm thinking summing up squared planed equations and solving the quadrics, like I do in mesh decimation. Finding the best vertex placement to recover the lost sharp edges
Alexis Naveros (Dec 03 2023 at 03:56):Since I believe you have googled everything already, does that algorithm already exist? Is it "shrink wrap"?
starseeker (Dec 03 2023 at 03:57):Actually, Sean's the one who is more up on the shrink wrap problem - let's wait for him to weigh in. I have only a casual knowledge
Alexis Naveros (Dec 03 2023 at 03:58):I lost your torus example. The collapsing box would wrap around a torus (step #0), then the next step would be to collapse further through the holes. Both sides of the collapsing box will meet in the hole, before collapsing further to properly capture all the inner sides of the torus
Alexis Naveros (Dec 03 2023 at 03:59):It's the "collapsing box meeting itself" I'm a bit stuck on, how to best detect and resolve it, how to rebuild the box's surface (which is really no longer a box at this point) with a... tunnel in it
starseeker (Dec 03 2023 at 03:59):Right - so wouldn't the center of the torus be where the two sides of the original box would connect? I.e. the box would intersect itself? Or am I misunderstanding?
starseeker (Dec 03 2023 at 04:00):Or are you asking how to detect when the self-intersection occurs?
Alexis Naveros (Dec 03 2023 at 04:00):Yes, somewhere in the hole. Might not be the exact center really, but they will meet
Alexis Naveros (Dec 03 2023 at 04:01):Detecting self-intersection fast is part of it, in an extremely robust manner, without any floating point precision concerns. How to resolve that intersection is the other part
starseeker (Dec 03 2023 at 04:05):I'm afraid compared to your expertise Alexis my ideas would be on the naive side. For collision detection, the only thing that comes to mind is trying to use something like an RTree to identify potential intersecting faces and then doing the triangle/triangle intersect calculation.
starseeker (Dec 03 2023 at 04:06):I'm aware generally of collision detection research for things like cloth simulation, but I don't know the details of the algorithms they use.
Alexis Naveros (Dec 03 2023 at 04:07):Yeah... but collisions will be rare, the vast majority of the iterative steps won't collide, and I want to have 64 threads working on that in parallel. So I want that to be really fast, with minimal spatial locking
Alexis Naveros (Dec 03 2023 at 04:08):Collision resolution will imply some kind of local boolean operation on triangle meshes. Which I have never done, doesn't seem excessively hard, but it's the kind of details that made me realize "oh, perhaps it's not that simple in the end..." :laughing:
starseeker (Dec 03 2023 at 04:09):Yes - "local boolean operation on triangle meshes" has caused a world of hurt for lots of computer graphics folks over the years :-P
Alexis Naveros (Dec 03 2023 at 04:10):Yes, really, I'm not surprised... This one small detail, fast self-collision and resolution by boolean thing, is what is currently bothering me. Everything else has been planned on paper
starseeker (Dec 03 2023 at 04:11):I think, if I'm following correctly, it's not really the mesh collision problem so much as it is detecting and resolving self-intersection
Alexis Naveros (Dec 03 2023 at 04:12):Yes, it's the box colliding with itself. But the box is the mesh, it's the only mesh, the one slowly deforming to capture the point cloud's surface
Alexis Naveros (Dec 03 2023 at 04:12):I realize naming it "box" is getting terribly inappropriate. It made sense at the time
starseeker (Dec 03 2023 at 04:13):Subdivided box might work
Alexis Naveros (Dec 03 2023 at 04:13):Which can break into multiple boxes and with tunnels... but it's still a box to me! :rolling_on_the_floor_laughing:
Alexis Naveros (Dec 03 2023 at 04:15):Well, that's the problem that's stopping me from getting started, it would be great if one of us could come up with a good solution
starseeker (Dec 03 2023 at 04:23):This might be worth a read: https://dl.acm.org/doi/pdf/10.1145/3592136
Alexis Naveros (Dec 03 2023 at 04:25):Thanks, reading.
Just to clarify a point, instead of having to do boolean operations on the triangle mesh (box), I was leaning towards the possibility of detecting a potential collision (if I perform the step), and then just meet the other colliding surface and joining vertices, creating the tunnel. It's less a hassle and more robust numerically than boolean operations
Alexis Naveros (Dec 03 2023 at 04:26):As soon as the tunnel exists with a proper surface topology, then the box will go on collapsing and capturing the hole's walls properly
starseeker (Dec 03 2023 at 04:27):Ah, so rather than a geometric calculation on the mesh to find an intersection, you would simply recognize the collision and locally alter the mesh topology to allow for further correct refinement?
Alexis Naveros (Dec 03 2023 at 04:30):Yes. Just detect if a step X would cause a self-intersection, instead create a tiny tunnel connecting the two surfaces, and let that tunnel grow with the future iterative steps
starseeker (Dec 03 2023 at 04:37):@Alexis Naveros I should probably mention something - before we fall back to SPSR based reconstruction, we first try the "Continuation" method based on Bloomenthal's polygonizer. That basically marches a mesh around the boundary of a volume using our raytracer for the inside/outside part of Bloomenthal's algorithm. Like SPSR it doesn't always work, but it tends to do better that SPSR at preserving our shapes. We also use the decimator on its output, IIRC, so it has that in common with SPSR.
Alexis Naveros (Dec 03 2023 at 04:39):Hm. I'm not sure I understand how that "marching a mesh around the boundary of a volume" works with complex shapes and holes... but I get the idea that you have multiple solutions, and none of them is guaranteed to work
starseeker (Dec 03 2023 at 04:41):I'm probably not describing it very well - https://people.eecs.berkeley.edu/~jrs/meshpapers/Bloomenthal.pdf is the writeup
starseeker (Dec 03 2023 at 04:42):It's actually our best option at the moment for the dsp height field primitive, and it does fairly well when we don't have super-thin shapes (but to be fair SPSR can't handle super-thin volumes well either)
starseeker (Dec 03 2023 at 04:44):I figured I should mention it because there's a chance a more intelligent implementation of that approach than the one I hacked together might have overall better behavior than doing an initial sampling with a point cloud
Alexis Naveros (Dec 03 2023 at 04:44):It's looking a bit like marching cubes?
starseeker (Dec 03 2023 at 04:44):It's related, I believe
Alexis Naveros (Dec 03 2023 at 04:45):I remember Doug from SURVICE had written a marching cubes implementation for Lee Butler, while I did ball pivoting. Also consuming raytraced point clouds
starseeker (Dec 03 2023 at 04:45):A straight up marching cubes has been tried before by Sean as well (IIRC) and the results are pretty bad - this does somewhat better, although we do tend to get some artifacts around sharp edges (typically less so than SPSR though.)
Alexis Naveros (Dec 03 2023 at 04:47):I'm not too concerned about sharp edges... Sum up squared planes (using point cloud normals) of near vertices in a quadric, invert and solve the matrix, get the best placement for edge vertices. It really should reconstruct the edges nicely
starseeker (Dec 03 2023 at 04:49):That'd be pretty cool. I'd be thrilled to ditch the polygonizer and SPSR codes if we had something that was reliable and produced better output - those fall squarely into the "it's ugly but currently useful enough we can't ditch 'em" category
starseeker (Dec 03 2023 at 04:50):Oh - I doubt you'll want or need it, but we do have Eigen available at compile time if that's a help.
Alexis Naveros (Dec 03 2023 at 04:51):Yes, I can imagine. It's a nice problem, it's a fun problem. And most of all, I like being able to correct "mistakes" of the past, when I have once written code that I'm absolutely not proud of
Alexis Naveros (Dec 03 2023 at 04:54):(Eons ago, SURVICE also put me on fluid dynamics, my math wasn't up to the task so I went brute force CUDA with tiny time steps, raw numerical turbulence, no shortcuts... A decade later, I had my revenge: http://www.rayforce.net/newcfd002.html )
starseeker (Dec 03 2023 at 04:57):Wow!
starseeker (Dec 03 2023 at 04:58):Is Rayforce still a thing, by the way? I can't find much of anything about it online these days
Alexis Naveros (Dec 03 2023 at 04:59):I don't think so... It was the fastest raytracer in the world for a while, but the "graph construction" was intense. It was taking a while. It was useless for games or any kind of dynamic geometry
Alexis Naveros (Dec 03 2023 at 04:59):It made sense if you were going to shoot a billion rays at the same model
starseeker (Dec 03 2023 at 05:01):Ah - yeah, I can see where that wouldn't be ideal for games or movies.
Alexis Naveros (Dec 03 2023 at 05:02):Some SURVICE guy wrote a paper or two about some novel techniques in it. He put me as co-author. I guess that was it
starseeker (Dec 03 2023 at 05:02):I can find the announcement SURVICE put about about releasing it as open source, but I can't find the source itself.
Alexis Naveros (Dec 03 2023 at 05:03):Oh. I have no idea really, I have moved on to other problems long ago :grinning:
starseeker (Dec 03 2023 at 05:03):No worries, just curious.
starseeker (Dec 03 2023 at 05:04):I've got 200 other holes to dig out of before I start trying to optimize our triangle raytracing more :-P
Alexis Naveros (Dec 03 2023 at 05:05):Eheh. Yeah, that makes sense. Let's make that 199!
Alexis Naveros (Dec 03 2023 at 06:53):Instead of simply collapsing the box to reconstruct the surface, I'm considering that the box could actually be full of tetrahedra, which becomes subdivided as I continuously create vertices over the box's surface. Then detecting a collision is just a matter of detecting when a tetrahedra gets totally squished. It's perfectly robust, no numerical issues with floating point. It also sounds a bit slow. And messy
Alexis Naveros (Dec 03 2023 at 10:36):(nevermind that, it's awful, all the processing time will be spent rebuilding the internal tetrahedra as the surface continuously gets deformed and tetrahedra are being punched in, it's complicated code too)
Alexis Naveros (Dec 05 2023 at 01:26):On-paper planning complete, now beginning to write code. Might take a few weeks, some parts are a bit complicated
starseeker (Dec 07 2023 at 17:37):@Alexis Naveros here's another fun point cloud: https://brlcad.org/~starseeker/ztec.pnts
starseeker (Dec 07 2023 at 17:37):I think the point of the cone is causing problems for all our current methods
Alexis Naveros (Dec 07 2023 at 20:52):Cool, thanks. I have only written the code for the first step #0, creating a convex hull. Seems to run okay but I need to write a quick visualization, I'm sure the next steps will have bugs to fix
Alexis Naveros (Dec 07 2023 at 20:53):If it's easy for you, could you generate point clouds for simple/easy test cases? Like a bolt or something. And something without holes. I'm sure I could use simple shapes to investigate future bugs
starseeker (Dec 08 2023 at 02:09):Sure - it'll be a little bit, but its no problem
starseeker (Dec 08 2023 at 02:12):I think we're using https://github.com/akuukka/quickhull right now - if you've got a better one perhaps we can switch to it and remove that code too :-). IIRC, there are some slim/small cases where that implementation doesn't quite work
Alexis Naveros (Dec 08 2023 at 05:17):At first glance, that code has epsilon values and comments like "This may fail due to numerical instability in which case we give up trying to solve horizon edge for this point and accept a minor degeneration"
Alexis Naveros (Dec 08 2023 at 05:18):And that sounds pretty bad. I have added checks so that everything is robust by design, no matter the numerical accuracy... now I just need examples that would stress these very rare paths
Alexis Naveros (Dec 08 2023 at 05:19):You actually need a convex hull code, that does only that, convex hull? It was only the first step of 3 for my planned code
Alexis Naveros (Dec 08 2023 at 05:27):Wow... when a point from the point cloud is giving trouble to their code, they just delete the point. Nice thinking there. Problem solved
Alexis Naveros (Dec 08 2023 at 05:28):And they call deleting points a "minor degeneration"
starseeker (Dec 08 2023 at 16:09):convex hull is exposed as a feature of the bot command - it's more of a "nice to have" but it's one option to produce a simple stand-in for a more complex shape
starseeker (Dec 08 2023 at 16:16):@Alexis Naveros https://brlcad.org/~starseeker/pnts/
starseeker (Dec 08 2023 at 16:16):the new ones should be pretty basic
Alexis Naveros (Dec 08 2023 at 19:08):Cool, thanks. I'll refine my question though... would it be possible to get a couple examples with fewer points? :grimacing: I expect to go step-by-step to visually recognize any glitches, while inspecting a verbose log. And that gets harder above 1k points
starseeker (Dec 08 2023 at 19:10):Heh - sure :laughing: I was thinking in terms of dense sampling to represent the shape, but you're quite right that large sizes are a debugging problem.
starseeker (Dec 08 2023 at 19:10):I can actually control the number of points sampled - any specific requests?
Alexis Naveros (Dec 08 2023 at 19:10):Oh, 500 or so is perfect
starseeker (Dec 08 2023 at 19:14):OK, the *_500.pnts files in the same directory have the smaller samples
starseeker (Dec 08 2023 at 19:14):Did you want sparse samples for the "problem" cases as well?
Alexis Naveros (Dec 08 2023 at 19:15):I certainly want all the point clouds that are giving you trouble with other codes!
Alexis Naveros (Dec 08 2023 at 19:16):Oh nevermind, I misunderstood. I don't need low res of these
Alexis Naveros (Dec 08 2023 at 19:20):Thanks
starseeker (Dec 20 2023 at 15:49):@Alexis Naveros Did those examples end up being what you need?
Alexis Naveros (Dec 20 2023 at 19:54):Hey yes, I think so. SURVICE keeps dragging me to do a bunch of things, I'm hoping to have the free time I requested shortly
Alexis Naveros (Dec 20 2023 at 19:55):I thought the chat was quite dead until your notification, it needed a Ctrl+R to see the new messages. Is Erik still around? He was on the user list on the right when I arrived, he isn't anymore. It would be fun to reconnect after all those years
starseeker (Dec 20 2023 at 20:07):He's on occasionally.
Alexis Naveros (Dec 20 2023 at 21:12):All right, cool. Sean, have you seen the previous discussion about the proposed mesh reconstruction algorithm? I know you are a great programmer so I'm interested in any thoughts you might have
starseeker (Jan 19 2024 at 14:30):Hey @Alexis Naveros, you had mentioned having gotten as far as having a convex hull implementation - do you think it's to the point where it's stable enough to add to the mmesh repository?
starseeker (Jan 19 2024 at 14:31):If @pca006132 or one of the other Manifold devs is going to look at their quickhull, it might be helpful to know what your implementation looks like...
pca006132 (Jan 20 2024 at 12:03):@starseeker what problem did you find with the point cloud? I tried both ztec.pnts and box_500.pnts and did not trigger the akuukka/quickhull problem (deleting a point)
pca006132 (Jan 20 2024 at 12:03):If my understanding of the pnts format is correct... I treat it as x y z nx ny nz (and just discard the normals when thrown into the convex hull)
starseeker (Jan 21 2024 at 21:27):@pca006132 Those inputs weren't problematic for quickhull - they're intended for a different algorithm Alexis wants to work on, a pseudo-shrinkwrap method to replace our Screened Poisson and polygonalizer fallback methods for facetization.
starseeker (Jan 21 2024 at 21:28):The problem I believe we've encountered with the QuickHull implementation (although I don't have a test case handy) was a super thin mesh - it didn't end up producing a manifold convex hull
starseeker (Jan 21 2024 at 21:31):It's a rarely used feature in BRL-CAD proper, so it hasn't been a priority to fix - it would be interesting to see what Manifold does with that particular mesh as an input.
pca006132 (Jan 21 2024 at 21:56):@starseeker sure, I remember I got this previously when I was doing some crazy minkowski sum, can probably try to reproduce that and extract a few test cases later.
starseeker (Mar 21 2024 at 14:02):@Alexis Naveros Any update on the reconstruction code?
Last updated: Oct 09 2024 at 00:44 UTC