📄 engine04.shtml
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<html>
<head>
<title>Dan's Tutorials: 04 - Constructive Solid Geometry</title>
<LINK REL="stylesheet" HREF="tutorial_styles.css">
</head>
<BODY BGCOLOR="white">
<a name="top"></a>
<BR>
<CENTER>
<!--
<br>
<DIV CLASS="main1">DAN'S</div><div class="main2">Programming Tutorials</DIV>
<br>
<TABLE WIDTH="700" BORDER="0" CELLPADDING="5" CELLSPACING="0">
<TR><TD BGCOLOR="black" ALIGN="center" VALIGN="center"><FONT FACE="arial" COLOR="white"><B>
[</B></FONT>
</TD><TD BGCOLOR="black" ALIGN="center" VALIGN="center" WIDTH="100"><FONT FACE="arial" COLOR="white"><B>
<A HREF="index.shtml">news</A></B></FONT>
</TD><TD BGCOLOR="black" ALIGN="center" VALIGN="center"><FONT FACE="arial" COLOR="white"><B>
|</B></FONT>
</TD><TD BGCOLOR="black" ALIGN="center" VALIGN="center" WIDTH="100"><FONT FACE="arial" COLOR="white"><B>
tutorials</B></FONT>
</TD><TD BGCOLOR="black" ALIGN="center" VALIGN="center"><FONT FACE="arial" COLOR="white"><B>
|</B></FONT>
</TD><TD BGCOLOR="black" ALIGN="center" VALIGN="center" WIDTH="100"><FONT FACE="arial" COLOR="white"><B>
<!--A HREF="Files.shtml"--><!--files</a></B></FONT>
</TD><TD BGCOLOR="black" ALIGN="center" VALIGN="center"><FONT FACE="arial" COLOR="white"><B>
|</B></FONT>
</TD><TD BGCOLOR="black" ALIGN="center" VALIGN="center" WIDTH="100"><FONT FACE="arial" COLOR="white"><B>
<a href="ResourcesWeb.shtml">links</a></B></FONT>
</TD><TD BGCOLOR="black" ALIGN="center" VALIGN="center"><FONT FACE="arial" COLOR="white"><B>
|</B></FONT>
</TD><TD BGCOLOR="black" ALIGN="center" VALIGN="center" WIDTH="100"><FONT FACE="arial" COLOR="white"><B>
<A HREF="Contact.shtml">contact</A></B></FONT>
</TD><TD BGCOLOR="black" ALIGN="center" VALIGN="center"><FONT FACE="arial" COLOR="white"><B>
]</B></FONT>
</TD></TR>
</TABLE>
-->
<BR>
<TABLE WIDTH="700" BORDER="0" CELLSPACING="0" CELLPADDING="0" ALIGN="CENTER" VALIGN="TOP">
<tr>
<td valign="top" align="left" width="200">
<TABLE WIDTH="200" BORDER="1" CELLPADDING="3" CELLSPACING="0">
<TR><TD BGCOLOR="silver" ALIGN="center">
<FONT FACE="arial" COLOR="black"><B>Table of Contents</B></FONT>
</TD></TR>
</TABLE>
<TABLE WIDTH="200" BORDER="0" CELLPADDING="3" CELLSPACING="0"><TR><TD>
<FONT FACE="arial" SIZE="-1">
<BR>
<CENTER><B>3D</B></CENTER>
Creating a cutting-edge engine<BR>
<A HREF="Engine01.shtml">01 - Design document</A><BR>
<A HREF="Engine02.shtml">02 - Overall structure</A><BR>
<BR>
<A HREF="Engine03.shtml">03 - Binary Space Partitioning</A><BR>
<A HREF="Engine04.shtml">04 - Constrctive Solid Geometry</A><BR>
<A HREF="Engine05.shtml">05 - Portals</A><BR>
<A HREF="Engine06.shtml">06 - Possible Visible Set</A><BR>
<A HREF="Engine07.shtml">07 - Radiosity lighting</A><BR>
<!--A HREF="Engine08.shtml"-->08 - Mirrors</A><BR>
<BR>
<!--A HREF="Dictionary.shtml"-->Dictionary of 3D terms</A><BR>
<BR>
<CENTER><B>OTHER</B></CENTER>
<!--A HREF="GeneticAlgorithm.shtml"-->A Genetic Algorithm</A><BR>
<A HREF="Line01.shtml">Line drawing</a><BR>
<!--A HREF="Line02.shtml"-->Line clipping</a><BR>
<!--A HREF="Line03.shtml"-->Line antialiasing</a><BR>
<!--A HREF="Line04.shtml"-->Line thickening</a><BR>
<!--A HREF="Line05.shtml"-->Line curving</a><BR>
<br>
<A HREF="ResourcesPrint.shtml">Resources in print</A><BR>
<A HREF="ResourcesWeb.shtml">Resources on the web</A><BR>
<!--A HREF="ResourcesFiles.shtml"-->Resources to download</A><BR>
<BR>
</FONT>
</TD></TR></TABLE>
<TABLE WIDTH="200" BORDER="0" CELLPADDING="0" CELLSPACING="0">
<TR><TD HEIGHT="850"></TD></TR>
<TR><TD><FONT FACE="arial" SIZE="-2">
This is not mind control.<br>
<br>
Think about it.</FONT></TD></TR>
<TR><TD HEIGHT="1000"></TD></TR>
<TR><TD><FONT FACE="arial" SIZE="-2">
Can you believe I did all that coloring by hand? One word: Insomnia.</FONT></TD></TR>
<TR><TD HEIGHT="600"></TD></TR>
<TR><TD><FONT FACE="arial" SIZE="-2">
Of course, if your BSP is 2D you won't HAVE T-junctions. I wonder what kind of problems arise in 4D?
Ick.</FONT></TD></TR>
<TR><TD HEIGHT="1250"></TD></TR>
<TR><TD><FONT FACE="arial" SIZE="-2">
1. <i>The Cat in the Hat</i> by Dr. Seuss<br>
<img src="thecatinthehat.jpg" width="100" height="154" alt="Sam, I am." border="0"></FONT></TD></TR>
</TABLE>
</td>
<td valign="top" align="right" width="500">
<table width="475" border="0" cellpadding="3" cellspacing="0">
<tr><td bgcolor="silver">
<font face="arial"><b>04 - Constructive Solid Geometry</b></font>
</td></tr>
<tr><td><font face="arial" size="-1">
If you're reading this letter, it means that I'm dead. No, wait, I'm still typing. Silly me, this is
the part where I'm supposed to talk about Constructive Solid Geometry. Note to self: more drugs. No,
that can't be right...<i>Ahem</i> I think I'll try again.<br>
<br>
If you've made it this far I certainly hope you have a firm, two handed grip on BSPs (I reccomend a
half-nelson and scissorhold combo). Why? Because now were are getting into some seriously dark
mojo, that mysterious realm known as Constructive Solid Geometry (CSG). CSG is the process of
performing regularized boolean set operations on geometric primitives in order to obtain more
complicated models. For example, two square could be added together to form a star-like shape.
a small cube could be subtracted from a large "wall" to create a window or a door. And so on.<br>
<br>
So: we've got 2 large sets of polygons that form closed volumes and the two sets may or may not
intersect. Gee, there's got to be an easy way to figure out if and where. But what could it be...
hmm... how about... the BSP trees? Why, how convenient!<br>
<br>
I want to make sure you don't get the wrong impression: CSG does not <i>have</i> to be performed with
BSP trees. But it's a lot easier. On a mostly unrelated topic, I want to make sure you get the right
impression: at the time I'm writing these words, this page is the ONLY online source for CSG
information. I had to figure it out myself and (of course) it was only after that I met some people
who had succeeded in figuring it out. So don't thank me for putting this here, just tell all your
friends about it. (=<br>
<br>
There are four basic types of operations: addition, subtraction, intersection and difference. Given
that we have a really simple case like two squares <font color="7777aa"><B>A</b></font> and
<font color="aa7777"><B>B</b></font>:<br>
<br>
<p align="center"><img src="0401.jpg" width="100" height="100" alt="A & B" border="0"></p>
<br>
Then the four operations would have the following results (respectively):<br>
<br>
<p align="center">
<img src="0402.jpg" width="100" height="100" alt="A + B" border="0">
<img src="0403.jpg" width="100" height="100" alt="A - B" border="0">
<img src="0404.jpg" width="100" height="100" alt="A & B" border="0">
<img src="0405.jpg" width="100" height="100" alt="A ^ B" border="0"><br>
(The darkened portion remains after each operation)<br>
</p>
<br>
Now let's see if there's a pattern in these CSG operations that will help us break down the problem
into something we can code. Take a good look at addition. Notice anything special? The part that
remains is the the sum of all of <font color="7777aa"><B>A</b></font> that was outside of
<font color="aa7777"><B>B</b></font> and all of <font color="aa7777"><B>B</b></font> that was outside
of <font color="7777aa"><B>A</b></font>! So how do we code it?<br>
<ul>
<li>Take every polygon in <font color="7777aa"><B>A</b></font> and "push" it through the BSP tree of
<font color="aa7777"><B>B</b></font>.
<li>If a polygon being pushed through the tree is coplanar with a node plane, test the polygon normal
so see if it matches the plane normal. If they match, push it down the inside. If they don't, push
it down the outside.
<li>Any polygon "remnants" that end on an outside leaf are stored.
<li>Any polygons remnants that end on an inside leaf are deleted.
<li>Repeat the process with every polygon in <font color="aa7777"><B>B</b></font> against the BSP
tree <font color="7777aa"><B>A</b></font>.
</ul>
Similar patterns can be found for the other 3 operations:<br>
<ul>
<li><b>Subtraction</b>: All <font color="aa7777"><B>B</b></font> inside
<font color="7777aa"><B>A</b></font> FLIPPED and all <font color="7777aa"><B>A</b></font> outside
<font color="aa7777"><B>B</b></font>.
<li><b>Intersecion</b>: All <font color="7777aa"><B>A</b></font> inside
<font color="aa7777"><B>B</b></font> and all <font color="aa7777"><B>B</b></font> inside
<font color="7777aa"><B>A</b></font>.
<li><b>Difference</b>: <font color="7777aa"><B>A</b></font> subtract
<font color="aa7777"><B>B</b></font> and <font color="aa7777"><B>B</b></font> subtract
<font color="7777aa"><B>A</b></font>.
</ul>
<hr>
Note: When I say 'flipped' I mean that the polygons have to have their normals inverted and (unless you
have some really fancy engine) the polygons' point order will have to be inverted.<br>
<hr>
<br>
Ok everyone, take a minute to let that sink in, work it on a piece of paper until you believe what I'm
saying and <b>do not</b> go further until you are sure you understand what I just wrote or you will
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -