Determine if edge would split face

Garry K · 29 Dec 2015, 19:07

I start with hundreds of faces and hundreds of edges. The faces are in one group and the edges are in another group.

The first image shows 1 face and 1 edge where the edge is coplanar with face.
I want to end up with 2 faces just like the second image.

I could get make a copy of the array of vertices that make up the face and then add the 2 points that make up the edge and then run fit_plane_to_points and check to see if the resultant plane is equal to the plane of the face.

If it passes then I would need to figure out how to calculate the 2 new vertices that are on the second image.

Any shortcuts or ideas on a better method? Is there a way to quickly throw out edges that aren't close?

jolran · 29 Dec 2015, 20:27

If 2D, sweepline-sort, perhaps with binary search Array and sort by X or Y.
Boundingbox from faces could be used as bounds..
I suppose the faces bounds coordinates would have to be sorted as well, not making it optimal..

If 3D I don't know. Faces could be standing straight up and sweepline would miss it..

Even if you sort roughly, you are gonna cut down the calculations a lot.
n faces * n edges is a bad algorithm. But for 100 edges and faces you shouldent get such a hit anyhow ?

fredo6 · 29 Dec 2015, 22:58

Possibly, you create a copy of the Group of Edges into the Group of faces, and then explode it. Sketchup would normally divide the faces for the edges which are coplanar to them. Then you erase the lonely edges (i.e. not attached to a face).

If you need to do that algorithmically, then, you can divide the global bounding box containing the group of edges and the group of faces into a 3D grid (for instance 20 x 20 x 20), as a set of BoundingBox objects. Then you can once mark each BB-cube with the faces and edges with respect to the conditions:

a face has one vertice in the BB-cube or an edge intersecting the BB-cube
an edge has one vertex in the BB-cube or intersects the BB-cube
These tests are normally fast, since based on built-in methods of BoundingBox.

Then you process each cube with its attached edges and faces. In principle, this should help to reduce the total number of tests.

By the way, you must keep track of all edges coplanar with a face, even those not splitting faces, because they can subsequently create sub-faces when associated with other coplanar edges.

Fredo

jolran · 30 Dec 2015, 06:48

@unknownuser said:

If you need to do that algorithmically, then, you can divide the global bounding box containing the group of edges and the group of faces into a 3D grid (for instance 20 x 20 x 20), as a set of BoundingBox objects. Then you can once mark each BB-cube with the faces and edges with respect to the conditions:

a face has one vertice in the BB-cube or an edge intersecting the BB-cube

an edge has one vertex in the BB-cube or intersects the BB-cube
These tests are normally fast, since based on built-in methods of BoundingBox.

I really like this idea.

Edit: removed nonsence I previously posted, missread the algorithm. Looping egdes and faces is only needed once to mark BB. Although one would have to loop each boundingbox per entity (worst case) to find the correct BB to attach to ? So to many bounding box divisions arent to ones advantage ?
20 X 20 X 20 = 8000 boundingboxes.
Edgeintersect boundingbox is presumably a Point in volume calculation ?
Meaning for each vertice first test if in rectangle X/Y(4 tests) then if inside Z (2 tests).
6 tests X 2 vertices (worst case) leads to a worst case of 96 000 tests per edge..

Solution might be to add double sweepline approach in boundingbox ranges. Per each BB column first test if egde fall within X and Y, and then proceed. If so then proceed in columns ( each BB in z-axis ). But maybe this is what you had in mind already but forgot to mention. I might be stating the obvious..

sdmitch · 30 Dec 2015, 15:15

@garry k said:

I start with hundreds of faces and hundreds of edges. The faces are in one group and the edges are in another group.

The first image shows 1 face and 1 edge where the edge is coplanar with face.
I want to end up with 2 faces just like the second image.

Any shortcuts or ideas on a better method? Is there a way to quickly throw out edges that aren't close?

Name the edge group "edges" and the face group "faces". Select both then execute this code. Of course this a simplistic example but I have no idea how complex the edges and faces maybe. If you would care to post a model, version<=2014 for me,

mod = Sketchup.active_model
ent = mod.active_entities
sel = mod.selection
egrp = sel.grep(Sketchup;;Group).select{|g|g.name=='edges'}[0]
edges = egrp.entities.grep(Sketchup;;Edge)
fgrp = sel.grep(Sketchup;;Group).select{|g|g.name=='faces'}[0]
faces = fgrp.entities.grep(Sketchup;;Face)
et = egrp.transformation; ft = fgrp.transformation; new_pts = []
for f in faces
 ctr = f.bounds.center.transform(ft)
 vec = f.normal.transform(ft); f_plane = f_line =[ctr,vec]
 for e in edges
  next unless e.start.position.transform(et).on_plane? f_plane
  next unless e.end.position.transform(et).on_plane? f_plane
  spt,vec=e.line; spt.transform!(et); vec.transform!(et); e_line=[spt,vec]
  pts = Geom.closest_points e_line,f_line
  next unless e.bounds.contains?(pts[0].transform(et.inverse))
  if f.classify_point(pts[0].transform(ft.inverse))==1
   new_pts << mod.raytest([pts[0],vec.reverse])[0].transform(ft.inverse)
   new_pts << mod.raytest([pts[0],vec])[0].transform(ft.inverse)
  end
 end
end
1.step(new_pts.length-1,2) {|i| fgrp.entities.add_line(new_pts[i-1],new_pts[i])}

Garry K · 30 Dec 2015, 15:58

Thanks guys - this gives me some good direction. I like Sam's strategy where he makes use of the raytest.