# Why is this computation loop not linear in time (performance-wise)?

I am sorry if this question has an obvious answer, which I just fail to see. Anyway, if anyone can enlighten me, I would be grateful. Writing a tool for a specific purpose, I needed to calculate whether something obstructed the view from the object to the camera eye (of the observer of the view). I use the API raytest function for this purpose, something which technically works absolutely correct.
However, calculating using raytest in a loop for every vertex in a grid with N vertices, I expected the loop to require approximately the same time per vertex. To my surprise, when testing with the three grids shown in the picture, I get these numbers:

Original array has 961 points
Processing done after: 0.389203 for 961 pts (0.0004049979188345474 sec/pt): nohits=961

Original array has 121 points
Processing done after: 0.006125 for 121 pts (5.061983471074381e-05 sec/pt): nohits=121

Original array has 441 points
Processing done after: 0.085612 for 441 pts (0.0001941315192743764 sec/pt): nohits=441

My test routine is fairly simple:

``````#
def self.check_if_vertices_unobstructed_x(vtx_ary, eye)

num_nohit = 0

num = vtx_ary.size

puts "Original array has #{num} points"
start_time = Time.now

if (vtx_ary.size > 0)
for i in 0..num-1
pos = vtx_ary[i].position
hit = Sketchup.active_model.raytest([pos, Geom::Vector3d.new(eye - pos)], true)
if (hit == nil)
num_nohit += 1
end
end
end

end_time = Time.now
diff_time = end_time - start_time
puts "Processing done after: #{diff_time} for #{num} pts (#{diff_time/num} sec/pt): nohits=#{num_nohit}"

return num, num_nohit
end

# From faces and edges, get all vertices
def self.get_vertex_ary(fac_ary, edg_ary)
vtx_ary = []
if (fac_ary != nil) && (fac_ary.size > 0)
fac_ary.each { |f|
f.edges.each { |e|
vtx_ary << e.start
vtx_ary << e.end
}
}
end

if (edg_ary != nil) && (edg_ary.size > 0)
edg_ary.each { |e|
vtx_ary << e.start
vtx_ary << e.end
}
end

vtx_ary.uniq!
return vtx_ary
end

# Get all active vertices
def self.get_active_vertex_ary()

# Get all active faces
fac_ary = Sketchup.active_model.active_entities.grep(Sketchup::Face)
# Get all vertices
vtx_ary = get_vertex_ary(fac_ary, nil)

return vtx_ary
end

# Default code, use or delete...
mod = Sketchup.active_model # Open model
ent = mod.entities # All entities in model
sel = mod.selection # Current selection

puts ""
# Get active vertices in context
@vtx_ary_all = self.get_active_vertex_ary()

# Return array with only visible (non_obstructed) vertices
num, num_nohit = check_if_vertices_unobstructed_x(@vtx_ary_all, Sketchup.active_model.active_view.camera.eye)
``````

Is there a straigthforward reason for the loop not behave linearly in time?
Doing this test in a loop is probably a bad idea if there existed a bulk raytest alternative. I am, however not aware of one?

I find the code hard to read so it’s hard to see if there is any issue with it. You can increase readability by correcting indentation, correct comments and method names (is `check_if_vertices_unobstructed_x` supposed to list these vertices or just count them? is it only checking the X coordinate?), purge unused code (“default” code) and shorten the code.

For instance `get_vertex_ary` could be replaced with `entities.flat_map(&:vertices).uniq`, where entities is an array of objects responding to `vertices` (edges and faces).

The Rubocop style guide is a good resources for writing readable code.

I’m on my phone so I can’t test code now, but I speculate that this is because in get_vertex_ary you are gathering the vertices for the start and end of every edge, but vertices are shared where edges intersect. If you count the number of vertices shared by two edges (outer corners), the number shared by three edges (borders except corners), and the number shared by four edges (interior), I think you will find that the total is not linear in the size of the grid.

Thanks a lot for throwing in a (good) suggestion.
It is fully possible that I am completely blind to something here, but I cannot really see
that I am counting vertices multiple times.
I have further simplified the code, if anyone cares to put it to a test.
I am still puzzled by this…

``````#
def self.check_if_vertices_unobstructed_x(vtx_ary, eye)

num_nohit = 0

num = vtx_ary.size
start_time = Time.now

if (vtx_ary.size > 0)
for i in 0..num-1
pos = vtx_ary[i].position
hit = Sketchup.active_model.raytest([pos, Geom::Vector3d.new(eye - pos)], true)
if (hit == nil)
num_nohit += 1
end
end
end

end_time = Time.now
diff_time = end_time - start_time
puts "Processing done after: #{diff_time} for #{num} pts (#{diff_time/num} sec/pt): nohits=#{num_nohit}"

return num, num_nohit
end

# Default code, use or delete...
mod = Sketchup.active_model # Open model
ent = mod.entities # All entities in model
sel = mod.selection # Current selection

puts ""

# Get all active vertices
vtx_ary_all = Sketchup.active_model.active_entities.flat_map(&:vertices).uniq
puts "Array has #{vtx_ary_all.size} vertices"

#
num, num_nohit = check_if_vertices_unobstructed_x(vtx_ary_all, Sketchup.active_model.active_view.camera.eye)
``````

The time it takes to process one ray cast is proportional to the amount of geometry in the model. The large grid has roughly twice the geometry of the medium grid and the processing time per ray is about double as well.

2 Likes

I guess you are onto something here. Would you care to elaborate a little why this is so?
Is there a way around this?

1 Like

(1) You do not need to do this clunky handling of array iteration …

Ruby handles the correct iteration of collections quite well. Use either …

``````for v in vtx_ary
# code ...
end
``````

… or …

``````vtx_ary.each do |v|
# code ...
end
``````

(2) Eliminate as many method calls in your loop as possible.

• Create a `model` reference to the active model before the loop so you call `Sketchup.active_model` only once.

• `Geom::Vector3d.new(eye - pos)` is a frivolous call to the class constructor method because the `Geom::Point3d.-` method already returns a `Geom::Vector3d` object.

• The creation of references takes time. So you can eliminate the need for the `pos` reference if you instead convert the vertex array to a point array before starting the loop. This also eliminates the repeated `.position` method calls within the loop.

Simpler example of the loop …

``````  model = Sketchup.active_model
pt_ary = vtx_ary.map(&:position)

num_nohit = 0
start_time = Time.now

for pt in pt_ary
hit = model.raytest([pt, eye - pt], true)
num_nohit += 1 if hit.nil?
end
``````

However you can also use the `Enumerable#count` iterator method instead of coding the `num_nohit` increment …

``````  model = Sketchup.active_model
pt_ary = vtx_ary.map(&:position)

start_time = Time.now
num_nohit = pt_ary.count do |pt|
model.raytest([pt, eye - pt], true).nil?
end
``````
1 Like

Can you share the test model.

Sure I can.
Here is also the revised test code as per Dan’s recommendations.

``````#
def self.check_if_vertices_unobstructed_x(vtx_ary, eye)

mdl = Sketchup.active_model
pt_ary = vtx_ary.map(&:position)

num_nohit = 0
start_time = Time.now

for pt in pt_ary
hit = mdl.raytest([pt, eye - pt], true)
num_nohit += 1 if hit.nil?
end

end_time = Time.now
diff_time = end_time - start_time
puts "Processing done after: #{diff_time} for #{pt_ary.size} pts (#{diff_time/pt_ary.size} sec/pt): nohits=#{num_nohit}"

return num_nohit
end

# Default code, use or delete...
mdl = Sketchup.active_model # Open model
ent = mdl.entities # All entities in model
sel = mdl.selection # Current selection

puts ""
#@vtx_ary_all = self.get_active_vertex_ary()
@vtx_ary_all = mdl.active_entities.flat_map(&:vertices).uniq

puts "Original array has #{@vtx_ary_all.size} points"

#
num_nohit = check_if_vertices_unobstructed_x(@vtx_ary_all, mdl.active_view.camera.eye)

`````` Untitled_X.skp (3.9 MB)
My numbers for running the test in the context of the various sandbox sizes:

Original array has 121 points
Processing done after: 0.005968 for 121 pts (4.932231404958678e-05 sec/pt): nohits=121

Original array has 441 points
Processing done after: 0.084026 for 441 pts (0.00019053514739229024 sec/pt): nohits=441

Original array has 961 points
Processing done after: 0.390207 for 961 pts (0.0004060426638917794 sec/pt): nohits=961

Original array has 10201 points
Processing done after: 57.576294 for 10201 pts (0.00564418135476914 sec/pt): nohits=10201

The operation gets prohibitively slow as one reaches a couple of thousands of vertexes.

It dawns on me that you must be doing something very similar in your Vertex Tools (which I am also using, by the way).
Could you share some insight on how you are collecting the visible (unobstructed) vertices there, because in your tool the collection is blindingly fast, also for 10000 points and even more???

(BTW: Thanks to all who gives good reasons to improve my ruby knowledge. I am not using ruby as my default language, but I am willing to learn and attempt to improve my skills.)

1 Like

There is a few things happening in Vertex Tools:

• I use a `Set` to ensure uniqueness and quick lookups
• When vertex mode is activated I collect all vertices in the current context by collecting the vertices from all visible edges:
``````  @vertices.clear
draw_hidden = Sketchup.active_model.rendering_options['DrawHidden']
@model.active_entities.grep(Sketchup::Edge) { |edge|
next unless edge.layer.visible?
next unless draw_hidden || edge.visible?
@vertices.merge(edge.vertices)
}
``````
If you collect from faces you end up with many more duplicates you need to filter out. (Also, you wouldn’t catch the vertices that only belong to edges.
• I perform the same action when the model changes.
• Drawing the vertices is also slow - because technically I have to draw a line segment in 3D space in order for the points to be occluded. `view.draw_points` is drawn in screen space (2D). Because of that, whenever I rebuild the set of vertices I also make a pass on them and use `view.screen_coords(v)` to check if they are within the bounds of the view’s `vpwidth` and `vpheight`.
• When performing selection actions it will use the on_screen subset - not the full set of vertices.
• By default all vertices on_screen is processed when selecting.
• If you enable Ignore Backfaces then it will filter out vertices connected to faces that are fall facing away from the camera. Often this is a decent occlusion approximation. This is relatively fast.
• If you want true occlusion then you must enable Select Only Visible which will perform a `model.raytest`. However, this is done only on the subset that was within the selection aperture or selection region as a final filtering step. I’m doing a lot to reduce number of raytests.

I need to look closer at your sample to understand the not-linear time observation you make.

But beside that - maybe you can explain quickly on a higher level what you are trying to do? Maybe there are other ways to improve performance to the task you are trying to achieve. Also helps to understand what performance affordances you might have.

This by the way is what 3D Studio Max does. I think most 3D apps will do this as true occlusion testing is expensive.