Progress Report?

Discussion about the next release of JPatch, with support for subdivision surfaces (SDS).

Re: Progress Report?

Postby dcuny » Tue Jun 03, 2008 2:51 am

sascha wrote:The good news is that JPatch can be started and most things work.

That's good news, all right. :o

So the next thing I'd like to read here is something like...

So you're saying it'll be ready for the next IRTC round? :wink:
dcuny
 
Posts: 2902
Joined: Fri May 21, 2004 6:07 am

Re: Progress Report?

Postby sascha » Tue Jun 03, 2008 9:40 am

"Wow - morphs and poses, that sound's like you're very close to implementing animation features again"

Thanks! :mrgreen:
That's good news, all right.

Sometimes you change just a small bit (like the way tools render themselves) and then wonder why nothing works - doh!
So you're saying it'll be ready for the next IRTC round?

I guess it'd be save to say that we'll will a Palme d'Or with a JPatch generated movie before the next IRTC round starts, or do you have some insider information about the IRTC resurrection?
sascha
Site Admin
 
Posts: 2792
Joined: Thu May 20, 2004 9:16 am
Location: Austria

Re: Progress Report?

Postby dcuny » Tue Jun 03, 2008 10:49 am

sascha wrote:I guess it'd be save to say that we'll will a Palme d'Or with a JPatch generated movie before the next IRTC round starts, or do you have some insider information about the IRTC resurrection?

The last I heard, David Buck was taking over the site. He'd hoped to have it running by the end of May, but Real LIfe(tm) got in the way.

The next animation round will "likely start Aug 15th and finish October 15th." I've got my fingers crossed. :)
dcuny
 
Posts: 2902
Joined: Fri May 21, 2004 6:07 am

Re: Reyes Renderer

Postby sascha » Wed Jul 09, 2008 6:13 pm

Edit: Merged from the Reyes Renderer thread.

sascha wrote:Darn it, I should be working on the modeling features, and not think about replacing my fully functional Catmull-Clark code with something better 8)
dcuny wrote:You can say that again!

Don't worry. Morphs should be working soon - they're no longer restricted to 1 dimension. Two dimensions are useful for puppeteer controls (e.g. a 2D area with several morph targets, and you can control the morph by dragging a knob within this 2D area), 3- or higher-dimensional morphs are useful for smartskin morphs (a 3D morph for a bone with 3 degrees of freedom).

Delaunay triangulation seems to work fine now - I've only tested it in 2D yet, but it should work well in higher dimensions too. One thing I haven't figured out yet is how to fill a unit hypercube with simplices to initialize everything - they should not be overlapping but fill the entire volume.

* In the 2D case it's trivial, the hypercube is actually a quad, and it can be filled with 2 triangles.

* In 3D it's a bit more complicated, the hypercube is a regular 3D cube, which can be filled either by 5 or 6 tetrahedrons (the 3D equivalent of a triangle). With a little imagination one can find those tetrahedrons.

* In 4D it gets confusing. We have a 4D hypercube and need to fill it with 4-simplices (pentachorons, the 4D equivalent of a tetrahedrons). My imagination is a little overstrained with that - so I'd need a pragmatic solution for this problem. I don't need to find all possible variants, just one.

* In 5D and higher I'd simply give up - can you imagine any algorithm that would find solutions for this?
sascha
Site Admin
 
Posts: 2792
Joined: Thu May 20, 2004 9:16 am
Location: Austria

Re: Reyes Renderer

Postby dcuny » Wed Jul 09, 2008 6:54 pm

sascha wrote:In 5D and higher I'd simply give up - can you imagine any algorithm that would find solutions for this?

This "math" stuff just confuses me. :P

Isn't the predictability of the tool part important? If the developer can't predict how it's going to behave, pity the poor user! ;)

I'll move this to the "Progress Report" thread, if you don't mind.
dcuny
 
Posts: 2902
Joined: Fri May 21, 2004 6:07 am

Re: Progress Report?

Postby sascha » Thu Jul 10, 2008 9:42 am

Isn't the predictability of the tool part important? If the developer can't predict how it's going to behave, pity the poor user!

Yes, but that's what this is about. Not only should it be predictable (I seldom use Math.random() anyway), but also intuitive. I really think that being able to interpolate between some morph-targets "in higher dimensions" is necessary to achieve this. One example are smartskin morphs - the JPatch 0.5 implementation is much too inflexible, and that's quite counter-intuitive. Here's an example:
Take the elbow and the lower arm bone. It can bend and twist. Especially when it's bended to the maximum (e.g. 160° or 170°), you'll have to correct some vertex-position to prevent the lover arm from overlapping. You could do that with JPatch 0.5, you could even add morph targets for any bend angle. What you could not do is add a morph target for poses where the arm was bended and twisted at the same time. Now that's what I call counter-intuitive.
The new system on the other hand will allow you to add smart-skin morph-targets at any combinations of x/y/z rotations of any bone - and if the bone can be scaled as well you'll need up to 6 dimensions for that. All the user has to think about is that "in this pose, I'd like to have a smart-skin morph-target" - once multiple targets have been added, JPatch will handle the interpolation between them.

The other application are 2D controls for e.g. facial expressions. You could bind tens or even more of morph targets to positions on a 2D control - moving the control in just 2 axes can thus save you from fine-tuning tens or even more of sliders.
sascha
Site Admin
 
Posts: 2792
Joined: Thu May 20, 2004 9:16 am
Location: Austria

Re: Progress Report?

Postby rjh » Fri Jul 11, 2008 4:31 pm

Hey Sascha,

Man ! All this sounds very interesting

"a 2D area with several morph targets, and you can control the morph by dragging a knob within this 2D area"


very interesting

"3- or higher-dimensional morphs are useful for smartskin morphs"


even more interesting

"Delaunay triangulation seems to work fine now - I've only tested it in 2D yet, but it should work well in higher dimensions too ... In the 2D case it's trivial ... In 3D it's a bit more complicated ... In 4D it gets confusing ... In 5D and higher I'd simply give up ..."

and
"The other application are 2D controls for e.g. facial expressions. You could bind tens or even more of morph targets to positions on a 2D control - moving the control in just 2 axes can thus save you from fine-tuning tens or even more of sliders."


all quite interesting.

So hey ... you have me wanting to try this out ... any of it. Got anything for us mortals to try out ?

Rob

BTW ... I just finished up animation using Jpatch on a short i am going to enter in some festivals ... will run it past you guys once i have the remainder of the sound implemented.
rjh
 
Posts: 179
Joined: Thu Dec 30, 2004 10:33 pm

Re: Progress Report?

Postby sascha » Fri Jul 11, 2008 4:34 pm

Looks like I've been barking up the wrong tree with natural neighbor interpolation.

What I need is some way to smoothly interpolate between some random samples, in any dimension. Doing some more research, I've learned about polyharmonic splines, and it looks like that this is exactly what I'm looking for.
I did some tests in 1D and 2D, and the results look more than promising. Here are some samples:
polyharmonic_spline_1d.png
polyharmonic_spline_1d.png (1.81 KiB) Viewed 5238 times
This shows a polyharmonic spline in 1D, fitting the curve to interpolate 4 samples.

The next images are more interesting, it shows the same thing in 2D:
polyharmonic_spline_2d_conrers.png
This spline surface interpolates four data samples (at the corners) - quite nice.

polyharmonic_spline_2d_random.png
Here the spline surface interpolates some random data samples.

To test whether it can reproduce a given function - sampled at random positions - I ran some more tests:
polyharmonic_spline_2d_ramp.png
polyharmonic_spline_2d_ramp.png (6.32 KiB) Viewed 5237 times
The data samples are at random positions, but sample a ramp function. As you can see, the spline is able to reconstruct the ramp function quite well. No flat spots, no undulation - cool.

polyharmonic_spline_2d_cone.png
Here a cone has been sampled at random positions. Again the spline is able to reconstruct it faithfully.

The algorithm works with any dimensions. Finding the weights takes some time as it requires solving a (potentially large) set of linear equations - but this isn't a problem, since the actual evaluation is very fast once the weights have been found. This would mean that if you modify a morph, the weights have to be recomputed, but during animation (e.g. when a morph slider value changes), evaluation of the spline function is pretty fast.
I'll have to run a few tests in higher dimensions, but if the results are as nice as the ones in 2D I'm pretty pleased.
This is just another example of what math can do for you ;-)

Edit: Works just fine in 3D - so I'm about to start working on morphs with this kind of interpolation.
I should also note that the 1D example above showed some overshoot - that's because it used distance³ term in the function - using just distance would yield linear interpolation. The 2D (and 3D) version just used distance, so there's no overshoot (and it results in something that's roughly equivalent to bilinear interpolation). I'll make this configurable, so you can basically treat smoothness against overshoot. Since it's just interpolating morph vectors, I think one can live with the "linear" interpolation, but anyway, it's always good to have options.
sascha
Site Admin
 
Posts: 2792
Joined: Thu May 20, 2004 9:16 am
Location: Austria

Re: Progress Report?

Postby dcuny » Fri Jul 11, 2008 6:45 pm

sascha wrote:Doing some more research, I've learned about polyharmonic splines, and it looks like that this is exactly what I'm looking for.

Research is good. And these splines look very slick. 8)

Since these are based on radial basis functions (i.e. functions of distance), they should be perfect for a 2D slider sort of interface, too.

The 2D (and 3D) version just used distance, so there's no overshoot (and it results in something that's roughly equivalent to bilinear interpolation). I'll make this configurable, so you can basically treat smoothness against overshoot. Since it's just interpolating morph vectors, I think one can live with the "linear" interpolation, but anyway, it's always good to have options.

Yes, being able to choose between these options would be great. When blocking out a shot, most people turn everything to linear, so that the "pops" from one pose to the next. That way, they can concentrate on moving from pose to pose, instead of being distracted by the interpolated action (which is usually pretty crappy at that point). Otherwise, you start tuning and fiddling before you've got your shot properly blocked out.
dcuny
 
Posts: 2902
Joined: Fri May 21, 2004 6:07 am

Re: Progress Report?

Postby sascha » Wed Jul 16, 2008 3:22 pm

I've modified the code so that it now can process multiple columns for the output-vectors. I ran some more realistic tests, and the results as well as the performance look good. Here's what I considered a typical application:
2D control with 6 morph-targets. Each target is a vector of size 300 (e.g. 100 3D vectors).
Time to solve the system: 0.6 milliseconds (This would run every time a morph-target was changed - can of course be evaluated lazily).
Time to evaluate the spline: 0.04 milliseconds (Would run for each frame).

I think this is more than acceptable. and assumed that most morphs will manipulate far less than 100 control-points, the system should be able to evaluate quite a few of such morphs in realtime.

When blocking out a shot, most people turn everything to linear, so that the "pops" from one pose to the next.

What you describe isn't linear interpolation, but nearest neighbor. I agree that this is still usable for "debugging" the animation.
What I was referring to was that linear interpolation will never lead to overshoot, but has discontinuities in the 1st derivative (i.e. the slope changes abruptly). Something like cubic interpolation (or, in this case, something like the r²ln(r) or r³ radial basis functions) produces smooth curves, but also leads to overshoot.
sascha
Site Admin
 
Posts: 2792
Joined: Thu May 20, 2004 9:16 am
Location: Austria

Re: Progress Report?

Postby dcuny » Wed Jul 16, 2008 5:18 pm

sascha wrote:What you describe isn't linear interpolation, but nearest neighbor. I agree that this is still usable for "debugging" the animation.

Yes, my brain is failing me. I visualized these "flat" curves (how's that for an oxymoron?) and thought "linear." I think "no interpolation" is the term I wanted.

Anyway, it's always good to see an update of any sort. :)
dcuny
 
Posts: 2902
Joined: Fri May 21, 2004 6:07 am

Re: Progress Report?

Postby sascha » Wed Jul 16, 2008 5:27 pm

Yes, we've had visitors from Friday 'til today, so I've had no to do any work on JPatch until now...
sascha
Site Admin
 
Posts: 2792
Joined: Thu May 20, 2004 9:16 am
Location: Austria

Re: Progress Report?

Postby nicholas_yue » Sun Jul 27, 2008 10:39 pm

sascha wrote:Looks like I've been barking up the wrong tree with natural neighbor interpolation.

What I need is some way to smoothly interpolate between some random samples, in any dimension. Doing some more research, I've learned about polyharmonic splines, and it looks like that this is exactly what I'm looking for.


Is the Polyharmonic code in the form of a library which can be reuse for other purposes?

If not, is there any implementation I could download to try out on my own set of data?

Regards
nicholas_yue
 
Posts: 6
Joined: Mon Apr 09, 2007 12:23 am

Re: Progress Report?

Postby sascha » Mon Jul 28, 2008 10:03 am

Is the Polyharmonic code in the form of a library which can be reuse for other purposes?

It's just a quite simple class - PolyharmonicSpline.java.
It depends on just a few utility methods to solve systems of linear equations, they're based on methods taken from the javax.vecmath package, and I've placed them into a utility class.
There's also a class called Test that can be started to test it.
Here's a jar file containing source and binary. The class you can use is PolyharmonicSpline (read this Wikipedia entry for reference), see Test.java to see how to use it. The spline takes any number of "centers", in any dimensions, and the same number of values (one per center), also any-dimensional. Use the evaluate function to evaluate it.

Feel free to ask if you have any questions, and let me know if you find any bugs please.

Here's the file: spline.jar - License is GPLv2.
sascha
Site Admin
 
Posts: 2792
Joined: Thu May 20, 2004 9:16 am
Location: Austria

Re: Progress Report?

Postby sascha » Wed Jul 30, 2008 9:22 pm

Here's another update.

Slowly the modeler starts becoming usable again. I've added XML output (parsing will follow shortly) - it's so much more fun if you can save your work ;-)
In order to not save meshes at e.g. level 4 (with potentially some million vertices) if just a few vertices have been moved, I've implemented a mechanism that tags modified hierarchy vertices and locates them by using a path. The path is basically an array of integers and locates a face at a given subdivision level, e.g. [2 1 0 3 209] means the third subface of the second subface of the first subface of the fourth subface of top-level-face #209.
This turned out to be very helpful, not only for saving and loading models, but during editing as well.
To keep things simply, certain operations (like extrude) delete some faces and create new ones. Until now, any hierarchical edits on such a face were lost, even if the extrude operation created the same face again. Now, since the hierarchy-edits are stored elsewhere, they're automatically reapplied once the face has been recreated.
This also means that for rendering JPatch doesn't have to keep the entire e.g. level-4 mesh in memory just because there are a few edited vertices at that level. Now it needs to create only a few high-level vertices (just to reach all the edited ones) - at least with renderers that have native support for hierarchical subdivision-meshes.

Weld is now implemented.

Undo/redo is deactivated for some operations, but the edits are basically all there, I just have to reactivate them.
sascha
Site Admin
 
Posts: 2792
Joined: Thu May 20, 2004 9:16 am
Location: Austria

PreviousNext

Return to JPatch SDS Minimal Development

Who is online

Users browsing this forum: No registered users and 1 guest

cron