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

天行健 君子當自強而不息

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>
            欧美亚洲在线视频| 亚洲免费av网站| 欧美在线视频日韩| 黄色工厂这里只有精品| 久久久av毛片精品| 久久久久久久久久码影片| 在线视频国产日韩| 亚洲国产精品久久91精品| 亚洲美女在线视频| 亚洲第一在线综合在线| 免费亚洲电影| 中国女人久久久| 亚洲在线播放电影| 伊人久久综合| 亚洲精品乱码久久久久久久久 | 欧美一级视频一区二区| 极品少妇一区二区三区精品视频 | 一区二区三区四区五区视频| 亚洲免费高清视频| 欧美一区在线视频| 伊人成人在线| 一本久久知道综合久久| 国产在线视频不卡二| 亚洲黄色一区| 国产视频一区免费看| 亚洲第一页中文字幕| 国产精品视频观看| 亚洲成人在线视频网站| 国产精品大片wwwwww| 欧美88av| 国产网站欧美日韩免费精品在线观看| 欧美激情在线有限公司| 国产区二精品视| 亚洲精品日韩欧美| 亚洲高清不卡| 欧美在线免费一级片| 在线视频精品一区| 免费在线看成人av| 久久视频一区| 国产伦精品一区二区三区视频黑人 | 欧美成人网在线| 国产精品美女www爽爽爽视频| 美女网站久久| 国产色视频一区| 在线亚洲高清视频| 亚洲伦理在线观看| 看欧美日韩国产| 久久女同互慰一区二区三区| 国产精品看片资源| 99re6热在线精品视频播放速度| 亚洲国产精品成人综合色在线婷婷 | 欧美成人免费在线观看| 国产日韩欧美精品综合| 一区二区三区精品久久久| 亚洲精选在线| 欧美电影美腿模特1979在线看| 久久在线免费观看| 黑人巨大精品欧美黑白配亚洲| 亚洲免费综合| 性欧美大战久久久久久久久| 欧美日韩在线一区二区| 亚洲精品一区二区在线| 一区二区三区不卡视频在线观看 | 国产一区二区精品久久| 午夜精品视频在线观看| 久久精品国产视频| 国产一区在线免费观看| 久久精品国产99国产精品| 久久久久久尹人网香蕉| 激情六月综合| 免费视频最近日韩| 亚洲理论在线| 午夜激情亚洲| 国产亚洲一本大道中文在线| 久久成人精品电影| 欧美大片一区二区| 日韩图片一区| 国产精品黄页免费高清在线观看| 亚洲一区日韩在线| 久久夜色精品国产亚洲aⅴ | 精品不卡在线| 美日韩在线观看| 亚洲美女淫视频| 欧美伊久线香蕉线新在线| 国产一区二区三区四区三区四| 久久婷婷国产麻豆91天堂| 亚洲国产成人tv| 亚洲欧美成人一区二区在线电影| 国产目拍亚洲精品99久久精品| 久久精品女人天堂| 亚洲精品久久久久久久久久久| 午夜精品视频在线观看一区二区| 黄色成人av网站| 欧美日韩国产123| 欧美一区二区在线免费观看 | 久久一二三四| 亚洲免费成人| 国内久久视频| 欧美日韩免费在线观看| 香蕉久久夜色精品| 亚洲国产精品久久久久秋霞影院| 午夜激情久久久| 亚洲国产精品精华液网站| 国产精品vvv| 欧美va亚洲va日韩∨a综合色| 中文精品视频| 亚洲国产精品嫩草影院| 欧美在线视频一区| 日韩午夜电影av| 国产综合久久久久久鬼色| 欧美日本国产精品| 久久精品视频在线| 亚洲一区二区三区免费视频 | 在线亚洲高清视频| 在线看不卡av| 国产日本欧美视频| 欧美日韩亚洲综合一区| 久久视频这里只有精品| 亚洲欧洲av一区二区| 亚洲日本中文字幕| 噜噜噜噜噜久久久久久91 | 在线亚洲国产精品网站| 在线看不卡av| 韩国v欧美v日本v亚洲v| 国产精品视频自拍| 欧美日韩亚洲视频| 欧美久久电影| 欧美va亚洲va香蕉在线| 久久久久久久波多野高潮日日 | 亚洲综合视频网| 日韩视频不卡| 亚洲精品久久在线| 亚洲国产成人高清精品| 欧美激情久久久久| 免费成人av在线| 麻豆91精品91久久久的内涵| 久久精品国产99国产精品| 午夜视频一区在线观看| 亚洲中字黄色| 午夜精品久久久久久久99水蜜桃| 亚洲天堂成人在线观看| 亚洲网站在线播放| 亚洲一区二区四区| 亚洲在线视频网站| 午夜精品久久久久久99热| 午夜精品一区二区三区四区| 亚洲欧美日韩在线不卡| 午夜免费电影一区在线观看| 亚洲欧洲av一区二区| 欧美一区二区三区电影在线观看| 性欧美超级视频| 久久精品人人做人人综合| 久久天堂国产精品| 欧美成人免费全部| 亚洲欧洲一区二区三区久久| 亚洲精品视频啊美女在线直播| 亚洲精品裸体| 亚洲一区精彩视频| 久久国产乱子精品免费女| 久久久成人精品| 欧美高清在线精品一区| 欧美日韩在线免费观看| 国产精品一区二区久久久| 激情久久久久| 日韩亚洲精品视频| 欧美一区二区免费| 欧美成人午夜激情在线| 亚洲精品国产系列| 亚洲欧美国产一区二区三区| 久久久久久成人| 欧美精品一区在线| 国产欧美综合一区二区三区| 在线观看一区二区视频| 亚洲午夜一区| 另类酷文…触手系列精品集v1小说| 欧美激情成人在线| 亚洲影院在线| 免费一级欧美片在线观看| 国产精品免费小视频| 亚洲二区三区四区| 午夜久久久久久| 亚洲国产精品视频| 亚洲欧美日韩爽爽影院| 免费在线国产精品| 国产色产综合色产在线视频| 日韩午夜三级在线| 久久精品女人天堂| 在线亚洲精品福利网址导航| 久久久一本精品99久久精品66| 欧美视频中文字幕| 亚洲国产欧美日韩| 欧美专区福利在线| 日韩图片一区| 欧美jizz19hd性欧美| 国产主播精品在线| 亚洲欧美日韩另类| 亚洲开发第一视频在线播放| 久久久久综合一区二区三区| 国产精品素人视频| 亚洲校园激情|