//Description: V-HACD (Volumetric Hierarchical Approximate Convex Decomposition)

//Description: Qt+Opengl学习笔记，关于OpenGL，基于Qt 5.15.2

//Description: Biomes (生物群落)

//Description: 机器学习笔记

//Description: 水体渲染

//Description: 图片格式总结

//Create Date: 2021-10-28 10:10:39

//Author: channy

Image Format

概述

记录各种图片格式

BMP

1. 文件头 bmp文件头包含如下信息：

bfType：2字节，文件类型； bfSize：4字节，文件大小； bfReserved1：2字节，保留，必须设置为0； bfReserved2：2字节，保留，必须设置为0； bfOffBits：4字节，从头到位图数据的偏移；

1. 位图信息头 位图信息头一共40字节，包含如下内容： biSize：4字节，信息头的大小，即40； biWidth：4字节，以像素为单位说明图像的宽度； biHeight：4字节，以像素为单位说明图像的高度，同时如果为正，说明位图倒立（即数据表示从图像的左下角到右上角），如果为负说明正向； biPlanes：2字节，为目标设备说明颜色平面数，总被设置为1； biBitCount：2字节，说明比特数/像素数，值有1、2、4、8、16、24、32； biCompression：4字节，说明图像的压缩类型，最常用的就是0（BI_RGB），表示不压缩； biSizeImages：4字节，说明位图数据的大小，当用BI_RGB格式时，可以设置为0； biXPelsPerMeter：表示水平分辨率，单位是像素/米，有符号整数； biYPelsPerMeter：表示垂直分辨率，单位是像素/米，有符号整数； biClrUsed：说明位图使用的调色板中的颜色索引数，为0说明使用所有； biClrImportant：说明对图像显示有重要影响的颜色索引数，为0说明都重要；

2. 调色板（selected）

3. 位图数据

PBM,PGM,PPM

PBM

只有黑白两种颜色的图像格式，1是黑色，0是白色。

1. P1/P4，编码格式
2. 图像size，宽度和高度，ASCII码
3. 数据：每一位代表一个像素

PGM

灰度图

1. P2/P5，编码格式
2. 图像size，宽度和高度，ASCII码
3. 最大灰度值
4. 数据： P5 每个像素用可以用二进制表示 P2 每个像素使用字符串来表示

PPM

PPM（Portable Pixmap Format）

1
2
3
4
5

P6
# Created by IrfanView
1280 960
255
,22,22+11.44156/34.23+/0,01/34.21-10/32.21.21265384.3/051384574352/32265376265273051/51/51.403954::-33/3426737:,03,1505929?.5;#-/#%%'!%($&%#%$"&' $%#'(&*+&')%&(()+)*,+,.()+&')()+)*,*+-+,.-.0./1,-/+,.-.0(,-)-.)-.,01-12)-.)-0*.1-.3./4108219,20(3/(40#//%&$$&$%&%#$#+"*%$%(*)

1. P3/P6，编码格式
2. 注释
3. 图像size，宽度和高度，ASCII码
4. 最大像素值，0-255
5. 数据： ASCII 按RGB顺序，空格隔开，每一行用回车隔开，对应图像中的一行
   Binary 用24bits代表每一个像素，红绿蓝分别占用8bits

上图例子中，编码格式为P6，图像大小为1280*960，最大像素值255，首个像素的rgb是0x2c3232

PNG

(Portable Network Graphic Format，PNG)

1. PNG，编码格式
2. 数据块，有两种类型的数据块，关键数据块（critical chunk）和辅助数据块（ancillary chunk）
3. 每个数据块由长度、数据块类型码、数据块实际内容、循环冗余检测 。。。。。。

JPG

GIF

GIF(Graphics Interchange Format)

数据块可分成3类：控制块(Control Block)，图形描绘块(Graphic-RenderingBlock)和专用块(Special Purpose Block)。

//Description: 学习roblox的地形工具

//Description: 从sdf数据中生成网格

//Create Date: 2021-07-10 14:46:27

//Author: channy

Mesh Generation From SDF 从sdf数据中生成网格

体素顶点的sdf (signed distance function) 值表示该顶点到目标网格面的最近距离，如果目标网格面是封闭的，sdf<0表示该顶点在网格面内部，>0表示在网格面外部

网格生成算法

1. Marching Cube (MC)
2. Dual Marching Cube (DMC)
3. Transvoxel
4. Dual Contouring (DC)
5. Surface Nets

Marching Cube (MC)

基本流程：

• 一个体素一条边的数值决定点的位置（在体素边上）
  • 如一条边如果两个点的值分别为p1=v1和p2=v2（v1v2<=0），则生成的点在p1-v1(p2-p1)/(v2-v1)上
• 一个体素生成的面只有16种情况

优势

• 经典，能够满足大部分使用场景
• 查表，效率高

劣势

• 所有顶点都生成在voxel的边上，有限制
• 有二义性（如右图点的不同连接方式），导致在特殊情况下会有裂缝
• 只能生成光滑的曲面，无法处理尖锐的棱角情况

Marching Cubes

Dual Marching Cube (DMC)

基本流程：

• MC的改进，体素顶点不是sdf值，而是Hermite data
• 其它同MC

优势

• 同MC

劣势

• 同MC

Transvoxel

基本流程：

• 同MC
• 在MC的基础上解决MC的二义性产生的裂缝

优势

• 在MC的基础上解决了MC的二义性问题

劣势

• 同MC

Dual Contouring (DC)

基本流程：

• 根据最小化二次误差函数生成顶点
• 误差函数E(x)=∑_i▒(n_i∙(x−p_i))^2
• 对每个voxel的8个顶点p_i，n_i为该顶点对应于目标网格面的法向，x为最终生成的点的位置

优势

• 能够处理MC不能处理的尖锐的棱角情况
• 有法线信息做为输入，能够生成精确度高的网格，并可根据法线进行调整

劣势

• 需要已知法线信息做为输入，通常适用于工业零件建模、或由Perlin噪声生成的不可变地形网格生成（Perlin噪声在生成地形的同时可以获取对应点的法向）

Dual Contouring

Surface Nets

基本流程：

• 对体素的8个顶点的sdf值与体素顶点位置做加权平均
• 每个voxel最多只生成一个顶点

优势

• 生成的顶点可以在voxel内部或边上任意位置，没有MC点在voxel边上的限制，也没有DC需要法线作为输入的限制，生成的曲面类型比较丰富

劣势

• 每个voxel最多只生成一个顶点，无法满足像地形粗糙类需要网格细分的需求（voxel体素通用劣势）

Native Surface Nets

总结

设sdf函数为f(v)，对每一个voxel，如果该voxel的12条棱中存在至少一条棱满足f(v1) * f(v2) <= 0，说明这个voxel包含有网格面，记为活动voxel。

对于MC，根据活动voxel所有顶点的情况共可分为10+个种类，依靠查找MC表确定活动voxel产生的顶点数和面数，每个产生的顶点都在voxel的边上，不会出现在内部或外部。

而对于DC和SN，都是每个活动voxel产生一个网格顶点，DC由法线控制，顶点可能会出现离voxel偏远的情况或是解矩阵方程无解的情况，需要特殊处理。

附地形数据生成

1. 把地形区域按整数划分成单位立方体，使得每个单位立方体的顶点的三维坐标都是整数
2. 对每一个单位立方体顶点，根据需要的地形计算该顶点所在位置的三维有向距离场 (Signed Distance Field，简称SDF)。其中SDF的定义为：当前位置与距离当前位置最近 的地形之间的距离，正数表示该位置朝向地形正面（地形表面），即在地形外面，负数 表示该位置朝向地形里面，即在地形里面。 一些基本的SDF计算方法： 生成一个球心在c(cx, cy, cz)半径为r的球形地形：点p(x, y, z)的sdf = (x - c).length() - r。 生成一个中心在c(cx, cy, cz)边长为s的正方体地形：记v(vx, vy, vz) = (p - c ) - 0.5 * s; 则 点p(x, y, z)的sdf = v.length() + min(0, max(vx, vy, vz))。 其中对于任一三维向量v(vx, vy, vz)，v的长度 v.length() = sqrt(vx * vx + vy * vy + vz * vz)
3. 对每一个在地形外部的顶点，其SDF值为正数，其材质为空气。而对于每一个在地形内 部的顶点，其SDF值为负数（即在地形里面的点），根据需要设置材质。材质分为四 种：1) 规则材质（砖块、木板等）、2) 半规则材质（路面、冰、玄武岩等）、3) 不规则 材质（沙、泥土、草等），4) 水材质，分别对应生成方块网格、带棱角的网格、及光滑 的网格。水材质需要单独考虑，是因为生成网格时需要考虑水面和水底（大陆架）两 层，而其它材质只需要生成一层。
4. 对每个单位立方体的顶点，用tag = {1, 2, 3}表示该顶点是空气、水、其它材质。

附三角网格生成

1. 考虑到地形可能很大，从计算机角度看一次性直接计算所有数据容易造成内存和cpu不够 用。故把整个地形分割成若干块，每个块为包含19 * 19 * 19个单位立方体的大立方体。 先对每个块生成三角形网格，再对所有块进行合并

2. 对每个块中的每个单位立方体，判断该单位立方体的8个顶点对应的SDF值是否同号； 如果8个顶点同号且tag相同，即顶点SDF值均为正数或均为负数，且tag均为同一类，则 说明该单位立方体要么全部位于地形外部，要么全部位于地形内部，不产生地形网格； 如果8个顶点异号或tag不相同，即其中至少有一个正数和一个负数，或tag包含两种类别 以上，则说明该单位立方体有地形表面经过，需要产生地形网格。不同的tag保证了水和 陆地相接触的立方体也能生成网格，即大陆架网格

3. 对每一个需要产生地形网格的单位立方体，记顶点的三维坐标位置e(ex, ey, ez)，8个顶 点的三维坐标位置$e_i(ex_{i}, ey_{i}, ez_{i})$，其中i = [1, 8]，每个顶点的SDF值sdf_{ei}，计算该单位立方体生成的网格顶点的位置p(px, py, pz) = \sum (e_i * sdf_{ei}), i = 1…8。

4. 根据材质调整生成的网格顶点的位置。对于生成该网格顶点的8个单位立方体顶点，如果 存在至少一个顶点的材质为规则材质，则表示需要生成方块地形，则把该网格顶点移到 该单位立方体的中心点；如果存在至少一个顶点的材质为半规则材质，则表示需要生成 带棱角的网格，则需要根据每种材质的光滑程度[0,1]，对该顶点进行一定的位移。例 如：玄武岩的光滑程度为0.3，记生成的网格顶点坐标位置为q(x, y, z)，则先对单位立文 体左下角的顶点p取哈希值得到偏移坐标值offset(ox, oy, oz)，再把生成的网格顶点坐标 位置q + offset得到最终的网格顶点坐标位置。为了计算方便，如果偏移后得到的坐标位 置超出了该单位立方体，则需要移回到立方体内部

5. 连接相邻单位立方体的顶点生成三角形网格。对于每一个块中的每一个单位立方体顶点p (x, y, z)，检测p1(x + 1, y, z), p2(x, y + 1, z) 和 p3(x, y, z + 1)三个相邻的顶点，如果p和 p_i的tag不相同，则把这几个单位立方体对应生成的网格顶点连接成三角形网格。 例 如：单位立方体顶点p(x, y, z)和p1(x + 1, y, z)的tag不相同，则单位立方体b(x, y, z)和b2 (x，y + 1, z)和b3(x, y, z + 1)和b23(x, y + 1, z + 1)四个单位立方体对应生成的网格顶点 bp、bp2、bp3和bp23连接成两个三角形(bp, bp2, bp23)和(bp, bp23, bp3)

6. 计算生成的每个三角形面的法线，再根据材质类型计算每个三角形顶点，即网格顶点的 法线，用于渲染出棱角。对于一个网格顶点，如果生成该网格顶点的单位立方体8个顶点 中，存在至少一个顶点的材质为非规则材质或水，则网格顶点不共用法线，即每个三角 形面的顶点有自己的法线，即为该三角形面的法线；否则网格顶点共用法线，即如果两 个三角形面有一个共同的顶点，则该顶点的法线为两个三角形面的法线的平均值。

7. 生成LOD（Level of Detail）网格。渲染对于近处和远处需要呈现的细节不同，故远处的 三角形网格可以比近处的三角形网格稀疏

//Description: 程序化地形生成

//Create Date: 2021-05-15 17:19:39

//Author: channy

noise terrain generation

概述

最终目标为生成全局地形vBox，地貌种类为n，包括如下部分：

• 基本地形生成，地形高低起伏，考虑洞穴（地形网格，否则直接用高度图即可）
• 地貌类型，根据地形高度和不同地貌的概率确定（地形材质）
• 生态，主要为动植物分布
• 其它物品

基本思路：

1. 非机器学习
   1. voronoi分成n个区域，对应n种地貌
   2. 根据输入的biome_size，把整块地形近似分割成biome_size方块，每个方块随机使用不同的地貌
   3. 对每个区域生成对应地貌
      1. 噪声生成主地貌
         • x-z遍历，目标单位立方体中，与其相邻的9个立方体（包括其本身）各自使用噪声产生一个数值（占有率），一个地貌index，同时记录其与目标立方体中随机点的距离
         • 对上面9个立方体各自生成权重参数
         • 在y即高度上，根据当前高度与总高度比值，排除上下固定地形（空气和地基），根据地貌修正占有率，及地表面和地里面的材质
           • 水平面
           • 平原：草地 + 石头 + 水
           • 沼泽：草地 + 泥 + 浆 + 水
           • 山地：草地 + 泥
           • 沙丘：沙 + 沙石
           • 熔岩：岩浆 + 岩浆岩 + 石头
           • 冰川：雪 + 冰
           • 峡谷：泥 + 水 + 浆
           • 龟裂：voronoi图
         • 根据ridge噪声生成洞穴，即判断当前立方体是否为洞穴，是则占有率置0
         • 根据地貌和高度设置温度，根据地貌设置湿度
      2. 地形边界平滑处理，噪声参数+权重
   4. 地形生态根据区域随机生成（erosion侵蚀，高度决定植被）
2. 机器学习
   1. 输入点、线、面作为地形高度、生态类型参考，算法生成具体生态
   2. 生态笔刷

Noise type 噪声分类

fastnoise library - a noise library contains most of classical noise

• single noise
  • Lattic based 基于晶格的方法
    • Gradient noise
      • Perlin noise
      • Simplex noise
      • Wavelet noise
    • Value noise
  • Point based 基于点的方法
    • Worley/Cell noise - Voronoi diagram
• fractal noise 频率+振幅
  • fbm noise
  • ridge noise
  • domain wrapping noise

用各种noise可以生成地形高度图，但无法生成复杂结构如山洞等

procedure terrain 利用噪声生成地形

Making maps with noise functions

游戏中的程序化地形生成技术简介

Terrain 算法整理

Free Terrain 3D models

Fantasy Map Generator

Perlin Noise/Simplex Noise

其中Perlin noise被广泛应用，可以用Perlin噪声生成三维噪声图，[-1,1]分布，根据每个空间点的噪声正负确定该点是否是地形的一部分（marching cubes 网格化算法）

常用于生成平滑的地形

perlin noise algorithm

• 生成网格梯度向量
• 曲线拟合
• Simplex Noise的梯度函数为三阶方程，避免导数不连续问题

Perlin noise in 3d

Perlin noise implement

2d perlin noise可生成高度图，3d perlin noise可生成立体图

fractal noise/分形噪声

分形噪声本质上是基础噪声的叠加，如Perlin + fbm多用于生成山地地形

（Fractal Noise is any noise which produces a fractal）

参数说明：

amplitude: 噪声振动幅度，影响噪声的最大最小值

frqueency: 频率

octaves: 分形数，影响平滑度。The level of detail. Lower = more peaks and valleys, higher = less peaks and valleys.

lacunarity: 倍数，间隙度。The level of detail on each octave (adjusts frequency).

gain: 增益。How much an octave contributes to overall shape (adjusts amplitude).

Voronoi图生成地形算法(Worley/Cell Noise)

效果：对整个地形进行分割成区域，每个区域一种地形（平原、山地…）；或用于平原粗糙化分裂

2d Voronoi基本图形生成

n个随机点vCenters（最后分割成的区域个数及中心点）

对图中每个像素点，查找最近的vCenters

over

2d Voronoi高度图生成

对图中的每个像素点，knn查找最近的k个点，计算到这k个点的加权距离，作为高度

2d Voronoi图边界粗糙化

level2, f(n) > n 个随机点vHCenters

对图中每个像素点，查找最近的vHCenters

对查找到的vHCenters，查找最近的vCenters

根据目标像素到最近中心点的距离确定高度，距离有Eular距离等

Diamond Square

Voxel数据存储

每个数组元素（Voxel）保存的不再是高度值，而是一个近似的距离值（iso-value）或密度值SDF，表示这个点有多大程度在土地里或暴露在空气中。

SDF distfunctions

3D 等值面提取/网格重建

• Marching Cubes
• Marching tetrahedra (2D) - Marching Cube (3D)
• Dividing Cubes
• Dual Contouring (Hermite data) 根据法线最小化误差函数求得点所在的坐标，每个inside的voxel顶点对应生成一个点，法线可指定 DC
• Transvoxel MC的改进
• Naive Surface Nets SurfaceNets
• Poisson
• Dual Marching Cubes dmc

Delaunay三角化

数学相关

convex hull

Andrew / Quickhull

距离分类

• Euclidean Use the Euclidean distance metric

• Manhattan Use the Manhattan distance metric.

• Chebychev Use the Chebychev distance metric.

• Minkowski Use the Minkowski distance metric.

数学库

CGAL 使用LGPL和GPL协议

[ALGLIB]

[Eigen]

LAPACK++

Math Libraries in C++

生态模拟

1. 不同噪声生成不同地形

• 山地：perlin + fbm
• 沙丘：perlin + ridge

  1 2 3 4 5 6 7 8 9 10 11

  //fast_noise_lite //set noise type noiseLite.SetNoiseType(NoiseType_Perlin); noiseLite.SetFractalType(FractalType_Ridged); //set noise params noiseLite.SetFrequency(0.01); noiseLite.SetFractalGain(0.5); noiseLite.SetFractalOctaves(7); noiseLite.SetFractalLacunarity(1.0/1.75); noiseLite.SetFractalWeightedStrength(2);

• 平原/丘陵/极地：perlin + domain wrapping
• 电路板：domain wrapping
• 河流: Voronoi图
  • 交互：确定最小初始高度，随机河流源头，梯度下降，erosion生成流域图
  • 非交互：
• 植被 （温度、湿度、高度）
  • 到水源的距离确定湿度
  • 基于密度图的植被放置方法
  • 三种噪声分别对应三个因素
• 道路
  • 贝塞尔曲线，Catmull-Rom曲线
• 城市

在地图上生成蜿蜒河流的两种方法 Polygonal Map Generation for Games

地形平滑

Gaussian filter

bi-linear interpolation

对voxel中的data进行滤波

voxel terrain storage

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

^
| A--------B
| |        |
| | P      |
| |        |
| C--------D
Y 
*X------------>

// This could be different depending on how you get points
// (basically generates a [0, 1] value depending on the position in quad;
px = P.x - (int)P.x
py = P.y - (int)P.y
AB = A.h * (1.0 - px) + B.h * px;
CD = C.h * (1.0 - px) + D.h * px;
ABCD = AB * (1.0 - py) + CD * py;

物理相关

raytracing

Raytracing on a grid

同roblox的比较Roblox-StudioTools

笔刷+水材质，以下terrain表示非水材质的地形

属性

笔刷形状：圆平面、正方形平面、球体、立方体、圆柱体…… 笔刷大小：1不一定有效，因为一个单位立方体最多只生成一个点，一个点不足以表示复杂多面体 材质：自动材质 锚点：鼠标打到地形表面的点处于形状的位置 锁定平面：是否根据地形表面的法线确定笔刷平面是垂直于法线还是保持鼠标刚点下时所在的平面不变 锁定方向：增长/侵蚀特有 强度：

操作

• 增加/生长
  • 如果笔刷大小比较小（<=2），稍微放大笔刷（+0.5），否则按原大小笔刷改变细微，肉眼可能看不出来
  • 根据形状计算形状内外的单位立方体的占有率occupancy
  • 如果是自动材质，根据笔刷方向，反向选择对应立方体的材质
  • 如果当前已有地形，比较占有率，新占有率大则更新原占有率；如果当前没有地形，赋值占有率和材质
  • 如果忽略水：先减少terrain，后在减少的位置上顺延增加水
  • terrain: 可在水上定位，但忽略水，直接增加terrain
• 减少/侵蚀
  • 如果笔刷大小比较小（<=2），稍微放大笔刷（+0.5），否则按原大小笔刷改变细微，肉眼可能看不出来
  • 根据形状计算形状内外的单位立方体的占有率occupancy
  • 如果当前已有地形，直接更新占有率和材质（空气），如果当前没有地形，比较占有率，新占有率小则更新原占有率
  • 已有水不受影响，先减少terrain，当减少部分有水时，水不做减少，原来要减少的部分替换成水
• 光滑
  • 取当前单位立方体和周围8个立方体的占有率，作平均
  • 水和terrain同等对待
• 展平
  • 展平terrain，当展平部分满足一定条件时，增加水
• 绘制
  • terrain能绘制成水，不可逆
• 海平面
  • 在一个整体范围内增加/删除所有水

性能优化

地形lod

• LOD减面
  • 保持最外圈的网格信息，减化内圈的网格信息 改进的Unreal4减面算法
• 边插入/删除
  • 边删除&边插入
• 缝合 前提：不同lod相接的地方有共同顶点
  • 缝合
• CDLOD

网格面简化

• 基于二次误差度量的网格简化
  • 二次度量误差（QEM，quadric error metric）指的是当前顶点到其邻域所有三角面（也称关联平面）的距离平方和。

Simplify Surface

reference

天美F1引擎专家：如何利用PCG技术加速大世界地形生产 Virtual Terrain

//Description: openmp

//Create Date: 2021-05-15 12:31:38

//Author: channy

OpenMP

Visual C++ supports the OpenMP 2.0 standard.

Qt:

1
2

QMAKE_CXXFLAGS += -fopenmp
LIBS += -fopenmp

parallel

用在一个代码段之前，表示这段代码将被多个线程并行执行

1
2
3
4
5
6
7

#pragma omp parallel
    {
        std::cout << omp_get_thread_num();
    }
	
//output	
//1320	

for

用于for循环之前，将循环分配到多个线程中并行执行，必须保证每次循环之间无相关性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

#pragma omp for
	for (int i = 0; i < 20; i++) {
		std::cout << i << " " << omp_get_thread_num() << std::endl;
	}

//invalid

	int a[5], i;

#pragma omp parallel
	{
		// Perform some computation.
#pragma omp for
		for (i = 0; i < 5; i++)
			a[i] = i * i;

		// Print intermediate results.
#pragma omp master
		for (i = 0; i < 5; i++)
			printf_s("a[%d] = %d\n", i, a[i]);

		// Wait.
#pragma omp barrier

// Continue with the computation.
#pragma omp for
		for (i = 0; i < 5; i++)
			a[i] += i;
	}

parallel for

也是用在一个for循环之前，表示当前层for循环的代码将被多个线程并行执行。

1
2
3
4

#pragma omp parallel for
    for (int i = 0; i < 10; i++) {
        std::cout << i << " " << omp_get_thread_num() <<std::endl;
    }

parallel for collapse(2)

多层for循环

1
2
3
4
5
6
7
8
9
10
11

	int sum = 0;
#pragma omp parallel for collapse(2)
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 11; j++) {
            sum += i * j;
#pragma omp critical
            {
                std::cout << i << " " << j << " " << omp_get_thread_num() << std::endl;
            }
        }
    }

reduction / reduction (operator: var1, val2, …)

其中sum是共享的，采用reduction之后，每个线程根据reduction（+: sum）的声明算出自己的sum，然后再将每个线程的sum加起来。

1
2
3
4
5
6

	int sum = 0;
#pragma omp parallel for num_threads(4) reduction(+:sum)
	for (int i = 0; i < 100; i++) {
		sum += i;
	}
	std::cout << sum << std::endl;

critical

用在一段代码临界区之前。表示同一时间内该段代码只被单个线程执行

single

只被单个线程执行一次

1
2
3
4
5
6
7
8
9
10

	int a = 0, b = 0;
#pragma omp parallel
	{
#pragma omp single
		a++;
#pragma omp critical 
		b++;
	}

	std::cout << a << " " << b << std::endl;

atomic

原子操作，多用于++,–,etc，仅对一句有效

1

# pragma omp atomic [read | write | update | capture]

master

用于指定一段代码块由主线程执行

sections / section

用在可能会被并行执行的代码段之前

parallel sections

parallel和sections两个语句的结合

flush

同步

barrier

用于并行区内代码的线程同步，所有线程执行到barrier时要停止，直到所有线程都执行到barrier时才继续往下执行。

1
2
3
4
5
6
7
8

    int sum = 0;
#pragma omp parallel num_threads(10)
    {
#pragma omp atomic
        sum += 10;
#pragma omp barrier
        std::cout << sum << std::endl;
    }

ordered

用于指定并行区域的循环按顺序执行

private / lastprivate / fristprivate

用于指定一个变量是线程私有的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

	int tmp = 0;
#pragma omp parallel for private(tmp) 
	for (int i = 0; i < 10; i++) {
		tmp += i;
		printf("%d %d %d\n", i, tmp, omp_get_thread_num());
	}

	std::cout << "------------------" << tmp << std::endl;

#pragma omp parallel for firstprivate(tmp)
	for (int i = 0; i < 10; i++) {
		tmp += i;
		printf("%d %d %d\n", i, tmp, omp_get_thread_num());
	}

	std::cout << "------------------" << tmp << std::endl;

#pragma omp parallel for lastprivate(tmp)
	for (int i = 0; i < 10; i++) {
		tmp += i;
		printf("%d %d %d\n", i, tmp, omp_get_thread_num());
	}

	std::cout << "------------------" << tmp << std::endl;

lock

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

    int value[10] = {0};
    omp_lock_t lock[10];
#pragma omp parallel for
    for (int i = 0; i < 10; i++) {
        omp_init_lock(&lock[i]);
    }
#pragma omp parallel for
    for (int i = 0; i < 10; i++) {
        int index = rand() % 10;
        omp_set_lock(&lock[index]);
        value[index]++;
        omp_unset_lock(&lock[index]);
    }
#pragma omp parallel for
    for (int i = 0; i < 10; i++) {
        omp_destroy_lock(&lock[i]);
    }

    for (int i = 0; i < 10; i++) {
        std::cout << value[i] << " ";
    }

barrier / nowait

for循环结束后默认带barrier

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

#pragma omp parallel
	{
#pragma omp for nowait
		for (int i = 0; i < 10; i++) {
			printf("+");
		}

#pragma omp for 
		for (int i = 0; i < 10; i++) {
			printf("-");
		}

		for (int i = 0; i < 10; i++) {
			printf("*");
		}
	}

task

for和sections指令的”缺陷“：无法根据运行时的环境动态的进行任务划分，必须是预先能知道的任务划分的情况。

task主要适用于不规则的循环迭代（如下面的循环）和递归的函数调用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

void mytask(int& a) {
    a++;
}

int main(int argc, char *argv[])
{
    int N = 10;
    int a[N];

    for (int i = 0; i < N; i++) {
        a[i] = 1;
    }

#pragma omp parallel num_threads(2)
    {
#pragma omp single
        {
            for (int i = 0; i < N; i = i + a[i])
            {
#pragma omp task
                mytask(a[i]);
            }
        }
    }

    for (int i = 0; i < N; i++) {
        std::cout << a[i] << std::endl;
    }

    return 0;
}

schedule

simd

向量化