Quadrics kinda sorta work for real time

Practical and theoretical implementation discussion.
hobold
Posts: 56
Joined: Wed Dec 21, 2011 6:08 pm

Re: Quadrics kinda sorta work for real time

Post by hobold » Tue Sep 11, 2012 9:02 am

Hmm. Maybe this can actually work ... :)
Image

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

Re: Quadrics kinda sorta work for real time

Post by graphicsMan » Tue Sep 11, 2012 4:16 pm

cool. Can you explain more? :) Which what is kinda working?

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

Re: Quadrics kinda sorta work for real time

Post by hobold » Tue Sep 11, 2012 6:38 pm

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.

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

Re: Quadrics kinda sorta work for real time

Post by graphicsMan » Tue Sep 11, 2012 7:24 pm

I'm looking forward to the point where you can provide memory/speed comparisons between small tessellation into quadrics vs deep tessellation into triangles at the same perceptual quality :) I will be eagerly watching this thread ;)

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

Re: Quadrics kinda sorta work for real time

Post by hobold » Tue Sep 11, 2012 8:17 pm

Today: a lab experiment; tomorrow: a prototype; next week: the world! :)

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

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

Re: Quadrics kinda sorta work for real time

Post by hobold » Mon Dec 03, 2012 11:09 pm

Slow progress (no bonus points if you can spot the obvious bugs and flaws):
Image
This is based on midedge subdivision of a toroidal control polyhedron of six by six vertices (i.e. a coarse torus with hexagonal cross sections for both ring and tube). It's been surprisingly difficult putting everything together. :-/

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

Re: Quadrics kinda sorta work for real time

Post by graphicsMan » Mon Dec 03, 2012 11:54 pm

Very cool. As you point out, this is not enough quadrics to appear artifact free (though it does look nice a smooth :) ). 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).

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

Re: Quadrics kinda sorta work for real time

Post by hobold » Thu May 30, 2013 12:13 am

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:

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

toxie
Posts: 118
Joined: Mon Nov 28, 2011 12:30 pm
Location: germany
Contact:

Re: Quadrics kinda sorta work for real time

Post by toxie » Thu May 30, 2013 9:00 am

I wish i knew more about surface modelling, but this sounds pretty cool to me.. ;)
Better you leave here with your head still full of kitty cats and puppy dogs.

jbikker
Posts: 217
Joined: Mon Nov 28, 2011 8:18 am
Contact:

Re: Quadrics kinda sorta work for real time

Post by jbikker » Thu May 30, 2013 10:40 am

Yes, no problem et al with this kind of info on the forum. :)

Post Reply