Capture convex hull of shape and delete interior geometry

Hello,

I have a little ruby script which creates a cloud-like shape by creating a mass of random spheres and ovoid shapes. I’m sorta happy with it, except the resulting file size of the cloud is rather large ~15MB. I would like to do something like: capture the outside surface of the cloud as finished shape, but delete all the geometry inside, leaving just the outside as the finished object.

Here you can see just how many objects are involved just on the exterior

I have included an example skp file of the cloud object.

clouds-2h5j234.skp (13.6 MB)

Thanks for any ideas
j_jones

Solid tools first icon and smooth edges…
Captura de pantalla 2023-08-29 a las 7.35.00

clouds-2h5j234.skp (2.2 MB)

with ruby (outer shell & soft edges)

1 Like

Here´s the cloud without internal geometry, I exploded the groups that were visible, deleted the ones in the interior that weren’t visible and intersected faces.

clouds-2h5j234 (1).skp (2.0 MB)

1 Like

I am experimenting how to make clouds out of curiosity, the first methods I used was with Artisan and it’s sculpting tools but the best result so far is starting with a cube, subdivide it with subD plugin adding 1 iteration, explode it then using vertex tools in soft selection mode grab vertex randomly and deform the geometry once I get the shape I like I subdivide it one more time, and create some creases on some places to make it look more real, finally I select everything and using random tools the random vertex moving tool I apply it to the entire geometry but the values of the distortion are very low no more than 0.1 on every axis. I got a pretty nice cloud.

P.S. This methods generates a lot of geometry so I wouldn’t recommend it if the cloud isn’t the main element of the model. It is also posible getting rid of some geometry using vertex tools combine by distance or with universal importer, importing the cloud on a new file and reducing the geometry.

1 Like

Thank you for all these suggestions. I will have to study them as they kind of went over my head. I should have mentioned I would like to do this algorithmically because I am trying to learn to utilize the ruby api. I am really more of a newbie than a developer I see now.

But here is my ruby script for generating this cloud shape if it is interesting.

module Cloud

  def self.create_color(color, alpha, i)
    model = Sketchup.active_model
    entities = model.active_entities
    material = model.materials.add("Cloud Color #{i}")
    material.color = color
    material.alpha = alpha
    return material
  end
  
  def self.get_sphere_dims(sphere)
    height = sphere.bounds.height
    width = sphere.bounds.width
    depth = sphere.bounds.depth
    hwd = [height, width, depth]
    return hwd
  end

  def self.create_ovoid_sphere(sphere, min_rand, max_rand)
    # todo: modify this method so all spheres are stretched along the axis of choice, instead of randomly
    cpt = sphere.bounds.center
    #hwd = self.get_sphere_dims(sphere)
    #print "create_ovoid_sphere: begin sphere dims:", hwd
    
    x = rand(min_rand..max_rand)
    y = rand(min_rand..max_rand)
    z = rand(min_rand..max_rand)
    scale = Geom::Transformation.scaling(cpt, x, y, z)
    sphere.transform!(scale)
    #hwd = self.get_sphere_dims(sphere)
    #print "create_ovoid_sphere: end sphere dims:", hwd
    return sphere
  end

  def self.create_sphere(center, radius, material)
    model = Sketchup.active_model
    entities = model.active_entities

    group = entities.add_group
    g_entities = group.entities
    model.start_operation("create_sphere",true,false,true)
    
    circle = g_entities.add_circle center, Z_AXIS, radius
    circle_face = g_entities.add_face circle
    circle_face.material = material
    circle_face.back_material = material

    path = g_entities.add_circle center, X_AXIS, radius + 1
    circle_face.followme path
    g_entities.erase_entities path
    model.commit_operation

    model.commit_operation
    model.active_view.refresh

    return group
  end
  
  def self.displace_sphere(sphere, x_range, y_range, z_range, angle_range)
    #cpt = sphere.bounds.center
    #print "displace_sphere: location:", cpt
    x = rand(-x_range..x_range)
    y = rand(-y_range..y_range)
    z = rand(-z_range..z_range)
    center = [x,y,z]
    angle = rand((90-angle_range)..90+angle_range)
  
    x_rotate_x = Geom::Transformation.rotation(ORIGIN, X_AXIS, angle.degrees)
    x_rotate_y = Geom::Transformation.rotation(ORIGIN, Y_AXIS, angle.degrees)
    x_rotate_z = Geom::Transformation.rotation(ORIGIN, Z_AXIS, angle.degrees)
    x_point = Geom::Transformation.new(center)

    sphere.transform!(x_rotate_z * x_rotate_x * x_rotate_y)
    sphere.transform!(x_point)
    #cpt = sphere.bounds.center
    #print "displace_sphere: new location:", cpt
  end

  def self.create_cloud(num_spheres, min_radius, max_radius, min_rand, max_rand, 
                          x_range, y_range, z_range, angle_range)
    model = Sketchup.active_model
    entities = model.active_entities
    model.start_operation("create_cloud",true,false,true)

    color = Sketchup::Color.new(255, 255, 255)
    material = self.create_color(color, 25.0, 1)

    num_spheres.times do |i|
      x = rand(min_rand..max_rand)
      y = rand(min_rand..max_rand)
      z = rand(min_rand..max_rand)
  
      radius = rand(min_radius..max_radius)
      sphere = self.create_sphere([x,y,z], radius, material)
      sphere = self.create_ovoid_sphere(sphere, 20, 40)
      self.displace_sphere(sphere, x_range, y_range, z_range, angle_range)
    end
    model.commit_operation
  end
end 

num_spheres = 75
min_radius = 15.0
max_radius = 40.0
min_rand = 1
max_rand = 40

x_range = 750
y_range = 750 
z_range = 750
angle_range = 20

Cloud.create_cloud(num_spheres, min_radius, max_radius, min_rand, max_rand, 
  x_range, y_range, z_range, angle_range)

After I run this, if I more or less like the random cloud that was generated, I stretch the whole thing out manually with the scale tool till it looks more aesthetically cloud like to me.

I also am trying another approach where I attempt to apply perlin noise to a sphere, but it is still a work in progress right now.

j_jones

Since all your spheres are convex, and assuming you have built them to shape the cloud, you could follow a brute-force method (i.e. not the fastest…).

All you do below is between a model.start_operation and model.commit_operation

  1. Create an empty Master group. This will be your future cloud
  2. Create each sphere as a group in this Master group and explode it
  3. Do an intersect_with to cut all the messy faces
  4. grep all the faces
  5. for each face, follow the following approach:
  • Construct the oriented line from its center along its normal the center (line = [bounds.center, face.normal]
  • Compute the intersection of the line with the plane of all other faces, that is (ptinter = Geom.intersect_line_plane(line, other_face.plane)).
  • If you find an intersection, check first if the vector from center of the face to the intersection point has the same direction as the face normal (ignore others). The test is roughly center.vector_to(ptinter) % face.normal > 0
  • check also that you intersect the other face via its backface, because the cloud itself may be concave. So, the test is center.vector_to(ptinter) % other_face.normal > 0
  • As soon as you find a valid intersection, delete the face.
  1. At the end of the process, you should be left with faces forming the convex hull of the cloud, enclosed in the Master group.

The main issue is the quality of the intersection, since Sketchup is sometimes missing intersections.

Also, as the doc on intersect_with is quite limited, you could use the following, assuming

  • your Master group is g
  • eeg = g.entities its Entities context
  • t = g.transformation is the transformation of the group

then
eeg.intersect_with(false, t, eeg, t, eeg, false, eeg.to_a)

2 Likes

Thank you @Fredo6 this sounds like what I need. I’m going to give it a try!

-j_jones

Hi @Fredo6, Welp, I tried to implement your instructions, but I think the part where it has to delete faces is just too much for my poor little mac. Even with a cloud of only two spheres, it hung and hung on that part before finally producing this funny result. And swallowed all the print statements to boot.

Maybe I implemented it wrong, or maybe it’s just too n^2 for my machine, I’m not sure.

Here’s my modified script in which I tried to implement what you suggested.

Everything goes great until the delete faces part at the end.

module Cloud

  def self.create_color(color, alpha, i)
    model = Sketchup.active_model
    entities = model.active_entities
    material = model.materials.add("Cloud Face #{i}")
    material.color = color
    material.alpha = alpha
    return material
  end # end create_color
  
  def self.create_ovoid_sphere(sphere, min_rand, max_rand)
    cpt = sphere.bounds.center

    x = rand(min_rand..max_rand)
    y = rand(min_rand..max_rand)
    z = rand(min_rand..max_rand)
    scale = Geom::Transformation.scaling(cpt, x, y, z)
    sphere.transform!(scale)
    return sphere
  end # end create_ovoid_sphere

  def self.create_sphere(entities, center, radius, material)
    #print "create_sphere"
    model = Sketchup.active_model
    group = entities.add_group
    g_entities = group.entities
    model.start_operation("create_sphere",true,false,true)
    
    circle = g_entities.add_circle(center, Z_AXIS, radius)
    circle_face = g_entities.add_face(circle)
    circle_face.material = material
    circle_face.back_material = material

    path = g_entities.add_circle(center, X_AXIS, radius + 1)
    circle_face.followme(path)
    g_entities.erase_entities path
    
    model.commit_operation
    model.active_view.refresh

    return group
  end # end create_sphere
  
  def self.displace_sphere(sphere, x_range, y_range, z_range, angle_range)
    cpt = sphere.bounds.center
    x = rand(-x_range..x_range)
    y = rand(-y_range..y_range)
    z = rand(-z_range..z_range)
    center = [x,y,z]
    angle = rand((90-angle_range)..90+angle_range)
  
    x_rotate_x = Geom::Transformation.rotation(ORIGIN, X_AXIS, angle.degrees)
    x_rotate_y = Geom::Transformation.rotation(ORIGIN, Y_AXIS, angle.degrees)
    x_rotate_z = Geom::Transformation.rotation(ORIGIN, Z_AXIS, angle.degrees)
    x_point = Geom::Transformation.new(center)

    sphere.transform!(x_rotate_z * x_rotate_x * x_rotate_y)
    sphere.transform!(x_point)
    return sphere
  end # end displace_sphere

  def self.create_cloud(num_spheres, min_radius, max_radius, min_rand, max_rand, 
                          x_range, y_range, z_range, angle_range)
    print "create_cloud"
    model = Sketchup.active_model
    entities = model.active_entities
    master_group = entities.add_group
    m_entities = master_group.entities

    model.start_operation("create_cloud",true,false,true)
    
    color = Sketchup::Color.new(255, 255, 255)
    material = self.create_color(color, 0.25, 1)

    num_spheres.times do |i|
      x = rand(min_rand..max_rand)
      y = rand(min_rand..max_rand)
      z = rand(min_rand..max_rand)
  
      radius = rand(min_radius..max_radius)
      sphere = self.create_sphere(m_entities, [x,y,z], radius, material)
      sphere = self.create_ovoid_sphere(sphere, 20, 40)
      sphere = self.displace_sphere(sphere, x_range, y_range, z_range, angle_range)
      pid = sphere.persistent_id
      eid = sphere.entityID
      thing1 = model.find_entity_by_id(pid)
      thing2 = model.find_entity_by_id(eid)
      print "thing1:", thing1
      print "thing2:", thing2
      sphere.explode
      thing1 = model.find_entity_by_id(pid)
      thing2 = model.find_entity_by_id(eid)
      print "thing1:", thing1
      print "thing2:", thing2
      
    end
    model.commit_operation
    Sketchup.active_model.active_view.zoom_extents
    return master_group
  end # end create_cloud
  
  def self.find_faces_to_delete(entity, other_entities, distance)
    print "find_faces_to_delete"
    model = Sketchup.active_model
    entities = model.active_entities

    extent = entity.bounds
    ctr = extent.center
    norm = entity.normal 
    line = [ ctr, ctr.offset(norm, distance) ]
    other_entities.each { |e|
      if e.deleted?
        print "skipping deleted face", e
        next
      end
      
      if e.is_a?(Sketchup::Face)
        other_face = e
        ptinter = Geom.intersect_line_plane(line, other_face.plane)
        if ptinter
          v = ctr.vector_to(ptinter)
          if v % other_face.normal > 0
            print "found a face to delete!", other_face
            entities.erase_entities([e])
          end
        end
      end
    }
  end
  
  def self.find_deletable_faces(cloud_group)
    model = Sketchup.active_model
    model.start_operation("find deletable faces",true,false,true)
    print "find things to delete"    
    entities = cloud_group.entities
    print "number of entities to process:", entities.length
    entities.each { | entity |
      print "entity:", entity
      if entity.is_a?(Sketchup::Face)
        self.find_faces_to_delete(entity, entities, 100)
      end
    }
    
    model.active_view.refresh
    model.commit_operation
    return entities_to_delete
  end
  
  def self.intersections(cloud_group)
    print "intersections"
    model = Sketchup.active_model
    model.start_operation("intersect",true,false,true)
    eeg = cloud_group.entities
    t = Geom::Transformation.new
    t2 = Geom::Transformation.new
    eeg.intersect_with(false, t, eeg, t2, false, eeg.to_a)
    print "done intersecting entities"
    model.active_view.refresh
    model.commit_operation
  end
end 

num_spheres = 2
min_radius = 15.0
max_radius = 40.0
min_rand = 1
max_rand = 40

x_range = 750
y_range = 750 
z_range = 750
angle_range = 20

cloud_group = Cloud.create_cloud(num_spheres, min_radius, max_radius, min_rand, max_rand,  x_range, y_range, z_range, angle_range)
  
Cloud.intersections(cloud_group)

Cloud.find_deletable_faces(cloud_group)

I wonder if there’s a way to do it with some kind of ray tracing where you only preserve surfaces that the sun hits or something. I don’t know. It’s probably too much for my machine as well!

Thank you
-j_jones

As usual, an algorithm is always more complex than anticipated and there are ‘details’.

I’ll have a closer look and come back…

1 Like

As said, there are a few additional considerations on the algorithm, mainly:

  1. We need to add, explode and intersect one sphere at a time. Doing so, it allows then to just count the number of intersections. If an odd number, then we mark the face for erasing. So, you first create the random spheres and keep each of them as a group, and then do the following process:
	for i in 0..nb_spheres-1
		sphere = lst_spheres[i]

		#Explode the sphere
		sphere.explode
		
		#Skip when there is only sphere in the cloud
		next if i == 0

		#Self intersect the cloud wit the new sphere
		@cloud_entities.intersect_with(false, @tr_id, @cloud_entities, @tr_id, false, @cloud_entities.to_a)
		
		#Erase the inside faces
		trim_faces
	end

  1. It is important to find a starting point which is INSIDE the face (i.e. not on vertex or edge). The method is to take a triangle of the face triangulation and compute its center. Normally, the triangulation of the face is already computed by Sketchup, so it should be fast enough. However, it may fail when the face is very tiny. In which case, the best is to ignore the face and to hope it will be discarded by another face (or to generate another cloud, since it is never good to have tiny faces in a model).
#Find a point which is on the face, but not on its vertices or edges
def find_center_on_face(face)
	mesh = face.mesh
	pts = mesh.points
	for ipoly in 0..mesh.polygons.length-1
		tri = mesh.polygons[ipoly].collect { |i| pts[i.abs-1] }
		ptmid = Geom.linear_combination(0.5, tri[1], 0.5, tri[2])
		center = Geom.linear_combination(0.5, tri[0], 0.5, ptmid)
		return center if face.classify_point(center) == Sketchup::Face::PointInside
	end	
	
	#Probably a very tiny face
	@error = 'Tiny face (no center found)'
	nil
end

  1. The trimming of the internal faces is based on counting the number of intersections of the oriented ray starting from the inside of the face along its normal. If the number is odd, then the face should be erased. However, you must NOT erase it immediately, but at the end of the process. Note that the erasing of faces may leave some standalone edges. The simplest is to detect them and erase them.

There is another small ‘detail’: if the ray encounters another face at a vertex or an edge, we must count it ONCE.

#Trim the faces which are inside the cloud
def trim_faces
	#List of faces in the group
	lst_faces = @cloud_entities.grep(Sketchup::Face)

	#Loop on each face to determine if it is part of the hull of the cloud
	lst_faces_to_erase = []
	lst_faces.each do |face|
	
		#Point on face: we must make sure that the center if INSIDE the face
		center = find_center_on_face(face)
		next unless center	#Hope it will be caught by other faces

		#Oriented line for intersection
		normal = face.normal
		line = [center, normal]

		#Build the list of intersection points: 
		#  - Retain only those which are in the direction of the normal
		#  - Make sure that the intersection point is WITHIN the other face
		nb_inter = 0
		hsh_faces_at_edge_or_vertex = {}
		lst_faces.each do |other_face|
			#Skip the faces which have been met at a vertex or an edge
			next if face == other_face || hsh_faces_at_edge_or_vertex[other_face.entityID]
			
			#Intersection point. We keep only the ones on the oriented ray
			ptinter = Geom.intersect_line_plane(line, other_face.plane)
			next unless ptinter && center.vector_to(ptinter) % normal > 0
			
			#Make sure that the intersection point is located on the other face
			#If on a vertex or an edge, we count it only once
			case other_face.classify_point(ptinter)
			when Sketchup::Face::PointOutside, Sketchup::Face::PointNotOnPlane, Sketchup::Face::PointUnknown
				next
			when Sketchup::Face::PointInside
				nb_inter += 1 
			when Sketchup::Face::PointOnVertex
				vx = other_face.vertices.find { |vx| vx.position == ptinter}
				vx.faces.each { |f| hsh_faces_at_edge_or_vertex[f.entityID] = true } if vx
				nb_inter += 1 
			when Sketchup::Face::PointOnEdge
				edge = other_face.edges.find { |ed| ptinter.on_line?([ed.start.position, ed.end.position]) }
				edge.faces.each { |f| hsh_faces_at_edge_or_vertex[f.entityID] = true } if edge
				nb_inter += 1 
			end	
		end
		
		#Eliminate the face if there are an odd number of intersections
		lst_faces_to_erase.push face if nb_inter.modulo(2) == 1
	end	
	
	#Erase the faces
	@cloud_entities.erase_entities lst_faces_to_erase
	
	#Eliminate lonely edges if any
	lst_erase_edges = @cloud_entities.grep(Sketchup::Edge).find_all { |edge| edge.faces.length == 0 }
	@cloud_entities.erase_entities lst_erase_edges unless lst_erase_edges.empty?
end

I suggest you paint the faces and edges at the end, when the cloud shell is generated. You will have less faces.

At the end of the process, the cloud should get the cloud shell as a solid group.



I have other remarks and suggestions, which I will send you in private message.
2 Likes

And there is indeed a faster method, using the outer_shell method of the Sketchup API.

	#Initiate the cloud with the first sphere and progressively add other spheres by computing their outer shell with the cloud
	@cloud_group = lst_spheres[0]
	for i in 1..nb_spheres-1
		@cloud_group = @cloud_group.outer_shell(lst_spheres[i])
	end
1 Like

The script you sent is amazingly fast, I’m quite astonished! I’m going to study it and hopefully improve my ruby sketchup skills thereby!

Again, many thanks!
-j_jones