没有合适的资源?快使用搜索试试~ 我知道了~
温馨提示
试读
60页
(ebook - PDF - Programming) Abrash, Michael - Ramblings in Realtime (On the Quake 3D Engine) (2000).pdf As for how to rethink the design, do it by pursuing whatever ideas occur to you, no matter how off-the-wall they seem. Many of the truly brilliant design ideas I’ve heard over the years sounded like nonsense at first, because they didn’t fit my preconceived view of the world. Often, such ideas are in fact off-the-wall, but just as the news about Paradise’s chip sparked Tom’s imagination, aggressively pursuing seemingly-outlandish ideas can open up new design possibilities for you. Case in point: The evolution of Quake’s 3-D graphics engine.
资源详情
资源评论
资源推荐
Blue's News Presents:
Ramblings in Realtime
by
Michael Abrash
Chapter 1: Inside Quake - Visible Surface Determination
Chapter 2: Consider the Alternatives - Quake's Hidden Surface Removal
Chapter 3: Sorted Spans in Action
Chapter 4: Quake's Lighting Model - Surface Caching
Chapter 5: Surface Caching Revisited - Quake's Triangle Models and More
Chapter 6: Quake's 3D Engine - The Big Picture
Appendix : Permissions and Author’s Note
Inside Quake: Visible-Surface Determination
by Michael Abrash
Years ago, I was working at Video Seven, a now-vanished video adapter manufacturer, helping
to develop a VGA clone. The fellow who was designing Video Seven’s VGA chip, Tom Wilson,
had worked around the clock for months to make his VGA run as fast as possible, and was
confident he had pretty much maxed out its performance. As Tom was putting the finishing
touches on his chip design, however, news came fourth-hand that a competitor, Paradise, had
juiced up the performance of the clone they were developing, by putting in a FIFO.
That was it; there was no information about what sort of FIFO, or how much it helped, or
anything else. Nonetheless, Tom, normally an affable, laid-back sort, took on the wide-awake,
haunted look of a man with too much caffeine in him and no answers to show for it, as he tried
to figure out, from hopelessly thin information, what Paradise had done. Finally, he concluded
that Paradise must have put a write FIFO between the system bus and the VGA, so that when
the CPU wrote to video memory, the write immediately went into the FIFO, allowing the CPU to
keep on processing instead of stalling each time it wrote to display memory.
Tom couldn’t spare the gates or the time to do a full FIFO, but he could implement a one-deep
FIFO, allowing the CPU to get one write ahead of the VGA. He wasn’t sure how well it would
work, but it was all he could do, so he put it in and taped out the chip.
The one-deep FIFO turned out to work astonishingly well; for a time, Video Seven’s VGAs were
the fastest around, a testament to Tom’s ingenuity and creativity under pressure. However, the
truly remarkable part of this story is that Paradise’s FIFO design turned out to bear not the
slightest resemblance to Tom’s, and didn’t work as well. Paradise had stuck a read FIFO
between display memory and the video output stage of the VGA, allowing the video output to
read ahead, so that when the CPU wanted to access display memory, pixels could come from
the FIFO while the CPU was serviced immediately. That did indeed help performance--but not
as much as Tom’s write FIFO.
What we have here is as neat a parable about the nature of creative design as one could hope
to find. The scrap of news about Paradise’s chip contained almost no actual information, but it
forced Tom to push past the limits he had unconsciously set in coming up with his original
design. And, in the end, I think that the single most important element of great design, whether
it be hardware or software or any creative endeavor, is precisely what the Paradise news
triggered in Tom: The ability to detect the limits you have built into the way you think about
your design, and transcend those limits.
The problem, of course, is how to go about transcending limits you don’t even know you’ve
imposed. There’s no formula for success, but two principles can stand you in good stead:
simplify, and keep on trying new things.
Generally, if you find your code getting more complex, you’re fine-tuning a frozen design, and
it’s likely you can get more of a speed-up, with less code, by rethinking the design. A really
good design should bring with it a moment of immense satisfaction in which everything falls into
place, and you’re amazed at how little code is needed and how all the boundary cases just
work properly.
As for how to rethink the design, do it by pursuing whatever ideas occur to you, no matter how
off-the-wall they seem. Many of the truly brilliant design ideas I’ve heard over the years
sounded like nonsense at first, because they didn’t fit my preconceived view of the world.
Often, such ideas are in fact off-the-wall, but just as the news about Paradise’s chip sparked
Tom’s imagination, aggressively pursuing seemingly-outlandish ideas can open up new design
possibilities for you.
Case in point: The evolution of Quake’s 3-D graphics engine.
The toughest 3-D challenge of all
I’ve spent most of my waking hours for the last seven months working on Quake, id Software’s
successor to DOOM, and after spending the next three months in much the same way, I expect
Quake will be out as shareware around the time you read this.
In terms of graphics, Quake is to DOOM as DOOM was to its predecessor, Wolfenstein 3D.
Quake adds true, arbitrary 3-D (you can look up and down, lean, and even fall on your side),
detailed lighting and shadows, and 3-D monsters and players in place of DOOM’s sprites.
Sometime soon, I’ll talk about how all that works, but this month I want to talk about what is, in
my book, the toughest 3-D problem of all, visible surface determination (drawing the proper
surface at each pixel), and its close relative, culling (discarding non-visible polygons as quickly
as possible, a way of accelerating visible surface determination). In the interests of brevity, I’ll
use the abbreviation VSD to mean both visible surface determination and culling from now on.
Why do I think VSD is the toughest 3-D challenge? Although rasterization issues such as
texture mapping are fascinating and important, they are tasks of relatively finite scope, and are
being moved into hardware as 3-D accelerators appear; also, they only scale with increases in
screen resolution, which are relatively modest.
In contrast, VSD is an open-ended problem, and there are dozens of approaches currently in
use. Even more significantly, the performance of VSD, done in an unsophisticated fashion,
scales directly with scene complexity, which tends to increase as a square or cube function, so
this very rapidly becomes the limiting factor in doing realistic worlds. I expect VSD increasingly
to be the dominant issue in realtime PC 3-D over the next few years, as 3-D worlds become
increasingly detailed. Already, a good-sized Quake level contains on the order of 10,000
polygons, about three times as many polygons as a comparable DOOM level.
The structure of Quake levels
Before diving into VSD, let me note that each Quake level is stored as a single huge 3-D BSP
tree. This BSP tree, like any BSP, subdivides space, in this case along the planes of the
polygons. However, unlike the BSP tree I presented last time, Quake’s BSP tree does not
store polygons in the tree nodes, as part of the splitting planes, but rather in the empty
(non-solid) leaves, as shown in overhead view in Figure 1.
Figure 1: In Quake, polygons are stored in the empty leaves. Shaded areas are solid leaves (solid
volumes, such as the insides of walls).
Correct drawing order can be obtained by drawing the leaves in front-to-back or back-to-front
BSP order, again as discussed last time. Also, because BSP leaves are always convex and
the polygons are on the boundaries of the BSP leaves, facing inward, the polygons in a given
leaf can never obscure one another and can be drawn in any order. (This is a general property
of convex polyhedra.)
Culling and visible surface determination
The process of VSD would ideally work as follows. First, you would cull all polygons that are
completely outside the view frustum (view pyramid), and would clip away the irrelevant portions
of any polygons that are partially outside. Then you would draw only those pixels of each
polygon that are actually visible from the current viewpoint, as shown in overhead view in
Figure 2, wasting no time overdrawing pixels multiple times; note how little of the polygon set in
Figure 2 actually need to be drawn. Finally, in a perfect world, the tests to figure out what parts
of which polygons are visible would be free, and the processing time would be the same for all
possible viewpoints, giving the game a smooth visual flow.
Figure 2: An ideal VSD architecture would draw only visible parts of visible polygons.
As it happens, it is easy to determine which polygons are outside the frustum or partially
clipped, and it’s quite possible to figure out precisely which pixels need to be drawn. Alas, the
world is far from perfect, and those tests are far from free, so the real trick is how to accelerate
or skip various tests and still produce the desired result.
As I discussed at length last time, given a BSP, it’s easy and inexpensive to walk the world in
front-to-back or back-to-front order. The simplest VSD solution, which I in fact demonstrated
last time, is to simply walk the tree back-to-front, clip each polygon to the frustum, and draw it if
it’s facing forward and not entirely clipped (the painter’s algorithm). Is that an adequate
solution?
For relatively simple worlds, it is perfectly acceptable. It doesn’t scale very well, though. One
problem is that as you add more polygons in the world, more transformations and tests have to
be performed to cull polygons that aren’t visible; at some point, that will bog performance down
considerably.
Happily, there’s a good workaround for this particular problem. As discussed earlier, each leaf
of a BSP tree represents a convex subspace, with the nodes that bound the leaf delimiting the
space. Perhaps less obvious is that each node in a BSP tree also describes a subspace--the
subspace composed of all the node’s children, as shown in Figure 3. Another way of thinking
of this is that each node splits into two pieces the subspace created by the nodes above it in
剩余59页未读,继续阅读
laimlaim
- 粉丝: 0
- 资源: 5
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- DMN2005K-7-VB一款N-Channel沟道SOT23的MOSFET晶体管参数介绍与应用说明
- 度目视频分析盒子B1 HTTP 开发文档
- DMN100-7-F-VB一款SOT23封装N-Channel场效应MOS管
- 清华大学计算机科学与技术专业课程介绍
- stm32cubemx入门教程.pdf
- DMG9933USD-VB一款SOP8封装2个P-Channel场效应MOS管
- 2021112501-齐敬涵.ipynb
- DMG6968UQ-7-VB一款SOT23封装N-Channel场效应MOS管
- 资源名称资源名称资源名称
- DMG4407SSS-13-VB一款P-Channel沟道SOP8的MOSFET晶体管参数介绍与应用说明
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论2