Quadrics kinda sorta work for real time

Practical and theoretical implementation discussion.
graphicsMan
Posts: 160
Joined: Mon Nov 28, 2011 7:28 pm

Re: Quadrics kinda sorta work for real time

Post by graphicsMan » Fri Jul 27, 2012 5:02 pm

well... if you can figure out a "good fit" to a Loop SubD, you can subdivide the mesh until the approximating quadrics fall below some error threshold. If this results in substantially fewer end primitives than it would with triangles, it could be a win. There are many references to subdividing Loop SubDs (I think PBRT does this).

I agree with all of your arguments, but the fact remains that you need some way of getting models that are approximated by quadrics :) If you have to painstakingly model each model specially using quadrics directly, no one will ever use this, since no existing commercial-grade software is available to make models this way.

hobold
Posts: 56
Joined: Wed Dec 21, 2011 6:08 pm

Re: Quadrics kinda sorta work for real time

Post by hobold » Fri Jul 27, 2012 5:42 pm

graphicsMan wrote:well... if you can figure out a "good fit" to a Loop SubD, you can subdivide the mesh until the approximating quadrics fall below some error threshold.
This is actually a very good idea. A much more interesting potential dead end than those that I had on my list. The subdivision process ought to locally sanitize any mesh ... thank you!

I have only basic knowledge about subdivision surfaces. Is there a particular reason why you suggest Loop type?
If you have to painstakingly model each model specially using quadrics directly, no one will ever use this, since no existing commercial-grade software is available to make models this way.
No argument there.

graphicsMan
Posts: 160
Joined: Mon Nov 28, 2011 7:28 pm

Re: Quadrics kinda sorta work for real time

Post by graphicsMan » Fri Jul 27, 2012 6:31 pm

Loop works with triangles as the subdivision primitive. CC works with quads. These are both good subdivision schemes that are C^2 everywhere but extraordinary vertices (where they are G^2). They both support hard edges and points. They're both suitable depending on your incoming base mesh. This paper might be of interest:

http://www.autodeskresearch.com/pdf/qtEG.pdf

hobold
Posts: 56
Joined: Wed Dec 21, 2011 6:08 pm

Re: Quadrics kinda sorta work for real time

Post by hobold » Sun Jul 29, 2012 10:42 pm

Reading up on subdivision surfaces, I learned about box splines. A particular one of those, also known as Zwart-Powell element, can be reproduced exactly with quadrics:
Image
It is only C^1, but has some other interesting properties that remind me of wavelets. It might be possible to build smooth height fields with seamless, continuous level of detail from such basis functions.

graphicsMan
Posts: 160
Joined: Mon Nov 28, 2011 7:28 pm

Re: Quadrics kinda sorta work for real time

Post by graphicsMan » Mon Jul 30, 2012 7:05 pm

Sounds interesting. Is there software that will model using Zwart-Powell SubDs? Does it support creases?

hobold
Posts: 56
Joined: Wed Dec 21, 2011 6:08 pm

Re: Quadrics kinda sorta work for real time

Post by hobold » Mon Jul 30, 2012 8:38 pm

I am as new to this as you are. :-)

The box splines were a proverbial "rose by the wayside" so to speak. That rose does have an intoxicating smell, though. For example, my gut feeling about similarities to wavelets is backed up by publications from the mathematical community. All box splines can serve as prewavelets. Some researchers have even constructed a large family of box splines that can serve as basis for biorthogonal wavelets (which is the most useful and most widely employed type of wavelets in computer graphics to my limited knowledge). No idea where the ZP-element fits in, or where this might ultimately lead to. It's been a while since I worked with wavelets, and even longer since I was slightly fluent in the abstract math required for reasoning this deep.

Looks like I'm gonna be busy for a while ... thank you again for sending me down this path!

graphicsMan
Posts: 160
Joined: Mon Nov 28, 2011 7:28 pm

Re: Quadrics kinda sorta work for real time

Post by graphicsMan » Mon Jul 30, 2012 8:54 pm

Sure. I look forward to seeing where it goes.

hobold
Posts: 56
Joined: Wed Dec 21, 2011 6:08 pm

Re: Quadrics kinda sorta work for real time

Post by hobold » Tue Jul 31, 2012 4:21 pm

A subdivision algorithm based on the ZP-element does indeed exist: http://www.cise.ufl.edu/research/SurfLa ... 97.sss.pdf. But I dare say it results in clearly inferior surfaces than the other constructions mentioned so far. And no word if the ZP-element based algorithm actually makes it easier for quadrics to approximate the limit surface well (in whichever sense). Still interesting, though.

graphicsMan
Posts: 160
Joined: Mon Nov 28, 2011 7:28 pm

Re: Quadrics kinda sorta work for real time

Post by graphicsMan » Tue Jul 31, 2012 5:03 pm

My vote (not that I get one ;) ) would be Catmull Clark. I think you can get this data from Blender, and perhaps Maya (though I'm unsure if this is straight-up CC SubD). Also, people have done research on intersecting these via on-the-fly subdivision, and it would be interesting to see how pre-refined into quadrics competes. They rely heavily on coherent rays for their performance, but if you have pre-tessellated, that shouldn't be necessary for decent perf.

hobold
Posts: 56
Joined: Wed Dec 21, 2011 6:08 pm

Re: Quadrics kinda sorta work for real time

Post by hobold » Wed Aug 01, 2012 10:46 am

I don't know yet if we will get to vote or if the underlying math will dictate it all.

Meanwhile, I found another more thorough derivation of the subdivision scheme based on the ZP-element: http://www.cs.rice.edu/~jwarren/papers/edge.ps. The authors propose a different way of handling irregular faces of the control polygon, and they claim that the limit surface has piecewise quadratic parameterization. This is not the same as being a piecewise quadric, but it strongly limits how weird the individual patches can be. This in turn bodes well for the accuracy of an approximation with a low number of quadric patches.

(That paper might be of general interest for extensions of other subdivision schemes. The authors derive ways of cutting and melding subdivision surfaces and a few other goodies.)

Edit: Oh, and the hybrid triangle/quadrangle subdivision that you linked above has also been further improved since: http://www.cs.rice.edu/~jwarren/papers/triquad.pdf.

Post Reply