Geometric modeling (GM) is considered a branch of applied mathematics and computational geometry that studies methods for the mathematical description of shapes as surfaces or solids. These descriptions may be based on mathematical functions used to compute the coordinates of points on or within the shape, or they may be based on discrete samples of points on or within the shape.
Procedural modeling (PM) (The object is defined implicitly by an algorithm, i.e., the shapes emerge from the algorithmic description of a construction process that computes points on or within it). In mathematical and computer sciences, an algorithm is a self-contained step-by-step set of operations to be performed to solve a particular problem. In the context of this paper, we believe there is a clear distinction between the ability to construct an algorithm capable of generating a shape, and the ability to implement an algorithm on a computer. The first ability describes an algorithm, ignoring the implementation details; the second requires a more machine formal description. In this paper we refer to the first capacity.
Both GM and PM are produced using a computer and for computer-based applications, but the user’s cognitive approach to each differs greatly. Usually, end users of a modeling system (architects or engineers) have a rich interface that they interact with by selecting 2D/3D actions that correspond to specific internal computer codes involved in different achievable options. Normal users do not have a background in algorithm techniques and do not have in-depth knowledge of the geometric/mathematical foundations involved in the achievable options. Therefore, user interface (interoperability) remains the main issue between common architects or engineers and commercial modeling systems. In this kind of approximation, users often ignore the essential differences between geometry and computer science in defining/describing a shape.
2.1 Geometric modeling (GM) shape specification based on mathematical functions
This section surveys several techniques for shape specification based on geometric modeling using mathematical functions. Application areas of these techniques are central to computer-aided-design and manufacturing (CAD/CAM) and widely used in many applied technical fields, including shipbuilding, aircraft and automotive industries, as well as architectural and industrial design and computer graphics.
Identifying relationships between the coordinates (x, y and z) of a point on or within a geometric object is helpful to further develop the taxonomy. This relationship may differ depending on how the coordinates are treated [
3]:
-
-
Symmetrical approach
-
Parametric equations, where the coordinates are treated as functional values: \(x=f_x(u,v),\ y = f_y(u,v),\ z = f_z(u,v)\)
-
Implicit equations, where the coordinates are treated as functional arguments: \(F(x,y,z)=0\), \(F(x,y,z)=c\) (isosurfaces)
The functions
g,
\(f_{x,y,z}\) or
F may contain any mathematical expressions. An expression that is only polynomial (the expression may be rational) is called algebraic; an expression that is non-polynomial (trigonometric, exponential, logarithmic and hyperbolic) is called transcendental.
Traditionally, computer graphics has favored the polynomial parametric over the implicit equation because the former is simpler to draw, render, tessellate, subdivide, bound and perform operations requiring detailed knowledge of the surface, and it is more convenient for certain geometric differential operations.
Implicit surface functions naturally describe whether a point is inside, outside, or on a surface, represent blends of volumes and provide an alternative to the often difficult process of filleting and rounding parametric surfaces.
Since parametric and implicit equations have complementary advantages with respect to certain geometric operations, converting from one to the other can be useful. Conversion from the parametric to the implicit form is known as implicitization and it is not always tractable and is often computationally demanding; conversion from the implicit to the parametric form is known as parameterization and it is not always possible. The implicitization of parametric curves and surfaces, parameterization of implicits, and techniques used to circumvent conversions between implicit and parametric representations are discussed in [
4].
2.1.1 Geometric modeling (GM) surface shape specification based on algebraic functions
As mentioned, algebraic surfaces [
5], may be defined parametrically or implicitly. There are some principal means to define algebraic objects that are more complex than low-order surfaces such as planes, quadric surfaces, and tori:
2.1.2 Geometric modeling (GM) volume shape specification based on mathematical functions
The division of space into inside and outside is the basis for the form of geometric modeling called solid modeling. A solid model is defined as a surface and it’s interior. The theoretical underpinnings of solid modeling are found in point-set topology: a solid is defined as a bounded closed regular set of points. Representations achieving this may be divided into three large classes as follows [
8]:
-
Constructive solid geometry (CSG) representing a point set as a combination of primitive point sets. Each of the primitives is represented as an instance of a primitive solid type. Constructive models include more general construction operations than mere gluing (union), namely rigid motions and set Boolean operations (union, intersection, and difference).
-
Decomposition models representing a point set as a collection of simple objects from a fixed collection of primitive objects, combined with a single gluing operation.
-
Boundary (B–Rep) representing a point set in relation to the boundary. The boundary of a three-dimensional solid point set is a two dimensional surface usually represented as patches.
2.1.3 Geometric modeling (GM) surface shape specification based on discrete samples
When designing products with free form shapes, the shape information can be acquired as a set of data points and then the surface patches have to be designed from the same. This modeling is named Point-based shapes. Point primitives have experienced a major renaissance in recent years. Modern three-dimensional digital photography and 3D scanning systems acquire both geometry and appearance of complex shapes, generating point clouds of a 3D shape of real-world objects. An overview of acquisition techniques [
9]:
2.2 Procedural modeling (PM) shape specification based on algorithms
This section surveys several shape specification techniques based on procedural modeling using algorithms. Application areas of this technique are central to computer graphics, industrial design, architectural shapes, city generation, terrain modeling, and so on.
Algorithms are often accompanied by a list of parameters. The term parameter (sometimes called formal parameter) is an intrinsic property of the algorithm included in its definition.
The procedural modeling design focuses on creating a shape based on a selected algorithmic procedure and the set of parameters that characterize it. Moreover, the specific derived shape depends on parameters that are explicit in the information structure and must be evaluated to obtain a specific solid shape. We must be aware that a procedural model comprises all the specific shapes derivable from the representation. Furthermore, the supported design paradigm allows the shape designer to define entire families of shapes, not just specific instances. This added flexibility can be exploited in many ways, and forms an important advance in shape modeling and its applications. Such possibilities are certainly not suitable for all users; they require a fairly sophisticated mathematical background, the ability to design and modify algorithms and substantial training investment.
The principal ideas of procedural modeling (PM) are:
-
The information necessary to generate a given shape is recoverable from the shape’s algorithmic definition. The procedural modeling captures the evolution of the shape from the building blocks, rather than merely specifying the end result of a creative process. The standard geometric model approach has no memory, since the shape’s generation is ignored rather than stored or regenerated for later recovery.
-
PM offers the ability to encapsulate a design and opens up new approaches and possibilities.
-
PM replaces complicated formulas with simple procedures. Thus, it is more in tune with modern computer science than classical mathematics.
-
PM can generate a larger class of shapes.
-
The complexity of a procedure, when measured in terms of the length of the shortest computer program that can generate it, is very small.
When a designer writes a geometric algorithm to solve a shape design and manufacture problem, the algorithm is both a description of the problem and the solution. Geometric algorithmic thinking means:
-
Taking on an interpretative role to understand the result of the algorithm.
-
Understanding how to modify the algorithm to explore new options.
-
Speculating on further design potential.
An algorithmic design enables the designer to define relationships between elements or groups of elements, and to assign values of complex expressions to organize and control those definitions.
As with any design tool, there are positive and negative aspects. The primary advantage is that, once the relationship has been established, the system may run autonomously within its parameters and explore novel solutions that may not be apparent to the designer. The main disadvantage of the parametric-design process is that it is very time-consuming, particularly for inexperienced designers. In the algorithmic approach, designers spend time and effort “designing the design”. Understanding this way of thinking requires considering algorithm-related knowledge, in its broadest sense, in the design process [
11].
Consequently, the algorithm is about rationalization, reasoning, logic, deduction, induction, extrapolation, exploration, and estimation of processes. In its manifold implications, it involves problem solving, mental structures, cognition, simulation, and rule-based intelligence, to name a few. It is well known that to find the algorithm that solves a problem, you first have to know how to solve the problem. Therefore, to paraphrase what tradition says was engraved on the door of Plato’s Academy, the school he founded in Athens, to produce an algorithmic design, “let no one ignorant of geometry enter”. We believe this sentence highlights the need for geometric knowledge to work in this field of design.
The most common types of geometry, and, therefore, necessary for algorithmic design, are: Euclidean geometry, computational geometry, differential geometry, differential topology, algebraic geometry, and fractal geometry. However, designers without much formal training in geometry can rely on the computer to help with geometry teaching, since it allows geometry to be manipulated dynamically and interactively. The proposed taxonomy can be seen in Fig.
1.
2.2.1 Generative modeling
In this article, the representation of a shape obtained by a generative model is considered a shape described by continuous arbitrary transformation of an initial shape called the generator. Generators and transformations may be embedded in a space of any dimension [
12]. Typically, a generative model is formed by transformations of a lower-dimensional generator. As an example, consider a generative surface consisting of all points generated by transformation acting on each point of a 3D curve.
-
Allows a generator be represented by the parametric function \(F(t): R^{l} \rightarrow R^{m} \).
-
Allows a continuous set of transformation be represented as a parametric transformation \(T(p; q): R^{m} \times R^{k} \rightarrow R^{n} \) where \(p \in R^{m}\) is a point to be transformed and \(q \in R^{k}\) is an additional parameter defining a continuum set of transformations.
-
The shape is the parametric function \( T(F(t); q): R^{l+k} \rightarrow R^{n}\).
A generative model allows arbitrary transformation of generators. Usually the base for representing generative models (generators and transformations) is functions of any number of parameters. In this approach, shapes are represented as multidimensional, continuous, piecewise differentiable parametric functions. Ultimately, the shape is a set of points that are the image of a mapping.
The taxonomy proposed split Generative modeling on these branchs: Parametric/Implicit functions [
12,
13], Iterated function systems (IFSs were conceived in their present form by John E. Hutchinson in 1981 [
14] and was popularized by Michael Barnsley’s book [
15]), Subdivision surfaces [
16,
17] and Grammars [
18].
2.2.2 Generative modeling. Parametric/implicit functions
The use of parametric generators and transformations yields a closure property because transformations of a generator can be expressed as a simple composition of parametric functions, resulting in another parametric function. In fact, the use of parametric generators and transformations blurs the distinction between generator and transformation, both are parametric functions:
-
Parametric functions are not the only basis for representing generative models that can be chosen. Generators and transformations can also be determined by implicit functions. An implicit function describes a shape as the set of points that solves a system of equations rather than as the set of points that is the image of a mapping. Although an implicit representation is valuable in many circumstances, rendering general implicit shapes is a costly computation.
-
Partly parametric and partly implicit generative shape:
-
Allows a generator to be represented by an implicit function \(F(x): R^{n} \rightarrow R^{m} \)
-
Allows a continuous transformation set to be represented as a parametric transformation \(T(p; q): R^{n} \times R^{k} \rightarrow R^{n} \) where \(p \in R^{n} \) is a point to be transformed and \(q \in R^{k} \) is an additional parameter defining a continuum set of transformations.
-
The shape can be expressed as the set \(T(x; q) | F(x) = 0, q \in R^{k} \)
-
Totally implicit generative shape
-
Allows a generator to be represented by an implicit function \(F(x): R^{n} \rightarrow R^{m} \).
-
Allows a continuous transformation set to be represented implicitly as \(T(p; q): R^{n} \times R^{k} \rightarrow R^{k} \) can be seen as a transformation of p by determining a q that solves \( T(p; q) = 0 \), where \(p \in R^{n} \) is a point to be transformed and \(q \in R^{k} \) is an additional parameter defining a continuum set of transformations.
-
The shape can be expressed as the set \(T(x; q) | F(x) = 0, q \in R^{k} \)
The transformation set utilized may be linear (affine transformations), fraction of linear functions (projective transformation) or non-linear (deformation transformation).
In general, generative models are easy to control and edit, since they encourage building high-dimensional shapes from low-dimensional components. Generative models are natural for specifying many man-made shapes and digital manufacturing processes. These digital fabrication approaches are known by the names: sectioning, interlocking, contouring, tessellation, and folding.
The usefulness of the generative modeling approach is not limited to mimicking the manufacturing processes. Totally synthetic generators and transformations can be used. Generative modeling can be seen as a device for human modelers to conceptualize shapes. Very complex shapes can be built with a series of transformations that act on simpler generator shapes.
Generative models are not limited to rigid 3D shapes. They can represent shapes deforming in time, shapes that are functions of manufacturing variables, or shapes composed of non-uniform materials. Such shapes can be represented using generators and transformations that are functions of desired parameters. Generative models allow meta-shapes through parameterized generators and transformations [
19].
Usually, as a user interface, a set of symbolic operators on such functions are used to build complicated shapes by simple composition of symbolic operators. All operators in the generative modeling approach are recursive, i.e., their results can be used as inputs for other operators. This recursive property together with the closure property gives the designer the use of any reasonable combination of operations to specify shapes.
An overview of the more usual techniques relationship with Generative Modeling is [
13]:
-
Basic spatial affine and projective transformations are: translation, rotation, reflection, scaling (uniform and non-uniform), shear, perspective.
-
Basic composition of transformation: glide reflection (reflection and a special translation), helical (rotation and translation), spiral (rotation, translation and scaling), other more general composition.
-
Traditional surface classes obtained with simple motions are: translational, rotational, ruled, helical, pipe, sweeping, skinning, other more general spatial motions.
-
Traditional surface classes obtained with deformations are: tapering, twisting, stretching/Compressing, bulging, shearing, bending, more general non-linear deformations.
2.2.3 The deterministic fractal shapes based on iterated function systems (IFS) as a special case of generative modeling
Conceptually, building a deterministic fractal based on IFSs requires two ingredients: a space of geometric shapes \(q_{k}\) and a transformation T that maps a coarse shape \(q_{k-1}\) to a fine shape \(p_{k}\). Given an initial shape \(q_{0}\), a fractal method defines an infinite sequence of shapes by iterating S according to \(q_{k}=T(q_{k-1})\). If the transformation T is chosen appropriately, the limit of \(q_{k}\) as \(k \rightarrow \infty \) is a well-defined shape \(q_{\infty }\) satisfying the fixed-point property \(q_{\infty }=T(q_{\infty })\).
In the standard fractal algorithm, we begin with a compact set \(C_0\) of points and iterate over a collection of (m) contractive transformations \(W_m\) each with a respective contractivity factor (r) to generate a sequence of compact sets \(C_{n+1} = W_m(Cn)\) that converge in the limit to a fractal shape \(C_{m,\infty } = \lim _{x \rightarrow \infty }C_{m,n}\) ; the final shape is \(q_\infty = \cup _{(i=1)}^n W_m(C_i)\).
The principal algorithms used are termed [
15]: deterministic and random iteration.
Each
\(W_m\) is associated with a probability
\(p_i > 0\), where
\(\sum _{i=1}^{n}p_{i}=1\).
\(p_i\) indicates the probability of occurrence of the event
\(C_n = W_m(C_{n-1})\). Despite the use of probabilities, the final shape is always deterministic [
20,
21].
The goal of fractal procedures is to construct extraordinary shapes like the patterns that can be found in nature [
22], unconventional forms as the obtained in [
23], from conventional origins.
One of the simplest methods for constructing fractals involves iterating a set of affine transformations. However, conceptually, it is possible to apply any of the previously presented transformations, provided that the selected transformation turns into contractive property. The problem of intentionality, which consists in finding the necessary transformations from a certain form, is a problem that has not yet been resolved. For example, in the case of IFS, the feasibility is found in the Collage theorem [
24]. However, the exhaustive search of an IFS to approximate a given image is beyond the capabilities of current computing systems. An IFS like that of the fern consists of 24 parameters, so finding their respective values by “brute force” would require a computation time that is impossible to quantify.
The question could be, so what are they useful for, a possible answer could be, so that the designer can find reasons or causes for inspiration.
2.2.4 Subdivision surfaces as another special case of generative modeling
Subdivision surfaces as another special case of generative modeling Subdivision algorithms are similar to fractal IFS procedures. In the standard fractal algorithm, we begin with a compact set \(C_0\) and iterate over a collection of contractive transformations \(W_m\) to generate, in each case, a sequence of compact sets \(C_{n+1} = W_m(C_n)\) that converge in the limit to a fractal shape \(q_\infty =\cup _{(i=1)}^n W_m (C_i)\).
In subdivision procedures, we start with a set \(P_0\) (usually either a control polygon or a control polyhedron, or a quadrilateral or triangular mesh) and recursively apply a set of rules S to generate a sequence of sets \(P_{n+1} = S(P_n)\) of the same general type as \(P_0\) that converge in the limit to a smooth curve or surface \(P_\infty = \lim _{n \rightarrow \infty }P_n\).
Although classical subdivision algorithms are essentially fractal (IFS) procedures, the goals of subdivision algorithms and fractal (IFS) procedures are, nevertheless, fundamentally different. The goal of fractal (IFS) procedures is to construct extraordinary shapes, unconventional forms from conventional origins; the goal of subdivision algorithms is to construct smooth shapes, differentiable functions from discrete data.
The subdivision algorithms are interesting for three reasons:
-
They are easy to understand and simple to implement.
-
They can generate a large class of smooth functions, not just polynomials and piecewise polynomials.
-
Subdivision algorithms on polyhedral meshes can produce shapes with arbitrary topology, unlike tensor product schemes that can only generate surfaces topologically equivalent to a rectangle, or by identifying edges to a cylinder or a torus.
There are three distinct paradigms for subdividing surfaces [
16]:
-
Box spline (a generalization of uniform tensor product B-spline surfaces).
-
Quadrilateral meshes, or arbitrary quadrilateral meshes.
-
Triangular meshes or arbitrary triangular meshes.
2.2.5 Grammars as another special case of generative modeling
A shape grammar consists of shape rules and a generation engine that selects and processes rules [
25]. The foundation of shape grammars has been defined in [
18]. A shape rule defines how an existing (part of a) shape can be transformed. A shape rule consists of two parts separated by an arrow pointing from left to right. The left part of the arrow is termed the left-hand side (LHS); it depicts a condition in terms of a shape and a marker. The right part of the arrow is termed the right-hand side (RHS); it depicts how the LHS shape should be transformed and where the marker is positioned. The marker helps to locate and orient the new shape.
A shape grammar minimally consists of three shape elements: an initial shape, at least one transformation rule, and a termination rule. The initial shape is necessary to start the shape generation process. The termination rule is necessary to stop the shape generation process. The simplest way to stop the process is by a shape rule that removes the marker.
Parametric shape grammars [
26] are an extension of shape grammars. The new shape in the RHS of the shape rule is defined by parameters so that it can consider more of the context of the already existing shapes. This typically affects internal proportions of the new shape so that a greater variety of forms can be created.
Despite their popularity and applicability in academic circles [
27], shape grammars have not found widespread use in generic computer-aided design applications, in part due to difficulties in implementing the identification of sub-shapes for applying rules, and of new emerging shapes that are not coincident with the geometric representation of the existing ones.
2.2.6 Fractal shapes in general
Since Euclid, mathematicians have developed the theory of smooth curves and surfaces. These shapes may have a very complicated structure globally, but in small neighborhoods they are just straight lines or planes. The discipline that deals with these objects is differential geometry. Fractals feature just the opposite of smoothness. While the smooth objects do not yield any more detail on smaller scales, a fractal possesses infinite detail at all scales no matter how small they are.
How are fractals different from the usual Euclidean shapes?
-
Whereas Euclidean shapes have one or at most a few, characteristic sizes or length scales (i.e., the size of a cube), fractals possess no characteristic sizes.
-
Euclidean geometry provides a concise accurate description of man-made objects but is inappropriate for natural shapes. Fractals, however, provide an excellent description of many natural shapes.
-
Finally, whereas Euclidean shapes are usually described by mathematical formulas, fractals, in general, are the result of a construction procedure or algorithm that is often recursive and ideally suited to computers. The complexity of a fractal, when measured in terms of the length of the shortest computer program than can generate it, is very small.
Fractal shapes are said to be self-similar and independent of scale or scaling; in other words, self-similar shapes repeat (statistically or exactly) under magnification with uniform scaling.
When the magnification is with non-uniform scaling, the shapes are (statistically or exactly) invariant under transformations that scale coordinates by different amounts, and the fractal is known as self-affinity.
The distinction between similarity and affinity is important. By way of summary, a self-similar object comprises
N copies of itself (with possible translations and rotations), each of which is scaled down by the ratio
r in all coordinates from the whole. On the other hand, a self-affinity object is the union of
N distinct (non-overlapping) subsets, each of which is scaled down by different ratios in each coordinate from the whole. Fractals can be Self-similar and Self-affine (see Fig.
1).
Fractals come in two major variations termed [
15]:
-
Deterministic. The procedure requires the use of a particular rule that is then repeated over and over in a usually recursive scheme. Application of the same procedure with the same input data, always generates the same shape.
-
Random. The procedure is similar to a deterministic procedure but there is an additional element of randomness. The same procedure, with the same initial data but with different random data, generates shapes of the same family but different from each other.
2.2.7 Generic shapes \(=\) algorithms \(+\) data structures
Many objects and environments contain repetitive or self-similar structures that can be modeled easily using some types of procedural modeling, generative and fractal techniques. This kind of procedural modeling as a mature technology in contemporary commercial systems has pervaded several architectural and engineering domains. After the advent of this paradigm, designers are now endowed with tools to construct new entities. In accordance with its philosophy, any design is viewed as a geometric object resulting from specific algorithmic computations. The type of procedural modeling we are referring to is also known in the literature as “smart geometry” [
28].
These approaches have been used to generate many complex shapes, but each method is mainly limited to a specific class of model or requires considerable user input or guidance. If the new objective is to shift from an instance design to a generic one, the procedural modeling paradigm is broadened by using the “bricks” that allow geometric algorithms to be built. The algorithm may employ conventional mathematical functions, arithmetic operators, vector and matrix operators, integration, differentiation, constraint solutions, constrained minimization, numerical solvers, widely used numerical techniques, data tables, or a rule-based or graph-based approach. It may also employ randomness or stochastic methods, and conditionals and iterations as well. In algorithmic science, a data structure is a particular way of organizing data in a computer so that it can be used efficiently.
In general, a procedural definition is not expressible in closed form. Consequently, geometers cannot understand the surface analytically. In this case, geometric properties can be deduced only through the function’s numerical evaluation. Designers, however, may find considerable flexibility in procedural methods.
The constraint-based algorithmic design is important in CAD/CAM applications. It allows the algorithm used to design the shape to be a function of a given set of parameters and constraints on them. A constraint specifies a relation on or between entities in a model that must be maintained. The following classes of constraints arise naturally in shape design:
-
Geometric relationship as well as metric dimensional constraints.
-
Equational constraints that express relations between dimensional parameters and/or technological variables, for instance (mechanical properties).
-
Semantic constraints that define validity conditions on a shape.
-
Topological relations between entities in a model, such as incidence or connectivity.
Although it would be impossible to describe all the ways algorithms are used to solve problems in a few lines, there are four strategies regularly employed by computer scientists at the core of this modern style of problem solving:
-
Careful problem definition.
-
Logical reasoning.
-
Decomposition techniques, also called divide and conquer. strategies. The idea is to approach a problem by separating it into its constituent sub problems, and then solve each sub problem individually.
-
Abstraction using anything that allows us to concentrate on important characteristics while deemphasizing less important, perhaps distracting, details.
Describing algorithms requires a notation to express a sequence of steps to be performed. The most common option is pseudocode, and the control structure is the mechanism for specifying the proper order the five steps must be performed in: sequential, selection, repetition, control abstraction and concurrency.
There are many different programming paradigms used in the field of algorithmic modeling. From the highest to the lowest capacity to generate shapes they are:
-
Imperative and oriented object: Using classical programming paradigms [
29].
-
Dataflow based: A shape description can be represented by a direct graph of the data flowing between operations [
30].
-
Ruled-based systems: These systems provide a declarative description of the construction behavior of a model by a set of rules. An example is L-systems [
25].