Examined the source code but found the implementation complex to fully understand
Searched existing issues and forums but didn’t find this specific information
Additional context:
While I’ve examined the source code, I’m having difficulty fully grasping the algorithm being used. I understand this might be a complex question, but any insights you could share would be greatly appreciated. Even a high-level overview of:
The core mathematical approach
Key data structures involved
Any important implementation considerations
would be very helpful for my use case.
Thank you for maintaining this powerful toolkit and for any guidance you can provide!
What is your use case? It might help me provide a better answer.
There is no publication or detailed algorithmic description, and I wrote the code 15 years ago so my memory is a little foggy, but here is an overview.
All input polygons must be convex.
1. for each point,
1.1 compute and store the signed distance from the cut plane
2. for each polygon,
2.1. create an empty ID list to hold the new "clipped" polygon
2.2. For each edge of the polygon,
2.2.1. let p0, p1 be the two endpoints that define the edge
2.2.2. let c0 be true iff p0 will be kept (signed distance > 0)
2.2.3. let c1 be true iff p1 will be kept
2.2.4. if one point will be kept, but not both points, then
2.2.4.1. create a new point where the line is cut [note 1]
2.2.4.2. add the ID of this point to list created in 2.1
2.2.5. if p1 will be kept, then add its ID to the ID list
2.3. if the ID list is not empty,
2.3.1. write a polygon to the output using the IDs in the list
2.3.2. If the polygon was cut,
2.3.2.1. store the new edge that was created by the cut
3. join all the new edges together to create "cap" polygons [note 2]
4. triangulate these cap polygon and add the triangles to the output
[note 1]
The new point p lies between the edge points p0,p1 and can be computed from the signed distances s0 and s1 by first converting these to unsigned distances d0 = abs(s0) and d1 = abs(s1). The formula is:
p = (d1*p0 + d0*p1) / (d0 + d1)
Since each edge in a mesh is usually shared by two polygons, we end up visiting each edge twice. The code uses a custom data structure (called the EdgeLocator class) to ensure that any edges that are cut are only considered once, in order to avoid duplicate points in the output.
[note 2]
The “cap” polygons are often not simple polygons. That is, they might contain holes. So the triangulation algorithm that is used must be able to robustly deal with non-simple polygons.