PDA

View Full Version : Removing duplicate vertices



JSoftware
24-10-2005, 07:51 PM
Hello PGD! :D

right at this moment you hopefully aren't able to see me but if you could then you would see a crying man on his knees! i wanted to actually finish something so i started coding a general purpose mesh editor(rather viewer and optimizer than editing..) for my meshformat. now i have made a very good stripification algorithm which is fully implemented and working. now this one ofcourse only works if the indices are over the same vertices. i need to have a procedure to remove all duplicate vertices.

i've sitten here for 2 days coding this and it just won't work. i can make it find a list of all duplicate vertices and it's correct but how would i go and both remove these and edit all the faces indices(and at both time take care of the altered offset)?

my mesh is declared like this:
tface = record
points: array of integer;
end;

tmesh = record
vertices: array of tvertex;
faces: array of tface;
end;

so atm i have something like this in my cleanup proc:


var i,i2: integer;
begin
for i := high(mesh.vertices) downto 0 do
begin
for i2 := 0 to i do
begin
if equal(mesh.vertices[i].pos, mesh.vertices[i2].pos) then
begin
//here we have either a duplicate vertice or the vertice itself meaning that i2 is the first vertex of it's kind
end;
end;
end;
end;


i've tried many things from here. when i just set the new vertices in all faces it all works well. if i run a loop for each vertice downto 0 and remove it if it's not used and in the same run decrement each index that is over that index i would suppose it should work?
however it just shows up as being completely random!

Help me guys! :cry:

Clootie
24-10-2005, 08:24 PM
Make it two pass:
1) First do comparision, assigning new indices, marking vertex as no more used (for example setting it to [inf, inf, inf]).
2) Scan all your vertex array for unused vertices and either :
(a) compact it one-by-one -> move all vertices down one slot; scan all indices and if index is larger than cleaned vertex number - decrement int by 1.
(b) build list of unused vertices (while compacting them) and after this compact and reassign all indices in single pass.

(b) is probably harder to implement / debug, but I'm not sure: will it gain you significant performance increase?

Paulius
24-10-2005, 09:25 PM
Do it like clootie suggested, or in a worst case dump everything in one big vertex array and recreate indices, like I did in this thread (http://www.pascalgamedevelopment.com/viewtopic.php?t=2375).