Shape Grammar 形状文法

形状文法最早由George Stiny于1971年在国际信息处理联合会IFIP正式提出，并被选为最佳论文，发表在1972年的论文集中[1]。将形状作为元语primitive，使用规则对形状进行生成。论文就抽象几何绘画（2D）和雕塑（3D）领域给出了一套形式化的生成理论。

形式定义

形状文法SG和乔姆斯基在语言学领域提出的短语结构语法PSG相似。PSG用符号集生成1维字符串，SG用形状集生成n维形状。SG遵循PSG的标准定义，有形式语言基础的话，理解起来会容易很多：

$SG = (V_T, V_M, R, I)$

  • $V_T$ 是终结形状的有限集合；

    终结形状出现在最终结果中

  • $V_M$ 是非终结形状的有限集合，有 $V_T^* \cap V_M = \varnothing$，集合的星闭包 $( \cdot )^*$ 是形式语言和自动机的基础知识，不再赘述。

    非终结形状用完即弃，不会出现在最终结果中。一个形状不能同时是二者

  • $I$ 是初始形状，有 $I \subset V_T^* + V_M$

    初始形状可以是任意终结形状和非终结形状的组合

  • $R$ 是形状规则的有限集合。形状规则是产生式 $u \to v$，有 $u \subset (V_T^* +V_M)$，即 $u$ 由 $V_T^*$ + $V_M$ 中的任意元素组成（可以没有终结形状，但必须有非终结形状）；而 $v$ 则有三种形式：
    • A类：$v \subset (u \cap V_T^*)$，$v$ 由 $u$ 中的终结形状组成

      实际上是做了减法，应用这类规则后，将$u$中的非终结形状去掉了。而且此种规则是终结性规则：一旦应用了这种规则，继续应用规则时要么没有可用的规则，要么用了也不会有改变，生成终止。

    • B类：$v \subset ((u \cap V_T^*) + V_M)$，$v$ 由 $u$ 中的终结形状和 $V_M$ 中的形状组成；

      纯生成性规则，因为必须有$V_M$中的形状存在。此类规则其实是冗余的，可以用下面的囊括

    • C类：$v \subset (u \cap V_T^*) + (V_T^* \cup V_M)$，$v$ 由 $u$ 中的终结形状和 $V_T^*$ 及 $V_M$ 中的任意元素组成。

      和上一条相比，多了$V_T^*$中的形状，因此涵盖的范围更广，可以是生成性规则，也可以是终结性规则，不管作为哪种规则，都比A和B多向结果中引入了$V_T^*$中的形状。

一个抽象绘画的形状文法示例：

规则应用

从初始形状开始，不断应用形状规则，可以生成复杂的形状结果。形状规则应用的过程如下，和PSG中字符匹配、替换的过程是相似的：

  1. 在形状中找到和规则中 $u$ 相似的部分 $u’$；
  2. 计算基本图形变换 $\tau$ （平移、旋转、缩放、镜像），有 $u’ = \tau (u)$，即$u$经过了怎样的图形变换变成了形状中的 $u’$；
  3. 对规则中的 $v$ 执行基本变换 $v’ = \tau (v)$，然后使用 $v’$ 替换掉形状中的 $u’$。

使用该形状文法生成抽象绘画的过程：

因为$V_M$是非终结符，因此SG所生成的语言L(SG)是一个不包含$V_M$中任何元素的集合，一个由有限类形状构成的无限集合。

该文法所对应的语言：

Stiny在1970年把上面三个上色之后作为绘画作品Urform I, II, III

终结层次

终结形状的层次和PSG中一样:

  • 初始形状中的终结符层次为0；
  • 当一个形状规则被应用之后，假设规则左侧 $u$ 中的终结形状层次为N，规则右侧 $v$ 中的终结形状的层次有
    • A类规则，为N。这也体现了A类规则的确是终止规则，终结形状的层次不再增加了；
    • B类规则，N+1，体现了纯生成性规则的特点；
    • C类规则，N+1，囊括了B类规则。

终结符的层次：

参考文献

[1] Stiny G, Gips J. Shape grammar and the generative specification of painting and sculpture. Information Processing 71 Proceedings of the IFIP Congress 1971. Volume 2, 71, 1460–1465.