import numpy as np
import scipy as sp
import scipy.optimize as spopt
import piqp
from typing import *
__all__ = [
'calc_quad_candidates',
'calc_quad_distortion',
'calc_quad_direction',
'calc_quad_smoothness',
'sovle_quad',
'sovle_quad_qp',
'tri_to_quad'
]
def calc_quad_candidates(
edges: np.ndarray,
face2edge: np.ndarray,
edge2face: np.ndarray,
):
"""
Calculate the candidate quad faces.
Args:
edges (np.ndarray): [E, 2] edge indices
face2edge (np.ndarray): [T, 3] face to edge relation
edge2face (np.ndarray): [E, 2] edge to face relation
Returns:
quads (np.ndarray): [Q, 4] quad candidate indices
quad2edge (np.ndarray): [Q, 4] edge to quad candidate relation
quad2adj (np.ndarray): [Q, 8] adjacent quad candidates of each quad candidate
quads_valid (np.ndarray): [E] whether the quad corresponding to the edge is valid
"""
E = edges.shape[0]
T = face2edge.shape[0]
quads_valid = edge2face[:, 1] != -1
Q = quads_valid.sum()
quad2face = edge2face[quads_valid] # [Q, 2]
quad2edge = face2edge[quad2face] # [Q, 2, 3]
flag = quad2edge == np.arange(E)[quads_valid][:, None, None] # [Q, 2, 3]
flag = flag.argmax(axis=-1) # [Q, 2]
quad2edge = np.stack([
quad2edge[np.arange(Q)[:, None], np.arange(2)[None, :], (flag + 1) % 3],
quad2edge[np.arange(Q)[:, None], np.arange(2)[None, :], (flag + 2) % 3],
], axis=-1).reshape(Q, 4) # [Q, 4]
quads = np.concatenate([
np.where(
(edges[quad2edge[:, 0:1], 1:] == edges[quad2edge[:, 1:2], :]).any(axis=-1),
edges[quad2edge[:, 0:1], [[0, 1]]],
edges[quad2edge[:, 0:1], [[1, 0]]],
),
np.where(
(edges[quad2edge[:, 2:3], 1:] == edges[quad2edge[:, 3:4], :]).any(axis=-1),
edges[quad2edge[:, 2:3], [[0, 1]]],
edges[quad2edge[:, 2:3], [[1, 0]]],
),
], axis=1) # [Q, 4]
quad2adj = edge2face[quad2edge] # [Q, 4, 2]
quad2adj = quad2adj[quad2adj != quad2face[:, [0,0,1,1], None]].reshape(Q, 4) # [Q, 4]
quad2adj_valid = quad2adj != -1
quad2adj = face2edge[quad2adj] # [Q, 4, 3]
quad2adj[~quad2adj_valid, 0] = quad2edge[~quad2adj_valid]
quad2adj[~quad2adj_valid, 1:] = -1
quad2adj = quad2adj[quad2adj != quad2edge[..., None]].reshape(Q, 8) # [Q, 8]
edge_valid = -np.ones(E, dtype=np.int32)
edge_valid[quads_valid] = np.arange(Q)
quad2adj_valid = quad2adj != -1
quad2adj[quad2adj_valid] = edge_valid[quad2adj[quad2adj_valid]] # [Q, 8]
return quads, quad2edge, quad2adj, quads_valid
def calc_quad_distortion(
vertices: np.ndarray,
quads: np.ndarray,
):
"""
Calculate the distortion of each candidate quad face.
Args:
vertices (np.ndarray): [N, 3] 3-dimensional vertices
quads (np.ndarray): [Q, 4] quad face indices
Returns:
distortion (np.ndarray): [Q] distortion of each quad face
"""
edge0 = vertices[quads[:, 1]] - vertices[quads[:, 0]] # [Q, 3]
edge1 = vertices[quads[:, 2]] - vertices[quads[:, 1]] # [Q, 3]
edge2 = vertices[quads[:, 3]] - vertices[quads[:, 2]] # [Q, 3]
edge3 = vertices[quads[:, 0]] - vertices[quads[:, 3]] # [Q, 3]
cross = vertices[quads[:, 0]] - vertices[quads[:, 2]] # [Q, 3]
len0 = np.maximum(np.linalg.norm(edge0, axis=-1), 1e-10) # [Q]
len1 = np.maximum(np.linalg.norm(edge1, axis=-1), 1e-10) # [Q]
len2 = np.maximum(np.linalg.norm(edge2, axis=-1), 1e-10) # [Q]
len3 = np.maximum(np.linalg.norm(edge3, axis=-1), 1e-10) # [Q]
len_cross = np.maximum(np.linalg.norm(cross, axis=-1), 1e-10) # [Q]
angle0 = np.arccos(np.clip(np.sum(-edge0 * edge1, axis=-1) / (len0 * len1), -1, 1)) # [Q]
angle1 = np.arccos(np.clip(np.sum(-edge1 * cross, axis=-1) / (len1 * len_cross), -1, 1)) \
+ np.arccos(np.clip(np.sum(cross * edge2, axis=-1) / (len_cross * len2), -1, 1)) # [Q]
angle2 = np.arccos(np.clip(np.sum(-edge2 * edge3, axis=-1) / (len2 * len3), -1, 1)) # [Q]
angle3 = np.arccos(np.clip(np.sum(-edge3 * -cross, axis=-1) / (len3 * len_cross), -1, 1)) \
+ np.arccos(np.clip(np.sum(-cross * edge0, axis=-1) / (len_cross * len0), -1, 1)) # [Q]
normal0 = np.cross(edge0, edge1) # [Q, 3]
normal1 = np.cross(edge2, edge3) # [Q, 3]
normal0 = normal0 / np.maximum(np.linalg.norm(normal0, axis=-1, keepdims=True), 1e-10) # [Q, 3]
normal1 = normal1 / np.maximum(np.linalg.norm(normal1, axis=-1, keepdims=True), 1e-10) # [Q, 3]
angle_normal = np.arccos(np.clip(np.sum(normal0 * normal1, axis=-1), -1, 1)) # [Q]
D90 = np.pi / 2
D180 = np.pi
D360 = np.pi * 2
ang_eng = (np.abs(angle0 - D90)**2 + np.abs(angle1 - D90)**2 + np.abs(angle2 - D90)**2 + np.abs(angle3 - D90)**2) / 4 # [Q]
dist_eng = np.abs(angle0 - angle2)**2 / np.minimum(np.maximum(np.minimum(angle0, angle2), 1e-10), np.maximum(D180 - np.maximum(angle0, angle2), 1e-10)) \
+ np.abs(angle1 - angle3)**2 / np.minimum(np.maximum(np.minimum(angle1, angle3), 1e-10), np.maximum(D180 - np.maximum(angle1, angle3), 1e-10)) # [Q]
plane_eng = np.where(angle_normal < D90/2, np.abs(angle_normal)**2, 1e10) # [Q]
eng = ang_eng + 2 * dist_eng + 2 * plane_eng # [Q]
return eng
def calc_quad_direction(
vertices: np.ndarray,
quads: np.ndarray,
):
"""
Calculate the direction of each candidate quad face.
Args:
vertices (np.ndarray): [N, 3] 3-dimensional vertices
quads (np.ndarray): [Q, 4] quad face indices
Returns:
direction (np.ndarray): [Q, 4] direction of each quad face.
Represented by the angle between the crossing and each edge.
"""
mid0 = (vertices[quads[:, 0]] + vertices[quads[:, 1]]) / 2 # [Q, 3]
mid1 = (vertices[quads[:, 1]] + vertices[quads[:, 2]]) / 2 # [Q, 3]
mid2 = (vertices[quads[:, 2]] + vertices[quads[:, 3]]) / 2 # [Q, 3]
mid3 = (vertices[quads[:, 3]] + vertices[quads[:, 0]]) / 2 # [Q, 3]
cross0 = mid2 - mid0 # [Q, 3]
cross1 = mid3 - mid1 # [Q, 3]
cross0 = cross0 / np.maximum(np.linalg.norm(cross0, axis=-1, keepdims=True), 1e-10) # [Q, 3]
cross1 = cross1 / np.maximum(np.linalg.norm(cross1, axis=-1, keepdims=True), 1e-10) # [Q, 3]
edge0 = vertices[quads[:, 1]] - vertices[quads[:, 0]] # [Q, 3]
edge1 = vertices[quads[:, 2]] - vertices[quads[:, 1]] # [Q, 3]
edge2 = vertices[quads[:, 3]] - vertices[quads[:, 2]] # [Q, 3]
edge3 = vertices[quads[:, 0]] - vertices[quads[:, 3]] # [Q, 3]
edge0 = edge0 / np.maximum(np.linalg.norm(edge0, axis=-1, keepdims=True), 1e-10) # [Q, 3]
edge1 = edge1 / np.maximum(np.linalg.norm(edge1, axis=-1, keepdims=True), 1e-10) # [Q, 3]
edge2 = edge2 / np.maximum(np.linalg.norm(edge2, axis=-1, keepdims=True), 1e-10) # [Q, 3]
edge3 = edge3 / np.maximum(np.linalg.norm(edge3, axis=-1, keepdims=True), 1e-10) # [Q, 3]
direction = np.stack([
np.arccos(np.clip(np.sum(cross0 * edge0, axis=-1), -1, 1)),
np.arccos(np.clip(np.sum(cross1 * edge1, axis=-1), -1, 1)),
np.arccos(np.clip(np.sum(-cross0 * edge2, axis=-1), -1, 1)),
np.arccos(np.clip(np.sum(-cross1 * edge3, axis=-1), -1, 1)),
], axis=-1) # [Q, 4]
return direction
def calc_quad_smoothness(
quad2edge: np.ndarray,
quad2adj: np.ndarray,
quads_direction: np.ndarray,
):
"""
Calculate the smoothness of each candidate quad face connection.
Args:
quad2adj (np.ndarray): [Q, 8] adjacent quad faces of each quad face
quads_direction (np.ndarray): [Q, 4] direction of each quad face
Returns:
smoothness (np.ndarray): [Q, 8] smoothness of each quad face connection
"""
Q = quad2adj.shape[0]
quad2adj_valid = quad2adj != -1
connections = np.stack([
np.arange(Q)[:, None].repeat(8, axis=1),
quad2adj,
], axis=-1)[quad2adj_valid] # [C, 2]
shared_edge_idx_0 = np.array([[0, 0, 1, 1, 2, 2, 3, 3]]).repeat(Q, axis=0)[quad2adj_valid] # [C]
shared_edge_idx_1 = np.argmax(quad2edge[quad2adj][quad2adj_valid] == quad2edge[connections[:, 0], shared_edge_idx_0][:, None], axis=-1) # [C]
valid_smoothness = np.abs(quads_direction[connections[:, 0], shared_edge_idx_0] - quads_direction[connections[:, 1], shared_edge_idx_1])**2 # [C]
smoothness = np.zeros([Q, 8], dtype=np.float32)
smoothness[quad2adj_valid] = valid_smoothness
return smoothness
def sovle_quad(
face2edge: np.ndarray,
edge2face: np.ndarray,
quad2adj: np.ndarray,
quads_distortion: np.ndarray,
quads_smoothness: np.ndarray,
quads_valid: np.ndarray,
):
"""
Solve the quad mesh from the candidate quad faces.
Args:
face2edge (np.ndarray): [T, 3] face to edge relation
edge2face (np.ndarray): [E, 2] edge to face relation
quad2adj (np.ndarray): [Q, 8] adjacent quad faces of each quad face
quads_distortion (np.ndarray): [Q] distortion of each quad face
quads_smoothness (np.ndarray): [Q, 8] smoothness of each quad face connection
quads_valid (np.ndarray): [E] whether the quad corresponding to the edge is valid
Returns:
weights (np.ndarray): [Q] weight of each valid quad face
"""
T = face2edge.shape[0]
E = edge2face.shape[0]
Q = quads_distortion.shape[0]
edge_valid = -np.ones(E, dtype=np.int32)
edge_valid[quads_valid] = np.arange(Q)
quads_connection = np.stack([
np.arange(Q)[:, None].repeat(8, axis=1),
quad2adj,
], axis=-1)[quad2adj != -1] # [C, 2]
quads_connection = np.sort(quads_connection, axis=-1) # [C, 2]
quads_connection, quads_connection_idx = np.unique(quads_connection, axis=0, return_index=True) # [C, 2], [C]
quads_smoothness = quads_smoothness[quad2adj != -1] # [C]
quads_smoothness = quads_smoothness[quads_connection_idx] # [C]
C = quads_connection.shape[0]
# Construct the linear programming problem
# Variables:
# quads_weight: [Q] weight of each quad face
# tri_min_weight: [T] minimum weight of each triangle face
# conn_min_weight: [C] minimum weight of each quad face connection
# conn_max_weight: [C] maximum weight of each quad face connection
# Objective:
# mimi
c = np.concatenate([
quads_distortion - 3,
quads_smoothness*4 - 2,
quads_smoothness*4,
], axis=0) # [Q+C]
A_ub_triplet = np.concatenate([
np.stack([np.arange(T), edge_valid[face2edge[:, 0]], np.ones(T)], axis=1), # [T, 3]
np.stack([np.arange(T), edge_valid[face2edge[:, 1]], np.ones(T)], axis=1), # [T, 3]
np.stack([np.arange(T), edge_valid[face2edge[:, 2]], np.ones(T)], axis=1), # [T, 3]
np.stack([np.arange(T, T+C), np.arange(Q, Q+C), np.ones(C)], axis=1), # [C, 3]
np.stack([np.arange(T, T+C), quads_connection[:, 0], -np.ones(C)], axis=1), # [C, 3]
np.stack([np.arange(T, T+C), quads_connection[:, 1], -np.ones(C)], axis=1), # [C, 3]
np.stack([np.arange(T+C, T+2*C), np.arange(Q+C, Q+2*C), -np.ones(C)], axis=1), # [C, 3]
np.stack([np.arange(T+C, T+2*C), quads_connection[:, 0], np.ones(C)], axis=1), # [C, 3]
np.stack([np.arange(T+C, T+2*C), quads_connection[:, 1], np.ones(C)], axis=1), # [C, 3]
], axis=0) # [3T+6C, 3]
A_ub_triplet = A_ub_triplet[A_ub_triplet[:, 1] != -1] # [3T', 3]
A_ub = sp.sparse.coo_matrix((A_ub_triplet[:, 2], (A_ub_triplet[:, 0], A_ub_triplet[:, 1])), shape=[T+2*C, Q+2*C]) # [T,
b_ub = np.concatenate([np.ones(T), -np.ones(C), np.ones(C)], axis=0) # [T+2C]
bound = np.stack([
np.concatenate([np.zeros(Q), -np.ones(C), np.zeros(C)], axis=0),
np.concatenate([np.ones(Q), np.ones(C), np.ones(C)], axis=0),
], axis=1) # [Q+2C, 2]
A_eq = None
b_eq = None
print('Solver statistics:')
print(f' #T = {T}')
print(f' #Q = {Q}')
print(f' #C = {C}')
# Solve the linear programming problem
last_num_valid = 0
for i in range(100):
res_ = spopt.linprog(c, A_ub=A_ub, b_ub=b_ub, A_eq=A_eq, b_eq=b_eq, bounds=bound)
if not res_.success:
print(f' Iter {i} | Failed with {res_.message}')
break
res = res_
weights = res.x[:Q]
valid = (weights > 0.5)
num_valid = valid.sum()
print(f' Iter {i} | #Q_valid = {num_valid}')
if num_valid == last_num_valid:
break
last_num_valid = num_valid
A_eq_triplet = np.stack([
np.arange(num_valid),
np.arange(Q)[valid],
np.ones(num_valid),
], axis=1) # [num_valid, 3]
A_eq = sp.sparse.coo_matrix((A_eq_triplet[:, 2], (A_eq_triplet[:, 0], A_eq_triplet[:, 1])), shape=[num_valid, Q+2*C]) # [num_valid, Q+C]
b_eq = np.where(weights[valid] > 0.5, 1, 0) # [num_valid]
# Return the result
quads_weight = res.x[:Q]
conn_min_weight = res.x[Q:Q+C]
conn_max_weight = res.x[Q+C:Q+2*C]
return quads_weight, conn_min_weight, conn_max_weight
def sovle_quad_qp(
face2edge: np.ndarray,
edge2face: np.ndarray,
quad2adj: np.ndarray,
quads_distortion: np.ndarray,
quads_smoothness: np.ndarray,
quads_valid: np.ndarray,
):
"""
Solve the quad mesh from the candidate quad faces.
Args:
face2edge (np.ndarray): [T, 3] face to edge relation
edge2face (np.ndarray): [E, 2] edge to face relation
quad2adj (np.ndarray): [Q, 8] adjacent quad faces of each quad face
quads_distortion (np.ndarray): [Q] distortion of each quad face
quads_smoothness (np.ndarray): [Q, 8] smoothness of each quad face connection
quads_valid (np.ndarray): [E] whether the quad corresponding to the edge is valid
Returns:
weights (np.ndarray): [Q] weight of each valid quad face
"""
T = face2edge.shape[0]
E = edge2face.shape[0]
Q = quads_distortion.shape[0]
edge_valid = -np.ones(E, dtype=np.int32)
edge_valid[quads_valid] = np.arange(Q)
# Construct the quadratic programming problem
C_smoothness_triplet = np.stack([
np.arange(Q)[:, None].repeat(8, axis=1)[quad2adj != -1],
quad2adj[quad2adj != -1],
5 * quads_smoothness[quad2adj != -1],
], axis=-1) # [C, 3]
# C_smoothness_triplet = np.concatenate([
# C_smoothness_triplet,
# np.stack([np.arange(Q), np.arange(Q), 20*np.ones(Q)], axis=1),
# ], axis=0) # [C+Q, 3]
C_smoothness = sp.sparse.coo_matrix((C_smoothness_triplet[:, 2], (C_smoothness_triplet[:, 0], C_smoothness_triplet[:, 1])), shape=[Q, Q]) # [Q, Q]
C_smoothness = C_smoothness.tocsc()
C_dist = quads_distortion - 20 # [Q]
A_eq = sp.sparse.coo_matrix((np.zeros(Q), (np.zeros(Q), np.arange(Q))), shape=[1, Q]) # [1, Q]\
A_eq = A_eq.tocsc()
b_eq = np.array([0])
A_ub_triplet = np.concatenate([
np.stack([np.arange(T), edge_valid[face2edge[:, 0]], np.ones(T)], axis=1), # [T, 3]
np.stack([np.arange(T), edge_valid[face2edge[:, 1]], np.ones(T)], axis=1), # [T, 3]
np.stack([np.arange(T), edge_valid[face2edge[:, 2]], np.ones(T)], axis=1), # [T, 3]
], axis=0) # [3T, 3]
A_ub_triplet = A_ub_triplet[A_ub_triplet[:, 1] != -1] # [3T', 3]
A_ub = sp.sparse.coo_matrix((A_ub_triplet[:, 2], (A_ub_triplet[:, 0], A_ub_triplet[:, 1])), shape=[T, Q]) # [T, Q]
A_ub = A_ub.tocsc()
b_ub = np.ones(T)
lb = np.zeros(Q)
ub = np.ones(Q)
solver = piqp.SparseSolver()
solver.settings.verbose = True
solver.settings.compute_timings = True
solver.setup(C_smoothness, C_dist, A_eq, b_eq, A_ub, b_ub, lb, ub)
status = solver.solve()
# x = cp.Variable(Q)
# prob = cp.Problem(
# cp.Minimize(cp.quad_form(x, C_smoothness) + C_dist.T @ x),
# [
# A_ub @ x <= b_ub,
# x >= 0, x <= 1,
# ]
# )
# # Solve the quadratic programming problem
# prob.solve(solver=cp.PIQP, verbose=True)
# Return the result
weights = solver.result.x
return weights
def tri_to_quad(
vertices: np.ndarray,
faces: np.ndarray,
) -> Tuple[np.ndarray, np.ndarray]:
"""
Convert a triangle mesh to a quad mesh.
NOTE: The input mesh must be a manifold mesh.
Args:
vertices (np.ndarray): [N, 3] 3-dimensional vertices
faces (np.ndarray): [T, 3] triangular face indices
Returns:
vertices (np.ndarray): [N_, 3] 3-dimensional vertices
faces (np.ndarray): [Q, 4] quad face indices
"""
raise NotImplementedError
if __name__ == '__main__':
import os
import sys
sys.path.insert(0, os.path.abspath(os.path.join(os.path.dirname(__file__), '..', '..', '..')))
import utils3d
import numpy as np
import cv2
from vis import vis_edge_color
file = 'miku'
vertices, faces = utils3d.io.read_ply(f'test/assets/{file}.ply')
edges, edge2face, face2edge, face2face = calc_relations(faces)
quad_cands, quad2edge, quad2adj, quad_valid = calc_quad_candidates(edges, face2edge, edge2face)
distortion = calc_quad_distortion(vertices, quad_cands)
direction = calc_quad_direction(vertices, quad_cands)
smoothness = calc_quad_smoothness(quad2edge, quad2adj, direction)
boundary_edges = edges[edge2face[:, 1] == -1]
quads_weight, conn_min_weight, conn_max_weight = sovle_quad(face2edge, edge2face, quad2adj, distortion, smoothness, quad_valid)
quads = quad_cands[quads_weight > 0.5]
print('Mesh statistics')
print(f' #V = {vertices.shape[0]}')
print(f' #F = {faces.shape[0]}')
print(f' #E = {edges.shape[0]}')
print(f' #B = {boundary_edges.shape[0]}')
print(f' #Q_cand = {quad_cands.shape[0]}')
print(f' #Q = {quads.shape[0]}')
utils3d.io.write_ply(f'test/assets/{file}_boundary_edges.ply', vertices=vertices, edges=boundary_edges)
utils3d.io.write_ply(f'test/assets/{file}_quad_candidates.ply', vertices=vertices, faces=quads)
edge_colors = np.zeros([edges.shape[0], 3], dtype=np.uint8)
distortion = (distortion - distortion.min()) / (distortion.max() - distortion.min())
distortion = (distortion * 255).astype(np.uint8)
edge_colors[quad_valid] = cv2.cvtColor(cv2.applyColorMap(distortion, cv2.COLORMAP_JET), cv2.COLOR_BGR2RGB).reshape(-1, 3)
utils3d.io.write_ply(f'test/assets/{file}_quad_candidates_distortion.ply', **vis_edge_color(vertices, edges, edge_colors))
edge_colors = np.zeros([edges.shape[0], 3], dtype=np.uint8)
edge_colors[quad_valid] = cv2.cvtColor(cv2.applyColorMap((quads_weight * 255).astype(np.uint8), cv2.COLORMAP_JET), cv2.COLOR_BGR2RGB).reshape(-1, 3)
utils3d.io.write_ply(f'test/assets/{file}_quad_candidates_weights.ply', **vis_edge_color(vertices, edges, edge_colors))
utils3d.io.write_ply(f'test/assets/{file}_quad.ply', vertices=vertices, faces=quads)
quad_centers = vertices[quad_cands].mean(axis=1)
conns = np.stack([
np.arange(quad_cands.shape[0])[:, None].repeat(8, axis=1),
quad2adj,
], axis=-1)[quad2adj != -1] # [C, 2]
conns, conns_idx = np.unique(np.sort(conns, axis=-1), axis=0, return_index=True) # [C, 2], [C]
smoothness = smoothness[quad2adj != -1][conns_idx] # [C]
conns_color = cv2.cvtColor(cv2.applyColorMap((smoothness * 255).astype(np.uint8), cv2.COLORMAP_JET), cv2.COLOR_BGR2RGB).reshape(-1, 3)
utils3d.io.write_ply(f'test/assets/{file}_quad_conn_smoothness.ply', **vis_edge_color(quad_centers, conns, conns_color))
conns_color = cv2.cvtColor(cv2.applyColorMap((conn_min_weight * 255).astype(np.uint8), cv2.COLORMAP_JET), cv2.COLOR_BGR2RGB).reshape(-1, 3)
utils3d.io.write_ply(f'test/assets/{file}_quad_conn_min.ply', **vis_edge_color(quad_centers, conns, conns_color))
conns_color = cv2.cvtColor(cv2.applyColorMap((conn_max_weight * 255).astype(np.uint8), cv2.COLORMAP_JET), cv2.COLOR_BGR2RGB).reshape(-1, 3)
utils3d.io.write_ply(f'test/assets/{file}_quad_conn_max.ply', **vis_edge_color(quad_centers, conns, conns_color))