Re: Fast hit-testing on a heightfield?
- From: "Robert Dunlop" <rdunlop@xxxxxxxx>
- Date: Thu, 31 Aug 2006 05:00:25 -0700
"Robinson" <itoldyounottospamme@xxxxxxxxxxxxxxxxxxxx> wrote in message
news:eccbqi$300$1$830fa79d@xxxxxxxxxxxxxxxxxxx
I have a 3d graph, defined as a 2d array, where each array value is a height (is turned into Z coord in the vertex buffer). What I want to do is provide a cursor (like a crosshair) on the grid wherever the mouse is pointing over it. Because it's a heightfield, I can't simply get the position of the mouse pointer transformed onto the plane as the mouse might in theory be intersecting many triangles. I don't want to have to test each triangle in the heightfield for intersection. Is there an efficient way of doing this? Perhaps rendering each triangle with a different colour and then doing a buffer readback on that pixel (as I might in OpenGL)?
Testing all of the triangles in the heightfield would be major overkill, you should only need to test against a limited number of triangles that cross the ray under the cursor. You may further optimize this by testing against the heightmap first to determine areas of possible intersection, to which can avoid more costly ray vs. triangle tests in areas where there is no possible intersection. You might do something like this:
* Calculate the point in world space under the cursor that intersects with the near depth plane.
* Calculate the point in world space under the cursor that intersects with the far depth plane.
* Step through the resulting ray, starting at the near plane intersection, and calculate the world space coordinate at each point where the ray crosses a boundary between points in the heightfield array.
* Compare the height at the calculated point against the height from the array of the two points defining the boundary.
* (Note: alternatively, calculate the point the ray enters and leaves each "cell" formed by adjacent row and column entries in the heightmap array, and compare these against the four points forming the cell)
* If either point is higher than the calculated point, test for intersection with the local geometry formed by triangles generated by these entries in the heightmap.
* (Note: if the view could be from above or below the heightfield, then you'll need to select a comparison based on the starting point of the ray, checking to see if either point is *lower* if the starting point of the ray is below the elevation at that point in the heightmap)
* If the ray intersects, use the closest point of intersection and return this as the position under the cursor. Since we are traversing the ray from closest to farthest, any intersections detected later on would be behind the intersection we just detected, so no need to search further.
Such a method would minimize the expense of testing for collision with the cursor by A) limiting tests to the area that falls along the ray defined by the cursor, B) using inexpensive tests to avoid intersection tests in areas where the ray cannot cross the heightfield, and C) searching in a view relevant order to avoid further testing once a hit is found.
--
Robert Dunlop
Microsoft DirectX MVP 1998-2006
http://rdunlop.spaces.msn.com/
-------------
The X-Zone
http://www.directxzone.com/
.
- References:
- Fast hit-testing on a heightfield?
- From: Robinson
- Fast hit-testing on a heightfield?
- Prev by Date: Re: OpenGL versus DirectX
- Next by Date: Re: Getting no debug output at all.
- Previous by thread: Fast hit-testing on a heightfield?
- Next by thread: How do I draw lines with a thickness > 1
- Index(es):
Relevant Pages
|
