| |
Cybernator
Registered: Jun 2002
Posts: 154 |
STr34kZ (aka. EOR lines)
Streaks, not freaks. :)
Does anyone have any idea how to _completely_ avoid the streaks in EOR fillers. SLJ in his tutorial mentioned that ---*--- intersections will fail. I wanted a complete 3D scene to be EOR filled at once. After some experimenting I came up with a technique to handle obscured objects, objects partially or wholly on the top of another, and it works ok (as long as the filling of a single object is successful). Pick up yer jaws, this doesn't work at realtime. :) Because of this, implementing of an algorithm to handle these intersections will not be a trouble, but I can't think of anything.
Lines are drawn from left to right and the last pixel is not drawn for horizontal lines (where dx>dy). For vertical lines, I don't draw the endpoints, and I only draw the last pixel of each vertical chunk (the way SLJ's routine works).
One interesting thing with the object where this happens is that if you watch it from the other side, there're no streaks.
Check out: http://www.geocities.com/lazeristoski/eor.zip
Use left/right arrows to change frames, F to toggle filling.
Btw, clipping against the upper border is handled as well, though you won't see that from the animations I have included.
Ah yes, make sure you have DirectX 7 or later installed. :P
(addon: just drag one of the .eor files onto the Exorizer.exe)
|
|
| |
Graham
Account closed
Registered: Dec 2002
Posts: 990 |
1st rule: always draw your lines in the same direction (usually from left to right)
2nd rule: make fitting definition for your starting end endpoints. which points do belong to a line and which don't?
example: line from x0 to x1 should contain pixels >= x0 but < x1. another possible definitaion is > x0 and <= x1. anything else will give you either gaps or pixels belonging to two lines. |
| |
Cruzer
Registered: Dec 2001
Posts: 1048 |
I drew lines in both directions for my glenz routine in yktr/cml, so apparently it's possible. My rule #1: Just tweak around with it untill it works. |
| |
Oswald
Registered: Apr 2002
Posts: 5094 |
rule 1 is not important indeed. sometimes you can even speed up things.
once I needed a speedcode, which has to check wether Y is in the range 0-7, so it had the code:
dey
beq *+x
if you always go to the same direction horizontally (left 2 right) you will need to use this when lines are drawn downwards:
iny
cmp #$08
beq *+x
if you keep your lines always drawn from bottom to top, in 2 cases you need to go left to right, in 2 right to left. going always from bottom to top you can avoid the cmp, and have always dey, beq. (this might need the rule of setting or not the start/end pixel to be changed for diff cases, but I dont remember now how I did it)
rule #2 is wiser than SLJ's one, and it's used in most (if not all) 'modern' eor fillers. |
| |
Krill
Registered: Apr 2002
Posts: 2980 |
wtf? you definately complicate things too much, oswald.
for me it worked fine to:
1) always draw left->right
2) always DON'T draw the first (leftmost) pixel of a line
3) put the pixels using eor
no extra measures were needed to avoid any colour leaks and similar problems. |
| |
Oswald
Registered: Apr 2002
Posts: 5094 |
krill: to avoid the extra cmp in the speedcode I needed a lineroutine which always goes from bottom to top (dey, beq). Notice, that this lineroutine is SPECIALIZED to make advantage of the bitmap mode to fasten up fillings (you can fill a whole char by one sta into the color ram, rite?), so it has to KNOW wether it moved out of the current character or not.. == it has to check the Y register after each pixel set.. and that is faster by dey beq than by doing iny cmp #$08 beq |
| |
Graham
Account closed
Registered: Dec 2002
Posts: 990 |
Krill wrote:
"2) always DON'T draw the first (leftmost) pixel of a line"
or the last... as i wrote in my previous post:
x0 <= xp < x1
x0 < xp <= x1
i never need any tweaking when following one of those rules. |
| |
Krill
Registered: Apr 2002
Posts: 2980 |
oswald: ok, i thought we were talking about basic eor filling instead of a specialized version working with whatever screen/bitmap mode :)
graham: yes true, i just wrote how i did it, it's of course not the only way possible. |
| |
Cybernator
Registered: Jun 2002
Posts: 154 |
As I already stated, lines are always drawn from left to right: x0 <= xp < x1. And yes, pixels are drawn using EOR. It wouldn't work otherwise. :) I believe the reason for the streaks is not because two polygons share the same edges. I'll try to get the exact polygon (one of'em, coz there're two streaks) which misbehaves, and I'll try it in SLJ's routine. In case it doesn't work, I don't know. I tweaked the routine enough, I have no ideas left.
One thing I noticed with the "3objects.eor" animation is that streaks _will_ appear if you don't take half the step the first time. The trouble was with the vertical lines (i.e. dy>dx). Add that to the rules. :) (and it should've been 57r34k2 :P) |
| |
Cybernator
Registered: Jun 2002
Posts: 154 |
How many times were you searching for a bug or a cause, and you found it where you least expected it? Have a look at http://www.geocities.com/lazeristoski/bug.zip
This polygon needs 4 lines, and here they go as found in bug.eor:
1. 68,33 - 274,33
2. 68,33 - 271,48
3. 71,48 - 271,48
4. 68,33 - 271,48
Doesn't look very nice, does it? If you try to draw'em, you'll see that the vertical ones are missing. Furthermore, you'll also find the line which divides the rectangle into triangles. That line exists twice, so it gets erased when EOR-ed. The trouble was caused by my ASE parser (or maybe by 3D Studio Max itself). In ASE files, lines that divide one face into triangles are marked as invisible (cheers to the dude who thought of this when he was creating the file format :)) So in the case of the boxes, there was no problem. However, the troublesome object was a box consisted of several segments, so that I could sharpen it. After that, the fuselage was optimized. This is most likely where Max had the trouble. (I mentioned the fuselage; this is supposed to be an alien aircraft. Who knows? Maybe I'll make it look like one. :P)
Oh well.. Let's see if there's cure for this. |
| |
Oswald
Registered: Apr 2002
Posts: 5094 |
my filledvectors use a routine which eliminates lines that 'normally' would be drawn more than once... simply checks which lines would be drawn more than once, and precalculates what the resulting color would be after that, and then only one line is drawn in the resulting color.. or no line if the color would be the bitpair 00. Guess other coders routines does this too ? |
| |
Krill
Registered: Apr 2002
Posts: 2980 |
yes, i do that as well. |
| |
Graham
Account closed
Registered: Dec 2002
Posts: 990 |
in my routines there is no such things as "lines drawn more than once" so i do not have to eliminate them. |
| |
Cruzer
Registered: Dec 2001
Posts: 1048 |
oldest trick in the book ;) |
| |
Oswald
Registered: Apr 2002
Posts: 5094 |
graham ?! how do you do that ? |
| |
JackAsser
Registered: Jun 2002
Posts: 2014 |
1. Perform backface removal.
2. Set all edge colors to 0.
3. For each face take face-color and eor the color with the color of each corresponding edge.
4. Draw all the edges using EOR.
5. EOR-fill.
Kind of, sort of... :D
ps. only works for convex objects naturaly. |
| |
Cruzer
Registered: Dec 2001
Posts: 1048 |
guess the code could look something like this, if the facevisibles were either $00 or $ff for true/false...
lda #facecolor0
and facevisible0
sta tmp
lda #facecolor1
and facevisible1
eor tmp
sta linecolor
|
| |
Oswald
Registered: Apr 2002
Posts: 5094 |
Quote: in my routines there is no such things as "lines drawn more than once" so i do not have to eliminate them.
jackasser, cruzer: you write how to actually eliminite, but graham says he doesnt has to... (?!?!) |
| |
Cruzer
Registered: Dec 2001
Posts: 1048 |
i guess you don't have to eliminate double lines in realtime if the lines are "born" knowing that they always have to consider two faces' colors and visibility to get their own line color. |
| |
Graham
Account closed
Registered: Dec 2002
Posts: 990 |
@Oswald:
something like JackA said. i do not think of the lines as "edges of a polygon" but rather "polygons are neighbours of the lines". |
| |
Cybernator
Registered: Jun 2002
Posts: 154 |
Some blah-blah about Z-sorting now. :) The 3 boxes work perfectly, but look what happens with my aircraft. http://www.geocities.com/lazeristoski/aircraft.zip
The jpg screenshot shows you how the wings are connected to the fuselage. As you can see the sorter doesn't work as it's supposed to. The aircraft is divided into several objects: fuselage (the box), cockpit, left wing, and right wing. This is because an object is assumed to have no overlapping faces. (of course front faces overlap back faces, but I'm talking about overlapping of a front face with another front face).
I calculate the centers of each object like this:
center.x=center.y=center.z=0;
for (i=0; i<nr_vertices; i++)
{
...center.x+=vertex.x;
...center.y+=vertex.y;
...center.z+=vertex.z;
}
center.x/=nr_vertices;
center.y/=nr_vertices;
center.z/=nr_vertices;
Now I do the following:
- rotate the aircraft
- before I project the points, I sort the objects according to the Z coord of the rotated centers
This is what I read in a tutorial (the PXD series, I think). But obviously this is not correct. All the tutorials I've found about Z-sorting deal with different sorting algorithms (bubble vs radix vs quick), but none of them tells _what_ to sort.
Any tips?
|
| |
Graham
Account closed
Registered: Dec 2002
Posts: 990 |
with standard sorting algos you cannot achieve a "correct" sorting for polygons. reducing a whole polygon to a 1-dimensional sorting key is invalid, if you wish perfect sorting you'll need something constraint based. definitely nothing you will do on c64...
anyway, for c64 i would go for a bucket sort. bubblesort brings you into sorting hell, and quicksort would require a software stack (256 bytes stack are usually not enough). |
| |
JackAsser
Registered: Jun 2002
Posts: 2014 |
Yep, it's invalid as Grahams states. Consider this classical problem with 4 planes (cut and paste into favorite mono-spaced text editor since CSDB doesn't have <pre> support:
...+-+....+-+...
...|#|....|#|...
+--|#|---------+
|##|#|#########|
+--|#|---------+
...|#|....|#|...
+---------|#|--+
|#########|#|##|
+---------|#|--+
...|#|....|#|...
...+-+....+-+...
No matter sort order you can't display this properly. There are several solutions to this problem. A geometrical algorithm is for instance BSP-trees which effectivly divides the above polygons into smaller ones which allows for a complete front-back rendering. Another pixel based approach is the classical z-buffer commonly used in todays 3D-hardware. |
| |
Cybernator
Registered: Jun 2002
Posts: 154 |
The animation is calculated on a PC. The C64 just draws lines and EOR fills, nothing more (ok, maybe loads the next realtime part :)). I separated the process into 3 programs, just to make it easier to maintain. First the ASCII file is converted to binary. This is then used to create the animation (rotating, sorting, projection), and saves a file with the frames. The objects are saved in back-to-front order. Now, ExORizer reads this file and converts the lines to EOR compatible ones. This is also where I take care of overlapping objects (that's why there's slight delay when you run ExORizer, unless your CPU's faster than 200 MHz :))
Now these lines should be packed well. Since "Feeling Retro" contains animations of acceptable length, this should be possible. :)
I know how Z-buffering works, although I've never coded that. But this only tells me whether I should draw the pixel or not. ExORizer really needs to use the painter's algorithm, i.e. it needs the objects sorted correctly. Actually I can achieve this with Z-buffering if I iterate the objects in pairs (every object with every object), then see which object is obscured by the other (pixel by pixel!). If they don't overlap, it wouldn't matter which of these is drawn first. At the end I'll have a sorted list, but this is completely inefficient.
I don't know much about BSP trees. I read that they can be used for various things. There's an example proggy that converts 2D lines (seen from the top) to a 3D scene. This immensely reminds of Ray Casting, yet allows sloped walls (if I don't misuse the term sloped-walls). One document says that BSP trees can be used for "partial Z-ordering". What does it mean by partial? I also know it's computationally expensive for realtime, but again this is no problem. :P BUT, can it work with real 3D scenes? If it only works with scenes generated from lines, it won't help at all.
No idea how S-buffering works. Can that be used to _sort_ the objects? Or maybe another slow-but-correct sorting technique which I haven't heard of?
|
| |
Graham
Account closed
Registered: Dec 2002
Posts: 990 |
bsp trees only help you with static world/object sorting. quake for example used a bsp tree to render the level. all moving objects (doors, enemies, other objects) use z-buffer for sorting against each other and the level. |
| |
JackAsser
Registered: Jun 2002
Posts: 2014 |
Using BSP will solve your problem. But as Graham states BSP are for static scenes so you have to recalculate the BSP-tree each frame to get a new polygon order. What a BSP-tree generator does is to create a tree in which you can traverse to get a correctly sorted front2back or back2front list of polygons from the current point of view. In places where it's impossible to have such order (as my example above) it will clip the polygons. And yes, this works for any dimensions. The algoritm is really simple.
1) Choose a polygon.
2) Calulate the plane from that polygon. I.e. where ax+by+cz+d=0 for all vertices in the polygon.
3) Cut all polygons in the world into two using the plane.
4) Repeat for front-side of the plane and treat that as it's own sub-world. Do the same for the back-side. All recursivly.
5) When you have only one polygon left in your sub-world the recursion is ready.
Now to use this BSP-tree:
1) Begin with the root-node. Figure out which side of the cut-plane you're at using the plane equation again.
2) Traverse either front-branch or back-branch depending on which side you're on.
3) If you're on the back side continue the traversion further deep into the tree.
4) When you're traveling back from the recursion depth then draw the corresponding polygon.
This will render all polygons in the world in a pure front-2-back or back-2-front manner and display them guaranteed 100% correct.
...with reservations from errors above, it was a really long time since I did BSP... (check algorithms on the net for better explanations).
|
| |
White Flame
Registered: Sep 2002
Posts: 136 |
For something like your aircraft, split it into convex objects: Left wing, Right wing, fuselage, cockpit. Then create a render order for the 8 directions you can view it from. For instance, if you have back-to-front rendering and you're looking at it from the JPG's view (bottom rear right), have the render list for that view be Cockpit, Left wing, Fuselage, Right wing. It takes a bit of manual tweaking, but incredibly fast at runtime becuase everything's presorted for the range of views. You might need to make more viewing ranges than the basic 8 if your object is very complex, but for most things, 8 views work fine (combinations of top|bottom, left|right, front|rear).
I've used S-buffering a lot. In a nutshell, it renders your polygons to line segments instead of pixels, clips those line segments against each other as they're generated from the polys, and then renders them to pixels only after your polygon rendering is finished. It's best used when you don't have interpenetrating polygons. However, calculating z-overlap is a bit more complex because you're interpolating instead of just comparing pixel z-coords, but there are far less comparisons overall. S-buffering is also fast because there is no overdraw of pixels, just recalculation of full line segments. Think of it as managing a RLE bitmap instead of pixels.
You can also easily perform front-to-back rendering with S-buffers, which is great for doing things like allocating color cells on the C64 bitmap. If you allocate colors while doing back-to-front overdraw, you end up having your colors taken up by things that aren't visible anymore. |
| |
Cybernator
Registered: Jun 2002
Posts: 154 |
I tried sorting using the Z-buffer, but although the wings worked correctly, there still are troubles. If the polygons don't overlap, I wouldn't know which one is in front and I skip this step in the sorter. This is most probably why it fails. White Flame's idea was ok, but I'd really like to make this work without human's assistance. :)
I get the idea behind BSP trees, but it will take some weeks before I understand enough details to implement a _2D_ BSP builder. Maybe it's possible to use the cut-with-plane method to sort, without tree generation. But this is where I'm weak. The math.. I can't find any document that deals with this part of BSP generation in details. What would you suggest me to google for? Of course I can start by understanding the plane equations, and maybe come up with my own way, but that won't take weeks. It will take years. :P The other way always worked nicer for me, like reading tutorials about 3D to understand vectors, matrices, dot/cross product, etc... (the basics at least :)) |
| |
JackAsser
Registered: Jun 2002
Posts: 2014 |
You can use existent BSP-generators. There's no point in doing your own. Coding a generator can, as u say, be very tricky, there are alot of special cases. Using the output from a BSP-generator though, is quite trivial. Search online for them, I know there is one for the old quake-level-pack for instance.
Basically the output is a new set of polygons together with the BSP-tree. Traverse the BSP-tree from the current view point and you get either a f2b or b2f sort order, depending on how traverse the tree. |
| |
Cybernator
Registered: Jun 2002
Posts: 154 |
> You can use existent BSP-generators.
Nono! I have to know how it works. And the only way to convince my self that I know it is to code it. Gotta feed my curiosity, y'see. Apart of that, maybe I'll have less trouble at university. ;) Also what kind of a gamecoder will I be if I don't know how to make a BSP builder? Yeah, I'm still hoping I'll be a John Carmack one day. :P But who knows, maybe I'll live my 70th. ;)
|
