3DS Dateiformat Probleme

Ishildur

Hallo zusammen
Ich schreibe im Zusammenhang mit meiner Thesis einen Decoder für das 3DS Format und komme dabei einfach nicht weiter

Ich möchte einen simplen Cube importieren, aber irgendwie funktioniert das überhaupt nicht, sobald ich die normalen berechnen muss. Hier ist mein Code zum Berechnen der Normalen:

// start a loop for walking each face
 for(uint32 i=0;i<szFce;++i){
  // compute the current index
  uint32 idx = 3*i;

  // copy the 3 indices defining the current face
  // (we ignore the material index for now)
  memcpy(&pIdx[idx],Data,3*sizeof(uint16));

  // compute the normal of this face
  Vector3 vc1 = pVtx[pIdx[idx+1]].Position-pVtx[pIdx[idx]].Position;
  Vector3 vc2 = pVtx[pIdx[idx+2]].Position-pVtx[pIdx[idx]].Position;
  pNrm[i] = Vector3::Normalize(Vector3::Cross(vc1,vc2));

  // advance the data pointer to the start of the next face
  Data += 4*sizeof(uint16);
 }

 // start a loop for walking each vertex within the vertex buffer
 for(uint32 i=0;i<szVrt;++i){
  // define a zero vector as start
  //(if no face uses this vertex it won't be lit)
  Vector3 vcNrm = Vector3::Zero;

  // start a loop for walking each index within the index buffer
  for(uint32 k=0;c=3*static_cast<uint32>(szFce);k<c;++k){
   // check if the current index indices the current vertex
   if(pIdx[k] == i) vcNrm += pNrm[k/3];
  }

  // finally assign the normalized mean of all
  // face vectors using the current vertex
  pVtx[i].Normal = Vector3::Normalize(vcNrm);
 }

Frage 1:
Bei 2^16/3 Vertices * 2^16 Indices würde man ja 2^32/3 Iterationen benötigen um alle Vertexnormalen zu berechnen Gibt es keine effizientere Variante als pro Vertex den gesamten Indexbuffer durchzugehen?

Frage 2:
Ich bin eifach Total verwirrt, wie 3D Studio diesen Würfen zusammensetzt. Dies fängt damit an, dass die VertexListe 26 Vertices erhält. Sollten das nicht entweder 24 oder 48 sein? Hinzu kommt, dass an einigen Ecken des Würfels 4 Vertices plaziert sind und an anderen wiederum nur 2. Ich dachte zunächst, dass ich irgendwie an der falschen Stelle (mit einem Pointeroffset) lese. Wenn ich allerdings im 3D Studio Max 2010 einen simplen Cube als 3ds exportiere und diesen anschliessend gleich wieder importiere, dann habe ich folgende Situation:

26 Vertices, teilweise hat er nur 2 Vertices an einer Ecke, zeigt mir jedoch 3 Normalen an
3 Normalen mit nur 2 Vertices, wie geht dass den??

Ich hoffe jemand von euch kennt dieses Format und kann mich aufklären, ich bin gerade ein wenig am resignieren...

Mfg Samuel

David_pb

Zu 1:
Du kannst dir den zweiten Schritt (start a loop for walk) doch sparen wenn du die Normalen direkt addierst.
Übrigens könnte es sein das du mit der Methode (MWE) schnell "fehlerhafte" Ergebnisse bekommst, weil z.B. die unterliegende Surfacetesselierung nicht berücksichtigt wird.

Ishildur

@David_pb
Hallo David
Mir ist nicht ganz klar, was du mit einem ersten Statement meinst? In Bezug auf die Tesselierung hast du natürlicht recht, aber eine solche ignoriere ich im Moment noch.

Ishildur

Mein Gott ja klar! Manchmal mache ich mir selbst Angst! :p Ich weiss jtzt, was du meinst!

David_pb

Ich mein folgendes (Pseudocode)

initialisiere alle vertexnormalen mit 0, 0, 0

foreach triangle t
  edge0 = t.edge0
  edge1 = t.edge1
  norm = normalize(edge0.cross(edge1))

  foreach vertex v of t
    (weight normal bei edge-angle)
    v.normal += norm;

Edit: ok!

Ishildur

@David_pb
Ich danke dir für diesen wertvollen Hinweis. Damit habe ich resp. DU das Laufzeitverhalten von O(v*i) auf O(i/3) heruntergebracht (im Prinzip von quadratisch auf linear!)

Nun, die zweite Frage bleibt noch offen... Ich habe mittlerweile bemerkt, dass ich dieses Problem eigentlich nur beim Cube habe. Alle anderen Primitiven, die ich von 3DStudio 2010 exportiere funktionieren, nur eben dieser Cube mit den 3Normalen auf 2 Vertices nicht.

Es ist da übrigens tatsächlich so: Ich selektiere einen einzigen Vertex und da steht auch: "Vertex 2 Selected" und es gehen 2 zueinander orthogonale Normalen von diesem Vertex aus... Wie ist denn das möglich?

Ishildur

@David_pb
Beim Versuch, das Ganze zu implementieren hat sich leider herausgestellt, dass es nun doch nicht ganz so einfach ist :-| Bspw. gibt es diverse Verticen, die dupliziert werden, weil für eine bestimmte Stelle 2 oder mehrere Texturkoordinaten vorhanden sind. Dadurch sind natürlich bestimmte Vertices nicht mehr gemeinsam referenziert, welche an sich dieselben Normalen hätten. Muss ich nun für jeden Vertex die komplette Liste durchgehen und sehen, ob sich da vielleicht noch ein Vertex mit einer identischen Position befindet oder was?

David_pb

Duplizierte Vertices kannst du doch behandeln wie "normale" Vertices?!

Ishildur

Ich dachte, ich kann beim Erstellen des Index Buffers einfach das Face Normal berechnen und dieses anschliessend bei jedem Vertex, welcher von dem entsprechenden Face referenziert wird, dazu addieren und anschliessend normalisieren. Wenn ich nun bspw. ein Vertex habe, welches von 6 Faces geteilt wird, dann wird dieser Algorithmus 6 Normales zu diesem Vertex addieren. Das ist auch die Methode, die du mir gezeigt hast
Das Problem ist nun, dass wenn diese Vertices nicht mehr geteilt werden (weil eben mehrere Texturkoordinaten benötigt werden), dann wird ja jeder Vertex nur noch von genau einem Face referenziert und als Konsequenz wird dieser Algorithmus natürlich bei jedem Vertex auch nur noch dasjenige Normal des einzigen Faces dazuaddieren, zu welchem es gehört.

Ich lese überall, "ja man muss halt einfach die Facenormals berechnen und anschliessend für jeden Vertex mitteln". Aber wie genau dass dann funktionieren soll (Das herausfinden, welche Faces zu einem Vertex gehört (Wenn ich bspw. 6 Vertices mit identischen Positionskoordinaten habe), da werden die Stimmen plötzlich ganz leise...

David_pb

Wenn der Vertex nur noch zu einem Face gehört dann ist die Vertexnormale doch genau die Facenormale. Du musst beim Duplizieren natürlich wissen zu welchen Faces der neue Vertex gehört und das entsprechend vermerken.

Ishildur

Wenn der Vertex nur noch zu einem Face gehört dann ist die Vertexnormale doch genau die Facenormale

Aus mathematischer Sicht vielleich schon, aber nicht aus Beleuchtungssicht. Zwar gehört jeder Vertex nur noch zu einem Face (mathematisch), aber es gibt nun bspw. immer je 6 Verticen mit identischen Positionskoordinaten. Dann habe ich 6 Normalen, welche in verschiedene Richtungen zeigen, aber dann habe ich ja per Face Shading, anstatt per Vertex. Die 6 Verticen müssen natürlich alle denselben Normalenvektor haben.

Ich stelle die Frage anders (hoffentlich einfacher). Nehmen wir einmal an, ich hätte keinen IndexBuffer, also eine nicht indizierte Vertex Liste (Kein Vertex wird gemeinsam von mehreren Faces verwendet). Ich möchte allerdings dennoch ein Per Vertex Shading. Die Facenormalen zu berechnen ist kein Problem, aber wie finde ich heraus zu welchen Verticen, ein jeweiliges Facenormal hinzuaddiert werden muss, wenn ich keine Indices habe. (Ich habe zwar welche aber kaum eines eferenziert denselben Vertex)

Natürlich habe ich mir bereits einen Algorithmus ausgedacht, aber der hat ein Laufzeitverhalten von ca. O(n^3), sehr schlecht...

hellihjb

Natürlich habe ich mir bereits einen Algorithmus ausgedacht, aber der hat ein Laufzeitverhalten von ca. O(n^3)

Du mapst alle Vertexposition der Faces die in der gleichen Smoothing-Group liegen auf einen eindeutigen Index.
Das kostet Dich mit Brute-Force N^2 und mit einer sinnvollen Hash-Funktion N*Wenige-Moegliche-Kandidaten.

Kirjuxa

gibt es eine Beschreibung wie man eine 3ds Datei ausliest.
Arbeite gerade an einer eigenen mini-3D Engine und wollte mal wissen wie ich eine 3ds datei bzw. .max Datei auslesen kann.
Gibt es da ein Tutorial zu?
ein Link wäre geil

Ishildur

@Kirjuxa
Ich habe hierfür folgende Resource verwendet: http://www.martinreddy.net/gfx/3d/3DS.spec Damit geht es kinderleicht

TGGC

Beim smoothen der Normals darf man natuerlich auch nur Faces beruecksichtigen, die in der selben Smoothegroup sind - wurde das beachtet? Ansonsten 3ds laden ist ziemlicher Selbstmord. f'`8k

Autocogito

Gruß, TGGC (Was Gamestar sagt...)

Ishildur

@TGGC
Naja, als Selbstmord würde ich es nicht bezeichnen. Der mp3 Decoder empfand ich bspw. als deutlich schwieriger als der 3ds Decoder. Also für den kompletten Importer (nur Meshes inkl. Submeshes, Berechnung des Tangentspace fürs Normalmapping und Gruppierung nach Material benötigte ich weniger als 500 Zeilen Code, wärendessen der Mp3 Decoder... Puuh..... :-p

Aber OK, was tatsächlich mühsam ist, ist dass die Daten einfach völlig anders abgespeichert sind, als ich sie benötigte. Meine Mesh klasse hat einen Vertex und einen IndexBuffer sowie mehrere Meshparts:

// ****************************************** struct "MeshPart" ******************************************
// This structure defines the data needed for rendering a part of a mesh.
// Author: Samuel Lörtscher
// *******************************************************************************************************
struct MeshPart{
 // --------------------------------------- public dynamic members ---------------------------------------
 uint32            MinVertex;  // the minimal vertex used within tis mesh part
 uint32            Offset;     // the offset of the first triangle using this mesh part (zero indexed)
 uint32            Count;      // the number of triangles using this mesh part
 ITextureResource *Diffuse;    // the diffuse map
 ITextureResource *Normal;     // the normal map
 ITextureResource *Specular;   // the specular map
 ITextureResource *Reflection; // the reflection map
 // ------------------------------------------------------------------------------------------------------

 // ------------------------------------- constructors and destructor ------------------------------------
  MeshPart(void);
  MeshPart(uint32 MinVertex,uint32 Offset,uint32 Count);
  ~MeshPart(void){}
 // ------------------------------------------------------------------------------------------------------
};
// *******************************************************************************************************

Problematisch war am Anfang, dass ich nicht wusste, wie gross ich den Vertex- bzw. Indexbuffer machen soll, da in keinem Headerjunk drinnsteht, wieviele Triangles das Teil denn nun hat (Es kann ja beliebig viele Vertexlist junks haben). Dieses Problem habe ich schliesslich mit einem Preparsing Step gelöst. Nicht sonderlich schwierig aber einfach MÜÜHSAM war, dass einfach willkürlich gewisse Faces ein anderes Material benutzen.