[fixed] unnecessary vertex duplication

You discovered a bug in the engine, and you are sure that it is not a problem of your code? Just post it in here. Please read the bug posting guidelines first.
eye776
Posts: 94
Joined: Sun Dec 28, 2008 11:07 pm

[fixed] unnecessary vertex duplication

Post by eye776 »

SOLVED! (sorta...)
Ok... i finally figured it out and made a fool out of myself in the process.

The way in which core::map uses the < operator is inconsistent with the vector3df use of the operator.

For example compare (as in <, >) the following vectors : (1, 0, -1) ? (-1, 1, 0)

Obviously (1, 0, -1) < (-1, 1, 0) won't cut it.
Neither will (1, 0, -1) > (-1, 1, 0).
Case closed.

My dumbass solution:

1) Open vector3d.h

2) First of all, for the sake of consistency add these functions:

Code: Select all

bool ltAll(const vector3d<T>&other) const { 
    return X<other.X && Y<other.Y && Z<other.Z;
}
bool gtAll(const vector3d<T>&other) const {
    return X>other.X && Y>other.Y && Z>other.Z;
}
3) Now replace the <, > operators like this (for better RB dispersion):

Code: Select all

bool operator<(const vector3d<T>&other) const { 
	return X<other.X ||
	(X==other.X && Y<other.Y) || 
	(X==other.X && Y==other.Y && Z<other.Z);
}

//Actually this operator is not used in core::map so it's not really needed
bool operator>(const vector3d<T>&other) const { 
	return X>other.X ||
	(X==other.X && Y>other.Y) ||
	(X==other.X && Y==other.Y && Z>other.Z);
}
4) Recompile and have fun.

Again, I personally NEED this solution because I NEED to get access to the EXACT vertices that I exported.

I do wonder:
If you import, then use the IMeshWriter, then import again, then use the IMeshWriter, etc... how many times will the vertices be duplicated :lol:?
Last edited by eye776 on Wed Apr 29, 2009 9:35 am, edited 5 times in total.
eye776
Posts: 94
Joined: Sun Dec 28, 2008 11:07 pm

Post by eye776 »

Okay, so decided to take matters into my own hand...
I fed irrlicht this obj file:

Code: Select all

# Exported from Wings 3D 0.99.53
mtllib lol.mtl
o cube1
#8 vertices, 12 faces
v -1.00000000 -1.00000000 1.00000000
v -1.00000000 1.00000000 1.00000000
v 1.00000000 1.00000000 1.00000000
v 1.00000000 -1.00000000 1.00000000
v -1.00000000 -1.00000000 -1.00000000
v -1.00000000 1.00000000 -1.00000000
v 1.00000000 1.00000000 -1.00000000
v 1.00000000 -1.00000000 -1.00000000
vn -0.57735027 -0.57735027 0.57735027
vn -0.57735027 0.57735027 0.57735027
vn 0.57735027 0.57735027 0.57735027
vn 0.57735027 -0.57735027 0.57735027
vn -0.57735027 -0.57735027 -0.57735027
vn -0.57735027 0.57735027 -0.57735027
vn 0.57735027 0.57735027 -0.57735027
vn 0.57735027 -0.57735027 -0.57735027
g cube1_default
usemtl default
f 1//1 4//4 2//2
f 1//1 5//5 4//4
f 2//2 4//4 3//3
f 2//2 5//5 1//1
f 2//2 7//7 6//6
f 3//3 7//7 2//2
f 4//4 5//5 8//8
f 4//4 7//7 3//3
f 5//5 7//7 8//8
f 6//6 5//5 2//2
f 6//6 7//7 5//5
f 8//8 7//7 4//4
With this mtl file:

Code: Select all

# Exported from Wings 3D 0.99.53
newmtl default
Ns 100.0
d 1.0
illum 2
Kd 1.0 1.0 1.0
Ka 1.0 1.0 1.0
Ks 1.0 1.0 1.0
Ke 0.0 0.0 0.0
Here is what irrlicht spits out:
Vertices:

Code: Select all

0 - 1.000000,-1.000000,1.000000 ; 
1 - -1.000000,-1.000000,1.000000 ; 
2 - 1.000000,1.000000,1.000000 ; 
3 - 1.000000,-1.000000,1.000000 ; 
4 - 1.000000,-1.000000,-1.000000 ; 
5 - 1.000000,1.000000,1.000000 ; 
6 - -1.000000,1.000000,1.000000 ; 
7 - 1.000000,-1.000000,-1.000000 ; 
8 - -1.000000,1.000000,-1.000000 ; 
9 - 1.000000,1.000000,-1.000000 ; 
10 - -1.000000,1.000000,1.000000 ; 
11 - -1.000000,1.000000,-1.000000 ; 
12 - 1.000000,1.000000,1.000000 ; 
13 - -1.000000,-1.000000,1.000000 ; 
14 - -1.000000,-1.000000,-1.000000 ; 
15 - -1.000000,1.000000,1.000000 ; 
16 - 1.000000,1.000000,-1.000000 ; 
17 - -1.000000,-1.000000,1.000000 ; 
And faces(triangles):

Code: Select all

0 - 2,1,0 ; 
1 - 1,4,3 ; 
2 - 6,1,5 ; 
3 - 3,7,5 ; 
4 - 9,8,5 ; 
5 - 12,11,10 ; 
6 - 14,7,13 ; 
7 - 15,11,13 ; 
8 - 14,11,7 ; 
9 - 12,7,16 ; 
10 - 7,11,16 ; 
11 - 17,11,14 ; 
I have only three letters to express my reaction ... W T F...
It's no wonder most of the mesh tinkering code I tried in the past botched up...

This is turing into a bug report...

EDIT: Sorry... I got a bit heated up... it may still be my fault. I'm writing another small test app to see something.
Jookia
Posts: 170
Joined: Wed Nov 19, 2008 1:11 am

Post by Jookia »

I'm stupid, so I'm going to ask the obvious.. Have you tried typecasting?
eye776
Posts: 94
Joined: Sun Dec 28, 2008 11:07 pm

Post by eye776 »

Lulz. App rewrote, linked with newest stable irrlicht (straight off the site).
Exact same s**t!!! (I'm not going to repost the exact same log again :D).
Here's the source for any parties interested. (Warning! dirty 5min app.)

Code: Select all

#include <irrlicht.h>

using namespace irr;
using namespace core;
using namespace scene;
using namespace video;

#pragma comment(lib, "Irrlicht.lib")

int main()
{
	IrrlichtDevice *device = 
		createDevice(EDT_NULL, dimension2d<s32>(640, 480), 16, false, false, false, 0);
	IVideoDriver* driver = device->getVideoDriver();
	ISceneManager* smgr = device->getSceneManager();

	IMesh* mesh = smgr->getMesh("lol.obj");
	IMeshBuffer* mb = mesh->getMeshBuffer(0);

	printf("Mesh has %d buffers.\n\n", mesh->getMeshBufferCount());

	const video::S3DVertex* mb_vertices = (const video::S3DVertex*)mb->getVertices();
	vector3df vtx;
	core::stringc vtxPos;
	for(u32 i = 0; i < mb->getVertexCount(); i++) {
		vtx = vector3df(mb_vertices[i].Pos);
		vtxPos.append(stringc(i)+" - "+stringc(vtx.X)+","+
			stringc(vtx.Y)+","+stringc(vtx.Z)+" ; \n");
	}
	printf("Vertices:\n");
	printf(vtxPos.c_str());
	printf("------------------\n\n");

	vtxPos = core::stringc();
	u16* mb_indices  = mb->getIndices();
	u16 v1i, v2i, v3i;
	for(u32 i = 0; i < mb->getIndexCount(); i+=3) {
		v1i = mb_indices[i];
		v2i = mb_indices[i+1];
		v3i = mb_indices[i+2];
		vtxPos.append(stringc((int)i/3)+" - "+stringc(v1i)+","+
			stringc(v2i)+","+stringc(v3i)+" ; \n");
	}

	printf("Indices:\n");
	printf(vtxPos.c_str());
	
	while(1) ;
	device->drop();
}
CuteAlien
Admin
Posts: 9734
Joined: Mon Mar 06, 2006 2:25 pm
Location: Tübingen, Germany
Contact:

Post by CuteAlien »

I debugged a little (while doing breakfeast) and I could reduce the bug to this:

Code: Select all

#include <irrlicht.h>

using namespace irr;
using namespace core;
using namespace scene;
using namespace video;

#pragma comment(lib, "Irrlicht.lib")

int main()
{
	core::map<video::S3DVertex, int> testmap;
	video::S3DVertex v;
	v.Pos = core::vector3df(1.000000, -1.000000, 1.000000);
	v.Normal = core::vector3df(0.577350, -0.577350, 0.577350);
	v.Color = SColor(255,204,204,204);
	v.TCoords = core::vector2d<f32>(0.f, 0.f);
	testmap.insert(v, 0);
	
	v.Pos = core::vector3df(-1.000000, -1.000000, 1.000000);
	v.Normal = core::vector3df(-0.577350, -0.577350, 0.577350);
	v.Color = SColor(255,204,204,204);
	v.TCoords = core::vector2d<f32>(0.f, 0.f);
	testmap.insert(v, 1);
	
	v.Pos = core::vector3df(1.000000, 1.000000, 1.000000);
	v.Normal = core::vector3df(0.577350, 0.577350, 0.577350);
	v.Color = SColor(255,204,204,204);
	v.TCoords = core::vector2d<f32>(0.f, 0.f);
	testmap.insert(v, 2);
	
	v.Pos = core::vector3df(1.000000, -1.000000, 1.000000);
	v.Normal = core::vector3df(0.577350, -0.577350, 0.577350);
	v.Color = SColor(255,204,204,204);
	v.TCoords = core::vector2d<f32>(0.f, 0.f);
	
	core::map<video::S3DVertex, int>::Node* n = testmap.find(v);
	if (n)
	{
		printf("found\n");
	}
	else
	{
		printf("not found\n");
	}

	return 0;
}
That's basically what is happening while entering the vertices in the loader. I have no more time right now. but looks to me like a problem in the core::map unless I'm missing here something.

Note that the vertex I'm looking for is identical to the first one. If I add less than 3 vertices it is still found.

Tested with newest svn.

edit: A few more short tests seem to hint that it's not the map to blame but the comparison operators of S3DVertex (works with other types).

edit2 (last edit now): I suppose the problem is that vector3d does use a tolerance for operator == but not for operator <. Don't know what the best solution to that is.
IRC: #irrlicht on irc.libera.chat
Code snippet repository: https://github.com/mzeilfelder/irr-playground-micha
Free racer made with Irrlicht: http://www.irrgheist.com/hcraftsource.htm
eye776
Posts: 94
Joined: Sun Dec 28, 2008 11:07 pm

Post by eye776 »

Ok, for all practical purposes, the problem IS SOLVED.
I can vouch for the OBJ and X formats (enough for me to get what I wanted done :P ).
CuteAlien
Admin
Posts: 9734
Joined: Mon Mar 06, 2006 2:25 pm
Location: Tübingen, Germany
Contact:

Post by CuteAlien »

eye776 wrote:Ok, for all practical purposes, the problem IS SOLVED.
Hm, but not yet in the engine, right? I would prefer not to have that already marked as [FIXED], because you stumpled upon some rather interesting problem here, which should also be fixed in the engine.

First your operator operator< and operator> look more correct to me than those which are right now in the engine.

And then there is still the thing that operator == and != use equals with tolerance while those operators all don't do that. And there are rather several ways this could be solved.

1. Ignore it - maybe it's correct already (or does not really matter) and I just don't see it as I'm not so deeply involved in that design of those classes and didn't give it too much thought yet (I would need some test-cases first to figure out if that really still causes problems or not once your new operators are used).
2. operator == and != could remove the tolerance. I think that's the common way to handle that in c++ as those operators usually are just symetric to operator =. But that would mean that it should probably be replaced by equals in many calls, so that could be some work.
3. Other operators could also work with same tolerance. Probably not much work and maybe the thing most people would expect.
4. As 3 but with a global parameter for the vector tolerance which can be set by the user (maybe my favorite solution).
5. As 3 but with a per-object (*shudder*) tolerance value. Just mentioning it.

I guess I better add an entry to the bugtracker.
IRC: #irrlicht on irc.libera.chat
Code snippet repository: https://github.com/mzeilfelder/irr-playground-micha
Free racer made with Irrlicht: http://www.irrgheist.com/hcraftsource.htm
eye776
Posts: 94
Joined: Sun Dec 28, 2008 11:07 pm

Post by eye776 »

Fine, i unmarked it.

You can't really define an absolute < and > operator for vectors.
You CAN order them by a criterion though:
Examples (bad ones)
1) Length (LOL, no, don't do it)
2) Position Relative to axes (WAAAY too complicated for a game engine)

For the binary formats (which aren't human readable) I can't guarantee anything (no time for testing).
For the text formats (X and OBJ) there are no problems.

This issue doesn't appear when you PROGRAMATICALLY create a mesh.
The LOADERS are written by different persons and as such, not very consistent as to what exactly they use to parse and load the mesh.

This is NOT a CORE engine problem. Also, the core::map class should use comparators rather than relying on operators, but that's just meFor the binary formats (which aren't human readable) I can't guarantee anything (no time for testing).
For the text formats (X and OBJ) there are no problems.

This issue doesn't appear when you PROGRAMATICALLY create a mesh.
The LOADERS are written by different persons and as such, not very consistent as to what exactly they use to parse and load the mesh.

This is NOT a CORE engine problem. Also, the core::map class should use comparators rather than relying on operators, but that's just me.

Anyway, do whatever you want. I just needed the vertex duplication issue gone :D

EDIT: I SHOULD mention that AFAIK not even DirectX has < and > operators for vectors (just == and !=).
What I wrote was chosen because it disperses the <S3DVertex, int> keys better in the map's RB tree (because of x, y, z differences) not because it's mathematically correct.
bitplane
Admin
Posts: 3204
Joined: Mon Mar 28, 2005 3:45 am
Location: England
Contact:

Post by bitplane »

For future reference, the bug is this one
Submit bugs/patches to the tracker!
Need help right now? Visit the chat room
CuteAlien
Admin
Posts: 9734
Joined: Mon Mar 06, 2006 2:25 pm
Location: Tübingen, Germany
Contact:

Post by CuteAlien »

I have changed the operators <, <=, >= and > now for vector2d and vector3d. I decided to add float tolerances to all operators as the == and != used those already. The comparison order is now first X then Y then Z.
IRC: #irrlicht on irc.libera.chat
Code snippet repository: https://github.com/mzeilfelder/irr-playground-micha
Free racer made with Irrlicht: http://www.irrgheist.com/hcraftsource.htm
Mikhail9
Posts: 54
Joined: Mon Jun 29, 2009 8:41 am

Post by Mikhail9 »

It's a sticky issue, mostly as a matter of choosing a convention, which you've now done. I think that the == and != operators are most useful in a graphics engine if they do independently compare x,y and z components, as you have it now. As we're working with computers, that's going to require a tolerance to deal with machine precision round-off, which you have also implemented.

It does get a little iffy when you start making greater-than and less-than operators, though. I personally would expect these to operate using some sort of vector norm (like comparing the length of the vectors). Otherwise you're forced to make an ordered comparison of the components, as CuteAlien has done. I'm not sure in what circumstances that would actually be useful; probably I would need a different order if it ever were useful. That's just the way things go.

Anyway, it seems a strange convention. One that you don't run across in general math. Only time will tell how it is received by the masses.
CuteAlien
Admin
Posts: 9734
Joined: Mon Mar 06, 2006 2:25 pm
Location: Tübingen, Germany
Contact:

Post by CuteAlien »

Just to explain my reasoning a little more:

I did go for ordering by components because this comparison is used for example for putting vectors in a map and finding them again there later (within the context of S3DVertex). So the main idea of the operators was to make each vector unique as long as it's not just different due to floating point differences. Ordering by components is unique while ordering by length would mean that for example we could not sort (1,2,1) and (2,1,1) as they would be seen as identical.

edit: Btw. - as a concrete use-case you can look at the code I have posted in this thread above. Identical code is now used as a test-case.
IRC: #irrlicht on irc.libera.chat
Code snippet repository: https://github.com/mzeilfelder/irr-playground-micha
Free racer made with Irrlicht: http://www.irrgheist.com/hcraftsource.htm
hybrid
Admin
Posts: 14143
Joined: Wed Apr 19, 2006 9:20 pm
Location: Oldenburg(Oldb), Germany
Contact:

Post by hybrid »

It's indeed absolutely necessary to have a total order on things which are put into sorting containers. And this is clearly not a typical thing for math, which is why you don't see such orders for vectors that often outside computer science. But, total orders are also quite useful in math, otherwise it would be hard to see that rational vectors are still enumerable :)
vitek
Bug Slayer
Posts: 3919
Joined: Mon Jan 16, 2006 10:52 am
Location: Corvallis, OR

Post by vitek »

It would be way better if the user of the container could specify the sorting/comparison function to be used. This way the comparison operators for classes don't have to be changed.

Travis
CuteAlien
Admin
Posts: 9734
Joined: Mon Mar 06, 2006 2:25 pm
Location: Tübingen, Germany
Contact:

Post by CuteAlien »

vitek wrote:It would be way better if the user of the container could specify the sorting/comparison function to be used. This way the comparison operators for classes don't have to be changed.
Travis
Yes, that is another change (I actually patched that already in a local Irrlicht of mine for the heapsort once, but I don't dare touching the irrMap so far. I hope I find time for that patch also, but that's probably something for 1.8 as I still have to write tests and we have already a feature freeze).

Do you think the old operator <, which was implemented as "x<other.x && y<other.y && z<other.z" was really useful for something? At least for the sorting (which is the only place I know it was used) it was simply wrong and caused bugs as you can probably see. Do I miss something and there is a situation in which the old implementation made (more) sense? Because I actually prefer the new version also because all comparisons between 2 vectors are now defined. In the old version a lot of comparison where left undefined (all comparisons failed) and you could also have for example stuff like a < b at the same time than a == b.
IRC: #irrlicht on irc.libera.chat
Code snippet repository: https://github.com/mzeilfelder/irr-playground-micha
Free racer made with Irrlicht: http://www.irrgheist.com/hcraftsource.htm
Post Reply