GDR Forum Index
Podcast Podcast
Dev Dev Logs
Search Search
RSS RSS
Register Register
Log in Log in
Reply to topic GDR Forum Index -> Game Developer's Refuge -> Development Log - Minimal 3d Software Renderer
View previous topic :: View next topic  
Author Message
n29
Developer

Joined: 13 Sep 2005
Posts: 879

PostPosted: Wed Feb 03, 2010 8:09 pm    Post subject: Development Log - Minimal 3d Software Renderer Reply with quote

I've been riding the '3d software renderer in 4k of Java bytecode' Dragon again lately and thought I'd put my results in a dev log since software rendering is a generally interesting subject (admit it you geeks! /joke). For reference I previously spent some time on this: http://gamedevelopersrefuge.org/GDR/viewtopic.php?t=218.

When contemplating a 'minimal' 3d software renderer that will fit into 4k of compressed byte code and leave room for something gamelike there's not room for a lot of standard 'techniques'. Ie, ideally, all the logic should fit into one method of one class; initialization, set up, main loop, rendering loop, logic, everything. No extra classes, not even any helpful classes like Matrix4f or Vector3f. The result is code that written in a very low level, non oo manner. Not even procedural since, as mentioned, everything SHOULD fit into one God method. It's kind of Assembler like in fact.

When doing software 3d, the 'one method' doesn't work because: you have to concatenate the model space and view space transformations; the job that's normal done by matrix operations but we don't have matrices. Ie there's a camera with a rotation and translation and each mesh in the game has a local rotation and translation. To draw an object first the mesh is rotated then translated, then the camera translation and rotation are applied. Repeating the same code twice for this case is simply too expensive in bytes that end up in the final executable. It would be nice to have methods translate and rotate that take mesh and apply the transformation like:

Code:
 
mesh = rotate(cameraRot, (translate(cameraTrans, translate(meshTrans, (rotate(meshRot, mesh)))))


A 'mesh' in this case isn't entirely accurate. The question of how represent 3d data is important. As stated, the goal is not introduce extra classes, so the solution is to represent data as arrays. Here the tris are 3 indexes into the vertex array for each corner of a triangle:

Code:

double [][] verts = {{x1, y1, z1}, {x2, y2, z2}, ...}
double [][] tris = {{v1, v2, v3},{v4, v5, v6}, ...}


In the case of rotation and translation we are only concerned with the vertexes. Below are the two ESSENTIAL methods I ended up. Simply apply the rotations in the most basic, least code way:

Code:

    // a = {rotation X, rotation Y, rotation Z}
    // v = {x, y, z}
    public double[] rotXYZ(double[] a, double[] v) {
        double[] v1 = new double[] {0, 0, 0};
        double[] v2 = new double[] {0, 0, 0};
        //rotX
        double cos = (double)Math.cos(a[0] * .01745329f);
        double sin = (double)Math.sin(a[0] * .01745329f);
        v1[0] = v[0];
        v1[1] = cos*v[1] - sin*v[2];
        v1[2] = sin*v[1] + cos*v[2];
        // rotY
        cos = (double)Math.cos(a[1] * .01745329f);
        sin = (double)Math.sin(a[1] * .01745329f);
        v2[0] = cos*v1[0] + sin*v1[2];
        v2[1] = v1[1];
        v2[2] = cos*v1[2] - sin*v1[0];
        // rotZ
        cos = (double)Math.cos(a[2] * .01745329f);
        sin = (double)Math.sin(a[2] * .01745329f);
        v1[0] = cos*v2[0] - sin*v2[1];
        v1[1] = sin*v2[0] + cos*v2[1];
        v1[2] = v2[2];
        return v1;
    }

    public double[] translate(double[] t, double[] v) {
        double[] v1 = new double[] {0, 0, 0};
        v1[0] = v[0] + t[0];
        v1[1] = v[1] + t[1];
        v1[2] = v[2] + t[2];
        return v1;
    }


Edit; clarified a couple of points


Edited by n29 on Thu Feb 04, 2010 5:28 am; edited 1 time
View user's profile Send private message
Sirocco
Moderator

Joined: 19 Aug 2005
Posts: 9328
Location: Not Finland
PostPosted: Thu Feb 04, 2010 4:11 am    Post subject: Reply with quote

I like software rendering. Passing everything off to a GPU is so boring!
View user's profile Send private message Visit poster's website
Gil
Developer

Joined: 14 Nov 2005
Posts: 2341
Location: Belgium
PostPosted: Thu Feb 04, 2010 9:23 am    Post subject: Reply with quote

Fun fact:

I wrote my first software 3D renderer in pascal when I was 15 on a school trip. On paper.

It was slow as hell obviously, but I'm pretty sure I get ultimate geek points for it. It came to me when playing Goldeneye. I never heard of a transformation matrix, it just dawned to me looking at the game, based on the trigonometry we had learned in school the previous year.

I also ended up drunk with a girl in my bed on that school trip, which probably negates the geek points though.
_________________
PoV: I had to wear pants today. Fo shame!
View user's profile Send private message Visit poster's website
n29
Developer

Joined: 13 Sep 2005
Posts: 879

PostPosted: Sat Feb 06, 2010 6:13 am    Post subject: Reply with quote

I forgot to mention that this log will be about polygon rendering; there are of course other techniques for doing 3d; ray casting (ala Doom) and voxels. I haven't explored those yet.

There seems to be two generally accepted methods for rendering polygons, and a third which is cheating:

1. Most windowing systems provide access to a graphics context associated with a window and provide a drawPolygon method. In Java this is the Graphics.drawPolygon() method. Using this method to draw 3d graphics has one major drawback; no z-buffer so the 'painters algorithm' must be used ie sort the polygons from back to front and draw the farthest away first. This technique also requires special care when constructing meshes to avoid/minimize 'z fighting'.

2. The halfspace method. Find the minimum bounding rectangle for a triangle and for each point in the rectangle, check if the point is alos within the triangle by calculating the dot product with each edge.

3. Scan line rasterizing. This the one you'll read about the most;decompose the triangle into a list of line segments and draw the line segments.

I'll talk about all these and how they fair when compressed into 4k of bytecode.
View user's profile Send private message
Bean
Admin

Joined: 20 Aug 2005
Posts: 3763

PostPosted: Sat Feb 06, 2010 3:12 pm    Post subject: Reply with quote

hehe reminds me of old SFB2: Vector Warriors
Wasn't true 3D since there was no rotation but for BASIC is was one of the cooler things I've done.

It'll be great when we move away from current 3D rendering.

-Bean
_________________
Kevin Reems | Nuclear Playground | Solid Driver
View user's profile Send private message Visit poster's website
sam
Moderator

Joined: 22 Aug 2005
Posts: 255
Location: The high seas
PostPosted: Sun Feb 07, 2010 3:20 pm    Post subject: Reply with quote

yeah that game was amazing, i think you released an sdk for it in some form as well which i had some fun with at the time
reminds me of an awesome racing game that was made in basic as well which had a good 3d engine, can't remember its name though
View user's profile Send private message Visit poster's website AIM Address MSN Messenger
Hard Rock
Contributor

Joined: 31 Aug 2005
Posts: 238

PostPosted: Sun Feb 07, 2010 4:41 pm    Post subject: Reply with quote

Groov Buggies?

_________________
Hard Rock
[The Stars Dev Company][Twitter]
View user's profile Send private message Visit poster's website
Bean
Admin

Joined: 20 Aug 2005
Posts: 3763

PostPosted: Sun Feb 07, 2010 10:41 pm    Post subject: Reply with quote

Yeah there was an SDK but to my knowledge no one ever made a game with it.

Never saw that Groov Buggies. Looks funky :)

edit: Just tried it out. It's pretty impressive for BASIC. And unlike my game it's true 3D. Runs slow though. Still quite an accomplishment.


-Bean
_________________
Kevin Reems | Nuclear Playground | Solid Driver
View user's profile Send private message Visit poster's website
syn9ne
Contributor

Joined: 09 Jan 2010
Posts: 303

PostPosted: Wed Feb 10, 2010 9:33 am    Post subject: Reply with quote

Stick fighters brawl was so bad ass at the time. ive considered doing something like that many times. even a couple months ago >)
_________________
The Hideout Games :: #thehideout on freenode.net :: Pinterest :: Greenlight
View user's profile Send private message Visit poster's website AIM Address Yahoo Messenger
sam
Moderator

Joined: 22 Aug 2005
Posts: 255
Location: The high seas
PostPosted: Wed Feb 10, 2010 2:23 pm    Post subject: Reply with quote

groov buggies was totally the one, i spent ages playing that game. really well done.
View user's profile Send private message Visit poster's website AIM Address MSN Messenger
n29
Developer

Joined: 13 Sep 2005
Posts: 879

PostPosted: Sun Feb 28, 2010 10:31 am    Post subject: Reply with quote

Above I have the mesh data as arrays of longs (verts) and ints (tri indices). This is just about the worst thing you can do in terms of Java bytecode. The compiler implements a literal array declaration like:

Code:
double [][] verts = {{x1, y1, z1}, {x2, y2, z2}, ...}


as a call to new an array, then load every value into the array individually. So that's a push and and a store instruction for every value. That's alot of bytes in the compiled class file. A much better solution is encode data into a character string, store it in a file, load, and extract data from the characters. Considering this, I started planning how to store the most data in the minimal amount of bytes.

If I only allow each dimension of a vertex to range from 0..15 whole numbers then I can fit a vertex into 12 bits and if the number of vertexes is constrained to 255, I can make each point of the triangle index 8 bits. Using a color table, I can set the color of each triangle in 4 bits for 16 colors. So given this scheme, I can fit the data for one triangle into at most 8 bytes. This will average out to far less since many triangles will share vertices.

For simplicity, I've always planned on using flat shading. To calculate the intensity of the face color, you take the dot product of the face normal with the light source. The face normal can be calculated from the face vertexes in view space, or calculated once in model space and stored then rotated with the face into view space. In the 4k star wars project I calculated face normals on the fly and this worked adequately. Another solution is store face normals (or normals in general) as indexes into a normal table. I didn't find anything online about how to do this. But after thinking about if for a while, it seems that visually, for a normal table you'd have n normals as arrows pointing out of a sphere. However many entries are how many arrows there are sticking out of the sphere. Then the question is how to calculate n evenly distributed points on a sphere. I don't know how to do this yet. Using this approach, I could fit a normal into 4 bits for 16 indexex or 8 bits for 255 indexes. 16 doesn't seem like a lot, so I think a byte sized index for each face normal for each triangle would be the way to go. So we have:

Code:

vertex:
  1.5 bytes
triangle:
  3 bytes vertex index
  4 bits color
  1 byte face normal table index


So that's at most 9 bytes per triangle. If the data is fairly regular, and it should be then it should compress very well. Using the literal array approach above it's something horrendous, like 20 or more bytes per triangle, at least. Also, if normals are cheap all of a sudden using the normal table approach, why not implement smooth/gauraud shading?

Edit; added bits per trianlge incorrectly
View user's profile Send private message
n29
Developer

Joined: 13 Sep 2005
Posts: 879

PostPosted: Mon Mar 01, 2010 6:36 pm    Post subject: Reply with quote

In the 4k star wars project I built meshes by stretching and rotating 1x1x1 cubes. With this 'new' scheme of encoding meshes in a byte/char stream, I need a modeller that will let me constrain vertexes to whole numbers and output a format I can work with (a post processing step to massage the data into a form I can use). So I started going back thru some blender tutorials. Blender will let me 'snap to' vertexes to a grid and it will export to the .obj format which is plain text. Here is a minimal vertex/triangle attempt at an x-wing:



This is blender running in a virtual box win xp instance on my ubuntu laptop (9,04). Unfortunately this version of ubuntu has gfx driver issues that keep blender from working properly without upgrading a bunch of stuff. I'm just going to wait for 10.04 before I upgrade again.
View user's profile Send private message
xearthianx
Developer

Joined: 28 Sep 2006
Posts: 771
Location: USA! USA!
PostPosted: Thu Mar 18, 2010 12:00 am    Post subject: Reply with quote

n29 wrote:
Another solution is store face normals (or normals in general) as indexes into a normal table. I didn't find anything online about how to do this. But after thinking about if for a while, it seems that visually, for a normal table you'd have n normals as arrows pointing out of a sphere. However many entries are how many arrows there are sticking out of the sphere. Then the question is how to calculate n evenly distributed points on a sphere. I don't know how to do this yet.


You would be able to do the normal table for a circle or thin ring, yes? Just rotate the ring about some axis, and you just built yourself a sphere. Calculate the normal vectors you need along the way, and ignore the redundant ones at the "poles".
_________________
Ionoclast Laboratories - Scientia et Dominatia!
View user's profile Send private message AIM Address Yahoo Messenger MSN Messenger
syn9ne
Contributor

Joined: 09 Jan 2010
Posts: 303

PostPosted: Thu Mar 18, 2010 6:05 am    Post subject: Reply with quote

i'd go 8 bits for 256 indexes, and id use an ico sphere in blender to get the evenly spaced vertices. then either load their normals in obj format, or load their verticies and normalize the mesh. once the mesh is normalized all the verticies become the normals you need.

if you dont want to load an external file, or dont have room to store the precalculated normals in code, you can just use a formula for an ico sphere and generate them at runtime. basically, you'd be generating the 12 vertices of a 20 sided die, then subdividing each equilateral triangle until you have as many vertices as you want, normalize the mesh, and viola!

also, not sure if it'd help, but you might be able to reduce your rotation code by using axis angle rotation. which will also prevent gimbal lock, which your current method can cause.

http://en.wikipedia.org/wiki/Icosphere
http://en.wikipedia.org/wiki/Rodrigues%27_rotation_formula
_________________
The Hideout Games :: #thehideout on freenode.net :: Pinterest :: Greenlight
View user's profile Send private message Visit poster's website AIM Address Yahoo Messenger
Sirocco
Moderator

Joined: 19 Aug 2005
Posts: 9328
Location: Not Finland
PostPosted: Sat Apr 03, 2010 5:22 pm    Post subject: Reply with quote

Speaking of software rendering...

I love seeing stuff like that.
View user's profile Send private message Visit poster's website
n29
Developer

Joined: 13 Sep 2005
Posts: 879

PostPosted: Tue Oct 26, 2010 7:49 pm    Post subject: Reply with quote

Winter means the Java4k is coming around again so that means I start thinking about 4k software rendering (again).

Going back to when I stopped last time, I was re-implementing the 'half space' renderer I had used in the 4k Star Wars prototype. Only that time I was seeing a weird artifact in the render. You can see in the image below the line where the two cubes intersect it should be straight but there's a slight curve. I still cannot figure out why this is. I think it may have something to do with either my z-buffer precision, how I'm calculating the z values, or perspective projection. It's really annoying.



Code:

    BufferedImage bb;
    void render(double[] v1, double[] v2, double[] v3, int color) {
        // clip to z
        if(v1[2] < 0 || v2[2] <0 || v3[2] < 0) return;

        // project to screen 400x400
        double y1 = -(200d*v1[1]/v1[2])+200d;
        double y2 = -(200d*v2[1]/v2[2])+200d;
        double y3 = -(200d*v3[1]/v3[2])+200d;

        double x1 = (200d*v1[0]/v1[2])+200d;
        double x2 = (200d*v2[0]/v2[2])+200d;
        double x3 = (200d*v3[0]/v3[2])+200d;

        double z1 = v1[2];
        double z2 = v2[2];
        double z3 = v3[2];

        // backface culling
        if( (x1-x2)*(y3-y2) - (y1-y2)*(x3-x2) <= 0) return;

        // the plane equation for this triangle: ax + by + cz = d
        double a = (y2 - y1)*(z3 - z1) - (y3 - y1)*(z2 - z1);
        double b = (x2 - x1)*(z3 - z1) - (x3 - x1)*(z2 - z1);
        double c = (x2 - x1)*(y3 - y1) - (x3 - x1)*(y2 - y1);
        double D = -x1*a + y1*b - z1*c;

        // bounding rectangle
        int minx = (int)Math.max(0,  Math.min(x1,Math.min(x2, x3)));
        int maxx = (int)Math.min(400,Math.max(x1,Math.max(x2, x3)));
        int miny = (int)Math.max(0,  Math.min(y1,Math.min(y2, y3)));
        int maxy = (int)Math.min(400,Math.max(y1,Math.max(y2, y3)));

        // scan through bounding rectangle
        for(int y = miny; y < maxy; y++) {
            for(int x = minx; x < maxx; x++) {
                // When all half-space functions positive, pixel is in triangle
                if((x1 - x2) * (y - y1) - (y1 - y2) * (x - x1) > 0 &&
                        (x2 - x3) * (y - y2) - (y2 - y3) * (x - x2) > 0 &&
                        (x3 - x1) * (y - y3) - (y3 - y1) * (x - x3) > 0) {
                    // clamp to visible area of display
                    if(x > 0 && x < 400 && y > 0 && y < 400) {
                        double z = (-D - a*x + b*y)/c;
                        int i = 400*y + x;
                        if(z < zbuffer[i]) {
                            bb.setRGB(x, y, color);
                            zbuffer[i] = z;
                        }
                    }
                }
            }
        }


This algorithm is explained in this link which I'm sure I've posted here before:

http://www.devmaster.net/codespotlight/show.php?id=17

So at this point I'm going to skip it and go on to triangle rasterization.

Edit: replaced code with more readable version
View user's profile Send private message
Reply to topic GDR Forum Index -> Game Developer's Refuge -> Development Log - Minimal 3d Software Renderer
Game Developer's Refuge
is proudly hosted by,

HostGator

All trademarks and copyrights on this page are owned by their respective owners. All comments owned by their respective posters.
phpBB code © 2001, 2005 phpBB Group. Other message board code © Kevin Reems.