# 3D Graphen Zeichnen



## theBigJimmy (23. Nov 2010)

Hallo zusammen,

ich hoffe ich habe dieses oder ein ähnliches Thema im Forum nicht übersehen. Ich habe einen Datensatz drei-dimensionaler Punkt. Zusätzlich habe ich zu jedem Punkt eine Adjazenzliste vorliegen... kurz gesagt: Ich habe einen ungerichteten geographischen Graphen im R^3. Diesen möchte ich jetzt zeichnen, sodass ich anschließend mit der Maus die Perspektive per Drag & Drop verändern kann. Das Ding muss überhaupt nicht toll aussehen. Es muss nur ein Frame sein, indem ein paar Punkte liegen, die mit ein Paar linien verbunden sind.

Könnte mir jemand hier mal ein Codebeispiel posten. Wichtig wäre der "Rahmen"... also, was ich importieren muss, wie ich ein geeignetes Fenster erzeuge usw.

Vielen Dank im Vorraus für die Mühe


----------



## Marco13 (24. Nov 2010)

Hm. Und WIE "schlecht" darf es sein? Sowas wie 3D Model: Cube oder vielleicht doch JOGL? (Warte mal, bald gibt's hier ein KSKB dazu, aber für mich ist es dafür im Moment _too late_  )


----------



## ThreadPool (24. Nov 2010)

Bevor du dir einen abquälst kannst du auch auf fertige OSS Produkte wie z.B. Gephi, an open source graph visualization and manipulation software zurückgreifen.


----------



## theBigJimmy (24. Nov 2010)

Hallo, 

danke erst einmal für die Antworten. Es darf sehr schlicht sein. Ich habe Datensätze mit bis zu 200000 Knoten und O(n) vielen Kanten. Von daher ist es sogar besser aus Performancegründen. Also das kleine Besipeil reicht völlig aus!!!! Ich brauche einfach nur kleine Knoten (z.B. kleine Kugeln) und Kanten. 
Ein fertiges Grundgerüst (code) in dem besiepielhaft Punkte und linien gezeichnet werden wäre optimal, dann könnte ich mir den Rest selber zusammen bauen.

Das Programm gucke ich mir mal an, danke auch dafür.

Viele Grüße


----------



## theBigJimmy (25. Nov 2010)

Hallo,

ich habe nun das erste Zeichnen von Objekten hinbekommen. Nocheinmal mein schlichtes Problem:

Ich habe N Punkte bzw. dessen 3D Koordinaten vorliegen und möchte diese im gleichen Koordinatensystem bzgl. ihrer Koordinaten platzieren. Zusätzlich möchte ich zwischen speziellen Knoten Kanten ziehen, also zwischen speziellen Punkten Segmente/Linien malen. Das gesamte Konstrukt soll dann im Raum gedreht/gezommt werden können... mit Maus oder ähnlichem...

Mein Ansatz bisher sieht so aus, dass ich zunächst ein übergeordnetes Objekt vom Typ TransformGroup anlege. Dieses versehe ich mit den entsprechenden Mouse/Tastatur-Events:


```
TransformGroup rootTransformGroup = new TransformGroup();

rootBranchGroup.addChild(rootTransformGroup);
rootTransformGroup.setCapability(TransformGroup.ALLOW_TRANSFORM_WRITE);
...
MouseRotate mouseRotate = new MouseRotate();
mouseRotate.setTransformGroup(rootTransformGroup); //!!!!!!!!!!
mouseRotate.setSchedulingBounds(boundingSphere);
rootBranchGroup.addChild(mouseRotate);
[\code]

Dann erezuege ich für jeden Punkt eine neues Objekt rootTransformGroup2 vom Typ TransformGroup und hänge an dieses ein Objekt vom Typ Transform3D, welches wiederum mit einem Vektor Vector3f versehen wird, welcher der Verschiebung des Punktes entspricht. Anschließend hänge ich  rootTransformGroup2 als Kind an rootTransformGroup, damit die Benutzer-Interaktive Veränderung der viewer Position sich auf alle Punkte auswirkt:

[code]
Transform3D transform3d = new Transform3D();
transform3d.setTranslation(new Vector3f(0.2f,0.00f,0.00f));
TransformGroup rootTransformGroup2 = new TransformGroup(transform3d);
rootTransformGroup2.addChild(new Box(0.6f,0.1f,0.1f,ap));
rootTransformGroup.addChild(rootTransformGroup2);
[\code]

Da ich Anfäner auf dem Gebiet Java3D bin kann es jetzt natürlich sein, dass ich mit der 3D Schrotflinte auf Punkte-Spatzen schieße... aber dafür frage ich jetzt ja euch. Ein weiteres Problem ist auch noch das ziehen der Kanten zwischen den einzelnen Punkten, die ich momentan als kleine Box'en zeichne...

Es wäre wirklich sehr nett, wenn mir jemand helfen könnte.

Vielen dank im Vorraus für eure Mühe.
Viele Grüße
```


----------



## Marco13 (25. Nov 2010)

Das mit der "Schrotflinte" _könnte_ zutreffen: Ich bin mir nicht sicher, wie es bei Java3D mit 200000 Boxes im Szenegraphen aussieht - das _könnte_ ziemlich langsam werden. Vielleicht erstmal einen Dummy-Test machen, wo du einfach 200000 Boxes (Spheres???) und 1 Million Linien (Kanten - Cylinders?) einfügst, und schaust, ob das überhaupt in vertretbarer Zeit renderbar ist...


----------



## theBigJimmy (25. Nov 2010)

Ja, werde ich tun. Genau so hatte ich mir das jetzt auch gedacht: Knoten werden durch Boxen oder Spheren und Kanten durch dünne Cylinder dargestellt.

Btw: Wie richte ich die Kanten bzw. Zylinder aus? Ich kenne die Endpunkte, also die beiden Adjazenten Knoten, kann aber keine Translation finden, mit der ich den Zylinder so ausrichten, kann so dass er eine Verbindung zwischen beiden Punkten darstellt?


----------



## Marco13 (25. Nov 2010)

Der Zylinder ist anfangs ... ähm ich glaube senkrecht aufgestellt, also seine Achse ist AFAIR der Einheitsvektor C=(0,1,0). Wenn man zwei Punkte P,Q hat, berechnet dann den Winkel a=angle(C,Q-P) und das Kreuzprodukt A=Cx(Q-P), und dreht den Zylinder dann um die Achse A um den Winkel a. Grenzfälle abfangen (Winkel 180° -> Kreuzprodukt wird 0,0,0)

EDIT: Auf die richtige Länge skalieren und zum Punkt P verschieben sollte ja klar sein...


----------



## theBigJimmy (25. Nov 2010)

Ok, ich habe jetzt einen Testdurchlauf mit 25000 Knoten gemacht und ohne Kanten. Die Punktmenge läßt sich nur sehr grob verschieben... also ein Drag&Drop mit der Maus reagiert erst 1-2 Sekunden später. Ich entwickle auf meinem Laptop. Allerdings habe ich in meinem Desktop ne GeForce GTX260... Java greift hier doch direkt auf die Grafikhardware zu, richtig? Dann müsste das Ding doch wieder rennen, richtig?
Ich probier es gleich mal aus und berichte dann.

Die Kanten realisiere ich dann anschließend.

Viele Grüße


----------



## theBigJimmy (25. Nov 2010)

Ich versuche seid Stunden, die Kanten in Form der Zylinder zu ziehen, bekomme das aber einfach nicht mit deser Winkelrotation hin.

Ich habe wie gesagt zwei Punkte in Form derer Koordinaten im R^3 gegeben, versuche jetzt einen Zylinder zu berechnen, der als Kante fungiert. Die Positinierung hat geklappt... Einfach eine Vektor-Translation auf den Mittelpunkt des verbindenden Segmentes setzen...

Aber jetzt die Berechnung wie der Zylinder gedreht werden muss, damit er die beiden Punkt verbindet bekomme ich einfach nicht hin. Konzeptionell ist mir was ich machen muss, siehe vroherige Antwort... aber ich kriegs nicht umgesetzt!!!


----------



## Marco13 (26. Nov 2010)

Wenn du ein KSKB postest, mit einer (leeren) Methode
void computeTransform(Point3f p0, Point3f p1, Matrix4f transform)
die in "transform" die Rotation für den Zylinder speichern soll, kann ich morgen mal versuchen, sie auszufüllen.


----------



## theBigJimmy (26. Nov 2010)

import javax.media.j3d.BoundingSphere;
import javax.media.j3d.BranchGroup;
import javax.media.j3d.Canvas3D;
import javax.media.j3d.TransformGroup;
import javax.media.j3d.Appearance;
import javax.media.j3d.ColoringAttributes;
import javax.media.j3d.PointAttributes;
import javax.media.j3d.Transform3D;





import javax.swing.JFrame;
import javax.vecmath.Point3d;
import javax.vecmath.Point3f;
import javax.vecmath.Matrix4f;
import javax.vecmath.Color3f;
import javax.vecmath.Vector3f;
import javax.vecmath.AxisAngle4d;


import com.sun.j3d.utils.behaviors.keyboard.KeyNavigatorBehavior;
import com.sun.j3d.utils.behaviors.mouse.MouseRotate;
import com.sun.j3d.utils.behaviors.mouse.MouseTranslate;
import com.sun.j3d.utils.behaviors.mouse.MouseZoom;
import com.sun.j3d.utils.geometry.ColorCube;
import com.sun.j3d.utils.universe.SimpleUniverse;
import com.sun.j3d.utils.geometry.Sphere;
import com.sun.j3d.utils.geometry.Box;
import com.sun.j3d.utils.geometry.Cylinder;


import java.io.File;
import java.io.BufferedReader;
import java.io.FileReader;

import java.util.LinkedList;

import java.lang.Math;




/**
 * @author Thomas.Darimont
 * 
 */
public class test2 extends JFrame{
	public void computeTransform(Point3f p0, Point3f p1, Matrix4f transform){

	}


	public test2() throws Exception{
        super("test2");
        setDefaultCloseOperation(EXIT_ON_CLOSE);

        Canvas3D canvas = new Canvas3D(SimpleUniverse.getPreferredConfiguration());
        canvas.setSize(320, 240);
        SimpleUniverse simpleUniverse = new SimpleUniverse(canvas);
        simpleUniverse.getViewingPlatform().setNominalViewingTransform();

        BranchGroup rootBranchGroup = new BranchGroup();
        TransformGroup rootTransformGroup = new TransformGroup();

        rootBranchGroup.addChild(rootTransformGroup);
        rootTransformGroup.setCapability(TransformGroup.ALLOW_TRANSFORM_WRITE);

        Appearance ap = new Appearance();
        ColoringAttributes ca = new ColoringAttributes();        
        ca.setColor(0f,0f,150f);        
        ap.setColoringAttributes(ca);

		Transform3D transform3d = new Transform3D();
    	transform3d.setTranslation(new Vector3f(0.4f,0.1f,0.2f));
    	TransformGroup rootTransformGroup2 = new TransformGroup(transform3d);
    	rootTransformGroup2.addChild(new Box(0.02f,0.02f,0.02f,ap));
    	rootTransformGroup.addChild(rootTransformGroup2);

    	Transform3D transform3d2 = new Transform3D();
    	transform3d2.setTranslation(new Vector3f(-0.1f,0.2f,-0.6f));
    	TransformGroup rootTransformGroup3 = new TransformGroup(transform3d2);
    	rootTransformGroup3.addChild(new Box(0.02f,0.02f,0.02f,ap));
    	rootTransformGroup.addChild(rootTransformGroup3);

    	BoundingSphere boundingSphere = new BoundingSphere(new Point3d(0,0,0),10000);

    	MouseRotate mouseRotate = new MouseRotate();
    	mouseRotate.setTransformGroup(rootTransformGroup); //!!!!!!!!!!
    	mouseRotate.setSchedulingBounds(boundingSphere);
    	rootBranchGroup.addChild(mouseRotate);

    	MouseTranslate mouseTranslate = new MouseTranslate();
    	mouseTranslate.setTransformGroup(rootTransformGroup); //!!!!!!!!!!!
    	mouseTranslate.setSchedulingBounds(boundingSphere);
    	rootBranchGroup.addChild(mouseTranslate);



    	MouseZoom mouseZoom = new  MouseZoom();
    	mouseZoom.setTransformGroup(rootTransformGroup); //!!!!!!!!!
    	mouseZoom.setSchedulingBounds(boundingSphere);
    	rootBranchGroup.addChild(mouseZoom);

    	KeyNavigatorBehavior keyNavigatorBehavior = new KeyNavigatorBehavior(rootTransformGroup);
    	keyNavigatorBehavior.setSchedulingBounds(boundingSphere);
    	rootBranchGroup.addChild(keyNavigatorBehavior);

    rootBranchGroup.compile();

    simpleUniverse.addBranchGraph(rootBranchGroup);


    add(canvas);
    pack();
    setVisible(true);
	}
	public static void main(String[] args)  throws Exception {
		// TODO Auto-generated method stub
		test2 t = new test2();
	}

}


----------



## Marco13 (26. Nov 2010)

```
import javax.media.j3d.BoundingSphere;
import javax.media.j3d.BranchGroup;
import javax.media.j3d.Canvas3D;
import javax.media.j3d.TransformGroup;
import javax.media.j3d.Appearance;
import javax.media.j3d.ColoringAttributes;
import javax.media.j3d.PointAttributes;
import javax.media.j3d.Transform3D;

import javax.swing.JFrame;
import javax.vecmath.Point3d;
import javax.vecmath.Point3f;
import javax.vecmath.Matrix4f;
import javax.vecmath.Color3f;
import javax.vecmath.Vector3f;
import javax.vecmath.*;

import com.sun.j3d.utils.behaviors.keyboard.KeyNavigatorBehavior;
import com.sun.j3d.utils.behaviors.mouse.MouseRotate;
import com.sun.j3d.utils.behaviors.mouse.MouseTranslate;
import com.sun.j3d.utils.behaviors.mouse.MouseZoom;
import com.sun.j3d.utils.geometry.ColorCube;
import com.sun.j3d.utils.universe.SimpleUniverse;
import com.sun.j3d.utils.geometry.Sphere;
import com.sun.j3d.utils.geometry.Box;
import com.sun.j3d.utils.geometry.Cylinder;

import java.io.File;
import java.io.BufferedReader;
import java.io.FileReader;

import java.util.LinkedList;

import java.lang.Math;

/**
 * @author Thomas.Darimont
 *
 */
public class AlignTest extends JFrame
{
    public void computeTransform(Vector3f p0, Vector3f p1, Matrix4f transform)
    {
        Vector3f direction = new Vector3f();
        direction.sub(p1, p0);
        float length = direction.length();

        // Compute rotation axis
        Vector3f axis = new Vector3f();
        Vector3f Y_AXIS = new Vector3f(0,1,0);
        axis.cross(direction, Y_AXIS);

        // Rotate cylinder around axis
        if (axis.lengthSquared() > 1e-6)
        {
            float angle = direction.angle(Y_AXIS);
            AxisAngle4f axisAngle = new AxisAngle4f(axis, -angle);
            transform.set(axisAngle);
        }
        Matrix4f m = new Matrix4f();

        // Move bottom of cylinder to p0
        m.setIdentity();
        m.setTranslation(p0);
        transform.mul(m, transform);

        // Scale cylinder to appropriate length
        m.setIdentity();
        m.m11 = length;
        transform.mul(m);

        // Move bottom of cylinder to origin
        m.setIdentity();
        m.m13 = 0.5f;
        transform.mul(m);
    }

    public AlignTest() throws Exception
    {
        super("AlignTest");
        setDefaultCloseOperation(EXIT_ON_CLOSE);

        Canvas3D canvas = new Canvas3D(
            SimpleUniverse.getPreferredConfiguration());
        canvas.setSize(320, 240);
        SimpleUniverse simpleUniverse = new SimpleUniverse(canvas);
        simpleUniverse.getViewingPlatform().setNominalViewingTransform();

        BranchGroup rootBranchGroup = new BranchGroup();
        TransformGroup rootTransformGroup = new TransformGroup();

        rootBranchGroup.addChild(rootTransformGroup);
        rootTransformGroup.setCapability(TransformGroup.ALLOW_TRANSFORM_WRITE);

        Appearance ap = new Appearance();
        ColoringAttributes ca = new ColoringAttributes();
        ca.setColor(0f, 0f, 150f);
        ap.setColoringAttributes(ca);

        Vector3f p0 = new Vector3f(0.4f, 0.5f, 0.2f);
        Transform3D transform3d = new Transform3D();
        transform3d.setTranslation(p0);
        TransformGroup rootTransformGroup2 = new TransformGroup(transform3d);
        rootTransformGroup2.addChild(new Box(0.02f, 0.02f, 0.02f, ap));
        rootTransformGroup.addChild(rootTransformGroup2);

        Vector3f p1 = new Vector3f(-0.1f, -0.2f, -0.1f);
        Transform3D transform3d2 = new Transform3D();
        transform3d2.setTranslation(p1);
        TransformGroup rootTransformGroup3 = new TransformGroup(transform3d2);
        rootTransformGroup3.addChild(new Box(0.02f, 0.02f, 0.02f, ap));
        rootTransformGroup.addChild(rootTransformGroup3);



        ap = new Appearance();
        ca = new ColoringAttributes();
        ca.setColor(0f, 150f, 150f);
        ap.setColoringAttributes(ca);

        Cylinder cylinder = new Cylinder(0.01f, 1.0f, Cylinder.GENERATE_NORMALS, 4, 2, ap);
        TransformGroup cylinderTransformGroup = new TransformGroup();
        cylinderTransformGroup.addChild(cylinder);
        rootTransformGroup.addChild(cylinderTransformGroup);

        Matrix4f transform = new Matrix4f();
        computeTransform(p0,p1,transform);
        cylinderTransformGroup.setTransform(new Transform3D(transform));



        BoundingSphere boundingSphere = new BoundingSphere(
            new Point3d(0, 0, 0), 10000);

        MouseRotate mouseRotate = new MouseRotate();
        mouseRotate.setTransformGroup(rootTransformGroup); // !!!!!!!!!!
        mouseRotate.setSchedulingBounds(boundingSphere);
        rootBranchGroup.addChild(mouseRotate);

        MouseTranslate mouseTranslate = new MouseTranslate();
        mouseTranslate.setTransformGroup(rootTransformGroup); // !!!!!!!!!!!
        mouseTranslate.setSchedulingBounds(boundingSphere);
        rootBranchGroup.addChild(mouseTranslate);

        MouseZoom mouseZoom = new MouseZoom();
        mouseZoom.setTransformGroup(rootTransformGroup); // !!!!!!!!!
        mouseZoom.setSchedulingBounds(boundingSphere);
        rootBranchGroup.addChild(mouseZoom);

        KeyNavigatorBehavior keyNavigatorBehavior = new KeyNavigatorBehavior(
            rootTransformGroup);
        keyNavigatorBehavior.setSchedulingBounds(boundingSphere);
        rootBranchGroup.addChild(keyNavigatorBehavior);

        rootBranchGroup.compile();

        simpleUniverse.addBranchGraph(rootBranchGroup);

        add(canvas);
        pack();
        setVisible(true);
    }

    public static void main(String[] args) throws Exception
    {
        // TODO Auto-generated method stub
        AlignTest t = new AlignTest();
    }

}
```

Bei vielen Cylindern wird das aber vermutlich schrecklich langsam (unabhängig von der Grafikkarte). Schneller kreigt man das wohl bestenfalls mit (viel) höherem Aufwand bei der Geometrieverwaltung, oder ggf. JOGL und eigenen Shadern hin....


----------



## theBigJimmy (29. Nov 2010)

Hallo,

ich habe den Code so umgesetzt. Vielen Dank erst einmal für die produktive Hilfe!!! 

Ich glaube aber, dass der Code noch einen Fehler hat, nur finde ich diesen nicht. Wenn man einfach die Vektoren p0 und p1 wie folgt setzt, wird eine Eception geworfen:

       (-5         )
p0 = (0.5        )
       (0.999583)

       (-5         )
p0 = (0          )
       (0.999992)

Hier die Exception:



> Exception in thread "main" javax.media.j3d.BadTransformException: TransformGroup: non-affine transform
> at javax.media.j3d.TransformGroup.setTransform(TransformGroup.java:137)
> at test2.<init>(test2.java:128)
> at test2.main(test2.java:167)
> ...


----------



## Marco13 (29. Nov 2010)

Oh ja: Der Abstand der beiden Punkte ist "praktisch 0", da kann man keine Ausrichtung mehr bestimmen. Den fall sollte man ggf. noch mit sowas wie
if (p0.distanceSquared(p1) < 1e5) macheNichts();
else macheWas();
abfangen.


----------



## theBigJimmy (29. Nov 2010)

Mmmmhhh...

Also die y-Koordinate unterscheidet sich um 0.5f...da die anderen beiden Koordinaten jeweils fast identisch sind, folgt ein Abstand von ca. 0.5f... Das müsste doch ausreichen. Ich verbinde außerdem bereits Punkte, die eine kleinere Distanz zueinander haben.


----------



## theBigJimmy (29. Nov 2010)

Bei der Übergabe der transform vom Typ Matrix4f an, das Tranform3D Objekt, ist m die Nullmatrix:


```
cylinderTransformGroup.setTransform(new Transform3D(transform)); [\JAVA]

Die Berechnung innerhalb der Funktion [code=Java] computeTransform [\JAVA] funktioniert. Also wird irgendwie nicht das zurückgegeben, was berechnet wurde.

??????????
```


----------



## theBigJimmy (29. Nov 2010)

Alles klar ich habs. Wir haben vergessen den Spezialfall abzufangen, dass die y-Achse und der Verbindungsvektor gleich null (mit Rundungsfehlern) bildet. Ich lasse den Thread trotzdem noch auf, weil ich noch weiter bastel...

Aber erst einmal danke und vielleicht bis später.


----------



## theBigJimmy (29. Nov 2010)

...den Winkel gleich null ... meine ich natürlich


----------



## Marco13 (29. Nov 2010)

Oh, das hatte ich übersehen. Kleine Winkel sollten eigentlich durch
if (axis.lengthSquared() > 1e-6)
abgefangen werden, aber vielleicht hab' ich da was übersehen...


----------

