#### Archived

This topic is now archived and is closed to further replies.

# [java] 3d Java program

This topic is 4942 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

##### Share on other sites
Way cool dude!
Wirting software engines is probably the coolest programming project you can do, because it allows you to do so much with your computer. Java is fun, too

--------------------------------------------------------
Life would be so much easier if we could just get the source code.

##### Share on other sites
Yes software rendering in Java can be especially challenging/rewarding. You can easily get by with drawPolygon() until you write your own triangle rasterizer. If you want to see a feature complete java software renderer google for ''idx3d''.

##### Share on other sites
Cool, I''ve also written a 3D engine in pure Java and it''s a pretty fun project .

By the way, if you want to take this further, definitely don''t use fillPolygon. Even for polygons of one single color with no z-buffer testing or blending or anything, writing to an int[] obtained by using BufferedImage.getDataSource got me about 10x faster performance than Graphics.fillPolygon. The Graphics class uses GDI, and it''s ridiculously slow.

##### Share on other sites
yeah ive seen demos of MemeorySourceImage use which takes an int[] parameter for the pixels.

How exactly are the pixels aranged in the array?

are they in order of horizontal lines or vertical lines?

eg

int[] = (x0,y0),(x1,y0),(x2,y0),(x3,y0),(x0,y1),(x1,y1),(x2,y1),(x3,y1) and so on.

or is it the other way around?

##### Share on other sites
yeah ive seen demos of MemeorySourceImage use which takes an int[] parameter for the pixels.

How exactly are the pixels aranged in the array?

are they in order of horizontal lines or vertical lines?

eg

int[] = (x0,y0),(x1,y0),(x2,y0),(x3,y0),(x0,y1),(x1,y1),(x2,y1),(x3,y1) and so on.

or is it the other way around?

edit:: feck!! look what i did, oops.

[edited by - Riviera Kid on May 30, 2004 7:42:22 AM]

##### Share on other sites
The pixel at (x,y) is in the int array at (y*width + x).

##### Share on other sites
Heh, I''ve recently a similar simple 3D java app as a university assignment (although the 3D wasn''t a requirement, it was a class of software design and UML crap and we had to do a game). Used Graphics.fillPolygon as well

I''d like to ask you about the polygon sorting. I tried to do it based on the average of the transformed Z coordinates, W coordinates, the average of the greatest and lowest transformed Z, but none of them seemed to work for my triangles, they were either z-fighting or incorrectly ordered when one of them stretched far off into the screen''s axis. I''m pretty sure I was screwing up something fundamental but I couldn''t find what was wrong.

So my question would be, how were you sorting your triangles?

##### Share on other sites
being mr lazy and mr new at this at first just for the time being i used Bubble Sort (stupid me). I only sorted per polygon and not per pixel so every now and then some polygons were not sorted properly but it was minor problem. I sorted from the center of the polygon.

Now i use the built in java sort Collections.sort(list).

The polygons furthest away go at the bottom of the list and the ones closest to me go at the top of the list. Thats all i know about polygon sorting.

Now i have a question.

How are you filling your polygons?

All this active edge list and scanline stuff gives me and head ache. Using fillpolygon doesnt allow texturing (afaik) so i recently made my own fill method.

I take 2 opposing lines on a polygon and traverse them both. As i do this i draw lines of pixels between them. It fills perfectly as far as i can see but it is extreemily slow.

My program isnt running fast at all. Any pointers on how to speed things up wud rule.

##### Share on other sites
You have to use a MemoryImageSource or BufferedImage (I haven't yet found out for sure which is faster) and write to an int array instead of to pixels. Also, using edge lists and interpolating accross each scanline is the way to go, it's really not that bad once you get down to it (probably very similar to what you've been doing). Here's an early (but therefore much easier to read ) version of my method, copied from a post on the java.sun.com forums:

    private   int  [] pixels;    private   MemoryImageSource imageSource;    private   Image backBuffer;    private   int  [] left = new   int  [2000];          // store the x value of the pixel on the left side of the triangle at a given y value.      private   int  [] right = new   int  [2000];      // ditto for the right side      private   void   createMemoryImage() {           // should be called after you set/change your window size          this  .pixels = new   int  [displayWidth*displayHeight];        this  .imageSource = new   MemoryImageSource(displayWidth, displayHeight, pixels, 0, displayWidth);        imageSource.setAnimated(true  );        this  .backBuffer = Toolkit.getDefaultToolkit().createImage(imageSource);    }    /*        Given a line, calculate its x coordinates for each y value and place them into dest.       My example uses some fixed-point math, which is not the best way; you can make it use doubles       or use a true integer line-scanning algorithm; I'll post a real one when I implement it myself - right       now this was just needed to get things working, and it does work fairly well.   */      private   void   getLineXVals(int   x1, int   y1, int   x2, int   y2, int  [] dest) {        if  (y1 > y2) {     // swap so y1 is on top              int   t = x1; x1 = x2; x2 = t;            t = y1; y1 = y2; y2 = t;        }        else   if  (y1 == y2) {     // horizontal              return  ;        }        int   dx, dy;        dy = y2 - y1;        dx = x2 - x1;        int   gi = (dx*2048) / dy;          // multiplies and divides by 2048 should get optimized to shifts by the compiler.          int   xi = (x1*2048);        for  (int   y = y1; y < y2; y++) {            dest[y] = (xi/2048);            xi += gi;        }    }    private   void   rasterizeTriangle(ProcessedPrimitive p) {        // p is just a class that contains the vertices of the triangle in *counterclockwise* order (important!)          // they are stored as doubles, so we cast them here; if you're really adventurous you can look for a moe          // precise line-drawing algorithm that actually uses doubles rather than ints and make the           // appropriate changes.          int   x0 = (int  ) p.x[0];        int   x1 = (int  ) p.x[1];        int   x2 = (int  ) p.x[2];        int   y0 = (int  ) p.y[0];        int   y1 = (int  ) p.y[1];        int   y2 = (int  ) p.y[2];        int   yMin = y0;        int   yMax = y0;        if  (y1 < yMin) yMin = y1;        else   if  (y1 > yMax) yMax = y1;        if  (y2 < yMin) yMin = y2;        else   if  (y2 > yMax) yMax = y2;                // use the fact that the vertices are in counterclockwise order to determine whether          // the edges are left or right edges.          getLineXVals(x0, y0, x1, y1, (y0>y1 ? left : right));        getLineXVals(x1, y1, x2, y2, (y1>y2 ? left : right));        getLineXVals(x0, y0, x2, y2, (y2>y0 ? left : right));                int   col = p.color.getRGB();        for  (int   y = yMin; y < yMax; y++) {            int   l = left[y];            int   r = right[y];            int   w = r - l;            if  (w<0) continue  ;            int   from = y*displayWidth + l;            int   to = from+w;            Arrays.fill(pixels, from, to, col);             // fast way to fill a continuous segment;              // if you want to do other calculations for each pixel (maybe Gouraud shading or texturing?), use              // a manual fill as follows:              // int pos = y*displayWidth + l;              // for(int i=0; i<w; i++) {              //    pixels[pos] = col;              //    pos++;              // }          }    }    public   void   paint(Graphics g) {         // clear background to black:          int   max = displayWidth*displayHeight;        for  (int   p=0; p<max; p++) {            pixels[p] = 0xff000000;          // alpha=255, r=0, g=0, b=0          }         // for each triangle, rasterizeTriangle(t);                    // now draw the raster image onto the screen          imageSource.newPixels();        g.drawImage(backBuffer, 0, 0, null);    }

[edited by - Matei on May 31, 2004 12:58:51 PM]

##### Share on other sites
Note: If you want to use BufferedImage, you need very few changes; the code for creating the image is the following:
this.backBuffer = new BufferedImage(displayWidth, displayHeight, BufferedImage.TYPE_INT_RGB);DataBufferInt buffer = (DataBufferInt) backBuffer.getRaster().getDataBuffer();pixels = buffer.getData();

I think this *is* actually better as long as the image type is TYPE_INT_RGB (no weird format).

With the method I posted above, this is quite fast (~50 FPS for a flat-shaded object on an 800x600 screen, and that includes Z-buffering which means that it'll be a lot faster if you just sort polygons).

[edited by - Matei on May 31, 2004 12:57:30 PM]

[edited by - Matei on May 31, 2004 1:00:26 PM]

##### Share on other sites
Riviera Kid (cant remember pw and couldnt b bothered opening hotmail to see it)

thanks alot. Thats great.

I am using memeoryimagesource atm. Using the bufferedimage is nice cos you still have access to the graphics paint if you create a graphics context from the buffer. I think.

cool. Ive read many tutorials on poly filling and that is by far the easiest to understand.

##### Share on other sites
Since array indexation in Java is rather slow, it is better to split the polygons into triangles. You can render triangles without using a left[] and right[] array.

##### Share on other sites
quote:
Original post by nonnus29
If you want to see a feature complete java software renderer google for ''idx3d''.
Anyway, about the MemoryImageSource vs. BufferedImage discussion: If you don''t want to support Java 1.1 (i.e. MS JView) use BufferedImage. It''s more flexible and should be a bit faster too. If you want to support 1.1, stick with MemoryImageSource or support both...but that requires a little more work to hide BufferedImage from 1.1. environments.

##### Share on other sites
check out ken perlin''s (of perlin noise fame) webpage...he has a very feature complete java software renderer entirely in java 1.0 (or 1.1?)...that means no bufferedImages, but the applets work in IE without upgrading the JVM...good for non techies.

an example object: ice cube

his website is at http://cat.nyu.edu/~perlin/ and all the code is around there somewhere, i just dont remember where. IIRC, its free to use (and to look at for your own edification) as long as you keep the attribution and dont use it for commercial purposes.

##### Share on other sites
Matei: the proper tag to use is [ source ][ /source ] so you don''t make the forum scroll left to right .

    private   int  [] pixels;    private   MemoryImageSource imageSource;    private   Image backBuffer;    private   int  [] left = new   int  [2000];          // store the x value of the pixel on the left side of the triangle at a given y value.</font>      private   int  [] right = new   int  [2000];      // ditto for the right side</font>      private   void   createMemoryImage() {           // should be called after you set/change your window size</font>          this  .pixels = new   int  [displayWidth*displayHeight];        this  .imageSource = new   MemoryImageSource(displayWidth, displayHeight, pixels, 0, displayWidth);        imageSource.setAnimated(true  );        this  .backBuffer = Toolkit.getDefaultToolkit().createImage(imageSource);    }    /*        Given a line, calculate its x coordinates for each y value and place them into dest.       My example uses some fixed-point math, which is not the best way; you can make it use doubles       or use a true integer line-scanning algorithm; I''ll post a real one when I implement it myself - right       now this was just needed to get things working, and it does work fairly well.   */</font>      private   void   getLineXVals(int   x1, int   y1, int   x2, int   y2, int  [] dest) {        if  (y1 > y2) {     // swap so y1 is on top</font>              int   t = x1; x1 = x2; x2 = t;            t = y1; y1 = y2; y2 = t;        }        else   if  (y1 == y2) {     // horizontal</font>              return  ;        }        int   dx, dy;        dy = y2 - y1;        dx = x2 - x1;        int   gi = (dx*2048) / dy;          // multiplies and divides by 2048 should get optimized to shifts by the compiler.</font>          int   xi = (x1*2048);        for  (int   y = y1; y < y2; y++) {            dest[y] = (xi/2048);            xi += gi;        }    }    private   void   rasterizeTriangle(ProcessedPrimitive p) {        // p is just a class that contains the vertices of the triangle in *counterclockwise* order (important!)</font>          // they are stored as doubles, so we cast them here; if you''re really adventurous you can look for a moe</font>          // precise line-drawing algorithm that actually uses doubles rather than ints and make the </font>          // appropriate changes.</font>          int   x0 = (int  ) p.x[0];        int   x1 = (int  ) p.x[1];        int   x2 = (int  ) p.x[2];        int   y0 = (int  ) p.y[0];        int   y1 = (int  ) p.y[1];        int   y2 = (int  ) p.y[2];        int   yMin = y0;        int   yMax = y0;        if  (y1 < yMin) yMin = y1;        else   if  (y1 > yMax) yMax = y1;        if  (y2 < yMin) yMin = y2;        else   if  (y2 > yMax) yMax = y2;                // use the fact that the vertices are in counterclockwise order to determine whether</font>          // the edges are left or right edges.</font>          getLineXVals(x0, y0, x1, y1, (y0>y1 ? left : right));        getLineXVals(x1, y1, x2, y2, (y1>y2 ? left : right));        getLineXVals(x0, y0, x2, y2, (y2>y0 ? left : right));                int   col = p.color.getRGB();        for  (int   y = yMin; y < yMax; y++) {            int   l = left[y];            int   r = right[y];            int   w = r - l;            if  (w<0) continue  ;            int   from = y*displayWidth + l;            int   to = from+w;            Arrays.fill(pixels, from, to, col);             // fast way to fill a continuous segment;</font>              // if you want to do other calculations for each pixel (maybe Gouraud shading or texturing?), use</font>              // a manual fill as follows:</font>              // int pos = y*displayWidth + l;</font>              // for(int i=0; i<w; i++) {</font>              //    pixels[pos] = col;</font>              //    pos++;</font>              // }</font>          }    }    public   void   paint(Graphics g) {         // clear background to black:</font>          int   max = displayWidth*displayHeight;        for  (int   p=0; p<max; p++) {            pixels[p] = 0xff000000;          // alpha=255, r=0, g=0, b=0</font>          }         // for each triangle, rasterizeTriangle(t);</font>                    // now draw the raster image onto the screen</font>          imageSource.newPixels();        g.drawImage(backBuffer, 0, 0, null);    }

First make it work, then make it fast. --Brian Kernighan

The problems of this world cannot possibly be solved by skeptics or cynics whose horizons are limited by the obvious realities. We need men and women who can dream of things that never were. - John Fitzgerald Kennedy(35th US President)

Do not interrupt your enemy when he is making a mistake. - Napolean Bonaparte

##### Share on other sites
quote:
Original post by EgonOlsen
quote:
Original post by nonnus29
If you want to see a feature complete java software renderer google for ''idx3d''.
Anyway, about the MemoryImageSource vs. BufferedImage discussion: If you don''t want to support Java 1.1 (i.e. MS JView) use BufferedImage. It''s more flexible and should be a bit faster too. If you want to support 1.1, stick with MemoryImageSource or support both...but that requires a little more work to hide BufferedImage from 1.1. environments.

Yes, but the source to jpct isn''t freely distributed now is it? Hmmm? But I would love to hear you insight on this:

Array access is too slow to go in the most often called routine in a software renderer (the rasterizer). It only takes another for() to get all the x values, which is there anyway in the getlineXVals() method.

##### Share on other sites
The array accesses for writing to the left and right happen an order of magnitude less often than the inner loop operation of writing a pixel to the screen, for which you have to use an array write anyway. So I think it's really worth the ease of use it brings. Later in my engine I added Gouraud shading and texturing, and all it took was a couple more calls to the interpolate functions instead of all kinds of temporary variables in my main function and worrying about all the possible types of triangles (when to switch the slope to loop along a new edge, and which edges to start looping down?). And I originally read about this method on a site from around 5-10 years ago, when people really tried to optimize things because they used much less powerful computers (www.exaflop.org). With the Hotspot JVM, you can't even really be sure that the array accesses will be that slow, since the triangle rasterizing functions will certainly be the main target for optimization.

[edited by - Matei on June 4, 2004 7:25:52 PM]

[edited by - Matei on June 4, 2004 7:27:47 PM]

##### Share on other sites
Thats true about the hotspot vm and the other, but I would just point out that 10 years ago asm/c programmers didn't have bounds checking unless they implemented it; and you can bet they didn't.

I'd like to do some test on this someday and see what the truth is... Maybe someone already has?

Edit:

http://www.gamedev.net/hosted/3dgraphics/implementation/software/index.html

[edited by - nonnus29 on June 4, 2004 7:42:06 PM]

• ### Forum Statistics

• Total Topics
628718
• Total Posts
2984375

• 25
• 11
• 10
• 14
• 14