Learning to Generate 3D Shapes with Generative Cellular Automata
Authors: Dongsu Zhang
Changwoon Choi
Jeonghwan Kim
Young Min Kim
Venue: ICLR 2021 Poster (2021)
Keywords: 3D generation
generative models

Abstract: In this work, we present a probabilistic 3D generative model, named Generative Cellular Automata, which is able to produce diverse and high quality shapes. We formulate the shape generation process as sampling from the transition kernel of a Markov chain, where the sampling chain eventually evolves to the full shape of the learned distribution. The transition kernel employs the local update rules of cellular automata, effectively reducing the search space in a high-resolution 3D grid space by exploiting the connectivity and sparsity of 3D shapes. Our progressive generation only focuses on the sparse set of occupied voxels and their neighborhood, thus enables the utilization of an expressive sparse convolutional network. We propose an effective training scheme to obtain the local homogeneous rule of generative cellular automata with sequences that are slightly different from the sampling chain but converge to the full shapes in the training data. Extensive experiments on probabilistic shape completion and shape generation demonstrate that our method achieves competitive performance against recent methods.

Published as a conference paper at ICLR 2021
LEARNING TO GENERATE 3D SHAPES WITH GENERATIVE CELLULAR AUTOMATA
Dongsu Zhang, Changwoon Choi, Jeonghwan Kim & Young Min Kim Department of Electrical and Computer Engineering, Scoul National University (961 i ives, zzzmaster, whitealex youngmin, kim) @snu a a... kr
ABSTRACT
We present a probabilistic 3D generative model, named Generative Cellular Au- tomata, which is able to produce diverse and high quality shapes. We formulate the shape generation process as sampling from the transition kernel of a Markov chain, where the sampling chain eventually evolves to the full shape of the learned distribution. The transition kernel employs the local update rules of cellular au- tomata, effectively reducing the search space in high-resolution 3D grid space by exploiting the connectivity and sparsity of 3D shapes. Our progressive generation only focuses the sparse set of occupied voxels and their neighborhood, thus enabling the utilization of an expressive sparse convolutional network. We propose effective training scheme obtain the local homogeneous rule of generative cellular automata with sequences that are slightly different from the sampling chain but converge the full shapes in the training data. Extensive experiments on probabilistic shape completion and shape generation demonstrate that our method achieves competitive performance against recent methods.
INTRODUCTION
Probabilistic 3D shape generation aims learn and sample from the distribution of diverse 3D shapes and has applications including 3D contents generation or robot interaction. Specifically, learning the distribution of shapes or scenes can automate the process of generating diverse and realistic virtual environments or new object designs. Likewise, modeling the conditional distribution of the whole scene given partial raw 3D scans can help the decision process of a robot, by informing various possible outputs of occluded space.
The distribution of plausible shapes in 3D space is diverse and complex, and we seek a scalable formulation of the shape generation process. Pioneering works on 3D shape generation try to regress the entire shape (Dai et al. (2017)) which often fail to recover fine details. We propose a more modular approach that progressively generates shape by sequence of local updates. Our work takes inspiration from prior works on autoregressive models in the image domains, such as the variants of pixelCNN (van den Oord & Kalchbrenner (2016); van den Oord al. 2016 2017)) ). which have been successful in image generation. The key idea of pixeICNN (yan den Oord et al. (2016) is to order the pixels, and then learn the conditional distribution of the next pixel given all of the previous pixels. Thus generating an image becomes the task of sampling pixel-by-pixel in the predefined order. Recently, PointGrow (Sun et al. (0200) proposes similar approach in the field of 3D generation, replacing the RGB values of pixels with the coordinates of points and sampling point-by- by-pint in sequential manner. While the work proposes promising interpretable generation process by sequentially growing shape, the required number of sampling procedures expands linearly with the number of points, making the model hard to scale high-resolution data.
We believe that a more scalable solution in 3D is to employ the local update rules of cellular automata (CA). CA, a mathematical model operating on grid, defines a state to be a collection cells that carries values in the grid (Wolfram) (1982) ). The CA repeatedly mutates its states based on the predefined homogeneous update rules only determined by the spatial neighborhood of the current cell. In contrast the conventional CA where the rules are predefined, we employ neural network to infer the stochastic sequential transition rule of individual cells based on Markov chain. The obtained homogeneous local rule for the individual cells constitutes the 3D generative model, named

---

Published as a conference paper at ICLR 2021
10
220
330
540
550
$60
100
Figure 1: Sampling chain shape generation. Full generation processes are included in the supple- mentary material.
Generative Cellular Automata (GCA). When the rule is distributed into the group of occupied cells of arbitrary starting shape, the sequence of local transitions eventually evolves into instance among the diverse shapes from the multi-modal distribution. The local update rules of CA greatly reduce the search space of voxel occupancy, exploiting the sparsity and connectivity of 3D shapes.
We suggest a simple, progressive training procedure to learn the distribution of local transitions of which repeated application generates the shape of the data distribution. We represent the shape in terms of surface points and store it within a 3D grid, and the transition rule is trained only on the occupied cells by employing a sparse CNN (Graham et al. (2018). The sparse representation can capture the high-resolution context information, and yet learn the effective rule enjoying the expressive power of deep CNN as demonstrated (2012); He et al. (2017)). Inspired by Bordes al. (2017), our model learns sequences that slightly different from the sampling chain but converge to the full shapes in the training data, The network successfully learns the update rules of CA, such that single inference samples from the distribution diverse modes along the surface.
various computer vision tasks (Krizhevsky et al.)
The contributions of the paper highlighted follows: (1) We propose Generative Cellular Automata (GCA), a Markov chain based 3D generative model that iteratively mends the shape to a learned distribution, generating diverse and high-fidelity shapes. (2) Our work is the first learn the local update rules of cellular automata for 3D shape generation in voxel representation. This enables the exploiting sparsity and connectivity of 3D shapes. (3) Extensive experiments show that our method has competitive performance against the state-of-the- models in probabilistic shape completion and shape generation.
an expressive sparse CNN and reduces the search space of voxel occupancy by fully
2 3D SHAPE GENERATION WITH GENERATIVE CELLULAR AUTOMATA
Let Z be an n-dimeensional uniform grid space, where n = 3 for a 3D voxel space. A 3D shape is represented as a state Z which an ordered of occupied cells Z in binary occupancy grid based on the location of the surface. Note that our voxel representation is different from the conventional occupancy grid, where represents that the cell is inside the surface. Instead, we only store the cells lying the surface. This representation can better exploit the sparsity of 3D shape than the full occupancy grid.
The shape generation process is presented as sequence of state variables 0.7 that is drawn from the following Markov Chain:
5 N~ p s+1 (s*)
(1)
where pd is the initial distribution and pe is the homogeneous transition kernel parameterized by as sampling chain. Given the data set D
We denote the sampled sequence 8 + - .....- containing 3D shapes z E D. our objective is to learn the parameters 0 of transition kernel po. such that the marginal distribution of final generated sample p( E (s(()) [lostr (o (
2

---

Published as a conference paper at ICLR 2021
Pr ((V(c)))))
p2= (c2(s=)))
Sparse
Cellwise
Sample
Conv.
Average
Ps (cs(ss))
Local Update Rules
pss
s##1
Figure 2: Overview GCA. The top shows a probabilistic shape completion sampling chain of chair starting from the partial input. Bottom figures show an illustrative figure of a single transition. Starting from state s' of occupied voxels, we apply sparse CNN to obtain the neighborhood occupancy probability. Then we aggregate the probabilities by cell-wise averaging and sample the next state.
close to the data distribution. The initial state 8 can be defined differently depending on the task to solve. For the task of probabilistic shape completion, 5 is given the partial input shape. For shape generation, we set the initial state s to be the most simple state we can think of, single cell {c). Figure presents examples of sampling chains of shape generation, where the starting shape s is merely a single cell.
The GCA further splits the transition kernel (s* be the combination of local update rules on individual occupied cells E s", as depicted in Figure The cellular transition is implemented with the sparse convolution, which is translation invariant if implemented with fully convolutional network, and outputs the distribution of local occupied cells. Then individual predictions are aggregated by cell-wise averaging, resulting in the binary probability distribution for occupancy of each cell that follows the Bernoulli distribution:
(s() = II po(c)s*).
(2)
eE
The next state gf+1 is sampled independently for individual cells from the obtained distribution and the sampling chain continues to the next time step.
For each transition ps (s"+) we limit the search space of the occupied cells by confining our predictions within the neighborhood of the occupied cells. The underlying assumption is that the occupied cells of a valid shape are connected and a successful generation is possible by progressive growing into the immediate neighborhood of the given state. Specifically, the output of the sparse convolution is the occupancy probability of neighborhood cells = (o (c:))s)s where the neighborhood cells are those that fall within radius ball centered at the cell, N(c.)) {c' z" d(c;, e') S r given distance metric d. Other cells are ignored assuming they have probability 0 of occupancy. If the input state has M occupied cells sf (c,,.... CMr). J. the sparse convolution predicts the occupancy probability of individual cells with N N-dimension vectors P = {PI..- Pas }. where N is the number of neighborhood cells fixed by the distance threshold within the uniform grid 7 After the cell-wise averaging step, the aggregated probability is nonzero for coordinates in (s* U. (c). Then the cell-wise sampling in Eq. (2) is performed only within Nss)),
instead of the full grid zn, leading to an efficient sampling procedure.
The stochastic local transition rule PP (c)))s) changes the state a cell's immediate neighborhood N(e)), but the inference is determined from larger perception neighborhood. In contrast, classical cellular automata updates a state of a cell determined by fixed rule given the observation of the cell's immediate neighborhood. The large perception neighborhood of GCA is effectively handled by deep sparse convolutional network, and results in convergence to a single consistent global shape out of diverse possible output shapes as further discussed in the appendix F
3

---

Published as a conference paper at ICLR 2021
3 TRAINING GENERATIVE CELLULAR AUTOMATA
We aim to learn the parameters for the local transition probability pa (N(()))s)) whose repetitive application generates shape that follows the complex distribution of the data set. If we have sequences of sampling chains, then all current and next states can serve as the training data. Because we only have the set of complete shapes D, we emulate the sequence of sampling chain and obtain the intermediate states.
The emulated sequence of sampling chain may start from an arbitrary state, and needs to converge to the full shape z E 'D after local transitions to the neighbor of the previous state. A naive method would be to sample the next state s² from the sampling chain and maximize pe(x n (s*)sss") the probability of the shape that is closest to z among reachable forms from the current state similar to scheduled sampling (Bengio et al. (201)). While this approach clearly emulates the inference procedure, it leads to learning a biased estimator pointed out in Huszár (015)). More importantly, the emulated sequence cannot consistently learn the full shape x as it is not guaranteed to visit the state s such that C (s)).
We instead employ the use of infusion training procedure suggested by Bordes et al. (017)) Specifi- ST is obtained as following:
cally, the infusion chain, denoted as 50
+ zz
5 (501)))) (x)
I),
- (1-a") (po(s( + ta' 6EN(3))
II
(3)
where 90 indicates the initial distribution of infusion chain, and q² is the infusion transition kernel at time step t. For probabilistic shape completion 3 is sampled as a subset of z, while for shape generation 5 is single cell E x. The transition kernel g is defined for cells in the neighborhood ē E (5e) as the mixture of po(c(²") and (,), which are the transition kernel of the sampling chain and the infusion of the ground shape x. respectively. (Z) is crucial to guarantee the sequence to ultimately reach the ground truth shape, and is formulated as the Bernoulli distribution with probability 1, if ē E x, else O. We set the infusion rate to increase linearly with respect to time step. i.e., a² max(wt, 1), where w 0 is the speed of infusion rate as in Bordes et al. (2017).
We can prove that the training procedure converges to the shape x the training data if it is composed of weakly connected cells. We first define the connectivity of two states.
Definition 1. We call state s' to be partially connected to state x, for any cell b E x, there is a cell cu 3 O x. and a finite sequence of coordinates CorT, in x that starts with cu and ends with Cn, = b, where each subsequent element is closer than the given threshold distance r, i.e., for any b E x, Boo., such that c, E x, d(c,, 1441) Sr. 0 S i i T. and co E 3', CT, b.
The shape x is partially connected any 8/ * 9 if any pair of cells in x that is composed of local transitions bounded by the distance r. This is a very weak connectivity condition, and any set that overlaps with x is partially connected for shapes with continuous surfaces, which include shapes in the conventional dataset.
create sequence of coordinates between
Now assuming that the state st is partially connected to the state x, we recursively create sequence by defining g1+1 A5*) n x, which the next sequence of infusion chain with infusion rate 1. Since we use linear scheduler for infusion rate, we can assume that there exists a state 3" such that infusion rate a = 1. The following proposition proves that the sequence (5") (3') converges to with local transitions.
Proposition 1. Let state z" be partially connected to state x, where x has a finite number of occupied cells. We denote sequence of states st' recursively defined as g++11 = (3*) O x. Then, there exists an integer T' such that st x, > T".
Proof. The proof is found in the appendix A
The proposition states that the samples of infusion chain eventually converge to the shape æ, and thus we can compute the nonzero likelihood p(z(3²") during training if T' is large enough. One can also interpret the training procedure as learning the sequence of states that converges to x and is close to
Since we defined a state as set of occupied cells, union (U), intersection (N), and subset (C) operations be defined as regular sets.
4

---

Published as a conference paper at ICLR 2021
Imput
GCA
cGAN
Input
GCA
cGAN
Figure 3: Qualitative comparison of probabilistic shape completion.
Figure 4: Samples from shape generation.
the sampling chain. We empirically observe that most the training samples converge to the shape x before the infusion rate becomes
The training procedure can summarized as the following:
1. Sample infusion chain g0:7 from 8 ~ (3"))))) gi-1 15
2. For each state s", maximize the ligeliiel that has the closest form to x via gradient descent, i.e., +- 0 0 log po (=
The full training algorithm utilizes data buffer de-correlate the gradients subsequent time steps, and accelerates the process by controlling the time steps based on the current state. More details regarding full training algorithm can found the appendix
EXPERIMENTS
We demonstrate the ability of GCA generate high-fidelity shapes in two tasks: probabilistic shape completion (Sec. 4.1) and shape generation (Sec. 4.2)
State-of-the-ar works both tasks generate shapes using point cloud whereas ours grid structure. For comparison, we extract high-resolution points from the CAD model and map them into 643 voxel grid, Individual shapes in the dataset centered and uniformly scaled to fit within the cube 1-,, We also present additional analysis on how the sparse representation and local transition of GCA can successfully learn to generate fine resolution shapes with continuous geometry (Sec. 4.3) Details regarding the training settings and baselines are reported in the appendix
4.1 PROBABILISTIC SHAPE COMPLETION
Dataset and implementation details. The probabilistic shape completion tested with PartNet (Mo) et al. (2019) and PartNet-Scan (Wu et al. (2200) dataset, where objects in ShapeNet(Chang et al. (2015) ) are annotated with instance-level parts. For each instance, we identify the input partial object by randomly choosing parts from the complete shape, and generating diverse set of complete shapes. PartNet-Scan dataset simulates the real-world situation where partial scans suffer from part-level incompleteness by randomly selecting parts from the PartNet and virtually scanning the remaining parts. We validate our approach on chair, lamp, and table categories following Wu et al.) (2020). We neighborhood radius = 3, T = 70 with infusion speed 0.005 for all datasets. Following the work of Wu et al. 2202)) for each partial shape in the test set, we generate ten completion results and sample 2,048 points from occupied cells.
We compare the performance of probabilistic shape completion of GCA against cGAN Wu et al. 2202 ) cGAN and its variations (cGAN-im-122 and cGAN-im-pe22) with 3D-IWGAN (mmith
We would like to acknowledge that, when training, eGAN only requires the partial set and complete shape set without any explicit pairing between each of the instances in the set. However, report cGAN the baseline

---

Published as a conference paper at ICLR 2021
PartNet
MMD (quality. L)
TMD (diversity, f)
UHD (fidelity. 4)
Method
Chair
Lamp
Table
Avg.
Chair
Lamp
Table
Avg.
Chair
Lamp
Table
Avg.
3D-IWGAN
1.94
3.57
8.18
4.56
0.99
3.58
1.52
2.03
6.89
8.86
8.07
7.94
cGAN-im-I2z
1.74
2.36
1.68
1.93
3.74
2.68
3.59
3.34
8.41
6.37
7.21
7.33
<GAN-im-pe22
1.90
2.55
1.54
2.00
1.01
0.56
0.51
0.69
6.65
5.40
5.38
5.81
cGAN
1.52
1.97
1.46
1.65
2.75
3.31
3.30
3.12
6.89
5.72
5.56
6.06
GCA
1.28
1.85
1.13
1.42
4.74
9.38
4.50
6.20
6.21
5.96
5.60
5.92
GCA (jint)
1.33
1.89
1.14
1.45
3.69
13.49
4.55
7.24
6.14
6.31
5.59
6,01
PartNet-Scan
MMD (quality. ()
TMD (diversity. 1)
UHD (fidelity. J)
Method
Chair
Lamp
Table
Avg-
Chair
Lamp
Table
AAg..
Chair
Lamp
Table
Avg.
cGAN-im-12z
1.79
2.58
1.92
2.10
3.85
3.18
4.75
3,93
7.88
6.39
7.40
7.22
<GAN-im-pc2e
1.65
2.75
1.84
2.08
1.91
0.50
1.86
1.42
7,50
5.36
5.68
6.18
cGAN
1.53
2.15
1.58
1.75
2.91
4.16
3.88
3.65
6.93
5,74
6.24
6,30
GCA
1.55
1.97
1.57
1.70
1.73
10.61
2.89
5.20
6.15
5.86
5.54
5.85
Table I: Quantitative comparison of probabilistic shape completion results on PartNet (top) and PartNet-Scan (bottom). The best results trained in single class are in bold. Note that MMD (quality). TMD (diversity) and UHD (fidelity) presented in the tables are multiplied by 10 102 and 10², respectively. GCA (joint) denotes GCA trained on all categories combined, but evaluated individually.
& Meger (017 The qualitative results in Figure 3 and the appendix H clearly show that our high- resolution completion exhibits sophisticated geometric details compared to the ofte-of-thheart Our superior performance is further verified in the quantitative results reported in Table I with three metrics: minimal matching distance (MMD), total mutual difference (TMD), and unidirectional Hausdorff distance (UHD). MMD and TMD are reported after generated samples are centered due to translation invariant nature of our model. The detailed description regarding the evaluation metrics are found in the appendix G.3
We outperform all other methods in MMD and TMD on average, and achieve comparable or the best results in UHD. The results indicate that we can generate high fidelity (MMD) yet diverse (TMD) shapes while being loyal to the given partial geometry (UHD). We observe an extremely large variation of completion modes in the lamp dataset, which is the dataset with the most diverse structure while having high level of incompleteness in the input partial data. This is because the lamp dataset contains fragmented small parts that could be selected as an highly incomplete input. We include further discussion about the diversity in the lamp dataset in the appendix E
Multiple category completion. While previous works on shape completion are trained and tested individual categories separately, we also provide the results on training with the entire category, denoted as GCA (joint) in Table [T] The performance of jointly trained transition kernel does not significantly differ to those of independently trained, demonstrating the expressiveness and high capacity of GCA. In addition, interesting behavior arises with the jointly trained GCA. As shown in the left image of F given ambiguous input shape, the completed shape can sometimes exhibit features from categories other than that of the given shape.
Furthermore, GCA is capable of completing a scene composed of multiple objects although it is trained to complete single object (Figure [ right). We believe that this is due the translation invariance and the local transition of GCA. As discussed in Section the deep network observes relatively large neighborhood, but GCA updates the local neighborhood based on multiple layers of sparse convolution which is less affected by distant voxels. The information propagation between layers of sparse convolutional network (Graham et al. (2018) mediated by occupied voxels, which effectively constrains the perception neighborhood to the connected voxels. As a result, the effect of separated objects are successfully controlled. We also include additional examples in the appendix D on how the GCA trained in one category completes the unseen category.
4.2 SHAPE GENERATION
Dataset and implementation details. We test the performance of shape generation using the ShapeNet (Chang et al. (2015) dataset, focusing on the categories with the most number of shapes:
to our method, since this is the most recent probabilistic shape completion. cGAN-im-127 and cGAN-im-pe2z variants of cGAN that implicitly model the multi-modality for probabilistic shape completion.

---

Published as a conference paper at ICLR 2021
Input
Output
Ground Truth
Input
Output
Figure 5: Shape completion results when jointly trained with multiple categories of shapes. Given an ambiguous input shape, features from different categories co-exist (top: lamp table, bottom: lamp + chair) in the completed shape (left). Even though GCA is trained to complete a single object, it can complete scene with multiple partial shapes of different categories (right).
ShapeNet
I-NNA (distance distributions, J)
COV (diversity, 1)
MMD (quality. .)
Method
Airplane
Chair
Avg.
Airplane
Avg.
Airplane
Chair
Avg.
=GNN
95.80
99.29
84,82
93.30
38.52
8.24
19.49
22.08
1.66
6.23
18.19
8.69
GCN
95. 16
86.52
9.38
6.95
2.62
23.10
16.15
3D-IWGAN
94,70
76.60
63.62
78.31
38.02
42.90
45.17
42.03
1.53
4.33
15.71
7.19
PointFlow
83.21
68.75
67.60
73.19
39.51
39.20
40.94
39.88
1.41
4.21
15.03
ShapeGF
85.06
65.48
66.16
72.23
47.65
44.60
46.37
46.21
1.29
4.09
14.82
6.73
GCA
90.62
65.06
65.71
74.85
35,80
46.31
44.56
40.79
1,25
4.19
16.89
7.44
Train set
72.10
52.98
53.93
59.67
45.43
48.30
50.45
48.06
1.29
4.21
15.89
7.13
Table 2: Quantitative comparison results of shape generation on ShapeNet. The best results are in bold. Note that MMD is multiplied by 103.
airplane, car, and chair, as presented in Yang al. (2019) We use the same experimental setup as Cai eet al. (2020), and sample 2,048 points from the occupied cells of the generate shape and center the shape, due to translation invariant aspect of our model, for fair comparison. We neighborhood size r = 2 with L1 distance metric, T = 100 inferences, infusion speed w = 0.005 for airplane and car dataset, and r for chair category, which tend to converge better.
The quantitative results of shape generation are reported in Table We compare the performance of our approach against recent point cloud based methods: r-GAN (Achlioptas al. (2018), GCN-GAN (Valsesia et al. (2019)), Tree-GAN (Shu et al. (2019)), Pointflow Yang et al. (2019)) ShapeGF (Cai ctt al. (ll2())222))))))))1 a voxel-based method: 3D-IWGAN (Smith & Meger (2017)), and training set. The optimal value for each metric. We evaluate
scores assigned to training set can be regarded our model on three metrics, 1 -nnarrst--niihhorr -aiurrrrriighhbrrrruurryyy accuracy (I-NNA), coverage (COV), and minimal matching distance (MMD) as defined in the appendix G.3
Our approach achieves the state-of-the-art results on I-NNA of car category. As remarked by] Yang al. 2019), 1-NNA is superior measuring the distributional similarity between generated set and test set from the perspective of both diversity and quality. Our method also achieves state-of-the-ant the-art results COV of car, implying that method is able to generate diverse results. Note using a homogeneous transition kernel confined within the local neighborhood of occupied cells, but still achieve noticeable performance generating rich distribution of shape. MMD is conventional metric to represent the shape fidelity, but some results achieve scores better than the training set which might be guestionable (Yang et al. (2019)). We visualize our shape generation results in Figure and in the appendix
4.3 ANALYSIS ON NEIGHBORHOOD AND CONNECTIVITY
GCA makes righ-resolution predictions by only handling the occupied voxels and their neighborhood. thus overcoming the limitation of memory requirement of voxel-based representation of 3D shape. In Figure we empirically analyze the required search space during the shape generation process that starts from single cell and evolves to the full shape. The occupied voxels take approximately 2% of
7

---

Published as a conference paper at ICLR 2021
occupied (ear)
neighborhood (car)
occupied (airplanc)
neighborhood (airplane)
occupancy rate (%)
occupied (chaiz)
neighborhood (chair)
$17
220
224
70
100
Figure Completing disconnected shapes. Top, front, and side views of generation pro- cess are shown with = 3, L1 metric neigh- borhood, where the diameter of the lamp- shade is over 30, Given the partial shape of the shade, GCA is able to generate the body of the lamp that disconnected from the input.
time steps
Figure 6: Search space visualization. The graph shows the percentage the occupied voxels (solid lines) and the searched neighborhood vox- els (dashed lines) during 100 time steps of shape generation process.
the total volume (solid lines), and their neighborhood adds up 2-8% (dashed lines). After certain amount of time steps, the growing speed of the search space gradually decreases, implying that our method tends converge and maintain the generated shape.
The large structural variation observed the lamp dataset leads to interesting observation on the neighborhood size of GCA and the connectivity of the shape. When r 1, nearly 10% of the infusion chain data fails to meet the stopping condition (cover more than 95% of æ, see the training detail in 100. This is because GCA trained on small neighborhood size, while enabling the transition kernel to be trained quickly, lacks the flexibility to model disconnected shapes even after large time steps. On the other hand, increased neighborhood size can capture disjoint parts at the expense of larger search space and instability. When 10, the trained transition kernel generates output that noisy or unrelated to the input partial shape. We believe that the transition kernel can not be trained to cover the entire search space the neighborhood size increases cubic to r. few bad sampling steps can lead to state that far from the previous state or unobserved during training. The effects of hyperparameters
the appendix B) with time step
further discussed in the appendix C
We also clarify the notion of connectivity in relation to the neighborhood size. While we mostly demonstrate the performance of GCA generating 3D shapes with continuous surface, GCA can surely generate disjoint parts as long as the distance between parts is within the radius r. Besides, GCA flexible enough to learn generate parts that farther than r. is merely the distance of cells between adjacent steps, and it is possible to learn the sequence of states that generates temporary bridge reach disconnected parts after a few steps. Figure 7 shows sampling chain that generates temporary bridge from the shade to the body of the lamp further than the neighborhood size. After the sampling chain reaches the main body, GCA removes the bridge and successfully generates the full shape.
observed sequence of
RELATED WORKS
5.1 GENERATIVE MODELS
Autoregressive models. PixelCNN and its variants (van den Oord & Kalchbrenner (2016): van den Oord et al. (0166) sequentially sample single pixel value at a time, conditioned on the previously generated pixels. PointGrow (Sun et al. (2020)) extends the idea to 3D by sampling the coordinates of points a sequential manner. While these approaches lead to tractable probabilistic density estimation, inferring
pixel/point with single inference is not scalable to high resolution 3D voxel space. GCA, on the other hand, can grow to the shape occupying any number of voxels the neighborhood each inference.
8

---

Published as a conference paper at ICLR 2021
Markov chain models. Previous works learn the transition kernel of Markov chain operating on the input space which eventually produces samples matching the data distribution (Sohl- Dickstiicsteen et al. (2015); Amirudh et al. (2017), Bordes et al. (2017)) The diffusion- based models
et al. 2015): (nirudh et al. (01 start from a random noise distribution and incrementally denoise the input to generate the data. They learn the reverse of diffusion process, which begins from the data and gradually adds noise to become a factorial noise distribution. On the other hand, the work of infusion training (Bordes et al. (2017)) slightly infuses data to input dimension during training, and learns the chain biased towards the data. This removes the process of inverting the diffusion chain and allows the chain start from any distribution. The training of GCA utilizes the technique of infusion, enabling to train on both shape generation and completion.
3D generative models. Recent works on 3D generative models (Yang al. (2019) Cai al. (2020): :
Wu et al. )2200) achieve noticeable success with point cloud based representation. They are based on PointNet Qi et al. (2016), one of the most widely-used neural network architecture consuming point cloud. PointNet condenses the 3D shape into single global feature vector to achieve permutation invariance, but in turn lacks the representation power of local context observed in deep neural architecture. On the other hand, voxel-based generation methods (Wu et al. (2016); Smith & Meger (2017)) can capture local features by directly adapting a CNN-based architecture, but suffer from immense memory consumption in high-resolution. Recent works of sparse CNN (Graham al. (0188) Choy et al. (2019)) solves the problem of voxel representation by exploiting sparsity, and outperforms other methods by a significant margin in the field of 3D semantic segmentation. To the best of our knowledge, we are the first to utilize the expressive power of sparse CNN to learn a probabilistic 3D generative model in a high-resolution 3D grid.
5.2 CELLULAR AUTOMATA
Cellular automata (CA) is introduced to simulate biological or chemical systems (Wolfram (1982);
Markus & Hess (190)). CA consists of a grid of cells where individual cells are repeatedly updated with the rule depending only on the state of neighborhood cells. Each cell is updated with the same set of local rules, but when the update repeatedly distributed in the entire grid, complex and interesting behavior can emerge. However, CA requires fixed rule to be given. Wulff & Hertz (1992) learn simple rules with a neural network and model the underlying dynamics of CA. Neural Cellular Automata (Mordvintsev al. (2020) shows interesting extension of CA that incorporates neural network to learn the iterative update rule and successfully generates a pre-specified image. While the benefits of CA are not clear in the image domain, show that the local update rule of CA can excel in generating 3D shape, which is sparse and connected, by achieving near state-of-the the-art performance.
There is one major difference of GCA compared to the classical CA. The transition kernel employs the deep sparse CNN and the effective perception neighborhood is much larger than the update neighborhood. With the extension, GCA has the capacity to perceive the complex context and concurrently generates high-fidelity local shape demonstrated by multi-category and multi-object generation in Figure
6 CONCLUSION AND FUTURE WORK
In this work, we present a probabilistic 3D generative model, named GCA, capable of producing diverse and high-fidelity shapes. Our model learns a transition kernel of Markov chain operating only on the spatial vicinity of input voxel shape, which is the local update rules of cellular automata. We effectively reduce the search space a high resolution voxel space, with the advantage of employing highly expressive sparse convolution neural network that leads to state-of-ther thet performance in probabilistic completion and yields competitive results against recent methods in shape generation.
Although our experiments are mainly focused on shape generation, we believe our framework is capable of modeling wide range of sequential data, which tends to be sparse and connected. For instance, particle-ber based fluid simulation models continuous movement of fluid particles, where the local update rules of our approach can be applied.

---

Published as a conference paper at ICLR 2021
ACKNOWLEDGMENTS
We thank Youngjae Lee for helpful discussion and advice. This research was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (No. 2020RICICI00S and the National Convergence Research of Scientific Challenges through the National Research Foundation of Korea (NRF) funded by Ministry of Science and ICT (NRF- 2020M3F7A10943000)
REFERENCES
Panos Achlioptas, Olga Diamanti, Ioannis Milliagkas, and Leonidas Guibas. Learning representations and generative models for 3D point clouds. volume 80 of Proceedings of Machine Learning Research, pp. 40-49, Stockholmsmässan, Stockholm Sweden, 10-15 Jul 2018. PMLR. URL
Anirudh, Nan Rosemary Ke, Surya Ganguli, and Yoshua Bengio. Variational walk- back: Learning a transition operator as a stochastic recurrent net. In I. Guyon, U. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Ad- vances in Neural Information Processing Systems 30, pp. 4392-449244 4402. Curran Associates, Inc., 2017. URL wtw.arraaatttooooorrtttroreooeea as--aeerrttrrr-aeaaeaaaaaaa attp:atcorraas-sssscttttaaaaaaaa www.ssttoosttit aaning-aa t
Samy Bengio, Oriol Vinyals, Navdeep Jaitly, and Noam Shazeer. Scheduled pling for sequence prediction with recurrent neural networks. In C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett (eds.), Advances in Neural Infor- mation Processing Systems 28, pp. 1171-1179, Curran Associates, Inc., 2015. URL http://papers.nisscccraaaa
scheduled satpeledddsslmliaaeee sampling for sequence- preciction with recurrent neural new.rksssttwwo.........
Florian Bordes, Sina Honari, and Pascal Vincent. Learning generate samples from noise through
infusion training. In International Conference on Learning Representations (ICLR), 2017.
Ruojin Cai, Guandao Yang. Hadar Averbuch-Elor Zekun Hao, Serge Belongie, Noah Snavely, and Bharath Hariharan. Learning gradient fields for shape generation. In Proceedings of the European Conference on Computer Vision (ECCV), 2020.
Angel X. Chang, Thomas Funkhouser, Leonidas Guibas, Pat Hanrahan, Qixing Huang, Zimo Li, Silvio Savarese, Manolis Savva, Shuran Song, Hao Su, Jianxiong Xiao, Li Yi, and Fisher Yu. ShapeNet: An Information-Rich 3D Model Repository. Technical Report arXiv: arXiv:1512.001 1512.03012 [cs. GR., Stanford University - Princeton University - Toyota Technological Institute at Chicago, 2015.
Christopher Choy, Jun Young Gwak, and Silvio Savarese. 4d spatio-temporal convnets: Minkowski convolutional neural networks. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp. 3075-3084, 2019.
Angela Dai, Charles Ruizhongtai Qi, and Matthias Nießner. Shape completion using 3d-encoder- predictor enns and shape synthesis. In Proc. Computer Vision and Pattern Recognition (CVPR), IEFF, 2017.
Benjamin Graham, Martin Engelcke, and Laurens van der Maaten. 3d semantic segmentation with submanifold sparse convolutional networks. CVPR, 2018.
K. He, G. Gkioxari, Dollár, and R. Girshick. Mask r-cnn. In 2017 IEEE International Conference Computer Vision (ICCV), pp. 2980-2988, 2017.
Ferene Huszár. How (not) to train your generative model: Scheduled sampling, likelihood, adversary?, 2015.
Long ji Lin. Self-improving reactive agents based on reinforcement learning, planning and teaching.
In Machine Learning, pp. 293-321, 1992.
10

---

Published as a conference paper at ICLR 2021
Diederick P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations (ICLR), 2015.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convo- Jutional neural networks. In F. Pereira, C. J. C. Burges, L. Bottou, and K. Q. Weinberger (eds.), Advances in Neural Information Processing Systems 25, pp. 1097-1 105, Curran Associates, Inc., 2012. URL http://///////paaaaap///////////
wit h.L.:ppgg..ccoououu..ooaaaaaaaap
David Lopez-Paz and Maxime Oquab, Revisiting Classifier Two-Sample Tests, arXiv e-prints, art. arXiv:1610.06545, October 2016.
Mario Markus and Benno Hess. Isotropic cellular automaton for modelling excitable media. Natue, 347(6288):56-58, September 1990. doi: 10. 10.1038/347056a.
Kaichun Mo, Shilin Zhu, Angel X. Chang, Li Yi, Subarna Tripathi, Leonidas J. Guibas, and Hao Su. PartNet: A large-scale benchmark for fine-grained and hierarchical part-level 3D object understanding. In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2019.
Alexander Mordvintsev, Ettore Randazzo, Eyvind Niklasson, Michael Levin, and Sam Greydanus. Thread: Differentiable self-organizing systems. Distill, 2020. doi: http:://disillllpb///20///////
Charles R Qi. Hao Su, Kaichun Mo, and Leonidas Guibas. Pointnet: Deep learning on point sets for 3d classification and segmentation. arXiv preprint arXiv:1612.00593 2016.
O. Ronneberger, P.Fischer, and T. Brox. U-net: Convolutional networks for biomedical image
segmentation. In Medical Image Computing and Computer-Assisted Intervention (MICCAI), volume 9351 of LNCS, pp. 234-241. Springer, 2015, URL tttstpp:/Iing htt///mmb.nnn wnw.mminifforaaammmmmmmmmm iik.ui Freiburg.de www.:///ewwiiciiiiscccc.m / RFB15a (available on arXiv: 1505. .04597 [cs.CV]).
Dong Wook Shu, Sung Woo Park, and Junseok Kwon. 3d point cloud generative adversarial network based tree structured graph convolutions. In The IEEE International Conference on Computer Vision (ICCV), October 2019.
Edward J. Smith and David Meger. Improved adversarial systems for 3d object generation and reconstruction. volume 78 of Proceedings of Machine Learning Research, pp. 87-96. PMLR, 13-15 Nov 2017. htt.:httpp/proceeeeeee
sm th1 ha.htmm
Jascha Sohl-Dicksteni Eric A. Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsupervised learning using nonequilibrium thermodynamics. In Proceedings of the 32nd International Confer- ence on International Conference on Machine Learning Volume 37, ICML pp. 2256-2265. .og.. 2015.
Yongbin Sun, Yue Wang, Ziwei Liu, Joshua Siegel, and Sanjay Sarma. Pointgrow: Autoregressively learned point cloud generation with self-attention. In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision (WACV), March 2020.
Diego Valsesia, Giulia Fracastoro, and Enrico Magli. Learning localized representations of point clouds with dia, 2019.
generative adversarial networks. IEEE Transactions on Multime-
Aaron van den Oord, Nal Kalchbrenner, Lasse Espeholt, koray kavukcuoglu, Oriol Vinyals, and Alex Graves. Conditional image generation with pixelcnn decoders. In D. D. Lee, M. Sugiyama, U. V. Luxburg, Guyon, and R. Garnett (eds.), Advances in Neural Information Processing Systems 29, pp. 47904479777 4798. Curran Associates, Inc 2016. URL RtLhhtp:// htttt:://paapers.iis.ooom pappe/ 6527 condit ona www.mmaaeeeaaaaaeeeemmeeme ienetiiowwwtt... pixel -nn--encddedds.pdd oww.
Aaron van den Oord, Oriol Vinyals, and Koray Kavukcuoglu. Neural discrete representation learn- ing. In Proceedings of the 31st International Conference on Neural Information Processing Systems. NIPS' 17, pp. 6309-63 -308, Red Hook, NY, USA, 2017. Curran Associates Inc. ISBN 9781510860964.
11

---

Published as a conference paper at ICLR 2021
Aäron den Oord and Nal Kalchbrenner. Pixel mn. In ICML, 2016.
Stephen Wolfram. Cellular automata as simple self-organizing systems. 1982.
Jiajun Wu, Chengkai Zhang, Tianfan Xue, William T. Freeman, and Joshua B. Tenenbaum. Learning probabilistic latent space of object shapes via 3d generative-adverrarii modeling. In Proceedings of the 30th International Conference on Neural Information Processing Systems, NIPS' 16, pp- 82-90. Red Hook, NY, USA, 2016. Curran Associates Inc. ISBN 9781510838819,
Rundi Wu, Xuelin Chen, Yixin Zhuang, and Baoquan Chen. Multimodal shape completion via conditional generative adversarial networks, 2020.
N. H. Wulff and J. A. Hertz. Learning cellular automaton dynamics with neural networks. In Proceedings the 5th International Conference on Neural Information Processing Systems, NIPS 92. pp. 631-638, San Francisco, CA, USA, 1992. Morgan Kaufmann Publishers Inc. ISBN 1558602747.
Guandao Yang, Xun Huang, Zekun Hao, Ming- Yu Liu, Serge Belongie, and Bharath Hariharan. Pointflow: 3d point cloud generation with continuous normalizing flows. arXiv, 2019.
12

---

Published as a conference paper at ICLR 2021
A PROOF OF PROPOSITION 1
We present the proposition in Sec. and its proof.
Proposition 1. Let state z6 be partially connected to state x, where has a finite number of occupied cells. We denote sequence of states z recursively defined as g++1 = =3 nr. Then, there exists an integer T' such that St 2, T2T. TV
Proof. If gT = x, 5T = n = x and 8² = for 2 T", Now we show that there exists an integer T" such that S by showing 8* C x and S C x. We first prove the former by showing that sequence of states z :00 is an increasing sequence bounded by x. VI > U'
n x
C ((*) nx
gh+1
C æ
Now we show 5T" 3 x to complete the proof. Recall the definition partially connected.
Definition 1, We call state to be partially connected to state x, if for any cell b E x, there is cell co E & n. and finite sequence of coordinates corr, in x that starts with co and ends with CT, = b, where each subsequent element is closer than the given threshold distance r, for any b E x, T such that ei E d(cr, c4+1 S r. 0 < i < To and E 3 ,T, b.
By definition, there exists a sequence of coordinates ci:,, for each coordinate b E x. Now we show cf E 3 using mathematical induction. ej E 3" Assuming of E 3 for t > 0,
c EN(()) næ CN(('tt))n gr'+0+
So c/ = gt'To, If set 7" maxbex To, x Ubez 8Th 8 holds, where the second subset holds due to the increasing property of 3 :0000 proven above, i.e., z4 c g for ti < tz. Thus we conclude that x C 3
B FULL DESCRIPTION OF TRAINING PROCEDURE
The training procedure described in Sec. introduces the infusion chain and provides high-level description of the training procedure. When the training data is sampled from the infusion chain, we utilizes the data buffer B as presented in experience replay (j Lin (992)). Sequential state transitions of the same data point, including our proposed infusion chain, are highly correlated and increase the variance of updates. With the data buffer B, we can train the network with a batch of state transitions from different data points, and de-correlate gradients for back preek-prpagation..
The overall training procedure is described in Algorithm 1 The buffer B carries tuples that consists of current state 8, the whole shape v, and the time step f. Given the maximum budget [B), the buffer is initialized by the tuples (5") xr, 0) where 5 ~ (5'1z) for a subset of data E D. For probabilistic shape completion (3") Iz) is a subset of x, and for shape generation we sample just one cell {c} C x. Then each training step utilizes M tuples of mini-batch popped from the buffer B3 We update the parameters of neural network by maximizing the log-likelihood of the state that is closest to x among the neighborhood of the current state, i.e., arg max, log po(x n ((*)) Then we sample the next state from the infusion chain as defined in Eq.
3 If the next state does not meet the stopping criterion, then the tuple with the next state (s! Fr, t + 1) is pushed back to the buffer. Else the buffer samples new data from the dataset.
While the stopping criterion (line 9) should reflect the convergence to the whole shape x, the amount of time steps needed generate the complete shape varies significantly depending on the incompleteness
13

---

Published as a conference paper at ICLR 2021
Algorithm Training GCA
1: Given dataset D, neural network parameter 0
2: Initialize buffer B with maximum budget [B] from
3: repeat
4: Pop mini-batch ,,,,,,, , k.)M from buffer
5: C= 0
6:
for each index i in mini-batch do
7:
L t- log (2; O (
8t ~0 (5) 1 [ 22))
8:
9:
sti+1 does not meet stopping criterion then
Push (af Fi, 1) into buffer B
11:
else
12:
Sample 2; E D
13:
($9) Sample 8 98 (3" x.)
14:
Push (8,, Fi, 0) into buffer
15:
end if
16:
end for
Update parameters + 0 + 2c
18:
until convergence of training or early stopping
20
1.5
3.0
20
18
-80
22-
-EE
40
-75
MMD
2.-
22
-00
-76
MMD
2.
UHD
18-
MMD
-10
-6.6
233
MMD
-20
-65
18
MMD
-0
33
TMD
188
TMD
-00
TMD
600 Infusion speed
-55
Neighborhood radius
Time step
Figure 8: Ablation study on the effects of neighborhood radius r, infusion speed w, and time step T (from left right) tested with probabilistic shape completion lamp dataset. Note that MMD (quality), TMD (diversity) and UHD (fidelity) presented in the figures are multiplied by 10a, 102 and 10a, respectively.
of the initial shape, the efficiency of the stochastic transitions, and the complexity the full shape. In addition, need to learn to stay the complete state once it is reached. We propose simple solution with an adaptive number of training steps for each data: When š, contains 95% the x for the first time, we train only constant Î more time steps. The additional ी steps lead to learn transition kernel similar that of identity, implicitly learning stay still after the generation is completed as in Anirudh et al. (2077).
GCA framework is successfully trained generate wide range of shapes even though transition kernel is confined within its local neighborhood. Over 99% of the training data in generation and completion experiments satisfies the stopping criterion, except for lamp in PartNet-Scan dataset on shape completion, in which 97% of data satisfies the stopping criterion.
C ABLATION STUDY ON HYPERPARAMETERS
In this section, we further investigate the effects of hyperparameters of neighborhood radius r. infusion speed and time step T', with probabilistic shape completion lamp dataset. The default hyperparameters are set to r 3. w = 0.005, corresponding feature is changed. For the study neighborhood radius and infusion speed, the networks were retrained with the matching hyperparameters, while the ablation study on time steps show the result of the model trained default hyperparameter but tested with the variation of time
70, and for each ablation study, only the
14

---

Published as a conference paper at ICLR 2021
(A)
Imput
Output
Ground Truth
Inpul
Output
Ground Truth
Input
Ourput
Ground Truth
Input
Outpet
Ground Truth
Figure 9: Completion results unseen initial states. The model is trained chair, but the initial
state of lamp is given as input.
step T. The Figure shows the effects of r, w and T on MMD (quality). TMD (diversity), and UHD (fidelity).
The effect of the neighborhood radius The neighborhood radius the size of update neigh- borhood of the probabilistic distribution for individual cells, .cc,)) = {c' E Z"I d(c, c') S r). When the radius r is too small
1,2), 2). the MMD (quality) is considerably high compared to when r == 3, 4. Since the size of update is small, models require more time steps to reconstruct the whole shape, and are not able to generate the disconnected lamps as shown in Figure 7 When the neighborhood size is adequate (r = 3, 4), GCA produces fine reconstructed shapes with reasonable scores on all metrics. However, when the radius is too high (r = 5, 10), the model yields shapes that considerably irrelevant to the given initial state, resulting in high TMD and UHD scores. Due to the large possible transition states, few bad samplings lead to states that are irrelevant to the initial state, resulting in the degradation of performance.
The effect of the infusion speed w. The infusion speed controls how likely the groudtruth shape is injected (a = max wt, 1) in Eq. (3)) with the increasing time step. When the infusion speed is too low, the infusion chain is close to the sampling chain, but it is less likely to visit a state that observes the whole complete state. Also, as Huszár (2015) said, the model learns a biased estimator, which implies that GCA may not converge to the correct model. The results in Figure [ show that MMD and UHD are high when the infusion speed w 0, 0.001 compared when that small w generates shapes with worse quality and fidelity. On the other hand, when the infusion speed is set too high (w 0.03, 0.05), the discrepancy between the infusion chain and sampling chain increases. We noticed the diverging behavior of GCA, when the infusion speed was set too high. Bordes et al. (2017) state that the optimal value for the infusion speed differs depending on the time step T. We empirically saw that 0.005 produced the best result for both shape generation and completion with T 100 and = 70.
0.005. This indicates
The effect of the number of time step T. The time step T indicates the number of state transitions performed to generate the shape s - s² + + S" The right plot of Figure 8 shows the performance of GCA with different time steps trained on the default hyperparameter. Even though MMD is lowest when T=30, some lamps fail to complete the shape in the given time steps. As the time steps increase, all scores tend increase by morphing the initial state to the complete state. However, we would like to emphasize that the scale of the plot is relatively small and the model is able to keep the MMD (quality) below 0.002 even when ran on 200 time steps. This is substantially low considering that the MMD of cGAN (Wu et al. (2020)) is 0.00197. This demonstrates that GCA able to maintain the quality of shapes, being robust to increasing time steps.
D COMPLETION RESULTS ON UNSEEN INITIAL STATES
We investigate the behavior of GCA when an unseen input is given as the initial state. The Figure shows the result of GCA trained on chair completion, but a partial lamp is given as the input. The behavior can be classified largely into three classes. First, the model respects the initial state and is able to generalize to novel shape as in Figure 9 (a). Second, as in Figure 9 (b) and (c) which are the most common cases, the model deforms the iitiall state into a trained state and generates results learned during training. The final state contains state similar to the initial, but deformed to shape that belongs to the trained category. Lastly, like in Figure 9 (d). if the initial state is dissimilar to the visited state, it fails generalize and starts diverging.
15

---

Published as a conference paper at ICLR 2021
Input
GCA
cGAN
Figure 10: Qualitative comparison against cGAN (Wu al. (2020) for lamp with small partial input.
4
11
50
56
30
g2
50
Figure 11:
Figure 12: Probability heatmap of chair completion. The probability of next state of occupancy is presented at a horizontal cross section, immediately below the input chair seat. We also present the current state s
Failure case.
E DIVERSITY ANALYSIS ON LAMP DATASET
Among the results presented in Sec. 4 our diversity score (TMD) for shape completion is significantly higher than the state-of-te oftte-of-thearrt the-art with lamp dataset (Table By further investigating instances with high TMD scores in lamp dataset, we could observe that the input part is small and highly incomplete. The input partial data created by randomly selecting a part from the instance, and the part labels in lamp dataset are fragmented and diverse with less regular structure with many small parts. A typical example with high TMD score shown in Figure 10, The input is a small part of a lamp, and our completion results cover wide variety of lamps including table lights and ceiling lights, and still exhibit fine geometry. In contrast, cGAN (Wu et al.) (2020) handles the ambiguity with consistently blurry output. The TMD score for this specific example is 20.45 for GCA, while the cGAN achieves 6.592.
F CONVERGING TO A SINGLE MODE
Our scalable formulation can generate multiple voxels at single inference time. This is a unique characteristic of our formulation compared other autoregressive models (yan den Oord al. (206)); Sun et al. 2220)) and the key to handle high-resolution 3D shapes. Specifically, the multiple voxels of the next state are sampled from conditionally independent occupancy for each cell, i.e, (s 4+11 |s²) (T (c(c)s") While we gain efficiency by making multiple independent decisions in single inference, there is central algorithm that explicitly controls the global shape. In other words, we can view the generation process of GCA as morphogenesis of an organism, but there is unified 'DNA' to eventually move towards a single realistic shape. We indeed encounter rare failure cases that make multiple conflicting decisions on the global structure, as presented in Figure
However, for most of the cases, our model is capable of generating a globally consistent shapes, converging to single mode out of multi-modal data distribution. For example, when chair seat is given as the partial input shape as in Figure [2] there are multiple possible modes of shape completion, including four-leg chairs swivel chairs. The ambiguity is present in 2:66 where both the center and
16

---

Published as a conference paper at ICLR 2021
Spare Coer Bead F.P
Spece Cuer Dona Blck
Figure 13: Architecture of U-Net. The parenthesis denotes the stride of the sparse convolution / deconvolution. Every convolution is followed by batch normalization.
the corners have high probability of chair legs. GCA eventually picks mode and decides to erase the legs the corners and only grow towards the center, creating swivel chair. As shown this example, the transition kernel of GCA observes the change in the context and eventually converges to a globally consistent mode even with independent samples of individual cells.
G EXPERIMENTAL DETAILS
G.1 NEURAL NETWORK ARCHITECTURE AND IMPLEMENTATION DETAILS
All experiments conducted use a variant of U-Net [Ronneberger et al. 2013)) architecture imple- mented with sparse convolution library MinkowskiEngin CChy al. (2019). depicted in Figure [3] We train our method using the Adam (Kingma & Ba (2013) optimizer with an imitial learning rate of 5e-4 and batch size of 32. The learning rate decays by 0.5 every 100k steps. All experiments are run on RTX 2080 ti 11GB GPU, except for the analysis on the neighborhood size with r = 10, which ran on Titan RTX 24GB GPU.
G.2 BASELINES
All experiments in Table 1 and Table 2 are excerpted from Wu et al. (2020) and Cai et al. (2020) except for the results of 3D-IWGAN (Smith & Meger] (017)). 3D-IWGAN was trained the dataset same as ours for 4000 epochs using the author's s offical code: httpp::/ /ttps://giiis www.t.ubcooo.ommoo wtw.s//tttt11113p31oo S IWGAN with the default hyperparameters, Since the original code only supports 32 32 x 32 voxel resolution, we added extra convolution / deconvolution layer for the GAN's discriminator, generator and VAE, generating 64 64 x 64 voxel resolution.
G.3 EVALUATION METRICS
We provide more detailed explanation regarding quantitative metrics for evaluation our approach. Since we compare method against recent point cloud based methods, convert voxels into point clouds simply by treating the coordinates of occupied voxels as points.
For all of the evaluations, we use the Chamfer distance (CD) to measure the similarity between shapes represented as point clouds. Chamfer distance between two sets point cloud and formally defined as
dx)(X,
Σ min I zex vey
vll2 +
min I Σ BEY
v11..
zeX
Probabilistic Shape Completion. We employ the use of minimal matching distance (MMD). total mutual difference (TMD), and unidirectional Hausdorff distance (UHD), as Wu et al. (2200)
Let Sp be the set of input partial shapes and S. be the set of complete shapes in the dataset. For each partial shape P E Sp, We generate & 10 complete shapes CfP Let G {CP,s be the collection of the entire generated set started from elements Sp.
MMD measures the quality of the generated set. For each complete shape in the test set, we compute the distance to the nearest neighbor in the generated set G and average which is
17

---

Published as a conference paper at ICLR 2021
formally defined by
MMD
1
Σ
min deD Y). XEG
(5)
S
YES.
TMD measures the diversity of the generated set. We average the Chamfer distance of all pairs of the generated set for the same partial input, formally defined by
TMD
E PES,
E Σ de cff). Lgickijjsh
(6)
S
k(k - 1)
UHD measures the fidelity of the completed results against the partial inputs. We average the unidirectional Hausdorf' distance dHD from the partial input to each of the completed results, formally defined as
UHD
Σ C.)
Sp
PESp
ISiSk
Shape Generation. We employ the use of -nearest-ncighhorr and minimal matching distance (MMD)) as in Cai et al. (2020). Since MMD was introduced above, state the definition of 1-NNA and COV. Let Sy be the set of generated shapes and S, be the set of reference shapes.
(I-NNA), coverage (COV,
I-NNA, proposed by Lopez-Paz & Oquab (016)), evaluates whether two distri- butions are identical. For shape X. we denote the nearest neighbor as Nx arg minyes_, (XD(X, Y), where S-x represents the set including the entire generated
and reference shapes except itself, S_x S, X. I-NNA is defined to be
I-, Exes, 1xxES, + +Eres, INy |S + [S
(8)
where is indicator function. The optimal value of 1-NNA 50%, when the distribution of two sets are equal, unable to distinguish the two sets.
COV measures the proportion of shapes in the reference set that are matched to at least one shape in the generated set, formally defined by
Hargminy millyes, den(X,Y) S
COV S,)
Sr
18

---

Published as a conference paper at ICLR 2021
H ADDITIONAL SAMPLES ON PROBABILISTIC COMPLETION
Input
GCA
cGAN
Figure 14: Qualitative comparison against cGAN (Wu et al. 2020 of probabilistic shape completion on chair.
19

---

Published as a conference paper at ICLR 2021
Input
GCA
cGAN
Figure Qualitative comparison against cGAN (Wu 2020 of probabilistic shape completion on table.
Input
GCA
cGAN
Figure 16: Qualitative comparison against cGAN (Wu et al. 2020 of probabilistic shape completion on lamp.
20

---

Published as a conference paper at ICLR 2021
1 ADDITIONAL SAMPLES ON SHAPE GENERATION
Figure 17: Samples from shape generation airplane dataset.
Figure 18: Samples from shape generation chair dataset.
21

---

Published as a conference paper at ICLR 2021
Figure 19: Samples from shape generation on car dataset.
22


Reviews:
[{"review_id": "sendmV2ZqYH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes a generative method for 3D objects (voxels representation). Given an initial voxels configuration (e.g. partial shape, or even a single voxel), the method learns a local transition kernel for a Markov chain to decide how to evolve the configuration; sampling iteratively from these probabilities leads to a final model. The paper shows results on shape completion and generation, obtaining fairly good results.\n\nPROS\n- Novelty: I find the approach interesting and the idea seems new in the 3D domain to me (while, as cited in the paper, there are some other similar works in the 2D). It may serve as inspiration for future works to build on it.\n\n- Theoretical foundation: I like the theory on which the paper is based on. I think several properties can be obtained thanks to the theory of finite-state automata (like the presented theorem about the final convergence of the method).\n\nCONS\n- Input/Output: the method is restricted to work in the voxel setting and it is not easily extendible on point clouds. This limits the quality of the generated objects. Also, looking at the attached .gif files, it seems that in the end the model has some noise and it is hard to decide when to stop it (while it seems structural stable). Finally, while in some case the process seems to respect the initial suggestion (e.g. for the lamp_completion example), sometimes seems it does not (e.g. the car_generation start from a place and move to another; is this linked by a strange position of the initial voxel? Also the disconnected_lamp example modifies its input state)\n\n- Results/Analysis: The experiments are a bit limited since they only involve a few rigid categories. I think the paper could be strengthened by testing the method on some non-rigid domains, e.g. humans. Also, the method requires the choice of several hyperparameters, and this is briefly discussed in Section 4.3. I would suggest performing ablation on them.\nFinally, an interesting analysis could investigate how the network behaves when an \"unlikely\" starting state has been feed (e.g. sparse noise, or never seen parts). Is it able to recover a reliable shape?\n\n- Presentation: some concepts (like the Cellular Automata or infusion chains) are only marginally discussed; I would like to see a better introduction to them since they are not so common concepts for Computer Graphics community. Also, the bibliography needs a serious revision, since many voices either break the margins with URLs or are incomplete (e.g. Huszar 2015).\n\nPRE-REBUTTAL RATING\n\nI think the paper could be strengthened by further analysis, experiments, and presentations fixing. However, I like the general idea and I am favorable to accept it as the first step of a different perspective for 3D generative methods. For the final version, I suggest including some further analysis on hyperparameters and initial-state.\n\n-------------\n\nFINAL RATING\n\nI have carefully read the other reviews and authors' replies.\nI agree with other reviewers that the rebuttal is satisfactory, and raised the score accordingly. \nThanks to the authors for their effort.", "extra_scores": {}, "extra_text": {}}, {"review_id": "gx3BIMg_7pw", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "I think this is a strong and interesting paper. It is well written and properly explains its ideas. I am especially impressed by the figures which are clean and helpful in understanding the ideas of the paper and performance of the method. I am also am happy with the variety of experiments, which answered the questions which arose to me when understanding the method. \n\nMy only real concern with respect to this paper is the lack of comparison to highly relevant papers . It does not compare to any other voxel-based 3D generation methods, only to point cloud ones. I think this is quite an important sticking point which I strongly encourage the authors to address, as without comparison within the same 3D representation it is very difficult to establish how much of the claimed improvement in performance is directly due to the benefits of the chosen representation. A clear example of this is in the visual comparison to cGAN (Figure 3) where your generations look far cleaner, however, this might just be a consequence of predicting in a grid as opposed to in a continuous space.  For 3D generation it would be a good idea to compare to : \"Learning a Probabilistic Latent Space of Object Shapes via 3D Generative-Adversarial Modeling\" ,  and \"Improved Adversarial Systems for 3D Object Generation and Reconstruction\". For shape completion you write: \"we report cGAN as the baseline to our method, since this is the only approach announced in probabilistic shape completion\". This is just not true. For example, a you could compare again to \"Improved Adversarial Systems for 3D Object Generation and Reconstruction\", and also to \"3D Object Reconstruction from a Single Depth View with Adversarial Learning\". I would like to see experiments comparing to other voxel based methods in the paper, and also shown here.  I would be very happy to raise my score if this is provided.  At the very least other voxel based methods should be referenced, and their absence from the experimental comparison justified.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "WlNsDCaBL1", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes an interesting formulation of 3D object point cloud generation -- sampling from the transition kernel of a Markov chain. Given an input partial shape, the method iteratively updates the 3D shape by growing point clouds in a local region, and finally outputs the complete 3D object. The proposed method is interesting and technically sound. The quantitative result achieves the state-of-the-art for shape completion and shows comparable results for shape generation. Besides, the paper is well written and easy to follow.\nMy detailed comments are as follows.\n1. It would be better to evaluate the inference speed compared with the state-of-the-arts. I'm curious about the computation cost of the Markov chain based 3D generative model.\n2. Although I like the illustration shown in Figure 6, I am still worried about whether different hyper-parameter sets (r, T, and infusion speed) will affect performance. For the example in Figure 6, it would be better to use different hyper-parameters to show qualitative comparisons. I'm also a bit concerned about the generalization ability of this approach, since the proposed method uses different sets of hyper-parameters for chair, table and lamp as stated in Sec.4.1, the first paragraph. It would be better to show the quantitative results using the same set of hyper-parameters for all classes. \n3. For the experiment (shape completion and shape generation), is the model trained for all categories or for each category respectively? Will different training settings affect the overall performance? My intuition is that this method can complete 3D objects (for example, only given the bottom of the lamp), because it is trained from a large amount of data, so it is easy to \"remember\" the data distribution of each class. If the model is trained on a single category, it is not surprising that it performs well. I want to know whether the model itself can learn categorical features through joint training of all classes. It will also be interesting to see that the shape generation result is a fusion of several classes -- this can show encouraging results for applications such as 3D object design.\n4. It would be nice to discuss how to extend this method to use other representations (for example, voxels, meshes, or implicit functions) for 3D object generation.\n\nIn general, I like the proposed idea and the results are promising. However, considering my above concerns (mainly #2 and #3), I think this article is \"slightly above the threshold\". I will re-evaluate the score based on the author’s feedback, .", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work proposes a method, inspired by Cellular Automata, to generate 3D objects in voxel space. By *only* using local update rule for each location, the method can probabilistic generate high resolution models of everyday objects in the dataset. Due to the ability to incrementally generate details, the quality of the samples are seemingly higher than tradition approaches using Voxel-based GANs.

Most reviewers and myself agree this is a strong and interesting paper that will spark good discussion in the ICLR community. It is also well written and ideas are clearly explained. During the review process, the authors improved the work by conducting additional experiments to analyze the sensitivity of hyper parameters and took in and incorporated various suggestions from the reviewers. After the revision, I believe the work to be in good shape to be accepted at ICLR2021, and I will recommend that this paper be accepted (Poster).
Decision: Accept (Poster)