# Software Rendering



## Steev (20. Sep 2010)

Hallo liebe Forengemeinde,

mich würde mal interessieren, was in Java der Performanteste Weg für einen Software-Rendering-Ansatz ist.
Manche schwören ja auf MemoryImageSource, andere meinen, dass man am besten VolatileImage verwendet und wieder anderer meinen, ein WriteableRaster sei das Maß aller Dinge.

Was muss man beachten und was sollte man am besten verwenden, wenn man seinen eigenen kleinen Software-Renderer schreiben will?
Ich habe zum Test mal folgenden Code geschrieben. Da kann man relativ gut sehen, welche Performance-Probleme es bei einem WriteableRaster schon bei einer Auflößung von 800x600 gibt.
Habe ich da irgendwas komplett falsch verstanden? Ich habe nämlich schon Software-Renderer in Java gesehen, die um einiges schneller waren...

[Java]import static java.lang.Math.PI;
import static java.lang.Math.cos;
import static java.lang.Math.round;
import static java.lang.Math.sin;

import java.awt.BorderLayout;
import java.awt.Color;
import java.awt.Dimension;
import java.awt.Graphics;
import java.awt.Rectangle;
import java.awt.image.BufferedImage;
import java.awt.image.WritableRaster;

import javax.swing.JFrame;
import javax.swing.JPanel;

public class XPaintTest extends JPanel implements Runnable {
    private static final long serialVersionUID = -276514233223047772L;

    BufferedImage bim = new BufferedImage(800, 600, BufferedImage.TYPE_INT_ARGB);
    BufferedImage img;

    int[] pos = new int[2];

    public XPaintTest() {
        setPreferredSize(new Dimension(800, 600));
        new Thread(this).start();

        img = new BufferedImage(100, 100, BufferedImage.TYPE_INT_ARGB);
        Graphics g = img.createGraphics();
        g.setColor(Color.CYAN);
        g.fillRect(25, 0, 50, 25);
        g.setColor(Color.RED);
        g.fillRect(0,25,100,25);
        g.setColor(Color.BLACK);
        g.fillOval(12, 50, 12, 12);
        g.fillOval(80, 50, 12, 12);
    }

    public void transform(int[] xy, double transX, double transY, double rotation, double rotX, double rotY, double xShear, double yShear, double xScale, double yScale) {
        double ix = xy[0];
        double iy = xy[1];

        ix -= transX;
        iy -= transY;

        ix -= rotX;
        iy -= rotY;

        double theta = PI / 180. * rotation;
        double sin = sin(theta);
        double cos = cos(theta);
        double anchorx = ix;
        double anchory = iy;
        ix = anchorx * cos + anchory * sin;
        iy = anchory * cos - anchorx * sin;

        ix /= xScale;
        iy /= yScale;

        anchorx = ix;
        anchory = iy;
        ix = anchorx - xShear * anchory;
        iy = anchory - yShear * anchorx;

        ix += rotX;
        iy += rotY;

        xy[0] = (int) ix;
        xy[1] = (int) iy;
    }

    public boolean getPixelFromPosition(int w, int h, int[] pos, double x, double y, double transX, double transY, double rotation, double rotX, double rotY, double xShear, double yShear, double xScale, double yScale) {
        if (pos == null)
            throw new IllegalArgumentException("Error, the argument \"pos\" could not be \"null\"!");

        pos[0] = (int) x;
        pos[1] = (int) y;

        transform(pos, transX, transY, rotation, rotX, rotY, xShear, yShear, xScale, yScale);

        if (pos[0] < 0 || pos[1] < 0 || pos[0] >= w || pos[1] >= h)
            return false;

        return true;
    }

    public void getPositionFromPixel(int[] pos, int px, int py, double transX, double transY, double rotation, double rotX, double rotY, double xShear, double yShear, double xScale, double yScale) {
        pos[0]=0;
        pos[1]=0;

        double ix = px;
        double iy = py;

        ix -= rotX;
        iy -= rotY;

        double anchorx = ix;
        double anchory = iy;
        ix = anchorx + xShear * anchory;
        iy = anchory + yShear * anchorx;

        ix *= xScale;
        iy *= yScale;

        double theta = PI / 180. * -rotation;
        double sin = sin(theta);
        double cos = cos(theta);
        anchorx = ix;
        anchory = iy;
        ix = anchorx * cos + anchory * sin;
        iy = anchory * cos - anchorx * sin;

        ix += rotX;
        iy += rotY;

        ix += transX;
        iy += transY;

        ix = round(ix);
        iy = round(iy);
        pos[0] = (int) ix;
        pos[1] = (int) iy;
    }

    double rot = 0;
    Rectangle rect = new Rectangle(200, 200, 100, 100);
    int[] color = new int[4];
    int[] xColor = new int[4];

    @Override
    protected void paintComponent(Graphics g) {
        super.paintComponent(g);

        WritableRaster raster = bim.getRaster();

        for (int x = 0; x < raster.getWidth(); x++)
            for (int y = 0; y < raster.getHeight(); y++) {
                color[0] = y/2+x/10;
                color[1] = x*y/100;
                color[2] = x/2+y/10;
                color[3] = 255;
                raster.setPixel(x, y, color);
            }

        // draw a rotated rectangle
        {
            double rotation = rot += 3.5;
            double xScale = 2;
            double yScale = 2;
            double rotPointX = rect.width / 2;
            double rotPointY = rect.height / 2;

            // calculate the bounds
            int minx = Integer.MAX_VALUE;
            int miny = Integer.MAX_VALUE;
            int maxx = Integer.MIN_VALUE;
            int maxy = Integer.MIN_VALUE;
            getPositionFromPixel(pos, -1, -1, rect.x, rect.y, rotation, rotPointX, rotPointY, 0, 0, xScale, yScale);
            if (pos[0] < minx) minx = pos[0];
            if (pos[1] < miny) miny = pos[1];
            if (pos[0] > maxx) maxx = pos[0];
            if (pos[1] > maxy) maxy = pos[1];
            getPositionFromPixel(pos, -1, rect.height + 1, rect.x, rect.y, rotation, rotPointX, rotPointY, 0, 0, xScale, yScale);
            if (pos[0] < minx) minx = pos[0];
            if (pos[1] < miny) miny = pos[1];
            if (pos[0] > maxx) maxx = pos[0];
            if (pos[1] > maxy) maxy = pos[1];
            getPositionFromPixel(pos, rect.width + 1, rect.height + 1, rect.x, rect.y, rotation, rotPointX, rotPointY, 0, 0, xScale, yScale);
            if (pos[0] < minx) minx = pos[0];
            if (pos[1] < miny) miny = pos[1];
            if (pos[0] > maxx) maxx = pos[0];
            if (pos[1] > maxy) maxy = pos[1];
            getPositionFromPixel(pos, rect.width + 1, -1, rect.x, rect.y, rotation, rotPointX, rotPointY, 0, 0, xScale, yScale);
            if (pos[0] < minx) minx = pos[0];
            if (pos[1] < miny) miny = pos[1];
            if (pos[0] > maxx) maxx = pos[0];
            if (pos[1] > maxy) maxy = pos[1];

            if (minx < 0) minx = 0;
            if (miny < 0) miny = 0;
            if (maxx > raster.getWidth()) maxx = raster.getWidth();
            if (maxy > raster.getHeight()) maxy = raster.getHeight();

            int argb;
            for (int x = minx; x <= maxx; x++)
                for (int y = miny; y <= maxy; y++) {
                    if (getPixelFromPosition(rect.width, rect.height, pos, x, y, rect.x, rect.y, rotation, rotPointX, rotPointY, 0, 0, xScale, yScale)) {
                        argb = img.getRGB(pos[0], pos[1]);
                        color[3] = (argb >> 24) & 0xff;
                        color[0] = (argb >> 16) & 0xff;
                        color[1] = (argb >> 8) & 0xff;
                        color[2] = (argb) & 0xff;

                        if (x >= 0 && x < raster.getWidth() && y >= 0 && y < raster.getHeight())
                            if (color[3] > 0)
                                raster.setPixel(x, y, color);
                    }
                }
        }

        g.drawImage(bim, 0, 0, null);
    }

    @Override
    public void run() {
        while (true) {
            repaint();
            try {
                Thread.sleep(60);
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
    }

    public static void main(String[] args) {
        JFrame f = new JFrame("XPaintTest");
        f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        f.setLayout(new BorderLayout());
        f.add(new XPaintTest());
        f.pack();
        f.setVisible(true);
    }
}
[/Java]

PS: Wie behandelt man eigendlich den Alphawert eines Pixels wenn man die vorherige Farbe noch sehen soll?


----------



## Marco13 (20. Sep 2010)

Etliche Multiplikationen, Divisionen (!) und trigonometische Funktionen (!!!) für JEDEN Pixel?  :noe: 

Man sollte meinen, dass ein gedrehtes Rechteck zu malen, einfach ist. Ist es aber nicht. Es ist richtig kompliziert. Und das komplizierteste ist es, es für den Computer einfach zu machen 

Ohne mir anmaßen wollen, mich in den Tiefen der Rasterisierung im Detail auszukennen, aber sofern man die letzte Stufe der klassichen 3D-Rendering Pipeline auf den 2D-Fall übertragen kann (wovon ich ausgehe) läuft das ganze GROB(!) und sehr vereinfacht so ab: Man rechnet die Eckpunkte des zu zeichnenden Polygons auf Bildschirmkoordinaten um. (Dabei verwendet man vorzugsweise Matrizen: Die speichern die gesamte Transformation, und man muss selbst bei 1000 Punkten den sinus/cosinus nur EIN map berechnen, und verwendet die resultierende Matrix dann für alle Punkte. Schau dir für den 2D-Fall mal die Klasse "AffineTransform" an). Wenn man die Eckpunkte des Rechtecks erstmal kennt, wird noch ein Clipping durchgeführt (im 3D-Fall schon früher), d.h. man schneidet den Teil weg, der außerhalb des Bildschirms liegt. Und dann läßt man das Ergebnis mit sowas wie Scanline rendering - Wikipedia, the free encyclopedia füllen. Das effizient zu machen kann schon tricky sein (der Bresehnham ist ja bekannt), aber spätestens wenn da noch Farbverläufe und Texturen reinkommen (sozusagen ein "mehrdimensionaler Bresenham") kann das richtig aufwändig werden...


----------



## Steev (20. Sep 2010)

Dankeschön für deine Antwort. Die AffineTransform habe ich mir vor einiger Zeit schonmal angesehen. Allerdings hatte ich da nicht verstanden, warum das so "kompliziert" gemacht wird und alles explizit abgespeichert wird. Mit deiner Erklärung scheint mir dass dann doch recht einfach und logisch zu sein. Ich werde dass dann nochmal umstellen. Ich denke allerdings, dass die meiste Zeit dabei drauf geht, Pixel für Pixel durch eine Bounding-Box zu wandern und zu rendern.
Allerdings finde ich keine andere Lösung. Ich wollte dann bei komplexeren Sachen einen Mechanismus erstellen, der nur das neuzeichnet, was sich auch ändert, glaube aber nicht, dass das nochmal soviel Performance rausholen wird, weil sich in der Art von Spiel, dass ich machen will die Kamera fast ständig bewegt.

Weist du (oder jemand anderes) vieleicht auch noch, wie man die Alpha-Wert-Geschichte realisieren kann?
Mir scheint dass ich da einfach noch einen Knoten im Hirn habe...

Danke und Gruß
Steev


----------



## Marco13 (20. Sep 2010)

Ja, da irgendwas mit Differenzen zu versuchen wäre vom Verwaltungsaufwand sicher höher, als alles in einem Rutsch (und DA dann natürlich so schnell wie möglich) neu zu zeichnen.

Zum Alpha: In OpenGL gibt's sie glBlendFunc ? DGL Wiki und es ist kein Zufall, dass es in Java dann ganz entsprechend das AlphaComposite (Java Platform SE 6) gibt. Es gibt da so verschiedene mögliche "Mischregeln". Beim ersten Link sind aber ein paar schöne Bilder dabei, damit wird vielleicht schneller deutlich, warum auch DAS wieder so "kompliziert" ist  . Man muss ggf. unterschieden, wie die Farbwerte gemischt werden sollen, additiv, subtraktiv, in bezug auf's Alpha oder die Farbe, premultiplied oder nicht, oder soll am Ende vielleicht DOCH einfach drübergepinselt werden...?

Wie auch immer: Hier ist mal ein Programm, bei dem ein Bild "image.jpg" geladen und angezeigt wird, und man mit der Maus so ein halbdurchsichtiges, rotes Rechteck drüberbewegen kann. Unoptimiert, nur als Beispiel.

```
package _main;

import java.awt.Color;
import java.awt.Graphics;
import java.awt.event.MouseEvent;
import java.awt.event.MouseMotionListener;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;

import javax.imageio.ImageIO;
import javax.swing.JFrame;
import javax.swing.JPanel;

public class AlphaTest
{
    public static void main(String args[]) throws IOException
    {
        BufferedImage bi = ImageIO.read(new File("image.jpg"));
        JFrame f = new JFrame();
        f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        f.setSize(800,800);
        TestImagePanel imagePanel = new TestImagePanel(bi); 
        f.getContentPane().add(imagePanel);
        f.setVisible(true);
        
    } 
    
}
class TestImagePanel extends JPanel implements MouseMotionListener
{
    private BufferedImage originalImage;
    private BufferedImage mixedImage;
    
    private Color rectangleColor = new Color(255,0,0,128); // Halbdurchsichtig
    
    public TestImagePanel(BufferedImage originalImage)
    {
        this.originalImage = originalImage;
        mixedImage = new BufferedImage(originalImage.getWidth(), originalImage.getHeight(), BufferedImage.TYPE_INT_RGB);
        addMouseMotionListener(this);
    }
    
    public void paintComponent(Graphics g)
    {
        super.paintComponent(g);
        g.drawImage(mixedImage,0,0,this);
    }
    
    @Override
    public void mouseMoved(MouseEvent e)
    {
        Graphics g = mixedImage.createGraphics();
        g.drawImage(originalImage, 0,0, this);
        g.dispose();
        
        int w = 100;
        int h = 100;
        for (int x=0; x<w; x++)
        {
            for (int y=0; y<h; y++)
            {
                int cx = e.getX()-x;
                int cy = e.getY()-y;
                
                if (cx>=0 && cx<mixedImage.getWidth() &&
                    cy>=0 && cy<mixedImage.getHeight())
                {
                    int input = originalImage.getRGB(cx, cy);
                    int added = rectangleColor.getRGB();
                    int newColor = mix(input, added);
                    mixedImage.setRGB(cx,cy,newColor);
                }
            }
        }
        repaint();
        
    }
    
    private int mix(int c0, int c1)
    {
        int a0 = (c0 >> 24) & 0xFF;
        int r0 = (c0 >> 16) & 0xFF;
        int g0 = (c0 >>  8) & 0xFF;
        int b0 = (c0 >>  0) & 0xFF;
        int a1 = (c1 >> 24) & 0xFF;
        int r1 = (c1 >> 16) & 0xFF;
        int g1 = (c1 >>  8) & 0xFF;
        int b1 = (c1 >>  0) & 0xFF;
        
        // "Normales Blending" von [url=http://wiki.delphigl.com/index.php/glBlendFunc]glBlendFunc ? DGL Wiki[/url] 
        float oneMinusSrcAlpha =  (255 - a1) / 256.0f;
        float srcAlpha =  a1 / 256.0f;
        int r2 = (int)(r0 * oneMinusSrcAlpha + r1 * srcAlpha);
        int g2 = (int)(g0 * oneMinusSrcAlpha + g1 * srcAlpha);
        int b2 = (int)(b0 * oneMinusSrcAlpha + b1 * srcAlpha);
        int a2 = (int)(a0 * oneMinusSrcAlpha + a1 * srcAlpha);
        
        r2 = clamp(r2);
        g2 = clamp(g2);
        b2 = clamp(b2);
        a2 = clamp(a2);
        
        //System.out.println("mix "+r0+" "+g0+" "+b0+" "+a0);
        //System.out.println("add "+r1+" "+g1+" "+b1+" "+a1);
        //System.out.println("is: "+r2+" "+g2+" "+b2+" "+a2);
        
        int result = 
            (a2 << 24) |
            (r2 << 16) |
            (g2 <<  8) |
            (b2 <<  0);
        return result;
    }
    
    private static int clamp(int n)
    {
        if (n > 255)
        {
            return 255;
        }
        if (n < 0)
        {
            return 0;
        }
        return n;
    }

    @Override
    public void mouseDragged(MouseEvent e)
    {
    }

    
    
}
```


----------

