Abstract
Visualization of large dynamic scenes is a challenging computer graphics problem. There are many approaches to solving this problem: frustum culling, occlusion culling, geometry simplification, and rendering optimization. One of the effective methods is the levels of detail (LOD) for scene objects. For large scenes, the hierarchical LOD (HLOD), whereby the levels of detail are created for large groups of objects, has proven efficient. However, this method faces certain difficulties when processing dynamic scenes. In this paper, we propose a method for visualizing scenes with deterministic dynamics that is based on hierarchical dynamic levels of detail (HDLOD). We also describe methods for generating HDLOD clusters and their visualization. Results of computational experiments conducted confirm high efficiency and practical potential of the proposed method.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.REFERENCES
Luebke, D. et al., Level of Detail for 3D Graphics, San Francisco: Morgan Kaufmann, 2003.
Garland, M. and Heckbert, P.S., Surface simplification using quadric error metrics, Proc. 24th Annu. Conf. Computer Graphics and Interactive Techniques (SIGGRAPH), 1997, pp. 209–216.
Erikson, C. et al., HLODs for faster display of large static and dynamic environments, Proc. Symp. Interactive 3D Graphics (I3D), 2001, pp. 111–120.
Lilley, S. and Cozzi, P., Cesium 3D tiles: Beyond 2D tiling, 2016. https://cesium.com/presentations/files/FOSS4GNA2016/3DTiles.pdf.
Toledo, L. et al., Hierarchical level of detail for varied animated crowds, Visual Comput., 2014, vol. 30, nos. 6–8, pp. 949–961.
Cohen-Or, D., Chrysanthou, Y.L., Silva, C.T., and Durand, F., A survey of visibility for walkthrough applications, IEEE Trans. Visualization Comput. Graphics, 2003, vol. 9, no. 3, pp. 412–431.
Bittner, J. et al., Coherent hierarchical culling: Hardware occlusion queries made useful, Comput. Graphics Forum, 2004, vol. 23, no. 3, pp. 615–624.
Guthe, M. et al., Near optimal hierarchical culling: Performance driven use of hardware occlusion queries, Proc. Eurographics Symp. Rendering, 2006, pp. 207–214.
Mattausch, O. et al., CHC++: Coherent hierarchical culling revisited, Comput. Graphics Forum, 2008, vol. 27, pp. 221–230.
Xu, D. and Tian, Y., A comprehensive survey of clustering algorithms, Ann. Data Sci., 2015, vol. 2, pp. 165–193.
Samet, H., Foundations of Multidimensional and Metric Data Structures, San Francisco: Morgan Kaufmann, 2006.
Morozov, S. et al., Indexing of hierarchically organized spatial-temporal data using dynamic regular octrees, Lect. Notes Comput. Sci., 2018, vol. 10742, pp. 276–290.
Lorach, T., OpenGL NVIDIA command-list: Approaching zero driver overhead, 2014. https://on-demand.gputechconf.com/siggraph/2015/presentation/SIG1512-Tristan-Lorach.pdf.
Bennett, J. and Carter, M., Performance gains achieved through modern OpenGL in the Siemens DirectModel rendering engine, 2015. http://on-demand.gputechconf.com/gtc/2015/presentation/S5387-Jeremy-Bennett.pdf.
Gonakhchyan, V., Efficient command buffer recording for accelerated rendering of large 3D scenes, Proc. 12th Int. Conf. Computer Graphics, Visualization, Computer Vision, and Image Processing, 2018, pp. 397–402.
Author information
Authors and Affiliations
Corresponding authors
Additional information
Translated by Yu. Kornienko
Appendices
PSEUDOCODE OF THE HDLOD VISUALIZATION ALGORITHM
PROCEDURE DISPLAY_CLUSTER(CLUSTER n, VIEW v, TIME t, RESOLUTION r)
{
IF (VALUE_OF(BEHAVIOR_FUNCTION(n), t) EQUAL 0)
RETURN
ELSEIF (IS_OUTSIDE_FRUSTUM(BOUNDING_BOX(n), v))
RETURN
ELSE IF (VALUE_OF(DELTA_FUNCTION(n), t) / DISTANCE(n, v) < r)
{
IF (VALUE_OF(BEHAVIOR_FUNCTION(n), t) >= 0.5)
RENDER(GEOMETRY(n), v))
ELSE
RETURN
}
ELSE
{
SET_OF_CLUSTER children = CHILDREN_NODES(n)
FOR_EACH (CLUSTER child IN children)
DISPLAY_CLUSTER(child, v, t, r)
}
}
PSEUDOCODE OF THE ALGORITHM FOR CLUSTERING PSEUDO-DYNAMIC OBJECTS
PROCEDURE GENERATE_HDLOD(SCENE scene, INTEGER levels, HDLOD tree)
{
SET_OF_CLUSTER active = NULL, next = NULL
FOR_EACH (OBJECT object IN OBJECTS(scene))
{
CLUSTER cluster = FORM_CLUSTER(object)
ADD_TO(cluster, tree)
ADD_TO(cluster, active)
}
FOR_EACH (INTEGER step = 1 TO levels)
{
REAL epsilon, gamma, w
COMPUTE_LEVEL_THRESHOLDS(scene, levels, step, epsilon, gamma, w)
WHILE (NOT_EMPTY(active))
{
CLUSTER representative = SELECT_REPRESENTATIVE(active)
SET_OF_CLUSTER neighbors = FIND_NEIGHBORS(active,
representative, gamma, w)
IF (IS_EMPTY(neighbors))
{
ADD_TO(representative, next)
REMOVE_FROM(representative, active)
}
ELSE
{
SET_OF_CLUSTER children
ADD_TO(representative, children)
FOR_EACH(CLUSTER neighbor IN neighbors)
ADD_TO(neighbor, children)
CLUSTER cluster = CREATE_CLUSTER(children)
SIMPLIFY (cluster, epsilon)
ADD_TO(cluster, tree)
ADD_TO(cluster, next)
REMOVE_FROM(representative, active)
FOR_EACH (CLUSTER neighbor IN neighbors)
REMOVE_FROM(neighbor, active)
}
COPY(next, active)
EMPTY(next)
}
}
Rights and permissions
About this article
Cite this article
Semenov, V.A., Shutkin, V.N., Zolotov, V.A. et al. Visualization of Large Scenes with Deterministic Dynamics. Program Comput Soft 46, 223–232 (2020). https://doi.org/10.1134/S036176882003007X
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1134/S036176882003007X