Grand Prize

Duality
Masanori Nakayama, Issei Fujishiro

Masanori Nakayama, Issei Fujishiro “Duality” 2017, Material: VeroWhite, Size: 246W x 120D x 189H (mm)In the present work, we attempted at expressing human “two-facedness” by the “two-sidedness” of the 3D structures. In the field ofgeometry, there exists a two-facedness called “duality,” which represents the relationship between diagrams that switch between faces(cells) and vertices. Delaunay diagram and Voronoi diagram give a typical example. We have developed an algorithm to generate aPoisson-disk distribution in an arbitrary shape to make sculptures with those diagrams. The Delaunay diagram generated by Poissondisk distribution point cloud makes up the uniform tetrahedral mesh (except for the surface). Since those cells are close to a regulartetrahedron, Voronoi vertices located on the circumcenters also have an almost uniform distribution.

8

Grand Prize

Keywords: Tetrahedralization, Delaunay diagram, Voronoi diagram

1 Concept

region into a uniform triangular mesh with Poisson disk

We have worked on an optimal subdivision algorithm todistribution (Fig. 1). By embedding the 2D Delaunay

discretize a given arbitrary shape. In 2D, we built on

diagram in 3D, we succeeded to subdivide an arbitrary closed

Delaunay diagram to subdivide an arbitrary closed curve

surface volume into a tetrahedral mesh with Poisson disk9

Grand Prize

Figure 1: Poisson-disk triangulation.

distribution (Fig. 2). In comparison with Guo’s prior work[2], the incorporated non-polygonal isosurfacing increases
the versatility in terms of input volume, simplifies meshingsteps, and improves the quality of output meshes.
All of our works root commonly in the “duality” of Delaunay
diagram and Voronoi diagram―both structures are mutuallyconvertible by swapping the roles of faces and vertices. In
the present work, we attempted at expressing human “two-Figure 2: Poisson-disk tetrahedralization.

facedness” with the “two-sidedness” of the two diagrams.

shape. Fig. 3 simply represents this in 2D.

2 How to Make

Next, we add points only in the inside region. Note that in

There exists a de facto standard tetrahedralization libraryorder to uniformly distribute vertices, we should not insert

called Tetgen [3]. For edgy curve surfaces that can bethem randomly. For each tetrahedron, we search for thedefined in a piecewise manner, a specific type oflargest circumscribed sphere, and insert a point at the centertetrahedralization algorithm was devised in [4].

of the sphere (Fig. 4). The position of the point is nothing

In our tetrahedralization scheme, we first generate aless than the vertex of the Voronoi diagram, indicating theDelaunay diagram with vertices on the target’s surface, andmost distant location from the existing points in the largest

thereby making separate inside and outside of the target

blank area.

10Grand Prize

Figure 3: Delaunay diagram of edge points.

By repeating the process, the vertex distribution automatically converges to a Poisson disk distribution, and resulting in

Figure 4: Voronoi vertices in empty circle.

the most uniform tetrahedral mesh. Variational tetrahedral

Referencesmeshing in [1] can further improve the location of all the[1] P. Alliez, D. Cohen-Steiner, M. Yvinec, M. Desbrun,vertices gradually, but works slowly.

Variational tetrahedral meshing, ACM Transactions on

In the process, the Voronoi diagram is generated together

Graphics, Vol.24, No.3, pp. 617–625, 2005.

with the Delaunay diagram, whereas the Voronoi diagram[2] J. Guo, D. Yan, L. Chen, Tetrahedral meshing via maxi-itself has no utility value. In the present work, however, bymal Poisson-disk sampling, Computer Aided Geometricjuxtaposing the two diagrams, we intended to express theDesign, Vol.43, No.C, pp. 186-199, 2016.

interest of geometry.

[3] H. Si, Tetgen, a Delaunay-based quality tetrahedral meshgenerator, ACM Transactions on Mathematical Software.

3 Software & System

Vol.4, No.2, Article 11, 2015.

All the programs have been implemented in the Object Pas-

[4] J. Tournois, C. Wormser, P. Alliez, M. Desbrun, Inter-cal language using an integrated development environment

leaving Delaunay refinement and optimization for practi-

Embarcadero Delphi. For editing/rendering the model, thecal isotropic tetrahedron mesh generation, ACM Transac-

3DCG software Cinema 4D was used.

tions on Graphics, Vol.28, No.3, Article 75, 2009.

11