Sphere Tessellation

[JHourigan]

Has anyone produced a sphere tessellation vi that generates a sphere by recursive subdivision?

Build Sphere.VI in the 3D examples does not generate a uniform distribution of vertices on a sphere which is what I am after. 

I can code up something like shown in the link below. But if it's already been done, no sense reinventing the wheel.

http://student.ulb.ac.be/~claugero/sphere/sphere.c

Thanks,

Jeremy 

[Ben_S]

JHourigan,

Hello! I did some quick searching and didn't find any code that uses sphere tessellation to build a sphere. However, if you have pre-existing working c code you could use a Code Interface Node with LabVIEW to run the C-Code from LabVIEW. Also, have you seen the Create Sphere VI? Is that what you mean by Build Sphere.VI?

[JHourigan]

Ben,

Thanks for the reply.  I could call the C code, but have minimal experience with this. So I will look in to that option.   

I actually jumped the gun and started working on labVIEW2009 code to do the tessellation translating from a MATLAB function called BuildSphere.m (I find MATLAB more intuitive than C)

http://www.mathworks.com/matlabcentral/fileexchange/23959-buildsphere-get-a-sphere-surface-model

CreateSphere.vi produces greater point density at the poles, where as the recursive subdivision method has a uniform distribution. 

I will post the tessellation code when I am done. 

Jeremy

[JHourigan]

Here is the spherical tessellation VI.  It works fine up to 3 iterations (642 vertices), but after that it gets bogged down.  

The MATLAB version of this code uses a Sparse matrix for keeping track of common edges, so is more efficient.  

Question:  Does LabVIEW handle arrays populated with many zeros more efficiently?  In other words is SPARSE somewhere in the background.  

This could be coded up relatively easily.  By making an array of pointers to non-zero elements in the matrix.    

The problem I ran into with the direct implementation of this code was that MATLAB index arrays starting at 1 vs. LabVIEW's 0.  Many headaches, but you live and learn.  My work around is not particularly efficient. There is a bit of coding left to implement this more efficiently.  I will post an update if I get there.

 

Message Edited by JHourigan on 10-23-2009 10:54 AM

[Ben · Accepted solution]

---

JHourigan wrote:

... 

Question:  Does LabVIEW handle arrays populated with many zeros more efficiently?  In other words is SPARSE somewhere in the background.  

...

---

Try using "NaN" for points you do not want rendered.

Ben

[JHourigan]

NaN helped a bit with speed (I think), at 5 iterations the "point-edge" matrix becomes 10,242 x 10,242 I32 array and chokes with a memory full error.   The SPARSE Matrix would for this case be 10,242 x 3 matrix peMap(i,j,k)... where I and j are the row and column of the non zero value and k is the value.  It turns out that the geometry of this problems means that there are only 10,242 non-zero values in this matrix.

So the FULL matrix memory should be around 42 MB where as the SPARSE should be 123KB.  Does this seems correct? 

[Ben]

Sorry Jeremy, but I only understood a fraction of what you wrote. Keep in mind I am just an old guy that has poked around in a lot of corners and I have never been through any fancy course where they teach the cryptic names.

Your code is blowing up because you are trying to crate a square array that needs more than a 1G to store it. Since I did not understand the other stuff you were doing in the code I'll stop right here.

Ben

[JHourigan]

Recursive subdivision means that you start with a shape, say a triangular pyramid where the vertices are a distance of one away from the origin.  Then you take all of those triangles, find the mid point of each edge of the triangle.  Then, from one triangle face you can create four inscribed triangle faces. and you do that for each triangle so if you started with four triangle faces, after one iteration you have sixteen faces which share a bunch of vertices. 

So each vertex can be represented by a 1x 3 array (x,y,z)....but then there is a huge amount of book keeping to figure out which vertex belongs to which triangle (Triangle Matrix) and which edges belong to which triangle (Point Edge Matrix)  So the PointEdgeMatrix I was referring to in my previous post in a MxM matrix that keeps track of which pionts in the vertex matrix comprise a common edge.  So if one indexes the point edge matrix and finds a zero, then the two vertices do not form an edge to a triangle face.  If one index a matrix say (50, 23) and gets 200 it means that the points at vertex indices  50 and 23 form an edge to triangle described by the components at index 200 in the Triangle Matrix.  

Long story short there is one matrix that is huge that is a relational database between the two other matrices. It size is the number of pts squared, so it gets big fast.  But the caveat is that it is mostly zeros.  The MATLAB code uses sparse matrices. These matrices describe the full 2-D array, with pointers to matrix positions of non zero numbers and there value.   So sparse matrix of

[100, 10, 35]

[250, 125,45]

Means that there are two non-zero values in the matrix 1)  at Row 100, colum 10 with a value of 35 and 2) at row 250, column 125 with a value of 45.   lets assume this describes a 250 x 250 matrix, the FULL matrix would have 250*250 values in memory all but 2 of which are zero.  The sparse matrix only has a 2x3 array in memory. 

So there are obvious memory benefits.  As Ben suggested adding NaNs seemed to help.  But are there any VIs out there that create sparse matrices?

Jeremy 

[Ben]

An aray of clusters where each cluster has three elements or the cluster has an array?

Ben

[Darin.K]

This seemed like a good excuse to try out something I have been meaning to for a while.  Here is a sparse matrix implementation using a functional global (aka Action Engine), and a dummy variant.  As is well-known to forum regulars, the search algorithm for name/value attribute pairs is quite efficient, making it a natural for lookup tables.  In this example I use the flattened row and column as the attribute name and the matrix element as the attribute value.   Get and Set are used to store and retrieve values from the sparse matrix.  No real testing, just threw it together as a starting point.  At least it didn't choke on a few million elements, perhaps you'll push it a bit farther.

You can change the data representation, I would think hard about using the most efficient type (ie smallest) that you can.