【十天自制软渲染器】DAY 03：画一个三角形（向量叉乘算法 & 重心坐标算法）

如果你喜欢我写的文章，可以把我的公众号设为星标 ，这样每次有更新就可以及时推送给你啦。

前面两天画了点和线，今天我们来画一个最简单也是最强大的面——三角形。

本文主要讲解三角形绘制算法的推导和思路（只涉及到一点点的向量知识），最后会给出代码实现，大家放心的看下去就好。

本文源码 ：toyRenderer-day3-draw-triangle

1.如何画一个三角形？

在正式开始这一小节前，我们先想一下如何利用上一节的画线算法绘制一个实心的三角形。

假设现在平面内有三个不共线的点组成一个三角形，我们可以利用上一节的直线算法轻易的连接三角形的三条边，这时候我们会生成一个空心的、封闭的三角形。

那么这时候问题就转换为，如何把这个空心的三角形变为一个实心的三角形？

我想大家这时候已经有思路了，就是一行一行地扫描像素，把两个边界点之间的像素全部涂满上色就可以了。

这个方法肯定是可以的，但是实现不是很优雅，也不是业内的主流实现方式。因为基于行扫描的算法不是本文的重点，所以详细的推导和代码实现就不提供了，感兴趣的同学可以自己尝试实现一下。

2.利用向量叉乘画三角形

开始本节前先简单复习一下向量叉乘的几何意义。

2.1 数学推导

在三维空间中，两个三维向量 和 做叉乘，会得到一个和已知两个向量垂直的新向量 。

既然叉乘产生的是一个新向量，那么它肯定有个方向，我们一般用右手定则来判断：将右手食指指向 的方向、中指指向 的方向，则此时拇指的方向即为 的方向。

综上所述，我们可以对向量叉乘做一个严谨的定义：

其中 表示 和 在它们所定义的平面上的夹角（）。 和 是向量 和 的模长，而 则是一个与 、 所构成的平面垂直的单位向量，方向由右手定则决定。

有上面的理论，我们就可以判断两个向量的相对位置：

• 向量叉乘 向量，如果值为正，则表示 向量在 向量左侧
• 向量叉乘 向量，如果值为负，则表示 向量在 向量右侧
• 向量叉乘 向量，如果值为零，则表示 向量与 向量共线

会判断两条线的相对位置了，我们可以做个理论迁移，利用向量叉乘判断点和三角形的位置关系。

例如下面这里例子，对于三角形 来说，把三条边看作 、 、 三条首尾相连的向量，平面内有一个点 ，我们通过向量叉乘来判断相对位置：

• ，值为正，故 在 左侧
• ，值为正，故 在 左侧
• ，值为正，故 在 左侧

综合以上三个限制条件，我们可以判断 在 内。

如果上面三个计算中有值为负的情况，说明 在三角形外；如果有值为 0 的情况，说明 在三角形的边或顶点上。

2.2 代码实现

理论基础复习完了，我们就可以写代码了。代码实现相当简单，我们构建一个函数 crossProduct，传入三角形的三个顶点和平面上的任意一点 ，然后根据四个顶点构建出向量计算叉乘就可以了：

// 利用叉乘判断是否在三角形内部
Vec3i crossProduct(Vec2i *pts, Vec2i P) {
    // 构建出三角形 ABC 三条边的向量
    Vec2i AB(pts[1].x - pts[0].x, pts[1].y - pts[0].y);
    Vec2i BC(pts[2].x - pts[1].x, pts[2].y - pts[1].y);
    Vec2i CA(pts[0].x - pts[2].x, pts[0].y - pts[2].y);
    
    // 三角形三个顶点和 P 链接形成的向量
    Vec2i AP(P.x - pts[0].x, P.y - pts[0].y);
    Vec2i BP(P.x - pts[1].x, P.y - pts[1].y);
    Vec2i CP(P.x - pts[2].x, P.y - pts[2].y);
    
    return Vec3i(AB^AP, BC^BP, CA^CP);
}


代码非常的简单，我们跑一个简单的例子验证一下：

void drawSingleTriangle() {
    // 图片的宽高
    int width  = 200;
    int height = 200;

    TGAImage frame(width, height, TGAImage::RGB);
    Vec2i pts[3] = {Vec2i(10, 10), Vec2i(150, 30), Vec2i(70, 160)};

    Vec2i P;
    // 遍历图片中的所有像素
    for (P.x = 0; P.x <= width - 1; P.x++) {
        for (P.y = 0; P.y <= height - 1; P.y++) {
            Vec3i bc_screen  = crossProduct(pts, P);

            // bc_screen 某个分量小于 0 则表示此点在三角形外（认为边也是三角形的一部分）
            if (bc_screen.x<0 || bc_screen.y<0 || bc_screen.z<0) {
                continue;
            }
            
            image.set(P.x, P.y, color);
        }
    }
    
    frame.flip_vertically();
    frame.write_tga_file("output/day03_cross_product_triangle.tga");
}


看输出图像，我们已经成功绘制了一个三角形：

触不及防的安利：大家可以看我头像关注

【十天自制软渲染器】DAY 03：画一个三角形（向量叉乘算法 & 重心坐标算法）的更多相关文章

1. 【十天自制软渲染器】DAY 01：图形学学习建议与环境搭建

   推荐直接阅读博客原文,更新更及时,阅读体验更佳 「十天自制软渲染器」这个标题我承认标题党了.在对图形学一无所知的情况下想十天自制一个软渲染器,就好似一节课没上过却试图一个晚上看完<30 天精通 ...

2. 【十天自制软渲染器】DAY 02：画一条直线（DDA 算法 &amp&semi; Bresenham’s 算法）

   推荐关注公众号「卤蛋实验室」或访问博客原文,更新更及时,阅读体验更佳 第一天我们搭建了 C++ 的运行环境并画了一个点,根据 点 → 线 → 面 的顺序,今天我们讲讲如何画一条直线. 本文主要讲解直线 ...

3. CSharpGL&lpar;34&rpar;以从零编写一个KleinBottle渲染器为例学习如何使用CSharpGL

   CSharpGL(34)以从零编写一个KleinBottle渲染器为例学习如何使用CSharpGL +BIT祝威+悄悄在此留下版了个权的信息说: 开始 本文用step by step的方式,讲述如何使 ...

4. 基于物理渲染的渲染器Tiberius计划

   既然决定实现一个光栅化软件渲染器,我又萌生了一个念头:实现一个基于物理渲染的渲染器.

5. Django&colon;之Sitemap站点地图、通用视图和上下文渲染器

   Django中自带了sitemap框架,用来生成xml文件 Django sitemap演示: sitemap很重要,可以用来通知搜索引擎页面的地址,页面的重要性,帮助站点得到比较好的收录. 开启si ...

6. 基于OpenGL编写一个简易的2D渲染框架-08 重构渲染器-整体架构

   事实上,前面编写的渲染器 Renderer 非常简陋,虽然能够进行一些简单的渲染,但是它并不能满足我们的要求. 当渲染粒子系统时,需要开启混合模式,但渲染其他顶点时却不需要开启混合模式.所以同时渲染粒 ...

7. 用 windows GDI 实现软光栅化渲染器--gdi3d（开源）

   尝试用windows GDI实现了一个简单的软光栅化渲染器,把OpenGL渲染管线实现了一遍,还是挺有收获的,搞清了以前一些似是而非的疑惑. ----更新2015-10-16代码已上传.gihub地址 ...

8. Restful framework【第十篇】响应器（渲染器）

   基本使用 -响应器(一般用默认就可以了) -局部配置 renderer_classes=[JSONRenderer,] -全局配置 'DEFAULT_RENDERER_CLASSES': ( 'res ...

9. Qt 3D的研究（十）：描边渲染（轮廓渲染）以及Silhouette Shader

   Qt 3D的研究(十):描边渲染(轮廓渲染)以及Silhouette Shader 之前写了两篇文章,介绍了我在边缘检測上面的研究.实际上.使用GPU对渲染图像进行边缘检測.前提是须要进行两遍渲染.前 ...

随机推荐

1. LoadRunner 12&period;02 安装以及汉化教程

   LoadRunner 12.02 安装 一.下载 首先下载Loadrunner12安装包. 下载后有四个安装包: HP_LoadRunner_12.02_Community_Edition_Addit ...

2. 仿Smarty替换模板标签时遇到的问题

   最近正在做一个微型的仿TP框架,当然以鄙人之技术只能略仿表层,于是遇到的问题层出不穷.今天做到View层替换模板部分,本以为一下子搞掂的事,果不其然又是败下阵来. 好了,来重点. 模板文件 test1 ...

3. bzoj 3675 &lbrack;Apio2014&rsqb;序列分割（斜率DP）

   [题目链接] http://www.lydsy.com/JudgeOnline/problem.php?id=3675 [题意] 将n个数的序列分割k次,每次的利益为分割后两部分数值和的积,求最大利益 ...

4. &lt&semi;Chapter 2&gt&semi;2-1-2&period;安装Java SDK

   Java运行时环境的App Engine SDK运行在任何运行了Java SE开发工具(JDK)的电脑上.Java SDK App Engine 支持JDK 6,并且当运行App Engine的时候, ...

5. magento 好好玩

   Magento更换服务器的方法   1.把magento的整个目录打包.上传到新服务器,把magento数据库导出,然后在新服务器上导入.如果导不进去的是因为magento的数据库使用了外键约束,通过 ...

6. eclipse和myeclipse设置默认编码格式为UTF-8

   1:jsp页面设置默认为utf-8 以eclipse为例 2:java界面设置: Window->Preferences->General->Workspace 面板Text fil ...

7. Thread Pools

   许多程序会动态创建数十个设置上百个线程.举个例子,一个web服务器可能在每一个新到来的请求时创建一个新线程,然后在请求完成后将其终止. 然而,创建一个新线程将会带来一定的耗费:它需要在内核中创建自身必 ...

8. 阿里推荐的线程使用方法 ThreadPoolExecutor

   阿里推荐原因:使用线程池可以减少创建和销毁线程上所花的时间以及系统资源的开销,然后之所以不用Executors自定义线程池,用ThreadPoolExecutor是为了规范线程池的使用,还有让其他人更 ...

9. 细说SQL Server中的加密【转】

   简介 加密是指通过使用密钥或密码对数据进行模糊处理的过程.在SQL Server中,加密并不能替代其他的安全设置,比如防止未被授权的人访问数据库或是数据库实例所在的Windows系统,甚至是数据库所在 ...

10. jquery 表格排序，实时搜索表格内容

    jquery 表格排序,实时搜索表格内容   演示 XML/HTML Code <table class="table-sort"> <thead> &lt ...