scott wrote:

> 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?

I played with this a bit under on the assumption that the result
is random anyway and a trade-off between quality and speed might
be reasonable. I came up with some sort of tile-based object load
balancing, which basically places a grid over the mask, assigns
object counts to each tile based on relative probabilities, and
then places objects for each tile separately.

The main advantage is that the local tile probabilites can be
normalized, as the lower probabilities are already accounted
for in the lower object count assigned to the tile, reducing
the number of misses (of course, this changes the output due
to clipping of the highest probabilities). I tested this with
a crackle pattern and it saved about 50% of object tests.

The main problem is to estimate the average probabilities within
each tile. In particular, if a tile is estimated at probability 0,
no objects will be placed into it, even if it does contain a small
region of high probability. The best results could be obtained with
an interpolated zoomed down copy of the input mask, but below,
I just use some random samples. However, the sample count should
not be set too high, as reducing the tile size also helps to
fix problems but improves load balancing as well.

As a border case, the number of tiles could be made equal to
the number of pixels in an input image map. In this case, each
pixel will be sampled once, and all objects may be placed without
further tests. In order to be useful, however, the desired object
count would need to be higher than the pixel count ;)

The snippet below expects the existence of two macros
PROBABILITY(pos) and PLACE_OBJECT(pos), so it should be
easy to hook your own mask and output to it. It probably
works best for smooth masks.


#local R = seed(0);
#local NUM_OBJECTS = 10000;
#local METHOD = 2;


// Global debug counters
#declare placed_objects = 0;
#declare position_tests = 0;


// Method 1: Naive placement

#if (METHOD = 1)

#local i = 0;
#while (i < NUM_OBJECTS)
   #local pos = <rand(R), 0, rand(R)>;
   #if (rand(R) < PROBABILITY(pos))
     PLACE_OBJECT(pos)
     #declare placed_objects = placed_objects + 1;
     #local i = i + 1;
   #end
   #declare position_tests = position_tests + 1;
#end

#end // METHOD 1


// Method 2: Tile-based object load balancing

#if (METHOD = 2)

// Method parameter
#local TILING      =  40;
#local NUM_SAMPLES =   3; // Better way would be interpolated,
                           // zoomed down copy of input pigment!

// Derived values
#local TILE_NUM       = TILING * TILING;
#local TILE_SIZE      = 1/TILING;
#local TILE_SIZE_HALF = 0.5*TILE_SIZE;


// Step 1: Sample probabilities

#local TILE_X       = array[TILE_NUM]; // Just for convenience
#local TILE_Z       = array[TILE_NUM]; // Just for convenience
#local TILE_PROB    = array[TILE_NUM];
#local TILE_OBJECTS = array[TILE_NUM];
#local TILE_PROBS   = 0;
#local TILE_INDEX   = 0;

#local i = 0;
#while (i < TILING)
   #local j = 0;
   #while (j < TILING)
     #local pos = <TILE_SIZE_HALF+i*TILE_SIZE, 0, TILE_SIZE_HALF+j*TILE_SIZE>;
     #local TILE_X[TILE_INDEX]       = pos.x;
     #local TILE_Z[TILE_INDEX]       = pos.z;
     #local k = 0;
     #local SAMPLE_PROBS = 0;
     #while (k < NUM_SAMPLES)
       #local pos2 = <TILE_X[TILE_INDEX]-TILE_SIZE_HALF+TILE_SIZE*rand(R), 0,
                      TILE_Z[TILE_INDEX]-TILE_SIZE_HALF+TILE_SIZE*rand(R)>; 

       #local SAMPLE_PROBS = SAMPLE_PROBS + PROBABILITY(pos2);
       #declare position_tests = position_tests + 1; // global debug counter
       #local k = k + 1;
     #end
     #local TILE_PROB[TILE_INDEX] = SAMPLE_PROBS / NUM_SAMPLES;
     #local TILE_PROBS = TILE_PROBS + TILE_PROB[TILE_INDEX];
     #local TILE_INDEX = TILE_INDEX + 1;
     #local j = j + 1;
   #end
   #local i = i + 1;
#end


// Step 2: Balance object load based on relative tile probabilities

#local i = 0;
#while (i < TILE_NUM)
   #local TILE_OBJECTS[i] = (TILE_PROB[i]/TILE_PROBS) * NUM_OBJECTS;
   #local i = i + 1;
#end


// Step 3: Execute normalized probability passes for each tile

#local i = 0;
#while (i < TILE_NUM)
   #if (TILE_PROB[i] > 0)
     #local boost = 1/TILE_PROB[i];
     #local j = 0;
     #while (j < TILE_OBJECTS[i])
       #local pos = <TILE_X[i] - TILE_SIZE_HALF + TILE_SIZE * rand(R), 0,
                     TILE_Z[i] - TILE_SIZE_HALF + TILE_SIZE * rand(R)>; 

       #if (rand(R) < boost*PROBABILITY(pos))
         PLACE_OBJECT(pos)
         #declare placed_objects = placed_objects + 1;
         #local j = j + 1;
       #end
       #declare position_tests = position_tests + 1; // global debug counter
     #end
   #end
   #local i = i + 1;
#end

#end // METHOD 2

#debug concat("Pigment evaluations: ", str(position_tests,0,0),"\n")
#debug concat("Object placements: ", str(placed_objects,0,0),"\n")

Post a reply to this message