Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (494)
Games in Android Showcase (114)
games submitted by our members
Games in WIP (563)
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  
  Vector math slow down  (Read 1542 times)
0 Members and 1 Guest are viewing this topic.
Offline moogie

JGO Knight


Medals: 12
Projects: 6
Exp: 10 years


Java games rock!


« Posted 2009-01-30 07:29:42 »

I have been implementing a raytracing engine for the space sim community project but have noticed, what seemed to me, an unwarranted significant performance issue.

My computer is an Athlon XP 2800
I am able to get the engine to iterate over the pixels of a 640x480 display at  over 250fps.

When i add in a array look up it slows down to 190fps

when i add in some quite simple vector math to set up a ray for tracing it slows down to 15fps which i believe is excessive.

I believe i have isolated the problem somewhat to the following (which is in a code fragment listed later in the post)

1  
 tempPixel.position.copy(tempVec3D_3); 


By commenting out the above statement my frame rate doubles! This seems quite odd as tempPixel.position is a Vec3D object and the copy method (listed further in the post) simply copies the contents of the given vector!

Can anyone give me some pointers as to why that task is so processor intensive?



This is the code in question. Note that the actual ray tracing call has been commented out.

tile.height and tile.width are 480 and 640 respectively.

pixels array is an array of Pixel objects which have attributes useful for ray tracing, i.e. position, intersection point, display co-ordinates etc.

tempVec3D_3 is an instance of the Vec3D class listed further in the post.

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
         // iterate over the tile's rows
        for (intTemp1=0;intTemp1<tile.height;++intTemp1)
         {
            // iterate over the tile's columns
           
            for (intTemp2=0;intTemp2<tile.width;++intTemp2)
            {
               // obtain the pixel at the current row and column
              tempPixel=camera.pixels[intTemp3++]; // with this alone i get ~190 fps
             

                  // calculate the pixel's 3D coordinates
                 tempVec3D_3.copy(tempVec);
                  tempVec3D_3.scaleAdd(camera.stepUp,intTemp1);
                  tempVec3D_3.scaleAdd(camera.stepRight,intTemp2);
                  tempPixel.position.copy(tempVec3D_3);
                 
                  // calculate the primary ray's direction vector
                 tempVec3D_3.subtract(camera.position);
                  tempVec3D_3.unit();
                 
                  // trace the primary ray
                 //world.primaryRayTrace(primaryRay,tempPixel,camera);
           }
            ++intTemp3;
         }


i have the following class which represents a 3d vector and contains the vector operations for it.

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
53  
54  
55  
56  
57  
58  
59  
60  
61  
62  
63  
64  
65  
66  
67  
68  
69  
70  
71  
72  
73  
74  
75  
76  
77  
78  
79  
80  
81  
82  
83  
84  
85  
86  
87  
88  
89  
90  
91  
92  
93  
94  
95  
96  
97  
98  
99  
100  
101  
102  
103  
104  
105  
106  
107  
108  
109  
110  
111  
112  
113  
114  
115  
116  
117  
118  
119  
120  
121  
122  
123  
124  
125  
126  
127  
128  
129  
130  
131  
132  
133  
134  
135  
136  
137  
138  
139  
140  
141  
142  
143  
144  
145  
146  
147  
148  
149  
150  
151  
152  
153  
154  
155  
156  
157  
158  
159  
160  
161  
162  
163  
164  
165  
166  
167  
168  
169  
170  
171  
172  
173  
174  
175  
176  
177  
178  
179  
180  
181  
182  
183  
184  
185  
186  
187  
188  
189  
190  
191  
192  
193  
194  
195  
196  
197  
198  
199  
200  
201  
202  
203  
204  
205  
206  
207  
208  
209  
210  
211  
212  
213  
214  
215  
216  
217  
218  
219  
220  
221  
222  
223  
224  
225  
226  
package org.moogiesoft.JRTRT;

/**
 * Three dimensional Vector Class and utilites
 * @author nklaebe
 *
 */

final public class Vec3D {
   
   /** The x, y and z components of the vector */
   public double x,y,z;
   
   /**
    * Copy constructor. returns a 3D vector initalised to the same value as the passed in 3D vector
    * @param other The vector to copy
    */

   public Vec3D (final Vec3D other)
   {
      x=other.x;
      y=other.y;
      z=other.z;
   }
   
   /**
    * Constructor<br>
    * <br> Vector components initalised to 0
    *
    *
    */

   public Vec3D ()
   {
     
   }
   
   /**
    * Constructor<br>
    * <br> Vector components initialised with the passed in values
    * @param x value to initialise the x component with
    * @param y value to initialise the y component with
    * @param z value to initialise the z component with
    */

   public Vec3D (final double x,final double y,final double z)
   {
      this.x=x;
      this.y=y;
      this.z=z;
   }
   
   /**
    * re-initalises the x, y and z components to 0
    *
    */

   final public void zeroise()
   {
      x=y=z=0.0;
   }
   
   final public String toString()
   {
      return "x= "+x+" y= "+y+" z= "+z;
   }

   /**
    * Scales the vector by the given multiplier
    * @param scaleMuliplier the value to scale the vector by
    */

   final public void scale(final double scaleMuliplier)
   {
        x=x * scaleMuliplier;
        y=y * scaleMuliplier;
        z=z * scaleMuliplier;
   }

   /**
    * Adds the given vector scaleled by the given multipler
    * @param other the vector to add
    * @param scale the value to mutliply the other vector by
    */

   final public void scaleAdd(final Vec3D other,final double scale)
   {
      x+=scale*other.x;
      y+=scale*other.y;
      z+=scale*other.z;
   }
   
   /**
    * returns the dot product of this vector and the given other vector
    * @param other the other vector
    * @return the dot product of this vector and the given other vector
    */

   final public double dot(final Vec3D other )
   {
      return x*other.x+
         y*other.y+
         z*other.z;
   }
   
   /**
    * Assigns this vector to one vector minus another vector
    * @param vec the vector to assign this vector to
    * @param other the vector to subtact from this vector
    */

   final public void copySubtract(final Vec3D vec, final Vec3D other )
   {
      x=vec.x-other.x;
      y=vec.y-other.y;
      z=vec.z-other.z;
   }
   
   /**
    * Subtracts the given vector from this vector
    * @param other the vector to subtact from this vector
    */

   final public void subtract(final Vec3D other )
   {
      x-=other.x;
      y-=other.y;
      z-=other.z;
   }
   
   /**
    * Assigns this vector to one vector plus another vector
    * @param vec the vector to assign this vector to
    * @param other the vector to add to this vector
    */

   final public void copyAdd(final Vec3D vec, final Vec3D other )
   {
      x=vec.x+other.x;
      y=vec.y+other.y;
      z=vec.z+other.z;
   }
   
   /**
    * Adds the given vector to this vector
    * @param other the vector to add to this vector
    */

   final public void add(final Vec3D other )
   {
      x+=other.x;
      y+=other.y;
      z+=other.z;
   }
   
   /**
    * converts this vector into a unit vector
    *
    */

   final public void unit()
   {
      final double val= 1.0/ Math.sqrt(x*x+y*y+z*z);
      x*=val;
        y*=val;
        z*=val;

   }
   
   /**
    * assigns this vector's components to that of the passed vector
    * @param other the vector from which this vector will copy the components.
    */

   final public void copy(final Vec3D other)
   {
      x=other.x;
      y=other.y;
      z=other.z;
   }
   
   /**
    * returns the length of the vector squared
    * @return returns the length of the vector squared
    */

   final public double lengthSquared()
   {
      return x*x+
            y*y+
            z*z;
   }
   
   /**
    * caps each component of the vector to 1.0 if over 1.0
    *
    */

   final public void cap()
   {
      x=x>1.0?1:x;
      y=y>1.0?1:y;
      z=z>1.0?1:z;
   }
   
   /**
    * assigns this vector to the cross product of this vector and the passed in vector
    * @param other the other vector to use in the cross product
    */

   final public void crossProduct(final Vec3D other)
   {
      final double oldx=x;
      final double oldy=y;
        x=y * other.z - z * other.y;
        y=z * other.x - oldx * other.z;
        z=x * other.y - oldy * other.x;
   }
   
   /**
    * Perform vector multiplication of this vector and the passed vector
    * @param other the vector to perform multiplication with this vector
    */

   final public void multiply(final Vec3D other)
   {
      x *= other.x;
        y *= other.y;
        z *= other.z;
   }
   
   /**
    * Assigns this vector to the vector scaled by the multiplier
    * @param other the vector to assign this vector to
    * @param scale multiplier to scale the other vector by
    */

   final public void copyScale(final Vec3D other,final double scale)
   {
      x=other.x*scale;
      y=other.y*scale;
      z=other.z*scale;
   }

}


Offline Riven
« League of Dukes »

JGO Overlord


Medals: 793
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #1 - Posted 2009-01-30 08:27:15 »

tempPixel.position.copy(tempVec3D_3);

This line seems to be the only one in that loop that accesses a huge memory structure.

I think you're suffering from cache misses.


From the packagename, I assume you're trying to write a RealTimeRayTracing engine, in which case you really need to think about memory access speeds. Plain Java with lots of objects scattered over lots of native pages doesn't cut it, performance wise.
If I were you, I'd start converting my data structure to float[]s, accessed by 'sliding window' objects, to keep it all managable - they'd be like FloatBuffers, but without the performance quirks. You could ofcourse go even nastier, with sun.misc.Unsafe, with raw pointers, removing the nullpointer/arraybounds checks.

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
public class FloatData
{
   public FloatData(float[] arr, int off, int len, int stride)
   {
     
   }

   public void select(int index)
   {
      off = index * stride;
   }

   public static void add3(FloatData op1, FloatData op2, FloatData dst)
   {
       int off1 = op1.off;
       int off2 = op2.off;
       int off3 = dst.off;

       dst.arr[off3+0] = op1.arr[off1+0] + op2.arr[off2+0];
       dst.arr[off3+1] = op1.arr[off1+1] + op2.arr[off2+1];
       dst.arr[off3+2] = op1.arr[off1+2] + op2.arr[off2+2];
   }
}

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline Jono
« Reply #2 - Posted 2009-01-30 08:37:39 »

I have been implementing a raytracing engine for the space sim community project but have noticed, what seemed to me, an unwarranted significant performance issue.
15 fps sounds about what you'd expect from tracing 300k rays. I have a similar performance from a software ray-caster when working with around that many rays.

It might just be that if the only line is
1  
tempPixel=camera.pixels[intTemp3++];

that the compiler optimises out the array lookup (since the values won't be accessed when this is the only line) and is actually just doing an increment.

Can you do something trivial with tempPixel and see if you still get 190 fps?
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline moogie

JGO Knight


Medals: 12
Projects: 6
Exp: 10 years


Java games rock!


« Reply #3 - Posted 2009-01-30 09:51:11 »

Jono: i think you may be correct... i put in a simple post increment to a member variable of the tempPixel and the frame rate drops to ~50fps. That 15 fps i quotes was "not" performing the actual ray tracing, purely creating the ray per pixel. which is quite bad really.

riven: I was afraid you might say that... i had my suspicions about cache misses... bugger... it just made my existing framework pretty much useless... ah well. I will do as you suggest and get rid of my objects and use primitives as much as possible.

thanks for the heads up!

 
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.

Dwinin (19 views)
2014-09-12 09:08:26

Norakomi (54 views)
2014-09-10 13:57:51

TehJavaDev (63 views)
2014-09-10 06:39:09

Tekkerue (31 views)
2014-09-09 02:24:56

mitcheeb (53 views)
2014-09-08 06:06:29

BurntPizza (37 views)
2014-09-07 01:13:42

Longarmx (23 views)
2014-09-07 01:12:14

Longarmx (27 views)
2014-09-07 01:11:22

Longarmx (27 views)
2014-09-07 01:10:19

mitcheeb (35 views)
2014-09-04 23:08:59
List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

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

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

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

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

HotSpot Options
by dleskov
2014-07-08 01:59:08
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!