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