關(guān)于碰撞檢測(cè),始終是物理系統(tǒng)在圖形學(xué)運(yùn)用上的一個(gè)比較復(fù)雜的問(wèn)題.碰撞檢測(cè)做的好不好.完全決定一個(gè)場(chǎng)景漫游的逼真性.
這幾天,在坐城市汽車仿真處理上,對(duì)于驅(qū)動(dòng)汽車運(yùn)動(dòng)時(shí)候,對(duì)于汽車的碰撞檢測(cè)問(wèn)題困擾了我相當(dāng)?shù)木?始終沒(méi)能做到很好.這當(dāng)中我現(xiàn)在使用的汽車包圍體對(duì)場(chǎng)景進(jìn)行求交測(cè)試時(shí)候,用到了OSG中PolytopeIntersector.
對(duì)于一個(gè)Polytope 應(yīng)當(dāng)是多個(gè)平面組成的一個(gè)空間區(qū)域,對(duì)于OSG求交器當(dāng)中,這個(gè)多面體各個(gè)平面的正面必須都是屬于這個(gè)區(qū)域內(nèi)的? 怎么解釋呢.平面的法線應(yīng)當(dāng)是指向該空間區(qū)域內(nèi)部.比如說(shuō)一個(gè)四面體.其內(nèi)部的四個(gè)面應(yīng)當(dāng)是正面(法線朝向的方向那個(gè)面.) 這是多面體求交器使用的一個(gè)關(guān)鍵.(這在之后的代碼解讀當(dāng)中會(huì)一并解釋).
對(duì)于OSG場(chǎng)景求交測(cè)試,是必然要用到訪問(wèn)器的(Vistor.這個(gè)應(yīng)當(dāng)在在另辟一篇文章才能詳述清楚,它的使用原理,因此這里我們暫時(shí)先用著.) 對(duì)于求交器使用到的訪問(wèn)器(Vistor)應(yīng)當(dāng)是交集訪問(wèn)器(IntersectionVistor).
因此,我們?cè)诙x上則應(yīng)當(dāng)是如下:
/**//** 創(chuàng)建一個(gè)多面體求交器*/
osgUtil::PolytopeIntersector* pI =new osgUtil::PolytopeIntersector(poly);
/**//** 構(gòu)造一個(gè)交集訪問(wèn)器*/
osgUtil::IntersectionVisitor iv(pI);
對(duì)于求交集 則應(yīng)當(dāng)對(duì)于場(chǎng)景根節(jié)點(diǎn)做請(qǐng)求訪問(wèn)的操作..這當(dāng)中可能需要避開(kāi)自身節(jié)點(diǎn)等一些不必要的節(jié)點(diǎn)等.
/**//** 設(shè)置避開(kāi)自身節(jié)點(diǎn)*/
_model->setNodeMask(0x0);
/**//** 根節(jié)點(diǎn)請(qǐng)求訪問(wèn)操作*/
root->accept(iv);
/**//** 恢復(fù)自身節(jié)點(diǎn)的NodeMask*/
_model->setNodeMask(0xffffffff);
對(duì)于setNodeMask()避開(kāi)節(jié)點(diǎn)等.我想應(yīng)當(dāng)在Vistor中在詳述..
再對(duì)于訪問(wèn)操作之后,我們就可以獲得所返回的交集了.
if(pI->containsIntersections())
{
typedef osgUtil::PolytopeIntersector::Intersections inters;
for(inters::iterator it=pI->getIntersections().begin();\
it!=pI->getIntersections().end();it++)
/**//** ……*/
}
固然,這些只是相對(duì)于簡(jiǎn)單的操作.而我們是想要深入到了解在root->accept(iv)之后到底做了什么事情?它到底如何求得了我們想要的數(shù)據(jù)? 那現(xiàn)在開(kāi)始我們的代碼解讀之旅……當(dāng)然這其中,我想有必要略去一些關(guān)系到Vistor的內(nèi)容.因?yàn)檫@些詳述起來(lái),不是簡(jiǎn)短的能夠說(shuō)的清楚...
現(xiàn)在我們定位到: 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();
}
因?yàn)間eode是葉子節(jié)點(diǎn),最后肯定都會(huì)請(qǐng)求到它,并訪問(wèn)..其中的代碼我們將能夠非常直觀的看出它將要干嘛?
對(duì)于geode下的所有可繪制圖元進(jìn)行求交.因此我們現(xiàn)在將轉(zhuǎn)到 intersect函數(shù)
定位到: include/osgUtil/IntersectionVisitor.h 第245行:
intersect
inline void intersect(osg::Drawable* drawable) { _intersectorStack.back()->intersect(*this, drawable); }
關(guān)于_intersectorStack 是個(gè)求交器的集合,我們?cè)跇?gòu)造的時(shí)候?qū)olytopeIntersector傳入后將會(huì)被加入到這個(gè)集合當(dāng)中..因此 這將會(huì)回到PolytopeIntersector中的intersect函數(shù)..因此,我們又得重新打開(kāi)polytope那個(gè)文件咯..
定位到 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 構(gòu)造了一個(gè)func 后(并設(shè)置多面體,和參考平面) 對(duì)于drawable進(jìn)行訪問(wèn)操作?似乎又回到vistor...? 其實(shí)這個(gè)只是類似的操作,但還算不上vistor..暫時(shí)當(dāng)作類似的對(duì)待吧..雖然Vistor模式在OSG中的運(yùn)用非常的多..而且?guī)缀跆幪幎紩?huì)用到..這個(gè)時(shí)候我們將要進(jìn)入一個(gè)關(guān)鍵時(shí)刻,因?yàn)槲覀冎?在osg中drawable里頭已經(jīng)是最后的頂點(diǎn)等所有數(shù)據(jù)存放的地方.drawable其實(shí)只是個(gè)抽象類.這里我只會(huì)簡(jiǎn)單的通過(guò)它的一個(gè)特例:Geometry 來(lái)講述這一段內(nèi)容..
所以現(xiàn)在 我們將定位在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);
}
}
/** *//** *//** *//** 后面對(duì)于存在索引數(shù)組的暫時(shí)省略……*/
}
對(duì)于這個(gè)操作,我們暫時(shí)只看不存在索引數(shù)據(jù)的..因?yàn)橄鄬?duì)于來(lái)講原理總是一樣的.后面的只是多了一些步驟將頂點(diǎn)數(shù)據(jù)取出..好了.我們回到正題.
functor.setVecterArray() 很直觀的明白,將頂點(diǎn)數(shù)據(jù)存到fuctor里.以便于在之后functor操作.
其后最主要的還是在于對(duì)于drawable里的每個(gè)primitiveset 進(jìn)行接受fuctor訪問(wèn)操作 (*itr)->accept(functor);
我們知道.primitiveset里頭擁有的數(shù)據(jù)是頂點(diǎn)最后繪制的規(guī)則. 相當(dāng)于我們?cè)贠PENGL當(dāng)中使用glBegin() glEnd()一樣指定最后基礎(chǔ)圖元生成的規(guī)則.而我們所要求交集的目的在于獲得跟這些基礎(chǔ)圖元的交集.因此.我們有必要繼續(xù)往下深究.我們還沒(méi)有嗅到最終結(jié)果,還不能夠放棄. 好了 繼續(xù)..PrimitiveSet又是一個(gè)虛類.因此,我們有必要挑個(gè)實(shí)體類來(lái)深究.就選DrawArray吧. DrawArray指定一個(gè)MODE,頂點(diǎn)的起始位置,以及參與繪制的頂點(diǎn)的總數(shù)目..
MODE 就相當(dāng)于 GL_LINES GL_TRIANGLES 等等.我們?cè)俅位氐酱a來(lái)說(shuō)吧.
這次我們將定位在: osg/PrimitiveSet.cpp 第43行:
很簡(jiǎn)單...
DrawArrays::accept
void DrawArrays::accept(PrimitiveFunctor& functor) const
{
functor.drawArrays(_mode,_first,_count);
}
所以最終的結(jié)果 都將回到fuctor里頭進(jìn)行交集運(yùn)算的處理..._mode _first _count 將擁有的規(guī)則送往fuctor..
在追究了這么多之后,我們又需要回到functor里頭.這個(gè)functor 是什么呢? 還記得我之前說(shuō)的使用PolytopePrimitiveIntersector 構(gòu)造了一個(gè)func對(duì)不? 所有的關(guān)鍵將在那里揭開(kāi)....最后的結(jié)果總還是深藏于原來(lái)的最初的起點(diǎn)位置..不過(guò)我想還真不枉繞了一圈...
在我們回到func 之前我們還需要深究下functor.drawArrays() 這個(gè)函數(shù)到底做了什么? 因?yàn)樵赑olytopePrimitiveIntersector當(dāng)初我們并未發(fā)現(xiàn)有這個(gè)函數(shù).PolytopePrimitiveIntersector這個(gè)類是在PolytopeIntersector.cpp文件當(dāng)中定義的.它只有一大堆的operator()操作...因此我們需要回到構(gòu)造它的那個(gè)functor()里頭..
現(xiàn)在我將定位到 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;
}
/** *//** 后面的其他省略…… */
}
對(duì)于此,我們暫時(shí)只觀看最簡(jiǎn)單的GL_TRIANGLES ,對(duì)于三角形的每三個(gè)點(diǎn)將會(huì)繪制一個(gè)三角形.因此每次只取三個(gè)頂點(diǎn),將它傳遞給當(dāng)前構(gòu)造的func0>operator()處理.這就是為什么 func里頭全部是都是operator()操作了..
我們弄明白這些之后,馬上回到PolytopePrimitiveIntersector 最后的結(jié)果.令人期待啊...
PolytopePrimitiveIntersector中的operator()支持很多種類型,.參數(shù)的不同,一個(gè)點(diǎn)(points)(兩個(gè)點(diǎn))lines,三個(gè)點(diǎn)(Triangles),四個(gè)點(diǎn)(quads)
最后定位在三角形的處理上: osgUtil/PolytopeIntersector.cpp 第208行.
這段代碼相當(dāng)?shù)拈L(zhǎng),但是看起來(lái)非常的好理解.這里我也將解釋為什么對(duì)于多面體在定義的時(shí)候法線很重要了? 我想我有必要將這部分代碼全部解讀清楚..這部分是關(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)前操作平面編號(hào)的標(biāo)記 inside_mask 標(biāo)記三角形在哪些平面的正面?即所說(shuō)在區(qū)域內(nèi)..對(duì)于所有平面,將進(jìn)行如下操作:
1. d1 d2 d3 分別求得 ax+by+cz+d < = > 0
[ax+by+cz >0 表示點(diǎn)在正面這邊,=0 表示點(diǎn)平面上,<0則表示在背面這邊]
若三個(gè)點(diǎn)都在某個(gè)平面的背面..那說(shuō)明這個(gè)三角形肯定在這個(gè)多面體的區(qū)域外.則結(jié)束..
若三個(gè)點(diǎn)都在某個(gè)平面的正面,則做標(biāo)記并繼續(xù)其他平面.
2. 若不是以上兩種情況,那分別判斷v1v2 v1v3 v2v3這三條線段的與平面的交點(diǎn).并加入至候選頂點(diǎn)列表當(dāng)中.
在對(duì)所有平面都進(jìn)行操作之后,需要判斷幾種情況我們可以考慮?
第一.三角形剛好在多面體內(nèi)部.
第二.可能這些交點(diǎn)落在其他平面的背面了.
第三 可能三條邊與平面是存在交點(diǎn).但是多面體的組成的閉合區(qū)域卻剛好穿過(guò)三角形內(nèi)部.這個(gè)時(shí)候必須對(duì)平面的交線與三角形求交點(diǎn)..
所以這三個(gè)部分完全概括了上面的代碼?是的.我想這個(gè)部分并不需要我講的有多么詳細(xì)了.很容易理解的.
其后,我還想深究下最后這個(gè)交集會(huì)存放到哪里去了?我們最終該如何使用獲得交集才能夠更好被我們所利用?
addIntersection(_index, _candidates);
對(duì)于每處理一個(gè)三角形 _index 都會(huì)在開(kāi)頭部分自增..因此 對(duì)于Intersections中的每一個(gè)交集的點(diǎn)都針對(duì)于同一個(gè)三角形..(對(duì)于別的同理可得?) 也就是說(shuō)_index表示在primitiveSet當(dāng)中.這個(gè)三角形是第幾個(gè)三角形.(三角形序號(hào))
最后,我們?cè)俅位氐轿覀冏铋_(kāi)始進(jìn)入這么大段篇幅討論的起始位置吧?還記得否?我們第二個(gè)intersect()函數(shù)..就是PolytopeIntersector類中的..因?yàn)槲覀冏詈蟮慕Y(jié)果總會(huì)回歸到我們需要的地方.所以我們現(xiàn)在得回到那里去取得我們最終獲得的數(shù)據(jù)/.
結(jié)果如何?
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);
}
對(duì)于從func中獲得的交集.我們將需要將它變成我們所需要的數(shù)據(jù).我將一一解釋最終我們得到的每個(gè)數(shù)據(jù)的含義:
hit.distance // 表示從當(dāng)前這個(gè)交集的所有頂點(diǎn)的中心點(diǎn)到參考平面的距離.
hit.primitiveIndex //表示之前我們說(shuō)的這個(gè)圖元在PrimitiveSet中的序號(hào).
hit.nodepath //表示這個(gè)從根結(jié)點(diǎn)到當(dāng)前這個(gè)geode的路徑..因?yàn)槲覀冎涝趘istor中我們有pushNodepath() popNodePath()來(lái)保存這個(gè)路徑操作..所以這個(gè)路徑是從vistor中獲得的.
hit.drawable //當(dāng)然是我們保存著當(dāng)前這個(gè)交集是對(duì)于哪個(gè)drawable.
hit.matrix //表示當(dāng)前這個(gè)drawable應(yīng)當(dāng)在世界坐標(biāo)系的變換矩陣.我們可以使用point*matrix 來(lái)得到獲得點(diǎn)在世界坐標(biāo)系下的位置..
hit.localIntersecotPoint //表示所有交點(diǎn)的中心點(diǎn).
hit.intersectorPoint //所有交點(diǎn)的一個(gè)數(shù)組..目前最多的頂點(diǎn)個(gè)數(shù)應(yīng)該是6.. enum { MaxNumIntesectionPoints=6 };
hit.numintersectorPoint // 所有頂點(diǎn)的個(gè)數(shù)..
我想這個(gè)解讀過(guò)程到此應(yīng)當(dāng)結(jié)束了...繼續(xù)學(xué)習(xí)ING.....
posted on 2009-08-02 15:03
米游 閱讀(7559)
評(píng)論(1) 編輯 收藏 引用 所屬分類:
OpenGL/OSG