關于碰撞檢測,始終是物理系統在圖形學運用上的一個比較復雜的問題.碰撞檢測做的好不好.完全決定一個場景漫游的逼真性.
這幾天,在坐城市汽車仿真處理上,對于驅動汽車運動時候,對于汽車的碰撞檢測問題困擾了我相當的久.始終沒能做到很好.這當中我現在使用的汽車包圍體對場景進行求交測試時候,用到了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)
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行:
intersect
inline void intersect(osg::Drawable* drawable) { _intersectorStack.back()->intersect(*this, drawable); }
關于_intersectorStack 是個求交器的集合,我們在構造的時候將PolytopeIntersector傳入后將會被加入到這個集合當中..因此 這將會回到PolytopeIntersector中的intersect函數..因此,我們又得重新打開polytope那個文件咯..
定位到 osgUtil/PolyIntersector.cpp 第547行..
PolytopeIntersector::intersect
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
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
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行..
drawArrays(GLenum mode,GLint first,GLsizei count)
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()
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類中的..因為我們最后的結果總會回歸到我們需要的地方.所以我們現在得回到那里去取得我們最終獲得的數據/.
結果如何?
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.....
posted on 2009-08-02 15:03
米游 閱讀(7555)
評論(1) 編輯 收藏 引用 所屬分類:
OpenGL/OSG