Read: Points - Surface | Voronoi + MLS

PDF | SemScho

Notes

(2024-06-02)

Abstract

Task: Display point set surface.
Solution:
1. Define a smooth manifold surface based on local maps and MLS.
  - local map from differential geometry:
  - “local”: neighbors
2. Upsampling and downsampling to fit the points spacing with the screen space resolution.
3. The approximation error is bounded.
Advantage: Applicable for any point set

Introduction

Task: Use point set as the shape representation
Why matter?
1. Point sets data are getting popular.
2. Representing a highly detailed surface with primitives requires substantial small unit that’s smaller than a single pixel.
Problems:
1. Although point set is an economical representation, point sets contain noisy and redundant points.
2. Point cloud is discrete without explicit surface.
Solution:
1. Adjust the density of points to reconstruct a smooth surface.
2. Use polynomials to approximate surface with MLS
  - Polynomials: What are basis functions are used to fit the surface function?
    - What does the surface function look like?
  - Projection (affine transformation): weighted sum / linear combination of x,y coordinate
    $$ \begin{bmatrix} a_1 \\\ a_2 \\\ a_3 \end{bmatrix} [1 \quad x \quad x^2] [^x_y] $$
  - MLS: The partial derivative of error w.r.t. coefficient matrix 𝐀 equals 0.
Explain idea:
- Generating new points is a sampling process on the hidden surface.
  - Doubt: Can generative models be applied? as this is a sampling process.
  - The error has a limited bound.
- Rendering a point set is achieved by up-sampling and down-sampling the point set.
  - The sampling error is bounded. How to prove?
- Reduce the input point set $P=\\{𝐩ᵢ\\}$ to “representation points” $R=\\{𝐫ᵢ\\}$ defining an MLS surface $S_R$, which approximates the original surface $S_P$.
  - Sounds like Variational Inference: Let an assumed posterior distribution of z $q(z|x)$ with learnable params (μ,σ) to approximate the true intractable posterior distribution of z $P(z|x)$, through minimizing the KL-divergence.
    
    On the other hand, if analyzing ELBO, the goal of maximizing the log-likelihood of x is transformed into maximizing the variational lower bound: ELBO.
  - Figuratively, use a proxy object to approximate the true object.

Related Work

(2024-06-07)

Consolidation
- A practical point cloud includes multiple scans to capture the complete geometry for a nontrivial object.
- Triangulation techniques.
  - Shortcomings
- Weighted averaging of multiple scans based on implicit function
- Weighted averaging points directly
  - Trianglulation
    - Doubt: Perhaps I should compare my Exp: PC01 with this kind of methods.
- Surface fitting using polynomial
- Resampling
  - Using physically-based particle systems to sample an implicit surface
  - Repulsive forces
- MLS + Projection + Iterations
- Extending k neighbors to a “fan”
Point Sample Rendering
- Converting geometric models into point-sampled data sets.
- Using a hierarchy of spheres of different radii to model a high-resolution model
  - time-critical rendering
- Principal curvatures
- Global illumination effects -> ray tracing technique
- Resampling the surface in object space during rendering to adapt the display resolution.
- Hybrid triangle-point approaches
  - QSplat

Method

A surface is defined by a projection procedure: through which the surface is obtained by projecting the input points.

Basic assumption: The input point set represent a surface implicitly.
Main idea:
- $r$ is a raw point deviating from the actural surface due to noise
- $p_i$ is a sampled point on the ground-truth surface.
- $S_p$ is the approximated surface estimated from $p_i$
- Find a local plane for $r$, which serves as a x-y plane for a 3D coordinate system. The local plane is a linear regression for r’s neighboring points.
  
  Then, find surface with referencing the local plane.

Projection

Two steps of the Projection Procedure:

Step Ⅰ: For an raw input point 𝐫, compute a local plane H:
$$ H =\\{𝐱 | ⟨𝐧,𝐱⟩-D = 0, 𝐱∈ ℝ³\\}, 𝐧∈ ℝ³,‖𝐧‖=1 $$
The plane H is determined by minimizing a Weighted Sum of Squared Distances from each neighboring point 𝐩ᵢ of the point 𝐫 to the approximate plane H, and solved by weighted least squares.

The weight is a function θ of the distance between the projection 𝐪 of 𝐫 on the plane to each of its neighboring point 𝐩ᵢ.
$$ ∑ᵢ₌₁ᴺ \underset{Error}{(⟨𝐧,𝐩ᵢ⟩-D)²} ⋅ \underset{Weights}{θ(‖𝐩ᵢ-𝐪‖)} $$
- Using distances between $pᵢ$ and $q$ aims to optimize the position of the plane H based on the grount-truth point set $pᵢ$.
- θ is a smooth, monotone decreasing function, positive on the whole space
- $N$ is the number of neighbors of 𝐫.
- A plane in 3D is defined with its normal vector 𝐧 and a point 𝐱 within the plane, that deviates from the origin by a distance D along the direction of normal: $⟨𝐧,𝐱⟩=D$
- The distance from 𝐩ᵢ to the plane is the inner product of 𝐧 and 𝐩ᵢ: $⟨𝐧, 𝐩ᵢ⟩$.
Further, represent the projection 𝐪 with a parameter t:
$$𝐪 = 𝐫 + t𝐧$$
The loss function: encouraging neighboring points 𝐩ᵢ close to the H, becomes:
$$ \begin{aligned} & ∑ᵢ₌₁ᴺ (⟨𝐧, 𝐩ᵢ⟩-D)² ⋅ θ(‖𝐩ᵢ- 𝐫 - t𝐧‖) \\\ &= ∑ᵢ₌₁ᴺ (⟨𝐧, 𝐩ᵢ⟩-⟨𝐧,𝐪⟩)² ⋅ θ(‖𝐩ᵢ- 𝐫 - t𝐧‖) \\\ &= ∑ᵢ₌₁ᴺ (⟨𝐧, 𝐩ᵢ-𝐪⟩)² ⋅ θ(‖𝐩ᵢ- 𝐫 - t𝐧‖) \\\ &= ∑ᵢ₌₁ᴺ ⟨𝐧, 𝐩ᵢ - 𝐫 - t𝐧⟩^2 ⋅ θ(\\| 𝐩ᵢ - 𝐫 - t𝐧 \\|) \end{aligned} $$

Denote the target plane H with the set of projections based on raw input points r:
$$Q(t) = 𝐪 = 𝐫 + t𝐧$$
- The t reminds me the sampling in NeRF: $𝐨 + t𝐝$. After rescaling the range of [near,far] to [-1,1], the t ranges from [0,1] to sample points starting from the near plane.
  
  The t is not the depth z, but the steps that are compatible for both LLFF scene (infinite boundary) and Blender scene (bounded).
- Similarly, Point-MVSNet used steps to refine the depth of the point along a ray.
The plane H will serve as a “ground” for measuring the height of each 𝐩ᵢ, using the coordinates (x,y) on the plane H for indexing.

Step Ⅱ: Approximate surface based on the local plane H:

The projection 𝓟 of 𝐫 onto the target surface $S_P$ is a sum of the projection of 𝐫 on the plane H and the “residual” approximed with a bivariate polynomial: g(x,y),
$$ \begin{aligned} \cal{P}(𝐫) &= 𝐪 + g(0,0)𝐧 \\\ &= 𝐫 + (t+g(0,0))𝐧 \end{aligned} $$
- Similarly, PointFlow in Point-MVSNet also predicts the depth residual to tweak a point.
- A surface equation is bivariate because it only has two dimensions: x and y.
The $g(x,y)$ gets optimized by minimizing the weighted sum of neigboring pionts 𝐩ᵢ height error:
$$∑ᵢ₌₁ᴺ (g(xᵢ,yᵢ) - fᵢ)² ⋅ θ(\\| 𝐩ᵢ - 𝐪 \\|)$$
- $fᵢ$ is the height of the point 𝐩ᵢ w.r.t. the plane H:
  $$fᵢ= 𝐧⋅(𝐩ᵢ - 𝐪)$$
- The projection 𝐪 of 𝐫 is the origin of the plane-H coordinate system.
  
  The projection of 𝐫 on the original surface can be represented as: $𝐪+g(0,0)⋅𝐧$

Properties

Properties of the Projection Procedure

(2024-06-09)

The equation holds, when the plane H is the original surface $S_P$:
$$\cal{P}(\cal{P}(𝐫)) = \cal{P}(𝐫)$$

Compute Projection

Computing the Projection

Tradeoff

Data Structures and Tradeoffs

Results

Resampling

Upsampling based on Voronoi diagram

https://i.ibb.co/2jd5S0V/Paper-computing-and-rendering-point-set-surface-7-Figure8-1.png

Active Recall

LLM Chat

Problems:

I want to find a teacher to correct my understanding

References:

ChatGPT

Notes:

(2025-04-06)

Chat with free ChatGPT
- Supports:
  1. Claude.ai has length limit - Cannot upload paper (neither pdf/html/md).
  2. Yuanbao.tencent.com has a bad image understanding of my “hand-draw” (whiteboard) image
  3. DeepSeek.com does not support image

Optimization in Common