Nanakiwurkz

20th November 2006 23:08 UTC

I need help
I'm looking for methods to make a preset that makes a dot cube and makes a tracing line to a point on beat or getosc whatever. any suggestion on the engine would be greatly apreciated.

Nanakiwurkz

20th November 2006 23:13 UTC

err hem.
sorry.
I was wondering if it was possible to draw a random line thats still connected to the other to a point inside the cube. would megabufs be useful here?

MaTTFURY

21st November 2006 07:29 UTC

just draw a cube and set it to dots not lines, but dont ask me howto draw the actual cube.

Warrior of the Light

21st November 2006 09:23 UTC

define dot cube: just the corners? edges? planes? solid/filled?

Nanakiwurkz

21st November 2006 22:18 UTC

20x20 dot cube is what i'm looking for. but i know how to make the cube but i need to know how to make the lines have a synced kind of way to the points inside and out. rotates and again sorry for the lack of info.

jheriko

24th November 2006 16:07 UTC

Re: I need help
You need to be descriptive enough for us to know what you want. I would help you if you were.

Originally posted by Nanakiwurkz
... makes a tracing line to a point on beat or getosc whatever ...

Originally posted by Nanakiwurkz
... I was wondering if it was possible to draw a random line thats still connected to the other to a point inside the cube ...

Originally posted by Nanakiwurkz
... to know how to make the lines have a synced kind of way to the points inside and out. rotates and again sorry for the lack of info...

Nanakiwurkz

25th November 2006 01:06 UTC

yeah Jheriko i guess your right.
i my 3d drawings are better on paper then in avs or my mind.
i'll have a drawing ready for you guys soon. again again sorry

Nanakiwurkz

27th November 2006 23:26 UTC

here it is
alright this is not in 3d but it will give you and idea of what i was thinking about. heh.

PAK-9

28th November 2006 10:02 UTC

This sounds like it can be done without much trouble but it doesnt sound like it would make a very good preset

jheriko

28th November 2006 16:03 UTC

the way you have described it the preset will only run for a finite amount of time before needing to be reset.

A little warning, paths across grids always look simple, but there are sometimes extrememly difficult problems involved in using them. Not overlapping another line for instance is not trivial, especially if you want the lines to travel around the faces on the cube rather than jumping through the space in the middle. The "cheap" solution would be to pick a random point, do an intersection test with the existing path then if it intersects, pick another random point.

Not going over existing points is quite easy, there are two approaches to dealing with this. One is to randomly pick any point and repeat the choice if we hit a point we already have in our path.

The (better imo) way is to make an array representing the points in megabuf and decrease the size of the array, and the random number value for each point added to the path. e.g., lets say we have 26 points, which make a 3x3x3 cube surface. then if we label each point 0...25 we can choose one with a rand(26). in megabuf we make something like: megabuf(0) = 0 megabuf(1) = 1... megabuf(25) = 25. when picking a point we do l = rand(k) where k starts as 26, we then goto the lth position in megabuf and shift everything along up to k

megabuf(0)=0, megabuf(1)=1... megabuf(l-1) = megabuf(l-1), megabuf(l) = megabuf(l+1), megabuf(l+1) = megabuf(l+2)... megabuf(k-1) = megabuf(k).

if you draw this on a piece of paper or whatever you should see that this is the same as removing the element at gmegabuf(l) from the list. once this is done we decrease k by 1. this way the same point is never chosen twice since we remove it from the list of choices once picked.


To give you an idea of why the interesecting line test is hard I will step through a simple derivation

If we have a path p_0,p_1,p_2,...,p_n (where these p_i represent the x_i,y_i,z_i in one symbol - a vector) then when we add a point p_n+1 then we need to check if the line from p_n+1 to p_n intersects any of the other lines. a line intersection is the same as a pair of simultaneous equations using the equations of the lines. Using y=mx+c (which i hope to god they still teach in schools) we find for our first equation (using the x_n's)

y = (y_n+1 - y_n)/(x_n+1 - x_n) x + x_n

we then need to solve this against the equations of all the different lines in the path, for some line between p_m and p_m+1 we have

y = (y_m+1 - y_m)/(x_m+1 - x_m) x + x_m

which echoes the first equation. now, to solve simultaneously is quite easy since we already have the y ready for substitution

(y_m+1 - y_m)/(x_m+1 - x_m) x + x_m = (y_n+1 - y_n)/(x_n+1 - x_n) x + x_n

grouping like terms gives:
((y_m+1 - y_m)/(x_m+1 - x_m) - (y_n+1 - y_n)/(x_n+1 - x_n))x + x_m - x_n = 0

so x = (x_n - x_m) / ((y_m+1 - y_m)/(x_m+1 - x_m)-(y_n+1 - y_n)/(x_n+1 - x_n))

these divisions don't all have to be repeated, but you should at least be able to see that this works out as at least 1 division per line on the path, and at worst it works out as 3 (we can optimise so that none of these extra two are repeated, but they still need to be done at least once and stored somewhere for retrieval later)

now consider what happens as the path grows... unless we destroy the ends and keep the path short the path will just keep on growing in size, and the length of time required to check for an interesection will grow in size as well, which will decrease the frame rate.

so your idea is fine if we keep the path sufficiently small since this limits the number of divisons per frame to something finite, and also because it never uses all of the cube's points up in one path. There is still the problem of having to act on the result of the intersection test.

If the problem restricted to a 2d surface it becomes obvious that it is possible to trap the path so that it can never grow (consider the 3x3 square with the path going around the edge), also, if we just pick a random point each time the interesection test fails we need to not repeat the point we test (not hard but its annoying at this depth of program logic), we can also pick a lot of points before finding one that avoids an intersection. Consider a 9x9 grid with a 3x3 square in the middle with one line missing and a line from one end of the "U" shape into the middle point. Notice that about two-thirds of the points are unreachable without making an intersection, or an intermediary point. this is something like 50 points, which on a 9x9x9 cube becomes more like 300 points. Thats 300 possible intersection tests and array removals (the thing with numbers in the megabuf i showed near the top) for no end result. Its not guaranteed to happen, but its not unusual either.

Avoiding these sorts of problems is extremely difficult, this is why the units in your favourite RTS sometimes get lost or stuck, or take a silly long path from A to B when there is clearly a shorter one.


EDIT: I recently wrote something very loosely related, where I was creating paths through an n-dimensional lattice with a given start and end point and with the constraints that no two paths be identical and that no path go over its own lines (I allowed point intersections to create loops). Although I finished writing it and it gave the answers exactly as expected it suffered severely in that I had to limit the grid size to such small values as 8x8x8x8 just to be able to get a result in less than an hour. Now I know why physicists use supercomputers to calculate those things...

oh and btw, yet again, bored at work, so sorry if it went on for so long.. but it consumed a nice 30 mins of my time

Originally posted by PAK-9
This sounds like it can be done without much trouble

PAK-9

28th November 2006 18:59 UTC

tl;dr

I think you have massively overcomplicated what Nanakiwurkz was describing because you are bored at work and wanted to consume vast quantities of time with a wordy description :P

If you look at the picture it seems to me he just wants to draw a new line at x=rand(cols),y=y+1 every frame/time step. As you pointed out though, you can only do this <rows> times until you have to reset it.

I may be completely missing the point (this does, after all, seem like it would make a pretty terrible preset). I cant be bothered to read your post and discover what your interpretation is.

jheriko

28th November 2006 19:18 UTC

Without the lines crossing and randomly creating the path.

Those are the key bits.

Warrior of the Light

29th November 2006 18:41 UTC

lines?
The request was for one line only.

jheriko

30th November 2006 13:53 UTC

Originally posted by Warrior of the Light
lines?
The request was for one line only.