Triangle based height map

The way I would do this would be to just create a triangle-based mesh that behaves like a heightfield, e.g., no triangles overlap when you look from the top. To query the height, you'd do a ray trace in the vertical direction...this is going to be slower than the very fast row/column lookup and interpolation that is possible with rectangular cells, but it can be quite fast. The idea is, once you have your triangle mesh, build a KdTree (or some other spatial partition) to partition the triangles, then ray trace against the KdTree. The tree will enable you to find a small number of candidate triangles very rapidly, then inside the leaf nodes of the tree you iterate through that small number of triangles and intersect the ray against the triangles. One of the triangles will intersect the ray and will give you the height. (If you are merely querying height, and don't have cliffs/holes or other discontinuities, then you can probably ignore floating point accuracy issues when the ray happens to hit near the edge of one or more triangles.)

Sorry if I wasn't clear; but the main purpose of this is to create ripples on water, and I need some way of subdividing the triangle so I can create a heightmap. I've decided I'm going to do it like this (because i couldn't find a better way), so now I need to figure out how I'm giong to arrange the points in a way with the least amount of RAM/CPU used as possible.

Any ideas?

Quote:

Original post by Phynix Sorry if I wasn't clear; but the main purpose of this is to create ripples on water, and I need some way of subdividing the triangle so I can create a heightmap. I've decided I'm going to do it like this (because i couldn't find a better way), so now I need to figure out how I'm giong to arrange the points in a way with the least amount of RAM/CPU used as possible.

It's easier to think about a right triangle, with the following indexing and vertex placement; then you can transform this to whatever triangle you want (e.g. an equilateral one); here a picture is worth a thousand words:

Indexing:     Vertices (right triangle):   Vertices (equilateral triangle): 1                  (0,1)                      (1/2, sqrt(3)/2) 2 3                  | \                            / \ 4 5 6                |  \                          /   \ 7 8 9 10           (0,0)--(1,0)                (0,0)---(0,1)

If you transform this right triangle by the linear transformation represented by the matrix

    [ 1   cos(pi/3) ]   [ 1     1/2     ]A = [               ] = [               ]    [ 0   sin(pi/3) ]   [ 0   sqrt(3)/2 ]

you get the given equilateral triangle. The inverse of this transformation is

           2      [ sqrt(3)/2   -1/2 ]   [ 1  -1/sqrt(3) ]A^(-1) = -------- [                  ] = [               ]          sqrt(3) [ 0            1   ]   [ 0   2/sqrt(3) ]

which tells you how to go from the equilateral triangle to the corresponding right triangle and hence to the indices.