Deleting Redundant Edges from a Solid

#1

Yet another weird topological problem. As many of you know I am battling with my complex roof module right now and so far it is proving more difficult than I would like to admit.

I have the plugin creating the roof primitive 99% of the time but in a few cases I end up with an extra edge or two that are not actually required to make the group a solid. I call these redundant edges. The extra edges do not render the group a non-solid but they are splitting up faces that I would rather not split.

Has anyone ever come across and algorithm or method for removing non-essential edges from a solid (manifold)?

Capture
Capture.JPG1056×812 101 KB

#2

Turns out the solution wasn’t too hard to devise:

def check_redundant_edges
	
	edge_list = @group1.entities.grep(Sketchup::Edge)

	edge_list.each do |e|
		next unless e.valid?
		next if e.line[1][2].round(5) == 0.0
		next if e.start.position[2] == @Fasciaz || e.end.position[2] == @Fasciaz
		
		if e.start.position[2] > e.end.position[2]
			ve = e.start
		else
			ve = e.end
		end

		edges_ve = ve.edges
		edges_ve.delete(e)
		
		next unless edges_ve[0].line[1].samedirection?(edges_ve[1].line[1])
		
		e.erase!
		puts 'redundant edge removed'
	end
end

I will say that this is probably one of my most efficient algorithms to date.

#3

EDIT … Please see this other thread using plane / vertex comparison …

Would something like this also work ?

# Erase redundant edges in an entities context. A face is redundant if it is
# used by more than 1 face and all it's faces have parallel normal vectors.
#
# @param context [Sketchup::Entities] can be any entities context (choose from: 
# model.entities, model.active_entities, group.entities or definition.entities.)
#
# @return [Integer] count of deleted edges.
#
def erase_redundant_edges(context)
  edge_list = context.grep(Sketchup::Edge)
  redundant = edge_list.find_all do |e|
    next false unless e.faces > 1
    vector = e.faces.first.normal
    e.faces.all? { |f| f.normal.parallel?(vector) }
  end
  unless redundant.empty?
    context.model.start_operation('Remove redundant edges',true,false,true)
      context.erase_entities(redundant)
    context.model.commit_operation
  end
  redundant.count { |e| e.deleted? }
end

Edited: To put whole operation inside unless redundant.empty? block.
Edit-2: Corrected first line to remove call to .entities as context should be an Sketchup::Entities instance object. Added docsting for YARD. Adding return a count of deleted edges.
Edit-3: Corrected the erase_entities line (in the operation) to remove .entities call (as it is now an entities context.)

1 Like
#4

What is this ‘context’ that you are putting in front of the start and commit operation methods, how does that work? I’ve never seen that before.

#5

‘context’ can be any entities context:- choose from…

  • model.entities
  • model.active_entities
  • group.entities
  • definition.entities
2 Likes
#6

What I actually did was renamed the @group1 reference in your code snippet to context but one step UP from what TIG described. Perhaps it should be named object instead, but it cannot be just any object class. It has to respond_to? method calls :entities and :model.
So perhaps container would be a better name ?

I just realized I may have “outsmarted” myself. I thought at the last minute that you could possibly pass in either: a group, a component or the model proper.
BUT, now I see that this will not work as written. Ie, a call to model.model would produce a NoMethodError, as well as if you passed in a ComponentInstance (the entities call needs to be made on it’s definition.)

So really TIG has the right of it.

The method’s arg should be any of his listed 4 entities collections …
and the 1st line should change from …

 edge_list = context.entities.grep(Sketchup::Edge)

… to …

 edge_list = context.grep(Sketchup::Edge)

I’ll change the above snippet for future readers and add TIG’s list as method params.

And also changed the erase_entities line (in the operation) to remove .entities call as it is now (as always should have been,) an entities context.

context.entities.erase_entities(redundant)

… is now …

context.erase_entities(redundant)
1 Like
#7

Comparing normals of faces is not sufficient to determine if you can erase the edges between them. This is due to tolerances when you get small faces or slither faces etc.

Instead take the plane of one of the faces and see if the vertices of the other faces lies on that same plane. This is now SketchUp compares if faces are planar to each other.

(CleanUp has this implemented: https://github.com/thomthom/cleanup)

1 Like
#8

Which we’ve been discussing in this other thread the past few days …

1 Like
#9

When I do the boolean subtraction to cut out the various roof planes occasionally I get these extra edges (that are redundant). It seems to be unpredictable or somewhat random, sometimes they appear and sometimes they don’t, I’m not entirely sure why this behavior exists:

truss_su573_800
truss_su573_800.jpg800×535 21.5 KB

My previous algorithm was quite specific and dealt only with redundant edges on the actual roof planes.

With the interior gables enabled I’m now facing the possibility of redundant edges on the vertical (wall) faces as well.

Looks like I will need to revisit this topic and see if I can come up with a more general solution.

I tend to dislike general solutions since they tend to be more computationally expensive especially when you have a complex shape with many polygons. The downside to the more specific algorithms is that if something new likes this comes along then you have to re-adjust. It’s debatable as to which is the better way of doing things.

#10

is the skp somewhere?

john

1 Like
#11

View model here:

#12

The first thing that is jumping out at me is that the edges in question are all vertical.

I use this chunk of code to detect for horizontal edges (or ridges):

if edgei.line[1][2].round(5) == 0.0

What would be the most efficient way to check for vertical edges?

#13

Perhaps something like this?

if edgei.line[1].parallel?(Z_AXIS)

1 Like
#14

you must know the start points for all of those already?

can you not find new edges with those start point…

john

#15

This seems to work quite well:

if e.line[1].parallel?(Z_AXIS)
	e.erase!
	puts 'vertical redundant edge removed'
end

Its not a general solution but it does remove all of the vertical edges, which in this particular case is exactly what I need.

At some point though I may need the completely general case. I do like the idea of comparing the normal vector of faces that belong to an edge and if they are the same direction then the edge is redundant. If you look at a solid it quickly becomes apparent that any given edge can only belong or border two faces.

Maybe something like this:

def remove_redundant_edges
  edge_list = @group1.entities.grep(Sketchup::Edge)
  edge_list.each do |e|
    next unless e.valid?
    edgefaces = e.faces
    if edgefaces[0].normal.parallel?(edgefaces[1].normal)
      e.erase!
      puts 'redundant edge removed'
    end
  end
end
#16

BUT … you only want to erase vertical edges that divide faces that are planar with one another.

There are other vertical faces at the bottom corners of the roof slopes, and you’ll have vertical edges on dormers.

1 Like
#17

True, but I forgot to mention that the bottom section of the roof (fascia) does not exist at first, I push-pull that later. I also don’t have dormers, that will be part of the secondary roof module which will be a completely different roof assembly and have its own roof primitive.

#18

Iterate over your edges and for any edge connected to two faces, check if they are co-planar: