flat assembler
Message board for the users of flat assembler.

Index > Heap > Slope of a line???

Author
Thread Post new topic Reply to topic
rhyno_dagreat



Joined: 31 Jul 2006
Posts: 487
Location: Maryland, Unol Daleithiau
rhyno_dagreat
I'm trying to figure out how to do poly filling, and have succeeded in it. However, it was by trial and error and not truly by understanding, so I'm here to ask if anyone understands the following conundrum.

With a triangle, you have three lines, designated with points P1, P2, and P3.

Each of those lines has a slope... if you recall from algebra, it is the following equation:

m = (y2 - y1)/(x2 - x1)

Now... To do poly filling, you sort the points from top to bottom, P1 being the top and P3 being the bottom point, respectively.

Then you find the slopes of the lines between each point, giving you 3 slopes all together (but for right now let's say that the bottom line between P2 and P3 is horizontal, so we're not worried with a slope about that line).

One thing we will worry about in this example is coordinate systems. Let's use it like video memory, where the top lefthand side is 0,0 and it expands rightward and downward.

In order to fill the polygon, you go down each Y point between P1 and P3 and add the slope amount to the previous X in the series. BUT... it's not the real slope
it's the following equation:

inv_m = (x2 - x1)/(y2 - y1)

Or the inverse of the slope that is being used. That makes perfect sense because the Y expands positively downward.

However... I tried converting it to a normal cartesian coordinate system, and I'd convert back using the following equations:

ScrX = X + (Scanline / 2)
ScrY = -Y + (Vertline / 2)

and I'd set the slope to a normal slope.

But... it didn't work. It exceeded the bounds of the triangle.

But when I set it to the inverse slope being used, it worked!!! And this is for a regular cartesian-coordinate system!!!!

Does anyone have any ideas as to why it's doing that?
Post 27 Dec 2007, 23:58
View user's profile Send private message Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2906
Location: [RSP+8*5]
bitRAKE
I did an implementation about 20 years ago with the following algorithm:

http://en.wikipedia.org/wiki/Sutherland-Hodgeman
Post 28 Dec 2007, 03:26
View user's profile Send private message Visit poster's website Reply with quote
rhyno_dagreat



Joined: 31 Jul 2006
Posts: 487
Location: Maryland, Unol Daleithiau
rhyno_dagreat
Thanks bitRAKE. I talked with my dad about it, and he explained it's all about what is your primary axis of motion. (x or y).

Also I have a 3D program on the way I'm writing in FreeBASIC.

I still have a few bugs to get out of it.
Post 28 Dec 2007, 06:39
View user's profile Send private message Reply with quote
Borsuc



Joined: 29 Dec 2005
Posts: 2466
Location: Bucharest, Romania
Borsuc
rhyno_dagreat wrote:
With a triangle, you have three lines, designated with points P1, P2, and P3.

Each of those lines has a slope... if you recall from algebra, it is the following equation:

m = (y2 - y1)/(x2 - x1)
For drawing triangles, you should instead use the (x2-x1)/(y2-y1) because you usually draw HORIZONTALLY, and only then increase the vertical position. The slope is used to 'calculate' the new 'horizontal' position on the next line (it does so successively for every line).

In fact, you can think of the slope as "how many x per y to move each line". Let's assume you have the following simple line which takes up three vertical positions:
Code:
  /
 /
/    
The first '/' has position (2,0) (where (x,y) is the format), the second '/' has position (1,1) and the third '/' has position (0,2). In reality lines can have any slope, but for this one the slope is -1. (because (0-2)/(2-0) is -1, from my formula above).

And it also makes perfect sense. Each successive vertical line has a different 'starting' x value, in fact, it's one to the left. The first line has x=2. The second has x=1. That is, we moved by -1 to the left. The last one has x=0, again, we moved by -1 to the left from the second one.

This is the slope. It calculates the newly 'x' positions for each vertical line (drawn on the screen). Obviously for a triangle, you'll have to keep track of two slopes (left and right edges), and calculate the 'x' on both sides (so you know where the respective line you draw begins and ends).

I am quite experienced with 3D programming and math (my advice is not to learn formulas by heart, but rather understand them in the true sense, not in the 'symbolic' sense Wink, or derive them yourself).

I don't think the coordinate system really matters, as long as you're drawing in increasing 'y' order (i.e if the coordinate were to have y=0 at the bottom, the formula would have been the same if you started drawing from the bottom upwards!).

The normal "slope" of the line is concerned mainly with linear functions, so it's the (y2-y1)/(x2-x1) thingy. If you were to use that formula, you should have instead drawn the screen vertical-horizontal (i.e draw a vertical line, use slope to calculate new 'y' positions, draw next vertical line, etc..). This makes sense because (y2-y1)/(x2-x1) means "how much y per x".

Since you draw the screen horizontally-vertical (i.e left-right then top-bottom), you need to calculate 'x' from y, which means you have to use the other slope.

You can usually compute the left and right edges simultaneously (in parallel), but I'd reserve the full registers for the drawing where you can do several pixels in parallel.


in case you're dealing with curves the idea is similar but a bit more complicated. In fact, the derivatives of the function actually represent the 'slope'. For higher-order polynomials (e.g 3rd), you'll need 3 formulas to update because the poly has 3 derivatives in such a case. But I'm not going to overcomplicate matters since you're only interested in lines I guess Wink

if re-arranging formulas is a bit tedious, have a look at Maxima and Pari (two CAS programs). Maxima is very useful for symbolic stuff (it can solve equations, etc.), while Pari has arbitrary precision, is much faster, but for numeric stuff. I use them both and they're free. In fact, I got a lot of enthusiasm in math because of Maxima, and now I view it from a different perspective. It really isn't that hard once you get it.

have fun Smile
Post 28 Dec 2007, 12:45
View user's profile Send private message Reply with quote
rhyno_dagreat



Joined: 31 Jul 2006
Posts: 487
Location: Maryland, Unol Daleithiau
rhyno_dagreat
Ah, the reason I posted this was to gain an understanding. I knew after I tried it it worked, but I didn't see why. My dad help by explaining it, and you elaborated it. Thanks!

Also, I'm working on my first ever solid 3D program which allows you to rotate around and move towards or away from a pyramid. However, the translation algorithm is broke (even though all I'm doing is incrementing or decrementing all Z values of the model!)

I'm programming it in FreeBasic, so please don't be a hater.
Post 28 Dec 2007, 17:08
View user's profile Send private message Reply with quote
edfed



Joined: 20 Feb 2006
Posts: 4237
Location: 2018
edfed
P1 P2 P3

who is the top left?
who is the bottom right?

one list:
y x xl
1 2 5
2 3 4
3 4 3
4 5 2
5 6 1

y is the possition in list,
x is the x coordinate for the Y entry
xl is the lengh of horizontal line...
result of this list is a triangle.
Post 28 Dec 2007, 17:13
View user's profile Send private message Visit poster's website Reply with quote
Borsuc



Joined: 29 Dec 2005
Posts: 2466
Location: Bucharest, Romania
Borsuc
edfed wrote:
P1 P2 P3

who is the top left?
who is the bottom right?
obviously for the algorithm to work they have to be sorted in increasing Y values (first one is top). I hope you did sort them?
Post 28 Dec 2007, 17:16
View user's profile Send private message Reply with quote
edfed



Joined: 20 Feb 2006
Posts: 4237
Location: 2018
edfed
painting polygon is not a simple thing.
Post 28 Dec 2007, 17:18
View user's profile Send private message Visit poster's website Reply with quote
Borsuc



Joined: 29 Dec 2005
Posts: 2466
Location: Bucharest, Romania
Borsuc
painting a polygon with a simple color is not THAT hard really, you only need slopes, etc..

texture mapping, shading, those are beasts you need to be afraid of Wink
on a sidenote, you can even do the reverse (i.e scan the bitmap image and find the position of each 'texel' on the screen).
Post 28 Dec 2007, 17:21
View user's profile Send private message Reply with quote
edfed



Joined: 20 Feb 2006
Posts: 4237
Location: 2018
edfed
light ray tracing.
Post 28 Dec 2007, 17:29
View user's profile Send private message Visit poster's website Reply with quote
rhyno_dagreat



Joined: 31 Jul 2006
Posts: 487
Location: Maryland, Unol Daleithiau
rhyno_dagreat
Raytracing is easy in some cases (i.e. spheres and planes), but it's a beast for the CPU to handle.

I've been trying to figure out how do I raytrace a triangle though.
Post 28 Dec 2007, 18:07
View user's profile Send private message Reply with quote
edfed



Joined: 20 Feb 2006
Posts: 4237
Location: 2018
edfed
what wrong whith this code?
Code:






















































































































































































































































































    
Post 28 Dec 2007, 19:14
View user's profile Send private message Visit poster's website Reply with quote
rhyno_dagreat



Joined: 31 Jul 2006
Posts: 487
Location: Maryland, Unol Daleithiau
rhyno_dagreat
Nothing there...?
Post 28 Dec 2007, 19:27
View user's profile Send private message Reply with quote
edfed



Joined: 20 Feb 2006
Posts: 4237
Location: 2018
edfed
erf, was a joke
Post 28 Dec 2007, 19:28
View user's profile Send private message Visit poster's website Reply with quote
rhyno_dagreat



Joined: 31 Jul 2006
Posts: 487
Location: Maryland, Unol Daleithiau
rhyno_dagreat
Lol, kinda figured. XD
Post 28 Dec 2007, 21:22
View user's profile Send private message Reply with quote
edfed



Joined: 20 Feb 2006
Posts: 4237
Location: 2018
edfed
triangle tracing, but bug, not really beautifull.

and really not optimised.

just for tries.

the principle is to find the up, the down and the middle dot of the triangle. then, fill two tables, start and stop.
with up/down for start, and up/mid mid/down for stop.

then, convert the stop coordinates in counters.
and trace it.
the problem is for start and stop pixels, sometimes it is good, but mostlly it is bad computed, it need to know what is really the start and the stop before to fill the tables.

Code:
dots:
.1 dd x,y
.2 dd x,Y
...

polygon:
dd dot.1,dot.2,dot.3

.p1x rd 1
.p2x rd 1
.p3x rd 1
.p1y rd 1
.p2y rd 1
.p3y rd 1

raster:
.start:
rd 200
.stop:
rd 200

    


Description: 1,2,3,4,5,6,7,8,9 to select the dot
Up Down Left Right to move the dot.

Download
Filename: triangle.zip
Filesize: 9.16 KB
Downloaded: 61 Time(s)

Post 14 Mar 2008, 17:14
View user's profile Send private message Visit poster's website Reply with quote
rugxulo



Joined: 09 Aug 2005
Posts: 2341
Location: Usono (aka, USA)
rugxulo
rhyno_dagreat wrote:
I'm programming it in FreeBasic, so please don't be a hater.


You could always post on their forums (if not already, I haven't checked). But FB supports inline asm, which I assume you're using Twisted Evil , so you shouldn't have any complaints. (BTW, FB rocks, really nice!)
Post 17 Mar 2008, 18:33
View user's profile Send private message Visit poster's website Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  


< Last Thread | Next Thread >
Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You can attach files in this forum
You can download files in this forum


Copyright © 1999-2020, Tomasz Grysztar.

Powered by rwasa.