flat assembler
Message board for the users of flat assembler.

 Index > Heap > Slope of a line???
Author
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?
27 Dec 2007, 23:58
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
28 Dec 2007, 03:26
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.
28 Dec 2007, 06:39
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 , 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

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
28 Dec 2007, 12:45
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.
28 Dec 2007, 17:08
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.
28 Dec 2007, 17:13
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?
28 Dec 2007, 17:16
edfed

Joined: 20 Feb 2006
Posts: 4237
Location: 2018
edfed
painting polygon is not a simple thing.
28 Dec 2007, 17:18
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
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).
28 Dec 2007, 17:21
edfed

Joined: 20 Feb 2006
Posts: 4237
Location: 2018
edfed
light ray tracing.
28 Dec 2007, 17:29
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.
28 Dec 2007, 18:07
edfed

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

```
28 Dec 2007, 19:14
rhyno_dagreat

Joined: 31 Jul 2006
Posts: 487
Location: Maryland, Unol Daleithiau
rhyno_dagreat
Nothing there...?
28 Dec 2007, 19:27
edfed

Joined: 20 Feb 2006
Posts: 4237
Location: 2018
edfed
erf, was a joke
28 Dec 2007, 19:28
rhyno_dagreat

Joined: 31 Jul 2006
Posts: 487
Location: Maryland, Unol Daleithiau
rhyno_dagreat
Lol, kinda figured. XD
28 Dec 2007, 21:22
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)

14 Mar 2008, 17:14
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 , so you shouldn't have any complaints. (BTW, FB rocks, really nice!)
17 Mar 2008, 18:33
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

 Jump to: Select a forum Official----------------AssemblyPeripheria General----------------MainDOSWindowsLinuxUnixMenuetOS Specific----------------MacroinstructionsCompiler InternalsIDE DevelopmentOS ConstructionNon-x86 architecturesHigh Level LanguagesProgramming Language DesignProjects and IdeasExamples and Tutorials Other----------------FeedbackHeapTest Area

Forum Rules:
 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot vote in polls in this forumYou can attach files in this forumYou can download files in this forum