Hook implementation

Ideas, enhancements, feature requests and development related discussion.

Hook implementation

Postby Torf » Sun Feb 26, 2006 6:32 pm

I'm trying to understand how hooks are implemented and I think I figured it out, but it seems pretty complicated: If you've got 2 control points A and B (with B the successor of A) and you hook in a third control point C between them. What's actually done is that two new control points, D1 and D2, are created, with D1 registered to A as child hook and D2 to B. Then C is registered as successor of D1 and D2 as successor of C.

Why? I'm certain there's a reason for this, but why aren't hooks simply saved in a list at control point A?

Sorry if I'm tiring you with questions about the sources. If I do just tell me to shut up :D
Torf
 
Posts: 155
Joined: Mon Nov 08, 2004 8:45 pm
Location: Germany/Konstanz

Postby sascha » Sun Feb 26, 2006 8:42 pm

Your explaination is right.
Hereis an old and partly outdated documentation about the ControlPoint class.
It shows the basic idea behind hooks, but some things have changed in the meantime.
Both ends of the "hook curve" have their parentHook pointers pointing to, well, their parent-hooks on the regular curve. Only one (the first) point of the parent hook curve has its childHook pointer set.

There's a debugging tool included in JPatch called controlpoint-browser (accessible via the main menu). Select a single cp and open the menu-item. Here you'll see all the pointers to other ControlPoints, as seen from the currently selected one. You can jump to the other points, and "sync" will set the controlpoint-browser to the current selection again.

The "dump" menuitem is also helpful in this respect.

And finally there's a "check model" item - both dump their output to the console - whenever you suspect that something's wrong with the model, you can run "check model", if it prints an error it is the result of a bug, but the output may help to find the bug.

Ah, before I forget: You ask why I implemented hooks that way.
The answer is that the first version had no support for hooks, and I didn't want to touch the patch-finding algorithm when implementing them, so I looked for a way that did not alter existing patches when adding a hook (of course modifications were necessary to detect patches that had a hook as a corner).
At one point I wanted to rewrite the code and make hooks regular controlpoints with just a flag set, but this would make other parts more complicated:
The patch-finder had to be rewritten.
The code that computes the tangents had to be rewritten.
I think all in all a new implementation would be a slight improvement over the current one, but I don't think that its worth the effort. On the other hand there are many "edits" that have to take special care about hooks - I'll have to think about a different hooks implementation, and whether or not it would make things easier (I mean, hooks will always need special treatment, it's just a matter of how much).

If you like we could discuss the impacts of alternative designs and later decide if they justify a rewrite.

Sorry if I'm tiring you with questions about the sources.

To the contrary! If you've got a question about JPatch or the JPatch source, just ask!
sascha
Site Admin
 
Posts: 2792
Joined: Thu May 20, 2004 9:16 am
Location: Austria

Postby Torf » Mon Feb 27, 2006 8:05 pm

I've been going through the inner workings of AbstractClone again. And although I really like the design of the JPatch sources otherwhere, I must say that this hook implementation is awful :D It makes things so complicated, especially with cloning. My standard test "model" for bug hunting was as simple as possible - a curve between two points, with a hook in the middle, and the curved hooked in also only one segment long. Still the clone-tool fails to do its job correctly and there is code in AbstractClone.buildCloneMap which just does not make sense to me: The hook is not cloned because the curve which it (or, in fact, the point attached to the hook) is only one segment long. :?

I understand you not being all too cheerfull about changing the hook implementation. It would mean a major rewrite, because there's not much code in the modeler which would not be influenced by it.

The knife tool is also borked when working with hooks, because it simply cuts through all curves - even those hook-suplementary ones :( But that's probably a lot easier to fix than rewriting the hook handling.

A discussion can't harm, though. The problem with the current hook model is, IMHO, that there's too much ballast in it - if I create one hook I get 3 additional control points. Those have to be taken care of every time the hook is modified. The data structure seems to be too unflexible for this, too:

Create a curve from point A to B. Hook in another curve in the middle. Let the hook be point H1. so now A has a child hook who's successor is H1 and B has a child hook who's predecessor is H1, too. Fine. Now append a point C to the A-B curve and hook in another new curve between B and C (let us call this hook H2). You loose the reference from B to H1 because B's child hook now points to H2. Play the same game again, this time append a curve before point A and hook in another in the middle of the new segment. Now you've lost both references to H1. I don't know if that's bad (you can always get back from H1's neighbours to their parents), but it doesn't seem right.

The question is: What does one need to know about a hook and who has to know about it?
  • The control point itself should know that it's a hook. Needed for UI (e.g. a hook can't be moved) and other stuff
  • At least one of the points the hook is hooked into needs to know. Needed for e.g. patch calculation.
Additionally, a hook should know its parent and its hook position (to calculate its 3d position).

So what are possible structures? Here are two suggestions. Feel free to tear them apart :D
  • Hooks are inserted into another curve as any normal cp would be (as predecessors and successors). A hook knows that it's hook by a flag.

    Advantages: Patch computation should be pretty the same as now. Hook creation and deletion is trivial. A conversion hook<->control point is nothing more than toggling a flag.

    Disadvantages: Control point traversing which ignores hooks (e.g. curve drawing) has to be changed. One would need something like a ControlPoint.getNextNoneHook method (etc.). Not too much work though.
  • Each start point of a curve segment keeps a list of hooks attached to the segment. A control point knows whether it's a hook by a flag.

    Advantages: Hooks don't interfere with normal point traversal.

    Disadvantages: While you reduce the ballast (now new control points) and get rid off the reference problem (no hook references will be overwritten) the code itself won't probably get that much cleaner than with the current method.

There's more to it, of course. Both suggestions need some more details, like references from the hook to its parent. But I guess you get the idea. IMHO the second suggestions is nothing more than the current method with only minor improvements. The first suggestion, however, seems clear, uncomplicated and yet powerful enough to handle special cases.

My final suggestion is: We pick what seems to be the best way of handling hooks and I'll go and try it. By trying I don't mean fully converting JPatch to the new method, but rewriting some of the most important stuff - patch computations, edits, etc. That'll show us if the method is as good as we thought. And you can focus on integrating the animator, which shouldn't have to much to do with hooks (or so I think, I never actually looked at the code :wink:)
Torf
 
Posts: 155
Joined: Mon Nov 08, 2004 8:45 pm
Location: Germany/Konstanz

Postby sascha » Mon Feb 27, 2006 9:24 pm

I agree that the hook implementation is probably not optimal (to say the least)
It's also likely that there's a bug in AbstractClone (it was a try to reuse code by all cases that needed "cloning" - e.g. copy, lath and extrude).
It's been a long time, I'll have to dig into it again, but IIRC it's cloning the hooks in a second pass.

Create a curve from point A to B. Hook in another curve in the middle...

I'm afraid you've lost me here :)
Note that there's only one pointer from the parent curve to the hook curve, but two from the hook curve to the parent curve. In your case you've A -> B (the parent curve), and let's say C->D->E - where D is our hook. A's childHook points to C, C's parentHook to A and E's parentHook to B. If another hook would be added after B, B's childHook would point to the start of the hookcurve, the hookCurve CDE would be unaffected.

You've suggested two possible new ways to handle hooks. I don't think that the second suggestion (storing hooks in a list at what is now the parent hook) is an improvement. Sure, it would simplify the datastructures needed to store all necessary information, but there's more than that: You need to be able to find patches, the hook-curves must be able to compute their tangents (which is a simple decasteljau operation), and the curve attached to the hook also needs special treatment. I haven't really thought this through, but I think it would make some things easier while making other things more difficult.

The first suggestion (using just the regular curves, and just set a flag on hooks) looks more interesting. I already thought about that when I was refactoring the edits, but then decided against it.
I know that the current implementation makes many edits very intransparent and hard to debug, and in fact most of the bugs I found in JPatch were related to hooks - so I think that this rewrite would pay off.
But be aware that rewriting this isn't a small task, and there is no hurry. Before rewriting anything we should work out a clear concept and discuss every aspect of it to see where the pros and the cons are, and to decide whether it is worth the effort or not.

Things to keep in mind are: Patch finding, cloning, tangent calculation, removing/deleting points, file import/export (and maybe more).

Disadvantages: Control point traversing which ignores hooks (e.g. curve drawing) has to be changed.

Not really. Right now it doesn't paint hook curves, but with this design the drawing method could simply treat hook curves just like ordinary curves (after all, the are congruent).

PS: When touching the patch-finder we could also think about making it "adaptive" (e.g. when the user adds/removes a new controlpoint, automatically recompute new patches that could have been affected but that point).
sascha
Site Admin
 
Posts: 2792
Joined: Thu May 20, 2004 9:16 am
Location: Austria

Postby Torf » Tue Feb 28, 2006 7:10 pm

I guess we can safely drop my second suggestion and concentrate on the first one.

But be aware that rewriting this isn't a small task, and there is no hurry. Before rewriting anything we should work out a clear concept and discuss every aspect of it to see where the pros and the cons are, and to decide whether it is worth the effort or not.

Judging from what I've seen in the code it would be worth the effort, although I do see that it's a big task. I, too, see no hurry and prefer a clean solution to a quick 'n' dirty one - after all we're out to get the code cleaner.

Things to keep in mind are: Patch finding, cloning, tangent calculation, removing/deleting points, file import/export (and maybe more).

Ah, nice. Such a list of points of impact is always good to have.

Disadvantages: Control point traversing which ignores hooks (e.g. curve drawing) has to be changed.

Not really. Right now it doesn't paint hook curves, but with this design the drawing method could simply treat hook curves just like ordinary curves (after all, the are congruent).

After reading your answer on this I'm not sure if we're talking about the same implementation. Here's a more detailed explanation of the one I had in mind:

Without hooks, everything stays the same: Appending points to form curves, attaching points to connect curves.

To see what a hook changes, let's have a curve A->B. So here A.getNext() == B and B.getPrev() == A. Now let's add a second curve, C->D and hook C in the middle between A and B. Because C belongs to another curve, we first create a hook point on A->B, called D, so that we no have A->D->B. Because D is not a normal control point, its hook flag is set to true and its hook position is saved (in D). This could be combined: Hook position == -1 => no hook. Then C is attached to D as if D was a regular control point (so that C->getHead() will return D).

How does the other parts of the source now treat hooks?
  • To check if a point X is part of a hook, they check wheter X.isHook() || (X.getHead()!=null && X.getHead().isHook()) is true.
  • To get the next non-hook after a point Z they loop through its successors until they find one which hasn't got its hook flag enabled
  • The patch finder can treat hooks as normal control points. The drawing algorithm has to ignore them (but not their attached points), so that a curve is not drawn between a regular cp X and X.getNext(), but X and X.getNextNoneHook() (see above).
  • IMO a hook can calculate its tangent as any other control point would do. In fact, the tangent would not be calculated by the hook, but by the point attached to it, which is almost a normal cp. BTW, is the behaviour shown in the attachement desired? It certainly looks strange. Vanilla 0.5.2
  • Removing hooks does not need a special treatment: I think currently, if a cp is removed, all its attached points are removed, too. Right? The same applies to a hook. When a hook is removed, there will never be the situation that it's part of a curve which consists of only 2 points (and which would have to be removed, too), so no special care has to be taken here, as the normal test won't harm (for the point attached to a hook the test does make sense as with normal cps)
  • Cloning a hook is only needed if its "start" and "end" points (in case of the former A->D->B that would be A and B) and the point attached to it (in the former example that was C) are cloned. A possible strategy would be to first check which non-hook cps will be cloned and then add the hooks between them to the cloneMap
  • I have not looked into file import/export, yet. Normal JPatch file i/o shouldn't be a problem (I guess changing the file format is fine in beta state if it's necessary at all) and as a conversion from the current hook model to the suggested one seems to be not too hard I don't think we'll encounter many problems here
  • A conversion hook->cp would be simple, because (taking the names of the example again) only D's hook flag would've to be reset. Converting a control point into a hook would involve some more checks (not an endpoint, where to hook in, etc.) but that should be doable, too.
  • I don't know how the information flow from A,B to D is currently handled: What happens if A and B are moved? Is D's position (and therefore C's, too) recalculated instantly? I guess so, and I don't see a problem here, either: Just loop through the appended cps (A.getNext()) until you hit a non-hook one. For every hook one, get its hook-position, calculate its reference position and apply it to the point attached to the hook, too.
Of course many of the routines above could be encapsulated in proper methods, like
Code: Select all
boolean isPartOfHook() {
    return (isHook() || (cpHead!=null && cpHead.isHook());
}

ControlPoint getNextNoneHook() {
    if (cpNext == null) {
        return null;
    } else if (!cpNext.isHook()) {
        return cpNext;
    } else {
        return cpNext.getNextNoneHook();
    }
}


PS: When touching the patch-finder we could also think about making it "adaptive"

Sure. IMHO it would make sense to create a per-point patch finder, e.g. Patch[] computePatches(ControlPoint cp), and then use that to create a global patch finder, along the lines of
Code: Select all
void computePatches() {
    Map<ControlPoint> mapChecked = new Map<ControlPoint>();
    for (Iterator it=lstCPs.iterator(); it.hasNext(); ) {
        ControlPoint cp = (ControlPoint)it.next();
        if (mapChecked.contains(cp)) {
            continue;
        }
        Patches[] arrPatches = computePatches(cp);
        for (int a=0; a<arrPatches.length; a++) {
            Patch p = arrPatches[a];
            for (int b=0; b<p.arrCPs.length; b++) {
                mapChecked.insert(p.arrCPs[b]);
            }
            addPatch(p);
       }
}

(This one misses some stuff like the possibility of destroying invalid patches, but you get the idea).

Phew, pretty long post :) Seems I'm using every excuse not to learn for my differential equations exam...
Attachments
hook_peak.png
Why is the hook's curve segment straight?
hook_peak.png (1.08 KiB) Viewed 11158 times
Torf
 
Posts: 155
Joined: Mon Nov 08, 2004 8:45 pm
Location: Germany/Konstanz

Postby sascha » Tue Feb 28, 2006 8:21 pm

I don't have much time right now, I'll give you more detailed answers tomorrow. Just a few notes:

I'm not sure if we're talking about the same implementation. Here's a more detailed explanation of the one I had in mind:...

Yes, that's exactly what I meant :)

The patch finder can treat hooks as normal control points.

No. It would find the patches containing the hooks, but not the ajacent patch. It looks for neighbors, but in your case A->D->B (where D is a hook), not only A/D and D/B, but also A/B are neighbors - to not make it too easy, A/D/B is of course not a valid 3-point patch...
It can be done, but the patch-finder won't be less complex than it is now.

IMO a hook can calculate its tangent as any other control point would do

Yes sure - after all it calculates its tangent now too - what I was trying to say is that this code had to be adapted to the new design.

Removing hooks does not need a special treatment

Yes, but (for example) removing a regular point that is between two hooks does require special treatment.

I have not looked into file import/export, yet. Normal JPatch file i/o shouldn't be a problem (I guess changing the file format is fine in beta state if it's necessary at all)

The file format doesn't require any changes. Ironically the file-format already reflects this new design :)
What has to be changes is the code that imports/exports, but that would be quite straightforward.

A conversion hook->cp would be simple

Agreed.

I don't know how the information flow from A,B to D is currently handled: What happens if A and B are moved? Is D's position (and therefore C's, too) recalculated instantly?

No - earlier versions did a lot of caching, but it became more and more difficult to invalidate the cached values, so the current version doesn't cache any coordinates of controlpoints (what it does cache are the transformation matrices inside the bone hierarchy, but that's a different story).
Values that arn't immediately accessible are computed on the fly whenever they are needed (this includes all tangents and the positions of the hooks). The performance impact of not caching those values is IHMO marginal, and the code becomes much cleaner. Sometimes invalidating the cached values is more complicated than computing new values anyway...

IMHO it would make sense to create a per-point patch finder

Yes. JPatch already removes patches automatically (so there's no need to run the patchfinder when e.g. deleting a point). The only operation that can create new patches is a welding operation (when one point is attached or appended to anotherone) - and in this case it would be sufficient to tell the patchfinder to examine the point in question and see if it is part of new patches.

I think it would make sense to move this discussion into the Wiki, what do you think? At least after we've agreed on something we should put it to the wiki, finding things in the forum after a month or even a week can sometimes be difficult.

Ok, more tomorrow...

Seems I'm using every excuse not to learn for my differential equations exam...

Good luck!
sascha
Site Admin
 
Posts: 2792
Joined: Thu May 20, 2004 9:16 am
Location: Austria

Postby sascha » Wed Mar 01, 2006 10:36 am

MHO it would make sense to create a per-point patch finder, e.g. Patch[] computePatches(ControlPoint cp), and then use that to create a global patch finder, along the lines of...

I'm not sure. The current patch-finder seems to work well, and I think it's quite efficient too - the necessary modifications to support the new hook implementation IMHO wouldn't justify a complete rewrite.
I think it would be best to have an additional "per point" patchfinder. If the two share common code, this code can (and should) be moved into separete methods.

About the screenshot with the hook: It looks odd. It isn't a real problem because it disappears after the hook spline is attached to other splines (so that it can form a patch) and the hook tangent is the average of the two splines. Nevertheless this should be fixed.

I'll start a new wiki page with notes on the new hook implementation. It should be a "live" document, so feel free to change it. We can discuss about it here. A chat (IRC?) would also be nice, what do you think?
sascha
Site Admin
 
Posts: 2792
Joined: Thu May 20, 2004 9:16 am
Location: Austria

Postby sascha » Wed Mar 01, 2006 11:45 am

I've started a wiki page here.
sascha
Site Admin
 
Posts: 2792
Joined: Thu May 20, 2004 9:16 am
Location: Austria

Postby sascha » Wed Mar 01, 2006 2:54 pm

I'm not sure how we should handle the rewrite, but I've got an idea:
You suggested that you'd give the new hook implementation a try. I'm of course available if you have questions and I can also help and modify some classes myself, but as my time is rather limited these days I'd like to focus on the animator and the timeline.
I've never done this, but perhaps a CVS branch would be a good idea. During the rewrite of the hooks major parts of JPatch will not work properly, but with a branch we could both work on the hooks issues in one branch and I could continue working on the timeline in the other branch.
Once the new hooks work, we can join the branches again - as I think that I won't touch any classes relevant for the hooks implementation when working on the timeline, the join should be straight forward and without any collisions.
What do you think?
sascha
Site Admin
 
Posts: 2792
Joined: Thu May 20, 2004 9:16 am
Location: Austria

Postby sascha » Wed Mar 01, 2006 3:02 pm

Btw, I've been wrong about the xml file format - it needs to be changed. But to be backward compatible, the new xml-reader should also be able to parse files with the old syntax and "convert" the hooks to the new format.
sascha
Site Admin
 
Posts: 2792
Joined: Thu May 20, 2004 9:16 am
Location: Austria

Postby Torf » Wed Mar 01, 2006 6:15 pm

sascha wrote:
The patch finder can treat hooks as normal control points.

No. It would find the patches containing the hooks, but not the ajacent patch. It looks for neighbors, but in your case A->D->B (where D is a hook), not only A/D and D/B, but also A/B are neighbors - to not make it too easy, A/D/B is of course not a valid 3-point patch...

I don't think A and B would qualify as neighbours anymore after D has been hooked in - A and D, D and B are neighbours, A and B not anymore. That's one great benefit of the new solution IMO. Because A,D and B are on the same spline, checking A/D/B for a 3-point-patch would never happen.

removing a regular point that is between two hooks does require special treatment.

That's right. Right now, deleting a cp will also remove all hooks on curves going out from that cp. That behaviour should be easy to get with the new model, too. But perhaps one could even achieve a more conservative approach which would try to keep the hooks if the point is removed using BACKSPACE.

I've never done this, but perhaps a CVS branch would be a good idea.

Never done this, either, but it sounds like branches were developed for just such situations. It'll keep the changes clear and allow us to join the code later, as you mentioned. Definitely a good idea.

I'll start a new wiki page with notes on the new hook implementation. It should be a "live" document, so feel free to change it. We can discuss about it here. A chat (IRC?) would also be nice, what do you think?

The wiki page is nice. It'll prevent information from getting buried in the discussion. IRC is good, too, or perhaps ICQ. My ICQ# is 258914849. There are several IRC channels I'm in, but I guess creating a new one would be the best option. A popular server with open source seems to be Freenode (e.g. vinge.freenode.net).

My exam is in two weeks and since my learning motivation is still pretty low, university is on vacation and my girl-friend on the other side of the planet from friday, I'll hopefully have some time left :D

Some things I noticed while reading the wiki page:
To be “backward compatible” with other parts of the code, ControlPoint getNext() and ControlPoint getPrev() should be modified to return the next and previous non hook CPs, respectively.

Personally, I'd rather change the occurances of getNext()/getPrev() which need the next-none-hook cp to use getNextNoneHook()/getPrevNoneHook(). It's part of regarding hooks as regular cps most of the time. It also makes traversing code cleaner: You want to traverse all cps (incl. hooks)? Use getNext(). Traverse only regular cps? Use getNextNoneHook(). With a getNextHook(), traversing all cps (including hooks) would be ugly, because you'd had to check if getNextHook() returned null, then use getNext() instead, etc. One could also use getNextRegular() instead of getNextNoneHook(), which is a bit shorter.
Torf
 
Posts: 155
Joined: Mon Nov 08, 2004 8:45 pm
Location: Germany/Konstanz

Postby sascha » Wed Mar 01, 2006 8:42 pm

I don't think A and B would qualify as neighbours anymore after D has been hooked in

No, no - wait a minute :)
I'll try to be more precise: The patch finder (at least as it is implemented now) relies on neighbor information - If two points are neighbors, they form an edge - and four edges connecting form a 4 point patch. Look at the image below:
Image
It doesn't show all the attached controlpoints, I've only named one curve segment (A,B) with a hook on it (C). For patch X A and B are neighbors (like in the current implementation), for patch Y C and B are neighbors and for patch Z A and C are neighbors.
In other words, if we have a point A, both A.getNext() and A.getNextNonHook() would qualify as neighbors!
Thus, special care needs to be taken to not introduce invalid 3, 4 or 5- point patches composed of only one curve-segment and its hooks.

Personally, I'd rather change the occurances of getNext()/getPrev() which need the next-none-hook cp to use getNextNoneHook()/getPrevNoneHook().

Well, currently all methods that call getPrev() or getNext() expect non hooks. These methods are not only used for point traversal. One other use is e.g. to select curve segments. If you select a curve segment (TAB) what you want is selecting the whole segment, not the segment to the next hook.
Of course Eclipse's refactoring feature could be used - if you rename the current getNext() to getNextNonHook() all references will be updated, and you can then change the code to return the next non-hook.

ICQ sounds good - do you know Linux client?

One more note: I'd like to get rid of the 1/4, 1/2 and 3/4 position limits for hooks - there's no reason for this limitation. It would make sense to constrain the point where a hook can be set to these positions (perhaps relative to the next hook), but allow the user to move the hook along the curve later.
It's also required when transforming a hook into a regular CP. If the hook was on 1/4, but there are also points on 1/2 and 3/4 and you transform the 1/4 hook into a regular CP, the ohter hooks would end up on 1/3 and 2/3...
sascha
Site Admin
 
Posts: 2792
Joined: Thu May 20, 2004 9:16 am
Location: Austria

Postby Torf » Thu Mar 02, 2006 6:07 pm

sascha wrote:Look at the image below:

Ah, now I see what you mean. Yes, you're right. Basically, for a regular cp you need to check both getNext() and getNextNoneHook() (if they differ) and for a hook only getNext(). I wonder if the whole patch-finding could be made more elegant with help of some graph theory. I'll get out my books and do some reading about it.

Of course Eclipse's refactoring feature could be used

I wasn't going to do this by hand :)

BTW, Eclipse was such a help when I was trying to find my way around the JPatch sources - Especially jumping to the declaration (F3) and showing the references to a method/class in other parts of the code comes in so handy.

ICQ sounds good - do you know Linux client?

Most popular seems to be GAIM. Personally I'm more into IRC, so I use X-Chat in combination with Bitlbee, an ICQ-to-IRC gateway.

I'd like to get rid of the 1/4, 1/2 and 3/4 position limits for hooks

Good idea. Personally, I'd also like to be able to select a hook by clicking on it. Tools like cp<->hook conversion are just not practical if you can't select the hooks properly. Same goes for moving a hook on the curve. Therefore I suggest that hooks are displayed in the viewports, too. Of course their visual representation should distinguish them from normal cps. As usual this could be done with another color or shape. Because by now we've already got 4 colors of cps (normal, attached, multi-attached, selected), I'd go for a different shape. Perhaps something like an x.
Torf
 
Posts: 155
Joined: Mon Nov 08, 2004 8:45 pm
Location: Germany/Konstanz

Postby sascha » Fri Mar 03, 2006 3:33 pm

I wonder if the whole patch-finding could be made more elegant with help of some graph theory. I'll get out my books and do some reading about it.

Earlier implementations of the patch-finder had poor performance (N²) - but I think the current one has N performance. I doubt that you can get logN performance, because you do have to check every vertex.
But sure, if you find a better/faster/more elegant way to find loops in graphs, I won't stop you :)
It's just that it basically works (and it isn't that slow, is it?), so the time is perhaps better spent elsewhere - adapting the current algorithm to the new hooks code shouldn't be too hard...

I agree that the code could use some clean-up (some clean data-structures, and using the new 5.0 generics would also help a lot) - but I really can't imagine a faster algorithm. It simply creates a list of neighbors for each vertex, and then uses this list to find 3- or 5-point loops.
Before I started writing it I did some research on the internet concerning graph theory and detecting loops in graphs, but didn't find anything useful - so I came up with the algorithm as it is implemented now. Buf if there is a faster way, please let me know - I'm curious :)

Because by now we've already got 4 colors of cps (normal, attached, multi-attached, selected), I'd go for a different shape. Perhaps something like an x.

Yes, that was my earlier approach too (with yellow diamonds for the un-attached cps) - but when migrating to GL I abandoned the concept. Sure, GL can draw points, and polygons or lines as well, but the problems begin when using a perspective projection. A point in GL will always have the specified size in pixel - but when drawing a line or a polygon, they're subject to a perspective projection, and to get them e.g. exactly 5 pixels wide you'd have to compensate for the /z divide. To keep things simple we should only use GL Point primitives, but with different colors and/or sizes. Right now we have green, red, yellow and orange dots - what about blue? :wink:
sascha
Site Admin
 
Posts: 2792
Joined: Thu May 20, 2004 9:16 am
Location: Austria

Postby Torf » Fri Mar 03, 2006 4:57 pm

But sure, if you find a better/faster/more elegant way to find loops in graphs, I won't stop you :)
It's just that it basically works (and it isn't that slow, is it?), so the time is perhaps better spent elsewhere - adapting the current algorithm to the new hooks code shouldn't be too hard...

I guess you're right. Patch finding is a special situation: We only search for 3,4 and 5 cycles, and we have a undirected graph. So I guess cleaning up the old code while adapting it should be enough, just as you said (and I've never noticed speed issues with it anyway). I'm still thinking about how one could combine the adaptive and the global patch finder nicely. We'll see.

but I really can't imagine a faster algorithm.

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 :wink:

what about blue? :wink:

Didn't know about the GL issue. Blue's a nice color, though :) After all, the colors are modifiable by the user.

I'm away for the weekend, but I'm eager to start coding on this next week. Or is there anything about the concept that's not been discussed? Here's my plan for implementing the changes:
  1. Prepare the code (e.g. rename old methods, like getNext() -> getNextNoneHook())
  2. Implement the core functionality (Creation/Modification/Removal of hooks)
  3. Adapt other parts of the code (patch finder, file i/o, ...)

But first of all I have to read some docs about that CVS branching :)
Torf
 
Posts: 155
Joined: Mon Nov 08, 2004 8:45 pm
Location: Germany/Konstanz

Next

Return to Development

Who is online

Users browsing this forum: No registered users and 1 guest

cron