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

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);

/** 恢復自身節點的NodeMask*/

_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行:

apply(osg::Geode& geode)

    因為geode是葉子節點,最后肯定都會請求到它,并訪問..其中的代碼我們將能夠非常直觀的看出它將要干嘛?
對于geode下的所有可繪制圖元進行求交.因此我們現在將轉到 intersect函數

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

intersect

    關于_intersectorStack 是個求交器的集合,我們在構造的時候將PolytopeIntersector傳入后將會被加入到這個集合當中..因此這將會回到PolytopeIntersector中的intersect函數..因此,我們又得重新打開polytope那個文件咯..
    定位到 osgUtil/PolyIntersector.cpp 第547行..

PolytopeIntersector::intersect

我們可以看到再用 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::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);

}

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

}

      對于這個操作,我們暫時只看不存在索引數據的..因為相對于來講原理總是一樣的.后面的只是多了一些步驟將頂點數據取出..好了.我們回到正題.
       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

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

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

drawArrays(GLenum mode,GLint first,GLsizei count)

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

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

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

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;

}

現在將做最后的代碼解讀工作 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類中的..因為我們最后的結果總會回歸到我們需要的地方.所以我們現在得回到那里去取得我們最終獲得的數據/.

結果如何?

      對于從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.....

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

評論:

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

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

刷新評論列表

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

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

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理