Sorry your browser is not supported!

You are using an outdated browser that does not support modern web technologies, in order to use this site please update to a new browser.

Browsers supported include Chrome, FireFox, Safari, Opera, Internet Explorer 10+ or Microsoft Edge.

DarkBASIC Professional Discussion / 'vertexdata' How to add vertices?

Author
Message
WLGfx
18
Years of Service
User Offline
Joined: 1st Nov 2007
Location: NW United Kingdom
Posted: 20th Jun 2011 17:11
I've got this far with understanding the vertex data commands, I've also been given some pointers on how to create objects manually. I'm slowly getting there.



All I need to know now is how to create vertices and create faces if anyone has any pointers?

Warning! May contain Nuts!
IanM
Retired Moderator
23
Years of Service
User Offline
Joined: 11th Sep 2002
Location: In my moon base
Posted: 20th Jun 2011 19:22
First, don't use memblocks

There! Got that out of the way.

There are commands provided by my plug-ins that allow you to create objects to spec from scratch.

The first command is MAKE OBJECT NEW which will allow you to create a single-limb object with the number of vertices and indices that you specify.

Here's a simple multi-coloured cube built from vertex data:0


The second command is actually a whole set of commands - BEGIN NEW OBJECT / ADD NEW LIMB / FINISH NEW OBJECT - that you can use to build multi-limbed objects, linked how you wish.

Here's an example:


If you have an existing object, then my plug-ins can't help directly (I'll look into it!).
The way to do it though is to create a new object with the number of vertices and indices that you want to add, then make a mesh of it, then use the ADD MESH TO VERTEXDATA command to add it to a locked limb.

WLGfx
18
Years of Service
User Offline
Joined: 1st Nov 2007
Location: NW United Kingdom
Posted: 20th Jun 2011 21:23 Edited at: 20th Jun 2011 21:25
Ah fantastic, I just came across the extra commands in your plugins before I came back here to check but you've explained everything. I'll get this working in DBPro then I'll have something to start with in GDK.

Am I right in assuming that you can re-use a vertex more than once. ie a corner of a cube can be used three times (or 6?).

Edit: LOL at not using memblocks. Maybe in GDK I'll use something similar but I'm getting to grips with it all first.

Warning! May contain Nuts!
IanM
Retired Moderator
23
Years of Service
User Offline
Joined: 11th Sep 2002
Location: In my moon base
Posted: 20th Jun 2011 21:26
Yes, but only if you use an index buffer too.

You'll see in the cube example, I'm using 4 vertices for each side of the cube, 1 for each corner, but specifying 6 indices for each side, specifying the 3 points for each of the 2 polys.

WLGfx
18
Years of Service
User Offline
Joined: 1st Nov 2007
Location: NW United Kingdom
Posted: 20th Jun 2011 21:36
Similar to welding vertices in a 3d modelling program. Is it possible to shrink and expand the vertices list and the indices list? Sorry to keep asking. I'm almost there until I find my next bug...

Warning! May contain Nuts!
IanM
Retired Moderator
23
Years of Service
User Offline
Joined: 11th Sep 2002
Location: In my moon base
Posted: 20th Jun 2011 21:42
Yes, via the DELETE MESH FROM VERTEXDATA command.

Alternatively, you can specify the number of polys to be rendered using the SET LIMB DRAW PRIMITIVES command, rather than continually resize the vertex/index buffers.

WLGfx
18
Years of Service
User Offline
Joined: 1st Nov 2007
Location: NW United Kingdom
Posted: 3rd Jul 2011 01:55 Edited at: 3rd Jul 2011 01:56
I thought I'd come back to this thread to ask about the normals. In the code:

I understand the normals here, front and back face vertices use the z axis normals as -1 and 1. The problem I'm facing is I'm sharing vertices on the corners.

Do I need to angle my normals pointing away from all faces. (hopefully the image might explain a bit better) I know where each vertex is going and the faces will all be square and aligned straight to the map being built.



Warning! May contain Nuts!
Brendy boy
20
Years of Service
User Offline
Joined: 17th Jul 2005
Location: Croatia
Posted: 3rd Jul 2011 02:07
Quote: "Do I need to angle my normals pointing away from all faces."

it depends weather you want smooth shading on your object or not.
If not you only need to calculate face normals and then set that normal to every vertex of that face.

If you want smooth shading then after you calculate face normals do this for every vertex: - find all faces that share that vertex and add ther normals together and the vector you get divide with the number of faces that share that vertex, that way you'll get the averageg normal vector

WLGfx
18
Years of Service
User Offline
Joined: 1st Nov 2007
Location: NW United Kingdom
Posted: 3rd Jul 2011 02:22
Yeah, I was googling that and found some answers. For the purpose of what I'm working on I probably don't need smooth shading but for the exercise I want to at least understand it better for future reference.

If all my faces are flat against either the XY or Z axis then I should just be able to put in straight forward values for the normals without any calculations. I'm hoping this is the case because I'm a bit away from getting my code to show anything visually yet in 3D apart from a trace file output showing values.

Thanks for the info. Helps confirm things...

Warning! May contain Nuts!
Green Gandalf
VIP Member
21
Years of Service
User Offline
Joined: 3rd Jan 2005
Playing: Malevolence:Sword of Ahkranox, Skyrim, Civ6.
Posted: 3rd Jul 2011 14:01
Quote: "The problem I'm facing is I'm sharing vertices on the corners."


How are you overcoming that problem? If you want three normals for the three faces of a cube that meet on a corner then you probably need three separate but identical vertices, i.e. they can't be shared ("welded"). [Although I have a feeling there may be a way around this. Perhaps someone else can cast light on this? Using a simple welded cube with 8 vertices for example?]
IanM
Retired Moderator
23
Years of Service
User Offline
Joined: 11th Sep 2002
Location: In my moon base
Posted: 3rd Jul 2011 14:22
The point is that you only share a vertex when all data related to that vertex is identical, including the normals. If you don't want smooth shading, then you have to have separate vertices... at least to a point.

For example, each side of a cube can use share vertices, but they can't share those vertices with other sides because they will have different normals.

Vertices = Side (4x2) times 6 sides = 24 vertices
Indices = Side (3x2) times 6 sides = 36 indices

WLGfx
18
Years of Service
User Offline
Joined: 1st Nov 2007
Location: NW United Kingdom
Posted: 3rd Jul 2011 15:25 Edited at: 3rd Jul 2011 15:44
Yep, I'm sharing the vertices on each corner. So for a cube I'm using 8 vertices. I've some notes:


So far I will be experimenting with the smoothing and shared vertices, I might even get a false lighting effect, but if not I'll switch the smoothing off.

I was also looking into sharing a complete vertex list between objects. I haven't started on this part of my code yet to try it but was wondering if that was possible. The quicker I can get the generation of levels within my code is my goal. A lot of people do say don't worry about the number, size, etc. For me it is just an exercise which I hope to write some sort of tutorial on working with these commands.

I do have a slow laptop which in a way helps me optimise some things. Once I've got something working then I'll be re-writing all the code again, whether it be calculating everything in a single loop or separating each calculation stage.

EDIT: A reference from sourceforge says that vertex buffers can be shared between lists, I'm assuming this means index lists for objects. If the object is not being modified then it will stay in the GPU's memory making for faster FPS updates. (Although this was a reference to OpenGL and not Direct X)

Warning! May contain Nuts!
IanM
Retired Moderator
23
Years of Service
User Offline
Joined: 11th Sep 2002
Location: In my moon base
Posted: 3rd Jul 2011 19:55
Quote: "I was also looking into sharing a complete vertex list between objects."

The nearest you can get with DBPro is with instancing, which uses the same vertex buffer and index buffer for each instance of the object (or actually, for each limb).

WLGfx
18
Years of Service
User Offline
Joined: 1st Nov 2007
Location: NW United Kingdom
Posted: 5th Jul 2011 19:14 Edited at: 5th Jul 2011 19:20
I've come to a stumbling block with the MAKE OBJECT NEW() command. I'm getting the error "Indices must be less than or equal to 65535" although I only have about 19,000 indices. I've also casted the variable from the UDT array into an integer just in case.

The project is attached but this is part of the function where it crashes out with the error:


It gives me these results for group 0 - Faces 185091 Vertices 19182

I'm also unsure about the FVF values. I'm after setting up my object with coords, a texture, I'll play with specular, don't need a diffuse value, and vertex normals so I can play with fake lighting.

I am just hoping it's something daft that I'm missing.

Thanks...

EDIT: It's been a while because I had some house work to do for a change that took days... :-(

EDIT 2: Ooops the error is about Indices not vertices... Darn it... Can't go over 65535...

Any way around this?

Warning! May contain Nuts!
Green Gandalf
VIP Member
21
Years of Service
User Offline
Joined: 3rd Jan 2005
Playing: Malevolence:Sword of Ahkranox, Skyrim, Civ6.
Posted: 5th Jul 2011 20:16 Edited at: 5th Jul 2011 20:21
Quote: "Any way around this?"


Split it into smaller limbs.

Quote: "fvf = FVF_XYZ || FVF_NORMAL || FVF_SPECULAR || FVF_TEX0 || FVF_DIFFUSE"


What values did you specify for those constants?
WLGfx
18
Years of Service
User Offline
Joined: 1st Nov 2007
Location: NW United Kingdom
Posted: 5th Jul 2011 20:23
The figures keep getting bigger and I thought I could get away with a few things until I came across this limit. For now I'll go back to my original plan of separating the floors, walls and ceilings into their own limbs and see what figures I get. I was hoping for large maps well over 256 x 256, but even a 96 x 96 causes a big index count.

Warning! May contain Nuts!
Green Gandalf
VIP Member
21
Years of Service
User Offline
Joined: 3rd Jan 2005
Playing: Malevolence:Sword of Ahkranox, Skyrim, Civ6.
Posted: 5th Jul 2011 20:40
Quote: "I was hoping for large maps well over 256 x 256"


What units? A 256x256 array of vertices?

Incidentally, did you intend to use FVF_TEX0 as one of your constants? That means no UV data.
WLGfx
18
Years of Service
User Offline
Joined: 1st Nov 2007
Location: NW United Kingdom
Posted: 5th Jul 2011 20:50
It would convert a 2d map array into a 3d map. So each 2d map square, only if used would use up to 8 vertices, for the floor, walls and ceiling. But it would share vertices to cut down the count. I didn't realise that even though I was cutting down the vertex count the index count wasn't being affected. I can't share indices.

Erm, FVF_TEX0-8, that would have been a thing I would have googled then probably came here to ask about.

Now having to cut the index count I'm having to drop my experiment with normals and lighting.

Although, as an afterthought, I could always check whether vertices are spread across a straight wall, delete them, fill in the gap with one face and re-calculate the UV mapping. (Awww no, more maffs)

Warning! May contain Nuts!
Green Gandalf
VIP Member
21
Years of Service
User Offline
Joined: 3rd Jan 2005
Playing: Malevolence:Sword of Ahkranox, Skyrim, Civ6.
Posted: 5th Jul 2011 22:03
Quote: "fill in the gap with one face and re-calculate the UV mapping"


In which case you need at least one set of UV coordinates, i.e. one of FVF_TEX1-8.

Quote: "Awww no, more maffs"


That's the best bit.
IanM
Retired Moderator
23
Years of Service
User Offline
Joined: 11th Sep 2002
Location: In my moon base
Posted: 6th Jul 2011 01:03
Quote: "Indices must be less than or equal to 65535"

Sorry, DBPro limit.

As GG said though, you can split your object up into separate limbs - it's a pain, but not too hard to do, depending on the object you are creating (and dead easy if you are creating traditional terrain).

WLGfx
18
Years of Service
User Offline
Joined: 1st Nov 2007
Location: NW United Kingdom
Posted: 6th Jul 2011 03:53 Edited at: 6th Jul 2011 23:35
I've been optimising one thing to keep the numbers down without thinking about the other. I'm thinking of creating the mesh (out of the bounds of the DBP restrictions) then optimising the faces. A bit like a 3D modelling program does. They are only square floors, walls and ceilings so it shouldn't be too hard to do.

ie: if the floor area takes up a 12 x 12 grid, that would be 169 (13x13 vertices) vertices, but can be optimised and re-mapped for UV coords down to just 4 vertices and only taking up 6 indices.

I'll need to make some more notes before I give up and do each portion separate... It may take me another load of days but I'll get back here and let you know how I get on.

Thanks Green Gandalf and IanM...

Warning! May contain Nuts!
WLGfx
18
Years of Service
User Offline
Joined: 1st Nov 2007
Location: NW United Kingdom
Posted: 6th Jul 2011 23:38
So far I have the beginnings of an idea:

Just got to try and put this bit into code, then try and see if I can work something out for not just the floor but for walls and the ceiling as well because ideally I want to play around with the vertex normals.

If in the meantime anybody can point me in a direction of mesh optimisation algorithms I would be grateful.

Warning! May contain Nuts!
Green Gandalf
VIP Member
21
Years of Service
User Offline
Joined: 3rd Jan 2005
Playing: Malevolence:Sword of Ahkranox, Skyrim, Civ6.
Posted: 6th Jul 2011 23:58
You could try a bit of Googling. Google came up with a blitzbasic forum which contained this in a post (!!):

mesh reduction software

I see it has a trial download. Might be worth a look.

Do you ever get the feeling you are going round in circles? I just did.
WLGfx
18
Years of Service
User Offline
Joined: 1st Nov 2007
Location: NW United Kingdom
Posted: 7th Jul 2011 00:34
I have done a fair bit of googling and downloaded a few pdf files explaining various methods of mesh reduction optimisations. Mine is going to be quite simple as it is all square edges.

A lot of what I've found so far I really don't understand because they explain it in all that weird looking maffs language with squiggly this and strange letters that. I didn't get that far in college. It's a bit like looking at the pictures first then reading the text afterwards.

Portions of this helped - http://liris.cnrs.fr/guillaume.lavoue/travaux/revue/VC2011.pdf

http://www.i3dpost.eu/dyn/1294679901357/3DPVT-TTakai.pdf - Has some nice pictures to it and some things I'll look into for the future.

Last night I found a few more but where I saved them I can't find at the moment.

Green Gandalf, I really hope my journey around this big circle helps. I know what I want but getting there is one hell of a learning curve. Things weren't so hard in the 8-bit days...

Warning! May contain Nuts!
Green Gandalf
VIP Member
21
Years of Service
User Offline
Joined: 3rd Jan 2005
Playing: Malevolence:Sword of Ahkranox, Skyrim, Civ6.
Posted: 7th Jul 2011 01:47 Edited at: 7th Jul 2011 12:57
The download button on the link I gave you seems to be broken.

[Edit Mike has fixed the link now. Thanks Mike. ]

Here's another link which works:

http://www.action3d.net/

I've just tested the trial download from that page and it seems to work OK.

I realise you want to do it yourself ideally. If I see an understandable technical description I'll post it. I'll check out your links tomorrow.
WLGfx
18
Years of Service
User Offline
Joined: 1st Nov 2007
Location: NW United Kingdom
Posted: 7th Jul 2011 02:55 Edited at: 7th Jul 2011 03:13
I like action3d, I tried it on a few high poly meshes. It's the same kind of thing 3ds max does with its optimise mesh option.

The algorithm I'm working on just cleans up straight faces.

The main idea behind what I want to do is to create the function:

MAKE_GAME_LEVEL_WITH_BADDIES_AND_PICKUPS_AND_OTHER_STUFF(random_number as integer)

The early 8-bit computers had Elite, a galaxy, with star systems and using the games time line, the stock market.

My favourite and were I am getting my inspiration from is Anthony Crowthers - Captive, using the same technique. Give a single random number, generate a complete level, baddies, pickups, shops, etc and the game is a goodun'. Especially the Map Generator.

Far from being at that point at the moment because of my maffs, I've a clear idea of what I'm after. As Green Gandalf said, circles, I could growl at circles everyday, but I'm patient/stubborn.

Warning! May contain Nuts!
Green Gandalf
VIP Member
21
Years of Service
User Offline
Joined: 3rd Jan 2005
Playing: Malevolence:Sword of Ahkranox, Skyrim, Civ6.
Posted: 7th Jul 2011 12:54
The circle I was referring to was this:

browsing TGC thread > Google search > blitzbasic site > link to product on TGC site



Just had a quick look at the paper by Lee and co. Yes, something like that seems to be what you're after - but it should be much simpler in your case with just rectangles. It's still likely to be messy and hard work though. I doubt it's worth over-optimising - just avoid making segments that are unnecessarily high poly. Or perhaps just have a strategy for identifying segments that can be reduced easily? I guess part of the problem is to maintain welded edges and vertices.

I suspect the difficulty is more about logic than maths as such.

Interesting project. I hope you keep us informed how you get on.
WLGfx
18
Years of Service
User Offline
Joined: 1st Nov 2007
Location: NW United Kingdom
Posted: 7th Jul 2011 19:33
I've emailed mootools.com about their Polygon Cruncher SDK - Depending on their response I may have to work on a dll to integrate it with Dark Basic Pro so I can carry on with this project.

If not then back to doing more maffs...

Warning! May contain Nuts!
Green Gandalf
VIP Member
21
Years of Service
User Offline
Joined: 3rd Jan 2005
Playing: Malevolence:Sword of Ahkranox, Skyrim, Civ6.
Posted: 7th Jul 2011 21:29
Here's another link.

Polygon reduction

That looked like a very simple explanation of one possible approach. I might even try it myself when I have nothing better to do ...
WLGfx
18
Years of Service
User Offline
Joined: 1st Nov 2007
Location: NW United Kingdom
Posted: 7th Jul 2011 21:53
I'm going to spend this evening pouring over that document. Thanks Green Gandalf, that piece looks ideal so far.

Converting the code to DBP shouldn't be much of a problem. I'll see where I get with it too.

Warning! May contain Nuts!
Green Gandalf
VIP Member
21
Years of Service
User Offline
Joined: 3rd Jan 2005
Playing: Malevolence:Sword of Ahkranox, Skyrim, Civ6.
Posted: 7th Jul 2011 22:12
Yes, the basic idea seems very simple.

I might see if it helps with one of my terrain buiding projects. My terrains are built using a grid of NxN limbs (a bit like Advanced Terrain). That can be very wasteful of vertices in certain parts of the terrain and that article has suggested a stratgey for simplifying the limbs. Should be easy to implement in such cases. It'll be interesting to see what performance gains result.
WLGfx
18
Years of Service
User Offline
Joined: 1st Nov 2007
Location: NW United Kingdom
Posted: 7th Jul 2011 23:27 Edited at: 8th Jul 2011 00:44
I'm thinking along the same lines as you with the level generator, the less vertices and indices then other elements can be added without the worry of mesh size. I can simply set that code to optimise anything below a 90 degree angle.

It looks like in your case you would have to copy the mesh data, perform the optimisation then rebuild a mesh from the result. Where as in mine I build my mesh, optimise it then build the object. I think it's time for me to get my brain cell around this.

EDIT: I've also come across this, http://www.gdmag.com/code.htm I'm just having a browse through some of the mesh reduction code.

Warning! May contain Nuts!
Green Gandalf
VIP Member
21
Years of Service
User Offline
Joined: 3rd Jan 2005
Playing: Malevolence:Sword of Ahkranox, Skyrim, Civ6.
Posted: 8th Jul 2011 01:37
The main problems with mesh reduction arise in the housekeeping details.

Quote: "It looks like in your case you would have to copy the mesh data, perform the optimisation then rebuild a mesh from the result."


I would work on one limb at a time, reducing a limb's vertex data before building the limb itself. I've had a brief look at my existing code and it is feasible but I think I would probably have to limit the reduction algorithm to avoid spending too much time on the housekeeping details. I haven't studied other people's code yet so perhaps there's a crafty way of organising the calculations to stop it getting messy.
WLGfx
18
Years of Service
User Offline
Joined: 1st Nov 2007
Location: NW United Kingdom
Posted: 8th Jul 2011 02:55
I've come across the algorithm I'm going to use for my mesh. http://www.flipcode.com/archives/Efficient_Polygon_Triangulation.shtml

It a polygon triangulation algorithm. If I trace the edge of my 2d floor map I can place all the corner vertices into a 2d array and get this code to fill it with triangles. The same coords can be used for the ceiling. And also the same set of coords can be used to define the walls.

It took some thinking and a lot of googling tonight but I've sussed out what I need.

There's lots of source code out there already that reduces a meshes polygons but they all seem quite fiddly to implement. I've logged a few on a blog post for future reference.

I'm glad that I don't actually now need that.

@Green Gandalf - A lot of the resource libs available (after long searching) do all the house-keeping themselves. GLOD was a simple enough one, (1) init GLOD, (2) set up your arrays for GLOD, (3) call the reduction function, (4) retrieve data back into your own format.

Warning! May contain Nuts!
Green Gandalf
VIP Member
21
Years of Service
User Offline
Joined: 3rd Jan 2005
Playing: Malevolence:Sword of Ahkranox, Skyrim, Civ6.
Posted: 8th Jul 2011 13:53
Quote: "If I trace the edge of my 2d floor map I can place all the corner vertices into a 2d array and get this code to fill it with triangles."


Sounds like the best option for your situation - and possibly mine as well.

Quote: "There's lots of source code out there already that reduces a meshes polygons but they all seem quite fiddly to implement."


I was coming round to that view too. Perhaps the solution to my terrain problem is to use a variation of the triangulation idea as follows:

1. Decide which vertices are needed to maintain sufficient detail.
2. Triangulate those vertices. (I would probably keep the original edge vertices on each limb to avoid problems across joins between limbs.)

Not sure how feasible that is yet but at first sight it seems a better strategy than fiddling about trying to remove edges/vertices/triangles. Food for thought.

Quote: "I'm glad that I don't actually now need that."


Indeed.

Quote: "A lot of the resource libs available (after long searching) do all the house-keeping themselves."


I was hoping that would be the case. I haven't got as far as delving into the details yet. Sounds like I don't need to now though. I'll look at that link asap. Thanks.

These sorts of discussions can be very useful.
Green Gandalf
VIP Member
21
Years of Service
User Offline
Joined: 3rd Jan 2005
Playing: Malevolence:Sword of Ahkranox, Skyrim, Civ6.
Posted: 8th Jul 2011 14:41 Edited at: 8th Jul 2011 18:37
[Edit Oops!! Just realised I pasted the wrong snippet - must have selected and forgotten to copy! Hopefully I've got it right now.]

Sorry for double post but I've just realised that we've already done the "triangulate polygon" thing before.

Here's the latest version of some code that several of us worked on some time back:



Just click in the black area for the outline of your polygon (doesn't need to be convex) then click the small square to triangulate it. Not sure if this is exactly what you want but it should be possible to adapt the code.

Now to see if I can adapt it for the terrain thing.

Now I really do feel I'm going round in circles.

Edit2 Looks like I need this (e.g. see comments under Applications):

Delaunay Triangulation

Now all I need is an efficient way of choosing vertices to use - and how many.
WLGfx
18
Years of Service
User Offline
Joined: 1st Nov 2007
Location: NW United Kingdom
Posted: 9th Jul 2011 18:14
Sometimes it's good to have a pause and a good think about how to do something.

Just before I was about to adapt some code to DBP I realised that my polygons are going to have holes in them. I'm going to have fun tracing the outline then figuring out how to work out the holes. I've got some C++ code that triangulates polygons with holes but getting there first is a slight problem.

I don't think this one is a circle that I'm going round this time. It's seems more like a ladder that I'm taking a few steps down on. I'm hoping I can find something that I can adapt to figure that bit out.

I'm hoping that maybe I can adapt something inside my flood fill code to trace the outline and holes.

@Green Gandalf - Is the method you're thinking of similar to tessellation or subdividing a large polygon?

I like that piece of code you posted, very easy to understand and it looks like a good place to start.

Warning! May contain Nuts!
Green Gandalf
VIP Member
21
Years of Service
User Offline
Joined: 3rd Jan 2005
Playing: Malevolence:Sword of Ahkranox, Skyrim, Civ6.
Posted: 10th Jul 2011 00:32 Edited at: 10th Jul 2011 00:33
Quote: "Is the method you're thinking of similar to tessellation or subdividing a large polygon?"


I don't think so. I was thinking of starting with a rectangular grid of vertices then keeping the edge vertices but deleting as many interior vertices as possible without losing useful information about the terrain's shape. As a final step I would actually triangulate the vertices as illustrated below. No doubt better triangulations might be possible, taking into account the terrain height info ideally.



One problem with that is that to get good results you probably need a new triangulation each time a vertex is considered for deletion (so you can get a suitable error estimate) but I guess simplified versions are possible. There are quite a few useful looking articles available on the web but they all look a bit heavy handed for what I need - and as you said earlier they can be quite complex.

Quote: "I've got some C++ code that triangulates polygons with holes but getting there first is a slight problem."


Do you mean the code doesn't work or that C++ is the problem? Sounds like it's what you need.
WLGfx
18
Years of Service
User Offline
Joined: 1st Nov 2007
Location: NW United Kingdom
Posted: 12th Jul 2011 03:36
Had a long break over the weekend and done nothing with programming. ...

@Green Gandalf - My map generator creates holes, so I'm actually thinking about adding to the flood fill algorithm which groups the areas, to also trace the outline of the polygons. I'm hoping that I can also trace outlines to the holes in the map areas too. Once that is done then that part is over.

The C++ code which triangulates a polygon with holes should (hopefully) be converted to DBP. I've had a good study of it and I'm getting a better understanding of it.

On your terrain, how many vertices/faces are you looking at without optimisation on the whole? That was another thing I was thinking about over the weekend was terrain generation. Raising blocks on the grid then delete vertices that are within flat areas.

I also want to look into multi-texturing objects on manual creation which will be 'oh so' useful...

Warning! May contain Nuts!
Green Gandalf
VIP Member
21
Years of Service
User Offline
Joined: 3rd Jan 2005
Playing: Malevolence:Sword of Ahkranox, Skyrim, Civ6.
Posted: 12th Jul 2011 13:00 Edited at: 12th Jul 2011 14:32
Quote: "The C++ code which triangulates a polygon with holes should (hopefully) be converted to DBP."


I hope you post that.

Quote: "On your terrain, how many vertices/faces are you looking at without optimisation on the whole?"


It's under my control. I create a terrain using an NxN grid of limbs consisting of MxM welded plains. I would consider optimising it whenever the vertex count seemed to be causing problems - unless the optimising works well in which case I could include it by default.

I realised after my previous post that the vertex reduction could be simpler than I feared. I might proceed as follows.

I could start with the edge vertices (without triangulation) then look for the best single interior vertex to include. This could be a simple loop through all of them since at that stage triangulation is simple - just join all the border vertices to the interior vertex. Then calculate some sort of error criterion. Do this for each vertex and pick the one which gives smallest error. At that stage we have an initial triangulation of the limb with just one interior vertx included. This initial step could be quite time consuming.

Adding later vertices should be somewhat faster. I would again loop through the remaining vertices but now when one is added it need affect only one of the existing triangles which is then triangulated in the obvious way. The error criterion can be updated using just the vertices that fall within the new triangles. This is then done for each candidate vertex and the best one chosen. This procedure can be repeated till a specified number of vertices are included or a given error tolerance has been achieved. Such a procedure should be straightforward to implement. It could be enhanced by looking for the best triangulation of the whole limb each time a new vertex is considered. That would slow things up enormously though - especially the programming .

Edit Here's a sample screenshot using typical values. The total number of vertices is (no of limbs)x(no of vertices per limb), i.e. 961x1024 = 984064 (Edit corrected ). The number of distinct vertices is rather less because of repetition along the seams between adjacent limbs.

WLGfx
18
Years of Service
User Offline
Joined: 1st Nov 2007
Location: NW United Kingdom
Posted: 12th Jul 2011 18:41
That actually looks very sweet. I doubt on this machine I'm on at the moment I'd get any decent frame rates though. If you've got it to that stage already then wouldn't a mesh optimise be a good option or are you still working on the creation of the mesh?

I've spent a lot of the time today researching 'raster to vector' conversion techniques and I've come across two I could use.

It would mean doing a command line like call to do the conversion but if it's quick enough under testing conditions then I'd go down that route.

I would need to create my portion of the level/dungeon/caves on a 2d floor map. Save the bitmap to a temporary file. Call the program to convert it to a poly file. Read the file in and create my mesh from it. I'm hoping that if it works then it would run in under 5 seconds to complete everything.

My old version of creating a dungeon took about 1.7 seconds from start to finish.

The links to the raster to vector software are - Potrace and AutoTrace

Failing that route, both these programs provide the source code to the public which I could maybe convert.

Here's hoping to the 5 second limit...

Warning! May contain Nuts!
Green Gandalf
VIP Member
21
Years of Service
User Offline
Joined: 3rd Jan 2005
Playing: Malevolence:Sword of Ahkranox, Skyrim, Civ6.
Posted: 12th Jul 2011 19:47 Edited at: 12th Jul 2011 20:10
Quote: "If you've got it to that stage already then wouldn't a mesh optimise be a good option or are you still working on the creation of the mesh?"


Yes, as far as the mesh is concerned optimisation would be the next step. Another thing to think about is limb culling which might improve matters.

Somewhat bizarrely, uncapped that demo runs at about 50-54 fps with the shader applied but only 50-51 without. The shader uses triplanar mapping to do the texturing plus a few other things so I'm quite surprised that it's faster. However, 50-54 is too slow as a starting point for a game so some optimisation is probably needed.

I've just done some quick tests and found that reducing the vertex count has negligible effect - I reduced each limb from 32x32 vertices to 12x12, i.e. roughly 90% reduction and noticed no real change in fps. On the other hand hiding (or excluding) limbs had a much bigger effect - increasing the fps from about 50 to about 80. So it looks like efficient limb culling is the way to go rather than worry about complicated mesh optimisation. Perhaps limb culling plus many limbs is the best option. I'll do another quick test now and report back.

Edit

Ouch. Keeping the total vertex count the same but increasing the number of limbs from 961 to 15376 (somewhat drastic I know ) dropped the fps from about 50 to 3.

So I guess it's a case of looking for a happy medium somewhere. Use enough limbs for limb culling to be effective but not so many that rendering is slowed down.

Time to have another look at Lost In Thought's limb culling code perhaps?
Green Gandalf
VIP Member
21
Years of Service
User Offline
Joined: 3rd Jan 2005
Playing: Malevolence:Sword of Ahkranox, Skyrim, Civ6.
Posted: 12th Jul 2011 20:57
OK. This is probably worth a new post.

I tried LIT's limb culling code some time back but got strange results so I shelved it. I've now just added it to my limbed terrain demo and it worked perfectly first time (OK I had to read the instructions twice ). The initial FPS (with the terrain in full view) dropped slightly from about 50 to 47. However, close up the fps jumped from around 54 to 300+, even reaching 500 at certain camera angles. The slight drop is no doubt the slight overhead of the culling system when nothing is actually being culled. (I thought that limb culling was already done by DBPro - something for me to look at more carefully.)

I'd definitely recommend anyone who hasn't tried LIT's culling code to do so.

[I now know what I did wrong before. Amazing what you learn when you read the instructions carefully. ]
WLGfx
18
Years of Service
User Offline
Joined: 1st Nov 2007
Location: NW United Kingdom
Posted: 12th Jul 2011 21:17
I'll have to have a look in to the LIT culling to see what it is if you have a link for it? If it's doing what you say then it's something worth remembering for future use.

I'm still going to work on manually creating models for the time being now that I've got a clear idea of where I'm going with it. Sometimes its worth taking a step back and giving myself time to think.

Quote: "[I now know what I did wrong before. Amazing what you learn when you read the instructions carefully. ]"


I'm not one for even reading instructions. I just run a program and hope I pick it up in 5 minutes.

Warning! May contain Nuts!
Green Gandalf
VIP Member
21
Years of Service
User Offline
Joined: 3rd Jan 2005
Playing: Malevolence:Sword of Ahkranox, Skyrim, Civ6.
Posted: 12th Jul 2011 21:26
Quote: "I'll have to have a look in to the LIT culling to see what it is if you have a link for it?"


Here's the link:

Lost In Thought's limb culling system
WLGfx
18
Years of Service
User Offline
Joined: 1st Nov 2007
Location: NW United Kingdom
Posted: 14th Jul 2011 03:43
Getting somewhere at last...

Once my algorithm for digging the level and finding the largest group it will save a .bmp file for potrace to convert into a .svg file.

The next piece of code will now need to decipher the .svg file to read the paths outputted and then pass them onto a triangulation routine.



So far I am looking into this SVG FILE FORMAT to help with reading the .svg file in. Using the command line "potrace -s -n pic.bmp --output text.txt" within a split second it converts an 800x600 bitmap to a vector file.

Warning! May contain Nuts!
Green Gandalf
VIP Member
21
Years of Service
User Offline
Joined: 3rd Jan 2005
Playing: Malevolence:Sword of Ahkranox, Skyrim, Civ6.
Posted: 14th Jul 2011 12:31
Sounds good. Wish I knew what SVG was.
WLGfx
18
Years of Service
User Offline
Joined: 1st Nov 2007
Location: NW United Kingdom
Posted: 15th Jul 2011 14:09
Slight update.

I can't be bothered using potrace.exe although a good utility, I really do not want to have to parse the SVG file before I can use the details.

'Triangle' by Jonathan Shewchuk is another utility than seems rock solid in its use. I've run a few test on it after having to compile it in VC++ and it's fast. Triangle is found here.

Skipping the potrace.exe step I'm planning on adding inside my flood fill algorithm the outline trace of the floor map including the holes to create a polygon outline. 'Triangle.exe' with then triangulate the mesh. I've been thinking really hard about this and I think I can outline it fine.

Right, back to work. Took me ages but I'm patient.

@Green Gandalf - SVG is a very basic Scalable Vector Graphics file format which is similar to an XML file.

Triangle outputs a file which is so much easier to read in.

Warning! May contain Nuts!
Neuro Fuzzy
19
Years of Service
User Offline
Joined: 11th Jun 2007
Location:
Posted: 15th Jul 2011 22:10 Edited at: 15th Jul 2011 22:13
svg=Scalable Vector Graphics

which is interesting because it allows animated images other than .gifs to be embedded on the web


[edit]
And it's sort-of easy to edit. For example, the code in the above .svg image:



Why does blue text appear every time you are near?
Green Gandalf
VIP Member
21
Years of Service
User Offline
Joined: 3rd Jan 2005
Playing: Malevolence:Sword of Ahkranox, Skyrim, Civ6.
Posted: 15th Jul 2011 22:46
But what do you do with the code? Editing it is one thing, but making it do something is another.

Login to post a reply

Server time is: 2026-07-11 10:26:09
Your offset time is: 2026-07-11 10:26:09