DarkBASIC Professional Discussion->Welding vertex data, another method
V
Visigoth Joined: 8th Jan 2005
Location: Bakersfield, California
Posted: 22nd Jun 2007 7:24
I know there is a thread already open about welding vertices, but, this is different enough, and I think cool enough, it deserves its own thread. So, here it is, a function to weld vertices on static objects. And what I mean by static is objects that have no animations. I haven't tested that yet, so can't say if it will work. The function has just one parameter, the object ID of the object you want welded.
To try it out, just add it to your program, and pass an object into it. It will recreate the object with the same ID. You have to put the type at the top of your code, and there is one global variable, as well, the creation of the type.
+ Code Snippet
REM *** Include File: objects.dba ***
REM Created: 6/20/2007 2:39:06 AM
REM Created by Mike Shihrer aka Visigoth
REM Free to use and modify, just a credit would be nice
REM Special thanks to IanM for getting me to think about this!
REM Included in Project: E:\Dev\Projects\grids\grids.dbpro
REM

function weld_vertices(id as integer)
remstart
rem put this at the top of your code

type vdata
   x1 as float
   y1 as float
   z1 as float
   index as integer
   index2 as integer
   x2 as float
   y2 as float
   z2 as float
   match as boolean
endtype
Global Dim copyv(1) as vdata

remend
undim copyv()
numVerts = 0
vc = 0
rem create a mesh from an object
make mesh from object 1,id
rem save it to an .x file, so you can see the differences. This is not necessary, and can be deleted.
save mesh "beforeweld_obj"+str$(id)+".x",1
delete object id
lock vertexdata for mesh 1
rem get the total number of indexes (polys) and total number of vertex x,y,z coordinates
vi = get vertexdata index count()
vc = get vertexdata vertex count()
rem create our type array
Global Dim copyv(vi) as vdata

rem copy vertex data into type array
for i = 1 to vi
   copyv(i).index = get indexdata(i -1)
   copyv(i).x1 = get vertexdata position x(copyv(i).index)
   copyv(i).y1 = get vertexdata position y(copyv(i).index)
   copyv(i).z1 = get vertexdata position z(copyv(i).index)
   copyv(i).index2 = 0
   copyv(i).x2 = 0
   copyv(i).y2 = 0
   copyv(i).z2 = 0
next vi

rem look for duplicate vertices, and flag them
for i = 1 to vi
   for j = i + 1 to vi
      if copyv(i).x1 = copyv(j).x1 and copyv(i).y1 = copyv(j).y1 and copyv(i).z1 = copyv(j).z1
         copyv(j).match = 1
      endif
   next j
next i

rem get the total count of unique vertices, copy them into type array
for i = 1 to vi
   If copyv(i).match = 0
      copyv(numVerts + 1).x2 = copyv(i).x1
      copyv(numVerts + 1).y2 = copyv(i).y1
      copyv(numVerts + 1).z2 = copyv(i).z1
      copyv(numVerts + 1).index2 = numVerts rem remove this?
      inc numVerts,1
   endif
next i

rem compare the unique verts to the original verts, and write the index data to the type array
for i = 1 to numVerts
   for j = 1 to vi
    if copyv(i).x2 = copyv(j).x1 and copyv(i).y2 = copyv(j).y1 and copyv(i).z2 = copyv(j).z1
         copyv(j).index = copyv(i).index2
    endif
   next j
next i

rem resize the vertexdata to allow for only unique vertices
delete mesh from vertexdata numVerts,vc,0,0
rem write the vertices to the vertexdata
for i = 1 to numverts
   set vertexdata position (i - 1),copyv(i).x2,copyv(i).y2,copyv(i).z2
next i

rem and finally, update the indexdata so faces draw the same
for i = 1 to vi
   set indexdata (i - 1),copyv(i).index
next i

unlock vertexdata
make object id,1,0

rem create normals data for vertices
set object normals id
save mesh "afterweld_obj"+str$(id)+".x",1
delete mesh 1
undim copyv()

endfunction

Now, I have to admit I could have never wrote this without seeing IanM's code, so I thank him right now for getting me to think about this. Now, the key differences between my method and his.

1. You only need 1 type array
2. Uses DBPros built in command, SET OBJECT NORMALS for calculating normals values, if you wish.
3. All manipulation of the vertexdata is done within the array, so only two write backs to the vertexdata.
4. Writes a "before" and "after" .x file of the mesh, so you can see the actual effect of the weld operation.

Things left to do:
actually, just UV mapping, but that should actually be a function by itself, because you need to know the order the polys are drawn to map properly.

I did this so I can create my own matrixs, because the built in DBPro matrix and terrain commands are not doing what I want them to do. After doing this, I discovered that those few vertexdata commands we have access to are REALLY REALLY powerful. I now have a complete, firm grasp of every command relating to vertexdata, so if you have any questions, fire away!
T
tiresius Joined: 13th Nov 2002
Location: MA USA
Posted: 22nd Jun 2007 7:30
What's the benefit of welding vertices? Does it make the object a lot smaller in memory? Quicker to render? Thanks.
V
Visigoth Joined: 8th Jan 2005
Location: Bakersfield, California
Posted: 22nd Jun 2007 7:37
ah, the BIG question. Welding vertices allows faces, or polys that share the same point in 3d space to be manipulated by moving just the one point. The way a DBPro cube is drawn, it has 12 polys, two triangles per side. Since there are six sides to a cube, thats 12 polys. Now, it also creates the cube with 36 veritices, three per triangle, 6 per face, 6x6 is 36. You only need 8. All the rest are duplicates. Now, since each triangle has its own set of vertices, if you want to move the corner of the cube, without welding you'd have to move 6 vertices individually, because 6 triangles actually touch that one corner. So, by eliminating the duplicates, and you really aren't eliminating anything, you are just telling the vertexdata to look at only the unique ones, you can move all 6 triangle points by moving just one vertice. This will allow for EASY creation of your own matrixs. And, since they are just objects, you can put them anywhere you want.
V
Visigoth Joined: 8th Jan 2005
Location: Bakersfield, California
Posted: 22nd Jun 2007 8:11
I'm going to give you an example, here of what I am talking about. this is also giving up a big secret I've been playing with for a while. I think its ready now.
+ Code Snippet
REM Project: Demo
REM Created: 6/21/2007 9:47:00 PM
REM Created by Mike Shihrer aka Visigoth
REM ***** Main Source File *****
REM


set display mode 1024,768,32
autocam off
sync on
sync rate 0

type vdata
   x1 as float
   y1 as float
   z1 as float
   index as integer
   index2 as integer
   x2 as float
   y2 as float
   z2 as float
   match as boolean
endtype
Global Dim copyv(1) as vdata

position camera 0,50,0

make_grid(1,1000,1000,20,20)
weld_vertices(1)

make mesh from object 1,1
delete object 1
lock vertexdata for mesh 1

vc = get vertexdata vertex count()

for i = 0 to vc
   set vertexdata position i, get vertexdata position x(i),get vertexdata position y(i) + rnd(20), get vertexdata position z(i)
next i

unlock vertexdata

make object 1,1,0
delete mesh 1
set object wireframe 1,1

rem xrotate object 1,90


do
   display_data()
   move_camera()
   sync
loop



function weld_vertices(id as integer)
remstart
rem put this at the top of your code

type vdata
   x1 as float
   y1 as float
   z1 as float
   index as integer
   index2 as integer
   x2 as float
   y2 as float
   z2 as float
   match as boolean
endtype
Global Dim copyv(1) as vdata

remend
undim copyv()
numVerts = 0
vc = 0
rem create a mesh from an object
make mesh from object 1,id
rem save it to an .x file, so you can see the differences. This is not necessary, and can be deleted.
save mesh "beforeweld_obj"+str$(id)+".x",1
delete object id
lock vertexdata for mesh 1
rem get the total number of indexes (polys) and total number of vertex x,y,z coordinates
vi = get vertexdata index count()
vc = get vertexdata vertex count()
rem create our type array
Global Dim copyv(vi) as vdata

rem copy vertex data into type array
for i = 1 to vi
   copyv(i).index = get indexdata(i -1)
   copyv(i).x1 = get vertexdata position x(copyv(i).index)
   copyv(i).y1 = get vertexdata position y(copyv(i).index)
   copyv(i).z1 = get vertexdata position z(copyv(i).index)
   copyv(i).index2 = 0
   copyv(i).x2 = 0
   copyv(i).y2 = 0
   copyv(i).z2 = 0
next vi

rem look for duplicate vertices, and flag them
for i = 1 to vi
   for j = i + 1 to vi
      if copyv(i).x1 = copyv(j).x1 and copyv(i).y1 = copyv(j).y1 and copyv(i).z1 = copyv(j).z1
         copyv(j).match = 1
      endif
   next j
next i

rem get the total count of unique vertices, copy them into type array
for i = 1 to vi
   If copyv(i).match = 0
      copyv(numVerts + 1).x2 = copyv(i).x1
      copyv(numVerts + 1).y2 = copyv(i).y1
      copyv(numVerts + 1).z2 = copyv(i).z1
      copyv(numVerts + 1).index2 = numVerts rem remove this?
      inc numVerts,1
   endif
next i

rem compare the unique verts to the original verts, and write the index data to the type array
for i = 1 to numVerts
   for j = 1 to vi
    if copyv(i).x2 = copyv(j).x1 and copyv(i).y2 = copyv(j).y1 and copyv(i).z2 = copyv(j).z1
         copyv(j).index = copyv(i).index2
    endif
   next j
next i

rem resize the vertexdata to allow for only unique vertices
delete mesh from vertexdata numVerts,vc,0,0
rem write the vertices to the vertexdata
for i = 1 to numverts
   set vertexdata position (i - 1),copyv(i).x2,copyv(i).y2,copyv(i).z2
next i

rem and finally, update the indexdata so faces draw the same
for i = 1 to vi
   set indexdata (i - 1),copyv(i).index
next i

unlock vertexdata
make object id,1,0

rem create normals data for vertices
rem set object normals id
save mesh "afterweld_obj"+str$(id)+".x",1
delete mesh 1
undim copyv()
set object wireframe id,1
endfunction

function make_grid(id as integer,x_width as float, z_height as float,x_segments as integer,z_segments as integer)

unitwidth# = x_width / x_segments
unitheight# = z_height / z_segments
xpos# = 0
zpos# = 0
J = 1

make object triangle 1,0,0,0,0,0,1,1,0,0
make mesh from object 1,1
lock vertexdata for mesh 1
delete mesh from vertexdata 0,3,0,3
unlock vertexdata
delete object 1

for I = 1 to x_segments
   lock vertexdata for mesh 1
   make object triangle 2,xpos#,0,zpos#,xpos#,0,zpos# + unitheight#,xpos# + unitwidth#,0,zpos#
   make object triangle 3,xpos#,0,zpos# + unitheight#,xpos# + unitwidth#,0,zpos# + unitheight#,xpos# + unitwidth#,0,zpos#
   make mesh from object 2,2
   make mesh from object 3,3
   add mesh to vertexdata 2
   add mesh to vertexdata 3
   delete mesh 2
   delete mesh 3
   unlock vertexdata
   delete object 2
   delete object 3
   inc xpos#, unitwidth#
If J < z_segments
   If I = x_segments
      Inc J,1
      inc zpos#,unitheight#
      xpos# = 0
      I = 0
   endif
endif
next I

make object id,1,0
set object wireframe id,1
delete mesh 1

endfunction

function move_camera()

if upkey() then move camera 1
if downkey()then move camera -1
if leftkey() then turn camera left 1
if rightkey() then turn camera right 1

endfunction



function display_data()
text 0,0,"Total Polygons :" + str$(statistic(1))




endfunction

There is a line of code in there that is commented out. It is xrotate object 1,90
take the coment line out after you run it, you are going to get a kick out of the result.
Yup, a modifiable mesh that you can put anyway you want. What can I do with it?
Well, some ideas, use for ceilings in caves, simulate stalagtites(sp?). Really bumpy walls. Wanna be able to WALK on walls?
Break into a grayscale .bmp. sized to the same size as the grid. Read the color value, and set it to the y value in the grid. Yup. A heightmap for a matrix. There is one flaw with this, and it's the same flaw with all the matrixs, and thats how the triangles are drawn. For a real matrix, the triangles should alternate, so if you pull up on the middle vertex of a four square, it looks like a pyramid. I am working on fixing that.
V
Visigoth Joined: 8th Jan 2005
Location: Bakersfield, California
Posted: 22nd Jun 2007 10:46
well, after some more testing, it seems I jumped the gun here. It works, but when you get BIG meshes, over 15,000 polys, things really bog down. But the good news is, there is no reason this could not be converted to memblocks. So, back to the drawing board.
G
Green Gandalf Joined: 3rd Jan 2005
Location: Malevolence:Sword of Ahkranox, Skyrim, Civ6.
Posted: 22nd Jun 2007 12:56
well, after some more testing, it seems I jumped the gun here. It works, but when you get BIG meshes, over 15,000 polys, things really bog down


The same thing happens to IanM's code so don't be put off by that. Have you compared the two methods for speed?

I haven't looked at your code but the problem with IanM's code is probably the way vertices are searched for matches - when you are constructing your own meshes, as in simple terrain examples, that step is not really necessary because you should know which vertices are repeated in your mesh (since you created them yourself).

Having said that, I'm still using IanM's code and am just putting up with the 10 minute wait while it searches for matching vertices. But one day I'll write my own code to use the vertex matching information that I already have ...
I
IanM Joined: 11th Sep 2002
Location: In my moon base
Posted: 22nd Jun 2007 15:33
@Visigoth,
Well done
with texture coordinates, my code just assumes that they are present and correct. If they are, this avoids welding vertices that need to have different texture coordinates - if you are building a big terrain object though, there's no need to worry to much about it as you can add them afterwards based upon the vertex positions.

The speed is something that I don't think is easy to get around - every time you add another vertex you add another N-1 comparisons. TBH, I didn't realise that it was being used for such large objects, and you would normally optimise your objects once and save them anyway.

There are two ways to fix this:
- Convert to a faster language, such as using a C++ plug-in. You may now be able to do your comparisons twice as fast, but you'll soon hit the same performance bottleneck although admittedly at a higher number of vertices.

Using example numbers with completely made-up timings - say that you can run an object of 5 vertices through the DBPro code in 1 second. Converting the code to a DLL means that you can now run it in half a second - now you can process more vertices in that 1 second, right? Well, disappointing as it may sound, you get to add another 2 vertices before you lose that gain.

+ Code Snippet
1    -> 0 comparisons
2    -> 1 comparison
3    -> 3 comparisons
4    -> 5 comparisons
5    -> 10 comparisons
6    -> 15 comparisons
7    -> 21 comparisons
8    -> 28 comparisons
9    -> 36 comparisons
10   -> 45 comparisons

Adding 2 extra vertices takes you from 10 comparisons up to 21 comparisons.

There's really no way to win by doing the same thing you are now, but faster. Which leads to ...

- Change the algorithm. There are one or two alternatives that could reduce the number of comparisons that I'll need to look in to. Effectively, what we have at the moment has the same complexity as a bubblesort - we need the equivalent complexity of quicksort.
G
Green Gandalf Joined: 3rd Jan 2005
Location: Malevolence:Sword of Ahkranox, Skyrim, Civ6.
Posted: 22nd Jun 2007 19:02
There are two ways to fix this


For general "unseen" objects I agree - but not for simple terrain objects which you might be building yourself. We probably need two versions of your code: (1) your original one for general objects(perhaps with modifications such as the one I'm using now and those you are suggesting); (2) a version which is supplied with the vertex matching list "ready-made" as data.

Change the algorithm. There are one or two alternatives that could reduce the number of comparisons that I'll need to look in to. Effectively, what we have at the moment has the same complexity as a bubblesort - we need the equivalent complexity of quicksort.


Agreed.

I think the order of that is nlog(n) rather than nxn which will make a BIG difference with 1000s of vertices.

That would be a very useful amendment to your original code.
V
Visigoth Joined: 8th Jan 2005
Location: Bakersfield, California
Posted: 22nd Jun 2007 22:40

Having said that, I'm still using IanM's code and am just putting up with the 10 minute wait while it searches for matching vertices. But one day I'll write my own code to use the vertex matching information that I already have ...


hmm. I have been sucessful with meshes up to 15000 polys, and the function will weld them in seconds, not minutes. But the problem is objects in general. If I make a regular matrix even, with more than 15000 polys and just try to display it, it really really hits the frame rate. I think this is why I need to learn to use memblocks. I don't think you can really do anything big without them. Also, I have a better idea on how to create my matrixs. I realize now I don't have to make two triangles. I just need a list of vertices, and in index to point at the vertices. So, I'll have the grid function greatly improved later tonight after I get off work.
Thanks for your comments and insights.
V
Visigoth Joined: 8th Jan 2005
Location: Bakersfield, California
Posted: 24th Jun 2007 22:13
well, I've been playing around a bit, and I added some timer code to see just how long it takes to do the welds on my grids. Also, I don't quite know why, but all of a sudden I'm doing over 20,000 polys and no real hit on the framerate. Anyway, I am doing this at work on a real POS computer, like a 2 gig regular Athlon, I think. I'd like to see what the numbers are on a really fast pc, like a core Duo or x2. So, if someone doesn't mind, could you run this code and post the results? Start with the grid size small. When I do a 20k poly grid, I set it to 2000,2000,100,100.
Thanks if you do this for me.
BTW, for this example, 1800 polys, takes 3.25 seconds to generate, 1.51 seconds to weld.
+ Code Snippet
REM Project: Demo
REM Created: 6/21/2007 9:47:00 PM
REM Created by Mike Shihrer aka Visigoth
REM ***** Main Source File *****
REM


set display mode 1024,768,32
autocam off
sync on
sync rate 0

type vdata
   x1 as float
   y1 as float
   z1 as float
   index as integer
   index2 as integer
   x2 as float
   y2 as float
   z2 as float
   match as boolean
endtype
Global Dim copyv(1) as vdata
Global tw_time#
Global tc_time#

position camera 0,20,0

rem make_grid params: Object ID, grid width, grid height, squares per width, squares per height
make_grid(1,2000,2000,30,30)
weld_vertices(1)

rem randomize_grid params: Object ID, x position, y position, z position
randomize_grid(1,0,15,0)
set object wireframe 1,1

rem /////////////////////////////Main Loop///////////////////////////////////
do
   display_data1()
   move_camera1()
   sync
loop
rem ////////////////////////////////////////////////////////////////////////

function weld_vertices(id as integer)
remstart
rem put this at the top of your code

type vdata
   x1 as float
   y1 as float
   z1 as float
   index as integer
   index2 as integer
   x2 as float
   y2 as float
   z2 as float
   match as boolean
endtype
Global Dim copyv(1) as vdata

remend
a_time = timer()
undim copyv()
numVerts = 0
vc = 0
rem create a mesh from an object
make mesh from object 1,id
rem save it to an .x file, so you can see the differences. This is not necessary, and can be deleted.
rem save mesh "beforeweld_obj"+str$(id)+".x",1
delete object id
lock vertexdata for mesh 1
rem get the total number of indexes (polys) and total number of vertex x,y,z coordinates
vi = get vertexdata index count()
vc = get vertexdata vertex count()
rem create our type array
Global Dim copyv(vi) as vdata

rem copy vertex data into type array
for i = 1 to vi
   copyv(i).index = get indexdata(i -1)
   copyv(i).x1 = get vertexdata position x(copyv(i).index)
   copyv(i).y1 = get vertexdata position y(copyv(i).index)
   copyv(i).z1 = get vertexdata position z(copyv(i).index)
   copyv(i).index2 = 0
   copyv(i).x2 = 0
   copyv(i).y2 = 0
   copyv(i).z2 = 0
next vi

rem look for duplicate vertices, and flag them
for i = 1 to vi
   for j = i + 1 to vi
      if copyv(i).x1 = copyv(j).x1 and copyv(i).y1 = copyv(j).y1 and copyv(i).z1 = copyv(j).z1
         copyv(j).match = 1
      endif
   next j
next i

rem get the total count of unique vertices, copy them into type array
for i = 1 to vi
   If copyv(i).match = 0
      copyv(numVerts + 1).x2 = copyv(i).x1
      copyv(numVerts + 1).y2 = copyv(i).y1
      copyv(numVerts + 1).z2 = copyv(i).z1
      copyv(numVerts + 1).index2 = numVerts rem remove this?
      inc numVerts,1
   endif
next i

rem compare the unique verts to the original verts, and write the index data to the type array
for i = 1 to numVerts
   for j = 1 to vi
    if copyv(i).x2 = copyv(j).x1 and copyv(i).y2 = copyv(j).y1 and copyv(i).z2 = copyv(j).z1
         copyv(j).index = copyv(i).index2
    endif
   next j
next i

rem resize the vertexdata to allow for only unique vertices
delete mesh from vertexdata numVerts,vc,0,0
rem write the vertices to the vertexdata
for i = 1 to numverts
   set vertexdata position (i - 1),copyv(i).x2,copyv(i).y2,copyv(i).z2
next i

rem and finally, update the indexdata so faces draw the same
for i = 1 to vi
   set indexdata (i - 1),copyv(i).index
next i

unlock vertexdata
make object id,1,0

rem create normals data for vertices
set object normals id
rem save mesh "afterweld_obj"+str$(id)+".x",1
delete mesh 1
undim copyv()
b_time = timer()
tw_time# = (b_time - a_time) * .001

endfunction

function make_grid(id as integer,x_width as float, z_height as float,x_segments as integer,z_segments as integer)
a_time = timer()
unitwidth# = x_width / x_segments
unitheight# = z_height / z_segments
xpos# = 0
zpos# = 0
J = 1

make object triangle 1,0,0,0,0,0,1,1,0,0
make mesh from object 1,1
lock vertexdata for mesh 1
delete mesh from vertexdata 0,3,0,3
unlock vertexdata
delete object 1

for I = 1 to x_segments
   lock vertexdata for mesh 1
   make object triangle 2,xpos#,0,zpos#,xpos#,0,zpos# + unitheight#,xpos# + unitwidth#,0,zpos#
   make object triangle 3,xpos#,0,zpos# + unitheight#,xpos# + unitwidth#,0,zpos# + unitheight#,xpos# + unitwidth#,0,zpos#
   make mesh from object 2,2
   make mesh from object 3,3
   add mesh to vertexdata 2
   add mesh to vertexdata 3
   delete mesh 2
   delete mesh 3
   unlock vertexdata
   delete object 2
   delete object 3
   inc xpos#, unitwidth#
If J < z_segments
   If I = x_segments
      Inc J,1
      inc zpos#,unitheight#
      xpos# = 0
      I = 0
   endif
endif
next I

make object id,1,0
delete mesh 1
b_time = timer()
tc_time# = (b_time - a_time) * .001
endfunction

function move_camera1()

if upkey() then move camera 1
if downkey()then move camera -1
if leftkey() then turn camera left 1
if rightkey() then turn camera right 1

endfunction

function display_data1()
   text (screen width()/2),0, "Use arrow keys to move"
   text 0,0,"Total Polygons: " + str$(statistic(1))
   text 0,10,"Screen FPS: " + str$(screen fps())
   text 0,20,"Index Count: " + str$(vi)
   text 0,30,"Vertex Count: " + str$(vc)
   text 0,40,"Make Time: " + str$(tc_time#) + " seconds"
   text 0,50,"Weld Time: " + str$(tw_time#) + " seconds"
endfunction

function randomize_grid(id as integer,x_val as float, y_val as float, z_val as float)
make mesh from object 1,id
delete object id
lock vertexdata for mesh 1
vc = get vertexdata vertex count()

for i = 0 to vc
   set vertexdata position i, get vertexdata position x(i) + Rnd(x_val),get vertexdata position y(i) + rnd(y_val), get vertexdata position z(i) + rnd(z_val)
next i

unlock vertexdata
make object 1,1,0
delete mesh 1
endfunction
V
Visigoth Joined: 8th Jan 2005
Location: Bakersfield, California
Posted: 25th Jun 2007 7:20
well, no takers?
ok, anyway, I'm home now, and on my Athlon 64 3000, same code returns
make: 0.79 seconds
weld: 1.90 seconds

so, cpu really makes a difference.
G
Green Gandalf Joined: 3rd Jan 2005
Location: Malevolence:Sword of Ahkranox, Skyrim, Civ6.
Posted: 26th Jun 2007 0:30
On my Pentium III/930MHz machine I get:

make: 11.1 secs
weld: 4.3 secs

The display also shows "0 vertices" and "0 indices". Is that correct?

And, yes, CPU does make a difference.
J
Johaness Joined: 20th Sep 2006
Location:
Posted: 26th Jun 2007 2:51
Pentium4 2.4Mhz

make: 4.85
weld: 1.54
V
Visigoth Joined: 8th Jan 2005
Location: Bakersfield, California
Posted: 27th Jun 2007 3:22
GG-
yes, thats correct because I was using those variables for information I am no longer reporting in this code. I just forgot to strip out the line in the displaydata() function. But one thing, that is way too slow. The weld isn't too bad, but, the grid really needs work. thanks both of you guys.
D
dononeton Joined: 12th Jun 2004
Location: Tusaloosa, AL : USA
Posted: 27th Jun 2007 4:27
3800 amd athlon 2 core
make 1.3
weld 1.8
V
Visigoth Joined: 8th Jan 2005
Location: Bakersfield, California
Posted: 27th Jun 2007 4:54
dononeton-
wow, thats not what I expected, not at all. I'm running single core and am faster? Your rig should smoke mine. Is that result with the 1800 polys?
It's looking like the weld is doing fairly weld, its my grid that is real slow, BUT, and keep your fingers crossed, I think I figured out a neat little way to make the grid a whole lot faster. Testing it now, stay tuned....
V
Visigoth Joined: 8th Jan 2005
Location: Bakersfield, California
Posted: 28th Jun 2007 13:21
EDIT: For some reason, spheres aren't working now, they worked fine before. So, try spheres at your own risk. Its throwing exceptions up.
Edit: ok, found the bug, spheres work now
UPDATE:
Ok, I found two spots in the code where things were really bogging down. Made a couple small changes, made a big difference. Also, I found out that after you weld an object, you can't tile a texture anymore, because of the shared verts. So, I wrote in a little block of code that will stretch an image across the entire object. I also found a way to make my grids WAY WAY WAY faster, and without memblocks, but this is also a kind of cool trick, so I think its going to get its own thread, but I want to make sure it hasn't been brought up before first. Anyway, here is the new function. It has 2 parameters now, object ID and UV flag. Set UV flag to 0 for no mapping, or 1 for stretch mapping.
+ Code Snippet
function weld_vertices(id as integer,texturemode as integer)
remstart
rem put this at the top of your code

type vdata
   x1 as float
   y1 as float
   z1 as float
   u as integer
   v as integer
   index as integer
   index2 as integer
   x2 as float
   y2 as float
   z2 as float
   match as boolean
endtype
Global Dim copyv(1) as vdata

remend
rem a_time# = timer()
undim copyv()
numVerts = 0
vc = 0
rem create a mesh from an object
make mesh from object 1,id
rem save it to an .x file, so you can see the differences. This is not necessary, and can be deleted.
save mesh "beforeweld_obj"+str$(id)+".x",1
delete object id
lock vertexdata for mesh 1
rem get the total number of indexes (polys) and total number of vertexs
vi = get vertexdata index count()
vc = get vertexdata vertex count()
rem create our type array
Global Dim copyv(vi) as vdata

rem copy vertex data into type array
for i = 1 to vi
   copyv(i).index = get indexdata(i -1)
   copyv(i).x1 = get vertexdata position x(copyv(i).index)
   copyv(i).y1 = get vertexdata position y(copyv(i).index)
   copyv(i).z1 = get vertexdata position z(copyv(i).index)
   copyv(i).index2 = 0
   copyv(i).x2 = 0
   copyv(i).y2 = 0
   copyv(i).z2 = 0
next vi

rem look for duplicate vertices, and flag them this took 4.4 seconds on 3200 polys this is the slow part
for i = 1 to vi
   if copyv(i).match = 0 rem this fixed the slowness a bunch, only check the list if not already marked a match
      for j = i + 1 to vi
         if copyv(i).x1 = copyv(j).x1 and copyv(i).y1 = copyv(j).y1 and copyv(i).z1 = copyv(j).z1
            copyv(j).match = 1
         endif
      next j
   endif
next i


rem get the total count of unique vertices, copy them into type array
for i = 1 to vi
   If copyv(i).match = 0
      copyv(numVerts + 1).x2 = copyv(i).x1
      copyv(numVerts + 1).y2 = copyv(i).y1
      copyv(numVerts + 1).z2 = copyv(i).z1
      copyv(numVerts + 1).index2 = numVerts rem remove this?
      inc numVerts,1
   endif
next i

rem compare the unique verts to the original verts, and write the index data to the type array
rem I changed this to preload the x,y.z values into a variable so the code doesn't have to look backwards into the type everytime it compares.
rem this saved about a half second
for i = 1 to numVerts
   x2# = copyv(i).x2
   y2# = copyv(i).y2
   z2# = copyv(i).z2
   i2 = copyv(i).index2
   for j = i to vi
      if copyv(j).x1 = x2# and copyv(j).y1 = y2# and copyv(j).z1 = z2#
         copyv(j).index = i2
      endif
   next j
next i

rem resize the vertexdata to allow for only unique vertices
delete mesh from vertexdata numVerts,vc,0,0
rem write the vertices to the vertexdata
for i = 1 to numverts
   set vertexdata position (i - 1),copyv(i).x2,copyv(i).y2,copyv(i).z2
next i

rem and finally, update the indexdata so faces draw the same
for i = 1 to vi
   set indexdata (i - 1),copyv(i).index
next i
rem set uv coordinates to stretch across object
rem should probably break this down into its own function for different kinds of objects, like mode 0 for my grid, 1 for DBPro cubes, 2 for DBPro box, etc

unlock vertexdata
make object id,1,0
save mesh "afterweld_obj"+str$(id)+".x",1
delete mesh 1

If texturemode = 1
u# =  object size x(id)
v# =  object size z(id)

make mesh from object 1,id
delete object id
lock vertexdata for mesh 1

rem loop throught the texture coordinates and determine what percent of total width, height the vertex is at
for i = 0 to numverts - 1
   set vertexdata uv i, get vertexdata position x(i) / u#, v# - (get vertexdata position z(i) / v#)
next i
unlock vertexdata
make object id,1,0
save mesh "afterweld_obj"+str$(id)+".x",1
delete mesh 1
endif

rem create normals data for vertices
set object normals id
undim copyv()

rem b_time# = timer()
rem tw_time# = (b_time# - a_time#) * .001

endfunction


I documented the changes, again they were small, one loop was searching the list of verts for matches, even if they were already marked as matches. That was the big one. The other loop was a nested loop that didn't need to search from the top every iteration. I don't think I can get this to go any faster without doing anything directly with memory.
V
Visigoth Joined: 8th Jan 2005
Location: Bakersfield, California
Posted: 2nd Jul 2007 12:25
Well, I've been busy
I decided to take the plunge and learn memblocks, which now that I have, I don't see how you can make anything serious without them. So, if you haven't used them, you better learn them, because you'll be glad you did. so, I decided to see if I could write the make_grid() function using memblocks. That was a success, and it works so well, I'll post it in the code snippets. So then I decided to try to do the weld_vertices() function. It too was a success, kind of. It doesn't really do it faster, in fact, it is slower with really large objects. But if all you are doing is primitives, which is what this whole thread was about anyway, then it does them lickety split. The biggest primitive you can have is a sphere, and it's limited to about 1100 verts in the vertexdata, so it can handle it. (100 cols x 100 rows). I know where the lag is in the code, its the two loops that search for the duplicates and order the indexes. I think its because I'm doing the loop and compares on the same memblock. I have an idea how I can speed it up by making a third memblock, and comparing between the two, but for now, this just proves it can be done. Oh, and the advantage so far over the old way, you don't need any global variables or types.
+ Code Snippet
function memblock_weld_vertices(id as integer,texture_mode as integer)
rem Created by Mike Shihrer, aka Visigoth
rem and as always, free to use and modify

a_time# = timer()
make mesh from object 1,id
delete object id
make memblock from mesh 1,1
delete mesh 1

m_size = get memblock size(1)
m_header = memblock dword(1,0)
m_vertices = memblock dword(1,8)

remstart
rem make a new memblock with a new structure to create an index data index
rem for when we write the new index and coordinates to the vertexdata
rem new format will be:

dword /header data
dword /header data
dword /header data
float /x coord position
float /y coord position
float /z coord position
dword /vertex index
dword /index  index
dword /duplicate flag
float /u
float /v

remend
make memblock 2,m_size
m2_size = get memblock size(2)
rem write some header stuff. This is just a buffer space to match original fvf format
write memblock dword 2,0,111
write memblock dword 2,4,222
write memblock dword 2,8,333
rem copy the vertices into the new memblock and create a vertex index
a = 0
For i = 12 to (m_size - 32) step 32
   x1# = memblock float(1,i) : y1# = memblock float(1,i + 4) : z1# = memblock float(1,i + 8)  rem get our triangle data from the original memblock
   write memblock float 2,i,x1# : write memblock float 2,i + 4,y1# : write memblock float 2,i + 8,z1#  rem our triangle data pasted to the new memblock
   write memblock dword 2,i + 12,a    rem this will create a vertex index number
   write memblock dword 2,i + 16,a    rem this will be our indexdata index
   write memblock dword 2,i + 20,0    rem this is our duplicate flag
   write memblock float 2,i + 24,1    rem u mapping data  just going to put 1 here for now
   write memblock float 2,i + 28,1    rem v mapping data  just going to put 1 here for now
   inc a,1
next i

rem loop through the new memblock, look for duplicates and flag them
rem what this will do is flag all duplicate vertices with a 1, uniques will be left at 0
For i = 12 to (m_size - 32) step 32
   x1# = memblock float(2,i) : y1# = memblock float(2,i + 4) : z1# = memblock float(2,i + 8)
   for j = (i + 32) to (m_size - 32) step 32
      x2# = memblock float(2,j) : y2# = memblock float(2,j + 4) : z2# = memblock float(2,j + 8)
      If (x1# = x2#) and (y1# = y2#) and (z1# = z2#)
         write memblock dword 2,i + 20,1
      endif
   next j
next i

rem assign new vertexdata index to the unique vertices
a = 0
For i = 12 to (m_size - 32) step 32
   if memblock dword(2,i + 20) = 0
      write memblock dword 2,i + 12,a
      inc a,1
   endif
next i


rem compare the unique vertices to the duplicate vertices, and write the indexdata value of the duplicate
rem to point at the matching unique vertice
numVerts = 0
For i = 12 to (m_size - 32) step 32
   if memblock dword(2,i + 20) = 0
      x1# = memblock float(2,i) : y1# = memblock float(2,i + 4) : z1# = memblock float(2,i + 8)
      inc numVerts,1
      for j = 12 to (m_size - 32) step 32
         x2# = memblock float(2,j) : y2# = memblock float(2,j + 4) : z2# = memblock float(2,j + 8)
         If (x1# = x2#) and (y1# = y2#) and (z1# = z2#)
            write memblock dword 2,j + 16,memblock dword(2,i + 12)
         endif
      next j
   endif
next i

remstart
rem this is just a block of code to write a data file of what is in the memblock
rem not needed unless you want to see it.

if file exist("memblocktest.txt") = 0
   open to write 1,"memblocktest.txt"
else
   delete file "memblocktest.txt"
   open to write 1,"memblocktest.txt"
endif
For i = 12 to (m2_size - 32) step 32
   write string 1,str$(memblock float(2,i)) + "," + str$(memblock float(2,i + 4)) + "," + str$(memblock float(2,i + 8)) rem x,y,z pos
   write string 1,"vertex index: " + str$(memblock dword(2,i + 12))
   write string 1,"indexdata index: " + str$(memblock dword(2,i + 16))
   write string 1,"duplicate: " + str$(memblock dword(2,i + 20))
   write string 1,"--------------"
next i
close file 1
remend


rem for some reason, you can't delete a mesh from a mesh made from a memblock. Possible bug?
rem so that is why I made a mesh from memblock, then an object, then a mesh from an object

make mesh from memblock 1,1
rem lock vertexdata for mesh 1
rem numVerts = get vertexdata index count()
rem delete mesh from vertexdata numVerts,m_vertices,0,0

make object id,1,0
delete mesh 1
make mesh from object 1,id
delete object id
lock vertexdata for mesh 1
numVerts = get vertexdata index count()
delete mesh from vertexdata numVerts,m_vertices,0,0

rem write the vertices to the vertexdata
a = 0
For i = 12 to (m_size - 32) step 32
   if memblock dword(2,i + 20) = 0
      x1# = memblock float(2,i) : y1# = memblock float(2,i + 4) : z1# = memblock float(2,i + 8)
         set vertexdata position a,x1#,y1#,z1#
         inc a,1
   endif
next i

rem and finally, write the indexdata
a = 0
For i = 12 to (m_size - 32) step 32
      index_value = memblock dword(2,i + 16)
         set indexdata (a),index_value
         inc a,1
next i

unlock vertexdata
make object id,1,0
delete mesh 1
delete memblock 1
delete memblock 2


rem set uv coordinates to stretch across object
rem should probably break this down into its own function for different kinds of objects, like mode 0 for my grid, 1 for DBPro cubes, 2 for DBPro box, etc
rem right now, this just a planar type mapping
If texture_mode = 1
   u# =  object size x(id)
   v# =  object size z(id)
   make mesh from object 1,id
   delete object id
   lock vertexdata for mesh 1
rem loop throught the texture coordinates and determine what percent of total width, height the vertex is at
   a = get vertexdata index count()

   for i = 0 to a
      set vertexdata uv i, get vertexdata position x(i) / u#, get vertexdata position z(i) / v#
   next i

   unlock vertexdata
   make object id,1,0
   rem save mesh "afterweld_obj"+str$(id)+".x",1
   delete mesh 1
endif

b_time# = timer()
tw_time# = (b_time# - a_time#) * .001

endfunction


If you just add this function to the examples I already posted, then call this function with the parameters id(your object id) and texture_mode(0 for no UV map, 1 for stretch UV map), it should go. I commented it pretty good, and even have some file writing code in there so you can see what is going on in the memblock. Have fun.

EDITED TO ADD:
BTW, you must only use objects with an FVF format of 274, which is the standard format in DBPro. This can easily be modified for format 338 if need be, in fact it is on my list to do to check for format, and do either 274 or 338, and reject anything else.
V
Visigoth Joined: 8th Jan 2005
Location: Bakersfield, California
Posted: 9th Jul 2007 8:27
still busy
I know this thread got buried, but, I've made some adjustments to the function. I was able to increase the speed of the search by HALF. Also, I found out by experimentation, that delete mesh from mesh() is not even needed. All you need to do is point the indexdata in the vertexdata buffer to point at the duplicate vertices. So, here it is, in all it's glory
+ Code Snippet
function memblock_weld_vertices(id as integer,texture_mode as integer)

make mesh from object 1,id
save mesh "before_weld_memblock.x",1
delete object id
make memblock from mesh 1,1
delete mesh 1

m_size = get memblock size(1)
m_header = memblock dword(1,0)
m_vertices = memblock dword(1,8)

remstart
rem make a new memblock with a new structure to create an index data index
rem for when we write the new index and coordinates to the vertexdata
rem new format will be:

dword /header data
dword /header data
dword /header data
float /x coord position
float /y coord position
float /z coord position
dword /vertex index
dword /index  index
dword /duplicate flag
float /u
float /v

remend
make memblock 2,m_size
m2_size = get memblock size(2)
rem write some header stuff. This is just a buffer space to match original fvf format
write memblock dword 2,0,111
write memblock dword 2,4,222
write memblock dword 2,8,333
rem copy the vertices into the new memblock and create a vertex index
a = 0
For i = 12 to (m_size - 32) step 32
   x1# = memblock float(1,i) : y1# = memblock float(1,i + 4) : z1# = memblock float(1,i + 8)  rem get our triangle data from the original memblock
   write memblock float 2,i,x1# : write memblock float 2,i + 4,y1# : write memblock float 2,i + 8,z1#  rem our triangle data pasted to the new memblock
   write memblock dword 2,i + 12,a    rem this will create a vertex index number
   write memblock dword 2,i + 16,a    rem this will be our indexdata index
   write memblock dword 2,i + 20,0    rem this is our duplicate flag
   write memblock float 2,i + 24,1    rem u mapping data  just going to put 1 here for now
   write memblock float 2,i + 28,1    rem v mapping data  just going to put 1 here for now
   inc a,1
next i
rem a_time# = timer()
rem loop through the new memblock, look for duplicates and flag them
rem what this will do is flag all duplicate vertices with a 1, uniques will be left at 0
For i = 12 to (m_size - 32) step 32
   x1# = memblock float(2,i) : y1# = memblock float(2,i + 4) : z1# = memblock float(2,i + 8)
rem search until a duplicate is found, then exit search
   for j = (i + 32) to (m_size - 32) step 32
      if memblock dword(2,i + 20) = 0
      x2# = memblock float(2,j) : y2# = memblock float(2,j + 4) : z2# = memblock float(2,j + 8)
         If (x1# = x2#) and (y1# = y2#) and (z1# = z2#)
            write memblock dword 2,i + 20,1
         endif
      endif
   next j
next i
rem b_time# = timer()
rem assign new vertexdata index to the unique vertices

a = 0
For i = 12 to (m_size - 32) step 32
   if memblock dword(2,i + 20) = 0
      write memblock dword 2,i + 12,a
      inc a,1
   endif
next i


rem compare the unique vertices to the duplicate vertices, and write the indexdata value of the duplicate
rem to point at the matching unique vertice


For i = 12 to (m_size - 32) step 32
   if memblock dword(2,i + 20) = 0
      x1# = memblock float(2,i) : y1# = memblock float(2,i + 4) : z1# = memblock float(2,i + 8)
      inc numVerts,1
      for j = 12 to (m_size - 32) step 32
         x2# = memblock float(2,j) : y2# = memblock float(2,j + 4) : z2# = memblock float(2,j + 8)
         If (x1# = x2#) and (y1# = y2#) and (z1# = z2#)
            write memblock dword 2,j + 16,memblock dword(2,i + 12)
         endif
      next j
   endif
next i

remstart
rem this is just a block of code to write a data file of what is in the memblock
rem not needed unless you want to see it.

if file exist("memblocktest.txt") = 0
   open to write 1,"memblocktest.txt"
else
   delete file "memblocktest.txt"
   open to write 1,"memblocktest.txt"
endif
For i = 12 to (m2_size - 32) step 32
   write string 1,str$(memblock float(2,i)) + "," + str$(memblock float(2,i + 4)) + "," + str$(memblock float(2,i + 8)) rem x,y,z pos
   write string 1,"vertex index: " + str$(memblock dword(2,i + 12))
   write string 1,"indexdata index: " + str$(memblock dword(2,i + 16))
   write string 1,"duplicate: " + str$(memblock dword(2,i + 20))
   write string 1,"--------------"
next i
close file 1
remend

rem for some reason, you can't delete a mesh from a mesh made from a memblock. Possible bug?
rem No longer necessary to use delete mesh from vertexdata(). It really has no effect on the mesh
rem All you really need to do is reorder the index data to weld.
make mesh from memblock 1,1
save mesh "memblock.x",1
lock vertexdata for mesh 1

rem write the vertices to the vertexdata
a = 0
For i = 12 to (m_size - 32) step 32
   if memblock dword(2,i + 20) = 0
      x1# = memblock float(2,i) : y1# = memblock float(2,i + 4) : z1# = memblock float(2,i + 8)
         set vertexdata position a,x1#,y1#,z1#
         inc a,1
   endif
next i

rem and finally, write the indexdata
a = 0
For i = 12 to (m_size - 32) step 32
      index_value = memblock dword(2,i + 16)
         set indexdata (a),index_value
         inc a,1
next i

unlock vertexdata
make object id,1,0
save mesh "mb_afterweld_obj"+str$(id)+".x",1
delete mesh 1
delete memblock 1
delete memblock 2

rem set uv coordinates to stretch across object
rem should probably break this down into its own function for different kinds of objects, like mode 0 for my grid, 1 for DBPro cubes, 2 for DBPro box, etc
rem right now, this just a planar type mapping
If texture_mode = 1
   u# =  object size x(id)
   v# =  object size z(id)
   make mesh from object 1,id
   delete object id
   lock vertexdata for mesh 1
rem loop throught the texture coordinates and determine what percent of total width, height the vertex is at
   a = get vertexdata index count()

   for i = 0 to a
      set vertexdata uv i, get vertexdata position x(i) / u#, get vertexdata position z(i) / v#
   next i

   unlock vertexdata
   make object id,1,0
   save mesh "afterweld_obj"+str$(id)+".x",1
   delete mesh 1
endif


rem tw_time# = (b_time# - a_time#) * .001

endfunction

It looks alot scarier than it is. There is alot of comment code in there. What does it do? Pass in the number of the object you want welded, and it will weld it. What is welded? Welded vertices just share the same index to a vertice in the vertxdata buffer.
If that sounds crazy, then how about this.
It means you can take a cube and twist it all around, or a sphere and make asteroids, or whatever. I have a full set ofother functions that demonstrate this. The goal was to do this without globals or types. And I'm having a blast. Right now, on my machine, it still takes about 80 seconds to weld 20,000 polys, which is still WAY TO SLOW. I know where the hold up is, thanks to Lee's Tips in the newsletters about using timers to check code block speed. But still, this is a significant improvement, and I know I'll get it even faster.