tags:

views:

55

answers:

1
+1  Q: 

Finding the polygon in a 2d mesh which contains a point

I have a 3d polygon mesh and a corresponding 2d polygon mesh (actually from a uv map) which I'm using to map the geometry onto a 2d plane. Given a point on the plane, how can I efficiently find the polygon on which it's resting in order to map that 2d point back into 3d?

The best approach I can think of is to store the polygons in a 2d interval tree, and use that to get candidate polygons. Is there a simpler approach?

Edit: To clarify, this is not for a shader. I'm actually taking a 2D physical simulation and rendering it wrapped around a 3d mesh. For drawing each object, I need to figure out what point in 3d corresponds to its real 2d position.

A: 
brainjam  2010-09-08 14:53:39
Thanks, I thought of doing something like this to update to new positions each frame, which would work well given that things don't generally move very far in a frame. Unfortunately, my meshes can be concave or have holes, so I might end up having to use some sort of space partitioning tree, I'm thinking quadtrees instead of 2d interval trees for simplicity.
Henk  2010-09-10 02:32:51
@Henk, when you say your meshes can be concave of have holes, do you mean the polygons?
brainjam  2010-09-10 03:33:39

related questions

Compute the Centroid of a 3D Planar Polygon
Get the Area of a 3D surface
Fastest way to get the set of convex polygons formed by Voronoi line segments
Find the biggest rectangular area consisting only of 2 types of letter in a given MxN board.
Mesh Grid Simplification
General Polygon Clipper: Triangulate without additional vertices
General Polygon Clipper: Attach data to vertex
latitude/longitude find nearest latitude/longitude - complex sql or complex calculation!
Convex hull of 4 points.
CGAL 3.4: How do I get end vertex co-ordinates from a Finite_edges_iterator?
How do I solve an arithmetic sequence?
Computational Geometry open source lib
simple 2d collision problem
How do I iterate over faces in CGAL
Where can I find line buffering code?
Perpendicular on a line from a given point
Generate new polygons from a cut polygon (2D)
Solving for optimal alignment of 3d polygonal mesh
Triangulated Irregular Networks from qhull
Shortest distance between points algorithm
C++ 2D tessellation library?
An algorithm for inflating/deflating (offsetting, buffering) polygons
Find medial axis of a polygon using C#
How to determine if a Delaunay triangle is internal or external?
Algorithm to compute a Voronoi diagram on a sphere?