给你一个数组 nums，你可以执行以下操作任意次数：

• 选择 相邻 元素对中 和最小 的一对。如果存在多个这样的对，选择最左边的一个。
• 用它们的和替换这对元素。

返回将数组变为 非递减 所需的 最小操作次数 。

如果一个数组中每个元素都大于或等于它前一个元素（如果存在的话），则称该数组为非递减。

示例 1：

示例 2：

提示：

• 1 <= nums.length <= 50
• -1000 <= nums[i] <= 1000

解法一

思路和算法

如果初始时数组 $\textit{nums}$ 已经非递减，则最小操作次数是 $0$。以下只考虑初始时数组 $\textit{nums}$ 不满足非递减的情况。

最直观的思路是模拟数组的操作。每次操作时，遍历数组 $\textit{nums}$ 寻找相邻元素对中的元素和最小且最左边的一个元素对，用元素和替换这对元素，直到数组变成非递减，此时的操作次数即为将数组变为非递减所需的最小操作次数。

用 $n$ 表示数组 $\textit{nums}$ 的长度。由于每次操作之后都会将数组中的元素个数减少 $1$，因此每次操作应将执行合并操作的元素对右侧的元素向左移动。对于 $0 \le k < n$ 的整数 $k$，在执行 $k$ 次操作之后，剩余元素个数是 $n - k$，因此下一次操作时应只考虑数组的前 $n - k$ 个元素。

代码

###Java

class Solution {
    public int minimumPairRemoval(int[] nums) {
        int removals = 0;
        int n = nums.length;
        while (!isNonDecreasing(nums, n)) {
            update(nums, n);
            removals++;
            n--;
        }
        return removals;
    }

    public void update(int[] nums, int n) {
        int minSum = Integer.MAX_VALUE;
        int index = -1;
        for (int i = 0; i < n - 1; i++) {
            if (nums[i] + nums[i + 1] < minSum) {
                minSum = nums[i] + nums[i + 1];
                index = i;
            }
        }
        if (index >= 0) {
            nums[index] = minSum;
            for (int i = index + 1; i < n - 1; i++) {
                nums[i] = nums[i + 1];
            }
        }
    }

    public boolean isNonDecreasing(int[] nums, int n) {
        for (int i = 1; i < n; i++) {
            if (nums[i - 1] > nums[i]) {
                return false;
            }
        }
        return true;
    }
}

###C#

public class Solution {
    public int MinimumPairRemoval(int[] nums) {
        int removals = 0;
        int n = nums.Length;
        while (!IsNonDecreasing(nums, n)) {
            Update(nums, n);
            removals++;
            n--;
        }
        return removals;
    }

    public void Update(int[] nums, int n) {
        int minSum = int.MaxValue;
        int index = -1;
        for (int i = 0; i < n - 1; i++) {
            if (nums[i] + nums[i + 1] < minSum) {
                minSum = nums[i] + nums[i + 1];
                index = i;
            }
        }
        if (index >= 0) {
            nums[index] = minSum;
            for (int i = index + 1; i < n - 1; i++) {
                nums[i] = nums[i + 1];
            }
        }
    }

    public bool IsNonDecreasing(int[] nums, int n) {
        for (int i = 1; i < n; i++) {
            if (nums[i - 1] > nums[i]) {
                return false;
            }
        }
        return true;
    }
}

复杂度分析

• 时间复杂度：$O(n^2)$，其中 $n$ 是数组 $\textit{nums}$ 的长度。最差情况需要执行 $n - 1$ 次操作，每次操作的时间是 $O(n)$，因此时间复杂度是 $O(n^2)$。

• 空间复杂度：$O(1)$。所有的操作均为原地修改数组。

解法二

思路和算法

使用双向链表、哈希表和优先队列，可以将时间复杂度降低到 $O(n \log n)$。具体见题解「3510. 移除最小数对使数组有序 II」。

代码

###Java

class Solution {
    private class Node {
        private int index;
        private long value;
        private Node prev;
        private Node next;

        public Node() {
            this(-1, Integer.MAX_VALUE);
        }

        public Node(int index, long value) {
            this.index = index;
            this.value = value;
            prev = null;
            next = null;
        }

        public int getIndex() {
            return index;
        }

        public long getValue() {
            return value;
        }

        public void setValue(long value) {
            this.value = value;
        }

        public Node getPrev() {
            return prev;
        }

        public void setPrev(Node prev) {
            this.prev = prev;
        }

        public Node getNext() {
            return next;
        }

        public void setNext(Node next) {
            this.next = next;
        }
    }

    public int minimumPairRemoval(int[] nums) {
        int removals = 0;
        Map<Integer, Node> indexToNode = new HashMap<Integer, Node>();
        Node pseudoHead = new Node();
        Node pseudoTail = new Node();
        Node prevNode = pseudoHead;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            Node node = new Node(i, nums[i]);
            indexToNode.put(i, node);
            prevNode.setNext(node);
            node.setPrev(prevNode);
            prevNode = node;
        }
        prevNode.setNext(pseudoTail);
        pseudoTail.setPrev(prevNode);
        PriorityQueue<long[]> pq = new PriorityQueue<long[]>((a, b) -> a[0] != b[0] ? Long.compare(a[0], b[0]) : Long.compare(a[1], b[1]));
        int reversePairs = 0;
        for (int i = 0; i < n - 1; i++) {
            pq.offer(new long[]{nums[i] + nums[i + 1], i, i + 1});
            if (nums[i] > nums[i + 1]) {
                reversePairs++;
            }
        }
        while (reversePairs > 0) {
            long[] arr = pq.poll();
            long newValue = arr[0];
            int index1 = (int) arr[1], index2 = (int) arr[2];
            if (!indexToNode.containsKey(index1) || !indexToNode.containsKey(index2) || newValue != indexToNode.get(index1).getValue() + indexToNode.get(index2).getValue()) {
                continue;
            }
            removals++;
            Node node1 = indexToNode.get(index1), node2 = indexToNode.get(index2);
            if (node1.getValue() > node2.getValue()) {
                reversePairs--;
            }
            if (node1.getPrev().getIndex() >= 0 && node1.getPrev().getValue() > node1.getValue()) {
                reversePairs--;
            }
            if (node2.getNext().getIndex() >= 0 && node2.getNext().getValue() < node2.getValue()) {
                reversePairs--;
            }
            node1.setValue(newValue);
            remove(node2);
            indexToNode.remove(index2);
            if (node1.getPrev().getIndex() >= 0) {
                pq.offer(new long[]{node1.getPrev().getValue() + node1.getValue(), node1.getPrev().getIndex(), node1.getIndex()});
                if (node1.getPrev().getValue() > node1.getValue()) {
                    reversePairs++;
                }
            }
            if (node1.getNext().getIndex() >= 0) {
                pq.offer(new long[]{node1.getValue() + node1.getNext().getValue(), node1.getIndex(), node1.getNext().getIndex()});
                if (node1.getNext().getValue() < node1.getValue()) {
                    reversePairs++;
                }
            }
        }
        return removals;
    }

    public void remove(Node node) {
        Node prev = node.getPrev(), next = node.getNext();
        prev.setNext(next);
        next.setPrev(prev);
    }
}

###C#

public class Solution {
    public class Node {
        public int Index { get; set; }
        public long Value { get; set; }
        public Node Prev { get; set; }
        public Node Next { get; set; }

        public Node() : this(-1, int.MaxValue) {

        }

        public Node(int index, long value) {
            Index = index;
            Value = value;
            Prev = null;
            Next = null;
        }
    }

    public int MinimumPairRemoval(int[] nums) {
        int removals = 0;
        IDictionary<int, Node> indexToNode = new Dictionary<int, Node>();
        Node pseudoHead = new Node();
        Node pseudoTail = new Node();
        Node prevNode = pseudoHead;
        int n = nums.Length;
        for (int i = 0; i < n; i++) {
            Node node = new Node(i, nums[i]);
            indexToNode.Add(i, node);
            prevNode.Next = node;
            node.Prev = prevNode;
            prevNode = node;
        }
        prevNode.Next = pseudoTail;
        pseudoTail.Prev = prevNode;
        Comparer<Tuple<long, int, int>> comparer = Comparer<Tuple<long, int, int>>.Create((a, b) => a.Item1 != b.Item1 ? a.Item1.CompareTo(b.Item1) : a.Item2.CompareTo(b.Item2));
        PriorityQueue<Tuple<long, int, int>, Tuple<long, int, int>> pq = new PriorityQueue<Tuple<long, int, int>, Tuple<long, int, int>>(comparer);
        int reversePairs = 0;
        for (int i = 0; i < n - 1; i++) {
            pq.Enqueue(new Tuple<long, int, int>(nums[i] + nums[i + 1], i, i + 1), new Tuple<long, int, int>(nums[i] + nums[i + 1], i, i + 1));
            if (nums[i] > nums[i + 1]) {
                reversePairs++;
            }
        }
        while (reversePairs > 0) {
            Tuple<long, int, int> tuple = pq.Dequeue();
            long newValue = tuple.Item1;
            int index1 = tuple.Item2, index2 = tuple.Item3;
            if (!indexToNode.ContainsKey(index1) || !indexToNode.ContainsKey(index2) || newValue != indexToNode[index1].Value + indexToNode[index2].Value) {
                continue;
            }
            removals++;
            Node node1 = indexToNode[index1], node2 = indexToNode[index2];
            if (node1.Value > node2.Value) {
                reversePairs--;
            }
            if (node1.Prev.Index >= 0 && node1.Prev.Value > node1.Value) {
                reversePairs--;
            }
            if (node2.Next.Index >= 0 && node2.Next.Value < node2.Value) {
                reversePairs--;
            }
            node1.Value = newValue;
            Remove(node2);
            indexToNode.Remove(index2);
            if (node1.Prev.Index >= 0) {
                pq.Enqueue(new Tuple<long, int, int>(node1.Prev.Value + node1.Value, node1.Prev.Index, node1.Index), new Tuple<long, int, int>(node1.Prev.Value + node1.Value, node1.Prev.Index, node1.Index));
                if (node1.Prev.Value > node1.Value) {
                    reversePairs++;
                }
            }
            if (node1.Next.Index >= 0) {
                pq.Enqueue(new Tuple<long, int, int>(node1.Value + node1.Next.Value, node1.Index, node1.Next.Index), new Tuple<long, int, int>(node1.Value + node1.Next.Value, node1.Index, node1.Next.Index));
                if (node1.Next.Value < node1.Value) {
                    reversePairs++;
                }
            }
        }
        return removals;
    }

    public void Remove(Node node) {
        Node prev = node.Prev, next = node.Next;
        prev.Next = next;
        next.Prev = prev;
    }
}

复杂度分析

• 时间复杂度：$O(n \log n)$，其中 $n$ 是数组 $\textit{nums}$ 的长度。遍历数组初始化数据结构的时间是 $O(n \log n)$，最差情况需要执行 $n - 1$ 次操作，每次操作中的双向链表和哈希表的更新时间是 $O(1)$，优先队列的更新时间是 $O(\log n)$，因此时间复杂度是 $O(n \log n)$。

• 空间复杂度：$O(n)$，其中 $n$ 是数组 $\textit{nums}$ 的长度。双向链表、哈希表和优先队列的空间是 $O(n)$。

本题和 3510. 移除最小数对使数组有序 II 是一样的，请看 我的题解。

大部分前端应该都或多或少地使用过 TypeScript 开发，但是此文将带你探索少有人了解的 TS 领域：模板字符串类型。

这样的类型操作你见过吗？

type World = 'World'
type Greeting = `Hello ${World}` // "Hello World"

type UserName = 'cookie'
type UserNameCapitalize = Capitalize<UserName> // "Cookie"

type ButtonVariant = `btn-${'primary' | 'secondary'}-${'sm' | 'lg'}`
// "btn-primary-sm" | "btn-primary-lg" | "btn-secondary-sm" | "btn-secondary-lg"

看起来不可思议，但是这些都是 TypeScript 模板字符串类型的能力。

模板字符串类型（Template Literal Types） 是 TypeScript 4.1 引入的高级特性。它建立在字符串字面量类型的基础上，允许你通过类似 JavaScript 模板字符串的语法，动态地组合、操作和生成新的字符串类型。

接下来，我将从字符串字面量类型开始，逐步讲解到模板字符串类型的初级到高级的用法。

一、基础：什么是字符串字面量类型？

1. 定义

字符串字面量类型是指将一个具体的字符串值作为一种类型。

// 普通的 string 类型
let s1: string = 'hello'
s1 = 'world' // 正确

// 字符串字面量类型
let s2: 'hello' = 'hello'
s2 = 'world' // 报错：不能将类型"world"分配给类型"hello"

2. 联合类型 (Union Types)

字符串字面量类型最常见的用法是配合联合类型使用，限制变量只能是某几个特定字符串之一。

type HttpMethod = 'GET' | 'POST' | 'PUT' | 'DELETE' | 'PATCH'
function request(method: HttpMethod, url: string) {
  // ...
}
request('GET', url) // 正确
request('LET', url) // 报错：类型"LET"的参数不能赋给类型"HttpMethod"的参数。

二、进阶：模板字符串类型

1. 基础拼接

就像 JavaScript 中的模板字符串 ${var} 一样，TypeScript 类型也可以通过反引号 `` 和 ${} 配合实现字符串类型的插值。

// 字符串拼接
type World = 'World'
type Greeting = `Hello ${World}` // 类型 "Hello World"

// 多个插值
type Protocol = 'https'
type Domain = 'example.com'
type URL = `${Protocol}://${Domain}` // 类型 "https://example.com"

// 与其他类型结合
type Version = 1 | 2 | 3
type APIVersion = `v${Version}` // "v1" | "v2" | "v3"

在这里提醒一下大家，一定不要把类型和值搞混，这里操作的是类型，不要把它当做值去操作。一些错误示例：

console.log(World) // 报错："World"仅表示类型，但在此处却作为值使用。
type Greeting = "Hello" + World // 报错："World"仅表示类型，但在此处却作为值使用。

2. 联合类型的自动分发（笛卡尔积）

在模板字符串中，把多个联合类型组合在一起时，TypeScript 会自动生成所有可能的组合，也就是按笛卡尔积（Cartesian Product）组合。

type Space = 'sm' | 'md' | 'lg'
type Side = 't' | 'b' | 'l' | 'r'
type PaddingClass = `p-${Side}-${Space}`
// "p-t-sm" | "p-t-md" | "p-t-lg" | "p-b-sm" | "p-b-md" | "p-b-lg" | "p-l-sm" | "p-l-md" | "p-l-lg" | "p-r-sm" | "p-r-md" | "p-r-lg"

// 实际使用
function addPadding(el: HTMLElement, className: PaddingClass) {
  el.classList.add(className)
}
const div = document.createElement('div')
addPadding(div, 'p-t-sm') // 正确
addPadding(div, 'p-x-xx') // 类型错误

性能提示：当联合类型的成员数量较多时，组合后的类型数量会呈指数级增长（例如 3 个联合类型各有 10 个成员，组合后会有 1000 种可能），这可能会导致 TypeScript 编译器性能下降或类型检查变慢。

3. 内置工具类型

为了性能和方便，TypeScript 编译器内置了四个特殊的工具类型。它们不是通过 TS 代码实现的，而是直接由编译器处理。

• Uppercase<S> 将字符串中的每个字符转换为大写
• Lowercase<S> 将字符串中的每个字符转换为小写
• Capitalize<S> 将字符串的第一个字符转换为大写
• Uncapitalize<S> 将字符串的第一个字符转换为小写

下面是使用示例：

// Uppercase：全部转大写
type Color = 'red'
type UpperColor = Uppercase<Color> // "RED"

// Lowercase：全部转小写
type MixedCase = 'TypeScript'
type LowerCase = Lowercase<MixedCase> // "typescript"

// Capitalize：首字母大写
type Name = 'cookie'
type CapName = Capitalize<Name> // "Cookie"

// Uncapitalize：首字母小写
type Components = 'Button' | 'Input' | 'Modal'
type UncapComponents = Uncapitalize<Components> // "button" | "input" | "modal"

结合模板字符串使用：

// 生成事件处理器名称
type Events = 'click' | 'change' | 'input'
type EventHandlers = `on${Capitalize<Events>}`
// "onClick" | "onChange" | "onInput"

// 生成 CSS 类名
type Size = 'sm' | 'MD' | 'Lg'
type SizeClass = `size-${Lowercase<Size>}`
// "size-sm" | "size-md" | "size-lg"

三、 高阶：模式匹配与 infer

掌握了基础的模板字符串拼接后，接下来我们进入更强大的领域——模式匹配。要在类型中解析字符串（例如提取参数、去掉空格），我们需要结合 extends 和 infer。

1. 什么是 infer ？

infer 属于 TS 的高阶用法，它需要配合条件语句一起使用：

A extends B ? C : D

含义是：如果类型 A 可以赋值给类型 B，则结果为 C，否则为 D。

而 infer 的作用是在条件类型的 extends 子句（也就是 B 语句）中 声明一个待推断的类型变量。可以把它理解为"占位符"，让 TypeScript 帮你从某个复杂类型中"提取"出一部分。当类型匹配成功时，infer 声明的类型变量会被推断为匹配到的具体类型。

举一些实用的例子：

// 获取 Promise 返回值的类型
type UnpackPromise<T> = T extends Promise<infer R> ? R : T
type P1 = UnpackPromise<Promise<string>> // string

// 获取数组中元素类型
type GetArrayType<T> = T extends (infer U)[] ? U : never
type A1 = GetArrayType<number[]> // number

// 获取函数的返回值类型
type GetReturnType<T> = T extends (...args: any[]) => infer R ? R : never
type R1 = GetReturnType<() => boolean> // boolean

2. 在模板字符串类型中使用 infer

在模板字符串中 infer 的使用方法同上，也需要配合条件语句，区别是我们需要通过 ${infer T} 把它插入到模板字符串类型中，通过模式匹配来提取字符串的特定部分。

比如提取出字符串类型空格后面的部分。

type GetSurname<S> = S extends `${infer First} ${infer Last}` ? Last : never

type T1 = GetSurname<'Hello Cookie'> // "Cookie"
type T2 = GetSurname<'Cookie'> // never (因为没有空格，匹配失败)

3. 贪婪与非贪婪匹配

多个 infer 连用，TypeScript 使用 “非贪婪” 匹配策略，也就是会遵循 “从左到右，尽可能匹配最小单位” 的原则。

比如，当使用 ${infer A}${infer B} 时：

• A（第一个 infer）：匹配第一个字符（最短匹配）
• B（第二个 infer）：匹配剩余所有字符（由于 A 已经匹配了第一个字符，B 必须匹配剩余的全部内容）

举例说明：

// 三个连续的 infer 会依次匹配：A 匹配第一个字符，B 匹配第二个字符，C 匹配剩余所有字符
type Split<S> = S extends `${infer A}${infer B}${infer C}` ? [A, B, C] : []
type Res = Split<'Hello'> // ["H", "e", "llo"]

// 有占位符的情况，也只会匹配到第一个
type GetExt<S> = S extends `${infer Name}.${infer Ext}` ? Ext : never
type E2 = GetExt<'ts.config.json'> 
// "config.json"（Name 匹配到第一个点之前，Ext 获取之后的所有内容）

4. infer 与联合类型联动

当模式中包含联合类型时，TypeScript 会尝试匹配联合类型中的任意一个成员：

// 提取指定几种扩展类型的文件名
type ImageExt = 'jpg' | 'png' | 'gif' | 'webp'
type ExtractRawName<FileName> = FileName extends `${infer Name}.${ImageExt}`
  ? Name
  : never

type E1 = ExtractRawName<'photo.jpg'> // "photo"
type E2 = ExtractRawName<'logo.png'> // "logo"
type E3 = ExtractRawName<'document.pdf'> // never (pdf 不在 ImageExt 联合类型中)

TypeScript 会对联合类型中的每一个成员分别执行 infer 逻辑，最后再把结果重新组合成一个新的联合类型，在模板字符串中也一样。

type IconNames = 'icon-home' | 'icon-user' | 'icon-settings' | 'logo-main'

// 提取所有以 "icon-" 开头的图标名称
type ExtractIcon<T> = T extends `icon-${infer Name}` ? Name : never

type PureNames = ExtractIcon<IconNames>
// 结果: "home" | "user" | "settings"
// 注意: "logo-main" 匹配失败，返回 never，在联合类型中 never 会被自动过滤掉

5. 递归类型 (Recursive Types)

在上一节的基础上，我们再结合递归，可以更加灵活的处理字符串，接下来以 TrimLeft 举例：

目标：去除字符串左边的空格。

type Space = ' ' | '\n' | '\t' // 联合类型 包含三种空白字符

// 如果第一个字符是空白字符，就取除了第一个空白字符的剩余字符串，然后递归处理
// 否则直接取整个字符
type TrimLeft<S extends string> = S extends `${Space}${infer R}`
  ? TrimLeft<R> // 递归调用
  : S // 终止

type T = TrimLeft<'  cookie'> // "cookie"

如果你在纠结为什么不是 \s 而是 ' '？这是因为 TypeScript 的模板字符串类型不支持正则表达式语法。这里的 ' '、'\n'、'\t' 都是具体的字符串字面量类型，而 \s 是正则表达式的特殊语法，在类型系统中没有意义。

四、 映射类型与模板字符串的结合

TypeScript 4.1 不仅引入了模板字符串类型，还支持在映射类型中使用 as 重命名键名。

1. as 语法

type MappedType<T> = {
  [K in keyof T as NewKeyType<K>]: T[K]
}

在之前《面试官：请实现 TS 中的 Pick 和 Omit》一文中，在 Omit 的实现中就用到了 as 来剔除一些类型：

type MyOmit<T, K> = {
  [P in keyof T as P extends K ? never : P]: T[P];
};

type Todo = {
  title: string
  description: string
  completed: boolean
}
type TodoWithoutDescription = MyOmit<Todo, 'description'>
/*
type TodoWithoutDescription = {
  title: string
  completed: boolean
}
*/

2. 在模板字符串中使用

示例 1：添加前缀/后缀

type AddPrefix<T, Prefix extends string> = {
  [K in keyof T as `${Prefix}${string & K}`]: T[K]
}

interface User {
  name: string
  age: number
}

type PrefixedUser = AddPrefix<User, 'user_'>
// { user_name: string; user_age: number }

为什么要 string & K？

因为 K 的类型是 keyof T，可能是 string | number | symbol。用交叉类型 & 将其约束为 string。

示例 2：生成 Getter/Setter

type Getters<T> = {
  [K in keyof T as `get${Capitalize<string & K>}`]: () => T[K]
}

type Setters<T> = {
  [K in keyof T as `set${Capitalize<string & K>}`]: (val: T[K]) => void
}

interface State {
  count: number
  name: string
}

type StateGetters = Getters<State>
// { getCount: () => number; getName: () => string }

type StateSetters = Setters<State>
// { setCount: (val: number) => void; setName: (val: string) => void }

示例 3：移除特定前缀

type RemovePrefix<T, Prefix extends string> = {
  [K in keyof T as K extends `${Prefix}${infer Rest}` ? Rest : K]: T[K]
}

interface ApiResponse {
  api_name: string
  api_token: string
  userId: number
}

type CleanResponse = RemovePrefix<ApiResponse, 'api_'>
// { name: string; token: string; userId: number }

// 注意：传入空字符串作为前缀时，由于空字符串会匹配所有键名，但实际上不会移除任何内容
type CleanResponse1 = RemovePrefix<ApiResponse, ''>
// { api_name: string; api_token: string; userId: number }

五、 总结

写这篇文章因为我在刷 TypeScript 类型体操 时，遇到了第一个模板字符串类型的题目 TrimLeft 搜了半天没有发现现成的文章，干脆自己写一个。

如果你也对 TypeScript 类型体操感兴趣，欢迎一起来刷！💪🏻💪🏻💪🏻

实时渲染

2. 图形渲染管线

2.3 几何处理

GPU上的几何处理阶段负责大多数每个三角形和每个顶点的操作。该阶段进一步分为以下功能阶段：顶点着色、投影、裁剪和屏幕映射（如图2.3）。

2.3.1 顶点着色

顶点着色有两个主要任务，即计算顶点的位置和评估程序员可能喜欢的顶点输出数据，例如法线坐标和纹理坐标。传统上，对象的大部分阴影是通过将灯光应用到每个顶点的位置和法线并仅将结果颜色存储在顶点来计算的。然后将这些颜色插入整个三角形。出于这个原因，这个可编程的顶点处理单元被命名为顶点着色器[1049]。随着现代GPU的出现，以及每个像素发生的部分或全部着色，这个顶点着色阶段更加通用，并且可能根本不会求取任何着色方程的值，其工作主要取决于程序员的意图。顶点着色器现在是一个更通用的单元，专门用于设置与每个顶点关联的数据。例如，顶点着色器可以使用第4.4节和第4.5节中的方法为对象设置动画。

我们首先描述如何计算顶点位置，一组始终需要的坐标。在被屏幕显示的过程中，模型被转换成几个不同的空间或坐标系。最初，模型驻留在自己的模型空间中，这仅意味着它根本没有被转换。每个模型都可以与模型变换相关联，以便可以对其进行定位和定向。可以将多个模型转换与单个模型相关联。这允许同一模型的多个副本（称为实例）在同一场景中具有不同的位置、方向和大小，而无需复制基本几何体。

模型变换所变换的是模型的顶点和法线。对象的坐标称为模型坐标，在对这些坐标应用模型变换后，模型被称为位于世界坐标或世界空间中。世界空间是唯一的，模型经过各自的模型变换后，所有的模型都存在于同一个空间中。

如前所述，模型只有被相机（或观察者）看到才能渲染。相机在世界空间中有一个位置和一个方向，用于放置和瞄准相机。为了便于投影和剪辑，相机和所有模型都使用视图变换进行了变换。视图变换的目的是将相机放置在原点并瞄准它，使其看向负z轴的方向，y轴指向上方，x轴指向右侧。我们使用-z轴约定；一些文章也会使用向下看+z轴的约定。区别主要是语义上的，因为一个和另一个之间的转换很简单。应用视图变换后的实际位置和方向取决于底层应用程序编程接口 (API)。如此划定的空间称为相机空间，或更常见的是，视图空间或眼睛空间。视图变换影响相机和模型的方式示例如图2.4所示。模型变换和视图变换都可以用4×4矩阵来实现，这是第4章的主题。但是，重要的是要意识到可以以程序员喜欢的任何方式计算顶点的位置和法线。

接下来，我们将描述顶点着色的第二种类型的输出。要生成逼真的场景，仅渲染对象的形状和位置是不够的，还必须对它们的外观进行建模。该描述包括每个物体的材质，以及任何光源照射在物体上的效果。材料和灯光可以通过多种方式建模，从简单的颜色到物理描述的精细表示。

这种确定光对材料效果的操作称为着色。它涉及计算对象上不同点的着色方程。通常，其中一些计算在模型顶点的几何处理期间执行，而其他计算可能在逐像素处理期间执行。各种材质数据可以存储在每个顶点，例如点的位置、法线、颜色或求取着色方程值所需的任何其他数字信息。然后，顶点着色结果（可以是颜色、矢量、纹理坐标以及任何其他类型的着色数据）被发送到光栅化和像素处理阶段进行插值并用于计算表面的着色。

GPU顶点着色器形式的顶点着色在本书中进行了更深入的讨论，尤其是在第3章和第5章中。

作为顶点着色的一部分，渲染系统先进行投影，然后进行裁剪，将视图体换为单位立方体，其极值点位于$(-1,-1,-1)$(−1,−1,−1) 和$(1,1,1)$(1,1,1)之间。可以使用不同的范围来定义相同的体积，例如，$(0 ≤ z ≤ 1)$(0≤z≤1)。单位立方体称为正规化视图体。投影是在GPU上由顶点着色器首先完成的。常用的投影方法有两种，即正射投影（也称平行投影）和透视投影，如图2.5。事实上，正射投影只是一种平行投影。也可以使用其他几种投影方式（特别是在建筑领域），例如斜投影和轴测投影。老式街机游戏Zaxxon就是以后者命名的。

请注意，投影表示为矩阵（第4.7节），因此它有时可能与几何变换的其余部分连接。

正交观察的视图体通常是一个矩形框，正交投影将这个视图体变换为单位立方体。正交投影的主要特点是平行线在变换后保持平行。这种转换是平移和缩放的组合。

透视投影有点复杂。在这种类型的投影中，物体离相机越远，投影后看起来越小。另外，平行线可能会聚在地平线上。因此，透视变换模仿了我们感知物体大小的方式。在几何上，称为截头锥体的视图体是一个具有矩形底面的截棱锥。截头锥体也转化为单位立方体。正交变换和透视变换都可以用4×4矩阵构造（第4章），并且在任一变换之后，模型都被称为在裁剪坐标中。这些实际上是齐次坐标，在第4章中讨论过，因此这发生在除以w之前。GPU的顶点着色器必须始终输出这种类型的坐标，以便下一个功能阶段（裁剪）正常工作。

尽管这些矩阵将一个几何体转换为另一个几何体，但它们被称为投影，因为在显示之后，z坐标不存储在生成的图像中，而是存储在z缓冲区中，如第2.5节所述。通过这种方式，模型从三维投影到两维。

2.3.2 可选的顶点处理

每个管线都有刚刚描述的顶点处理。完成此处理后，可以在GPU上进行几个可选阶段，按顺序是：曲面细分、几何着色和流输出。它们的使用取决于硬件的能力——并非所有 GPU 都有它们——以及程序员的愿望。它们相互独立，一般不常用。 将在第3章中详细介绍每一个。

第一个可选阶段是曲面细分。假设你有一个弹跳球对象。如果用一组三角形表示它，则可能会遇到质量或性能问题。您的球在5米外可能看起来不错，但近距离观察单个三角形，三角形的轮廓，就会变得清晰可见。如果你用更多的三角形制作球来提高质量，当球很远并且只覆盖屏幕上的几个像素时，你可能会浪费大量的处理时间和内存。通过曲面细分，可以使用适当数量的三角形生成曲面。

我们已经讨论了一些三角形，但在管线中的这一点上，我们只处理了顶点。这些可用于表示点、线、三角形或其他对象。顶点可用于描述曲面，例如球。这样的表面可以由一组面片指定，每个面片由一组顶点组成。曲面细分阶段由一系列阶段本身组成——外包着色器(hull shader)、曲面细分器(tessellator)和域着色器(domain shader)——将这些面片顶点集转换为（通常）更大的顶点集，然后用于制作新的三角形集。场景的相机可用于确定生成了多少个三角形：面片很近时很多，远处时很少。

下一个可选阶段是几何着色器。该着色器早于曲面细分着色器，因此在GPU上更常见。它类似于曲面细分着色器，因为它接受各种类型的图元并可以生成新的顶点。这是一个更简单的阶段，因为此创建的范围有限，输出图元的类型也更有限。几何着色器有多种用途，其中最流行的一种是粒子生成。想象一下模拟烟花爆炸。每个火球都可以用一个点来表示，一个顶点。几何着色器可以将每个点变成面向观察者并覆盖多个像素的正方形（由两个三角形组成），从而为我们提供更令人信服的图元进行着色。

最后一个可选阶段称为流输出。这个阶段让我们使用GPU作为几何引擎。与将我们处理过的顶点沿着管道的其余部分发送到屏幕上不同，此时我们可以选择将这些顶点输出到数组中以供进一步处理。这些数据可以由CPU或GPU本身在以后的过程中使用。此阶段通常用于粒子模拟，例如我们的烟花示例。

这三个阶段按此顺序执行——曲面细分、几何着色和流输出——每个阶段都是可选的。无论使用哪个（如果有）选项，如果我们继续沿着管道向下走，我们就会得到一组具有齐次坐标的顶点，这些顶点将被检查相机是否能看到它们。

2.3.3 裁剪

只有全部或部分在视图体内部的图元需要传递到光栅化阶段（以及随后的像素处理阶段），然后在屏幕上绘制它们。完全位于视图体内部的图元将按原样传递到下一个阶段。完全在视图体积之外的基元不会被进一步传递，因为它们没有被渲染。部分位于视图体内部的图元需要裁剪。例如，一条直线，在视图体外部有一个顶点，在视图体积内部有一个顶点，此时应该根据视图体对其进行裁剪；以便外部的顶点被位于该线和视图体之间的交点处的新顶点替换。投影矩阵的使用意味着变换后的图元被裁剪到单位立方体上。在裁剪之前进行视图变换和投影的好处是可以使裁剪问题保持一致；图元总是针对单位立方体进行裁剪。

裁剪过程如图2.6所示。除了视图体积的六个剪裁平面之外，用户还可以定义额外的剪裁平面来明显地剪裁对象。第818页的图19.1中显示了显示这种可视化类型的图像，称为剖视(sectioning)。

裁剪步骤使用投影产生的4值齐次坐标进行裁剪。值通常不会跨透视空间中的三角形进行线性插值。需要第四个坐标，以便在使用透视投影时正确插入和裁剪数据。最后，执行透视除法，将生成的三角形的位置放入三维标准化设备坐标中。如前所述，此视图体积范围从$(-1,-1,-1)$(−1,−1,−1)到$(1,1,1)$(1,1,1)。几何阶段的最后一步是从这个空间转换到窗口坐标。

2.3.4 屏幕映射

只有视图体内部的（裁剪的）图元被传递到屏幕映射阶段，进入这个阶段时坐标仍然是三维的。每个图元的x和y坐标被转换为屏幕坐标。屏幕坐标与z坐标一起也称为窗口坐标。假设场景应该被渲染到一个最小位置在$(x_1,y_1)$(x1,y1)，最大位置在$(x_2 ,y_2)$(x2,y2)处的窗口（其中$x_1 < x_2$x1<x2和$y_1 < y_2$y1<y2）。屏幕映射先是平移，然后是缩放操作。新的x和y坐标称为屏幕坐标。z坐标（OpenGL的$[−1,+1]$[−1,+1]和DirectX的$[0,1]$[0,1]）也被映射到$[z_1,z_2]$[z1,z2]，其中$z_1=0$z1=0和$z_2=1$z2=1作为默认值。但是，这些可以通过API进行更改。窗口坐标连同这个重新映射的z值被传递到光栅化阶段。屏幕映射过程如图2.7所示。

接下来，我们描述整数和浮点值如何与像素（和纹理坐标）相关。给定像素的水平数组并使用笛卡尔坐标，最左边像素的左边缘在浮点坐标中为0.0。OpenGL一直使用这种方案，DirectX10及其后续版本也使用它。该像素的中心为0.5。因此，一系列像素 [0,9] 覆盖了 [0.0,10.0) 的跨度。转换很简单：

其中$d$d是像素的离散（整数）索引，$c$c是像素内的连续（浮点）值。

虽然所有API的像素位置值都从左到右增加，但在OpenGL和DirectX¹之间的某些情况下，顶部和底部边缘的零位置不一致。OpenGL始终偏爱笛卡尔系统，将左下角视为最低值元素，而DirectX有时根据上下文将左上角定义为该元素。每个人都有一个逻辑，在他们不同的地方不存在正确的答案。例如，$(0,0)$(0,0)在 OpenGL中位于图像的左下角，而在DirectX中位于左上角。在从一个API迁移到另一个API时，必须考虑到这种差异。

Footnotes

1. “Direct3D”是DirectX的三维图形API组件。DirectX包括其他API元素，例如输入和音频控件。我们不区分在指定特定版本时编写“DirectX”和在讨论此特定API时编写“Direct3D”，而是通过始终编写“DirectX”来遵循常见用法。 ↩