I'm currently giving my particle-system some rest and working
on my vegetation-macros.

The one I'm currently working on will be the essential part
of it all:
It locates a position on a given heightfield, checks for steepness
and vicinity of other objects, and does so until it suspects that
it has reached the maximum number of objects that may be placed
at all...

How does it do that?
1. It generates a position on the heightfield.
2. Checks if surface-normal is not too steep
3. Checks if formerly placed objects are far enough away,
by running through the former data and checking until
too-near-object is found
4. If both checks are successful (i.e. object may be placed),
the position is saved to disc, and loop begins anew.

Though its very basic right now (does not take different
sized objects into account yet), I've already made sure
that user-defined checks and position-generation are
possible (in case someone would like to use something
different than a heightfield).

Nontheless, I'm thinking how I can simplify the method of
counter-checking every new object with ALL objects
that were formerly generated. I do know of the subdivision
method, i.e. creating several blocks and only checking in
those and the nearest blocks, but are there any different
approaches, like sorting all positions somehow?

--
Tim Nikias
Homepage: http://www.digitaltwilight.de/no_lights/index.html
Email: Tim### [at] gmxde

Post a reply to this message

Does anyone know of a method how I could keep track where
the system has formerly spread the objects?

I was thinking about creating a grid, and the system checks how
often objects were placed in certain squares, and tries to locate
positions in rarely used squares, sort of trying to spread the objects
evenly, if possible...

Post a reply to this message

When I wanted to tackle this problem I made a program in a completely 
different language that randomly placed points without letting each 
one's radius intersect any of the other's. The program then spit out an 
array for POV to read. That way, when POV goes to render the scene, it 
doesn't take an enormous amount of time. I never took the prgram to the 
next step: allowing different-sized objects. You can check out the saved 
coordinates in my post to povray.binaries.scene-files, titled 
Pre-calculated, Spaced Vectors.

Tim Nikias wrote:

> I'm currently giving my particle-system some rest and working
> on my vegetation-macros.
> 
> The one I'm currently working on will be the essential part
> of it all:
> It locates a position on a given heightfield, checks for steepness
> and vicinity of other objects, and does so until it suspects that
> it has reached the maximum number of objects that may be placed
> at all...
> 
> How does it do that?
> 1. It generates a position on the heightfield.
> 2. Checks if surface-normal is not too steep
> 3. Checks if formerly placed objects are far enough away,
> by running through the former data and checking until
> too-near-object is found
> 4. If both checks are successful (i.e. object may be placed),
> the position is saved to disc, and loop begins anew.
> 
> Though its very basic right now (does not take different
> sized objects into account yet), I've already made sure
> that user-defined checks and position-generation are
> possible (in case someone would like to use something
> different than a heightfield).
> 
> Nontheless, I'm thinking how I can simplify the method of
> counter-checking every new object with ALL objects
> that were formerly generated. I do know of the subdivision
> method, i.e. creating several blocks and only checking in
> those and the nearest blocks, but are there any different
> approaches, like sorting all positions somehow?
> 
> --
> Tim Nikias
> Homepage: http://www.digitaltwilight.de/no_lights/index.html
> Email: Tim### [at] gmxde
> 
> 
> 


-- 
Samuel Benge

sbe### [at] caltelcom

Post a reply to this message

You could put all the objects in tree-like structures to speed up the
searching process. Order by location: x-coord, y-coord and z-coord --> 3
levels

--
Apache
POV-Ray Cloth experiments: http://geitenkaas.dns2go.com/experiments/
Email: apa### [at] yahoocom
ICQ: 146690431

Post a reply to this message

Samuel Benge schrieb:

> When I wanted to tackle this problem I made a program in a completely
> different language that randomly placed points without letting each
> one's radius intersect any of the other's. The program then spit out an
> array for POV to read. That way, when POV goes to render the scene, it
> doesn't take an enormous amount of time. I never took the prgram to the
> next step: allowing different-sized objects. You can check out the saved
> coordinates in my post to povray.binaries.scene-files, titled
> Pre-calculated, Spaced Vectors.
>

I was thinking about that as well. I've begun studying computer
engeneering last year, but civil service interrupted that, so I'm
nowhere near where I wanted to be by this time... :-(

Nontheless, my brother is a C# addict, and maybe I can get
him to implement some of the more fundamental vector-
functions and create a simple POV-Math-parser for me...

In this case, the only requirement out of the ordinary math
is to read and calculate a heightfield + slope at any given
position.

Then I need File I/O to read the different sized objects...

I'll think about it, but on the other side, I'm a purist... ;-)

With POV, thats what my brother tells me while he is
programming his OpenGL-3D-Engine, time is no
issue, with 3D-Realtime, it is.

I'm POV. :-)

--
Tim Nikias
Homepage: http://www.digitaltwilight.de/no_lights/index.html
Email: Tim### [at] gmxde

Post a reply to this message

Apache wrote:

> You could put all the objects in tree-like structures to speed up the
> searching process. Order by location: x-coord, y-coord and z-coord --> 3
> levels
>

How would you model tree-structures in POV-Ray?

Arrays are likely not to work, since adding and deleting
leafs is near to impossible (in terms of easy handling and
parse time).

I've though about creating some basic routines like trees
etc with File I/O and a well-thought-of naming system,
but first I'd have to dig myself into tree-structures again,
and then into methods/macros of implementing that
to POV...

Using File I/O, its not too difficult keeping track of
positions/normals and their amount when using some
clever String-Parsing and identifiers...


But right now, I was thinking about something simple
to implement. Needn't be the best of the best, just
something to quicken it up a little. If I use a macro
to call that sorting, I could easily update and enhance
it later some day...

--
Tim Nikias
Homepage: http://www.digitaltwilight.de/no_lights/index.html
Email: Tim### [at] gmxde

Post a reply to this message

> ... That way, when POV goes to render the scene, it
> doesn't take an enormous amount of time. ...

By the way, I added a debug which tells me on which object-number
its working on... Now, with 5000 being the limit set by the user,
its neat watching the numbers run at the beginning, and then,
sometimes it occurs that the loop needs to run again for the same
ID (cause it didn't find a valid spot). It runs the loop up to
300 times (again, set by the user), until it concludes that all
positions it would probably come up with, are invalid.

Every now and then... POP, some numbers trickle through. I'm
thinking about adding a Highscore, which keeps track of how many
reruns the loop made for one ID. Though the limit is obviously not
to be beaten (it stops then), after running through the file, you could
see if its perhaps worth to run using the already given data and search
for some more positions...

Hm. That reminds me. I need to add some switch in order to not
completely delete the old data, but use it as basis for further
calculations...

Could become a funny macro-set. When you start Windows,
POV-Ray is set to autostart those macros, and tries to generate
new positions until it will finally give up at an incredible amount
of reruns. How to tackle that POV does write only entire
vectors to disk (not interrupting it from writing a vector
midway) would be difficult though...

--
Tim Nikias
Homepage: http://www.digitaltwilight.de/no_lights/index.html
Email: Tim### [at] gmxde

Post a reply to this message

I've done something similar a while ago, placing different sized spheres on a
plane. I used a blockmap which had a counter for each bin. This prevented me from
trying to add more objects than the array size would allow for, but could be used
to search for the most vacant bin reasonably easily. From memory, I dumped about
32000 spheres (radius 1-5 units) down without intersections in a few minutes. I
don't have the code handy but I could dig it out in a day or so.

MJL

Post a reply to this message

On Fri, 21 Jun 2002 00:01:34 +0200, Tim Nikias <tim### [at] gmxde> wrote:
> Nontheless, I'm thinking how I can simplify the method of
> counter-checking every new object with ALL objects
> that were formerly generated. I do know of the subdivision
> method, i.e. creating several blocks and only checking in
> those and the nearest blocks, but are there any different
> approaches, like sorting all positions somehow?

Simple and lazy solution: use vturbulence on grid with maximal value of
tubulence adjusted to step of grid - no data storing, one pass.

More advanced solution: use probability patterns with speedup of testing and
placing realized with help of "precompiled" functions.

ABX

Post a reply to this message

> I've done something similar a while ago, placing different sized spheres on a
> plane. I used a blockmap which had a counter for each bin. This prevented me from
> trying to add more objects than the array size would allow for, but could be used
> to search for the most vacant bin reasonably easily. From memory, I dumped about
> 32000 spheres (radius 1-5 units) down without intersections in a few minutes. I
> don't have the code handy but I could dig it out in a day or so.

That was the same idea I had! If you'd send me the code, I'd
be happy to have a look at it...


--
Tim Nikias
Homepage: http://www.digitaltwilight.de/no_lights/index.html
Email: Tim### [at] gmxde

Post a reply to this message

> Simple and lazy solution: use vturbulence on grid with maximal value of
> tubulence adjusted to step of grid - no data storing, one pass.
>

I did that some time ago, and IMHO you can actually see that
you've used a grid. The random distribution method makes clutters
possible, and sometimes, an object may be placed which makes
it impossible to place maximum amount of objects, nontheless,
thats quite natural.

>
> More advanced solution: use probability patterns with speedup of testing and
> placing realized with help of "precompiled" functions.

I'm not sure what you mean with this... Preprocessing the heightfield and
trying to predict, how many objects may be placed where, and
then trying to place objects?


--
Tim Nikias
Homepage: http://www.digitaltwilight.de/no_lights/index.html
Email: Tim### [at] gmxde

Post a reply to this message

"Tim Nikias" <tim### [at] gmxde> wrote:
> I was thinking about creating a grid, and the system checks how
> often objects were placed in certain squares, and tries to locate
> positions in rarely used squares, sort of trying to spread the objects
> evenly, if possible...

Some variation of it would probably the right thing to do. For example, DOOM
maintains such a grid, with the list of line segments (sectors' bounds)
associated with each cell. This way, it avoids checking player's (or
monsters') positions against all the lines on the scene.

Post a reply to this message

On Fri, 21 Jun 2002 11:00:22 +0200, Tim Nikias <tim### [at] gmxde> wrote:
> I'm not sure what you mean with this... Preprocessing the heightfield and
> trying to predict, how many objects may be placed where, and
> then trying to place objects?

Since my language skills are limited take a look at below example.
Render this with 3.5.

#include "math.inc"
#include "functions.inc"

#default{texture{pigment{rgb 1}finish{ambient 1 diffuse 0}}}

#declare Count=1000;
#declare Generator=seed(0);

#declare Pattern=function{pattern{bozo}}
#declare Probability=function{Pattern(x,y,z)/10}

#local Min=<-1,-1,0>;
#local Max=<1,1,1>;

union{
#local C=0;
#while(C<Count)
  #local X=Interpolate(rand(Generator),0,1,Min.x,Max.x,1);
  #local Y=Interpolate(rand(Generator),0,1,Min.y,Max.y,1);
  #local Radius=Probability(X,Y,0);
  #if (!C) // first placing
    #declare Placing=function(x,y){f_sphere(x-X,y-Y,0,Radius)};
    #declare Distance=function(x,y){f_r(x-X,y-Y,0)};
    #declare C=C+1;
  #else
    #if(Placing(X,Y)>0)
      #if(Distance(X,Y)>Radius)
        sphere{<X,Y,0>.01}
        #declare t_Placing=function(x,y)
          {select(f_sphere(x-X,y-Y,0,Radius),-1,Placing(x,y))};
        #declare t_Distance=function(x,y)
          {min(Distance(x,y),f_r(x-X,y-Y,0))};
        #undef Placing
        #undef Distance
        #declare Placing=t_Placing;
        #declare Distance=t_Distance;
        #undef t_Placing
        #undef t_Distance
        #declare C=C+1;
      #end
    #end
  #end
#end
  box{
    Min Max
    pigment{function{1-Pattern(x,y,0)}}
  }
  translate 2.2*z
}

ABX

Post a reply to this message

On Fri, 21 Jun 2002 14:20:23 +0200, W�odzimierz ABX Skiba <abx### [at] babilonorg>
wrote:
> #declare Count=1000;

With #declare Count=1500; it reached limit of recursion but it can be simple
avoided with smart script :-)

ABX

Post a reply to this message

On Fri, 21 Jun 2002 14:20:23 +0200, W�odzimierz ABX Skiba <abx### [at] babilonorg>
wrote:
>  #local X=Interpolate(rand(Generator),0,1,Min.x,Max.x,1);
>  #local Y=Interpolate(rand(Generator),0,1,Min.y,Max.y,1);

and of course above could be much speed up with

  #local X=adj_range(rand(Generator),Min.x,Max.x);
  #local Y=adj_range(rand(Generator),Min.y,Max.y);

ABX

Post a reply to this message

Tim Nikias wrote:

> I'll think about it, but on the other side, I'm a purist... ;-)
> 

I justify using external scene creation utilities by:
1. seeing just how long a scene can take to render if you use POV to 
figure out complex coordinates for vector coordinates and objects such 
as meshes
2. realizing that POV supports all kinds of file types for a reason

I'm afraid if I start down the road of absolute purism (a redundant 
statement, I know :) I'll be forced to try and take the brute-force 
apporach to everything, making the render times skyrocket.
I guess I like to take shortcuts if it doesn't drastically reduce the 
quality of the scene!

-- 
Samuel Benge

sbe### [at] caltelcom

Post a reply to this message

Tim Nikias wrote:
> 
> Nontheless, I'm thinking how I can simplify the method of
> counter-checking every new object with ALL objects
> that were formerly generated. I do know of the subdivision
> method, i.e. creating several blocks and only checking in
> those and the nearest blocks, but are there any different
> approaches, like sorting all positions somehow?

Make a big two-dimensional array.  Initialize each value to a negative
number, equal to the radius of the largest object you'll be placing.

Map each object to a position in this array.  Fill in this position with
the radius of the object, plus the amount of whatever
minimum clearance you want between objects.  Fill in the surrounding
spaces with values that decrease from this amount in a linear fashion,
depending on the distance represented between the two; except that
a higher value is never replaced with a lower one.

For each object placed thereafter, check the position in the array
that maps to the center of the object to be placed; if the value at
that spot, plus the radius of the object, is greater than zero, the
object will overlap another; pick another spot.

The array doesn't need to be that precise.

Can't figure out how to tell when the array is full, other than a
brute-force check of the entire array.

Regards,
John

Post a reply to this message

I agree. I started experimenting with cloth particle systems using SDL, but
it was way too slow. I ported the stuff to perl and later on I decided to
use C, because that language is pretty fast stuff.
And maybe I'm a purist myself, because I want to create all stuff myself
instead of using 3D Studio or Maya and plug-ins.

--
Apache
POV-Ray Cloth experiments: http://geitenkaas.dns2go.com/experiments/
Email: apa### [at] yahoocom
ICQ: 146690431

Post a reply to this message

You're both right. Using C# to write own programs is no
act against purism... ;-)

But I like to think of POV-Ray like I think of JAVA:
Once the script is finished, anybody who has POV-Ray,
and is thus the probably only person interested in the
script I've written for POV-Ray (why should a 3D-Gamer
be interested in a non I/O particle system, when my
methods are of no use to him?), can actually run it.
With C#, I'd probably have to compile it for Unix, Linux,
Mac and whatnot (I'm not too sure about all those, but we
all know that different systems aren't fully compatible)...

That's why I like to keep my code in POV-SDL, though I do
think that there could be some way to manage to get the
source-codes compatible. Somehow. Hope so at least.



Apache wrote:

> I agree. I started experimenting with cloth particle systems using SDL, but
> it was way too slow. I ported the stuff to perl and later on I decided to
> use C, because that language is pretty fast stuff.
> And maybe I'm a purist myself, because I want to create all stuff myself
> instead of using 3D Studio or Maya and plug-ins.
>
> --
> Apache
> POV-Ray Cloth experiments: http://geitenkaas.dns2go.com/experiments/
> Email: apa### [at] yahoocom
> ICQ: 146690431




--
Tim Nikias
Homepage: http://www.digitaltwilight.de/no_lights/index.html
Email: Tim### [at] gmxde

Post a reply to this message

You're system keeps track of how much of the ground
is occupied. Its a neat idea, though when combined with
slopes, its hard to predict how much space you actually
have availabe.

But I'll keep it in mind for future projects... Thanks!


John VanSickle wrote:

> Tim Nikias wrote:
> >
> > Nontheless, I'm thinking how I can simplify the method of
> > counter-checking every new object with ALL objects
> > that were formerly generated. I do know of the subdivision
> > method, i.e. creating several blocks and only checking in
> > those and the nearest blocks, but are there any different
> > approaches, like sorting all positions somehow?
>
> Make a big two-dimensional array.  Initialize each value to a negative
> number, equal to the radius of the largest object you'll be placing.
>
> Map each object to a position in this array.  Fill in this position with
> the radius of the object, plus the amount of whatever
> minimum clearance you want between objects.  Fill in the surrounding
> spaces with values that decrease from this amount in a linear fashion,
> depending on the distance represented between the two; except that
> a higher value is never replaced with a lower one.
>
> For each object placed thereafter, check the position in the array
> that maps to the center of the object to be placed; if the value at
> that spot, plus the radius of the object, is greater than zero, the
> object will overlap another; pick another spot.
>
> The array doesn't need to be that precise.
>
> Can't figure out how to tell when the array is full, other than a
> brute-force check of the entire array.
>
> Regards,
> John




--
Tim Nikias
Homepage: http://www.digitaltwilight.de/no_lights/index.html
Email: Tim### [at] gmxde

Post a reply to this message

All my C/C++ code is ANSI, so it compiles on all platforms without too much
tweaking.

--
Apache
POV-Ray Cloth experiments: http://geitenkaas.dns2go.com/experiments/
Email: apa### [at] yahoocom
ICQ: 146690431

Post a reply to this message

Still needs a C++ compiler, not everyone has one... When using
POV, everyone has POV. When using POV, not everyone has
C++. That was the point I would put most emphasize on.

You're right though.

Apache wrote:

> All my C/C++ code is ANSI, so it compiles on all platforms without too much
> tweaking.
>
> --
> Apache
> POV-Ray Cloth experiments: http://geitenkaas.dns2go.com/experiments/
> Email: apa### [at] yahoocom
> ICQ: 146690431




--
Tim Nikias
Homepage: http://www.digitaltwilight.de/no_lights/index.html
Email: Tim### [at] gmxde

Post a reply to this message

Apache <apa### [at] yahoocom> wrote:
> All my C/C++ code is ANSI, so it compiles on all platforms without too much
> tweaking.

  C/C++ code conforming to the ANSI standard doesn't necessarily mean
that it will work in all platforms (or even in more than one specific
platform).

  For example there's nothing against the standard in the following code:

void PutPixel(int x, int y, unsigned char color)
{
  unsigned char* screen = (unsigned char*)0xA0000;
  screen[x+y*320] = color;
}

  However, in most systems it will just cause a segmentation fault, and even
if it doesn't, it certainly will not work as expected.

  Also some things cause surprises among the unaware coders:

char table[10];
int* ptr = (int*)(&table[1]);
*ptr = 5;

  This works ok in some systems (eg. Intel) but in most RISC processors it
causes a bus error (ie. the program crashes).

  Conforming to the standard is not enough to make portable code.

-- 
#macro M(A,N,D,L)plane{-z,-9pigment{mandel L*9translate N color_map{[0rgb x]
[1rgb 9]}scale<D,D*3D>*1e3}rotate y*A*8}#end M(-3<1.206434.28623>70,7)M(
-1<.7438.1795>1,20)M(1<.77595.13699>30,20)M(3<.75923.07145>80,99)// - Warp -

Post a reply to this message