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