Omnimaga
Calculator Community => TI Calculators => Axe => Topic started by: pimathbrainiac on April 17, 2013, 10:15:53 pm
-
Line clipping? I thought that that is a problem being worked on by Runer112 for future versions?
Well, yes, but here's a temporary fix, using trig!
To all those who may spot any error in my trig: please tell me. I'll try to fix it.
Inspiration:
I saw god's (leafy's) Super Hexagon port, and I saw a problem that he listed: The line clipping. I thought to myself: how do I solve this? The answer is by using trig!
Just to show you I'm not crazy: here are some screenies for a very incomplete Super Hexagon engine (I will not continue after this point because I just made it to solve a problem):
(http://img.removedfromgame.com/imgs/Line_Wrapping_Fix.gif)
Axe trig background:
Trig in Axe is not standard to the trig you learned in school. There are no degrees or radians. There are only sine and cosine functions (of which all normal functions can be derived from). The period of these functions is 256, and the amplitude 128 (signed).
To get a sine of an angle (0-255, not 0-359), it is simply sin(angle)//127 (make sure it is // and not /, due to the output being signed). The same works with cosine.
Since my super hexagon engine is done in polar coordinates, it is easier with this case, but there is only one more step with using
Now: here's some code before I explain how to do stuff (copied from graph-link):
.HEXAGON
ExprOn
For(A,0,7)
0ü{A+L}
End
64ü{1+L}
128ü{3+L}
192ü{5+L}
0ü{7+L}
0üXüAüBüCüD
1üF
2üE
65435üW
43üO
0üR
0üGüHüIüJüKüLüMüN
Repeat (getKey(15))
D+EüD
8*(getKey(3)-getKey(2))üC
X+CüX
If (Xùú8)
248üX
ElseIf (Xù255)
0üX
End
If (Dùú2)
254üD
F++
sub(A)
ElseIf (Dù255)
0üD
F++
sub(A)
End
10*cos(X+D)üA
10*sin(X+D)üB
ClrDraw
Pxl-On(47+(A//128),31+(B//128))
Line((7*cos(0*O+D))//128+47,(7*sin(0*O+D))//128+31,(7*cos(1*O+D))//128+47,(7*sin(1*O+D))//128+31)
Line((7*cos(1*O+D))//128+47,(7*sin(1*O+D))//128+31,(7*cos(2*O+D))//128+47,(7*sin(2*O+D))//128+31)
Line((7*cos(2*O+D))//128+47,(7*sin(2*O+D))//128+31,(7*cos(3*O+D))//128+47,(7*sin(3*O+D))//128+31)
Line((7*cos(3*O+D))//128+47,(7*sin(3*O+D))//128+31,(7*cos(4*O+D))//128+47,(7*sin(4*O+D))//128+31)
Line((7*cos(4*O+D))//128+47,(7*sin(4*O+D))//128+31,(7*cos(5*O+D))//128+47,(7*sin(5*O+D))//128+31)
Line((7*cos(5*O+D))//128+47,(7*sin(5*O+D))//128+31,(7*cos(0*O+D))//128+47,(7*sin(0*O+D))//128+31)
sub(B)
DispGraph
End
Return
Lbl A
!If (F^5)
úEüE
End
Return
Lbl B
0üGüHüIüJüKüLüMüNüR
For(K,0,3)
{(2*K)+L}üH
{(2*K)+1+L}-6ü{(2*K)+1+L}
{(2*K)+1+L}/2üG
If (G÷7)
0ü{(2*K)+1+L}
{(2*K)+1+L}/2üG
End
For(L,0,5)
(G*cos(L*O+D))//128+47üI
(G*sin(L*O+D))//128+31üJ
(G*cos((L+1)*O+D))//128+47üM
(G*sin((L+1)*O+D))//128+31üN
If ((J<<0) and (N<<0))
ElseIf (J<<0)
J*sin(O-(448-(L*O+D)))//127//sin(64-(O-(448-(L*O+D))))//127+IüI
0üJ
ElseIf (N<<0)
N*sin(O-(448-((L+1)*O+D)))//127//sin(64-(O-(448-((L+1)*O+D))))//127+MüM
0üN
End
If ((J>>63) and (N>>63))
ElseIf (J>>63)
J*sin(O-(448-(L*O+D)))//127//sin(64-(O-(448-(L*O+D))))//127+IüI
63üJ
ElseIf (N>>63)
N*sin(O-(448-((L+1)*O+D)))//127//sin(64-(O-(448-((L+1)*O+D))))//127+MüM
63üN
End
!If (H=L)
Line(I,J,M,N)
End
End
End
Return
We are only concerned with this segment of code:
Lbl B
0üGüHüIüJüKüLüMüNüR
For(K,0,3)
{(2*K)+L}üH
{(2*K)+1+L}-6ü{(2*K)+1+L}
{(2*K)+1+L}/2üG
If (G÷7)
0ü{(2*K)+1+L}
{(2*K)+1+L}/2üG
End
For(L,0,5)
(G*cos(L*O+D))//128+47üI
(G*sin(L*O+D))//128+31üJ
(G*cos((L+1)*O+D))//128+47üM
(G*sin((L+1)*O+D))//128+31üN
If ((J<<0) and (N<<0))
ElseIf (J<<0)
J*sin(O-(448-(L*O+D)))//127//sin(64-(O-(448-(L*O+D))))//127+IüI
0üJ
ElseIf (N<<0)
N*sin(O-(448-((L+1)*O+D)))//127//sin(64-(O-(448-((L+1)*O+D))))//127+MüM
0üN
End
If ((J>>63) and (N>>63))
ElseIf (J>>63)
J*sin(O-(448-(L*O+D)))//127//sin(64-(O-(448-(L*O+D))))//127+IüI
63üJ
ElseIf (N>>63)
N*sin(O-(448-((L+1)*O+D)))//127//sin(64-(O-(448-((L+1)*O+D))))//127+MüM
63üN
End
!If (H=L)
Line(I,J,M,N)
End
End
End
Return
Simply put: This is the display routine for incoming sprites. If it sees a line that is clipped, it fixes it.
This is the first little bit of code:
(G*cos(L*O+D))//128+47üI
(G*sin(L*O+D))//128+31üJ
(G*cos((L+1)*O+D))//128+47üM
(G*sin((L+1)*O+D))//128+31üN
It does the polar to rectangular conversion.
G is the radius, L*O is the angle of one point relative to D (which rotates everything, so it is added here), and (L+1)*O is the other
The 47 and 31 are the coordinates for the center of the screen (the origin)
If ((J<<0) and (N<<0))
ElseIf (J<<0)
J*sin(O-(448-(L*O+D)))//127//sin(64-(O-(448-(L*O+D))))//127+IüI
0üJ
ElseIf (N<<0)
N*sin(O-(448-((L+1)*O+D)))//127//sin(64-(O-(448-((L+1)*O+D))))//127+MüM
0üN
End
If ((J>>63) and (N>>63))
ElseIf (J>>63)
J*sin(O-(448-(L*O+D)))//127//sin(64-(O-(448-(L*O+D))))//127+IüI
63üJ
ElseIf (N>>63)
N*sin(O-(448-((L+1)*O+D)))//127//sin(64-(O-(448-((L+1)*O+D))))//127+MüM
63üN
End
This is the meat of the routine. It checks if an endpoint is out of bounds (and it both are, it does nothing) (Note: This routine was written for the top and bottom of the screen to be checked, but not the sides. It follows pretty much the same process, only the coordinates are flipped and 448 is 364)
The key is the law of sines: There is a triangle formed by the top border of the screen, the vertical line of the x coordinate of the point off-screen, and the line that is being clipped. By using this (the formula above) we can calculate the x coordinate of the point on the line that is at y=0
That is all. Remember to find your angles first if you are using rectangular coordinates. If you don't feel that I explained it well enough, please let me know and tell me what I need to explain.
-
If you really need line clipping, you can use this 449 byte routine (not including the subroutines used).
The routine uses the full signed 16-bits of each parameter, however it fails for large |x2-x1| and/or large |y2-y1| due to overflow
:Lbl LineC
:If r4<<r2
:r1->r5:r3->r1:r5->r3
:r2->r6:r4->r2:r6->r4
:End
:ReturnIf r4<<0
:ReturnIf r2>=>=64
:r1-r3->r5
:r4-r2->r6
:If r2<<0
:r4*r5//r6+r3->r1:0->r2
:End
:If r4>=>=64
:r2-63*r5//r6+r1->r3:63->r4
:End
:If r3<<r1
:r1->r5:r3->r1:r5->r3
:r2->r6:r4->r2:r6->r4
:End
:ReturnIf r3<<0
:ReturnIf r1>=>=96
:r2-r4->r5
:r3-r1->r6
:If r1<<0
:r3*r5//r6+r4->r2:0->r1
:End
:If r3>=>=96
:r1-95*r5//r6+r2->r4:95->r3
:End
:Line(r1,r2,r3,r4)
:Return
Just sayin...
-
pimathbrainiac you should definitely post a program as well so we can try everything out. Looking at the screenshots it looks like there might be something funny going on, but it's hard to tell when everything's moving so fast.
-
The problem I had wasn't with lines not clipping, it was how to do them in an extremely optimized manner. There are a couple routines lying around on the forums, but for my applications they're mostly too slow.
-
Maybe someone can create a line clipping axiom?
-
It's extremly hard to get a super optimized line cliping (I work on it since 2 week :'( )
For what I do, 3D, I need a routine, but a particular one : cliping against a polygon. I can do with the following code (C, find on net), but it's not enough fast D:
// Cyrus-Beck 2-D Line Clipping algorithm
// for ease of coding we will treat a 2D point and a 2D vector
// as the same
struct Point2D
{ float x,y;
}
// for simplicity we set an upper bound on the number of
// points allowed to define a polygon - by moving to a class
// with a constructor we could make the array any size we wanted
const int MAXP = 100;
struct Polygon
{ int nPoints;
Point2D v[MAXP];
}
const int MAXN = 100;
typedef Point2D Normal[MAXN];
// compute the outer normals.
// note that this requires that the polygon be convex
// to always work
void CalcNormals (Polygon p, Normal & n)
{ int i,j,k;
point2D v;
for (i = 0; i < p.nPoints; i++)
{ j = (i+1)%p.nPoints;
k = (i+2)%p.nPoints;
// make vector be -1/mI + 1J
n[i].x = -(p.v[j].y - p.v[i].y)/(p.v[j].x - p.v[i].x);
n[i].y = 1.0;
v.x = p.v[k].x - p.v[i].x;
v.y = p.v[k].y - p.v[i].y;
if (DotProduct (n[i],v) > 0) // inner normal
{ n[i].x *= -1;
n[i].y = -1;
}
}
}
float DotProduct (Point2D v1, Point2D v2)
{
return v1.x*v2.x + v1.y*v2*y;
}
void CBClip (Point2D p1, Point2D p2, Normal n, Polygon p, Boolean & visible,
Point2D & rp, Point2D & q)
{ float t1,t2,t,num,den;
Point2D dirV,F; // vectors
int I;
// start largest at smallest legal value and smallest
// at largest legal value
t1 = 0.0;
t2 = 1.0;
// compute the direction vector
dirV.x = p2.x - p1.x;
dirV.y = p2.y - p1.y;
visible = TRUE;
i = 0;
while ( (i < p.nPoints) && visible)
{ F.x = p1.x - p.v[i].x;
F.y = p1.y - p.v[i].y;
num = DotProduct (n[i],F);
den = DotProduct (n[i],dirV);
if (den == 0.0) // Parallel or Point
{ // parallel - if outside then forget the line; if inside then there are no
// intersections with this side
// but there may be with other edges, so in this case just keep going
if (num > 0.0)
visible = FALSE; // Parallel and outside or point (p1 == p2) and outside
}
else
{ t = -(num/den);
if (den < 0.0) // entering
{ if (t <= 1.0)
if (t > t1)
t1 = t;
}
else if ( t >= 0.0) //exiting
if (t < t2)
t2 = t;
}
i++;
}
if ( t1 <= t2)
{ rp.x = p1.x + t1*dirV.x;
rp.y = p1.y + t1*dirV.y;
q.x = p1.x + t2.dirV.x
q.y = p1.y + t2*dirV.y
}
else
visible = FALSE;
}
maybe asm can help, though
-
Constructive notes, not about the content but the form:
- I don't get the title :P
- "0üGüHüIüJüKüLüMüNüR" is bad, use TokenIDE or SourceCoder or I don't know whatever other software that actually translates arrows to arrows :P
-
Constructive notes, not about the content but the form:
- I don't get the title :P
- "0üGüHüIüJüKüLüMüNüR" is bad, use TokenIDE or SourceCoder or I don't know whatever other software that actually translates arrows to arrows :P
Yeah, the title was a bad title. I didn't think about SourceCoder. Thanks!
Also: I came up with a non-trig routine. I WAY over-thought the process.