**THE POST BELOW IS MORE THAN 5 YEARS OLD. RELATED SUPPORT INFORMATION MIGHT BE OUTDATED OR DEPRECATED**

*On 20/05/2009 at 01:22, ***xxxxxxxx** wrote:

OK, that last message was incoherent- sorry for the late night rambling. I've written a functional function, but it seems very inefficient to me:

I build an array of edges that has an extra column for hits. I grab the first edge, and then search its first point against both edge points in all unhit edges, if I find a match, then I test the other points in the two pairs, if those also match, I label the third column for each as a hit. I then move on to the next unhit edge. If I run this on a sphere, made editable from the default, it takes nearly 0.24 seconds to return(280quads/tris)- less if there is a hole because I exit the function. If I run it on a default sphere switched to icosohedral and made editable, it still takes 0.18 seconds to return on 320 triangles... this all seems insanely slow for array math and I'm guessing that even though my main loops are less than n^2, my f_find_lowest_nil is really causing a bottleneck.

Any suggestions? If not, I guess I can at least contribute a usable function...

Thanks,

Graham

as noted, you can just cut and paste this whole thing into a COFFEE tag and create a polyhedron, for example, make a sphere editable, then name it Sphere1 and look in the console for results.

> ` \> f_algorithm_speedometer(pStartTime, pEndTime); \> f_find_lowest_nil_index(pArray, pStartIndex, pArrayColumnToTest); \> f_is_polyhedron_closed(pPolyhedron); \> \> main(doc,op) \> { \> var vObj = doc->FindObject("Sphere1"); // Make a sphere named Sphere1 editable...nice test because it has poly's and quads. \> // Delete points or polys to see function return 0 instead of 1 \> var vStartTime = time(); \> var vClosed = f_is_polyhedron_closed(vObj); \> var vEndTime = time(); \> var vClosedSpeed = f_algorithm_speedometer(vStartTime, vEndTime); \> println("vClosed = ", vClosed, " the alg took ", vClosedSpeed); // vClosed = 0 means you failed to send a point object. =1 means polyhedron is closed. =2 means polyhedron has an unshared edge. \> } // end MAIN \> \> \> // Functions start here \> f_algorithm_speedometer(pStartTime, pEndTime) \> { \> // Time() can be used to profile the speed of an algorithm. \> var AlgorithmSpeed = (pEndTime-pStartTime)/1000.0; // time values returned in milliseconds so divide by 1000 to get seconds. \> return AlgorithmSpeed; \> } \> \> f_is_polyhedron_closed(pPolyhedron) \> { \> // COFFEE function by Graham Johnson of www.grahamj.com and www.fivth.com \> if (!instanceof(pPolyhedron, PointObject)) return FALSE; // Not a point object, so escape the function. \> var vArrayOfPolygons = pPolyhedron->GetPolygons(); // Create a polygon array (1D list of points that form quads and tris.) \> var i,j,m,k; \> var vArrayOfEdgesWidth = 3; \> var vArrayOfEdges = new(array, sizeof(vArrayOfPolygons), vArrayOfEdgesWidth); \> // Fill Array of Edges \> for (i=0; i<sizeof(vArrayOfPolygons); i+=4) \> { \> var vJcounter = 0; \> for (j=i; j<i+4; j++) // Loop through ABCs \> { \> var vJplusOne = j+1; \> if (vJcounter == 2) \> if (vArrayOfPolygons[j] == vArrayOfPolygons[j+1]) \> { \> vJplusOne = i; \> } \> if (vJcounter == 3) \> { \> vJplusOne = i; \> if (vArrayOfPolygons[j] == vArrayOfPolygons[j-1]) \> { \> continue; \> } \> } \> vArrayOfEdges[j][0] = vArrayOfPolygons[j]; \> vArrayOfEdges[j][1] = vArrayOfPolygons[vJplusOne]; \> vJcounter++; \> } \> } \> // Test each non redundant edge for a match \> var vMatchCounter = 0; \> var vLowestNilIndexI = 0; \> var vLowestNilIndexJ = 1; \> var vIsafetyCount = 0; \> for (i=0; i<sizeof(vArrayOfPolygons) && vIsafetyCount<sizeof(vArrayOfPolygons); i= vLowestNilIndexI) \> { \> vLowestNilIndexJ = f_find_lowest_nil_index(vArrayOfEdges, vLowestNilIndexI+1, 2); \> var vJsafetyCount = 0; \> for (j=vLowestNilIndexJ; j<sizeof(vArrayOfPolygons) && vJsafetyCount<sizeof(vArrayOfPolygons); j=vLowestNilIndexJ) \> { \> if ( vArrayOfEdges[i][0] == vArrayOfEdges[j][0] ) \> { \> if ( vArrayOfEdges[i][1] == vArrayOfEdges[j][1] ) \> { \> vArrayOfEdges[i][2] = 1; \> vArrayOfEdges[j][2] = 1; \> vMatchCounter++; \> } \> } \> if ( vArrayOfEdges[i][0] == vArrayOfEdges[j][1] ) \> { \> if ( vArrayOfEdges[i][1] == vArrayOfEdges[j][0] ) \> { \> vArrayOfEdges[i][2] = 1; \> vArrayOfEdges[j][2] = 1; \> vMatchCounter++; \> } \> } \> vLowestNilIndexJ = f_find_lowest_nil_index(vArrayOfEdges, j+1, 2); \> if (!vLowestNilIndexJ) break; \> vJsafetyCount++; \> }//end for j \> vIsafetyCount++; \> vLowestNilIndexI = f_find_lowest_nil_index(vArrayOfEdges, i, 2); \> if(vLowestNilIndexI == i) \> { \> // println("Holey HOLE found! I have at least one unshared edge, the first is on polygon ",floor(i/4) ); \> // println(" between points ", vArrayOfPolygons[vLowestNilIndexI], " and ", vArrayOfPolygons[vLowestNilIndexI+1] ); \> return 2; \> } \> if(!vLowestNilIndexI) \> { \> // println("I have no holes as there are ", vMatchCounter, " edges shared on a polygon with ",sizeof(vArrayOfPolygons)/4 ," faces."); \> return 1; \> } \> }//end for i \> } \> \> \> f_find_lowest_nil_index(pArray, pStartIndex, pArrayColumnToTest) \> { \> var i=0; \> for(i=pStartIndex; i<sizeof(pArray); i++) \> if (!pArray[i][2]) return i; \> } \> `