New Patch: QuadTree and Z interpolation

Dec 1, 2015 at 8:01 PM
I found your library to be the best .Net solution for my current project. I made few changes and figured I should submit back what I did.

I changed the points to allow a z (not used for triangulation) so I could calculate an interpolated z for any point on a triangle.

I also found QuadTree crashed when I tried to use it. It looks like it was trying to reference triangles by their index in a list, but that was broken somewhere. I changed it to directly reference the triangle objects and fixed the crash, but found the quad tree was not always putting the triangles into the correct nodes. I re-wrote most of the QuadTree code and have a seemingly working solution.

I am submitting back the full solution that now includes a DanTest project that is a simple form that demonstrates the QuadTree, z interpolation, and the ContainsPoint method I added to the Triangle class.

Thanks to all who have worked on this project.

Here are the changes:

- added ContainsPoint
- added Vertices accessor to directly access the Vertex array
- added BoundingBox that is only calculated when needed
- added ComputeZ that takes a point within the triangle and calculates interpolated z value
- added ContainsPoint required by ITriangle (throws exception)
- added Bounds accessor required by ITriangle (throws exception)
- new constructor taking a list of triangles
- removed IsPointInTriangle and used Triangle.ContainsPoint instead
- changed to use original Triangle objects rather than list indexes
- change Query to return first valid triangle encountered and return null if none are found rather than creating a new list and returning FirstOrDefault()
- replaced the code that determined what region a triangle belonged to (wasn't always working)
  • added another AddPoint overload that also takes in a z value
- added z (not used for triangulation, only interpolation on the result triangles)
- added ContainsPoint
- added Bounds BoundingBox accessor
- added new constructor that takes a collection of triangles and determines min/max from their vertices
- added Intersects method that checks if the bounding box intersects another bounding box
- added EdgesIntersectTriangle that determines if any edge on the bounding box intersects any edge of the triangle
Dec 8, 2015 at 8:08 PM
Thanks, Dan.

I've added a conditional compilation symbol (USE_Z) in the latest commit, but I'm not sure if this will be enabled by default in the future. There's also a new Interpolation class in the TriangleNet.Tools namespace, which can be used to interpolate the z values.

The quadtree in beta 3 was indeed broken. I fixed it in changeset 74908. Still, your implementation seems to be about 3x faster (due to some checks before actually calculating line segment intersections). I'll update the code for the next release.