隨筆-38 評論-23 文章-0 trackbacks-0

OSG 碰撞檢測之多面體求交器代碼解讀(PloytopeIntersector)

      關(guān)于碰撞檢測,始終是物理系統(tǒng)在圖形學(xué)運(yùn)用上的一個比較復(fù)雜的問題.碰撞檢測做的好不好.完全決定一個場景漫游的逼真性.
     這幾天,在坐城市汽車仿真處理上,對于驅(qū)動汽車運(yùn)動時候,對于汽車的碰撞檢測問題困擾了我相當(dāng)?shù)木?始終沒能做到很好.這當(dāng)中我現(xiàn)在使用的汽車包圍體對場景進(jìn)行求交測試時候,用到了OSG中PolytopeIntersector.
     對于一個Polytope 應(yīng)當(dāng)是多個平面組成的一個空間區(qū)域,對于OSG求交器當(dāng)中,這個多面體各個平面的正面必須都是屬于這個區(qū)域內(nèi)的? 怎么解釋呢.平面的法線應(yīng)當(dāng)是指向該空間區(qū)域內(nèi)部.比如說一個四面體.其內(nèi)部的四個面應(yīng)當(dāng)是正面(法線朝向的方向那個面.) 這是多面體求交器使用的一個關(guān)鍵.(這在之后的代碼解讀當(dāng)中會一并解釋).

     對于OSG場景求交測試,是必然要用到訪問器的(Vistor.這個應(yīng)當(dāng)在在另辟一篇文章才能詳述清楚,它的使用原理,因此這里我們暫時先用著.) 對于求交器使用到的訪問器(Vistor)應(yīng)當(dāng)是交集訪問器(IntersectionVistor).

    因此,我們在定義上則應(yīng)當(dāng)是如下:

/** 創(chuàng)建一個多面體求交器*/

osgUtil::PolytopeIntersector* pI =new osgUtil::PolytopeIntersector(poly);

/** 構(gòu)造一個交集訪問器*/

osgUtil::IntersectionVisitor iv(pI);

對于求交集則應(yīng)當(dāng)對于場景根節(jié)點(diǎn)做請求訪問的操作..這當(dāng)中可能需要避開自身節(jié)點(diǎn)等一些不必要的節(jié)點(diǎn)等.

/**　設(shè)置避開自身節(jié)點(diǎn)*/

_model->setNodeMask(0x0);

/** 根節(jié)點(diǎn)請求訪問操作*/

root->accept(iv);

/** 恢復(fù)自身節(jié)點(diǎn)的NodeMask*/

_model->setNodeMask(0xffffffff);

     對于setNodeMask()避開節(jié)點(diǎn)等.我想應(yīng)當(dāng)在Vistor中在詳述..
     再對于訪問操作之后,我們就可以獲得所返回的交集了.

if(pI->containsIntersections())

{

typedef osgUtil::PolytopeIntersector::Intersections inters;

for(inters::iterator it=pI->getIntersections().begin();\

it!=pI->getIntersections().end();it++)

/** ……*/

}

固然,這些只是相對于簡單的操作.而我們是想要深入到了解在root->accept(iv)之后到底做了什么事情?它到底如何求得了我們想要的數(shù)據(jù)? 那現(xiàn)在開始我們的代碼解讀之旅……當(dāng)然這其中,我想有必要略去一些關(guān)系到Vistor的內(nèi)容.因?yàn)檫@些詳述起來,不是簡短的能夠說的清楚...

現(xiàn)在我們定位到: osgUtil/IntersectionVisitor.cpp 第226行:

apply(osg::Geode& geode)

    因?yàn)間eode是葉子節(jié)點(diǎn),最后肯定都會請求到它,并訪問..其中的代碼我們將能夠非常直觀的看出它將要干嘛?
對于geode下的所有可繪制圖元進(jìn)行求交.因此我們現(xiàn)在將轉(zhuǎn)到 intersect函數(shù)

    定位到: include/osgUtil/IntersectionVisitor.h 第245行:

intersect

    關(guān)于_intersectorStack 是個求交器的集合,我們在構(gòu)造的時候?qū)olytopeIntersector傳入后將會被加入到這個集合當(dāng)中..因此這將會回到PolytopeIntersector中的intersect函數(shù)..因此,我們又得重新打開polytope那個文件咯..
    定位到 osgUtil/PolyIntersector.cpp 第547行..

PolytopeIntersector::intersect

我們可以看到再用 PolytopePrimitiveIntersector 構(gòu)造了一個func 后(并設(shè)置多面體,和參考平面) 對于drawable進(jìn)行訪問操作?似乎又回到vistor...? 其實(shí)這個只是類似的操作,但還算不上vistor..暫時當(dāng)作類似的對待吧..雖然Vistor模式在OSG中的運(yùn)用非常的多..而且?guī)缀跆幪幎紩玫?.這個時候我們將要進(jìn)入一個關(guān)鍵時刻,因?yàn)槲覀冎?在osg中drawable里頭已經(jīng)是最后的頂點(diǎn)等所有數(shù)據(jù)存放的地方.drawable其實(shí)只是個抽象類.這里我只會簡單的通過它的一個特例:Geometry 來講述這一段內(nèi)容..
所以現(xiàn)在我們將定位在osg/Geometry.cpp 第2199行:

void Geometry::accept(PrimitiveFunctor& functor) const

{

if (!_vertexData.array.valid() || _vertexData.array->getNumElements()==0) return;

if (!_vertexData.indices.valid())

{

switch(_vertexData.array->getType())

{

case(Array::Vec2ArrayType):

functor.setVertexArray(_vertexData.array->getNumElements(),static_cast<const Vec2*>(_vertexData.array->getDataPointer()));

break;

case(Array::Vec3ArrayType):

functor.setVertexArray(_vertexData.array->getNumElements(),static_cast<const Vec3*>(_vertexData.array->getDataPointer()));

break;

case(Array::Vec4ArrayType):

functor.setVertexArray(_vertexData.array->getNumElements(),static_cast<const Vec4*>(_vertexData.array->getDataPointer()));

break;

case(Array::Vec2dArrayType):

functor.setVertexArray(_vertexData.array->getNumElements(),static_cast<const Vec2d*>(_vertexData.array->getDataPointer()));

break;

case(Array::Vec3dArrayType):

functor.setVertexArray(_vertexData.array->getNumElements(),static_cast<const Vec3d*>(_vertexData.array->getDataPointer()));

break;

case(Array::Vec4dArrayType):

functor.setVertexArray(_vertexData.array->getNumElements(),static_cast<const Vec4d*>(_vertexData.array->getDataPointer()));

break;

default:

notify(WARN)<<"Warning: Geometry::accept(PrimitiveFunctor&) cannot handle Vertex Array type"<<_vertexData.array->getType()<<std::endl;

return;

}

for(PrimitiveSetList::const_iterator itr=_primitives.begin();

itr!=_primitives.end();

++itr)

{

(*itr)->accept(functor);

}

/** *//** 后面對于存在索引數(shù)組的暫時省略……*/

}

      對于這個操作,我們暫時只看不存在索引數(shù)據(jù)的..因?yàn)橄鄬τ趤碇v原理總是一樣的.后面的只是多了一些步驟將頂點(diǎn)數(shù)據(jù)取出..好了.我們回到正題.
       functor.setVecterArray() 很直觀的明白,將頂點(diǎn)數(shù)據(jù)存到fuctor里.以便于在之后functor操作.

      其后最主要的還是在于對于drawable里的每個primitiveset 進(jìn)行接受fuctor訪問操作 (*itr)->accept(functor);
我們知道.primitiveset里頭擁有的數(shù)據(jù)是頂點(diǎn)最后繪制的規(guī)則. 相當(dāng)于我們在OPENGL當(dāng)中使用glBegin() glEnd()一樣指定最后基礎(chǔ)圖元生成的規(guī)則.而我們所要求交集的目的在于獲得跟這些基礎(chǔ)圖元的交集.因此.我們有必要繼續(xù)往下深究.我們還沒有嗅到最終結(jié)果,還不能夠放棄. 好了繼續(xù)..PrimitiveSet又是一個虛類.因此,我們有必要挑個實(shí)體類來深究.就選DrawArray吧. DrawArray指定一個MODE,頂點(diǎn)的起始位置,以及參與繪制的頂點(diǎn)的總數(shù)目..
MODE 就相當(dāng)于 GL_LINES GL_TRIANGLES 等等.我們再次回到代碼來說吧.
       這次我們將定位在: osg/PrimitiveSet.cpp 第43行:
       很簡單...

DrawArrays::accept

        所以最終的結(jié)果都將回到fuctor里頭進(jìn)行交集運(yùn)算的處理..._mode _first _count 將擁有的規(guī)則送往fuctor..

       在追究了這么多之后,我們又需要回到functor里頭.這個functor 是什么呢? 還記得我之前說的使用PolytopePrimitiveIntersector 構(gòu)造了一個func對不? 所有的關(guān)鍵將在那里揭開....最后的結(jié)果總還是深藏于原來的最初的起點(diǎn)位置..不過我想還真不枉繞了一圈...
      在我們回到func 之前我們還需要深究下functor.drawArrays() 這個函數(shù)到底做了什么? 因?yàn)樵赑olytopePrimitiveIntersector當(dāng)初我們并未發(fā)現(xiàn)有這個函數(shù).PolytopePrimitiveIntersector這個類是在PolytopeIntersector.cpp文件當(dāng)中定義的.它只有一大堆的operator()操作...因此我們需要回到構(gòu)造它的那個functor()里頭..
現(xiàn)在我將定位到 include/osg/TemplatePrimitiveFunctor.h 第90行..

drawArrays(GLenum mode,GLint first,GLsizei count)

        對于此,我們暫時只觀看最簡單的GL_TRIANGLES ,對于三角形的每三個點(diǎn)將會繪制一個三角形.因此每次只取三個頂點(diǎn),將它傳遞給當(dāng)前構(gòu)造的func0>operator()處理.這就是為什么 func里頭全部是都是operator()操作了..
       我們弄明白這些之后,馬上回到PolytopePrimitiveIntersector 最后的結(jié)果.令人期待啊...
       PolytopePrimitiveIntersector中的operator()支持很多種類型,.參數(shù)的不同,一個點(diǎn)(points)(兩個點(diǎn))lines,三個點(diǎn)(Triangles),四個點(diǎn)(quads)

       最后定位在三角形的處理上: osgUtil/PolytopeIntersector.cpp 第208行.

       這段代碼相當(dāng)?shù)拈L,但是看起來非常的好理解.這里我也將解釋為什么對于多面體在定義的時候法線很重要了? 我想我有必要將這部分代碼全部解讀清楚..這部分是關(guān)鍵.

void operator()

void operator()(const Vec3_type v1, const Vec3_type v2, const Vec3_type v3, bool treatVertexDataAsTemporary)

{

++_index;

if ((_dimensionMask & PolytopeIntersector::DimTwo) == 0) return;

PlaneMask selector_mask = 0x1;

PlaneMask inside_mask = 0x0;

_candidates.clear();

for(PlaneList::const_iterator it=_planes.begin();

it!=_planes.end();

++it, selector_mask <<= 1)

{

const osg::Plane& plane=*it;

const value_type d1=plane.distance(v1);

const value_type d2=plane.distance(v2);

const value_type d3=plane.distance(v3);

const bool d1IsNegative = (d1<0.0f);

const bool d2IsNegative = (d2<0.0f);

const bool d3IsNegative = (d3<0.0f);

if (d1IsNegative && d2IsNegative && d3IsNegative) return; // triangle outside

if (!d1IsNegative && !d2IsNegative && !d3IsNegative)

{

inside_mask |= selector_mask;

continue; // completly inside

}

// edge v1-v2 intersects

if (d1==0.0f)

{

_candidates.push_back( CandList_t::value_type(selector_mask, v1) );

}

else if (d2==0.0f)

{

_candidates.push_back( CandList_t::value_type(selector_mask, v2) );

}

else if (d1IsNegative && !d2IsNegative)

{

_candidates.push_back( CandList_t::value_type(selector_mask, (v1-(v2-v1)*(d1/(-d1+d2))) ) );

}

else if (!d1IsNegative && d2IsNegative)

{

_candidates.push_back( CandList_t::value_type(selector_mask, (v1+(v2-v1)*(d1/(d1-d2))) ) );

}

// edge v1-v3 intersects

if (d3==0.0f)

{

_candidates.push_back( CandList_t::value_type(selector_mask, v3) );

}

else if (d1IsNegative && !d3IsNegative)

{

_candidates.push_back( CandList_t::value_type(selector_mask, (v1-(v3-v1)*(d1/(-d1+d3))) ) );

}

else if (!d1IsNegative && d3IsNegative)

{

_candidates.push_back( CandList_t::value_type(selector_mask, (v1+(v3-v1)*(d1/(d1-d3))) ) );

}

// edge v2-v3 intersects

if (d2IsNegative && !d3IsNegative)

{

_candidates.push_back( CandList_t::value_type(selector_mask, (v2-(v3-v2)*(d2/(-d2+d3))) ) );

} else if (!d2IsNegative && d3IsNegative)

{

_candidates.push_back( CandList_t::value_type(selector_mask, (v2+(v3-v2)*(d2/(d2-d3))) ) );

}

if (_plane_mask==inside_mask)

{ // triangle lies inside of all planes

_candidates.push_back( CandList_t::value_type(_plane_mask, v1) );

_candidates.push_back( CandList_t::value_type(_plane_mask, v2) );

_candidates.push_back( CandList_t::value_type(_plane_mask, v3) );

addIntersection(_index, _candidates);

return;

}

if (_candidates.empty() && _planes.size()<3) return;

unsigned int numCands=checkCandidatePoints(inside_mask);

if (numCands>0)

{

addIntersection(_index, _candidates);

return;

}

// handle case where the polytope goes through the triangle

// without containing any point of it

LinesList& lines=getPolytopeLines();

_candidates.clear();

// check all polytope lines against the triangle

// use algorithm from "Real-time rendering" (second edition) pp.580

const Vec3_type e1=v2-v1;

const Vec3_type e2=v3-v1;

for (LinesList::const_iterator it=lines.begin(); it!=lines.end(); ++it)

{

const PlanesLine& line=*it;

Vec3_type p=line.dir^e2;

const value_type a=e1*p;

if (osg::absolute(a)<eps()) continue;

const value_type f=1.0f/a;

const Vec3_type s=(line.pos-v1);

const value_type u=f*(s*p);

if (u<0.0f || u>1.0f) continue;

const Vec3_type q=s^e1;

const value_type v=f*(line.dir*q);

if (v<0.0f || u+v>1.0f) continue;

const value_type t=f*(e2*q);

_candidates.push_back(CandList_t::value_type(line.mask, line.pos+line.dir*t));

}

numCands=checkCandidatePoints(inside_mask);

if (numCands>0)

{

addIntersection(_index, _candidates);

return;

}

現(xiàn)在將做最后的代碼解讀工作 selector_mask 當(dāng)前操作平面編號的標(biāo)記 inside_mask 標(biāo)記三角形在哪些平面的正面?即所說在區(qū)域內(nèi)..對于所有平面,將進(jìn)行如下操作:
1. d1 d2 d3 分別求得 ax+by+cz+d < = > 0
    [ax+by+cz >0 表示點(diǎn)在正面這邊,=0 表示點(diǎn)平面上,<0則表示在背面這邊]
     若三個點(diǎn)都在某個平面的背面..那說明這個三角形肯定在這個多面體的區(qū)域外.則結(jié)束..
     若三個點(diǎn)都在某個平面的正面,則做標(biāo)記并繼續(xù)其他平面.
2. 若不是以上兩種情況,那分別判斷v1v2 v1v3 v2v3這三條線段的與平面的交點(diǎn).并加入至候選頂點(diǎn)列表當(dāng)中.

在對所有平面都進(jìn)行操作之后,需要判斷幾種情況我們可以考慮?
第一.三角形剛好在多面體內(nèi)部.
第二.可能這些交點(diǎn)落在其他平面的背面了.
第三可能三條邊與平面是存在交點(diǎn).但是多面體的組成的閉合區(qū)域卻剛好穿過三角形內(nèi)部.這個時候必須對平面的交線與三角形求交點(diǎn)..

所以這三個部分完全概括了上面的代碼?是的.我想這個部分并不需要我講的有多么詳細(xì)了.很容易理解的.

其后,我還想深究下最后這個交集會存放到哪里去了?我們最終該如何使用獲得交集才能夠更好被我們所利用?

    addIntersection(_index, _candidates);

    對于每處理一個三角形 _index 都會在開頭部分自增..因此對于Intersections中的每一個交集的點(diǎn)都針對于同一個三角形..(對于別的同理可得?) 也就是說_index表示在primitiveSet當(dāng)中.這個三角形是第幾個三角形.(三角形序號)
    最后,我們再次回到我們最開始進(jìn)入這么大段篇幅討論的起始位置吧?還記得否?我們第二個intersect()函數(shù)..就是PolytopeIntersector類中的..因?yàn)槲覀冏詈蟮慕Y(jié)果總會回歸到我們需要的地方.所以我們現(xiàn)在得回到那里去取得我們最終獲得的數(shù)據(jù)/.

結(jié)果如何?

      對于從func中獲得的交集.我們將需要將它變成我們所需要的數(shù)據(jù).我將一一解釋最終我們得到的每個數(shù)據(jù)的含義:
     hit.distance // 表示從當(dāng)前這個交集的所有頂點(diǎn)的中心點(diǎn)到參考平面的距離.
     hit.primitiveIndex //表示之前我們說的這個圖元在PrimitiveSet中的序號.
     hit.nodepath //表示這個從根結(jié)點(diǎn)到當(dāng)前這個geode的路徑..因?yàn)槲覀冎涝趘istor中我們有pushNodepath() popNodePath()來保存這個路徑操作..所以這個路徑是從vistor中獲得的.
     hit.drawable //當(dāng)然是我們保存著當(dāng)前這個交集是對于哪個drawable.
     hit.matrix   //表示當(dāng)前這個drawable應(yīng)當(dāng)在世界坐標(biāo)系的變換矩陣.我們可以使用point*matrix 來得到獲得點(diǎn)在世界坐標(biāo)系下的位置..
     hit.localIntersecotPoint //表示所有交點(diǎn)的中心點(diǎn).
     hit.intersectorPoint //所有交點(diǎn)的一個數(shù)組..目前最多的頂點(diǎn)個數(shù)應(yīng)該是6.. enum { MaxNumIntesectionPoints=6 };
     hit.numintersectorPoint // 所有頂點(diǎn)的個數(shù)..

我想這個解讀過程到此應(yīng)當(dāng)結(jié)束了...繼續(xù)學(xué)習(xí)ING.....

posted on 2009-08-02 15:03 米游閱讀(7577) 評論(1) 編輯收藏引用所屬分類: OpenGL/OSG

評論:

# re: OSG 碰撞檢測之多面體求交器代碼解讀(PloytopeIntersector) 2018-05-03 14:49 | 盧江

你好，能不能分享一下你寫的這個碰撞檢測，多面體求交的源碼呀？我最近在寫這個碰撞檢測的代碼上碰到好多問題，希望能參考一下你的代碼，不勝感激！（我的郵箱：313741269@qq.com）回復(fù) 更多評論

刷新評論列表

只有注冊用戶登錄后才能發(fā)表評論。


相關(guān)文章: OSG 學(xué)習(xí)<4> MatrixTransform 與 PosiotionAttitudeTransform OpenGL 渲染管線理論 OSG學(xué)習(xí)<3> Drawable 與幾何體創(chuàng)建 OSG學(xué)習(xí)<2> GraphicsContext與窗口建立 OSG學(xué)習(xí)<1> osg概述以及學(xué)習(xí)方法等 opengl nehe lesson 1-24課 glut版本代碼 opengl學(xué)習(xí) nehe opengl lesson_9 opengl學(xué)習(xí) nehe lesson 8 OSG 碰撞檢測之多面體求交器代碼解讀(PloytopeIntersector) opengl 使用bmp位圖紋理(8-bit 24bit)

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理