4. Layout techniques

Mass Scenes Rendering Framework

page 4 of 8

4. Layout techniques

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

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

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

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


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 on

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 tennis match).
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.

Mass Scenes Rendering Framework, Dušan Bezák, 1999-2001, http://www.ksp.sk/~dushan/dipl/