Home
JAQForum Ver 20.06
Log In or Join  
Active Topics
Local Time 22:01 28 Mar 2024 Privacy Policy
Jump to

Notice. New forum software under development. It's going to miss a few functions and look a bit ugly for a while, but I'm working on it full time now as the old forum was too unstable. Couple days, all good. If you notice any issues, please contact me.

Forum Index : Microcontroller and PC projects : The Great Colour Maximite 2 Octahedron Prize Challenge

     Page 11 of 11    
Author Message
matherp
Guru

Joined: 11/12/2012
Location: United Kingdom
Posts: 8516
Posted: 03:25pm 28 Nov 2020
Copy link to clipboard 
Print this post

The 3D team

I've attached the latest hack version for you to try and help me diagnose the problem with my hidden surface algorithm


CMM2V1.5.zip

Here is the test program

option explicit
option default float
dim integer viewplane = 700
dim q(4)
dim roll=rad(0.5)
dim integer nv=9, nf=9 ' cube has 9 vertices and 9 faces
'array to hold vertices
dim v(2,nv-1)=(-1,1,-1,  1,1,-1, 1,-1,-1, -1,-1,-1, -1,1,1, 1,1,1, 1,-1,1,  -1,-1,1, 0,0,.1)
math scale v(),200,v()
' array to hold number of vertices for each face
dim integer fc(nf-1) =(4,4,4,4,4,3,3,3,3)
dim integer bcol(nf-1)=(rgb(red),rgb(blue),rgb(green),rgb(magenta),rgb(yellow),rgb(cyan),rgb(white),rgb(brown),rgb(gray))
dim integer fcol(nf-1)=(0,0,0,0,0,0,0,0,0)
'array to hold vertices for each face
dim integer fv(math(sum fc())-1)=(1,5,6,2, 1,0,4,5,  0,3,7,4,  5,4,7,6, 2,6,7,3, 0,1,8, 1,2,8, 2,3,8 , 3,0,8)
draw3d create 1, nv, nf, v(), fc(), fv(),fcol(),bcol()
dim integer c
page write 1
draw3d camera 1,viewplane, mm.hres\2, mm.vres\2, 0
for c=0 to 720
 math q_create roll,1,2,3,q()
 draw3d show 1,mm.hres\2,mm.vres\2,1000
 draw3d rotate 1,q()
 inc roll,rad(0.5)
 page copy 1 to 0,b
 do while inkey$="":loop
next
draw3d close all


If you run the code you will see a diagnostic at the top of the screen. This prints the normalised vector from the vertex to the camera x, y, and z and then the calculated surface normal of the triangle and finally the dot product of the two. This output is for the brown triangle.
If you step the program forward by pressing any key you will see the dot product slowly increasing and then when it gets positive the brown segment disappears when it clearly is still facing the camera. This is my bug I can't find.

The C source is below if it helps

for(f=0;f<struct3d[n]->nf;f++){
// calculate the surface normals for each face
vp=struct3d[n]->facestart[f];
p1.x=struct3d[n]->r_vertices[struct3d[n]->face_x_vert[vp+1]].x;
p1.y=struct3d[n]->r_vertices[struct3d[n]->face_x_vert[vp+1]].y;
p1.z=struct3d[n]->r_vertices[struct3d[n]->face_x_vert[vp+1]].z;
p2.x=struct3d[n]->r_vertices[struct3d[n]->face_x_vert[vp+2]].x;
p2.y=struct3d[n]->r_vertices[struct3d[n]->face_x_vert[vp+2]].y;
p2.z=struct3d[n]->r_vertices[struct3d[n]->face_x_vert[vp+2]].z;
p3.x=struct3d[n]->r_vertices[struct3d[n]->face_x_vert[vp]].x;
p3.y=struct3d[n]->r_vertices[struct3d[n]->face_x_vert[vp]].y;
p3.z=struct3d[n]->r_vertices[struct3d[n]->face_x_vert[vp]].z;
U.x=p2.x-p1.x;  U.y=p2.y-p1.y;  U.z=p2.z-p1.z;
V.x=p3.x-p1.x;  V.y=p3.y-p1.y;  V.z=p3.z-p1.z;
normals.x=U.y*V.z-U.z*V.y;
normals.y=U.z*V.x-U.x*V.z;
normals.z=U.x*V.y-U.y*V.x;
normalise(&normals);
ray.x=struct3d[n]->r_vertices[struct3d[n]->face_x_vert[vp+1]].x*struct3d[n]->r_vertices[struct3d[n]->face_x_vert[vp+1]].m+x-struct3d[n]->camera.x;
ray.y=struct3d[n]->r_vertices[struct3d[n]->face_x_vert[vp+1]].y*struct3d[n]->r_vertices[struct3d[n]->face_x_vert[vp+1]].m+y-struct3d[n]->camera.y;
ray.z=struct3d[n]->r_vertices[struct3d[n]->face_x_vert[vp+1]].z*struct3d[n]->r_vertices[struct3d[n]->face_x_vert[vp+1]].m+z-struct3d[n]->camera.z;
normalise(&ray);
if(f==7){
PInt(f);PFlt(ray.x);PFltComma(ray.y);PFltComma(ray.z);PFltComma(normals.x);PFltComma(normals.y);PFltComma(normals.z);
}
struct3d[n]->dots[f] = ray.x * normals.x + ray.y * normals.y + ray.z * normals.z;
depth[f]=struct3d[n]->nearest[f];
depthindex[f]=f;
if(f==7){
PFltComma(struct3d[n]->dots[f]);PRet();
}
}
// sort the distances from the camera
depthsort(depth, struct3d[n]->nf, depthindex);
// display the forward facing faces in the order of the furthest away first
for(f=0;f<struct3d[n]->nf;f++){
// sortindex=f;
sortindex=depthindex[f];
vp=struct3d[n]->facestart[sortindex];
if(struct3d[n]->dots[sortindex]<0){
for(v=0;v<struct3d[n]->facecount[sortindex];v++){
xp=struct3d[n]->r_vertices[struct3d[n]->face_x_vert[vp+v]].x*struct3d[n]->r_vertices[struct3d[n]->face_x_vert[vp+v]].m+x;
yp=struct3d[n]->r_vertices[struct3d[n]->face_x_vert[vp+v]].y*struct3d[n]->r_vertices[struct3d[n]->face_x_vert[vp+v]].m+y;
zp=struct3d[n]->r_vertices[struct3d[n]->face_x_vert[vp+v]].z*struct3d[n]->r_vertices[struct3d[n]->face_x_vert[vp+v]].m+z;
// We now have the coordinates in real space so project them
zdist=sqrt((xp-struct3d[n]->camera.x) * (xp-struct3d[n]->camera.x) +
(yp-struct3d[n]->camera.y) * (yp-struct3d[n]->camera.y) +
(zp-struct3d[n]->camera.z) * (zp-struct3d[n]->camera.z));
zratio=1.0-struct3d[n]->viewplane/zdist;
// We now know how far the point is away from the camera
xadjust=(x-xp)*zratio;
yadjust=(y-yp)*zratio;
// PFlt(zratio);PFltComma(xp);PFltComma(xadjust);PFltComma(yp);PFltComma(yadjust);PRet();
struct3d[n]->coordinates[vp+v].x=xp+xadjust;
struct3d[n]->coordinates[vp+v].y=yp+yadjust;
if(struct3d[n]->coordinates[vp+v].x>struct3d[n]->xmax)struct3d[n]->xmax=struct3d[n]->coordinates[vp+v].x;
if(struct3d[n]->coordinates[vp+v].x<struct3d[n]->xmin)struct3d[n]->xmin=struct3d[n]->coordinates[vp+v].x;
if(struct3d[n]->coordinates[vp+v].y>struct3d[n]->ymax)struct3d[n]->ymax=struct3d[n]->coordinates[vp+v].y;
if(struct3d[n]->coordinates[vp+v].y<struct3d[n]->ymin)struct3d[n]->ymin=struct3d[n]->coordinates[vp+v].y;
}
DrawPolygon(n, sortindex);
}
}

Edited 2020-11-29 01:26 by matherp
 
vegipete

Guru

Joined: 29/01/2013
Location: Canada
Posts: 1081
Posted: 05:53pm 28 Nov 2020
Copy link to clipboard 
Print this post

  matherp said  I think that in this case the act of projection can effectively "hide" faces that are pointing towards the camera and therefore some sorting of drawing order is needed but it is very difficult to demonstrate and I could be completely wrong.

Bingo! You just put it in words in a way that made it go click in my mind. Yes, it is very much the case that projection hides faces. Faces are not visible because the face normal is (even slightly) towards the camera in 3 dimensions. Faces are visible because the angle between the face normal and the line of sight to the face is less than 90 degrees.

You can solve this in two ways:
1) do the full 3D calculation - the cross product of two sides gives the face normal (make sure it's outward), then the sign of the dot product of this normal and a vector from the camera to the face (which can be the vector from the camera to any vertex of the face, or the centroid, if you choose) determines visibility. Since the dot product is given by the product of the magnitudes of the 2 vectors multiplied by the cosine of the angle between them, if the sign of the result is positive, then angle must be less than 90 degrees.
2) project the points onto the viewing plane first, then look if the projected points are clockwise or counter-clockwise. This can be done with a 2D cross product.

  matherp said  This is a harder challenge. Can anyone work out how to rotate this shape
dim integer nv=9, nf=9 ' cube with  one face concave

Oh, now you've dialed it up! You either have to calculate clipping regions, because a nearer face can _partially_ cover a farther face, or rely on painters to do the partial obscuring for you. I'd suggest solving the face visibility first, then this may be fixed for free.

  Quote  Because the triangles on the front face are equilateral the surface normal always calculates as 0!

That can't be. Something is wrong in the normal calculation. The normal can only be 0 if one of the vectors is 0.
Visit Vegipete's *Mite Library for cool programs.
 
PeteCotton

Guru

Joined: 13/08/2020
Location: Canada
Posts: 311
Posted: 06:05pm 28 Nov 2020
Copy link to clipboard 
Print this post

I've gone through the C calcs manually and can't see any problems. Is that normalise function a standard library, or is there possibly a bug in it?


normalise(&normals);
 
PeteCotton

Guru

Joined: 13/08/2020
Location: Canada
Posts: 311
Posted: 06:31pm 28 Nov 2020
Copy link to clipboard 
Print this post

  PeteCotton said  I've gone through the C calcs manually and can't see any problems. Is that normalise function a standard library, or is there possibly a bug in it?


normalise(&normals);


Actually, the more I look at this, I don't think that the vector called "normals" has been normalised.

normals.x=U.y*V.z-U.z*V.y;
normals.y=U.z*V.x-U.x*V.z;
normals.z=U.x*V.y-U.y*V.x;
normalise(&normals);
.
.
.
if(f==7){
PInt(f);PFlt(ray.x);PFltComma(ray.y);PFltComma(ray.z);PFltComma(normals.x);PFltComma(normals.y);PFltComma(normals.z);
}

If those last three numbers are the normalised vector of vector "normals", there values squared and added together should approximate 1.

At the point where the z goes positive we have the following values
x: 0.6276  y:0.1203  z:0.0014

0.6276^2 + 0.1203^2 + 0.0014^2 = 0.39388176 + 0.01447209 + 0.00000196 = ~0.4
Edited 2020-11-29 04:33 by PeteCotton
 
matherp
Guru

Joined: 11/12/2012
Location: United Kingdom
Posts: 8516
Posted: 06:52pm 28 Nov 2020
Copy link to clipboard 
Print this post

Got it
 
PeteCotton

Guru

Joined: 13/08/2020
Location: Canada
Posts: 311
Posted: 06:57pm 28 Nov 2020
Copy link to clipboard 
Print this post

  matherp said  Got it


Fantastic!
 
matherp
Guru

Joined: 11/12/2012
Location: United Kingdom
Posts: 8516
Posted: 07:24pm 28 Nov 2020
Copy link to clipboard 
Print this post

Pete

Do you have the coordinates for the Elite Spacestation that you fly into?
Edited 2020-11-29 05:40 by matherp
 
PeteCotton

Guru

Joined: 13/08/2020
Location: Canada
Posts: 311
Posted: 08:07pm 28 Nov 2020
Copy link to clipboard 
Print this post

  matherp said  Pete

Do you have the coordinates for the Elite Spacestation that you fly into?


Sure. The Coriolis station.


#VRML V2.0 utf8

Shape {
geometry IndexedFaceSet {
coordIndex [
0, 1, 2, 3, -1,
0, 1, 5, -1,
0, 3, 4, -1,
0, 4, 8, 5, -1,
1, 2, 6, -1,
1, 6, 9, 5, -1,
2, 3, 7, -1,
2, 6, 10, 7, -1,
3, 4, 11, 7, -1,
4, 8, 11, -1,
5, 8, 9, -1,
6, 9, 10, -1,
7, 10, 11, -1,
8, 9, 10, 11, -1
]

coord Coordinate { point [
160 0 160,
0 160 160,
-160 0 160,
0 -160 160,
160 -160 0,
160 160 0,
-160 160 0,
-160 -160 0,
160 0 -160,
0 160 -160,
-160 0 -160,
0 -160 -160,
10 -30 160,
10 30 160,
-10 30 160,
-10 -30 160
]
}

solid FALSE
}

appearance Appearance {
material Material {
shininess 0.2
specularColor 1 1 1
diffuseColor 0.8 0.8 0.9
}
}
}


All of the files are available in this .zip

EliteShips.zip

This file foramt is .wrl. It looks pretty easy to understand. I might write a wee conversion program tomorrow to read them and convert them in to CMM2 3D objects (I am running around today).
 
vegipete

Guru

Joined: 29/01/2013
Location: Canada
Posts: 1081
Posted: 08:48pm 28 Nov 2020
Copy link to clipboard 
Print this post

  PeteCotton said  All of the files are available in this .zip

EliteShips.zip

This file foramt is .wrl. It looks pretty easy to understand. I might write a wee conversion program tomorrow to read them and convert them in to CMM2 3D objects (I am running around today).

Nasty. Some of the data is comma delimited, some is space delimited. That's just evil.  
Visit Vegipete's *Mite Library for cool programs.
 
vegipete

Guru

Joined: 29/01/2013
Location: Canada
Posts: 1081
Posted: 09:18pm 28 Nov 2020
Copy link to clipboard 
Print this post

On the bright side, 3D Builder, which is built in to windows 10, can open these VRML files with a double-click.

FreeCAD, available for windows, mac and linux, can also natively open them.

Both of these programs make it easy to view this file type. I suppose it makes sense that the VRML format be the default 3d file format.
"draw3D load #n, filename$" perhaps?
Visit Vegipete's *Mite Library for cool programs.
 
PeteCotton

Guru

Joined: 13/08/2020
Location: Canada
Posts: 311
Posted: 07:49am 29 Nov 2020
Copy link to clipboard 
Print this post

I have hacked together a very rudimentary .WRL loader. And when I say hacked - I do mean hacked. The code is a mess. I will re-write it with some nice string handling functions - this was really just cut#1 to get it working.

The data seems to be loaded in to the 3D object okay, but some of the faces are missing. I suspect that maybe they aren't all in right hand notation after all? Or is this possibly the face removal bug matherp found earlier?

Either way, it's 12.45am and I need my beauty sleep. I will look at it again tomorrow.

Like I say, don't judge me on the horrible state of this code - it will be much cleaner once I am happy it is working.


option explicit
option default float
dim integer camera_y = mm.vres-20
dim integer viewplane = 700
dim integer camera_z = 0
dim integer camera_x
dim integer c,t,s
timer=0
dim q(4)
dim yaw=rad(1),pitch=rad(2),roll=rad(0.5)
DiskRead(1,"..\EliteShips\coriolis.wrl")

draw3d camera 1,viewplane,camera_x,camera_y,camera_z

'gui cursor on 1,40,camera_y
page write 1

for c=0 to 7200
camera_x=c+40
draw3d show 1,mm.hres\4,mm.vres\2,1000'
math q_euler yaw,pitch,roll,q()
draw3d rotate 1,q()   ' rotate this object #
inc yaw,rad(0.1)
' inc pitch,rad(2)
' inc roll,rad(0.5)
page copy 1 to 0,b
next
page write 0
print 720000/timer
draw3d close all
end

sub DiskRead(objNum as integer, filename as string)
 local string dataLine$, a$, vert$, face$
 local integer readingVertices=0
 local integer readingFaces=0
 local integer t,j
 local integer temp, faceCount,VertCount, index1, index2, index3
 'Pass 1 get the data out of the file and in to vert$ and face$
 open filename for input as #1
 do  while not eof(1)
   line input #1,a$
   a$=Trim$(a$) ' Get rid of any leading or trailing spaces
   ' strip all formatting out of input line
   dataLine$=""
   for t=1 to len(a$)
     if asc(mid$(a$,t,1))>=32 then dataLine$=dataLine$ + mid$(a$,t,1)
   next t
   if left$(dataLine$,10)="coordIndex" then readingVertices=0:readingFaces=1
   if left$(dataLine$,16) = "coord Coordinate" then readingVertices=1:readingFaces=0
   if left$(dataLine$,1)="]" then readingVertices=0:readingFaces=0
   if left$(dataLine$,1)="-" or (asc(left$(dataLine$,1))>47 and asc(left$(dataLine$,1))<58) then
     ' This line starts with a number
     if readingVertices=1 then vert$=vert$+dataLine$
     if readingFaces=1 then face$=face$+dataLine$
   endif
 loop
 
 close #1
 'vert$ is 3 points seperated by spaces. Each 3 points are then seperated by a comma
 ' count the nuber of verts
 for t=1 to len(vert$)
   if mid$(vert$,t,1)="," then vertCount=vertCount+1
 next t
 vertCount=vertCount+1' The last item does not have a comma - so compensate for that

 ' face$ uses 4 or 5 numbers seperated by commas. -1 is used as the terminator
 ' Count the number of -1's to give us the face count
 for t=1 to len(face$)
   if val(mid$(face$,t,2))=-1 then temp=temp+1
 next t
 faceCount=temp

 'load the face$ and vert$ data in to our 3D object
 local float v(2,vertCount-1)
 index1=0
 index2=0
 a$=""
 for t=1 to len(vert$)
   if mid$(vert$,t,1)="," then
     v(index2,index1)=val(a$):index1=index1+1:index2=0:a$="" ' New vertice next
   else if mid$(vert$,t,1)=" " then
     v(index2,index1)=val(a$):index2=index2+1:a$=""
   else
     a$=a$+mid$(vert$,t,1)
   end if
 next t
 v(index2,index1)=val(a$) ' be sure to catch the last value as it's not ended with a comma

 local string faceData(faceCount-1)
 local integer fc(faceCount-1)
 index1=0  ' position in array faceData() and fc()
 index2=0  ' face count
 a$=""
 for t=1 to len(face$)
   if mid$(face$,t,1)="-" then 'end of this group
     t=t+1 'this is really naughty- but I'll fix it in a later rev
     faceData(index1)=a$
     fc(index1)=index2
     index1=index1+1
     index2=0
     a$=""
   else if mid$(face$,t,1)="," then
     if a$<>"" then index2=index2+1:a$=a$+","
   else
     a$=a$+mid$(face$,t,1)
   endif
 next t


 local integer bcol(faceCount-1)
 for t=0 to faceCount-1
   bcol(t)=rgb(100+rnd*155,100+rnd*155, 100+rnd*155)
 next t

 local integer fv(math(sum fc())-1)
 index1=0  ' position in array fv()
 a$=""
 for t=0 to faceCount-1
   a$=""
   for j=1 to len(faceData(t))
     if mid$(faceData(t),j,1)="," then
       fv(index1)=val(a$)
       a$=""
       index1=index1+1
     else
       a$=a$+mid$(faceData(t),j,1)
     endif
   next j
 next t

 draw3d create objNum, vertCount, faceCount, v(), fc(), fv(),bcol(),bcol()
end sub

function LTrim$(a$)
 LTrim$=a$
 do while instr(" ", left$(LTrim$,1))
   LTrim$=Mid$(Ltrim$,2)
 loop
end function

function RTrim$(a$)
 RTrim$=a$
 do while instr(" ", right$(RTrim$,1))
   RTrim$=Mid$(Rtrim$,1,len(RTrim$)-1)
 loop
end function

function Trim$(a$)
 Trim$=RTrim$(LTrim$(a$))
end function

 
LeoNicolas

Guru

Joined: 07/10/2020
Location: Canada
Posts: 432
Posted: 08:49am 29 Nov 2020
Copy link to clipboard 
Print this post

Very cool Peter. Concave faces should be resolved with Painter or Z-buffer.

I'm still working on the camera example but I do not have a lot of time to work on it because I'm studying for a certification exam.

How are you thinking to implement the camera?
 
     Page 11 of 11    
Print this page


To reply to this topic, you need to log in.

© JAQ Software 2024