Skip to content

mesh -- Meshes and discretised objects

Topology

A lot of similarities exists between these classes, because many of their methods are topologically generic to every dimension. They are often implemented for specific mesh For convenience, there is aliases to these classes highlighting their topology genericity

  • Mesh0 (alias to Wire) mesh with inner dimension 0 (simplices are points)
  • Mesh1 (alias to Web) mesh with inner dimension 1 (simplices are edges)
  • Mesh2 (alias to Mesh) mesh with inner dimension 2 (simplices are triangles)

naming:

  • a mesh outer dimension is the dimension of the space its points belong to. for vec3 it is 3. In madcad, all meshes have outer dimension 3
  • a mesh inner dimension is the dimension of the space of its simplices. for a line it is 1 because 1 scalar is sufficient to interpolate over a line

Architecture

The data structures defined here are just containers, they do not intend a specific usage of the geometries as it can be with halfedges, binary trees, etc. The data structures here intend to store efficiently the mesh information and allow basic data operation like concatenation, find-replace, and so.

The following considerations are common to the classes here:

  • the classes are just wrapping references to data buffers they do not own exclusively their content, nor it is forbidden to hack into their content (it is just lists, you can append, insert, copy, etc what you want). As so, it is almost no cost to shallow-copy a mesh, or to create it from existing buffers without computation nor data copy. It is very common that several meshes are sharing the same buffer of points, faces, groups ...

  • the management of the container's data ownership is left to the user the user has to copy the data explicitely when necessary to unlink containers sharing the same buffers. To allow the user to do so, the madcad functions observe the following rules: + the container's methods that modify a small portion of its data does so in-place. when they do not return a particular value, they do return 'self' (lowercase, meaning the current container instance) + the container's methods that modify a big amount of its data do return a new container instance, sharing the untouched buffers with the current one and duplicating the altered data. They do return a new instance of 'Self' (uppercase, meaning it is the current container type)

  • the methods defined for containers are only simple and very general operations. The more complex operations are left to separated functions. Most of the time, container methods are for data/buffers management, connectivity operations, and mathematical caracteristics extractions (like normals, surface, volume, etc)

See Mesh.own() for instance.

Inner identification

The containers are provided with an inner-identification system allowing to keep track of portion of geometries in the mesh across operations applies on. This is permitted by their field tracks and groups. Each simplex (point, edge or face depending of the mesh inner dimension) is associated to a group number referencing a group definition in the group list.

Groups definitions can be anything, but more often is a dictionnary (containing the group attributes we can filter on), or simply None. To easily extract portions of one mesh, its is straightforward to associate keys to the interesting groups using .qualify(key) and then select groups calling .group(key) to retreive it later. groups can also be filtered manually.

See Mesh.qualify() for more details

Conversions

mesh(*arg, resolution=None)

Build a Mesh object from supported objects:

:mesh: return it with no copy :primitive: call its .mesh method and convert the result to web :iterable: convert each element to web and join them

Source code in madcad/mesh/conversions.py 
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
def mesh(*arg, resolution=None) -> Mesh:
	''' Build a Mesh object from supported objects:

		:mesh:              return it with no copy
		:primitive:         call its ``.mesh`` method and convert the result to web
		:iterable:          convert each element to web and join them
	'''
	if not arg:	
		raise TypeError('mesh takes at least one argument')
	if len(arg) == 1:	
		arg = arg[0]
	if isinstance(arg, Mesh):		
		return arg
	elif hasattr(arg, 'mesh'):
		return mesh(arg.mesh(resolution=resolution))
	elif hasattr(arg, '__iter__'):
		pool = Mesh()
		for primitive in arg:
			pool += mesh(primitive, resolution=resolution)
		pool.mergeclose()
		return pool
	else:
		raise TypeError('incompatible data type for Web creation')

web(*arg, resolution=None)

Build a Web object from supported objects:

:web: return it with no copy :wire: reference points and generate edge couples :primitive: call its .mesh method and convert the result to web :iterable: convert each element to web and join them :list of vec3: reference it and generate trivial indices :iterable of vec3: get points and generate trivial indices

Source code in madcad/mesh/conversions.py 
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
def web(*arg, resolution=None) -> Web:
	''' Build a Web object from supported objects:

		:web:               return it with no copy
		:wire:              reference points and generate edge couples
		:primitive:         call its ``.mesh`` method and convert the result to web
		:iterable:          convert each element to web and join them
		:list of vec3:      reference it and generate trivial indices
		:iterable of vec3:  get points and generate trivial indices
	'''
	if not arg:	
		raise TypeError('web takes at least one argument')
	if len(arg) == 1:	
		arg = arg[0]
	if isinstance(arg, Web):		
		return arg
	elif isinstance(arg, Wire):	
		return Web(
				arg.points, 
				arg.edges(), 
				arg.tracks[:-1] if arg.tracks else None, 
				groups=arg.groups,
				)
	elif hasattr(arg, 'mesh'):
		return web(arg.mesh(resolution=resolution))
	elif isinstance(arg, (typedlist,list,tuple)) and isinstance(arg[0], vec3):
		return Web(arg, [(i,i+1) for i in range(len(arg)-1)])
	elif hasattr(arg, '__iter__'):
		pool = Web()
		for primitive in arg:
			pool += web(primitive, resolution=resolution)
		pool.mergeclose()
		return pool
	else:
		raise TypeError('incompatible data type for Web creation')

wire(*arg, resolution=None)

Build a Wire object from the other compatible types. Supported types are:

:wire: return it with no copy :web: find the edges to joint, keep the same point buffer :primitive: call its .mesh method and convert the result to wire :iterable: convert each element to Wire and joint them :list of vec3: reference it and put trivial indices :iterable of vec3: create internal point list from it, and put trivial indices

Source code in madcad/mesh/conversions.py 
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
def wire(*arg, resolution=None) -> Wire:
	''' Build a Wire object from the other compatible types.
		Supported types are:

		:wire:              return it with no copy
		:web:               find the edges to joint, keep the same point buffer
		:primitive:         call its ``.mesh`` method and convert the result to wire
		:iterable:          convert each element to Wire and joint them
		:list of vec3:      reference it and put trivial indices
		:iterable of vec3:  create internal point list from it, and put trivial indices
	'''
	if not arg:	
		raise TypeError('wire takes at least one argument')
	if len(arg) == 1:	
		arg = arg[0]
	if isinstance(arg, Wire):		
		return arg
	elif isinstance(arg, Web):
		indices = suites(arg.edges)
		if len(indices) > 1:	raise ValueError('the given web has junctions or is discontinuous')
		return Wire(arg.points, indices[0], groups=[None])	# TODO: find a way to get the groups from the Web edges through suites or not
	elif hasattr(arg, 'mesh'):
		return wire(arg.mesh(resolution=resolution))
	elif isinstance(arg, vec3):
		return Wire([arg])
	elif isinstance(arg, (typedlist,list,tuple)):
		try:
			return Wire(arg, groups=[None])
		except TypeError:
			pass
	if hasattr(arg, '__iter__'):
		pool = Wire()
		for primitive in arg:
			pool += wire(primitive, resolution=resolution)
		pool.mergeclose()
		return pool
	else:
		raise TypeError('incompatible data type for Wire creation')

typedlist_to_numpy(array, dtype)

Convert a typedlist to a numpy.ndarray with the given dtype, if the conversion is possible term to term

Source code in madcad/mesh/container.py 
267
268
269
270
271
272
273
def typedlist_to_numpy(array: 'typedlist', dtype) -> np.ndarray:
	''' Convert a typedlist to a numpy.ndarray with the given dtype, if the conversion is possible term to term '''
	tmp = np.asarray(array)
	if tmp.dtype.fields:
		return rfn.structured_to_unstructured(tmp, dtype)
	else:
		return tmp.astype(dtype)

numpy_to_typedlist(array, dtype)

Convert a numpy.ndarray into a typedlist with the given dtype, if the conversion is possible term to term

Source code in madcad/mesh/container.py 
259
260
261
262
263
264
265
def numpy_to_typedlist(array: np.ndarray, dtype) -> typedlist:
	''' Convert a numpy.ndarray into a typedlist with the given dtype, if the conversion is possible term to term '''
	ndtype = np.array(typedlist(dtype)).dtype
	if ndtype.fields:
		return typedlist(rfn.unstructured_to_structured(array).astype(ndtype, copy=False), dtype)
	else:
		return typedlist(array.astype(ndtype, copy=False), dtype)

ensure_typedlist(obj, dtype)

Return a typedlist with the given dtype, create it from whatever is in obj if needed

Source code in madcad/mesh/container.py 
275
276
277
278
279
280
def ensure_typedlist(obj, dtype):
	''' Return a typedlist with the given dtype, create it from whatever is in obj if needed '''
	if isinstance(obj, typedlist) and obj.dtype == dtype:
		return obj
	else:
		return typedlist(obj, dtype)

Misc

MeshError

Bases: Exception

Inconsistent data in mesh

line_simplification(web, prec=None)

return a dictionnary of merges to simplify edges when there is points aligned.

This function sort the points to remove on the height of the triangle with adjacent points. The returned dictionnary is guaranteed without cycles

Source code in madcad/mesh/__init__.py 
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
def line_simplification(web, prec=None):
	''' return a dictionnary of merges to simplify edges when there is points aligned.

		This function sort the points to remove on the height of the triangle with adjacent points.
		The returned dictionnary is guaranteed without cycles
	'''
	if not prec:	prec = web.precision()
	pts = web.points

	# simplify points when it forms triangles with too small height
	merges = {}
	def process(a,b,c):
		# merge with current merge point if height is not sufficient, use it as new merge point
		height = length(noproject(pts[c]-pts[b], pts[c]-pts[a]))
		if height > prec:
			#scn3D.add(text.Text(pts[b], str(height), 8, (1,0,1), align=('left', 'center')))
			return b
		else:
			merges[b] = a
			return a

	for k,line in enumerate(suites(web.edges, oriented=False)):
		s = line[0]
		for i in range(2, len(line)):
			s = process(s, line[i-1], line[i])
		if line[0]==line[-1]: process(s, line[0], line[1])

	# remove redundancies in merges (there can't be loops in merges)
	for k,v in merges.items():
		while v in merges and merges[v] != v:
			merges[k] = v = merges[v]

	return merges

mesh_distance(m0, m1)

minimal distance between elements of meshes

The result is a tuple (distance, primitive from m0, primitive from m1). primitive can be:

    :int:                           index of the closest point
    :(int,int):                     indices of the closest edge
    :(int,int,int):         indices of the closest triangle
Source code in madcad/mesh/__init__.py 
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
def mesh_distance(m0, m1) -> '(d, prim0, prim1)':
	''' minimal distance between elements of meshes

		The result is a tuple `(distance, primitive from m0, primitive from m1)`.
		`primitive` can be:

			:int:				index of the closest point
			:(int,int):			indices of the closest edge
			:(int,int,int): 	indices of the closest triangle
	'''
	# compute distance from each points of m to o
	def analyse(m, o):
		# get an iterator over actually used points only
		if isinstance(m, Mesh):
			usage = [False]*len(m.points)
			for f in m.faces:
				for p in f:	usage[p] = True
			it = (i for i,u in enumerate(usage) if u)
		elif isinstance(m, Web):
			usage = [False]*len(m.points)
			for e in m.edges:
				for p in e:	usage[p] = True
			it = (i for i,u in enumerate(usage) if u)
		elif isinstance(m, Wire):
			it = m.indices
		elif isinstance(m, vec3):
			return (*distance2_pm(m, o), 0)
		# comfront to the mesh
		return min((
				(*distance2_pm(m.points[i], o), i)
				for i in it),
				key=lambda t:t[0])
	# symetrical evaluation
	d0 = analyse(m0, m1)
	d1 = analyse(m1, m0)
	if d0[0] < d1[0]:	return (sqrt(d0[0]), d0[2], d0[1])
	else:				return (sqrt(d1[0]), d1[1], d1[2])

distance2_pm(point, mesh)

squared distance from a point to a mesh

Source code in madcad/mesh/__init__.py 
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
def distance2_pm(point, mesh) -> '(d, prim)':
	''' squared distance from a point to a mesh
	'''
	score = inf
	best = None
	if isinstance(mesh, Mesh):
		for face in mesh.faces:
			f = mesh.facepoints(face)
			n = cross(f[1]-f[0], f[2]-f[0])
			if not n:	continue
			# check if closer to the triangle's edges than to the triangle plane
			plane = True
			for i in range(3):
				d = f[i-1]-f[i-2]
				if dot(cross(n, d), point-f[i-2]) < 0:
					x = dot(point-f[i-2], d) / length2(d)
					# check if closer to the edge points than to the edge axis
					if x < 0:	dist, candidate = distance2(point, f[i-2]), face[i-2]
					elif x > 1:	dist, candidate = distance2(point, f[i-1]), face[i-1]
					else:		dist, candidate = length2(noproject(point - f[i-2], d)), (face[i-2], face[i-1])
					plane = False
					break
			if plane:
				dist, candidate = dot(point-f[0], n) **2 / length2(n), face
			if dist < score:
				best, score = candidate, dist
	elif isinstance(mesh, (Web,Wire)):
		if isinstance(mesh, Web):	edges = mesh.edges
		else:						edges = mesh.edges()
		for edge in edges:
			e = mesh.edgepoints(edge)
			d = e[1]-e[0]
			x = dot(point - e[0], d) / length2(d)
			# check if closer to the edge points than to the edge axis
			if x < 0:	dist, candidate = distance2(point, e[0]), edge[0]
			elif x > 1:	dist, candidate = distance2(point, e[1]), edge[1]
			else:		dist, candidate = length2(noproject(point - e[0], d)), edge
			if dist < score:
				best, score = candidate, dist
	elif isinstance(mesh, vec3):
		return distance2(point, mesh), 0
	else:
		raise TypeError('cannot evaluate distance from vec3 to {}'.format(type(mesh)))
	return score, best