Show simple item record

dc.contributor.authorWang, Peihuien_US
dc.contributor.authorYuan, Naen_US
dc.contributor.authorMa, Yuewenen_US
dc.contributor.authorXin, Shiqingen_US
dc.contributor.authorHe, Yingen_US
dc.contributor.authorChen, Shuangminen_US
dc.contributor.authorXu, Jianen_US
dc.contributor.authorWang, Wenpingen_US
dc.contributor.editorEisemann, Elmar and Jacobson, Alec and Zhang, Fang-Lueen_US
dc.description.abstractApollonius 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.en_US
dc.publisherThe Eurographics Association and John Wiley & Sons Ltd.en_US
dc.titleRobust Computation of 3D Apollonius Diagramsen_US
dc.description.seriesinformationComputer Graphics Forum
dc.description.sectionheadersGeometry and Modeling

Files in this item


This item appears in the following Collection(s)

  • 39-Issue 7
    Pacific Graphics 2020 - Symposium Proceedings

Show simple item record