[CSDb] - User Forums - STr34kZ (aka. EOR lines)

You are not logged in - nap

CSDb User Forums

Forums > C64 Coding > STr34kZ (aka. EOR lines)

2005-02-15 15:46

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)

... 19 posts hidden. Click here to view all posts....

2005-02-20 15:47

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?

2005-02-20 16:18

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

2005-02-20 16:53

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.

2005-02-20 19:28

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?

2005-02-20 21:09

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.

2005-02-20 21:48

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

2005-02-21 22:22

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.

2005-02-25 22:49

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

2005-02-28 09:25

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.

2005-02-28 22:32

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. ;)

Previous - 1 | 2 | 3 - Next

Refresh

Subscribe to this thread:

You need to be logged in to post in the forum.

Search the forum:
Search for in
All times are CET.

Search CSDb

Advanced

Users Online

WVL/Xenon
algorithm
Acidchild/Padua
MCM/ONSLAUGHT
DnP
wil
v3nt0r/ibex-crew
Guests online: 121

Top Demos

1 Next Level  (9.7)
2 13:37  (9.7)
3 Mojo  (9.7)
4 Coma Light 13  (9.6)
5 The Demo Coder  (9.6)
6 Edge of Disgrace  (9.6)
7 What Is The Matrix 2  (9.6)
8 Uncensored  (9.6)
9 Comaland 100%  (9.6)
10 Wonderland XIV  (9.6)

Top onefile Demos

1 No Listen  (9.6)
2 Layers  (9.6)
3 Cubic Dream  (9.6)
4 Party Elk 2  (9.6)
5 Copper Booze  (9.6)
6 X-Mas Demo 2024  (9.5)
7 Dawnfall V1.1  (9.5)
8 Rainbow Connection  (9.5)
9 Onscreen 5k  (9.5)
10 Morph  (9.5)

Top Groups

1 Performers  (9.3)
2 Booze Design  (9.3)
3 Oxyron  (9.3)
4 Censor Design  (9.3)
5 Triad  (9.3)

Top Original Suppliers

1 Derbyshire Ram  (9.7)
2 Fungus  (9.3)
3 Black Beard  (9.2)
4 Baracuda  (9.2)
5 hedning  (9.1)

Page generated in: 0.172 sec.