ShootersForever.com Forum Index

GoldenEye 007 Nintendo 64 Community, GoldenEye X, Nintendo 64 Games Discussion
GoldenEye Cheats, GoldenEye X Codes, Tips, Help, Nintendo 64 Gaming Community


Opcode 09 - Binary Seperating Plane

 
Post new topic   Reply to topic    ShootersForever.com Forum Index -> Q-Lab Hacking Department
View previous topic :: View next topic  
Trevor
007
007


Joined: 15 Jan 2010
Posts: 926
Location: UK, Friockheim OS:Win11-Dev PerfectGold:Latest

 PostPosted: Sat Jan 09, 2016 10:41 am    Post subject: Opcode 09 - Binary Seperating Plane Reply with quote Back to top

Rules for Binary Separating Plane.

    Note 2018:
    All examples below use GwppksilZ.
    Opening Editor to "Edit Model" and going to GwppksilZ will show a familiar window of parts on the bottom left. If you now click on "Tree View" you will see the editor use the same tree style I show below.
    This tree view allows Drag and Drop placement of parts within a BSP.

    On New Guns you first need to add via the dropdown on the right "09 Binary Space Partition"* then you can drag your "Left" and "Right" "Display List" on to it, then finally drag the BSP under a "Position" node.
    Keep adding BSP nodes until every "Display List" is partitioned.
    New BSP Nodes should only have 2 children of any type, including further BSP.
    If you have 3 Display Lists - lets say topslide, frame and grip you need 2 BSP nodes with the first having children Topslide and BSP and the second Frame and Grip.
    Code:
    Position
        |
       BSP
     |    |
    top  BSP
         |  |
      frame grip


    You then need to orientate the Separating Plane, in this case horizontally since the topslide is above the frame which is above the grip. To do this each plane has a vector of 0,-1,0 (pointing down) and a position set to the boundary of each display list - i.e. where the topslide meets the frame.
    If you reversed the order so that the grip was on the first BSP and the frame and topslide were on the second BSP
    Code:
    Position
        |
       BSP
     |    |
    grip BSP
         |  |
      frame top

    Then you would need a vector of 0,1,0 (pointing up).

    If you use the Editor Drag and Drop feature you don't need to read about references since the Editor deals with all of this for you.

    *This is a typo and should read Binary Separating Plane




BSP Nodes Must Reference 2 parts, eg part 30 and Part 08

Reference 1 Must be the Lower Order Part - eg 08
Reference 2 Must be the Higher Order Part - eg 30

If you use the wrong order then they fail to draw any children.
    Eg, setting BSP 07 on Silenced PPK to
    Ref1: 30
    Ref2: 08
    Will only draw a silencer in the air, nothing else.


These references define which branch is on which side of the plane.
In Leafy BSP tree nomenclature this is "Left" and "Right", but put simply, we have a "Front" of plane and "Back" of plane.
Reference 1 is "Left" or "Back"
Reference 2 is "Right" or "Front"

BSP 07 References Parts 08 and 30 and the plane points forward.
This assigns part 30 to the right/front and part 08 to the left/back.

In Normal 1st person view, the camera (our eyes) are "Behind" the plane so the front is drawn first with the back drawn "on top" next.
    in 3D programs All objects are drawn or "painted" on top of anything that comes before in the "drawing list".
    eg. if we reprisent the list as a series of numbers that draw to the screen big enough to see 1 number at a time:
    - the list : 1,2,3,4,5 will have a 5 on screen since 5 was last.
    - the list : 1,5,2,4,3 will have 3 on screen since 3 was last

    The Z-Buffer is a mechanism to sort lists by distance, but uses more RAM. BSP is another sorting mechanism as demontrated below


If we turn the gun round, like in the watch, then Part 30 would be in front of the plane as we look at it, therefor drawing last as "In Front"



Planes do not nessesarelly have to split parts exactly, but they should. There is no down side to not being alligned, as the below examples show.
(I have multiplied the vector lines x10 so they are more visible)



If the plane was wildly off then odd results will show, so best to be sure.



To swap the order you Invert the Vectors or click "invert X,Y or Z" in PG.
- Format is PointX, PointY, PointZ, VectorX, VectorY, VectorZ

eg:
to Draw part 30 on top of the rest, invert BSP 07 Vector to -Z, [ 0,0,-21 ]
To Draw the UpperTopslide below the LowerTopslide invert BSP 2C to -Y, [ 0,-21,0 ]



BSP Example in Motion.

I have a slight error in the PPK where somewhere along the line it draws double-sided.
If the silencer draws first, it is single sided, if drawn last its double sided.
As the gun rotates it switches from single to double sided.
I made 2 examples with inverted BSP vector (07) and they appeared opposite to each other.

From the front of the gun, the silencer is drawn last. (Because we and it are in front of the plane)

This can be seen in the watch as I left a cull command open on the sights. Because of this, the silencer appears bolder since its drawing both front and back faces.


From the Back of the gun (as held), the silencer is drawn first, or if you will, the rest of the gun is drawn last as both we and the rest of the gun are on the same side of the plane.

This can be seen in the watch as the open cull command has not yet been reached and so only the front faces of the silencer are drawn.


When I invert the vector of BSP 07, the opposit is shown in watch.




The first image shows a double sided silencer away from us, and a single sided one towards us.
This means the silencer is last, then when closest to us, first (being overritten by everything else, as you can probably see the topslide taking over the silencer)


I hope this all makes sence, but its finally easy to swap orders and move planes around for our Goldfinger Guns.


Objects and guards use BSP as there is a Binary Seperating Plane between the neck and head.
This is to draw the head on top of the body when looking at the front of a guard after certian distances when the z-buffer looses accuriacy.
likewise, the BSP draws the neck on top of the head when looked at from behind.

The Dam Truck uses BSP to correctly draw the wheels from all viewpoints, the "Jeep" neglects to use the BSP and will draw wrongly when looked at from 1 side (passenger side)

Another use for BSP is to help speed up the z-buffer, the rules are opposit to normal though with regard to plane direction.
eg. z-buffered surfaces are drawn Front to Back instead of the "painters" back to front.
This helps save Z-Buffer re-write and incuring only a read and can speed up a scene x2.


Example Binary Seperating Plane Trees



Binary Sperating Planes in PD

PD does support BSP, guns and related objects could be imported As-Is and work however there are 2 big problems I will describe below.

    1 - Hands, If you want to use PD Hands, forget it.
    Hands are a single model and cannot be position set within the guns model tree. Therefor Hands will ALWAYS draw on top.

    2 - Coronas Fail to be occluded by Z-Less guns.


To be of use in PD, all vectors need to be reversed to draw Front-Back from the viewpoint and all geometry needs ZBuffer enabled.

Now, this seems to be a waist, except that it allows for less Z-Buffer re-writes in the best case or no change in the worst.

Is the work worth it... no, thats why rare didnt bother.

BSP in that useage would need to be on much bigger screen filling polygons to reduce z-buffer thrashing.



Apart from those however, BSP does work and can continue to be - and should be - used on trucks and trees etc.



Tree Traversal Example

in the following tree of the PPK Silenced we will decide what is left and right from the first BSP (07)



7 has child of 8.
8 = left ref
8 has child 9.
9 is dlist, mark left.
9 has no child or next, return to 8
8 has next, A.
A NOT = RightRef (continue to mark as left)
A has child B
B has child C
C had child D
D has child E
E is Dlist, mark left
E has no child or next, return to D
D has next, F
F is dlist, mark as left
F has no child or next, return to C
C has next, 10
10 has child 11
11 has child 12
12 has child 13
13 has child 14
14 is dlist, mark as left
14 has no child but has next, 15
15 is dlist, mark as left
15 has no child or next, return to 13.
13 has next, 16
16 is dlist, mark left
16 has no child or next, return to 12
12 has no next, return to 11
11 has next, 17
17 has child 18
18 is dlist, mark left
18 has no child but has next, 19
19 has child 1a
1a has child 1b
1b is dlist, mark as left
1b has no child or next, return to 1a
1a has no next, return to 19
19 has next, 1c
1c is dlist, mark left
1c has no child, has next, 1d
1d has child 1e
1e has child 1f
1f is dlist, mark left
1f has no child or next, return to 1e
1e has no next, return to 1d
1d has next 20
20 is dlist, mark left
20 has no child or next, return to 17
17 has no next, return to 10
10 has no next, return to B
B has next, 21
21 has child 22
22 has child 23
23 is dlist, mark as left
23 has no child or next, return to 22
22 has next 24
24 has child 25
25 has child 26
26 is dlist, mark as left
26 has no child or next, return to 25
25 has next, 27
27 is dlist, mark as left
27 has no next or child, return to 24
24 has no next, return to 21
21 has next, 28
28 has child 29
29 has child 2A
2A has child 2b
2b is dlist, mark as left
2b has no child, has next 2c
2c has child 2d
2d is dlist, mark as left
wd has no child, has next 2e
2e is dlist, mark as left
2e has no child or next, return to 2c
2c has no next, return to 2a
2a has next, 2f
2f is dlist, mark as left.
2f has no child or next, return to 29
29 has no next, return to 28
28 has no next, return to A

A has next, 30, 30 = rightref
30 is dlist, mark as right.
30 has no child or next, return to 7 and end





Trev

All BSP of PPK Scilenced in a model for moving around if needed is here.
http://fgfc.ddns.net/PerfectGold/GunBSP/PPK_Scil_BSPlanes.an8
http://fgfc.ddns.net/PerfectGold/GunBSP/PPK_Scil_BSPlanes.obj


Last edited by Trevor on Sat Mar 10, 2018 7:10 am; edited 20 times in total
 
View user's profile Send private message
Trevor
007
007


Joined: 15 Jan 2010
Posts: 926
Location: UK, Friockheim OS:Win11-Dev PerfectGold:Latest

 PostPosted: Wed Jan 13, 2016 10:55 am    Post subject: Reply with quote Back to top

This was the original post, moved to second post since its not the headline.
Rules and workings are correctly described above, this is archive only.


Background:
While Altering Guns I noticed that some parts that were late in the list actually drew first, specifically the Silencer.
While the silencer is last and should draw on top of everything, it does not.

Ill paste the PPK Gun Tree here for reference, Original file with aditional comments is located Here

Code:

PPK/Silenced
   

00 [02 Position] (main) (Command: 0000) (Matrix: 00000000)                               
    01 [12 Handle/Switch]                                                               
        02 [02 Position] (muzzle flash near) (Command: 0001) (Matrix: 00000040)
            03 [02 Position] (muzzle flash far) (Command: 0002) (Matrix: 00000080)
                04 [04 Display List No Collision]                MFlash
            05 [04 Display List No Collision]                    NMflash
    06 [15 Position Held-items] (0003) (Matrix: 000000C0)
    07 [09 Head/Hat Placement]                                   08:30 (30>8>A)
        08 [12 Handle/Switch]                                                           
            09 [04 Display List No Collision]                    03 Barrel
        0A [09 Head/Hat Placement]                               0B:21 (0B>21>28)
            0B [09 Head/Hat Placement]                           0C:10 (10>0C)
                0C [09 Head/Hat Placement]                       0D:0F (0F>0D)
                    0D [12 Handle/Switch]                                               
                        0E [04 Display List No Collision]        04 Thumb
                    0F [04 Display List No Collision]            05 frame
                10 [09 Head/Hat Placement]                       11:17 (17>11)
                    11 [12 Handle/Switch]                                               
                        12 [09 Head/Hat Placement]               13:16 (16>13)
                            13 [09 Head/Hat Placement]           14:15 (15>14)
                                14 [04 Display List No Collision]06 Mid
                                15 [04 Display List No Collision]07 Ring
                            16 [04 Display List No Collision]    08 Pinky
                    17 [09 Head/Hat Placement]                   18:20 (18>19>1C>1D>20)
                        18 [04 Display List No Collision]        09 trigger/Inside
                        19 [12 Handle/Switch]                                           
                            1A [02 Position] (trigger finger) (Command: 0004) (...
                                1B [04 Display List No Collision]0A Tfinger
                        1C [04 Display List No Collision]        0B RightGripSide
                        1D [12 Handle/Switch]                                           
                            1E [12 Handle/Switch]                                     
                                1F [04 Display List No Collision]0C fingersrear
                        20 [04 Display List No Collision]        0D Grip
            21 [09 Head/Hat Placement]                           22:24 (22>24)
                22 [12 Handle/Switch]                                                   
                    23 [04 Display List No Collision]            0E knuckles
                24 [12 Handle/Switch]                                                 
                    25 [12 Handle/Switch]                                               
                        26 [04 Display List No Collision]        0F wrist
                    27 [04 Display List No Collision]            10 SlideGuard
            28 [02 Position] (top slide) (Command: 0005) (Matrix: 00000140)
                29 [09 Head/Hat Placement]                       2A:2F (2A>2F)
                    2A [09 Head/Hat Placement]                   2B:2C (2C>2B)
                        2B [04 Display List No Collision]        11 Hammer         
                        2C [09 Head/Hat Placement]               2D:2E (2D>2E)
                            2D [04 Display List No Collision]    12 LowerTopslide
                            2E [04 Display List No Collision]    13 upperTopslide
                    2F [04 Display List No Collision]            14 Sights
        30 [04 Display List No Collision]                        15 Silencer


Analysis:
Ill draw your attention to each call of [09 Head/Hat Placement].

These determin the draw order for the referenced parts, eg
07 [09 Head/Hat Placement] This references parts 08 & 30.

How it determins order was the question untill it was revealed that Guns used a technique called "Leafy BSP".
While BSP (Binary Space partitioning) uses polygons to specify a plane and therefore each BSP Node has 1 poly on it, Leafy BSP an arbitory Plane to divide Groups of Polygons. BSP here is Binary Seperation Plane.

In MultiGen they inserted BSP nodes between Model parts and allowed MultiGen to do all the calculations for Dissabled Z-Buffer.

This might not be the recognised way to do it, but its how Rare did it.

Just as standard BSP, a Point (or model Center in Leafy case) is tested against the plane and view location. If the View is in front of the plane, then rear objects are drawn first followed by Front, Likewise, If the view is behind the plane then the front object is drawn first followed by the rear.

The next problem was finding out how this worked.
The Equation of a plane is ax+by+cz+d=0 (point-Normal). You can also define a plane as 3 points, or 2 vectors.
The BSP Node seperating the Silencer and rest of the gun has a 192bit value. It would seem logical to keep the original assumption of 6 32bit floats.
So, what do the values mean?

Conclusion:
My final guess is that they define a point (xyz) and a direction (Vector) (abc) although this goes against the flt spec in my original doc
However, it does seem to fit.
Example 1 BSP 07 (Silencer/Rest of gun)
Punching the numbers in we get (assuming I am doing this right)
(0 * 0) + (0 * 57.956562) + (21.299997 * 182.028091) = d. d= 3877.198
While it seems like a very big number, it shows that is points forward (c=21, Normalised is +1) and is set forward of the origin (d=3877, perhaps Im supposed to normalise first, making d=182 which is more reasonable).
The silencer is on the "Front" and since we are "back" (as plane faces away from us) the "front" is drawn first.

Example 2 BSP 2A (Hammer/Rest of Topslide)
(0 * 0) + (-15.061374 * 14.569698) + (15.061375 * -51.424210) = -993
Ok, I am definatly doing something wrong, but let me continue.
This plane points 45 degrees down forward and is set back of the origin. This fits the Hammer as the hammer is slanted.
The hammer is considered "Back", since we are back Hammer is drawn last.

Example 3, Lets try a different order, BSP 2C (Lower/Upper topslide)
(0 * 0) + (21.299999 * -6.283808) + (0 * -31.807751) = -133.845104116192
Well, regardless of the stupid equation, this plane points "up" and is raised off the origin.
The Upper Topslide is considered "Front", as we are above the plane, we too are considered "Front" so Lower is drawn first.
If you rotate the gun so that the upper topslide is behind the lower topslide, it should still draw correctly since the camera will be on the "Back" of the BSP Node and the order will swap drawing Back after front.

Trev

P.S. I should note this topic is open to dicussion on the values.

It seems that the equation serves no purpose in my above examples except to find the constand d.
ax + by + cz = d
(0 * 0) + (21.299999 * 6.283808) + (0 * -31.807751) = -133.845104116192

However, this is then used to find the "side" of a verticie or object center.

a(objCenx) + b(objCeny) + c(objCenz) + 133.8 = Side

If Side => 0, obj is in "Front"
If Side < 0, obj is in "Back"

Normalisation to unit vectors is not required since we do not care about the distance the object is from the plane, only its side (+/-).

Example: - - - - - - -

If an objCen was (0,-6.283808,-31.807751) then we punch in:
(0 * 0) + (21.299999 * -6.283808) + (0 * -31.807751) + 133.8 = Side

Since Side = 0 this Object lies on the plane.

- - - - - -

If an objCen was (0,10,30) then we punch in:
(0 * 0) + (21.299999 * 10) + (0 * 30) + 133.8 = Side

Since Side = 346.8 this Object lies in front of the plane.

- - - - - -

If an objCen was (0,-30,0) then we punch in:
(0 * 0) + (21.299999 * -30) + (0 * 0) + 133.8 = Side

Since Side = -505.2 this Object lies in Back of the plane.


Edit:13/06/2016
I should note here that all refrences above to ObjCen are wrong. The only test done is CameraLocation.
The same equations apply, its just that its not objects that are tested, but camera location.
eg: lets use my last eqn
If CamLoc is (0,-30,0) then we punch in:
(0 * 0) + (21.299999 * -30) + (0 * 0) + 133.8 = Side

Since Side = -505.2 the camera lies in Back of the plane meaning "Back" or "Left" tree is dran on top.
That is to say, it will travers the whole right side now before returning to draw the left on top
_________________
 
View user's profile Send private message
Wreck
Administrator
Administrator


Joined: 14 Dec 2005
Posts: 7197
Location: Ontario, Canada

 PostPosted: Fri Mar 09, 2018 7:56 pm    Post subject: Reply with quote Back to top

Moved per request of Trevor.
Bumping up to top for newer viewers.
 
View user's profile Send private message Visit poster's website
Display posts from previous:   
Post new topic   Reply to topic    ShootersForever.com Forum Index -> Q-Lab Hacking Department All times are GMT - 8 Hours
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum

Cobalt 2.0 BB theme/template by Jakob Persson.
Copyright © 2002-2004 Jakob Persson


Powered by BB © 01, 02 BB Group

 


Please Visit My Other Sites: GoldenEyeForever.com | GrandTheftAutoForever.com

Got kids? Check out my Dora The Explorer site with games and coloring pages!

Our forums feature Nintendo 64 games, GoldenEye 007 N64 New Maps and Missions, GoldenEye Cheats, N64 Emulator, Gameshark, GoldenEye Multiplayer and more!

[ Privacy Policy ]