mag@eniac.inesc.pt (Manuel Noronha Gamito) (03/31/91)
Hi, guys! Perhaps somebody can help me about this: I'm trying to raytrace a procedurally defined height field using Perlin's turbulence function, wich has fractal characteristics. The key problem in this is to find a good ray-object intersection algorithm (I guess this is the most discussed issue about raytracing :-) A rather obvious solution is to discretize the turbulence function into a two-dimensional array and use standard methods for tesselated height fields like Musgrave's gridtracing. I thought of an algorithm that doesn't use that much dynamic memory without being too slow (... I hope): 1- Make the ray go trough a hierarchy of cheesecake extents surrounding progessively smaller areas of the fractal surface. The process stops when a leaf extent is found surrounding an area small enough so that the surface normal is known to be well behaved inside it. 2- Apply Newton's root findind method to calculate the ray-surface intersection. If the area found in 1 was correctly calculated there won't be any stationarity points in it's interior and therefore Newton's method is guaranteed to converge. Could anybody point out possible weaknesses, give sugestions, direct me to good papers on this topic, ... you name it. Thanks! -- Manuel Noronha Gamito, INESC | email: mag@eniac.inesc.pt "There are billions of planets in our galaxy. | mcsun!inesc!mag@uunet.UU.NET Why should this modest planet be the only one to have | Phone: +351 1 545150 living forms? The Cosmos must be filled with life!" | Fax: +351 1 525843
dbc@cs.brown.edu (Brook Conner) (04/01/91)
In article <1727@inesc.UUCP>, mag@eniac.inesc.pt (Manuel Noronha Gamito) writes: |> Hi, guys! |> Perhaps somebody can help me about this: |> |> I'm trying to raytrace a procedurally defined height field using |> Perlin's turbulence function, wich has fractal characteristics. |> |> The key problem in this is to find a good ray-object intersection |> algorithm (I guess this is the most discussed issue about raytracing :-) |> |> A rather obvious solution is to discretize the turbulence function into |> a two-dimensional array and use standard methods for tesselated |> height fields like Musgrave's gridtracing. Musgrave will be fast, since it is basically Bresenham's applied to raytracing. Since you are doing a height field, I think you definitely want to exploit that. Musgrave's is a damn good way to discard large parts of the field. But you don't want to tesselate (understandably, since that's a memory pig). So... |> |> I thought of an algorithm that doesn't use that much dynamic memory |> without being too slow (... I hope): |> |> 1- Make the ray go trough a hierarchy of cheesecake extents surrounding |> progessively smaller areas of the fractal surface. |> The process stops when a leaf extent is found surrounding an area small |> enough so that the surface normal is known to be well behaved inside it. Why not use Musgrave's instead? The "cheesecake" alg is checking parts of the height field the ray comes nowhere near. Why not use Musgrave's (without tesselating, i.e. use Bresenham's) to determine the parts of the field that the ray passes over. Then either "cheesecake" those cells, or go straight to Newton's.... |> 2- Apply Newton's root findind method to calculate the ray-surface |> intersection. If the area found in 1 was correctly calculated there |> won't be any stationarity points in it's interior and therefore Newton's |> method is guaranteed to converge. Keep in mind, that in not tesselating, you will be performing a lot of calculations again and again. I might tesselate, and use Musgrave's to get a best-first-guess to give to Newton's (I.e. a very close approximation) and then use Newton's or something similar to get the final bits of precision. This should be much faster than repeatedly generating recursive cheesecake extents. However, I work on machines with lots of swap (> 100meg), so I don't worry too much about a big block if I need the speed. It's still O(n) space :-) |> Could anybody point out possible weaknesses, give sugestions, direct |> me to good papers on this topic, ... you name it. Musgrave Kolb and Mace in SIG 89 is the newest paper I know of (SIG90 didn't have any "fractals" papers, per se, just some natural phenom stuff at the end) YOu might look at Hart, Sandin and Kauffman, about 200 pages later in SIG89, though. |> |> Thanks! |> -- |> Manuel Noronha Gamito, INESC | email: mag@eniac.inesc.pt |> "There are billions of planets in our galaxy. | mcsun!inesc!mag@uunet.UU.NET |> Why should this modest planet be the only one to have | Phone: +351 1 545150 |> living forms? The Cosmos must be filled with life!" | Fax: +351 1 525843 No prob. Brook -- Brook Conner | Klacktoveedsedstene Brown Computer Graphics | Fortune sez: Brook's Law -- Adding manpower to a late dbc@cs.brown.edu | software project makes it later uunet!brunix!dbc dbc@browncs.bitnet Box 4013 Brown U Prov RI 02912