Code to tessellate a general quadric

| | August 11, 2015

Does anyone know of a C/C++ library (or has some source code) that can generate and output (by which I don’t mean render) a tessellation of a general quadric, i.e. a 3d surface defined by the matrix equation

X’AX + B’X + c = 0

where X is a 3d point, A is a symmetric 3×3 matrix, B is a 3×1 vector and c is a scalar?

2 Responses to “Code to tessellate a general quadric”

  1. Steven Stadnicki on November 30, -0001 @ 12:00 AM

    I don’t think there’s a quick, easy answer to this, although I wouldn’t be shocked to find one somewhere in an old ’80s SIGGRAPH article – that’s where I’d suggest looking first, FWIW. The approach I would probably take to this:

    1. Identify what kind of quadric you have; the best way to do this should be to diagonalizing your matrix A and find its eigenvalues.
    2. Translate it to the ‘canonical’ version of that quadric – that is, eliminate all of the (eliminable) linear terms by setting e.g. x’ = x-(B_x)/2.
    3. Use a standard parametrization of your quadric to create a generic tessellation; for instance, for the sphere this would be something like (cos u sin v, sin u sin v, cos v); for a one-sheeted hyperboloid it might be (cos u cosh v, sin u cosh v, sinh v); etc. Note that for an even better tessellation you’ll want to use the eigenvalues you found in step 1 to control the relative spacing of your u/v coordinates here, to leave a more uniform final result after the squash/stretch of the first stage.
    4. Translate this tessellation back by the inverse of the translation and diagonalizing transforms you had to use to get it into standard form.

    In general this will work reasonably well; it’s very possible that there will be corner cases for which it’s pretty terrible, and if you care deeply about those then you’ll really want to dig into the literature to make sure you do this right, but for 95% of what you’ll likely need, this should do the trick.

  2. I found a relatively simple solution, though the tessellation isn’t very pretty or efficient:
    The quadric defines a scalar value in 3-dimensional space, with the surface lying on the the 0 iso-contour. I therefore create a scalar volume using the quadric equation, and use the marching cubes algorithm to give me a tessellation of the 0 iso-contour.

Leave a Reply