Hook implementation

Ideas, enhancements, feature requests and development related discussion.

Postby sascha » Sat Mar 04, 2006 10:13 am

I'm still thinking about how one could combine the adaptive and the global patch finder nicely. We'll see.

I think this should be possible. We could keep the cp/neighbor table "live" (but this would require modifying the edits - if e.g. a point was removed or detached, that neighborship table needs to be updated), and then call the patchfinder on the point in question (IIRC right now the outmost loops simply walks through all points).

That's probably the most popular way of thinking with most people, me included. But then I'm always amazed what can be done with a bit of theory and a good idea...

You're right - but still, I don't think that finding the cycles is possible without looping through all points one time - so N performance seems to be the best we can get. The implementation could be done better though (IIRC there's a lot of unneccessary conversion between lists and arrays right now, and perhaps some things can be handled more effeciently using sets or maps instead of lists - I'll have to look...).

Here's my plan for implementing the changes:

Ok (if you add a 0. CVS branch ;-) )
sascha
Site Admin
 
Posts: 2792
Joined: Thu May 20, 2004 9:16 am
Location: Austria

Postby Torf » Mon Mar 06, 2006 8:43 pm

Okay, I started working on it. There's now a new branch, called new_hook and the main branch was "versioned" Root_new_hook at the time of the branching. That should make merging easy (hopefully :)).

I'm already in step 1, preparation of the sources. There are quite some changes in ControlPoint. I'd like to hear your opinion about some of them. Feel free to veto any of the following:


public static final float[] HOOKPOS - Not needed anymore

private static final float[] HOOK_B0 - These seem to be the interpolation coefficients for the bezier curve at the old hook positions. They're only used in getReferenceHookPosition(int). With dynamic hook positions, I guess we won't be able to cache hook positions like this. So these are obsolete, too.

private ControlPoint cpChildHook
private ControlPoint cpParentHook - Not needed anymore

public ControlPoint getHookAt(float hookPos) - This has to be replaced by something like getHookNear(float hookPos), a function which returns the next hook whose distance to hookPos is less than a fixed distance epsilon. 2*epsilon would be the minimal distance of two hooks one the same curve. Also makes sense from user's point of view, IMHO. See below the list, too.

private ControlPoint getHookHead()
public ControlPoint getChildHook()
public ControlPoint getParentHook()
public void setChildHook(ControlPoint childHook)
public void setParentHook(ControlPoint parentHook) - Not needed anymore

public ControlPoint getHookCurve() - Not needed anymore

public ControlPoint createEmptyHookCurve() - Should be replaced by something like createHookAt(float hookPos) which returns the new hook like the old method.

public void computeTargetHookBorderTangents(Vector3f v3Direction, Vector3f v3Start, Vector3f v3End)
public void computeReferenceTargetHookBorderTangents(Vector3f v3Direction, Vector3f v3Start, Vector3f v3End) - Could you explain what these methods do? I'm not getting it from the JavaDocs :)

public ControlPoint trueCp() - Not needed anymore. For target-hooks, getPrevAttached() can be used from now on.


Of course there are other changes, too. But these are the changes which change the interface of the class. Additionally, there are the curve traversal methods:
  • getNext()
  • getPrev()
  • getNextCheckLoop()
  • getNextCheckNextLoop()
  • getPrevCheckLoop()
I suggested renaming the old ones to make clear that they return none-hook cps. At least those ...CheckLoop ones would get really long names, though. I'm not sure if that's practical. So the question is: Long names or abbreviations? The best would be to use "NH" instead of "NoneHook", IMHO. So getNextCheckNextLoop becomes getNextNHCheckNextLoop. Not too readable, but the best we probably get.
All these methods will be created for all-point-traversal, too (with the old names).

There's another point of the whole concept I'd like to discuss: Although non-static hook-positions are a good idea some restrictions have to be made in order to keep the whole thing useable. One is mentioned above: There should be a mininmal distance between two hooks on the same curve. With dynamic hook positions, being able to drag one hook over another one (so that they switch positions on the curve) would be a nice feature, too.
Torf
 
Posts: 155
Joined: Mon Nov 08, 2004 8:45 pm
Location: Germany/Konstanz

Postby sascha » Tue Mar 07, 2006 9:40 am

Hi Torf,

I agree with you about the obsolete methods.

computeTargetHookBorderTangents... Could you explain what these methods do? I'm not getting it from the JavaDocs


Yes, I've added it to the wiki, you can find an explaination here.

One is mentioned above: There should be a mininmal distance between two hooks on the same curve.

Agreed.
sascha
Site Admin
 
Posts: 2792
Joined: Thu May 20, 2004 9:16 am
Location: Austria

Postby Torf » Wed Mar 08, 2006 9:17 pm

Here's my status report after step I (preparation of sources) is pretty much complete:

public Point3f getReferenceHookPosition(int hook)
public Point3f getHookPosition(int hook)
Not sure what to do with these methods. They're used in ViewDefinition.getClosestControlPoint(). But that method won't work as it did before with the new hook concept. If I'm right getClosestControlPoint is used to detect mouse clicks on control points (which would work as before) and on possible hook points (that won't work as before).
As hooks can now be placed anywhere on a curve, something like a getPositionOnCurve(Point3f p) could replace getHookPosition. The new method would return a value from 0 to 1 if the given point was closer to the curve at that position than a fixed minimum distance, or -1 else.
Of course getClosestControlPoint would have to be adapted.

public void setPosition(Point3f position)
public void setPosition(float x, float y, float z)
public void setReferencePosition(float x, float y, float z)
According to the docs, those set the (reference-) position on the cp, or on the cp's head (if the cp isn't a head). But they throw a IllegalStateException if the cp's not a head instead. I think they should throw that exception if the cp is a hook and call getHead().setPosition() if the cp's not a head. What's wrong - docs or sources?

public void invalidateTangents()
All the calls to it and the method itself have been commented out. Are they needed anymore?

Last but not least another question came up: The ControlPoint class makes heavy use of its private members cpNext and cpPrev. In most of the cases, getNextNH() and getPrevNH() would have to be used from now on instead. I haven't tested anything yet, but depending on how often these pieces of code are called, executing the get..NH() methods every time could have a negative impact on performance. So the question is: Should we keep a pointer to the next and previous none-hook cps? Something like private ControlPoint cpNextNH. The advantage would be cleaner and possibly faster code, the disadvantage additional book-keeping. Book-keeping would have to be done when creating or removing control points. Hook creation and removal would not influence the fields. Should be simple, so I vote for the extra pointers.
Torf
 
Posts: 155
Joined: Mon Nov 08, 2004 8:45 pm
Location: Germany/Konstanz

Postby sascha » Thu Mar 09, 2006 8:13 am

If I'm right getClosestControlPoint is used to detect mouse clicks on control points...

Yes, that's right. My idea was to constraint new hooks to the 1/4, 1/2 and 3/4 positions, and allow the user to move them later. This way the code that detects if the mouse hit a possible hook position doesn't have to be changed.

What's wrong - docs or sources?

I'd say the docs have been right until I changed the source ;-)
Trying to set the position of a non head doesn't make sense and should not happen, so I think the method should only set the position on heads and throw an exception when called on an attached cp or on a hook.

All the calls to it and the method itself have been commented out. Are they needed anymore?

Before I implemented bones, the tangents (inTangent and outTangent) were cached (so getXXTangent() returned the cached value) untin the points were moved (which triggered a call to invalidateTangents). But sice cp's can also be "moved" by rotating some bones the code to properly invalidate the tangents became too complex, so I abandoned that concept.

I haven't tested anything yet, but depending on how often these pieces of code are called, executing the get..NH() methods every time could have a negative impact on performance.

I tend to disagree. In most cases the next (or prev) CP won't be a hook, so the overhead reduces to a if (cpNext.hookPos > 0) check - the performance impact of which should be negligible.
Similar checks are performed e.g. in getNextCheckLoop()...
So I'd integrate it without any caching, and only if we see bad performace we could try to add optimizations.

Some random quotes on that subject:
"More computing sins are committed in the name of efficiency (without necessarily achieving it) than for any other single reason - including blind stupidity." -W.A. Wulf
"Premature optimization is the root of all evil." -Hoare and Knuth
"Bottlenecks occur in surprising places, so don't try to second guess and put in a speed hack until you have proven that's where the bottleneck is." -Rob Pike
"The First Rule of Program Optimization: Don't do it.
The Second Rule of Program Optimization (for experts only!): Don't do it yet."-Michael Jackson

Ok, I guess you get the idea :wink:
sascha
Site Admin
 
Posts: 2792
Joined: Thu May 20, 2004 9:16 am
Location: Austria

Postby Torf » Sat Mar 11, 2006 5:19 pm

Hehe. You're right about the performance of getNextNH() and friends, I guess. Now that I changed those pieces of code I noticed that they aren't called often anyway. And it really is cleaner that way :wink:

That brings me right to my next question: As you stated yourself in the wiki, there's a lot of duplicated code due to the ...Reference... methods for tangents and positions. I took a look at it and it shouldn't be hard to merge a lot of that code. But I'm not 100% sure about what's the difference between reference and non-reference, and I'd like to have that one clear before damaging anything. I'd say that the reference ones are object-space and the others world-space. Is that right? And the way to transform from one into the other is the m4Transform matrix, isn't it?

I noticed another thing, but it's not crucial, so I only mention it to hear your opinion about it: IMHO the tangent calculations for the different tangent modes (Peak, SPatch, etc.) should be outsourced into their own classes:
Code: Select all
protected class TangentComputer {
    protected abstract void calculateTangents()
    protected abstract void calculateReferenceTangents()
}
The actual implementation of the code could be realized as inner classes of ControlPoint, so we don't loose the access to the private members.
Torf
 
Posts: 155
Joined: Mon Nov 08, 2004 8:45 pm
Location: Germany/Konstanz

Postby sascha » Sat Mar 11, 2006 7:24 pm

But I'm not 100% sure about what's the difference between reference and non-reference, and I'd like to have that one clear before damaging anything. I'd say that the reference ones are object-space and the others world-space. Is that right? And the way to transform from one into the other is the m4Transform matrix, isn't it?

Yes and no :?
The reference position is the position of the point when no pose and no morph is applied (just like if there were no morphs and no bones set up). If you apply a morph or rotate a bone, a point can can change its position. The mapping between this reference position and the - let's call it posed position (I'm open for suggestions for a better name) - is stored in a 4x4 matrix per controlpoint.

I initially cached the posed position too, but the code needed to properly invalidate it when needed was quite complex (and likely slower then passing the position vector through the matrix), but it keeps the inverse of that matrix cached.

A more naive approach would be to allow modifications only in the reference pose - but this isn't a limitation in this design: You can pose the model, apply morphs and still move controlpoints (this behavior is actually needed when defining muscle-morphs).

IMHO the tangent calculations for the different tangent modes (Peak, SPatch, etc.) should be outsourced into their own classes.

Agreed, that would be much nicer in terms of OO design. On the other hand, dynamic dispatch might be costly and this method gets called quite often - and I don't plan to add more tangent modes in the future, so I could live with a switch...case block too.
I also thought about a Hook class (as a subclass of Controlpoint) - but I'm not sure - I mean ControlPoint isn't intended for subclassing outside the entity package, so we could switch from private to package (default) visibility, but then again I've read that the overhead of method invocation is orders of magnitudes higher over private final methods. (I think the compiler can inline private final methods, which could lead to better cache hit rates, but I'm really not sure about that and maybe talking nonsense :-) )

I feel a bit like caught in a trap now - just one message earlier I preached that clean design goes over performance, and optimization is the root of all evil... :oops:
I really don't know - I mean, a hook is the only special case of controlpoint (and as long as this doesn't change, there is little need for a class hierarchy), and there are actually only two types of tangent flavors: sPatch mode and JPatch mode (I think the A:M compatible mode isn't used ATM) - and there's peak and round mode of course.
It's a matter of taste: Both, the classes for the tangent mode, and a hook subclass would make the code more clean and readable. But I would closely monitor performance, as these methods could be called about 4 times per controlpoint during rendering - just to be on the save side. As long as it doesn't slow down everything by a factor of two (which I don't believe) I think that a clean design is more important than a marginal performance improve.
sascha
Site Admin
 
Posts: 2792
Joined: Thu May 20, 2004 9:16 am
Location: Austria

Postby Torf » Fri Mar 17, 2006 7:34 pm

Just a quick status update to let you know how the progress is: The last week I've been busy with Real Life (tm), though, so progress has been slow.

The ControlPoint class is totally converted to the new hook system. I also merged all those ...Reference... methods with the standard ones, whereas I left the tangent computers as normal methods.

I'm now working at getting the edits working again. The changes to ControlPoint caused 180 errors in the whole JPatch sources due to now obsolete methods. About 90 of those were easy to fix, the rest is nested in the edits. Before fixing those, I need to understand how those edits interact, that's what I'm trying to figure out right now (A little nitpick here: Comments that don't match the code don't make this job easier :wink:).

After adapting the edits it should at least run again. Of course the patch finder and stuff like i/o will still have to be taken care of then. Last but not least: Lots of testing (and hopefully much less bug hunting :wink:).
Torf
 
Posts: 155
Joined: Mon Nov 08, 2004 8:45 pm
Location: Germany/Konstanz

Postby sascha » Fri Mar 17, 2006 7:51 pm

A little nitpick here: Comments that don't match the code don't make this job easier

:cry:
At least I tried :wink:
I know, I know. Would it make sense if I try to bring the flow-charts up-to-date (say, until mid next week)? This way it would be easier for you to figure out how the edits collaborate, and you could update the flowcharts again if you change the edits. What do you think?
I think at least for debugging the flowcharts could be extremely helpful (to distinct design- from implementation problems).
sascha
Site Admin
 
Posts: 2792
Joined: Thu May 20, 2004 9:16 am
Location: Austria

Postby Torf » Sat Mar 18, 2006 4:11 pm

sascha wrote:At least I tried

I know that. It's just that I'm a comment-maniac :wink: I do understand, however, that not everybody shares my obsession for comments. Missing comments are often not the problem, but if the comments don't match the code one wonders which is wrong...

About the charts: IMHO we don't need those detailed ones showing each edit individually, because one can look into the sources for that kind of information (the edits are pretty short and simple). What I'd like to see (and what I started to prepare) is a chart which shows the overall structure of the edits, their differences and how they interact.

As I already started preparing it you don't need to do it on your own (at least if it isn't your most urgent wish :wink:). I'll just present you the final chart to check if I got it right.
Torf
 
Posts: 155
Joined: Mon Nov 08, 2004 8:45 pm
Location: Germany/Konstanz

Postby sascha » Sat Mar 18, 2006 4:36 pm

Agreed. IRRC the flowcharts for most of the atomic edits are already there (though not all are up-to-date), but many of the compound edits are missing. The compound-edit simply have boxes that represent atomic (or other compound) edits in their flowcharts.

I think the charts are a good thing - once you don't code on the edits you'll quickly forget, and believe me, six month later you've got no idea what's going on :D
Now I'm perfectly aware that documenting the code should prevent exactly this situation, but in the case of edits I felt that a documentation is not enough - the edits are interweaved, and I started to create the flowcharts to somehow capture the big picture.

If you're working on the diagrams too, that's great, and I'll wait (I think it's not the best idea if we both work on them at the same time ;-) )
We'll gonna need them for debugging later. What I have in mind is some kind of automatic testing framework that checks the models. Perhaps you've already discovered the "check model" feature that tests the model's sanity, but what's needed is such a test for edits - i.e. "is is the model still ok after several steps of undo/redo of different edits?". It's quite impossible to test all combinations "by hand", and sometimes an error can sneak in without being noticed (e.g. coincident splines).

Do you have expirence with junit? I wondered if it would make sense to make such tests as junit tests...
sascha
Site Admin
 
Posts: 2792
Joined: Thu May 20, 2004 9:16 am
Location: Austria

Postby Torf » Sat Mar 18, 2006 7:17 pm

Found some time to work on it again :D

I re-checked the situation with the edits. Firstly, I might not need the chart, yet, because most edits will at least compile. There are still some edits which use now obsolete methods, and I need your help in understanding what they do:

It's all about the drop/remove/delete control point/curve stuff. I see what the basic principle is, i.e. removing means 'physically' removing something (from the data structures), dropping means 'logically' removing something (from the overall concepts) and revalidating the environment. But what's deleting? Especially the trio Remove/Delete/DropControlPoint is hard to understand. Could you explain those a bit?

Nevertheless, those charts are nice to have, and after looking at them again, I think you're right when saying that the detailed ones are useful, too.

The clone edits are broken, too. But these are probably one of the hardest pieces to fix, so I'll leave them until the rest works again. Otherwise I'll die debugging them :)

Secondly, I forgot one task which is left after the stuff compiles again: The usages of the getNextNH() and similar methods have to be checked - some of the edits (e.g. AtomicReverseCurve) have to be rewritten (or at least changed), too.
Torf
 
Posts: 155
Joined: Mon Nov 08, 2004 8:45 pm
Location: Germany/Konstanz

Postby sascha » Sat Mar 18, 2006 11:51 pm

Especially the trio Remove/Delete/DropControlPoint is hard to understand. Could you explain those a bit?

The difference between removing and deleting a controlpoint is that deleting it (delete key) would open (and split) the curve, while removing it (backspace key) would just remove it from the curve (and reconnect the curve again).

The curve 1-2-3-4-5 would, after deleting point 3 look like 1-2 and 4-5 (split into two parts), but after removing point 3 it would look like 1-2-4-5. The same is true if multiple points are deleted or removed, respectively.

Now, whenever you'd like to get rid of a controlpoint, there are several things to do: If it has attached points, they'll have to be detached, if it is part of a patch, the patch has to be removed, if it is part of a selection, it has to be removed from that selection, if it is a part of a morph, it has to be removed from the morph,... you get the picture. Before I rewrote the edits, all those taks were spread across several methods and edits, and the code wasn't maintainable any more. That's why I wrote that drop edit: It simply cleans up before the controlpoint can be discarded.
Perhaps discard would be a better name.

IIRC the drop edit just removed the controlpoint from any other datastructures that reference it. Other things (like removing an entire curve if it's shorter than two points) are handled by other edits.

The usages of the getNextNH() and similar methods have to be checked - some of the edits (e.g. AtomicReverseCurve) have to be rewritten (or at least changed), too.

If there's something missing in the wiki about the new hook implementation (here), please add/correct it - it might help us later to check and polish up everything once the dust has settled :-).
sascha
Site Admin
 
Posts: 2792
Joined: Thu May 20, 2004 9:16 am
Location: Austria

Postby Torf » Sun Mar 19, 2006 11:58 am

sascha wrote:The difference between removing and deleting a controlpoint is that deleting it (delete key) would open (and split) the curve, while removing it (backspace key) would just remove it from the curve (and reconnect the curve again).

*bangs head against a wall*
Of course! I've never thought about that possibility. It seemed to be too high-level somehow (although that train of thought doesn't make much sense). Thanks for pointing it out.

I'll go over my changes and update the wiki, too.
Torf
 
Posts: 155
Joined: Mon Nov 08, 2004 8:45 pm
Location: Germany/Konstanz

Postby sascha » Sun Mar 19, 2006 3:14 pm

I think I've made a mistake: DropControlPoint actually checks some hook issues (I guess this part needs to be rewritten), calls RemoveControlPointFromEntities (which does what I described first: it removes the CP from all objects that have a reference to it - patches, selections, morphs,...), detatched the point and finally sets a deleted flag on the cp (this isn't very smart, I know, but it was the easiest way to prevent a cp from being removed twice during a single delete/remove operation).
sascha
Site Admin
 
Posts: 2792
Joined: Thu May 20, 2004 9:16 am
Location: Austria

PreviousNext

Return to Development

Who is online

Users browsing this forum: No registered users and 1 guest

cron