📄 progbintri.htm
字号:
<!--Header-->
<HTML>
<HEAD>
<TITLE>GPMega - Advanced Section - Binary Triangle Trees and Terrain Tessellation</TITLE>
<META NAME="DESCRIPTION" CONTENT="In this informative article, Seumas goes into the uses of Binary Triangle Trees in Terrain Rendering. He introduces the BinTriTree as a data structure and presents tips on making use of it by converting a binary triangle to a tree. Code on computing variance for a terrain is also included.">
</HEAD>
<BODY BGCOLOR=#000000 TEXT=#FFFFFF LINK=#00FF00 VLINK=#00FF00 ALINK=#0000FF>
<!--End Header-->
<!--Advertiser-->
<CENTER>
<TABLE>
<TR>
<TD>
<A HREF="http://www.ugo.com/">
<IMG SRC="/GPMega/ugologo120.gif" BORDER=0 WIDTH=120 HEIGHT=60></A>
</TD>
<TD>
<IMG SRC="/GPMega/sponsored.gif" WIDTH=468 HEIGHT=10><br><br>
<SCRIPT LANGUAGE= "JavaScript">
<!--
var now = new Date();
var random_num = now.getSeconds();
document.write("<A HREF='http://www.ugo.net/RealMedia/ads/click_nx.cgi/www.perplexed.com/GPMega/advanced/progbintri.htm/" + random_num + "/@Top'>");
document.write("<IMG SRC='http://www.ugo.net/RealMedia/ads/adstream_nx.cgi/www.perplexed.com/GPMega/advanced/progbintri.htm/" + random_num + "/@Top' BORDER='0' WIDTH='468' HEIGHT='60'></A>");
//-->
</SCRIPT>
</TD>
</TR>
</TABLE>
</CENTER>
<!--End Advertiser-->
<!--Splitter-->
<BR>
<!--End Splitter-->
<!--Body-->
<FONT SIZE=2 FACE=Helvetica>
<STRONG>
<!--Top Navigation-->
<A NAME="top"></A>
<CENTER>
<TABLE WIDTH=75%>
<TR VALIGN=MIDDLE>
<TD ALIGN=LEFT>
<IMG SRC="gradsplit2.jpg" WIDTH=100% HEIGHT=1><BR><BR>
<A HREF="http://www.perplexed.com/GPMega/"><IMG SRC="logo.jpg" BORDER=0 ALT="Home" WIDTH=80 HEIGHT=47 ALIGN=CENTER></A>
<FONT COLOR=#666666 FACE=HELVETICA SIZE=-1><I>
This Article Is Taken From <A HREF="http://www.perplexed.com/GPMega/">The Game Programming MegaSite</A>, A Definitive Resource For Game Developers!
</I></FONT><BR>
<IMG SRC="gradsplit2.jpg" WIDTH=100% HEIGHT=1>
</TD>
</TR>
</TABLE>
</CENTER>
<BR><!--End Top Navigation-->
<!--Title-->
<H3 ALIGN=CENTER><font color="#FFFA00">B</font><font color="#FFF500">i</font><font color="#FFF000">n</font><font color="#FFEB00">a</font><font color="#FFE600">r</font><font color="#FFE100">y</font><font color="#FFDC00"> </font><font color="#FFD700">T</font><font color="#FFD200">r</font><font color="#FFCD00">i</font><font color="#FFC800">a</font><font color="#FFC300">n</font><font color="#FFBE00">g</font><font color="#FFB900">l</font><font color="#FFB400">e</font><font color="#FFAF00"> </font><font color="#FFAA00">T</font><font color="#FFA500">r</font><font color="#FFA000">e</font><font color="#FF9B00">e</font><font color="#FF9600">s</font><font color="#FF9100"> </font><font color="#FF8C00">a</font><font color="#FF8700">n</font><font color="#FF8200">d</font><font color="#FF7D00"> </font><font color="#FF7800">T</font><font color="#FF7300">e</font><font color="#FF6E00">r</font><font color="#FF6900">r</font><font color="#FF6400">a</font><font color="#FF5F00">i</font><font color="#FF5A00">n</font><font color="#FF5500"> </font><font color="#FF5000">T</font><font color="#FF4B00">e</font><font color="#FF4600">s</font><font color="#FF4100">s</font><font color="#FF3C00">e</font><font color="#FF3700">l</font><font color="#FF3200">l</font><font color="#FF2D00">a</font><font color="#FF2800">t</font><font color="#FF2300">i</font><font color="#FF1E00">o</font><font color="#FF1900">n</font><BR><FONT SIZE=-2>By: <A HREF="mailto:longbow@sympatico.ca">Seumas McNally</A></FONT></H3>
<!--End Title-->
<P><FONT SIZE=-2><I>Courtesy Of <A HREF="http://www.LongbowDigitalArts.com/">Longbow Digital Arts</A></I></FONT>
<P>A Binary Triangle Tree
(bintritree) is a very interesting data structure. They combine the
simplicity of a Binary Tree (each node having only two descendants) with
the 2-dimensional area covering properties of a Quad-Tree. You also get
the advantage of all areas being right isosceles triangles (a 90 degree
angle connecting two equal sides) that are perfect for throwing at a 3D
rendering API, and will never, ever develop cracks or T-junctions. This
makes BinTriTrees especially handy for tessellating regular arrays (e.g.
height fields) to non-regular triangle densities, so that e.g. close to
the viewer you tessellate to a high density, and far from the viewer you
use a very low triangle density.
<P>Normally you think of the
triangles in a BinTriTree with the hypotenuse down, and with two children,
a Left Child and a Right Child. Look at the simple BinTriTree represented
below. The root triangle is A, with a Right Child B, and a Left Child C. C
has a Right Child D, and a Left Child E. This subdivision can
theoretically go on forever, though you usually stop once you've reached
the granularity of your regular array (though you can go finer using
algorithmic sampling).
<P><IMG src="bintri2.gif">
<P>In order to arbitrarily refine a
particular triangle in the tree without causing cracks or T-junctions, you
also need to store three more pointers in each BinTriTree node (or array
indecise, depending on how you pool your node structures), a Left Neighbor
Pointer, a Right Neighbor Pointer, and a Bottom Neighbor Pointer. The Left
and Right Neighbors point to the triangles that are on the left and right
with the hypotenuse down, and the Bottom Neighbor is the triangle that
meets the hypotenuse. Note that Neighbor Pointers of lowest-level nodes
should always point to other lowest-level nodes; if a neighboring triangle
is split, all neighbor pointers should be updated to point to the new
children.
<P>Here's psuedo code for splitting a binary triangle in a tree:
<BLOCKQUOTE>
<PRE><FONT SIZE=2 COLOR=RED>
Split(BinTri *tri){
if tri->BottomNeighbor is valid {
if tri->BottomNeighbor->BottomNeighbor != tri {
Split(tri->BottomNeighbor)
}
Split2(tri)
Split2(tri->BottomNeighbor)
tri->LeftChild->RightNeighbor = tri->BottomNeighbor->RightChild
tri->RightChild->LeftNeighbor = tri->BottomNeighbor->LeftChild
tri->BottomNeighbor->LeftChild->RightNeighbor = tri->RightChild
tri->BottomNeighbor->RightChild->LeftNeighbor = tri->LeftChild
}else{
Split2(tri)
tri->LeftChild->RightNeighbor = 0;
tri->RightChild->LeftNeighbor = 0;
}
}
Split2(tri){
tri->LeftChild = AllocateBinTri();
tri->RightChild = AllocateBinTri();
tri->LeftChild->LeftNeighbor = tri->RightChild
tri->RightChild->RightNeighbor = tri->LeftChild
tri->LeftChild->BottomNeighbor = tri->LeftNeighbor
if tri->LeftNeighbor is valid {
if tri->LeftNeighbor->BottomNeighbor == tri {
tri->LeftNeighbor->BottomNeighbor = tri->LeftChild
}else{
if tri->LeftNeighbor->LeftNeighbor == tri {
tri->LeftNeighbor->LeftNeighbor = tri->LeftChild
}else{
tri->LeftNeighbor->RightNeighbor = tri->LeftChild
}
}
}
tri->RightChild->BottomNeighbor = tri->RightNeighbor
if tri->RightNeighbor is valid {
if tri->RightNeighbor->BottomNeighbor == tri {
tri->RightNeighbor->BottomNeighbor = tri->RightChild
}else{
if tri->RightNeighbor->RightNeighbor == tri {
tri->RightNeighbor->RightNeighbor = tri->RightChild
}else{
tri->RightNeighbor->LeftNeighbor = tri->RightChild
}
}
}
tri->LeftChild->LeftChild = 0
tri->LeftChild->RightChild = 0
tri->RightChild->LeftChild = 0
tri->RightChild->RightChild = 0
}
</FONT></PRE>
</BLOCKQUOTE>
<P>As you can see from the steps
above, when a triangle to be split doesn't share a hypotenuse with its
bottom neighbor, the bottom neighbor is forced to split first. Since
bottom neighbors will always be either at the same level or one level
higher, it will only ever need to be forced to split once, before it is
split normally in combination with the original triangle. Two triangles
that share a hypotenuse are referred to as a Diamond, and happen to form a
perfect square, which comes in handy when representing areas such as
square 2D arrays using BinTriTrees. To encompass a square area, you will
actually need two seperate Binary Triangle Trees in a Diamond formation.
As long as their Neighbor pointers are properly connected to each other,
it won't matter that they are two seperate trees descending from two
seperate root nodes. You can use this fact to easily create multiple
linked sets of trees representing large tiles of terrain data.
<P><IMG src="bintri1.gif">
<P>In the example above, if
triangle A splits, the Diamond formed by A and B will be easily split.
However if triangle 1 is asked to split, triangle 2 will need to be split
first, so that its Right Child forms a diamond with 1, and then the two
triangles in the Diamond can be split. Splitting a triangle deep in a
BinTriTree can sometimes cause a recursive chain reaction of many forced
splits, but they are required to keep the tree in order.
<P>With the fundamental building
block of Binary Triangle Trees laid bare, it's easy to see how it can be
used for the real time display of highly detailed terrain. When
tessellating a regular height array into triangles using a BinTriTree,
there are a number of criteria that can be used to decide when a triangle
should be split further, and when it should be left as-is:
<UL>
<LI>If the triangle is in the view frustum.
<LI>If the pre-computed variance of the actual height values within the triangle's
area vs. the flat plane of the triangle (as scaled by the distance from
the camera) is greater than some defined maximum-variance quality setting.
(This is the most critical one for variable frequency terrain.)
<LI>If the triangle is facing the viewer.
<LI>If the triangle is close to an important object that is resting on the ground.
</UL>
<P>Pre-computing
"variance" is easy, and can be handled very well using a
recursive function. The only sticky issue is how to store the variance
tree. If your terrain is small, you may be able to store a tree of
variance values all the way down to the lowest level representable.
However with even reasonably large terrain, storing all variance values
becomes prohibitively expensive, and you have to cap the variance tree at
some level higher than the lowest. I personally use a byte-based implicit
tree, which is essentially a large array of bytes, with one byte for each
triangle in a BinTriTree down to a certian level, with that byte holding
the "variance" for that triangle. The following pseudo code
should calculate the variances for a tree, with storing variances left as
an excercise for the programmer. By adding a check to see if each triangle
is within a "dirty rectangle" before recursing further, you can
easily recalculate variances for just a small portion of a map, such as
when a crater is blasted in real time.
<BLOCKQUOTE>
<PRE><FONT SIZE=2 COLOR=RED>
int CalcVariance(tri){
int RealHeight = the map height at the middle of the hypotenuse
int AvgHeight = the average of the real heights at the two ends of the hypot
int v = abs( RealHeight - AvgHeight )
if tri->LeftChild is valid {
v = max( v, CalcVariance(tri->LeftChild) )
}
if tri->RightChild is valid {
v = max( v, CalcVariance(tri->RightChild) )
}
return v
}
</FONT></PRE>
</BLOCKQUOTE>
<P>For more information on how to
use Binary Triangle Trees for real time variable Level of Detail terrain
rendering, have a look at the <A href="http://www.llnl.gov/graphics/ROAM/"
target=_blank>ROAM paper</A>. It's only available as PDF or PostScript,
but it's well worth printing out and reading a few times over.
<P>Another paper to check out is
Hugues Hoppe's "Smooth view-dependent level-of-detail control and its
application to terrain rendering", available at his <A
href="http://research.microsoft.com/~hoppe/" target=_blank>home page</A>
at Microsoft. It takes a different look at view-dependant LOD rendering,
with an algorithm that should work great for caves and overhangs, but
lacking the simplicity and mutability (real time craters etc.) of methods
based on a regular height array.
<P><I>This Document Copyright 1998-1999 by Seumas McNally.<br>
No reproduction may be made without the author's written consent.</I></P>
<!--Bottom Navigation-->
<A NAME="bottom"></A>
<!--End Bottom Navigation-->
</STRONG>
</FONT>
<!--End Body-->
<!--Bottom-->
<BR>
<IMG SRC="gradbar.jpg">
<BR>
<FONT SIZE=2 COLOR=#8B8B8B FACE=Helvetica>
<I><font color="#FBFBFB">T</font><font color="#F7F7F7">h</font><font color="#F3F3F3">e</font><font color="#EFEFEF"> </font><font color="#EBEBEB">G</font><font color="#E7E7E7">a</font><font color="#E3E3E3">m</font><font color="#DFDFDF">e</font><font color="#DBDBDB"> </font><font color="#D7D7D7">P</font><font color="#D3D3D3">r</font><font color="#CFCFCF">o</font><font color="#CBCBCB">g</font><font color="#C7C7C7">r</font><font color="#C3C3C3">a</font><font color="#BFBFBF">m</font><font color="#BBBBBB">m</font><font color="#B7B7B7">i</font><font color="#B3B3B3">n</font><font color="#AFAFAF">g</font><font color="#ABABAB"> </font><font color="#A7A7A7">M</font><font color="#A3A3A3">e</font><font color="#9F9F9F">g</font><font color="#9B9B9B">a</font><font color="#979797">S</font><font color="#939393">i</font><font color="#8F8F8F">t</font><font color="#8B8B8B">e</font> - ⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -