前言

在这个课程里，我会跟大家说一下我2023年去滴滴应聘时，遇到的几个比较经典的面试题。

我当时应聘的岗位就是前端可视化，而滴滴也正好需要一个懂图形学的前端，因此他给我出的面试题也是跟图形学相关的。

滴滴我在1面过了后，就发给我3道图形学相关的笔试题，让我在3天内写完。

写完后，我需要把代码发给滴滴的HR，然后在2面的时候讲给面试官听。

这3道面试题我觉得挺不错的，所以事后就将其做成了课程，希望大家也可以更加顺利的找到自己喜欢的工作。

课程重点

这个课程的重点其实并不是canvas，而是图形学。

当你的图形学扎实了，无论你学习canvas，还是WebGL、WebGPU等，都会事半功倍。

我在滴滴的工作中，就用到了很多技术栈，比如canvas、js端OpenCV、Mapbox、WebGL、three.js 等，与此同时，还需要看懂后端的c++、c++端OpenCV、OpenGL等。

前后端的语言各不相同，唯有图形学算法和原理是不变的。

滴滴在出面试题的时候，其实并不要求你用什么语言实现，他在乎的是其中的图形学算法。

课前准备学习目标知识点1-题目内容1-1-绘制多角星

多角星就是有多个角的星形，比如五角星。

1-2-绘制球体与多边形的碰撞反弹路径

球体会朝某一方向运动，碰到墙体时会反弹，碰到障碍物时会停止运动。请画出球体的运动路径。

AABB和BVH优化策略：

1-3-制作b站弹幕效果

1-4-寻路

寻路算法是我最后要附赠给大家的一道题，它是我1面时的面试官问我的，他让我口述一下寻路算法。

我当时就把自己比较熟悉的dikjstra寻路和heuristic寻路跟他滔滔不绝的讲了一遍。

他说挺好的，这道题主要是考察一下面试者的知识积累。

在我实际的面试经历中，寻路是我遇到的比较多的，尤其是做智能驾驶的公司，考的概率会很大，所以我有所准备。

2-热身

在做题之前，我们先做个热身，说一下我自己搭建的canvas渲染引擎，之后做题时会用到。

2-1-canvas渲染引擎简介

这个canvas渲染引擎是在《canvas进阶-矩阵变换》课里的canvas渲染引擎的基础上改进的，算是其2.0版本了

其结构比较简单：

Scene 是场景对象，它是所有图形展示自我的舞台。

Scene对象有children和camera 两个属性。

children 是Scene里所有要展示自我的图形的集合。

camera 是给图形拍照，可以位移和缩放视口，从而给某个图形一个特写，或者给所有图形来个合照。

所有要渲染的图形都继承自Graph2D 对象，它有控点位的Geometry 属性和控样式的Style 属性。

玩过three.js 同学应该就会想到，他们就是Mesh、Geometry和Material的关系。

对，我这引擎就是照着three.js写的，我有点想叫它three2d.js。

我们举几个例子说以其基本用法。

2-2-绘图

我当前的课程项目是用vue3.0+vite+ts 搭建的，大家可以下载我的源码，然后yarn 安装依赖，vite 运行即可。

我不同的示例，都有不同的.vue 文件，这些文件都有相应的路由和导航，以便点击查看。

路由和导航的配置我就不说了，大家可以看源码。

1.建立一个Graph2D.vue文件，用来写canvas渲染引擎的测试案例。

<script setup lang="ts">
import { ref, onMounted } from 'vue'
import { Scene } from '../lmm/core/Scene'
import { StandStyle } from '../lmm/style/StandStyle'
import { Graph2D } from '../lmm/objects/Graph2D'
import { CircleGeometry } from '../lmm/geometry/CircleGeometry'
import { RectGeometry } from '../lmm/geometry/RectGeometry'
import { PolyGeometry } from '../lmm/geometry/PolyGeometry'
import { TextGraph2D } from '../lmm/objects/TextGraph2D'
import { TextStyle } from '../lmm/style/TextStyle'
import { Vector2 } from '../lmm/math/Vector2'
import { ImageGraph2D } from '../lmm/objects/ImageGraph2D'
// 获取父级属性
defineProps({
    size: { type: Object, default: { width: 0, height: 0 } },
})
// 对应canvas 画布的Ref对象
const canvasRef = ref<HTMLCanvasElement>()
onMounted(() => {
    const canvas = canvasRef.value
})
script>
<template>
    <canvas
        ref="canvasRef"
        :width="size.width"
        :height="size.height"
    >canvas>
template>
<style scoped>style>

在上面的代码中，我们建立了一个canvas画布，并在onMounted 生命周期中通过Ref 对象拿到了这张画布。

画布的尺寸是从其父组件App.vue 中拿到的，大家可以自己结合源码来看。

2.实例化一个场景。

/* 场景 */
const scene = new Scene()
onMounted(() => {
    const canvas = canvasRef.value
    if (canvas) {
        scene.setOption({ canvas })
        scene.render()
    }
})

scene.setOption({ canvas }) 确定了要在哪个canvas上搭建舞台。

scene.render() 是渲染方法。

3.用Graph2D对象绘制一个三角形。

/* 多边形 */
const polyGeometry = new PolyGeometry([0, -300, 100, -250, -100, -250]).close()
const polyStyle = new StandStyle({
    strokeStyle: '#fff',
    fillStyle: '#00acec',
    lineWidth: 6,
    lineDash: [6],
})
const polyObj = new Graph2D(polyGeometry, polyStyle)
scene.add(polyObj)

效果如下：

PolyGeometry 是多边形Geometry，在其构造参数中可以写入多个点位，其点位是平展开的x,y位置。

PolyGeometry对象的.close() 方法可以闭合多边形路径。

StandStyle 是标准样式，其样式都是按照canvas API 定义的。

Graph2D 可以将图形和样式合二为一，形成一个有形有色的图形对象。

我们可以把不同的Geometry 图形交给Graph2D，比如圆、矩形、多角星等。

4.圆形

CircleGeometry对象继承自polyGeometry，所以它是可以分段的。

const circleGeometry = new CircleGeometry(50, 8)
const circleStyle = new StandStyle({
    fillStyle: '#00acec',
})
const circleObj = new Graph2D(circleGeometry, circleStyle)
circleObj.position.set(0, -200)
scene.add(circleObj)

效果如下：

上例是一个半径50，分段为8的圆。

CircleGeometry 对象的构造函数有2种参数结构：

Graph2D对象可以通过position、rotate、scale 设置其本地模型矩阵。

5.矩形

RectGeometry对象继承自polyGeometry。

const rectObj = new Graph2D(
    new RectGeometry(0,0,200, 50),
    new StandStyle({ fillStyle: '#00acec' })
)
rectObj.position.set(-100, -150)
scene.add(rectObj)

效果如下：

除了路径图形，我还封装了文字和图像对象。

RectGeometry 对象的构造函数有多种参数结构：

constructor(offset?:Vector2,size?:Vector2,counterclockwise?:boolean)

6.文字

TextGraph2D 是继承自Graph2D的文本对象，其文字是用canvas 内置的文本方法画的。

const textStyle=new TextStyle({
  fontSize:50,
  textAlign:'center',
  textBaseline:'middle',
  fillStyle:'#00acec'
})
const textObj=new TextGraph2D('Sphinx',new Vector2(0,-30),textStyle )
textObj.position.set(0,-20)
textObj.rotate=0.1
scene.add(textObj)

效果如下：

TextGraph2D 对象的构造函数有多种参数结构：

7.图像

ImageGraph2D 是继承自Graph2D的图像对象，其图像是用canvas 内置的drawImage()画的。

/* 图像 */
const image = new Image()
image.src =
    'https://yxyy-pandora.oss-cn-beijing.aliyuncs.com/stamp-images/1.png'
let imageObj:ImageGraph2D=new ImageGraph2D(image)
scene.add(imageObj)
image.onload=function(){
  imageObj.style.setOption({
    fillStyle:'rgba(0,172,236,0.1)',
    strokeStyle:'#00acec',
    order:['image','fill','stroke'],
    shadowColor: 'rgba(0,0,0,0.5)',
    shadowBlur: 5,
    shadowOffsetY: 20,
  })
  imageObj.size.set(image.width/2,image.height/2)
  imageObj.offset.copy(imageObj.size.clone().multiplyScalar(-0.5))
  imageObj.scale.set(0.4)
  imageObj.position.set(0,90)
  imageObj.update()
  scene.render()
}

效果如下：

StandStyle 中的order 属性是图像、描边和填充的渲染顺序。

当前案例的渲染顺序是先渲染图案，然后渲染填充色，最后渲染描边。

若你没有给填充色或描边色，或者没有在order 中给出相应的顺序，那相应的样式就不会被渲染。

ImageGraph2D 的构造函数有多种参数结构：

ImageGraph2D 的构造参数除了样式，其余的都来自于canvas 原生的绘制图像方法drawImage()

2-3-图形选择

我在选择图形的时候，用的是canvas 的内置方法isPointIn()。

不过，isPointIn()方法只适用于路径图形，无法选择图像和文字。

所以我提前在ImageGraph2D 和TextGraph2D 中做了封装，给了它们一个包围盒。

这种包围盒对于ImageGraph2D 还好，因为图像就是矩形的，包围盒即使图像的边界。

但对于文字而言，它就无法做出精确选择。因为文字只能通过文字的包围盒做选择，而无法精确到文字实体。

这种选择方式对于一般的需求是够用的，若一定要选择文字实体，可参考three.js将文字转顶点的方法，不过这样的话消耗就会非常大。

接下来我们对之前画的图形做一下选择。

1.给canvas 画布添加一个鼠标移动事件。

    ref="canvasRef"
        :width="size.width"
        :height="size.height"
        @pointermove="pointermove"
    >

2.在脚本中建立pointermove 方法，并在其中选择图形。

function pointermove(event: PointerEvent) {
  // 鼠标的世界坐标位
  const worldPosition=scene.clientToWorld(event.clientX, event.clientY);
    [polyObj, circleObj, rectObj,textObj,imageObj].forEach((obj) => {
    // 鼠标在图形对象中的本地坐标位
    const localPosition=worldPosition.clone().applyMatrix3(obj.worldMatrix.invert())
    // 判断点位是否在图形中
    const bool=obj.isPointIn(localPosition) 
    // 用于选择切换的颜色
    const colors='isImageGraph2D' in obj?['rgba(0,172,236,0.1)','rgba(255,0,0,0.1)']:['#00acec','orange']
    // 设置图形的填充样式
        obj.style.fillStyle = colors[+bool]
    })
  // 渲染
    scene.render()  
}

图形的选择方法都是isPointIn(point:Vector2) 方法。

因为图形是在本地坐标系中绘制的，所以在判断一个点位是否在图形中的时候，也要将此点位放在图形本地。

3.文字的包围盒。

之前我们说文字的选择时，说到其选择的是文字的包围盒。

我们可以通过下面的方法将其文字的包围盒示出来：

const textBoundingBox=new Graph2D(
    textObj.geometry.clone().applyMatrix3(textObj.worldMatrix),
    new StandStyle({ strokeStyle: '#00acec' })
)
scene.add(textBoundingBox)

效果如下：

textObj 的geometry 是处于其本地坐标系的，我们要将其画到世界坐标系中，就需要通过applyMatrix3(textObj.worldMatrix) 方法将其变换到世界坐标系。

总结

这节课我们对课程做了简单介绍，说了我要跟大家讲的3个滴滴笔试题，外加1个寻路算法。

接下来，我还说了我自己搭建的一个canvas渲染引擎的基本用法，后面我会用它来做面试题。

如果大家对canvas渲染引擎感兴趣的话，可以跟我说，我可以根据大家的需求专门出一个讲canvas渲染引擎的课。