青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

天行健 君子當自強而不息

3D幾何圖元(3)

新建網頁 1


矩形邊界框

另一種常見的用來界定物體的幾何圖元是矩形邊界框,矩形邊界框可以是與軸對齊的或是任意方向的。軸對齊矩形邊界框有一個限制,就是它的邊必須垂直于坐標軸??s寫AABB常用來表示axially aligned bounding box(軸對齊矩形邊界框),OBB用來表示oriented bounding box(方向矩形邊界框)。軸對齊矩形邊界框不僅容易創建,而且易于使用。

一個3D的AABB就是一個簡單的六面體,每一邊都平行于一個坐標平面。矩形邊界框不一定是立方體,它的長、寬、高可以彼此不同。在圖12.10中,畫出了一些簡單的3D物體和它們的AABB

 

AABB的表達方法

先介紹AABB的一些重要性質和引用這些值時所用到的記法。AABB內的點滿足下列等式:

xmin x xmax

ymin y ymax

zmin z zmax

特別重要的兩個點為:

pmin = [xmin   ymin   zmin ]

pmax = [xmax   ymax   zmax ]

中心點c為:

c = (pmin + pmax) /2

"尺寸向量"s是從pmin指向pmax的向量,包含了矩形邊界的長、寬、高:

s = pmax - pmin

還可以求出矩形邊界框的"半徑向量"r,它是從中心指向pmax的向量:

r = pmax - c = s/2

明確地定義一個AABB只需要pmin、pmax、c、s、r這5個向量中的兩個(除sr不能配對外,它們中的任意兩個都可配對)。在一些情況下,某些配對形式比其他的會更有用。我們建議用pminpmax表示一個邊界框,因為實際應用中,使用它們的頻率遠高于c、s、r。當然,由pminpmax計算其余三個中的任意一個都是很容易的。

在我們的C++代碼中,使用下面的類表示AABB,這是一個縮略的代碼清單。

    #ifndef AABB3_H
   
#define AABB3_H
   
    #include "vector3.h"
   
   
class cMatrix4x3;
   
   
    //---------------------------------------------------------------------------
    // Implement a 3D axially aligned bounding box
    //---------------------------------------------------------------------------
   
class cAABB3
    {
   
public:
        cVector3 min, max;
   
   
public:
        
// query for dimentions
   
    cVector3 size() const        { return max - min; }
        
float     x_size()            { return max.x - min.x; }
        
float     y_size()            { return max.y - min.y; }
        
float     z_size()            { return max.z - min.z; }
        cVector3 center() 
const        { return (min + max) * 0.5f; }
   
        
// fetch one of the eight corner points
   
    cVector3 corner(int i) const;
   
        
// "Empty" the box, by setting the values to really large/small numbers.
   
    void empty();
   
        
// add a point to the box
   
    void add(const cVector3& p);
   
        
// add an AABB to the box
   
    void add(const cAABB3& box);
   
        
// return true if the box is empty
   
    bool is_empty() const;
   
        
// return true if the box contains a point
   
    bool contains(const cVector3& p) const;
   
        
// transform the box and compute the new AABB
   
    void set_to_transformed_box(const cAABB3& box, const cMatrix4x3& m);
   
        
// return the clostet point on this box to another point
   
    cVector3 clostet_point_to(const cVector3& p) const;
    };
   
   
#endif

計算AABB

計算一個頂點集合的AABB是非常簡單的,先將最小值和最大值設為"正負無窮大"或任何比實際中用到的數都大或小得多的數。接著,遍歷全部點,并擴展邊界框直到它包含所有點為止。

我們在cAABB類中引入了兩個輔助函數,第一個函數負責"清空"AABB

    //---------------------------------------------------------------------------
    // "Empty" the box, by setting the values to really large/small numbers.
    //---------------------------------------------------------------------------
   
void cAABB3::empty() 
    {
        
const float big_number = 1e37f;
   
        min.x = min.y = min.z = big_number;
        max.x = max.y = max.z = -big_number;
    }

第二個函數將單個點""到AABB中,并在必要的時候擴展AABB以包含每個點:

    //---------------------------------------------------------------------------
    // Add a point to the box
    //---------------------------------------------------------------------------
   
void cAABB3::add(const cVector3& p)
    {
        
// expand the box as necessary to contain the point
   
    if(p.x < min.x)        min.x = p.x;
        
if(p.x > max.x)        max.x = p.x;
        
if(p.y < min.y)        min.y = p.y;
        
if(p.y > max.y)        max.y = p.y;
        
if(p.z < min.z)        min.z = p.z;
        
if(p.z > max.z)        max.z = p.z;
    }

現在,從一個點集創建矩形邊界框,可以使用下面的代碼:

    Listing 12.1: Computing the AABB for a set of points
   
   
// Our list of points
   
const int n;
    Vector3 list[n];
   
   
// First, empty the box
   
AABB3 box;
    box.empty();
   
   
// Add each point into the box
   
for (int i = 0 ; i < n ; ++i) 
      box.add(list[i]);

取得AABB的頂點:

    //--------------------------------------------------------------------------------------
    // Return one of the 8 corner points.  The points are numbered as follows:
    //
    //            6                                7
    //              ------------------------------
    //             /|                           /|
    //            / |                          / |
    //           /  |                         /  |
    //          /   |                        /   |
    //         /    |                       /    |
    //        /     |                      /     |
    //       /      |                     /      |
    //      /       |                    /       |
    //     /        |                   /        |
    //  2 /         |                3 /         |
    //   /----------------------------/          |
    //   |          |                 |          |
    //   |          |                 |          |      +Y
    //   |        4 |                 |          | 
    //   |          |-----------------|----------|      |
    //   |         /                  |         /  5    |
    //   |        /                   |        /        |       +Z
    //   |       /                    |       /         |
    //   |      /                     |      /          |     /
    //   |     /                      |     /           |    /
    //   |    /                       |    /            |   /
    //   |   /                        |   /             |  /
    //   |  /                         |  /              | /
    //   | /                          | /               |/
    //   |/                           |/                ----------------- +X
    //   ------------------------------
    //  0                              1
    //
    // Bit 0 selects min.x vs. max.x
    // Bit 1 selects min.y vs. max.y
    // Bit 2 selects min.z vs. max.z
    //--------------------------------------------------------------------------------------
   
cVector3 cAABB3::corner(int i) const
    {
        assert(i >= 0 && i <= 7);    
// make sure index is in range
   

        
return cVector3((i & 1) ? max.x : min.x,
                        (i & 2) ? max.y : min.y,
                        (i & 4) ? max.z : min.z);
    }

其他的相關函數,具體功能詳見注釋:

    //---------------------------------------------------------------------------
    // Add an AABB to the box
    //---------------------------------------------------------------------------
   
void cAABB3::add(const cAABB3& box)
    {
        
// expand the box as necessary
   
    if(box.min.x < min.x)    min.x = box.min.x;
        
if(box.min.x > max.x)    max.x = box.min.x;
        
if(box.min.y < min.y)    min.y = box.min.y;
        
if(box.min.y > max.y)    max.y = box.min.y;
        
if(box.min.z < min.z)    min.z = box.min.z;
        
if(box.min.z > max.z)    max.z = box.min.z;
    }
   
   
//---------------------------------------------------------------------------
    // Return true if the box is empty
    //---------------------------------------------------------------------------
   
bool cAABB3::is_empty() const
    {
        
// check if we're inverted on any axis
   
    return (min.x > max.x) || (min.y > max.y) || (min.z > max.z);
    }
   
   
//---------------------------------------------------------------------------
    // Return true if the box contains a point
    //---------------------------------------------------------------------------
   
bool cAABB3::contains(const cVector3& p) const
    {
        
// check for overlap on each axis
   
    return (p.x >= min.x) && (p.x <= max.x) &&
               (p.y >= min.y) && (p.y <= max.y) &&
               (p.z >= min.z) && (p.z <= max.z);
    }
   
   
//---------------------------------------------------------------------------
    // return the closest point on this box to another point
    //---------------------------------------------------------------------------
   
cVector3 cAABB3::clostet_point_to(const cVector3& p) const
    {
        
// "push" p into the box, on each dimension.
   

        cVector3 r;
   
        
if(p.x < min.x)
            r.x = min.x;
        
else if(p.x > max.x)
            r.x = max.x;
        
else
            r.x = p.x;
   
        
if(p.y < min.y) 
            r.y = min.y;
        
else if(p.y > max.y) 
            r.y = max.y;
        
else
            r.y = p.y;
   
        
if(p.z < min.z)
            r.z = min.z;
        
else if(p.z > max.z)
            r.z = max.z;
        
else
            r.z = p.z;
   
        
return r;
    }

AABB與邊界球

很多情況下,AABB比邊界球更適合于做定界球:

(1)計算一個點集的AABB,在編程上更容易實現,并能在較短的時間內完成。計算邊界球則困難得多。

(2)對實際世界里的許多物體,AABB提供了一種"更緊湊"的邊界。當然,對于某些物體,邊界球更好(設想一個本身就是球形的物體)。在極端情況下,AABB的體積可能僅相當于邊界球體積的1/2,大部分時候邊界球的體積會比矩形框的體積大得多,比較一下電線桿的邊界球和AABB就知道了。圖12.11所示為不同物體的AABB與邊界球的比較。

邊界球的根本問題是它的形狀只有一個自由度----半徑,而AABB卻有三個自由度----長、寬、高。因此,它可以調節這些自由度以適應不同物體。對圖12.11中的大部分物體,除了右上角的星形體外,AABB都比邊界球小。對這顆星,邊界球也僅比AABB略小一些。通過圖12.11,我們可以注意到AABB對物體的方向很敏感。比較下面兩支槍的AABB,圖中槍的大小都是相同的,只是方向不同而已;還應注意到在這一情況下邊界球大小相同,因為邊界球對物體方向不敏感。

 

變換AABB

當物體在虛擬世界中移動時,它的AABB也需要隨之移動。此時我們有兩個選擇----用變換后的物體來重新計算AABB,或者對AABB做和物體同樣的變換。所得到的結果不一定是軸對齊的(如果物體旋轉),也不一定是盒狀的(如果物體發生了扭曲)。不過,通過"變換后的AABB"進行計算要比通過"經過變換后的物體"計算AABB快得多,因為AABB只有8個頂點。

通過"變換后的AABB"計算不能只是簡單地變換8個頂點,也不能通過轉換原pminpmax來得到新的pminpmax ----這樣可能會導致xmin > xmax。為了計算新的AABB,必須先變換8個頂點,再從這8個頂點中計算一個新的AABB。

根據變換的不同,這種方法可能使新邊界框比原邊界框大許多。例如,在2D中,45度的旋轉會大大增加邊界框的尺寸,如圖12.12所示:

比較圖12.12中原AABB(灰色框)和新AABB(右邊較大的方框),它是通過旋轉后的AABB計算的,新AABB幾乎是原來的兩倍。注意,如果從旋轉后的物體而不是通過旋轉后的AABB來計算新AABB,它的大小將和原來的AABB相同。

可以利用AABB的結構來加快新的AABB的計算速度,而不必先變換8個頂點,再從這8個頂點中計算新AABB。

讓我們簡單回顧一下3x3矩陣變換一個3D點的過程:

設原邊界框為xmin,xmax,ymin...,新邊界框計算將得到x'minx'max,y'min...?,F在我們的任務就是想辦法加快計算x'min的速度,換句話說,我們希望找到m11x+m21y+m31z的最小值,其中[x, y, z]是原8個頂點中的任意一個,我們所要做的就是找出這些點經過變換后誰的x坐標最小。看第一個乘積:m11x,為了最小化乘積,必須決定是用xmin還是xmax來代換其中的x。顯然,如果m11>0,用xmin能得到最小化乘積;如果m11<0,則用xmax能得到最小化乘積。比較方便的是,不管xminxmax中哪個被用來計算xmin,都可以用另外一個來計算xmax??梢詫仃?個元素中的每個都應用這個計算過程,如下列代碼所示:

    //---------------------------------------------------------------------------
    // Transform the box and compute the new AABB.  Remember, this always
    // results in an AABB that is at least as big as the origin, and may be
    // considerably bigger.
    //---------------------------------------------------------------------------
   
void cAABB3::set_to_transformed_box(const cAABB3& box, const cMatrix4x3& m)
    {
        
// if we're empty, then bail.
   
    if(box.is_empty())
        {
            empty();
            
return;
        }
   
        
// start with the translation portion
   
    min = max = get_translation(m);
   
        
// examine each of the 9 matrix elements and compute the new AABB
   

        
if(m.m11 > 0.0f)
        {
            min.x += m.m11 * box.min.x;
            max.x += m.m11 * box.max.x;
        }
        
else
        {
            min.x += m.m11 * box.max.x;
            max.x += m.m11 * box.min.x;
        }
   
        
if(m.m21 > 0.0f)
        {
            min.x += m.m21 * box.min.y; 
            max.x += m.m21 * box.max.y;
        }
        
else
        {
            min.x += m.m21 * box.max.y; 
            max.x += m.m21 * box.min.y;
        }
   
        
if(m.m31 > 0.0f)
        {
            min.x += m.m31 * box.min.z; 
            max.x += m.m31 * box.max.z;
        }
        
else
        {
            min.x += m.m31 * box.max.z; 
            max.x += m.m31 * box.min.z;
        }
   
        
if(m.m12 > 0.0f) 
        {
            min.y += m.m12 * box.min.x; 
            max.y += m.m12 * box.max.x;
        }
        
else
        {
            min.y += m.m12 * box.max.x; 
            max.y += m.m12 * box.min.x;
        }
   
        
if(m.m22 > 0.0f)
        {
            min.y += m.m22 * box.min.y; 
            max.y += m.m22 * box.max.y;
        }
        
else
        {
            min.y += m.m22 * box.max.y; 
            max.y += m.m22 * box.min.y;
        }
   
        
if(m.m32 > 0.0f)
        {
            min.y += m.m32 * box.min.z; 
            max.y += m.m32 * box.max.z;
        }
        
else
        {
            min.y += m.m32 * box.max.z; 
            max.y += m.m32 * box.min.z;
        }
   
        
if(m.m13 > 0.0f) 
        {
            min.z += m.m13 * box.min.x; 
            max.z += m.m13 * box.max.x;
        }
        
else
        {
            min.z += m.m13 * box.max.x; 
            max.z += m.m13 * box.min.x;
        }
   
        
if(m.m23 > 0.0f)
        {
            min.z += m.m23 * box.min.y; 
            max.z += m.m23 * box.max.y;
        }
        
else
        {
            min.z += m.m23 * box.max.y; 
            max.z += m.m23 * box.min.y;
        }
   
        
if(m.m33 > 0.0f)
        {
            min.z += m.m33 * box.min.z; 
            max.z += m.m33 * box.max.z;
        }
        
else
        {
            min.z += m.m33 * box.max.z; 
            max.z += m.m33 * box.min.z;
        }
    }

posted on 2008-02-23 12:25 lovedday 閱讀(2651) 評論(0)  編輯 收藏 引用

公告

導航

統計

常用鏈接

隨筆分類(178)

3D游戲編程相關鏈接

搜索

最新評論

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            欧美α欧美αv大片| 欧美大片免费久久精品三p| 欧美一区二区三区精品| 亚洲精品午夜| 欧美一区二区三区免费观看| 99国产精品久久久久老师| 久久精品99无色码中文字幕| 亚洲国产精品久久| 亚洲一区二区在线看| 一本一本久久a久久精品综合麻豆| 性做久久久久久久免费看| 亚洲网站在线播放| 欧美激情五月| 免费一级欧美在线大片| 国产一区二区三区丝袜| 亚洲综合视频一区| 亚洲经典在线| 鲁鲁狠狠狠7777一区二区| 久久久久国产一区二区三区四区 | 免费看av成人| 久久精品视频导航| 国产精品久久久久久久久久尿| 亚洲精品1区| 在线日韩日本国产亚洲| 亚洲一区二区影院| 亚洲一区尤物| 国产精品s色| 9i看片成人免费高清| 国产精品99久久不卡二区| 欧美日韩国产系列| 亚洲成在人线av| 亚洲激情偷拍| 欧美va亚洲va香蕉在线| 欧美国产国产综合| 午夜视频在线观看一区二区三区| 99精品视频一区| 欧美精品日韩三级| 亚洲老司机av| 午夜久久福利| 国产亚洲综合精品| 久久精品国产第一区二区三区| 久久精品一区蜜桃臀影院| 国产日韩一区二区三区在线| 欧美一区亚洲| 米奇777在线欧美播放| 亚洲大片免费看| 欧美一区二区三区久久精品茉莉花 | 亚洲人久久久| 欧美日韩精品免费| 中文av一区特黄| 亚洲欧美区自拍先锋| 国产日产精品一区二区三区四区的观看方式 | 国产欧美精品一区| 欧美在线视频一区二区| 欧美a一区二区| 日韩视频免费观看高清完整版| 欧美三区免费完整视频在线观看| 亚洲一区二区三区激情| 久久婷婷成人综合色| 亚洲精品日韩在线观看| 国产精品久久二区| 久久久精品一区二区三区| 91久久精品国产91久久性色tv| 亚洲尤物在线| 国产伦一区二区三区色一情| 久久午夜av| 一本色道久久88精品综合| 亚洲欧美一区二区在线观看| 亚洲国产成人不卡| 欧美久久在线| 久久国产99| 亚洲美女av网站| 久久蜜桃资源一区二区老牛| 99精品久久久| 黄色成人免费网站| 欧美色综合天天久久综合精品| 亚欧成人在线| 日韩西西人体444www| 裸体一区二区| 中文一区在线| 亚洲韩国精品一区| 国产主播喷水一区二区| 欧美调教vk| 免费欧美网站| 亚洲影视中文字幕| 精品成人在线视频| 国产乱人伦精品一区二区 | 午夜在线精品| 99在线热播精品免费| 欧美成人69av| 久久先锋影音| 亚洲免费不卡| 亚洲国产精品热久久| 国产综合久久久久影院| 国产精品成人一区二区| 欧美成人亚洲成人日韩成人| 亚洲午夜性刺激影院| 亚洲精品九九| 亚洲激情成人| 一区二区三区免费在线观看| 在线观看日韩精品| 亚洲成色精品| 亚洲精品久久久久中文字幕欢迎你| 在线看视频不卡| 亚洲国产精品毛片| 亚洲人成在线播放| 99re6热在线精品视频播放速度| 亚洲日韩中文字幕在线播放| 亚洲每日更新| 亚洲午夜影视影院在线观看| 亚洲淫片在线视频| 久久国产精品99精品国产| 久久国产综合精品| 久久亚洲影院| 亚洲电影在线观看| 日韩视频免费在线| 亚洲一区二区视频在线观看| 欧美一区二区日韩| 快射av在线播放一区| 欧美精品久久99久久在免费线| 欧美日韩国产麻豆| 国产精品性做久久久久久| 国产精品久久91| 激情av一区| 一片黄亚洲嫩模| 久久精品日韩欧美| 欧美韩日精品| 亚洲一区尤物| 久久综合久久综合久久综合| 欧美日韩ab片| 国产亚洲a∨片在线观看| 亚洲电影下载| 亚洲一区在线免费| 毛片精品免费在线观看| 亚洲精品资源| 欧美在线观看网址综合| 欧美激情麻豆| 国模吧视频一区| 亚洲免费电影在线| 久久久亚洲综合| 亚洲美女色禁图| 欧美专区第一页| 欧美日韩中文字幕精品| 好吊色欧美一区二区三区视频| 亚洲精品日本| 久久免费国产| 宅男噜噜噜66一区二区| 乱中年女人伦av一区二区| 欧美午夜精品一区| 亚洲国内自拍| 久久久久久久久久久久久女国产乱 | 久久狠狠亚洲综合| 亚洲精品视频啊美女在线直播| 欧美在线观看一区二区三区| 欧美日韩国产色视频| 亚洲福利视频免费观看| 欧美在线视频日韩| 亚洲看片免费| 蜜臀久久99精品久久久画质超高清 | 久久一二三四| 亚洲影院在线观看| 欧美视频精品在线观看| 亚洲激情视频在线| 久久一二三四| 欧美一区二区视频在线观看| 国产精品高清在线| 一区二区欧美视频| 亚洲国产色一区| 久久久亚洲欧洲日产国码αv| 国产精品一区二区a| 中日韩美女免费视频网站在线观看| 欧美xxx成人| 久久综合中文| 在线观看日韩精品| 久久亚洲一区二区三区四区| 欧美一级精品大片| 国产精品一二三四| 午夜精品久久| 亚洲一级片在线看| 国产精品久久9| 午夜影院日韩| 亚洲影视在线| 国产精品日韩精品欧美在线 | 久久人91精品久久久久久不卡| 亚洲男同1069视频| 国产精品大片| 午夜精品久久一牛影视| 日韩午夜在线视频| 国产精品成人观看视频国产奇米| 一本色道久久综合狠狠躁的推荐| 亚洲国产一区二区三区高清| 欧美大片国产精品| 日韩视频在线一区二区| 亚洲精品在线免费观看视频| 欧美日韩一区在线播放| 亚洲一二三区精品| 亚洲免费一区二区| 国语自产精品视频在线看| 久久综合色一综合色88| 免费观看成人|