Jeremy Biddle
Roberto Downs
=93Computer Rendering of Stochastic Models=94 by Fournier, Fussell, and=20
Carpenter
---------------------------------------------------------------------------=
---
The problem presented by this paper is the generation of natural=20
irregular objects and phenomena without undue time or space=20
overhead within realistic pictures by computers. The authors describe a=20
solution to this problem which models objects as sample paths of=20
stochastic processes. Efficiency through implementation is stressed as=20
a major factor in the value of a new approach to object modeling in=20
computer graphics. The authors introduce a new algorithm which=20
computes a realistic, visually satisfactory approximation to fractional=20
Brownian motion in faster time than with exact calculations. An=20
immediate benefit of such an algorithm is that it allows the=20
computation of a surface to arbitrary levels of detail without increasing=
=20
the size of the database; thus, complex objects can be displayed using=20
small databases. Citing sample code in Pascal and offering a full view=20
of the logic behind the algorithm, this paper allows the mathematically=20
challenged a view into the model created by the authors. The analysis=20
of the algorithm seems solid as well as the discussion regarding=20
further applications of the model, including issues such as creating a=20
series of images of a scene in which smooth, continuous motions of=20
objects in the scene are depicted. While presenting a solution to the=20
problem posed, this paper is persistent in its claim that the stochastic=20
properties of the real world can benefit greatly from such approaches,=20
and -- more or less -- I am convinced that this is so.
---------------------------------------------------------------------------=
--
=93Developmental Models of Herbaceous Plants for Computer Imagery=20
Purposes=94 by Prusinkiewicz, Lindenmayer, and Hanan
---------------------------------------------------------------------------=
--
This paper presents a method for modeling herbaceous plants which is=20
suitable for generating realistic plant images and animating=20
developmental processes. The authors suggest achieving realism by=20
simulating mechanisms which control plant growth in nature. This=20
approach can also be extended to the modeling of leaves and flowers.=20
The plant modeling method chosen by the authors offers the=20
simulation of the development as the key to its realism. In other words,=20
to model a particular form, the authors attempt to capture the essence=20
of the developmental process which leads to the form. The reasons for=20
this are founded within the study of biology. The developmental=20
approach to plant modeling has two approaches: (1) emphasis on the=20
space-time relation between plant parts, and (2) inherent capability of=20
growth simulation. The authors reenact plant development by=20
simulating natural control mechanisms and simulate developmental=20
processes using the formalism of L-systmes. Thus, this approach to the=20
modeling of plants has its origin in biological studies expressed in=20
terms of L-systems. The authors place an emphasis on the modeling of=20
compound flowering structures or inflorescences. The control=20
mechanisms which govern inflorescence development follow: (1) the=20
phase beauty of sequential growth, (2) the use of delays, (3) modeling=20
qualitative changes of developmental processes, and (4) environmental=20
change. The authors continue by detailing how biologically noted=20
attributes of plant growth are simulated within their system. Problems=20
addressed for further research include: (1) addition of texture, (2)=20
improved surface models, (3) time step control, (4) analysis of=20
simulation complexity, and (5) addition of a graphical interface. While=20
the issues pointed out for further research are critical to the end-user, I=
=20
felt that the authors handled the presentation of a solution to modeling=20
plants well. The biological foundations upon which the modeling was=20
based is strong as there are obvious reasons why simulation of natural=20
processes would yield the most realistic visualization. The content of=20
this paper was thorough in regards to the theory behind the simulation=20
even as it lacked any suggested models for user control of the=20
simulation with an efficient -- but powerful -- interface.
---------------------------------------------------------------------------=
-
Bob Gaimari
"Computer Rendering of Stochastic Models"
This paper discusses techniques for rendering realistic, natural objects
within reasonable computing resources. Natural objects, such as a mountain
range, are typically irregularly shaped, and cannot be modeled well with
polygons, splines, or other smooth surfaces without a great deal of
overhead. Also, if you want to zoom in on a picture, you will see the
limits of the model, appearing as simple straight lines or smooth curves.
The main reason for these problems is that the primitives are made up
completely deterministically. This paper attempts to fix these problems by
introducing stochastic functions combined with the deterministic ones. A
very good stochastic model to use (for terrain, for example) is fractals,
or fractional Brownian motion.
They discusses the requirements for an algorithm using fractional Brownian
motion, such as internal consistency (primitive's features do not depend
upon location in space) and external consistency (continuity of adjacent
primitives). There is also a discussion of previous algorithms, which are
all too computationaly costly to use, and they present their own algorithm.
Their algorithm takes two endpoints and subdivides it in two parts,
changing the midpoint proportional to the standard deviation.
The paper goes on to discuss applications of this model, most importantly
the creation of stochastic modeling primitives. For a one-dimensional
primitive, they give an example showing the coastline of Australia
represented as a simple polygon with 8 points, and applying the stochastic
interpolation to give it a much more realistic appearance. Even though
this does not produce an exact match (since it is random, and not based
upon real data points), it produces a very authentic looking coastline.
They also discuss two-dimensional primitives, used for displaying mountain
ranges or planet surfaces. Here, instead of subdividing lines segments,
they subdivide polygons into smaller polygons of an appropriate resolution.
They also briefly mention applications in motion of irregular objects, such
as uncrumpling a piece of paper.
"Developmental Models of Herbaceous Plants for Computer Imagery Purposes"
This paper concerns modeling realistic plants. They've developed a grammar
which allows them to model not only what a plant would look like, but how
it develops into that state. Drawing is done using a turtle-like device,
moving in 3-D, which takes a string in this grammar as input, and follows
its instructions, drawing lines, branching, drawing polygons, etc. The
turtle can also be affected by variables representing gravity (pulling a
plant downward) or sunlight (pulling toward the light).
They then go on to show some examples of these rewriting rules, to show
different types of growing processes. For example, some plants delay
producing a flower until a certain number of leaves have grown, or certain
changes in the environment have occured. The way these plants are "grown"
can be seen to be modeled by these rules. The paper also discusses rules
for drawing leaves, buds, flowers, fruits, etc.
Daniel Gentle
John Isidoro
Dave Martin
Computer Rendering of Stochastic Models
Fournier, Fussell, Carpeneter
(with objections by B. Mandelbrot)
The primary contribution of this article is the algorithm on its sixth page
and the ensuing discussion of stochastic primitives. Previous algorithms
for computing sample points are claimed to have unsatisfactory running-time
requirements and unfortunate boundary behaviors, whereas the presented
algorithm runs in linear time and exhibits external consistency (i.e.,
continuity along stochastic primitive boundaries).
The background material on fractional Brownian motion is not very
enlightening, although it may be technically complete. It is not clear to
me what w is used for in B(u,w), and I have no intuitive feeling for the
meaning of the fractional parameter H of fBm. The authors write that "one
of the features of fBm is an infinite span of interdependence", which seems
to contradict the definition that B(u2,w)-B(u1,w) is independent of
B(u4,w)-B(u3,w) whenever (u1,u2) and (u3,u4) are disjoint. The
interdependence may be realized in some different fashion, but it would
have been worth a sentence to clear this up. The rest of the paper almost
dismisses these formalisms, noting that "any approximation which is
sufficiently good to pass our visual test may itself be likely to be an
equally good model by these statistical tests." In the final analysis, fBm
seems to be a generalization of Bm that is appropriate for some unspecified
(but cited) reason, and the presented algorithm may approximate fBm.
The three essential requirements for a reasonable path-computing algorithm
are (1) efficiency, (2) internal consistency, and (3) external consistency.
Internal consistency means that the object's features are independent of
its position, orientation, or size---except that consistent details may
emerge at larger magnifications. This can largely be realized through the
use of seedable random number generators and breadth-first rendering (which
their sample algorithm does not implement). As mentioned, external
consistency has to do with the continuity of adjacent objects. Zero-order
continuity is achieved in their algorithm by having the "random" numbers at
the boundaries be a function of the endpoint locations themselves.
Their impressive example is the rendering of a very believable outline of
Australia using only 8 sample points. I can't help but think that
something's fishy, though, since all of their images show the coastline
bending more or less in the right direction! Is this a likely result of
the fBm process, or did they just choose to publish the improbable results?
Things become a little trickier in the 2D case. The first primitive
discussed is polygon subdivision with random displacements. Even if the
same randomized displacements are used on adjacent polygon edges, the
polygons will most likely have different surface normals, and so
displacements from those normals will cause visible gaps in the surface.
One possible solution is averaging the normals of surrounding polygons;
another is forcing the displacements to be taken along the normal of the
original (nondisplaced) polygon. The latter technique is faster and has
desirable statistical properties, but it also makes higher-order
discontinuities strikingly clear. The displaced points can alternatively
be used as control points for parametric surfaces.
The second 2D primitive addressed is stochastic parametric surfaces.
Figure 16 shows the key to maintaining consistency in the computed surface;
consistency is realized in the order of interpolation.
The rest of the paper describes the figures and hints at some of the
implementation details. The authors suggest other applications of the
general technique, such as color gradation and turbulent motion.
Developmental Models of Herbaceous Plants for Computer Imagery Purposes
Prusinkiewicz, Lindenmayer, Hanan
This paper describes a method for generating plant images that explicitly
relies on the plant's growth and development, at least the parts of it that
are visually interesting. This makes it easy to display plants displaying
many simultaneous stages of development, and naturally leads to growth
visualization. The authors concentrate on herbacious plants, since their
development is less dependent on the environment than woody plants.
The technique used is a simple attributed context-sensitive grammar (also
called an L-system). Some nonterminals denote visible branch segments, and
others are used only in the derivation process. Since the plants in
question are all topological trees, they can be easily represented with a
text representation highly reminiscent of Lisp S-expressions: for instance,
A[BC][D[EF]G] begins with an A and then splits into two branches, the
second of which has a subbranch EF between segments D and G.
It is not shocking to find that CSGs can generate realistic plant images,
since these are really rather powerful grammars. Any language that can be
recognized in linear time is generated by a CSG, and vice-versa. Since
most plants exhibit essentially local structures, (e.g., a flower's petals
demand the presence of its sepals, which demand the presence of a branch,
etc.), recognizing them is intrinsically easy.
Attributes are used in the grammars to control the rendering of the image.
Example attributes cause the turtle to rotate, change colors, start a new
branch, and so on. Additionally, the system supports tropism, which
imposes a fixed vector bias on rotation attributes. This allows the
generation of realistic effects such as bending towards light or gravity.
There are many other extensions to standard CSGs useful for this
application. These include subscripting of nonterminals for arbitrary
growth and extension, the ability to completely switch CSGs at a certain
time, and probabilistic transitions.
I suspect that the major contribution of this paper is its exposition of a
specific language that people can use to generate beautiful images with
very short programs. The fact that the images are rendered developmentally
seems to be a direct consequence of the use of L-systems, which had
certainly been used to describe plants before. It seems like it would take
a fair amount of effort and experience to build a CSG for a specific plant,
but chances are that the resulting program would also be surprisingly
short.
The system does not directly support smooth growth animations. Part of the
growth is realized through nonterminal replacement---an intrinsically
discrete operation---and part through the choice of angles and lengths
associated with the attributes. To grow a plant slower, the CSG has to be
rewritten. The system also does not seem able to easily model death and
decay. Still, the output is very impressive, and I'm quite sure that even
most "unrealistic" plants are very interesting.
John Petry
"COMPUTER RENDERING OF STOCHASTIC MODELS," by Fournier, Fussel and Carpenter
This paper describes a method of generating images of realistic, natural
objects whose surface properties are best modelled by stochastic functions,
rather than as smooth polygons. The method is essentially that described
in class. It works best on objects that have low signal to noise ratios.
A highly desirable property of the authors' algorithm is that it runs in
O(N) time, rather than O(N logN) or even O(N^2) time. Essentially, it
generates detail appropriate for the current resolution, neither wasting
cycles on interpolating points below what is visible, nor failing to generate
necessary detail and thus leaving the surface artificially smooth.
The two key requirements for a good algorithm are that it be internally and
externally consistent. The internal consistency means that it is independent
of viewing angle, coordinate choices, etc..., and that it is scale independent.
While not easy, these are simpler to enforce than external consistency,
meaning that piecewise models maintain continuity across boundaries.
One reasonable way they present to enforce external continuity given a set
of initial points is to generate a curve connecting them, where the curve
itself meets the continuity requirements (e.g. using splines with C1 or C2
continuity). Then modify the curve using the stochastic algorithm.
One point to bear in mind is that sub-regions must also enforce external
continuity. They suggest doing this by saving and sharing the random numbers
used to produce the results at shared points. This seems somewhat awkward;
it would seem easier to simply mark these points the first time they are
computed, and not recompute them when the adjoining region is computed.
(Unless I'm missing something).
They bring out the good points that although the computations can be done
interactively as the user zooms or translates, old values or random number
seeds must be saved to insure that the same image is produced when the user
returns to a previously-viewed configuration. Also, a good clipping algorithm
is required to insure that excess points outside the view are not computed.
Overall, it's a good paper, and is quite clearly written.
"DEVELOPMENTAL MODELS OF HERBACEOUS PLANTS FOR COMPUTER IMAGERY PURPOSES,"
by Prusinkiewicz, Lindenmayer and Hanan
This paper describes an algorithm for generating images of synthetic plants.
Tree branching is specified by a bracketed string language which nests
substructures, combined with a simple rule system which specifies how the
tree is to branch at each iteration.
The rendering is handled with the help of LOGO turtles, which I didn't follow.
The rule system is very easy to follow for simple, 2-D structures. For more
complex structures, or when the number of constraints is high, it takes a lot
more effort to understand. Given their visual representations of their model
in Figures 1, 2 and 3, I almost wonder that they don't develop a GUI to
describe the basic structure and rules.
It seems to break down a bit in 3-D. They mention that surfaces are
represented by pateches, which can't grow, resulting in the need for different
models to reflect time changes.
Given moderately simple rules and a bit of stochastic processing as in the
first paper, this seems like a great way to generate complex plants. It
should also be easy to quickly view how changes in the constraints change
the resulting plants, though I'm not sure if the more complex rule sets
are easy to modify to achieve a desired result.
Although plants are an obvious first choice for this, I suspect this
approach could be extended to other types of creatures, though I'd have to
think about that for a bit.
Robert Pitts
Computer Rendering of Stochastic Models
Fourier et al.
==============
The article addresses the use of stochastic processes to model and
instantiate certain natural objects. Traditional deterministic
techniques are often inadequate for such objects because of their
complexity and randomness. A stochastic process reduces complexity by
requiring only storage of a small set of parameters that control the
evolution of the process. This is in contrast to storing thousands of
polygons (or whatever basic primitive would be used in a deterministic
technique). Furthermore, the probabilistic nature of stochastic
processes model the randomness well.
Another limitation of deterministic models is that they determine at
what scale detail is generated. If a user was then to "zoom in" on an
object, the apparent detail would be bleak because detail was not
generated at that level. In contrast, stochastic processes can be
interpreted at finer and finer intervals to give finer detail. It was
not clear to me whether there aren't some deterministic models that
provide more detail at finer levels of interpolation.
Stochastic processes chosen to model a particular object can be based
on actual mathematical models of an object or chosen from a set of
processes that give the desired appearance (perhaps from a core of
usable processes). In either case, there needs to be an algorithm for
approximating the process to implement detail of a certain depth.
Two issues in using a stochastic process to generate natural objects
are "internal consistency," that the internal details of an object do not
change at different positions and levels of detail, and "external
consistency," that features of objects match up properly. Although
these problems are easier to deal with in deterministic models, the
authors suggest how to deal with them in their examples.
The authors introduce a stochastic process for modeling natural
contours and provide a method for recursively defining levels of
detail. They show one- and two-dimensional implementations of the
algorithm used to produce convincing images. Particularly interesting
is their use of a stochastic process to augment a deterministic shape
with more believable variations. At one point, they describe how they
evaluate a model as successful as what can produce "visually
convincing" objects. Moreover, they note when a particular generated
object has similar physical characteristics of a real object being
modeled--I felt this gave some extra credibility to their claims. In
summary, they should develop techniques for comparing statistic
properties of real and generated objects.
Interesting novel uses of these techniques are presented at the end of
the article. These including varying the stochastic process at
different levels of detail, applying the probabilistic approach to
other parameters of objects than just contour (such as color), and
modeling changes as a function of time to represent motion.
This article was a good theoretic and practical treatise of using a
particular class of stochastic processes to model real-world objects. In
addition, the authors were frank about the "parameter tweaking" issues
that they encountered in their implementations.
Developmental Models of Herbaceous Plants for Computer Imagery Purposes
by Prusinkiewicz et al.
=======================
This article describes a method for generating natural images of a
class of plants by modeling the development of a species using sets of
rules that augment the plant structure over time. The basic geometric
components from which plants are built are simple geometric primitives
such as lines.
The authors present a graph theoretic for describing plants as "axial
trees," which are trees with additional properties such as orientation
in 3-dimensional space. These additional properties are needed to
describe real object that exists in 3-space.
The mechanism for augmenting plant structure over time uses a set of
production rules that can be applied in parallel, an L-system. There
are two types of productions, context-free and context-sensitive, which
operate on the axial tree representation of the plant (the latter
requires information about neighbors of the currently focused-on
portion of the tree). A particular L-system that models the
development of a particular species must be encoded by the modeler.
This requires that the modeler understand how a particular species
develop over time. Although this seems to require quite a bit of
knowledge on the part of the modeler, the authors show that there is a
core of growth behavior that can simulate several types of plant
development.
Since applying a distinct set of rules every time produces
unnatural-looking plants, the authors describe how to allow for
variations. Their techniques include switching between a set of rules
after a deterministically- or probabilistically-determined number of
steps and choosing amongst a set of rules at _every_ time step
probabilistically. Because the production rules implement _local_
transformations, global transformations, such as growing towards a
light source, have to be dealt with external to the production rule
mechanism.
Finally, the authors discuss how this technique, which primarily
describes the development of stems and branches, can be used to model
the development of plant organs, such as flowers and leaves. It does
well when these organs can be modeled with simple wireframes that can
be filled with color or texture. It does not model well organs with
more complex structure because the basic geometric primitives used are
perhaps not expressive enough.
A particular real-time limitation of their technique is described in
the concluding section. The L-system approach transforms the axial
trees from one discrete state to another. Since there is no way to
divide states, the timescale is "fixed" in many senses. Although this
limitation may be critical for some applications, I believe their
choice of a discrete representation is valuable from an efficiency and
simplicity standpoint. A continuous model of development that used
differential equations, for example, would be more difficult to
implement. Finally, I would have liked a discussion of how the
L-system rules interact over time, but this topic may be covered in
cited literature.