[Closed] Convex Hull Script

Very cool not sure where I would even start with something like this.

too bad its an encrypted script, I would love to learn about the algorithm to make this work

Yeah, that is very cool

They had a script like that at Bungie that did the same thing. Not sure how to go about something like that either… : \

Yea, well, sorry for the encryption… It’s not because i am sort of protective about the code, but rather embarrassed about how dirty i wrote it… I had to implement some rather stupid hacks as i don’t really know how to fix some of the math behind it. In the end all i did was porting the giftwrap algorithm of this code i found online to maxscript:

Convex Hull Algorithms

I did the script for the same reason: To understand the algorithm behind it, which i sorta accomplished. And well, why hide it, maybe it does somebody else some good too But if you’re really interested in my maxscript solution, drop me a line… I just don’t think it’s that much of a deal.

nice one,
i personally would go and shoot rays from vert to vert and if nothing intersected the ray collect that pair (of verts)(for later edges) and then form faces from those :wip:

edit: thinking about it collecting groups of 3 would be smarter

after that to make it more gameFriendly i guess id loop through the edges and get their neighboring faces, get their normals and if their angle diff (acos(dot face1Normal face2Normal)) was smaller than some value collect them to be removed, including their verts of course

but thats just my hack

Nicely done! I worked on 2D ‘gift wrapping’ code last year, and that was tough enough for my teeney little brain… I looked briefly at 3D, but seeing as i needed mine to run in as near real time as possible, it just wasn’t going to be an option… In programming, as with so many things in life… You’re your own worst critic

Hi, i have readed the http://www.cse.unsw.edu.au/~lambert/java/3d/quickhull.html and try to do the same thing into maxscript but is very slow and with a lot of bugs… can someone tell me if exist a dll library to implement it via dotnet ?

escapeEnable = true
 fn QuickHull vertices =
 (
 	/* By johnwhile */
	/* check no-colinear and other.... */
 	if vertices.count<3 do return undefined
 	if vertices.count<4 do return mesh faces:#([1,2,3]) vertices:vertices
 	/*  inizialize double triangle  */
 	faceDouble = #([1,2,3],[3,2,1])
 	qhull = mesh faces:faceDouble vertices:vertices
 	convertTo qhull Editable_Poly --meshop.createPolygon have a bug, it duplicate edges
 
 	local vmark = #{4..vertices.count}
 	with undo off
 	with redraw off 
 	for iv in vmark do
 	(
 		if getProgressCancel() do return undefined
 		--format "* process vertex % *
" iv
 		vmark[iv] = FALSE
 		local vp = vertices[iv]
 		local visibleFaces = #{}
 		for iif=1 to qhull.numfaces do
 		(
 			local face = getFace qhull.mesh iif
 			local a = vertices[face.x] - vp
 			local b = vertices[face.y] - vp
 			local c = vertices[face.z] - vp
 			/* get volume size */
 			visibleFaces[iif] = (a.x * (b.y*c.z - b.z*c.y) + a.y * (b.z*c.x - b.x*c.z) + a.z * (b.x*c.y - b.y*c.x))<0.5
 		)
 		--format ">> found % visible faces
" visibleFaces.numberset
 		if visibleFaces.count>0 then
 		(
 			/* delete the face what "look" the vertex iv, but preserve isoverts to don't change internal index */
 			polyop.deleteFaces qhull visibleFaces delIsoVerts:false
 			BorderEdges = polyop.getOpenEdges qhull
 			newFaceArr = for ie in BorderEdges collect
 			(
 				/* obtein true oriented face very important , the algorithm don't converge into convex if some face are wrong oriented */
 				local adjface = polyop.getFacesUsingEdge qhull #{ie} as array
 				local face = getFace qhull.mesh adjface[1]
 				/* insert new vertex */
 				edgeverts = polyop.getVertsUsingEdge qhull #{ie}
 				local i=1 ; while i<3 and edgeverts[face[i]] do i+=1 ; face[i] = iv
 				/* invert orientation */
 				swap face.x face.z
 				#(face.x , face.y , face.z)
 			)
 			for newface in newFaceArr do polyop.createPolygon qhull newface
 			--format ">> build % faces
" newFaceArr.count
 		)
 	)
 	update qhull
 	qhull
 )
 
 (
 delete objects
 clearListener()
 vertices = for i=1 to 50 collect random [-10,-10,-10] [10,10,10]
 st = timestamp()
 qhullMesh = QuickHull vertices
 format "> QuickHull complete in % ms for % vertices
" (timestamp()-st) vertices.count
 qhullMesh.vertexticks = true
 )

http://blog.wolfire.com/2012/01/Overgrowth-a163-video-changelog

…???