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

關于碰撞檢測,始終是實體系統在圖形學運用上的一個比較複雜的問題.碰撞檢測做的好不好.完全決定一個場景漫遊的逼真性.

這幾天,在坐城市汽車仿真處理上,對于驅動汽車運動時候,對于汽車的碰撞檢測問題困擾了我相當的久.始終沒能做到很好.這當中我現在使用的汽車包圍體對場景進行求交測試時候,用到了OSG中PolytopeIntersector.

對于一個Polytope 應當是多個平面組成的一個空間區域,對于OSG求交器當中,這個多面體各個平面的正面必須都是屬于這個區域内的? 怎麼解釋呢.平面的法線應當是指向該空間區域内部.比如說一個四面體.其内部的四個面應當是正面(法線朝向的方向那個面.) 這是多面體求交器使用的一個關鍵.(這在之後的代碼解讀當中會一并解釋).

對于OSG場景求交測試,是必然要用到通路器的(Vistor.這個應當在在另辟一篇文章才能詳述清楚,它的使用原理,是以這裡我們暫時先用着.) 對于求交器使用到的通路器(Vistor)應當是交集通路器(IntersectionVistor).

是以,我們在定義上則應當是如下:

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

osgUtil::IntersectionVisitor iv(pI); 對于求交集則應當對于場景根節點做請求通路的操作..這當中可能需要避開自身節點等一些不必要的節點等.

_model->setNodeMask(0x0);

root->accept(iv);

_model->setNodeMask(0xffffffff); 對于setNodeMask()避開節點等.我想應當在Vistor中在詳述..

再對于通路操作之後,我們就可以獲得所傳回的交集了. if(pI->containsIntersections())

{

typedef osgUtil::PolytopeIntersector::Intersections inters;

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

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

} 固然,這些隻是相對于簡單的操作.而我們是想要深入到了解在root->accept(iv)之後到底做了什麼事情?它到底如何求得了我們想要的資料? 那現在開始我們的代碼解讀之旅……當然這其中,我想有必要略去一些關系到Vistor的内容.因為這些詳述起來,不是簡短的能夠說的清楚...

現在我們定位到: osgUtil/IntersectionVisitor.cpp 第226行: void IntersectionVisitor::apply(osg::Geode& geode)

{

// osg::notify(osg::NOTICE)<<"apply(Geode&)"<<std::endl; if (!enter(geode)) return; // osg::notify(osg::NOTICE)<<"inside apply(Geode&)"<<std::endl; for(unsigned int i=0; i<geode.getNumDrawables(); ++i)

{

intersect( geode.getDrawable(i) );

} leave();

} 因為geode是葉子節點,最後肯定都會請求到它,并通路..其中的代碼我們将能夠非常直覺的看出它将要幹嘛?

對于geode下的所有可繪制圖元進行求交.是以我們現在将轉到 intersect函數

定位到: include/osgUtil/IntersectionVisitor.h 第245行: inline void intersect(osg::Drawable* drawable) { _intersectorStack.back()->intersect(*this, drawable); } 關于_intersectorStack 是個求交器的集合,我們在構造的時候将PolytopeIntersector傳入後将會被加入到這個集合當中..是以這将會回到PolytopeIntersector中的intersect函數..是以,我們又得重新打開polytope那個檔案咯..

定位到 osgUtil/PolyIntersector.cpp 第547行.. void PolytopeIntersector::intersect(osgUtil::IntersectionVisitor& iv, osg::Drawable* drawable)

{

osg::TemplatePrimitiveFunctor<PolytopeIntersectorUtils::PolytopePrimitiveIntersector> func;

func.setPolytope( _polytope, _referencePlane );

func.setDimensionMask( _dimensionMask );

drawable->accept(func);

} 我們可以看到再用 PolytopePrimitiveIntersector 構造了一個func 後(并設定多面體,和參考平面) 對于drawable進行通路操作?似乎又回到vistor...? 其實這個隻是類似的操作,但還算不上vistor..暫時當作類似的對待吧..雖然Vistor模式在OSG中的運用非常的多..而且幾乎處處都會用到..這個時候我們将要進入一個關鍵時刻,因為我們知道.在osg中drawable裡頭已經是最後的頂點等所有資料存放的地方.drawable其實隻是個抽象類.這裡我隻會簡單的通過它的一個特例:Geometry 來講述這一段内容..

是以現在我們将定位在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::Vec3ArrayType):

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

}

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

itr!=_primitives.end();

++itr)

{

(*itr)->accept(functor);

}

} 對于這個操作,我們暫時隻看不存在索引資料的..因為相對于來講原理總是一樣的.後面的隻是多了一些步驟将頂點資料取出..好了.我們回到正題.

functor.setVecterArray() 很直覺的明白,将頂點資料存到fuctor裡.以便于在之後functor操作. 後續(下篇)

續上:

其後最主要的還是在于對于drawable裡的每個primitiveset 進行接受fuctor通路操作 (*itr)->accept(functor);

我們知道.primitiveset裡頭擁有的資料是頂點最後繪制的規則. 相當于我們在OPENGL當中使用glBegin() glEnd()一樣指定最後基礎圖元生成的規則.而我們所要求交集的目的在于獲得跟這些基礎圖元的交集.是以.我們有必要繼續往下深究.我們還沒有嗅到最終結果,還不能夠放棄. 好了繼續..PrimitiveSet又是一個虛類.是以,我們有必要挑個實體類來深究.就選DrawArray吧. DrawArray指定一個MODE,頂點的起始位置,以及參與繪制的頂點的總數目..

MODE 就相當于 GL_LINES GL_TRIANGLES 等等.我們再次回到代碼來說吧.

這次我們将定位在: osg/PrimitiveSet.cpp 第43行:

很簡單... DrawArrays::accept void DrawArrays::accept(PrimitiveFunctor& functor) const

{

functor.drawArrays(_mode,_first,_count);

} 是以最終的結果都将回到fuctor裡頭進行交集運算的處理..._mode _first _count 将擁有的規則送往fuctor..

在追究了這麼多之後,我們又需要回到functor裡頭.這個functor 是什麼呢? 還記得我之前說的使用PolytopePrimitiveIntersector 構造了一個func對不? 所有的關鍵将在那裡揭開....最後的結果總還是深藏于原來的最初的起點位置..不過我想還真不枉繞了一圈...

在我們回到func 之前我們還需要深究下functor.drawArrays() 這個函數到底做了什麼? 因為在PolytopePrimitiveIntersector當初我們并未發現有這個函數.PolytopePrimitiveIntersector這個類是在PolytopeIntersector.cpp檔案當中定義的.它隻有一大堆的operator()操作...是以我們需要回到構造它的那個functor()裡頭..

現在我将定位到 include/osg/TemplatePrimitiveFunctor.h 第90行.. virtual void drawArrays(GLenum mode,GLint first,GLsizei count)

{

if (_vertexArrayPtr==0 || count==0) return; switch(mode)

{

case(GL_TRIANGLES): {

const Vec3* vlast = &_vertexArrayPtr[first+count];

for(const Vec3* vptr=&_vertexArrayPtr[first];vptr<vlast;vptr+=3)

this->operator()(*(vptr),*(vptr+1),*(vptr+2),_treatVertexDataAsTemporary);

break;

}

} 對于此,我們暫時隻觀看最簡單的GL_TRIANGLES ,對于三角形的每三個點将會繪制一個三角形.是以每次隻取三個頂點,将它傳遞給目前構造的func0>operator()處理.這就是為什麼 func裡頭全部是都是operator()操作了..

我們弄明白這些之後,馬上回到PolytopePrimitiveIntersector 最後的結果.令人期待啊...

PolytopePrimitiveIntersector中的operator()支援很多種類型,.參數的不同,一個點(points)(兩個點)lines,三個點(Triangles),四個點(quads)

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

這段代碼相當的長,但是看起來非常的好了解.這裡我也将解釋為什麼對于多面體在定義的時候法線很重要了? 我想我有必要将這部分代碼全部解讀清楚..這部分是關鍵. void operator()(const Vec3_type v1, const Vec3_type v2, const Vec3_type v3, bool treatVertexDataAsTemporary)

{

} 現在将做最後的代碼解讀工作 selector_mask 目前操作平面編号的标記 inside_mask 标記三角形在哪些平面的正面?即所說在區域内..對于所有平面,将進行如下操作:

1. d1 d2 d3 分别求得 ax+by+cz+d < = > 0

[ax+by+cz >0 表示點在正面這邊,=0 表示點平面上,<0則表示在背面這邊]

若三個點都在某個平面的背面..那說明這個三角形肯定在這個多面體的區域外.則結束..

若三個點都在某個平面的正面,則做标記并繼續其他平面.

2. 若不是以上兩種情況,那分别判斷v1v2 v1v3 v2v3這三條線段的與平面的交點.并加入至候選頂點清單當中.

在對所有平面都進行操作之後,需要判斷幾種情況我們可以考慮?

第一.三角形剛好在多面體内部.

第二.可能這些交點落在其他平面的背面了.

第三可能三條邊與平面是存在交點.但是多面體的組成的閉合區域卻剛好穿過三角形内部.這個時候必須對平面的交線與三角形求交點..

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

其後,我還想深究下最後這個交集會存放到哪裡去了?我們最終該如何使用獲得交集才能夠更好被我們所利用? addIntersection(_index, _candidates); 對于每處理一個三角形 _index 都會在開頭部分自增..是以對于Intersections中的每一個交集的點都針對于同一個三角形..(對于别的同理可得?) 也就是說_index表示在primitiveSet當中.這個三角形是第幾個三角形.(三角形序号)

最後,我們再次回到我們最開始進入這麼大段篇幅讨論的起始位置吧?還記得否?我們第二個intersect()函數..就是PolytopeIntersector類中的..因為我們最後的結果總會回歸到我們需要的地方.是以我們現在得回到那裡去取得我們最終獲得的資料/.

結果如何? for(PolytopeIntersectorUtils::Intersections::const_iterator it=func.intersections.begin();

it!=func.intersections.end();

++it)

{

const PolytopeIntersectorUtils::PolytopeIntersection& intersection = *it; Intersection hit;

hit.distance = intersection._distance;

hit.maxDistance = intersection._maxDistance;

hit.primitiveIndex = intersection._index;

hit.nodePath = iv.getNodePath();

hit.drawable = drawable;

hit.matrix = iv.getModelMatrix(); osg::Vec3 center;

for (unsigned int i=0; i<intersection._numPoints; ++i)

{

center += intersection._points[i];

}

center /= float(intersection._numPoints);

hit.localIntersectionPoint = center; hit.numIntersectionPoints = intersection._numPoints;

std::copy(&intersection._points[0], &intersection._points[intersection._numPoints],

&hit.intersectionPoints[0]); insertIntersection(hit);

} 對于從func中獲得的交集.我們将需要将它變成我們所需要的資料.我将一一解釋最終我們得到的每個資料的含義:

hit.distance // 表示從目前這個交集的所有頂點的中心點到參考平面的距離.

hit.primitiveIndex //表示之前我們說的這個圖元在PrimitiveSet中的序号.

hit.nodepath //表示這個從根結點到目前這個geode的路徑..因為我們知道在vistor中我們有pushNodepath() popNodePath()來儲存這個路徑操作..是以這個路徑是從vistor中獲得的.

hit.drawable //當然是我們儲存着目前這個交集是對于哪個drawable.

hit.matrix //表示目前這個drawable應當在世界坐标系的變換矩陣.我們可以使用point*matrix 來得到獲得點在世界坐标系下的位置..

hit.localIntersecotPoint //表示所有交點的中心點.

hit.intersectorPoint //所有交點的一個數組..目前最多的頂點個數應該是6.. enum { MaxNumIntesectionPoints=6 };

hit.numintersectorPoint // 所有頂點的個數.. 我想這個解讀過程到此應當結束了...繼續學習ING.....

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

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

繼續閱讀

20/20: Top 20 Programming Lessons I've Learned in 20 Years

20條程式設計經驗

【觀點】風雨20年：我所積累的20條程式設計經驗【觀點】風雨20年：我所積累的20條程式設計經驗

【轉載】風雨20年：我所積累的20條程式設計經驗

恢複Linux作業系統的GRUB引導程式

兩種清除浮動的方法

淺談---測試Native Windows Command與Native PowerShell Command哪個效率高

Xcode中建立Target的步驟

利用Fiddler進行移動端弱網測試

各種二分查找

【原創】程式設計之美之二分搜尋

CentOS7下TestLink環境的部署

軟體測試基礎_對應TestLink整理的測試計劃流程步驟

七牛雲-C#SDK-上傳-前期準備

[轉]iOS微信小視訊優化心得

測試面試題整理