Dev Implementation

From AvoCADoWiki

Conceptual overview of Constructing a 3D Solid

• 1. Start a 2D-Sketch on an existing plane (or XY, YZ, XZ if no other planes have been created)
• 2. Place and adjust parameters of 2D-Tools comprised entirely of 2D-Prims (Arc, Line, Quadratic, Cubic, etc.)
• 3. Find all unique closed regions where 2D-Prims intersect
• 4. Decompose regions and into convex polygons (curves are now discretized; too bad)
• 5. Use a 2Dto3D-Tool on the 2D-Sketch to select regions/primitives for construction
• 6. Build a "Constructive Solid Geometry" (CSG) solid model from the regions/primitives/2Dto3D-Tool
• 7. Union/intersection/subtraction with the new CSG solid model and the existing part's solid model.

User Interface

Menuet (mode based menu system)

The hierarchy for the menuet is laid out as follows:

• Project
  • Share (present, sync, etc.)
  • Group (multiple parts)
    • Part (the basic 3D component)
      • Sketch (make 2D drawing)
      • Build (2D->3D features)
      • Modify (3D->3D modifications)

Major Algorithms

CSG Boolean Operations

Constructive Solid Geometry -- Union, Intersection, and Subtractions are performed via the algorithm described in:

Laidlaw, Trumbore, and Hughes
"Constructive Solid Geometry for Polyhedral Objects"
SIGGRAPH 1986, Volume 20, Number 4, pp.161-170

In a nutshell, two solids (comprised of faces to make a water-tight shell) are compared.
Each face (a set of convex, coplanar, noncollinear polygons) is checked for intersection with the other solid.
If an intersection is found, the line of intersection is computed and checked for overlap between the faces.
Each face is then divided into additional convex coplanar polygons so that no polygons intersect.
Once both solids have been subdivided to eliminate polygon intersection, each polygon is classified via ray-casting.
Depending on the closest polygon, if any, that the ray intersects, each face is determined to be:
 - inside  (polygonA is inside solidB)
 - outside (polygonA is outside solidB)
 - opposite,same (polygonA is opposite or the same as what is in solidB).  
Boolean operations (Union, Intersection, Subtraction) are then performed by only including certain polygon types.

Region Formation from list of 2D Primitives

After a sketch has been constructed (a list of feature2D, which themselves are composed of 2D primitives) it is important to be able to find all of the 2D regions that it defines. These 2D regions can then be used to extrude parts of the sketch and create faces on the part.

overview of 2D region formation from 2D primitives.

// 1. find intersections of all prim2D and split them so that none overlap (except at endpoints).
// 2. only keep unique Prim2D.
// 3. get rid of all prim2D that do not connect to others (or themselves) at both ends.
//      these are referred to as "dangling" prim2D.
//
// 4. start from each prim2D still remaining, and walk down connecting prim2D, always taking 
//      the left-most turn possible when the elements branch. 
// 5. check to see what the total angle was for the cycle (is it clockwise?).
// 6. if the cycle was clockwise (!isCCW) then keep it and consume elements in that direction.
//
// 7. perform steps 4,5,6 again but starting at the opposite end of the initial prim2D.
// 
// 8. there is a chance for duplicate cycles, but in opposite direction.. make sure these
//      duplicates are removed.
//
// 9. all cycles are of minimal area and unique!... EXCEPT, fully enclosed regions.
//     (e.g., a circle withing a circle)
//    check to see if every point of each region is within any other region.
// 10. cut the larger region to go around the inner region.
// 
// 11. repeat steps 8,9 until there are no more cuts to be made.
//

Concave to Convex Polygon Tessellation

pseudo-code for "convexize polygon" method

 //  coffeeshop back-of-napkin idea by Adam Kumpf, likely to have bugs!
 //  (but seems to work for pretty much anything I've thrown at it so far)
 
 // "Convexize a Polygon"
 
 pointList = list of all vertices given in order (clockwise, but may be concave)
 while(at least 3 points to consider and index < numberOfPoints)
   ptA,ptB,ptC starting at index%numberOfPoints
   if(angle{ABC} > 0)
     construct potential polygon(A,B,C)
     if(poly doesn't overlap/contain any other point)
       for(every remaining pointD)
         if(angle{poly.LastLastPt, poly.LastPt, pointD} > 0 && 
            angle{poly.LastPt, pointD, poly.firstPoint} > 0 &&
            angle{pointD, poly.firstPoint, poly.secPoint} > 0)
           if(poly doesn't contains any other point)
             poly.add(ptD);
           else
             break;
         else
           break;
       face.addPoly(poly);
       remove all of poly's middle points from pointList
       index = 0;
     else
       index++
   else
     index++;

Perimeter Vertices from a set of Planar Polygons

A face on a part may be split up into many polygons due to rendering limitations of concave polygons. To draw the perimeter of this multi-polygon planar face, the following algorithm seems to work quite nicely.

 // pseudo-code for constructing a list of perimeter vertices from the set of planar, non-overlapping polygons.
 
 List P // list of perimeter vertices
 List G // list of polygons (gets modified, use a copy if G should be untouched)
 
 int lastSize = infinite;
 boolean isFirstTime = true;
 
 while(lastSize > G.size){
   lastSize = G.size;
   for(n=0; n<G.size; n++){ 
     L = G.get(n); // L = a polygon in G (the list of all remaining polygons to add)
     if(isFirstTime){
       add all points of L to P;
       G.remove(L);
       isFirstTime = false;
     }else{
       // look for a shared edge, if it exists, squish polygons together
       boolean gotoNext = false;
       for(i=0; i<L.totalVertices; i++){
         vertPolyA = L.get(i);
         for(j=0; j<P.totalVertices; j++){
           vertPerimA = P.get(j);
           if(vertPolyA == vertPerimA){
             vertPolyB  = L.get(i+1);
             vertPerimB = P.get(j-1);
             if(vertPolyB == vertPerimB){
               // edge matched!
               for(q=i; q>(i-L.totalVertices+1); q--){
                 P.add(j, L.get(q)); // add vertex to perimeter at location "j"
               }
               G.remove(L);	
               gotoNext = true;
             }
           }	
         if(gotoNext) break; // start looking from beginning again since P has changed.
       }
       if(gotoNext) break;  // start looking from beginning again since P has changed.
     }
   }
 }

 P now has the set of perimeter vertices