Java-Gaming.org Hi !
Featured games (91)
games approved by the League of Dukes
Games in Showcase (798)
Games in Android Showcase (234)
games submitted by our members
Games in WIP (865)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: 1 ... 174 175 [176] 177 178 ... 214
  ignore  |  Print  
  What I did today  (Read 3463734 times)
Longarmx and 4 Guests are viewing this topic.
Offline theagentd
« Reply #5250 - Posted 2017-02-17 16:40:02 »

Today, I wrote a mesh optimizer in Java to be used on the output of my Blender export plugin.

I'm not too proficient in Python and it's just so goddamn slow at everything, so instead of completely ruining the fast export times I've managed to get so far, I opted for writing a simple optimizer that takes in a model file, optimizes it, then writes it out again. This is done in 3 steps:

1. In the first step, I simply eliminate all duplicated vertices and leave just one of each, then reference the same one with an index buffer. The mesh I output from Blender is mostly unoptimized with lots of duplicated vertices, and this step reduces the vertex count by about 75% percent. This saves a lot of memory on the harddrive and reduces loadtimes a lot, but it actually does not improve performance very much. For example, in one of the submeshes of the giant robots of Robot Farm, the vertex count goes from 38544 --> 9248, a 76% reduction, but the number of vertex shader invocations only drop from 38544 --> 26902, a 30% drop. This leads to the next step...

2. In the next step, the triangles in the mesh is reordered to improve the effectiveness of the hardware vertex cache. As some people might remember, I've done a lot of experiments on the hardware vertex caches of Nvidia, AMD and Intel GPUs, and basically concluded that Nvidia's is f**king weird, AMD's is kinda weird and Intel's is the only sane one. In the end, I concluded that optimizing the meshes for each graphics vendor was too much work, so I simply went with a mainstream algorithm. I ended up implementing Tom Forsyth's simple algorithm, and it works really well. This algorithm simply reorders the triangles in the mesh (by reordering the indices in the index buffer) to increase the chance that vertices are reused as much as possible without specializing it too much to a specific cache size. It's pretty much a general-purpose optimization that should be better than nothing. Anyway, this step further reduced the vertex shader invocation count from 26902 --> 11847, which together with step 1 was a total reduction of 70%! Now, optimally, the number of invocations should be equal to the number of vertices in the mesh, which would mean that there is perfect reuse of vertices and no vertex had to be transformed more than once, but it may not be possible to achieve this. In the end, for this particular mesh the number of invocations is 28% more than optimal, which is acceptable to me.

3. Now, the meshes are optimized for the vertex cache and need a minimal number of vertex shader invocations, but there is one last thing that can be optimized. Inspecting the actual index buffer generated after step 2 reordered the triangles, it's pretty damn random.
Quote
..., 6031, 5989, 5991, 5992, 5993, 5991, 6032, 5992, 5994, 5995, 5996, 5994, 6033, 5995, 8387, 8388, 8389, 8387, 8409, 8388, 8390, 8391, 8392, 8390...
There's a lot of good reuse happening here, but also very huge jumps in which vertex each triangle uses. It essentially reads a completely random vertex from the vertex buffer each execution. This is bad for the GPU, as the vertex data from the VBO is read in with a certain cache line size depending on the GPU. In short, if you reference vertex 1000 and 1001, there's a big chance that the memory read for the data of vertex 1000 will cause the data for vertex 1001 to also be loaded into the cache. Therefore, it is a good idea to try to minimize the "distance" between each subsequent index in the index buffer to increase the chance of the input data of the vertex shader already being in the cache. I did this by simply reordering the vertices in the data to so that they are in the order that the index buffer references them. This does not change the triangle order; it simply changes where the vertices of each triangle lies in memory. Here's an excerpt from the output index buffer:
Quote
..., 2571, 2565, 2571, 2568, 2566, 2567, 2572, 2571, 2566, 2572, 2572, 2567, 2573, 2571, 2574, 2568, 2569, 2568, 2574, 2569, 2575, 2570, 2569, 2574, 2575, 2575, 2576, 2570, 2571, 2572, ...
Much better! This works super well with the optimized triangle order from step 2, as the algorithm tries to place all uses of a given vertex in one place so that it can be reused, so there's a very low risk of a very old vertex being referenced again. To measure the effectiveness of this step, I measured the average "index distance", which is the average
abs(currentIndex - previousIndex)
over the entire index buffer. The average index distance went from 42.82251 --> 5.490958, a very significant improvement to cache coherency!

All in all, here are the final results for the mesh:
Quote
Eliminating duplicate vertices...
Optimizing for post-transform vertex cache...
Optimizing for pre-transform vertex cache...
Vertex count: 38544 --> 9248 (76.00664% reduction)
Invocations: 38544 --> 26902 --> 11847 (69.2637% reduction, 28.103378% more than optimal)
Average index distance: 42.82251 --> 5.490958

Placing 500 of those high-poly robots with no LOD or anything in a test program, my FPS went from 12 to 32 when I switched to the optimized mesh, a ~62.5% reduction in frame time, which matches very well with the ~~70% invocation reduction when you add postprocessing and everything else taking up a bit of time in the first place.

Myomyomyo.
Offline FabulousFellini
« Reply #5251 - Posted 2017-02-17 22:19:41 »

This has nothing to do with java, but it doesn't happen every day.  I found a bag of drugs on the ground on my way to work.  If it was weed I would be very happy, but since it's white, I'm not sure what to do with it.  Maybe I'll go ask a cop what it is lol, but then again, I live in Chicago and would promptly be arrested for possession of a controlled substance.

-FabulousFellini
www.fabulousfellini.com
Offline princec

« JGO Spiffy Duke »


Medals: 1107
Projects: 3
Exp: 20 years


Eh? Who? What? ... Me?


« Reply #5252 - Posted 2017-02-17 23:54:45 »

Chuck it in the bin. Seriously. No good ever comes of white powdered drugs.

Cas Smiley

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline ags1

JGO Kernel


Medals: 367
Projects: 7


Make code not war!


« Reply #5253 - Posted 2017-02-18 01:24:10 »

Chuck it in the bin... with your fingerprints on it?

Offline vfmachado

Junior Devvie


Medals: 9
Exp: 4 years



« Reply #5254 - Posted 2017-02-18 02:32:10 »

Today I put my engine into Astah to see how the things are connected...

I didn't include the terrain package and shaders code but I think that still valid.

Ps: I'm really open to suggestions about the initial architecture (I know that was a mess  Huh Cry )
Ps2: hope to help someone to realize how the game/engine architecture can be initialized.


Offline Archive
« Reply #5255 - Posted 2017-02-18 03:44:21 »

This isn't java or programming related. But i've now learned a pretty good amount of meshuggah songs on the drums!
Here's the list as of today:
-New Millenium Cyanide Christ
-The Exquisite Machinery of Torture
-Sickening
-Future Breed Machine
-Beneath
-Soul Burn
-Inside What's Within Behind
-Marrow
-Humiliative
-Stengah
-Rational Gaze
-Glints Collide
-Spasm

I'm currently working on learning Closed Eye Visuals

Now, for the java related thing:
I've completed the javadocs of the engine!

Offline Coldstream24

JGO Ninja


Medals: 82
Projects: 1
Exp: 4 years


You can fill that void inside with programming, but you'll never return a value.


« Reply #5256 - Posted 2017-02-18 11:21:12 »

I registered my company site and installed MediaWiki Smiley Also made a logo, which I quite like.
http://www.onedropgames.com/


If I wanted to post a WIP about my engine in the coming days, would it be okay?

My website: http://www.onedropgames.com/
My soundcloud: http://www.soundcloud.com/coldstream24
Creator of the Morningside Engine, co-founder of Onedrop Games.
Offline h.pernpeintner

JGO Ninja


Medals: 107



« Reply #5257 - Posted 2017-02-18 11:27:00 »

Placing 500 of those high-poly robots with no LOD or anything in a test program, my FPS went from 12 to 32 when I switched to the optimized mesh, a ~62.5% reduction in frame time, which matches very well with the ~~70% invocation reduction when you add postprocessing and everything else taking up a bit of time in the first place.

You never fail to amaze me, agent. Never thought that index ordering could have such an impact. This topic is now definitely on my (long) list of TODOs. Are games nowadays always optimizing this? And....since you implement so much stuff, why don't you share your repository or your code?  Pointing
Offline theagentd
« Reply #5258 - Posted 2017-02-18 13:44:48 »

You never fail to amaze me, agent. Never thought that index ordering could have such an impact. This topic is now definitely on my (long) list of TODOs. Are games nowadays always optimizing this? And....since you implement so much stuff, why don't you share your repository or your code?  Pointing
Thanks. =P

I'd imagine most games do something to optimize this since the gains can be so huge. In my case, it was really going from the worst possible case to almost optimal reuse, so my gains were a bit exaggerated.

Here's the code for my triangle order optimizer: http://www.java-gaming.org/?action=pastebin&id=1508 My implementation is O(n^2), so not entirely optimal according to the original paper. Still, it's fast enough for my uses. A 12 848 triangle mesh took 260ms to optimize for me, so good enough for an offline tool. There's some low-hanging fruit in there to optimize.

Here's the pre-vertex cache optimizer code. http://www.java-gaming.org/?action=pastebin&id=1509 Very simple, there's probably much better algorithms out there, but I couldn't measure significant gains from running this anyway.

Note: You should always run the triangle order optimizer FIRST, then run the pre-vertex cache optimizer. The triangle order optimizer messes up the vertex order, which the pre-vertex cache optimizer fixes without changing the triangle order.

Myomyomyo.
Offline princec

« JGO Spiffy Duke »


Medals: 1107
Projects: 3
Exp: 20 years


Eh? Who? What? ... Me?


« Reply #5259 - Posted 2017-02-18 15:13:49 »

I seem to recall years and years ago getting perfectly decent performance optimisation just by the simple expedient of sorting triangles in order of their average vertex index number. And that's O(n log n) perf on average. It's not quite as fancy but it gets like 90% of the win for bugger all effort and the best bit is that it can be done in realtime with dynamic meshes. Food for thought. (Why not try it and compare?)

Cas Smiley

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline theagentd
« Reply #5260 - Posted 2017-02-18 15:22:46 »

I seem to recall years and years ago getting perfectly decent performance optimisation just by the simple expedient of sorting triangles in order of their average vertex index number. And that's O(n log n) perf on average. It's not quite as fancy but it gets like 90% of the win for bugger all effort and the best bit is that it can be done in realtime with dynamic meshes. Food for thought. (Why not try it and compare?)

Cas Smiley
Actually, the first thing I did was sort based on the lowest index number. It couldn't compare to Tom's algorithm. Hmm... I'm gonna try something similar though.


EDIT: So I tried something really simple:

1. Sort triangles based on (i0 + i1 + i2).
2. Reorder vertices in the order they are used by the triangles (= the pre-transform cache coherency optimization, step 3 in my previous long post).
3. Repeat until the result gets stable.

The result was actually pretty good, but still not as good as Tom Forsyth's algorithm.

Quote
Simple algorithm after 86 iterations: invocations: 38544 --> 26902 --> 14308 (62.878788% reduction, 54.71454% more than optimal)
Tom Forsyth's algorithm: 38544 --> 26902 --> 11904 (69.115814% reduction, 28.719727% more than optimal)

EDIT 2: According to Forsyth, his algorithm can be implemented in linear time.

EDIT 3: Note that all the invocations counts are reported by the hardware of my Nvidia GPU. The numbers may be very different on AMD and Intel GPUs.

Myomyomyo.
Offline princec

« JGO Spiffy Duke »


Medals: 1107
Projects: 3
Exp: 20 years


Eh? Who? What? ... Me?


« Reply #5261 - Posted 2017-02-18 15:58:37 »

Try the average of the 3 verts as the sort key.

Cas Smiley

Offline theagentd
« Reply #5262 - Posted 2017-02-18 16:05:05 »

Try the average of the 3 verts as the sort key.

Cas Smiley
It's the exact same thing. The average is (i1 + i2 + i3) / 3, so I'm just sorting based on <average>*3.

Myomyomyo.
Offline princec

« JGO Spiffy Duke »


Medals: 1107
Projects: 3
Exp: 20 years


Eh? Who? What? ... Me?


« Reply #5263 - Posted 2017-02-18 16:06:03 »

Hah, so it is of course.

Cas Smiley

Offline FabulousFellini
« Reply #5264 - Posted 2017-02-18 16:35:11 »

Chuck it in the bin. Seriously. No good ever comes of white powdered drugs.

Cas Smiley

Oh I know!  I took it home to show my wife and threw it out.

-FabulousFellini
www.fabulousfellini.com
Offline princec

« JGO Spiffy Duke »


Medals: 1107
Projects: 3
Exp: 20 years


Eh? Who? What? ... Me?


« Reply #5265 - Posted 2017-02-18 17:19:29 »

We used to call cocaine twat powder here. Because it turns ordinary people into twats.

Cas Smiley

Offline FabulousFellini
« Reply #5266 - Posted 2017-02-18 17:23:38 »

We used to call cocaine twat powder here. Because it turns ordinary people into twats.

Cas Smiley

Yeah most people turn into twats.  At the recording studio I used to work at, one of the engineers snorted 60k of the studio's money.  Then the owner found out, and it was not a pretty day that day.

-FabulousFellini
www.fabulousfellini.com
Offline Icecore
« Reply #5267 - Posted 2017-02-18 18:24:09 »

Today, I wrote a mesh optimizer in Java to be used on the output of my Blender export plugin.
Nice job)
I also may recommend try put draw in to DisplayList
– yes I know it deprecated – but you don’t lose anything trying)

Last known State: Reassembled in Cyberspace
End Transmission....
..
.
Journey began Now)
Offline CJC

Senior Devvie


Medals: 16
Exp: 7 years


Just press buttons until it works.


« Reply #5268 - Posted 2017-02-18 19:34:45 »

Howdy all! Cheesy
There. That's my introduction

Well, today (technically I started on it late yesterday, and finished today) I got curious as to how games implemented power systems, and rather than try to read their code, I decided to try and see if I could come up with my own way without other people's code. It now can have "points" (a power source, a power consumer, or an intermediate point) that are connected to each other. I can find the shortest path of connections between two points (shortest distance, and then the least number of connections), as well as find the nearest power source. Cheesy

I feel the need to use this in a game now, but even this (despite being completely code based) made me incredibly happy to have achieved. Cheesy
Offline Coldstream24

JGO Ninja


Medals: 82
Projects: 1
Exp: 4 years


You can fill that void inside with programming, but you'll never return a value.


« Reply #5269 - Posted 2017-02-19 05:53:32 »

I added a nice little shorthand to my console Smiley
Instead of having to type
1  
ent_input <entity name> <parameters>[] 
you can now do this:
1  
<entity name>.input <parameters>

It's not huge but I like the convenience.  It also populates a suggestion list with all the available inputs.

My website: http://www.onedropgames.com/
My soundcloud: http://www.soundcloud.com/coldstream24
Creator of the Morningside Engine, co-founder of Onedrop Games.
Offline Roquen

JGO Kernel


Medals: 518



« Reply #5270 - Posted 2017-02-19 10:58:14 »

RYG did an easy to understand breakdown of out-of-order optimization of some code by PhysX author Pierre Terdiman,
https://gist.github.com/rygorous/fdd41f45b24472649aaeb5b55bbe6e26?ts=4
Offline theagentd
« Reply #5271 - Posted 2017-02-19 15:17:38 »

Nice job)
I also may recommend try put draw in to DisplayList
– yes I know it deprecated – but you don’t lose anything trying)
Good idea, but testing that would require half a rewrite of my model renderer ingame, so I'd have to write an artifical test for it... Also, the amount of optimization the drivers do will vary a lot between vendors, so I'm not sure the information would be that valuable.

RYG did an easy to understand breakdown of out-of-order optimization of some code by PhysX author Pierre Terdiman,
https://gist.github.com/rygorous/fdd41f45b24472649aaeb5b55bbe6e26?ts=4
Hmm. Is there any way could write code that would take advantage of that info in Java? Some pattern that helps Hotspot do the same thing I mean.

Myomyomyo.
Offline Roquen

JGO Kernel


Medals: 518



« Reply #5272 - Posted 2017-02-19 18:49:58 »

My thinking was more "how to think about costs" than the specific example.  BTW, the original (not-complete) sequence is found here: http://www.codercorner.com/
Offline basil_

« JGO Bitwise Duke »


Medals: 418
Exp: 13 years



« Reply #5273 - Posted 2017-02-20 21:19:33 »

i wrote java bindings to portmidi cos' java midi-api is really not good.
Offline CJC

Senior Devvie


Medals: 16
Exp: 7 years


Just press buttons until it works.


« Reply #5274 - Posted 2017-02-21 04:16:38 »

Today I discovered one more reason to do a job right the first time. About 3 years ago I was "commissioned" (is it technically a commission if your "pay" is having membership fees waved?) for a group. Essentially they needed a custom dropbox/google drive system where they could host files and have them synced to authorized users computers. Meaning I needed the server and the client to go along side it. Long story short, the server host can go burn in a hole. Tongue I have no idea what settings they have on that system, but they suck. Nearly all the files were popping up as being "invalidily named" and couldn't be saved on the host (they worked on my test machine). The problem however didn't really manifest until a few days ago, and by then we've had this system running for a long while. So, without destroying the system I had to rewrite the way that files were stored on the server to use a UUID for the file name, and then store the real file name in a database with a reference to the UUID of the file so that I could find it when someone searched for it's name/downloaded the file.

TL;DR-> Do things right the first time, or you may have to do a major rewrite of crucial functions for a system that is under very active use.
Offline Icecore
« Reply #5275 - Posted 2017-02-21 08:09:38 »

files were stored on the server to use a UUID for the file name, and then store the real file name in a database with a reference to the UUID
You don’t need create new file system)
unique UUID is good idea for any file system, but
You can use - base Folder tree structure for users
Simple create new folder per user,
It direct sync with folder on user system
-if user try write duplicate files - behave as normal file system do)

(+ of course caching folders tree structure for faster search ^^)

Last known State: Reassembled in Cyberspace
End Transmission....
..
.
Journey began Now)
Offline CJC

Senior Devvie


Medals: 16
Exp: 7 years


Just press buttons until it works.


« Reply #5276 - Posted 2017-02-21 13:48:55 »

files were stored on the server to use a UUID for the file name, and then store the real file name in a database with a reference to the UUID
You don’t need create new file system)
unique UUID is good idea for any file system, but
You can use - base Folder tree structure for users
Simple create new folder per user,
It direct sync with folder on user system
-if user try write duplicate files - behave as normal file system do)

(+ of course caching folders tree structure for faster search ^^)

As a side note, I don't think it has an affect on the way it ended up being implemented: each user doesn't have their own folder, the group uses the same folder, and no subfolders are allowed to be created. So, I inevitably have to stick everyone's files together.

But the real reason I had to do that, was that at random times characters would be permitted in the file name (most of these files are news clippings and news agencies will occasionally use non ASCII characters in their file names. Windows and Mac typically don't have a problem with those character, the host machine does and won't save it). The real reason for the UUID was just to have a unique reference to a file that I knew would work. I could have used the old file name, and just replaced any "invalid" characters, but then it would/did show up as '"Tru___ cabinet pick is said to be the _w_rst_ yet." Which isn't the end of the world, but it they go to search for it, they won't find it very easily. Plus, Inevitably after the users reached 7020 files (which they have) grabbing the files was a few seconds slower than an SQL search, so I list the files/search for files via the database. When the files get listed, the database shows the name that was given to it on upload, and a link to the file with its UUID. The client reads both, downloads the file by its UUID, and then names it accordingly.

I do like the idea your presented, it's sorta what I did at first, but didn't work with the host machine like it did in my dev environment.
Offline CoDi^R
« Reply #5277 - Posted 2017-02-21 13:56:52 »

files were stored on the server to use a UUID for the file name, and then store the real file name in a database with a reference to the UUID

Hash the file content, e.g. with SHA-1. Use this as your UUID and file name. As a side effect, you gain the option to detect hash collisions / duplicates. You lose the 1:1 mapping of user to file ownership, but there are solutions to this problem too.

Robotality - steamworks4j - @code_disaster - codi^r @ #java-gaming
Offline CJC

Senior Devvie


Medals: 16
Exp: 7 years


Just press buttons until it works.


« Reply #5278 - Posted 2017-02-21 14:31:54 »

files were stored on the server to use a UUID for the file name, and then store the real file name in a database with a reference to the UUID

Hash the file content, e.g. with SHA-1. Use this as your UUID and file name. As a side effect, you gain the option to detect hash collisions / duplicates. You lose the 1:1 mapping of user to file ownership, but there are solutions to this problem too.

Now that I like. Don't know why I didn't think of that honestly. I do think that I want to wait until the slow season kicks in before I make that change though, so I'll keep that in the back of my head for later.
Offline CJC

Senior Devvie


Medals: 16
Exp: 7 years


Just press buttons until it works.


« Reply #5279 - Posted 2017-02-22 15:13:42 »

Did a non work related thing today! Cheesy

Built a rough entity system so now I can spawn in entities, automatically have them removed if they die, and get an entity via it's collision box (not sure how I feel about having to resort to that, but I can't think of an alternative to find the entity).

I also got an ability system working, so I can swap out abilities for the player and essentially use that to make unique characters. I have a rewind ability (moves the player "back in time"), a slam ability (throws the player to the ground and creates a "smash" affect around them that damages entities), and a freeze ability that turns the player into a static body so that they can neither move, nor be moved. Mostly it's just me experimenting with ideas I get. Not sure if any of those would be fun to play with, but they were fun to write. Cheesy
Pages: 1 ... 174 175 [176] 177 178 ... 214
  ignore  |  Print  
 
 

 
Riven (81 views)
2019-09-04 15:33:17

hadezbladez (4336 views)
2018-11-16 13:46:03

hadezbladez (1547 views)
2018-11-16 13:41:33

hadezbladez (4462 views)
2018-11-16 13:35:35

hadezbladez (871 views)
2018-11-16 13:32:03

EgonOlsen (4152 views)
2018-06-10 19:43:48

EgonOlsen (4855 views)
2018-06-10 19:43:44

EgonOlsen (2803 views)
2018-06-10 19:43:20

DesertCoockie (3707 views)
2018-05-13 18:23:11

nelsongames (3998 views)
2018-04-24 18:15:36
Java Gaming Resources
by philfrei
2019-05-14 16:15:13

Deployment and Packaging
by philfrei
2019-05-08 15:15:36

Deployment and Packaging
by philfrei
2019-05-08 15:13:34

Deployment and Packaging
by philfrei
2019-02-17 20:25:53

Deployment and Packaging
by mudlee
2018-08-22 18:09:50

Java Gaming Resources
by gouessej
2018-08-22 08:19:41

Deployment and Packaging
by gouessej
2018-08-22 08:04:08

Deployment and Packaging
by gouessej
2018-08-22 08:03:45
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!