[Closed] How to create a surface starting from a cloud of points ?

other than using vertex snap, and making the polygons yourself, I don’t think you have much chance of a ‘clean’ result.

You could use metaparticles – I don’t think this is what you’re after, it’s rather hard to build faces from vertexes unless you know what order they go in.

prettyPixel,

in this thread: Delauney triangulation
is a link to a ‘plain text’ explanation: http://astronomy.swin.edu.au/~pbourke/

search for ‘delauney’.

maybe it helps.

Georg

hey thanks guys !
I read only now your 3 answers.

That is the problem which I encounter.
My method does not always generate correct surfaces.

Thanks for this useful informations. At this time my method is not based on an approximation. I really want to use each vertex (because each point is really essential for me). Nevertheless this approach is interesting.

Thanks Georg. I am going to read this method now…

Here is my version to calculate a surface.
Of course, I did not yet use your ideas.
It is not an estimatition, but it sometimes that generates errors.
Certain points can be ignored.

struct flagObj
	(
	obj,
	flagVerts=#{1..obj.numVerts},
	flagEdges=#{},
	flagFaces=#{}
	)

fn createVertexCloud csize csegs =
	(
	obj=geoSphere radius:csize baseType:1 segs:csegs
	cscale=csize/2.2 ; cstr=csize/4.0
	addmodifier obj (noiseModifier scale:cscale strength:[cstr,cstr,cstr] )
	convertToPoly obj
	polyOp.deleteFaces obj #{1..obj.numFaces} delIsoVerts:false
	--return
	obj
	)

fn createFirstFace theObj =
	(
	obj=theObj.obj
	-- vertex 1
	v1=1
	v1Pos=polyOp.getVert obj v1
	theObj.flagVerts[v1]=false
	-- vertex 2
	objNumVerts=obj.numVerts
	theCenter=obj.center
	theVector=v1Pos-theCenter
	theMax=-1.0 ; theMaxIdx=0
	for v=1 to objNumVerts where theObj.flagVerts[v] do
		(
		currentPos=polyOp.getVert obj v
		currentVector=currentPos-theCenter
		currentDot=(dot (normalize theVector) (normalize currentVector))+1.0
		if currentDot>theMax do ( theMax=currentDot ; theMaxIdx=v )
		)
	v2=theMaxIdx
	v2Pos=polyOp.getVert obj v2
	theObj.flagVerts[v2]=false
	-- vertex 3
	midEdge=(v1Pos+v2Pos)/2.0
	edgeVector=v2Pos-v1Pos
	theVector=midEdge-theCenter
	theMax=-1.0 ; theMaxIdx=0
	for v=1 to objNumVerts where theObj.flagVerts[v] do
		(
		currentPos=polyOp.getVert obj v
		currentVector=currentPos-theCenter
		currentVectorP=currentPos-midEdge
		currentDot=(dot (normalize theVector) (normalize currentVector))+1.0
		currentDotPerp=1.0-(abs( dot (normalize edgeVector) (normalize currentVectorP) ))
		currentDot*=currentDotPerp
		if currentDot>theMax do ( theMax=currentDot ; theMaxIdx=v )
		)
	v3=theMaxIdx
	v3Pos=polyOp.getVert obj v3
	theObj.flagVerts[v3]=false
	-- face 1
	faceNormal=normalize ( cross (v2Pos-v1Pos) (v3Pos-v1Pos) )
	pseudoFaceNormal=normalize ( ((v1Pos+v2Pos+v3Pos)/3.0)-theCenter )
	if (dot faceNormal pseudoFaceNormal)>0.0 then newFace=polyOp.createPolygon obj #(v1,v2,v3) else newFace=polyOp.createPolygon obj #(v1,v3,v2)
	theObj.flagFaces=#{1}
	theObj.flagEdges=#{1..3}
	--return
	OK
	)

fn getFirstItem theBitArray = ( for i in theBitArray do return i )

fn getProxyVert theObj theCenter v1 v2 v3 face =
	(
	obj=theObj.obj
	st1=theObj.flagVerts[v1]; theObj.flagVerts[v1]=false
	st2=theObj.flagVerts[v2]; theObj.flagVerts[v2]=false
	st3=theObj.flagVerts[v3]; theObj.flagVerts[v3]=false	
	-- initialisation
	faceNormal=polyOp.getFaceNormal obj face
	v1Pos=polyOp.getVert obj v1
	v2Pos=polyOp.getVert obj v2
	theVector=v2Pos-v1Pos
	midEdge=(v1Pos+v2Pos)/2.0
	midEdgePerpVector=normalize ( cross theVector faceNormal )
	firstActiveVert=getFirstItem theObj.flagVerts
	currentPos=polyOp.getVert obj firstActiveVert
	vector2MidEdge=midEdge-theCenter
	currentVector=currentPos-theCenter
	dAngle=acos (dot (normalize vector2MidEdge) (normalize currentVector))
	currentMidEdgeVector=currentPos-midEdge
	dotP=dot (normalize midEdgePerpVector) (normalize currentMidEdgeVector)
	dFactor=1.0-((dotP+1.0)/2.0)
	dirInfluence=2.0
	dAngle=dAngle+(dAngle*dFactor*dirInfluence)
	dmin=dAngle
	dminIdx=firstActiveVert
	-- find the nearest
	theObjFlagVerts=theObj.flagVerts
	for v in theObjFlagVerts do
		(
		currentPos=polyOp.getVert obj v
		currentVector=currentPos-theCenter
		dAngle=acos (dot (normalize vector2MidEdge) (normalize currentVector) )
		currentMidEdgeVector=currentPos-midEdge
		dotP=dot (normalize midEdgePerpVector) (normalize currentMidEdgeVector)
		dFactor=1.0-((dotP+1.0)/2.0)
		dAngle=dAngle+(dAngle*dFactor*dirInfluence)
		if dAngle<dmin do ( dmin=dAngle ; dminIdx=v )
		)
	theObj.flagVerts[v1]=st1
	theObj.flagVerts[v2]=st2
	theObj.flagVerts[v3]=st3
	-- return
	dminIdx
	)

fn notInArray theArray theValues = ( for v in theValues where (findItem theArray v)==0 collect v )

fn getFirstEdge theObj face =
	(
	obj=theObj.obj
	edgesOfFace=polyOp.getFaceEdges obj face
	filterEdgesOfFace=for e in edgesOfFace where theObj.flagEdges[e] collect e
	if filterEdgesOfFace.count!=0
		then ( for e in filterEdgesOfFace do return e )
		else (
			theObj.flagFaces[face]=false
			0
			)	
	)

fn getFirstFace theObj =
	(
	theObjFlagFaces=theObj.flagFaces
	if theObjFlagFaces.numberSet!=0
		then ( for f in theObjFlagFaces do return f )
		else 0
	)

fn createSurface obj =
	(
	theObj=flagObj obj
	createFirstFace theObj
	errorLevel=0
	securityCountF=0
	maxCountF=20
	maxCountE=6
	while (thisFace=getFirstFace theObj )!=0 do
		(
		securityCountF+=1 ; if securityCountF>maxCountF do (format "+++ securityCountF
" ; exit)
		securityCountE=0
		theFaceVerts=polyOp.getFaceVerts theObj.obj thisFace
		while (thisEdge=getFirstEdge theObj thisFace)!=0 do
			(
			securityCountE+=1 ; if securityCountE>maxCountE do (format "+++ securityCountE
" ; exit)
			theFaceVerts=polyOp.getFaceVerts theObj.obj thisFace
			theEdgeVerts=polyOp.getEdgeVerts theObj.obj thisEdge
			difArray=notInArray theEdgeVerts theFaceVerts
			newVert=getProxyVert theObj theObj.obj.center theEdgeVerts[1] theEdgeVerts[2] difArray[1] thisFace
			if newVert!=0
				then (
					newFace=polyOp.createPolygon theObj.obj #(theEdgeVerts[2],theEdgeVerts[1],newVert)
					if newFace!=undefined then
						(
						securityCountF=0
						theObj.flagFaces[newFace]=true
						theObj.flagEdges[thisEdge]=false
						edgesOfNewFace=polyOp.getFaceEdges theObj.obj newFace
						for e in edgesOfNewFace do (
								facesOfEdge=polyOp.getEdgeFaces theObj.obj e
								if facesOfEdge.count==2 then theObj.flagEdges[e]=false else theObj.flagEdges[e]=true
								)
						)
						else (
							errorLevel+=1
							theObj.flagEdges[thisEdge]=false
							)
					)--if
				else (
					errorLevel+=1
					if theObj.flagEdges.numberSet==3 then (
						the3Verts=#()
						for e in theObj.flagEdges do
							(
							vertsOfEdge=polyOp.getEdgeVerts theObj.obj e
							if findItem the3Verts vertsOfEdge[1]==0 do append the3Verts vertsOfEdge[1]
							if findItem the3Verts vertsOfEdge[2]==0 do append the3Verts vertsOfEdge[2]
							)
						if the3Verts.count==3 do
							(
							newFace=polyOp.createPolygon theObj.obj #(the3Verts[3],the3Verts[2],the3Verts[1])
							for e in theObj.flagEdges do theObj.flagEdges[e]=false
							)
						)
						else ( theObj.flagEdges[thisEdge]=false )
					)
			)--while
		)--while
	--return
	errorLevel
	)--fn

clearListener()
max modify mode
cloudObj=createVertexCloud 100.0 5
cloudObj.vertexTicks=true
max views redraw
messageBox ("ready for surface creation
click Ok to continue")
errorLevel=createSurface cloudObj
if errorLevel!=0 then messageBox ("errorLevel = "+errorLevel as string)
cloudObj.vertexTicks=false
max views redraw

Are the points equal distances from each other? like a geosphere.

Convex Hulls, I think that’s your ticket. A short summation of the brute force method:
[ol]
[li]Select 3 verts. [/li][li]Make a plane (not a plane object) out of them. [/li][li]Test each vert and see on which side of the plane they lie. [/li][li]If each vertex falls behind the plane it is convex, build the face. [/li][li]Otherwise it is probably concave so don’t build the face, choose the next 3 verts repeat until there are no more open edges (don’t test the same combination of verts again). [/li][/ol] There is a bit of maths involved here (plane from 3 points, point infront of/behind plane, etc.), but it will give you a neat, convex shape out of any point cloud. It is not, however, guaranteed that every vert will have attached faces, as some may lie inside the convex volume.

Google Convex Hulls and/or Paul Bourke.

Hope this helps.

Ouch

We should add that to the weekly scripting challenge thread

I work at present on the method of Delauney. For the moment I encounter problems during the reconstruction of long concave faces.

Thank you for explanations
Could you explain in detail how to know if a selection of faces is concave or convex ?

Pixel,

the convex hull method will check every combination of 3 vertices. In other words, it will check every possible face that you could possibly make. For each potential face, it checks to see if ALL of the other vertices not used by that face fall on one side of the face. If all the verts fall on one side, then the face you’re looking at is definitely on the outside of the object, thus it is a convex face. If some of the verts are on one side of the face-plane and some are on the other side, then this isn’t necessarily an outside face of the object, so it is not made into a face.

Therefore, this method would work perfectly well if your points were to form a sphere. However, since you are adding noise to the sphere, the convex hull method will NOT work…because probably most of the “outside” faces will not satisfy the plane-test desrcribed above, and therefore they wouldn’t be built into faces.

However, the convex hull method will PARTIALLY build what you want…and you can be guarnateed that the parts it builds will be correct. You will just have to do a lot more work to complete it.