We propose a new algorithm to compute the topology of a real algebraic space curve . The novelties of this algorithm are a new technique to achieve the lifting step which recovers points of the space curve in each plane fiber from several projections and a weaker notion of generic position. As distinct to previous work, our sweep generic position does not require that x -critical points have different x -coordinates. The complexity of achieving this sweep generic position property is thus no longer a bottleneck in term of complexity. The bit complexity of our algorithm is O ˜ ( d 18 + d 17 τ ) where d and τ bound the degree and the bitsize of the integer coefficients, respectively, of the defining polynomials of the curve and polylogarithmic factors are ignored. To the best of our knowledge, this improves upon the best currently known results at least by a factor of d 2 .

Computing the intersection between two parametric surfaces (SSI) is one of the most fundamental problems in geometric and solid modeling. Maintaining the SSI topology is critical to its computation robustness. We propose a topology-driven hybrid symbolic-numeric framework to approximate rational parametric surface-surface intersection (SSI) based on a concept of interval algebraic topology analysis (IATA) , which configures within a 4D interval box the SSI topology. We map the SSI topology to an algebraic system's solutions within the framework, classify and enumerate all topological cases as a mixture of four fundamental cases (or their specific sub-cases). Various complicated topological situations are covered, such as cusp points or curves, tangent points (isolated or not) or curves, tiny loops, self-intersections, or their mixtures. The theoretical formulation is also implemented numerically using advanced real solution isolation techniques, and computed within a topology-driven framework which maximally utilizes the advantages of the topology maintenance of algebraic analysis, the robustness of iterative subdivision, and the efficiency of forward marching. The approach demonstrates improved robustness under benchmark topological cases when compared with available open-source and commercial solutions, including IRIT, SISL, and Parasolid.

We propose a novel normal estimation method called HSurf-Net, which can accurately predict normals from point clouds with noise and density variations. Previous methods focus on learning point weights to fit neighborhoods into a geometric surface approximated by a polynomial function with a predefined order, based on which normals are estimated. However, fitting surfaces explicitly from raw point clouds suffers from overfitting or underfitting issues caused by inappropriate polynomial orders and outliers, which significantly limits the performance of existing methods. To address these issues, we introduce hyper surface fitting to implicitly learn hyper surfaces, which are represented by multi-layer perceptron (MLP) layers that take point features as input and output surface patterns in a high dimensional feature space. We introduce a novel space transformation module, which consists of a sequence of local aggregation layers and global shift layers, to learn an optimal feature space, and a relative position encoding module to effectively convert point clouds into the learned feature space. Our model learns hyper surfaces from the noise-less features and directly predicts normal vectors. We jointly optimize the MLP weights and module parameters in a data-driven manner to make the model adaptively find the most suitable surface pattern for various points. Experimental results show that our HSurf-Net achieves the state-of-the-art performance on the synthetic shape dataset, the real-world indoor and outdoor scene datasets. The code, data and pretrained models are publicly available.

In this paper, we present a new method for isolating real roots of a bivariate polynomial system. Our method is a subdivision method which is based on real root isolation of univariate polynomials and analyzing the local geometrical properties of the given system. We propose the concept of the orthogonal monotone system in a box and use it to determine the uniqueness and the existence of a simple real zero of the system in the box. We implement our method to isolate the real zeros of a given bivariate polynomial system. The experiments show the effectivity and efficiency of our method, especially for systems with high degrees and sparse terms. Our method also works for non-polynomial systems.

We revisit the problem of computing the topology and geometry of a real algebraic plane curve. The topology is of prime interest but geometric information, such as the position of singular and critical points, is also relevant. A challenge is to compute efficiently this information for the given coordinate system even if the curve is not in generic position.

A local generic position method is proposed to isolate the real roots of a bivariate polynomial system ∑={f(x,y),g(x,y)}. In this method, the roots of the system are represented as linear combinations of the roots of two univariate polynomial equations t(x)=0 and T(X)=0: {x = α, y = β -- α/s | α ε V(t(x)), β ε V(T(X)), ||β -- α| < S}, where s, S are constants satisfying certain conditions. The multiplicities of the roots of Σ=0 are the same as that of the corresponding roots of T(X)=0. This representation leads to an efficient and stable algorithm to isolate the real roots of Σ.

We present a complete numerical algorithm of isolating all the real zeros of a zero-dimensional triangular polynomial system Fn Z[x1…,xn]. Our system Fn is general, with no further assumptions. In particular, our algorithm successfully treat multiple zeros directly in such systems. A key idea is to introduce evaluation bounds and sleeve bounds. We implemented our algorithm and promising experimental results are shown.