青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

eryar

PipeCAD - Plant Piping Design Software.
RvmTranslator - Translate AVEVA RVM to OBJ, glTF, etc.
posts - 603, comments - 590, trackbacks - 0, articles - 0

Bounding Volume Hierarchy BVH in OpenCASCADE

Posted on 2017-05-03 22:50 eryar 閱讀(6452) 評論(0)  編輯 收藏 引用 所屬分類: 2.OpenCASCADE

Bounding Volume Hierarchy BVH in OpenCASCADE

eryar@163.com

Abstract. Bounding Volume Hierarchy(BVH) organizes geometric objects in the tree based on spatial relationships. Each node in the tree contains an axis-aligned bounding box of all the objects below it. Bounding volume hierarchies are used in many algorithms to support efficient operations on the sets of geometric objects, such as collision detection, ray-tracing, searching of nearest objects, and view frustum culling. The paper focus on the usage of BVH on TopoDS_Shape, and its application.

Key Words. BVH, Bounding Volume Hierarchy, Collision Detection

1.Introduction

層次包圍盒(Bounding Volume Hierarchy, BVH)是一種基于物體的場景管理技術,廣泛用于碰撞檢測,光線追蹤,視錐體物體剔除等場合。對于三維場景的實時渲染來說,BVH是最常用的數據結構。場景以層次樹形結構進行組織,包含一個根節點、內部節點、葉子節點。樹中的每個節點,包括葉子節點都有一個包圍體,可以將其子樹的所有幾何體包圍起來,這就是BVH名字的由來。如下圖所示:

wps9752.tmp

Figure 1. Simple Scene(left), BVH Scene Graph(right)

本文主要介紹OpenCASCADE中的BVH包及其應用,如碰撞檢測。

2.Build BVH

在BVH包中的頭文件里面找到BVH的作者:Denis BOGOLEPOV, Danila ULYANOV,在網上搜到他們的一篇論文:Real-Time SAH BVH Construction for Ray Tracing Dynamic Scenes. 因此,可知BVH中是應用SAH(Surface Area Heuristic)策略來構造BVH樹的。根據BVH_BinnedBuilder頭文件中的注釋可知:

//! Performs construction of BVH tree using binned SAH algorithm. Number
//! of bins controls BVH quality in cost of construction time (greater
//! better). For optimal results, use 32 - 48 bins. However, reasonable
//! performance is provided even for 4 - 8 bins (it is only 10-20% lower
//! in comparison with optimal settings). Note that multiple threads can
//! be used only with thread safe BVH primitive sets.

OpenCASCADE中也提供了其他的構造方法,如類BVH_LinearBuilder中使用了Spatial Morton codes方法:

//! Performs fast BVH construction using LBVH building approach.
//! Algorithm uses spatial Morton codes to reduce the BVH construction
//! problem to a sorting problem (radix sort -- O(N) complexity). This
//! Linear Bounding Volume Hierarchy (LBVH) builder produces BVH trees
//! of lower quality compared to SAH-based BVH builders but it is over
//! an order of magnitude faster (up to 3M triangles per second).
//!
//! For more details see:
//! C. Lauterbach, M. Garland, S. Sengupta, D. Luebke, and D. Manocha.
//! Fast BVH construction on GPUs. Eurographics, 2009.

3.Traversal BVH

由類BVH_TreeBase可知,當得到BVH樹后,可以取出節點索引的數組。下面給出將TopoDS_Shape的BVH樹顯示出來的示例代碼:

/*
Copyright(C) 2017 Shing Liu(eryar@163.com)

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files(the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and / or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions :

The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.
*/

// Visual Studio 2013 & OpenCASCADE7.1.0
// 2017-04-18  20:52 

#include <BRepExtrema_TriangleSet.hxx>

#include <BRepTools.hxx>
#include <BRep_Builder.hxx>

#include <TopoDS.hxx>

#include <TopExp_Explorer.hxx>

#include <BRepPrimAPI_MakeBox.hxx>

#include <BRepMesh_IncrementalMesh.hxx>

#pragma comment(lib, "TKernel.lib")
#pragma comment(lib, "TKMath.lib")

#pragma comment(lib, "TKG2d.lib")
#pragma comment(lib, "TKG3d.lib")
#pragma comment(lib, "TKGeomBase.lib")
#pragma comment(lib, "TKGeomAlgo.lib")

#pragma comment(lib, "TKBRep.lib")
#pragma comment(lib, "TKPrim.lib")
#pragma comment(lib, "TKMesh.lib")
#pragma comment(lib, "TKTopAlgo.lib")


void testBvh(const std::string& theFileName)
{
    BRep_Builder aBuilder;
    TopoDS_Compound aCompound;

    TopoDS_Shape aShape;
    BRepTools::Read(aShape, theFileName.c_str(), aBuilder);

    BRepExtrema_ShapeList aFaceList;
    for (TopExp_Explorer i(aShape, TopAbs_FACE); i.More(); i.Next())
    {
        aFaceList.Append(TopoDS::Face(i.Current()));
    }

    aBuilder.MakeCompound(aCompound);

    BRepMesh_IncrementalMesh aMesher(aShape, 1.0);

    BRepExtrema_TriangleSet aTriangleSet(aFaceList);
    const NCollection_Handle<BVH_Tree<Standard_Real, 3> >& aBvh = aTriangleSet.BVH();
    for (int i = 0; i < aBvh->Length(); i++)
    {
        const BVH_Vec4i& aNodeData = aBvh->NodeInfoBuffer()[i];

        if (aNodeData.x() == 0)
        {
            // inner node.
            const BVH_Vec3d& aP1 = aBvh->MinPoint(aNodeData.y());
            const BVH_Vec3d& aP2 = aBvh->MaxPoint(aNodeData.y());

            const BVH_Vec3d& aQ1 = aBvh->MinPoint(aNodeData.z());
            const BVH_Vec3d& aQ2 = aBvh->MaxPoint(aNodeData.z());

            try
            {
                BRepPrimAPI_MakeBox aBoxMaker(gp_Pnt(aP1.x(), aP1.y(), aP1.z()),
                    gp_Pnt(aP2.x(), aP2.y(), aP2.z()));
                for (TopExp_Explorer i(aBoxMaker.Shape(), TopAbs_EDGE); i.More(); i.Next())
                {
                    aBuilder.Add(aCompound, i.Current());
                }
            }
            catch (Standard_Failure f)
            {
            }

            try
            {
                BRepPrimAPI_MakeBox aBoxMaker(gp_Pnt(aQ1.x(), aQ1.y(), aQ1.z()),
                    gp_Pnt(aQ2.x(), aQ2.y(), aQ2.z()));
                for (TopExp_Explorer i(aBoxMaker.Shape(), TopAbs_EDGE); i.More(); i.Next())
                {
                    aBuilder.Add(aCompound, i.Current());
                }
            }
            catch (Standard_Failure f)
            {
            }
        }
        else
        {
            // leaves node.
            const BVH_Vec3d& aP1 = aBvh->MinPoint(i);
            const BVH_Vec3d& aP2 = aBvh->MaxPoint(i);

            try
            {
                BRepPrimAPI_MakeBox aBoxMaker(gp_Pnt(aP1.x(), aP1.y(), aP1.z()),
                    gp_Pnt(aP2.x(), aP2.y(), aP2.z()));

                aBuilder.Add(aCompound, aBoxMaker.Shape());
            }
            catch (Standard_Failure f)
            {
            }
        }
    }

    BRepTools::Write(aCompound, "d:/bvh.brep");
}

int main(int argc, char* argv[])
{
    if (argc > 1)
    {
        testBvh(argv[1]);
    }

    return 0;
}

由上述代碼可知,當得到節點信息

const BVH_Vec4i& aNodeData = aBvh->NodeInfoBuffer()[i];

后,通過判斷aNodeData.x()分量來確定此節點是內部節點還是葉子節點。顯示OCC自帶的螺旋槳模型的BVH如下圖所示:

wps9772.tmp

wps9773.tmp

其中紅色線框為內部節點,黃色實體模型是葉子節點。

wps9774.tmp

wps9775.tmp

4.BVH Application

BVH在OpenCASCADE中也有廣泛地應用,如開源版本中的模型快速碰撞檢測,使用類BRepExtrema_ShapeProximity. 模型選擇操作,光線跟蹤等算法中都有應用。

5.Conclusion

因為OpenCASCADE中構造BVH時依賴模型的網格三角形,所以BVH算法的應用的結果就依賴于網格化算法的質量了。如兩個Topo形狀碰撞檢測時,網格化的質量越高,結果精度越高。如果用解析算法去對兩個Topo形狀做碰撞檢測,也會涉及到解析算法的精度問題。

BVH結構廣泛應用于碰撞檢測、光線跟蹤等算法中,大大提高程序性能。本文只是拋磚引玉,對BVH感興趣的童鞋可以參考相關資料及OpenCASCADE中的代碼實現,去深入學習應用。

6.References

1. Dmitry Sopin, Denis Bogolepov, Danila Ulyanov. Real-Time SAH BVH Construction for Ray Tracing Dynamic Scenes. http://graphicon.ru/html/2011/conference/gc2011Sopin.pdf

2. BVH with SAH. http://www.cnblogs.com/lookof/p/3546320.html

3. 3D游戲引擎中常見的三維場景管理方法. http://www.cnblogs.com/wangchengfeng/p/3495954.html

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            久久免费99精品久久久久久| 亚洲小说欧美另类社区| 久久国产精品一区二区三区| 亚洲午夜电影| 国产一区二区| 欧美不卡在线视频| 欧美激情在线| 亚洲欧美日韩在线不卡| 久久国产精彩视频| 亚洲美女区一区| 亚洲专区一区二区三区| 极品日韩久久| 亚洲精品四区| 国产九九精品视频| 亚洲国产cao| 国产精品扒开腿做爽爽爽视频| 欧美一级视频精品观看| 免费在线国产精品| 性欧美暴力猛交另类hd| 久久蜜臀精品av| 午夜精品999| 免费毛片一区二区三区久久久| 亚洲一区二区三区免费观看| 欧美一区亚洲一区| 亚洲视屏一区| 欧美xxxx在线观看| 欧美在线看片a免费观看| 久久久久久久久久码影片| 999亚洲国产精| 久久久精品欧美丰满| 9l国产精品久久久久麻豆| 校园春色国产精品| 99在线观看免费视频精品观看| 亚洲特色特黄| 在线看成人片| 欧美一级一区| 亚洲欧美电影院| 欧美a级一区二区| 久久这里只有| 国产农村妇女毛片精品久久莱园子 | 亚洲精品久久7777| 精品69视频一区二区三区| aaa亚洲精品一二三区| 亚洲国产成人精品女人久久久| 亚洲一区二区三区四区五区黄| 亚洲巨乳在线| 美女在线一区二区| 久热国产精品视频| 国产一区二区三区黄视频| 亚洲一卡二卡三卡四卡五卡| 亚洲精品在线免费| 女人香蕉久久**毛片精品| 久久婷婷激情| 狠狠色综合色区| 久久精品色图| 久久久之久亚州精品露出| 国产精品午夜春色av| 亚洲视频综合在线| 亚洲自拍偷拍视频| 毛片基地黄久久久久久天堂| 欧美日韩国产丝袜另类| 亚洲视频免费看| 亚洲激情欧美| 亚洲最黄网站| 伊人成人开心激情综合网| 这里只有精品视频在线| 亚洲午夜精品久久| 欧美午夜视频一区二区| 亚洲精品激情| 一本色道久久综合| 欧美高清视频一区| 亚洲人人精品| 亚洲欧美日韩一区二区在线| 欧美午夜精品理论片a级大开眼界| 99国产精品自拍| 亚洲欧美日本精品| 国产亚洲人成a一在线v站 | 欧美日韩中文| 在线视频免费在线观看一区二区| 亚洲欧美中日韩| 国精品一区二区| 欧美freesex交免费视频| 欧美激情综合色| 亚洲一区精彩视频| 国产香蕉97碰碰久久人人| 久久激情婷婷| 亚洲精品久久久久久下一站| 亚洲欧美精品伊人久久| 国产一区亚洲一区| 欧美韩国日本综合| 亚洲欧美视频在线观看视频| 蜜臀av一级做a爰片久久| 亚洲乱码国产乱码精品精| 欧美体内谢she精2性欧美| 性高湖久久久久久久久| 欧美国产日本在线| 午夜精品视频| 91久久精品视频| 国产日韩欧美在线播放| 欧美激情日韩| 性欧美暴力猛交69hd| 亚洲国产成人久久综合| 欧美亚洲一区| 在线亚洲欧美| 亚洲黄色高清| 国产自产v一区二区三区c| 欧美精品九九| 久久躁日日躁aaaaxxxx| 亚洲天堂av在线免费| 欧美电影在线播放| 久久er精品视频| 国产精品99久久久久久人| 伊人婷婷久久| 国产一区二区三区四区老人| 欧美日韩国产91| 欧美.com| 老鸭窝毛片一区二区三区| 亚洲在线1234| 一本一道久久综合狠狠老精东影业| 美脚丝袜一区二区三区在线观看 | 亚洲天堂视频在线观看| 亚洲国产1区| 韩国av一区二区三区四区| 欧美特黄一级| 欧美三日本三级少妇三2023| 美日韩精品免费| 久久一区二区视频| 久久久久国产精品人| 欧美一区日本一区韩国一区| 一区二区三区高清视频在线观看| 亚洲国产精品一区二区第一页| 裸体丰满少妇做受久久99精品 | 亚洲免费不卡| 99人久久精品视频最新地址| 亚洲激情电影在线| 亚洲国产精品成人综合色在线婷婷| 国产婷婷精品| 国产综合色产| 国内精品久久久久影院优| 国产欧美日韩| 国产性做久久久久久| 国产午夜久久| 影音国产精品| 亚洲精品一区在线观看香蕉| 亚洲国产毛片完整版| 亚洲大胆视频| 亚洲国产精品一区二区第一页| 亚洲第一黄网| 亚洲人精品午夜| 一区二区三区四区蜜桃| 亚洲一区免费看| 欧美在线视频免费| 开心色5月久久精品| 欧美成人精品激情在线观看| 欧美国产极速在线| 日韩视频在线一区| 亚洲综合国产激情另类一区| 亚洲欧美综合| 模特精品在线| 欧美天天视频| 国内精品久久久久久久97牛牛| 激情综合中文娱乐网| 亚洲青涩在线| 午夜精品在线视频| 美女国产一区| 夜夜精品视频一区二区| 午夜精品久久久久久久99水蜜桃 | 一本色道久久综合精品竹菊| 亚洲欧美日本精品| 久久先锋影音av| 亚洲看片免费| 久久福利影视| 欧美私人网站| 在线免费高清一区二区三区| 夜夜狂射影院欧美极品| 欧美专区一区二区三区| 欧美激情欧美激情在线五月| 日韩视频中文| 久久九九热re6这里有精品| 欧美黄色大片网站| 国产三级精品在线不卡| 亚洲国产精品福利| 性色av一区二区三区| 久久这里只有| 一本色道久久88亚洲综合88| 西瓜成人精品人成网站| 媚黑女一区二区| 国产亚洲观看| 亚洲新中文字幕| 亚洲第一色中文字幕| 亚洲图中文字幕| 欧美日韩国产精品 | 欧美日韩免费| 亚洲第一黄网| 久久国产福利| 亚洲视频在线播放| 欧美大片在线观看一区| 国产伪娘ts一区| 午夜久久久久久| 亚洲理论在线观看|