Some algorithms in computer graphics and topology never get a satisfactory solution that is both fast and logically simple to implement. One is line segment intersection , the other is the classic point-in-polygon (PIP) , fundamental to object selection / picking. I was attempting to make an implementation for World Wind for generic PolygonFeature picking.
Polygons rendered can be quite complex with holes and are curved to the earth's surface. 2D-topological solutions may not be adequate in all cases and DirectX based object selection may not be accurate. There are multiple strategies for PIP solution, here is the summary of a few:
1: Ray-Trace Test
2: Winding Number Test
3: Successive approximation using grids and bounding boxes
4: Triangle test
Not all strategies work for complex polygons(re-entrant,concave, with holes and what have you), and need to be carefully chosen for intended use and efficiency.
The strategy I am proposing for World Wind will be bounding box checks then rigorous checks using winding rule for holes and outer ring, that is if I don't get lazy and choose to use NTS instead, or just tag any quads being rendered using Direct-X ( filled polygons at altitude) and use DirectX picking.
Wednesday, October 10, 2007
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment