Grasshopper

algorithmic modeling for Rhino

Hi 

I got a mesh from image process, and want to extract the shape of the mesh.

In addition, I converted the mesh into the point cloud,and tried to find some plane to bulid the polyhedron. But the result was bad:(

(mesh)

(point cloud)

Do you have any idea for the problem? 

thanks for any help!!!

Tommy

Views: 2199

Attachments:

Replies to This Discussion

Hmm .. just spotted that one.

NOT a case for a novice nor for an expert (without extensive experience in coding).

Why? Well ... first do some Google search "coPlanar points clusters". You'll find a vast variety of papers (mostly related with LIDAR airborne sampled clouds) ... but ... hmm ... no code (other than some "abstract" algos that may (or may not) work). Reason? A very hot cake that one these days: from reverse engineering to DARPA founded future defense systems and up to cruse missiles pattern recognition algos.

The solution (obviously doable only via code) is the so called flat hard clustering ... were points are sampled into clusters based on the coPlanarity "rule". For large amounts recursive octTrees (an oriented box divided in 8 "partitions") subdivisions are used and then pts are processed in parallel  (and then clusters are re-evaluated in order to "absorb" other clusters with same plane A,B,C,D vars etc etc).

See what's happening in a very carefully made test point collection:

3.7 ms and the "ideal" clustering (7 search loops VS the max 42M theoretical threshold):

Depending on the pts "preparation" ... a considerable more time/search loops is required ... and ... well ... also "valid" clusters (4 points and up) made:

So "ideally" speaking in your case:

1. Mesh faces center points (or alternatively: mesh vertices) are sampled into a pts collection .

2. Hard flat coPlanarity clustering is attempted yielding pts/planes in equivalent DataTrees.

3. Planar Breps are made with respect the planes (like the black things captured above) and sampled, say, into a breps List.

4. The method Brep[] solids = Brep.CreateSolid(breps);  is used for attempting to create your desired "engulfing" brep. This method is very slow mind (other waaaay faster approaches also available).

Here's a test using 1.5K random points:

This freaky set of Breps (out of the clustered coPlanar ps):

is made into this:

Attachments:

Hi Peter:

Thanks for your suggestion,and the result looks great.

Would you mind to share your code for "flat hard clustering"? 

Tommy

Hi Tommy

Apologies but this is classified as strictly internal. The purpose of my writing is to inform you that this is doable (anyway ... in most of cases) ... but is not something achievable without coding.

But I can use the code (or some other versions) to provide to you an end-result (like the ones attached as 3dm demos) out of points (for instance: random points, "ordered" points, mesh vertices, brep vertices, mesh/brep related other points [centers or other] etc etc).

May I ask why you need such a "reverse engineering" engulfing polysurface? Maybe there's more "palatable" ways to skin the cat on that matter if you approach the problem differently.

best, Peter

Hi Peter:

Thanks for your reply.

The mesh is from real foam structure, and we want to measure the shape of the cell by computer.

Tommy

Well ...

1. See this attached (a rather very primitive way to spread random points on "drilled" facet dome breps). Primitive because points are not "moved" up/down with respect some local Z "noise" etc etc.

2. IF you can find a BPA (Ball Pivot algo) you can by-pass the quite tricky reverse engineering coplanar clustering task. Good news: if memory serves well there's a BPA "add-on" component available for GH. Bad news: don't ask me where (I can't remember a thing or two).

PS: using Morph Methods you can severely "distort" the points List and get more intriguing topologies.

Internal BPA in action:

In order to get a "similar" with your picks result you'll need " A LOT of random points (say "around" 5/6K), probably some random Z noise ... and a rather very fast BPA.

If Z noise is used ... well ... then things are challenging: create a Truss like graph where tetrahedron type of rigidity is achieved: every quad set of neighbor points is connected with 6 lines.

best.

Attachments:

And this (trad) update s rather more "compact" I confess.

Attachments:

BTW 1:

For finding "seed" quad coplaner pts in some chaotic collection and regardless "smart" ways to prepare the data (divisions, parallel processing, Karma etc etc)... we actually need 4 nested loops: so if you have a gazillion of points you have a threshold of Math.Pow (gazillion, 4) loops > yikes ^ yikes.

BTW 2:

On the other hand ... clustering "structured" data (some call this as a "topological sort") is 10000 times faster than doing it in chaotic collections (like the random points on N BrepFaces etc).

Reason? Well ... a mesh (or brep) is a mini RDBMS (kinda) with regard "relations" (connectivity) between the 3 basic "classes of objects": vertices, edges and faces (or BrepFaces if we inquire a brep). This means that we can have 3*3 = 9 possible connectivity trees (see SandBox that makes some of them but it doesn't work on invalid [LOL] meshes).

So in this case of yours with that "drilled" mesh and approaching the problem the reverse engineering way ... the clustering "rule" is simple: if the normal angle of a given meshFace VS any other search meshFace normal is within some tolerance (say 1 to 5 degrees or some other domain) > consider the faces as coplanar > get the  search meshFace index in a cluster (a branch in some Tree, that is), remove it from the search list and go find some other or initiate a new cluster. This means 2 nested search loops VS 4 (a colossal difference).

The good news are that when we search similar stuff we have connectivity info on hand (neighbor faces, that is) and this makes a colossal difference in the processing time required.

So if this first pass is finished we get points sampled  into tree branches > meaning equivalent planes fitted to these > the rest are history (with a variety of ways). 

Hi Tom:

Thanks a lot!

Is there a better way to do in rhino? 

Because I need to measure a lot of objects(mesh), i use grasshopper.

Tommy

Tom,

For your level of abilities (rather high I confess) I would strongly suggest a recursive search on MeshFaces (using neighbors etc) and testing the MeshFace pairs normals for satisfying the coplanal condition (within some -/+ vector angle user specified domain).

Sample centers, vertices, cats, dogs ... whatever appears suitable for the job (tripple espresso and the Force always a must).

BTW: I'm sure that you know how a facet dome algo works (intersect neighbor planes > a potentially self intersecting polyline > planar array of Breps out of this > brep outer loops > get the one that contains the center of search > blah, blah).

LINQ (and PLINQ in some occasions) is kinda any Harley Davidson ... but is WOW and "cool" (kinda a H/D). On the other hand creating slow code is very good > forces people to buy new gear > that's the essence of progress in our plastic is fantastic times (I consume therefor I exist).

With these in mind my "working" solution is politically incorrect (BTW it's slow as well).

Do the recursive stuff on MeshFaces and make the %$#%$# coplanar clusters.

And what is ASTools?

BTW: Speaking about LINQ/PLINQ matters ... get this attached > totally irrelevant with this thread ... but a genius guide to future // programming (i.e.  ultra slow, pointless, meaningless  == 100% proper).

BTW: This is approved by Paris Hilton, Microsoft, NASA, CCN and ... er ... hmm ... even KGB (let the good old times roll).

Attachments:

RSS

About

Translate

Search

Photos

  • Add Photos
  • View All

Videos

  • Add Videos
  • View All

© 2024   Created by Scott Davidson.   Powered by

Badges  |  Report an Issue  |  Terms of Service