Dark Bit Factory & Gravity
PROGRAMMING => General coding questions => Topic started by: Pixel_Outlaw on December 30, 2007
-
EDIT: I just realized that the algorithm is working but it WILL NOT allow for loops in shapes. I guess this is my main problem.
I was just killing some time and decided to try splines via division. Now according to wikipedia (which is known to be a faulty source of information) one can construct a curve via subdivision. Now I think I have gotten the algorithm down. First you take your lines and find the midpoint. You then add the old initial first and last points to the new set. The funny thing is that a spline IS produced but it eventually collapses back into a 3 point spline no matter how many initial hulls you have.
Some pics and the program. (Hit space bar to go one more iteration, hit n to get a new set of random points)\
The first picture demonstrates the control points, the second is an iteration some time later.
source' attempt at subdivision algorithm for splines
Strict
SeedRnd(MilliSecs())
Global points:point[]
Type point
Field x:Float, y:Float
End Type
Function midpoint:point(a:point, b:point)
Local p:point = New point
p.x = (a.x + b.x) / 2.0
p.y = (a.y + b.y) / 2.0
Return p
End Function
Function add_point:point[] (p:point, a:point[] )
Local i:Int = a.Length
a = a[..i + 1]
a[i] = p
Return a
EndFunction
Function divide()
' save the first and last points
Local start:point = New point
start = points[0]
Local eEnd:point = New point
eEnd = points[points.length - 1]
Local temp_array:point[] ' one point longer than the old array
' add first point
temp_array = add_point(start, temp_array)
' find new midpoints and add them to temp array
For Local i = 0 To points.Length - 2
Local n:point = midpoint(points[i] , points[i + 1] )
temp_array = add_point(n, temp_array)
Next
temp_array = add_point(eEnd, temp_array)
points = temp_array
End Function
Function draw()
For Local i = 0 To points.Length - 2
DrawLine(points[i].x, points[i].y, points[i + 1].x, points[i + 1].y)
Next
End Function
' seed the points
Function seed()
For Local i = 0 To 6
Local p:point = New point
p.x = Rand(640)
p.y = Rand(480)
points = add_point(p, points)
Next
EndFunction
seed()
Graphics(640, 480)
While Not KeyDown(KEY_ESCAPE)
If KeyHit(KEY_SPACE)
If points.length < 180
divide()
EndIf
End If
If KeyHit(KEY_N)
Cls
points = Null
seed()
End If
'draw point count
SetColor 0, 0, 0
DrawRect(0, 0, 128, 24)
SetColor 255, 255, 255
DrawText("Points: " + points.Length, 2, 2)
SetColor((255 * (Float(points.Length) / 180)), 255 - (255 * (Float(points.Length) / 180)), 255 * (Float(points.Length) / 180))
draw()
Flip
WEnd
-
This might be useful:
http://syn9.thingie.net/?table=simple_spline
-
That is an interesting approach. I'm going to try this tomorrow when I get up. Thanks relsoft. Have some "Instant Karma".
-
Ok it works great. We have a winner.
source if anyone wants.
' attempt at subdivision algorithem for splines
Strict
SeedRnd(MilliSecs())
Global points:point[]
Type point
Field x:Float, y:Float
End Type
Function midpoint:point(a:point, b:point, percent:Float)
Local p:point = New point
Local length:Float = Sqr(((a.x - b.x) * (a.x - b.x)) + ((a.y - b.y) * (a.y - b.y))) * percent
Local direction:Float = point_direction(a.x, a.y, b.x, b.y)
p.x = a.x + Cos(direction) * length
p.y = a.y + Sin(direction) * length
Return p
End Function
Function point_direction:Float(x1:Float, y1:Float, x2:Float, y2:Float)
Local direction#= ATan2(y1-y2,x1-x2)+180
While direction > 360
direction:-180
Wend
While direction<0
direction:+180
Wend
Return direction
EndFunction
Function add_point:point[] (p:point, a:point[] )
Local i:Int = a.Length
a = a[..i + 1]
a[i] = p
Return a
EndFunction
Function divide()
' save the first and last points
Local start:point = New point
start = points[0]
Local eEnd:point = New point
eEnd = points[points.length - 1]
Local temp_array:point[] ' one point longer than the old array
' add first point
temp_array = add_point(start, temp_array)
' find new midpoints and add them to temp array
For Local i = 0 To points.Length - 2
Local n:point = midpoint(points[i] , points[i + 1] , .25)
temp_array = add_point(n, temp_array)
n = midpoint(points[i] , points[i + 1] , .75)
temp_array = add_point(n, temp_array)
Next
temp_array = add_point(eEnd, temp_array)
points = temp_array
End Function
Function draw()
For Local i = 0 To points.Length - 2
DrawLine(points[i].x, points[i].y, points[i + 1].x, points[i + 1].y)
Next
End Function
' seed the points
Function seed()
For Local i = 0 To 25
Local p:point = New point
p.x = Rand(640)
p.y = Rand(480)
points = add_point(p, points)
Next
EndFunction
seed()
Graphics(640, 480)
While Not KeyDown(KEY_ESCAPE)
If KeyHit(KEY_SPACE)
divide()
End If
If KeyHit(KEY_N)
Cls
points = Null
seed()
End If
'draw point count
SetColor 0, 0, 0
DrawRect(0, 0, 128, 24)
SetColor 255, 255 * (Float(points.Length) / 360.0), 255-(255 * (Float(points.Length) / 180.0))
DrawText("Points: " + points.Length, 2, 2)
draw()
Flip
WEnd
A pic:
-
Nice, have some karma for sharing :)
-
I've taken some time to study this curve and it is really great for me. First off the curve formed has multiple control points that the curve passes through. They are not on the verticies, but instead lie at the midpoint of each original segment. The second great feature is that the spline remains confined within the hulls formed. This particular spline seems better for motion than the Bezier Spline for it has more than two control points and also superior to the Cardinal Spline for the spline is contained within the hulls of the initial shape.
These new splines should be powerful in motion planning. The movement will be contained within the initial shape and also has control points in the form of midpoints for the initial segments. Might work neat for camera work or that "toothpaste laser" in the early Raiden games. I'm thinking a homing laser in the next shmup, something that can go through 20 enemies at once.
I've got the code working faster than ever now and will soon post an updated version including support for closed polygons.
-
Cool stuff, I'd been looking into cubic interpolation but I can see the advantages of having the points within the initial shape.
K+
-
Just finished the closed algorithem. The first point should be the same as the last now. I've moved away from the crumby vector method of calculating the sub points, improving division speed by a whopping 50%.
Here is the source:
' attempt at subdivision algorithem for splines
Strict
SeedRnd(MilliSecs())
' set up an array for our point objects
Global points:point[]
' toggle variable for closed or open shapes
Global closed:Int = 0
' a point datastructure holding x and y
Type point
Field x:Float, y:Float
End Type
' return a point at a percent between both points
Function midpoint:point(a:point, b:point, percent:Float)
Local p:point = New point
p.x = a.x + ((b.x - a.x) * percent)
p.y = a.y + ((b.y - a.y) * percent)
Return p
End Function
' return a list with a point added
Function add_point:point[] (p:point, a:point[] )
Local i:Int = a.Length
a = a[..i + 1]
a[i] = p
Return a
EndFunction
' used to divide a curve
Function divide()
' save the first and last points
Local start:point = New point
start = points[0]
Local eEnd:point = New point
eEnd = points[points.length - 1]
Local temp_array:point[] ' one point longer than the old array
' add first point
temp_array = add_point(start, temp_array)
' find new midpoints and add them to temp array
For Local i = 0 To points.Length - 2
Local n:point = midpoint(points[i] , points[i + 1] , .25)
temp_array = add_point(n, temp_array)
n = midpoint(points[i] , points[i + 1] , .75)
temp_array = add_point(n, temp_array)
Next
temp_array = add_point(eEnd, temp_array)
points = temp_array
End Function
' used to divide a CLOSED curve
Function divide_loop()
' save the first and last points
Local eEnd:point = New point
eEnd = midpoint(points[points.length - 1] , points[points.length - 2] , .25)
Local temp_array:point[] ' one point longer than the old array
' add first point
' find new midpoints and add them to temp array
temp_array = add_point(eEnd, temp_array)
For Local i = 0 To points.Length - 2
Local n:point = midpoint(points[i] , points[i + 1] , .25)
temp_array = add_point(n, temp_array)
n = midpoint(points[i] , points[i + 1] , .75)
temp_array = add_point(n, temp_array)
Next
points = temp_array
End Function
' draw all segments in the curve array
Function draw()
For Local i = 0 To points.Length - 2
DrawLine(points[i].x, points[i].y, points[i + 1].x, points[i + 1].y)
Next
DrawOval(points[0].x - 2, points[0].y - 2, 4, 4)
DrawOval(points[points.length - 1].x - 2, points[points.length - 1].y - 2, 4, 4)
End Function
' seed the points
Function seed()
Local a:point = New point
a.x = 320
a.y = 384
points = add_point(a, points)
Local b:point = New point
b.x = 208
b.y = 256
points = add_point(b, points)
Local c:point = New point
c.x = 208
c.y = 160
points = add_point(c, points)
Local d:point = New point
d.x = 304
d.y = 160
points = add_point(d, points)
Local e:point = New point
e.x = 320
e.y = 192+32
points = add_point(e, points)
Local f:point = New point
f.x = 336
f.y = 160
points = add_point(f, points)
Local g:point = New point
g.x = 432
g.y = 160
points = add_point(g, points)
Local h:point = New point
h.x = 432
h.y = 256
points = add_point(h, points)
Local i:point = New point
i.x = 320
i.y = 384
points = add_point(i, points)
EndFunction
seed()
Graphics(640, 480)
While Not KeyDown(KEY_ESCAPE)
If KeyHit(KEY_SPACE)
If closed
divide_loop()
Else
divide()
EndIf
End If
If KeyHit(KEY_N)
Cls
points = Null
seed()
End If
If KeyHit(KEY_C)
Cls
closed = True
points = Null
seed()
End If
If KeyHit(KEY_O)
Cls
closed = False
points = Null
seed()
End If
'draw point count
SetColor 0, 0, 0
DrawRect(0, 0, 640, 24)
SetColor 255, 255 * (Float(points.Length) / 360.0), 255-(255 * (Float(points.Length) / 180.0))
DrawText("Points: " + points.Length + " O-Open Polyline" + " C-Closed Polyline", 2, 2)
draw()
Flip
WEnd
A cute little heart shape closed inside a ridged frame.
-
If you can avoid calling New Point inside the midpoint subdivision, I suspect it will go much faster again.
Jim
-
Midpoint?
Can you use this formula?
midx = (bx+ax)/2
midy = (by+ay)/2
-
Midpoint?
Can you use this formula?
midx = (bx+ax)/2
midy = (by+ay)/2
Well my midpoint function is misleading. Originally I used that midpoint function and it produced horrible results. Instead I adopted the algo you linked to.