tinyrenderer-Bresenham绘制直线算法

2024-03-20 21:44

本文主要是介绍tinyrenderer-Bresenham绘制直线算法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

如何画线段

第一种尝试

求x,y起始点的差值,按平均间隔插入固定点数
起始点平均插入100个点:

void line(int x0, int y0, int x1, int y1, TGAImage& image, TGAColor color) {for (float t = 0.; t < 1.; t += .01) {int x = x0 + (x1 - x0) * t;int y = y0 + (y1 - y0) * t;image.set(x, y, color);}
}
//...
line(2, 52, 90, 80, image, white);
//...

在这里插入图片描述

问题
线段距离过长,插入固定点数过少时,线段无法连续
插入10个点:

for (float t = 0.; t < 1.; t += .1) {

在这里插入图片描述

第二种尝试

根据 x轴的移动像素比例,给y轴线性插值
注意x轴的移动比例要转成float

void line(int x0, int y0, int x1, int y1, TGAImage &image, TGAColor color) { for (int x=x0; x<=x1; x++) { float t = (x-x0)/(float)(x1-x0); int y = y0*(1.-t) + y1*t; image.set(x, y, color); } 
}
//...
line(13, 20, 80, 40, image, white);
line(20, 13, 40, 80, image, red);
line(80, 40, 13, 20, image, red);
//...

在这里插入图片描述
问题

  1. 当y轴移动距离大于x轴移动距离时,y轴的插入值会非常离散,因为y轴的插入频率小于x轴
  2. 起点x必须小于终点x

第三种尝试

判断线段的宽高比(斜率),以长的方向递增做为插值频率
并且对比起点,终点在递增方向轴的大小,以小的点做为递增起始点

void line(int x0, int y0, int x1, int y1, TGAImage &image, TGAColor color) { bool steep = false; if (std::abs(x0-x1)<std::abs(y0-y1)) { // if the line is steep, we transpose the image std::swap(x0, y0); std::swap(x1, y1); steep = true; } if (x0>x1) { // make it left−to−right std::swap(x0, x1); std::swap(y0, y1); } for (int x=x0; x<=x1; x++) { float t = (x-x0)/(float)(x1-x0); int y = y0*(1.-t) + y1*t; if (steep) { image.set(y, x, color); // if transposed, de−transpose } else { image.set(x, y, color); } } 
}
//...
line(13, 20, 80, 40, image, white);
line(20, 13, 40, 80, image, red);
line(80, 40, 13, 20, image, red);
//...

在这里插入图片描述
问题
效率低,做了多次除法和浮点数运算。10%的时间花在复制颜色上。但是70%的时间都花在了调用line()上
没有断言,没有越界检查等(这些文章里为了可读性,所以不处理)

第四种尝试

每个除法都有相同的除数,可以提到循环外
在这里插入图片描述
我们是以长轴每次递增1做为循环,因此另一个轴每次递增的插值是在[0,1]之间。根据斜率决定。
这里我们假设长轴是x,如上图,每次x递增1时,y轴根据斜率判断增加的值,如果大于0.5时,则代表了线段的y值是在右上的格子(y+1),小于0.5表示线段的y值是在右边的格子(y不变)
由此可以根据斜率判断每次x递增时,y轴的值是否需要+1
循环内省去了除法计算,减少了浮点数计算
float t = (x - x0) / (float)(x1 - x0);
int y = y0 * (1. - t) + y1 * t;

void line(int x0, int y0, int x1, int y1, TGAImage &image, TGAColor color) { bool steep = false; if (std::abs(x0-x1)<std::abs(y0-y1)) { std::swap(x0, y0); std::swap(x1, y1); steep = true; } if (x0>x1) { std::swap(x0, x1); std::swap(y0, y1); } int dx = x1-x0; int dy = y1-y0; float derror = std::abs(dy/float(dx)); float error = 0; int y = y0; for (int x=x0; x<=x1; x++) { if (steep) { image.set(y, x, color); } else { image.set(x, y, color); } error += derror; if (error>.5) { y += (y1>y0?1:-1); error -= 1.; } } 
} 

问题
仍然还有一个浮点数计算及比较
error += derror;

第五次尝试

error浮点数在循环体中的作用就是来用与0.5做大小比较
error += derror;
if (error > .5)
error -= 1.;

==>> error每次变化量都乘2
error += derror * 2;
if (error > 1)
error -= 2;

==>> error每次变化量都乘dx
error += derror * 2 * dx;
if (error > dx)
error -= 2 * dx;

==>> derror * 2 * dx 是int型 std::abs(dy)*2;
==>>error也不需要再是float

void line(int x0, int y0, int x1, int y1, TGAImage &image, TGAColor color) { bool steep = false; if (std::abs(x0-x1)<std::abs(y0-y1)) { std::swap(x0, y0); std::swap(x1, y1); steep = true; } if (x0>x1) { std::swap(x0, x1); std::swap(y0, y1); } int dx = x1-x0; int dy = y1-y0; int derror2 = std::abs(dy)*2; int error2 = 0; int y = y0; for (int x=x0; x<=x1; x++) { if (steep) { image.set(y, x, color); } else { image.set(x, y, color); } error2 += derror2; if (error2 > dx) { y += (y1>y0?1:-1); error2 -= dx*2; } } 
} 

消除循环中的分支
将steep判断移到for循环外,可以通过牺牲一些代码膨胀,把速度提高到2倍
(现代一些编译器会自动移出到for循环外)

if(steep) {for(int x = x0; x<=x1; ++x) {img.set_pixel_color(y, x, color);error2 += derror2;if(error2 > dx) {y += (y1>y0? 1 : -1);error2 -= dx*2;}}} else {for(int x = x0; x<=x1; ++x) {img.set_pixel_color(x, y, color);error2 += derror2;if(error2 > dx) {y += (y1>y0? 1 : -1);error2 -= dx*2;}}}

线框显示

导入了一个模型数据读取的类model.h,model.cpp和向量几何运算的类geometry.h

obj文件的数据:
v 0.608654 -0.568839 -0.416318
其中“v "开头的数据代表了模型顶点的位置,归一化之后的。通常取值在-1,1,实际要根据自身屏幕的宽高进行转化
f 1193/1240/1193 1180/1227/1180 1179/1226/1179
"f "储存了每个面(至少是个三角形)的信息,每组数字的第一个代表了前面对”v “开头的顶点数据的索引。obj文件的索引是从1开始,因此从c++的数组读取时,索引要-1读取

for (int i=0; i<model->nfaces(); i++) { std::vector<int> face = model->face(i); for (int j=0; j<3; j++) { Vec3f v0 = model->vert(face[j]); Vec3f v1 = model->vert(face[(j+1)%3]); int x0 = (v0.x+1.)*width/2.; int y0 = (v0.y+1.)*height/2.; int x1 = (v1.x+1.)*width/2.; int y1 = (v1.y+1.)*height/2.; line(x0, y0, x1, y1, image, white); } 
}

我这里给model加了个maxNum,用来适配obj顶点数据是非标准化设备坐标
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

项目跟随练习代码地址

这篇关于tinyrenderer-Bresenham绘制直线算法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/830823

相关文章

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例:使用随机森林预测鸢尾花品种4.1

使用Python绘制蛇年春节祝福艺术图

《使用Python绘制蛇年春节祝福艺术图》:本文主要介绍如何使用Python的Matplotlib库绘制一幅富有创意的“蛇年有福”艺术图,这幅图结合了数字,蛇形,花朵等装饰,需要的可以参考下... 目录1. 绘图的基本概念2. 准备工作3. 实现代码解析3.1 设置绘图画布3.2 绘制数字“2025”3.3

使用Python绘制可爱的招财猫

《使用Python绘制可爱的招财猫》招财猫,也被称为“幸运猫”,是一种象征财富和好运的吉祥物,经常出现在亚洲文化的商店、餐厅和家庭中,今天,我将带你用Python和matplotlib库从零开始绘制一... 目录1. 为什么选择用 python 绘制?2. 绘图的基本概念3. 实现代码解析3.1 设置绘图画

Python绘制土地利用和土地覆盖类型图示例详解

《Python绘制土地利用和土地覆盖类型图示例详解》本文介绍了如何使用Python绘制土地利用和土地覆盖类型图,并提供了详细的代码示例,通过安装所需的库,准备地理数据,使用geopandas和matp... 目录一、所需库的安装二、数据准备三、绘制土地利用和土地覆盖类型图四、代码解释五、其他可视化形式1.