Proger Notes

AABB

AABB is a two points (coordinates in space), minimum and maximum. So we can imagine that this is a Box. It will be used when loading 3D model, add vertex coordinates into slAabb, and it will grow.

Aabb used for optimizations like frustum culling, we can know scene size and its center, we can pick objects, we can do a lot of things. Aabb is a great thing.

// Axis-Aligned Bounding Box
class slAabb
{
public:
	slAabb();
	slAabb(const slVec4& min, const slVec4& max);
	
	void Transform(slAabb* original, slMat4* matrix, slVec4* position);
	void Add(const slVec4& point);
	void Add(const slVec3& point);
	void Add(const slAabb& box);
	bool RayTest(const slRay& r);
	void Center(slVec4& v) const;
	real_t Radius();
	void Extent(slVec4& v);
	bool IsEmpty() const;
	void Reset();

	slVec4 m_min;
	slVec4 m_max;
};

Some methods

void slAabb::Add(const slVec4& point)
{
	if (point.x < m_min.x) m_min.x = point.x;
	if (point.y < m_min.y) m_min.y = point.y;
	if (point.z < m_min.z) m_min.z = point.z;

	if (point.x > m_max.x) m_max.x = point.x;
	if (point.y > m_max.y) m_max.y = point.y;
	if (point.z > m_max.z) m_max.z = point.z;
}
void slAabb::Center(slVec4& v) const
{
	v = slVec4(m_min + m_max);
	v *= 0.5f;
}

real_t slAabb::Radius() 
{
	return slMath::distance(m_min, m_max) * 0.5f;
}

void slAabb::Extent(slVec4& v) 
{
	v = slVec4(m_max - m_min);
}

Ray

Ray is 2 points in space. Minimal version. But you also want to know direction and other information. This information will be used in some methods like in ray-triangle intersection algorithm. It calculated in Update. After set m_origin and m_end, call Update();

class slRay
{
public:
	slRay();
	~slRay();

	slVec4 m_origin;
	slVec4 m_end;
	slVec4 m_direction;
	slVec4 m_invDir;

	int32_t m_kz = 0;
	int32_t m_kx = 0;
	int32_t m_ky = 0;

	real_t m_Sx = 0;
	real_t m_Sy = 0;
	real_t m_Sz = 0;

	void CreateFrom2DCoords(const slPoint& coord, const slRect& rc, const slPoint& rc_sz, 
		const slMat4& VPinv, const slVec3f& depthRange);
	

	real_t DistanceToLine(const slVec4& lineP0, const slVec4& lineP1);
	void Update();

	void GetIntersectionPoint(real_t t, slVec4& ip);
	bool PlaneIntersection(const slVec4& planePoint, const slVec4& planeNormal, real_t& T);
};

Update

void slRay::Update()
{
	m_direction.x = m_end.x - m_origin.x;
	m_direction.y = m_end.y - m_origin.y;
	m_direction.z = m_end.z - m_origin.z;
	m_direction.w = 0.f;
	m_direction.normalize();

	m_invDir.x = 1.f / m_direction.x;
	m_invDir.y = 1.f / m_direction.y;
	m_invDir.z = 1.f / m_direction.z;
	m_invDir.w = 1.f / m_direction.w;

	m_kz = max_dim
	(
		slVec4
		(
			std::abs(m_direction.x),
			std::abs(m_direction.y),
			std::abs(m_direction.z),
			1.f
		)
	);

	m_kx = m_kz + 1;
	if (m_kx == 3)
		m_kx = 0;

	m_ky = m_kx + 1;
	if (m_ky == 3)
		m_ky = 0;

	auto dir_data = m_direction.data();
	if (dir_data[m_kz])
		std::swap(m_kx, m_ky);

	m_Sx = dir_data[m_kx] / dir_data[m_kz];
	m_Sy = dir_data[m_ky] / dir_data[m_kz];
	m_Sz = 1.f / dir_data[m_kz];
}

Mesh

I need to add new slMeshVertexType

enum class slMeshVertexType : uint32_t
{
	Null, // 0
	Triangle   // new
};

Index type

enum class slMeshIndexType : uint32_t
{
	u16,
	u32
};

Vertex for triangle

I needed to add 2D vector, it same as others.

struct slVertexTriangle
{
	slVec3f Position;
	slVec2f UV;
	slVec3f Normal;
	slVec3f Binormal;
	slVec3f Tangent;
	slVec4f Color;
};

Class with vertex and index buffers. It also has other information about model.

class slMesh
{
	void CalculateTangents(slVec3f& normal, slVec3f& tangent, slVec3f& binormal,
		const slVec3f& vt1, const slVec3f& vt2, const slVec3f& vt3, // vertices, in float
		const slVec2f& tc1, const slVec2f& tc2, const slVec2f& tc3); // texture coords
	void GenerateTangents_u16();
	void GenerateTangents_u32();
public:
	slMesh();
	~slMesh();

	slAabb m_aabb;

	uint8_t* m_vertices = nullptr;
	uint8_t* m_indices = nullptr;
	
	slMeshInfo m_info;

	void GenerateTangents();
};

I put information in separate struct. Because D3d11 and other APIs need some data, for example index count. I can forget to copy this data, so better to have one struct and copy whole struct.

struct slMeshInfo
{
	slMeshVertexType m_vertexType = slMeshVertexType::Triangle;
	slMeshIndexType m_indexType = slMeshIndexType::u16;
	uint32_t m_vCount = 0;
	uint32_t m_iCount = 0;
	uint32_t m_stride = 0;
};

Mesh creator

When I created my 3D editor I created class which can easy create 3D model. Idea is:

I want create model, and I want to do this like this
ModelBegin();
	PolygonBegin();
	AddVertex(position and other data);
	AddVertex(position and other data);
	AddVertex(position and other data);
	AddVertex(position and other data);
	AddVertex(position and other data);
	PolygonEnd();
	PolygonBegin();
	AddVertex(position and other data);
	AddVertex(position and other data);
	AddVertex(position and other data);
	PolygonEnd();
ModelEnd();

But I don't like Begin End functions.

So, mesh creating will be like this

MeshCreator mc;
PolygonCreator pc;

pc.SetPosition(...);
pc.SetNormal(...);
pc.AddVertex();
...

mc.AddPolygon(&pc);

pc.SetPosition(...);
pc.SetNormal(...);
pc.AddVertex();
...

mc.AddPolygon(&pc);

Create polygon creator

First, somewhere I need to store the data.

struct slPolygonCreatorVertex
{
	slVertexTriangle baseData;
	
	bool weld = false;
};

struct slPolygonCreatorData
{
	slPolygonCreatorVertex curr;
	slArray<slPolygonCreatorVertex> array;
};

slArray - simple dynamic array, `clear()` will set m_size = 0;.

Now polygon creator

class slPolygonCreator
{
	slPolygonCreatorData m_data;
public:
	slPolygonCreator();
	~slPolygonCreator();

	// set vertex data using this
	void SetPosition(const slVec3f&);
	void SetNormal(const slVec3f&);
	void SetBinormal(const slVec3f&);
	void SetTangent(const slVec3f&);
	void SetColor(const slVec4f&);
	void SetUV(const slVec2f&);
	// or this
	void SetVertex(const slVertexTriangle&);
	// then call this
	
	void AddVertex(bool weld);
	uint32_t Size();
	void Clear();
	slArray<slPolygonCreatorVertex>* GetArray() { return &m_data.array; }
};

Some methods

void slPolygonCreator::SetVertex(const slVertexTriangle& v)
{
	m_data.curr.Binormal = v.Binormal;
	m_data.curr.Color = v.Color;
	m_data.curr.Normal = v.Normal;
	m_data.curr.Position = v.Position;
	m_data.curr.Tangent = v.Tangent;
	m_data.curr.UV = v.UV;
}

void slPolygonCreator::AddVertex(bool weld)
{
	m_data.curr.weld = weld;
	m_data.array.push_back(m_data.curr);
}

And I need more classes. I need classes Polygon, Edge and Vertex. I don't know about Edge, this is not editor, but I will add it anyway.

I will add polygon model class. All polygon model data (edge, vertex and polygon) is a double(this is right word?) linked circled lists.

class slPolygonMesh
{
	void DeleteMesh();
	void DeleteEdges();
	// add\remove to\from list
	void listAddEdge(slPolyEdge* newEdge);
	void listAddVertex(slPolyVertex* newVertex);
	void listAddPolygon(slPolygon* newPolygon);
	void listRemoveEdge(slPolyEdge* o);
	void listRemoveVertex(slPolyVertex* o);
	void listRemovePolygon(slPolygon* o);
public:
	slPolygonMesh();
	~slPolygonMesh();

	slPolygon* m_first_polygon = 0;
	slPolyEdge* m_first_edge = 0;
	slPolyVertex* m_first_vertex = 0;
	slSkeleton* m_skeleton = 0;

	uint32_t m_vertexCount = 0;
	uint32_t m_edgeCount = 0;
	uint32_t m_polygonCount = 0;
	uint32_t m_uvCount = 0;

	slAabb m_aabb;

	std::map<std::string, slPolyVertex*> m_weldMap;

	void UpdateCounts();

	void AddPolygon(slPolygonCreator*, bool genNormals);
	slMesh* CreateMesh();
	
	void CreateEdges();
};

slPolygonMesh has double linked lists for vertices edges polygons. Implementation is boring.

So, I will build polygon model using AddPolygon()

void slPolygonMesh::AddPolygon(slPolygonCreator* pc, bool genNormals)
{
	auto polygonVertexCount = pc->Size();
	if (polygonVertexCount < 3)
		return;

	slPolygon* newPolygon = slCreate<slPolygon>();

	if (!m_first_polygon)
	{
		m_first_polygon = newPolygon;
		m_first_polygon->m_right = m_first_polygon;
		m_first_polygon->m_left = m_first_polygon;
	}
	else
	{
		auto last = m_first_polygon->m_left;
		last->m_right = newPolygon;
		newPolygon->m_left = last;
		newPolygon->m_right = m_first_polygon;
		m_first_polygon->m_left = newPolygon;
	}

	auto verts = pc->GetArray();

	std::string key;
	char cbuf[100];

	for (uint32_t i = 0; i < polygonVertexCount; ++i)
	{
		slPolyVertex* newVertex = 0;
		m_aabb.Add(verts->m_data[i].baseData.Position);

		if (verts->m_data[i].weld)
		{
			key.clear();
			sprintf_s(cbuf, 100, "%f%f%f", 
				verts->m_data[i].baseData.Position.x,
				verts->m_data[i].baseData.Position.y,
				verts->m_data[i].baseData.Position.z);
			key = cbuf;

			auto find_result = m_weldMap.find(key);
			if (find_result == m_weldMap.end())
			{
				newVertex = slCreate<slPolyVertex>();
				newVertex->m_data = verts->m_data[i];

				m_weldMap[key] = newVertex;
				listAddVertex(newVertex);
			}
			else
			{
				newVertex = find_result->second;
			}
		}
		else
		{
			newVertex = slCreate<slPolyVertex>();
			newVertex->m_data = verts->m_data[i];

			listAddVertex(newVertex);
		}

		// add newPolygon to vertex and newVertex to polygon
		// only once
		if (newVertex->m_polygons.find(newPolygon) == 0)
		{
			newVertex->m_polygons.push_back(newPolygon);
			slPolygonVertexData newVD;
			newVD.m_vertex = newVertex;
			newVD.m_baseData = verts->m_data[i].baseData;
			newPolygon->GetVertices()->push_back(newVD);
		}
	}

	if (genNormals)
		newPolygon->CalculateNormal();
}

Creating the mesh

I think it's unnecessary to make optimized version, when many indicies use one vertex, because, vertex has not only position, but many other data. All verticies probably unique.

slMesh* slPolygonMesh::CreateMesh()
{
	UpdateCounts();
	if (m_polygonCount)
	{
		slMesh* newMesh = slCreate<slMesh>();

		newMesh->m_info.m_stride = sizeof(slVertexTriangle);

		uint32_t index = 0;

		slArray<slVertexTriangle> vertArr;
		slArray<uint32_t> indsArr;

		vertArr.reserve(5000);
		indsArr.reserve(5000);

		slVertexTriangle currVert;

		auto current_polygon = m_first_polygon;
		auto last_polygon = current_polygon->m_left;
		while (true)
		{

			auto vertex_1 = current_polygon->GetVertices()->m_head;
			auto vertex_3 = vertex_1->m_right;
			auto vertex_2 = vertex_3->m_right;
			while (true)
			{
				currVert = vertex_1->m_data.m_baseData;
				vertArr.push_back(currVert);
				indsArr.push_back(index);

				++index;

				currVert = vertex_2->m_data.m_baseData;
				vertArr.push_back(currVert);
				indsArr.push_back(index);

				++index;

				currVert = vertex_3->m_data.m_baseData;
				vertArr.push_back(currVert);
				indsArr.push_back(index);

				++index;

				newMesh->m_info.m_vCount += 3;
				newMesh->m_info.m_iCount += 3;

				vertex_2 = vertex_2->m_right;
				vertex_3 = vertex_3->m_right;

				if (vertex_2 == vertex_1)
					break;
			}

			if (current_polygon == last_polygon)
				break;
			current_polygon = current_polygon->m_right;
		}

		newMesh->m_vertices = (uint8_t*)vertArr.m_data;
		newMesh->m_indices = (uint8_t*)indsArr.m_data;

		if (newMesh->m_info.m_iCount < 0xFFFF)
		{
			newMesh->m_info.m_indexType = slMeshIndexType::u16;

			uint32_t* oldIndices = (uint32_t*)newMesh->m_indices;

			newMesh->m_indices = (uint8_t*)slMemory::malloc(newMesh->m_info.m_iCount * sizeof(uint16_t));
			uint16_t* i16 = (uint16_t*)newMesh->m_indices;

			for (uint32_t i = 0; i < newMesh->m_info.m_iCount; ++i)
			{
				*i16 = *oldIndices;
				++oldIndices;
				++i16;
			}

			indsArr.free_memory();
		}

		vertArr.m_data = 0;
		indsArr.m_data = 0;

		newMesh->m_aabb = m_aabb;

		return newMesh;
	}
	return 0;
}

Looks like everything is ok, I can't check this functions in this moment.

There is some boring classes:

Polygon

struct slPolygonVertexData
{
	slPolygonVertexData() :m_vertex(0), m_flags(0) {}
	slPolygonVertexData(slPolyVertex* v) :m_vertex(v), m_flags(0) {}
	slPolygonVertexData(slPolyVertex* v, const slVec2f& uv, const slVec3f& normal, uint32_t flags)
		:
		m_vertex(v),
		m_flags(flags)
	{
		m_baseData.UV = uv;
		m_baseData.Normal = normal;
	}

	bool operator==(const slPolygonVertexData& other) {
		return m_vertex == other.m_vertex;
	}

	enum { flag_isSelected = 1, };

	slPolyVertex* m_vertex;
	// slPolyVertex is vertex for editor, and this vertex can contain many slMesh\GPU vertices
	// slPolygonVertexData have data for each unique slMesh\GPU vertex
	slVertexTriangle m_baseData;
	uint32_t m_flags;
};
class slPolygon
{
	void* m_data = 0; //hide all in .cpp
public:
	slPolygon();
	~slPolygon();

	slPolygon* m_left = 0;
	slPolygon* m_right = 0;

	uint32_t GetFlags();

	void SelectUVs();
	void DeselectUVs();
	slListNode<slPolygonVertexData>* FindVertex(slPolyVertex* v);

	slList<slPolygonVertexData>* GetVertices();
	slList<slPolyEdge*>* GetEdges();

	bool IsVisible();
	void CalculateNormal();

	slVec3f GetFaceNormal();
	slVec3f GetFaceNormalCalculateNew();

	void Flip();

	// not guaranteed but better than nothing
	void FixOrder(float lineLineCollisionLen);
};

Edge

class slPolyEdge
{
public:
	slPolyEdge() {}
	~slPolyEdge() {}

	uint32_t m_flags = 0;
	enum
	{
		flag_isSelected = 0x1,
		flag_User1 = 0x2,
	};

	bool IsSelected() { return (m_flags & flag_isSelected) == flag_isSelected; }
	void Select() { m_flags |= flag_isSelected; }
	void Deselect() { m_flags &= ~flag_isSelected; }

	void CopyData(slPolyEdge* other) {
		m_flags = other->m_flags;
	}

	slPolyEdge* m_left = 0;
	slPolyEdge* m_right = 0;

	slPolyVertex* m_vertex1 = 0;
	slPolyVertex* m_vertex2 = 0;

	slPolygon* m_polygon1 = 0;
	slPolygon* m_polygon2 = 0;
};

Vertex

class slPolyVertex
{
public:

	slPolyVertex() {}
	~slPolyVertex() {}

	slPolyVertex* m_left = 0;
	slPolyVertex* m_right = 0;

	slVec3f m_position;

	uint32_t m_flags = 0;
	enum {
		flag_isSelected = 0x1,
		flag_User1 = 0x2,
		flag_User2 = 0x4,
	};

	bool IsSelected() { return (m_flags & flag_isSelected) == flag_isSelected; }
	void Select() { m_flags |= flag_isSelected; }
	void Deselect() { m_flags &= ~flag_isSelected; }

	void CopyData(slPolyVertex* other)
	{
		m_position = other->m_position;
		m_flags = other->m_flags;
	}


	slList<slPolygon*> m_polygons;
	slList<slPolyEdge*> m_edges;

	bool IsOnEdge();
};

Also triangle

class slPolyTriangle
{
public:
	slPolyTriangle();
	slPolyTriangle(const slVec4f& _v1, const slVec4f& _v2, const slVec4f& _v3);
	slPolyTriangle(const slVec3f& _v1, const slVec3f& _v2, const slVec3f& _v3);

	slVec4f v1;
	slVec4f v2;
	slVec4f v3;
	//v4f faceNormal;
	slVec4f normal1;
	slVec4f normal2;
	slVec4f normal3;
	slVec4f e1;
	slVec4f e2;
	slVec4f t1;
	slVec4f t2;
	slVec4f t3;

	void update();
	void center(slVec4f& out);
	bool rayTest_MT(const slRay& ray, bool withBackFace, real_t& T, real_t& U, real_t& V, real_t& W);
	bool rayTest_Watertight(const slRay& ray, bool withBackFace, real_t& T, real_t& U, real_t& V, real_t& W);
};

Array

It's like string, similar idea

// `clear` must do m_size = 0;
template<typename type>
class slArray
{
	uint32_t m_allocated;
	void reallocate(uint32_t new_capacity)
	{
		new_capacity += (uint32_t)ceilf((float)m_allocated * 0.5f);
		auto tmp_size = new_capacity * sizeof(type);
		pointer new_data = static_cast<type*>(slMemory::malloc(tmp_size));
		memset(new_data, 0, tmp_size);

		if (m_data)
		{
			for (uint32_t i = 0u; i < m_size; ++i)
			{
				new(&new_data[i]) type(m_data[i]);
				(&m_data[i])->~type();
			}
			slMemory::free(m_data);
		}
		m_data = new_data;
		m_allocated = new_capacity;
	}
public:
	typedef type* pointer;
	typedef type& reference;
	typedef const type& const_reference;

	slArray() 
		:
		m_allocated(0), 
		m_size(0), 
		m_data(0) 
	{}

List

Small part

template<typename _type>
struct slListNode{
	slListNode() :m_left(0), m_right(0) {}
	~slListNode() {}
	_type m_data;
	slListNode* m_left;
	slListNode* m_right;
};

// circular double linked list
template<typename _type>
class slList{
	slList(const slList& other) {};
	slList(slList&& other) {};
public:
	slList() :m_head(0) {}
	~slList() {
		clear();
	}

	slListNode<_type>* find(const _type& data){
		if (!m_head)
			return 0;

		auto node = m_head;
		auto last = m_head->m_left;
		while (true){
			if (node->m_data == data)
				return node;

			if (node == last)
				break;
			node = node->m_right;
		}
		return 0;
	}

	void clear(){
		if (!m_head)
			return;
		auto last = m_head->m_left;
		while (true)
		{
			auto next = m_head->m_right;
			m_head->~slListNode();
			slMemory::free(m_head);

			if (m_head == last)
				break;
			m_head = next;
		}
		m_head = nullptr;
	}

	slListNode<_type>* push_back(const _type& data){
		slListNode<_type>* node = (slListNode<_type>*)slMemory::malloc(sizeof(slListNode<_type>));
		new(node)slListNode<_type>();
		node->m_data = data;
		if (!m_head){
			m_head = node;
			m_head->m_right = m_head;
			m_head->m_left = m_head;
		}else{
			auto last = m_head->m_left;
			last->m_right = node;
			node->m_left = last;
			node->m_right = m_head;
			m_head->m_left = node;
		}
		return node;
	}
......	
	slListNode<_type>* m_head;
};

Download