I've been working on a tessellation patch, and I'm having some rather 
bizzare problems. I've created a singleton class to make mesh creation 
easier, and I think the problem is in there, I assume I'm somehow not 
using the mesh code properly...the class is below. For some reason, a 
triangle sometimes gets a vertex from a different triangle, apparently 
the previous one. When I make quads from two triangles with vertices 
arranged like this:

D-C
|/|
A-B

The effect is as if the ABC triangle goes DBC, overlapping and leaving a 
gap. But it only does this sometimes: on one half of a cylinder, or 
specific segments of a tessellated sphere, even though the exact same 
code is creating the triangles.

/*
 *  meshfactory.h
 *  POV35
 *
 *  Created by Christopher James Huff on Fri Dec 20 2002.
 *  Copyright (c) 2002 Christopher James Huff. All rights reserved.
 *
 */

/*A very simple class created to assist in managing mesh creation,
a separate interface to the mesh code.*/

#ifndef MESH_FACTORY
#define MESH_FACTORY

#include "frame.h"
#include "mesh.h"

class MeshFactory {
  private:
    static MESH * mesh;
    
    static bool fullyTextured;
    
    static int numTriangles;
    static int numVertices;
    static int numNormals;
    static int numTextures;
    static int numUVCoords;
    
    static int maxTriangles;
    static int maxVertices;
    static int maxNormals;
    static int maxTextures;
    static int maxUVCoords;
    
    static MESH_TRIANGLE * triangles;
    static SNGL_VECT * vertices;
    static SNGL_VECT * normals;
    static TEXTURE ** textures;
    static UV_VECT * UVCoords;
    
    MeshFactory() {}//keep MeshFactory instances from being created
    ~MeshFactory() {}
  public:
    static void StartMesh();
    
    static void SetInsideVector(VECTOR ins);
    static void AddTriangle(VECTOR ptA, VECTOR ptB, VECTOR ptC, TEXTURE 
* t1 = NULL, TEXTURE * t2 = NULL, TEXTURE * t3 = NULL);
    static void AddTriangle(VECTOR ptA, VECTOR ptB, VECTOR ptC, VECTOR 
normA, VECTOR normB, VECTOR normC, TEXTURE * t1 = NULL, TEXTURE * t2 = 
NULL, TEXTURE * t3 = NULL);
    
    static void AddQuad(VECTOR p1, VECTOR p2, VECTOR p3, VECTOR p4, 
TEXTURE * t1 = NULL, TEXTURE * t2 = NULL, TEXTURE * t3 = NULL, TEXTURE * 
t4 = NULL);
    static void AddQuad(VECTOR p1, VECTOR p2, VECTOR p3, VECTOR p4, 
VECTOR n1, VECTOR n2, VECTOR n3, VECTOR n4, TEXTURE * t1 = NULL, TEXTURE 
* t2 = NULL, TEXTURE * t3 = NULL, TEXTURE * t4 = NULL);
    
    static MESH * GetMesh();
};

#endif


/*
 *  meshfactory.cpp
 *  POV35
 *
 *  Created by Christopher James Huff on Fri Dec 20 2002.
 *  Copyright (c) 2002 Christopher James Huff. All rights reserved.
 *
 */

#include "frame.h"
#include "pov_mem.h"
#include "povproto.h"
#include "vector.h"
#include "objects.h"
#include "texture.h"
#include "meshfactory.h"

#include <iostream>

MESH * MeshFactory::mesh = NULL;
bool MeshFactory::fullyTextured;
int MeshFactory::numTriangles;
int MeshFactory::numVertices;
int MeshFactory::numNormals;
int MeshFactory::numTextures;
int MeshFactory::numUVCoords;

int MeshFactory::maxTriangles;
int MeshFactory::maxVertices;
int MeshFactory::maxNormals;
int MeshFactory::maxTextures;
int MeshFactory::maxUVCoords;

MESH_TRIANGLE * MeshFactory::triangles;
SNGL_VECT * MeshFactory::vertices;
SNGL_VECT * MeshFactory::normals;
TEXTURE ** MeshFactory::textures;
UV_VECT * MeshFactory::UVCoords;

void MeshFactory::StartMesh()
{
    //need to check for non-NULL
    mesh = Create_Mesh();
    
    fullyTextured = true;
    mesh->has_inside_vector = false;
    
    maxTriangles = 256;
    maxVertices = 256;
    maxNormals = 256;
    maxTextures = 16;
    maxUVCoords = 256;
    
    numTriangles = 0;
    numVertices = 0;
    numNormals = 0;
    numTextures = 0;
    numUVCoords = 0;
    
    triangles = (MESH_TRIANGLE 
*)POV_MALLOC(maxTriangles*sizeof(MESH_TRIANGLE), "temporary triangle 
mesh data");
    vertices = (SNGL_VECT *)POV_MALLOC(maxVertices*sizeof(SNGL_VECT), 
"temporary triangle mesh data");
    normals = (SNGL_VECT *)POV_MALLOC(maxNormals*sizeof(SNGL_VECT), 
"temporary triangle mesh data");
    textures = (TEXTURE **)POV_MALLOC(maxTextures*sizeof(TEXTURE *), 
"temporary triangle mesh data");
    UVCoords = (UV_VECT *)POV_MALLOC(maxUVCoords*sizeof(UV_VECT), 
"temporary triangle mesh data");
    
    Create_Mesh_Hash_Tables();
}

void MeshFactory::SetInsideVector(VECTOR ins)
{
    VNormalize(mesh->Data->Inside_Vect, ins);
    mesh->has_inside_vector = true;
}


//could simplify by abstracting triangle
void MeshFactory::AddTriangle(VECTOR ptA, VECTOR ptB, VECTOR ptC, 
TEXTURE * t1, TEXTURE * t2, TEXTURE * t3)
{
    if(!Mesh_Degenerate(ptA, ptB, ptC))
    {
        if(numTriangles >= maxTriangles)
        {
            if(maxTriangles >= INT_MAX/2)
                Error("Too many triangles in triangle mesh.");
            
            maxTriangles *= 2;
            triangles = (MESH_TRIANGLE *)POV_REALLOC(triangles, 
maxTriangles*sizeof(MESH_TRIANGLE), "triangle triangle mesh data");
        }
        
        Init_Mesh_Triangle(&triangles[numTriangles]);
        
        triangles[numTriangles].P1 = Mesh_Hash_Vertex(&numVertices, 
&maxVertices, &vertices, ptA);
        triangles[numTriangles].P2 = Mesh_Hash_Vertex(&numVertices, 
&maxVertices, &vertices, ptB);
        triangles[numTriangles].P3 = Mesh_Hash_Vertex(&numVertices, 
&maxVertices, &vertices, ptC);
        
        triangles[numTriangles].Texture = 
Mesh_Hash_Texture(&numTextures, &maxTextures, &textures, t1);
        if(t2)
            triangles[numTriangles].Texture2 = 
Mesh_Hash_Texture(&numTextures, &maxTextures, &textures, t2);
        if(t3)
            triangles[numTriangles].Texture3 = 
Mesh_Hash_Texture(&numTextures, &maxTextures, &textures, t3);
        
        if(t2 || t3)
            triangles[numTriangles].ThreeTex = true;
        
        //Hash in UV coords, even though they aren't used.
        UV_VECT UV_Temp;
        triangles[numTriangles].UV1 = Mesh_Hash_UV(&numUVCoords, 
&maxUVCoords, &UVCoords, UV_Temp);
        triangles[numTriangles].UV2 = Mesh_Hash_UV(&numUVCoords, 
&maxUVCoords, &UVCoords, UV_Temp);
        triangles[numTriangles].UV3 = Mesh_Hash_UV(&numUVCoords, 
&maxUVCoords, &UVCoords, UV_Temp);
        
        
        VECTOR N;
        Compute_Mesh_Triangle(&triangles[numTriangles], false, ptA, ptB, 
ptC, N);

        triangles[numTriangles].Normal_Ind = 
Mesh_Hash_Normal(&numNormals, &maxNormals, &normals, N);
        
        if(triangles[numTriangles].Texture < 0)
            fullyTextured = false;

        numTriangles++;
    }
    else
    {
        Error("MeshFactory: Degenerate triangle.");
    }
}


//smooth triangle without UV
void MeshFactory::AddTriangle(VECTOR ptA, VECTOR ptB, VECTOR ptC, VECTOR 
normA, VECTOR normB, VECTOR normC, TEXTURE * t1, TEXTURE * t2, TEXTURE * 
t3)
{
    if(!Mesh_Degenerate(ptA, ptB, ptC))
    {
        if(numTriangles >= maxTriangles)
        {
            if(maxTriangles >= INT_MAX/2)
                Error("MeshFactory: Too many triangles in triangle 
mesh.");
            
            maxTriangles *= 2;
            triangles = (MESH_TRIANGLE *)POV_REALLOC(triangles, 
maxTriangles*sizeof(MESH_TRIANGLE), "triangle triangle mesh data");
        }
        
        Init_Mesh_Triangle(&triangles[numTriangles]);
        triangles[numTriangles].P1 = Mesh_Hash_Vertex(&numVertices, 
&maxVertices, &vertices, ptA);
        triangles[numTriangles].P2 = Mesh_Hash_Vertex(&numVertices, 
&maxVertices, &vertices, ptB);
        triangles[numTriangles].P3 = Mesh_Hash_Vertex(&numVertices, 
&maxVertices, &vertices, ptC);
        
        triangles[numTriangles].Texture = 
Mesh_Hash_Texture(&numTextures, &maxTextures, &textures, t1);
        if(t2)
            triangles[numTriangles].Texture2 = 
Mesh_Hash_Texture(&numTextures, &maxTextures, &textures, t2);
        if(t3)
            triangles[numTriangles].Texture3 = 
Mesh_Hash_Texture(&numTextures, &maxTextures, &textures, t3);
        
        if(t2 || t3)
            triangles[numTriangles].ThreeTex = true;
        
        //Hash in UV coords, even though they aren't used.
        UV_VECT UV_Temp;
        triangles[numTriangles].UV1 = Mesh_Hash_UV(&numUVCoords, 
&maxUVCoords, &UVCoords, UV_Temp);
        triangles[numTriangles].UV2 = Mesh_Hash_UV(&numUVCoords, 
&maxUVCoords, &UVCoords, UV_Temp);
        triangles[numTriangles].UV3 = Mesh_Hash_UV(&numUVCoords, 
&maxUVCoords, &UVCoords, UV_Temp);
        
        triangles[numTriangles].N1 = Mesh_Hash_Normal(&numNormals, 
&maxNormals, &normals, normA);
        triangles[numTriangles].N2 = Mesh_Hash_Normal(&numNormals, 
&maxNormals, &normals, normB);
        triangles[numTriangles].N3 = Mesh_Hash_Normal(&numNormals, 
&maxNormals, &normals, normC);
        
        //doesn't do as much checking as Parse_Mesh()
        VECTOR N;
        Compute_Mesh_Triangle(&triangles[numTriangles], true, ptA, ptB, 
ptC, N);

        triangles[numTriangles].Normal_Ind = 
Mesh_Hash_Normal(&numNormals, &maxNormals, &normals, N);
        
        if(triangles[numTriangles].Texture < 0)
            fullyTextured = false;

        numTriangles++;
    }
}

void MeshFactory::AddQuad(VECTOR p1, VECTOR p2, VECTOR p3, VECTOR p4,
                          TEXTURE * t1, TEXTURE * t2, TEXTURE * t3, 
TEXTURE * t4)
{
    //points:
    //4 3
    //1 2
    //Should find the longest axis and split across that
    AddTriangle(p1, p2, p3, t1, t2, t3);
    AddTriangle(p1, p3, p4, t1, t3, t4);
}

void MeshFactory::AddQuad(VECTOR p1, VECTOR p2, VECTOR p3, VECTOR p4,
                          VECTOR n1, VECTOR n2, VECTOR n3, VECTOR n4,
                          TEXTURE * t1, TEXTURE * t2, TEXTURE * t3, 
TEXTURE * t4)
{
    AddTriangle(p1, p2, p3, n1, n2, n3, t1, t2, t3);
    AddTriangle(p1, p3, p4, n1, n3, n4, t1, t3, t4);
}



MESH * MeshFactory::GetMesh()
{
    Destroy_Mesh_Hash_Tables();
    
    if(numTriangles == 0)
        Error("MeshFactory: No triangles in triangle mesh.");
    
    std::cout << "\nMeshFactory: mesh complete.\n"
              << "triangles: " << numTriangles
              << "\nvertices: " << numVertices
              << "\nnormals: " << numNormals << std::endl;
    
    mesh->Data = (MESH_DATA *)POV_MALLOC(sizeof(MESH_DATA), "triangle 
mesh data");
    mesh->Data->References = 1;
    mesh->Data->Tree = NULL;
    
    if(fullyTextured)
        mesh->Type |= TEXTURED_OBJECT;
    
    mesh->Data->Triangles = (MESH_TRIANGLE 
*)POV_MALLOC(numTriangles*sizeof(MESH_TRIANGLE), "triangle mesh data");
    mesh->Data->Number_Of_Triangles = numTriangles;
    mesh->Data->Vertices = (SNGL_VECT 
*)POV_MALLOC(numVertices*sizeof(SNGL_VECT), "triangle mesh data");
    mesh->Data->Number_Of_Vertices = numVertices;
    mesh->Data->Normals = (SNGL_VECT 
*)POV_MALLOC(numNormals*sizeof(SNGL_VECT), "triangle mesh data");
    mesh->Data->Number_Of_Normals = numNormals;
    mesh->Data->UVCoords = (UV_VECT 
*)POV_MALLOC(numUVCoords*sizeof(UV_VECT), "triangle mesh data");
    mesh->Data->Number_Of_UVCoords = numUVCoords;
    
    if(numTextures == 0)
    {
        mesh->Textures = NULL;
    }
    else
    {
        Set_Flag(mesh, MULTITEXTURE_FLAG);
        mesh->Textures = (TEXTURE 
**)POV_MALLOC(numTextures*sizeof(TEXTURE *), "triangle mesh data");
    }
    mesh->Number_Of_Textures = numTextures;
    
    for(int i = 0; i < numTriangles; i++)
        mesh->Data->Triangles[i] = triangles[i];
    
    for(int i = 0; i < numVertices; i++)
        Assign_SNGL_Vect(mesh->Data->Vertices[i], vertices[i]);
    
    for(int i = 0; i < numNormals; i++)
        Assign_SNGL_Vect(mesh->Data->Normals[i], normals[i]);
    
    for(int i = 0; i < numUVCoords; i++)
        Assign_UV_Vect(mesh->Data->UVCoords[i], UVCoords[i]);
    
    for (int i = 0; i < numTextures; i++)
    {
        mesh->Textures[i] = Copy_Textures(textures[i]);
        Post_Textures(mesh->Textures[i]);
        // now free the texture, in order to decrement the reference 
count
        Destroy_Textures(textures[i]);
        //Is all the above really necessary?
    }
    
    POV_FREE(triangles);
    POV_FREE(vertices);
    POV_FREE(normals);
    POV_FREE(textures);
    POV_FREE(UVCoords);
    
    Compute_Mesh_BBox(mesh);
    Build_Mesh_BBox_Tree(mesh);
    
    MESH * msh = mesh;
    mesh = NULL;
    return msh;
}

-- 
Christopher James Huff <cja### [at] earthlinknet>
http://home.earthlink.net/~cjameshuff/
POV-Ray TAG: chr### [at] tagpovrayorg
http://tag.povray.org/

Post a reply to this message

Christopher James Huff wrote:


> {
>     AddTriangle(p1, p2, p3, n1, n2, n3, t1, t2, t3);
>     AddTriangle(p1, p3, p4, n1, n3, n4, t1, t3, t4);
> }


Beware of the hashing system: I seem to remember that there was a side 
effects on the vertex when addding a triangle, at least in 3.1g.
Safe way is/was to keep a 'protected' copy of the shared vertices/data: 
first you use one set, next you use the other set (and never twice the 
same variables!)

Post a reply to this message

In article <3E0### [at] freefr>, Le Forgeron <jgr### [at] freefr> 
wrote:

> Beware of the hashing system: I seem to remember that there was a side 
> effects on the vertex when addding a triangle, at least in 3.1g.
> Safe way is/was to keep a 'protected' copy of the shared vertices/data: 
> first you use one set, next you use the other set (and never twice the 
> same variables!)

I have found the guilty code: Compute_Mesh_Triangle() sometimes swaps 
two vertices of a triangle. I have no idea why...it doesn't look like it 
does anything useful. The vertices it swaps have already been hashed, 
the values it modifies are not used afterwords in the original 
code...this code has no effect other than screwing up my patch.

-- 
Christopher James Huff <cja### [at] earthlinknet>
http://home.earthlink.net/~cjameshuff/
POV-Ray TAG: chr### [at] tagpovrayorg
http://tag.povray.org/

Post a reply to this message

In article <chr### [at] netplexaussieorg> , 
Christopher James Huff <chr### [at] maccom>  wrote:

> this code has no effect other than screwing up my patch.

So it works as designed? ;-)

    Thorsten

____________________________________________________
Thorsten Froehlich, Duisburg, Germany
e-mail: tho### [at] trfde

Visit POV-Ray on the web: http://mac.povray.org

Post a reply to this message

In article <3e08a125$1@news.povray.org>,
 "Thorsten Froehlich" <tho### [at] trfde> wrote:

> In article <chr### [at] netplexaussieorg> , 
> Christopher James Huff <chr### [at] maccom>  wrote:
> 
> > this code has no effect other than screwing up my patch.
> 
> So it works as designed? ;-)

Heh...
Well, it actually does do something, but it does more work than it needs 
to. It swaps the vertices and then passes them to another function. I 
changed it to pass them in a different order, the code is cleaner IMO 
and slightly faster, though not in a place where it really matters.

Basically, replace the following in Compute_Mesh_Triangle():

    Assign_Vector(T1, P1);
    Assign_Vector(P1, P2);
    Assign_Vector(P2, T1);

    if (Smooth)
    {
      temp = Triangle->N2;
      Triangle->N2 = Triangle->N1;
      Triangle->N1 = temp;
    }
  }

  if (Smooth)
  {
  //  compute_smooth_triangle(Triangle, P1, P2, P3);
  Triangle->Smooth = true;
  }

    compute_smooth_triangle(Triangle, P1, P2, P3);

With this:
        if(Smooth)
        {
            temp = Triangle->N2;
            Triangle->N2 = Triangle->N1;
            Triangle->N1 = temp;
            Triangle->Smooth = true;
        }
        compute_smooth_triangle(Triangle, P2, P1, P3);
    }
    else
    {
        if(Smooth)
            Triangle->Smooth = true;
    
        compute_smooth_triangle(Triangle, P1, P2, P3);
    }

And get rid of the T1 variable. And if compute_smooth_triangle() really 
does something needed for flat triangles, that should probably be pulled 
out.

-- 
Christopher James Huff <cja### [at] earthlinknet>
http://home.earthlink.net/~cjameshuff/
POV-Ray TAG: chr### [at] tagpovrayorg
http://tag.povray.org/

Post a reply to this message

In article <chr### [at] netplexaussieorg> , 
Christopher James Huff <chr### [at] maccom>  wrote:

> Well, it actually does do something, but it does more work than it needs
> to. It swaps the vertices and then passes them to another function. I
> changed it to pass them in a different order, the code is cleaner IMO
> and slightly faster, though not in a place where it really matters.

Actually, there is a lot more that could be done to be more (space)
efficient in the current code...

For example to current indexing of vertex-, normal-, uv- vectors, as well as
of textures does not exploit locality very well.  Taking vertices as
example, but the same holds for the other uv vectors, normals and textures:

Many vertices that are close to each other will also belong to triangles
close to each other.  So one could partition the current single table of
vertices into smaller tables.  This would allow to reduce the data in
Mesh_Triangle_Struct by at least 16 bytes if the indices are turned into 16
bit ints with a 16 bit table index.  Of course for very large meshes this
could cause duplicate table entries, but given that per triangle four bytes
- that is 1/3 of a vertex vector - are saved, this will still reduce memory
consumption.

Of course, the cost of such a modification would be much more complex mesh
parsing as data would have to be kept in a more ordered fashion.  So it
would require rewriting large chunks of the current code...

Or take this to the extreme and provide one full index and make the other
two single byte offsets relative to that one.  That way only 6 compared to
the current 12 bytes would be needed per vertex (or the other indexed data).
And probably such a method would be easy to implement without changing much
of the current code!

    Thorsten

____________________________________________________
Thorsten Froehlich, Duisburg, Germany
e-mail: tho### [at] trfde

Visit POV-Ray on the web: http://mac.povray.org

Post a reply to this message

In article <3e08dc58@news.povray.org>,
 "Thorsten Froehlich" <tho### [at] trfde> wrote:

> Actually, there is a lot more that could be done to be more (space)
> efficient in the current code...

This is true of many parts of the code, unfortunately...there's a lot of 
crud and wasted computation or memory in there (non-refracting 
transparency, for instance). And some parts are just painful to read...
It's certainly time for a rewrite...my recent patching (specifically new 
tessellation, glow, and proximity patches) has been affecting such wide 
areas of code I've been considering rewriting the shape handling to use 
C++ classes myself. Only problem is that it would make my patches 
incompatible with a lot of other patches and future official updates...

-- 
Christopher James Huff <cja### [at] earthlinknet>
http://home.earthlink.net/~cjameshuff/
POV-Ray TAG: chr### [at] tagpovrayorg
http://tag.povray.org/

Post a reply to this message