The chain shot challenge

[Mike Lobanovsky]

Charles,

There is also an alternative (unofficial) picking technique that might work considerably faster than the official glLoadName() method.

The official method implies looping through all the objects in the scene to find out the one whose coordinates are the closest to the viewer's cursor in the given state of the frame's z-buffer. The looping is relatively slow, and especially so for heavily populated scenes with a few hundred thousand polies and more in view.

The unofficial method also presupposes an extra render invisible to the viewer because it is executed without the usual SwapBuffers() call (the hungriest FPS eater) at the end of frame render. The scene is rendered untextured and unlit, which makes the render yet faster. Instead, the objects are rendered simply in shades of red, green, or blue where each shade corresponds directly to the respective object's index in the array of scene objects.

For simplicity, let the number of objects in the scene be not more than 256. Then object 0 could be rendered in integer color RGB(0,0,0), object 1, in color RGB(0,0,1) (blue), object 2, in color RGB(0,0,2) (lighter blue), etc. etc. etc. All we have to do now is just poll the pixel color under the cursor's hotspot with glReadPixels() during this invisible render -- et voila the desired index of the object the cursor is pointing to, without unnecessary looping!

Below please find a screenshot of XANEngine's pick render forced on-screen for demonstration purposes. It uses shades of blue but in a 32-bit float color space because there may be up to 1K objects in the current field of view with some 200K+ visible (unculled) polies, some of which may also be alpha transparent. glLoadName() would've been unbearably slow in this environment.

The second screenshot is a practical use case of this unofficial color-coded method in the XANEngine Editor where it powers, amongst other things, the tooltip used to optionally display some data about the object that the cursor is currently pointing at within the famous 3D model of Sponza Palace in Aurel's beloved Croatia.

.

[JRS]

Amazing detail and realism with those cloths.

Great stuff, keep it coming!
 

[Charles Pegge]

Hi Mike,

We can reduce the burden of the pick-rendering quite a lot. - no shading or texturing - no buffer swap. Also replacing objects with bounding boxes or simple polyhedra. Furthermore, Pick is usually activated only on a mouse-click.

For my Opengl EditBox, I use 3 converging pick-passes. The passes converge with minimal geometry thus:

1: boxes to represent each text window.
2: boxes to represent each visible line within the selected text window.
3: boxes representing the left half and right-half of each character in the selected line.

This information is used to place the caret to the left or to the right of the identified character.



In this example, spheres are face-stepped at 45 degres instead of 6 degrees, during the pick pass:

Code: OxygenBasic

1.  '#compact
2.  includepath "$\inc\"
3.   % filename "t.exe"
4.  'include    "RTL32.inc"
5.  % Title    "Chainshot3D:    (left-click & right-click)"
6.   % Animated
7.   % ScaleUp
8.  '% PlaceCentral
9. '% AnchorCentral
10.  includepath "$\inc\"
11.   include "ConsoleG.inc"
12.   include "chaos.inc"
13.   %side 8
14.  
15.   indexbase 1
16.  
17.   type celltype
18.   long  a,n
19.   long  x,y,z
20.   float px,py,pz
21.   float tx,ty,tz
22.   end type
23.  
24.   sys sseed=GetTickCount
25.   celltype cell[side*side*side]
26.   sys      vsphere
27.  
28.   sub initcells()
29.   ===============  
30.   sys r,x,y
31.   'seed=0x2468abcd
32.  seed=sseed
33.   celltype *c
34.   @c=@cell
35.   for z=1 to side
36.     for y=1 to side
37.       for x= 1 to side
38.         r=irnd(1,4)
39.         c.x=x
40.         c.y=y
41.         c.z=z
42.         c.a=r
43.         c.n=z*64+y*side+x-side
44.         c.px= rnd()*32
45.         c.py= rnd()*32
46.         c.pz=-arnd()*100+10
47.         @c+=sizeof cell
48.       next
49.     next
50.   next
51.   end sub
52.  
53.   initcells()
54.  
55.   function GameLogic(sys i,optional a) as sys
56.   ===========================================
57.   '
58.  if not i then exit sub
59.   cell[i].a=0
60.   return 1
61.   end function
62.  
63.  
64.   sub render(celltype*c)
65.   ======================
66.   sys a
67.   a=c.a
68.   if a then
69.     glpushmatrix
70.     move c.px+c.tx, c.py+c.ty, c.pz+c.tz
71.     if pick then
72.       Picklabel c.n
73.       go vsphere 'crude bounding sphere
74.    else
75.       select a
76.       case 1 : RedShinyMaterial.act
77.       case 2 : BlueShinyMaterial.act
78.       case 3 : WhiteShinyMaterial.act
79.       case 4 : GoldMaterial.act
80.       end select
81.       'REDUCE TRANSITION DISTANCE
82.      'if c.tx then c.tx*=.75
83.      'if c.ty then c.ty*=.75
84.      'if c.tz then c.tz*=.75
85.      go sphere
86.     end if
87.     glpopmatrix
88.    end if
89.   end sub
90.  
91.   sub main()
92.   ==========
93.   if not vsphere then
94.     'CRUDE SPHERE
95.    vsphere   = CompileList : Spheric 1,1,45 : glEndList
96.   end if
97.   '
98.  static float az
99.   static sys   pki,count
100.   glClearColor 0,0.10,0,0
101.   Fog          0,0.10,0,0.05 'FOR SENSE OF DISTANCE
102.  '
103.  pushstate
104.   shading 'opposite of 'flat'
105.  '
106.  'DISPLAY TOP SECTION
107.  pushstate
108.     move 2
109.     color .90,.90,.90,.99
110.     scale 2 : print3d "Popped  id: " pki " count: " count
111.   popstate
112.   '
113.  move 16,-16,-4
114.   rotatez az : az+=.03125
115.   scale 2
116.   '
117.  'DISPLAY
118.  sys a,i,x,y
119.   for z=1 to side
120.     for y=1 to side
121.       for x=1 to side
122.         i++ : render cell[i]
123.         if picked=cell[i].n then pki=i
124.       next
125.     next
126.   next
127.   picklabel 0
128.   '
129.  popstate 'whole
130.  '
131.  if picked then
132.     GameLogic(pki)
133.     count++
134.     picked=0
135.   end if
136.   '
137.  end sub
138.  
139.   EndScript
140.  

Images showing 45 degree spheres and 6 degree spheres:

.

[Mike Lobanovsky]

Also replacing objects with bounding boxes or simple polyhedra.

I'm afraid this won't really work, Charles, except in very rare cases of extremely primitive shapes like in your example. It will certainly not work for the use case depicted in the attached screenshot where the task is to spot the red chair (ID 15) lying on the floor in the library, through the delicate suspension of the roof-mounted chandelier (ID 113).

Code: OxygenBasic

1.   for z=1 to side
2.     for y=1 to side
3.       for x=1 to side
4.         i++ : render cell[i]
5.         if picked=cell[i].n then pki=i
6.       next
7.     next
8.   next
9.  

Now how am I supposed to do all this picking in case I prefer to have all the balls in the scene precompiled in a list of draw lists in order to further improve the overall render speed rather than call each ball's draw list separately in a triply nested loop? Keep this loop in the code just for the sole purpose of if picked=cell(i).n then pki=i, really?

.

[Charles Pegge]

Yes Mike, I can see the advantage of using a color signature for picking, in those scenes. But the standard pick system works well in more abstract modelling, which might involve picking objects or their components, potentially thousands of similar items on the screen.

PS: an array of objects is most efficiently named using its index. However, in this case  I have chosen to use the object's n(ame) attribute - nothing to worry about in the broader scheme of things

[Mike Lobanovsky]

potentially thousands of similar items on the screen

Coloring the objects in a pick render with glColor3i(red , green, blue) in the following simple integer sequence:

• glColor3i(0, 0, 0) to glColor3i(0, 0, 255) - first 256 indices in the object array
• glColor3i(0, 1, 0) to glColor3i(0, 1, 255) - ditto, second 256 indices
• .............................
• glColor3i(255, 255, 255) - ditto, last index

will allow you to color code 16M distinct objects maximum.

Then, following the pseudo-code below:

Code: OxygenBasic

1. Type PIXCOLOR
2.         BYTE r
3.         BYTE g
4.         BYTE b
5.         =
6.         int i
7. End Type
8.  
9. PIXCOLOR pixel
10.  
11. glReadPixels(x, y, 1, 1, GL_RGB, GL_UNSIGNED_BYTE, @pixel) // x, y are cursor coords in OpenGL coord system
12.  
13. int index = pixel.i

will yield the required object's index in just one function call instead of triply nested loop.



If I were you (which of course I ain't ), I'd have Oxygen re-armed with this tool a.s.a.p.

[Charles Pegge]

Thanks Mike. I will think about it. Though I am am sceptical about how efficient this is when compared with colorless/non-pixelised passes in glrender GL_SELECT mode, and a tiny 2x2 viewport. Usually there are very few hits to resolve depthwise.

[Mike Lobanovsky]

There's nothing that prevents you from restricting your viewport to 2x2 px (or even 1x1 px, for that matter) in the color coded pick render method either, is there? And a single hardware accelerated glReadPixels() call for just one pixel in the frame buffer would hardly be slower than a call to GDI's GetPixelV(). Just think how much obsolete vendor code may be hidden behind the entire glRenderMode(GL_SELECT) method.


[EDIT] And oh, glColor() is usable in between glBegin() and glEnd(), i.e. freely compilable in a draw list. Also, please read Answer 15 on this StackOverflow page. Perhaps it will help alleviate your steady skepticism towards my methods. I'm not pressing you in any way, though.


Have a nice night, Charles!

[Charles Pegge]

Hi Mike,

Well, the article convinced me, so I dunnit! Your persistence has paid off I see that GL_SELECT is doomed to eventual obsolescence, along with numerous other OpenGl features traditionally used by CADs.

% ColorCodedPick will be used to switch-in the new picking system. The change is not quite so convenient to deploy, since the backdrop must be set to black during the pick phase, and also, no coloring of objects, between a pick-label and their  vertex specs.


Merry Chrismas all!

[Mike Lobanovsky]

Nice to hear that, Charles, and sorry for a delayed response but I've got an urgent business in the last 24 hours and I couldn't come here earlier.


Merry Christmas and a happy and prosperous New Year 2015 to you, Charles, and all the forum members and OxygenBasic fans who drop by from time to time!

[Charles Pegge]

.

[Charles Pegge]

With horizontal profiling:


.

[Mike Lobanovsky]

Cheers!

[RobbeK]

Thanks for all this info 

What'd you think about the Chain Shot Cylinder or the CS Sphere ?   


best , Rob

[Mike Lobanovsky]

Hi Rib,

A cylinder seems as feasible to play as a cube but a sphere would be very difficult to beat. There will be at least one splice of balls whose rim will have nothing both on top and beneath it. These balls will have only one chance to be blasted, which is with the right mouse click on the z axis.

But I like the idea immensely. Perhaps Charles could add those options to his game?