Mesh from Lines

Hi Giulio,

I am working on a new version of eve|voronax ( http://www.food4rhino.com/project/evevoronax ) and among other things, it will have cell recognition....cells filled with meshes or surfaces. I have been experimenting with different algorithms and the best one I have involves an underlying surface. This is OK 99% of the time but I am searching for ways to improve it. That is why I was wondering what kind of algorithm did you use for "Weave Back Mesh" in Weaverbird? Is it based on some research or did you just come up with it? I thought some fresh ideas might help me develop better cell recognition...

My guess is that you went with Convex Hull and then removed the faces whose edges didn`t match the input lines...is this the case?

Thanks!

Greetings,

Milos

Replies to This Discussion

Permalink Reply by Giulio Piacentino on June 17, 2014 at 4:26am

Hi Milos

thanks for posting this discussion also here.
I would be interested in hearing what exactly you mean by "the best one I have involves an underlying surface". Are you trying to fit a surface onto the points first, and then, ultimately, doing a planar search for bounding regions? The are papers for the latter part, but I wasn't very happy about them.

I've looked a bit for some literature for generic faces finders, but could not find one that would fit my needs (including, for example, finding the mesh for the line-representation of a torus). Maybe there's something out there that I did not find either.

The algorithm I use does not really translate easily to cells, but works fairly well if faces move smoothly on the surface. It's running on the edges and brute-force searching for closing faces around them. Then, it chooses the few paths that bound smaller loops. There are some minor optimizations to diminish the amount of searches and a series of clean-up steps after this, to make sure that the result does not contain duplicate faces, flipped faces, faces that encompass two or more faces, etc.

Another alternative I've coded but was not giving good enough results was a DFS on the edges, and closing faces on the go. However, I think I might still add this, and merge the result, as it was finding some intricate cases where the first method was, unluckily, following wrong twists, and so not giving all results.

Does it help?

Giulio
--
Giulio Piacentino
for Robert McNeel & Associates
giulio@mcneel.com

Permalink Reply by Milos Dimcic on June 17, 2014 at 4:57am

Thanks,

I`ll think about the possible options. To answer your question - you use some surface anyway to generate Voronoi/Voronax...so you don't need to fit a surface - there is one already there. Then I do a kind of a brute-force search in the parametric space of the surface and i have to say it works in 99.9% of the cases but I would like to make an algorithm that works for any grid/graph, without the underlying surface.

You say there are papers on the planar search for bounding regions...do you have some links?

Greetings,

Milos

Permalink Reply by Giulio Piacentino on June 17, 2014 at 6:15am

I don't have my original search anymore. It was also a little disappointing. I think there's more. But this might help you with keywords.

http://www.researchgate.net/profile/Alfredo_Ferreira2/publication/2...

Giulio
--
Giulio Piacentino
for Robert McNeel & Associates
giulio@mcneel.com

Permalink Reply by Ayuna Mitupova on April 5, 2016 at 4:25pm