Java-Gaming.org    
Featured games (79)
games approved by the League of Dukes
Games in Showcase (477)
Games in Android Showcase (109)
games submitted by our members
Games in WIP (537)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  primitive ordering  (Read 2239 times)
0 Members and 1 Guest are viewing this topic.
Offline deepthought
« Posted 2010-11-09 22:04:50 »

what is the best way to put my primitives in the right order so transparency will work?

jocks rule the highschools. GEEKS RULE THE WORLD MWAHAHAHA!!
captain failure test game
Offline lhkbob

JGO Knight


Medals: 32



« Reply #1 - Posted 2010-11-09 22:27:37 »

Back to front if you're using blending in OpenGL.  This gets tricky if you have a bunch of triangles in vertex arrays since there is no order guarantee when submitting a batch.  It's pretty effective to sort back to front on each object's z-position (in camera space) and just disable rendering of back faces.

Offline deepthought
« Reply #2 - Posted 2010-11-09 22:35:03 »

so you mean if i put 4 faces into a vertex array, and render it, then opengl won't render in the order i sent them? and i realize i should render back to front, but how should i do that? average all the points in the face to get the center and compare those?

jocks rule the highschools. GEEKS RULE THE WORLD MWAHAHAHA!!
captain failure test game
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline tom
« Reply #3 - Posted 2010-11-10 13:29:36 »

Averaging the points would do. I suggest using an index vertex array so you only have to reorder and update the indices. To optimise the sorting you can convert the distance from a float to an int using Float.toIntBits and then do a radix sort on the ints.

Offline Orangy Tang

JGO Kernel


Medals: 56
Projects: 11


Monkey for a head


« Reply #4 - Posted 2010-11-10 13:34:27 »

This gets tricky if you have a bunch of triangles in vertex arrays since there is no order guarantee when submitting a batch.

Incorrect.

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Offline lhkbob

JGO Knight


Medals: 32



« Reply #5 - Posted 2010-11-10 17:18:42 »

Incorrect.
Re-reading the spec, I you're right.  For some reason, I thought I heard drivers could render them in any order for efficiency, but it looks like they do it in the order that you provide indices in the index array (for glDrawElements).  But that means to do correct transparent rendering, you have to resort the indices every frame if your camera changes since each triangles relative order could change.

Offline Riven
« League of Dukes »

JGO Overlord


Medals: 757
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #6 - Posted 2010-11-10 17:58:29 »

But that means to do correct transparent rendering, you have to resort the indices every frame if your camera changes since each triangles relative order could change.
You indeed have to manage sorting yourself, per frame. It's always been like this, and will only be solved when we are rendering in additive blending mode or have raytracing renderers.

A generic sorting algorithm will perform rather poor in this case. What you need is an algorithm that excels at almost-sorted values with only a handful of elements requiring (a few) swaps. Bubble-sort seems like a good fit, if the camera moves slowly.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline princec

JGO Kernel


Medals: 343
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #7 - Posted 2010-11-10 19:50:41 »

Radix sort can be handy in that case.

Cas Smiley

Offline Riven
« League of Dukes »

JGO Overlord


Medals: 757
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #8 - Posted 2010-11-10 20:03:41 »

Radix sort can be handy in that case.

Could you please enlighten me on how that beats bubble-sort in almost-sorted arrays?
AFAIK radix sort relocates every element 'k' times (k=number of digits) as the initial operation is to sort in the least significant digit, which almost guarantees every element being put at another postion.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline princec

JGO Kernel


Medals: 343
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #9 - Posted 2010-11-10 21:27:46 »

The one I'm using doesn't seem to have to move anything if nothing's changed position (you pass in the previous sort order to start with). I may be wrong.

Cas Smiley

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline tom
« Reply #10 - Posted 2010-11-11 09:44:48 »

Bubble-sort seems like a good fit, if the camera moves slowly.
That is a big if. And even small changes in the view position can result in dramatic changes in the sort order depending on the object being sorted. Also if you only sort objects within the view frustum you will get n*n complexity when objects enter the view. Besides, the view is not always the only thing moving in a game. Transparent objects my be moving and rotating themselves. I would go for a stable sorting algorithm like radix sort. Then you don't have to worry about the game pausing because bubble sort degenerating to n*n.

Offline deepthought
« Reply #11 - Posted 2010-11-11 14:21:10 »

i intend on first culling off anything that's not in the frustum then sorting it based on distance from the camera, because i figure it's not just the z-depth from the camera's point of view, but if i'm looking at something transparent from the side, i've got to sort it too.

jocks rule the highschools. GEEKS RULE THE WORLD MWAHAHAHA!!
captain failure test game
Offline deepthought
« Reply #12 - Posted 2010-11-12 17:14:27 »

actually wouldn't quicksort be faster than radix sort for this kind of thing?

jocks rule the highschools. GEEKS RULE THE WORLD MWAHAHAHA!!
captain failure test game
Offline Jono
« Reply #13 - Posted 2010-11-12 18:58:27 »

actually wouldn't quicksort be faster than radix sort for this kind of thing?
If you can do radix sort and you have enough data that performance matters, then it ought to always be faster than quicksort. Just set it up to use a number of buckets passes less than log_2 of the number of values you are sorting.

If you use a quicksort for this almost in-order data then you'd better roll your own, because a lot of the simple ways of picking pivots will tend to O(n^2).
Offline deepthought
« Reply #14 - Posted 2010-11-15 14:09:56 »

Ok 1 last question. would it be better to store primitives as a vector of say, a class for faces, a class for lines, and a class for points, or just a float vector and just keep track in the indices?

jocks rule the highschools. GEEKS RULE THE WORLD MWAHAHAHA!!
captain failure test game
Offline ryanm

Senior Member


Projects: 1
Exp: 15 years


Used to be bleb


« Reply #15 - Posted 2010-11-15 15:00:17 »

Keeping an object per point/line/face will cost you dearly with object overhead and cache coherency.
Offline deepthought
« Reply #16 - Posted 2010-11-17 02:08:48 »

ok i lied maybe i do have one more question. should i radix sort according to the least significant or most significant digit?

jocks rule the highschools. GEEKS RULE THE WORLD MWAHAHAHA!!
captain failure test game
Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

CogWheelz (16 views)
2014-08-01 22:53:16

CogWheelz (15 views)
2014-08-01 22:51:43

CopyableCougar4 (18 views)
2014-08-01 19:37:19

CogWheelz (19 views)
2014-07-30 21:08:39

Riven (27 views)
2014-07-29 18:09:19

Riven (16 views)
2014-07-29 18:08:52

Dwinin (14 views)
2014-07-29 10:59:34

E.R. Fleming (42 views)
2014-07-29 03:07:13

E.R. Fleming (13 views)
2014-07-29 03:06:25

pw (44 views)
2014-07-24 01:59:36
Resources for WIP games
by CogWheelz
2014-08-01 18:20:17

Resources for WIP games
by CogWheelz
2014-08-01 18:19:50

List of Learning Resources
by SilverTiger
2014-07-31 18:29:50

List of Learning Resources
by SilverTiger
2014-07-31 18:26:06

List of Learning Resources
by SilverTiger
2014-07-31 13:54:12

HotSpot Options
by dleskov
2014-07-08 03:59:08

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:58:24

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:47:22
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!