| Latest revision |
Your text |
| Line 86: |
Line 86: |
| | June 18th: | | June 18th: |
| | Fixed numerous bugs both in my code and in test code. Tests are now very rigorous using rotations to generate large numbers of tests (these are nice becuase intersection is invariant under rotation so I still know the answer) At this point it seems that all of the low level functions are very robust. | | Fixed numerous bugs both in my code and in test code. Tests are now very rigorous using rotations to generate large numbers of tests (these are nice becuase intersection is invariant under rotation so I still know the answer) At this point it seems that all of the low level functions are very robust. |
| − |
| |
| − | June 19th,22nd:
| |
| − | Implemented the function MeshMeshIntersect. The final goal of all of these functions, it doesn't handle degenerate cases yet.
| |
| − | Next Steps: test the function very rigorously, since this function uses all of the lower level stuff it serves as a very good integrative test. Also these tests are closer to the sort of thing that it will actually be called on.
| |
| − |
| |
| − | June 25th:
| |
| − | Added integrative tests and tracked down a number of small bugs. MeshMeshIntersect now works perfectly on a nice (meaning not degenerate test case). Learned an important less about ON_SimpleArrays, nesting them cause them to segfault on initialization. Use ON_ClassArray<ON_SimpleArray<T> > instead.
| |
| − |
| |
| − | The only thing left that's need to actually perform CSG on meshes is implementing accounting systems to keep track of the curves and insert them as trimming curves.
| |
| − |
| |
| − | June 30th:
| |
| − | The accounting system to keep track of the CSG meshes is proving to be a tricky problem. The main problem is reconstructing the mesh and figure out which triangle are internal. And which are external. The approach I'm taking toward doing this is to record this information by the direction that the edges we return are pointing. At the end any face with it's normal pointing the same way as it's superface will be part of the external mesh, and any face with it's normally pointing the opposite way will be part of the internal. So the problem becomes maintaining the edge direction correctly. I believe that I've got most of the algorithm worked out but, there are still one or two pathological cases that I don't account for.
| |
| − |
| |
| − | Status July 7th:
| |
| − | I've spent the last few days going over the algorithm. To reiterate the challenge at hand is this. Given a triangle from a mesh intersection we need to figure out whether it was inside of the other mesh (internal) or (outside). Now to aid in this we have the following condition on the lines we get out of the intersection are oriented anti-parallel to the normal of the two intersecting faces. Now there are 5 different types of faces we can get out, note that as of now faces are exclusively triangles:
| |
| − |
| |
| − | Type 1:
| |
| − | Faces which have intersections but in which every line of intersection transverses the triangle in this case the correct thing to do is to load all of the segments from the intersection, and the segments from the edge of the triangle and use them to make closed paths. These closed paths lie along the boundaries between internal and external triangles. Furthermore if a path's normal is parallel to the original triangle's it's external, anti-parallel indicates internal. We then need to triangulate these paths to get the triangles.
| |
| − |
| |
| − | Type 2:
| |
| − | Faces which have intersections but have exclusively internal edges. This is the case that arises if a corner is poking through the triangle but doesn't hit any of the edges. In this case the first step is the same as the above we make the segments into paths, now one of these paths is going the be the edge of the triangle and then there can also be arbitrarily many internal paths. The paths can never cross one another, so the must be either inside one another or completely distinct. To solve this we arrange the paths in a tree, where path B is decedent of path A if B is contained in A. Thus the outer edge is the root of the tree. Then each path we triangulate will be the path and all its children.
| |
| − |
| |
| − | Type 3:
| |
| − | Faces which have intersections of both types, internal and transverse. Again we arrange as paths and then can arrange the same tree we had from type 2.
| |
| − |
| |
| − | Type 4:
| |
| − | Faces which have no intersections but are attached to faces which do have intersections. After we have gotten the answers for all of the above types. We get the connectivity of the faces. If a face is connected to an internal face (through a path which doesn't use external faces) then it is also internal. (Same of course with external.) Thus we can just get all the connected components for them.
| |
| − |
| |
| − | Type 5:
| |
| − | Faces which have no intersections and aren't attached to any faces that do. This occurs when we have one surface completely enclosed in another. (e.g Two concentric spheres) Then the only way to figure out which is inside the other is to do a direct test. The easiest test is simply whether a single point is inside or outside the the other mesh. To determine this for a point P, we simply choose some point in the distance Q, and count the intersections of PQ and the triangles of the other mesh. An even number indicates external, an odd internal.
| |
| − |
| |
| − | July 28th:
| |
| − | Spent last week starting to add support for intersection between paramtric surface. We've decided upon an entirely numeric solution, since algebraic one's are both substantially more complex and prohibitively slow.
| |
| − | Utility Functions:
| |
| − | -Closest Value: returns the closest point in a given interval to a given
| |
| − | -value used when we step off the edge of a surface.
| |
| − | -Push: very useful function that updates parameters move a point in a
| |
| − | -surface along an xyz vector.
| |
| − | -Step: walks a specified stepsize along the intersection between 2 surfaces.
| |
| − | -Jiggle: Given 2 points on different surfaces, that are close to equal,
| |
| − | -tries to find closer ones. Used both to mitigate inaccuracy due to
| |
| − | -stepsize, and to find starting points.
| |
| − | -WalkIntersection: Given a starting points walks, the full intersection
| |
| − | -curve of the two surfaces and returns the resulting Bezier trim Curve.
| |
| − | -GetStartPoints: divides up the surface and uses bounding box methods to
| |
| − | -hone in on starting points, has the huge disadvantage that it finds
| |
| − | -much more than 1 starting point per curve.
| |
| − | -SurfaceSurfaceIntersect: Puts together all the other functions to find
| |
| − | -starting points, walk them and eliminate duplicate starting points,
| |
| − | -getting just the intersection curves.
| |
| − |
| |
| − | Aug 19th:
| |
| − | Have since added a number of functions to round out the functionality of csg system
| |
| − | Classes:
| |
| − | -Face_X_Event:
| |
| − | -analogous to the ON_X_EVENT (which records curve on curve
| |
| − | -intersections and curve on surface intersections) but for BrepFace on
| |
| − | -BrepFace intersections.
| |
| − | Methods:
| |
| − | -Face_X_Event::Face_X_Event():
| |
| − | -on blank constructor to just make a new
| |
| − | -blank instance and one to fill in the values, really nothing to tricky
| |
| − | -going on here.
| |
| − | -Face_X_Event::Render_Curves():
| |
| − | -The intersection between 2 Faces is a subset of the intersection
| |
| − | -between the underlying surfaces depending on what the trim loops look
| |
| − | -like.
| |
| − | -Face_X_Event::Get_ON_X_Events():
| |
| − | -Intersects the 2 new curves with all of the trims in the Face loading
| |
| − | -the result into the x field in the class.
| |
| − | Functions
| |
| − | -SplitTrim:
| |
| − | -takes a trim and splits it at a given parameter using
| |
| − | -ON_Curve::Split(). It then replaces the reference in the m_trim_index
| |
| − | -array to the original trim with references to the left and the right
| |
| − | -side of the split.
| |
| − | -ShatterLoop:
| |
| − | -takes a trimming loop of a face and records its constituent trims and
| |
| − | -an array. Then it destroys the loop.
| |
| − | -Compare_X_Parameter:
| |
| − | -compares ON_X_EVENTS by the parameter of the first curve at which they
| |
| − | -occurred, used to be passed in to
| |
| − | -ON_SimpleArray<ON_X_EVENT>.Quicksort(), and
| |
| − | -ON_SimpleArray<ON_X_EVENT>.BinarySearch()
| |
| − | -Curve_Compare_start:
| |
| − | -Compares 2 curves by starting point, used in
| |
| − | -ON_SimpleArray<ON_Curve*>.QuickSort() and
| |
| − | -ON_SimpleArray<ON_Curve*>.BinarySearch()
| |
| − | -Curve_Compare_end:
| |
| − | -same as above yet for endpoints.
| |
| − | -SetCurveCurveIntersectionDir:
| |
| − | -Same purpose as ON_SetCurveCurveIntersectionDir, which is actually
| |
| − | -unimplemented. Sets the dir flags in an intersection event which is
| |
| − | -very important for what we're doing.
| |
| − | -MakeLoops:
| |
| − | -Creates trim loops out of trims by matching them end to end.
| |
| − | -IsClosed:
| |
| − | -Checks an ON_2dPointArray to see if it's closed, ie start and end
| |
| − | -within some tolerance of one another, and atleast one other point
| |
| − | -outside that tolerance.
| |
| − | -GetStartPointsInternal:
| |
| − | -finds starting intersection points between surfaces that are internal
| |
| − | -to both surfaces.
| |
| − | -GetStartPointsEdges:
| |
| − | -finds starting intersection points between surfaces that are one the
| |
| − | -edges.
| |
| − | -FaceFaceIntersect:
| |
| − | -SurfaceSurfaceIntersect has been renamed to FaceFaceIntersect same
| |
| − | -functionality but it records results in Face_X_Events thus it needs to
| |
| − | -know where to find the faces.
| |
| − | -BrepBrepIntersect:
| |
| − | -handles the work of intersecting 2 breps, intersects all the possible
| |
| − | -face pairs. Gets the results as Face_X_Events, renders the curves and
| |
| − | -shatters the loops. Then reconstructs the trims.
| |
| − |
| |
| − | Aug 26:
| |
| − | New function CurveCurveIntersect to replace the ON_Curve::IntersectCurve which doesn't actually exist.
| |
