A lot of mutually different objects could be generated. The task is
to put them into the scene - to find the proper reference points where
the generated objects will be placed. Three different techniques have
been developed and are introduced in this paper. The techniques are
dependent on the dimension of the layout problem. The basic
three-dimensional problem means that the reference points should
be distributed in some pre-defined space. How to describe the given
3D space? The POV-Ray environment gives the answer straightforward:
by a 3D object described by the scene description language.
The same idea should be applied to a two-and-half-dimensional problem
- to find the reference points on top of a terrain. The description of
the terrain should be again any standard 3D object.
Usually (in mathematics) a two-dimensional problem is easier than a more
dimensional. In the layout task, the two-dimensional problem means to
find the reference points on the surface of any 3D object. It is quite
hard indeed, because the 3D models are not described as standard
meshes, but they can be any CSG compositions of non-elementary
4.1 Layout inside an object
Given are a 3D object (to become the skeleton for the layout
- the layout object) and a parametrical description of the
object to be many times generated (the object's macro - the
macro object). The task is to find the so-called reference
points in the layout object to place the objects generated
by the macro. The ray-tracing capability of POV-Ray gives
the opportunity to call a function inside to ask if a (3D)
vertex is inside the layout object. The algorithm is quite
straightforward: generate random vertices inside the bounding-box
of the layout object, for each randomly generated vertex ask if it
is inside the layout object and if the test succeeds, a reference
point has been found.
Figure 3: An example of the layout inside technique. The layout
object is a conical object representing the soup. The objects
in the soup are automatically generated by the soupElement macro
4.2 Layout on top of an object
The input data specification is the same as in the layout inside,
but now the generated reference points should be on the top of the
layout objects. This is the most common layout request - the basic
association when talking about mass scenes is a crowd of people. And
the people generally stand on a ground. During the scene preparation
the author knows the exact 3D model of the layout object (e.g. a
street, a forest terrain, etc.) where he wants to have an automatically
Again the ray-tracing capabilities are used. The rays are not fired
as usually (from the eye through the projection plane), but they
start somewhere above the layout object, and they are heading
directly downwards. If the ray hits the terrain object, a reference
point has been found to place an object (to use the macro to generate
an object automatically).
To summarize the algorithm: find the bounding-box of the layout
object, generate random vertices in the top face of the bounding-box,
for each of these randomly generated vertices make a ray directed
downwards (in the proper coordinates), use the ray-casting method
for the layout object. If a hit occurred the reference point has
been found, otherwise repeat the process again.
Figure 4: Characters generated on the terrain using the
layout on top technique.
4.3 Layout on the surface of an object
The input data specification is the same again - the macro of the
object to be generated many times, and the object that will serve
as the skeleton of the layout. The task is to find a random vertex
on the surface of the layout object with constant density function.
The constant density function requirement is very important, because
there is the need of uniform distribution of the generated reference
points on the layout object's surface. Why? A typical surface mass
scene - a hairy monster, could answer this. It is expected that the
density of the hairs of the monster is the same everywhere on its
body. If the reference point's distribution were not uniform, there
would occur some areas with higher hairs presence.
An algorithm to find the random reference points on an object's
surface is again based on the ray-casting technique. Two random
vertices on the surface of a bounding sphere are generated, their
connection constitutes a ray (that is actually fired from the first
vertex heading towards the second), and the first intersection of
the ray with the layout object is taken as a reference point. The
reference points do not have necessarily the uniformity property
that has been demanded (in cases the layout object is not a sphere),
but it works quite fast. To obtain the uniform reference points
distribution, a simple check for the relative reference point
distances can be applied - if a ray in the algorithm has hit a
vertex, it becomes a reference point only if the distance to all
other reference points is greater than a given value.
A big disadvantage of this method is that if the layout object
has too concave surface (e.g. a vase) the probability of hitting
a vertex on the inner surface of the object is too small. In most
situations, this is not a serious drawback because the concave
parts of objects have usually limited visibility (if it is hard
for the rays to get into the vase, it is also hard to see there).
However, to solve this handicap another method has been developed.
The second algorithm gives better results but is (much) slower.
It finds the reference points on the surface of any object (or
almost any - except some fractal-based surfaces) with uniform
distribution. The idea is that random vertices are generated in
the bounding-box of the layout object. For each of these vertices
a very small (smaller than the smallest bend of the layout object's
surface) sphere is considered. On the surface of this sphere a random
vertex is chosen (called s; let the sphere centre be called c). A ray
is fired starting from the vertex s, targeting the centre c. If the
ray hits the layout object's surface on the line between s and c,
the vertex that was hit is a reference point. This algorithm provides
reference points with uniform distribution on the surface of the
Figure 5: The layout object.
Figure 6: A hairy monster. The result of the
layout on the surface technique.
4.4 Layout parameters
After a reference point is generated, the object creation macro is
called to create the object to be placed at that reference point.
There is nothing that prevents the macro objects from mutual
overlapping. An instrument that forbids the overlapping is the
minimum distance parameter. If a minimum distance is provided,
for each new reference point that is generated, the distance to
the nearest reference point is taken (it is the minimum distance
to all reference points) - and it is checked if it is greater than
the given value. If not, the reference point is discarded and the
respective generation algorithm continues. After a given number of
unsuccessful retries the algorithm stops with the output that no
more reference points could be found.
Another parameterization is to allow the object's macro to be
called with additional environment describing parameters. The
macro has the possibility to alter the generated objects depending
the location in the scene (the reference point). The macro
object is able (for instance) to change its color or size according
to the location. If the scene is a crowd of people, the persons (or
their heads) could be rotated according to their locations to look
at some special place (e.g. the audience looking at the ball in a
the ground orientation (the normal of the ground). This parameter
describes the elevation of the ground at the reference point. It is
useful (for instance) to rotate the hairs of a monster so that the
roots of the hairs are perpendicular to the layout object's surface.
the color of the layout object at the reference point. This is very
useful to generate the macro objects with different behavior at
different places in the scene. Typical example is a meadow with
flowers, where the flower-types are chosen according to the texture
of the meadow base object - if the texture is some gradient
transition, one side of the meadow will have a majority of
one type of flowers, the other side will have flowers of the
second type. It is also possible to alter the height of the
grass blades according to a well-chosen texture.
Also one important output parameter has been developed: The macro could output a boolean value determining if it wants to be generated (with the proposed settings) or not. For instance in a scene with characters on a terrain it is not very common to have a character on a high slope where the elevation is too big. The object's macro can check the input parameters and decide that the proposed reference point is not very suitable for the macro object to be generated there. It outputs false and the reference point generation continues with another try.