OniSplit/Akira/Polygon2Clipper.cs

using System;
using System.Collections.Generic;

namespace Oni.Akira
{
    internal struct Polygon2Clipper
    {
        private readonly List<Polygon2> result;
        private readonly RoomBspNode bspTree;

        #region private struct Line

        private struct Line
        {
            private float a, c, d;

            public Line(Plane plane)
            {
                a = plane.Normal.X;
                c = plane.Normal.Z;
                d = plane.D;
            }

            public int RelativePosition(Vector2 point)
            {
                float r = a * point.X + c * point.Y + d;

                if (r < -0.00001f)
                    return -1;
                else if (r > 0.00001f)
                    return 1;
                else
                    return 0;
            }

            public Vector2 Intersect(Vector2 p0, Vector2 p1)
            {
                if (p0.X == p1.X)
                {
                    float x = p0.X;
                    float y = (d + a * x) / -c;
                    return new Vector2(x, y);
                }
                else if (p0.Y == p1.Y)
                {
                    float x = (-c * p0.Y - d) / a;
                    float y = p0.Y;
                    return new Vector2(x, y);
                }
                else
                {
                    float m = (p1.Y - p0.Y) / (p1.X - p0.X);
                    float x = (c * m * p0.X - c * p0.Y - d) / (a + c * m);
                    float y = m * (x - p0.X) + p0.Y;
                    return new Vector2(x, y);
                }
            }
        }

        #endregion

        public Polygon2Clipper(RoomBspNode bspTree)
        {
            this.result = new List<Polygon2>();
            this.bspTree = bspTree;
        }

        public IEnumerable<Polygon2> Clip(Polygon2 polygon)
        {
            result.Clear();
            Clip(new[] { polygon }, bspTree);
            return result;
        }

        private void Clip(IEnumerable<Polygon2> polygons, RoomBspNode node)
        {
            var negative = new List<Polygon2>();
            var positive = new List<Polygon2>();

            var plane = node.Plane;

            if (Math.Abs(plane.Normal.Y) > 0.001f)
            {
                negative.AddRange(polygons);
                positive.AddRange(polygons);
            }
            else
            {
                var line = new Line(plane);

                foreach (Polygon2 polygon in polygons)
                    Clip(polygon, line, negative, positive);
            }

            if (node.FrontChild != null)
                Clip(positive, node.FrontChild);

            if (node.BackChild != null)
                Clip(negative, node.BackChild);
            else
                result.AddRange(negative);
        }

        private static void Clip(Polygon2 polygon, Line line, List<Polygon2> negative, List<Polygon2> positive)
        {
            var signs = new int[polygon.Length];
            int positiveCount = 0, negativeCount = 0;

            for (int i = 0; i < polygon.Length; i++)
            {
                signs[i] = line.RelativePosition(polygon[i]);

                if (signs[i] >= 0)
                    positiveCount++;

                if (signs[i] <= 0)
                    negativeCount++;
            }

            if (negativeCount == polygon.Length)
            {
                //
                // All points are in the negative half plane, nothing to clip.
                //

                negative.Add(polygon);
                return;
            }

            if (positiveCount == polygon.Length)
            {
                //
                // All points are in the positive half plane, nothing to clip.
                //

                positive.Add(polygon);
                return;
            }

            var negativePoints = new List<Vector2>();
            var positivePoints = new List<Vector2>();

            int start = 0;
            Vector2 p0;
            int s0;

            do
            {
                p0 = polygon[start];
                s0 = signs[start];
                start++;

                //
                // do not start right on the clip line
                //

            } while (s0 == 0);

            var intersections = new Vector2[2];
            int intersectionCount = 0;

            for (int i = 0; i < polygon.Length; i++)
            {
                Vector2 p1 = polygon[(i + start) % polygon.Length];
                int s1 = signs[(i + start) % polygon.Length];

                if (s0 == s1)
                {
                    //
                    // Same half plane, no intersection, add the existing edge.
                    //

                    if (s0 < 0)
                        negativePoints.Add(p0);
                    else
                        positivePoints.Add(p0);
                }
                else if (s0 == 0)
                {
                    //
                    // If the previous point was on the clip line then we need
                    // to use the current point sign to figure out the destination polygon.
                    //

                    if (s1 < 0)
                        negativePoints.Add(p0);
                    else
                        positivePoints.Add(p0);
                }
                else
                {
                    //
                    // Different half plane, split the edge in two.
                    //

                    Vector2 intersection;

                    if (s1 == 0)
                        intersection = p1;
                    else
                        intersection = line.Intersect(p0, p1);

                    intersections[intersectionCount++] = intersection;

                    if (s0 < 0)
                    {
                        // the negative polygon needs to be closed
                        // the positive polygon needs to have an edge added from the previous intersection to the new one

                        negativePoints.Add(p0);

                        if (intersectionCount == 2)
                        {
                            negativePoints.Add(intersection);
                            positivePoints.Add(intersections[0]);
                        }

                        if (s1 != 0)
                            positivePoints.Add(intersection);
                    }
                    else
                    {
                        // the positive polygon needs to be closed
                        // the negative polygon needs to have an edge added from the previous intersection to the new one

                        positivePoints.Add(p0);

                        if (intersectionCount == 2)
                        {
                            positivePoints.Add(intersection);
                            negativePoints.Add(intersections[0]);
                        }

                        if (s1 != 0)
                            negativePoints.Add(intersection);
                    }
                }

                p0 = p1;
                s0 = s1;
            }

            negative.Add(new Polygon2(negativePoints.ToArray()));
            positive.Add(new Polygon2(positivePoints.ToArray()));
        }
    }
}
Revision:	1114
Committed:	Wed Jan 22 14:08:57 2020 UTC (5 years, 8 months ago) by iritscen
File size:	7567 byte(s)
Log Message:	Adding OniSplit source code (v0.9.99.0). Many thanks to Neo for all his work over the years.
#	Content
1	using System;
2	using System.Collections.Generic;
3
4	namespace Oni.Akira
5	{
6	internal struct Polygon2Clipper
7	{
8	private readonly List<Polygon2> result;
9	private readonly RoomBspNode bspTree;
10
11	#region private struct Line
12
13	private struct Line
14	{
15	private float a, c, d;
16
17	public Line(Plane plane)
18	{
19	a = plane.Normal.X;
20	c = plane.Normal.Z;
21	d = plane.D;
22	}
23
24	public int RelativePosition(Vector2 point)
25	{
26	float r = a * point.X + c * point.Y + d;
27
28	if (r < -0.00001f)
29	return -1;
30	else if (r > 0.00001f)
31	return 1;
32	else
33	return 0;
34	}
35
36	public Vector2 Intersect(Vector2 p0, Vector2 p1)
37	{
38	if (p0.X == p1.X)
39	{
40	float x = p0.X;
41	float y = (d + a * x) / -c;
42	return new Vector2(x, y);
43	}
44	else if (p0.Y == p1.Y)
45	{
46	float x = (-c * p0.Y - d) / a;
47	float y = p0.Y;
48	return new Vector2(x, y);
49	}
50	else
51	{
52	float m = (p1.Y - p0.Y) / (p1.X - p0.X);
53	float x = (c * m * p0.X - c * p0.Y - d) / (a + c * m);
54	float y = m * (x - p0.X) + p0.Y;
55	return new Vector2(x, y);
56	}
57	}
58	}
59
60	#endregion
61
62	public Polygon2Clipper(RoomBspNode bspTree)
63	{
64	this.result = new List<Polygon2>();
65	this.bspTree = bspTree;
66	}
67
68	public IEnumerable<Polygon2> Clip(Polygon2 polygon)
69	{
70	result.Clear();
71	Clip(new[] { polygon }, bspTree);
72	return result;
73	}
74
75	private void Clip(IEnumerable<Polygon2> polygons, RoomBspNode node)
76	{
77	var negative = new List<Polygon2>();
78	var positive = new List<Polygon2>();
79
80	var plane = node.Plane;
81
82	if (Math.Abs(plane.Normal.Y) > 0.001f)
83	{
84	negative.AddRange(polygons);
85	positive.AddRange(polygons);
86	}
87	else
88	{
89	var line = new Line(plane);
90
91	foreach (Polygon2 polygon in polygons)
92	Clip(polygon, line, negative, positive);
93	}
94
95	if (node.FrontChild != null)
96	Clip(positive, node.FrontChild);
97
98	if (node.BackChild != null)
99	Clip(negative, node.BackChild);
100	else
101	result.AddRange(negative);
102	}
103
104	private static void Clip(Polygon2 polygon, Line line, List<Polygon2> negative, List<Polygon2> positive)
105	{
106	var signs = new int[polygon.Length];
107	int positiveCount = 0, negativeCount = 0;
108
109	for (int i = 0; i < polygon.Length; i++)
110	{
111	signs[i] = line.RelativePosition(polygon[i]);
112
113	if (signs[i] >= 0)
114	positiveCount++;
115
116	if (signs[i] <= 0)
117	negativeCount++;
118	}
119
120	if (negativeCount == polygon.Length)
121	{
122	//
123	// All points are in the negative half plane, nothing to clip.
124	//
125
126	negative.Add(polygon);
127	return;
128	}
129
130	if (positiveCount == polygon.Length)
131	{
132	//
133	// All points are in the positive half plane, nothing to clip.
134	//
135
136	positive.Add(polygon);
137	return;
138	}
139
140	var negativePoints = new List<Vector2>();
141	var positivePoints = new List<Vector2>();
142
143	int start = 0;
144	Vector2 p0;
145	int s0;
146
147	do
148	{
149	p0 = polygon[start];
150	s0 = signs[start];
151	start++;
152
153	//
154	// do not start right on the clip line
155	//
156
157	} while (s0 == 0);
158
159	var intersections = new Vector2[2];
160	int intersectionCount = 0;
161
162	for (int i = 0; i < polygon.Length; i++)
163	{
164	Vector2 p1 = polygon[(i + start) % polygon.Length];
165	int s1 = signs[(i + start) % polygon.Length];
166
167	if (s0 == s1)
168	{
169	//
170	// Same half plane, no intersection, add the existing edge.
171	//
172
173	if (s0 < 0)
174	negativePoints.Add(p0);
175	else
176	positivePoints.Add(p0);
177	}
178	else if (s0 == 0)
179	{
180	//
181	// If the previous point was on the clip line then we need
182	// to use the current point sign to figure out the destination polygon.
183	//
184
185	if (s1 < 0)
186	negativePoints.Add(p0);
187	else
188	positivePoints.Add(p0);
189	}
190	else
191	{
192	//
193	// Different half plane, split the edge in two.
194	//
195
196	Vector2 intersection;
197
198	if (s1 == 0)
199	intersection = p1;
200	else
201	intersection = line.Intersect(p0, p1);
202
203	intersections[intersectionCount++] = intersection;
204
205	if (s0 < 0)
206	{
207	// the negative polygon needs to be closed
208	// the positive polygon needs to have an edge added from the previous intersection to the new one
209
210	negativePoints.Add(p0);
211
212	if (intersectionCount == 2)
213	{
214	negativePoints.Add(intersection);
215	positivePoints.Add(intersections[0]);
216	}
217
218	if (s1 != 0)
219	positivePoints.Add(intersection);
220	}
221	else
222	{
223	// the positive polygon needs to be closed
224	// the negative polygon needs to have an edge added from the previous intersection to the new one
225
226	positivePoints.Add(p0);
227
228	if (intersectionCount == 2)
229	{
230	positivePoints.Add(intersection);
231	negativePoints.Add(intersections[0]);
232	}
233
234	if (s1 != 0)
235	negativePoints.Add(intersection);
236	}
237	}
238
239	p0 = p1;
240	s0 = s1;
241	}
242
243	negative.Add(new Polygon2(negativePoints.ToArray()));
244	positive.Add(new Polygon2(positivePoints.ToArray()));
245	}
246	}
247	}