Collision Code Optimization

bentleykfrog · 20 Feb 2011, 10:11

I've been doing some speed tests to model some collision 'physics' in sketchup and found these methods interesting. My collision model is based on 6 vertices projected out of the camera point to detect surrounding objects (to save overhead). The total time I was aiming for was below 0.04 seconds to produce a decent frame rate. I started out with this script using view.inputpoint to guess the target. Its a translation of guess_target from the Film & Stage Plugin(camera.rb);

Sketchup.active_model.start_operation("collision",true); 
view = Sketchup.active_model.active_view; 
t=Time.now; 
eye = view.camera.eye; 
10.times { 
  target = Geom;;Point3d.new(rand(10),rand(10),rand(10)); 
  view.camera.set(eye, target, Geom;;Vector3d.new(0,0,1)); 
  center_pt = view.center; 
  input_point = view.inputpoint center_pt.x, center_pt.y;
}; 
puts Time.now - t; 
Sketchup.active_model.abort_operation;

This produced on average over 10 iterations of 0.4136 seconds.

I compared this with the raytest method which removed the need to update the camera:

Sketchup.active_model.start_operation("collision",true); 
view = Sketchup.active_model.active_view; 
t=Time.now; 
eye = view.camera.eye; 
up = Geom;;Vector3d.new(0,0,1); 
10.times { 
  target = Geom;;Point3d.new(rand(10),rand(10),rand(10)); 
  ray = [eye, (eye.vector_to target)]; 
  result = Sketchup.active_model.raytest( ray ); 
}; 
puts Time.now - t; 
Sketchup.active_model.abort_operation;

This produced an average over 10 iterations of 0.1395 seconds.

I also noted that setting the second variable of raytest to false saves some more time. setting raytest to (ray,false) produced an average of 0.1363 seconds.

Since its a collision test, we've got a maximum distance that the collision 'physics' will cut in at, so we don't need to get any points beyond this. So performing raytest beyond this set distance to get a 3d point would be pointless. So I thought setting a maximum raytest distance by writing lines along each ray at this distance would stop raytest in its tracks. So this is what the script below does:

Sketchup.active_model.start_operation("collision",true); 
entities = Sketchup.active_model.active_entities;
group = entities.add_group;
entities = group.entities;
view = Sketchup.active_model.active_view; 
t=Time.now; 
eye = view.camera.eye;
up = Geom;;Vector3d.new(0,0,1);
10.times {
  target_vector = Geom;;Vector3d.new(1+rand(10),1+rand(10),1+rand(10));
  target = eye + target_vector;
  vector = eye.vector_to target;
  vector.reverse!;
  vector.normalize!;
  target2 = target + vector;
  line = entities.add_line target,target2;
  ray = [eye, target_vector];
  result = Sketchup.active_model.raytest(ray,false);
}; 
puts Time.now - t;
Sketchup.active_model.abort_operation;

This produced an average of 0.0219 seconds when in clear space, and an average of 0.1382 when close to an entity.

Its still a massive difference between each, and since the first only intersects with vertices, there's probably some large overhead when getting an intersection on a face? I could use this to simulate dead collisions, but any bouncing or parallel strafing would be quite slow.

Anybody got any suggestions or experience with the matter? I'm at a bit of a dead end.

-niall

Dan Rathbun · 21 Feb 2011, 09:27

May not give you much more:
Wrapped in a begin .. rescue .. end block.
Removed frivolous repeated method calls.
Init'd target_vector outside loop, and reused it using set!
Put initialed refs outside loop to perhaps gain a bit so Ruby doesn't need to keep creating new references.
Removed the ref assignment " line =" as it was not being used.
Commented out the ray and result line, as I don't see it being used.
The up line also.

<span class="syntaxdefault">model </span><span class="syntaxkeyword">=</span><span class="syntaxdefault"> Sketchup</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">active_model<br />entities </span><span class="syntaxkeyword">=</span><span class="syntaxdefault"> model</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">active_entities<br />view </span><span class="syntaxkeyword">=</span><span class="syntaxdefault"> model</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">active_view<br />eye </span><span class="syntaxkeyword">=</span><span class="syntaxdefault"> view</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">camera</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">eye<br /><br />begin <br />  model</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">start_operation</span><span class="syntaxkeyword">(</span><span class="syntaxstring">"collision"</span><span class="syntaxkeyword">,</span><span class="syntaxdefault">true</span><span class="syntaxkeyword">)<br /></span><span class="syntaxdefault">  group </span><span class="syntaxkeyword">=</span><span class="syntaxdefault"> entities</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">add_group<br />  entities </span><span class="syntaxkeyword">=</span><span class="syntaxdefault"> group</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">entities<br />  </span><span class="syntaxcomment">#up = Geom;;Vector3d.new(0,0,1)<br /></span><span class="syntaxdefault">  target_vector </span><span class="syntaxkeyword">=</span><span class="syntaxdefault"> Geom</span><span class="syntaxkeyword">;;</span><span class="syntaxdefault">Vector3d</span><span class="syntaxkeyword">.new<br />&nbsp;&nbsp;</span><span class="syntaxdefault">vector&nbsp;</span><span class="syntaxkeyword">=&nbsp;</span><span class="syntaxdefault">Geom</span><span class="syntaxkeyword">;;</span><span class="syntaxdefault">Vector3d</span><span class="syntaxkeyword">.new<br />&nbsp;&nbsp;</span><span class="syntaxdefault">target&nbsp;</span><span class="syntaxkeyword">=&nbsp;</span><span class="syntaxdefault">0<br />&nbsp;&nbsp;target2&nbsp;</span><span class="syntaxkeyword">=&nbsp;</span><span class="syntaxdefault">0<br />  t</span><span class="syntaxkeyword">=</span><span class="syntaxdefault">Time</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">now<br />  10</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">times </span><span class="syntaxkeyword">{<br /></span><span class="syntaxdefault">    target_vector</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">set</span><span class="syntaxkeyword">!(</span><span class="syntaxdefault">1</span><span class="syntaxkeyword">+</span><span class="syntaxdefault">rand</span><span class="syntaxkeyword">(</span><span class="syntaxdefault">10</span><span class="syntaxkeyword">),</span><span class="syntaxdefault">1</span><span class="syntaxkeyword">+</span><span class="syntaxdefault">rand</span><span class="syntaxkeyword">(</span><span class="syntaxdefault">10</span><span class="syntaxkeyword">),</span><span class="syntaxdefault">1</span><span class="syntaxkeyword">+</span><span class="syntaxdefault">rand</span><span class="syntaxkeyword">(</span><span class="syntaxdefault">10</span><span class="syntaxkeyword">))<br /></span><span class="syntaxdefault">    target </span><span class="syntaxkeyword">=</span><span class="syntaxdefault"> eye </span><span class="syntaxkeyword">+</span><span class="syntaxdefault"> target_vector<br />    vector </span><span class="syntaxkeyword">=</span><span class="syntaxdefault"> eye</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">vector_to</span><span class="syntaxkeyword">(</span><span class="syntaxdefault">target</span><span class="syntaxkeyword">)<br /></span><span class="syntaxdefault">    vector</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">reverse</span><span class="syntaxkeyword">!<br /></span><span class="syntaxdefault">    vector</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">normalize</span><span class="syntaxkeyword">!<br /></span><span class="syntaxdefault">    target2 </span><span class="syntaxkeyword">=</span><span class="syntaxdefault"> target </span><span class="syntaxkeyword">+</span><span class="syntaxdefault"> vector<br />    entities</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">add_line</span><span class="syntaxkeyword">(</span><span class="syntaxdefault">target</span><span class="syntaxkeyword">,</span><span class="syntaxdefault">target2</span><span class="syntaxkeyword">)<br /></span><span class="syntaxdefault">    </span><span class="syntaxcomment">#ray = [eye, target_vector]<br /></span><span class="syntaxdefault">    </span><span class="syntaxcomment">#result = model.raytest(ray,false)<br /></span><span class="syntaxdefault">  </span><span class="syntaxkeyword">}<br /></span><span class="syntaxdefault">  model</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">commit_operation<br />  puts</span><span class="syntaxkeyword">(</span><span class="syntaxdefault"> Time</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">now </span><span class="syntaxkeyword">-</span><span class="syntaxdefault"> t </span><span class="syntaxkeyword">)<br /></span><span class="syntaxdefault">rescue<br />  model</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">abort_operation<br />end</span>

AdamB · 21 Feb 2011, 11:43

Dan:
Its the other around surely. The add_line is superfluous and added just to confirm the lines are sane. He wants to test the performance of the raytest you commented out..

bentleykfrog:
SketchUp is not optimised for collision - it doesn't need to be - so you'll get disappointing results using a function whose primary focus is to aid GUI interaction with a 3D model.

Using the raytest functionality to add some nice "clash detection" when placing a Components is one thing. Resolving general interpenetration using some iterative convergence is another, requiring 100x / 1000x more performance.

bentleykfrog · 22 Feb 2011, 01:20

@adamb said:

Using the raytest functionality to add some nice "clash detection" when placing a Components is one thing. Resolving general interpenetration using some iterative convergence is another, requiring 100x / 1000x more performance.

I see your point Adam, thanks Its looking like I'll have to keep this very basic, with only one large raytest representing the point and vector of the camera. If raytest is affected by the large FOV clipping issue I'll have to apply some modifications based on the FOV and the angle between the cross of [the face normal and camera vector] and the camera vector. I'll have to translate the camera movement to the cross of the face normal and camera as well. If anything complex happens after this in the same frame the movement will need to stop dead to preserve the frame rate.

thanks

-niall

Dan Rathbun · 22 Feb 2011, 04:58

@adamb said:

Dan: Its the other [way] around surely. The add_line is superfluous and added just to confirm the lines are sane. He wants to test the performance of the raytest you commented out..

Okie.. dokie. I didn't understand what he was trying for (it was late.) That was why I just commented out the lines and did not remove them.

The gist of what I meant was to init references (vars,) outside the loop, and limit creation of new ones inside the loop unless they are actaully necessary (ie, to be used in some way.) Ruby takes time to create references.