Re: Quadrics kinda sorta work for real time

(L) [2012/07/27] [tby graphicsMan] [Re: Quadrics kinda sorta work for real time] Wayback!

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 [SMILEY :)] 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.

(L) [2012/07/27] [tby hobold] [Re: Quadrics kinda sorta work for real time] Wayback!

>> 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.

(L) [2012/07/27] [tby graphicsMan] [Re: Quadrics kinda sorta work for real time] Wayback!

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:
[LINK http://www.autodeskresearch.com/pdf/qtEG.pdf]

(L) [2012/07/29] [tby hobold] [Re: Quadrics kinda sorta work for real time] Wayback!

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:
[IMG #1 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.

[IMG #1]:

(L) [2012/07/30] [tby hobold] [Re: Quadrics kinda sorta work for real time] Wayback!

I am as new to this as you are. [SMILEY :-)]
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!

(L) [2012/07/31] [tby hobold] [Re: Quadrics kinda sorta work for real time] Wayback!

A subdivision algorithm based on the ZP-element does indeed exist: [LINK http://www.cise.ufl.edu/research/SurfLab/pre99-papers/9697.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.

(L) [2012/07/31] [tby graphicsMan] [Re: Quadrics kinda sorta work for real time] Wayback!

My vote (not that I get one [SMILEY ;)] ) 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.

(L) [2012/08/01] [tby hobold] [Re: Quadrics kinda sorta work for real time] Wayback!

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: [LINK 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: [LINK http://www.cs.rice.edu/~jwarren/papers/triquad.pdf].

(L) [2012/09/11] [tby hobold] [Re: Quadrics kinda sorta work for real time] Wayback!

Think of the grey cylinders as control mesh. If you applied mid-edge subdivision, the limit surface would consist of four curved triangular patches (order 2 Bezier triangles, I presume). What you are actually seeing are four triangular quadric patches, that seem to approximate the actual limit surface fairly well. "Fairly well" at least considering that no actual subdivision was done, and that four quadrics is the minimum number required (because that is the number of patches of the limit surface).
The 16 spheres along the outer rim are positioned on the limit surface to guarantee C0 connectivity to adjacent patches (because 5 points uniquely specify a conic curve). The inner 9 spheres are in some sense free parameters, but cannot be chosen arbitrarily (I still have to work out the exact constraints ... don't hold your breath; it is not as simple as a tetrahedral hull).
This single example doesn't prove anything, other than the approach has survived one more obstacle that could have killed the idea. The example is a rather friendly case, where the control mesh topology is regular (4 sided faces and vertices of valence 4), not too convoluted, and still relatively close to the "flat" case (which would yield a piece of the Zwart-Powell element). More contorted control meshes probably require a subdivision step or two before quadrics are a reasonably nice fit. No idea yet what happens at irregular faces or vertices.

(L) [2012/09/11] [tby hobold] [Re: Quadrics kinda sorta work for real time] Wayback!

Today: a lab experiment; tomorrow: a prototype; next week: the world! [SMILEY :)]
But jokes aside, this will be a long road. GraphicsMan, "you da man!" for pointing me to a much better starting point than what I have tried on my own. In the unlikely case that I do indeed end up enabling ubiquitous curved surfaces on digital screens everywhere, you'll know that it's all your fault. [SMILEY :)] And in the more likely case that I spectacularly fail, I will still be amazed by all the interesting things I learned along the way.
I'll reverse my earlier decision about giving up on this project. Instead I'm going to pester my acquaintances in academia to see if someone can feed me while I develop this further. Now I can finally prepare tangible examples, where before I only had a vague intuition. That's a very welcome change.

(L) [2012/12/03] [tby graphicsMan] [Re: Quadrics kinda sorta work for real time] Wayback!

Very cool. As you point out, this is not enough quadrics to appear artifact free (though it does look nice a smooth [SMILEY :)] ). It would be an interesting experiment to see how many quadrics are needed before this is imperceptibly different from a full catmull-clark or NURBS solution, and compare that to the same metric for triangles. It would be neat to see the difference in the number of primitives needed to achieve that quality, and the resulting in-memory size difference (as well as ray tracing speed differences).

(L) [2013/05/30] [tby hobold] [Re: Quadrics kinda sorta work for real time] Wayback!

After dabbling with CUDA and OpenCL, I have been drawn back to the more theoretical side of things. Been reading a lot about subdivision surfaces, about box splines and simplex splines ... experimented some more.
I stumbled on something interesting that might close a gap in our understanding of one particular subdivision algorithm, namely Kobbelt's sqrt(3) scheme. As you may know, all subdivision schemes generalize some bivariate spline basis to meshes of arbitrary topology. The only exception is the sqrt(3) scheme, which leads to a spline basis function that was previously unknown.
As it happens, there seems to be a gap between simplex splines and box splines, which are based on high dimensional analogues of tetrahedron and cube, respectively. High dimensional counterparts of octahedra ("orthoplexes") can cast shadows on lower dimensional spaces, too. And at least one such shadow of a four dimensional orthoplex looks suspiciously like a spline basis function:
[IMG #1 Image]
This one is a piece-wise quadric, unlike the sqrt(3) basis, but it is based on a slightly exotic hexagonal grid, just like sqrt(3) subdivision.
Surprisingly, this construction of splines seems to have been overlooked so far in the literature. I dare not claim that I found something truly new, given the close relationship to simplex splines and box splines. But until prior art is unearthed, I am taking the freedom to christen this family of splines Orthoplex Splines.
They are no revolution, but the least they do is enable a bivariate quadric spline on a triangular grid. And I strongly suspect they can explain where sqrt(3) subdivision is coming from.

I realize that most of you posters here focus on rendering. But some of you might care for the modeling side, too. This find seemed interesting enough to bother you and share it. [SMILEY :)]

[IMG #1]:

(L) [2013/05/30] [tby hobold] [Re: Quadrics kinda sorta work for real time] Wayback!

>> graphicsMan wrote:Do you have a formulation for automatically fitting these to a tri/quad mesh? Also, you say piece-wise quadric. Does this have any implications for the continuity of the overall surface?
Short version: this is no better or worse than the Zwart-Powell Element mentioned earlier in this thread.
Long version: I don't know the corresponding subdivision rule for the depicted basis function; I only know that it will have to follow the sqrt(3) grid refinement rules (otherwise the function cannot be decomposed into a weighted sum of smaller copies of itself). Without a subdivision scheme, I have no ... "anchor" for wrapping to an arbitrary mesh. And even then, the only thing I could guarantee is that the quadric patches would converge rather quickly towards the limit surface, i.e. some subdivision steps would still be required. (As before, quadrics are not a good primitive for direct modeling, but they might be a good primitive for rendering.)
Continuity of this new spline is still only C1. The only significant difference to the Zwart-Powell Element further above is that this new spline lives on a triagonal/hexagonal grid, and that it is a bit ... "rounder", despite its support polygon having only six vertices rather than eight. But it is rotationally symmetrical with respect to a 60 degree angle, while the Zwart-Powell Element is only symmetrical after 90 degrees of rotation.

Hypothetical outlook:
I think there is another orthoplex spline that has triangular support (but I have not performed that particular construction yet, so there might be showstoppers). Additionally, the bivariate simplex spline with C1 continuity (which would consequently be a piece-wise quadric) lives on a pentagon. If I can find another construction for an appropriate spline supported on a square, I would have some "natural" spline basis functions for vertex valences anywhere from three to six. There would be other constraints as well, so the mesh could still not be arbitrary. But this would be a significant step towards skipping the intermediate subdivision surface, and building a spline surface directly from quadric patches, while still maintaining the "user interface" of a subdivision surface.

(L) [2013/07/23] [tby hobold] [Re: Quadrics kinda sorta work for real time] Wayback!

It turns out that bivariate spline basis functions are not strictly limited to the two dimensional setting (i.e. height fields):
[IMG #1 Image]
The basic idea is the same as Metaballs. In this example, there would be one ellipsoid component in the center, and a cylindrical component subtracted from it (which effectively drills a hole). The ears are smaller ellipsoid components added to the central blob. The tangent continuity of the aforementioned spline bases carries over to three dimensional "blob" components. And that ultimately implies tangent continuity of any isosurface, an example of which you can see above.
As a user interface, I don't think Metaballs are a preferred choice of graphics artists. But this construction proves by demonstration that smooth quadric spline surfaces of arbitrary topology do exist and can be edited directly. That is a rather tangible, constructive result. [SMILEY :)]

[IMG #1]:

Re: Quadrics kinda sorta work for real time back

Board: Home Board index Raytracing General Development