« previous next »
Pages: [1]   Go Down

Author Topic: [TUTO] How to make get rid of line clipping in Axe!  (Read 4251 times)

0 Members and 1 Guest are viewing this topic.

Offline pimathbrainiac

  • Occasionally I make projects
  • Members
  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1731
  • Rating: +136/-23
  • dagaem
    • View Profile
[TUTO] How to make get rid of line clipping in Axe!
« 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):



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

Code: [Select]
.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:

Code: [Select]
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:

Code: [Select]
(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)

Code: [Select]
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.
Logged
+1/-0 karm for this message
I am Bach.

Offline jacobly

  • LV5 Advanced (Next: 300)
  • *****
  • Posts: 205
  • Rating: +161/-1
    • View Profile
Re: [TUTO] How to make get rid of line clipping in Axe!
« Reply #1 on: April 17, 2013, 10:30:24 pm »
Quote from: jacobly on October 08, 2011, 11:29:52 pm
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
Code: [Select]
: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...
Logged
+1/-0 karm for this message

Offline Builderboy

  • Physics Guru
  • CoT Emeritus
  • LV13 Extreme Addict (Next: 9001)
  • *
  • Posts: 5673
  • Rating: +613/-9
  • Would you kindly?
    • View Profile
Re: [TUTO] How to make get rid of line clipping in Axe!
« Reply #2 on: April 17, 2013, 10:43:49 pm »
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.
Logged

Offline leafy

  • CoT Emeritus
  • LV10 31337 u53r (Next: 2000)
  • *
  • Posts: 1554
  • Rating: +475/-97
  • Seizon senryakuuuu!
    • View Profile
    • keff.me
Re: [TUTO] How to make get rid of line clipping in Axe!
« Reply #3 on: April 17, 2013, 11:33:17 pm »
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.
Logged
In-progress: Graviter (...)

Offline aeTIos

  • Nonbinary computing specialist
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 3915
  • Rating: +184/-32
    • View Profile
    • wank.party
Re: [TUTO] How to make get rid of line clipping in Axe!
« Reply #4 on: April 18, 2013, 03:08:54 am »
Maybe someone can create  a line clipping axiom?
Logged
I'm not a nerd but I pretend:

Offline TheMachine02

  • LV6 Super Member (Next: 500)
  • ******
  • Posts: 452
  • Rating: +105/-0
  • me = EF99+F41A
    • View Profile
Re: [TUTO] How to make get rid of line clipping in Axe!
« Reply #5 on: April 18, 2013, 11:05:03 am »
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:

Code: [Select]
// 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
Logged
AXE/asm programmer - unleash the power of z80 //C++//C

epic 3D things http://www.ntu.edu.sg/home/ehchua/programming/opengl/CG_BasicsTheory.html

Offline Hayleia

  • Programming Absol
  • Coder Of Tomorrow
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 3367
  • Rating: +393/-7
    • View Profile
Re: [TUTO] How to make get rid of line clipping in Axe!
« Reply #6 on: April 18, 2013, 12:54:59 pm »
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
Logged
I own: 83+ ; 84+SE ; 76.fr ; CX CAS ; Prizm ; 84+CSE
Sorry if I answer with something that seems unrelated, English is not my primary language and I might not have understood well. Sorry if I make English mistakes too.

click here to know where you got your last +1s

Offline pimathbrainiac

  • Occasionally I make projects
  • Members
  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1731
  • Rating: +136/-23
  • dagaem
    • View Profile
Re: [TUTO] How to make get rid of line clipping in Axe!
« Reply #7 on: April 18, 2013, 12:58:25 pm »
Quote from: Hayleia on April 18, 2013, 12:54:59 pm
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.
Logged
I am Bach.
Pages: [1]   Go Up
« previous next »