scott napsal(a):
>> This is traced in the usual way, but the y-values that are found are 
>> not used
>> to place objects anywhere; rather, they are used to statistically(?) 
>> determine
>> whether an object is made or not made at any particular x/z 
>> location...a sort
>> of 'chance' determination, with a HF height of 0 being a zero% chance 
>> that an
>> object is made, up to 1 being a 100% chance.
> 
> I use this method currently too, in a game to place trees and things 
> around the level.  *But*, when you have large areas of low-density, and 
> you want to plant thousands of items, it starts to get slow (because 
> there are so many "misses").  I am wondering if there is a faster way to 
> do it?
> 
> 
As a mathematician, I can say for sure there is:
to sample in one dimension:
-integrate the density function from -inf to x.
	if the function is piecewise continuous (like all interpolations) the 
integral is defined
	if the function is windowed (zero outside a finite interval) the 
integral is finite
	
	for heightfields this means summing some data along a line and 
interpolating the sums.
-find the inverse function of this integral.
	if the density function is nonnegative this is always possible

	computing the inverse function of a piecewise polynomial function 
consists of finding the correct polynomial (e.g. by binary search) and 
finding the solution (e.g. by Newton algorithm or (much more slowly) by 
binary search).
-sample the integral range uniformly
	this is always possible for finite ranges
-evaluate the inverse function at each sample

for multiple dimensions
-integrate the density function in all but one dimension, with the one 
dimension as a parameter.
-sample this function according to the rules for one dimension
-sample the corresponding slice according to the rules for one or more 
dimensions.

It's not easy but it might be plausible :-)

-- 
You know you've been raytracing too long when...
you ever saw a beautiful scenery and regretted not to take your 6" 
reflective ball and a digital camera, thinking "this would have been a 
perfect light probe"
		-Johnny D
Johnny D

Post a reply to this message