# 3d Engine : Fragment Shader , aber wie?



## CreepyPvP (16. Jan 2018)

Hallo , ich schreibe zurzeit eine 3d Engine ohne Libary(ausser JOCL. für Grafikkartenzugriff). Mein letztes großes Problem ist : man hat ein Mesh (Dreieck), nachdem man einen Vertex Shader für alle seine Ecken ausgeführt hat. Wie könnte man nun einen Fragment Shader für jeden Punkt in diesem Mesh ausführen(man sollte natürlich die Koordinaten des jeweiligen Pixels haben). Natürlich könnte man auch die Java Klasse Polygon mit der contains() Methode benutzen. Ich wäre für Lösungsansätze (auch in Pseudocode) wie man jeden Pixel im Mesh und seine Koordinaten erfasst sehr Dankbar.
Grüsse Creepy


----------



## Blender3D (17. Jan 2018)

```
void triangleScanVerts ( Vektor3D A, Vektor3D B, Vektor3D C, float step ){
    Vektor3D DIR_c = B-A; // Richtung entlang Seite c
    Vektor3D DIR_b = C-A; // Richtung entlang Seite b
    Vektor3D DIR_a = C-B; // Richtung entlang Seite a
    DIR_c = DIR_c.norm().mul(step);
    DIR_b = DIR_b.norm().mul(step);
    DIR_a = DIR_a.norm().mul(step);
    Vektor3D START = A;
    Vektor3D END = B;

    while( !START.isInEpsilonOf( C, step ) ){
        GO = START;
        while( !GO.isInEpsilonOf(END, step ){
            // bewege GO in Richtung END entlang Seite c
            GO = GO.add( DIR_c );

            .. rufe gewünschte Operation für den Punkt GO auf
        }
        // bewege START in Richtung C entlang Seite b
        START = START.add( DIR_b );

        // bewege END in Richtung C entlang Seite a
        END = END.add( DIR_a );
    }
}
```
Nicht ganz durchdacht aber vielleicht hilft es!


----------



## CreepyPvP (17. Jan 2018)

Ist die Klasse Vector3D schon vorhanden oder woher kommen die Methoden isInEpsilonOf() oder add()?
Und was bedeutend mul(step) und wofür steht step?
Grüsse Creepy


----------



## Blender3D (17. Jan 2018)

CreepyPvP hat gesagt.:


> Ist die Klasse Vector3D schon vorhanden oder woher kommen die Methoden isInEpsilonOf() oder add()?
> Und was bedeutend mul(step) und wofür steht step?
> Grüsse Creepy


Die Klasse Vector3D musst Du Dir selbst bauen. Oder Du hast schon etwas ähnliches in Deiner 3D engine.


Blender3D hat gesagt.:


> isInEpsilonOf(END, step ){




```
static boolean isInEpsilonOf( Vector3D a, Vector3D b, float range ){
    // Ist a innerhalb des Abstandes range zu b
    return  Math.abs( (a.sub(b)).length()) <= range );
}
```
könnte man in etwa so bauen.
Der Code oben ist eine Art von Pseudocode.
mul( step  ) steht für die Multiplikation eines Vektors mit einer reellen Zahl. Step ist die Schrittweit (Auflösung) in der Du Dich bewegen willst. Zwischen zwei Zahlen gibt es unendlich viele Zahlen. --> Du kannst nur eine gewisse Anzahl davon behandeln. step = 1 oder step = 0.1 ( 10 mal mehr ) usw.
add()    steht für die Addition von 2 Vektoren.
norm()  steht für die Normierung des Vektors --> er hat die Länge 1.


----------



## CreepyPvP (17. Jan 2018)

Wofür steht die Methode sub(Vector3D) ?


----------



## Blender3D (17. Jan 2018)

Subtraktion Vektor von Vektor
V a = (10,4,4);
V b = (1,1,1);
V a.sub( b ) = (9,3,3)


----------



## CreepyPvP (17. Jan 2018)

OK und length() ist dann die Länge von dem Vector, nicht?


----------



## Blender3D (17. Jan 2018)

klar


----------



## Blender3D (17. Jan 2018)

Die Geschwindigkeit entlang a und b muss man noch angleichen um von beiden Seiten gleichzeitig im Punkt C zu landen.

```
void triangleScanVerts ( Vektor3D A, Vektor3D B, Vektor3D C, float step ){
     Vektor3D DIR_c = B.sub(A); // Richtung entlang Seite c
     Vektor3D DIR_b = C.sub(A); // Richtung entlang Seite b
     Vektor3D DIR_a = C.sub(B); // Richtung entlang Seite a
     DIR_a = DIR_a.norm().mul( step * DIR_a.length() / DIR_b.lengt() ); // Geschwindigkeit entlang a und b parallel halten
     DIR_c = DIR_c.norm().mul(step);
     DIR_b = DIR_b.norm().mul(step);
    
     Vektor3D START = A;
     Vektor3D END = B;

     while( !START.isInEpsilonOf( C, step ) ){
         GO = START;
         while( !GO.isInEpsilonOf(END, step ){
             // bewege GO in Richtung END entlang Seite c
             GO = GO.add( DIR_c );

             .. rufe gewünschte Operation für den Punkt GO auf
         }
         // bewege START in Richtung C entlang Seite b
         START = START.add( DIR_b );

         // bewege END in Richtung C entlang Seite a
         END = END.add( DIR_a );
     }
}
```


----------



## CreepyPvP (18. Jan 2018)

Blender3D hat gesagt.:


> void triangleScanVerts ( Vektor3D A, Vektor3D B, Vektor3D C, float step ){
> Vektor3D DIR_c = B.sub(A); // Richtung entlang Seite c
> Vektor3D DIR_b = C.sub(A); // Richtung entlang Seite b
> Vektor3D DIR_a = C.sub(B); // Richtung entlang Seite a
> ...


Erzeugt das nicht eine Endlos-Schleife? Dieser Code hat NICHT funktioniert. die Funktion wird beim ersten Mesh einmal begonnen und nicht wieder verlassen. Deswegen gehe ich davon aus, das hier eine Endlos Schleife erzeugt wird.
Grüsse Creepy


----------



## Blender3D (19. Jan 2018)

CreepyPvP hat gesagt.:


> für Lösungsansätze (auch in Pseudocode)


Der Code ist nicht getestet. Wie oben beschrieben nicht ganz durchdacht. Aber er zeigt die Möglichkeit auf wie die Punkte im Dreieck durchlaufen werden. Ein Problem im obigen Code ist die Abbruchbedingung. Wenn step über das Ziel läuft -->

```
void triangleScanVerts ( Vektor3D A, Vektor3D B, Vektor3D C, float step ){
     Vektor3D DIR_c = B.sub(A); // Richtung entlang Seite c
     Vektor3D DIR_b = C.sub(A); // Richtung entlang Seite b
     Vektor3D DIR_a = C.sub(B); // Richtung entlang Seite a
     DIR_a = DIR_a.norm().mul( step * DIR_a.length() / DIR_b.lengt() ); // Geschwindigkeit entlang a und b parallel halten
     double lenght_a = DIR_a.lenght();
     DIR_c = DIR_c.norm().mul(step);
     DIR_b = DIR_b.norm().mul(step);
 
     Vektor3D START = A;
     Vektor3D END = B;
     double lenght_a = (C.sub(B)).lenght();
     while(  lenght_a - (C.sub(END)).lenght() >= 0  ){
         GO = START;
         double lenght = (END.sub(START)).lenght();
         while( lenght - (GO.sub(START)).length() >= 0 ){
             // bewege GO in Richtung END entlang Seite c
             GO = GO.add( DIR_c );

             .. rufe gewünschte Operation für den Punkt GO auf
         }
         // bewege START in Richtung C entlang Seite b
         START = START.add( DIR_b );

         // bewege END in Richtung C entlang Seite a
         END = END.add( DIR_a );
     }
}
```
Auch muss die Vector3D Klasse korrekt implementiert sein.


----------



## Blender3D (20. Jan 2018)

Blender3D hat gesagt.:


> DIR_a = DIR_a.norm().mul( step * DIR_a.length() / DIR_b.lengt() ); // Geschwindigkeit entlang a und b parallel halten
> double lenght_a = DIR_a.lenght();


Die Zeilen vertauschen!!


----------



## CreepyPvP (21. Jan 2018)

Wie lautet nun der korrekte Code. Bei mir funktioniert das irgendwie nicht so ganz .... :/


Blender3D hat gesagt.:


> Der Code ist nicht getestet. Wie oben beschrieben nicht ganz durchdacht. Aber er zeigt die Möglichkeit auf wie die Punkte im Dreieck durchlaufen werden. Ein Problem im obigen Code ist die Abbruchbedingung. Wenn step über das Ziel läuft -->


Das habe ich leider nicht so ganz hinbekommen


----------



## Blender3D (22. Jan 2018)

Die unten gezeigte Version füllt ein Dreieck, das durch Mausklicks definiert wird, mit roter Farbe. Es handelt sich zwar um eine 2D Version aber der Algorithmus funktioniert in 3D genau so. Außerdem ist die verwendete Vektorklasse konstant, weil diese in der Anwendung leichter verständlich ist.
Für eine Grafikengine empfiehlt es sich eine nicht konstante Klasse zu kreieren, da das einen Geschwindigkeitsvorteil mit sich bringt weil die wiederholte Addition dann nicht ständig einen neuen Vektor erzeugt sondern nur die Koordinaten des benutzen Vektors abändert.
https://www.java-forum.org/thema/variablen-voneinander-abhaengig.180145/page-4#post-1144996


----------



## Blender3D (22. Jan 2018)

```
import java.awt.Point;

public final class Vector2D {
    final private double x;
    final private double y;

    public Vector2D(Vector2D v) {
        x = v.x;
        y = v.y;
    }

    public Vector2D(double x, double y) {
        this.x = x;
        this.y = y;
    }
    public Vector2D add(Vector2D v) {
        return new Vector2D(x + v.x, y + v.y);
    }
    public double getX() {
        return x;
    }
    public double getY() {
        return y;
    }
    public double lenght() {
        return Math.sqrt(x * x + y * y);
    }
    public Vector2D mul(double value) {
        return new Vector2D(x * value, y * value);
    }
    public double mulSkalar(Vector2D v) {
        return x * v.x + y * v.y;
    }
    public Vector2D norm() {
        return mul(1.0 / lenght());
    }
    public Vector2D sub(Vector2D v) {
        return new Vector2D(x - v.x, y - v.y);
    }
    public Point toPoint() {
        return new Point((int) Math.round(x), (int) Math.round(y));
    }
    @Override
    public String toString() {
        return String.format("[%.2f|%.2f]", x, y);
    }
}
```


```
import java.awt.Color;
import java.awt.image.BufferedImage;

public class TriangleTools {
    public static void triangleColorFill(BufferedImage img, Vector2D A, Vector2D B, Vector2D C, float step,
            Color fill) {
        if (img == null)
            return;
        Vector2D DIR_c = B.sub(A); // Richtung entlang Seite c
        Vector2D DIR_b = C.sub(A); // Richtung entlang Seite b
        Vector2D DIR_a = C.sub(B); // Richtung entlang Seite a
        int rgb = fill.getRGB();
        int width = img.getWidth();
        int height = img.getHeight();

        // Geschwindigkeit entlang a und b parallel halten
        double factor = step * DIR_a.lenght() / DIR_b.lenght();
        DIR_a = DIR_a.norm().mul(factor);
        DIR_c = DIR_c.norm().mul(step);
        DIR_b = DIR_b.norm().mul(step);

        Vector2D START = A;
        Vector2D END = B;
        while ((C.sub(END)).lenght() > step) {        
            Vector2D GO = START;        
            while ((GO.sub(END)).lenght() > step) {
                // bewege GO in Richtung END entlang Seite c
                int x = (int) Math.round(GO.getX());
                int y = (int) Math.round(GO.getY());
                if (x >= 0 && x <= width - 1 && y >= 0 && y <= height - 1)
                    img.setRGB(x, y, rgb);
                GO = GO.add(DIR_c);
            }

            // bewege START in Richtung C entlang Seite b
            START = START.add(DIR_b);
            // bewege END in Richtung C entlang Seite a
            END = END.add(DIR_a);
        }
    }
}
```


```
import java.awt.Color;
import java.awt.Dimension;
import java.awt.Graphics;
import java.awt.GraphicsConfiguration;
import java.awt.GraphicsEnvironment;
import java.awt.Point;
import java.awt.event.MouseEvent;
import java.awt.event.MouseListener;
import java.awt.image.BufferedImage;
import javax.swing.JPanel;
import shader.TriangleTools;
import shader.Vector2D;

@SuppressWarnings("serial")
public class TestTriangel extends JPanel implements MouseListener {
    public final static int A = 0;
    public final static int B = 1;
    public final static int C = 2;
    private Vector2D[] point = new Vector2D[3];
    private int clickCnt = 0;
    private final GraphicsConfiguration gfxConf = GraphicsEnvironment.getLocalGraphicsEnvironment()
            .getDefaultScreenDevice().getDefaultConfiguration(); // used to create image for drawing
    private BufferedImage imageBuffer = null; // used to draw graphics

    public TestTriangel(int width, int height) {
        super.setPreferredSize(new Dimension(width, height));
        addMouseListener(this);
    }

    private void drawTriangle(Graphics g) {
        if (point[A] != null && point[B] != null && point[C] != null) {
            TriangleTools.triangleColorFill(imageBuffer, point[A], point[B], point[C], .1f, Color.RED);
            Point[] p = { point[A].toPoint(), point[B].toPoint(), point[C].toPoint() };
            g.setColor(Color.WHITE);
            g.drawLine(p[A].x, p[A].y, p[B].x, p[B].y);
            g.drawLine(p[B].x, p[B].y, p[C].x, p[C].y);
            g.drawLine(p[C].x, p[C].y, p[A].x, p[A].y);
        }
    }

    @Override
    protected void paintComponent(Graphics g) {
        super.paintComponent(g);
        updateGraphics();
        g.drawImage(imageBuffer, 0, 0, this);
    }

    @Override
    public void mouseClicked(MouseEvent e) {

    }

    @Override
    public void mouseEntered(MouseEvent e) {
    }

    @Override
    public void mouseExited(MouseEvent e) {
    }

    @Override
    public void mousePressed(MouseEvent e) {
    }

    @Override
    public void mouseReleased(MouseEvent e) {
        if (clickCnt > 2) {
            clickCnt = 0;
            resetTriangle();
            repaint();
        }
        Point p = e.getPoint();
        point[clickCnt] = new Vector2D(p.x, p.y);
        clickCnt++;

        if (clickCnt == 3)
            repaint();
    }

    private void resetTriangle() {
        for (int i = 0; i < point.length; i++)
            point[i] = null;

    }

    private void updateGraphics() {
        if (imageBuffer == null || imageBuffer.getWidth() != getWidth() || imageBuffer.getHeight() != getHeight()) {
            imageBuffer = gfxConf.createCompatibleImage(getWidth(), getHeight());
        }
        Graphics g = imageBuffer.createGraphics();
        g.setColor(Color.BLACK);
        g.fillRect(0, 0, getWidth(), getHeight());
        drawTriangle(g);
        g.dispose();
    }
}
```


```
import javax.swing.JFrame;

public class start {
    public static void main(String[] args) {
        JFrame f = new JFrame();
        TestTriangel triangle = new TestTriangel(500, 500);
        f.getContentPane().add(triangle);
        f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        f.pack();
        f.setResizable(false);    
        f.setTitle("klick on 3 positions for a triangle");
        f.setVisible(true);
    }
}
```

Ich habe Dir eine getestet Version für ein Fill eines Dreiecks in 2D gebaut. Probiere die aus. Wenn Du daraus eine 3D Version machst kannst Du die dann verwenden.
Starte das Programm und klicke im Fenster auf 3 Punkte. --> Es wird ein Dreieck mit roter Farbe über die Funktion gefüllt.


----------



## mrBrown (22. Jan 2018)

Blender3D hat gesagt.:


> Für eine Grafikengine empfiehlt es sich eine nicht konstante Klasse zu kreieren, da das einen Geschwindigkeitsvorteil mit sich bringt weil die wiederholte Addition dann nicht ständig einen neuen Vektor erzeugt sondern nur die Koordinaten des benutzen Vektors abändert.


Endlich mal ein schöner Benchmark für sowas 

Ist der Code so korrekt mit "mutable" Vektoren umgesetzt?
(Vektor ist der gleiche wie deiner, nur wird statt jedem new der Vektor verändert und nichts zurückgegeben)


```
public class MutTriangleTools {
    public static void triangleColorFill(BufferedImage img, MutVector2D A, MutVector2D B, MutVector2D C, float step,
                                         Color fill) {
        if (img == null) {
            return;
        }


        final MutVector2D DIR_c = new MutVector2D(B);
        DIR_c.sub(A); // Richtung entlang Seite c
        final MutVector2D DIR_b = new MutVector2D(C);
        DIR_b.sub(A); // Richtung entlang Seite b
        final MutVector2D DIR_a = new MutVector2D(C);
        DIR_a.sub(B); // Richtung entlang Seite a


        int rgb = fill.getRGB();
        int width = img.getWidth();
        int height = img.getHeight();

        // Geschwindigkeit entlang a und b parallel halten
        double factor = step * DIR_a.lenght() / DIR_b.lenght();
        DIR_a.norm();
        DIR_a.mul(factor);
        DIR_c.norm();
        DIR_c.mul(step);
        DIR_b.norm();
        DIR_b.mul(step);


        MutVector2D START = new MutVector2D(A);
        MutVector2D END = new MutVector2D(B);
        while (C.dist(END) > step) {
            MutVector2D GO = new MutVector2D(START);
            while (GO.dist(END) > step) {
                // bewege GO in Richtung END entlang Seite c
                int x = (int) Math.round(GO.getX());
                int y = (int) Math.round(GO.getY());
                if (x >= 0 && x <= width - 1 && y >= 0 && y <= height - 1) {
                    img.setRGB(x, y, rgb);
                }
                GO.add(DIR_c);
            }

            // bewege START in Richtung C entlang Seite b
            START.add(DIR_b);
            // bewege END in Richtung C entlang Seite a
            END.add(DIR_a);
        }
    }
```


----------



## Blender3D (24. Jan 2018)

CreepyPvP hat gesagt.:


> Das habe ich leider nicht so ganz hinbekommen


Hast Du es jetzt hinbekommen?


----------



## CreepyPvP (30. Jan 2018)

Blender3D hat gesagt.:


> Hast Du es jetzt hinbekommen?


Ja vielen Dank!   Das hat mir sehr geholfen


----------

