共查询到20条相似文献,搜索用时 171 毫秒
1.
BSP树是图形学领域中用来加速大规模场景计算的重要手段之一.经典BSP树的构造策略是以形体表面的三角形本身作为分割平面,使得树的复杂度非常高,预处理时间长,所以一般适合于室内场景的渲染或碰撞检测.这里针对由许多小模型组成的大规模室外场景的渲染,给出一种构造物体级BSP树并利用其进行渲染的方法.这种方法在视点改变时无需更改BSP树,在视野范围不大的情况下,可以极大地提高渲染速度.实验结果证明了这种方法的有效性. 相似文献
2.
加快光线跟踪计算的网格优化划分 总被引:2,自引:0,他引:2
网格是一类重要的光线跟踪加速结构,其结构简单、能快速创建.但是网格划分的尺度对光线跟踪的效率有很大的影响.针对此,提出一种代价预估计算方法.以度量网格划分对光线跟踪计算效率的影响,并由此计算网格优化划分的分辨率,首先根据模型类型和网格使用方式计算几种场景参数,分别预估网格创建、跟踪和空间的开销;然后根据不同应用需求,以相应的预估代价最小来进行网格的优化划分.与已有方法不同,文中方法考虑了场景中面片分布类型对网格划分的影响,提高了度量计算的精度;还综合考虑了网格创建时间、空间需求等因素,以便度量计算能根据绘制任务的不同进行相应的优化处理.该方法能更好地提高绘制效率,特别是能处理动态场景和面片非均匀分布的复杂场景,而这些是已有方法难以处理的.实验结果表明,文中方法的预估网格优化分辨率与实际的最优分辨率很接近,优于已有的类似工作. 相似文献
3.
4.
5.
根据原始网格对细分极限曲面的影响分析,提出了基于laplacian坐标修正的sqrt(3)插值网格细分方法。通过插值出面片中心点的laplacian坐标,来对动态生成的中心点进行修正,达到保持原始网格细节的目的。在非封闭网格的边界面片细分方面,指出了原始3细分法的不足,提出了一种新的边界统一细分模式,它可以很好地控制边界面片的增长,而且具有稳定性和易于操作性。实验结果表明,该方法不仅能够让原始网格的细节在极限曲面上得到表达,而且可以得到一个连续光滑的曲面网格。 相似文献
6.
7.
文中描述了基于网格BSP系统BSP-G的设计和实现。BSP-G并行库利用网格中间件GlobusToolkit2.0提供的各种网格协议和服务,进行进程启动、监视、控制、身份认证、授权、资源分配、可执行程序的自动传送(Stage)。它使得用户能够在网格上直接运行BSP程序而无需关心网格接口的一些细节问题。最后给出了BSP-G的测试结果。 相似文献
8.
9.
根据原始网格对细分极限曲面的影响分析,提出了基于laplacian坐标修正的3~(1/2)插值网格细分方法。通过插值出面片中心点的laplacian坐标,来对动态生成的中心点进行修正,达到保持原始网格细节的目的。在非封闭网格的边界面片细分方面,指出了原始3~(1/2)细分法的不足,提出了一种新的边界统一细分模式,它可以很好地控制边界面片的增长,而且具有稳定性和易于操作性。实验结果表明,该方法不仅能够让原始网格的细节在极限曲面上得到表达,而且可以得到一个连续光滑的曲面网格。 相似文献
10.
11.
目的 结构化重建,即从离散点云或者原始三角网格中提取几何平面并将其拼接成紧凑的参数化3维模型,一直是计算机图形学领域中极具挑战性的问题。现有方法通常面临着两个挑战。一是传统的形状检测方法通常只考虑物体的局部特征,无法保证整体结果的准确性。二是现有的形状拼接算法往往受限于计算复杂度,从而只能处理由一百多个几何平面组成的物体,极大地限制了算法的应用场景。针对这些问题,提出了一种快速、鲁棒的结构化重建算法以自动地生成轻量的多边形网格。方法 提出了一种多源区域增长算法,全局地从原始3维数据中提取特征平面。该策略保证了原始数据可以被正确地聚类到所属的平面区域。为了减轻几何平面分割3维空间带来的计算负担,采用了一种基于二叉空间分割树的结构将3维空间切分为凸多面体。提出了一种基于光线射击的马尔可夫能量方程以提取水密、无自相交的多边形网格。结果 实验结果表明,本文方法可以在没有并行化方案的标准计算机上处理由上万个几何平面组成的物体。与传统的全相交分割相比,本文方法得到的多面体数目和运行时间都降低了至少两个数量级,总耗时可控制在5 s/万点以内。此外,模型化简前后的均方根误差平均控制在1%以内,面片化简比例控制在1.5%以内。结论 本文方法在计算效率以及结果的准确性上均取得了较大的进步,能够恢复有部分缺陷的表面模型,保留重要结构细节,在复杂性和保真度之间提供了一种较好的方案。 相似文献
12.
The Priority Face Determination Tree for Hidden Surface Removal 总被引:1,自引:0,他引:1
Many virtual environments are built from a set of polygons that form the basis of objects in the scene. Using priority-list algorithms, the sequence in which these polygons are drawn is dependent upon the location of an observer; the polygons must be ordered correctly before a realistic image can be displayed. It is necessary for a scene to be drawn correctly in real time from all locations before the observer can move interactively around the scene with complete freedom.
The binary-space partitioning (BSP) tree developed by Fuchs, Kedem and Naylor in 1980 stores the view independent priority of a set of polygons which can be used to obtain the correct order for any given view-point. However, the number of polygons grows significantly due to the BSP splitting stage, increasing the number of nodes in the tree. This affects linearly the number of tests necessary to traverse the tree to obtain the priority of the set of polygons.
The algorithm presented here is built using its associated BSP tree, but attempts to reduce the number of tests to, log4/3 n , at the cost of a tree of size of O ( N 1.5log4/3 n −1 ), where n is the initial number of polygons in the scene, and N the resulting number after BSP splitting. To achieve the increase in run-time efficiency, a height plane is used to restrict the view point of the observer to a fixed height, but the key to the efficiency of the algorithm is in the use of polygonal dependencies . In the scene; if we know our location relative to the front or back of a polygon, then our position relative to one-quarter of the remaining polygons, in the expected worst-case, can be determined. 相似文献
The binary-space partitioning (BSP) tree developed by Fuchs, Kedem and Naylor in 1980 stores the view independent priority of a set of polygons which can be used to obtain the correct order for any given view-point. However, the number of polygons grows significantly due to the BSP splitting stage, increasing the number of nodes in the tree. This affects linearly the number of tests necessary to traverse the tree to obtain the priority of the set of polygons.
The algorithm presented here is built using its associated BSP tree, but attempts to reduce the number of tests to, log
13.
Fu CW Wong TT Tong WS Tang CK Hanson AJ 《IEEE transactions on visualization and computer graphics》2004,10(1):58-71
We propose a novel 2D representation for 3D visibility sorting, the binary-space-partitioned image (BSPI), to accelerate real-time image-based rendering. BSPI is an efficient 2D realization of a 3D BSP tree, which is commonly used in computer graphics for time-critical visibility sorting. Since the overall structure of a BSP tree is encoded in a BSPI, traversing a BSPI is comparable to traversing the corresponding BSP tree. BSPI performs visibility sorting efficiently and accurately in the 2D image space by warping the reference image triangle-by-triangle instead of pixel-by-pixel. Multiple BSPIs can be combined to solve "disocclusion," when an occluded portion of the scene becomes visible at a novel viewpoint. Our method is highly automatic, including a tensor voting preprocessing step that generates candidate image partition lines for BSPIs, filters the noisy input data by rejecting outliers, and interpolates missing information. Our system has been applied to a variety of real data, including stereo, motion, and range images. 相似文献
14.
15.
Suresh S. Omkar S.N. Mani V. 《Parallel and Distributed Systems, IEEE Transactions on》2005,16(1):24-34
This work presents an efficient mapping scheme for the multilayer perceptron (MLP) network trained using back-propagation (BP) algorithm on network of workstations (NOWs). Hybrid partitioning (HP) scheme is used to partition the network and each partition is mapped on to processors in NOWs. We derive the processing time and memory space required to implement the parallel BP algorithm in NOWs. The performance parameters like speed-up and space reduction factor are evaluated for the HP scheme and it is compared with earlier work involving vertical partitioning (VP) scheme for mapping the MLP on NOWs. The performance of the HP scheme is evaluated by solving optical character recognition (OCR) problem in a network of ALPHA machines. The analytical and experimental performance shows that the proposed parallel algorithm has better speed-up, less communication time, and better space reduction factor than the earlier algorithm. This work also presents a simple and efficient static mapping scheme on heterogeneous system. Using divisible load scheduling theory, a closed-form expression for number of neurons assigned to each processor in the NOW is obtained. Analytical and experimental results for static mapping problem on NOWs are also presented. 相似文献
16.
17.
将显示平面分成多个区域,对组成场景模型的三角面片按区域进行重组,仿真时仅对图形发生变化的区域进行重绘.着重探讨了三角面片区域判定、虚拟场景部件遍历及重绘区域判定三个方面的问题,并给出了详细的改进算法.此外,文中还就区域粒度对算法性能的影响作了实验分析.该算法已应用于虚拟加工原型系统VMS中,显著地提高了加工仿真的速度. 相似文献
18.
We present a new data structure for object space partitioning that can be represented completely implicitly. The bounds of each node in the tree structure are recreated at run‐time from the scene objects contained therein. By applying a presorting procedure to the geometry, only a known fraction of the geometry is needed to locate the bounding planes of any node. We evaluate the impact of the implicit bounding plane representation and compare our algorithm to a classic bounding volume hierarchy. Though the representation is completely implicit, we still achieve interactive frame rates on commodity hardware. 相似文献
19.
20.
Jinho Lee Lance C. Burton Raghu Machiraju Donna S. Reese 《Computer Animation and Virtual Worlds》2005,16(1):53-68
Domain decomposition is a popular technique for solving large computational problems that require data to be divided into smaller sub‐domains. The exact manner of decomposition depends on the computational needs of the algorithm and often introduces irregular boundaries. Each subdomain forms a block of a larger grid and can be solved or rendered separately by different processing nodes. Rendering of each sub‐domain can result in images which are then composited in a back‐to‐front or front‐to‐back manner. This scenario is useful when visualization is used concurrently with the simulation. However, the irregularity of boundaries may prohibit the correct image composition due to a visibility anomaly between the sub‐domains. In this paper, we present an algorithm based on object‐space partitioning to resolve this problem. To accelerate the partitioning process, two techniques are introduced. First, an image‐space partition representation is employed for fast assignment of data points to correct partitions. Secondly, a k‐d tree is used to subdivide the view‐space adaptively according to the complexity of the surface. This view‐space partition provides a trade‐off between performance and accuracy of the rendered image. Large gains in performance can be achieved with only small losses of accuracy. Two examples of curvilinear grids of different complexity are used to demonstrate the effectiveness of this scheme. Copyright © 2005 John Wiley & Sons, Ltd. 相似文献