# Autoregressive 3D Shape Generation via
Canonical Mapping

An-Chieh Cheng1∗, Xueting Li2∗, Sifei Liu2, Min Sun1, Ming-Hsuan Yang3,
1National Tsing-Hua University, 2NVIDIA, 3University of California, Merced
Equal contribution

###### Abstract

With the capacity of modeling long-range dependencies in sequential data,
transformers have shown remarkable performances in a variety of generative
tasks such as image, audio, and text generation. Yet, taming them in
generating less structured and voluminous data formats such as high-resolution
point clouds have seldom been explored due to ambiguous sequentialization
processes and infeasible computation burden. In this paper, we aim to further
exploit the power of transformers and employ them for the task of 3D point
cloud generation. The key idea is to decompose point clouds of one category
into semantically aligned sequences of shape compositions, via a learned
canonical space. These shape compositions can then be quantized and used to
learn a context-rich composition codebook for point cloud generation.
Experimental results on point cloud reconstruction and unconditional
generation show that our model performs favorably against state-of-the-art
approaches. Furthermore, our model can be easily extended to multi-modal shape
completion as an application for conditional shape generation.

##  1 Introduction

In the past few years, transformers not only dominate the natural language
processing area [1, 2, 3], but also consistently show remarkable performance
in a variety of vision tasks such as image classification [4], semantic and
instance segmentation [5, 6] and image generation [7]. Compared to
convolutional neural networks, transformers learn dependencies between visual
elements from scratch without making any prior assumptions about data
structure. As a result, they are more flexible and capable of capturing long-
range dependencies in sequential data. Such property is especially desirable
in the autoregressive generation of globally coherent long-range sequential
data, such as high-resolution images. Indeed, promising performance of
autoregressive generation via transformers has been demonstrated in [7] for
image generation.

Figure 1: Given a point cloud, we first decompose it into a sequence of
perceptually meaningful shape compositions via a canonical auto-encoder in
(a). A group of codebooks is then learned on the sequentialized shape
compositions in (b). Finally, we introduce an autoregressive model for point
cloud generation in (c).

However, employing transformers for autoregression generation on less
structured data, such as raw point clouds, has seldom been explored hitherto.
The main challenge is that the sequentialization of such data is non-trivial.
Naively arranging a point cloud as a sequence of points will break shape
structural information and is computationally infeasible. To resolve the
limitation, similar to the grid-like patches applied to 2D images [7, 8], one
can uniformly divide a point cloud into several groups and lay them out as a
sequence. However, learning the sequential shape representation can be
difficult since such shape compositions are entirely random.

In this paper, we resolve these issues and take the first step to employ
transformers in 3D point cloud generation. The key idea is to decompose a
point cloud into a sequence of semantically meaningful shape compositions,
which are further encoded by an autoregressive model for point cloud
generation. Specifically, we first learn a mapping function that maps each
point cloud onto a shared canonical sphere primitive. Through a canonical
auto-encoder with a few self-supervised objectives, the mapping function
ensures that corresponding parts (e.g., tails of two airplanes) from different
instances overlap when mapped onto the canonical sphere, i.e., dense
correspondences of different instances are established and are explicitly
represented via a canonical sphere (see Fig. 1 (a) middle). Grouping is
carried out on the canonical sphere to obtain the shape compositions (see Fig.
1 (a) right). Thanks to the correspondence constraint, each group on the
canonical sphere essentially corresponds to the same semantic part on all
point cloud instances. As a result, each point cloud can be sequentialized
into a set of shape compositions that are semantically aligned across
different instances. Finally, we train a vector-quantized autoencoder (VQVAE)
using these sequentialized point cloud sequences, followed by learning a
transformer that resolves the point cloud generation task.

Thanks to the sequentialization of point clouds, we are able to learn an
independent codebook for each shape composition, as opposed to the
conventional VQVAE that uses a single, large codebook. Such design leads to
high utilization of codes, reduced number of codes, and the dimension of each
code. The learned VQVAE and transformer can be readily applied to point cloud
reconstruction and unconditional generation, performing favorably against
state-of-the-art approaches. Furthermore, our model can be easily extended to
multi-modal shape completion as an application for conditional shape
generation. The main contributions of this work include:

  * •

We propose a novel transformer-based autoregressive model for point cloud
generation.

  * •

We introduce a canonical autoencoder and a self-supervised point grouping
network to sequentialize point clouds into semantically aligned sequences of
shape compositions.

  * •

We train a VQVAE with group-specific codebooks, followed by learning a
transformer model using the sequentialized point clouds to resolve the task of
point cloud generation.

  * •

Qualitative and quantitative comparisons demonstrate that our model can
achieve state-of-the-art performance for point cloud auto-encoding and
generation. We also extend our model to multi-modal shape completion as an
application for conditional shape generation.

##  2 Related work

###  2.1 3D Shape Generation

3D shape generation targets at learning generative models on 3D shapes
including but not limited to point clouds [9], voxels [10], implicit surfaces
[11], etc. Some early works generate point clouds with a fixed-dimensional
matrix [12, 13]. Although these models can easily be plugged into existing
generative models (e.g., [13] a variational auto-encoder or [12] a generative
adversarial network), they are restricted to generating a fixed number of
points and are not permutation invariant. Several works [14, 15, 16] mitigate
this issue by mapping a primitive to a point cloud. Specifically, they attach
a global latent code to each sampled point on the primitive and then apply the
transformation to each concatenation. In this work, we also generate point
clouds from a shared primitive. Different from existing works, we decompose
the primitive into different compositions and represent each group as a local
latent code. Our model can generate point clouds with more fine-grained
details thanks to the local latent code representation.

Recently works consider point clouds as samples from a distribution and
propose different probabilistic models to capture the distribution. For
example, PointFlow (PF) [9] applies normalizing flow to 3D point clouds.
ShapeGF [17] learns the gradient of the log-density field of shapes and
generates point clouds using Langevin dynamics. DFM [18] and PVD [19] are both
diffusion models that learn a probabilistic model over a denoising process on
inputs.

Most related to our work, PointGrow [20] and AutoSDF [21] also use
autoregressive models to generate 3D shapes. Specifically, the PointGrow
discretizes point coordinates of a point cloud to fixed values and generate a
shape in a point-wise manner following the spatial order. However, due to the
large amount of points in each point cloud, the size of generated point clouds
is limited. Instead, our model decomposes a point cloud into compact shape
compositions that are both semantically meaningful and more efficient to
process. The AutoSDF learns an autoregressive model on volumetric Truncated-
Signed Distance Field (T-SDF), where a 3D shape is represented as a randomly
permuted sequence of latent variables, while the proposed method takes raw
point clouds as inputs and decomposes them into ordered sequences of shape
compositions.

###  2.2 Transformers for Point Clouds

Recently, more works start to apply transformers in model point clouds due to
their impressive representation capacity. For example, Zhao et al. [22]
introduce a point transformer layer using vector self-attention operations and
show improvement in point cloud classification and segmentation. Nico et al.
[23] propose to extract local and global features and relate both
representations using a transformer-based model. Guo et al. [24] use a
transformer to capture local context within the point cloud and thereby
enhance the input embedding. Xiang et al. [25] leverage a transformer
architecture to extract shape context features with a focus on enhancing shape
completion. Kim et al. [26] propose to encode a hierarchy of latent variables
for flexible subset structures using a transformer. However, these works only
employ transformer architectures on the encoding side to utilize its
representation learning ability. In contrast, we use transformer architectures
as the decoder and focus on the autoregressive generation process.

##  3 Method

We propose a framework that employs transformers in the task of point cloud
generation. The overview of our framework is illustrated in Fig. 1. Given a
point cloud, our method first maps it onto a canonical sphere in Section 3.1.
By adopting few self-supervised training objectives, we ensure that the
semantically corresponding points from different instances overlap on the
canonical sphere. Thus, by grouping points on the canonical sphere and
serializing them as a sequence, we equivalently decompose each point cloud
into an ordered sequence of shape compositions. This process is described in
Section 3.2. We then learn a vector-quantized variational auto-encoder (VQVAE)
using the sequentialized point clouds in Section 3.3, with codebooks as a
library of the shape compositions in the point clouds. Finally, a transformer
is trained for point cloud generation in Section 3.4.

Figure 2: Our Canonical Auto-encoder contains two parts: a point encoder that
produces the shape feature of an input point cloud; a nonlinear function that
decodes the canonical sphere, along with the shape feature, back to the input
shape.

###  3.1 Point Cloud Sequentialization

Different from convolutional neural networks, transformers model requires
sequential data as inputs. Taking the transformer in [7] as an example, an
image is first sequentialized by starting from the top left patch and
sequentially moving to the bottom right patch in a zigzag order. The underline
key is that all images are sequentialized by the same “zigzag” order, allowing
the transformer to learn to predict patches based on their surrounding
context. However, when it comes to an orderless data structure such as point
clouds, it remains challenging to sequentialize the unordered points in a
similar way as images.

To resolve this issue, two key questions need to be answered: a) what forms an
unit in a sequentialized point cloud? b) how to sort these units in a
consistent order for different point clouds? In this section, for the ease of
understanding, we consider a single point as an unit in each point cloud and
demonstrate how to sort these points in a consistent order for different point
clouds. We discuss how to learn more semantically meaningful and memory
friendly units (i.e., shape compositions) in the next section.

To sequentialize all point clouds in a consistent order, we first map them
onto a shared canonical sphere. Each point on the sphere is from semantically
corresponding points on different point clouds. Thus, by finding an order for
points on the sphere, all the point clouds can be sequentialized accordingly.
For instance, if a point on the canonical sphere is labeled as the $k$th point
in a sequence, then all its corresponding points in different point clouds are
also labeled as the $k$th point in the sequentialized point cloud. In the
following, we first discuss how to map point clouds to a canonical sphere and
then describe the order we choose to sort all points.

####  3.1.1 Mapping point clouds to a canonical sphere

We learn a nonlinear function to associate all point clouds with a canonical
sphere $\pi$ and thus obtain their correspondences, as inspired by [27]. As
shown in Fig. 2, given an input point cloud $x\in\mathcal{R}^{M\times 3}$
including $M$ points, we first encode it as a 256-dimensional global latent
code by an encoder, e.g., DGCNN [28]. We then replicate the global code and
concatenate it with points sampled from a canonical unit sphere as the input
to the nonlinear function. At the output end of the function, we reconstruct
the input point cloud via a Chamfer loss. The function thus performs a
nonlinear transformation between the sphere and an individual instance,
conditioned on its latent shape feature. We name the combination of the shape
encoder and the nonlinear function as Canonical Auto-encoder. For any point
$x_{i}$ from an input point cloud $x$, to locate its corresponding point on
the sphere, we can (1) search its nearest neighbor $\hat{x}_{i}$ on the
reconstructed point cloud $\hat{x}$, then (2) trace the point $\pi_{i}$ on the
sphere where $\hat{x}_{i}$ is mapped from.

As being proved by Cheng et al. [27], points of all the reconstructed shapes
are “re-ordered” according to the point indices of the canonical sphere (see
Fig. 2). We note that as the key difference, we remove the “point cloud-to-
sphere mapping network” designed in [27] to avoid processing the points that
are inaccurately mapped to locations far away from the sphere surface. Our
design also simplifies the following process in Sec. 3.2, i.e., the grouping
and sequentialization can be conducted on a complete sphere instead of a
subset of it [27]. For brevity, in the following, we denote the canonical
mapping process as $\Phi$, the corresponding point of $x_{i}\in x$ on the
sphere $\pi$ as $\Phi_{x\rightarrow\pi}(x_{i})$, and the corresponding point
of $\pi_{i}\in\pi$ on $x$ as $\Phi^{-1}_{\pi\rightarrow x}(\pi_{i})$.

####  3.1.2 Canonical sphere serialization

Since all point clouds are aligned with the canonical sphere by the canonical
mapping function, any order defined on the canonical sphere can be easily
transferred to any point cloud . In this paper, we traverse the canonical
sphere from the pole with a Fibonacci spiral (see Fig. 1 (a)) and serialize
the points in the spiral order along the way. As a result, the index of a
point in a point cloud can be easily determined as the index of its
corresponding point on the canonical sphere.

Figure 3: We learn a self-supervised network to decompose the canonical sphere
into non-overlapping groups. With canonical mapping, point clouds are
simultaneously decomposed into semantically aligned shape compositions. See
Sec. 3.2.

###  3.2 Shape Composition Learning

Though the re-ordered point clouds in Sec. 3.1 can be readily represented as
sequences of points, such sequences usually include thousands of points and
are intractable to be modeled by autoregressive models. In this section, we
introduce a more semantically meaningful and memory efficient unit for point
cloud sequentialization.

Specifically, we decompose the points of each point cloud instance into $G$
groups ($G=128$ throughout all experiments). We call each group a shape
composition, which is analogous to an image patch in the 2D domain. As
discussed above, since each point cloud is aligned to the canonical sphere,
decomposing the point clouds is thus equivalent to decomposing the canonical
sphere. A straightforward way is to uniformly divide the sphere by randomly
sampling $G$ points as center points and assigning each point to the nearest
center point. However, this approach does not take the semantic prior into
consideration and often produces discontinuous shape compositions.

Instead, we introduce a self-supervised grouping network as shown in Fig. 3.
For each point on the sphere, we predict its group assignment by a multi-layer
perceptron (MLP), followed by a SoftMax activation function. Both are shared
by all the points on the sphere. This results in an assignment probability map
$P$ for all points $q\in\pi$, where $P_{i}^{j}$ indicates the probability to
assign point $\pi_{i}$ to the $j$th group.

To train this network and produce reasonable shape compositions, at the output
end, we transfer the grouping assignment probability from each point
$\pi_{i}\in\pi$ on the canonical sphere to its corresponding point
$\Phi_{\pi\rightarrow x}^{-1}(\pi_{i})$ on the input point cloud. As a result,
we obtain an assignment probability map for each point cloud instance. To
ensure the learned grouping captures the structure of a point cloud and
formulates a decent abstraction of it, we compute $G$ structure points
$K\in\mathcal{R}^{G\times 3}$ [29], where each $K_{j}$ is computed as:

$K_{j}=\sum_{i=1}^{m}\Phi^{-1}_{\pi\rightarrow
x}(\pi_{i})P_{i}^{j}\quad\textrm{with}\quad\sum_{i=1}^{m}P_{i}^{j}=1\quad\textrm{for}\quad
j=1,2,...,G$ (1)

Finally, a Chamfer distance is applied between the predicted structure points
$K$ and the input point cloud $x$, as $\mathcal{L}_{CD}(K,x)$.

After training, we assign each point on $\pi$ to the group with the highest
probability. To assign each point $x_{i}\in x$ to a group, we simply let it
take the group label of its corresponding point
$\Phi_{x\rightarrow\pi}(x_{i})$ on the sphere. In different point clouds,
points on corresponding semantic parts share the same grouping assignment
through the canonical sphere. As a result, any point cloud instance is
decomposed into a set of shape compositions, each of which includes the points
assigned to this group.

These shape compositions form the basic shape units and are further sorted
into a sequence following the Fibonacci sipral order described in Sec. 3.1.2.
In the following sections, we still denote each point cloud as $x$ for
brevity, but we assume that all point clouds have been processed into
sequences of shape compositions using the method described above.

###  3.3 Point Cloud Reconstruction through VQVAE

Now we introduce how to utilize the sequentialized point clouds to learn a
VQVAE. Our VQVAE includes three components, an encoder $E$, a decoder $D$, and
a vector quantizer $Q$, as shown in Fig. 1(c). We discuss each component in
detail in the following.

####  3.3.1 Point cloud encoding

Given a sequentialized instance $x$, we first compute the point-wise feature
by the encoder $E$. To compute the feature of each shape composition, we apply
max-pooling to aggregate features of all points belonging to this shape
composition. We denote the feature of the $j$th group as $z^{j}$.

####  3.3.2 Point cloud sequence quantization

Next, we quantize the group feature vectors $z$ by a group of jointly learned
codebooks. In conventional VQVAEs, a single codebook is learned and shared by
all the compositions (e.g., image patches in 2D VQVAEs [30]). However, we
found that this strategy often leads to low code utilization. The model
struggles to capture the diverse feature of all groups via only a few codes
while leaving all the others unused. Such design leads to the usage of an
unnecessarily large codebook and inferior reconstruction results.

To resolve this issue, we learn an independent codebook for each group where
at least one code from each codebook will be utilized. Since each codebook is
only responsible for representing one particular shape composition, we can
safely reduce the number of codes and the dimension of each code without
degrading the performance. Specifically, given $z^{j}$ for group $j$, we first
reduce its dimension from 256 to 4 to obtain a low dimensional feature
$\hat{z}^{j}$ by learning a linear projection. We then quantize $\hat{z}^{j}$
into $z_{q}^{low}$ by finding its nearest neighbor token from the
corresponding group codebook $Z^{j}$. Note that each group codebook $Z^{j}$
contains 50 4-dimensional latent codes. Finally, we project the matched
codebook token back to the high-dimension embedding space and denote the
quantized group feature as $z_{q}$. We note that the recent work [31] also
shows that this dimension reduction process improves the reconstruction
quality. We show in Sec. 4.4 that our design choices for codebook
significantly increases codebook usage.

####  3.3.3 Point cloud sequence decoding

To recover the input point cloud from $z_{q}$, we concatenate each point in
the canonical sphere $\pi$ with the corresponding quantized group feature and
feed the concatenation to the decoder $D$.

####  3.3.4 VQVAE training

We use the same network architecture as in Sec. 3.1 for both $E$ and $D$. We
train them together with the codebooks by applying the Chamfer and Earth Mover
Distance between the reconstructed point cloud $\hat{x}$ and the input point
cloud $x$:

$\displaystyle\mathcal{L}_{Quantization}=\mathcal{L}_{CD}(x,\hat{x})+\mathcal{L}_{EMD}(x,\hat{x})$
$\displaystyle+\left\|sg[z_{q}^{low}]-\hat{z}\right\|_{2}^{2}$ (2)

where $sg[\cdot]$ is the stop-gradient operation. We use exponential moving
average (EMA) [32] to maintain the embeddings in each of the group codebooks
$Z^{j}$.

###  3.4 Point Cloud Generation through Transformers

Given the learned codebooks, we can represent a point cloud sequence as a
sequence of codebook token indices in order to learn an auto-regressive model.
Specifically, we represent the codebook token indices as
${s_{1},s_{2},...,s_{G}}$, where $G$ is the total group number. Given indices
$s_{<i}$, we train a transformer model to predict the distribution of possible
next indices $s_{i}$ based on its preceeding codebook tokens as:

$\prod_{i=1}^{G}p(s_{i}|s_{1},s_{2},...,s_{i-1})$ (3)

The training objective is to minimize the negative log-likelihood by

$\mathcal{L}_{Transformer}=\mathbb{E}_{x\mathtt{\sim}p(x))}\left[-\log
p(s)\right]$ (4)

The architecture of our transformer model is similar as [7], where the indices
are projected into the embedding space at each position together with an
additive positional embedding. However, since each of our groups owns its own
codebook, we do not use a shared embedding space for all codebook token
indices. Instead, each index $s_{i}$ is mapped to the embedding space using a
separate linear layer.

####  3.4.1 Unconditional generation

With the learned transformer model, unconditional shape generation is carried
out by sampling token-by-token from the output distribution. The sampled
tokens are then fed into the decoder $D$ in the VQVAE to decode output shapes.

####  3.4.2 Conditional generation

Going beyond unconditional generation, we further incorporate our transformer
with a conditional input. Specifically, given a condition $c$ (e.g., a depth
image), we use our transformer to generate a shape that matches the semantic
meaning of $c$. For instance, if $c$ is a depth image, then the transformer is
expected to generate a 3D shape that renders the depth image from the given
viewpoint. To this end, we first encode the condition $c$ into a feature
vector in the same dimension of token embedding, then prepend the feature
vector before the first token embedding.

Table 1: Shape auto-encoding on the ShapeNet dataset. The best results are highlighted in bold. CD is multiplied by $10^{4}$ and EMD is multiplied by $10^{2}$. |  | AtlasNet |  PF |  ShapeGF |  DPM |  Ours |  Oracle
---|---|---|---|---|---|---|---
Dataset |  Metric |  Sphere |  Patches |  |  |  |  |
Airplane |  CD |  1.002 |  0.969 |  1.208 |  0.966 |  0.997 |  0.889 |  0.837
EMD |  2.672 |  2.612 |  2.757 |  2.562 |  2.227 |  2.122 |  2.062
Chair |  CD |  6.564 |  6.693 |  10.120 |  5.599 |  7.305 |  6.177 |  3.201
EMD |  5.790 |  5.509 |  6.434 |  4.917 |  4.509 |  4.218 |  3.297
Car |  CD |  5.392 |  5.441 |  6.531 |  5.328 |  5.749 |  5.050 |  3.904
EMD |  4.587 |  4.570 |  5.138 |  4.409 |  4.141 |  3.614 |  3.251
|  |  |  |
---|---|---|---|---
|  |  |  |
|  |  |  |
PF | ShapeGF | DPM | Ours | Input
Figure 4: Auto-encoding (reconstruction) results. We also shown results from
PF (PointFlow) [9], ShapeGF [17], and DPM [18] on the left for comparison.

##  4 Experiments

In this section, we first evaluate our model’s performance by point cloud
auto-encoding (Sec. 4.1), unconditional generation (Sec. 4.2) and conditional
generation (Sec. 4.3). Then, we present ablation studies in Sec. 4.4.

##### Datasets.

Following previous works [9, 17, 26], we conduct our auto-encoding and
generation experiments on the airplane, chair, and car category from the
ShapeNet [33] dataset. We use data provided by [9], which includes 15,000
points sampled uniformly from the mesh surface for each object. We sub-sample
2048 points for training and testing, respectively. To train our model, we
normalize all point clouds to a unit sphere as in [14]. For the multi-modal
shape completion task, we follow [19] which uses the ShapeNet rendering data
from Genre [34]. Genre contains 20 random views with ground-truth depth maps
for each object in the ShapeNet. For baselines that take additional partial
point clouds as inputs, we use the data provided by [19].

##### Evaluation metrics.

For fair comparison, we follow prior works [14, 9, 17] and use the symmetric
Chamfer Distance (CD) as well as the Earth Mover’s Distance (EMD) to evaluate
the quality of the reconstructed point clouds. To evaluate the quality of the
unconditionally generated point clouds, we use the Minimum Matching Distance
(MMD) [12], the Coverage Score (COV) [12], and the 1-NN classifier accuracy
(1-NNA) [9]. To evaluate the multi-modal shape completion performance for the
conditional generation task, we follow Wu et al. [35] that uses a) the Total
Mutual Difference (TMD) to measure the generation diversity and b) the Minimal
Matching Distance (MMD) to measure the completion quality with Chamfer
Distance (CD) as distance measure. We provide details about each of the
metrics in the Appendix. For all generation experiments, we normalize each
point cloud to a unit sphere before measuring the metrics. This is to ensure
the metric focuses more on the geometry of the shape rather than on the scale.

###  4.1 Shape Auto-encoding

We first evaluate how well our model can approximate a shape with quantized
features. We quantitatively compare our results against the following state-
of-the-art point cloud auto-encoders: AtlasNet [15] variants that deform from
patches and from sphere, respectively, PointFlow (PF) [9], ShapeGF [17], and
DPM [18]. We also report the lower bound of the reconstruction errors in the
“Oracle” column. This bound is obtained by measuring the reconstruction error
between two different point clouds with the same number of points sampled from
the identical underlying meshes. As shown in Table 1, our method consistently
outperforms other methods when measured by EMD. We note that EMD is usually
considered a better metric for measuring a shape’s visual quality [19] because
it forces model outputs to have the same density as the ground-truth shapes
[36]. This suggests that our reconstructed point clouds have points that are
more uniformly distributed on the surface. We also provide qualitative results
compared to baselines in Figure 4 to validate the effectiveness of our model.

###  4.2 Unconditional Generation

Table 2: Shape generation results. $\uparrow$ means the higher the better, $\downarrow$ means the lower the better. MMD-CD is multiplied by $10^{3}$ and MMD-EMD is multiplied by $10^{2}$. |  |  MMD ($\downarrow$) |  |  COV (%, $\uparrow$) |  |  1-NNA (%, $\downarrow$)
---|---|---|---|---|---|---
Category |  Model |  CD |  EMD |  |  CD |  EMD |  |  CD |  EMD
Airplane |  PointGrow |  3.07 |  11.64 |  |  10.62 |  10.62 |  |  99.38 |  99.38
ShapeGF |  1.02 |  6.53 |  |  41.48 |  32.84 |  |  80.62 |  88.02
SP-GAN |  1.49 |  8.03 |  |  30.12 |  23.21 |  |  96.79 |  98.40
PF |  1.15 |  6.31 |  |  36.30 |  38.02 |  |  85.80 |  83.09
|  SetVAE |  1.04 |  6.16 |  |  39.51 |  38.77 |  |  89.51 |  87.65
|  DPM |  1.10 |  7.11 |  |  36.79 |  25.19 |  |  86.67 |  90.49
|  PVD |  1.12 |  6.17 |  |  40.49 |  45.68 |  |  80.25 |  77.65
|  Ours |  0.83 |  5.50 |  |  45.67 |  44.19 |  |  63.45 |  71.60
|  Train |  0.97 |  5.80 |  |  45.68 |  46.67 |  |  71.36 |  69.63
Chair |  PointGrow |  16.23 |  18.83 |  |  12.08 |  13.75 |  |  98.05 |  99.10
ShapeGF |  7.17 |  11.85 |  |  45.62 |  44.71 |  |  61.78 |  64.27
SP-GAN |  8.51 |  13.09 |  |  34.74 |  26.28 |  |  77.87 |  84.29
PF |  7.26 |  12.12 |  |  42.60 |  45.47 |  |  65.56 |  65.79
|  SetVAE |  7.60 |  12.10 |  |  42.75 |  40.48 |  |  65.79 |  70.39
|  DPM |  6.81 |  11.91 |  |  43.35 |  42.75 |  |  64.65 |  69.26
|  PVD |  7.65 |  11.87 |  |  45.77 |  45.02 |  |  60.05 |  59.52
|  Ours |  7.37 |  11.75 |  |  45.77 |  46.07 |  |  60.12 |  61.93
|  Train |  7.636 |  11.88 |  |  48.34 |  49.09 |  |  55.89 |  57.48
Car |  PointGrow |  14.12 |  18.33 |  |  6.82 |  11.65 |  |  99.86 |  98.01
ShapeGF |  3.63 |  9.11 |  |  48.30 |  44.03 |  |  60.09 |  61.36
PF |  3.69 |  9.03 |  |  44.32 |  45.17 |  |  63.78 |  57.67
SetVAE |  3.63 |  9.05 |  |  39.77 |  37.22 |  |  65.91 |  67.61
|  DPM |  3.70 |  9.39 |  |  38.07 |  30.40 |  |  74.01 |  73.15
|  PVD |  3.74 |  9.31 |  |  43.47 |  39.49 |  |  65.62 |  63.35
|  Ours |  3.31 |  8.89 |  |  41.76 |  47.72 |  |  55.68 |  57.81
|  Train |  3.74 |  9.38 |  |  53.12 |  47.16 |  |  52.70 |  54.26
|  |  |  |  |  |  |
---|---|---|---|---|---|---|---
|  |  |  |  |  |  |
|  |  |  |  |  |  |
PF | ShapeGF | SetVAE | DPM | PVD | Ours
Figure 5: Shape generation results. We shown results from PF (PointFlow) [9], ShapeGF [17], SetVAE [26], DPM [18], and PVD [19].  |  |  |  |  |
---|---|---|---|---|---
$n=1024$ | $n=2048$ | $n=1024$ | $n=2048$ | $n=4096$ | $n=8194$
PointGrow | Ours
Figure 6: High-resolution generation results comparing to PointGrow [20]. $n$
refers to the number of output points.

We quantitatively compare our method with the following state-of-the-art
generative models: PointGrow [20], ShapeGF [17], SP-GAN [16], PointFlow (PF)
[9], SetVAEF [26], DPM [18], and PVD[19]. We summarize the quantitative
results in Table 2. We also report the performance of point cloud sampled from
the training set in the “Train” row. For most of the metrics, our model has
comparable, if not better, performance than other baselines. This suggests
that our model is capable of generating diverse and realistic samples. We
provide qualitative results comparing to baselines in Figure 5.
Among these baselines, PointGrow is most relevant to our work that generates
point clouds in an autoregressive manner. Our model significantly outperforms
PointGrow in all metrics because PointGrow scales poorly [20] when generating
large point sets. In contrast, our method can generate shapes in an arbitrary
resolution ranging from low to high with sharp details within a single model.
We show point clouds generated with different resolutions comparing to
PointGrow in Figure 6.

###  4.3 Conditional Generation

Table 3: Multi-modal completion on the Chair dataset. $t$ denotes the temperature scaling factor. $\uparrow$ means the higher the better, $\downarrow$ means the lower the better. MMD and TMD are both multiplied by $10^{3}$. Category |  Metric |  Input |  MMD ($\downarrow$) |  TMD ($\uparrow$)
---|---|---|---|---
Airplane |  MSC |  Depth+Camera |  1.475 |  0.925
PVD |  Depth+Camera |  1.012 |  2.108
Ours (t=1) |  Depth |  0.663 |  1.449
|  Ours (t=2) |  Depth |  0.673 |  2.406
|  Ours (t=3) |  Depth |  0.684 |  2.352
Chair |  MSC |  Depth+Camera |  6.372 |  5.924
PVD |  Depth+Camera |  5.042 |  7.524
Ours (t=1) |  Depth |  5.142 |  6.553
|  Ours (t=2) |  Depth |  5.261 |  8.174
|  Ours (t=3) |  Depth |  6.427 |  13.341
|  |  |  |  |  |  |
---|---|---|---|---|---|---|---
|  |  |  |  |  |  |
|  |  |  |  |  |  |
Input$/$GT | MSC | PVD | Ours | Input$/$GT | MSC | PVD | Ours
Figure 7: Multi-modal shape completion results with comparison to MSC and PVD.
In the first column, we show the input depth-map, partial point cloud, and
reference ground-truth shape for each sample respectively from top to bottom.

During inference, our transformer model generates a sequence by probabilistic
sampling each token, which naturally allows multi-modal generation. On the
other hand, the shape completion problem is multi-modal in nature since the
incompleteness introduces significant ambiguity [35]. Motivated by this
property, we extend our approach to shape completion as an application for
conditional shape generation. Specifically, we use a depth map as the input
condition to the transformer model. We employ a ResNet50 [37] encoder to
extract global feature from the depth map and prepend the feature vector to
the transformer as discussed in follow Sec. 3.4.2.

To evaluate the performance, we compare with two state-of-the-art approaches
on multi-modal shape completion: MSC [35] and PVD [19]. Note that both MSC
[35] and PVD [19] take aligned point clouds as inputs. Therefore, they require
additional camera parameters to obtain partial scans from the depth map. We
present quantitative comparison results in Table 3 and show that our approach
can achieve comparable or even better performance without requiring additional
camera parameters. We also report results using different temperatures, which
suggests that our model can provide controllable diversity by scaling the
temperature parameter.

To further investigate the reason that our MMD metric in the chair category is
slightly inferior to PVD, we visualize qualitative results in Figure 7. In
general, our model produces shapes with better visual quality. However, due to
the inherent ambiguity in single-view reconstruction, it is difficult to infer
the real scale of objects without knowing the camera parameters, especially
for depth maps rendered from the side views. For instance, given a depth map
of a chair from side viewpoints, our model generates plausible but wider
chairs than the ground truth 3D shapes, as shown in the first row of Fig. 7.

Figure 8: Visulization of codebooks. Each of the $7\times 7$ grid corresponds
to a learned group codebook and each shape in the inner square represents a
shape composition decoded from a codebook token.

###  4.4 Ablation Study

Table 4: Ablation study on the effectiveness of primitive grouping on the Chair dataset. CD is multiplied by $10^{4}$ and EMD is multiplied by $10^{2}$. | Canonical Grouping | Uniform Grouping
---|---|---
$\\#groups$ |  16 |  128 |  256 |  16 |  128 |  256
CD ($\downarrow$) |  7.542 |  6.177 |  7.933 |  8.646 |  7.676 |  7.278
EMD ($\downarrow$) |  4.466 |  4.218 |  4.645 |  4.772 |  4.541 |  4.627
Table 5: Ablation study on using different vector quantization on the Chair dataset. CD is multiplied by $10^{4}$ and EMD is multiplied by $10^{2}$. Dimension Reduction |  ✗ |  256$\rightarrow$64 |  256$\rightarrow$4 |  256$\rightarrow$64 |  256$\rightarrow$4
---|---|---|---|---|---
Grouped Codebook |  ✗ |  ✗ |  ✗ |  ✓ |  ✓
CD ($\downarrow$) |  7.139 |  6.561 |  6.298 |  6.442 |  6.177
EMD ($\downarrow$) |  4.376 |  4.272 |  4.283 |  4.228 |  4.218
Codebook Usage (%, $\uparrow$) |  11.72 |  21.04 |  35.72 |  70.22 |  79.28

####  4.4.1 Effectiveness of the canonical mapping function

Table 4 shows ablations on the effectiveness of our canonical mapping
function, with empirical results on CD and EMD metrics using the ShapeNet
Chair dataset. We report variants of our model using a different number of
groups $G$ and an alternative way to segment the canonical sphere (in the
“Uniform Grouping” column). Specifically, we uniformly sample $G$ points on
the sphere as centers and use the nearest neighbor search to assign all points
on the sphere to its nearest center point. Though straightforward, this
approach does not provide any semantic correspondence across shape instances;
thereby, our model consistently performs better than this baseline in
different $G$ settings. For the “Uniform Grouping” setting, the auto-encoding
results directly relate to the $G$ because a larger $G$ results in a finer
segmentation. However, our model performs the best with a moderate $G=128$.
Since the size of each group is automatically determined in our model (i.e.
rather than explicitly restricted to an equal size), therefore, some groups
may include only a few points when $G$ is large. This tends to hurt the
encoding performance and results in over-fitting.

####  4.4.2 Effectiveness of group-wise codebooks

Table 5 demonstrates the effectiveness of the latent reduction and group-wise
codebook (see Sec. 3.3) in our vector quantizer $Q$. In addition to CD and
EMD, we also report the codebook usage for each model. The usage is computed
as the percentage of codes that have been utilized at least once over the
entire test set. For a fair comparison with our full model that uses 128 group
codebooks in size 50, we use a global codebook in size 5000 ($\approx$
128$\times$50) for each variant that does not use group-wise codebooks. Our
full model performs the best with dimension reduction from 256 to 4 together
with a group-wise codebook. Reducing the lookup dimension in the codebook and
using a group-wise codebook significantly boost the codebook usage and thereby
achieve better auto-encoding quality. To further show that the proposed model
can learn codebooks as a library of local shapes, we visualize the learned VQ
codes in different groups in Figure 8, where each codebook clearly captures
one meaningful part of the chair category.

##  5 Conclusions

In this work, we propose a transformer-based autoregressive model for point
cloud generation. The key idea is to decompose a point cloud into a sequence
of semantically aligned shape compositions in a learned canonical space. We
show that these compositions can be further used to learn a group of context-
rich codebooks for point cloud generation. Experimental results demonstrate
that the proposed method can achieve state-of-the-art performance for point
cloud auto-encoding and generation. Finally, we show that our model can be
easily extended to multi-modal shape completion as an application for
conditional shape generation.

## Appendix

In this Appendix, we provide more details about implementation, model
efficiency and additional results. We start by introducing implementation
details in Section A, followed by model size and computational time discussion
in Section B. We then show ablation studies on different shape composition
serialization methods in Section C. In Section D, Section E and Section F, we
demonstrate more qualitative results on auto-encoding, unconditional
generation and conditional generation. Finally, we discuss limitations of our
method in Section G.

##  Appendix A Implementation Details

Algorithm 1 : The training phase of our approach consists of learning four
components: (1) Canonical Auto-encoder (2) Canonical Grouping Network (3)
VQVAE (4) Transformer

(A) Canonical Auto-encoder $\vartriangleright$ 8 hours on Airplane category

1: Sub-sample $M$ points from the input point cloud $x$ and canonical sphere
$\pi$;

2: Initialize weight of the encoder $E_{c}(\cdot)$ and decoder $D_{c}(\cdot)$;

3: while not converged do

4: foreach iteration do

5: $\boldsymbol{z_{x}}\leftarrow\,E_{c}(x)$;

6: $\boldsymbol{\hat{x}}\leftarrow\,D_{c}([\pi_{i},z_{A}])$, where
$\pi_{i}\in\pi$;

7: Obtain reconstruction loss $L_{CD}(\hat{x},x)$ and $L_{EMD}(\hat{x},x)$;

8: Update weight;

(B) Canonical Grouping Network $\vartriangleright$ 2 hours on Airplane
category

1: Generate randomly $M$ points from the canonical sphere $\pi$;

2: Initialize weight of the canonical grouping network $MLP(\cdot)$;

3: while not converged do

4: foreach iteration do

5: Obtain the corresponding point of $\pi_{i}\in\pi$ on $x$ as
$\Phi^{-1}_{\pi\rightarrow x}(\pi_{i})$;

6: $\boldsymbol{P_{i}}\leftarrow\ MLP([x_{i},\pi_{i}])$, where $x_{i}\in
x,\pi_{i}\in\pi$;

7: $\boldsymbol{K_{j}}\leftarrow\ \sum_{i=1}^{m}\Phi^{-1}_{\pi\rightarrow
x}(\pi_{i})P_{i}^{j}$ , where $j=1,2,...,G$;

8: Obtain loss $L_{CD}(K,x)$;

9: Update weight;

(C) VQVAE $\vartriangleright$ 24 hours on Airplane category

1: Sub-sample $M$ points from the input point cloud $x$ and canonical sphere
$\pi$;

2: Sequentialize $x$;

3: Initialize weight of $E(\cdot)$, $D(\cdot)$, and $VQ(\cdot)$;

4: while not converged do

5: foreach iteration do

6: Obtain group feature $\boldsymbol{z}\leftarrow\ E(x)$

7: $\boldsymbol{z_{q}}\leftarrow\ VQ(z)$

8: $\boldsymbol{\hat{x}}\leftarrow\,D([\pi_{i},z_{q}])$, where
$\pi_{i}\in\pi$;

9: Obtain loss $L_{Quantization}$;

10: Update weight;

(D) Transformer $\vartriangleright$ 16 hours on Airplane category

1: Sub-sample $M$ points from the input point cloud $x$;

2: Initialize weight of the transformer;

3: Vector Quantize $x$ to a sequence $s$;

4: while not converged do

5: foreach iteration do

6: Obtain the probability distribution for each $s_{i}\in s$ autoregressively.

7: Obtain loss $L_{Transformer}$;

8: Update weight;

###  A.1 Model Architecture

We use the same model architecture for all encoders and decoders used in our
method. Specifically, we adopt the encoder structure from DGCNN [28], which
contains 3 EdgeConv layers using neighborhood size 20. Our decoder follows the
two branch structure as in SP-GAN [16]. Given a matrix that consists of sphere
points and features, the decoder first feeds sphere points to a graph
attention module to extract point-wise spatial features. On the other branch,
we use a nonlinear feature embedding to extract style features from the
latent. Then, we use adaptive instance normalization [38] to fuse the local
styles with the spatial features. We repeat the process with another round of
style embedding and fusion, then predict the final output from the fused
feature. For our grouping network, we follow [29], using a two-layer
128-neuron MLP with ReLU activations and BatchNorm layers. Our transformer
model is modified from [7], where we reduce their number of layers and heads
to 24 and 16, respectively.

###  A.2 Training Details

We use the airplane category in ShapeNet as an example to illustrate the
training pipeline. We perform all the experiments on a workstation with Intel
Xeon Gold 6154 CPU (3.00GHz) and 4 NVIDIA Tesla V100 (32GB) GPUs. We implement
our framework with Pytorch 1.10. Please see Algorithm 1 for more details. The
source code will be released to public upon publication.

###  A.3 Inference Details

Esser et al. [7] introduce several test-time hyper-parameters (e.g., top-k and
top-p heuristics, temperature scaling factor $t$) for transformer to obtain
best results. Following [7], we use top-p sampling heuristic for the
transformer model which we empirically set $p=0.92$ throughout all
experiments. We do not use top-k sampling heuristic and the temperature
scaling factor $t$ is set to 1 unless otherwise specified. We provide
unconditional generation results on ShapeNet Chair using different $p$ in
Table 6.

Table 6: Shape generation results on ShapeNet Chair. $\uparrow$ means the higher the better, $\downarrow$ means the lower the better. MMD-CD is multiplied by $10^{3}$ and MMD-EMD is multiplied by $10^{2}$. |  MMD ($\downarrow$) |  |  COV (%, $\uparrow$) |  |  1-NNA (%, $\downarrow$)
---|---|---|---|---|---
Model |  CD |  EMD |  |  CD |  EMD |  |  CD |  EMD
$p=0.85$ |  7.70 |  11.87 |  |  41.84 |  44.25 |  |  61.40 |  64.72
$p=0.92$ |  7.37 |  11.75 |  |  45.77 |  46.07 |  |  60.12 |  61.93
$p=0.99$ |  7.22 |  11.73 |  |  44.86 |  45.46 |  |  60.19 |  62.38

###  A.4 Evaluation Metrics

  * •

Minimum matching distance (MMD) [9] measures the fidelity of the generated
point clouds. For each sample in the reference point clouds, we compute the
distance to its nearest neighbor in the generated point cloud. The final MMD
is the average of the distances. Note that the nearest neighbor can be
calculated with different distance measurements such as Chamfer distance or
Earth Mover distance.

  * •

Coverage (COV) [9] detects mode-collapse by measuring the fraction of samples
in the reference point clouds that are matched to at least one sample in the
generated point clouds. Specifically, for each sample in the generated point
clouds, we mark its nearest neighbor in the reference point clouds as a match.
Similar to MMD, the nearest neighbor can be calculated with different distance
measurements such as Chamfer distance or Earth Mover distance.

  * •

1-nearest neighbor accuracy (1-NNA) [9] performs two-sample tests [39] on the
generated point clouds and the reference point clouds. If the generated point
clouds seem to be drawn from the reference point, then the classifier will
perform like a random guess (i.e. results in near 50% accuracy).

  * •

Total Mutual Difference (TMD) [35] measures the completion diversity given a
conditional input (e.g., depth-map, partial point cloud). Specifically, for
each shape $i$ in the $k$ generated shapes, we calculate its average Chamfer
distance $d^{CD}_{i}$ to the other $k-1$ shapes. The total TMD is calculated
as $\sum_{i=1}^{k}d^{CD}_{i}$.

##  Appendix B Computational Time and Model Size

Table 7: The parameter size and inference time for different models. Model |  $\\#$ Parameters |  Inference Time |
---|---|---|---
PointGrow [20] |  0.31M |  5303.70 |
ShapeGF [17] |  0.13M |  0.2659 |
SP-GAN [16] |  0.58M |  0.2407 |
PointFlow [9] |  1.61M |  0.3506 |
SetVAE [26] |  0.55M |  0.0158 |
DPM [18] |  3.87M |  0.0943 |
PVD [19] |  27.6M |  38.35 |
Ours (Transformer) |  20.6M |  1.5391 |
Ours (VQ) |  0.91M |  0.0981 |
Ours (Total) |  21.5M |  1.6372 |

We report the inference time and model size for different models in Table 7.
To be precise, the inference time and model size for each model is measured as
the time and the number of parameters needed for generating a shape instance.
All results are measured with their official implementation on a workstation
with Intel Xeon Gold 6154 CPU (3.00GHz) and a single NVIDIA Tesla V100 (32GB).
Note that PointGrow requires forwarding the model the same time as the desired
number of points (e.g., 2048), therefore, is slow to compute. PVD is a
diffusion-based approach which involves multi-step refinement from a random
noise, therefore, is computationally intensive, too.

##  Appendix C Ablation on Shape Composition Serialization

To analyze the effect of different shape composition serialization, we train
our transformer model with (1) random order (2) Fibonacci spiral order (3)
inverse Fibonacci spiral order (Spiral$\star$). As shown in Table 8, using
Fibonacci spiral order in either direction is generally better than using a
random order.

Table 8: Shape generation results on ShapeNet Chair. $\uparrow$ means the higher the better, $\downarrow$ means the lower the better. MMD-CD is multiplied by $10^{3}$ and MMD-EMD is multiplied by $10^{2}$. |  MMD ($\downarrow$) |  |  COV (%, $\uparrow$) |  |  1-NNA (%, $\downarrow$)
---|---|---|---|---|---
Model |  CD |  EMD |  |  CD |  EMD |  |  CD |  EMD
Random |  7.44 |  11.85 |  |  43.20 |  42.14 |  |  61.02 |  65.18
Spiral |  7.37 |  11.75 |  |  45.77 |  46.07 |  |  60.12 |  61.93
Spiral$\star$ |  7.17 |  11.61 |  |  44.56 |  44.71 |  |  59.36 |  62.23

##  Appendix D Qualitative Results of Auto-encoding

In Figure 9, we show more auto-encoding results. Thanks to the context-rich
codebook, our model is able to reconstruct shapes with better local details.
Moreover, the points are more uniformly distributed among the surface.

|  |  |  |
---|---|---|---|---
|  |  |  |
|  |  |  |
|  |  |  |
|  |  |  |
|  |  |  |
|  |  |  |
|  |  |  |
|  |  |  |
PF | ShapeGF | DPM | Ours | Input
Figure 9: Auto-encoding (reconstruction) results. We also shown results from
PF (PointFlow) [9], ShapeGF [17], and DPM [18] on the left for comparison.

##  Appendix E Qualitative Results of Unconditional Generation

In Figure 10, Figure 11, and Figure 12, we show more unconditional generation
results. The results suggest that our model can generate diverse shape in high
fidelity.

|  |  |  |  |
---|---|---|---|---|---
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
PF | ShapeGF | SetVAE | DPM | PVD | Ours
Figure 10: Shape generation results on ShapeNet Airplane. We shown results from PF (PointFlow) [9], ShapeGF [17], SetVAE [26], DPM [18], and PVD [19].  |  |  |  |  |
---|---|---|---|---|---
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
PF | ShapeGF | SetVAE | DPM | PVD | Ours
Figure 11: Shape generation results on ShapeNet Chair. We shown results from PF (PointFlow) [9], ShapeGF [17], SetVAE [26], DPM [18], and PVD [19].  |  |  |  |  |
---|---|---|---|---|---
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
PF | ShapeGF | SetVAE | DPM | PVD | Ours
Figure 12: Shape generation results on ShapeNet Car. We shown results from PF
(PointFlow) [9], ShapeGF [17], SetVAE [26], DPM [18], and PVD [19].

##  Appendix F Qualitative Results of Conditional Generation

In Figure 13, we show more conditional generation results. Our shape
completion results tend to show more variation and have better visual quality
comparing to MSC [35] and PVD [19].

|  |  |  |  |  |  |
---|---|---|---|---|---|---|---
|  |  |  |  |  |  |
|  |  |  |  |  |  |
|  |  |  |  |  |  |
|  |  |  |  |  |  |
|  |  |  |  |  |  |
Input$/$GT | MSC | PVD | Ours | Input$/$GT | MSC | PVD | Ours
Figure 13: Multi-modal shape completion results. We shown 4 samples comparing
to MSC [35] and PVD [19]. The input depth-map, partial point cloud, and
reference ground-truth shape for each sample is shown in the first column,
respectively (from top to bottom).

##  Appendix G Limitations

|  |  |  |  |
---|---|---|---|---|---
Input | Ours | Input | Ours | Input | Ours
Figure 14: Failure cases.

Our model relies on the learned correspondence from the canonical mapping
function, therefore, inherits similar limitations from Cheng et al. [27]. Our
model fails to reconstruct certain samples with holes or with complex
topology. We show some failure cases of our model in Figure 14.

## References

  * [1] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  NeurIPS, 2017.
  * [2] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  Bert: Pre-training of deep bidirectional transformers for language understanding.  arXiv preprint arXiv:1810.04805, 2018.
  * [3] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al.  Language models are few-shot learners.  NeurIPS, 2020.
  * [4] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al.  An image is worth 16x16 words: Transformers for image recognition at scale.  arXiv preprint arXiv:2010.11929, 2020.
  * [5] Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo.  Swin transformer: Hierarchical vision transformer using shifted windows.  In ICCV, 2021.
  * [6] Robin Strudel, Ricardo Garcia, Ivan Laptev, and Cordelia Schmid.  Segmenter: Transformer for semantic segmentation.  In ICCV, 2021.
  * [7] Patrick Esser, Robin Rombach, and Bjorn Ommer.  Taming transformers for high-resolution image synthesis.  In CVPR, 2021.
  * [8] Ali Razavi, Aaron Van den Oord, and Oriol Vinyals.  Generating diverse high-fidelity images with vq-vae-2.  NeurIPS, 32, 2019.
  * [9] Guandao Yang, Xun Huang, Zekun Hao, Ming-Yu Liu, Serge Belongie, and Bharath Hariharan.  Pointflow: 3d point cloud generation with continuous normalizing flows.  In CVPR, pages 4541–4550, 2019.
  * [10] Jiajun Wu, Chengkai Zhang, Tianfan Xue, Bill Freeman, and Josh Tenenbaum.  Learning a probabilistic latent space of object shapes via 3d generative-adversarial modeling.  NeurIPS, 2016.
  * [11] Eric R. Chan, Connor Z. Lin, Matthew A. Chan, Koki Nagano, Boxiao Pan, Shalini De Mello, Orazio Gallo, Leonidas Guibas, Jonathan Tremblay, Sameh Khamis, Tero Karras, and Gordon Wetzstein.  Efficient geometry-aware 3D generative adversarial networks.  In CVPR, 2022.
  * [12] Panos Achlioptas, Olga Diamanti, Ioannis Mitliagkas, and Leonidas Guibas.  Learning representations and generative models for 3d point clouds.  In ICML, pages 40–49, 2018.
  * [13] Matheus Gadelha, Rui Wang, and Subhransu Maji.  Multiresolution tree networks for 3d point cloud processing.  In Proceedings of the European Conference on Computer Vision (ECCV), pages 103–118, 2018.
  * [14] Yaoqing Yang, Chen Feng, Yiru Shen, and Dong Tian.  Foldingnet: Point cloud auto-encoder via deep grid deformation.  In CVPR, pages 206–215, 2018.
  * [15] Thibault Groueix, Matthew Fisher, Vladimir G Kim, Bryan C Russell, and Mathieu Aubry.  A papier-mâché approach to learning 3d surface generation.  In CVPR, pages 216–224, 2018.
  * [16] Ruihui Li, Xianzhi Li, Ka-Hei Hui, and Chi-Wing Fu.  Sp-gan: Sphere-guided 3d shape generation and manipulation.  TOG, 40(4):1–12, 2021.
  * [17] Ruojin Cai, Guandao Yang, Hadar Averbuch-Elor, Zekun Hao, Serge Belongie, Noah Snavely, and Bharath Hariharan.  Learning gradient fields for shape generation.  In ECCV, pages 364–381. Springer, 2020.
  * [18] Shitong Luo and Wei Hu.  Diffusion probabilistic models for 3d point cloud generation.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 2837–2845, 2021.
  * [19] Linqi Zhou, Yilun Du, and Jiajun Wu.  3d shape generation and completion through point-voxel diffusion.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 5826–5835, 2021.
  * [20] 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, pages 61–70, 2020.
  * [21] Paritosh Mittal, Yen-Chi Cheng, Maneesh Singh, and Shubham Tulsiani.  Autosdf: Shape priors for 3d completion, reconstruction and generation.  arXiv preprint arXiv:2203.09516, 2022.
  * [22] Hengshuang Zhao, Li Jiang, Jiaya Jia, Philip HS Torr, and Vladlen Koltun.  Point transformer.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 16259–16268, 2021.
  * [23] Nico Engel, Vasileios Belagiannis, and Klaus Dietmayer.  Point transformer.  IEEE Access, 9:134826–134840, 2021.
  * [24] Meng-Hao Guo, Jun-Xiong Cai, Zheng-Ning Liu, Tai-Jiang Mu, Ralph R. Martin, and Shi-Min Hu.  Pct: Point cloud transformer.  Computational Visual Media, page 187–199, Apr 2021.
  * [25] Peng Xiang, Xin Wen, Yu-Shen Liu, Yan-Pei Cao, Pengfei Wan, Wen Zheng, and Zhizhong Han.  SnowflakeNet: Point cloud completion by snowflake point deconvolution with skip-transformer.  In Proceedings of the IEEE International Conference on Computer Vision (ICCV), 2021.
  * [26] Jinwoo Kim, Jaehoon Yoo, Juho Lee, and Seunghoon Hong.  Setvae: Learning hierarchical composition for generative modeling of set-structured data.  In CVPR, pages 15059–15068, 2021.
  * [27] An-Chieh Cheng, Xueting Li, Min Sun, Ming-Hsuan Yang, and Sifei Liu.  Learning 3d dense correspondence via canonical point autoencoder.  In NeurIPS, 2021.
  * [28] Yue Wang, Yongbin Sun, Ziwei Liu, Sanjay E Sarma, Michael M Bronstein, and Justin M Solomon.  Dynamic graph cnn for learning on point clouds.  TOG, 38(5):1–12, 2019.
  * [29] Nenglun Chen, Lingjie Liu, Zhiming Cui, Runnan Chen, Duygu Ceylan, Changhe Tu, and Wenping Wang.  Unsupervised learning of intrinsic structural representation points.  In CVPR, 2020.
  * [30] Aaron Van Den Oord, Oriol Vinyals, et al.  Neural discrete representation learning.  NeurIPS, 30, 2017.
  * [31] Jiahui Yu, Xin Li, Jing Yu Koh, Han Zhang, Ruoming Pang, James Qin, Alexander Ku, Yuanzhong Xu, Jason Baldridge, and Yonghui Wu.  Vector-quantized image modeling with improved vqgan.  ICLR, 2022.
  * [32] Zhaowei Cai, Avinash Ravichandran, Subhransu Maji, Charless Fowlkes, Zhuowen Tu, and Stefano Soatto.  Exponential moving average normalization for self-supervised and semi-supervised learning.  In CVPR, 2021.
  * [33] Angel X Chang, Thomas Funkhouser, Leonidas Guibas, Pat Hanrahan, Qixing Huang, Zimo Li, Silvio Savarese, Manolis Savva, Shuran Song, Hao Su, et al.  Shapenet: An information-rich 3d model repository.  arXiv preprint arXiv:1512.03012, 2015.
  * [34] Xiuming Zhang, Zhoutong Zhang, Chengkai Zhang, Joshua B Tenenbaum, William T Freeman, and Jiajun Wu.  Learning to Reconstruct Shapes From Unseen Classes.  In NeurIPS, 2018.
  * [35] Rundi Wu, Xuelin Chen, Yixin Zhuang, and Baoquan Chen.  Multimodal shape completion via conditional generative adversarial networks.  In European Conference on Computer Vision, pages 281–296. Springer, 2020.
  * [36] Minghua Liu, Lu Sheng, Sheng Yang, Jing Shao, and Shi-Min Hu.  Morphing and sampling network for dense point cloud completion.  In AAAI, pages 11596–11603, 2020.
  * [37] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In CVPR, pages 770–778, 2016.
  * [38] Vincent Dumoulin, Jonathon Shlens, and Manjunath Kudlur.  A learned representation for artistic style.  ICLR, 2017.
  * [39] David Lopez-Paz and Maxime Oquab.  Revisiting classifier two-sample tests.  ICLR, 2017.


# A Textbook Case of Pentagram Rigidity

Richard Evan Schwartz Supported by N.S.F. Grant DMS-2102802

###### Abstract

In this paper I will explain a rigidity conjecture that intertwines the deep
diagonal pentagram maps and Poncelet polygons. I will also establish a simple
case of the conjecture, the one involving the $3$-diagonal map on a convex
$8$-gon with $4$-fold rotational symmetry. This case involves a textbook
analysis of a pencil of elliptic curves.

##  1 Introduction

###  1.1 Conjecture and Result

Let $\mbox{\boldmath{$R$}}\mbox{\boldmath{$P$}}^{2}$ denote the real
projective plane. A polygon in
$\mbox{\boldmath{$R$}}\mbox{\boldmath{$P$}}^{2}$ is convex if its image under
a suitable projective transformation is a convex polygon in the standard
affine patch of $\mbox{\boldmath{$R$}}\mbox{\boldmath{$P$}}^{2}$. See §2.1 for
definitions. We call a convex polygon Poncelet if it is inscribed in one
ellipse and circumscribed about another ellipse. More generally, a Poncelet
polygon is one whose vertices lie in one conic section and whose edges lie in
lines tangent to another conic section.

Let $(n,k)$ be a pair of integers, not both even, with $n\geq 7$ and
$k\in(2,n/2)$. Given an $n$-gon $P_{1}$, we let $P_{2}=T_{k}(P_{1})$ be the
$n$-gon obtained by intersecting the successive $k$-diagonals of $P_{1}$.
Figure 1 shows this for $(n,k)=(8,3)$. The map $T_{k}$ is generically defined
and invertible. The same construction works in any field, but convexity is
important for us here. The maps $T_{k}$ and $T_{k}^{-1}$ are always defined on
convex $n$-gons, though the image of a convex $n$-gon under one of these maps
need not be convex.

Figure 1: $P_{1}$ and $P_{2}=T_{3}(P_{1})$.

Figure 1 gives an example of where $P_{1}$ is convex but $P_{2}$ is not.
Starting with $P_{0}$ we define the $(n,k)$-pentagram orbit $\\{P_{j}\\}$
where $P_{j}=T_{k}^{j}(P_{0})$.

###### Conjecture 1.1

Suppose that $\\{P_{j}\\}$ is an $(n,k)$-pentagram orbit and that $P_{j}$ is
convex for all $j\in\mbox{\boldmath{$Z$}}$. Then $\\{P_{j}\\}$ is convex
Poncelet for all $j\in\mbox{\boldmath{$Z$}}$.

I proved in [15] that if $P_{0}$ is a Poncelet polygon, $T(P_{0})$ and $P_{0}$
are projectively equivalent. Thus, to prove the conjecture it is enough to
prove that the hypotheses force $P_{0}$ to be convex Poncelet.

In this paper I will prove a simple but nontrivial case of the conjecture.

###### Theorem 1.2

Suppose that $P_{0}$ is an $8$-gon with $4$-fold rotational symmetry and
$\\{P_{j}\\}$ is the $(8,3)$-pentagram orbit. Then $P_{0}$ is regular if and
only if $P_{j}$ is convex for all $j$. More precisely

  1. 1.

$P_{0}$ has $8$-fold dihedral symmetry, with symmetry lines containing the
vertices, if and only if $P_{j}$ is convex for all $j\geq 0$.

  2. 2.

$P_{0}$ has $8$-fold dihedral symmetry, with symmetry lines bisecting the
edges, if and only if $P_{j}$ is convex for all $j\leq 0$.

A version of Theorem 1.2 appears to be true when $(8,3)$ is replaced by a
general pair $(n,k)$ when $n$ is even and $k$ is odd and the $n$-gons have
$(n/2)$-fold rotational symmetry. The proof should be similar. A much more
interesting generalization is to the case of centrally symmetric octagons,
because these include all Poncelet octagons. I have just finished proving this
generalization in a much longer paper. See [16].

The conjecture is not true for $n$ and $k$ both even. In this case, $T_{k}$ is
$2$-periodic (modulo scaling) when restricted to the space of $n$-gons with
$(n/2)$-fold rotational symmetry, and $T_{k}$ has some non-regular convex
fixed points modulo scale.

###  1.2 Context

The classic case of the pentagram map is $(n,2)$ for $n\geq 5$. The case $n=5$
has been studied e.g. by Clebsch in the $19$th century and Motzkin [9] in
middle of the $20$th century. In $1992$ I wrote a paper [13] defining the
pentagram map for general $n$-gons and proving in the convex case that the
forward orbit shrinks to a point. Very recently, M. Glick [2] found a kind of
formula for this collapse point.

It is nice to consider the map $T_{2}$ as defined on the space ${\cal
P\/}_{n}$ of $n$-gons modulo projective transformation. With the correct
labeling, $T_{2}$ is the identity on ${\cal P\/}_{5}$ and $2$-periodic on
${\cal P\/}_{6}$. I observed experimentally that the orbits of $T_{2}$ in
general seem to lie on tori. Motivated (for some reason) by the scattering
transform for the KdV equation, I found [14] about $n$ algebraically
independent invariants for $T_{2}$. These invariants are now called the
monodromy invariants or the pentagram integrals.

In [10], V. Ovsienko, S. Tabachnikov, and I showed that $T_{2}$ has an
invariant Poisson structure of corank $2$ in the odd case and corank $4$ in
the even case, and that the monodromy invariants Poisson-commute with respect
to this structure. This established the complete Arnold-Liouville
integrability of the pentagam map on the larger space ${\cal T\/}_{n}$ of so-
called twisted $n$-gons. Essentially what this means is that the space ${\cal
T\/}_{n}$, a space of dimension $2n$, has a singular foliation by manifolds of
dimension about $n$ such that the restriction of $P_{2}$ to each manifold is a
translation in suitable coordinates. When these manifolds are compact they are
necessarily finite unions of tori.

Subsequently, we proved in [11] that $T_{2}$ is Arnold-Liouville integrable on
${\cal P\/}_{n}$, which is naturally a codimension $8$ subvariety of ${\cal
T\/}_{n}$. For the subset of convex $n$-gons, the manifolds in the singular
foliation are compact and hence finite unions of tori. At the same time, F.
Soloviev [19] proved that the pentagram map is algebro-geometrically
integrable on ${\cal P\/}_{n}$. This implies in particular that the torus
foliation discussed above is naturally an abelian fibration, with the
individual tori having natural desciptions as Jacobian varieties for certain
Riemann surfaces. Very recently, M. Weinreich [20] proved that $T_{2}$ is
algebro-geometrically integrable in any field of characteristic not equal to
$2$. In [3], M. Glick related the pentagram map to a cluster algebra.

By now there are many generalizations of the pentagram map, and also a number
of ways to generate invariant functions and the invariant Poisson structure.
In [1], M. Gekhtman, M. Shapiro, S. Tabachnikov, A. Vainshtein generalized the
pentagram map to similar maps using longer diagonals, and defined on spaces of
so-called corrugated polygons in higher dimensions. The work in [1] also
generalizes Glick’s cluster algebra and establishes the complete integrability
of these maps in some form. In [7], G. Mari-Beffa defines higher dimensional
generalizations of the pentagram map and relates their continuous limits to
various families of integrable PDEs. See also [8]. In [5], B. Khesin and F.
Soloviev obtain definitive results about higher dimensional analogues of the
pentagram map, their integrability, and their connection to KdV-type
equations.

The little survey above is not meant to be complete. Now let me explain how
these various results are related to the Pentagram Rigidity Conjecture above.
First of all, the map $T_{k}$ is the one used in [1]. It would be nice if one
could conclude from [1] that $T_{k}$ is completely integrable on ${\cal
P\/}_{n}$, but this has not been directly worked out. The spaces of corrugated
polygons are somewhat different than spaces of ordinary polygons, though in
some sense closely related. Ordinary polygons are limits of corrugated
polygons under a kind of flattening operation. Let me just leave it by saying
that $T_{k}$ is certainly believed to be completely integrable on ${\cal
P\/}_{n}$ in some sense.

The Pentagram Rigidity Conjecture is really about the global geometry of the
torus foliation of ${\cal P\/}_{n}$ (presumably) associated to $T_{k}$. The
smaller space ${\cal C\/}_{n}$ of convex $n$-gons modulo projective
transformations is a subset of ${\cal P\/}_{n}$. For $k\in[3,n/2)$ the tori in
this foliation probably are not contained in ${\cal C\/}_{n}$. So, if $T_{k}$
is not the identity on one of these tori, and moreover the intersection of the
torus with ${\cal C\/}_{n}$ is not too large, then the orbit of $T_{k}$ on
this torus cannot stay in ${\cal C\/}_{n}$. (See Lemma 2.1 below.) This
observation would prove the conjecture for the $n$-gons corresponding to this
torus. The Poncelet polygons in ${\cal C\/}_{n}$ also lie on these tori, but
$T$ is the identity there.

Motivated by the Pentagram Rigidity Conjecture, A. Izosimov [4] has recently
proved that if $n$ is odd and $P\in{\cal C\/}_{n}$ is a fixed point of $T_{2}$
then in fact $P$ is a Poncelet polygon. So, we now can say that for $n$ odd
points in ${\cal C\/}_{n}$ are fixed by $T_{2}$ if and only if they are
Poncelet. The convexity is important here. Izosimov gave some easy examples of
$n$-gons in $\mbox{\boldmath{$C$}}\mbox{\boldmath{$P$}}^{2}$ that are fixed by
$T_{2}$ but not Poncelet. The parity of $n$ is also important. As I mentioned
above, the result is not true when $n$ is even. Presumably, Izosimov’s result
would also work for general pairs $(n,k)$ where both numbers are not even.

In the case I consider, that of $T_{3}$ acting on $8$-gons with $4$-fold
rotational symmetry, there is just a single invariant for the map, and its
level curves are nonsingular elliptic curves except when they contain points
corresponding to octagons having $8$-fold dihedral symmetery. These are the
curves I analyze in §2.2. These elliptic indeed stretch outside ${\cal
C\/}_{8}$ in the appropriate sense, and this is enough to prove Theorem 1.2.
See Figure 2 in §3.4.

The various invariant-generating machines for the pentagram map probably would
turn up the invariant I found, but these machines are better developed for
$T_{2}$ than they are for $T_{3}$. I just guessed the invariant for $T_{3}$ by
looking at the picture, and then checked algebraically that it works. I will
explain in §3.2 what led me to the invariant.

There are two other connections I want to make between the Pentagram Rigidity
Conjecture and other areas of mathematics. When I originally thought of this
conjecture, about $30$ years ago, I had imagined it as a projective geometry
analogue of the circle packing rigidity theorem [12] of B. Rodin and D.
Sullivan. Much more recently, it occured to me that the conjecture is
something like a discrete analogue of the Birkhoff-Poritsky Conjecture about
billiards in strictly convex ovals. This conjecture says roughly that if a
neighborhood of the boundary of the (cylindrical) billiard phase space is
foliated by invariant curves (corresponding to caustics) then the oval is an
ellipse.

###  1.3 Organization

In §2 I will give some background information about projective geometry and
also analyze the family of elliptic curves that arises in the proof of Theorem
1.2. I will also present a few well-known results about complex tori. In §3 I
give the proof of Theorem 1.2.

The interested reader can download the computer program I wrote, which does
experiments with the $3$-diagonal map on centrally symmetric octagons. The
location of the program is
http://www.math.brown.edu/$\sim$res/Java/OCTAGON.tar:

###  1.4 Acknowledgements

I would like to thank Misha Bialy, Misha Gehktman, Anton Izosimov, Joe
Silverman, Sergei Tabachnikov, and Max Weinreich for helpful conversations.

##  2 Preliminaries

###  2.1 Projective Geometry

The real projective plane $\mbox{\boldmath{$R$}}\mbox{\boldmath{$P$}}^{2}$ is
the space of lines through the origin in $\mbox{\boldmath{$R$}}^{3}$.
Equivalently it is the space of scale-equivalence-classes of nonzero vectors
in $\mbox{\boldmath{$R$}}^{3}$. Points in
$\mbox{\boldmath{$R$}}\mbox{\boldmath{$P$}}^{2}$ will be denote by $[x:y:z]$.
This point represents the line through the origin and $(x,y,z)$. The quotient
map
$\mbox{\boldmath{$R$}}^{3}\to\mbox{\boldmath{$R$}}\mbox{\boldmath{$P$}}^{2}$
is called projectivization.

There is a natural inclusion
$\mbox{\boldmath{$R$}}^{2}\to\mbox{\boldmath{$R$}}\mbox{\boldmath{$P$}}^{2}$
given by

$(x,y)\to[x:y:1].$ (1)

The image of this inclusion is known as the standard affine patch. I often
identify $\mbox{\boldmath{$R$}}^{2}$ with its image under this inclusion, and
when speaking about points in the affine patch I will often write $(x,y)$ for
$[x:y:1]$. The inclusion in Equation 1 has an inverse, given by

$[x:y:z]\to(x/z,y/z).$ (2)

The line at infinity is the subset of
$\mbox{\boldmath{$R$}}\mbox{\boldmath{$P$}}^{2}$ outside the standard affine
patch. The line at infinity consists of points of the form $[x:y:0]$. More
generally, a line in $\mbox{\boldmath{$R$}}\mbox{\boldmath{$P$}}^{2}$ is the
set of members represented by lines in a $2$-dimensional subspace of
$\mbox{\boldmath{$R$}}^{3}$. We can also represent lines by triples $[a:b:c]$.
This point represents the linear subspace given by the equation $ax+by+cz=0$.
Conveniently, the line through $2$ points is represented by the cross product
of the corresponding vectors. Likewise, the intersection of $2$ lines is given
by the cross product of the corresponding vectors. These facts make
computations with the pentagram map very easy.

The dual projective space $\mbox{\boldmath{$R$}}\mbox{\boldmath{$P$}}^{2}_{*}$
is the space of lines in $\mbox{\boldmath{$R$}}\mbox{\boldmath{$P$}}^{2}$. As
our notation suggests, there is an isomorphism between
$\mbox{\boldmath{$R$}}\mbox{\boldmath{$P$}}^{2}$ and
$\mbox{\boldmath{$R$}}\mbox{\boldmath{$P$}}^{2}_{*}$. The isomorphism sends
the point represented by $[u:v:w]$ to the line represented by $[u:v:w]$. This
isomorphism sends collinear points to coincident lines.

Note that all the same words apply with the field $R$ replacing the field $C$.
Thus $\mbox{\boldmath{$C$}}\mbox{\boldmath{$P$}}^{2}$ is the complex
projective plane. A projective variety in
$\mbox{\boldmath{$C$}}\mbox{\boldmath{$P$}}^{2}$ is the projectivization of
the set $V(x,y,z)=0$ where $V(x,y,z)$ is a homogeneous polynomial in $3$
variables. This variety is called nonsingular if the (formal) gradient $\nabla
V$ is everywhere nonzero on the set $V(x,y,z)=0$. When $V$ is cubic and
nonsingular the corresponding projective variety is a smooth Riemann surface
of genus $1$, also known as a complex torus. See [18].

###  2.2 A Family of Cubics

In this section we study the solutions to the equation

$\frac{(x-y)(x^{2}+y^{2}-1)}{xy}=\lambda,\hskip
30.0pt(x-y)(x^{2}-y^{2}-1)-\lambda xy=0.$ (3)

The second equation is a rearrangement of the first one. To bring this
equation into the form we mentioned at the end of the last section, we expand
it out and then homogenize it by padding the $z$-variable. This gives us the
equation

$V(x,y,z)=x^{3}-y^{3}-x^{2}y+xy^{2}-xz^{2}+yz^{2}-\lambda xyz=0.$ (4)

Let $E_{\lambda}$ denote the complex projective variety corresponding to
$V=0$. Let $\rho$ be reflection in the line $\\{y=-x\\}$. Call this line $L$.
Call a subset of $\mbox{\boldmath{$R$}}\mbox{\boldmath{$P$}}^{2}$ bounded if
it lies in $\mbox{\boldmath{$R$}}^{2}$ and otherwise unbounded. Below, I will
prove two results:

  1. 1.

For all $\lambda\not=0,\pm 2,\pm 4i\sqrt{2}$ the variety $E_{\lambda}$ is
nonsingular, and hence a complex torus.

  2. 2.

When $\lambda\in\mbox{\boldmath{$R$}}-\\{-2,0,2\\}$, the set
$E_{\lambda}\cap\mbox{\boldmath{$R$}}\mbox{\boldmath{$P$}}^{2}$ consists of
$2$ smooth loops, both $\rho$-invariant, one bounded and one unbounded. The
bounded loop intersects $L$ twice and the unbounded loop intersects $L$ once.

Figure 2 in the next chapter shows a rough but topologically accurate picture
of $E_{\lambda}\cap\mbox{\boldmath{$R$}}^{2}$ for $\lambda\in(0,2)$.

First Statement: We want to see that the gradient never vanishes on the level
set $V=0$. We compute

$\nabla V=\left[\begin{matrix}V_{x}\cr V_{y}\cr
V_{z}\end{matrix}\right]=\left[\begin{matrix}-\lambda
yz+3x^{2}-2xy+y^{2}-z^{2}\cr-\lambda xz-x^{2}+2xy-3y^{2}+z^{2}\cr
2z(y-x)-\lambda xy\end{matrix}\right]$ (5)

To analyze this, let us first consider the points in the line at infinity that
belong to $V=0$. Indpendent of $\lambda$, these are the $3$ points

$[1:1:0],\hskip 30.0pt[i:1:0],\hskip 30.0pt[-i:1:0].$

Since both $x,y\not=0$ and $z=0$ for these points, we see from the equation
that the third coordinate of $\nabla V$ is nonzero. This takes care of these
points.

To consider the remaining points of $V$ we can set $z=1$. If $\nabla V=0$ we
have $V_{x}+V_{y}=0$. This gives one of two equations:

$y=-x,\hskip 30.0pty=\frac{2x-\lambda}{2}.$ (6)

When $y=-x$ we have

$\nabla V=\left[\begin{matrix}\lambda x+6x^{2}-1\cr-\lambda x-6x^{2}+1\cr
x(\lambda x-4)\end{matrix}\right]$ (7)

This can only vanish when $x=4/\lambda$. But then

$V\bigg{(}\frac{4}{\lambda},-\frac{4}{\lambda},1\bigg{)}=\frac{256}{\lambda^{3}}+\frac{8}{\lambda},$

and this vanishes only if $\lambda=\pm 4i\sqrt{2}$.

When $y=(2x-\lambda)/2$ we have

$V(x,y,1)=\frac{\lambda(4-\lambda^{2})}{8}.$

This can only vanish when $\lambda=0,\pm 2$. $\spadesuit$

Second Statement: Let $\lambda\in\mbox{\boldmath{$R$}}-\\{-2,0,2\\}$. The set
$E_{\lambda}\cap\mbox{\boldmath{$R$}}\mbox{\boldmath{$P$}}^{2}$ is a finite
disjoint union of smooth loops, permuted by $\rho$.

If $C$ is a bounded component and $\rho(C)\not=C$ then $C\cup\rho(C)$ would
intersect some line $4$ times, a contradiction. Hence $\rho$ preserves each
bounded component, and each bounded component intersects $L$ twice at right
angles. Since $E_{\lambda}$ intersects
$\mbox{\boldmath{$C$}}\mbox{\boldmath{$P$}}^{2}-\mbox{\boldmath{$C$}}^{2}$
three times, and exactly one of these intersection points, namely $[1:1:0]$,
lies in $\mbox{\boldmath{$R$}}\mbox{\boldmath{$P$}}^{2}$, we see that
$E_{\lambda}\cap\mbox{\boldmath{$R$}}\mbox{\boldmath{$P$}}^{2}$ has one
unbounded component.

Note that $E_{\lambda}\cap L$ always consists of $3$ points, namely $(x,-x)$
for $x=0$ and

$x==\frac{-\lambda\pm\sqrt{\lambda^{2}+32}}{8}\not=0.$

We conclude that
$E_{\lambda}\cap\mbox{\boldmath{$R$}}\mbox{\boldmath{$P$}}^{2}$ must have
exactly two components, both $\rho$-invariant, one bounded and one unbounded,
and the intersections are as claimed. $\spadesuit$

###  2.3 Uniformization

Let $E\subset\mbox{\boldmath{$C$}}\mbox{\boldmath{$P$}}^{2}$ be nonsingular
cubic variety. As we mentioned above, $E$ is a complex torus. Let $f:E\to E$
be some birational map which is also invertible. The birational nature of $f$
implie that all the singularities of $f$ on $E$ are removable. This means that
$f$ is a biholomorphic map of $E$ and orientation preserving.

As is well known, there is also a biholomorphic map
$\phi:E\to\mbox{\boldmath{$C$}}/\Lambda$ where
$\Lambda\subset\mbox{\boldmath{$C$}}$ is a lattice. The map $\phi$ conjugates
$f$ to an isometry of $\mbox{\boldmath{$C$}}/\Lambda$. Thus, we may simply
equip $E$ with the coordinates coming from $\phi$ and treat $E$ as a flat
torus and $f:E\to E$ as an orientation preserving isometry. We call this the
flat structure on $E$.

###  2.4 Minor Subsets of Tori

In this section I will prove a general lemma about flat tori. The only case
required for the proof of Theorem 1.2 is that of the circle
$\mbox{\boldmath{$R$}}/\mbox{\boldmath{$Z$}}$, but the general case might be
useful for a more general version of the conjecture. The general case rather
quickly reduces to the circle case anyway.

Say that a subset
$S\subset\mbox{\boldmath{$R$}}^{n}/\mbox{\boldmath{$Z$}}^{n}$ is minor if
there is some translation $\phi$ of
$\mbox{\boldmath{$R$}}^{n}/\mbox{\boldmath{$Z$}}^{n}$ such that
$\phi(S)\subset(0,1/2)^{n}$. In general, say that a subset $S$ of a flat torus
is minor if an affine isomorphism from the flat torus to
$\mbox{\boldmath{$R$}}^{n}/\mbox{\boldmath{$Z$}}^{n}$ carries $S$ to a minor
subset.

###### Lemma 2.1

Suppose $p\in S\subset Y$ where $S$ is a minor subset of the flat torus $Y$.
Suppose that $f:Y\to Y$ is a nontrivial translation. Then the forward orbit
$\\{f^{k}(p)|\ k>0\\}$ is not contained in $S$.

Proof: By affine symmetry it suffices to prove this when
$Y=\mbox{\boldmath{$R$}}^{n}/\mbox{\boldmath{$Z$}}^{n}$. The translation $f$
has a nontrivial action in at least one coordinate. Let
$f:\mbox{\boldmath{$R$}}^{n}/\mbox{\boldmath{$Z$}}^{n}\to\mbox{\boldmath{$R$}}/\mbox{\boldmath{$Z$}}$
be the projection onto this coordinate. By construction $f(S)$ is minor in
$\mbox{\boldmath{$R$}}/\mbox{\boldmath{$Z$}}$ and $f$ covers a nontrivial
translation of $\mbox{\boldmath{$R$}}/\mbox{\boldmath{$Z$}}$. This reduction
shows that it suffices to prove our result for
$Y=\mbox{\boldmath{$R$}}/\mbox{\boldmath{$Z$}}$. This is what we do. If
$f(p)\not\in S$ then we are done. Otherwise $|p-f(p)|<1/2$. But then the
forward orbit of $p$ is at least $1/4$-dense. This means that every point of
$\mbox{\boldmath{$R$}}/\mbox{\boldmath{$Z$}}$ is within $1/4$ of some point in
the forward orbit. In particular, the point $\zeta$ diametrically opposed from
the midpoint of $S$ has this property. But then the orbit point that is within
$1/4$ of $\zeta$ is disjoint from $S$. $\spadesuit$

##  3 Proof of the Result

###  3.1 Formulas

Let $\cal X$ denote the space of labeled $8$-gons with $4$-fold rotational
symmetry modulo similarities in the plane. We normalize so that the $4$-fold
symmetry in question is the map

$\rho([x:y:z])=[-y:x:z].$ (8)

This map fixes the origin $(0,0)$ in the affine patch and preserves the whole
affine patch. It is just rotation by $90$ degrees counterclockwise.

One possibility is that $\rho$ cycles the vertex labels by $2$ and the other
possibility is that $\rho$ cycles the vertex labels by $-2$. We only consider
the first possibility; the second possibility is essentially treated by
symmetry. For the purpose of getting formulas, we ignore for now the members
of $\cal X$ which have points on the line at infinity. We call the remaining
members finite. In other words, the finite members lie entirely in the
standard affine patch.

The Map: Every finite member of $\cal X$ has a canonical representative
$P(x,y)$ with vertices

$(1,0),\hskip 4.0pt(x,y),\hskip 4.0pt(0,1),\hskip 4.0pt(-y,x),\hskip
4.0pt(-1,0),\hskip 4.0pt(-x,-y),\hskip 4.0pt(0,-1),\hskip 4.0pt(y,-x).$ (9)

Here $(x,y)$ is really $[x:y:1]$, etc.

Expressed in these coordinates, and with a suitable labeling scheme, the map
$T_{3}$ is given by $T_{3}(x,y)=(x^{\prime},y^{\prime})$, where

$x^{\prime}=-Ax(B-2xy),\hskip 30.0pty^{\prime}=+Ay(B+2xy),$ (10)

$A=\frac{\alpha_{10}+\alpha_{20}}{(1+\alpha_{10})(\alpha_{20}+2\alpha_{30}+\alpha_{40}-\alpha_{11}-2\alpha_{12}+\alpha_{22})},\hskip
20.0pt\alpha_{ij}=x^{i}y^{j}+y^{i}x^{j}.$

$B=\beta_{10}+2\beta_{20}+\beta_{30}+\beta_{12},\hskip
20.0pt\beta_{ij}=x^{i}y^{j}-y^{i}x^{j}.$ (11)

In other words, $T_{3}$ sends the polygon $P(x,y)$ to the polygon
$P(x^{\prime},y^{\prime})$. I computed this map (and everything else in the
paper) using Mathematica [6].

The Invariant: Define the function

$\Psi(x,y)=\frac{(x-y)(x^{2}-y^{2}-1)}{xy}.$ (12)

A direct calculation shows that $\Psi\circ T_{3}=\Psi$. This is the invariant
mentioned in the introduction. In the next section I will explain where it
comes from.

Projective Duality: Each $8$-gon $P$, defined by its vertices, gives rise to
an $8$-gon $P^{*}$ in the dual space defined by the successive lines. The
successive “vertices” of $P^{*}$ are the successive lines extending the edges
of $P$. Using our isomorphism, we get a second polygon $(P^{*})^{\\#}$ in
$\cal X$. The operation $P\to(P^{*})^{\\#}$ is an involution given
algebraically by the map

$D(x,y)=\bigg{(}-\frac{y\left(x^{2}-x\\!+\\!y^{2}-y\right)}{x\left(x^{2}-2x+y^{2}+1\right)},\frac{y(x+y-1)}{x\left(x^{2}-2x+y^{2}+1\right)}\bigg{)}$
(13)

Direct calculations show

$\Psi\circ D=\Psi,\hskip 30.0ptDT_{3}D^{-1}=T_{3}^{-1}.$ (14)

One can also deduce these equations from abstract properties of projective
duality. I will leave this to the interested reader.

Symmetries and Factorization: Define

$\sigma_{1}(x,y)=(y,x),\hskip 30.0pt\sigma_{2}(x,y)=(-x,-y).$ (15)

A direct calculation shows that

$\sigma_{1}T_{3}\sigma_{1}^{-1}=T_{3},\hskip
30.0pt\sigma_{2}T_{3}\sigma_{2}^{-1}=T_{3}^{-1}.$ (16)

Geometrically, the map $\sigma_{2}$ swaps the regular and star-regular
$8$-gons. Beautifully, a calculation shows that

$T_{3}=(D\circ\sigma_{2})^{2}.$ (17)

In other words $T_{3}$ is the square of a simpler map. Readers familiar with
the pentagram map will not be surprised by this kind of factorization. The map
$D\circ\sigma_{2}$ satisfies the rule

$\Psi\circ(D\circ\sigma_{2})=-\Psi.$ (18)

This equation would probably be the quickest way for the reader to show,
without symbolic manipulation, that $\Psi$ is an invariant for $T_{3}$.

###  3.2 Special Cases

I first noticed that $T_{3}$ behaved nicely on the sets described in this
section. I then systematically tested Laurent monomials in the defining
functions for these sets and this led me to $\Psi$.

The Coordinate Axes: First of all

$T_{3}(x,0)=(-x,0),\hskip 30.0ptT_{3}(0,y)=(0,-y),$ (19)

So, $T_{3}$ preserves the coordinate axes and is an involution there. The
corresponding octagons look (to me) like the blades of a circular saw.

The Diagonal Line: Let $\Delta$ denote the diagonal line $x=y$. The $8$-gon
$P_{0}=P(x,x)$ has $8$-fold dihedral symmetry, with the lines of symmetry
going through the vertices. To study the $(8,3)$-pentagram orbit $\\{P_{j}\\}$
we compute

$T_{3}(x,x)=(x^{\prime},x^{\prime}),\hskip 30.0ptx^{\prime}=\frac{1+x}{1+2x}.$
(20)

The map $T_{3}$ is given by a projective transformation of $\Delta$. The fixed
points are

$p_{\pm}=\pm(1/\sqrt{2},1/\sqrt{2}).$ (21)

The fixed point $p_{+}$, which corresponds to the regular $8$-gon, is
attracting. The fixed point $p_{-}$, which corresponds to the star-regular
$8$-gon, is repelling. Thus, every orbit on $\Delta$ aside from $p_{-}$, is
attracted to $p_{+}$ So, if $P_{0}$ is not regular then $P_{j}$ is convex for
all $j\geq 0$. The inverse map $T_{3}^{-1}$ has $p_{-}$ as an attracting fixed
point and $p_{+}$ as a repelling fixed point. Hence $P_{j}$ is non-convex for
all $j$ sufficiently negative.

The Unit Circle: Let $S^{1}$ denote the unit circle. Here $S^{1}$ corresponds
to $8$-gons with $8$-fold dihedral symmetry in which the lines of symmetry
bisect the sides. These $8$-gons are dual to the ones on $\Delta$ and indeed
the map $D$ defined above has the property that $D(\Delta)=S^{1}$. Thus, the
action of $T_{3}^{-1}$ on $S^{1}$ is conjugate to the action of $T_{3}$ on
$\Delta$. In particular, if we start with $C_{0}$ convex then $C_{j}$ is
convex for all $j\leq 0$ but $C_{j}$ is non-convex for all $j$ sufficiently
positive.

This is a case that the reader can easily experiment with. Just draw a “stop
sign” and see what the $3$-diagonal map does.

Other Special Orbits: The material here is not needed for the proof of Theorem
1.2 but it is nice. Let $L_{\pm 2,1}$ denote the diagonal line $y=x\mp 1$ and
let $L_{\pm 2,2}$ denote the circle of radius $1/\sqrt{2}$ centered at $(\mp
1/2,\pm 1/2)$. The union $L_{\pm 2}=L_{\pm 2,1}\cup L_{\pm 2}$ is the level
set $\Psi=\pm 2$. Each of these two level sets is the disjoint union of a
diagonal line and a circle. The map $T_{3}^{2}$ preserves each component and
acts there with order $3$. For example

$T_{3}^{2}(x,x+1)=(x^{\prime\prime},x^{\prime\prime}+1),\hskip
30.0ptx^{\prime\prime}=\frac{-1-x}{x}.$ (22)

###  3.3 Nontriviality

Let $\lambda\in\mbox{\boldmath{$R$}}-\\{-2,0,2\\}$. We know that
$E_{\lambda}\cap\mbox{\boldmath{$R$}}^{2}$ contains one bounded loop and one
unbounded loop. Since $T_{3}$ preserves $E_{\lambda}$ and
$\mbox{\boldmath{$R$}}^{2}$ and
$\mbox{\boldmath{$R$}}\mbox{\boldmath{$P$}}^{2}$, we see that $f=T_{3}^{2}$
preserves both components of
$E_{\lambda}\cap\mbox{\boldmath{$R$}}\mbox{\boldmath{$P$}}^{2}$. Let
$\Upsilon$ be one of these.

###### Lemma 3.1

$f$ cannot be the identity on $\Upsilon$.

Proof: Suppose $f$ is the identity on $\Upsilon$. Since $f$ is a orientation
preserving isometry $E_{\lambda}$ in the flat coordinates, we see that $f$
must be the identity on $E_{\lambda}$. We saw in §2.2 that $E_{\lambda}$
intersects the line $\\{y=-x\\}$ in $3$ distinct points. Hence
$f(x,-x)=(x,-x)$ for two distinct nonzero points $(x_{1},-x_{1})$ and
$(x_{2},-x_{2})$ in $E_{\lambda}$. Setting the sum of the coordinates of
$f(x,-x)$ equal to $0$, we get

$\frac{(4x^{2}(-1-2x^{2}+x^{4}-6x^{6}+32x^{10}))}{((-1+x^{2}+4x^{4})(1-2x^{2}+x^{4}+24x^{6}+16x^{8}))}=0.$
(23)

The only nonzero real roots are

$x=\pm\frac{1}{2}\sqrt{\frac{1}{2}(1+\sqrt{17})}.$

But the corresponding points satisfy
$\Psi(x_{1},-x_{1})=-\Psi(x_{2},-x_{2})\not=0$ so these points cannot both lie
in $E_{\lambda}$. This is a contradiction. $\spadesuit$

Remark: The points $(x_{1},-x_{1})$ and $(x_{2},-x_{2})$ constructed in the
previous proof lie on level sets where $f$ has order $2$. In particular,
$f^{2}$ is the identity on these two level sets.

We call an orientation preserving isometry of a metric circle a translation.

###### Lemma 3.2

$f$ is a nontrivial translation of $\Upsilon$ in the flat coordinates.

Proof: Since $f$ is a nontrivial isometry of $\Upsilon$, we see that $f$ is
either a translation or an orientation reversing isometry on $\Upsilon$. In
the latter case, $f$ must have order $2$ on $\Upsilon$. If $f$ is orientation
reversing on $\Upsilon$ then $f$ is orientation reversing on nearby level
sets. This means that $f^{2}$ is the identity on all nearby level sets. But
then $f^{2}$ is the identity on an open subset of $\mbox{\boldmath{$R$}}^{2}$.
Since $f$ is a birational map, this forces $f^{2}=T_{3}^{4}$ to be the
identity. This is false. $\spadesuit$

###  3.4 The End of the Proof

Let ${\cal C\/}\subset{\cal X\/}$ denote the subset of convex $8$-gons. Let
${\cal C\/}_{-}$ and ${\cal C\/}_{+}$ respectively denote the subsets of $\cal
C$ corresponding to $8$-gons with $8$-fold dihedral symmetry with the lines of
symmetry respectively going through the vertices and bisecting the edges. Note
that ${\cal C\/}_{+}\cap{\cal C\/}_{-}$ is precisely the point representing
the regular $8$-gon.

The analysis of the special sets in §3.2 reduces us to considering polygons in
${\cal C\/}-{\cal C\/}_{+}-{\cal C\/}_{-}$. To finish the proof it suffices to
show that when we have $P_{0}\in{\cal C\/}-{\cal C\/}_{-}-{\cal C\/}_{+}$
there are indices $i<0<j$ such that $P_{i},P_{j}\not\in{\cal C\/}$. Our choice
of $P_{0}$ implies that $\Psi(p)\in\mbox{\boldmath{$R$}}-\\{-2,0,2\\}$. Here
$p$ is the point in $\cal C$ representing $P_{0}$. But then $p\in
E_{\lambda}\cap\mbox{\boldmath{$R$}}^{2}$, where $E_{\lambda}$ is the complex
torus discussed in §2.2.

Figure 2 shows a picture of the relevant sets. The shaded semidisk is $\cal
C$. The lightly shaded disk is the unit disk. The sets ${\cal C\/}_{+}$ and
${\cal C\/}_{-}$ are the intersection of ${\cal C\/}$ with the unit circle and
with the diagonal line respectively. The blue curve is a rough but
topologically accurate sketch of
$E_{\lambda}\cap\mbox{\boldmath{$R$}}\mbox{\boldmath{$P$}}^{2}$ when
$\lambda\in(0,2)$. If $\lambda\in(-2,0)$ the picture would be reflected in the
line $\\{y=x\\}$.

Figure 2: A topologically accurate sketch of
$E_{\lambda}\cap\mbox{\boldmath{$R$}}^{2}$ for $\lambda\in(0,2)$.

Let $\Upsilon$ be the component of
$E_{\lambda}\cap\mbox{\boldmath{$R$}}\mbox{\boldmath{$P$}}^{2}$ containing
$p$. We equip $\Upsilon$ with its flat coordinates. Let $f=T_{3}^{2}$ as in
the previous section. We know that $f$ is a nontrivial translation of
$\Upsilon$. Let $\rho$ be the reflection in the line $\\{y=-x\\}$. This is the
red diagonal in Figure 2. We showed in §2.2 that $\rho(\Upsilon)=\Upsilon$.
Being holomorphic, $\rho$ is an isometry of $\Upsilon$ in the flat
coordinates. The two sets $\Upsilon\cap{\cal C\/}$ and $\rho(\Upsilon\cap{\cal
C\/})$ are disjoint and have equal length. Hence $\Upsilon\cap{\cal C\/}$ is
minor in the sense of Lemma 2.1. By Lemma 2.1, we have
$f^{j}(p)\not\in\Upsilon\cap{\cal C\/}$ for some $j>0$. Applying the same
argument to $f^{-1}$ gives some $i<0$ such that $f^{i}(p)\not\in{\cal C\/}$.
This completes the proof of Theorem 1.2.

## References

  * [1] M. Gekhtman, M. Shapiro, S.Tabachnikov, A. Vainshtein, Higher pentagram maps, weighted directed networks, and cluster dynamics, Electron. Res. Announc. Math. Sci. 19 21012, 1–17
  * [2] M. Glick, The Limit Point of the Pentagram Map, International Mathematics Research Notices 9 (2020) 2818–2831
  * [3] M. Glick, The pentagram map and $Y$-patterns, Adv. Math. 227, 2012, 1019–1045.
  * [4] A. Izosimov, The pentagram map, Poncelet polygons, and commuting difference operators, arXiv 1906.10749 (2019)
  * [5] B. Khesin, F. Soloviev Integrability of higher pentagram maps, Mathem. Annalen. (to appear) 2013
  * [6] Wolfram Research Inc., Mathematica, Wolfram Programming Lab, Champaign, IL (2021)
  * [7] G. Mari Beffa, On Generalizations of the Pentagram Map: Discretizations of AGD Flows, arXiv:1303.5047, 2013
  * [8] G. Mari Beffa, On integrable generalizations of the pentagram map
arXiv:1303.4295, 2013

  * [9] Th. Motzkin, The pentagon in the projective plane, with a comment on Napier’s rule, Bull. Amer. Math. Soc. 52, 1945, 985–989.
  * [10] V. Ovsienko, R. Schwartz, S. Tabachnikov, The pentagram map: A discrete integrable system, Comm. Math. Phys. 299, 2010, 409–446.
  * [11] V. Ovsienko, R. Schwartz, S. Tabachnikov, Liouville-Arnold integrability of the pentagram map on closed polygons, to appear in Duke Math. J.
  * [12] B. Rodin and S. Sullivan, The convergence of circle packings to the Riemann maping, J. Diff. Geom. 26 (1987) 349–360
  * [13] R. Schwartz, The pentagram map, Experiment. Math. 1, 1992, 71–81.
  * [14] R. Schwartz, Discrete monodromy, pentagrams, and the method of condensation, J. of Fixed Point Theory and Appl. 3, 2008, 379–409.
  * [15] R. Schwartz, The Poncelet Grid, Advances in Geometry 7 (2006)
  * [16] R. Schwartz, Pentagram Rigidity for Centrally Symmetric Octagons, preprint (2021).
  * [17] R. Schwartz, S. Tabachnikov, Elementary surprises in projective geometry, Math. Intelligencer (2010)
  * [18] J. Silverman, The arithmetic of elliptic curves, Springer
  * [19] F. Soloviev Integrability of the Pentagram Map, Duke Math J.
  * [20] M. Weinreich, The Algebraic Dynamics of the Pentagram Map, (2021) arXiv: 2104.06211