Closed Polygon Object... Edge Looping?



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

    On 19/05/2009 at 00:16, xxxxxxxx wrote:

    User Information:
    Cinema 4D Version:   11.027 
    Platform:      Mac OSX  ; 
    Language(s) :   C.O.F.F.E.E  ;

    ---------
    Hi,
       Some code I'm working on could be made more efficient if I can tell the function whether or not a PolygonObject (polyhedron) being fed to it is closed or if it has holes.
    How to test for holes: My thought is to check each vector pair in a Polygon array to see if it has a partner... if one doesn't, then there must be a hole and I can stop the search for that particular polyhedron. Is this the most efficient plan, or is there a wiser approach? Is there already something built in that I've overlooked?
       Since I'm working in Coffee, I think my only access to the edges is the 1D array created via obj->GetPolygons();
    From there I've tried 4 nested loops
    i loops through the polygons and iterates i=+4
    j loops through the indices in each i iterating j++
    m loops from the i+1 polygon (i.e, i+4th poly index) to the end m=+4
    k loops through the indices in each m iterating k++
    if (polyArr[j] == polyArr[k])
       I test j+/-1 against k+/-1 for any matches and flip a boolean
    Problem with this approach is I'm doing a seemingly inefficient modulo on the endpoints of j and k to account for the 4th edge between A and D in the polygon array.
       Surely I just need sleep and a fresh start, but any suggestions will be much appreciated.
    Thanks,
    Graham



  • 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; \>      } \>



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

    On 20/05/2009 at 11:36, xxxxxxxx wrote:

    Bug in my code or in built in undo?

    The function above returns properly (2) if I delete a polygon or a point in a closed polyhedron. If I undo a polygon deletion, it properly returns (1), but if I undo a point deletion on an icosohedral sphere of triangles, it still returns 2. Is the point order somehow altered when undoing a point deletion?
    Thanks,
    Graham



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

    On 20/05/2009 at 11:43, xxxxxxxx wrote:

    On a default icosohedral sphere, if you select point zero, delete it and undo it, the function properly returns (1) to say the sphere is closed. If you select point 22 for example, and delete it, then undo, it returns 2 until you refresh the code by hitting execute again. Its as if I have some global variable that won't refresh. Choosing a different object and going back to this delete/undone object still reports (2) incorrectly. What gives?
    Thanks,
    Graham


Log in to reply