Yes, the following piece of code, using eval_pigment, gets me a fatal parse 
error: out of memory, while the same code by Kenneth, does not. tested with 
version 3.7 beta 25.

union {
  #while (counter <= 1500000)
    #declare trace_position =
      <rand(S1), 0, rand(S1)>;
    #declare intersexion =
      eval_pigment(mask2,trace_position);

    #if(pow(rand(S2), .333) <= intersexion.red)
     cone { <0, 0, 0>, 0.001, <0, 0.001, 0>, 0.0 translate 
<trace_position.x,0,trace_position.z>}
    #end

    #declare counter = counter + 1;
  #end
  pigment{Black}
  translate <-0.5,0,-0.5>
}


Thomas

Post a reply to this message

Just to stimulate your imagination!  :-)
Something you can only see from the air, like the Nasca plateau.

Thomas

Post a reply to this message

Attachments:
Download 'Kenneth airbrush4.jpg' (174 KB)

Preview of image 'Kenneth airbrush4.jpg'

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

Thomas de Groot nous illumina en ce 2008-05-14 04:09 -->
> "Kenneth" <kdw### [at] earthlinknet> schreef in bericht 
> news:web.4829b56bdace545278dcad930@news.povray.org...
>> "Zeger Knaepen" <zeg### [at] povplacecom> wrote:
>>> Cool, but you don't need the height_field, just use eval_pigment.  That 
>>> way,
>>> you can use any pigment as a mask..
>> Aha, I knew *someone* out there would find a way to improve it (in this 
>> case,
>> both you and Thomas.) I'll have to try this--I've never used eval before.
>> Thanks for the code example.
>>
> 
> In Zeger's example, I would replace .gray by .red (or .green or .blue). 
> Parsing will be much faster, for the same result.
> 
> Thomas 
> 
> 
It's the way to do it whenever the pigment is monochrome. Only take one of the 3 
identical colour channels instead of averaging them.

-- 
Alain
-------------------------------------------------
You know you've been raytracing too long when you've ever "lost" a Julia fractal 
because you're not quite sure how to align things in four dimensions.
Dylan Beattie

Post a reply to this message

"Thomas de Groot" <t.d### [at] internlDOTnet> wrote:

>
> In Zeger's example, I would replace .gray by .red (or .green or .blue).
> Parsing will be much faster, for the same result.
>


That's interesting.  Due, no doubt, to the extra calculations POV has to perform
in turning a full RGB pigment into .gray.

A  more accurate way of getting the pigment pattern's colors into grayscale
would be to substitute a PATTERN for the PIGMENT; it's already in grayscale.
I.e., pattern{bozo...} And--as far as I can tell from section 3.5.11.16 of the
docs--such patterns have 16-bit resolution.

KW

Post a reply to this message

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Kenneth wrote:
> "Thomas de Groot" <t.d### [at] internlDOTnet> wrote:
> 
>> In Zeger's example, I would replace .gray by .red (or .green or .blue).
>> Parsing will be much faster, for the same result.
>>
> 
> 
> That's interesting.  Due, no doubt, to the extra calculations POV has to perform
> in turning a full RGB pigment into .gray.
> 
> A  more accurate way of getting the pigment pattern's colors into grayscale
> would be to substitute a PATTERN for the PIGMENT; it's already in grayscale.
> I.e., pattern{bozo...} And--as far as I can tell from section 3.5.11.16 of the
> docs--such patterns have 16-bit resolution.
> 
	No, they actually have full 64 bits float resolution. But so do the
pigments.

		Jerome
- --
+------------------------- Jerome M. BERGER ---------------------+
|    mailto:jeb### [at] freefr      | ICQ:    238062172            |
|    http://jeberger.free.fr/     | Jabber: jeb### [at] jabberfr   |
+---------------------------------+------------------------------+
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.7 (GNU/Linux)

iD8DBQFIKyXDd0kWM4JG3k8RAkhdAJ9nO6BXCLy0g1FZN0gwWDwngjaS0wCeJRsv
EX7lXMQ3buZkUeEzprvH4C8=
=ib+I
-----END PGP SIGNATURE-----

Post a reply to this message

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

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

Sounds good - I didn't think of that.

> The best results could be obtained with
> an interpolated zoomed down copy of the input mask,

Which funnily enough, in realtime 3D graphics, you usually have access to, 
as they are used by the GPU when drawing your bitmap at small scales.  I'll 
give it a shot - thanks.

Post a reply to this message

"Thomas de Groot" <t.d### [at] internlDOTnet> wrote:
> Yes, the following piece of code, using eval_pigment, gets me a fatal parse
> error: out of memory, while the same code by Kenneth, does not. tested with
> version 3.7 beta 25.

Hi,
  First off, quite a clever idea, props Kenneth.

  Secondly, I haven't yet tried it, but I believe both parse time and memory
usage could be much improved by declaring a function from the pigment once and
then calling the function to get the appropriate value.  This would avoid
declaring the pigment function (which is what eval_pigment does) over and over
again for the same pigment, and replace a repeated macro call with a function
call, which should be much faster.

So for example, before the loop:

#declare Pig_F = function { pigment { Mask } }

Then, instead of eval_pigment:

// For Greyscale images
#declare Intersection = Pig_F(Position.x, Position.y, Position.z).red;

or

// For RGB images
#declare Intersection = Pig_F(Position.x, Position.y, Position.z).gray ;

-The Mildly Infamous Blue Herring

Post a reply to this message

For the fun of it, I re-coded my original method to trace the height_field in a
step-by-step linear fashion, rather than randomly. (The statistical process
still uses rand, though.) And for added fun, I let the found y-values of the HF
determine (somewhat) the scale of the small spheres; the result looks a bit like
halftone printing. (In that process, the printed dots vary in size.) The photo
is of Sophia Loren in the film EL CID--a beautiful film to study
for its lighting and image composition, BTW.

The only value that needs changing here is foobar; it determines the "scanning
resolution" of the traces (and automatically scales the spheres.) It can be any
value at all; it doesn't depend on the pixel resolution of the image_map. I.e.,
the trace rays don't *need* to hit a HF triangle vertex / image_map pixel in
order to return a valid height value; they can hit the triangles
anywhere.

One of the reasons I decided to try this linear tracing scheme was that it might
have some relevance to the time-saving 'tiling' idea that's been mentioned (re:
eliminating unnecessary traces from the large dark areas of the image_map/HF.)
I'm working up an overall tiling scheme, and will be back with it ASAP.

Meanwhile, here's the linear-tracing code. I'm not totally sure what values
counter_x and counter_z should start with--1 or 0. Either one *works* but it
should be a logically correct value. Sorry, my brain is tired...

---------

#declare mask =
     height_field {jpeg "sophia_image.jpeg"}

#declare S1 = seed(6455);
#declare counter_x = 0; // one or zero?
#declare counter_z = 0; // one or zero?
#declare foobar = 200; // You can think of this as the "scanning resolution."

union{

// two NESTED #while loops...
#while (counter_z <= foobar) // number of horizontal rows
#while (counter_x <= foobar) // number of trace rays in each row; reset after
                             // each row is completed.
#declare intersexion =
trace(mask, <counter_x/foobar,10,counter_z/foobar>, <0,-1,0>);

#if(rand(S1) <= intersexion.y)
// MAKE object
 sphere{0,1
  scale (.5/foobar)*(.3 + .7*intersexion.y)
        translate <intersexion.x,0,intersexion.z>
       }

#else
// make NO object
#end

#declare counter_x = counter_x + 1;
#end // of INNER #while loop

#declare counter_x = 0; // one or zero? Resets this for each new row
#declare counter_z = counter_z + 1; // to start a new row of traces
#end // of OUTER #while loop
        texture {....}
}

Post a reply to this message

Attachments:
Download 'sophia_render.jpg' (341 KB)

Preview of image 'sophia_render.jpg'