Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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 3x3 matrix, B is a 3x1 vector and c is a scalar?

share|improve this question
2  
A couple of questions that would be worth asking: what sort of uniformity or approximation properties do you want on your tesselation, and in particular do you want to specify a number of polys or a closeness-of-approximation? For the unbounded quadrics, do you want them clamped to a box, a sphere, or something else entirely? –  Steven Stadnicki Sep 26 '11 at 19:33
    
Unbounded quadrics will be clamped to a box. I'd be happy with any method of tessellation, as long as the mesh coarseness can be varied with an input parameter. –  user664303 Sep 27 '11 at 7:45
add comment

2 Answers 2

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.

share|improve this answer
add comment
up vote 1 down vote accepted

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.

share|improve this answer
    
This was quickest for me. If I cared about mesh complexity I could always run it through a mesh simplification tool. –  user664303 Dec 1 '11 at 18:50
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.