• Login
    View Item 
    •   Eurographics DL Home
    • Computer Graphics Forum
    • Volume 39 (2020)
    • 39-Issue 7
    • View Item
    •   Eurographics DL Home
    • Computer Graphics Forum
    • Volume 39 (2020)
    • 39-Issue 7
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Robust Computation of 3D Apollonius Diagrams

    Thumbnail
    View/Open
    v39i7pp043-055.pdf (30.43Mb)
    Date
    2020
    Author
    Wang, Peihui
    Yuan, Na
    Ma, Yuewen
    Xin, Shiqing
    He, Ying ORCID
    Chen, Shuangmin ORCID
    Xu, Jian
    Wang, Wenping
    Pay-Per-View via TIB Hannover:

    Try if this item/paper is available.

    Metadata
    Show full item record
    Abstract
    Apollonius diagrams, also known as additively weighted Voronoi diagrams, are an extension of Voronoi diagrams, where the weighted distance is defined by the Euclidean distance minus the weight. The bisectors of Apollonius diagrams have a hyperbolic form, which is fundamentally different from traditional Voronoi diagrams and power diagrams. Though robust solvers are available for computing 2D Apollonius diagrams, there is no practical approach for the 3D counterpart. In this paper, we systematically analyze the structural features of 3D Apollonius diagrams, and then develop a fast algorithm for robustly computing Apollonius diagrams in 3D. Our algorithm consists of vertex location, edge tracing and face extraction, among which the key step is to adaptively subdivide the initial large box into a set of sufficiently small boxes such that each box contains at most one Apollonius vertex. Finally, we use centroidal Voronoi tessellation (CVT) to discretize the curved bisectors with well-tessellated triangle meshes. We validate the effectiveness and robustness of our algorithm through extensive evaluation and experiments. We also demonstrate an application on computing centroidal Apollonius diagram.
    BibTeX
    @article {10.1111:cgf.14125,
    journal = {Computer Graphics Forum},
    title = {{Robust Computation of 3D Apollonius Diagrams}},
    author = {Wang, Peihui and Yuan, Na and Ma, Yuewen and Xin, Shiqing and He, Ying and Chen, Shuangmin and Xu, Jian and Wang, Wenping},
    year = {2020},
    publisher = {The Eurographics Association and John Wiley & Sons Ltd.},
    ISSN = {1467-8659},
    DOI = {10.1111/cgf.14125}
    }
    URI
    https://doi.org/10.1111/cgf.14125
    https://diglib.eg.org:443/handle/10.1111/cgf14125
    Collections
    • 39-Issue 7

    Eurographics Association copyright © 2013 - 2023 
    Send Feedback | Contact - Imprint | Data Privacy Policy | Disable Google Analytics
    Theme by @mire NV
    System hosted at  Graz University of Technology.
    TUGFhA
     

     

    Browse

    All of Eurographics DLCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    LoginRegister

    Statistics

    View Usage Statistics

    BibTeX | TOC

    Create BibTeX Create Table of Contents

    Eurographics Association copyright © 2013 - 2023 
    Send Feedback | Contact - Imprint | Data Privacy Policy | Disable Google Analytics
    Theme by @mire NV
    System hosted at  Graz University of Technology.
    TUGFhA