Home
Education
Research
Publications
Projects
Presentations
TA Courses
     

Ning Song

Ph.D Student, Graphics and Geometric Design Group
Department of Computer Science, Rice University
Office: Duncan Hall 3113
Phone: #3837
Email: nsong (a) cs*rice*edu
Education
Research & Publications
u-Bases and Their Applications in Geometric Modeling
Ph.D Thesis
Ning Song

Geometric modeling is the sub-field of computer science concerned with constructing, manipulating, and analyzing geometric models - computer models of physical, virtual or mathematical objects. In practice, many geometric models are represented by smooth algebraic functions, especially rational functions. For rational curves and surfaces, there are several common problems that are frequently encountered: computing intersections, finding implicit equations, and detecting singular points and base points. Generally, each of these problems eventually reduce to solving systems of polynomial equations. This thesis will focus on solving these common problems by u-bases.
u-Bases for Polynomial System in One Variable
Computer Aided Geometric Design (CAGD), under review
Ning Song, Ron Goldman

The concept of u-bases originated from a series of papers by Sederberg, Cox, Chen and their collaborators. u-bases can be used to implicitize as well as to find singularities for rational planar curves. Normally we represent a rational planar curve in homogeneous form by three polynomials in one variable.

In this paper, the notion of a u-basis for an arbitrary number of polynomials in one variable is defined. The basic properties of these u-bases are derived, and an algorithm is presented based on Gaussian Elimination to calculate a u-basis for any collection of univariate polynomials. These u-bases are then applied to solve implicitization, inversion and intersection problems for rational space curves. Systems where base points are present are also discussed.
Axial Moving Lines and Singularities of Rational Planar Curves
Computer Aided Geometric Design (CAGD), Vol.5 200-209, 2007
Ning Song, Falai Chen, Ron Goldman

Singularities such as cusps and self-intersections can help to determine the geometry and topology of rational curves. Detecting and avoiding local cusps and self-intersections is often important in Geometric Modeling applications. Moreover high order singularities lead to more compact representations for the implicit equation of a rational curve.

Here we show that there is a natural 1-1 correspondence between the singular points of rational planar curves and the axial moving lines that follow these curves. This correspondence is applied to compute and to analyze all the singular points of low degree rational planar curves using u-bases.
Sylvester A-Resultants for Bivariate Polynomials with Planar Newton Polygons
Proceedings of the 2004 International Symposium on Symbolic and Algebraic Computation (ISSAC-2004), 205-212
Amit Khetan, Ning Song, Ron Goldman

Necessary and sufficient conditions are derived which guarantee that a multiplying set of monomials generates exactly the Sylvester A-resultant for bivariate polynomials with a given planar Newton polygon. Valid multiplying sets are shown to come in complementary pairs, and any two complementary pairs of multiplying sets can be used to index the rows and columns of a pure Bezoutian A-resultant for the same Newton polygon.

The necessary and sufficient conditions include a set of Diophantine equations that can be solved to generate the multiplying sets and hence too the corresponding Sylvester A-resultants. Examples relevant to Geometric Modeling are provided. These examples not only flesh out the theory, but also demonstrate that none of the conditions are superfluous and that all the conditions are mutually independent.
A Computational Method for Constructing Sylvester-style sparse resultants
Proceedings of the Tenth International Conference on Applications of Computer Algebra (ACA-2004), 81-89
Ning Song, Ron Goldman

We present a computational approach for constructing Sylvester style resultants for sparse systems of bivariate polynomial equations. Necessary and sufficient conditions are derived which guarantee that a multiplying set of monomials generates an exact Sylvester style resultant for three bivariate polynomials with a given planar Newton polygon. These conditions include a set of Diophantine equations that can be solved to generate multiplying sets of monomials and therefore the corresponding Sylvester resultants. We have implemented this method in Mathematica, and the results show that such Sylvester style sparse resultants often exist, and they appear in certain specific patterns.
Interesting Programming Projects
Isosurface renderer for volume scan data
Individual work during summer internship at National Center for Macromolecular Imaging Lab (NCMI), Baylor College of Medicine, 2005

Developed in J2SE 1.4.2

  • Pure software renderer, compliant with Java 1.0/1.2 API, no additional package required. Can run as web applet or standalone java application.

  • Rendering isosurface from volume data using marching-cube algorithm.

  • Support basic 3D rendering features - point light, smooth shading, backface removal. Double-buffer drawing implemented.

  • Reading data from both local disk and http connection, support MRC type 1 file format.
    • Mouse brain layer viewer
    Collaborate work for Baylor College of Medicine, 2004

    Developed in J2SE 1.4.2

  • Pure software renderer, compliant with Java 1.0/1.2 API, no additional package required. Can run as web applet or standalone java application.

  • Optimized rendering speed

  • Support smooth shading, backface removal
    • Mouse brain layer align tool
    Collaborate work for Baylor College of Medicine, 2004

    Developed in J2SE 1.4.2 + Java3D 1.3.1

  • Fast 3D grid render utilizing Java3D package.

  • Showing both saggital layer and coronal layer, and their intersections.

  • Support multiple alignment algorithm, showing align fitness by color
    • 2D robot roadmap planner based on PRM
    Course project, C++/OpenGL

  • Implemented probabilistic roadmap plannar(PRM) for arbitrary polygon-shape robot.

  • Support adding/removing obstacle, loading/saving scene, robot position, and planned maps.

  • Support realtime animation for demonstration of robot movement.
    		•
    Fast Fourier transform demo
    Course project, Java - J2SE 1.3.1

  • Demo of several common spectrum transformation algorithms: FFT, DFT, DCT, WHT.

  • Implemented high-pass and low-pass filter, showing spectrum and invert transformation results, with progress bar showing algorithm performance for comparison.

  • Java interface, support loading/saving results.
    • OpenGL 3D model viewer
    Course project, C++/OpenGL

  • Implemented multiple rendering algorithm such as scanline converter, Z-Buffer, BSP-Tree, etc.

  • Implemented multiple shading algorithm, flat/gouraud/phong shading.

  • Inside/outside switch, texture mapping.
    • Software renderer - raytracing
    Course project, C++

  • Multiple modeling methods, including constructive solid geometry(CSG)

  • Multiple shading/lighting algorithm, reflection, refraction, full-reflection. Support point light and spot light.

  • Programmable surfaces, special reflection effects.
    • NURBS surface builder
    Course project, C++/OpenGL

  • Constructing NURBS from control points and knots, support knot insersion/refinement.

  • Smooth shading, support two-side rendering, free camera movement.

  • Attempting to reconstruct NURBS surface from point cloud.
    		•
    B-Spline curve editor
    Course project, C++/OpenGL

  • Different evaulation algorithm, Bezier and Lagrange interpolation.

  • Implemented De Boor's algorithm, verifying numerical stability.
    		•
    Conference Presentations and Posters
  • Poster - "u-Bases and Their Applications in Geometric Modeling"
    Department poster session, 2006


  • Poster - "Axial Moving Lines and Singularities of Rational Planar Curves"
    Department poster session, 2005
    		•
    Labbie & Teach Assistant:

    Comments or suggestions: nsong (a) cs*rice*edu