Jump to content
  • Advertisement
Sign in to follow this  
frob

Efficient representation of twists

This topic is 631 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm looking for a good data structure and set of twist addition/removal operations.

In a simulation I'm working on I need to represent twists in some cables.

There are an arbitrary but small number of cables, perhaps up to roughly 20 or 30. The bases of the cables are in a fixed order and will not move in space, but the tops of cables move around in 3D, potentially twisting with each other. 

Importantly, these are logical twists, and are NOT supposed to be physically accurate. I don't care about positions of the twists or distances along the cables, nor do I care if one twist slides up or down the the cable. Even though these examples show them twisted in space that is for communication only. On screen all the twists will end up meeting at a single point, but they need to untwist the right number of times.
P0pc6XO.png
I need a data structure that can efficiently handle adding and removing twists between the cables.  

I imagine I could store them in either order, but since they're accessible by index I could place them in a consistent order, like lowest is always first.  

The "simple twists" image could be created by adding a clockwise twist to black/green, and adding an anticlockwise twist to blue and red. I could untwist by adding an anticlockwise twist to black/green, and by adding a clockwise twist to blue/red.

In the "multiple twists" image, I can add multiple twists to a pair if they're the same direction.  If I added a clockwise turn it should remove the twist.

I should be able to cross multiple lines.  In the "simple twists" image, I should be able to have the green cable loop up and over the other cables, and as it moved in 3D passing the crossover points it would add a clockwise green/black, a clockwise green/red, and a clockwise green/blue to the collection of twists.

I would prefer to always consider it an addition.  Add a clockwise or add an anticlockwise, add both and the two should cancel out.  As the cables move in 3D I can test if they would cross each other, and in that case add an appropriate twist.

I will need a query to see how many twists any particular cable is involved in.

I will also need a query to detect all the cables in involved. The "no twists" would return four collections of one cable, the "simple twists" would return two collections each with two cables, the "multiple twists" would return three collections with one and two and one cables, and the "arbitrary twists" would return one collection with four cables.  

 

I think that's it. I'm not looking for a full implementation, just an idea to get this sorted out.
 
I've come up with some thoughts on my own that will work, but they all feel overly complex. I feel like there should be simple, elegant solution to this structure but I'm struggling to see it because I've been too close to the problem for too long.
Any helpful ideas?

Edited by frob
Formatting and clarity.

Share this post


Link to post
Share on other sites
Advertisement

As the cables move in 3D I can test if they would cross each other, and in that case add an appropriate twist.


This only makes sense to me if you're counting a "cross" as if projected in 2D somehow? Otherwise cables are either always twisting or never twisting if they aren't perfectly parallel.

I will need a query to see how many twists any particular cable is involved in.


Since I don't really have a good idea of what your insertion/removal/etc operations will be, the simplest thing I can think of is a vector of tuples: (cable1, cable2) where cable1 goes over cable2 (clockwise twist). (cable2, cable1) would be cable1 going under cable2 (anticlockwise).

It doesn't really make sense to me that you would be able to insert a twist in the middle of the vector, so you'll probably be push_backing everything. Might as well stick with a vector then.

I wouldn't bother trying to keep the isolated twists separate until they merge. "Merge" operations can be a hassle. Just keep everything in one vector.

Counting them would just be a linear pass that just tallies them all up (linear time for the loop, constant time for each increment operation assuming you can use constant-lookup for each cable into a map or array).
 

I will also need a query to detect all the cables in involved. The "no twists" would return four collections of one cable, the "simple twists" would return two collections each with two cables, the "multiple twists" would return three collections with one and two and one cables, and the "arbitrary twists" would return one collection with four cables.


This sounds similar to: https://en.wikipedia.org/wiki/Strongly_connected_component

There are some good linear time algorithms for that listed on the wiki page.

... Although, I guess your twists are more like an undirected graph. In which case you'll want a https://en.wikipedia.org/wiki/Disjoint-set_data_structure based algorithm, and treat cables as disjoint sets that you merge whenever they twist.


Found another thing that I hadn't seen before that might be applicable here:

https://en.wikipedia.org/wiki/Dynamic_connectivity Edited by Nypyren

Share this post


Link to post
Share on other sites

You're talking about braid groups right? Doesn't the standard presentation basically do what you want? For n cables:

https://en.wikipedia.org/wiki/Braid_group

G = <x1, ..., x(n-1) | xi+xj = xj+xi (|i - j| > 1 or i = j), xi+x(i+1)+xi = x(i+1)+xi+x(i+1) (0 < i < n-1)>

x2 means cable 2 goes under cable 3. x2 + x3 means cable 2 goes under cable 3 then cable 3 (which used to be cable 2) goes under cable 4. -x2 means cable 2 goes OVER cable 3. So x2 - x2 = 0. See below:

http://imgur.com/a/ix6YP

 

This numbering is different than yours, watch out for that. Below I encode your examples:

 

No twists:

0

 

Simple twist:

x1 - x3

= -x3 + x1

 

Multiple twist:

-x2 - x2 - x2

 

Arbitrary twists:

x1 + x2 - x3 + x2 + x1 + x3

= x1 + x2 - x3 + x2 + x3 + x1

 

Note: x2 - x3 + x2 != -x3 + x2 - x3.

 

Store the list of numbers (1, 2, -3, 2, 1, -3). It is exactly addition (in a group), when you see the same number and its inverse you just delete both. You can use the relations to rearrange and try to simplify the equation. E.g. ...

-x2 + x1 + x2 + x1 - x2 - x1

= -x2 + x2 + x1 + x2 - x2 - x1

= 0

 

See the other image in that imgur

 

To query how many twists a particular cable is involved in, you read the string from left to right, keeping track of which position the cable is in, and incrementing by 1 every time it is involved in a twist.

 

Or, since you always add twists at one end, do the computations to update the twists-per-cable counts every time you add a twist, and never recompute from the beginning.

 

To group the cables into components, where everything in a component is twisted together (transitively), read from left to right and keep track. Again, you can probably update this computation in real time if you prefer.

 

It's probably not very satisfying that you can get multiple representations for the same braid, even for the trivial braid, but that's fundamental to the problem. Maybe look into computations with the braid group?

Edited by EqualityAssignment

Share this post


Link to post
Share on other sites

This only makes sense to me if you're counting a "cross" as if projected in 2D somehow? Otherwise cables are either always twisting or never twisting if they aren't perfectly parallel.

They're able to move, like fish on the end of fishing lines, or kites on strings, or dogs on tied-off leashes.

They cross when -- as viewed from the base of the cable or the twist point -- they pass over a left/right boundary and then an up/down boundary, gaining either a clockwise twist or anticlockwise twist.

Since I don't really have a good idea of what your insertion/removal/etc operations will be, the simplest thing I can think of is a vector of tuples: (cable1, cable2) where cable1 goes over cable2 (clockwise twist). (cable2, cable1) would be cable1 going under cable2 (anticlockwise).
 

I suppose I should have offered up the solutions we've explored so far.

 

Initial "this can't be right" thought:

At first was a collection of twist tuples, {A, B, dir}.  When a twist is added, scan the collection for the {A, B} pair and if dir matches add another twist tuple, if dir is different remove the found tuple.  The problem is unbounded growth. 

Computing the count of twists means scanning the collection of tuples and counting the matches in A or in B. Linear search based on the number of elements.

Computing the set of cables involved in each cluster of twists can be nasty but shouldn't be too bad in small numbers. Put a cable into the first collection and scan the table. Any cable that twists with it gets added to the collection and queued for scanning. Repeat until no new cables are added. Add the next non-added cable to the next collection and scan it for twists, adding as above. Repeat until all cables have been scanned. Gives N*M, each cable scans the each twist in the array once. 

That potentially gets some horribly nasty growth as the number of twists grows, and soon we're no longer talking about nanoseconds for processing. As twists increase the problems rapidly grow. Design suggested adding a warning with a high number of twists like making cables start to blink and flash, and then calling it "broken" counting the game as a loss or something, but it wasn't satisfying.

 

After posting, someone (sadly not me, as I've been working on this too long) had an idea of a single element per pair with a count of accumulated twists, {A, B, sum}.  Adding a clockwise twist increases the sum, adding an anticlockwise twist decreases the sum. With 30 cables the worst case is 870 elements, which is tolerable. 

That still leaves us with a linear scan to compute the number of twists but we can add abs(sum) for the total. It also leaves the N*M for collections of twisted cables. With 30 cables, that's 26100 tests to build the group of collections, and it could probably be cached and only marked as dirty if a twist is added and then recalculated when eventually requested, probably the next frame.  That's not horrible, but still feels too high to me.

Share this post


Link to post
Share on other sites

You're talking about braid groups right? Doesn't the standard presentation basically do what you want?

Looking it over, that's probably exactly the set of math behind it, although some of the actions inside the description don't feel like they match the problem, at least not intuitively.  

I don't think that set of math makes the two queries any easier, though, I think they're still the same linear and N*M operations, unless there is something buried in braid group theory that makes them faster.

Edited by frob
Quoting text is hard when brain is fried. Probably time to be done for today.

Share this post


Link to post
Share on other sites

I agree. It doesn't help you answer those queries afaik.

 

But clumping cables by twist shouldn't be on the order of #cables*#twists should it? Assign every cable a color, then for each twist, if the cables have different colors (red, blue), pick one (red), then for every cable if its color is red make it blue. Iterate until no more twists. Each time you replace a color like that, the number of colors falls by 1. When it hits 1, you know every cable is together and you early-out. At the end you arrange the cables into lists by color.

 

So you can never iterate all the cables more than (#cables - 1) times. Because for each twist, either the cables are the same color and you don't iterate all the cables, or they are different colors and that can only happen (#cables - 1) times.

 

That's #twists + #cables^2 + some #cables terms for set-up and tear-down right? If #twists is the problem that should be fine?

Edited by EqualityAssignment

Share this post


Link to post
Share on other sites

Doing some more math and tracking them from the same perspective I was considering before, it boils out be the same. Their operation of ?1?2?1 = ?2?1?2 gives me the pairwise result of  {A,B,1} {A,C,1} {B,C,1}, and a few of the other operations also boil down to the same results when taken pairwise, the only difference is referencing them based on their cable letter rather than the index at the time of twist.  Since the game objects in the world will be tracked by the cable their attached to, it seems that would be the more natural approach for this.

The Wikipedia articles suggest the most compact representation is the "Lawrence–Krammer representation", taking (n(n-1))/2 square matrices, for 30 with each a pair, that works out to be the same as the all-pairs collection, so at least we happened upon the tightest representation.

I'm still not seeing anything useful for improving the two key operations of twist count or the sets that are braided together. ... but looking at the dates of the papers on braid theory, most within the last 60 years, this stupid little problem could become a published math paper if someone was bothered enough to write it up. :-)

 

 

When it hits 1, you know every cable is together and you early-out.

Yes, there are several early-out possibilities. If a cable is already included you don't need to test anything against it. But for such a small number, the cost of making special-case loop hopping probably is about the same cost as the cache-friendly linear scan.  With a structure of { byte, byte, short } or even {byte byte byte} it suggests some SIMD operations could make short work of the 26100 worst case.

Edited by frob

Share this post


Link to post
Share on other sites

After several more hours of research, and discovering there really isn't much depth to the young field of braid theory, I realized this encoding may be entirely novel, at least as far as research papers go.

I think (but haven't done that type of proof since grad school decades ago) it provides a unique, guaranteed minimal-twist encoding, which looks both shorter and easier than the normalization encoding you mentioned and the literature I could find also mentions.  There is no extra work involved since the minimal form is naturally accumulated when spanning the range. The only real change is that instead of consider operations by row you instead consider them based on the ID of the two lines that twisted.

Anybody looking for some low-hanging fruit for their math degree?

Share this post


Link to post
Share on other sites

First, in your blog post, "Multiple twists: {0, 0, 0, -2, 0, 0}" should be "Multiple twists: {0, 0, 0, -3, 0, 0}" shouldn't it?

More importantly, I think your normal form isn't right. Let there be three cables, red, green, and blue. Then we have an a length three twist array: {green-red, blue-red, blue-green}. I can make two different braids that both have twist array {2, 0, 2}, but they are not the same. In particular, if you add the same sequence of extra twists to the end, one of them untwists all the way and the other gets twistier. I think that is gonna be a problem for you?

Images here:

http://imgur.com/a/IDcls

x1+x1+x2+x2 and x2+x2+x1+x1. If I understand your idea right, you would call them both {2,0,2}. If you add (-x2-x2-x1-x1) to the end, then only one of them becomes the trivial braid, both you would call both {0,0,0}. I think that will cause problems for you?

The normal form defined in that paper doesn't look too much like yours to me. As exhibited above, even the positive word component can't be reduced to {*, *, *} form. That's equivalent to assuming commutativity for twist-addition I think, and commutativity fails.

I agree that your twist-array is a braid-invariant, but not a complete one. If the braids are the same they have the same twist-array, but if the twist-arrays are the same that doesn't mean the braids are. You basically proved that in your blog post. The set of twist-arrays has group structure with elementwise addition. The mapping from braid to twist-array is a group homomorphism. You proved this yourself, by showing that the sum of the twist-arrays of two braids is the twist-array of their concatenation, and by showing that the relations xi+xj=xj+xi (if not adjacent) and xi+x(i+1)+xi=x(i+1)+xi+x(i+1) hold for the twist-arrays too.

In the paper they use a braid invariant called exp which just counts twists (-1 for one way, +1 for the other), the twist-array is a stronger version of that invariant that counts twists for each pair of cables individually.

The normal form they define in the paper expresses every braid as the concatenation of a power of one of the "Garside braids" and a "positive braid", in which every crossing goes in the same direction (CW or CCW). If I am reading the paper right, the Garside braids themselves are positive braids, and in the normal form, the Garside braid always has power <= 0. Basically if you have B = delta^k * T with B a braid, delta a Garside braid, and T a positive word, you can always do B = delta^k * delta^(-1) * delta * T = delta^(k-1) * T' with T' = delta * T a new (larger) positive word. So you can always make the power on delta smaller, but it is bounded above. (Sorry, I just switched from additive to multiplicative notation.)

(Finally, The Sage mathematics package can draw braids nicely ... so no more gimp for me :). It's a pain to install though so that doesn't help you.)

I guess this still doesn't help you solve your problem. Good discussion though, thanks for bringing this up.

Edited by EqualityAssignment

Share this post


Link to post
Share on other sites

Multiple twists: {0, 0, 0, -2, 0, 0}" should be "Multiple twists: {0, 0, 0, -3, 0, 0}

Good eyes. That's three full rotations in my crappy hand drawing. Updating.

x1+x1+x2+x2 and x2+x2+x1+x1. If I understand your idea right, you would call them both {2,0,2}. If you add (-x2-x2-x1-x1) to the end, then only one of them becomes the trivial braid, both you would call both {0,0,0}. I think that will cause problems for you? ... twist-array is a braid-invariant, but not a complete one ...  they use a braid invariant called exp which...

It's been many, many years since my last class on topology (and I wouldn't care to repeat it), but I understand your comment about being braid-invariant but not complete is rather important. That's the part I don't really have the time or patience for in this math.  My understanding of reading that is that the core question is about the end conditions, and if a specific line can be pulled out or not.
I think that's where the notation difference becomes important. Their notation is about the row of the twist without regard of the line they are on. My notation was about the twists between individual lines without regard to which row they are in.
If you're counting the rank of the twist, this one happens relative to rank 1, that one in rank 2, another in rank 7, then they are not commutative because each change also changes the lines that are involved.  A twist on x2 one time happens to change red and green. A twist on x2 another time happens to change black and red.  Later a twist in x7 could also involve red and green. It appears that ordering is only important because they are operating on the rank of the twist, not operating on the lines of the twist. There might be other reasons in their theory, but I don't see them.
If we are working with the lines instead of the rank then (I believe) they are completely commutative. A swap of the red and black lines is the same no matter what rank they happen to be in at the time. There might be something more in their branch of math that causes that to be not true in the general case.

The normal form they define in the paper expresses every braid as the concatenation of a power of one of the "Garside braids" and a "positive braid", in which every crossing goes in the same direction (CW or CCW).


That part was a little trickier for me in the papers.  You can change the notation in a pair by reversing the order.  {Green Black +1} is equivalent to {Black Green -1}. For reasons of convenience I'd prefer them in consistent ordering by cable (e.g. operator less()) , rather than consistent ordering by direction (e.g. always positive).
I don't think that part makes a difference. I dislike their normal form because it focuses on something that is irrelevant to me. Which leads to the core of my problem, which I think is now fully resolved.
In my specific problem, I'm trying to control a few things:

  • Is the line involved in ANY twists? If no twists I can operate directly.
  • If there are twists I need to establish a knot point. Doing that means I need to know ALL the lines involved in the twists. If I have a knot involving the tethering cables holding objects A, C, and F are involved in a twist, then I need the knot to slide to their central point between the lines, which will be the midpoint between the three.
  • If an object can escape from the knot it needs to be able to do so immediately.

So in my specific problem we assume the lines can slip and slide freely because they are slippery and constantly being tugged. Ordering of the twists are irrelevant. Even if there are ten other line twists mixed among them, if a red line looped clockwise over the black line once, then there were a bunch of other twists involved that included the red line, then the red line eventually looped anticlockwise over the black line, no matter what other twists were involved with the red line, if that was the only involvement with the black line then the black line would be free of the braid.  
If red was twisted with green, green with yellow, yellow with pink, and pink with black, it would still be linked to the braid, but if black could get a corresponding un-twist for each, it would be free and could leave.  
An unexpected aspect that doesn't fit well with what I was reading is a simple physical problem.  Suppose I had three of them floating in a cluster, arbitrarily choosing A, C and F because I've mentioned those before, then another one (J) floats around them in a circle, it ends up adding a twist with each line individually as at passes.  Wrapping around causes a twist between AJ, CJ, and FJ. No matter what other twisting A, C, and F do, each one can perform an anti-twist with J and because they can slip freely, J becomes free.
I'm not absolutely sure physically if that works out exactly the same, and and that's where the question remains.  If A, C, and F have their own individual twists with J wrapped once around the bundle, would an anti-twist of AJ always free that pair? No matter the other twists, would CJ and FJ anti-twists free those pairs?  When I run it on paper myself I can always free the line, and that's why I think it works out. But I don't want to do the number crunching to prove it.

So as far as my problem set is concerned, I *THINK* it solves all the issues.  Physically it may be awkward to slip through an enormous pile of knot twists, but logically it seems that they could slide freely and the lines would escape the knot regardless of the topology of the other knots.

If that works out, I think it would be a useful alternate normal form, since it seems (I will readily admit to error) that the pairwise representation encodes the final twist state of all cables. If order doesn't matter -- and I don't think it does due to the examples they give of x1-x2-x1- being equivalent to x2-x1-x2-, then a strict weak ordering of pairs (like the < operator) would give a self-normalizing form. The papers discuss manual steps to find the shortest form in order to establish the normal form, but I don't think that is necessary. The papers also involve heavy math steps walking through the entire twist chain to see if a line becomes free of the braid, but I don't think that's necessary either with this encoding.
But as I wrote, it has been a long time since my math classes and there are probably more nuanced details that I am overlooking or not understanding.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!