Transcript Ornament

Computer-Generated
Floral Ornament
Michael T. Wong
Douglas E. Zongker
David H. Salesin
(University of Washington)
-SIGGRAPH 1998-
1
Abstract
• Principles of traditional floral ornamental
design → algorithm
• Adaptive clip art － fit a particularly shaped
region of plane
• Ornamental pattern
– Geometry of pattern is generated as a set of
two-dimensional curves and filled boundaries
– Geometry is rendered in any number of styles
2
Outline
•
•
•
•
•
•
Introduction
Principles of ornamental design
Approach
Implementation
Results
Conclusion
3
Introduction
• Book, architecture
• Web documents, new printing process
• Ornament be generated algorithmically
– Capture the “essence” of ornamental pattern
– Encoding it as a set of rules: adaptive clip art
• Automatically tailored to any particular region
• Problem statement
• Related work
4
Problem Statement
• The problem space of all possible
ornamental design if simply enormous
• Taxonomy
– Elements of ornamental design [Meyer 1957]
– Applications of ornament
5
Element
1. Geometrical elements
－line, polygons, ovals (a)
2. Natural forms
－plants (b)
－animal / human forms (c)
－physiographic features (d)
3. Artificial objects
－shields, ribbons, torches (e)
6
Applications
1. Bands (a)
－finite thickness in one dimension
－infinitely repeating in the other
2. Half-open borders (b)
－constrained along one or more edges
－open in other directions
3. Panels (c)
－arbitrary bounded regions of the plane
4. Open plane (d)
－the ornament typically becomes a
repeating pattern
7
Problem Statement
• Restrict the problem space to the case of
producing floral growth within panels
(application case (c))
• Not focus on design involving strict symmetries
• Explore a series of related approaches
• Principles of floral ornamental design
– Be created algorithmically
8
Related Work
1.
Alexander-SIGGRAPH ’75
－generate the 17 symmetry patterns
in the plane
Grunbaum and Shephard-‘87
－generate periodic tilings and
patterns
purely geometric and
purely on the open plane !
9
Related Work
2.
Glassner-IEEE’96
－frieze patterns
3.
band ornaments
Siromoney and Siromeney-’86
－kolam patterns (a form of ephemeral
ornament practiced in India)
graph grammars could be used to
generate such geometric patterns
10
Related Work
4.
Arvo and Kirk-Ausgraph ’88
－modeling of plant growth with
environmentally sensitive
automata
Greene-SIGGRAPH ‘89
－growth of plant-like branching
structures in voxel space
Prusinkiewicz et al.SIGGRAPH ’94
－generation of ornamental
topiary plant forms with open
L-system
adaptive to space, but not
designed to grow according to
conventions of 2D
ornamentation
11
Related Work
5.
Smith-SIGGRAPH ’84
－modeling of plant growth with a
class of parallel rewriting
grammars—”graftals”
－generate a branching structure
－could then be given visual
character through a
postprocessing step
use a similar two-step
procedure to create first the
structure and then the
rendering of our ornaments
12
Related Work
6.
Beach and Stone-SIGGRAPH ’83
－idea of procedurally generating a simple
repeating border pattern that is warped to
follow the path of a spline
HSsu and Lee-UIST ’93. SIGGRAPH ’94
－”skeletal strokes”: warping of predefined
vector clip art along a path
this paper builds on their approach by
creating a higher-level mechanism for the
automatic arrangement of skeletal
strokes within arbitrary regions of the
plane
13
Principles of Ornamental Design
• Ornament
– The aesthetic enrichment of the surfaces of man-made objects in
ways not directly contributing to their functional utility
– Addresses only a fraction of these principles
• Order in ornament
– Repetition
– Balance
– Conformation to geometric constraints
• Floral ornament
– Growth
– Conventionalization
14
Order in Ornament
• Underlying principle of ornament
– Conveyance of a sense of order or design
• Ornamentalists use three principal techniques in
conveying a perception of order
– repetition
– Balance
– Conformation to geometric constraints
15
Repetition
• The most fundamental
ordering principle
• When forms are repeated
(a)
– may be repeated exactly through
translation and rotation (a)
– Or may be reflected about some
axis, yielding bilateral symmetry
(c) or glide reflection (b)
(b)
• Rotational symmetries
(d)
(c)
– The point of radiation is
positioned off-center from the
design elements it controls
– Leading to a bilaterally symmetric
radiation (d)
16
Repetition
• A more subtle form of repetition is
the use of analogy
– Rhythmic controlling lines are used
to place and constrain different floral
or figurative elements (e)
• The recurrence of almost any
ratio, or proportion, in a design
can impart a pleasing unity of
form
• Color is another powerful attribute
of patterns
(e)
17
Repetition
• Designs based on rigid repetition may appeal to a clean,
austere aesthetic
• Patterns use variation within a class of forms to add
organic dynamism to their composition (h)
• Variation may be achieved
through alternation of color
or form (f)
• Through scaled repetition
18
Balance
• Requires that asymmetrical visual masses be made of equal
weight
• Applied to several compositions (a)
• Crane[1902]－each new line posing a question that requires
an answering line (b)
• Both these principles at work in (c)
(a)
(b)
(c)
19
Balance
• Combined with the primal
motivation for ornamentation,
yields the principle of uniform
density:
-ornament should uniformly fill
its allotted space• Unequal distribution can be
balanced with different elements
of a smaller scale
– Leads to a balance within and
among levels of hierarchies of
visual mass (d)
(d)
20
Conformation to Geometric Constraints
• First and foremost, a careful
fitting to boundaries is a
hallmark of ornament from many
cultures
– Provide appropriate positions for
secondary shoots to invade other
portions of the ornamented region
(a)
– Shapes of the design elements
themselves are sometimes
deformed to better fill space (b)
(a)
(b)
21
Conformation to Geometric Constraints
• Principle of tangential junction
lends a powerful sense of
teleological, or ends-driven,
design to the composition
(c)
– Cut through
– Hang together
– (c) (d)
(d)
22
Conformation to Geometric Constraints
• Layout of motifs is placement at signal geometric
points (e)
• Filling a region that has distinct corners (f)
– Growth motif: the growth is often coordinated by the skeleton
of the region to be filled
(e)
(f)
23
Conformation to Geometric Constraints
• Design of ornament proceeds through the subdivision of
an area followed by the filling of the division (g)
– Act of filling may be viewed as one of subdivision
– Process may be recursively repeated
– Leading to a many-tiered hierarchical composition in the final
design
(g)
24
Floral Ornament
• Floral ornament－any ornamental design
process involving plant-like growth models
– Branching structures
– Plant-like elements
• Vine, leaves, flowers
• Growth
– Progenitor of ornamental design
• Conventionalization
– Plant-like structures can be transformed into
ornamental elements through the process
25
Growth
• Owen Jones－Grammar of
Ornament
– Whenever any style of ornament
commands universal admiration,
it will always be found to be in
concordance with the laws which
regulate the distribution of form in
nature
• Particularly good source for
continuous patterns
– Fill space
– Logically transport a design in to
new regions
26
Growth
• Intention－ordering property
–
–
–
–
Growth tends to be more highly structured, or ordered
Aesthetic perception of teleological growth
Placement of form
Discernible from multiscale features of a design
• High-level：sub-motifs, serial, hierarchical composition
• Low-level：change in curvature, line’s width, angles
– Not just the process of growth in the absence of
external influences
27
Conventionalization
• Development of abstractions
of natural form, a highly
creative process
• Focus is to extract essential
features of form from the
vagaries of environmental
influence
• Nature and conventional
representation
28
Approach
• A given adaptive clip art pattern－a set of element
• Element
– Geometric primitives－comprise the ornament
– Together with a set of growth rules
• How the elements are structured in relation to one another and
to the boundaries of the panel
• L-systems
– Natural choice for expressing out growth rules
– Have been used to model many plant-like structures
29
Using L-systems for ornament
• Develop by biologists
– Seek to model the development of plants
– Create realistic plant images and
animations
• Traditional L-systems vs. open Lsystems
• Generation of ornament differs from
the growth of real plants
SIGGRAPH ‘94
30
Open L-systems
SIGGRAPH ‘96
31
Ornament vs. Plant Growth
• Floral ornaments conventionalization elements are often
connected and arranged in ways that no plant would ever
produce
• Environmental feedback loop for real plant growth is indirect
– L-systems loop by alternating “rule application”, “environment query”
– Procedure: both query the environment and directly act on the
results of those queries
• A successful iteration of system, consists of the selection of
a single element, followed by rule associated with if
32
Adaptive Clip Art
• Elements
– 2D geometric primitives (flowers, leaves stems)
– a collection of one or more proxies
• A relatively simple geometric shape that represents the element
• Locating empty spaces and testing for intersections
• Growth rules
– Procedures
– Perform environmental queries and create child elements
• The framework attempts
– Grow the ornament into large open space
– Shifts to filling in corners of the desired region
33
Implementation
• 600 lines of Perl (preprocessor)
• 3600 lines of C++ (framework)
• Preprocessor reads a rule file
– Encodes an ornamental pattern
• Executable
– Take a region specification and produce the ornamental pattern to
fill that particular region
• Output generated is a PostScript file
– Can be converted to paths and render with skeletal strokes
• Default rendering is provided for every element
– Simply draw each proxy of the element in outline form
34
Rule Invocation
• Framework－decide which elements to “grow”
with the rules in order to fill the given space
• R－region to be filled with a pattern
• Heuristic
– Finds the largest circle C
• Not intersect the boundary R or any element of the design
– Tries invoking rules on the elements within a distance
δof that circle
35
Rule Invocation
• Find the desired circle C
– Start small test circles at various point within the region
– Increase the radius of each circle until if intersects an
element or boundary
• Hits a boundary－discard
• Hitting an element－keep
• Center and radius of C are made available within
rule bodies
36
Rule Invocation
• Determine at which points to center the test circles
– Perform a medial axis transformation (MAT)
• Using the Manhattan distance metric
– A circle is centered on each pixel whose transform value is at least
as great as those of its neighbors
• All the rules on all the elements near a given circle C may
fail to place new elements
– Falling into an infinite loop
– Keep a list of points－exclude list
• A point can be removed from the exclude list in two ways
– A rule is successful in placing elements for a circle C
– A rule body to explicitly clear the list
37
Rule Invocation-Algorithm
initialize element tree with seed points
render boundary elements into buffer
compute initial MAT
initialize empty exclude list
repeat
C←FindEmptyCircle()
find elements within δof C
try elements in order of distance from C
try rules in order specified in rule file
if rule succeeds, break
if some rule succeeded
update element tree
render new elements into buffer
incrementally update MAT
remove points on exclude list within of C
else
add center of empty circle to exclude list
ε
• FindEmptyCircle procedure locates the largest empty circle in the
region, subject to the two restrictions above
38
Rule Invocation-Algorithm
One iteration of the main loop
(a)
(b)
(c)
(d)
39
Elements
• Each design element has a type
(available types is declared in the rule file)
• Each element type is associated with one or more proxies
– circles(circle), arcs(arc), cubic Bezier segments(bezier), line
segments(linesegment), etc…
• Each element contains a few standard fields
– Such as the number of children the element has
• The fields of each proxy are dependent on its type
– A circle proxy, has center and radius fields
40
Rules
• Each rule file must declare the element type seed, with
a single point proxy
• Seed elements are placed by the framework in user
selected locations at the beginning
• Each rule specifies
– what element type the rule acts on (the parent)
– what types of children the rule produces
• Static vs. Dynamic
• Difference: initialize and reference within the rule body
41
Body of the Rule
• Any thing that is legal within a C++ function is legal
within a rule body
• Special dollar-sign tokens provide convenient access to
the fields of the parent and child elements
• Each rule returns a flag to indicate success or failure
– Success
• children created by the rule are permanently added to the ornament
• a new iteration begins
– Failure
• Children elements are discarded
• Framework proceeds to try other element/rule combinations as “rule
invocation”
42
Examples
‧First dot is centered on the seed point
‧Subsequent dots are placed adjacent
to the existing ornament
‧Extend the ornament along the skeleton
of the region
‧Places a flower on top of the initial seed
point (invoke only once)
‧Places a new flower
-connect to an existing flower
-with a new stem segment
-add a leaf to the stem (long enough)
‧Number of children produced is variable
(two or three)
43
Result
‧Chinese vase
‧Two types of stylized flowers
‧Connected by curving stems
‧Small hook-shaped curves
‧Teardrop shapes
‧”intentional” growth
44
Result
‧Hierarchical growth
‧Start from seed point by growing the vines
‧Add red flowers, yellow and blue shapes
‧Connecting then to the main vine structure
(with shorter subsidiary vines)
‧Add leaves
(attached to a vine or floating on their own)
‧Small double-quote-shaped structure
(fill in small gaps)
‧Ordering of rule phases
(by adding “state” preconditions to each rule)
45
Result
‧Willow-leaf wallpaper
‧Add a curved stem with alternating
leaves (overlap)
‧Shortcoming-difficult to do significant
global planning of a design
46
Result
‧Equal- angle spiral
‧Spiral is composed of multiple curved segments
-use of dynamic child creation
-different length require different number s of
segments (smooth)
-orientation opposite to that of its parent
‧Large-scale structures
-outline of boundary space
‧Finer-scale details
-boundary space and evolving ornament
47
Result
48
Result
‧Same spiral design is rendered with four different strokes,
producing a variety of effects
49
Conclusion
• A mechanism for encapsulating growth principles for
ornamental design into “adaptive clip art” patterns
• Implement only a rudimentary tested for these ideas
– Powerful interactive authoring system
• Essentially provide a new medium of artistic expression
– “living”, dynamic patterns that adapt to their environments
• Creating better high-level, interactive tools
50
Future Research
• Ornaments over manifolds
– Creating ornaments over arbitrary manifolds (3D Objects)
• Incorporating global planning strategies
– Now: strategy of growth－largest empty region
– Future: look at the design globally and better incorporate
ornamental design principles (balance, symmetry)
• Putting an artist “in the loop”
– Semi-automatic algorithmic design processes and user interfaces
51